第七章模式識別

1、 第八章 模式識別方法8.1 導(dǎo)言 模式識別方法是50年代早期提出來的，60-80年代在各個學(xué)科得到廣泛應(yīng)用?；瘜W(xué)學(xué)科在此期間發(fā)表了數(shù)百篇文章。到80年代，模式識別方法發(fā)展為一種非常成熟的多元分析方法。 在低維空間如二維、三維空間，人眼對模式識別能力最強，但是在高維空間則必須借助于數(shù)學(xué)的方法才能夠?qū)δＪ竭M行區(qū)分。 什么是模式識別？ 模式識別屬于多元識別方法，它借助于計算機來揭示隱含于事物內(nèi)部規(guī)律的一種綜合分析技術(shù)。 模式識別是一種從大量信息和數(shù)據(jù)出發(fā),在專家經(jīng)驗和已有認識的基礎(chǔ)上,利用計算機和數(shù)學(xué)推理的方法對形狀、模式、曲線、數(shù)字、字符格式和圖形自動完成識別的過程。 模式識別包括相互關(guān)聯(lián)的兩個

2、階段,即學(xué)習階段和實現(xiàn)階段,前者是對樣本進行特征選擇,尋找分類的規(guī)律；后者是根據(jù)分類規(guī)律對未知樣本集進行分類和識別。 模式識別的類型： 有監(jiān)督模式識別：在模式識別時，如果樣品的類別是已知的，先用一組已知類別的化合物作為訓(xùn)練集，建立判別模型，再用建立的模型根據(jù)相似性原則來對未知樣品進行識別，稱謂判別分析。判別分析是在事先知道樣本類別的特征的情況下建立判別模型對樣本進行識別歸屬，是一種有監(jiān)督模式識別。包括線形判別，逐步判別方法，KNN法，SIMCA方法，神經(jīng)網(wǎng)絡(luò)等 無監(jiān)督模式識別：如果預(yù)先不知道樣本的類別，要在學(xué)習過程中根據(jù)樣本的相似性對被識別的樣品進行識別分類和歸類，稱為聚類分析。聚類分析是完全

3、依靠樣本自然特性進行識別的方法，是一種無監(jiān)督模式識別。包括最小生成樹，聚類分析等。 模式識別的研究內(nèi)容和應(yīng)用領(lǐng)域： 廣義的模式識別屬計算機科學(xué)中智能模擬的研究范疇,內(nèi)容非常廣泛,包括聲音和語言識別、文字識別、指紋識別、聲納信號和地震信號分析、照片圖片分析、化學(xué)模式識別等等。 模式識別可用來進行有機結(jié)構(gòu)解析，研究定量構(gòu)效關(guān)系，識別真?zhèn)紊唐?，追蹤污染源，進行藥物分類、臨床診斷、礦物普查、考古研究、材料設(shè)計等。模式識別過程的框圖8.2 數(shù)據(jù)的表示及預(yù)處理 在模式識別中，常把實驗數(shù)據(jù)表示為多維空間中的點。對于一次觀察（稱樣本），可用矢量表示為x = (x1, x2, , xn)T 其中xi 為變量i

4、的值，n為多維空間的維數(shù)，即變量個數(shù)。在模式識別中亦稱為特征（feature）。一張圖譜可視為多維空間的一個點，它的維數(shù)即為從此譜中抽提出的特征數(shù)。如C-13 NMR譜，它的特征為化學(xué)位移，而對于質(zhì)譜，它的特征為質(zhì)/荷（m/e）比。 在n維空間中，兩個樣本的相似程度反映了n對變量間的接近程度。反過來，這n對變量在多維空間中的距離是與其相互間的相似程度相關(guān)的。數(shù)據(jù)預(yù)處理是模式識別中的重要步驟：標準化處理（autoscaling） 1. 其中，xij 為標準化數(shù)據(jù)。經(jīng)標準化處理的變量權(quán)重相同，均值為零，方差為1n1jijixn1xSnxxiijijn112()iiij ijSxxxmnmmnnxx

5、xxxxxxxX2122221112112. 加權(quán)重 加權(quán)重僅在有監(jiān)督的方法中使用，其方法可用一定的經(jīng)驗式統(tǒng)計，給比較重要的變量賦予較大的權(quán)重。3.轉(zhuǎn)化 當變量的動態(tài)范圍較大時，可采用x，x 或 （x + 常數(shù)） 等方法進行轉(zhuǎn)化。對于光譜圖譜，可采用傅立葉、Hadamard 和 Naesh 等轉(zhuǎn)化。4.組合 將原來的變量，按一定的方式，如變量相加，變量相減等進行組合以產(chǎn)生新的變量。8.3 特征的提取和壓縮特征的提取和壓縮特征的提取特征的提取 特征的提取在模式識別中是最關(guān)鍵的一步，在化學(xué)中所用特征可分為6類：（1）拓撲特征：此類特征由分子的二維聯(lián)接表派生出來，如原子以及鍵的屬性，記數(shù)，原子的連接

6、度，以及各種各樣的拓撲指數(shù)。（2）幾何特征：此類特征由分子的三維模型派生出來，其中包括慣性動量，分子體積，分子表面積和分子的立體參數(shù)等。（3）電子特征：如原子電荷，原子半徑，鍵的強度等。（4）物理化學(xué)參數(shù)：如化合物的疏水性等。（5）化合物的譜圖特征：如碳-13 NMR共振波譜中的化學(xué)位移，質(zhì)譜中的峰位（即m/e）等。1.（6）化學(xué)組成：如某類物質(zhì)的無機化學(xué)組成及有機化學(xué)組成等。2. 特征的壓縮 在模式識別中應(yīng)使特征量數(shù)減至最少。一是因為有些特征與分類關(guān)系不大，若把這些特征作為模式變量，則可能導(dǎo)致分類結(jié)果變差；二是所選擇的特征量數(shù)目(空間維數(shù))d與樣本數(shù)n之間要保持一個合適的比例,通常至少是n/

7、d3,最好是n/d10。增加特征量數(shù)目d,相應(yīng)地需要增加樣本數(shù)n,增加實驗費用。 在特征選擇中，有一些屬于統(tǒng)計方法，如數(shù)據(jù)的偏差，以所得結(jié)果為依據(jù)來確定比較重要的特征。另外一些方法是測試特征對分類結(jié)果的影響，影響大的選之，否則，棄之，特征的選擇在模式識別中盡管研究得很廣泛，但尚無一通用理論可以遵循。目前常用選擇方法有；偏差權(quán)重法 對分類而言，偏差大的變量比偏差小的變量要更重要。特征i 的標準偏差vi為： 其中，為特征 i 之均值，即即Vi值可作為特征選取的一種判據(jù)。Vnxxiijijn1112()xnkijxnx112. Fisher比率法 特征i 的Fisher 比率Fi為： 式中，xi1，

8、xi2 分別為類 1 和類 2 中變量的均值， vi1，vi2分別為類 1 和類 2 中變量 i 的標準偏差。 Fi 值越大，意味著變量 i 重要。21221)(iiiiivvxxF3. 概率比率法 概率比率的定義為： 其中， pi1 和 pi2 分別為第 i 個特征在類 1 和類 2 中出現(xiàn)的概率。剔除特征的規(guī)則為：（1）在兩類中均不出現(xiàn)的特征；（2）在兩類中出現(xiàn)次數(shù)很少；（3）在兩類中出現(xiàn)的概率相同。4. 逐步判別 逐步判別分析為模式識別的一種方法，同時，該種方法亦用于變量的選擇。特別是兩變量共線，即相關(guān)系數(shù)較大時，用逐步判別方法可以消去不應(yīng)選取的變量。21iiipplgR 5. 學(xué)習機械

9、法 學(xué)習機械（learning machine）法為模式識別的一種方法。同時它可用于特征的選取。在特征選取時首先將判別函數(shù)系數(shù) wi 賦予任意初值，如均為“+1”。然后，逐步校正 wi ，直到 wi 不能夠進一步改善為止。再將wi均賦值以“-1”，重復(fù)如上迭代過程。同樣，程序執(zhí)行到wi 不能進一步改善為止。在兩次結(jié)果中，剔除 wi 符號有改變的特征。重復(fù)如上全部過程，直到再無特征可以剔除為止。6. 主成分分析法 在初選的特征量間可能存在相關(guān)，此時亦可采用原特征的線性組合，以形成新的特征量，并根據(jù)它們的特點，選取與問題最相關(guān)的特征參與以后的分類。 如何進行變量間的組合，主成分分析為我們提供了一條

10、可行的途徑。主成分分析所得本征矢量為原變量的線性組合，且本征矢量間相互正交，根據(jù)本征值的大小可以選擇少量本征矢量作為新的特征。8.4 相似系數(shù)和距離 在n維空間中，有向量xi = (xi1, xi2, , xin) 。其中，xij表示 i 第個樣本的第 j 個特征。下面介紹在模式識別中常用的相似系數(shù)及距離。8.4.1 相似系數(shù)1. 夾角余弦如進行圖譜比較時，當兩張圖完全相同時cos ij = 1，完全不同時， cos ij = 0。nknkjkiknkjkikij)x)(x(xxcos112212. 相關(guān)系數(shù)其中 分別為第 i 個和第 j 個樣本的均值。3. 指數(shù)相似系數(shù)其中， sk 表示第

11、k 個變量的標準偏差。)xx()xx()xx)(xx(rnkjjknkiikjjknkiikij21211nkk)xx(ijsenrjkik124321jixx 和4. 非參數(shù)法如果與相似，上述相關(guān)系數(shù)近于1，否則近于0。nkjkjknkjkijijxxxxr11),max(),min(nkjkjknkjkijijxxxxr11),max(21),min(nkjkiknkjkijijxxxxr11),min(8.4.2 距離 令D (xi, xj) 為樣本 xi 與 xj 之間的距離，則在泛函分析中一般要求 D (xi, xj) 滿足（1） D (xi, xj) = 0，當xi = xj時（2

12、） D (xi, xj) 0，當xi xj時（3） D (xi, xj) = D (xi, xj)（4） D (xi, xj) D (xi, xk) + (xk, xj)nkqqjkikijxxD11明考斯基距離當q=1時，叫做絕對距離或城市距離（city block）， 當q =2時，即為歐氏距離。nkjkikijxxD1nkjkikijxxD12122. 馬氏距離用V表示協(xié)方差陣，它的元素用 vij 表示其中，n為變量數(shù)。如果V的逆矩陣存在，則馬氏距離為 馬氏距離在一定程度上克服了由于變量的相關(guān)性及變量間量綱不同產(chǎn)生的影響。tjijiijxxVxxD)()(1)xx)(xx(nVjkjnk

13、ikiij1113. 蘭氏距離此公式一般對 xij 是同號時使用。nk)xx(xxDjkikjkikij14.海明（Haming）距離5. 塔尼莫特（Tanimoto）距離D = 1 Dij式中，AND，OR，和XOR分別為邏輯操作“與”， “或”和“排斥”。)x,x(OR)x,x(ANDDjkikjkikijnk)x ,x(XORDjkikij18.5 模式識別方法8.5.1 有監(jiān)督的方法 這一類方法是用一組已知類別的化合物作訓(xùn)練集，并由這個訓(xùn)練集得到判別模型，然后用另外一組已知歸屬的“未知樣本”來測試所得數(shù)學(xué)模型。在訓(xùn)練中，所得到的識別能力通常稱為識別率（recognition）,用測試集

14、所得結(jié)果通常成為預(yù)測率（prediction）。 在訓(xùn)練集中，如以兩類劃分為例，在類1和類2中樣本數(shù)不應(yīng)差別太大，而以兩類樣本數(shù)相等為宜。Fisher意義下的判別 方法的基本思想：設(shè)法找出一最佳投影方向，將m維空間中的點投影到低維空間，如一維空間中，使不同類的點盡可能分離開來，然后在低維空間再分類。 下面以兩個母體分類的情況為例： 我們將樣本的觀察數(shù)據(jù)記為 xigk i = 1, 2, ,m; g = 1, 2, ,G; k = 1, 2, , ng ; n1 + n2 + + ng = N 其中g(shù)表示類，ng表示g中的樣本數(shù)。投影，實際即為線性變換。m維空間向一維空間的投影可寫為： g =

15、1,2; k = 1,2, ng 式中 v = (v1, v2 vm)T 就是我們要尋找的投影方向。令w(Z)和b(Z)分別為Z的組內(nèi)和組間離差：niigkigkxvz1GgnkggkgZZZw11)()(GgggZZnZb1)()(可以證明：Ggjkjgknkigigkijxxxxwg11)( )( mimjjiijvvwZw11)( mimjjiijvvbZb11)(ggjigiiggijxxxxnb1)(其中及其中為使Z的組間與組內(nèi)離差比)()(ZWZbr 達到最大投影方向v = (v1, v2 vm)T ，則v應(yīng)滿足0ivr經(jīng)演算，最終可得到：)(211iimijijxxcvw其中mj

16、jiivxxnnnnrc1212121)(1c與i無關(guān)，對所求的v1, v2 vm僅起放大或縮小的作用，并不影響vi之間的相對比例關(guān)系。在實際計算時，可取一適當值，如令c=(N-2)以提高計算的精度。（8.1） 由式8.1可求出矢量v，因為投影空間為一直線，則可計算兩組樣本在投影空間上的均值miigigxvZ1及其在直線上的分解點2211*ZNnZNnZ對于任意給定的 x = (x1, x2, xm)T ，算出它們的判別函數(shù)，即投影點：當Z（x）Z*時，把x歸為第一個母體，當Z（x）1時，未知樣本所屬的類，用獲多數(shù)“選票”的方法確定。所謂多數(shù)選票，即在最近鄰的樣本中，視其屬于哪一類為多，則未知

17、樣本就屬于哪一類。8.5.2 無監(jiān)督方法系統(tǒng)聚類分析1. 聚類分析是數(shù)理統(tǒng)計中的一種方法，特別適用于樣本歸屬不清楚的情況。它所基于的主要思想是在多維空間中，同類化合物應(yīng)彼此靠得近些，彼此間的距離小些；不同類化合物應(yīng)彼此靠得遠些，彼此間的距離大些。聚類分析即為如何使相似的樣本“聚”在一起，從而達到分類的目的。聚類分析為無監(jiān)督方法，其中用得最多的為系統(tǒng)聚類法（hierarchical clustering）. 系統(tǒng)聚類的基本思想是首先定義樣本之間和類與類之間的距離。在各自成類樣本中，將距離最近的兩類合并，重新計算新類與其它類的距離，并按最小距離歸類，重復(fù)此過程，每次減少一類，知道所有的樣本成為一類

18、為止。其聚類過程用圖表示，稱為聚類圖。（1）最短距離法定義類Gi 與Gj之間的距離為klGxGxijdminDjlik 其中dkl是樣本xk 與xl的距離。也就是說兩類之間的距離等于兩類中最近樣品之間的距離。 設(shè)某一步將類Gp和Gq合并成Gr ，則類與距離的遞推公式為：iqipirddD,min（2）最長距離法 在此種方法中類與類之間的距離等于兩類中最遠樣本的距離，即klGxGxijdDjlik max顯然，最長距離法的遞推公式是：iqipirddD,max（3）中間距離法 在中間距離法中，類與類之間的距離既不采用兩類之間最近的距離，也不采用最遠距離，而是采用最遠和最近之間的距離。 如果在某一

19、步將Gp類Gq和合并為Gr ，任一類Gi與Gr的距離的取法可由如下三角形說明。Gi Gi Gq Gp Diq Dip Dpq 由初等幾何知道，該三角形的中線為：21222412121）（中線pqiqipDDD04121212222，pqiqipirDDDD當= - 時，就是上述三角形中線。上式即為中間距離法的遞推公式。（4）重心法 該方法定義兩類之間的距離為對應(yīng)這兩類重心之間的距離。對樣本來說，每一類的重心即為該類樣本的均值。 設(shè)某一步將Gp類Gq和合并為Gr ，它們各含有np, nq, nr (nr =np+nq) 個樣本，則此方法的遞推公式為：22222pqrqpiqrqiprpirDnn

20、nDnnDnnD（5）類平均法 在該類方法中，類Gp，Gq之間的距離表示為： PIqjGxGxijqppqdnnD221 其中，為類Gp，Gq中的樣本數(shù)。就是說類之間的平方距離等于各元素兩兩之間的平方距離的平均。其遞推公式為：222iqrqiprpirDnnDnnD（6）可變類平均法類平均法的距離遞推公式中對于Gp和Gq之間的距離沒有反映進去，可變類平均法將之改進為：2222)1 ()1 (pqiqrqiprpirDDnnDnnD其中，可變，1。（7）可變法 此種方法的遞推公式為：22221pqiqipirDDDD其中，可變，1。（8）方差平方和 該方法由Ward提出，故文獻中常稱為Ward法。該方法基本思想是方差分析。例如：G1=x1, x2=1, 2 G2=x3, x4=4.5, 6 G3=x5=8 G1與G2合并，兩類中所有元素的均值為：那么G1與G2方差平方和為：(1-3.667)2+(2-3.667)2+(4.5-3.667)2+(6-3.667)2+(8-3.667)2=15.687若將G1與G3合并，其方差平方和為28.667；若將G2與G3合并，其方差平方和為6.117在這三中分類中以G2與G3合并方差平方和最小，故為最佳方案。37536542141.).(x 一般來講，該種方法是將某一步中G1, G2, ,Gk類合并成k-1類，而由此