基于SSDKmeans算法的微博熱點(diǎn)話題發(fā)現(xiàn)研究

李海明

摘 要：為及時從海量微博信息中迅捷有效提取出微博熱點(diǎn)話題、事件，提出基于頻繁集的聚類SSDKmeans算法，在有限空間下統(tǒng)計(jì)分詞的近似頻數(shù)，并在此基礎(chǔ)上構(gòu)建文本向量空間模型，在聚類生成的每個話題簇中提煉話題關(guān)鍵詞。通過對2萬條微博數(shù)據(jù)進(jìn)行有效性驗(yàn)證，結(jié)果表明，基于SSDKmeans算法的話題發(fā)現(xiàn)有較高的召回率和精準(zhǔn)率，分別為91.3%、92.1%。SSDKmeans算法能夠有效提高微博熱點(diǎn)話題發(fā)現(xiàn)率，進(jìn)而及時了解社會熱點(diǎn)話題與輿論趨勢。

關(guān)鍵詞：話題發(fā)現(xiàn);文本聚類;微博短文本;頻繁集

DOI：10. 11907/rjdk. 192006 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP391文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2019）009-0173-03

Research on Hot Topic Discovery of Microblog Based on SSDKmeans Algorithms

LI Hai-ming

（College of Computer Science and Engineering，Shandong University of Science and Technology，Qingdao 266590，China）

Abstract： In order to quickly and effectively generate hot topics and events from the massive micro-blog information， in this paper， a clustering algorithm based on SSDKmeans of frequent sets is proposed to calculate the approximate frequency of word segmentation in finite space， and on this basis， a text vector space model is constructed to extract topic keywords in each topic cluster generated by clustering. The validity of 20 000 real microblog data is verified. The experimental results show that topic discovery based on SSDKmeans algorithm has higher recall rate and precision rate， 91.3% and 92.1% respectively. SSDKmeans algorithm can effectively improve the discovery of hot topics in Microblog， and then more timely understand the social hot topics， public opinion trends.

Key Words： topic discovery; text clustering; microblog short text; frequent sets

0 引言

據(jù)《第 42 次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》，截至 2018 年 6 月，微博注冊人數(shù)約 3.5 億，中國網(wǎng)民占比達(dá)42.13%。微博平臺每天發(fā)布海量數(shù)據(jù)，數(shù)據(jù)涵蓋許多熱點(diǎn)話題及事件描述[1]。如何高效處理海量微博數(shù)據(jù)、快速發(fā)現(xiàn)熱點(diǎn)話題是研究熱點(diǎn)。

微博通常以短文本形式呈現(xiàn)，其特點(diǎn)是短文本、噪聲大、網(wǎng)絡(luò)用語多。微博用戶通過不同方式傳發(fā)信息，如網(wǎng)頁頁面轉(zhuǎn)發(fā)、點(diǎn)贊等;支持客戶端設(shè)備也有多種，如平板電腦、臺式電腦及筆記本等。一方面，對于流傳的熱點(diǎn)話題用戶很在意，并且會主動了解信息的動態(tài);另一方面，微博平臺的特征決定了事件、熱點(diǎn)話題在其上流傳極為迅速 [2-3]。

有研究者通過采集微博數(shù)據(jù)得出解決問題方案，從而解決社會實(shí)際問題。2016年美國總統(tǒng)大選時，推特（twitter）用戶發(fā)表了許多包含情感及態(tài)度的詞條，國外有研究人員從中挖掘并分析人們的情感傾向，得到的結(jié)果與實(shí)際較為相符。

國內(nèi)微博平臺發(fā)展晚于國外，目前主要有新浪微博、騰訊微博等。鄭斐然等 [4]用算法 Apriori 進(jìn)行微博熱點(diǎn)話題發(fā)現(xiàn)，能夠迅速找到熱點(diǎn)話題。雖然話題發(fā)現(xiàn)能力有很大提高，但執(zhí)行效率還有較大提升空間;楊亮等 [5]基于時間有效性研究話題、事件，微博用戶發(fā)布信息中包含表達(dá)用戶的態(tài)度詞，這些詞條有較大的情感傾向，能夠較快發(fā)現(xiàn)熱點(diǎn)話題;文獻(xiàn)[6]研究用戶之間的相互關(guān)系及用戶特征，提出基于用戶特征的熱點(diǎn)話題發(fā)現(xiàn)方法 Topic-User，該方法雖然改善了話題詞選擇，但不具普適性。

以上方法都未考慮將有效頻繁項(xiàng)作為微博熱點(diǎn)話題詞[7]。本文提出SSDkmeans算法，對微博熱點(diǎn)話題提取進(jìn)行深入研究。通過研究微博信息的頻繁集詞條、微博文本聚類等相關(guān)技術(shù)，了解最新社會熱點(diǎn)話題，實(shí)時追蹤輿論動向。

1 相關(guān)理論

1.1 文本聚類

不同組別的文檔類型相似性低，相同組別的文檔類型相似性大，這是文本聚類的主要假設(shè)依據(jù)[8]。之所以文本聚類具備非人工處理能力和較好的可伸縮性，并成為文本信息加工的主要技術(shù)手段，是因?yàn)榫垲惒恍枰獧C(jī)器監(jiān)測，無須大量模擬訓(xùn)練過程，以及文檔分類標(biāo)注不需要人工干預(yù)。

對采集到的微博數(shù)據(jù)集進(jìn)行預(yù)處理是文本聚類的第一要務(wù)，將數(shù)學(xué)矩陣應(yīng)用到文本內(nèi)容并加工整合，即文本數(shù)學(xué)化、數(shù)字化，以特征項(xiàng)表征目標(biāo)微博文本信息[8]。利用文本信息建立特征項(xiàng)模型最具代表性的是向量空間模型（Vector Space Model，VSM） [9]。1969年Gerard Salton提出了構(gòu)建文本的VSM模型，是對文檔構(gòu)建的一種統(tǒng)計(jì)模型。將每個文檔構(gòu)造為由一個同屬性集合詞條向量空間中所對應(yīng)的一個“點(diǎn)”，這是VSM模型的重要思想，數(shù)學(xué)表征定義見式（1）。

其中，f是一條微博文本，ti表示特征詞條，wi 為特征詞條的權(quán)重值（其中i=1，2，3，…，n）。因?yàn)槲⒉┪谋緝?nèi)容通常很短，單個詞條大多出現(xiàn)次數(shù)為0或1，能夠很好地篩選出頻繁出現(xiàn)的詞條;而布爾權(quán)重法具有操作簡單、易于理解的特性，所以本文采用布爾權(quán)重法對特征值加權(quán)[10]。

布爾標(biāo)識微博文本，包含對應(yīng)的特征項(xiàng)權(quán)重為 1，否則為 0。

式（2）中，[wij]為微博權(quán)重，[tfij]為微博特征項(xiàng)的權(quán)重值（其中i，j=1，2，3，…，n）。

建立文本特征向量過程：對文本信息進(jìn)行預(yù)加工 （降噪） ，對微博文本進(jìn)行詞條劃割，頻繁項(xiàng)集挖掘，構(gòu)造微博文本向量空間。本文通過將微博短文本映射為VSM所對應(yīng)的向量空間中的點(diǎn)，使計(jì)算機(jī)在處理微博文本時更快速、更具有針對性。

1.2 SSDKmeans算法

Kmeans算法[11-13]依據(jù)各個類別簇的初始中心點(diǎn)進(jìn)行分組，再對初始類別進(jìn)行聚類調(diào)整。Kmeans算法的核心問題是初始中心點(diǎn)的選擇，如果中心選擇不好，聚類結(jié)果將會很差。因此，該算法需要反復(fù)多次優(yōu)化調(diào)整、重新計(jì)算每次優(yōu)化后的聚類中心，這導(dǎo)致處理巨量數(shù)據(jù)時算法性能很低。

1.2.1 Kmeans算法中的距離度量

余弦相似度，指向量空間中的向量夾角的余弦值[11]。余弦相似度相對于距離衡量，更關(guān)注向量在方向上的區(qū)別。如圖1所示，空間坐標(biāo)形象表示了余弦相似度，在三維空間中兩個空間向量A、B之間夾角越小就越相似，反之越不相似。

1.2.2 SSDKmeans算法設(shè)計(jì)

數(shù)據(jù)流是基于時間排序的一種特殊序列[14]。目前，各種網(wǎng)絡(luò)平臺都應(yīng)用了數(shù)據(jù)流技術(shù)，如京東、淘寶用戶在瀏覽物品時的圖片加載過程、NBA直播等。

頻繁項(xiàng)指在數(shù)據(jù)集合中項(xiàng)的出現(xiàn)次數(shù)達(dá)到某一閾值[14]，如某一數(shù)據(jù)集合中含有N個數(shù)據(jù)項(xiàng)，支持度設(shè)定為s∈（0，1），那么數(shù)據(jù)項(xiàng)頻數(shù)達(dá)到sN或者超過sN就歸并為頻繁項(xiàng)。頻繁項(xiàng)廣泛應(yīng)用于領(lǐng)域分析和研究，本文提出結(jié)合頻繁項(xiàng)挖掘ss（space saving，ss）算法[14]和基于距離改進(jìn)的Kmeans算法[15-18]即space saving distance kmeans（SSDKmeans）算法處理微博文本。ss算法主要用于數(shù)據(jù)流計(jì)算，其思想是：有N個數(shù)據(jù)，如果一個新的數(shù)據(jù)項(xiàng)ei在N里面，則對應(yīng)的計(jì)數(shù)加1;如果不在則判斷空間是否已經(jīng)滿了，滿了則替換計(jì)數(shù)最小的em，否則直接添加到數(shù)據(jù)集合D中。

SSDKmeans算法描述如下（其中，輸入是微博數(shù)據(jù)流，輸出是微博聚類簇）：

①數(shù)據(jù)集D有N個微博記錄詞條，每個詞條的計(jì)數(shù)為ci，輸入微博詞條;

②判斷ei是否在D中;

③如果在，fi = fi + ci作為ei的統(tǒng)計(jì)頻數(shù);

④如果不在，再判斷D 空間是否滿了;

⑤D空間沒滿，將加到D中;

⑥否則查找D中計(jì)數(shù)值fm最小的數(shù)據(jù)項(xiàng)em ，將其替換掉;

⑦對步驟⑥頻繁項(xiàng)的數(shù)據(jù)集進(jìn)行VSM建模;

⑧基于最大最小距離初始m個中心點(diǎn);

⑨對W[i][j]的每一條微博，分別計(jì)算它們與m個聚類中心的距離（通過余弦距離）distance（i，m）;

⑩對W[i][j]的每一條微博，計(jì)算最近聚類的中心near（i） = mi;

11評判W[i][j]每一條微博，如果所有的微博文本集都屬于最近的near（i）這一類別，那么終止。如果不是就繼續(xù)執(zhí)行;

12near（i），把i歸并到m中，重新計(jì)算各個中心（即各條微博的平均值），再循環(huán)從步驟⑩開始執(zhí)行。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)環(huán)境

對基于SSD-Kmeans算法的微博文本聚類算法效果進(jìn)行分析、驗(yàn)證和說明。實(shí)驗(yàn)環(huán)境為windows7系統(tǒng)，Microsoft Visual Studio2013開發(fā)軟件，SqlServer2012數(shù)據(jù)庫服務(wù)器，算法由 C#語言實(shí)現(xiàn)。實(shí)驗(yàn)過程中使用的分詞工具是中國科學(xué)院的NLPIR漢語分詞系統(tǒng)[19]。

2.2 數(shù)據(jù)集介紹

實(shí)驗(yàn)使用的數(shù)據(jù)集來自微博開發(fā)者官方平臺。通過預(yù)處理獲取到的微博數(shù)據(jù)集包含約2萬條有效微博文本，處理過程如圖2所示。

2.3 實(shí)驗(yàn)方法

對微博短文本聚類相似性結(jié)果采用召回率和精準(zhǔn)率評判[20]，召回率指SSDKmeans算法找到的頻繁項(xiàng)與實(shí)際存在的頻繁項(xiàng)之比，數(shù)學(xué)公式定義為：

2.4 實(shí)驗(yàn)結(jié)果與分析

對2萬多條關(guān)于某時間段用戶發(fā)表的微博文本信息進(jìn)行實(shí)驗(yàn)，部分實(shí)驗(yàn)結(jié)果如圖3所示，其中“||”前面為每條微博的id號（即每條微博的唯一標(biāo)識號），后面是微博文本信息。抽取的話題詞為失聯(lián)、女童、章子欣、回家。根據(jù)新浪微博官方網(wǎng)站提供的熱點(diǎn)話題列表進(jìn)行對照，實(shí)際存在的話題如圖4所示。

本文進(jìn)行若干次實(shí)驗(yàn)，分別取各自評測指標(biāo)的平均值進(jìn)行對比，如表1所示。從表1可以看出，SSDKmeans算法明顯優(yōu)于傳統(tǒng)Kmeans算法以及基于距離改進(jìn)的Kmeans算法。

本文對采集的微博數(shù)據(jù)預(yù)處理后使用SSDKmeans算法聚類，然后通過NLPIR漢語分詞系統(tǒng)提供的提取關(guān)鍵詞方法抽取話題，最后根據(jù)每個話題包含的微博簇進(jìn)行統(tǒng)計(jì)，某段時間話題熱度排序結(jié)果如表 2所示。

3 結(jié)語

微博作為特殊的網(wǎng)絡(luò)社交平臺，正在影響著人們的生活習(xí)慣以及信息傳播形式。基于SSDKmeans算法的微博文本聚類研究發(fā)現(xiàn)，本方案能夠較好地發(fā)現(xiàn)微博熱點(diǎn)話題。未來要研究如何結(jié)合深度學(xué)習(xí)進(jìn)一步提高微博熱點(diǎn)話題發(fā)現(xiàn)以及提高自然語言處理的精準(zhǔn)性。

參考文獻(xiàn)：

[1] 周煒翔，張仰森，張良. ?面向微博熱點(diǎn)事件的話題檢測及表述方法研究[J] . ?計(jì)算機(jī)應(yīng)用研究，2019，36（12）：69-75.

[2] 宋莉娜，馮旭鵬，劉利軍. 基于SOM聚類的微博話題發(fā)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究，2018， 35（3）：671-674.

[3] 馬哲坤，涂艷. 基于知識圖譜的網(wǎng)絡(luò)輿情突發(fā)話題內(nèi)容監(jiān)測研究[J]. 情報(bào)科學(xué)，2019， V37（2）：33-39.

[4] 鄭斐然，苗奪謙， 張志飛，等. ?一種中文微博新聞話題檢測的方法[J] . 計(jì)算機(jī)科學(xué)，2012，39（1）：138-141.

[5] 楊亮，林原，林鴻飛. 基于情感分布的微博熱點(diǎn)事件發(fā)現(xiàn)[J] . 中文信息學(xué)報(bào)，2012，26（1）：84-90.

[6] 朱少龍. 基于微博的社會化媒體分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2011.

[7] TAN P N.Introduction to data mining [M]. 范明，譯. 北京：人民郵電出版社，2006.

[8] 李慧，王麗婷. 基于詞項(xiàng)熱度的微博熱點(diǎn)話題發(fā)現(xiàn)研究[J] . 情報(bào)科學(xué)，2018，36（4）：45-50.

[9] 夏云慶，楊瑩，張鵬洲. 基于情感向量空間模型的歌詞情感分析[J]. 中文信息學(xué)報(bào)，2010， 24（1）：99-104.

[10] 謝婧. 文微博的話題檢測及微博預(yù)警[D]. 上海：上海交通大學(xué)，2012.

[11] HONG L. Internet public opinion hotspot detection and analysis based on k-means and SVM algorithm[C]. Information Science & Management Engineering， 2010：257-261.

[12] MAO D. Improved canopy-Kmeans algorithm based on Mapreduce[J]. ?Computer Engineering & Applications，2012，48（27）：22-26.

[13] DUNDAR M， QIANG K， ZHANG B， et al. Simplicity of Kmeans versus deepness of deep learning： a case of unsupervised feature learning with limited data[C]. IEEE International Conference on Machine Learning & Applications. 2016：456-461.

[14] METWALLY A，AGRAWAL D，ABBADI A E. Efficient computation of frequent and top-k elements in data streams[C]. 10th International Conference， Database Theory - ICDT， 2005：398-412.

[15] 趙將. 基于改進(jìn)K-means聚類的推薦方法研究[D]. 武漢：華中科技大學(xué)，2016.

[16] 鄭飛，張蕾. 基于分類的中文微博熱點(diǎn)話題發(fā)現(xiàn)方法研究[C]. ?第29次全國計(jì)算機(jī)安全學(xué)術(shù)交流會論文集，2014： 127-131.

[17] KAI P，LEUNG V，HUANG Q. Clustering approach based on mini batch Kmeans for intrusion detection system over big data[J]. IEEE Access， 2018， 6（99）：11897-11906.

[18] BOUKHDHIR A，LACHIHEB O，GOUIDER. An improved Mapreduce design of Kmeans for clustering very large datasets[C]. IEEE International Conference on Computer Systems & Applications，2016：233-238.

[19] 中科院計(jì)算所. NLPIR漢語分詞系統(tǒng)[EB/OL]. http：//ictclas.nlpir.org.

[20] MIN L S， TIAN C. Mongolian information retrieval method based on LDA model[C]. IEEE International Conference on Software Engineering & Service Science，2015：162-165.

（責(zé)任編輯：杜能鋼）