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

1、1 .簡(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í)的方法，解決

2、方案是數(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í)條件下的分 類。2 .什么是神經(jīng)網(wǎng)絡(luò)？有什么主要特點(diǎn)？選擇神經(jīng)網(wǎng)絡(luò)模式應(yīng)該考慮什么因素？（8）答（1）：

3、所謂人工神經(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í)間域順序處理方

4、面的困難；硬件限制；正確的訓(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í)間的限定。3 .畫出句法模式識(shí)別的框圖，并解釋其工作原理。（8'）答（1）：句法模式識(shí)別框圖如下：松式太述訓(xùn)練模包&些無(wú)不關(guān)系 選擇£法或結(jié)構(gòu) 推斷答（2）:句法模式識(shí)別系統(tǒng)的組成：圖像預(yù)處理，圖像分割，基元及其關(guān)系識(shí)別，句法 分析?；诿枋瞿Ｊ降慕Y(jié)構(gòu)信息，用形式語(yǔ)言中的規(guī)則進(jìn)行分類，可以更典型地應(yīng)用于景物圖 片的分析。因?yàn)樵谶@類問(wèn)題中， 所研究的模式通常十分復(fù)雜， 需要的特征也很多， 僅用數(shù)值上的特

5、征不足以反映它們的類別。句法模式識(shí)別系統(tǒng)處理過(guò)程： 基元本身包含的結(jié)構(gòu)信息已不多， 僅需少量特征即可識(shí)別。如果用有限個(gè)字符代表不同的基元，則由基元按一定結(jié)構(gòu)關(guān)系組成的子圖或圖形可以用一個(gè)有序的字符串來(lái)代表。 假如事先用形式語(yǔ)言的規(guī)則從字符串中推斷出能生成它的文法，則 可以通過(guò)句法分析，按給定的句法（文法）來(lái)辨識(shí)由基元字符組成的句子，從而判別它是 否屬于由該給定文法所能描述的模式類，達(dá)到分類的目的。4 . （1）解釋線性判別函數(shù)進(jìn)行模式分類的概念；（2）既然有了線性判別函數(shù)， 為什么還要用非線性判別函數(shù)進(jìn)行模式分類？ （3）兩類模式，每類包括5個(gè)3維不同的模式，且良好分布。如果它們是線性可分的，

6、問(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） WiXi W2X2 "I WnXn Wn 1 WX W-其中 Wo （W1，W2,., Wn）T 稱為權(quán)向量（或參數(shù)向量），X （X1，X2,., Xn）T。d（x）也可表示為：d（X） wTx其中，X （X1,X2,., Xn,1）T稱為增廣模式向量，Wo （W1,W2,., Wn, Wn

7、 1）T稱為增廣權(quán) 向量。兩類情況：判別函數(shù)d(x)：d(x) wTx0 if0 if多類情況：設(shè)模式可分成i2，M共M類，則有三種劃分方法:多類情況1用線性判別函數(shù)將屬于di(x) wTxif xif x這種情況稱為 i/一i兩分法,別函數(shù)，對(duì)應(yīng)的判別函數(shù)的權(quán)向量為英式與不屬于i類的模式分開(kāi)，其判別函數(shù)為：即把M類多類問(wèn)題分成 M個(gè)兩類問(wèn)題：因此共有 M個(gè)判wi,i 1,2，,n 1。多類情況2采用每對(duì)劃分，即 i | j兩分法，此時(shí)一個(gè)判別界面只能分開(kāi)兩種類別，但不能把它 與其余所有的界面分開(kāi)。其判別函數(shù)為：dj(x) wTx若dj(x) 0, j i,則x i重要性質(zhì)：dijdji要分開(kāi)

8、 M類模式，共需 M(M-1)/2個(gè)判別函數(shù)。不確定區(qū)域：若所有dij(x),找不到j(luò) i, dij (x) 0的情況。多類情況3 (多類情況2的特例)這是沒(méi)有不確定區(qū)域的i | j兩分法。假若多類情況2中的dij可分解成：dj (x) di(x) dj(x) (Wi Wj)Tx,則 dj0相當(dāng)于 di(x) dj(x) , j i。這時(shí)不存在不確定區(qū)域。此時(shí)，對(duì)M類情況應(yīng)有M個(gè)判別函數(shù)：djx) wTx, k 1,2,HI, M即 di(x) dj(x) , j i , i,j 1,2,.M ，則 x i ,也可寫成，若di(x) maxdk(x),k 1,2,.,M，則 x i。該分類的特

9、點(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更大一些（這是多類

10、情況 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） w1x w2x w3x w4所以權(quán)向量需要4個(gè)系數(shù)。對(duì)于n維x向量，采用r次多項(xiàng)式，d

11、（x）的權(quán)系數(shù)w的項(xiàng)數(shù)為:NwC(n r)!r! n!當(dāng) r=2 , n=3 時(shí),(n 2)! (n 2)(n 1)W -2!n!10所以，此時(shí)權(quán)向量需要 10個(gè)系數(shù)分量。5 .設(shè)一有限態(tài)自動(dòng)機(jī)A (0,1,q0,q1,q2, «&, 定義如下:(q0,0)q2, (0,0) q2, 4,0) q2(q0,1) q1, 9,1) q0, (q2,1) q1試求等價(jià)的正則文法，使得L(G尸T(A) o (10")解：設(shè)由 A 得一正則文法 G （Vn，Vt，P, S）,則 Vn S,Xi,X2, Vt 0,1,S q0由(q0,1)q1 ，得生成式S1X1由(q0,0

12、)q2 ，得生成式S0,S0X2由(q1,1)q0 ，得生成式X11S由(q1,0)q2 ，得生成式X10, X10X2由(q2,1)q1 ，得生成式X21X1由(q2,0)q2 ，得生成式X20,X20X2對(duì)比實(shí)例：當(dāng)掃描字符串 1110 時(shí)， A 按以下?tīng)顟B(tài)序列接受該字符串1110q0q1q0q1q2用對(duì)應(yīng)的正則文法 G推導(dǎo)，得:S 1x111S111x11110按有限態(tài)自動(dòng)機(jī)確定正則文法給定一個(gè)有限態(tài)自動(dòng)機(jī)A ( ,Q, ,q0, F) ，可確定一個(gè)正則文法G (VN ,VT ,P,S) ，使得 L(G) = T(A) 。由 Qq0,q1,.,qn,qn1,qn1 F ，可確定：VNS,

13、x1,x2,.,xn,xn1 ，Sq0，xiqi ， VT。從 求 G 中的生成式P 可按如下原則：(1) 若 (qi,a) qj ，則xiaxj(2) 若 (qi,a) qn 1，則xia,xiaxn 16. K-均值算法聚類：K=2,初始聚類中心為X，X2,數(shù)據(jù)為：(10')x1(0,0), x2 (1,0),x3 (0,1),x4 (1,1),x5 (8,7)X6 (9,7), X7 (8,8), X8 (9,8), X9 (8,9), X10 (9,9)算法 ：第一步：選K個(gè)初始聚類中心，4(1),Z2(1)，,4(1),其中括號(hào)內(nèi)的序號(hào)為尋找聚類中心的迭代運(yùn)算的次序號(hào)。 可選

14、開(kāi)始的 K 個(gè)模式樣本的向量值作為初始聚類 中心。第二步：逐個(gè)將需分類的模式樣本x按最小距離準(zhǔn)則分配給K個(gè)聚類中心中的某一個(gè) 4(1)。即 Dj(k) min|x z/k)/ 12“|k,則 x Sj(k),其中 k為迭代運(yùn)算的次序號(hào)，第一次迭代k 1 , Sj表示第j個(gè)聚類，其聚類中心為zj。第三步：計(jì)算各個(gè)聚類中心的新的向量值，Zj(k 1), j 1,2,., K求各聚類域中所包含樣本的均值向量：Zj(k 1) x, j 1,2,|,KNj x Sj(k)其中Nj為第j個(gè)聚類域Sj中所包含的樣本個(gè)數(shù)。以均值向量作為新的聚類中心，可使如下聚類準(zhǔn)則函數(shù)最?。?.Jjx Zj(k 1) , j

15、 1,2,|,Kx Sj(k)在這一步中要分別計(jì)算K個(gè)聚類中的樣本均值向量，所以稱之為K-均值算法。第四步：若Zj(k 1) Zj(k),則返回第二步，將模式樣本逐個(gè)重新分類，重復(fù)迭代 運(yùn)算；若Zj (k 1) Zj (k),則算法收斂，計(jì)算結(jié)束。7,給出兩類模式分布，每一列代表一個(gè)樣本:1 : x15 5 6 5 42 : x25 6 5 4 5試用K-L變換來(lái)做一維特征的提取(12')。 解：首先將所有樣本看作一個(gè)整體，求出樣本均值向量:1 51 5八m Xp x2j 05 j 15 j 1由于均值為0,符合K-L變換的最佳條件。如果均值不為0,則所有樣本要減去均值向量。由于1和2

16、的樣本數(shù)相同，所以認(rèn)為他們的先驗(yàn)概率相同，即：求出總體的自相關(guān)矩陣 R或協(xié)方差矩陣 C :25.4252525.42R P( i)EXxJ i 1解特征方程 R I 0,求出R的特征值:1 50.4, 2 0.4求出對(duì)應(yīng)于特征值的特征向量R i1 112 1選取1對(duì)應(yīng)的特征向量作為變換矩陣i 11, 2121,由yTx得出變換后的一維模式:10991111、2222210111199222228.用第二類勢(shì)函數(shù)的算法進(jìn)行分類(10')選擇指數(shù)型勢(shì)函數(shù)，取a =1,在二維情況下勢(shì)函數(shù)為：x xkl2(x1 % )2 (x2 xk )2K(x, xk) e11 k| e 12這里：1類為x

17、=(0 0) T, x=(2 0) T;2類為x=(1 1) T, x=(1-1) T解：可以看出，這兩類模式是線性不可分的。算法步驟如下：第一步：取 x(1)(0,0)T1 ,則_ 2_ 2 _22K1(x)K(x,x。)exp (x1 0) 誨 0) exp(為x2)第二步：取 x(2)(2,0)T 1因 exp (4 0) exp( 4) 0,故 K2(x) K(x) exp (x12 x22第三步：取4)(1,1)T2因 exp (1 1) exp( 2) 0,故22-22 -L(x) (x)K(x,x(3)exp(%x2) expJ1)(x21) 后面同理，就是不斷將樣本帶入，如果分

18、類正確，則勢(shì)函數(shù)保持不變，即:Kki(x) Kk(x)如果分類錯(cuò)誤，則有兩種情況：X(k 1)1, Kk(X(k1)0,貝UKki(x)Kk(x)K(x, x(ki)x(k 1)2 , Kk (x(k1)0,則Kk1(x)Kk(x)K(x,x(k 1)經(jīng)過(guò)迭代，全部模式都已正確分類，因此算法收斂于判別函數(shù)。22222222得出：d(x)(x1x2)-(x11) (x21) 八(x11) (x21) 八(% 2) x2eee9.有一種病，正常為1 ,不正常為2，已知：P( 1) 0.9,P( 2) 0.1 現(xiàn)對(duì)某人進(jìn)行檢查，結(jié)果為x,由概率曲線查出：P(x| 1) 02P(x| 2) 0.4風(fēng)險(xiǎn)

19、代價(jià)矩陣為：L L11 L120 6L21 L221 0對(duì)該檢查者進(jìn)行判決：(1)用貝葉斯最小錯(cuò)誤概率判別，求出判決函數(shù)和決策分界面(2)用貝葉斯最小風(fēng)險(xiǎn)判別，求出判別函數(shù)和決策分界面。 解(1)：P( 1|x) P( 1)P(x| 1)P( 2|x) P( 2)P(x| 2)由于P(x| 1)1 P( 2) 1l -P(x| 2)2P( 1)9所以x 1。解(2): 2rj(x)LjP(x| i)P( i), j 1,2i 1由于P(x| i) 1 P( 2)L21 L22154P(x| 2)2 P( 1) L12 L11所以x10.闡述誤差反傳算法(BP算法)的原理，并寫出其訓(xùn)練步驟 答(

20、1)：BP算法推算過(guò)程:當(dāng)加入第k個(gè)輸入時(shí)，隱蔽層 h結(jié)點(diǎn)的輸入加權(quán)和為:kkShWihXii如果令第一層的加權(quán)矩陣為 W ,則還可以表示為：k T ksh W1 x相應(yīng)節(jié)點(diǎn)的輸出為：yk F(s；) F( WihX：)i寫成矩陣形式為：yk F(sk) F(WiTxk)同樣，輸出層j結(jié)點(diǎn)的輸入加權(quán)和為：kkk、SjWhj yhWhj F (Wih Xi )hhi令第二次的加權(quán)矩陣為 W2 ,則可以寫成：sk W2r yk W2r F(WiTxk)相應(yīng)點(diǎn)的輸出：yk F(sk) F(亞川丫；)F wNF( wxk)hhi寫成矩陣形式為：yk F(W2TF(WiTxk)這里，各結(jié)點(diǎn)的閾值等效為一

21、個(gè)連接的加權(quán)w0h或w0j ,這些連接由各結(jié)點(diǎn)連到具有固定值-1的偏置結(jié)點(diǎn)，其連接加權(quán)也是可調(diào)的，同其它加權(quán)一樣參與調(diào)節(jié)過(guò)程。誤差函數(shù)為：E(W) 1 (Tjk yk)21 Tjk FWhjF(WihXik)22 k,j2 k,jhiEwhjwhj其中jk為輸出結(jié)點(diǎn)的誤差信號(hào):k為了使誤差函數(shù)最小，用梯度下降法求得最優(yōu)的加權(quán)，權(quán)值先從輸出層開(kāi)始修正，然 后依次修正前層權(quán)值，因此含有反傳的含義。根據(jù)梯度下降法，由隱蔽層到輸出層的連接 的加權(quán)調(diào)節(jié)量為：k kk kk k(Tjyj)F 用j yhkkF (sk)(Tjk yk) F (sk) kk t： ykk1在BP算法中常米用 Sigmoid函數(shù)：yF (s) s1 e其導(dǎo)數(shù)為：F'(s) F (s)(1 F(s) y(1 y)對(duì)應(yīng)的誤差為：yk(1 yk)(Tjk yk)對(duì)于輸入層到隱蔽層結(jié)點(diǎn)連接的加權(quán)修正量wih ,必須考慮將E(W)對(duì)wh求導(dǎo)，因此利用分層鏈路法，有:whEEkwhkyhjkwhjF (sk)xk k,jkyhwhk,jkXi(Tjkyk)F (sk)wh F (sk)Xik其中:F (sk)whj jkf (sh) hkkh