決策樹
前面我們講了線性回歸和樸素貝葉斯分類模型惑折。前者只能做回歸授账，后者只能做分類。但本文中要講的決策樹模型惨驶，卻既可以用于分類白热，又可以用于回歸。
什么是決策樹
決策樹是一種非炒植罚基礎(chǔ)又常見的機(jī)器學(xué)習(xí)模型屋确。
一棵決策樹（Decision Tree）是一個(gè)樹結(jié)構(gòu)（可以是二叉樹或非二叉樹），每個(gè)非葉節(jié)點(diǎn)對(duì)應(yīng)一個(gè)特征续扔，該節(jié)點(diǎn)的每個(gè)分支代表這個(gè)特征的一個(gè)取值攻臀，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別或一個(gè)回歸函數(shù)。
使用決策樹進(jìn)行決策的過程就是從根節(jié)點(diǎn)開始纱昧，提取出待分類項(xiàng)中相應(yīng)的特征刨啸，按照其值選擇輸出分支，依次向下识脆，直到到達(dá)葉子節(jié)點(diǎn)设联，將葉子節(jié)點(diǎn)存放的類別或者回歸函數(shù)的運(yùn)算結(jié)果作為輸出（決策）結(jié)果。
決策樹的決策過程非常直觀灼捂，容易被人理解离例，而且運(yùn)算量相對(duì)小。它在機(jī)器學(xué)習(xí)當(dāng)中非常重要悉稠。如果要列舉“十大機(jī)器學(xué)習(xí)模型”的話宫蛆，決策樹應(yīng)當(dāng)位列前三。
直觀理解決策樹
下圖是一個(gè)決策樹的例子：
這棵樹的作用偎球，是對(duì)要不要接受一個(gè) Offer 做出判斷洒扎。
我們看到，這棵樹一共有7個(gè)節(jié)點(diǎn)衰絮，其中有4個(gè)葉子節(jié)點(diǎn)和3個(gè)非葉子節(jié)點(diǎn)袍冷。它是一棵分類樹，每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)類別猫牡。
那么有4個(gè)葉子節(jié)點(diǎn)胡诗，是說一共有4個(gè)類別嗎？當(dāng)然不是淌友！從圖中我們也可以看出煌恢，總共只有2個(gè)類別：accept offer（接受）和 decline offer（拒絕）。
理論上講震庭，一棵分類樹有 n 個(gè)葉子節(jié)點(diǎn)（n>1瑰抵，只有一個(gè)結(jié)果也就不用分類了）時(shí)，可能對(duì)應(yīng)2~n 個(gè)類別器联。不同判斷路徑是可能得到相同結(jié)果的（殊途同歸）二汛。
以上例而言婿崭，拿到一個(gè) Offer 后，要判斷三個(gè)條件：(1)年薪肴颊；(2)通勤時(shí)間氓栈；(3)免費(fèi)咖啡。
這三個(gè)條件的重要程度顯然是不一樣的婿着，最重要的是根節(jié)點(diǎn)授瘦，越靠近根節(jié)點(diǎn)，也就越重要——如果年薪低于5萬美元竟宋，也就不用考慮了提完，直接 say no；當(dāng)工資足夠時(shí)袜硫，如果通勤時(shí)間大于一個(gè)小時(shí)氯葬，也不去那里上班；就算通勤時(shí)間不超過一小時(shí)婉陷，還要看是不是有免費(fèi)咖啡帚称，沒有也不去。
這三個(gè)非葉子節(jié)點(diǎn)（含根節(jié)點(diǎn)）秽澳，統(tǒng)稱決策節(jié)點(diǎn)闯睹，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)條件判斷，這個(gè)條件判斷的條件担神，我們叫做特征楼吃。上例是一個(gè)有三個(gè)特征的分類樹。
當(dāng)我們用這棵樹來判斷一個(gè) Offer 的時(shí)候妄讯，我們就需要從這個(gè) Offer 中提取年薪孩锡、通勤時(shí)間和有否免費(fèi)咖啡三個(gè)特征出來，將這三個(gè)值（比如：[ $ 65,000亥贸，0.5 hour, don’t offer free coffee]）輸入給該樹躬窜。
該樹按照根節(jié)點(diǎn)向下的順序篩選一個(gè)個(gè)條件，直到到達(dá)葉子為止炕置。到達(dá)的葉子所對(duì)應(yīng)的類別就是預(yù)測(cè)結(jié)果荣挨。
構(gòu)建決策樹
決策樹的作用過程是很簡(jiǎn)單的，那么決策樹是如何構(gòu)造的呢朴摊？
前面講了默垄，獲得一種模型的過程叫訓(xùn)練，那么我們?nèi)绾斡?xùn)練可以得到一棵決策樹呢甚纲？
簡(jiǎn)單講口锭，有以下幾步：
- 準(zhǔn)備若干的訓(xùn)練數(shù)據(jù)（假設(shè)有 m 個(gè)樣本）；
- 標(biāo)明每個(gè)樣本預(yù)期的類別介杆；
- 人為選取一些特征（即決策條件）鹃操；
- 為每個(gè)訓(xùn)練樣本對(duì)應(yīng)所有需要的特征生成相應(yīng)值——數(shù)值化特征况既；
- 將通過上面的1-4步獲得的訓(xùn)練數(shù)據(jù)輸入給訓(xùn)練算法，訓(xùn)練算法通過一定的原則组民，決定各個(gè)特征的重要性程度，然后按照決策重要性從高到底悲靴，生成決策樹臭胜。
那么訓(xùn)練算法到底是怎么樣的？決定特征重要程度的原則又是什么呢癞尚？
幾種常用算法
決策樹的構(gòu)造過程是一個(gè)迭代的過程耸三。每次迭代中，采用不同特征作為分裂點(diǎn)浇揩，來將樣本數(shù)據(jù)劃分成不同的類別仪壮。被用作分裂點(diǎn)的特征叫做分裂特征。
選擇分裂特征的目標(biāo)胳徽，是讓各個(gè)分裂子集盡可能地“純”积锅，即盡量讓一個(gè)分裂子集中的樣本都屬于同一類別。
如何使得各個(gè)分裂子集“純”养盗，算法也有多種缚陷，這里我們來看幾種。
ID3 算法
我們先來看看最直接也最簡(jiǎn)單的 ID3 算法（Iterative Dichotomiser 3）往核。
該算法的核心是：以信息增益為度量箫爷，選擇分裂后信息增益最大的特征進(jìn)行分裂。
首先我們要了解一個(gè)概念——信息熵聂儒。
假設(shè)一個(gè)隨機(jī)變量 x 有 n 種取值虎锚，分別為 {x1,x1,...,xn}，每一種取值取到的概率分別是 {p1,p2,...,pn}衩婚，那么 x 的信息熵定義為：
Entropy(x)=?∑ni=1pilog2(pi)
熵表示的是信息的混亂程度窜护，信息越混亂，熵值越大谅猾。
設(shè) S 為全部樣本的集合柄慰，全部的樣本一共分為 n 個(gè)類，則：
Entropy(S)=?∑ni=1pilog2(pi)
其中税娜，pi 為屬于第 i 個(gè)類別的樣本坐搔，在總樣本中出現(xiàn)的概率。
接下來要了解的概念是信息增益敬矩，信息增益的公式為（下式表達(dá)的是樣本集合 S 基于特征 T 進(jìn)行分裂后所獲取的信息增益）：
InformationGain(T)=Entropy(S)?∑value(T)|Sv||S|Entropy(Sv)
其中：
- S 為全部樣本集合概行，|S|為S 的樣本數(shù)；
- T為樣本的一個(gè)特征弧岳；
- value(T) 是特征 T 所有取值的集合凳忙；
- v 是 T 的一個(gè)特征值业踏；
- Sv 是 S 中特征 T 的值為 v 的樣本的集合，|Sv|為Sv 的樣本數(shù)涧卵。
C4.5
前面提到的 ID3 只是最簡(jiǎn)單的一種決策樹算法勤家。
它選用信息增量作為特征度量，雖然直觀柳恐，但卻有一個(gè)很大的缺點(diǎn)：ID3一般會(huì)優(yōu)先選擇取值種類較多的特征作為分裂特征伐脖。
因?yàn)槿≈捣N類多的特征會(huì)有相對(duì)較大的信息增益——信息增益反映的是給定一個(gè)條件以后不確定性被減少的程度，必然是分得越細(xì)的數(shù)據(jù)集確定性更高乐设。
被取值多的特征分裂讼庇，分裂成的結(jié)果也就容易細(xì)；分裂結(jié)果越細(xì)近尚，則信息增益越大蠕啄。
為了避免這個(gè)不足，在 ID3 算法的基礎(chǔ)上誕生了它的改進(jìn)版本：C4.5 算法戈锻。
C4.5 選用信息增益率（Gain Ratio)——用比例而不是單純的量——作為選擇分支的標(biāo)準(zhǔn)歼跟。
信息增益率通過引入一個(gè)被稱作分裂信息（Split Information）的項(xiàng)，來懲罰取值可能性較多的特征舶沛。
SplitInformation(T)=?∑value(T)|Sv||S|log|Sv||S|
GainRatio(T)=InformationGain(T)SplitInformation(T)
ID3 還有一個(gè)問題：就是不能處理取值在連續(xù)區(qū)間的特征嘹承。例如上面例子里，假設(shè)訓(xùn)練樣本有一個(gè)特征是年齡如庭，取值為(0,100)區(qū)間內(nèi)的實(shí)數(shù)叹卷。ID3 就不知如何是好了。
C4.5 在這方面也有彌補(bǔ)坪它，具體做法如下骤竹。
- 把需要處理的樣本（對(duì)應(yīng)整棵樹）或樣本子集（對(duì)應(yīng)子樹）按照連續(xù)變量的大小從小到大進(jìn)行排序。
- 假設(shè)所有 m 個(gè)樣本數(shù)據(jù)在特征上的實(shí)際取值一共有 k（k<=m）個(gè)往毡，那么總共有 k?1 個(gè)可能的候選分割閾值點(diǎn)蒙揣，每個(gè)候選的分割閾值點(diǎn)的值為上述排序后的特征值中兩兩前后連續(xù)元素的中點(diǎn)。根據(jù)這 k-1 個(gè)分割點(diǎn)把原來連續(xù)的一個(gè)特征开瞭，轉(zhuǎn)化為 k-1 個(gè) Bool 特征懒震。
- 用信息增益率選擇這 k-1 個(gè)特征的最佳劃分。
但是嗤详，C4.5 有個(gè)問題：當(dāng)某個(gè) |Sv| 的大小跟 |S| 的大小接近的時(shí)候：
SplitInformation(T)→0,GainRatio(T)→∞
為了避免這種情況導(dǎo)致某個(gè)其實(shí)無關(guān)緊要的特征占據(jù)根節(jié)點(diǎn)个扰，可以采用啟發(fā)式的思路，對(duì)每個(gè)特征先計(jì)算信息增益量葱色，在其信息增益量較高的情況下递宅，才應(yīng)用信息增益率作為分裂標(biāo)準(zhǔn)。
C4.5 的優(yōu)良性能和對(duì)數(shù)據(jù)和運(yùn)算力要求都相對(duì)較小的特點(diǎn)，使得它成為了機(jī)器學(xué)習(xí)最常用的算法之一办龄。它在實(shí)際應(yīng)用中的地位烘绽，比 ID3 還要高。
CART
ID3 和 C4.5 構(gòu)造的都是分類樹俐填。還有一種算法安接，在決策樹中應(yīng)用非常廣泛，它就是 CART 算法英融。
CART 算法的全稱是： Classification and Regression Tree赫段，分類和回歸樹。從這個(gè)名字一望可知矢赁，它不僅可以用來做分類，還可以用來做回歸贬丛。
CART 算法的運(yùn)行過程和 ID3 及 C4.5 大致相同撩银，不同之處在于：
- CART 的特征選取依據(jù)不是增益量或者增益率，而是 Gini 系數(shù)（Gini Coefficient）豺憔。每次選擇 Gini 系數(shù)最小的特征作為最優(yōu)切分點(diǎn)额获；
- CART 是一棵嚴(yán)格二叉樹。每次分裂只做二分恭应。
這里面要特別提到概念：Gini 系數(shù)（Gini Coefficient）抄邀。
Gini 系數(shù)原本是一個(gè)統(tǒng)計(jì)學(xué)概念，20世紀(jì)初由意大利學(xué)者科拉多·基尼提出昼榛，是用來判斷年收入分配公平程度的指標(biāo)境肾。Gini 系數(shù)本身是一個(gè)比例數(shù)，取值在0到1之間胆屿。
當(dāng) Gini 系數(shù)用于評(píng)判一個(gè)國(guó)家的民眾收入時(shí)奥喻，取值越小，說明年收入分配越平均非迹，反之則越集中环鲤。當(dāng) Gini 系數(shù)為0時(shí)，說明這一個(gè)國(guó)家的年收入在所有國(guó)民中平均分配憎兽，而當(dāng) Gini 系數(shù)為1時(shí)冷离，則說明該國(guó)該年所有收入都集中在一個(gè)人手里，其余的國(guó)民沒有收入纯命。
在 Gini 系數(shù)出現(xiàn)之前西剥，美國(guó)經(jīng)濟(jì)學(xué)家馬克斯·勞倫茨提出了“收入分配的曲線”（又稱勞倫茨曲線）的概念。下圖就是一條勞倫茨曲線：
圖中橫軸為人口累計(jì)百分比扎附，縱軸為該部分人的收入占全部人口總收入的百分比蔫耽，紅色線段表示人口收入分配處于絕對(duì)平均狀態(tài)，而橘色曲線就是勞倫茨曲線，表現(xiàn)的是實(shí)際的收入分配情況匙铡。
我們可以看出图甜，橫軸75%處，如果依據(jù)紅色線段鳖眼，對(duì)應(yīng)的縱軸也是75%黑毅，但是按照橘色曲線，則對(duì)應(yīng)縱軸只有不到40%钦讳。
A 是紅色線段和橘色曲線所夾部分面積矿瘦，而 B 是橘色曲線下部分的面積。Gini 系數(shù)實(shí)際上就是 AA+B的比值愿卒。這個(gè)概念在經(jīng)濟(jì)學(xué)領(lǐng)域遠(yuǎn)比在機(jī)器學(xué)習(xí)中有名缚去。
Gini 系數(shù)的計(jì)算方法是：
Gini(p)=∑ni=1pi(1?pi)=1?∑ni=1p2i
對(duì)于二分類問題，若樣本屬于第一類的概率是 p琼开，則：
Gini(p)=2p(1?p)
這時(shí)易结，如果 p = 0.5， 則 Gini 系數(shù)為0.5柜候；如果 p = 0.9搞动， 則 Gini 系數(shù)為0.18。0.18 < 0.5渣刷，根據(jù) CART 的原則鹦肿，當(dāng) p=0.9 時(shí)，這個(gè)特征更容易被選中作為分裂特征辅柴。
由此可見箩溃，對(duì)二分類問題中，兩種可能性的概率越不平均碌嘀，則越可能是更佳優(yōu)越的切分點(diǎn)碾篡。
上面的例子雖然用的是二分類，但實(shí)際上筏餐，對(duì)于多分類开泽，趨勢(shì)是一樣的，那些概率分布在不同可能性之間越不平均的特征魁瞪，越容易成為分裂特征穆律。
到了這里，可能有朋友會(huì)誤會(huì)导俘，認(rèn)為我們一直說的都是用 CART 做分類時(shí)的做法峦耘。但是實(shí)際上，無論是做分類還是做回歸旅薄，都是一樣的辅髓。
回歸樹和分類樹的區(qū)別在于最終的輸出值到底是連續(xù)的還是離散的泣崩，每個(gè)特征——也就是分裂點(diǎn)決策條件——無論特征值本身是連續(xù)的還是離散的，都要被當(dāng)作離散的來處理洛口，而且都是被轉(zhuǎn)化為二分類特征矫付，來進(jìn)行處理：
- 如果對(duì)應(yīng)的分裂特征是連續(xù)的，處理與 C4.5 算法相似第焰；
- 如果特征是離散的买优，而該特征總共有 k 個(gè)取值，則將這一個(gè)特征轉(zhuǎn)化為 k 個(gè)特征挺举，對(duì)每一個(gè)新特征按照是不是取這個(gè)值來分 Yes 和 No杀赢。
注意： 還有一個(gè)詞——Gini 指數(shù)（Gini Index），經(jīng)常在一些資料中被提及湘纵，并在 CART 算法中用來代替 Gini 系數(shù)脂崔，其實(shí) Gini 指數(shù)就是 Gini 系數(shù)乘100倍作百分比表示，兩者其實(shí)是一個(gè)東西梧喷。
