Note of Machine Learning 4

第4章　决策树

4.1　基本流程

决策树(decision tree)是基于树结构进行决策的一种常见机器学习方法。

决策过程的最终结论对应了所希望的判定结果；决策过程中提出的每个判定问题都是对某个属性的”测试”；每个测试或是导出结论，或是导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内。

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶节点；叶结点对应于决策结果，其他每个结点对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强的决策树，基本流程遵循”分治”(divide-and-conquer)策略。

4.2　划分选择

决策树的关键是如何选择最优划分属性。随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的”纯度”(purity)越来越高

4.2.1　信息增益

“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占比例为$p_k(k=1,2,\dots,|y|)$，则D的信息熵定义为

$$Ent(D)=-\sum_{k=1}^{|y|}p_k\log_2p_k.　　　　　(4.1)$$

$Ent(D)​$的值越小，D的纯度越高。

假定离散属性a有V个可能取值${a^1,a^2,\dots,a^V}$，若使用a来对样本集进行划分，则产生V个分支点，其中第v个分支点包含了D中所有在属性a上取值为$a^v$的样本，记为$D^v$。根据(4.1)计算出$D^v$的信息熵，再考虑到不同的分支结点所包含的样本数不同，于是可计算出用属性a对样本集D进行划分所获得的”信息增益”(information gain)

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

信息增益越大，意味着使用属性a来进行划分所获得的”纯度提升越大”越大。因此可用信息增益来进行决策树的划分属性选择。即在图4.2算法第8行选择属性$a*={\arg\max}{a\in A}Gain(D,a)$。

以表4.1西瓜数据集为例。数据集包含17个训练样例。$|y|=2$。决策树学习开始时，根结点包含D中所有样例，正例占$p_1=\frac{8}{17}$，反例占$p_2=\frac{9}{17}$。根据式(4.1)算出根结点的信息熵

$$Ent(D)=-\sum_{k=1}^2p_k\log_2p_k=-(\frac{8}{17}\log_2\frac{8}{17}+\frac{9}{17}\log_2\frac{9}{17})=0.998.$$

然后计算当前属性集合{色泽，根蒂，敲声，纹理，脐部，触感}中每个属性的信息增益。以色泽为例，使用该属性对D进行划分，可得到三个子集。根据式(4.1)分别计算出用色泽划分之后所获得的三个分支结点的信息熵为

$$Ent(D^1)=-(\frac{3}{6}\log_2\frac{3}{6}+\frac{3}{6}\log_2\frac{3}{6})=1.000,\\ Ent(D^2)=-(\frac{4}{6}\log_2\frac{4}{6}+\frac{2}{6}\log_2\frac{2}{6})=0.918,\\ Ent(D^3)=-(\frac{1}{5}\log_2\frac{1}{5}+\frac{4}{5}\log_2\frac{4}{5})=0.722,\\$$

于是根据式(4.2)计算属性色泽的信息增益为

$$\begin{aligned} Gain(D,色泽)&=End(D)-\sum_{v=1}^3\frac{|D^v|}{|D|}Ent(D^v)\\ &=0.998-(\frac{6}{17}\times1.000+\frac{6}{17}\times0.918+\frac{5}{17}\times0.722)\\ &=0.109. \end{aligned}$$

类似的，可计算出其他属性的信息增益。选择信息增益最大的属性作为划分属性。然后决策树学习算法将对每个分支点做进一步划分，最终得到的决策树如图4.4所示。

4.2.2　增益率

若把表4.1中的编号也作为一个候选划分属性，则其信息增益远大于其他候选划分属性。这样的决策树显然不具有泛化能力，实际上信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，可以使用”增益率”(gain ratio)来选择最优划分属性。采用与式(4.2)相同的符号表示，增益率定义为

$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)},　　　　　(4.3)$$

其中

$$IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}　　　　　(4.4)$$

称为属性a的”固有值”(intrinsic value)。属性a的可能取值数目越多(即V越大),IV(a)的值通常会越大。增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

4.2.3　基尼指数

CART决策树使用”基尼指数”(Gini index)来选择划分属性。采用与式(4.1)相同的符号，数据集D的纯度可用基尼值来度量：

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

Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此Gini(D)越小，则数据集D的纯度越高。采用与式(4.2)相同的符号表示，属性a的基尼指数定义为

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

于是，在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即$a*={\arg\min}{a\in A}Gini_index(D,a)$。

4.3　剪枝处理

剪枝(pruning)是决策树学习算法对付”过拟合”的主要手段。决策树剪枝的基本策略有”预剪枝”(prepruning)和”后剪枝”(postpruning)。预剪枝是在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升则停止划分并将当前结点标记为叶结点；后剪枝先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则为之。本节使用留出法进行判断泛化性能是否提升的标准。将表4.1随机划分为两部分变为表4.2，上为训练集下为测试集。

采用信息增益准则进行划分属性选择，生成一棵如图4.5的决策树。

4.3.1　预剪枝

基于预剪枝策略从表4.2数据所生成的决策树如图4.6所示，其测试集精度为71.4%。这是一棵仅有一层划分的决策树，亦称”决策树桩”(decision stump)。预剪枝降低了过拟合风险，减少了时间开销，却带来了欠拟合的风险。

4.3.2　后剪枝

后剪枝先基于表4.2生成如图4.5的决策树，其测试集精度为42.9%。然后依次考察每个结点，若将其领衔的子树替换为叶结点后测试集精度提升，则剪枝。最后生成如图4.7的决策树，其测试集精度为71.4%。后剪枝欠拟合风险很小，泛化性能往往优于预剪枝，但时间开销大。

4.4　连续与缺失值

4.4.1　连续值处理

现实学习任务中属性取值不一定离散，可能为连续值。处理连续值最简单的策略是二分法。

给定样本集D和连续属性a，假定a在D上出现了n个不同取值，将这些值从小到大进行排序。基于划分点t将D分为子集$D^-_t$和$D^+_t$，前者包含在属性a上取值不大于t的样本，后者反之。对相邻的属性取值$a^i,a^{i+1}$来说，t在区间$[a^i,a^{i+1})$中取任意值所产生的划分结果相同。因此对连续属性a，考察包含n-1个元素的候选划分点集合

$$T_a=\{\frac{a^i+a^{i+1}}{2}|1\leq i\leq n-1\},　　　　　(4.7)$$

然后像考虑离散值一样考虑这些划分点

$$\begin{aligned} Gain(D,a)&=\max_{t\in T_a}Gain(D,a,t)\\ &=\max_{t\in T_a}Ent(D)-\sum_{\lambda\in\{-,+\}}\frac{|D^\lambda_t|}{|D|}Ent(D^\lambda_t),　　　　　(4.8) \end{aligned}$$

例如，在表4.1的数据集上增加两个连续属性得到表4.3，来生成一棵决策树。对属性”密度”，由式(4.8)计算出信息增益0.262，对应于划分点0.381。对属性”含糖率”，计算出信息增益0.349，对应于划分点0.126。

与离散属性不同的是，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

4.4.2　缺失值处理

现实学习任务中可能遇到样本的某些属性值缺失，如表4.4。

此时面临两个问题：(1)如何在属性值缺失的情况下进行划分属性选择。(2)给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分。

给定训练集D和属性a，令$\tilde{D}$表示D中在属性a上没有缺失值的样本子集。对问题(1)，仅可根据$\tilde{D}$来判断属性a的优劣。假定属性a有V个可取值，令$\tilde{D}^v$表示$\tilde{D}$在属性a上取值为$a^v$的样本子集，$\tilde{D}k$表示$\tilde{D}$中属于第k类的样本子集，显然有$\tilde{D}=\bigcup^{|y|}{k=1}\tilde{D}k,\tilde{D}=\bigcup^V{v=1}\tilde{D}^v$。假定为每个样本x赋予一个权重$w_x$，并定义

$$\rho=\frac{\sum_{x\in\tilde{D}}w_x}{\sum_{x\in D}w_x},　　　　　(4.9)\\ \tilde{p}_k=\frac{\sum_{x\in\tilde{D}_k}w_x}{\sum_{x\in\tilde{D}}w_x}(1\leq k\leq|y|),　　　　　(4.10)\\ \tilde{r}_v=\frac{\sum_{x\in\tilde{D}^v}w_x}{\sum_{x\in\tilde{D}}w_x}(1\leq v\leq V).　　　　　(4.11)$$

其中$\rho$表示无缺失值样本所占的比例，$\tilde{p}k$表示无缺失值样本中第k类所占的比例，$\tilde{r}^v$表示无缺失值样本中在属性a上取值$a^v$的样本所占的比例。显然，$\sum{k=1}^{|y|}\tilde{p}k=1,\sum{v=1}^V\tilde{r}_v=1$。

基于上述定义将式(4.2)推广为

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

其中由式(4.1)，有

$$Ent(\tilde{D})=-\sum_{k=1}^{|y|}\tilde{p}_k\log_2\tilde{p}_k.$$

对问题(2)，若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子结点，且样本权值保持不变。否则，将x同时划入所有子结点，样本权值在与属性值$a^v$对应的子结点中调整为$\tilde{r}_v\cdot w_x$。以表4.4的数据集为例生成了如图4.9所示的决策树。

4.5　多变量决策树

把每个属性视为坐标空间中的一个坐标轴，d个属性描述的样本对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树形成的分类边界有明显的轴平行(axis-parallel)特点。以表4.5为数据集，学得图4.10所示决策树，其分类边界如图4.11

但在学习任务的真实分类边界比较复杂时，如图4.12所示，时间开销会很大。

此时可如图4.12中红色线段所示使用斜的划分边界，即使用”多变量决策树”(multivariate decision tree)或”斜决策树”(oblique decision tree)。与传统的”单变量决策树”(univariate decision tree)不同，多变量决策树学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。例如对表4.5数据集，可学得图4.13的多变量决策树，其分类边界如图4.14.