4.1 决策树算法简介

学习目标

• 知道什么是决策树
• 能够通过sklearn实现决策树分类，进一步认识决策树

---

1 概念

决策树思想的来源非常朴素，程序设计中的条件分支结构就是if-else结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法。

决策树：

怎么理解这句话？通过一个对话例子：

“闺女，我又给你找了个合适的对象，今天要不要见一面?”
“多大？ ” “26岁。”
“长得帅吗？ ” “还可以，不算太帅。”
“工资高么？ ” “略高于平均水平。”
“会写代码吗？ ” “人家是程序员，代码写得棒着呢！”
“好，那把他联系方式发来吧，我抽空见一面。”

上述图右侧部分，女儿最多通过四次判断，就可以得到答案，这时称我们的决策树的depth(深度)为3

概念：

• 是一种树形结构，本质是一颗由多个判断节点组成的树
• 其中每个内部节点表示一个属性上的判断，
• 每个分支代表一个判断结果的输出，
• 最后每个叶节点代表一种分类结果。

2 通过sklearn实现决策树分类并进一步认识决策树

• 基于鸢尾花数据绘制图像

  import numpy as np
  import matplotlib.pyplot as plt
  from sklearn.datasets import load_iris
  
  # 加载数据集
  iris = load_iris()
  
  # 获取特征值和目标值
  X = iris.data[:,2:]
  y = iris.target
  
  # 绘制图形展示效果,一共三种类别
  plt.scatter(X[y==0,0],X[y==0,1])
  plt.scatter(X[y==1,0],X[y==1,1])
  plt.scatter(X[y==2,0],X[y==2,1])
  plt.show()
  

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Cd7T2S8e-1631279255582)(./images/1.png)]

• 训练决策树模型

  from sklearn.tree import DecisionTreeClassifier
  
  # 实例化分类器
  tree = DecisionTreeClassifier(max_depth=2,criterion="gini")
  # 训练模型
  tree.fit(X,y)
  
  """
  DecisionTreeClassifier(ccp_alpha=0.0, class_weight=None, criterion='entropy',
                         max_depth=2, max_features=None, max_leaf_nodes=None,
                         min_impurity_decrease=0.0, min_impurity_split=None,
                         min_samples_leaf=1, min_samples_split=2,
                         min_weight_fraction_leaf=0.0, presort='deprecated',
                         random_state=None, splitter='best')
  """
  

• 依据模型绘制决策树的决策边界

  #找到模型的决策边界，并绘制图像(此方法所用到的api不需要掌握，能够调用就行)
  def plot_decision_boundary(model,axis):
      x0,x1 = np.meshgrid(
          np.linspace(axis[0],axis[1],int((axis[1]-axis[0])*100)).reshape(-1,1),
          np.linspace(axis[2],axis[3],int((axis[3]-axis[2])*100)).reshape(-1,1)
      )
      X_new = np.c_[x0.ravel(),x1.ravel()]
      y_predict = model.predict(X_new)
      zz = y_predict.reshape(x0.shape)
      
      from matplotlib.colors import ListedColormap
      custom_map = ListedColormap(["#EF9A9A","#FFF59D","#90CAF9"])
      
      plt.contourf(x0,x1,zz,linewidth=5,cmap=custom_map)
      
  plot_decision_boundary(tree,axis=[0.5,7.5,0,3])
  plt.scatter(X[y==0,0],X[y==0,1])
  plt.scatter(X[y==1,0],X[y==1,1])
  plt.scatter(X[y==2,0],X[y==2,1])
  plt.show()
  

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7VjDzAtG-1631279255584)(./images/13.png)]

  

通过上述分析可知：

• 决策树是非参数学习算法
• 决策树可以解决分类问题
• 决策树天然可以解决多分类问题
• 决策树可以解决回归问题：落在叶子节点(对应图中的A、B、C三点)的数据的平均值作为回归的结果
• 决策树可以应用于信用卡评级的案例中,生成相应的分类规则。

4.2 特征选择

学习目标

• 知道如何选择特征构建决策树
• 知道信息熵、信息增益、信息增益比

---

1 特征选择问题

特征选择在于选取对于训练数据具有分类能力的特征，这样可以提高决策树学习的效率。如果使用一个特征进行分类的结果与随机分类的结果没有很大差别，则该特征没有分类能力。扔掉这个特征对决策树学习的精度影响不大。特征选择就是决定用哪个特征来对数据集进行划分。

2 熵

• 定义

  • 熵在信息论中代表随机变量不确定度的度量。
  • 熵越大，数据的不确定性度越高
  • 熵越小，数据的不确定性越低

• 公式
  $$H=-\sum _{i=1}^k{p}_i\log (p_i)$$

  • 例子1：假如有三个类别，分别占比为：{1/3,1/3,1/3}，信息熵计算结果为：

    $$H=-\frac{1}{3}\log (\frac{1}{3})-\frac{1}{3}\log (\frac{1}{3})-\frac{1}{3}\log (\frac{1}{3})=1.0986$$

  • 例子2：假如有三个类别，分别占比为：{1/10,2/10,7/10}，信息熵计算结果为：

    $$H=-\frac{1}{10}\log (\frac{1}{10})-\frac{2}{10}\log (\frac{2}{10})-\frac{7}{10}\log (\frac{7}{10})=0.8018$$

    熵越大，表示整个系统不确定性越大，越随机，反之确定性越强。

  • 例子3：假如有三个类别，分别占比为：{1,0,0}，信息熵计算结果为：

    $$H=-1\log (1)=0$$

• 公式的转换

  当数据类别只有两类的情况下，公式可以做如下转换
  KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲\large H &= -\s…

  • 代码角度理解信息熵的概念

    import numpy as np
    import matplotlib.pyplot as plt
    
    def entropy(p):
        return -p*np.log(p)-(1-p)*np.log(1-p)
        
    x = np.linspace(0.01,0.99,200)
    plt.plot(x,entropy(x))
    plt.show()
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2C8AFhfb-1631279255586)(./images/6.png)]

    观察上图可以得出，当我们的系统每一个类别是等概率的时候(x轴值等于0.5)，系统的信息熵最高，当系统偏向于某一列，相当于系统有了一定程度的确定性，直到系统整体百分之百的都到某一类中，此时信息熵就达到了最低值，即为0。上述结论也可以拓展到多类别的情况。

3 信息增益

• 定义

  特征$$A$$对训练数据集D的信息增益$$g(D,A)$$，定义为集合$$D$$的经验熵$$H(D)$$与特征A给定条件下D的经验熵$$H(D|A)$$之差。即
  $$g(D,A)=H(D)-H(D|A)$$

• 根据信息增益选择特征方法是：对训练数据集D，计算其每个特征的信息增益，并比较它们的大小，并选择信息增益最大的特征进行划分。表示由于特征$$A$$而使得对数据D的分类不确定性减少的程度。

• 算法：

  设训练数据集为D，$$\mid D\mid$$表示其样本个数。设有$$K$$个类$$C_k$$，$$k=1,2,\cdots ,K$$，$$\mid C_k\mid$$为属于类$$C_k$$的样本个数，$$\sum _{k=1}^K=\mid D\mid$$。设特征A有$$n$$个不同取值 { a 1 , a 2 , ⋯   , a n } \{a_1, a_2, \cdots,a_n\} {a1​,a2​,⋯,an​}，根据特征A的取值将D划分为$$n$$个子集$$D_1,D_2,\cdots ,D_n$$，$$\mid D_i\mid$$为$$D_i$$样本个数，$$\sum _{i=1}^n\mid D_i\mid =\mid D\mid$$。子集中属于类$$C_k$$的样本集合为$$D_{ik}$$，即$$D_{ik}=D_i\bigcap C_k$$，$$\mid D_{ik}\mid$$为$$D_{ik}$$的样本个数。信息增益算法如下：

  • 输入：训练数据集D和特征A；
  • 输出：特征A对训练数据集D的信息增益$$g(D,A)$$
  • (1) 计算数据集D的经验熵$$H(D)$$
    • $$H(D)=-\sum _{k=1}^K\frac{\mid C_k\mid }{\mid D\mid }{\log }_2\frac{\mid C_k\mid }{\mid D\mid }$$
  • (2) 计算特征A对数据集D的经验条件熵$$H(D\mid A)$$
    • KaTeX parse error: Expected group after '_' at position 128: …\mid D\mid}\sum_̲\limits{k=1}^{K…
  • (3) 计算信息增益
    • $$g(D,A)=H(D)-H(D|A)$$

• 例子：

下面以常用的贷款申请样本数据表为样本集，通过数学计算来介绍信息增益计算过程。

ID	年龄(A1)	有工作(A2)	有房子(A3)	信贷情况(A4)	类别
1	青年	否	否	一般	拒绝
2	青年	否	否	好	拒绝
3	青年	是	否	好	同意
4	青年	是	是	一般	同意
5	青年	否	否	一般	拒绝
6	中年	否	否	一般	拒绝
7	中年	否	否	好	拒绝
8	中年	是	是	好	同意
9	中年	否	是	非常好	同意
10	中年	否	是	非常好	同意
11	老年	否	是	非常好	同意
12	老年	否	是	好	同意
13	老年	是	否	好	同意
14	老年	是	否	非常好	同意
15	老年	否	否	一般	拒绝

Step1 计算经验熵

• 类别一共是两个拒绝/同意，数量分别是6和9，根据熵定义可得：
  $$H(D)=-\frac{9}{15}{\log }_2\frac{9}{15}-\frac{6}{15}{\log }_2\frac{6}{15}=0.971$$

Step2 各特征的条件熵

• 将各特征分别记为 $$A_1,A_2,A_3,A_4$$ ，分别代表年龄、有无工作、有无房子和信贷情况，那么
  $$
  \begin{align}
  H(D\mid A_1)&=\frac{5}{15}(-\frac{2}{5}\log_2\frac{2}{5}-\frac{3}{5}\log_2\frac{3}{5})+\frac{5}{15}(-\frac{3}{5}\log_2\frac{3}{5}-\frac{2}{5}\log_2\frac{2}{5})+\frac{5}{15}(-\frac{4}{5}\log_2\frac{4}{5}-\frac{1}{5}\log_2\frac{1}{5})=0.888 \
  H(D\mid A_2)&= \frac{5}{15}(-\frac{5}{5}\log_2\frac{5}{5})+\frac{10}{15}(-\frac{4}{10}\log_2\frac{4}{10}-\frac{6}{10}\log_2\frac{6}{10})=0.647 \
  H(D\mid A_3) &= 0.551 \
  H(D\mid A_4) &= 0.608

  \end{align}
  $$

Step3 计算增益
$$\begin{gathered} g(D,A_1)=H(D)-H(D\mid A_1)=0.083 \\ g(D,A_2)=H(D)-H(D\mid A_2)=0.324 \\ g(D,A_3)=H(D)-H(D\mid A_3)=0.420 \\ g(D,A_4)=H(D)-H(D\mid A_4)=0.363 \end{gathered}$$
根据计算所得的信息增益，选取最大的$$A_3$$ 作为根节点的特征。它将训练集 $$D$$ 划分为两个子集$$D_1$$（取值为“是”）和$$D_2$$（取值为“否”）。由于$$D_1$$只有同一类的样本点，所以成为一个叶节点，节点标记为“是”。

ID	年龄(A1)	有工作(A2)	有房子(A3)	信贷情况(A4)	类别
4	青年	是	是	一般	同意
8	中年	是	是	好	同意
9	中年	否	是	非常好	同意
10	中年	否	是	非常好	同意
11	老年	否	是	非常好	同意
12	老年	否	是	好	同意

对于$$D_2$$需从特征$$A_1,A_2,A_4$$中选择新的特征。计算各个特征的信息增益

ID	年龄(A1)	有工作(A2)	有房子(A3)	信贷情况(A4)	类别
1	青年	否	否	一般	拒绝
2	青年	否	否	好	拒绝
3	青年	是	否	好	同意
5	青年	否	否	一般	拒绝
6	中年	否	否	一般	拒绝
7	中年	否	否	好	拒绝
13	老年	是	否	好	同意
14	老年	是	否	非常好	同意
15	老年	否	否	一般	拒绝

$$\begin{gathered} g(D_2,A_1)=0.918-0.668=0.251 \\ g(D_2,A_2)=0.918 \\ g(D_2,A_4)=0.474 \end{gathered}$$

选择信息增益最大的特征$$A_2$$作为节点的特征。由于$$A_2$$有两个可能取值，一个是“是”的子节点，有三个样本，且为同一类，所以是一个叶节点，类标记为“是”；另一个是“否”的子节点，包含6个样本，也属同一类，所以也是一个叶节点，类别标记为“否”。

最终构建的决策树如下：

4 信息增益比

以信息增益作为划分训练数据集的特征，存在倾向于选择取值较多的特征问题，使用信息增益比可以对这个问题进行矫正。这是特征选择的另一个准则。(了解)

• 定义：

  特征$$A$$对训练数据集$$D$$的信息增益比$$g_R(D,A)$$，为其信息增益$$g(D,A)$$与训练数据集$$D$$关于特征$$A$$的值的熵$$H_A(D)$$之比，即
  $$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$
  其中，$$H_A(D)=-\sum _{i=1}^n\frac{\mid D_i\mid }{\mid D\mid }{\log }_2\frac{\mid D_i\mid }{\mid D\mid }$$，$$n$$是特征$$A$$取值的个数。

  例如年龄(A1)列信息增益比计算:
  $$g_R(D,A1)=\frac{g(D,A)}{H_A(D)}=\frac{H(D)-H(D|A1)}{H_{A}1(D)}=\frac{0.083}{3\ast (-\frac{5}{15}{\log }_2\frac{5}{15})}$$

• 信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。惩罚参数：数据集D以特征A作为随机变量的熵的倒数。

4.3 决策树的生成

学习目标

• 知道ID3和C4.5决策树生成算法

---

1 ID3算法介绍

1.1 ID3算法

ID3算法的核心是在决策树的各个节点上应用信息增益准则进行特征选择，递归的构建决策树。具体方法是：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同哦取值建立子节点；再对子节点递归调用以上方法，构建决策树；直到所有特征的信息增益均很小或者没有特征可以选择为止。最后得到一个决策树。

2 C4.5算法介绍

​ C4.5算法与ID3算法相似，C4.5对ID3算法进行了改进，C4.5在生成决策树过程中，使用信息增益比来选择特征。

3 ID3和C4.5对比

• ID3算法缺点

  • ID3算法不能处理具有连续值的属性
  • ID3算法不能处理属性具有缺失值的样本
  • 算法会生成很深的树，容易产生过拟合现象
  • 算法一般会优先选择有较多属性值的特征，因为属性值多的特征会有相对较大的信息增益，但这里的属性并不一定是最优的

• C4.5算法的核心思想是ID3算法，对ID3算法进行了相应的改进。

  • C4.5使用的是信息增益比来选择特征，克服了ID3的不足。
  • 可以处理离散型描述属性，也可以处理连续数值型属性
  • 能处理不完整数据

• C4.5算法优缺点

  • 优点：分类规则利于理解，准确率高
  • 缺点
    • 在构造过程中，需要对数据集进行多次的顺序扫描和排序，导致算法的低效
    • C4.5只适合于能够驻留内存的数据集，当数据集非常大时，程序无法运行

• 无论是ID3还是C4.5最好在小数据集上使用，当特征取值很多时最好使用C4.5算法。

4.4 决策树剪枝

学习目标

• 知道决策时剪枝原因
• 知道决策时剪枝算法

1 什么是剪枝?

剪枝是指将一颗子树的子节点全部删掉，利用叶子节点替换子树(实质上是后剪枝技术)，也可以（假定当前对以root为根的子树进行剪枝）只保留根节点本身而删除所有的叶子，以下图为例：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-il4ktGet-1631279255588)(./images/wpsarP0jT.png)]

2 为什么要进行树的剪枝?

决策树是充分考虑了所有的数据点而生成的复杂树，有可能出现过拟合的情况，决策树越复杂，过拟合的程度会越高。

考虑极端的情况：如果我们令所有的叶子节点都只含有一个数据点，那么我们能够保证所有的训练数据都能准确分类，但是很有可能得到高的预测误差，原因是将训练数据中所有的噪声数据都”准确划分”了，强化了噪声数据的作用。

而剪枝修剪分裂前后分类误差相差不大的子树，能够降低决策树的复杂度，降低过拟合出现的概率。

关键步骤解释:

因为决策树的构建过程是一个递归的过层，所以必须确定停止条件，否则过程将不会停止，树会不停生长。通过我们前面的例子我们可以当一个节点下面的所有记录都属于同一类，或者当所有记录属性都具有相同的值时停止，但是这样往往会使得树的节点过多，导致过度拟合的问题。

过度拟合是指直接生成的完全决策树对训练样本的特征描述的“过于精确”，无法实现对新样本进行合理的分许，所以这种情况我们构建的树不是一颗最佳的决策树。

所以，为了避免过拟合，我们引入剪枝技术。

除了剪枝技术我们还有一种解决方法：当前结点中的记录数低于一个最小阈值就停止分裂，采用多数表决的方法决定叶节点的分类。

3 如何剪枝？

两种方案：先剪枝和后剪枝

• 先剪枝说白了就是提前结束决策树的增长，跟上述决策树停止生长的方法一样。
• 后剪枝是指在决策树生长完成之后再进行剪枝的过程。

接下来我们深入理解下这两种剪枝技术。

3.1 先剪枝（预剪枝）(max_depth,min_samples_split,min_samples_leaf)

先剪枝是对决策树停止标准的修改。

在ID3算法中，节点的分割一直到节点中的实例属于同一类别的时候才停止。对于包含较少实例的节点，很有可能被分割为单一实例的节点。为了避免这种情况，我们给出一个阈值，当一个节点分割导致的最大的不纯度下降小于a时，就把该节点看作是叶子结点。该方法选择的阈值对决策树的构建有很大的影响。

（1）当阈值a选择的过大的时候，节点的不纯度依然很高就停止了分裂。此时的树由于生长不足，导致决策树过小，分类的错误率过高。因此需要调整a参数的合理范围之内的值。

（2）当阈值a选择的过小的时候，比如a接近0，节点的分割过程近似于原始的分割过程。

由此可见，预剪枝方法虽然简单，但在实际应用中对a的选择存在很大的主观性。精确的给出a的值也是相当困难。

3.2 后剪枝(ccp_alpha)

后剪枝是从一个充分生长的树中，按照自低向上的方式修剪掉多余的分支，有两种方法：

（1）用新的叶子结点替换子树，该叶子结点的类标号由子树记录中的多数类决定。

（2）用子树中最常用的分支替代子树。

通常计算前后预期分类错误率，如果修剪导致预期分类错误率变大，则放弃修剪，保留相应的各个分支，否则就将相应的节点分支修剪删除。

通常采用后剪枝技术是最小的错误剪枝(MEP)技术，即在产生一系列的经过修剪后的决策树候选之后，利用一个独立的测试数据集，对这些经过修剪之后的决策树的分类准确性进行评价，保留下预期分类错误率最小的（修剪后）决策树。

除了最小错误剪枝技术外，还有悲观错误剪枝(MEP)和代价复杂度剪枝(CCP)

3.3 剪枝技术对比

预剪枝使得决策树的很多分支没有展开，这不仅仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能，甚至会导致泛化性能降低，但在其基础上进行的后续划分却有可能导致性能的显著提高。同时，预见值决策树也带来了欠拟合的风险。

后剪枝的决策树通常比预剪枝的决策树保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中所有非叶子节点进行逐一考察，因此在训练时间开销比未剪枝的决策树和预剪枝的决策树都要大得多。

4.5 决策树算法案例剖析

1 电商实例ID3算法实例详解

上述基于规则的建树，由于人工的规则有很大的主观性，引出基于模型的建树，引出信息熵和信息增益，接下来本案例通过基于信息增益的ID3算法继续实现案例。

表1-5：按照年龄分开数据集：

统计用户计数	年龄	收入	学生	信誉	是否购买
64	青	高	否	良	不买
64	青	高	否	优	不买
128	青	中	否	良	不买
64	青	低	是	良	买
64	青	中	是	优	买
128	中	高	否	良	买
64	中	低	是	优	买
32	中	中	否	优	买
32	中	高	是	良	买
60	老	中	否	良	买
64	老	低	是	良	买
64	老	低	是	优	不买
132	老	中	是	良	买
64	老	中	否	优	不买

1.1 ID3算法步骤演示

有了上面的基础之后，通过最上面的例子实现ID3算法的生成过程。

①计算对给定样本分类所需的信息熵:

类别标签S被分为两类：买or不买。其中：

S1（买）=640；

S2（不买）=384；

S=S1+S2=1024;

S1的概率p1=640/1024=0.625;

S2的概率p2=384/1024=0.375;

I(S1,S2)=I(640,384)=-p1log(p1) -p2log(p2)=0.9544

②计算每个特征的信息熵及信息增益

1. 计算“年龄”特征的信息熵：年龄分为三组：青年（0）、中年（1）、老年（2）

1.1 青年占总样本的概率

P(0)=384/1024=0.375

S1(买)=128

p1=128/384

S2(不买)=256

p2=256/384

I1(S1,S2)=I(128,256)=-p1log(p1) -p2log(p2)=0.9183

1.2 中年占总样本的概率

P(1)=256/1024=0.25

S1(买)=256

p1=256/256=1

S2(不买)=0

p2=0/384=0

I2(S1,S2)=I(256,0)=-p1log(p1) -p2log(p2)=0

1.3 老年占总样本的概率

P(2)=384/1024=0.375

S1(买)=257

p1=257/384

S2(不买)=127

p2=127/384

I3(S1,S2)=I(257,127)=-p1log(p1) -p2log(p2)=0.9157

则年龄的信息熵为：

​ E（年龄）= P(0)* I1(S1,S2)+ P(1)* I2(S1,S2)+ P(2)* I3(S1,S2)=0.375*0.9183+0.25*0+0375*0.9157 =0.6877

​ 则年龄的信息增益为：G（年龄）=0.9544-0.6877=0.2667

2. 计算“学生”特征的信息熵

E（学生）=0.7811 G（学生）=0.9544-0.7811=0.1733

3. 计算“收入”特征的熵

E（收入）=0.9361 G（收入）=0.9544-0.9361=0.0183

4. 计算“信誉”特征的熵

E（信誉）=0.9048 G（信誉）=0.9544-0.9048=0.0496

③从所有列的特征中选出信息增益最大的那个作为根节点或内部节点

根据上述信息增益的大小，选定年龄列G=0.2667来划分数据集。

④根据节点的不同取值将数据集拆分为若干子集，删除当前的特征列，在计算剩余列的特征信息熵。如果有信息增益，就重复第二步直至划分结束。

首次划分后，青年和老年内含有多个标签，所以可以继续划分，中年选项就剩下一个标签就称作为叶子结点。

⑤划分结束标志为：子集中只有一个类别标签，停止划分。

根据信息增益，选择出根节点，依次划分得到一颗决策树，大家可以对比下这颗决策树和之前的决策树的差别在哪里？

基于规则的决策树如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YpAoyvix-1631279255590)(./images/wpsDtplbe.png)]

2 基于模型的决策树

按照上述结果产生一个决策树如下图：

**（解释）**这张图明显是比我们根据规则手画的决策树优化了，根据年龄判断了直接就看是否为学生就可以达到分类目的。无需根据年龄à收入à学生-à是否购买来判断。

**（总结）**根据信息熵和信息增益得到的决策树和之前利用自己制定规则得到的决策树，有明显的不同，因此，利用信息熵和信息增益可以得到分类效果更优的决策树。

3 决策树算法处理连续值

连续值的处理：由于连续属性的可取值数目不在有限，因此，不能直接根据连续属性的取值对结点进行划分。此时，我们采用连续值离散化的技术，最简单的是采用二分法（将样本的属性取值从大到小排序，找一个划分点将样本集分成两个子集，大于划分点的集合是决策树的一个分支，小于划分点的是决策树的一个分支）对连续属性进行处理，这也是C4.5算法采用的策略。

4 决策树算法的特点

（1） 决策树的优点：

直观，便于理解，小规模数据集有效

执行效率高，执行只需要一次构建，可反复使用

（2）决策树的缺点：

处理连续变量不好，较难预测连续字段

类别较多时，错误增加的比较快

对于时间序列数据需要做很多的预处理

可规模性一般

实际分类的时候只能根据一个字段进行

5 构建决策树的三个步骤

通过上述总结分析，归纳总结构建决策树包括三个步骤:

**特征选择：**选取有较强分类能力的特征。

**决策树生成：**典型的算法有ID3和C4.5，它们生成决策树过程相似，ID3是采用信息增益作为特征选择度量，而C4.5采用信息增益比率。

决策树剪枝：剪枝原因是决策树生成算法生成的树对训练数据的预测很准确，但是对于未知数据分类很差，这就产生了过拟合的现象。

4.6 基尼指数和CART算法

学习目标

• 知道基尼指数计算
• 知道CART算法

---

1 基尼指数

• 定义

  分类问题中，假设有$$K$$个类，样本点属于第$$k$$类的概率为$$p_k$$，则概率分布的基尼指数定义为
  $$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$
  对于二分类问题，若样本点属于第一个类的概率为$$p$$， 则概率分布基尼指数为
  $$Gini(p)=2p(1-p)$$
  对于给定的样本集合$$D$$，其基尼指数为
  $$Gini(D)=1-\sum _{k=1}^K{\left(\frac{\mid C_k\mid }{\mid D\mid }\right)}^2$$
  这里$$C_k$$是$$D$$中属于第$$k$$类的样本子集，$$K$$为类的个数。

  如果样本集合$$D$$根据特征$$A$$是否取某一可能值$$\alpha$$被分割成$$D_1$$和$$D_2$$两部分，即
  D 1 = { ( x , y ) ∈ D ∣ A ( x ) = a } , D 2 = D − D 1 D_1= \left\{(x,y)\in D\mid A(x)=a \right\}, D_2=D-D_1 D1​={(x,y)∈D∣A(x)=a},D2​=D−D1​
  则在特征$$A$$的条件下，集合$$D$$的基尼指数定义为
  $$Gini(D,A)=\frac{\mid D_1\mid }{\mid D\mid }Gini(D_1)+\frac{\mid D_2\mid }{\mid D\mid }Gini(D_2)$$
  基尼指数$$Gini(D)$$表示集合$$D$$的不确定性，基尼指数$$Gini(D,A)$$表示经过$$A=a$$分割后的集合$$D$$的不确定性。基尼指数数值越大，样本集合的不确定性也就越大。

• 举例：

  • 例子1：假如有三个类别，分别占比为：{1/3,1/3,1/3}，基尼指数计算结果为：

    $$G=1-(1/3{)}^2-(1/3{)}^2-(1/3{)}^2=0.667$$

  • 例子2：假如有三个类别，分别占比为：{1/10,2/10,7/10}，基尼指数计算结果为：

    $$G=1-(1/10{)}^2-(2/10{)}^2-(7/10{)}^2=0.46$$

  • 例子3：假如有三个类别，分别占比为：{1,0,0}，基尼指数计算结果为：

    $$G=1-1^2=0$$

1.1分类决策树案例分析

数据集：

应用上述数据集，应用CART算法生成决策树。

分析：首先计算各特征的基尼指数，选择最优特征以及其最优切分点。我们以A1,A2,A3,A4表示年龄、有工作、有自己的房子和信贷4个特征，并以1，2，3表示年龄的值为青年、中年、老年，以1、2表示有工作和有自己的房子的值为是和否，以1、2、3表示信贷情况的值为非常好、好和一般。

求特征A1的基尼指数：

优于Gini(D,A1=1)和Gini(D,A1=3)相等，且最小，所以A1=1和A1=3都可以选作最优切分点。

求特征A2和A3的基尼指数：

由于A2和A3只有一个切分点，所以他们就是最优切分点。

求解特征4的基尼指数：

Gini(D,A4=3)最小，所以A4=3为A4的最优切分点。

在A1，A2，A3，A4几个特征中，Gini(D,A3=1)=0.27最小，所以选择A3为最优特征，A3=1为其最优切分点。于是根节点生成两个子节点，一个是叶节点，对另一个结点继续使用以上方法在A1，A2，A3中选择最优特征及其最优切分点，结果是A2=1，依次计算得知，所有结点都是叶节点。

该例子按照CART算法和ID3算法生成的决策树完全一致的。下图我们只拿A3和A2作为最优划分来切分数据集。

2 CART算法

2.1 CART树简介

前面讲了ID3算法和C4.5算法用于解决分类问题。我们可以看到，为了进行特征选择，引入了熵，但这里涉及到了大量的对数运算。CART分类树使用基尼系数来代替信息增益，基尼系数越小，模型的不纯度越低，特征越好。

Classification and Regression Tree，分类和回归树。**CART算法既可以用来分类，也可以用来做回归。**当CART是分类树时，采用$$Gini$$系数作为节点分裂的依据，并且输出是分类值；当CART是回归树时，采用样本的最小方差作为节点分裂的依据，输出是数值。另外，CART树是二叉树。

2.2 CART算法

CART树生成

输入：数据集$$D$$ ，特征$$A$$，样本个数阈值、基尼系数阈值

输出：$$CART$$决策树$$T$$

（1）对于当前节点的数据集为$$D$$，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归；

（2）计算样本集$$D$$的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归；

（3）计算当前节点现有的各个特征的各个特征值对数据集$$D$$的基尼系数；

（4）在计算出来的各个特征的各个特征值对数据集$$D$$的基尼系数中，选择基尼系数最小的特征$$A$$和对应的特征值$$\alpha$$。根据这个最优特征和最优特征值，把数据集划分成两部分$$D_1$$和，$$D_2$$同时建立当前节点的左右节点，左节点的数据集$$D$$为$$D_1$$，右节点的数据集$$D$$为$$D2$$；

（5）对左右的子节点递归的调用前面1-4步，生成决策树。

CART树剪枝

我们知道，决策树算法对训练集很容易过拟合，导致泛化能力很差，为解决此问题，需要对CART树进行剪枝。CART剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小，从而能够对未知数据有更准确的预测，也就是说CART使用的是后剪枝法。一般分为两步：先生成决策树，产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，最后选择泛化能力好的剪枝策略。

2.3 使用CART算法构建决策树

import numpy as np
import matplotlib.pyplot as plt

from sklearn import datasets

iris = datasets.load_iris()
X = iris.data[:,2:]
y = iris.target

from sklearn.tree import DecisionTreeClassifier

#注意：此处传入的是"gini"而不是"entropy"，默认criterion='gini'
tree = DecisionTreeClassifier(max_depth=2,criterion="gini")
tree.fit(X,y)

def plot_decision_boundary(model,axis):
    x0,x1 = np.meshgrid(
        np.linspace(axis[0],axis[1],int((axis[1]-axis[0])*100)).reshape(-1,1),
        np.linspace(axis[2],axis[3],int((axis[3]-axis[2])*100)).reshape(-1,1)
    )
    X_new = np.c_[x0.ravel(),x1.ravel()]
    y_predict = model.predict(X_new)
    zz = y_predict.reshape(x0.shape)
    
    from matplotlib.colors import ListedColormap
    custom_map = ListedColormap(["#EF9A9A","#FFF59D","#90CAF9"])
    
    plt.contourf(x0,x1,zz,linewidth=5,cmap=custom_map)
    
plot_decision_boundary(tree,axis=[0.5,7.5,0,3])
plt.scatter(X[y==0,0],X[y==0,1])
plt.scatter(X[y==1,0],X[y==1,1])
plt.scatter(X[y==2,0],X[y==2,1])
plt.show()

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4TBQRp1M-1631279255591)(./images/13.png)]

分析上图可知:

4.7 决策树算法的两个经典案例(Sklearn实现)

在刚讲决策树之前，我们引入了相亲的例子，接下来我们就利用模拟的一些数据，并将数据的某些字段转化为算法或程序能处理的数值，利用决策树来进行分类。

相亲数据

序号	身高	房子	车子	长相	工作	约否
1	1.8	有	无	6.5	Fact	约
2	1.62	有	无	5.5	IT	约
3	1.71	无	无	8.5	Bank	约
4	1.58	有	有	6.3	Bank	约
5	1.68	无	有	5.1	IT	不约
6	1.63	有	无	5.3	Bank	不约
7	1.78	无	无	4.5	It	不约
8	1.64	无	无	7.8	Fact	不约
9	1.65	有	有	6.6	bank	约吗？

转化为可处理的数据：

接下来通过scikit-learn实现上述分类需求。

1 Scikit-Learn库实现相亲约会的例子

1.1 导包并加载数据

import pandas as pd
from sklearn.tree import DecisionTreeClassifier

# 加载数据集
df = pd.read_csv('data/Sklearntest.csv')
df

	height	house	car	handsome	job	is_date
0	1.80	1	0	6.5	2	1
1	1.62	1	0	5.5	0	1
2	1.71	0	1	8.5	1	1
3	1.58	1	1	6.3	1	1
4	1.68	0	1	5.1	0	0
5	1.63	1	0	5.3	1	0
6	1.78	0	0	4.5	0	0
7	1.64	0	0	7.8	2	0
8	1.65	0	1	6.6	0	-1

1.2 划分数据集为训练集和测试集

# 划分数据集
train,test = df.query('is_date!=-1'),df.query('is_date==-1')
# 获取特征值目标值
x_train,y_train = train.drop(['is_date'],axis=1),train['is_date']
x_test = test.drop(['is_date'],axis=1)

1.3 使用决策树进行模型训练

# 机器学习 参数可选Gini或Entropy
model = DecisionTreeClassifier(criterion='gini')
# 模型训练
model.fit(x_train,y_train)

"""
DecisionTreeClassifier(ccp_alpha=0.0, class_weight=None, criterion='gini',
                       max_depth=None, max_features=None, max_leaf_nodes=None,
                       min_impurity_decrease=0.0, min_impurity_split=None,
                       min_samples_leaf=1, min_samples_split=2,
                       min_weight_fraction_leaf=0.0, presort='deprecated',
                       random_state=None, splitter='best')
"""

# 预测x_test类别
model.predict(x_test)

# array([1])

1.4 决策树模型可视化

from sklearn.tree import export_graphviz 
from sklearn.externals.six import StringIO
from IPython.display import Image
import pydotplus 
import os

# windows 系统添加此行代码,Graphviz路径
# os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin/'

with open("dt.dot", "w") as f:
    export_graphviz(model, out_file=f)
dot_data = StringIO() # 将数据写入到内存中
export_graphviz(model, out_file=dot_data,
                         feature_names=x_train.columns,
                         class_names=["is_date:no","is_date:yes"],
                         filled=True, rounded=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue()) # 获取数据
Image(graph.create_png()) # 展示图片

输出决策树图像，并作出决策
需要安装 Graphviz 软件，下载地址http://www.graphviz.org/download/
下载之后需要配置环境变量，把安装目录如‘C:/Program Files (x86)/Graphviz2.38/bin/’
需要安装两个python库
pip install graphviz
pip install pydotplus

1.5 分析图

注：对上述图像解析几点如下：

第一行为决策条件（非叶子节点），比如根节点handsome<=5.4条件为真走左边，为假走右边。

Gini表示当前数据集的基尼不纯度

Sample表示当前数据集的样本数

Value表示当前数据集中各个类别（按类别顺序从小到大排序，第0类，第1类…）的数量，如果value中的值相等，当前节点没有作色，也就是白色。

Class表示当前数据中的多数类别，如果value中各个值相等，则按顺序取值

1.6 分析图中的逻辑

• 长相小于或等于5.4的，一定不约
• 不满足前面条件，但有房子的，一定约
• 不满足前面条件，但有车，约，没有车的，不约
• 对于待测数据 1.65 0 1 6.6 0
  • 长相大于5.4，不满则规则1，则继续下一条
  • 没有房子，不满足第二条规则2，继续吓一条
  • 有车，符合第三条规则，最后的结果为约，也就是上述的结果1

2 决策树解决泰坦尼克号问题

2.1 背景介绍

大家都看过电影泰坦尼克号，是历史上一件家喻户晓的灾难性事件；泰坦尼克号沉船事故，1912年，当时属于英国的世界级豪华客轮泰坦尼克号，因在处女航行中不幸撞上北大西洋冰山而沉没。这场事故使得1500多名乘客患难。后来，这场震惊世界的惨剧被详细地调查，而且遇难乘客的信息也逐渐被披露。在当时救援条件下，无法短时间内确认每位乘客生还的可能性。而今，许多科学家视图通过计算机模拟和分析找出潜藏在数据背后的生还逻辑。我们也尝试通过代码，揭开尘封了100多年的数据的面纱。

2.2 了解数据

数据示例：

http://biostat.mc.vanderbilt.edu/wiki/pub/Main/DataSets/titanic.txt

如下所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qHvddre3-1631279255592)(./images/wpsqK9x3V.png)]

字段信息的备注：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TAYDWnGq-1631279255593)(./images/wpsAsTYeV.png)]

任务：预测泰坦尼克号乘客能否存活 预测模型 分类问题

2.3 导入数据

#1.1导入数据
import  pandas as pd
#1.2.利用pandas的read.csv模块从互联网中收集泰坦尼克号数据集
titanic=pd.read_csv("data/titanic.csv")

2.4 数据的分析和预处理

#2.1首先观察数据的基本特征
titanic.head()

#2.2使用pandas的info属性查看数据的统计特征
titanic.info()
#注：数据共有891条乘客信息，有些特征是完整的，有一些是不完整的，如name和pclass是完整的，age是不完整的。
#由于数据比较久远，难免会丢失掉一些数据造成数据的不完整，也有数据是没有量化的。
#在决策树模型之前，需要对数据做一些预处理和分析的工作。

#2.3特征选择，这里根据对泰坦尼克号的了解，sex，age，pclass作为判断生还的三个主要因素。
X=titanic[['pclass','age','sex']]
y=titanic['survived']
#对当前选择的特征进行探查
X.info()

#2.4根据上面的输出，设计几个数据处理的任务
#1）age这个数据列，只有714个，需要补全完整
#2）sex和pclass两个数据列都是类别型的值，需要转化为数值，比如one-hot编码。
#使用平均数或者中位数来填充，对模型偏离程度造成的影响比较小
X['age'].fillna(X['age'].mean(),inplace=True)
X.info()

2.5 数据集划分

from sklearn.model_selection import train_test_split
X_train,X_test,y_train,y_test=train_test_split(X,y,test_size=0.25,random_state=33)

2.6 数据的特征转化

from sklearn.feature_extraction import DictVectorizer
vec=DictVectorizer(sparse=False)
#转换特征后，我们发现凡是类别型的值的特征都单独剥离出来了，独成一列特征，数据型不改变其值。
X_train=vec.fit_transform(X_train.to_dict(orient='records'))

X_train
"""
array([[47.        ,  1.        ,  0.        ,  1.        ],
       [40.        ,  3.        ,  0.        ,  1.        ],
       [29.69911765,  3.        ,  0.        ,  1.        ],
       ...,
       [25.        ,  2.        ,  0.        ,  1.        ],
       [21.        ,  3.        ,  0.        ,  1.        ],
       [35.        ,  2.        ,  0.        ,  1.        ]])
"""

vec.feature_names_
# ['age', 'pclass', 'sex=female', 'sex=male']

X_test=vec.transform(X_test.to_dict(orient='records'))

2.7 使用决策树模型进行预测

from sklearn.tree import DecisionTreeClassifier
#使用默认的配置初始化决策树模型
dtc=DecisionTreeClassifier()
#使用分割的数据进行模型的学习
dtc.fit(X_train,y_train)
#用训练好的模型来对测试数据集进行预测
y_predict=dtc.predict(X_test)

2.8 模型评估

from sklearn.metrics import classification_report
#输出预测准确率
dtc.score(X_test,y_test)  #0.8340807174887892
#输出更加详细的分类性能
print(classification_report(y_predict,y_test,target_names=['died','survived']))

2.9 总结

相比其他学习模型，决策树在模型描述上有巨大的优势，决策树的逻辑推断非常直观，具有清晰的可解释性，也有很方便的模型的可视化。在决策树的使用中，无需考虑对数据量化和标准化，就能达到比较好的识别率。