數據挖掘中三種典型聚類算法的分析比較

李煜堃

摘要：大數據時代從大量無序的數據中發現隱含的、有效的、有價值的、可理解的模式變得越發重要。在此背景下，以數據挖掘眾多算法中的聚類算法為切人點，選取三種典型的聚類算法——K-means算法、AGNES算法、DBSCAN算法，進行可視化聚類結果和FMI值比較分析，歸納出DBSCAN算法可以發現任意形狀的簇類，AGNES算法和K-Means算法在中小型數據集中挖掘得到球形簇的效果較好。

關鍵詞：聚類;K-means算法;AGNES算法;DBSCAN算法

中圖分類號：TP301 文獻標識碼：A

文章編號：1009-3044（2020）15-0052-05

1引言

聚類是通過發現數據集中數據之間的相關關系，將數據分類到不同的類或簇的過程。聚類并不關心某一類別的信息，其目標是將相似的樣本聚在一起，實現同一類對象的相似度盡可的大，而不同類對象之間的相似度盡可能地小。因此，聚類算法只需要知道如何計算樣本之間的相似性，就可以對數據進行聚類。

目前聚類的方法很多，根據基本思想的不同，大致可以將聚類算法分為五大類：層次聚類算法、分割聚類算法、基于約束的聚類算法、機器學習中的聚類算法和用于高維度的聚類算法。

選取劃分聚類算法中傳統的K-means算法、層次聚類算法中具有代表性的AGNES算法以及典型的基于密度的聚類算法DBSCAN等三種算法對不同數據集的聚類效果進行分析，歸納不同聚類算法優缺點。

2算法相關理論

2.1 K-means算法的基本原理及實現步驟

2.1.1 K-means算法的基本原理

K-Means是典型的劃分聚類算法，其中K表示的是聚類為k個簇，Means代表取每一個聚類中數據值的均值作為該簇的中心，或者稱為質心，即用每一個類的質心對該簇進行描述。

K-Means算法的原理是對于給定的數據集，按照各數據點之間的距離大小關系，將數據集戈0分為K個簇。目標是實現簇內的點盡可能緊密的連在一起，而讓簇間的各點之間的距離盡可能大。在這里，距離是指各點之間的歐式距離。

2.1.2 K-means算法的實現步驟

第一步：在樣本數據集中任選k個樣本點作為初始的簇心;

第二步：掃描每個樣本點，求該樣本點到各個簇心之間的距離，選擇其中最短距離的簇心，并將樣本點歸入該簇心所表示的類;

第三步：分別對每個類中的所有樣本點求均值，作為新的簇心;

第四步：重復第二步和第三步，直至達到最大迭代次數，或者更新后的簇心與原來的簇心幾乎吻合（形成不動點）。

2.2 AGNES算法的基本原理及實現步驟

2.2.1 AGNES算法的基本原理

AGNES算法是具有代表性的層次聚類方法，采用自底向上聚合策略的算法。其思想是最初將每個對象作為一個簇，然后這些簇根據某些準則被一步步地合并。兩個簇間的相似度有多種不同的計算方法。聚類的合并過程反復進行直到所有對象最終滿足簇數目。

2.2.2 AGNES算法的實現步驟

第一步：將每個對象當成一個初始簇;

第二步：

REPEAT

計算任意兩個簇的距離，并找到最近的兩個簇;

合并兩個簇，生成新的簇的集合;

UNTIL終止條件得到滿足。

終止條件：

（1）設定一個最小距離閾值d，如果最相近的兩個簇間的距離已經超過d，則無須合并，即聚類終止。

（2）限定簇的個數k，當得到的簇的個數已經達到k，則聚類終止。

2.3 DBSCAN算法的基本原理及實現步驟

2.3.1 DBSCAN算法的基本原理

DBSCAN算法是一種基于密度的數據聚類方法，也是較常用的聚類方法。該算法將具有足夠密度的區域劃分為簇，不斷生長該區域。其基于一個事實：一個聚類可以由其中的任何核心對象唯一確定。

DBSCAN算法利用基于密度的聚類的概念，要求聚類空間中一定區域內（eps范圍內）所包含對象（點或其他空間對象）的數目不小于某一給定閾值（MinPts）。該算法能夠在具有噪聲的空間數據集中發現任意形狀的簇，并且可將密度足夠大的相鄰區域連接，從而對異常數據實現有效處理。其中，最重要的兩個參數為：掃描半徑（eps）和最小包含點數（MinPts）。

2.3.2 DBSCAN算法的實現步驟

第一步：DBSCAN通過檢查數據集中各個點的eps鄰域來搜索簇，如果點p的eps鄰域包含的點多于MinPts個，則創建一個以p為核心對象的簇;

第二步：DBSCAN迭代地聚集從這些核心對象直接密度可達的對象，該過程可能涉及一些密度可達簇的合并;

第三步：重復第一步和第二步，直到沒有新的點添加到任何簇時，該過程結束。

3三種典型聚類算法分析方式

3.1分析方式

考慮到針對不同的數據集，上述三種算法聚類得到的效果可能略有差異。選取兩種數據集：Iris Data Set和小規模的非凸數據集，對上述三種算法進行簡單的比較分析。

為了評估各算法對數據集的聚類效果，采取兩種分析方式：一是可視化聚類結果;二是利用FMI值，來分析比較對已有標簽數據集的聚類效果。

3.2評估方式

（1）可視化聚類結果：將得到的聚類結果繪制成二維圖像，與實際數據集圖像比較，大致觀察聚類效果。

（2）FMI（Fowlkes-Mallows IndeX）：對聚類結果和真實值計算得到的召回率和精確率進行幾何平均的結果，取值范圍為[0，1]，越接近1越好。故通過比較其值是否接近于1，來大致判斷聚類效果。

4Iris Data Set比較效果

為了分析比較上述三種算法的差異，選取了經典的數據集Iris Data Set，通過評估三者對數據集的聚類效果，來分析各算法間的優缺點。

4.1IrisDataSet

Iris Data Set（鳶尾屬植物數據集）是歷史比較悠久的數據集，也是聚類分析常用的數據集。它首次出現在著名的英國統計學家和生物學家Ronald Fisher 1936年的論文《The use of mul-tiple measurements in taxonomic problems》中，被用來介紹線性判別式分析。在這個數據集中，包括了三類不同的鳶尾屬植物：Iris Setosa，Iris Versicolour，Iris Virginica。每類分別收集了50個樣本，共包含了150個樣本。

該數據集測量了所有150個樣本的4個特征，分別是：

（1）sepal length（花萼長度）

（2）sepal width（花萼寬度）

（3）petal length（花瓣長度）

（4）petal width（花瓣寬度）

以上四個特征的單位都是厘米（ca）。

通常使用m表示樣本量的大小，n表示每個樣本所具有的特征數。因此在該數據集中，m=150，n=4。

利用該數據集4個特征中的前兩個f即花萼的長度和寬度），來展示所有的樣本點。選取sepallength和sepalwidth為坐標軸來繪制二維圖像，如圖1所示：

4.2 K-Means算法聚類

利用Python sklearn模塊中自帶的K-Means聚類模塊來對Iris Data Set進行聚類分析。由于已經知道數據集的分類數目（即K值）為3，故我們選取最終劃分成的簇數n_clusters的值也為3。以此，選取最佳的K值來得到K-Means中的最佳聚類效果。本文選取sepallength和sepalwidth為坐標軸來繪制二維圖像，可視化聚類結果如圖2所示：

4.3 AGNES算法聚類

利用Python sklearn模塊中自帶的Agglomerative Clustering聚類模塊來對Iris Data Set進行聚類分析。由于已經知道數據集的分類數目為3，故我們選取最終劃分成的簇數n_clusters的值也為3。同時設置參數linkage的值為"waYd”，表示定義類之間的距離為其間的離差平方和。以此，近似得到AGNES中的最佳聚類效果。選取sepal length和sepal width為坐標軸來繪制二維圖像，可視化聚類結果如圖3所示：

比較實際分類的圖1和AGNES聚類得到的圖3，可以發現選取n_clusters值為3的AGNES聚類模型，能夠得到較符合實際的結果，即取得了較好的聚類效果。

經計算，簇數為3時的AGNES聚類模型的FMI值為0.822170。

4.4 DBSCAN算法聚類

利用Pvthon sklearn模塊中自帶的DBSCAN聚類模塊來對Iris Data Set進行聚類分析。DBSCAN需要兩個重要參數：掃描半徑（eps）和形成高密度區域所需要的最少點數（MinPts）。MinPts的選取有一個指導性的原則，MinPts≥dim+1，其中dim表示待聚類數據的維度。由于已知數據集中每個樣本所

具有的特征數為4，不妨設置MinPts為5。而設置掃描半徑eps為默認值0.5。以此，初步觀察當前DBSCAN聚類模型的聚類效果。選取sepal length和sepal width為坐標軸來繪制二維圖像，可視化聚類結果如圖4所示：

觀察圖4可知：因為DBSCAN算法不需要預先指定聚類的類數，所以最后得到的類數也不確定。而在選取掃描半徑eps為0.5H.最少點數MinPts為5時的DBSCAN聚類模型將該數據集聚成了兩類，與實際結果并不相符，即聚類效果不理想。

經計算，掃描半徑eps為0.5，最少點數MinPts為5時的DB-SCAN聚類模型的FMI值為0.705385。

由于上述所得結果不理想，故簡單調整其參數eps和Minpts，得到與之對應的FMI值及相應的聚類類數，得到表1：

選取eps=0.43、Minpts=7時的DBSCAN模型作為近似的DBSCAN算法的最佳聚類效果，如圖5所示。

可見，DBSCAN算法對eps及Minpts兩個參數極其敏感。在實際聚類的過程中，必須找到最佳的參數值，才能得到良好的聚類效果。否則，兩參數值的細微變化將會導致其聚類效果的較大差異。

4.5分析比較

根據三種算法的聚類效果，可以看出針對Iris Data Set，K-Means算法與AGNES算法的聚類結果近似，且優于DBSCAN算法的聚類結果。

其原因是DBSCAN算法很難通過觀察來得到合適的參數——掃描半徑eps和最少點數Minpts。而上述參數值的細微變化，又會導致聚類結果產生較大差異。故，DBSCAN算法的關鍵便是找到合適的參數——eps和Minpts。

進一步考慮參數簇數n_clusters的選取，分析其對K-Means模型和AGNES模型的聚類效果的影響程度，通過列出簇數n_clusters與之對應的FMI值表格，來度量其間的影響程度如表2所示：

可見，K-Means算法與AGNES算法雖然也需要明確參數簇數n_clusters，但兩者對參數不會像DBSCAN算法那樣敏感。此外，在某些領域中，可以通過觀察來確定簇數的大致范圍。

5小規模非凸數據集比較效果

利用Python sklearn模塊中自帶的make_moons函數和make_blobs函數，加入高斯噪聲來生成小規模的非凸數據集，其各樣本點分布如圖6所示。構造的數據集的樣本量大小為2000，每個樣本所具有的特征數為2，整體大致分為三類。

5.1 K-Means算法聚類

依據上一部分的發現，k-means依賴于K值的選取。于是選取K值為3，來近似得到K-Means的最佳聚類效果。K-Means模型的聚類效果如圖7所示。

可見，K-Means算法對噪聲和離群值非常敏感，對非凸區域的鑒別效果不理想。查閱資料可知：

K-Means算法需要數據符合以下三個條件，才能得到較為良好的聚類效果：

（1）數據集中每個變量的方差基本上要保持相同

（2）每一個cluster中每個變量都近似正態分布（或者眾數等于中位數的對稱分布）

（3）每一個cluster中的元素個數要基本相同

其中，條件1和條件2幾乎保證每個cluster看起來像是球形而不是橢球形。上述三個條件，會使K-Means算法傾向于得到大小接近的凸型cluster。故，K-Means算法對非凸數據集的聚類效果不佳。

5.2 AGNES算法聚類

由于已經知道數據集的分類數目為3，故選取最終劃分成的簇數n_clusters的值也為3。同時設置參數linkage的值為“ward”，表示定義類之間的距離為其間的離差平方和。以此，近似得到AGNES算法的最佳聚類效果。AGNES模型的聚類效果如圖8所示：

可見基于此數據集，AGNES算法的聚類效果略優于K-Means算法，但其對非凸數據集并不能起到很好的聚類效果。

5.3 DBSCAN算法聚類

依據上一部分的發現，DBSCAN算法對參數eps和Minpts是較為敏感的。為了獲得近似最佳的DBSCAN模型的聚類效果，通過調整兩個參數值，以找到最符合實際劃分的DBSCAN模型。

當選取eps=0.5，Minpts=5時，整個數據集被聚成了一個大類，如圖9所示：

當選取eps=0.1，Minpts=5時，整個數據集被很好地分為三個類別，符合實際觀察情況，如圖10所示。

可見：DBSCAN算法能夠發現任意形狀的簇類，無論數據集本身是凸還是非凸，也能夠識別噪聲。但聚類的效果與參數的選取有較大關系。

6結論

6.1 K-Means算法與AGNES算法比較

K-Means算法的時間復雜度和空間復雜度都較低，即使對于大型數據集，也是簡單高效的。而AGNES算法的時間復雜度高，并不適合大型數據集。此外，對于AGNES算法一旦凝聚形成了新簇，就不會對此再發生更改。雖然，k-means算法與AGNES算法都需要指定劃分的簇數，但由于k-means算法需要挑選初始中心點，故其對初始值的設置很敏感。一般而言，上述兩種算法都對非凸數據集無法起到良好的聚類效果，但在中小型數據集中挖掘得到球形簇的效果較好。

6.2 K-Means算法與DBSCAN算法比較

與K-Means算法相比，DBSCAN算法不需要明確K值，即不需要事先指定形成簇類的數量。此外，DBSCAN算法可以發現任意形狀的簇類，也能夠識別出噪聲點。而K-Means算法對噪聲和離群值非常敏感，并且對非凸數據集的聚類效果不佳。當數據集較大時，K-Means算法容易陷入局部最優。雖然DB—SCAN算法具有眾多優點，但其對兩個參數eps和Minpts的設置卻非常敏感，導致聚類的效果與參數值的選取有較大關系。

6.3 AGNES算法與DBSCAN算法比較

AGNES算法可解釋性好，能產生高質量的聚類，但其時間復雜度較高，不適合大型數據集。同時，AGNES算法與K-Means算法類似，傾向于得到凸型的cluster，對非凸數據集并不能得到較好的聚類效果。而DBSCAN算法可以發現任意形狀的簇類。

7結語

K-means算法、AGNES算法、DBSCAN算法分別是聚類算法中基于劃分、層次、密度的三種典型算法。通過對上述三種算法的簡單分析比較，我們可以依據實際情況選取最為合適的算法對數據集進行聚類，從而得到最佳的效果。