决策树的启发函数¶

决策树的启发函数，这是决策树进行分枝的依据。本文介绍了 ID3、C4.5 和 CART 三种启发函数。

当我们依据某个变量的取值来决定下一步怎么做时，我们就是在使用决策树。

决策树作为最基础、最常见的有监督学习模型，常被用于分类问题和回归问题，在市场营销和生物医药等领域尤其受欢迎，主要因为树形结构与销售、诊断等场景下的决策过程十分相似。

如何构造决策树？从若干不同的决策树中选取最优的决策树是一个 NP 完全问题 (1)。

*[ID3]: Iterative Dichotomiser 3

首先需要了解经验熵（Entropy）的概念：

\[ H(D) = -\sum_{k=1}^{K} p(k) \log_2 p(k) \]

对上式的理解是：数据集\(D\)有\(K\)种取值，\(p(k)\)表示第\(k\)种取值在数据集\(D\)中的概率。经验熵可以用于衡量变量的混乱程度：经验熵越大，则变量的取值越混乱。

经验条件熵是给定某个特征时的经验熵：

\[ H(D|A) = \sum_{i=1}^{n}\frac{|D_i|}{|D|} H(D_i) \]

对上式的理解是：特征\(A\)有\(n\)种取值，\(\frac{|D_i|}{|D|}\)表示第\(i\)种取值在特征\(A\)中的概率。\(H(D_i)\)表示：当特征\(A\)的取值为\(D_i\)时的那部分数据集的经验熵。

由于经验条件熵是根据特征\(A\)对全样本进行了一次划分，而划分后的样本一般会变得更有序，所以经验条件熵总是比经验熵小。

于是，将经验熵减去经验条件熵，就得到了信息增益：

\[ g(D, A) = H(D) - H(D|A) \]

ID3 算法就是要找到某个特征，使得信息增益最大。

*[C4.5]: 据说这一算法最初是用 C 语言实现的，作者很自豪地将 C 语言作为算法名。4.5 则代表了软件的版本。

经验熵衡量了数据集标签的无序程度。同样地，我们也可以用取值熵来衡量数据集特征的无序程度。

\[ H_A(D) = -\sum_{i=1}^{n} \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|} \]

特征\(A\)对数据集\(D\)的信息增益比定义如下，也就是用信息增益除以特征的取值熵。

\[ g_{R}(D, A) = \frac{g(D, A)}{H_A(D)} \]

直觉理解：如果只用信息增益来判断特征是否对标签进行了有效的分类（即熵减的能力很强），那么，那些本身就有很多取值的特征更容易对标签进行正确的分类。C4.5 算法通过除以特征的取值熵来对那些本身就有很多取值的特征进行惩罚，提升决策树的泛化能力。

例如，如果我们拥有一个人的 DNA 信息，那么我们几乎可以非常准确地预测出它的性别、肤色、是否患有某种先天性疾病等。在准确的（或者说，纯的）分类后，经验条件熵几乎为 0，也就是能够得到很大的信息增益。这样的分类会得到一颗庞大且深度很浅的决策树，这是很不合理的。

*[CART]: Classification and Regression Tree，分类回归树。

基尼指数也被用于描述数据的混乱程度：

\[ Gini(D)=1-\sum_{k=1}^{K}p(k)^2 \]

特征\(A\)的基尼指数为：

\[ Gini(D|A)=\sum_{i=1}^{n} \frac{|D_i|}{|D|}Gini(D_i) \]

CART 通过选择使基尼指数最小的特征及其对应的切分点进行分类。

例如，特征\(A\)一共有 3 个取值，分别是“高”、“中”和“低”。并且 CART 给出的最优切分点是“特征\(A\)=高”，那么这个二叉树节点就是判断“特征\(A\)是否为高”。

与 ID3 和 C4.5 不同的是，CART 是一颗二叉树。ID3 和 C4.5 可以在每个节点上产生出多叉分支，且每个特征在层级之间不会复用，而 CART 中的每个结点只会产生两个分支，最后会形成一颗二叉树，且每个特征可以被重复使用。

评论