參考資料：
《西瓜書》 p73-p95
《百面機(jī)器學(xué)習(xí)》 p80-89
《統(tǒng)計(jì)學(xué)習(xí)方法》 p55-p75
《機(jī)器學(xué)習(xí)_ 學(xué)習(xí)筆記 (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

關(guān)鍵詞

無參浩峡、監(jiān)督學(xué)習(xí)支救、分類订讼、回歸淹接、ID3氯庆、C4.5、CART

基本概念

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

• 術(shù)語：
  根結(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)窟她、葉節(jié)點(diǎn)

一棵樹.png

• 決策樹學(xué)到的是什么：
  if-then規(guī)則集陈症，根結(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑為一條規(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)建的關(guān)鍵問題
  決策樹生成和決策樹剪枝

決策樹生成

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

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

• 特征選擇蚤蔓，不同的算法有不同的準(zhǔn)則。三種主要算法（ID3, C4.5, CART）對(duì)應(yīng)不同的啟發(fā)策略

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

墑（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 => 確定性事件沒有什么有價(jià)值的東西（足夠確定蘸劈，不混亂）

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

例子 摘自Jim Liang筆記 .png

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

使用墑作為準(zhǔn)則.png

ID3：

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

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

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

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

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

information Gain 摘自Jim Liang筆記.png

to be continued.png

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

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

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

C4.5：

• 由來：解決ID3存在的4個(gè)問題

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

C4.5決策樹算法[Quinlan,1993]采用的二分法(bi－partition)機(jī)制來處理連續(xù)屬性屡谐。對(duì)于連續(xù)屬性a，首先將n個(gè)不同取值進(jìn)行從小到大排序蝌数，選擇相鄰a屬性值的平均值t作為候選劃分點(diǎn)愕掏，劃分點(diǎn)將數(shù)據(jù)集分為兩類，因此有包含n－1個(gè)候選劃分點(diǎn)的集合顶伞，分別計(jì)算出每個(gè)劃分點(diǎn)下的信息增益饵撑，選擇信息增益最大的點(diǎn)作為該連續(xù)特征的二元離散分類點(diǎn)，根據(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

直觀計(jì)算splitinfo.png

• ID3特征選取偏好細(xì)節(jié)：對(duì)可取值數(shù)目較多的屬性有所偏好滑潘，例如一個(gè)屬性有幾十個(gè)取值，每一個(gè)取值只有一個(gè)元素锨咙，最后表現(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）

舉個(gè)例子语卤，對(duì)于多值特征（極端情況下，unique id）這時(shí)候按照信息增益切分后各個(gè)分支都是純的酪刀，熵最小粹舵，為0 ，信息增益最大骂倘，但是這種切分沒有意義
https://www.youtube.com/watch?v=rb1jdBPKzDk

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

• 信息增益率的本質(zhì)
  在信息增益的基礎(chǔ)上除以一個(gè)懲罰參數(shù)眼滤，當(dāng)特征個(gè)數(shù)較多的時(shí)候，懲罰參數(shù)較大历涝，信息增益率減少較大诅需，當(dāng)特征個(gè)數(shù)較少的時(shí)候，懲罰參數(shù)較小睬关，信息增益率減少較小

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

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

缺失值問題解決：

未完待續(xù)。丐箩。摇邦。。

過擬合問題解決

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

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

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

CART：（Classification and Regression Tree）

CART分類樹

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

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

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

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

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

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

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


3.4的解讀：有稍許的不同畅厢，原因在于CART做的的是二分處理，即使特征有多個(gè)值氮昧，其也是進(jìn)行一個(gè)二分的處理方式

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

CART 回歸樹

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

回歸樹算法.png