一、介紹
決策樹（Decision Tree）是一個(gè)樹結(jié)構(gòu)（可以是二叉樹或非二叉樹），其中每個(gè)非葉節(jié)點(diǎn)表示一個(gè)屬性上的測試，每個(gè)分支代表一個(gè)測試輸出，每個(gè)葉節(jié)點(diǎn)代表一種類別。機(jī)器學(xué)習(xí)中，決策樹是一個(gè)預(yù)測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。
決策樹最重要的是決策樹的構(gòu)造。所謂決策樹的構(gòu)造就是進(jìn)行屬性選擇度量確定各個(gè)特征屬性之間的拓?fù)浣Y(jié)構(gòu)。構(gòu)造決策樹的關(guān)鍵步驟是分裂屬性。所謂分裂屬性就是在某個(gè)節(jié)點(diǎn)處按照某一特征屬性的不同劃分構(gòu)造不同的分支，其目標(biāo)是讓各個(gè)分裂子集盡可能地“純”。盡可能“純”就是盡量讓一個(gè)分裂子集中待分類項(xiàng)屬于同一類別。分裂屬性分為三種不同的情況：
1、屬性是離散值且不要求生成二叉決策樹。此時(shí)用屬性的每一個(gè)劃分作為一個(gè)分支。
2、屬性是離散值且要求生成二叉決策樹。此時(shí)使用屬性劃分的一個(gè)子集進(jìn)行測試，按照“屬于此子集”和“不屬于此子集”分成兩個(gè)分支。
3、屬性是連續(xù)值。此時(shí)確定一個(gè)值作為分裂點(diǎn)split_point，按照>split_point和<=split_point生成兩個(gè)分支。
決策樹的屬性分裂選擇是”貪心“算法，也就是沒有回溯的。
二、原理
2.1 信息熵
1948年，香農(nóng)提出了“信息熵”的概念，才解決了對信息的量化度量問題。信息熵這個(gè)詞是C．E．香農(nóng)從熱力學(xué)中借用過來的。熱力學(xué)中的熱熵是表示分子狀態(tài)混亂程度的物理量。香農(nóng)用信息熵的概念來描述信源的不確定度。
由于信息的冗余性，冗余大小與信息中每個(gè)符號（數(shù)字、字母或單詞）的出現(xiàn)概率或者說不確定性有關(guān)。比如:問明天股票漲還是跌;回答:明天NBA決賽，這兩者似乎沒有什么聯(lián)系，所以你的信息量很少。但是回答：因?yàn)槊魈齑蠹叶既タ碞BA決賽，沒人坐莊導(dǎo)致股票大跌。因?yàn)槟愕幕卮鹗共淮_定變得很確定，包含的信息量也就很大。有些事情本來就很確定了，例如太陽從東邊升起，你說一百遍，也沒有絲毫信息量，因?yàn)檫@件事情確定的不能確定了。所以說信息量的大小跟事情不確定性的變化有關(guān)。
信息熵的三大性質(zhì)：
單調(diào)性，即發(fā)生概率越高的事件，其所攜帶的信息熵越低。極端案例就是“太陽從東方升起”，因?yàn)闉榇_定事件，所以不攜帶任何信息量。從信息論的角度，認(rèn)為這句話沒有消除任何不確定性。
非負(fù)性，即信息熵不能為負(fù)。這個(gè)很好理解，因?yàn)樨?fù)的信息，即你得知了某個(gè)信息后，卻增加了不確定性是不合邏輯的。
累加性，即多隨機(jī)事件同時(shí)發(fā)生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和，兩個(gè)事件相互獨(dú)立有，信息熵H(A,B)=H(A)+H(B)；如果兩個(gè)事件不相互獨(dú)立，那么滿足H(A,B)=H(A)+H(B)-I(A,B) ，其中I(A,B) 是互信息（mutual information），代表一個(gè)隨機(jī)變量包含另一個(gè)隨機(jī)變量信息量的度量。
那么，不確定性的變化跟什么有關(guān)呢？
一，跟事情的可能結(jié)果的數(shù)量有關(guān)；二，跟概率有關(guān)。
一個(gè)事件的信息量就是這個(gè)事件發(fā)生的概率的負(fù)對數(shù)。信息熵是跟所有可能性有關(guān)系的。每個(gè)可能事件的發(fā)生都有個(gè)概率。信息熵就是平均而言發(fā)生一個(gè)事件我們得到的信息量大?。ㄒ簿褪钦f信息熵代表某元組標(biāo)號所需的平均信息量）。所以數(shù)學(xué)上，信息熵其實(shí)是信息量的期望。
信息熵?cái)?shù)學(xué)表達(dá)式，如圖2-1所示：
Ent（D）的值越小，則D的純度越高
信息增益： 假定離散屬性a有V個(gè)可能的取值{a1,a2,a3,...,av}，若用a來對樣本集D進(jìn)行劃分，則會(huì)產(chǎn)生V個(gè)分支結(jié)點(diǎn)，其中第V個(gè)分支結(jié)點(diǎn)包含D中所有屬性a上取值為av的樣本，記作DV。數(shù)學(xué)表達(dá)式如圖2-2所示：
一般而言，信息增益越大，則意味著使用屬性a來進(jìn)行劃分所獲得的“純度提升”越大。
2.2 ID3.5決策樹
通過上述介紹，我們知道了信息熵和決策樹構(gòu)造過程是一個(gè)提純的過程，根據(jù)信息熵來判斷我們決策樹構(gòu)造方向。熵的變化可以被看做是信息增益，決策樹ID3算法的核心思想是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進(jìn)行劃分。
從信息論知識中我們知道，期望信息越小，信息增益越大，從而純度越高。“純”就是盡量讓一個(gè)劃分子集中待分類項(xiàng)屬于同一類別。
舉一個(gè)選瓜的例子（周志華《機(jī)器學(xué)習(xí)》），數(shù)據(jù)如圖2-3所示：
正例(好瓜)占 8/17，反例占 9/17 ，根結(jié)點(diǎn)的信息熵為，如圖2-4所示：
根據(jù)數(shù)據(jù)表可知，特征有色澤、根蒂、敲聲、紋理、臍部、觸感等六個(gè)特征。我們需要計(jì)算每個(gè)屬性的信息增益，以此最大程度的“提純”。
首先計(jì)算“色澤”，共3個(gè)子集{青綠，烏黑，淺白}，D1（青綠）={1,4,6,10,13,17}，D2（烏黑）={2,3,7,8,9,15}，D3（淺白）={5,11,12,14,16}。D1（青綠）集合中正例p1=3/6,反例p2=3/6。D2（烏黑）集合正例 p1=4/6,反例p2=2/6。D3（淺白）集合正例 p1=1/5,反例p2=4/5。計(jì)算過程如2-5所示：
根據(jù)色澤三個(gè)子集的信息熵即可計(jì)算出，“色澤”屬性的信息增益，如圖2-6所示：
同理，我們計(jì)算出其他屬性信息增益：Gain（D，根蒂）=0.143；Gain（D，敲聲）=0.141
Gain（D，紋理）=0.381；Gain（D，臍部）=0.289；Gain（D，觸感）=0.006
根據(jù)之前“提純”的原則，我們選擇信息增益最大作為第一個(gè)分支節(jié)點(diǎn)。劃分如圖2-7所示：
根據(jù)紋理劃分成3個(gè)子集，接下來要對每一個(gè)子集進(jìn)行下一步劃分，D1（紋理清晰）={1,2，3,4,5,6,8,10,15}，D2（紋理模糊）={7,9,13,14,17}，D3(紋理模糊)={11,12,16}。因?yàn)镈3子集中類別全是壞瓜，所以不需要再做劃分。剩下的屬性集合{色澤，根蒂，敲聲，臍部，觸感}，計(jì)算D1各屬性信息增益：
Gain(D1,色澤)=0.043; Gain(D1,根蒂)=0.458; Gain(D1,敲聲)=0.331; Gain(D1,臍部)=0.458; Gain(D1,觸感)=0.458
根據(jù)“提純”原則，我們繼續(xù)劃分可以任意選擇根蒂，臍部，觸感三個(gè)屬性其中一個(gè)為劃分結(jié)點(diǎn)，經(jīng)過多次劃分至只剩單一類別后，得到?jīng)Q策樹圖2-3所示：
2.3 C4.5決策樹
ID3.5使用信息增益作為“提純”方法，但實(shí)際上，信息增益對可取數(shù)目較多的屬性有所偏好，所以為了減少這種影響，提出用增益率來選擇最優(yōu)劃分，也就是C4.5決策樹算法。
增益率定義，如圖2-9所示：
可以從式中看出數(shù)目越多（V越大），IV（a）會(huì)越大，Gain_ratio越小，所以增益率對可取數(shù)目較少的屬性有所偏好。因此C4.5并不是直接選取增益率最高的，而是先從劃分屬性從選取信息增益高于平均水平的屬性，再從中選擇信息增益率最高的最為劃分結(jié)點(diǎn)。
2.4 CART決策樹
CART決策樹使用“基尼指數(shù)”（Gini index）來劃分屬性。數(shù)據(jù)集D純度使用基尼值來度量，如圖2-10所示：
Gini(D)反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個(gè)樣本，其類別標(biāo)記不一致的概率，因此，Gini(D)越小，則數(shù)據(jù)集D的純度越高。
屬性a的基尼指數(shù)定義，如圖2-11所示：
于是我們在候選屬性集合中選擇基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性。
2.5 剪枝處理
剪枝處理是為了解決決策樹分支過多而產(chǎn)生的“過擬合”問題。剪枝策略有“預(yù)剪枝”和“后剪枝”。
“預(yù)剪枝”是決策樹生成時(shí)，計(jì)算并比較每個(gè)結(jié)點(diǎn)劃分前和劃分后的驗(yàn)證集精度，若劃分前的結(jié)點(diǎn)精度要比劃分后高，則剪枝。反之則確認(rèn)劃分此結(jié)點(diǎn)
“后剪枝”是決策樹生成后，自底向上進(jìn)行計(jì)算剪枝前和剪枝后的驗(yàn)證集精度。若剪枝后比剪枝前的結(jié)點(diǎn)精度要高則剪枝，反之保留。
優(yōu)缺點(diǎn)：
“預(yù)剪枝”：由于一邊劃分結(jié)點(diǎn)的同時(shí)一邊計(jì)算精度來決定是否剪枝，所以“預(yù)剪枝”可以很有效的減少?zèng)Q策樹訓(xùn)練時(shí)間開銷和測試時(shí)間開銷。但由于很多分支還未完成展開并剪去，基于“貪心”本質(zhì)也很容易忽略后續(xù)優(yōu)秀的分支，導(dǎo)致欠擬合風(fēng)險(xiǎn)。
“后剪枝”：由于需要完全生成一顆決策樹后再進(jìn)行計(jì)算剪枝，導(dǎo)致時(shí)間開銷的增加，但是欠擬合的風(fēng)險(xiǎn)很小。
2.6 連續(xù)值處理
當(dāng)數(shù)據(jù)集中出現(xiàn)了連續(xù)屬性如何使用決策樹進(jìn)行劃分結(jié)點(diǎn)？由于連續(xù)屬性相對于離散屬性可取數(shù)目不是有限的，所以不能直接根據(jù)連續(xù)屬性可選值進(jìn)行劃分。
最簡單的策略使用二分法：
樣本集D中有連續(xù)屬性a，我們先進(jìn)行排序{a1,a2,a3....,an}。劃分時(shí)，以任意t為例，有1<=t<=n-1，
,即把區(qū)間[ai,ai+1)的中位點(diǎn)
作為候選點(diǎn)。然后即可像考慮離散屬性值一樣考慮這些劃分點(diǎn)：
Gain(D,a,t)是樣本集基于劃分點(diǎn)t二分后的信息增益，我們選擇Gain(D,a,t)最大的為劃分點(diǎn)。
2.7 缺失值處理
當(dāng)遇到樣本中某屬性的值缺失的情況下如何進(jìn)行劃分屬性選擇？
我們假設(shè)樣本集D和屬性a,用D~ 表示在D中屬性a上沒有缺失的樣本子集，D+表示在D中屬性a上表示的正類，D-表示在D中屬性a上的負(fù)類（假設(shè)二分類問題）。k表示屬性a中類別。我們可以用p表示無缺失值樣本所占的比例，pk+表示無缺失值樣本中第k類正例在第k類中所占的比例，Pk-表示無缺失值樣本中第k類負(fù)例在第k類中所占的比例，r表示無缺失值樣本中第k類在屬性a中無缺失樣本子集D~所占比例。定義如圖2-15 所示：
基于上述定義，我們可將信息增益計(jì)算公式推廣，如圖2-16所示：
例：有下列有缺失的西瓜數(shù)據(jù)集，如圖2-17所示：
我們以色澤為例來計(jì)算色澤屬性下各類別的信息增益，以此作為結(jié)點(diǎn)劃分依據(jù)。
樣本集D中有17個(gè)樣例，色澤屬性中無缺失的樣例子集D~編號有{2,3,4,6,7,8,9,10,11,12,14,15,16,17}。
D~信息熵，計(jì)算如圖2-20所示：
樣本集屬性為色澤的信息增益為：
然后計(jì)算出其它所有屬性在D中的信息增益。選擇信息增益最大的為最佳劃分結(jié)點(diǎn)
三、代碼實(shí)現(xiàn)
3.1 決策樹構(gòu)建流程
- 遍歷并評估每個(gè)特征
- 判斷是否某個(gè)分支下的數(shù)據(jù)屬于同一類型，如果是則返回作為標(biāo)簽，否之繼續(xù)。
- 尋找劃分?jǐn)?shù)據(jù)集的最好特征
- 劃分?jǐn)?shù)據(jù)集
- 創(chuàng)建分支節(jié)點(diǎn)
- 遞歸調(diào)用創(chuàng)建新的分支節(jié)點(diǎn)函數(shù)createBranch
3.2構(gòu)建決策樹預(yù)測隱形眼鏡類型
參考《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》第三章Logistic回歸樣例：使用決策樹預(yù)測隱形眼鏡類型
預(yù)測隱形眼鏡訓(xùn)練集樣本如圖3-1所示：
根據(jù)特征劃分?jǐn)?shù)據(jù)集，這樣可以依次計(jì)算出各屬性的信息增益，以此對比選擇最好的劃分節(jié)點(diǎn)。代碼如圖3-2所示
計(jì)算給定數(shù)據(jù)集的信息熵，代碼如圖3-3所示：
8 ~ 12行代碼統(tǒng)計(jì)了給定樣本集分類結(jié)果的各占的數(shù)量，14~16行計(jì)算出樣本信息熵 圖3-4
計(jì)算出信息熵后，接下來要計(jì)算每個(gè)屬性的信息增益，等到信息增益最大的屬性，代碼如圖3-5所示：
39 ~ 51行遍歷屬性a中總共有v個(gè)可能的值，計(jì)算{a1,a2,......,av}各自信息熵和信息增益，并篩選出最大的信息增益，計(jì)算信息增益表達(dá)式如圖3-6所示：
當(dāng)程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性或者每個(gè)分支所有實(shí)例都具有相同的分類，那么就可以結(jié)束算法。但是很多情況特征數(shù)目并不是每次劃分?jǐn)?shù)據(jù)分組的時(shí)候都減少，如C4.5和CART算法，因此我們可以設(shè)置算法劃分的一個(gè)最大分組數(shù)目作為結(jié)束分支的閾值。而且如果數(shù)據(jù)集已處理完了所有屬性，但是類標(biāo)簽依然不是唯一的，我們通常會(huì)選取分類最多的最為該節(jié)點(diǎn)分類。代碼如圖3-7所示：
最后構(gòu)建整個(gè)決策樹的代碼如圖3-8所示：
66行~67行，判斷類別是否都完全相同，相同則返回此類別結(jié)束。
69~70行，判斷是否遍歷完了所有特征，是則選擇屬性分類最多的最后的節(jié)點(diǎn)。
71~72行，選擇最好的劃分子節(jié)點(diǎn)，獲取其標(biāo)簽。
74~79行，將已劃分節(jié)點(diǎn)的類別從數(shù)據(jù)集中劃分出來，再用數(shù)據(jù)集剩下的子集劃分子樹。
最后導(dǎo)入數(shù)據(jù)集，得出結(jié)果，代碼如圖3-9所示：
結(jié)果樹狀圖如圖3-10所示：
四、總結(jié)
本章主要介紹了ID3、C4.5、CART決策樹算法計(jì)算信息的增益、信息增益率、基尼不純度等方法來度量數(shù)據(jù)集的無序程度，簡單來說就是從一個(gè)數(shù)據(jù)集中隨機(jī)選取子項(xiàng)，度量其被錯(cuò)誤分類到其他分組里的概率。通過這些決策樹算法我們能夠根據(jù)實(shí)際情況正確的劃分?jǐn)?shù)據(jù)集，但是為了避免過擬合問題，又有了前剪枝和后剪枝。對非離散的數(shù)據(jù)集和缺失的數(shù)據(jù)集又有合理的解決方案。
決策樹優(yōu)點(diǎn)：
決策樹易于理解和實(shí)現(xiàn)，它能夠直接體現(xiàn)數(shù)據(jù)的特點(diǎn)，而不需要使用者了解更多的背景知識
數(shù)據(jù)的準(zhǔn)備可以很簡單或者是不必要的，而且能夠同時(shí)處理數(shù)據(jù)型和常規(guī)型屬性，在相對短的時(shí)間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果。
易于通過靜態(tài)測試來對模型進(jìn)行評測，可以測定模型可信度；如果給定一個(gè)觀察的模型，那么根據(jù)所產(chǎn)生的決策樹很容易推出相應(yīng)的邏輯表達(dá)式
決策樹缺點(diǎn)：
對連續(xù)性的字段比較難預(yù)測。
對有時(shí)間順序的數(shù)據(jù)，需要很多預(yù)處理的工作。
當(dāng)類別太多時(shí)，錯(cuò)誤可能就會(huì)增加的比較快。
一般的算法分類的時(shí)候，只是根據(jù)一個(gè)字段來分類。
