机器学习之 scikit-learn 开发入门 -
监督学习 - 决策树
一、决策树的介绍决策树算法其实很古老，作为一个码农经常会不停的敲 if，else if，else，其实就已经在用到决策树的思想了。只是你有没有想过，有这么多条件，用哪个条件特征先做 if，哪个条件特征后做 if 比较优呢？怎么准确的定量选择这个标准就是决策树机器学习算法的关键了。
一般的，介绍决策树算法的书籍都晦涩难懂，这里我用西瓜简单描述下决策模型的原理。这个瓜是好瓜吗？我们对这个问题决策时，通常会进行一系列的判断，我们首先判断它的颜色，如果是青绿色，我们再判断它的根蒂是什么形态，如果是蜷缩，我们再判断它的敲声，最后决策出这是个好瓜。可以发现，我们是基于树结构来进行决策的，这恰是人类面临决策问题时一种很自然的处理机制。这就是决策模型的原理。
二、决策树经典案例小王是一家著名高尔夫俱乐部的经理。但是他被雇员数量问题搞得心情十分不好。某些天好像所有人都來玩高尔夫，以至于所有员工都忙的团团转还是应付不过来，而有些天不知道什么原因却一个人也不来，俱乐部为雇员数量浪费了不少资金。
决策树模型就被建起来，用于解决问题。
我们得出第一个结论：如果天气是多云，人们总是选择玩高尔夫，而只有少数很着迷的甚至在雨天也会玩。
接下来我们把晴天组的分为两部分，我们发现顾客不喜欢湿度高于 70% 的天气。最终我们还发现，如果雨天还有风的话，就不会有人打了。
通过分类树给出了一个解决方案。 在晴天，潮湿的天气或者刮风的雨天解雇了大部分员工，因为这种天气不会有人打高尔夫。而其他的天气可以雇用一些临时员工来工作。
结论是决策树帮助我们把复杂的数据表示转换成相对简单的直观的结构。
三、scikit-learn 决策树算法类库介绍scikit-learn 决策树算法类库内部分类决策树的类对应的是 DecisionTreeClassifier。下面就对 DecisionTreeClassifier 的重要参数做一个总结。
- 特征选择标准 criterion：可以使用“gini”或者“entropy”，前者代表基尼系数，后者代表信息增益。一般说使用默认的基尼系数“gini”就可以了，即 CART 算法。除非你更喜欢类似 ID3，C4.5 的最优特征选择方法。
- 特征划分点选择标准 splitter：可以使用“best”或者“random”。前者在特征的所有划分点中找出最优的划分点。后者是随机的在部分划分点中找局部最优的划分点。 默认的“best”适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐“random”。
- 决策树最大深 max_depth：决策树的最大深度，默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值 10-100 之间。
- 叶子节点继续划分所需最小样本数 min_samples_split：这个值限制了子树继续划分的条件，如果某节点的样本数少于 min_samples_split，则不会继续再尝试选择最优特征来继续划分子树。默认是 2。
- 叶子节点最少样本数 min_samples_leaf：这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。默认是 1。剪枝在原理篇会介绍到。
- 叶子节点最小的样本权重之和 min_weight_fraction_leaf：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。默认是 0，就是不考虑权重问题。
四、决策树应用示例1. 导入头文件# coding=utf-8 import numpy as np import matplotlib . pyplot as plt from sklearn import datasets from sklearn . tree import DecisionTreeClassifier
2. 生成样本数据# 使用自带的iris数据 iris = datasets . load_iris () x = iris . data [:, [ 0 , 2 ]] y = iris . target print iris . feature_names [ 0 ], iris . feature_names [ 1 ] print x [[ 0 , 50 , 100 ]] print iris . target_names print y [[ 0 , 50 , 100 ]]
我们看一看数据的含义：
可以看到矩阵的第一列是花萼的长度，第二列为花萼的宽度。0，1，2 分别代表三种花。 分别查了下这三种花：
Setosa：山鸢尾
Versicolor：云芝
Virginica：维吉尼亚鸢尾
3. 训练模型，限制树的最大深度 4# 训练模型，限制树的最大深度4 clf = DecisionTreeClassifier ( max_depth = 4 ) # 拟合模型 clf . fit ( X , y )
4. 列举所有的数据构成分类图# 生成花萼长度的最小值和最大值 x_min , x_max = X [:, 0 ]. min () - 1 , X [:, 0 ]. max () 1 # 生成花萼宽度的最小值和最大值 y_min , y_max = X [:, 1 ]. min () - 1 , X [:, 1 ]. max () 1 # 将上面横坐标生成连续的点间隔为0.1 xs = np . arange ( x_min , x_max , 0.1 ) # 将上面纵坐标生成连续的点间隔为0.1 ys = np . arange ( y_min , y_max , 0.1 ) # 将横坐标和纵坐标生成点的形成矩阵 xx , yy = np . meshgrid ( xs , ys ) print xx print yy
# 顺序预测矩阵的所有点 Z = clf . predict ( np . c_ [ xx . ravel (), yy . ravel ()]) Z = Z . reshape ( xx . shape ) # 画图 plt . contourf ( xx , yy , Z , alpha = 0.4 ) plt . scatter ( X [:, 0 ], X [:, 1 ], c = y , alpha = 0.8 ) plt . show ()
可以知道紫色为 Setosa，绿色为 Versicolor，黄色为 Virginica。
五、决策树构建过程可视化1. 准备环境如果想知道决策树是如何进行分类的需要安装 graphviz。安装过程如下：
- 安装 graphviz。下载地址在：www.graphviz.org。如果你是 linux，可以用 apt-get 或者 yum 的方法安装。如果是 windows，就在官网下载 msi 文件安装。无论是 linux 还是 windows，装完后都要设置环境变量，将 graphviz 的 bin 目录加到 PATH，比如我是 windows，将 C:/Program Files (x86)/Graphviz2.38/bin/ 加入了 PATH；
- 安装 python 插件 graphviz： pip install graphviz；
- 安装 python 插件 pydotplus。这个没有什么好说的：pip install pydotplus。
2. 导入头文件#coding=utf-8 from sklearn . datasets import load_iris from sklearn import tree import os import pydotplus from IPython . display import Image # 换成自己的路径 os . environ [ "PATH" ] = os . pathsep 'C:/Program Files (x86)/Graphviz2.38/bin'
3. 生成 dot 文件iris = load_iris () clf = tree . DecisionTreeClassifier () clf = clf . fit ( iris . data , iris . target ) with open ( "iris.dot" , 'w' ) as f : f = tree . export_graphviz ( clf , out_file = f )
4. 生成 PDF 查看决策树可视化图打开命令行输入：dot -Tpdf iris.dot -o iris.pdf 查看 PDF 如下图：
六、决策树的原理1. 决策树 ID3 算法1) 决策树 ID3 算法的信息论基础
首先，我们需要熟悉下信息论中信息熵的概念。信息(熵)定义为离散随机事件的出现概率。具体随机变量 X 的熵的表达式为：
比如 X 有 2 个可能的取值，而这两个取值各为 1/2 时 X 的熵最大，此时 X 具有最大的不确定性。值为：
如果一个值概率大于 1/2，另一个值概率小于 1/2，则不确定性减少，对应的熵也会减少。比如一个概率 1/3，一个概率 2/3，则对应熵为：
熟悉了一个变量X的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：
有了联合熵，又可以得到条件熵的表达式 H(X|Y)，条件熵类似于条件概率，它度量了我们的 X 在知道 Y 以后剩下的不确定性。表达式如下：
我们刚才提到 H(X) 度量了 X 的不确定性，条件熵 H(X|Y) 度量了我们在知道 Y 以后 X 剩下的不确定性，那么 H(X)-H(X|Y) 呢？从上面的描述大家可以看出，它度量了 X 在知道 Y 以后不确定性减少程度，这个度量我们在信息论中称为互信息，记为 I(X,Y)。在决策树 ID3 算法中叫做信息增益。ID3 算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。
下面用图进行说明：
左边的椭圆代表 H(X)，右边的椭圆代表 H(Y)，中间重合的部分就是我们的互信息或者信息增益 I(X,Y)，左边的椭圆去掉重合部分就是 H(X|Y)，右边的椭圆去掉重合部分就是 H(Y|X)。两个椭圆的并就是 H(X,Y)。
2) 决策树 ID3 算法的思路
ID3 算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。这里我们举一个信息增益计算的具体的例子。比如我们有 15 个样本 D，输出为 0 或者 1。其中有 9 个输出为 1， 6 个输出为 0。 样本中有个特征 A，取值为 A1，A2 和 A3。在取值为 A1 的样本的输出中，有 3 个输出为 1， 2 个输出为 0，取值为 A2 的样本输出中，2 个输出为 1，3个 输出为 0， 在取值为 A3 的样本中，4 个输出为 1，1 个输出为 0。
样本 D 的熵为：
样本 D 在特征下的条件熵为：
对应的信息增益为：
下面是算法过程： 输入的是 m 个样本，样本输出集合为 D，每个样本有 n 个离散特征，特征集合即为 A，输出为决策树 T。
- 初始化信息增益的阈值 E；
- 判断样本是否为同一类输出 Di，如果是则返回单节点树 T。标记类别为 Di；
- 判断特征是否为空，如果是则返回单节点树 T，标记类别为样本中输出类别 D 实例数最多的类别；
- 计算 A 中的各个特征（一共 n 个）对输出 D 的信息增益，选择信息增益最大的特征 Ag；
- 如果 Ag 的信息增益小于阈值 E，则返回单节点树 T，标记类别为样本中输出类别 D 实例数最多的类别；
- 否则，按特征 Ag 的不同取值 Agi 将对应的样本输出 D 分成不同的类别 Di。每个类别产生一个子节点。对应特征值为 Agi。返回增加了节点的数 T；
- 对于所有的子节点，令：
递归调用 2-6 步，得到子树 Ti 并返回。
3) 决策树 ID3 算法的不足
- ID3 没有考虑连续特征，比如长度，密度都是连续值，无法在 ID3 运用。这大大限制了 ID3 的用途；
- ID3 采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有 2 个值，各为 1/2，另一个变量为 3 个值，各为 1/3，其实他们都是完全不确定的变量，但是取 3 个值的比取 2 个值的信息增益大。如果校正这个问题呢？
- ID3 算法对于缺失值的情况没有做考虑；
- 没有考虑过拟合的问题。
2. 决策树 C4.5 算法1) 决策树 C4.5 算法的改进
ID3 算法有四个主要的不足，一是不能处理连续特征，第二个就是用信息增益作为标准容易偏向于取值较多的特征，最后两个是缺失值处理的问和过拟合问题。作者在 C4.5 算法中改进了上述 4 个问题。
对于第一个问题，不能处理连续比如 m 个样本的连续特征 A 有 m 个，从小到大排列 C4.5 取相邻两样本值的平均数，一共取得 m-1 个点，其中第 i 个点 Ti 表示为：Ti=ai ai 12。对于这 m-1 个点，分别计算以该点信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为 at，则小于 at 的值为类别 1，大于 at 的值为类别 2，这样我们就做到了连续特征的离散化。
对于第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题。C4.5 引入信息增益比的变量 IR(X,Y)，它是信息增益和特征熵的比值。表达式如下：
其中 D 为样本特征输出的集合，A 为样本特征，对于特征熵 HA(D)，表达式如下：
其中 n 为特征 A 的类别数， Di 为特征 A 的第 i 个取值对应的样本个数。D 为样本个数。 特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。
对于第三个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。
对于第一个子问题，对于某一个有缺失特征值的特征 A。C4.5 的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为 1），然后划分数据，一部分是有特征值 A 的数据 D1，另一部分是没有特征 A 的数据 D2。然后对于没有缺失特征 A 的数据集 D1 来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征 A 缺失的样本加权后所占加权总样本的比例。
对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征 A 的样本 a 之前权重为 1，特征 A 有 3 个特征值 A1, A2, A3。 3 个特征值对应的无缺失 A 特征的样本个数为 2, 3, 4，则 a 同时划分入 A1,A2,A3。对应权重调节为 2/9, 3/9, 4/9。
对于第 4 个问题，C4.5 引入了正则化系数进行初步的剪枝。具体方法这里不讨论。下篇讲 CART 的时候会详细讨论剪枝的思路。
2) 决策树 C4.5 算法的不足与思考
- 由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5 的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。后面在下篇讲 CART 树的时候我们会专门讲决策树的减枝思路，主要采用的是后剪枝加上交叉验证选择最合适的决策树。
- C4.5 生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
- C4.5 只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
- C4.5 由于使用了熵模型，里面有大量的耗时的对数运算，如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。
3. 决策树 CART 算法1) 决策树 CART 算法基础
CART，又名分类回归树，是在 ID3 的基础上进行优化的决策树，学习 CART 记住以下几个关键点：
- CART 既能是分类树，又能是分类树；
- 当 CART 是分类树时，采用 GINI 值作为节点分裂的依据；当 CART 是回归树时，采用样本的最小方差作为节点分裂的依据；
- CART 是一棵二叉树。
接下来将以一个实际的例子对 CART 进行介绍：
分类树的作用是通过一个对象的特征来预测该对象所属的类别，而回归树的目的是根据一个对象的信息预测该对象的属性，并以数值表示。
CART 既能是分类树，又能是回归树，如上表所示，如果我们想预测一个人是否已婚，那么构建的 CART 将是分类树；如果想预测一个人的年龄，那么构建的将是回归树。
分类树和回归树是怎么做决策的？假设我们构建了两棵决策树分别预测用户是否已婚和实际的年龄，如图 1 和图 2 所示：
图 1 表示一棵分类树，其叶子节点的输出结果为一个实际的类别，在这个例子里是婚姻的情况（已婚或者未婚），选择叶子节点中数量占比最大的类别作为输出的类别；
图 2 是一棵回归树，预测用户的实际年龄，是一个具体的输出值。怎样得到这个输出值？一般情况下选择使用中值、平均值或者众数进行表示，图 2 使用节点年龄数据的平均值作为输出值。
2) 决策树 CART 算法连续特征和离散特征的处理
分裂的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。那么 CART 是如何评价节点的纯度呢？如果是分类树，CART 采用 GINI 值衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度。节点越不纯，节点分类或者预测的效果就越差。 GINI 值的计算公式：
节点越不纯，GINI 值越大。以二分类为例，如果节点的所有数据只有一个类别，则：
如果两类数量相同，则
回归方差计算公式：
方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为 0，此时可以很肯定得认为该节点的输出值；如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大。
因此，无论是分类树还是回归树，CART 都要选择使子节点的 GINI 值或者回归方差最小的属性作为分裂的方案。即最小化（分类树）：
或者（回归树）：
3) 决策树 CART 算法建立树
节点的分裂分为两种情况，连续型的数据和离散型的数据。
CART 对连续型属性的处理与 C4.5 差不多，通过最小化分裂后的 GINI 值或者样本方差寻找最优分割点，将节点一分为二，在这里不再叙述，详细请看 C4.5。
对于离散型属性，理论上有多少个离散值就应该分裂成多少个节点。但 CART 是一棵二叉树，每一次分裂只会产生两个节点，怎么办呢？很简单，只要将其中一个离散值独立作为一个节点，其他的离散值生成另外一个节点即可。这种分裂方案有多少个离散值就有多少种划分的方法，举一个简单的例子：如果某离散属性一个有三个离散值 X，Y，Z，则该属性的分裂方法有 {X}、{Y,Z}，{Y}、{X,Z}，{Z}、{X,Y}，分别计算每种划分方法的基尼值或者样本方差确定最优的方法。
以属性“职业”为例，一共有三个离散值，“学生”、“老师”、“上班族”。该属性有三种划分的方案，分别为{“学生”}、{“老师”、“上班族”}，{“老师”}、{“学生”、“上班族”}，{“上班族”}、{“学生”、“老师”}，分别计算三种划分方案的子节点 GINI 值或者样本方差，选择最优的划分方法，如下图所示：
第一种划分方法：{“学生”}、{“老师”、“上班族”}
预测是否已婚（分类）：
预测年龄（回归）：
第二种划分方法：{“老师”}、{“学生”、“上班族”}
预测是否已婚（分类）：
预测年龄（回归）：
第三种划分方法：{“上班族”}、{“学生”、“老师”}
预测是否已婚（分类）：
预测年龄（回归）：
综上，如果想预测是否已婚，则选择{“上班族”}、{“学生”、“老师”}的划分方法，如果想预测年龄，则选择{“老师”}、{“学生”、“上班族”}的划分方法。
4) 决策树 CART 算法树剪枝
CART 采用 CCP（代价复杂度）剪枝方法。代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。
可描述如下： 令决策树的非叶子节点为｛T1,T2,T3,......,Tn｝。
- 计算所有非叶子节点的表面误差率增益值 a=｛a1,a2,a3,......,an｝；
- 选择表面误差率增益值ai最小的非叶子节点 Ti（若多个非叶子节点具有相同小的表面误差率增益值，选择节点数最多的非叶子节点）；
- 对 Ti 进行剪枝。
表面误差率增益值的计算公式：
其中：
- R(t) 表示叶子节点的误差代价，R(t)=r(t)*p(t) ，r(t) 为节点的错误率，p(t) 为节点数据量的占比；
- R(T) 表示子树的误差代价，
ri(t) 为子节点 i 的错误率，pi(t) 表示节点 i 的数据节点占比；
3. N(T) 表示子树节点个数。
5） 决策树 CART 算法小结
下表给出了 ID3，C4.5 和 CART 的一个比较总结。希望可以帮助大家理解。
七、决策树总结决策树算法的优点：
- 简单直观，生成的决策树很直观；
- 基本不需要预处理，不需要提前归一化，处理缺失值；
- 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值；
- 可以处理多维度输出的分类问题；
- 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释；
- 对于异常点的容错能力好，健壮性高。
决策树算法的缺点：
,
- 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进；
- 决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。即：集成学习通过将多个单个学习器集成/组合在一起，使它们共同完成学习任务，每个学习器侧重点不同，他们一起工作时各取所长；
- 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决；
- 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
