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

1、第4章 分類：基本概念、決策樹與模型評(píng)估分類：基本概念、決策樹與模型評(píng)估4.1預(yù)備知識(shí)4.2解決分類問題的一般方法4.3決策樹歸納4.4模型的過分?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)屬性）。分類？回歸？分類（classification） 通過學(xué)習(xí)得到一個(gè)目

2、標(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è)或描述二元或標(biāo)稱類型的數(shù)據(jù)集，對(duì)序數(shù)分類不太有效，因?yàn)榉诸惣夹g(shù)不考慮隱含在目標(biāo)類中的

3、序關(guān)系。分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。分類技術(shù)決策樹分類法決策樹分類法基于規(guī)則的分類法基于規(guī)則的分類法神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)支持向量機(jī)支持向量機(jī)這些技術(shù)都使用一種學(xué)習(xí)算法確定分類模型，修改這個(gè)模型能夠很好地?cái)M合輸入數(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)：建立具有很好的泛化能力的模型。二、解決分類問題的一般方法二、解決分類問題的一般方法樸素貝葉斯分類法樸素貝葉斯分類法訓(xùn)練集：由類標(biāo)號(hào)已知的記錄構(gòu)成檢驗(yàn)集：由類標(biāo)號(hào)未知的記錄構(gòu)成預(yù)測(cè)的類預(yù)測(cè)的類類=1類=0實(shí)際的類類=1類=000f01f10f1

4、1f二類問題的混淆矩陣ijfij表中每個(gè)表項(xiàng) 表示實(shí)際類標(biāo)號(hào)為 但是被預(yù)測(cè)為類 的記錄數(shù)。被分類模型正確預(yù)測(cè)的樣本總數(shù)是 ，而被錯(cuò)誤預(yù)測(cè)的樣本總數(shù)是 。0011ff0110ff雖然混淆矩陣提供衡量分類模型的信息，但是用一個(gè)數(shù)匯總這些信息更便于比較不同模型的性能。為實(shí)現(xiàn)這一目的，可以使用性能度量（performance metric），如準(zhǔn)確率（accuracy），其定義如下：同樣，分類模型的性能也可以用錯(cuò)誤率（error rate）來表示，其定義如下：000110110110ffffff預(yù)測(cè)總數(shù)錯(cuò)誤預(yù)測(cè)數(shù)錯(cuò)誤率目標(biāo)：尋求最高的準(zhǔn)確率或者最低的錯(cuò)誤率000110110011ffffff預(yù)測(cè)總數(shù)正

5、確預(yù)測(cè)數(shù)準(zhǔn)確率1、什么是決策樹？類似于流程圖的樹結(jié)構(gòu)每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試每個(gè)分枝代表一個(gè)測(cè)試輸出每個(gè)葉節(jié)點(diǎn)代表類或類分布三、決策樹（三、決策樹（decision tree）歸納）歸納3、決策樹的使用：對(duì)未知樣本進(jìn)行分類通過將樣本的屬性值與決策樹相比較2、決策樹的生成由兩個(gè)階段組成決策樹構(gòu)建開始時(shí)，所有的訓(xùn)練樣本都在根節(jié)點(diǎn)遞歸通過選定的屬性，來劃分樣本 （必須是離散值）樹剪枝許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn)，樹剪枝試圖檢測(cè)和剪去這種分枝根結(jié)點(diǎn)（root node）：它沒有入邊，但是有零條或多條出邊。內(nèi)部結(jié)點(diǎn)（internal node）：恰好有一條入邊和兩條或多條出邊。葉節(jié)

6、點(diǎn)（leaf node）或終結(jié)點(diǎn)（terminal node）：恰好有一條入邊， 但沒有出邊。葉結(jié)點(diǎn)根結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)體溫胎生非哺乳動(dòng)物哺乳動(dòng)物非哺乳動(dòng)物恒溫否冷血是 一旦構(gòu)造了決策樹，對(duì)檢驗(yàn)記錄進(jìn)行分類就很容易。從樹的根結(jié)點(diǎn)開始，將測(cè)試條件用于檢驗(yàn)記錄，根據(jù)測(cè)試結(jié)果選擇適當(dāng)?shù)姆种?。沿著該分支或者到達(dá)另一個(gè)內(nèi)部結(jié)點(diǎn)，使用新的測(cè)試條件，或者到達(dá)一個(gè)葉結(jié)點(diǎn)。到達(dá)葉結(jié)點(diǎn)之后，葉結(jié)點(diǎn)的類標(biāo)號(hào)就被賦值給該檢驗(yàn)記錄。名字名字體溫體溫胎生胎生類標(biāo)號(hào)類標(biāo)號(hào)火烈鳥恒溫否？體溫胎生非哺乳動(dòng)物哺乳動(dòng)物非哺乳動(dòng)物恒溫否冷血是如何建立決策樹 對(duì)于給定的屬性集，可以構(gòu)造的決策樹的數(shù)目達(dá)指數(shù)級(jí)。盡管某些決策樹比其他決策樹更準(zhǔn)確

7、，但是由于搜索空間是指數(shù)規(guī)模的，找出最佳決策樹在計(jì)算上是不可行的。 盡管如此，人們還是開發(fā)了一些有效的算法，能夠在合理的時(shí)間內(nèi)構(gòu)造出具有一定準(zhǔn)確率的次最優(yōu)決策樹。這些算法通常都采用貪心策略。有許多決策樹算法: （ID3ID3）（C4.5C4.5） (SLIQ(SLIQ，SPRINT)SPRINT)在Hunt算法中，通過將訓(xùn)練記錄相繼劃分成較純的子集，以遞歸方式建立決策樹。設(shè) 是與結(jié)點(diǎn)t相關(guān)聯(lián)的訓(xùn)練記錄集，而 是類標(biāo)號(hào)，Hunt算法的遞歸定義如下。tD,21cyyyy（1）如果 中所有記錄都屬于同一個(gè)類 ，則t是葉結(jié)點(diǎn)，用 標(biāo)記。tytDty（2）如果 中包含屬于多個(gè)類的記錄，則選擇一個(gè)屬性測(cè)試

8、條件，將記錄劃分成較小的子集。對(duì)于測(cè)試條件的每個(gè)輸出，創(chuàng)建一個(gè)子女結(jié)點(diǎn)，并根據(jù)測(cè)試結(jié)果將 中的記錄分布到子女結(jié)點(diǎn)中。然后，對(duì)于每個(gè)子女結(jié)點(diǎn)，遞歸地調(diào)用該算法。tDtDHunt算法Tid有房者有房者婚姻狀況婚姻狀況年收入年收入拖欠貸款者拖欠貸款者1是單身125k否2否已婚100k否3否單身70k否4是已婚120k否5否離異95k是6否已婚60k否7是離異220k否8否單身85k是9否已婚75k否10否單身90k是拖欠貸款者=否拖欠貸款者=否拖欠貸款者=否有房者拖欠貸款者=否有房者拖欠貸款者=否婚姻狀況年收入拖欠貸款者=是拖欠貸款者=否(b)(c)(d)(a)拖欠貸款者=否有房者拖欠貸款者=否婚姻

9、狀況拖欠貸款者=是是是否否否是單身離異單身離異已婚已婚=80kHunt算法構(gòu)造決策樹如果屬性值的每種組合都在訓(xùn)練數(shù)據(jù)中出現(xiàn)，并且每種組合都具有唯一的類標(biāo)號(hào)，則Hunt算法是有效的。但是對(duì)于大多數(shù)實(shí)際情況，這些假設(shè)太苛刻了，因此，需要附加的條件來處理以下的情況：（1）算法的第二步所創(chuàng)建的子女結(jié)點(diǎn)可能為空，即不存在與這些結(jié)點(diǎn)相關(guān)聯(lián)的記錄。如果沒有一個(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)為葉

10、結(jié)點(diǎn)，其標(biāo)號(hào)為與該結(jié)點(diǎn)相關(guān)聯(lián)的訓(xùn)練記錄中的多數(shù)類。tD決策樹歸納的設(shè)計(jì)問題（1）如何分裂訓(xùn)練記錄？（2）如何停止分裂過程？樹增長(zhǎng)過程的每個(gè)遞歸步驟都必須選擇一個(gè)屬性測(cè)試條件，將記錄劃分成較小的子集。為了實(shí)現(xiàn)這個(gè)步驟。算法必須提供為不同類型的屬性指定測(cè)試條件的方法，并且提供評(píng)估每種測(cè)試條件的客觀度量。決策樹需要有結(jié)束條件，以終止決策樹的生長(zhǎng)過程。一個(gè)可能的策略是分裂結(jié)點(diǎn)，直到所有的記錄都屬于同一個(gè)類，或者所有的記錄都具有相同的屬性值。表示屬性測(cè)試條件的方法1、二元屬性 二元屬性的測(cè)試條件產(chǎn)生兩個(gè)可能的輸出。體溫恒溫冷血二元屬性的測(cè)試條件2、標(biāo)稱屬性由于標(biāo)稱屬性有多個(gè)屬性值，它的測(cè)試條件可以用兩種

11、方法表示?；橐鰻顩r單身已婚離異婚姻狀況已婚單身，離異婚姻狀況離異單身，已婚婚姻狀況單身已婚，離異多路劃分二元?jiǎng)澐郑ㄍㄟ^屬性值分組）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ù)屬性來說，測(cè)試條件可以是具有二元輸出的比較測(cè)試 或 也可以是具有形如 輸出的范圍查詢。)(vA )(vA ), 2 , 1(1kivAvii年收入80k（a）（b）年收入是否10k10k,25k10k25k,50k50k,80k連續(xù)屬性的測(cè)試條件有

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

13、的結(jié)點(diǎn)具有零不純性，而均衡分布（0.5, 0.5）的結(jié)點(diǎn)具有最高的不純性。不純性度量的例子包括：102)|(log)|()(citiptiptEntropy102)|(1)(citiptGini)|(max1)(_Ctipterrorionlassificati熵：基尼指數(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類=150)6/6()6/0(122Gini0)6/6(log)6/6()6/0(log)6/0(22Entropy06/6 , 6/0max1Error278. 0

14、)6/5()6/1 (122Gini650. 0)6/5(log)6/5()6/1 (log)6/1 (22Entropy167. 06/5 , 6/1max1Error5 . 0)6/3()6/3(122Gini1)6/3(log)6/3()6/3(log)6/3(22Entropy5 . 06/3 , 6/3max1Error二元分類問題不純性度量之間的比較不同的不純性度量是一致的，但是作為測(cè)試條件的屬性選擇仍然因不純性度量的選擇而異。00.10.20.30.40.50.60.70.80.9100.10.20.30.40.50.60.70.80.91p 熵Gini分 類 誤 差為確定測(cè)試條

15、件的效果，我們需要比較父結(jié)點(diǎn)（劃分前）的不純性程度和子女結(jié)點(diǎn)（劃分后）的不純性程度，它們的差越大，測(cè)試條件的效果就越好。增益 是一種可以用來確定劃分效果的標(biāo)準(zhǔn)：kjjjvINvNparentI1)()()()(I其中， 是給定結(jié)點(diǎn)的不純性度量，N是父結(jié)點(diǎn)上的記錄總數(shù)，k是屬性值的個(gè)數(shù)， 是與子女結(jié)點(diǎn) 相關(guān)聯(lián)的記錄個(gè)數(shù)。)(jvNjv決策樹算法選擇最大化增益的測(cè)試條件。B是否結(jié)點(diǎn) N1結(jié)點(diǎn) N2A是否結(jié)點(diǎn) N1結(jié)點(diǎn) N2父結(jié)點(diǎn)父結(jié)點(diǎn)C06C16Gini=0.500N1N1N2N2C042C133Gini=0.486N1N1N2N2C015C142Gini=0.3711、二元屬性的劃分2、標(biāo)稱屬性

16、的劃分車型車型運(yùn)動(dòng)，豪華家用C091C173Gini0.468車型車型運(yùn)動(dòng)家用，豪華C082C1010Gini0.167車型車型家用運(yùn)動(dòng)豪華C0181C1307Gini0.163（a）二元?jiǎng)澐?b)多路劃分標(biāo)稱屬性可以產(chǎn)生二元?jiǎng)澐只蛘叨嗦穭澐?、連續(xù)屬性的劃分1.使用二元?jiǎng)澐?.劃分點(diǎn)v選擇N個(gè)記錄中所有屬性值作為劃分點(diǎn)3.對(duì)每個(gè)劃分進(jìn)行類計(jì)數(shù), A v 和 A v4.計(jì)算每個(gè)候選點(diǎn)v的Gini指標(biāo)，并從中選擇具有最小值的候選劃分點(diǎn)5.時(shí)間復(fù)雜度為O(n2)降低計(jì)算復(fù)雜性的方法:1.將記錄進(jìn)行排序2.從兩個(gè)相鄰的排過序的屬性值之間選擇中間值作為劃分點(diǎn)3.計(jì)算每個(gè)候選點(diǎn)的Gini值4.時(shí)間復(fù)雜度

17、為O（NlogN）4、增益率熵和Gini指標(biāo)等不純性度量趨向有利于具有大量不同值的屬性。性別男女車型家用運(yùn)動(dòng)豪華C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7（b）（a）測(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:1C1:0C0:1C1:0C0:0C1:1C0:0C1:1顧客IDv1v10v20v11（c） 如何解決？如何解決？第一種策略：限制測(cè)試條件只能是二元?jiǎng)澐帧５诙N策略：修改評(píng)估劃分的標(biāo)準(zhǔn)

18、，把屬性測(cè)試條件產(chǎn)生的輸出數(shù)也考慮進(jìn)去。例如：CART就是采用這樣的策略。例如：決策樹算法C4.5采用增益率（gain ratio）的劃分標(biāo)準(zhǔn)來評(píng)估劃分。InfoSplit ratioGain info是劃分的總數(shù)，而其中，劃分信息k)()logP(v-InfoSplit 1i2ikivP決策樹歸納特點(diǎn)的總結(jié)1、決策樹歸納是一種構(gòu)建分類模型的非參數(shù)方法。2、找到最佳的決策樹是NP完全問題。3、已開發(fā)的構(gòu)建決策樹技術(shù)不需要昂貴的計(jì)算代價(jià)，即使訓(xùn)練集非常 大，也可以快速建立模型。4、決策樹相對(duì)容易解釋，特別是小型的決策樹。5、決策樹是學(xué)習(xí)離散值函數(shù)的典型代表。6、決策樹算法對(duì)于噪聲的干擾具有相當(dāng)好

19、的魯棒性。7、冗余屬性不會(huì)對(duì)決策樹的準(zhǔn)確率造成不利的影響。8、由于大多數(shù)決策樹算法都采用自頂向下的遞歸劃分方法，因此沿著樹向下，記錄會(huì)越來越少。9、子樹可能在決策樹中重復(fù)多次，這使得決策樹過于復(fù)雜，并且可能更難解釋。10、目前為止，本章介紹的測(cè)試條件每次都只涉及一個(gè)屬性。二維數(shù)據(jù)集的決策樹及其邊界示例PQRS0101QS001使用僅涉及單個(gè)屬性的測(cè)試條件不能有效劃分的數(shù)據(jù)集的例子斜決策樹（oblique decision tree）可以克服以上的局限，因?yàn)樗试S測(cè)試條件涉及多個(gè)屬性。上圖中的數(shù)據(jù)集可以很容易地用斜決策樹表示，該決策樹只有一個(gè)結(jié)點(diǎn)，其測(cè)試條件為：1 yx缺點(diǎn)：盡管這種技術(shù)有更強(qiáng)的

20、表達(dá)能力，并且能夠產(chǎn)生更緊湊的決策樹，但是為給定的結(jié)點(diǎn)找出最佳測(cè)試條件的計(jì)算可能是相當(dāng)復(fù)雜的。x + y 1Class = + Class = 構(gòu)造歸納（constructive induction） 提供另一種將數(shù)據(jù)劃分成齊次非矩形區(qū)域的方法，該方法創(chuàng)建復(fù)合屬性，代表已有屬性的算術(shù)或邏輯組合。新屬性提供了更好的類區(qū)分能力，并在決策樹歸納之前就增廣到數(shù)據(jù)集中。 與決策樹不同，構(gòu)造歸納不需要昂貴的花費(fèi)，因?yàn)樵跇?gòu)造決策樹之前，它只需要一次性地確定屬性的所有相關(guān)組合，相比之下，在擴(kuò)展每個(gè)內(nèi)部結(jié)點(diǎn)時(shí)，斜決策樹都需要?jiǎng)討B(tài)地確定正確的屬性組合。然而構(gòu)造歸納會(huì)產(chǎn)生冗余的屬性，因?yàn)樾聞?chuàng)建的屬性是已有屬性的組合

21、。11、研究表明不純性度量方法的選擇對(duì)決策樹算法的性能影響很小。一個(gè)好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。四、模型的過分?jǐn)M合四、模型的過分?jǐn)M合二維數(shù)據(jù)過分?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)作為不純性度量的決策樹方法。具有兩個(gè)類的數(shù)據(jù)集的例子 當(dāng)決策樹很小時(shí)，訓(xùn)練誤差和檢驗(yàn)誤差都很大，這種情況稱作模型擬合不足（mode

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

23、與擬合不足是兩種與模型復(fù)雜度有關(guān)的異?，F(xiàn)象。名稱名稱體溫體溫胎生胎生4條腿條腿冬眠冬眠類標(biāo)號(hào)類標(biāo)號(hào)豪豬恒溫是是是是貓恒溫是是否是蝙蝠恒溫是否是否*鯨恒溫是否否否*蠑螈冷血否是是否科莫多巨蜥冷血否是否否蟒蛇冷血否否是否鮭魚冷血否否否否鷹恒溫否否否否虹鳉冷血是否否否哺乳動(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)致的過分?jǐn)M合名稱名稱體溫體溫胎生胎生4條腿條腿冬眠冬眠類標(biāo)號(hào)類標(biāo)號(hào)人恒溫是否否是鴿子恒溫否否否否象恒溫是是否是豹紋鯊冷血是否否否海龜冷血否是否否企鵝冷血否否否否鰻冷血否否否否海豚恒溫是否否是針鼴恒溫

24、否是是是希拉毒蜥冷血否是是否哺乳動(dòng)物分類的檢驗(yàn)數(shù)據(jù)集樣本。完全擬合訓(xùn)練數(shù)據(jù)的決策樹顯示在下圖（a）中，雖然該樹的訓(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）中決策樹M2盡管訓(xùn)練誤差較高（20%），但是它具有較低的檢驗(yàn)誤差。缺乏代表性樣本導(dǎo)致的過分?jǐn)M合名稱名稱體溫體溫胎生胎生4 4條腿條腿冬眠冬眠類標(biāo)號(hào)類標(biāo)號(hào)蠑螈冷血否是是否虹鳉冷血是否否否鷹恒溫否否否否弱夜鷹恒溫否否是否鴨嘴獸恒溫否是是是體溫恒溫冷血冬眠4條腿哺乳類動(dòng)物非哺

25、乳類動(dòng)物非哺乳類動(dòng)物非哺乳類動(dòng)物是否是否 人、大象和海豚都被誤分類，因?yàn)闆Q策樹把恒溫但不冬眠的脊柱動(dòng)物劃分為非哺乳動(dòng)物。決策樹做出這樣的分類決策是因?yàn)橹挥幸粋€(gè)訓(xùn)練記錄（鷹）具有這些特性。過分?jǐn)M合與多重比較過程1、在決策樹增長(zhǎng)過程中，可以進(jìn)行多種測(cè)試，以確定哪個(gè)屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。2、在這種情況下，算法實(shí)際上是使用多重比較過程來決定是否需要擴(kuò)展決策樹。3、當(dāng)候選屬性多，訓(xùn)練記錄數(shù)少時(shí)，這種影響就變得更加明顯。多重比較過程與模型過分?jǐn)M合有什么關(guān)系？1、過分?jǐn)M合的主要原因一直是個(gè)爭(zhēng)辯的話題，但大家還是普遍同意模型的復(fù)雜度對(duì)模型的過分?jǐn)M合有影響。2、如何確定正確的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)

26、生最低泛化誤差的模型的復(fù)雜度。3、估計(jì)泛化誤差的方法使用再代入估計(jì)。用訓(xùn)練誤差提供對(duì)泛化誤差的樂觀估計(jì)結(jié)合模型復(fù)雜度估計(jì)統(tǒng)計(jì)上界使用確定集泛化誤差估計(jì)泛化誤差估計(jì)1、使用再代入估計(jì)再代入估計(jì)方法假設(shè)訓(xùn)練數(shù)據(jù)集可以很好地代表整體數(shù)據(jù)，因而，可以使用訓(xùn)練誤差（又稱再代入誤差）提供泛化誤差的樂觀估計(jì)。但是訓(xùn)練誤差通常是泛化誤差的一種很差的估計(jì)。考慮下圖中的二叉決策樹。假設(shè)兩顆決策樹都由相同的訓(xùn)練數(shù)據(jù)產(chǎn)生，并且都根據(jù)每個(gè)葉結(jié)點(diǎn)多數(shù)類做出劃分。注意，左邊的樹T1復(fù)雜一些，它擴(kuò)展了右邊決策樹T2的某些結(jié)點(diǎn)。左決策樹的訓(xùn)練誤差是 ，而右決策樹的訓(xùn)練誤差是 。根據(jù)再代入估計(jì)，左決策樹要優(yōu)于右決策樹。 167.

27、 024/4)(1Te25. 024/6)(2Te+：3 -：0+：3 -：1+：1 -：2+：0 -：2+：2 -：1+：3 -：1+：0 -：5+：3 -：6+：3 -：0+：1 -：4+：5 -：2決策樹T1決策樹T22、結(jié)合模型復(fù)雜度如之前所述，模型越是復(fù)雜，出現(xiàn)過分?jǐn)M合的幾率就越高，因此，我們更喜歡采用較為簡(jiǎn)單的模型。這種策略與應(yīng)用眾所周知的奧卡姆剃刀一致。奧卡姆剃刀：給定兩個(gè)具有相同泛化誤差的模型，較簡(jiǎn)單的模型比較復(fù)雜的模型更可取。悲觀誤差評(píng)估悲觀誤差評(píng)估：使用訓(xùn)練誤差與模型復(fù)雜度罰項(xiàng)（penalty term）的和計(jì)算泛化誤差。結(jié)果泛化誤差可以看作模型的悲觀誤差估計(jì)。設(shè)n(t)是

28、結(jié)點(diǎn)t分類的訓(xùn)練記錄數(shù)，e(t)是被誤分類的記錄數(shù)。決策樹T的悲觀誤差估計(jì) 可以用下式計(jì)算：)(TegtkiikiiigNTTetntteTe)()()()()()(11其中，k是決策樹的葉結(jié)點(diǎn)數(shù)，e(T)是決策樹的總訓(xùn)練誤差， 是訓(xùn)練記錄數(shù)， 是每個(gè)結(jié)點(diǎn) 對(duì)應(yīng)的罰項(xiàng)。tN)(itit+：3 -：0+：3 -：1+：1 -：2+：0 -：2+：2 -：1+：3 -：1+：0 -：5+：3 -：6+：3 -：0+：1 -：4+：5 -：2決策樹T1決策樹T2考慮上圖的二叉決策樹。如果罰項(xiàng)等于0.5，左邊的決策樹的悲觀誤差估計(jì)為：3125. 0245 . 7245 . 074)(1Teg右邊的決策

29、樹的悲觀誤差估計(jì)為：333. 0248245 . 046)(2Teg此時(shí)，左邊的決策樹比右邊的決策樹具有更好的悲觀誤差估計(jì)。最小描述長(zhǎng)度原則（最小描述長(zhǎng)度原則（minimum description length, MDL）ABA?B?C?1001YesNoB1B2C1C2XyX11X20X30X41Xn1標(biāo)記的未標(biāo)記的Cost 是傳輸總代價(jià)。目標(biāo)：最小化Cost值。其中Cost(Data|Model) 是誤分類記錄編碼的開銷。Cost(Model) 是模型編碼的開銷 。另一種可能是，A決定建立一個(gè)分類模型，概括X和y點(diǎn)之間的關(guān)系。Cost(Model, Data) = Cost(Data|M

30、odel) + Cost(Model)3、估計(jì)統(tǒng)計(jì)上界泛化誤差也可以用訓(xùn)練誤差的統(tǒng)計(jì)修正來估計(jì)。因?yàn)榉夯`差傾向于比訓(xùn)練誤差大，所以統(tǒng)計(jì)修正通常是計(jì)算訓(xùn)練誤差的上界。4、使用確認(rèn)集在該方法中，不是用訓(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)練集該方法通常用于通過參數(shù)控制獲得具有不同復(fù)雜度模型的分類技術(shù)。通過調(diào)整學(xué)習(xí)算法中的參數(shù)，直到學(xué)習(xí)算法產(chǎn)生的模型在確認(rèn)集上達(dá)到最低的錯(cuò)誤率，可以估計(jì)最佳模型的復(fù)雜度。處理決策樹歸納中的過分?jǐn)M合先剪枝 (提前終止規(guī)則)樹增長(zhǎng)算法在產(chǎn)生

31、完全擬合整個(gè)訓(xùn)練數(shù)據(jù)集的之前就停止決策樹的生長(zhǎng)為了做到這一點(diǎn)，需要采用更具限制性的結(jié)束條件: 當(dāng)結(jié)點(diǎn)的記錄數(shù)少于一定閾值，則停止生長(zhǎng)當(dāng)不純性度量的增益低于某個(gè)確定的閾值時(shí)，則停止生長(zhǎng) (e.g., information gain).缺點(diǎn)：很難為提前終止選取正確的閾值: （1）閾值太高，導(dǎo)致擬合不足 （2）閾值太低，導(dǎo)致不能充分解決過分?jǐn)M合的問題。后剪枝在該方法中，初始決策樹按照最大規(guī)模生長(zhǎng)，然后進(jìn)行剪枝的步驟，按照自底向上的方式修剪完全增長(zhǎng)的決策樹。修剪有兩種做法:（1）用新的葉結(jié)點(diǎn)替換子樹，該葉結(jié)點(diǎn)的類標(biāo)號(hào)由子樹下記錄中的多數(shù)類定（2）用子樹中最常用的分支代替子樹五、評(píng)估分類器的性能五、評(píng)

32、估分類器的性能一、保持（Holdout）方法將被標(biāo)記的原始數(shù)據(jù)劃分成兩個(gè)不相交的集合，分別成為訓(xùn)練集和檢驗(yàn)集。在訓(xùn)練集上歸納分類模型，在檢驗(yàn)集上評(píng)估模型的性能。局限性：1、用于訓(xùn)練的被標(biāo)記樣本較少。2、模型可能高度依賴于訓(xùn)練集和檢驗(yàn)集的構(gòu)成。二、隨機(jī)二次抽樣（random subsampling）隨機(jī)二次抽樣可以多次重復(fù)保持方法來改進(jìn)分類器性能的估計(jì)。kiisubkaccacc1/由于它沒有控制每個(gè)記錄用于訓(xùn)練和檢驗(yàn)的次數(shù)，因此，有些用于訓(xùn)練的記錄使用的頻率可能比其他記錄高得多。三、交叉驗(yàn)證（cross-validation）在該方法中，每個(gè)記錄用于訓(xùn)練的次數(shù)相同，并且恰好檢驗(yàn)一次。例：假設(shè)把

33、數(shù)據(jù)分為相同大小的兩個(gè)子集，首先，我們選擇一個(gè)子集作訓(xùn)練集，而另一個(gè)作檢驗(yàn)集，然后交換兩個(gè)集合的角色，原先作訓(xùn)練集的現(xiàn)在作檢驗(yàn)集，反之亦然，這種方法叫做二折交叉驗(yàn)證。四、自助（bootstrap）法在自助法中，訓(xùn)練記錄采用有放回抽樣使得它等幾率地被重新抽取。如果原始數(shù)據(jù)有N個(gè)記錄，可以證明，平均來說，大小為N的自助樣本大約包含原始數(shù)據(jù)的63.2%的記錄。NN)11 (1至少一個(gè)記錄被自助樣本抽取的概率632. 011)11 (1limeNNN它通過組合每個(gè)自助樣本的準(zhǔn)確率 和由包含所有標(biāo)記樣本的訓(xùn)練集計(jì)算的準(zhǔn)確率 計(jì)算總準(zhǔn)確率 ：)(i)(sacc)(bootaccbisibootaccbacc1)368. 0632. 0(1