基于Spark 的大數(shù)據(jù)聚類研究及系統(tǒng)實(shí)現(xiàn)

王 磊 鄒恩岑 曾 誠(chéng) 奚雪峰 陸 悠

(1.蘇州科技大學(xué)電子與信息工程學(xué)院，蘇州，215009；2. 蘇州市虛擬現(xiàn)實(shí)智能交互及應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，蘇州，215009；3.蘇州科技大學(xué)普開大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，蘇州，215009；4. 昆山市公安局指揮中心，蘇州，215300)

引 言

聚類是數(shù)據(jù)挖掘研究的重要方法之一。大數(shù)據(jù)聚類能有效支撐如客戶群細(xì)分、文本主題發(fā)現(xiàn)和信息檢索等大量實(shí)際應(yīng)用[1]。傳統(tǒng)聚類方法的重要假設(shè)是數(shù)據(jù)能夠一次性地載入內(nèi)存，然而大部分聚類算法都是迭代型算法，下一輪計(jì)算依賴于上一輪的計(jì)算結(jié)果。隨著數(shù)據(jù)量的急劇增大，單機(jī)的內(nèi)存和運(yùn)算能力已經(jīng)不能滿足算法要求，需要人們利用分布式計(jì)算系統(tǒng)進(jìn)行并行處理。Hadoop平臺(tái)的MapReduce計(jì)算框架在迭代時(shí)需頻繁地讀寫磁盤，I/O開銷大，對(duì)于聚類算法效果并不理想。Spark作為基于內(nèi)存的計(jì)算框架，可將需要迭代的數(shù)據(jù)持久化到內(nèi)存當(dāng)中，當(dāng)內(nèi)存遠(yuǎn)大于待處理數(shù)據(jù)時(shí)，則無需進(jìn)行I/O操作，在很大程度上加快了算法的執(zhí)行速度。因而Spark基于內(nèi)存的計(jì)算方式顯然更加適合分布式的聚類計(jì)算。

聚類的算法眾多，最為常用的是K-means算法[1]。K-means算法往往能夠得到局部最優(yōu)，但與整體最優(yōu)卻相去甚遠(yuǎn)。為了提高算法的聚類效果，研究者們針對(duì)K-means算法提出了很多的優(yōu)化算法。比如文獻(xiàn)[3]提出了二分 K-means算法；Steinbach等[4]對(duì)二分K-means算法進(jìn)行了評(píng)估，發(fā)現(xiàn)其聚類質(zhì)量?jī)?yōu)于標(biāo)準(zhǔn)K-means算法，與層次聚類的聚類質(zhì)量相當(dāng)； Vassilvitski和Arthur[5]提出了K-means++算法，其選取初始聚類中心的基本原則是使它們之間的距離盡可能的遠(yuǎn)，選擇聚類中心時(shí)優(yōu)先選擇那些遠(yuǎn)離之前的選擇點(diǎn)，因?yàn)橥ǔＵJ(rèn)為好的聚類分析初始聚類中心都是相對(duì)分散的；Bahmani等[6]則針對(duì)大數(shù)據(jù)聚類提出了一種并行化版本的K-means++算法，稱之為K-means||。張翔等[7]和張玉芳等[8]分別基于馬氏距離和取樣的方式改進(jìn)了K-means算法，兩者在算法的穩(wěn)定性上均獲得了提升。在K-means算法的實(shí)現(xiàn)方法上，Lloyd算法是其最為常見的實(shí)現(xiàn)方式[9]。文獻(xiàn)[10]基于樹形結(jié)構(gòu)實(shí)現(xiàn)了K-means，并將原先運(yùn)行時(shí)間縮短了一到兩個(gè)數(shù)量級(jí)。然而，隨著大數(shù)據(jù)時(shí)代的到來，傳統(tǒng)的實(shí)現(xiàn)方式在效率上的不足依舊明顯。在大數(shù)據(jù)環(huán)境下，需要尋找新的解決方案[11]。張軍偉等[12]基于并行的思想實(shí)現(xiàn)了二分K均值，算法取得了不錯(cuò)的加速比。隨著并行框架Spark[13]的出現(xiàn)，研究者開始依靠Spark優(yōu)良的框架設(shè)計(jì)并行實(shí)現(xiàn)聚類算法。張波等[14]基于Spark實(shí)現(xiàn)了Canopy K-means并行算法，其相比于K-means并行算法更為高效，梁鵬等[15]則基于Spark實(shí)現(xiàn)了并行的模糊C均值算法，使得模型高效的同時(shí)能適應(yīng)更多形狀的數(shù)據(jù)。

本文首先給出任務(wù)定義，然后面向任務(wù)要求，提出基于Spark的大數(shù)據(jù)聚類系統(tǒng)框架，并詳細(xì)討論了系統(tǒng)組成模塊，根據(jù)常用聚類算法的比對(duì)選擇聚類效果最好的算法，以此組成所提系統(tǒng)中的聚類模塊。

1 K-means的優(yōu)化算法

1.1 K-means++算法

算法1K-means++(k) 聚類中心初始化算法

1.C←從數(shù)據(jù)集X中隨機(jī)選擇選擇一個(gè)點(diǎn)

2.while |C|

4.C←C∪{x}

5.end

1.2 K-means||算法

由于K-means++也存在不足之處，即選取初始聚類中心點(diǎn)具有內(nèi)在順序，必須經(jīng)過K步來選擇K個(gè)合適的初始聚類中心，所以很難適用于大量數(shù)據(jù)的聚類。Bahmani等[4]從K-means++算法中得到靈感，提出了一種并行化版本的K-means++算法，稱為K-means||算法。該算法先選出一個(gè)初始聚類中心并計(jì)算誤差平方和φ，之后在log (φ)次的循環(huán)當(dāng)中每次選取l個(gè)點(diǎn)，最后對(duì)選出的l·log (φ)個(gè)點(diǎn)進(jìn)行重新聚類得到K個(gè)初始聚類中心，其初始化算法的偽代碼如下。

算法2K-means||(k,l) 聚類中心初始化算法

1.C←從數(shù)據(jù)集X中隨機(jī)選擇選擇一個(gè)點(diǎn)

2.φ←?x(c)

3. forO(log (φ)) do

5. C ←C∪C′

6: end for

7:將C中的點(diǎn)重新聚類成K類

1.3 二分K-means算法

有研究者針對(duì)K-means算法收斂域局部最小的問題提出了二分K-means算法[1]。算法一開始將所有數(shù)據(jù)作為一個(gè)簇，然后將簇一分為二，之后選擇誤差平方和(Sum of the squared error,SSE)較大的簇繼續(xù)二分，不斷重復(fù)，直到得到用戶指定的簇?cái)?shù)目為止。其主要執(zhí)行流程如下。

算法3二分 K-means

1.C←將所有點(diǎn)作為一個(gè)簇

2.repeat

3. 從C中挑選出一個(gè)簇

4. foriton

5. k-means.trian(k=2)

6. 計(jì)算兩個(gè)子簇的SSE的和

7. end for

8.C←選取SSE和最小的兩個(gè)子簇

9.untilC中含有K個(gè)子簇

2 任務(wù)定義

本文根據(jù)第三屆全國(guó)高校云計(jì)算應(yīng)用創(chuàng)新大賽任務(wù)要求，設(shè)計(jì)基于Spark的大數(shù)據(jù)聚類系統(tǒng)實(shí)現(xiàn)給定數(shù)據(jù)集的聚類，本次比賽提供的數(shù)據(jù)集為KDD10%和Tr11數(shù)據(jù)集,其具體信息如表1所示。

表1 兩測(cè)試數(shù)據(jù)集的規(guī)模

KDDC10%數(shù)據(jù)集是KDD競(jìng)賽在1999年舉行時(shí)采用的數(shù)據(jù)集，它為密集數(shù)據(jù)集，每個(gè)數(shù)據(jù)用41個(gè)特征來描述。Tr11 是來自于 TREC 的一個(gè)文本數(shù)據(jù)集，它是個(gè)稀疏集，每項(xiàng)數(shù)據(jù)有6 429個(gè)特征數(shù)。Tr11特征值向量的維度較KDD10%要高出許多，但就數(shù)據(jù)規(guī)模，KDD10%則要遠(yuǎn)超Tr11，可見兩項(xiàng)測(cè)試數(shù)據(jù)之間差別較大，有利于系統(tǒng)性能的測(cè)試。

3 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

3.1 聚類系統(tǒng)框架

針對(duì)上述數(shù)據(jù)聚類任務(wù)，設(shè)計(jì)了基于Spark平臺(tái)的聚類系統(tǒng)KCluster。圖1是該系統(tǒng)的結(jié)構(gòu)框圖，主要包括3個(gè)部分：數(shù)據(jù)的預(yù)處理、數(shù)據(jù)內(nèi)存持久化及聚類分析模塊。

圖1 KCluster系統(tǒng)框圖Fig.1 KCluster system diagram

KCluster系統(tǒng)的主要執(zhí)行流程如圖2所示。通過Spark Context的textFile方法讀入存儲(chǔ)于HDFS當(dāng)中的數(shù)據(jù)，也就創(chuàng)建了一個(gè)彈性分布式數(shù)據(jù)集(Resilient distributed dataset,RDD)，直接讀入的數(shù)據(jù)為RDD[Array(String)]類型。作為Spark 的核心，PDD是一個(gè)高度抽象的分布式集合，能像本地集合一樣被操作；可通過Parallelize從普通集合中創(chuàng)建，也可以從Hadoop文件系統(tǒng)(如HDFS, HIVE等)創(chuàng)建而來。

圖2 KCluster系統(tǒng)流程圖Fig. 2 Flow chart of KCluster system

隨后，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，其處理過程也是KCluster系統(tǒng)的設(shè)計(jì)重點(diǎn)，將數(shù)據(jù)包裝到RDD[Vector]當(dāng)中之后通過Train方法開始聚類模型的訓(xùn)練，Train方法最后會(huì)返回KModel對(duì)象，通過該對(duì)象的predict方法完成類標(biāo)記的預(yù)測(cè)。最后，通過saveAsTextFile算子將聚類結(jié)果保存到HDFS當(dāng)中。

3.2 數(shù)據(jù)預(yù)處理

數(shù)據(jù)的預(yù)處理是KCluster系統(tǒng)中的重要一環(huán)，數(shù)據(jù)集讀入之后，需要進(jìn)行裁剪，裁剪步驟如下：(1)將數(shù)據(jù)按照空格切分；(2)去除數(shù)據(jù)中的空字符；(3)轉(zhuǎn)換數(shù)據(jù)類型。其中的重點(diǎn)在于數(shù)據(jù)類型轉(zhuǎn)換。

在完成切分和去除空字符之后得到的數(shù)據(jù)類型為RDD[Array(String)]， train方法需要的輸入數(shù)據(jù)類型為RDD[Vector]，這就需要將數(shù)據(jù)包裝到RDD[Vector]當(dāng)中 ，Spark的MLlib包提供了Vector(向量)的定義接口，用它可以實(shí)現(xiàn)向量的定義。

第1項(xiàng)測(cè)試數(shù)據(jù)KDD10%是一個(gè)密集型的數(shù)據(jù)集，即數(shù)據(jù)的特征值全部給出。對(duì)于密集型數(shù)據(jù)集調(diào)用Vectors包中的dense方法。dense方法接收一個(gè)參數(shù)values，values為Double類型的數(shù)組。所以對(duì)于KDD10%數(shù)據(jù)集，先將字符串轉(zhuǎn)換為Double類型的數(shù)，得到RDD[Array(Double)]，再將數(shù)組傳給dense方法。

第2項(xiàng)測(cè)試數(shù)據(jù)Tr11是稀疏型數(shù)據(jù)集，數(shù)據(jù)集中存在大量為零的特征值，為節(jié)省空間并提高程序運(yùn)行時(shí)間，數(shù)據(jù)集中只存放非零特征值。對(duì)于稀疏型數(shù)據(jù)調(diào)用Vectors包中的Sparse方法。

定義稀疏向量，輸入?yún)?shù)為兩個(gè)size和elements，size為數(shù)據(jù)集的大小。elements類型為Seq[(Int，Double)]，即(非零特征值的索引，非零特征值)組成的序列。針對(duì)給定的Tr11數(shù)據(jù)集的數(shù)據(jù)形式為特征索引、特征值交替出現(xiàn)，設(shè)計(jì)了arrToSeq算法來處理稀疏數(shù)據(jù)集，其流程如圖3所示。

圖3 arrToSeq算法流程圖Fig.3 Flow chart of arrToSeq algorithm

函數(shù)的基本思路是先將索引和特征值進(jìn)行分離，分別放入兩個(gè)數(shù)組當(dāng)中，再使用RDD的zip算子，zip算子可將兩數(shù)組合并，兩數(shù)組中的元素也會(huì)一一對(duì)應(yīng)形成元組。算法流程如下所示：

算法4arrToSeq

1.for 0 to arr.length step 2

arr1← 將索引為偶數(shù)的字符串轉(zhuǎn)換為Int類型的數(shù)據(jù)

end for

2.for 1 to arr.length step 2

arr2← 將索引為奇數(shù)的字符串轉(zhuǎn)換為Double類型的數(shù)據(jù)

end for

3.arr1.zip(arr2).toSeq

3.3 聚類模塊

重點(diǎn)比較標(biāo)準(zhǔn)K-means，K-means||及二分K-means算法在并行化平臺(tái)中的聚類性能，并選擇性能較好的算法用作數(shù)據(jù)聚類模塊。

3.4 集群部署

通過sbt將程序及其依賴包打包成一個(gè)Jar包，啟動(dòng)HDFS及Spark集群，將測(cè)試數(shù)據(jù)上傳到HDFS，通過Spark-Submit將Jar包和所需的參數(shù)提交給集群，待程序執(zhí)行完畢即可從指定的HDFS輸出路徑中下載結(jié)果。

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

KCluster系統(tǒng)在聚類模塊分別采用標(biāo)準(zhǔn)K-means，K-means||以及二分 K-means算法實(shí)現(xiàn)數(shù)據(jù)聚類，并采用算法的聚類時(shí)間、誤差平方和和歸一化互信息3個(gè)指標(biāo)評(píng)估聚類算法性能。

4.1 實(shí)驗(yàn)環(huán)境

整個(gè)測(cè)試在由3臺(tái)Dell PowerEdge R720xd服務(wù)器組成的分布式集群上完成，單節(jié)點(diǎn)核心數(shù)為32個(gè)，內(nèi)存為62 GB。程序通過Scala + sbt實(shí)現(xiàn)。Ubuntu版本為16.04，Hadoop版本為2.7.2，Spark版本為1.6.2， java版本為1.7.0_80，Scala版本為2.10.4。

4.2 數(shù)據(jù)持久化

為進(jìn)一步提升算法性能，充分利用Spark基于內(nèi)存的特點(diǎn)，將要重復(fù)使用的數(shù)據(jù)持久化到內(nèi)存當(dāng)中，數(shù)據(jù)無需落地磁盤，減少了大量的I/O操作。數(shù)據(jù)的持久化通過cache實(shí)現(xiàn)，每一個(gè)RDD都可以用不同的保存級(jí)別進(jìn)行保存，cache是使用默認(rèn)存儲(chǔ)級(jí)別的快捷方法。當(dāng)緩存了一個(gè)RDD，每個(gè)節(jié)點(diǎn)就會(huì)緩存該RDD的所有分區(qū)，這樣數(shù)據(jù)一直在內(nèi)存中進(jìn)行計(jì)算，使得以后在RDD上的動(dòng)作更快(通常提高10倍左右)。當(dāng)聚類分析完成之后，迭代計(jì)算所需的數(shù)據(jù)還緩存在內(nèi)存當(dāng)中，這部分空間不會(huì)自動(dòng)釋放，通過unpersist算子可以釋放這部分內(nèi)存，節(jié)約內(nèi)存資源。

在KDD10%和Tr11數(shù)據(jù)集上進(jìn)行聚類測(cè)試，結(jié)果如表2所示。當(dāng)未將數(shù)據(jù)持久化到內(nèi)存當(dāng)中時(shí)，KDD10%數(shù)據(jù)迭代一共花費(fèi)了121 s。當(dāng)使用cache將數(shù)據(jù)持久化到內(nèi)存當(dāng)中后，數(shù)據(jù)迭代只用了14 s，僅約為原來未作內(nèi)存持久化的11.6%。

表2 cache前后聚類時(shí)間對(duì)比

4.3 聚類評(píng)估指標(biāo)

4.3.1 誤差平方和

衡量簇的質(zhì)量通常用SSE來度量。在執(zhí)行聚類分析后，對(duì)每個(gè)點(diǎn)都計(jì)算一個(gè)誤差值，該誤差值為非質(zhì)心點(diǎn)到最近的質(zhì)心的距離，各點(diǎn)到其所在簇中心的歐氏距離的和即為誤差平方和，xi為樣本點(diǎn)，C為樣本聚類中心點(diǎn)的集合，D表示聚類完成后被聚類在一個(gè)簇中的所有點(diǎn)的集合，SSE的定義如式(1)所示。誤差平方和越小說明簇內(nèi)部越緊密，聚類效果越好。通過KModel的computeCost方法可以得到聚類結(jié)果的誤差平方和的值。

(1)

4.3.2 歸一化互信息

誤差平方和的大小并不能完全反映出算法聚類質(zhì)量的好壞，因此本文還通過計(jì)算簇標(biāo)簽與真實(shí)類標(biāo)簽之間的歸一化互信息(Normalized mutual information，NMI)來衡量算法的聚類準(zhǔn)確度。用X表示KCluster系統(tǒng)聚類分析后所得類標(biāo)記的隸屬矩陣，Y表示真實(shí)類標(biāo)記的隸屬矩陣，這兩種變量之間的歸一化互信息定義可表示為

(2)

(3)

(4)

(5)

式中：I(X,Y)為X和Y之間的互信息，H(X)和H(Y)為信息熵，用于對(duì)互信息歸一化，使其位于區(qū)間[0,1]內(nèi)。歸一化互信息有幾種不同的實(shí)現(xiàn)方式，但是大體的思想都是用熵做分母使NMI介于0與1之間。一個(gè)比較多見的實(shí)現(xiàn)如式(3)所示。

如果聚類結(jié)果與真實(shí)的類標(biāo)記完全吻合，則NMI值為1；如果數(shù)據(jù)的聚類效果很差，則 NMI 值趨近于0。將聚類結(jié)果的矩陣和類真實(shí)標(biāo)記的矩陣代入式(2)，即可求得NMI值。

4.4 實(shí)驗(yàn)結(jié)果

圖4為系統(tǒng)采用標(biāo)準(zhǔn)K-means算法、二分K-means算法及K-means||算法分別對(duì)兩測(cè)試數(shù)據(jù)集進(jìn)行5次聚類的結(jié)果。從圖4(a,b)中可以看到二分K-means算法在三者中穩(wěn)定性最好，多次計(jì)算的聚類結(jié)果的誤差平方和幾乎不發(fā)生改變；K-means||算法穩(wěn)定性僅次于二分 K-means算法；標(biāo)準(zhǔn)K-means算法聚類的結(jié)果波動(dòng)較大。觀察圖4(c, d)，K-means||算法的聚類時(shí)間最短，效率最高，而K-means算法的效率最差。

圖4 3種算法在兩數(shù)據(jù)集上進(jìn)行5次聚類結(jié)果Fig. 4 Five clustering results of three algorithms on two data sets

表3給出了3種算法5次聚類結(jié)果的平均值，從中可以看到K-means||算法在KDD數(shù)據(jù)集上的聚類時(shí)間大約為K-means算法的1/6，為二分K-means算法的1/4。其原因可能在于二分 K-means通過多次二分實(shí)驗(yàn)的方式尋找最優(yōu)解，使得它在對(duì)大規(guī)模數(shù)據(jù)進(jìn)行聚類時(shí)用時(shí)較多。從表中還可以看到K-means||算法聚類結(jié)果的誤差平方和遠(yuǎn)小于其他兩種算法，結(jié)果比標(biāo)準(zhǔn)K-means和二分 K-means的結(jié)果要小約一半，甚至一個(gè)數(shù)量級(jí)。

表3 3種算法5次聚類結(jié)果的平均值

按照數(shù)據(jù)標(biāo)簽的規(guī)模，將KDD10%數(shù)據(jù)集分為23類，Tr11數(shù)據(jù)集分為9類。從表3中可以看到KDD10%數(shù)據(jù)集的聚類效果良好,其中K-means||算法的NMI值接近0.7，但3種算法對(duì)于Tr11數(shù)據(jù)集的聚類效果非常不理想，NMI值都趨于0。經(jīng)過分析，發(fā)現(xiàn)Tr11作為一個(gè)文本數(shù)據(jù)集，其維度很高、數(shù)據(jù)很稀疏，所以在高維空間中，數(shù)據(jù)都聚集在一起，若將數(shù)據(jù)分為9類，數(shù)據(jù)間雖然有距離，但是距離很小無法將其分開。于是嘗試通過調(diào)節(jié)聚類中心數(shù)來改善聚類效果，改善后的實(shí)驗(yàn)結(jié)果如表4所示。最終發(fā)現(xiàn)3種算法均在數(shù)據(jù)集被分為60類左右時(shí)，NMI值達(dá)到局部最高，聚類效果提升明顯。由實(shí)驗(yàn)結(jié)果可見，K-means||算法在NMI值、聚類時(shí)間及誤差平方和3個(gè)評(píng)價(jià)指標(biāo)上，均優(yōu)于其他兩種算法。因此，本文設(shè)計(jì)的大數(shù)據(jù)聚類系統(tǒng)KCluster選擇K-means||算法實(shí)現(xiàn)聚類處理。

表4 數(shù)據(jù)分為不同類簇時(shí)的NMI值

5 結(jié)束語

本系統(tǒng)設(shè)計(jì)的關(guān)鍵點(diǎn)在于數(shù)據(jù)的預(yù)處理以及聚類性能的優(yōu)化。經(jīng)過分析，針對(duì)不同類型的初始數(shù)據(jù)集采用不同的處理策略進(jìn)行了預(yù)處理，在數(shù)據(jù)聚類階段采用K-means||算法；同時(shí)，利用Spark基于內(nèi)存的優(yōu)點(diǎn)，將數(shù)據(jù)持久化到內(nèi)存當(dāng)中，使運(yùn)行效率得到了進(jìn)一步的提升。本系統(tǒng)預(yù)處理之后的數(shù)據(jù)同時(shí)也適用于其他聚類算法的分析處理，系統(tǒng)具有一定的通用性。

下一步將通過對(duì)Tr11等高維數(shù)據(jù)集進(jìn)行降維處理，嘗試提升系統(tǒng)對(duì)高維稀疏數(shù)據(jù)的聚類性能，同時(shí)也將繼續(xù)著力于K-means算法的優(yōu)化工作，深入研究Spark平臺(tái)特性，進(jìn)行參數(shù)調(diào)優(yōu)。