王秀華

(晉中學(xué)院計(jì)算機(jī)學(xué)院，山西 晉中 030600)

0 引言

隨著計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，現(xiàn)實(shí)世界中需要處理的數(shù)據(jù)量越來(lái)越大。國(guó)際數(shù)據(jù)公司(IDC)的研究結(jié)果表明，2008年全球數(shù)據(jù)存儲(chǔ)量為0.49ZB，到2012年全球數(shù)據(jù)量達(dá)到了驚人的200PB，而到2020年全球數(shù)據(jù)存儲(chǔ)量將達(dá)到今天的44倍［1］。數(shù)據(jù)挖掘技術(shù)［2］是指從大規(guī)模的、不完整的、有噪聲的、模糊的、隨機(jī)的復(fù)雜數(shù)據(jù)集中提取潛在有用的信息或知識(shí)。

聚類是指將物理或抽象對(duì)象的集合劃分成由類似隊(duì)形組成的多個(gè)子類的過(guò)程，目前已在圖像、金融、信息安全等領(lǐng)域得到成功應(yīng)用［3-4］。目前聚類分析中常采用的模型包括:(1)劃分聚類方法［5］，即數(shù)據(jù)集根據(jù)一定的評(píng)測(cè)標(biāo)準(zhǔn)通過(guò)反復(fù)迭代劃分為不同的子類，使統(tǒng)一子類中盡可能相似，不同子類中盡可能不同，常見(jiàn)的劃分聚類方法如K-means方法、CLARANS方法等;(2)層次聚類方法［6］是對(duì)給定的數(shù)據(jù)集進(jìn)行層次結(jié)構(gòu)的分解，直到滿足聚類結(jié)果要求為止，可分為“自底向上”和“自頂向下”兩種，常見(jiàn)的如BIRCH方法、CURE方法等;(3)基于密度的聚類方法［7］根據(jù)區(qū)域中樣本點(diǎn)的密度進(jìn)行聚類，克服了其他方法只能發(fā)現(xiàn)“超球狀”類的問(wèn)題，常見(jiàn)的如DBSCAN方法、OPTICS 方法等。此外，網(wǎng)格聚類［8］、模型聚類［9］、傳遞閉包聚類［10］及譜聚類［11］等方法近年來(lái)也成為了聚類分析的研究熱點(diǎn)。

在這些聚類方法中，K-均值聚類是一種最為經(jīng)典，使用最為廣泛的劃分聚類方法［11-12］。K-均值聚類方法通過(guò)動(dòng)態(tài)地迭代調(diào)整聚類中心，根據(jù)樣本到每個(gè)子類中心的相似度進(jìn)行不斷迭代來(lái)得到聚類結(jié)果。但是，K-均值聚類方法由于需要反復(fù)地計(jì)算每個(gè)樣本到中心的相似度，算法的復(fù)雜度較高，當(dāng)樣本規(guī)模較大時(shí)無(wú)法進(jìn)行有效的處理。因此，如何采用K-均值聚類方法解決大規(guī)模數(shù)據(jù)的聚類問(wèn)題一直是聚類分析領(lǐng)域的一個(gè)研究熱點(diǎn)。

針對(duì)傳統(tǒng)K-均值聚類方法不能有效處理大規(guī)模數(shù)據(jù)聚類的問(wèn)題，本文提出一種基于隨機(jī)抽樣的加速K-均值聚類方法。Kmeans_RS方法首先從大規(guī)模的聚類數(shù)據(jù)集中進(jìn)行隨機(jī)抽樣，得到規(guī)模較小的工作集，并在工作集上進(jìn)行傳統(tǒng)K-均值聚類，得到聚類中心和半徑，完成抽樣過(guò)程，得到抽樣結(jié)果。然后通過(guò)衡量剩下的聚類樣本與已經(jīng)得到的抽樣結(jié)果的關(guān)系，對(duì)剩余樣本進(jìn)行歸類。由于該方法通過(guò)隨機(jī)抽樣大大地減小了參與K-均值聚類的問(wèn)題規(guī)模，有效提高了聚類效率;同時(shí)該方法避免了傳統(tǒng)K-均值聚類方法提前需要指定聚類個(gè)數(shù)參數(shù)的困難，可以自適應(yīng)地增加聚類個(gè)數(shù)。

1 基于隨機(jī)抽樣的加速K-均值聚類算法

設(shè)數(shù)據(jù)集 X={x1，…，xi，…xn}，且 xi∈Rd，其中n為樣本個(gè)數(shù)，d為樣本維度，k為聚類之前指定的聚類個(gè)數(shù)。傳統(tǒng)K-均值聚類算法首先隨機(jī)選擇k個(gè)樣本作為初始聚類中心 C={c1，…，cj，…，ck}，然后計(jì)算每個(gè)樣本xi∈X到聚類中心cj∈C的距離d(xi，cj)，根據(jù)每個(gè)樣本到聚類中心的距離將樣本劃分到與之最近類中，并計(jì)算更新后每個(gè)類的中心C，如此循環(huán)迭代直到更新后的類中心與更新前一致時(shí)停止。

本文算法結(jié)合隨機(jī)抽樣方法，首先通過(guò)隨機(jī)抽樣方法從樣本集X中抽取一個(gè)規(guī)模較小的工作集X'，假設(shè)，其中s為隨機(jī)抽樣參數(shù)。然后在工作集X'上進(jìn)行傳統(tǒng)K-均值聚類，得到聚類結(jié)果 X'→{X1'，…，Xp'，…，Xk'}，并對(duì)于每個(gè)聚類后得到的類Xp'，求解其類中心cp'和類半徑rp'，得到采樣結(jié)果。其次通過(guò)衡量剩余的聚類樣本與已得到的類的相似度，并設(shè)定聚類閾值，將相似度最高并在閾值γ內(nèi)的合并為一個(gè)類，類中心(兩個(gè)不同樣本)相似度的公式如下:

樣本xq所屬類別的確定公式如下:

即若剩余樣本到最相似的類中心的相似度大于閾值，則將其標(biāo)記為與其最相似的類別，反之，過(guò)剩余樣本到聚類中心的聚類小于或等于閾值，則擴(kuò)充一個(gè)新的類別，并將其并入聚類結(jié)果。基于隨機(jī)抽樣的加速K-均值聚類算法如下:

算法1 基于抽樣的加速K-均值聚類方法

初始化:設(shè)數(shù)據(jù)集為 X={x1，…，xi，…xn}(其中xi∈Rd)，隨機(jī)抽樣參數(shù)為s，聚類參數(shù)為k，閾值參數(shù)為γ。

Step1 采樣過(guò)程:

Step1.1 從樣本集X隨機(jī)抽取n/s個(gè)樣本構(gòu)成工作集X';

Step1.2 從工作集X'中隨機(jī)選擇k個(gè)樣本作為初始聚類中心 C'={c1'，…，cp'，…，ck'};

Step1.3 根據(jù)式(1)計(jì)算每個(gè)樣本xi'與所有不同聚類中心cp'之間的相似度，并將xi'歸為與其最相似的類中心所屬的類;

Step1.4 根據(jù)式(3)計(jì)算樣本重新分配后的每個(gè)類的聚類中心，其中np為第p個(gè)類Xp'中樣本的個(gè)數(shù);

Step1.5 若類中心有更新，則返回Step1.2繼續(xù)聚類，直到類中心不發(fā)生更新時(shí)迭代停止，得到工作集 X'的聚類結(jié)果 X'→{X1'，…，Xp'，…，Xk'};

Step1.6 得到采樣結(jié)果 C={c1'，…，cp'，…，ck'};

Step2 根據(jù)式(4)計(jì)算聚類結(jié)果中每個(gè)類的半徑;

Step3 根據(jù)采樣結(jié)果及式(1)計(jì)算剩余樣本集X/X'中任意一個(gè)樣本xq與已得到的采樣結(jié)果的相似度，并根據(jù)式(2)進(jìn)行歸類;

2 實(shí)驗(yàn)結(jié)果及分析

為充分驗(yàn)證基于隨機(jī)抽樣的K-均值聚類方法的有效性，本文在構(gòu)造的人工數(shù)據(jù)集和UCI的標(biāo)準(zhǔn)數(shù)據(jù)集上都作了實(shí)驗(yàn)。本文從兩個(gè)方面衡量了算法的性能，即聚類結(jié)果的抱團(tuán)性和聚類時(shí)間。聚類抱團(tuán)性的定義如下:

實(shí)驗(yàn)中將本文提出的Kmeans_RS方法與傳統(tǒng)K-均值聚類方法進(jìn)行了對(duì)比。

首先在類社會(huì)網(wǎng)絡(luò)的人工構(gòu)造數(shù)據(jù)集［13］上進(jìn)行了實(shí)驗(yàn)。該數(shù)據(jù)集模擬網(wǎng)絡(luò)社團(tuán)機(jī)構(gòu)，實(shí)驗(yàn)分別采用規(guī)模為100和2000的兩組數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)。其中第一組數(shù)據(jù)集被劃分成相同大小的4個(gè)社團(tuán)結(jié)構(gòu)，每個(gè)包含25個(gè)頂點(diǎn)，且社團(tuán)結(jié)構(gòu)中每個(gè)頂點(diǎn)的度符合如下條件:

其中zin為每個(gè)頂點(diǎn)指向相同社團(tuán)中頂點(diǎn)的有向邊數(shù)目，zout為指向落在不同社團(tuán)中頂點(diǎn)的有向邊數(shù)目，數(shù)據(jù)集如圖1所示，第二組較大規(guī)模的數(shù)據(jù)集與第一組構(gòu)造方法一致，規(guī)模擴(kuò)大20倍。

圖1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)中隨機(jī)抽取參數(shù)s取1/5，聚類個(gè)數(shù)參數(shù)為4，閾值參數(shù)取當(dāng)前已經(jīng)得到的最大類半徑的1.2倍，所得實(shí)驗(yàn)結(jié)果見(jiàn)表1。

表1 Kmeans_RS與K-means實(shí)驗(yàn)結(jié)果對(duì)比

從以上實(shí)驗(yàn)結(jié)果可以看出，在人工構(gòu)造模擬的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)數(shù)據(jù)集上，當(dāng)樣本規(guī)模為100時(shí)，本文提出的基于隨機(jī)采樣的K-均值聚類方法的J值較高，樣本的抱團(tuán)性較差，聚類效率與傳統(tǒng)K-均值聚類方法有一些提高;但是，當(dāng)樣本規(guī)模增加到2000時(shí)，本文提出的基于隨機(jī)采樣的K-均值聚類方法的J值接近于傳統(tǒng)K-均值聚類方法，而聚類的時(shí)間則只有傳統(tǒng)K-均值聚類方法的35%左右。

此外，本文還在4個(gè)標(biāo)準(zhǔn)的UCI數(shù)據(jù)集［14］上進(jìn)行了實(shí)驗(yàn)，數(shù)據(jù)集信息見(jiàn)表2。實(shí)驗(yàn)中隨機(jī)抽取參數(shù)s及閾值參數(shù)的設(shè)置同上。實(shí)驗(yàn)在不同的聚類個(gè)數(shù)參數(shù)下進(jìn)行了測(cè)試。實(shí)驗(yàn)結(jié)果所計(jì)算得到的J值見(jiàn)表3，所用聚類時(shí)間見(jiàn)表4。

表2 UCI標(biāo)準(zhǔn)數(shù)據(jù)集

表3 不同聚類參數(shù)下在UCI數(shù)據(jù)聚集上得到的J值

表4 不同聚類參數(shù)下在UCI數(shù)據(jù)聚集上所需聚類時(shí)間(s)

從以上實(shí)驗(yàn)結(jié)果可以看出，在標(biāo)準(zhǔn)數(shù)據(jù)集上，本文提出的基于隨機(jī)采樣的K-均值聚類方法的J值較高，樣本的抱團(tuán)性相對(duì)較差;其次，隨著聚類參數(shù)的增加，聚類結(jié)果的抱團(tuán)性越好，但聚類所用的時(shí)間也略有增長(zhǎng)。此外，從聚類效率看，基于隨機(jī)采樣的K-均值聚類方法比傳統(tǒng)K-均值聚類方法有較為明顯的提高，特別地，當(dāng)數(shù)據(jù)集規(guī)模較大時(shí)，在聚類效率上的提高效果非常明顯。

綜上可看出，由于本文提出的Kmeans_RS聚類方法采用了隨機(jī)采樣的方法，通過(guò)對(duì)小規(guī)模的工作集進(jìn)行K-均值聚類，而對(duì)大規(guī)模的剩余樣本直接歸類，因此能夠以較高的訓(xùn)練效率處理大規(guī)模數(shù)據(jù)的聚類問(wèn)題，同時(shí)保證了聚類結(jié)果的抱團(tuán)性能。

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

K-均值聚類方法是目前機(jī)器學(xué)習(xí)領(lǐng)域常用的一種有效聚類方法，本文針對(duì)傳統(tǒng)K-均值聚類方法對(duì)大規(guī)模數(shù)據(jù)聚類效率低下的問(wèn)題，提出一種基于隨機(jī)抽樣的加速K-均值聚類方法。該方法首先采用隨機(jī)抽樣的方法從整個(gè)聚類數(shù)據(jù)集中提取小規(guī)模的工作集并進(jìn)行傳統(tǒng)K-均值聚類，對(duì)聚類后的每個(gè)類計(jì)算其中心和半徑，通過(guò)衡量剩余樣本與已得到的聚類結(jié)果的關(guān)系，來(lái)對(duì)剩余的樣本進(jìn)行歸類。由于該方法通過(guò)隨機(jī)抽樣大大地減小了參與K-均值聚類的問(wèn)題規(guī)模，從而有效提高了聚類效率，可解決大規(guī)模數(shù)據(jù)的聚類問(wèn)題。

［1］Viktor M S，Kenneth C.大數(shù)據(jù)時(shí)代［M］.盛揚(yáng)燕，周濤譯.杭州:浙江人民出版社，2012.

［2］苗奪謙，王國(guó)胤，劉清，等.粒計(jì)算:過(guò)去、現(xiàn)在與展望［M］.北京:科學(xué)出版社，2007:299-303.

［3］張萍，王劍鋼.結(jié)合空間信息的FCM聚類噪聲圖像分割方法［J］.計(jì)算機(jī)與現(xiàn)代化，2012(3):52-54，58.

［4］湯秋菊，李義杰.無(wú)指導(dǎo)聚類在信用卡促銷中的應(yīng)用［J］.計(jì)算機(jī)與現(xiàn)代化，2007(9):100-102.

［5］張敏，于劍.基于劃分的模糊聚類算法［J］.軟件學(xué)報(bào)，2004，15(6):858-868.

［6］Rudi L Cilibrasi，Paul M B Vitányi.A fast quartet tree heuristic for hierarchical clustering［J］.Pattern Recognition，2011，44(3):662-677.

［7］周紅芳，趙雪涵，周揚(yáng).基于限定區(qū)域數(shù)據(jù)取樣的密度聚類算法［J］.計(jì)算機(jī)應(yīng)用，2012，32(8):2182-2185.

［8］Su M C，Chou C H.A modified version of the k-means algorithm with a distance based on cluster symmetry［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23(6):674-680.

［9］宋浩遠(yuǎn).基于模型的聚類方法研究［J］.重慶科技學(xué)院學(xué)報(bào):自然科學(xué)版，2008，10(3):71-73.

［10］劉宏兵，周文勇，郭振.基于模糊關(guān)系傳遞閉包的聚類方法［J］.信陽(yáng)師范學(xué)院學(xué)報(bào):自然科學(xué)版，2008，21(1):144-146.

［11］楊寧，唐常杰，王悅，等.基于譜聚類的多數(shù)據(jù)流演化事件挖掘［J］.軟件學(xué)報(bào)，2010，21(10):2395-2409.

［12］Elkan C.Using the triangle inequality to accelerate kmeans［C］//Proceedings of the 20th International Conference on Machine Learning.2003:147-153.

［13］王秀華.一種并行的加速K-均值聚類方法［J］.電腦知識(shí)與技術(shù)，2013，9(18):4299-4302.

［14］Huang G B，Ding X，Zhou H.Optimization method based extreme learning machine for classification［J］.Neurocomputing，2010，74(1-3):155-163.

［15］UCI Machine Learning Repository.Welcome to the UC Irvine Machine Learning Repository!［DB/OL］.http://archive.ics.uci.edu/ml/，2013-07-01.