中科院-模式識別考題

1、模式分類若可用任一個線性函數(shù)來劃分，則這些模式就稱為線性可分的，否則就是非線性可分的。一旦線性函數(shù)的系數(shù)wk被確定，這些函數(shù)就可用作模式分類的基礎(chǔ)。對于M類模式的分類，多類情況1需要M個判別函數(shù)，而多類情況2需要M*(M-1)/2個判別函數(shù)，當(dāng)M較大時，后者需要更多的判別式（這是多類情況2的一個缺點）。采用多類情況1時，每一個判別函數(shù)都要把一種類別的模式與其余M-1種類別的模式分開，而不是將一種類別的模式僅與另一種類別的模式分開。由于一種模式的分布要比M-1種模式的分布更為聚集，因此多類情況2對模式是線性可分的可能性比多類情況1更大一些（這是多類情況2的一個優(yōu)點）。答（2）廣義線性判別函數(shù)出發(fā)

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

3、有限態(tài)自動機，定義如下： 試求等價的正則文法，使得L(G)=T(A)。（10）解：設(shè)由A得一正則文法，則，由，得生成式 由，得生成式 由，得生成式 由，得生成式 由，得生成式 由，得生成式 對比實例：當(dāng)掃描字符串1110時，A按以下狀態(tài)序列接受該字符串用對應(yīng)的正則文法G推導(dǎo)，得：按有限態(tài)自動機確定正則文法給定一個有限態(tài)自動機，可確定一個正則文法，使得L(G) = T(A)。由 ，可確定：，。從求G中的生成式P可按如下原則：(1)若，則(2)若，則K-均值算法聚類：K=2，初始聚類中心為，數(shù)據(jù)為：（10） 算法：第一步：選個初始聚類中心，其中括號內(nèi)的序號為尋找聚類中心的迭代運算的次序號?？蛇x開始

4、的 個模式樣本的向量值作為初始聚類中心。第二步：逐個將需分類的模式樣本按最小距離準則分配給個聚類中心中的某一個。即，則，其中 為迭代運算的次序號，第一次迭代，表示第個聚類，其聚類中心為。第三步：計算各個聚類中心的新的向量值，求各聚類域中所包含樣本的均值向量：其中為第個聚類域中所包含的樣本個數(shù)。以均值向量作為新的聚類中心，可使如下聚類準則函數(shù)最?。涸谶@一步中要分別計算K個聚類中的樣本均值向量，所以稱之為K-均值算法。第四步：若，則返回第二步，將模式樣本逐個重新分類，重復(fù)迭代運算；若，則算法收斂，計算結(jié)束。給出兩類模式分布，每一列代表一個樣本： ： ：試用K-L變換來做一維特征的提?。?2）。解：

5、首先將所有樣本看作一個整體，求出樣本均值向量： 由于均值為0，符合K-L變換的最佳條件。如果均值不為0，則所有樣本要減去均值向量。由于和的樣本數(shù)相同，所以認為他們的先驗概率相同，即：求出總體的自相關(guān)矩陣或協(xié)方差矩陣： 解特征方程，求出的特征值： 求出對應(yīng)于特征值的特征向量： 選取對應(yīng)的特征向量作為變換矩陣，由得出變換后的一維模式： ： ：用第二類勢函數(shù)的算法進行分類（10）選擇指數(shù)型勢函數(shù)，取=1，在二維情況下勢函數(shù)為：這里：1類為x=(0 0)T, x=(2 0)T；2類為x=(1 1)T, x=(1 -1)T解：可以看出，這兩類模式是線性不可分的。算法步驟如下：第一步：取 ，則 第二步：取

6、因，故 第三步：取因，故 后面同理，就是不斷將樣本帶入，如果分類正確，則勢函數(shù)保持不變，即： 如果分類錯誤，則有兩種情況：，則，則經(jīng)過迭代，全部模式都已正確分類，因此算法收斂于判別函數(shù)。得出：有一種病，正常為 ，不正常為 ，已知： 現(xiàn)對某人進行檢查，結(jié)果為，由概率曲線查出： 風(fēng)險代價矩陣為： 對該檢查者進行判決：用貝葉斯最小錯誤概率判別，求出判決函數(shù)和決策分界面。用貝葉斯最小風(fēng)險判別，求出判別函數(shù)和決策分界面。解（1）： 由于 所以。解（2）： 由于 所以。闡述誤差反傳算法（BP算法）的原理，并寫出其訓(xùn)練步驟。答（1）：BP算法推算過程：當(dāng)加入第k個輸入時，隱蔽層h結(jié)點的輸入加權(quán)和為：如果令第

7、一層的加權(quán)矩陣為 ，則還可以表示為： 相應(yīng)節(jié)點的輸出為：寫成矩陣形式為： 同樣，輸出層j結(jié)點的輸入加權(quán)和為：令第二次的加權(quán)矩陣為，則可以寫成： 相應(yīng)點的輸出：寫成矩陣形式為： 這里，各結(jié)點的閾值等效為一個連接的加權(quán)或，這些連接由各結(jié)點連到具有固定值-1的偏置結(jié)點，其連接加權(quán)也是可調(diào)的，同其它加權(quán)一樣參與調(diào)節(jié)過程。誤差函數(shù)為：為了使誤差函數(shù)最小，用梯度下降法求得最優(yōu)的加權(quán)，權(quán)值先從輸出層開始修正，然后依次修正前層權(quán)值，因此含有反傳的含義。根據(jù)梯度下降法，由隱蔽層到輸出層的連接的加權(quán)調(diào)節(jié)量為：其中為輸出結(jié)點的誤差信號：在BP算法中常采用Sigmoid函數(shù)：其導(dǎo)數(shù)為： 對應(yīng)的誤差為：對于輸入層到隱蔽

8、層結(jié)點連接的加權(quán)修正量，必須考慮將對求導(dǎo)，因此利用分層鏈路法，有：其中：這樣就可以根據(jù)和分別調(diào)整輸出層和隱層的權(quán)值了。BP訓(xùn)練算法實現(xiàn)步驟準備：設(shè)網(wǎng)絡(luò)具有m層，表示第m層中第j個結(jié)點的輸出，（零層輸出）等于，即第j個輸入。表示從到的連接加權(quán)。這里，m代表層號，而不是向量的類號。1.（初始化加權(quán)矩陣）將各加權(quán)隨機置為小的隨機數(shù)?？捎镁鶆蚍植嫉碾S機數(shù)，以保證網(wǎng)絡(luò)不被大的加權(quán)值所飽和。2.（輸入數(shù)據(jù)）從訓(xùn)練數(shù)據(jù)組中選一數(shù)據(jù)對，將輸入向量加到輸入層（m=0），使得對所有端點i：，k表示向量類號。3.（輸出預(yù)測數(shù)據(jù)）信號通過網(wǎng)絡(luò)向前傳播，即利用關(guān)系式：計算從第一層開始的各層內(nèi)每個結(jié)點i的輸出，直到輸出層的每個結(jié)點的輸出計算完為止。4.（計算輸出層誤差）計算輸出層每個結(jié)點的誤差值，對Sigmod函數(shù)：它是由實際輸出和要求目標值之差獲