kmeans聚類演算法缺點

A. 八：聚類演算法K-means（20191223-29)

學習內容：無監督聚類演算法K-Means

k-means：模型原理、收斂過程、超參數的選擇

聚類分析是在數據中發現數據對象之間的關系，將數據進行分組，組內的相似性越大，組間的差別越大，則聚類效果越好。

不同的簇類型： 聚類旨在發現有用的對象簇，在現實中我們用到很多的簇的類型，使用不同的簇類型劃分數據的結果是不同的。

基於原型的： 簇是對象的集合，其中每個對象到定義該簇的 原型 的距離比其他簇的原型距離更近，如(b)所示的原型即為中心點，在一個簇中的數據到其中心點比到另一個簇的中心點更近。這是一種常見的 基於中心的簇 ，最常用的K-Means就是這樣的一種簇類型。 這樣的簇趨向於球形。

基於密度的 ：簇是對象的密度區域，(d)所示的是基於密度的簇，當簇不規則或相互盤繞，並且有早上和離群點事，常常使用基於密度的簇定義。

關於更多的簇介紹參考《數據挖掘導論》。

基本的聚類分析演算法

     1. K均值： 基於原型的、劃分的距離技術，它試圖發現用戶指定個數(K)的簇。

     2. 凝聚的層次距離： 思想是開始時，每個點都作為一個單點簇，然後，重復的合並兩個最靠近的簇，直到嘗試單個、包含所有點的簇。

     3. DBSCAN: 一種基於密度的劃分距離的演算法，簇的個數有演算法自動的確定，低密度中的點被視為雜訊而忽略，因此其不產生完全聚類。

不同的距離量度會對距離的結果產生影響，常見的距離量度如下所示：

優點：易於實現 

缺點：可能收斂於局部最小值，在大規模數據收斂慢

演算法思想：

選擇K個點作為初始質心 

repeat

    將每個點指派到最近的質心，形成K個簇 

    重新計算每個簇的質心  

until 簇不發生變化或達到最大迭代次數

這里的「重新計算每個簇的質心」，是根據目標函數來計算的，因此在開始時要考慮 距離度量和目標函數。

考慮歐幾里得距離的數據，使用 誤差平方和（Sum of the Squared Error,SSE） 作為聚類的目標函數，兩次運行K均值產生的兩個不同的簇集，使用SSE最小的那個。

k表示k個聚類中心，ci表示第幾個中心，dist表示的是歐幾里得距離。 

這里有一個問題就是為什麼，我們更新質心是讓所有的點的平均值，這里就是SSE所決定的。

k均值演算法非常簡單且使用廣泛，但是其有主要的兩個缺陷：

1. K值需要預先給定 ，屬於預先知識，很多情況下K值的估計是非常困難的，對於像計算全部微信用戶的交往圈這樣的場景就完全的沒辦法用K-Means進行。對於可以確定K值不會太大但不明確精確的K值的場景，可以進行迭代運算，然後找出Cost Function最小時所對應的K值，這個值往往能較好的描述有多少個簇類。

2. K-Means演算法對初始選取的聚類中心點是敏感的 ，不同的隨機種子點得到的聚類結果完全不同

3. K均值演算法並不是很所有的數據類型。 它不能處理非球形簇、不同尺寸和不同密度的簇，銀冠指定足夠大的簇的個數是他通常可以發現純子簇。

4. 對離群點的數據進行聚類時，K均值也有問題 ，這種情況下，離群點檢測和刪除有很大的幫助。

下面對初始質心的選擇進行討論：

當初始質心是隨機的進行初始化的時候，K均值的每次運行將會產生不同的SSE,而且隨機的選擇初始質心結果可能很糟糕，可能只能得到局部的最優解，而無法得到全局的最優解。

多次運行，每次使用一組不同的隨機初始質心，然後選擇一個具有最小的SSE的簇集。該策略非常的簡單，但是效果可能不是很好，這取決於數據集合尋找的簇的個數。

關於更多，參考《數據挖掘導論》

為了克服K-Means演算法收斂於局部最小值的問題，提出了一種 二分K-均值(bisecting K-means)

將所有的點看成是一個簇

當簇小於數目k時

    對於每一個簇

        計算總誤差

        在給定的簇上進行K-均值聚類,k值為2        計算將該簇劃分成兩個簇後總誤差

    選擇是的誤差最小的那個簇進行劃分

在原始的K-means演算法中，每一次的劃分所有的樣本都要參與運算，如果數據量非常大的話，這個時間是非常高的，因此有了一種分批處理的改進演算法。

使用Mini Batch（分批處理）的方法對數據點之間的距離進行計算。

Mini Batch的好處：不必使用所有的數據樣本，而是從不同類別的樣本中抽取一部分樣本來代表各自類型進行計算。n 由於計算樣本量少，所以會相應的減少運行時間n 但另一方面抽樣也必然會帶來准確度的下降。

聚類試圖將數據集中的樣本劃分為若干個通常是不相交的子集，每個子集成為一個「簇」。通過這樣的劃分，每個簇可能對應於一些潛在的概念（也就是類別）；需說明的是，這些概念對聚類演算法而言事先是未知的，聚類過程僅能自動形成簇結構，簇對應的概念語義由使用者來把握和命名。

聚類是無監督的學習演算法，分類是有監督的學習演算法。所謂有監督就是有已知標簽的訓練集（也就是說提前知道訓練集里的數據屬於哪個類別），機器學習演算法在訓練集上學習到相應的參數，構建模型，然後應用到測試集上。而聚類演算法是沒有標簽的，聚類的時候，需要實現的目標只是把相似的東西聚到一起。

聚類的目的是把相似的樣本聚到一起，而將不相似的樣本分開，類似於「物以類聚」，很直觀的想法是同一個簇中的相似度要盡可能高，而簇與簇之間的相似度要盡可能的低。

性能度量大概可分為兩類： 一是外部指標， 二是內部指標 。

外部指標：將聚類結果和某個「參考模型」進行比較。

內部指標：不利用任何參考模型，直接考察聚類結果。

對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大

初學者會很容易就把K-Means和KNN搞混，其實兩者的差別還是很大的。

K-Means是無監督學習的聚類演算法，沒有樣本輸出；而KNN是監督學習的分類演算法，有對應的類別輸出。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的k個點，用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到k個類別的最佳質心，從而決定樣本的簇類別。

當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。

優點：

簡單， 易於理解和實現 ；收斂快，一般僅需5-10次迭代即可，高效

缺點：

    1，對K值得選取把握不同對結果有很大的不同

    2，對於初始點的選取敏感，不同的隨機初始點得到的聚類結果可能完全不同

    3，對於不是凸的數據集比較難收斂

    4，對噪點過於敏感，因為演算法是根據基於均值的

    5，結果不一定是全局最優，只能保證局部最優

    6，對球形簇的分組效果較好，對非球型簇、不同尺寸、不同密度的簇分組效果不好。

K-means演算法簡單理解，易於實現（局部最優），卻會有對初始點、雜訊點敏感等問題；還容易和監督學習的分類演算法KNN混淆。

參考閱讀：

1.《 深入理解K-Means聚類演算法 》

2.《 K-Means 》

B. kmeans演算法原理

kmeans演算法原理如下：

K-means演算法是一種典型的基於劃分的聚類演算法該演算法具有運算速度快，執行過程簡單的優點，在很多大數據處理領域得到了廣泛的應用。

利用相似性度量方法來衡量數據集中所有數據之間的關系,將關系比較密切的數據劃分到一個集合中。K-means演算法首先需要選擇K個初始化聚類中，計算每個數據對象到K個初始化聚類中心的距離。

2、缺點：需要人工預先確定初始K值，該值與實際的類另數可能不吻合。tK均值只能收斂到局部最優。因為求解這個代價函數是個NP問題，採用的是貪心策略，所以只能通過多次迭代收斂到局部最優，而不是全局最優。

K<均值的效果受初始值和離群點的影響大。因為k均值本質上是基於距離度量來劃分的，均值和差大的維度將對數據的聚類結帆山塌果產生決定性的影響，因此需要進行歸-化處理:此外，離群點或雜訊對均值會產生影響，導致中心偏移,因此需要進行預處理。

C. 對比傳統K-Means等聚類演算法，LDA主題模型在文本聚類上有何優缺點

K-MEANS演算法:k-means演算法接受輸入量k；然後將n個數據對象劃分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。k-means演算法的工作過程說明如下：首先從n個數據對象任意選擇k個對象作為初始聚類中心；而對於所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然後再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數.k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。具體如下：輸入：k,data[n];（1）選擇k個初始中心點，例如c[0]=data[0],…c[k-1]=data[k-1];（2）對於data[0]….data[n],分別與c[0]…c[n-1]比較，假定與c[i]差值最少，就標記為i;（3）對於所有標記為i點，重新計算c[i]=/標記為i的個數；（4）重復(2)(3),直到所有c[i]值的變化小於給定閾值。演算法實現起來應該很容易，就不幫你編寫代碼了。

D. Kmeans聚類演算法簡介

由於具有出色的速度和良好的可擴展性，Kmeans聚類演算法算得上是最著名的聚類方法。Kmeans演算法是一個重復移動類中心點的過程，把類的中心點，也稱重心(centroids)，移動到其包含成員的平均位置，然後重新劃分其內部成員。k是演算法計算出的超參數，表示類的數量；Kmeans可以自動分配樣本到不同的類，但是不能決定究竟要分幾個類。k必須是一個比訓練集樣本數小的正整數。有時，類的數量是由問題內容指定的。例如，一個鞋廠有三種新款式，它想知道每種新款式都有哪些潛在客戶，於是它調研客戶，然後從數據里找出三類。也有一些問題沒有指定聚類的數量，最優的聚類數量是不確定的。後面我將會詳細介紹一些方法來估計最優聚類數量。

Kmeans的參數是類的重心位置和其內部觀測值的位置。與廣義線性模型和決策樹類似，Kmeans參數的最優解也是以成本函數最小化為目標。Kmeans成本函數公式如下：

μiμi是第kk個類的重心位置。成本函數是各個類畸變程度(distortions)之和。每個類的畸變程度等於該類重心與其內部成員位置距離的平方和。若類內部的成員彼此間越緊湊則類的畸變程度越小，反之，若類內部的成員彼此間越分散則類的畸變程度越大。求解成本函數最小化的參數就是一個重復配置每個類包含的觀測值，並不斷移動類重心的過程。首先，類的重心是隨機確定的位置。實際上，重心位置等於隨機選擇的觀測值的位置。每次迭代的時候，Kmeans會把觀測值分配到離它們最近的類，然後把重心移動到該類全部成員位置的平均值那裡。

2.1 根據問題內容確定

這種方法就不多講了，文章開篇就舉了一個例子。

2.2 肘部法則

如果問題中沒有指定kk的值，可以通過肘部法則這一技術來估計聚類數量。肘部法則會把不同kk值的成本函數值畫出來。隨著kk值的增大，平均畸變程度會減小；每個類包含的樣本數會減少，於是樣本離其重心會更近。但是，隨著kk值繼續增大，平均畸變程度的改善效果會不斷減低。kk值增大過程中，畸變程度的改善效果下降幅度最大的位置對應的kk值就是肘部。為了讓讀者看的更加明白，下面讓我們通過一張圖用肘部法則來確定最佳的kk值。下圖數據明顯可分成兩類：

從圖中可以看出，k值從1到2時，平均畸變程度變化最大。超過2以後，平均畸變程度變化顯著降低。因此最佳的k是2。

2.3 與層次聚類結合

經常會產生較好的聚類結果的一個有趣策略是，首先採用層次凝聚演算法決定結果粗的數目，並找到一個初始聚類，然後用迭代重定位來改進該聚類。

2.4 穩定性方法

穩定性方法對一個數據集進行2次重采樣產生2個數據子集，再用相同的聚類演算法對2個數據子集進行聚類，產生2個具有kk個聚類的聚類結果，計算2個聚類結果的相似度的分布情況。2個聚類結果具有高的相似度說明kk個聚類反映了穩定的聚類結構，其相似度可以用來估計聚類個數。採用次方法試探多個kk，找到合適的k值。

2.5 系統演化方法

系統演化方法將一個數據集視為偽熱力學系統，當數據集被劃分為kk個聚類時稱系統處於狀態kk。系統由初始狀態k=1k=1出發，經過分裂過程和合並過程，系統將演化到它的穩定平衡狀態 kiki ，其所對應的聚類結構決定了最優類數 kiki 。系統演化方法能提供關於所有聚類之間的相對邊界距離或可分程度，它適用於明顯分離的聚類結構和輕微重疊的聚類結構。

2.6 使用canopy演算法進行初始劃分

基於Canopy Method的聚類演算法將聚類過程分為兩個階段

(1) 聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬於任何Canopy的情況，可以把這一階段看做數據預處理；

(2) 在各個Canopy內使用傳統的聚類方法(如Kmeans)，不屬於同一Canopy的對象之間不進行相似性計算。

從這個方法起碼可以看出兩點好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會大大減少後續需要計算相似性的對象的個數；其次，類似於Kmeans這樣的聚類方法是需要人為指出K的值的，通過(1)得到的Canopy個數完全可以作為這個k值，一定程度上減少了選擇k的盲目性。

其他方法如貝葉斯信息准則方法(BIC)可參看文獻[4]。

選擇適當的初始質心是基本kmeans演算法的關鍵步驟。常見的方法是隨機的選取初始中心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然後選取具有最小SSE(誤差的平方和)的簇集。這種策略簡單，但是效果可能不好，這取決於數據集和尋找的簇的個數。

第二種有效的方法是，取一個樣本，並使用層次聚類技術對它聚類。從層次聚類中提取kk個簇，並用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效：(1)樣本相對較小，例如數百到數千(層次聚類開銷較大)；(2) kk相對於樣本大小較小。

第三種選擇初始質心的方法，隨機地選擇第一個點，或取所有點的質心作為第一個點。然後，對於每個後繼初始質心，選擇離已經選取過的初始質心最遠的點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用於點樣本。由於離群點很少(多了就不是離群點了)，它們多半不會在隨機樣本中出現。計算量也大幅減少。

第四種方法就是上面提到的canopy演算法。

常用的距離度量方法包括：歐幾里得距離和餘弦相似度。兩者都是評定個體間差異的大小的。

歐氏距離是最常見的距離度量，而餘弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基於這兩者的變形和衍生，所以下面重點比較下兩者在衡量個體差異時實現方式和應用環境上的區別。

藉助三維坐標系來看下歐氏距離和餘弦相似度的區別：

從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標(即個體特徵維度的數值)直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是體現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那麼這個時候餘弦相似cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。

根據歐氏距離和餘弦相似度各自的計算方式和衡量特徵，分別適用於不同的數據分析模型：歐氏距離能夠體現個體數值特徵的絕對差異，所以更多的用於需要從維度的數值大小中體現差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異；而餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用於使用用戶對內容評分來區分用戶興趣的相似度和差異，同時修正了用戶間可能存在的度量標准不統一的問題(因為餘弦相似度對絕對數值不敏感)。

因為歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需要先進行標准化，同時距離越大，個體間差異越大；空間向量餘弦夾角的相似度度量不會受指標刻度的影響，餘弦值落於區間[-1,1]，值越大，差異越小。但是針對具體應用，什麼情況下使用歐氏距離，什麼情況下使用餘弦相似度？

從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形，其頂角大小是不確定的。也就是說對於兩條空間向量，即使兩點距離一定，他們的夾角餘弦值也可以隨意變化。感性的認識，當兩用戶評分趨勢一致時，但是評分值差距很大，餘弦相似度傾向給出更優解。舉個極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認知其實是一樣的，但是歐式距離給出的解顯然沒有餘弦值合理。

我們把機器學習定義為對系統的設計和學習，通過對經驗數據的學習，將任務效果的不斷改善作為一個度量標准。Kmeans是一種非監督學習，沒有標簽和其他信息來比較聚類結果。但是，我們還是有一些指標可以評估演算法的性能。我們已經介紹過類的畸變程度的度量方法。本節為將介紹另一種聚類演算法效果評估方法稱為輪廓系數(Silhouette Coefficient)。輪廓系數是類的密集與分散程度的評價指標。它會隨著類的規模增大而增大。彼此相距很遠，本身很密集的類，其輪廓系數較大，彼此集中，本身很大的類，其輪廓系數較小。輪廓系數是通過所有樣本計算出來的，計算每個樣本分數的均值，計算公式如下：

aa是每一個類中樣本彼此距離的均值，bb是一個類中樣本與其最近的那個類的所有樣本的距離的均值。

輸入：聚類個數k，數據集XmxnXmxn。

輸出：滿足方差最小標準的k個聚類。

(1) 選擇k個初始中心點，例如c[0]=X[0] , … , c[k-1]=X[k-1]；

(2) 對於X[0]….X[n]，分別與c[0]…c[k-1]比較，假定與c[i]差值最少，就標記為i；

(3) 對於所有標記為i點，重新計算c[i]={ 所有標記為i的樣本的每個特徵的均值}；

(4) 重復(2)(3)，直到所有c[i]值的變化小於給定閾值或者達到最大迭代次數。

Kmeans的時間復雜度：O(tkmn)，空間復雜度：O((m+k)n)。其中，t為迭代次數，k為簇的數目，m為樣本數，n為特徵數。

7.1 優點

(1). 演算法原理簡單。需要調節的超參數就是一個k。

(2). 由具有出色的速度和良好的可擴展性。

7.2 缺點

(1). 在 Kmeans 演算法中 kk 需要事先確定，這個 kk 值的選定有時候是比較難確定。

(2). 在 Kmeans 演算法中，首先需要初始k個聚類中心，然後以此來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果。多設置一些不同的初值，對比最後的運算結果，一直到結果趨於穩定結束。

(3). 該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。

(4). 對離群點很敏感。

(5). 從數據表示角度來說，在 Kmeans 中,我們用單個點來對 cluster 進行建模，這實際上是一種最簡化的數據建模形式。這種用點來對 cluster 進行建模實際上就已經假設了各 cluster的數據是呈圓形(或者高維球形)或者方形等分布的。不能發現非凸形狀的簇。但在實際生活中，很少能有這種情況。所以在 GMM 中，使用了一種更加一般的數據表示，也就是高斯分布。

(6). 從數據先驗的角度來說，在 Kmeans 中,我們假設各個 cluster 的先驗概率是一樣的,但是各個 cluster 的數據量可能是不均勻的。舉個例子,cluster A 中包含了10000個樣本,cluster B 中只包含了100個。那麼對於一個新的樣本,在不考慮其與A cluster、 B cluster 相似度的情況,其屬於 cluster A 的概率肯定是要大於 cluster B的。

(7). 在 Kmeans 中，通常採用歐氏距離來衡量樣本與各個 cluster 的相似度。這種距離實際上假設了數據的各個維度對於相似度的衡量作用是一樣的。但在 GMM 中，相似度的衡量使用的是後驗概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通過引入協方差矩陣,我們就可以對各維度數據的不同重要性進行建模。

(8). 在 Kmeans 中，各個樣本點只屬於與其相似度最高的那個 cluster ，這實際上是一種 hard clustering 。

針對Kmeans演算法的缺點，很多前輩提出了一些改進的演算法。例如 K-modes 演算法，實現對離散數據的快速聚類，保留了Kmeans演算法的效率同時將Kmeans的應用范圍擴大到離散數據。還有K-Prototype演算法，可以對離散與數值屬性兩種混合的數據進行聚類，在K-prototype中定義了一個對數值與離散屬性都計算的相異性度量標准。當然還有其它的一些演算法，這里我 就不一一列舉了。

Kmeans 與 GMM 更像是一種 top-down 的思想，它們首先要解決的問題是，確定 cluster 數量，也就是 k 的取值。在確定了 k 後,再來進行數據的聚類。而 hierarchical clustering 則是一種 bottom-up 的形式，先有數據，然後通過不斷選取最相似的數據進行聚類。

E. 對比傳統K-Means等聚類演算法，LDA主題模型在文本聚類上有何優缺點

K-means 演算法屬於聚類分析方法中一種基本的且應用最廣泛的劃分演算法，它是一種已知聚類類別數的聚類演算法。指定類別數為K，對樣本集合進行聚類，聚類的結果由K 個聚類中心來表達，基於給定的聚類目標函數（或者說是聚類效果判別准則），演算法採用迭代更新的方法，每一次迭代過程都是向目標函數值減小的方向進行，最終的聚類結果使目標函數值取得極小值，達到較優的聚類效果。使用平均誤差准則函數E作為聚類結果好壞的衡量標准之一，保證了演算法運行結果的可靠性和有效性。
-

F. 四種聚類方法之比較

四種聚類方法之比較
介紹了較為常見的k-means、層次聚類、SOM、FCM等四種聚類演算法，闡述了各自的原理和使用步驟，利用國際通用測試數據集IRIS對這些演算法進行了驗證和比較。結果顯示對該測試類型數據，FCM和k-means都具有較高的准確度，層次聚類准確度最差，而SOM則耗時最長。
關鍵詞:聚類演算法；k-means；層次聚類；SOM；FCM
聚類分析是一種重要的人類行為，早在孩提時代，一個人就通過不斷改進下意識中的聚類模式來學會如何區分貓狗、動物植物。目前在許多領域都得到了廣泛的研究和成功的應用，如用於模式識別、數據分析、圖像處理、市場研究、客戶分割、Web文檔分類等[1]。
聚類就是按照某個特定標准(如距離准則)把一個數據集分割成不同的類或簇，使得同一個簇內的數據對象的相似性盡可能大，同時不在同一個簇中的數據對象的差異性也盡可能地大。即聚類後同一類的數據盡可能聚集到一起，不同數據盡量分離。
聚類技術[2]正在蓬勃發展，對此有貢獻的研究領域包括數據挖掘、統計學、機器學習、空間資料庫技術、生物學以及市場營銷等。各種聚類方法也被不斷提出和改進，而不同的方法適合於不同類型的數據，因此對各種聚類方法、聚類效果的比較成為值得研究的課題。
1 聚類演算法的分類
目前，有大量的聚類演算法[3]。而對於具體應用，聚類演算法的選擇取決於數據的類型、聚類的目的。如果聚類分析被用作描述或探查的工具，可以對同樣的數據嘗試多種演算法，以發現數據可能揭示的結果。
主要的聚類演算法可以劃分為如下幾類：劃分方法、層次方法、基於密度的方法、基於網格的方法以及基於模型的方法[4-6]。
每一類中都存在著得到廣泛應用的演算法，例如：劃分方法中的k-means[7]聚類演算法、層次方法中的凝聚型層次聚類演算法[8]、基於模型方法中的神經網路[9]聚類演算法等。
目前,聚類問題的研究不僅僅局限於上述的硬聚類，即每一個數據只能被歸為一類，模糊聚類[10]也是聚類分析中研究較為廣泛的一個分支。模糊聚類通過隸屬函數來確定每個數據隸屬於各個簇的程度，而不是將一個數據對象硬性地歸類到某一簇中。目前已有很多關於模糊聚類的演算法被提出，如著名的FCM演算法等。
本文主要對k-means聚類演算法、凝聚型層次聚類演算法、神經網路聚類演算法之SOM,以及模糊聚類的FCM演算法通過通用測試數據集進行聚類效果的比較和分析。
2 四種常用聚類演算法研究
2.1 k-means聚類演算法
k-means是劃分方法中較經典的聚類演算法之一。由於該演算法的效率高，所以在對大規模數據進行聚類時被廣泛應用。目前，許多演算法均圍繞著該演算法進行擴展和改進。
k-means演算法以k為參數，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相似度較低。k-means演算法的處理過程如下：首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心;對剩餘的每個對象，根據其與各簇中心的距離，將它賦給最近的簇;然後重新計算每個簇的平均值。這個過程不斷重復，直到准則函數收斂。通常，採用平方誤差准則，其定義如下：

這里E是資料庫中所有對象的平方誤差的總和，p是空間中的點，mi是簇Ci的平均值[9]。該目標函數使生成的簇盡可能緊湊獨立，使用的距離度量是歐幾里得距離,當然也可以用其他距離度量。k-means聚類演算法的演算法流程如下：
輸入：包含n個對象的資料庫和簇的數目k；
輸出：k個簇，使平方誤差准則最小。
步驟：
(1) 任意選擇k個對象作為初始的簇中心；
(2) repeat；
(3) 根據簇中對象的平均值，將每個對象(重新)賦予最類似的簇；
(4) 更新簇的平均值，即計算每個簇中對象的平均值；
(5) until不再發生變化。
2.2 層次聚類演算法
根據層次分解的順序是自底向上的還是自上向下的，層次聚類演算法分為凝聚的層次聚類演算法和分裂的層次聚類演算法。
凝聚型層次聚類的策略是先將每個對象作為一個簇，然後合並這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。絕大多數層次聚類屬於凝聚型層次聚類，它們只是在簇間相似度的定義上有所不同。四種廣泛採用的簇間距離度量方法如下：

這里給出採用最小距離的凝聚層次聚類演算法流程：
(1) 將每個對象看作一類，計算兩兩之間的最小距離；
(2) 將距離最小的兩個類合並成一個新類；
(3) 重新計算新類與所有類之間的距離；
(4) 重復(2)、(3)，直到所有類最後合並成一類。
2.3 SOM聚類演算法
SOM神經網路[11]是由芬蘭神經網路專家Kohonen教授提出的，該演算法假設在輸入對象中存在一些拓撲結構或順序，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓撲特徵保持性質,與實際的大腦處理有很強的理論聯系。
SOM網路包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特徵。
演算法流程：
(1) 網路初始化，對輸出層每個節點權重賦初值；
(2) 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；
(3) 定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；
(4) 提供新樣本、進行訓練；
(5) 收縮鄰域半徑、減小學習率、重復，直到小於允許值，輸出聚類結果。
2.4 FCM聚類演算法
1965年美國加州大學柏克萊分校的扎德教授第一次提出了『集合』的概念。經過十多年的發展，模糊集合理論漸漸被應用到各個實際應用方面。為克服非此即彼的分類缺點，出現了以模糊集合論為數學基礎的聚類分析。用模糊數學的方法進行聚類分析，就是模糊聚類分析[12]。
FCM演算法是一種以隸屬度來確定每個數據點屬於某個聚類程度的演算法。該聚類演算法是傳統硬聚類演算法的一種改進。

演算法流程：
(1) 標准化數據矩陣；
(2) 建立模糊相似矩陣，初始化隸屬矩陣；
(3) 演算法開始迭代，直到目標函數收斂到極小值；
(4) 根據迭代結果，由最後的隸屬矩陣確定數據所屬的類，顯示最後的聚類結果。
3 四種聚類演算法試驗
3.1 試驗數據
實驗中，選取專門用於測試分類、聚類演算法的國際通用的UCI資料庫中的IRIS[13]數據集，IRIS數據集包含150個樣本數據，分別取自三種不同的鶯尾屬植物setosa、versicolor和virginica的花朵樣本,每個數據含有4個屬性，即萼片長度、萼片寬度、花瓣長度，單位為cm。在數據集上執行不同的聚類演算法，可以得到不同精度的聚類結果。
3.2 試驗結果說明
文中基於前面所述各演算法原理及演算法流程，用matlab進行編程運算，得到表1所示聚類結果。

如表1所示，對於四種聚類演算法，按三方面進行比較：(1)聚錯樣本數：總的聚錯的樣本數，即各類中聚錯的樣本數的和；(2)運行時間：即聚類整個過程所耗費的時間，單位為s；(3)平均准確度：設原數據集有k個類,用ci表示第i類，ni為ci中樣本的個數，mi為聚類正確的個數,則mi/ni為第i類中的精度，則平均精度為：

3.3 試驗結果分析
四種聚類演算法中，在運行時間及准確度方面綜合考慮，k-means和FCM相對優於其他。但是，各個演算法還是存在固定缺點：k-means聚類演算法的初始點選擇不穩定，是隨機選取的，這就引起聚類結果的不穩定，本實驗中雖是經過多次實驗取的平均值，但是具體初始點的選擇方法還需進一步研究；層次聚類雖然不需要確定分類數，但是一旦一個分裂或者合並被執行，就不能修正，聚類質量受限制；FCM對初始聚類中心敏感，需要人為確定聚類數，容易陷入局部最優解；SOM與實際大腦處理有很強的理論聯系。但是處理時間較長，需要進一步研究使其適應大型資料庫。
聚類分析因其在許多領域的成功應用而展現出誘人的應用前景，除經典聚類演算法外，各種新的聚類方法正被不斷被提出。

G. K-means的演算法缺點

① 在 K-means 演算法中 K 是事先給定的，這個 K 值的選定是非常難以估計的。很多時候，事先並不知道給定的數據集應該分成多少個類別才最合適。這也是 K-means 演算法的一個不足。有的演算法是通過類的自動合並和分裂，得到較為合理的類型數目 K，例如 ISODATA 演算法。關於 K-means 演算法中聚類數目K 值的確定在文獻中，是根據方差分析理論，應用混合 F統計量來確定最佳分類數，並應用了模糊劃分熵來驗證最佳分類數的正確性。在文獻中，使用了一種結合全協方差矩陣的 RPCL 演算法，並逐步刪除那些只包含少量訓練數據的類。而文獻中使用的是一種稱為次勝者受罰的競爭學習規則，來自動決定類的適當數目。它的思想是：對每個輸入而言，不僅競爭獲勝單元的權值被修正以適應輸入值，而且對次勝單元採用懲罰的方法使之遠離輸入值。
② 在 K-means 演算法中，首先需要根據初始聚類中心來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果，這也成為 K-means演算法的一個主要問題。對於該問題的解決，許多演算法採用遺傳演算法（GA），例如文獻 中採用遺傳演算法（GA）進行初始化，以內部聚類准則作為評價指標。
③ 從 K-means 演算法框架可以看出，該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。所以需要對演算法的時間復雜度進行分析、改進，提高演算法應用范圍。在文獻中從該演算法的時間復雜度進行分析考慮，通過一定的相似性准則來去掉聚類中心的侯選集。而在文獻中，使用的 K-means 演算法是對樣本數據進行聚類，無論是初始點的選擇還是一次迭代完成時對數據的調整，都是建立在隨機選取的樣本數據的基礎之上，這樣可以提高演算法的收斂速度。

H. K-Means 聚類演算法

問題導入

    假如有這樣一種情況，在一天你想去某個城市旅遊，這個城市裡你想去的有70個地方，現在你只有每一個地方的地址，這個地址列表很長，有70個位置。事先肯定要做好攻略，你要把一些比較接近的地方放在一起組成一組，這樣就可以安排交通工具抵達這些組的「某個地址」，然後步行到每個組內的地址。那麼，如何確定這些組，如何確定這些組的「某個地址」？答案就是聚類。而本文所提供的k-means聚類分析方法就可以用於解決這類問題。

一，聚類思想

        所謂聚類演算法是指將一堆沒有標簽的數據自動劃分成幾類的方法，屬於無監督學習方法，這個方法要保證同一類的數據有相似的特徵，如下圖：

        根據樣本之間的距離或者說相似性，把越相似，差異越小的樣本聚成一類（簇），最後形成多個簇，使同一個簇內部的樣本相似度高，不同簇之間差異性高。

二，K-Means聚類分析演算法

        K-Means是一種基於自下而上的聚類分析方法，基本概念就是空間中有N個點，初始選擇K個點作為中心聚類點，將N個點分別與K個點計算距離，選擇自己最近的點作為自己的中心點，不斷地更新中心聚集點。

相關概念：

        K值：要得到的簇的個數

        質心：每個簇的均值向量，即向量各維取品軍即可

        距離度量：常用歐幾里得距離和餘弦相似度(先標准化)

        兩點之間的距離：

演算法流程：

        1    首先確定一個K值，即我們希望將數據集經過聚類得到 K個集合；

        2    從數據集中隨機選擇K個數據點作為質心；

        3    對數據集中每一個點，計算其與每個質心的距離(如歐式距離)，離哪個質心近，就劃分到哪個質心所屬的集合

        4    把所有數據歸好集合，一共有K個集合，然後重新計算每個集合的質心；

        5    如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂)，我們可以認為聚類已經達到期望的結果，演算法終止。

        6    如果新質心和原質心距離變化大，需要迭代3-5步驟

K-means實現過程

K-means 聚類演算法是一種非監督學習演算法，被用於非標簽數據（data without defined categories or groups）。該演算法使用迭代細化來產生最終結果。演算法輸入的是集群的數量 K 和數據集。數據集是每個數據點的一組功能。

演算法從 Κ 質心的初始估計開始，其可以隨機生成或從數據集中隨機選擇 。然後演算法在下面兩個步驟之間迭代：

1.數據分配：

每個質心定義一個集群。在此步驟中，基於平方歐氏距離將每個數據點分配到其最近的質心。更正式一點， ci 屬於質心集合 C ，然後每個數據點 x 基於下面的公式被分配到一個集群中。

其中 dist（·）是標准（L2）歐氏距離。讓指向第 i 個集群質心的數據點集合定為 Si 。

2. 質心更新：

在此步驟中，重新計算質心。這是通過獲取分配給該質心集群的所有數據點的平均值來完成的。公式如下：

K-means 演算法在步驟 1 和步驟 2 之間迭代，直到滿足停止條件（即，沒有數據點改變集群，距離的總和最小化，或者達到一些最大迭代次數）。

K 值的選擇

上述演算法找到特定預選 K 值和數據集標簽。為了找到數據中的集群數，用戶需要針對一系列 K 值運行 K-means 聚類演算法並比較結果。通常，沒有用於確定 K 的精確值的方法，但是可以使用以下技術獲得准確的估計。

Elbow point 拐點方法

通常用於比較不同 K 值的結果的度量之一是數據點與其聚類質心之間的平均距離。由於增加集群的數量將總是減少到數據點的距離，因此當 K 與數據點的數量相同時，增加 K 將總是減小該度量，達到零的極值。因此，該指標不能用作唯一目標。相反，繪制了作為 K 到質心的平均距離的函數，並且可以使用減小率急劇變化的「拐點」來粗略地確定 K 。

DBI（Davies-Bouldin Index）

DBI 是一種評估度量的聚類演算法的指標，通常用於評估 K-means 演算法中 k 的取值。簡單的理解就是：DBI 是聚類內的距離與聚類外的距離的比值。所以，DBI 的數值越小，表示分散程度越低，聚類效果越好。

還存在許多用於驗證 K 的其他技術，包括交叉驗證，信息標准，信息理論跳躍方法，輪廓方法和 G 均值演算法等等。

三，數學原理

K-Means採用的啟發式很簡單，可以用下面一組圖來形象的描述：

上述a表達了初始的數據集，假設 k=2 。在圖b中，我們隨機選擇了兩個 k 類所對應的類別質點，即圖中的紅色質點和藍色質點，然後分別求樣本中所有點到這兩個質心的距離，並標記每個樣本類別為和該樣本距離最小的質心的類別，如圖c所示，經過計算樣本和紅色質心和藍色質心的距離，我們得到了所有樣本點的第一輪迭代後的類別。此時我們對我們當前標記為紅色和藍色的點分別求其新的質心，如圖d所示，新的紅色質心和藍色質心大熱位置已經發生了變化。圖e和圖f重復了我們在圖c和圖d的過程，即將所有點的類別標記為距離最近的質心的類別並求出新的質心。最終我們得到的兩個類別如圖f.

四，實例

坐標系中有六個點：

1、我們分兩組，令K等於2，我們隨機選擇兩個點：P1和P2

2、通過勾股定理計算剩餘點分別到這兩個點的距離：

3、第一次分組後結果：

        組A：P1

        組B：P2、P3、P4、P5、P6

4、分別計算A組和B組的質心：

        A組質心還是P1=（0，0）

        B組新的質心坐標為：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）

5、再次計算每個點到質心的距離：

6、第二次分組結果：

        組A：P1、P2、P3

        組B：P4、P5、P6

7、再次計算質心：

        P哥1=（1.33，1） 

        P哥2=（9，8.33）

8、再次計算每個點到質心的距離：

9、第三次分組結果：

        組A：P1、P2、P3

        組B：P4、P5、P6

可以發現，第三次分組結果和第二次分組結果一致，說明已經收斂，聚類結束。

五、K-Means的優缺點

優點：

1、原理比較簡單，實現也是很容易，收斂速度快。

2、當結果簇是密集的，而簇與簇之間區別明顯時, 它的效果較好。

3、主要需要調參的參數僅僅是簇數k。

缺點：

1、K值需要預先給定，很多情況下K值的估計是非常困難的。

2、K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同 ，對結果影響很大。

3、對噪音和異常點比較的敏感。用來檢測異常值。

4、採用迭代方法， 可能只能得到局部的最優解，而無法得到全局的最優解 。

六、細節問題

1、K值怎麼定？

答：分幾類主要取決於個人的經驗與感覺，通常的做法是多嘗試幾個K值，看分成幾類的結果更好解釋，更符合分析目的等。或者可以把各種K值算出的 E 做比較，取最小的 E 的K值。

2、初始的K個質心怎麼選？

        答：最常用的方法是隨機選，初始質心的選取對最終聚類結果有影響，因此演算法一定要多執行幾次，哪個結果更reasonable，就用哪個結果。      當然也有一些優化的方法，第一種是選擇彼此距離最遠的點，具體來說就是先選第一個點，然後選離第一個點最遠的當第二個點，然後選第三個點，第三個點到第一、第二兩點的距離之和最小，以此類推。第二種是先根據其他聚類演算法（如層次聚類）得到聚類結果，從結果中每個分類選一個點。

3、關於離群值？

        答：離群值就是遠離整體的，非常異常、非常特殊的數據點，在聚類之前應該將這些「極大」「極小」之類的離群數據都去掉，否則會對於聚類的結果有影響。但是，離群值往往自身就很有分析的價值，可以把離群值單獨作為一類來分析。

4、單位要一致！

        答：比如X的單位是米，Y也是米，那麼距離算出來的單位還是米，是有意義的。但是如果X是米，Y是噸，用距離公式計算就會出現「米的平方」加上「噸的平方」再開平方，最後算出的東西沒有數學意義，這就有問題了。

5、標准化

        答：如果數據中X整體都比較小，比如都是1到10之間的數，Y很大，比如都是1000以上的數，那麼，在計算距離的時候Y起到的作用就比X大很多，X對於距離的影響幾乎可以忽略，這也有問題。因此，如果K-Means聚類中選擇歐幾里德距離計算距離，數據集又出現了上面所述的情況，就一定要進行數據的標准化（normalization），即將數據按比例縮放，使之落入一個小的特定區間。