第三節(jié)快速聚類法

第五章第三節(jié)一、快速聚類法的步驟二、用Lm距離進(jìn)行快速聚類快速聚類法7/28/2023在譜系聚類法中，因?yàn)闃悠芬坏┍粴w到某個(gè)類后就不變了，所以要求分類方法比較準(zhǔn)確。而樣品容量較大時(shí)，譜系聚類法的計(jì)算量過(guò)大。因此，為了彌補(bǔ)譜系聚類法的不足，產(chǎn)生了快速聚類法，又稱動(dòng)態(tài)聚類法?？焖倬垲惙ㄏ葘悠反植诘胤忠幌骂悾缓笤侔凑漳撤N原則進(jìn)行修正，直至分類比較合理為止。7/28/2023快速聚類法選擇聚點(diǎn)最終分類合理初始分類分類是否合理修改分類不合理7/28/2023一、快速聚類法的步驟1選擇聚點(diǎn)聚點(diǎn)（種子）是一批有代表性的樣品，它的選擇決定了初始分類，對(duì)最終分類有較大影響。在進(jìn)行快速聚類法前，要根據(jù)研究問(wèn)題的要求及了解程度先定下分類數(shù)k，這樣就可以在每一類中選擇一個(gè)有代表性的樣品作為聚點(diǎn)（初始聚點(diǎn)）。7/28/2023選擇聚點(diǎn)有下列方法：

(1)經(jīng)驗(yàn)選擇。如果對(duì)研究對(duì)象比較了解，根據(jù)以往的經(jīng)驗(yàn)定下k個(gè)樣品作為聚點(diǎn)。

(2)將n個(gè)樣品人為地（或隨機(jī)地）分成k類，以每類的重心作為聚點(diǎn)。

(3)最小最大原則。設(shè)要將n個(gè)樣品分成k類，先選擇所有樣品中距離最遠(yuǎn)的兩個(gè)樣品為前兩個(gè)聚點(diǎn),即選擇和使7/28/2023然后選擇第3個(gè)聚點(diǎn)使其與前兩個(gè)聚點(diǎn)的距離最小者等于所有其余的與的較小距離中最大的,用公式表示為然后按相同的原則選取依次下去，直至選定k個(gè)點(diǎn)若已選了l個(gè)聚點(diǎn)(l<k),則第l+1個(gè)聚點(diǎn)選取的原則為7/28/2023注：在SAS系統(tǒng)procfastclus過(guò)程中，分類數(shù)k是事先給定的。在給定k以后，procfastclus過(guò)程會(huì)按上述方法算出初始聚點(diǎn)的。2快速聚類法的計(jì)算步驟先假設(shè)聚類中采用的距離是歐式距離，即1）設(shè)k個(gè)初始聚點(diǎn)的集合是用下列原則實(shí)現(xiàn)初始分類。記7/28/2023則是每個(gè)樣品以最靠近的初始聚點(diǎn)歸類。這樣，將樣品分成不相交的k類。以上初始分類的原依照以上計(jì)算，得到一個(gè)初始分類2）從出發(fā)，計(jì)算新的聚點(diǎn)集合以的重重心作為新的聚點(diǎn)：7/28/2023其中是類中的樣品數(shù).這樣得到新的聚點(diǎn)集合：從出發(fā)，將樣品作新的分類。記得到分類這樣，依次重復(fù)計(jì)算下去。7/28/20233）設(shè)在第m步得到分類在以上遞推計(jì)算過(guò)程中，是類的重心.不一定是樣品，又一般不是的重心.當(dāng)m逐漸增大時(shí)，分類的重心，從而趨于穩(wěn)定.此時(shí)，就會(huì)近似認(rèn)為算法即可結(jié)束。實(shí)際計(jì)算時(shí)，從某一步m開始，分類與完全相同，計(jì)算即告結(jié)束。7/28/2023記理論上可以證明:當(dāng)m增加時(shí)為單調(diào)減下有界序?qū)⒅鸩椒€(wěn)定，即上述快速聚類法具有收斂性.故存在，即會(huì)逐步趨于穩(wěn)定。因此，分類結(jié)果也設(shè)給定若則遞推計(jì)算過(guò)程結(jié)束。7/28/2023例1.1976年74個(gè)國(guó)家和地區(qū)的人口出生率x1和死亡率x2的數(shù)據(jù)見(jiàn)表6.25（國(guó)家與地區(qū)名從略）.表中列出的數(shù)據(jù)是每10萬(wàn)人的出生數(shù)與死亡數(shù).試對(duì)這74個(gè)國(guó)家與地區(qū)按人口出生率與死亡率進(jìn)行快速聚類分析。7/28/2023data

shengsi;inputx1x2;cards;……;proc

fastclusdata=shengsiout=a1maxc=3cluster=cdistancelist;proc

plot;plotx2*x1=c;run;假定分3類7/28/20237/28/20237/28/20237/28/20237/28/2023data

shengsi;inputx1x2;cards;……;proc

fastclusdata=shengsiout=a1maxc=4cluster=cdistancelist;proc

plot;plotx2*x1=c;run;分為4類7/28/20237/28/20237/28/20237/28/20237/28/2023二、用Lm距離進(jìn)行快速聚類上面我們介紹的聚類方法都是用歐氏距離。下面我們介紹用Lm距離進(jìn)行快速聚類的方法。則Lm距離為設(shè)當(dāng)m=2時(shí)，即是歐氏距離，當(dāng)m=1時(shí)，為絕對(duì)距離：7/28/2023我們先討論L1的情況。對(duì)于一元數(shù)據(jù)要求一個(gè)數(shù)c，使得可知，使上式達(dá)到小的c是的中位數(shù)7/28/2023對(duì)于p元樣品的第k個(gè)分量的數(shù)據(jù)集是設(shè)它的中位數(shù)是則稱其為的中位向量，其中滿足7/28/2023從而7/28/2023討論Lm最優(yōu)化準(zhǔn)則。對(duì)于一元數(shù)據(jù)要求有一個(gè)數(shù)c，使得的m中心.對(duì)于p元樣品稱c為其中的第k個(gè)分量的數(shù)據(jù)集是設(shè)它的m中心是則7/28/2023的m中心向量，其中稱為滿足從而顯然，2中心向量即均值向量，1中心向量即中位向量.7/28/2023在采用Lm距離進(jìn)行快速聚類分析時(shí)，最終聚點(diǎn)應(yīng)是每一類的m中心向量。在采用L1距離進(jìn)行聚類分析時(shí),最終聚點(diǎn)應(yīng)是每一類的中位向量.用L1距離進(jìn)行聚類分析時(shí)，有較強(qiáng)的穩(wěn)健性，當(dāng)有異常數(shù)據(jù)時(shí)，分類結(jié)果經(jīng)常會(huì)更好些.采用不同的Lm距離，聚類分析的結(jié)果經(jīng)常會(huì)是不同的.7/28/2023例2.利用絕對(duì)距離對(duì)例6.8的數(shù)據(jù)進(jìn)行快速聚類。（1）分為3類；（2）分為4類。7/28/20237/28/20237/28/20237/28/20237/28/20237/28/20237/28/20237/28/2023例3.利用L