xk-split:基于k-medoids的分裂式聚類算法

陳逸斐, 虞慧群

(1.華東理工大學計算機科學與工程系,上海 200237; 2.上海市計算機軟件重點測評實驗室,上海 201112)

xk-split:基于k-medoids的分裂式聚類算法

陳逸斐1,2, 虞慧群1

(1.華東理工大學計算機科學與工程系,上海 200237; 2.上海市計算機軟件重點測評實驗室,上海 201112)

近年來互聯網數據規模呈爆炸式增長,如何對大數據進行分析已成為熱門話題。然而,采集的數據很難直接用于分析,需要進行一定程度的預處理,以提高大數據質量。通過使用分裂式的迭代過程,可以逐步將數據集分裂為子集,避免了傳統聚類算法聚類開始時需要確定集群數的限制,并降低了算法的時間復雜度。此外,通過基于閾值的噪聲數據過濾,可以在迭代過程中剔除噪音數據,提升了聚類算法對臟數據的忍耐力。

數據挖掘; 聚類; k-means; k-medoids; 分裂

數據的聚類算法是機器學習與數據挖掘中的一大命題,廣泛應用于機器學習、數據挖掘、圖像分析、模式識別等領域中。而聚類算法又可分為硬聚類和軟聚類算法,其中硬聚類算法將目標數據明確地劃分為不同集群,代表算法為k-means算法;而軟聚類算法又稱模糊聚類算法,數據點可能屬于一個或以上的集群,且數據點與集群通過成員水平互相聯系,代表算法為模糊C-均值(FCM)算法。本文針對聚類算法中的硬聚類算法展開討論。

聚類分析的主要工作是將較大規模的數據通過靜態分析的手段劃分為更小的子集,每個子集內部的對象有共同的特征。聚類分析的手段主要分為結構型與分散型算法。結構型算法需要使用已經存在的聚類器進行數據分析,而應用較為廣泛的是分散型聚類算法,其特征是一次性確定所有分類,而且需要指定聚類結果的個數,不明確聚類個數的情況下需要給出估計值。

分散型聚類算法k-means具有簡單、快速的特點,可以在短時間內完成初步的聚類分析。自從該算法被提出后被不斷地改進、完善,出現了例如k-medoids等高效且可靠的聚類算法,一定程度上改進了k-means算法對臟數據敏感的缺點。近年來,除了傳統的模式識別[1-3]、用戶行為分析等領域[4]外,k-medoids還被使用在防范SSDF攻擊[5]等場景中。k-means及其衍生算法的改進也越來越重要。

本文分析研究了現有的分散型聚類算法,使用分裂式的迭代方法替代一開始就確定所有聚類的手段,獲得了時間復雜度和噪聲忍耐度上的提升。另外,基于分裂式的聚類思想,提出了不需要給定聚類數量,而由程序自動完成聚類的新算法。

1 相關工作

1.1 k-means算法

最簡單也是應用最為廣泛的分散型數據聚類算法是由MacQueen提出的無監督聚類算法k-means[6]。k-means的主要實現方法是在數據集中隨機選取k個中心點,隨后循環迭代2個步驟:

(1) 集群。對集合內所有點分別計算其與每個中心點的歐氏距離,選擇最近的一個中心點并加入其集群。

(2) 重新選擇中心點。計算各個集群的質心,將其作為新的中心點。

對整個數據集不斷地重復執行以上步驟,直至集群分布不再改變。

k-means算法以較低的時間成本解決了數據無監督集群問題,但是存在很多問題:

(1) 需要指定k個起始點,即最終集群數量,若要使用k-means算法則知曉數據集共有幾個集群是先決條件。

(2) 在選擇中心點的步驟中使用質心作為新的中心,對臟數據較為敏感。

(3) 其本質是一種貪心算法,僅僅能求得局部最優解。加之起始點是隨機選取的,往往為了獲得一個較為優秀的解,需要重復執行多次k-means算法。

1.2 k-medoids算法

為了解決上述第2個問題,k-medoids算法被提出。該算法對k-means的改進僅僅在于選擇中心點時并不選用質心,而是選用離開集群中所有其他點最近的點。這樣雖然提高了一些對臟數據的寬容度,卻大大地增加了算法的時間復雜度,并且是一個NP-難問題。同時,也并沒有解決k-means存在的其他兩個問題。

現實生活中已對k-medoids有了非常廣泛的應用。由于其隨機性,需要迭代多次以獲得最優解,這個過程具有并行的特性,所以非常適合用戶Hadoop等平臺的大數據分析[7]。同時因為其較為優秀的臟數據耐受能力,也經常被用于用戶行為分析等工作上[8]。

1.3 其他改進的k-means算法

其他針對k-means的改進算法也經常被提出[9]。Xu等[10]提出了F2-k-means (Farest2-k-means)算法,該算法先找出數據集中距離最遠的兩個點,分別形成集群,在數據集中尋找接近集群的點并加入其中,直至到達閾值,再尋找新的點。這兩個算法有一個共同的特點,就是依賴閾值來判斷是否結束迭代,同時,最接近點對的比較也會大幅增加算法的時間復雜度,集群算法的準確度也依賴于閾值的選擇,如圖1所示,選擇閾值為10時,會導致源數據被過度分類。

圖1 閾值為10的F2-k-means算法Fig.1 F2-k-means algorithm with threshold value of 10

Zhou等[11]提出的自適應k-means算法可以使k-means擁有一定的學習能力,用較少的代價增加算法對臟數據的耐受能力,不過也較依賴于數據的規模,僅僅在有充足的數據進行訓練的前提下才會有較好的輸出。Cui等[12]提出了一種k-means的優化方案,在尋找中心點的過程中同時考慮集群內的凝聚度和集群間的分離度,以解決k-means算法僅僅能求得局部最優解的問題,但這個方法同樣大大增加了算法的時間復雜度。

本文在k-medoids算法和F2-k-means的基礎上提出了分裂式自適應聚xk-split算法,具有以下特征:

(1) 可以選擇指定或不指定k個初始點,在集群的過程中判斷出數據最佳的集群數量。

(2) 比k-medoids更穩定,受隨機選點的影響更小。

(3) 對臟數據不敏感,并且可以在集群過程中識別并排除噪聲數據。

(4) 時間復雜度低,在得到更低平均方差集群的同時,比多次執行k-medoids算法需要的時間更少。

2 分裂式自適應聚類算法xk-split

2.1 xk-split算法的迭代單元

xk-split算法不同于k-means和k-medoids算法,迭代開始時并不會確定k個初始集群,而是先確定2個集群,然后再將其逐步分裂成k個小集群。在分裂過程中,xk-split算法會根據閾值自動判斷分裂是否應該結束,從而達到了自動確定聚類數量的目的。

F2-k-means算法是對k-means算法的一種改進,其缺點是需要確定閾值。本文采用F2-K-means和k-medoids算法相結合的F2-k-medoid算法作為迭代的基本單元。由于一次迭代僅將源數據集分為兩個子集群,則F2-k-medoid算法并不需要接受閾值,而是將源數據的點全部劃分完畢,然后根據k-medoids的思想,在集群內選取距離所有點最近的點作為中心點,再進行下一步迭代直至聚類結果不再改變。

2.2 算法設計

xk-split算法結構如圖2所示。算法步驟如下:

步驟1 為了盡可能減少受隨機選取初始點的影響,對數據集執行一次k=2的k-medoids算法,將數據集分為兩個較大的待分裂集群。當k=2時,k-medoids算法受隨機選點的影響最小,往往執行多次能獲得較為接近的結果。除了待分裂集群集合S之外,還存在一個分裂完畢集群集合Sdone,在這一階段該集合仍是空集合。

步驟2 開始迭代。根據式(1)將方差最大的集群選出并從點集中剝離,待執行分裂操作。

Csplit=S[max(D(C1),D(C2),…,D(Ck)))]

(1)

(2)

其中:S表示當前集群的集合;Cx表示現有的某個集群;Csplit為待分裂的集群;n和k分別為集群和數據集中數據點的數量;D(x)為方差,由式(2)求得;Pi為集群中的某個數據點;Pcenter為集群當前的中心點;d(X1,X2)為求取兩點間歐氏距離。

由于k-medoids是按照某點離集群內其他點歐氏距離大小來選取中心點,對集群中任意點Pi來說,d(Pi,Pcenter)2為已知值,為了便于聚類以及方差計算,本文中所有k-medoids的點之間距離計算都取距離的平方值,即不對距離做開平方根處理,所以計算各集群方差并不會帶來額外的計算量。

步驟3 對步驟(2)中剝離出來的集群進行k=2的F2-k-medoids算法。完成操作后獲得兩個新集群。將這兩個新集群的規模與規模閾值θ和方差閾值γ進行判斷。θ和γ由式(3)、式(4)確定

θ= (N/K)α

(3)

(4)

式(3)中:N為整個數據集的規模;K為最終期望獲得的集群數量;α為控制參數,范圍為[0,1]。

式(4)中,D(C1)和D(C2)分別為由步驟2獲得的初始集群方差,β為控制參數。需要注意的是,當β=2時,γ為初始集群方差的平均值,該值應為γ的上界。此時按照下文確定的劃分規則,該數據集只能被分為約3個集群。為了使β的范圍控制在(0,1),進行如下變換:

(5)

式(5)即為最終閾值γ與參數β的對應關系。根據判斷的結果,這兩個新的數據集可能會被插入回S中,插入到Sdone或者被作為噪聲集群從數據集中刪除。

步驟4 重復上述步驟2、步驟3,直到集合S為空集為止。集合Sdone即為求解的聚類結果。

圖2 xk-split算法結構Fig.2 Structure of xk-split algorithm

2.3 xk-split算法的參數確定

2.3.1 接受參數k的xk-split算法 xk-split算法需要2個參數來輔助確定最終聚類結果中集群數量k。如果集群的k已知,則可以省去方差閾值γ的判斷,只需要使用規模閾值θ控制噪聲點的過濾即可,從而形成了接受參數k的xk-split算法。由于不需要自動確定集群數k,算法的復雜度大大簡化,并減少了一個閾值的學習成本,算法的閾值θ由式(3)確定。

隨后根據閾值進行判斷,對于規模小于閾值的集群,直接將其判斷為噪聲點集并拋棄;規模大于閾值的集群會被重新添加到數據集中。如果拋棄了噪聲點集,意味著這些數據永遠地從數據集中被刪除,所以需要用新的N來重新計算閾值θ。同時,將過多的數據點判斷為噪聲點會導致算法無法進行,需要重新調整參數α的值。

隨著α的上升,數據集中被排除的噪聲點增加,而平均方差下降。α越大所獲得的聚類效果越好,但是當α>0.4時,由于不斷地進行降噪和拋棄而使算法無法結束。α的最優值可能由于數據分布和噪聲點數量不同而不盡相同,具體使用時可以先從數據集中抽取一定的訓練集來確定α的值。α取值過小對聚類的完成并沒有影響,只會降低聚類的最終效果使其不理想,而過高的α值會使聚類操作無法繼續進行。所以本文算法在聚類結束之前檢測到現存的數據點數量不足原來的一半時會強制將α值設為0,以完成聚類。α從0.4上升到0.5的過程中,算法刪除的噪聲點數量急劇上升而平均方差急劇下降,即存在突躍變化。本文將α設為突躍變化發生前的最大值0.4。

2.3.2 閾值θ,γ和參數α,β的確定

(1)θ與α的確定。xk-split算法中,系統并不知道最終會有多少個聚類產生,θ的初始值由第1次分裂后2個集群的規模決定。

θ=αN/(Ndone+Nsplit)

(6)

式中:Ndone和Nsplit分別是分裂完畢集合Sdone和待分類集合S的集群數。Ndone+Nsplit為當前集群總數。一般來說該值比最終聚類結果的集群數k要小,所以α應比接受參數k的算法α小,才能保持對臟數據相同的寬容度。本文將前者的α取為后者的一半,即0.2,而后者的值可通過機器學習算得。

(2)γ與β的確定。xk-split能夠在不給定集群數k的情況下完成聚類算法,主要是由于算法中包含了方差閾值γ。其基礎值由第1次分類完成后所得的2個集群平均方差決定,這個值一定程度上反映了整個數據集中數據的分布狀態,然后通過一個(0,1)的參數β來最終確定γ。β越接近1,則γ越接近上限,對閾值的判斷就越為寬松,最終所獲得的集群數就越少。

β的取值與最終集群個數呈負相關而與集群的平均方差呈正相關。一個較小的β會將原數據集分為較多的集群,每個集群的規模和方差也相對較小,由于參數α采用了保護機制,在數據點過少的情況下不再過濾噪聲點,所以一個較小的β也不會使算法沒有足夠的數據點而終止,所以β的取值在(0,1)內都是安全的,β取值越小,算法聚類的精度越高。本文中β的取值為0.3,剛好能保證α不進入保護措施的值。

使用閾值γ進行判斷后,被判斷的集群可能會有以下3種處理方法:

(1) 繼續。集群被判斷為未達到要求,被添加回數據集,需要繼續進行分裂操作。

(2) 完成。集群已經達到要求,將該子集群標記為分裂完成,并終止對該子集群的分裂。

(3) 刪除。集群被判斷為噪聲集,從數據集中刪除。

表1列出了xk-split算法閾值行為的判斷結果。表中L(Ci)為集群Ci的規模,L(Ci)小于閾值θ時,無論方差閾值判斷結果如何,該集群都被判定為噪音數據被刪除,而滿足規模判斷的情況下,一旦集群方差D(Ci)小于閾值γ,則判定為滿足條件,結束該集群的分裂,否則將繼續進行分裂。

表1 xk-split算法閾值行為判斷

α和β都確定后就可以運行xk-split算法了。針對同一數據集連續進行100次實驗,結果表明xk-split算法的穩定度較高,能將數據集穩定地分為均值的±1個集群,其中87次結果為7個集群,8次結果為6個集群,剩余5次實驗結果為8個集群。其主要原因就是使用了F2-k-medoids和兩個閾值來控制噪聲點的排除,使聚類的結果最大程度穩定,隨機性僅僅來源于第1次分裂操作。

2.4 算法實現與分析

xk-split算法偽代碼如下:

function xk-split (dataSet){

resultClusters ← new Array

θ← (dataSet.length/k) *α

currentClusters ← k-mediods(dataSet):k=2

γ← currentClusters.averageVariance *β

while (currentClusters.length > 0){

splitCluster ← cluster with max

variance in currentClusters

currentClusters.remove(splitCluster)

splitedClusters ←

f2-k-mediods(splitCluster):k=2

for(cluster insplitedClusters){

if(cluster.length <θ){

continue

else if(cluster.variance <γ)

resultClusters.push(cluster)

else

currentClusters.push(cluster)

refreshθ

returnresultClusters

xk-split算法的特征是并不在一開始就確定k個中心,而是通過不斷地將方差最大的集群分裂以獲得目標集群。由于每次分裂都使用k=2的F2-k-medoids算法,所以相較于直接多次執行k-medoids來說穩定性高。

若輸入數據規模為N,目標集群數為k,迭代次數為T,則k-medoids和k-means的時間復雜度為O(NkT),空間復雜度為O(n+k)。對于xk-split而言,若每次分裂平均需要迭代t次,參與分裂的數據點數為k,則時間復雜度為O(ktK)。分裂操作是在單個簇中進行的,而平均每個簇含有N/K個數據點,所以k可以用N/K來表示,時間復雜度變為O(Nt)。對單一簇進行分裂迭代僅將其分為兩個子集群,其迭代次數t遠小于將整個數據集劃分為k個子集群的迭代次數T,即t<

3 實驗與分析

3.1 實驗設計

在一組基于位置信息的數據集上進行實驗分析,該數據集共含有700個數據點,每個數據點包含2個屬性,分別是經度和緯度。數據采集程序使用Cordova和Ionic框架,基于Angular.js 編寫,運行于iPhone6(iOS 9.3.5)上。位置信息采集使用了HTML5提供的geolocation接口,并調用了移動設備的GPS。所采集到的數據上傳至托管于Amazon EC2中的MongoDB中等待分析。算法程序使用Node.js編寫,并運行于2.4 GHz Core i5-4258U 的OS X 10.11.6上。

將傳統k-medoids算法與xk-split算法進行對比,比較其完成聚類算法的時間(ms)和聚類效果(集群平均方差)。對于k-medoids,將目標集群數k設為7(xk-split聚類的結果),并將重復次數設為7,取方差最小的一次進行對比,對于xk-split,將參數α設為0.2,將參數β設為0.3。

3.2 實驗結果與分析

3.2.1 平均方差分布 圖3示出了xk-split算法與k-medoids算法聚類結果的平均方差比較結果。可以看出,xk-split的平均方差比k-medoids下降了50%左右,這是由于噪聲數據剔除機制、規模閾值θ的存在。實驗數據為真實采集的位置數據,除了每天長時間停留的位置會形成數據集群之外,移動中所產生的數據基本為臟數據,這會對k-medoids的聚類效果產生很大的影響,如果采用k-means算法,其聚類效果可能會更差。這也說明xk-split算法相較于傳統的k-medoids與k-means算法,對噪聲數據的寬容度更高,不易受其影響。

圖3 兩種算法的平均方差對比Fig.3 Comparison of average variance of two algorithms

另外,k-medoids算法由于受到隨機選擇起始點的影響,方差分布范圍較大,單次執行的話穩定性很差,需要多次運算取其方差最小的結果。從實驗結果可知,k-medoids算法方差小于0.006的概率約為30%。要使得n次迭代后結果Sk-medoids中包含集群集合Sx,其平均方差D(Sx)落在(0,0.006)區內的概率大于等于90%,即滿足式(7)。

P(D(Sx)∈(0,0.006])≥90%,Sx∈Sk-medoids

(7)

需要使n滿足(1-0.3)n≤1-0.9求得

n≥6.456,所以取n=7,在接下來的實驗中,均對k-medoids算法迭代7次并取方差最小的結果為聚類結果。

3.2.2 算法時間效率

(1) 固定樣本點數。圖4示出了固定700個數據點時,兩種算法的耗時比較結果。由圖可知,xk-split算法的耗時比k-medoids少約40%,而k-medoids算法由于起始點是隨機選取的,聚類結果較不穩定,耗時分布也較其他兩個算法稍大。在該實驗過程中,k-medoids算法實際的迭代次數固定為7次,而xk-split算法實際的迭代次數為8～11次,但時間復雜度卻較低。這主要是因為每次迭代的數據集僅是原數據集的一小部分,且中心點為2個,隨著迭代的進行,數據規模也會越來越小。另一方面,k-medoids算法在每次迭代的過程中都對整個數據集進行k個中心點的聚類,所以時間復雜度會大大上升。

圖4 兩種算法樣本數量不變時效率對比Fig. Comparison of efficiency of two algorithms

(2) 變化樣本點數量。圖5示出了數據集規模從100到700變化時,各個算法的時間復雜度變化曲線。由圖5可知,在數據規模較小的情況下,xk-split與k-medoids算法的時間復雜度接近,但是隨著數據規模的增大,兩者運算的耗時逐漸拉開了差距。這也體現出了運用分裂策略的xk-split算法在應對大規模數據時的優越性。

圖5 兩種算法樣本數量變化時效率對比Fig.5 Comparison of efficiency of two algorithms for sample number change

4 結束語

本文在k-medoids和F2-k-means算法的基礎上提出了xk-split聚類算法。該算法以k=2的k-medoids算法作為基礎的迭代單位,并運用分裂策略,有效地解決了數據聚類的問題。

(1) xk-split算法采用參數α和β指導的學習策略,在不指定k個起始點的情況下也能自動對數據集進行聚類。

(2) 本文的兩個算法都包含噪音數據過濾階段,能將游離于集群外的點過濾掉,對臟數據的耐受力有明顯提升。

(3) 由于基礎的運算單元是k=2的F2-k-medoids算法和分裂操作,而不是對全體數據集進行隨機取點,本文算法擁有更高的穩定性,受隨機數的影響較小。

此外,由于采取了分裂的策略,xk-split算法的時間復雜度較k-medoids迭代有明顯的下降,更適合于真實數據的分析與聚類。不過,本文算法仍存在依賴于閾值控制的不足,為確定算法所需閾值參數需要對數據進行一定的學習過程。在進一步的研究中,會將重點放在xk-split算法參數的選擇策略優化上,降低選擇和學習成本,并提出高效且穩定的聚類算法。

[1] KHATAMI A,MIRGHASEMI S,KHOSRAVI A,etal.A new color space based on k-medoids clustering for fire detection[C]//2015 IEEE International Conference on Systems,Man,and Cybernetics (SMC).USA:IEEE,2015:2755-2760.

[2] YABUUCHI Y,HUNG H,WATADA J.Summarizing approach for efficient search by k-medoids method[C]// 2015 10th Asian Control Conference (ASCC).USA:IEEE,2015:1-6.

[3] ZHANG T,XIA Y,ZHU Q,etal.Mining related information of traffic flows on lanes by k-medoids[C]//2014 11th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD).USA:IEEE,2014:390-396.

[4] PURWITASARI D,FATICHAH C,ARIESHANTI I,etal.K-medoids algorithm on Indonesian Twitter feeds for clustering trending issue as important terms in news summarization[C]//2015 International Conference on Information & Communication Technology and Systems (ICTS).USA:IEEE,2015:95-98.

[5] NATH S,MARCHANG N,TAGGU A.Mitigating SSDF attack using k-medoids clustering in cognitive radio networks[C]//2015 IEEE 11th International Conference on Wireless and Mobile Computing,Networking and Communications (WiMob).USA:IEEE,2015:275-282.

[6] HARTIGAN J A,WONG M A.Algorithm AS 136:A k-means clustering algorithm[J].Journal of the Royal Statistical Society,Series C (Applied Statistics),1979,28(1):100-108.

[7] SHEN J J,LEE C F,HOU K L.Improved productivity of mosaic image by k-medoids and feature selection mechanism on hadoop-based framework[C]// 2016 International Conference on Networking and Network Applications.Hokkaido,Japan:IEEE,2016:288-293.

[8] HU Q,WANG G,PHILIP S Y.Public information sharing behaviors analysis over different social media[C]//2015 IEEE Conference on Collaboration and Internet Computing (CIC).USA:IEEE,2015:62-69.

[9] SHI G,GAO B,ZHANG L.The optimized k-means algorithms for improving randomly-initialed midpoints[C]// 2013 International Conference on Measurement,Information and Control (ICMIC).USA:IEEE,2013:1212-1216.

[10] XU Y,CHEN C.An improved K-means clustering algorithm[J].Computer Applications and Software,2005,25(3):275-277.

[11] ZHOU H.Adaptive K-means clustering algorithm SA-K-means[J].Science and Technology Innovation Herald,2009,N034:4-8.

[12] CUI X,WANG F.An Improved method for k-means clustering[C]//2015 International Conference on Computational Intelligence and Communication Networks (CICN).USA:IEEE,2015:756-759.

xk-split:ASplitClusteringAlgorithmBasesonk-medoids

CHENYi-fei1,2,YUHui-qun1

(1.DepartmentofComputerScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China; 2.ShanghaiKeyLaboratoryofComputerSoftwareEvaluationandTesting,Shanghai201112,China)

In recent years,the scale of internet data has explosive growth,which makes big data analysis become a hot topic.However,it is difficult to directly utilize the collected data,so a certain degree of pretreatment had to be made in order to improve the quality of big data.In this work,the data set will be gradually divided into smaller subsets by using the split iterative process,which can effectively avoid the limitation of traditional clustering algorithm and reduce the time complexity.In addition,by threshold-based noise data filtering,the dirty data can be eliminated during the iterative process so as to enhance the tolerance of the clustering algorithm to the dirty data.

data mining; clustering; k-means; k-medoids;split

1006-3080(2017)06-0849-06

10.14135/j.cnki.1006-3080.2017.06.015

2016-11-23

陳逸斐(1991-),男,碩士生,主要研究方向為云計算。

虞慧群,E-mail:yhq@ecust.edu.cn

TP391

A