1 前言

成熟的有监督学习的分类算法包括支援向量机（support vector machines），朴素贝叶斯（naïve Bayes），最近邻居法（K nearest neighbors），神经网络（neural nets），以及分类树（classification trees 又称 decision trees）及其发展出来的一系列高阶算法等等。下图为一些主流分类算法在三个不同的资料集上的分类效果。

在今天和下期的量化核武研究中，我们分两期聊聊分类树的相关算法，这包括基础的分类树，以及可以显著提升其分类效果的高阶算法，包括装袋算法（bagging）、提升算法（boosting）、以及随机森林（random forest）。这些高阶算法与基础分类树的本质区别是它们使用了许多个分类树（而非单一分类树），然后再把这些多个分类树的分类结果按某种权重平均，作为最终的分类结果。Bagging，Boosting 以及 Random Forest 都属于整合学习（ensemble learning），它们通过使用和结合多个单一分类树来取得更优秀的分类效果。因此，形象的说，单一分类树是一棵树，而这些高阶算法则使用了整片森林（许多许多的单一分类树组成了森林）。

在系列（上）篇，我们首先介绍单一分类树算法和它的一些问题。

2 分类树和 CART 算法

一个典型的分类问题可以描述如下：

有 n 个样本以及 m 个类别；每一个样本属于 m 个类别中的某一个，且每个样本可以由 K 个特征来描述。分类树（或任何一个其他的分类算法）就是一个分类器，它是从样本特征空间到类别空间的对映函式，根据样本的特征将样本分类。分类器之所以为有监督学习，是因为它的引数的选择依赖于基于历史资料的学习。这是因为人们相信过去的经验可以指导未来的分类。因此，在训练分类器的时候，所有的历史样本的正确类别是已知的，它们和样本的特征一起作为分类器的输入，分类器通过学习这些资料按照一定的损失函式（loss function）来决定分类器的引数。

一个分类树以所有的样本为待分类的起点，通过重复分裂（repetitive splits）将所有样本分成不同的子集。在每一次分裂时，以一个或多个特征的线性组合作为分类的依据、逐层分类，每层都在上一层分类的结果上选取新的分类属性进一步细分样本，从而形成一种发散式的树状递阶结构（hierarchical structure）。

下图是 wiki 上面一个用泰坦尼克号幸存者资料建模的分类树模型（输入资料为所有乘客的人口特征，类别为幸存和死亡两类）。图中，黑色粗体节点说明每一层级选用的分类特征，比如第一层分类时选用了性别（它的两个分支为男性和女性），第二层分类时选用了年龄（它的两个分支为年龄超过 9.5 岁与否），第三层分类时选用了同船的配偶及兄弟姐妹个数（它的两个分支为该个数是否大于 2.5）。这些分类节点在这个分类树中被称为内部节点。而图中红色和绿色的圆角矩形则代表了这颗分类树末端的树叶（leaf）；每片树叶都被标有一个明确的类别（本例中的幸存或者死亡）。分类树一旦确定，它的内部分类节点便清晰的说明了它的分类过程。在本例中，不难看出妇女和儿童是泰塔尼克沉船时的主要幸存者，这和实际情况是相符的。

本例虽然简单，但它说明分类树算法的两个重要的问题：

作为一种有监督学习，分类树可以根据给定的类别正确的发现最有效分类特征。分类树在学习之前并不知道泰坦尼克号的幸存者大部分为妇女和儿童，但是通过学习算法，它有效地选出性别和年龄（而非其他特征，诸如体重或者船舱等级）作为最重要的分类特征。在一棵分类树中，从最上方的第一个分类节点到一个给定的末端类别节点（树叶）便形成一个特定的分类路径。在分类时，所有满足该路径的样本都会被归到该树叶。在训练分类树模型时，我们并不刻意要求被归到同一树叶的所有样本都确实属于该树叶对应的类别。（随着特征的增加和不断细分，我们总能使得同一树叶下的样本完全满足该树叶对应的类别，但这往往意味着过度拟合。）比如在本例中，所有的女性乘客都被分到幸存者一类中（即这片树叶对应的类别为幸存）；而实际上在所有女性中，只有 73% 的女性幸存（即在满足该特征的所有样本中，仍然有 27% 的样本的实际类别与该树叶对应的类别不符）。当然，我们可以假想地对女性乘客继续细分下去——比如名叫 Rose 且恰好认识 Jack 的女性乘客死亡；叫 Anna 的一等舱女性乘客幸存——从而得到更多的分支和末端树叶（每个末端树叶包含的样本都满足该类）。但这样的细分对于该模型对于未来新资料的预测毫无意义：未来还会再有一个名叫 Rose 且恰好认识 Jack 的女性吗？即便有，她就一定也会在船撞上冰山时死亡吗？以上两点说明，一个分类树模型是否优秀取决于两点：如何选取有效的分类特征，以及如何确定分类树的大小（分的类太粗可能造成特征的不充分利用，分的类太细则造成过拟合）。下面就简要介绍确定分类树模型的 CART 算法。

2.2 CART 算法

CART 是 Classification And Regression Trees 的缩写，由 Breiman et al. (1984) 发明，自发明以来得到了长足的发展，成为了商业化的分类树算法软件。它可以根据给定的历史资料和评价标准来决定分类树模型（即选择各层的分类特征并确定分类树的大小）。

在确定分类树时，CART 算法考虑如下几个问题：（1）如何选择当前层的分类特征；（2）如何评价分类树的分类准确性；（3）如何通过综合考虑分类准确性和复杂程度来决定分类树的大小。下面逐一说明。

2.2.1 选择当前层的分类特征

CART 是一个递回式的二元分类法：对于每一个特征，待分配的样本按照是否满足该特征被分为两类。下图说明 CART 算法如何选择每一层的分类特征。假设在递回过程中，算法在上一步迭代中已经确定了特征节点 A1，让我们来考虑如何进一步选择特征 A2 来细分所有满足 A1 的样本。

在确定特征节点 A2 的时候，待分类样本包含的所有特征都会被考虑。在所有特征中，“分类效果最好”的那个特征将被选为 A2。那么如何定义“分类效果最好”呢？这可以由节点的纯度（purity）来定义。为此，定义一个衡量节点分类纯度的杂质方程（impurity function）。以特征节点 A1 为例，假设满足该节点的样本中，属于第 i 类的样本个数为 Pi，i = 1, …, m。因此，A1 节点的杂质方程可以由Gini 多样性指数（Gini index of diversity）或者熵函式（entropy function）来定义。它们都是 Pi 的函式。

Gini 多样性指数：

熵函式：

理想状态下，如果所有满足 A1 的样本都属于同一类，记为 i*，那么仅当 i = i* 时有 Pi = 1, 其他的 Pi = 0。在这种情况下，上述两个杂质函式的取值都是 0，说明节点的纯度为 1。在一般情况下，由于满足该节点的样本不可能都属于同一类，因此杂质函式的取值大于 0（节点纯度小于 1）。

有了分类好坏的评价标准，我们就可以选择分类特征 A2 了。对于每一个候选特征，计算按其分类后细分出来的两个节点（即满足该特征的节点和不满足该特征的节点）的纯度的加权平均（可以按照样本个数加权）。用这个纯度减去 A1 节点的纯度就是该候选特征的分类效果。在所有候选特征中，能够最大限度提升分类纯度的节点被选为 A2。值得一提的时，这个选择节点的方法只考虑了当前分类的区域性最优，即选出的 A2 是在当前情况下能最大化提升分类纯度的特征；A2 的选择是不考虑后续可能的分类的。因此，CART 算法在选择分类特征时是一种贪心法（greedy algorithm）。

2.2.2 评价分类树的准确性

和所有机器学习算法一样，我们关心的是得到的分类树对未来新样本的分类效果。因此，在评估分类树的准确性时，考虑该模型在训练资料（即用来建模的资料）上的效果是没有意义的。这是因为在极端过拟合的情况下，模型在训练集上的误差可以降为 0。对于分类树来说，如果每一个单一样本都通过它独有的特征取值被分到一个单一的末端树叶上，那么这个模型便可以 100% 正确地对训练集分类，但这样“准确性”对于我们评估该分类树对未来新资料的分类效果毫无帮助。

因此，在评判分类效果时，理想的状态是用在训练时没有使用过的资料，我们称之为测试集。测试集中的样本来自与训练集样本同样的本体（population）、符合同样的分布。因此，如果我们有足够多的资料，那么使用额外的测试集是最佳的选择。但是在很多情况下，尤其是金融领域，资料是稀缺和宝贵的。对于选股，我们希望尽可能多的使用历史资料来训练模型。在这种情况下，为了确保模型评价的正确性，可以采用 K 折交叉验证的方法（K-fold cross validation）。

K 折交叉验证将训练集分为 K 等分，每次将第 i 份（i = 1, …, K）的资料留作验证之用，而用剩余的 K-1 份资料建模得到一个分类树，然后将该模型对第 i 份资料进行分类，用分类的误差评估该模型的分类能力。对每份资料重复上面的操作便得到 K 个分类树模型（在实际中，K 的取值一般为 5 到 10 之间）。在建立这 K 个分类树时，应保证建模的标准是相同的（比如它们的杂质方程应该是相同的，不能有些使用 Gini 多样性指数，而另一些使用熵函式；又或者如果在建模时指定了分类树末端树叶的个数，那么这 K 棵树必须有相同的树叶个数）。把这 K 个分类树各自的误差取平均便得到了一个加权平均。如果我们用该建模标准对原始的所有训练样本资料进行建模，那么上述这个加权平均就是该模型误差的估计。

2.2.3 确定分类树的大小

在生成一颗分类树时，很难有一个有效的停止分裂标准（stop splitting rule）来决定不再继续细分。这是因为在分类树的发展中，可能出现这种情况，即当前这一步的分类只有限的提升分类效果，但接下来的分类却能很大的提升分类效果。在这种情况下，基于当前有限的分类提升效果而停止继续分类则是错误的。

在这个背景下，正确的做法是先生成一颗足够大的分类树（比如要求每个末端树叶下不超过 5 个样本），记为 T0。通过对这颗分类树进行“修剪”（pruning）来确定它的最佳尺寸。在修剪时，会综合考虑分类的误差和分类树的复杂程度，因而采用了成本及复杂性综合最小化的修剪（minimum cost–complexity pruning）。

假设我们有一颗分类树 T，它的末端树叶的个数记为 |T|，它的分类误差为 R(T)。另外，非负实数 a 为分类树复杂度的惩罚系数。如果用 Ra(T) 表示综合评价准确性和复杂性的测度，则有：

由于 a 是复杂度的惩罚系数，当 a 很小时，分类树的准确性会优先于复杂度，因此得到的分类树会有较多的枝节和末端树叶、分类误差较低；随着 a 的增大，对复杂度的厌恶程度加大，分类树的复杂度会降低，拥有较少的枝节和末端树叶、但分类误差也会增加。因此，我们希望通过搜寻来找到最优的 a 使得 Ra(T) 最小。当 Ra(T) 最小时对应的分类树就是最优的分类树。

为了找到最优的分类树，算法会从最初的分类树 T0 开始，对于不同的 a 的取值（由小到大，单调递增），按照最弱环节切割（weakest-link cutting）法生成一系列的巢状树（nested trees）T1，T2，……。由于修剪会减少分类树的节点，从而造成其分类效果下降，而修剪不同节点对分类效果的负面影响是不同的。因此，最弱环节切割的意思就是在修剪分类树的节点时，应该剪掉对分类效果负面影响最小的节点。（有兴趣的读者请进一步参阅 Sutton 2005）。

所谓巢状树，就是说 T1 是由修剪 T0 的枝干和节点得到，T2 是由修剪 T1 得到，每一棵树都由修剪之前一棵树得到。举例来说，假如我们在 1 到 10 之间的整数中寻找最优的 a：首先取 a = 1，并由 T0 开始生成一颗新的分类树 T1 使得 R1(T1) 最小；然后取 a = 2，并由 T1 开始生成一颗新的分类树 T2 使得 R2(T2) 最小；以此类推，最终我们会从分类树 T9 和 a = 10 生成最后一颗分类树 T10，使得 R10(T10) 最小。这样便得到了从 T1 开始到 T10 的一族巢状树，而之中的每一颗数之于它对应的 a 来说都是最优的。最后，比较这 10 个不同的 a 的取值，找到使 Ra(Ta) 最小的那个 a，

其对应的分类树 Ta 就是最优的。

综上所述，假设我们使用交叉验证来计算分类树 T 的准确性的话，那么确定最优分类树大小的步骤为：

确定最优分类树步骤

1. 将训练集样本分成 K 份

2. 对于每一份，重复下面的步骤：

2.1 将这份资料留作验证之用

2.2 用其他 K-1 份资料建模，得到一颗初始的足够大的分类树 T

2.3 以 T 为起点，对于给定范围的 a，通过 minimum cost–complexity pruning 得到一族巢状的分类树

3. 经过步骤 2 之后，对于每一个给定的 a，我们都有 K 颗不同的分类树，将它们的 Ra 取平均作为在整体训练集上使用 a 进行修剪后得到的最优分类树的分类效果的估计；记使得 Ra 平均取最小的那个 a 为 a*，它就是对于整体训练集最优的 a

4. 将训练集的所有样本为物件，以 a=a* 训练并修建出一颗分类树，这就是我们的最优分类树

3 分类树的特点和不足

然而（单颗）分类树存在一些先天的不足。假设 x 代表样本点特征（它的取值来自一个未知的概率分布），Yx 为该样本点的真实分类，C(x) 为某分类树对 x 的预测结果（因此 C(x) 是一个随机变数）。令 E[C(x)] 为 C(x) 的期望。因此，这个分类树的分类误差满足：

可见，分类器的误差分为偏差 E[(Yx – E[C(x)])^2] 和方差 Var(C(x)) 两个部分。分类树是一个不太稳定的分类器；当训练样本稍有改变时，分类树的分类节点可能会发生变化从而造成不同的分类结果。这意味着对于分类树来说，Var(C(x)) 不可忽视，即单一分类树自身的方差对分类误差的贡献是固有的。如果我们能够使用 E[C(x)] 代替 C(x) 则可以避免单一分类树自身的方差产生的分类误差。

当然，在实际中，E[C(x)] 是未知的，但是我们可以通过平均大量不同单颗分类树的分类结果来近似得到 E[C(x)]，使它们各自的方差相互抵消。根据大数定理，大量不同分类树的平均结果将有效的逼近 E[C(x)]。这便是“拥抱了整片森林”带来的优势。

本文第一节提到的 bagging（Breiman 1996a, 1996b），boosting（Freund and Schapire 1996），以及随机森林（Breiman 2001）等算法都是使用了大量多颗分类树取代单一分类树对资料进行分类的经典算法。它们在不改变偏差的前提下有效的降低了分类树自身的方差，从而显著提高了分类准确性。我们将在本篇的下期中介绍这些高阶算法。

参考文献

Breiman, L. (1996a). Bagging predictors. Machine Learning, Vol. 24, 123–140.Breiman, L. (1996b). Heuristics of instability and stabilization in model selection. Ann. Statist., Vol. 24, 2350–2383.Breiman, L. (2001). Random forests. Machine Learning, Vol. 45, 5–32.Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J. (1984). Classification and Regression Trees. Wadsworth, Pacific Grove, CA.Freund, Y., Schapire, R. (1996). Experiments with a new boosting algorithm. In: Saitta, L. (Ed.), Machine Learning: Proceedings of the Thirteenth International Conference. Morgan Kaufmann, San Francisco, CA.Sutton, C. D. (2005). Classification and Regression Trees, Bagging, and Boosting. In Rao, C. R., Wegman, E. J., Solka, J. L. (Eds.), Handbook of Statistics 24: Data Mining and Data Visualization, Chapter 11.