郝秀蘭，胡運發(fā)，申 情

（1.湖州師范學院 信息與工程學院，浙江 湖州313000；2.復旦大學 計算機科學與技術學院，上海200433）

網絡論壇中（又稱BBS）的帖子同所有的用戶生成內容（User－generated Content，UGC）一樣，具有以下特點：可以為不同背景、身份的用戶所創(chuàng)建；質量參差不齊，描述語言豐富多彩——書面語、口語、網絡用語等。如何對這些雜亂無章的內容進行監(jiān)控是安全部門所關心的重點之一，話題識別與跟蹤（Topic Detection and Tracking，TDT）是監(jiān)控的有效手段之一。

話題檢測與跟蹤是一項針對新聞報道進行信息識別、挖掘和組織的研究［1］。話題由一個種子事件以及后續(xù)直接相關的事件或活動組成；子話題是針對其中某一事件的相關描述；事件則定義為發(fā)生于特定時間和特定地點的事情。例如，“2001年9月11日針對美國世貿和五角大樓的恐怖襲擊”是話題“911”的種子事件，它與“災后處理”、“嫌疑犯調查”和“國際社會援助”等后續(xù)相關事件構成完整的“911”話題，其中對每個真實事件的相關描述構成了該話題內的不同子話題。但是，從種子事件到“災后處理”，話題已發(fā)生了“漂移”。

在TDT評測中，話題是由Nt個描述該話題的報道定義的。跟蹤系統(tǒng)根據給定的Nt個報道進行訓練，并對后繼的新聞報道流判斷出他們是否與給定的話題相關。

針對BBS的特點先提出了一個基線模型、一個解決“話題漂移”現象的改進模型、權重調節(jié)模型。從應對BBS帖子的不規(guī)范性及提高中文TDT系統(tǒng)的處理速度出發(fā)，提出了一種新的中文特征抽取方法。實驗結果顯示，該方法是有效的。

1 研究現狀

2004年TDT評測結束之后，國外文獻有關TDT的介紹較少。這里介紹的國外文獻絕大部分是2004年之前在TDT方面的研究，無論從問題定義、還是方法上，對TDT的研究都有重大影響和意義。國內的相關研究更側重基于TDT本身的特色進行探索，在方法上注重統(tǒng)計策略和自然語言處理技術相結合，在研究趨勢上逐步面向融入數據挖掘、信息抽取和篇章理解等相關技術。

1.1 話題跟蹤

傳統(tǒng)話題跟蹤主要基于統(tǒng)計，根據特征的概率分布，采用統(tǒng)計策略判別報道與話題模型的相關性。James Allan［2］采用Rocchio算法實施跟蹤。Franz等［3］則嘗試采用聚類方法將話題識別系統(tǒng)轉化成跟蹤系統(tǒng)。

基于統(tǒng)計策略的適應性話題跟蹤核心思想是系統(tǒng)可以根據偽相關反饋對話題模型進行自學習。在偽反饋過程中，所加入的話題只是種子事件的某一側面，會引起“話題漂移”。

為解決這一問題，LIMSI［4］在原有自學習過程中嵌入二次閾值截取功能，來削弱話題漂移。王會珍［5］采用增量式方法對話題跟蹤模型進行修正，在修正時考慮話題跟蹤任務基于時間的特點。鄭偉［6］基于改進的相關性模型，對跟蹤中偽相關反饋包含的新穎信息進行檢測和建模，跟蹤話題漂移。張輝等［7］針對新聞報道的特點，用三個維度：標題特征、內容特征、實體特征來刻畫一個文檔，構成三維文檔向量3DVM，并構建自適應的、基于kNN的追蹤器。

1.2 話題識別

統(tǒng)計模型的最大缺陷在于無法有效區(qū)分同一話題下的不同事件。Kumaran［8］、Yang［9］等學者使用自然語言處理（NLP）技術輔助統(tǒng)計策略解決新事件識別問題。Kumaran［8］將報道描述成三種向量空間：全集特征向量、僅包含NE的特征向量和排除NE的特征向量。Kumaran對比了三種向量空間模型對新事件識別的影響，發(fā)現NE在某些話題中可促進事件之間的區(qū)分，在另一些話題中效果卻不明顯。針對這一現象，Zhang Kuo［10］基于χ2分布統(tǒng)計TDT2中各NE類別與各話題類別的關聯(lián)性，并將這一關聯(lián)性的量化指標融入特征權重的再分配。

陳友等［11］提出一種基于噪音過濾的話題發(fā)現模型，從內容和用戶參與度兩個角度來檢測論壇話題。

Zhang［12］提出了基于話題的 T－tf×idf權重方式來度量模型中特征的重要性，用動態(tài)話題模型來解決兩個問題：話題漂移及話題中的噪聲。

陳友等［13］提出了一種通用的高質量主題發(fā)現框架，利用基于遺傳算法、禁忌搜索與機器學習的特征選擇算法提取內容特征，利用結構特征去發(fā)現高質量主題。

綜上所述，在TDT領域，為了提高識別與跟蹤性能，人們采用了統(tǒng)計與NLP相結合的方法，同時采用了多種方法并用的策略。在處理具體問題時，還考慮問題本身的特點。

2 話題跟蹤模型選擇

2.1 BBS帖子的特點

在BBS中，每一篇帖子都具有如下信息：發(fā)帖人標識、標題、內容、所屬版塊（也稱為社區(qū)）、發(fā)帖人IP地址、發(fā)帖時間等。例如，復旦日月光華BBS的新聞版塊主要包括以下幾個子社區(qū)：時事、房地產、海峽兩岸、證券投資／財經、軍事等。

內容相同的帖子，可能會發(fā)表在不同的社區(qū)。如，“黎巴嫩身上的三座大山：戰(zhàn)火把它變成戰(zhàn)爭代名詞”，有的人喜歡把它放在時事區(qū)，而有的人則會把它放在軍事區(qū)，還有人會把它同時放在這兩個社區(qū)里。也有可能被人從一個社區(qū)轉載到另一個社區(qū)。

同一標題下的帖子，通常第一個發(fā)帖人（樓主）的帖子較長，而回帖通常較短。

中文BBS的寫法更為隨意，有的人從頭到尾一個標點符號都不使用，只是使用換行；用語也更為豐富，漢語中夾雜有英文、英文縮寫、拼音、拼音縮寫，還有許多網絡用語，例如，“頂”、“ding”等都是常用詞匯。

2.2 基本模型

2.2.1 BBS中帖子的表示

面向BBS的話題識別與跟蹤仍然采用向量空間模型VSM來描述每一個帖子。對帖子首先進行分詞處理，濾掉停用詞。特征權重采用增量式TFIDF。用到的標記符號及其含義如表1所示。

表1 標記符號及其含義

在t時刻包含w的帖子數為：

時刻t收到的帖子s表示為

特征的權重表示為

對于較長的帖子，從帖子中選擇權重排在前1 000的特征來表示該帖子的內容。1 000個詞語足以使得大部分帖子的所有特征都包含進來，特別長的帖子用更為集中的特征來表示。

2.2.2 帖子的相似度計算

仍然采用余弦法來計算兩個帖子之間的相似度：

2.2.3 識別與跟蹤過程

整個識別與跟蹤過程采用TOD＋類心（Centroid）法。TOD算法即閾值順序依賴聚類算法，顧名思義，與閾值及數據的輸入順序密切相關，是一種單遍（Single－pass）聚類算法。在沒有話題可跟蹤時，只執(zhí)行話題識別任務：

○ 首先按時間順序對帖子進行排序；

○第一個話題：將出現最早的、由樓主發(fā)出的帖子及其跟帖組成的所有帖子，看作是一個類，形成偽類心，然后計算每個帖子與類心的相似度：

如果相似度小于一定閾值t1，則把這個帖子剔除出去；

否則，保留該帖；

最后再用保留的帖子計算真實類心；

○ 以后的每個話題都按第一個話題的方法，先產生偽類心，再產生真實類心，與前面的話題的真實類心進行相比：

如果與所有的話題相比，相似度都小于一定的閾值t2，則產生一個新的話題；

否則，歸入與它相似度最高的話題。

整個過程，可看作是兩個算法的嵌套，外層用的是TOD算法，內層用的是類心法。

對話題識別任務稍作修改，即可用于跟蹤任務：

對于每一待處理的話題，首先與需要跟蹤的話題進行相比，

如果相似度大于一定閾值t2，那么就認為是on－topic；

否則，用與話題識別相同的方法進行處理。

算法采用的是雙閾值方法，一個是計算同一標題下的跟帖是否與樓主討論的話題一致的閾值t1——標題內相似度閾值；另外，是后續(xù)話題與前面已產生話題進行比較的閾值t2，即判斷該話題是否是一個新話題——新話題閾值。

我們假設大多數的回帖都與樓主的帖子相關，所以標題內相似度閾值t1的設置較小。而進行跟蹤時所用到的閾值t2相對t1來說要大得多，可以通過它來控制所能跟蹤到的帖子的數量。

2.3 改進的識別與跟蹤過程

為了應對“話題漂移”現象，對上面的基準模型進行了修改，每個模型用兩個向量表示：

（1）種子向量

其中，s1表示關于某話題的首次帖子，即相應話題的樓主的帖子。由于標題是對帖子內容的概括，其中的詞含有表示帖子話題的詞。對于s1中出現的標題title中的詞，我們對其權重進行加重處理，即

（2）后續(xù)話題向量

假設話題Ti有N 個帖子，也就是有N－1個是跟蹤到的帖子，那么可用Trcaked向量來表示跟蹤到的后續(xù)話題向量：

其中，weight（Ti，N－1，wx）表示話題Ti后續(xù)帖子有N－1個時，后續(xù)話題向量中特征wx的權重。在時刻t，若又有一個帖子sk跟蹤到，那么Ti中將有N個跟蹤到的帖子，此時，后續(xù)話題向量權重的更新公式為

其中，sim（sk，Ti）表示話題Ti與帖子sk的相似度。也就是說，后續(xù)話題中出現的詞的權重已經按其與話題的相似度進行了加權，在一定程度上可以抑制與它相近而與原話題相差較遠的帖子的加入。

帖子s與話題Ti的相關度計算公式為：

2．4 權重改進模型

在這里我們借鑒Zhang Kuo［10］的思想，引入基于詞類及文本類別的權重調節(jié)。

詞類包括命名實體（人名、地名、組織名、日期、貨幣）、名詞、動詞、形容詞、副詞。不同的詞類在不同的話題間的作用是不同的，對特征權重按下式進行更新：

其中，type（w）為 w 的詞類，class（s）為s所屬文本類別，αck是類c、詞類為k的詞的權重調節(jié)參數。對于BBS的輿情監(jiān)督而言，較重要的信息有以下幾類：丑聞、犯罪、災害、軍事、財經等。參照Zhang Kuo［10］，αck的取值如表2所示。

表2 詞類在不同文本類別中的加權值

在本模型中，由于用到了文本類別，所以在實施話題識別與跟蹤前，需要對時事區(qū)中的帖子進行分類。因樓主的帖子所包含的信息量較大，先對樓主的帖子進行分類，跟帖的類別設置與樓主的帖子一致。我們使用kNN文本分類方法對樓主的帖子進行處理。動詞的加權值與名詞一樣，副詞的加權值與形容詞一樣。

3 特征選擇

常用的文檔特征有詞、短語和N－gram項，詞語是最直觀的表征文檔語義特征的方法。對于中文來說，需要借助于詞典和使用分詞技術。

為了在分類過程擺脫復雜的分詞程序，周［14－15］用N－gram項作為文檔的特征。但是，N－grams項的語義顯然沒有真正的詞那么明顯；同時，N－gram項的數目遠遠大于詞典中詞的數目，使算法的時間和空間消耗大大增加。

詞性也常常與其他種類的特征一起使用。例如，2．4節(jié)中與文本類別結合，對特征的權重進行調節(jié)。

在構建BBS話題識別與跟蹤系統(tǒng)中，考慮到帖子的不規(guī)范性及TDT系統(tǒng)的處理效率，我們嘗試使用了一種新的特征抽取方法——基于二元的準詞匯抽取方法。使用了以下幾個詞表：普通的準二字詞表（由二字詞、多字詞處理而成）、地名詞表。

3．1 普通詞表

由機器可讀詞典《現代漢語詞典》中的詞匯整理而成。一方面，由于單字詞的歧義很大，對區(qū)分話題的貢獻不大；另一方面，隨著抽取的2－grams的數目的增加，分類性能在不斷增加［15］，所以在普通詞表中，我們只收錄了二字及二字以上的詞匯。對于二字以上詞匯，進行如下處理：

設wordm＝τi1…τin，n＞2，那么可以把它拆分成n－1個二元項，即

例如，“精益求精”經過處理后，變成三個字串“精益”、“益求”、“求精”；而“計算機”經過處理，變成兩個字串“計算”、“算機”。最后，我們得到一個包含47 909個長度為兩個漢字的準詞匯表general＿bigram。

定義1 如果tf（s，w）＞1，那么詞w 在報道s中的出現次數是頻繁的。

定義2 如果dft（w）＞2，那么詞w在時刻t是頻繁的。

定理1 如果wordin在文檔s中是頻繁的，公式（11）的分解保證了τi1τi2，…，τi，n－1τin的頻繁性質。

證明：由Apriori性質證明，證明過程略。

定理2 在文檔s中，如果τi1…τi，n－1，τi2…τin是頻繁的，那么可以用它來生成1個長度為n的候選頻繁串。

定理3 在文檔s中，如果wordin是頻繁的，那么按式（11）分解之后的二元串不會破壞wordin的n元頻繁性，即wordin是可恢復的，且恢復后仍是頻繁的。

定理4 在文檔s中，對所有的長度大于2的頻繁普通詞按式（11）分解之后得到的二元串不會損失原有的詞信息。

由于篇幅所限，我們省略了以上定理的證明。

3.2 地名詞表

對于中國地名，我們收集了縣、區(qū)以上的地名共2 834個，并對其進行了縮寫處理。例如，“吉林省延邊朝鮮族自治州”縮寫為“延邊”等，這樣的特征更符合BBS發(fā)帖人的習慣。處理后得到的地名分布見表3。

表3 中國縣級以上地名長度及其分布

由表3可以得知，中國90%以上的縣級以上地名都可用兩個漢字來標識。對于三字及以上地名，我們也將其拆分為二元串，經過處理后，得到了3 039個二元字串。

對于外國地名，我們收集了240個國家和地區(qū)及其首都的名稱，長度及分布見表4。按式（11）分別拆分為二元串，得到了978個二元字串。

將中國地名二元字串及外國地名二元字串合并，最后得到一個包含3 981個二元字串的地名詞表place＿bigram。

表4 世界各國、首都地名長度及其分布

3.3 未登錄詞表

對于帖子標題，我們采用2－grams方法進行處理，以識別到gengeral＿bigram、place＿bigram 中未收錄的地名、人名、組織機構名等未登錄詞，將其放入unknown＿bigram中。

例1俄羅斯無法確認車臣匪首巴薩耶夫尸體

在例1里共有16個二元串，其中：俄羅、羅斯、無法、確認、匪首、尸體六個二元串可以由gengeral＿bigram、place＿bigram表確定為有意義的二元串。對于其他的二元串，可采用以下規(guī)則來修剪無意義的二元串。

R1對于字符串τi－2τi－1τiτi＋1τi＋2τi＋3，如果τi－2τi－1、τi＋2τi＋3是有意 義的二 元串，而τi－1τi、τiτi＋1、τi＋1τi＋2不能確定是否有意義，那么將τi－1τi、τi＋1τi＋2當作無意義的子串丟棄。

在例1里，斯無、法確、認車、首巴、臣匪、夫尸可用此規(guī)則修剪掉。最后可以得到以下四個未登錄的二元串：車臣、巴薩、薩耶、耶夫。

R2如果未登錄的二元串τiτi＋1出現在樓主的帖子s1中，那么保留；否則，修剪。

由于帖子標題的長度有限，用此方法進行處理既不耗時，又可以識別潛在的有意義的詞。

3.4 單字名詞表

包括地名的簡稱表abbr＿place、化學元素表chem＿element等。

有了以上詞表，我們就可以構造如圖1所示的基于二元的準詞匯抽取過程。與純2－grams相比，本方法在抽取二元特征的過程中避開了大量的無意義的二元串，從而提高了算法的時間效率和空間效率。由于避免了復雜分詞技術的使用，所以本特征抽取算法的時間效率要好于分詞算法。所抽取到的特征接近分詞程序（不會損失二字及二字以上的詞信息）。

圖1 基于二元的準詞匯抽取過程

4 實驗設置

4.1 數據集

由于沒有規(guī)范的語料，項目組從復旦大學日月光華BBS站上下載了一部分帖子，共有9 397篇帖子，進行了實驗。

4.2 評測

從漏檢和誤檢兩個角度進行評測，公式如下：

其中，PMiss和PFA分別表示系統(tǒng)的漏檢率和誤檢率，漏檢即為系統(tǒng)未識別出新話題，誤檢則是系統(tǒng)將舊話題的后續(xù)相關報道誤判為新話題；CMiss和CFA分別代表漏檢和誤檢的代價系數；Ptarget和Pnon－target是先驗目標概率。檢測錯誤代價CDet的規(guī)范化形式 Norm（CDet）如式（13）。

NIST面向TDT研究提供了可視化的評測工具，即檢測錯誤權衡圖（Detection Error Tradeoff，DET）。由于系統(tǒng)漏檢與誤檢的概率越低，其性能越好，因此DET曲線越靠近坐標系的左下角代表系統(tǒng)性能更優(yōu)。DET曲線上的最小規(guī)范化指標代表檢測系統(tǒng)的最佳性能，簡寫為Min Norm（Cost）。

計算時，設CMiss＝1，CFA＝0.1；Ptarget＝0.1①通常Ptarget設為0.02。在面向BBS的話題識別與跟蹤中，主要識別當前熱門討論的話題，因而目標出現的概率較高，我們采用了常用的10～90原則，即經常出現的話題占10%，另外一些不常見的話題占90%。。

4.3 閾值設置

人工對9 397篇帖子中的兩個話題：“黎巴嫩正式對以宣戰(zhàn)”、“朝鮮拒絕安理會導彈問題決議”進行了標注。經過對這兩個話題的識別與跟蹤進行分析，發(fā)現t2設為0.2時效果較好。t2值太大，發(fā)現不了新的相關話題，即漏報率PMiss太大；t2太小，則引入過多的噪聲，即誤報率PFA太大。

相似度計算中的α與鄭［6］一樣，設置為0.5。

4.4 實驗結果

4.4.1 模型比較

為了對本文所提的方法進行測試，我們設計并測試了三個系統(tǒng)?；€模型：實現了2.2節(jié)所介紹的基本模型；改進模型：實現了2.3節(jié)所介紹的改進的話題識別與跟蹤過程；

權重調節(jié)：在改進模型的基礎上，加入了zhang［10］所述的權重調節(jié)過程。

如圖2所示，改進模型優(yōu)于基線模型，而權重調節(jié)的改進模型又優(yōu)于單純的改進模型。

各模型的最小規(guī)范化代價為：

基線模型 Min（CDet）Norm＝0.307 5

改進模型 Min（CDet）Norm＝0.280 2

權重調節(jié)的改進模型

權重調節(jié)加改進模型較原來的基線系統(tǒng)上升了0.053 9。

4.4.2 特征比較

用純2－grams提取到的特征中無意義的字串比較多，以GB 2312－80國家標準為例，兩級字庫中共包括6 763個漢字，它們的二元組合數為6 763×6 763＝45 738 169，有四千五百多萬。所以，用純2－grams提取特征，其特征數會不斷上升。本文提到的基于二元的準詞匯抽取中，普通名詞和地名合起來，只有51 890個詞匯，所以普通詞和地名合起來的上限就是51 890?；诙臏试~匯抽取中的無意義的詞匯主要在標題的2－grams劃分過程中引入，通常標題的信息都是有用詞匯，所以在此引入的無意義詞匯是非常有限的。圖3顯示了用純2－grams方法、基于二元的準詞匯抽取方法抽到的特征數?？梢钥吹?，隨著帖子數的上升，純2－grams的特征數上漲很快。

圖2 面向BBS的DET圖

圖3 不同特征抽取方法所抽到的特征數比較

4.4.3 時間比較

受抽取到的特征數的影響，由圖4可以看到，隨著帖子數的上升，純2－grams的處理時間明顯變慢，基于二元準詞匯的處理時間變化不大。

圖4 不同特征抽取方法的處理時間比較

用分詞法取特征的實驗數據是經過分詞軟件預處理的，無法與其他兩個實驗進行比較。由于BBS文檔不規(guī)范，加工了近一周時間，才完成9 397篇語料的分詞及詞性標注。

5 討論

在對現有的話題識別與跟蹤方法進行研究的基礎上，我們提出了三個面向BBS的話題識別與跟蹤模型，實驗結果顯示，所提的模型可以較好地完成識別與跟蹤任務。

在實現面向BBS的話題識別與跟蹤系統(tǒng)過程中，我們的感受是語料太不規(guī)范。例如，有的人發(fā)表言論時，不使用標點符號，這就使得依賴于標點符號進行文本塊分割的分詞程序顯得無能為力。所以，語料的規(guī)范是面向應用時首先需要解決的問題。

另外，BBS中有“掛羊頭，賣狗肉”現象，看標題在說一件事情，但實際上內容與標題是不一致的，也是一種變相的“話題漂移”。怎么樣識別同一標題下，內容不屬同一話題的帖子，也是一個值得研究的問題。

［1］Yang Y，Carbonell J，Brown R，et al.Learning Approaches for Detecting and Tracking News Events［J］.In IEEE Intelligent Systems Special Issue on Applications of Intelligent Information Retrieval，14（4），1999：32－43.

［2］J.Allan，R.Papka，V.Lavrenko.On－line New Event Detection and Tracking ［C］／／Proceedings of SIGIR'98.University of Massachussetts：Amherst，1998，37－45.

［3］M.Franz，J. S. McCarley. Unsupervised and supervised clustering for topic tracking ［C］／／Proceedings of the 24th annual international ACM SIGIR，New Orleans，Louisiana，USA：ACM，2001：310－317.

［4］Y.Lo，J.L.Gauvain.The LIMSI Topic Tracking System for TDT 2002 ［C］／／Topic Detection and Tracking Workshop，Gaithersburg，USA，2002.

［5］王會珍，朱靖波，季鐸，等.基于反饋學習自適應的中文話題跟蹤［J］.中文信息學報，2006，20（3）：92－98.

［6］鄭偉，張宇，鄒博偉，等.基于相關性模型的中文話題跟蹤研究［C］／／全國第九屆計算語言學學術會議，2007：558－563.

［7］張輝，周敬民，王亮，等.基于三維文檔向量的自適應話題追蹤器模型［J］.中文信息學報，2010，24（5）：70－76.

［8］G.Kumaran，J.Allan.Text classification and named entities for new event detection ［C］／／Proceedings of the SIGIR Conference on Research and Development in Information Retrieval.Sheffield，South Yorkshire：ACM，2004：297－304.

［9］Y.Yang，J.Carbonell，etc.Topic－conditioned novelty detection ［C］／／Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2002：688－693.

［10］Zhang Kuo，Li Juan Zi， Wu Gang.New Event Detection Based on Indexing－tree and Named Entity［C］／／Proceedings of the SIGIR 2007， ACM：Amsterdam，2007：215－222.

［11］陳友，程學旗，楊森，等.面向網絡論壇的突發(fā)話題發(fā)現［J］.中文信息學報，2010，24（3）：29－36.

［12］X.Zhang，T.Wang.Topic Tracking with Dynamic Topic Model and Topic－based Weighting Method［J］.Journal of Sofware，2010，5（5）：482－489.

［13］陳友，程學旗，楊森，等.面向網絡論壇的高質量主題發(fā)現［J］.軟件學報，2011，22（8）：1785－1804.

［14］周水庚，關佶紅，俞紅奇，等.基于N－gram信息的中文文檔分類研究［J］.中文信息學報，2001，15（1）：34－39.

［15］周水庚，關佶紅，胡運發(fā)，等.一個無需詞典支持和切詞處理的中文文檔分類系統(tǒng)［J］.計算機研究與發(fā)展，2001，38（7）：839－844.