模(Mo)式識別

孫和利武漢大學遙感信息工程學院sunheli@126.com第一頁，共六十六頁。1引(Yin)言第二頁，共六十六頁。2課程對(Dui)象模式識別學科碩士研究生的專業(yè)基礎課第三頁，共六十六頁。3與模(Mo)式識別相關的學科統(tǒng)計學概率論線性代數(shù)（矩陣計算）形式語言機器學習人工智能圖像處理計算機視覺第四頁，共六十六頁。4教學(Xue)方法著重講述模式識別的基本概念，基本方法和算法原理。注重理論與實踐緊密結合實例教學：通過大量實例講述如何將所學知識運用到實際應用之中避免引用過多的、繁瑣的數(shù)學推導。第五頁，共六十六頁。5教學(Xue)目標掌握模式識別的基本概念和方法有效地運用所學知識和方法解決實際問題為研究新的模式識別的理論和方法打下基礎第六頁，共六十六頁。6教(Jiao)學效果基本：完成課程學習，通過考試，獲得學分。提高：能夠?qū)⑺鶎W知識和內(nèi)容用于課題研究，解決實際問題。飛躍：通過模式識別的學習，改進思維方式，為將來的工作打好基礎，終身受益。第七頁，共六十六頁。7教材/參考(Kao)文獻舒寧等，模式識別的理論與方法，武漢大學出版社，2004。.邊肇祺等，模式識別（第二版），清華大學出版社，2000。蔡元龍，模式識別，西北電訊工程學院出版社，1986。第八頁，共六十六頁。8本門課程的主要內(nèi)(Nei)容第一章概論第二章貝葉斯決策理論第三章判別函數(shù)與確定性分類器第四章聚類分析第五章模式特征分析與選取第六章模糊集合理論在模式識別中的應用第七章句法模式識別第八章神經(jīng)網(wǎng)絡在模式識別中的應用第九頁，共六十六頁。9第一章模式(Shi)識別概論§1-1模式識別的基本概念§1-2模式識別系統(tǒng)§1-3模式識別的應用§1-4模式識別的基本問題第十頁，共六十六頁。10§1-1模式識別的(De)基本概念一.模式識別的基本定義

模式(pattern)------存在于時間，空間中可觀察

的事物，具有時間或空間分布的信息。

------識別的對象，是對客體定量的或結構的描述。廣義地說，存在于時間和空間中可觀察的物體，如果我們可以區(qū)別它們是否相同或是否相似，都可以稱之為模式。模式所指的不是事物本身，而是從事物獲得的信息，因此，模式往往表現(xiàn)為具有時間和空間分布的信息。第十一頁，共六十六頁。11模式的直觀特(Te)性:可觀察性可區(qū)分性相似性

第十二頁，共六十六頁。12模式識別(PatternRecognition)------用計算機實現(xiàn)人對各種事物或現(xiàn)象的分析,描述,判斷,識別。周圍物體的認知：桌子、椅子人的識別：張三、李四聲音的辨別：汽車、火車，狗叫、人語氣味的分辯：炸帶魚、紅燒肉人和動物的模式識別能(Neng)力是極其平常的，但對計算機來說卻是非常困難的。模式類------具有共同特征的模式的集合。識別------對模式類的分辨，判斷，分類。目的------提高計算機的感知能力，開拓計算機的應用。第十三頁，共六十六頁。13模式識別(Bie)的研究目的：利用計算機對物理對象進行分類，在錯誤概率最小的條件下，使識別的結果盡量與客觀物體相符合。Y=F(X)X的定義域取自特征集Y的值域為類別的標號集F是模式識別的判別方法第十四頁，共六十六頁。14模式識別與圖象識別，圖象處理的關系

模式識別是模擬人的某些功能

模擬人的視(Shi)覺:計算機+光學系統(tǒng)模擬人的聽覺:計算機+聲音傳感器模擬人的嗅覺和觸覺:計算機+傳感器第十五頁，共六十六頁。15二.模式識(Shi)別的發(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)計模式識別仍是模式識別的主要理論。第十六頁，共六十六頁。1650年代NoamChemsky提出形式語言理論美籍華人付京蓀提出句法結構(Gou)模式識別。60年代L.A.Zadeh提出了模糊集理論，模糊模式識別理論得到了較廣泛的應用。80年代Hopfield提出神經(jīng)元網(wǎng)絡模型理論。近些年人工神經(jīng)元網(wǎng)絡在模式識別和人工智能上得到較廣泛的應用。90年代小樣本學習理論，支持向量機也受到了很大的重視。第十七頁，共六十六頁。17三.關于模式識別的國(Guo)內(nèi)、國(Guo)際學術組織1973年IEEE發(fā)起了第一次關于模式識別的國際會議“ICPR”，成立了國際模式識別協(xié)會---“IAPR”，每2年召開一次國際學術會議。1977年IEEE的計算機學會成立了模式分析與機器智能（PAMI）委員會，每2年召開一次模式識別與圖象處理學術會議。國內(nèi)的組織有電子學會，通信學會，自動化協(xié)會，中文信息學會….。第十八頁，共六十六頁。18§1-2模式識別方法(Fa)及模式識別系統(tǒng)模式識別方法模式識別系統(tǒng)的目標：在特征空間和解釋空間之間找到一種映射關系，這種映射也稱之為假說。特征空間：從模式得到的對分類有用的度量、屬性或基元構成的空間。解釋空間：將c個類別表示為i

,i=1,2……,c 其中為所屬類別的集合，稱為解釋空間。第十九頁，共六十六頁。19假說的兩種獲得(De)方法監(jiān)督學習、概念驅(qū)動或歸納假說：在特征空間中找到一個與解釋空間的結構相對應的假說。在給定模式下假定一個解決方案，任何在訓練集中接近目標的假說也都必須在“未知”的樣本上得到近似的結果。依靠已知所屬類別的的訓練樣本集，按它們特征向量的分布來確定假說（通常為一個判別函數(shù)），只有在判別函數(shù)確定之后才能用它對未知的模式進行分類；對分類的模式要有足夠的先驗知識，通常需要采集足夠數(shù)量的具有典型性的樣本進行訓練。第二十頁，共六十六頁。20假說的(De)兩種獲得方法（續(xù)）非監(jiān)督學習、數(shù)據(jù)驅(qū)動或演繹假說：在解釋空間中找到一個與特征空間的結構相對應的假說。這種方法試圖找到一種只以特征空間中的相似關系為基礎的有效假說。在沒有先驗知識的情況下，通常采用聚類分析方法，基于“物以類聚”的觀點，用數(shù)學方法分析各特征向量之間的距離及分散情況；如果特征向量集聚集若干個群，可按群間距離遠近把它們劃分成類；這種按各類之間的親疏程度的劃分，若事先能知道應劃分成幾類，則可獲得更好的分類結果。第二十一頁，共六十六頁。21模式分類(Lei)的主要方法統(tǒng)計模式識別

概率分類法聚類分析

模糊模式識別句法（結構）模式識別人工神經(jīng)網(wǎng)絡方法第二十二頁，共六十六頁。22統(tǒng)計模(Mo)式識別基于概率統(tǒng)計模型得到各類別的特征向量的分布，以取得分類的方法。特征向量分布的獲得是基于一個類別已知的訓練樣本集。是一種監(jiān)督分類的方法，分類器是概念驅(qū)動的。概率分類法第二十三頁，共六十六頁。23聚類(Lei)分析目標：用某種相似性度量的方法將原始數(shù)據(jù)組織成有意義的和有用的各種數(shù)據(jù)集。是一種非監(jiān)督學習的方法，解決方案是數(shù)據(jù)驅(qū)動的。第二十四頁，共六十六頁。24模(Mo)糊模(Mo)式識別

基于模糊數(shù)學理論，利用隸屬函數(shù)描述事物的不確定性。識別根據(jù)研究對象對于某模糊子集的隸屬程度采用最大隸屬原則識別法、擇近原則識別法，模糊聚類分析法對模式進行識別。第二十五頁，共六十六頁。25結構模(Mo)式識別該方法通過考慮識別對象的各部分之間的聯(lián)系來達到識別分類的目的。識別采用結構匹配的形式，通過計算一個匹配程度值（matchingscore）來評估一個未知的對象或未知對象某些部分與某種典型模式的關系如何。當成功地制定出了一組可以描述對象部分之間關系的規(guī)則后，可以應用一種特殊的結構模式識別方法–句法模式識別，來檢查一個模式基元的序列是否遵守某種規(guī)則，即句法規(guī)則或語法。第二十六頁，共六十六頁。26人工神經(jīng)網(wǎng)(Wang)絡方法神經(jīng)網(wǎng)絡是受人腦組織的生理學啟發(fā)而創(chuàng)立的。由一系列互相聯(lián)系的、相同的單元（神經(jīng)元）組成。相互間的聯(lián)系可以在不同的神經(jīng)元之間傳遞增強或抑制信號。增強或抑制是通過調(diào)整神經(jīng)元相互間聯(lián)系的權重系數(shù)來實現(xiàn)。神經(jīng)網(wǎng)絡可以實現(xiàn)監(jiān)督和非監(jiān)督學習條件下的分類。第二十七頁，共六十六頁。27模式識別系統(tǒng)的基本構(Gou)成數(shù)據(jù)獲取特征提取和選擇預處理分類決策分類器設計第二十八頁，共六十六頁。28數(shù)據(jù)獲?。河糜嬎銠C可以運算的符號來表示所研究的對象二維圖像：文字、指紋、地圖、照片等一維波形：腦電圖、心電圖、季節(jié)震動波形等物理參量和邏輯值：體溫、化驗數(shù)據(jù)、參量正常與否的描述預處理單元：去噪聲，提取有用信息，并對輸入測量儀(Yi)器或其它因素所造成的退化現(xiàn)象進行復原（圖像處理）第二十九頁，共六十六頁。29特征提取和選擇：對原始數(shù)據(jù)進行變換，得(De)到最能反映分類本質(zhì)的特征測量空間：原始數(shù)據(jù)組成的空間特征空間：分類識別賴以進行的空間模式表示：維數(shù)較高的測量空間->維數(shù)較低的特征空間分類器設計：分類器設計的主要功能是通過訓練確定判決規(guī)則，使按此類判決規(guī)則分類時，錯誤率最低。把這些判決規(guī)則建成標準庫。分類決策：在特征空間中對被識別對象進行分類。第三十頁，共六十六頁。30模式識別過(Guo)程實例在傳送帶上用光學傳感器件對魚按品種分類 鱸魚(Seabass) 品種 鮭魚(Salmon)第三十一頁，共六十六頁。31識別(Bie)過程數(shù)據(jù)獲取：架設一個攝像機，采集一些樣本圖像，獲取樣本數(shù)據(jù)預處理：去噪聲，用一個分割操作把魚和魚之間以及魚和背景之間分開第三十二頁，共六十六頁。32識別過(Guo)程特征提取和選擇：對單個魚的信息進行特征選擇，從而通過測量某些特征來減少信息量長度亮度寬度魚翅的數(shù)量和形狀嘴的位置，等等…分類決策：把特征送入決策分類器第三十三頁，共六十六頁。33第三十四頁，共六十六頁。34第三十五頁，共六十六頁。35第三十六頁，共六十六頁。36第三十七頁，共六十六頁。37第三十八頁，共六十六頁。38第三十九頁，共六十六頁。39模式分類器的(De)評測過程數(shù)據(jù)采集特征選取模型選擇訓練和測試計算結果和復雜度分析，反饋第四十頁，共六十六頁。40分(Fen)類器評測開始數(shù)據(jù)采集結束訓練和測試計算結果和復雜度分析，反饋特征選取模型選擇第四十一頁，共六十六頁。41訓練和(He)測試訓練集：是一個已知樣本集，在監(jiān)督學習方法中，用它來開發(fā)出模式分類器。測試集：在設計識別和分類系統(tǒng)時沒有用過的獨立樣本集。系統(tǒng)評價原則：為了更好地對模式識別系統(tǒng)性能進行評價，必須使用一組獨立于訓練集的測試集對系統(tǒng)進行測試。第四十二頁，共六十六頁。42實例：統(tǒng)(Tong)計模式識別19名男女同學進行體檢，測量了身高和體重，但事后發(fā)現(xiàn)其中有4人忘記填寫性別，試問（在最小錯誤的條件下）這4人是男是女？體檢數(shù)值如下：第四十三頁，共六十六頁。43實例：統(tǒng)計(Ji)模式識別（續(xù)）待識別的模式：性別（男或女）測量的特征：身高和體重訓練樣本：15名已知性別的樣本特征目標：希望借助于訓練樣本的特征建立判別函數(shù)（即數(shù)學模型）第四十四頁，共六十六頁。44實例：統(tǒng)計模(Mo)式識別（續(xù)）由訓練樣本得到的特征空間分布圖第四十五頁，共六十六頁。45實例：統(tǒng)計模(Mo)式識別（續(xù)）從圖中訓練樣本的分布情況，找出男、女兩類特征各自的聚類特點，從而求取一個判別函數(shù)（直線或曲線）。只要給出待分類的模式特征的數(shù)值，看它在特征平面上落在判別函數(shù)的哪一側，就可以判別是男還是女了。結論：1.錯誤最小。2.存在錯分。第四十六頁，共六十六頁。46實(Shi)例：句法模式識別問題：如何利用對圖像的結構信息描述，識別如下所示圖片：地板M墻壁NLTBDEXZY第四十七頁，共六十六頁。47實例：句法模式識別(Bie)（續(xù)）將整個場景圖像結構分解成一些比較簡單的子圖像的組合；子圖像又用一些更為簡單的基本圖像單元來表示，直至子圖像達到了我們認為的最簡單的圖像單元（基元）；所有這些基元按一定的結構關系來表示，利用多級樹結構對其進行描述（這種描述可以采用形式語言理論）。第四十八頁，共六十六頁。48實例：句法模式識(Shi)別（續(xù)）多級樹描述結構地板M墻壁NLTBDEXZY景物:A

景物A物體B背景C三角體D長方體E三角形T面L面Y地板M墻壁N面Z面X第四十九頁，共六十六頁。49實例：句法模式識別(Bie)（續(xù)）訓練過程：用已知結構信息的圖像作為訓練樣本，先識別出基元（比如場景圖中的X、Y、Z等簡單平面）和它們之間的連接關系（例如長方體E是由X、Y和Z三個面拼接而成），并用字母符號代表之；然后用構造句子的文法來描述生成這幅場景的過程，由此推斷出生成該場景的一種文法。第五十頁，共六十六頁。50實(Shi)例：句法模式識別（續(xù)）識別過程：先對未知結構信息的圖像進行基元提取及其相互結構關系的識別；然后用訓練過程獲得的文法做句法分析；如果能被已知結構信息的文法分析出來，則該幅未知圖像與訓練樣本具有相同的結構（識別成功），否則就不是這種結構（識別失?。?。第五十一頁，共六十六頁。51§1-3模式識別的(De)應用1.字符識別：包括印刷體字符的識別、手寫體字符的識別（脫機）、各種OCR設備例如信函分揀、文件處理、卡片輸入、支票查對、自動排板、期刊閱讀、稿件輸入、在線手寫字符的識別（聯(lián)機），各種書寫輸入板。2.醫(yī)療診斷：心電圖分析，腦電圖分析，醫(yī)學圖像分析，染色體，癌細胞識別，疾病診斷。3.遙感：數(shù)字攝影測量，資源衛(wèi)星照片，氣象衛(wèi)星照片處理。第五十二頁，共六十六頁。524.安全：指紋識別、人臉識別、監(jiān)視和報警系統(tǒng)5.工程：產(chǎn)品缺陷檢測、特征識別、語音識別、機器翻譯、電(Dian)話號碼自動查詢、自動導航系統(tǒng)、污染分析、大氣、水源、環(huán)境監(jiān)測。6.經(jīng)濟學：股票交易預測、企業(yè)行為分析。7.天文學：天文望遠鏡圖像分析、自動光譜學。8.生物學：自動細胞學、染色體特性研究、遺傳研究。9.軍事應用：航空攝像分析、雷達和聲納信號檢測和分類、自動目標識別。第五十三頁，共六十六頁。53§1-4模式識別的基(Ji)本問題一.模式(樣本)表示方法向量表示

:假設一個樣本有n個變量(特征)Ⅹ=(x1,x2,…,xn)T2.矩陣表示:N個樣本，n個變量(特征)第五十四頁，共六十六頁。543.幾何表示一維表示X1=1.5X2=3

二(Er)維表示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)T第五十五頁，共六十六頁。554.基元（鏈碼）表示：在右側的圖中八個基元分別表示0，1，2，3，4，5，6，7，八個方(Fang)向和基元線段長度。則右側樣本可以表示為X1=006666

這種方法將在句法模式識別中用到。第五十六頁，共六十六頁。56二.模式類的緊(Jin)致性1.緊致集：同一類模式類樣本的分布比較集中，沒有或臨界樣本很少，這樣的模式類稱緊致集。第五十七頁，共六十六頁。572.臨(Lin)界點(樣本)：在多類樣本中，某些樣本的值有微小變化時就變成另一類樣本稱為臨界樣本（點）。3.緊致集的性質(zhì)①要求臨界點很少②集合內(nèi)的任意兩點的連線,在線上的點屬于同一集合③集合內(nèi)的每一個點都有足夠大的鄰域,在鄰域內(nèi)只包含同一集合的點4.模式識別的要求：滿足緊致集，才能很好的分類；如果不滿足緊致集，就要采取變換的方法,滿足緊致集.第五十八頁，共六十六頁。58三.相似與(Yu)分類

1.兩個樣本xi，xj之間的相似度量滿足以下要求：①應為非負值②樣本本身相似性度量應最大③度量應滿足對稱性④在滿足緊致性的條件下，相似性應該是點間距離的單調(diào)函數(shù)

第五十九頁，共六十六頁。592.用各種距離表示相似性：

①絕對(Dui)值距離(“cityblock”distance)已知兩個樣本xi=(xi1,xi2,xi3,…,xin)Txj=(xj1,xj2,xj3,…,xjn)T又稱城市距離，街坊距離。第六十頁，共六十六頁。60②歐幾里德距離（歐氏距離）③明考(Kao)夫斯基距離（明氏距離）

其中當m=1時為絕對值距離，當m=2時為歐氏距離第六十一頁，共六十六頁。61④切比雪夫距(Ju)離m趨向無窮大時明氏距離的極限情況⑤馬哈拉諾比斯距離其中m為特征向量，C為協(xié)方差矩陣，使用的條件是樣本符合正態(tài)分布。第六十二頁，共六十六頁。62因為x1,x2

的夾角小，所(Suo)以x1,