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

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

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

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

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

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

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

1 概述

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

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

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

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

2 基于新聞要素的在線(xiàn)NED算法

2.1 報(bào)道和事件的表示模型

報(bào)道和事件的表示模型具體如下:

(1)報(bào)道預(yù)處理

在進(jìn)行NED之前首先要對(duì)報(bào)道進(jìn)行預(yù)處理,預(yù)處理步驟主要包括去重、分詞、詞性標(biāo)注、除去停用詞。本文研究中的中文分詞和詞性標(biāo)注工具采用的是北京理工大學(xué)張華平博士的NLPIR工具包[11]。

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

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

報(bào)道={主體,地點(diǎn),普通內(nèi)容,時(shí)間戳}

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

(3)增量TF-IDF模型

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

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

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

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

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

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

2.2 報(bào)道和事件相似度的計(jì)算

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

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

2.3 新事件檢測(cè)方法

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

其中,t是報(bào)道S的發(fā)布時(shí)間,如果分?jǐn)?shù)score(S)超過(guò)一定的閾值,則認(rèn)為存在一個(gè)和報(bào)道S相似的事件,S歸為一個(gè)舊事件;否則意味著沒(méi)有與報(bào)道S相似的事件,S可以認(rèn)為是新的事件。

目前絕大部分的在線(xiàn)新事件檢測(cè)算法都是基于單路徑聚類(lèi)算法,本文采用此聚類(lèi)方法,其算法具體過(guò)程如下:

(1)取報(bào)道流中一篇報(bào)道S,對(duì)其文本進(jìn)行預(yù)處理,提取人名、地名和時(shí)間以構(gòu)建S的表示模型。

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

(3)如果事件類(lèi)庫(kù)中已有事件,則使用式(4)對(duì)所有事件Ei計(jì)算Ei與報(bào)道S的相似度sim(S,Ei),求最大的相似度MaxSim以及達(dá)到最大相似度時(shí)的事件E。

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

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

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

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

3 改進(jìn)的快速NED算法

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

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

3.2 報(bào)道預(yù)處理的并行化

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

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

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

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

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

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

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

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

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

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

引入倒排索引機(jī)制以過(guò)濾無(wú)效報(bào)道后,對(duì)于某報(bào)道,通常會(huì)選取相似度最大的特定數(shù)量(通過(guò)多次實(shí)驗(yàn),本文選取值為20)的事件進(jìn)行準(zhǔn)確地計(jì)算,從中選取真正與當(dāng)前報(bào)道最相似的事件,判斷是否達(dá)到指定的閾值。

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

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

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

3.5 報(bào)道與事件比較過(guò)程的并行化

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 評(píng)測(cè)語(yǔ)料

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

4.2 評(píng)測(cè)標(biāo)準(zhǔn)

在對(duì)新事件檢測(cè)算法測(cè)試結(jié)果分析時(shí),通常采用由NIST為T(mén)DT建立的評(píng)測(cè)體系,該評(píng)測(cè)體系是在評(píng)測(cè)算法的誤檢率和漏檢率基礎(chǔ)上確立的。評(píng)測(cè)指標(biāo)CDet由式(8)定義:

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

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

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

4.3 結(jié)果分析

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

圖2 本文算法與文獻(xiàn)[5]算法的漏檢率-誤報(bào)率對(duì)比

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

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

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

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

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

5 結(jié)束語(yǔ)

在線(xiàn)新事件檢測(cè)是從新聞報(bào)道流中識(shí)別出未知的事件。目前已有的自動(dòng)在線(xiàn)新事件檢測(cè)方法能夠有效地檢測(cè)新事件,但幾乎均不適用于大規(guī)模數(shù)據(jù)環(huán)境下的在線(xiàn)新事件檢測(cè)。大規(guī)模數(shù)據(jù)下的在線(xiàn)新事件檢測(cè)需要算法具備極高的效率。為此,本文提出一種適用于大規(guī)模數(shù)據(jù)環(huán)境的在線(xiàn)新事件檢測(cè)算法,該算法在基于新聞要素的新事件檢測(cè)算法的基礎(chǔ)上進(jìn)行了3個(gè)方面的改進(jìn):(1)使用并行的方式進(jìn)行新聞報(bào)道的預(yù)處理;(2)利用高速索引機(jī)制,減少單路徑聚類(lèi)算法中的比較次數(shù);(3)使用MapReduce架構(gòu)使聚類(lèi)算法并行化。實(shí)驗(yàn)結(jié)果表明,該算法提高了新事件檢測(cè)過(guò)程的速度,下一步將研究大規(guī)模數(shù)據(jù)下的熱點(diǎn)話(huà)題發(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] 洪 宇,張 宇,劉 挺.話(huà)題檢測(cè)與跟蹤的評(píng)測(cè)及研究綜述[J].中文信息學(xué)報(bào),2007,21(6):7l-85.

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

[5] 李營(yíng)那.基于新聞要素的在線(xiàn)新事件檢測(cè)[D].上海:華東理工大學(xué),2013.

[6] 陳莉萍,杜軍平.突發(fā)事件熱點(diǎn)話(huà)題識(shí)別系統(tǒng)及關(guān)鍵問(wèn)題研究[J].計(jì)算機(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] 樊旭琴,張永奎.基于詞對(duì)向量空間模型的新事件檢測(cè)方法[J].計(jì)算機(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

國(guó)家科技支撐計(jì)劃基金資助項(xiàng)目“證券業(yè)云平臺(tái)研發(fā)與運(yùn)營(yíng)”(2012BAH13F02)。

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

2013-10-18

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

中文引用格式:蔡偃武,高大啟,阮 彤,等.面向大規(guī)模數(shù)據(jù)的在線(xiàn)新事件檢測(cè)[J].計(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.