《机器学习》第四章-决策树

第四章 决策树

决策树是符合人类决策直觉的一种机器学习算法，直觉上很简单，但是有些自动选择的操作比较精妙。

4.1 决策树算法流程

说明：

• 第12行应该是continue？属性a*的每一个值都要生成子节点吧！
• 关键是第8行，从A中选择最优划分属性。

4.2 划分选择

总目标：提高节点的纯度，本质上也反映了奥卡姆剃刀原则，即越简单的越好。

4.2.1 方案一：基于信息增益

信息熵：

$$Ent(D)=-\sum_{k=1}^{|y|}p_klog_2p_k$$

其中，D代表当前样本，第k类样本所占的比例为$p_k$，若所有$p_k$都小于1，则$Ent(D)$取正数，假设只有一类样本，即至纯，那么信息熵为0，最小，因此也说明了信息熵越大则越杂乱越不纯。

信息增益：

$$Gain(D,a) = Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)$$

其中，a表示用属性a对样本集D进行划分，假设属性a的取值为$a^1,a^2,…,a^V$，$D^v$表示样本D中属性a取$a^v$的样本。

说明：

• 信息增益对可取值较多的属性有偏好，增益率可以将一定程度上消除这种偏好。

ID3决策树：

该决策树就是用最大化信息增益为准则选取最优划分属性，然后用4.1生成决策树。

ID3，Iterative Dichotomiser，迭代二分类器

增益率：

$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}\\ \\ IV(a)=-\sum^V_{v=1}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$$

其中IV表示intrinsic value，固有值的意思，可取值较多时，IV值也较大，IV值直观上看是属性a划分的信息熵。

C4.5决策树：

该决策树利用了增益率来消除单纯信息增益带来的多取值属性的偏好，但也不是直接使用信息增益率，因为增益率毕竟只表示增益率，消除了增益本身的影响。

该决策树先从候选划分属性中找出信息增益高于平均的属性，再从总选择增益率最高的。

该决策树还进行了缺失值处理，4.4.2

基尼指数：

$$\begin{align} Gini(D)&=\sum_{k=1}^{|y|}\sum_{k'\neq k}p_kp_{k'}\\ &=1-\sum_{k=1}^{|y|}p_k^2 \end{align}$$

直观上看，Gini反映了从样本中随机抽取两个样本，其标签不一致的概率，因此Gini越小，样本集纯度越高。

类似信息增益，定义基尼指数：

$$Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$

CART决策树：

该决策树就用了基尼指数作为选择最优划分属性的标注，然后用4.1的算法生成决策树。

4.3 剪枝处理(pruning)

目的：划分过细导致过拟合，因此剪枝用来避免过拟合。

4.3.1 预剪枝(prepruning):

一句话描述：正式生成分支之前，可以先使用测试集来测试一下生成分支之前和之后（将分支节点当作叶节点处理，标签用占比最大的标签）的性能，有提升则进行划分，否则不划分。

说明：

• 优点：可以提高运算效率，节省计算资源，一定程度可以避免过拟合；
• 缺点：“试一下”的具体操作实际为贪心策略，无法保证继续划分下去之后性能一定下降。

4.3.2 后剪枝(postpruning)

一句话描述：在按照规则生成决策树后，按照节点生成的反向顺序，逐一判断节点取消分支是否能提高性能，直至根节点。

说明：

• 优点：欠拟合风险小，泛化性能优于预剪枝（从过程上看似乎不那么贪心）。
• 缺点：慢。

4.4 连续值与缺失值

4.4.1 连续值

即连续属性而不是离散属性。

基本策略——二分法:

将样本集中的连续属性按照从小到大的顺序排列，取一个截断点，将样本分为两类，这样就形成了分支节点。问题转化成了截断点如何选取，而这个问题同样可以用最大化信息增益来解决。

说明：

• 与离散属性不同，连续属性可以重复使用。

4.4.2 缺失值

就是一些样本的属性数据不完整。面对这样样本集，有两个问题要解决：①如何选择最优属性；②如何对样本划分。

基本思路：赋予样本以权值。

给定训练集D和属性a，令$\widetilde{D}$表示D中在a上没有样本缺失的子集。

假定a有V个可取值，$\{a^1,a^2,…,a^V\}$，令$\widetilde{D}^v$表$\widetilde{D}$中属性a取$a^v$的样本子集。

令$\widetilde{D}_k$表示$\widetilde{D}$中属于第k类的样本子集。

定义:

$$\begin{align} \rho&=\frac{\sum_{\boldsymbol{x}\in\widetilde{D}}w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x}\in D}w_{\boldsymbol{x}}}\\ \widetilde{p}_k&=\frac{\sum_{\boldsymbol{x}\in\widetilde{D}_k}w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x}\in \widetilde{D}}w_{\boldsymbol{x}}},1\le k\le|y|\\ \widetilde{r}_v&=\frac{\sum_{\boldsymbol{x}\in\widetilde{D}^v}w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x}\in \widetilde{D}}w_{\boldsymbol{x}}},1\le v\le V \end{align}$$

4.4.2.1 最优属性的选择

同样基于信息增益:

$$\begin{align} Gain(D,a)&=\rho\times Gain(\widetilde{D},a)\\ &=\rho\times (Ent(\widetilde{D})-\sum_{v=1}^{V}\widetilde{r}_vEnt(\widetilde{D}^v)) \end{align}$$

其中

$$Ent(\widetilde{D}) = -\sum_{k=1}^{|y|}\widetilde{p}_klog_2\widetilde{p}_k$$

4.4.2.2 样本划分

对有缺失值的样本，则将样本划入所有子节点，且样本权值在属性值$a^v$对应的子节点中调整为$\widetilde{r}_v$。就是相当于以不同的概率划分到对应的属性值节点中，后续选择最优属性时，$\rho$值会变大。

4.5 多变量决策树

对决策树的思想理解很重要，是从几何的观点出发。

即决策树的每一个非叶节点，都对应坐标空间的一个或多个（分支≥3时）超平面。

因此有了“斜决策树”（oblique decision tree），每个非叶节点是一个形如$\sum_{i=1}^dw_ia_t=t$的线性分类器，其中权重和常数可以通过学习而得。

4.5.1 典型多变量决策树

OC1、感知机树

4.6 阅读材料

• 可以拓展阅读C4.5Rule。
• 用信息增益、增益率和基尼指数就够了，其它改进的程度不大。
• 多变量决策树可以和神经网络、感知机结合。
• 决策树的增量学习算法：ID4、ID5R、ITI，增量学习可以有效地降低新样本加入后的训练时间开销，适合工业化，但是多步增量学习后的模型会与基于全部数据训练而得的模型有较大差别。