人工智能之機(jī)器學(xué)習(xí)CART算法解析

人工智能之機(jī)器學(xué)習(xí)主要有三大類：1）分類；2）回歸；3）聚類。今天我們重點(diǎn)探討一下CART算法。

我們知道十大機(jī)器學(xué)習(xí)中決策樹算法占有兩席位置，即C4．5算法和CART算法，可見CART算法的重要性。下面重點(diǎn)介紹CART算法。

不同于ID3與C4．5，CART為一種二分決策樹，是滿二叉樹。CART算法由Breiman等人在 1984 年提出，它采用與傳統(tǒng)統(tǒng)計(jì)學(xué)完全不同的方式構(gòu)建預(yù)測準(zhǔn)則，它是以二叉樹的形式給出，易于理解、使用和解釋。由CART 模型構(gòu)建的預(yù)測樹在很多情況下比常用的統(tǒng)計(jì)方法構(gòu)建的代數(shù)學(xué)預(yù)測準(zhǔn)則更加準(zhǔn)確，且數(shù)據(jù)越復(fù)雜、變量越多，算法的優(yōu)越性就越顯著。

CART算法既可用于分類也可用于回歸。CART算法被稱為數(shù)據(jù)挖掘領(lǐng)域內(nèi)里程碑式的算法。

CART（Classification andRegression Tree） 分類回歸樹是一種決策樹構(gòu)建算法。CART是在給定輸入隨機(jī)變量X條件下輸出隨機(jī)變量Y的條件概率分布的學(xué)習(xí)方法。CART假設(shè)決策樹是二叉樹，內(nèi)部結(jié)點(diǎn)特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價(jià)于遞歸地二分每個(gè)特征，將輸入空間即特征空間劃分為有限個(gè)單元，并在這些單元上確定預(yù)測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。

CART算法既可以處理離散型問題，也可以處理連續(xù)型問題。這種算法在處理連續(xù)型問題時(shí)，主要通過使用二元切分來處理連續(xù)型變量，即特征值大于某個(gè)給定的值就走左子樹，或者就走右子樹。

CART算法組成如下：

1）決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大；自上而下從根開始建立節(jié)點(diǎn)，在每個(gè)節(jié)點(diǎn)處要選擇一個(gè)最好（不同算法使用不同指標(biāo)來定義＂最好＂）的屬性來分裂，使得子節(jié)點(diǎn)中的訓(xùn)練數(shù)據(jù)集盡量的純。

2）決策樹剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹，這時(shí)損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。這里用代價(jià)復(fù)雜度剪枝CCP（Cost－Complexity Pruning）。

決策樹的生成就是通過遞歸地構(gòu)建二叉決策樹的過程，對(duì)回歸樹用平方誤差最小化準(zhǔn)則，對(duì)分類樹用基尼指數(shù)最小化準(zhǔn)則，進(jìn)行特征選擇，生成二叉樹。

1）回歸樹生成

回歸樹采用均方誤差作為損失函數(shù)，樹生成時(shí)會(huì)遞歸的按最優(yōu)特征與最優(yōu)特征下的最優(yōu)取值對(duì)空間進(jìn)行劃分，直到滿足停止條件為止，停止條件可以人為設(shè)定，比如當(dāng)切分后的損失減小值小于給定的閾值 ε，則停止切分，生成葉節(jié)點(diǎn)。對(duì)于生成的回歸樹，每個(gè)葉節(jié)點(diǎn)的類別為落到該葉節(jié)點(diǎn)數(shù)據(jù)的標(biāo)簽的均值。

回歸樹為一棵二叉樹，每次都是按特征下的某個(gè)取值進(jìn)行劃分，每一個(gè)內(nèi)部節(jié)點(diǎn)都是做一個(gè)對(duì)應(yīng)特征的判斷，直至走到葉節(jié)點(diǎn)得到其類別，構(gòu)建這棵樹的難點(diǎn)在于如何選取最優(yōu)的切分特征與切分特征對(duì)應(yīng)的切分變量。

回歸樹與模型樹既可以處理連續(xù)特征也可以處理離散特征。

回歸樹生成算法如下：

輸入：訓(xùn)練數(shù)據(jù)集 D＝｛（x1，y1），（x2，y2），…，（xN，yN）｝

輸出：回歸樹 T

1）求解選擇切分特征 j 與切分特征取值 s ，j 將訓(xùn)練集 D 劃分為兩部分，R1 與R2 ，依照（j，s）切分后如下：

R1（j，s）＝｛xi｜xji≤s｝ R2（j，s）＝｛xi｜xji＞s｝

c1＝1N1∑xi∈R1yi c2＝1N2∑xi∈R2yi

2）遍歷所有可能的解（j，s），找到最優(yōu)的 （j＊，s＊） ，最優(yōu)的解使得對(duì)應(yīng)損失最小，按照最優(yōu)特征（j＊，s＊）來切分即可。

Min ｛ ∑ （yi–c1）＾2 ＋∑ （yi–c2）＾2 ｝

j，s xi∈R1 xi∈R2

3）遞歸調(diào)用 1）和2），直到滿足停止條件。

4）返回決策樹 T。

回歸樹主要采用了分治策略，對(duì)于無法用唯一的全局線性回歸來優(yōu)化的目標(biāo)進(jìn)行分而治之，進(jìn)而取得比較準(zhǔn)確的結(jié)果，但分段取均值并不是一個(gè)明智的選擇，可以考慮將葉節(jié)點(diǎn)設(shè)置為一個(gè)線性函數(shù)，這便是所謂的分段線性模型樹。實(shí)驗(yàn)表明：模型樹效果比回歸樹的效果要好一些。模型樹只需在回歸樹的基礎(chǔ)上稍加修改即可，對(duì)于分到葉節(jié)點(diǎn)的數(shù)據(jù)，采用線性回歸的最小均方損失來計(jì)算該節(jié)點(diǎn)的損失。

2）分類樹生成

分類樹是CART中用來分類的，不同于 ID3 與 C4．5，CART分類樹采用基尼指數(shù)來選擇最優(yōu)的切分特征，而且每次都是二分。

基尼指數(shù)是一個(gè)類似與熵的概念，對(duì)于一個(gè)有 K 種狀態(tài)對(duì)應(yīng)的概率為 p1，p2，…，pK的隨機(jī)變量 X ，其基尼指數(shù)Gini定義如下：

Gini（X）＝∑pk（1？pk）＝1？∑kp2k

k k

在已知特征 A條件下集合 D 的基尼指數(shù)：

Gini（D，A）＝（｜D1｜／｜D｜）＊Gini（D1）＋（｜D2｜／｜D｜）＊Gini（D2）

Gini（D，A）取值越大，樣本的不確定性也越大，這一點(diǎn)與熵類似，所以選擇特征 A 的標(biāo)準(zhǔn)是 Gini（D，A） 的取值越小越好。