云計算環(huán)境中面向大數(shù)據(jù)的改進(jìn)密度峰值聚類算法

鄭冬花，葉麗珠，隋 棟，黃錦濤

(1. 廣州商學(xué)院 信息技術(shù)與工程學(xué)院，廣東 廣州 511363，中國；2. 管理與科學(xué)大學(xué) 研究生院，雪蘭莪 莎阿南 40100，馬來西亞；3. 北京建筑大學(xué) 電氣與信息工程學(xué)院，北京 102406，中國；4. 澳門大學(xué) 科技學(xué)院，澳門 999078，中國)

for big data samples by reasonably setting the nearest neighbor valuekofK-nearest neighbor algorithm. Compared with common clustering algorithms, this algorithm has higher clustering accuracy and efficiency, and is suitable for clustering big data samples.

Keywords: big data; cloud computing; density peaks clustering;K-nearest neighbor algorithm; decision diagram

大數(shù)據(jù)分析技術(shù)的發(fā)展給各行業(yè)生產(chǎn)及管理帶來了新的發(fā)展機(jī)遇，通過大數(shù)據(jù)技術(shù)對企業(yè)運(yùn)行過程中的各項數(shù)據(jù)進(jìn)行挖掘分析，可以獲得企業(yè)自身乃至整個行業(yè)的運(yùn)行內(nèi)在關(guān)聯(lián)數(shù)據(jù)。聚類技術(shù)作為大規(guī)模數(shù)據(jù)統(tǒng)計分析的常用方法[1]，能夠有效挖掘海量異構(gòu)多維數(shù)據(jù)之間的關(guān)系，完成非標(biāo)簽的數(shù)據(jù)分類，為大數(shù)據(jù)各種模型分析提供數(shù)據(jù)支持。通過聚類可以將數(shù)據(jù)進(jìn)行有效歸類整理，提高數(shù)據(jù)的可用性[2]。在大數(shù)據(jù)聚類過程中，由于待聚類樣本量較大且樣本屬性結(jié)構(gòu)復(fù)雜，因此完成精準(zhǔn)聚類需要較強(qiáng)的數(shù)據(jù)運(yùn)算平臺支持。云計算作為解決大規(guī)模運(yùn)算問題的重要方式，可以為聚類算法的順利實施提供平臺支持。

當(dāng)前，關(guān)于云計算環(huán)境的大數(shù)據(jù)聚類研究較多。孫倩等[3]將人工蜂群算法用于聚類，并通過MapReduce云平臺實現(xiàn)并行聚類，解決了大規(guī)模數(shù)據(jù)聚類的問題。趙恩毅等[4]采用Hadoop云平臺實現(xiàn)了大規(guī)模數(shù)據(jù)的聚類。雖然他們都充分利用了云計算環(huán)境優(yōu)勢，解決了聚類樣本量大的問題，但是在數(shù)據(jù)聚類性能方面優(yōu)勢并不明顯。本文中對密度峰值聚類(DPC)算法進(jìn)行改進(jìn)后用于數(shù)據(jù)聚類，以提高聚類適應(yīng)度，采用K近鄰(KNN)算法對DCP算法進(jìn)行優(yōu)化。根據(jù)距離矩陣計算樣本點(diǎn)的密度值，繪制決策圖并選擇簇內(nèi)中心點(diǎn)，將剩余點(diǎn)根據(jù)密度值分配給離中心點(diǎn)距離最近的類，最后將KNN-DPC算法部署至Hadoop云計算平臺，用于解決大規(guī)模數(shù)據(jù)聚類的問題。

1 DPC算法

設(shè)N個樣本集X被劃分為m類，其數(shù)學(xué)表示為C={C1,C2, …,Cm}，C表示不同的類型，其中m≤N，且X=C1∪C2∪…∪Cm，Ci∩Cj=○/(i≠j)。

樣本點(diǎn)xi到樣本點(diǎn)xj的距離為rij，表達(dá)式[5]為

(1)

式中n為當(dāng)前維度。

樣本點(diǎn)xi的局部密度ρi[6-7]為

(2)

式中：rc為距離閾值；χ為密度核函數(shù)，

(3)

設(shè)核函數(shù)為高斯函數(shù)，則ρi可以表示[8]為

(4)

樣本點(diǎn)xi所對應(yīng)的最小距離δi表示為距xi最近且密度比xi大的點(diǎn)的距離[9]，即

(5)

根據(jù)式(4)、(5)確定點(diǎn)xi為簇的一個中心點(diǎn)。根據(jù)樣本點(diǎn)局部密度ρi和距離δi可以生成決策圖，密度值大和距離值大的被選為中心點(diǎn)，因此處于二維決策圖右上角的點(diǎn)為中心點(diǎn)。

為了防止出現(xiàn)ρi和δi中一個值較大、另外一個值較小的情況，一般采用下式計算約束閾值γi[10]：

γi=ρiδi

。

(6)

然后根據(jù)ρi、δi和γi值綜合選擇簇中心點(diǎn)進(jìn)行聚類。為了更加直觀地表達(dá)聚類中心點(diǎn)的選擇過程，以下采用圖示方式進(jìn)行說明。圖1所示為樣本點(diǎn)分布。圖中的樣本初始分布類別個數(shù)為3，根據(jù)各樣本點(diǎn)的特征分布采用式(1)計算各自距離，然后根據(jù)式(4)、(5)計算樣本點(diǎn)密度ρ和距離δ，生成的二維決策分布如圖2所示。圖中3個聚類中心點(diǎn)分別是10、12和25，選擇中心點(diǎn)之后，按照中心點(diǎn)個數(shù)對所有樣本點(diǎn)進(jìn)行分類，對其余待分類的點(diǎn)按照樣本點(diǎn)密度值選擇離中心點(diǎn)距離最近的類別進(jìn)行聚類。

圖1 密度峰值聚類算法的樣本點(diǎn)分布

圖2 基于密度峰值聚類算法生成的二維決策分布

2 DPC算法的KNN優(yōu)化

在DPC算法實現(xiàn)過程中，rc的選擇非常重要，它既決定了該算法的聚類精度，也影響著算法的執(zhí)行效率。由于DPC算法受rc影響較大，對樣本點(diǎn)分布密度不均衡的處理效果差，因此本文中采取KNN算法對DPC算法進(jìn)行優(yōu)化。

2.1 KNN算法

設(shè)整個待聚類的樣本集為X，樣本點(diǎn)xi∈X，dist(·)為密度距離函數(shù)，Nk(xi)表示距離xi第k近的點(diǎn)的集合。

xi的近鄰表示[11]如下：

KNN(xi)={xj∈X|dist(xi,xj)≤dist[xi,Nk(xi)]},

(7)

K近鄰的密度[12]為

(8)

(9)

采用KNN算法對DPC算法進(jìn)行優(yōu)化后，算法不需要再進(jìn)行DPC算法的參數(shù)選擇，但是需要對近鄰值k進(jìn)行選擇[13]。

2.2 KNN-DPC算法聚類流程

在獲得待聚類的樣本后，計算待聚類的樣本點(diǎn)兩兩之間的距離，生成距離矩陣集合，然后計算各樣本點(diǎn)密度及距離，選擇兩者較大的樣本點(diǎn)作為樣本聚類的中心點(diǎn)，然后計算剩余樣本點(diǎn)相對于各中心點(diǎn)的距離，選擇較近的中心點(diǎn)所屬類別作為各剩余樣本點(diǎn)的類別。KNN-DPC算法聚類流程如圖3所示。

圖3 K近鄰(KNN)-密度峰值聚類(DPC)算法聚類流程

3 實例仿真

為了驗證KNN-DPC算法在大數(shù)據(jù)聚類中的性能，進(jìn)行實例仿真。云計算的Hadoop平臺版本為12.1，仿真數(shù)據(jù)來源為某在線大型學(xué)習(xí)平臺，樣本集相關(guān)數(shù)據(jù)見表1。首先對不同樣本量進(jìn)行聚類仿真，生成DPC算法的決策圖并分析其性能；然后分別采用DPC算法和KNN-DPC算法進(jìn)行聚類操作，分析KNN算法對DPC算法的優(yōu)化程度。

表1 某在線學(xué)習(xí)平臺樣本集

仿真的云計算環(huán)境為Apache Hadoop 2.0平臺，將聚類算法打包成jar文件格式，并將數(shù)據(jù)樣本和jar文件提交至Hadoop云平臺。

3.1 不同樣本量的決策圖性能仿真

在DPC算法聚類過程中，核心內(nèi)容是獲得準(zhǔn)確、有效的決策圖，通過決策圖選擇合適的聚類類別中心點(diǎn)，然后根據(jù)樣本點(diǎn)與各中心點(diǎn)距離獲得樣本類別。采用KNN-DPC算法對4個樣本集求解的決策圖如圖4所示。

(a)樣本集1(b)樣本集2(c)樣本集3(d)樣本集4圖4 K近鄰(KNN)-密度峰值聚類(DPC)算法對4個樣本集求解的決策圖

由圖可以看出： 當(dāng)樣本個數(shù)為1 000時，大部分樣本點(diǎn)分布在δ<1的范圍內(nèi)，樣本點(diǎn)的ρ分布范圍較廣；當(dāng)樣本個數(shù)為2 000時，大部分樣本點(diǎn)仍分布在δ<1的范圍內(nèi)，但相比于樣本個數(shù)為1 000時，ρ較大的樣本點(diǎn)增多；當(dāng)樣本個數(shù)為3 000時，δ>1的樣本點(diǎn)逐漸增多，ρ較大的樣本點(diǎn)也在增加；當(dāng)樣本個數(shù)為4 000時，相比于前3種樣本量，處于δ>1且ρ>30的樣本點(diǎn)數(shù)顯著增加。圖中位于坐標(biāo)軸右上角的樣本點(diǎn)δ變化較小，但ρ明顯增大?？傊?，隨著樣本數(shù)量增加，樣本點(diǎn)局部密度ρ最大值增大，但δ變化較小，原因是在聚類中心數(shù)不變的情況下，樣本數(shù)量增加使得聚類中心閾值范圍內(nèi)的樣本點(diǎn)數(shù)增多，從而樣本點(diǎn)局部密度值增大。因為聚類中心點(diǎn)個數(shù)沒有發(fā)生變化，所以樣本數(shù)量增加對影響較小。

采用KNN-DPC算法對4個樣本集進(jìn)行聚類準(zhǔn)確率仿真，結(jié)果如表2所示。從表中可以看出，當(dāng)樣本個數(shù)從1 000增至4 000時，平均聚類準(zhǔn)確率提升了1.84%。隨著樣本數(shù)量增加，在進(jìn)行KNN算法的近鄰密度求解時能夠更全面地獲取樣本點(diǎn)的密度，促使DPC算法獲得更優(yōu)的聚類效果，從而提升了聚類的準(zhǔn)確率，表明KNN-DPC算法特別適用于大數(shù)據(jù)聚類。

表2 K近鄰-密度峰值聚類算法的

3.2 KNN算法的優(yōu)化性能

為了驗證KNN算法對DPC算法的優(yōu)化性能，分別采用DPC算法和KNN-DPC算法對樣本集4進(jìn)行聚類仿真，并求解2種算法的聚類準(zhǔn)確率及標(biāo)準(zhǔn)差，結(jié)果見圖5。

(a)聚類準(zhǔn)確率

(b)標(biāo)準(zhǔn)差KNN—K近鄰算法；DPC算法—密度峰值聚類算法。圖5 不同算法的聚類準(zhǔn)確率及標(biāo)準(zhǔn)差

從圖5(a)中可以看出，KNN-DPC算法的聚類準(zhǔn)確率明顯高于DPC算法的，KNN-DPC算法收斂時準(zhǔn)確率約為0.95，而DPC算法的僅為0.83。從聚類時間來看，穩(wěn)定時DPC算法的聚類時間約為24 s，而KNN-DPC算法的聚類時間約為27 s，原因是引入KNN優(yōu)化后，聚類需要消耗更多的時間，但兩者差距并不大。從圖5(b)中可以看出，DPC算法和KNN-DPC算法的聚類準(zhǔn)確率標(biāo)準(zhǔn)差快速減小直至穩(wěn)定，在迭代82次后，KNN-DPC算法達(dá)到穩(wěn)定，標(biāo)準(zhǔn)差收斂于0.23左右，而DPC算法迭代90次后標(biāo)準(zhǔn)差才收斂于0.43，因此從聚類穩(wěn)定性來看，KNN-DPC算法優(yōu)于DPC算法。

通過對比可以看出，KNN-DPC算法比DPC算法需要較長的聚類時間，但是前者迭代次數(shù)更少，原因是引入KNN算法優(yōu)化后，DPC算法能夠獲得更優(yōu)的距離閾值，在相同聚類準(zhǔn)確率閾值條件下，雖然KNN算法優(yōu)化需要消耗時間，但算法達(dá)到收斂時的迭代次數(shù)更少，降低了聚類模型復(fù)雜度。

3.3 不同算法的聚類性能

為了驗證不同算法的大數(shù)據(jù)聚類性能，分別采用常用的模糊聚類算法[14]、K均值聚類算法[15]、卷積神經(jīng)網(wǎng)絡(luò)(CNN)算法[16]和KNN-DPC算法對樣本進(jìn)行仿真，仿真樣本來自公開的UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫，如表3所示，不同算法的聚類準(zhǔn)確率和標(biāo)準(zhǔn)差結(jié)果如表4、5所示。

表3 聚類算法仿真數(shù)據(jù)集

表4 不同算法的聚類準(zhǔn)確率

表5 不同算法的聚類準(zhǔn)確率標(biāo)準(zhǔn)差

從表4中可以看出，4種算法對4個不同類別樣本集的聚類性能差異明顯，KNN-DPC算法在4個樣本集中的聚類準(zhǔn)確率均最高，CNN算法的次之，模糊聚類算法的最低。4種算法在Iris樣本集中的聚類準(zhǔn)確率最高，在Wine樣本集中的聚類準(zhǔn)確率最低，其中KNN-DPC算法在Iris樣本集中的聚類準(zhǔn)確率達(dá)到0.836 4。從表5可以看出，KNN-DPC算法和CNN算法收斂時的聚類準(zhǔn)確率標(biāo)準(zhǔn)差明顯小于模糊聚類算法和K均值算法的，其中KNN-DPC算法在Seeds樣本集中的聚類準(zhǔn)確率標(biāo)準(zhǔn)差最小，僅為0.237 3。

4 結(jié)語

本文中將KNN算法優(yōu)化的DPC算法應(yīng)用于大數(shù)據(jù)聚類，能夠獲得較高的聚類準(zhǔn)確率，通過合理設(shè)置KNN算法中參與局部密度計算的近鄰值k，求解DPC算法的核心參數(shù)樣本局部密度和距離，選擇兩者中數(shù)值較大的點(diǎn)作為聚類中心點(diǎn)進(jìn)行聚類，與常用聚類算法對比，KNN-DPC算法具有更高的聚類準(zhǔn)確率且聚類效率高，適用于大數(shù)據(jù)聚類。