面向互聯網新聞的話題檢測與追蹤

摘要： 為了更加準確有效地從海量的互聯網網頁中獲取感興趣的信息，設計并實現了一個面向互聯網新聞的話題追蹤與檢測系統，并在該系統的基礎上提出了面向海量互聯網網頁時話題檢測中聚類算法選擇策略以及一個基于多重特征的話題追蹤模型，該模型能夠很好地區分相似與相同的話題，并且話題追蹤正確率達到了８５．７％，實驗結果表明文中系統能夠有效地檢測和追蹤互聯網上的話題。

關鍵詞：

中圖分類號： ＴＰ３９１ 文獻標識碼：Ａ 文章編號：２０９５－２１６３（２０１１）０１－００５９－０４

０引言

互聯網因其時效性強，交互性好等特點，已經成為人們日常獲取信息的重要途徑，但是面對每天新增的海量的互聯網網頁，人們往往難以從中準確有效地獲取到自己感興趣的信息，在這種情況下，話題檢測與追蹤受到了越來越多研究者的關注。

話題檢測與追蹤的主要任務是在缺乏話題先驗知識的前提下，檢測出系統未知的話題，并追蹤已知話題的后續報道，所以話題檢測和追蹤系統必須在假設沒有話題的先驗知識的前提下構造話題模型，并且該模型必須適用于所有話題，而不是局限于某一話題[１]。在這一領域已經有很多研究者做了許多深入的工作，ＫＵＭＡＲＡＮ[２]用自然語言處理的技術輔助統計策略來提高話題檢測和追蹤的正確率，并驗證了命名實體名詞對區分不同的話題有著重要的作用；ＰＡＰＫＡ[３]對話題檢測中不同的聚類算法進行了對比研究，并提出了一種融合各自優點的聚類策略；ＡＬＬＡＮ Ｊ[４]的話題追蹤系統嵌入了自學習模塊，利用后續報道更新話題模型；ＹＡＮＧ[５]在計算兩個話題相似度時引入了時間衰減函數。相對于國外學者更側重于以統計概率模型為主體進行的研究，國內學者的研究則主要側重于研究話題檢測與追蹤本身的特點。賈自艷等[６]提出標注時間、地點、人物等命名實體，在權重計算時提高命名實體的權重系數；駱衛華[７]針對層次化話題模型進行了研究；宋丹[８]則基于地點名詞建立地理樹，并根據地點名詞在地理樹中的路徑覆蓋率來計算兩個話題的相似度。

基于以上討論，可以看出目前國內外的研究主要集中在話題檢測與追蹤（ＴＤＴ）評測數據上，而面向互聯網新聞的話題檢測與追蹤的研究卻較少。雖然一系列改善話題檢測和追蹤效果的模型及算法被相繼提出，有效地提高了話題檢測與追蹤的正確率，但是這些模型大多只適用于評測數據，并不能完全適用于互聯網的海量數據。針對互聯網上的新聞報道冗余性高、數據量大、易漂移，持續時間長等特點，本文進行了面向互聯網新聞的話題檢測與追蹤系統研究，實驗結果證明文中的系統達到了實用的程度，能夠正確地檢測并追蹤到互聯網上出現的熱點話題。

１話題檢測與追蹤

本文所討論的面向互聯網網頁的話題檢測和追蹤系統主要包含：數據層、話題層、分析層、用戶層等模塊，如圖１所示。

１．１數據層

數據層的任務是抽取爬蟲抓取到的互聯網網頁中新聞正文文本、標題、時間、ＵＲＬ等結構化信息，然后進行分詞、

過濾停用詞、詞性標注等處理。因為新聞報道中最重要的是人物、時間、地點等命名實體，所以在此引入了命名實體識別的工具來標示命名實體。

１．２話題層

１．２．１向量空間模型（ＶＳＭ）

話題層的輸入是經過數據層預處理后的新聞文本集合?；跁r間與正確率的考慮，采用向量空間模型來表示新聞文本。假設Ｄｉ是一個預處理后的新聞文本，則Ｄｉ可以表示為（ｔｅｒｍ１，ｗｉ１；ｔｅｒｍ２，ｗｉ２，…；ｔｅｒｍｋ，ｗｉｋ）。ｗｉｋ表示第ｋ個詞在文檔Ｄｉ中的權重，采用公式（１）中定義的ＴＦ?觹ＩＤＦ公式來計算特征詞的權重ｗｉｋ。

式中，ｔｆｉｋ代表ｔｅｒｍｋ在新聞文本Ｄｉ中出現的次數，ｉｄｆｋ代表ｔｅｒｍｋ在所有文檔中出現的次數。

在經過對大量新聞語料的分析后，發現人物、地點和時間等命名實體是區分不同新聞文本的重要因素[２]，而一篇新聞的標題往往就是一篇新聞文本的主旨，所以本文在計算權重時增加了這些詞在相應文檔中的權重，采用了如公式（２）所示的改進的ＴＦ?觹ＩＤＦ計算公式。

式中，采用權重系數Ｗ來控制ｗｉｋ的大小。在計算命名實體以及新聞標題權重時，需賦予Ｗ＞１，以提高這些詞在相應的文檔中的權重；Ｎ代表新聞文檔的總數。

１．２．２話題檢測

話題檢測的關鍵技術是文檔聚類算法[９]，聚類算法的選擇直接影響到話題檢測的正確率和召回率。與傳統的ＴＤＴ評測數據相比，本文所處理的海量的新聞文本具有冗余性高、數量龐大、動態更新的特點。

針對互聯網海量網頁的這些特點，對各種聚類算法進行了深入的研究：基于劃分的方法需要預先提供劃分的個數；基于密度的方法時間復雜度為Ｏ（ｎ２）；基于網格的方法算法效率較高，但是聚類的精確度較低[３]，等。綜合評判后，文中選用了ＢＩＲＣＨ（Ｂａｌａ－ｎｃｅｄ Ｉｔｅｒａｔｉｖｅ Ｒｅｄｕｃｉｎｇ ａｎｄ Ｃｌｕｓｔｅｒｉｎｇ ｕｓｉｎｇ Ｈｉｅｒａｒｃｈｉｅｓ）聚類算法[１０]，因其較好地滿足了研究工作的要求：

首先，ＢＩＲＣＨ是一種層次聚類算法，不需要預先給出劃分的個數，滿足互聯網上每天產生的熱點話題數目不固定的要求。

其次，ＢＩＲＣＨ聚類算法的Ｉ/Ｏ花費與數據量成線性關系，因此ＢＩＲＣＨ算法的聚類速度較快，滿足互聯網上每天海量網頁、大數據量、高復雜性的要求。

最后，ＢＩＲＣＨ聚類算法具有增量式聚類的特性，當遇到新的文檔集時，不需要全部重新聚類，滿足話題隨著時間而動態更新的需求。

１．２．３話題追蹤

話題追蹤是整個系統的核心部分，其流程如圖２所示。

話題追蹤的主要任務是：判斷一個話題是否為已有話題。如果是已有話題，則更新該話題信息；反之，如果是首次出現的話題，則將其添加到已有話題集。

話題追蹤的關鍵技術是話題間的相似度計算。一個有效的度量兩個話題之間相似度的方法是：如果兩個話題在“距離”上越近，則其相似度就越高。基于這個原理，采用了余弦相似度計算公式，即兩個話題ｔｉ，ｔｊ之間的相似度定義如公式（３）所示。

式中，ｗｋｉ是第ｋ個詞 在話題 ｉ中的權重，ｗｋｊ是第ｋ個詞在話題ｊ中的權重．。

經過實驗后，分析可知兩個話題發生的時間間隔越小，是同一話題的概率就越高[５]。基于上述原理，引入了如公式（４）所示的時間衰減函數。

Ｔ（ｔｉ，ｔｊ）＝１－ｔｍ （４）

公式中，參數ｍ是衰減因子，用來控制衰減速度和話題追蹤的最大間隔時間，ｔ代表了兩個話題的間隔時間。最終的兩個話題之間的相似度計算公式如公式（５）所示。

ｓｉｍ（ｔｉ，ｔｊ）＝ｃｏｓ（ｔｉ，ｔｊ）＋Ｔ（ｔｉ，ｔｊ）（５）

由進一步的實驗分析獲知：采用公式（５）仍難以區分相似與相同的話題，再經過大量的語料分析，推證可得：命名實體與其他詞在確定一個話題時起著不同的作用。命名實體主要描述話題中的時間、地點、人物信息，而其他詞則主要描述話題中發生了什么。通過上述分析，提出了基于多重特征的話題追蹤模型來計算兩個話題的相似度，特征定義如下所示。

（１）利用話題中所有的詞，計算兩個話題的相似度，定義為ｄ１；

（２）利用話題中命名實體，計算兩個話題的相似度，定義為ｄ２；

（３）利用話題中命名實體以外的詞，計算兩個話題的相似度，定義為ｄ３。

話題相似度的綜合計算公式如公式（６）所示。

ｄ＝（ｄ１＞λ１）∧（ｄ２＞λ２）∧（ｄ３＞λ３） （６）

λ１，λ２，λ３是設定的閾值，只有公式（６）中的三個特征都滿足閾值要求時，即ｄ＝１，才認為兩個話題描述的為同一話題；如果ｄ＝０，就認為兩個話題不是相同話題。第三部分的實驗證明，本文的話題追蹤模型能夠有效地區分相似與相同的事件，正確地追蹤互聯網上已經出現的話題。

１．３分析層

在分析層中，系統根據話題的上榜天數、報道數目等信息計算話題的熱度，話題的熱度計算公式如（７）所示。

公式中，參數ｔ代表時間單元的總數，ｎｉ代表時間單元ｉ內新聞報道的總數，ｈｉ代表時間單元ｉ內話題新聞報道的數目，λ是調整因子，ｔｉ代表話題出現的時間單元的數目。在此基礎上，系統可以根據話題熱度指數、新聞報道數量的變化預測話題下一步的發展趨勢。

１．４用戶層

在用戶層中，管理員可以管理自動生成的話題，比如更正話題的摘要、編輯話題的其他信息，增加編輯選擇等。普通用戶可以通過可視化界面查閱系統檢測和追蹤到的熱點話題。

２實驗分析

本文采用騰訊新聞頻道報道的從２０１１－０４－０１至２０１１－０４－１０的８ ４７８個新聞文本作為實驗數據。

為了評估系統話題檢測模型的效果，本文采用人工識別的話題作為參考標準，采用正確率（正確識別的話題／識別到的所有話題）和錯誤關聯率（被錯誤分類的文檔／總文檔數）來評估文中的系統，得到話題檢測的正確率為８５．３％，錯誤關聯率為５．５２％。因此認為該系統達到了實際應用的水平。

為了評估基于多重特征的話題追蹤模型（記為Ｍ２）的效果，本文選擇只基于話題中所有詞這一單一特征的話題追蹤模型（記為Ｍ１）作為比較對象，用正確率、召回率以及Ｆ值來評價文中的模型。每兩天對話題追蹤的結果做一次統計，所得曲線圖如圖３所示，表１是從２０１１－０４－０１到２０１１－０４－１０對話題追蹤進行統計得到的結果。圖４則是由文中設計系統檢測和追蹤到的兩個熱點話題。

開展研究的目的是為了幫助用戶更加快速有效地從互聯網中獲取感興趣的信息，而用戶往往只關心幾個熱點的

話題，所以相對于系統的召回率，用戶更加關心系統的正確率。從圖３中，可以看到從２０１１－０４－０１到２０１１－０４－１０，每次話題追蹤的正確率與Ｆ值均有不同程度的提高，而且通過統計這１０天的話題追蹤結果（如表１所示），可以看到話題追蹤在召回率基本不變的情況下，正確率提高了９．７８％，Ｆ值也有顯著的提高，這得益于文中系統正確地區分了相似的話題與相同的話題。實驗結果證明此系統可以有效地追蹤到互聯網上出現的話題，滿足了實際應用的要求。

３結束語

本文設計并實現了一個面向互聯網新聞的話題檢測與追蹤系統，該系統能夠適應互聯網上的新聞事件冗余性高、數據量大、易漂移、持續時間長的特點，在系統中選擇了ＢＩＲＣＨ聚類算法用于話題檢測，并提出了一個基于多重特征的話題追蹤模型。實驗結果表明系統達到了實用的程度，能夠有效地檢測和追蹤到互聯網上出現的話題，從而幫助用戶更加快速有效地獲得感興趣的信息。

參考文獻：

[１] 洪宇，張宇，劉挺，等． 話題檢測與追蹤的評測及研究綜述[Ｊ]．中文信息學報，２００７，１１（６）：７１－８７．

[２] ＫＵＭＡＲＡＮ Ｇ，ＡＬＬＡＮ Ｊ． Ｔｅｘｔ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｎｄ ｎａｍｅｄ ｅｎｔｉｔ－ ｉｅｓ ｆｏｒ ｎｅｗ ｅｖｅｎｔ ｄｅｔｅｃｔｉｏｎ[Ｃ]／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＳＩＧＩＲ Ｃｏｎ－ ｆｅｒｅｎｃｅ ｏｎ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ． Ｓｈｅｆｆｉｅｌｄ， Ｓｏｕｔｈ Ｙｏｒｋｓｈｉｒｅ： ＡＣＭ， ２００４：２９７－３０４．

[３] Ｒｏｎ ＰＡＰＫＡ． Ｏｎ－ｌｉｎｅ Ｎｅｗ Ｅｖｅｎｔ Ｄｅｔｅｃｔｉｏｎ， Ｃｌｕｓｔｅｒｉｎｇ ａｎｄ Ｔ－ ｒａｃｋｉｎｇ [Ｄ]． Ａｍｈｅｒｓｔ： Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ＵＭＡ－ ＳＳ， １９９９．

[４] ＡＬＬＡＮ Ｊ，ＬＡＶＲＥＮＫＯ Ｖ，ＦＲＥＹ Ｄ，ｅｔ ａｌ． ＵＭａｓｓ ａｔ ＴＤＴ ２０－ ００[Ｃ]／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｔｏｐｉｃ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ Ｗｏｒｋｓｈｏｐ． ＵＳＡ： Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｎｄａｒ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２０００：１０９－ １１５．

[５] ＹＡＮＧ Ｙ， ＰＩＥＲＣＥ Ｔ，ＣＡＲＢＯＮＥＬＬ Ｊ． Ａ ｓｔｕｄｙ ｏｎ Ｒｅｔｒｏｓｐｅｃ－ ｔｉｖｅ ａｎｄ Ｏｎ－Ｌｉｎｅ Ｅｖｅｎｔ ｄｅｔｅｃｔｉｏｎ[Ｃ]／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２１ｓｔ ａｎｎｕａｌ ｉｎｔｅｒｎａｔｉｏｎａｌ ＡＣＭ ＳＩＧＩＲ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｅｓｅａｒｃｈ ａｎｄｄｅｖｅｌｏｐｍｅｎｔ ｉｎ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ． ＣＭＵ，ＵＳＡ：ＡＣＭ，１９９８：２８－ ３６．

[６] 賈自艷，何海，張俊海，等． 一種基于動態進化模型的事件探測 和追蹤算法[Ｊ]． 計算機研究與發展，２００４，４１（７）：１２７３－１２８０．

[７] 駱衛華，劉群，程學旗． 話題檢測與跟蹤技術的發展與研究[Ｃ]／／ 全國計算語言學聯合學術會議（ＪＳＣＬ－２００３）論文集． 北京：清 華大學出版社，２００３：５６０－５６６．

[８] 宋丹，衛東，陳英． 基于改進向量空間模型的話題識別與追蹤 [Ｊ]． 計算機技術與發展，２００６，９（１６）：６２－６７．

[９] ＭＥＹＥＲ ｚｕ ＥＩＳＳＥＮ Ｓ，ＳＴＥＩＮ Ｂ． Ａｎａｌｙｓｉｓ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏ－ ｒｉｔｈｍｓ ｆｏｒ ｗｅｂ－ｂａｓｅｄ ｓｅａｒｃｈ [Ｊ]． Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，２００２， ２５６９：１６８－１７８．

[１０] ＺＨＡＮＧ Ｔｉａｎ， Ｒａｇｈｕ Ｒａｍａｋｒｉｈｎａｎ ａｎｄ Ｍｉｒｏｎ Ｌｉｖｎｙ． ＢＩＲＣＨ：Ａ Ｎｅｗ Ｄａｔａ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ[Ｊ]． Ｄ－ａｔａ Ｍｉｎｉｎｇ ａｎｄ ｋｎｏｗｌｅｄｇｅ ｄｉｓｃｏｖｅｒｙ， １９９７，１（２）：１４１－１８２．