基于密度和中心指標(biāo)的Canopy二分K-均值算法優(yōu)化*

沈郭鑫，蔣中云

(1.上海海洋大學(xué)信息學(xué)院， 上海 201306；2.上海建橋?qū)W院信息技術(shù)學(xué)院， 上海 201306)

1 引言

聚類算法在數(shù)據(jù)挖掘中運用廣泛，其中K-均值(K-Means)聚類算法最為經(jīng)典。由于該算法簡單、實用以及能快速收斂等特點，被廣泛運用于商業(yè)[1]、特征學(xué)習(xí)[2]和電子商務(wù)[3]等領(lǐng)域。

傳統(tǒng)的K-均值算法通過隨機(jī)選取中心點以及人為設(shè)定K值的方式對原始數(shù)據(jù)進(jìn)行分類。換言之，這2個條件對聚類結(jié)果的好壞起著決定性的作用。因此，有學(xué)者提出二分K-均值算法Bisecting K-Means。該算法是先通過K-均值將原始數(shù)據(jù)分成2類，然后從這些類別中再選取數(shù)據(jù)繼續(xù)二分，直至滿足給定的數(shù)目K[4,5]，較好地克服了對初始中心敏感的問題。但是，從本質(zhì)上看，該算法與K-均值算法一樣，最后得到的聚類結(jié)果也會受到初始中心以及K值的影響，使得結(jié)果不穩(wěn)定[6]。

本文針對二分K-均值算法對初始中心敏感、簇類數(shù)目難以確定以及計算簇內(nèi)誤差時存在分類差的誤差和分類優(yōu)的誤差一同計算的問題，提出了一種基于樣本密度和中心指標(biāo)的Canopy二分K-均值算法改進(jìn)算法SDC_Bisecting K-Means(optimized Canopy Bisecting K-Means algorithm based on Sample Density and Central index)。以下是本文的重點工作：

(1)計算每個樣本點的密度，選取密度最小的點作為第1個中心，并計算該點的鄰域范圍；然后利用Canopy算法對數(shù)據(jù)進(jìn)行粗聚類，依次循環(huán)，直至原始數(shù)據(jù)集為空；最終確認(rèn)樣本的初始中心以及簇類數(shù)。

(2)在利用二分K-均值算法產(chǎn)生的簇內(nèi)誤差計算中引入指數(shù)函數(shù)，并將每個數(shù)據(jù)離自身最近中心點的距離以及鄰域密度的乘積作為中心指標(biāo)對指數(shù)進(jìn)行縮放，防止因指數(shù)過大影響最終的實驗結(jié)果。

利用UCI數(shù)據(jù)集以及自建數(shù)據(jù)集進(jìn)行實驗測試，結(jié)果表明該算法不僅能有效確定聚類數(shù)目和聚類中心，還提高了算法的準(zhǔn)確率，減少算法迭代次數(shù)，具有良好的穩(wěn)定性。

2 基于密度的Canopy算法

2.1 Canopy算法

Canopy算法是一種無監(jiān)督聚類算法，該算法可以作為劃分聚類和層次聚類的初始步驟[12]，其核心是將原始數(shù)據(jù)劃分成若干個canopy，每個canopy中包含一個或是多個樣本數(shù)據(jù)[13]，且無需設(shè)定簇的數(shù)目，劃分后的結(jié)果如圖1所示。因此，將每個canopy的中心點及其個數(shù)作為Bisecting K-Means算法的初始中心和聚類數(shù)。

Figure 1 Classification result of Canopy algorithm 圖1 Canopy算法分類結(jié)果圖

Canopy算法的步驟如下所示：

步驟1隨機(jī)排列原始數(shù)據(jù)得到D={x1,x2,…,xn}，然后利用交叉驗證設(shè)定參數(shù)T1和T2，且T1>T2。

步驟2從數(shù)據(jù)集D中隨機(jī)選取一個數(shù)據(jù)xi作為第1個canopy的中心，并刪除所選數(shù)據(jù)xi。

步驟3從數(shù)據(jù)集D中隨機(jī)選取一數(shù)據(jù)xj，計算xj到所有中心的距離d。若dT1，則表示該數(shù)據(jù)屬于另一個新的簇。

步驟4數(shù)據(jù)集D為空之前，一直重復(fù)步驟2和步驟3。

由于Canopy算法中的2個閾值T1、T2對聚類結(jié)果影響最大,若沒能很好地選取閾值，則會直接影響最終的實驗結(jié)果。為了盡可能降低T1、T2對聚類結(jié)果的影響，本文引入樣本密度這一概念，目的是為了找出樣本中密度最小的數(shù)據(jù)，同時降低步驟2中隨機(jī)選取初始中心對實驗造成的影響。

2.2 基于密度的Canopy算法

2.2.1 基本概念

假設(shè)數(shù)據(jù)集D={x1,x2,…,xn}包含n個樣本，每個樣本有p維屬性特征，在算法中，數(shù)據(jù)xi與xj之間的距離用歐氏距離表示[14]，如式(1)所示：

(1)

其中，i=1,2,…,n;j=1,2,…,n。

利用式(2)計算每個數(shù)據(jù)的密度值，尋找密度最小的數(shù)據(jù)xmin作為聚類的中心[15]：

(2)

其中i=1,2,…,n。

以數(shù)據(jù)xmin為中心，(m-1)×R和m×R為半徑形成的環(huán)形區(qū)域，稱為數(shù)據(jù)xi的m鄰域范圍，記為δm[16]。隨著中心xi的密度增大，其所屬鄰域內(nèi)的數(shù)據(jù)越稀疏，對應(yīng)的半徑也會相應(yīng)增大，計算公式如式(3)所示：

xj∈δm,if (m-1)×R≤dist(xmin,xj)

(3)

其中,m=1,2,…,K,R表示初始聚類中心的寬度,如式(4)所示：

(4)

其中,i,j=1,2,…,n；K為聚類的簇數(shù)；max(d)為距離數(shù)據(jù)xi最遠(yuǎn)的數(shù)據(jù)與xmin的歐氏距離；min(d)為距離數(shù)據(jù)xi最近的數(shù)據(jù)與xmin的歐氏距離；d=dist(xmin,xj)。

2.2.2 算法流程

步驟1根據(jù)式(2)計算出樣本集合中所有數(shù)據(jù)的density(xmin)，由于密度小的樣本意味著該樣本所處區(qū)域越密集，因此將xmin作為第1個初始中心，記為c1，將c1添加到中心集合C中，此時C={c1}。

步驟2結(jié)合傳統(tǒng)Canopy算法思想，利用式(3)和式(4)對數(shù)據(jù)進(jìn)行聚類。

步驟3循環(huán)執(zhí)行步驟2，在剩余數(shù)據(jù)中選出符合條件的數(shù)據(jù)，直至遍歷完所有數(shù)據(jù)。

步驟4判斷是否存在除簇內(nèi)中心外剩余簇數(shù)為個位數(shù)的簇。若存在，則將這些數(shù)據(jù)分配到距離中心點最近的簇中；若不存在，則循環(huán)結(jié)束，輸出最終的劃分結(jié)果。

最后，取出集合C中的數(shù)據(jù)。此時每個簇內(nèi)的數(shù)據(jù)到中心的距離之和均為最優(yōu)值。因此，確定了初始的聚類中心和聚類數(shù)。過程示意圖2所示。

a 步驟1示意圖

3 SDC_Bisecting K-Means算法

3.1 Bisecting K-Means算法描述

聚類算法是根據(jù)數(shù)據(jù)屬性相似性的大小來劃分?jǐn)?shù)據(jù)，每個類別中的數(shù)據(jù)都具有相似的屬性。聚類分析算法可以劃分為劃分聚類算法、層次聚類算法[17]、密度聚類算法、網(wǎng)格聚類算法和模型聚類算法。Abuaiadah[18]以K-Means為基礎(chǔ)算法進(jìn)行改進(jìn)得到Bisecting K-Means算法，雖然該算法改善了聚類效果，但隨機(jī)選取初始中心的缺點沒有改變。

對比K-Means算法，Bisecting K-Means算法得到的聚類結(jié)果更為穩(wěn)定，該算法同樣采用誤差平方和SSE(Sum of Squared Error)來衡量聚類的效果，如式(5)所示：

(5)

其中,ci為簇Ci的中心，z為簇Ci內(nèi)的任意一數(shù)據(jù)，K為聚類數(shù)。

該算法的中心思想是：將原始數(shù)據(jù)分成2個簇，并存放到集合S中，選取其中某一個簇運用K-Means算法進(jìn)行二分類，從分裂的簇中選取2個SSE總和最小的子簇，將其添加到集合S中，更新集合，依次循環(huán)，直至產(chǎn)生K個簇。

3.2 改進(jìn)誤差平方和

由于傳統(tǒng)的簇內(nèi)誤差平方和SSEi計算存在一個問題：通過求和產(chǎn)生的誤差會使得原本分類效果較差的簇中和分類效果較好的簇。例如，當(dāng)K=2時，會出現(xiàn)以下2種情況：(1)(SSE1=120，SSE2=120)；(2)(SSE1=30，SSE2=210)。一般情況下研究者會選擇第1種，分類比較均勻，但兩者的總誤差都是240。因此，為了解決這個問題，本文引入指數(shù)函數(shù)ex[19]。該函數(shù)具有單調(diào)遞增的特性，而且對于指數(shù)的變化非常敏感。圖3所示是不同函數(shù)在坐標(biāo)軸第一象限內(nèi)的對比。

Figure 3 Variation curves of different functions圖3 不同函數(shù)變化曲線

從圖3中可以看出，指數(shù)函數(shù)ex的增長趨勢更加明顯。因此，在式(5)中引入指數(shù)函數(shù)，能進(jìn)一步優(yōu)化聚類效果，避免在出現(xiàn)分類良好的簇中加入不屬于該簇的數(shù)據(jù)，改進(jìn)后的簇內(nèi)誤差平方和公式如式(6)所示：

(6)

在實際實驗時可能會出現(xiàn)以下情況：在同一簇中某一數(shù)據(jù)z到中心的距離相對較遠(yuǎn)，導(dǎo)致計算出來的簇內(nèi)誤差平方和較大。而指數(shù)函數(shù)對指數(shù)的變化非常敏感，使得產(chǎn)生的函數(shù)值過大，甚至出現(xiàn)“指數(shù)溢出”的現(xiàn)象。因此，本文引入中心指標(biāo)θ[20]對簇內(nèi)誤差平方進(jìn)行縮放，其效果如圖4所示。

Figure 4 Change curve of ex before and after the introduction of θ 圖4 引入θ前后的ex曲線

經(jīng)過調(diào)節(jié)后的SSE計算公式如式(7)所示：

(7)

其中，K為聚類的簇數(shù)，ci為簇Ci的中心，z為簇Ci內(nèi)的任意一數(shù)據(jù)，θz為數(shù)據(jù)z的中心指標(biāo)，計算如式(8)所示：

θz=wz×dz

(8)

其中，wz為z的權(quán)值;dz為z到距離自身最近的簇中心xi的距離。其計算公式分別如式(9)和式(10)所示：

(9)

(10)

其中，K為聚類中心數(shù)，d(xi,z)為數(shù)據(jù)之間的歐氏距離；式(10)中，num為初始變量，由于實驗中將數(shù)據(jù)以數(shù)組的形式保存，因此qnum-1表示取當(dāng)前下標(biāo)為[num-1]的數(shù)據(jù);mz為數(shù)據(jù)z鄰域內(nèi)的對象數(shù)，range表示數(shù)據(jù)集的空間大小，其計算方式與歐氏距離類似，如式(11)所示：

(11)

其中,p表示原始數(shù)據(jù)集的維度；maxzz、minzz為對應(yīng)維度的2個最值。θz越大，表示簇內(nèi)數(shù)據(jù)越緊密，此時SSE越小，分類效果越好。同時，減少了Bisecting K-Means算法的迭代次數(shù)，提高了運行效率。

以iris數(shù)據(jù)集為例，利用改進(jìn)后的誤差平方和計算公式，選擇過程如下所示：

首先，創(chuàng)建一個K行2列的數(shù)組用來存放對應(yīng)的聚類數(shù)K與誤差平方和SSE，為了便于說明實驗效果，聚類數(shù)K的取值為[1，8]；

接著，利用二分K-均值算法進(jìn)行遍歷，將得到的數(shù)據(jù)依次存入新建的數(shù)組中，并循環(huán)遍歷；

最后，利用Matplotlib繪制實驗結(jié)果。

實驗中利用式(5)和式(7)在不同的聚類數(shù)K情況下計算SSE，得到的結(jié)果如表1所示。

Table 1 SSE on iris dataset

從表1中可以看出，K取值在[1，4]時，引入指數(shù)函數(shù)的SSE下降效果更加明顯，因此利用式(7)能夠有效地解決求和過程中誤差相互中和的問題。

3.3 算法流程

SDC_Bisecting K-Means算法流程如下所示：

步驟1根據(jù)式(2)計算每個樣本數(shù)據(jù)的密度值density(xi)，并將計算結(jié)果降序排序。

步驟2選取密度值最小的xi計算其余樣本數(shù)據(jù)到xi的歐氏距離d。

步驟3根據(jù)式(3)和式(4)計算出該數(shù)據(jù)的鄰域δm。

步驟4結(jié)合Canopy算法原理，對原始數(shù)據(jù)集進(jìn)行聚類，并統(tǒng)計各鄰域δm的樣本數(shù)量n′。

步驟5判斷是否存在n′為個位數(shù)的簇。若不存在，則轉(zhuǎn)到步驟6；若存在，則將這些簇中的數(shù)據(jù)就近分配到與之距離最近的簇中。

步驟6選擇數(shù)量最多的前2個簇中心作為二分K-Means算法的初始中心。

步驟7輸入原始數(shù)據(jù)，并結(jié)合步驟6產(chǎn)生的結(jié)果，利用Bisecting K-Means算法進(jìn)行分類,并利用式(7)計算簇內(nèi)的誤差和SSE。

步驟8判斷當(dāng)前SSE與上一次SSE是否一致。若一致，則聚類結(jié)束；若不一致，則根據(jù)SSE選擇聚類效果差的簇繼續(xù)拆分，直至SSE不再發(fā)生變化。

算法流程圖如圖5所示。

Figure 5 Flow chart of SDC_Bisecting K-Means algorithm 圖5 SDC_Bisecting K-Means算法流程圖

4 實驗環(huán)境及結(jié)果

本文的實驗環(huán)境為AMD Ryzen 5 3600 6-Core Processor，3.60 GHz，16 GB內(nèi)存，操作系統(tǒng)為Windows 10，利用PyCharm軟件編寫代碼。實驗中，先利用部分公共數(shù)據(jù)集進(jìn)行實驗。之后為了驗證本文提出算法的準(zhǔn)確率，在自建數(shù)據(jù)集上進(jìn)行對比實驗。

4.1 UCI數(shù)據(jù)集

選取UCI數(shù)據(jù)中常用的公共數(shù)據(jù)集對本文提出的SDC_Bisecting K-Means算法進(jìn)行測試，并與傳統(tǒng)的二分K-Means算法、密度與劃分聚類結(jié)合的算法[12,14]以及層次聚類中的凝聚層次聚類AGNES(AGglomerative NESting)算法進(jìn)行對比實驗。表2所示為實驗中運用的公共數(shù)據(jù)集說明。

Table 2 Datasets description

為驗證本文算法的聚類效果，將每個算法分別運行10次，取平均值。評價指標(biāo)中除采用算法平均運行時間、聚類平均準(zhǔn)確率和平均誤差平方和之外，還利用了Jaccard 指數(shù)[21]、輪廓系數(shù)和Adjust- ed Rand Index系數(shù)[22]。其中Adjusted Rand Index系數(shù)是在已知明確分類的前提下對聚類結(jié)果進(jìn)行評估。

輪廓系數(shù)的計算方式如式(12)所示：

(12)

其中，a(i)為數(shù)據(jù)xi與簇內(nèi)其余數(shù)據(jù)的平均距離，b(i)為數(shù)據(jù)xi與其它簇中數(shù)據(jù)的最小值平均距離。輪廓系數(shù)越接近1或系數(shù)值越大，簇內(nèi)數(shù)據(jù)越緊湊，聚類效果越好。

Jaccard 指數(shù)(J)與Adjusted Rand Index系數(shù)(ARI)定義如下：假設(shè)U和V是樣本標(biāo)簽的2種分配情況，其中U表示已知的分類結(jié)果，而V表示經(jīng)過算法得到的結(jié)果。定義a表示U跟V共有的樣本數(shù)；b為在U中屬于同一類，而V中位于不同類的樣本數(shù)；c為在V中屬于同一類，而U中位于不同類的樣本數(shù)；d為在U和V中都不在同一類的樣本數(shù)。且M=a+b+c+d，M為樣本的總數(shù)。2個系數(shù)的計算分別如式(13)和式(14)所示：

(13)

(14)

Jaccard 指數(shù)表示聚類后正確分類的樣本數(shù)占聚類前后同一樣本的比重；ARI參數(shù)數(shù)值越大或越接近于1，聚類效果越好，越接近于-1，說明聚類結(jié)果與原始樣本分類越不一致。

實驗的結(jié)果如表3、表4和圖6～圖9所示。表3和表4分別為4種算法的平均運行時間和平均誤差平方和的比較。圖9～圖12分別為4種算法的Jaccard 指數(shù)、輪廓系數(shù)、Adjusted Rand Index系數(shù)和準(zhǔn)確率的比較。

Table 3 Comparison of average running time on public datasets

Table 4 Comparison of mean SSE

Figure 6 Comparison chart of Jaccard index on public datasets圖6 公共數(shù)據(jù)集上的Jaccard 指數(shù)對比圖

Figure 7 Comparison chart of contour coefficient on public datasets圖7 公共數(shù)據(jù)集上的輪廓系數(shù)對比圖

Figure 8 Comparison chart of Adjusted Rand Index coefficient on public datasets圖8 公共數(shù)據(jù)集上的Adjusted Rand Index系數(shù)對比圖

Figure 9 Comparison chart of accuracy on public datasets圖9 公共數(shù)據(jù)集上的準(zhǔn)確率對比圖

Figure 10 Comparison chart of Adjusted Rand Index coefficient on self-built datasets圖10 自建數(shù)據(jù)集上的Adjusted Rand Index系數(shù)對比圖

Figure 11 Comparison chart of accuracy on self-built datasets圖11 自建數(shù)據(jù)集上的準(zhǔn)確率對比圖

由表3可知，本文所提出的改進(jìn)算法，其運行效率要優(yōu)于文獻(xiàn)[12,14]算法和AGNES算法，但在維度高、數(shù)量大的數(shù)據(jù)集上，如ionosphere數(shù)據(jù)集，本文算法的運行時間不及文獻(xiàn)[14]算法和AGNES算法的。因為會有遺漏的離群點，導(dǎo)致計算的距離增大而消耗部分時間。

由表4可知，在soybean-small數(shù)據(jù)集上，本文算法的平均誤差平方和比二分K-Means算法與AGNES算法的高，但明顯小于文獻(xiàn)[12，14]算法的；在ionoshpere數(shù)據(jù)集上，本文算法的平均誤差平方和與文獻(xiàn)[12,14]算法的結(jié)果一樣，但小于二分K-Menas算法與AGNES算法的；在其余數(shù)據(jù)集上，本文算法的平均誤差平方和都明顯小于其它算法的。因此，本文提出的SDC_Bisecting K-Means算法具有較好的穩(wěn)定性。

從圖6～圖8的算法評價指標(biāo)中可以看出，本文所提出的SDC_Bisecting K-Means算法要優(yōu)于Bisecting K-Means算法、文獻(xiàn)[12,14] 算法和AGNES算法。從圖9所示準(zhǔn)確率來看，本文算法有較大的提升。

綜合上述算法指標(biāo)和準(zhǔn)確率可以看出，本文提出的基于密度和中心指標(biāo)的Canopy二分K-Means算法在提高準(zhǔn)確率的前提下，還能更快速地完成聚類并且具有良好的效果。

4.2 自建數(shù)據(jù)集

為了進(jìn)一步驗證本文算法的穩(wěn)定性及其聚類效果，隨機(jī)設(shè)計了含有正態(tài)分布的二維自建數(shù)據(jù)集，如表5所示。

在這些數(shù)據(jù)集上分別利用二分K-Means算法、文獻(xiàn)[12,14]算法、AGNES算法和本文算法進(jìn)行測試。實驗結(jié)果如表6、圖10和圖11所示。其中表6 是各算法運行時間，圖10和圖11為Adjusted Rand Index系數(shù)和準(zhǔn)確率的比較圖。

從表6中可以看出，對于數(shù)據(jù)較少的例如TestSet1和TestSet3等數(shù)據(jù)集，本文算法的運行時間與其它4種算法的沒有明顯差別，但隨著數(shù)據(jù)的增多，本文算法的運行時間優(yōu)于其余4種算法的。

因Adjusted Rand Index系數(shù)是評判聚類算法好壞的最好標(biāo)準(zhǔn)，故在自建數(shù)據(jù)集上只使用這一個評價指標(biāo)[23]。從圖10中可以看出，除了在TestSet3數(shù)據(jù)集上，本文算法的ARI稍低于文獻(xiàn)[12]算法的ARI外，在剩余的數(shù)據(jù)集上，本文算法的ARI都明顯高于其它4種算法的；由圖11可知，本文算法的聚類結(jié)果明顯優(yōu)于其它4種算法的。

5 結(jié)束語

本文通過對傳統(tǒng)K-Means算法、二分K-Means算法和相應(yīng)改進(jìn)算法的分析，提出了基于密度和中心指標(biāo)的Canopy二分K-Means算法——SDC_Bisecting K-Means算法。該算法首先計算樣本中數(shù)據(jù)密度及其鄰域半徑；然后選出密度最小的數(shù)據(jù)并利用Canopy算法進(jìn)行聚類，找出初始中心和最終聚類的簇數(shù)。此算法克服了傳統(tǒng)聚類算法因隨機(jī)選取初始中心和簇數(shù)對實驗結(jié)果的影響。在UCI數(shù)據(jù)集和自建數(shù)據(jù)集上的結(jié)果表明，SDC_Bisecting K-Means算法提高了聚類的準(zhǔn)確率，加快了收斂速度。但是，在實驗中也發(fā)現(xiàn)，對于維度高的數(shù)據(jù)，此算法消耗的時間稍長，因此在今后的研究中需要考慮對數(shù)據(jù)進(jìn)行降維處理；同時，也需要對代碼進(jìn)行改進(jìn)，以進(jìn)一步提高算法的運行效率。