程玉勝，黎　康，王一賓，任　勇

(安慶師范大學 計算機與信息學院，安徽 安慶 246133)

?

基于詞項關聯(lián)關系的FCM微博聚類算法

程玉勝，黎康，王一賓，任勇

(安慶師范大學 計算機與信息學院，安徽 安慶 246133)

針對微博內(nèi)容的稀疏、高維等特征，提出了一種基于詞項關聯(lián)關系的模糊C均值聚類算法。該算法通過挖掘詞項間語義的關聯(lián)程度，將文本特征最大化，并用提前標注部分同類文本的方式來指導模糊C均值算法在初始聚類中心上的選擇，從而達到優(yōu)化效果。實驗結果表明，該算法一定程度上克服了微博本身存在的數(shù)據(jù)稀疏性問題，能高效地進行微博聚類。

微博；詞項關聯(lián)關系；模糊聚類

自2009年8月國內(nèi)門戶網(wǎng)站推出微博服務后至2013年上半年，新浪微博和騰訊微博的注冊用戶分別達到了5.36億和5.07億，微博作為一種新型的社交媒體，已經(jīng)被人們廣泛關注。如何從數(shù)量龐大的微博內(nèi)容中得到有用輿情信息，從而權衡利弊，合理利用微博影響力，在輿情研究領域變得至關重要。傳統(tǒng)的人工數(shù)據(jù)處理方法，效率低且不能對微博輿論內(nèi)容的傳播和發(fā)展進行準確及時的監(jiān)測。因此，科學地分析微博數(shù)據(jù)，并對其熱門話題實施追蹤分析，對可能誘發(fā)社會動蕩事件的不良信息進行監(jiān)測和預警，才能推動微博長期健康有序的發(fā)展。

文本表示是實現(xiàn)文本聚類的核心部分。目前常見的文本表示方法是由Salton等人在20世紀70年代提出的向量空間模型[1-2](Vector Space Model，VSM)，用空間中的向量運算來簡化對文本內(nèi)容的處理，而且他用空間上的相似度計算值代替表示語義上的相似度計算值，簡單明了。然而，他認為所有詞之間都是相互獨立存在的，每個關鍵字只能表示一個概念或語義單元，但現(xiàn)實中卻是文檔中會出現(xiàn)許多一詞多義和同義詞的情況，所以這種假設很難解決實際問題；N-gram統(tǒng)計語言模型[3-4]沒有把組成文本的語義單位考慮進來，僅僅把整個文本看作是不同字符組成的字符串，所以在表示包括漢語、阿拉伯語在內(nèi)的各種語言文本文檔時都非常簡單。N-gram模型表示文本本質的是其統(tǒng)計特征，因而它的優(yōu)勢體現(xiàn)在計算機運算和機器學習方面。但N-gram表示有著計算量大、數(shù)據(jù)噪聲大、特征生成復雜等缺點；1958年，IBM公司科學家Luhn提出詞權重經(jīng)典計算方法 TF-IDF[5](Term Frequency-Inversed Docu-ment Frequency)。傳統(tǒng)的聚類方法采用特征向量來表示文本，以詞或短語作為特征，使用TF-IDF方法計算每個特征詞的權重。但由于微博文本非常短，很多詞語在短文本中僅出現(xiàn)一至兩次，TF值基本在1至2左右，使得TF值對TF-IDF的取值影響不大，更多是由IDF決定。而根據(jù)IDF取值規(guī)定，特征詞出現(xiàn)的頻率越高，它的IDF值越小，則整個TF-IDF權重就越小，這與短文本中高頻特征詞往往與主題息息相關相悖。對比傳統(tǒng)文本，微博信息不僅內(nèi)容較短，而且常常不以語法規(guī)則為前提，所以很難從中獲取充足的語義信息來進行相似度計算，另一方面，詞空間的高維、稀疏、多變和相關等特性，也讓文本聚類變得困難重重。

針對以上特點，本文提出一種基于融合詞項關聯(lián)關系[6-7]的模糊C均值聚類算法。該算法通過挖掘微博數(shù)據(jù)內(nèi)部的詞語信息以豐富微博的文本特征來輔助模糊C均值算法[8-11]進行聚類，進而挖掘出微博數(shù)據(jù)中潛在主題和語義信息。

1　詞項關聯(lián)關系

目前主要的短文本處理方法絕大多數(shù)是將特征詞項看作相互獨立的信息進行處理，沒有考慮兩個特征分量間或許具有關聯(lián)關系。但實際情況是文本相似度的計算結果與特征詞項分量間關聯(lián)程度大小有著密不可分的關系。把詞語的內(nèi)聯(lián)關系和外聯(lián)關系加進來，不僅能很好地實現(xiàn)對短文本數(shù)據(jù)降維，還能使短文本的特征信息最大化。

1.1互信息向量

圖1(a)中T1和T2代表不同的文檔，字母A，B，C是T1和T2中的詞項，其中字母B是T1和T2中都有的詞項，右圖顯示的是不同模式下的關聯(lián)詞關系。(b)圖描述的是文檔內(nèi)的詞項關系，(c)圖描述的是不同文檔之間的詞項關系。

(a) (b) (c)

要表示某個詞項fi的分布情況，可以用這個詞項和它所在文本中其余的詞項共現(xiàn)向量fi(w11，w12，…，wij)，其中wij是衡量詞fi和fj相互關聯(lián)程度的互信息?；谠~與其原文檔中其他詞的語義相關性來計算詞項關聯(lián)關系的具體步驟為

(1)

(2)n(fi,fj)是詞項fi和fj同時出現(xiàn)的次數(shù)，這樣就可以用互信息向量表示每個詞項的分布情況。

1.2同一文檔內(nèi)關聯(lián)關系

文檔內(nèi)關聯(lián)關系簡稱內(nèi)聯(lián)關系，定義的是在一篇文檔中兩個詞項之間的關系，如圖1中，T1中有詞fi和fk同時出現(xiàn)，T2中有詞fj和fk同時出現(xiàn)，則認為這兩對詞在其對應的原文檔中存在內(nèi)聯(lián)關系，采用經(jīng)典余弦相似度計算公式如下

(3)

1.3不同文檔間關聯(lián)關系

兩篇文檔中的詞與它們的共有詞一起出現(xiàn)，那么認為這2個詞存在文檔間關聯(lián)關系，簡稱外聯(lián)關系，如圖1中，兩個詞fi和fj，至少存在一個詞fk，讓詞fi和fj同時出現(xiàn)，則認為fi和fj具有外聯(lián)關系，其中詞fk稱為fi和fj的共有詞?？梢杂萌缦鹿接嬎阍~fi和fj的外聯(lián)關系:

Dep(fi,fj/k)=

min{D-Dep(fi,fk),D-Dep(fj,fk)}

(4)因為共有詞往往不止一個，所以需要對fi和fj所有的共有詞求和，然后規(guī)范化到[0，1]區(qū)間:

(5)

從(5)式可知，任意不同詞語間的關系親疏程度與這兩個詞語的共有詞數(shù)量呈正比。又因為加入了所有存在關聯(lián)關系的共有詞對應的文檔，所以外聯(lián)關系要比內(nèi)聯(lián)關系含有更多的語義信息。

目前為止，已經(jīng)挖掘出文檔內(nèi)與文檔間詞語的全部關聯(lián)關系，即

(6)式中，α表示兩種詞項關聯(lián)關系對應的比例，取值范圍為0到1。用以上方法計算獲取的關聯(lián)詞關系既涵蓋了同時出現(xiàn)詞語的互信息，又涵蓋了非同時出現(xiàn)詞語的文檔間關聯(lián)關系，所以其必然可以挖掘出更多的信息。

2　FCM聚類算法

假設樣本空間為X={x1，x2，…，xn}，把它分成m個類，m為正整數(shù)，取值范圍[0，∞]，用模糊矩陣u=(uij)來表示，uij是用來度量第i個樣本屬于第j個類別的排斥性，用cj表示第j個聚類中心點，樣本點xi到聚類中心點cj的歐氏距離用‖xi-cj‖表示，則

(7)

不難看出，排斥性的大小與樣本點到聚類中心的歐式距離呈正比關系，其中

i=1,2,…,n,j=1,2,…,m

(8)

將FCM的目標函數(shù)F(u，C)定義為

(9)

式中b為模糊指數(shù)。很明顯，F(xiàn)值的大小與‖xi-cj‖、uij的值大小呈正比。通過反復修改聚類中心的值，再按照步驟計算F(u，C)，直到得出的結果符合條件。所以，F(xiàn)CM算法的本質是對目標函數(shù)F(u，C)的最小化迭代收斂過程。因為需要反復修改聚類中心值，所以可以將聚類中心點設置為

(10)

聚類結果的模糊程度與b的取值大小呈正比關系，目前還缺乏理論知識對b的取值選擇進行指導，更多的是靠經(jīng)驗。正常情況下b的取值在1.5～2.5之間，有些情況下會直接將b的值賦為2。

3　基于詞項關聯(lián)關系的FCM聚類算法

首先通過互信息將每個詞項表示為它和其他詞項共現(xiàn)向量fi(w11，w12，…，wij)，再根據(jù)詞項關聯(lián)關系公式計算出各詞項所對應的值，通過定義，T-link表示為必屬同類別的詞項，F(xiàn)-link則表示必不屬同類別的詞項，再定義閾值3，計算詞項關聯(lián)關系的值，如果大于3，就認為其必屬同一類別，反之則認為其必不屬同一類別。顯然，同一類詞項具有傳遞效應。

通過詞項關聯(lián)關系計算可以初步確定部分文本的類別信息，此時選取詞項關聯(lián)關系計算時與其他詞項相同類別次數(shù)最多和相異類別次數(shù)最多的詞項其對應的文本作為模糊C均值聚類算法初次選取的聚類中心。

由此確定聚類算法的迭代過程如圖2所示。

圖2　算法流程圖

步驟1分別設定聚類簇數(shù)和模糊指數(shù)b的值；

步驟3把通過步驟2獲得的初始聚類中心代入(9)式中計算目標函數(shù)F(u，C)，再用目前獲得的uij去更新cj，重復本步驟，當F(u，C)的值達到最小，或是已經(jīng)低于提前定義的閾值時，停止計算，輸出結果。

4　實驗結果與分析

4.1數(shù)據(jù)來源

本實驗采用的數(shù)據(jù)取自國內(nèi)新浪微博平臺和國外的Twitter平臺。實驗數(shù)據(jù)采集的是2015年3月-2016年3月大量的微博數(shù)據(jù)，通過熱點話題搜索，分類查找得到在此期間國內(nèi)熱門話題8個，國際熱點話題4個。預處理實驗數(shù)據(jù)：第1步，剔除數(shù)據(jù)文本中的標點符號、表情字符和轉發(fā)鏈接等無效信息；第2步，對文本進行分詞，剔除停用詞、高頻詞和低頻詞后，得本文所需實驗數(shù)據(jù)集合。本文采用的是NLPIR漢語分詞系統(tǒng)，采用的1 028個停用詞是由新浪平臺提供的，得到的數(shù)據(jù)集如表1所示。

表1　實驗所需數(shù)據(jù)信息

4.2實驗結果與分析

為了取證本文方法的實際性能，現(xiàn)將FCM算法，K-means算法和本文算法對同組微博數(shù)據(jù)的聚類結果如表2所示。

表2　聚類情況的對比

為了更為直觀地觀察3種算法對實驗數(shù)據(jù)聚類的結果，將3種算法的準確性與時間消耗結果對應繪制成圖3。

從圖3可以明顯看出，F(xiàn)CM算法不僅存在對數(shù)據(jù)聚類效果差的問題，而且時間消耗較多，相比之下，經(jīng)典的K-means雖然在時間消耗上較少，但是其算法只從文字本身出發(fā)，不考慮詞項間可能存在的關系，因而獲得的詞項矩陣比較稀疏，它的文檔向量也不能準確地描述待測文檔的原始信息，所以算法在準確性上還有待提高。而本文所提算法在考慮了詞語間的互信息的同時，還最大限度發(fā)掘出詞語間的關聯(lián)關系，不僅克服了文本表示中忽略詞語間關系而導致的實驗結果不準確問題，而且在很大程度上降低了原始數(shù)據(jù)的高維稀疏性。因此本文提出的算法優(yōu)于其他的兩種聚類方法。

5　結束語

由于微博在現(xiàn)實生活中扮演的角色越來越重要，所以對微博數(shù)據(jù)的研究分析變得越來越有意義?？紤]實際情況中現(xiàn)有的主要聚類算法很難解決微博數(shù)據(jù)分詞后的詞項矩陣稀疏難題，本文提出了基于融合詞項關聯(lián)關系的FCM聚類算法。該算法克服了微博短文本的高維稀疏問題，通過挖掘詞項上下文關系豐富文本特征，并提前確定聚類中心的方法，減少了算法迭代次數(shù)，并且在聚類精度上取得了不錯的結果，具有較好的性能。但是，本文算法依然存在一定缺陷，在進行詞項關聯(lián)關系計算時，α值是實驗者主觀選取的經(jīng)驗值，還沒能建立一個有效簡潔的標準，這將是下一步研究的問題。

[1]楊玉珍,劉培玉,姜沛佩.向量空間模型中結合句法的文本表示研究[J].計算機工程, 2011, 37(3): 58-60.

[2]彭京, 楊冬青, 唐世渭, 等.一種基于語義內(nèi)積空間模型的文本聚類算法[J].計算機學報, 2007, 30(8): 1354-1363.

[3]秦健. N-gram技術在中文詞法分析中的應用研究 [D]. 青島：中國海洋大學, 2009.

[4]廖祥文,李藝紅. 基于N-gram超核的中文傾向性句子識別[J]. 中文信息學報, 2011, 25(5): 89-100.

[5]黃承慧,印鑒,侯昉.一種結合詞項語義信息和 TF-IDF 方法的文本相似度量方法[J].計算機學報, 2011, 34(5): 856-864.

[6]Mao Yuqing, Kimberly V A, Li Donghui, et al. Corpus Construction for the BioCreative IV GO Task [C]. Proceedings of the 4th BioCreative Challenge Evaluation Workshop, Bethesda, USA: BioCreative Organizing Committee, 2013: 128-138.

[7]馬慧芳,賈美惠子,袁媛,等. 融合詞項關聯(lián)關系的半監(jiān)督微博聚類算法[J]. 計算機工程, 2015, 41(5): 202-212.

[8]Ahmed E B, Nabli A, Gargouri F. Group extraction from professional social network using a new semi-supervised hierarchical clustering[J]. Knowledge and Information Systems, 2014, 40(1):29-47.

[9]Herawan T, Deris M M, Abawajy J H. A rough set approach for selecting clustering attribute[J]. Knowledge-Based Systems, 2010, 23: 220-231.

[10]朱琪,張會福,楊宇波,等. 基于減法聚類的合并最優(yōu)路徑層次聚類算法[J].計算機工程, 2015, 41(6): 178-187.

[11]王丹,吳孟達. 動態(tài)閾值粗糙C均值算法[J]. 計算機科學, 2011, 38(3): 218-242.

Fuzzy C-means Microblog Clustering Based on AlgorithmTerm Correlation Relationship

CHENG Yu-sheng ，LI Kang，WANG Yi-bing，REN Yong

(School of Computer and Information，Anqing Normal University, Anqing, Anhui 246133, China)

Because of feature of quick and easy to operate and strong interactive, micro-blog text has become the bridge and link of modern information communication. At the same time, it is likely to become the hotbed of false information since the supervision system is not perfect. Therefore, it is necessary to strengthen the micro-blog public opinion supervision, analysis and early warning. The paper puts forward a method based on term correlation relationship of fuzzy c-means clustering algorithm, which aiming at the features of sparse and high dimensional. The algorithm maximizes the feature of the text by excavating the relationship between different items. Meanwhile, by means of tagging part of the same text to guide the algorithm of fuzzy c-means to choice it’s clustering center, so as to achieve the effect of optimization. Experimental results show that the algorithm can overcome the sparse of micro-blog to a certain degree, and can clustering efficiently.

micro-blog; term correlation relationship; fuzzy clustering

2016-03-05

安徽省高等學校自然科學基金(KJ2013A177)。

程玉勝，男，安徽桐城人，博士，安慶師范大學計算機與信息學院教授，研究方向為文本挖掘、粗糙集理論等。E-mail: chengysh@aqnu.edu.cn

時間：2016-8-17 11:31

http://www.cnki.net/kcms/detail/34.1150.N.20160817.1131.019.html

TP3

A

1007-4260(2016)03-0068-05

10.13757/j.cnki.cn34-1150/n.2016.03.019