聚類分析算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、各聚類中心必然也與前一次的相同，不再出現(xiàn)新的類別劃分，故分類過程結束。因*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）改進的0均值法文獻【0基于核函數(shù)的概念提出了一種改進的一均值法，其分類性能要好于通常計算模式到類的距離時采用這個模式到類心的歐氏距離或馬氏距離的均值法。由于C均值法我們已作詳細介紹，這種改進的C均值法只簡單表述如下:對給定的待分類模式集兀為心進行初始分劃產生。類；計算各聚類嗎所含模式數(shù)、均值矢量和協(xié)

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

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

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

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