1、決策樹分類原理 　　

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

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

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

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

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

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

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

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

劃分?jǐn)?shù)據(jù)集的最大原則是：使無序的數(shù)據(jù)變的有序。如果一個訓(xùn)練數(shù)據(jù)中有20個特征，那么選取哪個做劃分依據(jù)？這就必須采用量化的方法來判斷，量化劃分方法有多重，其中一項就是“信息論度量信息分類”?；谛畔⒄摰臎Q策樹算法有ID3、CART和C4.5等算法，其中C4.5和CART兩種算法從ID3算法中衍生而來。

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

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

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

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

4、決策樹優(yōu)缺點

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

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

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

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

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

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

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

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

決策樹算法的缺點:

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

（2）決策樹可能是不穩(wěn)定的，因為數(shù)據(jù)中的微小變化可能會導(dǎo)致完全不同的樹生成。這個問題可以通過決策樹的集成來得到緩解。

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

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

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

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

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

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

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

（4）樹每增加一層，填充所需的樣本數(shù)量是原來的2倍，比如我們設(shè)置了最小葉節(jié)點的樣本數(shù)量，當(dāng)我們的樹層數(shù)增加一層的時候，所需的樣本數(shù)量就會翻倍，所以我們要控制好樹的最大深度，防止過擬合；

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

（6）當(dāng)樹的類比不平衡的時候，在訓(xùn)練之前一定要先平很數(shù)據(jù)集，防止一些類別大的類主宰了決策樹?？梢酝ㄟ^采樣的方法將各個類別的樣本數(shù)量到大致相等，或者最好是將每個類的樣本權(quán)重之和(sample_weight)規(guī)范化為相同的值。另請注意，基于權(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)將更簡單的去優(yōu)化樹結(jié)構(gòu)，如mn_weight_fraction_leaf，這確保了葉節(jié)點至少包含了樣本權(quán)值總體總和的一小部分；

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

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