? 之前泛泛看了下了Random Forest和決策樹(shù)，現(xiàn)在落實(shí)到一個(gè)具體決策樹(shù)算法：CART(Classification and Regression Tree)。

? CART是1984年由Breiman, Friedman, Olshen, Stone提出的一個(gè)決策樹(shù)算法，雖然不是第一個(gè)機(jī)器學(xué)習(xí)領(lǐng)域的決策樹(shù)，但卻是第一個(gè)有著復(fù)雜的統(tǒng)計(jì)學(xué)和概率論理論保證的決策樹(shù)(這些話太學(xué)術(shù)了，引自參考文獻(xiàn)[2])。

? CART是一個(gè)二叉決策樹(shù)，亦即決策樹(shù)的每個(gè)內(nèi)部節(jié)點(diǎn)(決策節(jié)點(diǎn))最多有兩個(gè)分支。因?yàn)橹坝? 博文 介紹過(guò)ID3和C4.5算法，所以這里只從確定最佳分裂屬性和剪枝兩方面介紹CART。

? 1. 確定最佳分裂屬性(和最佳分裂點(diǎn))

? 我們這里只考慮連續(xù)值的情況。對(duì)于每個(gè)輸入屬性的每個(gè)可能的分裂點(diǎn)(分裂點(diǎn)即相鄰兩個(gè)連續(xù)值的中點(diǎn))，我們計(jì)算每個(gè)劃分 Gini指標(biāo) ： ，然后對(duì)該分裂點(diǎn)的兩個(gè)劃分的Gini指標(biāo)求加權(quán)和。我們選取Gini指標(biāo)最小的那個(gè)輸入屬性的分裂點(diǎn)進(jìn)行劃分。

? 按照以上規(guī)則生成一個(gè)完全增長(zhǎng)的決策樹(shù)，不需要任何停止條件。

? 2. 剪枝

? 因?yàn)樯弦徊缴傻臎Q策樹(shù)是沒(méi)有停止條件的，所以這個(gè)決策樹(shù)可能會(huì)非常大，對(duì)訓(xùn)練數(shù)據(jù)很可能會(huì)過(guò)度擬合，所以需要對(duì)決策樹(shù)進(jìn)行后剪枝。

? CART算法采用的是 Cost-Complexy剪枝 :

? 我們用 來(lái)衡量一棵子樹(shù)的代價(jià)復(fù)雜度。其中R(T)代表將這個(gè)子樹(shù)替換為葉子節(jié)點(diǎn)后所帶來(lái)的誤差的增加，number-of-leaves為子樹(shù)T的葉子節(jié)點(diǎn)的個(gè)數(shù)，α不是一個(gè)常數(shù)，而是一個(gè)從0開(kāi)始增大到無(wú)窮大的數(shù)。對(duì)于決策樹(shù)T，我們?cè)讦敛皇且粋€(gè)常數(shù)，而是一個(gè)從0開(kāi)始增大到無(wú)窮大的數(shù)。逐步增加的過(guò)程中，每次選擇使Rα最小的子樹(shù)，并將之替換為一個(gè)葉子節(jié)點(diǎn)，對(duì)替換后的樹(shù)迭代執(zhí)行以上步驟。

? 上述過(guò)程可能略顯復(fù)雜，我們可以用另外一個(gè)等價(jià)的剪枝方法來(lái)得到相同的結(jié)果： Weakest-Link-Pruning ：

? (1)對(duì)于所有的子樹(shù)STi，我們?cè)噲D用合適的葉子節(jié)點(diǎn)來(lái)代替STi，然后計(jì)算增加的誤差E與STi的葉子節(jié)點(diǎn)的比值。我們選擇比值最小的那個(gè)子樹(shù)STj，用合適的葉子節(jié)點(diǎn)代替之。

? (2)重復(fù)迭代以上步驟，每次都替換掉一棵子樹(shù)。我們會(huì)得到從完全增長(zhǎng)的樹(shù)T0到只有根節(jié)點(diǎn)一個(gè)決策節(jié)點(diǎn)的樹(shù)Tn的一系列決策樹(shù)：T0,T1,.....Tn。然后我們用獨(dú)立的驗(yàn)證集(我們可以從可用數(shù)據(jù)集中抽取三分之一作為驗(yàn)證集，剩下的三分之二作為訓(xùn)練集)來(lái)驗(yàn)證各個(gè)決策樹(shù)的分類(lèi)準(zhǔn)確性。選取準(zhǔn)確性最高的決策樹(shù)為最終的CART決策樹(shù)。

參考文獻(xiàn)：

[1] CART算法學(xué)習(xí)及實(shí)現(xiàn)

[2] 機(jī)器學(xué)習(xí)十大算法：CART

[3] Complexity-Based Evaluation Of Rule-Based Expert Systems

?

機(jī)器學(xué)習(xí)-CART決策樹(shù)