基于Spark平臺的熱點話題發(fā)現(xiàn)算法并行化研究

王新星

摘要：話題發(fā)現(xiàn)中最常用的方法是基于增量式的SinglePass聚類算法，但是其依賴于文檔的輸入順序且效率低下。針對這兩個問題，提出在多層次話題發(fā)現(xiàn)基礎(chǔ)上，基于Spark平臺的算法并行化，將傳統(tǒng)的Kernel Kmeans算法進行并行化處理，以并行化的方式對數(shù)據(jù)進行初步聚類，并對后續(xù)數(shù)據(jù)進行增量式聚類。實驗表明，多層次處理提高了話題的準(zhǔn)確性；同時，并行化方式相比傳統(tǒng)的話題發(fā)現(xiàn)方法，其效率有較大提高。

關(guān)鍵詞：話題發(fā)現(xiàn)；SinglePass；Spark平臺；Kernel Kmeans算法

DOIDOI：10.11907/rjdk.161712

中圖分類號：TP312

文獻標(biāo)識碼：A文章編號文

章編號：16727800（2016）009005104

基金項目基金項目：

作者簡介作者簡介：王新星（1991-），男，陜西渭南人，西安工程大學(xué)計算機科學(xué)學(xué)院碩士研究生，研究方向為大數(shù)據(jù)、云計算。

0引言

隨著各種網(wǎng)絡(luò)社交媒體的普及，網(wǎng)絡(luò)平臺已成為人們了解社會動態(tài)、掌握社會熱點新聞的主要渠道，話題發(fā)現(xiàn)（Topic Detection，TD）成為當(dāng)前研究的熱點?？▋?nèi)基梅隆大學(xué)采用經(jīng)典的SinglePass算法識別新聞中的事件[1]，但是其過于依賴新聞報道的輸入順序。Forestiero等[2]提出了一種基于MultiAgent思想的SinglePass聚類，使用分散的自底向上和自組織策略對相似的數(shù)據(jù)點進行分類。賈自艷等[3]提出了一種基于動態(tài)進化模型的新聞事件話題發(fā)現(xiàn)算法，應(yīng)用基于時間距離的相似度計算模型自動對新聞資料進行組織，生成新聞專題。稅儀冬等[4] 針對增量式聚類初始時話題模型不夠充分和準(zhǔn)確的問題，提出周期分類和SinglePass相結(jié)合的話題識別與跟蹤方法，提高了話題的精度。格桑多吉等[5]結(jié)合網(wǎng)絡(luò)事件的時間距離，提出了改進的SinglePass算法，提高了文檔的相似度計算能力。

然而，上述研究都是通過算法自身來提高數(shù)據(jù)的處理能力與話題的聚類精度，并沒有考慮話題發(fā)現(xiàn)的效率。面對網(wǎng)絡(luò)信息的爆炸式增長，對于大規(guī)模且需要實時更新的數(shù)據(jù)處理，傳統(tǒng)方式已經(jīng)顯得力不從心。因此，結(jié)合大數(shù)據(jù)處理平臺將會是后續(xù)發(fā)展的必然趨勢。

目前，在處理海量數(shù)據(jù)方面，Hadoop是一個應(yīng)用比較廣的大數(shù)據(jù)處理平臺，基于Hadoop中的MapReduce并行化計算模型，可以高效地對海量數(shù)據(jù)進行挖掘處理。其中，Kmeans算法在Hadoop中的并行化已經(jīng)成為研究的熱點[68]。然而，Hadoop也存在一些不足，它需要不斷操作磁盤文件系統(tǒng)，將中間運行結(jié)果寫回文件系統(tǒng)，這樣在面對需要不斷迭代的操作過程時，其效率和性能會受到嚴(yán)重影響。為此，Apache開發(fā)了一種基于內(nèi)存的快速處理框架Spark[9]，其能更好地適用于數(shù)據(jù)挖掘與機器學(xué)習(xí)等需要迭代的MapReduce算法，使得在交互式數(shù)據(jù)分析和數(shù)據(jù)挖掘工作負載中表現(xiàn)得更加優(yōu)秀。因此，本文提出基于大數(shù)據(jù)處理平臺Spark的話題發(fā)現(xiàn)，以并行化的方式提高數(shù)據(jù)處理效率。

4結(jié)語

本文在結(jié)合多層次話題發(fā)現(xiàn)的基礎(chǔ)上，采用基于Kernel函數(shù)的Kmeans算法，借助Kernel函數(shù)在高維特征空間的轉(zhuǎn)換，提高了話題發(fā)現(xiàn)的精確度；同時實現(xiàn)了KernelKmeans算法在Spark平臺上的并行化，借助大數(shù)據(jù)處理平臺，改變了傳統(tǒng)話題發(fā)現(xiàn)算法的運行方式，從而解決了傳統(tǒng)方式對于大規(guī)模數(shù)據(jù)處理效率低下的問題，使得計算效率得到極大提高。實驗證明，其聚類結(jié)果更加準(zhǔn)確，且計算效率相比傳統(tǒng)方式有很大提高。

參考文獻參考文獻：

[1]BAEZAYATES R，RIBEIRONETO B.Modern information retrieval[M].Boston：Addison Wesley，2000.

[2]FORESTIERO A，PIZZUTI C，SPEZZANO G.A single pass algorithm for clustering evolving data streams based on swarm intelligence[J].Data Mining & Knowledge Discovery，2013，26（1）：126.

[3]賈自艷，何清，張?？。?一種基于動態(tài)進化模型的事件探測和追蹤算法[J].計算機研究與發(fā)展，2004，41（7）：12731280.

[4]稅儀冬，瞿有利，黃厚寬.周期分類和SinglePass聚類相結(jié)合的話題識別與跟蹤方法[J].北京交通大學(xué)學(xué)報：自然科學(xué)版， 2009，33（5）：8589.

[5]格桑多吉，喬少杰，韓楠，等.基于SinglePass的網(wǎng)絡(luò)輿情熱點發(fā)現(xiàn)算法[J].電子科技大學(xué)學(xué)報，2015（4）：599604.

[6]周婷，張君瑛，羅成.基于Hadoop的Kmeans聚類算法的實現(xiàn)[J].計算機技術(shù)與發(fā)展，2013，23（7）：1821.

[7]趙衛(wèi)中，馬慧芳，傅燕翔，等.基于云計算平臺Hadoop的并行Kmeans聚類算法設(shè)計研究[J].計算機科學(xué)，2011，38（10）：166168.

[8]江小平，李成華，向文，等.Kmeans聚類算法的MapReduce并行化實現(xiàn)[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2011，39（S1）：120124.

[9]ZAHARIA M，CHOWDHURY M，F(xiàn)RANKLIN M J，et al.Spark：cluster computing with working sets[J].Book of Extremes，2010，15（1）： 17651773.

[10]GIROLAMI MARK.Mercer kernelbased clustering in feature space[J].IEEE Transactions on Neural Networks，2002，13（3）：780784.

責(zé)任編輯（責(zé)任編輯：孫娟）