數(shù)學(xué)模式識(shí)別方法總結(jié)

機(jī)器實(shí)現(xiàn)自動(dòng)分類有兩大類方法：模板匹配對(duì)特征空間劃分子空間(每類的勢(shì)力范圍)這里是針對(duì)第二種方法而言的。分類方法總結(jié)貝葉斯判別：基于樣本概率，若無(wú)概率信息，需參數(shù)估計(jì)。非參數(shù)判別：利用樣本直接計(jì)算判決函數(shù)中的有關(guān)參數(shù)。

監(jiān)督（有教師）：利用某些已知類別的樣本進(jìn)行分類。

Fisher線性判別近鄰分類

無(wú)監(jiān)督ANNSVM

非監(jiān)督（無(wú)教師）：聚類分析、自組織競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)非參數(shù)判別的思路：設(shè)定一組判別函數(shù),并利用樣本直接計(jì)算判決函數(shù)中的有關(guān)參數(shù)。貝葉斯判別的核心問(wèn)題是：樣本為特征向量X時(shí)，它屬于哪一類可能性有多大。如能確定屬于各個(gè)類別的百分比(概率)，分類決策就有了依據(jù)。最大后驗(yàn)概率判決準(zhǔn)則最小風(fēng)險(xiǎn)貝葉斯判決準(zhǔn)則如果P(ω1|x)>P(ω2|x),則判決x屬于ω1;如果P(ω1|x)<P(ω2|x),則判決x屬于ω2;如果P(ω1|x)=P(ω2|x),則判決x屬于ω1或?qū)儆讦?。

這種決策稱為最大后驗(yàn)概率判決準(zhǔn)則,也稱為貝葉斯(Bayes)判決準(zhǔn)則。

假設(shè)已知P(ωi)和p(x|ωi)(i=1,2,…,m),最大后驗(yàn)概率判決準(zhǔn)則就是把樣本x歸入后驗(yàn)概率最大的類別中,也就是,則x∈ωj。最大后驗(yàn)概率判決準(zhǔn)則

幾種最大后驗(yàn)概率判決準(zhǔn)則的等價(jià)形式:

(1)若，則x∈ωj;

(2)若，則x∈ωj;

(3)若則x∈ωj。其中,L(x)稱為似然比，lnL(x)稱為對(duì)數(shù)似然比。

由于已知P(ωi)和p(x|ωi),因此我們希望找到P(ωi|x)與它們之間的關(guān)系。假設(shè)特征變量為X，由Bayes公式在最大后驗(yàn)概率判決準(zhǔn)則中,x∈ωj的決策區(qū)域Rj為

(j=1,2,…,m)

最大后驗(yàn)概率判決準(zhǔn)則的一個(gè)優(yōu)良性質(zhì)就是使平均錯(cuò)誤概率達(dá)到最小。因此,最大后驗(yàn)概率判決準(zhǔn)則又稱為最小錯(cuò)誤概率判決準(zhǔn)則。

基于最小錯(cuò)誤概率的貝葉斯決策理論就是按后驗(yàn)概率的大小作判決的。

類條件概率密度通過(guò)計(jì)算，換算成如下圖所示的后驗(yàn)概率分布?？梢钥闯觯赬值小時(shí)，判斷為ω1

類是比較合理的，判斷錯(cuò)誤的可能性小。

例如,假設(shè)模式x為一維的情況,得到的兩類分界點(diǎn)為t,將x軸分為兩個(gè)區(qū)域R1和R2,其中,紋理區(qū)域的面積表示平均錯(cuò)誤概率,即圖中，，圖2-2平均錯(cuò)誤概率計(jì)算示意圖在作出決策時(shí)，要考慮所承擔(dān)的風(fēng)險(xiǎn)?；谧钚★L(fēng)險(xiǎn)的貝葉斯決策的基本思路是給每一種決策規(guī)定一個(gè)損失值(或代價(jià)),將其作為因錯(cuò)誤決策而導(dǎo)致的損失的度量。最小風(fēng)險(xiǎn)貝葉斯判決準(zhǔn)則

(1)決策αj:將樣本x的類別判為第j類。

(2)損失函數(shù)λ(αj,ωi):對(duì)真實(shí)類別為第i類的樣本采取決策αj所帶來(lái)的損失。

(3)條件風(fēng)險(xiǎn)當(dāng)樣本x的真實(shí)類別未知時(shí),決策αj的條件風(fēng)險(xiǎn)是對(duì)x為所有可能的真實(shí)類別條件下將樣本判為第j類的代價(jià)求平均,即最小風(fēng)險(xiǎn)貝葉斯判決準(zhǔn)則:如果則判決x∈ωk?？紤]兩類別一維特征向量情況，R1與R2兩個(gè)區(qū)域的分界線不再是t，而是向左移了一段距離（t1)。這是由于損失函數(shù)λ12比λ21大所造成。在發(fā)生位移這一區(qū)域內(nèi)，盡管P(x|ω1)P(ω1)>P(x|ω2)P(ω2)，但是為了減少將ω2錯(cuò)判為ω1所帶來(lái)的嚴(yán)重?fù)p失，在P(x|ω2)P(ω2)不很小的情況下，使將ω2類樣本錯(cuò)判為ω1的可能性減小，以減小決策所承擔(dān)的風(fēng)險(xiǎn)。當(dāng)然平均錯(cuò)誤率則明顯增大了。t1t線性分類器

Fisher線性判決分段線性分類器

近鄰分類器有教師訓(xùn)練的ANNSVM監(jiān)督（有教師）分類方法

線性判別函數(shù)的形式如下:

線性分類器設(shè)計(jì)的關(guān)鍵在于確定權(quán)向量w和閾值權(quán)w0。線性判別函數(shù)常數(shù)其幾何意義為d維歐幾里德空間中的一個(gè)超平面。

(1)w是超平面的法向量。

對(duì)于兩類分類問(wèn)題,線性判決函數(shù)的幾何意義在于利用一個(gè)超平面實(shí)現(xiàn)對(duì)特征空間Rd的劃分。超平面示意圖w指向R1,R1中的點(diǎn)在H的正側(cè)。R2中的點(diǎn)在H的負(fù)側(cè)。

(2)g(x)是x到超平面距離的一種代數(shù)距離。x可以分解為超平面的法向量x在H上的投影x到H的垂直距離w方向上的單位法向量，該距離有符號(hào),當(dāng)符號(hào)為正時(shí),表明x對(duì)應(yīng)的點(diǎn)在超平面的正側(cè),反之在負(fù)側(cè)。

(2)確定一個(gè)準(zhǔn)則函數(shù)J,要求滿足以下兩個(gè)條件:①J是樣本集、w和w0的函數(shù);②J的值反映分類器性能,它的極值對(duì)應(yīng)于“最好”的決策。

(3)用最優(yōu)化技術(shù)求解準(zhǔn)則函數(shù),得到極值點(diǎn)對(duì)應(yīng)的w*和w*0。線性分類器設(shè)計(jì),其關(guān)鍵在于最優(yōu)準(zhǔn)則以及相應(yīng)的求解方法。

(1)選擇樣本集z={x1,x2,…,xN}。樣本集中的樣本來(lái)自兩類且類別已知。線性判別函數(shù)設(shè)計(jì)的一般步驟Fisher線性判決Fisher線性判決的基本思想是尋找一個(gè)最好的投影方向,當(dāng)特征向量x從d維空間映射到這個(gè)方向上時(shí),兩類能最好地分開(kāi)。這個(gè)方法實(shí)際上涉及特征維數(shù)的壓縮問(wèn)題。分析w1方向之所以比w2方向優(yōu)越，可以歸納出這樣一個(gè)準(zhǔn)則：即向量W的方向選擇應(yīng)能使兩類樣本投影的均值之差盡可能大些，而使類內(nèi)樣本的離散程度盡可能小。這就是Fisher準(zhǔn)則函數(shù)的基本思路。尋找最好的投影方向,在數(shù)學(xué)上就表現(xiàn)為尋找最好的變換方向w*。定義Fisher線性判決函數(shù)為分子反映了映射后兩類中心的距離平方,該值越大,類間可分性越好;分母反映了兩類的類內(nèi)離散度,其值越小越好;從總體上來(lái)講,JF(w)的值越大越好。在這種可分性評(píng)價(jià)標(biāo)準(zhǔn)下,使JF(w)達(dá)到最大值的w即為最佳投影方向。將JF(w)化成w的顯示格式故Fisher線性判決函數(shù)化為求JF(w)的極大值點(diǎn)利用w*,將樣本x往該方向上投影,可得在投影空間內(nèi)的決策準(zhǔn)則為:若y>y0,則x∈ω1,否則x∈ω2。閾值y0的典型選擇有:

第一步：計(jì)算參量。

(1)各類樣本的均值向量μi:

(2)樣本類內(nèi)離散度矩陣Si總類內(nèi)離散度矩陣Sw:第二步：計(jì)算最優(yōu)投影方向，并

將樣本往該方向上投影。第三步：決策。在投影空間內(nèi)的決策準(zhǔn)則為:若y>y0,則x∈ω1,否則x∈ω2。Fisher線性判決分段線性分類器線性分類器的分界面是一個(gè)超平面。當(dāng)類與類之間不能用任何一個(gè)超平面實(shí)現(xiàn)劃分時(shí),類間的分界面應(yīng)是一個(gè)超曲面?？紤]到曲線可以由多個(gè)線段近似表達(dá),曲面可以由多個(gè)平面逼近,因此,也可以用多個(gè)超平面近似表達(dá)超曲面,分段線性分類器正是基于這種思路而設(shè)計(jì)的一種分類器。

圖4-17

兩類非線性可分時(shí)可用多段超平面分開(kāi)分段線性距離分類器最小距離分類器,其判決函數(shù)為即這時(shí)類間的決策面為

它是兩類均值點(diǎn)連線的垂直平分面。<><>圖4-18

分段線性距離分類器示意圖近鄰分類器

將均值作為代表點(diǎn)時(shí),最小距離分類器的實(shí)質(zhì)就是將樣本判屬于與代表點(diǎn)距離最近的類。近鄰法最初是由Cover和Hart于1968年提出的,它的基本特點(diǎn)是將樣本集中的任何一個(gè)樣本都作為代表點(diǎn),它實(shí)質(zhì)上是一種分段線性分類器。

最近鄰法

最近鄰法的主要特點(diǎn)就是將樣本判屬它的最近鄰(和它距離最近的代表點(diǎn))所在的類。

假定有m個(gè)類別ω1,ω2,…,ωm的模式識(shí)別問(wèn)題,每類有Ni(i=1,2,…,m)個(gè)樣本,規(guī)定類ωi的判別函數(shù)為其中,xki表示第i類的第k個(gè)元素。判決準(zhǔn)則:若，則x∈ωj

k近鄰法

最近鄰分類器的判決思想是將樣本判屬與它距離最小的樣本所屬的類,這種方法的特點(diǎn)是概念容易理解,最近鄰樣本和待分類樣本在距離意義下是最相似的。其缺點(diǎn)在于受隨機(jī)噪聲影響較大,尤其是在兩類的交疊區(qū)內(nèi)。圖4-21隨機(jī)噪聲對(duì)最近鄰分類結(jié)果的影響對(duì)于待分類樣本x,在N個(gè)樣本集中找出它的k個(gè)近鄰,設(shè)k個(gè)樣本中屬于第i類的為ki個(gè)(i=1,2,…,m),即定義判別函數(shù):判決準(zhǔn)則為若，則x∈ωj圖4-22

8-近鄰示意圖多輸入、單輸出u1,u2,…,un是從外部環(huán)境或其他神經(jīng)元傳來(lái)的輸入信號(hào);k1,k2,…,kn是對(duì)應(yīng)于輸入的連接權(quán)值;θ是一個(gè)閾值;函數(shù)g:R→R為傳遞函數(shù),也稱為激活函數(shù)；y表示神經(jīng)元的輸出。人工神經(jīng)元模型

(1)閾值型函數(shù)。階躍函數(shù)：符號(hào)函數(shù)：常用的基本激活函數(shù)

(2)分段線性函數(shù)：(3)Sigmoid函數(shù)：或Sigmoid函數(shù)示意圖(a)取值在(0,1)內(nèi);(b)取值在(－1,1)內(nèi)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

神經(jīng)網(wǎng)絡(luò)是由大量的人工神經(jīng)元廣泛互連而成的網(wǎng)絡(luò)。根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不同,神經(jīng)網(wǎng)絡(luò)可分為：層次型網(wǎng)絡(luò)：前饋網(wǎng)絡(luò)（感知器、BP網(wǎng)絡(luò)、RBF網(wǎng)絡(luò)）和反饋網(wǎng)絡(luò)（Hopfield網(wǎng)絡(luò)）網(wǎng)狀結(jié)構(gòu)網(wǎng)絡(luò)（自組織競(jìng)爭(zhēng)網(wǎng)絡(luò)）

1.前饋網(wǎng)絡(luò)

結(jié)構(gòu)：神經(jīng)元分層排列，網(wǎng)絡(luò)由輸入層、中間層(也稱隱含層)、輸出層組成；

特點(diǎn)：每一層的各神經(jīng)元只能接受前一層神經(jīng)元的輸出,作為自身的輸入信號(hào)。單層前饋神經(jīng)網(wǎng)絡(luò)

多層前饋神經(jīng)網(wǎng)絡(luò)多層前饋網(wǎng)絡(luò)有一個(gè)或多個(gè)隱含層。2.反饋網(wǎng)絡(luò)特點(diǎn)：反饋網(wǎng)絡(luò)的輸出層接有反饋環(huán)路,將網(wǎng)絡(luò)的輸出信號(hào)回饋到輸入層。單層反饋神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)方法

神經(jīng)網(wǎng)絡(luò)信息處理包括學(xué)習(xí)和執(zhí)行兩個(gè)階段。(1)學(xué)習(xí)階段也稱為訓(xùn)練階段：給定訓(xùn)練樣本集,按一定的學(xué)習(xí)規(guī)則調(diào)整權(quán)系數(shù),使某種代價(jià)函數(shù)達(dá)到最小,也就是使權(quán)系數(shù)收斂到最優(yōu)值。

(2)執(zhí)行階段：利用學(xué)習(xí)階段得到的連接權(quán)系數(shù),對(duì)輸入信息進(jìn)行處理,并產(chǎn)生相應(yīng)的輸出。根據(jù)學(xué)習(xí)過(guò)程的組織與管理,神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)可分為:①有教師(有監(jiān)督)學(xué)習(xí)。對(duì)每一個(gè)輸入訓(xùn)練樣本,都有一個(gè)期望得到的輸出值(也稱教師信號(hào)),將它和實(shí)際輸出值進(jìn)行比較,根據(jù)兩者之間的差值不斷調(diào)整網(wǎng)絡(luò)的連接權(quán)值,直到差值減小到預(yù)定的要求。②無(wú)教師(無(wú)監(jiān)督、自組織)學(xué)習(xí)。網(wǎng)絡(luò)的學(xué)習(xí)完全是一種自我調(diào)整的過(guò)程,不存在教師信號(hào)。輸入模式進(jìn)入網(wǎng)絡(luò)后,網(wǎng)絡(luò)按照預(yù)先設(shè)定的某種規(guī)則反復(fù)地自動(dòng)調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)和連接權(quán)值,使網(wǎng)絡(luò)最終具有模式分類等功能。

學(xué)習(xí)規(guī)則wij(k+1)=wij(k)+Δwij單層前饋神經(jīng)網(wǎng)絡(luò)

yjjxii

wij

輸入模式為n維矢量x=(x1,x2,…,xn)T，輸入層包含n個(gè)節(jié)點(diǎn)；輸出模式為m個(gè)類別ω1,ω2,…,ωm，輸出層有m個(gè)輸出節(jié)點(diǎn)

y1,y2,…,ym,每個(gè)輸出節(jié)點(diǎn)對(duì)應(yīng)一個(gè)模式類；輸入節(jié)點(diǎn)i和輸出節(jié)點(diǎn)j

的連接權(quán)為wij(i=1,2,…,n;j=1,2,…,m)。單層感知器網(wǎng)絡(luò)結(jié)構(gòu)圖傳遞函數(shù)

f

采用符號(hào)函數(shù)。輸出層第j個(gè)神經(jīng)元的輸出為單層感知器網(wǎng)絡(luò)結(jié)構(gòu)圖若yj=1,則將輸入模式x判屬ωj類;若yj=－1,則輸入模式x不屬于ωj類。學(xué)習(xí)規(guī)則：

BP：反向傳播(BackPropagation)BP網(wǎng)絡(luò)是采用誤差反向傳播算法的多層前饋網(wǎng)絡(luò)傳遞函數(shù)為S型函數(shù)學(xué)習(xí)規(guī)則采用梯度下降算法在網(wǎng)絡(luò)學(xué)習(xí)過(guò)程中,把輸出層節(jié)點(diǎn)的期望輸出(目標(biāo)輸出)與實(shí)際輸出(計(jì)算輸出)的均方誤差,逐層向輸入層反向傳播,分配給各連接節(jié)點(diǎn),并計(jì)算出各連接節(jié)點(diǎn)的參考誤差,在此基礎(chǔ)上調(diào)整各連接權(quán)值,使得網(wǎng)絡(luò)的期望輸出與實(shí)際輸出的均方誤差達(dá)到最小。BP網(wǎng)絡(luò)

逐個(gè)處理的BP算法訓(xùn)練步驟如下:

(1)初始化。根據(jù)實(shí)際問(wèn)題,設(shè)計(jì)網(wǎng)絡(luò)連接結(jié)構(gòu)。例如,輸入變量和輸出變量個(gè)數(shù)、隱含的層數(shù)、各層神經(jīng)元的個(gè)數(shù),并隨機(jī)設(shè)置所有的連接權(quán)值為任意小值。假設(shè)輸入變量為n個(gè),輸出變量為m個(gè),每個(gè)訓(xùn)練樣本的形式為(x1,x2,…,xn;y1,y2,…,ym),其中,y=(y1,y2,…,ym)是輸入為x=(x1,x2,…,

xn)時(shí)的期望輸出。

(2)輸入一個(gè)樣本,用現(xiàn)有的權(quán)值計(jì)算網(wǎng)絡(luò)中各神經(jīng)元的實(shí)際輸出。

(3)計(jì)算局部誤差ε(i)p,k(i=1,2,…,l,l+1),l為隱含層的個(gè)數(shù)。輸出誤差第r隱含層各神經(jīng)元的輸出輸出層隱含層輸出層傳遞函數(shù)的偏導(dǎo)

(4)計(jì)算權(quán)值變化量ΔW(i)p,k(i=1,2,…,l,l+1),

并更新相應(yīng)的權(quán)值。

(5)輸入另一樣本,轉(zhuǎn)步驟(2)。把訓(xùn)練集中所有樣本都加到網(wǎng)絡(luò)上，直到網(wǎng)絡(luò)收斂且均方誤差小于給定的閾值，訓(xùn)練結(jié)束。此時(shí)，固定權(quán)值，網(wǎng)絡(luò)就構(gòu)成了一個(gè)模式分類器。成批處理時(shí),將全部N個(gè)樣本依次輸入,累加N個(gè)輸出誤差后對(duì)連接權(quán)進(jìn)行一次調(diào)整,連接權(quán)矩陣各行的調(diào)整方程可表示為支持向量機(jī)支持向量機(jī)(SupportVectorMachine,SVM)建立在統(tǒng)計(jì)學(xué)習(xí)理論的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則之上。結(jié)構(gòu)風(fēng)險(xiǎn)包括經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信風(fēng)險(xiǎn)。針對(duì)兩類分類問(wèn)題,SVM在高維空間中尋找一個(gè)超平面作為兩類的分割,以保證最小的分類錯(cuò)誤率。少數(shù)與超平面最接近的那些訓(xùn)練樣本稱為支持向量,它們決定了推廣性能。

線性可分情況

SVM從線性可分情況下的最優(yōu)分類發(fā)展而來(lái)。

利用支持向量機(jī)進(jìn)行樣本分類也包括訓(xùn)練和執(zhí)行兩個(gè)階段。

(1)樣本訓(xùn)練：給定訓(xùn)練樣本集訓(xùn)練線性分類器,即確定線性分類器參數(shù)。

(2)樣本識(shí)別：利用訓(xùn)練好的分類器對(duì)輸入樣本進(jìn)行識(shí)別。樣本的誤分次數(shù)與分類間隔密切相關(guān)。最優(yōu)分類線就是要求分類線不但能將兩類樣本正確分開(kāi),而且使分類間隔最大。(yi=+1)(yi=－1)將判別函數(shù)進(jìn)行歸一化,使兩類所有樣本