机器学习 学习笔记（8） 决策树

一般的，一棵决策树包含一个根结点、若干内部结点和若干个叶结点，叶子结点对应于决策结果，而其他每个结点对应于一个属性测试，每个结点被包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集。

决策树的生成是一个递归过程，在决策树基本算法中，有三种情形会导致递归返回，（1）当前结点包含的样本属于同一类别，无需划分，（2）当前属性集为空，或是所有样本在所有属性取值上相同，无法划分（3）当前结点包含的样本集合为空，不能划分。

在（2）情况下，把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别。在（3）情况下，把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。（2）是在利用当前结点的后验分布，（3）是把父结点的样本分布作为当前结点的先验分布。

可以将决策树看成一个if-then规则的集合，将决策树转换成if-then规则的过程是：由决策树根结点到叶结点的每一条路径构建一条规则，路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则额结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥且完备。

决策树的损失函数通常是正则化的极大似然函数，决策树学习的策略是以损失函数为目标函数的最小化。

决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程，由于决策树表示一个条件概率分布，因此深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，决策树的剪枝对应于模型的全局选择。

信息增益

信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合中第k类样本所占比例为

p_k(k=1,2,..|\gamma|)

，则D的信息熵定义为：

Ent(D)=-\sum_{k=1}^\gamma p_klog_2p_k

，Ent(D)值越小，则D的纯度越高。

假定离散属性a有V个可能的取值{

a^1,a^2,...,a^V

}，若使用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为

a^v

的样本，记为

D^v

，可以算出

D^v

的信息熵，考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重

\frac{|D^v|}{|D|}

，即样本数越多的分支结点的影响越大，于是可以计算出用属性a对样本集D进行划分所获得的信息增益：

Gain(D,a)=Ent(D)-\sum_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v)

一般而言，信息增益越大，意味着用属性a来划分所获得的纯度提升越大。所以可以用信息增益来进行决策树的划分属性选择。著名的ID3决策树算法就是以信息增益为准则来选择划分属性。

ID3算法：

输入：训练数据集D，特征集A，阈值

\varepsilon

输出：决策树T

（1）若D中所有实例属于同一类

C_k

，则T为单结点树，并将类

C_k

作为该结点的类标记，返回T

（2）若

A= \o

，则T为单结点树，并将D中实例数最大的类

C_k

作为该结点的类标记，返回T。

（3）否则，计算A中各特征对D的信息增益，选择信息增益最大的特征

A_g

。

（4）如果

A_g

的信息增益小于阈值

\varepsilon

，则置T为单结点树，并将D中实例数最大的类

C_k

作为该结点的类标记，返回T。

（5）否则，对

A_g

的每一可能只

a_i

，依据

A_g=a_i

将D分割为若干非空子集

D_i

，将

D_i

中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T。

（6）对第i个子结点，以

D_i

为训练集，以

A-{A_g}

为特征集，递归地调用（1）-（5），得到子树

T_i

，返回T

增益率

信息增益对于可取值数目较多的属性有偏好，为减少这种偏好可能带来的不利影响著名的C4.5决策树算法不直接使用信息增益，而是使用增益率来选取最优划分属性。增益率定义为：

Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}

IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}

是属性a的固有值，属性a可能的取值数目越多，IV(a)的值通常会越大。

增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式，先从候选属性划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

# 代码和数据集主要源自于机器学习实战，https://github.com/AnnDWang/MachineLearning/blob/master/thirdbook/ch3/trees.py
from math import log
import operator
def calcShannonEnt(dataSet):
    numEntries=len(dataSet)
    labelCounts={}
    for featVec in dataSet:
        currentLabel=featVec[-1]
        if currentLabel not in labelCounts:
            labelCounts[currentLabel]=0
        labelCounts[currentLabel]+=1
    shannonEnt=0.0
    for key in labelCounts:
        prob=float(labelCounts[key])/numEntries
        shannonEnt-=prob*log(prob,2)
    return shannonEnt

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 splitDataSet(dataSet,axis,value):
    retDataSet=[]
    for featVec in dataSet:
        if featVec[axis] ==value:
            reducedFeatVec=featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

myDat,labels=createDataSet()
splitDataSet(myDat,0,1)

# 选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
    numFeatures=len(dataSet[0])-1
    baseEntropy=calcShannonEnt(dataSet)
    bestInfoGain=0.0
    bestFeature=-1
    for i in range(numFeatures):
        featList=[example[i] for example in dataSet]
        uniqueVals=set(featList)
        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
        if(infoGain>bestInfoGain):
            bestInfoGain=infoGain
            bestFeature=i
    return bestFeature

def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys():classCount[vote]=0
        classCount[vote]+=1
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

# 创建树得到函数代码
def createTree(dataSet,labels):
    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]
    myTree={bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues=[example[bestFeat] for example in dataSet]
    uniqueVals=set(featValues)
    for value in uniqueVals:
        subLabels=labels[:]
        myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree

mytree=createTree(myDat,labels)


# 使用决策树的分类函数
def classify(inputTree,featLabels,testVec):
    firstStr=list(inputTree.keys())[0]
    secondDict=inputTree[firstStr]
    # 将标签字符串转为索引
    featIndex=featLabels.index(firstStr)
    for key in secondDict:
        if testVec[featIndex]==key:
            if type(secondDict[key]).__name__=='dict':
                classLabel=classify(secondDict[key],featLabels,testVec)
            else:
                classLabel=secondDict[key]
    return classLabel

# 使用pickle模块存储决策树
def storeTree(inputTree,filename):
    import pickle
    fw=open(filename,'w')
    pickle.dump(inputTree,fw)
    fw.close()

def grabTree(filename):
    import pickle
    fr=open(filename)
    return pickle.load(fr)

C4.5算法:

输入：训练数据集D，特征集A，阈值

\varepsilon

输出：决策树T

（1）若D中所有实例属于同一类

C_k

，则T为单结点树，并将类

C_k

作为该结点的类标记，返回T

（2）若

A= \o

，则T为单结点树，并将D中实例数最大的类

C_k

作为该结点的类标记，返回T。

（3）否则，计算A中各特征对D的信息增益比，选择信息增益比最大的特征

A_g

。

（4）如果

A_g

的信息增益比小于阈值

\varepsilon

，则置T为单结点树，并将D中实例数最大的类

C_k

作为该结点的类标记，返回T。

（5）否则，对

A_g

的每一可能只

a_i

，依据

A_g=a_i

将D分割为若干非空子集

D_i

，将

D_i

中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T。

（6）对第i个子结点，以

D_i

为训练集，以

A-{A_g}

为特征集，递归地调用（1）-（5），得到子树

T_i

，返回T

基尼指数

CART（Classification and Regression Tree）决策树使用基尼指数（Gini Index）来选择划分属性。数据集D的纯度可用基尼值来度量：

Gini(D)=\sum_{k=1}^{|Y|} \sum_{k'\neq k}p_kp_{k'}=1-\sum_{k=1}^{|Y|}p_k^2

Gini(D)反应了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，数据集D纯度越高。

Gini_index(D,a)=\sum_{v=1}^V\frac {|D^v|}{|D|}Gini(D^v)

在候选属性集合中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

CART生成算法：

输入：训练数据集D，停止计算条件

输出：CART决策树

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

（1）设结点的训练数据集为D，计算现有特征对于该数据集的基尼指数，此时对每一个特征A，对其可能取得每个值a，根据样本点测试是否将D分割成两个部分，计算相应的基尼指数。

（2）在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依据最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依据特征分配到两个子结点中去。

（3）对两个子结点递归调用（1）（2），直至满足条件

（4）生成CART决策树。

CART剪枝算法：

输入：CART算法生成的决策树

T_0

输出：最优决策树

T_\alpha

（1）设k=0，

T=T_0

（2）设

\alpha =+\infty

（3）自下而上地对各内部结点t计算

C(T_t)

，

|T_t|

以及

g(t)=\frac{C(T)-C(T_t)}{|T_t-1|}

，

\alpha =min(\alpha,g(t))

T_t

表示以t为根结点的子树，

C(T_t)

是对训练数据的预测误差，

|T_t|

是

T_t

的叶结点个数

（4）对

g(t)=\alpha

的内部结点t进行剪枝，并对叶结点t以多数表决法决定其类，得到树T。

（5）设k=k+1，

\alpha_k =\alpha

，

T_k=T

（6）如果

T_k

不是由根结点及两个叶结点构成的树，则回到步骤（3），否则令

T_k=T_n

（7）采用交叉验证法在子树序列

T_1 ,T_2 ,...,T_n

中选择最优子树

T_\alpha

剪枝处理

剪枝是决策树学习算法对付过拟合的主要手段。主要有预剪枝和后剪枝。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化的提升，则将该子树替换为叶结点。

只有一层划分的决策树，称为决策树桩。

预剪枝使得决策树的很多分支都没有展开，不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是另一方面，有些分支的当前划分虽不能提升泛华性能，甚至可能导致泛华性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于贪心的本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下，后剪枝决策树欠拟合的风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树大得多。

剪枝与损失函数

这里的剪枝通过极小化决策树整体的损失函数或代价函数来实现。设决策树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有

N_i

个样本点，其中k类的样本点有

N_{tk}

个，k=1,2,...,K，

H_t(T)为叶结点t上的经验熵

，

\alpha \geqslant 0

为参数，则决策树学习的损失函数为：

C_\alpha (T)=\sum_{t=1}^{|T|} N_tH_t(T)+\alpha |T|

，经验熵为

H_t(T)=-\sum_{k} \frac{N_{tk}}{N_t} log \frac{N_{tk}}{N_t}

，

损失函数中的右边的第一项为：

C_\alpha (T)=\sum_{t=1}^{|T|} N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^K N_{tk} log\frac{N_{tk}}{N_t}

，此时有

C_\alpha (T)=C(T)+\alpha |T|

C(T)是模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数

\alpha \geqslant 0

控制两者之间的影响，较大的

\alpha

促使选择较为简单的模型，较小的

\alpha

促使选择较复杂的模型。这个损失函数的极小化等价于正则化的极大似然估计。

连续值与缺失值

由于连续属性的可取值数目不再有限。因此，不能直接根据连续属性的可取值来对结点进行划分，此时，连续属性离散化技术可派上用场。最简单的策略是采用二分法对连续属性进行处理。给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为

{a^1,a^2,...,a^n}

。基于划分点t可将D分为子集

D^-_t

和

D^+_t

，其中

D^-_t

包含哪些在属性a上取值不大于t的样本，而

D^+_t

包含哪些在属性a上取值大于t的样本。因此，对连续属性a，我们可考察包含n-1个元素的候选划分点集合：

T_a=\frac{a^i+a^{i+1}}{2},1\leqslant i\leqslant n-1

。

Gain(D,a)=\max \limits_{t\in T_a} Gain(D,a,t)=\max \limits_{t\in T_a} Ent(D)-\sum_{\lambda \in {-,+}} \frac{|D^\lambda _t|}{|D|}Ent(D^\lambda _t)

其中Gain(D,a,t)是样本集D基于划分点t二分后的信息增益，选择使Gain(D,a,t)最大化的划分点。

与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

缺失值处理，给定训练集D和属性a，令

\widetilde{D}

表示D中在属性a上没有缺失值的样本子集。对于如何在属性值缺失的情况下进行属性选择，仅可根据

\widetilde{D}

来判断属性a的优劣，假定属性a有V个可取值，令

\widetilde{D}^v

表示

\widetilde{D}

中在属性a上取值为

a^v

的样本子集，

\widetilde{D}_k

表示

\widetilde{D}

中属于第k类的样本子集，则显然有

\widetilde{D}=\cup _{k=1}^y\widetilde{D}_k

，

\widetilde{D}=\cup _{v=1}^V\widetilde{D}^v

。假定我们为每个样本x赋予一个权重

w_x

，并定义

\rho =\frac{\sum_{x\in \widetilde D} w_x}{\sum_{x\in D} w_x}

，

\widetilde p_k=\frac {\sum_{x\in \widetilde D_k} w_x}{\sum _{x\in \widetilde D} w_x},1\leqslant k\leqslant y

，

\widetilde r_v=\frac {\sum_{x \in \widetilde D^v}w_x}{\sum _{x \in \widetilde D}w_x},1\leqslant v\leqslant V

对于属性a，

\rho

表示无缺失值样本所占比例，

\widetilde p_k

表示无缺失值样本中第k类所占的比例，

\widetilde r_v

则表示无缺失值样本中在属性a上取值

a^v

的样本所占的比例。

Gain(D,a)=\rho \times Gain(\widetilde D,a)=\rho \times (Ent(\widetilde D)-\sum_{v=1}^V \widetilde r_v Ent(\widetilde D^v))

,

Ent(\widetilde D)=-\sum_{k=1}^y \widetilde p_klog_2\widetilde p_k

对于给定划分属性，若样本在该属性上的值缺失 ，进行划分时，将样本同时划入所有的子结点，则样本权值在于属性值

a^v

对应的子结点中调整为

\widetilde r_v \times w_x

。这就是让同一个样本以不同的概率划入到不同的子结点中去。

多变量决策树

多变量决策树又称为斜决策树，实现如下图所示的斜划分 甚至更复杂的决策树：

参考

1. 《机器学习》
2. 《统计学习方法》
3. 《机器学习实战》