决策树算法

基本结构

决策树是一个类似流程图的树形结构：其中，每个节点表示在一个属性上的测试。每个分支表示一个输出，每个树叶节点代表类或类的分布。

上面这个例子中play和don’t play是结果，表示玩还是不玩。然后不是叶结点的节点都有一个问号，例如第一个outlook询问的是天气，后面还有湿度和是否刮风。通过这些条件得到了叶节点，叶结点都是只包含一种情况，要么是play要么是don’t play。

我们可以把OUTLOOK，HUMIDITY等称为属性，把其中的每一个选项称为类

现在问题的关键是如何确定进行划分的属性

决策树归纳算法（ID3）

决策树适合小规模，类别比较少的数据集。

确定属性的基础就是信息熵，这可以用来表示我们可以获得信息的多少，信息增益多我们就可以认为它对我们有帮助。

我们以此图为例来讲解求解过程。首先最后一行是我们想要知道的答案

首先期望获得的信息可以由以下公式给出

$$\begin{aligned} I(s_1 ,s_2 ,s_3 ..., s_m ) = -\sum_i p_i \log_2 (p_i ) \end{aligned}$$

上述公式中$s_m$是结果中的第几类，也就是上例中的买电脑和不买电脑。

之后我们就需要对每一类求出它的信息熵值

$$\begin{aligned} &p_{ij} = \frac{s_{ij}}{|s_{j}|} \\ &I(s_{1j}, s_{2j}, ..., s_{mj}) = - \sum_{i=1}^m p_{ij} \log_2 (p_{ij}) \\ &E(A) = \sum_{j=1}^{v} \frac{s_{ij} I(s_{1j}, s_{2j}, ..., s_{mj})}{s} \end{aligned}$$

其中$p_{ij}$表示在某个属性中第j个类是第i种结果的概率。（待会看例子就明白了）。而E(A)就是我们求得的信息熵。

然后通过下式求解出收益，选择收益最大的来划分。

$$Gain(A) = I(s_1 ,s_2 ,s_3 ..., s_m ) - E(A)$$

上面这个例子中，后面age的计算是该种类的概率（如5/14或4/14等）* 在这个种类里的信息获取量。上面青年有五种，然后求得五种里买电脑或者不买电脑的信息获取量。

最后可以求得gain，然后选取gain最大的作为该节点。 通过划分后如果只有一种目标，那么划分结束，如果有多种目标，那么重新用这种方法选取gain最大的。

如果所有属性都用完了，那么采用多数表决，即哪个结果多就把它划分成哪个类。例如最后所有属性都使用了一遍，最后三人买电脑，两人不买电脑，那么最后就把它划分成买电脑类。

如果分的太细也可能出现问题。所以有时候达到一定纯度就不再往下分。还可以先全部分完然后再剪。

如果属性过多可能导致树过深，这是就需要采用预剪枝技术，一种方法是直接限制树的最大高度。另一种方法是通过一些统计检验的方法，评估每次节点分裂对性能的增益，如果增益小于某一值则停止剪枝

运用

python中有一个scikit-learn库包含了决策树。

首先sklearn要求输入的属性值必须是数值型的值而不能是young，old之类模糊的数据。

具体可以变成由0和1组成的集合。例如假如是young，那么按照young Middle old排列的话取值是100，如果是middle那么就是010.

所有特征值形成了一串0和1,以这个作为输入。

python中提供了一个函数可以直接把属性转化成01， 他叫DictVectorizer(),使用它的条件是我们把属性转化成了一个列表（所有样例构成一个列表，但是单个样例可以用字典进行描述)

这是上例所形成的列表

vec = DictVectorizer()
dummyx = vec.fit_transform(featurelist).toarray()

输出

这是对于特征值的，对于目标标记也有专门的方法

lb = processing.LabelBinarizer()
dummyY = lb.fit_transform(labellist)

创建分类器

前面都是对数据进行预处理，预处理完毕之后我们就要把它转换成决策树模型了。

clf = tree.DecesionTreeClassifier(criterion = 'entropy') #criterion是使用的决策树算法，具体可以看文档
ans = clf.fit(dummyX, dummyY)

可视化

虽然我们产生了结果，但是结果非常不直观，我们可以用graphviz将结果变成上面看到的图。

with open("allElectronicInformationGainOri.dot", 'w') as f:
    f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file=f) # feature_names是属性的名字，因为在形成决策树过程中全变成0和1了

通过这两行代码可以把结果输出到文件中可以看到结果非常不直观，因此我们还需用graphviz进一步转化。

在cmd中输入dot -Tpdf iris.dot -o output.pdf iris.dot是原始文件的路径，-o是输出文件名

from sklearn.feature_extraction import DictVectorizer
import csv
from sklearn import tree
from sklearn import preprocessing
from sklearn.externals.six import StringIO

# Read in the csv file and put features into list of dict and list of class label
allElectronicsData = open(r'/home/zhoumiao/MachineLearning/01decisiontree/AllElectronics.csv', 'rb')
reader = csv.reader(allElectronicsData)
headers = reader.next()

print(headers)

featureList = []
labelList = []

for row in reader:
    labelList.append(row[len(row)-1])
    rowDict = {}
    for i in range(1, len(row)-1):
        rowDict[headers[i]] = row[i]
    featureList.append(rowDict)

print(featureList)

# Vetorize features
vec = DictVectorizer()
dummyX = vec.fit_transform(featureList) .toarray()

print("dummyX: " + str(dummyX))
print(vec.get_feature_names())

print("labelList: " + str(labelList))

# vectorize class labels
lb = preprocessing.LabelBinarizer()
dummyY = lb.fit_transform(labelList)
print("dummyY: " + str(dummyY))

# Using decision tree for classification
# clf = tree.DecisionTreeClassifier()
clf = tree.DecisionTreeClassifier(criterion='entropy')
clf = clf.fit(dummyX, dummyY)
print("clf: " + str(clf))


# Visualize model
with open("allElectronicInformationGainOri.dot", 'w') as f:
    f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file=f)

oneRowX = dummyX[0, :]
print("oneRowX: " + str(oneRowX))

newRowX = oneRowX
newRowX[0] = 1
newRowX[2] = 0
print("newRowX: " + str(newRowX))

predictedY = clf.predict(newRowX) # 创建一个新的节点然后预测
print("predictedY: " + str(predictedY))