王秀華

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

Step1 采樣過程:

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

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

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

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

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

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

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

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

2 實驗結(jié)果及分析

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

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

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

其中zin為每個頂點(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ù)據(jù)集

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

表1 Kmeans_RS與K-means實驗結(jié)果對比

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

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

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

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

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

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

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

3 結(jié)束語

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

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

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

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

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

［5］張敏，于劍.基于劃分的模糊聚類算法［J］.軟件學(xué)報，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ī)應(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é)報:自然科學(xué)版，2008，10(3):71-73.

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

［11］楊寧，唐常杰，王悅，等.基于譜聚類的多數(shù)據(jù)流演化事件挖掘［J］.軟件學(xué)報，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ù)，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.