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

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

認(rèn)識(shí)理解

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

認(rèn)識(shí)理解

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

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

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

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

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

(5/14)=0.94天氣

溫度

濕度

風(fēng)速

活動(dòng)

陰

炎熱

高

弱

進(jìn)行

雨

適中

高

弱

進(jìn)行

雨

寒冷

正常

弱

進(jìn)行

陰

寒冷

正常

強(qiáng)

進(jìn)行

晴

寒冷

正常

弱

進(jìn)行

雨

適中

正常

弱

進(jìn)行

晴

適中

正常

強(qiáng)

進(jìn)行

陰

適中

高

強(qiáng)

進(jìn)行

陰

炎熱

正常

弱

進(jìn)行

晴

炎熱

高

弱

取消

晴

炎熱

高

強(qiáng)

取消

雨

寒冷

正常

強(qiáng)

取消

晴

適中

高

弱

取消

雨

適中

高

強(qiáng)

取消

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

濕度

風(fēng)速

天氣

活動(dòng)

寒冷

正常

弱

晴

進(jìn)行

適中

正常

強(qiáng)

晴

進(jìn)行

炎熱

高

弱

晴

取消

炎熱

高

強(qiáng)

晴

取消

適中

高

弱

晴

取消

炎熱

高

弱

陰

進(jìn)行

寒冷

正常

強(qiáng)

陰

進(jìn)行

適中

高

強(qiáng)

陰

進(jìn)行

炎熱

正常

弱

陰

進(jìn)行

適中

高

弱

雨

進(jìn)行

寒冷

正常

弱

雨

進(jìn)行

適中

正常

弱

雨

進(jìn)行

寒冷

正常

強(qiáng)

雨

取消

適中

高

強(qiáng)

雨

取消

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

濕度

風(fēng)速

溫度

活動(dòng)

陰

高

弱

炎熱

進(jìn)行

陰

正常

弱

炎熱

進(jìn)行

晴

高

弱

炎熱

取消

晴

高

強(qiáng)

炎熱

取消

雨

高

弱

適中

進(jìn)行

雨

正常

弱

適中

進(jìn)行

晴

正常

強(qiáng)

適中

進(jìn)行

陰

高

強(qiáng)

適中

進(jìn)行

晴

高

弱

適中

取消

雨

高

強(qiáng)

適中

取消

雨

正常

弱

寒冷

進(jìn)行

陰

正常

強(qiáng)

寒冷

進(jìn)行

晴

正常

弱

寒冷

進(jìn)行

雨

正常

強(qiáng)

寒冷

取消

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

溫度

風(fēng)速

濕度

活動(dòng)

陰

炎熱

弱

高

進(jìn)行

雨

適中

弱

高

進(jìn)行

陰

適中

強(qiáng)

高

進(jìn)行

晴

炎熱

弱

高

取消

晴

炎熱

強(qiáng)

高

取消

晴

適中

弱

高

取消

雨

適中

強(qiáng)

高

取消

雨

寒冷

弱

正常

進(jìn)行

陰

寒冷

強(qiáng)

正常

進(jìn)行

晴

寒冷

弱

正常

進(jìn)行

雨

適中

弱

正常

進(jìn)行

晴

適中

強(qiáng)

正常

進(jìn)行

陰

炎熱

弱

正常

進(jìn)行

雨

寒冷

強(qiáng)

正常

取消

H(活動(dòng)|濕度)

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

溫度

濕度

風(fēng)速

活動(dòng)

陰

寒冷

正常

強(qiáng)

進(jìn)行

晴

適中

正常

強(qiáng)

進(jìn)行

陰

適中

高

強(qiáng)

進(jìn)行

晴

炎熱

高

強(qiáng)

取消

雨

寒冷

正常

強(qiáng)

取消

雨

適中

高

強(qiáng)

取消

陰

炎熱

高

弱

進(jìn)行

雨

適中

高

弱

進(jìn)行

雨

寒冷

正常

弱

進(jìn)行

晴

寒冷

正常

弱

進(jìn)行

雨

適中

正常

弱

進(jìn)行

陰

炎熱

正常

弱

進(jìn)行

晴

炎熱

高

弱

取消

晴

適中

高

弱

取消

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

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

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

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

濕度

風(fēng)速

活動(dòng)

寒冷

正常

弱

進(jìn)行

適中

正常

強(qiáng)

進(jìn)行

炎熱

高

弱

取消

炎熱

高

強(qiáng)

取消

適中

高

弱

取消

溫度

濕度

風(fēng)速

活動(dòng)

適中

高

弱

進(jìn)行

寒冷

正常

弱

進(jìn)行

適中

正常

弱

進(jìn)行

寒冷

正常

強(qiáng)

取消

適中

高

強(qiáng)

取消

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

溫度

濕度

風(fēng)速

活動(dòng)

晴

寒冷

正常

弱

進(jìn)行

晴

適中

正常

強(qiáng)

進(jìn)行

晴

炎熱

高

弱

取消

晴

炎熱

高

強(qiáng)

取消

晴

適中

高

弱

取消

陰

炎熱

高

弱

進(jìn)行

陰

寒冷

正常

強(qiáng)

進(jìn)行

陰

適中

高

強(qiáng)

進(jìn)行

陰

炎熱

正常

弱

進(jìn)行

雨

適中

高

弱

進(jìn)行

雨

寒冷

正常

弱

進(jìn)行

雨

適中

正常

弱

進(jìn)行

雨

寒冷

正常

強(qiáng)

取消

雨

適中

高

強(qiáng)

取消

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

認(rèn)識(shí)理解

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

認(rèn)識(shí)理解

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

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

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

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

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

(5/14)=0.94天氣

溫度

濕度

風(fēng)速

活動(dòng)

陰

炎熱

高

弱

進(jìn)行

雨

適中

高

弱

進(jìn)行

雨

寒冷

正常

弱

進(jìn)行

陰

寒冷

正常

強(qiáng)

進(jìn)行

晴

寒冷

正常

弱

進(jìn)行

雨

適中

正常

弱

進(jìn)行

晴

適中

正常

強(qiáng)

進(jìn)行

陰

適中

高

強(qiáng)

進(jìn)行

陰

炎熱

正常

弱

進(jìn)行

晴

炎熱

高

弱

取消

晴

炎熱

高

強(qiáng)

取消

雨

寒冷

正常

強(qiáng)

取消

晴

適中

高

弱

取消

雨

適中

高

強(qiáng)

取消

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

濕度

風(fēng)速

天氣

活動(dòng)

寒冷

正常

弱

晴

進(jìn)行

適中

正常

強(qiáng)

晴

進(jìn)行

炎熱

高

弱

晴

取消

炎熱

高

強(qiáng)

晴

取消

適中

高

弱

晴

取消

炎熱

高

弱

陰

進(jìn)行

寒冷

正常

強(qiáng)

陰

進(jìn)行

適中

高

強(qiáng)

陰

進(jìn)行

炎熱

正常

弱

陰

進(jìn)行

適中

高

弱

雨

進(jìn)行

寒冷

正常

弱

雨

進(jìn)行

適中

正常

弱

雨

進(jìn)行

寒冷

正常

強(qiáng)

雨

取消

適中

高

強(qiáng)

雨

取消

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

濕度

風(fēng)速

溫度

活動(dòng)

陰

高

弱

炎熱

進(jìn)行

陰

正常

弱

炎熱

進(jìn)行

晴

高

弱

炎熱

取消

晴

高

強(qiáng)

炎熱

取消

雨

高

弱

適中

進(jìn)行

雨

正常

弱

適中

進(jìn)行

晴

正常

強(qiáng)

適中

進(jìn)行

陰

高

強(qiáng)

適中

進(jìn)行

晴

高

弱

適中

取消

雨

高

強(qiáng)

適中

取消

雨

正常

弱

寒冷

進(jìn)行

陰

正常

強(qiáng)

寒冷

進(jìn)行

晴

正常

弱

寒冷

進(jìn)行

雨

正常

強(qiáng)

寒冷

取消

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

溫度

風(fēng)速

濕度

活動(dòng)

陰

炎熱

弱

高

進(jìn)行

雨

適中

弱

高

進(jìn)行

陰

適中

強(qiáng)

高

進(jìn)行

晴

炎熱

弱

高

取消

晴

炎熱

強(qiáng)

高

取消

晴

適中

弱

高

取消

雨

適中

強(qiáng)

高

取消

雨

寒冷

弱

正常

進(jìn)行

陰

寒冷

強(qiáng)

正常

進(jìn)行

晴

寒冷

弱

正常

進(jìn)行

雨

適中

弱

正常

進(jìn)行

晴

適中

強(qiáng)

正常

進(jìn)行

陰

炎熱

弱

正常

進(jìn)行

雨

寒冷

強(qiáng)

正常

取消

H(活動(dòng)|濕度)

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

溫度

濕度

風(fēng)速

活動(dòng)

陰

寒冷

正常

強(qiáng)

進(jìn)行

晴

適中

正常

強(qiáng)

進(jìn)行

陰

適中

高

強(qiáng)

進(jìn)行

晴

炎熱

高

強(qiáng)

取消

雨

寒冷

正常

強(qiáng)

取消

雨

適中

高

強(qiáng)

取消

陰

炎熱

高

弱

進(jìn)行

雨

適中

高

弱

進(jìn)行

雨

寒冷

正常

弱

進(jìn)行

晴

寒冷

正常

弱

進(jìn)行

雨

適中

正常

弱

進(jìn)行

陰

炎熱

正常

弱

進(jìn)行

晴

炎熱

高

弱

取消

晴

適中

高

弱

取消

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

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

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

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

濕度

風(fēng)速

活動(dòng)

寒冷

正常

弱

進(jìn)行

適中

正常

強(qiáng)

進(jìn)行

炎熱

高

弱

取消

炎熱

高

強(qiáng)

取消

適中

高

弱

取消

溫度

濕度

風(fēng)速

活動(dòng)

適中

高

弱

進(jìn)行

寒冷

正常

弱

進(jìn)行

適中

正常

弱

進(jìn)行

寒冷

正常

強(qiáng)

取消

適中

高

強(qiáng)

取消

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

溫度

濕度

風(fēng)速

活動(dòng)

晴

寒冷

正常

弱

進(jìn)行

晴

適中

正常

強(qiáng)

進(jìn)行

晴

炎熱

高

弱

取消

晴

炎熱

高

強(qiáng)

取消

晴

適中

高

弱

取消

陰

炎熱

高

弱

進(jìn)行

陰

寒冷

正常

強(qiáng)

進(jìn)行

陰

適中

高

強(qiáng)

進(jìn)行

陰

炎熱

正常

弱

進(jìn)行

雨

適中

高

弱

進(jìn)行

雨

寒冷

正常

弱

進(jìn)行

雨

適中

正常

弱

進(jìn)行

雨

寒冷

正常

強(qiáng)

取消

雨

適中

高

強(qiáng)

取消

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