模式識別復(fù)習(xí)題

1、精品1、模式識別系統(tǒng)的基本構(gòu)成單元，并對各單元簡要解釋?數(shù)據(jù)獲?。河糜?jì)算機(jī)可以運(yùn)算的符號來表示所研究的對象- 二維圖像：文字、指紋、地圖、照片等- 一維波形：腦電圖、心電圖、季節(jié)震動波形等- 物理參量和邏輯值：體溫、化驗(yàn)數(shù)據(jù)、參量正常與否的描述?預(yù)處理單元：去噪聲，提取有用信息，并對輸入測量儀器或其它因素所造成的退化現(xiàn)象進(jìn)行復(fù)原?特征提取和選擇：對原始數(shù)據(jù)進(jìn)行變換，得到最能反映分類本質(zhì)的特征- 測量空間：原始數(shù)據(jù)組成的空間- 特征空間：分類識別賴以進(jìn)行的空間- 模式表示：維數(shù)較高的測量空間，維數(shù)較低的特征空間?分類決策：在特征空間中用模式識別方法把被識別對象歸為某一類別- 基本做法：在樣本訓(xùn)練

2、集基礎(chǔ)上確定某個判決規(guī)則，使得按這種規(guī)則對被識別對象進(jìn)行分類所造成的錯誤識別率最小或引起的損失最小2、寫出K-均值聚類算法的基本步驟,例子見布置的作業(yè)題.算法：第一步：選K個初始聚類中心,zi（1）,Z2（1）,ZK（1）,其中括號內(nèi)的序號為尋找聚類中心的迭代運(yùn)算的次序號。聚類中心的向量值可任意設(shè)定，例如可選開始的K個模式樣本的向量值作為初始聚類中心。第二步：逐個將需分類的模式樣本x按最小距離準(zhǔn)則分配給K個聚類中心中的某一個Zj(1)。假設(shè)i=j時(shí)，Dj(k)=min乂-Zi(k)|,i=1,2,K,則xeSj(k),其中k為迭代運(yùn)算的次序號，第一次迭代k=i,Sj表示第j個聚類，具聚類中心為

3、Zjo第三步：計(jì)算各個聚類中心的新的向量值，Zj(k+1),j=1,2,叢1Zj(k1)x,j=1,2,|,KNjxSj(k)求各聚類域中所包含樣本的均值向量：Jj=Z|x-Zj(k+1,j=1,2J|,Kx。(k)其中Nj為第j個聚類域Sj中所包含的樣本個數(shù)。以均值向量作為新的聚類中心，可使如下聚類準(zhǔn)則函數(shù)最?。涸谶@一步中要分別計(jì)算K個聚類中的樣本均值向量，所以稱之為K-均值算法。第四步：若Zj(k+1)#Zj(k),j=1,2,K,則返回第二步，將模式樣本逐個重新分類，重復(fù)迭代運(yùn)算；若Zj(k+1)=Zj(k),j=1,2,K,則算法收斂，計(jì)算結(jié)束。例子：已知x1(0,0),x2(1,0)

4、,x3(0,1),x4(1,1),x5(2,1),x6(1,2),x7(2,2),x8(3,2),x9(6,6),x10(7,6),x11(8,6),x12(6,7),x13(7,7),x14(8,7),x15(9,7)x16(7,8),x17(8,8),x18(9,8),x19(8,9),x20(9,9),用K-均值算法進(jìn)行聚類分析解：選k=2,Zi=x1，Z2=x10,弟一步：選取4(1)=為=,Z2(1)=x|0第二步：根據(jù)聚類中心進(jìn)行聚類，得到§(1尸%？2,%?4?5,%?7,)<85(1)=x9,xl0,x11,x12,Ulx20第三步：計(jì)算新的聚類中心感謝下載載1

5、11.2500z1Fx；1)X=8(X1X2用X8)=1.125011,、z2="7xx=X9(x9X10|11x20)=N2XS2(1)1276667、Q.3333,第四步：因Zj(2)#Zj(1),j=1,2,故回到第二步第二步：根據(jù)新的聚類中心重新進(jìn)行聚類，得到S(2)-Xl,X2,X3,X4,X5,X6,X7,X8S2(2)-X9,X10，X11,X12，HIX20第三步：計(jì)算新的聚類中心Z1(3)=x.1,J1.2500X(X1X2IX8)=X02)81.1250一1一1.Z2Fx；(2)X=7X9X10用rd7.6667。3333第四步：Zj(3)=Zj(2),j=1,2

6、,所以算法收斂，得聚類中心為7.2500)7.6667),z2=1.1250；27.3333)迭代結(jié)束3、最、剪輯、壓縮近鄰法的基本思想最近鄰法的基本思想：以全部訓(xùn)練樣本作為“代表點(diǎn)”，計(jì)算測試樣本與這些“代表點(diǎn)”，即所有樣本的距離，并以最近鄰者的類別作為決策。剪輯近鄰法基本思想是，利用現(xiàn)有樣本集對其自身進(jìn)行剪輯，將不同類別交界處的樣本以適當(dāng)方式篩選，可以實(shí)現(xiàn)既減少樣本數(shù)又提高正確識別率的雙重目的。壓縮近鄰法：利用現(xiàn)有樣本集，逐漸生成一個新的樣本集，使該樣本集在保留最少量樣本的條件下，仍能對原有樣本的全部用最近鄰法正確分類，那末該樣本集也就能對待識別樣本進(jìn)行分類，并保持正常識別率4、設(shè)有6個5

7、維模式樣本如下，按最小/大距離準(zhǔn)則進(jìn)行聚類分析(直到分成三個類別為止，距離度量采用歐氏距離）XI：0,3,1,2,0X2：1,3,0,1,0X3：3,3,0,0,1X4：1,1,0,2,0X5：3,2,1,2,1X6：4,1,1,1,0按最大距離準(zhǔn)則進(jìn)行聚類分析：第1步：將每一樣本看成單獨(dú)一類，得G=X,G20）=X2,G3=%g40）=M,G50）=X5,g60）=%計(jì)算各類之間的歐式距離，可得距離矩陣Dc(0)g1N。）G2g30)（0）G4N。）G5c(0)G6G10（0）G2百0g30)85娓0（0）G47T30g50)后向巡V70g60)后R4顯440第2步：矩陣D（0）中最大元素為

8、而,它是G1（0）和g60）之間的距離，將他們合并為一個新類為G1=G1(0),g60),g2Jg20),g3Jg30),g4Jg40),gETg?計(jì)算聚類后的距離矩陣DG1G21)G31)G;G51)G10CG2JT40G31)760CG4忌而0G51)布8abV60第3步：由于D中距離最大者為布，它是G，與G：之間的距離，于是合并Gi和G31),得新的分類為g2)=Gi,g,g22)=g2。,g32)=gJ,g42)=g5。同樣，按最大距離準(zhǔn)則計(jì)算距離矩陣D，得G1(2)g22)g32)g42)G10g22)而0g32)而*0g42)而60第4步：由于D中距離最大者為714,它是Gi與G2

9、之間的距離，于是合并得新的分類為g)=Gi(2),g22),g23)=g32),g33)=g42)滿足聚類要求，如聚為3類，聚類完畢。5、設(shè)有5個6維模式樣本如下，按最小/大距離準(zhǔn)則進(jìn)行聚類分析(距離度量采用歐氏距離)XI：0,1,3,1,3,4X2：3,3,3,1,2,1X3：1,0,0,0,1,1X4：2,1,0,2,2,1X5：0,0,1,0,1,0用最小聚類準(zhǔn)則進(jìn)行系統(tǒng)聚類分析：第1步：將每一樣本看成單獨(dú)一類，得G1（0）=X1,G20）=X2,G30）=X3G40）=X4,G5°）=X5計(jì)算各類之間的歐式距離，可得距離矩陣DG1(0)G;)g30)g40)GFGE0（0）G

10、2扃0g30)后0（0）G4而VT5萬0g50)病出丘0第2步：矩陣D中最小元素為V3,它是630）和650）之間的距離，將他們合并為一類，得新的分類為G1-G1,G2-G2,G3-G37G5）,G4-G4計(jì)算聚類后的距離矩陣DG：G21)G31)G41)G10G21)V230G31)瘍V240CG47240第3步：由于D中距離最小者為"，它是g30與G9之間的距離，于是合并G31)和Gf),得新的分類為Gi=Gi,g22)=G22),g32)XG,Gf)同樣，按最小距離準(zhǔn)則計(jì)算距離矩陣D，得g；2)g22)g32)G1(2)0g22)0g32)聲壓0第4步：同理得gF=Gi(2),

11、g23)=g22),g32)滿足聚類要求，如聚為2類，聚類完畢。6、一個三類問題，其判別函數(shù)如下：di(x)=-x1,d2(x)=x1+X2-I,d3(X)=X1-x2-1設(shè)這些函數(shù)是在多類情況1條件下確定的。1)繪出其判別界面和每一個模式類別的區(qū)域。2)對如下三個樣本所屬模式作出判決：A=(45)T，B=(-25)T，C=(2-5)T例子：一個三類問題，其判別函數(shù)如下：d1(x)=-x1,d2(x)=x1+x2-1,d3(x)=x1-x2-11、設(shè)這些函數(shù)是在多類情況1條件下確定的，繪出其判別界面和每一個模式類別的區(qū)域。2、設(shè)為多類情況2,并使：d12(x)=d1(x),d13(x)=d2(

12、x),d23(x)=d3(x)繪出其判別界面和多類情況2的區(qū)域。繪出其判別界面3、設(shè)d1(x),d2(x)和d3(x)是在多類情況3的條件下確定的,和每類的區(qū)域d t(x)- xl0謔類判冽修乂4 域x2 L。d2(x)<0d：4(x)>0解：(1)其判別界面和每一個模式類別的區(qū)域如圖中所示:A=(45)T屬于，B=(-25)T屬于不確定區(qū)域，C=(2-5)T屬于a(2)其判別界面和每一個模式類別的區(qū)域如圖中所示:dL2(x)=d2L(i)=il=O為+門類判別區(qū)域dl2 (i) >013(r)>0dL3(x)為 +心靈判別區(qū) 域 d(x)X) d；n(x)>od

13、ZLOc)為 4J Ld23(x)=d32(i)=xl-x21=0眠(Ji)為捌;()為+起類判別區(qū)域md23(x)>0dn(x) 一(m3 ii+x2-i-o(3)其判別界面和每一個模式類別的區(qū)域如圖中所示:7、已知：u: X1, X2=(1 0 1) T, (0 1 1)T,W2： X3, X4=(1 1 0) T, (0 1 0)T。給定初始增廣權(quán)向量W1= (1 1 1 1) T ,C=1 。要求：1)用感知器算法求模式分類的解向量2)寫出判別函數(shù)和決策面方程。解：先求四個樣本的增值模式xi=(1,0,1,1) TX2 = (0,1,1,1) T的>0X3=(1,1,0,1

14、)TX4=(0,1,0,1)T假設(shè)初始權(quán)向量第一次迭代：W1TX1=(1,1,1,1)W1TX2=(1,1,1,1)W1TX3=(1,1,1,1)W1=(1,1,1,1) TT (1,0,1,1)=3>0T (0,1,1,1)=3>0T (1,1,0,1)=3>0C=1所以不修正所以不修正所以彳QEw1W2=W1-X3=(0,0,1,0)TW2TX4=(0,0,1,0)T(0,1,0,1)=0所以彳正W2第一次迭代后，權(quán)向量W3 = (0,-1,1,-1)T,再進(jìn)行第2,3，次迭代如下表:W3=W2-X4=(0,-1,1,-1)T訓(xùn)練樣本wkTx修正式修正后的權(quán)值WRI迭代次

15、數(shù)對1011+W11111Xj0111+W111111均1101+Wi-/0010x401010011-1峋101101-120Xj0111+W41-1102均11010Wf0-22-1x40101JW50-22：1Xi1011+W50-22-1Xj0111-W5+迫0-1303x31101-w.0-130x40101-w.0-130峋1011+0-130Xj0111+w.0-1304x31101-w.0-130x40101-%0-130直到在一個迭代過程中權(quán)向量相同，訓(xùn)練結(jié)束W6=W=(0,-1,3,0)判別函數(shù)gX=-X23X3決策面方程：g(x)=x2+3x3=0即X2-3X3=08、已

16、知：wi:Xi=(0,2)T,X3=(2,0)T,X5=(-1,-1)T2：X2=(1,1)T,X4=(0,-2)T,X6=(-2,0)T給定初始增廣權(quán)向量W1=(111)T,C=1。要求：用感知器算法求模式分類的解向量Wo解：此為線性不可分問題，利用感知器法求權(quán)向量權(quán)向量產(chǎn)生循環(huán)(1,1,1)T,(0,0,0)T,(2,0,1)T,(2,2,0)T,(1,1,1)T因此算法不收斂，我們可以取循環(huán)中任一權(quán)值，例如取W=(2,2,0)T則判別函數(shù)為：g(x)=2x1+2x2判別面方程為：g(x)=2x1+2x2=0所以：x1+x2=0由圖看出判別面H把二類分開，但其中x2錯分到1類，而x1錯分到

17、2類，但大部分分類還是正確的。9、對一大批人進(jìn)行癌癥普查，患癌者以3類代表，正常人以2類代表。已知P(1)=0.005,當(dāng)然P(2)=1-0.005=0.995.設(shè)有一種診斷癌癥的試驗(yàn)，其結(jié)果為“陽性”和“陰性”兩種反應(yīng)。假設(shè)根據(jù)臨床記錄發(fā)現(xiàn)這種方法有以下統(tǒng)計(jì)結(jié)果：患有癌癥的人試驗(yàn)反應(yīng)為陽性的概率=0.95,即p(x=陽|n)=0.95患有癌癥的人試驗(yàn)反應(yīng)為陰性的概率=0.05,即p(x=陰|3)=0.05正常人試驗(yàn)反應(yīng)為陽性的概率=0.01,即p(x=陽|32)=0.01精品正常人試驗(yàn)反應(yīng)為陰性的概率=0.99,即p（x二陰|32）=0.99問：若被化驗(yàn)的人具有陽性反應(yīng)，他患癌癥的概率為多少

18、?解:p但 I x=ro)=P（x=陽|孫尸（叫）P(xdH )P (x=陽|斜)P (斜)感謝下載載P(x=K|©1)P(©1)+P(x=W|02)P(s2)0.950.005八=0.3230.950.0050.010.995因?yàn)?，P(W2|x=陽尸1-P(wi|x=陽)=1-0.323=0.677P(wi|x=陽)<P(w2|x=陽)故判決：正常10、已知P(i)=0.9,P(2)=0.1,p(x|1)=0.2,p(x|2)=0.4。且有如下決策表：損失狀態(tài)決策312o106c210請按最小風(fēng)險(xiǎn)貝葉斯決策進(jìn)行分類解：已知條件為P(1)=0.9,P(2)=0.1,p

19、(x|1)=0.2,p(x|2)=0.4。11=0,12=6,21=1,22=0利用貝葉斯公式分別計(jì)算出1及2的后驗(yàn)概率P|x = 0.818Px|1P1_0.20.9Px11PlPx|2P20.20.90.40.1再計(jì)算條件風(fēng)險(xiǎn)：R：1|x=v-ijP-j|x=-12P.2|x,>1.0922jIR22x八2jPj|x=21P-1|x=0.818j1由于RO|x>R(%|x)即決策為2的條件風(fēng)險(xiǎn)小于決策為1的條件風(fēng)險(xiǎn)，因此我們采取決策行動«2,即判斷待識別的細(xì)胞x為2類一一異常細(xì)胞。11、設(shè)有如下三類模式樣本集CD1,2和3,其先驗(yàn)概率相等，求Sw和Sb1:(10)T,

20、(20)T,(11)T2:(-10)T,(01)T,(-11)T3:(-1-1)T,(0-1)T,(0-2)T解：由于本題中有三類模式，因此我們利用下面的公式：3Sb=zP(M)(mi-m0)(mi-m。);m0為C類模式分布總體的均值向量i工3即：m0=Ex-7p(i)mii1mi為第i類樣本樣本均值m11 12 13 |tp0 1m221 -1 +0 -1 23 10+1 +12<3 )1 -10 0m3 二3 |L-1 -1-2J -3 _4 3,m0=1 3 -33 1 .2 I _331343,19193Sb1 - P( 'i)(mi -m0)(mi -m°)

21、t i 471)J 4 19 ")7 7)41+ 一9 id9j 7 |l 9【94 4)7K -9 上9j 11 |l 9 < 944 ；4949 Z1681+8181+811649494481 J1 8181 )<81一1218144A814481 12162 1381 8113 6281 人 181 81J一一t1-11-(i)(i)TSw=P(i)*E(x-mi)(x-mi)/=-G=；(xk()-mii)(xk()-m。i13T33kd-62712試用感知器算法實(shí)現(xiàn)邏輯與”、“或系數(shù)自己設(shè)定）一、用感知器算法實(shí)現(xiàn)邏輯“與”功能真值表：x1x2T00-1(0)01

22、-1(0)10-1(0)111設(shè)8=0.05,"=0.02,叫=0.058,820=0.05,轉(zhuǎn)移函數(shù)為符號函數(shù)(1) (0)(1)(0)一S1Xi1X22-1=0+0-0.05=-0.05y=sgns()=-1、1=工-y-1-(-1)=0則有孫=0.058,©21)=0.05(2) (1)(2)(1)一S2=X'1x2/一1(2) =0+0.05-0.05=0y2=sgns(2)-1、2=丁2-丫2=T-(-1)=0則有仍，=0.058,022)=0.05功能。(初始加權(quán)值、閾值和訓(xùn)練速率(3) (2)(3)(2).S3=X1.，1X22=0.058+0-0.0

23、5=0.008y=sgns(3)=1Q3=T3-y3=-11=-2貝U有1(3)=0.0580.02(-2)1=0.023)=0.050.02(-2)0-0.05(4)(3)(4)(3)一S4=x1,1X212-(4) =0.018+0.05-0.05=0.018y4=sgns4)=14=T4-y4=1-1=0(4)(4)_則有必=0.018,02=0.05重復(fù)上述(1)(4)缶1(0)=81(4)=0.018,'20)=黃=0.05s1=X(1"0)WP0)”(5) =0+0-0.05=-0.05y1=sgn4)-1、1=工-y1=-1-(-1)=0則有孫(1)=0.018

24、,821)=0.05仍設(shè)日=0.05, "=0.02,81(0) =0.058,-0ov(2).(1),J2)(1)rS2X.1X2v2-二(6) =0+0.050.05=0y2=sgns(2)=-1、.2=t2_y2=7_(_1)=0則有仍，=0.018,co22)=0.05(3)(2)(3)(2)tS3=X'1x22-=0.018+0-0.05=-0.032y3=sgnsG)=-1。3=丁3-'丫3-1-'(7)-0則有以(3)=0.018,©23)=0.05820)=0.05,轉(zhuǎn)移函數(shù)為符號函數(shù)(1) (0)(1)(0)Si=整.,1X22=0

25、0-0.05-0.05y1=sgn4)=1、.1=T1-y1=一1一(一1)=0則有81(1)=0.058,821)=0.05c_J2)(1),J2)(1)rS2X111X21-2-(2) =00.05-0.05=0C_J4)(3),J4)(3)TS4-X11-1X2,-2-1(8)=0.018+0.05-0.05=0.018y4=sgnS4)二14=t4-y4=1-1=0則有以(4)=0.018,024)=0.05最后所得加權(quán)值為叫=0.018,。2=0.05y=sgn4)=-12=T2-y2=1-(-1)=2則有1(2)=0.0580.0220=0.058(2)2=0.050.0221=0

26、.09(3) (2)(3)(2).Ss-X1'1X22"-=0.05800.05=0.008二、用感知器算法實(shí)現(xiàn)邏輯“或”功能y3=sgnS3)=1真值表:'3=丁3一丫3=1一1=0x1x2T則有切，=0.058,切23)=0.09-1(0)S4=x(4),f,X4)，田(4)=0.0580.09-0.05=0.0981y4=sgns(4)=111=t4-y4=1-1=01=0.09則有孫(4)=0.058,切24)重復(fù)上述（1）（4）,(0)_1(4).1二'1二0.058,20)=,24)=0.09(1) (0)(1)(0).Si=Xi1.X2，2-uo

27、O0-0.05-0.05y=sgns1)=-1-1=T)y1=-1(1)=0則有01(1)=0.058,©21)=0.09S2=X1(2),1(1)W).U(9)=0+0.09-0.05=0.04y2=sgns2)=1則有切1(2)=0.058,822)=0.09(3) (2)(3)(2)s3=x1，1X22-(10)=0.058+00.05=0.008y3-sgns3)=1:3=T3-y3=1-'1-0則有以(3)=0.058,023)=0.09(4) (3)(4)(3)一s4=x1,，1X22_1(11)=0.058+0.09-0.05=0.098y4=sgns4)-1二

28、4=T4-y4=1-1=0則有期(4)=0.058,。24)=0.09最后所得加權(quán)值為81=0.058,82=0.09、2=丁2-y2=1-1=013.掌握BP算法.前饋與反饋網(wǎng)絡(luò)結(jié)構(gòu)與訓(xùn)練過程BP訓(xùn)練算法實(shí)現(xiàn)步驟m0準(zhǔn)備：訓(xùn)練數(shù)據(jù)組。設(shè)網(wǎng)絡(luò)具有m層，yj表示第m層中第j個結(jié)點(diǎn)的輸出，yj（零層輸.m.mJ.m、一.一出）等于Xj,即第j個輸入。Wij表布從V、到y(tǒng)j的連接加權(quán)。這里，m代表層號，而不是向量的類號。1,將各加權(quán)隨機(jī)置為小的隨機(jī)數(shù)?？捎镁鶆蚍植嫉碾S機(jī)數(shù)，以保證網(wǎng)絡(luò)不被大的加權(quán)值所飽和。2,從訓(xùn)練數(shù)據(jù)組中選一數(shù)據(jù)對（Xk,Tk）,將輸入向量加到輸入層（m=0）,使得對所有0k漏點(diǎn)i

29、：y、=X、，k表不向重類3mmm.mM3.信號通過網(wǎng)絡(luò)向前傳播，即利用關(guān)系式：yjF（Sj）F（乙wjy、）i計(jì)算從第一層開始的各層內(nèi)每個結(jié)點(diǎn)、的輸出ymm,直到輸出層的每個結(jié)點(diǎn)的輸出計(jì)算完為止。4,計(jì)算輸出層每個結(jié)點(diǎn)的誤差值（利用公式（1）3jm=F（Sjm）（Tjkym）=y：（1y：）（T；y：）（對Sigmod函數(shù)）它是由實(shí)際輸出和要求目標(biāo)值之差獲得。5.計(jì)算前面各層各結(jié)點(diǎn)的誤差值（利用公式（2）-m-1m-1mjF（sj）._wji-:i這里逐層計(jì)算反傳誤差，直到將每層內(nèi)每個結(jié)點(diǎn)的誤差值算出為止。6 .利用加權(quán)修正公式mv-mm、,knew01dWij=為yi和關(guān)系wij=Wij+AWj修正所有連接權(quán)。一般0.011,稱為訓(xùn)練速率系數(shù)。7 .返回第2步，為下一個輸入向量重復(fù)上述步驟，直至網(wǎng)絡(luò)收斂。（2）前饋網(wǎng)絡(luò)通過許多具有簡單處理能力的神經(jīng)元的復(fù)合作用，使整個網(wǎng)絡(luò)具有復(fù)雜的非線性映射能力。反饋網(wǎng)絡(luò)通過網(wǎng)絡(luò)神經(jīng)元狀態(tài)的變遷，最終穩(wěn)定于某一狀態(tài)，得到聯(lián)想存儲或神經(jīng)計(jì)算的結(jié)果。感知器訓(xùn)練算法準(zhǔn)備：收集一組訓(xùn)練對，即一組輸入向量，其中每個都有一個對應(yīng)的目標(biāo)向量。輸入：二進(jìn)制值或連續(xù)值