模式識別期末試題

1、一、填空與選擇填空（本題答案寫在此試卷上，30分）1、模式識別系統(tǒng)的基本構(gòu)成單元包括：模式采集、特征提取與選擇和模式分類。2、統(tǒng)計模式識別中描述模式的方法一般使用特真矢量;句法模式識別中模式描述方法一般有樹_、網(wǎng)。3、聚類分析算法屬于（1）;判別域代數(shù)界面方程法屬于（3）。（1）無監(jiān)督分類（2）有監(jiān)督分類（3）統(tǒng)計模式識別方法（4）句法模式識別方法4、若描述模式的特征量為0-1二值特征量，則一般采用（4）進(jìn)行相似性度量。（1）距離測度（2）模糊測度（3）相似測度（4）匹配測度5、下列函數(shù)可以作為聚類分析中的準(zhǔn)則函數(shù)的有(1)(3)(4)j-1l-l（1）人耶泮J二%sjJ=2網(wǎng)-河網(wǎng)-如（4）

2、 二6、Fisher線性判別函數(shù)的求解過程是將N維特征矢量投影在（2）中進(jìn)行。（1）二維空間（2）一維空間（3）N-1維空間7、下列判別域界面方程法中只適用于線性可分情況的算法有（1）;線性可分、不可分都適用的有(3)（1）感知器算法(2)H-K算法（3）積累位勢函數(shù)法8、下列四元組中滿足文法定義的有(1)(2)(4)。(1) (AB,0,1,-01,At0A1,At1A0,BtBA,Bt0,A)(A,0,1,A>0,A>0A,A)(3)(S,ab,S：00S,S-；11S,S：00,S.11,S(4) (丹,0,1,A>01,A>0A1,A>1A0,A)9、影響

3、層次聚類算法結(jié)果的主要因素有（計算模式距離的測度、（聚類準(zhǔn)則、類間距離門限、預(yù)定的類別數(shù)目）。10、歐式距離具有（1、2）;馬式距離具有（1、2、3、4）。（1）平移不變性（2）旋轉(zhuǎn)不變性（3）尺度縮放不變性（4）不受量綱影響的特性11、線性判別函數(shù)的正負(fù)和數(shù)值大小的幾何意義是（正（負(fù)）表示樣本點位于判別界面法向量指向的正（負(fù)）半空間中；絕對值正比于樣本點到判別界面的距離。）。12、感知器算法工。（1）只適用于線性可分的情況；（2）線性可分、不可分都適用。13、積累勢函數(shù)法較之于H-K算法的優(yōu)點是（該方法可用于非線性可分情況（也可用于線性可分情況）;K（x）=kK（x,Xk）一位勢函數(shù)K（x,

4、xk）與積累位勢函數(shù)K（x）的關(guān)系為（XkX）。14、在統(tǒng)計模式分類問題中，聶曼-皮爾遜判決準(zhǔn)則主要用于（某一種判決錯誤較另一種判決錯誤更為重要）情況；最小最大判決準(zhǔn)則主要用于（先驗概率未知的）情況。15、“特征個數(shù)越多越有利于分類”這種說法正確嗎？（錯誤）。特征選擇的主要目的是（從n個特征中選出最有利于分類的的m個特征（m<n）,以降低特征維數(shù)）。一般在（可分性判據(jù)對特征個數(shù)具有單調(diào)性）和（Cnm>>n）的條件下，可以使用分支定界法以減少計算量。16、散度Jij越大，說明母類模式與切類模式的分布（差別越大）;當(dāng)類模式與類模式的分布相同時，Jij=（0）。17、已知有限狀態(tài)自

5、動機(jī)Af=（Z,Q,0q0,F）,£=0,1;Q=q0,q1;&&q0,0）=q1,6（q0,1）=q1,如1,0）=q0,gq1,1）=q0；q0=q0;F=q0?，F(xiàn)有輸入字符串：（a）00011101011,（b）1100110011,（c）101100111000,（d）0010011，試問，用Af對上述字符串進(jìn)行分類的結(jié)果為（>1:a,d;32:b,c）o18、影響聚類算法結(jié)果的主要因素有（_）。已知類別的樣本質(zhì)量；分類準(zhǔn)則；特征選取；模式相似性測度。19、模式識別中，馬式距離較之于歐式距離的優(yōu)點是（）。平移不變性；旋轉(zhuǎn)不變性；尺度不變性；考慮了模式的分

6、布。20、基于二次準(zhǔn)則函數(shù)的H-K算法較之于感知器算法的優(yōu)點是（_）?？梢耘袆e問題是否線性可分；其解完全適用于非線性可分的情況；其解的適應(yīng)性更好；計算量小。21、影響基本C均值算法的主要因素有（）。樣本輸入順序；模式相似性測度；聚類準(zhǔn)則；初始類心的選取。22、位勢函數(shù)法的積累勢函數(shù)K（x）的作用相當(dāng)于Bayes判決中的（_）。先驗概率；后驗概率；類概率密度；類概率密度與先驗概率的乘積。23、在統(tǒng)計模式分類問題中，當(dāng)先驗概率未知時，可以使用（_）。最小損失準(zhǔn)則；最小最大損失準(zhǔn)則；最小誤判概率準(zhǔn)則；N-P判決。24、在（）情況下，用分支定界法做特征選擇計算量相對較少。Gd>>n,（n為

7、原特征個數(shù)，d為要選出的特征個數(shù)）；樣本較多；選用的可分性判據(jù)J對特征數(shù)目單調(diào)不減；選用的可分性判據(jù)J具有可加性。25、散度Jd是根據(jù)（）構(gòu)造的可分性判據(jù)。先驗概率；后驗概率；類概率密度；信息嫡；幾何距離。26、似然函數(shù)的概型已知且為單峰，則可用（_）估計該似然函數(shù)。矩估計；最大似然估計；Bayes估計；Bayes學(xué)習(xí)；Parzen窗法。27、Kn近鄰元法較之Parzen窗法的優(yōu)點是（_）。所需樣本數(shù)較少；穩(wěn)定性較好；分辨率較高；連續(xù)性較好。28、從分類的角度講，用DKLT做特征提取主要利用了DKLT的性質(zhì)：（一_）。變換產(chǎn)生的新分量正交或不相關(guān)；以部分新的分量表示原矢量均方誤差最?。皇棺儞Q后

8、的矢量能量更趨集中；29、一般，剪輯k-NN最近鄰方法在（_）的情況下效果較好。樣本數(shù)較大；樣本數(shù)較?。粯颖境蕡F(tuán)狀分布；樣本呈鏈狀分布。30、如果以特征向量的相關(guān)系數(shù)作為模式相似性測度，則影響聚類算法結(jié)果的主要因素有（_）。已知類別樣本質(zhì)量；分類準(zhǔn)則；特征選取；量綱。二、（15分）簡答及證明題（1）影響聚類結(jié)果的主要因素有那些？（2）證明馬氏距離是平移不變的、非奇異線性變換不變的。答：（1）分類準(zhǔn)則，模式相似性測度，特征量的選擇，量綱。（2）證明：（2分）（2分）（1分）戶（片用）二）-幻'丁1國-即JJ儲1椎1*£二一£尺冊a三、（8分）說明線性判別函數(shù)的正負(fù)和數(shù)

9、值大小在分類中的意義并證明之。答：（1）（4分）d的絕對值口同正比于？到超平面d二。的距離4式（1-1）的分子為判別函數(shù)絕對值，上式表明，的值口正比于7到超平面4=。的距離4,一個特征矢量代入判別函數(shù)后所得值的絕對值越大表明該特征點距判別界面越遠(yuǎn)。（2）（4分）判別函數(shù)值的正負(fù)表示出特征點位于哪個半空間中，或者換句話說，表示特征點位于界面的哪一側(cè)。四、（12分，每問4分）在目標(biāo)識別中，假定有農(nóng)田和裝甲車兩種類型，類型和類型如分別代表農(nóng)田和裝甲車，它們的先驗概率分別為0.8和0.2,損失函數(shù)如表1所示。現(xiàn)在做了三次試驗，獲得三個樣本的類概率密度如下：?（田?。?.3,0.1,0.6眄）:0.7

10、,0.8,0.3（1） 試用貝葉斯最小誤判概率準(zhǔn)則判決三個樣本各屬于哪一個類型；（2） 假定只考慮前兩種判決，試用貝葉斯最小風(fēng)險準(zhǔn)則判決三個樣本各屬于哪一類；（3） 把拒絕判決考慮在內(nèi)，重新考核三次試驗的結(jié)果。表1判決必叫%14%51%11_33解：由題可知：W=0.W）=0.3而而兩二，戶優(yōu)|可）_1尸每闖2F（馬|叼）8尸（為I的）（1） （4分）根據(jù)貝葉斯最小誤判概率準(zhǔn)則知：戶"11%）_PF（qI可）P）伉Iq）?二£尸（WI啊）f）,則可以任判；尸國I町）尸，則判為四；叼）尸，則判為Q；尸）（）4.3m4（2） （4分）由題可知：?3）4-4）07（4-1）7則尸

11、（XI弓）力，判為蜘;色）J產(chǎn)每1的）7,判為4；F（均J尸（弓I的）7,判為01；（3） （4分）對于兩類問題，對于樣本JT,假設(shè)PQ）已知，有#（勺Iz）=I離）式%I制+為%IIx）=_一|一）尸（彳I電）F（研）+2（%硒）P（x|的）尸（町）=PW則對于第一個樣本，民工）=5x0214x0.21產(chǎn)尸，蛔=2x0.21陽）z-103n<、0.59zI、0.24咫%二4&=否7歐%二一尸0)尸尸，則拒判;I、078»、219n,、051R（%Ik）=玄r，*（0'/工）=文-尸。）尸尸，拒判。五、i.監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)的區(qū)別：監(jiān)督學(xué)習(xí)方法用來對數(shù)據(jù)實現(xiàn)分

12、類，分類規(guī)則通過訓(xùn)練獲得。該訓(xùn)練集由帶分類號的數(shù)據(jù)集組成,因此監(jiān)督學(xué)習(xí)方法的訓(xùn)練過程是離線的。非監(jiān)督學(xué)習(xí)方法不需要單獨的離線訓(xùn)練過程，也沒有帶分類號（標(biāo)號）的訓(xùn)練數(shù)據(jù)集，一般用來對數(shù)據(jù)集進(jìn)行分析，如聚類，確定其分布的主分量等。（實例：道路圖）就道路圖像的分割而言，監(jiān)督學(xué)習(xí)方法則先在訓(xùn)練用圖像中獲取道路象素與非道路象素集，進(jìn)行分類器設(shè)計，然后用所設(shè)計的分類器對道路圖像進(jìn)行分割。使用非監(jiān)督學(xué)習(xí)方法，則依據(jù)道路路面象素與非道路象素之間的聚類分析進(jìn)行聚類運算，以實現(xiàn)道路圖像的分割。2.線性分類器三種最優(yōu)準(zhǔn)則：Fisher準(zhǔn)則：根據(jù)兩類樣本一般類內(nèi)密集，類間分離的特點，尋找線性分類器最佳的法線向量方向，

13、使兩類樣本在該方向上的投影滿足類內(nèi)盡可能密集，類間盡可能分開。該種度量通過類內(nèi)離散矩陣Sw和類間離散矩陣Sb實現(xiàn)。感知準(zhǔn)則函數(shù)：準(zhǔn)則函數(shù)以使錯分類樣本到分界面距離之和最小為原則。其優(yōu)點是通過錯分類樣本提供的信息對分類器函數(shù)進(jìn)行修正，這種準(zhǔn)則是人工神經(jīng)元網(wǎng)絡(luò)多層感知器的基礎(chǔ)。支持向量機(jī)：基本思想是在兩類線性可分條件下，所設(shè)計的分類器界面使兩類之間的間隔為最大，它的基本出發(fā)點是使期望泛化風(fēng)險盡可能小。一、試說明Mahalanobis距離平方的定義，到某點的Mahalanobis距離平方為常數(shù)的軌跡的幾何意義，它與歐氏距離的區(qū)別與聯(lián)系。答：Mahalanobis距離的平方定義為：r2（x,u）=（x

14、-u）TS-1（x-u）其中x,u為兩個數(shù)據(jù)，是一個正定對稱矩陣（一般為協(xié)方差矩陣）。根據(jù)定義，距某一點的Mahalanobis距離相等點的軌跡是超橢球，如果是單位矩陣2,則Mahalanobis距離就是通常的歐氏距離。二、試說明用監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)兩種方法對道路圖像中道路區(qū)域的劃分的基本做法，以說明這兩種學(xué)習(xí)方法的定義與它們間的區(qū)別。答：監(jiān)督學(xué)習(xí)方法用來對數(shù)據(jù)實現(xiàn)分類，分類規(guī)則通過訓(xùn)練獲得。該訓(xùn)練集由帶分類號的數(shù)據(jù)集組成，因此監(jiān)督學(xué)習(xí)方法的訓(xùn)練過程是離線的。非監(jiān)督學(xué)習(xí)方法不需要單獨的離線訓(xùn)練過程，也沒有帶分類號（標(biāo)號）的訓(xùn)練數(shù)據(jù)集，一般用來對數(shù)據(jù)集進(jìn)行分析，如聚類，確定其分布的主分量等。就

15、道路圖像的分割而言，監(jiān)督學(xué)習(xí)方法則先在訓(xùn)練用圖像中獲取道路象素與非道路象素集，進(jìn)行分類器設(shè)計，然后用所設(shè)計的分類器對道路圖像進(jìn)行分割。使用非監(jiān)督學(xué)習(xí)方法，則依據(jù)道路路面象素與非道路象素之間的聚類分析進(jìn)行聚類運算，以實現(xiàn)道路圖像的分割。三、試述動態(tài)聚類與分級聚類這兩種方法的原理與不同。答：動態(tài)聚類是指對當(dāng)前聚類通過迭代運算改善聚類；分級聚類則是將樣本個體，按相似度標(biāo)準(zhǔn)合并，隨著相似度要求的降低實現(xiàn)合并。四、試說明以下問題求解是基于監(jiān)督學(xué)習(xí)或是非監(jiān)督學(xué)習(xí)：1.求數(shù)據(jù)集的主分量2.漢字識別3.自組織特征映射4.CT圖像的分割答：1、求數(shù)據(jù)集的主分量是非監(jiān)督學(xué)習(xí)方法；2-漢字識別對待識別字符加上相應(yīng)類

16、別號一一有監(jiān)督學(xué)習(xí)方法；3、自組織特征映射一一將高維數(shù)組按保留近似度向低維映射一一非監(jiān)督學(xué)習(xí)；4、CT圖像分割一一按數(shù)據(jù)自然分布聚類一一非監(jiān)督學(xué)習(xí)方法；五、試列舉線性分類器中最著名的三種最佳準(zhǔn)則以及它們各自的原理。答：線性分類器三種最優(yōu)準(zhǔn)則：Fisher準(zhǔn)則：根據(jù)兩類樣本一般類內(nèi)密集，類間分離的特點，尋找線性分類器最佳的法線向量方向，使兩類樣本在該方向上的投影滿足類內(nèi)盡可能密集，類間盡可能分開。該種度量通過類內(nèi)離散矩陣Sw和類間離散矩陣Sb實現(xiàn)。感知準(zhǔn)則函數(shù)：準(zhǔn)則函數(shù)以使錯分類樣本到分界面距離之和最小為原則。其優(yōu)點是通過錯分類樣本提供的信息對分類器函數(shù)進(jìn)行修正，這種準(zhǔn)則是人工神經(jīng)元網(wǎng)絡(luò)多層感知

17、器的基礎(chǔ)。支持向量機(jī)：基本思想是在兩類線性可分條件下，所設(shè)計的分類器界面使兩類之間的間隔為最大，它的基本出發(fā)點是使期望泛化風(fēng)險盡可能小。十、對一副道路圖像，希望把道路部分劃分出來，可以采用以下兩種方法：1 .在該圖像中分別在道路部分與非道路部分畫出一個窗口，把在這兩個窗口中的象素數(shù)據(jù)作為訓(xùn)練集，用Fisher準(zhǔn)則方法求得分類器參數(shù)，再用該分類器對整幅圖進(jìn)行分類。2 .將整幅圖的每個象素的屬性記錄在一張數(shù)據(jù)表中，然后用某種方法將這些數(shù)據(jù)按它們的自然分第6頁共9頁布狀況劃分成兩類。因此每個象素就分別得到相應(yīng)的類別號，從而實現(xiàn)了道路圖像的分割。試問以上兩種方法哪一種是監(jiān)督學(xué)習(xí)，哪個是非監(jiān)督學(xué)習(xí)？答：

18、第一種方法中標(biāo)記了兩類樣本的標(biāo)號，需要人手工干預(yù)訓(xùn)練過程，屬于監(jiān)督學(xué)習(xí)方法；第二種方法只是依照數(shù)據(jù)的自然分布，把它們劃分成兩類，屬于非監(jiān)督學(xué)習(xí)方法。十三、試分析五種常用決策規(guī)則思想方法的異同。答、五種常用決策是：1. 基于最小錯誤率的貝葉斯決策，利用概率論中的貝葉斯公式，得出使得錯誤率最小的分類規(guī)則。2. 基于最小風(fēng)險的貝葉斯決策，引入了損失函數(shù)，得出使決策風(fēng)險最小的分類。當(dāng)在01損失函數(shù)條件下，基于最小風(fēng)險的貝葉斯決策變成基于最小錯誤率的貝葉斯決策。3. 在限定一類錯誤率條件下使另一類錯誤率最小的兩類別決策。4. 最大最小決策：類先驗概率未知，考察先驗概率變化對錯誤率的影響，找出使最小貝葉斯

19、奉獻(xiàn)最大的先驗概率，以這種最壞情況設(shè)計分類器。5. 序貫分類方法，除了考慮分類造成的損失外，還考慮特征獲取造成的代價，先用一部分特征分類，然后逐步加入性特征以減少分類損失，同時平衡總的損失，以求得最有效益。十四、假設(shè)在某個地區(qū)細(xì)胞識別中正常（w）和異常（W2）兩類先驗概率分別為P（wi）=0.9,P（W2）=0.1,現(xiàn)有一待識別的細(xì)胞，其觀察值為X,從類條件概率密度分布曲線上查得P（xw1）=0.2,P（x/w2）=0.4,并且已知1=0,%2=6,£21=1,，也=0試對該細(xì)胞x用一下兩種方法進(jìn)行分類：1.基于最小錯誤率的貝葉斯決策；2.基于最小風(fēng)險的貝葉斯決策；請分析兩種結(jié)果的異

20、同及原因。解：利用貝葉斯公式,分別計算出叱及叫的后驗概率,xI戶a汕（電）才力（工嗎）產(chǎn)（嗎）0.2X0.9+0,4X0.根據(jù)貝葉斯決策規(guī)則式（2-2）,有Pt&i）=,=0J82所以合理的決焚是把x婦類于正常狀態(tài)口2.解:已知條件為尸(叱)=0/p(jr|fl)=0.4*廣6心二。尸(修|jf)=0r1B2fY%)9*力(1=MA)jC'(蒞11，根據(jù)1的什莫維果可知后驗概率為尸(的|工)=0,磯8,再計算出條件風(fēng)險R?|tj=£"Pjt)二'P(g.)1,092K(%x)=JaiP(fl»i|jr)=fl.818由于RUix)>R

21、U-x)即決策為她的條件風(fēng)險小于決策為助的條件且險，因此我們采取決策行動的，即判斷待訊別的細(xì)胞工為叫類一異常細(xì)胞，招1與2相對比，其分類結(jié)果正好相反,這是因為這里影響決策結(jié)果的因素又多了一個，即損失'而且兩類錯誤決策所造成的損失相差很懸殊，因此“損失”就挺了主導(dǎo)作用.十五、有線性判別函數(shù)，為什么還要引進(jìn)非線性判別函數(shù)？分析由“線性判別函數(shù)”向“非線性判別函數(shù)”推廣的思想和方法。答：實際中有很多模式識別問題并不是線性可分的，這時就需要采用非線性分類器，比如當(dāng)兩類樣本分不具有多峰性質(zhì)并互相交錯時，簡單的線性判別函數(shù)往往會帶來較大的分類錯誤。這時，樹分類器作為一種分段線性分類器，常常能有效地

22、應(yīng)用于這種情況。十六、1.什么是特征選擇？2.什么是Fisher線性判別？答：1.特征選擇就是從一組特征中挑選出一些最有效的特征以達(dá)到降低特征空間維數(shù)的目的。2.Fisher線性判別：可以考慮把d維空間的樣本投影到一條直線上，形成一維空間，即把維數(shù)壓縮到一維，這在數(shù)學(xué)上容易辦到，然而，即使樣本在d維空間里形成若干緊湊的互相分得開的集群，如果把它們投影到一條任意的直線上，也可能使得幾類樣本混在一起而變得無法識別。但是在一般情況下，總可以找到某個方向，使得在這個方向的直線上，樣本的投影能分開得最好。問題是如何根據(jù)實際情況找到這條最好的、最易于分類的投影線，這就是Fisher算法所要解決的基本問題。十七、寫出兩類和多類情況下最小風(fēng)險貝葉斯決策判別函數(shù)和決策面方程。兩類別問