CART算法的原理是什么

1. CART算法的認(rèn)識(shí)

   Classification And Regression Tree，即分類回歸樹算法，簡稱CART算法，它是決策樹的一種實(shí)現(xiàn)，通常決策樹主要有三種實(shí)現(xiàn)，分別是ID3算法，CART算法和C4.5算法。

   CART算法是一種二分遞歸分割技術(shù)，把當(dāng)前樣本劃分為兩個(gè)子樣本，使得生成的每個(gè)非葉子結(jié)點(diǎn)都有兩個(gè)分支，因此CART算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。由于CART算法構(gòu)成的是一個(gè)二叉樹，它在每一步的決策時(shí)只能是“是”或者“否”，即使一個(gè)feature有多個(gè)取值，也是把數(shù)據(jù)分為兩部分。在CART算法中主要分為兩個(gè)步驟

   （1）將樣本遞歸劃分進(jìn)行建樹過程

   （2）用驗(yàn)證數(shù)據(jù)進(jìn)行剪枝

2. CART算法的原理

   上面說到了CART算法分為兩個(gè)過程，其中第一個(gè)過程進(jìn)行遞歸建立二叉樹，那么它是如何進(jìn)行劃分的 ？

   設(shè)代表單個(gè)樣本的個(gè)屬性，表示所屬類別。CART算法通過遞歸的方式將維的空間劃分為不重疊的矩形。

   劃分步驟大致如下：

   （1）選一個(gè)自變量，再選取的一個(gè)值，把維空間劃分為兩部分，一部分的所有點(diǎn)都滿足，另一部分的所有點(diǎn)都滿足，對(duì)非連續(xù)變量來說屬性值的取值只有兩個(gè)，即等于該值或不等于該值。

   （2）遞歸處理，將上面得到的兩部分按步驟（1）重新選取一個(gè)屬性繼續(xù)劃分，直到把整個(gè)維空間都劃分完。

   在劃分時(shí)候有一個(gè)問題，它是按照什么標(biāo)準(zhǔn)來劃分的 ？ 對(duì)于一個(gè)變量屬性來說，它的劃分點(diǎn)是一對(duì)連續(xù)變量屬性值的中點(diǎn)。假設(shè)個(gè)樣本的集合一個(gè)屬性有個(gè)連續(xù)的值，那么則會(huì)有個(gè)分裂點(diǎn)，每個(gè)分裂點(diǎn)為相鄰兩個(gè)連續(xù)值的均值。每個(gè)屬性的劃分按照能減少的雜質(zhì)的量來進(jìn)行排序，而雜質(zhì)的減少量定義為劃分前的雜質(zhì)減去劃分后的每個(gè)節(jié)點(diǎn)的雜質(zhì)量劃分所占比率之和。而雜質(zhì)度量方法常用Gini指標(biāo)，假設(shè)一個(gè)樣本共有類，那么一個(gè)節(jié)點(diǎn)的Gini不純度可定義為

   其中表示屬于類的概率，當(dāng)Gini(A)=0時(shí)，所有樣本屬于同類，所有類在節(jié)點(diǎn)中以等概率出現(xiàn)時(shí)，Gini(A)最大化，此時(shí)。

   有了上述理論基礎(chǔ)，實(shí)際的遞歸劃分過程是這樣的：如果當(dāng)前節(jié)點(diǎn)的所有樣本都不屬于同一類或者只剩下一個(gè)樣本，那么此節(jié)點(diǎn)為非葉子節(jié)點(diǎn)，所以會(huì)嘗試樣本的每個(gè)屬性以及每個(gè)屬性對(duì)應(yīng)的分裂點(diǎn)，嘗試找到雜質(zhì)變量最大的一個(gè)劃分，該屬性劃分的子樹即為最優(yōu)分支。

   下面舉個(gè)簡單的例子，如下圖

   在上述圖中，屬性有3個(gè)，分別是有房情況，婚姻狀況和年收入，其中有房情況和婚姻狀況是離散的取值，而年收入是連續(xù)的取值。拖欠貸款者屬于分類的結(jié)果。

   假設(shè)現(xiàn)在來看有房情況這個(gè)屬性，那么按照它劃分后的Gini指數(shù)計(jì)算如下

   而對(duì)于婚姻狀況屬性來說，它的取值有3種，按照每種屬性值分裂后Gini指標(biāo)計(jì)算如下

   最后還有一個(gè)取值連續(xù)的屬性，年收入，它的取值是連續(xù)的，那么連續(xù)的取值采用分裂點(diǎn)進(jìn)行分裂。如下

   根據(jù)這樣的分裂規(guī)則CART算法就能完成建樹過程。

   建樹完成后就進(jìn)行第二步了，即根據(jù)驗(yàn)證數(shù)據(jù)進(jìn)行剪枝。在CART樹的建樹過程中，可能存在Overfitting，許多分支中反映的是數(shù)據(jù)中的異常，這樣的決策樹對(duì)分類的準(zhǔn)確性不高，那么需要檢測并減去這些不可靠的分支。決策樹常用的剪枝有事前剪枝和事后剪枝，CART算法采用事后剪枝，具體方法為代價(jià)復(fù)雜性剪枝法。