分类与回归决策树详解——ID3,C4.5,CART,Python实现

云计算 waitig 785℃ 百度已收录 0评论

决策树可以用来进行分类或者回归,学习可以分为三个部分:特征选择、决策树的生成、决策树的修剪。


决策树模型

内部节点表示一个特征或者属性,叶子结点表示一个类。决策树工作时,从根节点开始,对实例的每个特征进行测试,根据测试结果,将实例分配到其子节点中,这时的每一个子节点对应着特征的一个取值,如此递归的对实例进行测试并分配,直到达到叶节点,最后将实例分配到叶节点所对应的类中。
决策树具有一个重要的性质:互斥并且完备。每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖,这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。


决策树与条件概率分布

决策树将特种空间划分为互不相交的单元或区域,在每个单元上定义了一个类的概率分布,则构成了条件概率分布。分类时,将该节点的实例强行分到条件概率大的那一类中。
决策树学习就是由训练数据集估计条件概率模型的过程。一个数据集可能对应不想矛盾的多个决策树,通常选择使损失函数最小的决策树。通常现实中决策树学习算法采用启发式方法,近似求解这一优化问题,这样得到的决策树是次优的。
学习算法通常是递归的选择最优特征。首先开始构建根节点,然后将所有训练数据放到根节点中,选择一个最优特征,按照这一特征对数据集分割成子集,使得各个子集有一个在当前条件下最好的分类,如果这个子集已经能够被基本正确分类,则构建叶节点,如果还有子集不能正确分类,则对这些子集选择新的最优特征,继续对其分割构建新的节点。
但是这样的方法可能能够对训练数据具有好的分类能力,但是不具有好的泛化能力,容易出现过拟合,因此我们需要对树进行减枝,让树变得简单,复杂度降低,使其具有很好的泛化能力,方法为去掉过于细分的叶节点,使其退回到父节点,甚至更高的节点,将父节点或更高节点改为新的叶节点。如果特征数量很多,也可以在开始时对特征进行选择,只留下对训练数据具有足够分类能力的特征。
决策树的生成对应于模型的局部选择,决策树的减枝对应于模型的全局选择。决策树的生成只考虑局部最优,决策树的减枝则考虑全局最优。


信息增益

信息增益是用来选择最优划分特征的指标。首先给出熵的概念。
在信息论与概率统计中,熵是表示随机变量不确定性的度量。X为取值有限的离散随机变量。概率分布为
P(X=xi)=pi    i=1,2,...,n
则X的熵为
H(X)=i=1npilogpi
pi=00log0=0。对数以2为底定义单位为比特(bit),以e为底定义单位为纳特(nat),熵只依赖于X的分布,不依赖于X的取值。熵越大,信息的不确定性越大。
条件熵
H(Y|X)=i=1npiH(Y|X=xi)
如果概率由数据估计得到,所对应的熵称为经验熵。
信息增益:得知特征X的信息而使得类Y的信息的不确定性减少的程度。特征A对训练数据集D的信息增益g(D,A),定义为
g(D,A)=H(D)H(D|A)
一般熵H(Y)与条件熵H(Y|X)之差称为互信息。信息增益大的特征具有更强的分类能力。
特征选择的方法为:队训练数据集D,计算其每个特征的信息增益,并比较他们的大小,选择信息增益最大的特征。

信息增益比

信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题,用信息增益比可以很好的解决。
信息增益比:特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益与训练数据集D关于特征A的值的熵HA(D)之比
gR(D,A)=g(D,A)HA(D)
其中,HA(D)=i=1n|Di||D|log2|Di||D|,n为特征A取值的个数。


ID3算法

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征,递归的构建决策树。
输入:数据集D,特征集A,阈值σ
输出:决策树T
(1).若D中的所有实例均属于同一类Ck,则T为单节点树,并将类Ck作为该节点的类标记,返回T。
(2).若A=,则T为单节点树,选择对多的特征作为该节点的类标记,返回T。
(3).计算A中各个特征对D的信息增益,选择信息增益最大的特征Ag
(4).若Ag的信息增益小于阈值σ,则T为单节点树,选择对多的特征作为该节点的类标记,返回T。
(5).否则,对Ag按其每一个可能取值将数据集D划分为非空子集Di,将Di中实例数最大的类作为标记,构建子节点,由节点及其子节点构成树T,返回T。
(6).对第i个子节点,以Di为训练集,以AAg为特征集,递归的调用(1)~(5),得到树Ti,返回Ti

import numpy as np
import math
import operator
def createDataSet():
    dataSet = [[1,1,'yes'],
               [1,1,'yes'],
               [1,0,'no'],
               [0,1,'no'],
               [0,1,'no'],]
    label = ['no surfacing','flippers']
    return dataSet,label

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
    for key in labelCounts:
        shannonEnt = shannonEnt - (labelCounts[key]/numEntries)*math.log2(labelCounts[key]/numEntries)
    return shannonEnt


def splitDataSet(dataSet,axis,value):#切割数据集
    retDataset = []
    for featVec in dataSet:
        if featVec[axis] == value:
            newVec = featVec[:axis]
            newVec.extend(featVec[axis+1:])
            retDataset.append(newVec)
    return retDataset

def chooseBestFeatureToSplit(dataSet):#选择最优特征
    numFeatures = len(dataSet[0]) - 1
    bestInfoGain = 0
    bestFeature = -1
    baseEntropy = calcShannonEnt(dataSet)
    for i in range(numFeatures):
        allValue = [example[i] for example in dataSet]
        allValue = set(allValue)
        newEntropy = 0
        for value in allValue:
            splitset = splitDataSet(dataSet,i,value)
            newEntropy = newEntropy + len(splitset)/len(dataSet)*calcShannonEnt(splitset)
        infoGain = baseEntropy - newEntropy
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

def majorityCnt(classList):#投票确定叶子节点的类
    classCount = {}
    for value in classList:
        if value not in classCount: classCount[value] = 0
        classCount[value] += 1
    classCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return classCount[0][0]          

def createTree(dataSet,labels):   #生成决策树
    classList = [example[-1] for example in dataSet]
    labelsCopy = labels[:]
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeature = chooseBestFeatureToSplit(dataSet)
    bestLabel = labelsCopy[bestFeature]
    myTree = {bestLabel:{}}
    featureValues = [example[bestFeature] for example in dataSet]
    featureValues = set(featureValues)
    del(labelsCopy[bestFeature])
    for value in featureValues:
        subLabels = labelsCopy[:]
        myTree[bestLabel][value] = createTree(splitDataSet(dataSet,bestFeature,value),subLabels)
    return myTree


def classify(inputTree,featLabels,testVec):
    currentFeat = list(inputTree.keys())[0]
    secondTree = inputTree[currentFeat]
    try:
        featureIndex = featLabels.index(currentFeat)
    except ValueError as err:
        print('yes')
    try:
        for value in secondTree.keys():
            if value == testVec[featureIndex]:
                if type(secondTree[value]).__name__ == 'dict':
                    classLabel = classify(secondTree[value],featLabels,testVec)
                else:
                    classLabel = secondTree[value]
        return classLabel
    except AttributeError:
        print(secondTree)

if __name__ == "__main__":
    dataset,label = createDataSet()
    myTree = createTree(dataset,label)
    a = [1,1]
    print(classify(myTree,label,a))

C4.5

C4.5就是讲ID3中的信息增益换为信息增益比。


决策树的减枝

由于决策树生成后有过拟合现象,缺乏泛化能力,因此需要进行减枝达到全局最优。
减枝通过极小化决策树整体的损失函数或代价函数来实现。|T|表示树T的叶节点个数。t为一个叶节点,该叶节点上有Nt个样本,其中k类样本点有Ntk个。Ht(T)为叶节点t上的经验熵。则损失函数可以定义为
Cα=t=1|T|NtHt(T)+α|T|=C(T)+α|T|
Dt(T)=kNtkNtlogNtkNt
C(T)表示模型对训练数据的预测误差,即模型与训练数据的拟合程度,|T|表示模型复杂度,α用来控制占比。

减枝算法

输入:树T,α
输出:修建好的树Tα
(1)计算每个节点的经验熵
(2)递归的从树的叶节点向上回缩
设一组叶节点回缩前后对应的损失函数为Cα(TB)Cα(TA)。如果Cα(TA)Cα(TB)则进行减枝,将父节点变为新的叶节点。
(3)返回(2)。直至不能继续为止。


CART算法

CART假定决策树是二叉树,内部节点特征的取值为“是”或“否”。也包含决策树的生成与减枝两个过程。回归树用平方误差最小化准则,分类树用基尼指数最小化准则。

CART回归树的生成

回归树将输入空间(特征空间)划分为多个单元,每个单元有一个固定的输出值cm,当输入空间的划分确定时,可以用平方误差xiRm来表示回归树的预测误差。单元输出最优值c^m是单元上所有实例输出值的平均值。则问题可以变为使用启发式的方法确定切分变量以及切分点,使误差最小。可以固定一个输入变量,然后启发式的寻找最优切分点,通过这样的方法遍历所有输入变量,确定最优的切分变量与切分点。

最小二乘回归树生成算法

输入:训练数据集D
输出:回归树
在训练数据集上递归的将每个区域划分为两个子区域并决定每个子区域的输出值,构建二叉决策树:
(1)选择最优切变量与切分点。遍历变量,对固定的切分变量扫描切分点,选择最优结果。
(2)通过选择的最优结果划分数据区域并确定相应的输出值。
(3)连续对两个子区域调用(1)(2),直至满足停止条件。
(4)得到决策树

CART分类树的生成

首先介绍基尼指数:分类问题中,假设有K个类,样本属于第k类的概率为pk,则概率分布的基尼指数为
Gini(p)=k=1Kpk(1pk)=1k=1Kp2k
对于给定样本集其基尼指数为
Gini(D)=1k=1K(|Ck||D|)2
在特征A的条件下,集合D的基尼指数为
Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)
基尼指数可以表示数据的不确定性,指数越大表示集合的不确定性越大。

基尼指数分类树生成算法

输入:训练数据集,停止条件
输出:分类树
从根节点开始,递归的对每个节点进行一下操作,构建二叉决策树。
(1)计算所有特征的所有可能取值的基尼指数
(2)选择最优特征与最优取值,将数据集切分为两个子数据集
(3)递归调用(1)(2)直到满足停止条件
(4)生成CART分类树
停止条件为:节点中的样本个数小于预定阈值,或样本集的基尼指数小于阈值,或没有更多的特征。


CART减枝

CART减枝步骤:首先从生成算法产生的决策树T0底端开始不断减枝,直到T0的根节点,形成子树序列T0,T1,...,Tn;然后通过交叉验证算法在独立的验证数据集上对子树进行测试,从中选择最优子树。
减枝过程中损失函数为Cα(T)=C(T)+α|T|C(T)可以是基尼指数或是误差平方和。当α固定时,最优子树唯一。可以通过将α从小增大,确定一系列T0,T1,...,Tn,然后从中通过交叉验证选择最优子树。具体可以参看Breiman算法。
在对T0中每一内部节点t,计算
g(t)=C(t)C(Tt)|Tt|1
C(t)为以t为单节点树的损失函数,C(Tt)为以t为根节点的子树Tt的损失函数。g(t)表示减枝后损失函数减少的程度。在T0中减去g(t)最小的Tt,将得到的子树作为T1,同时将最小的g(t)设为α1T1为区间[α1,α2)的最优子树。不断增加α,产生新的区间。
然后利用独立的验证数据,交叉验证子树序列T0,T1,...,Tn,平方误差或基尼指数最小的决策树被认为是最优的。

CART减枝算法

输入:原完整的生成树
输出:减枝后的生成树
(1)设k=0,T=T0
(2)设αinf
(3)自上而下的对各内部节点t计算
g(t)=C(t)C(Tt)|Tt|1
α=min(α,g(t))
(4)对g(t)=α的内部节点t进行减枝,并对节点t以多数表决法确定类,得T。
(5)k=k+1,αk=αTk=T
(6)如果Tk不是右根节点及其两个叶子组成的树,则回到(3),否则令Tk=Tn
(7)交叉验证子树序列,得到最优子树


本文由【waitig】发表在等英博客
本文固定链接:分类与回归决策树详解——ID3,C4.5,CART,Python实现
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)