基于MapReduce的分治k均值聚類(lèi)方法

臧艷輝，席運(yùn)江，趙雪章

(1.佛山職業(yè)技術(shù)學(xué)院 電子信息學(xué)院，廣東 佛山 528137；2.華南理工大學(xué) 經(jīng)濟(jì)管理學(xué)院，廣東 廣州 510000)

0 引 言

Hadoop的MapReduce框架是大數(shù)據(jù)處理的最理想的框架[1]。數(shù)據(jù)聚類(lèi)是數(shù)據(jù)挖掘和處理過(guò)程中最重要的任務(wù)之一。其中，k均值算法應(yīng)用最為廣泛，但其全局搜索能力較弱，隨機(jī)性使得聚類(lèi)結(jié)果可能陷入局部最優(yōu)，對(duì)簇密度不均的數(shù)據(jù)集處理效果和并行處理能力較差。

針對(duì)k均值算法的不足，許多專(zhuān)家學(xué)者進(jìn)行研究。其中，文獻(xiàn)[2]對(duì)k均值算法在迭代計(jì)算過(guò)程中易產(chǎn)生內(nèi)存泄漏做了進(jìn)一步的優(yōu)化。文獻(xiàn)[3]采用多次隨機(jī)采樣的方式確定算法的k值，為聚類(lèi)中心點(diǎn)個(gè)數(shù)選擇提供了較好的解決方案。文獻(xiàn)[4]研究了一種比例均衡的聚類(lèi)算法，有效地提高類(lèi)簇的聚類(lèi)質(zhì)量。為了克服原始k均值算法在Hadoop平臺(tái)上需多次遍歷數(shù)據(jù)集的問(wèn)題，文獻(xiàn)[5]提出了一種基于初始聚類(lèi)中心點(diǎn)優(yōu)化的選擇算法，能夠一次遍歷所有數(shù)據(jù)集，減少了原算法的遍歷時(shí)間，算法的加速比得到了提高。文獻(xiàn)[6]提出了一種改進(jìn)流式k-means算法，對(duì)能夠克服隨機(jī)性導(dǎo)致的聚類(lèi)結(jié)果陷入局部最優(yōu)缺點(diǎn)，但其并行處理能力有待提高。

為了解決上述問(wèn)題，提出了一種基于MapReduce的單通道分治k均值聚類(lèi)方法。本研究創(chuàng)新點(diǎn)總結(jié)如下：

(1)所提方法減少了聚類(lèi)的時(shí)間和I/O的復(fù)雜性，設(shè)n為項(xiàng)目數(shù)，I為迭代次數(shù)，p為可用處理器數(shù)，則復(fù)雜度將由O(I·n/p) 降低為O(n/p)。

(2)分治k均值聚類(lèi)法對(duì)最優(yōu)k均值法解的近似結(jié)果為O(log2k)，對(duì)結(jié)果的最優(yōu)性給出了強(qiáng)有力的界限。

(3)考慮到結(jié)果的速度和質(zhì)量，分治k均值聚類(lèi)法優(yōu)于k均值法和改進(jìn)的k均值法。當(dāng)機(jī)器數(shù)量或數(shù)據(jù)量增加時(shí)，分治k均值聚類(lèi)法擴(kuò)展性更好。

1 原始k均值法和改進(jìn)的k均值方法

k均值法是一種非常經(jīng)典的聚類(lèi)算法[7-9]。許多研究者已經(jīng)為并行架構(gòu)提出了多個(gè)并行版本，而且為分布式系統(tǒng)提出了幾個(gè)版本，但是基于MapReduce提出的工作卻相對(duì)較少。在數(shù)據(jù)流聚類(lèi)領(lǐng)域有一些相關(guān)的工作，研究人員試圖在一次傳遞中聚集給定的數(shù)據(jù)集，還有研究者提出了幾種用于流式數(shù)據(jù)的k均值變體[10]。這些解決方案能夠在一次通過(guò)中聚集數(shù)據(jù)集，但它們都不具備固有的能力，可以在分布式系統(tǒng)中執(zhí)行，尤其是MapReduce框架。

(1)每個(gè)簇應(yīng)至少分配一個(gè)數(shù)據(jù)項(xiàng)，即：?Ci∈C∶Ci≠?；

(2)每?jī)蓚€(gè)不同的集群應(yīng)該沒(méi)有共同的數(shù)據(jù)項(xiàng)，即：?Ci,Ci∈C∶Ci∩Cj=?。

這些約束意味著硬分區(qū)和分區(qū)聚類(lèi)。分配給群集的數(shù)據(jù)項(xiàng)應(yīng)盡可能相似。因此，也應(yīng)該定義相似性度量。使用最廣泛的相似性度量是歐幾里德距離的倒數(shù)[11]。任何兩個(gè)d維數(shù)據(jù)項(xiàng)之間的歐氏距離可以使用以下等式計(jì)算

(1)

在此定義的另一個(gè)屬性是群集的中心。群集的中心(質(zhì)心)實(shí)際上是該群集中所有數(shù)據(jù)項(xiàng)的平均值。通常，為了在一組數(shù)據(jù)項(xiàng)上運(yùn)行k均值法算法，能夠計(jì)算每?jī)蓪?duì)數(shù)據(jù)項(xiàng)之間的距離并計(jì)算一組數(shù)據(jù)項(xiàng)的中心是足夠的[12]?？梢允褂靡韵鹿接?jì)算群集的中心(質(zhì)心)

(2)

在討論分治k均值聚類(lèi)法之前，有必要定義k均值法和改進(jìn)的k均值法的原理。k均值法是一種簡(jiǎn)單而快速但有效的聚類(lèi)算法[13]。算法1給出了具體程序。

算法1：k均值法

(1)procedurek-MEANS (M,k) ?returns k centers

(3)repeat

(7)endprocedure

理論上，重復(fù)k均值法的主循環(huán)，直到中心集合收斂并且沒(méi)有變化。此過(guò)程也稱(chēng)為勞埃德算法。然而，在實(shí)踐中較滿意的結(jié)果可能需要多次迭代才能得到。因此，k均值法的主循環(huán)通常被限制為固定數(shù)。文獻(xiàn)[11]提出了一種改進(jìn)的k均值法，對(duì)k中心的初始化選擇一組精心挑選的初始中心而不是隨機(jī)初始化。如果假設(shè)D’(x) 是數(shù)據(jù)項(xiàng)x到已經(jīng)選擇的最近中心的距離，則改進(jìn)的k均值法的初始化步驟可以定義為算法2。在其余部分，使用n作為數(shù)字?jǐn)?shù)據(jù)集中的數(shù)據(jù)項(xiàng)，d表示每個(gè)數(shù)據(jù)項(xiàng)的大小(維度計(jì)數(shù))，k表示簇的數(shù)量。

算法2：改進(jìn)的k均值算法中心初始化

(1)procedureimprovedk-Means (M,k) returns k centers as the initial seed

(7)endwhile

(9)endprocedure

2 提出的分治k均值聚類(lèi)法

采取分治法處理大數(shù)據(jù)集，將整個(gè)數(shù)據(jù)集拆分為更小的塊，這些塊可以存儲(chǔ)在每臺(tái)機(jī)器的主存儲(chǔ)器中，通過(guò)可用的機(jī)器傳播，數(shù)據(jù)集的每個(gè)塊由其分配的機(jī)器獨(dú)立地聚類(lèi)。塊能夠完全并行處理，從每個(gè)塊中提取一些中間中心，從塊中提取的中間中心集可以安裝到單個(gè)機(jī)器主存儲(chǔ)器中的更小數(shù)據(jù)集，并且從這個(gè)較小的集合中提取最終中心。

將整個(gè)過(guò)程安裝到MapRduce框架中，在映射階段處理塊，并且在縮減階段處理較小的中心集。其主要優(yōu)勢(shì)是單通道，并且比基于MapReduce的k均值法實(shí)現(xiàn)能產(chǎn)生更準(zhǔn)確的結(jié)果。為了解釋分治k均值聚類(lèi)法，在不考慮Map-Reduce 的情況下解釋的分治法，解釋如何將解決方案安裝到MapReduce中。

2.1 分治法

為了定義分治法，首先需要定義應(yīng)用于每個(gè)塊的算法和應(yīng)用于中間中心集的最終算法。對(duì)于每個(gè)塊，應(yīng)用改進(jìn)的k均值法并提取k個(gè)中心。如果有c塊，在每個(gè)塊上應(yīng)用改進(jìn)的k均值法之后，將有一組k×c項(xiàng)作為中間集。為了更準(zhǔn)確，也會(huì)為每個(gè)提取的中心保留分配的項(xiàng)目數(shù)。也就是說(shuō)，從每個(gè)塊中提取k個(gè)中心和分配給每個(gè)中心的項(xiàng)目數(shù)。除了更高的準(zhǔn)確性，保持中心的權(quán)重有助于證明分治k均值聚類(lèi)法的最優(yōu)性。

(3)

此外，改進(jìn)的k均值法的選擇概率須更改為

(4)

將擬議的劃分和分治方法擬合到MapReduce框架中非常簡(jiǎn)單。由于每個(gè)塊的處理獨(dú)立于其它塊，因此可以在專(zhuān)用映射任務(wù)中處理每個(gè)塊。即每個(gè)映射任務(wù)選擇一塊數(shù)據(jù)集并在該塊上執(zhí)行改進(jìn)的k均值法，然后將得到的k個(gè)中心及其權(quán)重作為輸出[14]。

在映射階段完成之后，形成一組中間加權(quán)中心作為映射階段的輸出，并且該組中心被給予單個(gè)減少任務(wù)，并獲取一組中心數(shù)據(jù)及其權(quán)重，然后執(zhí)行最終改進(jìn)的k均值法，并返回最終中心作為輸出。

2.2 接近誤差界

(5)

由于需要證明不依賴(lài)于數(shù)據(jù)集的分區(qū)方式，因此證據(jù)的直接且重要的結(jié)果是以下語(yǔ)句：“塊大小和數(shù)據(jù)集的順序?qū)Ψ种蝛均值聚類(lèi)法的誤差界限沒(méi)有影響?！钡?，為了達(dá)到更好的質(zhì)量，更小的塊尺寸更適合更大的塊尺寸。

2.3 調(diào)整塊大小

2.4 收斂性判定

對(duì)于任意數(shù)據(jù)對(duì)象而言，在聚類(lèi)迭代的過(guò)程中，其數(shù)據(jù)對(duì)象均會(huì)被分配到離自己最近的簇中。隨著聚類(lèi)質(zhì)心的不斷調(diào)整，數(shù)據(jù)對(duì)象都將會(huì)越來(lái)越向著有利于自己的簇進(jìn)行靠近，ε的值會(huì)趨近于一個(gè)固定值，當(dāng)ε的值最終不變化時(shí)，算法最終達(dá)到最優(yōu)聚類(lèi)。但原始k均值法在每次迭代計(jì)算過(guò)程中并未指出，當(dāng)算法收斂到某種程度時(shí)，就可以結(jié)束整個(gè)算法的迭代計(jì)算過(guò)程，并未將準(zhǔn)則函數(shù)的值ε作為算法是否完成的判定標(biāo)志。分治k均值法采用最小加權(quán)距離來(lái)重新確定數(shù)據(jù)點(diǎn)應(yīng)該被分配的類(lèi)簇，并以此來(lái)判斷算法的收斂性。

3 實(shí)驗(yàn)結(jié)果與分析

為了評(píng)估分治k均值聚類(lèi)法，對(duì)實(shí)際和合成數(shù)據(jù)集進(jìn)行了詳細(xì)的實(shí)驗(yàn)。將實(shí)驗(yàn)分為兩個(gè)主要部分，在一臺(tái)機(jī)器上評(píng)估分治k均值聚類(lèi)法并使用單個(gè)線程。在單機(jī)實(shí)驗(yàn)期間，只使用實(shí)際的數(shù)據(jù)集，目標(biāo)是評(píng)估分治k均值聚類(lèi)法與標(biāo)準(zhǔn)k均值法及改進(jìn)k均值法相比的準(zhǔn)確性。因?yàn)榇蠖鄶?shù)可用的現(xiàn)實(shí)世界數(shù)據(jù)集都不是很大，可以在一臺(tái)機(jī)器上輕松處理，所以使用一臺(tái)機(jī)器進(jìn)行此實(shí)驗(yàn)。

使用Hadoop框架進(jìn)行了一系列分布式實(shí)驗(yàn)，在分布式實(shí)驗(yàn)中，使用了龐大的合成數(shù)據(jù)集，目標(biāo)是將分治k均值聚類(lèi)法的性能和準(zhǔn)確性與可用的k均值法變體進(jìn)行比較。實(shí)際表明盡管分治k均值聚類(lèi)法的最壞情況誤差界限相比于改進(jìn)的流式k均值法更寬松，但實(shí)際上它產(chǎn)生了更好的聚類(lèi)解決方案。

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

為了評(píng)估分治k均值聚類(lèi)法的性能，使用了一組合成數(shù)據(jù)集和4個(gè)真實(shí)數(shù)據(jù)集。使用的4個(gè)真實(shí)數(shù)據(jù)集是：“美國(guó)人口普查數(shù)據(jù)(US census data)”，也稱(chēng)為“US Census”；“KDDCUP04生物數(shù)據(jù)集(KDDCUP04 biology dataset)”又名“KDD04”；“撲克手?jǐn)?shù)據(jù)(Poker hand data)”又稱(chēng)“撲克(Poker)”；“皮膚分割(Skin segmentation)”又名“皮膚(Skin)”；以及“Birch算法的數(shù)據(jù)集(the Birch algorithm’s dataset)”，又名“Birch”。所有數(shù)據(jù)集都可通過(guò)UCI機(jī)器學(xué)習(xí)庫(kù)獲得。

與現(xiàn)有的相關(guān)工作一樣，合成數(shù)據(jù)集是通過(guò)從5個(gè)維度的超立方體中隨機(jī)選擇k個(gè)中心來(lái)生成的，這些超立方體的邊長(zhǎng)度為500，然后從標(biāo)準(zhǔn)差10的高斯分布中添加點(diǎn)，以每個(gè)中心為中心。因此，合成數(shù)據(jù)集包含一組分離良好的聚類(lèi)，最佳中心是原始中心。合成數(shù)據(jù)集由NORM-X表示，其中X表示數(shù)據(jù)集中的項(xiàng)目數(shù)。

3.2 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用40臺(tái)機(jī)器的私有云，每臺(tái)機(jī)器都有一個(gè)2核2.4 GHz Xeon CPU和12 GB RAM。所有機(jī)器均安裝Ubuntu Linux12.04和OpenJDK7，Apache Hadoop1.2和Mahout0.8也安裝在MapReduce框架中。分布式實(shí)驗(yàn)在40臺(tái)機(jī)器上完成，而串行實(shí)驗(yàn)在具有3.4 GHz i7 CPU和 8 GB RAM的單臺(tái)機(jī)器上執(zhí)行。

對(duì)于串行實(shí)驗(yàn)，使用Apache Commons Math 3.2實(shí)現(xiàn)。對(duì)于連續(xù)實(shí)驗(yàn)也嘗試了Weka和MATLAB，但兩者都比Apache Commons Math慢，無(wú)法處理像USCensus這樣的大型數(shù)據(jù)集。對(duì)于分布式實(shí)驗(yàn)，使用Apache Mahout來(lái)基于MapReduce的k均值法實(shí)現(xiàn)，以及使用GraphLab來(lái)基于MPI的分布式改進(jìn)的k均值法實(shí)現(xiàn)。

3.3 串行實(shí)驗(yàn)

系列實(shí)驗(yàn)的主要目標(biāo)是將分治k均值聚類(lèi)法與k均值法和改進(jìn)的k均值法進(jìn)行比較，對(duì)比結(jié)果見(jiàn)表1。對(duì)每個(gè)數(shù)據(jù)集用了3個(gè)不同數(shù)量的聚類(lèi)：10、50、100。

表1 串行執(zhí)行結(jié)果

如表1的結(jié)果所示，分治k均值聚類(lèi)法聚類(lèi)結(jié)果優(yōu)于k均值，分治k均值聚類(lèi)法比k均值法和k均值法++更快。對(duì)于在500次迭代之前未實(shí)現(xiàn)收斂的情況，削減執(zhí)行。結(jié)果表明，改進(jìn)的k均值法比k均值法收斂得更快，還得到具有更優(yōu)的簇。由于數(shù)據(jù)集不是很大，因此對(duì)于每個(gè)數(shù)據(jù)集和簇編號(hào)，分治k均值聚類(lèi)法的塊大小設(shè)置為10k。

表2 不同塊的數(shù)據(jù)集對(duì)分治k均值聚類(lèi)法結(jié)果的影響

3.4 分布式實(shí)驗(yàn)

分布式實(shí)驗(yàn)主要目標(biāo)是比較分治k均值聚類(lèi)法與可用解決方案相比的速度及準(zhǔn)確性。生成了4個(gè)由10 50 100和500個(gè)簇組成的大型合成數(shù)據(jù)集。每個(gè)數(shù)據(jù)集包含10億個(gè)項(xiàng)目。由于項(xiàng)目有5個(gè)特征，簇的標(biāo)準(zhǔn)差等于10，因此最優(yōu)聚類(lèi)的預(yù)期SSE在5×1011左右。

3.4.1 與ApacheMahout的比較

對(duì)Mahout的代碼進(jìn)行些調(diào)整，使標(biāo)準(zhǔn)和改進(jìn)的流式k均值法運(yùn)行得更快。例如，對(duì)于k=100和k=500，改進(jìn)的流式k均值法的原始版本在經(jīng)過(guò)一段時(shí)間運(yùn)行后崩潰，但在調(diào)整完成后，它成功完成了聚類(lèi)。實(shí)驗(yàn)細(xì)節(jié)見(jiàn)表3，最佳值用粗體表示。每個(gè)設(shè)置執(zhí)行11次，并報(bào)告中值。

從表3可以看出，分治k均值聚類(lèi)法總是比其它解決方

表3 與Mahout相比，分治k均值聚類(lèi)法的質(zhì)量和性能

案快幾倍。在所有數(shù)據(jù)集中，超過(guò)95%的執(zhí)行時(shí)間用在映射階段，表明分治k均值聚類(lèi)法是單通道，并且與標(biāo)準(zhǔn)k均值法的單次迭代一樣快。標(biāo)準(zhǔn)k均值法和分治k均值聚類(lèi)法的執(zhí)行時(shí)間通過(guò)簇?cái)?shù)的增加而線性增加。改進(jìn)的流式k均值法從每個(gè)塊中選擇k·logk項(xiàng)，與k均值法和分治k均值聚類(lèi)法相比，它的增長(zhǎng)是線性的，它們通過(guò)增加簇的數(shù)量線性增長(zhǎng)?？紤]到分治k均值聚類(lèi)法的質(zhì)量將5×1011作為最佳聚類(lèi)的預(yù)期SSE結(jié)果。考慮到準(zhǔn)確性，k均值法總是最差的。當(dāng)k為10時(shí)，改進(jìn)的流式k均值法和分治k均值聚類(lèi)法具有大致相同的精度，對(duì)于10以上的簇?cái)?shù)，分治k均值聚類(lèi)法具有最佳精度。當(dāng)群集數(shù)量增加時(shí)，改進(jìn)的流式k均值法的準(zhǔn)確性下降，作為改進(jìn)的流式k均值法的構(gòu)建塊的k均值算法在大量群集時(shí)執(zhí)行不良，而分治k均值聚類(lèi)法在具有大量聚類(lèi)的數(shù)據(jù)集時(shí)結(jié)果更優(yōu)。

3.4.2 與GraphLab的比較

通過(guò)GraphLab項(xiàng)目測(cè)試了改進(jìn)的k均值法的分布式版本。GraphLab不使用MapReduce模型，而是使用消息傳遞接口(MPI)。為了執(zhí)行改進(jìn)的k均值法，GraphLab在可用機(jī)器之間平均分割數(shù)據(jù)集，并且每臺(tái)機(jī)器將其所有共享加載到主存儲(chǔ)器。當(dāng)10億個(gè)項(xiàng)目數(shù)據(jù)集作為輸入時(shí)，并未被執(zhí)行，因?yàn)閿?shù)據(jù)集不在機(jī)器的主存儲(chǔ)器中。生成了一個(gè)較小的數(shù)據(jù)集，其中包含5個(gè)、50個(gè)、100個(gè)和500個(gè)集群的5億個(gè)項(xiàng)目。這些數(shù)據(jù)集的最佳SSE值為2.5×1011。

在5億個(gè)項(xiàng)目數(shù)據(jù)集上應(yīng)用了GraphLab的改進(jìn)k均值法和分治k均值聚類(lèi)法，結(jié)果在表4中給出，最佳值用粗體表示。為了進(jìn)一步比較，將改進(jìn)的k均值法的最大迭代次數(shù)設(shè)置為10，將GraphLab設(shè)置為100。結(jié)果表明，在10到100次迭代之間存在非常小的差異(低于1%)。也就是說(shuō)，10次迭代對(duì)于k均值就足夠了，SSE沒(méi)有相當(dāng)大的改進(jìn)。另一方面，與10次迭代相比，100次迭代至少需要5次。

表4 提出的分治k均值聚類(lèi)算法與基于GraphLab的分布式改進(jìn)k均值法的比較

從表4可以看出，當(dāng)最大迭代次數(shù)設(shè)置為10，最大迭代次數(shù)設(shè)置為100時(shí)，分治k均值聚類(lèi)法比GraphLab的改進(jìn)的k均值法更快。但與Mahout基于MapReduce的k均值相比，GraphLab的執(zhí)行速度更快。GraphLab的速度背后有兩個(gè)主要原因。首先，GraphLab將數(shù)據(jù)集加載到主內(nèi)存中，在每次迭代中，它不需要從磁盤(pán)重新加載數(shù)據(jù)集。其次，GraphLab是用C++語(yǔ)言編寫(xiě)的，并使用MPI執(zhí)行，MPI比使用Java語(yǔ)言編寫(xiě)并通過(guò)Hadoop執(zhí)行的Mahout快得多。將所有數(shù)據(jù)集加載到主存儲(chǔ)器中的要求是GraphLab分布式改進(jìn)的k均值法解決方案的一個(gè)重要缺點(diǎn)，這使它無(wú)法處理非常大的數(shù)據(jù)集。

另一點(diǎn)是GraphLab的聚類(lèi)結(jié)果的質(zhì)量，考慮到結(jié)果的質(zhì)量，預(yù)計(jì)GraphLab的改進(jìn)的k均值法將勝過(guò)分治k均值聚類(lèi)法，但當(dāng)集群數(shù)量超過(guò)10時(shí)，分治k均值聚類(lèi)法會(huì)生成更好的集群。因?yàn)樵紨?shù)據(jù)集非常大，所以每個(gè)塊都是公平的子樣本，分治k均值聚類(lèi)法在每個(gè)塊上獨(dú)立地應(yīng)用改進(jìn)的k均值法，分治k均值聚類(lèi)法正在執(zhí)行類(lèi)似集合的方法。分治k均值聚類(lèi)法的集合式方法使其更加穩(wěn)定，因此，與改進(jìn)的k均值法相比，k=10和k=500的SSE值之間的差異較小。

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

分治k均值聚類(lèi)法是一種單通道和線性時(shí)間分布式數(shù)據(jù)聚類(lèi)算法，其最優(yōu)結(jié)果是O(log2k)。 實(shí)驗(yàn)結(jié)果表明，分治k均值聚類(lèi)法在速度和結(jié)果質(zhì)量方面，均優(yōu)于k均值法和改進(jìn)的流式k均值法。但分治k均值聚類(lèi)法計(jì)算開(kāi)銷(xiāo)較大。

未來(lái)工作的方向是降低O(log2k) 的最優(yōu)性界限，減少分治k均值聚類(lèi)法的時(shí)間復(fù)雜度。另外還可以結(jié)合一些自動(dòng)聚類(lèi)方法，如貝葉斯信息準(zhǔn)則(Bayesian information criterion，BIC)或Akaike信息準(zhǔn)則(Akaike information criterion，AIC)，使分治k均值聚類(lèi)法能夠自動(dòng)預(yù)測(cè)聚類(lèi)數(shù)量。