机器学习之决策树

前言

决策树是很常见的机器学习分类算法，竟然叫决策树，那么它的模型其实就像树一样。通过对样本集的学习，挖掘出有用的规则。对于程序员来说或许以条件语句来看就更好理解了，决策树可以看成是多个if then条件语句的集合。这种模型等同于我们写的条件语句，所以它的预测分类速度是很快的。

例子

来个例子了解下决策树分类过程，以女生相亲挑“高富帅”为例吧，遇到已婚的肯定是不交往了，在未婚的情况下接着要看是否有房产，没有的话也免谈了，有房产那么继续看身高，180cm以上的接受，而180cm以下则再看有没有两套房，有则可以弥补身高不足，否则则拒绝。

一般一棵决策树包含了一个根节点、若干个内部节点（图中圆形节点）和若干个叶节点（图中方形节点），内部节点用于描述一种属性，而叶节点用来表示分类的结果。

怎么学习

从例子来看，假设这是一个贷款是否批准的样本，根据这个样本怎样创建一个决策树？

编号	房产	婚姻	月收入	是否批准
1	有	单身	30k	是
2	无	已婚	20k	是
3	无	单身	10k	是
4	有	已婚	30k	是
5	无	离婚	8k	否
6	无	单身	5k	否
7	有	离婚	10k	是

属性集为{“房产”，“婚姻”，“月收入”}，假如选择以房产为最优分割属性，那么样本集分为{1,4,7}和{2,3,5,6}，有房产情况都为批准，停止分割。

无房产的情况继续分割，{2,3,5,6}，此时属性集为{“婚姻”，“月收入”}，选择婚姻为分割属性，则分为{2}、{3,6}、{5}，分割后如下图。

最后剩下{3,6}待分割，用月收入属性以10k为界，最终完成整个决策树的创建。

要点：

所有数据从根节点开始
自上而下分而治之
样本根据属性集递归进行分割
通过一定规则或算法选择属性
每个节点上的数据都是同一类时则停止分割
根据样本训练出来的决策树尽可能与样本集没有矛盾且有预测能力
决策树生成只考虑局部最优，剪枝则全局最优。

属性划分选择

核心是通过信息增益来选择划分属性，在看信息增益的定义之前先看信息熵。设有样本集D，对于k个类，占得比例分别为 p_i(i=1,2,3...,n) ，则样本集D的信息熵为，

$H(D) = - \sum_{i=1}^{n} \ p_i \ log_2 p_i$

如果选择属性a来分割，假如它有m种可能值，即 ${a_1,a_2,...,a_m}$ 。则会有m个分支，其中第k个分支节点包含了集合D所有属性a值为 a_k 的样本，这里组成的新集合记为 D_k 。此时可以定义信息增益为，

$gain(D,a) = H(D) - \sum_{k=1}^{m}\cfrac{|D_k|}{|D|}H(D_k)$

重新回到前面例子，计算“房产”的信息增益，首先计算集合D的信息熵，

$H(D) = -(\frac{5}{7}\ log_2\frac{5}{7} + \frac{2}{7}\ log_2\frac{2}{7}) = 0.3467 + 0.5164 = 0.863$

选择“房产”为属性，样本集分为{1,4,7}和{2,3,5,6}，则

$H(D_1) = -(\frac{3}{3}\ log_2 \frac{3}{3} + \frac{0}{3}\ log_2 \frac{0}{3}) = 0$

$H(D_2) = -(\frac{2}{4}\ log_2 \frac{2}{4} + \frac{2}{4}\ log_2 \frac{2}{4}) = 1$

其中 0log_20 约定为0，此时分类已达到“纯”。增益为

$gain(D,house) = 0.863 - (\frac{3}{7} * 0 + \frac{4}{7} * 1) = 0.292$

其他的属性也类似计算出来，然后比较信息增益，选择最大的作为分割属性。

信息增益率

前面说到根据信息增益来对划分属性的选择，但是它会偏向于可能值较多的的属性，所以会对最终的属性选择带来偏向，于是引入信息增益率。它的定义如下，

$gain_r(D,a) = \frac{gain(D,a)}{I(a)}$

其中，

$I(a) = - \sum_{j=1}^{v} \frac{|D_j|}{|D|}log_2 \frac{|D_j|}{|D|}$

这里v就是a属性可能值的个数。

ID3和C4.5算法

ID3决策树算法在决策树生成的过程中，每个节点使用的是信息增益来选择分割属性。大致的步骤是从根节点开始，分别假设各个属性作为分割时的信息增益，即是像上面属性分割选择过程那样计算，选出信息增益最大的属性作为根节点的分割属性。完成后根据属性又可以分成若干分支，每个分支对应一个子节点，然后又根据上面的步骤计算不同属性的信息增益，不断递归下去，直到某节点以每个属性作为分割时的信息增益都很小或已经没有属性可以选择，这时则停止计算，得到一个最终的决策树。

C4.5与ID3创建决策树的过程类似，不同的是它的属性划分的选择是根据信息增益率的，而不是使用信息增益。

剪枝

为什么要剪枝？因为在生成决策树的过程中不断迭代产生的树很容易产生过拟合现象，虽然对训练样本的分类准确率高，但泛化能力可能较低，所以就需要通过一定手段进行剪枝操作。

判断某个枝是否要剪掉主要的依据就是，某个节点在划分前后是否能带来泛化能力的提升，如果可以则进行划分，否则则剪枝。那么现在工作就变为如何判断泛化能力是否提升？这就需要从训练集中抽取一部分数据作为验证集而不参与训练，然后在训练过程中在属性划分前后分别用验证集计算准确率，如果划分后准确率比划分前高则划分，否则不进行划分，即等同剪枝操作。

-------------推荐阅读------------

------------------广告时间----------------

公众号的菜单已分为“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等，可能有一款适合你的胃口。

鄙人的新书《Tomcat内核设计剖析》已经在京东销售了，有需要的朋友可以购买。感谢各位朋友。

为什么写《Tomcat内核设计剖析》

欢迎关注：