1驳规、決策樹分類原理 　　

決策樹是通過一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過程。它提供一種在什么條件下會(huì)得到什么值的類似規(guī)則的方法授账。決策樹分為分類樹和回歸樹兩種归园，分類樹對(duì)離散變量做決策樹黄虱，回歸樹對(duì)連續(xù)變量做決策樹。

如果不考慮效率等蔓倍，那么樣本所有特征的判斷級(jí)聯(lián)起來終會(huì)將某一個(gè)樣本分到一個(gè)類終止塊上悬钳。實(shí)際上盐捷，樣本所有特征中有一些特征在分類時(shí)起到?jīng)Q定性作用偶翅，決策樹的構(gòu)造過程就是找到這些具有決定性作用的特征，根據(jù)其決定性程度來構(gòu)造一個(gè)倒立的樹--決定性作用最大的那個(gè)特征作為根節(jié)點(diǎn)碉渡，然后遞歸找到各分支下子數(shù)據(jù)集中次大的決定性特征聚谁，直至子數(shù)據(jù)集中所有數(shù)據(jù)都屬于同一類。所以滞诺，構(gòu)造決策樹的過程本質(zhì)上就是根據(jù)數(shù)據(jù)特征將數(shù)據(jù)集分類的遞歸過程形导，我們需要解決的第一個(gè)問題就是，當(dāng)前數(shù)據(jù)集上哪個(gè)特征在劃分?jǐn)?shù)據(jù)分類時(shí)起決定性作用习霹。

2朵耕、決策樹的學(xué)習(xí)過程

一棵決策樹的生成過程主要分為以下3個(gè)部分:

特征選擇：特征選擇是指從訓(xùn)練數(shù)據(jù)中眾多的特征中選擇一個(gè)特征作為當(dāng)前節(jié)點(diǎn)的分裂標(biāo)準(zhǔn)，如何選擇特征有著很多不同量化評(píng)估標(biāo)準(zhǔn)標(biāo)準(zhǔn)淋叶，從而衍生出不同的決策樹算法阎曹。

決策樹生成： 根據(jù)選擇的特征評(píng)估標(biāo)準(zhǔn)，從上至下遞歸地生成子節(jié)點(diǎn)，直到數(shù)據(jù)集不可分則停止決策樹停止生長处嫌。 樹結(jié)構(gòu)來說栅贴，遞歸結(jié)構(gòu)是最容易理解的方式。

剪枝：決策樹容易過擬合熏迹，一般來需要剪枝檐薯，縮小樹結(jié)構(gòu)規(guī)模、緩解過擬合注暗。剪枝技術(shù)有預(yù)剪枝和后剪枝兩種坛缕。

3、基于信息論的三種決策樹算法 　　

劃分?jǐn)?shù)據(jù)集的最大原則是：使無序的數(shù)據(jù)變的有序友存。如果一個(gè)訓(xùn)練數(shù)據(jù)中有20個(gè)特征祷膳，那么選取哪個(gè)做劃分依據(jù)？這就必須采用量化的方法來判斷屡立，量化劃分方法有多重直晨，其中一項(xiàng)就是“信息論度量信息分類”∨蚶基于信息論的決策樹算法有ID3勇皇、CART和C4.5等算法，其中C4.5和CART兩種算法從ID3算法中衍生而來焚刺。

CART和C4.5支持?jǐn)?shù)據(jù)特征為連續(xù)分布時(shí)的處理敛摘，主要通過使用二元切分來處理連續(xù)型變量，即求一個(gè)特定的值-分裂值：特征值大于分裂值就走左子樹乳愉，或者就走右子樹兄淫。這個(gè)分裂值的選取的原則是使得劃分后的子樹中的“混亂程度”降低，具體到C4.5和CART算法則有不同的定義方式蔓姚。

ID3算法由Ross Quinlan發(fā)明捕虽，建立在“奧卡姆剃刀”的基礎(chǔ)上：越是小型的決策樹越優(yōu)于大的決策樹（be simple簡(jiǎn)單理論）。ID3算法中根據(jù)信息論的信息增益評(píng)估和選擇特征坡脐，每次選擇信息增益最大的特征做判斷模塊泄私。ID3算法可用于劃分標(biāo)稱型數(shù)據(jù)集，沒有剪枝的過程备闲，為了去除過度數(shù)據(jù)匹配的問題晌端，可通過裁剪合并相鄰的無法產(chǎn)生大量信息增益的葉子節(jié)點(diǎn)（例如設(shè)置信息增益閥值）。使用信息增益的話其實(shí)是有一個(gè)缺點(diǎn)恬砂，那就是它偏向于具有大量值的屬性--就是說在訓(xùn)練集中咧纠，某個(gè)屬性所取的不同值的個(gè)數(shù)越多，那么越有可能拿它來作為分裂屬性泻骤，而這樣做有時(shí)候是沒有意義的漆羔，另外ID3不能處理連續(xù)分布的數(shù)據(jù)特征乳幸，于是就有了C4.5算法。CART算法也支持連續(xù)分布的數(shù)據(jù)特征钧椰。

C4.5是ID3的一個(gè)改進(jìn)算法粹断，繼承了ID3算法的優(yōu)點(diǎn)。C4.5算法用信息增益率來選擇屬性嫡霞，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足在樹構(gòu)造過程中進(jìn)行剪枝瓶埋；能夠完成對(duì)連續(xù)屬性的離散化處理；能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理诊沪。C4.5算法產(chǎn)生的分類規(guī)則易于理解养筒、準(zhǔn)確率較高；但效率低端姚，因樹構(gòu)造過程中晕粪，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序。也是因?yàn)楸仨毝啻螖?shù)據(jù)集掃描渐裸，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集巫湘。

CART算法的全稱是Classification And Regression Tree，采用的是Gini指數(shù)（選Gini指數(shù)最小的特征s）作為分裂標(biāo)準(zhǔn),同時(shí)它也是包含后剪枝操作昏鹃。ID3算法和C4.5算法雖然在對(duì)訓(xùn)練樣本集的學(xué)習(xí)中可以盡可能多地挖掘信息尚氛，但其生成的決策樹分支較大，規(guī)模較大洞渤。為了簡(jiǎn)化決策樹的規(guī)模阅嘶，提高生成決策樹的效率，就出現(xiàn)了根據(jù)GINI系數(shù)來選擇測(cè)試屬性的決策樹算法CART载迄。

4讯柔、決策樹優(yōu)缺點(diǎn)

決策樹算法的優(yōu)點(diǎn)：

（1）便于理解和解釋，樹的結(jié)構(gòu)可以可視化出來

（2）基本不需要預(yù)處理护昧，不需要提前歸一化魂迄，處理缺失值

（3）使用決策樹預(yù)測(cè)的代價(jià)是O(log2m)，m為樣本數(shù)

（4）能夠處理數(shù)值型數(shù)據(jù)和分類數(shù)據(jù)

（5）可以處理多維度輸出的分類問題

（6）可以通過數(shù)值統(tǒng)計(jì)測(cè)試來驗(yàn)證該模型捏卓，這使解釋驗(yàn)證該模型的可靠性成為可能

（7）即使該模型假設(shè)的結(jié)果與真實(shí)模型所提供的數(shù)據(jù)有些違反极祸，其表現(xiàn)依舊良好

決策樹算法的缺點(diǎn):

（1）決策樹模型容易產(chǎn)生一個(gè)過于復(fù)雜的模型,這樣的模型對(duì)數(shù)據(jù)的泛化性能會(huì)很差慈格。這就是所謂的過擬合.一些策略像剪枝怠晴、設(shè)置葉節(jié)點(diǎn)所需的最小樣本數(shù)或設(shè)置數(shù)的最大深度是避免出現(xiàn)該問題最為有效地方法。

（2）決策樹可能是不穩(wěn)定的浴捆，因?yàn)閿?shù)據(jù)中的微小變化可能會(huì)導(dǎo)致完全不同的樹生成蒜田。這個(gè)問題可以通過決策樹的集成來得到緩解。

（3）在多方面性能最優(yōu)和簡(jiǎn)單化概念的要求下选泻，學(xué)習(xí)一棵最優(yōu)決策樹通常是一個(gè)NP難問題冲粤。因此美莫，實(shí)際的決策樹學(xué)習(xí)算法是基于啟發(fā)式算法，例如在每個(gè)節(jié)點(diǎn)進(jìn)行局部最優(yōu)決策的貪心算法梯捕。這樣的算法不能保證返回全局最優(yōu)決策樹厢呵。這個(gè)問題可以通過集成學(xué)習(xí)來訓(xùn)練多棵決策樹來緩解,這多棵決策樹一般通過對(duì)特征和樣本有放回的隨機(jī)采樣來生成。

（4）有些概念很難被決策樹學(xué)習(xí)到,因?yàn)闆Q策樹很難清楚的表述這些概念傀顾。例如XOR襟铭，奇偶或者復(fù)用器的問題。

（5）如果某些類在問題中占主導(dǎo)地位會(huì)使得創(chuàng)建的決策樹有偏差短曾。因此寒砖，我們建議在擬合前先對(duì)數(shù)據(jù)集進(jìn)行平衡。

5. 決策樹在sklearn中的一些建議

（1）當(dāng)數(shù)據(jù)的特征維度很高而數(shù)據(jù)量又很少的時(shí)候嫉拐，這樣的數(shù)據(jù)在構(gòu)建決策樹的時(shí)候往往會(huì)過擬合哩都。所以我們要控制樣本數(shù)量和特征的之間正確的比率；

（2）在構(gòu)建決策樹之前婉徘，可以考慮預(yù)先執(zhí)行降維技術(shù)（如PCA漠嵌，ICA或特征選擇），以使我們生成的樹更有可能找到具有辨別力的特征盖呼；

（3）在訓(xùn)練一棵樹的時(shí)候献雅，可以先設(shè)置max_depth=3來將樹可視化出來，以便我們找到樹是怎樣擬合我們數(shù)據(jù)的感覺塌计，然后在增加我們樹的深度挺身；

（4）樹每增加一層，填充所需的樣本數(shù)量是原來的2倍锌仅，比如我們?cè)O(shè)置了最小葉節(jié)點(diǎn)的樣本數(shù)量章钾，當(dāng)我們的樹層數(shù)增加一層的時(shí)候，所需的樣本數(shù)量就會(huì)翻倍热芹，所以我們要控制好樹的最大深度贱傀，防止過擬合；

（5）使用min_samples_split（節(jié)點(diǎn)可以切分時(shí)擁有的最小樣本數(shù)） 和 min_samples_leaf（最小葉節(jié)點(diǎn)數(shù)）來控制葉節(jié)點(diǎn)的樣本數(shù)量伊脓。這兩個(gè)值設(shè)置的很小通常意味著我們的樹過擬合了府寒，而設(shè)置的很大意味著我們樹預(yù)測(cè)的精度又會(huì)降低。通常設(shè)置min_samples_leaf=5报腔；

（6）當(dāng)樹的類比不平衡的時(shí)候株搔，在訓(xùn)練之前一定要先平很數(shù)據(jù)集，防止一些類別大的類主宰了決策樹纯蛾∠朔浚可以通過采樣的方法將各個(gè)類別的樣本數(shù)量到大致相等，或者最好是將每個(gè)類的樣本權(quán)重之和(sample_weight)規(guī)范化為相同的值翻诉。另請(qǐng)注意炮姨，基于權(quán)重的預(yù)剪枝標(biāo)準(zhǔn)（如min_weight_fraction_leaf）將比不知道樣本權(quán)重的標(biāo)準(zhǔn)（如min_samples_leaf）更少偏向主導(dǎo)類別捌刮。

（7）如果樣本是帶權(quán)重的，使用基于權(quán)重的預(yù)剪枝標(biāo)準(zhǔn)將更簡(jiǎn)單的去優(yōu)化樹結(jié)構(gòu)舒岸，如mn_weight_fraction_leaf绅作，這確保了葉節(jié)點(diǎn)至少包含了樣本權(quán)值總體總和的一小部分；

（8）在sklearn中所有決策樹使用的數(shù)據(jù)都是np.float32類型的內(nèi)部數(shù)組。如果訓(xùn)練數(shù)據(jù)不是這種格式，則將復(fù)制數(shù)據(jù)集耳胎，這樣會(huì)浪費(fèi)計(jì)算機(jī)資源猾警。

（9）如果輸入矩陣X非常稀疏，建議在調(diào)用fit函數(shù)和稀疏csr_matrix之前轉(zhuǎn)換為稀疏csc_matrix，然后再調(diào)用predict。 當(dāng)特征在大多數(shù)樣本中具有零值時(shí)，與密集矩陣相比役拴，稀疏矩陣輸入的訓(xùn)練時(shí)間可以快幾個(gè)數(shù)量級(jí)。