基于密度和中心指標的Canopy二分K-均值算法優化*

沈郭鑫，蔣中云

(1.上海海洋大學信息學院， 上海 201306；2.上海建橋學院信息技術學院， 上海 201306)

1 引言

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

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

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

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

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

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

2 基于密度的Canopy算法

2.1 Canopy算法

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

Figure 1 Classification result of Canopy algorithm 圖1 Canopy算法分類結果圖

Canopy算法的步驟如下所示：

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

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

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

步驟4數據集D為空之前，一直重復步驟2和步驟3。

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

2.2 基于密度的Canopy算法

2.2.1 基本概念

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

(1)

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

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

(2)

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

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

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

(3)

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

(4)

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

2.2.2 算法流程

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

步驟2結合傳統Canopy算法思想，利用式(3)和式(4)對數據進行聚類。

步驟3循環執行步驟2，在剩余數據中選出符合條件的數據，直至遍歷完所有數據。

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

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

a 步驟1示意圖

3 SDC_Bisecting K-Means算法

3.1 Bisecting K-Means算法描述

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

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

(5)

其中,ci為簇Ci的中心，z為簇Ci內的任意一數據，K為聚類數。

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

3.2 改進誤差平方和

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

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

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

(6)

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

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

經過調節后的SSE計算公式如式(7)所示：

(7)

其中，K為聚類的簇數，ci為簇Ci的中心，z為簇Ci內的任意一數據，θz為數據z的中心指標，計算如式(8)所示：

θz=wz×dz

(8)

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

(9)

(10)

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

(11)

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

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

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

接著，利用二分K-均值算法進行遍歷，將得到的數據依次存入新建的數組中，并循環遍歷；

最后，利用Matplotlib繪制實驗結果。

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

Table 1 SSE on iris dataset

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

3.3 算法流程

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

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

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

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

步驟4結合Canopy算法原理，對原始數據集進行聚類，并統計各鄰域δm的樣本數量n′。

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

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

步驟7輸入原始數據，并結合步驟6產生的結果，利用Bisecting K-Means算法進行分類,并利用式(7)計算簇內的誤差和SSE。

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

算法流程圖如圖5所示。

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

4 實驗環境及結果

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

4.1 UCI數據集

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

Table 2 Datasets description

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

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

(12)

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

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

(13)

(14)

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

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

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 公共數據集上的Jaccard 指數對比圖

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

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

Figure 9 Comparison chart of accuracy on public datasets圖9 公共數據集上的準確率對比圖

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

Figure 11 Comparison chart of accuracy on self-built datasets圖11 自建數據集上的準確率對比圖

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

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

從圖6～圖8的算法評價指標中可以看出，本文所提出的SDC_Bisecting K-Means算法要優于Bisecting K-Means算法、文獻[12,14] 算法和AGNES算法。從圖9所示準確率來看，本文算法有較大的提升。

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

4.2 自建數據集

為了進一步驗證本文算法的穩定性及其聚類效果，隨機設計了含有正態分布的二維自建數據集，如表5所示。

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

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

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

5 結束語

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