机器学习-决策树
一、总览
决策树是一种很常用也是很有效的分类和回归方法，属于有监督的学习，呈树形结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一个实例，它是以实例为基础的归纳学习。
决策树学习采用的是自顶向下的递归方法，基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点的实例都属于同一类。
决策树的本质是从训练数据集中归纳出一组分类规则，选择一个与训练数据集矛盾最小的树，不仅对于训练数据有很好的拟合，而且对于未来的数据也有很好的预测作用。所以决策树采用损失函数表示这一目标，策略就是以损失函数为目标的最小化。实际中从所有可能的决策树中选取最优的是NP完全问题，所以实际上得到的是一个次最优的树。
此外通过训练数据生成的决策树可能对于训练数据集有很好的拟合作用，但可能会产生过拟合现象，所以我们需要对已生成的树进行自下而上的剪枝，使其具有很好的泛化能力，通常有预剪枝和后剪枝。
优点是可读性好、分类速度快，可以自学习，在学习的过程中不需要了解太多背景知识，只需要对训练实例进行较好的标注就可以学习。主要的决策树算法有C4.5、ID3和CART算法。
二、决策树
决策树算法的基本过程：
-
开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
-
如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
-
如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。
4）每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。
通过一个简单的数据集来看一下，样本中我们根据房产情况、婚姻情况和年收入来判定是否可以偿还债务：
假设我们可以得到如下的一颗决策树：
从图中的树我们可以看出，利用了三个特征进行分类，那么具体为什么首选拥有房产这个特征而不选择其他的特征呢？这就是很重要的一个特征选择的问题，选择对训练数据具有分类能力的特征，可以提升决策树的学习效率，如果某一特征没有分类能力，舍弃掉也影响不大。通常特征选择的准则有信息增益、信息增益比和基尼系数。
1.熵
假设数据集D中数据x满足概率分布 P(X = xi) = pi，i=1，2，3…n，在信息论中我们定义X的信息熵就是：
其中规定若pi = 0，则0log0 = 0，log函数分别以2和e为底时，单位是比特和纳特，熵只依赖于X的分布，与X的取值无关，熵越大，随机变量的不确定性就越大，也就是纯度越低，熵的取值范围是0 =< Ent(D) =< logn。
- 信息增益与ID3
–
决策树的生成就是使得数据集的熵下降的过程，那么选择最有属性可以使得下降的速度最快。
在信息增益前我们需要知道经验熵和经验条件熵中的概率由数据估计（极大似然估计）得到时，所对应的熵和条件熵分别成为经验熵和经验条件熵。
经验熵：
条件经验熵：
那么信息增益的定义为：特征A对训练数据集D的信息增益g(D,A)定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：
具体的代码实现计算信息增益：
"""
函数说明:计算给定数据集的经验熵(香农熵)
Parameters:
dataSet - 数据集
Returns:
shannonEnt - 经验熵(香农熵)
"""
def calcShannonEnt(dataSet):
numEntires = len(dataSet) #返回数据集的行数，即实例总数
labelCounts = {} #保存每个标签(Label)出现次数的字典，键值是最后一列的数值，键值不存在时扩充字典
for featVec in dataSet: #对每组特征向量进行统计
currentLabel = featVec[-1] #取最后一列数据，即提取标签(Label)信息
if currentLabel not in labelCounts.keys(): #与已有的labelCounts中的键比较，如果标签(Label)没有放入统计次数的字典,添加进去，扩充字典
labelCounts[currentLabel] = 0 #labelCounts中该标签计数为0
labelCounts[currentLabel] += 1 #否则Label计数
shannonEnt = 0.0 #经验熵(香农熵)初始为0.0
for key in labelCounts: #取labelCounts中的键值，计算香农熵
prob = float(labelCounts[key]) / numEntires #labelCounts[key]返回label出现的次数，选择出现的频率作为该标签(Label)的概率
shannonEnt -= prob * log(prob, 2) #利用公式计算
return shannonEnt #返回经验熵(香农熵)
"""
函数说明:选择最优特征
Parameters:
dataSet - 数据集
Returns:
bestFeature - 信息增益最大的(最优)特征的索引值
"""
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #特征数量
baseEntropy = calcShannonEnt(dataSet) #计算数据集的香农熵
bestInfoGain = 0.0 #信息增益
bestFeature = -1 #最优特征的索引值
for i in range(numFeatures): #遍历所有特征
#获取dataSet的第i个所有特征
featList = [example[i] for example in dataSet] #利用列表推导式将所有第i个特征值或搜友可能的值写入
uniqueVals = set(featList) #创建set集合{},元素不可重复
newEntropy = 0.0 #经验条件熵
for value in uniqueVals: #计算信息增益
subDataSet = splitDataSet(dataSet, i, value) #subDataSet：划分后的子集
prob = len(subDataSet) / float(len(dataSet)) #计算子集的概率
newEntropy += prob * calcShannonEnt(subDataSet) #根据公式计算 经验条件熵
infoGain = baseEntropy - newEntropy #信息增益
# print("第%d个特征的增益为%.3f" % (i, infoGain)) #打印每个特征的信息增益
if (infoGain > bestInfoGain): #计算信息增益
bestInfoGain = infoGain #更新信息增益，找到最大的信息增益
bestFeature = i #记录信息增益最大的特征的索引值
return bestFeature #返回信息增益最大的特征的索引值
ID3算法就是使用信息增益作为评价准则实现的，但ID3 仅仅适用于二分类问题，ID3 仅仅能够处理离散属性。
ID3算法可以参考这里：ID3_algorithm
- 信息增益率与C4.5
–
实用信息增益会对取值数目较多的特征有所偏好，为了减少这种偏好带来的影响，C4.5对ID3进行了改进，使用信息增益率来选择特征。
4.基尼系数与CART
CART算法使用基尼系数来选择最优特征。
三、三种算法的比较
ID3
熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。
信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。
ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。
C4.5
C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。
C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。但是，对连续属性值需要扫描排序，会使C4.5性能下降。
ID3和C4.5都是分类树，CART（Classification and regression tree）可以是分类/回归树。
CART
CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。
CART 的全称是分类与回归树。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。
回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。
要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。
分类树种，使用 Gini 指数最小化准则来选择特征并进行划分；
Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。
信息增益 vs 信息增益比
之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。
Gini 指数 vs 熵
既然这两个都可以表示数据的不确定性，不纯度。那么这两个有什么区别那？
•Gini 指数的计算不需要对数运算，更加高效；
•Gini 指数更偏向于连续属性，熵更偏向于离散属性。
参考自：周志华《机器学习》
李航《统计学习方法》
决策树
《机器学习实战》