模式識別第2,3章聚類分析報告

1、第二章 聚類分析2.1 聚類分析的相關(guān)概念定義 對一批沒有標(biāo)出類別的模式樣本集，按照樣本之間的相似程度分類，相似的歸為一類，不相似的歸為另一類，這種分類稱為聚類分析，也稱為無監(jiān)督分類。模式相似/分類的依據(jù) 把整個模式樣本集的特征向量看成是分布在特征空間中的一些點，點與點之間的距離即可作為模式相似性的測量依據(jù)。聚類分析是按不同對象之間的差異，根據(jù)距離函數(shù)的規(guī)律（大?。┻M行模式分類的。聚類分析的有效性 聚類分析方法是否有效，與模式特征向量的分布形式有很大關(guān)系。若向量點的分布是一群一群的，同一群樣本密集（距離很近），不同群樣本距離很遠，則很容易聚類；若樣本集的向量分布聚成一團，不同群的樣本混在一起，

2、則很難分類；對具體對象做聚類分析的關(guān)鍵是選取合適的特征。特征選取得好，向量分布容易區(qū)分，選取得不好，向量分布很難分開。兩類模式分類的實例：一攤黑白圍棋子 選顏色作為特征進行分類，用“1”代表白，“0”代表黑，則很容易分類；選大小作為特征進行分類，則白子和黑子的特征相同，不能分類（把白子和黑子分開）。特征選擇的維數(shù)在特征選擇中往往會選擇一些多余的特征，它增加了維數(shù)，從而增加了聚類分析的復(fù)雜度，但對模式分類卻沒有提供多少有用的信息。在這種情況下，需要去掉相關(guān)程度過高的特征（進行降維處理）。降維方法設(shè)有N個樣本，它們的特征維數(shù)是n，則有n*n維的相關(guān)矩陣R = rij nxn 其中，rij是第i維與

3、第j維特征之間的相關(guān)系數(shù)： 這里：ii和jj分別是第i個和第j個分量的標(biāo)準(zhǔn)差，ij是第i個和第j個分量的協(xié)方差。分析：（1）根據(jù)相關(guān)系數(shù)的性質(zhì)：（利用柯西不等式證明）（2）rij=0：表示兩個分量完全不相關(guān)（3）rij=1：表示兩個分量完全相關(guān)結(jié)論：若rij->1，則表明第i維特征與第j維特征所反映的特征規(guī)律接近，因此可以略去其中的一個特征，或?qū)⑺鼈兒喜橐粋€特征，從而使維數(shù)降低一維。模式對象特征測量的數(shù)字化計算機只能處理離散的數(shù)值，因此根據(jù)識別對象的不同，要進行不同的數(shù)據(jù)化處理。連續(xù)量的量化：用連續(xù)量來度量的特性，如長度、重量、面積等等，僅需取其量化值；量級的數(shù)量化：度量時不需要詳盡的

4、數(shù)值，而是相應(yīng)地劃分成一些有次序的量化等級的值。l 病人的病程 0 代表病程 <= 1個月 1 代表1個月< 病程 <= 6個月2 代表6個月< 病程 <= 12個月 3 代表病程 > 12個月名義尺度：指定性的指標(biāo)，即特征度量時沒有數(shù)量關(guān)系，也沒有明顯的次序關(guān)系，如黑色和白色的關(guān)系，男性和女性的關(guān)系等，都可將它們分別用“0”和“1”來表示。超過2個狀態(tài)時，可用多個數(shù)值表示。2.2 模式相似性的測度和聚類準(zhǔn)則2.2.1 相似性測度目的：為了能將模式集劃分成不同的類別，必須定義一種相似性的測度，來度量同一類樣本間的類似性和不屬于同一類樣本間的差異性。歐氏距離設(shè)

5、x和z為兩個模式樣本，其歐氏距離定義為：D = | x - z | 例：x = (x1, x2)，z = (z1, z2)，則 顯然，模式x和z之間的距離越小，它們越相似。歐氏距離的概念和習(xí)慣上距離的概念是一致的。馬氏距離設(shè)x是模式向量，m是均值向量，C為模式總體的協(xié)方差矩陣，則馬氏距離的表達式： 特點：排除了模式樣本之間的相關(guān)性問題：協(xié)方差矩陣在實際應(yīng)用中難以計算。一般化的明氏距離模式樣本向量xi和xj之間的明氏距離表示為：其中xik和xjk分別表示xi和xj的第k各分量。顯然，當(dāng)m=2時，明氏距離即為歐氏距離。特例：當(dāng)m=1時，亦稱為街坊距離。角度相似性函數(shù)表達式：，它表示模式向量x和z之

6、間夾角的余弦，也稱為x的單位向量與z的單位向量之間的點積。特點：反映了幾何上相似形的特征，對于坐標(biāo)系的旋轉(zhuǎn)、放大和縮小等變化是不變的。當(dāng)特征的取值僅為(0,1)兩個值時的特例特例：當(dāng)特征的取值僅為(0, 1)兩個值時，夾角余弦度量具有特別的含義，即當(dāng)模式的第i個分量為1時，認為該模式具有第i個特征；當(dāng)模式的第i個分量為0時，認為該模式無此特征。這時，xTz的值就等于x和z這兩個向量共同具有的特征數(shù)目。同時，= x中具有的特征數(shù)目和z中具有的特征數(shù)目的幾何平均因此，在特征取值為0和1的二值情況下，S(x, z)等于x和z中具有的共同特征數(shù)目的相似性測度。2.2.2 聚類準(zhǔn)則有了模式的相似性測度，

7、還需要一種基于數(shù)值的聚類準(zhǔn)則，能將相似的模式樣本分在同一類，相異的模式樣本分在不同的類。試探方法憑直觀感覺或經(jīng)驗，針對實際問題定義一種相似性測度的閾值，然后按最近鄰規(guī)則指定某些模式樣本屬于某一個聚類類別。例如對歐氏距離，它反映了樣本間的近鄰性，但將一個樣本分到不同類別中的哪一個時，還必須規(guī)定一個距離測度的閾值作為聚類的判別準(zhǔn)則。聚類準(zhǔn)則函數(shù)法依據(jù)：由于聚類是將樣本進行分類以使類別間可分離性為最大，因此聚類準(zhǔn)則應(yīng)是反映類別間相似性或分離性的函數(shù)；由于類別是由一個個樣本組成的，因此一般來說類別的可分離性和樣本的可分離性是直接相關(guān)的；可以定義聚類準(zhǔn)則函數(shù)為模式樣本集x和模式類別Sj, j=1,2,c

8、的函數(shù)，從而使聚類分析轉(zhuǎn)化為尋找準(zhǔn)則函數(shù)極值的最優(yōu)化問題。一種聚類準(zhǔn)則函數(shù)J的定義其中，c為聚類類別的數(shù)目，Sj為第j個類別的樣本集合，為屬于Sj集合的樣本均值向量，Nj為Sj中的樣本數(shù)目。這里，以均值向量mj為Sj中樣本的代表。J代表了屬于c個聚類類別的全部模式樣本與其相應(yīng)類別模式均值之間的誤差平方和。對于不同的聚類形式，J值是不同的。目的：求取使J值達到最小的聚類形式。2.3 基于試探的聚類搜索算法2.3.1 按最近鄰規(guī)則的簡單試探法算法 給定N個待分類的模式樣本x1, x2, , xN，要求按距離閾值T，將它們分類到聚類中心z1, z2, 。第一步：任取一樣本xi作為一個聚類中心的初始值

9、，例如令z1 = x1，計算D21 = | x2 - z1 |，若D21 > T，則確定一個新的聚類中心z2 = x2，否則x2屬于以z1為中心的聚類；第二步：假設(shè)已有聚類中心z1、z2，計算 D31 = | x3 - z1 |，D32 = | x3 - z2 |，若D31 > T且D32 > T，則得一個新的聚類中心z3 = x3，否則x3屬于離z1和z2中的最近者······如此重復(fù)下去，直至將N個模式樣本分類完畢。討論 這種方法的優(yōu)點：計算簡單，若模式樣本的集合分布的先驗知識已知，則可通過選取正確的閾值和起始點

10、，以及確定樣本的選取次序等獲得較好的聚類結(jié)果。在實際中，對于高維模式樣本很難獲得準(zhǔn)確的先驗知識，因此只能選用不同的閾值和起始點來試探，所以這種方法在很大程度上依賴于以下因素：第一個聚類中心的位置；待分類模式樣本的排列次序；距離閾值T的大??；樣本分布的幾何性質(zhì)。2.3.2 最大最小距離算法基本思想：以試探類間歐氏距離為最大作為預(yù)選出聚類中心的條件。10個模式樣本點：x1(0 0), x2(3 8), x3(2 2), x4(1 1), x5(5 3), x6(4 8), x7(6 3), x8(5 4), x9(6 4), x10(7 5)第一步：選任意一個模式樣本作為第一個聚類中心，如z1 =

11、 x1；第二步：選距離z1最遠的樣本作為第二個聚類中心。經(jīng)計算，| x6 - z1 |最大，所以z2 = x6第三步：逐個計算各模式樣本xi, i = 1,2,N與 z1, z2之間的距離，即Di1 = | xi - z1 |，Di2 = | xi z2 |并選出其中的最小距離min(Di1, Di2)，i = 1,2,N第四步：在所有模式樣本的最小值中選出最大距離，若該最大值達到|z1 - z2 |的一定比例以上，則相應(yīng)的樣本點取為第三個聚類中心z3，即若maxmin(Di1, Di2), i = 1,2,N >|z1 - z2 |，則z3 = xi否則，若找不到適合要求的樣本作為新的

12、聚類中心，則找聚類中心的過程結(jié)束。這里，可用試探法取一固定分數(shù)，如1/2。在此例中，當(dāng)i=7時，符合上述條件，故z3 = x7第五步： 若有z3存在，則計算maxmin(Di1, Di2, Di3), i = 1,2,N。若該值超過|z1 - z2 |的一定比例，則存在z4，否則找聚類中心的過程結(jié)束。在此例中，無z4滿足條件。第六步：將模式樣本xi, i = 1,2,N按最近距離分到最近的聚類中心：z1 = x1：x1, x3, x4為第一類z2 = x6：x2, x6為第二類z3 = x7：x5, x7, x8, x9, x10為第三類，最后，還可在每一類中計算個樣本的均值，得到更具代表性的

13、聚類中心。2.4 系統(tǒng)聚類法基本思想：將模式樣本按距離準(zhǔn)則逐步分類，類別由多到少，直到獲得合適的分類要求為止。算法：第一步：設(shè)初始模式樣本共有N個，每個樣本自成一類，即建立N類，。計算各類之間的距離（初始時即為各樣本間的距離），得到一個N*N維的距離矩陣D(0)。這里，標(biāo)號(0)表示聚類開始運算前的狀態(tài)。第二步：假設(shè)前一步聚類運算中已求得距離矩陣D(n)，n為逐次聚類合并的次數(shù)，則求D(n)中的最小元素。如果它是Gi(n)和Gj(n)兩類之間的距離，則將Gi(n)和Gj(n)兩類合并為一類，由此建立新的分類：。第三步：計算合并后新類別之間的距離，得D(n+1)。計算與其它沒有發(fā)生合并的之間的距

14、離，可采用多種不同的距離計算準(zhǔn)則進行計算。第四步：返回第二步，重復(fù)計算及合并，直到得到滿意的分類結(jié)果。（如：達到所需的聚類數(shù)目，或D(n)中的最小分量超過給定閾值D等。）距離準(zhǔn)則函數(shù)進行聚類合并的一個關(guān)鍵就是每次迭代中形成的聚類之間以及它們和樣本之間距離的計算，采用不同的距離函數(shù)會得到不同的計算結(jié)果。主要的距離計算準(zhǔn)則：聚類準(zhǔn)則函數(shù)1.最短距離法：設(shè)H和K是兩個聚類，則兩類間的最短距離定義為：其中，du,v表示H類中的樣本xu和K類中的樣本xv之間的距離，DH,K表示H類中的所有樣本和K類中的所有樣本之間的最小距離。遞推運算：假若K類是由I和J兩類合并而成，則2.最長距離法：設(shè)H和K是兩個聚類

15、，則兩類間的最長距離定義為：其中du,v的含義與上面相同。遞推運算：假若K類是由I和J兩類合并而成，則3.中間距離法：設(shè)K類是由I和J兩類合并而成，則H和K類之間的距離為：它介于最長距離和最短距離之間。4.重心法：假設(shè)I類中有nI個樣本，J類中有nJ個樣本，則I和J合并后共有nI+nJ個樣本。用nI/(nI+nJ)和nJ/(nI+nJ)代替中間距離法中的系數(shù)，得到重心法的類間距離計算公式：5.類平均距離法：若采用樣本間所有距離的平均距離，則有：遞推運算公式：舉例設(shè)有6個五維模式樣本如下，按最小距離準(zhǔn)則進行聚類分析：x1: 0, 3, 1, 2, 0；x2: 1, 3, 0, 1, 0；x3:

16、3, 3, 0, 0, 1；x4: 1, 1, 0, 2, 0；x5: 3, 2, 1, 2, 1；x6: 4, 1, 1, 1, 0作業(yè)1.畫出給定迭代次數(shù)為n的系統(tǒng)聚類法的算法流程框圖2.對如下5個6維模式樣本，用最小聚類準(zhǔn)則進行系統(tǒng)聚類分析：x1: 0, 1, 3, 1, 3, 4；x2: 3, 3, 3, 1, 2, 1；x3: 1, 0, 0, 0, 1, 1；x4: 2, 1, 0, 2, 2, 1；x5: 0, 0, 1, 0, 1, 02.5 動態(tài)聚類法基本思想：首先選擇若干個樣本點作為聚類中心，再按某種聚類準(zhǔn)則（通常采用最小距離準(zhǔn)則）使樣本點向各中心聚集，從而得到初始聚類；然

17、后判斷初始分類是否合理，若不合理，則修改分類；如此反復(fù)進行修改聚類的迭代算法，直至合理為止。K-均值算法思想：基于使聚類性能指標(biāo)最小化，所用的聚類準(zhǔn)則函數(shù)是聚類集中每一個樣本點到該類中心的距離平方之和，并使其最小化。第一步：選K個初始聚類中心，z1(1)，z2(1)，zK(1)，其中括號的序號為尋找聚類中心的迭代運算的次序號。聚類中心的向量值可任意設(shè)定，例如可選開始的K個模式樣本的向量值作為初始聚類中心。第二步：逐個將需分類的模式樣本x按最小距離準(zhǔn)則分配給K個聚類中心中的某一個zj(1)。假設(shè)i=j時，則，其中k為迭代運算的次序號，第一次迭代k=1，Sj表示第j個聚類，其聚類中心為zj。第三步

18、：計算各個聚類中心的新的向量值，zj(k+1)，j=1,2,K。求各聚類域中所包含樣本的均值向量：其中Nj為第j個聚類域Sj中所包含的樣本個數(shù)。以均值向量作為新的聚類中心，可使如下聚類準(zhǔn)則函數(shù)最?。?，在這一步中要分別計算K個聚類中的樣本均值向量，所以稱之為K-均值算法。第四步：若，j=1,2,K，則返回第二步，將模式樣本逐個重新分類，重復(fù)迭代運算；若，j=1,2,K，則算法收斂，計算結(jié)束。討論K-均值算法的結(jié)果受如下選擇的影響：所選聚類的數(shù)目；聚類中心的初始分布；模式樣本的幾何性質(zhì)；讀入次序；在實際應(yīng)用中，需要試探不同的K值和選擇不同的聚類中心的起始值。如果模式樣本可以形成若干個相距較遠的孤立

19、的區(qū)域分布，一般都能得到較好的收斂效果。K-均值算法比較適合于分類數(shù)目已知的情況。作業(yè)/練習(xí)（選k=2,z1(1)=x1,z2(1)=x10,用K-均值算法進行聚類分析）ISODATA算法（迭代自組織數(shù)據(jù)分析算法）與K-均值算法的比較：K-均值算法通常適合于分類數(shù)目已知的聚類，而ISODATA算法則更加靈活；從算法角度看， ISODATA算法與K-均值算法相似，聚類中心都是通過樣本均值的迭代運算來決定的；ISODATA算法加入了一些試探步驟，并且可以結(jié)合成人機交互的結(jié)構(gòu)，使其能利用中間結(jié)果所取得的經(jīng)驗更好地進行分類?；静襟E和思路（1）選擇某些初始值?？蛇x不同的參數(shù)指標(biāo)，也可在迭代過程中人為修

20、改，以將N個模式樣本按指標(biāo)分配到各個聚類中心中去。（2）計算各類中諸樣本的距離指標(biāo)函數(shù)。（3）（5）按給定的要求，將前一次獲得的聚類集進行分裂和合并處理（4）為分裂處理，（5）為合并處理），從而獲得新的聚類中心。（6）重新進行迭代運算，計算各項指標(biāo)，判斷聚類結(jié)果是否符合要求。經(jīng)過多次迭代后，若結(jié)果收斂，則運算結(jié)束。算法：第一步：輸入N個模式樣本xi, i = 1, 2, , N預(yù)選Nc個初始聚類中心，它可以不等于所要求的聚類中心的數(shù)目，其初始位置可以從樣本中任意選取。預(yù)選：K = 預(yù)期的聚類中心數(shù)目；N = 每一聚類域中最少的樣本數(shù)目，若少于此數(shù)即不作為一個獨立的聚類；S = 一個聚類域中樣本

21、距離分布的標(biāo)準(zhǔn)差；c = 兩個聚類中心間的最小距離，若小于此數(shù)，兩個聚類需進行合并；L = 在一次迭代運算中可以合并的聚類中心的最多對數(shù)；I = 迭代運算的次數(shù)。第二步：將N個模式樣本分給最近的聚類Sj，假若，即|x-zj|的距離最小，則。第三步：如果Sj中的樣本數(shù)目Sj<N，則取消該樣本子集，此時Nc減去1。（以上各步對應(yīng)基本步驟（1）第四步：修正各聚類中心第五步：計算各聚類域Sj中模式樣本與各聚類中心間的平均距離第六步：計算全部模式樣本和其對應(yīng)聚類中心的總平均距離（以上各步對應(yīng)基本步驟（2）第七步：判別分裂、合并及迭代運算1.若迭代運算次數(shù)已達到I次，即最后一次迭代，則置c =0，轉(zhuǎn)

22、至第十一步。2.若，即聚類中心的數(shù)目小于或等于規(guī)定值的一半，則轉(zhuǎn)至第八步，對已有聚類進行分裂處理。3.若迭代運算的次數(shù)是偶數(shù)次，或，不進行分裂處理，轉(zhuǎn)至第十一步；否則（即既不是偶數(shù)次迭代，又不滿足），轉(zhuǎn)至第八步，進行分裂處理。（以上對應(yīng)基本步驟（3）第八步：計算每個聚類中樣本距離的標(biāo)準(zhǔn)差向量其中向量的各個分量為式中， i = 1, 2, , n為樣本特征向量的維數(shù)，j = 1, 2, , Nc為聚類數(shù)，Nj為Sj中的樣本個數(shù)。第九步：求每一標(biāo)準(zhǔn)差向量j, j = 1, 2, , Nc中的最大分量，以jmax, j = 1, 2, , Nc代表。第十步：在任一最大分量集jmax, j = 1,

23、2, , Nc中，若有jmax>S ，同時又滿足如下兩個條件之一：1.和Nj > 2(N + 1)，即Sj中樣本總數(shù)超過規(guī)定值一倍以上，2.，則將zj 分裂為兩個新的聚類中心和，且Nc加1。 中對應(yīng)于jmax的分量加上kjmax，其中；中對應(yīng)于jmax的分量減去kjmax。如果本步驟完成了分裂運算，則轉(zhuǎn)至第二步，否則繼續(xù)。（以上對應(yīng)基本步驟（4）進行分裂處理）第十一步：計算全部聚類中心的距離Dij = | zi - zj |，i = 1, 2, , Nc-1 ，j =i+1, , Nc。第十二步：比較Dij 與c 的值，將Dij <c 的值按最小距離次序遞增排列，即式中，。第

24、十三步：將距離為的兩個聚類中心和合并，得新的中心為：，k = 1, 2, , L式中，被合并的兩個聚類中心向量分別以其聚類域的樣本數(shù)加權(quán)，使為真正的平均向量。（以上對應(yīng)基本步驟（5）進行合并處理）第十四步：如果是最后一次迭代運算（即第I次），則算法結(jié)束；否則，若需要操作者改變輸入?yún)?shù)，轉(zhuǎn)至第一步；若輸入?yún)?shù)不變，轉(zhuǎn)至第二步。在本步運算中，迭代運算的次數(shù)每次應(yīng)加1。算法結(jié)束2.6 聚類結(jié)果的評價迅速評價聚類結(jié)果，在上述迭代運算中是很重要的，特別是具有高維特征向量的模式，不能直接看清聚類效果，因此，可考慮用以下幾個指標(biāo)來評價聚類效果：聚類中心之間的距離；距離值大，通常可考慮分為不同類；聚類域中的樣

25、本數(shù)目；樣本數(shù)目少且聚類中心距離遠，可考慮是否為噪聲；聚類域樣本的距離方差；方差過大的樣本可考慮是否屬于這一類討論：模式聚類目前還沒有一種通用的放之四海而皆準(zhǔn)的準(zhǔn)則，往往需要根據(jù)實際應(yīng)用來選擇合適的方法。作業(yè)1.畫出ISODATA算法的流程框圖2.試用ISODATA算法對如下模式分布進行聚類分析：x1(0, 0), x2(3,8), x3(2,2), x4(1,1), x5(5,3), x6(4,8), x7(6,3), x8(5,4),x9(6,4), x10(7,5)計算機編程編寫ISODATA聚類算法程序，對如下數(shù)據(jù)進行聚類分析：x1(0, 0), x2(3,8), x3(2,2), x

26、4(1,1), x5(5,3), x6(4,8), x7(6,3), x8(5,4), x9(6,4), x10(7,5)第三章 判別函數(shù)3.1 線性判別函數(shù)3.1.1 用判別函數(shù)分類的概念模式識別系統(tǒng)的主要作用：判別各個模式所屬的類別；對一個兩類問題的判別，就是將模式x劃分成1和2兩類。l 描述：兩類問題的判別函數(shù)（以二維模式樣本為例）若x是二維模式樣本x = (x1 x2)T，用x1和x2作為坐標(biāo)分量，得到模式的平面圖：這時，若這些分屬于1和2兩類的模式可用一個直線方程d(x)=0來劃分d(x) = w1x1 + w2x2 + w3 = 0其中x1、x2為坐標(biāo)變量，w1、w2、w3為參數(shù)方

27、程，則將一個不知類別的模式代入d(x)，有 若d(x) > 0，則若d(x) < 0，則此時，d(x)=0稱為判別函數(shù)。用判別函數(shù)進行模式分類依賴的兩個因素（1）判別函數(shù)的幾何性質(zhì)：線性的和非線性的函數(shù)。線性的是一條直線；非線性的可以是曲線、折線等；線性判別函數(shù)建立起來比較簡單（實際應(yīng)用較多）；非線性判別函數(shù)建立起來比較復(fù)雜。（2）判別函數(shù)的系數(shù)：判別函數(shù)的形式確定后，主要就是確定判別函數(shù)的系數(shù)問題。只要被研究的模式是可分的，就能用給定的模式樣本集來確定判別函數(shù)的系數(shù)。3.1.2 線性判別函數(shù)n維線性判別函數(shù)的一般形式：，其中w0 = (w1, w2, , wn)T稱為權(quán)向量（或參

28、數(shù)向量）, x = (x1, x2, , xn)T。d(x)也可表示為：d(x) = wTx，其中，x = (x1, x2, , xn, 1)T稱為增廣模式向量，w = (w1, w2, , wn+1)T稱為增廣權(quán)向量。分類問題兩類情況：判別函數(shù)d(x)：多類情況：設(shè)模式可分成1, 2, M共M類，則有三種劃分方法多類情況1用線性判別函數(shù)將屬于i類的模式與不屬于i類的模式分開，其判別函數(shù)為：i = 1, 2, , M，這種情況稱為兩分法，即把M類多類問題分成M個兩類問題，因此共有M個判別函數(shù)，對應(yīng)的判別函數(shù)的權(quán)向量為wi, i = 1, 2, , M。圖例：對一個三類情況，每一類模式可用一個簡

29、單的直線判別界面將它與其它類模式分開。例如對的模式，應(yīng)同時滿足：d1(x)>0，d2(x)<0，d3(x)<0，不確定區(qū)域：若對某一模式區(qū)域，di(x)>0的條件超過一個，或全部di(x)<0，i = 1, 2, , M，則分類失敗，這種區(qū)域稱為不確定區(qū)域(IR)。多類情況2采用每對劃分，即i/j兩分法，此時一個判別界面只能分開兩種類別，但不能把它與其余所有的界面分開。其判別函數(shù)為：若dij(x)>0，則重要性質(zhì)：dij = -dji圖例：對一個三類情況，d12(x)=0僅能分開1和2類，不能分開1和3類。要分開M類模式，共需M(M-1)/2個判別函數(shù)。不確

30、定區(qū)域：若所有dij(x)，找不到，dij(x)>0的情況。多類情況3這是沒有不確定區(qū)域的i/j兩分法。假若多類情況2中的dij可分解成：dij(x) = di(x) - dj(x) = (wi wj)Tx，則dij(x)>0相當(dāng)于di(x)>dj(x)，這時不存在不確定區(qū)域。此時，對M類情況應(yīng)有M個判別函數(shù)：即di(x)>dj(x)，i, j = 1,2,M，則，也可寫成，若di(x)=maxdk(x), k=1,2,M，則。該分類的特點是把M類情況分成M-1個兩類問題。小結(jié)：線性可分：模式分類若可用任一個線性函數(shù)來劃分，則這些模式就稱為線性可分的，否則就是非線性可分

31、的。一旦線性函數(shù)的系數(shù)wk被確定，這些函數(shù)就可用作模式分類的基礎(chǔ)。多類情況1和多類情況2的比較對于M類模式的分類，多類情況1需要M個判別函數(shù)，而多類情況2需要M*(M-1)/2個判別函數(shù)，當(dāng)M較大時，后者需要更多的判別式（這是多類情況2的一個缺點）。采用多類情況1時，每一個判別函數(shù)都要把一種類別的模式與其余M-1種類別的模式分開，而不是將一種類別的模式僅于另一種類別的模式分開。由于一種模式的分布要比M-1種模式的分布更為聚集，因此多類情況2對模式是線性可分的可能性比多類情況1更大一些（這是多類情況2的一個優(yōu)點）。作業(yè)（1）在一個10類的模式識別問題中，有3類單獨滿足多類情況1，其余的類別滿足多

32、類情況2。問該模式識別問題所需判別函數(shù)的最少數(shù)目是多少？作業(yè)（2）一個三類問題，其判別函數(shù)如下：d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-11.設(shè)這些函數(shù)是在多類情況1條件下確定的，繪出其判別界面和每一個模式類別的區(qū)域。2.設(shè)為多類情況2，并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。繪出其判別界面和多類情況2的區(qū)域。3.設(shè)d1(x), d2(x)和d3(x)是在多類情況3的條件下確定的，繪出其判別界面和每類的區(qū)域。3.2 廣義線性判別函數(shù)出發(fā)點線性判別函數(shù)簡單，容易實現(xiàn)；非線性判別函數(shù)復(fù)雜，不容易實現(xiàn)；若能將非

33、線性判別函數(shù)轉(zhuǎn)換為線性判別函數(shù)，則有利于模式分類的實現(xiàn)?；舅枷朐O(shè)有一個訓(xùn)練用的模式集x，在模式空間x中線性不可分，但在模式空間x*中線性可分，其中x*的各個分量是x的單值實函數(shù)，x*的維數(shù)k高于x的維數(shù)n，即若取x* = (f1(x), f2(x), ., fk(x), k>n,則分類界面在x*中是線性的，在x中是非線性的，此時只要將模式x進行非線性變換，使之變換后得到維數(shù)更高的模式x*，就可以用線性判別函數(shù)來進行分類。描述 一個非線性判別函數(shù)可如下表示：其中fi(x), i = 1,2,k是模式x的單值實函數(shù)。若定義成廣義形式：x* = (f1(x), f2(x), , fk(x),

34、 1)T此時有：d(x*) = wTx*，其中w = (w1, w2, , wk, wk+1)T,該式表明，非線性判別函數(shù)已被變換成廣義線性，因此只討論線性判別函數(shù)不會失去一般性意義。廣義線性判別函數(shù)的意義線性的判別函數(shù)取fi(x)為一次函數(shù)，例如xi，則變換后的模式x*=x，x*的維數(shù)k為x的維數(shù)n，此時廣義線性化后的判別式仍為：d(x) = wTx + wn+1,fi(x)選用二次多項式函數(shù)1.x是二維的情況，即x =(x1 x2) T。若原判別函數(shù)為：,要線性化為d(x*) = wTx*，須定義：,此時，只要把模式空間x*中的分量定義成x的單值實函數(shù)，x*即變成線性可分。此時x*的維數(shù)（

35、這里為6）大于x的維數(shù)（這里為2）。2.x是n維的情況，此時原判別函數(shù)設(shè)為：,式中各項的組成應(yīng)包含x的各個分量的二次項、一次項和常數(shù)項，其中平方項n個，二次項n(n-1)/2個，一次項n個，常數(shù)項一個，其總項數(shù)為：n + n(n-1)/2 + n + 1 = (n+1)(n+2)/2 > n顯然，對于d(x*) = wTx*，x*的維數(shù)大于x的維數(shù)，w分量的數(shù)目也與x*的維數(shù)相應(yīng)。x*的各分量的一般化形式為：說明:d(x)的項數(shù)隨r和n的增加會迅速增大，即使原來模式x的維數(shù)不高，若采用次數(shù)r較高的多項式來變換，也會使變換后的模式x*的維數(shù)很高，給分類帶來很大困難。實際情況可只取r=2，或

36、只選多項式的一部分，例如r=2時只取二次項，略去一次項，以減少x*的維數(shù)。作業(yè)兩類模式，每類包括5個3維不同的模式，且良好分布。如果它們是線性可分的，問權(quán)向量至少需要幾個系數(shù)分量？假如要建立二次的多項式判別函數(shù)，又至少需要幾個系數(shù)分量？（設(shè)模式的良好分布不因模式變化而改變。）3.3 分段線性判別函數(shù)出發(fā)點:線性判別函數(shù)在進行分類決策時是最簡單有效的，但在實際應(yīng)用中，常常會出現(xiàn)不能用線性判別函數(shù)直接進行分類的情況。采用廣義線性判別函數(shù)的概念，可以通過增加維數(shù)來得到線性判別，但維數(shù)的大量增加會使在低維空間里在解析和計算上行得通的方法在高維空間遇到困難，增加計算的復(fù)雜性。引入分段線性判別函數(shù)的判別過

37、程，它比一般的線性判別函數(shù)的錯誤率小，但又比非線性判別函數(shù)簡單。分段線性判別函數(shù)的設(shè)計:采用最小距離分類的方法設(shè)1和2為兩個模式類1和2的聚類中心，定義決策規(guī)則：這時的決策面是兩類期望連線的垂直平分面，這樣的分類器稱為最小距離分類器。3.4 模式空間和權(quán)空間分類描述: 設(shè)有判別函數(shù)：d(x)=wTx，其中x=(x1 x2xn 1)T，w=(w1 w2wn wn+1)T, ,判別界面為：wTx=0 ,對兩類問題，1類有模式x1 x2，2類有模式x3 x4 ，則應(yīng)滿足如下條件：若將屬于2類的模式都乘以(-1)，則上式可寫成：因此，若權(quán)向量能滿足上述四個條件，則wTx=0為所給模式集的判別界面。模式

38、空間:對一個線性方程w1x1+w2x2+w3x3=0，它在三維空間(x1 x2 x3)中是一個平面方程式，w=(w1 w2 w3)T是方程的系數(shù)。把w向量作為該平面的法線向量，則該線性方程決定的平面通過原點且與w垂直。若x是二維的增廣向量，此時x3=1，則在非增廣的模式空間中即為x1, x2 二維坐標(biāo)，判別函數(shù)是下列聯(lián)立方程的解 w1x1+w2x2+w3=0,x3=1即為這兩個平面相交的直線AB,此時，w =(w1 w2)T為非增廣的權(quán)向量，它與直線AB垂直；AB將平面分為正、負兩側(cè)，w離開直線的一側(cè)為正， w射向直線的一側(cè)為負。增廣向量決定的平面;非增廣向量決定的直線權(quán)空間若將方程x1w1+

39、x2w2+w3=0繪在權(quán)向量w=(w1 w2 w3)T的三維空間中，則x=(x1 x2 1)T為方程的系數(shù)。若以x向量作為法線向量，則該線性方程所決定的平面為通過原點且與法線向量垂直的平面，它同樣將權(quán)空間劃分為正、負兩邊。在系數(shù)x不變的條件下，若w值落在法線向量離開平面的一邊，則wTx>0，若w值落在法線向量射向平面的一邊，則wTx <0。權(quán)空間中判別界面的平面示意圖3.5 Fisher線性判別出發(fā)點:應(yīng)用統(tǒng)計方法解決模式識別問題時，一再碰到的問題之一就是維數(shù)問題。在低維空間里解析上或計算上行得通的方法，在高維空間里往往行不通。因此，降低維數(shù)有時就會成為處理實際問題的關(guān)鍵。問題描述

40、:考慮把d維空間的樣本投影到一條直線上,形成一維空間，即把維數(shù)壓縮到一維。然而，即使樣本在d維空間里形成若干緊湊的互相分得開的集群，當(dāng)把它們投影到一條直線上時，也可能會是幾類樣本混在一起而變得無法識別。但是，在一般情況下，總可以找到某個方向，使在這個方向的直線上，樣本的投影能分得開。問題：如何根據(jù)實際情況找到一條最好的、最易于分類的投影線，這就是Fisher判別方法所要解決的基本問題。從d維空間到一維空間的一般數(shù)學(xué)變換方法:假設(shè)有一集合包含N個d維樣本x1, x2, , xN，其中N1個屬于1類的樣本記為子集1， N2個屬于2類的樣本記為子集2 。若對xn的分量做線性組合可得標(biāo)量：yn = w

41、Txn, n=1,2,N,這樣便得到N個一維樣本yn組成的集合，并可分為兩個子集1和2 。實際上，w的值是無關(guān)緊要的，它僅是yn乘上一個比例因子，重要的是選擇w的方向。w的方向不同，將使樣本投影后的可分離程度不同，從而直接影響的分類效果。因此，上述尋找最佳投影方向的問題，在數(shù)學(xué)上就是尋找最好的變換向量w*的問題。Fisher準(zhǔn)則函數(shù)的定義Fisher準(zhǔn)則函數(shù)定義為：其中，是兩類均值之差，是樣本類離散度。顯然，應(yīng)該使JF(w)的分子盡可能大而分母盡可能小，即應(yīng)尋找使JF(w)盡可能大的w作為投影方向。但上式中并不顯含w，因此須設(shè)法將JF(w)變成w的顯函數(shù)。由各類樣本的均值可推出：，這樣，F(xiàn)is

42、her準(zhǔn)則函數(shù)JF(w)的分子可寫成：現(xiàn)在再來考察JF(w)的分母與w的關(guān)系：因此，將上述各式代入JF(w)，可得：其中Sb為樣本類間離散度矩陣，Sw為總樣本類離散度矩陣。幾個必要的基本參量:1在d維X空間:1)各類樣本的均值向量mi:2)樣本類離散度矩陣Si和總樣本類離散度矩陣Sw其中Sw是對稱半正定矩陣，而且當(dāng)N>d時通常是非奇異的。3)樣本類間離散度矩陣Sb Sb是對稱半正定矩陣。1.在一維Y空間:1)各類樣本的均值2)樣本類離散度和總樣本類離散度最佳變換向量w*的求取為求使取極大值時的w*，可以采用Lagrange乘數(shù)法求解。令分母等于非零常數(shù)，即：,定義Lagrange函數(shù)為：

43、其中為Lagrange乘子。將上式對w求偏導(dǎo)數(shù)，可得：,令偏導(dǎo)數(shù)為零，有；即其中w*就是JF(w)的極值解。因為Sw非奇異，將上式兩邊左乘，可得：上式為求一般矩陣的特征值問題。利用的定義，將上式左邊的寫成：其中為一標(biāo)量，所以總是在向量的方向上。因此w*可寫成：從而可得：由于我們的目的是尋找最佳的投影方向，w*的比例因子對此并無影響，因此可忽略比例因子R/,有：基于最佳變換向量w*的投影w*是使Fisher準(zhǔn)則函數(shù)JF(w)取極大值時的解，也就是d維X空間到一維Y空間的最佳投影方向。有了w*，就可以把d維樣本x投影到一維，這實際上是多維空間到一維空間的一種映射，這個一維空間的方向w*相對于Fis

44、her準(zhǔn)則函數(shù)JF(w)是最好的。利用Fisher準(zhǔn)則，就可以將d維分類問題轉(zhuǎn)化為一維分類問題，然后，只要確定一個閾值T，將投影點yn與T相比較，即可進行分類判別。我們希望投影后，在一維Y空間中各類樣本盡可能分得開些，即希望兩類均值之差越大越好，同時希望各類樣本部盡量密集，希望類離散度越小越好。Lagrange乘數(shù)法（詳見相關(guān)數(shù)學(xué)文獻）Lagrange乘數(shù)法是一種在等式約束條件下的優(yōu)化算法，其基本思想是將等式約束條件下的最優(yōu)化問題轉(zhuǎn)化為無約束條件下的最優(yōu)化問題。問題：設(shè)目標(biāo)函數(shù)為y=f(x)，x=(x1, x2, , xn)求其在m(m<n)個約束條件gk(x)=0，k=1,2,m下的極

45、值。描述：引進函數(shù),其中k，k=1,2,m為待定常數(shù)。將L當(dāng)作n+m個變量x1, x2, , xn和1, 2, , m的無約束的函數(shù)，對這些變量求一階偏導(dǎo)數(shù)可得穩(wěn)定點所要滿足的方程：3.6 感知器算法出發(fā)點：一旦判別函數(shù)的形式確定下來，不管它是線性的還是非線性的，剩下的問題就是如何確定它的系數(shù)。在模式識別中，系數(shù)確定的一個主要方法就是通過對已知樣本的訓(xùn)練和學(xué)習(xí)來得到。感知器算法就是通過訓(xùn)練樣本模式的迭代和學(xué)習(xí)，產(chǎn)生線性（或廣義線性）可分的模式判別函數(shù)?；舅枷氩捎酶兄魉惴?Perception Approach)能通過對訓(xùn)練模式樣本集的“學(xué)習(xí)”得到判別函數(shù)的系數(shù)。說明：這里采用的算法不需要對

46、各類別中模式的統(tǒng)計性質(zhì)做任何假設(shè)，因此稱為確定性的方法。背景“感知器”一詞出自于20世紀(jì)50年代中期到60年代中期人們對一種分類學(xué)習(xí)機模型的稱呼，它是屬于有關(guān)動物和機器學(xué)習(xí)的仿生學(xué)領(lǐng)域中的問題。當(dāng)時的一些研究者認為感知器是一種學(xué)習(xí)機的強有力模型，后來發(fā)現(xiàn)估計過高了，但發(fā)展感知器的一些相關(guān)概念仍然沿用下來。感知器的訓(xùn)練算法已知兩個訓(xùn)練模式集分別屬于1類和2類，權(quán)向量的初始值為w(1)，可任意取值。若，若，則在用全部訓(xùn)練模式集進行迭代訓(xùn)練時，第k次的訓(xùn)練步驟為：若且，則分類器對第k個模式xk做了錯誤分類，此時應(yīng)校正權(quán)向量，使得w(k+1) = w(k) + Cxk，其中C為一個校正增量。若且，同樣

47、分類器分類錯誤，則權(quán)向量應(yīng)校正如下：w(k+1) = w(k) - Cxk ，若以上情況不符合，則表明該模式樣本在第k次中分類正確，因此權(quán)向量不變，即：w(k+1) = w(k) ，若對的模式樣本乘以(-1)，則有：時，w(k+1) = w(k) + Cxk ，此時，感知器算法可統(tǒng)一寫成：感知器算法的收斂性只要模式類別是線性可分的，就可以在有限的迭代步數(shù)里求出權(quán)向量。（證明作為練習(xí)）作業(yè)及編程用感知器算法求下列模式分類的解向量w:1: (0 0 0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T，2: (0 0 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T

48、，編寫求解上述問題的感知器算法程序。3.7 采用感知器算法的多類模式的分類采用3.1的多類情況3，將感知器算法推廣到多類模式。感知器算法判別函數(shù)的推導(dǎo)多類情況3：對M類模式存在M個判別函數(shù)di,l i = 1,2,M，若，則。設(shè)有M種模式類別1，2，M，若在訓(xùn)練過程的第k次迭代時，一個屬于i類的模式樣本x送入分類器，則應(yīng)先計算出M個判別函數(shù)：，若的條件成立，則權(quán)向量不變，即若其中第l個權(quán)向量使得，則相應(yīng)的權(quán)向量應(yīng)做調(diào)整，即其中C是一個正常數(shù)。權(quán)向量的初始值wi(1)，i = 1,2,M可視情況任意選擇。討論：這里的分類算法都是通過模式樣本來確定判別函數(shù)的系數(shù)，但一個分類器的判斷性能最終要受并未

49、用于訓(xùn)練的那些未知樣本來檢驗。要使一個分類器設(shè)計完善，必須采用有代表性的訓(xùn)練數(shù)據(jù)，它能夠合理反映模式數(shù)據(jù)的整體。要獲得一個判別性能好的線性分類器，究竟需要多少訓(xùn)練樣本？直觀上是越多越好，但實際上能收集到的樣本數(shù)目會受到客觀條件的限制；過多的訓(xùn)練樣本在訓(xùn)練階段會使計算機需要較長的運算時間；一般來說，合適的樣本數(shù)目可如下估計：若k是模式的維數(shù)，令C=2(k+1)，則通常選用的訓(xùn)練樣本數(shù)目約為C的1020倍。感知器算法實質(zhì)上是一種賞罰過程對正確分類的模式則“賞”，實際上是“不罰”，即權(quán)向量不變。對錯誤分類的模式則“罰”，使w(k)加上一個正比于xk的分量。當(dāng)用全部模式樣本訓(xùn)練過一輪以后，只要有一個模

50、式是判別錯誤的，則需要進行下一輪迭代，即用全部模式樣本再訓(xùn)練一次。如此不斷反復(fù)直到全部模式樣本進行訓(xùn)練都能得到正確的分類結(jié)果為止。作業(yè)用多類感知器算法求下列模式的判別函數(shù)：1: (-1 -1)T，2: (0 0)T，3: (1 1)T3.8 可訓(xùn)練的確定性分類器的迭代算法3.8.1 梯度法定義：梯度是一個向量，它的最重要性質(zhì)就是指出了函數(shù)f在其自變量y增加時最大增長率的方向。負梯度指出f的最陡下降方向，利用這個性質(zhì)，可以設(shè)計一個迭代方案來尋找函數(shù)的最小值。設(shè)函數(shù)f(y)是向量y = (y1, y2, , yn)T的函數(shù)，則f(y)的梯度定義為：從w(k)導(dǎo)出w(k+1)的一般關(guān)系式C是一個正的

51、比例因子（步長）采用梯度法求解的基本思想對感知器算法式中的w(k)、xk隨迭代次數(shù)k而變，是變量。定義一個對錯誤分類敏感的準(zhǔn)則函數(shù)J(w, x)。先任選一個初始權(quán)向量w(1)，計算準(zhǔn)則函數(shù)J的梯度，然后從w(1)出發(fā)，在最陡方向（梯度方向）上移動某一距離得到下一個權(quán)向量w(2) 。討論：若正確地選擇了準(zhǔn)則函數(shù)J(w,x)，則當(dāng)權(quán)向量w是一個解時，J達到極小值（J的梯度為零）。由于權(quán)向量是按J的梯度值減小，因此這種方法稱為梯度法（最速下降法）。為了使權(quán)向量能較快地收斂于一個使函數(shù)J極小的解，C值的選擇是很重要的。若C值太小，則收斂太慢；若C值太大，則搜索可能過頭，引起發(fā)散。3.8.2 固定增量的

52、逐次調(diào)整算法過程說明：設(shè)已由前一步迭代得到w(k)的值。讀入模式樣本xk，判別wT(k)xk是否大于0。在示意圖中，xk界定的判別界面為wT(k)xk=0。當(dāng)w(k)在判別界面的負區(qū)域時， wT(k)xk<0。校正： w(k+1)= w(k)+ xk ，這里取C=1。校正后， w(k+1)向量比w(k)向量更接近于模式xk所決定的正區(qū)域。討論：若模式是線性可分的，選擇合適的準(zhǔn)則函數(shù)J(w,x)，算法就能給出解。若模式不是線性可分的，算法的結(jié)果就會來回擺動，得不到收斂。作業(yè)采用梯度法和準(zhǔn)則函數(shù) 式中實數(shù)b>0，試導(dǎo)出兩類模式的分類算法。3.8.3 最小平方誤差(LMSE)算法出發(fā)點：

53、感知器算法只是當(dāng)被分模式可用一個特定的判別界面分開時才收斂，在不可分情況下，只要計算程序不終止，它就始終不收斂。即使在模式可分的情況下，也很難事先算出達到收斂時所需要的迭代次數(shù)。這樣，在模式分類過程中，有時候會出現(xiàn)一次又一次迭代卻不見收斂的情況，白白浪費時間。為此需要知道：發(fā)生遲遲不見收斂的情況時，到底是由于收斂速度過慢造成的呢，還是由于所給的訓(xùn)練樣本集不是線性可分造成的呢？最小平方誤差(LMSE)算法，除了對可分模式是收斂的以外，對于類別不可分的情況也能指出來。分類器的不等式方程求兩類問題的解相當(dāng)于求一組線性不等式的解，因此，若給出分別屬于1和2的兩個模式樣本的訓(xùn)練樣本集，即可求出其權(quán)向量w

54、的解，其性質(zhì)應(yīng)滿足：，將屬于2的模式乘以(-1)，可得對于全部模式都有的條件。設(shè)兩類模式的訓(xùn)練樣本總數(shù)為N，寫成增廣形式，則有不等式組：Xw > 0式中： w = (w1, w2, , wn, wn+1)T其中，0是零向量，是第i個n維模式樣本的增廣向量，即，它包括分屬于1和2中全部供訓(xùn)練用的樣本，但屬于2類的模式應(yīng)乘以(-1)，所以，X是一個N*(n+1)階的矩陣。Ho-Kashyap(H-K)算法lH-K算法是求解Xw=b，式中b=( b1, b2, , bn)T，b的所有分量都是正值。這里要同時計算w和b，我們已知X不是N*N的方陣，通常是行多于列的N*(n+1)階的長方陣，屬于超

55、定方程，因此一般情況下，Xw=b沒有唯一確定解，但可求其線性最小二乘解。設(shè)Xw=b的線性最小二乘解為w*，即使|Xw*-b|=極小。采用梯度法，定義準(zhǔn)則函數(shù)：。當(dāng)Xw=b的條件滿足時，J達到最小值。由于上式中包括的項為兩個數(shù)量方差的和，且我們將使其最小化，因此也稱之為最小均方誤差算法。使函數(shù)J同時對變量w和b求最小。對于w的梯度為：。使，得XT(Xw-b)=0，從而XTXw=XTb。因為XTX為(n+1)*(n+1)階方陣，因此可求得解：w = (XTX)-1XTb = X#b。這里X#= (XTX)-1XT稱為X的偽逆，X是N*(n+1)階的長方陣。由上式可知，只要求出b即可求得w。利用梯度

56、法可求得b的迭代公式為：根據(jù)上述約束條件，在每次迭代中，b(k)的全部分量只能是正值。由J的準(zhǔn)則函數(shù)式，J也是正值，因此，當(dāng)取校正增量C為正值時，為保證每次迭代中的b(k)都是正值，應(yīng)使為非正值。在此條件下，準(zhǔn)則函數(shù)J的微分為：該式滿足以下條件：若Xw(k) b(k) > 0，則若Xw(k) b(k) < 0，則由b的迭代式和微分，有：b(k+1) = b(k) + b(k)b(k) = CXw(k) b(k) + | Xw(k) b(k)|將此式代入w=X#b，有：w(k+1) = X#b(k+1) = X#b(k) +b(k) = w(k) + X#b(k)為簡化起見，令e(k) = Xw(k) b(k)，可得H-K算法的迭代式。設(shè)初值為b(1)，其每一分量均為正值，則：w(1) = X#b(1)。e(k) = Xw(k) b(k)。w(k+1) = w(k) + X#CXw(k) b(k) + |Xw(k) b(k)|= w(k) + CX#e(k) + |e(k)|。由于X#e(k) = X#Xw(k) b(k) = (XTX)-1XTXw(k) b(k)= w(k) X#b(k) = 0。因此w(k+1) = w(k) + CX#|e(k)|。b(k+1) = b(k) + CX