基于Spark的模糊C均值算法改進

夏 邢,薛 濤,李 婷

(西安工程大學(xué) 計算機科學(xué)學(xué)院,陜西 西安 710048)

0 引 言

模糊C均值聚類[1]算法是基于目標(biāo)函數(shù)的代表性模糊聚類算法,它與k-means[2]等算法屬于常用聚類算法[3]之一。核心思想是算法進行柔性劃分后,使同類簇下的對象之間相似度最大,不同類簇的對象之間相似度最小。由于FCM具有有效處理模糊信息的能力,從而在大規(guī)模數(shù)據(jù)分析、數(shù)據(jù)挖掘等眾多領(lǐng)域被廣泛使用。

但FCM算法存在聚類效果不佳、聚類時間長等問題,目前國內(nèi)外研究者針對其不足提出了多種改進方法。YU等[4]使用MapReduce編程框架來解決FCM聚類算法花費時間較長的問題;DAI等[5]針對模糊均值聚類算法的聚類質(zhì)量和聚類速度依賴于初始聚類中心,提出了一種基于MapReduce編程框架的混合Canopy-FCM算法;王桂蘭等[6]針對FCM算法會衍生大量矩陣運算的問題,使用了基于Spark的機器學(xué)習(xí)庫MLib分布式矩陣運算。

以上改進方法相比較傳統(tǒng)的FCM都有一定的改進效果,但MapReduce[7]任務(wù)在進行中間結(jié)果磁盤讀寫和資源申請過程不僅耗時長而且浪費網(wǎng)絡(luò)資源,本文給出一種基于Spark的Canopy-FCMBM并行算法,從目標(biāo)函數(shù)度量方式和算法并行化處理兩個方面提高算法執(zhí)行效率和聚類準(zhǔn)確率。Spark是一款基于內(nèi)存的分布式計算框架,不同于MapReduce將Job中間輸出結(jié)果保存在HDFS中,Spark將結(jié)果直接保存在內(nèi)存中,從而不再需要讀寫HDFS,產(chǎn)生大量的磁盤I/O,可有效縮短執(zhí)行時間。首先利用Canopy算法進行粗糙聚類[8-9],將其作為FCM算法的初始聚類中心,加快聚類收斂速度;并將傳統(tǒng)FCM目標(biāo)函數(shù)的距離度量方式由歐氏距離替換成馬氏距離[10],提高聚類結(jié)果的準(zhǔn)確性;最后利用Spark框架實現(xiàn)算法的并行化[11],減少聚類花費時間。

1 Canopy-FCMBM聚類算法設(shè)計

傳統(tǒng)的FCM算法在對維度大且分布不均勻的數(shù)據(jù)聚類過程中,表現(xiàn)出無法考慮維度特征之間的差異,從而導(dǎo)致聚類精度低等問題,本文將其原始目標(biāo)函數(shù)的度量方式更改為考慮維度權(quán)重的馬氏距離,通過不斷地迭代聚類中心矩陣,判斷兩次迭代的改變量是否小于設(shè)定的閾值來進行模糊聚類。并將Canopy粗糙聚類算法的結(jié)果作為FCM初始化的聚類中心矩陣,減小聚類隨機中心導(dǎo)致的聚類結(jié)果不可控等問題,可有效提高聚類時間和精度。

1.1 FCM聚類算法

模糊C均值算法是一種重疊聚類算法,它的思想是通過優(yōu)化目標(biāo)函數(shù)得到每個樣本點對所有聚類中心的隸屬度,從而決定樣本點的歸屬完成自動聚類。FCM算法是對于普通C均值算法的改進[12],普通C均值算法對數(shù)據(jù)屬于硬性劃分,而FCM是一種柔性的模糊劃分。

FCM算法可以借助模糊參數(shù)[13]m來描述聚類過程和結(jié)果,一般情況下當(dāng)m=1時,它就是普通的C均值聚類算法。m取值越高,算法的模糊程度也會越高[14],在實際應(yīng)用中,m通常取值為2。FCM算法相比較其他聚類算法的優(yōu)勢在于精度高且柔性聚類,不類似硬性聚類非0即1的結(jié)果。但FCM也存在一定缺點,例如對初始化敏感、計算復(fù)雜等,因此本文提出了Canopy-FCMBM的改進方法。

1.2 Canopy算法

Canopy算法[15]是一種無監(jiān)督的學(xué)習(xí)算法,屬于快速聚類算法,但是其聚類效果卻不理想。目前,比較普遍的聚類算法模式是將Canopy算法與其他聚類算法結(jié)合應(yīng)用。它通常被用作聚類預(yù)處理方法以加快其他主要聚類算法的進程,有利于處理大規(guī)模數(shù)據(jù)集。Canopy算法的基本步驟[16]如下:

(1) 首先將數(shù)據(jù)集向量化得到一個listS放入內(nèi)存,通過交叉檢驗的方式來選取2個閾值T1,T2,并保證T1>T2,一般情況下T1的取值是T2的2倍左右;

(2) 隨機選取中一個對象P作為Canopy中心,并將P從S中刪除;

(3) 計算數(shù)據(jù)集S中每個對象到所Canopy中心的距離d,若d

(4) 若d

(5) 判斷S是否為空,若為空則算法終止,輸出Canopy中心數(shù)目和每個Canopy中心,否則轉(zhuǎn)到步驟2,直至數(shù)據(jù)集合S為空。

1.3 改進后的Canopy-FCMBM算法

Canopy-FCMBM算法的主要思想是首先使用Canopy算法完成粗糙聚類,產(chǎn)生初始聚類中心[17],并將其作為FCM聚類算法的初始聚類中心矩陣,并將FCM的目標(biāo)函數(shù)距離度量方式替換為馬哈拉諾比斯距離[18],然后對目標(biāo)函數(shù)進行迭代計算得到最終的隸屬度矩陣U,最后通過Spark計算引擎實現(xiàn)算法的并行化。

由于在進行數(shù)據(jù)挖掘時,大部分?jǐn)?shù)據(jù)都存在多維度且分布不均勻的特點,傳統(tǒng)FCM算法的距離度量采用的是歐式距離,它不考慮樣本屬性之間的權(quán)重比例,從而導(dǎo)致聚類結(jié)果不精確。為了消除不同特征量綱的影響,提高聚類準(zhǔn)確度,本文將FCM算法原始目標(biāo)函數(shù)的距離度量方式由歐式距離替換為馬氏距離,它不受量綱的影響,即計算兩點之間的馬氏距離不必考慮原始數(shù)據(jù)的測量單位,這樣可以避免變量之間相關(guān)性的干擾,對改進的算法簡稱為FCMBM(Fuzzy C-Means based on Mahalanobis)算法。但需注意的是,在計算Mahalanobis距離時,必須保證樣本數(shù)量大于樣本的維數(shù),否則得到目標(biāo)函數(shù)協(xié)方差矩陣的逆矩陣會出現(xiàn)不存在的情況,從而無法計算出樣本間距離,導(dǎo)致聚類失敗。

根據(jù)列出的拉格朗日函數(shù),對各個矩陣參數(shù)求極值,即可得到目標(biāo)函數(shù)的拉格朗日最優(yōu)解。

2 基于Spark的Canopy-FCMBM算法

2.1 Spark編程模型

Spark是一種基于內(nèi)存計算的大數(shù)據(jù)并行計算框架[19],與MapReduce編程框架不同,Spark能夠?qū)ob的中間結(jié)果保存在內(nèi)存中,減少對HDFS的讀寫,從而減少磁盤I/O以及節(jié)約網(wǎng)絡(luò)傳輸時間,這使得交互式計算和復(fù)雜算法的效率得到大幅度提升。Spark的核心概念是彈性數(shù)據(jù)集(RDD),指的是一個只讀、可分區(qū)的分布式數(shù)據(jù)集,能夠以基本一致的操作方式去應(yīng)對不同的大數(shù)據(jù)應(yīng)用場景。RDD本質(zhì)上是一個基于內(nèi)存的不可變的數(shù)據(jù)結(jié)構(gòu),將用戶上傳數(shù)據(jù)進行封裝,Spark通過不同的轉(zhuǎn)換操作輸出結(jié)果,由于大數(shù)據(jù)迭代算法中經(jīng)常會多次使用同一數(shù)據(jù)集,所以Spark提供對RDD的持久化,避免多次調(diào)用行動操作對同一RDD計算而帶來的開銷。

2.2 Canopy-FCMBM算法并行化

使用單機方式運行FCM算法執(zhí)行效率較低,而利用MapReduce實現(xiàn)FCM算法的并行化耗費網(wǎng)絡(luò)資源及磁盤I/O較大,因此本文采用Spark對算法進行并行化處理。Canopy-FCMBM算法的并行化主要包含2個階段,其流程如圖1所示。

階段一為Canopy算法在Spark計算框架的處理過程:

(1) 算法開始,從HDFS或者HBase上讀取原始數(shù)集S,將其轉(zhuǎn)換成RDD對象對數(shù)據(jù)進行持久化操作,并通過調(diào)用word2vec接口將數(shù)據(jù)集格式化為向量形式;

(2) Master節(jié)點將任務(wù)分配給各worker節(jié)點,在各節(jié)點上分別執(zhí)行flatmap、reduce等操作,計算本數(shù)據(jù)點與Canopy中心點之間的距離;

(3) 計算數(shù)據(jù)集S中每個對象到所有Canopy中心的距離d,根據(jù)預(yù)定規(guī)則,給這個數(shù)據(jù)貼上弱標(biāo)記,將這個對象加入到當(dāng)前的Canopy中,得到局部Canopy中心點;

(4) 將各個Worker節(jié)點通過RDD計算出的局部Canopy中心點,執(zhí)行reduce操作,匯總得出全局的Canopy中心點。

圖 1 Canopy-FCMBM算法流程圖Fig.1 The process of Canopy-FCMBM algorithm

階段二為FCMBM算法在Spark計算框架的處理過程:

(1) 將階段一產(chǎn)生的聚類中心設(shè)置為FCMBM算法的輸入即初始聚類中心矩陣;

(2) 各Worker節(jié)點執(zhí)行map操作,分別計算數(shù)據(jù)集中每個數(shù)據(jù)到中心點的距離,即數(shù)據(jù)對象xn與第i個聚類簇的聚類中心vi的隸屬度值;

(3) 各節(jié)點在經(jīng)過cache持久化操作,以預(yù)備這個矩陣之后的RDD操作時可減少計算,再對RDD進行reduce操作執(zhí)行FCMBM局部聚類;

(4) 判斷本次聚類中心點與上次的聚類中心點的改變是否小于某個閾值,如果小于則算法停止,否則把本次的中心當(dāng)做初始聚類中心,繼續(xù)進行矩陣迭代運算;

(5) 主控節(jié)點執(zhí)行reduce 操作將各個計算節(jié)點產(chǎn)生的局部聚類結(jié)果歸并為全局聚類結(jié)果

Canopy 中的聚類中心經(jīng)過cache持久化操作后,其數(shù)據(jù)對象放置于內(nèi)存中,所以下一階段FCMBM算法在聚類時可多次重復(fù)使用,并且FCMBM算法在迭代計算時,如果結(jié)果不收斂,可將本次的聚類中心執(zhí)行cache操作,至此不需每次都對矩陣進行一系列RDDs的算子操作,并且不需要每次都在 HDFS 分布式文件系統(tǒng)上讀取,從而可以有效提高算法執(zhí)行的效率。

FCM算法在聚類過程中,會出現(xiàn)大量的包括隸屬度矩陣、距離矩陣、更新聚類中心矩陣等矩陣迭代計算。若使用MapReduce計算框架,每迭代一次矩陣運算都要啟動一次完整的MapReduce執(zhí)行操作,并且在運算過程中會將中間結(jié)果寫入硬盤,而頻繁的讀寫硬盤會大大增加運算時間,這樣不僅編寫map階段和reduce階段代碼不靈活而且執(zhí)行效率不高。Spark使用內(nèi)存運算技術(shù),提供了豐富的RDDs算子轉(zhuǎn)換操作,代碼編寫靈活高可用,使用的map、flatMap、reduce等操作可以輕松解決FCM算法中矩陣的轉(zhuǎn)置、求笛卡爾積等數(shù)學(xué)計算,此外cache將中間數(shù)據(jù)對象寫入內(nèi)存,可有效避免矩陣重復(fù)計算,所以基于Spark的算法運算速度相比于Hadoop MapReduce計算框架有所提升。

3 結(jié)果與分析

3.1 實驗環(huán)境和實驗數(shù)據(jù)

實驗平臺是在Hadoop2.6.5的基礎(chǔ)上部署Spark框架,在VMware中創(chuàng)建4臺虛擬機,其中1臺為master節(jié)點，3臺為slave節(jié)點。操作系統(tǒng)均為CentOS-6.3-x86-64版本,Java環(huán)境為jdk1.8-103,Spark版本為Spark2.1.1,Scala版本為2.12.6,Sqoop版本為sqoop-1.4.6.bin--hadoop-2.0.4-alpha,mahout版本為apache-mahout-distribution-0.10.1。

本次實驗數(shù)據(jù)集選用來自UCI機器學(xué)習(xí)庫的Iris,Balance Scale和Car Evalution 3個標(biāo)準(zhǔn)數(shù)據(jù)集作為測試數(shù)據(jù),實驗測試數(shù)據(jù)集描述如表1所示。

表 1 實驗數(shù)據(jù)集

為方便實驗結(jié)果比較,將數(shù)據(jù)集分為兩大類,其中Iris和Balance Scale屬于小數(shù)據(jù)集,其屬性維度相對較少,Car Evaluation為大數(shù)據(jù)集。但所選數(shù)據(jù)集均滿足樣本數(shù)量大于屬性數(shù)量的要求,假設(shè)所選數(shù)據(jù)集模糊指數(shù)m=2。

3.2 結(jié)果分析

為了驗證Canopy-FCMBM算法的有效性,本文基于Spark平臺,采用Spark On Yarn運行模式,使用實驗平臺中的4個worker節(jié)點去對UCI 3個不同大小和維度的數(shù)據(jù)集進行FCM算法、Canopy-FCM算法與Canopy-FCMBM算法分析比較,上述3個聚類算法結(jié)果如圖2所示。

圖 2 算法聚類準(zhǔn)確度對比Fig.2 Comparison of algorithm clustering accuracy

從圖2知,針對數(shù)據(jù)量少且數(shù)據(jù)維度少Iris數(shù)據(jù)集,改進后的Canopy-FCMBM的性能低于傳統(tǒng)的FCM,但是隨著數(shù)據(jù)量和屬性維度的增長,Canopy-FCMBM算法的性能明顯高于后兩者。聚類準(zhǔn)確率平均提升了12.7%。實驗結(jié)果表明,改進后的算法具有更好的聚類效果。

利用Canopy-FCMBM算法,針對上述數(shù)據(jù)集,分別在單機模式下和Spark計算框架下多個Worker節(jié)點進行試驗,計算聚類算法運行時間,實驗結(jié)果如圖3所示。

圖 3 單機模式與并行模式算法運行時間對比

從圖3可知,當(dāng)數(shù)據(jù)量不大時,聚類算法的運行時間較為接近。當(dāng)處理大規(guī)模數(shù)據(jù)集時,分布式的多節(jié)點明顯優(yōu)越于單機處理。這是因為,隨著節(jié)點增多,分布式處理進程也會增多,Spark的Master節(jié)點會讓W(xué)orker快速啟動Driver,SparkContext初始化之后Master節(jié)點會給各個Slave節(jié)點分配具體Task讓其執(zhí)行,同時,因task執(zhí)行時讀寫數(shù)據(jù)都在內(nèi)存中,也會加快算法執(zhí)行速度。

為進一步驗證Canopy-FCMBM算法的性能優(yōu)勢以及在Spark計算框架下的運行優(yōu)勢,實驗針對同一數(shù)據(jù)樣本Car Evaluation數(shù)據(jù)集,將集群節(jié)點擴展到5個,測試在Spark計算框架下與MapReduce計算框架下因Worker節(jié)點不同,聚類算法的運行時間對比,算法運行時間結(jié)果如圖4所示。

圖 4 Spark與MapReduce框架下聚類收斂時間比

由圖4可以看出,Spark的執(zhí)行效率要高于MapReduce。當(dāng)執(zhí)行節(jié)點數(shù)達到5個的時候,Spark的執(zhí)行效率大約為MapReduce的1.35倍,這是由于Spark使用RDD進行迭代計算的特點,將每次計算后的中間結(jié)果都保存在內(nèi)存中,減少對磁盤的I/O操作,可提高聚類速度。

4 結(jié) 語

隨著大數(shù)據(jù)逐漸日常化,傳統(tǒng)模糊C均值聚類算法在分析海量數(shù)據(jù)時存在聚類中心隨機取值,導(dǎo)致聚類結(jié)果不準(zhǔn)確等問題.本文將傳統(tǒng)FCM與Canopy算法結(jié)合,并將FCM目標(biāo)函數(shù)距離度量方式由歐式距離替換成馬氏距離,形成Canopy-FCMBM算法,這樣可以有效解決對于多維度且分布不均勻大數(shù)據(jù)聚類結(jié)果不準(zhǔn)確的問題。將Spark基于內(nèi)存處理的計算框架應(yīng)用于Canopy-FCMBM算法,大大提高了傳統(tǒng)FCM算法的計算性能以及大數(shù)據(jù)適應(yīng)能力。實驗結(jié)果表明,改進后的算法有較快的聚類速度和較高的聚類準(zhǔn)確率。但在研究中發(fā)現(xiàn),面對數(shù)據(jù)量較小的數(shù)據(jù)集時,基于Spark編程模型的Canopy-FCMBM算法優(yōu)越性難以體現(xiàn),其聚類的準(zhǔn)確率也相對低于傳統(tǒng)算法。此類問題,將作為下一步工作的研究內(nèi)容。