基于Spark的聚類算法優(yōu)化與實現(xiàn)

趙玉明 舒紅平 魏培陽 劉魁

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

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

中圖分類號： TN911?34; TP301.6? ? ? ? ? ? ? ? ?文獻標識碼： 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ù)據挖掘可以幫助人們從大型數(shù)據庫中提取模式、關聯(lián)、變化、異常、及有意義的結構[1]。聚類主要源于很多學科領域，包括：數(shù)學、計算機科學、統(tǒng)計學、生物學和經濟學[2]等。

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

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

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

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

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

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

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

1? 相關工作

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

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

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

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

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

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

1.2? Spark框架和算法流程

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

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

2.1? 數(shù)據預聚類

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

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

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

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

2.2.1? 概率矩陣的形成過程

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

2.2.2? 距離矩陣的形成過程

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

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

3? 實驗與分析

3.1? 數(shù)據選擇

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

3.2? 過程分析

3.2.1? 算法評價指標

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

3.2.2? 預聚類分析

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

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

3.2.3? 實驗結果對比分析

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

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

4? 結? 語

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

參考文獻

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

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

[3] 陳新泉，周靈晶，劉耀中.聚類算法綜述[J].集成技術，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] 楊琪.基于深度學習的聚類關鍵技術研究[D].成都：西南交通大學，2016.

[6] 王衛(wèi)衛(wèi)，李小平，馮象初，等.稀疏子空間聚類綜述[J].自動化學報，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ù)據環(huán)境下的新聚類算法[J].計算機科學，2015，42（12）：247?250.

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

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

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

[14] 徐健銳，詹永照.基于Spark的改進K?means快速聚類算法[J].江蘇大學學報（自然科學版），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ù)據動態(tài)聚類算法[C]//第八屆中國衛(wèi)星導航學術年會論文集.上海：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散度的多源軟件缺陷預測方法[J].小型微型計算機系統(tǒng)，2017，38（11）：2494?2498.

[21] 王永，鄧江洲.基于KL散度的用戶相似性協(xié)同過濾算法[J].北京郵電大學學報，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.