决策树(Decision Tree)

简介

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。

Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

分类树（决策树）是一种十分常用的分类方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

决策树既可以用作分类，也可以用作回归。本文所写着重为分类

一、决策树算法的基本流程

决策树（Decision Tree）是⼀种实现分治策略的层次数据结构。它是⼀种有效的⾮参数学习⽅法，并可以⽤于分类和回归。我们主要讨论分类的决策树。
分类决策树模型表示⼀种基于特征对实例进⾏分类的树形结构（包括⼆叉树和多叉树）。
决策树由结点（node）和有向边（directed edge）组成，树中包含三种结点：

• 根结点（root node）：包含样本全集。没有⼊边，但有零条或多条出边；
• 内部结点（internal node）：对应于属性测试条件，恰有⼀条⼊边，和两条或多条出边；
• 叶结点（leaf node）或终结点（terminal node）：对应于决策结果，恰有⼀条⼊边，但没有出边。
  

从根结点到每个叶结点的路径对应了⼀个判定测试序列，其基本流程遵循简单且直观的 “分⽽治之” 策略。由此，局部区域通过少数⼏步递归分裂确定，每个决策节点实现⼀个具有离散输出的属性测试函数，标记分⽀。

决策树可以表示为给定决策节点下类的条件概率分布，这⼀条件概率分布定义在特征空间的⼀个划分上。每个将空间划分成较⼩区域，在从根结点沿⼀条路径向下时，这些较⼩的区域被进⼀步划分，并在每个区域定义⼀个类的概率分布就构成了⼀个条件概率分布。

假设$X$X是表示特征的随机变量，$Y$Y是表示类的随机变量，则条件概率分布可表示为$P(Y|X)$P(Y∣X)。$X$X取值于给定划分条件下的区域的集合，$Y$Y取值于类的集合。各叶结点（区域）上的条件概率往往会偏向某⼀个类，即属于某⼀类的概率较⼤。决策树在分类时会将该结点的实例强⾏分到条件概率⼤的那⼀类去。
上面左图表示了特征空间的⼀个划分，假定现在只有$w_{10}$w10​和$w_{20}$w20​两个决策节点，特征空间被决策节点沿轴划分，并且相继划分相互正交。

每个⼩矩形表示⼀个区域，特征空间划分上的区域构成了⼀个集合，$X$X取值为区域的集合。在这⾥假设只有两类，即$Y$Y的取值为 "$\Box$□“ 和 “$\bigodot$⨀“ 。当某个区域$c$c的条件概率分布满⾜$P(Y=\bigodot|X=c)>0.5$P(Y=⨀∣X=c)>0.5时，则认为这个区域属于该类，即落在这个区域的实例都将被视为该类。

右图为对应于条件概率分布的决策树。

如果输⼊维$x_N$xN​是离散的，取$n$n个可能的值之⼀，则该决策节点检查$x_N$xN​的值，并取相应分⽀，实现⼀个$n$n路划分。决策节点具有离散分⽀，数值输⼊应当离散化。如果$x_N$xN​是连续型数值，则测试⽐较：
$f_m(Y):x_N \geqq w_m$fm​(Y):xN​≧wm​

其中$w_m$wm​是适当选择的阈值。该决策节点将输⼊空间⼀分为⼆：$L_m=\{Y|x_N\geqq w_m\}$Lm​={Y∣xN​≧wm​} 和$R_m=\{Y|x_N < w_m\}$Rm​={Y∣xN​<wm​}，称作⼀个⼆元划分（binary split）。从根结点到叶结点的路径上的相继决策节点使⽤其他属性进⼀步把它们⼀分为⼆，产⽣相互正交的划分。此时，叶结点对应输⼊空间中的超矩形。

从图中可以看出，第⼀次划分后，$\{Y|x_1 \ge w_{10}\}${Y∣x1​≥w10​} 已经是纯的，所以不需要再划分。

二、决策树的特征选择

决策树学习的关键在如何选择最优划分属性。⼀般⽽⾔，随着划分过程不断进⾏，我们希望决策树的分⽀结点所包含的样本尽可能属于同⼀类别， 即结点的 “纯度” （purity）越来越⾼。在分类树中，划分的优劣⽤不纯度度量（impurity-measure）定量分析。

假设$p(i|t)$p(i∣t)表示给定节点$t$t中属于类$i$i的记录所占的比例，在二分类问题中，任意结点的类分布都可以记作$(p_0,p_1)$(p0​,p1​)，其中$p_1=1-p_0$p1​=1−p0​。

那么对最优的划分度量常见的有3种：

1. 信息熵（香农熵）
   $Entropy(t)=-\sum^{c-1}_{i=0}{p(i|t)log_2p(i|t)}$Entropy(t)=−i=0∑c−1​p(i∣t)log2​p(i∣t)
2. 基尼系数
   $Gini(t)=1-\sum^{c-1}_{i=0}{[p(i|t)]^2}$Gini(t)=1−i=0∑c−1​[p(i∣t)]2
3. 分类误差
   $Classification \ error(t)=1-\max_i[p(i|t)]$Classification error(t)=1−imax​[p(i∣t)]
   注：其中$c$c是指类的个数，并且在计算信息熵的时候，$0log_20=0$0log2​0=0。

下面给出二分类问题的三个不纯性度量方法的计算实例：

结点$N_1$N1​	计数
类=0	0
类=1	6

$Entropy=-(0/6)log_2(0/6)-(6/6)log_2(6/6)=0$Entropy=−(0/6)log2​(0/6)−(6/6)log2​(6/6)=0

$Gini=1-(0/6)^2-(6/6)^2=0$Gini=1−(0/6)2−(6/6)2=0

$Classification \ error=1-\max_i[0/6,6/6]=0$Classification error=1−maxi​[0/6,6/6]=0

结点$N_1$N1​	计数
类=0	1
类=1	5

$Entropy=-(1/6)log_2(1/6)-(5/6)log_2(5/6)=0.650$Entropy=−(1/6)log2​(1/6)−(5/6)log2​(5/6)=0.650

$Gini=1-(1/6)^2-(5/6)^2=0.278$Gini=1−(1/6)2−(5/6)2=0.278

$Classification \ error=1-\max_i[1/6,5/6]=0.167$Classification error=1−maxi​[1/6,5/6]=0.167

结点$N_1$N1​	计数
类=0	3
类=1	3

$Entropy=-(3/6)log_2(3/6)-(3/6)log_2(3/6)=1$Entropy=−(3/6)log2​(3/6)−(3/6)log2​(3/6)=1

$Gini=1-(3/6)^2-(3/6)^2=0.5$Gini=1−(3/6)2−(3/6)2=0.5

$Classification \ error=1-\max_i[3/6,3/6]=0.5$Classification error=1−maxi​[3/6,3/6]=0.5

下面给出二分类问题下不纯度度量的值域范围：

　　　　　　　　　　　　　　上图来自于数据挖掘导论（完整版）——范明、范宏建
　　　　　　　　　　　　　　
为了确定测试条件的效果，我们需要比较父结点（划分前）的不纯度和子女结点（划分后）的不纯成都，他们的差越大，测试条件的效果就越好。增益$\Delta$Δ是一种可以用来确定划分效果的标准：
$\Delta=I(parent)-\sum^k_{j=1}{\frac{N(v_j)}{N}I(V_j)}$Δ=I(parent)−j=1∑k​NN(vj​)​I(Vj​)
其中$I(.)$I(.)是给定节点的不纯性度量，$N$N是父节点上的记录总数，$k$k是属性值的个数，$N(v_j)$N(vj​)是与子女结点$v_j$vj​相关联的记录个数。决策树归纳算法通常选择最大化增益$\Delta$Δ的测试条件，因为对所有的测试条件来说$I(parent)$I(parent)是一个不变的值，所以最大化增益等价于最小化子女结点的不纯性度量的加权平均值。最后当选择熵(entropy)作为度量时，熵的差就是所谓的信息增益$（information \ gain）\Delta_{info}$（information gain）Δinfo​。

1.对于离散属性的划分

直接使用上述的信息增益来对每一个离散属性来进行分类，找出信息增益最大的那个属性，对其进行结点的划分。

2.对于连续属性的划分

是对于连续值按照从小到大进行排列，并且按照每两个相邻属性值的均值划分，将所有的属性划分为二分类问题，并从中找到信息增益最大的那个划分点，并在这个点上进行划分。

上述介绍的信息增益是$ID3$ID3所使用的方法，而在此基础上修改的$C4.5$C4.5算法运用的特征选择为增益率$(gain \ ration)$(gain ration)的划分标准来评估划分，增益率的定义如下：
$Gain \ ration=\frac{\Delta_{info}}{Split \ Info}$Gain ration=Split InfoΔinfo​​
其中，划分信息$Split \ Info=-\sum^{k}_{i=0}{p(v_i)log_2p(v_i)}$Split Info=−∑i=0k​p(vi​)log2​p(vi​)，而$k$k是划分的总数。
而$Cart$Cart树所采用的划分指标则是使用的$Gini$Gini系数，并且Cart树一定是二叉树。

三、决策树的算法手写代码实现（Python）

注：该手写代码基于ID3算法实现。
所使用的数据为：

No.	no surfacing	flippers	fish
0	1	1	yes
1	1	1	yes
2	1	0	no
3	0	1	no
4	0	1	no

使用上面的这个数据进行训练，并且使用前三行的数据来测试。

import numpy as np
import pandas as pd

def calEnt(dataSet):
    """
    函数功能:计算⾹农熵
    参数说明:
        dataSet:原始数据集
    返回:
        ent:⾹农熵的值
    """
    n = dataSet.shape[0] # 数据集总⾏数
    iset = dataSet.iloc[:,-1].value_counts() # 标签的所有类别
    p = iset/n # 每⼀类标签所占⽐
    ent = (-p*np.log2(p)).sum() # 计算信息熵
    return ent

# 创建数据集
def createDataSet():
    row_data = {'no surfacing':[1,1,1,0,0],
    'flippers':[1,1,0,1,1],
    'fish':['yes','yes','no','no','no']}
    dataSet = pd.DataFrame(row_data)
    return dataSet

# 选择最优的列进⾏切分
def bestSplit(dataSet):
    """
    函数功能：根据信息增益选择出最佳数据集切分的列
    参数说明：
        dataSet：原始数据集
    返回：
        axis：数据集最佳切分列的索引
    """
    baseEnt = calEnt(dataSet) # 计算原始熵
    bestGain = 0 # 初始化信息增益
    axis = -1 # 初始化最佳切分列，标签列
    for i in range(dataSet.shape[1]-1): # 对特征的每⼀列进⾏循环
        levels= dataSet.iloc[:,i].value_counts().index # 提取出当前列的所有取值
        ents = 0 # 初始化⼦节点的信息熵
        for j in levels: # 对当前列的每⼀个取值进⾏循环
            childSet = dataSet[dataSet.iloc[:,i]==j] # 某⼀个⼦节点的dataframe
            ent = calEnt(childSet) # 计算某⼀个⼦节点的信息熵
            ents += (childSet.shape[0]/dataSet.shape[0])*ent # 计算当前列的信息熵
        #print(f'第{i}列的信息熵为{ents}')
        infoGain = baseEnt-ents # 计算当前列的信息增益
        #print(f'第{i}列的信息增益为{infoGain}')
        if (infoGain > bestGain):
            bestGain = infoGain # 选择最⼤信息增益
            axis = i # 最⼤信息增益所在列的索引
    return axis

def mySplit(dataSet,axis,value):
    """
    函数功能：按照给定的列划分数据集
    参数说明：
        dataSet：原始数据集
        axis：指定的列索引
        value：指定的属性值
    返回：
        redataSet：按照指定列索引和属性值切分后的数据集
    """
    col = dataSet.columns[axis]
    redataSet = dataSet.loc[dataSet[col]==value,:].drop(col,axis=1)    #丢弃掉标题为col 的列
    return redataSet

def createTree(dataSet):
    """
    函数功能：基于最⼤信息增益切分数据集，递归构建决策树
    参数说明：
        dataSet：原始数据集(最有⼀列是标签)
    返回：
        myTree：字典形式的树
    """    
    featlist = list(dataSet.columns) # 提取出数据集所有的列
    classlist = dataSet.iloc[:,-1].value_counts() # 获取最后⼀列类标签
    # 判断最多标签数目是否等于数据集⾏数，或者数据集是否只有⼀列
    if classlist[0]==dataSet.shape[0] or dataSet.shape[1] == 1:
        return classlist.index[0] # 如果是，返回类标签
    axis = bestSplit(dataSet) # 确定出当前最佳切分列的索引
    bestfeat = featlist[axis] # 获取该索引对应的特征
    myTree = {bestfeat:{}} # 采用字典嵌套的⽅式存储树信息
    del featlist[axis] # 删除当前特征
    valuelist = set(dataSet.iloc[:,axis]) # 提取最佳切分列所有属性值
    for value in valuelist: # 对每⼀个属性值递归建树
        myTree[bestfeat][value] = createTree(mySplit(dataSet,axis,value))
    return myTree

def classify(inputTree,labels,testVec):
    """
    函数功能：对⼀个测试实例进⾏分类
    参数说明：
        inputTree：已经⽣成的决策树
        labels：存储选择的最优特征标签
        testVec：测试数据列表，顺序对应原数据集
    返回：
        classLabel：分类结果
    """
    firstStr = next(iter(inputTree)) # 获取决策树第⼀个节点  iter()函数获取这些可迭代对象的迭代器
    secondDict = inputTree[firstStr] # 下⼀个字典
    featIndex = labels.index(firstStr) # 第⼀个节点所在列的索引
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]) == dict :
                classLabel = classify(secondDict[key], labels, testVec)
            else:
                classLabel = secondDict[key]
    return classLabel

def acc_classify(train,test):
    """
    函数功能：对测试集进⾏预测，并返回预测后的结果
    参数说明：
        train：训练集
        test：测试集
    返回：
        test：预测分类后的测试集
    """
    inputTree = createTree(train) #根据测试集⽣成⼀棵树
    labels = list(train.columns) #数据集所有的列名称
    result = []
    for i in range(test.shape[0]): #对测试集中每⼀条数据进⾏循环
        testVec = test.iloc[i,:-1] #测试集中的⼀个实例
        classLabel = classify(inputTree,labels,testVec) #预测该实例的分类
        result.append(classLabel) #将分类结果追加到result列表中
    test['predict']=result #将预测结果追加到测试集最后⼀列
    acc = (test.iloc[:,-1]==test.iloc[:,-2]).mean() #计算准确率
    print(f'模型预测准确率为{acc}')
    return test


if __name__=='__main__':
    myTree = createTree(dataSet)
    train = createDataSet()
    test = dataSet.iloc[:3,:]
    test = acc_classify(train,test)
    print(test)

输出结果为

 模型预测准确率为1.0
    no surfacing  flippers fish predict
 0             1         1  yes     yes
 1             1         1  yes     yes
 2             1         0   no      no

四、决策树在SKlearn中的调用

Decision Trees在SKlearn中——https://scikit-learn.org/stable/modules/tree.html

class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, splitter=’best’, max_depth=None,
min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None,
random_state=None,max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None,
class_weight=None, presort=False)

决策树（分类树）中的重要参数：

• criterion : 分类标准。默认为’gini‘
  可能输⼊的值有：
  ‘gini’：使用基尼系数来作为分类标准，
  ‘entropy’：使用信息熵来作为分类标准

• splitter : 结点的分割策略。默认为‘best’
  可能输⼊的值有：
  ‘random’：随机策略划分
  ‘best’：最优分类标准划分

• max_depth : 最大树深，默认贪心算法指导无法分割。

• min_samples_split : 最小样本结点，小于该最小样本结点则无法划分。默认为2。
  如果该参数为整数，直接把参数作为最小标准。
  如果该参数为浮点数，那么就把(min_samples_split * n_samples)作为最小标准

• min_samples_leaf : 最小叶子结点，小于该叶子结点，则该次划分无效，默认为1。
  如果该参数为整数，直接把参数作为最小标准。
  如果该参数为浮点数，那么（min_samples_leaf * n_samples）是每个结点的样本的最小数目。

• min_weight_fraction_leaf : 叶节点所需的（所有输入样本的）权重总和的最小加权分数。未提供样品重量时，样品重量相等。

• max_features : 在寻找最佳分割时要考虑的特征数，默认为None
  可能输⼊的值：
  若为整数’int’：则在每次拆分时考虑“max_features”。
  若为浮点数’float’：那么“max_features”是一个分数，并且每次拆分时都会考虑“int(max_features * n_features)”。
  若为’auto’：那么“max_features=sqrt(n_features)”。
  若为’sqrt’：则“max_features=sqrt(n_features)”。
  若为’log2’：则“max_features=log2(n_features)”。
  如果None：max_features=n_features”。

• max_leaf_nodes : 最大叶子结点数。默认为None
  可能输⼊的值：
  int or None，具体数值或者没有限制。

• min_impurity_decrease : 最小增益划分。默认为0.0

• min_impurity_split : 最低不纯度划分。默认为None

• class_weight : 分类权重，面对样本不均衡时使用。默认为None。可选‘balanced’，自动按照权重的反比输入数据。

下面举例用红酒数据集来展示决策树在SKlearn中的具体调用：
读取各个模块

from sklearn import tree                          #  导入决策树的模块
from sklearn.datasets import load_wine            #  导入红酒数据模块
from sklearn.model_selection import train_test_split  #导入划分训练集和数据集的模块
import matplotlib.pyplot as plt
%matplotlib inline

读取数据、划分训练集等

wine = load_wine()# 这里不作展示，自行查看wine数据集内的内容

Xtrain, Xtest, Ytrain, Ytest =train_test_split(wine.data,wine.target,test_size=0.3) #划分训练集和测试集

feature_name = ['酒精','苹果酸',      # 定义中文名，为之后画树做准备，这里是与wine.feature_names对应的
                '灰','灰的碱性',
                '镁','总酚',
                '类⻩酮','⾮⻩烷类酚类',
                '花⻘素','颜⾊强度','⾊调',
                'od280/od315稀释葡萄酒','脯氨酸']

plt.rcParams['font.sans-serif']=['Simhei']  # 设置字体
plt.rcParams['axes.unicode_minus']=False          #字符显示

查看得分情况

score =[]
for i in range(500):
    clf = tree.DecisionTreeClassifier(criterion = 'entropy',splitter='best')
    clf = clf.fit(Xtrain,Ytrain)
    score.append(clf.score(Xtest,Ytest))
print(set(score))

结果为：

{0.9444444444444444, 0.9814814814814815, 0.9259259259259259, 0.9629629629629629, 1.0, 0.9074074074074074}

将就上次最后一次的训练来画一棵决策树（调参过程就不细说，只是演示一次调用过程）

import graphviz
dot_data = tree.export_graphviz(clf,
                                out_file = None,
                                feature_names= feature_name ,
                                class_names=["琴酒","雪莉","贝尔摩德"] ,
                                filled=True,rounded=True)

graph = graphviz.Source(dot_data)
graph

重要接口：clf.predict(Xtest)
表示对于测试集类划分的反馈
结果如下：

array([1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 2, 0, 0, 1, 0, 1, 0, 1, 2, 2, 0, 0,
       1, 1, 1, 2, 2, 2, 0, 2, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 2, 0, 0,
       2, 1, 0, 1, 2, 0, 0, 1, 1, 0])

参考：
数据挖掘导论（完整版）——范明、范宏建