決策樹(Decision Tree)

參考資料:
《西瓜書》 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à)值的東西(足夠確定蘸劈,不混亂)

\text { Entropy }=-\sum_{i=1}^{n} p_{i} \log _{2} p_{i}

p_{i} = P(X=x_{i}) 昏苏,表示數(shù)據(jù)屬于第i類出現(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)
\text {GainRatio}(A)=\frac{\text {Gain}(A)}{\text {SplitInfo}(A)}

\text {SplitInfo}_{A}(D)=-\sum_{j=1}^{v} \frac{\left|D_{j}\right|}{|D|} \times \log _{2}\left(\frac{\left|D_{j}\right|}{D}\right)
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)
\operatorname{Gini}(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}

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í)候的度量方式哮洽。

回歸樹 分類樹
輸出 葉子的均值或者中位數(shù) 葉子節(jié)點(diǎn)里概率最大的類別
度量 和方差 基尼系數(shù)
回歸樹算法.png
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市弦聂,隨后出現(xiàn)的幾起案子鸟辅,更是在濱河造成了極大的恐慌,老刑警劉巖莺葫,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件匪凉,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡捺檬,警方通過查閱死者的電腦和手機(jī)再层,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來堡纬,“玉大人聂受,你說我怎么就攤上這事】靖洌” “怎么了蛋济?”我有些...
    開封第一講書人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)炮叶。 經(jīng)常有香客問我碗旅,道長(zhǎng),這世上最難降的妖魔是什么镜悉? 我笑而不...
    開封第一講書人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任祟辟,我火速辦了婚禮,結(jié)果婚禮上侣肄,老公的妹妹穿的比我還像新娘旧困。我一直安慰自己,他們只是感情好稼锅,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開白布叮喳。 她就那樣靜靜地躺著,像睡著了一般缰贝。 火紅的嫁衣襯著肌膚如雪馍悟。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,736評(píng)論 1 312
  • 那天剩晴,我揣著相機(jī)與錄音锣咒,去河邊找鬼侵状。 笑死,一個(gè)胖子當(dāng)著我的面吹牛毅整,可吹牛的內(nèi)容都是我干的趣兄。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼悼嫉,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼艇潭!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起戏蔑,我...
    開封第一講書人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤蹋凝,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后总棵,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體鳍寂,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年情龄,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了迄汛。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡骤视,死狀恐怖鞍爱,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情专酗,我是刑警寧澤硬霍,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站笼裳,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏粱玲。R本人自食惡果不足惜躬柬,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望抽减。 院中可真熱鬧允青,春花似錦、人聲如沸卵沉。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽史汗。三九已至琼掠,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間停撞,已是汗流浹背瓷蛙。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工悼瓮, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人艰猬。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓横堡,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親冠桃。 傳聞我的和親對(duì)象是個(gè)殘疾皇子命贴,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361