決策樹

1.前言

決策樹是一種基本的分類和回歸方法。決策樹呈樹形結(jié)構(gòu)，在分類問題中，表示基于特征對(duì)實(shí)例進(jìn)行分類的過程。采用的是自頂而下的遞歸方法，從根節(jié)點(diǎn)開始一步步走到葉子節(jié)點(diǎn)，所有的數(shù)據(jù)最終都會(huì)落在葉子節(jié)點(diǎn)。它可以認(rèn)為是if-then規(guī)則的集合，也可以認(rèn)為是定義在特征空間和類空間上的條件概率分布。學(xué)習(xí)時(shí)，利用訓(xùn)練數(shù)據(jù)，根據(jù)損失函數(shù)最小化的原則建立決策樹模型。預(yù)測(cè)時(shí)，對(duì)新的數(shù)據(jù)，利用決策樹模型進(jìn)行分類。決策樹學(xué)習(xí)通常包括三個(gè)步驟：特征選擇、決策樹的生成和決策樹的剪枝。決策樹算法的發(fā)展從ID3到C4.5再到CART。

1.1 樹的組成

  • 根節(jié)點(diǎn)：第一個(gè)選擇點(diǎn)
  • 非葉子節(jié)點(diǎn)與分支：中間過程
  • 葉子節(jié)點(diǎn)：最終的決策結(jié)果

1.2 決策樹的訓(xùn)練與測(cè)試

  • 訓(xùn)練階段：從給定的訓(xùn)練集構(gòu)造出來一棵樹（從跟節(jié)點(diǎn)開始選擇特征，如何進(jìn)行特征切分）
  • 測(cè)試階段：根據(jù)構(gòu)造出來的樹模型從上到下去走一遍就好了
  • 一旦構(gòu)造好了決策樹，那么分類或者預(yù)測(cè)任務(wù)就很簡(jiǎn)單了，只需要走一遍就可以了，那么難點(diǎn)就在于如何構(gòu)造出來一顆樹，這就沒那么容易了，需要考慮的問題還有很多的

2. 特征選擇

  • 問題：根節(jié)點(diǎn)的選擇該用哪個(gè)特征呢？接下來呢？如何切分呢？
  • 想象一下：我們的目標(biāo)應(yīng)該是根節(jié)點(diǎn)就像一個(gè)老大似的能更好的切分?jǐn)?shù)據(jù)（分類的效果更好），根節(jié)點(diǎn)下面的節(jié)點(diǎn)自然就是二當(dāng)家了。
  • 目標(biāo)：通過一種衡量標(biāo)準(zhǔn)，來計(jì)算通過不同特征進(jìn)行分支選擇后的分類情況，找出來最好的那個(gè)當(dāng)成根節(jié)點(diǎn)，以此類推。

特征選擇在于選取對(duì)訓(xùn)練數(shù)據(jù)具有分類能力的特征。特征選擇的基本方法有三種：ID3的信息增益、C4.5的信息增益比、CART的基尼系數(shù)。

2.1 信息增益

特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的經(jīng)驗(yàn)熵H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差，即

g(D,A)=H(D)?H(D|A)

2.2 信息增益比

在C4.5中，引入了信息增益比I_R(X,Y)，它是信息增益和特征熵的比值。表達(dá)式如下：

I_R(D,A)=\frac{I(A,D)}{H_A(D)}

其中D為樣本特征輸出的集合，A為樣本特征，對(duì)于特征熵H_A(D), 表達(dá)式如下：

H_A(D)=-\displaystyle \sum^{n}_{i=1} {\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}}

其中n為特征A的類別數(shù)，D_i為特征A的第i個(gè)取值對(duì)應(yīng)的樣本個(gè)數(shù)。D為樣本個(gè)數(shù)。

2.3 基尼系數(shù)

CART分類樹算法使用基尼系數(shù)來代替信息增益比，基尼系數(shù)代表了模型的不純度，基尼系數(shù)越小，則不純度越低，特征越好。這和信息增益(比)是相反的。
具體的，在分類問題中，假設(shè)有K個(gè)類別，第k個(gè)類別的概率為p_k, 則基尼系數(shù)的表達(dá)式為：

Gini(p)=\displaystyle\sum^{K}_{k=1}{p_k(1?p_k)} = 1-\displaystyle\sum^{K}_{k=1}{p_k}^2

3.決策樹的生成

3.1 ID3算法

ID3算法的核心是再?zèng)Q策樹各個(gè)節(jié)點(diǎn)上應(yīng)用信息增益選擇特征，遞歸的構(gòu)建決策樹。
輸入：訓(xùn)練集D，特征集A，閾值ε
輸出：決策樹T

  1. 初始化信息增益的閾值ε
  2. 判斷樣本是否為同一類輸出D_i，如果是則返回單節(jié)點(diǎn)樹T。標(biāo)記類別為D_i。
  3. 判斷特征是否為空，如果是則返回單節(jié)點(diǎn)樹&T&，標(biāo)記類別為樣本中輸出類別D實(shí)例數(shù)最多的類別。
  4. 計(jì)算A中的各個(gè)特征（一共n個(gè)）對(duì)輸出D的信息增益，選擇信息增益最大的特征A_g。
  5. 如果A_g的信息增益小于閾值ε，則返回單節(jié)點(diǎn)樹T，標(biāo)記類別為樣本中輸出類別D實(shí)例數(shù)最多的類別。
  6. 否則，按特征A_g的不同取值A_{gi}將對(duì)應(yīng)的樣本輸出D分成不同的類別D_i。每個(gè)類別產(chǎn)生一個(gè)子節(jié)點(diǎn)。對(duì)應(yīng)特征值為A_{gi}。返回增加了節(jié)點(diǎn)的數(shù)T。
  7. 對(duì)于所有的子節(jié)點(diǎn)，令D=Di,A=A?A_g遞歸調(diào)用2-6步，得到子樹T_i并返回。

3.2 C4.5算法

C4.5算法整體結(jié)構(gòu)和ID3基本一樣，只有在特征選擇的時(shí)候換成了信息增益比。

3.3 CART算法

輸入是訓(xùn)練集D，基尼系數(shù)的閾值ε_(tái)1，樣本個(gè)數(shù)閾值ε_(tái)2。
輸出是決策樹T。
我們的算法從根節(jié)點(diǎn)開始，用訓(xùn)練集遞歸的建立CART樹。

  1. 對(duì)于當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)集為D，如果樣本個(gè)數(shù)小于閾值ε_(tái)2或者沒有特征，則返回決策子樹，當(dāng)前節(jié)點(diǎn)停止遞歸。
  2. 計(jì)算樣本集D的基尼系數(shù)，如果基尼系數(shù)小于閾值ε_(tái)1，則返回決策樹子樹，當(dāng)前節(jié)點(diǎn)停止遞歸。
  3. 計(jì)算當(dāng)前節(jié)點(diǎn)現(xiàn)有的各個(gè)特征的各個(gè)特征值對(duì)數(shù)據(jù)集D的基尼系數(shù)。
  4. 在計(jì)算出來的各個(gè)特征的各個(gè)特征值對(duì)數(shù)據(jù)集D的基尼系數(shù)中，選擇基尼系數(shù)最小的特征A和對(duì)應(yīng)的特征值a。根據(jù)這個(gè)最優(yōu)特征和最優(yōu)特征值，把數(shù)據(jù)集劃分成兩部分D1和D2，同時(shí)建立當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)，左節(jié)點(diǎn)的數(shù)據(jù)集D為D1，右節(jié)點(diǎn)的數(shù)據(jù)集D為D2。
  5. 對(duì)左右的子節(jié)點(diǎn)遞歸的調(diào)用1-4步，生成決策樹。

4.決策樹的剪枝

決策樹生成算法遞歸地產(chǎn)生決策樹，直到不能繼續(xù)下去為止。這樣產(chǎn)生的樹往往對(duì)訓(xùn)練數(shù)據(jù)的分類很準(zhǔn)確，但對(duì)未知的測(cè)試數(shù)據(jù)的分類卻沒那么準(zhǔn)確，即出現(xiàn)過擬合現(xiàn)象。過擬合的原因在于學(xué)習(xí)時(shí)過多地考慮如何提高對(duì)訓(xùn)練數(shù)據(jù)的正確分類，從而構(gòu)建出過于復(fù)雜的決策樹。解決這個(gè)問題的辦法是考慮決策樹的復(fù)雜度，對(duì)已生成的決策樹進(jìn)行簡(jiǎn)化。

可以通過剪枝的方式降低決策樹的復(fù)雜度，剪枝類型分為預(yù)剪枝、后剪枝。

  • 預(yù)剪枝：是在構(gòu)建決策樹的過程中，提前終止決策樹的生長(zhǎng)，從而避免過多的節(jié)點(diǎn)產(chǎn)生。預(yù)剪枝方法雖然簡(jiǎn)單但實(shí)用性不強(qiáng)，因?yàn)楹茈y精確的判斷何時(shí)終止樹的生長(zhǎng)。
  • 后剪枝：是在決策樹構(gòu)建完成之后，對(duì)那些置信度不達(dá)標(biāo)的節(jié)點(diǎn)子樹用葉子結(jié)點(diǎn)代替，該葉子結(jié)點(diǎn)的類標(biāo)號(hào)用該節(jié)點(diǎn)子樹中頻率最高的類標(biāo)記。后剪枝方法又分為兩種:
    • 把訓(xùn)練數(shù)據(jù)集分成樹的生長(zhǎng)集和剪枝集（參考周志華老師的西瓜書上介紹的剪枝方法）。
    • 使用同一數(shù)據(jù)集進(jìn)行決策樹生長(zhǎng)和剪枝。常見的后剪枝方法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。 C4.5算法采用PEP(Pessimistic Error Pruning)剪枝法。PEP剪枝法由Quinlan提出，是一種自上而下的剪枝法，根據(jù)剪枝前后的錯(cuò)誤率來判定是否進(jìn)行子樹的修剪。CART采用的是CCP(Cost Complexity Pruning)的剪枝法策略。

以下將介紹CART決策樹的后剪枝算法CCP(Cost Complexity Pruning)。

4.1 CART的CCP剪枝算法

總體思路：由完全樹T_0開始，剪枝部分結(jié)點(diǎn)得到T_1，再次剪枝部分結(jié)點(diǎn)得到T_2...直到剩下樹根的樹T_k；在驗(yàn)證數(shù)據(jù)集上對(duì)這k個(gè)樹分別評(píng)價(jià)，選擇損失函數(shù)最小的樹T_a。
變量預(yù)定義： |T_{leaf}|表示樹T的葉結(jié)點(diǎn)個(gè)數(shù)，t表示樹T的葉結(jié)點(diǎn)，同時(shí)N_t表示該葉結(jié)點(diǎn)含有的樣本點(diǎn)個(gè)數(shù)，其中屬于k類的樣本點(diǎn)有N_{tk}個(gè)，K表示類別的個(gè)數(shù)，H_t(T)為葉結(jié)點(diǎn)t上的經(jīng)驗(yàn)熵，α≥0為參數(shù)。

一個(gè)節(jié)點(diǎn)的樣本數(shù)，是這個(gè)樣本所有類的數(shù)量的和，公式如下：

N_t=\displaystyle\sum^{K}_{k=1}{N_{tk}}

  • 經(jīng)驗(yàn)熵：

H_t(T)=-\displaystyle\sum^{K}_{k}\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t}

經(jīng)驗(yàn)熵反映了一個(gè)葉結(jié)點(diǎn)中的分類結(jié)果的混亂程度。經(jīng)驗(yàn)熵越大，說明該葉結(jié)點(diǎn)所對(duì)應(yīng)的分類結(jié)果越混亂，也就是說分類結(jié)果中包含了較多的類別，表明該分支的分類效果較差。

  • 損失函數(shù)：

C(T)=\displaystyle\sum^{|T_{leaf}|}_{t=1}N_tH_t(T)

損失函數(shù)其實(shí)是求葉結(jié)點(diǎn)的經(jīng)驗(yàn)熵期望。用N_t給經(jīng)驗(yàn)熵加權(quán)的依據(jù)是葉子節(jié)點(diǎn)含有的樣本個(gè)數(shù)越多，其分類效果或混亂程度越占主導(dǎo)，相當(dāng)于求了期望，可以更好的描述分支前后的關(guān)系。例如設(shè)一個(gè)結(jié)點(diǎn)r有n個(gè)樣本，其組成是第i類有n_i個(gè)樣本，在分了幾個(gè)孩子結(jié)點(diǎn)后各個(gè)葉結(jié)點(diǎn)的成分仍保持原比例，記新的子樹為R，可以計(jì)算得出評(píng)價(jià)函數(shù)C(r)=C(R)，即在隨機(jī)分組后不會(huì)有任何分類效果的改進(jìn)。損失函數(shù)越小越好。熵的期望和熵一樣，越小越好。所以，損失函數(shù)越大，說明模型的分類效果越差。

  • 損失函數(shù)的正則化:

C_α(T)=\displaystyle\sum^{|T_{leaf}|}_{t=1}N_tH_t(T)+\alpha|T_{leaf}|

修正項(xiàng)α|T_{leaf}|是基于復(fù)雜度的考慮。如上面提到的情況，r與R其實(shí)是一樣的，沒有進(jìn)行任何分類的處理，但是我們?nèi)匀挥X得r更好，原因在于R的復(fù)雜度更高。加了此修正項(xiàng)后具有現(xiàn)實(shí)的意義：如果α=0表示未剪枝的完全樹損失更小（熵更小的占主導(dǎo)地位），如果\alpha\to \infty表示剪枝到只剩根結(jié)點(diǎn)更好（葉結(jié)點(diǎn)個(gè)數(shù)占主導(dǎo)地位）。修正項(xiàng)α|T_{leaf}|可以避免過擬合。修正項(xiàng)α|T_{leaf}|考慮到了復(fù)雜度，α值設(shè)置得好可以避免出現(xiàn)完全樹和根結(jié)點(diǎn)這類的極端情況，因此可以避免過擬合。

  • 損失函數(shù)簡(jiǎn)化形式：

C_α(T)=C(T)+α|T_{leaf}|

  • 計(jì)算剪枝系數(shù)α:

假定當(dāng)前對(duì)以t為根的子樹T_t剪枝，剪枝后只保留t本身而刪掉所有的子結(jié)點(diǎn)。
剪枝后的損失函數(shù)：C_α(t)=C(t)+α

剪枝前的損失函數(shù)：C_α(T_t)=C(T_t)+α|T_{leaf}|( C(T_t)應(yīng)該是小于C(t))

令二者相等，求得：α=\frac{C(t)?C(T)}{|T_{leaf}|?1}，因?yàn)閾p失相同，那就取復(fù)雜度小的，所以就可以剪枝。α稱為結(jié)點(diǎn)t的剪枝系數(shù)。

  • 剪枝算法流程：
  1. 對(duì)于給定的決策樹T_0。
  2. 計(jì)算所有內(nèi)部結(jié)點(diǎn)的剪枝系數(shù)。
  3. 查找最小剪枝系數(shù)的結(jié)點(diǎn)，剪枝得決策樹T_k。
  4. 重復(fù)以上步驟，直到?jīng)Q策樹T_k只有一個(gè)結(jié)點(diǎn)。
  5. 得到?jīng)Q策樹序列T_0,T_1,T_2...T_k。
  6. 使用驗(yàn)證樣本集選擇最優(yōu)子樹。

5. ID3、C4.5、CART比較

5.1 ID3算法

5.1.1 ID3原理

ID3算法就是用信息增益大小來判斷當(dāng)前節(jié)點(diǎn)應(yīng)該用什么特征來構(gòu)建決策樹，用計(jì)算出的信息增益最大的特征來建立決策樹的當(dāng)前節(jié)點(diǎn)。算法具體過程看上文。

5.1.2 ID3的不足

ID3算法雖然提出了新思路，但是還是有很多值得改進(jìn)的地方。

  • ID3沒有考慮連續(xù)特征，比如長(zhǎng)度，密度都是連續(xù)值，無法在ID3運(yùn)用。這大大限制了ID3的用途。
  • ID3采用信息增益大的特征優(yōu)先建立決策樹的節(jié)點(diǎn)。很快就被人發(fā)現(xiàn)，在相同條件下，取值比較多的特征比取值少的特征信息增益大。比如一個(gè)變量有2個(gè)值，各為1/2，另一個(gè)變量為3個(gè)值，各為1/3，其實(shí)他們都是完全不確定的變量，但是取3個(gè)值的比取2個(gè)值的信息增益大。如果校正這個(gè)問題呢？
  • ID3算法對(duì)于缺失值的情況沒有做考慮
  • 沒有考慮過擬合的問題
    ID3 算法的作者昆蘭基于上述不足，對(duì)ID3算法做了改進(jìn)，這就是C4.5算法，也許你會(huì)問，為什么不叫ID4，ID5之類的名字呢?那是因?yàn)闆Q策樹太火爆，他的ID3一出來，別人二次創(chuàng)新，很快就占了ID4，ID5，所以他另辟蹊徑，取名C4.0算法，后來的進(jìn)化版為C4.5算法。

5.2 C4.5算法

5.2.1 C4.5對(duì)ID3的改進(jìn)

C4.5改進(jìn)了上面ID3的4個(gè)問題：

  1. 對(duì)于ID3不能處理連續(xù)特征，C4.5的思路是將連續(xù)的特征離散化。比如m個(gè)樣本的連續(xù)特征A有m個(gè)，從小到大排列為a_1,a_2,...,a_m, 則C4.5取相鄰兩樣本值的平均數(shù)，一共取得m?1個(gè)劃分點(diǎn)，其中第i個(gè)劃分點(diǎn)T_i表示為：Ti=\frac{a_i+a_i+1}{2}。對(duì)于這m?1個(gè)點(diǎn)，分別計(jì)算以該點(diǎn)作為二元分類點(diǎn)時(shí)的信息增益。選擇信息增益最大的點(diǎn)作為該連續(xù)特征的二元離散分類點(diǎn)。比如取到的增益最大的點(diǎn)為a_t, 則小于a_t的值為類別1，大于a_t的值為類別2，這樣我們就做到了連續(xù)特征的離散化。要注意的是，與離散屬性不同的是，如果當(dāng)前節(jié)點(diǎn)為連續(xù)屬性，則該屬性后面還可以參與子節(jié)點(diǎn)的產(chǎn)生選擇過程。
  2. 對(duì)于ID3的第2個(gè)問題，信息增益作為標(biāo)準(zhǔn)容易偏向于取值較多的特征的問題。我們引入一個(gè)信息增益比的變量I_R(X,Y)，它是信息增益和特征熵的比值。

    I_R(D,A)=\frac{I(A,D)}{H_A(D)}

  3. 對(duì)于ID3的第3個(gè)缺失值處理的問題，主要需要解決的是兩個(gè)問題，一是在樣本某些特征缺失的情況下選擇劃分的屬性，二是選定了劃分屬性，對(duì)于在該屬性上缺失特征的樣本的處理。
    1. 對(duì)于第一個(gè)子問題，對(duì)于某一個(gè)有缺失特征值的特征A。C4.5的思路是將數(shù)據(jù)分成兩部分，對(duì)每個(gè)樣本設(shè)置一個(gè)權(quán)重（初始可以都為1），然后劃分?jǐn)?shù)據(jù)，一部分是有特征值A的數(shù)據(jù)D_1，另一部分是沒有特征A的數(shù)據(jù)D_2。然后對(duì)于沒有缺失特征A的數(shù)據(jù)集D_1來和對(duì)應(yīng)的A特征的各個(gè)特征值一起計(jì)算加權(quán)重后的信息增益比，最后乘上一個(gè)系數(shù)，這個(gè)系數(shù)是無特征A缺失的樣本加權(quán)后所占加權(quán)總樣本的比例。
    2. 對(duì)于第二個(gè)子問題，可以將缺失特征的樣本同時(shí)劃分入所有的子節(jié)點(diǎn)，不過將該樣本的權(quán)重按各個(gè)子節(jié)點(diǎn)樣本的數(shù)量比例來分配。比如缺失特征A的樣本a之前權(quán)重1，特征A有3個(gè)特征值A_1,A_2,A_3。3個(gè)特征值對(duì)應(yīng)的無缺失A特征的樣本個(gè)數(shù)為2,3,4。a同時(shí)劃分入A_1,A_2,A_3。對(duì)應(yīng)權(quán)重調(diào)節(jié)為2/9, 3/9, 4/9。
  4. 對(duì)于ID3的第4個(gè)問題，C4.5引入了正則化系數(shù)進(jìn)行剪枝。
5.2.2 C4.5的不足

C4.5雖然改進(jìn)或者改善了ID3算法的幾個(gè)主要的問題，仍然有優(yōu)化的空間。

  • 由于決策樹算法非常容易過擬合，因此對(duì)于生成的決策樹必須要進(jìn)行剪枝。C4.5的剪枝方法是PEP。PEP的準(zhǔn)確度比較高，但是依舊會(huì)存在以下的問題：

    1. PEP算法實(shí)用的從從上而下的剪枝策略，這種剪枝會(huì)導(dǎo)致和預(yù)剪枝同樣的問題，造成剪枝過度。

    2.PEP剪枝會(huì)出現(xiàn)剪枝失敗的情況。

  • C4.5生成的是多叉樹，即一個(gè)父節(jié)點(diǎn)可以有多個(gè)節(jié)點(diǎn)。很多時(shí)候，在計(jì)算機(jī)中二叉樹模型會(huì)比多叉樹運(yùn)算效率高。如果采用二叉樹，可以提高效率。

  • C4.5只能用于分類，如果能將決策樹用于回歸的話可以擴(kuò)大它的使用范圍。

  • C4.5由于使用了熵模型，里面有大量的耗時(shí)的對(duì)數(shù)運(yùn)算,如果是連續(xù)值還有大量的排序運(yùn)算。如果能夠加以模型簡(jiǎn)化可以減少運(yùn)算強(qiáng)度但又不犧牲太多準(zhǔn)確性的話，那就更好了。

5.3 CART算法

5.3.1 CART對(duì)C4.5的改進(jìn)

CART算法在C4.5的基礎(chǔ)上，對(duì)于C4.5中的出現(xiàn)的問題進(jìn)行了改進(jìn)。針對(duì)上面提到的C4.5中出現(xiàn)的4點(diǎn)問題，進(jìn)行如下改進(jìn)：

  1. CART使用了CCP代價(jià)復(fù)雜度剪枝算法，對(duì)C4.5的剪枝方法進(jìn)行了優(yōu)化。

  2. 針對(duì)C4.5的多叉樹的問題，CART改成了二叉樹。CART采用的是不停的二分，舉個(gè)例子，CART分類樹會(huì)考慮把A分成{A_1}和{A_2,A_3},{A_2}和{A_1,A_3},{A_3}和{A_1,A_2}三種情況，找到基尼系數(shù)最小的組合，比如{A_2}和{A_1,A_3}, 然后建立二叉樹節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)是{A_2}對(duì)應(yīng)的樣本，另一個(gè)節(jié)點(diǎn)是{A_1,A_3}對(duì)應(yīng)的節(jié)點(diǎn)。同時(shí)，由于這次沒有把特征A的取值完全分開，后面我們還有機(jī)會(huì)在子節(jié)點(diǎn)繼續(xù)選擇到特征A來劃分{A_1}和{A_3}。這和ID3或者C4.5不同，在ID3或者C4.5的一棵子樹中，離散特征只會(huì)參與一次節(jié)點(diǎn)的建立，而CART中的離散特征會(huì)參與多次節(jié)點(diǎn)建立。

  3. CART可以分為CART分類樹和CART回歸樹。CART分類樹和CART回歸樹的算法大致相同，主要區(qū)別有下面兩點(diǎn)：

    1. 連續(xù)值的處理方法不同。
      1. CART分類樹采用的是用基尼系數(shù)的大小來度量特征的各個(gè)劃分點(diǎn)的優(yōu)劣情況
      2. CART回歸樹的度量目標(biāo)是，對(duì)于任意劃分特征A，對(duì)應(yīng)的任意劃分點(diǎn)s兩邊劃分成的數(shù)據(jù)集D_1和D_2，求出使D_1和D_2各自集合的均方差最小，同時(shí)D_1和D_2的均方差之和最小所對(duì)應(yīng)的特征和特征值劃分點(diǎn)。表達(dá)式為：

    \underbrace{min}_{A,s}\left[ \underbrace{min}_{c_1} \sum^{}_{x_i\in{D_1}(A,s)}{(y_i-c_1)^2} + \underbrace{min}_{c_2} \sum^{}_{x_i\in{D_2}(A,s)}{(y_i-c_2)^2} \right]

    1. 決策樹建立后做預(yù)測(cè)的方式不同。
      1. CART分類樹采用葉子節(jié)點(diǎn)里概率最大的類別作為當(dāng)前節(jié)點(diǎn)的預(yù)測(cè)類別。
      2. CART回歸樹輸出不是類別，它采用的是用最終葉子的均值或者中位數(shù)來預(yù)測(cè)輸出結(jié)果。

4.CART分類樹使用了使用的是基尼系數(shù)的度量方式

CART算法相比C4.5算法的分類方法，采用了簡(jiǎn)化的二叉樹模型，同時(shí)特征選擇采用了近似的基尼系數(shù)來簡(jiǎn)化計(jì)算。當(dāng)然CART樹最大的好處是還可以做回歸模型，這個(gè)C4.5沒有。

5.3.2 CART的不足
  1. 無論是ID3, C4.5還是CART,在做特征選擇的時(shí)候都是選擇最優(yōu)的一個(gè)特征來做分類決策，但是大多數(shù)，分類決策不應(yīng)該是由某一個(gè)特征決定的，而是應(yīng)該由一組特征決定的。這樣決策得到的決策樹更加準(zhǔn)確。這個(gè)決策樹叫做多變量決策樹(multi-variate decision tree)。在選擇最優(yōu)特征的時(shí)候，多變量決策樹不是選擇某一個(gè)最優(yōu)特征，而是選擇最優(yōu)的一個(gè)特征線性組合來做決策。這個(gè)算法的代表是OC1，這里不多介紹。
  2. 如果樣本發(fā)生一點(diǎn)點(diǎn)的改動(dòng)，就會(huì)導(dǎo)致樹結(jié)構(gòu)的劇烈改變。這個(gè)可以通過集成學(xué)習(xí)里面的隨機(jī)森林之類的方法解決。

6. 總結(jié)

決策樹算法的優(yōu)點(diǎn)：

  1. 簡(jiǎn)單直觀，生成的決策樹很直觀。
  2. 基本不需要預(yù)處理，不需要提前歸一化，處理缺失值。
  3. 使用決策樹預(yù)測(cè)的代價(jià)是O({\log_2^m})。 m為樣本數(shù)。
  4. 既可以處理離散值也可以處理連續(xù)值。很多算法只是專注于離散值或者連續(xù)值。
  5. 可以處理多維度輸出的分類問題。
  6. 相比于神經(jīng)網(wǎng)絡(luò)之類的黑盒分類模型，決策樹在邏輯上可以得到很好的解釋
  7. 可以交叉驗(yàn)證的剪枝來選擇模型，從而提高泛化能力。
  8. 對(duì)于異常點(diǎn)的容錯(cuò)能力好，健壯性高。

決策樹算法的缺點(diǎn):

  1. 決策樹算法非常容易過擬合，導(dǎo)致泛化能力不強(qiáng)?？梢酝ㄟ^設(shè)置節(jié)點(diǎn)最少樣本數(shù)量和限制決策樹深度來改進(jìn)。
  2. 決策樹會(huì)因?yàn)闃颖景l(fā)生一點(diǎn)點(diǎn)的改動(dòng)，就會(huì)導(dǎo)致樹結(jié)構(gòu)的劇烈改變。這個(gè)可以通過集成學(xué)習(xí)之類的方法解決。
  3. 尋找最優(yōu)的決策樹是一個(gè)NP難的問題，我們一般是通過啟發(fā)式方法，容易陷入局部最優(yōu)。可以通過集成學(xué)習(xí)之類的方法來改善。
  4. 有些比較復(fù)雜的關(guān)系，決策樹很難學(xué)習(xí)，比如異或。這個(gè)就沒有辦法了，一般這種關(guān)系可以換神經(jīng)網(wǎng)絡(luò)分類方法來解決。
  5. 如果某些特征的樣本比例過大，生成決策樹容易偏向于這些特征。這個(gè)可以通過調(diào)節(jié)樣本權(quán)重來改善。
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容