陳逸斐, 虞慧群

(1.華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系,上海 200237; 2.上海市計(jì)算機(jī)軟件重點(diǎn)測(cè)評(píng)實(shí)驗(yàn)室,上海 201112)

xk-split:基于k-medoids的分裂式聚類(lèi)算法

陳逸斐1,2, 虞慧群1

(1.華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系,上海 200237; 2.上海市計(jì)算機(jī)軟件重點(diǎn)測(cè)評(píng)實(shí)驗(yàn)室,上海 201112)

近年來(lái)互聯(lián)網(wǎng)數(shù)據(jù)規(guī)模呈爆炸式增長(zhǎng),如何對(duì)大數(shù)據(jù)進(jìn)行分析已成為熱門(mén)話題。然而,采集的數(shù)據(jù)很難直接用于分析,需要進(jìn)行一定程度的預(yù)處理,以提高大數(shù)據(jù)質(zhì)量。通過(guò)使用分裂式的迭代過(guò)程,可以逐步將數(shù)據(jù)集分裂為子集,避免了傳統(tǒng)聚類(lèi)算法聚類(lèi)開(kāi)始時(shí)需要確定集群數(shù)的限制,并降低了算法的時(shí)間復(fù)雜度。此外,通過(guò)基于閾值的噪聲數(shù)據(jù)過(guò)濾,可以在迭代過(guò)程中剔除噪音數(shù)據(jù),提升了聚類(lèi)算法對(duì)臟數(shù)據(jù)的忍耐力。

數(shù)據(jù)挖掘; 聚類(lèi); k-means; k-medoids; 分裂

數(shù)據(jù)的聚類(lèi)算法是機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘中的一大命題,廣泛應(yīng)用于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、圖像分析、模式識(shí)別等領(lǐng)域中。而聚類(lèi)算法又可分為硬聚類(lèi)和軟聚類(lèi)算法,其中硬聚類(lèi)算法將目標(biāo)數(shù)據(jù)明確地劃分為不同集群,代表算法為k-means算法;而軟聚類(lèi)算法又稱(chēng)模糊聚類(lèi)算法,數(shù)據(jù)點(diǎn)可能屬于一個(gè)或以上的集群,且數(shù)據(jù)點(diǎn)與集群通過(guò)成員水平互相聯(lián)系,代表算法為模糊C-均值(FCM)算法。本文針對(duì)聚類(lèi)算法中的硬聚類(lèi)算法展開(kāi)討論。

聚類(lèi)分析的主要工作是將較大規(guī)模的數(shù)據(jù)通過(guò)靜態(tài)分析的手段劃分為更小的子集,每個(gè)子集內(nèi)部的對(duì)象有共同的特征。聚類(lèi)分析的手段主要分為結(jié)構(gòu)型與分散型算法。結(jié)構(gòu)型算法需要使用已經(jīng)存在的聚類(lèi)器進(jìn)行數(shù)據(jù)分析,而應(yīng)用較為廣泛的是分散型聚類(lèi)算法,其特征是一次性確定所有分類(lèi),而且需要指定聚類(lèi)結(jié)果的個(gè)數(shù),不明確聚類(lèi)個(gè)數(shù)的情況下需要給出估計(jì)值。

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

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

1 相關(guān)工作

1.1 k-means算法

最簡(jiǎn)單也是應(yīng)用最為廣泛的分散型數(shù)據(jù)聚類(lèi)算法是由MacQueen提出的無(wú)監(jiān)督聚類(lèi)算法k-means[6]。k-means的主要實(shí)現(xiàn)方法是在數(shù)據(jù)集中隨機(jī)選取k個(gè)中心點(diǎn),隨后循環(huán)迭代2個(gè)步驟:

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

(2) 重新選擇中心點(diǎn)。計(jì)算各個(gè)集群的質(zhì)心,將其作為新的中心點(diǎn)。

對(duì)整個(gè)數(shù)據(jù)集不斷地重復(fù)執(zhí)行以上步驟,直至集群分布不再改變。

k-means算法以較低的時(shí)間成本解決了數(shù)據(jù)無(wú)監(jiān)督集群?jiǎn)栴},但是存在很多問(wèn)題:

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

(2) 在選擇中心點(diǎn)的步驟中使用質(zhì)心作為新的中心,對(duì)臟數(shù)據(jù)較為敏感。

(3) 其本質(zhì)是一種貪心算法,僅僅能求得局部最優(yōu)解。加之起始點(diǎn)是隨機(jī)選取的,往往為了獲得一個(gè)較為優(yōu)秀的解,需要重復(fù)執(zhí)行多次k-means算法。

1.2 k-medoids算法

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

現(xiàn)實(shí)生活中已對(duì)k-medoids有了非常廣泛的應(yīng)用。由于其隨機(jī)性,需要迭代多次以獲得最優(yōu)解,這個(gè)過(guò)程具有并行的特性,所以非常適合用戶(hù)Hadoop等平臺(tái)的大數(shù)據(jù)分析[7]。同時(shí)因?yàn)槠漭^為優(yōu)秀的臟數(shù)據(jù)耐受能力,也經(jīng)常被用于用戶(hù)行為分析等工作上[8]。

1.3 其他改進(jìn)的k-means算法

其他針對(duì)k-means的改進(jìn)算法也經(jīng)常被提出[9]。Xu等[10]提出了F2-k-means (Farest2-k-means)算法,該算法先找出數(shù)據(jù)集中距離最遠(yuǎn)的兩個(gè)點(diǎn),分別形成集群,在數(shù)據(jù)集中尋找接近集群的點(diǎn)并加入其中,直至到達(dá)閾值,再尋找新的點(diǎn)。這兩個(gè)算法有一個(gè)共同的特點(diǎn),就是依賴(lài)閾值來(lái)判斷是否結(jié)束迭代,同時(shí),最接近點(diǎn)對(duì)的比較也會(huì)大幅增加算法的時(shí)間復(fù)雜度,集群算法的準(zhǔn)確度也依賴(lài)于閾值的選擇,如圖1所示,選擇閾值為10時(shí),會(huì)導(dǎo)致源數(shù)據(jù)被過(guò)度分類(lèi)。

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

Zhou等[11]提出的自適應(yīng)k-means算法可以使k-means擁有一定的學(xué)習(xí)能力,用較少的代價(jià)增加算法對(duì)臟數(shù)據(jù)的耐受能力,不過(guò)也較依賴(lài)于數(shù)據(jù)的規(guī)模,僅僅在有充足的數(shù)據(jù)進(jìn)行訓(xùn)練的前提下才會(huì)有較好的輸出。Cui等[12]提出了一種k-means的優(yōu)化方案,在尋找中心點(diǎn)的過(guò)程中同時(shí)考慮集群內(nèi)的凝聚度和集群間的分離度,以解決k-means算法僅僅能求得局部最優(yōu)解的問(wèn)題,但這個(gè)方法同樣大大增加了算法的時(shí)間復(fù)雜度。

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

(1) 可以選擇指定或不指定k個(gè)初始點(diǎn),在集群的過(guò)程中判斷出數(shù)據(jù)最佳的集群數(shù)量。

(2) 比k-medoids更穩(wěn)定,受隨機(jī)選點(diǎn)的影響更小。

(3) 對(duì)臟數(shù)據(jù)不敏感,并且可以在集群過(guò)程中識(shí)別并排除噪聲數(shù)據(jù)。

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

2 分裂式自適應(yīng)聚類(lèi)算法xk-split

2.1 xk-split算法的迭代單元

xk-split算法不同于k-means和k-medoids算法,迭代開(kāi)始時(shí)并不會(huì)確定k個(gè)初始集群,而是先確定2個(gè)集群,然后再將其逐步分裂成k個(gè)小集群。在分裂過(guò)程中,xk-split算法會(huì)根據(jù)閾值自動(dòng)判斷分裂是否應(yīng)該結(jié)束,從而達(dá)到了自動(dòng)確定聚類(lèi)數(shù)量的目的。

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

2.2 算法設(shè)計(jì)

xk-split算法結(jié)構(gòu)如圖2所示。算法步驟如下:

步驟1 為了盡可能減少受隨機(jī)選取初始點(diǎn)的影響,對(duì)數(shù)據(jù)集執(zhí)行一次k=2的k-medoids算法,將數(shù)據(jù)集分為兩個(gè)較大的待分裂集群。當(dāng)k=2時(shí),k-medoids算法受隨機(jī)選點(diǎn)的影響最小,往往執(zhí)行多次能獲得較為接近的結(jié)果。除了待分裂集群集合S之外,還存在一個(gè)分裂完畢集群集合Sdone,在這一階段該集合仍是空集合。

步驟2 開(kāi)始迭代。根據(jù)式(1)將方差最大的集群選出并從點(diǎn)集中剝離,待執(zhí)行分裂操作。

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

(1)

(2)

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

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

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

θ= (N/K)α

(3)

(4)

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

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

(5)

式(5)即為最終閾值γ與參數(shù)β的對(duì)應(yīng)關(guān)系。根據(jù)判斷的結(jié)果,這兩個(gè)新的數(shù)據(jù)集可能會(huì)被插入回S中,插入到Sdone或者被作為噪聲集群從數(shù)據(jù)集中刪除。

步驟4 重復(fù)上述步驟2、步驟3,直到集合S為空集為止。集合Sdone即為求解的聚類(lèi)結(jié)果。

圖2 xk-split算法結(jié)構(gòu)Fig.2 Structure of xk-split algorithm

2.3 xk-split算法的參數(shù)確定

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

隨后根據(jù)閾值進(jìn)行判斷,對(duì)于規(guī)模小于閾值的集群,直接將其判斷為噪聲點(diǎn)集并拋棄;規(guī)模大于閾值的集群會(huì)被重新添加到數(shù)據(jù)集中。如果拋棄了噪聲點(diǎn)集,意味著這些數(shù)據(jù)永遠(yuǎn)地從數(shù)據(jù)集中被刪除,所以需要用新的N來(lái)重新計(jì)算閾值θ。同時(shí),將過(guò)多的數(shù)據(jù)點(diǎn)判斷為噪聲點(diǎn)會(huì)導(dǎo)致算法無(wú)法進(jìn)行,需要重新調(diào)整參數(shù)α的值。

隨著α的上升,數(shù)據(jù)集中被排除的噪聲點(diǎn)增加,而平均方差下降。α越大所獲得的聚類(lèi)效果越好,但是當(dāng)α>0.4時(shí),由于不斷地進(jìn)行降噪和拋棄而使算法無(wú)法結(jié)束。α的最優(yōu)值可能由于數(shù)據(jù)分布和噪聲點(diǎn)數(shù)量不同而不盡相同,具體使用時(shí)可以先從數(shù)據(jù)集中抽取一定的訓(xùn)練集來(lái)確定α的值。α取值過(guò)小對(duì)聚類(lèi)的完成并沒(méi)有影響,只會(huì)降低聚類(lèi)的最終效果使其不理想,而過(guò)高的α值會(huì)使聚類(lèi)操作無(wú)法繼續(xù)進(jìn)行。所以本文算法在聚類(lèi)結(jié)束之前檢測(cè)到現(xiàn)存的數(shù)據(jù)點(diǎn)數(shù)量不足原來(lái)的一半時(shí)會(huì)強(qiáng)制將α值設(shè)為0,以完成聚類(lèi)。α從0.4上升到0.5的過(guò)程中,算法刪除的噪聲點(diǎn)數(shù)量急劇上升而平均方差急劇下降,即存在突躍變化。本文將α設(shè)為突躍變化發(fā)生前的最大值0.4。

2.3.2 閾值θ,γ和參數(shù)α,β的確定

(1)θ與α的確定。xk-split算法中,系統(tǒng)并不知道最終會(huì)有多少個(gè)聚類(lèi)產(chǎn)生,θ的初始值由第1次分裂后2個(gè)集群的規(guī)模決定。

θ=αN/(Ndone+Nsplit)

(6)

式中:Ndone和Nsplit分別是分裂完畢集合Sdone和待分類(lèi)集合S的集群數(shù)。Ndone+Nsplit為當(dāng)前集群總數(shù)。一般來(lái)說(shuō)該值比最終聚類(lèi)結(jié)果的集群數(shù)k要小,所以α應(yīng)比接受參數(shù)k的算法α小,才能保持對(duì)臟數(shù)據(jù)相同的寬容度。本文將前者的α取為后者的一半,即0.2,而后者的值可通過(guò)機(jī)器學(xué)習(xí)算得。

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

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

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

(1) 繼續(xù)。集群被判斷為未達(dá)到要求,被添加回?cái)?shù)據(jù)集,需要繼續(xù)進(jìn)行分裂操作。

(2) 完成。集群已經(jīng)達(dá)到要求,將該子集群標(biāo)記為分裂完成,并終止對(duì)該子集群的分裂。

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

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

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

α和β都確定后就可以運(yùn)行xk-split算法了。針對(duì)同一數(shù)據(jù)集連續(xù)進(jìn)行100次實(shí)驗(yàn),結(jié)果表明xk-split算法的穩(wěn)定度較高,能將數(shù)據(jù)集穩(wěn)定地分為均值的±1個(gè)集群,其中87次結(jié)果為7個(gè)集群,8次結(jié)果為6個(gè)集群,剩余5次實(shí)驗(yàn)結(jié)果為8個(gè)集群。其主要原因就是使用了F2-k-medoids和兩個(gè)閾值來(lái)控制噪聲點(diǎn)的排除,使聚類(lèi)的結(jié)果最大程度穩(wěn)定,隨機(jī)性?xún)H僅來(lái)源于第1次分裂操作。

2.4 算法實(shí)現(xiàn)與分析

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āi)始就確定k個(gè)中心,而是通過(guò)不斷地將方差最大的集群分裂以獲得目標(biāo)集群。由于每次分裂都使用k=2的F2-k-medoids算法,所以相較于直接多次執(zhí)行k-medoids來(lái)說(shuō)穩(wěn)定性高。

若輸入數(shù)據(jù)規(guī)模為N,目標(biāo)集群數(shù)為k,迭代次數(shù)為T(mén),則k-medoids和k-means的時(shí)間復(fù)雜度為O(NkT),空間復(fù)雜度為O(n+k)。對(duì)于xk-split而言,若每次分裂平均需要迭代t次,參與分裂的數(shù)據(jù)點(diǎn)數(shù)為k,則時(shí)間復(fù)雜度為O(ktK)。分裂操作是在單個(gè)簇中進(jìn)行的,而平均每個(gè)簇含有N/K個(gè)數(shù)據(jù)點(diǎn),所以k可以用N/K來(lái)表示,時(shí)間復(fù)雜度變?yōu)镺(Nt)。對(duì)單一簇進(jìn)行分裂迭代僅將其分為兩個(gè)子集群,其迭代次數(shù)t遠(yuǎn)小于將整個(gè)數(shù)據(jù)集劃分為k個(gè)子集群的迭代次數(shù)T,即t<

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

將傳統(tǒng)k-medoids算法與xk-split算法進(jìn)行對(duì)比,比較其完成聚類(lèi)算法的時(shí)間(ms)和聚類(lèi)效果(集群平均方差)。對(duì)于k-medoids,將目標(biāo)集群數(shù)k設(shè)為7(xk-split聚類(lèi)的結(jié)果),并將重復(fù)次數(shù)設(shè)為7,取方差最小的一次進(jìn)行對(duì)比,對(duì)于xk-split,將參數(shù)α設(shè)為0.2,將參數(shù)β設(shè)為0.3。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 平均方差分布 圖3示出了xk-split算法與k-medoids算法聚類(lèi)結(jié)果的平均方差比較結(jié)果?？梢钥闯?xk-split的平均方差比k-medoids下降了50%左右,這是由于噪聲數(shù)據(jù)剔除機(jī)制、規(guī)模閾值θ的存在。實(shí)驗(yàn)數(shù)據(jù)為真實(shí)采集的位置數(shù)據(jù),除了每天長(zhǎng)時(shí)間停留的位置會(huì)形成數(shù)據(jù)集群之外,移動(dòng)中所產(chǎn)生的數(shù)據(jù)基本為臟數(shù)據(jù),這會(huì)對(duì)k-medoids的聚類(lèi)效果產(chǎn)生很大的影響,如果采用k-means算法,其聚類(lèi)效果可能會(huì)更差。這也說(shuō)明xk-split算法相較于傳統(tǒng)的k-medoids與k-means算法,對(duì)噪聲數(shù)據(jù)的寬容度更高,不易受其影響。

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

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

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

(7)

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

n≥6.456,所以取n=7,在接下來(lái)的實(shí)驗(yàn)中,均對(duì)k-medoids算法迭代7次并取方差最小的結(jié)果為聚類(lèi)結(jié)果。

3.2.2 算法時(shí)間效率

(1) 固定樣本點(diǎn)數(shù)。圖4示出了固定700個(gè)數(shù)據(jù)點(diǎn)時(shí),兩種算法的耗時(shí)比較結(jié)果。由圖可知,xk-split算法的耗時(shí)比k-medoids少約40%,而k-medoids算法由于起始點(diǎn)是隨機(jī)選取的,聚類(lèi)結(jié)果較不穩(wěn)定,耗時(shí)分布也較其他兩個(gè)算法稍大。在該實(shí)驗(yàn)過(guò)程中,k-medoids算法實(shí)際的迭代次數(shù)固定為7次,而xk-split算法實(shí)際的迭代次數(shù)為8～11次,但時(shí)間復(fù)雜度卻較低。這主要是因?yàn)槊看蔚臄?shù)據(jù)集僅是原數(shù)據(jù)集的一小部分,且中心點(diǎn)為2個(gè),隨著迭代的進(jìn)行,數(shù)據(jù)規(guī)模也會(huì)越來(lái)越小。另一方面,k-medoids算法在每次迭代的過(guò)程中都對(duì)整個(gè)數(shù)據(jù)集進(jìn)行k個(gè)中心點(diǎn)的聚類(lèi),所以時(shí)間復(fù)雜度會(huì)大大上升。

圖4 兩種算法樣本數(shù)量不變時(shí)效率對(duì)比Fig. Comparison of efficiency of two algorithms

(2) 變化樣本點(diǎn)數(shù)量。圖5示出了數(shù)據(jù)集規(guī)模從100到700變化時(shí),各個(gè)算法的時(shí)間復(fù)雜度變化曲線。由圖5可知,在數(shù)據(jù)規(guī)模較小的情況下,xk-split與k-medoids算法的時(shí)間復(fù)雜度接近,但是隨著數(shù)據(jù)規(guī)模的增大,兩者運(yùn)算的耗時(shí)逐漸拉開(kāi)了差距。這也體現(xiàn)出了運(yùn)用分裂策略的xk-split算法在應(yīng)對(duì)大規(guī)模數(shù)據(jù)時(shí)的優(yōu)越性。

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

4 結(jié)束語(yǔ)

本文在k-medoids和F2-k-means算法的基礎(chǔ)上提出了xk-split聚類(lèi)算法。該算法以k=2的k-medoids算法作為基礎(chǔ)的迭代單位,并運(yùn)用分裂策略,有效地解決了數(shù)據(jù)聚類(lèi)的問(wèn)題。

(1) xk-split算法采用參數(shù)α和β指導(dǎo)的學(xué)習(xí)策略,在不指定k個(gè)起始點(diǎn)的情況下也能自動(dòng)對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)。

(2) 本文的兩個(gè)算法都包含噪音數(shù)據(jù)過(guò)濾階段,能將游離于集群外的點(diǎn)過(guò)濾掉,對(duì)臟數(shù)據(jù)的耐受力有明顯提升。

(3) 由于基礎(chǔ)的運(yùn)算單元是k=2的F2-k-medoids算法和分裂操作,而不是對(duì)全體數(shù)據(jù)集進(jìn)行隨機(jī)取點(diǎn),本文算法擁有更高的穩(wěn)定性,受隨機(jī)數(shù)的影響較小。

此外,由于采取了分裂的策略,xk-split算法的時(shí)間復(fù)雜度較k-medoids迭代有明顯的下降,更適合于真實(shí)數(shù)據(jù)的分析與聚類(lèi)。不過(guò),本文算法仍存在依賴(lài)于閾值控制的不足,為確定算法所需閾值參數(shù)需要對(duì)數(shù)據(jù)進(jìn)行一定的學(xué)習(xí)過(guò)程。在進(jìn)一步的研究中,會(huì)將重點(diǎn)放在xk-split算法參數(shù)的選擇策略?xún)?yōu)化上,降低選擇和學(xué)習(xí)成本,并提出高效且穩(wěn)定的聚類(lèi)算法。

[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-),男,碩士生,主要研究方向?yàn)樵朴?jì)算。

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

TP391

A