ＬＳ－ＳＶＭ：一種有效的新聞主題追蹤方法
2008-12-31 00:00:00潘淵李弼程張先飛
計算機應用研究 2008年9期
摘 要：新聞主題追蹤是對主體所感興趣的新聞主題的發展趨勢進行動態追蹤，其優勢在于對所感興趣的主題基于文本模型及理解的動態追蹤，因此更多地涉及文本表示與語義理解。LSSVM首先將文本利用LSI（隱含語義分析）進行分析，完成對文本基于語義的特征降維及文本表示；然后將隱含語義文本表示的結果輸出給SVM進行主題追蹤，從而實現從語義層次上的新聞主題追蹤。實驗結果表明，與傳統的主題追蹤相比較，該方法能夠有效提高主題追蹤的性能，減少追蹤的錯報率和漏報率。
關鍵詞：隱含語義分析；支持向量機；主題追蹤；奇異值分解；隱含語義
中圖分類號：TP391 文獻標志碼：A
文章編號：1001-3695(2008)09-2661-03
LSSVM:effective algorithm of news topic tracking
PAN Yuan，LI Bicheng，ZHANG Xianfei
（ Institute of Information Engineering， PLA Information Engineering University， Zhengzhou 450002， China）
Abstract:Topic tracking is to track news trend which someone is interested in it.Its advantages lie in dynamic tracking based on text model and understanding， so it involves in more text express and semantic understanding. LSSVM first analyzed text using LSI(latent semantic indexing)， which achieved semanticbased character reduction and text express， then combined SVM to complete semanticbased topic tracking. The result of experiment shows， compared to conventional methods， LSSVM can improve performance of topic tracking effectively and reduce fault and fail rate of topic tracking.
Key words:LSI; SVM; topic tracking; SVD; latent semantics
隨著互聯網的出現和普及，為人們提供的信息急劇膨脹，而且與一個主題相關的信息往往孤立地分散在不同的時間段和不同的地方，因此人們很難快捷地獲取自己感興趣的信息。主題檢測與追蹤 （topic detection and tracking，TDT）技術正是為了改變這一狀況而產生的[1]，它是一種主要研究如何檢測新發生的事件并追蹤事件后續動態發展的信息智能獲取技術。
主題追蹤是TDT的一方面，是最近幾年信息檢索中一個新的研究方向，也是繼關鍵詞檢索之后的一種非常實用的信息檢索技術。不同于傳統的信息檢索、信息抽取、文本分類和數據挖掘等技術，主題追蹤是對特定新聞流進行基于主題內容的理解，其目標是在對新聞進行理解的基礎上建立新聞理解系統，從而實現主題追蹤。
主題追蹤的實質是一種有指導的學習，利用非常少的正例數據和大量的反例數據來設計追蹤器，利用訓練好的追蹤器對新聞流進行處理，以此來完成對感興趣主題的追蹤。主題追蹤的方法很多，但基本上都是將文本中的詞看做獨立不相關的，僅僅是利用詞的頻度信息建立相應的模型來追蹤主題，并沒有從人理解的角度去作深入的語義分析。人類思維對一篇文本的理解是從語義的層次上對文本理解的，而對主題的追蹤分析就應該讓機器接近人的理解，從語義的角度出發來追蹤主題。
LSI[2，3]（latent semantic indexing，隱含語義分析）能夠深入分析文檔中的詞匯同現[4]，克服文檔詞語多義性和同義性帶來的困擾。LSI的核心是奇異值分解[5]（SVD），通過SVD不僅更加凸現詞和文檔之間隱含的語義結構，而且使得文檔向量空間大大縮減，簡化了計算的復雜性。本文的貢獻在于：a)將文本利用LSI模型進行分析，采用SVD對中文分詞后的多維特征進行有效降維，從而完成LSI的文本表示；將SVM[6]應用于主題追蹤中，將LSI文本表示結果輸出給SVM，從而避免向量空間模型的不足之處，完成新聞主題的追蹤。
1 LSI模型
1.1 LSI
LSI是基于這樣一種斷言，即文檔庫中存在隱含的關于詞使用的語義結構，這種語義由于部分被文檔中詞的語義和形式上的多樣性所掩蓋而不明顯。LSI通過對原文檔庫的詞—文檔矩陣的SVD計算和取k秩近似矩陣，消減了詞與文檔之間的語義模糊度，從而在語義理解的角度更有利于對主題的追蹤。利用LSI可以分析文檔中詞條的同現。文檔中兩個或者更多詞條的同現不是偶然事件，如表1所示。
表1 詞條同現的實例
文檔詞條1詞條2詞條3詞條4詞條5
文檔1宇航員宇宙月亮
文檔2宇航員月亮
文檔3宇宙
從表1中可以看出，文檔1對于文檔2來說具有更好的相似性，因為文檔1中包含了文檔2中所有的詞條。但是文檔3 與文檔2也具有很好的相似性，雖然它與文檔2 沒有相同的詞條，但它表達的是一種語義相關的信息。LSI就是一種探查這種內在語義聯系的方法，它將同現詞條映射到同一維空間，非同現詞條映射到不同空間。所以，即使文檔之間沒有共同的詞條，它們的余弦相似度仍然可能很高。
從空間降維角度講，LSI方法具備了某種最優特性，它把原對象投影到方差最大軸上，即數據在所選取的映射軸上具備最大的可分性。LSI空間與原來的空間相比，維數小得多，這是因為文檔中的很多詞條被投影到了同一維上，文檔向量被從高維空間映射到較低維的空間。因此，LSI是一種有效的降維方法。
1.2 詞—文檔表示
在LSI模型中，一個文檔庫可以表示為一個m×n的詞—文檔矩陣A。這里，n表示文檔庫中的文檔數；m表示文檔庫中包含的所有不同詞的個數。即每一個詞對應于矩陣A的一行；每一個文檔則對應于矩陣的一列。A表示為
其中:TF(Wi，Doc)為單詞Wi在文檔Doc中的出現頻度;D為總文檔數，DF(Wi)為單詞Wi在其中出現至少一次的文檔的數目。
降維因子k值的選取非常關鍵，k＜rank(A)且k< LSI與SVM相結合形成LSSVM，將LSI從基于語義的理解去表示文本向量，然后將向量輸出給SVM以完成主題的追蹤。其算法流程具體表示如下： a）讀入文本流； b）對中文文本進行中文分詞處理； c）完成對分詞之后的文本特征提取； d）將第c）步所提取的特征按照式（1）完成詞—文檔的表示，其中的權值計算方法采用式（2）計算； e）將詞—文檔矩陣按照式（3）進行降維，其中參數的選取依據式（5）進行； f）根據式（4）將其所完成的文檔向量輸出給SVM； g）調整SVM中的各參數，選取相應的核函數完成追蹤器的訓練； h）將測試文檔同樣投影到LSI空間，并將其文檔向量輸入給SVM追蹤器，完成對主題的追蹤。 3 基于LSSVM的主題追蹤 將LSSVM方法用于新聞主題追蹤，其系統框圖如圖1所示。 LSSVM用于新聞主題追蹤，具體步驟如下： a）將訓練文檔表示為LSI空間中的文檔向量。 （a）將n篇文檔進行中文分詞，將所有詞掃描到一個列表中形成原始詞表；然后對原始詞表中的所有詞去除停用詞，采用信息增益法（IG）計算每個詞的評估值。 （b）根據評估值抽取前m個較大值的詞形成最優詞表。將n篇文檔分別與最優詞表匹配生成文檔向量，計算最優詞表中的每個詞的TF×IDF值來表示權重，作為矩陣A的每個元素。 （c）利用含有m個詞的最優詞表和與最優詞表匹配生成的n個文檔向量形成詞—文檔矩陣A。 （d）對A進行SVD分解并選取k值作截斷處理生成文檔—文檔關聯矩陣Dk。Dk中的每一行表示一個訓練文檔向量。 b)將利用LSI所形成的文檔向量輸入給SVM，利用訓練文檔對SVM追蹤器進行訓練。其中SVM的核函數選用徑向基函數（RBF），公式如下： K(x，xi)=exp{-|x-xi|2/σ2}(6) c)將測試文檔投影到LSI空間。測試文檔只有投影到LSI空間才能與LSI模型中的訓練文檔向量進行匹配。把關于一個主題的若干篇文檔進行SVD分解形成LSI模型，將測試文檔按照式（7）作為新增文檔映射到LSI 空間中。 由式(7)可知，假設有一測試文檔向量d，投影到Ak空間后，等效為Dk中一行向量： d)將映射到LSI空間的測試文檔向量作為輸入參數輸入到SVM追蹤器中，以此完成對新聞主題的追蹤。 4 實驗結果及性能分析 4.1 實驗數據及測試方法 本文的實驗數據源自互聯網（新浪www.sina.com.cn和搜狐www.sohu.com），共包括訓練及測試數據2 927篇新聞網頁，如表2所示。實驗數據共包括25個新聞主題，主要新聞類型為國際和國內新聞，其中訓練數據的所屬新聞主題全部由手工標注。 表2 實驗數據的事件集合 主題名稱新聞個數主題名稱新聞個數 埃及發生三起爆炸100印尼爪哇島地震312 埃塞俄比亞卷入索馬里內戰126美軍虐囚32 俄羅斯154客機失事138伊朗客機失事118 格魯吉亞間諜風波176亞美尼亞客機失事142 米洛舍維奇死亡97無極破壞環境60 車臣匪首巴薩耶夫被擊斃37泰國軍事政變132 莫斯科市場發生爆炸34伊朗核問題144 美國客機失事125斐濟發生政變93 所羅門群島騷亂187匈牙利發生騷亂31 美國敘利亞大使館被襲擊55以色列大選122 臺風派安比63網絡文明129 陳水扁廢統207新浪人事變動74 韓日獨島之爭163 實驗選取多個不同主題進行測試比較，現以“亞美尼亞客機失事”這個主題為例詳細說明，所有對單個主題進行測試的結果都可以有效說明追蹤器的性能。實驗分別選取“亞美尼亞客機失事”這個主題中的1、2、4篇新聞報道作為正例（用于訓練一個話題的訓練樣本只有N=1，2，4個[8]），選取語料庫中的其余24個主題中的200篇新聞報道作為反例來構建追蹤器。測試數據為語料庫中除去用于追蹤訓練語料之外的其他所有新聞報道。為了使實驗結果有說服力，本文采用目前主題追蹤效果比較好的KNN追蹤法、SVM追蹤法同本文的LSSVM追蹤法進行對比， SVM與LSSVM中的關于SVM的參數選取相同。實驗中的網頁首先經過本課題組開發的htmltotxt進行網頁文本轉換，中文分詞采用中科院ICTCLAS 3.0完成，特征提取采用信息增益評估函數。 4.2 實驗結果評測標準 本文方法的實驗結果評測采用TDT在2004年的評測方法[7]。在TDT的評價標準中，除了采用與傳統的信息檢索和文本分類相類似的正確率P、召回率R、F1measure來評價結果之外，TDT還采用系統錯誤率來評價結果。這主要包括漏報率Pmiss和錯報率這些方法可表示為追蹤到的文檔：a(相關)/b(不相關)；未追蹤到的文檔：相關）/（不相關）。其中：追蹤到的文檔是指被系統正確劃分的屬于所追蹤主題的文檔，相關文檔是指由人工判斷與追蹤的主題相關的文檔。效率評價公式可表示為將召回率和正確率結合起來估計模型的質量，即 4.3 結果和性能分析 對所選主題進行追蹤的結果如表3所示。 表4數據中，當N取值一樣時，追蹤準確率最低的是KNN追蹤法，其次是SVM追蹤器，最優的是LSSVM追蹤器。這充分體現了LSI相比于其他文本表示模型上的優越性，采用LSI來表示文本可以有效提高追蹤器的性能。另外從錯報率、漏報率、召回率以及其他兩個參數上的比較都可以看出算法LSSVM在新聞主題追蹤上性能的優越性。 可以看出，實驗結果中存在著召回率較高、準確率較低的特點，這是由于LSI利用了詞匯的同現度，深入分析了詞匯之間的相關性，召回率就高。基于主題追蹤的特點，在訓練正例非常少的情況下，要求較高的召回率而準確率稍差一些是可以允許的。 從實驗結果的縱向比較可以看出，無論哪種方法都是隨著N的增大其追蹤的效果越來越好，究其原因主要在于訓練正例的增多，使所要追蹤的主題特征更鮮明，避免主題被大量的反例淹沒，從而能提高追蹤的性能。但是否隨著N的值無限增大，其追蹤效果可以逼近完美還沒有定論。本文實驗是參考文獻[8]所做，最多時取到測試正例數目與反例數目相當的情況下，其追蹤效果與N＝4時相近。這個問題的具體探究為本課題的下一步工作。 5 結束語 主題追蹤是一種能自動跟蹤主體所感興趣的某一新聞主題動態發展的新方法。本文將LSI文本表示方法與SVM相結合，提出了一種有效的主題追蹤方法——LSSVM。該方法有效挖掘了文檔的隱含語義信息，從語義的深度結合SVM完成對新聞主題的追蹤。從理論上分析，本方法相比于其他基于詞頻的主題追蹤方法而言，能夠從人理解的角度出發來完成主題追蹤；實驗結果也證實，從語義角度出發的LSSVM主題追蹤方法是一種非常實用、有效的新聞主題追蹤方法。 參考文獻： ［1］ ALLAN J.Introduction to topic detection and tracking[M]//Topic Detection and Tracking: Eventbased Information Organization.Norwell:Kluwer Academic Publishers，2002:116. [2]FIERRO R D，BERRY M W.Efficient computation of the Riemannian SVD in TLS problems in information retrieval[M]//Total Least Squares and ErrorsInVariables Modeling: Analysis， Algorithms， and Applications.Norwell:Kluwer Academic Publishers，2002:349-360. [3]范春法，李慶中，李偉，等.統計自然語言處理[M]. 北京: 電子工業出版社，2005. [4]HOFMANN T.Gaussian latent semantic models for collaborative filtering[C]//Proc of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York:ACM Press，2003:259-266. [5]鄭新立，徐云青，駱昌日.LSI模型在信息檢索中的應用[J]. 計算機技術與發展，2006，10(16):160162. [6]蘇新寧.信息檢索理論與技術[M].北京:科學技術文獻出版社，2004. [7]The 2004 Topic Detection and Tracking. Task definition and evaluation plan[EB/OL].(2004).http://www.nist.gov/speech/tests/tdt/tdt2002/evalpan/htm. [8]王會珍，朱靖波，季鐸，等.基于反饋學習自適應的中文話題追蹤[J].中文信息學報，2006，20(3):92-98
