【正文】 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 青 中 否 良 不買 64 青 低 是 良 買 64 青 中 是 優(yōu) 買 如果選擇收入作為節(jié)點(diǎn) 分高、中、低 平均信息期望（加權(quán)總和）： E(收入） = * 0 + * + * 0 = Gain(收入 ) = I(128, 256) E(收入 )= – = I(0,128)=0 比例 : 128/384= I(64,128)= 比例 : 192/384= I(64,0)=0 比例 : 64/384= 注意 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 年齡 青年 中年 老年 學(xué)生 買 信譽(yù) 葉子 否 是 優(yōu) 良 買 不買 買 / 不買 買 葉子 葉子 葉子 決策樹算法 第 6章 決策樹 ID3 決策樹建立算法 1 決定分類屬性； 2 對(duì)目前的數(shù)據(jù)表，建立一個(gè)節(jié)點(diǎn) N 3 如果數(shù)據(jù)庫中的數(shù)據(jù)都屬于同一個(gè)類， N就是樹葉，在樹葉上 標(biāo)出所屬的類 4 如果數(shù)據(jù)表中沒有其他屬性可以考慮，則 N也是樹葉，按照少 數(shù)服從多數(shù)的原則在樹葉上標(biāo)出所屬類別 5 否則，根據(jù)平均信息期望值 E或 GAIN值選出一個(gè)最佳屬性作 為節(jié)點(diǎn) N的測試屬性 6 節(jié)點(diǎn)屬性選定后，對(duì)于該屬性中的每個(gè)值： 從 N生成一個(gè)分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形 成分支節(jié)點(diǎn)的數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄 如果分支數(shù)據(jù)表非空，則運(yùn)用以上算法從該節(jié)點(diǎn)建立子樹。 顯然，上可以作為數(shù)據(jù)純凈度或混亂度的衡量指標(biāo)。 假設(shè)有 n個(gè)互不相容的事件 a1,a2,a3,….,an, 它們中有且僅有一個(gè) 發(fā)生，則其平均的信息量可如下度量： ??????ni iiniin apapaIaaaI12121 )(1log)()(),... ,( )(1log)()(2iii apapaI ?第 6章 決策樹 ID3 –信息量大小的度量 決策樹算法 ??????ni iiniin apapaIaaaI12121 )(1log)()(),... ,(上式，對(duì)數(shù)底數(shù)可以為任何數(shù)，不同的取值對(duì)應(yīng)了熵的不同單位。 (b)顯然要比 (a)好。是決策樹學(xué)習(xí)方法中最 具影響和最為典型的算法。否則 3 根據(jù) 某種策略 從訓(xùn)練樣本屬性表中選擇屬性 A 作為測試屬性 , 生成測試結(jié)點(diǎn) A 4 若 A的取值為 v1,v2,…,vm, 則根據(jù) A 的取值的 不同 ,將 T 劃分成 m個(gè)子集 T1,T2,…,Tm。對(duì)每個(gè)結(jié)點(diǎn)上問題的不同測試輸出導(dǎo)致不同的分枝，最后 會(huì)達(dá)到一個(gè)葉子結(jié)點(diǎn)。 1993年， Quinlan 進(jìn)一步發(fā)展了 ID3算法，改進(jìn)成 。由于對(duì) c僅有的信息只是它在訓(xùn)練樣例上 的值，因此歸納學(xué)習(xí)最多只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬 合。 第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 3） 分類模型的性能根據(jù)模型正確和錯(cuò)誤預(yù)測也可以根據(jù)的檢驗(yàn)記錄計(jì)數(shù) 進(jìn)行評(píng)估。通過 調(diào)整假設(shè)的表示，學(xué)習(xí)過程將產(chǎn)生出假設(shè)的不同變形。直 到最終的一般化描述。這種一般性 描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來預(yù)測新的數(shù)據(jù)。 第 6章 決策樹 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (1) 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。 優(yōu)點(diǎn)在于對(duì)數(shù)據(jù)前幾輪中的預(yù)測標(biāo)識(shí)可以通過后驗(yàn)概率 來改變。這 點(diǎn)對(duì)于較為復(fù)雜的分類尤其重要。 無指導(dǎo)的學(xué)習(xí)（ unsupervised learning 一般用于聚類） 每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集合和數(shù)量 也可能是事先未知的。 分類技術(shù)一般是用一種學(xué)習(xí)算法確定分類模型，該模型可以很好 地?cái)M合輸入數(shù)據(jù)中類標(biāo)號(hào)和屬性集之間的聯(lián)系。學(xué)習(xí)算法得到的 模型不僅要很好擬合輸入數(shù)據(jù)，還要能夠正確地預(yù)測未知樣本的 類標(biāo)號(hào)。 通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號(hào)或進(jìn)行聚類 第 6章 決策樹 決策樹基本概念 半監(jiān)督學(xué)習(xí)（ semisupervised learning ） 傳統(tǒng)的機(jī)器學(xué)習(xí)技術(shù)需要使用大量有標(biāo)記訓(xùn)練樣本進(jìn)行學(xué) 習(xí)，但是在很多真實(shí)應(yīng)用中，獲取大量有標(biāo)記訓(xùn)練樣本相當(dāng)困 難，但是很容易獲得大量未標(biāo)記訓(xùn)練樣本。 自訓(xùn)練方法及特點(diǎn) 第 6章 決策樹 半監(jiān)督學(xué)習(xí)（ semisupervised learning ） 協(xié)同訓(xùn)練方法及特點(diǎn) 協(xié)同訓(xùn)練是一種利用互補(bǔ)的分類器對(duì)未標(biāo)識(shí)樣本特征空間 進(jìn)行探索的半監(jiān)督學(xué)習(xí)方法。這樣在初始分類器準(zhǔn)確率不高的情況下優(yōu)于協(xié)同訓(xùn) 練。 歸納是從特殊到一般的過程。 銳角三角形內(nèi)角和等于 180度； 鈍角三角形內(nèi)角和等于 180度； 三角形內(nèi)角和 直角三角形內(nèi)角和等于 180度； 等于 180度 已知三角形 ABC， A角等于 76度， B角等于 89度，則其 C角等于 15度 歸納學(xué)習(xí)由于依賴于檢驗(yàn)數(shù)據(jù)，因此又稱為檢驗(yàn)學(xué)習(xí)。 自頂向下法對(duì)可能的一般性描述集進(jìn)行搜索，試圖找到一些 滿足一定要求的最優(yōu)的描述。在表示中 通常需要修改參數(shù)（如 a, b）。這些計(jì)數(shù)存儲(chǔ)在混淆矩陣（ Confusion Matrix）的表格中，二元 分類問題混淆矩陣如下： 實(shí)際 的類 類 1 f11 類 0 f01 f10 f00 類 1 類 0 預(yù)測的類 準(zhǔn)確率 =正確的預(yù)測數(shù) /預(yù)測總數(shù) =（ f11+f00） /(f11+f01+f10+f00) 差錯(cuò)率 =錯(cuò)誤的預(yù)測數(shù) /預(yù)測總數(shù) =（ f10+f01） /(f11+f01+f10+f00) 第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 4） 混淆矩陣一般可以用于衡量分類器的精度。若沒有更多的信息，只能假定對(duì)于未見實(shí)例最好的假設(shè)就是 訓(xùn)練數(shù)據(jù)最佳擬合的假設(shè)。 另一類決策樹算法為 CART，與 ， CART的決策樹由二元邏輯問題生成，每個(gè)樹節(jié)點(diǎn)只有兩個(gè)分枝，分別包括學(xué)習(xí)實(shí)例的正例與反例。這一過程就是利用決策樹進(jìn)行分類的過程， 利用若干個(gè)變量來判斷屬性的類別 第 6章 決策樹 決策樹算法 CLS（ Concept Learning System）算法 CLS算法是早期的決策樹學(xué)習(xí)算法。 5 從訓(xùn)練樣本屬性表中刪除屬性 A。 該方法使用信息增益度選擇測試屬性。 因?yàn)閺姆诸愵A(yù)測的觀點(diǎn)來看， (b)比 (a)犯錯(cuò)誤的可能性要小。 通常取 2，并規(guī)定當(dāng) p(ai)=0時(shí) =0 )(1log)()(2iii apapaI ?公式 1 第 6章 決策樹 決策樹算法 例：假設(shè)有一個(gè)數(shù)據(jù)集合 D，其中只有兩個(gè)類，一個(gè)是正例類，一個(gè)是負(fù)例類 計(jì)算 D中正例類和負(fù)例類在三種不同的組分下熵的變化情況。這正是決策樹學(xué)習(xí)中 需要的。 決策樹算法 第 6章 決策樹 決策樹算法 ID Age Hasjob Own_house Credit_rating Class 1 Young False False Fair No 2 Young False False Good No 3 Young True False Good Yes 4 Young True True Fair Yes 5 Young False False Fair No 6 Middle False False Fair No 7 Middle False False Good No 8 Middle True True Good Yes 9 Middle False True Excellent Yes 10 Middle False True Excellent Yes 11 Old False True Excellent Yes 12 Old False True Good Yes 13 Old True False Good Yes 14 Old True False Excellent Yes 15 Old False False fair no 例申請(qǐng)貸款 的數(shù)據(jù)集合 Age？ young middle old No:3 Yes:2 No:2 Yes:3 No:4 Yes:1 Own_house？ true false No:0 Yes:6 No:6 Yes:3 （ a） （ b） 第 6章 決策樹 決策樹算法 第 6章 決策樹 決策樹算法 (1)首先計(jì)算 D的熵 D有 6個(gè)否類訓(xùn)練樣例和 9個(gè)是類訓(xùn)練樣例，可計(jì)算如下： entropy(D)= 6/15*log26/15 9/15*log29/15 = (2)嘗試采用 age屬性劃分?jǐn)?shù)據(jù)，可以劃分為三類， D1(age=young), D2(age=midde), D3(age=old) entropyage(D) = 5/15*entropy(D1)5/15*entropy(D2)5/15*entropy(D3) =5/15*+5/15*+5/15*= 3/5*log23/52/5*log22/5= 1/5*log21/54/5*log24/5 = (3) 嘗試采用 own_house屬性將數(shù)據(jù)劃分為兩個(gè)子集 entropyown_house(D)=6/15*entropy(D1)9/15*entropy(D2) =6/15*0+9/15*= entropy(D1)=0/6*log20/66/6*log26/6=0 entropy(D2)=6/9*log26/93/9*log23/9= 第 6章 決策樹 決策樹算法 (4) 分別計(jì)算采用 has_job， Credit_rating屬性的熵值 entropyhas_job(D)= entropyCredit_rating(D)= (5)各個(gè)屬性的信息增益 gain(D,Age)== gain(D,Own_house)== gain(D,Has_job)== gain(D,Credit_rating)== (6)…………. 第 6章 決策樹 決策樹的數(shù)據(jù)準(zhǔn)備 姓名 年齡 收入 學(xué)生 信譽(yù) 電話 地址 郵編 買計(jì)算機(jī) 張三 23 4000 是 良 2