id3演算法c

① 決策樹原理及演算法比較

決策樹是什麼？

    和線性回歸一樣是一種模型，內部節點和葉節點。實現分類，內部節點和葉節點通過有向線（分類規      則）連接起來

決策樹的目標是什麼？

    決策樹通過對數據復雜度的計算，建立特徵分類標准，確定最佳分類特徵。

    表現為「熵」（entropy）和信息增益（information gain），基於決策樹思想的三種演算法：ID3，C4.5,CART演算法，三種演算法的信息衡量的指標也不同.

    熵來表示信息的復雜度，熵越大，信息也就越復雜，公式如下：

那些演算法能夠實現決策樹？

    在決策樹構建過程中，什麼是比較重要的。特徵選擇（按照熵變計算），演算法產生最重要的部分，

決策樹中葉節點的分類比較純，

節點順序的排列規則：

熵變：

數據的預處理：

改進思路一般有兩個1，換演算法；2，調參數

做好數據的預處理：

1，做好特徵選擇；

2，做好數據離散化、異常值處理、缺失填充

分類器：

在決策樹中，從根到達任意一個葉節點的之間最長路徑的長度，表示對應的演算法排序中最壞情況下的比較次數。這樣一個比較演算法排序中的最壞情況的比較次數就與其決策樹的高度相同，同時如果決策樹中每種排列以可達葉子的形式出現，那麼關於其決策樹高度的下界也就是關於比較排序演算法運行時間的下界，

ID3演算法存在的缺點：

    1，ID3演算法在選擇根節點和內部節點分支屬性時，採用信息增益作為評價標准。信息增益的缺點是傾向於選擇取值較多的屬性

    2，當數據為連續性變數的時候，ID3演算法就不是一個合理的演算法的模型了

C4.5信息增益比率，

     1，在信息增益的基礎上除以split-info，是將信息增益改為信息增益比，以解決取值較多的屬性的問題，另外它還可以處理連續型屬性，其判別標準是θ，

      2，C4.5演算法利用增益/熵值，克服了樹生長的過程中，總是『貪婪』選擇變數分類多的進行分類

      3，處理來內需型變數，C4.5的分類樹的分支就是兩條

衡量指標：

（1）信息增益

基於ID3演算法的信息增益對於判定連續型變數的時候病不是最優選擇，C4.5演算法用了信息增益率這個概念。

分類信息類的定義如下：

這個值表示將訓練數據集D劃分成對應屬性A測試的V個輸出v個劃分產生的信息，信息增益率定義為：

選擇最大信息增益率的屬性作為分裂屬性

Gini指標，CART

表明樣本的「純凈度」。Gini系數避免了信息增益產生的問題，

過擬合問題，非常好的泛化能力，有很好的推廣能力

Gini系數的計算：

在分類問題中，假設有k個類，樣本點屬於第k類的概率為Pk，則概率分布的gini指數的定義為：

如果樣本集合D根據某個特徵A被分割為D1，D2兩個部分，那麼在特徵A的提哦啊見下，集合D的gini指數的定義為：

Gini指數代表特徵A不同分組下的數據集D的不確定性，gini指數越大，樣本集合的不確定性也就越大，這一點和熵的概念相類似

決策樹原理介紹：

第三步：對於每個屬性執行劃分：

（1）該屬性為離散型變數

記樣本中的變數分為m中

窮舉m種取值分為兩類的劃分

對上述所有劃分計算GINI系數

（2）該屬性為連續型變數

將數據集中從小到大劃分

按順序逐一將兩個相臨值的均值作為分割點

對上述所有劃分計算GINI系數

學歷的劃分使得順序的劃分有個保證，化為連續型變數處理。

決策樹的生成演算法分為兩個步驟：

預剪枝和後剪枝  CCP（cost and complexity）演算法：在樹變小和變大的的情況有個判斷標准。誤差率增益值：α值為誤差的變化

決策樹的終止條件：

      1，某一個節點的分支所覆蓋的樣本都是同一類的時候

      2，某一個分支覆蓋的樣本的個數如果小於一個閾值，那麼也可以產生葉子節點，從而終止Tree-Growth

確定葉子結點的類：

      1，第一種方式，葉子結點覆蓋的樣本都屬於同一類

      2， 葉子節點覆蓋的樣本未必是同一類，所佔的大多數，那麼該葉子節點的類別就是那個佔大多數的類

② 【理論篇】決策樹演算法 - 信息增益率、GINI系數

ID3 決策樹演算法在特徵選擇時存在什麼問題呢？

我們來舉個例子：數據集 A 存在一個非常稀疏的特徵 ID 列，我們知道 ID 是唯一不重復的，種類自然就會非常龐大。

這個時候，如果我們使用 ID 去切分數據集，那切分到最後，每個樣本都會被分配到單獨的樣子結點上，每個樣子結點的數據只有一樣，不確定性為 0 ，熵值也為 0 。

那這樣是不是就說名 ID 這個特徵非常好呢？根據 ID 就能預測標簽？當然不是，實際上 ID 這個特徵毫無意義。

小魚這里拿 ID 舉例，只是個極端的例子。但足以說明，對於類似 ID 這樣數據種類非常多，分布非常稀疏的特徵來說，ID3 決策樹演算法通過信息增益來選取結點特徵是遠遠不夠的。

為了解決 ID3 決策樹演算法的問題，我們引入了信息增益率，計算信息增益時，考慮特徵分布的自身熵。

C4.5 決策樹演算法使用信息增益率來衡量特徵節點的分類能力。所謂信息增益率就是在信息增益的基礎上除以該特徵自身的熵值計算而來。

為什麼要除以特徵自身的熵值呢？我們舉個例子：還是剛才的 ID 特徵，ID 特徵切分完數據後的熵值為 0 ，原始數據集的熵值為 G，特徵 ID 的熵值為 -n*(1/n)*log(1/n) = -log(1/n) 其中 n 為數據集樣本的個數。因此，特徵 ID 的熵 G2 是一個非常龐大的數值。

使用 ID 節點切分數據集之後，得到的信息增益為：G - 0 = G，信息增益非常大，分類效果堪稱完美。但如果使用信息增益率去衡量，則：(G - 0)/G2，其中 G2 一定是遠遠大於 G 的，因為很顯然標簽的混亂層度遠低於 ID 列的混亂層度。

因此，我們求得的信息增益率就是一個非常小的值了，這個時候就可以發現 ID 這個特徵分類效果非常差。也因此 C4.5 演算法很好地解決了 ID3 演算法對稀疏特徵衡量的不足。

GINI 系數和熵的衡量標准類似，只是計算方式不同。GINI 系數的公式為：

當概率 P 為 0 或者 1 時，此時沒有不確定性。其中概率為 1 時，GINI系數為 0 ，概率為 0 時，GINI 系數也為 0 。

③ C4.5演算法

C4.5是一系列用在機器學習和數據挖掘的分類問題中的演算法。它的目標是監督學習：給定一個數據集，其中的每一個元組都能用一組屬性值來描述，每一個元組屬於一個互斥的類別中的某一類。C4.5的目標是通過學習，找到一個從屬性值到類別的映射關系，並且這個映射能用於對新的類別未知的實體進行分類。
C4.5由J.Ross Quinlan在ID3的基礎上提出的。ID3演算法用來構造決策樹。決策樹是一種類似流程圖的樹結構，其中每個內部節點（非樹葉節點）表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個樹葉節點存放一個類標號。一旦建立好了決策樹，對於一個未給定類標號的元組，跟蹤一條有根節點到葉節點的路徑，該葉節點就存放著該元組的預測。決策樹的優勢在於不需要任何領域知識或參數設置，適合於探測性的知識發現。

決策樹呈樹形結構，在分類問題中，表示基於特徵對實例進行分類的過程。學習時，利用訓練數據，根據損失函數最小化的原則建立決策樹模型；預測時，對新的數據，利用決策模型進行分類。

決策樹是一種通過對特徵屬性的分類對樣本進行分類的樹形結構，包括有向邊以及三類節點：

上圖給出了（二叉）決策樹的示例。決策樹具有以下特點：

決策樹學習的本質是從訓練集中歸納出一組分類規則。但隨著分裂屬性次序的不同，所得到的決策樹也會不同。如何得到一棵決策樹既對訓練數據有較好的擬合，又對未知數據有很好的預測呢？

首先，我們要解決兩個問題：

一般的，一顆決策樹包含一個根節點、若干個內部結點和若干個葉結點；葉結點則對應於一個屬性冊書；每個葉結點包含的樣本集合根據屬性測試的結果被劃分到子結點中；根結點包含樣本全集，從根結點到每個葉結點的路徑對飲過了一個判定測試序列。決策樹學習的目的是為了產生一顆泛化能力強的決策樹，其基本流程遵循簡單且只管的「分而治之」（divide-and-conquer）策略，如下圖所示：

顯然，決策樹的生成是一個遞歸的過程。在決策樹基本演算法中，有三種情形會導致遞歸返回：

在第二種情形下，我們把當前結點標記為葉結點，並且將其類別設定為該結點所含樣本最多的類別；在第三種情形下，同樣把當前結點標記為葉結點，但將其類別設定為其父結點所含樣本最多類別。注意這兩種情形的處理實質不同：情形二是在利用當前結點的後驗分布，而情形三則是把父結點的樣本分布當做當前結點的先驗分布。

決策樹學習的關鍵在於如何選擇最優劃分屬性。一般而言，隨著劃分過程的不斷進行，我們希望決策樹的分支結點所包含的樣本盡可能屬於同一類別，即結點的「純度」越來越高。

「信息熵」（information entropy）是度量樣本集合純度最常用的一種指標。假定當前樣本集合 中第k類樣本所佔比例為 ，則 的信息熵定義為

的值越小，則 的純度越高。
假定離散屬性 有 個可能的取值 ,若使用 來對樣本集合 進行劃分，則會產生 個分支結點，其中第v個分支結點包含了 中所有在屬性 上取值為 的樣本，記為 ，我們根據上述公式計算出 的信息熵，再考慮到不同的分支結點所包含的樣本數不同，給分支結點賦予權重 ，即樣本越多的分支結點影響越大，於是可以計算出用屬性 對樣本集合 進行劃分所獲得的"信息增益"（information gain）

一般而言，信息增益越大，則意味著使用屬性a來進行劃分所獲得的「純度提升越大」。因此，我們可用信息增益來進行決策樹的劃分屬性選擇。

實際上，信息增益准則對可取值數目較多的屬性有所偏好（如何以序號作為劃分屬性，每一個事物作為一個單獨存在的類別的時候，信息增益往往會很高，但是這樣進行劃分並沒有什麼意義），為了減少這種偏好可能帶來的不利影響，著名的C4.5演算法並不是直接使用信息增益，而是使用增益率（gain ratio）來選擇最優的劃分屬性。增益率的定義為：

值得注意的是： 增益率准則對可取值數目較少的屬性有所偏好，因此C4.5演算法並不是直接選擇增益率最大的候選劃分屬性，而是使用了一個啟發式： 先從候選劃分屬性中找出信息增益高於平均水平的屬性，再從中選擇增益率最高的

CART決策樹使用「基尼指數」來選擇劃分屬性。數據集 的純度可用基尼值來度量：

直觀來說， 反映了從數據集 中隨機抽取兩個樣本，其類別標記不一致的概率，因此 值越小，則數據集 的純度就越高。屬性 的基尼指數定義為：

於是，我們在候選屬性集合 中，選擇那個使得劃分後基尼指數最小的屬性作為最優劃分屬性，即

銀行希望能夠通過一個人的信息（包括職業、年齡、收入、學歷）去判斷他是否有貸款的意向，從而更有針對性地完成工作。下表是銀行現在能夠掌握的信息，我們的目標是通過對下面的數據進行分析建立一個預測用戶貸款一下的模型。

上表中有4個客戶的屬性，如何綜合利用這些屬性去判斷用戶的貸款意向？決策樹的做法是每次選擇一個屬性進行判斷，如果不能得出結論，繼續選擇其他屬性進行判斷，直到能夠「肯定地」判斷出用戶的類型或者是上述屬性都已經使用完畢。比如說我們要判斷一個客戶的貸款意向，我們可以先根據客戶的職業進行判斷，如果不能得出結論，再根據年齡作判斷，這樣以此類推，直到可以得出結論為止。決策樹用樹結構實現上述的判斷流程，如圖所示：

以熵作為節點復雜度的統計量，分別求出下面例子的信息增益，圖3.1表示節點選擇屬性1進行分裂的結果，圖3.2表示節點選擇屬性2進行分裂的結果，通過計算兩個屬性分裂後的信息增益，選擇最優的分裂屬性。

屬性一

屬性二

由於 ，所以屬性1是比屬性2更優的分裂屬性，故而選擇屬性1作為分裂屬性。

由於 ，故而選擇屬性2作為分裂屬性。

剪枝（pruning）是決策樹學習演算法對付「過擬合」的主要手段。在決策樹學習中，為了盡可能正確分類訓練樣本，結點劃分過程將不斷重復，有事會造成決策樹分支過多，這是就可能因為訓練樣本學得太好了，以致把訓練集自身的一些特點黨組喲所有數據都具有的一般性質而導致過擬合。因此，可通過主動去掉一些分支來降低過擬合的風險。

其中{1,2,3,6,7,10,14,15,16,17}為測試集，{4,5,8,9,11,12,13}為訓練集。

預剪枝是要對劃分前後泛化性能進行評估。對比決策樹某節點生成前與生成後的泛化性能。

2.計算訓練集的信息增益，得知臍部的信息增益最大，因此按照臍部進行劃分。又因為在訓練集中，凹陷特徵好瓜的佔比多，因此凹陷劃分為好瓜，稍凹特徵好過佔比多，因此將其標記為好瓜，因此按照臍部劃分的子樹結果如下：

劃分後，對比結果如下：

由圖可知，預剪枝使得很多分支沒有展開，這不僅降低了過擬合的風險，還顯著減少了決策樹的訓練時間開銷和測試時間。但是，有些分支雖當前不能提升泛化性。甚至可能導致泛化性暫時降低，但在其基礎上進行後續劃分卻有可能導致顯著提高，因此預剪枝的這種貪心本質，給決策樹帶來了欠擬合的風險。

後剪枝表示先從訓練集中生成一顆完整決策樹。

對比標記節點的劃分類與各數據的真實分類，計算準確率，如下表所示：

生成的決策樹，在驗證集上的准確度為3/7*100%=42.9%.

對比預剪枝與後剪枝生成的決策樹，可以看出，後剪枝通常比預剪枝保留更多的分支，其欠擬合風險很小，因此後剪枝的泛化性能往往由於預剪枝決策樹。但後剪枝過程是從底往上裁剪，因此其訓練時間開銷比前剪枝要大。

④ 決策樹演算法的典型演算法

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

⑤ 數據挖掘的十大經典演算法，總算是講清楚了，想提升自己的趕快收藏

一個優秀的數據分析師，除了要掌握基本的統計學、數據分析思維、數據分析工具之外，還需要掌握基本的數據挖掘思想，幫助我們挖掘出有價值的數據，這也是數據分析專家和一般數據分析師的差距所在。

國際權威的學術組織the IEEE International Conference on Data Mining (ICDM) 評選出了數據挖掘領域的十大經典演算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART.

不僅僅是選中的十大演算法，其實參加評選的18種演算法，實際上隨便拿出一種來都可以稱得上是經典演算法，它們在數據挖掘領域都產生了極為深遠的影響。今天主要分享其中10種經典演算法，內容較干，建議收藏備用學習。

1. C4.5

C4.5演算法是機器學習演算法中的一種分類決策樹演算法,其核心演算法是ID3演算法. C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：

1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；

2) 在樹構造過程中進行剪枝；

3) 能夠完成對連續屬性的離散化處理；

4) 能夠對不完整數據進行處理。

C4.5演算法有如下優點：產生的分類規則易於理解，准確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致演算法的低效（相對的CART演算法只需要掃描兩次數據集，以下僅為決策樹優缺點）。

2. The k-means algorithm 即K-Means演算法

k-means algorithm演算法是一個聚類演算法，把n的對象根據他們的屬性分為k個分割，k < n。它與處理混合正態分布的最大期望演算法很相似，因為他們都試圖找到數據中自然聚類的中心。它假設對象屬性來自於空間向量，並且目標是使各個群組內部的均 方誤差總和最小。

3. Support vector machines

支持向量機，英文為Support Vector Machine，簡稱SV機（論文中一般簡稱SVM）。它是一種監督式學習的方法，它廣泛的應用於統計分類以及回歸分析中。支持向量機將向量映射到一個更 高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。一個極好的指南是C.J.C Burges的《模式識別支持向量機指南》。van der Walt 和 Barnard 將支持向量機和其他分類器進行了比較。

4. The Apriori algorithm

Apriori演算法是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法。其核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這里，所有支持度大於最小支持度的項集稱為頻繁項集，簡稱頻集。

5. 最大期望(EM)演算法

在統計計算中，最大期望（EM，Expectation–Maximization）演算法是在概率（probabilistic）模型中尋找參數最大似然 估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variabl）。最大期望經常用在機器學習和計算機視覺的數據集聚（Data Clustering）領域。

6. PageRank

PageRank是Google演算法的重要內容。2001年9月被授予美國專利，專利人是Google創始人之一拉里·佩奇（Larry Page）。因此，PageRank里的page不是指網頁，而是指佩奇，即這個等級方法是以佩奇來命名的。

PageRank根據網站的外部鏈接和內部鏈接的數量和質量倆衡量網站的價值。PageRank背後的概念是，每個到頁面的鏈接都是對該頁面的一次投票， 被鏈接的越多，就意味著被其他網站投票越多。這個就是所謂的「鏈接流行度」——衡量多少人願意將他們的網站和你的網站掛鉤。PageRank這個概念引自 學術中一篇論文的被引述的頻度——即被別人引述的次數越多，一般判斷這篇論文的權威性就越高。

7. AdaBoost

Adaboost是一種迭代演算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然後把這些弱分類器集合起來，構成一個更強的最終分類器 (強分類器)。其演算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的准確率，來確定每個樣本的權 值。將修改過權值的新數據集送給下層分類器進行訓練，最後將每次訓練得到的分類器最後融合起來，作為最後的決策分類器。

8. kNN: k-nearest neighbor classification

K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。

9. Naive Bayes

在眾多的分類模型中，應用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型（Naive Bayesian Model，NBC）。 樸素貝葉斯模型發源於古典數學理論，有著堅實的數學基礎，以及穩定的分類效率。

同時，NBC模型所需估計的參數很少，對缺失數據不太敏感，演算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。 但是實際上並非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬 性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關性較小時，NBC模型的性能最為良好。

10. CART: 分類與回歸樹

CART, Classification and Regression Trees。 在分類樹下面有兩個關鍵的思想。第一個是關於遞歸地劃分自變數空間的想法（二元切分法）；第二個想法是用驗證數據進行剪枝（預剪枝、後剪枝）。在回歸樹的基礎上的模型樹構建難度可能增加了，但同時其分類效果也有提升。

參考書籍：《機器學習實戰》

⑥ 用python實現紅酒數據集的ID3,C4.5和CART演算法

ID3演算法介紹
ID3演算法全稱為迭代二叉樹3代演算法（Iterative Dichotomiser 3）
該演算法要先進行特徵選擇，再生成決策樹，其中特徵選擇是基於「信息增益」最大的原則進行的。
但由於決策樹完全基於訓練集生成的，有可能對訓練集過於「依賴」，即產生過擬合現象。因此在生成決策樹後，需要對決策樹進行剪枝。剪枝有兩種形式，分別為前剪枝（Pre-Pruning）和後剪枝（Post-Pruning），一般採用後剪枝。
信息熵、條件熵和信息增益
信息熵：來自於香農定理，表示信息集合所含信息的平均不確定性。信息熵越大，表示不確定性越大，所含的信息量也就越大。
設x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x
1

,x
2

,x
3

,...x
n

為信息集合X的n個取值，則x i x_ix
i

的概率：
P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n
P(X=i)=p
i

,i=1,2,3,...,n

信息集合X的信息熵為：
H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}
H(X)=−
i=1
∑
n

p
i

logp
i

條件熵：指已知某個隨機變數的情況下，信息集合的信息熵。
設信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y
1

,y
2

,y
3

,...y
m

組成的隨機變數集合Y，則隨機變數（X，Y）的聯合概率分布為
P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}
P(x=i,y=j)=p
ij

條件熵：
H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}
H(X∣Y)=
j=1
∑
m

p(y
j

)H(X∣y
j

)
由
H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ⁡ p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}
H(X∣y
j

)=−
j=1
∑
m

p(y
j

)
i=1
∑
n

p(x
i

∣y
j

)logp(x
i

∣y
j

)
和貝葉斯公式：
p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)
p(x
i

y
j

)=p(x
i

∣y
j

)p(y
j

)
可以化簡條件熵的計算公式為:
H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ⁡ p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}
H(X∣Y)=
j=1
∑
m

i=1
∑
n

p(x
i

,y
j

)log
p(x
i

,y
j

)
p(x
i

)

信息增益：信息熵-條件熵，用於衡量在知道已知隨機變數後，信息不確定性減小越大。
d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)
d(X,Y)=H(X)−H(X∣Y)

python代碼實現
import numpy as np
import math

def calShannonEnt(dataSet):
""" 計算信息熵 """
labelCountDict = {}
for d in dataSet:
label = d[-1]
if label not in labelCountDict.keys():
labelCountDict[label] = 1
else:
labelCountDict[label] += 1
entropy = 0.0
for l, c in labelCountDict.items():
p = 1.0 * c / len(dataSet)
entropy -= p * math.log(p, 2)
return entropy

def filterSubDataSet(dataSet, colIndex, value):
"""返回colIndex特徵列label等於value，並且過濾掉改特徵列的數據集"""
subDataSetList = []
for r in dataSet:
if r[colIndex] == value:
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
subDataSetList.append(newR)
return np.array(subDataSetList)

def chooseFeature(dataSet):
""" 通過計算信息增益選擇最合適的特徵"""
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeatureIndex = -1
for i in range(featureNum):
uniqueValues = np.unique(dataSet[:, i])
condition_entropy = 0.0

for v in uniqueValues: #計算條件熵
subDataSet = filterSubDataSet(dataSet, i, v)
p = 1.0 * len(subDataSet) / len(dataSet)
condition_entropy += p * calShannonEnt(subDataSet)
infoGain = entropy - condition_entropy #計算信息增益

if infoGain >= bestInfoGain: #選擇最大信息增益
bestInfoGain = infoGain
bestFeatureIndex = i
return bestFeatureIndex

def creatDecisionTree(dataSet, featNames):
""" 通過訓練集生成決策樹 """
featureName = featNames[:] # 拷貝featNames，此處不能直接用賦值操作，否則新變數會指向舊變數的地址
classList = list(dataSet[:, -1])
if len(set(classList)) == 1: # 只有一個類別
return classList[0]
if dataSet.shape[1] == 1: #當所有特徵屬性都利用完仍然無法判斷樣本屬於哪一類，此時歸為該數據集中數量最多的那一類
return max(set(classList), key=classList.count)

bestFeatureIndex = chooseFeature(dataSet) #選擇特徵
bestFeatureName = featNames[bestFeatureIndex]
del featureName[bestFeatureIndex] #移除已選特徵列
decisionTree = {bestFeatureName: {}}

featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已選特徵列所包含的類別， 通過遞歸生成決策樹
for v in featureValueUnique:
FeatureName = featureName[:]
subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, FeatureName)
return decisionTree

def classify(decisionTree, featnames, featList):
""" 使用訓練所得的決策樹進行分類 """
classLabel = None
root = decisionTree.keys()[0]
firstGenDict = decisionTree[root]
featIndex = featnames.index(root)
for k in firstGenDict.keys():
if featList[featIndex] == k:
if isinstance(firstGenDict[k], dict): #若子節點仍是樹，則遞歸查找
classLabel = classify(firstGenDict[k], featnames, featList)
else:
classLabel = firstGenDict[k]
return classLabel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
下面用鳶尾花數據集對該演算法進行測試。由於ID3演算法只能用於標稱型數據，因此用在對連續型的數值數據上時，還需要對數據進行離散化，離散化的方法稍後說明，此處為了簡化，先使用每一種特徵所有連續性數值的中值作為分界點，小於中值的標記為1，大於中值的標記為0。訓練1000次，統計准確率均值。

from sklearn import datasets
from sklearn.model_selection import train_test_split

iris = datasets.load_iris()
data = np.c_[iris.data, iris.target]

scoreL = []
for i in range(1000): #對該過程進行10000次
trainData, testData = train_test_split(data) #區分測試集和訓練集

featNames = iris.feature_names[:]
for i in range(trainData.shape[1] - 1): #對訓練集每個特徵，以中值為分界點進行離散化
splitPoint = np.mean(trainData[:, i])
featNames[i] = featNames[i]+'<='+'{:.3f}'.format(splitPoint)
trainData[:, i] = [1 if x <= splitPoint else 0 for x in trainData[:, i]]
testData[:, i] = [1 if x <= splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
print 'score: ', np.mean(scoreL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
輸出結果為：score: 0.7335，即准確率有73%。每次訓練和預測的准確率分布如下：

數據離散化
然而，在上例中對特徵值離散化的劃分點實際上過於「野蠻」，此處介紹一種通過信息增益最大的標准來對數據進行離散化。原理很簡單，當信息增益最大時，說明用該點劃分能最大程度降低數據集的不確定性。
具體步驟如下：

對每個特徵所包含的數值型特徵值排序
對相鄰兩個特徵值取均值，這些均值就是待選的劃分點
用每一個待選點把該特徵的特徵值劃分成兩類，小於該特徵點置為1， 大於該特徵點置為0，計算此時的條件熵，並計算出信息增益
選擇信息使信息增益最大的劃分點進行特徵離散化
實現代碼如下：

def filterRawData(dataSet, colIndex, value, tag):
""" 用於把每個特徵的連續值按照區分點分成兩類，加入tag參數，可用於標記篩選的是哪一部分數據"""
filterDataList = []
for r in dataSet:
if (tag and r[colIndex] <= value) or ((not tag) and r[colIndex] > value):
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
filterDataList.append(newR)
return np.array(filterDataList)

def dataDiscretization(dataSet, featName):
""" 對數據每個特徵的數值型特徵值進行離散化 """
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)

for featIndex in range(featureNum): #對於每一個特徵
uniqueValues = sorted(np.unique(dataSet[:, featIndex]))
meanPoint = []

for i in range(len(uniqueValues) - 1): # 求出相鄰兩個值的平均值
meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)
bestInfoGain = 0.0
bestMeanPoint = -1
for mp in meanPoint: #對於每個劃分點
subEntropy = 0.0 #計算該劃分點的信息熵
for tag in range(2): #分別劃分為兩類
subDataSet = filterRawData(dataSet, featIndex, mp, tag)
p = 1.0 * len(subDataSet) / len(dataSet)
subEntropy += p * calShannonEnt(subDataSet)

## 計算信息增益
infoGain = entropy - subEntropy
## 選擇最大信息增益
if infoGain >= bestInfoGain:
bestInfoGain = infoGain
bestMeanPoint = mp
featName[featIndex] = featName[featIndex] + "<=" + "{:.3f}".format(bestMeanPoint)
dataSet[:, featIndex] = [1 if x <= bestMeanPoint else 0 for x in dataSet[:, featIndex]]
return dataSet, featName
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
重新對數據進行離散化，並重復該步驟1000次，同時用sklearn中的DecisionTreeClassifier對相同數據進行分類，分別統計平均准確率。運行代碼如下:

from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
scoreL = []
scoreL_sk = []
for i in range(1000): #對該過程進行1000次
featNames = iris.feature_names[:]
trainData, testData = train_test_split(data) #區分測試集和訓練集
trainData_tmp = .(trainData)
testData_tmp = .(testData)
discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根據信息增益離散化
for i in range(testData.shape[1]-1): #根據測試集的區分點離散化訓練集
splitPoint = float(discritizationFeatName[i].split('<=')[-1])
testData[:, i] = [1 if x<=splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

clf = DecisionTreeClassifier('entropy')
clf.fit(trainData[:, :-1], trainData[:, -1])
clf.predict(testData[:, :-1])
scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))

print 'score: ', np.mean(scoreL)
print 'score-sk: ', np.mean(scoreL_sk)
fig = plt.figure(figsize=(10, 4))
plt.subplot(1,2,1)
pd.Series(scoreL).hist(grid=False, bins=10)
plt.subplot(1,2,2)
pd.Series(scoreL_sk).hist(grid=False, bins=10)
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
兩者准確率分別為：
score: 0.7037894736842105
score-sk: 0.7044736842105263

准確率分布如下：

兩者的結果非常一樣。
（但是。。為什麼根據信息熵離散化得到的准確率比直接用均值離散化的准確率還要低啊？？哇的哭出聲。。）

最後一次決策樹圖形如下：

決策樹剪枝
由於決策樹是完全依照訓練集生成的，有可能會有過擬合現象，因此一般會對生成的決策樹進行剪枝。常用的是通過決策樹損失函數剪枝，決策樹損失函數表示為:
C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|
C
a

(T)=
t=1
∑
T

N
t

H
t

(T)+α∣T∣

其中，H t ( T ) H_t(T)H
t

(T)表示葉子節點t的熵值，T表示決策樹的深度。前項∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑
t=1
T

N
t

H
t

(T)是決策樹的經驗損失函數當隨著T的增加，該節點被不停的劃分的時候，熵值可以達到最小，然而T的增加會使後項的值增大。決策樹損失函數要做的就是在兩者之間進行平衡，使得該值最小。
對於決策樹損失函數的理解，如何理解決策樹的損失函數? - 陶輕松的回答 - 知乎這個回答寫得挺好，可以按照答主的思路理解一下

C4.5演算法
ID3演算法通過信息增益來進行特徵選擇會有一個比較明顯的缺點：即在選擇的過程中該演算法會優先選擇類別較多的屬性（這些屬性的不確定性小，條件熵小，因此信息增益會大），另外，ID3演算法無法解決當每個特徵屬性中每個分類都只有一個樣本的情況（此時每個屬性的條件熵都為0）。
C4.5演算法ID3演算法的改進，它不是依據信息增益進行特徵選擇，而是依據信息增益率，它添加了特徵分裂信息作為懲罰項。定義分裂信息：
S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ⁡ ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}
SplitInfo(X,Y)=−
i
∑
n

∣X∣
∣X
i

∣

log
∣X∣
∣X
i

∣

則信息增益率為：
G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}
GainRatio(X,Y)=
SplitInfo(X,Y)
d(X,Y)

關於ID3和C4.5演算法
在學習分類回歸決策樹演算法時，看了不少的資料和博客。關於這兩個演算法，ID3演算法是最早的分類演算法，這個演算法剛出生的時候其實帶有很多缺陷：

無法處理連續性特徵數據
特徵選取會傾向於分類較多的特徵
沒有解決過擬合的問題
沒有解決缺失值的問題
即該演算法出生時是沒有帶有連續特徵離散化、剪枝等步驟的。C4.5作為ID3的改進版本彌補列ID3演算法不少的缺陷：

通過信息最大增益的標准離散化連續的特徵數據
在選擇特徵是標准從「最大信息增益」改為「最大信息增益率」
通過加入正則項系數對決策樹進行剪枝
對缺失值的處理體現在兩個方面：特徵選擇和生成決策樹。初始條件下對每個樣本的權重置為1。
特徵選擇：在選取最優特徵時，計算出每個特徵的信息增益後，需要乘以一個**「非缺失值樣本權重占總樣本權重的比例」**作為系數來對比每個特徵信息增益的大小
生成決策樹：在生成決策樹時，對於缺失的樣本我們按照一定比例把它歸屬到每個特徵值中，比例為該特徵每一個特徵值占非缺失數據的比重
關於C4.5和CART回歸樹
作為ID3的改進版本，C4.5克服了許多缺陷，但是它自身還是存在不少問題：

C4.5的熵運算中涉及了對數運算，在數據量大的時候效率非常低。
C4.5的剪枝過於簡單
C4.5隻能用於分類運算不能用於回歸
當特徵有多個特徵值是C4.5生成多叉樹會使樹的深度加深
————————————————
版權聲明：本文為CSDN博主「Sarah Huang」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/weixin_44794704/article/details/89406612

⑦ 決策樹演算法基礎 ID3與C4.5

決策樹演算法基礎：ID3與C4.5
設X是一個取有限個值得離散隨機變數，其概率分布為P(X=xi)=pi, i=1,2,…,n。則隨機變數X的信息熵為
條件熵H(Y|X)表示在已知隨機變數X的條件下隨機變數Y的不確定性。H(Y|X)的計算公式為
所以決策樹分支後信息總熵H(D|A)=P1*H1+P2*H2+...+Pn*Hn,(特徵A條件下D的經驗條件熵)
所以信息增益ΔH=H(D)-H(D|A)
H(D|A)越小，ΔH越大，該特徵A越適合作為當前的決策節點。
選取最佳特徵偽代碼：
計算信息總熵H(D)
遍歷每一個特徵下的關於D的經驗條件熵H(D|A)
計算每一個特徵的信息增益ΔH
將信息增益ΔH最大的特徵作為最佳特徵選為當前決策節點
ID3演算法偽代碼：
如果第一個標簽的數量等於所有的標簽數量，說明這是一個單節點樹，返回這個標簽作為該節點類
如果特徵只有一個，說明這是一個單節點樹，用多數表決法投票選出標簽返回作為該節點類
否則，按信息增益最大的特徵A作為當前決策節點，即決策樹父節點
如果該特徵的信息增益ΔH小於閾值，則用多數表決法投票選出標簽返回作為該節點類
否則，對於該特徵A的每一個可能值ai，將原空間D分割為若干個子空間Di
對於若干個非空子集Di，將每個Di中實例數最大的類作為標記，構建子節點
以Di為訓練空間，遞歸調用上述步驟
由於信息增益存在偏向於選擇取值較多的特徵的問題，而C4.5演算法中，將ID3演算法里的信息增益換成信息增益比，較好地解決了這個問題。
決策樹的優點在於計算量簡單，適合有缺失屬性值的樣本，適合處理不相關的特徵。而缺點是容易過擬合，可以通過剪枝來簡化模型，另外隨機森林也解決了這個問題。