決策樹生成演算法

A. 數據挖掘-決策樹演算法

決策樹演算法是一種比較簡易的監督學習分類演算法，既然叫做決策樹，那麼首先他是一個樹形結構，簡單寫一下樹形結構（數據結構的時候學過不少了）。

樹狀結構是一個或多個節點的有限集合，在決策樹里，構成比較簡單，有如下幾種元素：

在決策樹中，每個葉子節點都有一個類標簽，非葉子節點包含對屬性的測試條件，用此進行分類。
所以個人理解，決策樹就是 對一些樣本，用樹形結構對樣本的特徵進行分支，分到葉子節點就能得到樣本最終的分類，而其中的非葉子節點和分支就是分類的條件，測試和預測分類就可以照著這些條件來走相應的路徑進行分類。

根據這個邏輯，很明顯決策樹的關鍵就是如何找出決策條件和什麼時候算作葉子節點即決策樹終止。

決策樹的核心是為不同類型的特徵提供表示決策條件和對應輸出的方法，特徵類型和劃分方法包括以下幾個：

注意，這些圖中的第二層都是分支，不是葉子節點。

如何合理的對特徵進行劃分，從而找到最優的決策模型呢？在這里需要引入信息熵的概念。

先來看熵的概念：

在數據集中，參考熵的定義，把信息熵描述為樣本中的不純度，熵越高，不純度越高，數據越混亂（越難區分分類）。

例如：要給（0，1）分類，熵是0，因為能明顯分類，而均衡分布的（0.5，0.5）熵比較高，因為難以劃分。

信息熵的計算公式為：
其中 代表信息熵。 是類的個數， 代表在 類時 發生的概率。
另外有一種Gini系數，也可以用來衡量樣本的不純度：
其中 代表Gini系數，一般用於決策樹的 CART演算法 。

舉個例子：

如果有上述樣本，那麼樣本中可以知道，能被分為0類的有3個，分為1類的也有3個，那麼信息熵為：
Gini系數為：
總共有6個數據，那麼其中0類3個，佔比就是3/6，同理1類。

我們再來計算一個分布比較一下：

信息熵為：
Gini系數為：

很明顯，因為第二個分布中，很明顯這些數偏向了其中一類，所以 純度更高 ，相對的信息熵和Gini系數較低。

有了上述的概念，很明顯如果我們有一組數據要進行分類，最快的建立決策樹的途徑就是讓其在每一層都讓這個樣本純度最大化，那麼就要引入信息增益的概念。

所謂增益，就是做了一次決策之後，樣本的純度提升了多少（不純度降低了多少），也就是比較決策之前的樣本不純度和決策之後的樣本不純度，差越大，效果越好。
讓信息熵降低，每一層降低的越快越好。
度量這個信息熵差的方法如下：
其中 代表的就是信息熵（或者其他可以度量不純度的系數）的差， 是樣本(parent是決策之前， 是決策之後)的信息熵（或者其他可以度量不純度的系數）， 為特徵值的個數， 是原樣本的記錄總數， 是與決策後的樣本相關聯的記錄個數。

當選擇信息熵作為樣本的不純度度量時，Δ就叫做信息增益 。

我們可以遍歷每一個特徵，看就哪個特徵決策時，產生的信息增益最大，就把他作為當前決策節點，之後在下一層繼續這個過程。

舉個例子：

如果我們的目標是判斷什麼情況下，銷量會比較高（受天氣，周末，促銷三個因素影響），根據上述的信息增益求法，我們首先應該找到根據哪個特徵來決策，以信息熵為例：

首先肯定是要求 ，也就是銷量這個特徵的信息熵：

接下來，就分別看三個特徵關於銷量的信息熵，先看天氣，天氣分為好和壞兩種，其中天氣為好的條件下，銷量為高的有11條，低的有6條；天氣壞時，銷量為高的有7條，銷量為低的有10條，並且天氣好的總共17條，天氣壞的總共17條。

分別計算天氣好和天氣壞時的信息熵，天氣好時：

根據公式 ，可以知道，N是34，而天氣特徵有2個值，則k=2，第一個值有17條可以關聯到決策後的節點，第二個值也是17條，則能得出計算：

再計算周末這個特徵，也只有兩個特徵值，一個是，一個否，其中是有14條，否有20條；周末為是的中有11條銷量是高，3條銷量低，以此類推有：


信息增益為：

另外可以得到是否有促銷的信息增益為0.127268。

可以看出，以周末為決策，可以得到最大的信息增益，因此根節點就可以用周末這個特徵進行分支：

注意再接下來一層的原樣本集，不是34個而是周末為「是」和「否」分別計算，為是的是14個，否的是20個。
這樣一層一層往下遞歸，直到判斷節點中的樣本是否都屬於一類，或者都有同一個特徵值，此時就不繼續往下分了，也就生成了葉子節點。

上述模型的決策樹分配如下：

需要注意的是，特徵是否出現需要在分支當中看，並不是整體互斥的，周末生成的兩個分支，一個需要用促銷來決策，一個需要用天氣，並不代表再接下來就沒有特徵可以分了，而是在促銷決策層下面可以再分天氣，另外一遍天氣決策下面可以再分促銷。

決策樹的模型比較容易解釋，看這個樹形圖就能很容易的說出分類的條件。

我們知道屬性有二元屬性、標稱屬性、序數屬性和連續屬性，其中二元、標稱和序數都是類似的，因為是離散的屬性，按照上述方式進行信息增益計算即可，而連續屬性與這三個不同。

對於連續的屬性，為了降低其時間復雜度，我們可以先將屬性內部排序，之後取相鄰節點的均值作為決策值，依次取每兩個相鄰的屬性值的均值，之後比較他們的不純度度量。

需要注意的是，連續屬性可能在決策樹中出現多次，而不是像離散的屬性一樣在一個分支中出現一次就不會再出現了。

用信息熵或者Gini系數等不純度度量有一個缺點，就是會傾向於將多分支的屬性優先分類——而往往這種屬性並不是特徵。

例如上面例子中的第一行序號，有34個不同的值，那麼信息熵一定很高，但是實際上它並沒有任何意義，因此我們需要規避這種情況，如何規避呢，有兩種方式：

公式如下：

其中k為劃分的總數，如果每個屬性值具有相同的記錄數，則 ，劃分信息等於 ，那麼如果某個屬性產生了大量劃分，則劃分信息很大，信息增益率低，就能規避這種情況了。

為了防止過擬合現象，往往會對決策樹做優化，一般是通過剪枝的方式，剪枝又分為預剪枝和後剪枝。

在構建決策樹時，設定各種各樣的條件如葉子節點的樣本數不大於多少就停止分支，樹的最大深度等，讓決策樹的層級變少以防止過擬合。
也就是在生成決策樹之前，設定了決策樹的條件。

後剪枝就是在最大決策樹生成之後，進行剪枝，按照自底向上的方式進行修剪，修剪的規則是，評估葉子節點和其父節點的代價函數，如果父節點的代價函數比較小，則去掉這個葉子節點。
這里引入的代價函數公式是：
其中 代表的是葉子節點中樣本個數， 代表的是該葉子節點上的不純度度量，把每個葉子節點的 加起來，和父節點的 比較，之後進行剪枝即可。

B. 決策樹分類演算法有哪些

問題一：決策樹演算法是按什麼來進行分類的 決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納演算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
決策樹方法最早產生於上世紀60年代，到70年代末。由J Ross Quinlan提出了ID3演算法，此演算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5演算法在ID3演算法的基礎上進行了改進，對於預測變數的缺值處理、剪枝技術、派生規則等方面作了較大改進，既適合於分類問題，又適合於回歸問題。
決策樹演算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹演算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪枝：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡准確性的分枝剪除。

問題二：數據挖掘分類方法決策樹可以分多類么 數據挖掘,也稱之為資料庫中知識發現是一個可以從海量數據中智能地和自動地抽取一些有用的、可信的、有效的和可以理解的模式的過程.分類是數據挖掘的重要內容之一.目前,分類已廣泛應用於許多領域,如醫療診斷、天氣預測、信用證實、顧客區分、欺詐甄別. 現己有多種分類的方法,其中決策樹分類法在海量數據環境中應用最為廣泛.其原因如下：
1、決策樹分類的直觀的表示方法較容易轉化為標準的資料庫查詢
2、決策樹分類歸納的方法行之有效,尤其適合大型數據集.
3、決策樹在分類過程中,除了數據集中已包括的信息外,不再需要額外的信息.
4、決策樹分類模型的精確度較高. 該文首先研究了評估分類模型的方法.在此基礎上著重研究了決策樹分類方法,並對決策樹演算法的可伸縮性問題進行了具體分析,最後給出了基於OLE DB for DM開發決策樹分類預測應用程序.

問題三：基於規則的分類器（比如用RIPPER演算法）和決策樹的區別在哪，使用場景有什麼不同？ 決策樹實際上是規則分類器。基於轉換的錯誤驅動學習方法的提出者曾經在論文中論證過這個問題，他的學習方法是規則學習器，但和決策樹等價。

問題四：決策樹的優缺點是什麼啊 決策樹(Decision Tree)是在已知各種情況發生概率的基礎上，通過構成決策樹來求取凈現值的期望值大於等於零的概率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。
決策樹的優缺點：
優點：

1) 可以生成可以理解的規則。

2) 計算量相對來說不是很大。

3) 可以處理連續和種類字穿。

4) 決策樹可以清晰的顯示哪些欄位比較重要

缺點：

1) 對連續性的欄位比較難預測。

2) 對有時間順序的數據，需要很多預處理的工作。

3) 當類別太多時，錯誤可能就會增加的比較快。

4) 一般的演算法分類的時候，只是根據一個欄位來分類。

問題五：c4.5決策樹演算法怎麼得到分類結果 決策樹主要有ID3，C4.5，CART等形式。ID3選取信息增益的屬性遞歸進行分類，C4.5改進為使用信息增益率來選取分類屬性。CART是Classfication and Regression Tree的縮寫。表明CART不僅可以進行分類，也可以進行回歸。

問題六：決策樹分類演算法的適用領域，不要概括成經濟、社會、醫療領域，具體到實際問題。且用什麼軟體實現較方便。 決策樹演算法主要用於數據挖掘和機器學習，數據挖掘就是從海量數據中找出規律。一個有名的例子就是啤酒和尿布的例子，這是數據挖掘的典型。決策樹演算法包括ID3，C4.5，CART等，各種演算法都是利用海量的數據來生成決策樹的，決策樹能幫助人或者機器做出決策。最簡單的一個例子就是你去看病，根據決策樹，醫生能夠判斷這是什麼病。軟體的話用VISUAL STUDIO就可以，C語言，C++,C#，java都可以。

問題七：貝葉斯網路和貝葉斯分類演算法的區別 貝葉斯分類演算法是統計學的一種分類方法，它是一類利用概率統計知識進行分類的演算法。在許多場合，樸素貝葉斯(Na?ve Bayes，NB)分類演算法可以與決策樹和神經網路分類演算法相媲美，該演算法能運用到大型資料庫中，而且方法簡單、分類准確率高、速度快。
由於貝葉斯定理假設一個屬性值對給定類的影響獨立於其它屬性的值，而此假設在實際情況中經常是不成立的，因此其分類准確率可能會下降。為此，就衍生出許多降低獨立性假設的貝葉斯分類演算法，如TAN(tree augmented Bayes network)演算法。

C. 決策樹的演算法

C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：
1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；
2) 在樹構造過程中進行剪枝；
3) 能夠完成對連續屬性的離散化處理；
4) 能夠對不完整數據進行處理。
C4.5演算法有如下優點：產生的分類規則易於理解，准確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致演算法的低效。此外，C4.5隻適合於能夠駐留於內存的數據集，當訓練集大得無法在內存容納時程序無法運行。
具體演算法步驟如下；
1創建節點N
2如果訓練集為空，在返回節點N標記為Failure
3如果訓練集中的所有記錄都屬於同一個類別，則以該類別標記節點N
4如果候選屬性為空，則返回N作為葉節點，標記為訓練集中最普通的類；
5for each 候選屬性 attribute_list
6if 候選屬性是連續的then
7對該屬性進行離散化
8選擇候選屬性attribute_list中具有最高信息增益率的屬性D
9標記節點N為屬性D
10for each 屬性D的一致值d
11由節點N長出一個條件為D=d的分支
12設s是訓練集中D=d的訓練樣本的集合
13if s為空
14加上一個樹葉，標記為訓練集中最普通的類
15else加上一個有C4.5（R - {D},C，s）返回的點 背景：
分類與回歸樹(CART——Classification And Regression Tree)) 是一種非常有趣並且十分有效的非參數分類和回歸方法。它通過構建二叉樹達到預測目的。
分類與回歸樹CART 模型最早由Breiman 等人提出，已經在統計領域和數據挖掘技術中普遍使用。它採用與傳統統計學完全不同的方式構建預測准則，它是以二叉樹的形式給出，易於理解、使用和解釋。由CART 模型構建的預測樹在很多情況下比常用的統計方法構建的代數學預測准則更加准確，且數據越復雜、變數越多，演算法的優越性就越顯著。模型的關鍵是預測准則的構建，准確的。
定義：
分類和回歸首先利用已知的多變數數據構建預測准則, 進而根據其它變數值對一個變數進行預測。在分類中, 人們往往先對某一客體進行各種測量, 然後利用一定的分類准則確定該客體歸屬那一類。例如, 給定某一化石的鑒定特徵, 預測該化石屬那一科、那一屬, 甚至那一種。另外一個例子是, 已知某一地區的地質和物化探信息, 預測該區是否有礦。回歸則與分類不同, 它被用來預測客體的某一數值, 而不是客體的歸類。例如, 給定某一地區的礦產資源特徵, 預測該區的資源量。

D. 決策樹演算法原理是什麼

決策樹構造的輸入是一組帶有類別標記的例子，構造的結果是一棵二叉樹或多叉樹。二叉樹的 內部節點(非 葉子節點)一般表示為一個邏輯判斷，如形式為a=aj的邏輯判斷，其中a是屬性，aj是該屬性的所有取值：樹的邊是邏輯判斷的分支結果。

多叉樹(ID3)的內部結點是屬性，邊是該屬性的所有取值，有幾個 屬性值就有幾條邊。樹的葉子節點都是類別標記。

由於數據表示不當、有雜訊或者由於決策樹生成時產生重復的子樹等原因，都會造成產生的決策樹過大。

因此，簡化決策樹是一個不可缺少的環節。尋找一棵最優決策樹，主要應解決以下3個最優化問題：①生成最少數目的葉子節點；②生成的每個葉子節點的深度最小；③生成的決策樹葉子節點最少且每個葉子節點的深度最小。

(4)決策樹生成演算法擴展閱讀：

決策樹演算法的優點如下：

（1）分類精度高；

（2）生成的模式簡單；

（3）對雜訊數據有很好的健壯性。

因而是目前應用最為廣泛的歸納推理演算法之一，在 數據挖掘中受到研究者的廣泛關注。

E. 決策樹演算法的典型演算法

決策樹的典型演算法有ID3，C4.5，CART等。
國際權威的學術組織，數據挖掘國際會議ICDM （the IEEE International Conference on Data Mining）在2006年12月評選出了數據挖掘領域的十大經典演算法中，C4.5演算法排名第一。C4.5演算法是機器學習演算法中的一種分類決策樹演算法,其核心演算法是ID3演算法。C4.5演算法產生的分類規則易於理解，准確率較高。不過在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，在實際應用中因而會導致演算法的低效。
決策樹演算法的優點如下：
（1）分類精度高；
（2）生成的模式簡單；
（3）對雜訊數據有很好的健壯性。
因而是目前應用最為廣泛的歸納推理演算法之一，在數據挖掘中受到研究者的廣泛關注。

F. 決策樹法分為那幾個步驟

1、特徵選擇

特徵選擇決定了使用哪些特徵來做判斷。在訓練數據集中，每個樣本的屬性可能有很多個，不同屬性的作用有大有小。因而特徵選擇的作用就是篩選出跟分類結果相關性較高的特徵，也就是分類能力較強的特徵。在特徵選擇中通常使用的准則是：信息增益。

2、決策樹生成

選擇好特徵後，就從根節點觸發，對節點計算所有特徵的信息增益，選擇信息增益最大的特徵作為節點特徵，根據該特徵的不同取值建立子節點；對每個子節點使用相同的方式生成新的子節點，直到信息增益很小或者沒有特徵可以選擇為止。

3、決策樹剪枝

剪枝的主要目的是對抗「過擬合」，通過主動去掉部分分支來降低過擬合的風險。

【簡介】

決策樹是一種解決分類問題的演算法，決策樹演算法採用樹形結構，使用層層推理來實現最終的分類。

G. 決策樹演算法原理

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

如果不考慮效率等，那麼樣本所有特徵的判斷級聯起來終會將某一個樣本分到一個類終止塊上。實際上，樣本所有特徵中有一些特徵在分類時起到決定性作用，決策樹的構造過程就是找到這些具有決定性作用的特徵，根據其決定性程度來構造一個倒立的樹--決定性作用最大的那個特徵作為根節點，然後遞歸找到各分支下子數據集中次大的決定性特徵，直至子數據集中所有數據都屬於同一類。所以，構造決策樹的過程本質上就是根據數據特徵將數據集分類的遞歸過程，我們需要解決的第一個問題就是，當前數據集上哪個特徵在劃分數據分類時起決定性作用。

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

特徵選擇：特徵選擇是指從訓練數據中眾多的特徵中選擇一個特徵作為當前節點的分裂標准，如何選擇特徵有著很多不同量化評估標准標准，從而衍生出不同的決策樹演算法。

決策樹生成： 根據選擇的特徵評估標准，從上至下遞歸地生成子節點，直到數據集不可分則停止決策樹停止生長。 樹結構來說，遞歸結構是最容易理解的方式。

剪枝：決策樹容易過擬合，一般來需要剪枝，縮小樹結構規模、緩解過擬合。剪枝技術有預剪枝和後剪枝兩種。

劃分數據集的最大原則是：使無序的數據變的有序。如果一個訓練數據中有20個特徵，那麼選取哪個做劃分依據？這就必須採用量化的方法來判斷，量化劃分方法有多重，其中一項就是「資訊理論度量信息分類」。基於資訊理論的決策樹演算法有ID3、CART和C4.5等演算法，其中C4.5和CART兩種演算法從ID3演算法中衍生而來。

CART和C4.5支持數據特徵為連續分布時的處理，主要通過使用二元切分來處理連續型變數，即求一個特定的值-分裂值：特徵值大於分裂值就走左子樹，或者就走右子樹。這個分裂值的選取的原則是使得劃分後的子樹中的「混亂程度」降低，具體到C4.5和CART演算法則有不同的定義方式。

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

C4.5是ID3的一個改進演算法，繼承了ID3演算法的優點。C4.5演算法用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足在樹構造過程中進行剪枝；能夠完成對連續屬性的離散化處理；能夠對不完整數據進行處理。C4.5演算法產生的分類規則易於理解、准確率較高；但效率低，因樹構造過程中，需要對數據集進行多次的順序掃描和排序。也是因為必須多次數據集掃描，C4.5隻適合於能夠駐留於內存的數據集。

CART演算法的全稱是Classification And Regression Tree，採用的是Gini指數（選Gini指數最小的特徵s）作為分裂標准,同時它也是包含後剪枝操作。ID3演算法和C4.5演算法雖然在對訓練樣本集的學習中可以盡可能多地挖掘信息，但其生成的決策樹分支較大，規模較大。為了簡化決策樹的規模，提高生成決策樹的效率，就出現了根據GINI系數來選擇測試屬性的決策樹演算法CART。

決策樹演算法的優點：

（1）便於理解和解釋，樹的結構可以可視化出來

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

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

（4）能夠處理數值型數據和分類數據

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

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

（7）即使該模型假設的結果與真實模型所提供的數據有些違反，其表現依舊良好

決策樹演算法的缺點:

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

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

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

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

（5）如果某些類在問題中佔主導地位會使得創建的決策樹有偏差。因此，我們建議在擬合前先對數據集進行平衡。

（1）當數據的特徵維度很高而數據量又很少的時候，這樣的數據在構建決策樹的時候往往會過擬合。所以我們要控制樣本數量和特徵的之間正確的比率；

（2）在構建決策樹之前，可以考慮預先執行降維技術（如PCA，ICA或特徵選擇），以使我們生成的樹更有可能找到具有辨別力的特徵；

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

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

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

（6）當樹的類比不平衡的時候，在訓練之前一定要先平很數據集，防止一些類別大的類主宰了決策樹。可以通過采樣的方法將各個類別的樣本數量到大致相等，或者最好是將每個類的樣本權重之和(sample_weight)規范化為相同的值。另請注意，基於權重的預剪枝標准（如min_weight_fraction_leaf）將比不知道樣本權重的標准（如min_samples_leaf）更少偏向主導類別。

（7）如果樣本是帶權重的，使用基於權重的預剪枝標准將更簡單的去優化樹結構，如mn_weight_fraction_leaf，這確保了葉節點至少包含了樣本權值總體總和的一小部分；

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

（9）如果輸入矩陣X非常稀疏，建議在調用fit函數和稀疏csr_matrix之前轉換為稀疏csc_matrix，然後再調用predict。 當特徵在大多數樣本中具有零值時，與密集矩陣相比，稀疏矩陣輸入的訓練時間可以快幾個數量級。

H. 決策樹的原理及演算法

決策樹基本上就是把我們以前的經驗總結出來。我給你准備了一個打籃球的訓練集。如果我們要出門打籃球，一般會根據「天氣」、「溫度」、「濕度」、「刮風」這幾個條件來判斷，最後得到結果：去打籃球？還是不去？

上面這個圖就是一棵典型的決策樹。我們在做決策樹的時候，會經歷兩個階段：構造和剪枝。

構造就是生成一棵完整的決策樹。簡單來說，構造的過程就是選擇什麼屬性作為節點的過程，那麼在構造過程中，會存在三種節點：
根節點：就是樹的最頂端，最開始的那個節點。在上圖中，「天氣」就是一個根節點；
內部節點：就是樹中間的那些節點，比如說「溫度」、「濕度」、「刮風」；
葉節點：就是樹最底部的節點，也就是決策結果。

剪枝就是給決策樹瘦身，防止過擬合。分為「預剪枝」（Pre-Pruning）和「後剪枝」（Post-Pruning）。

預剪枝是在決策樹構造時就進行剪枝。方法是在構造的過程中對節點進行評估，如果對某個節點進行劃分，在驗證集中不能帶來准確性的提升，那麼對這個節點進行劃分就沒有意義，這時就會把當前節點作為葉節點，不對其進行劃分。

後剪枝就是在生成決策樹之後再進行剪枝，通常會從決策樹的葉節點開始，逐層向上對每個節點進行評估。如果剪掉這個節點子樹，與保留該節點子樹在分類准確性上差別不大，或者剪掉該節點子樹，能在驗證集中帶來准確性的提升，那麼就可以把該節點子樹進行剪枝。

1是欠擬合，3是過擬合，都會導致分類錯誤。

造成過擬合的原因之一就是因為訓練集中樣本量較小。如果決策樹選擇的屬性過多，構造出來的決策樹一定能夠「完美」地把訓練集中的樣本分類，但是這樣就會把訓練集中一些數據的特點當成所有數據的特點，但這個特點不一定是全部數據的特點，這就使得這個決策樹在真實的數據分類中出現錯誤，也就是模型的「泛化能力」差。

p(i|t) 代表了節點 t 為分類 i 的概率，其中 log2 為取以 2 為底的對數。這里我們不是來介紹公式的，而是說存在一種度量，它能幫我們反映出來這個信息的不確定度。當不確定性越大時，它所包含的信息量也就越大，信息熵也就越高。

ID3 演算法計算的是信息增益，信息增益指的就是劃分可以帶來純度的提高，信息熵的下降。它的計算公式，是父親節點的信息熵減去所有子節點的信息熵。

公式中 D 是父親節點，Di 是子節點，Gain(D,a) 中的 a 作為 D 節點的屬性選擇。

因為 ID3 在計算的時候，傾向於選擇取值多的屬性。為了避免這個問題，C4.5 採用信息增益率的方式來選擇屬性。信息增益率 = 信息增益 / 屬性熵，具體的計算公式這里省略。

當屬性有很多值的時候，相當於被劃分成了許多份，雖然信息增益變大了，但是對於 C4.5 來說，屬性熵也會變大，所以整體的信息增益率並不大。

ID3 構造決策樹的時候，容易產生過擬合的情況。在 C4.5 中，會在決策樹構造之後採用悲觀剪枝（PEP），這樣可以提升決策樹的泛化能力。

悲觀剪枝是後剪枝技術中的一種，通過遞歸估算每個內部節點的分類錯誤率，比較剪枝前後這個節點的分類錯誤率來決定是否對其進行剪枝。這種剪枝方法不再需要一個單獨的測試數據集。

C4.5 可以處理連續屬性的情況，對連續的屬性進行離散化的處理。比如打籃球存在的「濕度」屬性，不按照「高、中」劃分，而是按照濕度值進行計算，那麼濕度取什麼值都有可能。該怎麼選擇這個閾值呢，C4.5 選擇具有最高信息增益的劃分所對應的閾值。

針對數據集不完整的情況，C4.5 也可以進行處理。

暫無

請你用下面的例子來模擬下決策樹的流程，假設好蘋果的數據如下，請用 ID3 演算法來給出好蘋果的決策樹。

「紅」的信息增益為：1「大」的信息增益為：0
因此選擇「紅」的作為根節點，「大」沒有用，剪枝。

數據分析實戰45講.17 丨決策樹（上）：要不要去打籃球？決策樹來告訴你

I. 決策樹演算法-原理篇

關於決策樹演算法，我打算分兩篇來講，一篇講思想原理，另一篇直接擼碼來分析演算法。本篇為原理篇。
通過閱讀這篇文章，你可以學到：
1、決策樹的本質
2、決策樹的構造過程
3、決策樹的優化方向

決策樹根據使用目的分為：分類樹和回歸樹，其本質上是一樣的。本文只講分類樹。

決策樹，根據名字來解釋就是，使用樹型結構來模擬決策。
用圖形表示就是下面這樣。

其中橢圓形代表：特徵或屬性。長方形代表：類別結果。
面對一堆數據（含有特徵和類別），決策樹就是根據這些特徵（橢圓形）來給數據歸類（長方形）
例如，信用貸款問題，我根據《神奇動物在哪裡》的劇情給銀行造了個決策樹模型，如下圖：

然而，決定是否貸款可以根據很多特徵，然麻雞銀行選擇了：（1）是否房產價值>100w；（2）是否有其他值錢的抵押物；（3）月收入>10k；（4）是否結婚；這四個特徵，來決定是否給予貸款。
先不管是否合理，但可以肯定的是，決策樹做了特徵選擇工作，即選擇出類別區分度高的特徵。

由此可見， 決策樹其實是一種特徵選擇方法。 （特徵選擇有多種，決策樹屬於嵌入型特徵選擇，以後或許會講到，先給個圖）即選擇區分度高的特徵子集。

那麼， 從特徵選擇角度來看決策樹，決策樹就是嵌入型特徵選擇技術

同時，決策樹也是機器學習中經典分類器演算法，通過決策路徑，最終能確定實例屬於哪一類別。
那麼， 從分類器角度來看決策樹，決策樹就是樹型結構的分類模型

從人工智慧知識表示法角度來看，決策樹類似於if-then的產生式表示法。
那麼， 從知識表示角度來看決策樹，決策樹就是if-then規則的集合

由上面的例子可知，麻雞銀行通過決策樹模型來決定給哪些人貸款，這樣決定貸款的流程就是固定的，而不由人的主觀情感來決定。
那麼， 從使用者角度來看決策樹，決策樹就是規范流程的方法

最後我們再來看看決策樹的本質是什麼已經不重要了。
決策樹好像是一種思想，而通過應用在分類任務中從而成就了「決策樹演算法」。

下面內容還是繼續講解用於分類的「決策樹演算法」。

前面講了決策樹是一種 特徵選擇技術 。

既然決策樹就是一種特徵選擇的方法，那麼經典決策樹演算法其實就是使用了不同的特徵選擇方案。
如：
（1）ID3：使用信息增益作為特徵選擇
（2）C4.5：使用信息增益率作為特徵選擇
（3）CART：使用GINI系數作為特徵選擇
具體選擇的方法網上一大把，在這里我提供幾個鏈接，不細講。

但，不僅僅如此。
決策樹作為嵌入型特徵選擇技術結合了特徵選擇和分類演算法，根據特徵選擇如何生成分類模型也是決策樹的一部分。
其生成過程基本如下：

根據這三個步驟，可以確定決策樹由：（1）特徵選擇；（2）生成方法；（3）剪枝，組成。
決策樹中學習演算法與特徵選擇的關系如下圖所示：

原始特徵集合T：就是包含收集到的原始數據所有的特徵，例如：麻瓜銀行收集到與是否具有償還能力的所有特徵，如：是否結婚、是否擁有100w的房產、是否擁有汽車、是否有小孩、月收入是否>10k等等。
中間的虛線框就是特徵選擇過程，例如：ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系數。
其中評價指標（如：信息增益）就是對特徵的要求，特徵需要滿足這種條件（一般是某個閾值），才能被選擇，而這一選擇過程嵌入在學習演算法中，最終被選擇的特徵子集也歸到學習演算法中去。
這就是抽象的決策樹生成過程，不論哪種演算法都是將這一抽象過程的具體化。
其具體演算法我將留在下一篇文章來講解。

而決策樹的剪枝，其實用得不是很多，因為很多情況下隨機森林能解決決策樹帶來的過擬合問題，因此在這里也不講了。

決策樹的優化主要也是圍繞決策樹生成過程的三個步驟來進行優化的。
樹型結構，可想而知，演算法效率決定於樹的深度，優化這方面主要從特徵選擇方向上優化。
提高分類性能是最重要的優化目標，其主要也是特徵選擇。
面對過擬合問題，一般使用剪枝來優化，如：李國和基於決策樹生成及剪枝的數據集優化及其應用。
同時，決策樹有很多不足，如：多值偏向、計算效率低下、對數據空缺較為敏感等，這方面的優化也有很多，大部分也是特徵選擇方向，如：陳沛玲使用粗糙集進行特徵降維。
由此，決策樹的優化方向大多都是特徵選擇方向，像ID3、C4.5、CART都是基於特徵選擇進行優化。

參考文獻
統計學習方法-李航
特徵選擇方法綜述-李郅琴
決策樹分類演算法優化研究_陳沛玲
基於決策樹生成及剪枝的數據集優化及其應用-李國和