基于抽樣和最大最小距離法的并行K-means聚類算法

劉 燕

(山西大學 商務學院， 太原 030031)

引言

聚類是將物理或抽象的對象分成相似對象集合的過程，簇是數據對象的集合，同一簇中的對象特征相似，而與其它簇中的對象卻彼此相異[1]。聚類分析在數據挖掘、模式識別、文本分析、圖形處理、市場研究等諸多領域應用廣泛。作為一種獲得廣泛應用的經典聚類劃分算法，K-means算法具有算法數學思想清晰且易于實現、收斂速度快等優勢[2]，但是需要事先指定初始聚類中心的個數k值，而且由于中心點選取的隨機性而容易陷入局部最優解。

隨著數據庫和網絡技術的快速發展，生成的數據呈海量增長，傳統的聚類算法很難滿足時下的數據分析處理需求。2004年，Google公司研發了一個稱為Hadoop的開源MapReduce并行計算框架和系統，給大數據并行處理帶來了重大的影響，現已成為迄今為止易于使用、廣為接受的業界主流大數據并行處理技術。因此，許多學者運用MapReduce模型陸續展開了有關海量數據的聚類研究。江小平等人[3]提出了一種基于MapReduce的并行K-means聚類算法，該算法的執行效率較高，但由于K-means算法在收斂前需要進行多次迭代計算，不斷地重啟計算任務及讀取原始數據集，因此造成更多的I/O開銷。毛典輝[4]提出的基于MapReduce的Canopy-Kmeans改進算法，采用最大最小原則對該算法進行改進。虞倩倩等人[5]提出了基于MapReduce的ACO-Kmeans并行聚類算法，針對K-means聚類算法處理海量數據時存在的內存不足等問題，研究了利用MapReduce實現K-means聚類算法的并行化。

綜上這些算法很好地解決了傳統K-means算法處理海量數據的一些不足，但是仍存在聚類效果不穩定、準確率不高，也未能充分考慮算法執行過程中的計算量以及通信代價等問題。為此，本文擬基于MapReduce模型，采用抽樣技術和最大最小距離法，設計提出一種高效的并行K-means算法。通過在UCI標準數據集地行實驗，最終結果表明該算法的收斂速度、聚類精度，以及在處理海量數據時的并行性能都得到了提高。

1 相關理論

1.1 傳統的K-means聚類算法

設數據集X={x1,x2,…,xn}，其中xi表示一個數據對象，通常采用歐式距離作為判斷2個數據對象之間相似性的依據。任意2個數據對象間的歐式距離為：

(1)

其中，m為數據集的屬性維數，xir，xjr為數據對象xi和xj的第r個屬性值。距離越小相似性越大，相反則相似性越小。

傳統K-means算法的設計流程可描述如下[6]。

(1)針對數據集X={x1,x2,…,xn}，指定聚類個數為k，并隨機選取k個數據對象作為初始聚類中心{c1,c2,…,ck}。

(2)根據公式(1)計算每個數據對象xi到k個聚類中心的歐式距離，并把數據對象xi劃分到與之距離最近的聚類中心所屬的聚類中。

(3)計算每一個類簇中所有數據對象的平均值作為新的聚類中心。

(4)重復執行步驟(2)和步驟(3)進行下一輪聚類，直到各個聚類中心在某個精度范圍內不再變化或者達到最大迭代次數為止，算法結束。

1.2 隨機抽樣

在統計學中，簡單隨機采樣是各類抽樣方法的基礎，但在大規模的抽樣調查中卻很少被單獨采用，而在數據挖掘技術中，因其呈現的總體確定性，這一限制也隨即被消除。

由統計學的大數定律、中心極限定律、貝努利大數定律等可得到如下結論[7]，不論總體服從何種分布，只要其數學期望和方差存在，從中抽取容量為n的樣本，這個樣本的和或平均數將作為隨機變量，當n充分大時，趨于正態分布，則可得隨機抽樣樣本容量n的數學公式為：

(2)

其中，N為數據集總量；t為概率度；δ為標準差；ε為誤差限制。通常，隨機采樣時采用置信度為0.95，概率度為1.96。

1.3 最大最小距離法

最大最小距離法以歐式距離為基礎，采取以最大距離原則選取新的聚類中心，以最小距離原則進行模式歸類。因此避免了K-means算法初值選取時可能出現的聚類中心過于鄰近的情況[8]，而且可以智能確定初始聚類中心的個數，提高了劃分初始數據集的效率。算法運行各步驟可詳述如下。

(1)有n個對象，Sn={X1,X2,…,Xn}。

(2)任取一個數據對象，例如X1，作為第一個聚類中心，然后找出集合Sn中到第一個聚類中心距離最遠的數據對象作為第二個聚類中心。

(3)對Sn中剩余的其它數據對象Xi，分別計算到第一個、第二個聚類中心的距離，令其中較小的為DXi。

(4)計算maxSn={DXi}。若maxSn={DXi}>m×[average(|X2-X1|)]，則取Xi為新的聚類中心。通常取值為m∈[1/2，1)。

(5)重復執行步驟(1)～(4)，直到不產生新的聚類中心為止。

2 基于抽樣和最大最小距離法的并行K-means聚類算法

本算法首先采用抽樣技術對原始數據集進行多次隨機抽樣，以產生新的數據集；然后運用MapReduce模型，2次采用最大最小距離法生成最佳的初始聚類中心；最后基于MapReduce模型利用K-means算法進行迭代聚類。算法的執行過程可表述如下。

輸入：原始數據集D和聚類數目k，采樣次數J

(1)計算原始數據集D的平均值和方差，并根據公式(2)確定抽樣樣本量。

(2)對原始數據集D進行J次隨機抽樣。

(3)初始聚類中心運算

① Map1階段：對每個抽樣樣本運用最大最小距離法生成若干的初始聚類中心集合。

② Reduce1階段：將這些初始聚類中心集合匯總后再次運用最大最小距離法，從而得到最佳的k個初始聚類中心。

(4)新的聚類中心運算

① Map2階段：計算每個初始聚類中心的歐式距離并重新標記所屬類別。

② Reduce2階段：依據中間結果再次計算新的聚類中心。

(5)經過多次迭代計算，直至收斂，從而得到最終的聚類結果。

3 實驗結果與分析

實驗選用Hadoop集群平臺由一個master節點和9個slavers節點組成。實驗運用的數據集均來自UCI數據庫，各數據集信息可詳見表1。通過一系列實驗，測試這些數據集在Hadoop集群環境下本文算法和基于MapReduce的K-means并行算法[3]的收斂速度、聚類精度及其并行性能。對此，將給出研究論述如下。

表1 實驗數據集

(1)收斂速度的對比分析。研究中，為了保證仿真實驗結果的客觀性，則將2種算法各重復運行10次，測試每種算法的收斂速度，即各自完成聚類所需要的迭代次數，對比結果可見表2。

表2 收斂速度對比

從表2中可以看出，本文算法的聚類收斂速度與基于MapReduce的K-means并行算法相比要更快一些。究其原因就在于本文算法運用了最大最小距離法對初值選取進行了優化，K-means聚類過程對初始聚類中心的依賴性有所減小，從而使得該算法聚類時所需要的迭代次數明顯減少，收斂速度加快。

(2)聚類精度的對比分析。聚類精度是指數據對象被置于正確的類簇中的數據個數與總的數據對象個數的比值。2種算法的聚類精度對比結果可見表3。從表3中可以看出，本文算法的聚類精度要高于基于MapReduce的K-means并行算法，這也說明本文算法對含噪聲數據以及分布異常數據的處理能力有所提升，聚類質量也更高。

表3 聚類精度對比

(3)并行性能的對比分析。加速比是同一個任務在單處理器系統和并行處理器系統中運行消耗的時間的比率，用來衡量并行系統或程序并行化的性能和效果[9]。計算公式為：

Sp=T1/Tp

(3)

其中，T1表示順序執行算法(即單一PC機)的執行時間，Tp表示并行算法(即p個處理器)的執行時間。加速比越大，說明并行計算消耗的相對時間越少，并行效率越高。

通過對數據集1990 US Census Data擴充為2倍、4倍、8倍不同大小的數據集，分別在不同節點數的Hadoop集群平臺下運行本文算法，由此得出加速比的并行性能對比結果。

在Hadoop集群平臺下，本文算法的加速比則如圖1所示。可以看到，隨著節點數增加和數據量增大，加速比也呈現提升態勢。由此分析可得，在處理海量高維數據集時，單機由于內存不足將無法運行，而集群則能有效提高算法的計算效率，并行性能堪稱優良。

圖1 Hadoop集群平臺的加速比

4 結束語

針對傳統聚類算法處理海量數據的一些問題與不足，本文將基于MapReduce模型，采用抽樣技術和最大最小距離法，設計提出一種高效的并行K-means算法。通過在UCI標準數據集進行實驗，結果表明該算法的收斂速度、聚類精度，以及在處理海量數據時的并行性能均在一定程度上獲得了提升。未來將會在更多的大數據集上展開測試，包括高維數據，從而進一步驗證算法的性能并提供后續的改進與完善。