徐健銳, 詹永照

(1. 江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院, 江蘇 鎮(zhèn)江 212013; 2. 江蘇聯(lián)合職業(yè)技術(shù)學(xué)院 鎮(zhèn)江分院, 江蘇 鎮(zhèn)江 212016)

聚類分析是數(shù)據(jù)挖掘領(lǐng)域重點(diǎn)研究的方向之一,其中經(jīng)典的K-means聚類算法[1]得到了廣泛的研究和使用.但是,近幾年來隨著大數(shù)據(jù)、云計(jì)算等新技術(shù)的發(fā)展,普通規(guī)模的數(shù)據(jù)都達(dá)到了TB級[2],而且數(shù)據(jù)特征越來越復(fù)雜,臟數(shù)據(jù)也越來越多.在這種背景下,對聚類分析算法的性能要求越來越高.經(jīng)典的K-means聚類算法雖然得到了廣泛應(yīng)用,但是它過分的依賴算法初始K個(gè)中心點(diǎn)的選擇[3],初始點(diǎn)選擇不合適,就很容易導(dǎo)致最終解局部最優(yōu),使算法的迭代次數(shù)增加,特別是算法處理的數(shù)據(jù)量很大時(shí),執(zhí)行效率的缺陷就更明顯[4].因此,隨著待處理數(shù)據(jù)量的不斷增加,有必要對K-means聚類算法的缺陷進(jìn)行改進(jìn),并進(jìn)行大規(guī)?？焖貹-means聚類算法的研究.

基于內(nèi)存的分布式[5]計(jì)算框架Spark是繼分布式計(jì)算框架Hadoop之后又一個(gè)被廣泛應(yīng)用的主流大數(shù)據(jù)處理和計(jì)算平臺[6].它采用內(nèi)存式數(shù)據(jù)存儲方式,而不需要將計(jì)算過程產(chǎn)生的中間數(shù)據(jù)轉(zhuǎn)存到磁盤當(dāng)中,極大地減少了計(jì)算過程中與磁盤的數(shù)據(jù)交換次數(shù)[7],從而提高了數(shù)據(jù)的處理速度.相對于Hadoop分布式計(jì)算框架而言,Spark在處理同一數(shù)量級數(shù)據(jù)時(shí),處理速度有百倍的提高.Spark的內(nèi)存分布式計(jì)算建立在一種叫做彈性分布式數(shù)據(jù)集[8](resilient distributed dataset,RDD)的數(shù)據(jù)抽象基礎(chǔ)之上.通過這種數(shù)據(jù)抽象,可在本地服務(wù)器上操作集群上其他服務(wù)器上的數(shù)據(jù)集,非常適合于大規(guī)模數(shù)據(jù)多次迭代計(jì)算的優(yōu)化.在Spark內(nèi)存分布式框架基礎(chǔ)上開發(fā)的機(jī)器學(xué)習(xí)算法庫[9](machine learning library,MLlib)可作為算法基礎(chǔ),針對基礎(chǔ)應(yīng)用進(jìn)行擴(kuò)展,廣泛應(yīng)用的算法主要包括聚類分析、分類以及多種回歸算法.

Spark內(nèi)存分布式框架基礎(chǔ)上開發(fā)的機(jī)器學(xué)習(xí)算法庫不僅能夠?qū)崿F(xiàn)不同規(guī)模集群間的分布式計(jì)算,并且很好地將矩陣的轉(zhuǎn)置、相乘、相加以及求和等基礎(chǔ)操作融合到計(jì)算過程中.通過對原始待計(jì)算數(shù)據(jù)進(jìn)行矩陣劃分,既可以利用矩陣基礎(chǔ)算法提高計(jì)算速度,又可以減少不同結(jié)點(diǎn)之間的數(shù)據(jù)交換.針對K-means算法因初始聚類點(diǎn)選擇不當(dāng)導(dǎo)致局部最優(yōu)、迭代次數(shù)增加而無法適應(yīng)大規(guī)模數(shù)據(jù)聚類的問題,通過預(yù)抽樣和最大最小距離相結(jié)合對K-means算法進(jìn)行改進(jìn).

文中將改進(jìn)的K-means算法和分布式計(jì)算框架Spark結(jié)合提出大數(shù)據(jù)下的快速聚類算法Spark-KM,既彌補(bǔ)經(jīng)典K-means算法的不足,又發(fā)揮了Spark分布式計(jì)算處理速度快的優(yōu)勢;并通過單機(jī)和集群環(huán)境的試驗(yàn)對比,證明算法在大數(shù)據(jù)規(guī)模下的可擴(kuò)展性和有效性.

1 相關(guān)研究

1.1 K-means算法

K-means算法[10]從待聚類的原始數(shù)據(jù)集中隨機(jī)選擇K個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心,然后根據(jù)特定的距離算法計(jì)算非中心點(diǎn)到聚類中心的距離,進(jìn)行初步的聚類劃分.最后計(jì)算每個(gè)聚類中到中心點(diǎn)的平均距離,并調(diào)整聚類中心,經(jīng)過多次迭代最終使得聚類中元素最相似,類間的元素不相似.

具體的算法如下.輸入:聚類中心的初始個(gè)數(shù)K和待聚類的數(shù)據(jù)集S.輸出:最終的聚類結(jié)果,即K個(gè)類簇.詳細(xì)步驟: ① 從待聚類的數(shù)據(jù)集S中隨機(jī)選擇K個(gè)對象作為初始聚類中心; ② 計(jì)算非中心點(diǎn)到每個(gè)聚類中心的距離,將該點(diǎn)回歸到距離最短的那個(gè)聚類中心所在的類簇中; ③ 計(jì)算每個(gè)類簇中距離的平均值作為新的聚類中心; ④ 根據(jù)每個(gè)非中心點(diǎn)到中心點(diǎn)的距離最小原則,對數(shù)據(jù)集進(jìn)行重新聚類; ⑤ 重復(fù)步驟③,④,直到聚類簇不再變化,或者達(dá)到設(shè)定的迭代次數(shù)就結(jié)束算法.

K-means算法的主要缺點(diǎn)[11]: ① 算法對初始聚類中心的選擇和待處理數(shù)據(jù)點(diǎn)的輸入次序敏感,也就是說,選擇不同的初始聚類中心,不同的待處理數(shù)據(jù)點(diǎn)輸入次序,對應(yīng)的最終聚類結(jié)果差別很大; ② 如果初始聚類中心靠近某個(gè)最小值,經(jīng)過多次迭代之后,很容易陷入局部最優(yōu)解的情況,這樣會增加算法的迭代次數(shù),隨著迭代次數(shù)的增加,算法在處理大數(shù)據(jù)時(shí)時(shí)間效率將會非常低; ③ 原始數(shù)據(jù)中存在孤立點(diǎn)時(shí),算法的聚類準(zhǔn)確性很難保證.

1.2 Spark

Spark是近幾年開始流行的基于內(nèi)存的分布式計(jì)算框架[12],它和分布式計(jì)算框架Hadoop相比,共同點(diǎn)在于均利用了MapReduce的思想,所以Spark具有Hadoop的所有優(yōu)點(diǎn).但是,因?yàn)镾park是基于內(nèi)存的,也就是說計(jì)算過程的中間結(jié)果存儲在內(nèi)存中,而不需要將其轉(zhuǎn)存到磁盤,這樣就減少了輸入輸出的時(shí)間消耗,所以較Hadoop更適合于大數(shù)據(jù)量、多次迭代的計(jì)算.

Spark是一個(gè)集成了多個(gè)計(jì)算組件的統(tǒng)一軟件棧.通過計(jì)算引擎,Spark可以協(xié)調(diào)和調(diào)度運(yùn)行在多個(gè)工作機(jī)器或計(jì)算機(jī)集群上的計(jì)算組件.Spark的生態(tài)系統(tǒng)主要包括結(jié)構(gòu)化數(shù)據(jù)、實(shí)時(shí)計(jì)算、機(jī)器學(xué)習(xí)和圖計(jì)算幾個(gè)部分,其各個(gè)組件見圖1.

Spark SQL是一種可以用來操作結(jié)構(gòu)化數(shù)據(jù)的程序集合[13].在Spark SQL基礎(chǔ)上可以利用SQL或者Apache Hive的SQL對數(shù)據(jù)進(jìn)行查詢操作.Spark streaming 是Spark提供的可以對實(shí)時(shí)數(shù)據(jù)進(jìn)行流式計(jì)算的組件,適合于處理網(wǎng)絡(luò)服務(wù)器日志、網(wǎng)絡(luò)實(shí)時(shí)更新的消息隊(duì)列等流式數(shù)據(jù).MLlib集成了常用的機(jī)器學(xué)習(xí)的算法,主要包括協(xié)同過濾、回歸、分類、聚類等,還提供了對數(shù)據(jù)模型的評估和數(shù)據(jù)的導(dǎo)入等額外功能.GraphX主要是用來完成對基于圖的模型的操作,比如從社交網(wǎng)絡(luò)圖中挖掘社交關(guān)系和常用的圖計(jì)算.

彈性分布式數(shù)據(jù)RDD是分布式的元素集合,是Spark對數(shù)據(jù)的核心抽象.Spark通過創(chuàng)建RDD、轉(zhuǎn)換RDD、以及調(diào)用RDD的相關(guān)操作,對集群數(shù)據(jù)結(jié)點(diǎn)的操作實(shí)現(xiàn)本地化操作,最后將數(shù)據(jù)分發(fā)到集群上,實(shí)現(xiàn)操作的并行化.圖2給出了RDD的相關(guān)操作轉(zhuǎn)換.

圖2 RDD的相關(guān)操作轉(zhuǎn)換

2 改進(jìn)K-means算法

2.1 算法改進(jìn)思想

在1.1節(jié)中分析了K-means算法的主要缺點(diǎn),下面對如何優(yōu)化初始聚類中心和并行化提出解決辦法.

改進(jìn)算法的思想如下:設(shè)原始數(shù)據(jù)集Y={y1,y2,…，yn},且yi∈Rd,其中：n是數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)；yi代表d維向量.改進(jìn)算法首先從原始數(shù)據(jù)集Y中隨機(jī)抽取一個(gè)較小的數(shù)據(jù)集Y′,令|Y′|=|Y|×s,其中：|Y′|,|Y|分別代表數(shù)據(jù)集Y′和Y的元素個(gè)數(shù)；s為抽樣調(diào)和數(shù),s的取值通常在1%～20%內(nèi)(即從原始數(shù)據(jù)集中抽取1%～20%的數(shù)據(jù)),具體大小根據(jù)原始數(shù)據(jù)的數(shù)據(jù)量確定.然后根據(jù)最大最小算法抽取聚類中心C1,再將C1作為初始聚類中心C.每次計(jì)算新的聚類中心時(shí),聚類都可以獨(dú)立進(jìn)行,所以可以使用MapReduce分布式計(jì)算框架進(jìn)行并行化計(jì)算,從而提高計(jì)算效率.根據(jù)相應(yīng)的距離計(jì)算方法計(jì)算新聚類中心與初始聚類中心的距離,如果該距離小于設(shè)定的閾值,則算法迭代結(jié)束,返回新的聚類中心和聚類的結(jié)果,否則用新的聚類中心更新初始聚類中心,直到滿足閾值條件.

大數(shù)據(jù)的聚類容易因孤立點(diǎn)對聚類準(zhǔn)則函數(shù)造成影響,所以將聚類準(zhǔn)則函數(shù),即加權(quán)的聚類準(zhǔn)則函數(shù)Jc改進(jìn)為

改進(jìn)算法的時(shí)間復(fù)雜度為o(nk(s+t)/(M×N)),其中：n為數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)；k為聚類個(gè)數(shù)；t為算法的迭代次數(shù)；M為Map作業(yè)的個(gè)數(shù)；N為進(jìn)行計(jì)算的集群中結(jié)點(diǎn)個(gè)數(shù).

2.2 改進(jìn)算法的執(zhí)行過程

聚類個(gè)數(shù)為k,閾值設(shè)定為T,則改進(jìn)算法步驟如下:

3) 將C1作為初始聚類中心C,使用Spark分布式并行計(jì)算新的聚類中心C′.

4) 計(jì)算C與C′的距離,并與閾值T比較:如果小于,則返回聚類中心C和聚類結(jié)果,否則用C′作為新的聚類中心重新迭代計(jì)算,直到滿足閾值條件.

3 Spark矩陣操作定義

Spark以彈性分布式數(shù)據(jù)集為核心數(shù)據(jù)抽象,為方便程序的開發(fā),提供了創(chuàng)建、轉(zhuǎn)換和動(dòng)作等基礎(chǔ)操作[14].但是,通常情況下需要組合使用這些操作,特別是對矩陣的處理,相應(yīng)的專用操作比較少,這就導(dǎo)致很多算法只能在本地操作,而不適用于運(yùn)行效率更高的分布式操作.為此,文中給出基于Spark平臺常用矩陣操作的分布式計(jì)算方法.

3.1 矩陣操作定義

定義1矩陣Am×n表示有m行n列的數(shù)值矩陣,即

在Spark-KM算法中,對原始數(shù)據(jù)采用矩陣劃分的方式,利用IndexedMatrix對矩陣劃分后的原始數(shù)據(jù)進(jìn)行矩陣存儲,從而充分利用集群中分布式內(nèi)存的優(yōu)勢,使算法可以用于大規(guī)模的數(shù)值計(jì)算[15].IndexedMatrix在集群中的分布如圖3所示.

圖3 RDD矩陣存儲

由圖3可見,一個(gè)RDD包含多個(gè)Partition,每個(gè)Partition由多個(gè)行向量組成,每個(gè)行向量又包含一個(gè)索引和本地向量vector.

定義2矩陣轉(zhuǎn)置如下:定義1中矩陣對應(yīng)的轉(zhuǎn)置矩陣是一個(gè)n×m矩陣,用AT表示,即

Spark通過flatMap,reduce等操作完成矩陣轉(zhuǎn)置.圖4通過具體實(shí)例來說明RDD的轉(zhuǎn)換過程,數(shù)據(jù)的行向量(i,Vi)集合表示矩陣.

圖4 RDD的轉(zhuǎn)換過程

由圖4可見,通過flatMap操作將原始數(shù)據(jù)分解成列與行對應(yīng)的鍵值對,然后將列數(shù)據(jù)通過groupByKey操作分配到同一組,并通過排序操作sortByKey對每個(gè)劃分內(nèi)的數(shù)據(jù)排序,得到最終結(jié)果.

轉(zhuǎn)換過程的偽代碼如下:

matrixAT=A.map(row=>row.vector.toArray)

.flatMap(vector=>{

vararray=newArray[Double,Int)](vector.size)

for(i<-0 tovector.size-1)

{array(i)=(a(i),i)}

returnarray}).map(v=>(v._2,v._1)).

groupByKey().sortByKey().map(line

=>new

IndexedRow(line._1,Vectors.dense(line._2.toArray)))

定義3矩陣乘法如下:m行n列的數(shù)值矩陣A左乘n行l(wèi)列的矩陣B，得到m行l(wèi)列的矩陣C,即Am×n×Bn×l=Cm×l.在Spark平臺中,通過Map和MapReduce來實(shí)現(xiàn)矩陣乘法.

Map矩陣乘法:對于數(shù)據(jù)量較小并且可以在單節(jié)點(diǎn)內(nèi)存中存放的矩陣,將其廣播到集群中的所有節(jié)點(diǎn)內(nèi),在本地只進(jìn)行分塊乘法,最終計(jì)算結(jié)果用RDD存放.

文中的矩陣運(yùn)算以行向量為計(jì)算單位,但是,傳統(tǒng)矩陣是行與列的組合,不符合文中算法規(guī)則.所以,首先通過轉(zhuǎn)置操作將矩陣的乘法轉(zhuǎn)換為行向量相乘,從而充分利用Spark內(nèi)存計(jì)算的特性.用行作為計(jì)算單位,可以充分利用行數(shù)據(jù)在物理存儲上的連續(xù)性,從而避免傳統(tǒng)矩陣列存儲不連續(xù)性造成的緩存浪費(fèi).Map矩陣乘法的RDD變換操作見圖5.

Map矩陣乘法偽代碼如下：

matrixB=sc.broadcast(BT)

matrixC=A.map(line=>newIndexedRow(

ai.index,(vectorci

for(bi<-B)

{for(i<-0 tovector.size-1)

{ci(i)=ai×bi}}

returnci}))

MapRdduce矩陣乘法:對于兩個(gè)較大的數(shù)據(jù)矩陣很難在一個(gè)集群節(jié)點(diǎn)直接存儲的情況,首先把矩陣進(jìn)行轉(zhuǎn)置,然后計(jì)算笛卡爾積和乘積,最后輸出計(jì)算結(jié)果.

MapReduce矩陣乘法的RDD變換操作見圖6.

圖5 Map矩陣乘法的RDD變換

圖6 MapReduce矩陣乘法的RDD變換

MapReduce矩陣乘法偽代碼如下:

matrixA=AT

matrixC=B.cartesian(A)

.map(row=>(bj.index,Aj.index),row._1×row._2))

.groupByKey().sortByKey().map()

定義4矩陣加法如下:兩個(gè)同型矩陣對應(yīng)元素相加,即

cij=aij+bij,C=A+B.

在Spark中首先通過join連接兩個(gè)矩陣,然后通過map得到結(jié)果.矩陣加法的RDD操作過程見圖7.

圖7 矩陣加法的RDD操作

矩陣加法偽代碼如下:

matrixA=AT

matrixC=B.join(A).map(Ai+Bi)

3.2 廣播變量

在Spark-KM算法中,把較小的數(shù)據(jù)集廣播到集群中的結(jié)點(diǎn)內(nèi)存,然后相應(yīng)的map操作進(jìn)行計(jì)算,從而減少reduce過程中數(shù)據(jù)在結(jié)點(diǎn)間的移動(dòng)次數(shù).算法中定義廣播變量Broadcast,在集群節(jié)點(diǎn)中只保存一個(gè)只讀備份,把作業(yè)的粒度定義為節(jié)點(diǎn)粒度,充分利用內(nèi)存,同時(shí)優(yōu)化Broadcast,節(jié)約節(jié)點(diǎn)間的通信開銷.

4 Spark-KM算法

基于第2節(jié)改進(jìn)K-means算法和第3節(jié)Spark矩陣操作的定義,提出分布式內(nèi)存計(jì)算平臺Spark基礎(chǔ)上的改進(jìn)K-means算法Spark-KM算法.該算法避免了傳統(tǒng)K-means聚類算法初始聚類中心選擇不當(dāng)而使聚類結(jié)果陷入局部最優(yōu)的不足,通過矩陣運(yùn)算,不僅提高了運(yùn)算速度,減少節(jié)點(diǎn)間數(shù)據(jù)的移動(dòng)次數(shù),還利用分布式特性使算法能夠處理大規(guī)模數(shù)據(jù)的聚類問題.

傳統(tǒng)K-means算法需要多次迭代計(jì)算新一輪聚類的中心、數(shù)據(jù)點(diǎn)到聚類中心的距離,每一個(gè)步驟都需要在集群中的結(jié)點(diǎn)間進(jìn)行數(shù)據(jù)移動(dòng).Spark-KM算法根據(jù)RDD數(shù)據(jù)特點(diǎn)和相關(guān)操作,利用廣播變量來減少數(shù)據(jù)在節(jié)點(diǎn)間的移動(dòng),從而減少節(jié)點(diǎn)間通信負(fù)擔(dān),提高算法的整體效率.

Spark-KM算法的主要步驟如下:

1) 重新計(jì)算聚類中心.根據(jù)2.2節(jié)改進(jìn)K-means算法執(zhí)行過程中聚類中心的計(jì)算方法,通過Spark定義的矩陣乘法和累加,以及定義的廣播變量來實(shí)現(xiàn).將矩陣通過廣播變量分布到集群中的所有節(jié)點(diǎn)當(dāng)中,每個(gè)結(jié)點(diǎn)中單獨(dú)進(jìn)行距離計(jì)算并更新聚類中心,最終以RDD的形式返回計(jì)算結(jié)果.

2) 距離矩陣的計(jì)算.距離矩陣存放原始數(shù)據(jù)與聚類中心的距離.在計(jì)算過程中,由于聚類中心的數(shù)據(jù)點(diǎn)個(gè)數(shù)相對原始數(shù)據(jù)來說規(guī)模較小,所以把聚類中心以廣播變量的形式廣播到集群中所有的結(jié)點(diǎn),這樣就可以實(shí)現(xiàn)本地計(jì)算,而不需要在節(jié)點(diǎn)間移動(dòng)數(shù)據(jù).然后,距離矩陣轉(zhuǎn)置,方便后續(xù)操作.

3) 更新隸屬矩陣.隸屬矩陣表征數(shù)據(jù)點(diǎn)屬于哪個(gè)聚類.通過矩陣?yán)奂硬僮?計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到聚類中心的距離之和,然后通過廣播變量把距離和分發(fā)到集群中的所有節(jié)點(diǎn);最終通過map操作得到隸屬矩陣,為判斷數(shù)據(jù)點(diǎn)隸屬于哪個(gè)聚類做準(zhǔn)備.

4) 依據(jù)初始設(shè)定的距離閾值或者迭代次數(shù)確定是否繼續(xù)迭代運(yùn)算.

Spark-KM算法偽代碼如下:

Spark-KM()

for(i<-0 to maxiter)∥maxiter最大迭代次數(shù)

{C=S(X×U)∥broadcast矩陣乘法

D=C×X∥計(jì)算距離矩陣

U=D.map()∥更新隸屬矩陣

if(Ji-Ji-1

break}

5 試驗(yàn)與結(jié)果分析

5.1 試驗(yàn)環(huán)境

硬件環(huán)境如下:四核CPU,主頻為3.4 GHz,硬盤2 TB,內(nèi)存8 GB.軟件環(huán)境如下:VMware 12.5.2,操作系統(tǒng)CentOS6.5,jdk1.8.0_45,scala-2.10.4,hadoop-2.6.0,spark-1.3.0-bin-hadoop 2.4.

5.2 試驗(yàn)內(nèi)容和結(jié)果分析

試驗(yàn)內(nèi)容主要包括兩部分: ① 對改進(jìn)K-means算法的有效性進(jìn)行驗(yàn)證; ② 在單機(jī)和集群環(huán)境下對比Spark-KM算法的性能,并驗(yàn)證Spark-KM算法在集群中大數(shù)據(jù)處理的可擴(kuò)展性和適應(yīng)性.

試驗(yàn)中參數(shù)含義如下:n為待聚類的數(shù)據(jù)點(diǎn)個(gè)數(shù)(單位:萬);k為聚類個(gè)數(shù);Y為結(jié)束條件;M為選用的聚類方法;t為迭代次數(shù);T為運(yùn)行時(shí)間.

5.2.1 改進(jìn)K-means算法有效性的驗(yàn)證

幾種算法可簡寫如下:S代表普通的K-means算法,即隨機(jī)選擇聚類中心;MM代表通過最大最小距離選擇聚類中心的K-means算法;MS代表文中的改進(jìn)算法,即通過隨機(jī)抽樣,然后用最大最小距離選擇聚類中心的K-means算法.

驗(yàn)證試驗(yàn)數(shù)據(jù)為人工標(biāo)注的5萬條測試數(shù)據(jù).表1是不同聚類方法在不同聚類個(gè)數(shù)中的5次聚類結(jié)果的平均值.圖8給出了Jc趨勢圖.

表1 不同方法的聚類結(jié)果

圖8 Jc趨勢圖

由表1和圖8可見,MM算法在5次試驗(yàn)中都比較穩(wěn)定,對隨機(jī)選擇聚類中心的聚類算法S起到了優(yōu)化作用,且明顯優(yōu)于S算法.但是,當(dāng)數(shù)據(jù)量很大時(shí),依據(jù)最大最小距離算法迭代計(jì)算聚類的中心時(shí),不僅會花費(fèi)大量的時(shí)間,也容易導(dǎo)致內(nèi)存不足.所以,選擇這兩種距離計(jì)算方法的折中,即文中的改進(jìn)算法MS,通過隨機(jī)抽樣,然后用最大最小距離選擇聚類中心的K-means算法.

5.2.2 單機(jī)偽分布驗(yàn)證Spark-KM算法有效性

有效性試驗(yàn)中隨機(jī)產(chǎn)生1萬、10萬、100萬個(gè)聚類數(shù)據(jù)點(diǎn),單機(jī)偽分布,選擇100個(gè)聚類中心,方法同5.2.1,試驗(yàn)結(jié)果見表2.

表2 單機(jī)偽分布試驗(yàn)結(jié)果

由表2可見,通過3個(gè)數(shù)據(jù)量的試驗(yàn)對比,在數(shù)據(jù)量較小的情況下,基于最大最小距離計(jì)算聚類中心算法MM的聚類準(zhǔn)則函數(shù)Jc最小,且算法運(yùn)行時(shí)間最短;但是,隨著處理的數(shù)據(jù)量增大,MM算法在迭代計(jì)算聚類中心時(shí)所需時(shí)間過長,由表2可知,100萬個(gè)數(shù)據(jù)點(diǎn)的聚類時(shí)間已經(jīng)無法接受,說明這種算法已經(jīng)不再適合大數(shù)據(jù)的聚類.文中的改進(jìn)算法MS,在單機(jī)情況下,與S,MM算法相比,在聚類準(zhǔn)則函數(shù)Jc相差不大且穩(wěn)定的前提下,有明顯的時(shí)間優(yōu)勢.

5.2.3 集群環(huán)境驗(yàn)證Spark-KM算法有效性

本試驗(yàn)是在VMware中配置5臺虛擬機(jī),1臺作為master節(jié)點(diǎn),其他4臺作為slave節(jié)點(diǎn).為了與單機(jī)偽分布進(jìn)行對比,本試驗(yàn)依然采用5.2.2中的試驗(yàn)數(shù)據(jù),聚類中心個(gè)數(shù)為100,試驗(yàn)結(jié)果見表3.

表3 集群試驗(yàn)結(jié)果

由表2,3的對比可見,在數(shù)據(jù)量、迭代次數(shù)相同,聚類準(zhǔn)則函數(shù)Jc相近的情況下,MS算法的時(shí)間效率有了明顯的提高;同時(shí),S,MM,MS這3種方法在相同數(shù)據(jù)量的聚類中,MS算法所用時(shí)間只有其他兩種方法的1/3～2/3,并且隨著數(shù)據(jù)量的增加,MS算法的時(shí)間效率比其他兩種算法提高得更快.原因在于: ① Spark-KM算法在充分發(fā)揮分布式內(nèi)存計(jì)算框架內(nèi)存計(jì)算的高效性基礎(chǔ)上,通過改進(jìn)基于RDD的矩陣分布式計(jì)算和廣播變量,實(shí)現(xiàn)了本地計(jì)算,從而減少了節(jié)點(diǎn)間的數(shù)據(jù)傳輸帶來的效率損耗; ② 改進(jìn)的K-means算法通過抽樣的方法避免聚類陷入局部最優(yōu),同時(shí)最大最小距離計(jì)算聚類中心,使聚類中心的選取最優(yōu)化,從而減少迭代次數(shù).

6 結(jié) 論

文中改進(jìn)了K-means聚類算法,并結(jié)合分布式內(nèi)存計(jì)算框架Spark提出了Spark-KM算法.通過隨機(jī)抽樣和基于最大最小距離優(yōu)化聚類中心的選擇;改進(jìn)Spark的矩陣計(jì)算,對原始數(shù)據(jù)進(jìn)行矩陣分割,并存儲在不同的Spark計(jì)算框架的節(jié)點(diǎn)當(dāng)中,能夠減少節(jié)點(diǎn)間的數(shù)據(jù)移動(dòng)次數(shù).試驗(yàn)結(jié)果表明,Spark-KM算法能夠?qū)崿F(xiàn)大數(shù)據(jù)的快速聚類,并且具有很好的可擴(kuò)展性.

后續(xù)將繼續(xù)研究聚類中心的優(yōu)化選取方法和分布式矩陣計(jì)算,并在改進(jìn)算法的基礎(chǔ)上開發(fā)基礎(chǔ)函數(shù)庫.

參考文獻(xiàn)(References)

[ 1 ] 張慶新,崔展博,馬睿,等.基于k-means聚類與徑向基神經(jīng)(RBF)網(wǎng)絡(luò)的電力系統(tǒng)日負(fù)荷預(yù)測[J].科學(xué)技術(shù)與工程,2013, 13(34):10177-10181.

ZHANG Q X, CUI Z B, MA R, et al. Daily load forecasting of industrial enterprise power system based onk-means clustering and RBF neural network[J]. Science Technology and Engineering, 2013,13(34):10177-10181.(in Chinese)

[ 2 ] 趙國鋒,葛丹鳳.數(shù)據(jù)虛擬化研究綜述[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 28 (4): 494-502.

ZHAO G F, GE D F. A survey on data virtualization[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2016, 28(4): 494-502.(in Chinese)

[ 3 ] 楊杰明,吳啟龍,曲朝陽,等.MapReduce框架下基于抽樣的分布式K-Means聚類算法[J]. 吉林大學(xué)學(xué)報(bào)(理學(xué)版),2017,55(1):109-115.

YANG J M, WU Q L, QU C Y, et al. DistributedK-means clustering algorithm based on sampling under Map-Reduce framework[J]. Journal of Jilin University(Science Edition), 2017,55(1):109-115. (in Chinese)

[ 4 ] 王飛,秦小麟,劉亮,等.云環(huán)境下基于數(shù)據(jù)流的k-means聚類算法[J].計(jì)算機(jī)科學(xué), 2015,42(11):235-239,265.

WANG F, QIN X L, LIU L, et al. Algorithm fork-means based on data stream in cloud computing[J]. Computer Science,2015,42 (11):235-239,265. (in Chinese)

[ 5 ] LIU Y, XU L X, LI M Z. The parallelization of back propagation neural network in MapReduce and Spark[J].International Journal of Parallel Programming, 2017,45(4):760-779.

[ 6 ] 朱葉青,牛德姣,蔡濤,等.不同網(wǎng)絡(luò)環(huán)境下大數(shù)據(jù)系統(tǒng)的測試與分析[J].江蘇大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,37(4):429-437.

ZHU Y Q,NIU D J,CAI T,et al. Test and analysis of big data system in different network environment[J]. Journal of Jiangsu University (Natural Science Edition), 2016, 37(4): 429-437.(in Chinese)

[ 7 ] ZADEH R B, MENG X R, ULANOV A, et al. Matrix computations and optimization in Apache Spark[C]∥Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. [S.l.]:ACM, 2016:31-38.

[ 8 ] LIU J, LIANG Y, ANSARI N. Spark-based large-scale matrix inversion for big data processing[J]. IEEE Access, 2016, 4: 2166-2176.

[ 9 ] 唐云.基于Spark的大規(guī)模分布式矩陣運(yùn)算算法研究與實(shí)現(xiàn)[D].南京:南京大學(xué),2016.

[10] FRIGGSTAD Z, REZAPOUR M, SALAVATIPOUR M R. Local search yields a PTAS fork-means in doubling metrics[C]∥Proceedings of the Foundations of Compu-ter Science. Piscataway:IEEE,2016:365-374.

[11] 尹緒森.Spark MLlib:矩陣參數(shù)的模式[J]. 程序員,2014(8):108-112.

YIN X S. Model of Spark MLlib: matrix parameter[J]. Programmer,2014(8):108-112. (in Chinese)

[12] 王吉源,孟祥茂,廖列法.具有層次結(jié)構(gòu)的K-means聚類算法研究[J].微電子學(xué)與計(jì)算機(jī),2015,32(12):63-67.

WANG J Y, MENG X M, LIAO L F. Research on an improved hierarchical clustering algorithm ofK-means[J]. Microelectronics and Computer,2015,32 (12):63-67. (in Chinese)

[13] 王曉華.Spark MLlib機(jī)器學(xué)習(xí)實(shí)踐[M].北京:清華大學(xué)出版社,2015.

[14] 蘭云旭,王俊峰,唐鵬.基于Spark的并行醫(yī)學(xué)圖像處理研究[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,54(1):65-70.

LAN Y X, WANG J F, TANG P. Parallel processing researches of medical image based on Spark[J]. Journal of Sichuan University (Natural Science Edition), 2017, 54(1):65-70. (in Chinese)

[15] 鄭鳳飛,黃文培,賈明正.基于Spark的矩陣分解推薦算法[J].計(jì)算機(jī)應(yīng)用,2015, 35(10):2781-2783,2788.

ZHENG F F, HUANG W P, JIA M Z. Matrix factorization recommendation algorithm based on Spark [J].Journal of Computer Applications,2015,35(10):2781-2783,2788. (in Chinese)