《模式識別原理與應(yīng)用》課件第6章

第6章聚類分析6.1

模式相似性測度與聚類準(zhǔn)則6.2

基于試探的聚類算法6.3層次聚類法6.4動態(tài)聚類法6.5分解法習(xí)題6.1模式相似性測度與聚類準(zhǔn)則

聚類分析是以模式相似性為基礎(chǔ),按照某種聚類準(zhǔn)則進(jìn)行判決。本節(jié)主要介紹模式相似性測度與聚類準(zhǔn)則。6.1.1模式相似性測度分類在實際工作中經(jīng)常出現(xiàn),例如,在古生物研究中,根據(jù)骨骼的形狀和大小對它們進(jìn)行分類;在地質(zhì)勘探中,根據(jù)礦石標(biāo)本的物探和化探指標(biāo)對標(biāo)本進(jìn)行分類,等等。其中,骨骼的形狀和大小、標(biāo)本的物探和化探指標(biāo)是描述樣本特征的具體參數(shù),是分類的依據(jù)。根據(jù)測量尺度的不同,模式特征的數(shù)值化測量結(jié)果主要分為以下三種類型:

(1)物理量:特征用連續(xù)的量來表示,如長度、重量、壓力等。

(2)次序量:特征度量沒有明確的數(shù)量表示,只有次序關(guān)系。例如,評價茶葉的質(zhì)量分成優(yōu)、良、中、差四等,其中,有次序關(guān)系,沒有數(shù)量表示。

(3)名義量:特征度量既沒有數(shù)量表示也沒有次序關(guān)系。例如,電路中的開和關(guān);醫(yī)療診斷中的“+”和“-”;天氣中的晴天和雨天,等等。為了對模式進(jìn)行分類,需要定義相似性測度來度量各模式之間的相似性和差異性。一種方法是將每一個樣本看成m維特征空間的一個點,并在該空間定義距離,距離較近的點歸為一類,距離較遠(yuǎn)的點劃分為不同的類。另一種方法是利用相似系數(shù),特征越接近的樣本之間的相似系數(shù)越大(接近于1),把它們歸為一類;反過來,彼此無關(guān)的樣本之間的相似系數(shù)接近于0,把它們劃分為不同的類。在聚類分析中正確選擇距離與相似系數(shù)是非常重要的,它直接影響到分類的效果。

1.距離用dij表示第i個樣本與第j個樣本之間的距離,一般要求距離滿足三個條件(即距離三公理):

(1)非負(fù)性:dij≥0(i,j),當(dāng)且僅當(dāng)?shù)趇個樣本與第j個樣本的各個特征相同時,dij=0;

(2)對稱性:dij=dji(i,j);

(3)三角不等式:(6-1)在模式識別中定義的有些距離并不滿足“三角不等式”,只是在廣義的角度上也稱它為距離。在有些場合,“三角不等式”加強(qiáng)為(6-2)第5章已經(jīng)給出了幾種常用的距離,包括歐幾里德(Euclidean)距離、加權(quán)歐幾里德距離、漢明(Haming)距離、馬氏(Mahalanobis)距離、明可夫斯基(Minkowsky)距離和切比雪夫(Chebyshev)距離等。

2.相似系數(shù)用cij表示向量yi與yj的相似系數(shù),一般規(guī)定:

(1)cij=±1yi=ayj,a≠0是一常數(shù);

(2)|cij|≤1,對一切i,j;

(3)cij=cji,對一切i,j,其中,|cij|越接近于1,yi與yj的關(guān)系越密切。當(dāng)特征用連續(xù)的量來表示時,常用的相似系數(shù)有如下幾種。

1)夾角余弦夾角余弦是受相似形的啟發(fā)而產(chǎn)生的。向量(xi1,xi2,…,xin)T與(xj1,xj2,…,xjn)T之間的夾角余弦的定義為(6-3)

2)相關(guān)系數(shù)相關(guān)系數(shù)是將數(shù)據(jù)標(biāo)準(zhǔn)化后的夾角余弦,即(6-4)其中,為第k個分量的平均值(k=1,2,…,n)?？梢越柚谙嗨葡禂?shù)來定義距離,例如:(6-5)

3)指數(shù)相似系數(shù)指數(shù)相似系數(shù)定義為(6-6)其中,為相應(yīng)分量的方差。指數(shù)相似系數(shù)不受量綱變化的影響。

4)特征向量的各分量為非負(fù)時的幾種相似系數(shù)當(dāng)特征向量的各分量非負(fù)時,還有下列幾種相似系數(shù):(6-7)(6-8)(6-9)

5)列聯(lián)系數(shù)和關(guān)聯(lián)系數(shù)對于名義量,它們之間的相似系數(shù)通過列聯(lián)表來定義。設(shè)名義量yi取值是t1,t2,…,tp,yj取值是r1,r2,…,rq,用nkl表示yi取tk、yj取rl的樣本數(shù),列成表6-1的形式,稱為列聯(lián)表。令(6-10)其中(6-11)(6-12)(6-13)利用χ2可以定義名義量之間的相似系數(shù):列聯(lián)系數(shù)(6-14)關(guān)聯(lián)系數(shù)(6-15)(6-16)(6-17)表6-1列聯(lián)表6.1.2聚類準(zhǔn)則在模式分類中,可以有多種不同的聚類方法,將未知類別的N個樣本劃分到m類中去,從而,需要確定一種聚類準(zhǔn)則來評價各種聚類方法的優(yōu)劣。事實上,聚類的優(yōu)劣只是就某種評價準(zhǔn)則而言的,很難找到對各種準(zhǔn)則均表現(xiàn)優(yōu)良特性的聚類方法。

聚類準(zhǔn)則的確定主要有兩種方式:

(1)試探方式。憑直觀和經(jīng)驗,針對實際問題給定一種模式相似性測度的閾值,按最近鄰規(guī)則指定待分類樣本屬于某一類別。例如,以歐氏距離作相似性的度量,將一個樣本分到某一類時,憑直觀和經(jīng)驗規(guī)定一個距離閾值作為聚類的判別準(zhǔn)則。

(2)聚類準(zhǔn)則函數(shù)法。定義一種聚類準(zhǔn)則函數(shù)J,其函數(shù)值與樣本的劃分有關(guān),當(dāng)J取得極值時,就認(rèn)為得到了最佳劃分。常用的聚類準(zhǔn)則函數(shù)為誤差平方和準(zhǔn)則與類間距離和準(zhǔn)則。假設(shè)有N個樣本,在某種相似性測度的準(zhǔn)則下屬于類ω1,ω2,…,ωm,類ωi中有Ni個樣本。

1.誤差平方和準(zhǔn)則誤差平方和準(zhǔn)則也可以稱為類內(nèi)距離準(zhǔn)則,是一種簡單而又應(yīng)用廣泛的聚類準(zhǔn)則。類ωi的均值為(6-18)誤差平方和定義為(6-19)

J是樣本與聚類中心的函數(shù),表示各樣本到其被劃歸類別的中心的距離之平方和。對應(yīng)一種劃分,可求得一個誤差平方和J。以誤差平方和作為準(zhǔn)則時,目的就是要找到使J值最小的那種劃分。誤差平方和準(zhǔn)則適用于同類樣本比較密集,各類樣本數(shù)目相差不大,且類間距離較大的情況。當(dāng)各類樣本數(shù)相差很大且類間距離較小時,采用誤差平方和準(zhǔn)則,就有可能將樣本數(shù)多的一類拆成兩類或多類,從而出現(xiàn)錯誤聚類。

2.類間距離和準(zhǔn)則

全部樣本的均值μ為(6-20)類間距離和定義為(6-21)加權(quán)的類間距離和定義為(6-22)對應(yīng)一種劃分，可求得一個類間距離和。類間距離和準(zhǔn)則是找到使類間距離和達(dá)到最大的那種劃分。6.2基于試探的聚類算法確定一種聚類準(zhǔn)則后,每一種分類方法對應(yīng)于一個J值,其中使J取得極值的分類,就被認(rèn)為是最佳分類。這種處理方式的計算量太大,可以對某些關(guān)鍵性的參數(shù)進(jìn)行試探性地選取,使聚類準(zhǔn)則函數(shù)達(dá)到最優(yōu),這類方法可稱為基于試探的聚類算法。6.2.1基于最近鄰規(guī)則的試探法設(shè)待分類樣本集為{x1,x2,…,xN},按最近鄰規(guī)則進(jìn)行聚類,算法具體步驟如下:

(1)選取任意一個樣本作為第一個聚類中心z1,例如,令ω1類的中心z1=x1,選定一非負(fù)的類內(nèi)距離閾值T。

(2)計算下一個樣本x2到z1的距離d21。若d21>T,則建立一新的聚類中心z2,且ω2類的中心z2=x2;若d21≤T,則認(rèn)為x2在以z1為中心的鄰域中,即x2屬于ω1類。

(3)假定已有m類的中心z1,z2,…,zm,計算尚未確定類別的樣本xi到m類中心zj(j=1,2,…,m)的距離dij。如果所有的dij均滿足dij>T,則建立一新的聚類中心zm+1,且ωm+1類的中心zm+1=xi;否則將xi劃分到距離其最近的聚類中心所代表的類中。

(4)檢查是否所有的樣本已經(jīng)確定類別,如果都已確定類別,則轉(zhuǎn)下一步;否則返回(3)。

(5)按照某種聚類準(zhǔn)則評價聚類結(jié)果,如果不滿意,則重新選取第一個聚類中心和類間距離閾值T,返回(2);如果滿意,則算法結(jié)束。這種方法的聚類結(jié)果與第一個聚類中心的選取、待分類樣本的排列次序、閾值T的大小以及樣本分布的幾何特性有關(guān)。圖6-1表示了距離閾值T的大小和初始聚類中心位置對聚類結(jié)果的影響。圖6-1距離閾值和初始類心對聚類結(jié)果的影響6.2.2最大最小距離聚類算法最大最小距離聚類算法是另一種簡單的試探法,以類間距離最大作為選取新的聚類中心的條件,以最小距離原則進(jìn)行樣本歸類。這種算法通常采用歐氏距離,算法具體步驟如下:

(1)選取任意一個樣本作為第一個聚類中心z1。

(2)選取距離z1最遠(yuǎn)的樣本作為第二個聚類中心z2。

(3)計算所有未作為聚類中心的樣本xi與z1、z2的距離di1,di2,并設(shè)di=min(di1,di2),若存在則建立第三個聚類中心z3,且z3=xl。其中:d(z1,z2)為z1與z2之間的距離;θ可用試探法取為一固定分?jǐn)?shù),例如,。(4)假定已有m個聚類中心z1,z2,…,zm,計算尚未作為聚類中心的各樣本xi到m類中心zj(j=1,2,…,m)的距離dij,并計算如果dJ>θ·d(z1,z2),則建立第m+1個聚類中心zm+1,且zm+1=xJ,并轉(zhuǎn)(4);否則轉(zhuǎn)下一步。

(5)將全部樣本按最近距離原則劃分到各類中。

(6)按照某種聚類準(zhǔn)則評價聚類結(jié)果,如果不滿意,則重新選取第一個聚類中心和θ值,返回(2);如果滿意,則算法結(jié)

【例6.1】

10個樣本數(shù)據(jù)如圖6-2所示,用最大最小距離聚類算法對樣本集分類。

解

(1)給定θ=1/2,選取任意一個樣本作為第一個聚類中心z1,令z1=x1。

(2)計算其他樣本到z1的距離,可得x6距離z1最遠(yuǎn),則建立第二個聚類中心z2=x6。

(3)計算所有未作為聚類中心的樣本與z1、z2的距離,根據(jù)最大最小距離聚類算法,得到第三個聚類中心z3=x7。

(4)判斷出不再有新的聚類中心,將全部樣本按最近距離原則劃分到各類中,得到{x1,x3,x4}為第一類,{x2,x6}為第二類,{x5,x7,x8,x9,x10}為第三類。

(5)通過直觀判斷,認(rèn)為本次分類結(jié)果比較合理,對樣本集的分類完成。圖6-2最大最小距離聚類算法示例6.3層次聚類法

6.3.1層次聚類法概述層次聚類法(HierarchicalClusteringMethod)又稱為系統(tǒng)聚類法,是一種常用的聚類方法。這種方法的基本思想是:首先將N個樣本各自看成一類,計算類與類之間的距離,選擇距離最小的一對合并成一個新類;計算新類和其他類之間的距離,再將距離最近的兩類合并;這樣每次減少一類,直至所有的樣本劃分成兩類為止,或者直到滿足分類要求。層次聚類算法的具體步驟如下:

(1)初始分類。假設(shè)有N個樣本,每個樣本自成一類,則有N類:G01,G02,…,G0N(Gki表示第k次合并時的第i類,此步k=0)。(2)計算各類之間的距離,得m×m維的距離矩陣Dk,m為類別個數(shù)(初始時m=N,k=0)。

(3)已求得距離矩陣Dk,找出Dk中類間距離最小的元素,如果它對應(yīng)著Gki和Gkj,則將類Gki與Gkj合并為一類,由此得到新的分類Gk+11,Gk+12,…,并令m=m－1,計算距離矩陣Dk+1。

(4)若Dk+1中類間距離最小值大于距離閾值T,則算法停止,所得分類即為聚類結(jié)果(或者,如果所有的樣本被聚成兩類,則算法停止);否則轉(zhuǎn)(3)。層次聚類法將樣本逐步聚類,類別由多到少。層次聚類算法的特點是在聚類的過程中類心不斷地調(diào)整,但樣本一旦劃到某個類以后就不會再改變了。6.3.2類與類之間的距離層次聚類算法中,需要計算各類之間的距離構(gòu)成距離矩陣。類與類之間的距離有許多定義的方法,例如可定義為兩類之間最近的距離,或者定義為兩類重心之間的距離等,采用不同的定義就產(chǎn)生了層次聚類的不同過程。下面介紹常用的8種類間距離定義方法。

1.最短距離法用dij表示樣本xi和樣本xj之間的距離,G1,G2,…表示類,定義類與類之間的距離為兩類相距最近的樣本之間的距離,用Dpq表示類Gp與類Gq的距離,則(6-23)若Gpq是Gp與Gq合并而得,則遞推可得Gi與Gpq的距離為(6-24)

2.最長距離法最長距離法就是類與類之間的距離用兩類樣本之間最遠(yuǎn)的距離來表示,即(6-25)若Gpq是Gp與Gq合并而得,則遞推可得Gi與Gpq的距離為(6-26)

3.中間距離法

設(shè)某一步將Gp與Gq合并為類Gpq,需要計算Gpq與任意一類Gi的距離。不失一般性,假設(shè)Diq>Dip。按最短距離法,Di,pq=Dip;按最長距離法,Di,pq=Diq。如圖6-3所示,三角形的三個邊是Dip、Diq

、Dpq,直觀上看,在Dip與Diq之間,選擇邊Dpq的中線為好。圖6-3中間距離法示意圖由初等幾何可知,中線長度的平方等于。若把這個中線長度作為類Gpq與類Gi之間的距離Di,pq,則有遞推公式:(6-27)

Di,pq介于最短距離和最長距離之間。由于式(6-27)中出現(xiàn)的全是距離的平方,為了計算方便,在層次聚類中,若采用中間距離法,一般用距離的平方代替距離,進(jìn)行比較。中間距離法還可以推廣為更一般的形式,即(6-28)其中,－1/4≤β≤0。

4.重心法重心法用一個類的重心(該類樣本的均值)代表該類,類與類之間的距離就用重心之間的距離來表示。設(shè)Gp與Gq的重心分別是xp和xq,則Gp與Gq之間的距離是Dpq=d(xp,xq)。設(shè)某一個類Gp與Gq的重心分別是xp和xq,它們的樣本數(shù)分別為np與nq,將類Gp與Gq合并為Gpq,則類Gpq的樣本數(shù)為npq=np+nq,它的重心xpq為(6-29)進(jìn)一步假設(shè)類Gi的重心為xi。采用歐氏距離時,類Gi與Gpq的距離滿足:(6-30)其中,(6-31)則(6-32)式(6-32)是重心法的遞推公式。

5.類平均距離法類平均距離法是將兩類之間的距離平方定義為這兩類樣本兩兩之間的距離平方的平均,即(6-33)將類Gp與Gq合并為Gpq,由式(6-33)可得,類Gk與Gpq的距離平方為(6-34)于是,類平均距離法的遞推公式為(6-35)類平均距離法充分利用各樣本的信息,從而成為層次聚類法中效果比較好的方法之一。

6.可變類平均法可變類平均法是在類平均距離法的遞推公式(6-35)中加入Dpq的影響,把遞推公式修正為(6-36)()

7.可變法

可變法是在中間距離法的推廣遞推公式(6-28)中將前兩項的系數(shù)也依賴于β,即(6-37)可變類平均法與可變法的分類效果依賴于β的選擇,有一定的主觀性,在實際中使用并不多。

8.離差平方和法設(shè)將N個樣本分成k類G1,G2,…,Gk,用xit表示Gt中的第i個樣本,nt表示Gt中的樣本個數(shù),xt是Gt的重心,則在Gt中的樣本的類內(nèi)離差平方和為(6-38)聚類過程中,將兩類合并,離差平方和就會增大。把兩類合并所增加的離差平方和定義為兩類距離平方,即將類Gp與Gq合并為Gpq時,定義D2pq=Spq－Sp－Sq,且有(6-39)可以證明,離差平方和法有遞推公式如下:(6-40)公式中各符號意義同前。以上給出了8種類與類之間的距離,并且得到不同的遞推公式,這些遞推公式具有統(tǒng)一的形式:(6-41)其中,系數(shù)αp、αq、β、γ對于不同的方法有不同的取值。表6-2列出了上述8種方法中四個參數(shù)的取值。表6-2遞推公式中的參數(shù)

方法αpαqβγ最短距離法1/21/20-1/2最長距離法1/21/201/2中間距離法1/2?－1/4≤β≤00重心法np/npqnq/npq-αpαq0類平均距離法np/npqnq/npq00可變類平均法<10可變法(1－β)/2(1－β)/2<10離差平方和法06.4動態(tài)聚類法

6.4.1動態(tài)聚類法的基本思想在層次聚類法中,樣本一旦歸入某個類以后就不再改變了,因此要求分類方法的準(zhǔn)確度要高。動態(tài)聚類法就是,先選擇一些初始聚類中心,讓樣本按某種原則劃分到各類中,得到初始分類;然后,用某種原則進(jìn)行修正,直到分類比較合理為止。動態(tài)聚類法的流程框圖如圖6-4所示,其中,每一部分都有很多種方法,不同的組合方式可得到不同動態(tài)聚類算法。動態(tài)聚類法有三個要點:

(1)選定某種相似性測度作為樣本間的相似性度量;

(2)確定某個評價聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù);

(3)給定某個初始分類,用迭代的算法找出使準(zhǔn)則函數(shù)取極值的聚類結(jié)果。下面簡要介紹幾種典型的動態(tài)聚類法:K均值算法和迭代自組織的數(shù)據(jù)分析算法,以及基于LBG算法的聚類分析。圖6-4動態(tài)聚類法的流程框圖6.4.2

K均值算法

K均值算法使用的聚類準(zhǔn)則函數(shù)是誤差平方和準(zhǔn)則,通過反復(fù)迭代優(yōu)化聚類結(jié)果,使所有樣本到各自所屬類別的中心的距離平方和達(dá)到最小。

K均值算法的步驟如下:

(1)任選K個初始聚類中心:z(1)1,z(1)2,…,z(1)K,其中,上角標(biāo)表示聚類過程中的迭代運算次數(shù)。

(2)假設(shè)已進(jìn)行到第r次迭代。若對某一樣本x有(6-42)則x∈S(r)j。其中,S(r)j是以z(r)j為聚類中心的樣本子集。以此種方法,即最小距離原則,將全部樣本分配到K個聚類中。

(3)計算重新分類后的各聚類中心:(6-43)式中,n(r)j為S(r)j中所包含的樣本數(shù)。

(4)若z(r+1)j=z(r)j,j=1,2,…,K,則結(jié)束;否則轉(zhuǎn)(2)。因為在第(3)步要計算K個聚類的樣本均值,故稱做K均值算法。該算法的特點是選一批代表點(初始聚類中心)后,計算所有樣本到聚類中心的距離,將所有樣本按最小距離原則劃分類別,形成初始分類,再重新計算各聚類中心,這是一種批處理方法。另一種方法是逐個處理法,每讀入一個樣本就把它歸于距離最近的一類,形成新的分類并計算新的聚類中心,然后再讀入下一個樣本歸類,即每個樣本的歸類都改變一次聚類中心。

K均值算法的分類結(jié)果與所選聚類中心的個數(shù)K和初始聚類中心選擇有關(guān),因此在實際應(yīng)用中需試探不同的K值和選擇不同的初始聚類中心。初始聚類中心的選取方法一般有如下幾種:

(1)用樣本集的前K個樣本作為初始聚類中心。

(2)將全部樣本隨機(jī)分成K類,計算每類重心,把這些重心作為每類的初始聚類中心。

(3)憑經(jīng)驗選初始聚類中心。根據(jù)問題的性質(zhì)、數(shù)據(jù)分布,選擇從直觀上看來較合理的K個初始聚類中心。

(4)按密度大小選代表點。以每個樣本作為球心,以d為半徑作球形,落在球內(nèi)的樣本數(shù)稱為該點的密度,并按密度大小排序。首先選密度最大的樣本點作為第一個代表點,即第一個初始聚類中心。再考慮第二大密度點,若第二大密度點距第一個代表點的距離大于d1(預(yù)先規(guī)定的一個正數(shù)),則把第二大密度點作為第二個代表點,否則不能作為代表點。這樣按密度大小依次考察下去,選擇K個樣本作為初始聚類中心。

(5)將相距最遠(yuǎn)的K個樣本作為初始聚類中心。此外,K均值算法的分類結(jié)果受到樣本的幾何性質(zhì)和讀入次序的影響。如果樣本的幾何特性能使它們形成幾個相距較遠(yuǎn)的孤立區(qū),那么算法一般能夠收斂。

【例6.2】模式分布如圖6-5所示,試用K均值法進(jìn)行聚類。取K=2。圖6-5

K均值算法例題樣本集解(1)選取z(1)1=x1=(0,0)T,z(1)2=x2=(1,0)T。

(2)因為‖x1－z(1)1‖<‖x1－z(1)2‖,所以x1∈S(1)1;因為‖x2－z(1)1‖>‖x2－z(1)2‖,所以x2∈S(1)2;因為‖x3－z(1)1‖<‖x3－z(1)2‖,所以x3∈S(1)1;

得S(1)1={x1,x3}

(3)計算新的聚類中心

(4)因為z(2)i≠z(1)i,i=1,2,所以回到(2)按新的聚類中心重新分類(用(2′)表示)。(2′)由新的聚類中心,有，所以，所以得(3′)計算新的聚類中心

(4′)因為z(3)i≠z(2)i,i=1,2,所以回到(2′)(用(2″)表示)。

(2″)按新的聚類中心進(jìn)行分類,分類結(jié)果與上一次迭代相同S(3)1=S(2)1,S(3)2=S(2)2。

(3″)計算聚類中心。

(4″)因為聚類中心與上一次相同,算法結(jié)束。6.4.3迭代自組織的數(shù)據(jù)分析算法迭代自組織的數(shù)據(jù)分析算法(IterativeSelfOrganizingDataTechniqueAlgorithm)簡稱ISODATA算法。類似于K均值算法,

ISODATA算法的聚類中心也是通過樣本均值的迭代運算來決定的。與K均值算法不同的是,ISODATA算法增加了一些試探性步驟和人機(jī)交互的“自組織”處理方式,在迭代過程中可將一類分成兩類,亦可能將兩類合為一類,即分裂和合并處理。迭代自組織算法流程圖如圖6-6所示。圖6-6迭代自組織算法流程圖

ISODATA算法的具體步驟如下:

(1)讀入包含N個模式的樣本集{x1,x2,…,xN},選擇m個初始聚類中心{z1,z2,…,zm}。其中,m不一定等于預(yù)期的聚類中心數(shù)目。參數(shù)設(shè)計如下:

K——預(yù)期的聚類中心數(shù)目;

θN——一個聚類中最少的樣本數(shù)目,即如少于此數(shù)就不作為一個獨立的聚類;

θs——聚類中樣本單個分量的標(biāo)準(zhǔn)方差的上限,若某個聚類中樣本單個分量的標(biāo)準(zhǔn)方差的最大值大于此數(shù),則可能分裂該聚類的中心。

θc——兩聚類中心之間的最小距離,如小于此數(shù),合并兩個聚類;

L——在一次迭代過程中,最多可以合并的聚類中心的對數(shù);

I——最大的迭代次數(shù)。

(2)根據(jù)最小距離準(zhǔn)則,將樣本x1,x2,…,xN分別歸入最近的聚類,若(6-44)即距離d(x,zj)最小,則x∈Sj。其中,Sj是以zj為聚類中心的樣本子集。

(3)如果Sj(j=1,2,…,m)中的樣本數(shù)目Nj<θN,則取消Sj,令m=m－1,并轉(zhuǎn)入(2);否則轉(zhuǎn)入下一步。

(4)調(diào)整聚類中心:(6-45)(5)計算各聚類中樣本與聚類中心之間的平均距離:(6-46)(6)計算全部模式樣本與相應(yīng)聚類中心之間的平均距離:(6-47)

(7)判斷分裂、合并和迭代運算等步驟:①如果迭代運算次數(shù)已達(dá)最大的迭代次數(shù)I,即最后一次迭代,令θc=0,轉(zhuǎn)入(11),結(jié)束迭代運算。②如聚類中心的數(shù)目小于等于規(guī)定值的一半,即m≤K/2,則轉(zhuǎn)入(8),分裂已有的聚類。③如迭代運算的次數(shù)是偶數(shù),或者m≥2K,則不進(jìn)行分裂處理,轉(zhuǎn)入(11);否則,轉(zhuǎn)入(8),分裂已有的聚類。分裂處理:

(8)計算聚類Sj中樣本的標(biāo)準(zhǔn)方差向量:(6-48)向量σj的第i個分量為(6-49)其中:d為樣本的維數(shù);樣本xk=(xk1,xk2,…,xkd)T;Sj的中心zj=(zj1,zj2,…,zjd)T。

(9)找出標(biāo)準(zhǔn)方差向量σj=(σj1,σj2,…,σjd)T中的最大分量,記為σj,max,j=1,2,…,m。

(10)檢測最大分量集{σj,max,j=1,2,…,m}中所有的元素,如σj,max>θs(該值給定),同時又滿足以下兩個條件中的一個:①和Nj>2(θN+1),即Sj中樣本總數(shù)超過規(guī)定值的一倍以上;②m≤K/2,則將Sj的中心zj分裂為兩個新的聚類中心z+j和z－j,且令m=m+1,其中,z+j和z－j的計算如下:①選定一個p值,0<p≤1;②令γj=pσj或γj=(0,…,pσj,max,…,0)T;③z+j=zj+γj,z－j=zj－γj。如果本步完成了分裂運算,則轉(zhuǎn)入(2),否則轉(zhuǎn)入(11)。合并處理:

(11)計算全部聚類中心之間的距離:；(6-50)

(12)比較Dij與θc值,將Dij<θc的前L個值遞增排列,即其中,Di1j1≤Di2j2≤…≤DiLjL。

(13)從最小的Di1j1開始,對于每個Diljl,合并相應(yīng)的兩個聚類中心zil和zjl,新的聚類中心為(6-51)并令m=m－L。

(14)如果迭代運算次數(shù)已達(dá)最大的迭代次數(shù)I,即最后一次迭代,則算法結(jié)束;否則,如果需要由操作者改變輸入?yún)?shù),轉(zhuǎn)入(1),設(shè)計相應(yīng)的參數(shù);否則,轉(zhuǎn)入(2)。到了本步運算,迭代運算的次數(shù)加1。6.4.4基于LBG算法的聚類分析

LBG算法是K均值算法的推廣。LBG算法是矢量量化中的一種重要碼書生成算法,先選取初始碼書,通過對訓(xùn)練樣本的量化、聚類、迭代,產(chǎn)生局部最優(yōu)的碼書。這里,把LBG算法應(yīng)用于聚類分析,具體步驟如下:

(1)設(shè)樣本集為{x1,x2,…,xN}。給定初始聚類中心{z(0)i|i=1,2,…,K},并置r=0,設(shè)起始平均失真D(-1)→∞,給定計算停止門限ε(0<ε<1)。

(2)設(shè)已進(jìn)行到第r次迭代。若對每一樣本x有(6-52)則x∈S(r)j,其中,S(r)j是以z(r)j為聚類中心的樣本子集。以此種方法將全部樣本分配到K個聚類中。

(3)計算平均失真與相對失真。平均失真為(6-53)其中,距離d(z(r)j,xi)取為歐氏距離。相對失真為(6-54)若≤ε,則停止,當(dāng)前聚類為設(shè)計好的最終聚類;否則,進(jìn)行(4)。

(4)計算各聚類中心的新向量值(6-55)式中,Nj為S(r)j中所包含的樣本數(shù),并置r=r+1,返回到(2),將全部樣本重新分類,重復(fù)迭代計算。初始聚類中心的選取算法有隨機(jī)法、分裂法等,其中分裂法效果顯著。隨機(jī)法就是隨機(jī)地選取K個樣本作為初始聚類中心。分裂法將在6.5節(jié)中介紹。事實上,在矢量量化中,最終聚類的各個聚類中心組成碼書。6.5分解法

在層次聚類中,類別由多到小。分解法的思想是類別由小到多,也就是說,開始把全體樣本看成一類,然后分成兩類、三類……直至所有的樣本各自為一類,或者分類比較合理為止。6.5.1一分為二法一分為二法是將一個聚類分解為兩子類,然后對其子類又一分為二。設(shè)某類G中有n個樣本,它的兩個子類G1、G2各有n1和n2個樣本;兩類重心為z1和z2,G的重心為z。類G、G1與G2的離差平方和分別為(6-56)(6-58)一般要求S1+S2盡可能的小,或S－(S1+S2)盡可能的大。可以證明:或者，(6-59)以E=S－(S1+