郭占元 林 濤

(河北工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院 天津 300401)

面向大規(guī)模數(shù)據(jù)快速聚類K-means算法的研究

郭占元 林 濤

(河北工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院 天津 300401)

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

大規(guī)模數(shù)據(jù) 聚類算法 MapReduce Hash樣本抽樣 Pam算法

0 引 言

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

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

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

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

1 相關(guān)概念與描述

1.1 基于Hash函數(shù)的取樣

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

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

1.2 各類型變量的近似分布

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

(1)

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

(2)

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

(3)

1.3MapReduce并行編程框架

MapReduce編程模型是一個簡化的并行計算編程模型，自動實現(xiàn)資源調(diào)度，屏蔽了底層復(fù)雜的細(xì)節(jié)。MapReduce的核心是Map和Reduce兩個函數(shù)，它們的功能是將輸入的鍵值對轉(zhuǎn)換成符合要求的。其中，Map端負(fù)責(zé)分解任務(wù)，Reduce端負(fù)責(zé)合并任務(wù)。當(dāng)所有Map任務(wù)成功完成之后，具有相同key的鍵值對會被發(fā)送到同一個Reduce進(jìn)行合并。

經(jīng)Map端處理后的，在被發(fā)送到Reduce端前，用戶可以通過實現(xiàn)Combine函數(shù)進(jìn)行本地合并，從而減少網(wǎng)絡(luò)的IO操作以及數(shù)據(jù)的傳輸量，使MapReduce更加有效。

2 基于MapReduce的聚類優(yōu)化算法

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

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

2.1 基于Hash函數(shù)的樣本抽樣算法過程

(4)

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

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

(5)

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

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

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

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

(3) 構(gòu)造Hash函數(shù)如式(5)；

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

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

2.2 改進(jìn)算法方案設(shè)計

針對傳統(tǒng)K-means聚類算法面對大規(guī)模數(shù)據(jù)，算法時間開銷大、執(zhí)行效率低，另外隨機(jī)選取初始中心，可能會陷入局部最優(yōu)解，導(dǎo)致聚類結(jié)果不準(zhǔn)確的問題。本文提出以下改進(jìn)方案：

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

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

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

2.3 改進(jìn)算法執(zhí)行流程

改進(jìn)算法具體過程如下：

1) 計算數(shù)據(jù)對象的均值、標(biāo)準(zhǔn)差。

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

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

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

Repeat

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

Repeat

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

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

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

Until沒有類簇進(jìn)行中心點重新分配；

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

5) 將C作為全局初始聚類中心，輸入數(shù)據(jù)集以及相關(guān)參數(shù)。

6) 運行并行的K-means聚類算法，直到所有類簇穩(wěn)定，或者達(dá)到最大迭代次數(shù)，算法結(jié)束。

對應(yīng)算法流程如圖1所示。

圖1 算法流程圖

2.4 算法時間復(fù)雜度分析

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

3 實驗及結(jié)果分析

3.1 實驗環(huán)境

硬件：6臺普通PC機(jī)，1臺作為主節(jié)點，其余5臺為從節(jié)點。其配置均為3.20GHz的4核CPU，500GB硬盤，4GB內(nèi)存。

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

3.2 仿真實驗與分析

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

3.2.1 實驗1：驗證改進(jìn)算法的加速比

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

圖2 各數(shù)據(jù)集在不同節(jié)點下的運行時間

由圖2可得出以下結(jié)論：

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

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

圖3 各數(shù)據(jù)集在不同節(jié)點下的加速比

由圖3可知：隨著節(jié)點數(shù)目的增加，算法的加速比接近線性增長，說明本文提出的改進(jìn)算法具有良好的可擴(kuò)展性，能很好地適應(yīng)于并行化。

3.2.2 實驗2：驗證改進(jìn)算法的有效性

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

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

表2 各算法迭代次數(shù)對比表

綜合表1、表2可得出以下結(jié)論：

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

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

3.2.3 實驗3：驗證改進(jìn)算法的正確性

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

表3 各算法準(zhǔn)確率對比表 %

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

3.2.4 實驗4：驗證改進(jìn)算法的穩(wěn)定性

實驗說明：為驗證算法的穩(wěn)定性，在節(jié)點數(shù)為5的集群環(huán)境下，分別利用四種算法對data3數(shù)據(jù)集進(jìn)行聚類。記錄四種算法10次聚類結(jié)果的準(zhǔn)確率如圖4所示。

通過圖4可以得出以下結(jié)論：

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

圖4 各算法10次實驗結(jié)果的準(zhǔn)確率

4 結(jié) 語

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

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

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

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

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

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

[6] 張靖,段富.優(yōu)化初始聚類中心的改進(jìn)K-means算法[J].計算機(jī)工程與設(shè)計,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的隨機(jī)抽樣K-means算法[J].計算機(jī)工程與應(yīng)用,2016(8):74-79.

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

[10] 王秀華.基于隨機(jī)抽樣的加速K-均值聚類方法[J].計算機(jī)與現(xiàn)代化,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。天津市科技支持計劃科技服務(wù)重大專項(14ZCDZGX00818)。郭占元，碩士，主研領(lǐng)域：數(shù)據(jù)挖掘，云計算與大數(shù)據(jù)處理。林濤，教授。

TP311

A

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