机器学习实战之决策树（基础）

信息：若Xi(i=1,2,...n)为分类类别，则信息值 $\mathbf{i}$ (Xi) = $-\log _{2}^{\mathbf{p}(Xi)}$ .(X为某一特征)

熵：（随机变量的不确定性的度量）信息的数学期望。E = $\sum_{i=1}^{n}\mathbf{p}(Xi)\cdot \mathbf{i}(Xi)$

经验熵：概率由数学估计得到。

 1 # -*- coding: UTF-8 -*-
 2 from math import log
 3 def createDataSet():
 4     dataSet = [[0, 0, 0, 0, 'no'],         #数据集
 5             [0, 0, 0, 1, 'no'],
 6             [0, 1, 0, 1, 'yes'],
 7             [0, 1, 1, 0, 'yes'],
 8             [0, 0, 0, 0, 'no'],
 9             [1, 0, 0, 0, 'no'],
10             [1, 0, 0, 1, 'no'],
11             [1, 1, 1, 1, 'yes'],
12             [1, 0, 1, 2, 'yes'],
13             [1, 0, 1, 2, 'yes'],
14             [2, 0, 1, 2, 'yes'],
15             [2, 0, 1, 1, 'yes'],
16             [2, 1, 0, 1, 'yes'],
17             [2, 1, 0, 2, 'yes'],
18             [2, 0, 0, 0, 'no']]
19     labels = ['年龄', '有工作', '有自己的房子', '信贷情况']        #分类属性
20     return dataSet, labels                #返回数据集和分类属性
21 
22 
23 #函数说明:计算给定数据集的经验熵(香农熵)
24 def calcShannonEnt(dataSet):
25     numEntires = len(dataSet)                        #返回数据集的行数
26     labelCounts = {}                                #保存每个标签(Label)出现次数的字典
27     for featVec in dataSet:                            #对每组特征向量进行统计
28         currentLabel = featVec[-1]                    #提取标签(Label)信息
29         labelCounts[currentLabel] = labelCounts.get(currentLabel,0)+1 #Label计数,如果标签(Label)没有放入统计次数的字典,添加进去
30              
31     shannonEnt = 0.0                                #经验熵(香农熵)
32     for key in labelCounts:                            #计算香农熵
33         prob = float(labelCounts[key]) / numEntires    #选择该标签(Label)的概率
34         shannonEnt -= prob * log(prob, 2)            #利用公式计算
35     return shannonEnt                           #返回经验熵(香农熵)
36 
37 if __name__ == '__main__':
38     dataSet, features = createDataSet()
39     print(dataSet)
40     print(calcShannonEnt(dataSet))

条件熵H(Y|X)：表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) 定义为X给定条件下，Y的条件概率分布的熵（H(Y|Xi)）对X的数学期望：

$H(Y|X) = \sum_{i=1}^{n}\mathbf{pi}\cdot \mathbf{H}(Y|Xi)$ , 其中 $pi=p(X=Xi)$ , i=1,2,3...n。

信息增益(互信息)：相对于某个特征而言。决策树学习中的信息增益等价于训练数据集中类(标签)与特征的互信息。因此特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即 $\mathbf{g}(D,A) = H(D) - H(D|A)$ = $H(D)-\sum_{i=1}^{n}\mathbf{pi}\cdot \mathbf{H}(Y|Ai)$

以代码中数据为例，A可以是年龄，则Ai可取青年(i=1)，中年(i=2)，老年(i=3)。H（D）即为标签类别(Yes/No)的熵，H(D|A1)即为青年样本对分类标签的熵，p1=青年样本数/样本总数。

 1 # -*- coding: UTF-8 -*-
 2 from math import log
 3 
 4 """
 5 函数说明:计算给定数据集的经验熵(香农熵)
 6 
 7 """
 8 def calcShannonEnt(dataSet):
 9     numEntires = len(dataSet)                        #返回数据集的行数
10     labelCounts = {}                                #保存每个标签(Label)出现次数的字典
11     for featVec in dataSet:                            #对每组特征向量进行统计
12         currentLabel = featVec[-1]                    #提取标签(Label)信息
13         labelCounts[currentLabel] = labelCounts.get(currentLabel,0)+1 #Label计数,如果标签(Label)没有放入统计次数的字典,添加进去
14 
15     shannonEnt = 0.0                                #经验熵(香农熵)
16     for key in labelCounts:                            #计算香农熵
17         prob = float(labelCounts[key]) / numEntires    #选择该标签(Label)的概率
18         shannonEnt -= prob * log(prob, 2)            #利用公式计算
19     return shannonEnt                                #返回经验熵(香农熵)
20 
21 """
22 函数说明:创建测试数据集
23 """
24 def createDataSet():
25     dataSet = [[0, 0, 0, 0, 'no'],                        #数据集
26             [0, 0, 0, 1, 'no'],
27             [0, 1, 0, 1, 'yes'],
28             [0, 1, 1, 0, 'yes'],
29             [0, 0, 0, 0, 'no'],
30             [1, 0, 0, 0, 'no'],
31             [1, 0, 0, 1, 'no'],
32             [1, 1, 1, 1, 'yes'],
33             [1, 0, 1, 2, 'yes'],
34             [1, 0, 1, 2, 'yes'],
35             [2, 0, 1, 2, 'yes'],
36             [2, 0, 1, 1, 'yes'],
37             [2, 1, 0, 1, 'yes'],
38             [2, 1, 0, 2, 'yes'],
39             [2, 0, 0, 0, 'no']]
40     labels = ['年龄', '有工作', '有自己的房子', '信贷情况']        #分类属性
41     return dataSet, labels                             #返回数据集和分类属性
42 
43 """
44 函数说明:按照给定特征划分数据集
45 
46 Parameters:
47     dataSet - 待划分的数据集
48     index - 划分数据集的特征，代表第几个特征，如年龄。
49     value - 需要返回的特征的值，代表该特征下的某个分类，如年龄下的中年。
50 """
51 def splitDataSet(dataSet, index, value):     
52     retDataSet = []                                        #创建返回的数据集列表
53     for featVec in dataSet:                             #遍历数据集
54         if featVec[index] == value:
55     #将符合条件的添加到返回的数据集
56             retDataSet.append(featVec)
57     return retDataSet                                      #返回划分后的数据集
58 
59 """
60 函数说明:选择最优特征
61 
62 Parameters:
63     dataSet - 数据集
64 Returns:
65     bestFeature - 信息增益最大的(最优)特征的索引值
66 """
67 def chooseBestFeature(dataSet):
68     numFeatures = len(dataSet[0]) - 1                    #特征数量
69     baseEntropy = calcShannonEnt(dataSet)                 #计算数据集的香农熵
70     bestInfoGain = 0.0                                  #信息增益
71     bestFeature = -1                                    #最优特征的索引值
72     for i in range(numFeatures):                         #遍历所有特征
73         #获取dataSet的第i个所有特征
74         featList = [item[i] for item in dataSet]
75         uniqueVals = set(featList)                         #以列表创建set集合{},元素不可重复
76         newEntropy = 0.0                                  #经验条件熵
77         for value in uniqueVals:                         #计算信息增益
78             subDataSet = splitDataSet(dataSet, i, value)         #subDataSet划分后的子集
79             prob = len(subDataSet) / float(len(dataSet))           #计算子集的概率
80             newEntropy += prob * calcShannonEnt(subDataSet)     #根据公式计算经验条件熵
81         infoGain = baseEntropy - newEntropy                     #信息增益
82         print("第%d个特征的增益为%.3f" % (i, infoGain))            #打印每个特征的信息增益
83         if (infoGain > bestInfoGain):                             #计算信息增益
84             bestInfoGain = infoGain                             #更新信息增益，找到最大的信息增益
85             bestFeature = i                                     #记录信息增益最大的特征的索引值
86     return bestFeature                                             #返回信息增益最大的特征的索引值
87 
88 if __name__ == '__main__':
89     dataSet, features = createDataSet()
90     print("最优特征索引值:" + str(chooseBestFeature(dataSet)))

决策树算法实现步骤：

计算经验熵；
选择最优特征；
递归。

常用的有CART, C4.5。