決策樹算法核心理論知識解析

  • 決策樹算法利用非度量（nunmetric）的方式進(jìn)行一系列的查詢問答來判斷和分類，被廣泛用于分類和回歸模型，三種最常用的實(shí)現(xiàn)算法是CART、ID3、C4.5。
  • 對于同一個(gè)數(shù)據(jù)集，特征和節(jié)點(diǎn)可以有多種組合方式，實(shí)際上可以生成很多決策樹。我們運(yùn)用決策樹算法是希望從中找出最合適的樹，因此算法的目標(biāo)是在合適的節(jié)點(diǎn)上放入合適的特征。
image.png

決策樹構(gòu)成

  • 決策樹由三部分構(gòu)成：根節(jié)點(diǎn)（root）、節(jié)點(diǎn)（node）、葉子（leaves）
    root
  • 決策樹的根部，即上圖中的第一層“顏色”。
    nodes
  • 決策樹的節(jié)點(diǎn)。
    leaves
  • 決策樹的葉子，即最終的標(biāo)記，如西瓜、蘋果等。

1.算法優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

  • 可展示性強(qiáng)：決策樹可以提取規(guī)則/決策依據(jù)，類似人類邏輯化的決策，易于向其他人展示和說明模型的決策過程。
  • 分類速度快：決策樹只需要一系列的簡單查詢，無需計(jì)算和度量，當(dāng)問題比較簡單且訓(xùn)練樣本比較少時(shí)，非常有效。

缺點(diǎn)

  • 最優(yōu)決策樹難尋：對于同一個(gè)數(shù)據(jù)集，可以生成很多類型的決策樹。雖然已有很多先進(jìn)的算法和測量指標(biāo)，但如何找到全局最優(yōu)的樹依舊令人困惑。通常來講，我們遵循奧卡姆剃刀原則，傾向于選擇更簡單緊湊的樹，即最少的節(jié)點(diǎn)和最少的葉子。
    image.png

2.算法核心問題

2.1.分支數(shù)量和葉節(jié)點(diǎn)標(biāo)記

  • 分支數(shù)量是指從一個(gè)節(jié)點(diǎn)分出去的分支數(shù)目，也稱為節(jié)點(diǎn)的分支系數(shù)或分支率（branching ratio）。
  • 根據(jù)分支數(shù)量的不同，可以把樹分成二叉樹（分支數(shù)量恒等于2）和多叉樹（分支數(shù)量部分大于2）。一般來說，由于計(jì)算復(fù)雜度不同，計(jì)算機(jī)處理二叉樹的能力優(yōu)于多叉樹。
  • 關(guān)于葉節(jié)點(diǎn)標(biāo)記，理想情況下，最終樹的每一個(gè)葉子都只包含單一樣本，那該類別的標(biāo)記就是葉節(jié)點(diǎn)標(biāo)記；但是，多數(shù)情況下，葉子一般都有多個(gè)類型的樣本，這時(shí)就是少數(shù)服從多數(shù)，用數(shù)量最多的樣本類別來標(biāo)記。

2.2.節(jié)點(diǎn)選取和不純度

  • 在構(gòu)建模型時(shí)，我們希望節(jié)點(diǎn)數(shù)據(jù)盡可能地“純”，這樣就可以停止分叉。因此，我們定義了一個(gè)“不純度（impurity）”指標(biāo)，并選擇能夠使不純度下降最快的特征做分支。
  • 不純度用i(N)表示節(jié)點(diǎn)N的不純度。當(dāng)所有數(shù)據(jù)均屬于同一類別時(shí)，i(N)=0。常見的不純度測量函數(shù)有3個(gè)，分別是熵不純度(entropy impurity)、Gini不純度(Gini Index)、方差不純度、誤分類不純度((Classification error)，其中普遍采用的是前兩種。

1)熵不純度

  • 熵不純度亦稱為信息量不純度(information impurity)，是對信息量的一個(gè)加權(quán)計(jì)算，適用于類別標(biāo)記概率不等的情況（即P(w_j)≠P(w_i)），計(jì)算公式為：
    i_E(N) = -\sum_j P(w_j)log_2P(w_i)
  • 熵不純度最大值為1，表示最不確定；最小值為0，表示完全確定。
  • 舉例：14個(gè)人中有9個(gè)人買了N，5個(gè)人沒買N，則i(N)為：
    i_E(N) = -{\frac{9}{14}}log_2{\frac{9}{14}} - {\frac{5}{14}}log_2{\frac{5}{14}} = 0.940

2)方差不純度

  • 方差不純度適用于二分類問題，計(jì)算公式是：
    i_V(N) = P(w_1)P(w_2)

3)Gini不純度

  • Gini不純度也叫基尼指數(shù)，由方差不純度推廣而來，可用于多分類問題，表示當(dāng)節(jié)點(diǎn)N的類別標(biāo)記隨機(jī)選取時(shí)對應(yīng)的誤差率，計(jì)算公式為：
    i_g(N) = \sum_{i≠j}P(w_i)P(w_j) = 1- \sum_{j}P^2(w_j)
  • 當(dāng)P(w_1)=P(w_2)=...=P(w_j)=\frac{1}{j}時(shí)，Gini不純度最大，為1-\frac{1}{j}，表示最不確定；Gini不純度最小為0，表示完全確定。

4)誤分類不純度

  • 誤分類不純度用于衡量節(jié)點(diǎn)N處分類誤差的最小概率，類別標(biāo)記等概率時(shí)，誤分類不純度具有最好的峰值特性，計(jì)算公式為：
    i_C(N) = 1-max_jP(w_j)
  • 需注意的是：誤分類不純度存在不連續(xù)的導(dǎo)數(shù)值，因而在連續(xù)參數(shù)控件搜索最大值時(shí)會(huì)出現(xiàn)問題。

5)不純度變化量

二叉樹(即二分支)：

  • 二分支的不純度變化量以“不純度下降差”進(jìn)行比較，選擇\Delta i(N)最大的那個(gè)。
    \Delta i(N) = i(N)- P_Li(N_L)-(1-P_L)i(N_R)
  • 其中，N_L和N_R分別是左、右節(jié)點(diǎn)，i(N_L)和i(N_R)表示相應(yīng)的不純度。
  • 如果采用的是熵不純度，則不純度下降差就是本次分支所能提供的信息增益（Information Gain）

多叉樹(即多重分支)：

  • 多重分支的不純度變化量以“增益比不純度”進(jìn)行比較，選擇\Delta i_B(s)最大的那個(gè)。
    \Delta i(s) = i(N)- \sum_{k=1}^{B} P_ki(N_k)
    \Delta i_B(s) = \frac{\Delta i(s)}{-\sum_{k=1}^{B} P_k log_2 P_k}

6)不純度知識總結(jié)

1.我們通過不純度測量選擇最合適的分支特征，最常用的測量函數(shù)是基于信息加權(quán)的熵不純度和基于隨機(jī)選取誤差率的Gini不純度。
2.不管用哪種不純度測量函數(shù)，最終我們的目的是計(jì)算和比較各個(gè)特征的不純度變化量，選擇變化量最大的特征做分支。
3.實(shí)踐中發(fā)現(xiàn)選擇不同形式的不純度函數(shù)對最終分類效果及性能影響很小，切勿糾結(jié)于此！

2.3.停止分支準(zhǔn)則

  • 如果我們持續(xù)生長樹，直到所有的葉節(jié)點(diǎn)都達(dá)到最小的不純度，則數(shù)據(jù)可能會(huì)“過擬合”。
  • 為防止過擬合，我們可以使用停止分支準(zhǔn)則來控制樹的生長，常見的做法有：
    1.控制驗(yàn)證集或交叉驗(yàn)證的分類誤差：持續(xù)分支直至分類誤差最小化
    2.設(shè)定不純度變化量的閾值：當(dāng)不純度變化量低于閾值時(shí)，停止分支
    3.分析不純度變化量的統(tǒng)計(jì)顯著性：當(dāng)不純度下降統(tǒng)計(jì)不顯著，停止分支

1)驗(yàn)證集或交叉驗(yàn)證

  • 首先需說明：驗(yàn)證集和交叉驗(yàn)證是不同的。驗(yàn)證集(validation set)是指用部分的訓(xùn)練樣本(如90%)進(jìn)行訓(xùn)練，然后用剩余部分進(jìn)行驗(yàn)證；交叉驗(yàn)證(cross-validation)則依賴于從訓(xùn)練集中隨機(jī)選擇的子集，適用于樣本量較少的情況。
  • 該做法是預(yù)先設(shè)定一個(gè)分類誤差衡量指標(biāo)，如f1score、accuracy、G-mean、AUC等。然后持續(xù)進(jìn)行分支，直至達(dá)到指標(biāo)最優(yōu)為止。

2)設(shè)定不純度變化閾值

  • 該做法的優(yōu)點(diǎn)在于全部的樣本都可用于訓(xùn)練，而不需要預(yù)留驗(yàn)證的數(shù)據(jù)；但也存在明顯的缺點(diǎn)是：閾值的選擇相當(dāng)困難，因?yàn)槟Ｐ偷淖罱K性能和閾值的大小無直接的函數(shù)關(guān)系。簡而言之，就是我們雖然可以通過閾值停止分支，但無法得知這個(gè)模型是否是最優(yōu)的。
  • 我們一般通過設(shè)定決策樹最大深度（max_depth）、節(jié)點(diǎn)被分開的最小樣本數(shù)（min_samples_split）、葉子節(jié)點(diǎn)的最小樣本數(shù)（min_samples_leaf）、分開節(jié)點(diǎn)變?yōu)槿~子的最小比例（min_weight_fraction_leaf）、葉子節(jié)點(diǎn)的最大數(shù)（max_leaf_nodes）來間接設(shè)定閾值。

3)不純度變化量的統(tǒng)計(jì)顯著性分析

  • 這一做法融合了“假設(shè)檢驗(yàn)”技術(shù)，使用卡方檢驗(yàn)來做分析，當(dāng)某個(gè)節(jié)點(diǎn)“最顯著”的分支生成的卡方統(tǒng)計(jì)量比給定的置信水平低時(shí)，認(rèn)為統(tǒng)計(jì)不顯著，停止分支。
  • 統(tǒng)計(jì)顯著性分析的目的是確定候選分支是否有統(tǒng)計(jì)學(xué)上的意義，即判斷該分支是否明顯有別于隨機(jī)分支，用卡方來估計(jì)分支s和隨機(jī)分支的偏離度，則：
    X_2 = \sum_{i=1}^{2} \frac{{(n_{iL}-n_{ie})}^2}{n_{ie}}
  • 其中，n_{iL}是指s分支下w_{i}類的樣本送往左分支的數(shù)目，n_{ie}則是隨機(jī)分支情況下的值。

2.4.剪枝技術(shù)(pruning)

  • 因?yàn)橥Ｖ狗种?zhǔn)則是從樹的根節(jié)點(diǎn)開始優(yōu)化，在節(jié)點(diǎn)N處進(jìn)行的最優(yōu)分支決策不會(huì)考慮對其下面一層的節(jié)點(diǎn)的影響。因此，有時(shí)候，分支會(huì)因?yàn)槿鄙僮銐虻那罢靶远^早停止，稱為“視界局限效應(yīng)”。
  • 剪枝技術(shù)和停止分支準(zhǔn)則不同的是：它允許樹先充分生長直到葉節(jié)點(diǎn)都有最小的不純度，從而克服視界局限效應(yīng)；然后再考慮是否消去相鄰的葉子或子樹。
  • 簡而言之，停止分支準(zhǔn)則是在樹還是“樹苗”的時(shí)候就控制它是否繼續(xù)生長；而剪枝技術(shù)則等樹長成“參天大樹”之后再慢慢修剪。因此，它們也被稱為“預(yù)剪枝”技術(shù)和“后剪枝”技術(shù)。

1)剪枝技術(shù)優(yōu)缺點(diǎn)

  • 優(yōu)點(diǎn)：克服了“視界局限效應(yīng)”，且無需保留驗(yàn)證集數(shù)據(jù)。
  • 缺點(diǎn)：計(jì)算量代價(jià)過大，特別是對于大樣本集。

2)剪枝類型

  • 不純度剪枝：通過比較刪除后的不純度變化量，考慮是否刪除相鄰的葉節(jié)點(diǎn)，并令他們的公共父節(jié)點(diǎn)成為新的葉節(jié)點(diǎn)。
  • 規(guī)則剪枝：規(guī)則剪枝的優(yōu)點(diǎn)在于它考慮了上下文信息的區(qū)別，其在每一個(gè)葉節(jié)點(diǎn)上都附有一條規(guī)則，根據(jù)規(guī)則是否冗余的判斷，進(jìn)行規(guī)則簡化，提高模型的推廣能力。后文中提及的C4.5算法就是基于樹規(guī)則的剪枝。
  • 綜上所述，我們在進(jìn)行決策樹模型優(yōu)化時(shí)，可從停止分支和剪枝等方面進(jìn)行優(yōu)化。
  • 一般來說，對于小樣本的數(shù)據(jù)集，由于計(jì)算代價(jià)小，剪枝方法優(yōu)于分支停止方法。

2.5.特征處理

1)連續(xù)值處理

  • 決策樹對連續(xù)變量的處理方式是將其離散化。
  • 為了減少計(jì)算量，不管是二叉樹還是多叉樹，常見做法都是將數(shù)據(jù)一分為二，計(jì)算使不純度最小的劃分點(diǎn)。

2)缺失值處理

  • 不同于其他算法，決策樹對缺失值的容忍度較高，常用的樹算法如CART、C4.5都支持缺失值處理。
  • 不同樹算法的缺失值處理方式不同，在此不做具體說明。

3.常用樹算法

在這里，我們介紹3種最常用的決策樹算法：CART、ID3、C4.5

3.1.CART算法

  • CART算法是一種二分遞歸分割技術(shù)，把當(dāng)前樣本劃分為兩個(gè)子樣本，使得生成的每個(gè)非葉子結(jié)點(diǎn)都有兩個(gè)分支， 因此CART算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹(binary tree)。
  • 二叉樹的分支率(branching ratio)為2，每一步的決策時(shí)只能是“是”或者“否”，即使一個(gè)特征有多個(gè)取值，也是把數(shù)據(jù)分為兩部分。任何一個(gè)具有任意分支率的樹都可以用二叉樹表示。
image.png

1)CART的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

  • 訓(xùn)練簡單：二叉樹具有萬能的表達(dá)能力，并且訓(xùn)練上非常簡便。
  • 優(yōu)化簡單：二叉樹作為一棵單調(diào)簡單的樹，在節(jié)點(diǎn)處的判別是一個(gè)一維優(yōu)化的過程，更容易在節(jié)點(diǎn)處找到最優(yōu)決策。
  • 模型普適：不同另外兩種算法，CART既可用于分類，又能用于回歸。

缺點(diǎn)

  • 模型不穩(wěn)定：CART算法最大的缺點(diǎn)在于，即便是很小的樣本點(diǎn)變動(dòng)，也會(huì)導(dǎo)致截然不同的模型。這個(gè)缺點(diǎn)可以由集成學(xué)習(xí)里的隨機(jī)森林方法、gradientboost等方法補(bǔ)足。

3.2.ID3算法

  • ID3最早的設(shè)計(jì)意圖是用于處理“語義（無序）數(shù)據(jù)”的，因此，對于它并不能直接處理數(shù)值連續(xù)變量，但它開創(chuàng)了使用熵來度量不純度的先河，率先對信息進(jìn)行了加權(quán)計(jì)算。
  • 當(dāng)然，作為一個(gè)創(chuàng)新的算法，有著很多的不足。

1)ID3的不足

  • 無法處理連續(xù)變量和缺失值。
  • 無法剪枝，沒有考慮過擬合的問題。

3.3.C4.5算法

C4.5是ID3的作者改良后的版本，它解決了ID3的不足，包括連續(xù)變量的處理、剪枝技術(shù)等。

1)C4.5的不足

  • 計(jì)算效率低：C4.5生成的是多叉樹，相較二叉樹，在節(jié)點(diǎn)處理上更復(fù)雜，運(yùn)行效率較低。
  • 不支持回歸：C4.5只能用于分類，這也限制了它的推廣。

3.4.算法比較

image.png

對這三個(gè)算法感興趣想要進(jìn)一步了解的童鞋可以看一下這位博主的文章，寫得非常詳細(xì)：
1.《決策樹算法原理(上)》https://www.cnblogs.com/pinard/p/6050306.html
2.《決策樹算法原理(下)》https://www.cnblogs.com/pinard/p/6053344.html

THE END

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

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