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

趙玉明 舒紅平 魏培陽(yáng) 劉魁

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

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

中圖分類(lèi)號(hào)： TN911?34; TP301.6? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 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? 引? 言

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

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

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

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

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

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

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

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

1? 相關(guān)工作

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

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

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

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

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

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

1.2? Spark框架和算法流程

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

2? 基于Spark的聚類(lèi)算法（KL?Cluster）

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

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

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

2.2? 基于KL散度的聚類(lèi)過(guò)程

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

2.2.1? 概率矩陣的形成過(guò)程

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

2.2.2? 距離矩陣的形成過(guò)程

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

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

3? 實(shí)驗(yàn)與分析

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

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

3.2? 過(guò)程分析

3.2.1? 算法評(píng)價(jià)指標(biāo)

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

3.2.2? 預(yù)聚類(lèi)分析

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

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

3.2.3? 實(shí)驗(yàn)結(jié)果對(duì)比分析

本算法與K?means以及高斯混合聚類(lèi)運(yùn)行時(shí)間的對(duì)比見(jiàn)表3。

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

4? 結(jié)? 語(yǔ)

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

參考文獻(xiàn)

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

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

[3] 陳新泉，周靈晶，劉耀中.聚類(lèi)算法綜述[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í)的聚類(lèi)關(guān)鍵技術(shù)研究[D].成都：西南交通大學(xué)，2016.

[6] 王衛(wèi)衛(wèi)，李小平，馮象初，等.稀疏子空間聚類(lèi)綜述[J].自動(dòng)化學(xué)報(bào)，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)境下的新聚類(lèi)算法[J].計(jì)算機(jī)科學(xué)，2015，42（12）：247?250.

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

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

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

[14] 徐健銳，詹永照.基于Spark的改進(jìn)K?means快速聚類(lèi)算法[J].江蘇大學(xué)學(xué)報(bào)（自然科學(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] 陸一瀟，潘常春，白杰，等.基于對(duì)稱(chēng)KL散度的符號(hào)大數(shù)據(jù)動(dòng)態(tài)聚類(lèi)算法[C]//第八屆中國(guó)衛(wèi)星導(dǎo)航學(xué)術(shù)年會(huì)論文集.上海：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ù)測(cè)方法[J].小型微型計(jì)算機(jī)系統(tǒng)，2017，38（11）：2494?2498.

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