導(dǎo)讀：人工智能機(jī)器學(xué)習(xí)有關(guān)算法內(nèi)容，今天我們重點探討一下CART算法。
繼上兩篇決策樹算法之ID3算法和ID3的改進(jìn)算法－C4．5算法后，本文繼續(xù)討論另一種二分決策樹算法－CART算法。我們知道十大機(jī)器學(xué)習(xí)中決策樹算法占有兩席位置，即C4．5算法和CART算法，可見CART算法的重要性。下面重點介紹CART算法。
不同于ID3與C4．5，CART為一種二分決策樹，是滿二叉樹。CART算法由Breiman等人在 1984 年提出，它采用與傳統(tǒng)統(tǒng)計學(xué)完全不同的方式構(gòu)建預(yù)測準(zhǔn)則，它是以二叉樹的形式給出，易于理解、使用和解釋。由CART 模型構(gòu)建的預(yù)測樹在很多情況下比常用的統(tǒng)計方法構(gòu)建的代數(shù)學(xué)預(yù)測準(zhǔn)則更加準(zhǔn)確，且數(shù)據(jù)越復(fù)雜、變量越多，算法的優(yōu)越性就越顯著。
CART算法既可用于分類也可用于回歸。CART算法被稱為數(shù)據(jù)挖掘領(lǐng)域內(nèi)里程碑式的算法。
CART算法概念：
CART（ClassificaTIon andRegression Tree）分類回歸樹是一種決策樹構(gòu)建算法。CART是在給定輸入隨機(jī)變量X條件下輸出隨機(jī)變量Y的條件概率分布的學(xué)習(xí)方法。CART假設(shè)決策樹是二叉樹，內(nèi)部結(jié)點特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價于遞歸地二分每個特征，將輸入空間即特征空間劃分為有限個單元，并在這些單元上確定預(yù)測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。
CART算法既可以處理離散型問題，也可以處理連續(xù)型問題。這種算法在處理連續(xù)型問題時，主要通過使用二元切分來處理連續(xù)型變量，即特征值大于某個給定的值就走左子樹，或者就走右子樹。
CART算法組成：1）決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大；自上而下從根開始建立節(jié)點，在每個節(jié)點處要選擇一個最好（不同算法使用不同指標(biāo)來定義＂最好＂）的屬性來分裂，使得子節(jié)點中的訓(xùn)練數(shù)據(jù)集盡量的純。
2）決策樹剪枝：用驗證數(shù)據(jù)集對已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹，這時損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。這里用代價復(fù)雜度剪枝CCP（Cost－Complexity Pruning）。
決策樹的生成就是通過遞歸地構(gòu)建二叉決策樹的過程，對回歸樹用平方誤差最小化準(zhǔn)則，對分類樹用基尼指數(shù)最小化準(zhǔn)則，進(jìn)行特征選擇，生成二叉樹。
CART決策樹生成： 1）回歸樹生成回歸樹采用均方誤差作為損失函數(shù)，樹生成時會遞歸的按最優(yōu)特征與最優(yōu)特征下的最優(yōu)取值對空間進(jìn)行劃分，直到滿足停止條件為止，停止條件可以人為設(shè)定，比如當(dāng)切分后的損失減小值小于給定的閾值 ε，則停止切分，生成葉節(jié)點。對于生成的回歸樹，每個葉節(jié)點的類別為落到該葉節(jié)點數(shù)據(jù)的標(biāo)簽的均值。
回歸樹為一棵二叉樹，每次都是按特征下的某個取值進(jìn)行劃分，每一個內(nèi)部節(jié)點都是做一個對應(yīng)特征的判斷，直至走到葉節(jié)點得到其類別，構(gòu)建這棵樹的難點在于如何選取最優(yōu)的切分特征與切分特征對應(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)的解使得對應(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。
回歸樹主要采用了分治策略，對于無法用唯一的全局線性回歸來優(yōu)化的目標(biāo)進(jìn)行分而治之，進(jìn)而取得比較準(zhǔn)確的結(jié)果，但分段取均值并不是一個明智的選擇，可以考慮將葉節(jié)點設(shè)置為一個線性函數(shù)，這便是所謂的分段線性模型樹。實驗表明：模型樹效果比回歸樹的效果要好一些。模型樹只需在回歸樹的基礎(chǔ)上稍加修改即可，對于分到葉節(jié)點的數(shù)據(jù)，采用線性回歸的最小均方損失來計算該節(jié)點的損失。
2）分類樹生成分類樹是CART中用來分類的，不同于 ID3 與 C4．5，CART分類樹采用基尼指數(shù)來選擇最優(yōu)的切分特征，而且每次都是二分。
基尼指數(shù)是一個類似與熵的概念，對于一個有 K 種狀態(tài)對應(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）取值越大，樣本的不確定性也越大，這一點與熵類似，所以選擇特征 A 的標(biāo)準(zhǔn)是 Gini（D，A） 的取值越小越好。
分類樹生成算法如下：
輸入：訓(xùn)練數(shù)據(jù)集 D＝｛（x1，y1），（x2，y2），…，（xN，yN）｝，停止條件
輸出：分類樹 T
1）利用特征 A 的取值 a 將數(shù)據(jù)分為兩部分，計算 A＝a時的基尼系數(shù)：
Gini（D，A）＝（｜D1｜／｜D｜）＊Gini（D1）＋（｜D2｜／｜D｜）＊Gini（D2）
2）對整個數(shù)據(jù)集中所有的可能特征 A 以及其可能取值 a 選取基尼系數(shù)最小的特征 A＊ 與特征下的取值 a＊，來將數(shù)據(jù)集切分，將數(shù)據(jù) D1、D2 分到兩個子節(jié)點中去。
3）對子節(jié)點遞歸調(diào)用 1）和2） ，直至滿足停止條件
4）返回 CART 樹 T
該算法停止條件可以是節(jié)點中的樣本數(shù)不能小于給定閾值，或者樣本集的基尼系數(shù)小于給定閾值，或者沒有更多的特征。
3）剪枝CART需要對生成的樹進(jìn)行剪枝，避免模型過度擬合訓(xùn)練數(shù)據(jù)，剪枝時使用的損失函數(shù)如下：
Ca（T）＝C（T）＋a｜T｜
C（T）為樹 T 對訓(xùn)練數(shù)據(jù)的誤差，可以用基尼系數(shù)或者均方損失來表示，a≥0 代表一個權(quán)衡訓(xùn)練數(shù)據(jù)損失 C（T）與總節(jié)點數(shù) ｜T｜的參數(shù)，Ca（T） 代表了樹 T 的整體損失，對于固定的 a，一定存在一個確定的使得 Ca（T）最小的子樹，當(dāng) a偏大時， ｜T｜ 偏小，樹 T 的規(guī)模偏小，反之，樹 T 的規(guī)模偏大，Breiman 等人采用遞歸的方法對 CART 進(jìn)行剪枝，將 a從小增大 0＝a0＜a1＜…＜an，如此產(chǎn)生的區(qū)間 a∈［ai，ai＋1）， i＝1，2，…，n用對應(yīng)此區(qū)間的 a 產(chǎn)生一系列的子樹序列 ｛T0，T1，…，Tn｝這里 TI＋1總是由 TI 剪枝后產(chǎn)生。
剪枝算法如下：
輸入：CART 生成樹 T0
輸出：剪枝后的最優(yōu)樹 T＊
1）設(shè) k＝0 ， T＝T0 ，a＝＋∞
3） 自下而上的對內(nèi)部節(jié)點 t 計算：
g（t）＝［Ct？C（Tt）］／（｜Tt｜？1）
a＝min（a，g（t））
4） 自上而下的訪問內(nèi)部節(jié)點 t ，對最小的 g（t）＝a進(jìn)行剪枝，并對葉節(jié)點 t 以多數(shù)表決形式?jīng)Q定其類別，得到樹 T
5） k＝k＋1， ak＝a，Tk＝T
6） 如果 T 為非單節(jié)點樹，回到4）
7） 對于產(chǎn)生的子樹序列 ｛T0，T1，…，Tn｝分別計算損失，得到最優(yōu)子樹 T＊并返回．
剪枝后的樹便是所需要的CART決策樹。
CART優(yōu)點：1） 可以生成可以理解的規(guī)則；
2） 計算量相對來說不是很大；
3） 可以處理連續(xù)和種類字段；
4）決策樹可以清晰的顯示哪些字段比較重要。
CART缺點：1） 對連續(xù)性的字段比較難預(yù)測；
2） 對有時間順序的數(shù)據(jù)，需要很多預(yù)處理的工作；
3）當(dāng)類別太多時，錯誤可能就會增加的比較快；
4）一般的算法分類的時候，只是根據(jù)一個字段來分類。
CART應(yīng)用場景：CART算法既可以處理離散型問題，也可以處理連續(xù)型問題。CART算法是一種非常有趣且十分有效的非參數(shù)分類和回歸方法。它通過構(gòu)建二叉樹達(dá)到預(yù)測目的。它已在統(tǒng)計、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域中普遍使用，是一種應(yīng)用廣泛的決策樹算法。
結(jié)語：CART模型最早由Breiman 等人提出，它采用與傳統(tǒng)統(tǒng)計學(xué)完全不同的方式構(gòu)建預(yù)測準(zhǔn)則，它是以二叉樹形式給出，易于理解、使用和解釋。由CART 模型構(gòu)建的預(yù)測樹在很多情況下比常用的統(tǒng)計方法構(gòu)建的代數(shù)學(xué)預(yù)測準(zhǔn)則更加準(zhǔn)確，且數(shù)據(jù)越復(fù)雜、變量越多，CART算法優(yōu)越性就越顯著。模型的關(guān)鍵是預(yù)測準(zhǔn)則的構(gòu)建。CART算法在統(tǒng)計、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等領(lǐng)域得到廣泛應(yīng)用。
下載文檔
