细语呢喃

技术改变生活

0%

『我爱机器学习』决策树

发表于 分类于 ， 阅读次数： 评论数：

本文将介绍一个简单常见的机器学习方法--决策树。包括但不限于：

  • ID3
  • C4.5
  • CART
  • 决策树剪枝

决策树简介

什么是决策树呢？下面的图来自西瓜书，这就是一棵决策树，这个决策树用来判断一个瓜是否位好瓜。

decision-tree-example

对于一个瓜，首先看其纹理，

  • 纹理模糊，说明是坏瓜
  • 纹理稍糊，还得看其触感，如果触感硬滑为好瓜，触感软粘为坏瓜
  • 纹理清晰，则接下来看根蒂....

可以看出，决策树是一个可解释性很强的模型，用数据结构里的树来描述的话，是一棵多叉树，其中间结点代表决策步骤，叶子结点代表决策结果（或者说类别标签），而从根结点到叶子结点则描述了我们决策的过程。

不过，如何训练决策树呢？给定训练数据，可能存在多棵能拟合数据的决策树，如果要求解全局最优的决策树，那么是一个NP问题，因此，我们往往采用贪心法建立次优决策树。

采用贪心法建立决策树的框架如下（采用分治法（Divide and conquer）递归的建树）：

decision-tree-algorithm

上图中，有2种情形使得递归返回，

  • 情形1：即代码2-4行，当前结点的样本都属于同一类别，无需划分，递归返回
  • 情形2：即代码5-7行，在当前属性集为空，或是所有样本在所有属性上取值都相同，无法进一步划分，所以返回

很简单是不是！我们只需要搞定第8行就可以了，如何选择最优划分属性呢？这就是不同贪心算法采用的不同策略了。

PS: 周志华的西瓜书中，认为第12行应该标记完然后return；我觉得是错误的。因为还有其它取值非空的\(D_v\)。因此这里我将图上的return去除了。

ID3与信息增益

一般而言，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度越来越高。而ID3中采用信息增益来衡量“纯度”的变化，从而选择划分点。

信息论与概率统计中，熵（Entropy）用来表示随机变量不确定性的大小，熵越大，不确定性越大。

设随机变量D有d个取值\(\{a_1,a_2,\cdots, a_d\}\), 取值取值为\(a_i\)的概率为\(p_i\), 则随机变量的熵定义为： \[ H(D) = -\sum_{i=1}^dp_i\log p_i\tag{2-1} \] 计算时约定当p = 0时，\(p_i\log p_i = 0\) 。因为熵只依赖于X的分布，所以可以将\(H(D)\)写为\(H(p)\)

应用在分类数据集中，\(p_i\)可以表示第i个类别占总样本的比重。

接着介绍条件熵（conditional entropy），即给定随机变量a后，D剩余的不确定性（熵）: \[ H(D|A)= \sum_{i=1}^dp(A=a_i)H(D|A=a_i)\tag{2-2} \] 看不懂条件熵的式子？其实就是按特征A的取值划分数据，对取值为\(a_i\)的数据计算熵，然后乘以取值为\(a_i\)的概率。

信息增益(information gain)描述的是，给定随机变量A后，X所减少的不确定性(即熵 - 条件熵)： \[ IG(D|A) = H(D) - H(D | A) \tag{2-3} \] 一般而言，信息增益越大，说明选择属性A来进行划分所获得的“纯度"提升越大。因此，著名的ID3决策树学习算法就是用信息增益来划分属性的。

例子

以周志华的西瓜书中西瓜数据2.0为例：

decision-tree-data-watermelon-2.0

该数据共有17条，我们可以用这个数据来学习一棵判断一个瓜是否为好瓜的决策树。

首先看好瓜出现了8次，坏瓜出现了9次，因此可以用式2-1计算出根结点的熵为： \[ H(D) =-\sum_{i=1}^2p_i\log p_i= - (\frac{8}{17}\log_2\frac{8}{17}+\frac{9}{17}\log_2\frac{9}{17}) = 0.998 \] 接着，查看可选取的特征有：{色泽、根蒂、敲声、纹理、脐部、触感}

先查看色泽特征，有三种取值，{青绿， 乌黑，浅白}，

  • 色泽为青绿的时候，有{1, 4, 6, 10, 13, 17} 6个样例，其中好瓜为{1,4,6}
  • 色泽为乌黑时有{2, 3, 7, 8, 9, 15} 6个样例，其中好瓜为{2,3,7,8}
  • 色泽为浅白时有{5, 11, 12, 14, 16} 5个样例，其中好瓜为{5}

因此我们用式子2-2计算条件熵： \[ \begin{align*} H(D | 色泽) &= \sum_{i=1}^3p(A=a_i)H(D|A=a_i) \\ &=p(A=青绿)H(D|A=青绿) +p(A=乌黑)H(D|A=乌黑)+p(A=浅白)H(D|A=浅白) \\ &=\frac{6}{17}\left( - (\frac{3}{6}\log_2\frac{3}{6} + \frac{3}{6}\log_2\frac{3}{6}) \right) + \frac{6}{17}\left( - (\frac{4}{6}\log_2\frac{4}{6} + \frac{2}{6}\log_2\frac{2}{6}) \right) + \frac{5}{17}\left( - (\frac{1}{5}\log_2\frac{1}{5} + \frac{4}{5}\log_2\frac{4}{5}) \right)\\ &=\frac{6}{17}*1.000 + \frac{6}{17}*0.918 + \frac{5}{17}*0.722\\ &= 0.8893 \end{align*} \] 最后用2-3计算给定了色泽特征的信息增益： \[ IG(D|色泽) = H(D) - H(D | 色泽) = 0.998-0.8893=0.109 \] 同理计算出其它特征的信息增益， \[ \begin{align*} &IG(D|根蒂) = 0.143；IG(D|敲声) =0.141\\ &IG(D|纹理) = 0.381；IG(D|脐部) =0.289\\ &IG(D|触感) = 0.006； \end{align*} \] 因为纹理的信息增益最大，所以会选纹理作为这次的划分特征。

根据前面讲的决策树算法框架，会将数据集根据纹理的取值划分，

  • 纹理清晰：{1, 2, 3, 4, 5, 6, 8, 10, 15}
  • 纹理稍糊: {7, 9, 13, 14, 17}
  • 纹理模糊: {11, 12, 16}

然后，建立递归的建立三棵子树，不过子树中就没有纹理特征了。

以纹理清晰的子树为例，有9个样例(设为\(D^1\)用来和原始数据进行区分)， \[ H(D^1) =-\sum_{i=1}^2p_i\log p_i= - (\frac{7}{9}\log_2\frac{7}{9}+\frac{2}{9}\log_2\frac{2}{9}) =0.7642 \] 可以用{色泽、根蒂、敲声、脐部、触感}这五个特征计算信息增益，来选择信息增益最大的特征，从而进一步划分。

这里继续以色泽特征的信息增益计算为例：{1, 2, 3, 4, 5, 6, 8, 10, 15} 有三种取值，{青绿， 乌黑，浅白}，

  • 色泽为青绿的时候，有{1, 4, 6, 10} 4个样例，其中好瓜为{1, 4, 6}
  • 色泽为乌黑时有{2, 3, 8, 15} 4个样例，其中好瓜为{2, 3, 8}
  • 色泽为浅白时有{5} 1个样例，其中好瓜为{5}

\[ \begin{align*} H(D^1 | 色泽) &= \sum_{i=1}^3p(A=a_i)H(D^1|A=a_i) \\ &=p(A=青绿)H(D^1|A=青绿) +p(A=乌黑)H(D^1|A=乌黑)+p(A=浅白)H(D^1|A=浅白) \\ &=\frac{4}{9}\left( - (\frac{3}{4}\log_2\frac{3}{4} + \frac{1}{4}\log_2\frac{1}{4}) \right) + \frac{4}{9}\left( - (\frac{3}{4}\log_2\frac{3}{4} + \frac{1}{4}\log_2\frac{1}{4}) \right) + \frac{1}{9}\left( - (\frac{1}{1}\log_2\frac{1}{1} + \frac{0}{1}\log_2\frac{0}{1}) \right)\\ &=\frac{4}{9}*0.8113 + \frac{4}{9}*0.8113 + \frac{1}{9}*0\\ &= 0.7215 \end{align*} \]

因此信息增益为: \[ IG(D^1|色泽) = H(D^1) - H(D^1 | 色泽) = 0.7642-0.7215=0.043 \] 类似可以算出其它的信息增益，然后选最大进行划分。

最终的决策树即为本文一开始给出的图，这里再贴出来方便读者查看：

decision-tree-example

C4.5

ID3有一些不足的地方：

  • 选择分裂变量时会倾向于选择类别较多的变量
  • 只能处理类别变量，不能处理连续性变量（实数的）
  • 不能处理缺失值

下面来看看C4.5是如何改进的。

增益率

信息增益对可取值数目较多的特征有所偏好（你可以想象极端情况，只有一个取值的时候，信息增益为0），为减少这种偏好的影响，C4.5决策树算法采用增益率： \[ {\rm Gain\_ratio}(D|A) = \frac{IG(D|A)}{H(A)} \tag{3-1} \]

2-4只有分母是仿佛我们没见过的？其实就是特征A的熵，之前我们计算H(D)是按D的类别（好瓜、坏瓜），而H(A)则按A的取值来计算。

如以上面的样例数据，再次以色泽为例， \[ H(色泽) = -\sum_{i=1}^3p_i\log_2p_i = -(\frac{6}{17}\log_2\frac{6}{17} + \frac{6}{17}\log_2\frac{6}{17}+\frac{5}{17}\log_2\frac{5}{17}) = 1.580 \] 注意的是，增益率对可取值数目较少的特征有所偏好，因此C4.5并不是直接选取增益率最大的特征作为划分，而是先从候选特征中找出信息增益高于平均水平的特征，然后再从中选出增益率最高的。

连续变量处理

C4.5中，处理连续变量的方法是对连续变量离散化。

如我们有一个连续的特征A，共有n个不同的取值，将这些取值从小到大进行排序，得到： \(\{a_1,a_2,...,a_n\}\)

这样，可以在相邻的取值\(a^i\)和\(a^{i+1}\)中间点t处进行切分，将数据划分为两部分，一部分小于等于t，另一部分大于t。

可能的划分点有n-1种：\(t \in \{\frac{a_1 + a_2}{2},\frac{a_2 + a_3}{2},\cdots,\frac{a_{n-1} + a_n}{2} \}\)

这样，在n - 1个取值中选择最优划分点即可。

缺失值处理

在真实数据中，往往会遇到不完整的样本，即样本中某些特征式缺失的。那么要如何处理呢？

要处理缺失值，需要解决两个问题：

  1. 如何在属性值缺失的情况下进行划分属性选择？
  2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

给定训练数据集D和属性a，令\(\tilde{D}\)表示D中在属性a上没有缺失值的样本子集。对于问题1，我们尽可根据\(\tilde{D}\)来判断属性a的优劣，假定a有V个可取值\(\{a^1,a^2,\cdots,a^V\}\)，令\(\tilde{D}^v\)表示\(\tilde{D}\)中在属性a上取值为\(a^v\)的样本，\(\tilde{D}_k\)表示\(\tilde{D}\)中属于第k类的样本子集，则显然有\(\tilde{D} = \bigcup_{k=1}^K\tilde{D}_k = \bigcup_{v=1}^V\tilde{D}^v\)

假定我们为每个样本x赋予一个权重\(w_x\)，并定义 \[ \rho = \frac{\sum_{x \in \tilde{D}}w_x}{\sum_{x \in D}w_x}\\ \tilde{p}_k = \frac{\sum_{x \in \tilde{D}_k}w_x}{\sum_{x \in \tilde{D}}w_x}\\ \tilde{r}_v = \frac{\sum_{x \in \tilde{D}^v}w_x}{\sum_{x \in \tilde{D}}w_x} \] 直观上看，对属性a，

  • \(\rho\) 表示无缺失值样本所占的比例
  • \(\tilde{p}_k\)表示无缺失样本中第k类的比例
  • \(\tilde{r}_v\)表示无缺失样本在属性a上取值\(a^v\)的样本所占的比例

显然\(\sum_{k=1}^K\tilde{p}_k=1; \ \sum_{v=1}^V\tilde{r}_v =1\)

基于上述定义，可以将信息增益2-3推广为 \[ Gain(D, a) =\rho \times Gain(\tilde{D}, a) = \rho\times\left( H(\tilde{D}) - \sum_{v=1}^V\tilde{r}_vH(\tilde{D}^v)) \right)\\ H(\tilde{D^v})= -\sum_{k=1}^K \tilde{p}_k \log_2 \tilde{p}_k \] 其实上式和原来的差不多，只是计算熵和条件熵的时候，采用的是没有缺失的样本子集\(\tilde{D}\)，并且是加权的结果，然后最后信息增益乘以\(\tilde{D}\)占\(D\)的加权比重

对于问题2

  • 若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子结点。
  • 取值未知，则将x同时划入所有的子结点，且样本权值在属性值\(a^v\)对应的子结点调整为\(\tilde{r}_v \cdot w_x\)，即让同一个样本以不同的概率划入不同的子结点中

例子

下面的例子以西瓜数据2.0\(\alpha\)为例：

decision-tree-data-missing-value

学习开始时，根节点包含全部17个样本，各个样例的权值为1。以特征色泽为例，无缺失的有14个样本，其中，包含正例6个，负例8个。因此： \[ \begin{align*} H(\tilde{D^v}) &= -\sum_{k=2}^K \tilde{p}_k \log_2 \tilde{p}_k \\&= -(\frac{6}{14}\log_2\frac{6}{14}+\frac{8}{14}\log_2\frac{8}{14}) = 0.985 \end{align*} \] \(\tilde{D}^1,\tilde{D}^2,\tilde{D}^3\)分别表示特征色泽上取值为“青绿","乌黑”，以及“浅白”的样本子集，有： \[ \begin{align*} H(\tilde{D^1}) &= -(\frac{2}{4}\log_2\frac{2}{4}+\frac{2}{4}\log_2\frac{2}{4}) = 1.000\\ H(\tilde{D^2}) &= -(\frac{4}{6}\log_2\frac{4}{6}+\frac{2}{6}\log_2\frac{2}{6}) = 0.918\\ H(\tilde{D^3}) &= -(\frac{0}{4}\log_2\frac{0}{4}+\frac{4}{4}\log_2\frac{4}{4}) = 0.000 \end{align*} \] 因此，样本子集\(\tilde{D}\)上属性“色泽”的信息增益为 : \[ \begin{align*} Gain(D, a)& = \rho\times\left( H(\tilde{D}) - \sum_{v=1}^V\tilde{r}_vH(\tilde{D}^v)) \right)\\ &= \frac{14}{17} *\left(0.985 - (\frac{4}{14} * 1+\frac{6}{14} * 0.918+ \frac{4}{14}* 0) \right)\\ &= \frac{14}{17} * 0.306 \\ & = 0.252 \end{align*} \] 其它类别依次类推。最后发现纹理取得最大信息增益。

  • {1, 2, 3, 4, 5, 6, 15}进入纹理= 清晰分支
  • {7, 9, 13, 14, 17} 进入纹理= 稍糊分支
  • {11, 12, 16}进入纹理=模糊分支
  • 对于编号8的样本，它缺失，因此同时进入三个分支中，但权重分别调整为\(\frac{7}{15},\frac{5}{15},\frac{3}{15}\)，编号10同理。

CART算法

CART算法想必你也有所耳闻，其全称为classification and regression tree，即分类与回归树。从这个名字就可以发现它很强大，因为它可分类可回归！

CART基本上和之前的决策树算法框架相同，不过CART假设决策树为二叉树，左边分支为取值“是", 右边分支取值为”否“。此外，其划分的策略也不是信息增益或信息增益率。

分类树生成

对于分类问题，采用基尼指数（Gini index）来判断分界点。假设有K个类，属于第k个类的概率为\(p_k\)，则基尼指数为： \[ {\rm Gini(D)}= \sum_{k=1}^Kp_k(1-p_k) = 1 -\sum_{k=1}^Kp_k^2\tag{4-1} \] 基尼指数反应了从数据集中抽取两个样本，其类别不一致的概率。因此Gini(D)越小，则数据集的纯度越高。也可以说，Gini(D)越大表示了集合D的不确定性越大。因此，划分的时候我们采用的是基尼指数最小的属性作为划分属性。

若在特征A的条件下，样本D根据特征A的某一可能取值a被分割为\(D_1=\{(x,y) \in D|A(x) = a\},\ D_2=D-D_1\)，集合D的基尼指数定义为: \[ {\rm Gini(D, A)} = \frac{|D_1|}{|D|}{\rm Gini(D_1)} + \frac{|D_2|}{|D|}{\rm Gini(D_2)}\tag{4-2} \]

4-2是不是和条件熵2-2也很类似? 关于基尼指数和熵的关系可以看下图（图来自李航老师）：

gini-entropy-classification-error

可以看出二者非常接近，此外，我们可以在\(p_i=1\)对\(-\log p_i\)进行泰勒展开： \[ \begin{align*} f(p_i) &= -\log p_i\\ f(p_i') &= f(p_i) + f'(p_i)(p_i-1) = f(1) +f'(1) (p_i-1) = 1-p_i \end{align*} \] 带入信息熵得： \[ \sum_{i} p_i\log p_i \approx \sum_i p_i(1-p_i) \] 即基尼系数！虽说他们数值上接近，但是gini的计算相比熵要简单的多，所以会更加的高效。

对于分类树和ID3的算法基本上相同，不过CART是二叉树，因此不像之前按特征划分，而是按特征取值划分。

  1. 对于给定的结点数据集为D，对于每一个特征A，对其所有可能的取值a，根据样本点对A=a的测试为“是”或“否"将D分割成\(D_1,D_2\)两部分，利用4-2计算A=a的基尼系数，从中选取基尼系数最小的特征以及对应的切分点作为最优特征与最优切分点，从现结点生成两个子结点，将训练数据集分配到两个子结点中去。
  2. 类似之前的算法递归调用步骤1直到满足停止条件即可。

可以看出，CART由于每次都是二分裂（划分成两部分），不像ID3是多分裂的，因此也没有ID3的倾向于取值较多的变量的缺陷。

回归树生成

回归树采用平方误差最小化为准则。

如何做呢？选择第j个特征\(x^{(j)}\)和它的取值s，作为切分变量和切分点，并定义两个区域： \[ R_1(j,s) = \{x|x^{(j)} \le s\} \\ R_2(j,s) = \{x|x^{(j)} \gt s\} \] PS： 这里真实中一般不直接用取值s来作为切分点，而先把特征的取值排序\(\{v_1,v_2,\cdots,v_n\}\)，然后可能的阈值有：\(\{\frac{v_1 + v_2}{2},\frac{v_2 + v_3}{2},\cdots,\frac{v_{n-1} + v_n}{2} \}\)。这里和C4.5中处理连续变量的方法一样。

然后采用平方误差损失求解最优的切分特征j 和切分点s: \[ \min_{j, s} \left[ \min_{c_1} \sum_{x_i \in R_1(j, s)} (y_i -c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j, s)} (y_i -c_2)^2 \right ] \tag{4-3} \] 其中\(c_1,c_2\)为对应的R1,R2部分的均值。 \[ \hat c_m = {1\over N_m}\sum_{x_i\in R_m(j,s)}y_i , \quad x\in R_m , m=1,2 \] 根据划分的区域递归的继续进行划分，最后就得到了回归树。

回归树例子

假设数据的特征就一个（就不用比较各个特征了），数据如下：

x 1 2 3 4 5 6 7 8 9 10
y 5.56 5.70 5.91 6.40 6.80 7.05 8.90 8.70 9.00 9.05

可以考虑划分点{1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5}，以s = 1.5为例，此时对应的c1= 5.56, c2=7.50

这里开挂用python代码计算剩下的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import numpy as np

data = np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05])
for k in range(len(data) - 1):
    left = data[:k + 1]
    right = data[k + 1:]

    left_mean = left.mean()
    right_mean = right.mean()

    left_error = np.sum([(left_mean - x) ** 2 for x in left])
    right_error = np.sum([(right_mean - x) ** 2 for x in right])
    mean_error = (left_error + right_error)
    print(k + 1.5, left, right, 'mean_error={0:5.2f} c1={1:5.2f} c2={2:5.2f}'.format(mean_error, left_mean, right_mean))

"""
1.5 [ 5.56] [ 5.7   5.91  6.4   6.8   7.05  8.9   8.7   9.    9.05] mean_error=15.72 c1= 5.56 c2= 7.50
2.5 [ 5.56  5.7 ] [ 5.91  6.4   6.8   7.05  8.9   8.7   9.    9.05] mean_error=12.08 c1= 5.63 c2= 7.73
3.5 [ 5.56  5.7   5.91] [ 6.4   6.8   7.05  8.9   8.7   9.    9.05] mean_error= 8.37 c1= 5.72 c2= 7.99
4.5 [ 5.56  5.7   5.91  6.4 ] [ 6.8   7.05  8.9   8.7   9.    9.05] mean_error= 5.78 c1= 5.89 c2= 8.25
5.5 [ 5.56  5.7   5.91  6.4   6.8 ] [ 7.05  8.9   8.7   9.    9.05] mean_error= 3.91 c1= 6.07 c2= 8.54
6.5 [ 5.56  5.7   5.91  6.4   6.8   7.05] [ 8.9   8.7   9.    9.05] mean_error= 1.93 c1= 6.24 c2= 8.91
7.5 [ 5.56  5.7   5.91  6.4   6.8   7.05  8.9 ] [ 8.7   9.    9.05] mean_error= 8.01 c1= 6.62 c2= 8.92
8.5 [ 5.56  5.7   5.91  6.4   6.8   7.05  8.9   8.7 ] [ 9.    9.05] mean_error=11.74 c1= 6.88 c2= 9.03
9.5 [ 5.56  5.7   5.91  6.4   6.8   7.05  8.9   8.7   9.  ] [ 9.05] mean_error=15.74 c1= 7.11 c2= 9.05
"""

可以看出，选6.5的时候最小，因此选6.5作为划分点。因此得到回归树\(T_1\)为： \[ T_1(x) = \begin{cases} 6.24, & x\le 6.5 \\ 8.91, & x \gt 6.5 \\ \end{cases} \] 接下来对\(R_1\)和\(R_2\)区域做同样的操作直到达到终止条件即可。

假如树的深度多允许为2，则最后的回归树为

decision-tree-partition-space-example

PS: 使用下面的代码生成 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import numpy as np
from sklearn.tree import DecisionTreeRegressor

X = np.arange(1, 11).reshape(-1, 1)
y = np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05])

tree = DecisionTreeRegressor(max_depth=2).fit(X, y)
# import os     
# os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin/'
from sklearn.externals.six import StringIO  
from IPython.display import Image  
from sklearn.tree import export_graphviz
import pydotplus

dot_data = export_graphviz(tree, out_file=None,  
                filled=True, rounded=True,
                special_characters=True)

graph = pydotplus.graph_from_dot_data(dot_data)  
Image(graph.create_png())

回归树的空间划分

在上面的例子中，可以画出对应的回归为：

decision-tree-partition-space

对应的python代码为

1
2
3
4
5
6
7
8
9
import matplotlib.pyplot as plt
plt.figure()
plt.scatter(X, y, s=20, edgecolor="black", c="darkorange", label="data")
plt.plot(X, tree.predict(X), color="cornflowerblue", label="regression tree", linewidth=2)
plt.xlabel("X")
plt.ylabel("Y")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

可以看出，一个回归树对应着输入空间（特征空间）的一个划分以及在划分的单元上的输出值。上图就是对输入空间X的划分。假设已经将输入空间划分为K个单元\(R_1, R_2, \ldots, R_K\), 在每个单元\(R_k\)上有个固定的输出\(c_k\),则回归树可以表示为: \[ f(\mathbf{X}) = \sum_{k=1}^K c_k I(\mathbf{X} \in R_k) \tag{4-4} \] 式4-4就是回归树比较数学的表示方法。比如上面的例子，\(x\in (3.5,6.5]\)时值就是6.75。可以看出各个划分空间是不相交的。

当输入空间的划分确定时，可以用平方误差\(\sum_{x_i \in R_k}(y_i - f(x_i))^2\)来表示回归树对于训练数据的预测误差，显然，单元\(R_k\)上的\(c_k\)的k最优值是\(R_k\)上所有输入实例\(x_i\)对应的\(y_i\)的均值。

决策树剪枝

决策树的生成算法递归的产生决策树，直到满足终止条件位置。产生的决策树可能过于复杂，对训练数据分类准确，但是对未知样本可能准确性不高。换句话说，决策树算法容易过拟合。为了防止过拟合，可以通过剪枝算法来降低复杂度，减少过拟合的风险。

决策树剪枝算法的基本策略有”预剪枝“和”后剪枝“两种策略。基本思路是极小化损失函数。

  • 预剪枝即在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分当前结点，并标记为叶结点。
  • 后剪枝是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该节点对应的子树替换为叶子结点能带来决策树的泛化性能提升，则将该子树替换为叶子结点。

上面的泛化性能考察，就要求我们对数据集划分，比如划分一部分为训练集，另一部分为验证集。然后考察在验证集上的准确率。

因此，我们划分出新的数据如下表，双线上部分为训练集，双线下部分为验证集

decision-tree-data-watermelon-2.0-train-and-validation-data

如果不经过剪枝，训练出来的决策树如下：

decision-tree-example-no-pruning

假设采用信息增益作为划分依据，现在来看看预剪枝和后剪枝怎么做的。

预剪枝

在不剪枝的做法中，我们根据信息增益准则，选取信息增益最大的脐部特征来进行划分，并产生3个分支。

而在预剪枝的过程中，我们需要看用脐部进行划分是否能提升泛化性能。

  • 若不划分，根结点被标记为叶子结点，类别为最多的类别，即设为正例”好瓜"(这个训练集中正例=负例，因此随便选一类都可以)，则验证集的7个样本中有3个样本正确分类，因此，精度为3 / 7 * 100% = 42.9%
  • 进行划分，
    • 结点2，包含编号{1, 2, 3, 14} => 好瓜
    • 结点3，包含编号{6, 7, 15, 17} =>好瓜
    • 结点4，包含编号{10, 16} =>坏瓜
    • 在测试集中，根据脐部特征的取值到相应的结点上，如编号4的验证数据为“凹陷”就到2号结点上，为好瓜。以此类推有{4，5，8，11，12}5个样本分类正确，因此精度为5 / 7 * 100% = 71.4%
  • 因为划分后的精度(71.4%)比不划分的(42.9%)高，所以进行划分。

对之后的结点2，3，4是否划分采用类似的过程。最后的决策树如下图所示：

decision-tree-example-pre-pruning

这是一棵只有一层划分的决策树，称为“决策树桩” （decision stump）。

预剪枝使得很多分支都没有展开，降低了过拟合的风险，也降低了决策树训练和预测的开销。但可能导致欠拟合。

后剪枝

后剪枝是作用在完整的决策树上的，因此我们先训练出一棵完整的决策树（即该小节一开始给的图）。

可以看出，验证集有{4, 11, 12}三个数据划分对了，因此精度为3/7=42.9%。

现在进行剪枝，先考察结点6，包含训练集{7, 15}，验证集{8，9}，若不剪枝为42.9%，若剪枝，则标记为好瓜，精度提高到57.1%，因此剪枝。

然后考察结点5，包含训练集{6, 7, 15}，验证集{8, 9}，若剪枝，则标记为好瓜，剪枝前后都是57.1%。根据奥卡姆剃刀原则，应选择简单的模型，因此应该进行剪枝。但是为了画图的直观，这里采用不剪枝的保守策略。

然后对于结点2，包含训练集{1, 2, 3, 14} ，验证集{4，5，13}，若进行剪枝，则标记为好瓜，精度提升到71.4%，因此剪枝。

对结点3和结点1做同样剪枝判断处理，但是精度并不提高，因此保留：

最后的决策树如下：

decision-tree-example-post-pruning

小结

决策树的特点：

  • 需要较少的数据预处理
  • 支持类别特征
  • 容易对模型进行解释和实现

缺点：

  • 容易过拟合
  • 拟合能力有限

和其他的方法比较：

  1. Decision Tree 可以很好的处理 missing feature，这是他的天然特性，因为决策树的每个节点只依赖一个 feature，如果某个 feature 不存在，这颗树依然可以拿来做决策，只是少一些路径。像逻辑回归，SVM 就没这个好处。
  2. Decision Tree 可以很好的处理各种类型的 feature，也是天然特性，很好理解，同样逻辑回归和 SVM 没这样的天然特性。
  3. 对特征空间的 outlier 有鲁棒性，因为每个节点都是 x < 𝑇 的形式，至于大多少，小多少没有区别，outlier 不会有什么大的影响，同样逻辑回归和 SVM 没有这样的天然特性。
  4. 如果有不相关的 feature，没什么干扰，如果数据中有不相关的 feature，顶多这个 feature 不出现在树的节点里。逻辑回归和 SVM 没有这样的天然特性(但是有相应的补救措施，比如逻辑回归里的 L1 正则化)。
  5. 数据规模影响不大，因为我们对弱分类器的要求不高，作为弱分类器的决策树的深 度一般设的比较小，即使是大数据量，也可以方便处理。像 SVM 这种数据规模大的时候训练会比较麻烦。

参考资料

  • 《机器学习》 - 周志华
  • 《统计学习方法》 - 李航
  • 机器学习技法 - 林轩田
  • http://leijun00.github.io/2014/10/decision-tree-2/
  • https://cethik.vip/2016/09/21/machineCAST/
请我喝杯咖啡吧~