哈工大 模式識別第四章第五章

2023/2/1哈爾濱工業(yè)大學電信院宿富林1第四章特征的選擇與提取2023/2/1哈爾濱工業(yè)大學電信院宿富林2§4.1基本概念

如何確定合適的特征空間是設計模式識別系統(tǒng)另一個十分重要，甚至更為關鍵的問題。如果所選用的特征空間能使同類物體分布具有緊致性，即各類樣本能分布在該特征空間中彼此分割開的區(qū)域內，這就為分類器設計成功提供良好的基礎。反之，如果不同類別的樣本在該特征空間中混雜在一起，再好的設計方法也無法提高分類器的準確性。這一章要討論的問題就是特征空間如何設計的問題2023/2/1哈爾濱工業(yè)大學電信院宿富林3

如何構造一個特征空間，即對要識別的事物用什么方法進行描述、分析的問題？1、物理量的獲取與轉換(原始測量）這是指用什么樣的傳感器獲取電信號，如攝取景物則要用攝像機。可以稱之為原始信息(原始測量，得到測量空間)。2、描述事物方法的選擇與設計(特征形成)

在得到了原始信息之后，要對它進一步加工，以獲取對分類最有效的信息。

設計所要信息的形式是十分關鍵的。2023/2/1哈爾濱工業(yè)大學電信院宿富林4例用RGB顏色空間和HSI顏色空間右邊是原始圖像，左邊是用HSI空間描述的同一圖像(但是為了顯示出來，用H對應R，S對應G，I對應B，然后再以RGB的方式顯示出來3、特征空間的優(yōu)化這個層次的工作發(fā)生在已有了特征的描述方法之后，也就是已有了一個初始的特征空間，如何對它進行改造與優(yōu)化的問題。一般說來要對初始的特征空間進行優(yōu)化是為了降維。即初始的特征空間維數(shù)較高。能否改成一個維數(shù)較低的空間，稱為優(yōu)化，優(yōu)化后的特征空間應該更有利于后續(xù)的分類計算，這就是本章著重討論的問題。對特征空間進行優(yōu)化有兩種基本方法：一種為特征選擇，一種為特征的組合優(yōu)化----特征的提取。2023/2/1哈爾濱工業(yè)大學電信院宿富林52023/2/1哈爾濱工業(yè)大學電信院宿富林6特征選擇已有D維特征向量空間，Y={y1,y2,…,yD}，從原有的D維特征空間，刪去一些特征描述量，從而得到精簡后的特征空間。在這個特征空間中，樣本由d維的特征向量描述：X={x1,x2,…,xd}，d＜D。X只是Y的一個子集，每個分量xi必然能在原特征集中找到其對應的描述量xi＝y(tǒng)j。

2023/2/1哈爾濱工業(yè)大學電信院宿富林7特征提取找到一個映射關系：

A:Y→X

使新樣本特征描述維數(shù)比原維數(shù)降低。其中每個分量xi是原特征向量各分量的函數(shù)，即

Xi=fi(y1,y2,…,yD)

這兩種降維的基本方法是不同的。在實際應用中可將兩者結合起來使用，比如先進特征提取，然后再進一步選擇其中一部分，或反過來。

2023/2/1哈爾濱工業(yè)大學電信院宿富林8§4.2類別可分離性判據

對原特征空間優(yōu)化，就要對優(yōu)化結果進行評價實際的評價方法，是對系統(tǒng)性能進行測試，測試指標主要有正確率、計算速度、存儲容量等。本章討論的評價方法：目的在于找出對特征空間進行優(yōu)化的具體算法。對特征空間進行優(yōu)化是一種計算過程，它的基本方法仍然是模式識別的典型方法：找到一種準則(或稱判據，通常用一種式子表示），以及一種優(yōu)化計算方法，使這種準則達到一個極值。

2023/2/1哈爾濱工業(yè)大學電信院宿富林9判據理想的情況是與計算錯誤率有關的判據直接反映錯誤率的是貝葉斯公式，在實際中運用有困難采用其他判據2023/2/1哈爾濱工業(yè)大學電信院宿富林10可分性判據應滿足的要求（1）與錯誤率有單調關系，這使判據取最大值時錯誤率也較?。?）當特征獨立時

有可加性：

（Jij是第i類與第j類的可分性準則）

（3）度量特性：（4）單調性：加入新的特征時，判據不減小2023/2/1哈爾濱工業(yè)大學電信院宿富林11幾種常用的可分性判據以計算樣本在特征空間離散程度為基礎的準則，稱為基于距離的可分性判據（重點）基于概率密度分布的可分性判據。基于熵函數(shù)的可分性判據（不講）

2023/2/1哈爾濱工業(yè)大學電信院宿富林12一、基于距離的可分性判據基于距離的度量是用來進行分類的重要依據。因為一般情況下同類物體在特征空間呈聚類狀態(tài)，即從總體上說同類物體內各樣本由于具有共性，因此類內樣本間距離應比跨類樣本間距離小。Fisher準則(也可看成是特征提取方法)正是以使類間距離盡可能大同時又保持類內距離較小這一種原理為基礎的。同樣在特征選擇與特征提取中也使用類似的原理，這一類被稱為基于距離的可分性判據。

2023/2/1哈爾濱工業(yè)大學電信院宿富林13兩類之間的距離：ω1任一點與ω2中任一點的距離和的平均。多類：各類之間的平均距離

:ωi任一點xk(i)與ωj中任一點xj(

j)的距離Pi,Pj是第i類和第j類的先驗概率度量類內、類間的距離，可用不同方法，如歐氏距離等。

2023/2/1哈爾濱工業(yè)大學電信院宿富林14歐氏距離下的可分性判據歐氏距離：每類均值：所有樣本集總均值：平均距離：（判據）令：則得判據的矩陣形式：上述公式是有限樣本集，是均值及散度的估計。對于無限樣本，

tr：跡2023/2/1哈爾濱工業(yè)大學電信院宿富林152023/2/1哈爾濱工業(yè)大學電信院宿富林16考慮類內類間歐氏距離的其它判據判據Jd(X)是計算特征向量的總平均距離，以下一些判據則基于使類間離散度盡量大，類內離散度盡量小的考慮而提出。2023/2/1哈爾濱工業(yè)大學電信院宿富林17基于距離的可分性判據優(yōu)缺點距離準則：是樣本在特征空間的分布的距離作為特征提取的依據。優(yōu)點：直觀，計算簡便。缺點：沒有考慮概率分布，因此當不同類樣本中有部分在特征空間中交迭分布時，簡單地按距離劃分，無法表明與錯誤概率之間的聯(lián)系。2023/2/1哈爾濱工業(yè)大學電信院宿富林18基于概率分布的可分性判據：依據不同類別類分布概率密度函數(shù)來優(yōu)化特征空間不考慮各類的先驗概率，或假設兩類樣本的先驗概率相等（如下圖），可以看出：如果兩類條件概率分布互不交迭，則這兩類就完全可分；對所有X都有p(X|ω1)＝p(X|ω2)，則兩類就完全不可分。

完全可分重合，完全不可分二、基于概率分布的可分性判據通俗的講：若不同類別在特征空間的不同區(qū)域聚集，則分類就容易，它們重迭的程度越低，越有別于分類，因此這一類可分性判據就是用各種方式來度量它們之間重迭的程度。分布的交疊程度可用概率密度之間距離來描述2023/2/1哈爾濱工業(yè)大學電信院宿富林192023/2/1哈爾濱工業(yè)大學電信院宿富林20任何函數(shù)若滿足下列條件，則用于做判據：

1、Jp≥02、當兩類完全不交疊時，Jp取最大值若對所有x有：p(X|ω2)≠0時，p(x|ω1)=0，則Jp=max3、當兩類分布相同時，Jp=0

若：p(X|ω2)=p(x|ω1)，則Jp=0一種是用p(x|ω1)，p(x|ω2)之間的乘法來計算其重迭程度，像Bhattacharya距離、Chernoff界限等Bhattacharyya距離、Chernoff界限與錯誤率的上界有直接關系（見第二章）。因此Bhattacharyya距離、Chernoff界限不僅用來對特征空間進行降維優(yōu)化，而且也用來對分類器的錯誤率作出估計。另一種用兩者間的比值，稱為散度。2023/2/1哈爾濱工業(yè)大學電信院宿富林212023/2/1哈爾濱工業(yè)大學電信院宿富林221、Bhattacharyya距離

和Chernoff界限Bhattacharyya距離顯然，當p(X|ω1)＝p(X|ω2)時，JB＝0；而當兩者完全不交迭時JB為無窮大Chernoff界限2023/2/1哈爾濱工業(yè)大學電信院宿富林232、散度另一種常用的基于概率距離度量的判據是利用似然比或對數(shù)似然比。對兩類問題，對數(shù)似然比為：

可提供ωi對ωj的可分性信息。如果對某個X，當p(X|ω1)＝p(X|ω2)時，則lij=0,反之若兩者差異越大，則lij的絕對值也大。

2023/2/1哈爾濱工業(yè)大學電信院宿富林24對整個特征空間概率分布的差異程度作出評價，可將對ωi類及對ωj

的平均可分性信息定義為

總的平均可分信息則可表示成散度

2023/2/1哈爾濱工業(yè)大學電信院宿富林253、正態(tài)分布時可分性判據

若則一維：2023/2/1哈爾濱工業(yè)大學電信院宿富林26若則2023/2/1哈爾濱工業(yè)大學電信院宿富林274.3特征提取4.3.1按距離度量的特征提取方法

基于距離的可分性判據的實質是Fisher準則的延伸，即綜合考慮不同類樣本的類內聚集程度與類間的離散程度這兩個因素。這種判據的優(yōu)化體現(xiàn)出降維后的特征空間較好地體現(xiàn)類內密集、類間分離的要求。2023/2/1哈爾濱工業(yè)大學電信院宿富林28按歐氏距離度量的特征提取方法基于距離可分性判據的特征優(yōu)化過程是通過一個線性變換實現(xiàn)的。設在原特征空間一個樣本向量表示成X(D維)而在優(yōu)化特征空間中，樣本向量表示成Y(d維)而X與Y之間的關系是：

Y=WTX其中W是一個D×d維矩陣（d<D）目的：利用判據找出一種線性變換W，它可實現(xiàn)這種判據J(Y)=J(W)的極值化。1、J2判據下的特征提取將原特征空間X(D維)通過線性映射Y=WTX降維到特征空間Y中，若X空間的類內離散度矩陣和類間離散度矩陣分別為SW,Sb;則按J2判據的的最后特征提取矩陣W是按如下方式構造的：若矩陣SW-1Sb

的本征值λi按大小順序列為則選擇前d個本征值所對應的本征向量組成變換矩陣WD*d，都可使這些判據J2(W)達到最大值。2023/2/1哈爾濱工業(yè)大學電信院宿富林292023/2/1哈爾濱工業(yè)大學電信院宿富林30證明：因為：Y=WTX，

設：X的類內和類間離散度矩陣分別為SW,Sb則：Y的類內和類間離散度矩陣分別為SW‘,Sb‘為SW’=WSW’WT,Sb’=WSb’WT

（見第3章中，F(xiàn)isher準則一節(jié)）在使用J2判據下，將其Y的可分性判據表示成變換W的函數(shù)：

J2(Y)=tr[(SW’)-1Sb’]則：J2(Y)=tr[(WSWWT)-1(WSbWT)]=J2(W)可以證明：在不降維條件下，即，設W是D*D維的，則J2判據不變J2(Y)=

J2(X)。哈爾濱工業(yè)大學電信院宿富林30J2(W)=tr[(WSWWT)-1(WSbWT)]=tr[(WT)-1SW-1W-1WSbWT)]=tr[(WT)-1SW-1SbWT]=tr[SW-1SbWT(WT)-1]=tr[SW-1Sb]=J2(X)設SW-1Sb的本征值為λ1>λ2>λ3>……>λD

，對應的本征向量矩陣為U=[u1，u2,….,uD]則UTSW-1SbU=Λ,其中：令W=UT=U-1則J2(W)=tr[UTSW-1SbU]

2023/2/1哈爾濱工業(yè)大學電信院宿富林312023/2/1哈爾濱工業(yè)大學電信院宿富林32上式表明D維特征空間中，J2判據的值是矩陣的全部本征值之和。令上式中WT=Ud=[u1，u2,….,ud]則則：如果矩陣的本征值按大小順序列為那么由對應于d個最大的本征值的本征向量所組成的矩陣W(D×d)，就能使所得到的d維特征滿足J2判據最大的要求。此結論對J4判據也適用2023/2/1哈爾濱工業(yè)大學電信院宿富林33例：給定先驗概率相等的兩類，其均值向量分別為：協(xié)方差矩陣是：

求用J2判據的最優(yōu)特征提取。

2023/2/1哈爾濱工業(yè)大學電信院宿富林34解：應先求，再求此矩的特征矩陣?；旌暇殿愰g離散度矩陣：類內離散度矩陣2023/2/1哈爾濱工業(yè)大學電信院宿富林35求

的本征值矩陣。由于這是一個兩類別問題，總均值向量μ值是兩個均值向量μ1和μ2的線性求和，則

中只有一個是獨立的，因此

的秩是一，換句話說它只有一個非零本征值，W是D×1矩陣，是一個向量W，求該向量需解

利用W向量對原始的兩類兩維樣本進行線性變換得到新的一維分布，特征空間從二維降到一維，并滿足J2判據。該特征空間實質上就是對應于Fisher準則求得的線性分類器的法向量。如果討論的是多類別C問題，則優(yōu)化后的維數(shù)至多為類別數(shù)減一(C-1)。2023/2/1哈爾濱工業(yè)大學電信院宿富林362、J5判據下的特征提取由于和是對稱矩陣，因此，存在矩陣U使得：則：

2023/2/1哈爾濱工業(yè)大學電信院宿富林372023/2/1哈爾濱工業(yè)大學電信院宿富林38即：是的本征值矩陣或是對角陣的證明及計算方法：2023/2/1哈爾濱工業(yè)大學電信院宿富林39J5的另一種形式（與J2比較）又設的本征值矩陣是則：2023/2/1哈爾濱工業(yè)大學電信院宿富林404.3.2按概率距離判據提取特征

設原始特征為Y，而經變換后的特征為X，兩者之間有映射關系

X=WTY

則原空間中一矩陣A經映射后為：A*=WTAW映射后概率距離判據：

JC(X)=JC(WTY)=JC(W)JD(X)=JD(WTY)=JD(W)2023/2/1哈爾濱工業(yè)大學電信院宿富林412023/2/1哈爾濱工業(yè)大學電信院宿富林41一、正態(tài)分布下基于Jc的特征提取當兩類都是正態(tài)分布時：2023/2/1哈爾濱工業(yè)大學電信院宿富林422023/2/1哈爾濱工業(yè)大學電信院宿富林432023/2/1哈爾濱工業(yè)大學電信院宿富林44由于Jc在任何非奇異變換下具有不變性，因此，WU=VU-1U=V也是最優(yōu)變換陣，是Σ-1M的本征向量。而M的秩是1，故只有一個非零本征值，此時：2023/2/1哈爾濱工業(yè)大學電信院宿富林45可證，只有一個非零本征值，此時，W是一維的：是的本征值矩陣W是其本征向量2023/2/1哈爾濱工業(yè)大學電信院宿富林462023/2/1哈爾濱工業(yè)大學電信院宿富林472023/2/1哈爾濱工業(yè)大學電信院宿富林48根據Jc對非奇異變換的不變性，W即是Σ2-1Σ1的本征向量。此時：2023/2/1哈爾濱工業(yè)大學電信院宿富林49為使Jc最大，應選擇滿足如下關系的d個本征值對應的本征向量組成的矩陣。2023/2/1哈爾濱工業(yè)大學電信院宿富林502023/2/1哈爾濱工業(yè)大學電信院宿富林50步驟不同s，結果不同。1、s=0.5，得：Vi,i=1,2,…,d。2、根據Vi,i=1,2,…,d,求最優(yōu)S(使Jc最大)3、求最佳Vi,i=1,2,…,d4、用新的S重復1，2、3直至獲得一組穩(wěn)定Vi二、用散度準則JD的特征提取2023/2/1哈爾濱工業(yè)大學電信院宿富林51只有兩類時：2023/2/1哈爾濱工業(yè)大學電信院宿富林52最佳W是對應下列次序的本征值對應的本征向量例：有兩類樣本：

W1:x11=(0,0,0)T,X12=(1,0,0)T,X13=(1,0,1)T,X14=(1,1,0)T

W2:x21=(0,0,1)T,X22=(0,1,0)T,X23=(0,1,1)T,X24=(11,1)T

試利用散度JD降低維數(shù)。2023/2/1哈爾濱工業(yè)大學電信院宿富林53特征提取結果：Y=WTXW1:y11=0,y12=-1,y13=0,y14=0W2:y21=1,y22=1,y23=2,y24=12023/2/1哈爾濱工業(yè)大學電信院宿富林54-1012*00*2023/2/1哈爾濱工業(yè)大學電信院宿富林55§4.4特征選擇

特征選擇在概念上十分簡單，即對原有特征進行刪選優(yōu)化。通常，人們認為：只要逐個分析每個特征，判斷它對分類的價值，然后根據其優(yōu)值刪去或保留，這是一個為人們常采用方法，但是這種方法并不能保證特征空間的最優(yōu)組合優(yōu)化，因此本節(jié)討論了一些原理上更好的方法。2023/2/1哈爾濱工業(yè)大學電信院宿富林56兩個問題一：選擇特征的標準：也就是選擇前面討論過的可分離性判據，以這些判據為準則，使所選擇的d維子空間具有最大的可分離性。二：是要找出較好的特征選擇方法，以在允許的時間內選擇出一組最優(yōu)的特征。所謂最優(yōu)的特征組，就是要找到合適的特征的組合。如果從逐個特征配組進行性能比較的話，即窮舉的算法，特征配組的數(shù)量可能極大，組合配置的數(shù)目按下式計算

2023/2/1哈爾濱工業(yè)大學電信院宿富林57如果D＝100，d＝10，則q的數(shù)量級就是1013，即使D＝20，d＝10，則q也可達184756種。如果將所有可能的特征配組列舉出來，按某選定的可分離性判據進行計算，從中擇優(yōu)，其計算量之大是可想而知的。任何非窮舉的算法都不能確保所得結果是最優(yōu)的，因此要得最優(yōu)解，就必需采用窮舉法，只是在搜索技術上采用一些技巧，使計算量有可能降低。2023/2/1哈爾濱工業(yè)大學電信院宿富林58“自上而下”與“自下而上”“自上而下”是指，從D維特征開始，逐步將其中某些特征刪除，直到剩下所要求的d維特征為止。而“自下而上”則是從零維特征空間開始，逐個地從D維持征中選擇特征，直至達到預定的維數(shù)指標為止。在選擇的過程中，“自上而下”算法做到篩選剩下的特征組在每一步上都是最優(yōu)的，而“自下而上”則在每一步都生成最優(yōu)的特征空間。

2023/2/1哈爾濱工業(yè)大學電信院宿富林59

4.4.1最優(yōu)搜索算法

“分支定界”算法：至今能得到最優(yōu)解的唯一快速算法屬于“自上而下”算法，但是具有回溯功能，可使所有可能的特征組合都被考慮到。其核心問題是通過合理組合搜索過程，可以避免一些計算而仍能得到最優(yōu)的結果。關鍵是利用了判據的單調性。如果特征存在包含關系：?i是?j的子集

則有J(?i)≤J(?j)稱該判據具有單調性分支定界算法（略）2023/2/1哈爾濱工業(yè)大學電信院宿富林604.4.2次優(yōu)搜索法

上述分支定界算法雖然比盲目窮舉法節(jié)省計算量，但計算量仍可能很大而無法實現(xiàn)，因此人們還是常用次優(yōu)搜索法。4.4.2.1單獨最優(yōu)特征組合

這是一種最簡單的方法，即將各特征按單獨使用計算其判據值，然后取其前d個判據值最大的特征作為最優(yōu)特征組合。這種做法的問題在于即使各特征是獨立統(tǒng)計的，也不一定得到最優(yōu)結果。

2023/2/1哈爾濱工業(yè)大學電信院宿富林61但如果可分性判據可寫成如下形式

或

則用這種方法可以選出一組最優(yōu)的特征來。例如當兩類都是正態(tài)分布，各特征統(tǒng)計獨立時，用Mahalanobis距離作為可分性判據，上述條件可以滿足。

2023/2/1哈爾濱工業(yè)大學電信院宿富林62

4.4.2.2順序前進法

(SequentialForwardSelection----SFS)

這是最簡單的自下而上搜索方法。首先計算每個特征單獨進行分類的判據值，并選擇其中判據值最大的特性，作為入選特征。然后每次從未入選的特征中選擇一個特征，使得它與已入選的特征組合在一起時所得的J值為最大，直到特征數(shù)增至d個為止。

2023/2/1哈爾濱工業(yè)大學電信院宿富林63廣義順序前進法

(GeneralizedSequentialForwardSelection----GSFS)順序前進法與前一小節(jié)的單獨特征最優(yōu)化組合相比，一般說來，由于考慮了特征之間的相關性，在選擇特征時計算與比較了組合特征的判據值，要比前者好些。其主要缺點是，一旦某一特征被選入，即使由于后加入的特征使它變?yōu)槎嘤?，也無法再把它剔除。推廣至每次入選

r個特征，而不是一個，稱為廣義順序前進法(GSFS)。與SFS相比，該法在每次入選r個特征時，考慮了他們之間的相關性。缺點是計算量大大增加.CD-kr。2023/2/1哈爾濱工業(yè)大學電信院宿富林644.4.2.3順序后退法

(SequentialBackwardSelection----SBS)

這是一種自上而下的方法。做法也很簡單，從現(xiàn)有的特征組中每次減去一個不同的特征并計算其判據，找出這些判據值中之最大值，如此重復下去直到特征數(shù)達到予定數(shù)值d為止。與SFS相比，此法計算判據值是在高維特征空間進行的，因此計算量比較大。此法也可推廣至每次剔除r個，稱為廣義順序后退法(GeneralizedSequentialBackwardSelection----GSBS)。

2023/2/1哈爾濱工業(yè)大學電信院宿富林65

4.4.2.4增l減r法(l-r法)

前面兩種方法都有一個缺點，即一旦特征入選(或剔除)，過程不可逆轉。為了克服這種缺點，可采用將這兩種方法結合起來的方法，即增l減r法。其原理是對特征組在增加l個特征后，轉入一個局部回溯過程，又用順序后退法，剔除掉r個特征。這種方法既可能是“自上而下”方法，也可能是“自下而上”的，這取決于l與r的數(shù)據大小。當l>r時，入選特征數(shù)逐漸增加，屬“自下而上”型，反之屬“自上而下”型。

l-r法1）用SFS法在未入選特征中逐個入選l個特征2）用SBS法在已入選特征中逐個剔除r個特征。3）若特征數(shù)是d，則終止算法。否則，轉入（1）L>r時，是自下而上的算法，先執(zhí)行第1步，起始時，入選特征是空集ΦL<r時，是自上而下的算法，先執(zhí)行第2步，起始時，入選特征是原有特征集X={x1,x2,….,XD}2023/2/1哈爾濱工業(yè)大學電信院宿富林662023/2/1哈爾濱工業(yè)大學電信院宿富林67（ZL,Zr）法此法也可推廣至用GSFS及GSBS代替SFS及SBS，并可在實現(xiàn)增加l特征時采用分幾步實現(xiàn)。(ZL,Zr)法：增L個特征用ZL步，每步可入選li(i=1,2,…,ZL)個特征。ZL=（l1,l2,l3,……,lZL）；減r則用Zr步，每步可剔除ri(i=1,2,…,Zr)個特征。Zr=（r1,r2,r3,……,rZr）這種做法是為了既考慮入選(或剔除)特征之間的相關性，又不至因此引起計算量過大。合理地設置ZL與Zr，可以同時對兩者，即計算復雜性及特征選擇的合理性兼顧考慮。2023/2/1哈爾濱工業(yè)大學電信院宿富林68前面的各種方法可看作是（ZL,Zr）法的特例(ZL,Zr)法等效算法ZL=（1）Zr=（0）SFSZL=（0）Zr=（1）SBSZL=（d）Zr=（0）窮舉法ZL=（L）Zr=（0）GSFSZL=（0）Zr=（r）GSBSZL=(1,1,1,…,1)Zr=(1,1,….,1)（l，r）2023/2/1哈爾濱工業(yè)大學電信院宿富林694.5基于Karhunen-Loeve變換

（K-L變換）的特征提取

K-L變換又稱主分量分析，是一種正交變換，常用來作為數(shù)據壓縮。這里我們用它作降維

2023/2/1哈爾濱工業(yè)大學電信院宿富林704.5.1傅立葉級數(shù)展開周期平穩(wěn)隨機過程x(t)的Fourier展開則：周期平穩(wěn)過程的Fourier系數(shù)互不相關2023/2/1哈爾濱工業(yè)大學電信院宿富林71(X(t)周期------R(t)周期,周期也為T）2023/2/1哈爾濱工業(yè)大學電信院宿富林724.5.2K-L展開將一個非周期隨機過程x(t)在區(qū)間[a,b]展開為其中：2023/2/1哈爾濱工業(yè)大學電信院宿富林73本征值本征函數(shù)則：兩邊同乘并積分，則：2023/2/1哈爾濱工業(yè)大學電信院宿富林74離散情況用完備正交向量(基)uj(j=1,2,…)展開若用有限項估計：則展開x’是x的一個近似均方誤差為：2023/2/1哈爾濱工業(yè)大學電信院宿富林75本征分解2023/2/1哈爾濱工業(yè)大學電信院宿富林76誤差因此，可對X的自相關做本征分解，若取前d個最大本征值對應的本征向量來展開X時，截斷的均方誤差最小(實際展開時，因為X的維數(shù)是D,只能求得D個本征值和本征向量)。這d個本征向量所組成的正交坐標系稱為X在D維空間的d維K-L變換系。X在K-L坐標系uj上的展開系數(shù)稱作X的K-L變換。2023/2/1哈爾濱工業(yè)大學電信院宿富林774.5.3K-L展開式的性質(1)K-L變換的展開系數(shù)是互相無關的。2023/2/1哈爾濱工業(yè)大學電信院宿富林78(2)K-L變換后的協(xié)方差陣為對角陣令K-L變換后的D維坐標系統(tǒng)中樣本向量為

X’=(c1,c2,…,cD)T則：或：這表明經過K-L變換后，原向量各分量之間存在的相關性已被消除。2023/2/1哈爾濱工業(yè)大學電信院宿富林794.5.4K-L變換的一些典型應用

1．降維與壓縮

例如：一幅人臉圖象，大小為：M×N。

K-L變換后只用到30個基，那么維數(shù)就降至30。可見降維的效果是極其明顯的。另一方面降維與數(shù)據壓縮又是緊密聯(lián)系在一起的。譬如原訓練樣本集的數(shù)量為V，現(xiàn)采用30個基，每個基實質上是一幅圖象，再加上每幅圖象的描述參數(shù)，數(shù)據量是大大降低?；鶊D像Ui，i=1，…,d是通用的

=(c1,c2,……)T

2023/2/1哈爾濱工業(yè)大學電信院宿富林802．構造參數(shù)模型使用K-L變換不僅僅起到降維與壓縮數(shù)據的作用，更重要的是每個描述量都有明確的意義，因而改變某一個參數(shù)就可讓圖象按所需要的方向變化。在沒有使用K-L變換的原數(shù)據集中對圖象的描述量是每個象素的灰度值，而弧立地改變某個象素的灰度值是沒有意義的。

而在使用K-L變換后，每個描述量都有其各自的作用。因此通過改變這些參數(shù)的值就可實現(xiàn)對模型的有效描述，這在圖象生成中是很有用的。因此利用K-L變換構造出可控制的，連續(xù)可調的參數(shù)模型在人臉識別與人臉圖象重構采方面的應用是十分有效的。

2023/2/1哈爾濱工業(yè)大學電信院宿富林813．人臉識別利用K-L變換進行人臉圖象識別是一個著名的方法。首先搜集要識別的人的人臉圖象，建立人臉圖象庫。然后利用K-L變換確定相應的人臉基圖象(特征臉)，再反過來用這些基圖象對人臉圖象庫中的所有人臉圖象進行K-L變換，從而得到每幅圖象的參數(shù)向量并將每幅圖的參數(shù)向量存起來。在識別時，先對一張所輸入的臉圖象進行必要的規(guī)范化，再進行K-L變換分析，得到其參數(shù)向量。將這個參數(shù)向量與庫中每幅圖的參數(shù)向量進行比較，找到最相似的參數(shù)向量，也就等于找到最相似的人臉，從而認為所輸入的人臉圖象就是庫內該人的一張人臉,完成了識別過程。

2023/2/1哈爾濱工業(yè)大學電信院宿富林824．人臉圖象合成用K-L變換構造參數(shù)模型的另一種典型用途是人臉圖象合成。有目的的控制各個分量的比例，也就是通過調整參數(shù)向量?？梢詫⒁环粠П砬閳D象改變成帶各種表情的圖象，稱為人臉表情圖象合成。2023/2/1哈爾濱工業(yè)大學電信院宿富林832023/2/1哈爾濱工業(yè)大學電信院宿富林844.5.5使用K-L變換進行特征提取上面討論K-L變換時得出K-L坐標系是由E[XXT]的本征值對應的本征向量產生，因而被稱為K-L坐標系的產生矩陣。實際上使用不同的向量作為產生矩陣，會得到不同的K-L坐標系，從而滿足不同的分類要求。一般，沒有類別標簽的樣本集的均值向量u常常沒有意義，因此，可用樣本數(shù)據的協(xié)方差矩陣

E[(X-u)(X-u)T]作為產生矩陣。

2023/2/1哈爾濱工業(yè)大學電信院宿富林85對分類問題，如何形成產生矩陣?當樣本集中各樣本的類別標簽已知時，可以得到不同的Σ，Σ有多個（不同類可有不同的Σ）,如何形成產生矩陣?1）如各類別先驗概率為Pi

，均值為i，協(xié)方差矩陣為Σi=E[(X-ui)(X-ui)T]

則可以用類內離散矩陣SW=ΣPi

Σi作為產生矩陣，其效果相當于只按類內離散程度進行特征選取。2）如果只以某一類樣本集的協(xié)方差矩陣Σi作為產生矩陣，則效果是對該類樣本集有信息壓縮的最優(yōu)性。2023/2/1哈爾濱工業(yè)大學電信院宿富林861利用類均值向量提取特征類條件均值ui包含大量的分類信息。為了降低維數(shù)，且盡可能地保持原有特征的分類信息，應選擇一種變換，是變換后的類條件均值向量的給分量比其他的變換保持更多的分類信息?；跉W氏距離特征提取：判據是從使類內盡可能密集，類間盡可能分開的思想出發(fā)的。但是，各類均值向量各分量的分類性能，不僅與取決于各均值向量各分量之間的距離，而且，還和其方差以及各分量的相關程度有關。如何在K-L變換方法中體現(xiàn)對這兩者的兼顧?具體算法1）為了估計各分量（特征）對于分類的單獨作用，先按類內離散度矩陣Sw作為產生矩陣產生相應的K-L坐標系統(tǒng)，從而把包含在原向量中各分量的相關性消除，并得到在新坐標系中各分量離散的程度。2）然后對均值向量在這些新坐標中分離的程度作出判斷，決定在各坐標軸分量均值向量所能提供的相對可分性信息。據此選取K-L變換的基向量作為特征提取變換矩陣。2023/2/1哈爾濱工業(yè)大學電信院宿富林872023/2/1哈爾濱工業(yè)大學電信院宿富林88在uj軸上，原第i類特征向量Xik投影為：Xikj=ujTXik其類內離散度：其類間離散度2023/2/1哈爾濱工業(yè)大學電信院宿富林892023/2/1哈爾濱工業(yè)大學電信院宿富林90可設判據J(Xi)為類間離散度與類內離散度在uj坐標的分量之比:

其中:J(Xi)越大，表明在新坐標系中該坐標抽包含較多可分性信息。2023/2/1哈爾濱工業(yè)大學電信院宿富林913）為了降低特征空間的維數(shù)，可以將各分量按大小重新排列，使

J(X1)≥J(X2)≥J(X3)….≥J(XD)

取與前面d個最大的J(Xi)≥值相對應的本征向量uj，j=1,...,d;作為特征空間的基向量。W=[u1,u2,…,ud]

2023/2/1哈爾濱工業(yè)大學電信院宿富林92

例:設有兩類問題，其先驗概率相等，即:P(w1)=P(w2)=0.5，設樣本的類均值向量分別為：

類協(xié)方差矩陣分別是：把維數(shù)從2壓縮為12023/2/1哈爾濱工業(yè)大學電信院宿富林93解1）將SW作K-L變換的產生矩陣，求其本征矩陣得K-L變換的變換矩陣?？汕蟮帽菊髦稻仃嚭捅菊飨蛄糠謩e是：2023/2/1哈爾濱工業(yè)大學電信院宿富林94又2）求得：3）2023/2/1哈爾濱工業(yè)大學電信院宿富林952、包含在類平均向量中判別信息的最優(yōu)壓縮上面方法（利用類均值向量提取特征）為了兼顧類內離散度與類間離散度，包含在類均值向量內的分類信息并沒有全部利用。即：類平均向量的判別信息在K-L坐標系的各個分量中都有反映，并沒有得到最優(yōu)壓縮。

如圖，如僅從類均值向量所包含的分類判別信息全部被利用出發(fā)，應選擇包含兩均值向量連線方向在內的坐標系。但是簡單地從類均值向量來確定特征子空間，雖然實現(xiàn)很容易，但一般不能滿足各分量間互不相關的要求。2023/2/1哈爾濱工業(yè)大學電信院宿富林96例外情況：如果類內離散度矩陣Sw是一個單位矩陣，即它在特征空間中以超球體分布，從類均值向量來確定特征子空間就可做到既保持各分量的不相關性，同時又能充分利用包含在類均值向量內的差別信息。從這種特殊情況得到啟發(fā)，一種充分利用類均值向量所包含的判別信息的方法因此而產生。具體說來這種方法分成兩步：1）白化處理2）特征提取2023/2/1哈爾濱工業(yè)大學電信院宿富林97第一步：白化處理1、先用原坐標系中Sw作為產生矩陣，實行K-L變換，將原有數(shù)據的相關性消除掉。

UTSw=ΛU，或UTSwU=Λ在K-L坐標系U上，新的特征向量為：Y1=UTX

Y1的類內離散度矩陣S’w=Λ是一個對角矩陣。2、進一步實行變換：Y2=Λ-1/2Y1，則Y2的類內離散度矩陣變?yōu)椋害?1/2

UTSwUΛ-1/2=Λ-1/2ΛΛ-1/2=I

即：(UΛ-1/2)

Sw(UΛ-1/2)=I3、令:B=UΛ-1/2（白化矩陣），則：BTSwB=I（白化）

此時，

Y2=Λ-1/2Y1=Λ-1/2UTX=(UΛ-1/2)TX=BTX經過B變換后（Y2）的類間離散度矩陣S’b應有：S’b=BTSbB2023/2/1哈爾濱工業(yè)大學電信院宿富林98第二步:特征提取1）采用上節(jié)方法求最佳的變換。因S’W

=I則，Λ=I而且，U可以是任何正交矩陣。即UTIU=UTU=I則判據：由于U可以上任何正交矩陣，因此，可以以S’b作為產生矩陣，作第二次K-L變換，得到正交矩陣VTSb’=Λ’V則判據因此，按判據最大選擇uj，就是按Sb’正交分解的本征值λ’j最大選擇。由于S’b的秩最多是c-1，所以最多只有c-1個非零本征值。選擇最大的d（≤c-1）個非零本征值

，則該d個非零本征值就可表示類均值向量所包含的全部信息。設這d個本征向量系統(tǒng)用V’表示，即

V’=[v1,v2,….,vd]（d≤c-1）則變換為:Y=V’TY22）將第一步得到的結果代入，整個變換為：Y=VTY2=VTBTX=(BV)TX=WTX因此變換矩陣為：W=BV=UΛ-1/2V2023/2/1哈爾濱工業(yè)大學電信院宿富林99具體算法1）對原特征向量計算類內離散度矩陣Sw和類間離散度矩陣Sb2）用Sw作為產生矩陣做KL變換求坐標系U及Λ：UTSwU=Λ3）計算變換矩陣:B=UΛ-1/24）計算經過B變換后的類間離散度矩陣S’b：S’b=BTSbB5）以S’b作為產生矩陣，作第二次K-L變換VTSb’=Λ’V6）選擇Λ’中最大d個本征值對應的d（≤c-1）個本征向量

V’=[v1,v2,….,vd]7）計算最終的變換矩陣：W=BV’=UΛ-1/2V’W即是降維的變換矩陣?？蓪維特征向量降維d維（前3步是白化過程）2023/2/1哈爾濱工業(yè)大學電信院宿富林1002023/2/1哈爾濱工業(yè)大學電信院宿富林1012023/2/1哈爾濱工業(yè)大學電信院宿富林101

例:數(shù)據同上例，求保持類均值向量中全部分類信息條件下壓縮為一維特征空間的坐標軸。

設有兩類問題，其先驗概率相等，即:P(w1)=P(w2)=0.5，設樣本的類均值向量分別為：

類協(xié)方差矩陣分別是：2023/2/1哈爾濱工業(yè)大學電信院宿富林102解：2023/2/1哈爾濱工業(yè)大學電信院宿富林103下圖給出了兩次變換步驟

以及變換對數(shù)據產生的作用由圖中看出，樣本原為橢圓形分布，經白化處理后轉化為圓形分布，此時S’w為單位矩陣。均值向量也隨之變化，最后得到的均值向量作為降維后的一維坐標。這種方法主要用在類別數(shù)C比原特征向量的維數(shù)D小得多的情況，由于Sb的秩最多為C-1，因此可使特征維數(shù)降至C維以下。2023/2/1哈爾濱工業(yè)大學電信院宿富林104第五章非監(jiān)督學習法2023/2/1哈爾濱工業(yè)大學電信院宿富林105本章重點1.什么叫非監(jiān)督學習方法，什么叫有監(jiān)督學習方法？

2.非監(jiān)督學習方法主要的用途

3.非監(jiān)督學習方法的兩種基本處理方法：按分布密集程度劃分，與按相似度聚類劃分

4.按分布密度程度劃分的基本方法

5.動態(tài)聚類方法與分級聚類方法的概念

6.典型的動態(tài)聚類方法C-均值算法與ISODATA算法

7.使用非歐氏距離計算相似度的動態(tài)聚類方法

8.分級聚類方法2023/2/1哈爾濱工業(yè)大學電信院宿富林106本章難點

1.非監(jiān)督學習方法與監(jiān)督學習方法概念的區(qū)別

2.按分布密集程度劃分的基本方法

3.動態(tài)聚類方法-迭代修正的概念

4.分級聚類方法2023/2/1哈爾濱工業(yè)大學電信院宿富林107本章學習目標

1.掌握非監(jiān)督學習方法的概念、用途

2.了解非監(jiān)督學習方法對數(shù)據劃分有兩種基本方法

3.掌握以c-均值算法，ISODATA算法為代表的動態(tài)聚類方法

2023/2/1哈爾濱工業(yè)大學電信院宿富林108§5.1引言以前討論的分類器設計方法都是在樣本集中的類別標簽已知的條件下進行的，這些樣本稱為訓練樣本。在樣本類別標簽已知的情況下，可以統(tǒng)計出各類訓練樣本不同的描述量，如其概率分布，或在特征空間分布的區(qū)域等，利用這些參數(shù)進行分類器設計，稱為有監(jiān)督的學習方法。然而在實際應用中，不少情況下無法預先知道樣本的標簽，也就是說沒有訓練樣本，因而只能從沒有樣本標簽的樣本集進行分類器設計，這就是非監(jiān)督學習方法。2023/2/1哈爾濱工業(yè)大學電信院宿富林109一幅道路圖像按路面與非路面分類其中左圖是在圖像中路面區(qū)與非路面中各找一個窗口，將其中每個象素分別作為這兩類的訓練樣本集，用這兩個樣本集在特征空間的分布參數(shù)進行設計（有監(jiān)督的學習）。右圖，無法預先選擇不同類別的樣本集，而是將整幅圖的像素都作為待分類樣本集，通過它們在特征空間中表現(xiàn)出來的聚類現(xiàn)象，把不同類別劃分開。（非監(jiān)督學習）2023/2/1哈爾濱工業(yè)大學電信院宿富林110

有監(jiān)督學習中，樣本集分布呈現(xiàn)交迭情況，而無監(jiān)督學習方法由于沒有類別樣本指導，無法確定它們的交迭情況，只能按分布的聚類情況進行劃分。在類似于該例的實際應用問題中，預先選定不同類別的樣本往往不可能，如時間不允許，或無法用人工干予等因素。

另外在某些有監(jiān)督學習方法中（例如，局部訓練法），也往往需要利用聚類方法將樣本按其分布劃分成若干子類等。聚類方法就是無監(jiān)督學習方法的一個內容，它是經常應用的一門技術。非監(jiān)督學習方法要解決的問題觀察事物與分析事物，從中尋找其規(guī)律性，這就是非監(jiān)督學習方法要解決的問題。2023/2/1哈爾濱工業(yè)大學電信院宿富林1112023/2/1哈爾濱工業(yè)大學電信院宿富林112非監(jiān)督學習與有監(jiān)督學習的不同點1．數(shù)據集不同：

有監(jiān)督學習方法必須要有訓練集與測試樣本。在訓練集中找規(guī)律，而對測試樣本使用這種規(guī)律；

非監(jiān)督學習沒有訓練集，只有一組數(shù)據，在該組數(shù)據集內尋找規(guī)規(guī)律2．目的不同有監(jiān)督學習方法的目的就是識別事物。識別的結果表現(xiàn)在給待識別數(shù)據加上了標號，因此訓練樣本集必須由帶標號的樣本組成。非監(jiān)督學習方法的目的是尋找數(shù)據集中的規(guī)律性。只有要分析的數(shù)據集本身，預先沒有什么標號。如果發(fā)現(xiàn)數(shù)據集呈現(xiàn)某種聚集性，則可按自然的聚集性分類，但不以與某種預先的分類標號對上號為目的。3.算法不同2023/2/1哈爾濱工業(yè)大學電信院宿富林113無監(jiān)督學習算法分類兩大類：基于概率密度函數(shù)估計的直接方法：指設法找到各類別在特征空間的分布參數(shù)再進行分類。如：單峰子類的分離方法（投影法等），基于樣本間相似性度量的間接聚類方法：其原理是設法定出不同類別的核心或初始類核，然后依據樣本與這些核心之間的相似性度量將樣本聚集成不同類別。迭代的動態(tài)聚類算法（K均值聚類，ISODATA算法），非迭代的分級聚類算法

2023/2/1哈爾濱工業(yè)大學電信院宿富林114§5.2單峰子類的分離方法

樣本概率密度分布在特征空間的分布是多峰的。每個單峰區(qū)域則被看作不同的決策域。落在同一單峰區(qū)域的待分類樣本就被劃分成同一類，稱為單峰子類。5.2.1投影法高維空間尋找概率密度的“峰”是困難的。一維空間尋找概率密度的“峰”較容易。因此，可通過將高維空間樣本投影到不同的一維空間ui上，xi=uiTY；然后，在此一維空間上估計邊緣概率密度p(xi)，并在此概率密度上尋找各個峰，并確定每個峰的范圍（即每個聚類），各個聚類的分解面與該坐標軸ui垂直，交點則是兩個峰值之間的最小點。稱為投影法。投影法的主要問題：一：如何設計合適的坐標系統(tǒng)（即投影方向）二、如何設計直方圖（計算邊緣概率密度）2023/2/1哈爾濱工業(yè)大學電信院宿富林115一、如何設計直方圖1）將數(shù)據xi(k)=uiTY(k)按大小排列2）確定直方圖上的單位間隔長度L3）根據L將數(shù)據xi(k)分成不同區(qū)間，統(tǒng)計；落在每個區(qū)間內的樣本數(shù)。K

則pi(k)=K/NN:總的樣本數(shù)2023/2/1哈爾濱工業(yè)大學電信院宿富林1162023/2/1哈爾濱工業(yè)大學電信院宿富林117二：如何設計合適的坐標系統(tǒng)目前還沒有合適的準則用于確定坐標系。一種啟發(fā)式的辦法是使待分類的樣本在某個坐標軸方向具有最大的分散性，可以采用K-L變換方法。具體說來是用混合樣本協(xié)方差矩陣作為K-L變換的產生矩陣，找到其本征值，并按大小排序。對此混合樣本來說，對應最大本征值的本征向量，離散程度最大，預期能發(fā)現(xiàn)明顯的峰值。但是，在這些方向的投影，并不能保證分出各個聚類。2023/2/1哈爾濱工業(yè)大學電信院宿富林118可以分出各個聚類不能分出各個聚類2023/2/1哈爾濱工業(yè)大學電信院宿富林119投影法的具體算法步驟1：計算樣本協(xié)方差矩陣具有最大本征值的本征向量Uj，把數(shù)據投影到Uj軸上。步驟2：用直方圖方法求數(shù)據的邊緣概率密度函數(shù)。步驟3：在直方圖的峰值間求最小值，在這些最小點作垂直于Uj的超平面把數(shù)據劃分為若干個聚類。步驟4：如果在這個軸上沒有這樣的最小值，則用下一個最大本征值對應的本征向量重復以上過程。步驟5：對每個得到的子集(聚類)重復上述過程，直到每個集不能再分(為單峰)為止。2023/2/1哈爾濱工業(yè)大學電信院宿富林1205.2.2單峰子集分離的其它方法基于對稱集性質的單峰子集分離法單峰子集分離的迭代算法（略）2023/2/1哈爾濱工業(yè)大學電信院宿富林1215.3類別分離的間接方法

----聚類方法聚類方法：不通過對概率密度函數(shù)作出估計而直接按樣本間的相似性，或彼此間在特征空間中的距離遠近進行分類。

如何聚類取決于聚類準則，以使某種聚類準則達到極值為最佳。兩類對數(shù)據集進行聚類的方法：迭代的動態(tài)聚類算法非迭代的分級聚類算法2023/2/1哈爾濱工業(yè)大學電信院宿富林1225.3.1動態(tài)聚類方法動態(tài)聚類方法的任務是將數(shù)據集劃分成一定數(shù)量的子集，子集數(shù)目在理想情況現(xiàn)能體現(xiàn)數(shù)據集比較合理的劃分。問題:

1．怎樣才能知道該數(shù)據集應該劃分的子集數(shù)目

2．如果劃分數(shù)目已定，則又如何找到最佳劃分

由于優(yōu)化過程是從不甚合理的劃分到“最佳”劃分，是一個動態(tài)的過程，故這種方法稱為動態(tài)聚類方法。2023/2/1哈爾濱工業(yè)大學電信院宿富林1235.3.1.1動態(tài)聚類方法3個要點1.選定某種距離度量作為樣本間的相似性度量；

2.確定樣本合理的初始分類，包括代表點的選擇，初始分類的方法選擇等。3.確定某種評價聚類結果質量的準則函數(shù)，用以調整初始分類直至達到該準則函數(shù)的極值。

2023/2/1哈爾濱工業(yè)大學電信院宿富林1245.3.1.2C-均值算法

也叫K-均值算法1.準則函數(shù)—誤差平方和準則這個準則函數(shù)是以計算各類樣本到其所屬類均值點誤差平方和為準則。若各類均值表示成

誤差平方和準則可表示成

最佳的聚類是使Jc為最小的分類。這種類型的聚類通常稱為最小方差劃分。2023/2/1哈爾濱工業(yè)大學電信院宿富林1252.樣本集初始劃分初始劃分的一般作法是（1）先選擇一些代表點作為聚類的核心（2）把其余的樣本按某種方法分到各類中去

2023/2/1哈爾濱工業(yè)大學電信院宿富林126（1）代表點的幾種選擇方法(a)憑經驗選擇代表點。根據問題的性質，用經驗的辦法確定類別數(shù)，從數(shù)據中找出從直觀上看來是比較合適的代表點。(b)將全部數(shù)據隨機地分為C類計算各類重心，將這些重心作為每類的代表點。（c）用前C個樣本作為代表點

2023/2/1哈爾濱工業(yè)大學電信院宿富林127(d)“密度”法選擇代表點?！懊芏取保簩γ總€樣本確定大小相等的鄰域（如同樣半徑的超球體），統(tǒng)計落在其鄰域的樣本數(shù)，稱為該點“密度”。確定一個距離d選“密度”為最大的樣本點作為第一個代表點；然后，找次高“密度”的樣本點作為第二個代表點；第2個代表點離第1個代表點的距離需大于d。依次選擇其它代表點。其離選定的代表點的距離應大于d。使用這種方法的目的是避免代表點過分集中在一起。

2023/2/1哈爾濱工業(yè)大學電信院宿富林128(e)從c-1個聚類劃分問題的解中產生C聚類劃分問題的代表點首先，將所有樣本集看作一個聚類，計算其總均值，然后找與該均值相距最遠的點，由該點及原均值點構成2聚類的代表點。其次，依同樣方法，對已有(c-1)個聚類代表點(由(c-1)個類均值點組成)找一樣本點，使該樣本點距所有這些均值點的最小距離為最大，這樣就得到了第c個代表點。代表點的選擇會影響迭代結果。因為迭代得到的結果往往是局部最優(yōu)而非全局最優(yōu)。2023/2/1哈爾濱工業(yè)大學電信院宿富林129(2)初始分類方法(a)對選定的代表點按距離最近的原則將樣本劃屬各代表點代表的類別。(b)在選擇樣本的點集后，將樣本按順序劃歸距離最近的代表點所屬類，并立即修改代表點參數(shù)，用樣本歸入后的重心代替原代表點。因此代表點在初始劃分過程中作了修改。

2023/2/1哈爾濱工業(yè)大學電信院宿富林130(c)一種既選擇代表點又同時確定初始分類的方法規(guī)定一閾值d，選w1={y1}計算樣本y2與y1的距離D(y2,y1)，如其小于d，則y2歸入w1；否則建立新的類別w2={y2}。當輪到樣本yj時，已有了K類即，而每類第一個入類樣本分別為y1,y2,…,yk（作為每類的代表點），則計算D(yi,yj),i=1,2,…,k；若有D(yi,yj)>d（對所有的i，i＝1,…，k），則建立新類。否則將yj歸入與y1,y2,…,yk距離最近的類別中。重復上一步，直至所有樣本分類

2023/2/1哈爾濱工業(yè)大學電信院宿富林131(d)標準化特征求和量化方法：i)先將數(shù)據標準化ii)若yij

表示標準化后第i個樣本的第j個特征量，令：iii)求出SUM(i)的最大值與最小值

MA=max{SUM(i)},MI=min{SUM(i)}iv）如果欲將樣本劃分為c類，則對每個i計算

v)如所得結果非整數(shù)，則找到其最近整數(shù)K，將第i個樣本歸入第K類

2023/2/1哈爾濱工業(yè)大學電信院宿富林1323.迭代計算c-均值算法的迭代計算過程在原理上與梯度下降法是一樣的，即以使準則函數(shù)值下降為準則。但是由于c-均值算法的準則函數(shù)值由數(shù)據劃分的調整所決定，因此只能通過逐個數(shù)據從某個子集轉移到另一子集計算準則函數(shù)值是否降低為準則。

2023/2/1哈爾濱工業(yè)大學電信院宿富林133對劃分的修改規(guī)則如果原屬Гk

中的一個樣本y從Гk

移入Гj

時，它會對誤差平方和產生影響,Гk類在抽出樣本y后其相應均值為而樣本y新加盟的Гj

集合均值

2023/2/1哈爾濱工業(yè)大學電信院宿富林134由于y的移動只影響到k與j這兩類的參數(shù)改動，因此，計算Jc值的變動只要計算相應兩類誤差平方和的變動即可，此時

總誤差變化：如果則即將樣本y從Гk

移入至Гj

就會使誤差平方總和Jc減小，它表明樣本變動是合乎準則要求的2023/2/1哈爾濱工業(yè)大學電信院宿富林135算法(1)選擇某種方法把樣本分成C個聚類的初始劃分，計算每個聚類的均值m1,…,mc和Jc(2)選擇一個備選樣本y，設其在wi中(3)若Ni=1，則轉(2)（樣本只有1個，不移出），否則繼續(xù)下一步。(4)計算

2023/2/1哈爾濱工業(yè)大學電信院宿富林136(5)對于所有的j，若ek≤ej（表明ek<ei）則將y從wi移到wk中（否則，ei<ei,不用移）(6)重新計算mi和mk，并修改Jc。(7)若連續(xù)迭代N次(即所有樣本都運算過)Jc不變，則停止，否則轉到2。

2023/2/1哈爾濱工業(yè)大學電信院宿富林137確定類別數(shù)的實驗方法上述C—均值算法都是在類別c已知條件下進行的。在類別數(shù)未知情況下，可以假設類別數(shù)是逐步增加的，準則函數(shù)隨c的增加而單調地減小?？蛇x擇平緩時轉折處的C值。2023/2/1哈爾濱工業(yè)大學電信院宿富林1385.3.1.3ISODATA算法

C—均值算法比較簡單，但它的自我調整能力也比較差。這主要表現(xiàn)在類別數(shù)不能改變，受代表點初始選擇的影響也比較大。全稱‘迭代自組織數(shù)據分析技術’（IterativeSelf-OrganizingData

AnalysisTechniqueAlgorithm）。ISODATA算法的功能與C—均值算法相比的改進。

1.不是每調整一個樣本的類別就重新計算一次各類均值（逐個樣本修正），而是每次把全部樣本都調整完畢后再重新計算樣本均值（成批樣本修正）。2.考慮了類別的合并與分裂，因而有了自我調整類別數(shù)的能力。從而可以得到較為合理的類別數(shù)。2023/2/1哈爾濱工業(yè)大學電信院宿富林139合并主要發(fā)生在某一類內樣本個數(shù)太少的情況，或兩類聚類中心之間距離太小的情況。為此設有最小類內樣本數(shù)限制N，以及類間中心距離參數(shù)L。若出現(xiàn)兩類聚類中心距離小于L或樣本數(shù)小于N的情況，可將此兩類合并分裂則主要發(fā)生在某一類別的某分量出現(xiàn)類內方差過大的現(xiàn)象，因而宜分裂成兩個類別，以維持合理的類內方差。

給出一個對類內分量方差的限制參數(shù)S，用以決定是否需要將某一類分裂成兩類。2023/2/1哈爾濱工業(yè)大學電信院宿富林140ISODATA算法的步驟步驟1：確定控制參數(shù)及設置代表點由于算法有自我調整的能力，因而需要設置若干個控制用參數(shù)。需確定的控制參數(shù)為：

K：聚類期望數(shù)；

QN：一個聚類中的最少樣本數(shù)；

θs：標準偏差控制參數(shù)，用于控制分裂；

θc

：類間距離控制參數(shù)，用于控制合并；

L：每次迭代允許合并的最大聚類對數(shù)；

I：允許迭代的次數(shù)。

設初始聚類數(shù)為c及聚類中心mi,i=1,2,…,C。

2023/2/1哈爾濱工業(yè)大學電信院宿富林141步驟2(分類)

對所有樣本，按給定的c個聚類中心，以最小距離進行分類，即

若

步驟3(撤消類內樣本數(shù)過小類別)

若有任何一個類，其樣本數(shù)，則舍去該類，令c＝c-1，將該類中原樣本分配至其它類；步驟4（重新計算均值向量）

2023/2/1哈爾濱工業(yè)大學電信院宿富林142步驟5(計算類內平均距離)

每類各樣本離開均值的平均距離

步驟6(計算整個樣本集偏離均值的平均距離)

j2023/2/1哈爾濱工業(yè)大學電信院宿富林143步驟7(入口選擇)

如這是最后一次迭代(取決于I)，則轉步驟11，并設置θc=0，防止合并發(fā)生。

如果c<K/2，則轉向步驟8，執(zhí)行分裂步驟；

如果c≥2K或是偶數(shù)次迭代，則轉向步驟11，執(zhí)行合并步驟步驟8(求各類內各分類標準偏差)

對每個聚類j，求其標準偏差

2023/2/1哈爾濱工業(yè)大學電信院宿富林144步驟9(求每類具有最大標準偏差的分量)

步驟10(分裂計算步驟)

若對任一個有，并且有

(a)且，或有(b)C<k/2則把wj分裂成兩個聚類，其中心相應為M+

j與M-

j

，把原來的Mj取消，且令c＝c+1，由于M+

j與M-

j設置不當將會導致影響到其它類別，可按以下步驟計算：

2023/2/1哈爾濱工業(yè)大學電信院宿富林145(a)給定一k值，0＜k＜1；

(b)令

(c)其中k值應使wj中的樣本到M+

j與M-

j的距離不同，但又應使wj中的樣本仍然在分裂后的新樣本類中。步驟11(計算類間聚類中心距離)

i類與j類的類間距離

2023/2/1哈爾濱工業(yè)大學電信院宿富林146步驟12(列出類間距離過近者)

比較Dij

與θc

并將小于θc

的Dij按上升次序排列

該隊列最大個數(shù)是控制合并對數(shù)的參數(shù)L步驟13(執(zhí)行合并)

從類間距離最小的兩類開始執(zhí)行合并過程，此時需將miL與miL合并，得

2023/2/1哈爾濱工業(yè)大學