一、介紹
決策樹（Decision Tree）是一個(gè)樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）俐银，其中每個(gè)非葉節(jié)點(diǎn)表示一個(gè)屬性上的測(cè)試尿背，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉節(jié)點(diǎn)代表一種類別捶惜。機(jī)器學(xué)習(xí)中田藐，決策樹是一個(gè)預(yù)測(cè)模型；他代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(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)行測(cè)試微峰，按照“屬于此子集”和“不屬于此子集”分成兩個(gè)分支舷丹。
3、屬性是連續(xù)值蜓肆。此時(shí)確定一個(gè)值作為分裂點(diǎn)split_point颜凯，按照>split_point和<=split_point生成兩個(gè)分支谋币。
決策樹的屬性分裂選擇是”貪心“算法，也就是沒有回溯的症概。
二蕾额、原理
2.1 信息熵
1948年，香農(nóng)提出了“信息熵”的概念彼城，才解決了對(duì)信息的量化度量問題诅蝶。信息熵這個(gè)詞是C．E．香農(nóng)從熱力學(xué)中借用過來的。熱力學(xué)中的熱熵是表示分子狀態(tài)混亂程度的物理量募壕。香農(nóng)用信息熵的概念來描述信源的不確定度调炬。
由于信息的冗余性，冗余大小與信息中每個(gè)符號(hào)（數(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ù)對(duì)數(shù)任内。信息熵是跟所有可能性有關(guān)系的。每個(gè)可能事件的發(fā)生都有個(gè)概率融柬。信息熵就是平均而言發(fā)生一個(gè)事件我們得到的信息量大兴类隆（也就是說信息熵代表某元組標(biāo)號(hào)所需的平均信息量）。所以數(shù)學(xué)上粒氧，信息熵其實(shí)是信息量的期望越除。
信息熵?cái)?shù)學(xué)表達(dá)式，如圖2-1所示：
Ent（D）的值越小外盯，則D的純度越高
信息增益： 假定離散屬性a有V個(gè)可能的取值{a1,a2,a3,...,av}摘盆，若用a來對(duì)樣本集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)行劃分。
從信息論知識(shí)中我們知道，期望信息越小氯析，信息增益越大亏较，從而純度越高⊙诨海“純”就是盡量讓一個(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è)子集镇眷，接下來要對(duì)每一個(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í)際上慌随，信息增益對(duì)可取數(shù)目較多的屬性有所偏好芬沉，所以為了減少這種影響，提出用增益率來選擇最優(yōu)劃分阁猜，也就是C4.5決策樹算法丸逸。
增益率定義，如圖2-9所示：
可以從式中看出數(shù)目越多（V越大）剃袍，IV（a）會(huì)越大黄刚，Gain_ratio越小，所以增益率對(duì)可取數(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所示：
于是我們?cè)诤蜻x屬性集合中選擇基尼指數(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í)間開銷和測(cè)試時(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ù)屬性相對(duì)于離散屬性可取數(shù)目不是有限的腥例，所以不能直接根據(jù)連續(xù)屬性可選值進(jìn)行劃分。
最簡(jiǎ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~編號(hào)有{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)建流程
- 遍歷并評(píng)估每個(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ù)測(cè)隱形眼鏡類型
參考《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》第三章Logistic回歸樣例：使用決策樹預(yù)測(cè)隱形眼鏡類型
預(yù)測(cè)隱形眼鏡訓(xùn)練集樣本如圖3-1所示：
根據(jù)特征劃分?jǐn)?shù)據(jù)集，這樣可以依次計(jì)算出各屬性的信息增益宜鸯，以此對(duì)比選擇最好的劃分節(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ù)集的無序程度疆栏，簡(jiǎn)單來說就是從一個(gè)數(shù)據(jù)集中隨機(jī)選取子項(xiàng)，度量其被錯(cuò)誤分類到其他分組里的概率惫谤。通過這些決策樹算法我們能夠根據(jù)實(shí)際情況正確的劃分?jǐn)?shù)據(jù)集壁顶，但是為了避免過擬合問題，又有了前剪枝和后剪枝溜歪。對(duì)非離散的數(shù)據(jù)集和缺失的數(shù)據(jù)集又有合理的解決方案若专。
決策樹優(yōu)點(diǎn)：
決策樹易于理解和實(shí)現(xiàn)，它能夠直接體現(xiàn)數(shù)據(jù)的特點(diǎn)蝴猪，而不需要使用者了解更多的背景知識(shí)
數(shù)據(jù)的準(zhǔn)備可以很簡(jiǎn)單或者是不必要的调衰，而且能夠同時(shí)處理數(shù)據(jù)型和常規(guī)型屬性，在相對(duì)短的時(shí)間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果自阱。
易于通過靜態(tài)測(cè)試來對(duì)模型進(jìn)行評(píng)測(cè)嚎莉，可以測(cè)定模型可信度；如果給定一個(gè)觀察的模型沛豌，那么根據(jù)所產(chǎn)生的決策樹很容易推出相應(yīng)的邏輯表達(dá)式
決策樹缺點(diǎn)：
對(duì)連續(xù)性的字段比較難預(yù)測(cè)趋箩。
對(duì)有時(shí)間順序的數(shù)據(jù)，需要很多預(yù)處理的工作加派。
當(dāng)類別太多時(shí)叫确，錯(cuò)誤可能就會(huì)增加的比較快。
一般的算法分類的時(shí)候芍锦，只是根據(jù)一個(gè)字段來分類竹勉。
