决策树生成算法

关于决策树,想必大部分人都已经耳熟能详了,这是一种用来预测行为的树状分叉结构。本文主要想总结一下最常用的决策树生成算法:ID3C4.5 以及 CART

构造的原则

熟悉决策树的你一定记得,决策树每个非叶子结点对应的其实是一个属性。比方说,想判断一个男生是不是 gay,我们首先需要判断他的性别是不是男的,是的话继续判断他的性取向,之后继续判断他的其他行为……这里的「性别」,「性取向」就是属性,而决策树的生成其实是依次挑选这些属性组成自己的节点,到最终可以明确得出结论的时候(也就是叶子结点),整棵树便生成了。所以,我们的目标就是按照某种方法依次挑选出这些属性。

我们挑选的原则是:每次选出这个属性后,可以最大限度地减小分类的可能性。回到 gay 这个问题,如果摆在我们眼前的属性有:「性取向」,「是否喜欢日漫」,「是否长发披肩」,那么,选择「性取向」这个属性,对我们之后的判断,帮助无疑是最大的。因为得知「性取向」之后,基本也就得到结论了。所以,对这个例子而言,「性取向」是我们优先挑选的属性。

那么,我们如何衡量这种帮助的大小呢?请往下看👇。

ID3 算法

ID3 算法归根到底就是提出一种合理的选择属性的方法。

(注意,决策树是一种知识学习算法,只有从众多样本中才能得出哪个属性最好,所以,构造决策树的前提是有大量的样本可供学习)

下面,为了方便讲解,我们需要引入信息学中「熵」的概念🙈。

熵(entropy)

第一次接触熵的概念是在学高中化学的时候,课本告诉我们:一堆整齐有序的分子,最终都会演变成一个混乱复杂的群体,也就是,这个系统的熵值会逐渐变大。因此,简单整齐的系统,熵越小,越混乱的系统,熵越大。接下来,让我们回顾一下分子的布朗运动……

开个玩笑啦🤗。

同化学里的熵一样,信息学的熵也有类似的作用。在信息学中,如果熵越大,证明掌握的信息越少,事情越不确定。看到这里,你有没有觉得,熵的定义和我们前面提出的挑选属性的原则有点类似。是的,ID3 的精髓也就是在这,它通过计算属性的熵,来得出一个属性对事情的确定性能产生多大的影响,从而选出最好的属性。

那么熵该如何度量呢?

著名的信息论创始人「香农」提出一个度量熵的方法:假设有一堆样本 D,那么 D 的熵可以这样计算: \[ H(D)=-\sum_{i=1}^{m}{p_ilog_2(p_i)} \] 其中,\(p_i\) 表示第 i 个类别在整个样本中出现的概率。 举个例子吧。假设我们投掷 10 枚硬币,其中,5 枚正面朝上,5 枚正面朝下,那么我们总共得到 10 个样本,这堆样本的熵为:

\(H(D)=-(\frac{5}{10}log_2{\frac{5}{10}} + \frac{5}{10}log_2{\frac{5}{10}})=1\)

反之,如果只有 1 枚硬币正面朝上,9 枚硬币正面朝下,那么熵为:

\(H(D)=-(\frac{1}{10}log_2{\frac{1}{10}} + \frac{9}{10}log_2{\frac{9}{10}})=0.469\)

如果全部硬币正面朝上,你应该可以算出来,熵为 0。 举这个例子是想说明:当熵的值越大的时候,事情会更加难以确定,如果你知道 10 次实验中,正面朝上的为 5 次,朝下的也为 5 次,那么下一次哪一面朝上,你是不是很难确定。相反,如果熵的值越小,事情就越明朗。当熵为 0,也就是 10 次都正面朝上的时候,下一次你会不会觉得正面朝上的概率会大很多(请忘掉你的传统思维,我没说这是一枚正常的硬币)。

选择属性

好了,有了熵的概念以及度量方法,下面我们可以正式地走一遍 ID3 的流程了。 同样的,假设我们有一堆数据 D,我们先计算出这堆样本的熵\(H(D)\),接下来,我们要对每个属性对信息的价值进行评估。假设我们挑选出 A 属性,那么,根据 A 属性的类别,我们可以把这堆样本分成几个子样本,每个子样本都对应 A 属性中的一类。我们继续按照熵的定义计算这几个子样本的熵,由于它们的熵是挑选出 A 后剩下的,因此我们定义为: \[ Remainder(A)=\sum_{j=1}^{v}\frac{|D_j|}{|D|}H(D_j) \] 这个公式其实和之前的是一个道理,我们通过 A 将 D 分成几个子集 \(D_j\),这个时候,我们仍然需要计算这堆样本的熵,因此,先分别计算出每个 \(D_j\) 的熵,然后乘以这个 \(D_j\) 样本占所有数据集的比重,最后将全部子集的熵加起来即可。前面说了,这个熵是挑选 A 后剩下的,那么很自然的,我们想知道 A 到底帮助消减了多少熵,于是,我们定义最后一个公式,即信息增益\[ Gain(A)=H(D)-Remainder(A) \] 之前对熵的说明告诉我们,熵越大,信息越少,反之,信息越多。\(Gain(A)\)其实就是 A 对信息的确定作用,它是我们选出 A 属性后,信息的混乱程度减少的量。 好了,到这里,ID3 的关键部分已经讲完了。其实,每次挑选属性的时候,我们都是计算出所有属性的信息增益,选择最大的作为分裂的属性,将样本分成几个子集,然后,对每个子集,继续选出最好的属性,继续分裂,直到所有样本都属于同一类为止(都是 gay 或者都是正面朝上)

举个例子

下面用的这个例子摘自文末的参考博客算法杂货铺——分类算法之决策树(Decision tree)。 假设我们有以下这堆 SNS 社区的资料,我们想确定一个账号是否是真实。 example 其中,s 、m 和 l 分别表示小、中和大。 我们先计算出这堆样本的熵:

\(H(D)=-(0.7*log_2{0.7}+0.3*log_2{0.3}) = 0.879\)

然后,我们计算每个属性的信息增益:

\[ \begin{align} Remainder(L)=&0.3*(-\frac{0}{3}log_2{0}{3}-\frac{3}{3}log_2{\frac{3}{3}})\\&+0.4*(-\frac{1}{4}log_2\frac{1}{4}-\frac{3}{4}log_2\frac{3}{4})\\&+0.3*(-\frac{1}{3}log_2\frac{1}{3})=0.603 \end{align} \]

\[ Gain(L)=0.879-0.603=0.276 \]

同样的道理:

\[Gain(F)=0.553\]

\[Gain(H)=0.033\]

经过比较,我们发现 F 的增益最高,于是选出 F 作为节点,构造出如下决策树:

注意,F 属性有三个类别,对应三个分支,其中,l 和 m 两个分支的数据都是同一类(账号真实性要么都是 no 要么都是 yes),因此这两个分支没法再分了,而 s 属性的分支,剩下一个四个样本的子集,我们之后的任务,是对这个子集继续分割,直到没法再分为止。 接下来要考虑 L 和 H 属性,同样的道理,我们继续计算增益,只不过这一次我们是在这个子集上计算。

\[H(D)=-(\frac{3}{4}*log_2{\frac{3}{4}}+\frac{1}{4}*log_2{\frac{1}{4}})=0.811\]

\[Remainder(L)=\frac{1}{2}*(0)+\frac{1}{2}(-\frac{1}{2}log_2{\frac{1}{2}}-\frac{1}{2}log_2{\frac{1}{2}})=0.5\]

\[Remainder(H)=\frac{3}{4}*[-\frac{2}{3}log_2(\frac{2}{3})-\frac{1}{3}log_2(\frac{1}{3})]+\frac{1}{4}*0=0.689\]

\[Gain(L)=0.811-0.5=0.311\]

\[Gain(H)=0.811-0.689=0.122\]

这一次,我们选择 L 属性进行分裂:

剩下的只有 H 属性,因此最后加上 H 节点。由于剩下的样本中只有 H=no 的数据,因此 yes 节点的数据没法判断(这种情况在数据量很大的时候一般不会遇到,因为数据量越大,涵盖的情况会更多),而剩下的两个样本存在 yes 和 no 两种情况,因此 no 节点往下也只能随机选择一种类别进行判断(这种情况一般是根据进行「多数表决」,即选择出现次数最多的类别作为最终类别,在数据量很大的情况下,出现次数一样多的情况几乎不会发生)。

属性为连续值的情况

上面给出的例子中,样本的特征都是离散值(e.g. s,m,l),而 ID3 算法确实也只对离散值起作用。如果遇到特征为连续值的情况,一般需要先将其离散化,例如:可以选定几个阈值\(a_1\)\(a_2\)\(a_3\)\(a_1\)<\(a_2\)<\(a_3\)),根据这些阈值,将样本特征分为四类:\(f < a_1\)\(a_1 < f < a_2\)\(a_2 < f < a_3\)\(f > a_3\)。然后,便可以按照一般的思路构建决策树了。

C4.5算法

C4.5 算法主要对 ID3 进行了改进,用「增益率」来衡量属性的信息增益效率。算法中定义了「分裂信息」:

\(SplitInfo(A)=-\sum_{j=1}^{v}{\frac{|D_j|}{|D|}log_2{\frac{|D_j|}{|D|}}}\)

然后,通过该信息,定义增益率公式为:

\(GainRatio(A)=\frac{Gain(A)}{SplitInfo(A)}\)

C4.5选择具有最大「增益率」的属性作为分裂属性,而其余步骤,和 ID3 完全一致。

CART

CART 指的是分类回归树(Classification And Regression Tree)。顾名思义,这是一棵既可以用于分类,也可以用于回归的树。不同于上面的两种树,CART 每一个非叶子节点只有有两个分支,所以 CART 是一棵二叉树。下面我们按照分类和回归两个用途分别介绍 CART 的构建。

分类树的生成

CART 在选择分裂节点的时候,用「基尼指数(Gini)」来挑选最合适的特征进行分裂。所谓「基尼指数」,其实和 ID3 中熵的作用类似。假设我们有一个数据集 D,其中包含 N 个类别,那么「基尼指数」为: \[ Gini(D) = 1 - \sum_{j=1}^{N}{P_j^2} \] 其中,\(P_j\)表示每个类别出现的概率。 同熵一样,「基尼系数」的值越小,样本越纯,分类越容易。 我们根据 Gini 选择一个最合适的特征作为 CART 的分裂节点。注意,与 ID3 不同的是,如果特征的类别超过两类,CART 不会根据特征的所有类别分出子树,而是选择其中的一个类别,根据是否属于这个类别分成两棵子树。假设 A 特征中有三种类别(s、m、l),我们需要分别按照「是否属于 s 」、「是否属于 m 」、「是否属于 l 」将样本分为两类,根据 Gini 值最小的情况挑选出分裂的特征类别(比如:按照「是否属于 s 」将样本分为两类)。对于分裂后的样本的 Gini 值,我们按照如下公式计算: \[ Gini(D, A) = \sum_{j}^{k}{\frac{|D_j|}{|D|}} \] 其中,k 表示分裂的子集数目。事实上,在 CART 中,k 的取值为 2。 然后,选择 \(Gini(D, A)\) 最小的特征 A 作为分裂的特征即可。 这里还需要注意一点,在 ID3 中,已经选择过的特征是没法在之后的节点分裂中被选上的,即每个特征只能被挑选一次。但 CART 没有这种限制,每次都是将所有特征放在一起,通过「基尼系数」选出最好的,哪怕这个特征已经在之前被挑选过了。有学者认为,ID3 这种只挑选一次的做法容易导致 overfitting 问题,所以相信 CART 的这种做法能使模型的泛化能力更强。 CART 按照这样的方式,不断挑选特征分裂子数,直到剩下的子样本都属于同一类别,或者特征没法再分为止,这个停止条件可以参考 ID3 ,这里就不再举例说明了。

回归树的生成

回归树相对来说比较难理解,我自己也花了较长时间咀嚼,其中还有一些不明白的地方,日后有了新的想法会继续补充修正。 为了更好地说明回归树的构建流程,我们假设有以下训练数据:

\(X\) \(Y\)
(\(x_{11}\)\(x_{12}\)\(x_{13}\)) \(y_1\)
(\(x_{21}\)\(x_{22}\)\(x_{23}\)) \(y_2\)
(\(x_{31}\)\(x_{32}\)\(x_{33}\)) \(y_3\)

上面的表中一共有三个样本,每个样本有三个特征,为了解说方便,我们分别命名为特征 1、特征 2、特征 3(比如:\(x_{11}\)\(x_{21}\)\(x_{31}\) 就属于特征 1)。 <br> 与分类树类似,回归树每次也需要从样本 \(X\) 选取特征,并根据特征值将数据集切分为两份。在分类树中,我们是用「熵」或者「基尼系数」来确定分裂特征,但回归树中的 \(X\)\(Y\) 都是连续值,因此需要采用新的特征挑选方式。 <br> 首先,我们先简单明确一下回归树的分裂原则:每次分裂后,每个样本集合内的数据要尽可能相似。这一点与分类树是不谋而合的,尽可能相似就是说,类别上要尽量统一。而为了做到这一点,最常用的方法便是「最小二乘法」。下面,我们定义「最小二乘法」的代价函数(可以简单认为就是回归树的信息熵):

\[ \min_{j,s}[\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] \]

其中,

  • \(j\) 表示样本的特征,上面例子中的 \(x_{11}\)\(x_{21}\) 就属于同一个特征。
  • \(s\) 表示特征的分裂值,如果 \(s=x_{11}\),就表示所有样本以特征 1 为基准,按照 \(>=x_{11}\)\(<x_{11}\) 分为两类。
  • \(R_1\) 表示分裂后的第一个样本集,\(R_2\) 表示分裂后的第二个样本集。
  • \(c_1\)\(c_2\) 分别表示 \(R_1\)\(R_2\) 的固定输出值。简单点说,它们是最能代表 \(R_1\)\(R_2\) 内所有样本的值。

如果我们进一步对 \(\sum_{x_i\ \in\ {R_1\ (j,s)}}{(y_i-c_1)}^2\) 求导的话,就会发现,要使这个式子最小,\(c\) 必须取 \(y_i\) 的平均值( \(y_i \in R\) )。因此,我们对原公式进行简化: \[ \min_{j,s}[\sum_{x_i\ \in\ {R_1\ (j,s)}}{(y_i-c_1)}^2+\sum_{x_i\ \in\ {R_2\ (j,s)}}{(y_i-c_2)}^2] \] 其中,\(c_1\)\(c_2\) 分别是 \(R_1\)\(R_2\) 两个集合中 \(y\) 的平均值。

(希望上面对符号的说明能减少读者对公式的畏惧🤒)

这个公式的做法其实很简单,就是枚举所有特征以及特征值,挑选出最好的特征以及特征值作为分裂点,将样本分为两部分,其中,每一部分内的样本值 \(y\) 的平方差最小。平方差最小,意味着这个样本内的数据是最相近的,可以认为属于同一类。

至此,回归树的精髓部分就介绍完了。下面顺藤摸瓜讲一下回归树的构建过程。

最小二乘回归树生成算法:

  1. 依次遍历每个特征 j,根据所有样本中特征 j 的取值 s,我们按照上面的公式计算代价函数,这样便可以得到每对 ( \(j\)\(s\) ) 的代价函数,我们选择函数值最小的作为切分点;
  2. 使用上一步的切分点将数据分为两份;
  3. 重复第 1、2 步,直到样本的平方差小于阈值或样本数目小于阈值为止。此时,叶子节点的数据就是该样本空间 \(R_m\) 的平均值 \(c_m\)
  4. 根据第 3 步构造的各个样本空间 \(R_m\),生成回归树。

在本文参考的博文 CART之回归树构建内有一个构建回归树的简单例子,虽然计算方式略有不同,但和本文陈述的方法应该大同小异,我这里偷个懒,就不再举例了😝。

参考