决策树算法简单实现

机器学习有数个最经典的算法模型，而决策树在这些算法中也能称作最经典之一。从符号主义盛行的上世纪八十年代，直到算法思想和算力都有所进步的今天，决策树因为其简单的逻辑和较好的效果，仍被众多学习者使用。

本文仅阐述练习项目中所用的决策树算法，参考了各类决策树算法（ID3, C4.5, CART)的部分内容，而各类决策树算法的详细类容和多算法结合的相关问题本文并不会太多涉及。实际上，上文所提到决策树算法并无本质差别，触类旁通并非难事。

决策树介绍

即使是不接触机器学习，决策树一词也并不少见。人在选择中，总是会做出一系列判断来辅助决策。

类似这种凭不同判断依据，将情况指向不同的决策的算法，被称为决策树。而所谓决策既可以为分类，也可为回归，可见决策树的适用面之广。

决策树基本训练算法

我所看过的每本参考资料中，所提到的决策树训练算法都大同小异，无非是用数据集对树中的每个节点选取某样特征、将数据集进行分裂，直至达到停止分裂的条件，便设定最后的节点为叶节点；当从根部分裂出的若干分支都停止在了叶节点时，我们就得到了所需的决策树。而使用该决策树进行判断时，我们仅需要依照每个非叶节点的指引，逐步靠近包含结果的叶节点即可。

下面是西瓜书中的决策树算法伪码，个人认为足够清晰明了。

训练算法本身是一种深度优先的递归过程，首先是简单的终止条件（同属一个分类、无剩余可用判断属性、可用判断属性全相同），然后是寻找最佳分割点（第8行是整个算法的核心，将会在后文详细解说），最后是对于不同的分类情况选择继续递归创建新节点或是使其称为叶节点。

而在另一本资料中，提出了算法实现中几大需要解决的重要问题：

1. 特征向量有多个分量，每个决策节点上应该选择哪个分量做判断？
2. 选定一个特征后，判定的规则是什么？
3. 何时停止分裂，将该节点设置为叶节点？
4. 以什么为依据为叶节点赋值？

本文并非教材，也不会像教材那样细致的讲解思考过程。下面给出我所理解的一份答卷：

1. 对每个特征都进行尝试性的分割，用某种指标判断划分优劣，并选择最优秀的划分方式。
2. 我的项目中只考虑了离散和连续两类特征，将在下文分别提到划分方法。
3. 正如伪码所示，当某个节点的训练集都为同一分类时、当某个节点可用以分类的特征为空时、当某个节点划分的收益过低时，我们都会结束分裂。运用决策树剪枝方法后，可能还会有其他判断依据。
4. 多数情况下，分类问题都是选取叶节点的样本中数量最多的那个分类作为节点的值，而对于回归问题，可以选择用样本的均值等统计量作为叶节点的值。

决策树划分选择

前文提到，寻找最佳分裂点是算法的核心，而本文所考虑的特征仅有简单的离散和连续特征。

离散特征

对于离散的特征（如颜色为红、黄、蓝、绿），不难想到直接对标签值进行分类得到数个子节点（对于例子可分为4个子节点，对其所传入的训练集分别是颜色特征为红、黄、蓝、绿的样本）。

可以见得，当某个节点以离散特征作为划分依据时，传入每个子节点的训练集的该特征均相同（传入第一个子节点的样本该特征都为红，传入第二个都为黄，以此类推），故子节点及后代节点都不再需要对该特征进行判断。也就是说，当节点以离散特征作为划分依据时，其后代节点不可以再凭该特征进行划分。

连续特征

连续特征并不能像离散特征一样直接以数据来进行分类，据我所知，不同的决策树经典算法也对其有不同的处理方式。

ID3 决策树选择的处理方法是将连续数据分为数个区间，再如同离散数据一般进行分类，也就是将连续数据离散化。这样的好处是程序会变得更加简洁，只需要考虑离散数据的分类，训练算法的复杂度也会大大降低；但就同将连续值转为离散区间一般，连续数据所含信息有所丢失，这样的分类并不一定能够达到最佳的分类效果。

和离散特征一样，这样的处理方式也决定了该特征不能也不能被后代节点作为划分依据。

第二种方法，也就是本小项目中采用的处理方法，是 C4.5 算法所用的二分法，即将连续数据划为为两个类别。我们将连续数据进行排序，并穷举所有的二分划分方法，即每两个相邻连续数据之间位置，判断每个位置的划分优劣，选择最优位置进行划分，此时判断值为该位置前后元素的平均值。

文字描述或许不尽简洁易懂，下面举个简单的例子。对于已排序的n个连续特征 $\{a^1,a^2,…,a^n\}$ ，我们可以得到 $n-1$ 个划分位置选择，即集合 $\{\frac{a^i+a^{i+1}}{2}|1\leq i\leq n-1\}$ ，我们再分别进行优劣判断。这种方法能比上一种方法保留更多信息，也更可能找到所有特征中最佳的划分方式，但它的复杂度更高，运算量会成倍增加，不过在我看来，一般情况下这种复杂对于计算机并不算太过分。

与离散数据不同的是，我们采取的二分方法并不一定能一次性得到该特征最好的划分效果，但它的优势在于，子代也可以在没有更优的划分选择时，选择再次凭连续特征进行分化，即使用二分类进行划分的连续特征仍可作为后代节点的划分依据。

划分优劣判断指标

在具体记录各种判断依据之前，不得不对前文两种特征类型稍微总结：一个含有 $n$ 种类别的离散特征划分需要判断的次数是 $1$ 次，而一个含有 $n$ 个数据的连续特征用二分法划分需要判断的次数是 $n-1$ 次。这是因为一个离散变量仅有 $1$ 种划分选择，而连续变量有 $n-1$ 种划分选择，这也是前文表示用二分法处理连续特征更复杂的原因。

下面将介绍几种划分选择可用的指标，各种定义并不随资料不同而有大的改变，我会摘抄西瓜书上部分的定义内容，再加上自己的理解和引导。

既然要判断划分的优劣，我们对于每个数据集也要有一种优劣判断指标，当样本纯度越高时，我们也希望这个指标会越高。我们一般选用信息熵(熵不纯度)这一指标来度量样本的纯度：
样本集合 $D$ 中的第 $k$ 类样本所占比例为 $p_k (k = 1,2,…,\lvert\mathcal{Y}\rvert)$ ，其信息熵为

$$Ent(D) = -\sum_{k=1}^{\lvert\mathcal{Y}\rvert}p_k\log_2p_k$$

当 $Ent(D)$ 越小时， $D$ 的纯度越高。

不难想到，对于划分前后的数据集，对其信息熵进行运算，可以得到一种划分优劣判断指标，较常用的是信息增益。
将样本集合 $D$ 依照特征 $a$ 划分为 $D^1,D^2,…,D^v$ 数个新样本集，每个样本集权重依照样本数定义为 $\frac{\lvert D^i \rvert}{\lvert D \rvert} (i=1,2,…,v)$ ，则特征 $a$ 对样本集合 $D$ 进行划分的信息增益为

$$Gain(D, a) = Ent(D) - \sum_{i=1}^{v}\frac{\lvert D^i \rvert}{\lvert D \rvert}Ent(D^i)$$

一般而言， $Gain(D, a)$ 越大，说明依照特征 $a$ 对 $D$ 进行划分得到的纯度提升越高。上文多次提到的 ID3 决策树算法就是以此指标作为判断依据。

西瓜书提到，依照信息增益进行划分，“会使可取值数目较多的属性有所偏好”，有时给模型训练会带来不良影响。

此时可以引出一种新的指标，即信息增益率。
同上文信息增益的条件下，依照特征 $a$ 对 $D$ 进行划分的信息增益率为

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

其中

$$IV(a) = -\sum_{i=1}^{v}\frac{\lvert D^i \rvert}{\lvert D \rvert}\log_2\frac{\lvert D^i \rvert}{\lvert D \rvert}$$

被称为特征 $a$ 的“固有值”，当凭特征 $a$ 所能分割的样本集数量越多， $IV(a)$通常会越大，与信息增益 $Gain(D, a)$ 相除一定程度上可以消除信息增益的偏好所带来的不良影响。但这种修正是否会矫枉过正呢？西瓜书又提到，信息增益率又会“对可取值数目较少的属性有所偏好”。C4.5 算法并非直接使用了这项指标作为判断依据，而是先找出信息增益高于平均水平的特征，再从中选取信息增益率最高的。
本小项目中并未考虑得如此细致，一是因为所用的训练集大多是只有连续特征，所有划分都是二分类，基本不存在这种不公平，二是精力有限，对于练习项目仅仅做出典型算法即可，至于更多拓展的内容，与经典算法并无本质区别，何苦刻意求全。
（观察可知，特征 $a$ 的固有值 $IV(a)$ 的写法与信息熵写法十分相像，可以看出它的本质：特征 $a$ 的固有值 $IV(a)$ 也就是样本集 $D$ 在特征 $a$ 上的信息熵，公式中“ $\sum_{i=1}^{v}\frac{\lvert D^i \rvert}{\lvert D \rvert}$ ”部分正是求均值的方法。）

除上文所提两种判断指标以外，还有其他的指标可以用在决策树，比如 CART 决策树算法所用的 Gini 指数（基尼指数），它依靠类似信息熵的一种指标，叫Gini 值 （基尼值/基尼不纯度）。

样本集合 $D$ 中的第 $k$ 类样本（即 $D_k$）所占比例为 $p_k (k = 1,2,…,\lvert\mathcal{Y}\rvert)$ ，该样本集的 Gini 值为

$$Gini(D) = \sum_{k=1}^{\lvert\mathcal{Y}\rvert}\sum_{k^{\prime} \neq k}p_kp_{k^{\prime}} = 1-\sum_{k=1}^{\lvert\mathcal{Y}\rvert}p_k^2 = 1-\frac{\sum_{i=1}^{k}{\lvert D_k \rvert}^2}{\lvert D \rvert}$$

它反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。

同前文对信息增益的定义，将样本集合 $D$ 依照特征 $a$ 划分为 $D^1,D^2,…,D^v$ 数个新样本集，则特征 $a$ 对样本集 $D$ 进行划分的 Gini 指数为

$$Gini\_index(D, a) = \sum_{i=1}^{v}\frac{\lvert D^i \rvert}{\lvert D \rvert}Gini(D^i)$$

则可以使得 Gini 指数最小的划分选择是该条件下最优划分选择。

此外，还有一些常用的不纯度指标，这里再记录一种误分类不纯度。

样本集合 $D$ 中的第 $k$ 类样本（即 $D_k$）所占比例为 $p_k (k = 1,2,…,\lvert\mathcal{Y}\rvert)$ ，该样本集的误分类不纯度为

$$E(D) = 1 - \max(p_i) (i=1,2,...,k)$$

共同点？

观察上文提到的信息增益和 Gini 指数，其实都是相同的套路——一是将划分前的样本集不纯度减去划分后的加权样本集不纯度得到的值，使该值最大时，样本划分的纯度提升最大，如信息增益；二是取分割后的样本集的加权不纯度，使该值最小时，样本划分的纯度提升最大，如 Gini 指数。

就前者先加论述，使这个值为 $G(D, a)$ ，所对应的不纯度指标为 $E(D)$ （此次并非特指上文的误分类不纯度），将样本集合 $D$ 依照特征 $a$ 划分为 $D^1,D^2,…,D^v$ 数个新样本集，则特征 $a$ 对样本集 $D$ 进行划分的 $G(D, a)$ 为

$$G(D, a) = E(D) - \sum_{i=1}^{v}\frac{\lvert D^i \rvert}{\lvert D \rvert}E(D^i)$$

我们选取最优分割的特征 $a^*$ 则是使 $G(D, a)$ 最大的特征

$$a^* = \underset{a}{\arg\max} G(D,a)$$

而后者较简单，仅仅表示划分后的加权不纯度，使这个值为 $E^\prime(D, a)$ ，则有

$$E^\prime(D, a) = \sum_{i=1}^{v}\frac{\lvert D^i \rvert}{\lvert D \rvert}E(D^i)$$

最优划分的特征 $a^*$ 则是使 $E^\prime(D, a)$ 最小的特征

$$a^* = \underset{a}{\arg\min} E^\prime(D, a)$$

决策树特殊处理

在实际编写程序时，还有许多异常情况需要另行处理。由于前文已提到连续值特征的处理问题，故本节不再详细讨论。而对于回归树的相关问题，本小项目并未涉及，还请另行查阅资料。

缺失值处理

决策树剪枝

程序实现