id3演算法決策樹

❶ 決策樹演算法原理

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

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

一棵決策樹的生成過程主要分為以下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）

決策樹是一種非參數有監督的機器學習方法，可以用於解決回歸問題和分類問題。通過學習已有的數據，計算得出一系列推斷規則來預測目標變數的值，並用類似流程圖的形式進行展示。決策樹模型可以進行可視化，具有很強的可解釋性，演算法容易理解，以決策樹為基礎的各種集成演算法在很多領域都有廣泛的應用。

熵的概念最早起源於物理學，用於度量一個熱力學系統的無序程度。在資訊理論裡面，信息熵代表著一個事件或一個變數等所含有的信息量。 在信息世界，熵越高，則能傳輸越多的信息，熵越低，則意味著傳輸的信息越少。

發生概率低的事件比發生概率高的事件具有更大的不確定性，需要更多的信息去描述他們，信息熵更高。

我們可以用計算事件發生的概率來計算事件的信息，又稱「香農信息」（ Shannon Information ）。一個離散事件x的信息可以表示為：
h(x) = -log(p(x))
p() 代表事件x發生的概率， log() 為以二為底的對數函數，即一個事件的信息量就是這個事件發生的概率的負對數。選擇以二為底的對數函數代表計算信息的單位是二進制。因為概率p(x)小於1，所以負號就保證了信息熵永遠不為負數。當事件的概率為1時，也就是當某事件百分之百發生時，信息為0。

熵（ entropy ），又稱「香農熵」（ Shannon entropy ），表示一個隨機變數的分布所需要的平均比特數。一個隨機變數的信息熵可以表示為：
H(x) = -sum(each k in K p(k)log(p(k)))
K表示變數x所可能具有的所有狀態（所有事件），將發生特定事件的概率和該事件的信息相乘，最後加和，即可得到該變數的信息熵。可以理解為，信息熵就是平均而言發生一個事件我們得到的信息量大小。所以數學上，信息熵其實是事件信息量的期望。

當組成該隨機變數的一個事件的概率為1時信息熵最小，為0， 即該事件必然發生。當組成該隨機變數的所有事件發生的概率相等時，信息熵最大，即完全不能判斷那一個事件更容易發生，不確定性最大。

當一個事件主導時，比如偏態分布（ Skewed Probability Distribution ），不確定性減小，信息熵較低（low entropy）；當所有事件發生概率相同時，比如均衡分布（ Balanced Probability Distribution ），不確定性極大，信息熵較高（high entropy）。

由以上的香農信息公式可知，信息熵主要有三條性質：
- 單調性 。發生概率越高的事件，其所攜帶的信息熵越低。比如一個真理的不確定性是極低的，那麼它所攜帶的信息熵就極低。
- 非負性 。信息熵不能為負。單純從邏輯層面理解，如果得知了某個信息後，卻增加了不確定性，這也是不合邏輯的。
- 可加性 。即多隨機事件同時發生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和。

若兩事件A和B同時發生，兩個事件相互獨立。 p(X=A,Y=B) = p(X = A)*p(Y=B) , 那麼信息熵為 H(A,B) = H(A) + H(B) 。但若兩事件不相互獨立，那麼 H(A,B) = H(A) + H(B) - I(A,B) 。其中 I(A,B) 是互信息（ mutual information，MI ），即一個隨機變數包含另一個隨機變數信息量的度量。即已知X的情況下，Y的分布是否會改變。

可以理解為，兩個隨機變數的互信息度量了兩個變數間相互依賴的程度。X 和 Y的互信息可以表示為：
I(X;Y) = H(X) - H(X|Y)
H(X)是X的信息熵，H(X|Y)是已知Y的情況下，X的信息熵。結果的單位是比特。
簡單來說，互信息的性質為：
- I(X;Y)>=0 互信息永遠不可能為負
- H(X) - H(X|Y) = I(X;Y) = I (Y;X) = H(Y) - H(Y|X) 互信息是對稱的
-當X，Y獨立的時候， I(X;Y) = 0 互信息值越大，兩變數相關性越強。
-當X，Y知道一個就能推斷另一個的時候， I(X;Y) = H(Y) = H(X)

在數據科學中，互信息常用於特徵篩選。在通信系統中互信息也應用廣泛。在一個點到點的通信系統中，發送信號為X，通過信道後，接收端接收到的信號為Y，那麼信息通過信道傳遞的信息量就是互信息 I(X,Y) 。根據這個概念，香農推導出信道容量（即臨界通信傳輸速率的值）。

信息增益（ Information Gain ）是用來按照一定規則劃分數據集後，衡量信息熵減少量的指數。

那數據集的信息熵又是怎麼計算的呢？比如一個常見的0,1二分類問題，我們可以計算它的熵為：
Entropy = -(p(0) * log(P(0)) + p(1) * log(P(1)))
當該數據集為50/50的數據集時，它的信息熵是最大的（1bit）。而10/90的數據集將會大大減少結果的不確定性，減小數據集的信息熵（約為0.469bit）。

這樣來說，信息熵可以用來表示數據集的純度（ purity ）。信息熵為0就表示該數據集只含有一個類別，純度最高。而較高的信息熵則代表較為平衡的數據集和較低的純度。

信息增益是提供了一種可以使用信息熵計算數據集經過一定的規則（比如決策樹中的一系列規則）進行數據集分割後信息熵的變化的方法。
IG(S,a) = H(S) - H(S|a)
其中，H(s) 是原數據集S的信息熵（在做任何改變之前），H(S|a)是經過變數a的一定分割規則。所以信息增益描述的是數據集S變換後所節省的比特數。

信息增益可以用做決策樹的分枝判斷方法。比如最常用CART樹（ Classification and Regression Tree ）中的分枝方法，只要在python中設置參數 criterion 為 「entropy」 即可。

信息增益也可以用作建模前的特徵篩選。在這種場景下，信息增益和互信息表達的含義相同，會被用來計算兩變數之間的獨立性。比如scikit-learn 中的函數 mutual_info_classiif()

信息增益在面對類別較少的離散數據時效果較好，但是面對取值較多的特徵時效果會有 偏向性 。因為當特徵的取值較多時，根據此特徵劃分得到的子集純度有更大的可能性會更高(對比與取值較少的特徵)，因此劃分之後的熵更低，由於劃分前的熵是一定的，因此信息增益更大，因此信息增益比較偏向取值較多的特徵。舉一個極端的例子來說，如果一個特徵為身份證號，當把每一個身份證號不同的樣本都分到不同的子節點時，熵會變為0，意味著信息增益最大，從而該特徵會被演算法選擇。但這種分法顯然沒有任何實際意義。

這種時候，信息增益率就起到了很重要的作用。
gR(D,A)=g(D,A)/HA(D)
HA(D) 又叫做特徵A的內部信息，HA(D)其實像是一個衡量以特徵AA的不同取值將數據集D分類後的不確定性的度量。如果特徵A的取值越多，那麼不確定性通常會更大，那麼HA(D)的值也會越大，而1/HA(D)的值也會越小。這相當於是在信息增益的基礎上乘上了一個懲罰系數。即 gR(D,A)=g(D,A)∗懲罰系數 。

在CART演算法中，基尼不純度表示一個隨機選中的樣本被分錯類別的可能性，即這個樣本被選中的概率乘以它被分錯的概率。當一個節點中所有樣本均為一種時（沒有被分錯的樣本），基尼不純度達到最低值0。

舉例來說，如果有綠色和藍色兩類數據點，各佔一半（藍色50%，綠色50%）。那麼我們隨機分類，有以下四種情況：
-分為藍色，但實際上是綠色（❌），概率25%
-分為藍色，實際上也是藍色（✔️），概率25%
-分為綠色，實際上也是綠色（✔️），概率25%
-分為綠色，但實際上是藍色（❌），概率25%
那麼將任意一個數據點分錯的概率為25%+25% = 50%。基尼不純度為0.5。

在特徵選擇中，我們可以選擇加入後使數據不純度減少最多的特徵。

噪音數據簡單來說就是會對模型造成誤導的數據。分為類別雜訊（ class noise 或 label noise ）和 變數雜訊（ attribute noise ）。類別雜訊指的的是被錯誤標記的錯誤數據，比如兩個相同的樣本具有不同的標簽等情況。變數雜訊指的是有問題的變數，比如缺失值、異常值和無關值等。

決策樹其實是一種圖結構，由節點和邊構成。
-根節點：只有出邊沒有入邊。包含樣本全集，表示一個對樣本最初的判斷。
-內部節點：一個入邊多個出邊。表示一個特徵或是屬性。每個內部節點都是一個判斷條件，包含數據集中從根節點到該節點所有滿足條件的數據的集合。
-葉節點：一個入邊無出邊。表示一個類，對應於決策結果。

決策樹的生成主要分為三個步驟：
1. 節點的分裂 ：當一個節點不夠純（單一分類佔比不夠大或者說信息熵較大）時，則選擇將這一節點進行分裂。
2. 決策邊界的確定 ：選擇正確的決策邊界（ Decision Boundary ），使分出的節點盡量純，信息增益（熵減少的值）盡可能大。
3. 重復及停止生長 ：重復1，2步驟，直到純度為0或樹達到最大深度。為避免過擬合，決策樹演算法一般需要制定樹分裂的最大深度。到達這一深度後，即使熵不等於0，樹也不會繼續進行分裂。

下面以超級知名的鳶尾花數據集舉例來說明。
這個數據集含有四個特徵：花瓣的長度（ petal length ）、花瓣的寬度( petal width )、花萼的長度( sepal length )和花萼的寬度( sepal width )。預測目標是鳶尾花的種類 iris setosa, iris versicolor 和 iris virginica 。

建立決策樹模型的目標是根據特徵盡可能正確地將樣本劃分到三個不同的「陣營」中。

根結點的選擇基於全部數據集，使用了貪婪演算法：遍歷所有的特徵，選擇可以使信息熵降到最低、基尼不純度最低的特徵。

如上圖，根節點的決策邊界為' petal width = 0.8cm '。那麼這個決策邊界是怎麼決定的呢？
-遍歷所有可能的決策邊界（需要注意的是，所有可能的決策邊界代表的是該子集中該特徵所有的值，不是以固定增幅遍歷一個區間內的所有值！那樣很沒有必要的～）
-計算新建的兩個子集的基尼不純度。
-選擇可以使新的子集達到最小基尼不純度的分割閾值。這個「最小」可以指兩個子集的基尼不純度的和或平均值。

ID3是最早提出的決策樹演算法。ID3演算法的核心是在決策樹各個節點上根據 信息增益 來選擇進行劃分的特徵，然後遞歸地構建決策樹。
- 缺點 ：
（1）沒有剪枝
（2）只能用於處理離散特徵
（3）採用信息增益作為選擇最優劃分特徵的標准，然而信息增益會偏向那些取值較多的特徵(例如，如果存在唯一標識屬性身份證號，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。)

C4.5 與ID3相似，但對ID3進行了改進：
-引入「悲觀剪枝」策略進行後剪枝
-信息增益率作為劃分標准
-將連續特徵離散化，假設 n 個樣本的連續特徵 A 有 m 個取值，C4.5 將其排序並取相鄰兩樣本值的平均數共 m-1 個劃分點，分別計算以該劃分點作為二元分類點時的信息增益，並選擇信息增益最大的點作為該連續特徵的二元離散分類點；
-可以處理缺失值

對於缺失值的處理可以分為兩個子問題：
（1）在特徵值缺失的情況下進行劃分特徵的選擇？（即如何計算特徵的信息增益率）
C4.5 中對於具有缺失值特徵，用沒有缺失的樣本子集所佔比重來折算；
（2）選定該劃分特徵，對於缺失該特徵值的樣本如何處理？（即到底把這個樣本劃分到哪個結點里）
C4.5 的做法是將樣本同時劃分到所有子節點，不過要調整樣本的權重值，其實也就是以不同概率劃分到不同節點中。

（1）剪枝策略可以再優化；
（2）C4.5 用的是多叉樹，用二叉樹效率更高；
（3）C4.5 只能用於分類；
（4）C4.5 使用的熵模型擁有大量耗時的對數運算，連續值還有排序運算；
（5）C4.5 在構造樹的過程中，對數值屬性值需要按照其大小進行排序，從中選擇一個分割點，所以只適合於能夠駐留於內存的數據集，當訓練集大得無法在內存容納時，程序無法運行。

可以用於分類，也可以用於回歸問題。CART 演算法使用了基尼系數取代了信息熵模型，計算復雜度更低。

CART 包含的基本過程有 分裂，剪枝和樹選擇 。
分裂 ：分裂過程是一個二叉遞歸劃分過程，其輸入和預測特徵既可以是連續型的也可以是離散型的，CART 沒有停止准則，會一直生長下去；
剪枝 ：採用「代價復雜度」剪枝，從最大樹開始，每次選擇訓練數據熵對整體性能貢獻最小的那個分裂節點作為下一個剪枝對象，直到只剩下根節點。CART 會產生一系列嵌套的剪枝樹，需要從中選出一顆最優的決策樹；
樹選擇 ：用單獨的測試集評估每棵剪枝樹的預測性能（也可以用交叉驗證）。

（1）C4.5 為多叉樹，運算速度慢，CART 為二叉樹，運算速度快；
（2）C4.5 只能分類，CART 既可以分類也可以回歸；
（3）CART 使用 Gini 系數作為變數的不純度量，減少了大量的對數運算；
（4）CART 採用代理測試來估計缺失值，而 C4.5 以不同概率劃分到不同節點中；
（5）CART 採用「基於代價復雜度剪枝」方法進行剪枝，而 C4.5 採用悲觀剪枝方法。

（1）決策樹易於理解和解釋，可以可視化分析，容易提取出規則
（2）可以同時處理分類型和數值型數據
（3）可以處理缺失值
（4）運行速度比較快（使用Gini的快於使用信息熵，因為信息熵演算法有log）

（1）容易發生過擬合（集成演算法如隨機森林可以很大程度上減少過擬合）
（2）容易忽略數據集中屬性的相互關聯；
（3）對於那些各類別樣本數量不一致的數據，在決策樹中，進行屬性劃分時，不同的判定準則會帶來不同的屬性選擇傾向。

寫在後面：這個專輯主要是本小白在機器學習演算法學習過程中的一些總結筆記和心得，如有不對之處還請各位大神多多指正！（關於決策樹的剪枝還有很多沒有搞懂，之後弄明白了會再單獨出一篇總結噠）

參考資料鏈接：
1. https://machinelearningmastery.com/what-is-information-entropy/
2. https://zhuanlan.hu.com/p/29679277
3. https://machinelearningmastery.com/information-gain-and-mutual-information/
4. https://victorzhou.com/blog/gini-impurity/
5. https://sci2s.ugr.es/noisydata
6. https://towardsdatascience.com/understanding-decision-trees-once-and-for-all-2d891b1be579
7. https://blog.csdn.net/weixin_36586536/article/details/80468426
8. https://zhuanlan.hu.com/p/85731206

❸ 決策樹的原理及演算法

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

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

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

剪枝就是給決策樹瘦身，防止過擬合。分為「預剪枝」（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 丨決策樹（上）：要不要去打籃球？決策樹來告訴你

❹ 5.10 決策樹與ID3演算法

https://blog.csdn.net/dorisi_h_n_q/article/details/82787295

決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）。決策過程是從根節點開始，測試待分類項中相應的特徵屬性，並按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。

決策樹的關鍵步驟是分裂屬性。就是在某節點處按某一特徵屬性的不同劃分構造不同的分支，目標是讓各個分裂子集盡可能地「純」。即讓一個分裂子集中待分類項屬於同一類別。

簡而言之，決策樹的劃分原則就是：將無序的數據變得更加有序

分裂屬性分為三種不同的情況 ：

構造決策樹的關鍵性內容是進行屬性選擇度量，屬性選擇度量（找一種計算方式來衡量怎麼劃分更劃算）是一種選擇分裂准則，它決定了拓撲結構及分裂點split_point的選擇。

屬性選擇度量演算法有很多，一般使用自頂向下遞歸分治法，並採用不回溯的貪心策略。這里介紹常用的ID3演算法。

貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，所做出的是在某種意義上的局部最優解。

此概念最早起源於物理學，是用來度量一個熱力學系統的無序程度。
而在信息學裡面，熵是對不確定性的度量。
在1948年，香農引入了信息熵，將其定義為離散隨機事件出現的概率，一個系統越是有序，信息熵就越低，反之一個系統越是混亂，它的信息熵就越高。所以信息熵可以被認為是系統有序化程度的一個度量。

熵定義為信息的期望值，在明晰這個概念之前，我們必須知道信息的定義。如果待分類的事務可能劃分在多個分類之中，則符號x的信息定義為：

在劃分數據集之前之後信息發生的變化稱為信息增益。
知道如何計算信息增益，就可計算每個特徵值劃分數據集獲得的信息增益，獲得信息增益最高的特徵就是最好的選擇。

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

根據上面公式，我們假設將訓練集D按屬性A進行劃分，則A對D劃分的期望信息為

則信息增益為如下兩者的差值

ID3演算法就是在每次需要分裂時，計算每個屬性的增益率，然後選擇增益率最大的屬性進行分裂

步驟：1. 對當前樣本集合，計算所有屬性的信息增益；

是最原始的決策樹分類演算法，基本流程是，從一棵空數出發，不斷的從決策表選取屬性加入數的生長過程中，直到決策樹可以滿足分類要求為止。CLS演算法存在的主要問題是在新增屬性選取時有很大的隨機性。ID3演算法是對CLS演算法的改進，主要是摒棄了屬性選擇的隨機性。

基於ID3演算法的改進，主要包括：使用信息增益比替換了信息增益下降度作為屬性選擇的標准；在決策樹構造的同時進行剪枝操作；避免了樹的過度擬合情況；可以對不完整屬性和連續型數據進行處理；使用k交叉驗證降低了計算復雜度；針對數據構成形式，提升了演算法的普適性。

信息增益值的大小相對於訓練數據集而言的，並沒有絕對意義，在分類問題困難時，也就是說在訓練數據集經驗熵大的時候，信息增益值會偏大，反之信息增益值會偏小，使用信息增益比可以對這個問題進行校正，這是特徵選擇
的另一個標准。
特徵對訓練數據集的信息增益比定義為其信息增益gR( D,A) 與訓練數據集的經驗熵g(D,A)之比 ：

gR(D,A) = g(D,A) / H(D)

sklearn的決策樹模型就是一個CART樹。是一種二分遞歸分割技術，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子節點都有兩個分支，因此，CART演算法生成的決策樹是結構簡潔的二叉樹。
分類回歸樹演算法(Classification and Regression Trees,簡稱CART演算法)是一種基於二分遞歸分割技術的演算法。該演算法是將當前的樣本集，分為兩個樣本子集，這樣做就使得每一個非葉子節點最多隻有兩個分支。因此，使用CART
演算法所建立的決策樹是一棵二叉樹，樹的結構簡單，與其它決策樹演算法相比，由該演算法生成的決策樹模型分類規則較少。

CART分類演算法的基本思想是：對訓練樣本集進行遞歸劃分自變數空間，並依次建立決策樹模型，然後採用驗證數據的方法進行樹枝修剪，從而得到一顆符合要求的決策樹分類模型。

CART分類演算法和C4.5演算法一樣既可以處理離散型數據，也可以處理連續型數據。CART分類演算法是根據基尼(gini)系
數來選擇測試屬性，gini系數的值越小，劃分效果越好。設樣本集合為T，則T的gini系數值可由下式計算：

CART演算法優點：除了具有一般決策樹的高准確性、高效性、模式簡單等特點外，還具有一些自身的特點。
如，CART演算法對目標變數和預測變數在概率分布上沒有要求，這樣就避免了因目標變數與預測變數概率分布的不同造成的結果；CART演算法能夠處理空缺值，這樣就避免了因空缺值造成的偏差；CART演算法能夠處理孤立的葉子結點，這樣可以避免因為數據集中與其它數據集具有不同的屬性的數據對進一步分支產生影響；CART演算法使用的是二元分支，能夠充分地運用數據集中的全部數據，進而發現全部樹的結構；比其它模型更容易理解，從模型中得到的規則能獲得非常直觀的解釋。

CART演算法缺點：CART演算法是一種大容量樣本集挖掘演算法，當樣本集比較小時不夠穩定；要求被選擇的屬性只能產生兩個子結點，當類別過多時，錯誤可能增加得比較快。

sklearn.tree.DecisionTreeClassifier

1.安裝graphviz.msi ， 一路next即可

ID3演算法就是在每次需要分裂時，計算每個屬性的增益率，然後選擇增益率最大的屬性進行分裂

按照好友密度劃分的信息增益：

按照是否使用真實頭像H劃分的信息增益

**所以，按先按好友密度劃分的信息增益比按真實頭像劃分的大。應先按好友密度劃分。

❺ 決策樹——ID3演算法應用實例

在ID3決策樹歸納方法中，通常是使用信息增益方法來幫助確定生成每個節點時所應採用的合適屬性。這樣就可以選擇具有最高信息增益（熵減少的程度最大）的屬性最為當前節點的測試屬性，以便對之後劃分的訓練樣本子集進行分類所需要的信息最小，也就是說，利用該屬性進行當前（節點所含）樣本集合劃分，將會使得所產生的樣本子集中的「不同類別的混合程度」降為最低。因此，採用這樣一種資訊理論方法將有效減少對象分來所需要的次數，從而確保所產生的決策樹最為簡單。

一、實驗目的

1、理解分類

2、掌握分類挖掘演算法ID3

3、為改進ID3打下基礎

二、實驗內容

1、選定一個數據集（可以參考教學中使用的數據集）

2、選擇合適的實現環境和工具實現演算法 ID3

3、給出分類規則

三、實驗原理

決策樹是一種最常見的分類演算法，它包含有很多不同的變種，ID3演算法是其中最簡單的一種。ID3演算法中最主要的部分就是信息熵和信息增益的計算。

❻ id3演算法是什麼

ID3演算法是一種貪心演算法，用來構造決策樹。ID3演算法起源於概念學習系統（CLS），以信息熵的下降速度為選取測試屬性的標准，即在每個節點選取還尚未被用來劃分的具有最高信息增益的屬性作為劃分標准，然後繼續這個過程，直到生成的決策樹能完美分類訓練樣例。

ID3演算法的背景

ID3演算法最早是由羅斯昆（J. Ross Quinlan）於1975年在悉尼大學提出的一種分類預測演算法，演算法的核心是「信息熵」。ID3演算法通過計算每個屬性的信息增益，認為信息增益高的是好屬性，每次劃分選取信息增益最高的屬性為劃分標准，重復這個過程，直至生成一個能完美分類訓練樣例的決策樹。

❼ 決策樹是什麼東東

小白自學路上的備忘記錄。。。

參考：
決策樹(分類樹、回歸樹)
決策樹 :這個博客的圖真好看，通俗易懂。哈哈
決策樹詳解

決策樹（Decision Tree）是一種有監督學習演算法，常用於分類和回歸。本文僅討論分類問題。

決策樹模型是運用於分類以及回歸的一種樹結構。決策樹由節點和有向邊組成，一般一棵決策樹包含一個根節點、若干內部節點和若干葉節點。決策樹的決策過程需要從決策樹的根節點開始，待測數據與決策樹中的特徵節點進行比較，並按照比較結果選擇選擇下一比較分支，直到葉子節點作為最終的決策結果。

簡而言之，決策樹是一個利用樹的模型進行決策的多分類模型

為了找到最優的劃分特徵，我們需要先了解一些資訊理論的知識：

純度 ：
你可以把決策樹的構造過程理解成為尋找純凈劃分的過程。數學上，我們可以用純度來表示，純度換一種方式來解釋就是讓目標變數的分歧最小

信息熵 ：表示信息的不確定度
在資訊理論中，隨機離散事件出現的概率存在著不確定性。為了衡量這種信息的不確定性，信息學之父香農引入了信息熵的概念.
當不確定性越大時，它所包含的信息量也就越大，信息熵也就越高 。
信息熵越大，純度越低。當集合中的所有樣本均勻混合時，信息熵最大，純度最低

經典的 「不純度」的指標有三種，分別是信息增益（ID3 演算法）、信息增益率（C4.5 演算法）以及基尼指數（Cart 演算法）
信息增益 ：
信息增益指的就是劃分可以帶來純度的提高，信息熵的下降。它的計算公式，是父親節點的信息熵減去所有子節點的信息熵。
信息增益率
信息增益率 = 信息增益 / 屬性熵
基尼指數
基尼指數（基尼不純度）：表示在樣本集合中一個隨機選中的樣本被分錯的概率。
即 基尼指數（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率
基尼系數的性質與信息熵一樣：度量隨機變數的不確定度的大小；
G 越大，數據的不確定性越高；
G 越小，數據的不確定性越低；
G = 0，數據集中的所有樣本都是同一類別
詳細參考： 機器學習——基尼指數

ID3 演算法是建立在奧卡姆剃刀（用較少的東西，同樣可以做好事情）的基礎上：越是小型的決策樹越優於大的決策樹
ID3演算法的核心是在決策樹各個節點上根據信息增益來選擇進行劃分的特徵，然後遞歸地構建決策樹。演算法採用自頂向下的貪婪搜索遍歷可能的決策樹空間。

具體方法 ：

ID3的局限 ：

C4.5與ID3相似，但大的特點是克服了 ID3 對特徵數目的偏重這一缺點，引入信息增益率來作為分類標准。

C4.5的實現基於ID3的改進 ：

信息增益率對可取值較少的特徵有所偏好（分母越小，整體越大），因此 C4.5 並不是直接用增益率最大的特徵進行劃分，而是使用一個 啟發式方法 ：先從候選劃分特徵中找到信息增益高於平均值的特徵，再從中選擇增益率最高的。

C4.5的局限 ：

ID3 和 C4.5 生成的決策樹分支、規模都比較大，CART 演算法的二分法可以簡化決策樹的規模，提高生成決策樹的效率。
CART(),分類回歸樹演算法，既可用於分類也可用於回歸，在這一部分我們先主要將其分類樹的生成。區別於ID3和C4.5,CART假設決策樹是二叉樹，內部節點特徵的取值為「是」和「否」，左分支為取值為「是」的分支，右分支為取值為」否「的分支。這樣的決策樹等價於遞歸地二分每個特徵，將輸入空間(即特徵空間)劃分為有限個單元。
CART的分類樹用基尼指數來選擇最優特徵的最優劃分點，具體過程如下

剪枝就是給決策樹瘦身，這一步想實現的目標就是，不需要太多的判斷，同樣可以得到不錯的結果。之所以這么做，是為了防止「過擬合」（Overfitting）現象的發生。
過擬合：指的是模型的訓練結果「太好了」，以至於在實際應用的過程中，會存在「死板」的情況，導致分類錯誤。
欠擬合：指的是模型的訓練結果不理想.
剪枝的方法 ：

參考： 【機器學習】決策樹（上）——ID3、C4.5、CART（非常詳細）

更多模型不斷更新中。。。。

❽ 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%.

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

❾ 決策樹（Decision Tree）

通俗來說，決策樹分類的思想類似於找對象。現想像一個女孩的母親要給這個女孩介紹男朋友，於是有了下面的對話：

      女兒：多大年紀了？

      母親：26。

      女兒：長的帥不帥？

      母親：挺帥的。

      女兒：收入高不？

      母親：不算很高，中等情況。

      女兒：是公務員不？

      母親：是，在稅務局上班呢。

      女兒：那好，我去見見。

      這個女孩的決策過程就是典型的分類樹決策。相當於通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見。假設這個女孩對男人的要求是：30歲以下、長相中等以上並且是高收入者或中等以上收入的公務員，圖1表示了女孩的決策邏輯。

如果你作為一個女生，你會優先考慮哪個條件：長相？收入？還是年齡。在考慮年齡條件時使用25歲為劃分點，還是35歲為劃分點。有這么多條件，用哪個條件特徵先做if，哪個條件特徵後做if比較優呢？還有怎麼確定用特徵中的哪個數值作為劃分的標准。這就是決策樹機器學習演算法的關鍵了。

首先，我們需要熟悉資訊理論中熵的概念。熵度量了事物的不確定性，越不確定的事物，它的熵就越大。具體的，隨機變數X的熵的表達式如下：

如拋一枚硬幣為事件 ， ， ，

擲一枚骰子為事件 ， ，

，顯然擲骰子的不確定性比投硬幣的不確定性要高。 

熟悉了單一變數的熵，很容易推廣到多個個變數的聯合熵，這里給出兩個變數X和Y的聯合熵表達式：

有了聯合熵，又可以得到條件熵的表達式H(X|Y)，條件熵類似於條件概率,它度量了我們在知道Y以後X剩下的不確定性。表達式：

我們剛才提到 度量了 的不確定性，條件熵 度量了我們在知道 以後 剩下的不確定性，那麼 呢？它度量了 在知道 以後不確定性減少程度，這個度量我們在資訊理論中稱為互信息，記為 。

信息熵 ，聯合熵 ，條件熵 ，互信息 之間的關系由圖2所示：

在決策樹的ID3演算法中，互信息 被稱為信息增益。ID3演算法就是用信息增益來判斷當前節點應該用什麼特徵來構建決策樹。信息增益大，則越適合用來分類。

下面我們用SNS社區中不真實賬號檢測的例子說明如何使用ID3演算法構造決策樹。為了簡單起見，我們假設訓練集合包含10個元素：

設L、F、H和D表示日誌密度、好友密度、是否使用真實頭像和賬號是否真實，下面計算各屬性的信息增益：

 因此日誌密度的信息增益是0.276。用同樣方法得到H和F的信息增益分別為0.033和0.553。因為F具有最大的信息增益，所以第一次分裂選擇F為分裂屬性，分裂後的結果圖3表示：

在上圖的基礎上，再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。

但是ID3演算法中還存在著一些不足之處：

1.ID3沒有考慮連續特徵，比如長度，密度都是連續值，無法在ID3運用。這大大限制了ID3的用途。

2.ID3採用信息增益大的特徵優先建立決策樹的節點。很快就被人發現，在相同條件下，取值比較多的特徵比取值少的特徵信息增益大。比如一個變數有2個值，各為 ，另一個變數為3個值，各為 ，其實他們都是完全不確定的變數，但是取3個值的比取2個值的信息增益大。（信息增益反映的給定一個條件以後不確定性減少的程度,必然是分得越細的數據集確定性更高,也就是條件熵越小,信息增益越大）如河校正這個問題呢？為了解決這些問題我們有了C4.5演算法。

對於第一個問題，不能處理連續特徵， C4.5的思路是將連續的特徵離散化。比如m個樣本的連續特徵A有m個，從小到大排列為 。則C4.5取相鄰兩樣本值的平均數，一共取得m-1個劃分點，其中第i個劃分點 表示為： 。對於這m-1個點，分別計算以該點作為二元分類點時的信息增益。選擇信息增益最大的點作為該連續特徵的二元離散分類點。比如取到的增益最大的點為 ，取大於 為類別1，小於 為類別2。這樣我們就做到了連續特徵的離散化。

對於第二個問題，信息增益作為標准容易偏向於取值較多的特徵。C4.5中提出了信息增益比：

即特徵 的對數據集 的信息增益與特徵 信息熵的比，信息增益比越大的特徵和劃分點，分類效果越好。某特徵中值得種類越多，特徵對應的特徵熵越大，它作為分母，可以校正信息增益導致的問題。

回到上面的例子：

 

同樣可得：  ， 。

因為F具有最大的信息增益比，所以第一次分裂選擇F為分裂屬性，分裂後的結果圖3表示。

再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。

看完上述材料，我們知道在ID3演算法中我們使用了信息增益來選擇特徵，信息增益大的優先選擇。在C4.5演算法中，採用了信息增益比來選擇特徵，以減少信息增益容易選擇特徵值種類多的特徵的問題。但是無論是ID3還是C4.5,都是基於資訊理論的熵模型的，這裡面會涉及大量的對數運算。能不能簡化模型同時也不至於完全丟失熵模型的優點呢？有！CART分類樹演算法使用基尼系數來代替信息增益比，基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特徵越好。這和信息增益(比)是相反的。

在分類問題中，假設有 個類別，第 個類別的概率為 ,則基尼系數為：

對於給定的樣本 ，假設有 個類別，第 個類別的數量為 ，則樣本的基尼系數為:

特別的，對於樣本D,如果根據特徵A的某個值a,把D分成D1和D2兩部分，則在特徵A的條件下，D的基尼系數為：

回到上面的例子：

同理得： ， 。

因為L具有最小的基尼系數，所以第一次分裂選擇L為分裂屬性。

再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。

小夥伴們如果覺得文章還行的請點個贊呦！！同時覺得文章哪裡有問題的可以評論一下  謝謝你！

❿ 決策樹演算法

決策樹演算法的演算法理論和應用場景

演算法理論：

我了解的決策樹演算法，主要有三種，最早期的ID3，再到後來的C4.5和CART這三種演算法。

這三種演算法的大致框架近似。

決策樹的學習過程

1.特徵選擇

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

2.決策樹生成

根據選擇的特徵評估標准，從上至下遞歸生成子節點，直到數據集不可分或者最小節點滿足閾值，此時決策樹停止生長。

3.剪枝

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

有些演算法用剪枝過程，有些沒有，如ID3。

預剪枝：對每個結點劃分前先進行估計，若當前結點的劃分不能帶來決策樹的泛化性能的提升，則停止劃分，並標記為葉結點。

後剪枝：現從訓練集生成一棵完整的決策樹，然後自底向上對非葉子結點進行考察，若該結點對應的子樹用葉結點能帶來決策樹泛化性能的提升，則將該子樹替換為葉結點。

但不管是預剪枝還是後剪枝都是用驗證集的數據進行評估。

ID3演算法是最早成型的決策樹演算法。ID3的演算法核心是在決策樹各個節點上應用信息增益准則來選擇特徵，遞歸構建決策樹。缺點是，在選擇分裂變數時容易選擇分類多的特徵，如ID值【值越多、分叉越多，子節點的不純度就越小，信息增益就越大】。

ID3之所以無法 處理缺失值、無法處理連續值、不剪紙等情況，主要是當時的重點並不是這些。

C4.5演算法與ID3近似，只是分裂標准從 信息增益 轉變成  信息增益率。可以處理連續值，含剪枝，可以處理缺失值，這里的做法多是 概率權重。

CART：1.可以處理連續值 2.可以進行缺失值處理 3.支持剪枝 4.可以分類可以回歸。

缺失值的處理是 作為一個單獨的類別進行分類。

建立CART樹

我們的演算法從根節點開始，用訓練集遞歸的建立CART樹。

1) 對於當前節點的數據集為D，如果樣本個數小於閾值或者沒有特徵，則返回決策子樹，當前節點停止遞歸。

2) 計算樣本集D的基尼系數， 如果基尼系數小於閾值 （說明已經很純了！！不需要再分了！！），則返回決策樹子樹，當前節點停止遞歸。

3) 計算當前節點現有的各個特徵的各個特徵值對數據集D的基尼系數。

4) 在計算出來的各個特徵的各個特徵值對數據集D的基尼系數中，選擇 基尼系數最小的特徵A和對應的特徵值a。根據這個最優特徵和最優特徵值，把數據集劃分成兩部分D1和D2，同時建立當前節點的左右節點，做節點的數據集D為D1，右節點的數據集D為D2。 (註：注意是二叉樹，故這里的D1和D2是有集合關系的，D2=D-D1)

5) 對左右的子節點遞歸的調用1-4步，生成決策樹。

CART採用的辦法是後剪枝法，即先生成決策樹，然後產生所有可能的剪枝後的CART樹，然後使用交叉驗證來檢驗各種剪枝的效果，選擇泛化能力最好的剪枝策略。

應用場景

比如欺詐問題中，通過決策樹演算法簡單分類，默認是CART的分類樹，默認不剪枝。然後在出圖後，自行選擇合適的葉節點進行拒絕操作。

這個不剪枝是因為欺詐問題的特殊性，欺詐問題一般而言較少，如數據的萬幾水平，即正樣本少，而整個欺詐問題需要解決的速度較快。此時只能根據業務要求，迅速針對已有的正樣本情況，在控制准確率的前提下，盡可能提高召回率。這種情況下，可以使用決策樹來簡單應用，這個可以替代原本手工選擇特徵及特徵閾值的情況。