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

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

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

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

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

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

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

信息增益

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

，则D的信息熵定义为：

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

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

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

的样本，记为

，可以算出

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

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

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

ID3算法：

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

输出：决策树T

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

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

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

（2）若

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

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

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

。

（4）如果

的信息增益小于阈值

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

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

（5）否则，对

的每一可能只

，依据

将D分割为若干非空子集

，将

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

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

为训练集，以

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

，返回T

增益率

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

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

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

代码语言：javascript复制

# 代码和数据集主要源自于机器学习实战，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，阈值

输出：决策树T

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

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

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

（2）若

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

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

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

。

（4）如果

的信息增益比小于阈值

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

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

（5）否则，对

的每一可能只

，依据

将D分割为若干非空子集

，将

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

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

为训练集，以

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

，返回T

基尼指数

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

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

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

CART生成算法：

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

输出：CART决策树

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

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

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

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

（4）生成CART决策树。

CART剪枝算法：

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

输出：最优决策树

（1）设k=0，

（2）设

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

，

以及

，

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

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

是

的叶结点个数

（4）对

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

（5）设k=k 1，

，

（6）如果

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

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

中选择最优子树

剪枝处理

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

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

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

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