机器学习_阅读笔记_决策树

决策树（decision tree）是一种基本的分类与回归方法，本文讨论分类决策树。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。决策树的学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。

模型与学习

模型

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或者属性，叶结点表示一个类。

if-then规则

将决策树转化成if-then规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则;路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。

这里给出机器学习实战中创建分支的伪代码函数createBranch()
检测数据集中的每个子项是否属于同一分类：

If so return 类标签 ：
Else
    寻找划分数据集的最好特征
    划分数据集
    创建分支节点
        for 每个划分的子集
                调用函数createBranch 并增加返回结果到分支节点中
    return   分子节点

特征选择

信息增益

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为

P(X=xi)=pi,i=1,2,⋯,n

则随机变量X的熵定义为

H(X)=−∑i=1npilogpi

通常上式中的对数以2为底或者以自然对数e为底，这时熵的单位分别称作比特（bit）或纳特（nat）。
由定义可知，熵只依赖于X分布，而与X的取值无关，所以也可以将X的熵记作H(p)

H(p)=−∑i=1npilogpi

熵越大，随机变量的不确定性就越大。从定义可以验证

0≤H(p)≤logn

当随机变量只取两个值(伯努利分布)，即X的分布为

P(X=1)=p,P(X=0)=1−p,0≤p≤1

熵为

H(p)=−plog2p−(1−p)log2(1−p)

这时，熵H(p)随概率p变化的曲线如图

设有随机变量(X,Y)，其联合概率分布为

P(X=xi,Y=yj)=pij

条件熵 H(Y|X)表示在随机变量X给定的条件下随机变量Y的条件熵(conditional entropy)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望(pi是X为xi的概率)

H(Y|X)=−∑i=1npiH(Y|X=xi)

当熵和条件熵中的概率由数理统计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。此时若有0概率，则令0log0=0
信息增益（information gain）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

g(D,A)=H(D)−H(D|A)

一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中的类与特征的互信息。
决策树学习应用信息增益准则选择特征。信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）D,计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。

信息增益比

信息增益的大小是相对于训练数据而言的，训练数据经验熵大则信息增益大，反之小。使用信息增益比（information gain ratio）可以对这一问题进行校正。这是特征选择的另一准则。
定义（信息增益比）：特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比，即

gR(D,A)=g(D,A)H(D)

构造算法

ID3算法

ID3算法（interative dichotomiser 3）的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。

注意：以下算法实现来自机器学习实战只适用于标称型数据，因此数值型数据必须离散化。可参考完整代码

#本示例中使用的数据格式如下，dataSet前两列为特征，最后一列为标签。labels为两个特征的名称(含义)，主要用于输出树(嵌套字典)
def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    return dataSet, labels

#计算给定数据集的香农熵
def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet: #the the number of unique elements and their occurance
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2) #log base 2
    return shannonEnt

#按照给定特征划分数据集，主要用于已经确认确认使用哪个特征划分之后划分该特征节点的子节点的
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]     #chop out axis used for splitting
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

#选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1      #the last column is used for the labels
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):        #iterate over all the features
        featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
        uniqueVals = set(featList)       #get a set of unique values
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)     
        infoGain = baseEntropy - newEntropy     #信息增益，newEntropy为该循环下特征的条件熵
        if (infoGain > bestInfoGain):       #compare this to the best gain so far
            bestInfoGain = infoGain         #if better than current best, set to best
            bestFeature = i
    return bestFeature                      #returns an integer


#创建树的函数代码
def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList): 
        return classList[0]#stop splitting when all of the classes are equal
    if len(dataSet[0]) == 1: #如果循环到只剩下一个特征，返回数据集中数量最多的标签
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]       #copy all of labels, so trees don't mess up existing labels
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree

#使用训练出来的模型做预测
def classify(inputTree,featLabels,testVec):
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    if isinstance(valueOfFeat, dict): 
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else: classLabel = valueOfFeat
    return classLabel  

ID3算法的不足
1、ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
2、ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？
3、ID3算法对于缺失值的情况没有做考虑
4、没有考虑过拟合的问题

C4.5算法

C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征。
针对ID3算法的不足，分别有以下改进
1、离散化连续值：对于是连续数值型的特征，假设特征为A，样本有m个。将m个特征A的值排序，假设按大到小排好后为a0,a1,..am-1，求每个相邻的值的平均值如(a0+a1)/2，这样就得到了m-1个特征值，对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点，然后小于该点的为类别1，大于改点的为类别2.
2、采用信息增益比来解决第2个问题
3、参考这
4、对于第4个问题，C4.5引入了正则化系数进行初步的剪枝。
除了上面的4点，C4.5和ID的思路区别不大。

C4.5算法的不足
1）由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。后面在下篇讲CART树的时候我们会专门讲决策树的减枝思路，主要采用的是后剪枝加上交叉验证选择最合适的决策树。
2）C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
3）C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
4）C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。

这4个问题在CART树里面部分加以了改进。所以目前如果不考虑集成学习话，在普通的决策树算法里，CART算法算是比较优的算法了。scikit-learn的决策树使用的也是CART算法。

决策树的剪枝

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树容易出现过拟合现象。解决这一问题的方法是考虑决策树的复杂度，对已生成的决策树进行简化。在决策树学习中讲已生成的树进行简化的过程称为剪枝（pruning）。
决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有Nt个样本，其中k类的样本点有Ntk个,Ht(T)为叶节点t上的经验熵，α≥0为参数，则决策树学习的损失函数可以定义为

Cα(T)=−∑i=1|T|NtHt(T)+α|T|

其中经验熵为

Ht(T)=−∑kNtkNtlogNtkNt

在损失函数中将右边第一个式子记录成

C(T)=−∑i=1|T|NtHt(T)=−∑t=1|T|∑k=1KNtklogNtkNt

这时有

Cα(T)=C(T)+α|T|

C(T)表示模型对训练数据预测的误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数α≥0控制两者之间的影响。较大的α促使选择较简单的模型（树），较小的α促使选择较复杂的模型（树）。α=0意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

树的剪枝算法
输入：生成算法产生的整个树T，参数α；
输出：修剪后的子树Tα
(1)计算每个结点的经验熵
(2)递归地从树的叶结点向上回缩
设一组叶结点回缩到其父结点之前与之后的整体树分别为TB与TA,其对应的损失函数值分别是Cα(TB)与Cα(TA),如果Cα(TA)≤Cα(TB)，则进行剪枝，即将父结点变为新的叶结点
(3)返回(2)，直至不能继续为止，得到损失函数最小的子树Tα。
剪枝算法可由动态规划算法实现

CART分类回归树算法

分类与回归树(classification and regression tree,CART)模型，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。以下将用于分类与回归的树统称为决策树。
CART对C4.5算法做了改进。C4.5模型是用较为复杂的熵来度量(涉及大量的对数运算)，使用了相对较为复杂的多叉树，只能处理分类不能处理回归。CART使用更简单的二叉树，能处理分类和回归问题，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。sk-learn中用的就是CART算法。
CART算法由以下两步组成：
(1)决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
(2)决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼（Gini index）指数最小化准则，进行特征选择，生成二叉树。

分类树生成

CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。
在分类问题中，假设有K个类别，第k个类别的概率为pk, 则基尼系数的表达式为：

Gini(p)=∑k=1Kpk(1−pk)=1−∑k=1Kp2k

如果是二类分类问题，如果属于第一个样本输出的概率是p，则基尼系数的表达式为:

Gini(p)=2p(1−p)

对于个给定的样本D,假设有K个类别, 第k个类别的数量为Ck,则样本D的基尼系数表达式为：

Gini(p)=∑k=1Kpk(1−pk)=1−∑k=1K(|Ck||D|)2

特别的，对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数表达式为：

Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)

对比基尼系数表达式和熵模型的表达式，二次运算比比对数简单。尤其是对二类分类的计算，更加简单。和熵模型的度量方式比，基尼系数对应的误差有多大呢？对于二类分类，基尼系数和熵之半的曲线如下：

从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在45度角附近误差稍大。因此，基尼系数可以做为熵模型的一个近似替代。而CART分类树算法就是使用的基尼系数来选择决策树的特征。

CART树的生成 :
输入：训练数据集D
输出： CART决策树
根据训练数据集，从根结点开始，递归地对每个结点进行一下操作，构建二叉决策树：
(1)设结点的训练数据集为D,计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试是“是”或“否”将D分割成D1和D2两部分
(2)在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点，依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中
(3)对两个子结点递归地调用(1),(2),直至满足停止条件
(4)生成CART决策树
算法停止的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。

对于CART分类树连续值的处理问题，其思想和C4.5是相同的，都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5使用的是信息增益比，则CART分类树使用的是基尼系数。

代码可参考机器学习算法的Python实现 (3)：决策树剪枝处理

回归树生成

假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集:

D={(x1,yi),(x2,y2),...,(xN,yN)}

一个回归树对应着输入空间（特征空间）的一个划分以及在划分的单元上的输出值，假设已将输入空间划分为M个单元R1,R2,……,Rm,并且每个单元Rm上都有一个固定的输出值Cm,于是回归树模型可表示为：

f(x)=∑m=1McmI(x∈Rm)

当输入空间的划分确定是，可以使用平方误差∑x∈Rm(yi−f(xi)2)来表示回归树对于训练数据的训练误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元Rm上的cm的最优值ĉ m是Rm上的所有输入实例xi对应的输出yi的均值，即

cm^=ave(yi|xi∈Rm)

这里使用启发式的方法对输入空间进行划分，选择第j个变量x(j)和他的取值s，作为切分变量和切分点，并定义两个区域：

R1(j,s)={x|x(j)≤s},R2(j,s)={x|x(j)>s}

然后寻找最优切分变量j和最优切分点s。具体地，求解

minj,s⎡⎣⎢⎢minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2⎤⎦⎥⎥

由上可知，c1、c2分别为R1、R2数据集的样本输出均值。

对于决策树建立后做预测的方式，上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

遍历所有的输入变量，找到最优的切分变量j，构成一对(j,s)，依次将输入空间划分为2个区域，接着对每个区域重复划分，直到满足条件为止，这样的回归树通常称为最小二乘回归树。

下面给出最小二乘回归树生成算法步骤：
输入：训练数据集D;
输出：回归树f(x)
(1)选择最优切分变量j与切分点s，求解

minj,s⎡⎣⎢⎢minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2⎤⎦⎥⎥

遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对(j,s)
(2)对选定的对(j,s)划分区域并决定相应的输出值：

R1(j,s)={x|x(j)≤s},R2(j,s)={x|x(j)>s}

ĉ m=1Nm∑xi∈Rm(j,s)yi,x∈Rm,m=1,2

(3)继续对两个子区域调用步骤(1),(2),直至满足停止条件。
(4)将输入空间划分为M个区域R1,R2,⋯,RM，生成决策树：

f(x)=∑m=1McmI(x∈Rm)

CART剪枝

类似C4.5公式和流程。有空再补充…

参考

机器学习实战之决策树（三）
五、决策树–统计学习方法总结
决策树ID3算法的信息论基础
决策树算法原理(下)