@toc

1、决策树

  决策树属于经典的十大数据挖掘算法之一，是一种类似于流程图的树型结构，其规则就是if…then…的思想，用于数值型因变量的预测和离散型因变量的分类。决策树算法简单直观，容易解释，而且在实际应用中具有其他算法难以比肩的速度优势。

  决策树方法在分类、预测和规则提取等领域有广泛应用。在20世纪70年代后期和80年代初期，机器学习研究人员J.Ross Quinlan开发了决策树算法，称为迭代的二分器（Iterative Dichotomiser, ID3），使得决策树在机器学习领域得到极大发展。Quinlan后来又提出ID3的后继C4.5算法，成为新的监督学习算法的性能比较基准。1984年几位统计学家又提出了CART分类算法。

  分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点(node)和有向边(directed edge)组成。节点有两种类型：内部节点和叶节点。内部节点表示一个特征或者属性，叶节点表示一个类。

  ==决策树分类过程==：**从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子节点；这时，每一个子节点对应该特征的一个取值。如此递归地对实例进行测试和分配，直至达到叶节点。**最后将实例分到叶节点地类中。如下图所示是一个决策树地示意图，图中地圆和三角形分别表示内部节点和叶子节点。

决策树特点：

• 树状结构，可以很好的对数据进行分类；
• 决策树的根节点到叶节点的每一条路径构建一条规则；
• 具有互斥且完备的特点，即每一个样本均被且只能被一条路径所覆盖；
• 只要提供的数据量足够庞大真实，通过数据挖掘模式，就可以构造决策树。

2、决策树算法

2.1 Hunt算法

  Hunt算法是一种采用局部最优策略地决策树构建算法，它同时也是许多决策树算法地基础，包括ID3、C4.5和CART等。

  在Hunt算法中，通过将训练记录相继划分成较纯的子集，以递归方式建立决策树。

  设 $D_t$是与节点t相关联的训练记录集，算法步骤：

• 如果 $D_t$ 中所有记录都属于同一个类 $y_t$，则t是叶节点，用 $y_t$标记
• 如果 $D_t$ 中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成较小的子集.对于测试条件的每个输出，创建一个子结点，并根据测试结果将 $D_t$ 中的记录分布到子结点中。然后，对于每个子结点，递归地调用该算法.

  我们用信用卡欺诈的例子来说明该算法，我们要预测信用卡用户是否会按时归还欠款，还是进行信用卡欺诈。对于这个问题，训练数据集可以通过考察以前贷款者的信用卡使用记录来构造。在下表中，每条记录都包含信用卡的个人信息，以及贷款者是否拖欠贷款的类标号。

Tid	Refund	Marital Status	Taxable Income	Cheat
1	Yes	Single	125K	No
2	No	Married	100K	No
3	No	Single	70K	No
4	Yes	Married	120K	No
5	No	Divorced	95K	Yes
6	No	Married	60K	No
7	Yes	Divorced	220K	No
8	No	Single	85K	Yes
9	No	Married	75K	No
10	No	Single	90K	Yes

  如上表所示，该分类问题的初始决策树只有一个节点，类标号为“欺诈=否”(如下图)

  这意味着大多数用户都不会进行信用卡欺诈。该树需要进一步细化，因为根节点同时包含“欺诈=否”和“欺诈=是”两个类的记录。根据“Refund”测试条件，这些记录被划分为较小的子集，如下图所示。

  接下来，对根节点的每个子女递归地调用Hunt算法。从训练数据集可以看出，Refund为“yes”的用户都按时长还了欠款，因此，根节点的左子女为叶节点，标记为“欺诈=否”(如下图)

  对于右子女，我们需要继续递归调用Hunt算法，直到所有的记录都属于同一个类为止。每次递归调用形成的决策树显示在下图中。

2.2 构建决策树的问题

2.2.1 怎样为不同类型的属性指定测试条件

==基于标称属性的分裂==

• 多路划分：划分数（输出数）取决于该属性不同属性值的个数

• 二元划分：划分数为2，这种划分要考虑创建k个属性值的二元划分的所有 $2^{k-1}-1$种方法

==基于序数属性的分裂==

• 多路划分：划分数（输出数）取决于该属性不同属性值的个数

  

• 二元划分：划分数为2，这种划分要考虑创建k个属性值的二元划分的所有 $2^{k-1}-1$种方法

==基于连续属性的划分==

• 二元划分：（A<v）or （A≥v）。考虑所有的划分点，选择一个最优划分点v。

  

• 多路划分：vi≤A<vi+1 （i=1,…,k）

2.2.2 怎样选择最佳划分

  随着划分过程的不断进行，我们希望决策树的分支节点包含的样本尽可能属于同一类，即节点的纯度越来越高。纯度越高，类分布就越倾斜，划分结果越好。

  如上图所示，当节点中的类 $C_0$的数量占总数的90%时，该节点的纯度较大。因此，为了确定按某个属性划分的效果，我们需要比较划分前(父亲节点)和划分后(所有儿子节点)不纯度的降低程度，降低越多，划分的效果就越好。那么我们需要在数学上对这个不纯性进行量化。

  ==决策树有三种划分数据集的方法：信息增益法(ID3)，信息增益率(C4.5)，基尼指数(CART)==

2.3信息增益算法

2.3.1 信息增益算法原理

  如下表所示，我们有一个电脑商店，以及它的部分用户信息，图中的数据就可以认为是一个数据集，其中的年龄、收入、爱好、信用就是数据集的属性，其中“是否有购买电脑的倾向”为数据类标号，我们的目的就是通过建立一个模型来讲这些用户分为两类，即有购买电脑的倾向和没有购买电脑的倾向，此时就可以利用决策树算法来解决该问题。

id	年龄	收入	爱好	信用	购买
1	青	高	否	中	否
2	青	高	否	优	否
3	中	高	否	中	是
4	老	中	否	中	是
5	老	低	是	中	是
6	老	低	是	优	否
7	中	低	是	优	是
8	青	中	否	中	否
9	青	低	是	中	是
10	老	中	是	中	是
11	青	中	是	优	是
12	中	中	否	优	是
13	中	高	是	中	是
14	老	中	否	优	否

  1948年，香农提出“信息熵”的概念。一条信息的信息量大小和它的不确定性有直接的关系，要搞清楚一件不确定的事就需要了解大量信息。熵(entropy)用于表示随机变量不确定性的度量，熵越大，表示不确定性越大。

  假设变量S有 $S_i(i=1,2,...,n)$种情况， $p_i$表示第i情况的概率，那么随机变量S的熵定义为：

$$Entropy(S)=-\sum_{i=1}^{c}p_i\log_{2}{p_i}$$

  熵的单位是比特(bit)。熵取值最大，随即变量不确定性就最大。回到买电脑的例子，在是否购买电脑这个结果中，数据集D有9个“是”，5个“否”，因此该数据“购买电脑”的熵为：

  在随机变量S给定的条件下，随机变量A的条件熵Entropy(A|S)定义为：

$$Entropy(A|S)=-\sum_{i=1}^{c}p_i\cdot Entropy(A|S=s_i)$$

  信息增益表示的是：得知特征X的信息而使得分类Y的信息的不确定性减少的程度。如果某个特征的信息增益比较大，就表示该特征对结果的影响较大，特征A对数据集D的信息增益表示为：

  其中， $S_v$为A取值为v时S的子集。

  以购买电脑的数据集为例，我们来计算年龄这个特征的信息增益。从图中可以看出，在14条数据的年龄特征中，青年有5人，中年有4人，老年人有5人。分别计算这三种情况下的信息熵，再将信息熵相加就能得到 $Info_{age}(D):$

$$Info_{age}(D)=\frac{5}{14}I(2,3)+ \frac{4}{14}I(0,4)+\frac{5}{14}I(3,2)=0.694$$

  因此，Gain(age)的信息增益为：

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

  根据上面的计算信息增量的方法，可以得出其他特征的信息增量：

  年龄这个特征的信息增益是最大的，为0.246bit，选择年龄作为第一个根节点进行分类；然后在每个子树种，根据其特征的信息增益量进行每个划分，递归地形成每个划分上地样本判定树，如下图所示。

2.3.2 其他节点纯度的测量

  我们知道，在ID3算法中使用信息增益来选择特征，优先选择信息增益大的特征。ID3基于信息论的熵模型，会涉及大量的对数计算。能不能再简化模型的同时也不至于完全丢失熵模型的优点呢？为了解决该问题，CART分类树算法使用==基尼系数==来代替信息增益比。具体地，在分类问题中，基尼系数的表达式为：

$$GINI(t)=1-\sum_{j}^{}[p(j|t)]^2$$

  其中，p( j | t) 是在结点t中，类j发生的概率。当类分布均衡时，Gini值达到最大值 $(1 - 1/n_c)$ 。相反当只有一个类时，Gini值达到最小值0，纯性越大。

如上图，当节点t中存在0个类 $C_1$、6个类 $C_2$时，

当节点t中存在3个类 $C_1$、3个类 $C_2$时，

除此之外，==分类错误(Classification Error)值==也是测量节点纯度的总要方法之一。分类错误值的表达式如下：

• 当类分布均衡时，Gini值达到最大值$ (1 - 1/n_c) $
• 相反当只有一个类时，Gini值达到最小值0，纯性越大

2.3.3 纯性度量之间的比较

二元分类问题：

2.4 C4.5算法

  C4.5算法也是用于生成决策树的一种经典算法，是ID3算法的一种延申和优化。C4.5算法对ID3算法进行了如下改进：

• 通过信息增益率选择分裂属性，克服了ID3算法通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足
• 能够处理离散型和连续型的属性类型，即能将连续型的属性进行离散化处理
• 构造决策树之后进行剪枝操作
• 能够处理具有缺失属性值的训练数据

  对于离散特征，C4.5算法不直接使用信息增益，而是使用增益率(gain ratio)来选择最优的分支标准，增益率的定义如下：

其中，

称作分支标准T的固有值。作为分支标准的属性可取值越多，SplitINFO的值越大。

  需要注意的是：增益率准则可对取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的属性作为分支标准，而是先从侯选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性。

  在如下数据中，用户收入的增益率为：

$$SplitINFO=-\frac{4}{14}\log_{2}{\frac{4}{14}} -\frac{6}{14}\log_{2}{\frac{6}{14}} -\frac{4}{14}\log_{2}{\frac{4}{14}}=1.557$$

2.5 CART算法

  分类与回归树(Classification And Regression Tree,CART)模型由Breiman等人在1984年提出，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。

  CART是在给定输入随机变量X的条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间(即特征空间)划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。CART算法由以下步骤组成：

• 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
• 决策树剪枝：用于验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

  如下表和图所示， 割草机制造商意欲发现一个把城市中的家庭分成那些愿意购买乘式割草机和不愿意购买的两类的方法。在这个城市的家庭中随机抽取24个非拥有者的家庭作为样本。这里的自变量是饭后如(x1)和草地面积(x2),类别为拥有和非拥有。

id	收入	草地面积	拥有
1	60	18.4	是
2	85.5	16.8	是
3	64.8	21.6	是
4	61.5	20.8	是
5	87	23.6	是
6	110.1	19.2	是
7	108	17.6	是
17	84	17.6	否
18	49.2	17.6	否
19	59.4	16	否
20	66	18.4	否
21	47.4	16.4	否
22	33	18.8	否
23	51	14	否
24	63	14.8	否

  如下图所示，在使用CART算法时，首先使用 $x_2$=19进行分类。从图中可以直接发现两个矩形部分更加同质(即同一类别的点更多地聚集在一起)。

  通过递归地二分每个特征，多次划分后地决策图如下图所示，并形成如下决策树。通过观察得知，每一个矩形都是同质的，即包含一种类别的点。该算法每一次划分都将节点划分为两个子节点。

  CART和ID3一样，存在偏小细小分割，即过拟合问题，为了解决这一问题，要对特别长的树进行剪枝处理。

  剪枝的目的是避免决策树模型的过拟合。因为决策树算法在学习过程总为了尽可能正确地分类训练样本，会不停地对节点进行划分，导致整棵树地分支过多，从而导致了过拟合。决策树地剪枝策略有两种：预剪枝和后剪枝。

• 预剪枝：预剪枝就是在构造决策树的过程中，先对每个节点在划分前进行估计，如果当前节点的划分不能带来决策树模型泛化能力的提升，则不对当前进行进行划分并且将当前节点标记为叶节点。
• 后剪枝：后剪枝就是先把整棵决策树构造完毕，然后自底向上地对非叶节点进行考察，若将该节点对应地子树换为叶节点能够带来泛化能力地提升，则把该节点替换为叶节点。

3、决策树算法对Iris数据集进行分类

import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn import tree
from sklearn.model_selection import train_test_split
import pandas as pd
iris=load_iris()
X_train,X_test,y_train,y_test=train_test_split(iris.data,iris.target,test_size=0.20,random_state=30,shuffle=True)
#criterion缺省为'gini'
clf=tree.DecisionTreeClassifier(criterion='entropy')
clf=clf.fit(X_train,y_train)
plt.figure(dpi=150)
# feature_names=iris.feature_names设置决策树种显示的特征名称
tree.plot_tree(clf,feature_names=iris.feature_names,class_names=iris.target_names)

# 预测数据[6,5,5,2]的类别
print('数据[6,5,5,2]的类别：',clf.predict([[6,5,5,2]]))
print('数据[5.1,3.5,1.4,0.2]的类别：',clf.predict([[5.1,3.5,1.4,0.2]]))
print('测试集的标签:\b',y_test)
y_pre=clf.predict(X_test)
print('预测的测试集标签：\b',y_pre)
print('模型准确率为:',clf.score(X_test,y_test))