基于關聯性的熱點話題識別

收稿日期：2014－03－20

基金項目:國家重點基礎研究發展計劃(973)(G2011CB302605）;國家自然科學基金（61173145）。

作者簡介：張玥(1975-)，女，黑龍江阿城人，博士研究生，講師，主要研究方向: 社會計算和數據挖掘；

張宏莉(1973-)，女，吉林榆樹人，博士，教授，博士生導師， 主要研究方向: 網絡安全與社會計算、并行計算、網絡計算等。

摘要：互聯網上的社會性媒體具有傳播內容廣泛、傳播范圍無地域限制、傳播迅速的特點。熱點性話題代表了多數人關注的對象、其動態變化影響著人們的生活和思想。識別熱點性話題具有重要意義。政策制定者通過熱點話題了解人們的生活、調整政策以管理民生。從紛繁變化的海量信息中抽取熱點話題是挑戰性問題。本文以網絡論壇為研究對象，基于網絡媒體中發生社會性熱點事件時會產生相關聯的高頻核心詞，核心詞高度抽象了事件的主要特征和發展方向。基于這個客觀現象，提出了基于主題特征詞關聯的密度聚類算法，建立社會性熱點事件發現模型。實驗表明，提出的主題詞關聯性的熱點話題識別算法識別準確率和召回率高，具有實用價值。

關鍵詞：熱點話題； 聚類； 關聯性

中圖分類號：TP311文獻標識碼：A文章編號：2095-2163（2014）03-0055-05

Correlation Based Hot Topic Identification

ZHANG Yue， ZHANG Hongli

(School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China)

Abstract：Social media of Internet has features of content widely spreading， no-region-restricting ， quickly spreading. Hot event are discussed by lot of people， whose evolution influenced mass’s life and thought. It has important value to identify hot topic. Administrator of government will grasp peoples’ view， and bring out policy to change people’s life. It is a challenge to extract hot topic from varying and massive contents. In network forum， hot events had highly frequency keywords， and keywords correlated with each other in one event. Keywords represented the event and it’s evolution. For this observation， the paper presents hot event clustering algorithm to identify social and hot event. Experiments in Tianya BBS shows that the proposed hot events identification algorithm has high recall and precision， which can be used in large and real dataset.

Key words：Hot Topic; Cluster; Correlation

0引言

互聯網上新興的社會性媒體，具有傳播內容廣泛、傳播范圍無地域限制、且傳播實時迅速的特點。更為重要的是，該媒體彌補了傳統媒體信息發布的單向性、無討論性和無反饋性的不足。社會媒體中，每天討論的話題不勝枚舉。其中的熱點性話題則代表了多數人關注的對象，而該對象的動態變化亦將對人們的生活和思想產生不可估量的深遠影響。2012年南京出現了老太太“碰瓷”事件，因對該事件的不當處理導致了人們不敢幫扶摔倒老人，由此即造成不良社會風氣的蔓延。2013年崔永元和方舟子關于是否食用轉基因的辯論，引發了人們的相關討論，也就是從轉基因的食用安全性問題到保護國家的民生類、保障類食品，以及百姓知情權的討論。這些熱點事件的討論，最終超出了其本身，而顯現出了長期性、社會性的影響作用。為此，識別熱點性話題具有重要意義。比如，政策制定者通過熱點話題深入了解人們的生活、調整政策以改善民生；市場分析人員和商家則依據人們的關注對象即進行有針對性的廣告投放。

“天涯社區”是國內網絡論壇的典型代表，在該論壇中每天都會出現很多新主題，且話題類別涉及覆蓋廣闊，從時事話題到生活娛樂類話題，比如“人口普查”等國家大事和“婚姻嫁娶”等個人瑣事。盡管論壇中人群具有普泛性，但用戶進入論壇后通常發生三種行為：

（1）瀏覽主題和評論；（2）創建主題，發布主題下獨特觀點；（3）對關注主題進行回復評論。

在這些行為中的用戶創建主題對熱點事件發現最具實質性意義，因為其瀏覽和評論都是對某事件的關注或深入討論。作者對網絡論壇中熱點事件進行了跟蹤，在2010年的“李剛門”事件中，12月16~20日僅天涯網絡論壇的天涯雜談版塊就出現29個標題討論該事件，而“黃山大學生黃山事件”則出現了56個標題，熱點事件的相關主題數量和主題核心詞即反映了熱點事件的整體概貌。

網絡媒體中發生社會性熱點事件時，就會出現相關聯的高頻核心詞，這些代表事件的核心詞通常高度抽象了事件的主要特征及發展方向。基于這一客觀現象，本文提出基于主題特征詞的密度聚類算法，建立社會性熱點事件發現模型。模型首先按時間片劃分主題集。對單主題進行詞切分，而根據詞性過濾僅保留名詞和動詞，再計算主題詞詞頻并進行歸一化處理得到主題詞權重，最后基于密度聚類算法識別事件。

1相關工作

熱點事件在話題發現與跟蹤(TDT)領域已開展較多研究，國際會議Trec\\[1\\]上從2008~2013年均有此類的相關議題。文獻\\[1\\]利用用戶關聯關系發現論壇中的話題。首先計算用戶之間的相似度，用戶相似度大的聚合團組即為社區，然后發現與這些用戶團相關聯的話題。文獻\\[2\\]通過馬氏邏輯網絡模型發現用戶參與的話題。因為在論壇中，用戶內容相對來說噪音小一些，因此從用戶角度來發現，用戶成為話題擴散的主要特征。但用戶僅是信息擴散的一個方面，單純依據用戶發現話題的效果很差，且描述性也不好。文獻\\[3\\]從文本內容和相關用戶兩個角度識別話題。首先利用TF-IDF對詞進行建模，再采用UF-ITUF模型對用戶參與度建模，該模型的缺點是噪音詞過多，影響了模型效果。

文獻\\[4\\]從數據規模和時間特性兩個角度，采用凝聚聚類算法識別短時間的事件微類，再對一段時間的微類事件進行聚類，由此而得到整體性熱點事件。文獻\\[5\\]從突發性角度識別話題。同時考察詞和用戶在時間上的變化規律。對有關數據從連續時間片上的變化角度展開分析，并采用頻譜劃分方法從中挖掘出時間序列，再利用時間序列上的突發性識別熱點話題。

第3期張玥，等：基于關聯性的熱點話題識別智能計算機與應用第4卷 部分研究者發現話題的同時，還要識別話題擴散所依托的網絡社區，文獻\\[6\\]即利用突發特征發現社區。文獻\\[7\\]則分析從相關聯的主題-社區中識別動態演化的主題，并于潛在的社區中提取主題擴散路徑，綜合文本特征、社會影響力和主題演化于一體，就可采用高斯分布的馬爾科夫隨機域模型識別社區級主題。

2熱點話題識別算法

在網絡中討論熱點話題時，就會創建具有關聯關系的標題，有些標題也會引用其他標題中的信息，還會在標題中添加新的元素以表示事件的最新進展狀況。代表熱點話題的標志性詞或短語具有高頻性，而且不同話題具有不同標志性詞語。主題間具有隱式關聯關系。主題間的關聯關系可依據核心性共現詞語進行關聯。主題間關聯關系如圖1所示。

圖1文檔-話題間層次圖

Fig.1Hierarchical relation of documents and subjects基于共現詞的話題聚類流程如圖2所示。

單時間窗事件識別算法主要包括三步：對單主題進行主題詞切分和過濾；計算各主題中特征詞權重；利用DBScan算法識別社會性熱點事件。下面分別展開論述。

圖2話題聚類算法流程

Fig.2Topic clustering model2.1相關定義

定義1：文檔集。di是文檔集中的文件，文檔集Ｄ={di}，Ｄ包含M個文件。文件di用具有共現關系的核心詞表示。核心詞集合W={wk}，包含L個核心詞。文件中的核心詞顯示了文件間核心詞的共現性，文件和核心詞是二維關系， di={c(di， wk)}，c(di， wk)表示共現詞wk在di中出現。

定義2：話題。在特定時間段上，從標題中抽取的具有關聯關系的共現詞構成的共現詞集θ，代表了事件的核心詞。θ={w}w∈W，當w∈θ，有c(di，w)，c(dj，w)，且|di，dj| SymbolcB@ δ，δ為文檔間距離閾值。2.2 主題詞切分（1）時間片分割。因為網絡中討論的話題內容具有時事敏感性和即時討論性，故可按時間段將標題集切分為多個數據塊，在數據塊內進行話題分析，而按時間切分標題后可以清晰地看出各時段的熱點事件。時間片大小即可為{日、旬、月、年}等形式，時間片過大會影響后續數據處理，時間片過小則導致聚類事件過細而不能真正代表事件。實驗過程中，依據事件通常的持續時間定義為旬，也可通過連續時間片分析長期性事件。（2）主題詞切分。通常，標題格式：“解決北京人口膨脹問題的必由之路”。對于中文內容的標題，需要進行詞切分，切分過程標記詞性，格式為“詞/詞性”，該標題分解為“解決/v 北京/n 人口/n 膨脹/a 問題/n 的/ude1 必由之路/n”。其中，“/n”為名詞，“/a”為形容詞，“/v”為動詞，“/ude1” 為助詞。中文標題采用中科院的ICTCIAS分詞系統進行分詞。在事件分析過程中，描述事件特征只需保留時間、地點、人物、動作即可，故切分主題詞后僅保留詞性為名詞和動詞兩種詞性的詞語。在主題內重復詞去重，使得主題詞唯一。主題句切分為主題詞后，主題表示為s={word1， word2，…，wordi}，其中wordi≠wordj (i ≠ j)。經詞性過濾后，單主題保留的特征詞數量通常小于10。社會性事件的典型特征是新生名詞多，且新生詞多為人名，如“李剛”、“陳曉鳳”等。新生詞不在ICTCIAS詞典中，人為將新生詞添加到ICTCIAS詞典中，也可動態升級詞典。切分后的詞語，還需要判斷同義詞以縮小詞義差距，如QQ和騰迅表示同一涵義。2.3 候選特征詞權值計算對詞切分后的標題縮略進行詞頻統計。高頻詞代表了該時段的熱點事件特征。詞頻統計過程中采用分治算法。算法輸入為主題集S，S={S1，S2，…，Sj}，其中Si={word1， word2， … ， wordk}，并且wordi ≠wordj (i ≠j)。例1：4個主題句，主題進行詞切分和詞性選取后，主題句表示為主題詞集合。S1={a1，a2，a3}，S2={a1，a3，a4}，S3={a2，a1}，S4={a5，a7}。詞頻統計過程采用自底向上的二路合并算法統計詞頻，如圖3所示。 圖3 主題詞詞頻統計算法Fig.3 The operation of merge same term in different subjects假定主題集中包含n個主題，各主題切分主題詞后，單主題保留的最大特征詞個數為m，那么特征主題詞最多為m ×n個詞語。根據自底向上遞歸算法，主題詞詞頻統計時間復雜度為Q(mnlg(mn))。統計詞頻的同時，還要維護主題詞詞頻數據結構。數據結構定義為三維數組[Subject Index] [Feature Word] [Term Frequent]。主題索引號Subject Index縮寫為“S index”；特征詞Feature Word縮寫為”Word”；詞頻Term Frequent縮寫為“Tf”。基于此，對例1進行詞頻統計的結果則如表1所示。表1 詞頻統計結果Tab.1 Words’ frequency of example1S index S1 S2 S3 S4 Word a1 a2 a3 a1 a3 a4 a2 a1 a5 a7 Tf 3 2 2 3 2 1 2 3 1 1 2.4 熱點事件發現算法發現熱點話題可以轉化為主題聚類問題，首先定義主題間距離，并根據主題間距離確定聚類中心點，其后采用基于高密度連接區域的密度聚類算法（DBSCAN），對單時間片的主題進行聚類，即可發現社會性事件。2.4.1 計算主題間距離2.4.1.1 計算特征詞權重特征詞權重就是特征詞詞頻與主題中各主題詞累加和的比值。為計算方便，將特征詞根據詞頻進行歸一化處理。特征詞權值用f表示，詞頻用Tf表示。特征詞權重的計算如式（1）所示。 f(wordi)= Tf(wordi) ∑Tf(wordj)  (1)其中，f(wordi)表示特征詞wordi的權重。2.4.1.2 計算主題權重主題Si的權重取決于特征詞詞頻大小，特征詞詞頻大，該主題權重就大，如果主題中包含多個高頻詞，則該主題權重將更大。主題權重定義如公式（2）所示。 f(Si)=∑×j f(wordj) (2)其中， f(Si)表示主題Si的權重。2.4.1.3 計算主題間距離主題Si和主題Sj之間距離由主題相似性確定，取決于共現詞數量和詞頻。主題間共現詞越多，詞頻就越大，則主題間距離小相似性越大。（1）基于局部關系的主題間距離基于共現詞頻計算主題間距離的思想是話題關聯時以主題句中的共現詞個數為關聯依據。每次僅考察兩個主題句間距離，由主題句間相交主題詞詞頻所決定。為減弱兩個主題句中僅包含一個高頻共現詞的關聯度，以防止話題漂移，引入關聯因子 SymbolbA@ ，其計算如公式（3）所示。 SymbolbA@ 由共現詞個數所決定，且0 SymbolcB@  SymbolbA@  SymbolcB@ 1。 β= |si∩sj| max(|si|，|sj|)  （3）主題句間基于局部直接距離LDD(Local Direct Distance)的定義如公式（4）所示： d′ij=1－β ∑×a∈(si∩sj) f(a) max(f(si)，f(sj))  （4）（2）基于全局關系的主題間距離主題句間基于局部直接距離LDD的缺點是僅考察兩個主題的主題詞詞頻，未能從整體角度考慮相關主題詞詞頻，因此仍會產生話題漂移問題。比如多個標題討論“人口普查”問題，而標題“房子會增值么？請考慮中國的人口變化趨勢”中雖然有高頻詞“人口”，但討論的卻并非人口普查話題。基于此，依據主題句中關鍵詞進行話題聚類，還需要對主題詞權重進行修正以防產生話題偏離。本文對所有主題詞的詞頻構建主題-詞矩陣，計算主題間距離，既考察兩兩主題句間距離，也考察和其他主題間相對距離。主題句-主題詞矩陣可為提取出的主題詞分配坐標，每個主題句中相應主題詞詞頻即作為其對應坐標值。主題Si表示由主題詞所構成的行向量，用xi表示，同樣Sj表示為向量xj。主題間距離根據主題詞向量采用歐式距離進行計算，dij表示Si和Sj之間距離，全局直接距離GDD(Global Direct Distance)定義如公式（5）所示： dij= ||xi－xj|| max(||xi||，||xj||)  (5)式中，|| SymbolwB@ ||表示l2范式。采用主題詞向量計算主題間距，可充分利用主題詞詞頻和共現詞的數量。例1中，主題S表示為行坐標，主題詞表示為縱坐標，S1到S3所構成的向量X表示為： X=0.3 0.2 0.2 0 0 0 00.3 0 0.2 0.1 0〖0 00.3 0.2 0 0 0 0 00 0 0 0 0.1 0 0.1 (6)與基于共現詞詞頻的主題間距離計算方法相比，通過全局級主題向量計算主題間距離取得了更好的效果，而且能夠防止低頻詞產生的話題漂移問題。（3）基于正文補償的主題間距離改進計算根據主題詞向量采用全局性直接距離方式計算標題間距離緩解了話題漂移問題。但主題句較短，主題句中包含的名次和動詞數量較少。多數網絡媒體有標題還有正文（微博除外），依據標題進行話題關聯，優點是復雜度低，運行速度快。而對標題進行充分解釋的正文，則可作為話題識別的重要依據。和標題處理相一致，對正文內容進行主題詞處理，可利用正文中主題詞的共現量作為話題識別的補充依據。在此提出基于正文補償的主題距離計算公式CCSD（Content Compensated Subjects Distance）。正文c間距離定義如公式（7）所示： d″ij(c)=1－ ∑×a∈(ci∩cj) w(a) max(w(ci)，w(cj))  (7)其后，還需利用正文進行修正補償。在標題詞距離基礎上，補充正文內容相似度，使主題間距離和實際距離更接近，主題距離改進方法CCSD如式（8）所示： d″ij(S)=α*dij(S)+β*d''ij(c) (8)其中， SymbolaA@ 和 SymbolbA@ 為調整因子，0< SymbolaA@ <1，0< SymbolbA@ <1。2.4.2 聚類算法DBSCAN算法首先選取聚類中心點-質心，搜索質心半徑范圍內節點，如果搜索到的節點數超過稠密度閾值則聚簇，再以質心半徑內節點為質心進行迭代和聚簇。（1）質心選取首先選取權值最大的主題作為質心進行基于密度的聚類。質心表示為c。在聚類過程中修改質心，使質心與聚簇點間距離最近。其計算公式為： ck=argminxi∈Gkd(xi，c)2 (9）（2）聚類過程初始選取權重最大的主題為質心，對稠密度閾值 SymbollA@ 和對象半徑 SymboleA@ -鄰域，尋找質心的密度可達點，再從密度可達點向外擴散得到聚類。算法1 主題間采用DBSCAN算法聚簇1) 選取質心q（q的權值最大）；2) 對未考察節點p，如果對象p與q之間距離dpq<ε，且q的ε半徑內節點數超過稠密度閾值λ ，則p與q是密度可達的，循環找到質心q的密度可達點放入事件簇；3) 在q的密度可達點中選取質心q′，重復步驟2）直到質心q所關聯的熱點事件考察結束；4) 對質心q所關聯的熱點事件外的主題，重新選取事件質心重復步驟1)到3)，直到檢測到所有熱點事件；5)對質心q所關聯的熱點事件外的主題，重新選取事件質心，重復步驟1)到3)，直至檢測到所有熱點事件。 3 實驗結果3.1 數據描述本文數據采集于“天涯”網絡論壇上“天涯雜談”版塊，歷時50天的主題，時間區間為2010-11-01~2011-12-20。共13 761個主題。用戶數20 890，帖子數37萬。在天涯雜談數據集中選取標題數多的事件，如“360和QQ大戰”、“我爸是李剛”、“人口普查”等30個事件人工標志作為論壇中的測評數據。3.2 測評指標可由識別準確率（Precision）和召回率（Recall）指標對事件識別結果進行量化分析。Precision和Recall定義分別為： precision= |Ed∩Eb| Ed  (10) recall= |Ed∩Eb| Eb (11)其中，Eb表示標示出的事件，Ed表示算法識別出的事件。3.3 熱點事件識別結果設置的關鍵詞詞頻閾值取為10，稠密度閾值為關聯主題個數設為3，主題間距離半徑設為0.001。對標注集中的事件采用公式（10）和（11）評價本文算法識別的精確度和召回率。算法識別的事件與標注事件中核心詞不完全相同，對核心詞重疊比例進行定義。重疊度是指算法識別出的事件中核心詞與標注集中事件核心詞的重疊比例。當算法識別的事件與標注集事件中核心詞的重疊度超過指定閾值，稱算法正確識別事件。本文對多組重疊度閾值下的準確率和召回率進行了分析。文中基于DBSCAN算法識別事件結果與標注數據集實驗結果如圖4所示。其中，圖4左為精確度曲線，圖4右為識別召回率曲線。圖中比較了采用不同主題距離計算公式的事件識別結果。由圖4可看出，采用不同主題距離計算公式對事件識別結果的影響也各有不同，其中CCSD算法的識別精確率和召回率最高，而GCD，LDD的精確率和召回率最低。從算法識別的準確率和召回率結果看，準確率平均超過60%，召回率平均超過50%。本文提出算法得到的關鍵詞和標注詞在不同重疊度下的精確率和召回率雖有差異，但總體識別結果仍然高于50%，本文算法完全可以在實際中予以推廣應用。 圖4 不同重疊度下的精確率和召回率Fig.4 Precision and recall of different overlap thresholds 參考文獻： \\[1\\] WU Zhili， LI Chunhung. Topic detection in online discussion using non-negative matrix factorization\\[C\\]//Proceedings of International Conferences on Web Intelligence and Intelligent Agent Technology. ACM， 2007: 272-275.［2］CHENG V， LI CH. Topic detection via participation using markov logic network \\[C\\]//Proceedings of 3th International IEEE Conference on Signal-Image Technologies and Internet-Based System， 2007:85-91.［3］ZHU M L， HU W M， WU Q. Topic detection and tracking for threaded discussion communities\\[C\\]//Proceedings of International Conferences on Web Intelligence and Agent Technology， 2008:77-83.[LL]［4］劉星星， 何婷婷， 龔海軍，等. 網絡熱點事件發現系統的設計\\[J\\]. 中文信息學報， 2008， 22(6):80-85.［5］陳友， 程學旗， 楊森. 面向網絡論壇的突發話題發現\\[J\\]. 中文信息學報， 2010， 24(3):80-85.［6］KLEINBERG J. Bursty and hierarchical structure in streams\\[C\\]//Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD’02). ACM， 2002:91-101.［7］LIN C X， MEI Q Z， et al. Inferring the diffusion and evolution of topics in social communities\\[C\\]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ( SNA-KDD’11). ACM， 2011: 1019-1028.［8］http://www.trec.org.