1、第四章第四章 聚類分析聚類分析相似性度量系統(tǒng)聚類法動態(tài)聚類法聚類分析聚類分析與判別分析判別分析的區(qū)別：事先已知研究對象可以分成哪幾種類別。需要擁有一批事先已經(jīng)知道類別的歷史樣本，參考這些樣本建立判別函數(shù)，對某一新的樣品，判斷其分類。：事先不知道研究對象可以分成哪些類別。聚類分析要做的就是根據(jù)數(shù)學(xué)方法定量地確定這些樣品之間的親疏關(guān)系，按照相似程度來對他們進(jìn)行分類。聚類分析舉例：例如，對一批環(huán)流形勢圖根據(jù)它們的相似程度進(jìn)行分類（這些環(huán)流形勢圖所造成的預(yù)報(bào)量的結(jié)果相同或未知，因此無法通過預(yù)報(bào)量對其進(jìn)行分類，只能根據(jù)這些圖像的相似程度來劃分它們的類別，這就是聚類分析的內(nèi)容）。第四章1 相似性的度量設(shè)某

2、研究對象有m個(gè)指標(biāo)(因子)， 若觀測了n次(找到了n個(gè)樣品)， 這mn個(gè)記錄所構(gòu)成的資料陣為：111212122212.=.nnmmmnxxxxxxxxxXMMMM與判別分析類似， X中的任意一列表示一個(gè)樣品，每個(gè)樣品包括m個(gè)成員。從向量空間的觀點(diǎn)來描述，每個(gè)樣品就是m維空間的一個(gè)點(diǎn)。聚類分析聚類分析就是要對這n個(gè)樣品進(jìn)行分類，首先要衡量任意兩個(gè)樣品之間的接近程度，有兩類指標(biāo)：(1) 距離系數(shù)距離系數(shù)(2) 相似系數(shù)相似系數(shù)任一樣品i可以看成是m維空間中的一個(gè)點(diǎn)，用向量xj=x1j , x2j, , xmjT表示，任兩個(gè)樣品xi與xj之間的距離記為dij，距離具有如下四條性質(zhì)：q dij 0,

3、 對于一切i,jq dij=0, 當(dāng)兩個(gè)樣品的各項(xiàng)指標(biāo)都相等，即xi=xj時(shí)q dij=dji, 對于一切i與jq dijdik+dkj, 對于一切i, j, k111212122212.=.nnmmmnxxxxxxxxxXMMMM(1)(1)絕對距離絕對距離兩樣品各因子之差的絕對值之和，即X矩陣中兩列向量作差、取絕對值、然后求和。1| ,( ,1,2,., )mijkikjkdxxi jn特別地，當(dāng)m=2時(shí)，平面上各點(diǎn)與原點(diǎn)（0, 0T）的絕對距離的等值線如右圖所示：-4-3-2-101234-4-3-2-101234135x1x2（2 2）歐氏距離）歐氏距離X矩陣中兩列向量xi和xj的差向

4、量各元素的平方和的平方根。12T21()() () ,( ,1,2,., )mijkikjijijkdxxi jnxxxx注意：上述兩種距離的大小與各變量的單位有關(guān)，為消除個(gè)變量單位的影響，需要先將數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，然后再計(jì)算距離。（3）馬氏）馬氏(Mahalanobis)距離距離馬氏距離與歐式距離的不同之處是它考慮到了各因子之間的聯(lián)系，又稱為協(xié)方差距離。2T1()()ijijijdxxVxxT1=1dddnVVX XXX其中， 為各因子的協(xié)方差陣，可用樣本計(jì)算協(xié)方差陣來估計(jì)，即：（為 的距平資料陣）。由馬氏距離的表達(dá)式可知，若各因子變量已經(jīng)過標(biāo)準(zhǔn)化處理(方差為1)且各因子相互獨(dú)立(不同因子

5、的協(xié)方差為0)，于是協(xié)方差陣V為單位陣單位陣，這時(shí)的馬氏距這時(shí)的馬氏距離就是歐氏距離的平方。離就是歐氏距離的平方。馬氏距離有個(gè)重要性質(zhì)是：已經(jīng)消除了變量單位的影響。即：利用距平數(shù)據(jù)和標(biāo)準(zhǔn)化數(shù)據(jù)算得的馬氏距離是相同的。例：已知二維正態(tài)總體G的分布為：G N ( , V), 并且：010.900.91G N （，）-1225.26-4.74=-4.745.2611(A)1 11.053(B)112011ijijdd -1-1VVV馬氏距離：，代入公式求得A與B距離均值的馬氏距離分別為：；110A=B=1-10 請分別計(jì)算和到均值的距離。222222( )112;( )1( 1)2ijijdAdB

6、若采用歐氏距離： 由二元正態(tài)分布的密度公式知本例的概率密度函數(shù)為：2212112211( ,)exp(1.8)0.3820.19f x xxx xx于是，A、B兩點(diǎn)處的概率密度值分別為：f(1,1)=0.2157; f(1,-1)=0.00001658; 密度值最大的均值處為：f (0,0) = 0.3651 所以，A點(diǎn)應(yīng)當(dāng)距離均值更近。2T111/2/222111( )exp()()=exp()22(2 )|(2 )|mmDf VxVxxV馬氏距離與多元正態(tài)分布的概率密度函數(shù)存在如下關(guān)系：圖解馬氏距離與歐氏距離的區(qū)別12010.900.9100 xxnN x某研究對象含有兩個(gè)因子 =， 個(gè)樣

7、品繪成散點(diǎn)圖(黃色圓點(diǎn))對于服從二元正態(tài)分布（，），那么，馬氏距空間中各點(diǎn)與均值的的等值線為右離圖所示：如果對該例計(jì)算歐氏距離的平方歐氏距離的平方，等值線如右圖所示：可見，歐氏距離與各因子變量之間的相關(guān)性(或協(xié)方差)無關(guān)。-4-3-2-101234-4-3-2-10123413510 x1x2-4-3-2-101234-4-3-2-10123413510 x1x2夾角余弦夾角余弦(相似系數(shù)相似系數(shù))xi與xj兩個(gè)樣品是m維空間中的兩個(gè)列向量，則xi與xj之間的相似程度可用兩個(gè)向量之間的夾角余弦來表示:T12211cos|mkikjijijkijmmijijkikjkkx xxxxxx xxxx

8、xcosij的取值范圍為-1, 1。相關(guān)系數(shù)相關(guān)系數(shù)xi和xj兩樣品的的相關(guān)系數(shù)為：12211()()()()mijkikjkijmmijkikjkkxxxxrxxxx如果X已經(jīng)是中心化(距平)或標(biāo)準(zhǔn)化的數(shù)據(jù)，12211= cosmkikjkijijmmkjkjkkx xrxx12iiimixxxxM可見可見，對于中心化數(shù)據(jù)來說，對于中心化數(shù)據(jù)來說，相關(guān)系數(shù)等于夾角相關(guān)系數(shù)等于夾角余弦。余弦。那么，相關(guān)系數(shù)的公式變?yōu)椋?1mikikxmx即：0夾角余弦多用于：比較多個(gè)多個(gè)變量的兩組兩組空間分布的相似程度。相關(guān)系數(shù)多用于：比較兩個(gè)兩個(gè)變量多次多次時(shí)間觀測(即兩個(gè)時(shí)間序列)的相似程度。第四章2 系

9、統(tǒng)聚類法“系統(tǒng)聚類系統(tǒng)聚類”方法又稱“逐級歸并”法，種類數(shù)目由多到少進(jìn)行歸并，最終把所有樣品歸為一類。其思想是：q 最開始，把n個(gè)樣品各成一類，即G1，G2，, Gn類，q 然后兩兩計(jì)算類與類之間的距離，選擇距離最小的兩類合并成新的一類(新類中含有兩個(gè)樣品)，q 然后再計(jì)算新類與其他類之間的距離，q 再找距離最小的兩類合并，如此進(jìn)行下去，直至所有樣品都合成一大類為止。第1節(jié)所介紹的距離系數(shù)僅是針對兩個(gè)樣品兩個(gè)樣品而言，不解決類與類之間的距離類與類之間的距離。類與類之間距離類與類之間距離的表示方法可有多種選擇，本節(jié)主要介紹的表示方法可有多種選擇，本節(jié)主要介紹“最短距離最短距離”法和法和“離差平方

10、和離差平方和”法。法。通過樣品歸并產(chǎn)生新類別之后，該類別內(nèi)部會包含多個(gè)樣品包含多個(gè)樣品，這時(shí)該如何計(jì)算類與類之間的距離類與類之間的距離？最短距離法設(shè)n個(gè)樣品已經(jīng)合并為k類，記為G1，G2，, Gk, 分別含有n1, n2, , nk個(gè)樣品，n1+n2+nk=n, dij是任意兩個(gè)樣品xi與xj之間的距離，則任意兩個(gè)類別Gp與Gq之間的最短距離為：,min pqpqiji Gj GDd即: Dpq取Gp和Gq兩類之間兩兩樣品距離的最小值。至于兩個(gè)樣品的距離dij ，可以采用絕對距離、歐氏距離或馬氏距離等多種選擇。n個(gè)樣品的最短距離聚類法最短距離聚類法的步驟：（任選一種距離，如“歐氏距離”，作為兩

11、個(gè)樣品之間的距離樣品之間的距離）：(1) 最開始，每個(gè)樣品作為一個(gè)類別（共n類），計(jì)算兩兩類別之間的距離，構(gòu)成一個(gè)距離矩陣，記為D(0) 。(2) 在D(0)中選擇距離最小的兩個(gè)類別進(jìn)行合并，例如Gp與Gq兩類的距離Dpg最小，則將Gp與Gq二類合并成新類，記為Gr，即Gr=Gp，Gq。(3) 繼續(xù)計(jì)算兩兩類別的距離，得到距離陣D(1) ，在計(jì)算Dr與其他類別Gk之間的距離時(shí)，采取最短距離法，公式為：(4) 對D(1)重復(fù)上述(2)(3)步驟，得到D(2), 繼續(xù)進(jìn)行下去直到所直到所有樣品歸并成一類有樣品歸并成一類為止。,minminmin,minrkpkqkrkijijiji Gj Gi G

12、j Gi Gj GDddd“最短距離法最短距離法”聚類舉例聚類舉例 （P114 例例1）設(shè)有6次觀測(n=6)的樣本: 1, 2, 5, 7, 9, 10。每個(gè)樣品的因子(指標(biāo))只有一個(gè)（m=1），試用最短距離法進(jìn)行聚類，樣品距離使用“絕對距離”。D(0)G1G2G3G4G5G6G1G21G343G4652G58742G698531(1)： 計(jì)算兩兩樣品之間的距離，組成距離矩陣D(0):(2)：分析D(0), 發(fā)現(xiàn)距離最小的兩類是D12=D56=1, 于是，G1與G2合并成G7， G5與G6合并成G8，之后，共有4類。(3)：重新計(jì)算各類的距離，得到矩陣D(1)。D(1)G3G4G7G8G3G

13、42G735G8427(4)：分析D(1), 找到距離最短的兩個(gè)類別，D34=D48=2, 所以把G3、G4與G8成新類G9,目前只剩2類: G7與G9。(5) ：把G7與G9合并成G10。D(2)G7G9G7G93最短距離法 聚類圖最長距離法只是，只是，類與類之間的距離，用兩兩樣品之間的最長距離兩兩樣品之間的最長距離來表示，即：,max pqpqiji Gj GDd最長距離法聚類的步驟與最短距離法完全相同完全相同，即：各樣品先自成一類，然后將距離最小距離最小的兩類合并。設(shè)某一步將Gp和Gq合并為Gr， 則Gr與其他類Gk的距離為：然后尋找距離最小的兩類進(jìn)行合并，直到所有樣品合并為一類為止。,

14、maxmaxmax,maxrkpkqkrkijijiji Gj Gi Gj Gi Gj GDddd離差平方和法離差平方和法是另一種系統(tǒng)聚類法，其原則是： 同一類別內(nèi)部各樣品之間的離差平方和應(yīng)該較小，類與類之間的離差平方和應(yīng)該較大。這n個(gè)樣品可分為k類， G1， G2，, Gk，每類的樣品數(shù)為ng(g=1,2, k)，總和為n：設(shè)有m個(gè)指標(biāo)(因子)，觀測到容量為n的樣本樣本，該資料陣可記為X(m行n列)。X的的每一列稱為一個(gè)每一列稱為一個(gè)“樣品樣品” 。111212122212.=.nnmmmnxxxxxxxxxXMMMM1Gggnn111212122212.=.ggggggngggnggggm

15、mmnxxxxxxxxxXMMMM對于第g類的資料陣（m行ng列，從X中抽取ng列），可以寫為Xg ：則第g類的類內(nèi)離差平方和可以寫為Sg：12=gtgggttgtgmtxxgttxxXx其中，向量為第 類的第 個(gè)樣品，即的第 列:T1() ()gngggggtttSxxxx111221111=1gggngtgtgnggggttgggnmgmttgxnxxxgnxxnxXxMM為的均值列向量，即每行的平均值，表示第 類樣品的重心，那么，k個(gè)類別總總的類內(nèi)離差平方和的類內(nèi)離差平方和就是對Sg求和(g=1,2,k)：即T11() ()gnkggggttgtSxxxx當(dāng)固定一個(gè)k時(shí)，我們希望：S達(dá)到

16、極小。達(dá)到極小。Sg其實(shí)就是第g類內(nèi)部各樣品與其重心的歐氏距離的平方再求和，也即：Xg的距平資料陣各元素的平方和。把n個(gè)樣品分成k類，分法非常多，要比較所有的分法使得S最小，不太現(xiàn)實(shí)。因此，只好放棄在一切分類中尋求S的極小值，提出使S達(dá)到局部極小的辦法。設(shè)Gp與Gq兩類的類內(nèi)離差平方和分別為Sp和Sq，若Gp與Gq合并成Gr類后的離差平方和為Sr，則此次合并導(dǎo)致總離差平方和的增量離差平方和的增量為：2()pqrpqDSSS聚類的原則是：選擇使D2pq最小的兩類合并，因此D2pq可認(rèn)為是兩類之間的距離，可以證明D2pq可由Gp與Gq兩類的重心之差的平方和來表示：2T() ()pqpqpqpqpq

17、n nDnnxxxx當(dāng)Gp與Gq合并成新類Gr后，Gr與其他類別Gk的距離，還可通過遞推公式來計(jì)算：2222kpkqkkrkpkqpqrkrkrknnnnnDDDDnnnnnn22TT111()()=()()1+12ijijijijijijijijDDxxxxxxxxxx在 聚 類 開 始 時(shí) ， 各 樣 品 自 成 一 類 ， 第 類 與 第 類 之 間 的為 ：恰 好 是和兩 樣 品 之 間 歐 氏 距 離 平 方 的 1/2“離差平方和”聚類法舉例設(shè)有設(shè)有6次觀測次觀測(n=6)的樣本的樣本: 1, 2, 5, 7, 9, 10。每個(gè)樣品的因子。每個(gè)樣品的因子(指標(biāo)指標(biāo))只有一個(gè)只有一個(gè)

18、（m=1），試用），試用“離差平方和離差平方和”法進(jìn)行系統(tǒng)聚類。法進(jìn)行系統(tǒng)聚類。首先，將n個(gè)樣品各自成一類，然后根據(jù)公式：計(jì)算兩兩類別之間的D2pq, 構(gòu)成陣D(0)2T() ()pqpqpqpqpqn nDnnxxxxD(0)G1G2G3G4G5G6G1G20.5G38.04.5G418.012.52.0G532.024.58.02.0G640.532.012.54.50.51. 由D(0)可知，若將G1和G2合并、G5與G6合并，總的離差平方和的增加量將最小，因此將G1和G2合并成新類G7, 把G5與G6合并成G8。D(1)G3G4G7G8G3G42.0G78.220.2G813.54.2

19、64.0合并之后，總共有4類，分別是：G3x3, G4x4, G7x1, x2, G8x5, x6計(jì)算這四類的距離陣D(1)如左圖所示2. D(1)中G3與G4的距離最小，將G3與G4合并成G10，目前共有三類：G7x1,x2, G8x5,x6, G10 x3,x4然后計(jì)算兩兩之間的距離陣D(2)如右圖所示：D(2)G7G8G10G7G864.0G1020.312.33. D(2)中G8與G10的距離最小，因此將G8與G10合并成G11，這時(shí)共有兩類，所含的樣品分別是：G7x1,x2, G11x3,x4, x5, x6然后計(jì)算他們之間的距離陣D(3)如右圖所示：D(3)G7G11G7G1152

20、.14，最后， 把剩下的兩類G7和G11合并成一類。修改p117表4.5第四章3 動態(tài)聚類法系統(tǒng)聚類法：系統(tǒng)聚類法：樣品劃給某一類之后不能再改變，無法考慮若干樣品被綜合在一起之后相互之間的相似關(guān)系。另外，類間距離陣D在n很大時(shí)占用內(nèi)存太多。動態(tài)聚類法：動態(tài)聚類法：克服了以上缺點(diǎn)，先給一個(gè)粗糙的初始分類，然后利用某種原則進(jìn)行修改，直至“分類比較合理分類比較合理”為止；又稱為：“逐步修改聚類法”?！胺诸愂欠窈侠矸诸愂欠窈侠怼钡呐袛鄻?biāo)準(zhǔn)：如果本輪分類與上一輪分類的結(jié)果完全相同，說明已達(dá)最終分類，動態(tài)聚類停止。K-均值(K-means)聚類：固定類別的數(shù)目為固定類別的數(shù)目為k類類，所以也可稱為“定K-

21、均值聚類”。111212122212.=.nnmmmnxxxxxxxxxXMMMM定定K均值聚類步驟：均值聚類步驟：q1. 任意選取(或依據(jù)其他某種原則選取)k個(gè)有代表性的樣品各自成為一類，稱為“凝聚點(diǎn)”。q2. 依次計(jì)算各個(gè)樣品與k個(gè)凝聚點(diǎn)之間的距離(可任選一種距離計(jì)算，如“絕對距離”或“歐氏距離” 等)。q3. 根據(jù)最近距離準(zhǔn)則，將余下的n-k個(gè)樣品逐個(gè)歸入k個(gè)凝聚點(diǎn)作為初始分類，并計(jì)算各類的重心(均值向量)作為新的凝聚點(diǎn)。q4. 將n個(gè)樣品重復(fù)2、3步驟，得到調(diào)整后的k類，如果此步之后n個(gè)樣品的分類結(jié)果與上一步的歸類完全一致，則停止運(yùn)算；否則重復(fù)步驟4.設(shè)有m個(gè)指標(biāo)n個(gè)樣品(n次觀測)的數(shù)據(jù)排列成如圖所示的資料陣X，先對X進(jìn)行標(biāo)準(zhǔn)化處理。一個(gè)凝聚點(diǎn)是一列向量，類似一個(gè)樣品P118例3，有一組4個(gè)指標(biāo)10次觀測的樣本數(shù)據(jù)，并已標(biāo)準(zhǔn)化(表4.6),試用定K-均值法進(jìn)行聚類，把10個(gè)樣品分成5類。1. 選取前5個(gè)樣品作為凝聚點(diǎn)。2. 計(jì)算各個(gè)樣品與凝聚點(diǎn)之間的距離，結(jié)果如表4.7。3. 根據(jù)樣品之間最小距離的原則，對樣品進(jìn)行歸類，4. 計(jì)算當(dāng)前各類別的重心（以作為新的凝聚點(diǎn)），即：計(jì)算各類別內(nèi)部每個(gè)指標(biāo)的平均值（每個(gè)類別對應(yīng)一個(gè)均值列向量）。類別類別12345樣品x1, x7x2x3