作者：石川

摘要：分類樹算法能處理大量樣本和大量特征數(shù)據(jù)，但單一分類樹存在固有的方差，影響了其準(zhǔn)確性。

1 引言

機(jī)器學(xué)習(xí)（machine learning）和投資的結(jié)合點(diǎn)之一便是選股。對于機(jī)器學(xué)習(xí)來說，選股可被視為一個(gè)分類（classification）問題。與股票相關(guān)的各種估值、財(cái)務(wù)和技術(shù)等因子都可以看作是用來對股票分類的特征（feature），而股票的漲跌幅則決定股票屬于哪一類（比如好的股票和差的股票）。用機(jī)器學(xué)習(xí)進(jìn)行選股屬于監(jiān)督學(xué)習(xí)（supervised learning），它將好的和差的股票進(jìn)行標(biāo)記（labeling），然后讓某種分類算法使用歷史數(shù)據(jù)訓(xùn)練、學(xué)習(xí)并挖掘股票收益率和股票特征之間的關(guān)系，從而形成一個(gè)分類模型。得到分類模型后，每當(dāng)有新一期的特征數(shù)據(jù)之后，便可以使用該模型對股票進(jìn)行分類，選出在下一個(gè)投資周期內(nèi)收益率（在概率上）會更加優(yōu)秀的股票。這便是機(jī)器學(xué)習(xí)選股的過程。在這個(gè)過程中，分類算法是一個(gè)選股成功與否的核心之一。

成熟的監(jiān)督學(xué)習(xí)的分類算法包括支持向量機(jī)（support vector machines），樸素貝葉斯（na?ve Bayes），最近鄰居法（K nearest neighbors），神經(jīng)網(wǎng)絡(luò)（neural nets），以及分類樹（classification trees 又稱 decision trees）及其發(fā)展出來的一系列高級算法等等。下圖為一些主流分類算法在三個(gè)不同的數(shù)據(jù)集上的分類效果。

在今天和下期的量化核武研究中，我們分兩期聊聊分類樹的相關(guān)算法，這包括基礎(chǔ)的分類樹，以及可以顯著提升其分類效果的高級算法，包括裝袋算法（bagging）、提升算法（boosting）、以及隨機(jī)森林（random forest）。這些高級算法與基礎(chǔ)分類樹的本質(zhì)區(qū)別是它們使用了許多個(gè)分類樹（而非單一分類樹），然后再把這些多個(gè)分類樹的分類結(jié)果按某種權(quán)重平均，作為最終的分類結(jié)果。Bagging，Boosting 以及 Random Forest 都屬于集成學(xué)習(xí)（ensemble learning），它們通過使用和結(jié)合多個(gè)單一分類樹來取得更優(yōu)秀的分類效果。因此，形象的說，單一分類樹是一棵樹，而這些高級算法則使用了整片森林（許多許多的單一分類樹組成了森林）。

在本期中，我們首先介紹單一分類樹算法和它的一些問題。

2 分類樹和 CART 算法

2.1 認(rèn)識分類樹

一個(gè)典型的分類問題可以描述如下：

分類器之所以為監(jiān)督學(xué)習(xí)，是因?yàn)樗膮?shù)的選擇依賴于基于歷史數(shù)據(jù)的學(xué)習(xí)。這是因?yàn)槿藗兿嘈胚^去的經(jīng)驗(yàn)可以指導(dǎo)未來的分類。因此，在訓(xùn)練分類器的時(shí)候，所有的歷史樣本的正確類別是已知的，它們和樣本的特征一起作為分類器的輸入，分類器通過學(xué)習(xí)這些數(shù)據(jù)按照一定的損失函數(shù)（loss function）來決定分類器的參數(shù)。

一個(gè)分類樹以所有的樣本為待分類的起點(diǎn)，通過重復(fù)分裂（repetitive splits）將所有樣本分成不同的子集。在每一次分裂時(shí)，以一個(gè)或多個(gè)特征的線性組合作為分類的依據(jù)、逐層分類，每層都在上一層分類的結(jié)果上選取新的分類屬性進(jìn)一步細(xì)分樣本，從而形成一種發(fā)散式的樹狀遞階結(jié)構(gòu)（hierarchical structure）。

下圖是 wiki 上面一個(gè)用泰坦尼克號幸存者數(shù)據(jù)建模的分類樹模型（輸入數(shù)據(jù)為所有乘客的人口特征，類別為幸存和死亡兩類）。圖中，黑色粗體節(jié)點(diǎn)說明每一層級選用的分類特征，比如第一層分類時(shí)選用了性別（它的兩個(gè)分支為男性和女性），第二層分類時(shí)選用了年齡（它的兩個(gè)分支為年齡超過 9.5 歲與否），第三層分類時(shí)選用了同船的配偶及兄弟姐妹個(gè)數(shù)（它的兩個(gè)分支為該個(gè)數(shù)是否大于 2.5）。這些分類節(jié)點(diǎn)在這個(gè)分類樹中被稱為內(nèi)部節(jié)點(diǎn)。而圖中紅色和綠色的圓角矩形則代表了這顆分類樹末端的樹葉（leaf）；每片樹葉都被標(biāo)有一個(gè)明確的類別（本例中的幸存或者死亡）。分類樹一旦確定，它的內(nèi)部分類節(jié)點(diǎn)便清晰的說明了它的分類過程。在本例中，不難看出婦女和兒童是泰塔尼克沉船時(shí)的主要幸存者，這和實(shí)際情況是相符的。

本例雖然簡單，但它說明分類樹算法的兩個(gè)重要的問題：

以上兩點(diǎn)說明，一個(gè)分類樹模型是否優(yōu)秀取決于兩點(diǎn)：如何選取有效的分類特征，以及如何確定分類樹的大小（分的類太粗可能造成特征的不充分利用，分的類太細(xì)則造成過擬合）。下面就簡要介紹確定分類樹模型的 CART 算法。

2.2 CART 算法

CART 是 Classification And Regression Trees 的縮寫，由 Breiman et al. (1984) 發(fā)明，自發(fā)明以來得到了長足的發(fā)展，成為了商業(yè)化的分類樹算法軟件。它可以根據(jù)給定的歷史數(shù)據(jù)和評價(jià)標(biāo)準(zhǔn)來決定分類樹模型（即選擇各層的分類特征并確定分類樹的大?。Ｔ诖_定分類樹時(shí)，CART 算法考慮如下幾個(gè)問題：（1）如何選擇當(dāng)前層的分類特征；（2）如何評價(jià)分類樹的分類準(zhǔn)確性；（3）如何通過綜合考慮分類準(zhǔn)確性和復(fù)雜程度來決定分類樹的大小。下面逐一說明。

選擇當(dāng)前層的分類特征：CART 是一個(gè)遞歸式的二元分類法：對于每一個(gè)特征，待分配的樣本按照是否滿足該特征被分為兩類。下圖說明 CART 算法如何選擇每一層的分類特征。假設(shè)在遞歸過程中，算法在上一步迭代中已經(jīng)確定了特征節(jié)點(diǎn) A1，讓我們來考慮如何進(jìn)一步選擇特征 A2 來細(xì)分所有滿足 A1 的樣本。

在確定特征節(jié)點(diǎn) A2 的時(shí)候，待分類樣本包含的所有特征都會被考慮。在所有特征中，“分類效果最好”的那個(gè)特征將被選為 A2。那么如何定義“分類效果最好”呢？這可以由節(jié)點(diǎn)的純度（purity）來定義。為此，定義一個(gè)衡量節(jié)點(diǎn)分類純度的雜質(zhì)方程（impurity function）。以特征節(jié)點(diǎn) A1 為例，假設(shè)滿足該節(jié)點(diǎn)的樣本中，屬于第 i 類的樣本個(gè)數(shù)為 Pi，i = 1, …, m。因此，A1 節(jié)點(diǎn)的雜質(zhì)方程可以由?Gini 多樣性指數(shù)（Gini index of diversity）或者熵函數(shù)（entropy function）來定義。它們都是 Pi 的函數(shù)。

Gini 多樣性指數(shù)：

熵函數(shù)：

理想狀態(tài)下，如果所有滿足 A1 的樣本都屬于同一類，記為 i*，那么僅當(dāng) i = i* 時(shí)有 Pi = 1, 其他的 Pi = 0。在這種情況下，上述兩個(gè)雜質(zhì)函數(shù)的取值都是 0，說明節(jié)點(diǎn)的純度為 1。在一般情況下，由于滿足該節(jié)點(diǎn)的樣本不可能都屬于同一類，因此雜質(zhì)函數(shù)的取值大于 0（節(jié)點(diǎn)純度小于 1）。

有了分類好壞的評價(jià)標(biāo)準(zhǔn)，我們就可以選擇分類特征 A2 了。對于每一個(gè)候選特征，計(jì)算按其分類后細(xì)分出來的兩個(gè)節(jié)點(diǎn)（即滿足該特征的節(jié)點(diǎn)和不滿足該特征的節(jié)點(diǎn)）的純度的加權(quán)平均（可以按照樣本個(gè)數(shù)加權(quán)）。用這個(gè)純度減去 A1 節(jié)點(diǎn)的純度就是該候選特征的分類效果。在所有候選特征中，能夠最大限度提升分類純度的節(jié)點(diǎn)被選為 A2。值得一提的時(shí)，這個(gè)選擇節(jié)點(diǎn)的方法只考慮了當(dāng)前分類的局部最優(yōu)，即選出的 A2 是在當(dāng)前情況下能最大化提升分類純度的特征；A2 的選擇是不考慮后續(xù)可能的分類的。因此，CART 算法在選擇分類特征時(shí)是一種貪心法（greedy algorithm）。

評價(jià)分類樹的準(zhǔn)確性：和所有機(jī)器學(xué)習(xí)算法一樣，我們關(guān)心的是得到的分類樹對未來新樣本的分類效果。因此，在評估分類樹的準(zhǔn)確性時(shí)，考慮該模型在訓(xùn)練數(shù)據(jù)（即用來建模的數(shù)據(jù)）上的效果是沒有意義的。這是因?yàn)樵跇O端過擬合的情況下，模型在訓(xùn)練集上的誤差可以降為 0。對于分類樹來說，如果每一個(gè)單一樣本都通過它獨(dú)有的特征取值被分到一個(gè)單一的末端樹葉上，那么這個(gè)模型便可以 100% 正確地對訓(xùn)練集分類，但這樣“準(zhǔn)確性”對于我們評估該分類樹對未來新數(shù)據(jù)的分類效果毫無幫助。

因此，在評判分類效果時(shí)，理想的狀態(tài)是用在訓(xùn)練時(shí)沒有使用過的數(shù)據(jù)，我們稱之為測試集。測試集中的樣本來自與訓(xùn)練集樣本同樣的本體（population）、符合同樣的分布。因此，如果我們有足夠多的數(shù)據(jù)，那么使用額外的測試集是最佳的選擇。但是在很多情況下，尤其是金融領(lǐng)域，數(shù)據(jù)是稀缺和寶貴的。對于選股，我們希望盡可能多的使用歷史數(shù)據(jù)來訓(xùn)練模型。在這種情況下，為了確保模型評價(jià)的正確性，可以采用?K 折交叉驗(yàn)證的方法（K-fold cross validation）。

K 折交叉驗(yàn)證將訓(xùn)練集分為 K 等分，每次將第 i 份（i = 1, …, K）的數(shù)據(jù)留作驗(yàn)證之用，而用剩余的 K-1 份數(shù)據(jù)建模得到一個(gè)分類樹，然后將該模型對第 i 份數(shù)據(jù)進(jìn)行分類，用分類的誤差評估該模型的分類能力。對每份數(shù)據(jù)重復(fù)上面的操作便得到 K 個(gè)分類樹模型（在實(shí)際中，K 的取值一般為 5 到 10 之間）。在建立這 K 個(gè)分類樹時(shí)，應(yīng)保證建模的標(biāo)準(zhǔn)是相同的（比如它們的雜質(zhì)方程應(yīng)該是相同的，不能有些使用 Gini 多樣性指數(shù)，而另一些使用熵函數(shù)；又或者如果在建模時(shí)指定了分類樹末端樹葉的個(gè)數(shù)，那么這 K 棵樹必須有相同的樹葉個(gè)數(shù)）。把這 K 個(gè)分類樹各自的誤差取平均便得到了一個(gè)加權(quán)平均。如果我們用該建模標(biāo)準(zhǔn)對原始的所有訓(xùn)練樣本數(shù)據(jù)進(jìn)行建模，那么上述這個(gè)加權(quán)平均就是該模型誤差的估計(jì)。

確定分類樹的大?。?/strong>在生成一顆分類樹時(shí)，很難有一個(gè)有效的停止分裂標(biāo)準(zhǔn)（stop splitting rule）來決定不再繼續(xù)細(xì)分。這是因?yàn)樵诜诸悩涞陌l(fā)展中，可能出現(xiàn)這種情況，即當(dāng)前這一步的分類只有限的提升分類效果，但接下來的分類卻能很大的提升分類效果。在這種情況下，基于當(dāng)前有限的分類提升效果而停止繼續(xù)分類則是錯(cuò)誤的。

在這個(gè)背景下，正確的做法是先生成一顆足夠大的分類樹（比如要求每個(gè)末端樹葉下不超過 5 個(gè)樣本），記為 T0。通過對這顆分類樹進(jìn)行“剪枝”（pruning）來確定它的最佳尺寸。在修剪時(shí)，會綜合考慮分類的誤差和分類樹的復(fù)雜程度，因而采用了成本及復(fù)雜性綜合最小化的剪枝（minimum cost–complexity pruning）。

假設(shè)我們有一顆分類樹 T，它的末端樹葉的個(gè)數(shù)記為 |T|，它的分類誤差為 R(T)。另外，非負(fù)實(shí)數(shù) a 為分類樹復(fù)雜度的懲罰系數(shù)。如果用?Ra(T) 表示綜合評價(jià)準(zhǔn)確性和復(fù)雜性的測度，則有：

由于 a 是復(fù)雜度的懲罰系數(shù)，當(dāng) a 很小時(shí)，分類樹的準(zhǔn)確性會優(yōu)先于復(fù)雜度，因此得到的分類樹會有較多的枝節(jié)和末端樹葉、分類誤差較低；隨著 a 的增大，對復(fù)雜度的厭惡程度加大，分類樹的復(fù)雜度會降低，擁有較少的枝節(jié)和末端樹葉、但分類誤差也會增加。因此，我們希望通過搜索來找到最優(yōu)的 a 使得?Ra(T) 最小。當(dāng)?Ra(T) 最小時(shí)對應(yīng)的分類樹就是最優(yōu)的分類樹。

為了找到最優(yōu)的分類樹，算法會從最初的分類樹 T0?開始，對于不同的 a 的取值（由小到大，單調(diào)遞增），按照最弱環(huán)節(jié)切割（weakest-link cutting）法生成一系列的嵌套樹（nested trees）T1，T2，……。由于修剪會減少分類樹的節(jié)點(diǎn)，從而造成其分類效果下降，而修剪不同節(jié)點(diǎn)對分類效果的負(fù)面影響是不同的。因此，最弱環(huán)節(jié)切割的意思就是在修剪分類樹的節(jié)點(diǎn)時(shí)，應(yīng)該剪掉對分類效果負(fù)面影響最小的節(jié)點(diǎn)。（有興趣的讀者請進(jìn)一步參閱 Sutton 2005）。

所謂嵌套樹，就是說 T1?是由修剪 T0?的枝干和節(jié)點(diǎn)得到，T2?是由修剪 T1?得到，每一棵樹都由修剪之前一棵樹得到。舉例來說，假如我們在 1 到 10 之間的整數(shù)中尋找最優(yōu)的 a：首先取 a = 1，并由 T0?開始生成一顆新的分類樹 T1?使得 R1(T1) 最?。蝗缓笕?a = 2，并由 T1?開始生成一顆新的分類樹 T2?使得 R2(T2) 最??；以此類推，最終我們會從分類樹 T9?和 a = 10 生成最后一顆分類樹 T10，使得 R10(T10) 最小。這樣便得到了從 T1?開始到 T10?的一族嵌套樹，而之中的每一顆數(shù)之于它對應(yīng)的 a 來說都是最優(yōu)的。最后，比較這 10 個(gè)不同的 a 的取值，找到使 Ra(Ta) 最小的那個(gè) a。其對應(yīng)的分類樹 Ta?就是最優(yōu)的。

綜上所述，假設(shè)我們使用交叉驗(yàn)證來計(jì)算分類樹 T 的準(zhǔn)確性的話，那么確定最優(yōu)分類樹大小的步驟為：

1. 將訓(xùn)練集樣本分成 K 份；

2. 對于每一份，重復(fù)下面的步驟：

? ? 2.1 將這份數(shù)據(jù)留作驗(yàn)證之用；

? ? 2.2 用其他 K-1 份數(shù)據(jù)建模，得到一顆初始的足夠大的分類樹 T；

? ? 2.3 以 T 為起點(diǎn)，對于給定范圍的 a，通過 minimum cost–complexity pruning 得到一族嵌套的分類樹；

3. 經(jīng)過步驟 2 之后，對于每一個(gè)給定的 a，我們都有 K 顆不同的分類樹，將它們的 Ra 取平均作為在整體訓(xùn)練集上使用 a 進(jìn)行修剪后得到的最優(yōu)分類樹的分類效果的估計(jì)；記使得 Ra 平均取最小的那個(gè) a 為 a*，它就是對于整體訓(xùn)練集最優(yōu)的 a；

4. 將訓(xùn)練集的所有樣本為對象，以 a=a* 訓(xùn)練并修建出一顆分類樹，這就是我們的最優(yōu)分類樹。

3 分類樹的特點(diǎn)和不足

分類樹是一種非參數(shù)化的計(jì)算密集型算法。但是隨著計(jì)算機(jī)技術(shù)的發(fā)展，計(jì)算強(qiáng)度已不再是一個(gè)太大的問題。這種分類算法可以處理大量的樣本以及大量的特征，有效的挖掘出特征之間的相互作用。此外，分類樹的解釋性也比較強(qiáng)，對特征數(shù)據(jù)也沒有獨(dú)立性要求，這些使它得到了廣泛的應(yīng)用。

然而（單顆）分類樹存在一些先天的不足。假設(shè) x 代表樣本點(diǎn)特征（它的取值來自一個(gè)未知的概率分布），Yx?為該樣本點(diǎn)的真實(shí)分類，C(x) 為某分類樹對 x 的預(yù)測結(jié)果（因此 C(x) 是一個(gè)隨機(jī)變量）。令 E[C(x)] 為 C(x) 的期望。因此，這個(gè)分類樹的分類誤差滿足：

可見，分類器的誤差分為偏差 E[(Yx?– E[C(x)])^2] 和方差 Var(C(x)) 兩個(gè)部分。分類樹是一個(gè)不太穩(wěn)定的分類器；當(dāng)訓(xùn)練樣本稍有改變時(shí)，分類樹的分類節(jié)點(diǎn)可能會發(fā)生變化從而造成不同的分類結(jié)果。這意味著對于分類樹來說，Var(C(x)) 不可忽視，即單一分類樹自身的方差對分類誤差的貢獻(xiàn)是固有的。如果我們能夠使用 E[C(x)] 代替 C(x) 則可以避免單一分類樹自身的方差產(chǎn)生的分類誤差。

當(dāng)然，在實(shí)際中，E[C(x)] 是未知的，但是我們可以通過平均大量不同單顆分類樹的分類結(jié)果來近似得到 E[C(x)]，使它們各自的方差相互抵消。根據(jù)大數(shù)定理，大量不同分類樹的平均結(jié)果將有效的逼近 E[C(x)]。這便是“少樹”服從“多樹”帶來的優(yōu)勢。

本文第一節(jié)提到的 bagging（Breiman 1996a, 1996b），boosting（Freund and Schapire 1996），以及隨機(jī)森林（Breiman 2001）等算法都是使用了大量多顆分類樹取代單一分類樹對數(shù)據(jù)進(jìn)行分類的經(jīng)典算法。它們在不改變偏差的前提下有效的降低了分類樹自身的方差，從而顯著提高了分類準(zhǔn)確性。我們將在本篇的下期中介紹這些高級算法。

參考文獻(xiàn)

Breiman, L. (1996a). Bagging predictors. Machine Learning 24, 123 – 140.

Breiman, L. (1996b). Heuristics of instability and stabilization in model selection. Ann. Statist. 24, 2350 – 2383.

Breiman, L. (2001). Random forests. Machine Learning 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.

免責(zé)聲明：入市有風(fēng)險(xiǎn)，投資需謹(jǐn)慎。在任何情況下，本文的內(nèi)容、信息及數(shù)據(jù)或所表述的意見并不構(gòu)成對任何人的投資建議。在任何情況下，本文作者及所屬機(jī)構(gòu)不對任何人因使用本文的任何內(nèi)容所引致的任何損失負(fù)任何責(zé)任。除特別說明外，文中圖表均直接或間接來自于相應(yīng)論文，僅為介紹之用，版權(quán)歸原作者和期刊所有。