第八章機器學(xué)習(xí)決策樹ID3算法的實例解析課件

決策樹模型決策樹模型1排名挖掘主題算法得票數(shù)發(fā)表時間作者陳述人1分類C4.5611993Quinlan,J.RHiroshiMotoda2聚類k-Means601967MacQueen,J.BJoydeepGhosh3統(tǒng)計學(xué)習(xí)SVM581995Vapnik,V.NQiangYang4關(guān)聯(lián)分析Apriori521994RakeshAgrawalChristosFaloutsos5統(tǒng)計學(xué)習(xí)EM482000McLachlan,GJoydeepGhosh6鏈接挖掘PageRank461998Brin,S.ChristosFaloutsos7集裝與推進AdaBoost451997Freund,Y.Zhi-HuaZhou8分類kNN451996Hastie,TVipinKumar9分類Na?veBayes452001Hand,D.JQiangYang10分類CART341984L.BreimanDanSteinberg共有145人參加了ICDM2006Panel(會議的專題討論),并對18種候選算法進行投票，選出了數(shù)據(jù)挖掘10大算法ICDM2006會議的算法投票結(jié)果排名挖掘主題算法得票數(shù)發(fā)表時間作者陳述人1分類C4.56112信息的定量描述衡量信息多少的物理量稱為信息量。若概率很大，受信者事先已有所估計，則該消息信息量就很??；若概率很小，受信者感覺很突然，該消息所含信息量就很大。信息的定量描述衡量信息多少的物理量稱為信息量。3信息量的定義根據(jù)客觀事實和人們的習(xí)慣概念，函數(shù)f(p)應(yīng)滿足以下條件：f(p)應(yīng)是概率p的嚴(yán)格單調(diào)遞減函數(shù)，即當(dāng)p1>p2，f(p1)<f(p2)；當(dāng)p=1時，f(p)=0；當(dāng)p=0時，f(p)=∞；兩個獨立事件的聯(lián)合信息量應(yīng)等于它們分別的信息量之和。信息量的定義根據(jù)客觀事實和人們的習(xí)慣概念，函數(shù)f(p)應(yīng)滿足4對信息量的

認(rèn)識理解

信息量的定義若一個消息x出現(xiàn)的概率為p，則這一消息所含的信息量為其中，對數(shù)的底大于1信息量單位以2為底時，單位為bit（binaryunit，比特）以e為底時，單位為nat（naturalunit，奈特）以10為底時，單位為hart（Hartley，哈特）對信息量的

認(rèn)識理解

信息量的定義5拋一枚均勻硬幣，出現(xiàn)正面與反面的信息量是多少？解：出現(xiàn)正面與反面的概率均為0.5，它們的信息量是I(正)=-lbp(正)=-lb0.5=1bI(反)=-lbp(反)=-lb0.5=1b拋一枚均勻硬幣，出現(xiàn)正面與反面的信息量是多少？6拋一枚畸形硬幣，出現(xiàn)正面與反面的概率分別是1/4，3/4，出現(xiàn)正面與反面時的信息量是多少？解：出現(xiàn)正面與反面的概率分別是1/4，3/4，它們的信息量是I(正)=-lbp(正)=-lb1/4=2bI(反)=-lbp(反)=-lb3/4=0.415b拋一枚畸形硬幣，出現(xiàn)正面與反面的概率分別是1/4，3/4，出7信源含有的信息量是信源發(fā)出的所有可能消息的平均不確定性，香農(nóng)把信源所含有的信息量稱為信息熵，是指每個符號所含信息量的統(tǒng)計平均值。m種符號的平均信息量為信源含有的信息量是信源發(fā)出的所有可能消息的平均不確定性，香農(nóng)8拋一枚均勻硬幣的信息熵是多少？解：出現(xiàn)正面與反面的概率均為0.5，信息熵是拋一枚均勻硬幣的信息熵是多少？9拋一枚畸形硬幣，出現(xiàn)正面與反面的概率分別是1/4，3/4，出現(xiàn)正面與反面時的信息量是多少？解：出現(xiàn)正面與反面的概率分別是1/4，3/4，信息熵是拋一枚畸形硬幣，出現(xiàn)正面與反面的概率分別是1/4，3/4，出10例：氣象預(yù)報例：氣象預(yù)報1112條件自信息量在事件yj出現(xiàn)的條件下，隨機事件xi發(fā)生的條件概率為p(xi|yj)，則它的條件自信息量定義為條件概率對數(shù)的負(fù)值：12條件自信息量在事件yj出現(xiàn)的條件下，隨機事件xi發(fā)生的條13條件熵在給定yj條件下，xi的條件自信息量為I(xi|yj),X集合的條件熵H(X|yj)為在給定Y(即各個yj

)條件下,X集合的條件熵H(X|Y)條件熵H(X|Y)表示已知Y后，X的不確定度13條件熵在給定yj條件下，xi的條件自信息量為I(xi|是否適合打壘球的決策表天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消是否適合打壘球的決策表天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎14活動天氣是否進行壘球活動進行取消晴陰雨晴陰雨活動進行取消活動天氣是否進行壘球活動進行取消晴陰雨晴陰雨活動進行15活動的熵活動有2個屬性值，進行，取消。其熵為：H(活動)=-(9/14)*log

(9/14)-(5/14)*log

(5/14)=0.94活動進行取消活動的熵活動有2個屬性值，進行，取消。其熵為：活動進行取消16已知戶外的天氣情況下活動的條件熵戶外有三個屬性值，晴，陰和雨。其熵分別為：H(活動|戶外=晴)=-(2/5)*log2(2/5)-(3/5)*log2(3/5)=0.971H(活動|戶外=陰)=-(4/4)*log2(4/4)=0H(活動|戶外=雨)=-(3/5)*log2(3/5)-(2/5)*log2(2/5)=0.971活動天氣進行取消晴陰雨已知戶外的天氣情況下活動的條件熵戶外有三個屬性值，晴，陰和雨17已知戶外時活動的條件熵H(活動|戶外)=5/14*H(活動|戶外=晴)+4/14*H(活動|戶外=陰)+5/14*H(活動|戶外=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693晴陰雨已知戶外時活動的條件熵H(活動|戶外)=5/14*H(活動|18平均互信息I(活動;戶外)=H(活動)-H(活動|戶外)=0.94-0.693=0.246平均互信息I(活動;戶外)=H(活動)-H(活動|戶19是否適合打壘球的決策表天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消是否適合打壘球的決策表天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎20活動的熵H(活動)=-(9/14)*lb

(9/14)-(5/14)*lb

(5/14)=0.94天氣

溫度

濕度

風(fēng)速

活動

陰

炎熱

高

弱

進行

雨

適中

高

弱

進行

雨

寒冷

正常

弱

進行

陰

寒冷

正常

強

進行

晴

寒冷

正常

弱

進行

雨

適中

正常

弱

進行

晴

適中

正常

強

進行

陰

適中

高

強

進行

陰

炎熱

正常

弱

進行

晴

炎熱

高

弱

取消

晴

炎熱

高

強

取消

雨

寒冷

正常

強

取消

晴

適中

高

弱

取消

雨

適中

高

強

取消

活動的熵H(活動)=-(9/14)*lb(9/14)21已知天氣時活動的條件熵H(活動|天氣)=5/14*H(活動|天氣=晴)+4/14*H(活動|天氣=陰)+5/14*H(活動|天氣=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693溫度

濕度

風(fēng)速

天氣

活動

寒冷

正常

弱

晴

進行

適中

正常

強

晴

進行

炎熱

高

弱

晴

取消

炎熱

高

強

晴

取消

適中

高

弱

晴

取消

炎熱

高

弱

陰

進行

寒冷

正常

強

陰

進行

適中

高

強

陰

進行

炎熱

正常

弱

陰

進行

適中

高

弱

雨

進行

寒冷

正常

弱

雨

進行

適中

正常

弱

雨

進行

寒冷

正常

強

雨

取消

適中

高

強

雨

取消

已知天氣時活動的條件熵H(活動|天氣)=5/14*H(活動|22天氣

濕度

風(fēng)速

溫度

活動

陰

高

弱

炎熱

進行

陰

正常

弱

炎熱

進行

晴

高

弱

炎熱

取消

晴

高

強

炎熱

取消

雨

高

弱

適中

進行

雨

正常

弱

適中

進行

晴

正常

強

適中

進行

陰

高

強

適中

進行

晴

高

弱

適中

取消

雨

高

強

適中

取消

雨

正常

弱

寒冷

進行

陰

正常

強

寒冷

進行

晴

正常

弱

寒冷

進行

雨

正常

強

寒冷

取消

已知溫度時活動的條件熵H(活動|溫度)=0.911天氣濕度風(fēng)速溫度活動陰高弱炎熱進行陰正23天氣

溫度

風(fēng)速

濕度

活動

陰

炎熱

弱

高

進行

雨

適中

弱

高

進行

陰

適中

強

高

進行

晴

炎熱

弱

高

取消

晴

炎熱

強

高

取消

晴

適中

弱

高

取消

雨

適中

強

高

取消

雨

寒冷

弱

正常

進行

陰

寒冷

強

正常

進行

晴

寒冷

弱

正常

進行

雨

適中

弱

正常

進行

晴

適中

強

正常

進行

陰

炎熱

弱

正常

進行

雨

寒冷

強

正常

取消

H(活動|濕度)

=0.789已知濕度時活動的條件熵天氣溫度風(fēng)速濕度活動陰炎熱弱高進行雨適24天氣

溫度

濕度

風(fēng)速

活動

陰

寒冷

正常

強

進行

晴

適中

正常

強

進行

陰

適中

高

強

進行

晴

炎熱

高

強

取消

雨

寒冷

正常

強

取消

雨

適中

高

強

取消

陰

炎熱

高

弱

進行

雨

適中

高

弱

進行

雨

寒冷

正常

弱

進行

晴

寒冷

正常

弱

進行

雨

適中

正常

弱

進行

陰

炎熱

正常

弱

進行

晴

炎熱

高

弱

取消

晴

適中

高

弱

取消

H(活動|風(fēng)速)=0.892已知風(fēng)速時活動的條件熵天氣溫度濕度風(fēng)速活動陰寒冷正常強進行晴25各互信息量I(活動;天氣)=H(活動)-H(活動|天氣)=0.94-0.693=0.246I(活動;溫度)=

H(活動)-H(活動|溫度)=0.94-0.911=0.029I(活動;濕度)=

H(活動)-H(活動|濕度)=0.94-0.789=0.151I(活動;風(fēng)速)=

H(活動)-H(活動|風(fēng)速)=0.94-0.892=0.048各互信息量I(活動;天氣)=H(活動)-H(活動|天26天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消溫度

濕度

風(fēng)速

活動

寒冷

正常

弱

進行

適中

正常

強

進行

炎熱

高

弱

取消

炎熱

高

強

取消

適中

高

弱

取消

溫度

濕度

風(fēng)速

活動

適中

高

弱

進行

寒冷

正常

弱

進行

適中

正常

弱

進行

寒冷

正常

強

取消

適中

高

強

取消

溫度濕度風(fēng)速活動炎熱高弱進行寒冷正常強進行適中高強進行炎熱正常弱進行陰晴雨天氣

溫度

濕度

風(fēng)速

活動

晴

寒冷

正常

弱

進行

晴

適中

正常

強

進行

晴

炎熱

高

弱

取消

晴

炎熱

高

強

取消

晴

適中

高

弱

取消

陰

炎熱

高

弱

進行

陰

寒冷

正常

強

進行

陰

適中

高

強

進行

陰

炎熱

正常

弱

進行

雨

適中

高

弱

進行

雨

寒冷

正常

弱

進行

雨

適中

正常

弱

進行

雨

寒冷

正常

強

取消

雨

適中

高

強

取消

天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進27ID3算法生成的決策樹ID3算法生成的決策樹28ID3算法ID3(A:條件屬性集合，d:決策屬性，U:訓(xùn)練集)返回一棵決策樹{ifU為空，返回一個值為Failure的單結(jié)點；//一般不會出現(xiàn)這種情況，為了程序的健壯性ifU是由其值均為相同決策屬性值的記錄組成，返回一個帶有該值的單結(jié)點；//此分支至此結(jié)束ifA為空，則返回一個單結(jié)點，其值為在U的記錄中找出的頻率最高的決策屬性值；//這時對記錄將出現(xiàn)誤分類將A中屬性之間具有最大I(d;a)的屬性賦給a；將屬性a的值賦給{aj|j=1,2,…,m}；將分別由對應(yīng)于a的值的aj的記錄組成的U的子集賦值給{uj|j=1,2,…,m}；返回一棵樹，其根標(biāo)記為a，樹枝標(biāo)記為a1,a2,…,am；再分別構(gòu)造以下樹：ID3(A-{a},d,u1)，ID3(A-{a},d,u2)，…，ID3(A-{a},d,um)；//遞歸算法}ID3算法ID3(A:條件屬性集合，d:決策屬性，U:訓(xùn)練集292003.11.1830決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際問題確定決策樹增長的深度處理連續(xù)值的屬性選擇一個適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價的屬性提高計算效率針對這些問題，ID3被擴展成C4.52003.11.1830決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際2003.11.1831避免過度擬合數(shù)據(jù)過度擬合對于一個假設(shè)，當(dāng)存在其他的假設(shè)對訓(xùn)練樣例的擬合比它差，但事實上在實例的整個分布上表現(xiàn)得卻更好時，我們說這個假設(shè)過度擬合訓(xùn)練樣例定義：給定一個假設(shè)空間H，一個假設(shè)hH，如果存在其他的假設(shè)h’H，使得在訓(xùn)練樣例上h的錯誤率比h’小，但在整個實例分布上h’的錯誤率比h小，那么就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。2003.11.1831避免過度擬合數(shù)據(jù)過度擬合2003.11.1832避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因一種可能原因是訓(xùn)練樣例含有隨機錯誤或噪聲當(dāng)訓(xùn)練數(shù)據(jù)沒有噪聲時，過度擬合也有可能發(fā)生，特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點時，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實際的目標(biāo)函數(shù)并無關(guān)系。2003.11.1832避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的33避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點第一種方法更直觀第一種方法中，精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功33避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法2003.11.1834避免過度擬合數(shù)據(jù)（4）避免過度擬合的關(guān)鍵使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模解決方法使用與訓(xùn)練樣例截然不同的一套分離的樣例，來評估通過后修剪方法從樹上修建節(jié)點的效用。使用所有可用數(shù)據(jù)進行訓(xùn)練，但進行統(tǒng)計測試來估計擴展（或修剪）一個特定的節(jié)點是否有可能改善在訓(xùn)練集合外的實例上的性能。使用一個明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，當(dāng)這個編碼的長度最小時停止樹增長。2003.11.1834避免過度擬合數(shù)據(jù)（4）避免過度擬合的2003.11.1835避免過度擬合數(shù)據(jù)（5）方法評述第一種方法是最普通的，常被稱為訓(xùn)練和驗證集法?？捎脭?shù)據(jù)分成兩個樣例集合：訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè)驗證集合，評估這個假設(shè)在后續(xù)數(shù)據(jù)上的精度方法的動機：即使學(xué)習(xí)器可能會被訓(xùn)練集合誤導(dǎo)，但驗證集合不大可能表現(xiàn)出同樣的隨機波動驗證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計意義的實例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗證集合。2003.11.1835避免過度擬合數(shù)據(jù)（5）方法評述2003.11.1836錯誤率降低修剪將樹上的每一個節(jié)點作為修剪得候選對象修剪步驟刪除以此節(jié)點為根的子樹，使它成為葉結(jié)點把和該節(jié)點關(guān)聯(lián)的訓(xùn)練樣例的最常見分類賦給它反復(fù)修剪節(jié)點，每次總是選取那些刪除后可以最大提高決策樹在驗證集合上的精度的節(jié)點繼續(xù)修剪，直到進一步的修剪是有害的為止數(shù)據(jù)分成3個子集訓(xùn)練樣例，形成決策樹驗證樣例，修剪決策樹測試樣例，精度的無偏估計如果有大量的數(shù)據(jù)可供使用，那么使用分離的數(shù)據(jù)集合來引導(dǎo)修剪2003.11.1836錯誤率降低修剪將樹上的每一個節(jié)點作為2003.11.1837規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好地擬合訓(xùn)練數(shù)據(jù)，允許過度擬合發(fā)生將決策樹轉(zhuǎn)化為等價的規(guī)則集合，方法是為從根節(jié)點到葉節(jié)點的每一條路徑創(chuàng)建一條規(guī)則通過刪除任何能導(dǎo)致估計精度提高的前件來修剪每一條規(guī)則按照修剪過的規(guī)則的估計精度對它們進行排序，并按這樣的順序應(yīng)用這些規(guī)則來分類后來的實例2003.11.1837規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增2003.11.1838規(guī)則后修剪（2）例子if(outlook=sunny)(Humidity=High)thenPlayTennis=No考慮刪除先行詞(outlook=sunny)和(Humidity=High)選擇使估計精度有最大提升的步驟考慮修剪第二個前件2003.11.1838規(guī)則后修剪（2）例子2003.11.1839規(guī)則后修剪（3）規(guī)則精度估計方法使用與訓(xùn)練集不相交的驗證集基于訓(xùn)練集合本身被C4.5使用，使用一種保守估計來彌補訓(xùn)練數(shù)據(jù)有利于當(dāng)前規(guī)則的估計偏置過程先計算規(guī)則在它應(yīng)用的訓(xùn)練樣例上的精度然后假定此估計精度為二項式分布，并計算它的標(biāo)準(zhǔn)差對于一個給定的置信區(qū)間，采用下界估計作為規(guī)則性能的度量評論對于大的數(shù)據(jù)集，保守預(yù)測非常接近觀察精度，隨著數(shù)據(jù)集合的減小，離觀察精度越來越遠不是統(tǒng)計有效，但是實踐中發(fā)現(xiàn)有效2003.11.1839規(guī)則后修剪（3）規(guī)則精度估計方法2003.11.1840規(guī)則后修剪（4）把決策樹轉(zhuǎn)化成規(guī)則集的好處可以區(qū)分決策節(jié)點使用的不同上下文消除了根節(jié)點附近的屬性測試和葉節(jié)點附近的屬性測試的區(qū)別提高了可讀性2003.11.1840規(guī)則后修剪（4）把決策樹轉(zhuǎn)化成規(guī)則集2003.11.1841合并連續(xù)值屬性ID3被限制為取離散值的屬性學(xué)習(xí)到的決策樹要預(yù)測的目標(biāo)屬性必須是離散的樹的決策節(jié)點的屬性也必須是離散的簡單刪除上面第2個限制的方法通過動態(tài)地定義新的離散值屬性來實現(xiàn)，即先把連續(xù)值屬性的值域分割為離散的區(qū)間集合2003.11.1841合并連續(xù)值屬性ID3被限制為取離散值2003.11.1842合并連續(xù)值屬性（2）例子，Temperature應(yīng)該定義什么樣的基于閾值的布爾屬性選擇產(chǎn)生最大信息增益的閾值按照連續(xù)屬性排列樣例，確定目標(biāo)分類不同的相鄰實例產(chǎn)生一組候選閾值，它們的值是相應(yīng)的A值之間的中間值可以證明產(chǎn)生最大信息增益的c值位于這樣的邊界中（Fayyad1991）通過計算與每個候選閾值關(guān)聯(lián)的信息增益評估這些候選值方法的擴展連續(xù)的屬性分割成多個區(qū)間，而不是單一閾值的兩個空間2003.11.1842合并連續(xù)值屬性（2）例子，Tempe2003.11.1843小結(jié)和補充讀物決策樹學(xué)習(xí)為概念學(xué)習(xí)和學(xué)習(xí)其他離散值的函數(shù)提供了一個實用的方法ID3算法貪婪算法從根向下推斷決策樹搜索完整的假設(shè)空間歸納偏置，較小的樹過度擬合問題ID3算法的擴展2003.11.1843小結(jié)和補充讀物決策樹學(xué)習(xí)為概念學(xué)習(xí)和2003.11.1844附錄C4.5isasoftwareextensionofthebasicID3algorithmdesignedbyQuinlantoaddressthefollowingissuesnotdealtwithbyID3:AvoidingoverfittingthedataDetermininghowdeeplytogrowadecisiontree.Reducederrorpruning.Rulepost-pruning.Handlingcontinuousattributes.e.g.,temperatureChoosinganappropriateattributeselectionmeasure.Handlingtrainingdatawithmissingattributevalues.Handlingattributeswithdifferingcosts.Improvingcomputationalefficiency.2003.11.1844附錄C4.5isasoftwa分類器評價標(biāo)準(zhǔn)預(yù)測準(zhǔn)確度計算復(fù)雜度模型描述的簡潔度：產(chǎn)生式規(guī)則分類器評價標(biāo)準(zhǔn)預(yù)測準(zhǔn)確度45準(zhǔn)確度分析一般采用召回率r(Recall)和精準(zhǔn)率p(Precision)這兩個指標(biāo)衡量分類器的準(zhǔn)確度?！獋€好的分類器應(yīng)同時具有較高的召回率和精準(zhǔn)率，當(dāng)然這兩個指標(biāo)一般情況下是互斥的，有時要根據(jù)需要在這兩個指標(biāo)間作某種權(quán)衡和妥協(xié)。準(zhǔn)確度分析一般采用召回率r(Recall)和精準(zhǔn)率p(Pre46召回率r(Recall)和精準(zhǔn)率p(Precision)為了定義這兩個指標(biāo)，引入分類中常用的兩個基本概念，Relevant和Retrieved。Relevant：真正屬于某類的集合Retrieved：判斷屬于某類的集合召回率反映了分類器正確分類的對象在真正歸入該類的對象中所占的比率，而精準(zhǔn)率反映了分類器正確分類的對象在系統(tǒng)歸入該類的對象中所占的比率。RelevantRetrievedRelevant∩RetrievedRelevantRetrievedRelevant∩Retrieved召回率r(Recall)和精準(zhǔn)率p(Precision)為了47F1召回率和精準(zhǔn)率反映了分類質(zhì)量的兩個不同側(cè)面，兩者必須綜合考慮，不可偏廢，因此，可引入一種新的評價指標(biāo)F1，該指標(biāo)綜合了這兩種因素，其公式如下：F1召回率和精準(zhǔn)率反映了分類質(zhì)量的兩個不同側(cè)面，兩者必須綜合48構(gòu)造分類器的主要步驟將現(xiàn)有的已知類別的數(shù)據(jù)劃分為訓(xùn)練集和測試集兩部分。構(gòu)造分類算法對訓(xùn)練集進行學(xué)習(xí)，得到一個分類模型，它可以以分類規(guī)則、決策樹或數(shù)學(xué)公式等形式給出。使用分類模型對測試集進行檢測，如果符合測試要求（如分類精度），則進行④；否則，返回②。應(yīng)用得到的分類模型對未知類別的數(shù)據(jù)進行分類。構(gòu)造分類器的主要步驟將現(xiàn)有的已知類別的數(shù)據(jù)劃分為訓(xùn)練集和測試49訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)的劃分方法其中，對于步驟(1)，目前主要有兩種劃分方法：保持（holdout）方法。保持方法將已知數(shù)據(jù)隨機劃分為訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)兩部分，一般是三分之二作為訓(xùn)練數(shù)據(jù)，另外三分之一作為測試數(shù)據(jù)。使用訓(xùn)練數(shù)據(jù)導(dǎo)出分類模型，它在測試數(shù)據(jù)上的分類精度作為最終的分類精度。k折交叉驗證（k-foldcrossvalidation）方法。k折交叉驗證則將已知數(shù)據(jù)隨機劃分為k個大致相等的數(shù)據(jù)子集S1，S2，…，Sk，訓(xùn)練和測試重復(fù)進行k次。在第i次過程中，Si作為測試數(shù)據(jù)，其余的子集則作為訓(xùn)練數(shù)據(jù)。最終分類器的分類精度取k次測試分類精度的平均值。這種方法適用于原始數(shù)據(jù)量較小的情況，這時不適合直接應(yīng)用保持方法。訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)的劃分方法其中，對于步驟(1)，目前主要有50作業(yè)給出決策樹方法的模型、策略、算法；C4.5決策樹方法中的信息增益比的特點?C4.5決策樹方法生成的決策樹的特點？作業(yè)給出決策樹方法的模型、策略、算法；51謝謝！謝謝！52演講完畢，謝謝觀看！演講完畢，謝謝觀看！53決策樹模型決策樹模型54排名挖掘主題算法得票數(shù)發(fā)表時間作者陳述人1分類C4.5611993Quinlan,J.RHiroshiMotoda2聚類k-Means601967MacQueen,J.BJoydeepGhosh3統(tǒng)計學(xué)習(xí)SVM581995Vapnik,V.NQiangYang4關(guān)聯(lián)分析Apriori521994RakeshAgrawalChristosFaloutsos5統(tǒng)計學(xué)習(xí)EM482000McLachlan,GJoydeepGhosh6鏈接挖掘PageRank461998Brin,S.ChristosFaloutsos7集裝與推進AdaBoost451997Freund,Y.Zhi-HuaZhou8分類kNN451996Hastie,TVipinKumar9分類Na?veBayes452001Hand,D.JQiangYang10分類CART341984L.BreimanDanSteinberg共有145人參加了ICDM2006Panel(會議的專題討論),并對18種候選算法進行投票，選出了數(shù)據(jù)挖掘10大算法ICDM2006會議的算法投票結(jié)果排名挖掘主題算法得票數(shù)發(fā)表時間作者陳述人1分類C4.561155信息的定量描述衡量信息多少的物理量稱為信息量。若概率很大，受信者事先已有所估計，則該消息信息量就很??；若概率很小，受信者感覺很突然，該消息所含信息量就很大。信息的定量描述衡量信息多少的物理量稱為信息量。56信息量的定義根據(jù)客觀事實和人們的習(xí)慣概念，函數(shù)f(p)應(yīng)滿足以下條件：f(p)應(yīng)是概率p的嚴(yán)格單調(diào)遞減函數(shù)，即當(dāng)p1>p2，f(p1)<f(p2)；當(dāng)p=1時，f(p)=0；當(dāng)p=0時，f(p)=∞；兩個獨立事件的聯(lián)合信息量應(yīng)等于它們分別的信息量之和。信息量的定義根據(jù)客觀事實和人們的習(xí)慣概念，函數(shù)f(p)應(yīng)滿足57對信息量的

認(rèn)識理解

信息量的定義若一個消息x出現(xiàn)的概率為p，則這一消息所含的信息量為其中，對數(shù)的底大于1信息量單位以2為底時，單位為bit（binaryunit，比特）以e為底時，單位為nat（naturalunit，奈特）以10為底時，單位為hart（Hartley，哈特）對信息量的

認(rèn)識理解

信息量的定義58拋一枚均勻硬幣，出現(xiàn)正面與反面的信息量是多少？解：出現(xiàn)正面與反面的概率均為0.5，它們的信息量是I(正)=-lbp(正)=-lb0.5=1bI(反)=-lbp(反)=-lb0.5=1b拋一枚均勻硬幣，出現(xiàn)正面與反面的信息量是多少？59拋一枚畸形硬幣，出現(xiàn)正面與反面的概率分別是1/4，3/4，出現(xiàn)正面與反面時的信息量是多少？解：出現(xiàn)正面與反面的概率分別是1/4，3/4，它們的信息量是I(正)=-lbp(正)=-lb1/4=2bI(反)=-lbp(反)=-lb3/4=0.415b拋一枚畸形硬幣，出現(xiàn)正面與反面的概率分別是1/4，3/4，出60信源含有的信息量是信源發(fā)出的所有可能消息的平均不確定性，香農(nóng)把信源所含有的信息量稱為信息熵，是指每個符號所含信息量的統(tǒng)計平均值。m種符號的平均信息量為信源含有的信息量是信源發(fā)出的所有可能消息的平均不確定性，香農(nóng)61拋一枚均勻硬幣的信息熵是多少？解：出現(xiàn)正面與反面的概率均為0.5，信息熵是拋一枚均勻硬幣的信息熵是多少？62拋一枚畸形硬幣，出現(xiàn)正面與反面的概率分別是1/4，3/4，出現(xiàn)正面與反面時的信息量是多少？解：出現(xiàn)正面與反面的概率分別是1/4，3/4，信息熵是拋一枚畸形硬幣，出現(xiàn)正面與反面的概率分別是1/4，3/4，出63例：氣象預(yù)報例：氣象預(yù)報6465條件自信息量在事件yj出現(xiàn)的條件下，隨機事件xi發(fā)生的條件概率為p(xi|yj)，則它的條件自信息量定義為條件概率對數(shù)的負(fù)值：12條件自信息量在事件yj出現(xiàn)的條件下，隨機事件xi發(fā)生的條66條件熵在給定yj條件下，xi的條件自信息量為I(xi|yj),X集合的條件熵H(X|yj)為在給定Y(即各個yj

)條件下,X集合的條件熵H(X|Y)條件熵H(X|Y)表示已知Y后，X的不確定度13條件熵在給定yj條件下，xi的條件自信息量為I(xi|是否適合打壘球的決策表天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消是否適合打壘球的決策表天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎67活動天氣是否進行壘球活動進行取消晴陰雨晴陰雨活動進行取消活動天氣是否進行壘球活動進行取消晴陰雨晴陰雨活動進行68活動的熵活動有2個屬性值，進行，取消。其熵為：H(活動)=-(9/14)*log

(9/14)-(5/14)*log

(5/14)=0.94活動進行取消活動的熵活動有2個屬性值，進行，取消。其熵為：活動進行取消69已知戶外的天氣情況下活動的條件熵戶外有三個屬性值，晴，陰和雨。其熵分別為：H(活動|戶外=晴)=-(2/5)*log2(2/5)-(3/5)*log2(3/5)=0.971H(活動|戶外=陰)=-(4/4)*log2(4/4)=0H(活動|戶外=雨)=-(3/5)*log2(3/5)-(2/5)*log2(2/5)=0.971活動天氣進行取消晴陰雨已知戶外的天氣情況下活動的條件熵戶外有三個屬性值，晴，陰和雨70已知戶外時活動的條件熵H(活動|戶外)=5/14*H(活動|戶外=晴)+4/14*H(活動|戶外=陰)+5/14*H(活動|戶外=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693晴陰雨已知戶外時活動的條件熵H(活動|戶外)=5/14*H(活動|71平均互信息I(活動;戶外)=H(活動)-H(活動|戶外)=0.94-0.693=0.246平均互信息I(活動;戶外)=H(活動)-H(活動|戶72是否適合打壘球的決策表天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消是否適合打壘球的決策表天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎73活動的熵H(活動)=-(9/14)*lb

(9/14)-(5/14)*lb

(5/14)=0.94天氣

溫度

濕度

風(fēng)速

活動

陰

炎熱

高

弱

進行

雨

適中

高

弱

進行

雨

寒冷

正常

弱

進行

陰

寒冷

正常

強

進行

晴

寒冷

正常

弱

進行

雨

適中

正常

弱

進行

晴

適中

正常

強

進行

陰

適中

高

強

進行

陰

炎熱

正常

弱

進行

晴

炎熱

高

弱

取消

晴

炎熱

高

強

取消

雨

寒冷

正常

強

取消

晴

適中

高

弱

取消

雨

適中

高

強

取消

活動的熵H(活動)=-(9/14)*lb(9/14)74已知天氣時活動的條件熵H(活動|天氣)=5/14*H(活動|天氣=晴)+4/14*H(活動|天氣=陰)+5/14*H(活動|天氣=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693溫度

濕度

風(fēng)速

天氣

活動

寒冷

正常

弱

晴

進行

適中

正常

強

晴

進行

炎熱

高

弱

晴

取消

炎熱

高

強

晴

取消

適中

高

弱

晴

取消

炎熱

高

弱

陰

進行

寒冷

正常

強

陰

進行

適中

高

強

陰

進行

炎熱

正常

弱

陰

進行

適中

高

弱

雨

進行

寒冷

正常

弱

雨

進行

適中

正常

弱

雨

進行

寒冷

正常

強

雨

取消

適中

高

強

雨

取消

已知天氣時活動的條件熵H(活動|天氣)=5/14*H(活動|75天氣

濕度

風(fēng)速

溫度

活動

陰

高

弱

炎熱

進行

陰

正常

弱

炎熱

進行

晴

高

弱

炎熱

取消

晴

高

強

炎熱

取消

雨

高

弱

適中

進行

雨

正常

弱

適中

進行

晴

正常

強

適中

進行

陰

高

強

適中

進行

晴

高

弱

適中

取消

雨

高

強

適中

取消

雨

正常

弱

寒冷

進行

陰

正常

強

寒冷

進行

晴

正常

弱

寒冷

進行

雨

正常

強

寒冷

取消

已知溫度時活動的條件熵H(活動|溫度)=0.911天氣濕度風(fēng)速溫度活動陰高弱炎熱進行陰正76天氣

溫度

風(fēng)速

濕度

活動

陰

炎熱

弱

高

進行

雨

適中

弱

高

進行

陰

適中

強

高

進行

晴

炎熱

弱

高

取消

晴

炎熱

強

高

取消

晴

適中

弱

高

取消

雨

適中

強

高

取消

雨

寒冷

弱

正常

進行

陰

寒冷

強

正常

進行

晴

寒冷

弱

正常

進行

雨

適中

弱

正常

進行

晴

適中

強

正常

進行

陰

炎熱

弱

正常

進行

雨

寒冷

強

正常

取消

H(活動|濕度)

=0.789已知濕度時活動的條件熵天氣溫度風(fēng)速濕度活動陰炎熱弱高進行雨適77天氣

溫度

濕度

風(fēng)速

活動

陰

寒冷

正常

強

進行

晴

適中

正常

強

進行

陰

適中

高

強

進行

晴

炎熱

高

強

取消

雨

寒冷

正常

強

取消

雨

適中

高

強

取消

陰

炎熱

高

弱

進行

雨

適中

高

弱

進行

雨

寒冷

正常

弱

進行

晴

寒冷

正常

弱

進行

雨

適中

正常

弱

進行

陰

炎熱

正常

弱

進行

晴

炎熱

高

弱

取消

晴

適中

高

弱

取消

H(活動|風(fēng)速)=0.892已知風(fēng)速時活動的條件熵天氣溫度濕度風(fēng)速活動陰寒冷正常強進行晴78各互信息量I(活動;天氣)=H(活動)-H(活動|天氣)=0.94-0.693=0.246I(活動;溫度)=

H(活動)-H(活動|溫度)=0.94-0.911=0.029I(活動;濕度)=

H(活動)-H(活動|濕度)=0.94-0.789=0.151I(活動;風(fēng)速)=

H(活動)-H(活動|風(fēng)速)=0.94-0.892=0.048各互信息量I(活動;天氣)=H(活動)-H(活動|天79天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消溫度

濕度

風(fēng)速

活動

寒冷

正常

弱

進行

適中

正常

強

進行

炎熱

高

弱

取消

炎熱

高

強

取消

適中

高

弱

取消

溫度

濕度

風(fēng)速

活動

適中

高

弱

進行

寒冷

正常

弱

進行

適中

正常

弱

進行

寒冷

正常

強

取消

適中

高

強

取消

溫度濕度風(fēng)速活動炎熱高弱進行寒冷正常強進行適中高強進行炎熱正常弱進行陰晴雨天氣

溫度

濕度

風(fēng)速

活動

晴

寒冷

正常

弱

進行

晴

適中

正常

強

進行

晴

炎熱

高

弱

取消

晴

炎熱

高

強

取消

晴

適中

高

弱

取消

陰

炎熱

高

弱

進行

陰

寒冷

正常

強

進行

陰

適中

高

強

進行

陰

炎熱

正常

弱

進行

雨

適中

高

弱

進行

雨

寒冷

正常

弱

進行

雨

適中

正常

弱

進行

雨

寒冷

正常

強

取消

雨

適中

高

強

取消

天氣溫度濕度風(fēng)速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進80ID3算法生成的決策樹ID3算法生成的決策樹81ID3算法ID3(A:條件屬性集合，d:決策屬性，U:訓(xùn)練集)返回一棵決策樹{ifU為空，返回一個值為Failure的單結(jié)點；//一般不會出現(xiàn)這種情況，為了程序的健壯性ifU是由其值均為相同決策屬性值的記錄組成，返回一個帶有該值的單結(jié)點；//此分支至此結(jié)束ifA為空，則返回一個單結(jié)點，其值為在U的記錄中找出的頻率最高的決策屬性值；//這時對記錄將出現(xiàn)誤分類將A中屬性之間具有最大I(d;a)的屬性賦給a；將屬性a的值賦給{aj|j=1,2,…,m}；將分別由對應(yīng)于a的值的aj的記錄組成的U的子集賦值給{uj|j=1,2,…,m}；返回一棵樹，其根標(biāo)記為a，樹枝標(biāo)記為a1,a2,…,am；再分別構(gòu)造以下樹：ID3(A-{a},d,u1)，ID3(A-{a},d,u2)，…，ID3(A-{a},d,um)；//遞歸算法}ID3算法ID3(A:條件屬性集合，d:決策屬性，U:訓(xùn)練集822003.11.1883決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際問題確定決策樹增長的深度處理連續(xù)值的屬性選擇一個適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價的屬性提高計算效率針對這些問題，ID3被擴展成C4.52003.11.1830決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際2003.11.1884避免過度擬合數(shù)據(jù)過度擬合對于一個假設(shè)，當(dāng)存在其他的假設(shè)對訓(xùn)練樣例的擬合比它差，但事實上在實例的整個分布上表現(xiàn)得卻更好時，我們說這個假設(shè)過度擬合訓(xùn)練樣例定義：給定一個假設(shè)空間H，一個假設(shè)hH，如果存在其他的假設(shè)h’H，使得在訓(xùn)練樣例上h的錯誤率比h’小，但在整個實例分布上h’的錯誤率比h小，那么就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。2003.11.1831避免過度擬合數(shù)據(jù)過度擬合2003.11.1885避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因一種可能原因是訓(xùn)練樣例含有隨機錯誤或噪聲當(dāng)訓(xùn)練數(shù)據(jù)沒有噪聲時，過度擬合也有可能發(fā)生，特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點時，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實際的目標(biāo)函數(shù)并無關(guān)系。2003.11.1832避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的86避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點第一種方法更直觀第一種方法中，精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功33避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法2003.11.1887避免過度擬合數(shù)據(jù)（4）避免過度擬合的關(guān)鍵使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模解決方法使用與訓(xùn)練樣例截然不同的一套分離的樣例，來評估通過后修剪方法從樹上修建節(jié)點的效用。使用所有可用數(shù)據(jù)進行訓(xùn)練，但進行統(tǒng)計測試來估計擴展（或修剪）一個特定的節(jié)點是否有可能改善在訓(xùn)練集合外的實例上的性能。使用一個明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，當(dāng)這個編碼的長度最小時停止樹增長。2003.11.1834避免過度擬合數(shù)據(jù)（4）避免過度擬合的2003.11.1888避免過度擬合數(shù)據(jù)（5）方法評述第一種方法是最普通的，常被稱為訓(xùn)練和驗證集法?？捎脭?shù)據(jù)分成兩個樣例集合：訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè)驗證集合，評估這個假設(shè)在后續(xù)數(shù)據(jù)上的精度方法的動機：即使學(xué)習(xí)器可能會被訓(xùn)練集合誤導(dǎo)，但驗證集合不大可能表現(xiàn)出同樣的隨機波動驗證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計意義的實例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗證集合。2003.11.1835避免過度擬合數(shù)據(jù)（5）方法評述2003.11.1889錯誤率降低修剪將樹上的每一個節(jié)點作為修剪得候選對象修剪步驟刪除以此節(jié)點為根的子樹，使它成為葉結(jié)點把和該節(jié)點關(guān)聯(lián)的訓(xùn)練樣例的最常見分類賦給它反復(fù)修剪節(jié)點，每次總是選取那些刪除后可以最大提高決策樹在驗證集合上的精度的節(jié)點繼續(xù)修剪，直到進一步的修剪是有害的為止數(shù)據(jù)分成3個子集訓(xùn)練樣例，形成決策樹驗證樣例，修剪決策樹測試樣例，精度的無偏估計如果有大量的數(shù)據(jù)可供使用，那么使用分離的數(shù)據(jù)集合來引導(dǎo)修剪2003.11.1836錯誤率降低修剪將樹上的每一個節(jié)點作為2003.11.1890規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好地擬合訓(xùn)練數(shù)據(jù)，允許過度擬合發(fā)生將決策樹轉(zhuǎn)化為等價的規(guī)則集合，方法是為從根節(jié)點到葉節(jié)點的每一條路徑創(chuàng)建一條規(guī)則通過刪除任何能導(dǎo)致估計精度提高的前件來修剪每一條規(guī)則按照修剪過的規(guī)則的估計精度對它們進行排序，并按這樣的順序應(yīng)用這些規(guī)則來分類后來的實例2003.11.1837規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增2003.11.1891規(guī)則后修剪（2）例子if(outlook=sunny)(Humidity=High)thenPlayTennis=No考慮刪除先行詞(outlook=sunny)和(Humidity=High)選擇使估計精度有最大提升的步驟考慮修剪第二個前件2003.11.1838規(guī)則后修剪（2）例子2003.11.1892規(guī)則后修剪（3）規(guī)則精度估計方法使用與訓(xùn)練集不相交的驗證集基于訓(xùn)練集合本身被C4.5使用，使用一種保守估計來彌補訓(xùn)練數(shù)據(jù)有利于當(dāng)前規(guī)則的估計偏置過程先計算規(guī)則在它應(yīng)用的訓(xùn)練樣例上的精度然后假定此估計精度為二項式分布，并計算它的標(biāo)準(zhǔn)差對于一個給定的置信區(qū)間，采用下界估計作為規(guī)則性能的度量評論對于大的數(shù)據(jù)集，保守預(yù)測非常接近觀察精度，隨著數(shù)據(jù)集合的減小，離觀察精度越來越遠不是統(tǒng)計有效，但是實踐中發(fā)現(xiàn)有效2003.11.1839規(guī)則后修剪（3）規(guī)則精度估計方法2003.11.1893規(guī)則后修剪（4）把決策樹轉(zhuǎn)化成規(guī)則集的好處可以區(qū)分決策節(jié)點使用的不同上下文消除了根節(jié)點附近的屬性測試和葉節(jié)點附近的屬性測試的區(qū)別提高了可讀性2003.11.1840規(guī)則后修剪（4）把決策樹轉(zhuǎn)化成規(guī)則集2003.11.1894合并連續(xù)值屬性ID3被限制為取離散值的屬性學(xué)習(xí)到的決策樹要預(yù)測的目標(biāo)屬性必須是離散的樹的決策節(jié)點的屬性也必須是離散的