決策樹模型概述

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

認識理解

信息量的定義若一個消息x出現的概率為p，則這一消息所含的信息量為其中，對數的底大于1信息量單位以2為底時，單位為bit（binaryunit，比特）以e為底時，單位為nat（naturalunit，奈特）以10為底時，單位為hart（Hartley，哈特）第五頁，共五十三頁。拋一枚均勻硬幣，出現正面與反面的信息量是多少？解：出現正面與反面的概率均為0.5，它們的信息量是I(正)=-lbp(正)=-lb0.5=1bI(反)=-lbp(反)=-lb0.5=1b第六頁，共五十三頁。拋一枚畸形硬幣，出現正面與反面的概率分別是1/4，3/4，出現正面與反面時的信息量是多少？解：出現正面與反面的概率分別是1/4，3/4，它們的信息量是I(正)=-lbp(正)=-lb1/4=2bI(反)=-lbp(反)=-lb3/4=0.415b第七頁，共五十三頁。信源含有的信息量是信源發(fā)出的所有可能消息的平均不確定性，香農把信源所含有的信息量稱為信息熵，是指每個符號所含信息量的統(tǒng)計平均值。m種符號的平均信息量為第八頁，共五十三頁。拋一枚均勻硬幣的信息熵是多少？解：出現正面與反面的概率均為0.5，信息熵是第九頁，共五十三頁。拋一枚畸形硬幣，出現正面與反面的概率分別是1/4，3/4，出現正面與反面時的信息量是多少？解：出現正面與反面的概率分別是1/4，3/4，信息熵是第十頁，共五十三頁。例：氣象預報第十一頁，共五十三頁。12條件自信息量在事件yj出現的條件下，隨機事件xi發(fā)生的條件概率為p(xi|yj)，則它的條件自信息量定義為條件概率對數的負值：第十二頁，共五十三頁。13條件熵在給定yj條件下，xi的條件自信息量為I(xi|yj),X集合的條件熵H(X|yj)為在給定Y(即各個yj

)條件下,X集合的條件熵H(X|Y)條件熵H(X|Y)表示已知Y后，X的不確定度第十三頁，共五十三頁。是否適合打壘球的決策表天氣溫度濕度風速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消第十四頁，共五十三頁?；顒犹鞖馐欠襁M行壘球活動進行取消晴陰雨晴陰雨活動進行取消第十五頁，共五十三頁。活動的熵活動有2個屬性值，進行，取消。其熵為：H(活動)=-(9/14)*log

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

(5/14)=0.94活動進行取消第十六頁，共五十三頁。已知戶外的天氣情況下活動的條件熵戶外有三個屬性值，晴，陰和雨。其熵分別為：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活動天氣進行取消晴陰雨第十七頁，共五十三頁。已知戶外時活動的條件熵H(活動|戶外)=5/14*H(活動|戶外=晴)+4/14*H(活動|戶外=陰)+5/14*H(活動|戶外=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693晴陰雨第十八頁，共五十三頁。平均互信息I(活動;戶外)=H(活動)-H(活動|戶外)=0.94-0.693=0.246第十九頁，共五十三頁。是否適合打壘球的決策表天氣溫度濕度風速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消第二十頁，共五十三頁。活動的熵H(活動)=-(9/14)*lb

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

(5/14)=0.94天氣

溫度

濕度

風速

活動

陰

炎熱

高

弱

進行

雨

適中

高

弱

進行

雨

寒冷

正常

弱

進行

陰

寒冷

正常

強

進行

晴

寒冷

正常

弱

進行

雨

適中

正常

弱

進行

晴

適中

正常

強

進行

陰

適中

高

強

進行

陰

炎熱

正常

弱

進行

晴

炎熱

高

弱

取消

晴

炎熱

高

強

取消

雨

寒冷

正常

強

取消

晴

適中

高

弱

取消

雨

適中

高

強

取消

第二十一頁，共五十三頁。已知天氣時活動的條件熵H(活動|天氣)=5/14*H(活動|天氣=晴)+4/14*H(活動|天氣=陰)+5/14*H(活動|天氣=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693溫度

濕度

風速

天氣

活動

寒冷

正常

弱

晴

進行

適中

正常

強

晴

進行

炎熱

高

弱

晴

取消

炎熱

高

強

晴

取消

適中

高

弱

晴

取消

炎熱

高

弱

陰

進行

寒冷

正常

強

陰

進行

適中

高

強

陰

進行

炎熱

正常

弱

陰

進行

適中

高

弱

雨

進行

寒冷

正常

弱

雨

進行

適中

正常

弱

雨

進行

寒冷

正常

強

雨

取消

適中

高

強

雨

取消

第二十二頁，共五十三頁。天氣

濕度

風速

溫度

活動

陰

高

弱

炎熱

進行

陰

正常

弱

炎熱

進行

晴

高

弱

炎熱

取消

晴

高

強

炎熱

取消

雨

高

弱

適中

進行

雨

正常

弱

適中

進行

晴

正常

強

適中

進行

陰

高

強

適中

進行

晴

高

弱

適中

取消

雨

高

強

適中

取消

雨

正常

弱

寒冷

進行

陰

正常

強

寒冷

進行

晴

正常

弱

寒冷

進行

雨

正常

強

寒冷

取消

已知溫度時活動的條件熵H(活動|溫度)=0.911第二十三頁，共五十三頁。天氣

溫度

風速

濕度

活動

陰

炎熱

弱

高

進行

雨

適中

弱

高

進行

陰

適中

強

高

進行

晴

炎熱

弱

高

取消

晴

炎熱

強

高

取消

晴

適中

弱

高

取消

雨

適中

強

高

取消

雨

寒冷

弱

正常

進行

陰

寒冷

強

正常

進行

晴

寒冷

弱

正常

進行

雨

適中

弱

正常

進行

晴

適中

強

正常

進行

陰

炎熱

弱

正常

進行

雨

寒冷

強

正常

取消

H(活動|濕度)

=0.789已知濕度時活動的條件熵第二十四頁，共五十三頁。天氣

溫度

濕度

風速

活動

陰

寒冷

正常

強

進行

晴

適中

正常

強

進行

陰

適中

高

強

進行

晴

炎熱

高

強

取消

雨

寒冷

正常

強

取消

雨

適中

高

強

取消

陰

炎熱

高

弱

進行

雨

適中

高

弱

進行

雨

寒冷

正常

弱

進行

晴

寒冷

正常

弱

進行

雨

適中

正常

弱

進行

陰

炎熱

正常

弱

進行

晴

炎熱

高

弱

取消

晴

適中

高

弱

取消

H(活動|風速)=0.892已知風速時活動的條件熵第二十五頁，共五十三頁。各互信息量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(活動;風速)=

H(活動)-H(活動|風速)=0.94-0.892=0.048第二十六頁，共五十三頁。天氣溫度濕度風速活動晴炎熱高弱取消晴炎熱高強取消陰炎熱高弱進行雨適中高弱進行雨寒冷正常弱進行雨寒冷正常強取消陰寒冷正常強進行晴適中高弱取消晴寒冷正常弱進行雨適中正常弱進行晴適中正常強進行陰適中高強進行陰炎熱正常弱進行雨適中高強取消溫度

濕度

風速

活動

寒冷

正常

弱

進行

適中

正常

強

進行

炎熱

高

弱

取消

炎熱

高

強

取消

適中

高

弱

取消

溫度

濕度

風速

活動

適中

高

弱

進行

寒冷

正常

弱

進行

適中

正常

弱

進行

寒冷

正常

強

取消

適中

高

強

取消

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

溫度

濕度

風速

活動

晴

寒冷

正常

弱

進行

晴

適中

正常

強

進行

晴

炎熱

高

弱

取消

晴

炎熱

高

強

取消

晴

適中

高

弱

取消

陰

炎熱

高

弱

進行

陰

寒冷

正常

強

進行

陰

適中

高

強

進行

陰

炎熱

正常

弱

進行

雨

適中

高

弱

進行

雨

寒冷

正常

弱

進行

雨

適中

正常

弱

進行

雨

寒冷

正常

強

取消

雨

適中

高

強

取消

第二十七頁，共五十三頁。ID3算法生成的決策樹第二十八頁，共五十三頁。ID3算法ID3(A:條件屬性集合，d:決策屬性，U:訓練集)返回一棵決策樹{ifU為空，返回一個值為Failure的單結點；//一般不會出現這種情況，為了程序的健壯性ifU是由其值均為相同決策屬性值的記錄組成，返回一個帶有該值的單結點；//此分支至此結束ifA為空，則返回一個單結點，其值為在U的記錄中找出的頻率最高的決策屬性值；//這時對記錄將出現誤分類將A中屬性之間具有最大I(d;a)的屬性賦給a；將屬性a的值賦給{aj|j=1,2,…,m}；將分別由對應于a的值的aj的記錄組成的U的子集賦值給{uj|j=1,2,…,m}；返回一棵樹，其根標記為a，樹枝標記為a1,a2,…,am；再分別構造以下樹：ID3(A-{a},d,u1)，ID3(A-{a},d,u2)，…，ID3(A-{a},d,um)；//遞歸算法}第二十九頁，共五十三頁。2003.11.1830決策樹學習的常見問題決策樹學習的實際問題確定決策樹增長的深度處理連續(xù)值的屬性選擇一個適當的屬性篩選度量標準處理屬性值不完整的訓練數據處理不同代價的屬性提高計算效率針對這些問題，ID3被擴展成C4.5第三十頁，共五十三頁。2003.11.1831避免過度擬合數據過度擬合對于一個假設，當存在其他的假設對訓練樣例的擬合比它差，但事實上在實例的整個分布上表現得卻更好時，我們說這個假設過度擬合訓練樣例定義：給定一個假設空間H，一個假設hH，如果存在其他的假設h’H，使得在訓練樣例上h的錯誤率比h’小，但在整個實例分布上h’的錯誤率比h小，那么就說假設h過度擬合訓練數據。第三十一頁，共五十三頁。2003.11.1832避免過度擬合數據（2）導致過度擬合的原因一種可能原因是訓練樣例含有隨機錯誤或噪聲當訓練數據沒有噪聲時，過度擬合也有可能發(fā)生，特別是當少量的樣例被關聯到葉子節(jié)點時，很可能出現巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實際的目標函數并無關系。第三十二頁，共五十三頁。33避免過度擬合數據（3）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點第一種方法更直觀第一種方法中，精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功第三十三頁，共五十三頁。2003.11.1834避免過度擬合數據（4）避免過度擬合的關鍵使用什么樣的準則來確定最終正確樹的規(guī)模解決方法使用與訓練樣例截然不同的一套分離的樣例，來評估通過后修剪方法從樹上修建節(jié)點的效用。使用所有可用數據進行訓練，但進行統(tǒng)計測試來估計擴展（或修剪）一個特定的節(jié)點是否有可能改善在訓練集合外的實例上的性能。使用一個明確的標準來衡量訓練樣例和決策樹的復雜度，當這個編碼的長度最小時停止樹增長。第三十四頁，共五十三頁。2003.11.1835避免過度擬合數據（5）方法評述第一種方法是最普通的，常被稱為訓練和驗證集法?？捎脭祿殖蓛蓚€樣例集合：訓練集合，形成學習到的假設驗證集合，評估這個假設在后續(xù)數據上的精度方法的動機：即使學習器可能會被訓練集合誤導，但驗證集合不大可能表現出同樣的隨機波動驗證集合應該足夠大，以便它本身可提供具有統(tǒng)計意義的實例樣本。常見的做法是，樣例的三分之二作訓練集合，三分之一作驗證集合。第三十五頁，共五十三頁。2003.11.1836錯誤率降低修剪將樹上的每一個節(jié)點作為修剪得候選對象修剪步驟刪除以此節(jié)點為根的子樹，使它成為葉結點把和該節(jié)點關聯的訓練樣例的最常見分類賦給它反復修剪節(jié)點，每次總是選取那些刪除后可以最大提高決策樹在驗證集合上的精度的節(jié)點繼續(xù)修剪，直到進一步的修剪是有害的為止數據分成3個子集訓練樣例，形成決策樹驗證樣例，修剪決策樹測試樣例，精度的無偏估計如果有大量的數據可供使用，那么使用分離的數據集合來引導修剪第三十六頁，共五十三頁。2003.11.1837規(guī)則后修剪從訓練集合推導出決策樹，增長決策樹直到盡可能好地擬合訓練數據，允許過度擬合發(fā)生將決策樹轉化為等價的規(guī)則集合，方法是為從根節(jié)點到葉節(jié)點的每一條路徑創(chuàng)建一條規(guī)則通過刪除任何能導致估計精度提高的前件來修剪每一條規(guī)則按照修剪過的規(guī)則的估計精度對它們進行排序，并按這樣的順序應用這些規(guī)則來分類后來的實例第三十七頁，共五十三頁。2003.11.1838規(guī)則后修剪（2）例子if(outlook=sunny)(Humidity=High)thenPlayTennis=No考慮刪除先行詞(outlook=sunny)和(Humidity=High)選擇使估計精度有最大提升的步驟考慮修剪第二個前件第三十八頁，共五十三頁。2003.11.1839規(guī)則后修剪（3）規(guī)則精度估計方法使用與訓練集不相交的驗證集基于訓練集合本身被C4.5使用，使用一種保守估計來彌補訓練數據有利于當前規(guī)則的估計偏置過程先計算規(guī)則在它應用的訓練樣例上的精度然后假定此估計精度為二項式分布，并計算它的標準差對于一個給定的置信區(qū)間，采用下界估計作為規(guī)則性能的度量評論對于大的數據集，保守預測非常接近觀察精度，隨著數據集合的減小，離觀察精度越來越遠不是統(tǒng)計有效，但是實踐中發(fā)現有效第三十九頁，共五十三頁。2003.11.1840規(guī)則后修剪（4）把決策樹轉化成規(guī)則集的好處可以區(qū)分決策節(jié)點使用的不同上下文消除了根節(jié)點附近的屬性測試和葉節(jié)點附近的屬性測試的區(qū)別提高了可讀性第四十頁，共五十三頁。2003.11.1841合并連續(xù)值屬性ID3被限制為取離散值的屬性學習到的決策樹要預測的目標屬性必須是離散的樹的決策節(jié)點的屬性也必須是離散的簡單刪除上面第2個限制的方法通過動態(tài)地定義新的離散值屬性來實現，即先把連續(xù)值屬性的值域分割為離散的區(qū)間集合第四十一頁，共五十三頁。2003.11.1842合并連續(xù)值屬性（2）例子，Temperature應該定義什么樣的基于閾值的布爾屬性選擇產生最大信息增益的閾值按照連續(xù)屬性排列樣例，確定目標分類不同的相鄰實例產生一組候選閾值，它們的值是相應的A值之間的中間值可以證明產生最大信息增益的c值位于這樣的邊界中（Fayyad1991）通過計算與每個候選閾值關聯的信息增益評估這些候選值方法的擴展連續(xù)的屬性分割成多個區(qū)間，而不是單一閾值的兩個空間第四十二頁，共五十三頁。2003.11.1843小結和補充讀物決策樹學習為概念學習和學習其他離散值的函數提供了一個實用的方法ID3算法貪婪算法從根向下推斷決策樹搜索完整的假設空間歸納偏置，較小的樹過度擬合問題ID3算法的擴展第四十三頁，共五十三頁。2003.11.1844附錄C4.5isasoftwareextensionofthebasicID3algorithmdesignedbyQuinlantoaddressthefollowingissuesnotdealtwithbyID3:AvoidingoverfittingthedataDetermininghowdeeplytogrowadecisiontree.Reducederrorpruning.Rulepost-pruning.Handlingcontinuousattributes.e.g.,temperatureChoosinganappropriateattributeselectionmeasure.Handlingtrainingdatawithmissingattributevalues.Handlingattributeswithdifferingcosts.Improvingcomputationalefficiency.第四十四頁，共五十三頁。分類器評價標準預測準確度計算復雜度模型描述的簡潔度：產生式規(guī)則第四十五頁，共五十三頁。準確度分析一般采用召回率r(Recall)和精準率p(Precision)這兩個指標衡量分類器的準確度?！獋€好的分類器應同時具有較高的召回率和精準率，當然這兩個指標一般情況下是互斥的，有時要根據需要在這兩個指標間作某種權衡和妥協(xié)。第四十六頁，共五十三頁。召回率r(Recall)和精準率p(Precision)為了定義這兩個指標，引入分類中常用的兩個基本概念，Relevant和Retrieved。Relevant：真正屬于某類的集合Retrieved：判斷屬于某類的集合召回率反映了分類器正確分類的對象在真正歸入該類的對象中所占的比率，而精準率反映了分類器正確分類的對象在系統(tǒng)歸入該類的對象中所占的比率。Relev