基于Spark平臺的熱點話題發現算法并行化研究

王新星

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

關鍵詞：話題發現；SinglePass；Spark平臺；Kernel Kmeans算法

DOIDOI：10.11907/rjdk.161712

中圖分類號：TP312

文獻標識碼：A文章編號文

章編號：16727800（2016）009005104

基金項目基金項目：

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

0引言

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

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

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

4結語

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

參考文獻參考文獻：

[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]賈自艷，何清，張海俊，等.一種基于動態進化模型的事件探測和追蹤算法[J].計算機研究與發展，2004，41（7）：12731280.

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

[5]格桑多吉，喬少杰，韓楠，等.基于SinglePass的網絡輿情熱點發現算法[J].電子科技大學學報，2015（4）：599604.

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

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

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

[9]ZAHARIA M，CHOWDHURY M，FRANKLIN 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.

責任編輯（責任編輯：孫娟）