机器学习（二）分类决策树

 

分类决策树是一种基于特征对实例进行划分的树形结构。如下图：

图中包括有内部节点和叶子节点，叶子节点表示的是分类结果，而内部节点表示基于特征对实例的划分。如根节点，是根据特征x1是否大于a1进行划分，划分成两个内部节点，但是此时的两个内部节点各自所包含的实例中依然有不同类别的实例，需要进一步划分；于是在x1<a1(左子树)的实例中，根据特征x2是否大于a2再次进行划分，此时划分出来的两部分实例，属于同一部分的实例都属于同一类别，于是划分完毕。

从图上的根节点到最末的叶子节点的每一条路径都是一条划分规则，这些不同的划分规则互斥且完备，也就是说，不存在一个实例，能够通过两条以上的路径进行划分。决策树学习的目标就是从训练数据集中学习到这一组分类规则，使得能够对实例进行正确的分类。

决策树的生成过程是根据局部最优的原则生成的，即这个学习过程是递归地选择一个最优特征，使得对数据集有个最好的分类，最好的分类就是这些子集能够被基本正确分类甚至是已经达成叶节点的目标了，那么怎么具体用算式的方法去衡量数据集有了最好的分类呢？也就是说衡量选择的这个特征好不好的具体标准是什么？这个涉及到下面的信息增益和信息增益比。

能够对数据集进行分类的树模型不是唯一的。当特征很多的时候，特征选择的先后也会起到影响，也就是说需要对特征进行选择，如上所述每次选择最优的特征，好过每次随机进行选取一个特征可能造成的模型复杂度大。（特征选择）

决策树的一条自上而下的路径表示一个条件概率分布，越深的树它的概率模型复杂度就越大；有时候对树进行过于完美的细分不是一件好事，可能会造成过拟合。考虑到这两点，就有了决策树的剪枝，自下而上去掉一些分类过细的叶节点，使其退回到更高的节点。决策树的剪枝相对于决策树的生成，剪枝考虑的是全局最优，生成是局部最优。（剪枝）

二、信息增益和信息增益比

 熵H(p)可以度量随机变量X的不确定性，这里的随机变量X是离散情况下可以通过下式计算熵：

当X取值为二值时，熵的变化曲线如下：

也就是说，当概率p=0.5时，即X取1的概率是0.5，取0的概率是0.5，此时随机变量具有最大的不确定性，通俗理解为：我们认为它取1或取0都是有道理的，如果说该X取1的概率为0.7，取0的概率为0.3，此时随机变量X的不确定性就没有前者那么大，毕竟我们明确的知道了X更可能取1。

以上是熵的定义，接下来解释条件熵：

就5.5这个式子而言，左式的H(Y|X)和右式的H(Y|X=xi)特别像，但是也是有区别的。左式H(Y|X)表示已知随机变量X的条件下随机变量Y的不确定性，含义就是这个已知的X可以是任何值；而右式中的H(Y|X=xi)表示的是随机变量X具体取某一个值下随机变量Y的不确定性，故它们的差别可以通过加上一个求和项来填补，只要将X取所有可能值的熵都加和，不就得到了左式吗？

当熵和条件熵中涉及的概率是由数据估计得到的，即通过我们的已有训练数据集得到的时候，我们称之为“经验”，即为经验熵和经验条件熵。

再回到最开始说明的决策树生成的过程，每一次遍历的选择一个最佳特征进行分类，这个特征要使得分类效果最好。衡量这一点的就有信息增益和信息增益比。假如我们不做特征选择，直接分，那么我们得到的就是最原始的这个数据集D的经验熵H(D)，如果就这么拿去给新样本进行分类，有很大的不确定性——就像我们有一组关于男女外貌特征及性别(分类类别)的数据集，数据中显示留长发(特征)的人都是女性，然后再给一个新样本，我们就可以根据新样本是否留长发来判断他的性别，这样通过特征来判断类别有助于提高准确性，假如我们不这样做，单纯给一个新样本，我们只好说新样本是女性的概率为0.5。

信息增益和信息增益比可以衡量这个特征的选择好还是不好。因为信息增益表示特征X的信息使得类别Y的信息不确定性减少的程度，如果在众多特征中选择一个特征，使得此时的信息增益比选择其他特征都大，那么这个特征就是一个当下最好的特征，它可以极大的降低分类过程中信息的不确定性。

 那么5.6中的集合D的经验熵H(D)具体要怎么算，参考下图的例子：

在不进行特征选择的时候，H(D)只用数一下类别Y即可，即上图的最后一列，这个数据表里的类别一共有6个‘否’，9个‘是’，通过数据估计的方法我们计算可得：

$H\left ( D \right )= -\frac{9}{15}log\left ( \frac{9}{15} \right )-\frac{6}{15}log\left ( \frac{6}{15} \right )$

给定特征条件A下D的经验条件熵H(D|A)稍微复杂一点，我们要先数出特征A中的比例，假设这里选择“有工作”这列作为特征A，有10个‘否’，5个‘是’；然后我们在这10个‘否’中数类别，有6个‘否’，4个‘是’；在特征A中的5个‘是’里操作相同：

$H\left ( D \right )= \frac{10}{15}[-\frac{6}{10}log\left ( \frac{6}{10} \right )-\frac{4}{10}log\left ( \frac{4}{10} \right )]+\frac{5}{15}[-\frac{5}{5}log\left ( \frac{5}{5} \right )-\frac{0}{5}log\left ( \frac{0}{5} \right )]$

二者之差就是信息增益。

但是，如果特征的取值有更多可能，就意味着经验条件熵会更小，二者差值会更大，信息增益会更大，这样在训练数据的时候，会偏向于选择取值较多的特征，这并不意味这这些特征更好（如上表的年龄和信贷情况特征），我们要排除掉因为特征取值个数不同所造成的差异，就有了信息增益比。信息增益比就是在我们计算出信息增益后，再除以这个特征A本身的熵，以上述为例，特征‘有工作’的熵为：

$-\frac{10}{15}log\left ( \frac{10}{15} \right )-\frac{5}{15}log\left ( \frac{5}{15} \right )$

这里有一个问题，特征的取值有更多的可能，熵就会越小？脑子里想了一下log函数关于x轴的翻转，好像简单通过图像无法进行解释，可能还得有空翻一下论文。

三、ID3算法和C4.5算法

二者的区别就在于生成树的时候采用信息增益原则还是信息增益比原则，ID3使用信息增益，C4.5使用信息增益比。既然差不多就一块讲了吧。

有两种特殊情况先事先说明，一是数据集所有样本都同属一个类别的时候，此时为单节点树，直接返回就好；二是没有特征，都没特征了所以也就不涉及特征选择啥的，那就看一下样本集里哪种类别多，就返回那个类别的节点就好，也是单节点树。

好，除了这两种特殊情况以外，剩下的情况就是，数据集有多个类别，也有特征供我们进行选择的正常情况了。先贴一个算法，然后在下面进行通俗解释：

就是排除了特殊情况后，设定一个阈值，先把所有特征的信息增益或信息增益比算出来，和阈值进行比较，这个阈值通常是一个比较小的值，如果发现所有特征的信息增益都比这个阈值还小，那么这个树就不用生成了，因为这些特征都不能很好的体现不同类别的区别，何必费心，直接定为单节点树算了。

但是如果并非所有的特征计算得信息增益都小于这个阈值，那就先把最大的那个特征先选咯，选择了这个特征就意味着我们把数据集进行了一个划分，分成了不同块，然后我们现在就要在每一块数据集里重复我们的上述工作：判断类别，判断是否有可选特征，判断与阈值的比较，选择最大的特征。这里要注意，已经选择过的特征不可以再进行选择。

那么什么时候终结呢，直到没有特征选了，知道划分出来的这块数据的类别相同了，直到剩下的特征的信息增益都小于我定的阈值了，这三点满足任意一个都可以终结该子树。

四、剪枝

刚开始机器学习的时候，会提到一个词‘过拟合’。在决策树里也有过拟合，就是一昧追求将训练数据完美划分，而将树分得过细，造成在生成子树的后期，会花很多的代价，只为提高一点点的准确率；还有就是这棵树，对训练集分类效果好，对任意一个新样本可就不一定了，树越细，就为新样本提了更多的要求，分错的概率也大大提高了，这新样本哪怕有一点不对，就会错过它的正确类别。

剪枝就是将已经生成的树进行简化，裁掉一些子树或者叶节点，使其退回到父节点。然后这里也涉及到剪枝的原则，剪枝的原则是整棵树损失函数极小化，那树的损失函数又怎么进行衡量呢，最小化又怎么计算呢？

先思考决策树的损失是什么，损失来源是什么，主要原因就是叶子节点太多了！不是说数据集的类别多，而是说分出来的叶子节点，其中可能有很多重复的类别。叶子节点多意味着分得细，就像前面说的，刚开始选择特征进行分类，可以使信息的不确定性下降90%，而到了后期，再选择特征分类时，可能只能使不确定性下降0.00001%，那花了同样的精力得到的回报实在太少，索性不干了！

于是，决策树的损失可以如下衡量：

也就是说，我们将每个叶节点上的样本数，乘以其叶节点的经验熵，就是决策树学习损失函数的第一项。如果一个叶节点上的所有样本都同属一个类别的话，其不确定性是最小的，即熵为0，因为给一个样本，只要样本它能够通过层层划分到这个叶节点，我们就可以确定的说出这个样本的类别。那么是否存在有的叶节点的熵不为0呢？也就是说是否一个叶子节点上的所有样本的类别不同？是有可能的，因为前面提到树的生成的时候讲到一个“阈值”，如果剩下来的特征的信息增益没那么大的时候，也就是说这些特征都不能够对样本进行一个很好的分类时，我们就不会再选择样本，而是让此时节点中 样本类别占比最大的 类别 作为该节点的分类结果，这种时候叶节点的经验熵就很可能不为0，而是一个大于0的数。

那么，经验熵为0和经验熵不为0，哪个更好一点，按照我们现在的说法来说，分的太细了肯定不好，就是说熵为0的时候不好，但是，分得太细和熵为0是等同关系吗？不是的，还有一些决策树，因为样本或特征选择优秀，就能够很好很准确的划分开数据集的类别。比如前面提到了，用[是否长发]这个特征来判断男女，这样划分出来的类别肯定是不准的，因为总有男生喜欢飘逸，也有女生走帅气风，那么我们的数据集里如果能采取到[DNA]呢？就能够很准确的划分开男女类别，并且只选取了一个特征，这种情况下的叶节点的熵也是0，但是就是一个非常简短且优秀的决策树。

所以单单从经验熵来判断完全不够，就必须有损失函数的第二项，T是树的节点数，第二项就是说明如果一棵树它的节点很多，这种树是不好的。因为节点多，说明这棵树，选了一个特征分不全，再选一个，再选一个...就会分得很细，即便它最后的叶子节点分得很准确（熵为0），但是由于节点数过多，损失函数依旧很大。

最好的树就是，仅用几个特征就分好了，而且叶子节点中只包含同一类的样本。除此之外的树的损失函数值都很大，都不大好。

不好的树就要进行剪枝，剪枝的思想其实比较简单，从下往上剪，分别计算剪枝前和剪枝后的损失函数值，如果剪枝后损失函数值有所下降，那么就可以剪枝，否则就不要剪。

先挖个坑，这里要用动态规划的方法来剪，等有空了去翻一下论文先。

五、项目

def createBranch():
    检测数据集中的所有数据的分类标签是否相同:
        If so return 类标签
        Else:
            寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
            划分数据集
            创建分支节点
                for 每个划分的子集
                    调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
            return 分支节点

案例需求：我们采集海洋生物数据信息，选择其中5条如下表所示，从诸多特征中选择2个最主要特征，以及判定是否属于鱼类（此处我们选择二分类法即只考虑鱼类和非鱼类）。根据这些信息如何创建一个决策树进行分类并可视化展示？

根据上表，先把数据输进去，如果是很多的数据，就要通过pandas进行导入了：

#创建数据集，返回数据集和特征名
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

# 1 打印数据集和标签
dataset,label=createDataSet()
print(dataset)
print(label)

输出结果：

 

#计算熵
def calcShannonEnt(dataSet):
    # 需要对 list 中的大量计数时,可以直接使用Counter,不用新建字典来计数
    label_count = Counter(data[-1] for data in dataSet) # 统计标签出现的次数
    probs = [p[1] / len(dataSet) for p in label_count.items()] # 计算概率
    shannonEnt = sum(np.array([-p * np.math.log(p, 2) for p in probs]))# 计算香农熵
    print(de.Decimal(shannonEnt).quantize(de.Decimal('0.00000')))
    return shannonEnt

# 2 计算数据集的熵
calcShannonEnt(dataset)

输出结果为0.97095，这是原数据集的熵，也就是不考虑特征，只通过数类别的个数然后再套用熵公式算出来的。主要是因为这里的五个样本中类别的分布是2:3，接近1:1，即在不给特征的时候，判断一个样本的类别的准确率很接近0.5，p=0.5时数据的不确定性最大。这里接近0.5，也可以认为此时不确定性很大。

接下来要做的就是选择一个信息增益最大的特征进行分类，信息增益最大等价于特征的经验条件熵最小，经验条件熵最小可以说明这个特征的分类能够达到最好的准确率。

先跳过特征条件熵的计算，看如何基于某个特征划分数据集：

#根据特征划分数据集
def splitDataSet(dataSet, index, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[index] == value:# 判断index列的值是否为value
            reducedFeatVec = featVec[:index] # [:index]表示取前index个特征
            reducedFeatVec.extend(featVec[index+1:]) # 取接下来的数据
            retDataSet.append(reducedFeatVec)
    print(retDataSet)
    return retDataSet

#3 划分数据集
splitDataSet(dataset,0,1)#根据第0个特征是否为1进行划分

这三个返回的样本都是第0个特征为1的样本点。

接下来把计算集合熵，和特征选择部分结合：

#选择最好的特征
def chooseBestFeatureToSplit(dataSet):
    base_entropy = calcShannonEnt(dataSet) # 计算初始香农熵
    best_info_gain = 0
    best_feature = -1
    # 遍历每一个特征
    for i in range(len(dataSet[0]) - 1):
        # 对当前特征进行统计
        feature_count = Counter([data[i] for data in dataSet])
        # 计算分割后的香农熵
        new_entropy = sum(feature[1] / float(len(dataSet)) * calcShannonEnt(splitDataSet(dataSet, i, feature[0])) for feature in feature_count.items())
        # 更新值
        info_gain = base_entropy - new_entropy
        # print('No. {0} feature info gain is {1:.3f}'.format(i, info_gain))
        if info_gain > best_info_gain:
            best_info_gain = info_gain
            best_feature = i
    print(best_feature)
    return best_feature

# 4 选择最好的数据集划分方式
chooseBestFeatureToSplit(dataset)

输出为0，说明0是最好的特征，我们要选择特征0进行划分。

接下来构建树，构建出这个树后，可以进行保存反复使用：

def majorityCnt(classList):
    major_label = Counter(classList).most_common(1)[0]
    print('sortedClassCount:', major_label[0])
    return major_label[0]

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]#翻转数据集
    # 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行
    # 第一个停止条件：所有的类标签完全相同，则直接返回该类标签。
    # count() 函数是统计括号中的值在list中出现的次数
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
    # 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    # 选择最优的列，得到最优列对应的label含义
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 获取label的名称
    bestFeatLabel = labels[bestFeat]
    # 初始化myTree
    myTree = {bestFeatLabel: {}}
    # 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list
    #del(labels[bestFeat])
    # 取出最优列，然后它的branch做分类
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # 求出剩余的标签label
        subLabels = labels[:]
        # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
        # print('myTree', value, myTree)
    print(myTree)
    return myTree

输出结果为：{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

解读一下就是先对'no surfacing'特征划分，再对'flippers’划分。

然后有了树，也有了特征选取，也有了熵的计算，现在开始进行类别的判定：

def classify(inputTree, featLabels, testVec):
    firstStr = list(inputTree.keys())[0] # 获取tree的根节点对于的key值
    secondDict = inputTree[firstStr]  # 通过key得到根节点对应的value
    # 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类
    featIndex = featLabels.index(firstStr)
    for key in secondDict.keys():
        if testVec[featIndex] == key:#如果测试数据的特征等于中间节点的key
            if type(secondDict[key])is dict:
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:
                classLabel = secondDict[key]
    print(classLabel)
    return classLabel

再把所有的联合一下：

def fishTest():
    # 1.创建数据和结果标签
    myDat, labels = createDataSet()

    # 计算label分类标签的香农熵
    calcShannonEnt(myDat)

    # 求第0列 为 1/0的列的数据集【排除第0列】
    print('1---', splitDataSet(myDat, 0, 1))
    print('0---', splitDataSet(myDat, 0, 0))

    # 计算最好的信息增益的列
    print(chooseBestFeatureToSplit(myDat))

    import copy
    myTree = createTree(myDat, copy.deepcopy(labels))
    # [1, 1]表示要取的分支上的节点位置，对应的结果值
    print(classify(myTree, labels, [1, 1]))
    
fishTest()

结果为：

 

 

全代码如下：

import decimal as de
import numpy as np
from collections import Counter
#创建数据集，返回数据集和特征名
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


#计算熵
def calcShannonEnt(dataSet):
    # 需要对 list 中的大量计数时,可以直接使用Counter,不用新建字典来计数
    label_count = Counter(data[-1] for data in dataSet) # 统计标签出现的次数
    probs = [p[1] / len(dataSet) for p in label_count.items()] # 计算概率
    shannonEnt = sum(np.array([-p * np.math.log(p, 2) for p in probs]))# 计算香农熵
    #print(de.Decimal(shannonEnt).quantize(de.Decimal('0.00000')))
    return shannonEnt


#根据特征条件熵划分数据集
def splitDataSet(dataSet, index, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[index] == value:# 判断index列的值是否为value
            reducedFeatVec = featVec[:index] # [:index]表示取前index个特征
            reducedFeatVec.extend(featVec[index+1:]) # 取接下来的数据
            retDataSet.append(reducedFeatVec)
    #print(retDataSet)
    return retDataSet




#选择最好的特征
def chooseBestFeatureToSplit(dataSet):
    base_entropy = calcShannonEnt(dataSet) # 计算初始香农熵
    best_info_gain = 0
    best_feature = -1
    # 遍历每一个特征
    for i in range(len(dataSet[0]) - 1):
        # 对当前特征进行统计
        feature_count = Counter([data[i] for data in dataSet])
        # 计算分割后的香农熵
        new_entropy = sum(feature[1] / float(len(dataSet)) * calcShannonEnt(splitDataSet(dataSet, i, feature[0])) for feature in feature_count.items())
        # 更新值
        info_gain = base_entropy - new_entropy
        # print('No. {0} feature info gain is {1:.3f}'.format(i, info_gain))
        if info_gain > best_info_gain:
            best_info_gain = info_gain
            best_feature = i
    #print(best_feature)
    return best_feature


def majorityCnt(classList):
    major_label = Counter(classList).most_common(1)[0]
    #print('sortedClassCount:', major_label[0])
    return major_label[0]

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]#翻转数据集
    # 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行
    # 第一个停止条件：所有的类标签完全相同，则直接返回该类标签。
    # count() 函数是统计括号中的值在list中出现的次数
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
    # 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    # 选择最优的列，得到最优列对应的label含义
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 获取label的名称
    bestFeatLabel = labels[bestFeat]
    # 初始化myTree
    myTree = {bestFeatLabel: {}}
    # 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list
    del(labels[bestFeat])
    # 取出最优列，然后它的branch做分类
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # 求出剩余的标签label
        subLabels = labels[:]
        # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
        # print('myTree', value, myTree)
    print(myTree)
    return myTree

def classify(inputTree, featLabels, testVec):
    firstStr = list(inputTree.keys())[0] # 获取tree的根节点对于的key值
    secondDict = inputTree[firstStr]  # 通过key得到根节点对应的value
    # 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类
    featIndex = featLabels.index(firstStr)
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]) is dict:
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:
                classLabel = secondDict[key]
    #print(classLabel)
    return classLabel


def fishTest():
    # 1.创建数据和结果标签
    myDat, labels = createDataSet()

    # 计算label分类标签的香农熵
    calcShannonEnt(myDat)

    # 求第0列 为 1/0的列的数据集【排除第0列】
    print('1---', splitDataSet(myDat, 0, 1))
    print('0---', splitDataSet(myDat, 0, 0))

    # 计算最好的信息增益的列
    print(chooseBestFeatureToSplit(myDat))

    import copy
    myTree = createTree(myDat, copy.deepcopy(labels))
    # [1, 1]表示要取的分支上的节点位置，对应的结果值
    print(classify(myTree, labels, [1, 1]))
    
fishTest()