陳逸斐, 虞慧群

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

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

陳逸斐1,2, 虞慧群1

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 k-means算法

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

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

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

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

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

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

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

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

1.2 k-medoids算法

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

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

1.3 其他改進的k-means算法

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

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

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

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

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

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

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

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

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

2.1 xk-split算法的迭代單元

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

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

2.2 算法設計

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

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

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

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

(1)

(2)

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

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

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

θ= (N/K)α

(3)

(4)

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

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

(5)

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

步驟4 重復上述步驟2、步驟3,直到集合S為空集為止。集合Sdone即為求解的聚類結(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個參數(shù)來輔助確定最終聚類結(jié)果中集群數(shù)量k。如果集群的k已知,則可以省去方差閾值γ的判斷,只需要使用規(guī)模閾值θ控制噪聲點的過濾即可,從而形成了接受參數(shù)k的xk-split算法。由于不需要自動確定集群數(shù)k,算法的復雜度大大簡化,并減少了一個閾值的學習成本,算法的閾值θ由式(3)確定。

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

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

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

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

θ=αN/(Ndone+Nsplit)

(6)

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

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

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

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

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

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

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

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

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

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

2.4 算法實現(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個中心,而是通過不斷地將方差最大的集群分裂以獲得目標集群。由于每次分裂都使用k=2的F2-k-medoids算法,所以相較于直接多次執(zhí)行k-medoids來說穩(wěn)定性高。

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

3 實驗與分析

3.1 實驗設計

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

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

3.2 實驗結(jié)果與分析

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

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

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

3.2.2 算法時間效率

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

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

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

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

4 結(jié)束語

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

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

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

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

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

[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