Python机器学习算法 — 决策树(Decision Tree)

时间:2024-02-29 16:43:33

决策树 -- 简介

        决策树(decision tree)一般都是自上而下的来生成的。每个决策或事件(即自然状态)都可能引出两个或多个事件,导致不同的结果,把这种决策分支画成图形很像一棵树的枝干,故称决策树。

        决策树是一种有监管学习分类方法。决策树的生成算法有 ID3 、C4.5 和 CART(Classification And Regression Tree)等,CART的分类效果一般优于其他决策树。

        决策树的决策过程需要从决策树的根节点开始,待测数据与决策树中的特征节点进行比较,并按照比较结果选择选择下一比较分支,直到叶子节点作为最终的决策结果。

        决策树一般流程

                1、收集数据

                2、准备数据(数值型数据必须离散化)

                3、分析数据

                4、训练数据

                5、学习数据,使用经验树计算错误率

       构建决策树由以下三部分所构成 

                1、特征选择

                2、决策树生成

                3、决策树剪枝

特征选择阶段

为了解释清楚各个数学概念,引入例子

        上表有15个样本数据表。数据包括贷款申请人的4个特征:年龄、有工作与否、有房子与否、信贷情况,其中最后一列类别的意思是:是否同意发放贷款,这个就是决策树最后要给出的结论,即目标属性——是否发放贷款,即决策树最末端的叶子节点只分成2类:同意发放贷款与不同意发放贷款。

信息熵(entropy)

        信息熵是用来衡量一个随机变量出现的期望值。如果信息的不确定性越大,熵的值也就越大,出现的各种情况也就越多。

                                               

        其中,S为所有事件集合,p为发生概率,c为特征总数。

        注意:熵是以2进制位的个数来度量编码长度的,因此熵的最大值是log2C。

        其中pi表示第i个类别在整个训练数据中出现的概率,可以用属于此类别元素的数量除以训练数据(即样本数据)总数量作为估计。

        具体问题具体分析:是否发放贷款,将9个发放归为一类,剩余6个不发放归为一类,这样进行分类的信息熵为:

信息增益(information gain)

        信息增益是指信息划分前后的熵的变化,也就是说由于使用这个属性分割样例而导致的期望熵降低。也就是说,信息增益就是原有信息熵与属性划分后信息熵(需要对划分后的信息熵取期望值)的差值,具体计算法如下:

                                       

        其中,第二项为属性A对S划分的期望信息。

具体问题具体分析

        年龄为已知条件的条件熵为

       以年龄为条件的信息增益为

        

      有工作的信息增益


       有房子的信息增益

       信贷情况的信息增益

        最后比较各特征的信息增益值,对于特征A3有自己房子的信息增益值最大,所以选择特征A3作为最优特征。

由于特征A3(有自己房子)的信息增益值最大,所以选择特征A3作为根节点的特征。它将训练数据集划分为两个子集D1(A3取值为是)和D2(A3取值为否)。由于D1只有同一类样本点,可以明确要贷款给D1,所以它成为一个叶节点,节点类标记为“是”。

对于D2则需要从特征A1(年龄),A2(有工作)和A4(信贷情况)中选择新的特征。计算各个特征的信息增益:


选择信息增益最大的特征A2(有工作)作为节点特征。A2有2个取值,一个对应“是”(有工作)的子节点,包含3个样本,他们属于同一类,所以这是一个叶节点,类标记为“是”;另一个对应“否”(无工作)的子节点,包含6个样本,属于同一类,这也是一个叶节点,类标记为“否”。

换句话有15个贷款人,经过是否有房这一筛选条件,有房子的6个人能够贷款。剩余9个人需要进一步筛选,以是否有工作为筛选条件,有工作的3个人可以贷款,无工作的6个人不能够贷款。

        该决策树只用了两个特征(有两个内部结点),以有自己的房子作为首要判决条件,然后以有工作作为判决条件是否可以贷款。

决策树生成阶段

决策树学习比较典型的有三种算法:ID3算法、 C4.5算法和CART算法。

一、ID3算法

        ID3算法由Ross Quinlan发明,建立在“奥卡姆剃刀”的基础上:越是小型的决策树越优于大的决策树(be simple简单理论)。

        ID3算法中根据信息增益评估和选择特征,每次选择信息增益最大的特征作为判断模块建立子结点。

        ID3算法可用于划分标称型数据集,没有剪枝的过程,为了去除过度数据匹配的问题,可通过裁剪合并相邻的无法产生大量信息增益的叶子节点(例如设置信息增益阀值)。

       使用信息增益的话其实是有一个缺点,那就是它偏向于具有大量值的属性。就是说在训练集中,某个属性所取的不同值的个数越多,那么越有可能拿它来作为分裂属性,而这样做有时候是没有意义的。

ID3算法步骤:


二、C4.5算法

        C4.5算法用信息增益率来选择属性,继承了ID3算法的优点。并在以下几方面对ID3算法进行了改进:

  • 用信息增益率来选择属性,克服了用信息增益选择属性偏向选择多值属性的不足;
  • 在构造树的过程中进行剪枝;
  • 能够完成对连续属性进行离散化;
  • 能够对不完整的数据进行处理。


        C4.5算法产生的分类规则易于理解、准确率较高;但效率低,因树构造过程中,需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描,C4.5只适合于能够驻留于内存的数据集。

        在实现过程中,C4.5算法在结构与递归上与ID3完全相同,区别只在于选取决决策特征时的决策依据不同,二者都有贪心性质:即通过局部最优构造全局最优。

C4.5算法步骤:



三、CART算法

        CART,即分类和回归树(classification and regression tree),也是一种应用很广泛的决策树学习方法。这是一种可以处理离散特征值和连续特征值的决策树,处理离散特征值使用分类决策树,处理连续特征值使用回归决策树。

        作为分类树时,其本质与ID3、C4.5并有多大区别,只是选择特征的依据不同而已。另外,CART算法建立的决策树一般是二叉树,即特征值只有yes or no的情况(个人认为并不是绝对的,只是看实际需要)。当CART用作回归树时,以最小平方误差作为划分样本的依据。

        基尼指数 (Gini)

            分类树采用基尼指数选择最优特征。                                                                                                                                                                假设有K个类,样本点属于第k类的概率为pk,则概率分布的基尼指数定义为:


            对于给定的样本集合D,其基尼指数为:


Ck是  D中 属于第k类 的样本子集,K是 类的个数。

CART分类树的算法步骤: 


决策树剪枝阶段

先剪枝:  
        通过提前停止树的构造,如通过决定在给定的节点不再分裂或划分训练元组的子集,而对树剪枝,一旦停止,该节点即成为树叶。在构造树时,可以使用诸如统计显著性、信息增益等度量评估分裂的优劣,如果划分一个节点的元组低于预先定义阈值的分裂,则给定子集的进一步划分将停止。但选取一个适当的阈值是困难的,较高的阈值可能导致过分简化的树,而较低的阈值可能使得树的简化太少。

后剪枝:

        它由完全生长的树剪去子树,通过删除节点的分支,并用树叶替换它而剪掉给定节点的子树,树叶用被替换的子树中最频繁的类标记。

  其中C4.5算法使用悲观剪枝方法CART算法则为代价复杂度剪枝算法(后剪枝)。

  悲观剪枝法的基本思路是:设训练集生成的决策树是T,用T来分类训练集中的N的元组,设K为到达某个叶子节点的元组个数,其中分类错误地个数为J。由于树T是由训练集生成的,是适合训练集的,因此J/K不能可信地估计错误率。所以用(J+0.5)/K来表示。设S为T的子树,其叶节点个数为L(s)

        为到达此子树的叶节点的元组个数总和


        为此子树中被错误分类的元组个数之和。在分类新的元组时,则其错误分类个数为


        其标准错误表示为:

        当用此树分类训练集时,设E为分类错误个数,当下面的式子成立时,则删掉子树S,用叶节点代替,且S的子树不必再计算。


ID3算法 -- 实例

    根据头发和声音怎么判断一位同学的性别。

头发声音性别
from math import log
import operator

def calcShannonEnt(dataSet):  # 计算数据的熵(entropy)
    numEntries=len(dataSet)  # 数据条数
    labelCounts={}
    for featVec in dataSet:
        currentLabel=featVec[-1] # 每行数据的最后一个字(类别)
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel]=0
        labelCounts[currentLabel]+=1  # 统计有多少个类以及每个类的数量
    shannonEnt=0
    for key in labelCounts:
        prob=float(labelCounts[key])/numEntries # 计算单个类的熵值
        shannonEnt-=prob*log(prob,2) # 累加每个类的熵值
    return shannonEnt

def createDataSet():    # 创造示例数据
    dataSet = [[\'长\', \'粗\', \'男\'],
               [\'短\', \'粗\', \'男\'],
               [\'短\', \'粗\', \'男\'],
               [\'长\', \'细\', \'女\'],
               [\'短\', \'细\', \'女\'],
               [\'短\', \'粗\', \'女\'],
               [\'长\', \'粗\', \'女\'],
               [\'长\', \'粗\', \'女\']]
    labels = [\'头发\',\'声音\']  #两个特征
    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

def chooseBestFeatureToSplit(dataSet):  # 选择最优的分类特征
    numFeatures = len(dataSet[0])-1
    baseEntropy = calcShannonEnt(dataSet)  # 原始的熵
    bestInfoGain = 0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 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):    #按分类后类别数量排序,比如:最后分类为2男1女,则判定为男;
    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


if __name__==\'__main__\':
    dataSet, labels=createDataSet()  # 创造示列数据
    print(createTree(dataSet, labels))  # 输出决策树模型结果

输出结果为:

{\'声音\': {\'细\': \'女\', \'粗\': {\'头发\': {\'短\': \'男\', \'长\': \'女\'}}}}
      这个结果的意思是:首先按声音分类,声音细为女生;然后再按头发分类:声音粗,头发短为男生;声音粗,头发长为女生。