一種改進的回溯事件檢測算法

摘要：重點研究事件檢測模型中層次聚類算法的改進，提出利用在關鍵詞抽取基礎上利用新聞的各種要素信息計算新聞之間相似度的方式，搭建了一個在線新聞檢索系統，在其上利用新華社的新聞語料進行實驗。實驗結果表明改進方法的效果明顯，性能較之未使用前有顯著的提升。

關鍵詞：事件檢測； 聚類； 關鍵詞抽取

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2008)05-1333-04

近年來隨著網絡的普及，在網上瀏覽新聞已成為人們獲得最新信息的最佳媒介之一。目前各大門戶網站及主要的搜索引擎公司都提供了在線新聞閱讀服務。Google和百度等網站還支持基本的新聞分類（如國內、國外、政治、體育等）瀏覽功能，用戶可以通過這些服務瀏覽當日或者過去所發生的新聞。但是，由于新聞報道的更新頻繁，其龐大的數據量使得用戶常常有信息過量的感覺，很難快速準確地檢索到高質量的新聞信息。除了簡單的分類瀏覽以外，目前仍然沒有進一步輔助用戶閱讀相對粒度更細的新聞事件的工具。新聞事件由于有多人同時撰述的特性，并沒有一個公正客觀的角度來描述特定的事件。而且，新聞記者采寫同一事件的立場差異很大，切入角度也有所不同，再加上專業素質等原因，其所撰寫的稿件內容可能與實際情況有所出入。這樣，讀者想要客觀了解某一新聞事件，就必須多方閱讀和比較，花費在新聞瀏覽與搜尋上的時間十分可觀。

新聞事件除必須掌握時效性以外，熱點事件更需深入挖掘以及跟蹤報道。此外由于篇幅所限，對同一事件的后續報道經常需要參考和引述之前的文章。一般來說，讀者多根據現存報道加之回憶勾勒出事件的梗概，再在計算機中檢索以獲取歷史報道。傳統的檢索方式需要用戶對自己的查詢需求有相當的理解。然而，如果用戶對查詢的需求比較模糊，如新聞編輯想知道過去一年國內農業領域都有哪些熱點事件等，類似上述這樣的需求，用戶很難精確定義查詢請求，僅僅依靠關鍵字檢索無法滿足要求。如果能根據新聞事件將某一主題的新聞文檔進行匯整，對于提高新聞資料的利用價值和幫助新聞工作者改進效率，應有相當的助益。

基于以上的理由，在分析了新聞內容的特點后，本文采用多維向量空間模型來表示新聞文檔。在計算新聞之間相似度時綜合考慮時間、類別和新聞具體內容等信息，并且利用關鍵字抽取對新聞文檔進行預處理，簡化了向量的維度。本文還借鑒層次聚類的思想實現對新聞事件的檢測，使得新聞事件的粒度劃分更加靈活和準確。

1相關研究

1．1關鍵詞抽取

在信息檢索中，對于文件內容首先需要借由分詞技術來分析文件，從而篩選出能代表該文件的特征詞。本文所探討的新聞文件是由中文描述。由于中文自身的特點，它不像英文那樣在詞與詞之間有空格間隔，而且最近的研究表明，由新詞導致的分詞錯誤占到60%[1]，加之中文字詞的多樣性，這些都給中文分詞增加了相當的困難。對于新聞文件來說，新詞的作用更是不可忽視。中文分詞的方法可歸納為三種，即基于詞典、基于統計和結合前兩種方法的混合分詞法[2]。

經過分詞處理后還不足以被選做代表文件的關鍵詞。要選出這樣的字詞，還需計算該詞在文件中的權重。詞權重的設定是借由計算該字詞在單一文件的重要性及在整個文件集合中的重要性而來的。目前最常使用的詞權重計算方式為TFIDF（term frequency inverse document frequency)。

1．2新聞事件檢測與追蹤

這項研究開始于1998年由美國國防部高等研究計劃局（DARPA）所主導的新聞主題探測與追蹤計劃(topic detection and tracking，TDT)。該計劃的目的主要是希望從新聞廣播的數據流中找出并追蹤新的事件。新聞事件檢測與追蹤為其中的一個子任務。

事件定義為在一個確定時間、確定地點發生的事情[3]；主題則被定義為一個種子事件以及所有與其直接相關的事件與活動[4]。在本文的工作中，事件都表現為新聞文檔的集合，主題則表現為查詢詞。例如，在一個時間段內，報道禽流感在某地發生的新聞文檔構成了一個新聞事件，而這些事件又是屬于查詢農業這個主題所得到的結果集合。

回溯事件檢測(RED)定義為在歷史新聞庫中發現未經定義的事件[5]。雖然RED相關的研究已經進行了多年，但它仍然有很多問題尚待解決。這方面最早的工作是由Yang等人提出的，他們提出了凝聚聚類算法(GAC)來解決RED問題。此后，研究人員更多地關注與RED類似的新事件檢測（NED）問題。最近，LI Zhi－wei等人[6]利用新聞的時間分布和內容信息定義了一個概率模型來描述新聞事件，并利用此模型估計事件的個數。本文提出的算法參考了Yang的思想，并在GAC的基礎上提出了若干改進。

2系統框架

基于新華社的語料設計并實現了基于事件的新聞檢索系統，其目的是為用戶提供更加靈活的檢索方式，以及將檢索結果按照所描述的新聞事件有效地組織起來，從而增加新聞文檔的利用率。

本文中所述系統討論的主要數據是新聞語料。在設計算法時考慮到新聞語料的自身特點，系統的性能會得到改善。新聞稿件應當包括作者、新聞來源、報道時間等信息。國內外較大的通訊社其新聞稿件又有自身的特點。下面將詳細介紹新聞稿件的新華社預處理、相似度計算以及事件檢測算法，而其中很重要的一步，即關鍵詞抽取因篇幅關系將另作介紹。系統流程如圖1所示；查詢界面如圖2所示。

2．1預處理及新聞描述

由于系統要處理的新聞數據是XML文檔，其內容片段如下：

〈?xml version=\"1．0\" encoding=\"UTF-8\"?〉

〈XinhuaML〉

〈Package〉

〈TransmissionId〉20050420xjdfw5505〈/TransmissionId〉

〈DateTime〉20050420T013057Z〈/DateTime〉

……

〈Item〉

……

〈Component〉

〈Role NormalName=\"Main\"/〉

〈Lines〉

〈HeadLine〉（服務·IT）國產高端手機集體\"跳水\"〈/HeadLine〉

〈KeywordLine Eid=\"GJ\"〉經濟〈/KeywordLine〉

〈/Lines〉

……

〈ContentItem〉

〈MediaType NormalName=\"Text\"/〉

〈Format NormalName=\"TEXT\"/〉

〈Characteristics〉

〈Property NormalName=\"WordCount\" HowPresent=\"字數\" Value=\"501\"/〉

〈/Characteristics〉

〈Content〉

〈![CDATA[新華社北京4月20日專電（記者 令偉家）五一“黃金周”的“前哨站”已拉開了序幕：從本周開始，聯想、波導、海爾、夏新、康佳等國產手機品牌中的“高端產品”——以百萬像素拍照手機、智能商務手機、6．5萬色低價彩屏手機為代表的主流手機產品價格開始全線下挫。

記者在北京蘇寧朝陽路店看到，許多國產“高端”手機的售價已跌破千元：一款原價1288元的6．5萬色彩屏、30萬像素攝像頭的聯想手機的售價為998元；而一款30萬像素的波導彩屏手機由原來的1258元降至1058元；一款東信6．5萬色彩屏折疊手機僅售655元……

據業內人士介紹，今年手機市場最主要的特點是產品個性化的細分，上半年主流產品將以6．5萬色雙屏30萬攝像頭手機為主，下半年的“領航者”可能是彩屏帶攝像頭的mp3手機。目前國產手機廠商在這類產品上的技術難關已攻破，現在關鍵是讓產品盡快與消費者見面。

處于年中的五一“黃金周”，一直是手機銷售集中爆發的時段，也是手機銷售上下半年的分水嶺，因此成了眾多廠商十分看重的黃金商機。國美、蘇寧、大中等許多家電連鎖超市都紛紛聯手國產手機廠家，調低多款手機價格，以期能在這次與“洋品牌”的手機大戰中收復地盤。（完）]]〉〈/Content〉

〈/ContentItem〉

〈/Component〉

〈/Item〉

〈/XinhuaML〉

數據預處理包含兩個過程：利用XML解析器將新聞文檔中元數據提取出來，包括新聞報道的撰寫時間、作者、新聞分類、標題和新聞內容;利用分詞技術、去除停用詞等字詞處理技術將標題和新聞內容表示成一系列詞構成的向量。

其中：w(t，d)為詞 t 在文本d中的權重；tf(t，d)為詞t在文本d中的詞頻；N 為訓練文本的總數，此處由于系統使用新華社的新聞預料作測試數據，N為測試數據的新聞條數20 000；nt為訓練文本集中出現t的文本數；分母為歸一化因子。

由于新聞報道的篇幅限制，向量空間的維度并不會很高，經過統計，一般在200個詞左右。算法的復雜度并不會隨向量空間的規模呈現指數級的增長，而且后續工作還要對已經得到的結果作進一步處理。因此本文并未考慮使用傳統的方法來進行特征選擇，而是使用后面將會提到的關鍵詞抽取技術將特征詞的維度進一步降低。這樣，經過以上處理，每個新聞可以描述為由兩個向量構成的模型：

2．2關鍵詞抽取

基于上述工作，使用中國科學院計算所的ICTCLAS[7]并利用前面已經得到的結果dcontent和dtitle抽取出一串候選的關鍵詞。候選的關鍵詞是通過評價函數來評價的，分數越高越可能是關鍵詞。這個評價函數是在TF－IDF的基礎上增加若干機制來設計的，包括有單詞的各種特征(長度、位置、詞頻等)。此外，本文還應用了新的新詞發現機制。由于篇幅所限，這里不再作詳述。

3事件檢測算法

3．1新聞相似度計算

這一部分的算法應用在如圖1系統中事件檢測的部分。由于預處理后從新聞文檔中可以得到時間、新聞分類和內容等信息，在計算新聞間的相似度時對這三個部分分別進行計算，然后再通過加權合并得到統一的新聞相似度。此外，相似度也可以在檢索時根據需要靈活地按用戶定制的方式計算。

對于新聞分類，按其在分類樹中的距離進行計算。需要說明的是，這里的新聞分類指的是新華社的新聞數據中知識屬性分類法對應的類別。其類別如表1所示。

3．2聚類算法

這一部分的算法對應在圖2的聚類模塊中。算法借鑒了層次聚類的思想來實現事件的檢測。該算法可以動態調整聚類結果的粒度；缺點是其算法執行性能受到數據集的影響。本文對此應用了QuadTree[7]對算法的性能方面作了優化。

說明：在操作相似度矩陣時為了避免重復計算，使用了QuadTree算法進行優化，這里不作更詳細的介紹；通過大量的實驗表明，閾值σ設為0．11可以有效地將結果控制在10~15類，且對比實驗的結果最好。

4實驗結果

本文從新華社的新聞庫中選取了2005年4月~2006年1月的27 072篇新聞文檔，并利用XML解析器從中

抽取元數據信息作為實驗數據。由于實驗數據是中文數據且目前沒有相關成熟的系統作比較，本文所做的工作都是在前面提到的檢索系統中進行測試。

4．1實驗方法及評價標準

實驗的方式是首先選擇幾個有代表性的查詢詞，在檢索系統中對查詢結果進行聚類，由領域專家按事件進行分類。選擇的查詢詞為“農業”“住房”，分別對檢索結果進行分類；然后，將結果與僅使用內容和標題的特征詞向量進行聚類的事件檢測算法和應用關鍵詞抽取后的事件檢測算法進行比較。

本文采用應用廣泛的F－measure算法來評價事件檢測的結果。在已知文檔分類的前提下，先計算查全率和查準率：

表3為不使用關鍵詞抽取而僅在預處理后的內容和標題的特征向量基礎上應用本文的事件檢測算法和采用關鍵詞抽取后并應用本文中算法對查詢結果進行聚類得到的結果對比。各符號的定義如下：ei為事件i的文檔總數；nj為聚類簇j的文檔總數；max(nij)為事件i達到最大F－measure值時聚類簇j中包含事件i的文檔個數；max(F(i， j))為事件i和不同聚類簇j的F－measure值中最大的值。

從F－measure的結果來看，對于查詢農業相關的新聞，應用了本文所提出的事件檢測算法后的結果與未使用它的方法相比較，F－measure提高了40%。圖3、4分別是查詢農業和住房時的詳細結果對比圖。從F－measure的結果來看，對于查詢住房來說算法提高了16．7%；從查準率和查全率的結果來看，對于查詢農業和查詢住房這兩種方法分別提高了43．3%與17．7%，20．9%與42．2%；查準率平均提高了32．1%，查全率平均提高了30．1%。

從結果中可以看到，使用關鍵詞抽取和層次聚類后對于聚類效果起到了明顯的增強作用。通過分析結果中各聚類簇的新聞文檔，可以將這個增強作用總結成以下幾點：

a）關鍵詞抽取使得描述新聞的向量空間維度更小，特征詞更具代表性，過濾了許多與新聞關系不密切的詞。b）充分利用了各個新聞要素進行相似度計算，使得結果更為精確。

c）利用層次聚類方法來控制結果粒度。

5結束語

本文首先從信息檢索的角度給出了新聞事件檢測的概念模型，描述了構成系統的各部分所涉及到的相關技術，并重點闡述了基于關鍵詞抽取和新聞相似度計算的層次聚類算法。通過實驗表明，采用該方法可以增強用戶體驗和對資源更為高效的管理。本文所述的事件檢測算法中，算法的核心部分是通過計算新聞相似度和利用層次聚類來完成的。在下一步的工作中，筆者將考慮事件的要素抽取，包括時間、人物、地點、事件描述，形成帶語義的結構化信息，并使用數據挖掘的方法挖掘新的知識。同時，將考慮利用機器學習方法挖掘事件之間的聯系，并利用模板生成更為詳細的事件路徑圖。

參考文獻：

[1]SPROAT R， EMERSON T. The first international Chinese word segmentation bakeoff[C]//Proc of the 1st SIGHAN Workshop Attached with the ACL2003. Sapporo:[s.n]， 2003:133－143.

[2]張春霞，郝天永.漢語自動分詞的研究現狀與困難[J].系統仿真學報，2005，17(1):139－140.

[3]YANG Yi－ming， CARBONELL J G， BROWN R， et al. Learning approaches for detecting and tracking news events[J]. IEEE Intelligent Systems: Special Issue on Applications of Intelligent Information Retrieval， 1999，14(4):32-43.

[4]ALLAN J. Topic detection and tracking: event－based information organization[M]. Norwell: Kluwer Academic Publishers， 2002:17-31.

[5]YANG Yi－ming， PIERCE T， CARBONELL J G. A study on retrospective and on－line event detection[C]//Proc of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press， 1998:28-36.

[6]LI Zhi－wei， WANG Bin， LI Ming－jing， et al. A probabilistic model for retrospective news event detection[C]//Proc of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press， 2005:106－113.

[7]張華平，劉群.ICTCLAS[EB/OL].http://www.nlp.org.cn/project/project.php?proj_id=6.

[8]EPPSTEIN D. Fast hierarchical clustering and other applications of dynamic closest pairs[C]//Proc of the 9th Symposium Discrete Algorithms. San Francisco: ACM and SIAM， 1998:619-628.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”