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

葉瑾玫 程 科

（江蘇科技大學計算機學院 鎮江 212003）

1 引言

隨著互聯網的高速發展，互聯網已經成為了人們工作和生活中非常重要的一部分。同時，互聯網上的信息量也在不斷的增長，甚至出現了信息的“大爆炸”。當今的互聯網包含著各種各樣的信息，網絡輿情（Public Opinion）是其中非常重要的一種。

特別是微博的興起，對企業網絡輿情以及社會事件的發展趨勢產生著巨大的影響力，作為互聯網中的一種新媒體［1］，企業將其運用到營銷活動、產品或其他企業信息發布等管理活動中，同時也能夠讓消費者隨時隨地收聽企業微博“直播”，對促進社會的經濟建設具有極其重要的意義。

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

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

2 改進的FSDPC算法

2.1 FSDPC算法

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

dij表示兩點i和j之間的歐式距離，dc＞0為截斷距離，每個數據點與之距離不超過dc的點數目大概占數據點總數的2%。

δi與比自己局部密度更高的點的距離定義為

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

計算出各點的ρi和δi值后，根據ρi和δi值生成決策圖，如圖1所示。

圖1 決策圖

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

2.2 改進的FSDPC算法

在上述局部密度的計算公式中，截斷距離dc參數需要手動設置這一缺陷直接影響了初始中心選取結果，即使將閾值定為選取數據對象的2%，但該算法的魯棒性依然較弱，本文介紹基于相鄰元素最大差值dc選取法。

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

圖2 截斷距離示意圖

對于離群點，從圖3中可以看出離群點與簇內數據點同樣有著最大差值，即dij=M，di(j+1)=N，則理想的截斷距離為

將各個數據對象的截斷距離組成集合D={dc1，dc2，…，dcn}，該集合中包含有數據群臨界點以及孤立點的截斷距離，為避免受到這些噪聲點的影響，dc應取集合D中擁有最小截斷距離的數據對象值，即dc=min(D)。

3 改進的k-means算法

3.1 K-means算法

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

K-means算法實現過程：

1）從樣本集中隨機指定k個點作為初始類簇中心；

3）重新計算每個集合的中心點；

4）新計算出來的中心點位置變化不大，趨于穩定，則聚類結束，反之循環上述步驟2）和3）。

3.2 改進的K-means聚類

將改進的FSDPC算法獲取到的初始聚類簇中心在K-means算法中進行迭代，得到最終的微博聚類結果。實現過程如表1所示。

表1 聚類實現過程

4 實驗過程與結果分析

4.1 實驗過程設計

為驗證改進后的算法在聚類效果上的優越性，分別用傳統的K-means算法和本文基于密度峰值優化后的K-means算法應用于微博輿情分析實驗中，然后根據實驗結果對比分析，輿情分析應用的數據集情況見表2。

表2 實驗數據集

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

4.2 實驗結果分析

本文采用F度量值作為聚類結果的評價標準。該方法結合了精確率（P）和召回率（R）兩個指標，P和R分別由下面的計算公式得到［12］：

其中，TP為檢索到的相關文本，即聚類的正確文檔數，FP為聚類到的不正確的文本數，FN為未聚類到的正確的文本數，TP+FP表示所有相關的文本數，即聚類到的所有正確的文本總數，TP+FN表示用來聚類的文本總數。引出F度量值來綜合精確率和召回率兩個指標，度量值計算公式為

本文提出的算法和傳統的K-means算法相比較，在F度量值和迭代次數上均有明顯變化，實驗結果如表3，表4所示。

表3 傳統的K-means算法的聚類結果

表4 本文算法的聚類結果

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

5 結語

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