運(yùn)行平臺(tái)：?Windows?
Python版本：?Python3.x?
IDE：?pycharm
一、決策樹
決策樹是什么克懊？決策樹(decision tree)是一種基本的分類與回歸方法忱辅。舉個(gè)通俗易懂的例子，如下圖所示的流程圖就是一個(gè)決策樹谭溉，長(zhǎng)方形代表判斷模塊(decision block)耕蝉，橢圓形成代表終止模塊(terminating block)，表示已經(jīng)得出結(jié)論夜只，可以終止運(yùn)行垒在。從判斷模塊引出的左右箭頭稱作為分支(branch)，它可以達(dá)到另一個(gè)判斷模塊或者終止模塊。我們還可以這樣理解场躯，分類決策樹模型是一種描述對(duì)實(shí)例進(jìn)行分類的樹形結(jié)構(gòu)谈为。決策樹由結(jié)點(diǎn)(node)和有向邊(directed edge)組成。結(jié)點(diǎn)有兩種類型：內(nèi)部結(jié)點(diǎn)(internal node)和葉結(jié)點(diǎn)(leaf node)踢关。內(nèi)部結(jié)點(diǎn)表示一個(gè)特征或?qū)傩陨■辏~結(jié)點(diǎn)表示一個(gè)類。如下圖所示的決策樹签舞，長(zhǎng)方形和橢圓形都是結(jié)點(diǎn)秕脓。長(zhǎng)方形的結(jié)點(diǎn)屬于內(nèi)部結(jié)點(diǎn)，橢圓形的結(jié)點(diǎn)屬于葉結(jié)點(diǎn)儒搭，從結(jié)點(diǎn)引出的左右箭頭就是有向邊吠架。而最上面的結(jié)點(diǎn)就是決策樹的根結(jié)點(diǎn)(root node)。這樣搂鲫，結(jié)點(diǎn)說法就與模塊說法對(duì)應(yīng)上了傍药，理解就好。
我們可以把決策樹看成一個(gè)if-then規(guī)則的集合拐辽，將決策樹轉(zhuǎn)換成if-then規(guī)則的過程是這樣的：由決策樹的根結(jié)點(diǎn)(root node)到葉結(jié)點(diǎn)(leaf node)的每一條路徑構(gòu)建一條規(guī)則；路徑上內(nèi)部結(jié)點(diǎn)的特征對(duì)應(yīng)著規(guī)則的條件擦酌，而葉結(jié)點(diǎn)的類對(duì)應(yīng)著規(guī)則的結(jié)論俱诸。決策樹的路徑或其對(duì)應(yīng)的if-then規(guī)則集合具有一個(gè)重要的性質(zhì)：互斥并且完備。這就是說赊舶，每一個(gè)實(shí)例都被一條路徑或一條規(guī)則所覆蓋乙埃，而且只被一條路徑或一條規(guī)則所覆蓋。這里所覆蓋是指實(shí)例的特征與路徑上的特征一致或?qū)嵗凉M足規(guī)則的條件锯岖。
?使用決策樹做預(yù)測(cè)需要以下過程：
收集數(shù)據(jù)：可以使用任何方法介袜。比如想構(gòu)建一個(gè)相親系統(tǒng)，我們可以從媒婆那里出吹，或者通過參訪相親對(duì)象獲取數(shù)據(jù)遇伞。根據(jù)他們考慮的因素和最終的選擇結(jié)果，就可以得到一些供我們利用的數(shù)據(jù)了捶牢。
準(zhǔn)備數(shù)據(jù)：收集完的數(shù)據(jù)鸠珠，我們要進(jìn)行整理，將這些所有收集的信息按照一定規(guī)則整理出來秋麸，并排版渐排，方便我們進(jìn)行后續(xù)處理。
分析數(shù)據(jù)：可以使用任何方法灸蟆，決策樹構(gòu)造完成之后驯耻，我們可以檢查決策樹圖形是否符合預(yù)期。
訓(xùn)練算法：這個(gè)過程也就是構(gòu)造決策樹，同樣也可以說是決策樹學(xué)習(xí)可缚，就是構(gòu)造一個(gè)決策樹的數(shù)據(jù)結(jié)構(gòu)霎迫。
測(cè)試算法：使用經(jīng)驗(yàn)樹計(jì)算錯(cuò)誤率。當(dāng)錯(cuò)誤率達(dá)到了可接收范圍帘靡，這個(gè)決策樹就可以投放使用了知给。
使用算法：此步驟可以使用適用于任何監(jiān)督學(xué)習(xí)算法，而使用決策樹可以更好地理解數(shù)據(jù)的內(nèi)在含義
二描姚、構(gòu)建決策樹
? 使用決策樹做預(yù)測(cè)的每一步驟都很重要涩赢，數(shù)據(jù)收集不到位，將會(huì)導(dǎo)致沒有足夠的特征讓我們構(gòu)建錯(cuò)誤率低的決策樹轩勘。數(shù)據(jù)特征充足筒扒，但是不知道用哪些特征好，將會(huì)導(dǎo)致無法構(gòu)建出分類效果好的決策樹模型赃阀。從算法方面看，決策樹的構(gòu)建是我們的核心內(nèi)容擎颖。
????決策樹要如何構(gòu)建呢榛斯？通常，這一過程可以概括為3個(gè)步驟：特征選擇搂捧、決策樹的生成和決策樹的修剪
特征選擇
特征選擇在于選取對(duì)訓(xùn)練數(shù)據(jù)具有分類能力的特征驮俗。這樣可以提高決策樹學(xué)習(xí)的效率，如果利用一個(gè)特征進(jìn)行分類的結(jié)果與隨機(jī)分類的結(jié)果沒有很大差別允跑，則稱這個(gè)特征是沒有分類能力的王凑。經(jīng)驗(yàn)上扔掉這樣的特征對(duì)決策樹學(xué)習(xí)的精度影響不大。通常特征選擇的標(biāo)準(zhǔn)是信息增益(information gain)或信息增益比聋丝，為了簡(jiǎn)單索烹，本文章使用信息增益作為選擇特征的標(biāo)準(zhǔn)。那么弱睦，什么是信息增益百姓？在講解信息增益之前，讓我們看一組實(shí)例况木，貸款申請(qǐng)樣本數(shù)據(jù)表垒拢。
希望通過所給的訓(xùn)練數(shù)據(jù)學(xué)習(xí)一個(gè)貸款申請(qǐng)的決策樹，用以對(duì)未來的貸款申請(qǐng)進(jìn)行分類火惊，即當(dāng)新的客戶提出貸款申請(qǐng)時(shí)求类，根據(jù)申請(qǐng)人的特征利用決策樹決定是否批準(zhǔn)貸款申請(qǐng)。
特征選擇就是決定用哪個(gè)特征來劃分特征空間屹耐。比如尸疆，我們通過上述數(shù)據(jù)表得到兩個(gè)可能的決策樹，分別由兩個(gè)不同特征的根結(jié)點(diǎn)構(gòu)成。
?圖(a)所示的根結(jié)點(diǎn)的特征是年齡仓技，有3個(gè)取值鸵贬，對(duì)應(yīng)于不同的取值有不同的子結(jié)點(diǎn)。圖(b)所示的根節(jié)點(diǎn)的特征是工作脖捻，有2個(gè)取值阔逼，對(duì)應(yīng)于不同的取值有不同的子結(jié)點(diǎn)。兩個(gè)決策樹都可以從此延續(xù)下去地沮。問題是：究竟選擇哪個(gè)特征更好些嗜浮？這就要求確定選擇特征的準(zhǔn)則。直觀上摩疑，如果一個(gè)特征具有更好的分類能力危融，或者說，按照這一特征將訓(xùn)練數(shù)據(jù)集分割成子集雷袋，使得各個(gè)子集在當(dāng)前條件下有最好的分類吉殃，那么就更應(yīng)該選擇這個(gè)特征。信息增益就能夠很好地表示這一直觀的準(zhǔn)則楷怒。
什么是信息增益呢蛋勺？在劃分?jǐn)?shù)據(jù)集之前之后信息發(fā)生的變化成為信息增益，知道如何計(jì)算信息增益鸠删，我們就可以計(jì)算每個(gè)特征值劃分?jǐn)?shù)據(jù)集獲得的信息增益抱完，獲得信息增益最高的特征就是最好的選擇。
香農(nóng)熵
在可以評(píng)測(cè)哪個(gè)數(shù)據(jù)劃分方式是最好的數(shù)據(jù)劃分之前刃泡，我們必須學(xué)習(xí)如何計(jì)算信息增益巧娱。集合信息的度量方式成為香農(nóng)熵或者簡(jiǎn)稱為熵(entropy)，這個(gè)名字來源于信息論之父克勞德·香農(nóng)烘贴。
如果看不明白什么是信息增益和熵禁添，請(qǐng)不要著急，因?yàn)樗麄冏哉Q生的那一天起桨踪，就注定會(huì)令世人十分費(fèi)解上荡。克勞德·香農(nóng)寫完信息論之后馒闷，約翰·馮·諾依曼建議使用”熵”這個(gè)術(shù)語酪捡，因?yàn)榇蠹叶疾恢浪鞘裁匆馑肌?/p>
熵定義為信息的期望值。在信息論與概率統(tǒng)計(jì)中，熵是表示隨機(jī)變量不確定性的度量。如果待分類的事務(wù)可能劃分在多個(gè)分類之中引润，則符號(hào)xi的信息定義為
其中p(xi)是選擇該分類的概率济舆。有人可能會(huì)問，信息為啥這樣定義翱贝俊宋舷？答曰：前輩得出的結(jié)論鳖链。這就跟1+1等于2一樣呢袱，記住并且會(huì)用即可官扣。上述式中的對(duì)數(shù)以2為底，也可以e為底(自然對(duì)數(shù))羞福。
通過上式惕蹄，我們可以得到所有類別的信息。為了計(jì)算熵治专，我們需要計(jì)算所有類別所有可能值包含的信息期望值(數(shù)學(xué)期望)卖陵，通過下面的公式得到：
其中n是分類的數(shù)目。熵越大张峰，隨機(jī)變量的不確定性就越大泪蔫。
當(dāng)熵中的概率由數(shù)據(jù)估計(jì)(特別是最大似然估計(jì))得到時(shí)，所對(duì)應(yīng)的熵稱為經(jīng)驗(yàn)熵(empirical entropy)喘批。什么叫由數(shù)據(jù)估計(jì)撩荣？比如有10個(gè)數(shù)據(jù)，一共有兩個(gè)類別饶深，A類和B類餐曹。其中有7個(gè)數(shù)據(jù)屬于A類，則該A類的概率即為十分之七粥喜。其中有3個(gè)數(shù)據(jù)屬于B類凸主，則該B類的概率即為十分之三橘券。淺顯的解釋就是额湘，這概率是我們根據(jù)數(shù)據(jù)數(shù)出來的。我們定義貸款申請(qǐng)樣本數(shù)據(jù)表中的數(shù)據(jù)為訓(xùn)練數(shù)據(jù)集D旁舰，則訓(xùn)練數(shù)據(jù)集D的經(jīng)驗(yàn)熵為H(D)锋华，|D|表示其樣本容量，及樣本個(gè)數(shù)箭窜。設(shè)有K個(gè)類Ck毯焕，k = 1,2,3,···,K，|Ck|為屬于類Ck的樣本個(gè)數(shù)磺樱，這經(jīng)驗(yàn)熵公式可以寫為：
根據(jù)此公式計(jì)算經(jīng)驗(yàn)熵H(D)纳猫，分析貸款申請(qǐng)樣本數(shù)據(jù)表中的數(shù)據(jù)。最終分類結(jié)果只有兩類竹捉，即放貸和不放貸芜辕。根據(jù)表中的數(shù)據(jù)統(tǒng)計(jì)可知，在15個(gè)數(shù)據(jù)中块差，9個(gè)數(shù)據(jù)的結(jié)果為放貸侵续，6個(gè)數(shù)據(jù)的結(jié)果為不放貸倔丈。所以數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)為：
編寫程序計(jì)算經(jīng)驗(yàn)熵
在編寫代碼之前，我們先對(duì)數(shù)據(jù)集進(jìn)行屬性標(biāo)注状蜗。
年齡：0代表青年需五，1代表中年，2代表老年轧坎；
有工作：0代表否宏邮，1代表是；
有自己的房子：0代表否眶根，1代表是蜀铲；
信貸情況：0代表一般，1代表好属百，2代表非常好记劝；
類別(是否給貸款)：no代表否，yes代表是族扰。
確定這些之后厌丑，我們就可以創(chuàng)建數(shù)據(jù)集，并計(jì)算經(jīng)驗(yàn)熵了渔呵，代碼編寫如下：
link:https://github.com/songshijun007/Decision-Tree/blob/master/calcShannonEntcalcShannonEnt.py
信息增益
在上面怒竿，我們已經(jīng)說過，如何選擇特征扩氢，需要看信息增益耕驰。也就是說，信息增益是相對(duì)于特征而言的录豺，信息增益越大朦肘，特征對(duì)最終的分類結(jié)果影響也就越大，我們就應(yīng)該選擇對(duì)最終分類結(jié)果影響最大的那個(gè)特征作為我們的分類特征双饥。
在講解信息增益定義之前媒抠，我們還需要明確一個(gè)概念，條件熵咏花。
熵我們知道是什么趴生，條件熵又是個(gè)什么鬼？條件熵H(Y|X)表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性昏翰，隨機(jī)變量X給定的條件下隨機(jī)變量Y的條件熵(conditional entropy) H(Y|X)苍匆，定義X給定條件下Y的條件概率分布的熵對(duì)X的數(shù)學(xué)期望：
其中，
同理棚菊，當(dāng)條件熵中的概率由數(shù)據(jù)估計(jì)(特別是極大似然估計(jì))得到時(shí)浸踩，所對(duì)應(yīng)的條件熵成為條件經(jīng)驗(yàn)熵(empirical conditional entropy)。
明確了條件熵和經(jīng)驗(yàn)條件熵的概念窍株。接下來民轴，讓我們說說信息增益攻柠。前面也提到了，信息增益是相對(duì)于特征而言的后裸。所以瑰钮，特征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)之差微驶，即
? 一般地浪谴，熵H(D)與條件熵H(D|A)之差成為互信息(mutual information)。決策樹學(xué)習(xí)中的信息增益等價(jià)于訓(xùn)練數(shù)據(jù)集中類與特征的互信息因苹。
設(shè)特征A有n個(gè)不同的取值{a1,a2,···,an}苟耻，根據(jù)特征A的取值將D劃分為n個(gè)子集D1,D2，···,Dn扶檐，|Di|為Di的樣本個(gè)數(shù)凶杖。記子集Di中屬于Ck的樣本的集合為Dik，即Dik = Di ∩ Ck款筑，|Dik|為Dik的樣本個(gè)數(shù)智蝠。于是經(jīng)驗(yàn)條件熵的公式可以些為：
以貸款申請(qǐng)樣本數(shù)據(jù)表為例進(jìn)行說明∧问幔看下年齡這一列的數(shù)據(jù)杈湾，也就是特征A1，一共有三個(gè)類別攘须，分別是：青年漆撞、中年和老年。我們只看年齡是青年的數(shù)據(jù)于宙，年齡是青年的數(shù)據(jù)一共有5個(gè)浮驳，所以年齡是青年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率是十五分之五，也就是三分之一限煞。同理抹恳，年齡是中年和老年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率也都是三分之一≡蹦現(xiàn)在我們只看年齡是青年的數(shù)據(jù)的最終得到貸款的概率為五分之二署驻，因?yàn)樵谖鍌€(gè)數(shù)據(jù)中，只有兩個(gè)數(shù)據(jù)顯示拿到了最終的貸款健霹，同理旺上，年齡是中年和老年的數(shù)據(jù)最終得到貸款的概率分別為五分之三、五分之四糖埋。所以計(jì)算年齡的信息增益宣吱，過程如下：
?最后杭攻，比較特征的信息增益，由于特征A3(有自己的房子)的信息增益值最大疤坝，所以選擇A3作為最優(yōu)特征兆解。
編寫程序計(jì)算信息增益
link:
決策樹生成和修剪
已經(jīng)學(xué)習(xí)了從數(shù)據(jù)集構(gòu)造決策樹算法所需要的子功能模塊，包括經(jīng)驗(yàn)熵的計(jì)算和最優(yōu)特征的選擇跑揉，其工作原理如下：得到原始數(shù)據(jù)集锅睛，然后基于最好的屬性值劃分?jǐn)?shù)據(jù)集，由于特征值可能多于兩個(gè)历谍，因此可能存在大于兩個(gè)分支的數(shù)據(jù)集劃分现拒。第一次劃分之后，數(shù)據(jù)集被向下傳遞到樹的分支的下一個(gè)結(jié)點(diǎn)望侈。在這個(gè)結(jié)點(diǎn)上印蔬，我們可以再次劃分?jǐn)?shù)據(jù)。因此我們可以采用遞歸的原則處理數(shù)據(jù)集脱衙。
構(gòu)建決策樹的算法有很多扛点，比如C4.5、ID3和CART岂丘，這些算法在運(yùn)行時(shí)并不總是在每次劃分?jǐn)?shù)據(jù)分組時(shí)都會(huì)消耗特征陵究。由于特征數(shù)目并不是每次劃分?jǐn)?shù)據(jù)分組時(shí)都減少，因此這些算法在實(shí)際使用時(shí)可能引起一定的問題奥帘。目前我們并不需要考慮這個(gè)問題铜邮，只需要在算法開始運(yùn)行前計(jì)算列的數(shù)目，查看算法是否使用了所有屬性即可寨蹋。
決策樹生成算法遞歸地產(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)化秸讹。
ID3算法構(gòu)建決策樹
ID3算法的核心是在決策樹各個(gè)結(jié)點(diǎn)上對(duì)應(yīng)信息增益準(zhǔn)則選擇特征檀咙，遞歸地構(gòu)建決策樹。具體方法是：從根結(jié)點(diǎn)(root node)開始璃诀，對(duì)結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益弧可，選擇信息增益最大的特征作為結(jié)點(diǎn)的特征，由該特征的不同取值建立子節(jié)點(diǎn)劣欢；再對(duì)子結(jié)點(diǎn)遞歸地調(diào)用以上方法棕诵，構(gòu)建決策樹裁良；直到所有特征的信息增益均很小或沒有特征可以選擇為止。最后得到一個(gè)決策樹校套。ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇趴久。
由于特征A3(有自己的房子)的信息增益值最大，所以選擇特征A3作為根結(jié)點(diǎn)的特征搔确。它將訓(xùn)練集D劃分為兩個(gè)子集D1(A3取值為"是")和D2(A3取值為"否")彼棍。由于D1只有同一類的樣本點(diǎn)，所以它成為一個(gè)葉結(jié)點(diǎn)膳算，結(jié)點(diǎn)的類標(biāo)記為“是”座硕。
對(duì)D2則需要從特征A1(年齡)，A2(有工作)和A4(信貸情況)中選擇新的特征涕蜂，計(jì)算各個(gè)特征的信息增益：
g(D2,A1) = H(D2) - H(D2 | A1) = 0.251
g(D2,A2) = H(D2) - H(D2 | A2) = 0.918
g(D2,A3) = H(D2) - H(D2 | A3) = 0.474
????根據(jù)計(jì)算华匾，選擇信息增益最大的特征A2(有工作)作為結(jié)點(diǎn)的特征。由于A2有兩個(gè)可能取值机隙，從這一結(jié)點(diǎn)引出兩個(gè)子結(jié)點(diǎn)：一個(gè)對(duì)應(yīng)”是”(有工作)的子結(jié)點(diǎn)蜘拉，包含3個(gè)樣本，它們屬于同一類有鹿，所以這是一個(gè)葉結(jié)點(diǎn)旭旭，類標(biāo)記為”是”；另一個(gè)是對(duì)應(yīng)”否”(無工作)的子結(jié)點(diǎn)葱跋，包含6個(gè)樣本持寄，它們也屬于同一類，所以這也是一個(gè)葉結(jié)點(diǎn)娱俺，類標(biāo)記為”否”稍味。
????這樣就生成了一個(gè)決策樹，該決策樹只用了兩個(gè)特征(有兩個(gè)內(nèi)部結(jié)點(diǎn))荠卷，生成的決策樹如下圖所示模庐。
這樣我們就使用ID3算法構(gòu)建出來了決策樹，接下來油宜，讓我們看看如何進(jìn)行代實(shí)現(xiàn)掂碱。
編寫代碼構(gòu)建決策樹
我們使用字典存儲(chǔ)決策樹的結(jié)構(gòu)，比如上小節(jié)我們分析出來的決策樹验庙，用字典可以表示為：
{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
創(chuàng)建函數(shù)majorityCnt統(tǒng)計(jì)classList中出現(xiàn)此處最多的元素(類標(biāo)簽)顶吮，創(chuàng)建函數(shù)createTree用來遞歸構(gòu)建決策樹社牲。編寫代碼如下：
