決策樹演算法的流程圖

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

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

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

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

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

2. 決策樹（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

3. 決策樹（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：
整理得到最終的決策樹：

4. ML - 決策樹(decision tree)

機器學習中分類和預測演算法的評估：

判定樹是一個類似於流程圖的樹結構：其中，每個內部結點表示在一個 屬性上的測試 ，每個分支代表一個 屬性輸出 ，而每個樹葉結點代表 類或類分布 。樹的最頂層是根結點。
機器學習中分類方法中的一個重要演算法

信息和抽象，如何度量？

1948年，香農提出了 」信息熵(entropy)「的概念

一條信息的信息量大小和它的不確定性有直接的關系，要搞清楚一件非常非常不確定的事情，或者

是我們一無所知的事情，需要了解大量信息==> 信息量的度量就等於不確定性的多少

例子：猜世界盃冠軍，假如一無所知，猜多少次？

每個隊奪冠的幾率不是相等的

比特(bit)來衡量信息的多少

變數的不確定性越大，熵也就越大

3.1 決策樹歸納演算法 （ ID3 ）

1970-1980， J.Ross. Quinlan, ID3演算法

選擇屬性（A為age時）判斷結點

信息獲取量(Information Gain) ：
Gain(A) = Info(D) - Infor_A(D)
Gain(A) =按yes/no分的熵 - 按A屬性分類的熵

通過A來作為節點分類獲取了多少信息

類似
Gain(income) = 0.029
Gain(student) = 0.151
Gain(credit_rating)=0.048
所以，選擇age作為第一個根節點

重復。。。

演算法：

*其他演算法：

C4.5 : Quinlan

Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)

共同點：都是貪心演算法，自上而下(Top-down approach)

區別：屬性選擇度量方法不同： C4.5 （gain ratio), CART(gini index), ID3 (Information Gain)

先剪枝

後剪枝

直觀，便於理解，小規模數據集有效

處理連續變數不好（離散化，閾值選擇對結果影響大）

類別較多時，錯誤增加的比較快

可規模性一般

1. Python

2. Python機器學習的庫： scikit-learn

2.1： 特性：

簡單高效的數據挖掘和機器學習分析

對所有用戶開放，根據不同需求高度可重用性

基於Numpy, SciPy和matplotlib

開源，商用級別：獲得 BSD許可

2.2 覆蓋問題領域：

分類（classification), 回歸（regression), 聚類（clustering), 降維(dimensionality rection)

模型選擇(model selection), 預處理(preprocessing)

3. 使用用scikit-learn

安裝scikit-learn: pip, easy_install, windows installer

安裝必要package：numpy， SciPy和matplotlib， 可使用 Anaconda (包含numpy, scipy等科學計算常用package）

4. 例子：

文檔： http://scikit-learn.org/stable/moles/tree.html

安裝 Graphviz： http://www.graphviz.org/
配置環境變數
轉化dot文件至pdf可視化決策樹：dot -Tpdf iris.dot -o outpu.pdf

5. 如何畫決策樹

畫決策樹的步驟如下：

A、先畫一個方框作為出發點，又稱決策節點；
B、從出發點向右引出若干條直線，這些直線叫做方案枝；
C、在每個方案枝的末端畫一個圓圈，這個圓圈稱為概率分叉點，或自然狀態點；
D、從自然狀態點引出代表各自然狀態的分枝，稱為概率分枝；
E、如果問題只需要一級決策，則概率分枝末端畫三角形，表示終點。


例題）
假設有一項工程，施工管理人員需要決定下月是否開工。如果開工後天氣好，則可為國家創收4萬元，若開工後天氣壞，將給國家造成損失1萬元，不開工則損失1000元。根據過去的統計資料，下月天氣好的概率是0.3,天氣壞的概率是0.7。請做出決策。現採用決策樹方法進行決策
【解】第一步：將題意表格化

6. 決策樹分析方法的基本步驟

決策樹分析方法的基本步驟

1.繪制決策樹圖。從左到右的順序畫決策樹，此過程本身就是對決策問題的再分析過程。

2.按從右到左的順序計算各方案的期望值，並將結果寫在相應方案節點上方。期望值的計算是從右到左沿著決策樹的反方向進行計算的。

3.對比各方案的期望值的大小，將期望值小的方案(即劣等方案)剪掉，所剩的最後方案為最佳方案。

決策樹(簡稱DT)利用概率論的原理，並且利用一種樹形圖作為分析工具。其基本原理是用決策點代表決策問題，用方案分枝代表可供選擇的方案，用概率分枝代表方案可能出現的各種結果，經過對各種方案在各種結果條件下損益值的計算比較，為決策者提供決策依據。

缺點：

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

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

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

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

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

1、特徵選擇

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

2、決策樹生成

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

3、決策樹剪枝

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

【簡介】

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