聚類分析算法

1、第二章聚類分析聚類的算法聚1類的技術(shù)方案簡(jiǎn)單聚類根據(jù)相似性閾值和最小距離原則聚類WQ,u,uu,；(,e,是,中的樣本個(gè)數(shù)，是給定的閥值。e,類心一旦確定將不會(huì)改變。譜系或?qū)哟尉垲惏醋钚【嚯x原則不斷進(jìn)行兩類合并類心不斷地修正，但模式類別一旦指定后就不再改變。依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類影響聚類結(jié)果的主要因數(shù)：類心、類別個(gè)數(shù)、模式輸入順序。所謂動(dòng)態(tài)聚類，是指上述因數(shù)在聚類過程中是可變的。規(guī)定一些分類的目標(biāo)參數(shù)，定義一個(gè)能刻劃聚類過程或結(jié)果優(yōu)劣的準(zhǔn)則函數(shù)，聚類過程就是使準(zhǔn)則函數(shù)取極值的優(yōu)化過程。這類方法有一均值法、法、近鄰函數(shù)法以及運(yùn)用圖論理論的最小張樹法。簡(jiǎn)2單聚類方法根據(jù)相似性閾值和最小距離原則的簡(jiǎn)單

2、聚類方法條件及約定設(shè)待分類的模式為區(qū)冠巫,選定類內(nèi)距離門限f。算法思想計(jì)算模式特征矢量到聚類中心的距離并和門限F比較而決定歸屬該類或作為新的一類中心。通常選擇歐氏距離。算法原理步驟取任意的一個(gè)模式特征矢量作為第一個(gè)聚類中心。例如，令第一類朗的中心岔二石。（2）計(jì)算下一個(gè)模式特征矢量鬲到筍的距離血1。若比，則建立新的一類2，其中心蒼=為；若込1蘭T，則為已1。假設(shè)已有聚類中心耳知恙，計(jì)算尚未確定類別的模式特征矢量爲(wèi)到各聚類中心幻（廠12我）的距離珀，如果軸（丿=12我），則爲(wèi)作為新的一類孤+i的中心，茲；否則，如果則指判爲(wèi)。檢查是否所有的模式都分劃完類別，如都分劃完了則結(jié)束；否則返到。性能計(jì)算簡(jiǎn)

3、單。聚類結(jié)果很大程度上依賴于距離門限F的選取、待分類特征矢量參與分類的次序和聚類中心的選取。當(dāng)有特征矢量分布的先驗(yàn)知識(shí)來指導(dǎo)門限F及初始中心云的選取時(shí)，可以獲得較合理結(jié)果。改進(jìn)通常采用試探法，選用不同的門限及模式輸入次序來試分類，并對(duì)聚類結(jié)果進(jìn)行檢驗(yàn)即用聚類準(zhǔn)則函數(shù)。例如，計(jì)算每一聚類中心與該類中最遠(yuǎn)樣本點(diǎn)的距離，或計(jì)算類內(nèi)及類間方差，用這些結(jié)果指導(dǎo)F及筍的重選。最后對(duì)各種方案的劃分結(jié)果進(jìn)行比較，選取最好的一種聚類結(jié)果。圖(2-4距-離1閾)值及初始類心對(duì)聚類的影響最大最小距離算法條件及約定設(shè)待分類的模式特征矢量集為區(qū)耳瓦，選定比例系數(shù)B。基本思想在模式特征矢量集中以最大距離原則選取新的聚類中

4、心，以最小距離原則進(jìn)行模式歸類。這種方法通常也使用歐氏距離。3.算法原理步驟3.算法原理步驟選任一模式特征矢量作為第一個(gè)聚類中心爲(wèi)。例如，爲(wèi)二瓦。從待分類矢量集中選距離爲(wèi)最遠(yuǎn)的特征矢量作為第二個(gè)聚類中心爲(wèi)。例如圖中如圖中-2)最大，取爲(wèi)二焉。計(jì)算未被作為聚類中心的各模式特征矢量朝與云、蒼之間的距離并求出它們之中的最小值，即dv=為表述簡(jiǎn)潔，雖然某些模式已選做聚類中心，但上面仍將所有模式下角標(biāo)全部列寫出來，因這并不影響算法的正確性。若町=maxmin(dn,di2)創(chuàng)屋-刼|則相應(yīng)的特征矢量耳作為第三個(gè)聚類中心，召二石。此例中務(wù)二爲(wèi)。然后轉(zhuǎn)至;否則，轉(zhuǎn)至最后一步。設(shè)存在此個(gè)聚類中心，計(jì)算未被作為

5、聚類中心的各特征矢量到各聚類中心的距離箱并算出跆X4圖-距11跆X4圖-距11盤遠(yuǎn)選為Z287圖最-大2最）小距離算法舉例如果必臨一羽，則心并轉(zhuǎn)至；否則，轉(zhuǎn)至最后一步。當(dāng)判斷出不再有新的聚類中心之后，將模式特征矢量兀兀，曲；按最小距離原則分到各類中去，即計(jì)算（=12；心12,當(dāng)妒啰囲，則判羌書。在此例中，石屆屆已1，云=兀；國(guó)心亡2,z2X6；兀5，為，io已39;z3X7，O這種算法的聚類結(jié)果與參數(shù)B以及第一個(gè)聚類中心的選取有關(guān)。如果沒有先驗(yàn)知識(shí)指導(dǎo)8和云的選取，可適當(dāng)調(diào)整&和云，比較多次試探分類結(jié)果，選取最合理的一種聚類。Xi：（OnO）期彩）紐：（詢皿,3）圖：（4腐:6,3）躊:5,4

6、）砂尬4）血億5）.譜.譜3系聚類法法)系統(tǒng)聚類法、層次聚類效果較好、是常用方法之一。條件及約定設(shè)待分類的模式特征矢量為國(guó)冠，胡，嚴(yán)表示第次合并時(shí)的第I類?；舅枷胧紫葘ⅰ皞€(gè)模式視作各自成為一類，然后計(jì)算類與類之間的距離，選擇距離最小的一對(duì)合并成一個(gè)新類，計(jì)算在新產(chǎn)生的類別分劃下各類之間的距離，再將距離最近的兩類合并，直至所有模式聚成兩類為止。算法步驟初始分類。令0,每個(gè)模式自成一類，即潭f計(jì)算各類間的距離，生成一個(gè)對(duì)稱的距離矩陣沙742,m為類的個(gè)數(shù)。找出前一步求得的矩陣岀)中的最小元素，設(shè)它是叫和於間的距離,將即和兩類合并成一類，r-d.t+l).-ffUl)將即和兩類合并成一類，于是產(chǎn)生

7、新的聚類檢查類的個(gè)數(shù)。如果類數(shù)擁大于2令花十，轉(zhuǎn)至；否則，停止。如果某一循環(huán)中具有最小類間距離不止一個(gè)類對(duì)，則對(duì)應(yīng)這些最小距離的類可以同時(shí)合并。上述算法步驟給出了從類至2類的完整聚類過程，停止條件以類間距離門限丁作為停止條件，即取距離門限，當(dāng)口中最小陣元大于丁時(shí)，聚類過程停止；以預(yù)定的類別數(shù)目作為停止條件，當(dāng)類別合并過程中，類數(shù)等于預(yù)定值時(shí)，聚類過程停止。類間距離的定義與遞推在該算法中可以采用上節(jié)已詳細(xì)介紹過的不同的類間距離定義方式，并使用類間距離遞推公式。所采用的類間距離定義不同，聚類過程及結(jié)果是不一樣的。上述算法在歸并的每次迭代過程中，距離矩陣的最小元素值不斷地改變，如果有單調(diào)不減關(guān)系則稱

8、類間距離對(duì)并類具有單調(diào)性。最近距離法、最遠(yuǎn)距離法、平均法及離差平方和法等定義的類間距離都具有這個(gè)性質(zhì)，而重心法沒有這個(gè)性質(zhì)。算法特點(diǎn)聚類過程中類心不斷地調(diào)整，但某一模式一旦分劃到某一類中就不再改變。從粗到細(xì)的層次聚類這類技術(shù)的另一個(gè)算法和上述算法過程相反，依據(jù)類的離差平方和遞推公式按1類至類進(jìn)行譜系分解，這里不作介紹了。聚類過程可以表示成一個(gè)樹圖。例：給出6個(gè)樣本特征矢量如下，按最小距離原則進(jìn)行聚類。瓦=（1丄020）禮=（H212iy焉=（4,1,1丄0）解：將每一樣本看成自成一類局色=為七6嘰伉色性和計(jì)算距離矩陣表4曲中最小陣元為低它是甲與身之間的距離，將它們合并為一類,得一新的分類為甲斗

9、型烤卜隱鬲駕制理=當(dāng)甲斗型烤卜隱鬲駕制理=當(dāng)計(jì)算合并后的距離矩陣門表卑制）題=當(dāng)。-在2這）里使用了距離遞推公式，如瑙=rnrn型與第）距離，酸）與逡1距離=rnrn/15,-76）=肝邛中距離最小者為折，它是謂）與帶間的距離，合并第）和電），得新的分類同樣計(jì)算門表，進(jìn)一步聚類得同樣計(jì)算門表，進(jìn)一步聚類得呼）=申）,曙）常）=今常）二皆即即計(jì)算門表，計(jì)算門表，由表可知，空、霍）和霍可以一起合并成一類。表4-表-表-表表4-表-表-表-3動(dòng)4態(tài)聚類法最大距離和層次聚類算法的一個(gè)共同特點(diǎn)是某個(gè)模式一旦劃分到某一類之后，在后繼的算法過程中就不改變了，而簡(jiǎn)單聚類算法中類心一旦選定后在后繼算法過程中也不

10、再改變了，這類方法效果一般不會(huì)太理想。和上述各算法相對(duì)應(yīng)有一種動(dòng)態(tài)聚類法。其要點(diǎn)為：確定模式和聚類的距離測(cè)度。當(dāng)采用歐氏距離時(shí)，是計(jì)算此模式和該類中心的歐氏距離；為能反映出類的模式分布結(jié)構(gòu)，應(yīng)采用馬氏距離，設(shè)該類的均矢為口，協(xié)方差陣為貝醮式和該類的距離平方為與該類均矢口的馬氏距離應(yīng)2=亍一口）逞（壬一遼）確定評(píng)估聚類質(zhì)量的準(zhǔn)則函數(shù)。確定模式分劃及聚類合并或分裂的規(guī)貝。動(dòng)態(tài)聚類算法的基本步驟：建立初始聚類中心，進(jìn)行初始聚類；計(jì)算模式和類的距離，調(diào)整模式的類別；計(jì)算各聚類的參數(shù)，刪除、合并或分裂一些聚類；從初始聚類開始，運(yùn)用迭代算法動(dòng)態(tài)地改變模式的類別和聚類的中心使準(zhǔn)貝函數(shù)取得極值或設(shè)定的參數(shù)達(dá)到

11、設(shè)計(jì)要求時(shí)停止。動(dòng)態(tài)聚類原理框圖如下：圖匚一均值法（條件及約定設(shè)待分類的模式特征矢量集為區(qū)冠為，類的數(shù)目。是取定的?；舅枷肴《▊€(gè)類別和選取。個(gè)初始聚類中心，按最小距離原則將各模式分配到。類中的某一類，不斷地計(jì)算類心和調(diào)整各模式的類別使每個(gè)模式特征矢量到其所屬類別的距離平方之和最小,算法步驟任選。個(gè)模式特征矢量作為初始聚類中心:帶左沽刖。將待分類的模式特征矢量集國(guó)中的模式逐個(gè)按最小距離原則分劃給。類中的某一類，即則判召十。式中硝表示吾和時(shí)的中心躋的距離，上角標(biāo)表示迭代次數(shù)。于是產(chǎn)生新的聚類呼in。計(jì)算重新分類后的各類心式中挖畀）為呼類中所含模式的個(gè)數(shù)。因?yàn)檫@一步采取平均的方法計(jì)算調(diào)整后類的中心

12、，且定為。類，故稱一均值法。如果工勺，則轉(zhuǎn)至；如果勺則結(jié)束。如果工勺，則轉(zhuǎn)至；如果勺則結(jié)束。分析我們以歐氏距離為例，簡(jiǎn)單地分析該算法的可收斂性。在上述算法中，雖然沒有直接運(yùn)用準(zhǔn)則函數(shù)進(jìn)行分類，但在中根據(jù)式進(jìn)行模式分劃可使嚴(yán)）趨于變小。設(shè)某樣本石從聚類叫移至聚類孤中，叫移出石后的集合記為為，喩移入石后的集合記為娥。設(shè)叫和叫所含樣本數(shù)分別為和叫，聚類叫、爲(wèi)、叫和娥的均矢分別鳳和,顯然有鳳和,顯然有而這兩個(gè)新的聚類的類內(nèi)歐氏距離平方幾和人與原來的兩個(gè)聚類的類內(nèi)歐氏距離平方心和人的關(guān)系是石7十2嚴(yán)距忍比距劭更近時(shí)，使得由式-及可知，將瓦分劃給喩類可使J變小。這說明在分類問題中不斷地計(jì)算新分劃的各類的類

13、心，并按最小距離原則歸類可使值減至極小值。在上述算法中，也可以利用式（2-4進(jìn)-行1模3式）類別的重新分劃性能算法簡(jiǎn)單，收斂（已于年和年分別給出了嚴(yán)格證明）。如模式分布呈現(xiàn)類內(nèi)團(tuán)聚狀，該算法是能達(dá)到很好聚類結(jié)果的，故應(yīng)用較多。能使各模式到其所判屬類別中心距離平方之和為最小的最佳聚類。以確定的類數(shù)C、模式輸入次序及選定的初始聚類中心為前提，受此限制結(jié)果只是局部最優(yōu)。改進(jìn)二的調(diào)整作一條一曲線，其曲率變化的最大點(diǎn)對(duì)應(yīng)的類數(shù)是比較接近最優(yōu)的類數(shù)。在類別數(shù)未知的情況下，可使類數(shù)c由較小值逐步增加，對(duì)于每個(gè)選定的c分別使用該算法。顯然準(zhǔn)則函數(shù)是隨。的增加而單調(diào)減少。在。增加過程中，總會(huì)出現(xiàn)使本來較密集的類

14、再拆開的情況，此時(shí)雖減小，但減小速度將變緩。如果作一條。一曲線，其曲率變化的最大點(diǎn)對(duì)應(yīng)的類數(shù)是比較接近最優(yōu)的類數(shù)。然而在許多情況下，曲線并無明顯的這樣的點(diǎn)。另一種方法是利用問題的先驗(yàn)知識(shí)分析選取合理的聚類數(shù)。初始聚類中心選取初始聚類中心可按以下幾種方法之一選?。簯{經(jīng)驗(yàn)選擇初始類心。將模式隨機(jī)地分成類，計(jì)算每類中心，以其作為初始類心。（最大密度）,求以每個(gè)特征點(diǎn)為球心、某一正數(shù)為半徑的球形域中特征點(diǎn)個(gè)數(shù)，這個(gè)數(shù)稱為該點(diǎn)的密度。選取密度最大的特征點(diǎn)作為第一個(gè)初始類心卸），然后在與計(jì)）大于某個(gè)距離川的那些特征點(diǎn)中選取具有“最大”密度的特征點(diǎn)作為第二個(gè)初始類心硏，如此進(jìn)行，選取個(gè)初始聚類中心。用相距最

15、遠(yuǎn)的。個(gè)特征點(diǎn)作為初始類心。具體地講，是按前述的最大最小距離算法求取個(gè)初始聚類中心。當(dāng)N較大時(shí)，先隨機(jī)地從個(gè)模式中取出一部分模式用譜系聚類法聚成c類，以每類的重心作為初始類心。設(shè)已標(biāo)準(zhǔn)化的待分類模式集為國(guó)怎為，希望將它們分為。類。令模式噸）=遲恥令模式噸）=遲恥.（:-1，定義且令MA=maxs(z)MA=maxs(z)計(jì)算顯然-C,若務(wù)最接近整數(shù)，則把石分劃至嗎中。對(duì)所有樣本都實(shí)行上述處理，就可實(shí)現(xiàn)初始分類，從而產(chǎn)生初始聚類中心。用類核代替類心前面的算法存在一個(gè)不足，即是只用一個(gè)聚類中心點(diǎn)作為一類的代表，但是一個(gè)點(diǎn)往往不能充分地反映該類的模式分布結(jié)構(gòu)，從而損失很多有用的信息。當(dāng)類的分布是球狀

16、或近似球狀時(shí)，算法尚能有較好的效果，但對(duì)于如圖（2-4所-示的那種各分量方差不等的正態(tài)分布而兩類的主軸和類心又是那樣的情況，分類效果就不好了，/點(diǎn)應(yīng)屬于朗類，但由于它距禺類的均矢更近，按前述的算法則被指判到朗類。如果已知各類模式分布的某些知識(shí)，則可以利用它們指導(dǎo)聚類。為此，我們定義一個(gè)類核函數(shù)島二禺元？1表示類嗎的模式分布情況，其中廠關(guān)于類叫的一個(gè)參數(shù)集，是挖維空間中的特征矢量，島可以是一個(gè)函數(shù)、一個(gè)點(diǎn)集或其他適當(dāng)?shù)哪Ｐ?。為了刻劃待識(shí)模式和嗎類的接近程度還應(yīng)規(guī)定一個(gè)模式特征矢量到核島的距離把區(qū)。實(shí)際上，馬氏距離就是核函數(shù)距離的一種簡(jiǎn)化。當(dāng)已知某類的分布近似為正態(tài)分布時(shí)，可以用以這類樣本統(tǒng)計(jì)估計(jì)

17、值為參數(shù)的正態(tài)分布函數(shù)作為核函數(shù)，即其中式中勺為進(jìn)行參數(shù)估計(jì)的該類樣本數(shù)。則模式亍與該類的距離為這實(shí)際上是第四章將要討論的最小誤判概率準(zhǔn)則下先驗(yàn)概率相同時(shí)的判決函數(shù)。當(dāng)已知各類樣本分別在相應(yīng)的主軸附近分布時(shí)，可以定義主軸核函數(shù)：Kxy；=Ux式中，mx耳）是由和叫類的統(tǒng)計(jì)協(xié)方差陣爲(wèi)的猙禺）個(gè)最大特征值所對(duì)應(yīng)的已規(guī)格化的特征矢量作成的矩陣，即6是協(xié)方差陣烏給出的部分主軸系統(tǒng)，斑，叫）給出了樣本分布的主軸方向散布的情況由特征值反映出來）區(qū)為礙軸上的單位矢量。設(shè)耳是類樣本的均值矢量，求一點(diǎn)和一個(gè)軸碼的距離可見圖-模式和嗎類間的距離平方可以用和該類的主軸間的歐氏距離平方來度量。dl（%=贋-耳）-Up

18、f/.x-耳）肪-禺）-UJJ伝-禺）各分量方差不等的正態(tài)分布）沿主軸分布）各分量方差不等的正態(tài)分布）沿主軸分布類-的4模）式分布情況的示例求-和5主）軸距離示意圖例：模式分布如圖所-例：模式分布如圖所-示6，試用。一均值法進(jìn)行聚類，取。器丄石=器丄石=（o,oyz=x2=(y牡=聲屁站=2.中=鬲忑，屁JN2=，計(jì)算新的聚類中心m5.33,m5.33,因孝工踏（Tt），故轉(zhuǎn)至。由新的聚類中心，得何護(hù)卜何即|心1,2,說故得計(jì)算聚類中心.2驢JO（4）因聲f七），故轉(zhuǎn)至。求得的分類結(jié)果與前一次的結(jié)果相同，呼二呼各聚類中心必然也與前一次的相同，不再出現(xiàn)新的類別劃分，故分類過程結(jié)束。因*X1Q*X

19、各聚類中心必然也與前一次的相同，不再出現(xiàn)新的類別劃分，故分類過程結(jié)束。因*X1Q*X20-X16-X17-K18K）腐:1）跨（叮）觀：1,1）於W）毗1,3）迢W）蹲3）遜：（6上）邊。：（7）xn：（8/）牝：（阿沁門J）Xi+：（S?7）紐5：（g/oxis：（9?8）紐9：（訕盜加：9,9）改進(jìn)的0均值法文獻(xiàn)【0基于核函數(shù)的概念提出了一種改進(jìn)的一均值法，其分類性能要好于通常計(jì)算模式到類的距離時(shí)采用這個(gè)模式到類心的歐氏距離或馬氏距離的均值法。由于C均值法我們已作詳細(xì)介紹，這種改進(jìn)的C均值法只簡(jiǎn)單表述如下:對(duì)給定的待分類模式集兀為心進(jìn)行初始分劃產(chǎn)生。類；計(jì)算各聚類嗎所含模式數(shù)、均值矢量和協(xié)

20、方差陣弓；將各模式召按最小距離原則分劃到某一聚類中。這里采用最小誤判概率準(zhǔn)則下正態(tài)分布情況的判決規(guī)則，計(jì)算模式到叫的距離d（x,j）=In%+d（元d（元J=inin）如果則判如果沒有模式改變其類別，則停止算法；否則轉(zhuǎn)至。（三）迭代自組織數(shù)據(jù)分析算法特點(diǎn)：具有啟發(fā)性推理、分析監(jiān)督、控制聚類結(jié)構(gòu)及人機(jī)交互。條件及約定設(shè)待分類的模式特征矢量為氏龐為，算法運(yùn)行前需設(shè)定個(gè)初始參數(shù)。算法思想在每輪迭代過程中，樣本重新調(diào)整類別之后計(jì)算類內(nèi)及類間有關(guān)參數(shù)，并和設(shè)定的門限比較，確定是兩類合并為一類還是一類分裂為兩類，不斷地“自組織”以達(dá)到在各參數(shù)滿足設(shè)計(jì)要求條件下，使各模式到其類心的距離平方和最小。算法原理步

21、驟預(yù)置設(shè)定聚類分析控制參數(shù)：C預(yù)期的類數(shù)，肚初始聚類中心個(gè)數(shù)可以不等于。）圧每一類中允許的最少模式數(shù)目若少于此數(shù)就不能單獨(dú)成為一類）Q類內(nèi)各分量分布的距離標(biāo)準(zhǔn)差上界大于此數(shù)就分裂）氐兩類中心間的最小距離下界若小于此數(shù)，這兩類應(yīng)合并）在每次迭代中可以合并的類的最多對(duì)數(shù)，允許的最多迭代次數(shù)。將待分類的模式特征矢量國(guó)耳臥讀入。選定初始聚類中心，可從待分類的模式特征矢量集刃中任選磯個(gè)模式特征矢量作為初始聚類中心相按最小距離原則將模式集憶中每個(gè)模式分到某一類中，即式中山表示珀和類叫的中心之間的距離。依據(jù)氏判斷合并。如果類旳中樣本數(shù)35，則取消該類的中心石，產(chǎn)琢T，轉(zhuǎn)至或計(jì)算產(chǎn)琢T，轉(zhuǎn)至或計(jì)算6尸憐-引心

22、12氏），將叫并入距離最近的那一類中；這時(shí)“尸肚T，轉(zhuǎn)至。計(jì)算分類后的參數(shù):計(jì)算分類后的參數(shù):各類中心、類內(nèi)平均距離及總體平均距離。計(jì)算各類的中心（尸12（尸12氏）計(jì)算各類中模式到類心的平均距離計(jì)算各個(gè)模式到其類內(nèi)中心的總體平均距離依據(jù)嘰判斷停止、分裂或合并。若迭代次數(shù)心已達(dá)，則置屜轉(zhuǎn)到；否則轉(zhuǎn)下。若恥氣則轉(zhuǎn)到將一些類分裂；否則轉(zhuǎn)下。若NK則跳過分裂處理轉(zhuǎn)至否則轉(zhuǎn)下。二：F譏-Zc若2，當(dāng)?shù)螖?shù)“是奇數(shù)時(shí)轉(zhuǎn)至分裂處理）迭代次數(shù)是偶數(shù)時(shí)轉(zhuǎn)至合并處理。計(jì)算各類類內(nèi)距離的標(biāo)準(zhǔn)差矢量，鞏）其各分量12楓）式中，疋為分量編號(hào)，為類的編號(hào),式中，疋為分量編號(hào)，為類的編號(hào),挖為矢量維數(shù)，叱是嗎的第疋個(gè)分

23、量，是冠的第氐個(gè)分量。對(duì)每一聚類，求出類內(nèi)距離標(biāo)準(zhǔn)差矢量?jī)抑械淖畲蠓至績(jī)铱г诨脟嵵?，?duì)任一勺逐，若有逐色，同時(shí)又滿足下面兩個(gè)條件之一：則將該類叫分裂為兩個(gè)聚類，且令尸M+1。這兩個(gè)新類的中心石和石是這樣構(gòu)成的：右和虧只是在勺中相應(yīng)于遜的分量分別加上和減去肚，而其它分量不變，其中W抵的選取應(yīng)使右和仍在嗎的類域空間中且其它類出“力的模式到石和幻距離較遠(yuǎn)，而原叫類中的模式和它們距離較小。分裂后，3裂后，3，轉(zhuǎn)至；否則，轉(zhuǎn)下。計(jì)算各對(duì)聚類中心間的距離（心12楓-1;E+1,，甌）依據(jù)判斷合并。將坷與比較，并將小于氐的那些必按遞增次序排列，取前個(gè)，入D。從最小的必開始，將相應(yīng)的兩類合并。若原來的兩個(gè)類心為和勺，則合并后的聚類中心為（心12（心12）“尸N廠（已并掉的類數(shù)）。在一次迭代中，某一類最多只能被合并一次。（11）如果迭代次數(shù)婦已達(dá)次或過程收斂，則結(jié)束。否則，片二片+1，若需要調(diào)整參數(shù)，則轉(zhuǎn)至；若不改變參數(shù)，則轉(zhuǎn)至。我們將該算法的合并和分裂的條件歸納如下：合并的條件：類內(nèi)樣本數(shù)空氏）類的數(shù)目王比）兩類間中心距離弐“）分裂的條件：類的數(shù)目類的某分量標(biāo)準(zhǔn)差）類的數(shù)目類的某分量標(biāo)準(zhǔn)差）J）A（-2（eB+i）vw|）這里，v表示“或”的關(guān)系；八表示“與”的關(guān)系。如果類的數(shù)目甌有，當(dāng)。是奇數(shù)時(shí)分裂，當(dāng)$是偶數(shù)時(shí)合并。由上述合并與分裂的判斷條