王新星

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

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

DOIDOI：10.11907/rjdk.161712

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文

章編號(hào)：16727800（2016）009005104

基金項(xiàng)目基金項(xiàng)目：

作者簡(jiǎn)介作者簡(jiǎn)介：王新星（1991-），男，陜西渭南人，西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，研究方向?yàn)榇髷?shù)據(jù)、云計(jì)算。

0引言

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

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

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

4結(jié)語(yǔ)

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

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

[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]賈自艷，何清，張海俊，等.一種基于動(dòng)態(tài)進(jìn)化模型的事件探測(cè)和追蹤算法[J].計(jì)算機(jī)研究與發(fā)展，2004，41（7）：12731280.

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

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

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

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

[8]江小平，李成華，向文，等.Kmeans聚類(lèi)算法的MapReduce并行化實(shí)現(xiàn)[J].華中科技大學(xué)學(xué)報(bào)：自然科學(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é)任編輯：孫娟）