1.什么是決策樹(shù)碰辅？

? ? 決策樹(shù)是監(jiān)督學(xué)習(xí)算法懂昂。是機(jī)器學(xué)習(xí)算法中一種依靠對(duì)條件進(jìn)行判斷來(lái)進(jìn)行分類(針對(duì)離散數(shù)據(jù)生成分類樹(shù))和回歸(針對(duì)連續(xù)數(shù)據(jù)生成回歸樹(shù))的算法。是直觀運(yùn)用概率分析的一種圖解法没宾。在機(jī)器學(xué)習(xí)中凌彬，決策樹(shù)是一個(gè)預(yù)測(cè)模型沸柔，他代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。

? ? 樹(shù)中每個(gè)節(jié)點(diǎn)表示某個(gè)對(duì)象铲敛，而每個(gè)分叉路徑則代表某個(gè)可能的屬性值褐澎，而每個(gè)葉節(jié)點(diǎn)則對(duì)應(yīng)從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)所經(jīng)歷的路徑所表示的對(duì)象的值。決策樹(shù)僅有單一輸出伐蒋，若欲有負(fù)數(shù)輸出乱凿，可以建立獨(dú)立的決策樹(shù)以處理不同輸出。數(shù)據(jù)挖掘中決策樹(shù)是一種經(jīng)常要用到的技術(shù)咽弦，可以用于分析數(shù)據(jù)徒蟆，同樣也可以用來(lái)做預(yù)測(cè)。

2.決策樹(shù)的工作原理

? ? 決策樹(shù)的學(xué)習(xí)本質(zhì)上就是從訓(xùn)練數(shù)據(jù)集中歸納出一組分類規(guī)則型型，使它與訓(xùn)練數(shù)據(jù)矛盾較小的同時(shí)具有較強(qiáng)的泛化能力段审。從另一個(gè)角度看，學(xué)習(xí)也是基于訓(xùn)練數(shù)據(jù)集估計(jì)條件概率模型闹蒜。在面對(duì)多個(gè)屬性的數(shù)據(jù)時(shí)寺枉，決策樹(shù)的做法是每次選擇一個(gè)屬性進(jìn)行判斷，如果不能得出結(jié)論绷落，繼續(xù)選擇其他屬性進(jìn)行判斷姥闪，直到能夠"肯定地"判斷出結(jié)果或者是上述屬性都已經(jīng)使用完畢。

2.1如何構(gòu)建決策樹(shù)

? ? 那么問(wèn)題來(lái)了砌烁，如何構(gòu)建一棵決策樹(shù)呢?決策樹(shù)的構(gòu)建是數(shù)據(jù)逐步分裂的過(guò)程筐喳，構(gòu)建的步驟如下：

步驟1：將所有的數(shù)據(jù)看成是一個(gè)節(jié)點(diǎn)，進(jìn)入步驟2函喉；

步驟2：從所有的數(shù)據(jù)特征中挑選一個(gè)數(shù)據(jù)特征對(duì)節(jié)點(diǎn)進(jìn)行分割避归，進(jìn)入步驟3；

步驟3：生成若干孩子節(jié)點(diǎn)管呵，對(duì)每一個(gè)孩子節(jié)點(diǎn)進(jìn)行判斷梳毙，如果滿足停止分裂的條件，進(jìn)入步驟4捐下；否則账锹，進(jìn)入步驟2；

步驟4：設(shè)置該節(jié)點(diǎn)是子節(jié)點(diǎn)坷襟，其輸出的結(jié)果為該節(jié)點(diǎn)數(shù)量占比最大的類別奸柬。

從上述步驟可以看出，決策生成過(guò)程中有三個(gè)重要的問(wèn)題：

如何選擇分裂的特征

數(shù)據(jù)如何分割

什么時(shí)候停止分割

2.2決策樹(shù)的特征選擇算法

? ? 決策樹(shù)學(xué)習(xí)的關(guān)鍵在于如何選擇最優(yōu)的劃分屬性啤握，所謂最優(yōu)的劃分屬性鸟缕，對(duì)于二元分類而言，就是盡量使劃分的樣本屬于同一類別，即“純度”最高的屬性懂从。那么如何來(lái)度量特征(features)的純度授段，這時(shí)候就要用到“信息熵”和“信息增益”，“信息增益率”以及”基尼系數(shù)“等概念番甩。

信息增益的理解：

? ? 對(duì)于待劃分的數(shù)據(jù)集D侵贵，其entroy(前)是一定的，但是劃分之后的熵entroy(后)是不定的缘薛，entroy(后)越小使用此特征劃分得到的子集的不確定性越小(也就是純度越高)窍育，因此entroy(前)-entroy(后)差異越大，說(shuō)明使用當(dāng)前特征劃分?jǐn)?shù)據(jù)集D的話宴胧，其純度上升的更快漱抓。而我們?cè)跇?gòu)建最優(yōu)的決策樹(shù)的時(shí)候總希望能夠快速到達(dá)純度更高的集合，這一點(diǎn)可以參考優(yōu)化算法中的梯度下降算法恕齐，每一步沿著負(fù)梯度方法最小化損失函數(shù)的原因就是負(fù)梯度方向是函數(shù)值減小最快的方向乞娄。同理：在決策樹(shù)構(gòu)建的過(guò)程中我們總希望集合往最快到達(dá)純度更高的子集合方向發(fā)展，因此我們總是選擇使得信息增益最大的特征來(lái)劃分當(dāng)前數(shù)據(jù)集D显歧。

缺點(diǎn)：信息增益偏向取值較多的特征仪或。

原因：當(dāng)特征的取值較多時(shí)，根據(jù)此特征劃分更容易得到純度更高的子集士骤，一次劃分之后的熵更低范删，由于劃分前的熵是一定的，因此信息增益更大拷肌，因此信息增益比較傾向取值較多的特征到旦。

信息增益率

? ? 信息增益比 = 懲罰系數(shù)*信息增益

信息增益比本質(zhì)：是在信息增益的基礎(chǔ)之上乘上一個(gè)懲罰參數(shù)。特征個(gè)數(shù)較多時(shí)廓块，懲罰參數(shù)較邢峋；特征個(gè)數(shù)較少時(shí)带猴，懲罰參數(shù)較大。

懲罰系數(shù)：數(shù)據(jù)集D以特征A作為隨機(jī)變量的熵的倒數(shù)懈万，即：將特征A取值相同的樣本劃分到同一子集中(之前所說(shuō)數(shù)據(jù)集的熵是依據(jù)類別進(jìn)行劃分的)

缺點(diǎn)：信息增益比偏向取值較少的特征

原因：當(dāng)特征取值較少時(shí)的值較小拴清，因此其倒數(shù)較大，因而信息增益比較大会通，所以偏向取值較少的特征口予。

使用信息增益比：基于以上缺點(diǎn)，并不是直接選擇增益率最大的特征涕侈，而是現(xiàn)在候選特征中找出信息增益高于平均水平的特征沪停，然后在這些特征值再選擇信息增益率最高的特征。

GINI指數(shù)：

? ? 定義：基尼指數(shù)(基尼不純度)：表示在樣本集合中一個(gè)隨機(jī)選擇的樣本被分錯(cuò)的概率。

? ? 注意：Gini指數(shù)越小表示集合中被選中的樣本被分錯(cuò)的概率越小木张，也就是說(shuō)集合的純度越高众辨，反之，集合越不純舷礼。即基尼系數(shù)(基尼不純度)=樣本被選中的概率*樣本被分錯(cuò)的概率鹃彻。

? ? 因而對(duì)于一個(gè)具有多個(gè)取值(超過(guò)2個(gè))的特征，需要計(jì)算以每一個(gè)取值作為劃分點(diǎn)妻献，對(duì)樣本D劃分之后子集的純度Gini(D,Ai)蛛株，(其中AI表示特征A的可能取值)。然后從所以的可能劃分的Gini指數(shù)最小的劃分育拨，這個(gè)劃分的劃分點(diǎn)谨履，便是使用特征A對(duì)于樣本集D進(jìn)行劃分的最佳劃分點(diǎn)。

C4.5

? ? C4.5算法是用于生成決策樹(shù)的一種經(jīng)典算法熬丧，是ID3算法的一種延伸和優(yōu)化屉符。C4.5算法對(duì)ID3算法主要做了以下幾點(diǎn)改進(jìn)。

1）通過(guò)信息增益率選擇分裂屬性锹引，克服了ID3算法中通過(guò)信息增益傾向于選擇擁有多個(gè)屬性值的屬性作為分裂熟悉的不足矗钟。

2）能夠處理離散型和連續(xù)型的屬性類型，即將連續(xù)型的屬性進(jìn)行離散化處理嫌变。

3）構(gòu)造決策樹(shù)之后進(jìn)行剪枝操作吨艇；

4）能夠處理具有缺失屬性值的訓(xùn)練數(shù)據(jù)。

CART

? ? CART樹(shù)里面對(duì)C4.5中存在的問(wèn)題進(jìn)行了改進(jìn)腾啥。CART假設(shè)決策樹(shù)是二叉樹(shù)东涡，并且可以分類也可以回歸，而且用基尼指數(shù)代替了熵模型進(jìn)行特征選擇倘待，也提供了優(yōu)化的剪枝策略高氮。

回歸樹(shù)：劃分的準(zhǔn)則是平方誤差最小化辽话。

分類樹(shù)：劃分的準(zhǔn)則是基尼指數(shù)最小化。

3.決策樹(shù)何時(shí)停止分裂

? ? 決策樹(shù)不可能無(wú)限制地生長(zhǎng)，總有停止分裂的時(shí)候套耕，最極端的情況是當(dāng)節(jié)點(diǎn)分裂到只剩下一個(gè)數(shù)據(jù)點(diǎn)時(shí)總動(dòng)結(jié)束分裂，但這種情況下樹(shù)過(guò)于復(fù)雜咕别，而且預(yù)測(cè)的精度不高收叶。一般情況下為了降低決策樹(shù)度復(fù)雜度和提高預(yù)測(cè)的精度，會(huì)適當(dāng)提前終止節(jié)點(diǎn)的分裂菇夸。

????以下是決策樹(shù)節(jié)點(diǎn)停止分裂的一般性條件：

1）最小節(jié)點(diǎn)數(shù)

? ? 當(dāng)節(jié)點(diǎn)的數(shù)據(jù)量小于一個(gè)指定的數(shù)量時(shí)琼富，不繼續(xù)分裂。兩個(gè)原因：一是數(shù)據(jù)量較少時(shí)庄新，再做分裂容易強(qiáng)化噪聲數(shù)據(jù)的作用鞠眉；二是降低樹(shù)生長(zhǎng)的復(fù)雜性薯鼠。提前結(jié)束分裂一定程度上有利于降低過(guò)擬合的影響。

2）熵或者基尼值小于閾值

? ? 由上述可知械蹋，熵或基尼值的大小表示數(shù)據(jù)的復(fù)雜程度出皇，當(dāng)熵或者基尼值過(guò)小時(shí)，表示數(shù)據(jù)的初度比較大朝蜘，如果熵或者基尼值小于一定程度數(shù)恶迈，節(jié)點(diǎn)停止分裂。

3）決策樹(shù)的深度達(dá)到指定的條件

? ? 節(jié)點(diǎn)的深度可以理解為節(jié)點(diǎn)與決策樹(shù)跟節(jié)點(diǎn)的距離谱醇，如果根節(jié)點(diǎn)的子節(jié)點(diǎn)的深度為1暇仲，因?yàn)檫@些節(jié)點(diǎn)與根節(jié)點(diǎn)的距離為1，子節(jié)點(diǎn)的深度比父節(jié)點(diǎn)的深度大1副渴。決策樹(shù)的深度是所有葉子節(jié)點(diǎn)的最大深度奈附，當(dāng)深度到達(dá)指定的上限大小時(shí)，停止分裂煮剧。

4）所有特征已經(jīng)使用完畢斥滤，不能繼續(xù)進(jìn)行分裂

? ? 被動(dòng)式停止分裂的條件，當(dāng)已經(jīng)沒(méi)有可分的屬性時(shí)勉盅，直接將當(dāng)前節(jié)點(diǎn)設(shè)置為葉子節(jié)點(diǎn)佑颇。

4.決策樹(shù)的優(yōu)化

? ? 決策樹(shù)生成之后，我們就可以用來(lái)對(duì)分類未知的樣本進(jìn)行預(yù)測(cè)草娜，這時(shí)決策樹(shù)的泛化性能就顯得很重要了挑胸。一棵生成之后不加任何操作的決策樹(shù)往往不是泛化性能非常好的，常用的解決辦法是剪枝宰闰。決策樹(shù)的剪枝分為兩種茬贵，一種是預(yù)剪枝，另一種是后剪枝移袍，下面分別來(lái)介紹解藻。

預(yù)剪枝

? ? 預(yù)剪枝就是在完全正確分類訓(xùn)練集之前，較早地停止樹(shù)的生長(zhǎng)葡盗。具體在什么時(shí)候停止決策樹(shù)的生長(zhǎng)有很多種不同的方法：

? ? ? ? 1）一種最為簡(jiǎn)單的方法就是在決策樹(shù)到達(dá)一定高度的情況下就停止樹(shù)的生長(zhǎng)螟左。

? ? ? ? 2）到達(dá)此結(jié)點(diǎn)的實(shí)例個(gè)數(shù)小于某一個(gè)閾值也可停止樹(shù)的生長(zhǎng)。

? ? ? ? 3）到達(dá)此結(jié)點(diǎn)的實(shí)例個(gè)數(shù)小于某一個(gè)閾值也可停止樹(shù)的生長(zhǎng)戳粒。

? ? ? ? 4）還有一種更為普遍的做法是計(jì)算每次擴(kuò)張對(duì)系統(tǒng)性能的增益路狮，如果這個(gè)增益值小于某個(gè)閾值則不進(jìn)行擴(kuò)展。

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

? ? 優(yōu)點(diǎn)：由于預(yù)剪枝不必生成整顆決策樹(shù)蔚约，且算法相對(duì)簡(jiǎn)單，效率很高涂籽，適合解決大規(guī)模問(wèn)題苹祟。但是盡管這一方法看起來(lái)很直接，但是怎樣精確地估計(jì)何時(shí)停止樹(shù)的增長(zhǎng)是相對(duì)困難的。

? ? 缺點(diǎn)：預(yù)剪枝有一個(gè)缺點(diǎn)树枫，即視野效果問(wèn)題直焙。也就是說(shuō)在相同的標(biāo)準(zhǔn)下，也許當(dāng)前的擴(kuò)展會(huì)造成過(guò)度擬合訓(xùn)練數(shù)據(jù)砂轻，但是更進(jìn)一步的擴(kuò)展能夠滿足要求奔誓，也有可能準(zhǔn)確地?cái)M合訓(xùn)練數(shù)據(jù)。這將使得算法過(guò)早地停止決策樹(shù)的構(gòu)造搔涝。

后剪枝

后剪枝的通常做法是極小化決策樹(shù)整體的損失函數(shù)厨喂。

4.處理缺失數(shù)據(jù)

決策樹(shù)模型還有一個(gè)很大的優(yōu)勢(shì)，就是可以容忍缺失數(shù)據(jù)庄呈。如果決策樹(shù)中某個(gè)條件缺失蜕煌，可以按一定的權(quán)重分配繼續(xù)往以后的分支走，最終的結(jié)果可能有多個(gè)诬留，每個(gè)結(jié)果有一定的概率斜纪，即：

? ? 最終結(jié)果=某個(gè)分支的結(jié)果*該分支的權(quán)重(該分支下的結(jié)果數(shù)/總結(jié)果數(shù))

5.sklearn中決策樹(shù)的使用

? ??5.1決策樹(shù)的參數(shù)：

1）criterion{''gini","entropy"},default='gini'確定決策樹(shù)是基于基尼指數(shù)還是信息熵。

2）max_depth：樹(shù)的層數(shù)文兑，限制樹(shù)的最大深度盒刚，超過(guò)設(shè)定深度的樹(shù)枝全部剪掉，這是用的最廣泛的剪枝參數(shù)绿贞，在高維度低樣本量時(shí)非常有效因块。決策樹(shù)多生長(zhǎng)一層，對(duì)樣本量的需求會(huì)增長(zhǎng)一倍樟蠕，所以限制樹(shù)深度能夠有效地限制過(guò)擬合贮聂。在集成算法中也非常實(shí)用。實(shí)際使用時(shí)寨辩，建議從=3開(kāi)始嘗試吓懈，看看擬合的效果再?zèng)Q定是否增加設(shè)定深度。實(shí)際層數(shù)為max_depth+1考慮靡狞。

3）min_impurity_decrease：限制決策樹(shù)的生長(zhǎng)耻警，如果節(jié)點(diǎn)的不純度(Gini,Gain)小于這個(gè)閾值，就不在生成子節(jié)點(diǎn)甸怕。

4）min_impurity_split：不純度必須大于這個(gè)值甘穿，不然不分裂。

5）class_weight：可以用來(lái)定義某一個(gè)類別的權(quán)重梢杭，讓這一個(gè)類在計(jì)算的時(shí)候温兼，信息增益變得稍微大一些。

6）random_state：隨機(jī)數(shù)種子武契，固定種子之后募判，訓(xùn)練的模型是一樣的荡含。

7）splitter：用來(lái)控制決策樹(shù)中的隨機(jī)選項(xiàng)的，有兩種輸入值届垫，輸入”best"释液，決策樹(shù)在分枝時(shí)雖然隨機(jī)，但是還是會(huì)優(yōu)先選擇更重要的特征進(jìn)行分枝（重要性可以通過(guò)屬性feature_importances_查看）装处，輸入“random"误债，決策樹(shù)在分枝時(shí)會(huì)更加隨機(jī)，樹(shù)會(huì)因?yàn)楹懈嗟牟槐匾畔⒍罡笸ǎ⒁蜻@些不必要信息而降低對(duì)訓(xùn)練集的擬合寝蹈。這也是防止過(guò)擬合的一種方式。當(dāng)你預(yù)測(cè)到你的模型會(huì)過(guò)擬合判族，用這兩個(gè)參數(shù)來(lái)幫助你降低樹(shù)建成之后過(guò)擬合的可能性躺盛。當(dāng)然，樹(shù)一旦建成形帮，我們依然是使用剪枝參數(shù)來(lái)防止過(guò)擬合槽惫。所以要想泛化好，最好splitter設(shè)置成random辩撑。

和剪枝相關(guān)的參數(shù)：

1）min_samples_leaf：一個(gè)節(jié)點(diǎn)在分支后的每個(gè)子節(jié)點(diǎn)都必須包含至少min_samples_leaf個(gè)訓(xùn)練樣本界斜，否則分枝就不會(huì)發(fā)生，或者合冀，分枝會(huì)朝著滿足每個(gè)子節(jié)點(diǎn)都包含min_samples_leaf個(gè)樣本的方向去發(fā)生各薇。

2）一般搭配max_depth使用，在回歸樹(shù)中有神奇的效果君躺，可以讓模型變得更加平滑峭判。這個(gè)參數(shù)的數(shù)量設(shè)置得太小會(huì)引起過(guò)擬合，設(shè)置得太大就會(huì)阻止模型學(xué)習(xí)數(shù)據(jù)棕叫。一般來(lái)說(shuō)林螃，建議從=5開(kāi)始使用。如果葉節(jié)點(diǎn)中含有的樣本量變化很大俺泣，建議輸入浮點(diǎn)數(shù)作為樣本量的百分比來(lái)使用疗认。同時(shí)，這個(gè)參數(shù)可以保證每個(gè)葉子的最小尺寸伏钠，可以在回歸問(wèn)題中避免低方差横漏，過(guò)擬合的葉子節(jié)點(diǎn)出現(xiàn)。對(duì)于類別不多的分類問(wèn)題熟掂，=1通常就是最佳選擇缎浇。

3）min_weight_fraction_leaf：有了權(quán)重之后，樣本量就不再是單純地記錄數(shù)目赴肚，而是受輸入的權(quán)重影響了华畏，因此這時(shí)候剪枝鹏秋，就需要搭配min_ weight_fraction_leaf這個(gè)基于權(quán)重的剪枝參數(shù)來(lái)使用尊蚁。另請(qǐng)注意亡笑，基于權(quán)重的剪枝參數(shù)（例如min_weight_ fraction_leaf）將比不知道樣本權(quán)重的標(biāo)準(zhǔn)（比如min_samples_leaf）更少偏向主導(dǎo)類。如果樣本是加權(quán)的横朋，則使用基于權(quán)重的預(yù)修剪標(biāo)準(zhǔn)來(lái)更容易優(yōu)化樹(shù)結(jié)構(gòu)仑乌，這確保葉節(jié)點(diǎn)至少包含樣本權(quán)重的總和的一小部分。

分類決策樹(shù)score函數(shù)返回的是預(yù)測(cè)的準(zhǔn)確率

回歸樹(shù)的接口score返回的是R2

注意在sklearn中實(shí)現(xiàn)的決策樹(shù)都是二叉樹(shù)琴锭。

????5.2 決策樹(shù)的可視化

????????可以使用graphviz安裝包：pip install graphviz

????feature_name = ["A","B","C"]

????importgraphvizdot_data = tree.export_graphviz(clf ,feature_names= feature_name ,class_names=["1","2","3"] ???????? ???????????????????????????????????????????????????????????????????? ,filled=True,rounded=True,out_file=None)

?????graph = graphviz.Source(dot_data)graph

6.算法的優(yōu)缺點(diǎn)總結(jié)

來(lái)看看決策樹(shù)算法作為一個(gè)大類別的分類回歸算法的優(yōu)缺點(diǎn)晰甚。

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

1）簡(jiǎn)單直觀，生成的決策樹(shù)很直觀决帖。對(duì)于異常點(diǎn)的容錯(cuò)能力好厕九，健壯性高。

2）基本不需要預(yù)處理地回，不需要提前歸一化扁远，處理缺失值。

3）使用決策樹(shù)預(yù)測(cè)的代價(jià)是刻像，m為樣本數(shù)畅买。

4）既可以處理離散值也可以處理連續(xù)值。很多算法只是專注于離散值或者連續(xù)值细睡。

5）可以處理多維度輸出的分類問(wèn)題谷羞。

6）相比于神經(jīng)網(wǎng)絡(luò)之類的黑盒分類模型，決策樹(shù)在邏輯上可以得到很好的解釋溜徙。

????缺點(diǎn)：

1）決策樹(shù)算法非常容易過(guò)擬合湃缎，導(dǎo)致泛化能力不強(qiáng)〈酪迹可以通過(guò)設(shè)置節(jié)點(diǎn)最少樣本數(shù)量和限制決策樹(shù)深度來(lái)改進(jìn)嗓违。

2）決策樹(shù)會(huì)因?yàn)闃颖景l(fā)生一點(diǎn)點(diǎn)的改動(dòng)，就會(huì)導(dǎo)致樹(shù)結(jié)構(gòu)的劇烈改變知残。這個(gè)可以通過(guò)集成學(xué)習(xí)之類的方法解決靠瞎。

3）尋找最優(yōu)的決策樹(shù)是一個(gè)NP難的問(wèn)題，我們一般是通過(guò)啟發(fā)式方法求妹，容易陷入局部最優(yōu)乏盐。可以通過(guò)集成學(xué)習(xí)之類的方法來(lái)改善制恍。

4）有些比較復(fù)雜的關(guān)系父能，決策樹(shù)很難學(xué)習(xí)，比如異或净神。這個(gè)就沒(méi)有辦法了何吝，一般這種關(guān)系可以換神經(jīng)網(wǎng)絡(luò)分類方法來(lái)解決溉委。

5）如果某些特征的樣本比例過(guò)大，生成決策樹(shù)容易偏向于這些特征爱榕。這個(gè)可以通過(guò)調(diào)節(jié)樣本權(quán)重來(lái)改善瓣喊。