各種聚類算法介紹及對比9頁

1、一、層次聚類1、層次聚類的原理及分類1）層次法（Hierarchical methods）先計算樣本之間的距離。每次將距離最近的點合并到同一個類。然后，再計算類與類之間的距離，將距離最近的類合并為一個大類。不停的合并，直到合成了一個類。其中類與類的距離的計算方法有：最短距離法，最長距離法，中間距離法，類平均法等。比如最短距離法，將類與類的距離定義為類與類之間樣本的最短距離。層次聚類算法根據(jù)層次分解的順序分為：自下底向上和自上向下，即凝聚的層次聚類算法和分裂的層次聚類算法（agglomerative和divisive），也可以理解為自下而上法（bottom-up）和自上而下法（top-down）

2、。自下而上法就是一開始每個個體（object）都是一個類，然后根據(jù)linkage尋找同類，最后形成一個“類”。自上而下法就是反過來，一開始所有個體都屬于一個“類”，然后根據(jù)linkage排除異己，最后每個個體都成為一個“類”。這兩種路方法沒有孰優(yōu)孰劣之分，只是在實際應用的時候要根據(jù)數(shù)據(jù)特點以及你想要的“類”的個數(shù)，來考慮是自上而下更快還是自下而上更快。至于根據(jù)Linkage判斷“類”的方法就是最短距離法、最長距離法、中間距離法、類平均法等等（其中類平均法往往被認為是最常用也最好用的方法，一方面因為其良好的單調性，另一方面因為其空間擴張/濃縮的程度適中）。為彌補分解與合并的不足，層次合并經(jīng)常要與

3、其它聚類方法相結合，如循環(huán)定位。 2）Hierarchical methods中比較新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用層次方法的平衡迭代規(guī)約和聚類）主要是在數(shù)據(jù)量很大的時候使用，而且數(shù)據(jù)類型是numerical。首先利用樹的結構對對象集進行劃分，然后再利用其它聚類方法對這些聚類進行優(yōu)化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的數(shù)據(jù)類型上；Chame

4、leon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此構建一個graph，Chameleon的聚類效果被認為非常強大，比BIRCH好用，但運算復雜度很高，O(n2)。2、層次聚類的流程凝聚型層次聚類的策略是先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。絕大多數(shù)層次聚類屬于凝聚型層次聚類，它們只是在簇間相似度的定義上有所不同。 這里給出采用最小距離的凝聚層次聚類算法流程：(1) 將

5、每個對象看作一類，計算兩兩之間的最小距離；(2) 將距離最小的兩個類合并成一個新類；(3) 重新計算新類與所有類之間的距離；(4) 重復(2)、(3)，直到所有類最后合并成一類。 聚類的效果如下圖，黑色是噪音點： 另外我們可以看出凝聚的層次聚類并沒有類似基本K均值的全局目標函數(shù)，沒有局部極小問題或是很難選擇初始點的問題。合并的操作往往是最終的，一旦合并兩個簇之后就不會撤銷。當然其計算存儲的代價是昂貴的。3、層次聚類的優(yōu)缺點優(yōu)點：1，距離和規(guī)則的相似度容易定義，限制少；2，不需要預先制定聚類數(shù)；3，可以發(fā)現(xiàn)類的層次關系；4，可以聚類成其它形狀缺點：1，計算復雜度太高；2，奇異值也能產生

6、很大影響；3，算法很可能聚類成鏈狀 r語言中使用hclust(d, method = "complete", members=NULL) ：進行層次聚類。d為距離矩陣；method表示類的合并方法，single最短距離法，complete最長距離法，median中間距離法，mcquitty 相似法，average 類平均法，centroid重心法，ward離差平方和法；members為NULL或d長度的矢量。二、劃分聚類法k-means基于劃分的方法（Partition-based methods）：其原理簡單來說就是，想象你有一堆散點需要聚類

7、，想要的聚類效果就是“類內的點都足夠近，類間的點都足夠遠”。首先你要確定這堆散點最后聚成幾類，然后挑選幾個點作為初始中心點，再然后依據(jù)預先定好的啟發(fā)式算法（heuristic algorithms）給數(shù)據(jù)點做迭代重置（iterative relocation），直到最后到達“類內的點都足夠近，類間的點都足夠遠”的目標效果。Partition-based methods聚類多適用于中等體量的數(shù)據(jù)集，但我們也不知道“中等”到底有多“中”，所以不妨理解成，數(shù)據(jù)集越大，越有可能陷入局部最小。1、Kmeans算法的原理k-means算法以k為參數(shù)，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相

8、似度較低。k-means算法的處理過程如下：首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心，即選擇K個初始質心;對剩余的每個對象，根據(jù)其與各簇中心的距離，將它賦給最近的簇;然后重新計算每個簇的平均值。 這個過程不斷重復，直到準則函數(shù)收斂，直到質心不發(fā)生明顯的變化。通常，采用平方誤差準則，誤差的平方和SSE作為全局的目標函數(shù)，即最小化每個點到最近質心的歐幾里得距離的平方和。此時，簇的質心就是該簇內所有數(shù)據(jù)點的平均值。選擇K個點作為初始質心  repeat      將每個點指派到最近的質心，形成K

9、個簇      重新計算每個簇的質心  until 簇不發(fā)生變化或達到最大迭代次數(shù)  時間復雜度：O(tKmn)，其中，t為迭代次數(shù)，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)空間復雜度：O(m+K)n)，其中，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)K-Means 算法的詳細過程從上圖中，我們可以看到，A, B, C, D, E 是五個在圖中點。而灰色的點是我們的種子點，也就是我們用來找點群的點。有兩個種子點，所以K=2。然后，K-Means的算法如下：隨機在圖中取K（這里K=2）個種子點。然后對

10、圖中的所有點求到這K個種子點的距離，假如點Pi離種子點Si最近，那么Pi屬于Si點群。（我們可以看到A,B屬于上面的種子點，C,D,E屬于下面中部的種子點）接下來，我們要移動種子點到屬于他的“點群”的中心。（見圖上的第三步）然后重復第2）和第3）步，直到，種子點沒有移動（我們可以看到圖中的第四步上面的種子點聚合了A,B,C，下面的種子點聚合了D，E）。 聚類的效果如下圖，折線是歷次循環(huán)時3個簇的質心的更新軌跡，黑點是初始質心： 我們查看基本K均值算法實現(xiàn)步驟及上面的聚類效果可以發(fā)現(xiàn)，該聚類算法將所有數(shù)據(jù)點都進行了指派，不識別噪音點。另外選擇適當?shù)某踉囐|心是基本K均值過程的關鍵。2、k

11、均值的優(yōu)缺點及分類優(yōu)點：1，簡單，易于理解和實現(xiàn)；2，時間復雜度低缺點：1）kmeans要手工輸入類數(shù)目，對初始值的設置很敏感；所以有了k-means+、intelligent k-means、genetic k-means；2）k-means對噪聲和離群值非常敏感，所以有了k-medoids和k-medians；3）k-means只用于numerical類型數(shù)據(jù)，不適用于categorical類型數(shù)據(jù)，所以k-modes；4）k-means不能解決非凸（non-convex）數(shù)據(jù)，所以有了kernel k-means。5）k-means主要發(fā)現(xiàn)圓形或者球形簇，不能識別非球形的簇。3、k-me

12、ans與DBSCAN的區(qū)別k-means聚類算法的初始點選擇不穩(wěn)定，是隨機選取的，這就引起聚類結果的不穩(wěn)定。k-means屬于動態(tài)聚類，往往聚出來的類有點圓形或者橢圓形。kmeans對于圓形區(qū)域聚類效果較好，dbscan基于密度，對于集中區(qū)域效果較好。對于不規(guī)則形狀，kmeans完全無法用，dbscan可以起到很好的效果。4、k-means注意問題1）K如何確定        kmenas算法首先選擇K個初始質心，其中K是用戶指定的參數(shù)，即所期望的簇的個數(shù)。這樣做的前提是我們已經(jīng)知道數(shù)據(jù)集中包含多少個簇，但很多情況下，我們并不知道數(shù)據(jù)的分布情況，實際上聚

13、類就是我們發(fā)現(xiàn)數(shù)據(jù)分布的一種手段。如何有效的確定K值，這里大致提供幾種方法：與層次聚類結合2         經(jīng)常會產生較好的聚類結果的一個有趣策略是，首先采用層次凝聚算法決定結果粗的數(shù)目，并找到一個初始聚類，然后用迭代重定位來改進該聚類。穩(wěn)定性方法3        穩(wěn)定性方法對一個數(shù)據(jù)集進行2次重采樣產生2個數(shù)據(jù)子集，再用相同的聚類算法對2個數(shù)據(jù)子集進行聚類，產生2個具有k個聚類的聚類結果，計算2個聚類結果的相似度的分布情況。2個聚類結果具有高的相似度說明k個聚類反映了穩(wěn)定的聚類結構，其相似度可以用來估

14、計聚類個數(shù)。采用次方法試探多個k，找到合適的k值。系統(tǒng)演化方法3         系統(tǒng)演化方法將一個數(shù)據(jù)集視為偽熱力學系統(tǒng)，當數(shù)據(jù)集被劃分為K個聚類時稱系統(tǒng)處于狀態(tài)K。系統(tǒng)由初始狀態(tài)K=1出發(fā)，經(jīng)過分裂過程和合并過程，系統(tǒng)將演化到它的穩(wěn)定平衡狀態(tài)Ki，所對應的聚類結構決定了最優(yōu)類數(shù)Ki。系統(tǒng)演化方法能提供關于所有聚類之間的相對邊界距離或可分程度，適用于明顯分離的聚類結構和輕微重疊的聚類結構。使用canopy算法進行初始劃分4          基于Canopy Method的聚類算法將聚類過程分

15、為兩個階段         Stage1、聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy ，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬于任何Canopy的情況，可以把這一階段看做數(shù)據(jù)預處理；          Stage2、在各個Canopy 內使用傳統(tǒng)的聚類方法(如K-means)，不屬于同一Canopy 的對象之間不

16、進行相似性計算。從這個方法起碼可以看出兩點好處：首先，Canopy 不要太大且Canopy 之間重疊的不要太多的話會大大減少后續(xù)需要計算相似性的對象的個數(shù)；其次，類似于K-means這樣的聚類方法是需要人為指出K的值的，通過Stage1得到的Canopy 個數(shù)完全可以作為這個K值，一定程度上減少了選擇K的盲目性。         其他方法如貝葉斯信息準則方法（BIC）可參看文獻5。2）初始質心的選取          選擇適當?shù)某跏假|心是基本kmeans算法的關鍵步驟。常見的方法是隨機的選取初始

17、質心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然后選取具有最小SSE（誤差的平方和）的簇集。這種策略簡單，但是效果可能不好，這取決于數(shù)據(jù)集和尋找的簇的個數(shù)。          第二種有效的方法是，取一個樣本，并使用層次聚類技術對它聚類。從層次聚類中提取K個簇，并用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效：（1）樣本相對較小，例如數(shù)百到數(shù)千（層次聚類開銷較大）；（2）K相對于樣本大小較小          &#

18、160;第三種選擇初始質心的方法，隨機地選擇第一個點，或取所有點的質心作為第一個點。然后，對于每個后繼初始質心，選擇離已經(jīng)選取過的初始質心最遠的點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用于點樣本。由于離群點很少（多了就不是離群點了），它們多半不會在隨機樣本中出現(xiàn)。計算量也大幅減少。          第四種方法就是上面提到的canopy算法。3）距離的度量       

19、60; 常用的距離度量方法包括：歐幾里得距離和余弦相似度。兩者都是評定個體間差異的大小的。歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需要先進行標準化，同時距離越大，個體間差異越大；空間向量余弦夾角的相似度度量不會受指標刻度的影響，余弦值落于區(qū)間-1,1，值越大，差異越小。但是針對具體應用，什么情況下使用歐氏距離，什么情況下使用余弦相似度？          從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形，其頂角大小是不確定的。也就是說對于兩條空間向量，即使兩點距離一定，他們的夾角余弦值也可以隨意變化。感性的認識，當

20、兩用戶評分趨勢一致時，但是評分值差距很大，余弦相似度傾向給出更優(yōu)解。舉個極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認知其實是一樣的，但是歐式距離給出的解顯然沒有余弦值合理。4）質心的計算         對于距離度量不管是采用歐式距離還是采用余弦相似度，簇的質心都是其均值，即向量各維取平均即可。5）算法停止條件         一般是目標函數(shù)達到最優(yōu)或者達到最大的迭代次數(shù)即可終止。對于不同的距離度量，目標函數(shù)往往不同。當采用歐式距離時，目標函數(shù)一般為最小化

21、對象到其簇質心的距離的平方和。         當采用余弦相似度時，目標函數(shù)一般為最大化對象到其簇質心的余弦相似度和。6）空聚類的處理           如果所有的點在指派步驟都未分配到某個簇，就會得到空簇。如果這種情況發(fā)生，則需要某種策略來選擇一個替補質心，否則的話，平方誤差將會偏大。一種方法是選擇一個距離當前任何質心最遠的點。這將消除當前對總平方誤差影響最大的點。另一種方法是從具有最大SSE的簇中選擇一個替補的質心。這將分裂簇并降低聚類的總SSE。如果有多個空簇，則該過程重復多次

22、。另外，編程實現(xiàn)時，要注意空簇可能導致的程序bug。三、基于密度的聚類基于密度的方法（Density-based methods）：k-means解決不了不規(guī)則形狀的聚類。于是就有了Density-based methods來系統(tǒng)解決這個問題。該方法同時也對噪聲數(shù)據(jù)的處理比較好?；诿芏染垲惖乃枷耄核悸肪褪嵌ㄒ粋€距離半徑，最少有多少個點，然后把可以到達的點都連起來，判定為同類。其原理簡單說畫圈兒，其中要定義兩個參數(shù)，一個是圈兒的最大半徑，一個是一個圈兒里最少應容納幾個點。最后在一個圈里的，就是一個類。DBSCAN（Density-Based Spatial Clustering of Appl

23、ications with Noise）就是其中的典型，可惜參數(shù)設置也是個問題，對這兩個參數(shù)的設置非常敏感。DBSCAN的擴展叫OPTICS（Ordering Points To Identify Clustering Structure）通過優(yōu)先對高密度（high density）進行搜索，然后根據(jù)高密度的特點設置參數(shù)，改善了DBSCAN的不足。1、DBSCAN的概念dbscan基于密度，對于集中區(qū)域效果較好，為了發(fā)現(xiàn)任意形狀的簇，這類方法將簇看做是數(shù)據(jù)空間中被低密度區(qū)域分割開的稠密對象區(qū)域；一種基于高密度連通區(qū)域的基于密度的聚類方法，該算法將具有足夠高密度的區(qū)域劃分為簇，并在具有噪聲的空間

24、數(shù)據(jù)中發(fā)現(xiàn)任意形狀的簇。DBSCAN中的幾個定義：鄰域：給定對象半徑為內的區(qū)域稱為該對象的鄰域；核心對象：如果給定對象領域內的樣本點數(shù)大于等于MinPts，則稱該對象為核心對象；直接密度可達：對于樣本集合D，如果樣本點q在p的領域內，并且p為核心對象，那么對象q從對象p直接密度可達。密度可達：對于樣本集合D，給定一串樣本點p1,p2.pn，p= p1,q= pn,假如對象pi從pi-1直接密度可達，那么對象q從對象p密度可達。注意：密度可達是單向的，密度可達即可容納同一類。密度相連：存在樣本集合D中的一點o，如果對象o到對象p和對象q都是密度可達的，那么p和q密度相聯(lián)。密度可達是直接密度可達的

25、傳遞閉包，并且這種關系是非對稱的。密度相連是對稱關系。DBSCAN目的是找到密度相連對象的最大集合。有了以上的概念接下來就是算法描述了：DBSCAN通過檢查數(shù)據(jù)庫中每點的r鄰域來搜索簇。如果點p的r鄰域包含的點多于MinPts個，則創(chuàng)建一個以p為核心對象的新簇。然后，DBSCAN迭代的聚集從這些核心對象直接密度可達的對象，這個過程可能涉及一些密度可達簇的合并。當沒有新的點可以添加到任何簇時，該過程結束。 例如：Eg: 假設半徑=3，MinPts=3，點p的E領域中有點m,p,p1,p2,o, 點m的E領域中有點m,q,p,m1,m2,點q的E領域中有點q,m,點o的E領域中有點o,p

26、,s,點s的E領域中有點o,s,s1.那么核心對象有p,m,o,s(q不是核心對象，因為它對應的E領域中點數(shù)量等于2，小于MinPts=3)；點m從點p直接密度可達，因為m在p的E領域內，并且p為核心對象；點q從點p密度可達，因為點q從點m直接密度可達，并且點m從點p直接密度可達；點q到點s密度相連，因為點q從點p密度可達，并且s從點p密度可達。2、簇的生成原理及過程1）DBSCAN聚類算法原理的基本要點：確定半徑eps的值DBSCAN算法需要選擇一種距離度量，對于待聚類的數(shù)據(jù)集中，任意兩個點之間的距離，反映了點之間的密度，說明了點與點是否能夠聚到同一類中。由于DBSCAN算法對高維數(shù)據(jù)定義密

27、度很困難，所以對于二維空間中的點，可以使用歐幾里德距離來進行度量。DBSCAN算法需要用戶輸入2個參數(shù)：一個參數(shù)是半徑（Eps），表示以給定點P為中心的圓形鄰域的范圍；另一個參數(shù)是以點P為中心的鄰域內最少點的數(shù)量（MinPts）。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數(shù)不少于MinPts，則稱點P為核心點。DBSCAN聚類使用到一個k-距離的概念，k-距離是指：給定數(shù)據(jù)集P=p(i); i=0,1,n，對于任意點P(i)，計算點P(i)到集合D的子集S=p(1), p(2), , p(i-1), p(i+1), , p(n)中所有點之間的距離，距離按照從小到大的順序排序，假設排序

28、后的距離集合為D=d(1), d(2), , d(k-1), d(k), d(k+1), ,d(n)，則d(k)就被稱為k-距離。也就是說，k-距離是點p(i)到所有點（除了p(i)點）之間距離第k近的距離。對待聚類集合中每個點p(i)都計算k-距離，最后得到所有點的k-距離集合E=e(1), e(2), , e(n)。根據(jù)經(jīng)驗計算半徑Eps：根據(jù)得到的所有點的k-距離集合E，對集合E進行升序排序后得到k-距離集合E，需要擬合一條排序后的E集合中k-距離的變化曲線圖，然后繪出曲線，通過觀察，將急劇發(fā)生變化的位置所對應的k-距離的值，確定為半徑Eps的值。根據(jù)經(jīng)驗計算最少點的數(shù)量MinPts：確

29、定MinPts的大小，實際上也是確定k-距離中k的值，DBSCAN算法取k=4，則MinPts=4。另外，如果覺得經(jīng)驗值聚類的結果不滿意，可以適當調整Eps和MinPts的值，經(jīng)過多次迭代計算對比，選擇最合適的參數(shù)值?？梢钥闯觯绻鸐inPts不變，Eps取得值過大，會導致大多數(shù)點都聚到同一個簇中，Eps過小，會導致一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導致同一個簇中點被標記為噪聲點，MinPts過小，會導致發(fā)現(xiàn)大量的核心點。我們需要知道的是，DBSCAN算法，需要輸入2個參數(shù)，這兩個參數(shù)的計算都來自經(jīng)驗知識。半徑Eps的計算依賴于計算k-距離，DBSCAN取k=4，也就是設置MinPts=4，然后需要根據(jù)k-距離曲線，根據(jù)經(jīng)驗觀察找到合適的半徑Eps的值。 2）連通核心點生成簇核心點能夠連通（有些書籍中稱為：“密度可達”），它們構成的以Eps長度為半徑的圓形鄰域相互連接或重疊，這些連通的核心點及其所處的鄰域內的全部點構成一個簇。假設MinPts=4，則連通的核心點示例，如下圖所示：計算連通的核心點的思路是，基于廣度遍歷與深度遍歷集合