決策樹的分裂演算法

① 決策樹法的計算題

依據y坐標將六個點劃分為兩個子類，水平線上面的兩個點是同一個分類，但是水平線之下的四個點是不純凈的。

對這四個點進行再次分類，以x左邊分類，通過兩層分類，現了對樣本點的完全分類。

決策樹是一種具有樹狀結構的分類和預測工具，其中每個內部節點表示對一個屬性的測試，每個分支表示測試的結果，每個葉節點(終端節點)持有一個類標簽。

(1)決策樹的分裂演算法擴展閱讀

決策樹演算法的關鍵

1、分裂屬性的選擇

即選擇哪個自變數作為樹叉，也就是在n個自變數中，優先選擇哪個自變數進行分叉。

2、樹剪枝

即在構建樹叉時，由於數據中的雜訊和離群點，許多分支反映的是訓練數據中的異常，而樹剪枝則是處理這種過分擬合的數據問題，常用的剪枝方法為先剪枝和後剪枝。

② 決策樹總結

參考鏈接： https://www.cnblogs.com/yonghao/p/5061873.html

樹：由節點和邊兩種元素組成。
父節點、子節點是相對的，子節點由父節點根據某一規則分裂而來。
根節點：沒有父節點的節點，初始分裂節點。
葉子節點：沒有子節點的節點。

決策樹： 利用樹形結構進行決策，每一個非葉子節點是一個判斷條件，每一個葉子節點是結論。從根節點開始，經過多次判斷得出結論。

每次選擇一個屬性進行判斷（如何選擇？），如果不能得出結論，繼續選擇其他屬性進行判斷，知道能夠肯定地判斷出用戶類型或者上述屬性都已使用完畢。

在決策樹的過程中，三個問題最為關鍵：

貪婪思想：選擇可以得到最有分裂結果的屬性進行分裂。每一次分裂之後孩子節點的數據盡量「純」。

信息增益
信息增益率

信息增益作為選擇分裂的條件有一個不可避免的缺點：傾向選擇分支比較多的屬性進行分裂。（為什麼？）

表示分列前後的數據復雜度和分裂節點數據復雜度的變化值：

Gain表示節點復雜度，Gain越大復雜度越高。
信息增益大 ，分裂後復雜度減小得多， 分類效果明顯 。

復雜度的兩種計算方式：
熵和基尼指數，主要區別在於，熵達到峰值的過程要相對慢一些。因此，熵對於混亂集合的判罰要更重一些。
a）熵Entropy
取值范圍：[0,1]
熵大，混亂程度高，純度低。v.v.

pi表示第i類的數量佔比。Entropy也記為H(X)。
二分類中：如果兩類數量相同，純度最低，熵為1 。如果全部數據都屬於一個類，及誒單純度最高，熵為0 。

pi<1， 由上圖可知，pi log(pi)為負值，故熵為pi log(pi)的和乘以-1。

條件熵：
隨機變數X在給定條件下隨機變數Y的條件熵。
X給定條件下Y的條件干率分布的熵對X的數學期望，在機器學習中為選定某個特徵後的熵，公式如下：

b）基尼指數 Gini Index
取值范圍：[0,1]
是一種不等性度量
總體內包含的類別越雜亂，gini指數越大，數據越不純。

pi依舊為第i類的數量佔比

使用信息增益作為選擇分裂的條件傾向選擇分支比較多的屬性進行分裂。
為了解決這個問題，引入了信息增益率這個概念。信息增益率是在信息增益的基礎上除以分裂節點數據量的信息增益。

InstrinsicInfo：分裂子節點數據量的信息增益
m：子節點數量
ni：第i個子節點的數據量
N：父節點數據量

離散型屬性：按照屬性值進行分裂，每一種屬性值對應一個分裂節點。
連續性屬性：按照該屬性進行排序，並分為若干區間，每個區間對應一個節點。（區間大小如何選擇？）

1）最小節點數
當街點數據量小於一個指定的數據量時，不繼續分裂。
原因：

分類樹：輸出具體的類別
回歸樹：輸出確定的數值
構建方法主要有三種：

預剪枝（Pre-Pruning）
後剪枝（Post-Pruning）

③ 決策樹演算法的基本思想

1）樹以代表訓練樣本的單個結點開始。
2）如果樣本都在同一個類．則該結點成為樹葉，並用該類標記。
3）否則，演算法選擇最有分類能力的屬性作為決策樹的當前結點．
4）根據當前決策結點屬性取值的不同，將訓練樣本數據集tlI分為若乾子集，每個取值形成一個分枝，有幾個取值形成幾個分枝。勻針對上一步得到的一個子集，重復進行先前步驟，遞4'I形成每個劃分樣本上的決策樹。一旦一個屬性出現在一個結點上，就不必在該結點的任何後代考慮它。
5）遞歸劃分步驟僅當下列條件之一成立時停止：
①給定結點的所有樣本屬於同一類。
②沒有剩餘屬性可以用來進一步劃分樣本．在這種情況下．使用多數表決，將給定的結點轉換成樹葉，並以樣本中元組個數最多的類別作為類別標記，同時也可以存放該結點樣本的類別分布，
③如果某一分枝tc，沒有滿足該分支中已有分類的樣本，則以樣本的多數類創建一個樹葉。

④ 決策樹演算法原理

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

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

一棵決策樹的生成過程主要分為以下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。 當特徵在大多數樣本中具有零值時，與密集矩陣相比，稀疏矩陣輸入的訓練時間可以快幾個數量級。

⑤ 決策樹（Decision Tree）

  決策樹（Decision Tree）是一種基本的分類與回歸方法，其模型呈樹狀結構，在分類問題中，表示基於特徵對實例進行分類的過程。本質上，決策樹模型就是一個定義在特徵空間與類空間上的條件概率分布。決策樹學習通常包括三個步驟： 特徵選擇 、 決策樹的生成 和 決策樹的修剪 。

  分類決策樹模型是一種描述對實例進行分類的樹形結構，決策樹由節點（node）和有向邊（directed edge）組成。節點有兩種類型：內部節點（internal node）和葉節點（leaf node）。內部節點表示一個特徵或屬性，葉節點表示一個類。

  利用決策樹進行分類，從根節點開始，對實例的某一特徵進行測試，根據測試結果將實例分配到其子節點；這時，每一個子節點對應著該特徵的一個取值。如此遞歸地對實例進行測試並分配，直至達到葉節點。最後將實例分到葉節點的類中。

  決策樹是給定特徵條件下類的條件概率分布，這一條件概率分布定義在特徵區間的一個劃分（partiton）上。將特徵空間劃分為互不相交的單元（cell）或區域（region），並在每個單元定義一個類的概率分布就構成了一個條件概率分布。決策樹的一條路徑對應劃分中的一個單元，決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成。假設X為表示特徵的隨機變數，Y為表示類的隨機變數，那麼這個條件概率分布可以表示成P(Y|X)。X取值於給定劃分下單元的集合，Y取值於類的集合，各葉節點（單元）上的條件概率往往偏向於某一個類，即屬於某一類的概率較大，決策樹分類時將該節點的實例分到條件概率大的那一類去。也就以為著決策樹學習的過程其實也就是由數據集估計條件概率模型的過程，這些基於特徵區間劃分的類的條件概率模型由無窮多個，在進行選擇時，不僅要考慮模型的擬合能力還要考慮其泛化能力。

  為了使模型兼顧模型的擬合和泛化能力，決策樹學習使用正則化的極大似然函數來作為損失函數，以最小化損失函數為目標，尋找最優的模型。顯然從所有可能的決策樹中選取最優決策樹是NP完全問題，所以在實際中通常採用啟發式的方法，近似求解這一最優化問題： 通過遞歸的選擇最優特徵，根據該特徵對訓練數據進行劃分直到使得各個子數據集有一個最好的分類，最終生成特徵樹 。當然，這樣得到的決策樹實際上是次最優（sub-optimal）的。進一步的，由於決策樹的演算法特性，為了防止模型過擬合，需要對已生成的決策樹自下而上進行剪枝，將樹變得更簡單，提升模型的泛化能力。具體來說，就是去掉過於細分的葉節點，使其退回到父節點，甚至更高的節點，然後將父節點或更高的節點改為新的葉節點。如果數據集的特徵較多，也可以在進行決策樹學習之前，對數據集進行特徵篩選。

  由於決策樹是一個條件概率分布，所以深淺不同的決策樹對應著不同復雜度的概率模型，決策樹的生成對應模型的局部選擇，決策樹的剪枝對應著模型的全局選擇。

   熵（Entropy） 的概念最早起源於物理學，最初物理學家用這個概念度量一個熱力學系統的無序程度。在1948年， 克勞德·艾爾伍德·香農 將熱力學的熵，引入到 資訊理論 ，因此它又被稱為 香農熵 。在資訊理論中，熵是對不確定性的量度，在一條信息的熵越高則能傳輸越多的信息，反之，則意味著傳輸的信息越少。

  如果有一枚理想的硬幣，其出現正面和反面的機會相等，則拋硬幣事件的熵等於其能夠達到的最大值。我們無法知道下一個硬幣拋擲的結果是什麼，因此每一次拋硬幣都是不可預測的。因此，使用一枚正常硬幣進行若干次拋擲，這個事件的熵是一 比特 ，因為結果不外乎兩個——正面或者反面，可以表示為 0, 1 編碼，而且兩個結果彼此之間相互獨立。若進行 n 次 獨立實驗 ，則熵為 n ，因為可以用長度為 n 的比特流表示。但是如果一枚硬幣的兩面完全相同，那個這個系列拋硬幣事件的熵等於零，因為 結果能被准確預測 。現實世界裡，我們收集到的數據的熵介於上面兩種情況之間。

  另一個稍微復雜的例子是假設一個 隨機變數 X ，取三種可能值 ，概率分別為 ，那麼編碼平均比特長度是： 。其熵為 。因此<u>熵實際是對隨機變數的比特量和順次發生概率相乘再總和的</u> 數學期望 。

  依據玻爾茲曼H定理，香農把隨機變數X的熵 定義為：

  其中 是隨機變數X的信息量，當隨機變數取自有限樣本時，熵可以表示為：

  若 ，則定義 。

  同理可以定義條件熵 :

  很容易看出，條件熵（conditional entropy） 就是X給定條件下Y的條件概率分布的熵對X的數學期望。當熵和條件熵中的概率有極大似然估計得到時，所對應的熵和條件熵分別稱為檢驗熵（empirical entropy）和經驗條件熵（empirical conditional entropy）.

  熵越大，隨機變數的不確定性就越大，從定義可以驗證:

  當底數 時，熵的單位是 ；當 時，熵的單位是 ;而當 時，熵的單位是 .

  如英語有26個字母，假如每個字母在文章中出現的次數平均的話，每個字母的信息量 為：

  同理常用漢字2500有個，假設每個漢字在文章中出現的次數平均的話，每個漢字的信息量 為：

  事實上每個字母和漢字在文章中出現的次數並不平均，少見字母和罕見漢字具有相對較高的信息量，顯然，由期望的定義，熵是整個消息系統的平均消息量。

  熵可以用來表示數據集的不確定性，熵越大，則數據集的不確定性越大。因此使用 劃分前後數據集熵的差值 量度使用當前特徵對於數據集進行劃分的效果（類似於深度學習的代價函數）。對於待劃分的數據集 ，其劃分前的數據集的熵 是一定的，但是劃分之後的熵 是不定的， 越小說明使用此特徵劃分得到的子集的不確定性越小（也就是純度越高）。因此 越大，說明使用當前特徵劃分數據集 時，純度上升的更快。而我們在構建最優的決策樹的時候總希望能更快速到達純度更高的數據子集，這一點可以參考優化演算法中的梯度下降演算法，每一步沿著負梯度方法最小化損失函數的原因就是負梯度方向是函數值減小最快的方向。同理：在決策樹構建的過程中我們總是希望集合往最快到達純度更高的子集合方向發展，因此我們總是選擇使得信息增益最大的特徵來劃分當前數據集 。

  顯然這種劃分方式是存在弊端的，按信息增益准則的劃分方式，當數據集的某個特徵B取值較多時，依此特徵進行劃分更容易得到純度更高的數據子集，使得 偏小，信息增益會偏大，最終導致信息增益偏向取值較多的特徵。

  設 是 個數據樣本的集合，假定類別屬性具有 個不同的值： ,設 是類 中的樣本數。對於一個給定樣本，它的信息熵為：

  其中， 是任意樣本屬於 的概率，一般可以用 估計。

  設一個屬性A具有 個不同的值 ，利用屬性A將集合 劃分為 個子集 ，其中 包含了集合 中屬性 取 值的樣本。若選擇屬性A為測試屬性，則這些子集就是從集合 的節點生長出來的新的葉節點。設 是子集 中類別為 的樣本數，則根據屬性A劃分樣本的信息熵為：

  其中 , 是子集 中類別為 的樣本的概率。最後，用屬性A劃分樣本子集 後所得的 信息增益(Gain) 為：

  即，<u>屬性A的信息增益=劃分前數據的熵-按屬性A劃分後數據子集的熵</u>。 信息增益（information gain）又稱為互信息（matual information）表示得知特徵X的信息而使得類Y的信息的不確定性減少的程度 。信息增益顯然 越小， 的值越大，說明選擇測試屬性A對於分類提供的信息越多，選擇A之後對分類的不確定程度越小。

  經典演算法 ID3 使用的信息增益特徵選擇准則會使得劃分更偏相遇取值更多的特徵，為了避免這種情況。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基礎上將特徵選擇准則由 信息增益 改為了 信息增益率 。在信息增益的基礎之上乘上一個懲罰參數。特徵個數較多時，懲罰參數較小；特徵個數較少時，懲罰參數較大（類似於正則化）。這個懲罰參數就是 分裂信息度量 的倒數 。

  不同於 ID3 和 C4.5 , CART 使用基尼不純度來作為特徵選擇准則。基尼不純度也叫基尼指數 , 表示在樣本集合中一個隨機選中的樣本被分錯的概率 則<u>基尼指數（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率</u>。Gini指數越小表示集合中被選中的樣本被分錯的概率越小，也就是說集合的純度越高，反之，集合越不純。

樣本集合的基尼指數：
樣本集合 有m個類別， 表示第 個類別的樣本數量,則 的Gini指數為：

基於某個特徵劃分樣本集合S之後的基尼指數：
  CART是一個二叉樹，也就是當使用某個特徵劃分樣本集合後，得到兩個集合：a.等於給定的特徵值的樣本集合 ；b.不等於給定特徵值的樣本集合 。實質上是對擁有多個取值的特徵的二值處理。

對於上述的每一種劃分，都可以計算出基於劃分特=某個特徵值將樣本集合劃分為兩個子集的純度：

因而對於一個具有多個取值（超過2個）的特徵，需要計算以每個取值為劃分點，對樣本集合劃分後子集的純度 ( 表示特徵 的可能取值)然後從所有的劃分可能 中找出Gini指數最小的劃分，這個劃分的劃分點，就是使用特徵 對樣本集合 進行劃分的最佳劃分點。

參考文獻 ：

決策樹--信息增益，信息增益比，Geni指數的理解

【機器學習】深入理解--信息熵（Information Entropy）

統計學習方法 （李航）

  為了便於理解，利用以下數據集分別使用三種方法進行分類：

  在進行具體分析之前，考慮到收入是數值類型，要使用決策樹演算法，需要先對該屬性進行離散化。
  在機器學習演算法中，一些分類演算法（ID3、Apriori等）要求數據是分類屬性形式，因此在處理分類問題時經常需要將一些連續屬性變換為分類屬性。一般來說，連續屬性的離散化都是通過在數據集的值域內設定若干個離散的劃分點，將值域劃分為若干區間，然後用不同的符號或整數數值代表落在每個子區間中的數據值。所以，離散化最核心的兩個問題是：如何確定分類數以及如何將連續屬性映射到這些分類值。常用的離散化方法有 等寬法 ， 等頻法 以及 一維聚類法 等。

在實際使用時往往使用Pandas的 cut() 函數實現等寬離散化:

  可以看到與手工計算的離散化結果相同，需要注意的是，<u> 等寬法對於離群點比較敏感，傾向於不均勻地把屬性值分布到各個區間，導致某些區間數據較多，某些區間數據很少，這顯然不利用決策模型的建立。 </u>

使用四個分位數作為邊界點，對區間進行劃分：

<u> 等頻率離散化雖然避免了等寬離散化的數據分布不均勻的問題,卻可能將相同的數據值分到不同的區間以滿足每個區間具有相同數量的屬性取值的要求。 </u>

使用一維聚類的離散化方法後得到數據集為：

  在本次實例中選擇使用基於聚類的離散化方法後得到的數據集進行指標計算。為了預測客戶能否償還債務，使用A（擁有房產）、B（婚姻情況）、C（年收入）等屬性來進行數據集的劃分最終構建決策樹。

單身 ：

離婚 ：

已婚 ：

顯然，由B屬性取值'已婚'劃分得到的子數據集屬於同一個葉節點，無法再進行分類。
接下來，對由B屬性取值'單身'劃分得到的子數據集 再進行最優特徵選擇：

1）計算數據集 總的信息熵，其中4個數據中，能否償還債務為'是'數據有3，'否'數據有1,則總的信息熵：

2）對於A(擁有房產)屬性，其屬性值有'是'和'否'兩種。其中，在A為'是'的前提下，能否償還債務為'是'的有1、'否'的有0；在A為'否'的前提下，能否償還債務為'是'的有2、為'否'的有1，則A屬性的信息熵為：

3)對於B（婚姻情況）屬性，由於已被確定，在這個數據子集信息熵為0

4)對於C（年收入）屬性，其屬性值有'中等輸入'、'低收入'兩種。在C為'中等收入'的前提下，能否償還作為為'是'的有1,為'否'的有0；在C為'低收入'的前提下，能否償還作為為'是'的有2,為'否'的有1;則C屬性的信息熵為：

5）最後分別計算兩個屬性的信息增益值：


信息增益值相同，說明以兩個屬性對數據子集進行劃分後決策樹的純度上升是相同的，此時任選其一成為葉節點即可。
同理，對數據子集 進行最優特徵選擇，發現信息熵為0：
整理得到最終的決策樹：

⑥ 決策樹、隨機森林

在了解樹模型之前，自然想到樹模型和線性模型，他們有什麼區別呢？

決策樹與邏輯回歸的分類區別也在於此。

樹形模型更加接近人的思維方式，可以 產生可視化的分類規則，產生的模型具有可解釋性 。樹模型擬合出來的函數其實是 分區間的階梯函數 。

決策樹（decision tree）是一種基本的分類與回歸方法，此處主要討論分類的決策樹。決策樹是一種十分常用的分類方法，屬於有監督學習（Supervised Learning）。所謂有監督學習，就是給出一堆樣本，每個樣本都有一組屬性和一個分類結果，也就是分類結果已知，那麼通過學習這些樣本得到一個決策樹，這個決策樹能夠對新的數據給出正確的分類。

決策樹是一種樹形結構，它主要有三種不同的節點：

決策樹演算法主要包括三個部分： 特徵選擇、樹的生成、樹的剪枝。

比較常用的決策樹演算法有ID3，C4.5和CART（Classification And Regression Tree），CART的分類效果一般優於其他決策樹。

樣本數量，特徵數量上面，一開始需要注意的：

當熵中的概率由數據估計(特別是最大似然估計)得到時，所對應的熵稱為 經驗熵 (empirical entropy)。

什麼叫由數據估計？比如有10個數據，一共有兩個類別，A類和B類。其中有7個數據屬於A類，則該A類的概率即為十分之七。其中有3個數據屬於B類，則該B類的概率即為十分之三。淺顯的解釋就是，這概率是我們根據數據數出來的。

訓練數據集D，則訓練數據集D的經驗熵為H(D)，|D|表示其樣本容量，及樣本個數。設有K個類Ck，k = 1,2,3,···,K，|Ck|為屬於類Ck的樣本個數，這經驗熵公式可以寫為：

信息增益表示得知特徵X的信息而使得類Y的信息不確定性減少的程度。

條件熵H(Y|X)表示在已知隨機變數X的條件下隨機變數Y的不確定性，隨機變數X給定的條件下隨機變數Y的條件熵(conditional entropy) H(Y|X)，定義X給定條件下Y的條件概率分布的熵對X的數學期望：

當熵和條件熵中的概率由數據估計（特別是極大似然估計）得到時，所對應的分別為經驗熵和經驗條件熵，此時如果有0概率，令0log0=0。

信息增益

一般地， 熵H(D)與條件熵H(D|A)之差成為互信息(mutual information) 。決策樹學習中的信息增益等價於訓練數據集中類與特徵的互信息。

信息增益比

Gini 指數

舉例計算Gini指數（不純度）

這個分類結果明顯並不是很好，因為它沒有將見面與不見面完全的分開，在演算法中，當然不能憑我們的「感覺」去評價分類結果的好壞。我們需要用一個數去表示。（具體數值代入上面的基尼指數計算公式）

信息增益 vs 信息增益比

Gini 指數 vs 熵

ID3演算法的核心是在決策樹各個結點上對應信息增益准則選擇特徵，遞歸地構建決策樹。

具體方法是：

1）從根結點(root node)開始，對結點計算所有可能的特徵的信息增益，選擇信息增益最大的特徵作為結點的特徵。

2）由該特徵的不同取值建立子節點，再對子結點遞歸地調用以上方法，構建決策樹；直到 所有特徵的信息增益均很小或沒有特徵可以選擇 為止；

3）最後得到一個決策樹。

ID3相當於用 極大似然法進行概率模型的選擇 。

與ID3演算法相似，但是做了改進，將信息增益比作為選擇特徵的標准。

CART 的全稱是分類與回歸樹。從這個名字中就應該知道，CART 既可以用於分類問題，也可以用於回歸問題。

回歸樹中，使用平方誤差最小化准則來選擇特徵並進行劃分。每一個葉子節點給出的預測值，是劃分到該葉子節點的所有樣本目標值的均值，這樣只是在給定劃分的情況下最小化了平方誤差。

要確定最優化分，還需要遍歷所有屬性，以及其所有的取值來分別嘗試劃分並計算在此種劃分情況下的最小平方誤差，選取最小的作為此次劃分的依據。由於回歸樹生成使用平方誤差最小化准則，所以又叫做最小二乘回歸樹。

ID3

熵表示的是數據中包含的信息量大小。熵越小，數據的純度越高，也就是說數據越趨於一致，這是我們希望的劃分之後每個子節點的樣子。

信息增益 = 劃分前熵 - 劃分後熵。信息增益越大，則意味著使用屬性 a 來進行劃分所獲得的 「純度提升」 越大 **。也就是說，用屬性 a 來劃分訓練集，得到的結果中純度比較高。

ID3 僅僅適用於二分類問題。ID3 僅僅能夠處理離散屬性。

C4.5 克服了 ID3 僅僅能夠處理離散屬性的問題，以及信息增益偏向選擇取值較多特徵的問題，使用信息增益比來選擇特徵。 信息增益比 = 信息增益 / 劃分前熵 選擇信息增益比最大的作為最優特徵。

C4.5 處理連續特徵是先將特徵取值排序，以連續兩個值中間值作為劃分標准。嘗試每一種劃分，並計算修正後的信息增益，選擇信息增益最大的分裂點作為該屬性的分裂點。

CART 與 ID3，C4.5 不同之處在於 CART 生成的樹必須是二叉樹 。也就是說，無論是回歸還是分類問題，無論特徵是離散的還是連續的，無論屬性取值有多個還是兩個，內部節點只能根據屬性值進行二分。

決策樹生成演算法遞歸的產生決策樹，直到不能繼續下去為止，這樣產生的樹往往對訓練數據的分類很准確，但對未知測試數據的分類缺沒有那麼精確，即會出現過擬合現象。過擬合產生的原因在於在學習時過多的考慮如何提高對訓練數據的正確分類，從而構建出過於復雜的決策樹，解決方法是考慮決策樹的復雜度，對已經生成的樹進行簡化。

剪枝（pruning）：從已經生成的樹上裁掉一些子樹或葉節點，並將其根節點或父節點作為新的葉子節點，從而簡化分類樹模型。

實現方式：極小化決策樹整體的損失函數或代價函數來實現

決策樹學習的損失函數定義為：

https://www.cnblogs.com/ooon/p/5647309.html

鑒於決策樹容易過擬合的缺點，隨機森林採用多個決策樹的投票機制來改善決策樹，我們假設隨機森林使用了m棵決策樹，那麼就需要產生m個一定數量的樣本集來訓練每一棵樹，如果用全樣本去訓練m棵決策樹顯然是不可取的，全樣本訓練忽視了局部樣本的規律，對於模型的泛化能力是有害的。

產生n個樣本的方法採用Bootstraping法，這是一種有放回的抽樣方法，產生n個樣本。

而最終結果採用Bagging的策略來獲得，即多數投票機制。

隨機森林的生成方法：

1.從樣本集中通過重采樣的方式產生n個樣本

2.假設樣本特徵數目為a，對n個樣本選擇a中的k個特徵，用建立決策樹的方式獲得最佳分割點

3.重復m次，產生m棵決策樹

4.多數投票機制來進行預測

（需要注意的一點是，這里m是指循環的次數，n是指樣本的數目，n個樣本構成訓練的樣本集，而m次循環中又會產生m個這樣的樣本集）

隨機森林是一個比較優秀的模型，在我的項目的使用效果上來看，它對於多維特徵的數據集分類有很高的效率，還可以做特徵重要性的選擇。運行效率和准確率較高，實現起來也比較簡單。 但是在數據噪音比較大的情況下會過擬合，過擬合的缺點對於隨機森林來說還是較為致命的。

機器學習實戰（三）——決策樹 https://blog.csdn.net/jiaoyangwm/article/details/79525237

⑦ 決策樹標簽怎麼分成10類

決策樹標簽分成10類的方法是：使用決策樹構建然後對決策樹進行節點分割來分為10類

步驟1：將所有的數據看成是一個節點，進入步驟2。

步驟2：從所有的數據特徵中挑選一個最優數據特徵對節點進行分割，使得分割後的子集有一個在當前條件下最好的分類，進入步驟3。

步驟3：生成若干孩子節點，對每一個孩子節點進行判斷，如果滿足停止分裂的條件，進入步驟4否則，進入步驟2。

步驟4：設置該節點是子節點，其輸出的結果為該節點數量佔比最大的類別。

決策樹的特點是：

優點：計算復雜度不高，輸出結果易於理解，對中間值的缺失不敏感，可以處理不相關特徵數據。

缺點：可能會產生過度匹配的問題（需要剪枝）。 適用數據類型：數值型和標稱型。

決策樹在對中間節點進行分裂的時候，是選擇最優分裂結果的屬性進行分裂，決策樹使用信息增益或者信息增益率作為選擇屬性的依據。

信息增益表示劃分數據前後信息發生的變化，獲得信息增益最高的特徵就是最好的選擇。

⑧ 決策樹法的步驟

決策樹法的幾個關鍵步驟是：

1、畫出決策樹，畫決策樹的過程也就是對未來可能發生的各種事件進行周密思考、預測的過程，把這些情況用樹狀圖表示出來．先畫決策點，再找方案分枝和方案點．最後再畫出概率分枝。

(8)決策樹的分裂演算法擴展閱讀

決策樹的優點

1、決策樹易於理解和實現. 人們在通過解釋後都有能力去理解決策樹所表達的意義。

2、對於決策樹，數據的准備往往是簡單或者是不必要的 . 其他的技術往往要求先把數據一般化，比如去掉多餘的或者空白的屬性。

3、能夠同時處理數據型和常規型屬性。其他的技術往往要求數據屬性的單一。

4、 在相對短的時間內能夠對大型數據源做出可行且效果良好的結果。

5、對缺失值不敏感

6、可以處理不相關特徵數據

7、效率高，決策樹只需要一次構建，反復使用，每一次預測的最大計算次數不超過決策樹的深度。

決策樹的缺點

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

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

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

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

5、在處理特徵關聯性比較強的數據時表現得不是太好

⑨ 決策樹法分為那幾個步驟

1、特徵選擇

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

2、決策樹生成

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

3、決策樹剪枝

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

【簡介】

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

⑩ 決策樹演算法原理是什麼

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

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

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

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

(10)決策樹的分裂演算法擴展閱讀：

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

（1）分類精度高；

（2）生成的模式簡單；

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

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