趙玉明 舒紅平 魏培陽 劉魁

摘要： 在數(shù)據(jù)挖掘中，針對聚類過程中數(shù)據(jù)存在的稀疏性問題，如果仍用傳統(tǒng)的歐氏距離作為聚類指標(biāo)，聚類的質(zhì)量和效率將會受到一定的影響。受到信息論中KL散度的啟發(fā)，文中提出一種基于Spark開源數(shù)據(jù)框架下利用KL散度的相似性度量方法，對目前使用的聚類算法進(jìn)行優(yōu)化。首先，通過預(yù)聚類，對數(shù)據(jù)的整體分布進(jìn)行分析;然后，借助KL散度作為聚類的距離指標(biāo)，充分利用數(shù)據(jù)集中元素提供的信息來度量不同數(shù)據(jù)集的相互關(guān)系，指導(dǎo)數(shù)據(jù)的聚類，在一定程度上改善了數(shù)據(jù)分布稀疏性的問題。整個過程基于Spark分布式數(shù)據(jù)處理框架，充分利用集群的能力對數(shù)據(jù)進(jìn)行處理，提升數(shù)據(jù)處理的準(zhǔn)確度和算法的時間效率;同時利用KL散度作為數(shù)據(jù)聚類距離指標(biāo)，以充分考慮數(shù)據(jù)內(nèi)部蘊(yùn)藏的信息，使得聚類的質(zhì)量得到了提升。最后通過一個實驗來驗證所提算法的有效性。

關(guān)鍵詞： 聚類算法優(yōu)化; Spark; 數(shù)據(jù)分布分析; 數(shù)據(jù)聚類; 聚類分析; 數(shù)據(jù)處理

中圖分類號： TN911?34; TP301.6? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）08?0052?04

Optimization and implementation of clustering algorithm based on Spark

ZHAO Yuming1，2， SHU Hongping1，2， WEI Peiyang1，2， LIU Kui1，2

（1. College of Software Engineering， Chengdu University of Information Technology， Chengdu 610225， China;

2. Key Laboratory of Software Automatic Generation and Intelligent Information Service， Chengdu University of Information Technology， Chengdu 610225， China）

Abstract： In the data mining， if the traditional Euclidean distance is still used as the clustering index to deal with the data sparseness in the clustering process， the clustering quality and efficiency would be affected to a certain extent. On the basis of the inspiration of KL divergence in information theory， a similarity measure method using KL divergence and based on Spark open source data framework is proposed to optimize the clustering algorithm used at present. The entire distribution of data is analyzed by pre?clustering.? By taking the KL divergence as the distance index of clustering， the information provided by elements in data sets is fully utilized to measure the mutual relationship of different data sets and guide the data′s clustering， by which the sparseness of data distribution is improved to a certain extent. The whole process is based on Spark distributed data processing framework， by which the data is processed by making full use of the cluster ability to improve the accuracy of data processing and the time efficiency of the algorithm. KL divergence is used as the distance index of data clustering， so that the information hided in the data is fully considered， which may make the clustering quality improved. An experiment was carried out to verify the effectiveness of the proposed algorithm.

Keywords： clustering algorithm optimization; Spark; data distribution analysis; data clustering; clustering analysis; data processing

0? 引? 言

作為知識庫發(fā)現(xiàn)的一個步驟，數(shù)據(jù)挖掘可以幫助人們從大型數(shù)據(jù)庫中提取模式、關(guān)聯(lián)、變化、異常、及有意義的結(jié)構(gòu)[1]。聚類主要源于很多學(xué)科領(lǐng)域，包括：數(shù)學(xué)、計算機(jī)科學(xué)、統(tǒng)計學(xué)、生物學(xué)和經(jīng)濟(jì)學(xué)[2]等。

傳統(tǒng)的聚類算法大致可以分為劃分聚類、層次聚類、密度聚類等。近年來，量子聚類、譜聚類、粒度聚類等也流行起來。

在劃分的聚類方法中，通過構(gòu)造一個迭代過程來優(yōu)化目標(biāo)函數(shù)，當(dāng)優(yōu)化到目標(biāo)函數(shù)的最小值或極小值的時候，就可以得到一系列不相交的子集，這時每一個子集就是一個聚類[3]。其中，K?means聚類算法就是典型的代表，而在此過程中會遇到如下的三個問題：

1） 如果數(shù)據(jù)維度非常高，并且呈現(xiàn)出相當(dāng)大的稀疏性。傳統(tǒng)的K?means聚類算法，更多考慮共同項之間的距離，忽略非共同項之間可能蘊(yùn)藏的信息。尤其在數(shù)據(jù)分布呈現(xiàn)極度稀疏性的時候，缺乏考慮數(shù)據(jù)上下文之間的關(guān)系，無法達(dá)到準(zhǔn)確的聚類效果[4]。

2） 在使用K?means進(jìn)行聚類時，無法很好地衡量出不同數(shù)據(jù)集中數(shù)據(jù)的依賴性以及分布不均衡特點。同時缺乏從數(shù)據(jù)的整體分布進(jìn)行聚類，導(dǎo)致聚類的質(zhì)量產(chǎn)生嚴(yán)重的影響[5]。

3） 基于劃分的聚類方法，而對于極不規(guī)則、大小相差很大的數(shù)據(jù)集表現(xiàn)的非常不理想。尤其初始聚類中心和聚類數(shù)目直接影響了聚類的準(zhǔn)確率。同時，數(shù)據(jù)的并發(fā)處理效率很低，無法滿足目前大數(shù)據(jù)處理的要求[6]。

在信息論中，KL散度[5]用來衡量一個分布來擬合另一個分布時候產(chǎn)生的信息損耗。使用KL散度可以將統(tǒng)計學(xué)中的概率分布引入進(jìn)來，充分考慮數(shù)據(jù)整體的分布特性以及數(shù)據(jù)集中不同數(shù)據(jù)提供的信息。Spark作為新興的、應(yīng)用范圍最為廣泛的大數(shù)據(jù)處理開源框架引起了廣泛的關(guān)注[7]。相比于Hadoop，Spark在設(shè)計之初就是基于內(nèi)存而設(shè)計，這樣的分布式框架可以將中間數(shù)據(jù)處理結(jié)果存放在內(nèi)存中，每次迭代處理數(shù)據(jù)的時候不需要重復(fù)讀取HDFS數(shù)據(jù)，降低了I/O負(fù)荷;同時基于Spark的聚類算法設(shè)計基于Spark DAG的任務(wù)調(diào)度執(zhí)行機(jī)制，要優(yōu)于Hadoop MapReduce的迭代執(zhí)行機(jī)制[8]。

基于以上分析，在面對稀疏數(shù)據(jù)集的聚類過程中，提出基于Spark的開源大數(shù)據(jù)處理框架，利用KL散度作為聚類指標(biāo)，對數(shù)據(jù)進(jìn)行聚類。通過這樣的方式，提高了聚類的準(zhǔn)確度和算法的執(zhí)行效率。

1? 相關(guān)工作

1.1? KL散度的引入及數(shù)據(jù)特征分析

相對熵又稱互熵，交叉熵，鑒別信息。Kullback熵，Kullback?Leible散度（即KL散度）等。設(shè)P（x）和Q（x）是X取值的兩個概率概率分布，則P對Q的相對熵為：

相對熵突出的特點是非對稱性，也就是[D（PQ）]和[DQP]是不相等的，但是表示的都是P和Q之間的距離，在本文的算法設(shè)計中采取兩者的平均值作為兩個簇或者類之間的距離。

以下介紹數(shù)據(jù)分布，在聚類過程中，假設(shè)要聚類的數(shù)據(jù)為：X={X1，X2，…，Xn-1，Xn}。X是n個Rx（x=1，2，…，m-1，m）空間的數(shù)據(jù)。其基本的分布見表1。

設(shè)N是數(shù)據(jù)集的個數(shù)，M是每個數(shù)據(jù)的最大空間維度，V表示非零數(shù)據(jù)的個數(shù)，K表示此數(shù)據(jù)集的稀疏度，則：

通常認(rèn)為K值小于5%的時候，可以將這類數(shù)據(jù)集歸納為稀疏性數(shù)據(jù)。

1.2? Spark框架和算法流程

Apache Spark[9]是加州大學(xué)伯克利分校的AMPLabs開發(fā)的開源分布式輕量級通用計算框架。整個聚類過程基于Spark框架，在設(shè)計上，首先，利用Spark分布式開源框架，將幾臺PC機(jī)連接起來，形成主從式的控制結(jié)構(gòu)。主節(jié)點對從節(jié)點進(jìn)行任務(wù)調(diào)度、分發(fā)和容錯，從節(jié)點實現(xiàn)并行計算，此結(jié)構(gòu)被證明是一個擁有高可靠、高并發(fā)、高性能計算能力的分布式結(jié)構(gòu)。然后，利用普通機(jī)上的HDFS存儲系統(tǒng)對數(shù)據(jù)進(jìn)行存儲。最后利用KL散度作為數(shù)據(jù)聚類的距離指標(biāo)，完善對數(shù)據(jù)聚類的質(zhì)量控制。針對以上分析，本文提出基于Spark的算法執(zhí)行流程，如圖1所示。

2? 基于Spark的聚類算法（KL?Cluster）

2.1? 數(shù)據(jù)預(yù)聚類

首先，掃描整體數(shù)據(jù)，對稀疏數(shù)據(jù)集上的數(shù)據(jù)進(jìn)行預(yù)聚類。預(yù)聚類是完成對整體數(shù)據(jù)所屬類別的確定過程，可以在整體上分析數(shù)據(jù)分布情況。

文獻(xiàn)[1]提供了一種基于層次思想的計算方法，即COPS。本文在數(shù)據(jù)的預(yù)聚類階段采用此種方法，對數(shù)據(jù)的整體分布進(jìn)行分析。通過預(yù)聚類形成的Q（C）曲線，可以直觀地看到每個數(shù)據(jù)分布的依賴性、噪聲影響以及邊界模糊等情況。完整的設(shè)計過程可以參看文獻(xiàn)[1]。

2.2? 基于KL散度的聚類過程

在聚類過程中，主要分為根據(jù)概率矩陣的形成過程、距離矩陣的形成過程以及循環(huán)迭代過程。

2.2.1? 概率矩陣的形成過程

通過預(yù)聚類過程，離散數(shù)據(jù)集上的數(shù)據(jù)分為k（k=1，2，…，k-1，k）類。然后循環(huán)統(tǒng)計簇中數(shù)據(jù)在k類數(shù)據(jù)上分頻率分布，這樣就會形成一個n×k的概率矩陣。形成的概率矩陣如下：

2.2.2? 距離矩陣的形成過程

根據(jù)以上的概率矩陣，分別計算矩陣中任意一行和其他一行之間的KL距離，形成整體數(shù)據(jù)集上的KL矩陣。在KL散度介紹中也談到了KL具有非對稱性，這里采用任意兩行相互計算距離的平均值作為實際的KL值[10]。剩下的部分都用0來填充，最后形成上三角概率矩陣如下：

通過形成的KL矩陣，將距離矩陣中小于一定精度的值所代表的兩行數(shù)據(jù)合并[11]。通過以上過程完成對數(shù)據(jù)集的一次合并，形成新的數(shù)據(jù)集。對合并后形成的數(shù)據(jù)集，按照上面的過程形成新的概率矩陣和距離矩陣，再次完成數(shù)據(jù)的合并。通過不斷重復(fù)，直到KL矩陣無法達(dá)到合并數(shù)據(jù)的精度后，完成所有數(shù)據(jù)集的聚類。

3? 實驗與分析

3.1? 數(shù)據(jù)選擇

為了驗證本算法的有效性，并且本算法主要針對的是離散性數(shù)據(jù)集。一方面，引用公開數(shù)據(jù)集MovieLens中最新的數(shù)據(jù)，ML?Lastest?Small和Yahoo Music作為數(shù)據(jù)集;另一方面，在The? Movie? DB中下載數(shù)據(jù)，然后將數(shù)據(jù)清洗、整理，得到179位觀眾對國內(nèi)外將近180部電影評分的數(shù)據(jù)集，這里簡稱為MVD，來驗證算法的有效性。數(shù)據(jù)基本情況見表2。

3.2? 過程分析

3.2.1? 算法評價指標(biāo)

在算法準(zhǔn)確率和效率上，使用本文提供的算法和Spark MLlib中的K?means算法、高斯混合聚類算法進(jìn)行對比。在同樣使用Spark框架下對比出不同算法的準(zhǔn)確率和時間效率。

3.2.2? 預(yù)聚類分析

首先對每個數(shù)據(jù)集上的數(shù)據(jù)集進(jìn)行預(yù)聚類，根據(jù)文獻(xiàn)[1]的方法，得到的實驗結(jié)果如圖2～圖4所示。

通過預(yù)聚類可以發(fā)現(xiàn)，聚類數(shù)目從最優(yōu)變化到變到兩邊次優(yōu)的時候，聚類質(zhì)量發(fā)生大幅度下降。在圖2和圖3中，可以明顯看到有兩個基本重合的簇，數(shù)據(jù)存在一定的關(guān)聯(lián)性。圖4中，在達(dá)到最佳的聚類數(shù)10之前，曲線的變化很小，說明數(shù)據(jù)由于密度分布不均勻、邊界模糊的情況，尤其是在聚類數(shù)目達(dá)到8的時候，Q（C）曲線出現(xiàn)了一定的上升趨勢。

3.2.3? 實驗結(jié)果對比分析

本算法與K?means以及高斯混合聚類運(yùn)行時間的對比見表3。

從以上的實驗結(jié)果可以看出，同樣是基于Spark的KL?Cluster算法相比于Spark MLlib中提供的K?means和K?Prototypes，聚類的準(zhǔn)確度上有了明顯的提高。而運(yùn)行時間在某種程度上增加，時間差距在0.08～0.67 s之間。原因是在預(yù)聚類中占用了一段時間，雖然犧牲了一定的時間效率，但是不影響整個算法的執(zhí)行時間效率。但是針對稀疏性的數(shù)據(jù)集上的聚類質(zhì)量得到大幅度的提高。

4? 結(jié)? 語

聚類算法是機(jī)器學(xué)習(xí)算法中經(jīng)常使用的一類算法，傳統(tǒng)的K?means算法并不能很好地處理數(shù)據(jù)稀疏性問題，在聚類的質(zhì)量上產(chǎn)生嚴(yán)重的誤差。為了解決此問題，本文提出了一種基于Spark的聚類算法。整個執(zhí)行過程是基于Spark的分布式數(shù)據(jù)處理框架，首先通過預(yù)聚類綜合考慮了數(shù)據(jù)的分布情況，對將整體的數(shù)據(jù)進(jìn)行聚類，劃分類別;然后根據(jù)的數(shù)據(jù)分布情況構(gòu)建概率矩陣，計算KL矩陣;最后通過KL矩陣得到數(shù)據(jù)聚類。通過這樣的迭代過程完成聚類。通過這種方式可以減少引言中提到的三個問題，提升對稀疏數(shù)據(jù)集中聚類質(zhì)量和效率，同時基于Spark的分布式處理框架提升了數(shù)據(jù)處理的并行度。

參考文獻(xiàn)

[1] 陳黎飛，姜青山，王聲瑞.基于層次劃分的最佳聚類數(shù)確定方法[J].軟件學(xué)報，2008，19（1）：62?72.

[2] 無恒，李文杰，蔣旻.引入信息熵的CURE聚類算法[J].計算機(jī)應(yīng)用研究，2017，34（8）：2303?2305.

[3] 陳新泉，周靈晶，劉耀中.聚類算法綜述[J].集成技術(shù)，2017，6（3）：41?49.

[4] LI Jundong， CHENG Kewei， WANG Suhang， et al. Feature selection： a data perspective [J]. ACM computing surveys， 2018， 50（6）： 194.

[5] 楊琪.基于深度學(xué)習(xí)的聚類關(guān)鍵技術(shù)研究[D].成都：西南交通大學(xué)，2016.

[6] 王衛(wèi)衛(wèi)，李小平，馮象初，等.稀疏子空間聚類綜述[J].自動化學(xué)報，2015，41（8）：1373?1384.

[7] MENG X R， BRANDLEY J， YAVUZ B， et al. MLlib： machine learning in apache spark [J]. Journal of machine learning research， 2016， 17（1）： 1235?1241.

[8] ZAHARIA M， CHOWDHURY M， FRANKLIN M J， et al. Spark： cluster computing with working sets [J]. Hot cloud， 2010（6）： 1?6.

[9] SALLOUM S， DAUTOV R， CHEN X J， et al. Big data analytics on apache spark [J]. International journal of data science and analytics， 2016， 1（3/4）： 145?164.

[10] 李斌，王勁松，黃瑋.一種大數(shù)據(jù)環(huán)境下的新聚類算法[J].計算機(jī)科學(xué)，2015，42（12）：247?250.

[11] 張文，姜祎盼，張思光，等.基于經(jīng)驗分布和K散度的協(xié)同過濾推薦質(zhì)量評價研究[J].計算機(jī)應(yīng)用研究，2018，36（9）：17?24.

[12] 何玉林，黃哲學(xué).大規(guī)模數(shù)據(jù)集聚類算法的研究進(jìn)展[J].深圳大學(xué)學(xué)報（理學(xué)版），2019，36（1）：4?17.

[13] 許明杰，蔚承建，沈航.基于Spark的并行K?means算法研究[J].微電子學(xué)與計算機(jī)，2018，35（5）：95?98.

[14] 徐健銳，詹永照.基于Spark的改進(jìn)K?means快速聚類算法[J].江蘇大學(xué)學(xué)報（自然科學(xué)版），2018，39（3）：316?323.

[15] XIE M， HU J K， GUO S， et al. Distributed segment?based anomaly detection with Kullback?Leibler divergence in wireless sensor networks [J]. IEEE transactions on information forensics & security， 2017， 12（1）： 101?110.

[16] WILSON R C， HANCOCK E R， PEKALSKA E， et al. Spherical and hyperbolic embeddings of data [J]. IEEE transactions on pattern analysis and machine intelligence， 2014， 36（11）： 2255?2269.

[17] AHN H S， YU W. Environmental adaptive RSSI based indoor localization [J]. IEEE transactions on automation science and engineering， 2009， 6（4）： 626?633.

[18] 陸一瀟，潘常春，白杰，等.基于對稱KL散度的符號大數(shù)據(jù)動態(tài)聚類算法[C]//第八屆中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會論文集.上海：Springer，2017：89?94.

[19] SOLTANOLKOTABI M， CAND′ES E J. A geometric analysis of subspace clustering with outliers [J]. The annals of statistics， 2012， 40（4）： 2195?2238.

[20] 楊杰，燕雪峰，張德平.考慮KL散度的多源軟件缺陷預(yù)測方法[J].小型微型計算機(jī)系統(tǒng)，2017，38（11）：2494?2498.

[21] 王永，鄧江洲.基于KL散度的用戶相似性協(xié)同過濾算法[J].北京郵電大學(xué)學(xué)報，2017，40（2）：110?114.

[22] AL?KAHTANI M S， KARIM L. An efficient distributed algorithm for big data processing [J]. Arabian journal for science & engineering， 2017（42）： 3149?3157.

[23] GOU Jie， MA Zitang. Parallel CSA?FCM clustering algorithm based on Mapreduce [J]. Computer engineering and applications， 2016， 52（1）： 66?70.

[24] PATEL V M， VAN NGUYEN H， VIDAL R. Latent space sparse subspace clustering [C]// Proceedings of 2013 IEEE International Conference on Computer Vision. Sydney： IEEE， 2013： 225?232.

[25] FAHAD A， ALSHATRI N， TARI Z， et al. A survey of clustering algorithms for big data： taxonomy and empirical analysis [J]. IEEE transactions on emerging topics in computing， 2014， 2（3）： 267?279.

[26] ZALIK K R. An efficient k?means clustering algorithm [J]. Pattern recognition letters， 2008， 29（9）： 1385?1391.

[27] ZHAO Q， MENG D Y， XU Z B， et al. Robust principal component analysis with complex noise [C]// Proceedings of 31st International Conference on Machine Learning. Beijing： IEEE， 2014： 55?63.

[28] VILLALBA L J G， OROZCO A L S， CORRIPIO J R. Smartphone image clustering [J]. Expert systems with applications， 2015， 42（4）： 1927?1940.

[29] LU C Y， FENG J S， LIN Z C， et al. Correlation adaptive subspace segmentation by Trace Lasso [C]// Proceedings of 2013 IEEE International Conference on Computer Vision. Sydney： IEEE， 2013： 1345?1352.