机器学习系列（二）决策树（Decision Tree）
原文链接：机器学习系列（二）决策树（Decision Tree）
目录
一、算法概述 二、决策树的构建过程 三、常用指标 四、决策树停止分裂的条件 五、决策树算法 六、决策树的剪枝 七、梯度提升决策树（GBDT） 八、实现方法
一、算法概述
决策树是一种树形结构的机器学习方法，是一种监督学习方法（Supervised Learning），在决策树的树形结构里，每个内部节点表示由一种特征属性引发的判断，每个节点下面的分支代表某个判断结果的输出，最后的叶子结点表示一种分类结果。
决策树有三种结点：根节点：就是树的最顶端，最开始的那个节点；内部节点：就是树中间的那些节点；叶节点：就是树最底部的节点，也就是决策结果。节点之间存在父子关系。比如根节点会有子节点，子节点会有子子节点，但是到了叶节点就停止了，叶节点不存在子节点。
二、决策树的构建过程
步骤1：将所有的数据看成是一个节点，进入步骤2；
步骤2：从所有的数据特征中挑选一个最优数据特征对节点进行分割，使得分割后的子集有一个在当前条件下最好的分类，进入步骤3；
步骤3：生成若干孩子节点，对每一个孩子节点进行判断，如果满足停止分裂的条件，进入步骤4；否则，进入步骤2；
步骤4：设置该节点是子节点，其输出的结果为该节点数量占比最大的类别。
决策树的特点： 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。缺点：可能会产生过度匹配的问题（需要剪枝）。适用数据类型：数值型和标称型
决策树在对中间结点进行分裂的时候，是选择最优分裂结果的属性进行分裂，决策树使用信息增益或者信息增益率作为选择属性的依据。信息增益表示划分数据前后信息发生的变化，获得信息增益最高的特征就是最好的选择。
三、常用指标
Python代码：
from math import log
def calcShannonEnt(dataSet):
#返回数据集行数
numEntries=len(dataSet)
#保存每个标签（label）出现次数的字典
labelCounts={}
#对每组特征向量进行统计
for featVec in dataSet:
currentLabel=featVec[-1] #提取标签信息
if currentLabel not in labelCounts.keys(): #如果标签没有放入统计次数的字典，添加进去
labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1 #label计数
shannonEnt=0.0 #经验熵
#计算经验熵
for key in labelCounts:
prob=float(labelCounts[key])/numEntries #选择该标签的概率
shannonEnt-=prob*log(prob,2) #利用公式计算
return shannonEnt #返回经验熵
Python代码：
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]
#创建set集合{}，元素不可重复
uniqueVals = set(featList)
#经验条件熵
newEntropy = 0.0
#计算信息增益
for value in uniqueVals:
#subDataSet划分后的子集
subDataSet = splitDataSet(dataSet, i, value)
#计算子集的概率
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
一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
「信息增益的缺点」： 在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，且信息增益会倾向选择分支比较多的属性，单纯用信息增益来做决策难免会不准确，使用信息增益比可以对这个问题进行校正，这是特征选择的另一个标准。
四、决策树停止分裂的条件
如果要等到最后一个数据样本再结束分裂，这样的决策树会过于复杂，对于测试样本的预测准确率也不会高，因此需要提前停止分裂。 1） 最小结点数 当某个节点的数据量小于指定的最小节点数值时，停止分裂，这样避免对噪声数据的过度分裂，降低过拟合。 2） 熵的最小值 当熵过小时，数据复杂程度不大，没必要继续分裂，如果熵小于给定阈值，则停止分裂。 3） 决策树的深度 决策树的深度是所有叶子结点的最大深度，子结点比父结点的深度大1，当决策树的深度达到指定深度阈值，则停止分裂。 4） 特征使用情况 当所有的特征属性都用完时，没有可继续分裂的属性，直接将当前节点设置为叶子结点。
五、决策树算法
「决策树」可以分为「分类树」（分裂结果为类别）和「回归树」（分裂结果为数值）。 「ID3算法」是采用「信息增益」来做特征选择的，在每个结点处，计算所有可能特征的信息增益，选择信息增益最大的特征蕞为节点分裂特征，递归处理之后的子结点直到分裂结束。 Python代码：
def createTree(dataSet,labels,featLabels):
#取分类标签（是否放贷：yes or no）
classList=[example[-1] for example in dataSet]
#如果类别完全相同，则停止继续划分
if classList.count(classList[0])==len(classList):
return classList[0]
#遍历完所有特征时返回出现次数最多的类标签
if len(dataSet[0])==1:
return majorityCnt(classList)
#选择最优特征
bestFeat=chooseBestFeatureToSplit(dataSet)
#最优特征的标签
bestFeatLabel=labels[bestFeat]
featLabels.append(bestFeatLabel)
#根据最优特征的标签生成树
myTree={bestFeatLabel:{}}
#删除已经使用的特征标签
del(labels[bestFeat])
#得到训练集中所有最优特征的属性值
featValues=[example[bestFeat] for example in dataSet]
#去掉重复的属性值
uniqueVls=set(featValues)
#遍历特征，创建决策树
for value in uniqueVls:
myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),
labels,featLabels)
return myTree
「C4.5算法」对ID3算法进行改进，信息增益比作为选择特征的标准，如果分裂太多信息增益率会降低。 「CART」也叫「分类回归树」，是「二叉树」，每个节点只能分为2个子结点，既可以分类也可以回归，CRART采用「GINI指数」作为选择特征的标准，和ID3一样也会存在过度分裂造成过拟合的问题。 前面介绍说决策树容易造成过拟合，也是过度匹配，而剪枝就是给决策树瘦身，不需要太多判断分支也能得到比较好的结果。下图从左到右分别表示分类问题的欠拟合，拟合和过拟合。
重点解释一下「过拟合」问题，如果决策树在构建时中间结点过多，决策树很复杂，所有训练数据都可以完美的做分类，决策模型过分依赖现有训练数据的特征，但当遇到测试样本时，错误率反而很高。
六、决策树的剪枝
「剪枝」一般分两种方法：
第一种方法是「预剪枝」，就是在决策树的构建过程中进行剪枝，在构造的过程中对节点进行评估，如果对某个节点进行划分时不能带来准确性的提升（损失函数的降低），那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。
第二种方法是「后剪枝」，在生成决策树之后再进行剪枝。通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。
七、梯度提升决策树（GBDT）
「梯度提升决策树」（Gradient Boosting Decision Tree或Gradient Boosting Regression Tree）作为机器学习领域的“屠龙刀”是一种基于「集成思想」的决策树。GBDT的核心在于每一棵树学的是之前所有树结论和的「残差」，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学，如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。这就是Gradient Boosting在GBDT中的意义。
GBDT主要的优点： 1）可以灵活处理各种类型的数据，包括连续值和离散值； 2）在相对少的调参时间情况下，预测的准确率也可以比较高； 3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
八、实现方法
在构建决策树模型时，除了自己写代码外还可以采用「sklearn」的决策树包和「weka」数据挖掘平台。
部分转自：https://blog.csdn.net/jiaoyangwm/article/details/79525237 https://www.cnblogs.com/molieren/articles/10664954.html
腾讯云开发者
