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

摘要：針對微博的實(shí)時(shí)性、稀疏性和海量性特點(diǎn)，提出基于實(shí)時(shí)詞共現(xiàn)網(wǎng)絡(luò)的話題發(fā)現(xiàn)模型。首先，從原始語料中篩選出主題詞集合，再利用時(shí)間參數(shù)計(jì)算共現(xiàn)主題詞的關(guān)系權(quán)重以實(shí)現(xiàn)詞共現(xiàn)網(wǎng)絡(luò)的構(gòu)建，通過該網(wǎng)絡(luò)推算出與話題關(guān)聯(lián)性強(qiáng)的潛在特征詞以解決微博特征詞的稀疏性； 其次，采用改進(jìn)SinglePass算法實(shí)現(xiàn)話題增量聚類；最后，對每個(gè)話題的主題詞按熱度計(jì)算進(jìn)行排序，獲得最具代表性的話題主題詞。實(shí)驗(yàn)結(jié)果表明，該模型與經(jīng)典SinglePass聚類算法相比，話題發(fā)現(xiàn)準(zhǔn)確率約提高6%，綜合指標(biāo)提高8%。實(shí)驗(yàn)結(jié)果證明所提模型的有效性和準(zhǔn)確性。

關(guān)鍵詞：話題發(fā)現(xiàn)；實(shí)時(shí)共現(xiàn)網(wǎng)絡(luò)；短文本；SinglePass聚類；熱度計(jì)算

中圖分類號：TP391.1 文獻(xiàn)標(biāo)志碼：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 引言

微博以其驚人的傳播速度和傳播范圍以及積極的社會影響力吸引不少人的眼球。其中，跟蹤和分享新鮮事是用戶使用微博的一個(gè)很重要的目的[1]。由于微博較強(qiáng)的即時(shí)性和交互性，突發(fā)新聞在微博上的傳播速度非?？欤瑢τ谟绊懥^大的新聞事件，參與評論轉(zhuǎn)發(fā)的用戶量也很大，使得微博能夠先于傳統(tǒng)新聞媒體作出反應(yīng)，成為一個(gè)信息流量相當(dāng)大的平臺，但是其內(nèi)容非常散亂，數(shù)據(jù)噪聲較大。因此及時(shí)發(fā)現(xiàn)微博熱點(diǎn)話題并進(jìn)行監(jiān)管，對營造一個(gè)溫馨、健康、穩(wěn)定的社會環(huán)境有重大的作用和意義，同時(shí)，還可以為網(wǎng)絡(luò)精準(zhǔn)營銷和廣告推薦等新型營銷手段奠定基礎(chǔ)。

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

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

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

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

1 基于CWSTM的話題發(fā)現(xiàn)方法

基于CWSTM的話題發(fā)現(xiàn)主要分為實(shí)時(shí)詞共現(xiàn)網(wǎng)絡(luò)構(gòu)建、話題聚類、熱度排序三個(gè)子任務(wù)，其流程如圖1所示。對采集到的文本通過詞性標(biāo)注和權(quán)重計(jì)算實(shí)現(xiàn)詞共現(xiàn)網(wǎng)絡(luò)的構(gòu)建，該網(wǎng)絡(luò)為整個(gè)CWSTM模型建立基礎(chǔ)，目的是發(fā)現(xiàn)關(guān)聯(lián)性強(qiáng)的潛在特征詞。其次，采用改進(jìn)SinglePass算法實(shí)現(xiàn)話題聚類，最后按熱度計(jì)算進(jìn)行排序，過濾掉話題中熱度較低的詞。

1.1 構(gòu)建實(shí)時(shí)詞共現(xiàn)網(wǎng)絡(luò)

詞共現(xiàn)網(wǎng)絡(luò)的相關(guān)研究早期來源于復(fù)雜網(wǎng)絡(luò)領(lǐng)域，應(yīng)用相對廣泛的是在情報(bào)學(xué)領(lǐng)域。文獻(xiàn)[14-15]針對不同研究領(lǐng)域，給出了不同共現(xiàn)網(wǎng)絡(luò)的構(gòu)建過程，并對網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行了分析。本文認(rèn)為，所謂的詞共現(xiàn)網(wǎng)絡(luò)可以理解成一個(gè)三元帶權(quán)圖G=〈V，E，P〉，即最簡單的共現(xiàn)網(wǎng)絡(luò)的形式是兩點(diǎn)一邊一權(quán)值，例如x和y分別表示主題詞，e=（x， y）表示主題詞x和y同時(shí)出現(xiàn)在文本的一句話中， p表示一對主題詞在詞共現(xiàn)網(wǎng)絡(luò)中的權(quán)值。

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

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

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

3 結(jié)語

本文提出基于CWSTM模型的微博話題發(fā)現(xiàn)方法，針對微博實(shí)時(shí)性和稀疏性等特點(diǎn)，構(gòu)建實(shí)時(shí)詞共現(xiàn)網(wǎng)絡(luò)獲得與話題關(guān)聯(lián)性強(qiáng)的潛在特征詞，采用“簇中心”的SinglePass算法實(shí)現(xiàn)增量聚類，然后通過熱度計(jì)算對每個(gè)話題涉及的詞進(jìn)行降序排列，過濾掉話題中代表性不強(qiáng)的干擾性主題詞。該方法的特點(diǎn)是構(gòu)建實(shí)時(shí)詞共現(xiàn)網(wǎng)絡(luò)，實(shí)時(shí)更新并且獲取與話題關(guān)聯(lián)性強(qiáng)的潛在特征詞，使短文本聚類結(jié)果的準(zhǔn)確度有所提高。實(shí)驗(yàn)結(jié)果表明CWLTM模型的綜合指標(biāo)優(yōu)于無網(wǎng)絡(luò)的SinglePass方法約8個(gè)百分點(diǎn)。后續(xù)工作是研究如何更好地構(gòu)建詞共現(xiàn)網(wǎng)絡(luò)來提高潛在特征詞的質(zhì)量。

參考文獻(xiàn)：

[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]賀亮， 李芳.基于話題模型的科技文獻(xiàn)話題發(fā)現(xiàn)和趨勢分析[J].中文信息學(xué)報(bào)， 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].中文信息學(xué)報(bào)， 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]駱衛(wèi)華， 于滿泉， 許洪波， 等.基于多策略優(yōu)化的分治多層聚類算法的話題發(fā)現(xiàn)研究[J].中文信息學(xué)報(bào)， 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]劉星星， 何婷婷， 龔海軍， 等.網(wǎng)絡(luò)熱點(diǎn)事件發(fā)現(xiàn)系統(tǒng)的設(shè)計(jì)[J].中文信息學(xué)報(bào)， 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]黃九鳴， 吳泉源， 劉春陽， 等.短文本信息流的無監(jiān)督會話抽取技術(shù)[J].軟件學(xué)報(bào)， 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]雷震， 吳玲達(dá)， 雷蕾， 等.初始化類中心的增量K均值法及其在新聞事件探測中的應(yīng)用[J].軟件學(xué)報(bào)， 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]洪宇， 張宇， 范基禮， 等.基于語義域語言模型的中文話題關(guān)聯(lián)檢測[J].軟件學(xué)報(bào)， 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]劉振鹿， 王大玲， 馮時(shí)， 等.一種基于LDA的潛在語義區(qū)劃分及Web文檔聚類算法[J].中文信息學(xué)報(bào)， 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].計(jì)算機(jī)應(yīng)用， 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]蒙祖強(qiáng)， 黃柏雄.一種新的網(wǎng)絡(luò)熱點(diǎn)話題提取方法[J].小型微型計(jì)算機(jī)系統(tǒng)， 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]楊菲， 黃柏雄.詞共現(xiàn)網(wǎng)絡(luò)的遺傳聚類在話題發(fā)現(xiàn)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，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]余傳明， 周丹.情感詞匯共現(xiàn)網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)特性分析[J].情報(bào)學(xué)報(bào)，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.