基于MapReduce的分治k均值聚類方法

臧艷輝，席運江，趙雪章

(1.佛山職業技術學院 電子信息學院，廣東 佛山 528137；2.華南理工大學 經濟管理學院，廣東 廣州 510000)

0 引 言

Hadoop的MapReduce框架是大數據處理的最理想的框架[1]。數據聚類是數據挖掘和處理過程中最重要的任務之一。其中，k均值算法應用最為廣泛，但其全局搜索能力較弱，隨機性使得聚類結果可能陷入局部最優，對簇密度不均的數據集處理效果和并行處理能力較差。

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

為了解決上述問題，提出了一種基于MapReduce的單通道分治k均值聚類方法。本研究創新點總結如下：

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

(2)分治k均值聚類法對最優k均值法解的近似結果為O(log2k)，對結果的最優性給出了強有力的界限。

(3)考慮到結果的速度和質量，分治k均值聚類法優于k均值法和改進的k均值法。當機器數量或數據量增加時，分治k均值聚類法擴展性更好。

1 原始k均值法和改進的k均值方法

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

(1)每個簇應至少分配一個數據項，即：?Ci∈C∶Ci≠?；

(2)每兩個不同的集群應該沒有共同的數據項，即：?Ci,Ci∈C∶Ci∩Cj=?。

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

(1)

在此定義的另一個屬性是群集的中心。群集的中心(質心)實際上是該群集中所有數據項的平均值。通常，為了在一組數據項上運行k均值法算法，能夠計算每兩對數據項之間的距離并計算一組數據項的中心是足夠的[12]?？梢允褂靡韵鹿接嬎闳杭闹行?質心)

(2)

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

算法1：k均值法

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

(3)repeat

(7)endprocedure

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

算法2：改進的k均值算法中心初始化

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

(7)endwhile

(9)endprocedure

2 提出的分治k均值聚類法

采取分治法處理大數據集，將整個數據集拆分為更小的塊，這些塊可以存儲在每臺機器的主存儲器中，通過可用的機器傳播，數據集的每個塊由其分配的機器獨立地聚類。塊能夠完全并行處理，從每個塊中提取一些中間中心，從塊中提取的中間中心集可以安裝到單個機器主存儲器中的更小數據集，并且從這個較小的集合中提取最終中心。

將整個過程安裝到MapRduce框架中，在映射階段處理塊，并且在縮減階段處理較小的中心集。其主要優勢是單通道，并且比基于MapReduce的k均值法實現能產生更準確的結果。為了解釋分治k均值聚類法，在不考慮Map-Reduce 的情況下解釋的分治法，解釋如何將解決方案安裝到MapReduce中。

2.1 分治法

為了定義分治法，首先需要定義應用于每個塊的算法和應用于中間中心集的最終算法。對于每個塊，應用改進的k均值法并提取k個中心。如果有c塊，在每個塊上應用改進的k均值法之后，將有一組k×c項作為中間集。為了更準確，也會為每個提取的中心保留分配的項目數。也就是說，從每個塊中提取k個中心和分配給每個中心的項目數。除了更高的準確性，保持中心的權重有助于證明分治k均值聚類法的最優性。

(3)

此外，改進的k均值法的選擇概率須更改為

(4)

將擬議的劃分和分治方法擬合到MapReduce框架中非常簡單。由于每個塊的處理獨立于其它塊，因此可以在專用映射任務中處理每個塊。即每個映射任務選擇一塊數據集并在該塊上執行改進的k均值法，然后將得到的k個中心及其權重作為輸出[14]。

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

2.2 接近誤差界

(5)

由于需要證明不依賴于數據集的分區方式，因此證據的直接且重要的結果是以下語句：“塊大小和數據集的順序對分治k均值聚類法的誤差界限沒有影響?！钡?，為了達到更好的質量，更小的塊尺寸更適合更大的塊尺寸。

2.3 調整塊大小

2.4 收斂性判定

對于任意數據對象而言，在聚類迭代的過程中，其數據對象均會被分配到離自己最近的簇中。隨著聚類質心的不斷調整，數據對象都將會越來越向著有利于自己的簇進行靠近，ε的值會趨近于一個固定值，當ε的值最終不變化時，算法最終達到最優聚類。但原始k均值法在每次迭代計算過程中并未指出，當算法收斂到某種程度時，就可以結束整個算法的迭代計算過程，并未將準則函數的值ε作為算法是否完成的判定標志。分治k均值法采用最小加權距離來重新確定數據點應該被分配的類簇，并以此來判斷算法的收斂性。

3 實驗結果與分析

為了評估分治k均值聚類法，對實際和合成數據集進行了詳細的實驗。將實驗分為兩個主要部分，在一臺機器上評估分治k均值聚類法并使用單個線程。在單機實驗期間，只使用實際的數據集，目標是評估分治k均值聚類法與標準k均值法及改進k均值法相比的準確性。因為大多數可用的現實世界數據集都不是很大，可以在一臺機器上輕松處理，所以使用一臺機器進行此實驗。

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

3.1 數據集

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

與現有的相關工作一樣，合成數據集是通過從5個維度的超立方體中隨機選擇k個中心來生成的，這些超立方體的邊長度為500，然后從標準差10的高斯分布中添加點，以每個中心為中心。因此，合成數據集包含一組分離良好的聚類，最佳中心是原始中心。合成數據集由NORM-X表示，其中X表示數據集中的項目數。

3.2 實驗設置

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

對于串行實驗，使用Apache Commons Math 3.2實現。對于連續實驗也嘗試了Weka和MATLAB，但兩者都比Apache Commons Math慢，無法處理像USCensus這樣的大型數據集。對于分布式實驗，使用Apache Mahout來基于MapReduce的k均值法實現，以及使用GraphLab來基于MPI的分布式改進的k均值法實現。

3.3 串行實驗

系列實驗的主要目標是將分治k均值聚類法與k均值法和改進的k均值法進行比較，對比結果見表1。對每個數據集用了3個不同數量的聚類：10、50、100。

表1 串行執行結果

如表1的結果所示，分治k均值聚類法聚類結果優于k均值，分治k均值聚類法比k均值法和k均值法++更快。對于在500次迭代之前未實現收斂的情況，削減執行。結果表明，改進的k均值法比k均值法收斂得更快，還得到具有更優的簇。由于數據集不是很大，因此對于每個數據集和簇編號，分治k均值聚類法的塊大小設置為10k。

表2 不同塊的數據集對分治k均值聚類法結果的影響

3.4 分布式實驗

分布式實驗主要目標是比較分治k均值聚類法與可用解決方案相比的速度及準確性。生成了4個由10 50 100和500個簇組成的大型合成數據集。每個數據集包含10億個項目。由于項目有5個特征，簇的標準差等于10，因此最優聚類的預期SSE在5×1011左右。

3.4.1 與ApacheMahout的比較

對Mahout的代碼進行些調整，使標準和改進的流式k均值法運行得更快。例如，對于k=100和k=500，改進的流式k均值法的原始版本在經過一段時間運行后崩潰，但在調整完成后，它成功完成了聚類。實驗細節見表3，最佳值用粗體表示。每個設置執行11次，并報告中值。

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

表3 與Mahout相比，分治k均值聚類法的質量和性能

案快幾倍。在所有數據集中，超過95%的執行時間用在映射階段，表明分治k均值聚類法是單通道，并且與標準k均值法的單次迭代一樣快。標準k均值法和分治k均值聚類法的執行時間通過簇數的增加而線性增加。改進的流式k均值法從每個塊中選擇k·logk項，與k均值法和分治k均值聚類法相比，它的增長是線性的，它們通過增加簇的數量線性增長?？紤]到分治k均值聚類法的質量將5×1011作為最佳聚類的預期SSE結果?？紤]到準確性，k均值法總是最差的。當k為10時，改進的流式k均值法和分治k均值聚類法具有大致相同的精度，對于10以上的簇數，分治k均值聚類法具有最佳精度。當群集數量增加時，改進的流式k均值法的準確性下降，作為改進的流式k均值法的構建塊的k均值算法在大量群集時執行不良，而分治k均值聚類法在具有大量聚類的數據集時結果更優。

3.4.2 與GraphLab的比較

通過GraphLab項目測試了改進的k均值法的分布式版本。GraphLab不使用MapReduce模型，而是使用消息傳遞接口(MPI)。為了執行改進的k均值法，GraphLab在可用機器之間平均分割數據集，并且每臺機器將其所有共享加載到主存儲器。當10億個項目數據集作為輸入時，并未被執行，因為數據集不在機器的主存儲器中。生成了一個較小的數據集，其中包含5個、50個、100個和500個集群的5億個項目。這些數據集的最佳SSE值為2.5×1011。

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

表4 提出的分治k均值聚類算法與基于GraphLab的分布式改進k均值法的比較

從表4可以看出，當最大迭代次數設置為10，最大迭代次數設置為100時，分治k均值聚類法比GraphLab的改進的k均值法更快。但與Mahout基于MapReduce的k均值相比，GraphLab的執行速度更快。GraphLab的速度背后有兩個主要原因。首先，GraphLab將數據集加載到主內存中，在每次迭代中，它不需要從磁盤重新加載數據集。其次，GraphLab是用C++語言編寫的，并使用MPI執行，MPI比使用Java語言編寫并通過Hadoop執行的Mahout快得多。將所有數據集加載到主存儲器中的要求是GraphLab分布式改進的k均值法解決方案的一個重要缺點，這使它無法處理非常大的數據集。

另一點是GraphLab的聚類結果的質量，考慮到結果的質量，預計GraphLab的改進的k均值法將勝過分治k均值聚類法，但當集群數量超過10時，分治k均值聚類法會生成更好的集群。因為原始數據集非常大，所以每個塊都是公平的子樣本，分治k均值聚類法在每個塊上獨立地應用改進的k均值法，分治k均值聚類法正在執行類似集合的方法。分治k均值聚類法的集合式方法使其更加穩定，因此，與改進的k均值法相比，k=10和k=500的SSE值之間的差異較小。

4 結束語

分治k均值聚類法是一種單通道和線性時間分布式數據聚類算法，其最優結果是O(log2k)。 實驗結果表明，分治k均值聚類法在速度和結果質量方面，均優于k均值法和改進的流式k均值法。但分治k均值聚類法計算開銷較大。

未來工作的方向是降低O(log2k) 的最優性界限，減少分治k均值聚類法的時間復雜度。另外還可以結合一些自動聚類方法，如貝葉斯信息準則(Bayesian information criterion，BIC)或Akaike信息準則(Akaike information criterion，AIC)，使分治k均值聚類法能夠自動預測聚類數量。