12決策樹學(xué)習(xí)和ASMS3000決策分析平臺

第1.2節(jié)決策樹學(xué)習(xí)(DecisionTree)內(nèi)容決策樹方法的原理決策樹中的過擬合問題決策樹的其他問題屬性的其他度量決策樹學(xué)習(xí)——決定是否打網(wǎng)球看看天氣看看濕度陽光明媚下雨看看風(fēng)速高正常不去打球去打球大小不去打球去打球節(jié)點(diǎn)：每一個節(jié)點(diǎn)測試一個屬性,分支：屬性的可選數(shù)值,葉子節(jié)點(diǎn)：最終預(yù)測去打球陰天決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)node=root循環(huán){ 1.為當(dāng)下一個節(jié)點(diǎn)選擇一個最好的屬性x2.將屬性x分配給節(jié)點(diǎn)node

3.對于x的所有可能數(shù)值，創(chuàng)建一個降序排列的節(jié)點(diǎn)node

4.將所有訓(xùn)練樣本在葉子節(jié)點(diǎn)排序分類

5.如果分類結(jié)果達(dá)到了錯誤率要求，跳出循環(huán)，否則，在葉子節(jié)點(diǎn)開始新循環(huán)-〉遞歸}決策樹表示法決策樹通過把實例從根節(jié)點(diǎn)排列到某個葉子節(jié)點(diǎn)來分類實例。葉子節(jié)點(diǎn)即為實例所屬的分類樹上每個節(jié)點(diǎn)說明了對實例的某個屬性的測試節(jié)點(diǎn)的每個后繼分支對應(yīng)于該屬性的一個可能值決策樹代表實例屬性值約束的合取的析取式。從樹葉到樹根的每一條路徑對應(yīng)一組屬性測試的合取，樹本身對應(yīng)這些合取的析取。決策樹學(xué)習(xí)的適用問題適用問題的特征實例由“屬性-值”對表示目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實例問題舉例根據(jù)天氣好壞確定是否去打球根據(jù)疾病分類患者根據(jù)起因分類設(shè)備故障根據(jù)拖欠支付的可能性分類貸款申請分類問題核心任務(wù)是把樣例分類到各可能的離散值對應(yīng)的類別基本的決策樹學(xué)習(xí)算法大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹空間ID3是這種算法的代表基本的決策樹學(xué)習(xí)算法ID3的思想自頂向下構(gòu)造決策樹從“哪一個屬性將在樹的根節(jié)點(diǎn)被測試”開始使用統(tǒng)計測試來確定每一個實例屬性單獨(dú)分類訓(xùn)練樣例的能力ID3的過程分類能力最好的屬性被選作樹的根節(jié)點(diǎn)根節(jié)點(diǎn)的每個可能值產(chǎn)生一個分支訓(xùn)練樣例排列到適當(dāng)?shù)姆种е貜?fù)上面的過程決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)編號天氣溫度濕度風(fēng)是否去打球1晴天炎熱高弱不去2晴天炎熱高強(qiáng)不去3陰天炎熱高弱去4下雨適中高弱去5下雨寒冷正常弱去6下雨寒冷正常強(qiáng)不去7陰天寒冷正常強(qiáng)去8晴天適中高弱不去9晴天寒冷正常弱去10下雨適中正常弱去11晴天適中正常強(qiáng)去12陰天適中高強(qiáng)去13陰天炎熱正常弱去14下雨適中高強(qiáng)不去表-1：是否去打球的數(shù)據(jù)統(tǒng)計—訓(xùn)練數(shù)據(jù)決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)濕度高正常(3+,4-)(6+,1-)S:(9+,5-)風(fēng)

弱強(qiáng)(6+,2-)(3+,3-)S:(9+,5-)問題：哪一個屬性（特征）更好？決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)熵:物理學(xué)概念宏觀上：熱力學(xué)定律—體系的熵變等于可逆過程吸收或耗散的熱量除以它的絕對溫度（克勞修斯，1865）微觀上：熵是大量微觀粒子的位置和速度的分布概率的函數(shù)，是描述系統(tǒng)中大量微觀粒子的無序性的宏觀參數(shù)（波爾茲曼，1872）結(jié)論：熵是描述事物無序性的參數(shù)，熵越大則無序性越強(qiáng),在信息領(lǐng)域定義為“熵越大，不確定性越大”（香濃，1948年）決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)隨機(jī)變量的熵熵比較多的用于信源編碼，數(shù)據(jù)壓縮，假設(shè)是最有效的編碼方式是使用位編碼于是對于隨即變量的最有效編碼位之和：決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)表示訓(xùn)練集合中的樣本表示訓(xùn)練集合中反例樣本的比例表示訓(xùn)練集合中正例樣本的比例表示訓(xùn)練集合的熵決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)信息增益：informationgain信息的增加意味著不確定性的減少，也就是熵的減小，信息增益在諸多系統(tǒng)中定義為：在某一個操作之前的系統(tǒng)熵與操作之后的系統(tǒng)熵的差值，也即是不確定性的減小量信息增益(InformationGain)原來的不確定性知道x之后的不確定性信息增益:原來-知道x之后的原來不確定性-經(jīng)過屬性x劃分以后的不確定性信息增益(InformationGain)選擇屬性的標(biāo)準(zhǔn)：選擇具有最高信息增益(InformationGain)的屬性假設(shè)有兩個類,+

和

-假設(shè)集合S中含有p個類別為+的樣本,n個類別為-的樣本將S中已知樣本進(jìn)行分類所需要的期望信息定義為:信息增益在決策樹中的使用假設(shè)屬性x將把集合S劃分成K份{S1,S2,…,SK}如果Si

中包含pi

個類別為“+”的樣本,

ni

個類別為“-”,的樣本。那么熵就是(entropy),在x上進(jìn)行決策分枝所獲得的信息增益為:決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)*決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)問題：哪一個屬性（特征）更好？分析極端的情況溫度高正常(4+,4-)(4+,4-)S:(8+,8-)心情

好壞(8+,0-)(0+,8-)S:(8+,8-)E=1.0E=0.0E=0.0Gain(S,溫度）=1.0-（8/16)*1.0-（8/16）*1.0=0.0Gain(S,心情）=1.0-(8/16)*0.0-(8/16)*0.0=1.0E=1.0E=1.0決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)濕度高正常(3+,4-)(6+,1-)S:(9+,5-)風(fēng)

弱強(qiáng)(6+,2-)(3+,3-)S:(9+,5-)問題：哪一個屬性（特征）更好？I=0.985I=0.592I=0.811I=1.00Gain(S,濕度）=0.940-（7/14).985-7/14*0.592=0.151Gain(S,風(fēng)）=0.940-(8/14).811-(6/14)1.0=0.048E=0.940E=0.940決策樹學(xué)習(xí)原理簡介—(ID3,C4.5算法)決策樹的構(gòu)造過程示意x1x3x8x3x7+-+-+-決策樹學(xué)習(xí)將樹轉(zhuǎn)化為規(guī)則將樹轉(zhuǎn)化為規(guī)則集合測試規(guī)則是否相互矛盾將規(guī)則排序存儲Tree:If(陰天）-〉去打球If（晴天）If（風(fēng)速低）-〉去打球Else-〉不去打球決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際問題確定決策樹增長的深度處理連續(xù)值的屬性選擇一個適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價的屬性提高計算效率針對這些問題，ID3被擴(kuò)展成C4.5決策樹學(xué)習(xí)及over-fitting看看天氣看看濕度陽光明媚下雨看看風(fēng)速高正常不去打球去打球大小不去打球去打球去打球陰天1晴天炎熱高強(qiáng)去打球增加一個錯誤樣本決策樹學(xué)習(xí)及over-fitting過度擬合對于一個假設(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ù)。決策樹學(xué)習(xí)及over-fitting導(dǎo)致過度擬合的原因一種可能原因是訓(xùn)練樣例含有隨機(jī)錯誤或噪聲當(dāng)訓(xùn)練數(shù)據(jù)沒有噪聲時，過度擬合也有可能發(fā)生，特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點(diǎn)時，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實際的目標(biāo)函數(shù)并無關(guān)系。決策樹學(xué)習(xí)及over-fitting假設(shè)在訓(xùn)練樣本集合上的錯誤率為樣本集合上的真實錯誤率為訓(xùn)練結(jié)果在如下情況下即會產(chǎn)生過擬合決策樹學(xué)習(xí)及over-fitting決策樹學(xué)習(xí)及over-fitting避免過擬合的方法如果對數(shù)據(jù)劃分沒有明顯好處的屬性不選擇，同時不再將決策數(shù)細(xì)分構(gòu)建完成整個樹以后進(jìn)行剪枝”Prune”在訓(xùn)練數(shù)據(jù)上測量性能在交叉驗證數(shù)據(jù)上測量性能MDLMinmize(Size(tree)+Size(misclassifications(tree))

決策樹學(xué)習(xí)及over-fitting避免過擬合的方法評估所生成的新節(jié)點(diǎn)對于Validation數(shù)據(jù)集合的性能生成一些節(jié)點(diǎn)很少但是性能很好的“Sub-tree”決策樹學(xué)習(xí)及over-fitting避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點(diǎn)第一種方法更直觀第一種方法中，精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功決策樹學(xué)習(xí)及over-fitting避免過度擬合的關(guān)鍵使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模解決方法使用與訓(xùn)練樣例截然不同的一套分離的樣例，來評估通過后修剪方法從樹上修建節(jié)點(diǎn)的效用。使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計測試來估計擴(kuò)展（或修剪）一個特定的節(jié)點(diǎn)是否有可能改善在訓(xùn)練集合外的實例上的性能。使用一個明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，當(dāng)這個編碼的長度最小時停止樹增長。決策樹學(xué)習(xí)及over-fitting方法評述第一種方法是最普通的，常被稱為訓(xùn)練和驗證集法?？捎脭?shù)據(jù)分成兩個樣例集合：訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè)驗證集合，評估這個假設(shè)在后續(xù)數(shù)據(jù)上的精度方法的動機(jī)：即使學(xué)習(xí)器可能會被訓(xùn)練集合誤導(dǎo)，但驗證集合不大可能表現(xiàn)出同樣的隨機(jī)波動驗證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計意義的實例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗證集合。訓(xùn)練誤差升高修剪將樹上的每一個節(jié)點(diǎn)作為修剪候選對象修剪步驟刪除以此節(jié)點(diǎn)為根的子樹，使它成為葉結(jié)點(diǎn)把和該節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例的最常見分類賦給它反復(fù)修剪節(jié)點(diǎn)，每次總是選取那些刪除后可以最大提高決策樹在驗證集合上的精度的節(jié)點(diǎn)繼續(xù)修剪，直到進(jìn)一步的修剪是有害的為止數(shù)據(jù)分成3個子集訓(xùn)練樣例，形成決策樹驗證樣例，修剪決策樹測試樣例，精度的無偏估計如果有大量的數(shù)據(jù)可供使用，那么使用分離的數(shù)據(jù)集合來引導(dǎo)修剪規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好地擬合訓(xùn)練數(shù)據(jù)，允許過度擬合發(fā)生將決策樹轉(zhuǎn)化為等價的規(guī)則集合，方法是為從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑創(chuàng)建一條規(guī)則通過“任何能導(dǎo)致估計精度提高的前提”來修剪每一條規(guī)則按照修剪過的規(guī)則的估計精度對它們進(jìn)行排序，并按這樣的順序應(yīng)用這些規(guī)則來分類后來的實例規(guī)則后修剪規(guī)則精度估計方法使用與訓(xùn)練集不相交的驗證集基于訓(xùn)練集合本身被C4.5使用，使用一種保守估計來彌補(bǔ)訓(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)有效規(guī)則后修剪把決策樹轉(zhuǎn)化成規(guī)則集的好處可以區(qū)分決策節(jié)點(diǎn)使用的不同上下文消除了根節(jié)點(diǎn)附近的屬性測試和葉節(jié)點(diǎn)附近的屬性測試的區(qū)別提高了可讀性合并連續(xù)值屬性ID3被限制為取離散值的屬性學(xué)習(xí)到的決策樹要預(yù)測的目標(biāo)屬性必須是離散的樹的決策節(jié)點(diǎn)的屬性也必須是離散的簡單刪除上面第2個限制的方法通過動態(tài)地定義新的離散值屬性來實現(xiàn)，即先把連續(xù)值屬性的值域分割為離散的區(qū)間集合合并連續(xù)值屬性例，Temperature應(yīng)該定義什么樣的基于閾值的布爾屬性選擇產(chǎn)生最大信息增益的閾值按照連續(xù)屬性排列樣例，確定目標(biāo)分類不同的相鄰實例產(chǎn)生一組候選閾值，它們的值是相應(yīng)的A值之間的中間值可以證明產(chǎn)生最大信息增益的c值位于這樣的邊界中（Fayyad1991）通過計算與每個候選閾值關(guān)聯(lián)的信息增益評估這些候選值方法的擴(kuò)展連續(xù)的屬性分割成多個區(qū)間，而不是單一閾值的兩個空間屬性選擇的其他度量標(biāo)準(zhǔn)信息增益度量存在一個內(nèi)在偏置，偏向具有較多值的屬性避免方法，其他度量，比如增益比率增益比率通過加入一個被稱作分裂信息的項來懲罰多值屬性，分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻性

SplitInformation(S,A)= GainRatio(S,A)=分裂信息項阻礙選擇值為均勻分布的屬性問題，當(dāng)某個SiS。解決方法：采用一些啟發(fā)式規(guī)則，比如僅對增益高過平均值的屬性應(yīng)用增益比率測試決策樹學(xué)習(xí)中的假設(shè)空間搜索—屬性分段觀察ID3的搜索空間和搜索策略，認(rèn)識到這個算法的優(yōu)勢假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個完整空間維護(hù)單一的當(dāng)前假設(shè),不進(jìn)行回溯，能收斂到局部最優(yōu)每一步使用所有的訓(xùn)練樣例，不同于基于單獨(dú)的訓(xùn)練樣例遞增作出決定，容錯性增強(qiáng)決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略優(yōu)先選擇較短的樹選擇那些信息增益高的屬性離根節(jié)點(diǎn)較近的樹很難準(zhǔn)確刻畫ID3的歸納偏置近似的ID3的歸納偏置較短的樹比較長的樹優(yōu)先近似在于ID3得到局部最優(yōu)，而不一定是全局最優(yōu)一個精確具有這個歸納偏置的算法，BFS-ID3更貼切近似的歸納偏置較短的樹比較長的樹優(yōu)先，信息增益高的屬性更靠近根節(jié)點(diǎn)的樹優(yōu)先為什么短的假設(shè)優(yōu)先ID3的歸納偏置的直觀基礎(chǔ)奧坎姆剃刀優(yōu)先選擇擬合數(shù)據(jù)的最簡單的假設(shè)科學(xué)上的例子物理學(xué)家優(yōu)先選擇行星運(yùn)動的簡單假設(shè)簡單假設(shè)的數(shù)量遠(yuǎn)比復(fù)雜假設(shè)的數(shù)量少簡單假設(shè)對訓(xùn)練樣例的針對性更小，更像是泛化的規(guī)律，而不是訓(xùn)練樣例的另一種描述屬性選擇的其他度量標(biāo)準(zhǔn)基于距離的度量定義了數(shù)據(jù)劃分間的一種距離尺度計算每個屬性產(chǎn)生的劃分與理想劃分間的距離LopezdeMantaras定義了這個距離度量，證明了它不偏向有大量值的屬性Mingers實驗，不同的屬性選擇度量對最終精度的影響小于后修剪的程度和方法的影響缺少屬性值的訓(xùn)練樣例例子，醫(yī)學(xué)領(lǐng)域，很多待測屬性無法觀測經(jīng)常需要根據(jù)此屬性值已知實例來估計這個缺少的屬性值一種策略，給它節(jié)點(diǎn)n的訓(xùn)練樣例中該屬性的最常見值另一種策略是賦給它節(jié)點(diǎn)n的被分類為c(x)的訓(xùn)練樣例中該屬性的最常見值更復(fù)雜的策略，為x的每個可能值賦予一個概率，而不是簡單地將最常見的值賦給x，決策樹與概率結(jié)合處理不同代價的屬性實例的屬性可能與代價相關(guān)優(yōu)先選擇盡可能使用低代價屬性的決策樹，僅當(dāng)需要產(chǎn)生可靠的分類時才依賴高代價屬性通過引入一個代價項到屬性選擇度量中，可以使ID3算法考慮屬性代價加權(quán)的方法小結(jié)決策樹學(xué)習(xí)為離散值輸入提供了一個實用的方法ID3算法從根向下推斷決策樹搜索完整的假設(shè)空間較小的樹C4.5算法過度擬合問題決策樹的其他問題本章作業(yè)本章作業(yè)：寫出“利用決策樹建立轉(zhuǎn)基因植物生物安全評價的讀書報告”格式為PPT或者Word，素材見課程網(wǎng)站ASMS3000決策分析平臺

1、決策分析平臺的重要性2、訂票、出票、送票統(tǒng)計3、銷售數(shù)據(jù)分析、坐席工作效率分析與航線銷售對比分析的查看與統(tǒng)計4、盈利分析5、員工業(yè)績統(tǒng)計分析6、問題考核?1.1決策分析平臺的重要性全方位的統(tǒng)計公司銷售上的各類數(shù)據(jù)，有利于代理人的領(lǐng)導(dǎo)層掌握公司運(yùn)轉(zhuǎn)狀態(tài)，針對現(xiàn)有的情況作出進(jìn)一步的決策。

準(zhǔn)確把握員工的工作效率利用決策分析平臺的各類員工工作效率的分析，制定有效地獎懲措施，解決工作效率存在的問題。盈利分析

管理層通過具體的盈利數(shù)據(jù)，查看公司的一段時間內(nèi)各個階段的盈利數(shù)據(jù)，通過對比分析原因，制訂下階段的策略。?2.1訂票、出