机器学习之决策树算法

决策树 (decision tree) 是一种常用的有监督算法。

决策树算法有很多类型，其中最大的差别就是最优特征选择的方法不同。最优特征指的是，在每个结点处，如何选择最好的特征（属性）对样本进行分类，这里最佳的意义即经过这步划分，能使分类精度最好，直到这棵树能准确分类所有训练样本。

通常特征选择的方法有信息增益、信息增益比、基尼指数等，对应 3 种最常用的决策树实现算法，分别是 ID3 算法、C4.5 算法和 CART 算法。

CART 算法与基尼指数

CART 算法

CART (classification and regression tree) 分类回归树可以用于分类任务也可以用于回归任务。

它形成的决策树是一棵二叉树，在每次进行划分时，它都把当前样本集划分为两个子样本集，生成两个分枝，因此每一步的划分决策只能是“是”或“否”，即使用来划分的特征有多个取值，也是处理后二分。在划分时，CART 每次都是针对单个变量进行划分，并且这个变量可能重复使用。在划分后，CART 还会采用交叉验证法进行剪枝。

决策树的生长过程实际就是不断把样本集进行分割的过程，每次分割都要求被分到一个分枝（或叶子）上的样本间的差异最小，而不同分枝（或叶子）之间的差异最大。如何度量这个“差异”的指标，被称为“不纯性”。CART 使用的不纯性度量指标是基尼指数。

基尼指数

基尼指数 (Gini index) 是一种不等性度量，通常用来度量收入不平衡，也可以用来度量任何不均匀分布，是一个介于 0~1 的实数。基尼指数代表了不纯度，基尼指数越小，则样本的不纯度越低，特征越好。

在分类问题中，假设有 K 个类别，第 k 个类别的概率为 \(p_k\)，则基尼指数的表达式为：
\[Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^K{p_k}^2\]
若是二类分类问题，计算就更简单了，如果属于第一个样本输出的概率是 \(p\)，则基尼指数的表达式为：
\[Gini(p)=2p(1-p)\]
对于给定样本 D，假设有 K 个类别，第 k 个类别的数量为 \(C_k\)，则样本 D 的基尼指数表达式为：
\[Gini(D)=1-\sum_{k=1}^K{(\frac{|C_k|} {|D|})}^2\]
特别的，对于样本 D，如果根据特征 A 的某个值 a，把 D 分成 \(D_1\) 和 \(D_2\) 两部分，则在特征 A 的条件下，D 的基尼指数表达式为：
\[Gini(D,A)=\frac{|D_1|} {|D|}Gini(D_1)+\frac{|D_2|} {|D|}Gini(D_2)\]
如此，CART 算法基于最小化基尼指数的原则，得出当前样本集上最优的划分，生成两个子结点，将当前训练样本集分配到这两个节点中，完成一次划分。整个决策树构建的过程即不断递归这一步骤，直到满足一定条件为止。

算法过程

（1）设结点处的训练数据集为 D，计算现有特征对该数据集的基尼指数。此时对每一个特征 A，对其可能取的每个值 a，根据样本点对 \(A=a\) 的测试为“是”或“否”，将 D 分割成 \(D_1\) 和 \(D_2\) 两部分，利用基尼指数计算公式计算。

（2）在所有可能的特征 A 及它们所有可能的切分点 a 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依据最优特征与最优切分点，从当前结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。

（3）对两个子结点递归地调用步骤（1）~（2），直至满足停止条件。

（4）生成 CART 决策树。

算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或者没有更多特征。

算法的优缺点

优点：

（1）产生的决策树模型非常直观，能直接生成判断规则，方便业务角度的理解。

（2）数据不需要预处理和标准化。

（3）对于数据的分布没有严格规定。

（4）对于缺失值和异常值较健壮，受影响较小。

（5）可以帮助其他算法挑选重要的特征变量，发现哪些特征对分类最有价值。

（6）可以轻松处理多分类问题。

缺点：

（1）很容易在训练数据中生成复杂的树结构，从而造成过拟合，模型泛化能力不强。

（2）会因为样本发生一点点的改动，导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

解决决策树过拟合问题

决策树的生成算法递归地产生决策树，直到无法分割为止，这样产生的模型容易变得很复杂，产生过拟合。使用这样的树模型对未知的数据进行分类，准确性往往不高。

一般来说，有以下几个方法来解决决策树的过拟合问题。

剪枝

剪枝可分为前剪枝 (prepruning) 和后剪枝 (postpruning)，前剪枝即在决策树生成之前就人为定义好树的层数，以及每个结点允许的最少样本数等，而且在给定的结点不再分裂。后剪枝指的是先让决策树充分生长，然后减去部分子树，用树叶替换删除掉的结点。

CART 算法采用的后剪枝方法，它先生成一棵完整的树，然后产生所有可能的剪枝过的 CART 树，再使用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的树作为最终的 CART 树。

K 层交叉验证

首先计算出整体的决策树 T ，叶节点个数记作 N，设 i 属于 \([1, N]\)。对每个 i，使用 K 层交叉验证方法衡量决策树，并裁剪到 i 个节点，计算错误率，最后求出平均错误率。这样可以用最小错误率对应的 i 作为最终决策树的大小，对原始决策树进行裁剪，得到最优决策树。

随机森林

随机森林是用训练数据随机计算出许多决策树，形成一个由多个决策树构成的“森林”，然后用这个森林对未知数据进行预测，选取投票最多的分类作为分类结果。

Demo

使用 CART 对 Iris 数据集进行分类。

Jupyter Notebook 链接为：CART-Iris

【References】

[1] 裔隽，张怿檬，张目清等．Python机器学习实战[M]．北京：科学技术文献出版社，2018