基于Spark 的聚類算法探討

紀(jì)兆華 王立東 宋海英 張小華

（ 1、北京信息職業(yè)技術(shù)學(xué)院，北京100018 2、共青團內(nèi)蒙古興安盟委員會，內(nèi)蒙古 烏蘭浩特137400 3、興安職業(yè)技術(shù)學(xué)院，內(nèi)蒙古 烏蘭浩特137400）

隨著信息技術(shù)深度的不斷發(fā)展， 積累的數(shù)據(jù)量產(chǎn)生了TB、PB、EB 級數(shù)據(jù)量。 傳統(tǒng)計算機的軟硬件不能夠支持足夠龐大的數(shù)據(jù)量的存儲、管理及數(shù)據(jù)分析能力，因此，針對大數(shù)據(jù)的分布式處理技術(shù)隨之產(chǎn)生， 主流的大數(shù)據(jù)處理平臺有Hdoop 和Spark。傳統(tǒng)的以Hdoop 為代表的數(shù)據(jù)處理技術(shù)不能滿足當(dāng)前應(yīng)用實時性以及迭代運算需求，Spark 作為基于內(nèi)存計算大數(shù)據(jù)處理平臺以其高速、多場景適用的特點成為大數(shù)據(jù)平臺的后起之秀，Spark 中 的Spark SQL、Spark Streaming、MLlib 和graphX 被廣泛的應(yīng)用在各領(lǐng)域，有望成為未來大數(shù)據(jù)分析的主流平臺。

1 Spark 的功能及體系結(jié)構(gòu)

Spark 主要提供基于內(nèi)存計算的開源， 能快速進行數(shù)據(jù)分析，具有通用性，是可擴展的分布式計算引擎。Spark 支持?jǐn)?shù)據(jù)查詢、機器學(xué)習(xí)等業(yè)務(wù)場景，業(yè)務(wù)場景能無縫交叉融合，在不同應(yīng)用中使用，可以快速的構(gòu)建高性能大數(shù)據(jù)分析[1]。

Spark 的體系結(jié)構(gòu)不同于Hadoop 的MapReduce 和HDFS，主要可分為三部分：Spark Core， 如： 彈性分布式數(shù)據(jù)集（ RDD，resilient distributed datasets）、 上下文（ Spark Context） 等實現(xiàn)Spark 系統(tǒng)中的計算、IO、 調(diào)度和shuffle 等系統(tǒng)基本功能；Spark Core 的上層建立的應(yīng)用框架，如：Spark SQL 查詢子項目、支持機器學(xué)習(xí)的MLlib 庫、GraphX 圖計算以及支持流計算的Spark Streaming 等四大框架；其他實驗性項目，如：Tachyon、BlinkDB 和Tungsten 等，這些項目共同組成Spark 體系結(jié)構(gòu)[2]。

Spark 用彈性分布式數(shù)據(jù)集進行數(shù)據(jù)抽象，可在內(nèi)存中存儲數(shù)據(jù)，將中間處理數(shù)據(jù)全部放到了內(nèi)存中，減少磁盤IO 達到性能的提升，大幅度的降低了運行時間[3]。

2 Spark 的特點

Spark 與其他大數(shù)據(jù)平臺不同的特點，主要如下：

2.1 處理速度快。 Spark 進行數(shù)據(jù)分析的速度快，彈性分布式數(shù)據(jù)集將執(zhí)行的多個查詢工作集緩存到內(nèi)存中，后面的數(shù)據(jù)查詢可以再次重用內(nèi)存中的工作集，提高了查詢速度。

2.2 支持語言多。 Spark 支持的開發(fā)語言環(huán)境多， 如Java、Scala、Python 及R 等進行工作，應(yīng)用范圍得到普及，允許在shell中進行交互式查詢，多種使用模式的特點讓應(yīng)用更靈活。

2.3 支持復(fù)雜查詢。Spark 支持map 和reduce 操作，以及SQL查詢、流式查詢等復(fù)雜查詢，它們都基于RDD 這一抽象數(shù)據(jù)集在不同業(yè)務(wù)過程中進行轉(zhuǎn)換，轉(zhuǎn)換代價小，統(tǒng)一引擎解決不同類型工作場景?？稍谕粋€工作流中無縫的搭配復(fù)雜查詢功能。

2.4 實施流處理。Spark 還支持實時流計算（ Spark Streaming）用來對數(shù)據(jù)進行實時處理，允許用戶快速開發(fā)流應(yīng)用程序，容錯能力強，集成性好，為流處理和批處理重用了同樣的代碼，可將流數(shù)據(jù)保存到歷史數(shù)據(jù)中

2.5 運行模式多。 Spark 可使用standalone 模式獨立的運行，也能在當(dāng)下的YARN 管理集群中運行，還可以讀取已有的任何Hadoop 數(shù)據(jù)，在HBase、HDFS 等任何Hadoop 數(shù)據(jù)源上運行，并能讓用戶在已有Hadoop 應(yīng)用遷移[4]。

3 基于Spark 的聚類算法

3.1 聚類算法

聚類算法把具有相同或者相似特征的無標(biāo)簽的數(shù)據(jù)對象劃分為同一簇，同一簇的數(shù)據(jù)對象在在特征上盡可能相近或者相似，不同簇的數(shù)據(jù)對象盡可能不同或者相異，并且每個數(shù)據(jù)對象要保證只能劃分在同一簇。 同一簇的中心點向量的個數(shù)和位置以及相似性度量的選取為聚類算法的重點內(nèi)容， 并通過聚類算法多次迭代執(zhí)行找到最優(yōu)的聚類結(jié)果。 聚類算法被分為如下幾類， 基于劃分方法有K-means 聚類算法、K-medoids 聚類算法等；基于層次方法有Agnes、Diana 等；根據(jù)密度方法有高斯混合(Gaussian mixture)等。 在聚類算法執(zhí)行過程中，能否分析識別出來整體數(shù)據(jù)對象分布的稠密和稀疏區(qū)域，能否發(fā)現(xiàn)哪些是存在的孤立點或者鼓勵簇[5]。

3.2 常用的聚類算法K-mean

K-means 是最常用的聚類算法，從算法的執(zhí)行過程來看，在每個類組中選取新的聚類中心點，通常使用歐式距離的多次迭代，達到最優(yōu)解。 聚類的步驟通常包括如下幾個步驟：a.選擇需要進行聚類分析的數(shù)據(jù)；b.計算分析數(shù)據(jù)對象之間的相似度，對分析的結(jié)果做量化處理，在相似矩陣中存儲；c.采用聚類算法做聚類分析；d.把分析結(jié)果顯示出來。 首先選取要分析的數(shù)據(jù)空間的k 個數(shù)據(jù)對象作為中心點，每個數(shù)據(jù)對象代表一個聚類中心[6]。

3.3 支持機器學(xué)習(xí)的MLlib 庫

MLlib 是Spark 生態(tài)系統(tǒng)在機器學(xué)習(xí)領(lǐng)域的重要應(yīng)用，是Spark 里的機器學(xué)習(xí)庫，提供了很多常用機器學(xué)習(xí)算法的分布式實現(xiàn)，如聚類、分類、回歸等。Spark MLlib 庫中的K-means 算法，使用map 分布式讀取數(shù)據(jù)集，數(shù)據(jù)集讀取后，cache 進內(nèi)存里。計算時， 選取用map 鍵值對表示隨機挑選出來的k 個聚類中心，Spark 的驅(qū)動器節(jié)點負(fù)責(zé)把數(shù)據(jù)發(fā)送到各個工作節(jié)點， 實現(xiàn)具體的計算任務(wù)。Spark MLlib 擴展性強、運行速度快，充分利用RDD 的迭代優(yōu)勢，能對大規(guī)模數(shù)據(jù)應(yīng)用機器學(xué)習(xí)模型，并能與Spark Streaming、Spark SQL 進行協(xié)作開發(fā)應(yīng)用， 讓機器學(xué)習(xí)算法在基于大數(shù)據(jù)的預(yù)測、推薦和模式識別等方面應(yīng)用更廣泛[7]。

使用Spark MLlib 做機器學(xué)習(xí)很簡單，首先對原始數(shù)據(jù)進行數(shù)據(jù)處理， 然后直接調(diào)用相應(yīng)的API 實現(xiàn)分析數(shù)據(jù)。Spark MLlib 不同于傳統(tǒng)的機器學(xué)習(xí)工具，Spark MLlib 提供了簡單易用的API， 特別是Spark 能夠高效的處理 大數(shù)據(jù)，并且在迭代計算時具有較強的優(yōu)勢。 因此，需要熟悉MLlib 的API就可以開始數(shù)據(jù)分析工作

結(jié)束語

Spark 是一個開源分析處理大數(shù)據(jù)平臺，基于Spark 的聚類算法在圖像分析、Web 文本分類、生物科學(xué)、客戶分群、市場營銷、 欺詐檢測以及信息安全與管理等領(lǐng)域有著廣泛的應(yīng)用，為應(yīng)對現(xiàn)實環(huán)境中復(fù)雜的場景，與不同的框架結(jié)合使用，發(fā)揮了更好的性能。 Spark 能快速處理多種場景下的大數(shù)據(jù)問題，高效挖掘大數(shù)據(jù)中的價值，為業(yè)務(wù)發(fā)展提供決策支持。