摘? 要：為了從大量微博信息中提取重要事件并預(yù)測發(fā)展趨勢，基于微博的地理特征和時(shí)間特征，提出了一種對微博進(jìn)行聚類和索引的多層次方法。該方法使用X均值聚類，根據(jù)用戶輸入的關(guān)鍵詞建立索引，并根據(jù)索引自動評估聚類的數(shù)量。同時(shí)，基于情感特征對微博進(jìn)行聚類，創(chuàng)建包含負(fù)面情感微博和正面情感微博的兩個聚類。實(shí)驗(yàn)結(jié)果表明，所提索引機(jī)制不僅便于搜索，而且有利于檢索任務(wù)。與其他微博聚類方法相比，所提方法在DBI指標(biāo)和S系數(shù)兩個指標(biāo)上均有更好的表現(xiàn)，且時(shí)間復(fù)雜度較傳統(tǒng)方法更低，與輸入數(shù)據(jù)量的對數(shù)成正比。

關(guān)鍵詞：微博檢索;時(shí)間特征;地理特征;情感特征

中圖分類號：TP391? ? ?文獻(xiàn)標(biāo)識碼：A

Research on Multi-level Microblog Retrieval Method based on Multiple Features

FAN Yimin

（College of Computer Information and Engineering， Nanchang Institute of Technology， Nanchang 330044， China）

rowan521@163.com

Abstract： In order to extract important events from a large amount of microblog information and predict the development trend， this paper proposes a multi-level method for clustering and indexing microblogs based on geographic and temporal characteristics of microblogs. X-mean clustering is used in this method， an index is built based on the keywords entered by the user， and the number of clusters is automatically evaluated based on the index. At the same time， the microblogs are clustered based on emotional characteristics， and two clusters containing negative emotional microblogs and positive emotional microblogs are created. Experimental results show that the proposed indexing mechanism is not only convenient for searching， but also conducive to retrieval tasks. Compared with other microblog clustering methods， the proposed method has better performance on both the DBI （Discriminated Bond Index） indicator and the S coefficient. The time complexity is lower than that of the traditional method， which is proportional to the logarithm of the input data volume.

Keywords： microblog retrieval; temporal characteristics; geographic characteristics; emotional characteristics

1? ?引言（Introduction）

過去幾年中，網(wǎng)絡(luò)媒體得到了飛速發(fā)展，越來越多的出版公司將重心從紙媒體轉(zhuǎn)移到網(wǎng)絡(luò)媒體。在線媒體通過社交網(wǎng)絡(luò)平臺完成點(diǎn)對點(diǎn)分享和廣播。在博客和微博中，用戶可以與特定人群共享信息，或向大量用戶傳播信息。由于微博的主體或元數(shù)據(jù)中包含了大量信息，因此，以微博時(shí)間、地理位置或空間特征為基礎(chǔ)，可以提取重要事件及其發(fā)展趨勢[1]。

微博的聚類檢索是一個熱門研究課題，已經(jīng)有很多研究者對其進(jìn)行了研究。王李冬等[2-3]提出了基于HowNet知識庫系統(tǒng)的微博語義檢索方法。楊震等[4]提出了一種微博檢索結(jié)果的二次重排算法，基于微博內(nèi)容相似關(guān)系構(gòu)建關(guān)系圖模型，利用PageRank算法對微博檢索結(jié)果進(jìn)行二次排序。SAMUEL等[5]提出了一個Lex-Rank算法的變體，以提取微博中存在的不同類型的時(shí)間信息，并將之用于摘要創(chuàng)建。韓中元等[6]提出了一種面向微博檢索的基于詞匯時(shí)間分布的查詢擴(kuò)展方法。DEMIRIZ等[7]提出了基于數(shù)據(jù)的空間和時(shí)間特征進(jìn)行數(shù)據(jù)分析的方法，并使用模糊規(guī)則將該方法應(yīng)用到欺詐檢測任務(wù)中，表現(xiàn)出較好的性能。

本文的目標(biāo)是開發(fā)一個含有微博時(shí)間、地理坐標(biāo)和情感特征的框架，并使用這些特征進(jìn)行聚類，建立起時(shí)間摘要處理的索引。本文提出了一個框架，以克服傳統(tǒng)聚類（如K均值算法[8]）算法的缺陷，并提出了一個多層級聚類方法，其中，空間特征進(jìn)行1級聚類，時(shí)間特征完成2級聚類。同時(shí)，還可以基于情感對微博進(jìn)行聚類。

2? ?提出的方法（Proposed method）

本文提出的方法主要以微博的時(shí)間、地理位置和情感特征為基礎(chǔ)，對微博進(jìn)行索引并創(chuàng)建聚類。以往的方法依靠用戶指定的聚類數(shù)量，而本文的方法則基于建立的索引，自動評估聚類的數(shù)量。所提方法對K均值聚類做出了改進(jìn)，有助于以微博的時(shí)間、地理位置和情感特征為基礎(chǔ)，從微博中確定聚類的數(shù)量[9]。

首先，定義一個數(shù)據(jù)集，包含總計(jì) 個文檔，該數(shù)據(jù)集共維，有不同的模型，利用完成對模型的評分。使用柯西-施瓦茲準(zhǔn)則對后驗(yàn)進(jìn)行逼近，如下所示：

（1）

式中，為第個模型的似然對數(shù)，取最大似然點(diǎn);為中的參數(shù)數(shù)量，選擇得分最高的模型。點(diǎn)概率的計(jì)算公式如下：

（2）

自由參數(shù)的數(shù)量為，X均值在全局用柯西-施瓦茲準(zhǔn)則選擇最佳模型，并在局部引導(dǎo)形心的分割。的范圍表示為。開始時(shí)，X均值從開始，并在需要時(shí)持續(xù)添加形心，直到達(dá)到上限為止。在該過程中，將得分最高的形心集合記錄為最佳路線，并將之作為輸出結(jié)果。對微博的定義如下：

（3）

式中，為微博ID，為用戶名，為微博正文文本，為微博發(fā)表時(shí)間，為發(fā)布微博的地理位置，為微博語言，為用戶ID，為微博中包含的主題標(biāo)簽，為回復(fù)微博，為轉(zhuǎn)發(fā)微博，為微博的轉(zhuǎn)發(fā)數(shù)量。

每條微博中包含的特征數(shù)量不同，最高可能超過30 個特征。本文僅利用了少數(shù)幾個特征，利用基于查詢的方法完成對微博的索引，其中用戶向系統(tǒng)提供搜索話題，利用該關(guān)鍵詞建立一個索引。在建立索引的過程中，本文將首先對帶噪數(shù)據(jù)的微博進(jìn)行預(yù)處理，移除不包含原始內(nèi)容的微博。

本文提出的基于時(shí)間和空間特征對微博進(jìn)行聚類和索引的框架如圖1所示。首先，移除時(shí)間和空間之外的其他特征，用包含微博用戶所用的普通文本的最新詞語和縮寫形式的微博字典，對微博進(jìn)行標(biāo)準(zhǔn)化，并從微博中移除停用詞;然后，對微博進(jìn)行詞語切分，在微博上執(zhí)行“詞干”搜尋，將“詞干”切分存儲在數(shù)據(jù)庫中，建立兩個數(shù)據(jù)框架;最后，將查詢與微博庫進(jìn)行匹配，如果數(shù)據(jù)框架中存在該詞語，則該微博將被放入一個新的數(shù)據(jù)集中。利用X均值聚類算法[1-9]得出位置的數(shù)量和與該數(shù)量相對應(yīng)形成的聚類數(shù)量，找出聚類的最優(yōu)數(shù)量。完成初始聚類的形成后，在每個以地理位置特征形成的聚類上，完成基于微博時(shí)間特征的聚類，得到在地理位置特征中與微博的時(shí)間相關(guān)的2級聚類。

3? ?實(shí)驗(yàn)與分析（Experiments and Analysis）

本文實(shí)驗(yàn)使用Intel Core i7處理器、RAM為16 GB的個人電腦作為實(shí)驗(yàn)平臺，利用Fire-hose API得到所有的微博數(shù)據(jù)，包括地理位置信息的微博數(shù)量為134，540 條。數(shù)據(jù)收集于2019 年2 月至2019 年5 月。

基于Vincenty公式[9]，使用大圓距離計(jì)算出兩個地理坐標(biāo)之間的距離，以保證微博位置在用戶設(shè)定的距離閾值內(nèi)。如果該微博在閾值之外，則該微博形成一個單獨(dú)的聚類。距離定義如下：

（4）

式中，、為點(diǎn)1的緯度和經(jīng)度;、為點(diǎn)2的緯度和經(jīng)度;為點(diǎn)之間的圓心角。

利用兩個位置坐標(biāo)，通過上述公式得出兩個位置之間的距離。接著，進(jìn)行如下實(shí)驗(yàn)：首先，計(jì)算兩微博之間的距離，利用給定的閾值形成聚類;然后，利用微博的發(fā)帖時(shí)間對聚類內(nèi)的微博再次進(jìn)行聚類，即通過X均值完成該聚類;最后，利用微博的創(chuàng)建時(shí)間得出聚類。

3.1? ?評價(jià)分析

為了進(jìn)行聚類評價(jià)，本文實(shí)驗(yàn)首先得出基于地理位置的第一個聚類，然后使用微博的創(chuàng)建時(shí)間對這些聚類再次進(jìn)行聚類?；诘乩碜鴺?biāo)的聚類形成如圖2所示，其中，“×”表示聚類的中心。圖3給出了聚類1中的聚類，基于微博事件再次形成聚類的結(jié)果?？梢钥闯觯啾扔?級聚類，2級聚類具有更好的類間和類內(nèi)的特征，特征樣本更加清晰明了。

本文使用DBI指標(biāo)和S系數(shù)兩種方法進(jìn)行評價(jià)，這兩種指標(biāo)數(shù)值越高，表示結(jié)果越好。不同方法的聚類評價(jià)結(jié)果如表1所示。實(shí)驗(yàn)中，每種方法在不同數(shù)量的微博上運(yùn)行3 次。由表1可知，在所有場景中，本文提出的系統(tǒng)均表現(xiàn)出超過其他聚類系統(tǒng)的性能。文獻(xiàn)[5]提取微博中存在的不同類型的時(shí)間信息，并將之用于摘要創(chuàng)建，所用的元素比較少，獲得的聚類結(jié)果較差。文獻(xiàn)[8]使用較為傳統(tǒng)的K均值聚類，在總體微博聚類過程中，使用的特征元素和層次較少。文獻(xiàn)[7]將數(shù)據(jù)的空間和時(shí)間特征進(jìn)行數(shù)據(jù)分析，取得了聚類結(jié)果最為接近本文的方法，優(yōu)于文獻(xiàn)[5]和文獻(xiàn)[8]?？傮w來說，本文方法兩種評價(jià)結(jié)果最優(yōu)，其使用的特征元素和層次較為充分，因此，獲得的聚類效果更好。

3.2? ?復(fù)雜度分析

本文提出框架的復(fù)雜度為，其中，表示微博數(shù)量，表示要形成的數(shù)據(jù)量。這表明所提方法的執(zhí)行時(shí)間與輸入數(shù)據(jù)的對數(shù)成正比，本文方法并不需要使用所有數(shù)據(jù)。傳統(tǒng)微博K均值方法的復(fù)雜度為，其中，表示待聚類的項(xiàng)數(shù)，表示要形成的聚類數(shù)，表示維度。這表明其運(yùn)行時(shí)間取決于因子數(shù)量，例如，待聚類的項(xiàng)數(shù)、要形成的聚類數(shù)和維度等。這證明與傳統(tǒng)的微博聚類算法相比，所提方法的復(fù)雜度更低。

4? ?結(jié)論（Conclusion）

本文提出了一種基于微博的時(shí)間特征、地理位置和情感對微博進(jìn)行聚類的方法，該方法能夠?qū)儆谀硞€特定位置、某個特定的時(shí)間段或包含某種特定情感的微博進(jìn)行聚類。在聚類之前，本文首先建立兩個索引，分別用于非詞干關(guān)鍵詞和詞干關(guān)鍵詞，以達(dá)到有利于搜索過程和匯總過程的目的，使得微博的搜索工作量降低，搜索時(shí)間加快。

參考文獻(xiàn)（References）

[1] 曹霧，張景鵬，胡含凱，等.基于文森特公式計(jì)算遙測天線理論跟蹤彈道[J].探測與控制學(xué)報(bào)，2015，37（6）：103-106.

[2] 王李冬，張慧熙.基于HowNet的微博文本語義檢索研究[J].情報(bào)科學(xué)，2016，34（9）：134-137.

[3] 王李冬，呂明琪.融合語義和時(shí)間因子的微博檢索[J].情報(bào)雜志，2016，35（4）：190-194.

[4] 楊震，張廣源，范科峰.基于圖模型決策的微博檢索二次排序算法[J].北京工業(yè)大學(xué)學(xué)報(bào)，2017，43（1）：94-99.

[5] SAMUEL A， SHARMA D K. Modified lexrank for tweet summarization[J]. International Journal of Rough Sets and Data Analysis （IJRSDA）， 2016， 3（4）：79-90.

[6] 韓中元，楊沐昀，孔蕾蕾，等.基于詞匯時(shí)間分布的微博查詢擴(kuò)展[J].計(jì)算機(jī)學(xué)報(bào)，2016，39（10）：2031-2044.

[7] DEMIRIZ A， LU B? E. Fuzzy rule-based analysis of spatio-temporal ATM usage data for fraud detection and prevention1[J]. Journal of Intelligent & Fuzzy Systems， 2016， 31（02）：805-813.

[8] 張?jiān)苽ィ伟曹?基于K-Means改進(jìn)算法在微博話題發(fā)現(xiàn)中的應(yīng)用研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2016，25（10）：308-311.

[9] 曹鵬，李博，栗偉，等.結(jié)合X-means聚類的自適應(yīng)隨機(jī)子空間組合分類算法[J].計(jì)算機(jī)應(yīng)用，2013，33（2）：550-553.

作者簡介：

范怡敏（1981-），女，碩士，講師.研究領(lǐng)域：軟件工程，大數(shù)據(jù).