參考資料：
《西瓜書》 p73-p95
《百面機器學習》 p80-89
《統(tǒng)計學習方法》 p55-p75
《機器學習_ 學習筆記 (all in one)V0.96》 p622-p650
《Decision Tree - Super Attributes》http://www.saedsayad.com/decision_tree_super.htm
決策樹算法原理(上) https://www.cnblogs.com/pinard/p/6050306.html
決策樹算法原理(下) https://www.cnblogs.com/pinard/p/6053344.html
StatQuest: Decision Trees: https://www.youtube.com/watch?v=7VeUPuFGJHk

關鍵詞

無參、監(jiān)督學習、分類、回歸、ID3、C4.5、CART

基本概念

• 定義：
  決策樹就是一棵樹，它以樹的形式來構(gòu)建分類或者回歸模型，其思想在于分而治之，通過遵循樹中從根（開始）到葉節(jié)點的決策來預測目標變量的值或?qū)ζ溥M行分類。

• 術語：
  根結(jié)點、內(nèi)部節(jié)點、葉節(jié)點

一棵樹.png

• 決策樹學到的是什么：
  if-then規(guī)則集，根結(jié)點到葉節(jié)點的每一條路徑為一條規(guī)則，路徑中分支的特征反映其規(guī)則的條件，規(guī)則之間互斥且完備

• 如何構(gòu)造一顆決策樹：（摘自Jim Liang筆記）
  Strategy: top-down Recursive divide-and-conquer fashion

  1. First: select attribute for the root node
     Create a branch for each possible attribute value
  2. Then: split instances into subsets
     One for each branch extending from the node
  3. Finally: repeat recursively for each branch, using only instances that reach the branch

  Stop if all instances have the same class

• 決策樹構(gòu)建的關鍵問題
  決策樹生成和決策樹剪枝

決策樹生成

決策樹生成主要需要考慮的就是特征選擇問題和何時停止樹木構(gòu)建的問題。

• 何時停的問題，比較容易解決，就是看被分到同一個分支下的子集之間的類別是否完全統(tǒng)一，若已經(jīng)統(tǒng)一，則可以停止繼續(xù)劃分，若還是有不同的類，則對該子集繼續(xù)選擇特征生成樹枝。
  when to terminate:
  (1) hit a pure class
  (2) run out of attributes (另一種情況)

• 特征選擇，不同的算法有不同的準則。三種主要算法（ID3, C4.5, CART）對應不同的啟發(fā)策略

ID3, C4.5, CART盡管使用不同的啟發(fā)策略，但是其使用的思想還是一樣的（CART的的純度思想類似于信息墑），這個思想就是信息論里面的墑思想。

墑（Entropy）: 衡量事物的不確定性指數(shù)，a measure of disorder or uncertainty

信息墑（Information entropy）：消息中包含的信息的平均量，可以理解為某條數(shù)據(jù)包含多少信息內(nèi)容，the average amount of information produced by a stochastic source of data. Generally, information entropy is the average amount of information conveyed by an event

小概率事件包含的信息墑比大概率事件包含的信息墑多 More uncertainty, more entropy!
直觀理解舉例： Event e ~ I(e) is its entropy if P(e)=1 I(e) = 0 => 確定性事件沒有什么有價值的東西（足夠確定，不混亂）

，表示數(shù)據(jù)屬于第類出現(xiàn)的概率

例子 摘自Jim Liang筆記 .png

拋硬幣例子： I(x) = -0.5 * log0.5 - 0.5 * log0.5= 1

使用墑作為準則.png

ID3：

昆蘭大神用信息論中的熵來度量決策樹的決策選擇過程

信息增益（Information Gain）
Information Gain = Entropy(before) - Entropy(after)

簡單的理解來說，信息增益就是通過得到了數(shù)據(jù)的一部分特征信息后導致原有數(shù)據(jù)混亂程度的降低，在決策樹里面可以使用這樣一個衡量指數(shù)作為尋找最優(yōu)特征的啟發(fā)準則。

Constructing a decision tree is all about finding attribute that returns the highest information gain

個人覺得書籍里說的關于經(jīng)驗條件墑之類的太過于抽象，其實主要的思想就是如下：

information Gain 摘自Jim Liang筆記.png

to be continued.png

所以ID3算法的核心思想就是通過信息增益來尋找最優(yōu)的特征，
可以從第一步開始通過計算原始數(shù)據(jù)的墑作為初始信息墑，通過計算根據(jù)每個特征得到的數(shù)據(jù)集合的墑，查看哪一個特征導致的信息增益最大，依據(jù)此作為根結(jié)點的確定，后續(xù)根據(jù)相同的準則來完成決策樹的生長。

決策樹實現(xiàn)（ID3）：
1.判斷樣本是否為同一類輸出Di,如果是則返回單節(jié)點樹T,標記類別為Di  --- 停止的條件1
2.判斷特征是否為空，如果是則返回單節(jié)點樹T，標記類別為樣本中輸出類別D實例數(shù)最多的類別 -- 停止的條件2
3.計算樣本中各個特征的信息增益，選擇最大的特征作為條件，按照其特征不同的取值將對應的樣本分成不同的類別，每一個類別為一個分支
4.對于所有的分支，遞歸調(diào)用1-3步，得到子樹

• ID3存在問題：
  1. 連續(xù)特征無法適用
  2. 特征取值偏好（相同條件下，優(yōu)先選取特征值多的特征）
  3. 缺失值的情況無法處理
  4. 過擬合問題

C4.5：

• 由來：解決ID3存在的4個問題

連續(xù)特征問題解決：

C4.5決策樹算法[Quinlan,1993]采用的二分法(bi－partition)機制來處理連續(xù)屬性。對于連續(xù)屬性a，首先將n個不同取值進行從小到大排序，選擇相鄰a屬性值的平均值t作為候選劃分點，劃分點將數(shù)據(jù)集分為兩類，因此有包含n－1個候選劃分點的集合，分別計算出每個劃分點下的信息增益，選擇信息增益最大的點作為該連續(xù)特征的二元離散分類點，根據(jù)此做到了連續(xù)值的離散劃分。
（摘自 https://www.zhihu.com/question/63762734/answer/512747829）

特征選取偏好問題解決：

信息增益率（Information Gain Ratio）

splitting the training data set D into v partitions, corresponding to v outcomes on attribute A

直觀計算splitinfo.png

• ID3特征選取偏好細節(jié)：對可取值數(shù)目較多的屬性有所偏好，例如一個屬性有幾十個取值，每一個取值只有一個元素，最后表現(xiàn)出來其信息增益很大（信息增益偏向于支持有著許多結(jié)果的特征）
  The information gain equation, G(T, X) is biased toward attributes that have a large number of values over attributes that have a smaller number of values. These ‘Super Attributes’ will easily be selected as the root, resulting in a broad tree that classifies perfectly but performs poorly on unseen instances.（摘自http://www.saedsayad.com/decision_tree_super.htm）

舉個例子，對于多值特征（極端情況下，unique id）這時候按照信息增益切分后各個分支都是純的，熵最小，為0 ，信息增益最大，但是這種切分沒有意義
https://www.youtube.com/watch?v=rb1jdBPKzDk

摘自[http://www.saedsayad.com/decision_tree_super.htm] .png

• 信息增益率的本質(zhì)
  在信息增益的基礎上除以一個懲罰參數(shù)，當特征個數(shù)較多的時候，懲罰參數(shù)較大，信息增益率減少較大，當特征個數(shù)較少的時候，懲罰參數(shù)較小，信息增益率減少較小

• 信息增益率帶來的問題：
  根據(jù)定義不難看出來，信息增益率會偏向取值比較小的特征

• 權衡：C4.5算法并不是直接選擇信息增益率最大的特征作為節(jié)點進行屬性劃分，而是首先從候選劃分中選擇信息增益高于平均水平的，再從中選擇信息增益率最大的（兩步操作）。

缺失值問題解決：

未完待續(xù)。。。。

過擬合問題解決

剪枝（后續(xù)有細節(jié)描述）

• C4.5 依舊存在的不足：
  1. 只適用于分類問題
  2. 熵模型有大量的耗時的對數(shù)運算,對于連續(xù)值有大量的排序運算

決策樹實現(xiàn)（C4.5）：
1.判斷樣本是否為同一類輸出Di,如果是則返回單節(jié)點樹T,標記類別為Di  --- 停止的條件1
2.判斷特征是否為空，如果是則返回單節(jié)點樹T，標記類別為樣本中輸出類別D實例數(shù)最多的類別 -- 停止的條件2
3.計算樣本中各個特征的信息增益比，選擇最大的特征作為條件，按照其特征不同的取值將對應的樣本分成不同的類別，每一個類別為一個分支（這里會有連續(xù)特征和缺失問題的處理）
4.對于所有的分支，遞歸調(diào)用1-3步，得到子樹

CART：（Classification and Regression Tree）

CART分類樹

解決問題：ID3還是C4.5都是基于信息論的熵模型的，其中涉及大量的對數(shù)運算。

CART采用Gini指數(shù)作為特征選擇的策略，Gini(D)越小，數(shù)據(jù)集D的純度越高，所以在特征選擇的過程中，選取全部累加起來后最小的作為節(jié)點，最小化不純度，和最大化信息增益（ID3，C4.5）正好相反。

基尼指數(shù)（Gini index）

Gini index example（不知道那個之前在哪個網(wǎng)頁看見的，隨手截下，侵刪）.png

• CART算法僅對特征的值進行二分，而不是多分,因此得到的決策樹是一顆二叉樹。（目的，1.簡化基尼系數(shù)的計算，2.建立一個更加優(yōu)雅的二叉樹模型）

CART中連續(xù)值的處理：bi-partition + gini index（思想和C4.5相同，但是使用度量方式不一樣）

分類決策樹實現(xiàn)（CART）：
1.判斷樣本是否為同一類輸出Di,如果是則返回單節(jié)點樹T,標記類別為Di  --- 停止的條件1
2.判斷特征是否為空，如果是則返回單節(jié)點樹T，標記類別為樣本中輸出類別D實例數(shù)最多的類別 -- 停止的條件2
3.計算樣本中各個特征的基尼系數(shù)（這里會有連續(xù)特征和缺失問題的處理）
4.在計算出來的各個特征的各個特征值對數(shù)據(jù)集D的基尼系數(shù)中，選擇基尼系數(shù)最小的特征A和對應的特征值a。根據(jù)這個最優(yōu)特征和最優(yōu)特征值，把數(shù)據(jù)集劃分成兩部分D1和D2，同時建立當前節(jié)點的左右節(jié)點，做節(jié)點的數(shù)據(jù)集D為D1，右節(jié)點的數(shù)據(jù)集D為D2.
5.對于所有的分支，遞歸調(diào)用1-4步，得到子樹


3.4的解讀：有稍許的不同，原因在于CART做的的是二分處理，即使特征有多個值，其也是進行一個二分的處理方式

舉個例子：
如果某個特征A被選取建立決策樹節(jié)點，如果它有A1,A2,A3三種類別，
CART分類樹會考慮把A分成
{A1}和{A2,A3} 
{A2}和{A1,A3}
{A3}和{A1,A2}
在這三種情況中找到基尼系數(shù)最小的組合，比如{A2}和{A1,A3}
然后建立二叉樹節(jié)點，一個節(jié)點是A2對應的樣本，另一個節(jié)點是{A1,A3}對應的節(jié)點。同時，由于這次沒有把特征A的取值完全分開，后面還有機會在子節(jié)點繼續(xù)選擇到特征A來劃分A1和A3。這和ID3或者C4.5不同，在ID3或者C4.5的一棵子樹中，離散特征只會參與一次節(jié)點的建立。
https://www.cnblogs.com/pinard/p/6053344.html

CART 回歸樹

CART回歸樹和分類樹算法比較類似，不同的地方在于最后的輸出以及特征選擇時候的度量方式。

回歸樹算法.png