基于實時詞共現網絡的微博話題發現

李亞星 王兆凱 馮旭鵬 劉利軍 黃青松

摘要：針對微博的實時性、稀疏性和海量性特點，提出基于實時詞共現網絡的話題發現模型。首先，從原始語料中篩選出主題詞集合，再利用時間參數計算共現主題詞的關系權重以實現詞共現網絡的構建，通過該網絡推算出與話題關聯性強的潛在特征詞以解決微博特征詞的稀疏性； 其次，采用改進SinglePass算法實現話題增量聚類；最后，對每個話題的主題詞按熱度計算進行排序，獲得最具代表性的話題主題詞。實驗結果表明，該模型與經典SinglePass聚類算法相比，話題發現準確率約提高6%，綜合指標提高8%。實驗結果證明所提模型的有效性和準確性。

關鍵詞：話題發現；實時共現網絡；短文本；SinglePass聚類；熱度計算

中圖分類號：TP391.1 文獻標志碼：A

Abstract：In view of the realtime， sparse and massive characteristics of microblog， a topic discovery model based on realtime cooccurrence network was proposed. Firstly， the set of keywords was extracted from the primitive data by the model， and the relationship weights was calculated on the basis of the time parameter to structure the word cooccurrence network. Then， sparsity could be reduced by finding potential features of a strong correlation based on weight adjustment coefficient. Secondly， the topic incremental clustering could be achieved by using the improved SinglePass algorithm. Finally， the feature words of each topic were sorted by heat calculation， so the most representative keywords of the topic were got. The experimental results show that the accuracy and comprehensive index of the proposed model increase 6%， 8% respectively compared with the SinglePass algorithm. The experimental results prove the validity and accuracy of the proposed model.

Key words：topic discovery； realtime cooccurrence network； short text； SinglePass cluster； hot degree calculation

0 引言

微博以其驚人的傳播速度和傳播范圍以及積極的社會影響力吸引不少人的眼球。其中，跟蹤和分享新鮮事是用戶使用微博的一個很重要的目的[1]。由于微博較強的即時性和交互性，突發新聞在微博上的傳播速度非?？?，對于影響力較大的新聞事件，參與評論轉發的用戶量也很大，使得微博能夠先于傳統新聞媒體作出反應，成為一個信息流量相當大的平臺，但是其內容非常散亂，數據噪聲較大。因此及時發現微博熱點話題并進行監管，對營造一個溫馨、健康、穩定的社會環境有重大的作用和意義，同時，還可以為網絡精準營銷和廣告推薦等新型營銷手段奠定基礎。

話題發現研究總體上包含兩類：基于概率的話題模型和基于聚類算法。賀亮等[2]利用文檔主題生成模型 LDA（Latent Dirichlet Allocation）抽取科技文獻話題，然后計算話題的強度和影響力，最后針對冷門和熱門話題以及影響力高和影響力低的話題進行了趨勢分析。同時也有很多文獻將作者信息或者參考文獻信息等特征用于LDA實現話題發現。單斌等[3]就LDA話題模型作了一個綜述，作為一種非監督方法，LDA話題模型能夠自動獲取海量文本信息的主題或話題，具有實際應用的前景，同時提及大多數話題演化方法都假設話題數目是固定的，無法探測新話題的產生，舊話題的消亡和分裂。

駱衛華等[4]在相對成熟算法的基礎上，提出基于分治多層聚類的話題發現算法；劉星星等[5]采用SinglePass聚類算法設計了一個網絡熱點事件發現系統；黃九鳴等[6]基于信息流時序特征和上下文相關度，設計了基于SinglePass聚類模型的會話在線抽取算法（SinglePass based on Frequency and Correlation， SPFC）。SinglePass算法在話題檢測方面成為經典[7]。同時，文獻[8-11]在傳統聚類的基礎上進行改進。有研究使用密度函數進行聚類中心的初始化以便客觀地選擇初始化中心，使得結果受語料被處理順序的影響較小，或者引入對內容結構和語義的分析，將分析結果進行聚類。聚類算法針對文本稀疏性和上下文依賴性的解決方法主要有兩類[12]：第一類是借助外部文本如搜索引擎結果擴展短文本；第二類是借助知識庫如WordNet和Wikipedia等，挖掘短文本中詞語之間的內在聯系。第一類方法消耗時間較長，且對搜索引擎的結果非常依賴；第二類方法可以發現詞庫里的詞義關系，但是對詞庫里不存在的詞無法解決。

為快速有效發現話題，出現了詞共現網絡用于話題發現的研究。蒙祖強等[13]基于小世界理論建立詞共現網絡模型并去除大量冗余詞，然后運用極大相容塊技術并基于過濾后的詞共現網絡實現對相交話題的提取，從而獲取網絡話題。但微博擁有海量數據，且更新頻繁，使得此方法用于微博話題發現適用性不強。

針對上述方法存在的問題，本文提出基于實時詞共現網絡話題發現模型（Word Cooccurrence SinglePass Topic Model， CWSTM），有效解決主題特征詞稀疏的問題，該模型基于實時詞共現網絡發現關聯性強的潛在特征詞，采用改進SinglePass算法實現話題聚類，最后為了避免詞集過長，利用熱度計算公式對每個話題涉及的詞進行降序排列。經過多次測試表明，前55%的詞基本涵蓋了每一類的主要話題。

1 基于CWSTM的話題發現方法

基于CWSTM的話題發現主要分為實時詞共現網絡構建、話題聚類、熱度排序三個子任務，其流程如圖1所示。對采集到的文本通過詞性標注和權重計算實現詞共現網絡的構建，該網絡為整個CWSTM模型建立基礎，目的是發現關聯性強的潛在特征詞。其次，采用改進SinglePass算法實現話題聚類，最后按熱度計算進行排序，過濾掉話題中熱度較低的詞。

1.1 構建實時詞共現網絡

詞共現網絡的相關研究早期來源于復雜網絡領域，應用相對廣泛的是在情報學領域。文獻[14-15]針對不同研究領域，給出了不同共現網絡的構建過程，并對網絡結構特征進行了分析。本文認為，所謂的詞共現網絡可以理解成一個三元帶權圖G=〈V，E，P〉，即最簡單的共現網絡的形式是兩點一邊一權值，例如x和y分別表示主題詞，e=（x， y）表示主題詞x和y同時出現在文本的一句話中， p表示一對主題詞在詞共現網絡中的權值。

詞共現網絡構建在現有的詞匯集合和詞關系矩陣[15]的基礎上引入帶時間系數的權重計算。首先對語料庫中的文本進行分詞和詞性標注。如“臺風“燦鴻”被稱60年來7月登陸浙江的最強臺風。受“燦鴻”影響，東海南部海域已出現10～12級大風，并繼續增加，臺風中心風力可達14～17級?！睒擞洖椤芭_風/n， “/w， 燦/ag， 鴻/ag， ”/w， 被/p， 稱/v， 60年/m， 來/v， 7月/m， 登陸/v， 浙江/ns， 的/uj， 最/d， 強臺風/n，。/w， 受/v， “/w， 燦/ag， 鴻/ag， ”/w， 影響/vn，，/w， 東海/ns， 南部/f， 海域/n， 已/d， 出現/v， 10/m， -， 12級/m， 大風/n，，/w， 并/c， 繼續/v， 增加/v，，/w， 臺風/n， 中心/n， 風力/n， 可達/nz， 14/m， -， 17級/m，。/w”。然后篩選出具有實際意義名詞和動詞統稱為主題詞，作為待研究對象放入微博詞匯集合，如L={f1， f2，…， fn}表示微博的集合， f={g1，g2，…，gn}表示一篇微博中詞匯的集合。如圖2所示。

但是，經典SinglePass中存在一些缺陷：相似度計算時需要將新微博與每一類的所有微博進行比較，計算量較大，且用于短文本聚類時特征詞過于稀疏。針對以上問題，本模型首先構建實時詞共現網絡，發現關聯性較強的潛在特征詞。其次在經典SinglePass算法中引入“簇中心”思想?！按刂行摹倍x：簇中心C是最能代表本聚類中所有微博話題的特征詞集合Ci={w1，w2，…}。新微博只與“簇中心”進行相似度比較，而不是與聚類中的每一篇文本進行相似度比較，從而減少計算量。若sim（di，dj）小于閾值θ（經典SinglePass聚類設定θ=0.25），則將其分配到相似度最大的話題聚類中；若sim（di，dj）均大于θ，則作為一個新的話題種子。新微博的特征詞（Fw）與原“簇中心”（C）進行比較時，若 “簇中心”不能全面表示出類中所有微博的話題，要不斷優化“簇中心”。具體方式如下：1）當新微博的特征詞個數（FwN）小于等于“簇中心”特征詞個數時，“簇中心”不發生改變； 2）當新微博的特征詞個數大于“簇中心”時，需要拿新微博和“簇中心”分別與本類中的微博依次進行相似度計算并求和，得到新微博微博綜合相似度F1和“簇中心”微博綜合相似度F2，若F1

算法1 “簇中心”更新算法。

3 結語

本文提出基于CWSTM模型的微博話題發現方法，針對微博實時性和稀疏性等特點，構建實時詞共現網絡獲得與話題關聯性強的潛在特征詞，采用“簇中心”的SinglePass算法實現增量聚類，然后通過熱度計算對每個話題涉及的詞進行降序排列，過濾掉話題中代表性不強的干擾性主題詞。該方法的特點是構建實時詞共現網絡，實時更新并且獲取與話題關聯性強的潛在特征詞，使短文本聚類結果的準確度有所提高。實驗結果表明CWLTM模型的綜合指標優于無網絡的SinglePass方法約8個百分點。后續工作是研究如何更好地構建詞共現網絡來提高潛在特征詞的質量。

參考文獻：

[1]KWAK H， LEE C， PARK H. What is Twitter， a social network or a news media？[C]// WWW 2010： Proceedings of the 19th International Conference on World Wide Web. New York： ACM， 2010：591-600.

[2]賀亮， 李芳.基于話題模型的科技文獻話題發現和趨勢分析[J].中文信息學報， 2010， 26（2）：109-115.（HE L， LI F. Topic discovery and trend analysis in scientific literature based on topic model [J]. Journal of Chinese Information Processing， 2010， 26（2）：109-115.）

[3]單斌， 李芳.基于LDA話題演化研究方法綜述[J].中文信息學報， 2010， 24（6）： 43-49.（SHAN B， LI F. A survey of topic evolution based on LDA [J]. Journal of Chinese Information Processing， 2010， 24（6）： 43-49.）

[4]駱衛華， 于滿泉， 許洪波， 等.基于多策略優化的分治多層聚類算法的話題發現研究[J].中文信息學報， 2005， 20（1）：29-35.（LUO W H， YU M Q， XU H B， et al. The study of topic detection based on algorithm of division and multilevel clustering with multistrategy optimization [J]. Journal of Chinese Information Processing， 2010， 20（1）： 29-35.）.

[5]劉星星， 何婷婷， 龔海軍， 等.網絡熱點事件發現系統的設計[J].中文信息學報， 2008， 22（6）： 80-85. （LIU X X， HE T T， GONG H J， et al. Design of hot Web event detection system [J]. Journal of Chinese Information Processing， 2008， 22（6）： 80-85.）

[6]黃九鳴， 吳泉源， 劉春陽， 等.短文本信息流的無監督會話抽取技術[J].軟件學報， 2012， 23（4）：735-747. （HUANG J M， WU Q Y， LIU C Y， et al. Unsupervised conversation extraction in short text message streams[J]. Journal of Software， 2012， 23（4）： 735-747.）

[7]YANG Y M， PIERCE T， CARBONELL J. A study of retrospective and online event detection[C]// SIGIR 1998： Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 1998.28-36.

[8]雷震， 吳玲達， 雷蕾， 等.初始化類中心的增量K均值法及其在新聞事件探測中的應用[J].軟件學報， 2006， 25（3）：289-295.（LEI Z， WU L D， LEI L， et al. Incremental Kmeans method based on initialisation of cluster centers and its application in news event detection [J]. Journal of Software， 2006， 25（3）： 289-295.）

[9]SALTON G， WONG A， YANG C S. A vector space model for automatic indexing [J]. Communications of the ACM， 1975， 18（11）： 613-630.

[10]洪宇， 張宇， 范基禮， 等.基于語義域語言模型的中文話題關聯檢測[J].軟件學報， 2008， 19（9）：2265-2275.（HONG Y， ZHANG Y， FAN J L， et al. Chinese topic link detection based on semantic domain language model [J]. Journal of Software， 2008， 19（9）： 2265-2275.）

[11]劉振鹿， 王大玲， 馮時， 等.一種基于LDA的潛在語義區劃分及Web文檔聚類算法[J].中文信息學報， 2011， 25（1）：60-65.（LIU Z L， WANG D L， FENG S， et al. An approach of latent semantic space partition and Web document clustering [J]. Journal of Chinese Information Processing， 2011， 25（1）： 60-65.）

[12]張志飛， 苗奪謙， 高燦.基于LDA主題模型的短文本分類方法[J].計算機應用， 2013， 33（6）：1587-1590. （ZHANG Z F， MIAO D Q， GAO C. Short text classification using latent Dirichlet allocation [J]. Journal of Computer Applications， 2013， 33（6）：1587-1590.）

[13]蒙祖強， 黃柏雄.一種新的網絡熱點話題提取方法[J].小型微型計算機系統， 2013， 34（4）：743-748. （MENG Z Q， HUANG B X. Novel approach to Internet hot topic extraction [J]. Journal of Chinese Computer Systems， 2013， 34（4）：743-748.）

[14]楊菲， 黃柏雄.詞共現網絡的遺傳聚類在話題發現中的應用[J].計算機工程與應用，2013， 49（14）：126-129.（YANG F， HUANG B X. Application of GCA of word cooccurrence network in topic detection [J]. Computer Engineering and Applications， 2013， 49（14）：126-129.）

[15]余傳明， 周丹.情感詞匯共現網絡的復雜網絡特性分析[J].情報學報，2010， 29（5）：906-914.（YU C M， ZHOU D. The complexity analysis of the emotional word cooccurrence network [J]. Journal of the China Society for Scientific and Technical Information， 2010， 29（5）：906-914.）

[16]PAPKA R， ALLAN J. Online new event detection using single pass clustering[EB/OL]. [20150210]. http：//maroo.cs.umass.edu/getpdf.php？id=28.