面向大規模數據快速聚類K-means算法的研究

郭占元 林 濤

(河北工業大學計算機科學與軟件學院 天津 300401)

面向大規模數據快速聚類K-means算法的研究

郭占元 林 濤

(河北工業大學計算機科學與軟件學院 天津 300401)

為進一步提高K-means算法對大規模數據聚類的效率，結合MapReduce計算模型，提出一種先利用Hash函數進行樣本抽取，再利用Pam算法獲取初始中心的并行聚類方法。通過Hash函數抽取的樣本能充分反映數據的統計特性，使用Pam算法獲取初始聚類中心，改善了傳統聚類算法依賴初始中心的問題。實驗結果表明該算法有效提高了聚類質量和執行效率，適用于對大規模數據的聚類分析。

大規模數據 聚類算法 MapReduce Hash樣本抽樣 Pam算法

0 引 言

聚類分析是數據挖掘領域中的一個重要分支。聚類的基本思想是，同一個簇中的對象是相似的，不同簇中的對象相差較大。典型的K-means算法對初始化的k個中心依賴性很大，若初始中心選擇不當，往往會得不到全局最優解，增加算法的迭代次數和運算時間，降低算法的執行效率[1]。

快速確定優秀的初始聚類中心，最終獲取全局最優解，提高聚類算法的收斂速度是K-means聚類算法的重點研究內容。文獻[2]選取距離最大的兩個數據對象作為初始聚類中心，迭代分裂，直到獲取k個中心點；文獻[3]利用領導者算法將數據分成不同的部分，從中選擇初始中心點；文獻[4-5]選取位于高密度區域且相距較遠的數據對象作為初始中心。上述研究能有效地獲取優秀的聚類初始中心，從而提高聚類算法的質量，但算法的時間復雜度較高，無法適應海量數據的聚類要求[6]。

隨著數據量的不斷增長，串行環境下的聚類算法在執行效率和準確程度上難以均衡兩者之間的關系，因此許多研究將傳統的聚類算法進行并行實現，從而滿足對海量數據的處理要求。MapReduce是處理大規模數據的并行編程框架，利用MapReduce框架進行數據聚類，能有效地提高算法的執行效率，其分布式集群提供的存儲與計算能力能夠解決龐大的數據規模和復雜的數據類型所帶來的問題。因此，基于MapReduce框架面向大規模數據的并行聚類算法[7]逐漸被學者重視和提出。文獻[1]基于MapReduce提出一種先抽樣再用最大最小距離算法獲取初始中心的K-means并行聚類算法；文獻[8]結合MapReduce框架，提出了經過多次隨機抽樣獲取優秀初始中心的K-means并行聚類算法；文獻[9]對基于MapReduce的K-means并行聚類算法，從通信模式和初始中心方面，提出了改進思路和具體實現。

本文在此基礎上，以典型的K-means為研究對象，結合MapReduce并行編程模型，提出一種先利用Hash函數對數據進行樣本抽樣，然后通過Pam算法獲取初始中心的K-means并行聚類方法。

1 相關概念與描述

1.1 基于Hash函數的取樣

傳統的抽樣方法一般采用簡單隨機抽樣[10]，但這種方法具有不確定性，誤差方差較大，不能真正反映數據分布的統計特性。特別當數據分布不均勻時，樣本不具有對總體數據統計分布的代表性。

基于Hash函數的取樣技術是基于傳統的分層抽樣提出的。利用Hash桶進行分層，將m維立體數據按等概率進行分桶，使得每層(即通過Hash函數構造的Hash桶)的數據特性相近，以較小的計算代價得到分層的效果，然后進行分層抽樣，使樣本充分反映數據的統計特性，同時該算法具有較好的時間復雜度O(n)。

1.2 各類型變量的近似分布

(1) 對于連續隨機變量x，其估計分布函數服從近似正態分布N(μ,σ2)，分布函數為：

(1)

(2) 對于二元變量x，設其狀態為0、1。樣本中，0狀態的個數為n，1狀態的個數為m，則其估計分布函數為：

(2)

(3) 對于標稱變量x,所抽樣本中各狀態出現的個數為n1,n2,…,nt，令pi=ni/(n1+n2+…+nt)，則其估計分布函數為：

(3)

1.3MapReduce并行編程框架

MapReduce編程模型是一個簡化的并行計算編程模型，自動實現資源調度，屏蔽了底層復雜的細節。MapReduce的核心是Map和Reduce兩個函數，它們的功能是將輸入的鍵值對轉換成符合要求的。其中，Map端負責分解任務，Reduce端負責合并任務。當所有Map任務成功完成之后，具有相同key的鍵值對會被發送到同一個Reduce進行合并。

經Map端處理后的，在被發送到Reduce端前，用戶可以通過實現Combine函數進行本地合并，從而減少網絡的IO操作以及數據的傳輸量，使MapReduce更加有效。

2 基于MapReduce的聚類優化算法

傳統的基于MapReduce框架的K-means算法從數據集中隨機選取k個對象作為初始中心，每次迭代啟動一個job任務，Map函數計算所有對象到k個中心的距離并將其分配到離它最近的簇，Reduce函數利用均值等方法更新該類的中心值。經過多次迭代，生成穩定的簇中心。這些算法只是將K-means算法遷移到MapReduce框架下，依然存在依賴初始化中心的問題，同時在執行Map/Reduce方法的過程中，也存在通信量過大、可伸縮性較差等問題。

因此，本文結合MapReduce對算法進行優化和改進，利用Hash函數抽取樣本充分反映數據的分布情況，使用Pam算法對樣本進行聚類，采用實際樣本點作為新的聚類中心，避免噪聲點和孤立點的影響，從而提高了算法的聚類效果，加快了算法的處理速度。

2.1 基于Hash函數的樣本抽樣算法過程

(4)

(2) 按照式(1)-式(3)對每維變量進行近似分布估計，可構造如下Hash函數：

H(x1,x2,…,xm)=F(x1),F(x2),…,F(xm)

(5)

易知該Hash函數的取值范圍為[0,1]，設要獲取n個樣本數據，則將該區間n等分：0 =i1

基于Hash函數的樣本抽樣算法過程如下：

(1) 確定抽樣樣本容量n；

(2) 按照式(1)-式(3)估計各列分布函數F(x)；

(3) 構造Hash函數如式(5)；

(4) 將所有數據對象分配到這n個桶中；

(5) 隨機地從每個Hash桶抽取一定比例的數據，組成一個樣本數為n的樣本數據集。

2.2 改進算法方案設計

針對傳統K-means聚類算法面對大規模數據，算法時間開銷大、執行效率低，另外隨機選取初始中心，可能會陷入局部最優解，導致聚類結果不準確的問題。本文提出以下改進方案：

(1) 對于K-means的聚類初始化問題，本文采用一種結合Hash函數的樣本抽樣方法從數據集X中抽取一部分分布均勻的數據集X={x1,x2,…,xn}，然后應用Pam聚類算法獲取樣本的聚類中心，作為數據集的初始聚類中心。

(2) 針對K-means算法在處理海量數據時效率低下的問題，本文結合MapReduce計算模型，對K-means聚類算法進行并行實現。

(3) 針對傳統Pam算法采用全局順序替換策略，時間復雜度高的問題，利用MapReduce框架并行實現Pam算法。

2.3 改進算法執行流程

改進算法具體過程如下：

1) 計算數據對象的均值、標準差。

2) 根據式(4)確定抽樣的樣本數量n。

3) 按照上述利用Hash函數進行樣本抽樣的過程從數據集X中進行樣本抽樣。

4) 對抽取的樣本利用Pam聚類算法進行聚類，從而獲取初始中心，過程如下：

Repeat

(1) 計算樣本數據集中的每個非中心點xi與各個中心點之間的距離，將其分配給距它最近的第k個中心點，形成多個類簇；

Repeat

(2) 選擇樣本數據集中一個未被選擇的非中心點xi替換當前簇的中心點；

(3) 如果存在某個非中心點代替當前中心點的代價小于0，則用該非中心點替換中心點，形成一個新的類簇；

Until所有非中心點被選擇過；

Until沒有類簇進行中心點重新分配；

(4) 將穩定的聚類中心記錄為C。

5) 將C作為全局初始聚類中心，輸入數據集以及相關參數。

6) 運行并行的K-means聚類算法，直到所有類簇穩定，或者達到最大迭代次數，算法結束。

對應算法流程如圖1所示。

圖1 算法流程圖

2.4 算法時間復雜度分析

設N為數據對象數量，k為類別個數，t為迭代次數，w為每個對象的維度，Map節點的個數為m，Reduce的個數為r，抽取的樣本容量為n，則串行條件下K-means算法的時間復雜度為O(Nktw)。

3 實驗及結果分析

3.1 實驗環境

硬件：6臺普通PC機，1臺作為主節點，其余5臺為從節點。其配置均為3.20GHz的4核CPU，500GB硬盤，4GB內存。

軟件：操作系統CentOS6.4，Hadoop2.20，Jdk1.7，Eclipse4.42，Hadoop集群環境采用完全分布式模式部署。

3.2 仿真實驗與分析

實驗數據為UCI機器學習庫中的Synthetic-Control數據集，每條數據的維度為60，共包含6個類別。為驗證改進算法處理大規模數據的能力，在此基礎上構造了data1～data3三組數據集用于聚類，規模分別為600MB、1 200MB、2 000MB。每次實驗均取10次實驗結果的平均值為最終結果。

3.2.1 實驗1：驗證改進算法的加速比

實驗說明：本實驗在節點個數分別為1、2、3、4、5的Hadoop平臺上，利用本文算法對data1～data3三組數據進行聚類，運行時間如圖2所示。

圖2 各數據集在不同節點下的運行時間

由圖2可得出以下結論：

(1) 對于同一數據集，隨著集群中參與運算的節點個數不斷地增多，單個節點處理的數據逐漸變少，從而導致總體的運行時間減少。而且當數據規模相對較大時，算法運行時間的減少幅度更加明顯，說明集群的并行化有效提高了算法處理大規模數據的執行效率。

(2) 隨著節點個數的增加，運行時間曲線趨于平緩，這是因為當各節點處理的數據量較少時，各節點進行邏輯運算所消耗的時間占總時長比例較小，而MapReduce在啟動任務和各節點之間進行數據通信消耗的時間占據了一定比例，綜合兩者導致總時長差距不明顯。

圖3 各數據集在不同節點下的加速比

由圖3可知：隨著節點數目的增加，算法的加速比接近線性增長，說明本文提出的改進算法具有良好的可擴展性，能很好地適應于并行化。

3.2.2 實驗2：驗證改進算法的有效性

實驗說明：為驗證算法的有效性，在節點數為5的集群環境下，利用基于MapReduce的K-means并行聚類算法(算法1)、文獻[1]提出的改進算法(算法2)、文獻[8]提出的改進算法(算法3)和本文提出的改進算法分別對data1、data2、data3數據集進行聚類實驗。記錄四種算法的運行時間(單位：分鐘)如表1所示，算法執行的迭代次數如表2所示。

表1 各算法運行時間對比表

表2 各算法迭代次數對比表

綜合表1、表2可得出以下結論：

(1) 當數據集為data1時，數據記錄相對較少，各算法運行時間差距不大，這是因為經過優化后的算法雖然選取了優秀的初始聚類中心，減少了算法的迭代次數，但同時也消耗了時間。隨著數據規模的增大，通過樣本獲取初始中心消耗的時間占總時長的比例逐漸減少，算法本身成為影響執行時間的主要因素，算法運行總時長的差距也相應變大。

(2) 在運行相同條件下，算法2所用時間最長，由于其獲取初始中心時，采用串行實現的最大最小距離算法，時間復雜度較高，增加了時間的開銷。而本文提出的改進算法，無論是迭代次數還是執行時間，與其他算法相比，都有所減少，說明其能快速有效地獲取優秀的初始聚類中心，從而縮短算法的運行時間，提高算法的執行效率。

3.2.3 實驗3：驗證改進算法的正確性

實驗說明：為驗證算法的正確性，利用本文提出的改進算法分別對不同的數據集進行聚類。實驗數據為UCI機器學習庫中的Synthetic-Control數據集、Iris數據集和Wine數據集。其中，Iris和Wine數據集均包含3個類別，每條記錄分別由4個和13個屬性構成。本實驗在此基礎上分別將3個數據集擴充為3百萬條記錄，取10次實驗結果的平均值為最終結果。實驗結果如表3所示。

表3 各算法準確率對比表 %

由表3可知：同一數據集下，算法2、算法3和本文算法的準確率相對于算法1都有所提高，說明通過獲取優秀的初始聚類中心，提高了算法的聚類效果。而本文算法的聚類效果更佳，說明利用Pam算法獲取聚類中心，有效降低了異常點的干擾，從而提高了算法的準確率。

3.2.4 實驗4：驗證改進算法的穩定性

實驗說明：為驗證算法的穩定性，在節點數為5的集群環境下，分別利用四種算法對data3數據集進行聚類。記錄四種算法10次聚類結果的準確率如圖4所示。

通過圖4可以得出以下結論：

本文算法準確率曲線走勢相對平穩，而其它三種算法準確率曲線偏離中心線幅度較大，其中算法1偏離程度最為嚴重。由于算法2和算法3在獲取聚類初始中心時，隨機取樣的不穩定性導致選擇的初始聚類中心與實際的聚類中心存在一定偏差，但其通過選擇優秀的聚類中心，改善了中心點對聚類結果的影響，所以兩者的準確率曲線波動范圍與算法1相比相對較小。而本文算法利用Hash函數進行樣本抽樣，客觀地反映了數據的分布特性，獲取的初始中心與數據集的聚類中心更接近，與其他三種算法相比，表現出更高的穩定性和準確性。

圖4 各算法10次實驗結果的準確率

4 結 語

本文主要通過Hadoop平臺上的MapReduce框架實現了針對大規模數據進行快速聚類的優化算法，實驗結果表明：這種改進的方法較快地選取了優秀的初始聚類中心，降低了對初始聚類中心的依賴性，提高了大規模數據集下聚類算法的正確率，加速了聚類的收斂速度。并行環境下，能適應海量數據的快速聚類。下一步工作主要對集群的參數配置進行實驗調優，以提高系統負載均衡的能力和魯棒性。同時聚類中心k值的自動確定，是以后的研究重點。

[1] 韓巖,李曉.加速大數據聚類K-means算法的改進[J].計算機工程與設計,2015,36(5):1317-1320.

[2] 陳光平,王文鵬,黃俊.一種改進初始聚類中心選擇的K-means算法[J].小型微型計算機系統,2012,33(6):1320-1323.

[3]KumarKM,ReddyARM.AfastK-meansclusteringusingprototypesforinitialclustercenterselection[C]//InternationalConferenceonIntelligentSystemsandControl,2015:1-4.

[4] 謝娟英,王艷娥.最小方差優化初始聚類中心的K-means算法[J].計算機工程,2014,40(8):205-211.

[5]LinK,LiX,ZhangZ,etal.AK-meansclusteringwithoptimizedinitialcenterbasedonHadoopplatform[C]//InternationalConferenceonComputerScience&Education,2014:263-266.

[6] 張靖,段富.優化初始聚類中心的改進K-means算法[J].計算機工程與設計,2013,34(5):1691-1694,1699.

[7] Kumar A,Kiran M,Prathap B R.Verification and Validation of Map Reduce Program model for Parallel K-Means algorithm on Hadoop Cluster[C]//International Conference on Advanced Computing and Communication Systems,2014:1-8.

[8] 王永貴,武超,戴偉.基于MapReduce的隨機抽樣K-means算法[J].計算機工程與應用,2016(8):74-79.

[9] 牛新征,佘堃.面向大規模數據的快速并行聚類劃分算法研究[J].計算機科學,2012,39(1):134-137.

[10] 王秀華.基于隨機抽樣的加速K-均值聚類方法[J].計算機與現代化,2013(12):27-29.

RESEARCH ON FAST CLUSTERING K-MEANS ALGORITHM FOR LARGE-SCALE DATA

Guo Zhanyuan Lin Tao

(SchoolofComputerScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,China)

To further enhance the efficiency of K-means clustering algorithm for large-scale data, combined with MapReduce computational model, a parallel clustering method is proposed, which uses Hash function to extract samples and then obtains initial center by Pam algorithm. The sample extracted by Hash function can fully reflect the statistical characteristics of the data, using Pam algorithm to obtain the initial clustering center, and improve the traditional clustering algorithm to rely on the initial center of the problem. It uses the Pam algorithm to obtain the initial clustering center, and improves the problem of that the traditional clustering algorithms rely on the initial center. The experimental results show that the proposed algorithm can effectively improve the clustering quality and efficiency, and is suitable for the clustering analysis of large-scale data.

Large-scale data Clustering algorithm MapReduce Hash sampling Pam algorithm

2016-06-16。天津市科技支持計劃科技服務重大專項(14ZCDZGX00818)。郭占元，碩士，主研領域：數據挖掘，云計算與大數據處理。林濤，教授。

TP311

A

10.3969/j.issn.1000-386x.2017.05.008