一種改進(jìn)的基于大數(shù)據(jù)集的混合聚類算法*

張 曉，王 紅

(1.山東師范大學(xué)信息科學(xué)與工程學(xué)院，山東 濟(jì)南 250014;2.山東省分布式計(jì)算機(jī)軟件重點(diǎn)實(shí)驗(yàn)室，山東 濟(jì)南 250014)

一種改進(jìn)的基于大數(shù)據(jù)集的混合聚類算法*

張 曉，王 紅

(1.山東師范大學(xué)信息科學(xué)與工程學(xué)院，山東 濟(jì)南 250014;2.山東省分布式計(jì)算機(jī)軟件重點(diǎn)實(shí)驗(yàn)室，山東 濟(jì)南 250014)

針對(duì)k-means算法過度依賴初始聚類中心、收斂速度慢等局限性及其在處理海量數(shù)據(jù)時(shí)存在的內(nèi)存不足問題，提出一種新的針對(duì)大數(shù)據(jù)集的混合聚類算法super-k-means，將改進(jìn)的基于超網(wǎng)絡(luò)的高維數(shù)據(jù)聚類算法與k-means相結(jié)合，并經(jīng)過MapReduce并行化后部署在Hadoop集群上運(yùn)行。實(shí)驗(yàn)表明，該算法不僅在收斂性以及聚類精度兩方面得到優(yōu)化，其加速比和擴(kuò)展性也有了大幅度的改善。

k-means；超網(wǎng)絡(luò)；頻繁項(xiàng)集；超圖劃分；MapReduce

1 引言

大數(shù)據(jù)聚類是當(dāng)前聚類研究的重點(diǎn)。在海量數(shù)據(jù)的聚類中，現(xiàn)有的聚類算法在時(shí)間復(fù)雜性和空間復(fù)雜性上都存在一定的局限，解決這個(gè)問題的一種途徑就是引用并行處理技術(shù)，設(shè)計(jì)出高效的并行聚類算法，來提高算法性能。目前，MapReduce是最主流且實(shí)用的并行化模型。

k-means算法是傳統(tǒng)的經(jīng)典聚類算法，但是該算法對(duì)初始值具有很強(qiáng)的依賴性[1]，即算法的魯棒性不高。此外，k-means算法在串行計(jì)算方法中的時(shí)間復(fù)雜度比較高，處理能力難以滿足需求。目前，對(duì)與k-means算法相結(jié)合的混合聚類算法及其并行化方面已經(jīng)取得了較為理想的研究成果。賴玉霞等人[2]提出的一種優(yōu)化的基于密度的算法有效地解決了k-means算法過度依賴初始值的問題。田森平等人[3]提出了自動(dòng)獲取最佳k值的算法。畢曉君等人[4]提出一種結(jié)合人工蜂群和k-均值的混合聚類算法，使得聚類效果有了明顯改善。Fagin R等人[5]提出了一種結(jié)合遺傳算法和k-means的混合聚類方法，該方法能有效地解決k-means過于依賴初始值的瓶頸問題，但是串行依然會(huì)增加算法運(yùn)行的時(shí)間復(fù)雜度。Ngazimbi M等人[6]利用Apache Hadoop MapReduce框架實(shí)現(xiàn)了k-means、Greedy Agglomerative和Expectation Maximization聚類算法。

針對(duì)k-means聚類算法應(yīng)用在大數(shù)據(jù)集上的不足，本文提出一種新的針對(duì)大數(shù)據(jù)集的混合聚類算法super-k-means，首先，將高維數(shù)據(jù)映射到一個(gè)大規(guī)模帶權(quán)超網(wǎng)絡(luò)中；其次，定義超網(wǎng)絡(luò)中邊的權(quán)重；再次，采用優(yōu)化的超圖劃分方法劃分帶權(quán)超網(wǎng)絡(luò)；最后，將得到的k個(gè)劃分作為k-means算法的k個(gè)初始聚類中心，通過MapReduce并行化后部署在Hadoop集群上運(yùn)行。這樣既能有效地過濾掉聚類中的噪聲數(shù)據(jù)，又克服了傳統(tǒng)k-means算法穩(wěn)定性差的缺點(diǎn)。實(shí)驗(yàn)表明，本文提出的算法super-k-means行之有效。

2 相關(guān)工作

2.1 k-means算法的基本原理

k-means算法是1967年由MacQueen首次提出的一種經(jīng)典算法， K-means算法的處理流程[7]如下：

(1)在所有的n個(gè)數(shù)據(jù)點(diǎn)中隨機(jī)選取k個(gè)點(diǎn)作為初始簇中心；

(2)將k個(gè)選擇點(diǎn)之外的每個(gè)數(shù)據(jù)點(diǎn)，根據(jù)它們與k個(gè)初始簇中心的相似度(歐氏距離)，分別分配到與其最相似的(歐氏距離最小)簇；

(3)重新計(jì)算得出新聚類的中心對(duì)象(均值)；

(4)迭代該過程至聚類質(zhì)量檢測(cè)函數(shù)收斂。

k-means聚類算法的偽代碼如下所示：

算法k-means

輸入：數(shù)據(jù)集D，劃分簇的個(gè)數(shù)k;

輸出：k個(gè)簇的集合。

(1)Initially choosekpoints that are likely to be in different clusters;

(2)Make these points the centroids of their clusters;

(3)FOR each remaining pointpDO

(4) find the centroid to whichpis closest;

(5) Addpto the cluster of that centroid;

(6) Adjust the centroid of that cluster to account forp;

(7)END;

k-means算法通常使用誤差平方和SSE(Sum of Squared Error)[7]來檢測(cè)聚類質(zhì)量。其形式化的定義如下所示：

(1)

其中，d()表示兩個(gè)對(duì)象之間的距離(通常采用歐氏距離)。k值相同時(shí)，SSE越小說明簇內(nèi)對(duì)象越集中，對(duì)于不同的k值，k值越大對(duì)應(yīng)的SSE值越小。

2.2 基于超網(wǎng)絡(luò)的數(shù)據(jù)聚類算法流程

對(duì)于大規(guī)模的高維數(shù)據(jù),由于維度災(zāi)難的影響,若采用傳統(tǒng)的基于降維的算法進(jìn)行聚類,會(huì)出現(xiàn)的一個(gè)共同問題是損失一部分有用的信息，而這會(huì)影響聚類結(jié)果。利用超網(wǎng)絡(luò)方法進(jìn)行高維數(shù)據(jù)聚類，能有效過濾掉聚類中的噪聲數(shù)據(jù)，保證數(shù)據(jù)聚類的質(zhì)量。超網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)即超圖。

一個(gè)超圖[8]：

H=(V，E)

(2)

由一個(gè)頂點(diǎn)集(V)和一個(gè)邊集(E)構(gòu)成。權(quán)重超圖就是帶權(quán)圖的擴(kuò)充，超邊可以連接多于兩個(gè)以上的頂點(diǎn)。在這類圖模型中，頂點(diǎn)集V表示將要聚類的數(shù)據(jù)類的集，而每個(gè)超邊e∈E連著相關(guān)類的集。

聚類實(shí)現(xiàn)步驟如下:

步驟1使用經(jīng)典的 Apriori 算法挖掘出所有頻繁的超邊，即找出所有支持度大于設(shè)定的最小閾值的超邊。對(duì)每條超邊，找到其頻繁項(xiàng)集中包含的支持度和置信度分別滿足最小閾值的關(guān)聯(lián)規(guī)則，從而計(jì)算每條超邊的權(quán)重。這里將采用支持度與置信度的乘積作為權(quán)重。

步驟2通常采用的超圖分割算法是hMETIS。其基本思想:將建立的超圖模型通過粗化、初始劃分、遷移優(yōu)化三個(gè)階段尋找權(quán)重最小的邊并將它切割，不斷反復(fù)直到得到k個(gè)有效劃分。hMETIS能在幾分鐘內(nèi)在包含超過100 000個(gè)點(diǎn)的大規(guī)模線路中找到非常好的劃分。特別對(duì)k方式劃分來說，hMETIS的復(fù)雜性是O((|V|+|E|)lgk)，其中|V|是頂點(diǎn)數(shù)，|E|是邊數(shù)。

步驟3由上個(gè)步驟得到k個(gè)簇，然后通過評(píng)價(jià)函數(shù)來確定符合要求的聚類結(jié)果。

Figure 1 Basic flowchart of the algorithm

2.3 改進(jìn)的兩階段混合聚類算法

本文提出的這種聚類算法super-k-means，先通過第一階段的超圖聚類得到k個(gè)簇，作為第二階段k-means聚類算法的k個(gè)初始中心進(jìn)行聚類，通過兩階段的混合聚類既克服了k-means算法過度依賴初始聚類中心、穩(wěn)定性差的缺點(diǎn)，又汲取了超圖模型適用于大規(guī)模的高維數(shù)據(jù)聚類的優(yōu)點(diǎn)。同時(shí)，基于Hadoop平臺(tái)的并行化處理也大大縮短了程序的運(yùn)行時(shí)間。該算法的主要流程如圖2所示。

Figure 2 Flowchart of the super-k-means algorithm

3 super-k-means算法的MapReduce并行化實(shí)現(xiàn)

由上述super-k-means的實(shí)現(xiàn)流程可見串行實(shí)現(xiàn)算法的時(shí)間復(fù)雜度比較高，與O(super-k-means)、N(數(shù)據(jù)記錄總個(gè)數(shù))、N(期望得到的聚類的個(gè)數(shù))、N(算法迭代次數(shù))、T(計(jì)算待分配的數(shù)據(jù)到中心點(diǎn)距離)等變量之間存在線性關(guān)系。如果要將M個(gè)數(shù)據(jù)對(duì)象聚成N個(gè)簇，那么在一次迭代中就需要完成MN次記錄到中心點(diǎn)的距離的計(jì)算操作，雖然這類計(jì)算操作最耗時(shí)，但也最容易并行處理：各個(gè)記錄與k個(gè)聚類中心的距離進(jìn)行比較的操作可以同時(shí)進(jìn)行。

從k-means算法流程中可以看出，主要的計(jì)算工作是將每個(gè)數(shù)據(jù)對(duì)象分配到跟其相似度最高(距離最近)的簇，并且該操作是相互獨(dú)立的，所以在每次MapReduce job中，這一步驟super-k-means算法可以通過分別執(zhí)行相同的Map和Reduce操作得到并行處理。

3.1 MapReduce模型

MapReduce編程模型[9]的基本思路：Hadoop MapReduce是當(dāng)前最主流的分布式計(jì)算框架，基于該框架的應(yīng)用程序能夠運(yùn)行在由數(shù)臺(tái)普通計(jì)算機(jī)組成的大型集群上，并能容錯(cuò)地并行處理大規(guī)模數(shù)據(jù)。MapReduce框架運(yùn)行在〈key,value〉上，Map是把原始輸入數(shù)據(jù)分解成一組中間的〈key,value〉對(duì)，Reduce把結(jié)果合成最終輸出。

這樣一項(xiàng)包含若干項(xiàng)任務(wù)(Task)的工作在MapReduce中被稱為作業(yè)(Job)。任務(wù)又包含若干map任務(wù)和若干reduce任務(wù),先由map任務(wù)并行地處理這些〈key,value〉鍵值對(duì)，然后MapReduce框架會(huì)將map的輸出結(jié)果進(jìn)行一系列復(fù)制、分組、排序等處理之后輸出給reduce任務(wù)。

Map函數(shù)和Reduce函數(shù)[10]是由程序員提供的， map和reduce任務(wù)分布在集群節(jié)點(diǎn)上運(yùn)行，并把結(jié)果存儲(chǔ)在分布式文件系統(tǒng)上。整個(gè)MapReduce對(duì)任務(wù)進(jìn)行調(diào)度和監(jiān)控，以及重新執(zhí)行失敗的任務(wù)。MapReduce框架是由一個(gè)主JobTracker和分布在每個(gè)集群節(jié)點(diǎn)的一個(gè)個(gè)從屬的TaskTracker組成。如圖3所示。

Figure 3 MapReduce job schematic

3.2 Map函數(shù)和Reduce函數(shù)的設(shè)計(jì)

Map函數(shù)：計(jì)算各個(gè)數(shù)據(jù)對(duì)象到中心點(diǎn)的距離并對(duì)該數(shù)據(jù)屬于的新類別重新標(biāo)記。將所有數(shù)據(jù)對(duì)象和上一輪Job的聚類中心作為Map函數(shù)的輸入，輸入數(shù)據(jù)鍵值對(duì)形式為〈row number,record number〉；按照讀入的簇中心記錄文件，Map函數(shù)計(jì)算出到每個(gè)輸入數(shù)據(jù)記錄距離最近的簇中心，并作出新的標(biāo)記；輸出中間結(jié)果鍵值對(duì)的形式為〈cluster category ID,records attribute vector〉。

Reduce函數(shù)：通過Map函數(shù)得到的結(jié)果計(jì)算出新的聚類中心，供下一輪Job使用。輸入數(shù)據(jù)鍵值對(duì)的形式為〈cluster category ID,{record attribute vector set}〉所有key相同的記錄送給同一個(gè)Reduce，累加key相同的點(diǎn)個(gè)數(shù)和各記錄分量并求出各分量的均值，并生成新的簇中心記錄；輸出結(jié)果鍵值對(duì)的形式為〈cluster category ID,mean vector〉。

Job結(jié)束之后，計(jì)算該輪新的聚類中心偏離誤差并進(jìn)行判斷。如果小于給定的閾值則算法結(jié)束；反之，用新的簇中心記錄文件覆蓋上一輪的文件，并啟動(dòng)新Job。

super-k-means算法在MapReduce框架下的運(yùn)行流程及算法偽代碼如下所示。

Figure 4 Super-k-means parallel implementation based on MapReduce

算法偽代碼如下：

Job：計(jì)算新的聚類中心

Map階段：

輸入：〈Object，一條數(shù)據(jù)〉

輸出：〈所屬類Ci，數(shù)據(jù)〉

public voidmap(Objectkey,Textvalue,

OutputCollector〈IntWritable,Text〉output,Reporterreporter) {

Stringline=value.toString().trim();

intsort=0;//聚類類別

doubleminDis=Double.MAX_VALUE;

for (inti=1;i<=k;i++) {

doubletmpDis=calDis(i,line);/*數(shù)據(jù)和類i間的距離*/

if (tmpDis

sort=i;

minDis=tmpDis;

}

}

output.collect(new IntWritable(sort),value);

}

Reduce階段：

輸入：〈Ci，相應(yīng)數(shù)據(jù)的集合〉

輸出：〈Ci,新的聚類中心〉

public voidreduce(IntWritablekey,Iterator〈Text〉values,OutputCollector〈IntWritable,Text〉output,Reporterreporter) {

introws=0,i=0;//rows表示數(shù)據(jù)條數(shù)

doublerecords[]=new double[COLS];/*COLS為全局變量，表示屬性的個(gè)數(shù)*/

while (values.hasNext()) {

rows++;

Stringtmp=values.next().toString();

StringTokenizeritr=newStringTokenizer(tmp);

i=0;

while (itr.hasMoreTokens()&&i

records[i++] += Double.parseDouble(itr.nextToken());

}

}

Stringline="";

for (i=0;i

line+=records[i]/rows+ " ";

}

output.collect(key,newText(line));

迭代Job，直至連續(xù)兩次聚類中心偏離距離小于給定的閾值。

4 實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境：本文采用由九臺(tái)普通PC機(jī)搭建的Hadoop集群進(jìn)行實(shí)驗(yàn)，測(cè)試super-k-means并行聚類算法，其中一臺(tái)作為master,其他8臺(tái)作為slaves。軟件配置如下： JDK 1.6.0.29；Hadoop 0.20.2，master節(jié)點(diǎn)上部署Hadoop的NameNode和JobTracker，slaves節(jié)點(diǎn)上部署TaskTracker和DataNode。每臺(tái)節(jié)點(diǎn)的硬件配置如下：CPU為雙核2.4 GHz；物理內(nèi)存為4 GB；硬盤為2 TB。實(shí)驗(yàn)數(shù)據(jù)集主要是人工數(shù)據(jù)以及聯(lián)合聚類算法的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集(http://www.datatang.com/data/44245)。數(shù)據(jù)維度為6。每組實(shí)驗(yàn)均采用平均執(zhí)行多次取平均值的方法作為實(shí)驗(yàn)結(jié)果。

4.1 單機(jī)處理對(duì)比實(shí)驗(yàn)

4.1.1 聚類精確度對(duì)比

實(shí)驗(yàn)內(nèi)容：在處理相同數(shù)據(jù)的條件下，super-k-means 聚類算法與k-means聚類算法各自完成聚類結(jié)果的精確度對(duì)比。從實(shí)驗(yàn)數(shù)據(jù)中構(gòu)造數(shù)據(jù)記錄數(shù)依次為500、2 000、5 000的數(shù)據(jù)集Data1、Data2、Data3。分別采用三種算法進(jìn)行聚類，用6次的平均值作為最終實(shí)驗(yàn)結(jié)果。如表1所示。

Table 1 Accuracy comparison of different clustering algorithms表1 聚類精確度對(duì)比

由表1可以看出，在處理小的數(shù)據(jù)集時(shí)，k-means算法所得到的結(jié)果也不太理想，而在用改進(jìn)后的super-k-means(超網(wǎng)絡(luò)聚類與k-means相結(jié)合)算法后聚類效果明顯得到了改善。采用并行super-k-means后，隨著處理的數(shù)據(jù)集規(guī)模的不斷增大，所得到的聚類結(jié)果和串行的算法相比較也進(jìn)一步有了明顯的改善。這主要是因?yàn)槌W(wǎng)絡(luò)聚類算法在較大規(guī)模數(shù)據(jù)聚類方面具有一定的優(yōu)勢(shì)，并且通過超網(wǎng)絡(luò)聚類算法幫助k-means確定了初始聚類中心，從而收斂到了較好的結(jié)果。

4.1.2 單機(jī)處理對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)內(nèi)容：在相同配置環(huán)境下處理相同規(guī)模數(shù)據(jù)時(shí)，比較集群中的一個(gè)節(jié)點(diǎn)與單機(jī)super-k-means算法完成聚類所需要的時(shí)間。本實(shí)驗(yàn)中Java虛擬機(jī)JVM(Java Virtual Machine)的內(nèi)存設(shè)置為1 GB。實(shí)驗(yàn)結(jié)果如表2所示。

Table 2 Single processing experimental results表2 單機(jī)處理實(shí)驗(yàn)結(jié)果

其中，r1為單機(jī)上使用super-k-means聚類算法所用的時(shí)間；r2為集群中一個(gè)節(jié)點(diǎn)完成super-k-means聚類算法所用時(shí)間。實(shí)驗(yàn)中，隨著數(shù)據(jù)量的急劇增大，super-k-means算法的時(shí)間復(fù)雜度會(huì)急劇增大并會(huì)產(chǎn)生內(nèi)存溢出。實(shí)驗(yàn)表明，當(dāng)數(shù)據(jù)規(guī)模很小時(shí)，單機(jī)運(yùn)行的super-k-means 聚類算法的運(yùn)算能力要大大高于Hadoop集群中單節(jié)點(diǎn)，這是因?yàn)榕c實(shí)際的計(jì)算時(shí)間相比較而言，MapReduce 每次啟動(dòng) map 和 reduce 占據(jù)的時(shí)間比例較大。但是，當(dāng)單機(jī)super-k-means聚類算法因?yàn)閮?nèi)存不足而停止計(jì)算時(shí)，Hadoop單節(jié)點(diǎn)仍能正常完成聚類運(yùn)算，由此初步可見， super-k-means聚類算法在經(jīng) MapReduce并行化之后在處理大數(shù)據(jù)方面有了一定的優(yōu)勢(shì)。

4.2 小型集群加速比實(shí)驗(yàn)

實(shí)驗(yàn)1加速比(Speedup)。

(3)

其中，Sn是加速比。

從實(shí)驗(yàn)數(shù)據(jù)中構(gòu)建大小依次為60 GB、40 GB、20 GB的DataA、DataB、DataC三個(gè)用于并行算法的大規(guī)模數(shù)據(jù)集。

將集群中所有節(jié)點(diǎn)按需要逐漸參與計(jì)算，并觀察每個(gè)節(jié)點(diǎn)的加速比。實(shí)驗(yàn)中，集群中每個(gè)節(jié)點(diǎn)上運(yùn)行時(shí)的最大map數(shù)和最大reduce 數(shù)可以根據(jù)數(shù)據(jù)規(guī)模大小調(diào)節(jié)，可以更大限度地調(diào)用 Hadoop集群的能力。實(shí)驗(yàn)結(jié)果如圖5 所示。從圖5中可以看出，隨著節(jié)點(diǎn)數(shù)的增加，每個(gè)Job運(yùn)行的時(shí)間降低，對(duì)相同規(guī)模數(shù)據(jù)來說，隨著節(jié)點(diǎn)數(shù)的增加，系統(tǒng)的處理能力有了顯著的提高，這說明集群在處理super-k-means算法時(shí)具有良好的加速比。可針對(duì)各種指標(biāo)對(duì)不同聚類算法進(jìn)行對(duì)比驗(yàn)證分析。

Figure 5 Super-k-means acceleration ratio experiment based on MapReduce

實(shí)驗(yàn)2分別進(jìn)行三組實(shí)驗(yàn)測(cè)試super-k-means聚類算法的擴(kuò)展性：第一組，數(shù)據(jù)集大小為2 GB、4 GB、8 GB、16 GB對(duì)應(yīng)1、2、4、8個(gè)節(jié)點(diǎn)；第二組，數(shù)據(jù)集大小為4 GB、8 GB、16 GB、32 GB對(duì)應(yīng)1、2、4、8個(gè)節(jié)點(diǎn)；第三組，數(shù)據(jù)集大小為8 GB、16 GB、32 GB、64 GB對(duì)應(yīng)1、2、4、8個(gè)節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果如圖6所示。從圖6中可以看出，當(dāng)節(jié)點(diǎn)數(shù)和數(shù)據(jù)規(guī)模同比例增長(zhǎng)時(shí)，算法的整體擴(kuò)展性是逐漸降低的，主要是因?yàn)殡S著節(jié)點(diǎn)數(shù)的增加，系統(tǒng)節(jié)點(diǎn)間的通訊開銷增大，從而導(dǎo)致算法的整體運(yùn)行速度變慢。但是，隨著數(shù)據(jù)規(guī)模的逐漸增大，算法的擴(kuò)展性越來越好，是由于數(shù)據(jù)規(guī)模越大越能充分調(diào)動(dòng)集群中每個(gè)節(jié)點(diǎn)的處理能力，此時(shí)節(jié)點(diǎn)間的通訊開銷減少的比例也越來越高。因此，第三組中算法的擴(kuò)展性大于第一組和第二組，更適合處理大規(guī)模數(shù)據(jù)集。

Figure 6 Super-k-means scalability experiment based on MapReduce

5 結(jié)束語

將兩種不同的聚類算法相結(jié)合可以互相取長(zhǎng)補(bǔ)短，從而提高聚類效果，但同時(shí)又會(huì)產(chǎn)生算法時(shí)間復(fù)雜度高的問題。Super-k-means算法在Hadoop平臺(tái)下的并行化設(shè)計(jì)和實(shí)現(xiàn)，不僅提高了算法運(yùn)行的時(shí)間效率而且也改善了算法運(yùn)行的結(jié)果。

對(duì)于如何改進(jìn)基于超網(wǎng)絡(luò)的聚類算法從而提高超網(wǎng)絡(luò)模型的劃分精確度，以及對(duì)k-means算法中如何確定最佳的k值從而避免陷入局部最優(yōu)，加快收斂速度，這些都是有待于以后進(jìn)行研究的問題。

[1] Li Qun,Yuan Jin-sheng. Optimal density text clustering algorithm based on DBSCAN [J]. Computer Engineering and Design,2012,33(4):1409-1413.(in Chinese)

[2] Lai Yu-xia,Liu Jian-ping. Optimal study on initial center ofk-means algorithm [J]. Computer Engineering and Applications,2008,44(10):147-149. (in Chinese)

[3] Tian Sen-ping,Wu Wen-liang. Algorithm of automatic gained parameter valuekbased on dynamick-means [J]. Computer Engineering and Design,2011,32(1):274-276.(in Chinese)

[4] Bi Xiao-jun，Gong Ru-jiang.Hybrid clustering algorithm based

on artificial bee colony andk-means algorithm [J]. Application Research of Computers, 2012，29(6):2040-2045.(in Chinese)

[5] Fagin R，Kolaitis P G，Pops L． Data exchange:Getting to the core[J]． ACM TODS，2005，30(1):147-210．

[6] Ngazimbi M.Data clustering using MapReduce[D]. Idaho：BosieState University，2009.

[7] Sun Ji-gui,Liu Jie. Clustering algorithms research[J]. Journal of Software,2008，22(19)：48-61.(in Chinese)

[8] Wang Zhi-ping,Wang Zhong-tuo. Super network theory and its application[M]. Beijing:Science Press,2008.(in Chinese)

[9] Verma A，Llorae X，Goldberg D E．Scaling genetic algorithms using MapReduce[C]∥Proc of International Conference on Intelligent Systems Design and Applications,2009:1.

[10] Jin C，Vecchiola C，Buyya R．Mrpga：An extension of MapReduce for parallelizing genetic algorithms[C]∥Proc of IEEE the 4th International Conference on Science，2008：214-221.

附中文參考文獻(xiàn)

[1] 李群，袁金生. 基于DBSCAN的最優(yōu)密度文本聚類算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2012，33(4):1409-1413.

[2] 賴玉霞，劉建平.k-means算法的初始聚類中心的優(yōu)化[J]．計(jì)算機(jī)工程與應(yīng)用，2008，44(10)：147-149．

[3] 田森平，吳文亮．自動(dòng)獲取k-means聚類參數(shù)k值的方法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2011,32(1):274-276.

[4] 畢曉君，宮汝江. 一種結(jié)合人工蜂群和k-均值的混合聚類算法[J]. 計(jì)算機(jī)應(yīng)用研究，2012，29(6)：2040-2045.

[7] 孫吉貴,劉杰. 聚類算法研究[J]. 軟件學(xué)報(bào)，2008，22(19)：48-61.

[8] 王志平,王眾托. 超網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京：科學(xué)出版社,2008.

張曉(1988-),女,山東萊蕪人，碩士生，CCF會(huì)員(E200037819G),研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)和大數(shù)據(jù)。E-mail:970790885@qq.com

ZHANG Xiao,born in 1988,MS candidate,CCF member(E200037819G),her research interests include complex network, and big data.

王紅(1966-),女,天津人，博士，教授，研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)和大數(shù)據(jù)。E-mail:1456029328@qq.com

WANG Hong,born in 1966,PhD,professor,her research interests include complex network, and big data.

An improved hybrid clustering algorithm based on large data sets

ZHANG Xiao,WANG Hong

(1.School of Information Science and Engineering,Shandong Normal University,Jinan 250014;2.Key Laboratory of Distributed Computer Software in Shandong Province,Jinan 250014,China)

Aiming at the following three problems of thek-means algorithm:excessive dependence on the initial clustering center, slow convergence speed and insufficient memory when dealing with huge amounts of data, we present a new hybrid clustering algorithm called super-k-means for large data sets. The algorithm combines thek-means algorithm with the improved high-dimensional data clustering algorithm based on the super-network. We run it on the Hadoop clusters after the MapReduce parallel processing, and an ideal effect of clustering is achieved. Experimental results show that the algorithm not only improves the convergence and the clustering accuracy but also has high speedup and scalability performance.

k-means;super network;frequent itemsets；hypergraph partitioning;MapReduce

1007-130X(2015)09-1621-06

2014-09-28;

2014-12-16基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61373149,61472233)；山東省科技計(jì)劃項(xiàng)目(2012GGX10118，2014GGX101026)

TP391

A

10.3969/j.issn.1007-130X.2015.09.003

通信地址：250014 山東省濟(jì)南市歷下區(qū)文化東路88號(hào)山東師范大學(xué)信息科學(xué)與工程學(xué)院

Address:School of Information Science and Engineering,Shandong Normal University,Jinan 250014,Shandong,P.R.China