研二模式識別線性判別函數(shù)

LinearDiscriminantFunctions

線性判別函數(shù)1主要內(nèi)容?引言?線性判別函數(shù)和判定面?廣義線性判別函數(shù)?兩類線性可分的情況?感知器準(zhǔn)則函數(shù)最小化?固定增量算法?最小平方誤差方法2引言?本章內(nèi)容：－假定判別函數(shù)的形式已知，而用訓(xùn)練的方法來估計(jì)判別函數(shù)的參數(shù)值－介紹各種算法?判別函數(shù)的形式：－是x的各個(gè)分量的線性函數(shù)－或者是關(guān)于以x為自變量的某些函數(shù)的線性函數(shù)3判別函數(shù)的形式x的各個(gè)分量的線性函數(shù)關(guān)于以x為自變量的某些函數(shù)的線性函數(shù)權(quán)向量：w=[w1,w2,…,wd]偏置：w04線性判別的幾何意義WHHW0||W||XXpg(X)||W||R1R2g(X)=0g(X)>0g(X)<05線性判別的幾何意義6兩類分類（1）?兩類分類的判定規(guī)則：g(x)>0判定為第一類（1）g(x)<0判定為第二類（2）g(x)=0判定為第一或二類（1/2）?系統(tǒng)實(shí)現(xiàn)結(jié)構(gòu)：7兩類分類（2）方程g(x)=0定義了一個(gè)判定面，它把兩個(gè)類的點(diǎn)分開來。當(dāng)函數(shù)是線性時(shí)，這個(gè)平面被稱為超平面。如果x1和x2都在判別面上，則8多類分類（1）（1）將C類問題分成C個(gè)兩類問題，每次把Ci類和非Ci類分開9多類分類(2)（2）將C類問題分成C(C-1)/2個(gè)兩類問題，每次把Ci類和Cj類分開10多類分類（3）由于上面的兩種方法都會產(chǎn)生無法確定類型的區(qū)域，所以需用另一種方法：–定義c個(gè)判別函數(shù)：–判定準(zhǔn)則：11多類分類（4）得到的分類器稱為“線性機(jī)”，把特征空間分為K個(gè)判定域Ri當(dāng)x在Ri中時(shí)，gi(x)有最大值12

廣義線性判別函數(shù)（1）

GeneralizedLinearDiscriminantFunctions131415兩類線性可分的情況假設(shè)有一個(gè)包含n個(gè)樣本的集合y1,y2,…yn，一些標(biāo)記為C1,另一些標(biāo)記為C2。我們希望用這些樣本來確定權(quán)向量。一個(gè)合理的想法是：尋找一個(gè)能將所有這些樣本正確分類的權(quán)向量。假如這個(gè)權(quán)向量存在，則這些樣本則是線性可分的。我們可以用一種“規(guī)范化”操作來簡化兩類樣本的訓(xùn)練過程，也就是說，對于屬于C2的樣本用負(fù)號表示。這樣，我們可以忘掉這些標(biāo)記，而尋找一個(gè)對所有樣本都有aTy>0的A。這樣的向量成為“分離向量”或者“解向量”。16Solutionregion:Fourtrainingsamples(blackforw1,redforw2)andthesolutionregioninfeaturespace.Thefigureontheleftshowstherawdata;thesolutionvectorsleadstoaplanethatseparatesthepatternsfromthetwocategories.Inthefigureontheright,theredpointshavebeen“normalized”,i.e.,changedinsign.Nowthesolutionvectorleadstoaplanethatplacesall“normalized”pointsonthesameside.17是18Basicgradientdescent19BatchPerceptron20Example有兩類的二維數(shù)據(jù)，其中第一類的兩個(gè)樣本為(1,4)t和(2,3)t，第二類的兩個(gè)樣本為(3,2)t和(4,1)t。假設(shè)初始的a=(0,1)t，n(k)=1利用批處理感知器算法求解線性判別函數(shù)g(y)=aty的權(quán)向量a。首先規(guī)范化樣本，第二類的樣本更改為：(-3,-2)t和(-4,-1)t。計(jì)算錯(cuò)分的樣本集：g(y1)=(0,1)(1,4)t=4（正確）g(y2)=(0,1)(2,3)t=3（正確）g(y3)=(0,1)(-3,-2)t=-2（錯(cuò)分）g(y1)=(0,1)(-4,-1)t=-1（錯(cuò)分）21對錯(cuò)分的樣本集求和：(-3,-2)t+(-4,-1)t=(-7,-3)t修正權(quán)向量a：a=(0,1)t+(-7,-3)t=(-7,-2)t再計(jì)算錯(cuò)分的樣本集：g(y1)=(-7,-2)(1,4)t=-15（錯(cuò)分）g(y2)=(-7,-2)(2,3)t=-20（錯(cuò)分）g(y3)=(-7,-2)(-3,-2)t=25（正確）g(y1)=(-7,-2)(-4,-1)t=30（正確）對錯(cuò)分的樣本集求和：(1,4)t+(2,3)t=(3,7)t修正權(quán)向量a：a=(-7,-2)t+(3,7)t=(-4,5)t再計(jì)算錯(cuò)分的樣本集：g(y1)=(-4,5)(1,4)t=16（正確）g(y2)=(-4,5)(2,3)t=7（正確）g(y3)=(-4,5)(-3,-2)t=2（正確）g(y1)=(-4,5)(-4,-1)t=11（正確）全部樣本正確分類，算法結(jié)束，a=(-4,5)t。22Fixed-incrementsingle-samplePerceptronconsiderthesamplesinasequenceandshallmodifytheweightvectorwheneveritmisclassifiesasinglesample.23homework有兩類的二維數(shù)據(jù)，其中第一類的兩個(gè)樣本為(1,4)t和(2,3)t，第二類的兩個(gè)樣本為(3,2)t和(4,1)t。假設(shè)初始的a=(0,1)t，利用固定增量單樣本感知器算法求解線性判別函數(shù)g(y)=aty的權(quán)向量a。2425262728有兩類的二維數(shù)據(jù)，其中第一類的兩個(gè)樣本為(1,4)t和(2,3)t，第二類的兩個(gè)樣本為(3,2)t和(4,1)t。假設(shè)裕量b=(1,1,1,1)t,試用最小平方誤差法(偽逆矩陣)求解線性判別函數(shù)g(y)=aty的權(quán)向量a。29

Fisher線性判別：

X空間

X=-WTX-W0>0X∈ω1X=-WTX-W0<0X∈ω2

映射Y空間Y=WTX-W0>0X∈ω1Y=WTX-W0<0X∈ω2把X空間各點(diǎn)投影到Y(jié)空間得一直線上，維數(shù)由2維降為一維。若適當(dāng)選擇W的方向，可以使二類分開。下面我們從數(shù)學(xué)上尋找最好的投影方向，即尋找最好的變換向量W的問題。w(y)wy1y2x2x1ω1ω230Fisher線性判別Fisher判別的基本思想：希望投影后的一維數(shù)據(jù)滿足：1兩類之間的距離盡可能遠(yuǎn)；1每一類自身盡可能緊湊。準(zhǔn)則的描述：1用投影后數(shù)據(jù)的統(tǒng)計(jì)性質(zhì)—均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn)。31i=1,2i=1,232類間散布矩陣33上式就是n維x空間向一維y空間的最好投影方向，它實(shí)際是多維空間向一維空間的一種映射。其中Sw為類內(nèi)散布矩陣,Sb為類間散布矩陣34現(xiàn)在我們已把一個(gè)n維的問題轉(zhuǎn)化為一維的問題?，F(xiàn)在一維空間設(shè)計(jì)Fisher分類器:W0的選擇

35

Yki表示第i類中第k個(gè)樣本的投影值

N1為ω1樣本數(shù)N2為ω2樣本數(shù)

當(dāng)W0選定后，對任一樣本X，只要判斷Y=WTX>0則X∈ω1;Y=WTX<0則X∈ω2。分類問題就解決了36習(xí)題已知有兩類數(shù)據(jù),分別為ω1:(1,0)T,(2,0)T,(1,1)Tω2:(-1,0)T,(0,1)T,(-1,1)T試構(gòu)造fisher線性判別函數(shù)。37決策樹用途：解決多類或多峰問題。原理：利用多個(gè)判別準(zhǔn)則將復(fù)雜的多類問題轉(zhuǎn)化為若干個(gè)單類問題。組成：一個(gè)根節(jié)點(diǎn)、一組內(nèi)節(jié)點(diǎn)和一組葉節(jié)點(diǎn)。識別方法：在內(nèi)部節(jié)點(diǎn)比較特征，特征的不同取值對應(yīng)不同分支，在葉節(jié)點(diǎn)處得到分類結(jié)果。n1n2t1t2t3a2b2b1a138決策樹構(gòu)建算法—ID3算法是以信息熵的下降速度最為特征選取標(biāo)準(zhǔn)樣本集：X={x1,x2,…,XN}，個(gè)數(shù)為N決策樹對樣本的空間劃分：R={R1,R2,…,Rm}，對應(yīng)的類別ω1,ω2,…,ωm第i類出現(xiàn)的概率P(ωi)=Ni/N，Ni：第i類的樣本數(shù)決策樹對R劃分的不確定性：H(X,R)=-∑P(ωi)logP(ωi)在學(xué)習(xí)過程中，應(yīng)使決策樹對劃分的不確定性逐漸減少。特征選取b，b={b1,b2,..bn},b=bj時(shí)，訓(xùn)練樣本屬于ωi的數(shù)量Nij，P(ωi|b=bj)=Nij/N決策樹對R劃分的不確定性：H(X|b=bj)=-∑P(ωi|b=bj)logP(ωi|b=bj)根據(jù)b的不同特征得到葉節(jié)點(diǎn)對分類的信息熵為：

H(X|b)=∑

P(b=bj)H(X|b=bj)特征b對分類的信息量I(X;b)=H(X)-H(X|b)，ID3選取I(X;b)最大分類，即H(X|b)最小。39序號OutlookTemperatureHumidityWindy類1OvercastHotHighNotN2OvercastHotHighveryN3OvercastHotHighMediumN4sunnyHotHighNotP5sunnyHotHighMediumP6RainMildHighNotN7RainMildHighMediumN8RainHotnormalNotP9RainCoolnormalMediumN10RainHotnormalveryN11sunnyCoolnormalveryP12sunnyCoolnormalMediumP13OvercastMildHighNotN14OvercastMildHighMediumN15OvercastCoolnormalNotP16OvercastCoolnormalMediumP17RainMildnormalNotN18RainMildnormalMediumN19OvercastMildnormalMediumP20OvercastMildnormalveryP21sunnyMildHighveryP22sunnyMildHighMediumP23sunnyhotnormalNotP24RainMildHighveryNH(X)=-12/24lb12/24-12/24lb12/24=1選屬性特征分類H(X|Outlook)=9/24(-4/9lb4/9-5/9lb5/9)+8/24((-1/8lb1/8-7/8lb7/8)+7/24((-7/7lb7/7)=0.5528H(X|Temperature)=8/24(-4/8lb4/8-4/8lb4/8)+11/24((-4/11lb4/11-7/11lb7/11)+5/24((-4/5lb4/5-1/5lb1/5)=0.6739H(X|Humidity)=12/24(-4/12lb4/12-8/12lb8/12)+12/24((-4/12lb4/12-12lb8/1