机器学习基础-决策树理论-分类决策树

作者: 阿瑟_TJRS | 来源:发表于2020-04-25 18:25 被阅读0次

本文是笔者综合多篇博客，对决策树中的关键内容进行梳理分析和总结，并结合了部分代码实现。

前言

决策树（Decision Tree）是一种基本的机器学习模型，可用于分类与回归任务，当决策树用于分类时称为分类树，用于回归时称为回归树。

顾名思义，决策树是典型的树结构。结点有两种类型：内部结点和叶结点，其中内部结点表示一个特征或属性，叶结点表示一个类别或预测值。叶结点对应于决策结果，其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。在下图中，圆和方框分别表示内部结点和叶结点。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

本节主要说明分类决策树的相关内容
分类树是一种描述对实例进行分类的树形结构。在使用分类树进行分类时，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点。这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个，我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。

决策树学习用损失函数表示这一目标，其损失函数通常是正则化的极大似然函数，决策树学习的策略是以损失函数为目标函数的最小化。当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优的。

分类决策树学习基本流程：

从上面的算法流程中可以看到，建树的流程在于递归地选取最优划分属性/特征以及满足递归结束条件后结束训练，递归结束条件包括：

1. 所有样本属于同一类别
1. 当前的特征/属性集为空，或所有样本在属性集上取值相同，无法划分
1. 当前节点包含的样本集为空，无需划分，直接把当前节点的父节点作为叶节点即可。

在第二种情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别。在第三种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。这两种情形的处理实质不同：第二种情况是在利用当前结点的后验分布，而第三种情况则是把父结点的样本分布作为当前结点的先验分布。

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

所以，总的来说，决策树学习包含三个关键问题：特征选择，树生成，树的剪枝。
下面介绍经典的三类分类决策树算法，他们主要的区别在于特征选择方法的不同。

ID3 Tree

ID3 Tree使用信息增益来进行特征选择，信息增益源于信息论，在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为: $P(X=x_i)=p_i,i=1,2...,n$ ，对于随机变量X的熵为：
$H(X)=\sum_i^np_ilog(p_i)$
熵依赖于变量的分布情况，分布越均匀，熵越大，不确定性越大。与热力学中的熵增有同样的哲学意义。

条件熵H(Y∣X)表示在已知随机变量X的条件下随机变量Y的不确定性，条件熵（conditional entropy）H(Y∣X)：
$H(Y|X)=\sum_i^np_iH(Y|X=x_i)$
当熵和条件熵中的概率由数据估计（如极大似然估计）得到时，所对应的条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy):

**信息增益(Information Gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度,整个建树的过程抽象为降低类别分布信息不确定性的过程，与我们追求的实际预测任务是相一致的。具体定义为：
$G(D,a^*)=H(D)-H(D|a^*)$ , $a^*$ 为某一特征，在信息论中，熵与条件熵的差值也被称为互信息。

信息增益，表示由特征a∗ 划分数据使得对D的分类的不确定性减少的程度。显然，对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。具体的计算方式如下：

其中为数据类别。
那么ID3算法的具体流程如下

增加了信息增益阈值,当最优的特征分裂信息增益小于阈值时，也停止递归。

简单的实现如下：
数据如下：

day,outlook,temp,humidity,wind,play
D1,Sunny,Hot,High,Weak,No
D2,Sunny,Hot,High,Strong,No
D3,Overcast,Hot,High,Weak,Yes
D4,Rain,Mild,High,Weak,Yes
D5,Rain,Cool,Normal,Weak,Yes
D6,Rain,Cool,Normal,Strong,No
D7,Overcast,Cool,Normal,Strong,Yes
D8,Sunny,Mild,High,Weak,No
D9,Sunny,Cool,Normal,Weak,Yes
D10,Rain,Mild,Normal,Weak,Yes
D11,Sunny,Mild,Normal,Strong,Yes
D12,Overcast,Mild,High,Strong,Yes
D13,Overcast,Hot,Normal,Weak,Yes
D14,Rain,Mild,High,Strong,No

import numpy as np


def get_shannon_entropy(labels: np.ndarray) -> float:
    """
    计算香农熵
    即H(X)=−∑(i=1,n)pi * log2pi
    :param labels: shape = (n, )，n个标签
    :return: float香农熵值
    """
    num_labels = len(labels)
    labels_dic = {}     # 考虑到labels不一定是数字，我们用字典来装
    shannon_entropy = 0
    for label in labels:        
        if label not in labels_dic.keys():
            labels_dic[label] = 0
        labels_dic[label] += 1

    for i in labels_dic.keys():
        prob = labels_dic[i] / num_labels
        shannon_entropy += - prob * np.log2(prob)

    return shannon_entropy


def get_conditional_entropy(datas: np.ndarray, labels: np.ndarray) -> float:
    """
    条件熵
    即H(Y|X)=∑(i=1,n)piH(Y|X=xi)    
   
    """
    num_data = len(datas)
    conditional_entropy = 0
    num_class = {}    
    # 特征的不同取值下样本的数量
    for class_val in datas:    
        if class_val not in num_class.keys():
            num_class[class_val] = 0
        num_class[class_val] += 1
  
  # 特征的不同取值下条件熵的计算
    for i in num_class.keys():
        prob = num_class[i] / num_data
        index = np.argwhere(datas == i).squeeze()  
        # print(index.shape)
        if index.shape != ():          
            i_labels = labels[index]   
        else:
            i_labels = list([])               
            i_labels.append(labels[index])
        conditional_entropy += prob * get_shannon_entropy(i_labels)
    return conditional_entropy

    """
    计算信息增益，并找出最佳的信息增益值，作为当前最佳的划分依据
    即g(D,X)=H(D)−H(D|X)   
    best_gain = max(g(D,X))
    :param datas: shape(n, m) n条数据，m种特征
    :param labels: shape = (n, )，n个标签
    :return:返回最佳特征和对应的gain值
    """

def get_best_gain(datas: np.ndarray, labels: np.ndarray) -> (float, float):

    best_gain = 0
    best_feature = -1
    (num_data, num_feature) = datas.shape
    for feature in range(num_feature):
        current_data = datas[:, feature]
        gain = get_shannon_entropy(labels) - get_conditional_entropy(current_data, labels)
        if gain > best_gain:
            best_gain = gain
            best_feature = feature
    return best_feature, best_gain


def create_tree(datas_header: list, datas: np.ndarray, labels: np.ndarray) -> dict:
    """
    get_best_gain()是给一组datas,labels计算一次最佳划分特征
    要构建一棵决策树，那必须要在划分完剩下的数据集继续划分(递归过程)，直到以下情况出现：
    1.剩下全部结果都是相同的，那么直接作为结果。
   
    2.遍历完了所有特征，但是还是无法得到唯一标签，则少数服从多数。

    """
    # 结束条件1
    if list(labels).count(labels[0]) == len(labels):
        return labels[0]
    # 结束条件2
    if len(datas) == 0 and len(set(labels)) > 1:
        result_num = {}
        for result in labels:
            if result not in result_num.keys():
                result_num[result] = 0
            result_num[result] += 1
        more = -1
        decide = ''
        for result, num in result_num.items():
            if num > more:
                more = num
                decide = result
        return decide

    cur_best_feature_num, _ = get_best_gain(datas, labels)
    cur_best_feature_name = datas_header[cur_best_feature_num]


    class_val = set([data[cur_best_feature_num] for data in datas])
    trees = {cur_best_feature_name: {}}
    for val in class_val:   # 逐一找出每个特征值的数据    
        new_datas = [datas[i] for i in range(len(datas)) if datas[i, cur_best_feature_num] == val]    # 用列表生成式，读作:遍历datas每行，找到每行的'是否帅'特征下值为'帅'的行，返回该行
        new_labels = [labels[i] for i in range(len(datas)) if datas[i, cur_best_feature_num] == val]

        new_datas = np.delete(new_datas, cur_best_feature_num, axis=1)     # 删除最佳列，准备进入下一个划分依据
        new_datas_header = np.delete(datas_header, cur_best_feature_num)
        # 递归:去掉该行该列再丢进
        trees[cur_best_feature_name][val] = create_tree(list(new_datas_header), new_datas, np.array(new_labels))
    return trees


def predict_result(trees_model: dict, input_data: np, datas_header: list) -> str:
    """
    1.找字典中的第一个划分特征      
    2.在datas_header中找到高是第几个特征      
    3.在input_data中找到这个特征对应的值        
    4.找到字典中的特征的值，如果为叶节点，则直接返回结果，如果是字典，则进行下一个节点预测（递归）
    :param trees_model:
    :param input_data:
    :param datas_header:
    :return:
    """
    cur_judge = list(trees_model.keys())[0]      
    num_feature = datas_header.index(cur_judge)      
    cur_val = input_data[num_feature]       
    cur_tree = trees_model[cur_judge]
    # print(type(cur_tree[cur_val]))
    if type(cur_tree[cur_val]) == np.str_:
        return cur_tree[cur_val]
    return predict_result(cur_tree[cur_val], input_data, datas_header)


# 保存和读取函数
def store_tree(input_tree, filename):
    import pickle
    with open(filename, 'wb') as f:
        pickle.dump(input_tree, f)
        f.close()


def restore_tree(filename):
    import pickle
    with open(filename, 'rb') as f:
        return pickle.load(f)

决策树的可视化结果代码如下：

import matplotlib.pyplot as plt
import matplotlib
matplotlib.rcParams['font.sans-serif']=[u'SimHei']
# font = {'family': '宋体',
#        'weight': 'bold',
#        'size': 12}
 
# plt.rc("font", **font)

decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")

def getNumLeafs(myTree):
    numLeafs = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in list(secondDict.keys()):
        if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes
            numLeafs += getNumLeafs(secondDict[key])
        else:   numLeafs +=1
    return numLeafs

def getTreeDepth(myTree):
    maxDepth = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in list(secondDict.keys()):
        if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:   thisDepth = 1
        if thisDepth > maxDepth: maxDepth = thisDepth
    return maxDepth

def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',
             xytext=centerPt, textcoords='axes fraction',
             va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )
    
def plotMidText(cntrPt, parentPt, txtString):
    xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
    yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
    createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)

def plotTree(myTree, parentPt, nodeTxt):#if the first key tells you what feat was split on
    numLeafs = getNumLeafs(myTree)  #this determines the x width of this tree
    depth = getTreeDepth(myTree)
    firstStr = list(myTree.keys())[0]     #the text label for this node should be this
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
    plotMidText(cntrPt, parentPt, nodeTxt)
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    secondDict = myTree[firstStr]
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes   
            plotTree(secondDict[key],cntrPt,str(key))        #recursion
        else:   #it's a leaf node print the leaf node
            plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
            plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
    plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
#if you do get a dictonary you know it's a tree, and the first element will be another dict

def createPlot(inTree):
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)    #no ticks
    #createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses 
    plotTree.totalW = float(getNumLeafs(inTree))
    plotTree.totalD = float(getTreeDepth(inTree))
    plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;
    plotTree(inTree, (0.5,1.0), '')
    plt.show()

#def createPlot():
#    fig = plt.figure(1, facecolor='white')
#    fig.clf()
#    createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses 
#    plotNode('a decision node', (0.5, 0.1), (0.1, 0.5), decisionNode)
#    plotNode('a leaf node', (0.8, 0.1), (0.3, 0.8), leafNode)
#    plt.show()

# 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]
print(tree_model,type(tree_model))
print(list(tree_model.keys())[0])
createPlot(tree_model)

简易的可视化效果如下：

C4.5 Tree

信息增益有一个明显的问题：偏向取值较多的特征
原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。比如考虑极端特征，把序号信息作为特征，那么每个子划分中，仅有一个样本，条件熵为0，信息增益等于经验熵，这无疑是理论上最大的信息增益，然而使用这种序号信息进行特征划分并没有实际意义。

我们再以知乎用户@flower的回答进行分析：

特征A划分后的信息增益 Gain(D,A)=0.029
特征B划分后的信息增益 Gain(D,B)=0.029
特征C划分后的信息增益 Gain(D,C)=0.037

通过对比我们发现

A特征和B特征的信息增益是相同的，因为其实b1和b2等价，b3和b4等价，（所以b1,b2这种划分其实并不是有效特征，完全可以合并），也就是ID3算法并不是什么情况下都倾向于选择特征取值更多的特征

C特征的信息增益是高于A特征的，我们可以简单理解为C特征是对A特征的进一步细分，那么自然是消除了更多的不确定性，有更高的信息增益
所以说： ID3算法倾向于选择特征取值更多的特征，在特征有效性的前提下，特征取值更多，相当于对数据集的进一步细分，那么自然是消除了更多的数据的不确定性，获得了更大的信息增益，这其实是没有问题的

消除这种倾向性的主要原因是：

数据集的有限性：因为数据并不是无限的，所以理论上如果特征的取值过多，每个取值下的数据就越少，那么现有数据并不能反映该特征对结果的真正影响，也就是出现了所谓的过拟合，极端情况就是西瓜书上以序号为特征的例子了。所以具体的任务中，如果数据量相对于特征取值足够多，或者是对特征的有效性有足够的先验知识可以作为保证，那么就不会发生类似的过拟合情况，ID3算法的有效性会得到保障.

这就是信息增益率出现的背景了，信息增益率=惩罚因子*信息增益：
$G_R(D,A)=\frac{G(D,A)}{H_A(D)},H_A(D)=\sum_{i \in value(A)}\frac{|D_i|}{|D|}log\frac{|D_i|}{|D|}$
$H_A(D)$ 即将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵。

最后C4.5的算法流程如下

在进行最优特征划分时，单一使用信息增益比会偏向取值较少的特征，因此同时考虑信息增益和信息增益率两个因素，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

CART( Classification and Regression Tree)

除了信息增益与信息增益率外，还有利用基尼系数进行特征选择：
$Gini(D)=\sum_{k=1}^Kp_k(1-p_k)$
$Gini(D,A)=\sum_{v=1}^V\frac{|D_v|}{|D|}Gini(D_v)$
直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D) 越小，则数据集D的纯度越高。

其中，横坐标表示概率p，纵坐标表示损失。可以看出基尼指数和熵的一半的曲线很接近，都可以近似地代表分类误差率。

因此在CART算法中，选取基尼系数最小的特征作为最优划分特征进行建树。具体的流程如下：

算法输入训练集D，基尼系数的阈值，样本个数阈值。
输出的是决策树T。
算法从根节点开始，用训练集递归建立CART分类树。
　(1)、对于当前节点的数据集为D，如果样本个数小于阈值或没有特征，则返回决策子树，当前节点停止递归。
　(2)、计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。
　(3)、计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数
　(4)、在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2。
　(5)、对左右的子节点递归的调用1-4步，生成决策树。

所以CART树构建出的是二叉树结构，这是其在结构上明显区别ID3与C4.5的特点。

连续值与缺失值处理

[TBD]

树剪枝

[TBD]

决策树的优缺点

优点：

简单直观，生成的决策树很直观。
基本不需要预处理，不需要提前归一化和处理缺失值。
使用决策树预测的代价是O(log2m)。m为样本数。
既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
可以处理多维度输出的分类问题。
相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以很好解释。
可以交叉验证的剪枝来选择模型，从而提高泛化能力。
对于异常点的容错能力好，健壮性高。
缺点：
决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
决策树会因为样本发生一点的改动，导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
寻找最优的决策树是一个NP难题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习的方法来改善。
有些比较复杂的关系，决策树很难学习，比如异或。这种关系可以换神经网络分类方法来解决。
如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

上述三种经典决策树算法的对比如下图：

(1)无论ID3，C4.5，CART都是选择一个最优的特征做分类决策，但大多数，分类决策不是由某一个特征决定，而是一组特征。这样得到的决策树更加准确，这种决策树叫多变量决策树(multi-variate decision tree)。在选择最优特征的时，多变量决策树不是选择某一个最优特征，而是选择一个最优的特征线性组合做决策。代表算法OC1。
(2)样本一点点改动，树结构剧烈改变。这个通过集成学习里面的随机森林之类的方法解决。

参考资料

[1] https://zhuanlan.zhihu.com/p/101721467
[2] https://blog.csdn.net/hy592070616/article/details/81628956?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1
[3] 周志华. 《机器学习》
[4] https://www.zhihu.com/question/22928442/answer/786804946
[5] https://www.cnblogs.com/keye/p/10564914.html

机器学习基础-决策树理论-分类决策树

前言

ID3 Tree

C4.5 Tree

CART( Classification and Regression Tree)

连续值与缺失值处理

树剪枝

决策树的优缺点

参考资料

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读