【机器学习】决策树

基本思想

决策树，顾名思义，就是用于决策的树结构，或者说是基于树结构来进行决策。

一棵决策树一般包含一个根节点、若干个内部节点和若干个叶节点。每个叶节点对应一个决策结果，其他非叶节点对应于一个属性测试，每个节点包含的样本集合根据属性测试的结果被划分到子节点当中。根节点包含样本全集，从根节点到每个叶节点的路径对应了一个判定测试序列。

决策树学习的目的是产生一棵泛化能力强的决策树。

下图是判断西瓜是好瓜还是坏瓜的一棵决策树：

周志华《机器学习》 图4.4

举一个例子来说明上面介绍的概念，每一个非叶节点（圆角矩形）都是对某个属性“测试”的问题，比如图中的根蒂形状，或者是西瓜色泽等。叶节点代表从根节点经过一系列属性测试得到我们要判断的西瓜是好是坏。假如现在有一个纹理清晰、根蒂稍蜷、色泽青绿的瓜，根据上图的路径可以做出这个瓜是好瓜的判断。

（其实就是一系列if-then条件判断）

从上面的内容可以看出基于决策树的分类是非常直观的，但是决策树的关键在于如何根据训练数据构造决策树。

构造决策树的算法还是比较容易想到的：假设有训练集$D$和特征集合$A$,从根节点开始，每个节点选择一个特征$a_{\ast}$，然后根据这个特征每一个取值划分，递归地调用函数进行子树的构造，同时使用的训练集和特征集合也要相应的进行修改（$A$去掉使用过的特征，从$D$中选择符合特征取值的样本子集），直到叶子节点。

递归调用的边界有三个：（1）$D$中所有样本都是同一类别的，无法分类（2）属性集为空，或者所有样本在所有属性上取值相同，无法划分（3）当前节点包含的样本集合为空（见下图中非蓝色框）

在这个算法当中最关键的就是如何选择最优划分属性（上图蓝色框）。

划分选择

一般而言，我们希望随着划分过程的进行，决策树的分支节点所包含的样本尽可能属于同一类别，也就是节点的纯度越来越高。对于纯度的度量方法的不同也就导致了不同的决策树学习算法。

ID3

"信息熵"是度量样本集合纯度（不确定度）最常用的指标。假定当前样本集合$D$中第$k$类样本所占的比例为$p_k(k=1,2,3,...,\Upsilon)$,则$D$的信息熵定义为：
$Ent(D)=-\sum^{|\Upsilon|}_{k=1}p_klog_{2}p_k$
显然，$Ent(D)$越小，说明$D$的纯度越高（极端条件下，只有一种样本，则$Ent(D)=0$）

假设离散属性$a$有$V$个可能取值$(a^1,a^2,...,a^V)$,将属性$a$上取值为$a^v$的样本集合记作$D^v$,则用属性$a$对样本集$D$进行划分获得的信息增益为：
$Gain(D,a)=Ent(D)-\sum^V_{v=1}\frac{|D^v|}{|D|}Ent(D^v)$
ID3决策树学习算法就是在选择特征时选择最大学习增益的特征：
$a_{\ast}=arg max_{a\in A}Gain(D,a)$
下面使用ID3算法选择第一个划分的特征：

周志华《机器学习》表4.1

样本集$D$中8个好瓜，9个坏瓜：
$Ent(D) = -(\frac{8}{17}log_2\frac{8}{17}+\frac{9}{17}log_2\frac{9}{17})=0.998$
待选择的特征有：色泽、根蒂、敲声、纹理、脐部、触感。

以色泽为例，色泽特征可能的取值有{青绿、乌黑、浅白}
$\begin{aligned} &D^1(色泽=青绿) = \{1, 4, 6, 10, 13, 17\}，其中好瓜3个坏瓜3个\\ &D^2(色泽=乌黑) = \{2, 3, 7, 8, 9, 15\}，其中好瓜4个坏瓜2个\\ &D^3(色泽=浅白) = \{5, 11, 12, 14, 16\}，其中好瓜1个坏瓜4个 \end{aligned}$
如果用“色泽”划分，3个分支节点的信息熵：

那么色泽特征的信息增益为：

同理计算出其他属性的信息增益，最终选择纹理作为划分特征。

信息熵代表随机变量的复杂度（不确定度），信息增益公式的后半部分是划分后各子节点的信息熵加权和，样本数越多的子节点影响越大。我们的目标是提升纯度（样本尽可能多的属于同一类别），所以划分后的信息熵加权和越小越好（越小代表纯度越高，复杂度越低）。

C4.5

在计算信息增益时，有意忽略了编号这一属性，假设存在与编号类似的一个属性$b$，每一个样本都有不同的一个属性值，那么$N$个样本按照$b$划分的信息增益远大于其他属性：因为每个分支仅包含一个样本，纯度达到最大。但是这样的决策树显然不具有泛化能力。

从上述可以知道信息增益其实对于可取值数目较多的属性有偏好，为减少这种偏好的不利影响，C4.5决策树算法使用**“增益率”选择最优划分属性：
$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}\\ IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$
$IV(a)$称作属性$a$的固有值**，$a$可能的取值数目越多，$IV(a)$的值通常会越大，这样就弥补了使用信息增益的缺点，但是有了$IV(a)$之后，增益率准则对可取值数目较少的属性有所偏好（分母变小，整体变大），所以C4.5算法不直接选择增益率最大的候选划分属性，候选划分属性中找出信息增益高于平均水平的属性（这样保证了大部分好的的特征），再从中选择增益率最高的（又保证了不会出现编号特征这种极端的情况）

CART

CART决策树使用基尼指数选择划分属性：
$Gini(D)=\sum_{k=1}^{|\Upsilon|}\sum_{k^‘\neq k}p_kp_{k'}=1-\sum_{k=1}^{|\Upsilon|}p_k^2$
$Gini(D)$反映了从数据集中随机抽取两个样本其类别标记不一致的概率，$Gini(D)$越小数据集纯度越高
选择划分后基尼指数最小的属性作为最优划分属性：
$a_{\ast}=argmin_{a \in A}Gini\_index(D,a)\\ Gini\_index(D,a)=\sum^{V}_{v=1}\frac{|D^v|}{|D|}Gini(D^v)$

剪枝处理

待更新

参考

• 周志华《机器学习》
• 深入浅出理解决策树算法（二）-ID3算法与C4.5算法