張鴻賓模式識(shí)別-第一講.ppt

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