2.1.2 模式分類

模式分類是模式識別的核心，現已提出了多種模式分類器的設計方法，總體上可以分為基于貝葉斯決策的分類器設計方法、線性分類器設計方法和非線性分類的設計方法。其中貝葉斯分類器是其他方法的基礎。本節將簡要介紹貝葉斯決策中的最小錯誤率的貝葉斯決策方法、線性分類中的感知器分類器和非線性分類器中的近鄰法（即常用的模板匹配法）。

模式分類是模式識別的主要內容。基于已知類別的若干個樣本的特征，對待測模式進行分類判別是最常用的模式識別的決策方法。這種方法要建立已知類別的樣本庫，根據這些樣本庫建立分類判別函數，這一過程稱為學習或訓練過程，然后對未知類別的新的模式分析它的特征，決定它屬于哪一類。這是一種監督分類的方法。

1.最小錯誤率的貝葉斯決策

貝葉斯分類器在統計模式識別中被稱為最優分類器。采用貝葉斯分類器必須滿足下列兩個先決條件：

·要決策的類別數是一定的。假設要研究的分類問題有c個模式類。

·各類別總體的概率分布是已知的。假設待識別客體的特征向量值 x 所對應的狀態后驗概率P(ωi|x)是已知的；或者，對應于各個類別出現的先驗概率和類條件概率密度函數是已知的。

對于兩類分類問題，最小錯誤率貝葉斯分類的指導思想是：對于模式x，如果它屬于模式類ω1的概率大于屬于模式類ω2的概率，則決策模式x屬于模式類ω1；反之，決策模式x屬于模式類ω2。用數學語言描述為

式中，條件概率P(ωi|x)稱為狀態的后驗概率。

由貝葉斯公式得

同時考慮到P(x)>0，則上面的決策規則可改寫為

式中，p(x|ω1)、p(x|ω2)分別是ω1類和ω2類下模式x的類條件概率密度。

這樣，最小錯誤率貝葉斯分類有兩種形式，一種是后驗概率形式：

另一種是類條件概率密度形式：

將兩種情況推廣到c類情況，最小錯誤率貝葉斯分類規則如下：

·后驗概率形式：

·類條件概率密度形式：

應用貝葉斯決策規則對模式x進行分類的分類器稱為貝葉斯分類器。

對于c類分類問題，按照決策規則可以把特征向量空間（或稱模式空間）分成c個決策域，各決策域的邊界稱為決策邊界。

貝葉斯決策規則可通過判別函數來表達。對于c類分類問題，定義c個判別函數di(x)(i=1,2,???,c)。對照兩種形式下的最小錯誤率貝葉斯決策規則，判別函數可定義為

di(x)=P(ωi|x) (i=1,2,???,c)

及

di (x)= p(x|ωi)P(ωi) (i=1,2,???,c)

這樣，決策規則可寫為

決策邊界由判別函數確定，相鄰的兩個決策域在決策邊界上其判別函數值是相等的。如果決策域Ri與R j是相鄰的，則分割這兩個決策域的決策邊界方程應滿足

一般來說，當模式x為一維時，決策邊界為一個分界點；當x為二維時，決策邊界為一條曲線；當x為n維(n>3)時，決策邊界為一個超曲面。

2.感知器分類器

使用貝葉斯分類器，必須已知樣本的分布，但這一點難以做到。為此必須利用樣本集估計各模式類的類條件概率密度，進而由此設計貝葉斯判別函數，因此，設計出的判別函數可能是線性函數，也可能是各種各樣的非線性函數。

線性分類器指的是判別函數為線性的分類器，其形式簡單，可以根據實際問題，利用已有樣本集，選擇合適的算法估計判別函數中的未知參數。感知器是線性分類器中最經典的方法，本節將在簡單介紹線性判別函數的基礎上，介紹感知器算法。

（1）線性判別函數的基本概念

對于一本樣本集，若存在一個線性分類器能把每個樣本都正確分類，則稱這組樣本集為線性可分的；否則稱為線性不可分的。反過來，若樣本集是線性可分的，則必然存在一個分類器能把每個樣本正確分類。

假設模式向量x是n維的，線性判別函數的一般形式為

式中，w0 =(w稱為增廣模式向量。1,w2,…,w n)稱為權向量；w n+1稱為閾值；w稱為增廣權向量；X =(x1,x2,…,xn,1)

在兩種情況下，可以僅定義一個判別函數：

決策規則為

決策邊界方程為d(x)=0。當d(x)為線性函數時，這個決策邊界便是超平面，超平面的方向和位置分別由w0和wn+1確定。這個超平面將模式空間分割成兩個決策域。

在多類情況下，例如c類，通常有兩種方案實現分類：一對一和一對多。實際上，這兩種方案也適用于非線性分類情況。

在一對一中，要設計c(c-1)/2個分類函數，每個分類函數對兩類進行決策，最后通過投票的方式決定分類結果。

在一對多中，只要設計c個分類器，第i個分類器就會將第i類與其他c-1類分開。

（2）感知器準則函數

對一兩類線性可分問題，訓練樣本集S={X1,X 2,…,X N}。現欲通過感知器準則函數求出判別函數d(x)=wT X 中的權向量w。為便于推導，先對樣本進行規范化處理：

式中，X(i)稱為規范化樣本。規范化后，當Xi∈ω1時，若w將Xi正確分類，則wTX (i)>0；若w將Xi錯誤分類，則wTX (i)<0。當Xi∈ω2時，若w將Xi正解分類，則wTXi<0,wTX (i)>0；若w將Xi錯誤分類，則wTXi>0，wTX (i)<0。

這樣，不管Xi屬于哪一類，若正確分類，則wTX(i) >0；若錯誤分類，則wTX(i) <0。感知器準則函數定義為

式中，Se是被w錯誤分類的樣本集合。對錯誤分類樣本X i，有wT i)( <0，即-wT X(i)>0。因此，上式中的 J(w)總是大于0，而且僅當不存在錯分樣本，即 Se為空集時，J(w)才為0。這時準則函數達到極小值，對應的w就是我們要尋找的權向量w*。

下面采用梯度下降法求解使J(w)達到極小值時的權向量w*。

對J(w)關于w求梯度：

為使J(w)盡快減小，w的變化方向必須與?J(w)的方向一致。由此建立w的迭代公式：

式中，c(k)為步長。從任意給定初始權向量w(1)出發，反復使用上式，就可得到序列

對于感知器準則函數而言，梯度下降法的迭代公式為

感知器準則函數梯度下降法可歸納成如下步驟：

（a）給定初始權向量w(1)和步長c(k)。

（b）找出被權向量w(k)錯分類的樣本，執行第（c）步；如果無錯分類樣本，算法結束。

（c）按式（2-61）的迭代公式求新的權向量w(k+1)，然后轉到第（b）步。

可以證明，采用梯度下降法對于線性可分的樣本集，經過有限步修正，一定能找到一個使準則函數達到極小值的權向量 w*，即算法在有限步內收斂。其收斂速度取決于初始權向量 w(1)和步長c(k)。

獲得權值向量后，就可對待識模式 Xi進行分類，計算di =wTX(i)的值。若 di>0，則將 Xi分到w1類中；若di<0，則將Xi分到w2類中。

感知器分類算法只適用于線性可分的情況，對于線性不可分的情形，其不會收斂。上面給出的算法在迭代的每一步中將樣本集中全體錯分樣本一次性找出，并予以修正。實際上，改進的算法可以處理線性不可分和一次輸入一個樣本的情況。

3.近鄰分類器

如果樣本集線性可分，使用線性分類器就能夠很好地完成分類任務。但是，如果樣本集線性不可分，使用線性分類器的分類，誤差往往偏大。因此，對于線性不可分的樣本集應該采用非線性分類器。

近鄰法是一種典型的非線性分類器，也是一種非參數模式識別方法，與感知器算法一樣，也不需要事先給出先驗概率和類條件概率密度函數等知識，而是直接對樣本進行操作。近鄰法將全部樣本作為標準樣本，根據所使用在待識樣本周圍的近鄰樣本個數，又分為最近鄰法和K-近鄰法。

（1）最近鄰法

最近鄰法的基本思想很簡單：如果待識樣本X與樣本X k之間的距離最小，而X k∈ωi，則決策X屬于ωi類。

也可以用判別函數來說明最近鄰法。設有 c 類模式樣本ω1，ω2，…，ωc，每類有樣本ni個，i=1,2,…,c，則最近鄰法的判別函數為

于是決策法則就是：若有di (X ) < dj (X), i ≠ j，則把X分到第i類中。

最近鄰法在應用中又稱模板匹配法。在模板匹配法中，已知的樣本稱模板，將待識模式與模板逐一進行比對，最相近的模板所屬的類別就是待識模式的類別。在實際應用中，模板匹配法，通常并不采用最近鄰法中使用的距離度量進行相似性比對，而是采用角度相似性函數進行相似性比對，當待識模式與模板的相似性函數值小于指定的閾值時，判定待識模式屬于相應模板所屬的類別。

（2）K-近鄰法

對最近鄰法的一個明顯的改進是K-近鄰法。這個法則就是在X的K個近鄰中，按出現最多的樣本類別來作為X的類別。換句話說，就是先對X的K個近鄰一一找出他們的類別，然后對X的類別作出一次表決。

設有一組樣本，共N個：S={X1,X 2,…,X N}，首先在這N個樣本中找出X的K個近鄰。若k1,k2,…,kc分別是K個近鄰中屬于ω1,ω2,…,ωc類中的樣本數，則可以定義判別函數為

決策規則為：若，則決策x∈ωj。

近鄰法是一種次優方法，其優點是算法簡單，且錯誤率能得到保證，因而得到較為廣泛的應用。其不足是存儲量和計算量都較大。