一棵树不够，就送你整片森林（上）

1

前言

机器学习（machine learning）和投资的结合点之一便是人工智能选股。对于机器学习来说，选股是一个典型的分类（classification）问题。与股票相关的各种估值、财务和技术等因子都可以看作是用来对股票分类的特征（feature），而股票的涨跌幅则决定股票属于哪一类（比如好的股票和差的股票）。用机器学习进行选股属于有监督学习（supervised learning），它将好的和差的股票进行标识（labelling），然后让某种分类算法使用历史数据训练、学习并挖掘股票收益率和股票特征之间的关系，从而形成一个分类模型。得到分类模型后，每当有新一期的特征数据之后，便可以使用该模型对股票进行分类，选出在下一个投资周期内收益率（在概率上）会更加优秀的股票。这便是机器学习选股的过程。在这个过程中，分类算法是一个选股成功与否的核心之一。

成熟的有监督学习的分类算法包括支持向量机（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算法

2.1

认识分类树

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

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

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

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

1 作为一种有监督学习，分类树可以根据给定的类别正确的发现最有效分类特征。分类树在学习之前并不知道泰坦尼克号的幸存者大部分为妇女和儿童，但是通过学习算法，它有效地选出性别和年龄（而非其他特征，诸如体重或者船舱等级）作为最重要的分类特征。

2 在一棵分类树中，从最上方的第一个分类节点到一个给定的末端类别节点（树叶）便形成一个特定的分类路径。在分类时，所有满足该路径的样本都会被归到该树叶。在训练分类树模型时，我们并不刻意要求被归到同一树叶的所有样本都确实属于该树叶对应的类别。（随着特征的增加和不断细分，我们总能使得同一树叶下的样本完全满足该树叶对应的类别，但这往往意味着过度拟合。）比如在本例中，所有的女性乘客都被分到幸存者一类中（即这片树叶对应的类别为幸存）；而实际上在所有女性中，只有73%的女性幸存（即在满足该特征的所有样本中，仍然有27%的样本的实际类别与该树叶对应的类别不符）。当然，我们可以假想地对女性乘客继续细分下去——比如名叫Rose且恰好认识Jack的女性乘客死亡；叫Anna的一等舱女性乘客幸存——从而得到更多的分支和末端树叶（每个末端树叶包含的样本都满足该类）。但这样的细分对于该模型对于未来新数据的预测毫无意义：未来还会再有一个名叫Rose且恰好认识Jack的女性吗？即便有，她就一定也会在船撞上冰山时死亡吗？

以上两点说明，一个分类树模型是否优秀取决于两点：如何选取有效的分类特征，以及如何确定分类树的大小（分的类太粗可能造成特征的不充分利用，分的类太细则造成过拟合）。下面就简要介绍确定分类树模型的CART算法。

2.2

CART算法

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

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

选择当前层的分类特征

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 = 0, 其他的Pi = 0。在这种情况下，上述两个杂质函数的取值都是0，说明节点的纯度为1。在一般情况下，由于满足该节点的样本不可能都属于同一类，因此杂质函数的取值大于0（节点纯度小于1）。

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

评价分类树的准确性

和所有机器学习算法一样，我们关心的是得到的分类树对未来新样本的分类效果。因此，在评估分类树的准确性时，考虑该模型在训练数据（即用来建模的数据）上的效果是没有意义的。这是因为在极端过拟合的情况下，模型在训练集上的误差可以降为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个分类树各自的误差取平均便得到了一个加权平均。如果我们用该建模标准对原始的所有训练样本数据进行建模，那么上述这个加权平均就是该模型误差的估计。

确定分类树的大小

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

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

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

R_a(T) = R(T) + a|T|

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

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

所谓嵌套树，就是说T₁是由修剪T₀的枝干和节点得到，T₂是由修剪T₁得到，每一棵树都由修剪之前一棵树得到。举例来说，假如我们在1到10之间的整数中寻找最优的a：首先取a = 1，并由T₀开始生成一颗新的分类树T₁使得R₁(T₁)最小；然后取a = 2，并由T₁开始生成一颗新的分类树T₂使得R₂(T₂)最小；以此类推，最终我们会从分类树T₉和a = 10生成最后一颗分类树T₁₀，使得R₁₀(T₁₀)最小。这样便得到了从T₁开始到T₁₀的一族嵌套树，而之中的每一颗数之于它对应的a来说都是最优的。最后，比较这10个不同的a的取值，找到使R_a(T_a)最小的那个a，其对应的分类树T_a就是最优的。

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

确定最优分类树步骤

1 将训练集样本分成K份

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

2.1 将这份数据留作验证之用

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

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

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

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

3

分类树的特点和不足

分类树是一种非参数化的计算密集型算法。但是随着计算机技术的发展，计算强度已不再是一个太大的问题。这种分类算法可以处理大量的样本以及大量的特征，有效的挖掘出特征之间的相互作用。此外，分类树的解释性也比较强，对特征数据也没有独立性要求，这些使它得到了广泛的应用。

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

E([Y_x –C(x)]²)

= E([(Y_x – E[C(x)]) + (E[C(x)] – C(x))]²)

= E([Y_x – E[C(x)]]²) + 2E(Y_x – E[C(x)])E(E[C(x)] – C(x)) + E([E[C(x)] –C(x)]²)

= E([Y_x – E[C(x)]]²) + E([E[C(x)] –C(x)]²)

= E([Y_x – E[C(x)]]²) + Var(C(x))

>= E([Y_x – E[C(x)]]²)

可见，分类器的误差分为偏差E([Yx – E[C(x)]]²)和方差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.