决策树

问题引入

试想一下有一些海洋动物,它们有2个特征:1.不浮出海面是否可以生存 2.是否有脚蹼

image.png

根据这些特征我们可以将这些海洋动物分为2类(1,2和3,4,5)。显然是否属于鱼类和它们的各个特征之间是有联系的,就如上的数据而言,我们发现只要第一项特征为否就一定不属于鱼类,在第一项特征为是的情况下,还要根据第二项来判断是否为鱼类。根据这个简单的决策关系,我们可以做出一个简单的决策树。

image.png

那么当我们要去解决一个陌生领域的问题时,只要我们有大量的样本数据,就能通过决策树算法合理划分数据集,从而对一个全新的数据作出判断分类。现实中一些优秀的决策树往往能媲美在该领域中工作了十几年的专家。

前置芝士

信息熵

可以看出在决策树的建立过程中选取哪个特征进行划分是关键。信息熵就是衡量选取特征好坏的方式之一。

何为信息熵?给个通俗的理解,大家都知道小明cpp课平时在睡觉。期末考试发生了以下两种情况。

A. 小明的cpp课挂科了。

B. 小明的cpp课拿到了90分的高分。

那么对于A事件,大家并不惊讶,这件事带来的信息熵就小;而对于B事件,显然大家都是没意料到的,这件事的信息熵就大。所以决策树里的信息熵就是我们通过划分数据集使数据集变得有序带来的信息增益。那么信息增益当然是越大越好。

设一件事情发生的概率为$p(x_i)$,所包含的信息为$l(x_i)$。

$$l(x_i)=-log_2p(x_i)$$

那么对于一个有不同标签的数据集而言,它的熵就需计算所有类别所有可能值所包含的信息总和。

$$H=-\sum_{i=1}^{n}p(x_i)log_2p(x_i)$$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def calcEnt(dataSet): #计算给定数据集的熵
    numEnts=len(dataSet)  #数据集中实例的总数
    labels={}
    for featvec in dataSet: #为所有可能分类创建字典
        curlabel=featvec[-1]
        labels[curlabel]=labels.get(curlabel,0)+1
    Ent=0
    for key in labels: # l(xi)=-log2p(xi)计算熵
        prob=labels[key]/numEnts
        Ent-=prob*log2(prob)
    return Ent

划分数据集

我们知道了如何计算给定数据集的信息熵,接下来就可以来选取划分属性了。

思路很简单:遍历所有的特征,计算出选取该特征作为划分依据时所得到的信息熵,从中选取最大的就好了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def splitDataSet(dataSet,axis,value): #根据axis来划分dataSet,返回去掉axis的dataset
    retDataSet=[]
    for featvec in dataSet:
        if(featvec[axis]==value):
            reducedfeatvec=featvec[:axis]
            reducedfeatvec.extend(featvec[axis+1:]) #去掉axis维
            retDataSet.append(reducedfeatvec)
    return retDataSet
def choseBestfeat(dataSet): #选取最好的划分属性
    numfeat=len(dataSet[0])-1 
    baseEnt=calcEnt(dataSet) #未划分数据集的熵
    bestInfoGain=0
    for i in range(numfeat): #依次选取不同的属性作为划分依据
        featlist=[value[i] for value in dataSet]
        featlist=set(featlist) #提取当前属性的所有value
        Ent=0
        for value in featlist: #计算划分数据集后的熵
            subdataSet=splitDataSet(dataSet,i,value)
            prob=len(subdataSet)/len(dataSet)
            Ent+=prob*calcEnt(subdataSet)
        if(baseEnt-Ent>bestInfoGain): #求出信息增益最大时的属性
            bestInfoGain=baseEnt-Ent
            bestfeat=i
    return bestfeat

构建决策树

准备工作都做完了,接下来到重头戏了,如何构建一个决策树。

1.选取信息熵最大的特征来划分数据集

2.所有特征都已经用作划分的依据或者每个分支下的所有实例都已经具有相同的分类

3.若满足2,退出 ;若不满足2,回到1继续划分

这就是递归构造决策树的过程。(这里树的存储是采用了python中的字典嵌套。)

maxclasscnt函数返回的是一个列表当中最多的class,目的是处理所有属性都已经遍历完,但依然有分支下的所有实例不具有相同的标签,因此只能多数代表少数(这也是决策树会判断失误的例子)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def maxclasscnt(classlist): #返回classlist中最多的class
    classcnt={}
    for label in classlist:
        classcnt=classcnt.get(label,0)+1
    sortedclasscnt=sorted(classcnt.items,key=operator.itemgetter(1),reverse=False)
    return sortedclasscnt[0][0]
def createTree(dataSet,labels): 
    classlist=[example[-1] for example in dataSet] 
    if(classlist.count(classlist[0])==len(classlist)): #当前的dataset已经类别相同,直接返回
        return classlist[0]
    if(len(dataSet[0])==1): #所有的属性都已经遍历完,返回最多的class
        return maxclasscnt(classlist) 
    bestfeat=choseBestfeat(dataSet)
    sublabels=labels[:]
    bestlabel=sublabels[bestfeat]
    mytree={bestlabel:{}} #字典嵌套建树,构建根节点
    del(sublabels[bestfeat]) #删除已经作为分类依据的属性
    featvalue=[example[bestfeat] for example in dataSet] #儿子节点可能的值
    featvalue=set(featvalue)
    for value in featvalue: #递归建树(分别将划分好的数据集作为儿子节点)
        mytree[bestlabel][value]=createTree(splitDataSet(dataSet,bestfeat,value),sublabels)
    return mytree

构建完后让我们来测试一下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def createDataSet():
    dataSet=[[1,1,"yes"],
        [1,1,"yes"],
        [1,0,"no"],
        [0,1,"no"],
        [0,1,"no"]]
    labels=["no surfacing","flippers"] #每个样本的2个属性
    return dataSet,labels
dataSet,labels=createDataSet()
mytree=createTree(dataSet,labels)

如果一切正常的话,得到的mytree应该是这样子的:

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

这个样子的树看起来很抽象对不对,等会我们就用matplob来绘制树的图。

下面我们先写一个输入新的数据时 分类的函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def classify(inputTree,featlabels,testVec): # 利用决策树分类
    root=list(inputTree.keys())[0]
    son=inputTree[root]
    featindex=featlabels.index(root) # 找到对应特征向量的索引
    for key in son.keys():
        if(testVec[featindex]==key):
            if(type(son[key]).__name__=='dict'): #如果下面还有儿子
                classlabel=classify(son[key],featlabels,testVec)
            else: classlabel=son[key]
    return classlabel