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

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

1 引 言

聚類作為數(shù)據(jù)挖掘中的一個重要功能,廣泛應(yīng)用于數(shù)據(jù)分析、圖像處理、用戶畫像等多個領(lǐng)域.聚類算法有多種分類,有基于劃分思想,比如K-means、K-medoids等,利用類內(nèi)的點(diǎn)足夠近,類間的點(diǎn)足夠遠(yuǎn)的原則進(jìn)行聚類,但其需要事先指定簇數(shù),對于海量數(shù)據(jù)而言,準(zhǔn)確的簇數(shù)往往難以確定[1].有基于密度思想,比如DBSCAN (Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise)、OPTICS (Ordering Points To Identify Clustering Structure)等,這類算法根據(jù)密度和最大半徑進(jìn)行聚類,但其存在大量的距離計算并且對于參數(shù)的依賴性很大的問題[2,3].有基于網(wǎng)格思想,比如STING (Statistical Information Grid)、CLIQUE (CLustering In QUEst)等,它們將數(shù)據(jù)空間劃分為網(wǎng)格單元,把數(shù)據(jù)對象集映射至網(wǎng)格單元中,并計算每個單元的密度.相比于前二者,這類算法雖然在處理數(shù)據(jù)的速度上有所提升,但準(zhǔn)確率又不能很好地保證[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的改進(jìn)算法FKNN-DPC (Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors)[6],其在DPC算法的基礎(chǔ)上,運(yùn)用K近鄰思想,結(jié)合模糊權(quán)重進(jìn)行數(shù)據(jù)點(diǎn)的再度分配,這種算法在大部分?jǐn)?shù)據(jù)集上的效果是優(yōu)于DPC的,但卻增加了計算量,影響了運(yùn)行效率.

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

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

2 相關(guān)工作

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

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

3 AMCBS聚類算法原理

3.1 相對熵

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

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

(1)

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

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

(2)

其中,Gi是第i維上全部網(wǎng)格的集合.

定義3.合并網(wǎng)格的相對熵閾值T定義為：

(3)

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

AMCBS算法利用相對熵自適應(yīng)劃分網(wǎng)格的過程如下：

Step1.設(shè)置初始網(wǎng)格長度gL,根據(jù)步長等分?jǐn)?shù)據(jù)集Bi,構(gòu)造網(wǎng)格空間中的第i維網(wǎng)格集合Gi;

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

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

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

Step5.重復(fù)以上步驟,直至多維網(wǎng)格劃分完成為止.

3.2 決策圖

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

定義4.每一個網(wǎng)格gridi的密度dsi定義為：

dsi=countNum(gridi)

(4)

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

(5)

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

假設(shè)網(wǎng)格集合中密度最高的網(wǎng)格對象為mx,其距離值為dtmx：

dtmx=max(dmx,j)

(6)

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

3.3 線性判別分析

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

Step1.計算類內(nèi)均值mi與類間均值m,類內(nèi)均值定義為：

(7)

類間均值定義為：

(8)

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

Step2.計算類間散度矩陣Mb與類內(nèi)散度矩陣Mw,類間散度矩陣定義為：

(9)

類內(nèi)散度矩陣為：

(10)

類間散度矩陣Mb與類內(nèi)散度矩陣Mw均為k階方陣;

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

W=[v1,…,vi]

(11)

則經(jīng)過降維后的新樣本為：

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

(12)

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

3.4 Spark平臺

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

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

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

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

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

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

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

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

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

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

4 AMCBS算法描述

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

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

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

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

5 實(shí) 驗

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

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

實(shí)驗數(shù)據(jù)集包括UCI機(jī)器學(xué)習(xí)標(biāo)準(zhǔn)數(shù)據(jù)集、奧利維蒂人臉數(shù)據(jù)集、GitHub文本數(shù)據(jù)集和D31數(shù)據(jù)集.各數(shù)據(jù)集的數(shù)據(jù)量、數(shù)據(jù)維度和類別數(shù)如表3所示.

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

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

5.2 實(shí)驗結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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