一種改進的自適應網格劃分的分布式聚類算法

蔡 莉,王浩宇,周 君,何 婧,劉俊暉

(云南大學 軟件學院,昆明 650091) E-mail：caili@ynu.edu.cn

1 引 言

聚類作為數(shù)據(jù)挖掘中的一個重要功能,廣泛應用于數(shù)據(jù)分析、圖像處理、用戶畫像等多個領域.聚類算法有多種分類,有基于劃分思想,比如K-means、K-medoids等,利用類內的點足夠近,類間的點足夠遠的原則進行聚類,但其需要事先指定簇數(shù),對于海量數(shù)據(jù)而言,準確的簇數(shù)往往難以確定[1].有基于密度思想,比如DBSCAN (Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise)、OPTICS (Ordering Points To Identify Clustering Structure)等,這類算法根據(jù)密度和最大半徑進行聚類,但其存在大量的距離計算并且對于參數(shù)的依賴性很大的問題[2,3].有基于網格思想,比如STING (Statistical Information Grid)、CLIQUE (CLustering In QUEst)等,它們將數(shù)據(jù)空間劃分為網格單元,把數(shù)據(jù)對象集映射至網格單元中,并計算每個單元的密度.相比于前二者,這類算法雖然在處理數(shù)據(jù)的速度上有所提升,但準確率又不能很好地保證[4].

Rodriguez和Laio提出了一種基于快速搜索和發(fā)現(xiàn)密度峰值的聚類算法(Clustering By Fast Search And Find Of Density Peaks),簡稱為DPC[5].DPC算法能夠自動識別簇中心并且適用于任何形狀的數(shù)據(jù)聚類,但是,對于各簇間密集程度差異較大的情況,并不能展現(xiàn)出很好的聚類效果.Xie等人于2016年提出一種基于DPC的改進算法FKNN-DPC (Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors)[6],其在DPC算法的基礎上,運用K近鄰思想,結合模糊權重進行數(shù)據(jù)點的再度分配,這種算法在大部分數(shù)據(jù)集上的效果是優(yōu)于DPC的,但卻增加了計算量,影響了運行效率.

單機版的聚類算法在計算性能和內存方面存在著難以解決的上限問題,很難滿足對海量數(shù)據(jù)的聚類需求,而分布式計算平臺則為處理海量數(shù)據(jù)的聚類提供了一種有效的途徑.現(xiàn)有的分布式聚類算法,比如分布式K-means、分布式DBSCAN等,在處理海量高維數(shù)據(jù)時,因為其本身實現(xiàn)涉及大量的高維距離計算,造成了大量的計算開銷,所以很大程度上也會降低分布式算法的運行效率[7,8].

為了彌補上述聚類算法的不足,本文提出了一種改進的自適應網格劃分的分布式聚類算法AMCBS (An Adaptive Meshing Clustering Algorithm Based On Spark Platform).該算法能夠根據(jù)數(shù)據(jù)分布自適應地劃分網格以獲得更好的聚類效果;同時,使用線性判別分析法處理高維數(shù)據(jù),提高了聚類的準確性和適用性.

2 相關工作

如何高效地劃分數(shù)據(jù)、合并局部簇一直是聚類算法的研究重點.汪晶等人利用樣本方差和最小方差的概念,提出了一種基于最小方差來獲取K-means聚類中心的分布式算法MVC-Kmeans[9],提升了原有K-means的準確率和運行效率.但算法參數(shù)的選取具有不確定性,其結果也易受參數(shù)的影響.寧建飛實現(xiàn)了DBSCAN聚類算法在Spark處理平臺上的應用[10],提高了DBSCAN算法處理海量數(shù)據(jù)的能力.然而,算法本身存在著大量的距離和密度計算,平均耗時較長.何仝等人基于密度峰值的高效分布式聚類算法EDDPC[11],根據(jù)局部敏感哈希對數(shù)據(jù)集進行劃分,并采用多次Hash方法修正分區(qū)后的結果,保證了聚類質量.但是,此算法涉及多個索引空間以及多次哈希表查詢,生成的索引文件的大小是原始數(shù)據(jù)大小的數(shù)十倍甚至數(shù)百倍.He等人提出的MR-DBSCAN算法[12]采用定長網格來劃分數(shù)據(jù),將數(shù)據(jù)點集轉移到了數(shù)據(jù)網格集,減少了原有計算量.不過,MR-DBSCAN算法也存在明顯的缺點：一是均勻劃分網格時,網格單元的大小實際難以確定,聚類效果易受網格單元大小的影響;二是算法在合并局部簇時采用增量的方式,計算效率仍然較低.Song等人和Huang等人分別提出了基于Hadoop平臺下的H-DBSCAN算法[13]和基于Spark平臺下的S-DBSCAN算法[14],通過分布式計算框架和加入網格邊界的擴展,來提高聚類結果的精確度和局部簇的合并效率.兩種算法都采用均分網格的方法來劃分數(shù)據(jù),這會導致最終的聚類結果會存在較大的誤差;其次,兩種算法也未充分考慮高維數(shù)據(jù)集的處理情況.

上述算法雖然在一定程度上提升了運行效率和準確度,但依舊存在諸多問題：例如在處理高維數(shù)據(jù),性能會大大降低,聚類效果不理想;算法易受參數(shù)的影響,整體穩(wěn)定性較低.

3 AMCBS聚類算法原理

3.1 相對熵

相對熵是評判兩個概率分布間差異的非對稱性度量單位,可以較為直觀地反映數(shù)據(jù)點分布趨近于均勻分布的情況.當數(shù)據(jù)分布越趨于均勻,相對熵值越大;當數(shù)據(jù)分布越趨于集中,相對熵值越小.本文利用相對熵的這一性質,用來區(qū)分網格區(qū)間的稠密程度,從而達到自適應劃分網格的目的.

定義1.在網格空間中,第i維上的單個網格的相對熵定義為：

(1)

其中,gij是第i維上的第j個網格,s(gij)是該網格里的數(shù)據(jù)數(shù)量占整個數(shù)據(jù)空間數(shù)據(jù)集的比例,Ni是第i維上的網格的數(shù)量.

定義2.在網格空間中,第i維上的全部網格的相對熵定義為：

(2)

其中,Gi是第i維上全部網格的集合.

定義3.合并網格的相對熵閾值T定義為：

(3)

其中,e(gij)是第i維的第j個網格的相對熵,Mi是第i維網格的相對熵中位數(shù).

AMCBS算法利用相對熵自適應劃分網格的過程如下：

Step1.設置初始網格長度gL,根據(jù)步長等分數(shù)據(jù)集Bi,構造網格空間中的第i維網格集合Gi;

Step2.根據(jù)公式計算第i維上的單個網格的相對熵eij;

Step3.計算第i維上的全部網格相對熵Ei以及相對熵閾值T;

Step4.遍歷網格空間第i維上所有的單個網格相對熵eij,根據(jù)相對熵閾值T,進行合并操作;

Step5.重復以上步驟,直至多維網格劃分完成為止.

3.2 決策圖

基于決策圖的聚類算法可以實現(xiàn)數(shù)據(jù)對象的快速聚類,核心思想是對聚類中心或密度峰值點進行相關的理論假設[15]：1)每個數(shù)據(jù)聚類簇組中的聚類中心擁有最大的局部密度參數(shù)值;2)不同數(shù)據(jù)聚類簇組的聚類中心之間有著比較遠的距離.決策圖聚類算法引入了兩個重要的參數(shù)變量,局部密度以及數(shù)據(jù)對象到最近大密度點的距離.

定義4.每一個網格gridi的密度dsi定義為：

dsi=countNum(gridi)

(4)

定義5.每一個網格gridi到更高密度網格對象gridj的最近距離作為網格對象的距離值dti定義為：

(5)

其中,dij為網格對象gridi中心位置到網格對象gridj中心位置的歐式距離.

假設網格集合中密度最高的網格對象為mx,其距離值為dtmx：

dtmx=max(dmx,j)

(6)

AMCBS算法會計算出每個網格單元的密度dsi與距離dti,依據(jù)位于簇心位置的網格對象會同時具有較高的密度ds和較大距離dt的特點,確定網格集合中簇的個數(shù)m以及簇中心的網格單元.

3.3 線性判別分析

線性判別分析(Linear Discriminant Analysis,LDA)的原理是通過正交變換,將一組可能存在相關性的變量進行降維處理,目標是將高維數(shù)據(jù)投影至低維后,同類的數(shù)據(jù)之間距離盡可能近、不同類數(shù)據(jù)之間距離盡可能遠[16].具體流程為：

Step1.計算類內均值mi與類間均值m,類內均值定義為：

(7)

類間均值定義為：

(8)

其中,mi和m均為k維向量;

Step2.計算類間散度矩陣Mb與類內散度矩陣Mw,類間散度矩陣定義為：

(9)

類內散度矩陣為：

(10)

類間散度矩陣Mb與類內散度矩陣Mw均為k階方陣;

Step4.對初始的特征值進行線性變換,選取前i個特征向量,組成投影矩陣：

W=[v1,…,vi]

(11)

則經過降維后的新樣本為：

[Y1,…,Yk]=WT[X1,…,Xk]

(12)

AMCBS在處理高維數(shù)據(jù)時,會通過LDA的方式將其統(tǒng)一轉化為低維數(shù)據(jù)(一般是二維或者三維),之后把轉化后的低維數(shù)據(jù)輸入進Spark應用程序中,執(zhí)行對應的處理單元.

3.4 Spark平臺

Spark是加州大學伯克利分校AMP (Algorithms,Machines,and People Lab)實驗室開發(fā)的一個基于內存計算的大數(shù)據(jù)并行計算框架.與MapReduce相比,Spark在處理大規(guī)模數(shù)據(jù)時,具有更高的效率,其主要原因是：一是把Job的中間結果直接存放至內存中,可以更好的適用于機器學習以及數(shù)據(jù)挖掘的多次迭代計算;二是引入了彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset,RDD),其本質上是分布在一組節(jié)點中的只讀對象集合,具備像MapReduce等數(shù)據(jù)流模型的容錯特性,可以允許進行重建操作;三是更加的通用,提供了多種數(shù)據(jù)集的操作類型;四是支持用戶自主確定分區(qū)策略,可以做到盡量少的在不同的執(zhí)行單元之間使用網絡交換數(shù)據(jù),減少運行時間[17,18].本文利用Spark平臺完成數(shù)據(jù)預處理、網格劃分、剩余點分配等操作,提升了算法的運行效率,流程框架如圖1所示.

圖1 AMCBS分布式算法的框架Fig.1 AMCBS distributed algorithm framework

AMCBS分布式算法主要處理步驟如下：

1)創(chuàng)建Spark對象,SparkContext的創(chuàng)建是運行Spark程序必要的開端.

2)從分布式文件存儲系統(tǒng)HDFS中讀取經過LDA降維后的低維數(shù)據(jù)集,并將其轉化為RDD格式.

3)計算出數(shù)據(jù)集各維度的邊界值,執(zhí)行網格劃分函數(shù),根據(jù)相對熵及其閾值,獲得多維自適應網格集,并將結果廣播至各個分區(qū)Partition.

4)計算每個網格單元最近的K個單位,采用SparkRDD的mapPartitions方法將函數(shù)作用到每個分區(qū).

5)計算網格聚類中心,采用reduceByKey函數(shù),分別計算同一簇下的樣本對象和sum和樣本數(shù)量count.

6)執(zhí)行不同方式的單元分配函數(shù),并進行迭代,直至符合分配標準為止.

7)迭代結束后,返回聚類結果集Cluster,算法結束.

4 AMCBS算法描述

AMCBS算法中所涉及到的變量定義如表1所示.

表1 AMCBS算法中的變量定義Table 1 Notations in AMCBS algorithm

AMCBS算法的偽代碼描述如表2所示.

表2 AMCBS算法偽代碼Table 2 Pseudocode of AMCBS algorithm

5 實 驗

本文的實驗環(huán)境是由3臺Linux Ubuntu 16.04操作系統(tǒng)的高性能服務器搭建出一個Spark分布式集群,其中包含一臺管理服務器(master)以及兩臺工作服務器(slave).集群中每個節(jié)點具體配置為CPU Intel i7-9800X,內存60GB,硬盤4TB.

5.1 實驗數(shù)據(jù)集

實驗數(shù)據(jù)集包括UCI機器學習標準數(shù)據(jù)集、奧利維蒂人臉數(shù)據(jù)集、GitHub文本數(shù)據(jù)集和D31數(shù)據(jù)集.各數(shù)據(jù)集的數(shù)據(jù)量、數(shù)據(jù)維度和類別數(shù)如表3所示.

表3 實驗數(shù)據(jù)集相關特征Table 3 Correlation characteristics of experimental data sets

為了驗證AMCBS算法的有效性,將該算法的聚類結果與分布式FKNN-DPC算法、EDDPC算法、分布式DBSCAN算法和基于網格聚類的S-DBSCAN算法進行對比.采用常用的評價指標準確率(Accuracy,ACC)、調整互信息(Adjusted Mutual Information,AMI)、調整蘭德指數(shù)(Adjusted Rand Index,ARI)和同質性(Homogeneity)等來衡量5種算法的聚類性能.其中,ACC是指正確聚類數(shù)據(jù)量占總體數(shù)據(jù)量的比例;AMI是基于互信息分數(shù)來衡量結果簇向量與真實簇向量相似度,AMI取值越大說明簇向量的相似度越高,AMI越接近于0則表示簇向量越是隨機分配;ARI是衡量兩個數(shù)據(jù)分布之間的吻合程度,取值范圍在[-1,1],值越大,表示聚類結果和真實情況越吻合;Homogeneity是指每個簇中正確分類的樣本數(shù)占該簇總樣本數(shù)的比例和.

5.2 實驗結果分析

5.2.1 UCI數(shù)據(jù)集對比實驗

UCI數(shù)據(jù)集包含了Iris數(shù)據(jù)集(4維)、Seeds數(shù)據(jù)集(7維)、Wine數(shù)據(jù)集(13維)和Libras movement數(shù)據(jù)集(90維),各算法在4個評價指標上的對比結果如圖2～圖5所示.可以發(fā)現(xiàn)：AMCBS算法在Iris數(shù)據(jù)集、Seeds數(shù)據(jù)集和Wine數(shù)據(jù)集上的評價結果均優(yōu)于其他算法,對于Libras movement數(shù)據(jù)集而言,AMCBS算法的ACC和Homogeneity指標也是最好的.

5.2.2 奧利維蒂人臉數(shù)據(jù)集

奧利維蒂人臉數(shù)據(jù)集是機器學習領域常用的一個標準數(shù)據(jù)集,40個志愿者提供了不同角度、不同表情的各10張面部圖片組成,共計400張.本文將每張人臉圖片轉換成向量(46×56),經過數(shù)據(jù)壓縮后作為輸入數(shù)據(jù),并進行聚類.這里,以前100張和全部的400張圖片作為數(shù)據(jù)集分別實驗,以驗證AMCBS算法的有效性.前100張圖片的具體實驗結果如圖6所示.

圖2 Iris數(shù)據(jù)集結果 Fig.2 Iris data set results圖3 Seeds數(shù)據(jù)集結果 Fig.3 Seeds data set results圖4 Wine數(shù)據(jù)集結果 Fig.4 Wine data set results

圖5 Libras數(shù)據(jù)集結果 Fig.5 Libras data set results圖6 人臉數(shù)據(jù)集前100張圖片結果 Fig.6 Results of the first 100 images in the face data set圖7 400張圖片結果 Fig.7 400 picture results

400張圖片具體實驗結果如圖7和圖8所示.由圖6～圖8可知：無論是前100張還是整個400張人臉圖片,AMCBS在評價指標和運行時間上都優(yōu)于對比算法.

圖8 400張圖片運行時間 Fig.8 Running time for 400 images圖9 GitHub數(shù)據(jù)集結果 Fig.9 GitHub sets results圖10 GitHub運行時間 Fig.10 GitHub running time

5.2.3 GitHub文本數(shù)據(jù)集

GitHub文本數(shù)據(jù)集是由3個類別的中文文本標簽所組成,包括8000個動物標簽、8000個食品標簽和8000個藥物標簽,共計24000個.本文在處理中文標簽時,采用了BERT模型,把詞轉換成向量(768維),作為輸入數(shù)據(jù)并進行聚類,具體實驗結果如圖9和圖10所示.可以發(fā)現(xiàn)：AMCBS算法對于處理較大規(guī)模文本數(shù)據(jù)集也有較好效果,在ACC、AMI和Homogeneity指標上均優(yōu)于其他4種算法,運行時間上也有明顯優(yōu)勢.

5.2.4 D31數(shù)據(jù)集

D31數(shù)據(jù)集包含了3100條2維數(shù)據(jù),共有31個類別,每個類別100條數(shù)據(jù),因該數(shù)據(jù)集本身就是2維數(shù)據(jù),所以就沒有通過LDA降維,而是直接作為輸入數(shù)據(jù)進行聚類,其實驗結果如圖11所示.可以看出：AMCBS算法在ACC、AMI、Homogeneity和運行時間上均優(yōu)于其他4個算法,并且ARI也處于較高水平.

圖11 D31數(shù)據(jù)集結果Fig.11 Results of D31 data set

為了進一步地說明算法對于大規(guī)模數(shù)據(jù)集的適應性,本文擴充了D31數(shù)據(jù)集,之后,分別選取3.1×104、3.1×105、3.1×106和3.1×107數(shù)量級的數(shù)據(jù)進行實驗,其結果如圖12所示.可以看出：隨著數(shù)據(jù)集的逐步增大,AMCBS算法與其他4種分布式算法相比,運行時間大幅減少,效率提升明顯.

6 結束語

為了解決現(xiàn)有算法在運行時間和正確率上存在的問題,本文提出了一種改進的高效分布式聚類算法,通過分布式技術和自適應網格劃分的思想來處理高維海量數(shù)據(jù).其主要工作有：1)根據(jù)數(shù)據(jù)點在空間的分布狀況,利用相對熵進行自適應網格劃分;2)利用決策圖的思想,根據(jù)各單元距離密度值,確定網格集合中的各個簇;3)引入了線性判別分析,對于高維數(shù)據(jù),通過降維手段,進行預處理;4)為了提高算法的聚類準確度,采用了階段式分配策略;5)結合Spark計算平臺,使用并行化合并局部簇,從而進一步提升網格聚類算法的并行化效率.通過與4種分布式算法在UCI數(shù)據(jù)集、人臉圖片數(shù)據(jù)集和文本數(shù)據(jù)集等進行對比,可知AMCBS算法對于海量數(shù)據(jù)和高維數(shù)據(jù)均具有較好的有效性和處理性能.不過,在剩余點的分配過程中,網格輻射范圍的選取會在一定程度上影響聚類結果,目前的解決辦法是多次實驗以獲得最好的效果;此外,本文沒有解決在不平衡數(shù)據(jù)融合下的聚類問題,這兩點將是論文下一步的研究重點.

圖12 各算法在擴充數(shù)據(jù)集上的運行時間Fig.12 Running time under the extended data sets