目錄：

4.1基本流程

4.2劃分選擇

4.3剪枝處理

4.4連續(xù)與缺失值

4.5多變量決策樹(shù)

4.1基本流程

決策樹(shù)（decision tree）是一個(gè)樹(shù)結(jié)構(gòu)（可以是二叉樹(shù)或者非二叉樹(shù)）溶诞。決策樹(shù)分為分類樹(shù)和回歸樹(shù)兩種果港，分類樹(shù)對(duì)離散變量做決策樹(shù)击你，回歸樹(shù)對(duì)連續(xù)變量做決策樹(shù)。

其中每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測(cè)試，每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放在一個(gè)類別。使用決策樹(shù)進(jìn)行決策的過(guò)程就是從根節(jié)點(diǎn)開(kāi)始母怜，測(cè)試待分類項(xiàng)中相應(yīng)的特征屬性，并按照其值選擇輸出分支缚柏，知道到達(dá)葉子節(jié)點(diǎn)苹熏，將葉子節(jié)點(diǎn)存放的類別作為決策結(jié)果。

決策樹(shù)學(xué)習(xí)的目的是為 了產(chǎn)生一棵泛化能力強(qiáng)币喧，即處理未見(jiàn)示例能力強(qiáng)的決策樹(shù)轨域，其基本流程遵循簡(jiǎn) 單且直觀的"分而治之" (divide-and-conquer)策略

決策樹(shù)算法原理：（主要分為三個(gè)部分）

第一，特征選擇

特征選擇是指從訓(xùn)練數(shù)據(jù)中眾多的特征中選擇一個(gè)特征作為當(dāng)前節(jié)點(diǎn)的分裂標(biāo)準(zhǔn)杀餐，如何選擇特征有著很多不同量化評(píng)估標(biāo)準(zhǔn)干发，從而衍生出不同的決策樹(shù)算法。

第二史翘，決策樹(shù)生成

根據(jù)選擇的特征評(píng)估標(biāo)準(zhǔn)枉长，從上至下遞歸地生成子節(jié)點(diǎn)，直到數(shù)據(jù)集不可分則停止決策樹(shù)停止生長(zhǎng)琼讽。樹(shù)結(jié)構(gòu)來(lái)說(shuō)搀暑，遞歸結(jié)構(gòu)是最容易理解的方式。

第三跨琳，決策樹(shù)的剪枝

決策樹(shù)容易過(guò)擬合，一般來(lái)需要剪枝桐罕，縮小樹(shù)結(jié)構(gòu)規(guī)則脉让，緩解過(guò)擬合，剪枝技術(shù)有預(yù)剪枝和后剪枝兩種功炮。

基本算法

決策樹(shù)的生成是一個(gè)遞歸過(guò)程溅潜。在決策樹(shù)基本算法中，有三種情形會(huì) 導(dǎo)致遞歸返回:?

(1) 當(dāng)前結(jié)點(diǎn)包含的樣本全屬于同一類別薪伏，無(wú)需劃分;?

(2) 當(dāng)前 屬性集為空滚澜，或是所有樣本在所有屬性上取值相同，無(wú)法劃分;?

(3) 當(dāng)前結(jié)點(diǎn)包 含的樣本集合為空嫁怀，不能劃分设捐。

關(guān)于決策樹(shù)學(xué)習(xí)基本算法的課外補(bǔ)充請(qǐng)參考深入學(xué)習(xí)決策樹(shù)算法原理 -博客園

4.2劃分選擇

4.21信息增益

由算法 4.2 可看出7 決策樹(shù)學(xué)習(xí)的關(guān)鍵是第 8 行，即如何選擇最優(yōu)劃分屬性（我們希望決策樹(shù)的分支結(jié)點(diǎn)所包含的樣 本盡可能屬于同一類別塘淑，即結(jié)點(diǎn)的"純度" (purity)越來(lái)越高.）

Claude Shannon 定義了熵（entropy）和信息增益(information gain)萝招。 下面先介紹一下概念：

熵（entropy）

在信息論與概率論中，熵（entropy）用于表示“隨機(jī)變量不確定性的度量”

在決策樹(shù)的算法中存捺，熵是一個(gè)非常非常重要的概念槐沼，一件事發(fā)生的概率越小，我們說(shuō)它蘊(yùn)含的信息量越大。

信息量熵的定義：

設(shè)X是一個(gè)有限狀態(tài)的離散型隨機(jī)變量岗钩，其概率分布為：

則隨機(jī)變量X的熵定義為：

隨機(jī)變量X的熵定義

　　熵越大纽窟，則隨機(jī)變量的不確定性越大。

　　當(dāng)隨機(jī)變量只有0和1兩種取值的時(shí)候兼吓，假設(shè)P（X=1）=p臂港，則有：

　　從而可知，當(dāng)p=0.5時(shí)周蹭，熵取值最大趋艘，隨機(jī)變量不確定性最大。如圖：

同理凶朗，條件熵（conditional entropy）：隨機(jī)變量X給定的條件下瓷胧，Y的條件概率分布的熵對(duì)X的數(shù)學(xué)期望

"信息熵" (information entropy)是度量樣本集合純度最常用的一種指標(biāo). 假定當(dāng)前樣本集合 D 中第 k 類樣本所占的比例為 Pk (k = 1,2,. . . , IYI)，則 D 的信息熵定義為：

Entt(D) 的值越小棚愤，則 D 的純度越高.

"信息增益"定義為：

信息增益

信息增益越大搓萧，則意味著使周屬性 α 來(lái)進(jìn)行劃分所獲得的"純 度提升"越大

對(duì)于判斷西瓜好壞問(wèn)題上，屬于二分類問(wèn)題(Y=2),Pk宛畦，k=1（好瓜）瘸洛，k=2（不是好瓜），根結(jié)點(diǎn)包含 D 中的所有樣例次和，其中正例占 P1 =8/17反肋，反例占P2 =9/17；代入可得Ent(D)

同理踏施，若使用該屬性對(duì) D 進(jìn)行劃分石蔗，則可得到 3 個(gè)子集，分別記為: D1 (色澤=青綠)畅形， D2 (色澤2 烏黑)养距， D3 (色澤=淺白).?

子集 D1 包含編號(hào)為 {1，4, 6, 10, 13, 17} 的 6 個(gè)樣例日熬，其中正例占 p1=3/6棍厌， 反例占p2=3/6; D2 包含編號(hào)為 {2， 3, 7, 8, 9, 15} 的 6 個(gè)樣例竖席，其中正耘纱、反例分 別占 Pl = 4/6， P2 = 2/6; D3 包含編號(hào)為 {5毕荐， 11, 12, 14, 16} 的 5 個(gè)樣例揣炕，其中正、 反例分別占 p1=1/5东跪，p2=4/5.根據(jù)式(4.1)可計(jì)算出用"色澤"劃分之后所獲得 的 3 個(gè)分支結(jié)點(diǎn)的信息熵畸陡。Ent（D1）鹰溜、Ent(D2)、Ent（D3)

于是丁恭，根據(jù)式(4.2)可計(jì)算出屬性"色澤"的信息增益為：

Dv,? v=1,2,3

類似的曹动，我們可計(jì)算出其他屬性的信息增益:

Gain(D，根蒂) = 0.143; Gain(D牲览，敲聲) = 0.141; Gain(D墓陈，紋理) = 0.381; Gain(D，臍部) = 0.289; Gain(D第献， 觸感) = 0.006.顯然贡必，屬性"紋理"的信息增益最大?于是它被選為劃分屬性.圖 4.3 給出 了基于"紋理"對(duì)根結(jié)點(diǎn)進(jìn)行劃分的結(jié)果，各分支結(jié)點(diǎn)所包含的樣例子集顯示在結(jié)點(diǎn)中.

然后庸毫，決策樹(shù)學(xué)習(xí)算法將對(duì)每個(gè)分支結(jié)點(diǎn)做進(jìn)一步劃分.以圖 4.3 中第一 個(gè)分支結(jié)點(diǎn)( "紋理=清晰" )為例仔拟，該結(jié)點(diǎn)包含的樣例集合 D1 中有編號(hào)為 {1，2, 3, 4, 5, 6, 8, 10, 15} 的 9 個(gè)樣例飒赃，可用屬性集合為{色澤利花，根蒂，敲聲载佳，臍部7,觸感(因?yàn)椤凹y理”已經(jīng)確定炒事，就不用計(jì)算”紋理“)}.基于 D1 計(jì)算出各屬性的信息增益;三個(gè)信息增益值最大的屬性（"根蒂"、 "臍部"蔫慧、 "觸感"）挠乳，類似的，對(duì)每個(gè)分支結(jié)點(diǎn)進(jìn)行上述操作姑躲，最終得到的 決策樹(shù)如圈 4.4 所示.

小結(jié)：

基于數(shù)據(jù)信息生成決策樹(shù)步驟：

1.算出以每個(gè)屬性劃分之后所獲得的分支結(jié)點(diǎn)的信息熵睡扬，多少分支（多少個(gè)屬性值）就多少個(gè)信息熵。（計(jì)算公式參考公式4.1）

2.從而算出每個(gè)屬性的信息增益（計(jì)算公式參考公式4.2）

3.求出信息增益最大的那個(gè)屬性為根節(jié)點(diǎn)肋联，對(duì)每個(gè)分支結(jié)點(diǎn)做進(jìn)一步劃分。以其屬性值分類刁俭，重復(fù)上面兩步的方法橄仍，算出各分支最大信息增益的屬性（不用算上一分支的屬性）

4.類似的，層層算出牍戚，對(duì)每個(gè)分支結(jié)點(diǎn)進(jìn)行上述操作侮繁，最終得到?jīng)Q策樹(shù)。

增益率：

稱為屬性 α 的"固有值" (intrinsic value) [Quinlan, 1993J. 屬性 α 的可能 取值數(shù)目越多(即 V 越大)如孝，則 IV(α) 的值通常會(huì)越大宪哩。

基尼指數(shù)

直觀來(lái)說(shuō)， Gini(D) 反映了從數(shù)據(jù)集 D 中隨機(jī)抽取兩個(gè)樣本第晰，其類別標(biāo)記 不一致的概率.因此锁孟， Gini(D) 越小彬祖，則數(shù)據(jù)集 D 的純度越高.

采用與式(4.2)相同的符號(hào)表示，屬性 α 的基尼指數(shù)定義為：

基尼指數(shù)

4.3 剪枝處理

剪枝(pruning)是決策樹(shù)學(xué)習(xí)算法對(duì)付"過(guò)擬合"的主要手段品抽，決策樹(shù)剪枝的基本策略有"預(yù)剪枝" (prepruning)和"后剪枝"(post" pruning) [Quinlan, 1993].

本節(jié)假定采用留出法储笑，即預(yù)留一部分?jǐn)?shù)據(jù)用作"驗(yàn)證集"以進(jìn)行性 能評(píng)估.例如對(duì)表 4.1 的西瓜數(shù)據(jù)集 2札我們將其隨機(jī)劃分為兩部分：

留出法得到的數(shù)據(jù)

4.3.1 預(yù)剪枝

我們先討論預(yù)剪枝.基于信息增益準(zhǔn)則，我們會(huì)選取屬性"臍部"來(lái)對(duì)訓(xùn) 練集進(jìn)行劃分圆恤，并產(chǎn)生 3 個(gè)分支突倍。在劃分之前，所有樣例集中在根結(jié)點(diǎn).若不進(jìn)行劃分盆昙，則根據(jù)算法 4.2 第 6 行羽历，該結(jié)點(diǎn)將被標(biāo)記為葉結(jié)點(diǎn)，其類別標(biāo)記為訓(xùn)練樣例數(shù)最多的類別淡喜，假設(shè)我們將這個(gè)葉結(jié)點(diǎn)標(biāo)記為"好瓜"用表 4.2 的驗(yàn)證集對(duì)這個(gè)單結(jié)點(diǎn)決策樹(shù)進(jìn)行評(píng)估?則編號(hào)為 {4秕磷，5，8} 的樣例被分類正確?另外 4 個(gè)樣例分類錯(cuò)誤拆火，于是跳夭，驗(yàn)證集精度為3/7 x 100% = 42.9%

在用屬性"臍部"劃分之后，圖 4.6 中的結(jié)點(diǎn)②们镜、③币叹、④分別包含編 號(hào)為 {1， 2模狭， 3颈抚， 14}、 {6嚼鹉， 7贩汉， 15， 17}锚赤、 {10匹舞， 16} 的訓(xùn)練樣例，因此這 3 個(gè)結(jié)點(diǎn)分別 被標(biāo)記為葉結(jié)點(diǎn)"好瓜"线脚、 "好瓜"赐稽、 "壞瓜"此時(shí)，驗(yàn)證集中編號(hào)為 {4浑侥， 5姊舵， 8，11寓落， 12} 的樣例被分類正確括丁，驗(yàn)證集精度為5/7 x 100% = 71.4% > 42.9% 于是，用"臍部"進(jìn)行劃分得以確定.

然后伶选，決策樹(shù)算法應(yīng)該對(duì)結(jié)點(diǎn)②進(jìn)行劃分史飞，基于信息增益準(zhǔn)則將挑選出劃 分屬性"色澤"然而尖昏，在使用"色澤"劃分后，計(jì)算各葉節(jié)點(diǎn)的驗(yàn)證集精度祸憋，與劃分前比較会宪。若精度大于劃分前的，則進(jìn)行下一級(jí)劃分蚯窥，反之則終止劃分掸鹅。

優(yōu)點(diǎn)：預(yù)剪枝不僅降低的過(guò)擬合的風(fēng)險(xiǎn)，還減少了決策樹(shù)訓(xùn)練時(shí)間和測(cè)試時(shí)間的開(kāi)銷拦赠。

缺點(diǎn)：有些分支的當(dāng)前劃分雖不能提升泛化性能巍沙、甚至可能導(dǎo)致泛化性能暫時(shí)下降?但在其基礎(chǔ)上進(jìn)行的后續(xù)劃分卻有可能導(dǎo)致性能顯著提高; 預(yù)剪枝基于"貪心"本質(zhì)禁止這些分支展開(kāi)，給預(yù)剪枝決策樹(shù)帶來(lái)了 欠擬含的風(fēng)險(xiǎn)荷鼠。

4.3.2 后剪枝

后剪枝先從訓(xùn)練集生成一棵完整決策樹(shù)句携？例如基于表 4.2 的數(shù)據(jù)我們得到 如圖 4.5 所示的決策樹(shù).易知， 該決策樹(shù)的驗(yàn)證集精度為 42.9%允乐。

后剪枝首先考察圖 4.5 中的結(jié)點(diǎn)⑥.若將其領(lǐng)銜的分支剪除矮嫉，則相當(dāng)于 把⑤替換為葉結(jié)點(diǎn).替換后的葉結(jié)點(diǎn)包含編號(hào)為 {7， 15} 的訓(xùn)練樣本牍疏，于是蠢笋，該葉結(jié)點(diǎn)的類別標(biāo)記為"好瓜"，此時(shí)決策樹(shù)的驗(yàn)證集精度提高至 57.1%. 于是鳞陨， 后剪枝策略決定剪枝昨寞，如圖 4.7 所示：

然后考察結(jié)點(diǎn)⑤，若將其領(lǐng)銜的子樹(shù)替換為葉結(jié)點(diǎn)厦滤，則替換后的葉結(jié)點(diǎn)包含編號(hào)為 {6援岩， 7， 15} 的訓(xùn)練樣例掏导，葉結(jié)點(diǎn)類別標(biāo)記為"好瓜'享怀，此時(shí)決策樹(shù)驗(yàn)證集精度仍為 57.1%.。于是趟咆，可以不進(jìn)行剪枝.

以此類推添瓷，直到剪到結(jié)點(diǎn)①。

優(yōu)點(diǎn)：后剪枝決策樹(shù)的欠擬合風(fēng)險(xiǎn)很小忍啸，泛化性能往往優(yōu)于預(yù) 剪枝決策樹(shù)

缺點(diǎn)：后剪枝過(guò)程是在生成完全決策樹(shù)之后進(jìn)行的仰坦， 并且要自底向上地對(duì)樹(shù)中的所有非葉結(jié)點(diǎn)進(jìn)行逐一考察履植，因此其訓(xùn)練時(shí)間開(kāi)銷比未剪枝決策樹(shù)和預(yù)剪枝決策樹(shù)都要大得多计雌。

4.4連續(xù)與缺失值

4.4.1 連續(xù)值處理

給定樣本集 D 和連續(xù)屬性 α，假定 α 在 D 上出現(xiàn)了 n個(gè)不同的取值玫霎，將這 些值從小到大進(jìn)行排序凿滤，記為 {α1 α2 . . 妈橄， an}，在區(qū)間[ai翁脆， ai+1) 中取任意值所產(chǎn)生的劃分結(jié)果相同眷蚓。因此，對(duì)連續(xù)屬性 a反番， 我們可考察包含 n-1 個(gè)元素的候選劃分點(diǎn)集合沙热。即把區(qū)間 [ai， ai+1) 的中位點(diǎn){（ai+ai+1）/2 }出作為候選劃分點(diǎn)罢缸。

中位點(diǎn)

Gain(D篙贸， a, t) 是樣本集 D 基于劃分點(diǎn) t 工分后的信息增益.

對(duì)屬性"密度"，枫疆，該屬性的候選劃分點(diǎn)集合包含 16 個(gè)候選值: T密度 {0.244爵川， 0.294, 0.351, 0.381, 0.420, 0.459, 0.518, 0.574, 0.600, 0.621, 0.636, 0.648, 0.661, 0.681, 0.708, 0.746}。 由式(4.8) 可計(jì)算 出屬性"密度"的信息增益為 0.262息楔，對(duì)應(yīng)于劃分點(diǎn) 0.381（根據(jù)表中是否好瓜的最小臨界值求出）寝贡。

同理，對(duì)屬性"含糖率"其候選劃分點(diǎn)集合也包含 16 個(gè)候選值:'L含糖率=

{0.049, 0.074, 0.095, 0.101, 0.126, 0.155, 0.179, 0.204, 0.213, 0.226, 0.250, 0.265, 0.292, 0.344, 0.373, 0.418}. 類似的值依，根據(jù)式(4.8)可計(jì)算出其信息增益為 0.349圃泡， 對(duì)應(yīng)于劃分點(diǎn) 0.126。（根據(jù)表中是否好瓜的最小臨界值求出）

接下來(lái)鳞滨，根據(jù)第二節(jié)學(xué)習(xí)的方法步驟（離散型）洞焙，求出決策樹(shù)。

需注意的是拯啦，與離散屬性不同澡匪，若當(dāng)前結(jié)點(diǎn)劃分屬性為連續(xù)屬性，該屬性還 可作為其后代結(jié)點(diǎn)的劃分屬性褒链。例如在父結(jié)點(diǎn)上使用了 "密度'＜=0.381" 唁情，不會(huì)禁 止在子結(jié)點(diǎn)上使用"密度＜=0.294" 根时。

4.4.2 缺失值處理

如果簡(jiǎn)單地放棄不完整樣本帽蝶，僅使用無(wú)缺失值的樣本來(lái)進(jìn)行學(xué)習(xí)，顯然是對(duì)數(shù)據(jù)信息極大的浪費(fèi)趟脂。

我們需解決兩個(gè)問(wèn)題: (1) 如何在屬性值缺失的情況 下進(jìn)行劃分屬性選擇? (2) 給定劃分屬性兵迅，若樣本在該屬性上的值缺失抢韭，如何對(duì)樣本進(jìn)行劃分?

給定訓(xùn)練集 D 和屬性 α，令 D 表示 D 中在屬性 α 上沒(méi)有缺失值的樣本子 集恍箭。對(duì)問(wèn)題(1)刻恭，顯然我們僅可根據(jù) b 來(lái)判斷屬性 α 的優(yōu)劣.假定屬性 α 有 V 個(gè) 可取值 {α1，α2 …， αV}鳍贾， 令 D~V 表示 D ~中在屬性 a上取值為av的樣本子集鞍匾，D~k 表示 b 中屬于第 k 類 (k = 1,2, .. . , lyl)的樣本子集。

w表示權(quán)重

對(duì)屬性 α骑科， ρ 表辰無(wú)缺失值樣本所占的比例橡淑， Pk 表示無(wú)缺失值樣本中 第 k 類所占的比例?ι 則表示無(wú)缺失值樣本中在屬性 α 上取值曠的樣本所占的比例。

缺失值類型的信息增益

根結(jié)點(diǎn)包含樣本集 D 中全部 17 個(gè)樣例咆爽，各樣例的權(quán)值 均為1.以屬性"色澤"為例梁棠，該屬性上無(wú)缺失值的樣例子集 b 包含編號(hào)為 {2， 3斗埂， 4掰茶， 6， 7蜜笤， 8濒蒋， 9， 10把兔， 11沪伙， 12， 14县好， 15围橡， 16， 17} 的 14 個(gè)樣例.顯然缕贡，D~的信息熵為Ent（D~）翁授，再求出子集Ent（D1）、Ent（D2）晾咪、Ent（D3）收擦，求得Gain（D~，屬性）谍倦，最后求得屬性信息增益Gain（D塞赂，屬性）=p（完整的占全部的比例）*Gain（D~，屬性）

求得各屬性的信息增益后昼蛀，再根據(jù)前面的方法宴猾，劃分過(guò)程遞歸執(zhí)行，求得決策樹(shù)叼旋。

小結(jié)：

信息增益的三個(gè)表達(dá)式：

離散型普通信息增益

連續(xù)值的信息增益

含缺失值的信息增益

4.5 多變量決策樹(shù)

若我們把每個(gè)屬性視為坐標(biāo)空間中的一個(gè)坐標(biāo)軸仇哆，則 d 個(gè)屬性描述的樣本 就對(duì)應(yīng)了 d 維空間中的一個(gè)數(shù)據(jù)點(diǎn)。

若能使用斜的劃分邊界夫植，如圖 4.12 中紅色線段所示讹剔，則決策樹(shù)模型將大為 簡(jiǎn)化"多變量決策樹(shù)" (multivariate decision tree)，非葉結(jié)點(diǎn)不再是僅對(duì)某個(gè)屬性，而是對(duì)屬性的線性組合進(jìn)行測(cè)試辟拷。

每個(gè)非葉結(jié)點(diǎn)是一個(gè)形如叫線性分類器，其中是屬性的權(quán)重阐斜，和 t 可在該結(jié)點(diǎn)所含的樣本集和屬性集上學(xué)得.

在多變量決策樹(shù)的學(xué)習(xí)過(guò)程中衫冻， 不是為每個(gè)非葉結(jié)點(diǎn)尋找一個(gè)最優(yōu)劃分屬性，而是試圖建立一個(gè)合適的線性分類器谒出。

詳細(xì)了解線性學(xué)習(xí)器隅俘，請(qǐng)點(diǎn)擊CS231n——機(jī)器學(xué)習(xí)算法——線性分類（上: 線性分類器）