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

李煜堃

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

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

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）15-0052-05

1引言

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

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

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

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

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

2.1.1 K-means算法的基本原理

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

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

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

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

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

第三步：分別對(duì)每個(gè)類中的所有樣本點(diǎn)求均值，作為新的簇心;

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

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

2.2.1 AGNES算法的基本原理

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

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

第一步：將每個(gè)對(duì)象當(dāng)成一個(gè)初始簇;

第二步：

REPEAT

計(jì)算任意兩個(gè)簇的距離，并找到最近的兩個(gè)簇;

合并兩個(gè)簇，生成新的簇的集合;

UNTIL終止條件得到滿足。

終止條件：

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

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

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

2.3.1 DBSCAN算法的基本原理

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

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

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

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

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

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

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

3.1分析方式

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

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

3.2評(píng)估方式

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

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

4Iris Data Set比較效果

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

4.1IrisDataSet

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

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

（1）sepal length（花萼長(zhǎng)度）

（2）sepal width（花萼寬度）

（3）petal length（花瓣長(zhǎng)度）

（4）petal width（花瓣寬度）

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

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

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

4.2 K-Means算法聚類

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

4.3 AGNES算法聚類

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

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

經(jīng)計(jì)算，簇?cái)?shù)為3時(shí)的AGNES聚類模型的FMI值為0.822170。

4.4 DBSCAN算法聚類

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

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

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

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

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

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

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

4.5分析比較

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

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

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

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

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

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

5.1 K-Means算法聚類

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

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

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

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

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

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

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

5.2 AGNES算法聚類

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

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

5.3 DBSCAN算法聚類

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

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

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

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

6結(jié)論

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

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

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

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

6.3 AGNES算法與DBSCAN算法比較

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

7結(jié)語

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