數(shù)據(jù)挖掘中三種典型聚類算法的分析比較

李煜堃

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

關(guān)鍵詞：聚類;K-means算法;AGNES算法;DBSCAN算法

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

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

1引言

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

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

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

2算法相關(guān)理論

2.1 K-means算法的基本原理及實現(xiàn)步驟

2.1.1 K-means算法的基本原理

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

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

2.1.2 K-means算法的實現(xiàn)步驟

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

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

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

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

2.2 AGNES算法的基本原理及實現(xiàn)步驟

2.2.1 AGNES算法的基本原理

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

2.2.2 AGNES算法的實現(xiàn)步驟

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

第二步：

REPEAT

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

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

UNTIL終止條件得到滿足。

終止條件：

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

（2）限定簇的個數(shù)k，當?shù)玫降拇氐膫€數(shù)已經(jīng)達到k，則聚類終止。

2.3 DBSCAN算法的基本原理及實現(xiàn)步驟

2.3.1 DBSCAN算法的基本原理

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

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

2.3.2 DBSCAN算法的實現(xiàn)步驟

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

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

第三步：重復(fù)第一步和第二步，直到?jīng)]有新的點添加到任何簇時，該過程結(jié)束。

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

3.1分析方式

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

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

3.2評估方式

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

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

4Iris Data Set比較效果

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

4.1IrisDataSet

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

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

（1）sepal length（花萼長度）

（2）sepal width（花萼寬度）

（3）petal length（花瓣長度）

（4）petal width（花瓣寬度）

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

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

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

4.2 K-Means算法聚類

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

4.3 AGNES算法聚類

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

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

經(jīng)計算，簇數(shù)為3時的AGNES聚類模型的FMI值為0.822170。

4.4 DBSCAN算法聚類

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

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

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

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

由于上述所得結(jié)果不理想，故簡單調(diào)整其參數(shù)eps和Minpts，得到與之對應(yīng)的FMI值及相應(yīng)的聚類類數(shù)，得到表1：

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

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

4.5分析比較

根據(jù)三種算法的聚類效果，可以看出針對Iris Data Set，K-Means算法與AGNES算法的聚類結(jié)果近似，且優(yōu)于DBSCAN算法的聚類結(jié)果。

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

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

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

5小規(guī)模非凸數(shù)據(jù)集比較效果

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

5.1 K-Means算法聚類

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

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

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

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

（2）每一個cluster中每個變量都近似正態(tài)分布（或者眾數(shù)等于中位數(shù)的對稱分布）

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

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

5.2 AGNES算法聚類

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

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

5.3 DBSCAN算法聚類

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

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

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

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

6結(jié)論

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

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

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

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

6.3 AGNES算法與DBSCAN算法比較

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

7結(jié)語

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