基于事件關聯網絡的用戶興趣話題發現算法

摘 "要： 面對海量的網絡新聞信息，為了能更加準確與全面地從中發現用戶感興趣的話題，提出一種基于事件關聯網絡的用戶興趣話題發現算法。該算法建立了代表事件之間關聯關系的事件關聯網絡，基于該事件關聯網絡，采用鏈接分析技術度量用戶對不同新聞事件感興趣的程度，從而采用針對新聞特定語義架構的改進Single?pass聚類算法發現用戶感興趣的話題。此外，采用Bootstrapping算法，實現對相關興趣領域詞匯的語義擴展。實驗表明，該算法能夠更加準確而全面地獲取用戶感興趣的話題。

關鍵詞： 話題識別; 鏈接分析; 用戶興趣; Bootstrapping算法; 關聯網絡

中圖分類號： TN711?34; TP391 " " " " " "文獻標識碼： A " " " " " " " " " " " " "文章編號： 1004?373X（2015）06?0007?06

Algorithm to find topics that users are interested based on network associated with events

WU Jisiguleng， LIU Xiao?ying， YAN Chu?ping

（No.15 Research Institute， China Electronics Technology Group Corporation， Beijing 100083， China）

Abstract：Being faced of massive Internet news information， to improve the accuracy of detecting the topics that the users are interested， a topic detection algorithm based on the network associated with the events is proposed "for users’ interest. The algorithm established an event?related network representative of relevance relationship among news events. The link analysis technique is used to measure the degree of user interest in the news， so as to identify the topics that the users are interested by using an improved Single?pass clustering algorithm based on news specific semantic structure. In addition， Bootstrapping algorithm is adopted to achieve the related interest words’ semantic extensions. The experiment result shows that the algorithm can more accurately and comprehensively get the topics that the users are interested.

Keywords： topic recognition; link analysis; user interest; Bootstrapping algorithm; associated network

0 "引 "言

隨著互聯網的迅速發展，網絡信息量爆炸式增長，導致人們處理和使用這些龐大的信息變得越來越困難。面對網絡信息過載，如何快速準確地獲取人們感興趣的新聞話題，并對這些新聞話題進行有效地組織、處理和分析，是當前信息處理領域研究的一個重點，其研究成果具有重要的意義。

話題識別與跟蹤技術正是在這種情況下所產生。針對不同話題識別任務的特點，新聞話題識別的研究可分為熱點話題識別[1?3]、敏感話題識別[4?5]、領域話題識別[6]和用戶興趣話題識別[7]四個方面。關于用戶興趣話題識別方面的研究相對較少，Kurtz等人所提出的系統[7]，基于個人配置文件提取用戶興趣過濾新聞文本，從而采用改進的話題聚類算法獲取用戶感興趣的話題。該算法在基于新聞文本自身所攜信息進行過濾時，易遺漏某些同樣需關注的相關話題。為解決該類問題需充分考慮事件關系，關于事件關系識別，楊雪蓉等人提出了一種基于核心詞和實體推理的事件關系識別方法[8]。該方法明顯優于單基于事件語義的事件關系識別方法，但當面對大量的網絡熱點新聞事件時，該算法中事件線索集的構建有限，因為對部分事件無法構建虛擬相關事件集合。為了有效提高大規模互聯網數據中用戶興趣話題識別的準確率，避免對相關興趣新聞事件的遺漏，本文提出一種符合新聞特定語義結構的事件多維關聯關系計算方法識別事件關系，從而構建事件加權關聯網絡。基于該事件關聯網絡，采用連接分析技術綜合考慮各新聞事件之間的關聯關系，對新聞集按照用戶感興趣的程度進行排序，獲取用戶感興趣的新聞事件，進而通過改進的single ?pass聚類算法獲取用戶感興趣的話題。此外，針對用戶興趣的動態變化特性，本文只需用戶擇感興趣的興趣領域標簽即可。實驗表明，該算法能達到較高的準確率，使人們能對感興趣的話題具有全面而準確地認識。

1 "算法提出

本文提出的基于事件關聯網絡的用戶興趣話題發現算法中引入了新聞事件興趣度值的概念，表示用戶想要關注某新聞事件的程度。該算法可分為以下四個步驟：第一，基于自主可擴展的知識庫，對不同興趣領域詞匯進行擴展;第二，構建由新獲取到的新聞事件與用戶感興趣的歷史新聞事件組成的事件加權關聯網絡;第三，基于所構建的事件關聯網絡，采用鏈接分析技術，通過計算每個新聞事件的興趣度值獲取用戶感興趣的新聞集。最后，在所得用戶感興趣的新聞集上，基于新聞文本特有的語義框架，采用改進的聚類算法獲取用戶感興趣的話題。

1.1 "構建可擴展領域知識庫

通常用戶所能提供的興趣詞數量較為有限，為能更好地把握用戶興趣需求，本文通過采用Bootstrapping半監督機器學習算法[9]構建可自主擴展的知識庫，將少量不同興趣領域詞集擴展為能夠較全面代表用戶興趣需求的興趣詞集。關于知識庫的自主擴展，人工選取新聞語料中少量不同興趣領域的中心詞作為種子詞集，從大量的新聞語料庫中提取有效詞作為待標注詞集，自動地進行知識學習，從而實現知識庫中不同興趣領域詞匯的擴展。

共現關系與相似關系是建立可擴展知識庫的基礎，本文分別基于Wordnet與Google檢索計算詞之間的語義相似度值和共現關系值，將語義相似度值和共現關系值作為每輪新擴展興趣詞的二維置信度。基于Bootstrapping算法，逐步對新獲取的新聞詞匯進行標注，實現知識庫中不同興趣領域的有效詞、相似詞對和共現詞對的自主擴展。具體算法如下：

輸入：用戶提供的少量興趣詞集

輸出：基于知識庫擴展后的能較全面代表用戶興趣的興趣詞集

（1） 將用戶提供的少量興趣詞賦予興趣度值x，初始賦值為1，作為初始種子詞集W;

（2） 從領域知識庫中獲取實詞，作為待標注詞集U;

（3） 基于領域知識庫，計算U中每個詞與W中詞的語義相似度值Si和共現度值Gi，分別作為二維置信度;

（4） 將置信度較高的前n個詞，作為新增種子詞集N，擴展原始種子詞集為W+N;

（5） 對新增加的n個種子詞，基于置信度值和對應的原始興趣種子詞，計算其興趣度值x;

（6） 重復第（3）～（5）步，直至符合算法結束條件，獲取最終的種子詞集FW;

該方法中用戶只需選擇感興趣的興趣領域標簽即可，有效避免了用戶興趣的動態變化特性所帶來用戶興趣判斷不準確。隨著新輸入新聞語料的增多，知識庫擴展的效果將更加全面與準確。

1.2 "構建事件關聯網絡

大量的互聯網新聞數據中，每一篇新聞報道代表一個新聞事件。大量的事件之間存在著紛繁復雜的關聯關系。僅基于事件所攜主要信息計算事件的興趣度值，易忽略同樣需關注的相關事件。構建事件關聯網絡，綜合考慮事件間的關聯因素，有助于更加準確和全面地獲取用戶感興趣的話題。

事件關聯網絡中，每個節點代表一個新聞事件，將事件興趣度值作為節點的權重;每個邊代表兩個事件之間的相關聯程度，將事件在時間、人物（或機構）、地點和行為四個維度上的相關程度作為邊的四維權重。采用命名實體識別技術獲取新聞中表示地點、人物（或機構）和行為的詞，基于新聞的實時性，視新聞報道的時間為事件的近似時間，計算事件在時間、人物（或機構）、地點和行為四個維度上的相關程度，即關聯網絡中邊的四維權重，從而綜合考慮事件之間在以上四個維度的關聯程度。事件各維關聯度的計算公式如下：

（1） 事件時間關聯度計算

如果兩個事件發生的時間差值在一定的范圍內，則認為這兩個事件在時間上是關聯的。關聯的強度與發生時間的間隔有關。時間的間隔越短，關聯的強度越強。具體計算公式如式（1）所示：

[Reltime（T1，T2）=time（T1）-time（T2）maxTi，TjΔtime（Ti，Tj）] （1）

式中：[time（T1）]，[time（T2）]分別表示事件[T1]，[T2]的時間;[Ti]和[Tj]是任意相關事件。[Reltime（T1，T2）]的值在[0，1]。

（2） 事件人物（或機構）關聯度計算

如果兩個事件中涉及的人物（或機構）相同或具有較高的相似度或共現率，則認為這兩個事件在人物（或機構）上是關聯的，關聯的強度以相同人物（或機構）為最強。基于改進的詞集相似度計算公式，獲取事件的人物（或機構）關聯度值，具體計算公式如式（2）所示：

[Relobject（T1，T2）=object（T1）?object（T2）object（T1）?object（T2）] " "（2）

式中：[object（T1）]、[object（T2）]為事件中涉及的人名（或機構名稱）的集合，集合中的元素可以重復;[object（T1）?object（T2）]表示兩個事件中重復出現的人名（或機構名稱）和具有較高相似度或共現率的人名數量;[object（T1）?object（T2）]表示兩個事件中總共涉及的人名數量，[Relobject（T1，T2）]的值在[0，1]。

（3） 事件地點關聯度計算

基于改進的詞集相似度計算公式，獲取事件的地點關聯度值，具體計算公式如式（3）所示：

[Rellocate（T1，T2）=locate（T1）?locate（T2）locate（T1）?locate（T2）] " " （3）

式中：[locate（T1）]，[locate（T2）]為事件中涉及的地名集合，集合中的元素可以重復;[locate（T1）?locate（T2）]表示兩個話題中重復出現的地名和具有較高相似度或共現率的地名數量;[locate（T1）?locate（T2）]表示兩個事件中總共涉及的地名數量;[Rellocate（T1，T2）]的值在[0，1]。

（4） 事件行為關聯度計算

如果兩個事件中涉及的行為相同，或是相近的，則認為這兩個事件在行為上是關聯的。關聯的強度以相同行為為最強。事件的行為關聯度值通過度量新聞事件中除表示時間、地點、人物以外的特征詞間的語義相似度得到。具體計算公式如式（4）所示：

[Relact（A1，A2）=12（w∈A1（maxSim（w，A2）·IDF（w））w∈A1IDF（w）+ " " " " " " " " " " " " " "w∈A2（maxSim（w，A1）·IDF（w））w∈A2IDF（w））] （4）

式中：A1和A2是表示話題行為的特征詞集合， [maxSim（w，A）*IDF（w）]是詞w與特征詞集A中語義最相近的詞的語義相似性;[IDF（w）]反映了詞包含信息量的多少。英國國家語料庫（British National Corpus）被用來統計[IDF（w）]。

1.3 "計算事件興趣度值

基于事件關聯網絡計算用戶對某一新聞感興趣的程度，所采取的鏈接分析從兩個方面展開：一是考慮當前新獲取的事件間的關聯影響，如果某一事件與其他用戶感興趣的新聞事件關聯關系越緊密，則認為該事件的事件興趣度值越高;二是考慮用戶感興趣的相似的歷史新聞事件對當前事件的影響，認為相似的事件通常具有相近的事件興趣度。另外，在每次對新獲取的事件興趣度度量時，將興趣度較高的事件保留起來作為歷史新聞事件。

對新獲取的新聞事件，在事件關聯網絡中分別從時間、對象（人物或組織）、空間和行為這四個維度來分析事件的興趣度值。首先，對網絡中代表新獲取新聞事件的節點賦予表示其事件興趣度值的初始權重[SEvent（t）]，具體計算公式如式（5）所示：

[SEvent（t）=a1?Stime（t）+a2?Sobject（t）+ " " " " " " " "a3?Sspace（t）+a4?Sact（t）] "（5）

式中：[a1]，[a2]，[a3]，[a4]分別表示時間、人物（或機構）、地點和行為興趣度在事件興趣度計算所占權重;[Stime（t）]，[Sobject（t）]，[Sspace（t）]和[Sact（t）]分別表示通過與用戶擴展興趣詞集的匹配，新聞事件特征詞集中興趣度值最高的表示時間、人物（或機構）、地點和行為的詞的興趣度值。

然后，為分析事件之間的關聯影響，在建立的事件關聯網絡上，采用隨機游走模型，分析事件的興趣度。關聯網絡中所有事件的集合表示為T={t1，t2，…，tn}，ti是關聯圖中的事件。無向圖G=lt;v，ET，EO，ES，EAgt;是根據事件間的相關度建立的關聯圖，其中V是包含n個事件的節點的集合，等于T;ET、EO、ES、EA分別是新聞事件節點在時間、對象、空間、行為上的邊的集合，若兩節點間的相關度大于給定閾值，則有邊存在，它是v×v的一個子集。對新爬取到的新聞事件在多維度相關事件影響下的事件興趣度[SEvent（t）]的計算公式如式（6）所示：

式中：[a1]和[a5]，[a2]和[a6]，[a3]和[a7]，[a4]和[a8]分別表示在時間、空間、對象和行為上的權重，取值范圍為（0，1]，[i=18ai=1]，且[0lt;ailt;1];[Stime（t）]和[Stime（w）]，[Sobject（t）]和[Sobject（w）]，[Sspace（t）]和[Sspace（w）]，[Sact（t）]和[Sact（w）]分別是事件在時間、空間、對象（人物或組織）、行為這四個維度上的初始興趣度值。[Reltime（t，w）]，[Relobject（t，w）]，[Relspace（t，w）]，[Relact（t，w）]反映了事件在時間、對象（人物或組織）、空間、和行為這四個維度上的相關聯程度。

基于式（6）計算事件興趣度值，將事件興趣度值大于特定閾值的新聞事件，歸為用戶感興趣的新聞事件集，獲取用戶感興趣的事件集。

1.4 "用戶興趣話題識別

針對網絡熱點新聞話題中難以區分一個話題下的多個子話題現象，本文采用一種基于LDA（Latent Dirichlet Allocation）模型的改進的Single?Pass聚類算法對1.3節中所獲取的用戶感興趣的新聞進行聚類，從而獲取用戶興趣話題。應用LDA模型對新聞文檔進行建模[10]，使用Single?Pass聚類算法生成話題，并針對新聞文本特有的語義架構，在Single?Pass聚類算法中的文本相似性將同時利用向量相似性和命名實體相似性。

計算向量相似性，采用基于有效詞庫的方法，文本的向量維度一般能夠達到上萬維，消耗了大量的計算資源。故采用LDA模型，LDA不僅能發掘文本中隱含的主題信息，同時能夠將文本表示成主題分布的過程看作是將文本用低維度向量表示的過程，即LDA能夠很大程度上對高維文本向量進行降維處理。LDA模型參數中K代表將在文本集合中設定的K個主題，將每一個文本向這K個主題上去映射，轉換成一個K維的向量，向量的每一個維度對應一個主題。如此，原本基于有效詞庫用高維文本向量表示的文本即可用K維的低維文本向量進行表示。從而，易通過計算兩個K維向量的夾角獲取這兩個文本之間的向量相似度。然而，僅僅考慮向量相似度是不夠的，新聞數據集中包含有很多十分相似的話題，比如“中日關系系列話題”，“世界杯比賽系列話題”，“自然災害相關話題”等，這些話題從內容相似性上來說非常的相近，因此可以推斷出經過LDA主題模型表示后，這些文本之間的區別體現得仍然不是特別全面。故，引入命名實體相似度的計算，通過得到兩個文本的命名實體集合，基于新聞特有的語義框架[11]，分別基于1.2節中的式（1）～式（4）計算兩個新聞文本在時間、人名（或組織名）、地名和行為四個方面的相似度，實現對話體更加精準劃分聚類。

2 "實驗分析

2.1 "實驗數據

通過網絡爬蟲收集自Retuers網站 （http：//www.reuter s.com/）的英文數據集，作為實驗所用的英文數據集，包含2014年1月—2014年6月的18 000篇新聞，如表1所示，涵蓋了國際、經濟、政治、軍事、社會、科技等多個領域。

構建可供用戶選擇的興趣分類標簽集，分別有自然災害、醫療疾病、食品安全、事故、領土紛爭、恐怖主義、信息安全、能源、政治和腐敗等標簽。每個標簽下人為標注少量的領域中心詞作為初始種子詞。標注人員根據興趣選取不同標簽，如表2所示。每位標注人員分別在6組數據集上標注出其感興趣的話題，構建標準的測試數據集。

表1 測試數據集

表2 用戶所選興趣標簽

2.2 "評價標準

本實驗中使用準確率、召回率和F值對該算法進行評估。準確率表示一個被識別出的用戶感興趣的新聞話題是用戶感興趣的可能性。召回率表示識別出的用戶感興趣的新聞話題與用戶實際感興趣的話題的比率;F指標是為了同時考察召回率和準確率所提出，F指標把準確率和召回率統一到一個指標。

基于該算法在6組數據集上依次進行實驗時，將上一組數據中所得用戶感興趣的新聞事件作為下一組實驗所構建的事件關聯網絡中的歷史新聞事件。例如，在數據集3上進行實驗，構建事件關聯網絡時，將數據集1，2上所得用戶感興趣的新聞事件作為該關聯網絡中的歷史新聞事件。

2.3 "實驗結果分析

在已標注的6組測試數據集上，經過參數調試，取1.4節所提聚類算法中向量相似度閾值rv=0.375、命名實體相似度閾值rn=0.475和LDA模型中主題個數K=120時，可獲取最優話題聚類結果。同時，對所構建的事件關聯網絡，將節點間在時間、人物、地點和行為4個緯度上的關聯度閾值Rt，Ro，Rl和Ra分別設置為0.325，0.15，0.15和0.275可得最佳新聞事件過濾效果。

基于以上參數設定，為驗證該算法的有效性，采用用戶1提供的興趣標簽，分別在6組數據集上依次進行試驗。將加入事件關聯網絡后的用戶興趣話題發現算法與加入事件關聯網絡前的用戶興趣話題發現算法進行對比。加入事件關聯網絡前，基于式（5）計算每篇新聞興趣度值，并對每篇新聞的興趣度值做歸一化處理，設置興趣度閾值為0.5，大于該閾值的新聞歸為用戶感興趣的新聞。兩組實驗結果分別如表4所示。

表4 實驗結果

從以上實驗結果可知，僅基于文本自身所攜關鍵詞集的用戶興趣話題發現算法準確率并不是很高，并且隨著數據量的增加其準確率會明顯下降。從6組測試數據上的兩組實驗結果可知，引入事件關聯網絡后，用戶興趣話題識別的準確率，召回率和F值都有明顯提高;并且，隨著數據量的增加，基于事件關聯網絡的用戶興趣話題發現算法能夠維持在一個較高的準確率。通過對所識別出的用戶興趣話題內容分析，可知該算法能對相關興趣話題有更加全面的識別，與更加精準的劃分。表5為基于用戶1所選興趣標簽，在數據集5，6上所獲取的部分興趣話題的代表性特征詞集實例。

表5 特征詞集

為進一步驗證關聯網絡中時間、人物、地點和行為每個維度對事件關聯關系的影響，在6組測試數據集上分別將式（6）中，表示時間、空間、對象和行為上的權重[a1]和[a5]，[a2]和[a6]，[a3]和[a7]，[a4]和[a8]依次設為0，其他三維取均值，并與四個維度取均值時所獲實驗效果進行對比。實驗所得用戶興趣話題識別的準確率，召回率和F值如圖1～圖3所示，在充分考慮新聞事件在時間、人物、地點和行為上的關聯度時可達最優的實驗效果。

lt;E：＼王芳＼現代電子技術201506＼現代電子技術15年38卷第6期＼Image＼30T1.tifgt;

圖1 準確率對比

lt;E：＼王芳＼現代電子技術201506＼現代電子技術15年38卷第6期＼Image＼30T2.tifgt;

圖2 召回率對比

lt;E：＼王芳＼現代電子技術201506＼現代電子技術15年38卷第6期＼Image＼30T3.tifgt;

圖3 F值對比

實際上，某些需關注新聞事件本身所包含的興趣關鍵詞并不多，主要原因為該類事件可能是由某興趣話題所衍生出的新話題，或是與興趣話題有著較強相互影響關系的其他話題，這時僅基于文本自身所攜興趣關鍵詞信息，將無法準確判斷該類新聞事件。引入事件關聯網絡后，該類新聞事件因和某些具有較高興趣度值的事件有著較強的關聯關系，基于1.3節中的鏈接分析模型，計算新聞的興趣度值，獲取用戶感興趣的新聞事件集。從而基于改進的聚類算法獲得用戶興趣話題。綜上，該算法能夠有效地適用于大數據量情況下的用戶興趣話題的識別，且取得了較為理想的實驗結果。

3 "結 "語

針對用戶興趣話題識別中話題識別不全與誤差較大的問題，本文所提基于事件關聯網絡的用戶興趣話題發現算法中充分考慮了海量信息中新聞事件之間的復雜關聯關系，將其與基于新聞文本自身所攜用戶興趣信息的文本過濾算法有機結合，獲取用戶感興趣的新聞事件集，有助于識別出同樣需關注的相關感興趣的話題。并提出了一種基于LDA模型的改進的single?pass聚類算法最終獲取用戶感興趣的話題。實驗結果表明，針對網絡中的大量新聞數據，該算法只需用戶選擇感興趣的相關領域標簽，并通過引入基于新聞文本特有語義框架的事件關聯網絡，能夠較為準確而全面地獲取用戶感興趣的話題。

參考文獻

[1] 張玥，張宏莉.基于關聯性的熱點話題識別[J].智能計算機與應用，2014（3）：55?59.

[2] MA Hui?fang. Hot topic extraction using time window [C]// Proceedings of 2011 International Conference on Machine Learning and Cybernetics （ICMLC）. Guilin， China： [s.n.]， 2011： 56?60.

[3] YOU Bo， "LIU Ming， "LIU Bing?quan， et al. Detecting hot topics in technology news streams [C]// Proceedings of 2012 International Conference on Machine Learning and Cybernetics （ICMLC）. Xi’an， China： [s.n.]， 2012： 1968?1974.

[4] ZHAO Li?yong， ZHAO Chong?chong，PANG Jing?qin， et al. "Sensitive topic detection model based on collaboration of dynamic case knowledge base [C]// Proceedings of 20th IEEE International Workshops on Enabling Technologies： Infrastructure for Collaborative Enterprises （WETICE）. Paris： IEEE， 2011： 156?161.

[5] ZHAO Li?yong， LI Ai?min. A novel system for sensitive topic detection and alert assessment [C]// Proceedings of "2011Eighth International Conference on Fuzzy Systems and Knowledge Discovery （FSKD）. Shanghai， China： [s.n.]， 2011： 1751?1755.

[6] DAI Xiang?ying， CHEN Qing?cai， WANG Xiao?long，et al. Online topic detection and tracking of financial news based on hierarchical clustering [C]// Proceedings of International Conference on Machine Learning and Cybernetics （ICMLC）. Qingdao，2010： 3341?3346.

[7] KURTZ A J， MOSTAFA J. Topic detection and interest tracking in a dynamic online news source [C]// Proceedings of Joint Conference on Digital Libraries. [S.l.]： [s.n.]， 2003： 122?124.

[8] 楊雪蓉，洪宇，馬彬，等.基于核心詞和實體推理的事件關系識別方法[J].中文信息學報，2014，28（2）：100?108.

[9] VETTER T， JONES M J， POGGIO T. A bootstrapping algorithm for learning linear models of object classes [C]// Proceedings of 1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Juan： IEEE， 1997： 40?46.

[10] 趙愛華，劉培玉，鄭燕.基于LDA的新聞話題子話題劃分方法[J].小型微型計算機系統，2013，34（4）：732?737.

[11] 林雪能.基于語義框架的話題檢測與跟蹤技術研究[D].北京：北京郵電大學，2012.