機器學(xué)習(xí)-決策樹ID算法的實例解析

1、整理ppt決策樹模型決策樹模型整理ppt排名排名挖掘主題挖掘主題算法算法得票數(shù)得票數(shù)發(fā)表時間發(fā)表時間作者作者陳述陳述人人1分類C4.5611993Quinlan, J.RHiroshi Motoda2聚類k-Means 601967MacQueen, J.BJoydeep Ghosh3統(tǒng)計學(xué)習(xí)SVM 581995Vapnik, V.NQiangYang4關(guān)聯(lián)分析Apriori 521994Rakesh Agrawal Christos Faloutsos5統(tǒng)計學(xué)習(xí)EM482000McLachlan, GJoydeep Ghosh 6鏈接挖掘PageRank461998Brin, S.Chris

2、tos Faloutsos7集裝與推進AdaBoost451997Freund, Y.Zhi-Hua Zhou 8分類kNN451996Hastie, TVipin Kumar 9分類Nave Bayes452001Hand, D.JQiang Yang 10分類CART341984L.BreimanDan Steinberg 共有145人參加了ICDM 2006 Panel (會議的專題討論),并對18種候選算法進行投票，選出了數(shù)據(jù)挖掘10大算法ICDM 2006會議的算法投票結(jié)果會議的算法投票結(jié)果整理ppt信息的定量描述信息的定量描述整理ppt信息量的定義根據(jù)客觀事實和人們的習(xí)慣概念，函數(shù)

3、f(p)應(yīng)滿足以下條件：f(p)應(yīng)是概率p的嚴(yán)格單調(diào)遞減函數(shù)，即當(dāng)p1p2， f(p1)f(p2)；當(dāng)p=1時，f(p)=0；當(dāng)p=0時，f(p)=；1.兩個獨立事件的聯(lián)合信息量應(yīng)等于它們分別的信息量之和。整理ppt整理ppt整理pptiiiiiixpxpxIxpXH)(log)()()()(整理ppt b1) 5 . 0log5 . 05 . 0log5 . 0(log1iqiixpxpxH整理ppt b/symbol811. 0)4/1log4/34/1log4/1 (log1iqiixpxpxH整理ppt例：氣象預(yù)報整理ppt12條件自信息量在事件yj出現(xiàn)的條件下，隨機事件xi發(fā)生的條件

4、概率為p(xi | yj) ，則它的條件自信息量定義為條件概率對數(shù)的負(fù)值：)|(log)|(jijiyxpyxI整理ppt13條件熵條件熵在給定yj條件下，xi的條件自信息量為I(xi| yj), X集合的條件熵H(X|yj)為 在給定Y(即各個yj )條件下,X集合的條件熵H(X|Y)條件熵H(X|Y)表示已知Y后，X的不確定度整理ppt是否適合打壘球的決策表天氣天氣溫度溫度濕度濕度風(fēng)速風(fēng)速活動活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行

5、雨適中高強取消整理ppt是否進行壘球活動進行取消晴陰雨晴陰雨進行取消整理ppt活動的熵活動有2個屬性值，進行，取消。其熵為：H(活動) = - (9/14)*log (9/14) - (5/14)*log (5/14) = 0.94進行取消整理ppt已知戶外戶外的天氣情況下活動的條件熵戶外戶外有三個屬性值，晴，陰和雨。其熵分別為：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

6、/5) = 0.971進行取消晴陰雨整理ppt已知戶外戶外時時活動的條件熵H(活動|戶外)=5/14*H(活動|戶外=晴)+4/14*H(活動|戶外=陰) +5/14* H(活動|戶外=雨)= (5/14)*0.971 + (4/14)*0 +(5/14)*0.971= 0.693晴陰雨整理ppt平均互信息I(活動;戶外戶外) = H(活動) - H(活動|戶外) = 0.94- 0.693 = 0.246整理ppt是否適合打壘球的決策表天氣天氣溫度溫度濕度濕度風(fēng)速風(fēng)速活動活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消

7、晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消整理ppt活動的熵H(活動) = - (9/14)*lb (9/14) - (5/14)*lb (5/14) = 0.94天氣天氣 溫度溫度 濕度濕度 風(fēng)速風(fēng)速 活動活動 陰 炎熱 高 弱 進行 雨 適中 高 弱 進行 雨 寒冷 正常 弱 進行 陰 寒冷 正常 強 進行 晴 寒冷 正常 弱 進行 雨 適中 正常 弱 進行 晴 適中 正常 強 進行 陰 適中 高 強 進行 陰 炎熱 正常 弱 進行 晴 炎熱 高 弱 取消 晴 炎熱 高 強 取消 雨 寒冷 正常 強 取消 晴 適中 高 弱 取消 雨 適中

8、高 強 取消 整理ppt已知天氣時活動的條件熵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)速風(fēng)速 天氣天氣 活動活動 寒冷 正常 弱 晴 進行 適中 正常 強 晴 進行 炎熱 高 弱 晴 取消 炎熱 高 強 晴 取消 適中 高 弱 晴 取消 炎熱 高 弱 陰 進行 寒冷 正常 強 陰 進行 適中 高 強 陰 進行 炎熱 正常 弱 陰 進行 適中 高 弱 雨 進行 寒冷 正常 弱 雨 進行 適中

9、正常 弱 雨 進行 寒冷 正常 強 雨 取消 適中 高 強 雨 取消 整理ppt天氣天氣 濕度濕度 風(fēng)速風(fēng)速 溫度溫度 活動活動 陰 高 弱 炎熱 進行 陰 正常 弱 炎熱 進行 晴 高 弱 炎熱 取消 晴 高 強 炎熱 取消 雨 高 弱 適中 進行 雨 正常 弱 適中 進行 晴 正常 強 適中 進行 陰 高 強 適中 進行 晴 高 弱 適中 取消 雨 高 強 適中 取消 雨 正常 弱 寒冷 進行 陰 正常 強 寒冷 進行 晴 正常 弱 寒冷 進行 雨 正常 強 寒冷 取消 已知溫度時活動的條件熵H(活動|溫度) = 0.911整理ppt天氣天氣 溫度溫度 風(fēng)速風(fēng)速 濕度濕度 活動活動 陰 炎

10、熱 弱 高 進行 雨 適中 弱 高 進行 陰 適中 強 高 進行 晴 炎熱 弱 高 取消 晴 炎熱 強 高 取消 晴 適中 弱 高 取消 雨 適中 強 高 取消 雨 寒冷 弱 正常 進行 陰 寒冷 強 正常 進行 晴 寒冷 弱 正常 進行 雨 適中 弱 正常 進行 晴 適中 強 正常 進行 陰 炎熱 弱 正常 進行 雨 寒冷 強 正常 取消 H(活動|濕度) = 0.789已知濕度時活動的條件熵整理ppt天氣天氣 溫度溫度 濕度濕度 風(fēng)速風(fēng)速 活動活動 陰 寒冷 正常 強 進行 晴 適中 正常 強 進行 陰 適中 高 強 進行 晴 炎熱 高 強 取消 雨 寒冷 正常 強 取消 雨 適中 高 強

11、 取消 陰 炎熱 高 弱 進行 雨 適中 高 弱 進行 雨 寒冷 正常 弱 進行 晴 寒冷 正常 弱 進行 雨 適中 正常 弱 進行 陰 炎熱 正常 弱 進行 晴 炎熱 高 弱 取消 晴 適中 高 弱 取消 H(活動|風(fēng)速) = 0.892已知風(fēng)速時活動的條件熵整理ppt各互信息量I(活動活動;天氣天氣) = H(活動活動) - H(活動活動|天氣天氣) = 0.94- 0.693 = 0.246I(活動活動;溫度) = H(活動活動) - H(活動|溫度) = 0.94- 0.911 = 0.029I(活動活動;濕度) = H(活動活動) - H(活動|濕度) = 0.94- 0.789 =

12、 0.151I(活動活動;風(fēng)速) = H(活動活動) - H(活動|風(fēng)速) = 0.94- 0.892 = 0.048整理ppt天氣天氣溫度溫度濕度濕度風(fēng)速風(fēng)速活動活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消溫度溫度 濕度濕度 風(fēng)速風(fēng)速 活動活動 寒冷 正常 弱 進行 適中 正常 強 進行 炎熱 高 弱 取消 炎熱 高 強 取消 適中 高 弱 取消 溫度溫度 濕度濕度 風(fēng)速風(fēng)速 活動活動 適中 高 弱 進行 寒冷 正常 弱 進

13、行 適中 正常 弱 進行 寒冷 正常 強 取消 適中 高 強 取消 溫度 濕度 風(fēng)速 活動 炎熱 高 弱 進行 寒冷 正常 強 進行 適中 高 強 進行 炎熱 正常 弱 進行 陰晴雨天氣天氣 溫度溫度 濕度濕度 風(fēng)速風(fēng)速 活動活動 晴 寒冷 正常 弱 進行 晴 適中 正常 強 進行 晴 炎熱 高 弱 取消 晴 炎熱 高 強 取消 晴 適中 高 弱 取消 陰 炎熱 高 弱 進行 陰 寒冷 正常 強 進行 陰 適中 高 強 進行 陰 炎熱 正常 弱 進行 雨 適中 高 弱 進行 雨 寒冷 正常 弱 進行 雨 適中 正常 弱 進行 雨 寒冷 正常 強 取消 雨 適中 高 強 取消 整理pptID3算

14、法生成的決策樹整理pptID3算法ID3(A:條件屬性集合，d:決策屬性，U:訓(xùn)練集)返回一棵決策樹if U為空，返回一個值為Failure的單結(jié)點；/一般不會出現(xiàn)這種情況，為了程序的健壯性if U是由其值均為相同決策屬性值的記錄組成，返回一個帶有該值的單結(jié)點；/此分支至此結(jié)束if A為空，則返回一個單結(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；再

15、分別構(gòu)造以下樹：ID3(A-a,d,u1)，ID3(A-a,d,u2)，ID3(A-a,d,um)；/遞歸算法2003.11.18整理ppt30決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際問題確定決策樹增長的深度處理連續(xù)值的屬性選擇一個適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價的屬性提高計算效率針對這些問題，ID3被擴展成C4.52003.11.18整理ppt31避免過度擬合數(shù)據(jù)過度擬合對于一個假設(shè)，當(dāng)存在其他的假設(shè)對訓(xùn)練樣例的擬合比它差，但事實上在實例的整個分布上表現(xiàn)得卻更好時，我們說這個假設(shè)過度擬合訓(xùn)練樣例定義：給定一個假設(shè)空間H，一個假設(shè)hH，如果存在其他的假設(shè)hH，使得在訓(xùn)練

16、樣例上h的錯誤率比h小，但在整個實例分布上h的錯誤率比h小，那么就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。2003.11.18整理ppt32避免過度擬合數(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)系。整理ppt33避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點第一種方法更直觀第一種方法中，精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功2003.11.18整理ppt34避免過度

17、擬合數(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.18整理ppt35避免過度擬合數(shù)據(jù)（5）方法評述第一種方法是最普通的，常被稱為訓(xùn)練和驗證集法?？捎脭?shù)據(jù)分成兩個樣例集合：訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè)驗證集合，評估這個假設(shè)在后續(xù)數(shù)據(jù)上的精度方法的動機：即使學(xué)習(xí)器可能會被訓(xùn)練集合

18、誤導(dǎo)，但驗證集合不大可能表現(xiàn)出同樣的隨機波動驗證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計意義的實例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗證集合。2003.11.18整理ppt36錯誤率降低修剪將樹上的每一個節(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.

19、11.18整理ppt37規(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.18整理ppt38規(guī)則后修剪（2）例子if (outlook=sunny)(Humidity=High) then PlayTennis=No考慮刪除先行詞(outlook=sunny)和(Humidity=High)選擇使估計精度有最大提升的步驟考慮修剪第

20、二個前件2003.11.18整理ppt39規(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ù)集合的減小，離觀察精度越來越遠(yuǎn)不是統(tǒng)計有效，但是實踐中發(fā)現(xiàn)有效2003.11.18整理ppt40規(guī)則后修剪（4）把決策樹轉(zhuǎn)化成規(guī)則集的好處可以區(qū)分決策節(jié)點使用的不同上下文消除了根節(jié)點附近的屬性測試和葉節(jié)點附近的屬性測試

21、的區(qū)別提高了可讀性2003.11.18整理ppt41合并連續(xù)值屬性ID3被限制為取離散值的屬性學(xué)習(xí)到的決策樹要預(yù)測的目標(biāo)屬性必須是離散的樹的決策節(jié)點的屬性也必須是離散的簡單刪除上面第2個限制的方法通過動態(tài)地定義新的離散值屬性來實現(xiàn)，即先把連續(xù)值屬性的值域分割為離散的區(qū)間集合2003.11.18整理ppt42合并連續(xù)值屬性（2）例子，Temperature應(yīng)該定義什么樣的基于閾值的布爾屬性選擇產(chǎn)生最大信息增益的閾值按照連續(xù)屬性排列樣例，確定目標(biāo)分類不同的相鄰實例產(chǎn)生一組候選閾值，它們的值是相應(yīng)的A值之間的中間值可以證明產(chǎn)生最大信息增益的c值位于這樣的邊界中（Fayyad1991）通過計算與每個候

22、選閾值關(guān)聯(lián)的信息增益評估這些候選值方法的擴展連續(xù)的屬性分割成多個區(qū)間，而不是單一閾值的兩個空間2003.11.18整理ppt43小結(jié)和補充讀物決策樹學(xué)習(xí)為概念學(xué)習(xí)和學(xué)習(xí)其他離散值的函數(shù)提供了一個實用的方法ID3算法貪婪算法從根向下推斷決策樹搜索完整的假設(shè)空間歸納偏置，較小的樹過度擬合問題ID3算法的擴展2003.11.18整理ppt44附錄C4.5 is a software extension of the basic ID3 algorithm designed by Quinlan to address the following issues not dealt with by ID3

23、: Avoiding overfitting the data Determining how deeply to grow a decision tree. Reduced error pruning. Rule post-pruning. Handling continuous attributes. e.g., temperature Choosing an appropriate attribute selection measure. Handling training data with missing attribute values. Handling attributes w

24、ith differing costs. Improving computational efficiency. 整理ppt分類器評價標(biāo)準(zhǔn)預(yù)測準(zhǔn)確度計算復(fù)雜度模型描述的簡潔度：產(chǎn)生式規(guī)則整理ppt準(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é)。整理ppt召回率r(Recall)和精準(zhǔn)率p(Precision)為了定義這兩個指標(biāo)，引入分類中常用的兩個基本概念，Relevant和Retrieved。Relevant：真正屬于某類的集合Retrieved：判斷屬于某類的集合召回率反映了分類器正確分類的對