種子事件與新穎事件演化關(guān)系的話題檢測與追蹤*

胡耀斌 ，林培光 ，聶培堯 ，耿長欣 ，文 卉

（1.山東財經(jīng)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南250014；2.山東財經(jīng)大學(xué) 財政稅務(wù)學(xué)院，山東 濟(jì)南250014）

隨著信息技術(shù)的不斷發(fā)展，互聯(lián)網(wǎng)已經(jīng)成為人們獲得信息的主要來源之一，然而面對互聯(lián)網(wǎng)的海量信息，用戶要集中關(guān)注某個感興趣的主題時，往往感到無所適從。在這種情況下，話題檢測與追蹤TDT(Topic Detection and Tracking)應(yīng)運而生。TDT概念由美國國防高級研究計劃委員會DARPA(Defense Advanced Research Project Agency)在1996年提出，近些年關(guān)于TDT的研究得到迅速發(fā)展，目前已經(jīng)發(fā)展到第五代TDT技術(shù)評價階段[1]。

TDT對話題的定義為：一個話題由一個種子事件或活動以及與其直接相關(guān)的事件或活動組成。話題檢測的主要任務(wù)是檢測識別出系統(tǒng)未知的話題。話題追蹤被定義為用一個或幾個報道定義一個話題，在一個報道流中順序檢測出對該話題的所有相關(guān)報道[2]。

在話題檢測和追蹤領(lǐng)域存在一種現(xiàn)象，話題會隨著時間的變化轉(zhuǎn)移重心，例如當(dāng)某自然災(zāi)害發(fā)生時，新聞報道的內(nèi)容主要是該自然災(zāi)害造成的傷亡和損失，隨著事件的發(fā)生，新聞報道的重心則轉(zhuǎn)移到了災(zāi)后的救助和災(zāi)后重建，這種話題的動態(tài)演變稱為話題漂移。本文旨在提出一種能夠解決話題漂移的話題檢測與追蹤模型，使得TDT系統(tǒng)在追蹤話題漂移的報道時，能夠準(zhǔn)確地將其劃分到所屬的話題中。

1 國內(nèi)外研究現(xiàn)狀

國外對TDT的研究起步較早，最初的研究參與者不僅包括卡耐基梅隆大學(xué)、馬薩諸塞大學(xué)、賓州大學(xué)等一流的大學(xué)，還包括 IBM、GE、Dragon Systems等實力雄厚的公司。馬薩諸塞大學(xué)采用Rocchio算法，利用特征詞的不同權(quán)重組合實現(xiàn)自適應(yīng)的話題追蹤算法，證明了采用“NUC”權(quán)重計算方法可取得最優(yōu)性能[3]?？突仿〈髮W(xué)的研究者提出了一種基于決策樹的組合系統(tǒng)BORG TRACK，該系統(tǒng)在話題追蹤領(lǐng)域表現(xiàn)優(yōu)異[4]。IBM公司在話題檢測和追蹤系統(tǒng)中采用了兩次聚類的策略，使得系統(tǒng)在準(zhǔn)確率方面得到很大的提高[5]。另外還有多種不同方法在這項研究中被嘗試使用，如Single-Pass方法、貝葉斯算法、K-最近鄰居方法等，其中比較成功的有K-最近鄰居方法以及多種方法的組合。

話題檢測和追蹤已經(jīng)成為國內(nèi)信息處理領(lǐng)域的熱點問題，雖然國內(nèi)對TDT的研究相對國外起步較晚，但經(jīng)過多年的發(fā)展也取得了一些突出的研究成果。賈自艷[6]把命名實體融入到TDT系統(tǒng)中，并將時間信息考慮到文本相似性計算的閾值中，有效地提升了TDT系統(tǒng)跟蹤話題的性能。趙華[7]在TDT系統(tǒng)中考慮時間信息的重要性，提出了一種基于時間信息的動態(tài)閾值模型，證明了時間信息應(yīng)該在話題檢測系統(tǒng)中得到充分利用。

2 相關(guān)技術(shù)

2.1 報道模型

文本表示模型共有3種：布爾模型、概率模型及向量空間模型，其中向量空間模型應(yīng)用最為廣泛。本文采用向量空間模型作為文本表示模型。眾所周知，新聞報道包含4個要素：時間、地點、人物和事件。其中時間、地點、人物和組織機(jī)構(gòu)名等4種命名實體詞對新聞報道內(nèi)容的貢獻(xiàn)度大于其他特征詞。為區(qū)分命名實體詞和其他特征詞對文章的貢獻(xiàn)度，在構(gòu)造新聞報道向量空間模型時，提取上述4種命名實體詞作為命名實體向量，提取除命名實體詞外的其他特征詞作為內(nèi)容向量。

一個新聞文本可以表示為：R=(NR，CR)，其中 NR=(t1，x1；t2，x2； … ；ti，xi； … ；tn，xn)表 示 命 名 實 體 變 量 ；CR=(l1，y1；l2，y2；…；lj，yj；…；lm，ym)表示內(nèi)容向量。 ti表示命名實體特征詞，xi表示命名實體特征詞對應(yīng)的權(quán)重，lj表示內(nèi)容特征詞，yj表示內(nèi)容特征詞對應(yīng)的權(quán)重。

2.2 話題模型

為了方便報道和計算話題的相似度，話題模型應(yīng)該采取與報道模型相同的表示方法（向量空間模型）。一個話題模型可以表示為：T=(NT，CT)，其中 NT=（t1，z1；t2，z2；… ；ti，zi； … ；tn，zn） 表 示 命 名 實 體 變 量 ；CT=（l1，h1；l2，h2；…；lj，hj；…；lm，hm）表示內(nèi)容向量。 ti表示命名實體特征詞，zi表示命名實體特征詞對應(yīng)的權(quán)重，lj表示內(nèi)容特征詞，hj表示內(nèi)容特征詞對應(yīng)的權(quán)重。

在報道模型中，某特征詞的權(quán)重等于模型中所有報道的對應(yīng)特征詞權(quán)重的加權(quán)平均值，即：

其中num為話題模型中所含報道的個數(shù)。

每當(dāng)有新的報道被劃分到話題模型中后，都需要重新計算話題模型的權(quán)重，以完成話題模型的更新，目的是讓更新后的話題模型能夠體現(xiàn)出新加入報道對該模型的影響。

2.3 新聞報道中特征詞權(quán)重的計算

經(jīng)過一些文本預(yù)處理（去噪分詞）后，新聞文本被表示為一系列的詞，而詞與詞之間對文本的貢獻(xiàn)是不同的，如何計算這些詞的權(quán)重顯得很重要。顯而易見的是，出現(xiàn)次數(shù)越多的特征詞對文本的貢獻(xiàn)越高，表現(xiàn)形式越突出的特征詞對文本的貢獻(xiàn)越高，例如各級標(biāo)題中的特征詞或加粗后的特征詞要比那些普通的特征詞具有更高的貢獻(xiàn)。

本文在計算特征詞權(quán)重時，將特征詞分成兩部分。第一部分是命名實體特征詞和特殊內(nèi)容特征詞，命名實體特征詞指表示時間、人物、地點、組織機(jī)構(gòu)名的詞；特殊內(nèi)容特征詞指那些加粗或出現(xiàn)在各級標(biāo)題中的內(nèi)容特征詞。第二部分為除第一部分外，無明顯表現(xiàn)特征的普通內(nèi)容特征詞。

本文特征詞權(quán)重計算基于目前應(yīng)用最為廣泛的TF*IDF權(quán)重計算方法，tf(ti)表示特征詞在文檔中出現(xiàn)的次數(shù)，即詞頻 TF(Term Frequency)，idf(ti)表示 ti反文檔頻率 IDF(Inverse Document Frequency)，idf(ti)=lg(+1)，其中N表示文檔總數(shù)，df(ti)表示文檔集中含有ti的文檔數(shù)目，則權(quán)重計算公式為：wi=tf(ti)×idf(ti)。

關(guān)于第一部分特征詞的權(quán)重計算，本文定義了一組權(quán)重輔助值wλ來表示對第一部分特征詞中特征信息(命名實體)和表現(xiàn)形式信息(存在于各級標(biāo)題)的考慮，則該部分特征詞的權(quán)重計算公式為：wi=tf(ti)×idf(ti)+wλ。

第二部分特征詞的權(quán)重直接利用TF*IDF的權(quán)重計算方法，即 wi=tf(ti)×idf(ti)。

2.4 特征選擇

由于新聞文本中含有豐富的詞匯量，而能夠表示話題核心的詞匯卻只占一小部分，如果不對特征詞加以選擇，那么空間向量的維數(shù)會變得非常高，加大了相似度計算的復(fù)雜度，系統(tǒng)的性能也會隨之下降，這就要求對特征項加以選擇。本文采用隱含語義分析LSA（Latent Semantic Analysis）技術(shù)對文本向量實施降維，經(jīng)過驗證LSA是目前最好的降維方法之一。

隱含語義分析的核心思想是將特征項和文本映射到一個二維的向量空間(矩陣 Ai×j)中，假設(shè)這個矩陣的秩為r，其中每行代表一個特征詞的權(quán)重，每列代表一個文本。然后對矩陣進(jìn)行奇異值分解，即：A=UBVT，其中U 和 V 均 為 正 交 矩 陣，B=diag(β1，β2，…，βr)，然 后 在 這 r個特征值中取前k個。

2.5 相似性計算

根據(jù)新聞報道R與話題T的相似性計算結(jié)果判斷報道是新話題或是已存在話題。本文將相似度的計算分成兩部分，即新聞報道的命名實體向量與話題的命名實體向量二者之間的相似度(Simn)、新聞報道的內(nèi)容空間向量與話題的內(nèi)容空間向量二者之間的相似度(Simc)。

報道 R與話題 T之間的相似度為：Sim＝Simn+Simc，其中Simn、Simc采用余弦公式進(jìn)行計算：

3 話題檢測與追蹤算法

根據(jù)TDT對話題的定義，可知話題是由種子事件引起的，新聞報道的內(nèi)容則是圍繞種子事件進(jìn)行描述的。隨著事態(tài)的發(fā)展，種子事件可能會產(chǎn)生新的狀態(tài)或情況，新聞報道的內(nèi)容重心也產(chǎn)生了漂移，這種新的事態(tài)情況稱為新穎事件，這個過程即為種子事件到新穎事件的演化。新穎事件仍然屬于原始話題。在實際生活中，話題發(fā)生演變過程中，即新聞報道中產(chǎn)生新穎事件時，常常會有對種子事件或前一個新穎事件的回顧性描述，而且新穎事件一定是發(fā)生在種子事件之后。

根據(jù)上述內(nèi)容可以得出一個結(jié)論，即新穎事件的報道中常常會有對種子事件或前一個新穎事件的回顧性描述，而事件描述的主要內(nèi)容是時間、地點、人物等命名實體，這就意味著新聞報道的命名實體向量與所屬話題的命名實體向量具有高相似性。設(shè)定閾值為λ1，若不屬同一話題二者的命名實體向量的相似性則低于閾值λ1，然后比較新聞報道的內(nèi)容向量與模型的內(nèi)容向量相似度，若該相似度大于閾值λ2，則仍然認(rèn)為新聞報道屬于該話題。

該算法將報道按時間先后進(jìn)行排序，依次處理報道流中的報道。具體算法實現(xiàn)如下：

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

本文語料以日本政府購買釣魚島事件為例，選取了自2012年4月16日起900多篇語料，利用中科院分詞系統(tǒng)ICTCLAS進(jìn)行分詞和詞性標(biāo)注，計算出特征詞的詞頻以及相應(yīng)的特征詞權(quán)重。從中抽取200篇新聞報道作為樣本，發(fā)現(xiàn)每篇命名實體中的特征詞平均有121個，每篇內(nèi)容特征詞平均有224個，結(jié)合前面所述的特征選擇方法，選取命名實體特征詞前80個，選取內(nèi)容特征詞前160個。表1是4月17日新聞報道中部分高頻詞的權(quán)重。

表1 部分特征詞的詞頻與權(quán)重

本文TDT系統(tǒng)采用美國國家標(biāo)準(zhǔn)技術(shù)研究院制定的TDT評測體系，即采用準(zhǔn)確率、召回率以及二者的綜合指標(biāo)（F1-measure）來評價話題追蹤的效率。三個指標(biāo)的計算公式如下：

其中，A表示系統(tǒng)追蹤到的相關(guān)新聞報道數(shù)；B表示系統(tǒng)追蹤到的不相關(guān)新聞報道數(shù)；C表示系統(tǒng)未追蹤到的相關(guān)新聞報道數(shù)；D表示系統(tǒng)未追蹤到的不相關(guān)新聞報道數(shù)。

通過對前20個樣本的學(xué)習(xí)，得到參數(shù)的最優(yōu)值分別為：wλ＝0.07，λ1＝0.39，λ2＝0.44， 利用所得參數(shù)對剩余報道進(jìn)行話題追蹤，最終得到準(zhǔn)確率為95.24%，召回率為93.02%，F(xiàn)1-measure為94%。從評價指標(biāo)中可以看出本文提出的基于種子事件和新穎事件時序關(guān)系的話題檢測和話題追蹤模型實現(xiàn)了較好的效果，有效地解決了話題漂移帶來的問題。

本文首先介紹了TDT系統(tǒng)的相關(guān)技術(shù)，包括向量空間模型、特征詞權(quán)重計算、相似度計算等，為體現(xiàn)本系統(tǒng)所陳述的算法思想，并對這些相關(guān)技術(shù)在一定程度上進(jìn)行了改進(jìn)。另外，本文提出了種子事件和后續(xù)的新穎事件之間的時序關(guān)系，并在此基礎(chǔ)上提出了新的話題探測和追蹤模型。通過實驗證明，該模型能夠有效地解決話題漂移帶來的問題，保證了TDT系統(tǒng)的有效性。

[1]ALLAN J.Topic detection and tracking-event based information organization[M].Boston：Kluwer Academic Publisher，2002：1241-1253.

[2]CIERI C，STRASSEL S，GRAFF D.Corpora for topic detection and tracking[A].In：ALLAN J.Topic detection andtracking-event based information organization[M].Boston：Kluwer Academic Publisher，2002：33-66.

[3]ROECHIO J.Relevance feedback in information retrieval[A].In：SALTON G.The smart retrieval system：experiments in automatic document processing[M].New Jersey：Prentice Hall，1971：313-323.

[4]MITCHEN T M.機(jī)器學(xué)習(xí)[M].曾華軍，張銀奎，譯.北京：機(jī)械工業(yè)出版社，2003.

[5]ALLAN.Topic detection and tracking-Event-based Information Organization[M].Dordrecht：Kluwer Academic Publishers，2002.

[6]賈自艷，何清，張?？?，等.一種基于動態(tài)進(jìn)化模型的事件探測和追蹤算法[J].計算機(jī)研究與發(fā)展，2004，41(7)：1273-1280.

[7]趙華，趙鐵軍，趙霞.時間信息在話題檢測中的應(yīng)用研究[J].計算機(jī)科學(xué)，2008，35(1)：221-223.