模式識(shí)別復(fù)習(xí)資料.ppt_第1頁
模式識(shí)別復(fù)習(xí)資料.ppt_第2頁
模式識(shí)別復(fù)習(xí)資料.ppt_第3頁
模式識(shí)別復(fù)習(xí)資料.ppt_第4頁
模式識(shí)別復(fù)習(xí)資料.ppt_第5頁
已閱讀5頁,還剩40頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

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

3、T。,對(duì)應(yīng)最小距離中的最大值, 且T,選作Z3。,結(jié)果:Z1=X1;Z2=X6; Z3=X7 。, 用全體模式對(duì)三個(gè)聚類中心計(jì)算最小距離中的最大值,無T 情況,停止尋找中心。, 聚類,算法描述,1)N個(gè)初始模式樣本自成一類,即建立N 類: 計(jì)算各類之間(即各樣本間)的距離,得一NN維距離矩陣D(0)?!?”表示初始狀態(tài)。,(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í),結(jié)束條件: 1)取距

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

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

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

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論