一種基于關(guān)鍵詞的微博話題聚類算法

林 丹 劉建明 谷志瑜

(桂林電子科技大學(xué) 廣西 桂林 541004)

0 引 言

隨著互聯(lián)網(wǎng)的迅速發(fā)展，微博已經(jīng)成為人們表達情感的主流方式之一，這也得益于微博的短小便捷。隨著微博成為人們廣為傳播的社交網(wǎng)站，微博也反映了社會的熱點話題以及暗藏了群眾對話題所表現(xiàn)出來的情感。當(dāng)今網(wǎng)絡(luò)輿情分析也成為人們關(guān)注的重要領(lǐng)域，從社交網(wǎng)站中挖掘出有價值的信息并且呈現(xiàn)出來，也引起了人們的關(guān)注。中國互聯(lián)網(wǎng)絡(luò)信息中心第36次發(fā)布的《中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告》[1]顯示，截至2015年6月，我國微博客用戶規(guī)模為2.04億，手機端微博客用戶數(shù)為1.62億。微博集成了大量用戶以及海量的信息，從各方面影響人們的生活。并且微博上的信息傳播及時，擴散速度快，也為研究學(xué)者們提供了良好的信息平臺。對微博數(shù)據(jù)的話題聚類，能夠發(fā)掘人們當(dāng)前所關(guān)注的主題，有利于輔助政府以及企業(yè)做出決策引導(dǎo)事件向有利的方向發(fā)展。

但是，由于微博短文本的特性，文本的相似度計算采用傳統(tǒng)的文本相似度算法效果并不理想。所以本文結(jié)合LDA算法所得出的“詞袋”以及相關(guān)詞對微博進行主題聚類，使用得到的話題關(guān)鍵詞和提出的文本關(guān)聯(lián)詞算法進行聚類分析，并使用文本關(guān)聯(lián)詞算法對LDA聚類的結(jié)果進行優(yōu)化調(diào)整。

1 相關(guān)工作

國外的相關(guān)研究用到的語料主要是英文語料。Erna等[2]把K-means算法聚類結(jié)合簡單加權(quán)法應(yīng)用于決策支持系統(tǒng)中的。Shubankar等[3]提出一種頻繁使用的關(guān)鍵詞集合來生成話題的話題聚類方法。張晨逸等[4]利用文本生成模型LDA在大規(guī)模Twitter 數(shù)據(jù)集上挖掘話題。Martinez等[5]根據(jù)文本語義構(gòu)造文本屬性數(shù)據(jù)集中心，改進聚類算法。Fodeh等[6]采用核心語義特征的本文驅(qū)動的文本聚類算法提高了聚類的準(zhǔn)確率。Song等[7]結(jié)合本體和基于其潛在語義索引和基于詞典的遺傳算法。

當(dāng)前很多學(xué)者對中文微博的話題發(fā)現(xiàn)進行了研究。楊震等[8]將中文微博看成由單字組成的字符串，基于字符串的特征實現(xiàn)聚類。趙文清等[9]通過烤爐相對詞頻增加率影響因素抽取微博特征詞，根據(jù)共詞網(wǎng)絡(luò)圖實現(xiàn)微博的話題聚類。吳青林等[10]通過設(shè)定特征值相似度閾值，增加相應(yīng)類別的特征詞實現(xiàn)了快速聚類。史劍虹等[11]提出了一種多步驟話題挖掘算法，有效應(yīng)用于高維、稀疏的中文微博。馬雯雯等[12]把隱語義分析(LSA)和層次聚類、K-means聚類結(jié)合起來，提出一種基于LSA的兩階段聚類話題挖掘方法。彭敏等[13]提出一種在回歸預(yù)測和譜聚類基礎(chǔ)上的突發(fā)話題檢測方法。鄭斐然等[14]使用向量空間模型在線檢測中文微博消息中的關(guān)鍵字，通過聚類方法來搜尋新聞話題。葉宇飛[15]依據(jù)知網(wǎng)語義改進最近領(lǐng)聚類算法的Web中文文本聚類算法。

由于文本聚類得到了越來越多研究學(xué)者們的青睞，各種文本聚類方法應(yīng)用層出不窮。本文基于LDA給出的話題關(guān)鍵詞使用一種文本關(guān)聯(lián)詞算法進行話題聚類。

2 基于LDA的話題聚類

2.1 LDA話題模型

基于潛在狄利克雷分布LDA是“詞袋”聚類及主題挖掘模型。LDA模型采用兩種方法：生成模型和主題模型。可以將每篇文檔映射到指定數(shù)量的主題類別中。這是一種非監(jiān)督機器學(xué)習(xí)方法，可以用來發(fā)掘大規(guī)模文檔數(shù)據(jù)集中潛在的主題和進行文本聚類。例如“Iphone7”和“蘋果”就存在很高的關(guān)聯(lián)性，在文檔集合中，共同出現(xiàn)的概率就會比較高。在話題模型的計算中，把這兩個詞語歸于一個主題中，就更有利于計算文本的相似性。

LDA是基于PLSA的文檔生成模型，該模型假設(shè)文檔存在潛在的主題。LDA模型中假設(shè)每篇文檔都有一個主題，每個主題由一系列的詞語組成。在生成文檔的過程中，不斷使用文檔對應(yīng)于主題的概率模型選擇一個主題，再使用主題對應(yīng)與詞語的概率模型挑選一個詞語，直到所有文本被使用完畢。

LDA能夠?qū)ξ谋镜闹黝}信息建模，然后對文本的語義特征很好地降維。這是一種完全的文檔生成模型。 LDA 需要計算詞語對應(yīng)于主題和主題對應(yīng)于詞語這兩個模型的參數(shù)，是典型的有向概率圖模型，如圖1所示。

圖1 LDA概率圖模型

(1)

LDA主題模型推導(dǎo)到出新的文檔潛在參數(shù)的先驗分布是推斷的關(guān)鍵問題。 然而通常我們不是很容易能夠計算出這個先驗分布，僅能通過如拉普拉斯近似法、MCMC(馬爾可夫鏈特卡爾羅方法)、變分近似法等近似算法推斷出來。本文采用的是MCMC中的Gibbs抽樣的方法，是目前最為廣泛的方法之一。

Gibbs抽樣推斷某個單詞屬于某個話題的概率的根據(jù)是文檔中其他詞的概率分布，通過貝葉斯概率公式及其推導(dǎo)，該條件概率分布可以表示為式(2)：

(2)

式中：zj為文檔集合語料庫中的第j個單詞，i=(m，n)是一個二維下標(biāo)，對應(yīng)第m篇文檔的第n個詞，用i表示去除下標(biāo)為i的詞。根據(jù)Dirichlet參數(shù)估計的公式，最終得到LDA的Gibbs抽樣公式見式(3)。

(3)

訓(xùn)練就是使用Gibbs抽樣得到文檔集合中(z，w)的樣本，Gibbs抽樣的過程是計算時每次選定概率向量的一個維度，然后在其他維度的變量值給定的情況下采樣該維度的值，一直迭代到收斂輸出待估計的參數(shù)。一般的過程是：初始時對文檔集合中每個文檔中的每個詞w隨機分配一個編號z，接著不斷重復(fù)讀取每篇文檔，由式(3)重新采樣每個單詞w的主題z，一直到Gibbs抽樣收斂。在推斷時，跟訓(xùn)練的過程相似，只是最后得到的θ分布就是文檔的主題分布。

LDA算法在大規(guī)模文本中對文本進行分類，每個話題對應(yīng)一個詞袋，每個詞袋中包含了一系列的詞語以及其相關(guān)權(quán)重。采用開源的GibbsLDA++訓(xùn)練采集到的所有微博，Gibbs抽樣迭代次數(shù)設(shè)為1 000。經(jīng)過LDA主題模型計算后得出每個主題及其主題分布，運行后輸出的文件包括.others、.phi、.theta、.tassign 和.twords幾個文件。其中，twords文件為每個主題及其所包含的關(guān)鍵詞，.theta是每篇文檔屬于每個話題的概率分布，向量的長度是話題數(shù)量K。

張紹凡依舊跟我同班，她依然是眾星捧月的焦點，成績依舊很好，全班第一，年級第三。我的成績進步很大，雖然暫時不足以撼動張紹凡的“班一寶座”，但于我自己卻是全新的開始。

2.2 文本關(guān)聯(lián)詞算法

使用LDA話題模型對微博數(shù)據(jù)進行話題挖掘后，可以得到比較明確的主題和微博所屬的話題類別，下面使用微博的關(guān)聯(lián)詞算法來重新對微博進行優(yōu)化調(diào)整。一個詞語w在所有文檔中的關(guān)聯(lián)詞算法如下：

1) 從全部微博的開頭掃描，若找到詞語w，則在該位置停下。

2) 把這前后相鄰10個位置內(nèi)的詞語作為詞語w的關(guān)聯(lián)詞，由于微博的短文本特性，設(shè)定一個詞與其前10個詞相關(guān)聯(lián)，也與后面10個詞相關(guān)聯(lián)，把關(guān)聯(lián)的詞語及其關(guān)聯(lián)數(shù)量分別保存為CW、CN，其中cwi∈CW，cni∈CN，若關(guān)聯(lián)詞相同則合并，關(guān)聯(lián)次數(shù)相加。

3) 計算詞語w的每個關(guān)聯(lián)詞在全部微博中出現(xiàn)的次數(shù)N，其中ni∈N。

5) 根據(jù)得到的關(guān)聯(lián)詞及其權(quán)重進行權(quán)重降序排序。

“貪官”一詞得到的關(guān)聯(lián)詞排序結(jié)果見表1。

表1 “貪官”一次的關(guān)聯(lián)詞排序圖

對一條微博所包含的詞語，逐一進行關(guān)聯(lián)詞計算，就可以得到微博的關(guān)聯(lián)詞，與特色主題的關(guān)鍵詞進行關(guān)聯(lián)計算，就可以微博與主題的關(guān)聯(lián)性。微博與主題的關(guān)聯(lián)性計算步驟如下：

2) 每個詞使用上面介紹的關(guān)聯(lián)詞算法，取前10個關(guān)聯(lián)詞，也就是關(guān)聯(lián)性最大的10個詞語，得到一條微博的所有關(guān)聯(lián)詞組合CW，其中cwi∈CW。

3) 把得到的關(guān)聯(lián)詞與每個特色主題的關(guān)鍵詞進行比較，微博wbi與每個特色主題的關(guān)聯(lián)性記為CWN，其中cwni∈CWN。CWN這樣計算：在wbi對某個特色主題進行關(guān)聯(lián)性計算時，若wbi的詞語組合中的詞wordj出現(xiàn)在特色主題Tk中，則wbi的與該特色主題的關(guān)聯(lián)性cwnk增加50，若wbi的關(guān)聯(lián)詞在該特色主題關(guān)鍵詞中的第m個位置出現(xiàn)時，則根據(jù)關(guān)鍵詞在該主題中的排序cwnk增加K-m，其中K為聚類時設(shè)定的K個主題。

4) 重復(fù)步驟(1)-步驟(3)就可以得到全部微博與每個主題的關(guān)聯(lián)性。

當(dāng)使用該算法對聚類結(jié)果進行聚類結(jié)果優(yōu)化時，則當(dāng)關(guān)聯(lián)性CWN的最大值cwnmax>0時，則把該微博歸為關(guān)聯(lián)性最高的主題中。

若使用主題關(guān)鍵詞結(jié)合文本關(guān)聯(lián)詞算法進行話題聚類，則當(dāng)cwnmax>α(α為設(shè)定的閾值)，則把該微博歸為關(guān)聯(lián)性最高的主題中。

2.3 數(shù)據(jù)預(yù)處理

由于中文文本沒有任何符號來分割詞語，所以必須要通過分詞工具來進行詞語的分割。本文采用開源的結(jié)巴分詞作為分詞工具，該分詞工具支持自己添加詞典和停用詞，分詞速度跟分析效果都比較好。以“壯哉我長春亞泰！贏得了恒大，輸?shù)昧艘泸v！亞泰的世界你永遠不懂！”為例，經(jīng)過分詞后的內(nèi)容為：壯哉/我/長春/亞泰/贏得/了/恒大/輸/得了/毅騰/亞泰/的/世界/你/永遠/不懂。本文采用停用詞表來去除停用詞，停用詞表中的停用詞為833個，包括連詞、語氣詞等。

由于微博中存在像“@”這樣無意義的符號以及網(wǎng)址，在預(yù)處理中都必須去除，去除它們以及停用詞后，剩下的有可能是空文本或者字?jǐn)?shù)太少的文本，都應(yīng)該去掉。比如“今天心情很好”，“不開心”。字?jǐn)?shù)太少的文本信息量少，意義不大，不能完整表達話題。所以把詞匯量少于3的都過濾掉。

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

本文采用的語料為新浪微博的2014年4月30日至2014年5月11日10帶標(biāo)注的數(shù)據(jù)集，數(shù)據(jù)集包括6個主題的1 238條。加入了683條無標(biāo)注的噪聲數(shù)據(jù)，總共為1 921條數(shù)據(jù)。經(jīng)過預(yù)處理后剩余1 907條數(shù)據(jù)。帶標(biāo)注的數(shù)據(jù)主題為：電影“同桌的你”、恒大比賽、房價下跌、魅族手機、反腐倡廉和霧霾。各話題的具體信息見表2。

表2 各話題信息圖

3.2 評價標(biāo)準(zhǔn)

本次實驗的評價標(biāo)準(zhǔn)采用準(zhǔn)確率、召回率以及F值三個評價指標(biāo)。

其中a為被正確提取的數(shù)據(jù)條數(shù)，b為提出的信息條數(shù)，c為該類的全部樣本數(shù)，F(xiàn)值是綜合準(zhǔn)確率和召回率的的整體指標(biāo)，見式(4)-式(6)。

(4)

(5)

(6)

3.3 實驗結(jié)果

使用GibbsLDA++對微博數(shù)據(jù)進行話題聚類，令超參數(shù)α=0.5，β=0.1，K=11，迭代次數(shù)為1 000。通過LDA模型聚類后得到K個話題，每個話題由對應(yīng)的關(guān)鍵字表示，LDA運行的部分結(jié)果如表3所示。

表3 部分LDA結(jié)果示例圖

根據(jù)GibbsLDA++運行得到的文件.theta的文本所屬主題的概率矩陣對微博進行聚類，文件.theta中每行對應(yīng)每條微博屬于每個主題的概率，把每條微博歸入對應(yīng)的概率最大的主題中，這樣就完成了通過LDA話題模型實現(xiàn)的微博聚類。接著對聚類的結(jié)果采用文本關(guān)聯(lián)詞算法進行優(yōu)化調(diào)整。

利用LDA聚類得到每個話題的關(guān)鍵詞，使用文本關(guān)聯(lián)詞算法對微博進行聚類分析，根據(jù)在LDA話題模型得到被歸類正確的微博，計算它們與所屬話題的關(guān)聯(lián)性，關(guān)聯(lián)性分布如表4所示。由表4可知，關(guān)聯(lián)性最小的區(qū)間在200到250之間，則實驗中把α的值設(shè)為200來進行聚類分析。

表4 LDA話題聚類正確的微博與主題的關(guān)聯(lián)性分布

把α的值在200附近變化時，發(fā)現(xiàn)當(dāng)α取值為160時得到的結(jié)果是最優(yōu)的。圖2為閾值α取值得到的評估曲線圖。當(dāng)α的值為160時，聚類得到的準(zhǔn)確率、召回率和F值都達到了最優(yōu)。

圖2 不同閾值α得到的評估曲線圖

3.4 對比實驗分析

為了驗證文本關(guān)聯(lián)詞算法的有效性，實驗把LDA聚類算法、采用文本關(guān)聯(lián)詞算法優(yōu)化和關(guān)鍵詞結(jié)合文本關(guān)聯(lián)詞算法進行聚類的結(jié)果進行對比分析。所有話題的準(zhǔn)確率、召回率、F值對比實驗結(jié)果表5所示，對比柱狀圖如圖3所示。

表5 算法評估實驗結(jié)果

圖3 算法評估對比柱狀圖

4 結(jié) 語

根據(jù)以上實驗結(jié)果分析，使用文本關(guān)聯(lián)詞算法對微博進行優(yōu)化調(diào)整后，得到準(zhǔn)確率、召回率和F值基本都得到了提高。而采用關(guān)鍵詞和文本關(guān)聯(lián)詞算法進行微博聚類，得到的準(zhǔn)確率、召回率、F值均得到了5個百分點以上的提高，在最優(yōu)的情況下比LDA算法每個指標(biāo)均提高10百分點以上。實驗證明，該算法在文本聚類的應(yīng)用中是有效的。但是文本關(guān)聯(lián)詞算法優(yōu)化時只能發(fā)現(xiàn)一部分被錯誤歸類的微博，不能發(fā)現(xiàn)被歸為垃圾主題中的微博，在以后的研究中還可以改進，提高算法的有效性。而且，算法依賴于每個主題所對應(yīng)的關(guān)鍵詞，在主題沒有關(guān)鍵詞的情況下，無法使用。只要每個主題存在關(guān)鍵詞，該算法可以對聚類進行優(yōu)化或者聚類分析。

[1] http://help.3g.163.com/15/0723/16/AV7KRQCD00964K JA.html.

[2] Daniati E,Nugroho A.K-Means clustering with Decision Support System using SAW Determining thesis topic[C]//2016 6th IEEE International Conference on Control System,Computing and Engineering (ICCSCE),2016:326-331.

[3] Shubankar K,Singh A P,Pudi V.A frequent keyword-set based algorithm for topic modeling and clustering of research papers[C]//2011 3rd Conference on Data Mining and Optimization (DMO),2011:96-102.

[4] 張晨逸,孫建伶,丁軼群.基于MB-LDA模型的微博主題挖掘[J].計算機研究與發(fā)展,2011,48(10):1795-1802.

[5] Martinez S,Valls A,Sanchez D.Semantically-grounded construction of centroids for datasets with textual attributes[J].Knowledge-Based Systems,2012,35(15):162-172.

[6] Fodeh S,Punch B,Tan P N.On ontology-driven document clustering using core semantic features[J].Knowledge and Information Systems,2011,28(2):395-421.

[7] Song W,Li C H,Park S C.Genetic algorithm for text clustering using ontology and evaluating the validity of various semantic similarity measures[J].Expert Systems with Applications An International Journal,2009,36(5):9095-9104.

[8] 楊震,段麗娟.基于層次結(jié)構(gòu)的多策略中文微博情感分析和特征抽取[J].中文信息學(xué)報,2012,26(1):78-83.

[9] 趙文清,侯小可.基于詞共現(xiàn)圖的中文微博新聞話題識別[J].智能系統(tǒng)學(xué)報,2012,7(5):444-449.

[10] 吳青林,周天宏.基于話題聚類及情感強度的中文微博輿情分析[J].情報理論與實踐,2016,39(1):109-112.

[11] 史劍虹,陳興蜀,王文賢.基于隱主題分析的中文微博話題發(fā)現(xiàn)[J].計算機應(yīng)用研究,2014,31(3):700-704.

[12] 馬雯雯,魏文晗,鄧一貴.基于隱含語義分析的微博話題發(fā)現(xiàn)方法[J].計算機工程與應(yīng)用,2014,50(1):96-100.

[13] 彭敏,張?zhí)┈|,黃佳佳,等.基于回歸模型與譜聚類的微博突發(fā)話題檢測方法[J].計算機工程,2015,41(12):176-181.

[14] 鄭斐然,苗奪謙,張志飛,等.一種中文微博新聞話題檢測的方法[J].計算機科學(xué),2012,39(1):138-141.

[15] 葉宇飛.基于知網(wǎng)語義的Web中文文本聚類方法研究[D].重慶:重慶郵電大學(xué),2013.