基于聚類算法的并行化研究

摘要:聚類是數據挖掘中重要組成部分，為了提高聚類的處理效率，將并行處理技術運用于k-means和PAM算法中，對k-means與PAM算法進行了改進。實驗結果表明:并行k-means算法相對串行k-means算法有更好的執行效率;且k-means算法有比PAM算法更好的并行性和可擴展性。最后，該文提出和介紹了將并行技術引入譜聚類算法。

關鍵詞:聚類算法;并行;K-means;PAM

中圖分類號:TP391文獻標識碼:A文章編號:1009-3044(2009)24-7010-03

Research on Parallelizing Based on Clustering Algorithm

PENG Hou-wen， YANG Shuang， HE Feng-cheng

(Dalian University of TechnologyNational Exemplary Software School， Dalian 116620， China)

Abstract: Cluster analysis is an important component of data mining， aiming at improving the executive efficiency of clustering. In this paper， a method of parallel operating is applied to k-means algorithm and PAM algorithm， in order to improve these two algorithms. Experiments show that: parallel k-means algorithm has better performance than serial k-means algorithm; and k-means algorithm has better parallelism and extendibility than PAM algorithm. Finally， this paper puts forward the idea of introducing the method of parallel operating into spectral clustering algorithm technology.

Key words: clustering algorithm; parallelizing; k-means PAM

所謂數據挖掘，簡言之是指在大量的數據中發現、提取潛在的有用信息和知識的過程。聚類分析是數據挖掘法技術中重要組成部分，聚類分析是指根據數據中對象及其之間的關系，將數據對象分組。其目標是，使組內的對象相互之間是相似的(相關的)，而不同組中的對象是不同的(不相關的)。組內的相似性(同質性)越大，組間差別越大，聚類效果就越好[1]。

由于數據挖掘是從海量數據中提取有用信息，處理效率問題成了對海量數據處理的瓶頸之一，傳統的單機串行算法效率較低;由于部分聚類算法中蘊涵并行性，所以為了解決處理效率問題，將并行化的程序設計思想(并行處理)引入聚類算法，同時降低算法的復雜度，使用機群系統進行并行計算，從而有效的縮短聚類的時間。

1 K-means算法

1.1 傳統K-means聚類算法

K-means算法以k為輸入參數，把包含n個對象的集合分為k個簇，使得結果簇內的相似度高，而簇間的相似度低。簇的相似度是關于簇中對象的均值度量，可以看做簇的質心或重心[2]。

傳統K-means算法的處理流程如下:

輸入:k:簇的數目

D:包含n個對象的數據集

輸出:k個簇的集合

方法:

1) 從D中任意選擇k個對象作為初始簇重心

2) Do

3) 根據簇中對象的均值，將每個對象(再)指派到最相似的簇

4) 更新簇均值，即計算每個簇中對象的均值

5) while 數據集中所有對象的平方誤差和E不再發生變化

通常，采用平方誤差準則，其定義如下:

其中，E是數據集中所有對象的平方誤差和，p是空間中的點，即給定對象，mi是簇Ci的均值(p和mi都是多維的)。換言之，對于每個簇中的每個對象，求對象到簇中心距離的平方再求和。這個準則試圖使得生成的k個結果簇盡可能的緊湊和獨立。

1.2 并行化K-means改進算法

隨著并行處理技術的快速發展，越來越多的研究人員嘗試將并行處理方法應用于提高聚類算法的效率，通過研究發現K-means算法具有很大的并行性。首先，可將待挖掘的數據集N劃分為t個數據子集，t為并行處理環境中處理機的數目;然后將劃分后t個數據子集分別發送到t臺處理機進行數據聚類處理;最后主機將收到的節點機的聚類結果計算平方誤差準則函數E的值，并將前后兩次結果做差，如果差的絕對值小于閾值10-6，則處理結束，否則繼續循環處理。并行K-means算法的流程如圖1所示。

1.3 實驗結果與分析

我們搭建工作站機群系統，通過以太網卡等連接5臺PC機(Intel P4.17GHz、256MB RAM，安裝LINUX redhat OS)，采用Master/Slave模式的數據并行策略，建立基于消息傳遞的工作站機群系統，用MPI進行算法編程驗證實驗。

本實驗的主要目的是驗證并行化后的K-means算法的執行時間和效率，所以為了簡單起見，本實驗中的數據是通過計算機隨機產生的整型數據。同時，我們將并行與串行算法的實驗結果相比較，當進行算法比較時，把程序運行10次并取平均值進行作圖比較(如圖2)。

從圖2中我們可以看出并行K-means在數據集較大時表現出比串行K-means更好的執行效率，而當數據集較小時，主要由于并行計算中PC間通信時耗較大，所以單機串行算法表現出相對更高的執行效率。實驗可以證明K-means算法在并行機群上具有了良好的并行性和可擴展性。

2 PAM算法

2.1 PAM聚類算法

PAM是k中心點(k-medoid)算法之一，它試圖確定n個對象的k個劃分。在隨機選擇k個初始代表對象之后，該算法反復試圖選擇簇的更好的代表對象。分析所有可能的對象對，每對中的一個對象看作是代表對象，另一個看做非代表對象。對于每個這樣的組合，計算結果聚類的質量。對象oj被那個可以使誤差值減少最多的對象所取代。再一次迭代中產生的每個簇中最好的對象集合成為下次迭代的代表對象。最終集合中的代表對象便是簇的代表中心。PAM算法的處理流程如下[2]:

輸入:k: 結果簇的個數

D: 包含n個對象的數據集合

輸出:k個簇的集合

方法:

1) 從D中任意選取k個對象作為初始的對象或種子

2) repeat

3) 將每個剩余對象指派到最近的代表對象所代表的簇

4) 隨機地選取一個非代表對象Orandom

5) 計算用Orandom交換代表對象Oj的總代價S

6) if S<0 then 用Orandom替換Oj，形成新的k個代表對象的集合

7) until不在發生變化

2.2 并行化PAM改進算法

為了使問題簡單化，首先我們選擇任意的當前k個對象作為節點{Ol，…，Ok}。對于PAM算法，當每一步結束時，一種情況是找到一個代價最小的相鄰節點，另一種情況是算法結束(當前節點代價最小)[3]。如果我們需要從當前節點移動到一個新的節點，我們必須交換一個已選對象和一個未選對象。為了保證已選對象在前k位，我們交換他們的下標。這樣{Ol，…，Ok}會一直作為當前節點，而且不會受到當前節點移動的影響。

PAM的主要任務是檢查當前節點的所有相鄰節點，而且必須在劃分的同時檢查[3]。假設在p個進程(記為p1，p2，…，pp)上運行PAM算法。算法描述為:

1)將所有相鄰節點寫在列表中并按下標(升序)排序;

2)前[k(n-k)/p]個相鄰節點指派給p1，接著的[k(n-k)/p]個相鄰節點指派給 p2，…，最后的[k(n-k)/p]個相鄰節點指派給process p;

3)p個進程并行，并且報告各自相鄰節點n1，…，np;

4)如果沒有相鄰節點被報告，算法結束(當前節點的代價最小);

5)從n1，…，np中選擇代價最小的節點，將此節點改為當前節點，重復第一步。

下面舉一個例子簡單說明該算法，給定一個對象集{1，2，3，4，5，6，7}，假設k=4，“1234”相鄰節點為(用上述方法得到):1235，1236，1237(i=4);1245，1246，1247(i=3);1345，1346，1347(i=2);2345，2346，2347(i=1)。

每個進程被指派任務后，各自查找代價最小的節點，最后所有的進程(除了p1)將得到的節點報告給p1，由p1作比較工作。

2.3 實驗結果與分析

利用2.3中搭建的工作站機群系統，此時用3臺PC機，進行PAM算法的執行效率驗證，并對比串行和并行PAM的執行時間(如圖3)，由于PAM算法不適用于大量數據集的處理，所以實驗n取1000以內的數值。

從圖3中我們可以看出并行PAM的執行時間比串行PAM的執行時間長，并沒有提高算法的執行效率，由此我們可知K-means算法有比PAM更好的并行性和可擴展性。

3 具有并行性的其他聚類算法

聚類算法中除了上述K-means、PAM算法具有潛在的并行性和可擴展性外，還有一些算法可以進行并行化處理例如:并行硬聚類算法中的K-mediods，面向大規模數據庫系統的BIRCH算法，處理非數值屬性聚類的CACTUS算法，子空間聚類算法ENCLUS等[4]，以及模糊聚類算法中的FCM等算法，理論上也具有在并行機群上的加速性。

4 進一步研究方向與展望

近年來誕生了聚類算法中的一個嶄新分支和研究熱點—譜聚類算法，譜聚類算法建立在譜圖理論之上，其實質是將聚類問題轉化為圖的最優劃分問題，相對于傳統的聚類算法有許多優勢，并在實踐中取得了很好的效果。由于譜聚類算法一般可以歸納總結為三個步驟[5]:

步驟一:構造數據集表示矩陣Z;

步驟二:計算Z的前k個特征值和特征向量，構造特征值的向量空間;

步驟三:利用K-means或其它傳統聚類算法對特征向量進行聚類。

由于譜聚類算法研究中可以運用K-means算法等具有并行性的聚類算法進行特征向量的聚類，所以本文對K-means算法并行化的研究也可以運用于譜聚類的并行化，提高譜聚類算法的執行效率，是很有前景的研究問題。

參考文獻:

[1] Tan P N， Steinbach M， Kumar V. Introduction to Data Mining[M].Beijing:POSTS TELECOM PRESS，2006.

[2] Jia W H， Micheline Kamber. Data Mining Concepts and Techniques[M]. Beijing: China Machine Press，2006.

[3] Yan Z P， Shao X L， Zhang F. Parallel Clustering Methods for Data Mining[J].Acta Scientiarum Naturalium Universitatis Nankaiensis， 2008(4):106-111.

[4] 蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述[J].計算機科學，2008(7):14-18.