机器学习实战之决策树基础笔记

决策树的优缺点

优点

• 计算复杂度不高
• 输出结果容易理解
• 对中间值的缺失不敏感
• 可以处理不相关特征数据

缺点

• 可能会产生过度匹配问题

决策树原理

《机器学习实战》书中讲了二十个问题的游戏的一个例子：就是参与游戏的一方脑子里想着某个事物。其他参与者可以向他提29个问题，但是答案只能用对错来回答。比如最简单的猜数游戏。我心里想一个数是7.然后A说你心里想的数比100小。然后我说正确。然后B说你心里想的数比10大，我说回答错误。然后C、D、E等人继续提问，直到那个数的范围越来越小，直到猜中答案。决策树的工作原理就是这样，用户给出一系列数据，然后给出游戏的答案。
相比于书中给出的邮件的例子，我更喜欢Jack Cui的例子，便于理解。所以下文中所有的例子以Jack Cui的例子为主。
如下就是一个决策树的树状图。决策树的结构主要是由结点和有向边组成。结点分为内部结点和叶结点。内部节点用来表示一个特征或者一个属性。叶结点表示一个类。长方形和椭圆形都是结点。长方形属于内部结点，下面还有分支或者叶结点。椭圆形是叶结点，下面没有分支。是结束。

对上图中的一些元素进行解释：

• 长方形代表判断模块
• 椭圆形代表终止模块，用于得到结论
• 从长方形（判断模块）出来的箭头是分支，可以到达另一个模块或者终止模块

流程图解释

这是一个简单的岳母相亲的分类模型。就是岳母来了先问问你有没有房子车子啊，如果有的话，你这个对象就可以被考虑了。
但是如果你没有车子也没有房子，但是你非常有上进心非常努力也可以啊，还是可以把你考虑进去的。然后当个备胎。如果没车没房没上进心，那肯定不符合岳母的标准啊。立马拜拜了。当然，这只是一个简单的分类模型，属性只有两个。

小结

决策树的模型其实是一个多种条件或者规则的结合。每一个从根节点到叶节点都是一个规则，或者说都对应着上面那个模型的一类人。决策树的各个路径或者规则的性质是互斥并且覆盖。

决策树的一般流程

• 收集数据
• 准备数据，对数据进行处理
• 分析数据：可以使用任何方法，构造树完成之后，检查图形是否符合我们的预期
• 训练算法：构造树的数据结构
• 测试算法：使用经验树计算错误率
• 使用算法，使用决策树解决实际问题，这个步骤适用于任何监督学习算法

决策树的构造

在构造一棵决策树之前，我们先使用信息论划分数据集，然后将编写代码到具体的数据集上，最后构建决策树。

特征选择

在构造一棵决策树之前，首先我们要对特征进行选择。特征选择选择什么？**特征选择就是选择出对训练数据有分类能力的特征。**选择的是当前数据集上那个特征在划分数据集分类上起到决定性的作用。所以我们想要划分出来最好的结果，就要对每一个特征进行评估。完成测试之后，原始的数据集就会被划分为几个数据子集，这些数据子集会分布在第一个决策点的所有分支上。如果某一个分支上的数据属于同一个类型，那么数据已经正确的划分了，不需要进一步对数据进行分割了。如果数据子集中的数据还不是同一类型，还要对数据子集进行再次划分，直到分支下的数据类型相同。

如果一次划分之后，各个分支下面都是相同类型的数据，比如，都是青年、中年、老年的数据，那么说明这次划分是成功的，然后可以在这个数据子集下面接着递归划分。
特征选择的标准是什么呢？通常特征选择的标准是信息增益或者信息增益比。
下面我们根据一个例子来进行学习。

上面这组数组是一个贷款申请的数据。我们通过训练以上数据来的带一个贷款申请的决策树。当一个新用户来申请贷款的时候，我们的树能够判断是否给放款。
特征选择是选择用哪个特征划分特征空间。我们以上面那个贷款的例子来自己构造两个不一样的决策树。

上面就是分别根据年龄和是否有工作两个特征构造的决策树。那么这两个决策树哪个更好呢。我们上面说过，我们按照现在的这个特征将训练的数据集分割成各个自己，使得各个自己在当前的条件下能够更好的分类，那么这个特征就是我们应该选择的。在这里就是说我们按照年龄和有工作这两个特征划分数据集，哪个特征更好分类，哪个特征就是好的。
那么信息增益的概念也就是这样。就是划分数据集之后信息的变化就是信息增益。就是我们按照年龄和工作划分数据集之后信息的变化。在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以
计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
在可以评测哪种数据划分方式是最好的数据划分之前，我们必须学习如何计算信息增益。集合信息的度量方式称为香农熵或者简称为熵，这个名字来源于信息论之父克劳德·香农。
熵定义是信息的期望值。熵是表示随机变量不确定性的变量。熵越大，随机变量的不确定性越大。计算信息增益和熵的公式如下：

其中p(xi)是选择该分类的概率。就是这种分类在这个总的数据中占的比例。比如一种商品有A、B两种。A有3中，B有2种。那么A的p(x)是3/5.B的p(x)的概率是2/5.上面的底数也可以是以e为底数。
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值。就是所有的类别的所有的可能值取和的过程。公式如下：

上式中，n是分类的数目。熵越大，随机变量的不确定性就越大。
当熵中的概率由数据统计（特别是最大似然估计）得到的时候，这个熵就是经验熵。数据统计就是通过数据统计（简单说就是我们根据数据数出来的）得到的分类的概率。
我们定义贷款申请样本数据表中的数据为训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck, = 1,2,3,…,K,|Ck|为属于类Ck的样本个数，因此经验熵公式就可以写为 ：

上面的我们给出的放贷的数据可得，分类的结果有两类。一共有15个数据，9个结果是放贷，6个结果是不放贷。那么经验熵如下：

编写代码

• 在写代码之前，对我们放贷的数据集进行属性标注。
• 年龄：0代表青年，1代表中年，2代表老年
• 工作情况：0代表没有工作，1代表有工作
• 是否有自己的房子：0代表没有自己的房子，1代表有自己的房子
• 信贷情况：0代表一般，1代表好，2代表非常好
• 是否放贷：no代表否 yes代表是

from math import log
'''
创建测试数据集
Returns:
    dataSet - 数据集
    labels - 分类属性
'''
def createDataSet():
    dataSet=[
        [0, 0, 0, 0, 'no'],  # 数据集
        [0, 0, 0, 1, 'no'],
        [0, 1, 0, 1, 'yes'],
        [0, 1, 1, 0, 'yes'],
        [0, 0, 0, 0, 'no'],
        [1, 0, 0, 0, 'no'],
        [1, 0, 0, 1, 'no'],
        [1, 1, 1, 1, 'yes'],
        [1, 0, 1, 2, 'yes'],
        [1, 0, 1, 2, 'yes'],
        [2, 0, 1, 2, 'yes'],
        [2, 0, 1, 1, 'yes'],
        [2, 1, 0, 1, 'yes'],
        [2, 1, 0, 2, 'yes'],
        [2, 0, 0, 0, 'no']
    ]
    labels=['放贷','不放贷']
    return dataSet,labels

'''
计算经验熵
Parameters:
    dataSet - 数据集
Returns:
    shannonEnt - 经验熵(香农熵)
'''
def calShannonEnt(dataSet):
    ##返回数据集的行数
    numEntires=len(dataSet)
    #保存每个label出现的次数
    labelCounts={}
    #对每一个特征向量统计
    for featVec in dataSet:
        #拿到标签
        currentLabel=featVec[-1]
        if currentLabel not in labelCounts.keys():
            #如果标签不在labelCounts，那么就放进去
                labelCounts[currentLabel]=0
        #如果标签在labelCounts的话，就计数
        labelCounts[currentLabel]+=1
    #计算经验熵
    ShannonEnt=0.0
    for key in labelCounts:
        #计算这个标签的概率
        prob=float(labelCounts[key])/numEntires
        ShannonEnt -= prob*log(prob,2)
    return ShannonEnt
if __name__ == '__main__':
    #调用函数创建数据集
    dataSet,features=createDataSet()
    print(dataSet)
    #计算经验熵
    print(calShannonEnt(dataSet))

打印结果：

划分数据集

计算完成熵之后，我们用熵来划分数据集。

条件熵

信息增益是用来衡量特征的，信息增益越大，特征对于最终的分类结果的影响也就越大。
在学习信息增益之前还要理解条件熵。
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。


当条件熵中的概率由数据统计（特别是极大似然估计）得到时，所对应的条件熵称为条件经验熵。

信息增益

信息增益是用来衡量特征的，信息增益越大，特征对于最终的分类结果的影响也就越大。所以，特征A对训练集D来说的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A在给定条件下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的样本个数。

还是用上面的例子（贷款申请模型）梳理一下。
年龄这一列的数据，也就是特征A1，一共有三个类别，分别是青年、中年和老年。这里暂时先看青年的数据。青年的数据是5个，所以年龄是青年的数据在训练集出现的概率是十五分之五。年龄是中年和老年的数据出现的概率也是十五分之五。而青年的数据贷款成功的概率是五分之二。年龄是中年和老年的贷款成功的概率是五分之三和五分之四。计算年龄的信息增益如下所示：

计算有工作g(D,A2)、有房子g(D,A3)、信贷情况g(D,A4)的信息增益如下:

通过比较最后得到，g(D,A3)的增益最大，说明特征最优。

计算信息增益

from math import log
'''
创建测试数据集
Returns:
    dataSet - 数据集
    labels - 分类属性
'''
def createDataSet():
    dataSet=[
        [0, 0, 0, 0, 'no'],  # 数据集
        [0, 0, 0, 1, 'no'],
        [0, 1, 0, 1, 'yes'],
        [0, 1, 1, 0, 'yes'],
        [0, 0, 0, 0, 'no'],
        [1, 0, 0, 0, 'no'],
        [1, 0, 0, 1, 'no'],
        [1, 1, 1, 1, 'yes'],
        [1, 0, 1, 2, 'yes'],
        [1, 0, 1, 2, 'yes'],
        [2, 0, 1, 2, 'yes'],
        [2, 0, 1, 1, 'yes'],
        [2, 1, 0, 1, 'yes'],
        [2, 1, 0, 2, 'yes'],
        [2, 0, 0, 0, 'no']
    ]
    labels=['放贷','不放贷']
    return dataSet,labels

'''
计算经验熵
Parameters:
    dataSet - 数据集
Returns:
    shannonEnt - 经验熵(香农熵)
'''
def calShannonEnt(dataSet):
    ##返回数据集的行数
    numEntires=len(dataSet)
    #保存每个label出现的次数
    labelCounts={}
    #对每一个特征向量统计
    for featVec in dataSet:
        #拿到标签
        currentLabel=featVec[-1]
        if currentLabel not in labelCounts.keys():
            #如果标签不在labelCounts，那么就放进去
                labelCounts[currentLabel]=0
        #如果标签在labelCounts的话，就计数
        labelCounts[currentLabel]+=1
    #计算经验熵
    ShannonEnt=0.0
    for key in labelCounts:
        #计算这个标签的概率
        prob=float(labelCounts[key])/numEntires
        ShannonEnt -= prob*log(prob,2)
    return ShannonEnt


def calcShannonEnt(dataSet):
    numEntires = len(dataSet)  # 返回数据集的行数
    labelCounts = {}  # 保存每个标签(Label)出现次数的字典
    for featVec in dataSet:  # 对每组特征向量进行统计
        currentLabel = featVec[-1]  # 提取标签(Label)信息
        if currentLabel not in labelCounts.keys():  # 如果标签(Label)没有放入统计次数的字典,添加进去
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1  # Label计数
    shannonEnt = 0.0  # 经验熵(香农熵)
    for key in labelCounts:  # 计算香农熵
        prob = float(labelCounts[key]) / numEntires  # 选择该标签(Label)的概率
        shannonEnt -= prob * log(prob, 2)  # 利用公式计算
    return shannonEnt  # 返回经验熵(香农熵)


'''
根据特征划分数据集
Parameters:
    dataSet - 待划分的数据集
    axis - 划分数据集的特征
    value - 需要返回的特征的值
Returns:
    无
'''
def splitDataSet(dataSet, axis, value):
    retDataSet = []                                        #创建返回的数据集列表
    for featVec in dataSet:                             #遍历数据集
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]                #去掉axis特征
            reducedFeatVec.extend(featVec[axis+1:])     #将符合条件的添加到返回的数据集
            retDataSet.append(reducedFeatVec)
    return retDataSet                                      #返回划分后的数据集

'''
说明：选择最优的特征
Parameters:
    dataSet - 数据集
Returns:
    bestFeature - 信息增益最大的(最优)特征的索引值
'''
def chooseBestFeatureToSplit(dataSet):
    #特征的数量
    numFeatures=len(dataSet[0])-1
    #计算数据集的熵
    baseEntropy=calShannonEnt(dataSet)
    #信息增益变量
    bestInfoGain=0.0
    #最优特征索引值
    bestFeature=-1
    #遍历所有的特征
    for i in range(numFeatures):
        #获取dataSet的第i个特征
        featList=[example[i] for example in dataSet]
        #注意set中元素不可重复
        uniqueVals = set(featList)
        #经验条件熵
        newEntropy=0.0
        #计算信息增益
        for value in uniqueVals:
            #划分子集
            subDataSet=splitDataSet(dataSet,i,value)
            #计算子集概率
            prob=len(subDataSet)/float(len(dataSet))
            #计算经验熵
            newEntropy += prob * calShannonEnt(subDataSet)
            #信息增益
            infoGain=baseEntropy-newEntropy
            #打印每个特征的信息增益
            print("第%d个特征的增益为%.3f" % (i, infoGain))
            #计算信息增益
            if(infoGain > bestInfoGain):
                #更新信息增益为最大的信息增益
                bestInfoGain=infoGain
                #记录信息增益的最大的特征的索引值
                bestFeature=i
    #返回最大增益的索引值
    return bestFeature

if __name__ == '__main__':
    #调用函数创建数据集
    dataSet,features=createDataSet()
    print("最优特征索引值:" + str(chooseBestFeatureToSplit(dataSet)))

    #print(dataSet)
    #计算经验熵
   # print(calShannonEnt(dataSet))

学习资料

1. Jack Cui的个人博客
2. 《机器学习实战》
3. 《机器学习》