机器学习（3）决策树

2019-02-11

一、决策树

决策树(decision tree)是一种基本的分类与回归方法。

分类决策树模型是一种描述对实例进行分类的树形结构。
决策树由结点(node)和有向边(directed edge)组成。
结点有两种类型：内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。

我们可以将决策树转换成if-then规则：由决策树的根结点(root node)到叶结点(leaf node)的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。

决策树要如何构建呢？通常，这一过程可以概括为3个步骤：

特征选择
决策树的生成
决策树的修剪

二、特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。

通常特征选择的标准是信息增益(information gain)。在划分数据集之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

香农熵

信息论之父克劳德·香农，威廉庞德斯通在05年出版的《财富公式》中这样描述香农：“贝尔实验室和MIT有很多人将香农和爱因斯坦相提并论，而其他人则认为这种对比是不公平的–对香农是不公平的。”

熵本来是个热力学名词，热力学中表征物质状态的参量之一，用符号S表示，其物理意义是体系混乱程度的度量。冯诺依曼建议使用“熵”来定义信息的期望值。

待分类的事务可能划分在多个分类之中，则符号 $x_i$ 的信息定义为 $l(x_i)=- \log_2{p(x_i)}$ ，其中 $p(x_i)$ 是选择该分类的概率。

所有类别所有可能值包含的信息期望值，可通过公式得到： $H=- \sum_{i=1}^n{p(x_i) \log_2{p(x_i)}}$ ，其中n是分类的数目，熵越大，随机变量的不确定性就越大。

要说信息为啥定义成这样？不知道，记住用就好。因为我至今也不知道为啥1+1=2。

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。什么叫由数据估计？浅显的解释就是，这概率是我们根据数据数出来的。我们定义训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类C_k, = 1,2,3,…,K,|C_k|为属于类Ck的样本个数，因此经验熵公式就可以写为:

H(D)=- \sum_{k=1}^K {\dfrac{|C_k|}{|D|} \log_2{\dfrac{|C_k|}{|D|}}}

信息增益

信息增益是相对于特征而言的，信息增益越大，特征对最终的分类结果影响也就越大，我们就应该选择对最终分类结果影响最大的那个特征作为我们的分类特征。

条件熵H(Y|X)表示在已知随机变量X的条件下，随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵(conditional entropy)H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

H(Y|X) = \sum_{i=1}^n{p_i H(Y|X=x_i)}

其中，当条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的条件熵称为条件经验熵(empirical conditional entropy)。

p_i = P(X=x_i),i=1,2,...,n

信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

g(D,A)=H(D)-H(D|A)

设特征A有n个不同的取值{a1,a2,···,an}，根据特征A的取值将D划分为n个子集{D1,D2，···,Dn}，|Di|为Di的样本个数。记子集Di中属于Ck的样本的集合为Dik，即Dik = Di ∩ Ck，|Dik|为Dik的样本个数。于是经验条件熵的公式：

H(D|A) = \sum_{i=1}^n{\dfrac{|D_i|}{|D|} H(D_i)} = - \sum_{i=1}^n{\dfrac{|D_i|}{|D|} \sum_{k=1}^K {\dfrac{|D_{ik}|}{|D_i|} \lg{\dfrac{|D_{ik}|}{|D_i|}}} }

上面的公式看着头有些晕，下面对概念进行通俗解释，并且找个简单的例子实际计算一下，应该就豁然开朗了。

通俗解释

1、熵：表示一个随机变量的复杂性或者不确定性。

假我要剁手买一件衣服，但是我一直犹豫着要不要买，我决定买这件事的不确定性（熵）为2.5。

2、条件熵：表示在直到某一条件后，某一随机变量的复杂性或不确定性。

我在看了这件衣服的评价后，我决定买衣服这件事的不确定性是1.2。

我在线下实体店试穿衣服后，我决定买衣服这件事的不确定性是0.9。

3、信息增益：表示在知道某一条件后，某一随机变量的不确定性的减少量。

一个是看了网上的评价，此时的信息增益是Gain1=2.5−1.2=1.3。

另一个是线下试穿了衣服，此时的信息增益Gain2=2.5−0.9=1.6。

熵和信息增益实例1

问题背景

对海洋生物的两个特征“不浮出水面是否可以生存”和“是否有脚蹼”，是否属于鱼类。有数据如下：

海洋生物	不浮出水面是否可以生存	是否有脚蹼	属于鱼类
1	是	是	是
2	是	是	是
3	是	否	否
4	否	是	否
5	否	是	否

熵的计算

按照定义，整体数据集的经验熵为：-2/5 lg(2/5)- 3/5 lg(3/5)=0.9709505944546686。

如果“是否是鱼类”的结果都是yes或者no，那么可计算得到 -5/5 * lg(5/5)=0。熵为0，变量的不确定性为0，即结果是确定的。

熵的代码实现

'''
trees.py
'''
from math import log

def calcShannonEnt(dataSet):
    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.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

import trees

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

if __name__ == '__main__':
    dataSet,label=createDataSet()
    shannonEnt=trees.calcShannonEnt(dataSet)
    print(shannonEnt) #0.9709505944546686

信息增益的计算

设定特征A1-不浮出水面是否可以生存，特征A2-是否有脚蹼。

1、A1的信息增益

会根据A1划分为两个子数据集D1=[[1, 1, ‘yes’],[1, 1, ‘yes’],[1, 0, ‘no’]]和D2=[[0, 1, ‘no’],[0, 1, ‘no’]]。

g(D,A1)=H(D)-[3/5 H(D1) + 2/5 H(D2)]

H(D)=0.9709505944546686，前面有计算。

H(D1)=-1/3 * lg(1/3)- 2/3 * lg(2/3)=0.9183

H(D2)= -2/2 lg(2/2)=0

g(D,A1)= 0.41997

2、A2特征的信息增益

会根据A2划分为两个子数据集，D1=[[1, 1, ‘yes’],[1, 1, ‘yes’],[0, 1, ‘no’],[0, 1, ‘no’]]和D2=[[1, 0, ‘no’]]

可得出g(D,A2)=H(D)-[4/5 H(D1) + 1/5 H(D2)]

H(D1)=-2/4 * lg(2/4)- 2/4 * lg(2/4)=1

H(D2)= -1/1 lg(1/1)=0

g(D,A2)= 0.17095

3、通过数学计算，或者下方代码实现，可得出g(D,A1)的信息增益更大，所以选择A1作为最优特征。

信息增益的代码实现

'''
trees.py
'''
from math import log

def splitDataSet(dataSet, axis, value):
    retDataSet = []  #创建返回的数据集列表，必须创建新的，否则会修改原dataSet
    for featVec in dataSet: #遍历数据集
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]  #去掉axis特征
            reducedFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reducedFeatVec) #将符合条件的添加到返回的数据集
    return retDataSet   #返回划分后的数据集


def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1  # 最后一列用于标签label
    baseEntropy = calcShannonEnt(dataSet) # 计算整体集合的经验熵
    bestInfoGain = 0.0;                 # 最大信息增益
    bestFeature = -1                    # 最优特征索引
    for i in range(numFeatures):  # 遍历特征值
        featList = [example[i] for example in dataSet]  # 获取数据集里所有该特征值，组成数组
        uniqueVals = set(featList)  # set集合，不可重复
        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

三、决策树的生成

得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个结点。在这个结点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。递归结束的条件是:程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。

构建决策树的算法有很多，比如ID3、C4.5和CART，下面使用ID3算法进行构造（流行的是C4.5和CART）

构造决策树

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), 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]  # stop splitting when all of the classes are equal
    if len(dataSet[0]) == 1:  # stop splitting when there are no more features in dataSet
        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[:]  # copy all of labels, so trees don't mess up existing labels
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

绘制的决策树如下:

测试和存储分类器

依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于构造树的标签向量。

'''
@File    :   tree_classify.py  
@Version : 1.0  
@Author :   iherr
@Desciption : 测试决策树分类
'''

import trees

def retrieveTree(i):
    listOfTrees =[{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}},
                  {'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}
                  ]
    return listOfTrees[i]

result=trees.classify(retrieveTree(0),['no surfacing', 'flippers'],[1,0])
print(result) # 结果为yes

构造决策树是很耗时的任务，可以用创建好的决策树解决分类问题。因此，为了节省计算时间，可以pickle序列化决策树对象，然后执行分类时读取直接调用。

def storeTree(inputTree, filename):
    '''
    存储决策树
    :param inputTree: 决策树
    :param filename: 文件名
    :return:
    '''
    import pickle
    fw = open(filename, 'wb')
    pickle.dump(inputTree, fw)
    fw.close()

def grabTree(filename):
    '''
    读取决策树
    :param filename: 文件名
    :return:
    '''
    import pickle
    fr = open(filename,'rb')
    return pickle.load(fr)

四、相关代码

『代码传送门』