模式識別緒論

1、模 式 識 別 Pattern Recognition第一章 緒論 模式識別的研究內(nèi)容、方法和應(yīng)用 模式識別學(xué)科已經(jīng)有近五十年的歷史了模式識別是五十年代末迅速發(fā)展的一門學(xué)科，當(dāng)時的興趣主要在“學(xué)習(xí)機(jī)械”上。在六、七十年代得到了迅速的發(fā)展。P.R.的研究推動了“機(jī)器智能”的發(fā)展，擴(kuò)大了計算機(jī)應(yīng)用的領(lǐng)域。P.R.所研究的理論和方法在許多領(lǐng)域得到了應(yīng)用。P.R.已經(jīng)成為當(dāng)今機(jī)器智能的重要支撐學(xué)科。已廣泛應(yīng)用于工業(yè)自動化、空間和軍事技術(shù)、地質(zhì)、氣象、天文、醫(yī)療、材料分析、化工、產(chǎn)品檢驗(yàn)和控制、經(jīng)濟(jì)上的預(yù)測和預(yù)報等領(lǐng)域。廣義上講如何使機(jī)器具有智能。和人工智能學(xué)科一樣。機(jī)器學(xué)習(xí)的一種方法，參數(shù)、分布、決策

2、的學(xué)習(xí)。狹義上講研究模式的分類、聚類、決策和估計等問題。使機(jī)器具有智能是人類的愿望。（機(jī)器是人手的延長，智能機(jī)是人腦的延長）但使機(jī)器具有智能這個工作很不容易，仍然有許多謎，人腦的機(jī)制不明。盡管已有五十年的歷史，但仍有許多問題有待解決，目前仍然是一個活躍的學(xué)科Ross在1998年的書中說，“一個好的計算機(jī)程序可以幫助銀行對人的信用進(jìn)行評估，幫助醫(yī)生診斷疾病，幫助飛機(jī)駕駛員著陸，所以應(yīng)該更加重視模式識別的教學(xué)。”這一節(jié)介紹什么是模式識別、模式識別的方法、模式識別的應(yīng)用，然后結(jié)合一些例子說明模式識別的一些基本概念。一. 什么是模式識別 使機(jī)器具有能夠感知環(huán)境，自動地對物體進(jìn)行描述、分類、分組的能力是

3、科技、工程中的重要問題 。在社會科學(xué)、生物學(xué)、心理學(xué)、醫(yī)學(xué)、市場分析和預(yù)測、自動化、計算機(jī)視覺、人工智能、遙感、軍事、生物特征識別等問題中有重要應(yīng)用。什么是模式呢？ Watanabe定義模式 “as opposite of a chaos; it is an entity, vaguely defined, that could be given a name.模式，（匈牙利，波蘭，新加波)相似但又不完全相同的一些物體、現(xiàn)象，對象。不混沌（chaos）。 模式可以是一個手寫的字符、一幅指紋圖像、一幅人臉的圖像、一段語音信號等。 模式(pattern)這個單詞的 兩種用法 ：單個，模式類模式的識

4、別/分類可能有兩種方式： 有監(jiān)督的分類/識別（Supervised Classification）：把模式分到預(yù)先定義好的類里去。 無監(jiān)督的分類/識別（Unsupervised Classification, clustering）：基于相似性，把模式聚合成一定的類。二. 模式識別的應(yīng)用 隨著計算機(jī)性能的提高、Internet的迅速發(fā)展，理論研究的深入，和其他研究領(lǐng)域的融合、促進(jìn)（如機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、數(shù)學(xué)、統(tǒng)計學(xué)、計算機(jī)科學(xué)、生物學(xué)等），模式識別的應(yīng)用不僅在它的傳統(tǒng)領(lǐng)域，如文字識別、語音識別、指紋識別、遙感圖像、醫(yī)學(xué)等領(lǐng)域越做越好，而且涌現(xiàn)了很多新的應(yīng)用。模式識別的應(yīng)用（續(xù)）例如數(shù)據(jù)挖掘（d

5、ata mining）、文檔的分類（document classification）、財政金融、股票的預(yù)測、預(yù)報，多媒體數(shù)據(jù)庫的檢索，基于biometrics（生物特征）的人的身份鑒別，人的情感識別等等。特征是數(shù)據(jù)驅(qū)動，自動提取挖掘的，不是專家建議的。 模式識別應(yīng)用的一些例子 問題的領(lǐng)域 應(yīng)用 輸入模式 模式類 生物信息科學(xué) 序列分析 DNA/蛋白質(zhì)(Protein)序列 基因類型/模式 數(shù)據(jù)挖掘 搜索有用的模式 多維空間的點(diǎn) 緊湊（Compact）且分得開的聚類 文檔分類（document） Internet搜索 文本文件 語義類，如商業(yè)、體育、文娛等 模式識別應(yīng)用的一些例子（續(xù)）文本圖像分

6、類 盲人閱讀機(jī)，OCR支票閱讀，郵件分揀文本圖像 字符工業(yè)自動化（計算機(jī)視覺） 印刷電路板的質(zhì)量檢查，裝配線 灰度或距離（深度）圖像 缺陷有/無，抓、裝配零件 模式識別應(yīng)用的一些例子（續(xù)）多媒體數(shù)據(jù)庫檢索 Internet搜索 Video clip Video genres，如行動、會話等 生物特征識別（biometric） 身份鑒別 指紋、面像、虹膜（iris） 人的認(rèn)證，訪問控制 遙感 農(nóng)作物等的預(yù)測、預(yù)報 多頻譜圖像 地形地貌的分類，生長情況 模式識別應(yīng)用的一些例子（續(xù)）語音識別 電話的自動應(yīng)答，翻譯機(jī)，人機(jī)通信 語音波形 語音的單字（詞） 計算機(jī)輔助診斷 X片、CT、fMRI、ECG、

7、EEG、機(jī)器故障診斷一維、兩維信號正常/異常三. 模式識別的方法 隨著供模式識別系統(tǒng)使用的計算機(jī)的性能（速度和存儲能力）的提高，使得使用更復(fù)雜的算法、使用多信息源、多種算法的融合與集成來處理更多的數(shù)據(jù)、更困難的問題成為可能。另一方面，現(xiàn)實(shí)中的問題的要求也越來越高（速度、精度、代價）。 在要解決的問題更復(fù)雜的情況下，單一的模式識別方法、單一的數(shù)據(jù)源已經(jīng)達(dá)不到要求要組合不同的方法（算法）、不同傳感器的信息。（Fusion，Several sensing modality)一個模式識別系統(tǒng)，一般都包括以下三個方面 數(shù)據(jù)的獲取和預(yù)處理 數(shù)據(jù)的表示分類、決策（decision making）在解決不同的

8、具體問題時，要根據(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） 這些方法不是絕對獨(dú)立的。同一種方法有不同的解釋，有時要混合使用。 1.模板匹配 模式識別中使用最早、最簡單、直觀的方法 所謂匹配是一類運(yùn)算，用來確定兩個對象間（點(diǎn)集、曲線、面、形狀）的相似性。在模板匹配中，要有一個模板（一般是一個二維形狀）或一個模式原

9、型（prototype），待匹配的模式和這個預(yù)先存儲好的模板相匹配 模板本身也是從訓(xùn)練樣本中學(xué)習(xí)得來的 模板匹配一般要花費(fèi)較大的計算量，隨著計算機(jī)速度的加快，這種方法變得更可行了 1. 模板匹配(續(xù)）剛性模板匹配的缺點(diǎn)：處理畸變模式難畸變是由傳感器的問題、視點(diǎn)的改變、類內(nèi)偏差大等引起的使用變形模板2. 統(tǒng)計模式識別 在統(tǒng)計模式識別中，每一模式是用一個d維的測量值、特征向量來表示的，它是d維特征空間的一個點(diǎn)。目標(biāo)是選擇這樣的一些特征，使同一類的模式在空間中盡量緊湊，而不同類的模式間盡量分開、不相交 給定一組樣本，模式識別的任務(wù)是要確定決策（分界）面、邊界，以把不同的類分開。 在統(tǒng)計決策理論的方法

10、下，決策邊界是根據(jù)模式的概率分布確定的。這些概率分布是事先知道，或通過學(xué)習(xí)估計得到。 另外一種統(tǒng)計模式識別的工具是判別分析（discriminant analysis）。這種方法是先假定決策邊界的數(shù)學(xué)形式（一次、二次），然后利用訓(xùn)練樣本確定最好的邊界（方程中的一些參數(shù)）。構(gòu)造邊界時一般利用均方差準(zhǔn)則（mean squared error）。再一種方法是從樣本中直接構(gòu)造決策邊界。如Vapnik的支撐向量機(jī)（support vector machine, SVM） Vapnik方法的思想（哲學(xué)，philosophy）是：“當(dāng)只有有限的信息來求解某一問題時，那你就直接去解這一問題，不要試圖去解一個更

11、一般的問題，然后再解決你的特殊問題。因?yàn)槟闶种械男畔⒁苍S對解決你的具體問題是夠（充分）的，但對解決更一般的問題也許就不夠了?！?3. 句法或結(jié)構(gòu)的方法 句法模式識別的方法來源于這樣的思想：復(fù)雜的模式是由簡單的子模式組成的，而子模式又是由更簡單的子模式組成。最簡單的子模式稱為基元（primitives），復(fù)雜模式就是由這些基元以及它們間的相互關(guān)系確定。如同物體組成的原子、分子論。句法模式識別的方法來源于形式語言和自動機(jī)：模式句子，基元字母表，模式結(jié)構(gòu)語法規(guī)則，模式分類語法分析。規(guī)則的產(chǎn)生要靠語法推斷 結(jié)構(gòu)模式識別的優(yōu)點(diǎn)是它的層次結(jié)構(gòu)，用少量的基元和規(guī)則來描述物體。這種方法常用在有一定結(jié)構(gòu)的模式上

12、，例如心電圖（ECG）、紋理圖像（texture）、物體輪廓的分析上 句法模式識別的難點(diǎn)在于如何從噪聲干擾的信號中分割出模式基元，如何從訓(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)想等功能實(shí)現(xiàn)在一個加權(quán)的有向圖

13、式的結(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-Organization 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)用（如分類、特征提取）獲得了很大的普及和成功，其原因在于：

14、 1. 和基于規(guī)則或模型的方法相比，較少依賴特定問題領(lǐng)域的知識； 2.對實(shí)際工作者來講，有有效的學(xué)習(xí)算法可供使用。 人工神經(jīng)網(wǎng)絡(luò)為解決非線性的特征提取和分類提供了一套工具。此外，已經(jīng)存在的統(tǒng)計模式識別方法也可以用神經(jīng)網(wǎng)絡(luò)實(shí)施，可硬件實(shí)施。 Anderson (MIT, 1990)指出：“神經(jīng)網(wǎng)絡(luò)是外行人（amateurs）的統(tǒng)計學(xué)”。 盡管統(tǒng)計的方法和人工神經(jīng)網(wǎng)絡(luò)在基本原理上有很多不同，但它們在方法上是等價或相似的 人工神經(jīng)網(wǎng)絡(luò)為外行提供了求解非線性問題的工具 四種方法的比較 StatPRSyntPRNeurPR模式發(fā)生的機(jī)理 概率模型 形式語法 穩(wěn)定狀態(tài)或連接權(quán)數(shù)組 模式分類（識別、描述）基

15、礎(chǔ) 估計/決策理論 語法剖析parsing NN的特性 四種方法的比較（續(xù)）特征的組織 特征向量 基元及它們的關(guān)系 網(wǎng)絡(luò)輸入或網(wǎng)絡(luò)狀態(tài) 典型的學(xué)習(xí)訓(xùn)練方法有監(jiān)督無監(jiān)督 概率密度/分布的估計（一般是參數(shù)的）聚類分析 形成語法（啟發(fā)式的或語法推斷）聚類分析確定NN系統(tǒng)的參數(shù)，如權(quán)等聚類分析局限 較難表示結(jié)構(gòu)信息 較難學(xué)習(xí)語法規(guī)則 語義信息不清楚，“黑箱”，不透明 四. 模式識別系統(tǒng) 有教師的模式識別系統(tǒng)六. 幾個例子1. 字符識別 印刷的、手寫的 通過OCR等設(shè)備（Optical Character Reader）得到觀測向量 GG字符識別觀察向量：物理的，幾何的，數(shù)學(xué)的，主觀的 特征空間：Rd，

16、0，1d 符號或邏輯值的2. 醫(yī)療診斷問題-心電圖正常/異常 小結(jié)： 模式可以用多維向量空間中的一個矢量來表示，一個點(diǎn) 模式不是確定性的，帶有概率性質(zhì)，要用統(tǒng)計的方法，要用到數(shù)理統(tǒng)計、線性代數(shù)（矩陣）等工具。 分類就是要把特征空間劃分為一些區(qū)域，不相交，類間不重迭。 R1R2R3線性（或分段線性）R1R2R3二次的R1R2R3R4一般的分類區(qū)域、形式線性（或分段線性）二次的一般的R1R2R3R3R2R2R1R1R3R43. 兩類字符識別 10測量矢量:0000.3.000.6.如何確定決策的閾值：作直方圖，可以得到“0”和“1”的分布NP5.5R1R2P1P05.55.5面積小結(jié)： 設(shè)計分類器

17、時不是要求沒有錯分類的，而是在一定意義下使錯誤率最小 下面我們再看一個稍微復(fù)雜的問題 4. 三類字符識別-除了“0”、“1”之外，還要識別“x” X一個特征（占的面積）就不夠了?！?”、“x”的覆蓋面積近似相等。加上另一特征（對角線上1、7、13、19、25面積之和）分類規(guī)則： if else 上面的分類規(guī)則還可以寫成更方便的形式： 定義函數(shù)：這樣，決策規(guī)則可以表示為：若分到 類 則上面的g(y)稱為判別函數(shù)。這種形式特別方便計算機(jī)實(shí)施 計算各個判別函數(shù) 選擇最大的判別函數(shù)值，歸到該類 所形成的決策區(qū)域?yàn)椋?各個分類（決策）邊界可以表示為：gi(y)=gj(y), ij 小結(jié)：增加維數(shù)可以增加

18、模式識別的能力，但計算量要增加，并且需要的樣本數(shù)大大增加。維數(shù)和計算量的折衷。 例3：從25維測量矢量 1維的特征矢量例4：從25維測量矢量 2維的特征矢量5.聚類問題聚類問題，是另一類模式識別問題。如遙感圖像分類。這類問題，樣本類別不知，甚至類別數(shù)目也不知。這類問題經(jīng)常用在化學(xué)、生物、醫(yī)學(xué)、心理學(xué)、社會、經(jīng)濟(jì)預(yù)測、預(yù)報等領(lǐng)域 人材預(yù)測問題： 有200個問題的答卷，每一個問題作了0-10的量化 200維的特征空間 七. 模式識別方法中的一些問題1. 機(jī)器學(xué)習(xí)人的學(xué)習(xí)能力，(如小孩認(rèn)字，能分類),機(jī)器能否做到？什么是機(jī)器學(xué)習(xí)？人腦的不透明過程 機(jī)器的透明過程學(xué)習(xí)目的的一種：使模式識別系統(tǒng)的某個規(guī)

19、定的性能指標(biāo)達(dá)到最優(yōu)。所謂學(xué)習(xí)就是調(diào)整系統(tǒng)的參數(shù)和結(jié)構(gòu)使性能指標(biāo)達(dá)到最優(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”判別中的閾值模式的緊致性和可分性 為了能夠進(jìn)行分類，要求同一類的模式組成一個緊致集合。1.從一點(diǎn)可以均勻過渡到另一點(diǎn)，且途中所有點(diǎn)屬于同一類； 2. 小鄰域內(nèi)仍屬同一類。 如果模式滿足緊致性要求，原則上P.R.沒有什么困難。如果在某個特征空間不滿足緊致性要求，能否找到一個線性或非線性變換，把它變到另一個空間中的緊致集？神經(jīng)網(wǎng)絡(luò)。 距離和相似性度量

20、緊致性要求定義距離度量（在相應(yīng)的空間），及模式間的相似性度量相似不相似。定性、定量描述 本節(jié)小結(jié) 上面介紹了模式信息處理、模式識別的一些基本概念。 參考書：模式識別，邊肇祺，張學(xué)工等著，清華大學(xué)出版社。R.O.Duda, P.E.Hart, and D.G.Stocrk, Pattern Classification. Second ed. 模式分類, 機(jī)械工業(yè)出版社K.Fukunaka, Introduction to Ststiscal Pattern Recognition,Second ed.參考書：4. S.Theodoridis, and K. koutroumbas, Patte

21、rn Recognition, Second ed.,2003.神經(jīng)網(wǎng)絡(luò)和模式識別：5. Simon Haykin, Neural Networks: a comprehensive Foundation, Second ed.,（清華大學(xué)影印版），2001。6. 人工神經(jīng)網(wǎng)絡(luò)與與模擬進(jìn)化計算。 閻平凡，張長水。清華大學(xué)出版社。 神經(jīng)網(wǎng)絡(luò)和模式識別7. C.M.Bishop, Neunal Networks for Pattern Recognition. Oxford: Clarendon Press,1995.8. B.Ripley, Pattern Recognition and Neu

22、ral Networks. Cambridge, Mass: Cambridge Univ. Press,1996.An Example“Sorting incoming Fish on a conveyor according to species using optical sensing”Sea bassSpeciesSalmonProblem AnalysisSet up a camera and take some sample images to extract featuresLengthLightnessWidthNumber and shape of finsPosition

23、 of the mouth, etcThis is the set of all suggested features to explore for use in our classifier! PreprocessingUse a segmentation operation to isolate fishes from one another and from the backgroundInformation from a single fish is sent to a feature extractor whose purpose is to reduce the data by measuring certain featuresThe features are passed to a classifier ClassificationSelect the length of the fish as a possible feature for discriminationThe length is a poor feature alone!Select