概要

本部分介紹 CART，是一種非常重要的機(jī)器學(xué)習(xí)算法。
?

---

基本原理

?
CART 全稱為 Classification And Regression Trees，即分類回歸樹(shù)。顧名思義，該算法既可以用于分類還可以用于回歸。

克服了 ID3 算法只能處理離散型數(shù)據(jù)的缺點(diǎn)，CART 可以使用二元切分來(lái)處理連續(xù)型變量。二元切分法，即每次把數(shù)據(jù)集切分成兩份，具體地處理方法是：如果特征值大于給定值就走左子樹(shù)，否則就走右子樹(shù)。對(duì) CART 稍作修改就可以處理回歸問(wèn)題。先前我們使用香農(nóng)熵來(lái)度量集合的無(wú)組織程度，如果選用其它方法來(lái)代替香農(nóng)熵，就可以使用樹(shù)構(gòu)建算法來(lái)完成回歸。

本部分將構(gòu)建兩種樹(shù)，第一種是回歸樹(shù)，其每個(gè)葉節(jié)點(diǎn)包含單個(gè)值；第二種是模型樹(shù)，其每個(gè)葉節(jié)點(diǎn)包含一個(gè)線性方程。
?

---

回歸樹(shù)

要對(duì)樹(shù)據(jù)的復(fù)雜關(guān)系建模，我們已經(jīng)決定用樹(shù)結(jié)構(gòu)來(lái)幫助切分?jǐn)?shù)據(jù)，那么如何實(shí)現(xiàn)數(shù)據(jù)的切分呢？怎么才能知道是否已經(jīng)充分切分呢？這些問(wèn)題的答案取決于葉節(jié)點(diǎn)的建模方式。回歸樹(shù)假設(shè)葉節(jié)點(diǎn)是常數(shù)值，需要度量出數(shù)據(jù)的一致性，在這里我們選擇使用平方誤差的總值來(lái)達(dá)到這一目的。

選擇特征的偽代碼如下：

對(duì)每個(gè)特征：
    對(duì)每個(gè)特征值：
        將數(shù)據(jù)切分成兩份（二元切分）
             計(jì)算切分的誤差（平方誤差）
             如果當(dāng)前誤差小于當(dāng)前最小誤差，那么將當(dāng)前切分設(shè)定為最佳切分并更新最小誤差
返回最佳切分的特征和閾值

與 ID3 或 C4.5 唯一不同的是度量數(shù)據(jù)的一致性不同，前兩者分別是信息增益和信息增益率，而這個(gè)是用平方誤差的總值，有一點(diǎn)聚類的感覺(jué)。比如這樣的數(shù)據(jù)集：

程序創(chuàng)建的樹(shù)結(jié)構(gòu)就是：

{'spInd': 0, 'spVal': 0.48813000000000001, 'left': 1.0180967672413792, 'right': -0.044650285714285719}

在分類樹(shù)中最常用的是基尼指數(shù)：在分類問(wèn)題中，假設(shè)有 (K) 個(gè)類，樣本點(diǎn)屬于第 (k) 類的概率為 (p_k)，則概率分布的基尼指數(shù)定義為
egin{align}
Gini(p) = sum_{k=1}^K p_k(1-p_k) = 1- sum_{k=1}^K p_k^2
end{align}
基尼系數(shù)與熵的特性類似，也是不確定性的一種度量。對(duì)于樣本集合 (D)，基尼指數(shù)為
egin{align}
Gini(D) = 1- sum_{k=1}^Kleft( frac{lvert C_k vert }{lvert D vert} ight)
end{align}
其中 (C_k) 是 (D) 中屬于樣本集合第 (k) 類的樣本子集， (K) 是類的個(gè)數(shù)。
?

---

剪枝

一棵樹(shù)如果節(jié)點(diǎn)過(guò)多，表明該模型可能對(duì)數(shù)據(jù)進(jìn)行了“過(guò)擬合”。控制決策樹(shù)規(guī)模的方法稱為剪枝，一種是先剪枝， 一種是后剪枝。所謂先剪枝，實(shí)際上是控制決策樹(shù)的生長(zhǎng)，后剪枝是指對(duì)完全生成的決策樹(shù)進(jìn)行修剪。

先剪枝方法有：

數(shù)據(jù)劃分法。劃分?jǐn)?shù)據(jù)成訓(xùn)練樣本和測(cè)試樣本，使用訓(xùn)練樣本進(jìn)行訓(xùn)練，使用測(cè)試樣本進(jìn)行樹(shù)生長(zhǎng)檢驗(yàn)
閾值法。當(dāng)某節(jié)點(diǎn)的信息增益小于某閾值時(shí)，停止樹(shù)生長(zhǎng)
信息增益的統(tǒng)計(jì)顯著性分析。從已有節(jié)點(diǎn)獲得的所有信息增益統(tǒng)計(jì)其分布，如果繼續(xù)生長(zhǎng)得到的信息增益與該分布相比不顯著，則停止樹(shù)的生長(zhǎng)

先剪枝的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：簡(jiǎn)單直接
缺點(diǎn)：對(duì)于不回溯的貪婪算法，缺乏后效性考慮，可能導(dǎo)致樹(shù)提前停止

?

后剪枝方法有：

減少分類錯(cuò)誤修剪法。使用獨(dú)立的剪枝集估計(jì)剪枝前后的分類錯(cuò)誤率，基于此進(jìn)行剪枝
最小代價(jià)與復(fù)雜性折中的剪枝。對(duì)剪枝后的樹(shù)綜合評(píng)價(jià)錯(cuò)誤率和復(fù)雜性，決定是否剪枝
最小描述長(zhǎng)度準(zhǔn)則。最簡(jiǎn)單的樹(shù)就是最好的樹(shù)，對(duì)決策樹(shù)進(jìn)行編碼，通過(guò)剪枝得到編碼最小的樹(shù)
規(guī)則后剪枝。將訓(xùn)練完的決策樹(shù)轉(zhuǎn)換成規(guī)則，通過(guò)刪除不會(huì)降低估計(jì)精度的前提下修剪每一條規(guī)則

后剪枝的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：實(shí)際應(yīng)用中有效
缺點(diǎn)：數(shù)據(jù)量大時(shí)，計(jì)算代價(jià)較大

?
下面講述一種用于 CART 回歸樹(shù)的剪枝操作。一般使用后剪枝方法需要將數(shù)據(jù)集分成測(cè)試集和訓(xùn)練集，C4.5 所用的剪枝操作還是一種特殊的后剪枝操作，不需要測(cè)試集。

剪枝操作前，首先指定參數(shù)，使得構(gòu)建出的樹(shù)足夠大、足夠復(fù)雜，便于剪枝。接下來(lái)從上而下找到葉結(jié)點(diǎn)，用測(cè)試集來(lái)判斷將這些葉節(jié)點(diǎn)合并是否能降低測(cè)試誤差，如果是的話就合并。偽代碼如下：

基于已有的樹(shù)切分測(cè)試數(shù)據(jù)：
    如果存在任一子集是一棵樹(shù)，則在該子集遞歸剪枝過(guò)程
    計(jì)算將當(dāng)前兩個(gè)葉節(jié)點(diǎn)合并后的誤差
    計(jì)算不合并的誤差
    如果合并會(huì)降低誤差的話，就將葉節(jié)點(diǎn)合并

?

---

模型樹(shù)

模型樹(shù)仍然采用二元切分，但葉節(jié)點(diǎn)不再是簡(jiǎn)單的數(shù)值，取而代之的是一些線性模型。

考慮下圖中的數(shù)據(jù)，顯然兩條直線擬合效果更好。

對(duì)回歸樹(shù)稍作修改就可以變成模型樹(shù)。模型樹(shù)的生成樹(shù)關(guān)鍵在于誤差的計(jì)算。對(duì)于給定的數(shù)據(jù)集，應(yīng)該先用線性的模型對(duì)它進(jìn)行擬合，然后計(jì)算真實(shí)的目標(biāo)值與模型預(yù)測(cè)值間的差值。最后將這些差值的平方求和就得到了所需要的誤差。

?

樹(shù)回歸優(yōu)缺點(diǎn)

?

優(yōu)點(diǎn)：可以對(duì)復(fù)雜和非線性的數(shù)據(jù)建模
缺點(diǎn)：結(jié)果不易理解
?

?

總結(jié)

以上是生活随笔為你收集整理的分类回归树（CART）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。