模式識(shí)別復(fù)習(xí)資料.ppt

1、復(fù)習(xí),1模式和模式識(shí)別的概念 1）模式：對(duì)某些感興趣的客體的定量的或結(jié)構(gòu)的描述。模式類(lèi)是具有某些共同特性的模式的集合。 2）模式識(shí)別：研究一種自動(dòng)技術(shù)，依靠這種技術(shù)，計(jì)算機(jī)將自動(dòng)地（或人盡量少地干涉）把待別識(shí)模式分配到各自的模式類(lèi)中去。,復(fù)習(xí),2 模式識(shí)別系統(tǒng)組成,復(fù)習(xí),1） 監(jiān)督分類(lèi)：需要依靠已知類(lèi)別的訓(xùn)練樣本集，按照他們特征向量的分布來(lái)確定判別函數(shù)，然后利用判別函數(shù)對(duì)未知模式進(jìn)行分類(lèi)。需要足夠的先驗(yàn)知識(shí)。 判別。需要有足夠的先驗(yàn)知識(shí)。 2） 非監(jiān)督分類(lèi)：用于沒(méi)有先驗(yàn)知識(shí)的情況，通常采用聚類(lèi)分析的方法。,3 監(jiān)督分類(lèi)和無(wú)監(jiān)督分類(lèi),復(fù)習(xí),4 模式識(shí)別整體知識(shí)結(jié)構(gòu),5 最大最小距離算法（小中取大

2、距離算法 ）,算法描述, 選任意一模式樣本做為第一聚類(lèi)中心Z1。, 選擇離Z1距離最遠(yuǎn)的樣本作為第二聚類(lèi)中心Z2。, 逐個(gè)計(jì)算各模式樣本與已確定的所有聚類(lèi)中心之間的距離，并選出其中的最小距離。例當(dāng)聚類(lèi)中心數(shù)k=2時(shí)，計(jì)算,復(fù)習(xí), 將樣本 按最近距離劃分到相應(yīng)聚類(lèi)中心對(duì)應(yīng) 的類(lèi)別中。, 重復(fù)步驟，直到?jīng)]有新的聚類(lèi)中心出現(xiàn)為止。, 在所有最小距離中選出最大距離，如該最大值達(dá)到 的一定分?jǐn)?shù)比值( 閾值T ) 以上，則相應(yīng)的樣本點(diǎn)取為新的聚類(lèi)中心，返回；否則，尋找聚類(lèi)中心的工作結(jié)束。,例k =2時(shí),復(fù)習(xí),例2.1 對(duì)圖示模式樣本用最大最小距離算法進(jìn)行聚類(lèi)分析。,選Z1=X1,距Z1最遠(yuǎn)，選為Z2。計(jì)算

3、T。,對(duì)應(yīng)最小距離中的最大值， 且T，選作Z3。,結(jié)果：Z1=X1；Z2=X6； Z3=X7 。, 用全體模式對(duì)三個(gè)聚類(lèi)中心計(jì)算最小距離中的最大值，無(wú)T 情況，停止尋找中心。, 聚類(lèi),算法描述,1）N個(gè)初始模式樣本自成一類(lèi)，即建立N 類(lèi)： 計(jì)算各類(lèi)之間（即各樣本間）的距離，得一NN維距離矩陣D(0)?！?”表示初始狀態(tài)。,(G_Group),6 層次聚類(lèi)法,2）假設(shè)已求得距離矩陣D(n)（n為逐次聚類(lèi)合并的次數(shù)），找出D(n)中的最小元素，將其對(duì)應(yīng)的兩類(lèi)合并為一類(lèi)。由此建立新的分類(lèi)：,3）計(jì)算合并后新類(lèi)別之間的距離，得D(n+1)。,4）跳至第2步，重復(fù)計(jì)算及合并。,復(fù)習(xí),結(jié)束條件： 1）取距

4、離閾值T，當(dāng)D(n)的最小分量超過(guò)給定值 T 時(shí)，算法停 止。所得即為聚類(lèi)結(jié)果。 2）或不設(shè)閾值T，一直將全部樣本聚成一類(lèi)為止，輸出聚類(lèi)的分 級(jí)樹(shù)。,復(fù)習(xí),例：給出6個(gè)五維模式樣本如下，按最短距離準(zhǔn)則進(jìn)行系統(tǒng)聚類(lèi)分類(lèi)。,計(jì)算各類(lèi)間歐氏距離：,解：（1）將每一樣本看作單獨(dú)一類(lèi)，得：,， ， ， ；,；,（2）將最小距離 對(duì)應(yīng)的類(lèi) 和 合并為1類(lèi)，得 新的分類(lèi)。,計(jì)算聚類(lèi)后的距離矩陣D(1)： 由D(0) 遞推出D(1) 。,得距離矩陣D(0)：,（3）將D(1)中最小值 對(duì)應(yīng)的類(lèi)合為一類(lèi)， 得D(2)。,（4）將D(2)中最小值 對(duì)應(yīng)的類(lèi)合為一類(lèi)，得D(3)。,若給定的閾值為 ，D(3)中的最小

5、元素 ，聚類(lèi)結(jié)束。,若無(wú)閾值，繼續(xù)分下去，最終全部樣本歸為一類(lèi)?？山o出聚類(lèi)過(guò)程的樹(shù)狀表示圖。,層次聚類(lèi)法的樹(shù)狀表示,類(lèi)間距離 閾值增大， 分類(lèi)變粗。,7 K-均值算法,算法描述,（1）任選K個(gè)初始聚類(lèi)中心：Z1(1)， Z2(1)， ZK(1),（2）按最小距離原則將其余樣品分配到K個(gè)聚類(lèi)中心中的某一 個(gè)。,Nj：第j類(lèi)的樣本數(shù)。,（3）計(jì)算各個(gè)聚類(lèi)中心的新向量值：,（4）如果 ，則回到（2），將模式 樣本逐個(gè)重新分類(lèi)，重復(fù)迭代計(jì)算。,，算法收斂，計(jì)算完畢。,如果,復(fù)習(xí),例2.3：已知20個(gè)模式樣本如下，試用K-均值算法分類(lèi)。,解： 取K=2，并選：, 計(jì)算距離，聚類(lèi)：,：,：,：,，可得到：

6、, 計(jì)算新的聚類(lèi)中：, 從新的聚類(lèi)中心得：,：,：,有：, 計(jì)算聚類(lèi)中心：,返回第步，以Z1(3)， Z2(3)為中心進(jìn)行聚類(lèi)。, 以新的聚類(lèi)中心分類(lèi)，求得的分類(lèi)結(jié)果與前一次迭代結(jié)果相 同：, 計(jì)算新聚類(lèi)中心向量值，聚類(lèi)中心與前一次結(jié)果相同，即：,，故算法收斂，得聚類(lèi)中心為,結(jié)果圖示：,圖2.10 K-均值算法聚類(lèi)結(jié)果,上述K-均值算法，其類(lèi)型數(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)系曲線(xiàn)如下圖：,8 聚類(lèi)準(zhǔn)則函數(shù)Jj與K的關(guān)系曲線(xiàn),曲線(xiàn)的拐點(diǎn) A

7、對(duì)應(yīng)著接近最優(yōu) 的K值（J 值減小量、計(jì)算量以及 分類(lèi)效果的權(quán)衡）。 并非所有的情況都容易找到關(guān) 系曲線(xiàn)的拐點(diǎn)。迭代自組織的數(shù)據(jù) 分析算法可以確定模式類(lèi)的個(gè)數(shù)K 。,用線(xiàn)性判別函數(shù)將屬于i類(lèi)的模式與其余不屬于i類(lèi)的 模式分開(kāi)。,識(shí)別分類(lèi)時(shí)：,9 線(xiàn)性判別函數(shù),復(fù)習(xí),對(duì)某一模式區(qū)，di(X)0 的條件超過(guò)一個(gè)，或全部 的di(X)0 ，分類(lèi)失效。 相當(dāng)于不確定區(qū)(indefinite region ，IR)。,此法將 M 個(gè)多類(lèi)問(wèn)題分成M個(gè)兩類(lèi)問(wèn)題，識(shí)別每一類(lèi)均 需M個(gè)判別函數(shù)。識(shí)別出所有的M類(lèi)仍是這M個(gè)函數(shù)。,例3.1 設(shè)有一個(gè)三類(lèi)問(wèn)題，其判別式為：,現(xiàn)有一模式，X=7,5T，試判定應(yīng)屬于哪類(lèi)

8、？并畫(huà)出三類(lèi)模式的分布區(qū)域。,解：將X=7,5T代入上三式，有：,三個(gè)判別界面分別為：,圖示如下：,步驟：,a) 畫(huà)出界面直線(xiàn)。,b) 判別界面正負(fù)側(cè)：找特殊點(diǎn)帶入。,c) 找交集。,感知器算法步驟：,（1）選擇N個(gè)分屬于1和 2類(lèi)的模式樣本構(gòu)成訓(xùn)練樣本集 X1, , XN 構(gòu)成增廣向量形式，并進(jìn)行規(guī)范化處理。任取權(quán)向量初始 值W(1)，開(kāi)始迭代。迭代次數(shù)k=1 。,（2）用全部訓(xùn)練樣本進(jìn)行一輪迭代，計(jì)算WT(k)Xi 的值，并修 正權(quán)向量。,分兩種情況，更新權(quán)向量的值：,9 感知器算法,復(fù)習(xí),c：正的校正增量。,分類(lèi)器對(duì)第i個(gè)模式做了錯(cuò)誤分類(lèi)，,權(quán)向量校正為：,統(tǒng)一寫(xiě)為：,（3）分析分類(lèi)結(jié)果

9、：只要有一個(gè)錯(cuò)誤分類(lèi)，回到（2），直至 對(duì)所有樣本正確分類(lèi)。,分類(lèi)正確時(shí)，對(duì)權(quán)向量“賞”這里用“不罰”，即權(quán)向量不變； 分類(lèi)錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”對(duì)其修改，向正確的方向轉(zhuǎn)換。,感知器算法是一種賞罰過(guò)程：,例3.8 已知兩類(lèi)訓(xùn)練樣本,解：所有樣本寫(xiě)成增廣向量形式； 進(jìn)行規(guī)范化處理，屬于2的樣本乘以(1)。,用感知器算法求出將模式分為兩類(lèi)的權(quán)向量解和判別函數(shù)。,任取W(1)=0，取c=1，迭代過(guò)程為：,第一輪：,有兩個(gè)WT(k)Xi 0的情況（錯(cuò)判），進(jìn)行第二輪迭代。,第二輪：,第三輪：,第四輪：,該輪迭代的分類(lèi)結(jié)果全部正確，故解向量,相應(yīng)的判別函數(shù)為：,當(dāng)c、W(1)取其他值 時(shí)，結(jié)果可能不一樣

10、， 所以感知器算法的解不是單值的。,判別界面d(X)=0如圖示。,10 最小錯(cuò)誤率貝葉斯決策,對(duì)兩類(lèi)問(wèn)題,可改寫(xiě)為：,統(tǒng)計(jì)學(xué)中稱(chēng)l12(X)為似然比， 為似然比閾值。,例4.1 假定在細(xì)胞識(shí)別中，病變細(xì)胞的先驗(yàn)概率和正常細(xì)胞的 先驗(yàn)概率分別為 。現(xiàn)有一待識(shí)別細(xì)胞， 其觀察值為X，從類(lèi)條件概率密度發(fā)布曲線(xiàn)上查得：,試對(duì)細(xì)胞X進(jìn)行分類(lèi)。,解：方法1 通過(guò)后驗(yàn)概率計(jì)算。,方法2：利用先驗(yàn)概率和類(lèi)概率密度計(jì)算。,，是正常細(xì)胞。,11 最小風(fēng)險(xiǎn)貝葉斯決策,2）兩類(lèi)情況：對(duì)樣本 X,當(dāng)X 被判為1類(lèi)時(shí)：,當(dāng)X 被判為2類(lèi)時(shí)：,（4-15）,（4-16）,由（4-15）式：,決策規(guī)則：,，為閾值。, 計(jì)算

11、。, 計(jì)算 。, 定義損失函數(shù)Lij。,判別步驟：,類(lèi)概率密度函數(shù) p(X |i) 也稱(chēng)i的似然函數(shù),解：計(jì)算 和 得：,例4.2 在細(xì)胞識(shí)別中，病變細(xì)胞和正常細(xì)胞的先驗(yàn)概率 分別為,現(xiàn)有一待識(shí)別細(xì)胞，觀察值為X， 從類(lèi)概率密度分布曲線(xiàn)上查得,損失函數(shù)分別為L(zhǎng)11=0，L21=10， L22=0，L12=1。按最小風(fēng)險(xiǎn)貝 葉斯決策分類(lèi)。,為病變細(xì)胞。,經(jīng)過(guò)選擇或變換，組成識(shí)別特征，盡可能保留分類(lèi)信息，在保證一定分類(lèi)精度的前提下，減少特征維數(shù)，使分類(lèi)器的工作即快又準(zhǔn)確。,12 特征選擇和提取的目的,13 特征選擇和特征提取的異同,（1）特征選擇：從L個(gè)度量值集合 中按一定準(zhǔn) 則選出供分類(lèi)用的子集，作為降維（m維，m L）的分類(lèi) 特征。,（2）特征提取：使一組度量值 通過(guò)某種變換 產(chǎn)生新的m個(gè)特征 ，作為降維的分類(lèi)特征， 其中 。,復(fù)習(xí),14特征提取的方法,其中，,第二步：計(jì)算C的特征值，對(duì)特征值從小到大進(jìn)行排隊(duì)，選擇 前m個(gè)。,第四步：利用A對(duì)樣本集X進(jìn)行變換。,則m維（m n）模式向量X *就是作為分類(lèi)用的模式向量。,解：1) 求樣本均值向量和協(xié)