模式識別第一章Clustering

第一章

聚類分析1.1聚類分析的相關(guān)概念1.2模式相似性的測度和聚類準(zhǔn)則1.3基于試探的聚類搜索算法1.4分級（系統(tǒng)）聚類法1.5動態(tài)聚類法1.6聚類結(jié)果的評價（1）相似性和距離聚類：模式之間具有一定的相似性，這既表現(xiàn)在實(shí)物的顯著特征上，也表現(xiàn)在經(jīng)過抽象以后特征空間內(nèi)的特征向量的分布狀態(tài)上。一個樣本的特征向量相當(dāng)于特征空間中的一點(diǎn)，整個模式樣本集合的特征向量可以看成特征空間的一些點(diǎn)，點(diǎn)之間的距離函數(shù)可以作為模式相似性的度量，并以此作為模式的分類依據(jù)。§1.1距離聚類的概念§1.1距離聚類的概念

定義對一批沒有標(biāo)出類別的模式樣本集，按照樣本之間的相似程度分類，相似的歸為一類，不相似的歸為另一類，這種分類稱為聚類分析，也稱為無監(jiān)督分類。把整個模式樣本集的特征向量看成是分布在特征空間中的一些點(diǎn)，點(diǎn)與點(diǎn)之間的距離即可作為模式相似性的測量依據(jù)。

聚類分析是按不同對象之間的差異，根據(jù)距離函數(shù)的規(guī)律（大小）進(jìn)行模式分類的?！?.1距離聚類的概念

§1.1距離聚類的概念聚類分析的有效性

聚類分析方法是否有效，與模式特征向量的分布形式有很大關(guān)系。若向量點(diǎn)的分布是一群一群的，同一群樣本密集（距離很近），不同群樣本距離很遠(yuǎn)，則很容易聚類；若樣本集的向量分布聚成一團(tuán)，不同群的樣本混在一起，則很難分類；對具體對象做聚類分析的關(guān)鍵是選取合適的特征。特征選取得好，向量分布容易區(qū)分，選取得不好，向量分布很難分開?！?.1距離聚類的概念

(2)特征分量個數(shù)（特征選擇的維數(shù)）

如果特征空間的維數(shù)較多，也就是表征模式的特征向量的維數(shù)較多，也就是特征選取較多，這都會增加以距離作為聚類分類的工作量。因此我們在特征提取的過程中應(yīng)該根據(jù)模式的具體特點(diǎn)，盡量合理的抽取較好反映模式典型的特征。

[降維方法]…….§1.1距離聚類的概念(3)特征的表示數(shù)值表示通常特征可用數(shù)值來表示，比如即便是性別特征是男和女，但是我們都可以用0和1來進(jìn)行表示，如身份證號碼的最后一個數(shù)。但是具體的對象，數(shù)字的取值要求不一樣，如有的可以是連續(xù)的，身高、體重等。有的是分級量化的。如學(xué)分2分、3分等，有的是二值化的。如前面說的M、F?！?.1距離聚類的概念量綱選擇對同一個分類樣本總體來說，他們每個特征都應(yīng)該采用同一個規(guī)則進(jìn)行標(biāo)識量化。同時特征反映了模式的某一個物理量，它與一定的單位量綱聯(lián)系在一起的，量綱不同，會影響到數(shù)值的大小，如，說某人身高170cm，也可以說1.7m。在取值的時候要特別注意。

量綱對分類的影響（圖例）§1.1距離聚類的概念兩類模式分類的實(shí)例：一攤黑白圍棋子選顏色作為特征進(jìn)行分類，用“1”代表白，“0”代表黑，則很容易分類；選大小作為特征進(jìn)行分類，則白子和黑子的特征相同，不能分類（把白子和黑子分開）?！?.2模式相似性的測度和聚類準(zhǔn)則

1.2.1相似性的測度已知兩個樣本

Xi=(Xi1,Xi2,Xi3,…,Xin)T

Xj=(Xj1,Xj2,Xj3,…,Xjn)T（1）歐氏距離:表征了兩個模式樣本在特征空間中的歐幾里得距離，需要特別注意的是Xi和Xj的量綱應(yīng)該一致，如果用歐式距離作為判斷多個樣本之間的距離時候，更應(yīng)該有一致的物理量綱，這樣才有可比性。

當(dāng)m＝2時，明氏距離就是歐氏距離，當(dāng)m＝1時，就是街坊或絕對（cityblock)距離

（2）一般化的明氏距離切比雪夫距離

m趨向無窮大時明氏距離的極限情況（3）馬氏距離它表征了模式向量X與其均值向量m之間的距離平方，C是模式總體的協(xié)方差，馬氏距離將協(xié)方差考慮進(jìn)來，排除了樣本之間的相關(guān)性。當(dāng)協(xié)方差為單位矩陣時，馬氏距離和歐氏距離相同。馬氏距離與歐氏距離相比，就中間多了一項(xiàng)。（4）角度相似性函數(shù)

表征了模式向量Xi、Xj之間夾角的余弦，反映了幾何上的相似性，當(dāng)坐標(biāo)系旋轉(zhuǎn)或者尺度變換（放大or縮小），Cij均保持不變，這有點(diǎn)類似我們中學(xué)學(xué)的相似三角形的特性。（關(guān)于坐標(biāo)變換，如仿射變換，雙線性變換，平方變換、雙平方變換等請參見有關(guān)文獻(xiàn)）x1x2x1x2x3（5）Tanimoto測度

其中x和z的分量用二值來表示，0表示不具有某種特征，1表示具有某種特征。(6)相關(guān)系數(shù)為xixj（類或者維）的均值1.2.2聚類準(zhǔn)則的確定方法（1）

試探方法

依據(jù)經(jīng)驗(yàn)選擇測度和閾值來判別分類，并可以選擇一定的訓(xùn)練樣本來檢驗(yàn)測度和閾值的可靠程度。 憑直觀感覺，針對實(shí)際問題定義一種相似性測度的閾值，然后按最近鄰規(guī)則指定某些模式樣本屬于某一個聚類類別。例如對歐氏距離，它反映了樣本間的近鄰性，但將一個樣本分到不同類別中的哪一個時，還必須規(guī)定一個距離測度的閾值作為聚類的判別準(zhǔn)則（2）聚類準(zhǔn)則函數(shù)法依據(jù)：由于聚類是將樣本進(jìn)行分類以使類別間可分離性為最大，因此聚類準(zhǔn)則應(yīng)是反映類別間相似性或分離性的函數(shù)；由于類別是由一個個樣本組成的，因此一般來說類別的可分離性和樣本的可分離性是直接相關(guān)的；可以定義聚類準(zhǔn)則函數(shù)為模式樣本集(x)和模式類別(Sj,j=1,2,…,c)的函數(shù)，從而使聚類分析轉(zhuǎn)化為尋找準(zhǔn)則函數(shù)極值的最優(yōu)化問題?！?.3基于試探的聚類搜索算法1.3.1按最鄰近規(guī)則的簡單試探法

1.3.2最大最小距離算法NOTE:在以后的算法中用于描述兩個樣本之間距離，如果沒有特殊說明，都是指歐式距離。類與類之間的距離則具體指定。1.3.1按最鄰近規(guī)則的試探法

1.3.1按最鄰近規(guī)則的試探法討論這種方法的優(yōu)點(diǎn)：計(jì)算簡單，若模式樣本的集合分布的先驗(yàn)知識已知，則可獲得較好的聚類結(jié)果。在實(shí)際中，對于高維模式樣本很難獲得準(zhǔn)確的先驗(yàn)知識，因此只能選用不同的閾值和起始點(diǎn)來試探，因此這種方法缺點(diǎn)：依賴第一個聚類中心的位置，且類中心位置隨機(jī)待分類模式樣本的排列次序距離閾值T的大小樣本分布的幾何性質(zhì)1.3.1按最鄰近規(guī)則的試探法距離閾值T對聚類結(jié)果的影響1.3.2最大最小距離算法

基本思想：以試探類間歐氏距離為最大作為預(yù)選出聚類中心的條件。算法過程描述：先按照距離最小最大的方法預(yù)選出聚類中心，在按照按最鄰近規(guī)則將模式分類到聚類中心。

以例子來說明具體步驟：

1.3.2最大最小距離算法[算法（實(shí)例）]x1x2x3x4x5x6x7x8x9x10x10x20x30x40x50x60x70x80x90x100x1(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);算法性能分析：算法復(fù)雜度增加，在選聚類中心過程中消耗較大的資源。

這種方法缺點(diǎn)：依賴第一個聚類中心的位置，且類中心位置隨機(jī)樣本分布的幾何性質(zhì)§1.4系統(tǒng)聚類分類法

基本思想 將模式樣本按距離準(zhǔn)則逐步分類，類別由多到少，直到獲得合適的分類要求為止。數(shù)據(jù)結(jié)構(gòu)：進(jìn)行聚類合并的一個關(guān)鍵就是每次迭代中形成的聚類之間以及它們和樣本之間距離的計(jì)算，采用不同的距離函數(shù)會得到不同的計(jì)算結(jié)果。主要的距離計(jì)算準(zhǔn)則：

最短距離、最長距離、中間距離、重心法、類平均距離等

§1.4系統(tǒng)聚類分類法(續(xù))最短距離

DH、K＝H類中的所有樣本與K類中所有樣本之間最小的距離。最長距離DH、K＝H類中的所有樣本與K類中所有樣本之間最大的距離。中間距離

重心法類平均距離遞推公式：…………距離不同，則結(jié)果可能不同

§1.4系統(tǒng)聚類分類法(續(xù))[舉例]設(shè)有6個五維模式樣本如下，按最小距離準(zhǔn)則進(jìn)行聚類分析：x1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,0§1.4系統(tǒng)聚類分類法(續(xù))算法過程描述：

Step1:每個樣本看成一類：

說明：（1）距離矩陣元的值是類與類之間的距離，距離的定義有多種。（2）距離矩陣，是對稱矩陣。對角上線的元值表示同類之間的距離，即為0。000000x1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,0Step2:合并距離最小的兩類，產(chǎn)生新的距離矩陣

說明：距離矩陣中選擇距離最小的，如果有相同的可以任選其中一個，要忽略對角線上的元素。00000Step3：繼續(xù)合并，計(jì)算新的距離矩陣

說明：合并類的距離計(jì)算

應(yīng)該符合距離的運(yùn)算

規(guī)則。如，距離反映

的是兩類的重心距離，

那么合并后，應(yīng)該仍然

反映的重心的距離。Step4：繼續(xù)合并，直到收斂

說明：算法的收斂條件判斷準(zhǔn)則的確定。

0000000§1.4系統(tǒng)聚類法(續(xù))系統(tǒng)聚類的 樹狀表示§1.5動態(tài)聚類分類法

基本思想首先選擇若干個樣本點(diǎn)作為聚類中心，再按某種聚類準(zhǔn)則（通常采用最小距離準(zhǔn)則）使樣本點(diǎn)向各中心聚集，從而得到初始聚類；然后判斷初始分類是否合理，若不合理，則修改分類；如此反復(fù)進(jìn)行修改聚類的迭代算法，直至合理為止1.5.1C－均值算法1.5.2ISODATA算法（迭代自組織的數(shù)據(jù)分析方法）1.5.1C－均值算法思想：基于使聚類性能指標(biāo)最小化，所用的聚類準(zhǔn)則函數(shù)是聚類集中每一個樣本點(diǎn)到該類中心的距離平方之和，并使其最小化。1.5.1C－均值算法目標(biāo)：將對象分成C個“最好”的非空的子集基本C均值算法（第二版P237，第三版P193）每次調(diào)整一個樣本就需要重新計(jì)算一次類的均值改進(jìn)：第一步：選C個初始聚類中心，任選C個樣本作為初始聚類中心第二步：計(jì)算每個類的平均值作為中心點(diǎn).

第三步：重新將對象劃分到離它最近的聚類

第四步：重新計(jì)算聚類的中心，重新劃分類，直到所有的類中心都不再發(fā)生變化.1.5.1C-均值算法[舉例]對如圖模式 樣本用C-均 值算法進(jìn)行 分類1.5.1C－均值算法說明：（1）C是指需要分成C類，均值是指每類的中心,就是該類所有樣本的平均值，不一定就有某個樣本在這個位置上。(2)算法的收斂性判別：前后兩次迭代的結(jié)果，也就是每迭代分類后，分類都是一樣的，此時停止。（3）C值和初始聚類中心對分類的結(jié)果影響很大。通常需要其它的算法來確定這兩個的選取。

1.5.1C-均值算法（4）C的選擇： 上面所說的是C已知的情況，如果C未知，則我們把類別數(shù)依次增加：C=1，C=2，C=3。。。，分別適用該算法。顯然準(zhǔn)則函數(shù)Je隨著類別增加而減小。我們可以選擇拐點(diǎn)處的C作為我們的類別數(shù)。1.5.1C-均值算法討論

C-均值算法的結(jié)果受如下選擇的影響：所選聚類的數(shù)目聚類中心的初始分布模式樣本的幾何性質(zhì)讀入次序在實(shí)際應(yīng)用中，需要試探不同的C值和選擇不同的聚類中心的起始值。如果模式樣本可以形成若干個相距較遠(yuǎn)的孤立的區(qū)域分布，一般都能得到較好的收斂效果。C-均值算法比較適合于分類數(shù)目已知的情況。1.5.2ISODATA算法IterativeSelf-OrganizingDataAnalysisTechniqueAlgorithm 迭代自組織數(shù)據(jù)分析算法1.5.2ISODATA算法1.考慮了類別的合并與分裂，因而有了自我調(diào)整類別數(shù)的能力。合并主要發(fā)生在某一類內(nèi)樣本個數(shù)太少的情況，或兩類聚類中心之間距離太小的情況。為此設(shè)有最小類內(nèi)樣本數(shù)限制，以及類間中心距離參數(shù)。若出現(xiàn)兩類聚類中心距離小于的情況，可考慮將此兩類合并。

分裂則主要發(fā)生在某一類別的某分量出現(xiàn)類內(nèi)方差過大的現(xiàn)象，因而宜分裂成兩個類別，以維持合理的類內(nèi)方差。給出一個對類內(nèi)分量方差的限制參數(shù)，用以決定是否需要將某一類分裂成兩類。1.5.2ISODATA算法2.由于算法有自我調(diào)整的能力，因而需要設(shè)置若干個控制用參數(shù)，如聚類數(shù)期望值K、每次迭代允許合并的最大聚類對數(shù)L、及允許迭代次數(shù)I等。1.5.2ISODATA算法算法描述：

Ref第二版P238，第三版P196說明：基本步驟： (i)選擇某些初始值—可選不同指標(biāo)，也可在迭代運(yùn)算過程中人為修改，以使所有模式樣本按指標(biāo)分配到各個中心中去。 步驟1 ~2（ii）計(jì)算各類別和其中樣本的距離函數(shù)等指標(biāo) 步驟4~6（iii）判斷分裂、合并以及迭代運(yùn)算等步驟 步驟7(iv)分裂處理 步驟8~10（v）合并處理 步驟11~13(vi)進(jìn)行迭代運(yùn)算，重新計(jì)算各項(xiàng)指標(biāo)，判別聚類結(jié)果是否符合要求。 步驟14共計(jì)6大步。基本步驟都不會變化。對于該算法，不同的文獻(xiàn)上對其具體6個步驟的描述略有差異，如，計(jì)算各個參數(shù)的值，判斷分裂和合并的標(biāo)準(zhǔn)依據(jù)。1.5.3基于核的動態(tài)聚類方法前面的方法使用均值作為類代表點(diǎn)，這種方法適用于各個分量方差接近或者相等的情況為了解決方差相差比較大的情況，可以適用核函數(shù)方法：

Kj=K(a,Vj)

相似性度量Δ(y,Kj)當(dāng)核函數(shù)不能確定形式或者不能簡單用函數(shù)來表示，可