基于改進的Single-Pass算法微博話題發現

陳龍穩

（四川大學計算機學院，成都　610065）

基于改進的Single-Pass算法微博話題發現

陳龍穩

（四川大學計算機學院，成都610065）

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

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

0　引言

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

1　微博客的特點

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

2　Single-Pass算法

2.1經典的Single-Pass算法

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

經典的Single-Pass算法存在一些問題：

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

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

2.2改進的Single-Pass算法

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

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

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

3　基于改進的Single-Pass算法微博客話題發現

3.1文本預處理

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

3.2構建空間向量模型 （Vector Space Model，VSM）

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

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

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

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

TF的計算公式為：

其中，fim表示文檔Dm中第i個詞出現的次數，Nm表示Dm中詞的個數。

IDF的計算公式為：

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

則權值可表示為：

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

則經過歸一化TF-IDF加權后的單個文檔Dm可以表示為向量Dm，即：

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

3.3算法執行的步驟

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

將微博客經文本預處理后表示為歸一化TF-IDF加權的空間向量模型。

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

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

343 耳石復位聯合藥物對繼發性良性陣發性位置性眩暈患者的應用效果 于紅霞，王淑珍，李英杰，武曉玲，郝智軍

對于T，在S聚類結果的基礎上，用同樣的方法進行聚類。

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

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

4　實驗結果及分析

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

實驗采用的性能評價指標為準確率、召回率和F值，各指標含義如下所示。

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

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

F值（F-measures）是準確率和召回率的調和平均，計算公式如下：

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

表1

表2

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

5　結語

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

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

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

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

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

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

［5］Pangning T，Steinbach M，Kumar V.數據挖掘導論［M］.北京：人民郵電出版社，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 value index is superior to the traditional method.

1007-1423（2016）29-0022-04

10.3969/j.issn.1007-1423.2016.29.005

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

2016-07-19

2016-09-10