决策树系列0:你需要一棵决策树

关于决策树

决策树是非常流行的一种机器学习算法,基于决策树的集成算法随机森林更是位于机器学习 Top10 的算法之一。决策树之所以备受推崇,很大一个原因是其实现的过程与人类思考问题的方式非常接近,即使没有任何机器学习基础的人也可以看懂决策树做出判断的过程:

相关概念

决策树的概念来自自然界中的树,树有分支、叶子、根和树干;决策树的节点根据选定的属性进行分裂,形成分支,这些分支上的节点是上一层节点的子节点,如果某节点不存在子节点(即不再向下延伸),那么这个节点就是叶子节点。每个决策树都有一个根节点(root),和树的跟一样,这是一棵决策树开始生长的起点。

种一棵决策树

决策树的生长意味着对数据空间的不断分割,每个叶子节点都对应于空间中的某一部分,将所有叶子节点对应的空间相加就是原来的数据空间,以二维数据空间为例,\(X\in \mathbf{X}\),有两个维度的特征,每一次我们都选择其中一个特征进行分割,这个过程我们可以用下图形象地表示出来:

上图中叶子节点是 \(X_3,X_5,X_6,X_7,X_8\) ,这些叶子节点对应的子空间之和即为原始数据空间。在二维空间里似乎几何分割更加直观,但是我们几乎不可能画出更高维空间的分割方法,对于决策树来说,高维空间和低维空间的分割的过程大同小异,无非是再增添一些节点,让树生长的更为茂盛罢了。

构造一颗决策树需要解决四个问题:

  1. 选择什么特征进行分裂?如何给定分裂的临界值?
  2. 如何评估分类的效果?
  3. 分裂到什么时候停止?
  4. 每个叶子节点都有一个对应的分类结果,怎么给?

我们来看看这些问题该如何解决:

  • 选择分裂特征和分裂值

假设我们输入的的数据 \(\mathbf{x}=[x_1,x_2…x_n]^T\) ,其中既有连续变量又有离散变量,以 CART 树为例,对于连续变量 \(x_i\),我们会选定一个判定值 \(c\),当 \(x_i^{(j)}\leqslant c\) 时,该样本进入左边的子节点,否则进入右边的子节点(CART 树做二元分类),连续变量的取值虽然是无穷的,但是训练的数据是有限的,如果训练集的数量是 \(m\),那么临界值 \(c\) 最多只有 \(m\) 种选择(考虑所有样本不能落入同一个子节点的话就是 \(m-1\) 种),其中一种处理思路是,依次取 \(c\in \{x_i^{(1)}, x_i^{(2)}, x_i^{(3)}...x_i^{(m)}\}\) ,选择分类效果最好的一种作为当前节点的分裂值。

对于离散变量 \(x_j\),它的取值范围必然是有限的,假设共有 M 个不同的类别,进行分裂时,我们会给定一个 子集\(A\subset \{1,2,3…M\}\) ,如果 \(x_j^{(i)}\in c\) 进入左边的子节点,反之进入右边的子节点,同样我们会遍历所有子集 \(A\),并从中选择效果最好的一个作为分裂值 。

通过上面的过程,我们完成了当前节点其中一个特征作为分裂变量的评估,并确定了该特征对应的最佳分裂点,最终我们还需要对所有属性的最佳分裂点进行评估,从中选出其中效果最好的属性作为分裂变量,该属性的分裂值即为当前节点的最佳分裂值。用伪代码的形式表达这个流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
初始化 当前最佳分类效果,当前最佳分裂特征和当前最佳分裂值;
for(i = 0;i < 特征数量; ++i){
选择待评估的特征 x_i;
if (x_i 是连续变量){
找出最佳分裂值 c;
计算选择 x_i 进行分裂的对应的最佳效果 E_i;
}
else{
找出最佳分裂集合 A;
计算选择 x_i 进行分裂的对应的最佳效果 E_i;
}
if (E_i > 当前最佳分类效果){
当前最佳分类效果 = E_i;
当前最佳分裂特征 = x_i;
当前最佳分裂值 = c 或 A;
}
}
  • 评估分裂效果

我们需要一个能定量评估分类效果的函数 \(\phi\) ,通常把它叫做不纯度函数(Impurity Function),顾名思义,一个节点中样本类型越多不纯度越高。我们的目的是要获得尽可能小的不纯度,即每一次分裂都让不纯度降低。假设数据总共有 \(K\) 个类型,对于当前节点 \(t\) ,类型为 \(k\) 的数据所占比例为 \(p(k|t)\) ,容易推得 \(\sum_{k=1}^Kp(k|t)=1\)

不纯度函数可以有很多选择,但都必须遵循以下原则:

  1. 节点中各类型的数据均匀分布时,不纯度最高,即 \(p(k|t)=1/K,(k=1,2…K)\) 时,\(\phi\) 达到最大;
  2. 节点中只有一种类型的数据时,不纯度最低,即 \(p(k|t)=1,p(i|t)=0,(i=0,1…k-1,k+1…K)\) 时,\(\phi\) 达到最小;
  3. \(\phi\) 对于 \(p\) 是对称的,即任意对调 \(p(i|t)\)\(p(j|t)\) 的值,\(\phi\) 不变;

给定不纯度函数 \(\phi\) 后,我们用 \(i(t)\) 来表示节点 \(t\) 的不纯度: \[ i(t)=\phi(p(1|t), p(2|t)...p(K|t)) \] 有了节点的不纯度之后,我们就可以定量评估对于节点 \(t\),分裂 \(s\) (表示具体的分裂属性和分裂值)的效果 \(\Phi(s,t)\)\[ \Phi(s,t)=i(t)-p_Ri(t_R)-p_Li(t_L) \] 其中, \(p_R, p_L\) 分别表示节点 \(t\) 中的数据落入右边子节点和左边的子节点的概率,\(i(t_R), i(t_L)\) 则为子节点的不纯度,显然 \(\Phi(s,t)\) 表示的是,经过分裂之后,子节点的不纯度总和相对于父节点来说降低了多少,这个值越大表示这次分裂的效果越好。

最后我们再定义树的不纯度 \(I(T)\)\[ I(T)=\sum_{t\in \widetilde{T}}i(t)p(t) \] 注意上式只对所有的叶子节点 \(\widetilde{T}\) 进行求和,\(p(t)\) 可以用进入叶子节点 \(t\) 中的样本数量除以样本总量求得。

最后的最后给出三个常用的不纯度函数:

  1. 信息熵函数(Entropy Function):\(\sum_{j=1}^{K}p_j \text{ log }\frac{1}{p_j}\)
  2. 错误分类率(Misclassification Rate):\(1 - \mathbf{max}_j p_j\)
  3. 基尼指数(Gini Index):\(\sum_{j=1}^{K}p_j (1-p_j)=1-\sum_{j=1}^{K}p_{j}^{2}\)

读者可以尝试证明一下这三个不纯度函数是否满足我们之前所说的三个原则。

  • 给叶子节点赋值

所有的叶子节点最后都要给出一个答案,即落入这个叶子节点的数据应该属于哪一类?赋值方式是相当简单粗暴的,少数服从多数,占多数的类即为该叶子节点的分类结果。

  • 什么时候停止分裂

这取决于我们的不纯度函数和种树的策略,可以证明如果以错误分类率作为不纯度函数,子节点的不纯度之和总是小于父节点(证明见最后),意味着分裂将进行到每个叶子节点只有一个样本时(分无可分),这会让我们的树变得非常庞大,引起严重的过拟合问题。一种处理方法是,设置一个不纯度降低的阈值,当某次分裂带来的不纯度减小小于这个值时,可以认为此次分裂效果并不理想,应当停止分裂,这种方法的缺点在于分裂的依据过于短视,当前效果平平的分裂很有可能对之后几步影响巨大;另一种较为常用的策略是,不限制树的生长,后期进行剪枝。

处理缺失值

决策树在处理缺失值时相比其他的算法有着天然的优势,一般来说有一下几种处理方法:

  1. 把「缺失」另做一类,或归到已有的一类中,即假设「缺失」也是对应特征的一个值;
  2. 根据概率分布到子节点中,有全部分配到最大概率子节点的,也可以根据各子节点中的数量按比例分配
  3. 替代分割法(surrogate split),当前节点的最佳分组是对于变量 \(s\) 时,如果数据中(训练或者测试数据)有个别条目缺失 \(s\) ,那么将通过其他变量进行一系列的分组,这些分组的结果非常接近 \(s\) 的最佳分组结果,从中选出最接近的分组方法来处理缺失 \(s\) 属性的条目。
  4. 计算不纯度时,基于该特征未缺失的样本进行计算,而对于有缺失的样本可以将其添加到该特征下的所有分类中

对于替代分割法,还需要说明一点,在寻找替代的分组时,不以不纯度减小作为准则,仅仅追求分类结果与目标分组最接近的(是对于当前节点分组最接近的还是所有衍生的子节点?)。替代分割法是最能体现决策树优势的一种处理缺失值的策略。

尽管如此,作为相关问题领域的专家,往往有对于缺失数据更为可靠的补全方法,如果你有更可靠的依据或方法去补全数据,还是不要太依赖决策树的自动补全。

剪枝预热

防止决策树过拟合有这几种方法:

  1. 停止准则:当某次分割的不纯度降低小于我们制定的标准时,该节点不再分裂;
  2. 剪枝:不限制树的生长,在树形成之后合并某些节点,即剪枝;
  3. 限定树的深度:当决策树层数达到限定的值深度时,停止生长;

停止准则最大的问题是视线过于短浅,有时候一次不是那么完美的分裂在当前看起来效果不好,但是可能给后续的继续分裂创造良好的基础。

实际的情况是,如果我们不限制树的大小,决策树总是倾向于尽可能长得大(层数多,叶子节点多),这带来的一个问题就是过拟合(可以证明父节点错分率必然大于子节点,决策树倾向于长大)。

在讲剪枝前(Pruning)先引入几个概念:

  • Descendant:派生节点,如果一个节点 \(t'\) 可以从另一个节点 \(t\) 沿着一条连续的路径向下派生出来,我们就说,\(t'\)\(t\) 的派生节点;
  • Ancestor:先祖节点,如果 \(t'\)\(t\) 的派生节点,那么反过来 \(t\) 就是 \(t'\) 的派生节点;
  • Branch:分支,如果 \(T_t\) 是树 \(T\) 的一个分支,那么 \(T_t\) 的根节点 \(t\) 以及 \(t\) 所包含的所有派生节点构成了这个分支 \(T_t\)
  • Pruning:剪枝的过程是从原来的树 \(T\) 中剪去一个分支 \(T_t\) ,这个过程会去掉 \(T_t\) 中的所有节点(除了 \(T_t\) 的根节点 \(t\)),可以用 \(T-T_t\) 来表示这个剪枝的过程;剪枝过后的树可以用 \(T'\) 来表示,用 \(T'<T\) 表示剪枝过后的树小于原来的树;

一个非常残酷的现实是,即使树 \(T\) 的规模并不是很大,其分支数量也是相当惊人的,穷举所有的分支进行判断并不可行,我们需要一种更为聪明的策略来进行剪枝,敬请期待决策树系列的下一篇文章:Minimal Cost-Complexity Pruning…

动手玩一玩

本文提供了一个决策树的代码(没有剪枝),👉戳这里,是基于 Programming Collective Intelligence 第七章的一个案例,你也可以看 Patrick L. Lê 写的一个详细的教程,他也提供了代码,先看一看再自己动手写一个完整的决策树代码,把代码和上面讲的对应起来,讲真对于加深理解很有帮助啊。

附证明:

\(R(t) \geq R(t_L) + R(t_R)\)

令节点 \(t\) 的多数类是 \(j^*\)

\[ \begin {align}p(j^* |t)& = p(j^*,t_L |t) + p(j^*,t_R |t) \\ & = p(j^*|t_L) p(t_L|t)+p(j^*|t_R) p(t_R|t) \\ & = p_Lp(j^*|t_L)+p_Rp(j^*|t_R) \\ & \le p_L\underset{j}{\text{ max }}p(j|t_L)+p_R\underset{j}{\text{ max }}p(j|t_R) \\ r(t)& = 1-p(j^*|t) \\ & \ge 1-\left[ p_L\underset{j}{\text{ max }}p(j|t_L)+p_R\underset{j}{\text{ max }}p(j|t_R) \right] \\ & = p_L(1-\underset{j}{\text{ max }}p(j|t_L))+p_R(1-\underset{j}{\text{ max }}p(j|t_R)) \\ & = p_Lr(t_L)+p_Rr(t_R) \\ R(t)& = p(t)r(t) \\ & \ge p(t)p_Lr(t_L)+p(t)p_Rr(t_R) \\ & = p(t_L)r(t_L)+p(t_R)r(t_R) \\ & = R(t_L)+R(t_R) \\ \end {align} \]

图一来自 IBM 素材库

图二来自蓝鲸的网站分析笔记

文末证明过程参考:https://onlinecourses.science.psu.edu/stat857/node/53