第4章 分類：基本概念、決策樹(shù)與模型評(píng)估

1、第4章 分類：基本概念、決策樹(shù)與模型評(píng)估分類：基本概念、決策樹(shù)與模型評(píng)估 4.1預(yù)備知識(shí) 4.2解決分類問(wèn)題的一般方法 4.3決策樹(shù)歸納 4.4模型的過(guò)分?jǐn)M合 4.5評(píng)估分類器的性質(zhì) 4.6比較分類器的方法 分類任務(wù)：確定對(duì)象屬于哪個(gè)預(yù)定義的目標(biāo)類 例子： 1、根據(jù)電子郵件的標(biāo)題和內(nèi)容檢查 出垃圾郵件。 2、根據(jù)星系的形狀對(duì)它們分類。 螺旋狀的星系 橢圓狀的星系 一、預(yù)備知識(shí)一、預(yù)備知識(shí) 分類任務(wù)的輸入數(shù)據(jù)是記錄的集合。每條記錄也稱實(shí)例或者樣例， 用元組（x, y）表示，其中x是屬性的集合，而y是一個(gè)特殊的屬性， 指出樣例的類標(biāo)號(hào)（也成為分類屬性或目標(biāo)屬性）。 分類？回歸？ 分類（classi

2、fication） 通過(guò)學(xué)習(xí)得到一個(gè)目標(biāo)函數(shù)（target function） ， 也成為分類模 型（classification model），把每個(gè)屬性集x映射到一個(gè)預(yù)先定義的類標(biāo) 號(hào)y。 f 目的： 1、描述性建模 分類模型可以作為解釋性的工具，用于區(qū)分不同類中的對(duì)象。 2、預(yù)測(cè)性建模 分類模型還可以用于預(yù)測(cè)未知記錄的類標(biāo)號(hào)。 名字名字體溫體溫表皮表皮 覆蓋覆蓋 胎生胎生水生水生 動(dòng)物動(dòng)物 飛行飛行 動(dòng)物動(dòng)物 有腿有腿冬眠冬眠類標(biāo)類標(biāo) 號(hào)號(hào) 毒蜥冷血鱗片否否否是是？ 輸入屬性集（x） 分類模型 輸出類標(biāo)號(hào)（y） 分類器的任務(wù)：根據(jù)輸入屬性集x確定類標(biāo)號(hào)y 分類技術(shù)非常適合預(yù)測(cè)或描述二元或

3、標(biāo)稱類型的數(shù)據(jù)集，對(duì)序數(shù)分類不 太有效，因?yàn)榉诸惣夹g(shù)不考慮隱含在目標(biāo)類中的序關(guān)系。 分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。 分類技術(shù) 決策樹(shù)分類法決策樹(shù)分類法 基于規(guī)則的分類法基于規(guī)則的分類法 神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò) 支持向量機(jī)支持向量機(jī) 這些技術(shù)都使用一種學(xué)習(xí)算法確定分類模型，修改這個(gè)模型能夠很好地 擬合輸入數(shù)據(jù)中類標(biāo)號(hào)和屬性集之間的聯(lián)系。學(xué)習(xí)算法得到的模型不僅 要很好地?cái)M合輸入數(shù)據(jù)，還要能夠正確地預(yù)測(cè)未知樣本的類標(biāo)號(hào)。 訓(xùn)練算法的目標(biāo)：建立具有很好的泛化能力的模型。 二、解決分類問(wèn)題的一般方法二、解決分類問(wèn)題的一般方法 樸素貝葉斯分類法樸素貝葉斯分類法 訓(xùn)練集：由類標(biāo)號(hào)已知的記錄構(gòu)

4、成 檢驗(yàn)集：由類標(biāo)號(hào)未知的記錄構(gòu)成 預(yù)測(cè)的類預(yù)測(cè)的類 類=1類=0 實(shí)際的類類=1 類=0 00 f 01 f 10 f 11 f 二類問(wèn)題的混淆矩陣 ij f ij 表中每個(gè)表項(xiàng) 表示實(shí)際類標(biāo)號(hào)為 但是被預(yù)測(cè)為類 的記 錄數(shù)。被分類模型正確預(yù)測(cè)的樣本總數(shù)是 ，而被錯(cuò)誤 預(yù)測(cè)的樣本總數(shù)是 。 0011 ff 0110 ff 雖然混淆矩陣提供衡量分類模型的信息，但是用一個(gè)數(shù)匯總這些信 息更便于比較不同模型的性能。為實(shí)現(xiàn)這一目的，可以使用性能度 量（performance metric），如準(zhǔn)確率（accuracy），其定義如下： 同樣，分類模型的性能也可以用錯(cuò)誤率（error rate）來(lái)表示，

5、其定 義如下： 00011011 0110 ffff ff 預(yù)測(cè)總數(shù) 錯(cuò)誤預(yù)測(cè)數(shù) 錯(cuò)誤率 目標(biāo)：尋求最高的準(zhǔn)確率或者最低的錯(cuò)誤率 00011011 0011 ffff ff 預(yù)測(cè)總數(shù) 正確預(yù)測(cè)數(shù) 準(zhǔn)確率 1、什么是決策樹(shù)？ 類似于流程圖的樹(shù)結(jié)構(gòu) 每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試 每個(gè)分枝代表一個(gè)測(cè)試輸出 每個(gè)葉節(jié)點(diǎn)代表類或類分布 三、決策樹(shù)（三、決策樹(shù)（decision tree）歸納）歸納 3、決策樹(shù)的使用：對(duì)未知樣本進(jìn)行分類 通過(guò)將樣本的屬性值與決策樹(shù)相比較 2、決策樹(shù)的生成由兩個(gè)階段組成 決策樹(shù)構(gòu)建 開(kāi)始時(shí)，所有的訓(xùn)練樣本都在根節(jié)點(diǎn) 遞歸通過(guò)選定的屬性，來(lái)劃分樣本 （必須是離散值） 樹(shù)

6、剪枝 許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn)，樹(shù)剪枝試圖檢測(cè)和剪 去這種分枝 根結(jié)點(diǎn)（root node）：它沒(méi)有入邊，但是有零條或多條出邊。 內(nèi)部結(jié)點(diǎn)（internal node）：恰好有一條入邊和兩條或多條出邊。 葉節(jié)點(diǎn)（leaf node）或終結(jié)點(diǎn)（terminal node）：恰好有一條入邊， 但沒(méi)有出邊。 葉結(jié)點(diǎn) 根結(jié)點(diǎn) 內(nèi)部結(jié)點(diǎn) 體溫 胎生 非哺乳動(dòng) 物 哺乳動(dòng)物 非哺乳動(dòng) 物 恒溫 否 冷血 是 一旦構(gòu)造了決策樹(shù)，對(duì)檢驗(yàn)記錄進(jìn)行分類就很容易。從樹(shù)的根結(jié)點(diǎn) 開(kāi)始，將測(cè)試條件用于檢驗(yàn)記錄，根據(jù)測(cè)試結(jié)果選擇適當(dāng)?shù)姆种?。沿著?分支或者到達(dá)另一個(gè)內(nèi)部結(jié)點(diǎn)，使用新的測(cè)試條件，或者到達(dá)一個(gè)

7、葉結(jié)點(diǎn)。 到達(dá)葉結(jié)點(diǎn)之后，葉結(jié)點(diǎn)的類標(biāo)號(hào)就被賦值給該檢驗(yàn)記錄。 名字名字體溫體溫胎生胎生類標(biāo)號(hào)類標(biāo)號(hào) 火烈鳥(niǎo)恒溫否？ 體溫 胎生 非哺乳 動(dòng)物 哺乳動(dòng) 物 非哺乳 動(dòng)物 恒溫 否 冷血 是 如何建立決策樹(shù) 對(duì)于給定的屬性集，可以構(gòu)造的決策樹(shù)的數(shù)目達(dá)指數(shù)級(jí)。 盡管某些決策樹(shù)比其他決策樹(shù)更準(zhǔn)確，但是由于搜索空間是 指數(shù)規(guī)模的，找出最佳決策樹(shù)在計(jì)算上是不可行的。 盡管如此，人們還是開(kāi)發(fā)了一些有效的算法，能夠在合 理的時(shí)間內(nèi)構(gòu)造出具有一定準(zhǔn)確率的次最優(yōu)決策樹(shù)。這些算 法通常都采用貪心策略。 有許多決策樹(shù)算法: （ID3ID3） （C4.5C4.5） (SLIQ(SLIQ， SPRINT)SPRINT)

8、 在Hunt算法中，通過(guò)將訓(xùn)練記錄相繼劃分成較純的子集，以遞歸方式 建立決策樹(shù)。設(shè) 是與結(jié)點(diǎn)t相關(guān)聯(lián)的訓(xùn)練記錄集，而 是類標(biāo)號(hào)，Hunt算法的遞歸定義如下。 t D , 21c yyyy （1）如果 中所有記錄都屬于同一個(gè)類 ，則t是葉結(jié)點(diǎn)，用 標(biāo)記。 t y t D t y （2）如果 中包含屬于多個(gè)類的記錄，則選擇一個(gè)屬性測(cè)試條件， 將記錄劃分成較小的子集。對(duì)于測(cè)試條件的每個(gè)輸出，創(chuàng)建一個(gè)子女 結(jié)點(diǎn)，并根據(jù)測(cè)試結(jié)果將 中的記錄分布到子女結(jié)點(diǎn)中。然后，對(duì)于 每個(gè)子女結(jié)點(diǎn)，遞歸地調(diào)用該算法。 t D t D Hunt算法 Tid有房者有房者婚姻狀況婚姻狀況年收入年收入拖欠貸款者拖欠貸款者 1是

9、單身125k否 2否已婚100k否 3否單身70k否 4是已婚120k否 5否離異95k是 6否已婚60k否 7是離異220k否 8否單身85k是 9否已婚75k否 10否單身90k是 拖欠貸款者=否拖欠貸款者=否拖欠貸款者=否 有房者 拖欠貸款者=否 有房者 拖欠貸款者=否 婚姻狀況 年收入 拖欠貸款者=是拖欠貸款者=否 (b) (c)(d) (a) 拖欠貸款者=否 有房者 拖欠貸款者=否 婚姻狀況 拖欠貸款者=是 是 是 否 否 否 是 單身離異 單身離異 已婚 已婚 =80k Hunt算法構(gòu)造決策樹(shù) 如果屬性值的每種組合都在訓(xùn)練數(shù)據(jù)中出現(xiàn)，并且每種組合都具有唯一的類 標(biāo)號(hào)，則Hunt算法

10、是有效的。但是對(duì)于大多數(shù)實(shí)際情況，這些假設(shè)太苛刻了， 因此，需要附加的條件來(lái)處理以下的情況： （1）算法的第二步所創(chuàng)建的子女結(jié)點(diǎn)可能為空，即不存在與這些結(jié)點(diǎn)相關(guān) 聯(lián)的記錄。如果沒(méi)有一個(gè)訓(xùn)練記錄包含這樣的結(jié)點(diǎn)相關(guān)聯(lián)的屬性值組合，這 種情形就可能發(fā)生。這時(shí)，該結(jié)點(diǎn)成為葉結(jié)點(diǎn)，類標(biāo)號(hào)為其父結(jié)點(diǎn)上訓(xùn)練記 錄中的多數(shù)類。 （2）在第二步，如果與 相關(guān)聯(lián)的所有記錄都具有相同的屬性值（目標(biāo)屬 性除外），則不可能進(jìn)一步劃分這些記錄。在這種情況下，該結(jié)點(diǎn)為葉結(jié)點(diǎn)， 其標(biāo)號(hào)為與該結(jié)點(diǎn)相關(guān)聯(lián)的訓(xùn)練記錄中的多數(shù)類。 t D 決策樹(shù)歸納的設(shè)計(jì)問(wèn)題 （1）如何分裂訓(xùn)練記錄？ （2）如何停止分裂過(guò)程？ 樹(shù)增長(zhǎng)過(guò)程的每個(gè)遞歸

11、步驟都必須選擇一個(gè)屬性測(cè)試條件，將 記錄劃分成較小的子集。為了實(shí)現(xiàn)這個(gè)步驟。算法必須提供為 不同類型的屬性指定測(cè)試條件的方法，并且提供評(píng)估每種測(cè)試 條件的客觀度量。 決策樹(shù)需要有結(jié)束條件，以終止決策樹(shù)的生長(zhǎng)過(guò)程。一個(gè)可能 的策略是分裂結(jié)點(diǎn)，直到所有的記錄都屬于同一個(gè)類，或者所 有的記錄都具有相同的屬性值。 表示屬性測(cè)試條件的方法 1、二元屬性 二元屬性的測(cè)試條件產(chǎn)生兩個(gè)可能的輸出。 體溫 恒溫冷血 二元屬性的測(cè)試條件 2、標(biāo)稱屬性 由于標(biāo)稱屬性有多個(gè)屬性值，它的測(cè)試條件可以用兩種方法表示。 婚姻狀 況 單身已婚離異 婚姻狀 況 已婚單身，離異 婚姻狀 況 離異單身，已婚 婚姻狀 況 單身已婚，

12、離異 多路劃分 二元?jiǎng)澐郑ㄍㄟ^(guò)屬性值分組） 3、序數(shù)屬性 序數(shù)屬性也可以產(chǎn)生二元或多路劃分，只要不違背序數(shù)屬性值的有序 性，就可以對(duì)屬性值進(jìn)行分組。 襯衣尺碼 小號(hào)， 中號(hào) 大號(hào)， 加大號(hào) 襯衣尺碼 小號(hào)中號(hào)， 加大號(hào) 襯衣尺碼 小號(hào)， 大號(hào) 中號(hào)， 加大號(hào) （a）（b）（c） 4、連續(xù)屬性 對(duì)于連續(xù)屬性來(lái)說(shuō)，測(cè)試條件可以是具有二元輸出的比較測(cè)試 或 也可以是具有形如 輸出的范圍查詢。 )(vA )(vA ), 2 , 1( 1 kivAv ii 年收入 80k （a） （b） 年收入 是 否10k 10k,25k 10k 25k,50k50k,80k 連續(xù)屬性的測(cè)試條件 有很多度量可以用來(lái)確

13、定劃分記錄的最佳方法，這些度量用劃分前和劃分 后的記錄的類分布定義。 選擇最佳劃分的度量 設(shè) 表示給定結(jié)點(diǎn)t中屬于類i的記錄所占的比例，有時(shí)，我們省略結(jié)點(diǎn)t， 直接用 表示該比例。在兩類問(wèn)題中，任意結(jié)點(diǎn)的類分布都可以記作 其中 。 )|(tip ),( 10 pp 01 1pp i p 性別 男 女 車型 家用 運(yùn)動(dòng) 豪華 C0:6 C1:4 C0:4 C1:6 C0:1 C1:3 C0:8 C1:0 C0:1 C1:7 （b）（a） C0:1 C1:0 C0:1 C1:0 C0:0 C1:1 C0:0 C1:1 顧客ID v1 v10 v20 v11 （c） 選擇最佳劃分的度量通常是根據(jù)劃分

14、后子女結(jié)點(diǎn)不純性的度量。不純的 程度越低，類分布就越傾斜。例如（0,1）的結(jié)點(diǎn)具有零不純性，而均衡 分布（0.5, 0.5）的結(jié)點(diǎn)具有最高的不純性。不純性度量的例子包括： 1 0 2 )|(log)|()( c i tiptiptEntropy 1 0 2 )|(1)( c i tiptGini )|(max1)(_Ctipterrorionlassificat i 熵： 基尼指數(shù)： 分類誤差： 其中c是類的個(gè)數(shù)，并且在計(jì)算熵時(shí)， 00log2O 結(jié)點(diǎn)結(jié)點(diǎn)N1計(jì)數(shù)計(jì)數(shù) 類=00 類=16 結(jié)點(diǎn)結(jié)點(diǎn)N3計(jì)數(shù)計(jì)數(shù) 類=03 類=13 結(jié)點(diǎn)結(jié)點(diǎn)N2計(jì)數(shù)計(jì)數(shù) 類=01 類=15 0)6/6()6/0(

15、1 22 Gini 0)6/6(log)6/6()6/0(log)6/0( 22 Entropy 06/6 , 6/0max1Error 278. 0)6/5()6/1 (1 22 Gini 650. 0)6/5(log)6/5()6/1 (log)6/1 ( 22 Entropy 167. 06/5 , 6/1max1Error 5 . 0)6/3()6/3(1 22 Gini 1)6/3(log)6/3()6/3(log)6/3( 22 Entropy 5 . 06/3 , 6/3max1Error 二元分類問(wèn)題不純性度量之間的比較 不同的不純性度量是一致的，但是作為測(cè)試條件的屬性選擇仍然

16、 因不純性度量的選擇而異。 00.10.20.30.40.50.60.70.80.91 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 p 熵 Gini 分 類 誤 差 為確定測(cè)試條件的效果，我們需要比較父結(jié)點(diǎn)（劃分前）的不純性程度和 子女結(jié)點(diǎn)（劃分后）的不純性程度，它們的差越大，測(cè)試條件的效果就越 好。增益 是一種可以用來(lái)確定劃分效果的標(biāo)準(zhǔn)： k j j j vI N vN parentI 1 )( )( )( )(I其中， 是給定結(jié)點(diǎn)的不純性度量，N是父結(jié)點(diǎn)上的記錄總數(shù)，k是 屬性值的個(gè)數(shù)， 是與子女結(jié)點(diǎn) 相關(guān)聯(lián)的記錄個(gè)數(shù)。)( j vN j v 決策樹(shù)算法

17、選擇最大化增益的測(cè)試條件。 B 是否 結(jié)點(diǎn) N1結(jié)點(diǎn) N2 A 是否 結(jié)點(diǎn) N1結(jié)點(diǎn) N2 父結(jié)點(diǎn)父結(jié)點(diǎn) C06 C16 Gini=0.500 N1N1N2N2 C042 C133 Gini=0.486 N1N1N2N2 C015 C142 Gini=0.371 1、二元屬性的劃分 2、標(biāo)稱屬性的劃分 車型車型 運(yùn)動(dòng)，豪華家用 C091 C173 Gini0.468 車型車型 運(yùn)動(dòng)家用，豪華 C082 C1010 Gini0.167 車型車型 家用運(yùn)動(dòng)豪華 C0181 C1307 Gini0.163 （a）二元?jiǎng)澐?(b)多路劃分 標(biāo)稱屬性可以產(chǎn)生二元?jiǎng)澐只蛘叨嗦穭澐?3、連續(xù)屬性的劃分 1.

18、使用二元?jiǎng)澐?2.劃分點(diǎn)v選擇 N個(gè)記錄中所有屬性值作為劃分點(diǎn) 3.對(duì)每個(gè)劃分進(jìn)行類計(jì)數(shù), A v 和 A v 4.計(jì)算每個(gè)候選點(diǎn)v的Gini指標(biāo)，并從中選擇具有最小值的候選劃分點(diǎn) 5.時(shí)間復(fù)雜度為O(n2) 降低計(jì)算復(fù)雜性的方法: 1.將記錄進(jìn)行排序 2.從兩個(gè)相鄰的排過(guò)序的屬性值之間選擇中間值作為劃分點(diǎn) 3.計(jì)算每個(gè)候選點(diǎn)的Gini值 4.時(shí)間復(fù)雜度為O（NlogN） 4、增益率 熵和Gini指標(biāo)等不純性度量趨向有利于具有大量不同值的屬性。 性別 男 女 車型 家用 運(yùn)動(dòng) 豪華 C0:6 C1:4 C0:4 C1:6 C0:1 C1:3 C0:8 C1:0 C0:1 C1:7 （b）（a）

19、 測(cè)試條件“車型”要比測(cè)試條件“性別”要好，因?yàn)樗a(chǎn)生了更純的派生結(jié)點(diǎn)。 測(cè)試條件“顧客ID”相比前兩個(gè)產(chǎn)生更純的劃分，但是它卻不是一個(gè)有預(yù)測(cè)性的 屬性，因?yàn)榕c每個(gè)劃分相關(guān)聯(lián)的記錄太少，以致不能作出可靠的預(yù)測(cè)。 C0:1 C1:0 C0:1 C1:0 C0:0 C1:1 C0:0 C1:1 顧客ID v1 v10 v20 v11 （c） 如何解決？如何解決？ 第一種策略：限制測(cè)試條件只能是二元?jiǎng)澐帧?第二種策略：修改評(píng)估劃分的標(biāo)準(zhǔn)，把屬性測(cè)試條件產(chǎn)生的輸出數(shù)也考慮 進(jìn)去。 例如：CART就是采用這樣的策略。 例如：決策樹(shù)算法C4.5采用增益率（gain ratio）的劃分標(biāo)準(zhǔn)來(lái) 評(píng)估劃分。 I

20、nfoSplit ratioGain info 是劃分的總數(shù)，而其中，劃分信息k)()logP(v-InfoSplit 1i 2i k i vP 決策樹(shù)歸納特點(diǎn)的總結(jié) 1、決策樹(shù)歸納是一種構(gòu)建分類模型的非參數(shù)方法。 2、找到最佳的決策樹(shù)是NP完全問(wèn)題。 3、已開(kāi)發(fā)的構(gòu)建決策樹(shù)技術(shù)不需要昂貴的計(jì)算代價(jià)，即使訓(xùn)練集非常 大，也可以快速建立模型。 4、決策樹(shù)相對(duì)容易解釋，特別是小型的決策樹(shù)。 5、決策樹(shù)是學(xué)習(xí)離散值函數(shù)的典型代表。 6、決策樹(shù)算法對(duì)于噪聲的干擾具有相當(dāng)好的魯棒性。 7、冗余屬性不會(huì)對(duì)決策樹(shù)的準(zhǔn)確率造成不利的影響。 8、由于大多數(shù)決策樹(shù)算法都采用自頂向下的遞歸劃分方法，因此沿著 樹(shù)向下

21、，記錄會(huì)越來(lái)越少。 9、子樹(shù)可能在決策樹(shù)中重復(fù)多次，這使得決策樹(shù)過(guò)于復(fù)雜，并且可能 更難解釋。 10、目前為止，本章介紹的測(cè)試條件每次都只涉及一個(gè)屬性。 二維數(shù)據(jù)集的決策樹(shù)及其邊界示例 P QR S01 01 Q S0 01 使用僅涉及單個(gè)屬性的測(cè)試條件不能有效劃分的數(shù)據(jù)集的例子 斜決策樹(shù)（oblique decision tree）可以克服以上的局限，因?yàn)樗试S測(cè)試條 件涉及多個(gè)屬性。上圖中的數(shù)據(jù)集可以很容易地用斜決策樹(shù)表示，該決策樹(shù) 只有一個(gè)結(jié)點(diǎn)，其測(cè)試條件為： 1 yx 缺點(diǎn)：盡管這種技術(shù)有更強(qiáng)的表達(dá)能力，并且能夠產(chǎn)生更緊湊的決策樹(shù)， 但是為給定的結(jié)點(diǎn)找出最佳測(cè)試條件的計(jì)算可能是相當(dāng)復(fù)雜

22、的。 x + y 1 Class = + Class = 構(gòu)造歸納（constructive induction） 提供另一種將數(shù)據(jù)劃分成齊次非矩形區(qū)域的方法，該方法創(chuàng)建復(fù)合 屬性，代表已有屬性的算術(shù)或邏輯組合。新屬性提供了更好的類區(qū)分能 力，并在決策樹(shù)歸納之前就增廣到數(shù)據(jù)集中。 與決策樹(shù)不同，構(gòu)造歸納不需要昂貴的花費(fèi)，因?yàn)樵跇?gòu)造決策樹(shù)之 前，它只需要一次性地確定屬性的所有相關(guān)組合，相比之下，在擴(kuò)展每 個(gè)內(nèi)部結(jié)點(diǎn)時(shí)，斜決策樹(shù)都需要?jiǎng)討B(tài)地確定正確的屬性組合。然而構(gòu)造 歸納會(huì)產(chǎn)生冗余的屬性，因?yàn)樾聞?chuàng)建的屬性是已有屬性的組合。 11、研究表明不純性度量方法的選擇對(duì)決策樹(shù)算法的性能影響很小。 一個(gè)好的

23、分類模型必須具有低訓(xùn)練誤差和低泛化誤差。 四、模型的過(guò)分?jǐn)M合四、模型的過(guò)分?jǐn)M合 二維數(shù)據(jù)過(guò)分?jǐn)M合的例子 下圖所示的二維數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)屬于兩個(gè)類，分別標(biāo)記為類“o”和類 “+”，類“o”的數(shù)據(jù)點(diǎn)由三個(gè)高斯分布混合產(chǎn)生，而類“+”的數(shù)據(jù)點(diǎn) 用一個(gè)均勻分布產(chǎn)生。數(shù)據(jù)集中，總共有1200個(gè)數(shù)據(jù)點(diǎn)是屬于類“o”， 1800個(gè)數(shù)據(jù)點(diǎn)屬于類“+”，其中30%的點(diǎn)用于訓(xùn)練，剩下的70%用于檢 驗(yàn)。對(duì)訓(xùn)練集使用以Gini指標(biāo)作為不純性度量的決策樹(shù)方法。 具有兩個(gè)類的數(shù)據(jù)集的例子 當(dāng)決策樹(shù)很小時(shí)，訓(xùn)練誤差和檢驗(yàn)誤差都很大，這種情況稱作模型擬合不 足（model underfitting）。出現(xiàn)擬合不足的原因是模

24、型尚未學(xué)習(xí)到數(shù)據(jù)的真實(shí) 結(jié)構(gòu)，因此，模型在訓(xùn)練集和檢驗(yàn)集上的性能都很差。 一旦樹(shù)的規(guī)模變得太大，即使訓(xùn)練誤差還在降低，但是檢驗(yàn)誤差開(kāi)始增大， 這種現(xiàn)象稱為模型過(guò)分?jǐn)M合（model overfitting）。 訓(xùn)練誤差和檢驗(yàn)誤差 為理解過(guò)分?jǐn)M合現(xiàn)象，舉個(gè)例子：可以擴(kuò)展樹(shù)的葉結(jié)點(diǎn)，直到它完全擬合訓(xùn)練 數(shù)據(jù)。雖然這樣一顆復(fù)雜的樹(shù)的訓(xùn)練誤差為0，但是檢驗(yàn)誤差可能很大，因?yàn)樵摌?shù) 可能包含這樣的結(jié)點(diǎn)，它們偶然地?cái)M合訓(xùn)練數(shù)據(jù)中某些噪聲。這些結(jié)點(diǎn)降低了決策 樹(shù)的性能，因?yàn)樗麄儾荒芎芎玫姆夯綑z驗(yàn)樣本。 （a）包含11個(gè)葉結(jié)點(diǎn)的決策樹(shù)（b）包含24個(gè)葉結(jié)點(diǎn)的決策樹(shù) 過(guò)分?jǐn)M合與擬合不足是兩種與模型復(fù)雜度有關(guān)的異常

25、現(xiàn)象。 名稱名稱體溫體溫胎生胎生4條腿條腿冬眠冬眠類標(biāo)號(hào)類標(biāo)號(hào) 豪豬恒溫是是是是 貓恒溫是是否是 蝙蝠恒溫是否是否* 鯨恒溫是否否否* 蠑螈冷血否是是否 科莫多巨蜥冷血否是否否 蟒蛇冷血否否是否 鮭魚(yú)冷血否否否否 鷹恒溫否否否否 虹鳉冷血是否否否 哺乳動(dòng)物分類的訓(xùn)練數(shù)據(jù)集樣本。（“*”為錯(cuò)誤標(biāo)記記錄） 十個(gè)訓(xùn)練記錄中有兩個(gè)被錯(cuò)誤標(biāo)記：蝙蝠和鯨被錯(cuò)誤標(biāo)記為非哺乳 動(dòng)物，而不是哺乳動(dòng)物。 噪聲導(dǎo)致的過(guò)分?jǐn)M合 名稱名稱體溫體溫胎生胎生4條腿條腿冬眠冬眠類標(biāo)號(hào)類標(biāo)號(hào) 人恒溫是否否是 鴿子恒溫否否否否 象恒溫是是否是 豹紋鯊冷血是否否否 海龜冷血否是否否 企鵝冷血否否否否 鰻冷血否否否否 海豚恒溫是否否

26、是 針鼴恒溫否是是是 希拉毒蜥冷血否是是否 哺乳動(dòng)物分類的檢驗(yàn)數(shù)據(jù)集樣本。 完全擬合訓(xùn)練數(shù)據(jù)的決策樹(shù)顯示在下圖（a）中，雖然該樹(shù)的訓(xùn)練誤差 為0，但是它在檢驗(yàn)數(shù)據(jù)集上的誤差高達(dá)30%。 體溫 恒溫 冷血 胎生 4條腿 哺乳類 動(dòng)物 非哺乳 類動(dòng)物 非哺乳 類動(dòng)物 非哺乳 類動(dòng)物 是否 是否 體溫 恒溫 冷血 胎生 非哺乳 類動(dòng)物 非哺乳 類動(dòng)物 是否 哺乳類 動(dòng)物 （a）模型M1 （b）模型M2 圖（b）中決策樹(shù)M2盡管訓(xùn)練誤差較高（20%）， 但是它具有較低的檢驗(yàn)誤差。 缺乏代表性樣本導(dǎo)致的過(guò)分?jǐn)M合 名稱名稱體溫體溫胎生胎生4 4條腿條腿冬眠冬眠類標(biāo)號(hào)類標(biāo)號(hào) 蠑螈冷血否是是否 虹鳉冷血是否否

27、否 鷹恒溫否否否否 弱夜鷹恒溫否否是否 鴨嘴獸恒溫否是是是 體溫 恒溫 冷血 冬眠 4條腿 哺乳類 動(dòng)物 非哺乳 類動(dòng)物 非哺乳 類動(dòng)物 非哺乳 類動(dòng)物 是否 是否 人、大象和海豚都被誤分類，因?yàn)闆Q策樹(shù) 把恒溫但不冬眠的脊柱動(dòng)物劃分為非哺乳動(dòng)物。 決策樹(shù)做出這樣的分類決策是因?yàn)橹挥幸粋€(gè)訓(xùn) 練記錄（鷹）具有這些特性。 過(guò)分?jǐn)M合與多重比較過(guò)程 1、在決策樹(shù)增長(zhǎng)過(guò)程中，可以進(jìn)行多種測(cè)試，以確定哪個(gè)屬性能夠 最好的劃分訓(xùn)練數(shù)據(jù)。 2、在這種情況下，算法實(shí)際上是使用多重比較過(guò)程來(lái)決定是否需要 擴(kuò)展決策樹(shù)。 3、當(dāng)候選屬性多，訓(xùn)練記錄數(shù)少時(shí)，這種影響就變得更加明顯。 多重比較過(guò)程與模型過(guò)分?jǐn)M合有什么關(guān)系？

28、 1、過(guò)分?jǐn)M合的主要原因一直是個(gè)爭(zhēng)辯的話題，但大家還是普遍同意模型 的復(fù)雜度對(duì)模型的過(guò)分?jǐn)M合有影響。 2、如何確定正確的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的 模型的復(fù)雜度。 3、估計(jì)泛化誤差的方法 使用再代入估計(jì)。用訓(xùn)練誤差提供對(duì)泛化誤差的樂(lè)觀估計(jì) 結(jié)合模型復(fù)雜度 估計(jì)統(tǒng)計(jì)上界 使用確定集 泛化誤差估計(jì) 泛化誤差估計(jì) 1、使用再代入估計(jì) 再代入估計(jì)方法假設(shè)訓(xùn)練數(shù)據(jù)集可以很好地代表整體數(shù)據(jù)，因而， 可以使用訓(xùn)練誤差（又稱再代入誤差）提供泛化誤差的樂(lè)觀估計(jì)。 但是訓(xùn)練誤差通常是泛化誤差的一種很差的估計(jì)。 考慮下圖中的二叉決策樹(shù)。假設(shè)兩顆決策樹(shù)都由相同的訓(xùn)練數(shù)據(jù)產(chǎn) 生，并且都根據(jù)每個(gè)葉結(jié)點(diǎn)

29、多數(shù)類做出劃分。注意，左邊的樹(shù)T1復(fù) 雜一些，它擴(kuò)展了右邊決策樹(shù)T2的某些結(jié)點(diǎn)。左決策樹(shù)的訓(xùn)練誤差 是 ，而右決策樹(shù)的訓(xùn)練誤差是 。 根據(jù)再代入估計(jì)，左決策樹(shù)要優(yōu)于右決策樹(shù)。 167. 024/4)( 1 Te25. 024/6)( 2 Te +：3 -：0 +：3 -：1 +：1 -：2 +：0 -：2 +：2 -：1 +：3 -：1 +：0 -：5 +：3 -：6 +：3 -：0 +：1 -：4 +：5 -：2 決策樹(shù)T1 決策樹(shù)T2 2、結(jié)合模型復(fù)雜度 如之前所述，模型越是復(fù)雜，出現(xiàn)過(guò)分?jǐn)M合的幾率就越高，因此，我們更喜歡采 用較為簡(jiǎn)單的模型。這種策略與應(yīng)用眾所周知的奧卡姆剃刀一致。 奧卡

30、姆剃刀：給定兩個(gè)具有相同泛化誤差的模型，較簡(jiǎn)單的模型比較復(fù)雜的模型 更可取。 悲觀誤差評(píng)估悲觀誤差評(píng)估：使用訓(xùn)練誤差與模型復(fù)雜度罰項(xiàng)（penalty term）的和計(jì)算泛 化誤差。結(jié)果泛化誤差可以看作模型的悲觀誤差估計(jì)。設(shè)n(t)是結(jié)點(diǎn)t分類的 訓(xùn)練記錄數(shù)，e(t)是被誤分類的記錄數(shù)。決策樹(shù)T的悲觀誤差估計(jì) 可以用 下式計(jì)算： )(Teg t k i i k i ii g N TTe tn tte Te )()( )( )()( )( 1 1 其中，k是決策樹(shù)的葉結(jié)點(diǎn)數(shù)，e(T)是決策樹(shù)的總訓(xùn)練誤差， 是訓(xùn)練記 錄數(shù)， 是每個(gè)結(jié)點(diǎn) 對(duì)應(yīng)的罰項(xiàng)。 t N )( i t i t +：3 -：0 +

31、：3 -：1 +：1 -：2 +：0 -：2 +：2 -：1 +：3 -：1 +：0 -：5 +：3 -：6 +：3 -：0 +：1 -：4 +：5 -：2 決策樹(shù)T1 決策樹(shù)T2 考慮上圖的二叉決策樹(shù)。如果罰項(xiàng)等于0.5，左邊的決策樹(shù)的悲觀誤差 估計(jì)為： 3125. 0 24 5 . 7 24 5 . 074 )( 1 Teg 右邊的決策樹(shù)的悲觀誤差估計(jì)為： 333. 0 24 8 24 5 . 046 )( 2 Teg 此時(shí)，左邊的決策樹(shù)比右邊的決策樹(shù)具有更好的悲觀誤差估計(jì)。 最小描述長(zhǎng)度原則（最小描述長(zhǎng)度原則（minimum description length, MDL） AB A?

32、B? C? 10 0 1 YesNo B1B2 C1C2 Xy X11 X20 X30 X41 Xn1 標(biāo)記的未標(biāo)記的 Cost 是傳輸總代價(jià)。目標(biāo)：最小化Cost值。 其中Cost(Data|Model) 是誤分類記錄編碼的開(kāi)銷。Cost(Model) 是模 型編碼的開(kāi)銷 。 另一種可能是，A決定建立一個(gè)分類模型，概括X和y點(diǎn)之間的關(guān)系。 Cost(Model, Data) = Cost(Data|Model) + Cost(Model) 3、估計(jì)統(tǒng)計(jì)上界 泛化誤差也可以用訓(xùn)練誤差的統(tǒng)計(jì)修正來(lái)估計(jì)。因?yàn)榉夯`差傾向 于比訓(xùn)練誤差大，所以統(tǒng)計(jì)修正通常是計(jì)算訓(xùn)練誤差的上界。 4、使用確認(rèn)集 在該

33、方法中，不是用訓(xùn)練集估計(jì)泛化誤差，而是把原始的訓(xùn)練數(shù)據(jù) 集分為兩個(gè)較小的子集，一個(gè)子集用于訓(xùn)練，而另一個(gè)稱為確認(rèn)集， 用于估計(jì)泛化誤差。 2/3訓(xùn)練集 建立模型建立模型 誤差估計(jì)誤差估計(jì) 1/3訓(xùn)練集 該方法通常用于通過(guò)參數(shù)控制獲得具有不同復(fù)雜度模型的分類技術(shù)。 通過(guò)調(diào)整學(xué)習(xí)算法中的參數(shù)，直到學(xué)習(xí)算法產(chǎn)生的模型在確認(rèn)集上 達(dá)到最低的錯(cuò)誤率，可以估計(jì)最佳模型的復(fù)雜度。 處理決策樹(shù)歸納中的過(guò)分?jǐn)M合 先剪枝 (提前終止規(guī)則) 樹(shù)增長(zhǎng)算法在產(chǎn)生完全擬合整個(gè)訓(xùn)練數(shù)據(jù)集的之前就停止決策樹(shù)的生長(zhǎng) 為了做到這一點(diǎn)，需要采用更具限制性的結(jié)束條件: 當(dāng)結(jié)點(diǎn)的記錄數(shù)少于一定閾值，則停止生長(zhǎng) 當(dāng)不純性度量的增益低于某

34、個(gè)確定的閾值時(shí)，則停止生長(zhǎng) (e.g., information gain). 缺點(diǎn)：很難為提前終止選取正確的閾值: （1）閾值太高，導(dǎo)致擬合不足 （2）閾值太低，導(dǎo)致不能充分解決過(guò)分?jǐn)M合的問(wèn)題。 后剪枝 在該方法中，初始決策樹(shù)按照最大規(guī)模生長(zhǎng)，然后進(jìn)行剪枝的步驟，按照自 底向上的方式修剪完全增長(zhǎng)的決策樹(shù)。 修剪有兩種做法: （1）用新的葉結(jié)點(diǎn)替換子樹(shù)，該葉結(jié)點(diǎn)的類標(biāo)號(hào)由子樹(shù)下記錄中的多數(shù)類定 （2）用子樹(shù)中最常用的分支代替子樹(shù) 五、評(píng)估分類器的性能五、評(píng)估分類器的性能 一、保持（Holdout）方法 將被標(biāo)記的原始數(shù)據(jù)劃分成兩個(gè)不相交的集合，分別成為訓(xùn)練集和 檢驗(yàn)集。在訓(xùn)練集上歸納分類模型，

35、在檢驗(yàn)集上評(píng)估模型的性能。 局限性： 1、用于訓(xùn)練的被標(biāo)記樣本較少。 2、模型可能高度依賴于訓(xùn)練集和檢驗(yàn)集的構(gòu)成。 二、隨機(jī)二次抽樣（random subsampling） 隨機(jī)二次抽樣可以多次重復(fù)保持方法來(lái)改進(jìn)分類器性能的估計(jì)。 k i isub kaccacc 1 / 由于它沒(méi)有控制每個(gè)記錄用于訓(xùn)練和檢驗(yàn)的次數(shù)，因此，有些 用于訓(xùn)練的記錄使用的頻率可能比其他記錄高得多。 三、交叉驗(yàn)證（cross-validation） 在該方法中，每個(gè)記錄用于訓(xùn)練的次數(shù)相同，并且恰好檢驗(yàn)一次。 例：假設(shè)把數(shù)據(jù)分為相同大小的兩個(gè)子集，首先，我們選擇一個(gè)子 集作訓(xùn)練集，而另一個(gè)作檢驗(yàn)集，然后交換兩個(gè)集合的角色

36、，原先 作訓(xùn)練集的現(xiàn)在作檢驗(yàn)集，反之亦然，這種方法叫做二折交叉驗(yàn)證。 四、自助（bootstrap）法 在自助法中，訓(xùn)練記錄采用有放回抽樣使得它等幾率地被重新抽取。如果原 始數(shù)據(jù)有N個(gè)記錄，可以證明，平均來(lái)說(shuō)，大小為N的自助樣本大約包含原始 數(shù)據(jù)的63.2%的記錄。 N N ) 1 1 (1至少一個(gè)記錄被自助樣本抽取的概率632. 0 1 1) 1 1 (1lim eN N N 它通過(guò)組合每個(gè)自助樣本的準(zhǔn)確率 和由包含所有標(biāo)記樣本的訓(xùn)練集計(jì)算的 準(zhǔn)確率 計(jì)算總準(zhǔn)確率 ： )( i )( s acc)( boot acc b i siboot acc b acc 1 )368. 0632. 0( 1 六、比較分類器的方法六、比較分類器的方法 考慮一對(duì)分類模型Model A和model