謝修娟 ，李香菊，莫凌飛

(1.東南大學成賢學院計算機工程系，江蘇 南京 210000;2.東南大學儀器科學與工程學院，江蘇 南京 210000)

1 引言

隨著媒體技術的不斷進步和信息傳播渠道的日趨多元化，當今社會進入了“人人都是新聞傳播者”的自媒體時代。廣大網民參與言論的熱情高漲，特別是微博的興起，網民可以通過電腦、手機隨時隨地發(fā)表言論。新浪微博——Twitter[1]類的新興網絡應用，自2009年推出，截至目前，注冊用戶已超過5億，月活躍用戶數(shù)約為2億，用戶每日發(fā)博量突破1億條[2]。可見，微博上的輿論已成為網絡輿情中極具影響力的一種。如何從海量數(shù)據(jù)中快速有效地發(fā)現(xiàn)網民關注的熱門話題？從而引導政府相關部門及時捕捉微博中敏感的輿論信息，合理地控制負面輿論的擴散。目前，很多政府機關采用全人工或是半自動的監(jiān)測統(tǒng)計方法，效率低，準確度也低[3,4]。因此，迫切需要一種更為有效的微博熱點話題發(fā)現(xiàn)方法。

K-means[5]是一種最為經典、使用最為廣泛的劃分聚類算法，經常被用于網絡輿情的聚類中。但是，其使用有一定的局限性[6 - 8]:(1)需要事先確定聚類數(shù)；(2)初始聚類中心的選擇方法不一，選取不當，往往導致最終聚類結果陷入局部最優(yōu)。針對上述情況，研究者從不同角度提出一系列改進的K-means算法，文獻[9]利用文檔標題的稀疏相似度，確定K-means算法的初始聚類中心；文獻[10]提出用凝聚的層次算法干預K-means算法的隨機選取聚類中心的方式，保證最終的初始聚類中心更具有典型性；文獻[11]提出使用二分思想遞歸分裂相似度大于給定閾值的簇，合并相似度小于閾值的簇，來獲得聚類簇數(shù)。

本文提出一種基于密度的K-means聚類算法，對傳統(tǒng)的K-means初始聚類中心選擇方法進行改進，并將改進后的算法用于新浪微博的聚類中，以期能更快、更準確地對最近的微博數(shù)據(jù)進行聚類，以便發(fā)現(xiàn)微博熱門話題。

2 相關的定義

定義1微博文檔的表示：采用空間向量模型VSM(Vector Space Model)，bi=(w1(bi)，w2(bi)，… ，wj(bi)，… ，wn(bi))，wj(bi)表示第j個特征項在微博文檔bi中的權重，本文權重計算采用TF-IDF方法，w=tf×idf，tf指特征項在某微博文檔bi中出現(xiàn)的次數(shù)，idf是特征項在微博文檔集bi中出現(xiàn)頻率的量化。為了降低高頻特征項對其它中低頻特征項的抑制作用，需要對特征向量進行歸一化處理，處理后的權重計算公式如下：

其中，tfj(bi)是指第j個特征項在bi中出現(xiàn)的次數(shù)，N是所有微博文檔的個數(shù)，nj表示包含第j個特征項的微博文檔的個數(shù)，n是bi中特征項的總個數(shù)，分母為歸一化因子。

定義2兩個微博文檔bi和bj之間的相似度similarity(bi,bj) 定義為兩個向量對象在狀態(tài)空間方向上正交的可能性，用這兩個向量的夾角余弦cosθij表示，若完全正交，表示兩文檔毫無相似性，點積為0。夾角余弦cosθij采用如下的計算公式：

其中，bik、bjk分別表示文檔bi和bj第k個特征項的權值，1≤k≤N。

其中，E表示所有聚類文檔的誤差平方和，x是聚類簇cj中某個聚類文檔，mi是每個聚類簇cj內所有聚類文檔的均值。

定義4密度density：給定文檔集合BL，b∈BL，文檔b的密度定義為該文檔與其它文檔的平均相似度，采用如下的計算公式：

density(b)=∑x∈BLsimilarity(x,b)/NBL

其中，分子是文檔b與其它文檔兩兩間的相似度之和，分母是BL所包含的文檔數(shù)。

定義5核心文檔：若文檔b的密度大于或等于給定參考值refSimilarity(大于0)，則該文檔是核心文檔,refSimilarity稱為密度閾值。

通過計算密度得到核心文檔，能有效地規(guī)避噪聲文檔，避免初始聚類中心取到孤立點而導致聚類結果陷入局部最優(yōu)。采用反證法：假設噪聲點是核心文檔，而其與各個文檔間極不相似，根據(jù)定義2和定義3,噪聲文檔的密度約為0，這與核心文檔的定義相沖突，因此，核心文檔不可能是噪聲文檔。

3 改進的K-means聚類算法

3.1 基于密度思想的初始聚類簇中心選擇算法

借鑒DBSCAN密度聚類思想，本文提出一種初始聚類簇中心選擇算法InitialCenters，首先找出所有核心微博文檔，選取K個相互間最不相似的核心文檔作為初始聚類中心。

InitialCenters算法流程描述如下：

輸入：微博文檔集合blogList={b1,b2,…,bn}；聚類簇數(shù)K；密度閾值refSimilarity。

輸出：初始聚類簇中心centers={c1,c2,…,cK}。

Step1對于給定的微博文檔集合blogList，求出任意兩個文檔間的相似度，保存至相似度矩陣docSimilarity中；

Step2根據(jù)相似度矩陣docSimilarity，計算每一個文檔與其它文檔兩兩之間的平均相似度，找出平均相似度高于密度閾值的文檔，形成核心文檔集合coreDocs；

Step3將coreDocs中的第一個核心文檔作為第一個初始聚類中心點centers[1]，并從coreDocs刪除該文檔，令計數(shù)變量nk=1，同時，將centers[1]置為當前聚類中心點；

Step4遍歷coreDocs剩余核心文檔，選擇與當前聚類中心點最不相似的文檔作為下一個初始聚類中心點，添加到centers中，并從coreDocs刪除該文檔；

Step5更新當前聚類中心點，并使nk=nk+1，轉Step 4；

Step6重復Step 4和Step 5，直至nk與聚類簇數(shù)K值相等為止，輸出centers，算法結束。

3.2 改進的K-means聚類算法

將InitialCenters算法所得到的初始聚類簇中心，再按照傳統(tǒng)的K-means算法重復迭代，得到最終的微博數(shù)據(jù)聚類結果。

給定微博文檔集合blogList={b1,b2,…,bn}，初始聚類簇中心點集合centers={c1,c2,…,cK}，初始化聚類簇clusters={clu1,clu2,…,cluK}，K為聚類數(shù)。

其具體步驟如下：

Step1計算每個微博文檔bi與每個初始聚類簇中心點的相似度，并將bi歸入到與其最相似的簇clusters中；

Step3重復迭代Step 1和 Step 2，直到準則函數(shù)E收斂；

Step4輸出最終聚類結果。

4 實驗過程與結果分析

4.1 實驗過程設計

本文將使用相同的數(shù)據(jù)源對傳統(tǒng)的K-means算法以及改進后的K-means算法進行對比實驗，以驗證本文提出的改進算法在聚類效果上的優(yōu)越性。

首先構建了一個抓取新浪微博的API，選取一些時下比較熱門、關注度高的詞條作為關鍵詞抓取數(shù)據(jù)。本實驗分別以“春晚”“逼婚”“羋月傳”“環(huán)衛(wèi)工”為關鍵詞抓取了每個類別最近發(fā)表的1 000條微博數(shù)據(jù)，為保證數(shù)據(jù)的有效性，經人工過濾，從每個類中選取200條字符長度在15以上的微博，共計800條數(shù)據(jù)，作為此次實驗的訓練測試集。采用中國科學院ICTCLAS分詞系統(tǒng)對微博數(shù)據(jù)進行分詞、詞性標注處理，并借助停用詞表對分詞結果中的詞匯進行停用詞過濾，而后使用定義1提及的TF-IDF方法構造微博數(shù)據(jù)的向量空間模型(VSM特征項矩陣)，來實現(xiàn)微博文本聚類。

4.2 實驗結果分析

本文采用F度量值[12]作為聚類結果的評價標準。該方法同時兼顧了查準率(P)和查全率(R)兩個指標，P和R分別由下面的計算公式得到。

P=TP/(TP+FP)

R=TP/(TP+FN)

其中，TP為正類被劃分為正類的文檔數(shù)，即聚類的正確文檔數(shù)，F(xiàn)P為負類被劃分為正類的文檔數(shù)，F(xiàn)N為正類被劃分為負類的文檔數(shù)，TP+FP表示實際分類的文檔數(shù)，TP+FN表示應有的文檔數(shù)。

為更客觀地評價聚類性能，本研究對傳統(tǒng)的算法進行多次隨機選擇初始聚類中心完成聚類，對本文提出的初始中心選擇算法，也是選取了多個密度閾值進行聚類，分別取各自最佳的一次結果。參數(shù)的取值情況為：傳統(tǒng)的K-means算法，初始聚類中心為(3,102,456,617)，改進后的K-means算法密度參考值為0.036 25。表1是傳統(tǒng)的K-means算法與改進后的K-means算法的F值的實驗結果。

Table 1 F value comparison between the traditional K-meansalgorithm and the improved K-means algorithm

從表1中不難發(fā)現(xiàn)，改進后的聚類算法F值相對比較穩(wěn)定，而不像傳統(tǒng)算法F值上下波動比較大，此外，改進后的算法總體的聚類準確度有所提高，表1中，除了“逼婚”這一類別偏低，其它三類都比傳統(tǒng)算法的F值高。可見，運用改進后的K-means算法對四個關鍵詞近4 000條的微博數(shù)據(jù)進行聚類，所得到的聚類簇基本與事實數(shù)據(jù)一致，從每個簇中的特征項可以很快獲得輿論關注的熱點，以“春晚”為例，最近討論比較多的是“六小齡童”“春晚主持人”“春晚吉祥物”“節(jié)目單”等，其中“六小齡童”熱度最高。

再者是運行時間，雖然改進后的算法在計算初始聚類中心時有一定時間消耗，但是從幾次實驗來看，聚類過程中的迭代次數(shù)少了，因此最終的運行時間成本反而降低了。為驗證改進算法的時間效率，在傳統(tǒng)算法以及改進算法的多次實驗中，分別選取具有代表性的四次聚類時間進行比較，圖1直觀地顯示了改進后的算法在運行時間上所表現(xiàn)出的優(yōu)越性。

可見，改進后的K-means算法不僅提高了微博聚類的正確性、穩(wěn)定性，而且提高了運行效率，運用改進的K-means算法對一段時間內的微博數(shù)據(jù)進行聚類，能夠快速、準確地發(fā)現(xiàn)輿情熱點話題。

Figure 1 Comparation of time t圖1 時間t值的比較

5 結束語

本文借鑒了密度聚類算法DBSCAN的思想，對K-means的初始聚類中心選擇方法進行優(yōu)化，提出在平均相似度較高的核心文檔中找出相互間最不相似的文檔作為初始聚類中心，以消除初始聚類中心選取到孤立點可能導致聚類結果陷入局部最優(yōu)的不良影響，并將改進后的算法應用于微博數(shù)據(jù)的聚類中。實驗結果表明，改進后的算法在聚類的準確性和時間效率方面都有一定的優(yōu)勢，可以用其對微博數(shù)據(jù)進行聚類分析，以發(fā)現(xiàn)一段時間內的微博輿情熱點。

[1] Yu L L,Asur S,Huberman B A.Trend dynamics and attention in Chinese social media[J].American Behavioral Scientist,2015,59 (9):1142-1156.

[2] Wei Yang.Enterprise negative network public opinion propagation characteristic research based on the sina weibo[D].Hefei:Anhui University,2013.(in Chinese)

[3] Yi Chen-he.Emergency evolution law of network public opinion and government monitoring[D].Xiangtan:Xiangtan University,2014.(in Chinese)

[4] Zhang Li-juan.The countermeasure research of network public opinion guide of the local government[J].China Management Informationization,2015,18(18):203-204.(in Chinese)

[5] Takens F. Determing strange attractors in turbulence[M]∥Lecture Notes in Mathematics.Berlin:Springer Berlin Heideberg,1981:339-359.

[6] Yuan Fang,Zhou Zhi-yong,Song Xin.K-means clustering algorithm with meliorated initial center[J].Computer Engineering,2007,33(3):65-66.(in Chinese)

[7] Tang Xiao-qin,Dai Ru-yuan.Technique of cluster analysis in data mining[J].Microcomputer Information,2003,19(1):3-4.(in Chinese)

[8] Yang Zun-qi, Zhang Qian-nan.Research on attention of microblog users based onK-means cluster analysis[J].Journal of Intelligence,2013,32(8):142-144.(in Chinese)

[9] Tang Han-qing,Wang Han-jun.Application of improvedK-means algorithm to analysis of online public opinions[J].Computer Systems & Applications,2011,20(3):165-168.(in Chinese)

[10] Luo Hui-xia, Qu Xiao-ling.The improvement ofK-means clustering algorithm based on internet public opinion[J].Computer Development & Applications,2010,23(8):4-6.(in Chinese)

[11] Zhang Zhong-ping, Wang Ai-jie,Chai Xu-guang.Easy and efficient algorithm to determine number of clusters[J].Computer Engineering and Applications,2009,45(15):166-168.(in Chinese)

[12] Zhong Jiang,Liu Rong-hui.Improved KNN text categorization[J].Computer Engineering and Applications,2012,48(2):142-144.(in Chinese)

附中文參考文獻：

[2] 魏楊.基于新浪微博的企業(yè)負面網絡輿情傳播特征研究[D].合肥：安徽大學,2013.

[3] 易臣何.突發(fā)事件網絡輿情的演化規(guī)律與政府監(jiān)控[D].湘潭:湘潭大學,2014.

[4] 張李娟.地方政府網絡輿情引導的對策研究[J].中國管理信息化,2015,18(18):203-204.

[6] 袁方,周志勇,宋鑫.初始聚類中心優(yōu)化的K-means算法[J].計算機工程,2007,33(3):65-66.

[7] 湯效琴,戴汝源.數(shù)據(jù)挖掘中聚類分析的技術方法[J].微計算機信息,2003,19(1):3-4.

[8] 楊尊琦,張倩楠.基于K-means算法的微博用戶推薦功能研究[J].情報雜志,2013,32(8):142-144.

[9] 湯寒青,王漢軍.改進的K-means算法在網絡輿情分析中的應用[J].計算機系統(tǒng)應用,2011,20(3):165-168.

[10] 羅暉霞,曲曉玲.基于網絡輿情的K-Means算法的改進研究[J].電腦開發(fā)與應用,2010,23(8):4-6.

[11] 張忠平，王愛杰，柴旭光.簡單有效的確定聚類數(shù)目算法[J].計算機工程與應用,2009,45(15):166-168.

[12] 鐘將，劉榮輝.一種改進的KNN文本分類[J].計算機工程與應用,2012,48(2):142-144.