謝修娟 ，李香菊，莫凌飛

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

1 引言

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

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

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

2 相關(guān)的定義

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

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

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

其中，bik、bjk分別表示文檔bi和bj第k個(gè)特征項(xiàng)的權(quán)值，1≤k≤N。

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

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

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

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

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

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

3 改進(jìn)的K-means聚類(lèi)算法

3.1 基于密度思想的初始聚類(lèi)簇中心選擇算法

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

InitialCenters算法流程描述如下：

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

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

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

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

Step3將coreDocs中的第一個(gè)核心文檔作為第一個(gè)初始聚類(lèi)中心點(diǎn)centers[1]，并從coreDocs刪除該文檔，令計(jì)數(shù)變量nk=1，同時(shí)，將centers[1]置為當(dāng)前聚類(lèi)中心點(diǎn)；

Step4遍歷coreDocs剩余核心文檔，選擇與當(dāng)前聚類(lèi)中心點(diǎn)最不相似的文檔作為下一個(gè)初始聚類(lèi)中心點(diǎn)，添加到centers中，并從coreDocs刪除該文檔；

Step5更新當(dāng)前聚類(lèi)中心點(diǎn)，并使nk=nk+1，轉(zhuǎn)Step 4；

Step6重復(fù)Step 4和Step 5，直至nk與聚類(lèi)簇?cái)?shù)K值相等為止，輸出centers，算法結(jié)束。

3.2 改進(jìn)的K-means聚類(lèi)算法

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

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

其具體步驟如下：

Step1計(jì)算每個(gè)微博文檔bi與每個(gè)初始聚類(lèi)簇中心點(diǎn)的相似度，并將bi歸入到與其最相似的簇clusters中；

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

Step4輸出最終聚類(lèi)結(jié)果。

4 實(shí)驗(yàn)過(guò)程與結(jié)果分析

4.1 實(shí)驗(yàn)過(guò)程設(shè)計(jì)

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

本文采用F度量值[12]作為聚類(lèi)結(jié)果的評(píng)價(jià)標(biāo)準(zhǔn)。該方法同時(shí)兼顧了查準(zhǔn)率(P)和查全率(R)兩個(gè)指標(biāo)，P和R分別由下面的計(jì)算公式得到。

P=TP/(TP+FP)

R=TP/(TP+FN)

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

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

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

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

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

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

Figure 1 Comparation of time t圖1 時(shí)間t值的比較

5 結(jié)束語(yǔ)

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

附中文參考文獻(xiàn)：

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

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

[4] 張李娟.地方政府網(wǎng)絡(luò)輿情引導(dǎo)的對(duì)策研究[J].中國(guó)管理信息化,2015,18(18):203-204.

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

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

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

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

[10] 羅暉霞,曲曉玲.基于網(wǎng)絡(luò)輿情的K-Means算法的改進(jìn)研究[J].電腦開(kāi)發(fā)與應(yīng)用,2010,23(8):4-6.

[11] 張忠平，王愛(ài)杰，柴旭光.簡(jiǎn)單有效的確定聚類(lèi)數(shù)目算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(15):166-168.

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