(完整版)中科院-模式識(shí)別考題總結(jié)(詳細(xì)答案)

簡(jiǎn)述模式的概念及其直觀特性，模式識(shí)別的分類，有哪幾種方法。（6’）答（1）:什么是模式？廣義地說(shuō)，存在于時(shí)間和空間中可觀察的物體，如果我們可以區(qū)別它們是否相同或是否相似，都可以稱之為模式。模式所指的不是事物本身，而是從事物獲得的信息，因此，模式往往表現(xiàn)為具有時(shí)間和空間分布的信息。模式的直觀特性：可觀察性；可區(qū)分性；相似性。答（2）：模式識(shí)別的分類：假說(shuō)的兩種獲得方法（模式識(shí)別進(jìn)行學(xué)習(xí)的兩種方法）：監(jiān)督學(xué)習(xí)、概念驅(qū)動(dòng)或歸納假說(shuō);非監(jiān)督學(xué)習(xí)、數(shù)據(jù)驅(qū)動(dòng)或演繹假說(shuō)。模式分類的主要方法：數(shù)據(jù)聚類:用某種相似性度量的方法將原始數(shù)據(jù)組織成有意義的和有用的各種數(shù)據(jù)集。是一種非監(jiān)督學(xué)習(xí)的方法，解決方案是數(shù)據(jù)驅(qū)動(dòng)的。統(tǒng)計(jì)分類：基于概率統(tǒng)計(jì)模型得到各類別的特征向量的分布，以取得分類的方法。特征向量分布的獲得是基于一個(gè)類別已知的訓(xùn)練樣本集。是一種監(jiān)督分類的方法，分類器是概念驅(qū)動(dòng)的。結(jié)構(gòu)模式識(shí)別:該方法通過(guò)考慮識(shí)別對(duì)象的各部分之間的聯(lián)系來(lái)達(dá)到識(shí)別分類的目的。（句法模式識(shí)別）神經(jīng)網(wǎng)絡(luò):由一系列互相聯(lián)系的、相同的單元（神經(jīng)元）組成。相互間的聯(lián)系可以在不同的神經(jīng)元之間傳遞增強(qiáng)或抑制信號(hào)。增強(qiáng)或抑制是通過(guò)調(diào)整神經(jīng)元相互間聯(lián)系的權(quán)重系數(shù)來(lái)（weight）實(shí)現(xiàn)。神經(jīng)網(wǎng)絡(luò)可以實(shí)現(xiàn)監(jiān)督和非監(jiān)督學(xué)習(xí)條件下的分類。什么是神經(jīng)網(wǎng)絡(luò)？有什么主要特點(diǎn)？選擇神經(jīng)網(wǎng)絡(luò)模式應(yīng)該考慮什么因素？（8’）答（1）：所謂人工神經(jīng)網(wǎng)絡(luò)就是基于模仿生物大腦的結(jié)構(gòu)和功能而構(gòu)成的一種信息處理系統(tǒng)（計(jì)算機(jī)）。由于我們建立的信息處理系統(tǒng)實(shí)際上是模仿生理神經(jīng)網(wǎng)絡(luò)，因此稱它為人工神經(jīng)網(wǎng)絡(luò)。這種網(wǎng)絡(luò)依靠系統(tǒng)的復(fù)雜程度，通過(guò)調(diào)整內(nèi)部大量節(jié)點(diǎn)之間相互連接的關(guān)系，從而達(dá)到處理信息的目的。人工神經(jīng)網(wǎng)絡(luò)的兩種操作過(guò)程：訓(xùn)練學(xué)習(xí)、正常操作（回憶操作）。答（2）：人工神經(jīng)網(wǎng)絡(luò)的特點(diǎn)：固有的并行結(jié)構(gòu)和并行處理；知識(shí)的分布存儲(chǔ)；有較強(qiáng)的容錯(cuò)性；有一定的自適應(yīng)性；人工神經(jīng)網(wǎng)絡(luò)的局限性：人工神經(jīng)網(wǎng)絡(luò)不適于高精度的計(jì)算；人工神經(jīng)網(wǎng)絡(luò)不適于做類似順序計(jì)數(shù)的工作；人工神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)和訓(xùn)練往往是一個(gè)艱難的過(guò)程；人工神經(jīng)網(wǎng)絡(luò)必須克服時(shí)間域順序處理方面的困難；硬件限制；正確的訓(xùn)練數(shù)據(jù)的收集。答（3）：選取人工神經(jīng)網(wǎng)絡(luò)模型，要基于應(yīng)用的要求和人工神經(jīng)網(wǎng)絡(luò)模型的能力間的匹配，主要考慮因素包括：網(wǎng)絡(luò)大?。凰栎敵鲱愋?；聯(lián)想記憶類型；訓(xùn)練方法；時(shí)間的限定。畫出句法模式識(shí)別的框圖，并解釋其工作原理。（8’）答（1）：句法模式識(shí)別框圖如下：分類結(jié)果輸入圖像星兀和大系訓(xùn)練模式樣本識(shí)別和描述模式表述*分別或分解基元及其美?系識(shí)我分類結(jié)果輸入圖像星兀和大系訓(xùn)練模式樣本識(shí)別和描述模式表述*分別或分解基元及其美?系識(shí)我文法或結(jié)構(gòu)推斷句法或結(jié)構(gòu)分析圖像預(yù)處理答（2）：句法模式識(shí)別系統(tǒng)的組成：圖像預(yù)處理，圖像分割，基元及其關(guān)系識(shí)別，句法分析?；诿枋瞿Ｊ降慕Y(jié)構(gòu)信息，用形式語(yǔ)言中的規(guī)則進(jìn)行分類，可以更典型地應(yīng)用于景物圖片的分析。因?yàn)樵谶@類問(wèn)題中，所研究的模式通常十分復(fù)雜，需要的特征也很多，僅用數(shù)值上的特征不足以反映它們的類別。句法模式識(shí)別系統(tǒng)處理過(guò)程：基元本身包含的結(jié)構(gòu)信息已不多，僅需少量特征即可識(shí)別。如果用有限個(gè)字符代表不同的基元，則由基元按一定結(jié)構(gòu)關(guān)系組成的子圖或圖形可以用一個(gè)有序的字符串來(lái)代表。假如事先用形式語(yǔ)言的規(guī)則從字符串中推斷出能生成它的文法，則可以通過(guò)句法分析，按給定的句法（文法）來(lái)辨識(shí)由基元字符組成的句子，從而判別它是否屬于由該給定文法所能描述的模式類，達(dá)到分類的目的。（1）解釋線性判別函數(shù)進(jìn)行模式分類的概念；（2）既然有了線性判別函數(shù)，為什么還要用非線性判別函數(shù)進(jìn)行模式分類？（3）兩類模式，每類包括5個(gè)3維不同的模式，且良好分布。如果它們是線性可分的，問(wèn)權(quán)向量至少需要幾個(gè)系數(shù)分量？假如要建立二次的多項(xiàng)式判別函數(shù)，又至少需要幾個(gè)系數(shù)分量？（設(shè)模式的良好分布不因模式變化而改變。）（8’）答（1）：模式識(shí)別系統(tǒng)的主要作用是判別各個(gè)模式所屬的類別。線性判別函數(shù)分類就是使用線性判別函數(shù)將多類樣本模式分開(kāi)。一個(gè)n維線性判別函數(shù)的一般形式：d（X）=Wx+Wx++WX+w=wrx+w1122nnn+l0n+l其中W=（W,W，…,W）T稱為權(quán)向量（或參數(shù)向量），X=（X,X，…,X）T。012n12n???d（x）也可表示為：d（x）=WTX其中，X=（X,X,...,X,1）T稱為增廣模式向量，W=（W,W,...,W,W）T稱為增廣權(quán)12n012nn+1

向量。兩類情況：判別函數(shù)d(x)：[>0ifxw3d(x)=wtx=<1[V0ifxw32多類情況：設(shè)模式可分成3，3，…，①共M類，則有三種劃分方法：12M?多類情況11>0d(x)1>0d(x)=wtx=<ii[V0ifxG3iifx任3i這種情況稱為3/3兩分法，即把M類多類問(wèn)題分成M個(gè)兩類問(wèn)題，因此共有M個(gè)ii判別函數(shù)，對(duì)應(yīng)的判別函數(shù)的權(quán)向量為w,i=1,2，…,n+1。i多類情況2采用每對(duì)劃分，即3|3兩分法，此時(shí)一個(gè)判別界面只能分開(kāi)兩種類別，但不能把它ij與其余所有的界面分開(kāi)。TOC\o"1-5"\h\z其判別函數(shù)為：d(x)=WTx若d(x)>0，的?中i，則xG3ijijiji重要性質(zhì)：d二-diji要分開(kāi)M類模式，共需M(M-1)/2個(gè)判另IJ函數(shù)。不確定區(qū)域：若所有d(x)，找不到刃?豐i，d(x)>0的情況。ijij多類情況3(多類情況2的特例)這是沒(méi)有不確定區(qū)域的313兩分法。假若多類情況2中的d可分解成：ijijd(x)=d(x)一d(x)=(w一w)Tx，則d>0相當(dāng)于d(x)>d(x)，Vj,豐i。這時(shí)ijijijijij不存在不確定區(qū)域。此時(shí)，對(duì)M類情況應(yīng)有M個(gè)判別函數(shù)：d(x)=wtx,k=1,2,,Mkk即d(x)>d(x)，Vj'豐i，i,j=1,2,...M，則xG3，也可寫成，若iji???d(x)=max{d(x),k=1,2,...,M}，則xG3。iki該分類的特點(diǎn)是把M類情況分成M-1個(gè)兩類問(wèn)題。模式分類若可用任一個(gè)線性函數(shù)來(lái)劃分，則這些模式就稱為線性可分的，否則就是非線性可分的。一旦線性函數(shù)的系數(shù)wk被確定，這些函數(shù)就可用作模式分類的基礎(chǔ)。對(duì)于M類模式的分類，多類情況1需要M個(gè)判別函數(shù)，而多類情況2需要M*(M-1)/2個(gè)判別函數(shù)，當(dāng)M較大時(shí)，后者需要更多的判別式(這是多類情況2的一個(gè)缺點(diǎn))。采用多類情況1時(shí)，每一個(gè)判別函數(shù)都要把一種類別的模式與其余M-1種類別的模式分開(kāi)，而不是將一種類別的模式僅與另一種類別的模式分開(kāi)。由于一種模式的分布要比M-1種模式的分布更為聚集，因此多類情況2對(duì)模式是線性可分的可能性比多類情況1更大一些(這是多類情況2的一個(gè)優(yōu)點(diǎn))。答(2)廣義線性判別函數(shù)出發(fā)點(diǎn)：線性判別函數(shù)簡(jiǎn)單，容易實(shí)現(xiàn)；非線性判別函數(shù)復(fù)雜，不容易實(shí)現(xiàn)；若能將非線性判別函數(shù)轉(zhuǎn)換為線性判別函數(shù)，則有利于模式分類的實(shí)現(xiàn)。采用廣義線性判別函數(shù)的概念，可以通過(guò)增加維數(shù)來(lái)得到線性判別，但維數(shù)的大量增加會(huì)使在低維空間里在解析和計(jì)算上行得通的方法在高維空間遇到困難，增加計(jì)算的復(fù)雜性。所以某些情況下使用非線性判別函數(shù)或分段線性判別函數(shù)效果更好。解(3)假設(shè)該兩類模式是線性可分的，則在三維空間中一個(gè)線性平面可以將這兩類模式分開(kāi)，所以判別函數(shù)可以寫成：d(x)=wx+wx+wx+w1234所以權(quán)向量需要4個(gè)系數(shù)。對(duì)于n維x向量，采用r次多項(xiàng)式，d(x)的權(quán)系數(shù)w的項(xiàng)數(shù)為:(n+r)!

r!n!當(dāng)r=2，n=3時(shí)，TOC\o"1-5"\h\z3二(n+2)(n+1)二io

2!n!2所以，此時(shí)權(quán)向量需要10個(gè)系數(shù)分量。5.設(shè)一有限態(tài)自動(dòng)機(jī)A=({0,1},{q,q,q},8,q,q}，8定義如下:012028(q,0)=q,8(q,0)=q,8(q,0)=q0212228(q,1)=q,8(q,1)=q,8(q,1)=q011021試求等價(jià)的正則文法，使得L(G)=T(A)。(10’)解：設(shè)由A得一正則文法G=(V,V,P，S),則V={S,x,x},V={0,1},S=qTOC\o"1-5"\h\zNTN12T0由b(q,1)=q，得生成式S>1x011由b(q,0)=q，得生成式S>0,S>0x022由b(q,1)=q，得生成式x>1S101由b(q,0)=q，得生成式x>0,x>0x12112由b(q,1)=q，得生成式x>1x21由b(q,0)=q，得生成式x>0,x>0x222對(duì)比實(shí)例：當(dāng)掃描字符串1110時(shí)，A按以下?tīng)顟B(tài)序列接受該字符串q―1>q—1>q—1>q―0>q

01012用對(duì)應(yīng)的正則文法G推導(dǎo)，得：Sn1xn11Sn111xn111011?按有限態(tài)自動(dòng)機(jī)確定正則文法給定一個(gè)有限態(tài)自動(dòng)機(jī)A=Q,Q,b,q,F)，可確定一個(gè)正則文法G=(V,V,P,S)，0NT使得L(G)=T(A)。由Q={q,q，…,q,q},qeF，可確定：V={S,x,x，…,x,x}，S=q，01nn+1n+1N12nn+10x=q，V=￡。iiT從b求G中的生成式P可按如下原則：(1)若b(q,a)=q，則x>axijij(2)若b(q,a)=q，則x>a,x>axTOC\o"1-5"\h\zin+1iin+1K-均值算法聚類：K=2,初始聚類中心為x,x，數(shù)據(jù)為：(10’)12{x=(0,0),x=(1,0),x=(0,1),x=(1,1),x=(8,7)2345x=(9,7),x=(8,8),x=(9,8),x=(8,9),x=(9,9)}678910算法：第一步：選K個(gè)初始聚類中心，z⑴,z(1)，…,z(1)，其中括號(hào)內(nèi)的序號(hào)為尋找聚類12k中心的迭代運(yùn)算的次序號(hào)。可選開(kāi)始的K個(gè)模式樣本的向量值作為初始聚類中心。

第二步：逐個(gè)將需分類的模式樣本｛%｝按最小距離準(zhǔn)則分配給K個(gè)聚類中心中的某一個(gè)z⑴。即D(k)=min｛x—z(k),i=1,2,K｝，則1￡S(k)，其中kjjij為迭代運(yùn)算的次序號(hào)，第一次迭代k=1，S表示第j個(gè)聚類，其聚類中心為j???z。j第三步：計(jì)算各個(gè)聚類中心的新的向量值，z(k+1),j=1,2,...,Kj求各聚類域中所包含樣本的均值向量：…、1y.Njx￡S(k)jjz(k+1)Njx￡S(k)jj其中N.為第j個(gè)聚類域S,中所包含的樣本個(gè)數(shù)。?以均值向量作為新的聚類中心，可使如下聚類準(zhǔn)則函數(shù)最?。篔=yx—z(k+1)2,j=1,2,,Kjjx￡S(k)

j在這一步中要分別計(jì)算K個(gè)聚類中的樣本均值向量，所以稱之為K-均值算法。第四步：若z(k+1)豐z(k)，則返回第二步，將模式樣本逐個(gè)重新分類，重復(fù)迭代jj運(yùn)算；若z(k+1)=z(k)，則算法收斂，計(jì)算結(jié)束。jj給出兩類模式分布，每一列代表一個(gè)樣本：(—5—5—4—5—613：X=1i1-5—4—5—6—5)(5565413：X=22156545)試用K-L變換來(lái)做一維特征的提取(12’)。解：首先將所有樣本看作一個(gè)整體，求出樣本均值向量：m=1yx+1yx=051j52j

j=1j=1由于均值為0，符合K-L變換的最佳條件。如果均值不為0，則所有樣本要減去均值向量。由于3和3的樣本數(shù)相同，所以認(rèn)為他們的先驗(yàn)概率相同，即：12P(3)=P(3)=0.512

求出總體的自相關(guān)矩陣R或協(xié)方差矩陣C：R=￡P(guān)(3)E{xxt}iiii=125.425'2525.4,入=50.4,九1:，25.425'2525.4,入=50.4,九1:，=0.42求出對(duì)應(yīng)于特征值的特征向量R6=入。：iiiir1、IF[J選取?對(duì)應(yīng)的特征向量作為變換矩陣①，由J=OTx得出變換后的一維模式:3?X，/—10—9—9-11-11]31：x「[國(guó)V2不用不),(1011119913：Xr=22I戶&**V2)8.用第二類勢(shì)函數(shù)的算法進(jìn)行分類(10‘)選擇指數(shù)型勢(shì)函數(shù)，取a=1,在二維情況下勢(shì)函數(shù)為：K(x,x)=e-x-x)2=e-g-%)2+(x2-xk2)2]k這里：3]類為X①=(00)T,X②=(20)T;32類為X③=(11)T,X④=(1-1)T解：可以看出，這兩類模式是線性不可分的。算法步驟如下：TOC\o"1-5"\h\z第一步：取X=(0,0)T￡3，貝U(1)1K(x)=K(x,x)=exp{-[(x一0)2+(x-0)2]}=exp[-(x2+x2)](1)1212第二步：取x=(2,0)T￡3(2)1因exp[-(4+0)]=exp(-4)>0,故K(x)=K(x)=exp[-(x2+x2)]2112第三步：取x=(1,1)T￡3(3)2因exp[-(1+1)]=exp(-2)>0,故K(x)=K(x)-K(x,x)=exp[-(x2+x2)]-exp{-[(x-1)2+(x-1)2]}32(3)1212

后面同理，就是不斷將樣本帶入，如果分類正確，則勢(shì)函數(shù)保持不變，即：TOC\o"1-5"\h\zK(x)=K(x)

k+1k如果分類錯(cuò)誤，則有兩種情況：xw3,K(x)<0，則K(x)=K(x)+K(x,x)(k+1)1k(k+1)k+1k(k+1)xe3,K(x)>0，則K(x)-K(x)一K(x,x)(k+1)2k(k+1)k+1k(k+1)經(jīng)過(guò)迭代，全部模式都已正確分類，因此算法收斂于判別函數(shù)。得出：d(x)-e一(x2+x2)-e一[(x1-1)2+(x2-1)2]一e一[(x[i)2+(x2+1)2]+e一[(、一2)2+x2]9.有一種病，正常為號(hào)，不正常為9.有一種病，正常為號(hào)，不正常為①？，已知:P（3）-0.9,P（3）=0.112

現(xiàn)對(duì)某人進(jìn)行檢查，結(jié)果為x，由概率曲線查出:P(P(x|3)-10.2,P(x|3)-0.42風(fēng)險(xiǎn)代價(jià)矩陣為:L-LL-L11L21L22對(duì)該檢查者進(jìn)行判決:用貝葉斯最小錯(cuò)誤概率判別，求出判決函數(shù)和決策分界面。用貝葉斯最小風(fēng)險(xiǎn)判別，求出判別函數(shù)和決策分界面。解（1）:TOC\o"1-5"\h\zP(3Ix)XP(3)P(xI3)111P(3Ix)XP(3)P(xI3)222由于P(xI3)1P(3)1l-1-——>2———P(xI3)2P(3)921所以x￡3]。解(2):r(x)=2LP(x13)P(3),j―1,2TOC\o"1-5"\h\zjijiii-1由于P(xI3)1P(3)L一L1/—1—、CC1cc—1———>22122-P(x13)2P(3)L一L54211211

10.闡述誤差反傳算法（BP算法）的原理，并寫出其訓(xùn)練步驟。答（1）：?BP算法推算過(guò)程：史宛,史宛,h苗WM/T?當(dāng)加入第k個(gè)輸入時(shí)，隱蔽層h結(jié)點(diǎn)的輸入加權(quán)和為:Sk=ZWXk

hihii如果令第一層的加權(quán)矩陣為W1，則還可以表示為:sk二WTxkh1相應(yīng)節(jié)點(diǎn)的輸出為：yk=F(Sk)=F(ZWXk)

hhihii寫成矩陣形式為：yk=F(sk)=F(WTxk)

hh1同樣，輸出層j結(jié)點(diǎn)的輸入加權(quán)和為:Sk=ZSk=ZjWykhjh=ZWFhjh(ZWXk)

ihii令第二次的加權(quán)矩陣為嗎，則可以寫成:TOC\o"1-5"\h\zsk=WTyk=WTF(WTxk)

j2h21相應(yīng)點(diǎn)的輸出：yk=F(Sk)=F(ZWyk)=F[ZWF(ZWXk)]jjhjhhjihihhi寫成矩陣形式為：yk=F(WTF(WTxk))

j21

這里，各結(jié)點(diǎn)的閾值等效為一個(gè)連接的加權(quán)e=wo,或w0/這些連接由各結(jié)點(diǎn)連到具有固定值-1的偏置結(jié)點(diǎn)，其連接加權(quán)也是可調(diào)的，誤差函數(shù)為：E(W)=1Z(Tk-Jk)2=1Z{Tk2jj2j

k,jk,j同其它加權(quán)一樣參與調(diào)節(jié)過(guò)程。-F同其它加權(quán)一樣參與調(diào)節(jié)過(guò)程。-F[ZwF(Zwxk)]}2

hjihihiAwhj0E-n—0whj二“Z(Tk-Jk)F'(sk)Jk可ZbjjkjhkkJkjh其中8k為輸出結(jié)點(diǎn)的誤差信號(hào):j8k=F'(sk)(Tk—/)=F'(sk)AjjAkjAkjTk-Jkjj在BP算法中常采用Sigmoid函數(shù)：J=F(s)=其導(dǎo)數(shù)為：F'(s)=F(s)(1-F(s))=J(1-J)對(duì)應(yīng)的誤差為：8k=Jk(1—Jk)(Tk-Jk)jjjjj對(duì)于輸入層到隱蔽層結(jié)點(diǎn)連接的加權(quán)修正量Aw對(duì)于輸入層到隱蔽層結(jié)點(diǎn)連接的加權(quán)修正量Aw,必須考慮將E(W)對(duì)w求導(dǎo)，因此ihih利用分層鏈路法，有：Awih0E-n——dw="Awih0