數(shù)據(jù)挖掘?qū)д摰?章-分類-其他技術(shù)課件

數(shù)據(jù)挖掘?qū)д揚ang-ningTan,MichaelStieinbach,andVipinKumar著PearsonEducationLTD.范明等譯人民郵電出版社數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)第5章分類:其他技術(shù)基于規(guī)則的分類最近鄰分類貝葉斯分類神經(jīng)網(wǎng)絡(luò)支持向量機(jī)組合方法不平衡類問題多類問題數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)5.1基于規(guī)則的分類器數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)基于規(guī)則的分類器使用一組“if…then…”規(guī)則進(jìn)行分類規(guī)則:(Condition)

y其中

Condition

是屬性測試的合取

y

是類標(biāo)號左部:規(guī)則的前件或前提右部:規(guī)則的結(jié)論分類規(guī)則的例子:(BloodType=Warm)

(LayEggs=Yes)Birds(TaxableIncome<50K)(Refund=Yes)Evade=No2024/1/34數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)基于規(guī)則的分類器:例脊椎動物數(shù)據(jù)集

名稱體溫表皮覆蓋胎生水生動物飛行動物有腿冬眠類標(biāo)號人類蟒蛇鮭魚鯨青蛙巨蜥蝙蝠鴿子貓虹鳉美洲鱷企鵝豪豬鰻鱺蠑螈

恒溫冷血冷血恒溫冷血冷血恒溫恒溫恒溫冷血冷血恒溫恒溫冷血冷血毛發(fā)鱗片鱗片毛發(fā)無鱗片毛發(fā)羽毛軟毛鱗片鱗片羽毛剛毛鱗片無是否否是否否是否是是否否是否否否否是是半否否否否是半半否是半否否否否否否是是否否否否否否否是否否否是是是是是否是是是否是否是否否是否是否否否否否是否是哺乳類爬行類魚類哺乳類兩棲類爬行類哺乳類鳥類哺乳類魚類爬行類鳥類哺乳類魚類兩棲類2024/1/35數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)基于規(guī)則的分類器的使用規(guī)則r

覆蓋實例x，如果該實例的屬性滿足規(guī)則r的條件r1：（胎生=否）

（飛行動物=是）→鳥類r2：（胎生=否）

（水生動物=是）→魚類r3：（胎生=是）

（體溫=恒溫）→哺乳類r4：（胎生=否）

（飛行動物=否）→爬行類r5：（水生動物=半）→兩棲類規(guī)則r1覆蓋“鷹”=>鳥類規(guī)則r3

覆蓋“灰熊”=>哺乳類名稱體溫表皮覆蓋胎生水生動物飛行動物有腿冬眠類標(biāo)號鷹灰熊

恒溫恒溫羽毛軟毛否是否否是否是是否是？？2024/1/36數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則的質(zhì)量用覆蓋率和準(zhǔn)確率度量規(guī)則的覆蓋率（coverage）:滿足規(guī)則前件的記錄所占的比例規(guī)則的準(zhǔn)確率（accuracy）:在滿足規(guī)則前件的記錄中，滿足規(guī)則后件的記錄所占的比例規(guī)則:(Status=Single)NoCoverage=40%,Accuracy=50%Tid

Refund

Marital

Status

Taxable

Income

Class

1Yes

Single

125KNo2No

Married

100K

No3No

Single

70K

No

4

Yes

Married

120K

No

5

No

Divorced

95K

Yes

6

No

Married

60K

No

7

Yes

Divorced

220K

No

8

No

Single

85K

Yes

9No

Married

75K

No

10NoSingle90K

Yes10

2024/1/37數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)如何用規(guī)則分類一組規(guī)則r1：（胎生=否）

（飛行動物=是）→鳥類r2：（胎生=否）

（水生動物=是）→魚類r3：（胎生=是）

（體溫=恒溫）→哺乳類r4：（胎生=否）

（飛行動物=

否）→爬行類r5：（水生動物=半）→兩棲類待分類記錄狐猴觸發(fā)規(guī)則r3,它分到哺乳類海龜觸發(fā)規(guī)則r4和r5----沖突狗鯊未觸發(fā)任何規(guī)則名稱體溫胎生飛行動物水生動物類狐猴恒溫是否否?海龜冷血否否半水生?狗鯊冷血是否是?2024/1/38數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則的分類器的特征互斥規(guī)則集每個記錄最多被一個規(guī)則覆蓋如果規(guī)則都是相互獨立的，分類器包含互斥規(guī)則如果規(guī)則集不是互斥的一個記錄可能被多個規(guī)則觸發(fā)如何處理?

有序規(guī)則集基于規(guī)則的序vs基于類的序無序規(guī)則集–使用投票策略2024/1/39數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則的分類器的特征(續(xù))窮舉規(guī)則集每個記錄至少被一個規(guī)則覆蓋如果規(guī)則集涵蓋了屬性值的所有可能組合，則規(guī)則集具有窮舉覆蓋如果規(guī)則集不是窮舉的一個記錄可能不被任何規(guī)則觸發(fā)如何處理?

使用缺省類2024/1/310數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)有序規(guī)則集根據(jù)規(guī)則優(yōu)先權(quán)將規(guī)則排序定秩（rank）有序規(guī)則集又成決策表（decisionlist）對記錄進(jìn)行分類時由被觸發(fā)的，具有最高秩的規(guī)則確定記錄的類標(biāo)號如果沒有規(guī)則被觸發(fā)，則指派到缺省類r1：（胎生=否）

（飛行動物=是）→鳥類r2：（胎生=否）

（水生動物=是）→魚類r3：（胎生=是）

（體溫=恒溫）→哺乳類r4：（胎生=否）

（飛行動物=否）→爬行類r5：（水生動物=半）→兩棲類名稱體溫胎生飛行動物水生動物類海龜冷血否否半水生?2024/1/311數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則定序方案基于規(guī)則的序根據(jù)規(guī)則的質(zhì)量排序基于類的序?qū)儆谕活惖囊?guī)則放在一起基于類信息（如類的分布、重要性）對每類規(guī)則排序基于規(guī)則的排序（表皮覆蓋=羽毛,飛行動物=是）

鳥類（體溫=恒溫,胎生=是）

哺乳類（體溫=恒溫,胎生=否）

鳥類（水生動物=半）

兩棲類（表皮覆蓋=鱗片,水生動物=否）

爬行類（表皮覆蓋=鱗片,水生動物=是）

魚類（表皮覆蓋=無）

兩棲類基于類的排序（表皮覆蓋=羽毛,飛行動物=是）

鳥類（體溫=恒溫,胎生=否）

鳥類（體溫=恒溫,胎生=是）

哺乳類（水生動物=半）

兩棲類（表皮覆蓋=無）==＞兩棲類（表皮覆蓋=鱗片,水生動物=否）

爬行類（表皮覆蓋=鱗片,水生動物=是）

魚類2024/1/312數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)如何建立基于規(guī)則的分類器直接方法:直接由數(shù)據(jù)提取規(guī)則例如:RIPPER,CN2,Holte’s1R間接方法:由其他分類模型提取規(guī)則(例如，從決策樹、神經(jīng)網(wǎng)絡(luò)等).例如:C4.5rules2024/1/313數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)直接方法:順序覆蓋基本思想依次對每個類建立一個或多個規(guī)則對第i類建立規(guī)則第i類記錄為正例，其余為負(fù)例建立一個第i類的規(guī)則r，盡可能地覆蓋正例，而不覆蓋負(fù)例刪除r覆蓋的所有記錄，在剩余數(shù)據(jù)集上學(xué)習(xí)下一個規(guī)則，直到所有第i類記錄都被刪除2024/1/314數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)直接方法:順序覆蓋順序覆蓋（sequentialcovering）算法

1：令E是訓(xùn)練記錄，A是屬性—值對的集合{(Aj,vj)}2：令Yo是類的有序集{y1,y2,...,yk}3：令R={}是初始規(guī)則列表

4：for每個類y∈Yo

{yk}do5： while終止條件不滿足do6：r←Learn-One-Rule(E,A,y)7：從E中刪除被r覆蓋的訓(xùn)練記錄

8：追加r到規(guī)則列表尾部：R

R

r9：endwhile10：endfor11：把默認(rèn)規(guī)則{}→yk插入到規(guī)則列表R尾部2024/1/315數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)順序覆蓋:例(a)Originaldata(b)Step1(c)Step2(c)Step32024/1/316數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)刪除實例為什么要刪除實例?否則,下一個規(guī)則將與前面的規(guī)則相同為什么刪除正實例?確保下一個規(guī)則不同為什么刪除負(fù)實例?防止低估規(guī)則的準(zhǔn)確率比較圖中的規(guī)則R2和R32024/1/317數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)Learn-One-Rule規(guī)則增長實例刪除規(guī)則評估停止準(zhǔn)則規(guī)則剪枝2024/1/318數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則增長兩種策略一般到特殊從初始規(guī)則r:{}→y開始反復(fù)加入合取項，得到更特殊的規(guī)則，直到不能再加入特殊到一般隨機(jī)地選擇一個正例作為初始規(guī)則反復(fù)刪除合取項，得到更一般的規(guī)則，直到不能再刪除問題加入/刪除合取項有多種選擇，如何選擇？何時停止加入/刪除合取項？ 需要評估標(biāo)準(zhǔn)2024/1/319數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則增長:例一般到特殊體溫=恒溫，表皮覆蓋=毛發(fā)，胎生=是，水生動物=否，飛行動物=否，有腿=是，冬眠=否=>哺乳類表皮覆蓋=毛發(fā)，胎生=是，水生動物=否，飛行動物=否，有腿=是，冬眠=否=>哺乳類體溫=恒溫，表皮覆蓋=毛發(fā)，胎生=是，水生動物=否，飛行動物=否，有腿=是=>哺乳類{}=>哺乳類表皮覆蓋=毛發(fā)=>哺乳類體溫=恒溫=>哺乳類有腿=否=>哺乳類體溫=恒溫，有腿=是=>哺乳類體溫=恒溫，胎生=是=>哺乳類

特殊到一般2024/1/320數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則評估常用的度量準(zhǔn)確率似然比LaplaceM-estimateFOIL信息增益2024/1/321數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則評估(續(xù))準(zhǔn)確率Accuracyn:被規(guī)則覆蓋的實例數(shù)nc:被規(guī)則正確分類的實例數(shù)問題：準(zhǔn)確率高的規(guī)則可能覆蓋率太低似然比（越高越好）k是類的個數(shù)fi是被規(guī)則覆蓋的類i的樣本的觀測頻度ei是規(guī)則作隨機(jī)猜測的期望頻度2024/1/322數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則評估:例例:60個正例和100個反例 規(guī)則r1：覆蓋50個正例和5個反例（acc=90.9%） 規(guī)則r2：覆蓋2個正例和0個反例（acc=100%）使用準(zhǔn)確率,r2好使用似然比r1:正類的期望頻度為e+=55

60/160=20.625

負(fù)類的期望頻度為e

=55

100/160=34.375r2:正類的期望頻度為e+=2

60/160=0.75

負(fù)類的期望頻度為e

=2

100/160=1.25R(r1)=2

[50

log2(50/20.625)+5

log2(5/34.375)]=99.9R(r2)=2

[2

log2(2/0.75)+0

log2(0/1.25)]=5.66r1比r2好2024/1/323數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則評估(續(xù))

考慮規(guī)則覆蓋率的評估度量n是規(guī)則覆蓋的樣例數(shù)，f+是規(guī)則覆蓋的正例數(shù)，k是類的總數(shù)，p+是正類的先驗概率當(dāng)規(guī)則的覆蓋率很高時，兩個度量都漸近地趨向于規(guī)則的準(zhǔn)確率f+/n

繼續(xù)前例r1的Laplace度量為51/57=89.47%，很接近它的準(zhǔn)確率r2的Laplace度量（75%）比它的準(zhǔn)確率小很多2024/1/324數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則評估(續(xù))

考慮規(guī)則的支持度計數(shù)的評估度量規(guī)則的支持度計數(shù)對應(yīng)于它所覆蓋的正例數(shù)FOIL信息增益（FirstOrderInductiveLeanerinformationgain）設(shè)規(guī)則r:A→+覆蓋p0個正例和n0個反例;規(guī)則r’:A

B→+覆蓋p1個正例和n1個反例.擴(kuò)展后規(guī)則的FOIL信息增益定義為該度量與p1和p1/(p1+n1)成正比，所以它更傾向于選擇那些高支持度計數(shù)和高準(zhǔn)確率的規(guī)則繼續(xù)前例r1和r2的FOIL信息增益分別為43.12和2，因此規(guī)則r1比r2好2024/1/325數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)停止條件與規(guī)則剪枝停止條件計算增益如果增益不顯著,則丟棄新規(guī)則規(guī)則剪枝類似于決策樹后剪枝降低錯誤剪枝:

刪除規(guī)則中的合取項比較剪枝前后的錯誤率如果降低了錯誤率,則剪掉該合取項2024/1/326數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)直接方法:RIPPER對于2類問題,選定一個類為正類，另一個為負(fù)類從正類學(xué)習(xí)規(guī)則負(fù)類時缺省類多類問題按類的大小（屬于特定類的實例所占的比例）對諸類排序從最小的類開始學(xué)習(xí)規(guī)則，其余類都看做負(fù)類對次小類學(xué)習(xí)規(guī)則，如此下去2024/1/327數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)直接方法:RIPPER(續(xù))

規(guī)則增長:由空規(guī)則開始只要能夠提高FOIL信息增益就增加一個合取項當(dāng)規(guī)則不再覆蓋負(fù)實例時就停止剪枝剪枝度量:

v=(p

n)/(p+n)

p:驗證集中被規(guī)則覆蓋的正實例數(shù)

n:驗證集中被規(guī)則覆蓋的負(fù)實例數(shù)剪枝方法:如果剪掉合取項可以提高v就剪2024/1/328數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)直接方法:RIPPER(續(xù))

建立規(guī)則集:使用順序覆蓋算找出覆蓋當(dāng)前正實例的最佳規(guī)則刪除被規(guī)則覆蓋的所有正實例和負(fù)實例當(dāng)一個規(guī)則加入規(guī)則集時，計算新的描述長度當(dāng)新的描述長度比已經(jīng)得到的描述長度多d位時，就停止增加新規(guī)則2024/1/329數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)直接方法:RIPPER(續(xù))

優(yōu)化規(guī)則集:對規(guī)則集R中的每個規(guī)則r考慮2個替換的規(guī)則:替換規(guī)則(r*):重新增長新規(guī)則編輯的規(guī)則(r’):把一個新的合取項增加到規(guī)則r比較替換前后的規(guī)則集選擇最小化MDL的規(guī)則集對剩下的正實例，重復(fù)規(guī)則產(chǎn)生和優(yōu)化2024/1/330數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)規(guī)則提取的間接方法決策樹從根結(jié)點到葉結(jié)點的每一條路徑都可以表示為一個分類規(guī)則路徑中的測試條件構(gòu)成規(guī)則前件的合取項，葉結(jié)點的類標(biāo)號賦給規(guī)則后件

2024/1/331數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)間接方法:C4.5rules(續(xù))

從未剪枝的決策樹提取規(guī)則規(guī)則產(chǎn)生對每個規(guī)則r:A

y,考慮替換規(guī)則r’:A’

y其中A’由刪除A的一個合取項得到比較r與所有r’的悲觀誤差如果r’的悲觀誤差小，則剪枝重復(fù)該過程，直到不能改進(jìn)2024/1/332數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)間接方法:C4.5rules規(guī)則定序不是對規(guī)則定序，而是對規(guī)則的子集定序(classordering)每個規(guī)則子集是一組具有相同規(guī)則后件(class)的規(guī)則計算每個子集的描述長度描述長度=L(error)+g

L(model)g

是參數(shù)，考慮規(guī)則集中冗余屬性(缺省值g=0.5)2024/1/333數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)C4.5vsC4.5rulesvsRIPPERC4.5rules:（胎生=否，飛行動物=是）=>鳥類（胎生=否，水生動物=是）=>魚類（胎生=是）=>哺乳類（胎生=否，飛行動物=否，水生動物=否）=>爬行類（）=>兩棲類

胎生水生?飛行?哺乳類魚類兩棲類鳥類爬行類YesNoYesSometimesNoYesNo2024/1/334數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)基于規(guī)則的分類器的特征表達(dá)能力與決策樹一樣高容易解釋容易產(chǎn)生能夠快速對新實例分類性能可與決策樹相媲美2024/1/335數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)5.2最近鄰分類器數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)急切學(xué)習(xí)vs惰性學(xué)習(xí)急切學(xué)習(xí)（EagerLearner）兩步過程:(1)歸納(2)演繹惰性學(xué)習(xí)（lazylearner）把訓(xùn)練數(shù)據(jù)建模過程推遲到需要對樣本分類時例子Rote-learner（死記硬背）記住所有的訓(xùn)練數(shù)據(jù)，僅當(dāng)記錄的屬性值與一個訓(xùn)練記錄完全匹配才對它分類最近鄰（Nearestneighbor）使用“最近”的k

個點(最近鄰)進(jìn)行分類2024/1/337數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)最近鄰分類器基本思想:Ifitwalkslikeaduck,quackslikeaduck,thenit’sprobablyaduck訓(xùn)練記錄待分類記錄計算距離選擇k

個“最近”的記錄2024/1/338數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)最近鄰分類器要求存放訓(xùn)練記錄計算記錄間距離的度量k值,最近鄰數(shù)對未知記錄分類:計算域各訓(xùn)練記錄的距離找出k

個最近鄰使用最近鄰的類標(biāo)號決定未知記錄的類標(biāo)號(例如,多數(shù)表決)2024/1/339數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)最近鄰定義

記錄x的k-最近鄰是與x之間距離最小的k個訓(xùn)練數(shù)據(jù)點2024/1/340數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)1nearest-neighborVoronoiDiagram2024/1/341數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)

k-最近鄰分類算法k-最近鄰分類算法1：令k是最近鄰數(shù)目，D是訓(xùn)練樣例的集合2：for每個測試樣例z=(x',y')do3：計算z和每個樣例(x,y)

D之間的距離d(x',x)4：選擇離z最近的k個訓(xùn)練樣例的集合Dz

D5：6：endfor距離加權(quán)表決2024/1/342數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)k-最近鄰k值的選擇:如果k

太小,則對噪聲點敏感如果k

太大,鄰域可能包含很多其他類的點定標(biāo)問題（規(guī)范化）屬性可能需要規(guī)范化，防止距離度量被具有很大值域的屬性所左右2024/1/343數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)k-NN的特點k-NN的特點是一種基于實例的學(xué)習(xí)需要一個鄰近性度量來確定實例間的相似性或距離不需要建立模型，但分類一個測試樣例開銷很大需要計算域所有訓(xùn)練實例之間的距離基于局部信息進(jìn)行預(yù)測，對噪聲非常敏感最近鄰分類器可以生成任意形狀的決策邊界決策樹和基于規(guī)則的分類器通常是直線決策邊界需要適當(dāng)?shù)泥徑远攘亢蛿?shù)據(jù)預(yù)處理防止鄰近性度量被某個屬性左右2024/1/344數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)5.3貝葉斯分類器數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)貝葉斯定理每個記錄用一個d維特征向量X=(x1,x2,…,xd)表示假定有k個類y1,y2,…,yk.給定X,X屬于yj類的后驗概率P(yj|X)

滿足貝葉斯(Bayes)定理

MAP(maximumposteriorihypothesis,最大后驗假設(shè))將X指派到具有最大后驗概率P(yj|X)的類yj，即將X指派到P(X|yj)P(yj)

最大的類yj2024/1/346數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)樸素貝葉斯分類樸素貝葉斯分類(Na?veBayesClassifier)工作原理給定一個未知的數(shù)據(jù)樣本X,分類法將預(yù)測X屬于具有最高后驗概率的類.即,未知的樣本分配給類yj,當(dāng)且僅當(dāng) 根據(jù)貝葉斯定理,我們有由于P(X)

對于所有類為常數(shù),只需要最大化P(X|yj)P(yj)即可.2024/1/347數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)樸素貝葉斯分類(續(xù))估計P(yj)類yj的先驗概率可以用下式估計P(yj)=nj/n

其中,nj是類yj中的訓(xùn)練樣本數(shù),而n是訓(xùn)練樣本總數(shù)估計P(X|yj)為便于估計P(X|yj),假定類條件獨立----給定樣本的類標(biāo)號,假定屬性值條件地相互獨立.于是,P(X|Y=yj)可以用下式估計

其中,P(xi|yj)可以由訓(xùn)練樣本估值2024/1/348數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)樸素貝葉斯分類(續(xù))估計P(xi|yj)設(shè)第i個屬性Ai是分類屬性,則

P(xi|yj)=nij/nj

其中nij是在屬性Ai上具有值xi的yj類的訓(xùn)練樣本數(shù),而nj是yj類的訓(xùn)練樣本數(shù)設(shè)第i個屬性Ai是連續(xù)值屬性把Ai離散化假定Ai服從高斯分布其中,

ij,

ij分別為給定yj類的訓(xùn)練樣本在屬性Ai上的均值和標(biāo)準(zhǔn)差2024/1/349數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)樸素貝葉斯分類樸素貝葉斯分類器所需要的信息計算每個類的先驗概率P(yj) P(yj)=nj/n

其中,nj是yi類的訓(xùn)練樣本數(shù),而n是訓(xùn)練樣本總數(shù)對于離散屬性Ai，設(shè)的不同值為ai1,ai2,…,ail

，對于每個類yj，計算后驗概率P(aik|yj),1

k

lP(aik|yj)=nikj/nj其中nikj是在屬性Ai上具有值aik

的yj類的訓(xùn)練樣本數(shù),而nj是yj類的訓(xùn)練樣本數(shù)對于連續(xù)屬性Ai

和每個類yj，計算yj類樣本的均值

ij,標(biāo)準(zhǔn)差

ij2024/1/350數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)貝葉斯分類器:例例:P(Yes)=3/10P(No)=7/10P(有房=是|No)=3/7P(有房=否|No)=4/7P(有房=是|Yes)=0P(有房=否|Yes)=1P(婚姻狀況=單身|No)=2/7P(婚姻狀況=離婚|No)=1/7P(婚姻狀況=已婚|No)=4/7P(婚姻狀況=單身|Yes)=2/3P(婚姻狀況=離婚|Yes)=1/3P(婚姻狀況=已婚|Yes)=0年收入：類=No：樣本均值=110

樣本方差=2975類=Yes：樣本均值=90

樣本方差=25Tid有房婚姻狀況年收入拖欠貸款12345678910是否否是否否是否否否單身已婚單身已婚離婚已婚離婚單身已婚單身125K100K70K120K95K60K220K85K75K90KNoNoNoNoYesNoNoYesNoYes2024/1/351數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)貝葉斯分類器:例(續(xù))X=（有房=否，婚姻狀況=已婚，年收入=$120K）計算P(X|No)和P(X|Yes)

P(X|No)=P(有房=否|No)

P(婚姻狀況=已婚|No)

P(年收入=$120K|No) =4/7

4/7

0.0072=0.0024P(X|Yes)=P(有房=否|Yes)

P(婚姻狀況=已婚|Yes)

P(年收入=$120K|Yes) =1

0

1.2

10

9=0計算P(X|No)P(No)和P(X|Yes)P(Yes)

P(X|No)P(No)=0.00240.7=0.00168P(X|Yes)P(Yes)=00.3=0因為P(X|No)P(No)>P(X|Yes)P(Yes),所以X分類為No2024/1/352數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)貝葉斯分類器問題如果諸條件概率P(Xi=xi|Y=yj)中的一個為0，則它們的乘積（計算P(X|Y=yj)的表達(dá)式）為0很可能每個P(X|Y=yj)都為0解決方法使用Laplace估計:

原估計:P(Xi=xi|Y=yj)=nij/nj2024/1/353數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)貝葉斯分類器的特點對孤立的噪聲點的魯棒性個別點對概率估計的影響很小容易處理缺失值在估計概率時忽略缺失值的訓(xùn)練實例對不相關(guān)屬性的魯棒性各類在不相關(guān)屬性上具有類似分布類條件獨立假設(shè)可能不成立使用其他技術(shù)，如貝葉斯信念網(wǎng)絡(luò)（BayesianBeliefNetworks，BBN）2024/1/354數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)貝葉斯信念網(wǎng)絡(luò)貝葉斯信念網(wǎng)絡(luò)(Bayesianbeliefnetwork)允許在變量的子集間定義類條件獨立性因果關(guān)系圖模型表示變量之間的依賴給出聯(lián)合概率分布的說明圖示節(jié)點:隨機(jī)變量邊:依賴X,Y

是Z的父節(jié)點/前驅(qū),

并且Y

是P的父節(jié)點/前驅(qū)Z

和P之間沒有依賴關(guān)系圖中沒有環(huán)XYZP2024/1/355數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)貝葉斯信念網(wǎng)絡(luò):例變量LungCance(LC)值的條件概率表(CPT),給出其雙親結(jié)點FamilyHistory和Smoke的每個可能值的組合的條件概率2024/1/356數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)貝葉斯信念網(wǎng)絡(luò):例(續(xù))給出了LungCancer的CPT.對于其雙親值的每個可能組合,表中給出了LungCancer的每個值的條件概率.例如,由左上角和右下角,我們分別看到

P(LungCancer=“yes”|FamilyHistory=“yes”,Smoker=“yes”)=0.8 P(LungCancer=“no”|FamilyHistory=“no”,Smoker=“no”)=0.9對應(yīng)于屬性或變量Z1,…,Zn的任意元組(z1,…,zn)的聯(lián)合概率由下式計算 其中,P(zi|parents(zi))的值對應(yīng)于Zi的CPT中的表目2024/1/357數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)訓(xùn)練貝葉斯信念網(wǎng)絡(luò)若干情況給定網(wǎng)絡(luò)結(jié)構(gòu)和所有可觀測變量只需要學(xué)習(xí)CPT網(wǎng)絡(luò)結(jié)構(gòu)已知,而某些變量是隱藏的使用梯度下降法或類似于神經(jīng)網(wǎng)絡(luò)的方法訓(xùn)練信念網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)未知,所有的變量可以觀測搜索模型空間,構(gòu)造網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)未知,所有變量是隱藏的沒有已知的好算法D.Heckerman,Bayesiannetworksfordatamining2024/1/358數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)訓(xùn)練貝葉斯信念網(wǎng)絡(luò)梯度下降法設(shè)S是s個訓(xùn)練樣本X1,X2,...,Xs的集合,wijk是具有雙親Ui=uik的變量Y=yij的CPT項wijk可以看作權(quán),類似于神經(jīng)網(wǎng)絡(luò)中隱藏單元的權(quán).權(quán)的集合記作w

這些權(quán)被初始化為隨機(jī)概率值.梯度下降策略采用貪心爬山法.在每次迭代中,修改這些權(quán),并最終收斂到一個局部最優(yōu)解基于w的每個可能設(shè)置都等可能的假定,該方法搜索能最好地對數(shù)據(jù)建模wijk值.目標(biāo)是最大化2024/1/359數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)訓(xùn)練貝葉斯信念網(wǎng)絡(luò):梯度下降法給定網(wǎng)絡(luò)結(jié)構(gòu)和wijk的初值,該算法按以下步驟處理計算梯度：對每個i,j,k，計算沿梯度方向前進(jìn)一小步:用下式更新權(quán)值

l是表示步長的學(xué)習(xí)率,設(shè)置為一個小常數(shù)重新規(guī)格化權(quán)值：由于權(quán)值wijk是概率值,它們必須在0.0和1.0之間,并且對于所有的i,k，必須有2024/1/360數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)BBN的特點BBN提供了一種用圖形模型來捕獲特定領(lǐng)域的先驗知識的方法。網(wǎng)絡(luò)還可以用來對變量間的因果依賴關(guān)系進(jìn)行編碼構(gòu)造網(wǎng)絡(luò)可能既費時又費力。然而，一旦網(wǎng)絡(luò)結(jié)構(gòu)確定下來，添加新變量就十分容易貝葉斯網(wǎng)絡(luò)很適合處理不完整的數(shù)據(jù)。對有屬性遺漏的實例可以通過對該屬性的所有可能取值的概率求和或求積分來加以處理因為數(shù)據(jù)和先驗知識以概率的方式結(jié)合起來了，所以該方法對模型的過分?jǐn)M合問題是非常魯棒的2024/1/361數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)使用BBN進(jìn)行推理舉例E:鍛煉,D:飲食,HD:心臟病,Hb:胸口痛,BP:血壓,CP:胸痛鍛煉飲食心口痛心臟病血壓胸痛D=健康D=健康D=不健康健康不健康健康不健康BP=高2024/1/362數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)情況一：沒有先驗信息通過計算先驗概率P(HD=Yes)和P(HD=No)來確定一個人是否可能患心臟病設(shè)

∈{Yes,No}表示鍛煉的兩個值，

∈{健康,不健康}表示飲食的兩個值，由全概率公式P(HD=Yes)=

= =0.25

0.7

0.25+0.45

0.7

0.75+0.55

0.3

0.25+0.75

0.3

0.75 =0.49因為P(HD=No)=1

P(HD=Yes)=0.51，所以，此人不得心臟病的機(jī)率略微大一點2024/1/363數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)情況二：高血壓如果一個人有高血壓，可以通過比較后驗概率P(HD=Yes|BP=高)和P(HD=No|BP=高)來診斷他是否患有心臟病先用全概率公式，計算P(BP=高)P(BP=高)= =0.85

0.49+0.2

0.51=0.5185其中

{Yes,No}

用貝葉斯公式計算此人患心臟病的后驗概率2024/1/364數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)情況三情況三：高血壓、飲食健康、經(jīng)常鍛煉身體患心臟病的后驗概率2024/1/365數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)5.4人工神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)最早是由心理學(xué)家和神經(jīng)學(xué)家提出的,旨在尋求開發(fā)和測試神經(jīng)的計算模擬神經(jīng)網(wǎng)絡(luò)是一組連接的輸入/輸出單元,其中每個連接都與一個權(quán)相關(guān)聯(lián)在學(xué)習(xí)階段,通過調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán),使得能夠預(yù)測輸入樣本的正確類標(biāo)記神經(jīng)網(wǎng)絡(luò)的優(yōu)點對噪音數(shù)據(jù)的高承受能力對未知樣本的分類能力神經(jīng)網(wǎng)絡(luò)缺點需要很長的訓(xùn)練時間,因而對于有足夠長訓(xùn)練時間的應(yīng)用更合適很難解釋蘊涵在學(xué)習(xí)權(quán)之中的符號含義它需要大量的參數(shù),這些通常主要靠經(jīng)驗確定,如網(wǎng)絡(luò)拓?fù)浠颉敖Y(jié)構(gòu)”2024/1/367數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)多層前饋神經(jīng)網(wǎng)絡(luò)后向傳播是一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法后向傳播算法在多層前饋(multilayerfeed-forward)神經(jīng)網(wǎng)絡(luò)上學(xué)習(xí)例:一個多層前饋神經(jīng)網(wǎng)絡(luò)訓(xùn)練樣本X={x1,x2,...,xi}饋入輸入層.每層之間存在加權(quán)連接;其中,wij表示由某層的單元j到前一層的單元i的權(quán)2024/1/368數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)多層前饋神經(jīng)網(wǎng)絡(luò)(續(xù))輸入同時提供給稱作輸入層的單元層隱藏層的數(shù)量是任意的,實踐中通常只用一層輸出層發(fā)布給定樣本的網(wǎng)絡(luò)預(yù)測隱藏層和輸出層的單元,有時稱作neurodes(源于符號生物學(xué)),或輸出單元包含n個隱藏層的網(wǎng)絡(luò)稱作n+1層神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)是前饋的,如果其權(quán)都不回送到輸入單元,或前一層的輸出單元網(wǎng)絡(luò)是全連接的,如果每個單元都向下一層的每個單元提供輸入給定足夠多的隱藏單元,線性閾值函數(shù)的多層前饋神經(jīng)網(wǎng)絡(luò)可以逼近任何函數(shù)2024/1/369數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)多層前饋神經(jīng)網(wǎng)絡(luò)(續(xù))定義網(wǎng)絡(luò)拓?fù)溆脩舯仨氄f明輸入層的單元數(shù),隱藏層數(shù),每一隱藏層的單元數(shù)和輸出層的單元數(shù)對于“最好的”隱藏層單元數(shù)沒有明確的規(guī)則網(wǎng)絡(luò)設(shè)計是一個實驗過程,并可能影響結(jié)果訓(xùn)練網(wǎng)絡(luò)的準(zhǔn)確性.權(quán)的初值也可能影響結(jié)果的準(zhǔn)確性一旦網(wǎng)絡(luò)經(jīng)過訓(xùn)練,并且其準(zhǔn)確率不能被接受,則通常用不同的網(wǎng)絡(luò)拓?fù)浠蚴褂貌煌某跏紮?quán)值,重復(fù)訓(xùn)練過程對訓(xùn)練樣本中每個屬性的值進(jìn)行規(guī)格化將有助于加快學(xué)習(xí)過程通常,對輸入值規(guī)格化,使得它們落入0.0和1.0之間離散值屬性可以重新編碼,使得每個域值一個輸入單元例如,如果屬性A的定義域為(a0,a1,a2),則可以分配三個輸入單元I0,I1,I2表示A

2024/1/370數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播基本思想迭代地處理一組訓(xùn)練樣本,將每個樣本的網(wǎng)絡(luò)預(yù)測與實際知道的類標(biāo)號比較,進(jìn)行學(xué)習(xí).對于每個訓(xùn)練樣本,修改權(quán)值,使得網(wǎng)絡(luò)預(yù)測和實際類之間的均方誤差最小盡管不能保證,一般地,權(quán)將最終收斂,學(xué)習(xí)過程停止步驟解釋初始化權(quán):網(wǎng)絡(luò)的權(quán)被初始化為很小的隨機(jī)數(shù)(例如,由-1.0到1.0,或由-0.5到0.5),每個單元有一個偏置,也類似地初始化為小隨機(jī)數(shù)每個樣本X按以下步驟處理向前傳播輸入后向傳播誤差重復(fù)以上兩步,直至終止條件滿足2024/1/371數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播(續(xù))向前傳播輸入計算隱藏層和輸出層每個單元的凈輸入和輸出對于輸入層的單元j,它的輸出等于它的輸入;Oj

=Ij.給定隱藏層或輸出層的單元j,到單元j的凈輸入Ij是 其中,wij是由上一層的單元i到單元j的連接的權(quán);Oi是上一層的單元i的輸出;而

j是單元j的偏差(用來改變單元的活性)給定單元j的凈輸入Ij,則單元j的輸出Oj用下式(logistic函數(shù))計算 該函數(shù)又稱擠壓函數(shù),因為它將一個較大的輸入值域映射到較小的區(qū)間0到12024/1/372數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)一個神經(jīng)元(Neuron)一個隱藏或輸出單元j：j的輸入是來自前一層的輸出.這些與對應(yīng)的權(quán)相乘,以形成加權(quán)和,加權(quán)和加到與單元j相聯(lián)的偏差上,一個非線性的活化函數(shù)用于凈輸入激活函數(shù)輸出輸入（上一層的輸出）加權(quán)和權(quán)值偏置2024/1/373數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)神經(jīng)網(wǎng)絡(luò)的激活函數(shù)

線性函數(shù)S型函數(shù)雙曲正切函數(shù)符號函數(shù)2024/1/374數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播(續(xù))后向傳播誤差通過更新權(quán)和反映網(wǎng)絡(luò)預(yù)測誤差的偏置,向后傳播誤差對于輸出層單元j,誤差Errj用下式計算 其中,Oj是單元j的實際輸出,而Tj是j基于給定訓(xùn)練樣本的已知類標(biāo)號的真正輸出,Oj(1-Oj)是logistic函數(shù)的導(dǎo)數(shù)隱藏層單元j的誤差是 其中,wkj是由下一較高層中單元k到單元j的連接權(quán),而Errk是單元k的誤差2024/1/375數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播(續(xù))后向傳播誤差(續(xù))更新權(quán)和偏置,以反映傳播的誤差權(quán)由下式更新 其中,

wij是權(quán)wij的改變;變量l是學(xué)習(xí)率,通常取0和1之間的值.學(xué)習(xí)率幫助避免陷入判定空間的局部最小學(xué)習(xí)率調(diào)整規(guī)則:將學(xué)習(xí)率設(shè)置為1/t.其中t是已對訓(xùn)練樣本集迭代的次數(shù)偏置由下式更新 其中,

j是偏置

j的改變2024/1/376數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播(續(xù))實例更新VS.周期更新實例更新(caseupdate):每處理一個樣本就更新權(quán)值和偏置周期更新(epochupdate):處理完訓(xùn)練集中的所有樣本之后再更新權(quán)值和偏置終止條件前一周期所有的

wij都小于某個指定的閾值,或前一周期未正確分類的樣本百分比小于某個閾值,或超過預(yù)先指定的周期數(shù)實踐中,權(quán)值收斂可能需要數(shù)十萬個周期2024/1/377數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播算法輸入D:由訓(xùn)練元組和它們的相關(guān)聯(lián)的目標(biāo)值組成的數(shù)據(jù)集l:學(xué)習(xí)率Network:多層前饋網(wǎng)絡(luò)輸出:訓(xùn)練后的神經(jīng)網(wǎng)絡(luò)方法:(1)初始化network的權(quán)和偏置(2)while(終止條件不滿足){(3)for(D中每個訓(xùn)練元組X){(4)//向前傳播輸入(5)for

每個輸入層單元j{(6)Oj

=Ij

；//輸入單元的輸出是它的實際輸入值(7)for(隱藏或輸出層每個單元j){(8)//相對于前一層i,計算單元j的凈輸入(9)//計算單元j的輸出

2024/1/378數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播算法(續(xù))(10)//后向傳播誤差(11)for輸出層每個單元j

(12)Errj

=Oj(1

Oj)(Tj

Oj)；//計算誤差(13)for(由最后一個到第一個隱藏層,對于隱藏層每個單元j)(14)//計算下一個較高層k的誤差(15)fornetwor中每個權(quán)wij{(16)

wij

=(l)ErrjOi

；//權(quán)值增量(17)wij=wij+

wij

；}//權(quán)值更新(18)fornetwor中每個偏差

j{(19)

j=(l)Errj；

//偏置增量(20)

j=

j+

j；}//偏置更新

(21)}}2024/1/379數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播:例一個多層前饋神經(jīng)網(wǎng)絡(luò)第一個訓(xùn)練樣本X={1,0,1}（其類標(biāo)號為1）2024/1/380數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播:例(續(xù))初始輸入、權(quán)值和偏差值凈輸入和輸出的計算計算每個結(jié)點的誤差x1x2x3w14w15w24w25w34w35w46w56

4

5

61010.2-0.30.40.1-0.50.2-0.3-0.2-0.40.20.1單元j凈輸入Ij輸出Oj4560.2+0

0.5

0.4=

0.7

0.3+0+0.2+0.2=0.1(-0.3)(0.332)-(0.2)(0.525)+0.1=-0.1051+(1+e0.7)=0.331+(1+e-0.1)=0.5251+(1+e-0.105)=0.474單元jErrj

654(0.474)(1-0.474)(1-0.474)=0.1311(0.525)(1-0.525)(0.1311)(-0.2)=-0.0065(0.332)(1-0.332)(0.1311)(-0.3)=-0.020872024/1/381數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)后向傳播:例(續(xù))計算權(quán)和偏置的更新權(quán)或偏差

新值

w46w56w14w15w24w25w34w35

6

5

4

-0.3+(0.9)(0.1311)(0.332)=-0.261-0.2+(0.9)(0.1311)(0.525)=-0.1380.2+(0.9)(-0.0087)(1)=0.192-0.3+(0.9)(0.0065)(1)=-0.3060.4+(0.9)(-0.0087)(0)=0.40.1+(0.9)(-0.0065)(0)=0.1-0.5+(0.9)(-0.0087)(1)=-0.5080.1+(0.9)(-0.0065)(1)=0.1940.1+(0.9)(0.1311)=0.2180.2+(0.9)(-0.0065)=0.194-0.4+(0.9)(-0.0087)=-0.4082024/1/382數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)神經(jīng)網(wǎng)絡(luò)的特點

至少含有一個隱藏層的多層神經(jīng)網(wǎng)絡(luò)是一種普適近似（universalapproximator），即可以用來近似任何目標(biāo)函數(shù)ANN可以處理冗余特征權(quán)值在訓(xùn)練過程中自動學(xué)習(xí)，冗余特征的權(quán)值非常小神經(jīng)網(wǎng)絡(luò)對訓(xùn)練數(shù)據(jù)中的噪聲非常敏感使用確認(rèn)集來確定模型的泛化誤差每次迭代把權(quán)值減少一個因子使用的梯度下降方法經(jīng)常會收斂到局部最小值權(quán)值更新公式中加上一個動量項訓(xùn)練ANN是一個很耗時的過程，但分類非?？?024/1/383數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)5.5支持向量機(jī)數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)支持向量機(jī)支持向量機(jī)(SupportVectorMachines,SVM)源于Vapnik和Chervonenkis的統(tǒng)計學(xué)習(xí)理論的早期工作第一篇論文是Boser,Guyon和Vapnik[BGV92]的文章優(yōu)點對復(fù)雜的非線性邊界的建模能力與其它模型相比,它們不太容易過分?jǐn)M合支持向量機(jī)還提供了學(xué)習(xí)模型的緊湊表示廣泛的使用范圍SVM可以用來預(yù)測和分類它們已經(jīng)用在許多領(lǐng)域,包括手寫數(shù)字識別、對象識別、演說人識別,以及基準(zhǔn)時間序列預(yù)測檢驗2024/1/385數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)支持向量機(jī)兩個線性可分的類找到這樣一個超平面，使得所有的方塊位于這個超平面的一側(cè)，而所有的圓圈位于它的另一側(cè)可能存在無窮多個那樣的超平面2024/1/386數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)決策邊界的邊緣找這樣的超平面，它最大化邊緣B1比B2好2024/1/387數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM的決策邊界和邊緣一個線性分類器的決策邊界可以寫成如下形式：

wx+b=0其中，w和b是模型的參數(shù)2024/1/388數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)邊緣方塊的類標(biāo)號為+1，圓圈的類標(biāo)號為

1z的類標(biāo)號y

調(diào)整決策邊界的參數(shù)w和b，兩個平行的超平面bi1和bi2可以表示如下bi1：w

x+b=1bi2：w

x+b=

1可以證明,邊緣d2024/1/389數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)邊緣推導(dǎo)w的方向垂直于決策邊界如果xa和xb是任意兩個位于決策邊界上的點，則wxa+b=0,wxb+b=0于是w(xb

xa)=0.由于xb

xa是決策超平面中任意向量,于是w的方向必然垂直于決策邊界令x1是bi1上的數(shù)據(jù)點，x2是bi2上的數(shù)據(jù)點.代入bi1和bi2相減得到w.(x1

x2)=2由令u=w,v=x1

x2,得到||w||||x1

x2||cos(w,x1

x2)=22024/1/390數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)邊緣推導(dǎo)(續(xù))但||x1

x2||cos(w,x1

x2)=d于是||w||

d=2，即2024/1/391數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVMSVM的訓(xùn)練階段從訓(xùn)練數(shù)據(jù)中估計決策邊界的參數(shù)w和b

最大化邊緣d，并滿足wxi+b≥1

如果yi

=1wxi+b≤

1

如果yi

=

1

即yi(wxi

+b)≥1

最大化d等價于最小化這是一個凸二次優(yōu)化問題，可以通過標(biāo)準(zhǔn)的拉格朗日乘子（Lagrangemultiplier）方法求解2024/1/392數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM(續(xù))拉格朗日算子其中，參數(shù)

i稱為拉格朗日乘子對Lp關(guān)于w和b求偏導(dǎo)，并令它們等于零因為拉格朗日乘子

i是未知的，因此仍然不能得到w和b的解(5-38)(5-39)(5-40)2024/1/393數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM(續(xù))使用Karuch-Kuhn-Tucher（KKT）條件：

i

≥0

i

[yi(wxi+b)

1]=0

（5.42）除非訓(xùn)練實例滿足方程yi(wxi

+b)=1,否則拉格朗日乘子

i必須為零

i

>0的訓(xùn)練實例位于超平面bi1或bi2上，稱為支持向量（5.39）和（5.40）代入到公式（5.38）中這是Lp的對偶問題(最大化問題).可以使用數(shù)值計算技術(shù),如二次規(guī)劃來求解(5-43)2024/1/394數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM(續(xù))解出

i后,用(5.39)求w,再用(5.42)求b決策邊界為z可以按以下的公式來分類

如果f(z)=1，則檢驗實例z被分為到正類，否則分到負(fù)類

2024/1/395數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM:例例:二維數(shù)據(jù)集包含8個訓(xùn)練實例使用二次規(guī)劃方法,求解優(yōu)化問題LD,得到

i.w1=

iyixi1=65.526110.3858+65.5261(1)0.4871=6.64w2=

iyixi2=65.526110.4687+65.5261(1)0.611=9.32b(1)=1wx1=1(6.64)(0.3858)(9.32)(0.4687)=7.9300b(2)=1wx2=1(6.64)(0.4871)(9.32)(0.611)=7.9289b=(b(1)+b(2))/2=7.93

i2024/1/396數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM:不可分情況如果不是線性可分的，怎么辦？軟邊緣（softmargin）

允許一定訓(xùn)練誤差引入松馳變量

i其中C和k是用戶指定的參數(shù)，對誤分訓(xùn)練實例加罰

取k=1，

C根據(jù)模型在確認(rèn)集上的性能選擇2024/1/397數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM:不可分情況(續(xù))拉格朗日算子其中，前面兩項是需要最小化的目標(biāo)函數(shù)，第三項表示與松弛變量相關(guān)的不等式約束，而最后一項是要求

i的值非負(fù)的結(jié)果KKT條件

i

≥0,

i

≥0,

i

≥0

i

{yi(w

xi+b)1+

i}=0

i

i=02024/1/398數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM:不可分情況(續(xù))令L關(guān)于w,b和

i的一階導(dǎo)數(shù)為零2024/1/399數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM:不可分情況(續(xù))對偶拉格朗日問題其形式與可分情況相同,但是0≤

i≤C

2024/1/3100數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)非線性SVM使用非線性變換

例:2024/1/3101數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)非線性SVM(續(xù))非線性SVM的優(yōu)化問題約束條件:yi(w

(xi)+b)≥1,i=1,2,...,N

對偶拉格朗日問題參數(shù)w和b

2024/1/3102數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)非線性SVM(續(xù))實例z分類點積

(xi)

(xj)

計算問題能否在原空間直接計算?例:2024/1/3103數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)核技術(shù)Mercer定理:

核函數(shù)K可以表示為K(u,v)=

(u)

(v),當(dāng)且僅當(dāng)對于任意滿足g(x)2dx為有限值的函數(shù)g(x)，則K(x,y)g(x)g(y)dxdy≥0滿足定理5.1的核函數(shù)稱為正定（positivedefinite）核函數(shù)常用核函數(shù)2024/1/3104數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)SVM的特點SVM學(xué)習(xí)問題可以表示為凸優(yōu)化問題，因此可以利用已知的有效算法發(fā)現(xiàn)目標(biāo)函數(shù)的全局最小值SVM通過最大化決策邊界的邊緣來控制模型的能力需要提供其他參數(shù)，如使用的核函數(shù)類型、為了引入松弛變量所需的代價函數(shù)C等分類屬性處理每個分類屬性值引入一個啞變量,轉(zhuǎn)化為二元變量可以推廣到多類問題2024/1/3105數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)多類問題SVM是對二類問題設(shè)計的還有一些方法也是針對二類問題的如何處理多類問題?訓(xùn)練令Y={y1,y2,...,yK}是類標(biāo)號的集合1-r方法:分解成K個二類問題每一個類yi

Y創(chuàng)建一個二類問題,其中所有屬于yi的樣本都被看作正類,而其他樣本作為負(fù)類1-1方法:構(gòu)建K(K

1)/2個二類分類器每一個分類器用來區(qū)分一對類(yi,yj)為類(yi,yj)構(gòu)建二類分類器時,不屬于yi或yj的樣本被忽略掉2024/1/3106數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)多類問題(續(xù))分類投票表決票的計算1-r方法如果一個樣本被分為正類,則正類得一票如果一個樣本被分為負(fù)類,則除正類之外的所有類都得到一票1-1方法如果Cj把樣本分到y(tǒng)i類,則yi類得一票沖突處理分到多數(shù)類/少數(shù)類2024/1/3107數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)多類問題:例例:Y={y1,y2,y3,y4}1-r方法建立4個分類器設(shè)這4個分類器分別把檢驗實例x分類為+,

,

,

使用簡單的多數(shù)表決,y1得到最高的票4，而其他類僅僅得到3票,因此檢驗實例被分類為y11-1方法建立6個分類器假設(shè)它們對x如下表y1和y4都得到2票,而y2和y3僅僅得到1票二類分類器類對+：y1

：y2

+：y1

：y3

+：y1

：y4

+：y2

：y3

+：y2

：y4

+：y3

：y4

分類++

+

+2024/1/3108數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)5.6組合方法數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)一般思想聚集多個分類器的預(yù)測來提高分類準(zhǔn)確率稱為組合（ensemble）或分類器組合（classifiercombination）方法2024/1/3110數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)Whydoesitwork?假定有25基分類器每個基分類器的誤差均為

=0.35假定基分類器是獨立的組合分類器錯誤預(yù)測的概率為:2024/1/3111數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)BaggingBagging又稱自助聚集（bootstrapaggregating）訓(xùn)練階段使用自助抽樣產(chǎn)生多個訓(xùn)練數(shù)據(jù)集有放回、等概率、等容量抽樣在每個訓(xùn)練數(shù)據(jù)集上使用相同的分類算法建立基分類器分類:x是待分類實例每個基分類器獨立地對x產(chǎn)生類預(yù)測,算作一票統(tǒng)計得票,并將x指派到得票最高的類2024/1/3112數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)Boosting基本思想訓(xùn)練賦予每個訓(xùn)練記錄一個權(quán)值wi權(quán)值反映對元組分類的困難程度迭代地學(xué)習(xí)k個分類器:學(xué)習(xí)得到分類器Mi之后,更新權(quán)值,使得其后的分類器Mi+1“更關(guān)注”被Mi誤分類的訓(xùn)練元組分類:x是待分類實例每個基分類器獨立地對x產(chǎn)生類預(yù)測通過基分類器的加權(quán)投票產(chǎn)生x最終的類預(yù)測,其中每個分類器投票的權(quán)重是其準(zhǔn)確率的函數(shù)2024/1/3113數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)Adaboost一種流行的boosting方法基本思想令{(xj,yj)|j=1,2,...,N}表示包含N個訓(xùn)練樣本的集合訓(xùn)練1.每個訓(xùn)練樣本一個抽樣權(quán)重wj.初始,wj=1/N，i=12.采用有放回、等容量、加權(quán)抽樣,產(chǎn)生訓(xùn)練集,建立基分類器Ci3.計算Ci的分類誤差

i,并調(diào)整每個記錄的抽樣權(quán)重wj4.如果

i>0.5,則令wj=1/N，轉(zhuǎn)步驟25.計算Ci的重要性

i6.如果i<k，則i=i+1,轉(zhuǎn)步驟2分類1.每個Ci產(chǎn)生x的類預(yù)測Ci(x)2.組合分類器預(yù)測：2024/1/3114數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)Adaboost(續(xù))Ci的分類誤差

i基分類器Ci的重要性權(quán)值更新1.2.規(guī)范化諸wi，使得（5-68）和算法5.7的行7需要修改2024/1/3115數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)RotationForest旋轉(zhuǎn)森林(RF)使用整個訓(xùn)練數(shù)據(jù)集（不抽樣）建立多個基分類器通過不同特征變換，把數(shù)據(jù)變換到不同的新的特征空間這是真正意義下的從不同角度分析數(shù)據(jù)在不同的變換后的空間上，使用決策樹建立不同的基分類器J.J.Rodriguez,L.I.Kuncheva,C.J.Alonso,RotationForest:anewclassifierensemblemethod,IEEETrans.PatternAnal.Mach.Intell.28(2006)1619–16302024/1/3116數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)RotationForest(續(xù))訓(xùn)練建立第i個基分類器把特征集F隨機(jī)地劃分為K個不相交的子集，將訓(xùn)練數(shù)據(jù)集投影到每個特征子集上，使用PCA得到每個特征子集的主成分Tij表示到第j個特征子集的主成分的變換。這些Tij形成一個如下形式的矩陣按照特征集F中的特征次序調(diào)整Ti的諸列，得到一個特征變換矩陣，記作Ti’(XTi’,y)為訓(xùn)練數(shù)據(jù)，使用決策樹算法建立基分類器Ci2024/1/3117數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)5.7不平衡類問題數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)準(zhǔn)確率的局限性考慮一個兩類問題0類的實例數(shù)=99901類的實例數(shù)=10如果模型預(yù)測每個實例為0類,則準(zhǔn)確率為9990/10000=99.9%準(zhǔn)確率是誤導(dǎo)，因為模型不能正確預(yù)測任何1類實例2024/1/3119數(shù)據(jù)挖掘?qū)д摰?章_分類_其他技術(shù)其它度量混淆矩陣

真正率（truepositive

rate,TPR）或靈敏度（sensitivity）TPR=TP/(TP+FN)真負(fù)率（turenegative

rate,TNR）或特指度（specificity）TNR=TN/(TN+FP)假正率（falsepositiverate,FPR）FPR=FP/(TN+FP)假負(fù)率（falsenegativerate,FNR）FNR=FN/(TP+FN)

+

+

f++(TP)f

+(FP)f+

(FN)PredictedclassActualclassf

(TN)2024/1/31