數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法之—CART算法(附代碼)
簡(jiǎn)介
CART與C4.5類似,是決策樹算法的一種。此外,常見的決策樹算法還有ID3,這三者的不同之處在于特征的劃分:
- ID3:特征劃分基于信息增益
- C4.5:特征劃分基于信息增益比
- CART:特征劃分基于基尼指數(shù)
基本思想
CART假設(shè)決策樹是二叉樹,內(nèi)部結(jié)點(diǎn)特征的取值為“是”和“否”,左分支是取值為“是”的分支,右分支是取值為“否”的分支。這樣的決策樹等價(jià)于遞歸地二分每個(gè)特征,將輸入空間即特征空間劃分為有限個(gè)單元,并在這些單元上確定預(yù)測(cè)的概率分布,也就是在輸入給定的條件下輸出的條件概率分布。
CART算法由以下兩步組成:
- 決策樹生成:基于訓(xùn)練數(shù)據(jù)集生成決策樹,生成的決策樹要盡量大;
- 決策樹剪枝:用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹,這時(shí)損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。
CART決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。CART決策樹既可以用于分類也可以用于回歸。本文我們僅討論用于分類的CART。對(duì)分類樹而言,CART用Gini系數(shù)最小化準(zhǔn)則來(lái)進(jìn)行特征選擇,生成二叉樹。 CART生成算法如下:
- 輸入:訓(xùn)練數(shù)據(jù)集D,停止計(jì)算的條件:
- 輸出:CART決策樹。
根據(jù)訓(xùn)練數(shù)據(jù)集,從根結(jié)點(diǎn)開始,遞歸地對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行以下操作,構(gòu)建二叉決策樹:
設(shè)結(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為D,計(jì)算現(xiàn)有特征對(duì)該數(shù)據(jù)集的Gini系數(shù)。此時(shí),對(duì)每一個(gè)特征A,對(duì)其可能取的每個(gè)值a,根據(jù)樣本點(diǎn)對(duì)A=a的測(cè)試為“是”或 “否”將D分割成D1和D2兩部分,計(jì)算A=a時(shí)的Gini系數(shù)。
在所有可能的特征A以及它們所有可能的切分點(diǎn)a中,選擇Gini系數(shù)最小的特征及其對(duì)應(yīng)的切分點(diǎn)作為最優(yōu)特征與最優(yōu)切分點(diǎn)。依最優(yōu)特征與最優(yōu)切分點(diǎn),從現(xiàn)結(jié)點(diǎn)生成兩個(gè)子結(jié)點(diǎn),將訓(xùn)練數(shù)據(jù)集依特征分配到兩個(gè)子結(jié)點(diǎn)中去。
對(duì)兩個(gè)子結(jié)點(diǎn)遞歸地調(diào)用步驟l~2,直至滿足停止條件。
生成CART決策樹。
算法停止計(jì)算的條件是結(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閾值,或樣本集的Gini系數(shù)小于預(yù)定閾值(樣本基本屬于同一類),或者沒有更多特征。
代碼
代碼已在github上實(shí)現(xiàn)(調(diào)用sklearn),這里也貼出來(lái)
測(cè)試數(shù)據(jù)集為MNIST數(shù)據(jù)集,獲取地址為train.csv
運(yùn)行結(jié)果


























