(長(zhǎng)江大學(xué)電子信息學(xué)院,湖北 荊州 434023)

K-means算法[1]和Canopy算法[2]都屬聚類(lèi)成員，是一種無(wú)監(jiān)督的模式分類(lèi)法[3]。K-means算法實(shí)現(xiàn)簡(jiǎn)單，收斂速度快，但其聚類(lèi)質(zhì)量受初始聚類(lèi)中心選取和類(lèi)簇?cái)?shù)影響較大。文獻(xiàn)[4]以聚類(lèi)對(duì)象分布密度為基礎(chǔ)來(lái)確定初始聚類(lèi)中心的選??；文獻(xiàn)[5]采用最大距離不斷劃分最大距離簇，得到相距較遠(yuǎn)的初始聚類(lèi)中心；文獻(xiàn)[6]以數(shù)據(jù)點(diǎn)的距離構(gòu)成最小生成樹(shù)，對(duì)樹(shù)剪枝將數(shù)據(jù)劃分為k個(gè)初始聚類(lèi)簇，獲得初始聚類(lèi)中心；文獻(xiàn)[7]引入Canopy算法進(jìn)行“粗”聚類(lèi)，獲得了K-means算法的類(lèi)簇?cái)?shù)k和聚類(lèi)中心。

以上這些方法都只是在串行化條件下對(duì)K-means進(jìn)行了改進(jìn)，隨著數(shù)據(jù)量增長(zhǎng)，傳統(tǒng)K-means以及改進(jìn)的K-means算法已很難滿(mǎn)足需求，因此，學(xué)者們提出了基于云平臺(tái)的分布式K-means方法。文獻(xiàn)[8]采用最小加權(quán)距離確定數(shù)據(jù)點(diǎn)被劃歸的類(lèi)簇，增加收斂性判定，最終聚類(lèi)準(zhǔn)確率、收斂時(shí)間都有明顯提升，并利用Hadoop平臺(tái)[9]的MapReduce編程框架[10]，將算法擴(kuò)展至大規(guī)模數(shù)據(jù)集，擴(kuò)展性和加速比的結(jié)果表明該算法適于海量數(shù)據(jù)處理。文獻(xiàn)[11]根據(jù)樣本密度剔除孤立點(diǎn)，利用最大最小化距離思想選擇k個(gè)初始中心，使初始聚類(lèi)中心點(diǎn)得到優(yōu)化，利用MapReduce模型進(jìn)行了并行化處理，提高了聚類(lèi)結(jié)果準(zhǔn)確率和穩(wěn)定性,同時(shí)很好地將算法擴(kuò)展至大規(guī)模數(shù)據(jù)處理。文獻(xiàn)[12]引入Canopy算法優(yōu)化K-means初始中心的選取，并利用MapReduce框架進(jìn)行并行化，算法能獲得較好的執(zhí)行效率和優(yōu)良的擴(kuò)展性，適合海量數(shù)據(jù)的聚類(lèi)分析。

針對(duì)文獻(xiàn)[7]和文獻(xiàn)[12]引入的Canopy算法未考慮任選的初始中心可能是離散點(diǎn)或是孤立點(diǎn)的問(wèn)題，筆者以樣本密度表征類(lèi)內(nèi)聚集度[13]程度，利用樣本方差和最小方差改進(jìn)Canopy算法的初始中心選取，并參照文獻(xiàn)[6，7]設(shè)定了Canopy中的閾值，提出了一種利用最小方差獲取Canopy最優(yōu)全局中心作為K-means聚類(lèi)中心初值的算法(簡(jiǎn)稱(chēng)MVC-Kmeans，K-means based on the Minimum Variance Canopy)。

1 相關(guān)知識(shí)

在實(shí)際應(yīng)用中，K-means算法通過(guò)設(shè)置k個(gè)初始聚類(lèi)中心，對(duì)待測(cè)數(shù)據(jù)集根據(jù)距離準(zhǔn)則反復(fù)迭代更新聚類(lèi)中心并進(jìn)行聚類(lèi)劃分直至收斂；Canopy算法根據(jù)隨機(jī)選取的初始Canopy中心和給定的閾值T1和T2(T1>T2)[14]，按照距離準(zhǔn)則對(duì)待測(cè)數(shù)據(jù)集進(jìn)行閾值劃分，最終生成互相重疊的Canopy類(lèi)。通常k值、初始聚類(lèi)中心以及T1和T2大多根據(jù)經(jīng)驗(yàn)或者隨機(jī)選取，帶有很強(qiáng)盲目性，對(duì)最終聚類(lèi)質(zhì)量有較大影響。因此對(duì)上述初值確定是筆者研究重點(diǎn)。

設(shè)待聚類(lèi)數(shù)據(jù)集為D={xi|xi∈Rm,i=1,2,3,…,n}，其中數(shù)據(jù)集每個(gè)樣本擁有m個(gè)屬性，數(shù)據(jù)xi可表示為xi=(xi1,xi2,…,xim)。

定義1樣本xi和xj的歐氏距離：

(1)

定義2樣本xi到所有樣本距離的平均值：

(2)

定義3樣本xi的方差：

(3)

定義4待聚類(lèi)數(shù)據(jù)集的平均距離：

(4)

定義5誤差平方和：

(5)

2 分布式MVC-Kmeans算法思想

圖1 MVC-Kmeans執(zhí)行流程圖

依據(jù)樣本方差原理，數(shù)據(jù)集中樣本方差的大小，直接決定樣本在數(shù)據(jù)集中的離散趨勢(shì)。方差越小，則樣本點(diǎn)周?chē)鷶?shù)據(jù)越稠密，收斂越快；反之，則越稀疏，收斂越慢。因此，對(duì)Canopy算法隨機(jī)從待聚類(lèi)樣本中任選一點(diǎn)作為Canopy中心的方式進(jìn)行優(yōu)化，利用式(1)～(3)計(jì)算樣本數(shù)據(jù)集中每個(gè)樣本的方差，以樣本方差最小點(diǎn)作為Canopy中心進(jìn)行Canopy劃分來(lái)獲取優(yōu)質(zhì)的初始聚類(lèi)中心作為K-means算法的輸入，同時(shí)參照文獻(xiàn)[5，6]設(shè)置Canopy中的閾值。其執(zhí)行流程圖如圖1所示。

3 MVC-Kmeans算法步驟

算法步驟描述如下：

步1Canopy階段獲得局部Canopy中心。

a)令t=0,根據(jù)式(1)～(3)獲取每一個(gè)數(shù)-據(jù)集D的樣本方差集合C，同時(shí)依據(jù)噪聲點(diǎn)和孤立點(diǎn)存在hi>hAV,為消除這些點(diǎn)的影響以及基于T1與T2之間存在的關(guān)系，設(shè)定T2=hAV，T1=2T2。

則將xj加入到Ct集合并C=C-Ct；

則將xj加入到Ct集合且該點(diǎn)可能會(huì)成為下一個(gè)Canopy中心；

else

xj可能會(huì)成為下一個(gè)Canopy中心；

d)若C為空，則獲得W={wt|wt∈Rm,t=1,2,3,…,n}結(jié)束；否則，轉(zhuǎn)到步1b)。

步2獲得Canopy算法的最終輸出。

a)令t=0,將W以式(1)～(3)獲得的每個(gè)樣本方差放入集合K，設(shè)定T2=hAV，T1=2T2。

則將xj加入到Ct集合并K=K-Ct；

則將xj加入到Ct集合且該點(diǎn)可能會(huì)成為下一個(gè)Canopy中心；

else

xj可能會(huì)成為下一個(gè)Canopy中心；

d)若K為空，則獲得G={gt|gt∈Rm,t=1,2,3,…,n}結(jié)束；否則，轉(zhuǎn)到步2b)。

e)將重疊區(qū)域的樣本歸入到與所屬Ct的gt距離最近的Ct中，并計(jì)算各個(gè)Ct的樣本與對(duì)應(yīng)gt和的均值，作為全局的Canopy中心，并更新集合G。

步3K-means階段構(gòu)造初始劃分。

a)以G為K-means的初始聚類(lèi)中心，利用式(1)計(jì)算D中各樣本到各初始中心的距離，根據(jù)相似性原則將樣本劃歸到最相似的類(lèi)簇中。

b)計(jì)算每個(gè)類(lèi)簇的平均值作為新的聚類(lèi)中心。

c)根據(jù)式(5)計(jì)算當(dāng)前聚類(lèi)結(jié)果的誤差平方和E。

步4重新構(gòu)造類(lèi)簇及更新聚類(lèi)中心。

a)以新的初始聚類(lèi)中心作為聚類(lèi)中心，利用式(1)計(jì)算D中各樣本到各初始中心的距離，根據(jù)相似性原則將樣本劃歸到最相似的類(lèi)簇中。

b)計(jì)算每個(gè)類(lèi)簇的平均值作為新的聚類(lèi)中心。

c)根據(jù)式(5)計(jì)算當(dāng)前聚類(lèi)結(jié)果的誤差平方和E′。

d)如果E′-E<ε,則聚類(lèi)收斂，算法結(jié)束；否則，令E=E′,轉(zhuǎn)到步3。

4 分布式MVC-Kmeans算法的并行設(shè)計(jì)

MVC-Kmeans算法的執(zhí)行流程如圖1所示，由兩部分組成。在Hadoop平臺(tái)的MapReduce下進(jìn)行了該算法的并行化設(shè)計(jì)，其包含2個(gè)任務(wù)，依次執(zhí)行，前一個(gè)任務(wù)的輸出將是下一個(gè)任務(wù)的輸入。

任務(wù)1：結(jié)合最小方差和Canopy算法思想在MapReduce編程框架下的實(shí)現(xiàn)。

在Map階段，利用分布在集群不同站點(diǎn)的數(shù)據(jù)子集，通過(guò)Canopy算法快速產(chǎn)生若干個(gè)以最小方差劃分的局部Canopy中心和重疊的Canopy；在Reduce階段，對(duì)Map階段輸出的Canopy中心重新計(jì)算后，以方差最小的樣本為新的初始Canopy中心，再次運(yùn)用Canopy算法獲得全局Canopy中心和重疊的Canopy，將重疊區(qū)域的樣本歸入到與所屬Canopy的Canopy中心距離最近的Canopy中，并計(jì)算各個(gè)Canopy的樣本與對(duì)應(yīng)Canopy中心和的均值，獲得K-means算法的初始聚類(lèi)中心。整個(gè)階段的算法設(shè)計(jì)流程如圖2、圖3所示。

圖2 最小方差Canopy-Map階段 圖3 最小方差Canopy-Reduce階段

任務(wù)2：該部分是傳統(tǒng)K-means算法在MapReduce編程框架的實(shí)現(xiàn)。

在Map階段，將來(lái)自于任務(wù)一的輸出作為全局的初始聚類(lèi)中心，通過(guò)對(duì)逐行讀取的數(shù)據(jù)按照就近原則進(jìn)行劃分歸類(lèi)；由于Map階段輸出的大量結(jié)果會(huì)寫(xiě)入磁盤(pán)，當(dāng)Reduce階段啟動(dòng)時(shí)需要通過(guò)網(wǎng)絡(luò)來(lái)獲取這些結(jié)果，嚴(yán)重消耗磁盤(pán)IO和網(wǎng)絡(luò)IO，為了優(yōu)化MapReduce中間產(chǎn)生的結(jié)果，設(shè)計(jì)了Combine階段，對(duì)于來(lái)自于Map階段的輸出，以Key相同的各個(gè)Value進(jìn)行合并；在Reduce階段，讀取每個(gè)Combine階段處理后的數(shù)據(jù)樣本個(gè)數(shù)N及各樣本維度的坐標(biāo)值，并將各維度的值對(duì)應(yīng)相加求均值，獲得新聚類(lèi)中心來(lái)更新原聚類(lèi)中心，然后進(jìn)入下一次迭代直至算法收斂。其K-means算法并行化設(shè)計(jì)如圖4所示。

圖4 K-means算法并行化設(shè)計(jì)

5 試驗(yàn)與分析

Hadoop平臺(tái)由1臺(tái)主節(jié)點(diǎn)和3臺(tái)從節(jié)點(diǎn)構(gòu)成，對(duì)來(lái)源于公開(kāi)UCI機(jī)器學(xué)習(xí)庫(kù)[15]中的數(shù)據(jù)集進(jìn)行試驗(yàn)分析。為了驗(yàn)證MVC-Kmeans算法的準(zhǔn)確性和收斂性,與傳統(tǒng)的K-means算法進(jìn)行了比較；同時(shí)，

表1 試驗(yàn)測(cè)試數(shù)據(jù)集

為了驗(yàn)證MVC-Kmeans算法處理大規(guī)模數(shù)據(jù)的優(yōu)勢(shì)，進(jìn)行了加速比和擴(kuò)展率的分析。

5.1 試驗(yàn)數(shù)據(jù)

表1列出了所選樣本的屬性、樣本數(shù)量以及類(lèi)別數(shù)。這些標(biāo)準(zhǔn)數(shù)據(jù)集用來(lái)準(zhǔn)確率量算法的聚類(lèi)質(zhì)量。

同時(shí)，為了符合MapReduce編程框架的數(shù)據(jù)格式要求，所有的數(shù)據(jù)以對(duì)形式表示，具體格式如表2所示。

表2 試驗(yàn)各階段數(shù)據(jù)格式

5.2 試驗(yàn)結(jié)果及分析

1)MVC-Kmeans算法與傳統(tǒng)K-means算法聚類(lèi)質(zhì)量的比較 利用表1數(shù)據(jù)集對(duì)優(yōu)化的算法在單機(jī)上進(jìn)行了檢驗(yàn)。為了保證檢驗(yàn)的結(jié)果可靠，每個(gè)樣本集在各算法下分別進(jìn)行10次，結(jié)果取10次試驗(yàn)的平均值，其試驗(yàn)結(jié)果如表3所示。

表3 樣本數(shù)據(jù)集試驗(yàn)結(jié)果

從表3中可以看出，MVC-Kmeans算法在所選數(shù)據(jù)集上聚類(lèi)精度均有提高，提高了4.11～25.91個(gè)百分點(diǎn)；誤差平方和與迭代次數(shù)均有降低，其降低幅度分別為4.70%～34.00%和16.67%～42.86%，可見(jiàn)MVC-Kmeans算法能獲得較好的聚類(lèi)質(zhì)量和更快的收斂速度

圖5 Iris數(shù)據(jù)集加速比測(cè)試結(jié)果 圖6 Iris數(shù)據(jù)集擴(kuò)展率測(cè)試結(jié)果

6 結(jié)語(yǔ)

筆者基于最小方差和Canopy算法優(yōu)化了K-means算法初始聚類(lèi)中心選取，提出了MVC-Kmeans聚類(lèi)算法。在Hadoop云計(jì)算平臺(tái)上，對(duì)MVC-Kmeans算法進(jìn)行了MapReduce并行化設(shè)計(jì)。在開(kāi)源數(shù)據(jù)集上相比傳統(tǒng)聚類(lèi)算法的試驗(yàn)結(jié)果表明，無(wú)論是在準(zhǔn)確率、迭代次數(shù)還是誤差平方和，MVC-Kmeans算法明顯優(yōu)于傳統(tǒng)K-means算法,能獲得更加穩(wěn)定的聚類(lèi)結(jié)果以及更快的收斂速度,并適于大規(guī)模數(shù)據(jù)的聚類(lèi)分析。但對(duì)于Canopy算法中閾值T1與T2的選擇不具備確定性，這將是下一步要開(kāi)展的工作。