完整word版,中科院-模式識別考題總結(jié)(詳細答案),推薦文檔

1、1. 簡述模式的概念及其直觀特性，模式識別的分類，有哪幾種方法。 （6）答（ 1）：什么是模式？ 廣義地說，存在于時間和空間中可觀察的物體，如果我們可以區(qū)別它們是否相同或是否相似，都可以稱之為模式。模式所指的不是事物本身， 而是從事物獲得的信息， 因此，模式往往表現(xiàn)為具有時間和空間分布的信息。模式的直觀特性：可觀察性；可區(qū)分性；相似性。答（ 2）：模式識別的分類：假說的兩種獲得方法（模式識別進行學習的兩種方法）：監(jiān)督學習 、概念驅(qū)動或歸納假說；非監(jiān)督學習 、數(shù)據(jù)驅(qū)動或演繹假說。模式分類的主要方法：數(shù)據(jù)聚類 ：用某種相似性度量的方法將原始數(shù)據(jù)組織成有意義的和有用的各種數(shù)據(jù)集。是一種非監(jiān)督學習的方

2、法，解決方案是數(shù)據(jù)驅(qū)動的。統(tǒng)計分類 ：基于概率統(tǒng)計模型得到各類別的特征向量的分布，以取得分類的方法。特征向量分布的獲得是基于一個類別已知的訓練樣本集。是一種監(jiān)督分類的方法，分類器是概念驅(qū)動的。結(jié)構(gòu)模式識別 ：該方法通過考慮識別對象的各部分之間的聯(lián)系來達到識別分類的目的。（句法模式識別）神經(jīng)網(wǎng)絡(luò) ：由一系列互相聯(lián)系的、相同的單元（神經(jīng)元）組成。相互間的聯(lián)系可以在不同的神經(jīng)元之間傳遞增強或抑制信號。 增強或抑制是通過調(diào)整神經(jīng)元相互間聯(lián)系的權(quán)重系數(shù)來（ weight ）實現(xiàn)。神經(jīng)網(wǎng)絡(luò)可以實現(xiàn)監(jiān)督和非監(jiān)督學習條件下的分類。2. 什么是神經(jīng)網(wǎng)絡(luò)？有什么主要特點？選擇神經(jīng)網(wǎng)絡(luò)模式應該考慮什么因素？（8）答

3、（ 1）：所謂人工神經(jīng)網(wǎng)絡(luò)就是基于模仿生物大腦的結(jié)構(gòu)和功能而構(gòu)成的一種信息處理系統(tǒng)（計算機） 。 由于我們建立的信息處理系統(tǒng)實際上是模仿生理神經(jīng)網(wǎng)絡(luò)，因此稱它為人工神經(jīng)網(wǎng)絡(luò)。 這種網(wǎng)絡(luò)依靠系統(tǒng)的復雜程度， 通過調(diào)整內(nèi)部大量節(jié)點之間相互連接的關(guān)系，從而達到處理信息的目的。人工神經(jīng)網(wǎng)絡(luò)的兩種操作過程：訓練學習、正常操作（回憶操作）。答（ 2）：人工神經(jīng)網(wǎng)絡(luò)的特點：固有的并行結(jié)構(gòu)和并行處理；知識的分布存儲；有較強的容錯性；有一定的自適應性；人工神經(jīng)網(wǎng)絡(luò)的局限性：人工神經(jīng)網(wǎng)絡(luò)不適于高精度的計算；人工神經(jīng)網(wǎng)絡(luò)不適于做類似順序計數(shù)的工作；人工神經(jīng)網(wǎng)絡(luò)的學習和訓練往往是一個艱難的過程；人工神經(jīng)網(wǎng)絡(luò)必須克服時

4、間域順序處理方面的困難；硬件限制；正確的訓練數(shù)據(jù)的收集。答（ 3）：選取人工神經(jīng)網(wǎng)絡(luò)模型，要基于應用的要求和人工神經(jīng)網(wǎng)絡(luò)模型的能力間的匹配，主要考慮因素包括：網(wǎng)絡(luò)大??；所需輸出類型；聯(lián)想記憶類型；訓練方法；時間的限定。3. 畫出句法模式識別的框圖，并解釋其工作原理。 （ 8）答（ 1）：句法模式識別框圖如下：答（ 2）：句法模式識別系統(tǒng)的組成：圖像預處理，圖像分割，基元及其關(guān)系識別，句法分析。基于描述模式的結(jié)構(gòu)信息， 用形式語言中的規(guī)則進行分類， 可以更典型地應用于景物圖片的分析。因為在這類問題中， 所研究的模式通常十分復雜， 需要的特征也很多， 僅用數(shù)值上的特征不足以反映它們的類別。句法模式

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

6、假如要建立二次的多項式判別函數(shù)，又至少需要幾個系數(shù)分量？ （設(shè)模式的良好分布不因模式變化而改變。 ）（8）答（1）：模式識別系統(tǒng)的主要作用是判別各個模式所屬的類別。線性判別函數(shù)分類就是使用線性判別函數(shù)將多類樣本模式分開。一個 n 維線性判別函數(shù)的一般形式：Td ( x) w1 x1 w2 x2 K wn xn wn 1 w0 x wn 1其中 w0 (w1, w2 ,., wn )T 稱為權(quán)向量（或參數(shù)向量）， x( x1 , x2 ,., xn )T 。d (x) 也可表示為： d( x)wT x其中， x ( x1 , x2 ,., xn ,1)T稱為增廣模式向量，w0( w1, w2 ,

7、., wn , wn 1 )T稱為增廣權(quán)向量。兩類情況 ：判別函數(shù)d (x) ：0ifxd (x) wT xifx012多類情況 ：設(shè)模式可分成1 ,2 ,.,M 共 M 類，則有三種劃分方法：多類情況1用線性判別函數(shù)將屬于i 類的模式與不屬于i 類的模式分開，其判別函數(shù)為：d( x)wT x0ifxiii0ifxi這種情況稱為i /i 兩分法， 即把 M 類多類問題分成M 個兩類問題，因此共有M 個判別函數(shù) ，對應的判別函數(shù)的權(quán)向量為wi , i1,2,., n 1 。多類情況 2采用每對劃分，即i |j 兩分法，此時一個判別界面只能分開兩種類別，但不能把它與其余所有的界面分開。其判別函數(shù)為

8、：d( x)wT x若 dij (x)0 ，j i，則 xiijij重要性質(zhì)： dijd ji要分開 M 類模式，共需M(M -1)/2 個判別函數(shù)。不確定區(qū)域：若所有dij ( x) ，找不到j(luò)i ， dij (x)0 的情況。多類情況3（多類情況2 的特例）這是沒有不確定區(qū)域的i |j兩 分 法 。 假 若 多 類 情 況 2 中 的 dij可分解成：dij ( x)di ( x)d j ( x)(wiw j )T x ，則 dij0 相當于 di (x)dj (x) ， j i。這時不存在不確定區(qū)域。此時，對 M 類情況應有 M 個判別函數(shù) ：dk ( x)wkT x, k1,2,K ,

9、 M即 di ( x) d j ( x)，ji ， i , j1,2,.M， 則 xi，也可寫成，若di ( x)max dk (x), k1,2,., M ，則 xi 。該分類的特點是把M 類情況分成 M-1 個兩類問題。模式分類若可用任一個線性函數(shù)來劃分，則這些模式就稱為線性可分的，否則就是非線性可分的。一旦線性函數(shù)的系數(shù)wk 被確定，這些函數(shù)就可用作模式分類的基礎(chǔ)。對于 M 類模式的分類，多類情況1 需要 M 個判別函數(shù)，而多類情況2 需要 M*(M -1)/2個判別函數(shù)，當M 較大時，后者需要更多的判別式（這是多類情況2 的一個缺點） 。采用多類情況1 時，每一個判別函數(shù)都要把一種類別

10、的模式與其余M-1 種類別的模式分開，而不是將一種類別的模式僅與另一種類別的模式分開。由于一種模式的分布要比M-1 種模式的分布更為聚集，因此多類情況2 對模式是線性可分的可能性比多類情況1 更大一些（這是多類情況2 的一個優(yōu)點） 。答（ 2）廣義線性判別函數(shù)出發(fā)點：線性判別函數(shù)簡單，容易實現(xiàn)；非線性判別函數(shù)復雜，不容易實現(xiàn)；若能將非線性判別函數(shù)轉(zhuǎn)換為線性判別函數(shù)，則有利于模式分類的實現(xiàn)。采用廣義線性判別函數(shù)的概念，可以通過增加維數(shù)來得到線性判別，但維數(shù)的大量增加會使在低維空間里在解析和計算上行得通的方法在高維空間遇到困難，增加計算的復雜性。所以某些情況下使用非線性判別函數(shù)或分段線性判別函數(shù)效

11、果更好。解（ 3）假設(shè)該兩類模式是線性可分的，則在三維空間中一個線性平面可以將這兩類模式分開，所以判別函數(shù)可以寫成：d (x)w1 xw2 xw3 xw4所以權(quán)向量需要4 個系數(shù)。對于 n 維 x 向量，采用r 次多項式， d(x)的權(quán)系數(shù) w 的項數(shù)為：N wC nrr(n r )!r !n!當 r=2， n=3 時，(n2)!(n2)( n 1)NW102! n!2所以，此時權(quán)向量需要10 個系數(shù)分量。5. 設(shè)一有限態(tài)自動機 A (0,1, q0 , q1 , q2, q0 , q2 ，定義如下：(q0 ,0)q2 , (q1,0)q2 , ( q2 ,0)q2(q0 ,1)q1 , (q

12、1 ,1)q0 , (q2,1)q1試求等價的正則文法，使得L(G)=T(A)。（ 10）解：設(shè)由 A 得一正則文法(,， )，則，GVNVTP SVN S, x1 , x2 VT0,1 S q0由 ( q0,1)q1 ，得生成式 S1x1由(q0 ,0)q2 ，得生成式 S0, S0x2由 ( q1,1)q0 ，得生成式 x11S由(q1,0)q2 ，得生成式 x10, x10x2由(q2 ,1)q1 ，得生成式 x21x1由(q2 ,0)q2 ，得生成式 x20, x20x2對比實例：當掃描字符串 1110時， A 按以下狀態(tài)序列接受該字符串1q11q01q10q2q0用對應的正則文法G

13、推導，得：S1x111S111x11110按有限態(tài)自動機確定正則文法給定一個有限態(tài)自動機A (,Q, q0 , F ) ，可確定一個正則文法G (VN,VT ,P, S) ，使得 L(G) = T(A)。由 Q q0 ,q1,., qn , qn 1, qn1F，可確定： VN S, x1, x2 ,., x n , xn 1 ， S q0 ，xi qi ， VT。從求 G 中的生成式 P 可按如下原則：(1)若(qi , a)q j ，則 xiax j(2)若(qi , a)qn1 ，則 xia, xiaxn 16. K-均值算法聚類： K=2，初始聚類中心為 x1, x2 ，數(shù)據(jù)為：（10

14、） 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 個初始聚類中心，z1 (1),z2 (1),., zk (1)，其中括號內(nèi)的序號為尋找聚類中心的迭代運算的次序號?？蛇x開始的K個模式樣本的向量值作為初始聚類中心。第二步：逐個將需分類的模式樣本 x 按最小距離準則分配給K 個聚類中心中的某一個 zj (1) 。即 D j(k ) min xzi(k ) , i1, 2,L K ，則 xSj ( k ) ，其中 k為迭代運算的次序號，第一次迭代k1，

15、Sj 表示第 j 個聚類，其聚類中心為zj 。第三步：計算各個聚類中心的新的向量值，zj(k1), j1,2,., K求各聚類域中所包含樣本的均值向量：z j ( k1x,j1,2,L, K1)N jx S j ( k )其中 N j 為第 j 個聚類域 Sj 中所包含的樣本個數(shù)。以均值向量作為新的聚類中心 ，可使如下聚類準則函數(shù)最?。?J jx zj( k 1),j1,2,L, Kx Sj ( k )在這一步中要分別計算K 個聚類中的樣本均值向量，所以稱之為 K-均值算法。第四步：若 zj (k 1)zj (k ) ，則返回第二步，將模式樣本逐個重新分類，重復迭代運算；若 zj (k 1)

16、zj ( k) ，則算法收斂，計算結(jié)束。7. 給出兩類模式分布，每一列代表一個樣本：1： x155456545652： x25565456545試用 K -L 變換來做一維特征的提?。?12）。解：首先將所有樣本看作一個整體，求出樣本均值向量：m15x1j155 jx 2j 015 j 1由于均值為0，符合 K -L 變換的最佳條件。如果均值不為0，則所有樣本要減去均值向量。由于1 和2 的樣本數(shù)相同，所以認為他們的先驗概率相同，即：P( 1)P( 2)0.5求出總體的自相關(guān)矩陣R 或協(xié)方差矩陣C ：2T25.425RP()E x xii1ii2525.4解特征方程 R I0 ，求出 R 的特

17、征值：150.4,20.4求出對應于特征值的特征向量R iii ：1111121, 221選取1 對應的特征向量作為變換矩陣，由 yT x 得出變換后的一維模式：109911111： x1'22222101111992： x2'222228. 用第二類勢函數(shù)的算法進行分類（ 10）選擇指數(shù)型勢函數(shù)，取 =1，在二維情況下勢函數(shù)為：x xk2( x1 xk) 2 ( x2xk) 2 K ( x, xk ) ee12這里： 1 類為 x=(0 0)T , x =(2 0)T； 2類為 x =(1 1)T , x=(1 -1)T解：可以看出，這兩類模式是線性不可分的。算法步驟如下：第

18、一步：取 x(1)(0,0)T1 ，則K1 ( x) K ( x, x(1) )exp ( x10)2( x20)2 exp ( x12x22 )第二步：取 x(2)(2,0) T1因 exp(40)exp(4)0 ，故 K 2 ( x)K1 ( x)exp( x12x22 )第三步：取 x(3)(1,1)T2因 exp (1 1) exp( 2)0 ，故K3 ( x)K 2 ( x)K ( x, x(3) )exp ( x1 2x22 )exp ( x11)2( x21)2 后面同理，就是不斷將樣本帶入，如果分類正確，則勢函數(shù)保持不變，即：K k 1( x)K k (x)如果分類錯誤，則有兩

19、種情況：x(k 1)1 , K k (x(k 1) )0，則 K k1 ( x)K k ( x)K ( x, x(k 1) )x(k 1)2 , K k (x(k 1) )0 ，則 K k1 ( x)K k (x)K ( x, x(k 1) )經(jīng)過迭代，全部模式都已正確分類，因此算法收斂于判別函數(shù)。得出： d ( x) e( x2x2 )e( x 1)2 ( x1)2 e( x 1) 2 ( x1)2 e( x 2) 2x2121212129. 有一種病，正常為 1 ，不正常為 2 ，已知：P( 1 )0.9,P( 2 )0.1現(xiàn)對某人進行檢查，結(jié)果為x ，由概率曲線查出：P( x | 1 )

20、0.2,P( x |2 )0.4風險代價矩陣為：L11L1206LL2210L21對該檢查者進行判決：（ 1） 用貝葉斯最小錯誤概率判別，求出判決函數(shù)和決策分界面。（ 2） 用貝葉斯最小風險判別，求出判別函數(shù)和決策分界面。解（ 1）：P(1 | x)P(1 )P(x |1 )P(2 | x)P(2 )P( x |2 )由于P( x |1)1P(2) 1l2P(1) 9P( x | 2 )所以 x1 。解（ 2）：2r j ( x)Lij P(x | i ) P( i ), j 1,2i1由于P( x |1 )1P(2) L21L221l '2 )2P(1) L12L1154P( x |

21、所以 x1 。10. 闡述誤差反傳算法（ BP 算法）的原理，并寫出其訓練步驟。答（ 1）：BP 算法推算過程：當加入第k 個輸入時，隱蔽層h 結(jié)點的輸入加權(quán)和為：skw xkhih ii如果令第一層的加權(quán)矩陣為W1 ，則還可以表示為：shkW1T xk相應節(jié)點的輸出為：yhkF ( shk )F (wih xik )i寫成矩陣形式為：yhkF (shk )F (W1T x k )同樣，輸出層j 結(jié)點的輸入加權(quán)和為：skjwhj yhkwhj F (wih xik )hhi令第二次的加權(quán)矩陣為W2 ，則可以寫成：skjW2T yhkW2T F (W1T x k )相應點的輸出：ykjF ( s

22、kj )F (whj yhk )F whj F (wih xik )hhi寫成矩陣形式為：ykjF (W2T F (W1T xk )這里，各結(jié)點的閾值等效為一個連接的加權(quán)w0 h 或 w0 j ，這些連接由各結(jié)點連到具有固定值 -1 的偏置結(jié)點，其連接加權(quán)也是可調(diào)的，同其它加權(quán)一樣參與調(diào)節(jié)過程。誤差函數(shù)為：E(W)1(T jky kj )2 1T jkF whj F ( wih xik ) 22 k , j2 k , jhi為了使誤差函數(shù)最小，用梯度下降法求得最優(yōu)的加權(quán)，權(quán)值先從輸出層開始修正，然后依次修正前層權(quán)值，因此含有反傳的含義。根據(jù)梯度下降法，由隱蔽層到輸出層的連接的加權(quán)調(diào)節(jié)量為：whjE(T jky kj ) F ( skj ) yhkjk yhkwhjkk其中jk 為輸出結(jié)點的誤差信號：kkkkk)kjF (sj)(T jy j) F (sjjkkkjTjy j在 BP 算法中常采用Sigmoid 函數(shù)： yF (s)1e s1其導數(shù)為： F '(s)F (s)(1F ( s)y(1y)kkkkk)對應的誤差為：jy j (1yj )(Tjy j對于輸入層到隱蔽層結(jié)點連接的加權(quán)修正量wih ，必須考慮將 E(W) 對 wih求導，因此利用分層鏈路法，有：EEyhkkkk)whjkkwihyhkwih(