模式識別第1章

1、模式識別關于本課程的有關說明 相關學科相關學科 教學方法教學方法 教學目標教學目標 基本要求基本要求 教材教材/ /參考文獻參考文獻統(tǒng)計學統(tǒng)計學概率論概率論線性代數(shù)（矩陣計算）線性代數(shù)（矩陣計算）形式語言形式語言人工智能人工智能圖像處理圖像處理計算機視覺計算機視覺等等等等 相關學科 教學方法著重講述模式識著重講述模式識別的基本概念，基別的基本概念，基本方法和算法原理。本方法和算法原理。注重理論與實踐注重理論與實踐緊密結合緊密結合 實例教學：通過實例教學：通過實例講述如何將所實例講述如何將所學知識運用到實際學知識運用到實際應用之中應用之中避免引用過多的、避免引用過多的、繁瑣的數(shù)學推導繁瑣的數(shù)學推

2、導 教學目標掌握模式識別的掌握模式識別的基本概念和方法基本概念和方法有效地運用所學有效地運用所學知識和方法解決實知識和方法解決實際問題際問題為研究新的模式為研究新的模式識別的理論和方法識別的理論和方法打下基礎打下基礎 基本要求基本：完成課程習基本：完成課程習通過考試，獲得學分。通過考試，獲得學分。提高：能夠將所知提高：能夠將所知和內容用于課題究決和內容用于課題究決實際問題。實際問題。飛躍：通過模式的飛躍：通過模式的學習，改進思維式為學習，改進思維式為將來的工作打好礎終將來的工作打好礎終身受益。身受益。邊肇祺邊肇祺.模式識別模式識別.清華大學出版社清華大學出版社孫即祥孫即祥.現(xiàn)代模式識別現(xiàn)代模式

3、識別.國防科技出版社國防科技出版社 羅耀光羅耀光,盛立東盛立東.模式識別模式識別.人民郵電出版社人民郵電出版社付京蓀付京蓀.模式識別及應用模式識別及應用.科學出版社科學出版社Richard O. Duda et al ，Pattern Classification.(2nd version,中、英版），中、英版），機械工業(yè)出版社機械工業(yè)出版社 K.S.Fu .Syntactic Pattern Recognition and Application J.T.Tom R.C. Gouzales.Pattern Recognition Principles 教材教材/參考文獻參考文獻引引 言言模式

4、識別的發(fā)展模式識別的發(fā)展n1929年 G. Tauschek發(fā)明閱讀機 ，能夠閱讀0-9的數(shù)字。n30年代 Fisher提出統(tǒng)計分類理論,奠定了統(tǒng)計模式識別的基礎。因此，在6070年代，統(tǒng)計模式識別發(fā)展很快，但由于被識別的模式愈來愈復雜，特征也愈多，就出現(xiàn)“維數(shù)災難”。隨著計算機運算速度的迅猛發(fā)展，這個問題得到一定克服。目前，統(tǒng)計模式識別仍是模式識別的主要理論。n50年代 Noam Chemsky 提出形式語言理論，在此基礎上，美籍華人付京蓀 提出句法結構模式識別。n60年代 L.A.Zadeh提出了模糊集理論，模糊模式識別理論得到了較廣泛的應用。80年代 Hopfield提出神經元網絡模型理

5、論。近些年人工神經元網絡在模式識別和人工智能上得到較廣泛的應用。90年代 小樣本學習理論，支持向量機也受到了很大的重視。1973年 IEEE發(fā)起了第一次關于模式識別的國際會議“ICPR”，成立了國際模式識別協(xié)會-“IAPR”，每2年召開一次國際學術會議；1977年 IEEE的計算機學會成立了模式分析與機器智能（PAMI）委員會，每2年召開一次模式識別與圖象處理學術會議；國內的組織有電子學會，通信學會，自動化協(xié)會，中文信息學會.。模式識別的應用領域更加廣泛：模式識別的應用領域更加廣泛： 生物、醫(yī)學、軍事、農業(yè)、工業(yè)、社會、教育、航天、航空、經濟、金融、生物認證、數(shù)字水印基于語音： 重點人物通信監(jiān)

6、控語音識別系統(tǒng)/規(guī)模音頻資料檢索基于圖像： 光學字符識別(Optical Character Recognition OCR)/車牌識別(Vehicle License Plate Recognition VLPR)/人臉識別/指紋識別/簽名認證/支票認證/表情和手勢識別/農作物分類與害蟲識別/生物信息學：DNA識別/航空與衛(wèi)星遙測遙感數(shù)據(jù)資源調查/軍用目標的圖像識別/基于圖形模式識別的機器人控制等基于工程數(shù)據(jù)： 振動模式分析與故障診斷/石油鉆井數(shù)據(jù)分析與事故預報/基于狀態(tài)模式的智能控制/數(shù)據(jù)挖掘與知識發(fā)現(xiàn)等n模式識別的計算手段更加先進：模式識別的計算手段更加先進： 海量存儲技術、高速計算/并

7、行計算技術、 網格技術、網絡技術、 新型前端器件(激光、紅外、MEMS、傳感器網絡)n模式識別的新型算法層出不窮：模式識別的新型算法層出不窮： Computation with word(Zadeh) Soft Computation DNA Computationn國內外模式識別的學術活動從未間斷國內外模式識別的學術活動從未間斷: 小波/模式識別國際會議、機器學習/模式識別國際會議、圖像處理/模式識別國際會議、數(shù)據(jù)挖掘/模式識別國際會議第1章 緒論例子例子1 1：醫(yī)生診病過程：醫(yī)生診病過程 1)測量病人的體溫和血壓，化驗血沉，詢問臨床表現(xiàn)； 2)通過綜合分析，抓住主要病癥； 3)醫(yī)生運用自己

8、的知識、經驗，根據(jù)主要病癥、測量化驗結果，作出正確的診斷。n在模式識別技術中，常用的術語有：樣本、模式、特征、類型等等，對照醫(yī)生診病過程，有：a.樣本：醫(yī)院里的眾多患者，每個患者都是一個樣本； 單一樣本：醫(yī)生診斷的某一患者，就是樣本空間中的一個單一樣本； 樣本值：某一患者的化驗、檢查結果與表征現(xiàn)象。b.模式：各樣本值按一定的數(shù)據(jù)準則綜合的結果； 模式樣本：具有某種模式的樣本； 模式采集：獲取某樣本的測量數(shù)值的過程；醫(yī)生診病過程醫(yī)生診病過程c.特征：患者某些具有顯著特征的化驗數(shù)據(jù)及表征； 特征選擇與提?。耗鼙碚?疾病)特異性的化驗結果與表征；d.判決：醫(yī)生運用知識、病例經驗綜合分析給出診斷； 判

9、決準則/規(guī)則：醫(yī)生的知識 判決結果：將患者明確(或以概率)確定為某一種病癥(或多種/并發(fā)病癥)的患者(及病患嚴重程度)事實上，最后的結果也成為分類。因此有預先知道類別(已知病癥)與未知類別(未知病癥)的區(qū)別。模式識別：就是以計算機為工具、各種傳感器為信息來源，數(shù)據(jù)計算與處理為方法，對各種現(xiàn)象、事物、狀態(tài)等進行準確地分析、判斷識別與歸類。n人類在生產過程的長期發(fā)展中，辨別事物的能力逐漸增強，辨別事物的需求也逐漸擴大。尤其是近代，隨著現(xiàn)代工業(yè)的飛速發(fā)展，辨別事物的能力逐漸發(fā)展為一項專門的技術，從20世紀初起，形成了專門的模式識別技術。n 從廣義來說，模式識別是人類的基本活動。從狹義來說，模式識別是

10、專門對于機器識別而言的，或者說是基于數(shù)學的基本原理以及信息學的基本原理，利用計算機技術來完成的機器識別。n客觀事物的主觀(符號化)表征即為模式。n模式的概念源于分類學。作為一個抽象化的概念，它不是被識別對象的固有屬性，而是人對被識別對象所加的主觀標簽。模式分類學的研究目的是基于特定的研究對象,尋找有效的描述方法,尋找對象固有的屬性特征,尋找合理的數(shù)學方法,實現(xiàn)類別歸屬的確定。模式識別的幾個主要關系：1.模式識別發(fā)展的動力是社會生產的需求2.分類類別的確定與確定類別的依據(jù)3.使用什么分類方法來完成分類目的以及所使用方法的評價n特征空間(描述空間,表示空間)n包含用以描述樣本的特征向量的向量空間。

11、n決策空間(解釋空間)n分類類別形成的集合.n尋找特征空間到決策空間的映射關系一、基本概念一、基本概念n模式識別模式識別(Pattern Recognition)(Pattern Recognition)：確定一個樣本的類別屬性確定一個樣本的類別屬性（模式類）的過程，即把某一樣本歸屬于多個類型中的某個類（模式類）的過程，即把某一樣本歸屬于多個類型中的某個類型。型。n樣本（樣本（Sample)Sample)：一個具體的研究（客觀）對象。如患者，某一個具體的研究（客觀）對象。如患者，某人寫的一個漢字，一幅圖片等。人寫的一個漢字，一幅圖片等。n模式模式(Pattern)(Pattern)：對客體（研

12、究對象）特征的描述（定量的或對客體（研究對象）特征的描述（定量的或結構的描述），是取自客觀世界的某一樣本的測量值的集合結構的描述），是取自客觀世界的某一樣本的測量值的集合（或綜合）。（或綜合）。n特征特征(Features)(Features)：能描述模式特性的量（測量值）。在統(tǒng)計模能描述模式特性的量（測量值）。在統(tǒng)計模式識別方法中，通常用一個矢量式識別方法中，通常用一個矢量 表示，稱之為特征矢量，記表示，稱之為特征矢量，記為為 n模式類模式類(Class)(Class)：具有某些共同特性的模式的集合。具有某些共同特性的模式的集合。x),(21nxxxx),(21nxxxx二、基本問題二、基本

13、問題模式模式(樣本樣本)表示方法表示方法模式類的緊致性描述模式類的相似性與度量模式類的特征描述空間映射的應用及其有效性準則函數(shù)的選擇與其適用范圍模式識別中的機器學習方法模式表示法模式表示法1.向量表示法向量表示法模式向量模式向量：以數(shù)量信息為特征的模式表示。即以模式的以數(shù)量信息為特征的模式表示。即以模式的n n個特征量測值組個特征量測值組成一個成一個n n維特征矢量維特征矢量 X=(xX=(x1 1,x,x2 2, ,x,xn n) )T T表示模式。表示模式。例：例：字符識別機，辨別每個輸入，判斷它是屬于哪一種字符，字符識別機，辨別每個輸入，判斷它是屬于哪一種字符，A AZ Z、0 09 9

14、、拒絕類，共、拒絕類，共26+10+1=3726+10+1=37個模式類。采用光電陣列把字符變成二值個模式類。采用光電陣列把字符變成二值的圖象，如的圖象，如6 66 6方陣，方陣，X=xX=x1 1x x2 2x x3 3x x3636 T T。 2. 2.矩陣表示矩陣表示N個樣本，個樣本，n個變量個變量(特征特征)3.幾何表示幾何表示一一維表示維表示 X1=0.5 X2=3 二維表示二維表示 X1=(x1,x2)T=(1,2)T X2=(x1,x2)T=(2,1)T三維表示三維表示 X1=(x1,x2,x3)T=(1,1,0)T X2=(x1,x2,x3)T=(1,0,1)T4. 4.符號串

15、表示法（符號串表示法（1 1）n定義了一定的模式基元，用模式基元的連接表示模式定義了一定的模式基元，用模式基元的連接表示模式。ba階梯模式： ababab 即 (ab)n,n1符號串表示法（2）n定義算子定義算子, ,增加串的表示能力增加串的表示能力 baa+bbaabbaa*bbba模式基元：ba-bba5.樹表示法n任何一個分層有序系統(tǒng)都導致樹結構，引入任何一個分層有序系統(tǒng)都導致樹結構，引入“在內部在內部”關系、關系、“由由組組成成”關系。關系。 abcdefghi$a$bcihgdfeR2R1R3T1T2墻（W）地板F立方體C錐體P錐體P$景物物體背景地板F墻W立方體CT1T2R1R2R

16、36.網表示法n網表示法：網是無向帶標志的點圖。在上圖中，我們在引入網表示法：網是無向帶標志的點圖。在上圖中，我們在引入“與與連接連接”，就可，就可以得到圖所示的網。以得到圖所示的網。 R2R1R3 T1 T2墻（W）地板F立方體C錐體P$景物物體背景地板F墻W錐體P立方體CT1T2R1R2R3模式類的緊致性描述為了保證分類的可行性,要求同類樣本在描述空間中應盡可能地靠近,或者說同類樣本是一個緊致集合.模式類的緊致性是就簡單分類面還是復雜分類面而言的.1. 1. 緊致集：同一類模式類樣本的分緊致集：同一類模式類樣本的分布比較集中，沒有臨界樣本或者布比較集中，沒有臨界樣本或者臨界樣本很少，這樣的

17、模式類稱臨界樣本很少，這樣的模式類稱緊致集。緊致集。2. 2. 臨界點臨界點( (樣本樣本) )：在多類樣本中，某些樣本的值有微小變化時就變成另一類樣本稱為在多類樣本中，某些樣本的值有微小變化時就變成另一類樣本稱為臨界樣本（點）臨界樣本（點）。3. 3. 緊致集的性質緊致集的性質 要求臨界點很少要求臨界點很少. . 集合內的任意兩點的連線集合內的任意兩點的連線, ,在線上的點屬于同在線上的點屬于同 一集合一集合. . 集合內的每一個點都有足夠大的鄰域集合內的每一個點都有足夠大的鄰域, ,在鄰域內只包含同一集合的點在鄰域內只包含同一集合的點. .4. 4. 模式識別的要求模式識別的要求: : 滿

18、足緊致集，才能很好的分類；如果不滿足緊致集，就要采取變滿足緊致集，才能很好的分類；如果不滿足緊致集，就要采取變換的方法換的方法, ,滿足緊致集滿足緊致集. .模式類的相似性模式類的相似性用以確定不同樣本是否同類.它是模式類上建立的一種相似關系.樣本之間的相似程度可以通過計算樣本距離而獲得.常用的如歐氏距離,下降函數(shù),向量夾角等,它們具有非負性,自反性,對稱性,但不具有傳遞性.1. 1.兩個樣本兩個樣本 x xi i 和和 x xj j 之間的相似度量滿足以下要求：之間的相似度量滿足以下要求： 應為非負值。 樣本本身相似性度量應最大。 度量應滿足對稱性。 在滿足緊致性的條件下，相似性應該是點間距

19、離的單調函數(shù)。 2. 2. 用各種距離表示相似性：用各種距離表示相似性： 已知兩個樣本 xi=(xi1, xi2 , xi3,xin)T xj=(xj1, xj2 , xj3,xjn)T 常用的距離有歐氏距離、馬氏距離等常用的距離有歐氏距離、馬氏距離等3. 分類的主觀性和客觀性分類的主觀性和客觀性 分類的主觀性：分類的主觀性：目的不同，分類不同。例如：鯨魚，牛，馬從生物學的角度來講都屬于哺乳類，但是從產業(yè)角度來講鯨魚屬于水產業(yè)，牛和馬屬于畜牧業(yè)。 分類的客觀性：分類的客觀性：科學性判斷分類必須有客觀標準，因此分類是追求客觀性的，但主觀性也很難避免，這就是分類的復雜性。模式類的特征模式類的特征是

20、從模式得到的對分類有用的度量,屬性或者基元,在數(shù)學上特征的定義空間則稱為特征空間.模式識別中的特征具有更加廣泛的含義.在模式識別中,獲取描述模式類的特征是關鍵的工作.所獲特征是否有效,以及如何剔除與分類無關的特征均是特征研究中的重要問題(即特征提取與特征壓縮).模式的特征空間表示模式的特征空間表示特征的分布特征的分布特征的生成特征的生成 1.低層特征：低層特征： 無序尺度：無序尺度：有明確的數(shù)量和數(shù)值. 有序尺度：有序尺度：有先后、好壞的次序關系，如酒分為上，中，下三個等級. 名義尺度：名義尺度：無數(shù)量、無次序關系，如有紅，黃兩種顏色. 2. 中層特征：中層特征：經過計算，變換得到的特征. 3

21、. 高層特征：高層特征：在中層特征的基礎上有目的的經過運算形成. 例如：椅子的重量=體積*比重. 體積與長，寬，高有關；比重與材料，紋理，顏色有關。這里低、中、高三層特征都有了。模式識別的訓練方法模式識別的訓練方法v有監(jiān)督學習有監(jiān)督學習（有教師學習）：預先已知訓練樣本集合中每個樣本的類別標號；v無監(jiān)督學習監(jiān)督學習（無教師學習）：預先不知道訓練樣本集合中每個樣本的類別標號；統(tǒng)計識別方法的分類統(tǒng)計識別方法的分類v一、根據(jù)樣本在空間中的幾何分布進行分類 方法一：近鄰法；方法二：判別函數(shù)法。v二、根據(jù)樣本在空間中的概率分布進行分類貝葉斯分類器識別系統(tǒng)的設計步驟識別系統(tǒng)的設計步驟v收集樣本 v確定識別特

22、征 v特征抽取 v特征分析v確定識別方法 v性能評價 v性能評價：v正確識別率 = 正確分類數(shù)/總數(shù)v錯誤識別率 = 錯誤分類數(shù)/總數(shù)v拒絕識別率 = 拒絕分類數(shù)/總數(shù)空間映射空間映射是解決特征空間與有效分類之間的橋梁.使用空間映射關系,可以將各種有效的數(shù)學方法應用于模式識別之中以解決分類問題.常用的空間映射方法:線性映射,傅立葉變換,DCT變換,沃爾什變換,K-L變換,非線性變換.數(shù)據(jù)的標準化數(shù)據(jù)的標準化ijijiXXRminmaxi jii jiXXXRi jii jiXXXS1.1.極差標準化極差標準化: :一批樣本中，每個特征的最大值與最小值之差為極差。極差極差標準化2.2.方差標準化

23、：方差標準化： Si 為方差標準化的方法很多，原始數(shù)據(jù)是否應該標準化，應采用什么方法標準化，都要根據(jù)具體情況來定。準則函數(shù)的選擇準則函數(shù)是用以解決分類問題的依據(jù).對于具體的分類問題應選擇合理的分類器設計方法與合理的準則函數(shù),使得分類器的設計滿足分類需要.各種準則函數(shù)都是在限定條件下被提出來,因此在實際使用中都有一定的局限性.機器學習方法即使用已知樣本來訓練分類器,使之達到希望的性能.各種分類器設計中,無一例外地使用了機器學習的方法.機器學習通過對樣本信息的學習獲得關于類別的知識,從而得到有效的分類器.三、各類空間（三、各類空間（Space)模模式式識識別別三三大大任任務務對象空間對象空間模式空

24、間模式空間特征空間特征空間類型空間類型空間模式采集：模式采集：從客觀世界（對象從客觀世界（對象空間）到模式空間的過程稱為空間）到模式空間的過程稱為模式采集。模式采集。特征提取和特征選擇：特征提取和特征選擇：由模式由模式空間到特征空間的變換和選擇?？臻g到特征空間的變換和選擇。類型判別：類型判別：特征空間到類型空特征空間到類型空間所作的操作。間所作的操作。四、模式識別系統(tǒng)數(shù)據(jù)采集數(shù)據(jù)采集特征提取特征提取二次特征二次特征提取與選擇提取與選擇分類分類識別識別待識待識對象對象識別結果識別結果數(shù)字化數(shù)字化比特流比特流預處理這個環(huán)節(jié)的內容預處理這個環(huán)節(jié)的內容很廣泛，與要解決的具體很廣泛，與要解決的具體問題有

25、關，例如，從圖象問題有關，例如，從圖象中將汽車車牌的號碼識別中將汽車車牌的號碼識別出來，就需要先將車牌從出來，就需要先將車牌從圖像中找出來，再對車牌圖像中找出來，再對車牌進行劃分，將每個數(shù)字分進行劃分，將每個數(shù)字分別劃分開。做到這一步以別劃分開。做到這一步以后，才能對每個數(shù)字進行后，才能對每個數(shù)字進行識別。以上工作都應該在識別。以上工作都應該在預處理階段完成。預處理階段完成。通常能描述對象的元素很多，通常能描述對象的元素很多，為節(jié)約資源和提高處理速度，有時為節(jié)約資源和提高處理速度，有時更為了可行性，在滿足分類識別正更為了可行性，在滿足分類識別正確率要求的條件下，按某種準則盡確率要求的條件下，按

26、某種準則盡量選用對正確分類識別作用較大的量選用對正確分類識別作用較大的特征。使得用較少的特征就能完成特征。使得用較少的特征就能完成分類識別任務。分類識別任務。分類識別是根據(jù)事先確定的分分類識別是根據(jù)事先確定的分類規(guī)則對前面選取的特征進行分類規(guī)則對前面選取的特征進行分類（即識別）。類（即識別）。40數(shù)據(jù)采集數(shù)據(jù)采集特征提取特征提取二次特征二次特征提取與選擇提取與選擇分類分類識別識別待識待識對象對象識別結果識別結果數(shù)據(jù)采集數(shù)據(jù)采集特征提取特征提取改進分類改進分類識別規(guī)則識別規(guī)則二次特征提二次特征提取與選擇取與選擇訓練訓練樣本樣本改進采集改進采集提取方法提取方法改進特征提改進特征提取與選擇取與選擇制

27、定改進分制定改進分類識別規(guī)則類識別規(guī)則人工人工干預干預正確率正確率測試測試模式識別系統(tǒng)的主要環(huán)節(jié)：模式識別系統(tǒng)的主要環(huán)節(jié)：特征提?。禾卣魈崛。悍柋硎?，如長度、波形、。符號表示，如長度、波形、。特征選擇：特征選擇：選擇有代表性的特征，能夠正確分類選擇有代表性的特征，能夠正確分類學習和訓練：學習和訓練：利用已知樣本建立分類和識別規(guī)則利用已知樣本建立分類和識別規(guī)則分類識別：分類識別：對所獲得樣本按建立的分類規(guī)則進行對所獲得樣本按建立的分類規(guī)則進行分類識別分類識別五、模式識別的方法五、模式識別的方法n決策理論方法（統(tǒng)計識別法）：以判別函數(shù)為基礎，利用判別函數(shù)對模式決策理論方法（統(tǒng)計識別法）：以判別函

28、數(shù)為基礎，利用判別函數(shù)對模式進行分類。進行分類。n句法模式識別（結構模式識別）：將對象分解為若干個基本單元句法模式識別（結構模式識別）：將對象分解為若干個基本單元基元，基元，用基元和他們的結構關系描述對象，運用形式語言理論進行句法分析，根用基元和他們的結構關系描述對象，運用形式語言理論進行句法分析，根據(jù)其是否符合某一類的文法而決定其類別。據(jù)其是否符合某一類的文法而決定其類別。n模糊模式識別：運用模糊數(shù)學的理論和方法解決模式識別問題，適用于分模糊模式識別：運用模糊數(shù)學的理論和方法解決模式識別問題，適用于分類識別對象本身或要求的識別結果具有模糊性的場合。類識別對象本身或要求的識別結果具有模糊性的場

29、合。n人工神經網絡法：是由大量簡單的神經元相互連接而構成的非線性動態(tài)系人工神經網絡法：是由大量簡單的神經元相互連接而構成的非線性動態(tài)系統(tǒng)，具有學習、自組織、聯(lián)想能力，在學習中具有自動提取特征，進行識統(tǒng)，具有學習、自組織、聯(lián)想能力，在學習中具有自動提取特征，進行識別、決策。別、決策。n人工智能方法：人工智能研究如何使機器具有人工智能方法：人工智能研究如何使機器具有人腦功能的理論和方法。將人腦功能的理論和方法。將學習、知識表示、推理等用于模式識別。學習、知識表示、推理等用于模式識別。統(tǒng)計模式識別統(tǒng)計模式識別n統(tǒng)計模式識別：是以決策函數(shù)為基礎，對模式向量進行分類。例w1,w2判別函數(shù)：d(X)=w1x1+w2 x 2+