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

郭占元 林 濤

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

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

郭占元 林 濤

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

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

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

0 引 言

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

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

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

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

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

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

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

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

1.2 各類型變量的近似分布

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

(1)

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

(2)

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

(3)

1.3MapReduce并行編程框架

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

經(jīng)Map端處理后的，在被發(fā)送到Reduce端前，用戶可以通過(guò)實(shí)現(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個(gè)對(duì)象作為初始中心，每次迭代啟動(dòng)一個(gè)job任務(wù)，Map函數(shù)計(jì)算所有對(duì)象到k個(gè)中心的距離并將其分配到離它最近的簇，Reduce函數(shù)利用均值等方法更新該類的中心值。經(jīng)過(guò)多次迭代，生成穩(wěn)定的簇中心。這些算法只是將K-means算法遷移到MapReduce框架下，依然存在依賴初始化中心的問(wèn)題，同時(shí)在執(zhí)行Map/Reduce方法的過(guò)程中，也存在通信量過(guò)大、可伸縮性較差等問(wèn)題。

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

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

(4)

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Repeat

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

Repeat

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

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

Until所有非中心點(diǎn)被選擇過(guò)；

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

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

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

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

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

圖1 算法流程圖

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

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

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

3.2 仿真實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

表1 各算法運(yùn)行時(shí)間對(duì)比表

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

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

[2] 陳光平,王文鵬,黃俊.一種改進(jìn)初始聚類中心選擇的K-means算法[J].小型微型計(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ì)算機(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ì)算機(jī)工程與設(shè)計(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的隨機(jī)抽樣K-means算法[J].計(jì)算機(jī)工程與應(yīng)用,2016(8):74-79.

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

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

TP311

A

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