云計算環境中面向大數據的改進密度峰值聚類算法

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

(1. 廣州商學院 信息技術與工程學院，廣東 廣州 511363，中國；2. 管理與科學大學 研究生院，雪蘭莪 莎阿南 40100，馬來西亞；3. 北京建筑大學 電氣與信息工程學院，北京 102406，中國；4. 澳門大學 科技學院，澳門 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

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

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

1 DPC算法

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

樣本點xi到樣本點xj的距離為rij，表達式[5]為

(1)

式中n為當前維度。

樣本點xi的局部密度ρi[6-7]為

(2)

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

(3)

設核函數為高斯函數，則ρi可以表示[8]為

(4)

樣本點xi所對應的最小距離δi表示為距xi最近且密度比xi大的點的距離[9]，即

(5)

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

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

γi=ρiδi

。

(6)

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

圖1 密度峰值聚類算法的樣本點分布

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

2 DPC算法的KNN優化

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

2.1 KNN算法

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

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

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

(7)

K近鄰的密度[12]為

(8)

(9)

采用KNN算法對DPC算法進行優化后，算法不需要再進行DPC算法的參數選擇，但是需要對近鄰值k進行選擇[13]。

2.2 KNN-DPC算法聚類流程

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

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

3 實例仿真

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

表1 某在線學習平臺樣本集

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

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

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

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

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

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

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

3.2 KNN算法的優化性能

為了驗證KNN算法對DPC算法的優化性能，分別采用DPC算法和KNN-DPC算法對樣本集4進行聚類仿真，并求解2種算法的聚類準確率及標準差，結果見圖5。

(a)聚類準確率

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

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

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

3.3 不同算法的聚類性能

為了驗證不同算法的大數據聚類性能，分別采用常用的模糊聚類算法[14]、K均值聚類算法[15]、卷積神經網絡(CNN)算法[16]和KNN-DPC算法對樣本進行仿真，仿真樣本來自公開的UCI機器學習數據庫，如表3所示，不同算法的聚類準確率和標準差結果如表4、5所示。

表3 聚類算法仿真數據集

表4 不同算法的聚類準確率

表5 不同算法的聚類準確率標準差

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

4 結語

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