聚類分析課件

聚類分析聚類系統(tǒng)聚類

例對10位應(yīng)聘者做智能檢驗(yàn)。3項(xiàng)指標(biāo)X，Y和Z分別表示數(shù)學(xué)推理能力，空間想象能力和語言理解能力。其得分如下，選擇合適的統(tǒng)計(jì)方法對應(yīng)聘者進(jìn)行分類。應(yīng)聘者12345678910X28181121262016142422Y29232223292322232927Z28181622262222242424一、什么是聚類分析我們直觀地來看，這個分類是否合理？計(jì)算4號和6號得分的離差平方和：

(21-20)2+(23-23)2+(22-22)2=1

計(jì)算1號和2號得分的離差平方和：

(28-18)2+(29-23)2+(28-18)2=236

計(jì)算1號和3號得分的離差平方和為482，由此可見一般，分類可能是合理的，歐氏距離很大的應(yīng)聘者沒有被聚在一起。由此，我們的問題是如何來選擇樣品間相似的測度指標(biāo)，如何將有相似性的類連接起來？聚類分析根據(jù)一批樣品的許多觀測指標(biāo)，按照一定的規(guī)則具體地計(jì)算一些樣品或一些參數(shù)(指標(biāo))的相似程度，把相似的樣品或指標(biāo)歸為一類，把不相似的歸為一類。

例如對上市公司的經(jīng)營業(yè)績進(jìn)行分類；據(jù)經(jīng)濟(jì)信息和市場行情，客觀地對不同商品、不同用戶及時地進(jìn)行分類。又例如當(dāng)我們對企業(yè)的經(jīng)濟(jì)效益進(jìn)行評價(jià)時，建立了一個由多個指標(biāo)組成的指標(biāo)體系，由于信息的重疊，一些指標(biāo)之間存在很強(qiáng)的相關(guān)性，所以需要將相似的指標(biāo)聚為一類，從而達(dá)到簡化指標(biāo)體系的目的。二、常見的相似性測度（一）距離設(shè)和是第和個樣品的觀測值，則二者之間的距離為：明氏距離歐氏距離馬氏距離（二）相關(guān)系數(shù)設(shè)和是第和個樣品的觀測值，則二者之間的相似測度為:其中三、系統(tǒng)聚類方法基本思想：

開始將n個樣品各自作為一類，并規(guī)定樣本之間的距離和類與類之間的距離，然后將距離最近的兩類合并成為一個新類，計(jì)算新類與其他類的距離；重復(fù)進(jìn)行兩個最近類的合并，每次減少一類，直至所有的樣品合并為一類。

1、根據(jù)樣品的特征，規(guī)定樣品之間的距離，共有個。將所有列表，記為D(0)表，該表是一張對稱表。

2、選擇D(0)表中最小的非零數(shù)，不妨假設(shè)，于是將和合并為一類，記為。

3、利用遞推公式計(jì)算新類與其它類之間的距離。分別刪除D(0)表的第p，q行和第p，q列，并新增一行和一列添上的結(jié)果，產(chǎn)生D(1)

表。（一）聚類的一般算法4、對D(1)重復(fù)上述對D(0)的兩步得D(2)

，如此下去直至所有元素合并為一類。000

1、最短距離法設(shè)抽取五個樣品，每個樣品只有一個變量，它們是1，2，3.5，7，9。用最短距離法對5個樣品進(jìn)行分類。首先采用絕對距離計(jì)算距離矩陣：

0

10

2.51.50

653.50

875.520（二）各種聚類方法D(0)然后和被聚為新類，得：

0

1.50

53.50

75.520D(1)

2、最長距離法用最長距離法對5個樣品進(jìn)行分類。首先采用絕對距離計(jì)算距離矩陣：

0

10

2.51.50

653.50

875.520D(0)然后和被聚為新類，得：

0

2.50

63.50

85.520

0

10

6.252.250

362512.250

644930.2540用中間距離法對5個樣品進(jìn)行分類。首先采用絕對距離計(jì)算距離平方矩陣：

3、中間距離法

0

40

30.2512.250

56.2530.25404、可變法

如果讓中間距離法的遞推公式前兩項(xiàng)的系數(shù)依賴于某個參數(shù)，則可推廣為更一般的形式，遞推公式為：

用上式作為遞推公式的系統(tǒng)聚類法稱為可變法。

5、類平均法類平均法定義類與類之間的平方距離是樣品對之間平方距離的平均值。

0

10

6.252.250

362512.250

644930.2540然后和被聚為新類，得：

0

4.250

30.2512.250

56.2530.2540

6、可變類平均法

類平均法的遞推公式中，沒有反映Gp類和Gq類的距離有多大，進(jìn)一步將其改進(jìn)，加入D2Pq，并給定系數(shù)<1，則類平均法的遞推公式改為：

用此遞推公式進(jìn)行聚類就是可變類平均法。

重心法，也稱為樣品的均值法。設(shè)Gp和Gq

為兩個類分別為Gp和Gq的重心，類與類之間的距離定義為兩個類重心（類內(nèi)樣品平均值）間的平方距離。7、重心法設(shè)某一步Gp和Gq的重心分別為和，類內(nèi)的樣品數(shù)分別為np和nq，如果要把Gp和Gq合并為Gr類，則Gr類的樣品數(shù)nr=np+nq，Gr類的重心為和的加權(quán)算術(shù)平均數(shù)：遞推公式為：8、離差平方和法

(Ward方法)如和為一類，則離差平方和

如和為一類，則離差平方和

和被聚為新類，重心為

類中各樣品到類重心的平方歐式距離之和稱為（類內(nèi)）的離差平方和。

類似于方差分析的想法，如果類分得恰當(dāng)，同類內(nèi)的樣品之間的離差平方和應(yīng)較小，而類間的離差平方和應(yīng)當(dāng)較大。

離差平方和法的思路是，當(dāng)k固定時，選擇使離差平方和S達(dá)到最小的分類。先讓n個樣品各自成一類，然后縮小一類，每縮小一類離差平方和就要增大，選擇使S2增加最小的兩類合并，直到所有的樣品歸為一類為止。其中是由Gp和Gq合并成的Gr類的類內(nèi)離差平方和?？梢宰C明離差平方和的聚類公式為（三）確定類的個數(shù)

在聚類分析過程中類的個數(shù)如何來確定才合適呢？這是一個十分困難的問題，人們至今仍未找到令人滿意的方法。但是這個問題又是不可回避的。下面我們介紹幾種方法。

1、給定閥值——通過觀測聚類圖，給出一個合適的閥值T。要求類與類之間的距離要超過T值。例如在圖6.3.1中,我們給定T=3.3，當(dāng)聚類時，類間的距離已經(jīng)超過了3.3，則聚類結(jié)束?？傠x差平方和的分解2、統(tǒng)計(jì)量如果著些樣品被分成兩類

統(tǒng)計(jì)量其中T是數(shù)據(jù)的總離差平方和，是組內(nèi)離差平方和。比較大，說明分G個類時類內(nèi)的離差平方和比較小，也就是說分G類是合適的。但是，分類越多，每個類的類內(nèi)的離差平方和就越小，也就越大；所以我們只能取合適的G，使得足夠大，而G本生很小，隨著G的增加，的增幅不大。比如，假定分4類時，=0.8；下一次合并分三類時，下降了許多，=0.32，則分4類是合適的。

3、偽F統(tǒng)計(jì)量的定義為偽F統(tǒng)計(jì)量用于評價(jià)聚為G類的效果。如果聚類的效果好，類間的離差平方和相對于類內(nèi)的離差平方和大，所以應(yīng)該取偽F統(tǒng)計(jì)量較大而類數(shù)較小的聚類水平。

PseudoFStatistic0102030405060708090100110120NumberofClusters123456789101112131415161718194、偽統(tǒng)計(jì)量的定義為其中和分別是的類內(nèi)離差平方和，是將K和L合并為第M類的離差平方和

=--為合并導(dǎo)致的類內(nèi)離差平方和的增量。用它評價(jià)合并第K和L類的效果，偽統(tǒng)計(jì)量大說明不應(yīng)該合并這兩類，應(yīng)該取合并前的水平。四、系統(tǒng)聚類法的基本性質(zhì)（一）單調(diào)性在聚類分析過程中，并類距離分別為Dk（k=1，2，3，…）若滿足，則稱該聚類方法具有單調(diào)性?？梢宰C明除了重心法和中間距離法之外，其他的系統(tǒng)聚類法均滿足單調(diào)性的條件。（二）空間的濃縮和擴(kuò)張

1、定義矩陣的大小設(shè)同階矩陣D（A）和D（B），如果D（A）的每一個元素不小于D（B）的每一個元素，則記為。

2、空間的濃縮和擴(kuò)張?jiān)O(shè)有兩種系統(tǒng)聚類法A和B，他們在第i步的距離矩陣分別為Ai和Bi（I=1，2，3…），若Ai>Bi

，則稱第一種方法A比第二種方法B使空間擴(kuò)張，或第二種方法比第一種方法濃縮。

3、方法的比較

D（短）D（平），D（重）D（平）；

D（長）D（平）；當(dāng)，D（變平）D（平）；當(dāng)，D（變平）D（平）。五、主要的步驟1、選擇變量（1）和聚類分析的目的密切相關(guān)（2）反映要分類變量的特征（3）在不同研究對象上的值有明顯的差異（4）變量之間不能高度相關(guān)2、計(jì)算相似性相似性是聚類分析中的基本概念，他反映了研究對象之間的親疏程度，聚類分析就是根據(jù)對象之間的相似性來分類的。有很多刻畫相似性的測度。

3、聚類選定了聚類的變量，計(jì)算出樣品或指標(biāo)之間的相似程度后，構(gòu)成了一個相似程度的矩陣。這時主要涉及兩個問題：（1）選擇聚類的方法（2）確定形成的類數(shù)4、聚類結(jié)果的解釋和證實(shí)

對聚類結(jié)果進(jìn)行解釋是希望對各個類的特征進(jìn)行準(zhǔn)確的描述，給每類起一個合適的名稱。這一步可以借助各種描述性統(tǒng)計(jì)量進(jìn)行分析，通常的做法是計(jì)算各類在各聚類變量上的均值，對均值進(jìn)行比較，還可以解釋各類產(chǎn)別的原因。

如果是變量聚類分析，聚類分析做完之后，各類中仍有較多的指標(biāo)。也就是說聚類分析并沒有達(dá)到降維的目的。這就需要在每類中選出一個代表指標(biāo)，具體做法是：假設(shè)某類中有個指標(biāo)，首先分別計(jì)算類內(nèi)指標(biāo)之間的相關(guān)指數(shù)，然后計(jì)算某個指標(biāo)與類內(nèi)其他指標(biāo)之間相關(guān)指數(shù)的平均數(shù)，即取最大的，做為該類的代表。例1某公司下屬30個企業(yè)，公司為了考核下屬企業(yè)的經(jīng)濟(jì)效益，設(shè)計(jì)了8個指標(biāo)。為了避免重復(fù)，需要對這8個指標(biāo)進(jìn)行篩選，建立一個恰當(dāng)?shù)慕?jīng)濟(jì)效益指標(biāo)體系。通過計(jì)算30個企業(yè)8個指標(biāo)的相關(guān)系數(shù)距離，數(shù)據(jù)是1-r2。得如下表:

x1x2

x3

x4x5

x6

x7

x8

x10

0.600

0.430.460

0.470.450.120

0.570.450.230.220

0.380.400.210.290.220

0.310.790.650.700.800.660

0.450.450.270.230.140.190.770試用將它們聚類。x2

x3x4x5

x6

x7

x8例2

根據(jù)美國等20個國家和地區(qū)的信息基礎(chǔ)設(shè)施的發(fā)展?fàn)顩r進(jìn)行分類。Call—每千人擁有的電話線數(shù)；movel—每千人戶居民擁有的蜂窩移動電話數(shù)；fee—高峰時期每三分鐘國際電話的成本；comp—每千人擁有的計(jì)算機(jī)數(shù)；mips—每千人計(jì)算機(jī)功率（每秒百萬指令）；

net—每千人互聯(lián)網(wǎng)絡(luò)戶主數(shù)。

國家callmovel

fee

comp

mips

netmeiguo631.6161.90.364032607335.34riben498.4143.23.57176102236.26deguo557.670.60284ruidian684.1281.81.42461666029.39ruishi64493.51.982341362122.68xinjiapo498.4147.52.52841357813.49taiwan469.456.13.6811969111.72hanguo434.5733.369957951.66baxi81.916.33.02198760.52zhili138.68.201.43114111.28moxige92.29.82.613117510.35eluosi174.955.122411010.48bolan1696.53.684017961.45xiongyali262.249.42.666830673.09malaixiya195.588.44.195327341.25taiguo78.627.84.952216620.11yindu13.60.306.2821010.01faguo559.142.91.27201117024.76yingguo521.10122.50.982481446111.91PseudoFStatistic0102030405060708090100110120NumberofClusters12345678910111213141516171819動態(tài)聚類

一、思想

系統(tǒng)聚類法是一種比較成功的聚類方法。然而當(dāng)樣品數(shù)量十分龐大時，則是一件非常繁重的工作，且聚類的計(jì)算速度也比較慢。比如在市場抽樣調(diào)查中，有4萬人就其對衣著的偏好作了回答，希望能迅速將他們分為幾類。這時，采用系統(tǒng)聚類法就很困難，而動態(tài)聚類法就會顯得方便，適用。動態(tài)聚類解決的問題是：假如有n個樣品，要把它們分類，使得每一類內(nèi)的元素都是聚合的，并且類與類之間還能很好地區(qū)別開。動態(tài)聚類適用于大型數(shù)據(jù)。選擇凝聚點(diǎn)分類修改分類分類是否合理分類結(jié)束YesNo（a）空間的群點(diǎn)(b)任取兩個聚核

(c)第一次分類(d)求各類中心

(e)第二次分類用一個簡單的例子來說明動態(tài)聚類法的工作過程。例如我們要把圖中的點(diǎn)分成兩類?？焖倬垲惖牟襟E：

1、隨機(jī)選取兩個點(diǎn)和作為聚核。

2、對于任何點(diǎn)，分別計(jì)算

3、若，則將劃為第一類，否則劃給第二類。于是得圖（b）的兩個類。

4、分別計(jì)算兩個類的重心，則得和，以其為新的聚核，對空間中的點(diǎn)進(jìn)行重新分類，得到新分類。二、方法（這里僅僅介紹k—均值法。）假定一樣品集，其中每個樣品取指標(biāo)。第一步：隨機(jī)選取K個點(diǎn)作為個聚核（為計(jì)算收斂更快，實(shí)際操作時可根據(jù)經(jīng)驗(yàn)或直觀判斷選取更有利的K個聚核），記為，根據(jù)，把中的點(diǎn)分為K類，記為，其中第二步：由出發(fā)，計(jì)算新的聚核

其中，作新的分類四、算法終止的標(biāo)準(zhǔn)我們有必要給出一個算法終止的標(biāo)準(zhǔn)。五、動態(tài)聚類步驟為：第一，選擇若干個觀測值點(diǎn)為“凝聚點(diǎn)”；第二，可選擇地，通過分配每個“凝聚點(diǎn)”最近的類里來形成臨時分類。每一次對一個觀測值點(diǎn)進(jìn)行歸類，“凝聚點(diǎn)”更新為這一類目前的均值；第三，可選擇地，通過分配每個“凝聚點(diǎn)”最近的類里來形成臨時分類。所有的觀測值點(diǎn)分配完后，這些類的“凝聚點(diǎn)”用臨時類的均值代替。該步驟可以一直進(jìn)行直到“凝聚點(diǎn)”的改變很小或?yàn)榱銜r止；第四，最終的分類有分配每一個觀測到最近的“凝聚點(diǎn)”而形成。例我國經(jīng)濟(jì)發(fā)展的總目標(biāo)是到2000年人民生活達(dá)到小康標(biāo)準(zhǔn)，因此，我們來了解各地區(qū)目前對小康生活質(zhì)量的實(shí)現(xiàn)程度。對各地區(qū)實(shí)現(xiàn)小康生活質(zhì)量的狀況進(jìn)行綜合評價(jià)，對各級政府部