基于密度峰值優(yōu)化K-means聚類算法的微博輿情分析*

葉瑾玫 程 科

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

隨著互聯(lián)網(wǎng)的高速發(fā)展，互聯(lián)網(wǎng)已經(jīng)成為了人們工作和生活中非常重要的一部分。同時(shí)，互聯(lián)網(wǎng)上的信息量也在不斷的增長(zhǎng)，甚至出現(xiàn)了信息的“大爆炸”。當(dāng)今的互聯(lián)網(wǎng)包含著各種各樣的信息，網(wǎng)絡(luò)輿情（Public Opinion）是其中非常重要的一種。

特別是微博的興起，對(duì)企業(yè)網(wǎng)絡(luò)輿情以及社會(huì)事件的發(fā)展趨勢(shì)產(chǎn)生著巨大的影響力，作為互聯(lián)網(wǎng)中的一種新媒體［1］，企業(yè)將其運(yùn)用到營(yíng)銷活動(dòng)、產(chǎn)品或其他企業(yè)信息發(fā)布等管理活動(dòng)中，同時(shí)也能夠讓消費(fèi)者隨時(shí)隨地收聽企業(yè)微博“直播”，對(duì)促進(jìn)社會(huì)的經(jīng)濟(jì)建設(shè)具有極其重要的意義。

聚類分析是基于相似性的思想，指將相似度較高的數(shù)據(jù)對(duì)象劃分為同一類簇，不同類別之間相似度較低的分析過程，通常又被稱為無監(jiān)督學(xué)習(xí)［2］，與監(jiān)督學(xué)習(xí)不同的是，在群集中沒有指示數(shù)據(jù)類型的分類或者分組信息。現(xiàn)階段的聚類算法中，最常用的有一下幾種［3］：基于密度的聚類、基于網(wǎng)格的聚類、基于層次的聚類、基于劃分的聚類。

K-means作為一種最經(jīng)典、使用場(chǎng)景最廣泛的一種基于劃分的聚類算法［4］，主要用于網(wǎng)絡(luò)輿情的聚類分析。然而，該算法存在一些缺陷，隨機(jī)選取的k個(gè)聚類中心點(diǎn)導(dǎo)致結(jié)果有很大的隨機(jī)性，聚類結(jié)果很大程度上取決于一開始選取的位置，不能保證全局最優(yōu)。針對(duì)上述情況，研究者圍繞K-means算法展開了各種研究，加以改進(jìn)算法缺點(diǎn)。文獻(xiàn)［5］提出基于直方圖方法從空間上劃分樣本數(shù)據(jù)，憑借數(shù)據(jù)分散布局具有本身一定的特色來找出初始類簇中心；文獻(xiàn)［6］提出依據(jù)每個(gè)樣本對(duì)象與類中心點(diǎn)的距離與之輪廓系數(shù)自適應(yīng)地選擇高質(zhì)量樣本來確定初始聚類中心；文獻(xiàn)［7］生成樣本的初始中心是利用密度敏感的相似性度量計(jì)算出對(duì)象的密度，該中心的生成具有啟發(fā)性，以均衡化函數(shù)為基則確定K值。本文根據(jù)每個(gè)數(shù)據(jù)對(duì)象的密度分布來選擇峰值密度較高的對(duì)象作為初始類中心點(diǎn)，并以初始中心數(shù)來確定類別數(shù)，使用選定的初始聚類中心進(jìn)行聚類，提高數(shù)據(jù)分析的準(zhǔn)確性、快速性，彌補(bǔ)了K-means算法選擇初始聚類中心和類別數(shù)目的缺陷，且使得算法迭代次數(shù)大大減少。

2 改進(jìn)的FSDPC算法

2.1 FSDPC算法

FSDPC算法是由Alex Rodriguez和Alessandro Laio于2014年提出，并將論文《Clustering by fast search and find ofdensity peaks》發(fā) 表 在Science［8］上。主要思想是尋找被低密度區(qū)域分離的高密度區(qū)域，類簇中心點(diǎn)的密度大于周圍鄰居點(diǎn)的密度并且類簇中心點(diǎn)與更高密度點(diǎn)之間的距離相對(duì)較大。因此，F(xiàn)SDPC算法主要有兩個(gè)需要計(jì)算的量：局部密度ρi和相對(duì)最小距離δi（與局部密度更大的樣本點(diǎn)之間的最小距離）［9］。這兩個(gè)量都與點(diǎn)之間的距離dij相關(guān)。對(duì)于點(diǎn)的局部密度ρi定義方式有兩種：

dij表示兩點(diǎn)i和j之間的歐式距離，dc＞0為截?cái)嗑嚯x，每個(gè)數(shù)據(jù)點(diǎn)與之距離不超過dc的點(diǎn)數(shù)目大概占數(shù)據(jù)點(diǎn)總數(shù)的2%。

δi與比自己局部密度更高的點(diǎn)的距離定義為

δi是具有最高局部密度的點(diǎn)與所有其他點(diǎn)之間的距離的最大值。定義為

計(jì)算出各點(diǎn)的ρi和δi值后，根據(jù)ρi和δi值生成決策圖，如圖1所示。

圖1 決策圖

從決策圖中可以選出具有較大局部密度ρi值和較大距離δi值，γi=ρi*δi，γi按從大到小進(jìn)行排序，γi的值越大則數(shù)據(jù)點(diǎn)越有可能為聚類中心［10］。

2.2 改進(jìn)的FSDPC算法

在上述局部密度的計(jì)算公式中，截?cái)嗑嚯xdc參數(shù)需要手動(dòng)設(shè)置這一缺陷直接影響了初始中心選取結(jié)果，即使將閾值定為選取數(shù)據(jù)對(duì)象的2%，但該算法的魯棒性依然較弱，本文介紹基于相鄰元素最大差值dc選取法。

計(jì)算出數(shù)據(jù)對(duì)象間的歐氏距離按升序進(jìn)行排序，獲取到距離集合di={di1，di2，…，din}(i=1，2，…，n)，由圖2可以看出，在同一個(gè)簇中數(shù)據(jù)點(diǎn)到數(shù)據(jù)對(duì)象i的距離較小，而另一個(gè)簇中的數(shù)據(jù)點(diǎn)到i的距離差距較大，這時(shí)距離集合可以設(shè)為di={di1，di2，…，dij，di(j+1)，…，din}(j=1，2，…，n;i≠j)，其中，dij=M，di(j+1)=L。M和L兩個(gè)相鄰的元素之間有著最大差值，則理想的截?cái)嗑嚯xdci可以定義為

圖2 截?cái)嗑嚯x示意圖

對(duì)于離群點(diǎn)，從圖3中可以看出離群點(diǎn)與簇內(nèi)數(shù)據(jù)點(diǎn)同樣有著最大差值，即dij=M，di(j+1)=N，則理想的截?cái)嗑嚯x為

將各個(gè)數(shù)據(jù)對(duì)象的截?cái)嗑嚯x組成集合D={dc1，dc2，…，dcn}，該集合中包含有數(shù)據(jù)群臨界點(diǎn)以及孤立點(diǎn)的截?cái)嗑嚯x，為避免受到這些噪聲點(diǎn)的影響，dc應(yīng)取集合D中擁有最小截?cái)嗑嚯x的數(shù)據(jù)對(duì)象值，即dc=min(D)。

3 改進(jìn)的k-means算法

3.1 K-means算法

K-means算法的思想很簡(jiǎn)單，把給定的樣本集按照樣本之間的距離大小劃分開來，取k個(gè)類簇和k個(gè)初始中心，將數(shù)據(jù)樣本點(diǎn)分配到與之距離最近的類簇中，以保證各簇中數(shù)據(jù)對(duì)象與簇中心的距離之差的平方總和最小，簇和簇之間的距離盡量拉大［11］，數(shù)據(jù)對(duì)象間的相似程度以歐式距離為準(zhǔn)則，采用方差作為目標(biāo)函數(shù)，其定義為

K-means算法實(shí)現(xiàn)過程：

1）從樣本集中隨機(jī)指定k個(gè)點(diǎn)作為初始類簇中心；

3）重新計(jì)算每個(gè)集合的中心點(diǎn)；

4）新計(jì)算出來的中心點(diǎn)位置變化不大，趨于穩(wěn)定，則聚類結(jié)束，反之循環(huán)上述步驟2）和3）。

3.2 改進(jìn)的K-means聚類

將改進(jìn)的FSDPC算法獲取到的初始聚類簇中心在K-means算法中進(jìn)行迭代，得到最終的微博聚類結(jié)果。實(shí)現(xiàn)過程如表1所示。

表1 聚類實(shí)現(xiàn)過程

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

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

為驗(yàn)證改進(jìn)后的算法在聚類效果上的優(yōu)越性，分別用傳統(tǒng)的K-means算法和本文基于密度峰值優(yōu)化后的K-means算法應(yīng)用于微博輿情分析實(shí)驗(yàn)中，然后根據(jù)實(shí)驗(yàn)結(jié)果對(duì)比分析，輿情分析應(yīng)用的數(shù)據(jù)集情況見表2。

表2 實(shí)驗(yàn)數(shù)據(jù)集

輿情采集的爬取腳本用JavaScript語言編寫，以微博中討論較多，比較熱門的話題作為關(guān)鍵詞抓取數(shù)據(jù)。然后對(duì)文本集預(yù)處理，利用分詞系統(tǒng)ICTCLAS對(duì)微博文檔進(jìn)行分詞、搜集停用詞表過濾掉已經(jīng)淘汰的詞語，建立微博文本的向量空間模型（Vector Space Model，VSM），使用向量空間信息檢索范例提出的文本特征計(jì)算方法TF-IDF（詞頻-逆文檔頻率）來計(jì)算權(quán)重。

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

本文采用F度量值作為聚類結(jié)果的評(píng)價(jià)標(biāo)準(zhǔn)。該方法結(jié)合了精確率（P）和召回率（R）兩個(gè)指標(biāo)，P和R分別由下面的計(jì)算公式得到［12］：

其中，TP為檢索到的相關(guān)文本，即聚類的正確文檔數(shù)，F(xiàn)P為聚類到的不正確的文本數(shù)，F(xiàn)N為未聚類到的正確的文本數(shù)，TP+FP表示所有相關(guān)的文本數(shù)，即聚類到的所有正確的文本總數(shù)，TP+FN表示用來聚類的文本總數(shù)。引出F度量值來綜合精確率和召回率兩個(gè)指標(biāo)，度量值計(jì)算公式為

本文提出的算法和傳統(tǒng)的K-means算法相比較，在F度量值和迭代次數(shù)上均有明顯變化，實(shí)驗(yàn)結(jié)果如表3，表4所示。

表3 傳統(tǒng)的K-means算法的聚類結(jié)果

表4 本文算法的聚類結(jié)果

從表3，表4的結(jié)果對(duì)比可以看出，改進(jìn)后的算法聚類效果對(duì)比傳統(tǒng)的K-means算法，雖然有一類別F值稍稍偏低，但其他三類都明顯高于傳統(tǒng)K-means算法，在迭代次數(shù)上，改進(jìn)后的算法明顯要少于傳統(tǒng)的K-means算法，從而證明改進(jìn)后的算法減少了聚類時(shí)間。由此可見，改進(jìn)后的K-means算法微博聚類分析上具有更高的準(zhǔn)確度，而且保證了分析結(jié)果的穩(wěn)定性，提高了在輿情分析過程中的效率，在輿情熱點(diǎn)話題上具有更好的挖掘效果。

5 結(jié)語

本文主要對(duì)微博不同類別的輿情進(jìn)行聚類分析，為了提高聚類效果，克服K-means算法隨機(jī)選取初始聚類中心的缺陷，引入密度峰值算法，并對(duì)其相關(guān)參數(shù)進(jìn)行優(yōu)化，在一定程度上提升了聚類算法的全局搜索能力，更加準(zhǔn)確、高效地對(duì)微博輿情進(jìn)行聚類分析。聚類結(jié)果表明，密度峰值優(yōu)化后的K-means算法具有更好的聚類效果，能夠更加精確地挖掘出微博的熱點(diǎn)話題。