一種大規(guī)模分類數(shù)據(jù)聚類算法及其并行實現(xiàn)

丁祥武　郭　濤　王　梅　金　冉

1(東華大學計算機科學與技術(shù)學院　上?！?01620)2(浙江萬里學院計算機與信息學院　浙江寧波　315100)(dingxw@dhu.edu.cn)

一種大規(guī)模分類數(shù)據(jù)聚類算法及其并行實現(xiàn)

丁祥武1郭濤1王梅1金冉2

1(東華大學計算機科學與技術(shù)學院上海201620)2(浙江萬里學院計算機與信息學院浙江寧波315100)(dingxw@dhu.edu.cn)

摘要CLOPE算法在大規(guī)模、稀疏、高維的分類數(shù)據(jù)集的聚類上取得了很好的聚類效果.然而該算法受輸入數(shù)據(jù)的順序影響，難以獲得穩(wěn)定且全局最優(yōu)的聚類結(jié)果.因此提出一種基于等分劃分再排列思想的p -CLOPE算法對這一缺陷進行改進.在p -CLOPE算法的每一輪迭代過程中，對輸入數(shù)據(jù)集等分為p部分再排列生成不同順序的p!份數(shù)據(jù)集，對這些數(shù)據(jù)集分別聚類并選取最優(yōu)的聚類結(jié)果作為下一輪迭代的輸入.為了降低上述過程的時間復雜度，提出了一種中間結(jié)果復用策略，較大程度地提高了聚類速度.最后，在Hadoop平臺上實現(xiàn)了一個包含p -CLOPE相關(guān)算法的開源聚類工具.實驗表明：p -CLOPE算法比CLOPE算法取得了更優(yōu)的聚類結(jié)果.對蘑菇數(shù)據(jù)集，當CLOPE算法取得最優(yōu)聚類結(jié)果時，p -CLOPE比CLOPE取得了高35.7%的收益值；在處理大量數(shù)據(jù)時，并行p -CLOPE比串行p -CLOPE極大地縮短了聚類時間，并在計算資源充足時，取得了接近p!倍的加速比.

關(guān)鍵詞分類數(shù)據(jù)；CLOPE；p -CLOPE；并行聚類；MapReduce

傳統(tǒng)的針對數(shù)值數(shù)據(jù)的聚類算法雖然在不斷取得突破[1]，但并不適合處理分類數(shù)據(jù)[2].分類數(shù)據(jù)由非數(shù)值的屬性組成.對分類數(shù)據(jù)快速且準確地聚類在零售業(yè)、電子商務(wù)、醫(yī)療診斷、生物信息學等領(lǐng)域都有大量應用.因此，研究分類數(shù)據(jù)的聚類算法具有重要意義.

然而，這些領(lǐng)域的數(shù)據(jù)通常具有高維度、稀疏、數(shù)據(jù)量大等特征，要對這種分類數(shù)據(jù)進行快速且準確地聚類通常非常困難.分類數(shù)據(jù)聚類算法k-modes[3]是對基于距離的數(shù)值數(shù)據(jù)聚類算法k-means[4]的擴展，采用0-1差異度來代替k-means算法中的距離，但沒能充分考慮2個屬性間的相似性，也沒有從全局的角度考慮2條交易間的相似性.層次聚類方法ROCK[5]采用公共鄰居數(shù)(鏈接)作為評價交易間相關(guān)性的度量標準.用于界定2條交易是否為鄰居的相似度閾值θ需要預先指定，但很難給出恰當?shù)拈撝?，另外還要求用戶事先選定聚類簇數(shù)k.LargeItem[6]算法通過迭代優(yōu)化一個全局評估函數(shù)來實現(xiàn)對大量分類數(shù)據(jù)的聚類，其最小支持度θ和權(quán)重w很難確定.CLOPE[7]算法在大規(guī)模、稀疏、高維數(shù)據(jù)集的聚類上取得了較好的聚類效果，該算法提出一個全局評估函數(shù)，通過一個簇的直方圖中的高與寬的比率來表示這個簇內(nèi)交易的重疊程度.CLOPE的運行速度比LargeItem和ROCK更快，聚類質(zhì)量比LargeItem更優(yōu)，與設(shè)定了合適參數(shù)值的ROCK算法接近[7].SCLOPE[8]和σ-SCLOPE[9]是CLOPE應用在數(shù)據(jù)流上的聚類算法，犧牲了一些聚類的準確性.FUZZY CLOPE[10]提出了一種修正的劃分模糊度，用來實現(xiàn)對CLOPE算法中的排斥因子r的自動優(yōu)選.但是，這些研究都沒有涉及一個問題：即數(shù)據(jù)集中交易的輸入順序會對聚類結(jié)果產(chǎn)生影響，不同的輸入順序可能會得到不一致的聚類結(jié)果.這一缺陷將導致CLOPE算法不能取得穩(wěn)定且最優(yōu)的聚類結(jié)果.

本文提出了p-CLOPE算法，它采用一種等分劃分再排列輸入數(shù)據(jù)的思想對上述缺陷進行改進.為了降低p-CLOPE算法的時間復雜度，提出了一種中間結(jié)果復用策略，通過該策略可以較大程度地提高聚類速度.最后，在Hadoop平臺上用MapReduce并行編程模型實現(xiàn)了p-CLOPE算法的并行化，并分析了時間與空間復雜度和加速比.實驗表明:p-CLOPE算法能比CLOPE算法取得更優(yōu)的聚類結(jié)果，也取得了很好的加速比.

1CLOPE算法及其缺陷

1.1CLOPE算法

分類數(shù)據(jù)聚類算法CLOPE[7]以簇的直方圖的高寬比作為全局評估函數(shù)(也稱全局收益函數(shù)).隨著每一簇內(nèi)數(shù)據(jù)重合度的增多，代表簇的統(tǒng)計直方圖的高寬比也逐漸增加.所有簇的直方圖的高寬比之和稱為全局收益值.當全局收益值達到最大時，所對應的聚類被認為是最優(yōu)的.

定義1[7]. 分類數(shù)據(jù)集D是一組交易數(shù)據(jù)的集合{t1,t2,…,tn}.每條交易數(shù)據(jù)是一些屬性項的集合{i1,i2,…,im}.一個聚類{C1,C2,…,Ck}是{t1,t2,…,tn}的一個劃分，也就是說C1∪C2∪…∪Ck={t1,t2,…,tn}而且對任意1≤i,j≤k，滿足Ci≠?，且Ci∩Cj=?.每一個Ci叫作一個簇，n，m，k分別表示交易的條數(shù)、屬性項的個數(shù)、簇的個數(shù).

給定一個簇C，可以找到這個簇中所有的不同屬性項，一個屬性項出現(xiàn)的頻率表示有多少條交易包含這個屬性項，用D(C)表示簇C中不同屬性項的集合，用Occ(i,C)表示屬性項i在簇C中出現(xiàn)的頻率.這樣可以畫出簇C的直方圖，用屬性項表示X軸，用每個屬性項出現(xiàn)的頻率表示Y軸[7].定義一個簇C的直方圖的面積S(C)和寬度W(C)為[7]

(1)

(2)

簇的高定義為H(C)=S(C)W(C)，全局評估函數(shù)定義為

(3)

其中，排斥因子r是一個正實數(shù)，用來控制簇內(nèi)交易間的相似程度.當r較大時，簇內(nèi)的交易必須有較多的公共項；相反，較小的r可用來對稀疏數(shù)據(jù)分組.通過調(diào)整排斥因子r的大小可以得到不同的簇個數(shù)，r越大，簇的個數(shù)越多.對于每個確定的r都可以找到一個劃分C使得收益值Profit(C)最大.具體的算法如下：

算法1. CLOPE算法[7].

① while 未到數(shù)據(jù)文件尾部

② 讀下一條交易〈t,unknown〉；

③ 將t放入一個使收益最大的現(xiàn)有簇或新簇Ci中;

④ 將〈t,i〉寫回數(shù)據(jù)集中;

⑤ repeat

⑥ 重新回到數(shù)據(jù)文件頭;

⑦moved=false；

⑧ while 未到數(shù)據(jù)文件尾部

⑨ 讀下一條交易〈t,i〉；

⑩ 移動t到一個使收益最大的現(xiàn)有簇或新簇Cj中;

1.2CLOPE算法的缺陷分析

對于一個特定的排斥因子r，CLOPE算法的目的是找一個收益值Profit(C)最大的聚類.但是實際上我們發(fā)現(xiàn)CLOPE算法并不能找到收益值最大的聚類，因為它的聚類結(jié)果會受數(shù)據(jù)集中交易的輸入順序的影響，交易的順序不同時聚類結(jié)果可能不一致.也就是說CLOPE算法不能得到穩(wěn)定的聚類結(jié)果，而且這個聚類結(jié)果通常不是最優(yōu)的.

這里舉例來說明這一問題：對數(shù)據(jù)集D={abd,bcd,acd,ab,bc,ac}，當排斥因子r=2.0時，如果數(shù)據(jù)按照從左到右(abd→bcd→acd→ab→bc→ac)的順序輸入給CLOPE算法，那么得到的聚類{D}只有一個簇，其收益值為0.938.但是，如果按照從右到左(ac→bc→ab→acd→bcd→abd)的順序輸入，那么得到的聚類{{ab,abd}，{bc,bcd}，{ac,acd}}有3個簇，此時收益值為0.556.從以上的例子可以看出，輸入交易的順序不同時，聚類的結(jié)果可能不同.但是由于在默認的情況下，CLOPE算法只是按交易的原始順序?qū)?shù)據(jù)集進行聚類，這樣很有可能得不到最優(yōu)的聚類結(jié)果.

上述例子用到的數(shù)據(jù)集D只有6條交易，我們通過窮舉所有的輸入順序進行計算，發(fā)現(xiàn)只有2種聚類結(jié)果.而對一個實際待聚類的數(shù)據(jù)集，其數(shù)據(jù)量很大，在有限的計算能力下，窮舉所有的輸入順序，其計算時間是很難接受的.本文接下來提出一種先對數(shù)據(jù)劃分再排列劃分塊的思想來克服這一缺陷.

2p-CLOPE算法

2.1算法設(shè)計

針對CLOPE算法的缺陷，本文的改進思想是對原始數(shù)據(jù)形成多種輸入順序，對每種順序的數(shù)據(jù)分別聚類，然后從中選擇最優(yōu)的聚類作為最后的輸出.本文提出等分再排列的思想來形成不同順序的數(shù)據(jù).具體來說是先將要聚類的數(shù)據(jù)集D進行等分劃分，再進行排列，目的是打亂輸入數(shù)據(jù)的順序.如果將D等分為p部分，那么可產(chǎn)生p!種不同的排列，將重新排列后的數(shù)據(jù)集分別定義為Di(1≤i≤p!)，每一份數(shù)據(jù)集中交易的集合是相同的，只是交易的順序不同.對于得到的p!份數(shù)據(jù)集，我們可有2種處理方案:1)對每一份數(shù)據(jù)集Di先執(zhí)行CLOPE算法的全過程，然后再比較對每一份數(shù)據(jù)集聚類的收益值，選出收益值最大的聚類結(jié)果作為最終聚類結(jié)果；2)用CLOPE算法對p!份數(shù)據(jù)集分別執(zhí)行一次迭代，然后對這些迭代中最優(yōu)的聚類結(jié)果重新等分劃分再排列作為下一次迭代的輸入，如此迭代，直至全局最優(yōu)聚類劃分不再變化時，整個聚類過程結(jié)束.第2種方案能達到每一次迭代結(jié)果的最優(yōu)，而且對最優(yōu)的聚類劃分代表的數(shù)據(jù)集又重新劃分排列成p!份數(shù)據(jù)集，因而它對交易的順序打亂得更充分，可以取得比第1種方案全局更優(yōu)的聚類結(jié)果，而且所需要的迭次代數(shù)更少，整個聚類過程所需時間當然更少.因而，我們選擇第2種方案，具體步驟如下：

階段1. 對于每一份數(shù)據(jù)集Di，依次讀取它的每一條交易t，決定將t放入一個已經(jīng)存在的簇還是放入一個新的簇中，這取決于哪種情況下收益值將更大.每一個簇的收益值定義為

(4)

通過比較將t放入已有的各簇和放入一個新的簇所產(chǎn)生的收益值增量的大小來判斷將t放入已有的某簇中還是放入一個新的簇中.這樣每一份數(shù)據(jù)集Di都會被劃分成一些簇，而且每條交易有了對應的簇編號.階段1結(jié)束后，每個數(shù)據(jù)集Di代表了一個聚類，計算各個聚類的收益值Profitr(C).比較各個聚類的收益值，選出收益值最大的數(shù)據(jù)集Dm.

階段2. 將Dm等分劃分為p份，再排列為p!份數(shù)據(jù)集{D1,D2,…,Dp!}，對每一份數(shù)據(jù)集Di執(zhí)行原始CLOPE算法的階段2，即依次讀取它的每一條交易t，將這條交易從原來的簇中移除，再根據(jù)簇收益值的增量大小選擇放入某個已有的簇或者放入一個新的簇，如果這條交易現(xiàn)在放入的簇和原來所在的簇是同一個簇，則表示這個交易沒有移動.如果一個數(shù)據(jù)集Di中所有的交易都沒有移動，則表示Di對應的整個聚類劃分不再變化.再次計算每個數(shù)據(jù)集的收益值，從中選出全局收益值最大的數(shù)據(jù)集Dm.如果在某一輪迭代中，Dm中沒有交易移動，則程序結(jié)束，Dm對應的聚類劃分就是最終所求的聚類劃分.否則，重復執(zhí)行以上階段2的步驟，直到迭代結(jié)束.

由于本文的改進思想中引入了劃分參數(shù)p，因此將新的算法命名為p-CLOPE.

2.2劃分參數(shù)p

對于我們新引入的劃分參數(shù)p，它是一個正整數(shù).理論上，如果p等于數(shù)據(jù)集中總的交易條數(shù)n，那么劃分的每一部分都只包含一條交易，這樣的排列是一個全排列，能得到交易的各種順序組合.但實際上，當n很大時，由于受計算能力和存儲空間的限制，將無法實現(xiàn)這種情況，因為p!是一個增長非?？斓暮瘮?shù).在我們設(shè)計的p-CLOPE算法里，將p設(shè)定為用戶可以指定的參數(shù)，根據(jù)實際的計算能力和存儲空間來設(shè)定.實際上從第3節(jié)的實驗中可以看到：當p=4時已經(jīng)可以達到非常好的聚類效果,當p=1時p-CLOPE退化為CLOPE.

2.3中間結(jié)果的復用

將待聚類的數(shù)據(jù)集進行等分劃分、再進行排列，目的是遍歷劃分塊所構(gòu)成的全排列，而我們發(fā)現(xiàn)這個計算過程中存在大量相同的中間結(jié)果，充分利用可重用的中間結(jié)果可以很大程度地提高聚類的速度.以p=4為例，將待聚類的數(shù)據(jù)集劃分為4等份，標記為A，B，C，D.以A開始的排列可以用如圖1所示的樹來表示(以B，C，D開始的排列類似).每一種排列就是從根節(jié)點到葉子節(jié)點順序遍歷的節(jié)點.

Fig. 1　Permutation tree started by A.圖1　以A開始的排列所構(gòu)成的樹

遍歷路徑上重復的節(jié)點就代表到該點的部分聚類結(jié)果可以在計算對應數(shù)據(jù)時復用.例如，對于ABCD和ABDC兩種排列表示的數(shù)據(jù)集，它們可以復用的部分就是AB上各點的局部聚類結(jié)果.以A開始的排列中所有需要計算的劃分個數(shù)就是圖1中節(jié)點的個數(shù)，以B，C，D開始的排列也類似.可以計算出當p=4時需要計算的劃分數(shù)是64(即16×4).按4個劃分組成一個數(shù)據(jù)集來計算的話，等同于16份數(shù)據(jù)集的計算量.與不復用時(p=4時，需要計算4!=24個數(shù)據(jù)集)相比，計算量只有原來的23，隨著p的增大，復用的程度會增加.可以歸納出采用復用技術(shù)時，需要計算的等量數(shù)據(jù)集個數(shù)為

(5)

不采用復用技術(shù)時，需要計算的數(shù)據(jù)集的個數(shù)為p!，復用與不復用時計算量的比值為

(6)

當p分別為2，3，4，5，6時，如果盡量復用，則需要計算的數(shù)據(jù)集個數(shù)分別為2，5，16，65，326；如果完全不復用，則需要計算的數(shù)據(jù)集為2，6，24，120，720，兩者比例為1，0.833，0.667，0.542，0.453.由式(6)可知，當p=2時不可以復用，當p增大時復用的程度會增大.

由以上分析可知，采用復用技術(shù)與不采用復用相比，能較大程度地減小計算量、提高聚類的速度.

2.4算法實現(xiàn)

根據(jù)2.1～2.3節(jié)的設(shè)計，下面給出p-CLOPE算法.

算法2.p-CLOPE算法.

① 劃分數(shù)據(jù)文件成p片；

② 變換p片數(shù)據(jù)之間的順序得p!個數(shù)據(jù)集{D1,D2,…,Dp!};

③ forDk∈{D1,D2,…,Dp!}

④ while 未到文件Dk的尾部

⑤ 讀下一條交易〈t,unknown〉；

⑥ 將t放入一個使收益最大的現(xiàn)有簇或新簇Ci中;

⑦ 將〈t,i〉寫回數(shù)據(jù)集；

⑧ endfor

⑨ 選擇具有最大收益的Dm.

⑩ repeat

Fig. 2　Execution flow chart of p -CLOPE.圖2　p -CLOPE的執(zhí)行流程圖

2.5并行實現(xiàn)

p-CLOPE算法的每一輪迭代都先將輸入數(shù)據(jù)集劃分成p等份，然后排列成p!份新的數(shù)據(jù)集，分別對這些數(shù)據(jù)集聚類，再將該輪迭代的最優(yōu)聚類結(jié)果作為下一輪迭代的輸入，反復迭代，直至得到最優(yōu)的聚類劃分.在每一輪迭代中，由于對每一份數(shù)據(jù)集Di都要單獨執(zhí)行一系列運算，計算出一個聚類劃分，再比較對應的聚類劃分根據(jù)式(3)計算的收益值，找出收益值最大的聚類.因此我們將每一份數(shù)據(jù)集Di的計算放在不同的計算單元上獨立完成，而比較全局收益值的計算可以統(tǒng)一在一個計算單元上處理.這一過程完全可以先并行運算再全局比較大小，這為并行聚類的實現(xiàn)提供了可能性.

MapReduce是一種數(shù)據(jù)并行編程模型[11]，但它同時又能實現(xiàn)一定程度的共享變量和消息傳遞，因此與其他的并行計算模型(如MPI[12]，OpenMP[13]等)相比較，MapReduce具有非常大的優(yōu)勢.用MapReduce編程模型實現(xiàn)p-CLOPE算法的編程方法是：對不同數(shù)據(jù)集Di的聚類用不同的Map來完成，比較全局收益值用Reduce來完成.

我們在分布式基礎(chǔ)架構(gòu)Hadoop[11,14]上實現(xiàn)了p-CLOPE算法，使用HDFS存儲數(shù)據(jù)，使用Map -Reduce實現(xiàn)算法并行化.具體來說，首先將待聚類的數(shù)據(jù)集D以指定的文本格式上傳到HDFS，作為程序的輸入文件.根據(jù)輸入文件的大小將D劃分成p等份，再將這p等份數(shù)據(jù)塊排列生成p!份數(shù)據(jù)集{D1,D2,…,Dp!}.將每一份數(shù)據(jù)集Di分發(fā)到一個Map任務(wù)進行一次迭代的聚類操作，并將得到的聚類劃分以及根據(jù)式(3)計算得到的收益值等中間結(jié)果寫回HDFS.所有的Map任務(wù)結(jié)束后，通過一次Reduce過程，比較p!份數(shù)據(jù)集的聚類收益值，選出收益值最大的聚類結(jié)果數(shù)據(jù)集作為下一輪迭代的輸入.依此迭代，當最優(yōu)的聚類中所有的交易都沒有移動時，聚類過程結(jié)束.這樣得到的聚類劃分就是整個算法所要求的最優(yōu)聚類結(jié)果.執(zhí)行流程如圖2所示:

2.6時間與空間復雜度

CLOPE算法一次迭代的時間復雜度是O(N×K×A)，其中A是每條交易的平均長度，N是交易的條數(shù)，K是簇的個數(shù)[7].它的空間復雜度是O(M×K)，其中M是維度，K是簇的個數(shù).比如，對擁有10 000個維度和1 000個簇的數(shù)據(jù)集使用的內(nèi)存為40 MB[7]，由此可看出CLOPE算法具有非?？斓膱?zhí)行速度而且非常省內(nèi)存.p-CLOPE算法由于一次迭代需要計算p!份數(shù)據(jù)集，在單機單線程上運行時，采用每排列生成一份數(shù)據(jù)集就執(zhí)行一次的方式，p-CLOPE的一次迭代的時間復雜度是CLOPE算法一次迭代的p!倍，即為O(p!×N×K×A)，空間復雜度同CLOPE算法相當，但是由于p-CLOPE每次迭代后都選出最好的聚類結(jié)果，通常會比CLOPE算法在更少的迭代次數(shù)后就收斂了(即聚類結(jié)束).

在處理少量數(shù)據(jù)時，網(wǎng)絡(luò)通信代價比數(shù)據(jù)處理的計算代價大很多，運行在分布式平臺Hadoop上的p-CLOPE算法并沒有優(yōu)勢，甚至不如串行p-CLOPE.但是在處理大量數(shù)據(jù)時，并行p-CLOPE所花費的時間比串行p-CLOPE大大縮短，使用HDFS又能很好地實現(xiàn)大規(guī)模數(shù)據(jù)的存儲.

2.7加速比分析

加速比[15]是串行運行時間與并行運行時間的比率.p-CLOPE算法在每一輪的迭代中，串行時要依次處理p!份數(shù)據(jù)集，并行處理時這p!份數(shù)據(jù)集同時被處理，在Hadoop集群中每個任務(wù)處理一份數(shù)據(jù)集.

在定量分析加速比之前先簡單介紹Hadoop集群中的任務(wù)執(zhí)行機制.Hadoop(版本：1.xx系列)集群是MasterSlave架構(gòu)，包含一臺Master服務(wù)器和若干臺Slave服務(wù)器.Master服務(wù)器上運行的進程有NameNode，SecondaryNameNode和JobTracker；Slave服務(wù)器上運行的進程有DataNode和TaskTracker.TaskTracker需要設(shè)置(每個節(jié)點上)可運行的任務(wù)數(shù)的上限(默認是4).2類服務(wù)器上運行的進程也代表著它們的功能角色.JobTracker向TaskTracker下達啟動任務(wù)命令后，TaskTracker會為每個任務(wù)創(chuàng)建一個單獨的Java虛擬機(這是為了防止任務(wù)之間的干擾)，并有專門的線程監(jiān)控其資源的使用情況[16].

目前，計算機的CPU一般都是多核多線程(例如，Intel i7 CPU是4核8線程)，內(nèi)存也較大.我們假設(shè)每個TaskTracker上設(shè)置的任務(wù)數(shù)為T時，一個TaskTracker管理的所有任務(wù)不是以時間分片的方式交替使用CPU，而是擁有足夠的CPU和內(nèi)存等計算資源來并行執(zhí)行，此時所有的TaskTracker管理的所有任務(wù)也都可以并行執(zhí)行.如果集群中共有N臺TaskTracker，那么整個集群能夠運行的任務(wù)總數(shù)Total_Task如式(7)所示：

Total_Task=T×N.

(7)

當p!≤Total_Task時，所有的p!份數(shù)據(jù)集都可以并行計算，這時整個p-CLOPE算法可以完全并行運行，其加速比的理想值為p!.

當p!>Total_Task時，所有的p!份數(shù)據(jù)集不可能并行計算，必然會有先后之分.Hadoop集群會分批執(zhí)行任務(wù)，每批的任務(wù)數(shù)為Total_Task，所以分的批數(shù)B如式(8)所示：

(8)

可以推導出此時理想的加速比如式(9)所示：

(9)

從式(9)不難得出加速比的上限值是Total_Task.

當處理大量數(shù)據(jù)時，并行p-CLOPE具有顯著的優(yōu)勢.但如果此時集群的CPU和內(nèi)存等計算資源相對不夠，或者每個TaskTracker設(shè)置的任務(wù)數(shù)過大時，都會導致任務(wù)不能擁有足夠的CPU和內(nèi)存等計算資源來并行運行，進而不能達到理想的加速比.集群環(huán)境受到網(wǎng)絡(luò)和IO開銷的影響時，也不能達到理想的加速比.

對理想的加速比舉例說明如下：如果集群中的任務(wù)數(shù)為8，每個TaskTracker上設(shè)置的任務(wù)數(shù)為4時(CPU、內(nèi)存等計算資源足夠)，8個任務(wù)可以完全并行，這時整個集群中能同時運行的最多任務(wù)數(shù)為32.在這種環(huán)境的集群上用p-CLOPE算法對某個數(shù)據(jù)集進行聚類，當p=4時，p!=24，24<32，p-CLOPE算法可以完全并行，理想的加速比為24；當p=5時，p!=120，120>32，p-CLOPE算法不能完全并行，由式(9)計算得到理想的加速比為30；當p=6時，同理可以計算出理想的加速比為31.3.

3實驗與分析

由于本文最大的貢獻在于提出的p-CLOPE算法對CLOPE算法聚類質(zhì)量進行了提升，其次在于將p-CLOPE算法并行化，所以實驗主要對比p-CLOPE算法和CLOPE算法的聚類質(zhì)量.

這里采用CLOPE

算法提出的全局評估函數(shù)(見式(3))作為評價聚類結(jié)果的指標.全局收益值Profitr(C)越大，聚類劃分越優(yōu).實驗采用了3組數(shù)據(jù)集：組1是CLOPE算法測過的蘑菇數(shù)據(jù)集，屬性項數(shù)固定；組2是植物數(shù)據(jù)集，其屬性項數(shù)是不定的；組3是美國人口普查數(shù)據(jù)集，其屬性項數(shù)也是固定的.在組3百萬條數(shù)據(jù)級別的情況下，我們不僅比較了p-CLOPE與CLOPE的聚類質(zhì)量，還比較了CLOPE、串行p-CLOPE、并行p-CLOPE三者的執(zhí)行時間.

實驗所使用的CLOPE算法的實現(xiàn)程序來自于數(shù)據(jù)挖掘軟件Weka[17]中的版本(在實驗中標記為Weka-CLOPE)和我們實現(xiàn)的版本(在實驗中標記為CLOPE)，因為Weka軟件中實現(xiàn)的CLOPE算法實際上只用到了原CLOPE算法的初始化階段，并沒有完全按照文獻[7]提出的CLOPE算法來實現(xiàn)，而我們實現(xiàn)的CLOPE算法是完全按文獻[7]來實現(xiàn)的.實驗所用p-CLOPE算法有串行實現(xiàn)和在Hadoop上并行實現(xiàn)2個版本.Weka-CLOPE、CLOPE、串行p-CLOPE是在單機(8 GB的內(nèi)存、i7處理器的聯(lián)想PC機)上執(zhí)行的，并行p-CLOPE是在9臺這樣的機器搭建的Hadoop集群上執(zhí)行的.

3.1蘑菇數(shù)據(jù)集

蘑菇數(shù)據(jù)集(Mushroom)來自加州大學歐文分校機器學習庫①(UCI machine learning repository)，它被很多算法測試過[5]，也是原CLOPE算法測試過的數(shù)據(jù)集,該數(shù)據(jù)集有8 124條交易，每條交易有22個屬性，分可食用(edible)和有毒的(poisonous)2個類別，各有4 208和3 916條交易.所有的屬性項共有116個不同的值，2 480個缺失屬性值用問題號“?”表示.

以下分別用Weka-CLOPE，CLOPE，p-CLOPE進行聚類，用收益值Profitr(C)作為衡量聚類質(zhì)量的指標進行測試.進行比較時以CLOPE算法的收益值為基準線，Weka-CLOPE，p-CLOPE算法的收益值與之相比較.對p-CLOPE算法測試了參數(shù)p取不同值時的情況，每組對應的算法用p-CLOPEp來表示，用排斥因子作為X軸、用收益比值作為Y軸，實驗結(jié)果如圖3所示.

Fig. 3　Clustering results on Mushroom datasets.圖3　蘑菇數(shù)據(jù)集的實驗對比圖

實驗中排斥因子r取0.1～3.9，以0.2為步長；參數(shù)p取1～6，以1為步長.圖3中收益值比率為1的是CLOPE算法，以其作為基準線，Weka-CLOPE在CLOPE之下，p-CLOPE在CLOPE之上.因為Weka-CLOPE只實現(xiàn)了CLOPE算法的初始化階段，沒有繼續(xù)迭代以尋找更好的聚類結(jié)果，這樣做雖然節(jié)約了時間，但畢竟損失了精度，所以結(jié)果自然會差于CLOPE.p-CLOPE需要同時處理p!份數(shù)據(jù)集，由于p!增長太快，所以在實驗中p值最大只取到了6，這時并行計算的任務(wù)數(shù)為720個.當p=1時，p-CLOPE算法退化為CLOPE算法.從圖3中還可以看出，在排斥因子r一定時，隨著參數(shù)p的增大，p-CLOPE的收益值一般是越來越大，但是會存在一個上限，圖3中p-CLOPE取不同參數(shù)時曲線有一定程度的重合正好直觀地說明了這一點.

對大多數(shù)實際的數(shù)據(jù)集，r>1才有意義，否則2條沒有相同屬性項的交易會被放入同一個簇[7].在介紹CLOPE算法的文獻[7]中，當r=3.1時取得最好的聚類結(jié)果，而在我們的實驗中p-CLOPE 4在相同的r=3.1時取得了比CLOPE高35.7%的收益值.

3.2植物數(shù)據(jù)集

植物數(shù)據(jù)集(Plants)同樣來自加州大學歐文分校機器學習庫，是從美國農(nóng)業(yè)部的植物數(shù)據(jù)庫②中提取出來的，其中包含所有的植物種類以及每種植物在美國和加拿大的哪些州出現(xiàn)過的信息.總共的交易條數(shù)為34 781，每條交易由植物的拉丁名和出現(xiàn)過的州名的縮寫組成，這些州名可以看作是交易的屬性項，不超過70個.與蘑菇數(shù)據(jù)集的數(shù)據(jù)屬性項相比，植物數(shù)據(jù)集的每條交易的屬性項個數(shù)不一定相同(因為有的植物只在部分州出現(xiàn))，而且屬性項的位置也是任意的，與出現(xiàn)的順序無關(guān).

分別用Weka-CLOPE，CLOPE，p-CLOPE進行聚類，實驗結(jié)果如圖4所示.

Fig. 4　Clustering results on Plants datasets.圖4　植物數(shù)據(jù)集的實驗對比圖

從圖4可以看出，在絕大多數(shù)情況下，p-CLOPE算法的聚類質(zhì)量相比CLOPE算法有較大提升.

3.3美國人口普查數(shù)據(jù)集

美國人口普查數(shù)據(jù)集(US Census data set)同樣來自加州大學歐文分校機器學習庫，是從美國商務(wù)部人口普查局①獲取的，具體是從1990年美國人口普查全樣本數(shù)據(jù)中按1%的比例抽取的公共使用微數(shù)據(jù)樣本.總共交易條數(shù)為2 458 285，包括祖先、族群、拉美族裔來源、行業(yè)職業(yè)、語言、出生地等領(lǐng)域的68個屬性.與前2個數(shù)據(jù)集相比，這個數(shù)據(jù)集的交易條數(shù)達到百萬級別.

分別用Weka-CLOPE，CLOPE，p-CLOPE進行聚類，實驗結(jié)果如圖5所示：

Fig. 5　Clustering results on US Census datasets.圖5　美國人口普查數(shù)據(jù)集的實驗對比圖

從圖5可以看出，p-CLOPE算法的聚類質(zhì)量相比CLOPE算法都有提升，特別是當排斥因子取較大值時(這也是實際有意義的情況)，質(zhì)量有明顯的提升.

對這組百萬級的數(shù)據(jù)集，我們還比較了CLOPE、串行p-CLOPE、并行p-CLOPE三者的執(zhí)行時間.3個算法在劃分參數(shù)p=4時的執(zhí)行時間如圖6所示：

Fig. 6　The execution time of three algorithms.圖6　3個算法的執(zhí)行時間對比圖

從圖6可以看出，在大部分情況下，并行p-CLOPE算法的執(zhí)行時間比CLOPE算法短.原因在于雖然使用MapReduce并行方式實現(xiàn)時，p-CLOPE算法會有一定的網(wǎng)絡(luò)通信開銷，但是它會更快地收斂到最優(yōu)結(jié)果，因此迭代次數(shù)一般會比CLOPE算法少，這樣總的時間也會更短.并行p-CLOPE與串行p-CLOPE相比，執(zhí)行時間有大幅減少，從實驗數(shù)據(jù)計算得出的平均加速比為22.4.對本實驗中并行p-CLOPE算法的加速比分析如下：本實驗使用的Hadoop集群由9臺計算機組成，其中8臺計算機作為DataNode，每個TaskTracker的任務(wù)(task)數(shù)為4，所以整個集群可同時運行的任務(wù)數(shù)為32.由于每臺計算機的CPU配置都是4核8線程，內(nèi)存配置為8 GB，集群中的每個任務(wù)可以獲得超過1 GB的內(nèi)存和足夠的CPU資源.美國人口普查數(shù)據(jù)集的大小為345 MB(由2.6節(jié)的分析知，p-CLOPE算法非常節(jié)省內(nèi)存，實際上還不需要把整個數(shù)據(jù)集全部放入內(nèi)存)，所以集群的32個任務(wù)能夠獲得足夠的CPU和內(nèi)存等計算資源來并行執(zhí)行.本次實驗中p=4，p-CLOPE算法的每一次迭代中需要同時處理24份數(shù)據(jù)集，24<32.在這種情況下，這24份數(shù)據(jù)集完全可以并行處理，即p-CLOPE算法在當前情況下可以完全并行化，所以本次實驗獲得的加速比為22.4,接近p!，這與本文2.7節(jié)的理論分析是一致的.

4結(jié)論

本文深入研究了基于統(tǒng)計直方圖思想的分類數(shù)據(jù)聚類算法CLOPE，指出了該算法由于受輸入交易順序的影響而不能獲得最優(yōu)聚類劃分的問題.針對此缺陷，我們提出了一種基于等分劃分再排列思想的p-CLOPE算法進行改進.實驗表明，p-CLOPE算法能比CLOPE算法取得更優(yōu)的聚類結(jié)果.對蘑菇數(shù)據(jù)集在CLOPE算法取得最優(yōu)聚類結(jié)果時，p-CLOPE取得比CLOPE高35.7%的收益值.對大量數(shù)據(jù)集p-CLOPE算法也取得了比CLOPE算法更好的聚類質(zhì)量，同時并行p-CLOPE比串行p-CLOPE極大地縮短了聚類時間，取得了很好的加速比.我們在Hadoop平臺上用MapReduce并行編模型實現(xiàn)了一個包含p-CLOPE相關(guān)算法的聚類工具，已發(fā)布到開源社區(qū)①.

下一步的研究工作將結(jié)合權(quán)重對不同屬性項的影響繼續(xù)改進p-CLOPE算法，同時研究輸入交易的順序?qū)ζ渌垲愃惴ǖ挠绊?

參考文獻

[1]Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496

[2]Agresti A. Categorical Data Analysis[M]. New York: John Wiley & Sons, 2014

[3]Huang Z. A fast clustering algorithm to cluster very large categorical data sets in data mining[C]Proc of Workshop on Research Issues on Data Mining and Knowledge Discovery. New York: ACM, 1997

[4]Macqueen J. Some methods for classification and analysis of multivariate observations[C]Proc of the 5th Berkeley Symp on Mathematical Statistics and Probability. Berkeley, CA: University of California Press, 1967: 281-297

[5]Guha S, Rastogi R, Shim K. ROCK: A robust clustering algorithm for categorical attributes[C]Proc of the 15th Int Conf on Data Engineering (ICDE 1999). Los Alamitos, CA: IEEE Comuter Society, 1999: 512-521

[6]Wang K, Xu C, Liu B. Clustering transactions using large items[C]Proc of the 8th Int Conf on Information and Knowledge Management. New York: ACM, 1999: 483-490

[7]Yang Y, Guan X, You J. CLOPE: A fast and effective clustering algorithm for transactional data[C]Proc of the 8th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2002: 682-687

[8]Ong K L, Li W, Ng W K, et al. SCLOPE: An algorithm for clustering data streams of categorical attributes[G]LNCS 3181: Proc of the 6th Int Conf on Data Warehousing and Knowledge Discovery. Berlin: Springer, 2004: 209-218

[9]Yap P H, Ong K L.σ-SCLOPE: Clustering categorical streams using attribute selection[G]LNCS 3682: Proc of the 9th Int Conf on Knowledge-Based Intelligent Information and Engineering Systems, Part Ⅱ. Berlin: Springer, 2005: 929-935

[10]Li Jie, Gao Xinbo, Jiao Licheng. Fuzzy CLOPE algorithm and its parameter optimal choice[J]. Control and Decision, 2004, 19(11): 1250-1254 (in Chinese)(李潔, 高新波, 焦李成. 模糊 CLOPE 算法及其參數(shù)優(yōu)選[J]. 控制與決策, 2004, 19(11): 1250-1254)

[11]Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113

[12]Pacheco P S. Parallel Programming with MPI[M]. San Francisco, CA: Morgan Kaufmann, 1997

[13]Dagum L, Menon R. OpenMP: An industry standard API for shared-memory programming[J]. IEEE Computational Science & Engineering, 1998, 5(1): 46-55

[14]Shvachko K, Kuang H, Radia S, et al. The Hadoop distributed file system[C]Proc of the 26th IEEE Symp on Mass Storage Systems and Technologies (MSST). Piscataway, NJ: IEEE, 2010: 1-10

[15]Eager D L, Zahorjan J, Lazowska E D. Speedup versus efficiency in parallel systems[J]. IEEE Trans on Computers, 1989, 38(3): 408-423

[16]Dong Xicheng. Hadoop Internals: In-Depth Study of MapReduce[M]. Beijing: China Machine Press, 2013 (in Chinese)(董西成. Hadoop技術(shù)內(nèi)幕:深入解析MapReduce架構(gòu)設(shè)計與實現(xiàn)原理[M]. 北京: 機械工業(yè)出版社, 2013)

[17]Hall M, Frank E, Holmes G, et al. The WEKA data mining software: An update[J]. ACM SIGKDD Explorations Newsletter, 2009, 11(1): 10-18

Ding Xiangwu, born in 1963. PhD and associate professor. Member of China Computer Federation. His main research interests include database, column-stores, distributed processing, etc.

Guo Tao, born in 1988. Master. His research interests include big data and data mining (j2cms.org@gmail.com).

Wang Mei, born in 1980. PhD and professor. Her primary research interests include database, image semantic analysis, and information retrieval (wangmei@dhu.edu.cn).

Jin Ran, born in 1978. Associate professor, received PhD degree from College of Information Science and Technology, Donghua University in 2015. His main research interests include artificial intelli-gence, wire less sensor network, cloud com-puting and data mining (ran.jin@163.com).

A Clustering Algorithm for Large -Scale Categorical Data and Its Parallel Implementation

Ding Xiangwu1, Guo Tao1, Wang Mei1, and Jin Ran2

1(CollegeofComputerScienceandTechnology,DonghuaUniversity,Shanghai201620)2(FacultyofComputerScienceandInformationTechnology,ZhejingWanliUniversity,Ningbo,Zhejiang315100)

AbstractCLOPE algorithm has achieved good results in clustering large, sparse categorical datasets with high dimensions. However, it is hard to stably find the global optimal clusters since the data order can affect the result of clustering. To deal with this problem, this paper proposes p -CLOPE algorithm iteratively dividing input data into multiply equal parts and then clustering their different permutations. In each iteration of p -CLOPE algorithm, the input dataset is split into p parts and they are permuted into p! datasets with different part orders, then each dataset is clustered and the optimal clustering is chosen according to the profit as the input of next iterations. In order to handle time complexity of the process, a result reusing strategy is put forward that can improve the speed of clustering, further. Finaly, a distributed solution is put forward that implements p -CLOPE on Hadoop platform and a clustering tool is developed which has been released to the open source community. Experiments show that p -CLOPE can achieve better results than CLOPE. For the Mushroom dataset, when CLOPE achieves optimal results, p -CLOPE can achieve 35.7% higher profit value than CLOPE. When dealing with big data, parallel p -CLOPE greatly shortens the computing time compared with serial p -CLOPE, and it achieves nearly p! speedup when there is enough computing resource.

Key wordscategorical data; CLOPE; p -CLOPE; parallel clustering; MapReduce

收稿日期：2014-12-23；修回日期：2015-04-08

基金項目：國家自然科學基金項目(61103046)；上海市自然科學基金項目(11ZR1401200)

中圖法分類號TP312

This work was supported by the National Natural Science Foundation of China (61103046) and the Natural Science Foundation of Shanghai (11ZR1401200).