1、.復(fù)習(xí)復(fù)習(xí)1模式和模式識(shí)別的概念 1）模式：對(duì)某些感興趣的客體的定量的或結(jié)構(gòu)的描述。模式類是具有某些共同特性的模式的集合。 2）模式識(shí)別：研究一種自動(dòng)技術(shù)，依靠這種技術(shù)，計(jì)算機(jī)將自動(dòng)地（或人盡量少地干涉）把待別識(shí)模式分配到各自的模式類中去。.復(fù)習(xí)復(fù)習(xí)2 模式識(shí)別系統(tǒng)組成學(xué)習(xí)過程判決過程分類規(guī)則訓(xùn)練分類決策數(shù)據(jù)獲取預(yù)處理特征選擇 或提取模式識(shí)別系統(tǒng)框圖 .復(fù)習(xí)復(fù)習(xí)1） 監(jiān)督分類：需要依靠已知類別的訓(xùn)練樣本集，按照他們特征向量的分布來確定判別函數(shù)，然后利用判別函數(shù)對(duì)未知模式進(jìn)行分類。需要足夠的先驗(yàn)知識(shí)。 判別。需要有足夠的先驗(yàn)知識(shí)。2） 非監(jiān)督分類：用于沒有先驗(yàn)知識(shí)的情況，通常采用聚類分析的方法。

2、3 監(jiān)督分類和無監(jiān)督分類.復(fù)習(xí)復(fù)習(xí)4 模式識(shí)別整體知識(shí)結(jié)構(gòu).5 最大最小距離算法（小中取大距離算法最大最小距離算法（小中取大距離算法 ） 算法描述算法描述 選任意一模式樣本做為第一聚類中心Z1。 選擇離Z1距離最遠(yuǎn)的樣本作為第二聚類中心Z2。 逐個(gè)計(jì)算各模式樣本與已確定的所有聚類中心之間的距離，并選出其中的最小距離。例當(dāng)聚類中心數(shù)k=2時(shí)，計(jì)算11ZX iiD22ZX iiDmin( Di1 , Di2 )，i=1，N（N個(gè)最小距離） 復(fù)習(xí)復(fù)習(xí). 將樣本 按最近距離劃分到相應(yīng)聚類中心對(duì)應(yīng)的類別中。Nii, 2 , 1,X 重復(fù)步驟，直到?jīng)]有新的聚類中心出現(xiàn)為止。 在所有最小距離中選出最大距離，

3、如該最大值達(dá)到 的一定分?jǐn)?shù)比值( 閾值T ) 以上，則相應(yīng)的樣本點(diǎn)取為新的聚類中心，返回；否則，尋找聚類中心的工作結(jié)束。21ZZ 10,.,2 , 1),maxmin(2121ZZNiDDii若（：用試探法取為一固定分?jǐn)?shù)，如1/2。）則Z3存在。例k =2時(shí)復(fù)習(xí)復(fù)習(xí).例2.1 對(duì)圖示模式樣本用最大最小距離算法進(jìn)行聚類分析。 選選Z1=X1距距Z1最遠(yuǎn)，選為最遠(yuǎn)，選為Z2。計(jì)算。計(jì)算T。對(duì)應(yīng)最小距離對(duì)應(yīng)最小距離中的最大值，中的最大值，且且T，選作，選作Z3。結(jié)果：Z1=X1；Z2=X6； Z3=X7 。 用全體模式對(duì)三個(gè)聚類中心計(jì)算最小距離中的最大值，無T 情況，停止尋找中心。 聚類802121

4、21ZZT10個(gè)最小距離中，X7對(duì)應(yīng)的距離T,73XZ.算法描述算法描述1）N個(gè)初始模式樣本自成一類，即建立N 類：計(jì)算各類之間（即各樣本間）的距離，得一NN維距離矩陣D(0)。“0”表示初始狀態(tài)。)0(,),0(),0(21NGGG(G_Group)6 層次聚類法層次聚類法2）假設(shè)已求得距離矩陣D(n)（n為逐次聚類合并的次數(shù)），找出D(n)中的最小元素，將其對(duì)應(yīng)的兩類合并為一類。由此建立新的分類：3）計(jì)算合并后新類別之間的距離，得D(n+1)。4）跳至第2步，重復(fù)計(jì)算及合并。復(fù)習(xí)復(fù)習(xí). 結(jié)束條件：結(jié)束條件：1）取距離閾值T，當(dāng)D(n)的最小分量超過給定值 T 時(shí)，算法停 止。所得即為聚類結(jié)

5、果。2）或不設(shè)閾值T，一直將全部樣本聚成一類為止，輸出聚類的分 級(jí)樹。復(fù)習(xí)復(fù)習(xí).T10 , 2 , 1 , 3 , 0XT20 , 1 , 0 , 3 , 1XT31 , 0 , 0 , 3 , 3XT40 , 2 , 0 , 1 , 1XT51 , 2 , 1 , 2 , 3XT60 , 1 , 1 , 1 ,4X例：給出6個(gè)五維模式樣本如下，按最短距離準(zhǔn)則進(jìn)行系統(tǒng)聚類分類。計(jì)算各類間歐氏距離：解：（1）將每一樣本看作單獨(dú)一類，得：11)0(XG22)0(XG33)0(XG44)0(XG55)0(XG66)0(XG301101) 0 (2121225152241422313222122211

6、12112xxxxxxxxxxDXX1512103)0(212213D)0(34D)0(35D)0(36D， ， ， ；) 0 (14D) 0 (15D) 0(16D) 0(23D) 0(24D) 0(25D) 0(26D；.) 0(1G)0(2G)0(3G)0(4G)0(5G)0(6G)0(1G)0(2G3)0(3G156)0(4G6513)0(5G11867)0(6G21148114（2）將最小距離 對(duì)應(yīng)的類 和 合并為1類，得 新的分類。3)0(1G) 0(2G)0() 1 (44GG)0() 1 (55GG)0(),0() 1 (2112GGG)0() 1 (33GG)0() 1 (6

7、6GG計(jì)算聚類后的距離矩陣D(1)：由D(0) 遞推出D(1) 。得距離矩陣D(0)：.) 0(1G)0(2G)0(3G)0(4G)0(5G)0(6G)0(1G)0(2G3)0(3G156)0(4G6513)0(5G11867)0(6G21148114) 1 (12G) 1 (3G) 1 (4G) 1 (5G) 1 (6G) 1 (12G) 1 (3G6) 1 (4G513) 1 (5G867) 1 (6G148114（3）將D(1)中最小值 對(duì)應(yīng)的類合為一類， 得D(2)。4)2(12G)2(3G)2(4G)2(56G) 2(12G)2(3G6)2(4G513) 2(56G867.（4）將D

8、(2)中最小值 對(duì)應(yīng)的類合為一類，得D(3)。5)2(12G)2(3G)2(4G)2(56G) 2(12G)2(3G6)2(4G513) 2(56G867) 3(124G) 3(3G)3(56G) 3(124G) 3(3G6)3(56G76若給定的閾值為 ，D(3)中的最小元素 ，聚類結(jié)束。5T4211,XXXG 32XG 653, XXG 若無閾值，繼續(xù)分下去，最終全部樣本歸為一類。可給出聚類過程的樹狀表示圖。13T6.65431X2X4X3X5X6X 層次聚類法的樹狀表示 類間距離類間距離閾值增大，閾值增大，分類變粗。分類變粗。.7 K-均值算法均值算法 算法描述算法描述（1）任選K個(gè)初始

9、聚類中心：Z1(1)， Z2(1)， ZK(1) （2）按最小距離原則將其余樣品分配到K個(gè)聚類中心中的某一 個(gè)。Nj：第j類的樣本數(shù)。 KjNkkjSXjj,2, 11)1(XZKjkj, 2 , 1) 1(Z（3）計(jì)算各個(gè)聚類中心的新向量值：（4）如果 ，則回到（2），將模式 樣本逐個(gè)重新分類，重復(fù)迭代計(jì)算。Kjkkjj, 2 , 1)() 1(ZZ復(fù)習(xí)復(fù)習(xí).例2.3：已知20個(gè)模式樣本如下，試用K-均值算法分類。 T10 , 0XT20 , 1XT31 , 0X T41 , 1XT51 , 2XT62 , 1XT72 , 2XT82 , 3XT96 , 6XT106 , 7XT116 ,

10、8XT127 , 6XT137 , 7XT147 , 8XT157 , 9XT168 , 7XT178 , 8XT188 , 9XT199 , 8XT209 , 9XT110 , 0) 1 ( XZT220 , 1) 1 ( XZ解： 取K=2，并選： 計(jì)算距離，聚類：10010|) 1 (|0|) 1 (|22212111ZXZXDD) 1 (1121SDDX1X： 0|) 1 (|1|) 1 (|222121ZXZXDD) 1 (2212SDDX2X：.20110|) 1 (|10100|) 1 (|2223222131ZXZXDD) 1 (1321SDDX3X： 10111|) 1 (|

11、20101|) 1 (|2224222141ZXZXDD) 1 (2412SDDX4X： 2,) 1 (1311NSXX18,.,) 1 (2205422NSXXXX，可得到： 計(jì)算新的聚類中： 5 .00100021)(211)2(311111XXXZSXN 33. 567. 5)(1811)2(20421222XXXXZSXN) 1 ()2(jjZZ2 , 1j 判斷：，故返回第步。. 從新的聚類中心得：|)2(|)2(|212111ZXZXDD) 2(11SX1X： |)2(|)2(|22021201ZXZXDD) 2(220S X20X： 8,)2(18211NSXXX12,.,)2(

12、2201092NSXXX有： 計(jì)算聚類中心： 13. 125. 1)(811)3(8212111XXXXZSXN 33. 767. 7)(1211) 3(201092222XXXXZSXN.)2() 3(jjZZ2 , 1j 返回第步，以Z1(3)， Z2(3)為中心進(jìn)行聚類。 以新的聚類中心分類，求得的分類結(jié)果與前一次迭代結(jié)果相 同：)2() 3(11SS)2() 3(22SS 計(jì)算新聚類中心向量值，聚類中心與前一次結(jié)果相同，即： 2, 1,3)4(jjjZZ) 3()4(jjZZ33.767.7,13.125.121ZZ ，故算法收斂，得聚類中心為結(jié)果圖示：.圖2.10 K-均值算法聚類結(jié)

13、果X1X4X3X5X8X9X7X10X2X6x1x213579135790X11X12X13X14X15X16X17X18X19X2013.125.11Z33. 767. 72Z. 上述K-均值算法，其類型數(shù)目假定已知為K個(gè)。當(dāng)K未知時(shí)，可以令K逐漸增加， 此時(shí)J j 會(huì)單調(diào)減少。最初減小速度快，但當(dāng)K 增加到一定數(shù)值時(shí)，減小速度會(huì)減慢，直到K =總樣本數(shù)N 時(shí)，Jj = 0。JjK關(guān)系曲線如下圖：8 聚類準(zhǔn)則函數(shù)聚類準(zhǔn)則函數(shù)Jj與與K的關(guān)系曲線的關(guān)系曲線JjA135724608109K 曲線的拐點(diǎn) A 對(duì)應(yīng)著接近最優(yōu)的K值（J 值減小量、計(jì)算量以及分類效果的權(quán)衡）。 并非所有的情況都容易找到

14、關(guān)系曲線的拐點(diǎn)。迭代自組織的數(shù)據(jù)分析算法可以確定模式類的個(gè)數(shù)K 。.ii兩分法(1)多類情況1： 用線性判別函數(shù)將屬于i類的模式與其余不屬于i類的模式分開。將某個(gè)待分類模式 X 分別代入 M 個(gè)類的d (X)中，若只有di(X)0，其他d(X)均0的條件超過一個(gè)，或全部的di(X)Tik XW()=1+kW( )ickXW+( )kW( )0Tik XW若( )0Tik XW若（3）分析分類結(jié)果：只要有一個(gè)錯(cuò)誤分類，回到（2），直至 對(duì)所有樣本正確分類。 分類正確時(shí)，對(duì)權(quán)向量“賞”這里用“不罰”，即權(quán)向量不變；分類錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”對(duì)其修改，向正確的方向轉(zhuǎn)換。感知器算法是一種賞罰過程：感知

15、器算法是一種賞罰過程：.例例3.8 已知兩類訓(xùn)練樣本解：所有樣本寫成增廣向量形式； 進(jìn)行規(guī)范化處理，屬于2的樣本乘以(1)。T11 , 0 , 0XT21 , 1 , 0XT31, 0 , 1 XT41, 1, 1X用感知器算法求出將模式分為兩類的權(quán)向量解和判別函數(shù)。 :1T10,0X:2T21 ,0XT30, 1XT41 , 1X.任取W(1)=0，取c=1，迭代過程為：第一輪： 0,1000 , 0 , 0) 1 (1TXWT11 , 0 , 0) 1 () 2(, 0XWW故1,1101 , 0 , 0)2(2TXWT1 , 0 , 0) 2() 3 (, 0WW故-1,1-01-1 ,

16、 0 , 0)3(3TXWT30 , 0 , 1-) 3 () 4(, 0XWW故1,1-1-1-0 , 0 , 1-)4(4TXWT0 , 0 , 1-) 4() 5 (, 0WW故有兩個(gè)WT(k)Xi 0的情況（錯(cuò)判），進(jìn)行第二輪迭代。.T11T1 , 0 , 1-)5()6(,00)5(XWWXW故T2T1 , 0 , 1-(6)7(,01)6(WWXW故T33T0 , 0 , 2-)7()8(,00)7(XWWXW故T4T0 , 0 , 2-)8()9(,02)8(WWXW故第二輪：T11T1 , 0 , 2-)9()10(,00)9(XWWXW故(10)11(,01)10(2TWWX

17、W故)11()12(,01)11(3TWWXW故)12()13(,01)12(4TWWXW故第三輪：)13()14(,01)13(1TWWXW故(14)15(,01)14(2TWWXW故)15()16(,01)15(3TWWXW故)16()17(,01)16(4TWWXW故第四輪：.T1 , 0 , 2W該輪迭代的分類結(jié)果全部正確，故解向量1+2=)(1xd X相應(yīng)的判別函數(shù)為： 當(dāng)c、W(1)取其他值時(shí)，結(jié)果可能不一樣，所以感知器算法的解不是單值的。判別界面d(X)=0如圖示。.10 最小錯(cuò)誤率貝葉斯決策最小錯(cuò)誤率貝葉斯決策對(duì)兩類問題)()|()|(2211PpPpXX1X若，則)()|()

18、|(2211PpPpXX2X若，則可改寫為：統(tǒng)計(jì)學(xué)中稱l12(X)為似然比， 為似然比閾值。)()(12PP21X)|()|()(2112XXXppl12)(PP若，則 （4-8）.2111)(|)()|()|(iiiPpPpPXXX16. 02 . 095. 05 . 005. 005. 05 . 0884. 02 . 095. 05 . 005. 095. 02 . 0)|(2XP)|()|(12XXPP2X例例4.1 假定在細(xì)胞識(shí)別中，病變細(xì)胞的先驗(yàn)概率和正常細(xì)胞的先驗(yàn)概率分別為 ?，F(xiàn)有一待識(shí)別細(xì)胞，其觀察值為X，從類條件概率密度發(fā)布曲線上查得： 95. 0)(,05. 0)(21PP5

19、 . 0)|(1Xp2 . 0)|(2Xp試對(duì)細(xì)胞X進(jìn)行分類。解：方法1 通過后驗(yàn)概率計(jì)算。 .方法2：利用先驗(yàn)概率和類概率密度計(jì)算。025. 005. 05 . 0)|(11Pp X19. 095. 02 . 0)|(22Pp X)()|()|(1122PpPpXX2X，是正常細(xì)胞。.最小風(fēng)險(xiǎn)貝葉斯決策基本思想： 以各種錯(cuò)誤分類所造成的平均風(fēng)險(xiǎn)最小為規(guī)則，進(jìn)行分類決策。11 最小風(fēng)險(xiǎn)貝葉斯決策最小風(fēng)險(xiǎn)貝葉斯決策.)(|)(|)(222211212PpLPpLrXXX)(|)(|)(221211111PpLPpLrXXX2）兩類情況）兩類情況：對(duì)樣本 X121)()(XXX則若rr221)()

20、(XXX則若rr當(dāng)X 被判為1類時(shí)：當(dāng)X 被判為2類時(shí)：（4-15） （4-16） )(|)(|)(|)(|2222112122121111PpLPpLPpLPpLXXXX )(|)(|111121222212PpLLPpLLXX)()()()()|()|(111212221221PLLPLLppXX由（4-15）式：MjjjijiPpLr1)()|()(XX決策規(guī)則：.令：)|()|()(2112XXXppl，稱似然比；)()()()(111122222112PLLPLL，為閾值。 計(jì)算 。12 計(jì)算 。 X12l 定義損失函數(shù)Lij。判別步驟：112)(XX則，若 l任意判決，若1212)

21、(Xl212)(XX則，若 l)()()()()|()|(111122222121PLLPLLppXX類概率密度函數(shù)p(X |i) 也稱i的似然函數(shù).95.0)(,05.0)(21PP2 . 0)|(, 5 . 0)|(21XXpp解：計(jì)算 和 得： X12l125 . 22 . 05 . 0)|()|()(2112XXXppl 1212Xl1X例4.2 在細(xì)胞識(shí)別中，病變細(xì)胞和正常細(xì)胞的先驗(yàn)概率 分別為現(xiàn)有一待識(shí)別細(xì)胞，觀察值為X， 從類概率密度分布曲線上查得損失函數(shù)分別為L11=0，L21=10， L22=0，L12=1。按最小風(fēng)險(xiǎn)貝葉斯決策分類。為病變細(xì)胞。 9 . 105. 0)010(95. 0)01 ()()()()(111212221212PLLPLL. 經(jīng)過選擇或變換，組成識(shí)別特征，盡可能保留分類信息，在保證一定分類精度的前提下，減少特征維數(shù)，使分類器的工作即快又準(zhǔn)確。12 特征選擇和提取的目的特征選擇和提取的目的 13 特征選擇和特征提取的異同特征選擇和特征提取的異同（1）特征選擇：從L個(gè)度量值集合 中按一定準(zhǔn)