面向大規(guī)模數(shù)據(jù)的在線新事件檢測

蔡偃武,高大啟,阮 彤,蔣銳權(quán)

(1.華東理工大學計算機科學與工程系,上海200237;2.上海證券交易所技術(shù)開發(fā)部,上海200120)

面向大規(guī)模數(shù)據(jù)的在線新事件檢測

蔡偃武1,高大啟1,阮 彤1,蔣銳權(quán)2

(1.華東理工大學計算機科學與工程系,上海200237;2.上海證券交易所技術(shù)開發(fā)部,上海200120)

通過分析基于新聞要素的在線新事件檢測算法的時間消耗,提出一種面向大規(guī)模數(shù)據(jù)環(huán)境的在線新事件檢測算法。該算法利用基于倒排索引的高效相似報道搜索機制,有效減少單路徑聚類算法中的相似度比較次數(shù)。通過對報道預處理、報道與事件比較以及索引搜索這3個過程的并行化,提高算法在多機環(huán)境下的運行效率和可伸縮性。實驗結(jié)果表明,該算法在不影響漏檢率和誤檢率的基礎(chǔ)上,提高了新事件檢測的速度,并且在千萬到億級別的報道規(guī)模下,其吞吐量達到150條/s～200條/s。

新事件檢測;單路徑聚類;大規(guī)模數(shù)據(jù);并行計算;倒排索引;MapReduce架構(gòu)

1 概述

隨著大數(shù)據(jù)時代的來臨,如何解決互聯(lián)網(wǎng)上的海量信息的過載問題,成為當前研究的一大熱點。解決互聯(lián)網(wǎng)信息過載的前提在于合理的組織信息,然后以一定的方式把信息提供給用戶。解決信息過載的一種方式是使用基于關(guān)鍵詞的信息檢索,該方法預先將海量信息按關(guān)鍵詞進行組織,用戶在需要查詢信息時,通過對指定關(guān)鍵詞進行匹配獲得相關(guān)信息。然而,基于關(guān)鍵詞信息檢索技術(shù)的局限性也非常明顯,在許多情況下,用戶難以用關(guān)鍵詞精準地表達自己的信息查詢意圖。因此,這種信息檢索方式越來越難以滿足人們的需求。

信息獲取的另一種方式是將信息以話題為主線來組織,然后通過話題來分類展現(xiàn)信息給用戶。話題是指一個種子事件或活動以及與之直接相關(guān)的事件或活動[1],以話題為主線組織信息的關(guān)鍵問題在于如何快速高效地從海量信息中發(fā)現(xiàn)話題并且跟蹤話題的發(fā)展。話題檢測與追蹤(Topic Detection and Tracking,TDT)技術(shù)是從新聞數(shù)據(jù)流中自動發(fā)現(xiàn)新話題并追蹤已知話題發(fā)展動態(tài)的信息智能獲取技術(shù)[2]。新事件檢測(New Event Detection,NED)作為話題檢測與追蹤的一項重要子任務(wù),其目標是從按時序順序到來的新聞源中識別新聞話題中一個事件的第—篇報道[3]。事件是指發(fā)生在特定時間和特定地點的事情[4](如神舟十號飛船發(fā)射升空),而不是指一個廣泛的概念(如中美關(guān)系)?？傮w而言,一個話題包含多個事件,事件則包含若干報道。NED的研究在現(xiàn)實中有廣泛的應(yīng)用,如信息源(電視、社交網(wǎng)絡(luò)等)的自動監(jiān)控、證券市場的分析、行業(yè)調(diào)研、個性化信息定制等。

通常影響NED性能的主要因素有3個:難以區(qū)分相似的事件,容易把屬于相同事件的報道誤報為不同事件,難以選擇報道歸并到事件的閾值和使用多維特征事件表示模型時各特征的權(quán)重系數(shù)。針對上述問題,文獻[5]提出一種利用新聞要素構(gòu)建表示模型的在線新事件檢測算法:將新聞的地點、人物和內(nèi)容3個特征提取形成三維向量表示報道和事件,并利用基于維基百科的簡單語義相似度計算方式判別報道與事件的相似性,有效地解決了前2個難點;同時使用基于SVM的分類算法訓練學習報道與事件的判別閾值以及各特征的系數(shù),利用機器學習方式有效地解決了閾值和系數(shù)的選擇問題。文獻[6]針對突發(fā)事件熱點話題識別系統(tǒng)提出一種正文裁剪方法和特征權(quán)重計算的改進模型,該模型具有更好的執(zhí)行效率和適應(yīng)性更強的文本表示能力。文獻[7]通過引入話題種子來改進面向互聯(lián)網(wǎng)話題識別的單路徑聚類算法,在降低漏檢率和誤檢率的同時提高了聚類速度。文獻[8]提出集合局部特征和全局特征的單路徑聚類算法,在網(wǎng)上論壇的話題識別中獲得了較好的性能。文獻[9]提出了用詞對來表示文本的方法,這種改進的向量空間模型優(yōu)化了對報道文本的表示模型。文獻[10]提出使用時間窗口策略的在線新事件檢測方法,該方法提升了新事件檢測的速度。然而,現(xiàn)有NED算法在投入到工程應(yīng)用中使用時,算法的效率問題成為主要瓶頸,主要原因為:與所有的基于單路徑的NED算法一樣,其整個過程為一串行的過程,先進行報道的預處理,然后每個到來的報道再與現(xiàn)有的事件逐個比較,因此,在最糟糕的(也是大多數(shù))情形下,其時間復雜度為O(n2),其中,n為報道數(shù)目。

本文在現(xiàn)有基于新聞要素的NED算法基礎(chǔ)上,著重解決算法的速度問題,進而提出有效的解決方案,并實現(xiàn)高速NED算法。

2 基于新聞要素的在線NED算法

2.1 報道和事件的表示模型

報道和事件的表示模型具體如下:

(1)報道預處理

在進行NED之前首先要對報道進行預處理,預處理步驟主要包括去重、分詞、詞性標注、除去停用詞。本文研究中的中文分詞和詞性標注工具采用的是北京理工大學張華平博士的NLPIR工具包[11]。

(2)新聞報道和事件的表示模型

從事件定義可以得知時間和地點為事件的2個主要特征,其實事件的另外兩大要素也同樣重要,即事件相關(guān)的人物和事件的主要內(nèi)容。同樣,對于一篇新聞報道,也可以使用這四大要素更精確地表示。傳統(tǒng)報道表示方法通常采用單一的文本向量表示,這種表示向量的維度一般比較高,使得計算變得過于復雜,又難以準確區(qū)分相似事件。因此,本文采用文獻[5]提出的一種基于新聞要素的報道與事件表示模型,它選用了報道的時間、人物、地點和普通內(nèi)容4個部分組成表示模型,其中,前3個部分采用向量空間模型表示;普通內(nèi)容是指具有實際意義的普通名詞和動詞。對于新聞報道來講“時間”是一個孤立的值,而對于事件來講“時間”是由第一篇報道時間和最近一篇報道時間所組成的時間段。因此,新聞報道和事件可以用以下形式表示:

報道={主體,地點,普通內(nèi)容,時間戳}

事件={主體,地點,普通內(nèi)容,時間段}

(3)增量TF-IDF模型

TF-IDF模型是一種計算詞權(quán)重的經(jīng)典模型,在該模型中一個詞在一個文檔中的頻率(TF)用從訓練語料中生成的逆文檔頻率衡量。在測試過程中出現(xiàn)新詞時,有2種解決方法:簡單地忽略該新詞或者設(shè)置該新詞的文檔頻率為常數(shù)1。第1種方法會導致新詞的權(quán)重為0,第2種方法會導致新詞項獲得過高的權(quán)重。為解決傳統(tǒng)TF-IDF模型的不足,本文利用增量式TF-IDF計算詞的權(quán)重,在增量TF-IDF中文檔頻率df(w)不是一個固定的常數(shù)而是隨著時間點變化。在時刻t通過更新頻率把一個新的測試文檔集合Ct加入到模型中,如式(1)所示:

其中,dfCt表示詞w在新加入的文檔集合Ct中的文檔頻率,初始的文檔頻率df0(w)從一個訓練集合生成。

在增量TF-IDF中沒有忽略新詞并且根據(jù)新詞在新文檔集合中的使用情況為其分配權(quán)重,由于新的事件經(jīng)常引進新詞,為新詞分配適當?shù)臋?quán)重可以改善模型效果。

在增量TF-IDF中,詞w在時刻t、文檔d中的權(quán)重如式(2)所示:

其中,tf(d,w)表示詞w在文檔d中出現(xiàn)的次數(shù);Nt表示在時刻t前采集到的報道總數(shù)。因此,一個文檔d在時刻t可以利用式(3)表示,n表示文檔d中相異的詞語總數(shù)。

采用基于新聞要素的報道表示模型,則一篇新聞報道S可以表示如下:S→{N,P,C,t},其中,N表示人名和機構(gòu)名;P表示地名;C表示具有實際意義的普通名詞和動詞;t表示報道的發(fā)布時間;N,P,C利用式(3)表示;事件E可以表示為E→{N,P,C, (te,t1)},tl表示事件E的最近一篇報道的時間,te表示E的第一篇報道的時間。

2.2 報道和事件相似度的計算

本文采用文獻[12]的報道和事件相似度計算方法,將報道和事件分成4個互不相關(guān)的部分,每個部分采用不同的文本表示模型。要計算報道和事件的相似度首先要分別計算幾個不同組成部分的相似度,包括地名部分的相似度、名稱部分的相似度以及普通內(nèi)容部分的相似度。通過這3個部分相似度的加權(quán)來表示報道S與事件E在t時刻的相似度,計算方法如式(4)所示:

其中,sim(S,E)表示報道和事件的相似度;sim(SP,EP),sim(SN,EN)和sim(SC,EC)分別表示報道和事件人名部分、地名部分及內(nèi)容部分的相似度,這些相似度分別由式(5)所示的余弦相似度公式計算得到;w1,w2,w3分別表示各部分的權(quán)重。

2.3 新事件檢測方法

新事件檢測方法主要是判斷報道和事件的相關(guān)性,而相關(guān)性是通過比較報道和事件的相似度與閾值的關(guān)系得出的,對于每個在t時刻接收到的報道S,式(6)的值是用于決定S是否是關(guān)于一個新事件的報道分數(shù)。

其中,t是報道S的發(fā)布時間,如果分數(shù)score(S)超過一定的閾值,則認為存在一個和報道S相似的事件,S歸為一個舊事件;否則意味著沒有與報道S相似的事件,S可以認為是新的事件。

目前絕大部分的在線新事件檢測算法都是基于單路徑聚類算法,本文采用此聚類方法,其算法具體過程如下:

(1)取報道流中一篇報道S,對其文本進行預處理,提取人名、地名和時間以構(gòu)建S的表示模型。

(2)如果事件類庫中尚不存在事件,則S作為第一篇報道,建立一個以S為中心的事件E,返回步驟(1)。

(3)如果事件類庫中已有事件,則使用式(4)對所有事件Ei計算Ei與報道S的相似度sim(S,Ei),求最大的相似度MaxSim以及達到最大相似度時的事件E。

(4)比較MaxSim與相似度閾值θ的大小,如果MaxSim未達到閾值,則認為S屬于新的事件,建立一個以S為第一報道的新事件類簇;如果MaxSim達到閾值,則認為報道S和事件E是相關(guān),將S歸入E中,并更新事件E。

(5)如果報道流中有未處理報道,返回步驟(1)繼續(xù)處理。

本文采用基于新聞要素的新事件檢測算法流程如圖1所示。

圖1 基于新聞要素的新事件檢測算法的流程

3 改進的快速NED算法

3.1 現(xiàn)有算法的時間消耗分析

從圖1可知,NED算法主要有3個步驟:預處理及轉(zhuǎn)化成表示模型,報道與事件的相似度計算,閾值判別及歸并到事件(報道達到合并到事件的閾值時)或創(chuàng)立事件(報道為一新事件時)。相對于前2個步驟,步驟3速度非常快,因為其操作次數(shù)為1次且操作過程非?？?。對于步驟1,每篇報道僅需要處理1次,因此其速度主要由所采用的NLP分詞、詞性標注等工具的處理速度決定。步驟2為算法中時間消耗最多的步驟,主要原因在于對于每篇報道,其計算次數(shù)隨報道數(shù)目成線性增長;而此步驟的總時間則隨報道數(shù)目的平方增長。因此,當算法運用于大規(guī)模數(shù)據(jù)處理時,其處理吞吐量會迅速下降。本節(jié)接下來著重解決提高預處理和報道與事件的相似度計算這2個步驟的速度。

3.2 報道預處理的并行化

在實驗環(huán)境下,報道通常依據(jù)嚴格的時間順序放入到NED算法中。在現(xiàn)實應(yīng)用中,尤其在大規(guī)模數(shù)據(jù)環(huán)境下,由于信息采集系統(tǒng)的工作原理決定了收集到的報道不可能完全符合時間的先后順序。然而,本文基于的NED算法及其他大多數(shù)NED算法并不需要時間具備嚴格的順序。

報道的預處理過程是獨立的,因此,該步驟可以輕易地進行并行化,僅需要啟用多個進行預處理的進程即可。而且并行化后的時間與并行進程的數(shù)目基本成反比。因此,當預處理步驟并行化后,理想情況下其時間可以忽略不計(只要有足夠多的硬盤設(shè)施)。

3.3 使用索引機制減少報道比較次數(shù)的方法

在現(xiàn)有的NED算法中,任何一條新到來的報道均需要與之前的事件進行比較,導致算法的復雜度為報道數(shù)目的平方。在現(xiàn)實應(yīng)用中,尤其在大規(guī)模數(shù)據(jù)情形下,這些比較絕大多數(shù)是無用的,比較得到的相似度很多都接近于0。既然如此,如果有一種機制,能把這些無效的比較預先進行過濾,將大大提高算法的效率。

在信息檢索中,倒排索引機制是進行文檔快速檢索的常用方式。倒排索引[13]是一種可以記錄文檔或文檔集中的單詞或關(guān)鍵詞在文檔中出現(xiàn)位置信息的一種索引數(shù)據(jù)結(jié)構(gòu)。這種索引方式是文檔全文檢索系統(tǒng)中最常使用的,它可以用于大規(guī)模的搜索引擎中。

通過分析報道與事件比較的計算方式,不難發(fā)現(xiàn),比較的過程實質(zhì)上就是一次查找最佳相似文檔的過程。因此,可以很自然地把索引方式引入到NED算法中。在時刻t0,現(xiàn)有的事件作為已有的索引文檔集合,而新到來的報道則作為搜索的目標,通過搜索即可找到與當前報道相似度最大的事件。倒排索引的效率是很高的,因此可大大提高算法的效率。在把倒排索引引入到NED算法中時,需要注意以下4點:

(1)本文使用多要素表示事件和報道,這些要素相當于倒排索引中的字段;

(2)并非所有的事件(報道)要素均可使用倒排索引:地點計算需要使用基于地理樹的語義相似度計算,時間戳也有其特定的算法,因此使用倒排索引的僅為主體要素和普通內(nèi)容要素;

(3)通過倒排索引得到的相似度值并不作為最終的相似度,因此,各要素的權(quán)重可依據(jù)經(jīng)驗值進行選取;

(4)通過倒排索引得到的值僅作為過濾NED算法中無效比較的參考值:對于某報道,最終選取的與其最相似的事件在倒排索引查找時必定也會得到較高的相似度。

引入倒排索引機制以過濾無效報道后,對于某報道,通常會選取相似度最大的特定數(shù)量(通過多次實驗,本文選取值為20)的事件進行準確地計算,從中選取真正與當前報道最相似的事件,判斷是否達到指定的閾值。

3.4 倒排索引設(shè)計與查找過程并行化

在NED中,事件和報道都是具備時效性的,報道與事件的相似度受它們之間的時間差距的影響非常大;因此,不能把所有的事件放入到一個倒排索引庫中。使用多索引的另一原因是效率問題,在大規(guī)模數(shù)據(jù)下,多個索引對速度的優(yōu)化也非常明顯。本文采用的基本時間單位是天,因此,對于一篇報道,它與過去某一天內(nèi)的所有報道的時間相似度因素是等同的。因此,本文采用以日期對索引庫進行分布的辦法,即同一日期的事件放到一個索引中。

在分開索引后,對于一篇報道,需要從有效時間范圍內(nèi)的所有索引庫中進行查找;顯然,此過程是可以并行進行的。多個索引查找完畢后,將結(jié)果合并排序,然后從中選取相似度值最大的一定數(shù)量的事件。

3.5 報道與事件比較過程的并行化

雖然整個NED過程是串行工作的,但對于一篇報道,它與現(xiàn)有報道的相似度計算是獨立的,也就是說可以并行計算的。因此,對于經(jīng)過倒排索引查找得到的特定數(shù)量的候選事件,并行化計算其真實相似度后,從結(jié)果中選取相似度值最大的事件與相應(yīng)的閾值進行對比。這個過程可使用MapReduce框架實現(xiàn),MapReduce框架的操作對象僅限于鍵值對＜key,value＞,其處理過程如式(7)所示:

在Map階段,輸入的鍵是新聞報道的URL,值是經(jīng)過預處理后的新聞報道,Map函數(shù)在不同處理節(jié)點上對每個新聞報道在分布式索引庫中進行搜索,Map輸出結(jié)果的鍵不改變,但是值是作為索引結(jié)果的候選事件。通過Combine階段將不同節(jié)點查找到的候選事件歸到一起,由Reduce階段的函數(shù)統(tǒng)一處理。在Reduce階段,計算每個報道的全部候選事件與報道的相似度,找出具有最大相似度的事件并輸出,輸出鍵值對的鍵是報道的URL,值是事件及最大相似度。

4 實驗結(jié)果與分析

4.1 評測語料

本文研究中的主要工作是對NED算法在速度上的改進,因此,本文需要使用大數(shù)據(jù)規(guī)模的語料。本文使用網(wǎng)頁采集爬蟲從互聯(lián)網(wǎng)采集了從2013年6月份的中文新聞報道,總數(shù)目為20 474 078。由于在大規(guī)模數(shù)據(jù)下,難以由人工驗證算法的結(jié)果,因此為了評估算法的其他性能,本文還采用了文獻[5]中的語料作為評估語料。

4.2 評測標準

在對新事件檢測算法測試結(jié)果分析時,通常采用由NIST為TDT建立的評測體系,該評測體系是在評測算法的誤檢率和漏檢率基礎(chǔ)上確立的。評測指標CDet由式(8)定義:

其中,CDet是性能損耗代價,綜合了漏檢率和誤檢率;CMiss是漏檢率的代價系數(shù);PMiss是漏檢率的條件概率;Ptarget和Pnon-target是先驗目標概率;CFA表示誤檢率代價系數(shù);PFA表示誤檢率的條件概率。評價TDT系統(tǒng)性能時常采用(CDet)Norm,它是CDet的規(guī)范化表示,由式(9)定義:

雖然本文主要工作側(cè)重于算法速度的改進而對于算法的漏檢率及誤報率方面并未在文獻[5]的基礎(chǔ)上作相應(yīng)改進,但是在改進算法速度時,對其中的算法過程進行了調(diào)整,可能會影響算法的誤報率和漏檢率。因此,本文將以文獻[5]中NED算法的結(jié)果作為對比評測標準,并同時使用其中的評測語料。

對于算法在速度性能上的改進,本文采用的是4.1節(jié)中所述的大規(guī)模數(shù)據(jù),同樣將與文獻[5]中的算法進行對比。

4.3 結(jié)果分析

本文對新的NED算法的漏檢率和誤報率進行了評估,得到的漏檢率-誤報率曲線[3]如圖2所示。由于SVM閾值法對算法參數(shù)進行了確定,因此得到并非曲線而是一個點。評測時,2種算法均使用手工閾值選取及使用SVM自動確定閾值的方式,而手工閾值均選用文獻[5]中確定的最佳值?？梢缘玫浇Y(jié)論,不論是采用何種閾值的確定方式,本文算法的改進對于算法的漏檢率和誤報率的影響小,基本可以忽略。

圖2 本文算法與文獻[5]算法的漏檢率-誤報率對比

然后,評估算法速度方面的性能,分別使用本文算法及文獻[5]算法在所選取的大規(guī)模數(shù)據(jù)集上運行。同時,為了評估算法時間與報道數(shù)目之間的關(guān)系,分別使用報道數(shù)目為10 000,100 000,1 000 000, 10 000 000以及所有的20 474 078,得到的時間消耗如表1所示(當算法消耗的時間大于100 h后,由于時間關(guān)系不能等待算法運行完畢)。由表1中可以得到以下結(jié)論:(1)本文算法的速度性能得到極大提高,尤其在大數(shù)據(jù)量時;(2)文獻[5]算法的時間復雜度基本為報道數(shù)目的平方,而本文算法的時間復雜度與報道數(shù)目成線性關(guān)系;(3)使用并行化處理使算法速度進一步提升,在C0和C1 2種情況下,算法速度都比文獻[5]快,A1同時使用了并行化預處理和并行化相似度比較,速度比C0和C1快。

表1為大規(guī)模數(shù)據(jù)集下各算法消耗的時間,其中,A0表示文獻[5]中使用手工閾值的算法;A1表示本文算法使用手工閾值;B0表示文獻[5]中使用SVM確定閾值的算法;B1表示本文算法使用SVM確定閾值;C0表示本文算法使用手工閾值但不用并行化預處理;C1表示本文算法手工閾值但不用并行化相似度比較。

本文對算法在處理大規(guī)模報道數(shù)據(jù)集的條件下進行可擴展性測試,實驗選擇報道庫中的5 000 000篇報道,測試計算節(jié)點數(shù)分別為3,4,6,8, 12,16情況下算法的消耗時間,結(jié)果如圖3所示。

圖3 系統(tǒng)消耗時間與節(jié)點數(shù)量的關(guān)系

從結(jié)果中可以發(fā)現(xiàn)隨著計算節(jié)點數(shù)的增加,會比較明顯地降低處理相同數(shù)據(jù)量時所需的時間,因此本文算法具有較好的可擴展性,在實際應(yīng)用中可以根據(jù)用戶數(shù)據(jù)規(guī)模需求來配置計算節(jié)點數(shù)目,滿足不同的用戶需求。

5 結(jié)束語

在線新事件檢測是從新聞報道流中識別出未知的事件。目前已有的自動在線新事件檢測方法能夠有效地檢測新事件,但幾乎均不適用于大規(guī)模數(shù)據(jù)環(huán)境下的在線新事件檢測。大規(guī)模數(shù)據(jù)下的在線新事件檢測需要算法具備極高的效率。為此,本文提出一種適用于大規(guī)模數(shù)據(jù)環(huán)境的在線新事件檢測算法,該算法在基于新聞要素的新事件檢測算法的基礎(chǔ)上進行了3個方面的改進:(1)使用并行的方式進行新聞報道的預處理;(2)利用高速索引機制,減少單路徑聚類算法中的比較次數(shù);(3)使用MapReduce架構(gòu)使聚類算法并行化。實驗結(jié)果表明,該算法提高了新事件檢測過程的速度,下一步將研究大規(guī)模數(shù)據(jù)下的熱點話題發(fā)現(xiàn)技術(shù)。

[1] Allan J,CarbonellJ,Doddington G,etal.Topic Detection and Tracking Pilot Study:Final Report[C]// Proceedings of DARPA Broadcast News Transcription and Understanding Workshop.[S.l.]:Lansdowne Press,1998.

[2] Allan J,Papka R,Lavrenko V.On-line New Event Detection and Tracking[C]//Proceedings of the 21st AnnualInternationalACM SIGIR Conference on Research and Development in Information Retrieval. Amherst,USA:University of Massachusetts,1998:37-45.

[3] 洪 宇,張 宇,劉 挺.話題檢測與跟蹤的評測及研究綜述[J].中文信息學報,2007,21(6):7l-85.

[4] Seo Y W,Sycara K.Text Clustering for Topic Detection [D].Pittsburgh,USA:Carnegie Mellon University,2004.

[5] 李營那.基于新聞要素的在線新事件檢測[D].上海:華東理工大學,2013.

[6] 陳莉萍,杜軍平.突發(fā)事件熱點話題識別系統(tǒng)及關(guān)鍵問題研究[J].計算機工程與應(yīng)用,2011,47(32):19-22.

[7] Yi Xiaolin,Zhao Xiao,Ke Nan,et al.An Improved Single-pass Clustering Algorithm Internet-oriented Network Topic Detection[C]//Proceedings of the 4th International Conference on IntelligentControland Information Processing.Beijing,China:[s.n.],2013: 560-564.

[8] Chen Feng,Du Juan,Qian Weining,etal.Topic Detection over Online Forum[C]//Proceedings of the 9th Web Information Systems and Applications Conference.Haikou,China:[s.n.],2012:235-240.

[9] 樊旭琴,張永奎.基于詞對向量空間模型的新事件檢測方法[J].計算機工程與應(yīng)用,2010,46(12):123-125.

[10] Xu Ruifeng,Peng Weihua,Xu Jun,et al.On-line New Event Detection Using Time Window Strategy[C]// Proceedings of 2011 International Conference on MachineLearning and Cybernetics.Guilin,China: [s.n.],2011:1932-1937.

[11] Zhang Huaping.NLPIR[EB/OL].(2013-06-01).http:// www.nlpir.org/.

[12] Allan J,Lavrenko V,Swan R.Explorations within Topic Tracking and Detection[M].[S.l.]:Kluwer Academic, 2002:197-224.

[13] Inverted Index[EB/OL].(2013-06-30).http://zh. wikipedia.org/w/index.php?title=Inverted Index&old id=19175626.

編輯 陸燕菲

Online New Event Detection for Large-scale Data

CAI Yan-wu1,GAO Da-qi1,RUAN Tong1,JIANG Rui-quan2
(1.Department of Computer Science and Technology,East China University of Science and Technology, Shanghai 200237,China;2.Technology Development Department,Shanghai Stock Exchange,Shanghai 200120,China)

Through analyzing the time consumption of the existing online New Event Detection(NED)algorithm based on news elements,this paper improves an online NED algorithm for large-scale data environment.The algorithm uses efficient reported similar search mechanism based on inverted index to reduce the similarity comparison of single path clustering algorithms.Through parallelization of report pretreatment,report and event comparison,index search,it improves the efficiency and scalability of the algorithm in multimachine.Experimental result shows that the algorithm can greatly improve new event detection speed without affecting the miss probability and false-alarm probability,and its throughput reaches 150～200 reports/s at the scale of 10～100 million reports.

New Event Detection(NED);single-pass clustering;large-scale data;parallel computing;inverted index; MapReduce architecture

1000-3428(2014)10-0037-06

A

TP391

10.3969/j.issn.1000-3428.2014.10.008

國家科技支撐計劃基金資助項目“證券業(yè)云平臺研發(fā)與運營”(2012BAH13F02)。

蔡偃武(1989-),男,碩士研究生,主研方向:話題檢測,模式識別,神經(jīng)網(wǎng)絡(luò);高大啟,教授、博士;阮 彤,副教授、博士;蔣銳權(quán),博士。

2013-10-18

2013-11-19E-mail:caiyanwu9988@163.com

中文引用格式:蔡偃武,高大啟,阮 彤,等.面向大規(guī)模數(shù)據(jù)的在線新事件檢測[J].計算機工程,2014,40(10):37-42.

英文引用格式:Cai Yanwu,Gao Daqi,Ruan Tong,et al.Online New Event Detection for Large-scale Data[J]. Computer Engineering,2014,40(10):37-42.