基于改進K-means 算法的微平臺輿情分析研究
——以UK-means 聚類算法為例

趙立坤 吳東領(lǐng) 韓燦燦

(唐山職業(yè)技術(shù)學(xué)院，河北 唐山 063000)

在國內(nèi)，網(wǎng)絡(luò)輿情規(guī)范的法律體制相對健全，文本聚類輿情監(jiān)控研究有不少，比如：北大方正技術(shù)研究院推出的方正智思輿情預(yù)警輔助決策支持系統(tǒng)[1]，該系統(tǒng)有效地解決了地方政府部門以傳統(tǒng)的人工方式進行輿情監(jiān)測的難題，但在音頻、視頻等多媒體信息方面還不能對不確定性數(shù)據(jù)進行挖掘，挖掘的識別率和數(shù)據(jù)效率性較低。

在國外，許多西方國家已制定了與互聯(lián)網(wǎng)輿情相關(guān)的法律規(guī)章。

美國TDT（Topic Detection and Tracking）系統(tǒng)是國外最有名的與互聯(lián)網(wǎng)熱點輿情發(fā)現(xiàn)與監(jiān)控有關(guān)的系統(tǒng)，初衷只是為了研究出一些能夠發(fā)現(xiàn)和跟蹤來自數(shù)據(jù)流中重要信息和內(nèi)容的算法[2]。

目前，國內(nèi)外輿情分析管理方面雖然取得了較好的研究成果，Hamdan 與Govaert 通過運用EM 算法解決不確定性數(shù)據(jù)聚類的混合密度問題。然而，這個模型卻不能任意地應(yīng)用于其他聚類算法。

K-means算法是一種最經(jīng)典、廣泛的劃分聚類算法，經(jīng)常被用于網(wǎng)絡(luò)輿情的聚類中分析中，因檢測、識別不精確、抽樣誤差、過時數(shù)據(jù)來源等條件因素，輿情數(shù)據(jù)往往挖掘不足，導(dǎo)致部分輿情數(shù)據(jù)遺漏。假設(shè)實際位置是有效的，僅僅依靠記錄的數(shù)據(jù)值，很多的目標(biāo)可能被置于錯誤的數(shù)據(jù)集群中，從過時數(shù)據(jù)值中得到的數(shù)據(jù)集群有明顯差異。

因此，本文提出一種基于UK-means 聚類算法對傳統(tǒng)的初始聚類中心選擇方法進行改進，通過不確定性因素與數(shù)據(jù)挖掘相結(jié)合的算法，用于微平臺的聚類中，以期能更快、更準(zhǔn)確地對近期微平臺數(shù)據(jù)進行聚類，實現(xiàn)熱點話題識別與追蹤。

1 不確定數(shù)據(jù)的分類

如圖1 所示，提出一種分類法來區(qū)分出硬聚類和模糊聚類的兩種數(shù)據(jù)聚類類型。硬聚類旨在通過考慮預(yù) 期的數(shù)據(jù)來提高聚類的準(zhǔn)確性和有效性。模糊聚類表示每個數(shù)據(jù)項被賦予分配給數(shù)據(jù)簇的任意成員的概率，聚類的結(jié)果為一個“模糊”表格。

圖1 不確定性數(shù)據(jù)挖掘的一種分類

傳統(tǒng)算法未考慮數(shù)據(jù)不確定性而導(dǎo)致部分?jǐn)?shù)據(jù)挖掘遺漏。在數(shù)據(jù)分類和數(shù)據(jù)聚集中，通過改進K-means算法對聚類質(zhì)心、兩個目標(biāo)的距離或目標(biāo)與質(zhì)心的距離等重要度量作重新定義和進行更深的研究[3]。

2 改進的K-means 聚類不確定性數(shù)據(jù)

為了在聚類過程中提取數(shù)據(jù)不確定性，我們提出一種實現(xiàn)最小化平方誤差總和的E(SSE)目標(biāo)算法。一個數(shù)據(jù)對象xi由一個帶有不確定性概率密度f(xi)的不確定性區(qū)域決定。假設(shè)給定一組數(shù)據(jù)群集，期望平方誤差總和計算如下：

數(shù)據(jù)集平均值如公式：

由此，我們將提出一種UK-means 聚類算法，來實現(xiàn)不確定性數(shù)據(jù)聚類。

1.Assign initial values for cluster means c1 to cK

2.repeat

3.for i=1 to n do

4.Assign each data point xito cluster Cj where E(||cj-xi||)is the minimum.

5.end for

6.for j=1 to K do

7.Recalculate cluster mean cj of cluster Cj

8.end for

9.until convergence

10.return C

通過UK-means 基于數(shù)據(jù)不確定性模型計算預(yù)期的距離和數(shù)據(jù)集質(zhì)心，收斂性可按照不同的標(biāo)準(zhǔn)來定義。如果收斂性依賴于下平方誤差，公式（1）中E(SSE)替代SSE。在第4 步中采用代數(shù)方法來確定E(||cj-xi||)，采用數(shù)值積分法確定線，圓等幾何圖形不確定性區(qū)域和不確定性概率密度。鑒于此，獲得的E(||cj-xi||2)用來替代E(||cj-xi||)。

3 實驗

3.1 線性移動不確定性數(shù)據(jù)聚類

UK-means 算法適用于任意一個不確定性區(qū)域和概率密度函數(shù)。為了證明方法的可行性，我們假設(shè)在一個質(zhì)心C=(z,q)和一個數(shù)據(jù)對象x 被指定在一個線性不確定的均勻分布的區(qū)域中。線性不確定性線段的終結(jié)點為（a,b）和（c,d），則參數(shù)δ 表示的線性方程式為(a+(c-a)t,b+(d-b)t)，其中t取值范圍屬于[0,1]。f(t)表示不確定性概率密度函數(shù)。

不確定性線段的距離公式為：

由此，可以得到：

其中B=2[(c-a)(a-z)+(d-b)(b-q)]

C=(z-a)2+(q-b)2

函數(shù)f(t)是均勻分布時，且f(t)=1 時，計算公式如下：

公式（4）、（5）計算為均勻分布的線性移動不確定性的平方距離。當(dāng)概率密度函數(shù)不是均勻分布時（如，高斯分布），采樣技術(shù)用來估計取值E(||cj-xi||)。

3.2 UK-means 算法的評估實驗

為了評估UK-means 算法的可行性，我們采用100×100 的二維空間所組成的一組隨機數(shù)據(jù)點作為記錄。對于每個數(shù)據(jù)點根據(jù)單向線性不確定性模型為其隨機產(chǎn)生不確定性。根據(jù)記錄和不確定性模擬記錄中的原始位置的偏移來表示目標(biāo)的真實位置。對于每個數(shù)據(jù)點位置記錄在案，目標(biāo)可能的移動距離由隨機產(chǎn)生一個數(shù)據(jù)來決定。計算和比較以下數(shù)據(jù)集的聚類輸出結(jié)果：

（1）記錄（傳統(tǒng)K-means）

（2）記錄+不確定性（改進UK-means）

（3）真實值（傳統(tǒng)K-means）

為核實UK-means 算法產(chǎn)生的數(shù)據(jù)群集接近真實數(shù)據(jù)中數(shù)據(jù)群集，采用調(diào)整相似度的蘭德指數(shù)（ARI）進行比較聚類結(jié)果[4]，計算兩個數(shù)據(jù)群集之間的相似度來對聚類結(jié)果進行評估。ARI 取值范圍為[?1,1]，值越大意味著聚類結(jié)果與真實情況越近似。

通過（2）與（3）數(shù)據(jù)群集間的ARI 指數(shù)和（1）與（3）數(shù)據(jù)群集間的ARI 指數(shù)比較，在不同的參數(shù)組合下，允許K-means 算法（（1）和（3））和UK-means算法（2）在一直運行至迭代次數(shù)達到10000 次或群集中的所有目標(biāo)在兩次連續(xù)迭代中沒有發(fā)生任何變化時結(jié)束，n=1000 和K=20 時，從表1 可以看出D 值的不同實驗結(jié)果。

表1 實驗結(jié)果

研究表明：當(dāng)不確定性程度增加時，UK-means 算法改進度就越高。當(dāng)群集的個數(shù)非常小時，目標(biāo)的個數(shù)和群集的個數(shù)對UK-means 算法的作用基本無影響。從表1 記錄數(shù)據(jù)中可以看到UK-means 算法中蘭德指數(shù)（ARI）的調(diào)整近似度始終高于傳統(tǒng)的K-means 算法。因此，UK-means 算法得到的數(shù)據(jù)群集更接近于從真實世界的數(shù)據(jù)群集。

4 結(jié)語

傳統(tǒng)數(shù)據(jù)挖掘算法無法挖掘固有的不確定性，產(chǎn)生的挖掘結(jié)果與真實世界的數(shù)據(jù)不相符。在本論文中，提出了在不確定性數(shù)據(jù)挖掘領(lǐng)域研究的一個分類方法，提高網(wǎng)絡(luò)輿情信息聚類結(jié)果的識別率、有效性，實現(xiàn)熱點話題識別與追蹤，從而準(zhǔn)確高效地管理互聯(lián)網(wǎng)信息[5]，防患于未然，對推動精神文明建設(shè)實現(xiàn)高質(zhì)量發(fā)展有著較為重要的使用價值和應(yīng)用價值。