2.2 統計模式識別

2.2.1 統計模式識別原理與工作流程

1.統計模式識別原理

統計模式識別是最先提出的一種模式識別方法，是受數學中決策理論的啟發而產生的。它一般假定被識別的對象或經過提取的特征向量是符合一定分布規律的隨機變量。首先通過測量與計算，提取待識別模式的一組統計特征，并將其表示為一個量化的特征向量；再將特征提取階段得到的特征向量定義在一個特征空間中，這個空間包含了所有的特征向量，不同的特征向量或者說不同類別的對象都對應于空間中的一點；在分類階段，則利用統計決策的原理，按某種決策函數設計的分類器，對特征空間進行劃分，從而達到識別不同特征的對象的目的。若將具有m個特征參量的m維特征空間進行劃分，使之形成不同區域，則每一區域均對應一類模式，根據參量所分配的具體區域可對事物的模式予以確定。分類方法有定界分類和不定界分類兩種。定界分類是指在分類之前已知界限定義和各類別的樣本，只需設計鑒別函數并用判決函數對模式特征進行判決，將其劃入到所屬類別中去；不定界分類是事前不知道有哪些類別，根據物以類聚的原則進行劃分，如聚類分類法。

在統計模式識別中，貝葉斯決策系統從理論上解決了最優分類器的設計問題，但其實施卻必須首先解決更困難的概率密度估計問題。反向傳播（BP）神經網絡直接從觀測數據（訓練樣本）學習，是更簡便、有效的方法，因而獲得了廣泛的應用，但它是一種啟發式技術，缺乏指導工程實踐的堅實理論基礎。統計推斷理論研究所取得的突破性成果導致現代統計學習理論——VC（Vapnik Chervonenkis）理論的建立；該理論不僅在嚴格的數學基礎上圓滿地回答了ANN中出現的理論問題，且導出了支持向量機（support vector machine，SVM）學習方法。

2.統計模式識別工作流程

一個完整的統計模式識別系統由數據獲取，數據處理，特征提取和選擇，分類決策四部分組成，如圖2.2所示。

（1）數據獲取

數據獲取就是對待識別對象的能夠觀測的一些特征數據進行統計，是指利用各種傳感器把被研究對象的各種信息轉換為計算機可以接收的數字或符號（串）集合。習慣上，稱這種數字或符號（串）所組成的空間為模式空間，這一步的關鍵是傳感器的選取。為了從這些數字或符號（串）中抽取出對識別有效的信息，必須進行數據處理，包括數字濾波和特征提取。

（2）數據處理

預處理是指消除輸入數據或信息中的噪聲，排除不相干的信號，只留下與被研究對象的性質和采用的識別方法密切相關的特征（如表征物體的形狀、周長、面積等）。例如，在進行指紋識別時，指紋掃描設備每次輸出的指紋圖像會隨著圖像對比度、亮度或背景等不同而不同，有時可能還會產生變形，而人們感興趣的僅僅是圖像中的指紋線、指紋分叉點、端點等，不需要指紋的其他部分或背景。因此，需要采用合適的濾波算法，如基于塊方圖的方向濾波、二值濾波等，過濾掉指紋圖像中不必要的部分。

（3）特征提取和選擇

常見的特征有幾何大小、灰度統計特征、邊緣形狀特征、紋理特征、視覺感知特征、灰度梯度特征、分形特征、顏色、對象特征、方向、梯度、密度、特征點、變換域紋理、局部特征等。對數據進行一定的預先處理后，當待識別對象原始特征的數量在預處理后有很多，或者處于一個高維空間中時，為了更好地用計算機進行分類，往往對這些高維的數據進行降維處理。通過一定變換將多個特征用少數幾個特征的線性組合來進行替換，從濾波數據中衍生出有用的信息，從許多特征中尋找出最有效的特征，從而起到一定的降維作用，這個過程就是特征提取。

特征選擇通常是指從待識別對象的眾多特征中選擇若干個能夠有效反映該類對象的特征組，用來表示該類所具有的模式特征向量；該過程去除掉一些無用或冗余的特征，如在曲線識別中對曲線特征的提取就要選擇有代表性的點集。對濾波后的這些特征進行必要的計算后，通過特征選擇和提取形成模式的特征空間。

特征選擇和提取是模式識別的一個關鍵問題。一般情況下，候選特征種類越多，得到的結果越難以求解。因此，數據處理階段的關鍵是濾波算法和特征提取方法的選取。不同的應用場合，采用的濾波算法和特征提取方法以及提取出來的特征也會不同。

（4）分類決策

基于數據處理生成的模式特征空間，用于進行模式識別的最后一步：模式分類或模型匹配。模式分類（即分類決策）就是運用分類器把待識別對象按照前面確定的類別特征進行分類識別的過程。該階段最后輸出的可能是對象所屬的類型，也可能是模型數據庫中與對象最相似的模式編號。模式分類或描述通常是基于已得到分類或描述的模式集合而進行的。人們稱這個模式集合為訓練集，由此產生的學習策略稱為監督學習。在有監督模式識別過程中，選擇好特征集和分類器之后，再用已知類別樣本集對分類器進行訓練，最后再用該分類器對未知類別樣本進行識別。學習也可以是非監督性學習，在此意義下產生的系統不需要提供模式類的先驗知識，而是基于模式的統計規律或模式的相似性學習來判斷模式的類別。在非監督模式識別過程中，選擇好特征向量后根據一定的聚類方法對待識別的樣本進行分類識別，聚類的過程是一個自學習過程，不用進行樣本集的訓練。

2.2.2 模板匹配分類法

在模式識別中，最原始的分類方法是模板匹配分類法（template matching method）.在這種方法中，首先對每一個模式建立一個標準模板，再把待識別的樣品與模板進行匹配比較，若樣品上的大多數單元與作為標準的模板上的大多數單元均相匹配，則稱二者匹配得好；反之，匹配得不好，取匹配最好的樣品作為識別的結果。模板匹配分類法又分光學模板匹配、電子模板匹配等。

光學模板匹配法如圖2.3所示，將待識別模式的正像（樣品）依次與各模板（負模）相匹配，輸出光通量轉換為電流量作為匹配不一致性的度量。若輸出電流為零，則匹配最好。實際應用中若檢測到的電流小于某個預先設定的閾值，則表示待識別的樣品為模板的識別類型，否則不被識別。

模板匹配原理是選擇已知對象作為模板，與圖像中選擇的區域進行比較，從而識別目標。模板匹配依據模板選擇的不同，可以分為兩類：一是，以某一已知目標為模板，在一幅圖像中進行模板匹配，找出與模板相近的區域，從而識別圖像中的物體，如點、線、幾何圖形、文字以及其他物體；二是，以一幅圖像為模板，與待處理的圖像進行比較，識別物體的存在和運動情況。模板匹配的計算量很大，相應的數據的存儲量也很大，且隨著圖像模板的增大，運算量和存儲量以幾何級數增長。若圖像和模板大到一定程度，就會導致計算機無法處理，隨之也就失去了圖像識別的意義。模板匹配的另一個缺點是由于匹配的點很多，理論上最終可以達到最優解，但實際卻很難做到。

2.2.3 最小距離分類法

最小距離分類法是指把模式經數學變換表示成n維特征空間向量X=（x₁，x₂，…，x_n），每一個模式對應空間一個點。兩個點的距離越小，則相應的兩個模式越相似，于是距離最小的模式劃為同一類，如圖2.4所示。矩形塊表示標準樣本，圓圈表示待識樣品，距離標準樣本最近的樣品為一類，較遠的樣品為另一類。

最小距離分類法根據樣本的分散性還可以細分為平均樣本法、平均距離法、最近鄰法等。在實際使用中，根據不同的應用目的可以采用不同的距離函數，如明氏（Minkowsk）、曼哈頓（Manhattan）、歐幾里得（Euclid）、Camberra、切比雪夫（Chebyshev）、哈拉諾比斯（Mahalanobis）、Dice及Yule等距離函數。

最小距離分類法的優點是概念直觀、方法簡單，有利于建立多維空間分類方法的幾何概念，也為其他分類提供了理論基礎，適用于低維、小樣本數、樣本分布小的情況。

2.2.4 幾何分類法

如前所述，每一個模式對應空間一個點。若空間不同類別的點很多，則可以用若干條直線或曲線將這些點按不同的類別區分，這就是幾何分類法的基本思想。這些直線（或曲線）稱為線性的（或非線性的）分類器，也稱為幾何分類器。通過幾何分類方法，將特征空間分解為對應于不同類別的子空間。

二類問題是模式分類的基礎，多類問題可以遞歸地用二類問題來解決。假設樣本X是二維的，設計一個判決函數g（X）=a₁x₁+a₂x₂，其中x₁，x₂為坐標變量，a₁，a₂為系數。將某一不知類別的模式求得X，代入g（X），如為正值，則屬于一類；如為負值，則屬于另一類；如為零，則不可判別，如圖2.5所示。

幾何分類法的缺點是只能處理確定可分問題，當樣本空間相互重疊時，尋找判決函數非常困難，有時甚至是不可能的。

2.2.5 概率分類法

為了克服幾何分類法的缺點，可以采用概率分類法。概率分類法在已知樣本集ω_i的先驗概率P（ω_i）和條件概率P（X|ω_i）的條件下，通過計算模式，屬于ω_i類的后驗條件概率來判斷模式的類別。這是因為后驗概率是一種客觀概率；它表明隨機實驗中事件發生的相對頻率，值越大，事件發生的相對頻率越高，模式屬于ω_i類的可能性越大。

在概率分類法中，需要用到貝葉斯決策理論，通過貝葉斯公式計算后驗概率，建立相應的判決函數和分類器來實現模式識別。

設有m個模式類，待識模式為X，根據貝葉斯公式，后驗概率為

貝葉斯判決法則是：若存在i∈{1，2，…，m}，使得對所有的j（j=1，2，…，i-1，i+1，…，m）均有P（ω_i |X）>P（ω_j |X），則X∈ω_i.

根據貝葉斯判決法則，可得到相應的判決函數G_i（X）>G_j（X）（i≠j）。判決函數把特征空間劃分為m個決策區域，凡落入該區域的X都判決它屬于ω_i類。相應的分類器如圖2.6所示。

2.2.6 聚類分類法

聚類分析法是一種不定界分類法，其前提條件是已知所屬類別的樣品，用判別函數比較未知樣品和已知樣品，從而進行分類。這是一種有教師分類法，已知樣品起教師作用，作為訓練集，對未知樣品按訓練集分類。若沒有訓練集，即沒有教師，則按物以類聚，人以群分的原則，根據樣品間的相似程度自動分類；這是一種無教師分類法。

聚類是基于物以類聚的樸素思想，目的是使得同一類別個體之間的距離盡可能地小，而不同類別個體間的距離盡可能地大。聚類又被稱為非監督分類。和分類學習相比，分類學習的例子或對象有一類別標記，而要聚類的例子則沒有標記，需要由聚類學習算法來自動確定，即把所有一類樣本作為未知樣本進行聚類。隨著科學技術的發展，對分類的要求越來越高，以致有時僅憑經驗和專業知識難以確切分類，于是人們逐漸地把數學工具引用到分類學中，形成數值分類學；之后又將多元分析的技術引入到數值分類學，形成了聚類分析。因此，分類問題和聚類問題根本的不同點為：在分類問題中，知道訓練樣本例的分類屬性值，而在聚類問題中，需要在訓練樣例中找到這個分類屬性值。

聚類分析的算法主要有劃分法（partitioning method）、層次法（hierarchical method）、基于密度的方法（density-based method）、基于網格的方法（grid-based method）以及基于模型的方法（model-based method）等。

1.劃分法

劃分法給定一個由N個元素組成或者記錄的數據集，構造K個分組，每一個分組就代表一個聚類，K<N，且這K個分組滿足下列條件：（1） 每一個分組至少包含一個數據記錄；（2） 每一個數據記錄屬于且僅屬于一個分組。對于給定的K，算法首先給出一種初始的分組方法，然后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次好。這樣，所謂好的標準就是同一分組中的記錄越近越好，而不同分組中的記錄越遠越好。使用這個基本思想的算法有K-MEANS算法、K-MEDOIDS算法、基于隨機搜索的聚類算法（clustering algorithm based on randomized search，CLARANS）算法等。

2.層次法

層次法對給定的數據集進行層次上的分解，直到某種條件滿足為止；具體又可分為“自下而上”和“自上而下”兩種方案。例如，在“自下而上”方案中，初始時每一個數據記錄都組成一個單獨的組；在接下來的迭代中，把相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或某個條件滿足為止。代表算法有利用層次方法的平衡迭代規約和聚類（balanced iterative reducing and clustering using hierarchies，BIRCH）算法、利用代表點聚類（clustering using representatives，CURE）算法、CHAMELEON算法等。

3.基于密度的方法

基于密度的方法與其他方法的一個根本區別是：它不是基于距離的，而是基于密度的。這樣，就能克服基于距離的算法只能發現“類圓形”的聚類的缺點。這個方法的指導思想是只要一個區域中點的密度大過某個閥值，就把它加到與之相近的聚類中去。代表算法有基于密度的有噪聲應用的空間聚類（densitybased spatial clustering of applications with noise，DBSCAN）算法、排序點以識別集群結構（ordering points to identify the clustering structure，OPTICS）算法、基于密度的聚類（density-based clustering，DENCLUE）算法等。

4.基于網格的方法

基于網格的方法是首先將數據空間劃分成為有限個單元的網格結構，所有的處理都是以單個單元為對象的。這樣處理的一個突出優點就是處理速度很快，通常與目標數據庫中記錄的個數無關，只與把數據空間分為多少個單元有關。代表算法有統計信息網絡（statistical information grid，STING）算法、聚類高維空間（clustering in QUEST，CLIQUE）算法、小波變換（WAVE-CLUSTER）算法等。

5.基于模型的方法

基于模型的方法給每一個聚類假定一個模型，然后去尋找能夠很好滿足這個模型的數據集。例如，此模型可以是數據點在空間中的密度分布函數。該方法的前提是目標數據集由一系列概率分布所決定的。

在采用聚類分類法時，首先需要確定聚類準則。確定聚類準則的方法有兩類：一類是憑經驗；另一類是使用準則函數。一種最簡單而又廣泛應用的準則函數是誤差平方和準則：設有n個樣本，分屬于ω₁，ω₂，…，ω_i類，設有n_i個樣品的ω_i類，其均值為

則誤差平方和為

式中，C為聚類數目。

由于聚類算法很多，這里只介紹最大最小距離法，其具體算法步驟如下：

（1）任選某樣品為第一個聚類中心Z₁，如x₁=Z₁；

（2）求出離x₁距離最大的樣品x₂，作為第二個聚類中心Z₂.

（3）求出所有n個樣品與這兩個聚類中心Z₁和Z₂的歐氏距離D_i1和D_i2，其中i=1，2，…，n.

（4）求第三個聚類中心Z₃，若存在max{min（D_i1，D_i2），i=1，2，…，n}>，則x_i=Z₃，轉（5），否則轉（6）.

（5）重復（3）和（4）的計算過程，計算n個樣品與Z₁，Z₂，Z₃的距離D_i1，D_i2，D_i3，求第四個聚類中心Z₄.

（6）將全部樣品按最近距離分到最近的聚類中心。若第一類為{x₁，x₂，x₃}，其聚類中心是Z₁=x₁；若第二類是{x₂，x₆}，其聚類中心是Z₂=x₆；若第三類為{x₃，x₇}，其聚類中心是Z₃=x₇.