張鴻賓模式識別-第一講.ppt

模 式 識 別 Pattern Recognition,張鴻賓,第一章 緒論,模式識別的研究內(nèi)容、方法和應(yīng)用,模式識別學(xué)科已經(jīng)有近五十年的歷史了。,廣義上講如何使機器具有智能。和人工智能學(xué)科一樣。 狹義上講研究模式的分類、聚類、決策和估計問題。 使機器具有智能是人類的愿望。（機器是人手的延長， 智能機是人腦的延長） 但使機器具有智能這個工作很不容易，仍然有許多謎，人腦的機制不明。,盡管已有近五十年的歷史，但仍有許多的問題待解決，也可以說剛起步。,Ross在1998年的書中說，“一個好的計算機程序可以幫助銀行對人的信用評估，幫助醫(yī)生診斷疾病，幫助飛機駕駛員著陸，所以應(yīng)該更加重視模式識別的教學(xué)。 這一節(jié)介紹什么是模式識別、模式識別的方法、模式識別的應(yīng)用，然后結(jié)合一些例子說明模式識別的一些基本概念。,一. 什么是模式識別,使機器具有能夠自動地對物體描述、分類、分組是科技、工程中的重要問題 。 在社會科學(xué)、生物學(xué)、心理學(xué)、醫(yī)學(xué)、市場分析預(yù)測、自動化、計算機視覺、人工智能、遙感、軍事、生物特征識別等問題中有重要應(yīng)用。,什么是模式呢？,Watanabe定義模式 “as opposite of a chaos; it is an entity, vaguely defined, that could be given a name. 模式，（匈牙利，波蘭，新加波) 相似但又不完全相同的一些物體、現(xiàn)象，不混沌（chaos）。 模式可以是一個手寫的字符、一幅指紋圖像、一幅人臉的圖像、一段語音信號等。,模式(pattern)這個單詞的 兩種用法 ：單個，模式類,模式的識別/分類可能有兩種方式： 有監(jiān)督的分類/識別（Supervised Classification）：把模式分到預(yù)先定義好的類里去。 無監(jiān)督的分類/識別（Unsupervised Classification, clustering）：基于相似性，把模式聚合成一定的類。,二. 模式識別的應(yīng)用,隨著計算機性能的提高、Internet的迅速發(fā)展，模式識別的應(yīng)用不僅在它的傳統(tǒng)領(lǐng)域，如文字識別、語音識別、指紋識別、遙感圖像、醫(yī)學(xué)等越做越好，而且涌現(xiàn)了很多新的應(yīng)用。例如數(shù)據(jù)挖掘（data mining）、文檔的分類（document classification）、財政金融、股票的預(yù)測、預(yù)報，多媒體數(shù)據(jù)庫的檢索，基于biometrics（生物統(tǒng)計學(xué)）的人的身份鑒別，甚至有的人研究識別人的感情。 特征是數(shù)據(jù)驅(qū)動提取的，不是專家建議的。,模式識別應(yīng)用的一些例子,模式識別應(yīng)用的一些例子（續(xù)）,模式識別應(yīng)用的一些例子（續(xù)）,模式識別應(yīng)用的一些例子（續(xù)）,三. 模式識別的方法,隨著供模式識別系統(tǒng)使用的計算機的性能（速度和存儲能力）的提高，使得使用更復(fù)雜的算法、使用多信息源、多種算法的融合與集成來處理更多的數(shù)據(jù)成為可能。另一方面，現(xiàn)實中的問題要求更高（速度、精度、代價）。,在要解決的問題更復(fù)雜的情況下，單一的模式識別方法、單一的數(shù)據(jù)源已經(jīng)達不到要求,要組合不同的方法（算法）、不同傳感器的信息。（Fusion，Several sensing modality),一個模式識別系統(tǒng)，基本上都包括以下三個方面,數(shù)據(jù)的獲得和預(yù)處理 數(shù)據(jù)的表示 分類、決策（decision making） 在解決不同的具體問題時，要根據(jù)該問題的性質(zhì)，確定傳感器、預(yù)處理、數(shù)據(jù)的表示和分類算法,常用的模式識別方法,模板匹配（template matching） 統(tǒng)計的方法（statistical P.R.） 句法或結(jié)構(gòu)的方法（syntactic or structural P.R.） 人工神經(jīng)網(wǎng)絡(luò)的方法（artificial neural network, ANN） 這些方法不是絕對獨立的，同一種方法有不同的解釋，有時要混合使用。,1.模板匹配,模式識別中使用最早、最簡單、直觀的方法 所謂匹配是一類運算，用來確定兩個對象間（點集、曲線、面、形狀）間的相似性。 在模板匹配中，要有一個模板（一般是一個二維形狀）或一個模式原型（prototype），待匹配的模式和這個預(yù)先存儲好的模板相匹配 模板本身也是從訓(xùn)練樣本中學(xué)習(xí)得來的 模板匹配一般要花費較大的計算量，隨著計算機速度的加快，這種方法變得更可行了,1. 模板匹配(續(xù)）,剛性模板匹配的缺點：處理畸變模式難 傳感器問題、視點改變、類內(nèi)偏差大 使用變形模板,2. 統(tǒng)計模式識別,在統(tǒng)計模式識別中，每一模式是用一個d維的測量值、特征向量來表示的，它是d維特征空間的一個點。目標(biāo)是選擇這樣的一些特征，使同一類的模式在空間中盡量緊湊，而不同類的模式間盡量分開、不相交 給定一組樣本，模式識別的任務(wù)是要確定決策（分割）面、邊界，以把不同的類分開。,在統(tǒng)計決策理論的方法下，決策邊界是根據(jù)模式的概率分布確定的。這些概率分布是事先知道，或通過學(xué)習(xí)估計得到。,另外一種統(tǒng)計模式識別的工具是判別分析（discriminant analysis）。這種方法是先假定決策邊界的數(shù)學(xué)形式（一次、或二次），然后利用訓(xùn)練樣本確定最好的邊界（方程中的一些參數(shù)）。構(gòu)造邊界時一般利用均方差準(zhǔn)則（mean squared error）。,再一種方法是從樣本中直接構(gòu)造決策邊界。如Vapnik的支撐向量機（support vector machine）,Vapnik方法的思想（哲學(xué)，philosophy）是：“當(dāng)只有有限的信息來求解某一問題時，那你就直接去解這一問題，不要試著去解一個更一般的問題，然后再解決你的特殊問題。因為你手中的信息也許對解決你的具體問題是夠（充分）的，但對解決更一般的問題也許就不夠了?！?3. 句法或結(jié)構(gòu)的方法,句法模式識別的方法來源于這樣的思想：復(fù)雜的模式是由簡單的子模式組成的，而子模式又是由更簡單的子模式組成。最簡單的子模式稱為基元（primitives），復(fù)雜模式就是由這些基元以及它們間的相互關(guān)系確定。如同物體組成的原子、分子論。,句法模式識別的方法來源于形式語言和自動機：模式句子，基元字母表，模式結(jié)構(gòu)語法規(guī)則，模式分類語法分析。規(guī)則的產(chǎn)生要靠語法推斷,結(jié)構(gòu)模式識別的優(yōu)點是它的層次結(jié)構(gòu)，用少量的基元和規(guī)則來描述物體。這種方法常用在有一定結(jié)構(gòu)的模式上，例如心電圖（ECG）、紋理圖像（texture）、物體輪廓的分析上,句法模式識別的難點在于如何從噪聲干擾下分割出模式基元，如何從訓(xùn)練樣本中推斷出語法規(guī)則來,存在組合“爆炸”的問題，要求大的訓(xùn)練樣本集、高計算復(fù)雜度。 “Conundrum of combinatorial complexity”,4. 人工神經(jīng)網(wǎng)絡(luò)的方法,人工神經(jīng)網(wǎng)絡(luò)是一個超大規(guī)模的并行計算系統(tǒng)。它由大量很簡單的計算單元相互連接組成。模擬人腦的計算，它試圖把學(xué)習(xí)、泛化（generalization）、自適應(yīng)（adaptivity）、容錯（fault tolerance）、分布式表示和計算、聯(lián)想等功能實現(xiàn)在一個加權(quán)的有向圖式的結(jié)構(gòu)上：圖的節(jié)點神經(jīng)元，有向邊（加權(quán)的）神經(jīng)元輸入、輸出連接,人工神經(jīng)網(wǎng)絡(luò)的突出優(yōu)點是它可以學(xué)習(xí)復(fù)雜的非線性輸入輸出關(guān)系（從樣本序列中）,常用的神經(jīng)網(wǎng)絡(luò)有兩種 : 前饋性網(wǎng)絡(luò)：分層 多層感知器（Multilayer Perceptron) 徑向基函數(shù)網(wǎng)（Radial Basis Function) 互連型網(wǎng)絡(luò)：互連 Kohonen的 Self-Oeganization Map Hopfield型的互連網(wǎng),網(wǎng)絡(luò)學(xué)習(xí)的過程是利用提供的樣本修改連接權(quán)（connection weights）或網(wǎng)絡(luò)的結(jié)構(gòu)（增減神經(jīng)元 ),人工神經(jīng)網(wǎng)絡(luò)的應(yīng)用（分類、特征提?。┇@得了很大的普及，其原因是： 1. 對特定問題域的知識較少依賴（和基于規(guī)則或模型的方法相比） 2.對實際工作者來講，有有效的學(xué)習(xí)算法可供使用 人工神經(jīng)網(wǎng)絡(luò)為解決非線性的特征提取和分類提供了一套工具。此外，已經(jīng)存在的統(tǒng)計模式識別方法也可以用神經(jīng)網(wǎng)絡(luò)實施,Anderson(MIT, 1990)指出：“神經(jīng)網(wǎng)絡(luò)是外行人（amateurs）的統(tǒng)計學(xué)”。,盡管統(tǒng)計的方法和人工神經(jīng)網(wǎng)絡(luò)在基本原理上有很多不同，但它們在方法上是等價或相似的 人工神經(jīng)網(wǎng)絡(luò)為外行提供了求解非線性問題的工具,四種方法的比較,四種方法的比較（續(xù)）,四. 模式識別系統(tǒng),模式識別系統(tǒng),六. 幾個例子,1. 字符識別 印刷的、手寫的 通過OCR等設(shè)備（Optical Character Reader）得到觀測向量,G,字符識別,觀察向量：物理的，幾何的，數(shù)學(xué)的，主觀的,特征空間：Rd，0，1d,符號或邏輯值的,2. 醫(yī)療診斷問題-心電圖正常/異常,小結(jié)：,模式可以用多維向量空間中的一個矢量來表示，一個點 模式不是確定性的，帶有概率性質(zhì)，要用統(tǒng)計的方法，要用到數(shù)理統(tǒng)計、線性代數(shù)（矩陣）等工具。 分類就是要把特征空間劃分為一些區(qū)域，不相交，類間不重迭。,分類區(qū)域、形式,線性（或分段線性）,二次的,一般的,R1,R2,R3,R3,R2,R2,R1,R1,R3,R4,3. 兩類字符識別,測量矢量:,0,如何確定決策的閾值：作直方圖，可以得到“0”和“1”的分布,R1,R2,P1,P0,5.5,5.5,面積,N,小結(jié)：,設(shè)計分類器時不是要求沒有錯分類的，而是在一定意義下使錯誤率最小 下面我們再看一個稍微復(fù)雜的問題,4. 三類字符識別-除了“0”、“1”之外，還要識別“x”,一個特征（占的面積）就不夠了?！?”、“x”的覆蓋面積近似相等。加上另一特征（對角線上1、7、13、19、25面積之和）,分類規(guī)則：,if else,上面的分類規(guī)則還可以寫成更方便的形式：,定義函數(shù)： 這樣，決策規(guī)則可以表示為：若,分到 類,則,上面的g(y)稱為判別函數(shù)。這種形式特別方便計算機實施,計算各個判別函數(shù) 選擇最大的判別函數(shù)值，歸到該類 所形成的決策區(qū)域為：,各個分類（決策）邊界可以表示為： gi(y)=gj(y), ij,小結(jié)：增加維數(shù)可以增加模式識別的能力，但計算量要增加，并且需要的樣本數(shù)大大增加。維數(shù)和計算量的折衷。 例3：從25維測量矢量 1維的特征矢量 例4：從25維測量矢量 2維的特征矢量,5.聚類問題,聚類問題，是另一類模式識別問題。如遙感圖像分類。這類問題，樣本類別不知，甚至類別數(shù)目也不知。這類問題經(jīng)常用在化學(xué)、生物、醫(yī)學(xué)、心理學(xué)、社會、經(jīng)濟預(yù)測、預(yù)報等領(lǐng)域 人材預(yù)測問題： 有200個問題的答卷，每一個作了0-10的量化 200維的特征空間,七. 模式識別方法中的一些問題,1. 機器學(xué)習(xí) 人的學(xué)習(xí)能力，(如小孩認字，能分類),機器能否做到？ 什么是機器學(xué)習(xí)？ 人腦的不透明過程 機器的透明過程 學(xué)習(xí)目的的一種：使模式識別系統(tǒng)的某個規(guī)定的性能指標(biāo)達到最優(yōu)。,所謂學(xué)習(xí)就是調(diào)整系統(tǒng)的參數(shù)和結(jié)構(gòu)使性能指標(biāo)達到最優(yōu)。,在P.R.中，一般采用錯分率的平均值或期望作準(zhǔn)則函數(shù)： J(c)=E R( F(y,c) 找c* F：決策規(guī)則，R()：損失函數(shù)，E：數(shù)學(xué)期望 c：要學(xué)習(xí)的參數(shù)，例如“0”、“1”判別中的閾值,模式的緊致性和可分性,為了能夠進行分類，要求同一類的模式組成一個緊致集。 1. 從一點可以均勻過渡到另一點，且途中所有點屬于同一類； 2. 小鄰域內(nèi)仍屬同一類。,如果模式滿足緊致性要求，原則上P.R.沒有什么困難。如果在某個特征空間不滿足緊致性要求，能否找到一個線性或非線性變換，把它變到另一個空間中的緊致集？神經(jīng)網(wǎng)絡(luò)。,距離和相似性度量,緊致性要求定義距離度量（在相應(yīng)的空間），及模式間的相似性度量 相似不相似。定性、定量描述,本節(jié)小結(jié),上面介紹了模式信息處理、模式識別的一些基本概念。,參考書：,模式識別，邊肇祺，張學(xué)工等著，清華大學(xué)出版社。 R.O.Duda, P.E.Hart, and D.G.Stocrk, Pattern Recognition and Scene Analysis, Second ed. K.Fukunaka, Introduction to Ststiscal Pattern Recognition,Second ed.,參考書：,4. S.Theodoridis, and K. koutroumbas, Pattern Recognition, Second ed.,2003. 神經(jīng)網(wǎng)絡(luò)和模式識別： 5. Simon Haykin, Neural Networks: a comprehensive F