作者：石川

摘要：裝袋法、隨機(jī)森林以及提升法是三種有效的集合學(xué)習(xí)元算法。它們可以提高分類樹(shù)的分類準(zhǔn)確性。

1 前文回顧

前篇《“少樹(shù)”服從“多樹(shù)”（上）》中系統(tǒng)介紹了單顆分類樹(shù)算法。同時(shí)，我們指出分類樹(shù)算法不夠穩(wěn)定，對(duì)訓(xùn)練樣本數(shù)據(jù)比較敏感，造成其固有的方差，而方差又是預(yù)測(cè)誤差的原因之一。為了有效降低方差，使用多顆分類樹(shù)然后平均它們的結(jié)果作為最終的結(jié)果便成為一種自然的選擇。在這方面，裝袋算法（bagging）、提升算法（boosting）、隨機(jī)森林（random forest）都是很好的方法。它們都是機(jī)器學(xué)習(xí)領(lǐng)域的集成學(xué)習(xí)元算法（ensemble learning?meta?algorithm）。元算法的意思是算法的算法；如果說(shuō)算法的作用對(duì)象是數(shù)據(jù)，那么元算法的作用對(duì)象就是算法。它們可以理解為一種作用于基礎(chǔ)分類算法上的技術(shù)，以取得更佳的分類效果。

本期就分別介紹并比較這三種技術(shù)。為了更好的介紹它們，首先來(lái)看一個(gè)名為自助抽樣法的概念。

2 自助抽樣法

有放回的的重采樣：自助抽樣法（bootstrapping）是指從給定的數(shù)據(jù)集中有放回的重采樣（resampling with replacement）。在這個(gè)定義中，“有放回”是核心。舉個(gè)例子。假設(shè)我們有標(biāo)號(hào) 1 到 10 的 10 個(gè)小球，放在一個(gè)袋子里。下面我們“有放回”地不斷地從袋子里隨機(jī)抽出小球。假設(shè)第一次抽取中，我們抽出了 3 號(hào)小球，有放回則是說(shuō)我們?cè)谙乱淮纬槿≈鞍?3 號(hào)小球放回到袋子里，即在第二次抽取的時(shí)候，我們?nèi)匀挥锌赡茉俅纬榈?3 號(hào)小球（它和其他 9 個(gè)球被抽到的概率是一樣的），這便是有放回的含義。作為對(duì)比，生活中更多的是“無(wú)放回抽取”，比如體彩 36 中 7 或者歐冠抽簽，抽出的小球都不會(huì)再放回池子中。

隨機(jī)生成大量不同的樣本：讓我們?nèi)匀豢紤] 10 個(gè)小球這個(gè)例子。假設(shè)我們有放回的從口袋里抽取 10 個(gè)球，得到一個(gè)小球序號(hào)的序列 3，5，6，1，1，7，9，10，2，6（即 1 號(hào)和 6 號(hào)球被取出兩次；4 號(hào)和 8 號(hào)球沒(méi)有被抽到）。這便是一個(gè)重采樣得到的樣本序列。通過(guò)進(jìn)行大量的有放回的重采樣，我們可以用原始的樣本生成許多不同的新的樣本序列。這么做的意義重大。

自助抽樣的統(tǒng)計(jì)學(xué)意義：自助抽樣的目的是幫助我們推斷樣本統(tǒng)計(jì)量（sample statistic）在估計(jì)總體統(tǒng)計(jì)量（population statistic）時(shí)的誤差。比如我們想知道全世界所有人的平均身高（這個(gè)平均身高就是總體統(tǒng)計(jì)量，因?yàn)槲覀兛紤]的全世界所有人）。然而，我們不可能給全世界約 74 億人都測(cè)量身高再計(jì)算平均值。因此，我們只能對(duì)一小部分樣本進(jìn)行分析。假設(shè)我們?cè)谌澜珉S機(jī)抽取了 5 萬(wàn)人、測(cè)量了這些人的身高，并計(jì)算出這 5 萬(wàn)人的平均身高為 1.72 米，這便是樣本統(tǒng)計(jì)量。當(dāng)我們用 1.72 米作為全世界總?cè)丝谄骄砀叩墓烙?jì)時(shí)，我們無(wú)法回答這個(gè)估計(jì)是否準(zhǔn)確、誤差是多少。這是因?yàn)槲覀冎挥羞@一個(gè) 5 萬(wàn)人的樣本；我們沒(méi)有更多的其他的樣本。這時(shí)，有放回的重采樣便可大顯身手。

具體的，我們可以把這 5 萬(wàn)人看作是原始數(shù)據(jù)，通過(guò)進(jìn)行大量的有放回重采樣（比如 10000 次），得到足夠多的樣本大小為 5 萬(wàn)人的不同的樣本序列。這個(gè)分析方法的核心和巧妙之處是：我們暫時(shí)拋開(kāi)那個(gè)真實(shí)的總體（74 億人），而把這 5 萬(wàn)人就當(dāng)作是我們分析的“總體”，并把經(jīng)過(guò)有放回重采樣得到的 10000 個(gè)樣本作為基于這個(gè) 5 萬(wàn)人“總體”得到的“樣本”。

通過(guò)計(jì)算這 10000 個(gè)"樣本"的平均身高，得到“樣本”平均身高的分布。由于“總體”就是那 5 萬(wàn)人；它的所有統(tǒng)計(jì)量都是已知的，因此我們可以準(zhǔn)確地計(jì)算這 10000 個(gè)“樣本”計(jì)算出的樣本統(tǒng)計(jì)量在推斷這 5 萬(wàn)人“總體”的總體統(tǒng)計(jì)量的誤差，記為 e'。更近一步，不要忘了這 5 萬(wàn)人其實(shí)是從那 74 億人真實(shí)總體得到的一個(gè)真實(shí)樣本。令 e 表示用這 5 萬(wàn)人樣本的樣本統(tǒng)計(jì)量推斷 74 億人總體的總體統(tǒng)計(jì)量時(shí)的誤差。如果這 5 萬(wàn)人的概率分布是那 74 億人的概率分布的一個(gè)合理的近似，那么我們就可以用 e' 來(lái)估計(jì) e。

3 裝袋算法

何為裝袋算法：裝袋算法（bagging）由 Breiman (1996a, 1996b) 發(fā)明。Bagging 一詞從英文?Bootstrap?aggregating?而來(lái)，中文翻譯為很拗口的引導(dǎo)聚類算法，為了好記又按 bagging 直譯取名為裝袋算法。為了理解它的含義，我們不用管那個(gè)中文翻譯，只需要把這兩個(gè)單詞拆開(kāi)來(lái)看：Bootstrap aggregating = Bootstrap + aggregate。前一個(gè)詞就代表了上一節(jié)介紹的自助抽樣，而后一個(gè)詞就是聚合之意。它的意思是：

裝袋為什么有效：分類樹(shù)本身是一種不穩(wěn)定的分類器，對(duì)訓(xùn)練數(shù)據(jù)的敏感性比較高。訓(xùn)練數(shù)據(jù)的特征值的一些細(xì)微擾動(dòng)可能造成分類樹(shù)結(jié)構(gòu)的不同，從而使得預(yù)測(cè)結(jié)果不同。這使得分類樹(shù)的預(yù)測(cè)方差比較大。一個(gè)分類算法的預(yù)測(cè)誤差由偏差和誤差兩部分造成（具體的請(qǐng)參閱 Sutton 2005）。裝袋算法通過(guò)聚合大量單一分類樹(shù)可以有效的減少單一分類樹(shù)的預(yù)測(cè)方差。誠(chéng)然，聚合也會(huì)在一定程度上增加預(yù)測(cè)偏差，但增加幅度有限，可以被大大減少的方差所抵消。因此，對(duì)于分類樹(shù)這種自身預(yù)測(cè)偏差較小，但是預(yù)測(cè)方差較大的分類器來(lái)說(shuō)，裝袋算法可以非常有效的提高其整體的預(yù)測(cè)準(zhǔn)確性。

在實(shí)際應(yīng)用中，Hastie et al. (2001) 指出使用 50 到 100 個(gè)重采樣的樣本便可以取得理想的結(jié)果（更多的樣本也無(wú)法明顯地進(jìn)一步提升準(zhǔn)確性）。上一篇中提到為了確定分類樹(shù)的最佳尺寸，需要使用 K 折交叉驗(yàn)證，這意味著找到最優(yōu)單顆分類樹(shù)都需要一定的計(jì)算時(shí)間。然而，當(dāng)我們采用裝袋算法時(shí)，可以避免使用交叉驗(yàn)證。對(duì)于每一棵分類樹(shù)，我們都可以使用原始的樣本數(shù)據(jù)作為測(cè)試集來(lái)檢驗(yàn)其準(zhǔn)確性。又或者，我們可以通過(guò)計(jì)算袋外誤差（out-of-bag error）來(lái)計(jì)算。計(jì)算袋外誤差時(shí)，對(duì)于訓(xùn)練樣本中的每一個(gè)點(diǎn)，使用所有那些用不包含該點(diǎn)的重采樣樣本所訓(xùn)練出的分類樹(shù)對(duì)其分類（這就是袋外的意思），和該點(diǎn)的實(shí)際類別比較看看是否分類正確。平均所有樣本點(diǎn)的分類正誤便得到袋外誤差。雖然裝袋算法要計(jì)算許多分類樹(shù)，但是由于它可以避免使用交叉驗(yàn)證，因此裝袋算法的計(jì)算時(shí)間仍然是可接受的。

最后用下面這個(gè)例子直觀的說(shuō)明裝袋法的好處。假設(shè)待分類的數(shù)據(jù)是二維平面上的點(diǎn)，每個(gè)點(diǎn)都可以用坐標(biāo) (x1, x2) 表示。下圖左一為所有點(diǎn)表示的總體，0 和 1 表示每一個(gè)點(diǎn)的分類，黑色的圓圈表示決策邊界（decision boundary）。假設(shè)我們從總體中隨機(jī)抽出 200 個(gè)點(diǎn)，并用它們來(lái)訓(xùn)練單一分類樹(shù)，得到的分類決策邊界如下圖中間那副所示。可以看到該決策邊界和真實(shí)的邊界差別非常明顯，這意味著這樣一個(gè)分類樹(shù)的分類誤差是非常可觀的。下圖右一為使用了裝袋算法后的結(jié)果?？梢郧宄目吹剑覀兊挠?xùn)練數(shù)據(jù)仍然還是那 200 個(gè)點(diǎn)，但是經(jīng)過(guò)重采樣再聚合，最后得到的決策邊界比單一分類樹(shù)的決策邊界大大平滑了，更加貼近真實(shí)的決策邊界，顯著提升了分類準(zhǔn)確性。

4 隨機(jī)森林

隨機(jī)森林（random forests）由 Breiman (2001) 提出，它和裝袋算法非常類似，是裝袋算法的進(jìn)階版。由前述可知，由于考慮了很多分類樹(shù)，裝袋算法本身已經(jīng)是“森林”了。因此，隨機(jī)森林和裝袋算法的唯一差別就在“隨機(jī)”兩個(gè)字上。

在裝袋法中，不同的樣本集都是通過(guò)對(duì)原始數(shù)據(jù)重采樣得到的。因此，這些樣本集——雖然它們之間有一定的差異——仍然是有很高的相關(guān)性的。在提出隨機(jī)森林的時(shí)候，Breiman?證明了裝袋算法的分類誤差的上限是和樣本集之間的相關(guān)性有關(guān)的。只有想辦法降低樣本集之間的相關(guān)性，才能進(jìn)一步提高裝袋法的效果。因此，他提出引入隨機(jī)性。

具體的，隨機(jī)森林算法在通過(guò)重采樣構(gòu)造大量樣本集時(shí)和裝袋算法并無(wú)差異。但是，在基于每個(gè)樣本集訓(xùn)練分類樹(shù)時(shí)，隨機(jī)森林算法在分類特征選擇時(shí)引入了隨機(jī)性。該算法在選擇當(dāng)前的分類特征時(shí)，從所有的候選特征中先隨機(jī)選出一個(gè)子集，然后再?gòu)脑撟蛹羞x擇出最好的分類特征。如果說(shuō)裝袋法僅僅考慮了樣本的隨機(jī)性，那么隨機(jī)森林既考慮了樣本隨機(jī)性又考慮了特征隨機(jī)性，從而降低了不同分類樹(shù)之間的相關(guān)性。

5 提升算法

提升算法（boosting）的出發(fā)點(diǎn)是想回答這樣一個(gè)問(wèn)題，即一組“弱學(xué)習(xí)者”（week learners）能否通過(guò)集合學(xué)習(xí)生成一個(gè)“強(qiáng)學(xué)習(xí)者”（strong learner）？弱學(xué)習(xí)者一般是但不限于一個(gè)分類效果只比隨機(jī)分類強(qiáng)一點(diǎn)點(diǎn)的分類器（因此單一分類樹(shù)——雖然它有不錯(cuò)的分類效果——仍然也可以在作為弱學(xué)習(xí)者）；強(qiáng)學(xué)習(xí)者指分類器的結(jié)果非常接近真值。因?yàn)樗惴ò讶鯇W(xué)習(xí)者變成強(qiáng)學(xué)習(xí)者，故得名提升算法。

Freund and Schapire (1996) 提出了?AdaBoost?算法，用于提升分類器的效果。它通過(guò)迭代，不斷地對(duì)原始樣本數(shù)據(jù)進(jìn)行有權(quán)重的分類。在迭代中的每一步中，樣本點(diǎn)的權(quán)重由上一步分類器的分類誤差計(jì)算得到。因此，該算法在每次迭代時(shí)，都會(huì)增加錯(cuò)誤分類樣本點(diǎn)的權(quán)重，使得新的分類器更有可能正確地對(duì)這些錯(cuò)誤點(diǎn)分類。

我們通過(guò)下面這個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明這個(gè)過(guò)程。假設(shè)我們的樣本數(shù)據(jù)屬于紅藍(lán)了兩個(gè)不同的類型（如下圖(1)所示）。首先我們賦予所有樣本點(diǎn)等權(quán)重，并用一個(gè)（弱）分類器來(lái)進(jìn)行分類，分類邊界由虛線表示?？梢?jiàn)，一個(gè)屬于紅色的樣本和兩個(gè)屬于藍(lán)色的樣本被分類錯(cuò)誤。在第二步迭代中，這三個(gè)點(diǎn)的權(quán)重被增大（其他點(diǎn)的權(quán)重相應(yīng)被減?。缓筮M(jìn)行第二次分類，得到新的分類邊界（圖(2)）。這時(shí)，有兩個(gè)藍(lán)色的樣本點(diǎn)被分類錯(cuò)誤，因此在第三步迭代中，它們的權(quán)重被增大，然后進(jìn)行第三次分類得到新的分類邊界。繼續(xù)重復(fù)這個(gè)過(guò)程直到迭代達(dá)到一定次數(shù)后，比如 M 次。對(duì)于任何一個(gè)新的待分類樣本點(diǎn)，將這 M 個(gè)（弱）分類器按照它們各自的分類誤差為權(quán)重進(jìn)行加和，得到的結(jié)果就是對(duì)新樣本點(diǎn)的分類結(jié)果。

從上面的描述可知，在迭代的每一步，新的分類結(jié)果都會(huì)傾向于更正確地對(duì)之前分類錯(cuò)誤的樣本進(jìn)行分類。這使得不同迭代步之間的分類邊界有很大得差異，從而造成了不同分類結(jié)果之間的低相關(guān)性。這也是這個(gè)算法能夠有效降低分類誤差的原因。隨機(jī)森林的發(fā)明者 Breiman 也提出了一種猜想，即 AdaBoost 可以被看作是一種特殊的隨機(jī)森林。關(guān)于 AdaBoost 算法的具體數(shù)學(xué)表達(dá)式和流程，感興趣的讀者請(qǐng)參考 Freund and Schapire (1996)。

6 效果比較

毋庸置疑，裝袋、隨機(jī)森林、以及提升這三種元算法都大大改善了單一分類樹(shù)的分類效果。就它們之間的比較來(lái)說(shuō)，隨機(jī)森林和提升法由于有效降低了不同分類樹(shù)之間的相關(guān)性，它們的效果均優(yōu)于裝袋法。下圖為裝袋法和提升法在某分類問(wèn)題上的誤差比較。隨著分類樹(shù)個(gè)數(shù)的增加，它們的分類誤差都逐漸收斂，但是提升法的誤差要明顯小于裝袋法。

然而，隨機(jī)森林和提升法孰優(yōu)孰劣，并沒(méi)有特別肯定的說(shuō)法。一些學(xué)者認(rèn)為提升法要優(yōu)于隨機(jī)森林，但是隨機(jī)森林的發(fā)明者 Breiman 指出該方法要比提升法有更好的效果。從大量業(yè)界的實(shí)際分類問(wèn)題的結(jié)果來(lái)看，這兩個(gè)方法都是非常優(yōu)秀的分類算法，它們的效果在很多問(wèn)題上和神經(jīng)網(wǎng)絡(luò)以及支持向量機(jī)不相上下。

參考文獻(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.

Hastie, T., Tibshirani, R., Friedman, J. (2001). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer-Verlag, New York.

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ù)或所表述的意見(jiàn)并不構(gòu)成對(duì)任何人的投資建議。在任何情況下，本文作者及所屬機(jī)構(gòu)不對(duì)任何人因使用本文的任何內(nèi)容所引致的任何損失負(fù)任何責(zé)任。除特別說(shuō)明外，文中圖表均直接或間接來(lái)自于相應(yīng)論文，僅為介紹之用，版權(quán)歸原作者和期刊所有。