參考資料:
《西瓜書》 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)
決策樹學(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- First: select attribute for the root node
Create a branch for each possible attribute value - Then: split instances into subsets
One for each branch extending from the node - Finally: repeat recursively for each branch, using only instances that reach the branch
Stop if all instances have the same class
- First: select attribute for the root node
決策樹構(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)的概率
拋硬幣例子: I(x) = -0.5 * log0.5 - 0.5 * log0.5= 1
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í)主要的思想就是如下:
所以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存在問題:
- 連續(xù)特征無法適用
- 特征取值偏好(相同條件下粘驰,優(yōu)先選取特征值多的特征)
- 缺失值的情況無法處理
- 過擬合問題
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
- 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
信息增益率的本質(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 依舊存在的不足:
- 只適用于分類問題
- 熵模型有大量的耗時(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)
- 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í)候的度量方式哮洽。
回歸樹 | 分類樹 | |
---|---|---|
輸出 | 葉子的均值或者中位數(shù) | 葉子節(jié)點(diǎn)里概率最大的類別 |
度量 | 和方差 | 基尼系數(shù) |