R語言聚類分析分析

1、聚類的基本步驟 什么是類：粗略地講，相似樣品（或指標(biāo)）的集合成為類。 聚類的兩個基本步驟1. 鄰近度度量的選擇：檢驗(yàn)每一對觀測值（對象）取值的相似性。一個相似性（鄰近度）的度量定義為對象間的“接近”程度。越接近越同質(zhì)。2. 組別構(gòu)建算法的選擇：根據(jù)鄰近度的度量，被分配到各組的對象間的差別變大，而被分配到同一組的觀測值應(yīng)盡可能接近。關(guān)于聚類：聚類應(yīng)用領(lǐng)域 倉儲管理：倉儲管理：對不同類的商品在入庫過程中進(jìn)行聚類儲存 營銷營銷: : 發(fā)現(xiàn)客戶集群并進(jìn)行直銷和重組 天文天文: : 發(fā)現(xiàn)相似恒星群以及星系群 地震研究地震研究: : 觀測到的地震震源應(yīng)聚集在大陸斷層帶 基因分析基因分析: : 發(fā)現(xiàn)具有相似

2、表達(dá)式的基因群 關(guān)于聚類：探索性的分析方法 作為一種探索性技術(shù)，EVERITT (1993)評價到：“聚類方法基本上是用于產(chǎn)生一些假設(shè)而不是檢驗(yàn)假設(shè)”。 有多少作聚類分析的人就有多少聚類方法。聚類的分類： 劃分聚類方法劃分聚類方法 層次聚類方法層次聚類方法 密度聚類方法密度聚類方法 網(wǎng)格聚類方法網(wǎng)格聚類方法 模型聚類方法模型聚類方法在基于劃分的聚類中，任務(wù)就是將數(shù)據(jù)劃分成K個不相交的點(diǎn)集，使每個子集中的點(diǎn)盡可能同質(zhì)。基于劃分的方法 ，其代表算法有 k-means算法、 K-medoids等劃分聚類方法K-MEANS 算法 K-MEANS 算法基本步驟1.從 N個數(shù)據(jù)對象任意選擇 K 個對象作為

3、初始聚類中心；2.根據(jù)每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分； 3.重新計算每個(有變化)聚類的均值(中心對象)； 4.計算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時，則算法終止；如果條件不滿足則回到步驟2。K-MEANS優(yōu)缺點(diǎn) 主要優(yōu)點(diǎn)： 是解決聚類問題的一種經(jīng)典算法，簡單、快速。 對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。 當(dāng)結(jié)果簇是密集的，它的效果較好。 主要缺點(diǎn) 在簇的中心（平均值）被定義的情況下才能使用。 必須事先給出K（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導(dǎo)致不同結(jié)果。 不適合于發(fā)現(xiàn)非凸面形

4、狀的簇或者大小差別很大的簇。而且，它對于“躁聲”和孤立點(diǎn)數(shù)據(jù)是敏感的。層次聚類方法 層次聚類方法對給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某種條件滿足為止。具體又可分為： 凝聚的層次聚類：一種自底向上的策略，首先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到某個終結(jié)條件被滿足。 分裂的層次聚類：采用自頂向下的策略，它首先將所有對象置于一個簇中，然后逐漸細(xì)分為越來越小的簇，直到達(dá)到了某個終結(jié)條件。 層次凝聚的代表是AGNES算法。層次分裂的代表是DIANA算法。層次聚類優(yōu)缺點(diǎn) 層次聚類方法是不可逆的，也就是說，當(dāng)通過凝聚式的方法將兩組合并后，無法通過分裂式的辦法再將其分離到之前的狀態(tài)，反之

5、亦然。 另外，層次聚類過程中調(diào)查者必須決定聚類在什么時候停止，以得到某個數(shù)量的分類。 在不必要的情況下應(yīng)該小心使用層次聚類方法。1、距離的定義 距離的定義有很多，但是必須遵循一定的規(guī)則。假設(shè) 表示樣本 之間的距離，則一般要求它滿足如下條件：（1） 對一切i,j都大于等于0（2） 等于0當(dāng)且僅當(dāng)i=j（3） 對一切i和j可以互換（4）如果距離的定義僅滿足前三條，則稱此距離為廣義距離。常用的距離有，明氏距離，蘭氏距離，馬氏距離，斜交空間距離，列名變量的相似性度量。 ijdjixx與ijdijdijd都成立,對一切kjidddkjikij2、常用的距離kplkjlilijxxd11)|(pljlil

6、ijxxd1明氏距離明氏距離特別地，當(dāng)k1時，即為絕對值距離絕對值距離(1) (1) 明氏距離明氏距離ixjxijd令表示樣品與的距離 npnnppxxxxxxxxx212222111211設(shè)原始數(shù)據(jù)為kplkjlilijxxd11)|(pljlilijxxd12)(明氏距離明氏距離當(dāng)k2時，即為歐氏距離歐氏距離當(dāng)k時，即為切比雪夫切比雪夫距離距離jlilplijxxd1max123452018104471055325.236.328.911.5171x2x3x3124224)(lllxxd222)5 .113 .36()510()418(歐氏距離歐氏距離切比雪夫距離切比雪夫距離lllxxd4

7、23124max8 .245 .113 .3624d計算例：明考夫斯基距離有以下兩個缺點(diǎn)： 明氏距離的數(shù)值與指標(biāo)的量綱量綱有關(guān)。當(dāng)各變量的測量值相差懸殊時，常發(fā)生“大數(shù)吃小數(shù)”的現(xiàn)象，為消除量綱的影響，通常先將每個變量進(jìn)行標(biāo)準(zhǔn)化。 明氏距離的定義沒有考慮各個變量之間相關(guān)性的影響。年齡收入家庭人口數(shù)甲3030001乙4032003222) 31 ()32003000()4030(d(2) 標(biāo)準(zhǔn)化的歐氏距離標(biāo)準(zhǔn)化的歐氏距離npnnppxxxxxxxxx212222111211設(shè)原始數(shù)據(jù)為ijd22222221111.ppjpipjijisxxsxxsxx222222211111.11jppippj

8、ijixxsxxsxxspllljlilsxx12 pppnpnnppppppppSxxSxxSxxSxxSxxSxxSxxSxxSxx222211112222221112112221211111 (3)馬氏距離馬氏距離 馬氏距離是由印度著名統(tǒng)計學(xué)家馬哈拉諾比斯(MAHALANOBIS)所定義的一種距離，其計算公式為： ijd21221112211,pjpijijipjpijijixxxxxxSxxxxxx =211jijixxSxxn馬氏距離又稱為廣義歐氏距離。n馬氏距離考慮了觀測變量之間的相關(guān)性。如果假定各變量之間相互獨(dú)立，即觀測變量的協(xié)方差矩陣是對角矩陣，此時馬氏距離就是標(biāo)準(zhǔn)化的歐氏距離

9、。n馬氏距離不受指標(biāo)量綱量綱及指標(biāo)間指標(biāo)間相關(guān)性相關(guān)性的影響 系統(tǒng)聚類法系統(tǒng)聚類法的基本思想系統(tǒng)聚類法的基本思想 先將N個樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近距離最近的兩類合并成一個新類，計算新類和其它類（各當(dāng)前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都?xì)w成一類為直至所有的樣品都?xì)w成一類為止止。 系統(tǒng)聚類法的基本步驟：系統(tǒng)聚類法的基本步驟：1. 計算n個樣品兩兩間的距離 ，記作D= 。2. 構(gòu)造n個類，每個類只包含一個樣品。3. 合并距離最近合并距離最近的兩類為一新類。4. 計算新類與各當(dāng)前類的距離計算新類與各當(dāng)前類的距

10、離。5. 重復(fù)步驟3、4，合并距離最近的兩類為新類，直到所有的類并為一類為止。6. 畫聚類譜系圖。7. 決定類的個數(shù)和類。ijd ijd1. 最短距離法最短距離法2.2. 最長距離法最長距離法3.3. 中間距離法中間距離法4.4. 重心法重心法5.5. 類平均法類平均法 6.6. 離差平方和離差平方和法（法（WardWard法法）系統(tǒng)聚類方法：系統(tǒng)聚類方法： 上述 6 種方法歸類的基本步驟一致基本步驟一致，只是類與類之間的距離類與類之間的距離有不同的定義。定義類p與q之間的距離為兩類最近樣品的距離，即 ijqjpipqdd,minxq1xp2xq2xp1pqdxq3一、最短距離法一、最短距離法

11、qrprkrddd,min設(shè)類p與 q合并成一個新類，記為k，則k與任一類r 的距離是pqkr例例 最短距離法最短距離法 設(shè)抽取5個樣品，每個樣品觀察2個指標(biāo) ， ：您每月大約喝多少瓶啤酒， ：您對“飲酒是人生的快樂”這句話的看法如何？觀察數(shù)據(jù)如下，對這5個樣品分類。1x2x12345201810447105531x2x 3.6 10.2 16.12 16.49 9.43 14.87 15.65 6 6.32 2 3.6 10.2 16.12 16.49 9.43 14.87 15.65 6 6.32 2ijdnnijdD)(1.計算5個樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），為最小，

12、245d2. 合并距離最小的兩類為新類，按順序定為第類。5 , 487.1465.15,87.14min,min524262ddd6,min534363ddd12.1649.16,12.16min,min514161ddd3、計算新類與各當(dāng)前類的距離，得距離矩陣如下：3.6 10.2 16.12 9.43 14.87 643. 9,min231373ddd87.14,min261676ddd6 . 312d 2 , 1為最小， = 6 9 .43 14.87 4、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。 43. 9,min673787ddd 636d6 , 3為最小

13、，=5、6、按聚類的過程畫聚類譜系圖 45并類距離3127、決定類的個數(shù)與類。 觀察此圖，我們可以把5個樣品分為3類， 2 , 1 35 , 4、。43. 966 . 328 ,76, 32, 15 , 4ddddx11x2112d二、最長距離法二、最長距離法定義類p與q之間的距離為兩類最遠(yuǎn)樣品的距離，即 ijqjpipqdd,max三、中間距離法三、中間距離法定義類與類之間的距離既不采用兩類之間最近的距離，也不采用兩類之間最遠(yuǎn)的距離，而是采用介于兩者之間的距離，故稱為中間距離法。 krdrpqk2222412121pqqrprkrdddd四、重心法四、重心法（CENTROID)11,x y2

14、2,xypx和qxqpxxpqdd類與類之間的距離就考慮用重心之間的距離表示。設(shè)p與q的重心分別是，則類p和q的距離為五、類平均法五、類平均法（AVERAGE)(61262524232221dddddd定義兩類之間的距離平方為這兩類元素兩兩之間距離平方的平均 piqjijqppqdnnd221pq六、差平方和法（WARD法 ） 2112221211)(nipipniiniixxxxxx)()(1XXXXinii反映樣品之間的差異程度 npnnppxxxxxxxxx212222111211設(shè)變量X的n個樣品觀察值為：n個樣品的離差平方和為：qpqSpSk設(shè)類p和q分別含有np、nq個樣品，其離差

15、平方和分別記為psqs和 直觀上容易想到把兩群樣品聚為一大群，大群的離差平方和將超過原來兩個群的離差平方和之和。 2qxpxdnnnnSSSqpqpqpk 如果將p和q并類得到新類k，則類k的離差平方和為pqs把增加的量記為定義類p和q之間的距離為：22qxpxdnnnnSdqpqppqpq設(shè)類p和q分別含有np、nq個樣品，其離差平方和分別記為psqs和動態(tài)聚類法-K均值法 系統(tǒng)聚類法是一種比較成功的聚類方法。然而當(dāng)樣本點(diǎn)數(shù)量十分龐大時，則是一件非常繁重的工作，且聚類的計算速度也比較慢。比如在市場抽樣調(diào)查中，有4萬人就其對衣著的偏好作了回答，希望能迅速將他們分為幾類。這時，采用系統(tǒng)聚類法就很

16、困難，而動態(tài)聚類法就會顯得方便，適用。 動態(tài)聚類適用于對大型數(shù)據(jù)的聚類。動態(tài)聚類法 基本思想：選取若干個樣品作為凝聚點(diǎn)，計算每個樣品和凝聚點(diǎn)的距離，進(jìn)行初始分類，然后根據(jù)初始分類計算其重心，再進(jìn)行第二次分類，一直到所有樣品不再調(diào)整為止。選擇凝聚點(diǎn)分 類修改分類分類是否合理分類結(jié)束YesNo 用一個簡單的例子來說明動態(tài)聚類法的工作過程。例如我們要把圖中的點(diǎn)分成兩類?？焖倬垲惖牟襟E： 1、隨機(jī)選取兩個點(diǎn) 和 作為凝聚點(diǎn)。 2、對于任何點(diǎn) ，分別計算 3、若 ，則將 劃為第一類，否則劃給第二類。于是得圖（ ）的兩個類。 )1 (1x)1 (2xkx),(),()1(2)1(1xxdxxdkk和),(

17、),()1(2)1(1xxdxxdkkkx4、分別計算兩個類的重心，則得 和 ，以其為新的凝聚點(diǎn)，對空間中的點(diǎn)進(jìn)行重新分類，得到新分類。)2(1x)2(2xc (b) 任取兩個凝聚點(diǎn) (c) 第一次分類 (d) 求各類中心 （a）空間的群點(diǎn) (e) 第二次分類動態(tài)聚類法 優(yōu)點(diǎn)：計算量小，方法簡便，可以根據(jù)經(jīng)驗(yàn)，先作主觀分類。 缺點(diǎn)：結(jié)果受選擇凝聚點(diǎn)好壞的影響，分類結(jié)果不穩(wěn)定。 選擇凝聚點(diǎn)和確定初始分類 凝聚點(diǎn)就是一批有代表性的點(diǎn)，是欲形成類的中心。凝聚點(diǎn)的 選擇直接決定初始分類，對分類結(jié)果也有很大的影響，由于凝聚點(diǎn) 的不同選擇，其最終分類結(jié)果也將出現(xiàn)不同。故選擇時要慎重通 常選擇凝聚點(diǎn)的方法有

18、： (1) 人為選擇人為選擇，當(dāng)人們對所欲分類的問題有一定了解時，根據(jù)經(jīng)驗(yàn)，預(yù)先確定分類個數(shù)和初始分類，并從每一類中選擇一個有代表性的樣品作為凝聚點(diǎn)。 (2) 重心法重心法 將數(shù)據(jù)人為地分為A類，計算每一類的重心，將重心作為凝聚點(diǎn)。第一第一、選擇凝聚點(diǎn)選擇凝聚點(diǎn)第二、初始分類第二、初始分類對于取定的凝聚點(diǎn)，視每個凝聚點(diǎn)為一類，將每個樣品根據(jù)定義的距離向最近的凝聚點(diǎn)歸類。第三、修改第三、修改分類分類得到初始分類，計算各類的重心，以這些重心作為新的凝聚點(diǎn)，重新進(jìn)行分類，重復(fù)步驟2，3，直到分類的結(jié)果與上一步的分類結(jié)果相同，表明分類已經(jīng)合理為止。動態(tài)聚類法的基本步驟：動態(tài)聚類法的基本步驟：劃分聚類方

19、法劃分聚類方法層次聚類方法層次聚類方法 密度聚類方法密度聚類方法 ：基于密度的聚類方法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類，無需預(yù)先設(shè)定簇的數(shù)量，因此特別適合對于未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類。網(wǎng)格聚類方法網(wǎng)格聚類方法 模型聚類方法模型聚類方法密度聚類方法密度聚類方法基于密度方法的聚類 密度聚類方法的指導(dǎo)思想是，只要一個區(qū)域中的點(diǎn)的密度大于某個域值，就把它加到與之相近的聚類中去。對于簇中每個對象，在給定的半徑的鄰域中至少要包含最小數(shù)數(shù)目（MINPTS）個對象。 這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點(diǎn)，可發(fā)現(xiàn)任意形狀的聚類，且對噪聲數(shù)據(jù)不敏感。 代表算法有：DBSCAN、O

20、PTICS、DENCLUE算法等?；诿芏确椒ǖ木垲? DBSCAN DBSCAN（DENSITY-BASED SPATIAL CLUSTERING OF APPLICATIONS WITH NOISE）一個比較有代表性的基于密度的聚類算法。與層次聚類方法不同，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。傳統(tǒng)基于中心的密度定義為：數(shù)據(jù)集中特定點(diǎn)的密度通過該點(diǎn)半徑之內(nèi)的點(diǎn)計數(shù)(包括本身)來估計。顯然，密度依賴于半徑。傳統(tǒng)的密度定義：基于中心的方法基于密度方法的聚類- DBSCAN 所用到的基本術(shù)語定義 對象的-鄰域：給定對象在半徑內(nèi)的區(qū)域。定義 核心對象：如果一個對象的-鄰域至少包含最小數(shù)目MinPts個 對象，則稱該對象為核心對象。 例 下圖中，=1cm，MinPts=5，q是一個核心對象。 定義 直接密度可達(dá)：給定一個對象集合D，如果p是在q的-鄰域內(nèi)，而 q是一個核心對象，我們說對象p從對象q出發(fā)是直接密度可達(dá)的。 例 在下圖中，=1cm，MinPts=5 ，q是一個核心對象，對象 p1從對象q出發(fā)是直接密度可達(dá)的?；诿芏确椒ǖ木垲? D