王 磊 鄒恩岑 曾 誠 奚雪峰 陸 悠

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

引 言

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

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

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

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

1.1 K-means++算法

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

1.C←從數(shù)據(jù)集X中隨機選擇選擇一個點

2.while |C|

4.C←C∪{x}

5.end

1.2 K-means||算法

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

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

1.C←從數(shù)據(jù)集X中隨機選擇選擇一個點

2.φ←?x(c)

3. forO(log (φ)) do

5. C ←C∪C′

6: end for

7:將C中的點重新聚類成K類

1.3 二分K-means算法

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

算法3二分 K-means

1.C←將所有點作為一個簇

2.repeat

3. 從C中挑選出一個簇

4. foriton

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

6. 計算兩個子簇的SSE的和

7. end for

8.C←選取SSE和最小的兩個子簇

9.untilC中含有K個子簇

2 任務定義

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

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

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

3 系統(tǒng)設計與實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法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 聚類模塊

重點比較標準K-means，K-means||及二分K-means算法在并行化平臺中的聚類性能，并選擇性能較好的算法用作數(shù)據(jù)聚類模塊。

3.4 集群部署

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

4 實驗與分析

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

4.1 實驗環(huán)境

整個測試在由3臺Dell PowerEdge R720xd服務器組成的分布式集群上完成，單節(jié)點核心數(shù)為32個，內(nèi)存為62 GB。程序通過Scala + sbt實現(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ù)持久化

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

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

表2 cache前后聚類時間對比

4.3 聚類評估指標

4.3.1 誤差平方和

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

(1)

4.3.2 歸一化互信息

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

(2)

(3)

(4)

(5)

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

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

4.4 實驗結(jié)果

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

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

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

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

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

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

5 結(jié)束語

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

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