01.模式識別緒論

1、模式識別Pattern Recognition,第一章 緒論,教學目標,掌握模式識別的基本概念和方法有效地運用所學知識和方法解決實際問題為研究新的模式識別的理論和方法打下基礎,教學方法,著重講述模式識別的基本概念，基本方法和算法原理。注重理論與實踐緊密結合實例教學：通過大量實例講述如何將所學知識運用到實際應用之中避免引用過多的、繁瑣的數(shù)學推導。,學習及考核,相關背景概率論，線性代數(shù)（矩陣計算）考核方式平時成績

2、 30%出勤情況，回答問題課堂討論，隨堂練習大作業(yè)（課程設計） 70%分組進行：2—3 名同學一組分別實現(xiàn)一種分類和聚類算法進行實驗，完成報告,參考文獻,R. Duda, P. Hart, D. Stork, Pattern Classification, second edition, 2000（有中譯本）.邊肇祺，模式識別（第二版,

3、第三版），清華大學出版社，2000(2010)。蔡元龍，模式識別，西北電訊工程學院出版社，1986。汪增福 .模式識別 .中國科學技術大學出版社 孫即祥 .現(xiàn)代模式識別 .國防科技大學出版社,相關的國內(nèi)、國際學術組織,1973年 IEEE發(fā)起了第一次關于模式識別的國際會議“ICPR”，成立了國際模式識別協(xié)會---“IAPR”，每2年召開一次國際學術會議。1977年 IEEE的計算機學會成立了模式分析與機器智能（PAMI）委員會

4、，每2年召開一次模式識別與圖象處理學術會議。國內(nèi)的組織有電子學會，通信學會，自動化協(xié)會，中文信息學會….。,本領域相關期刊,外文期刊：IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI);中文期刊：《模式識別與人工智能》，中國自動化學會等主辦，月刊,,模式識別?Pattern Recognition?,一 模式識別的基本概念,模式識別廣泛存在于

5、我們的日常生活中，我們幾乎每時每刻都在進行模式識別人們在觀察各種事物或接受各種客觀現(xiàn)象的時候，常把它們分成由各個相似的但又不完全相同的事物或現(xiàn)象組成的類別，幾乎每一項活動都離不開對外界事物的分類和識別。比如，我們今天來這里上課就要先識別課表（字符識別），來教室的路線（環(huán)境識別），以及教室的識別（數(shù)字識別）等等，聽課（聲音識別）；,,人和動物都具有模式識別的能力,人腦具有模式識別的能力比如，字母“B”可以有各種各樣的寫法，但是他們都

6、屬于同一類別。更重要的是，即使有某個寫法“B”，人們過去從未見過，也很容易把它分到“B”這個類別中去。又比如，我們今天見到的張三和上次見到的張三已經(jīng)不完全相同，但我們?nèi)匀荒軌蛘_地識別除了人，很多動物也具有一定的模式識別能力蝙蝠的雷達系統(tǒng)狗看到主人會搖頭擺尾，見到生人會狂吠不止為了生存，最低等的動物也要識別食物和敵害，并做出不同的反應,模式的概念,模式（pattern）凡是人類能用其感官直接或間接接受的外界信息都稱為模式，例

7、如文字，圖片，景物，聲音，語言；心電圖，腦電圖，地震波；社會經(jīng)濟現(xiàn)象，某個系統(tǒng)的狀態(tài)；模式的直觀特性可觀察性可區(qū)分性相似性,什么是模式（Pattern）？,模式(pattern)代表事物的模板或原型；表征事物特點的特征或性狀的組合；模式是一種規(guī)律，可以看作是對象的組成部分或影響因素間存在的規(guī)律性關系，或者是因素間存在確定性或隨機性規(guī)律的對象，過程或事件的集合；廣義地說，存在于時間和空間中可觀察的事物，如果我們可以區(qū)

8、分它們是否相同或是否相似，都可以稱之為模式；模式所指的不是事物本身，而是我們從事物獲得的信息模式往往表現(xiàn)為具有時間或空間分布的信息,模式識別的概念,模式識別（Pattern Recognition）把對象分門別類地認出來；對以前見過的對象的再認識（re-cognition）；對模式的區(qū)分和認識；把對象根據(jù)其特征歸到若干類別中適當?shù)囊活?，因此模式識別也稱為模式分類（pattern classification）對于復雜的模式

9、除了分類之外還要描述其結構特征，如 漢字識別和景物識別,模式識別的應用（舉例）,生物學自動細胞學、染色體特性研究、遺傳研究天文學，遙感天文望遠鏡圖像分析、自動光譜學經(jīng)濟學股票交易預測、企業(yè)行為分析醫(yī)學心電圖分析、腦電圖分析、醫(yī)學圖像分析,模式識別的應用（舉例）,工程產(chǎn)品缺陷檢測、特征識別、語音識別、自動導航系統(tǒng)、污染分析軍事航空攝像分析、雷達和聲納信號檢測和分類、自動目標識別安全指紋識別、人臉識別、監(jiān)視和報警系統(tǒng)

10、娛樂,模式識別的應用（舉例）,模式識別的應用（舉例）,,模式識別的應用（舉例）,模式識別應用舉例,人民幣防偽技術一直是模式識別應用領域之一，而欺騙這些防偽措施一直是偽造集團的努力方向。據(jù)說（沒有驗證過，為相關公司人員提供）早期投幣電話是通過投幣之后落入內(nèi)部的聲音來判斷投幣是何幣種。這個策略是抓住了不同幣值的硬幣在相同的條件下造成的聲音差異來區(qū)分幣種，是一種簡單的必要條件識別法。據(jù)說一個聰明的學生偶爾有一次在北京學院路的一個投幣電話

11、上發(fā)現(xiàn)了這個規(guī)律，聰明的學生拿著一個錄音機，播放類似的硬幣掉落的聲音，居然可以欺騙電話。當這個策略公開的時候，由于偽造的代價特別低，導致該方法的迅速失效。 故事還沒有結束，后來又發(fā)明了稱重法。就是內(nèi)置一個尺寸測量加上稱重裝置，根據(jù)硬幣的大小和重量的范圍，判斷是不是硬幣，是什么幣種。這種方法就比原來好很多，但是依然沒有解決真正的造假問題。假幣集團發(fā)現(xiàn)硬幣（一元硬幣）內(nèi)部是貴金屬，于是他們就想法用廉價的鉛替換內(nèi)部的重金屬，以較

12、低的代價獲得更高的價值，據(jù)說東南某省的一個造假作坊短期內(nèi)就賺取了幾百萬。尺寸加重量也不能擋住造假的手段。于是，在后來的機器上，越來越多的傳感器被裝進去，包括磁性等，以獲得越來越多硬幣的各種物理和化學屬性，提高識別的精確性。,模式識別的基本術語,樣本（sample）:所研究對象的一個個體樣本集（sample set）:若干樣本的集合類或類別（class）:在所有樣本上定義的一個子集，處于同一類的樣本在我們所關心的性質(zhì)上是不可區(qū)分的，

13、即具有相同的模式特征（feature）:用于表征樣本的觀測信息，通常是數(shù)值表示的，有時也稱為屬性（attribute）；如果是高維則稱為特征向量，樣本的特征（向量）構成了特征空間，每個樣本是特征空間中的一個點；,模式識別的基本術語,已知樣本（known sample）:事先知道類別標號的樣本（訓練樣本）；未知樣本（unknown sample）:類別標號未知但特征已知的樣本（待識別的樣本）,模式識別的研究內(nèi)容,Pattern rec

14、ognition is the study of how machines can observe the environment, learn to distinguish patterns of interest from their background, and make sound and reasonable decisions about the categories of the patterns. (Anil K. J

15、ain)利用計算機對物理對象進行分類，在錯誤概率最小的條件下，使識別的結果盡量與客觀物體相符合。,模式識別的目標,研究出能自動進行模式分類和描述的機器系統(tǒng)，以完成人類的模式識別的功能。這同人工智能范疇的其他分支的目標是一致的，都是要用機器來代替人類的部分智力活動,相關學科,模式識別是一門邊緣學科，與人工智能，信號處理，計算機科學與技術，概率統(tǒng)計，模糊集論，信息論，數(shù)字圖像處理，形式語言學，心理學，語言學等都有密切的關系，而且隨著這門學

16、科的發(fā)展，還會與其它更多學科發(fā)生關系,模式識別系統(tǒng)舉例,機器視覺：制造業(yè)的自動檢測和自動裝配線語音識別：讓計算機聽懂人類的指令，在有害環(huán)境中遠程控制機器，殘障人士通過談話控制機器，語音輸入說話人識別：根據(jù)語音確定說話人的身份字符與文字識別：信件的自動分揀，手寫輸入法，銀行支票的機器讀取，計算機輔助診斷技術：X-射線，超聲，心腦電圖等復雜圖像中特定目標的識別：道路圖像中汽車的檢測，人臉檢測，行路人檢測等根據(jù)地震勘探數(shù)據(jù)對地下儲

17、層性質(zhì)的識別（石油勘探）數(shù)據(jù)挖掘和知識發(fā)現(xiàn)：多媒體檢索，基因表達數(shù)據(jù)分析,一個例子：問題的提出,有一家魚包裝公司（fish-packing plant）要根據(jù)傳送帶上的魚的種類實現(xiàn)自動分揀,鱸魚（sea bass）,鮭魚(salmon),一個例子：可能的解決方案,架設一臺照相機，采集一些圖像通過初步觀察，注意到兩種魚之間的一些外在的差異（分類器的備用特征）長度（length）光澤度(lightness)寬度(width)鰭(

18、fins)的數(shù)目和形狀嘴的位置,系統(tǒng)的雛形,攝像機拍下魚的照片圖像的預處理：將魚從背景中分割出來，并彼此分開單條魚的信息送到一個特征提取器（feature extractor）提取的特征送到分類器（classifier）進行分類決策,特征提取器和分類器的設計,一般來說，鱸魚的長度要比鮭魚長，因此先考慮用長度作為分類特征分類基于的模型：鱸魚和鮭魚都有一個典型的長度，并且鱸魚的這個長度要大于鮭魚的長度通過樣本訓練確定分類的閾值l

19、*決策規(guī)則：看一條魚的長度是否超過閾值l*,以長度分類樣本的結果,數(shù)目,鮭魚,鱸魚,長度,分類結果分析,盡管平均意義下鱸魚的平均長度大于鮭魚，但用單一的長度作為分類標準結果并不理想無論我們?nèi)绾芜x擇閾值l* ，都無法可靠地把兩種魚分開來因此，需要考慮其他的特征,以平均光澤度作為分類特征,結論：以光澤度作為分類特征的效果要好得多,代價的考量,前面我們假定犯兩類錯誤的代價是相同的盡管這一假定很多時候適用，但也有例外由于鮭魚比鱸魚更美

20、味，因此顧客更容易接受鮭魚被錯分為鱸魚，而難以接受鱸魚被錯分為鮭魚。為減少錯誤分類的代價，必須減少鱸魚錯分為鮭魚的概率：決策邊界向光澤度小的方向偏移,如果我們對分類效果還不滿意,我們將繼續(xù)尋找新的能實現(xiàn)更好分類效果的單一特征假定在單一特征中光澤度的分類效果是最好的，則我們必須考慮多個特征例如，我們觀察到鱸魚一般來說要比鮭魚寬，就可以用光澤度和寬度來構造二維特征向量：,分類結果,結果分析,二維特征的分類結果看起來好于一維特征所以我

21、們可以考慮加入更多的特征來進一步提高分類效果，比如背鰭的頂角，嘴的位置等等問題：是否加入的特征越多，分類效果越好？答：不一定,為什么特征不是越多越好,特征越多，測量的代價就越多即使不考慮代價，加入冗余特征也不會提高分類效果，比如如果眼睛的顏色與寬度是完全相關的，則加入這一特征便不會提高分類效果特征越多，模型就越復雜，分類邊界也越復雜，盡管可以實現(xiàn)對樣本的完美分類，卻偏離了我們設計分類器的初衷,訓練樣本的完美分類,推廣能力問題（G

22、eneralization）,分類器設計的核心目標是實現(xiàn)對未知樣本的正確分類，也就是要有好的推廣能力。而一個過于復雜的決策界面一般來說不太可能有好的推廣能力，它只是針對個別訓練樣本的調(diào)整，而沒有真正地反映所要識別對象模型的本質(zhì)特征。結論：我們必須在訓練樣本的分類錯誤率和推廣能力之間權衡以得到滿意的設計,模式識別系統(tǒng),信息獲取,信息獲取一般是通過某種傳感器將光或聲音等信息轉化為電信息。信息可以是二維的圖像如文字，指紋，地圖，照片等；

23、可以是一維的波形如心電圖，腦電圖，機械振動波形；也可以是物理量與邏輯值，前者如疾病診斷中病人的體溫及各種化驗數(shù)據(jù)，后者如對某參量正常與否的判斷或對癥狀有無的描述等。此外，還可以是模糊值，如大，很大，比較大等。,預處理,由感知器輸入的信息往往需要進行適當?shù)念A處理，圖像識別中將圖像從背景中分割出來在語音識別中，區(qū)分單個的音素（phoneme）合成對象的各個組成部分正確分組（‘i’有兩個部分，但我們將它們識別為一個符號）預處理可

24、以去除噪聲，加強有用的信息預處理的方法：包括A\D,二值化，圖象的平滑，變換，增強，恢復，濾波等處理,特征提取和選擇,一般由原始測量所獲得的數(shù)據(jù)量是相當大的，為了有效地實現(xiàn)分類識別，就要對原始數(shù)據(jù)進行變換，得到最能反映分類本質(zhì)的特征，這就是特征提取和選擇的過程。所選的特征必須使同類的樣本相距較近，而不同類的樣本相距較遠，并對無關變換具有不變性，比如在前面鱸魚 和鮭魚的例子中，所選特征要對平移，旋轉，伸縮等具有不變性,分類決策,分類目

25、標： 把特征空間劃分成類型空間。 把未知類別屬性的樣本確定為類型空間的某一個類型實際分類過程中，對于預先給定的條件，分類中出現(xiàn)錯誤是不可避免的。因此，分類過程只能以某種錯誤率來完成。顯然，錯誤率越小越好。但是，分類錯誤率又受很多條件的制約：分類方法、分類器設計、選用的樣本及提取的特征等。因此，分類錯誤率不能任意小。,分類器設計：分類器設計的主要功能是通過訓練確定判決規(guī)則，使按此類判決規(guī)則分類時，錯誤率最低。分類決策：在特征空間中

26、把被識別對象進行分類，歸為某一類別。,分類決策,后處理,錯誤率和風險評估，從而改進設計，提高分類性能（從理論上估計最小錯誤率/風險，看我們設計的分類器還有多大差距）利用上下文信息解釋分類結果，提高分類性能利用多個分類器來提高分類效果,模式識別的分類,監(jiān)督模式識別/學習（supervised pattern recognition/learning）非監(jiān)督模式識別/學習，聚類（unsupervised pattern recogn

27、ition/learning，clustering）半監(jiān)督模式識別（semi-supervised pattern recognition）,監(jiān)督模式識別,在機器學習里稱為監(jiān)督學習（supervised learning）,存在有已知樣本的訓練集，比如在鱸魚和鮭魚的例子里，有一定數(shù)量的訓練樣本，可以利用的先驗信息相對比較多,非監(jiān)督模式識別,給定的是未知樣本集合，按其特征把相似的歸為一類在工程和社會科學中出現(xiàn)較多，比如多光譜遙感(

28、multispectral remote sensing)，圖像分割(image segmentation)，圖像和語音編碼(image and speech coding)等關鍵是如何定義兩個特征向量之間的相似性（similarity），并選擇一個合適的度量一般來說，不同的聚類算法會產(chǎn)生不同的聚類結果，需要專家來解釋,半監(jiān)督模式識別,其分類目標與監(jiān)督模式識別相同，但是在已知樣本之外還有一部分未知樣本一般出現(xiàn)在系統(tǒng)設計者只能得到很

29、少的已知樣本的情況下（用未知樣本做進一步的補充）也可以看成帶有約束條件（已知樣本）的聚類,二.模式識別的發(fā)展史,1929年 G. Tauschek發(fā)明閱讀機，能夠閱讀0-9的數(shù)字。30年代 Fisher提出統(tǒng)計分類理論,奠定了統(tǒng)計模式識別的基礎。因此，在60～70年代，統(tǒng)計模式識別發(fā)展很快，但由于被識別的模式愈來愈復雜，特征也愈多，就出現(xiàn)“維數(shù)災難”。但由于計算機運算速度的迅猛發(fā)展，這個問題得到一定克服。統(tǒng)計模式識別仍是模式識別的主

30、要理論。,50年代喬姆斯基 （ Noam Chemsky） 提出形式語言理論。美籍華人付京蓀 提出句法結構模式識別。60年代 L.A.Zadeh提出了模糊集理論，模糊模式識別理論得到了較廣泛的應用。80年代 Hopfield提出神經(jīng)元網(wǎng)絡模型理論。近些年人工神經(jīng)元網(wǎng)絡在模式識別和人工智能上得到較廣泛的應用。90年代Vapnik基于小樣本學習理論發(fā)展了支持向量機，支持向量機也受到了很大的重視。,§1-3 模式識別的方法,

31、模版匹配法(template matching)統(tǒng)計方法(statistical pattern recognition)神經(jīng)網(wǎng)絡方法(neural network)結構方法(句法方法)(structural pattern recognition ),模版匹配,模板匹配模式認為在人的長時記憶中,存在著代表各種景物形態(tài)的“模板”。當人注視景物時,景物通過眼睛及其視覺系統(tǒng)進入大腦與存儲在大腦中的模板進行匹配。若某個模板與輸入

32、景物匹配一致或相關量最大,就認為人已經(jīng)對這一景物能夠再認了。 實現(xiàn)方式：首先對每個類別建立一個或多個模版輸入樣本和數(shù)據(jù)庫中每個類別的模版進行比較，求相關或距離根據(jù)相關性或距離大小進行決策,優(yōu)點：直接、簡單 例如，當我們看一個字母A，視網(wǎng)膜接收的信息便傳到大腦，刺激信息在腦中得到相應的編碼，并與記憶中貯存的各式各樣的模板進行比較；通過決策過程判定它與模板A有最佳的匹配，于是字母A就得到識別。缺點：適應性

33、差 然而現(xiàn)實世界輸入視覺系統(tǒng)的景物是復雜的。就拿字符“F”來說，輸入“F”字符可能是拉伸的、壓縮的、旋轉的、歪扭的、斷裂的，等等，這使得模板匹配工作變得困難和復雜起來。,模版匹配,統(tǒng)計方法,根據(jù)訓練樣本，建立決策邊界(decision boundary) 統(tǒng)計決策理論—根據(jù)每一類總體的概率分布決定決策邊界判別式分析方法—給出帶參數(shù)的決策邊界，根據(jù)某種準則，由訓練樣本決定“最優(yōu)”的參數(shù)本課程的重點內(nèi)容,統(tǒng)計

34、方法,例1：男女19人進行體檢，測量身高和體重，如下表。但事后發(fā)現(xiàn)4人忘了寫性別，試問，這4人是男是女？,統(tǒng)計方法,解：試驗樣本是人，分為男、女兩個類別。二維的主要特征是身高、體重，構成二維特征空間。已知15人的性別，可以作為訓練樣本，根據(jù)其值確定他們在特征空間的位置。如下圖所示：,統(tǒng)計方法,,,統(tǒng)計方法,統(tǒng)計方法,現(xiàn)考察16～19號體檢者，由身高、體重確定在上圖中的位置。顯然，16(α)、19(δ)在負線一側，判定他們?yōu)榕浴?

35、7(β)、18(γ)位于正線一側，判為男性。,人工神經(jīng)網(wǎng)絡,受人的大腦神經(jīng)網(wǎng)絡的啟發(fā)提出的進行大規(guī)模并行計算的數(shù)學模型具有學習、推廣、自適應、容錯、分布表達和計算的能力優(yōu)點：可以有效的解決一些復雜的非線性問題缺點：缺少有效的學習理論，容易產(chǎn)生過學習,句法方法,許多復雜的模式可以分解為簡單的子模式，這些子模式組成所謂 “基元”每個模式都可以由基元根據(jù)一定的關系來組成基元可以認為是語言中的詞語，每個模式都可以認為是一個句子，關系可

36、以認為是語法模式的相似性由句子的相似性來決定優(yōu)點：適合結構性強的模式缺點：抗噪聲能力差，計算復雜度高,句法方法,例2：如下圖中一幅圖形，要識別圖中的物體，選用句法模式識別方法,,句法方法,解：圖形結構復雜，首先應分解為簡單的子圖（背景、物體）。背景由地板和墻組成，物體為長方體和三角體。三角體又分為一個長方形面和一個三角形面。長方體又分為三個長方形面。上述分析構成一個多級樹結構：,句法方法,其中，面、三角形、地板和墻壁，即

37、L、T、X、Y、Z、M和N均為基本圖形單元，簡稱基元。在句法模式識別中，基元就是特征。,,句法方法,句法模式識別的方法在學習過程中，確定基元與基元之間的關系，推斷出生成景物的方法。判決過程中，首先提取基元，識別基元之間的連接關系，使用推斷的文法規(guī)則做句法分析, 即分析給定的模式語句是否符合指定的語法，滿足某類語法的即被分入該類。若分析成立，則判斷輸入的景物屬于相應的類型。,本門課程的主要內(nèi)容,第一章 緒論第二章 聚類分析第三