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

2、方案是數據驅動的。統計分類：基于概率統計模型得到各類別的特征向量的分布，以取得分類的方法。 特征向量分布的獲得是基于一個類別已知的訓練樣本集。是一種監督分類的方法， 分類器是概念驅動的。結構模式識別:該方法通過考慮識別對象的各部分之間的聯系來達到識別分類的目的。（句法模式識別）神經網絡：由一系列互相聯系的、相同的單元（神經元）組成。相互間的聯系可以在不同的神經元之間傳遞增強或抑制信號。增強或抑制是通過調整神經元相互間聯系的權重系數來（weight）實現。神經網絡可以實現監督和非監督學習條件下的分 類。2 .什么是神經網絡？有什么主要特點？選擇神經網絡模式應該考慮什么因素？（8'）答（1

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

4、理方面的困難；硬件限制；正確的訓練數據的收集。答（3）:選取人工神經網絡模型，要基于應用的要求和人工神經網絡模型的能力間的網絡大小；所需輸出類型;聯想記憶類型；訓練方法；時間的限定。3 .畫出句法模式識別的框圖，并解釋其工作原理。（8'）答（1）：句法模式識別框圖如下：模式表述，l I訓練模包A基元fl關莪選擇£注或姑構推斷答（2）:句法模式識別系統的組成：圖像預處理，圖像分割，基元及其關系識別，句法 分析。基于描述模式的結構信息，用形式語言中的規則進行分類，可以更典型地應用于景物圖 片的分析。因為在這類問題中， 所研究的模式通常十分復雜， 需要的特征也很多， 僅用數值上的特

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

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

7、,向量。兩類情況：判別函數d(x)：d(x) wTx0 if0 if多類情況：設模式可分成2,，M共M類，則有三種劃分方法:多類情況1用線性判別函數將屬于i類的模式與不屬于i類的模式分開，其判別函數為:di (x) wTx這種情況稱為 i / -i兩分法，即把M類多類問題分成 M個兩類問題，因此共有判別函數，對應的判別函數的權向量為wi,i 1,2,., n 1。多類情況2采用每對劃分，即 i | j兩分法，此時一個判別界面只能分開兩種類別，但不能把它 與其余所有的界面分開。其判別函數為：dj(x) wTx若dj(x) 0, j i,則x i重要性質：djd ji要分開 M類模式，共需 M(M

8、-1)/2個判別函數。不確定區域：若所有 dj (x),找不到 j i , dj (x) 0的情況。多類情況3 (多類情況2的特例)這是沒有不確定區域的i | j兩分法。假若多類情況2中的dij可分解成：dij (x) di(x) dj(x) (wi wj)Tx,則 dj 0相當于 di(x) dj(x) , j i。這時 不存在不確定區域。此時， 對M類情況應有 M個判別函數:dk(x) wTx, k 1,2,K ,M即 di(x) dj(x) , j i , i,j 1,2,.M ，則 x i ,也可寫成，若di(x) maxdk(x),k 1,2,., M,則 x 該分類的特點是把 M類

9、情況分成 M-1個兩類問題。模式分類若可用任一個線性函數來劃分，則這些模式就稱為線性可分的，否則就是非線性可分的。一旦線性函數的系數wk被確定，這些函數就可用作模式分類的基礎。對于M類模式的分類，多類情況 1需要M個判別函數，而多類情況 2需要M*（M -1）/2 個判別函數，當 M較大時，后者需要更多的判別式（這是多類情況2的一個缺點）。采用多類情況1時，每一個判別函數都要把一種類別的模式與其余M-1種類別的模式分開，而不是將一種類別的模式僅與另一種類別的模式分開。由于一種模式的分布要比 M-1種模式的分布更為聚集，因此多類情況2對模式是線性可分的可能性比多類情況1更大一些（這是多類情況 2

10、的一個優點）。答（2）廣義線性判別函數出發點：線性判別函數簡單，容易實現；非線性判別函數復雜，不容易實現；若能將非線性判別函數轉換為線性判別函數，則有利于模式分類的實現。采用廣義線性判別函數的概念，可以通過增加維數來得到線性判別，但維數的大量增加會使在低維空間里在解析和計算上行得通的方法在高維空間遇到困難，增加計算的復雜性。所以某些情況下使用非線性判別函數或分段線性判別函數效果更好。解（3）假設該兩類模式是線性可分的，則在三維空間中一個線性平面可以將這兩類模式分開，所以判別函數可以寫成：d （x） W|X w2x w3x w4所以權向量需要4個系數。對于n維x向量，采用r次多項式，d（x）的權

11、系數w的項數為:Nw Cn r(n r)!r !n!當 r=2, n=3 時,NW(n 2)!2!n!(n 2)(n 1)210所以，此時權向量需要 10個系數分量。5 .設一有限態自動機 A (0,1, qoQQ, QQ, 定義如下:(q0,0)q2, (q1,0)q2, (q2,0) q2(q0,1) q, 9,1) q0, (q2,1) q1試求等價的正則文法，使得L(G尸T(A) (10)I一室解：設由 A得一正則文法 G (VnM，P, S)4UVn S,x1,x2,VT 0,1 , S q0由(q0,1)qi ,得生成式S1x1由(q0,0)q2,得生成式S0,s0x2由(q1,1

12、)q0,得生成式X11S由0,0)q2,得生成式X10,X10x2由QJ)q1，得生成式X21x1由(q2,0)q2,得生成式X20,X20X2對比實例：當才3描字符串1110時，A按以下狀態序列接受該字符串1110qoq1qoq1q2用對應的正則文法 G推導，得：S1x111S111x11110按有限態自動機確定正則文法給定一個有限態自動機 A ( ,Q, ,qo,F),可確定一個正則文法 G (Vn,Vt,P,S), 使得 L(G) = T(A>由 Q qo,q1,.,qn,qn 1, qn 1 F ，可確定：Vn S,x1, x2,., xn, xn 1 , S q0 ,xi qi

13、 , Vt。從 求G中的生成式P可按如下原則：(1)若(qi,a) qj ,則 Xaxj(2)若(qi,a) qn 1 ,則為a,xiaxn 16 . K-均值算法聚類：K=2,初始聚類中心為土出，數據為：(10')Xi(0.0), x2(1,0),x3(0,1),x4(1,1)孔(8,7)%(9,7), X7(8,8),X8(9,8),X9(8,9)，。(9,9)算法：第一步：選K個初始聚類中心，z,(1),Z2(1),.,Zk(1),其中括號內的序號為尋找聚類中心的迭代運算的次序號。可選開始的K個模式樣本的向量值作為初始聚類中0第二步：逐個將需分類的模式樣本x按最小距離準則分配給

14、K個聚類中心中的某一個Zj(1)。即 Dj(k) min | x zi(k)|,i 1,2,LK,則 x Sj(k),其中 k 為迭代運算的次序號，第一次迭代k 1,Sj表示第j個聚類，其聚類中心為Zj。第三步：計算各個聚類中心的新的向量值，zj(k 1), j 1,2,., K求各聚類域中所包含樣本的均值向量：1Zj(k 1)x, j 1,2,L ,KN j x Sj (k)其中Nj為第j個聚類域Sj中所包含的樣本個數。以均值向量作為新的聚類中心，可使如下聚類準則函數最小：Jj| x Zj(k 1，j 1,2,L ,Kx Sj (k)在這一步中要分別計算K個聚類中的樣本均值向量，所以稱之為K

15、-均值算法。第四步：若Zj(k 1) Zj (k),則返回第二步，將模式樣本逐個重新分類，重復迭代 運算；若Zj (k 1) Zj(k),則算法收斂，計算結束。7 .給出兩類模式分布，每一列代表一個樣本:1 : Xi5 5 6 5 4X25 6 5 4 5試用K-L變換來做一維特征的提取(12')。解：首先將所有樣本看作一個整體，求出樣本均值向量:1 51 5m -Xu - X2j 05 j 15 j 1由于均值為0,符合K-L變換的最佳條件。如果均值不為0,則所有樣本要減去均值向 量。由于1和2的樣本數相同，所以認為他們的先驗概率相同，即:P( 1) P( 2) 0.5求出總體的自相

16、關矩陣R或協方差矩陣 C ：25.4252525.42R P( i)Exx i 1解特征方程 R I 0,求出R的特征值:1 50.4, 2 0.4求出對應于特征值的特征向量R1 1111/2 1 ， 2.21選取1對應的特征向量作為變換矩陣,由yTx得出變換后的一維模式:10991111,222. 22101111992222 , 28 .用第二類勢函數的算法進行分類(10')選擇指數型勢函數，取a =1,在二維情況下勢函數為：222 1x Xk(Xi Xk1 ) (X2 Xk2 )K(x, Xk)e11 e這里：1類為X=(0 0)T, X=(2 0)T;2類為X=(1 1)T,

17、X=(1 -1)T解：可以看出，這兩類模式是線性不可分的。算法步驟如下：第一步：取 X(1)(0,0)T 1 ,則_ 2_ 2 _22Ki(x)K(X,X(1) exp (Xi 0)(X2 0) exp (xiX2 )第二步：取 x(2)(2,0)T 1因 exp (4 0) exp( 4) 0,故 K2(x)K1(x) exp (x12 x22)第三步：取X(3)(1,1)T2因 exp (1 1) exp( 2) 0,故22-22 -K3(x)K2(x) K(x,x(3) exp (K X2 ) exp (X1 1)(X2 1) 后面同理，就是不斷將樣本帶入，如果分類正確，則勢函數保持不變

18、，即:Kki(x) Kk(x)如果分類錯誤，則有兩種情況：x(k 1)1, Kk (x(k i)0,則 Kki(x) Kk(x) K(x, x(ki)x(k 1)2 , Kk (x(k 1)0,則 Kk1(x)Kk(x) K(x,x(k 1)經過迭代，全部模式都已正確分類，因此算法收斂于判別函數。22222222得出：d(x)(x1x2)-(x11)(x21)八(x11)(x21)八(% 2)X2 eee9.有一種病，正常為1 ,不正常為2，已知:P( 1) 0.9, P( 2) 0.1現對某人進行檢查，結果為x,由概率曲線查出:P(x| 1) 0.2,P(x| 2) 0.4風險代價矩陣為:L

19、11L1206L21L2210對該檢查者進行判決：(1)用貝葉斯最小錯誤概率判別，求出判決函數和決策分界面(2)用貝葉斯最小風險判別，求出判別函數和決策分界面。解(1)：P( 1|x) P( 1)P(x| 1)P( 2|x) P( 2)P(x| 2)由于P(x|1)1P(2)1l -P(x|2)2P(1)9所以x 1O解(2):2rj(x)LjP(x| i)P( i),j 1,21 1由于P(x| 1)1 P( 2)L21 L221P(x| 2)2 P( 1) L12 L1154所以x10.闡述誤差反傳算法(BP算法)的原理，并寫出其訓練步驟 答(1)：BP算法推算過程：宿 & 此 W

20、hJ汁TJ當加入第k個輸入時，隱蔽層 h結點的輸入加權和為：kkShWihXii如果令第一層的加權矩陣為 w ,則還可以表示為：k T k sh W1 x相應節點的輸出為：yk F(sk) F(wGk)i寫成矩陣形式為：yk F(sk) F(Wxk)同樣，輸出層j結點的輸入加權和為：kkk SjWhjyhWhjF( WihX )hhi令第二次的加權矩陣為 w2 ,則可以寫成： k T k TT kSj W2 yh W2 F(Wi x )相應點的輸出：y：F(sk) F(Whjy；) FwNF( w/k)hhi寫成矩陣形式為：yk F(W2TFWiTxk)這里，各結點的閾值等效為一個連接的加權W

21、0h或W0j ,這些連接由各結點連到具有固定值-1的偏置結點，其連接加權也是可調的，同其它加權一樣參與調節過程。 誤差函數為：E(W) 1 (Tjkyk)21Tjk FwNF(w.xk)22 k,j2 k,jhi為了使誤差函數最小，用梯度下降法求得最優的加權，權值先從輸出層開始修正，然 后依次修正前層權值，因此含有反傳的含義。根據梯度下降法，由隱蔽層到輸出層的連接 的加權調節量為：Ek k k kk kWhj (Tj yj)F (Sj)yhj yhWhjkk其中；為輸出結點的誤差信號：jk F (s：)(Tjk yk) F (s：) kk T： yk1在BP算法中常采用Sigmoid函數：y F (s)s1 e其導數為：F'(s) F (s)(1 F(s) y(1 y)對應的誤差為：:yk(1 yk)(T；yk)對于輸入層到隱蔽層結點連接的加權修正量亞由，必須考慮將E(W)對亞所求導，因此利用分層鏈路法，有:WihEEkWihkyhkk kjWhjF (Sh)Xi k, jk yhWih(甘k, jk