林丹楠，黃 銳

(1.福建商學(xué)院 信息技術(shù)學(xué)院，福建 福州 350012;2.北京理工大學(xué) 計算機(jī)學(xué)院，北京 100081)

伴隨著科技的發(fā)展，互聯(lián)網(wǎng)用戶數(shù)量的快速增加，網(wǎng)絡(luò)信息量也急劇增長，數(shù)據(jù)集中包含的數(shù)據(jù)量呈指數(shù)級增長，世界已經(jīng)進(jìn)入了大數(shù)據(jù)信息化時代[1-4].這些大數(shù)據(jù)包含了人們的生產(chǎn)活動的各方面信息，具有非常大的挖掘價值.但是，這些數(shù)據(jù)有噪音、持續(xù)、多樣化，如何從其中提取出所需的規(guī)律和隱含結(jié)構(gòu)，以便轉(zhuǎn)換成有用的信息，成了如今熱門的研究問題.數(shù)據(jù)挖掘技術(shù)成為了解決以上問題的主流技術(shù).

聚類算法一直是數(shù)據(jù)挖掘算法中比較重要的一個分支[5].聚類分析可以按照個體或樣品的特征將它們分類.聚類分析方法種類較多[5]，主要分為劃分聚類、層次聚類、基于密度的聚類、基于網(wǎng)格的聚類等.其中，作為十大經(jīng)典聚類算法之一，K-means算法是典型的基于劃分方法的聚類算法，被廣泛應(yīng)用于實(shí)際數(shù)據(jù)集的聚類分析中.

文獻(xiàn)[6]針對傳統(tǒng)K-means算法敏感于初始中心點(diǎn)的選取的問題，提出了基于不唯一密度的K-means優(yōu)化方法，改進(jìn)后的聚類結(jié)果較穩(wěn)定且準(zhǔn)確率有所提高.文獻(xiàn)[7]利用最小-最大相似度(MMS)建立初始質(zhì)心，對傳統(tǒng)的K-means聚類算法進(jìn)行了改進(jìn)得到了MMSK-means聚類算法，其作為一種標(biāo)簽聚類算法，可用于個性化搜索任務(wù).文獻(xiàn)[8]利用群體智能優(yōu)化算法中的PSO算法對典型K-means算法進(jìn)行了改進(jìn)，并將其在網(wǎng)絡(luò)入侵檢測中進(jìn)行了應(yīng)用.該方法能夠解決初始聚類中心隨機(jī)選擇問題，較少聚類結(jié)果對初始聚類中心的依賴性.但是，伴隨著數(shù)據(jù)量“爆炸式”的增長，傳統(tǒng)模式的K-means聚類算法已經(jīng)無法適應(yīng)大規(guī)模數(shù)據(jù)集的挖掘.因此，文獻(xiàn)[9]提出了一種基于CPU和GPU輔助的并行化核K-means聚類算法，大大較少了聚類算法的耗時.

隨著云計算的快速發(fā)展，Hadoop分布式平臺為新模式的聚類分析提供了有力支撐.因此，針對傳統(tǒng)K-means聚類的初始中心點(diǎn)選取和Hadoop并行化設(shè)計問題，提出了一種MapReduce并行聚類優(yōu)化算法.該算法充分利用了差分進(jìn)化算法的并行全局搜索優(yōu)勢.并把優(yōu)化后的算法在Hadoop的MapReduce框架下做了并行化的設(shè)計.實(shí)驗(yàn)結(jié)果表明優(yōu)化后的K-means 算法大大減少了運(yùn)算的時間，且聚類效果良好.

1 K-means聚類和差分進(jìn)化算法分析

1.1 K-means算法介紹

作為一種基于距離的劃分聚類算法，K-means聚類算法具有算法結(jié)構(gòu)簡單、運(yùn)行效率高且適用范圍大等優(yōu)點(diǎn)[10]-[13].K-means聚類算法一般通過如公式(1)所示的目標(biāo)函數(shù)來實(shí)現(xiàn)優(yōu)化.

(1)

可以看出，公式(1)所示的目標(biāo)函數(shù)是一個誤差平方和計算過程.其中，E為聚類準(zhǔn)則函數(shù)，K為聚類的總數(shù)，Cj,j=1,2,…,K為聚類中的簇j，x為簇Cj中的一個聚類目標(biāo)，mj為簇Cj的平均大小.通常來說，E的值越小則聚類效果越好.反之，E的值越大則聚類質(zhì)量越差.

1.2 差分進(jìn)化算法的基本原理

差分進(jìn)化算法是一種基于群體智能的新型啟發(fā)式算法，具有較強(qiáng)的全局優(yōu)化能力[14].設(shè)X表示初始種群，N為種群的大小，Xi(t)(t=1,2,…,N)為當(dāng)前種群中進(jìn)化個體，t為進(jìn)化過程的迭代次數(shù).種群中個體變異操作的過程如公式(2)所示.

(2)

其中，Xp1(t)Xp2(t)Xp3(t)是從當(dāng)前進(jìn)化種群中隨機(jī)選擇出來的三個不同個體，F(xiàn)是縮放因子，經(jīng)驗(yàn)表明，F(xiàn)=0.6時效果較好.D為種群中個體的維度，也就是說變異個體Vi(t)由D 個分量構(gòu)成.

當(dāng)前種群中的進(jìn)化個體Xi(t)與Vi(t)進(jìn)行交叉操作，生成競爭個體Ui(t)=(ui1(t),ui2(t),…,uiD(t))(由D 個分量構(gòu)成).競爭個體Ui(t)中j-th分量的計算方法如公式(3)所示[15].

(3)

其中，z為一個隨機(jī)整數(shù)，且z∈{1,2,…,D}.CR∈[0,1]為交叉概率，經(jīng)驗(yàn)表明，交叉概率CR的取值在0.3到0.9之間較為適宜.

按照如下方法擇優(yōu)更新種群[16-17].

(4)

2 基于差分進(jìn)化的K-means聚類優(yōu)化

通過研究發(fā)現(xiàn)K-means 算法具有較好的局部的搜索能力，但是容易收斂到局部最優(yōu)解.主要原因是K-means 算法敏感于初始中心點(diǎn)的選取，從而影響聚類結(jié)果的穩(wěn)定性、執(zhí)行時間和分類正確率.因此，為了快速高效地對初始聚類中心進(jìn)行優(yōu)化，本文利用差分進(jìn)化算法對 K-means 算法進(jìn)行改進(jìn)，從而提高聚類質(zhì)量.基于差分進(jìn)化的K-means聚類算法流程如圖1所示.

Input：聚類數(shù)目K，交叉概率CR，縮放因子F，初始數(shù)據(jù)集X及其樣本數(shù)量n，種群規(guī)模N.

Output：最佳聚類結(jié)果.

步驟1：編碼及種群初始化.采用實(shí)數(shù)編碼對數(shù)據(jù)集中隨機(jī)選出的聚類中心進(jìn)行編碼.對于進(jìn)化代數(shù)t=0時，初始種群的第i個樣本編碼方式如下：

Xi(0)=(ci1,ci2,…,ciK)i=1,2,…,N.

(5)

其中，cij示第i個個體的第j個聚類中心，j=1,2,…,K.

步驟2:：計算出個體Xi(t)的適應(yīng)度值f(Xi(t))，本文中的適應(yīng)度函數(shù)采用如下方式得到：

(6)

其中，mi表示簇wi的中心.

步驟3：對當(dāng)前種群中的個體Xi(t)按式(7)計算得到變異個體Vi(t)=(vi1(t),vi2(t),…,viK(t))完成變異操作.

vij(t)=xaj(t)+F(xbj(t)-xcj(t))j=1,2,…,K.

(7)

其中，a,b,c分別為一個隨機(jī)生成的整數(shù)，且a,b,c∈{1,2,…,N}.

步驟4：根據(jù)公式(3)計算競爭個體Ui(t)完成交叉操作.

步驟5：采用貪心選擇策略在當(dāng)前進(jìn)化個體Xi(t)和當(dāng)前競爭個體Ui(t)中選擇一者放入下一代種群中，選擇方式如公式(4)所示.

步驟6：當(dāng)達(dá)到最大的迭代次數(shù)時，停止迭代，輸出最優(yōu)解.否則t=t+1，跳轉(zhuǎn)到步驟2.

步驟7：把差分進(jìn)化算法的輸出作為最佳K個K-means的初始聚類中心組合，使用歐氏距離計算所有數(shù)據(jù)對象與中心的相似度，根據(jù)最近鄰原則，把數(shù)據(jù)對象劃分到相應(yīng)的簇中.

步驟8：輸出聚類結(jié)果.

3 基于MapReduce的聚類分布式設(shè)計

采用并行化的結(jié)構(gòu)設(shè)計理念完成MapReduce函數(shù)設(shè)計，包括map()和 reduce()函數(shù)，以便在Hadoop分布式平臺上運(yùn)行，提高運(yùn)行速度，具體分布式流程如下：

圖1 基于差分進(jìn)化的 K-均值聚類算法流程

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

4.1 Hadoop平臺的搭建

為了驗(yàn)證本文提出并行聚類優(yōu)化在大數(shù)據(jù)環(huán)境下的性能，在 4臺機(jī)器構(gòu)成的Hadoop Hadoop集群上進(jìn)行了性能測試分析.4個節(jié)點(diǎn)(1個主節(jié)點(diǎn)master和3個從節(jié)點(diǎn)slave)的軟硬件配置如表1所示.所有服務(wù)節(jié)點(diǎn)通過1000M光纖實(shí)現(xiàn)相互通信.在所有服務(wù)節(jié)點(diǎn)上均安裝了1.2.1版本的Hadoop，JDK 版本為1.7.4個節(jié)點(diǎn)的ip地址分別為214.102.61.2，214.102.61.3，214.102.61.4，214.102.61.5.

表1 節(jié)點(diǎn)的軟硬件配置參數(shù)

4.2 算法性能驗(yàn)證

采用數(shù)據(jù)集為UCI中的Iris、Wine 數(shù)據(jù)以及人工數(shù)據(jù)集KDS1，實(shí)驗(yàn)數(shù)據(jù)參數(shù)如表2所示.實(shí)驗(yàn)中算法的參數(shù)設(shè)置為：縮放因子F=0.6，交叉概率CR=0.5，最大進(jìn)化代數(shù)取TMAX=1 500.為了使有效性分析更合理，將本文提出算法與傳統(tǒng)的K-means 算法、PSO- K-means算法[8]進(jìn)行了比較，對其聚類結(jié)果取平均值.三種算法的實(shí)驗(yàn)結(jié)果分析如表3 所示.從表3可以看出，相比其他兩種算法，基于差分進(jìn)化的K-means聚類算法在準(zhǔn)確率方面具有最佳性能，即聚類性能最好.

表2 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)

表3三種算法的聚類結(jié)果對比

數(shù)據(jù)集傳統(tǒng)K-means正確率(%)PSO- K-means正確率(%)基于差分進(jìn)化的K-means正確率(%)Iris83.188.389.5Wine71.183.884.6KDS185.392.994.2

4.3 分布式平臺性能驗(yàn)證

圖2 運(yùn)行時間對比

為了驗(yàn)證提出MapReduce并行聚類優(yōu)化算法在分布式平臺的加速效果，在單機(jī)環(huán)境下和集群環(huán)境下對算法的執(zhí)行效率進(jìn)行了對比.兩種情況下運(yùn)行時間對比如圖2所示.可以看出，隨著數(shù)據(jù)集的不斷增大，獲得的加速效果越來越顯著.

5 結(jié)束語

本文將差分進(jìn)化算法與K-means算法相結(jié)合提出了一種MapReduce并行聚類優(yōu)化算法，以便解決傳統(tǒng)K-means聚類的初始中心點(diǎn)選取和Hadoop并行化設(shè)計問題.利用差分進(jìn)化算法的強(qiáng)大全局搜索能力克服K-means算法對初始中心較為敏感的缺點(diǎn)，利于增強(qiáng)全局最優(yōu)解的穩(wěn)定性.并把優(yōu)化后的算法在Hadoop的Map Reduce框架下做了并行化的設(shè)計.實(shí)驗(yàn)結(jié)果驗(yàn)證了提出MapReduce并行聚類優(yōu)化算法的準(zhǔn)確性和有效性，能夠在Hadoop分布式平臺上更加高效地處理海量數(shù)據(jù)挖掘任務(wù).