陳龍穩(wěn)

（四川大學(xué)計算機學(xué)院，成都　610065）

基于改進的Single-Pass算法微博話題發(fā)現(xiàn)

陳龍穩(wěn)

（四川大學(xué)計算機學(xué)院，成都610065）

詳細介紹傳統(tǒng)的Single-Pass算法并分析它的特點和不足之處，并針對傳統(tǒng)的Single-Pass算法對輸入順序敏感的問題，提出一種改進方法，即找出含有話題信息豐富的微博客文本優(yōu)先聚類，得到初始的話題簇，再對余下的微博客文本進行聚類以提高聚類的精度。對話題發(fā)現(xiàn)的流程：文本預(yù)處理、向量模型的構(gòu)建、Single-Pass聚類、凝聚層次聚類進行詳細的描述，實驗結(jié)果表明該方法在召回率、準(zhǔn)確率、F值指標(biāo)上均優(yōu)于傳統(tǒng)的方法。

微博；Single-Pass；話題；聚類

0　引言

以新浪微博為代表的微博客是年輕一代網(wǎng)民獲取資訊、分享信息的重要平臺，由于平臺準(zhǔn)入的門檻低，所有注冊用戶都可以對同一話題發(fā)表自己的看法、評論別人發(fā)表的信息。當(dāng)參與的網(wǎng)友眾多時，話題熱度會飆升，相關(guān)的帖子數(shù)量也隨之猛漲，而用戶的精力卻十分有限，不可能通過閱讀所有帖子來獲取相關(guān)話題的有用知識，話題檢測與追蹤技術(shù)可以有效解決此類問題［1］。微博客的話題檢測技術(shù)不僅可以為用戶展示當(dāng)前微博討論的話題，還可以為政府部門提供輿情監(jiān)督和輿情引導(dǎo)以及為商業(yè)決策提供數(shù)據(jù)依據(jù)，因此成為當(dāng)前學(xué)術(shù)界一個熱門的研究方向。

1　微博客的特點

微博客話題發(fā)現(xiàn)不同于傳統(tǒng)的話題發(fā)現(xiàn)，傳統(tǒng)的話題檢測（發(fā)現(xiàn)）主要針對的是新聞文章等篇幅較長、表意清楚的文章，一篇文章通常包含一個或幾個話題。而微博的長度普遍較短，少則幾個字、十幾個字，最多也就一百多字。微博短文本的特點主要體現(xiàn)在：①文本表達口語化，不規(guī)則用詞多、網(wǎng)絡(luò)用語多；②文本特征詞少且稀疏，使得特征之間的相關(guān)性難以度量［2］；③文本樣本數(shù)量巨大，分布高度不平衡，少部分的短文本在整體中占有較大比重［2］；④內(nèi)容多樣、隨意性大，不同的用戶可以隨時隨地根據(jù)自己的喜好自行組織語言、自行發(fā)布信息；⑤內(nèi)容碎片化、表意不完整，大部分的微博客文本內(nèi)容都很短小，且發(fā)布者只是簡略的發(fā)表自己的所見所聞或當(dāng)時的感受，沒有對事件進行完整的描述。針對微博客的這些特點，現(xiàn)在有很多話題發(fā)現(xiàn)算法，其中比較經(jīng)典的方法是Single-Pass聚類算法。

2　Single-Pass算法

2.1經(jīng)典的Single-Pass算法

Single-Pass算法是一種增量式的聚類算法，它的主體思想是：首先設(shè)置一個相似度的閾值ε，并把待聚類的文本排好序，然后對于每一個待聚類的文本，和之前各個聚類中的文本進行相似度的比較，如果相似度均小于閾值ε，則增加一個新的聚類且把此文本分配給該聚類；否則把該文本分配給與其相似度最大的聚類。

經(jīng)典的Single-Pass算法存在一些問題：

（1）對文檔的輸入順序敏感，如果先聚類的文檔質(zhì)量不高，含有的話題內(nèi)容不夠豐富，則最終形成該話題的聚類結(jié)果不夠理想。

（2）每個待聚類的文檔要與之前所有已經(jīng)聚類的文檔逐個進行相似度的計算并與閾值ε比較，當(dāng)文檔數(shù)很多時，后期的聚類計算量會很大，效率低下。針對這一問題，孫勝平［3］等引入話題向量來表示話題聚類簇，這樣新來的微博客文本只需和話題向量進行相似度的計算，如果相似度小于閾值則以此微博客文本創(chuàng)建一個新的話題聚類簇，否則把它并入到與它相似度最大的話題聚類簇中，并用該微博客文本更新此話題聚類簇的話題向量。

2.2改進的Single-Pass算法

針對經(jīng)典的Single-Pass算法存在的第一個問題，本文做出如下改進：

由于微博客一般字數(shù)較少，含有的話題信息較少，而字數(shù)較多的微博客含有的話題信息一般比較豐富，因此可以選擇字數(shù)較多微博客文本首先進行聚類形成初始的話題聚類簇，再把剩下的微博客聚類到前面的話題簇中，這樣初始的話題簇含有比較豐富的話題信息，可以大概的表示該話題，減少后續(xù)微博客文本誤分類的可能性。

對于第二個問題，本文采用孫勝平的方法，引入話題向量來表示一個話題簇。

3　基于改進的Single-Pass算法微博客話題發(fā)現(xiàn)

3.1文本預(yù)處理

去掉微博客中對話題表示沒有作用的內(nèi)容，如音頻、視頻、超鏈接、特殊符號，然后對處理后的微博客文本進行詞法分析，這里選用的是中國科學(xué)院計算技術(shù)研究所研制的漢語詞法分析系統(tǒng)NLPIR（又名ICTCLAS2013），它的主要功能包括中文分詞；詞性標(biāo)注；命名實體識別；用戶詞典功能；支持GBK編碼、UTF8編碼、BIG5編碼［4］。對分詞后的文本去掉連詞、代詞、介詞、標(biāo)點符號等對文本意思表達沒有作用的停用詞。

3.2構(gòu)建空間向量模型 （Vector Space Model，VSM）

設(shè)所有待聚類的文本集合為D=｛D1，D2，…，Dn｝，則單個文檔Di可以表示為向量Di，即：

其中，n為所有文檔的經(jīng)過預(yù)處理和停用詞過濾后的詞匯個數(shù)，dij為文檔Di含有的第j個詞，當(dāng)文檔含有該詞時dij=1，不含有該詞時dij=0。

由于在文檔中，不同的詞對文檔內(nèi)容的貢獻度不同，因此需要對詞進行加權(quán)處理，常用的加權(quán)方法有布爾函數(shù)加權(quán)、TF-IWF加權(quán)、歸一化的TF-IDF加權(quán)等。其中用的最多的是歸一化的TF-IDF加權(quán)，本文采用的是這種加權(quán)方法。

TF-IDF（Term Frequency-Inverse Document Frequency），即詞頻-反文檔頻率，詞頻TF表示一個詞在文檔中出現(xiàn)的頻率，反文檔頻率IDF表示詞在整個文檔集中出現(xiàn)的頻率。當(dāng)一個詞在本文檔中出現(xiàn)的次數(shù)較多而在其他文檔中很少出現(xiàn)，則它的TF-IDF值較大，該詞的權(quán)重也較大。

TF的計算公式為：

其中，fim表示文檔Dm中第i個詞出現(xiàn)的次數(shù)，Nm表示Dm中詞的個數(shù)。

IDF的計算公式為：

其中，N表示文檔總數(shù)，Ni表示包含詞i的文檔個數(shù)。

則權(quán)值可表示為：

一般會對詞的TF-IDf作歸一化處理，設(shè)文檔Dm的第i個詞的權(quán)重為wmi，則該詞的歸一化TF-IDF值wmi為：

則經(jīng)過歸一化TF-IDF加權(quán)后的單個文檔Dm可以表示為向量Dm，即：

而兩個文檔之間的相似性，可以用余弦相似度來衡量，記文檔Di，Dj之間的余弦相似度為sim（Di，Dj），則有：

3.3算法執(zhí)行的步驟

基于改進的Single-Pass算法話題發(fā)現(xiàn)的主要思想是：首先對微博客進行文本的預(yù)處理，去掉無用的信息，然后把微博客表示成詞向量形式，運用改進的Single-Pass算法先對內(nèi)容豐富的微博客文本進行聚類再對余下的微博客文本進行聚類，對得到的話題簇向量運用凝聚層次聚類［5］進行最終的聚類，最終得到的聚類結(jié)果即為發(fā)現(xiàn)的話題簇。具體步驟如下：

將微博客經(jīng)文本預(yù)處理后表示為歸一化TF-IDF加權(quán)的空間向量模型。

得到含詞較多的微博客文本向量集，記為S，余下的微博客文本向量集記為T。

對于S中文本向量，設(shè)置一個比較高的相似度閾值ε（為了得到凝聚度高的數(shù)量不太少的話題簇用于凝聚層次聚類），第一個文本向量記為該話題的話題向量，對于后面的文本向量，與之前的話題向量逐一進行比較，如果都小于閾值，則用該向量新建一個話題，否則把其歸為和它相似度最大的聚類簇中，并用此文本向量更新話題向量。直到S中的向量都進行了聚類。

343 耳石復(fù)位聯(lián)合藥物對繼發(fā)性良性陣發(fā)性位置性眩暈患者的應(yīng)用效果 于紅霞，王淑珍，李英杰，武曉玲，郝智軍

對于T，在S聚類結(jié)果的基礎(chǔ)上，用同樣的方法進行聚類。

得到經(jīng)3、4聚類的結(jié)果U=｛u1，u2，…，un｝，其中ui包含聚類的文本向量和表示該聚類簇話題向量。

設(shè)置一個較大的聚類相似度閾值k（為了最終得到幾個話題簇，而不是一個話題簇），進行凝聚層次聚類，對于兩個話題向量，當(dāng)它們的相似度大于k時才聚類，否則不予聚類。得到最終的話題簇。

4　實驗結(jié)果及分析

實驗采用的數(shù)據(jù)集是從BigDataOPC平臺爬取的微博客語料，包括“天津塘沽爆炸”、“導(dǎo)游侮辱游客”、“養(yǎng)老金改革”、“全面開放二胎”、“拐賣兒童入刑”這5個熱點話題各1000條及作為干擾的微博客500條。

實驗采用的性能評價指標(biāo)為準(zhǔn)確率、召回率和F值，各指標(biāo)含義如下所示。

準(zhǔn)確率（Precise）表示聚類算法檢測出來的屬于該話題的的博客數(shù)（A）與該聚類簇所有博客數(shù)（B）的比值，記為P，則：

召回率（Recall）表示聚類算法檢測出來的屬于該話題的的博客數(shù)（A）與屬于該話題的所有博客數(shù)（C）的比值，記為R，則：

F值（F-measures）是準(zhǔn)確率和召回率的調(diào)和平均，計算公式如下：

用原始Single-Pass算法（引入了話題向量）加凝聚層次聚類算法得到的結(jié)果如表1所示，用改進的Single-Pass算法加凝聚層次聚類算法得到的結(jié)果如表2所示。

表1

表2

由結(jié)果可知，經(jīng)過改進后的Single-Pass算法在準(zhǔn)確率、召回率和F值上均優(yōu)于原始的Single-Pass算法，這是由于改進的方法初始的聚類文本含有豐富的話題信息，能夠比較好的建立初始話題，在后續(xù)的微博客文本聚類中能夠減少錯誤聚類的可能性。

5　結(jié)語

本文針對初始聚類的微博客文本可能表示話題能力不足的問題，改進了Single-Pass算法并應(yīng)用到微博客話題發(fā)現(xiàn)中，實驗表明這種改進對微博客話題發(fā)現(xiàn)的性能有一定的的提升。

未來可以針對微博客的特點研究出新的方法來進一步改善話題檢測的精度，同時本文只是根據(jù)微博客中的文本信息進行話題發(fā)現(xiàn)，如何充分利用微博客中的圖片、視頻、社會網(wǎng)絡(luò)關(guān)系來發(fā)現(xiàn)話題是未來一個研究的重點。

［1］彭敏，官宸宇，朱佳暉，等.面向社交媒體文本的話題檢測與追蹤技術(shù)研究綜述［J］.武漢大學(xué)學(xué)報理學(xué)版，2016，3：197-217.

［2］蔣盛益，麥智凱，龐觀松，等.微博信息挖掘技術(shù)研究綜述［J］.圖書情報工作，2012，56（17）：136-142.

［3］孫勝平，張真繼.中文微博客熱點話題檢測與跟蹤技術(shù)研究［D］.北京：北京交通大學(xué)，2011.

［4］NLPIR［EB/OL］.http：//ictclas.nlpir.org/docs.

［5］Pangning T，Steinbach M，Kumar V.數(shù)據(jù)挖掘?qū)д摚跰］.北京：人民郵電出版社，2006.

WeiBo；Single-Pass；Topics；Clustering

Find Weibo Topics Based on the Improved Single-Pass Algorithm

CHEN Long-wen
（College of Computer Science，Sichuan University，Chengu 610065）

Introduces the traditional Single-Pass algorithm in details and analyses its characteristics and disadvantages，and in view of the traditional Single-Pass algorithm is sensitive to the problem of input sequence.In order to solve the problem and improve the accuracy of clustering，proposes an improved method，namely，identifies the topic information rich microblog text to cluster to get the initial cluster result，then clusters the rest of the micro blog text.Topic discovery process：text pretreatment，vector model build，Single-Pass algorithm，hierarchical clustering algorithm has carried on the detailed description.The test shows that the method on the recall ratio and accuracy，F(xiàn) value index is superior to the traditional method.

1007-1423（2016）29-0022-04

10.3969/j.issn.1007-1423.2016.29.005

陳龍穩(wěn)（1990-），男，湖北黃岡人，在讀碩士研究生，研究方向為數(shù)據(jù)挖掘、話題檢測與追蹤

2016-07-19

2016-09-10