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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由此，我們將提出一種UK-means 聚類算法，來實(shí)現(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ù)不確定性模型計(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 實(shí)驗(yàn)

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

UK-means 算法適用于任意一個(gè)不確定性區(qū)域和概率密度函數(shù)。為了證明方法的可行性，我們假設(shè)在一個(gè)質(zhì)心C=(z,q)和一個(gè)數(shù)據(jù)對象x 被指定在一個(gè)線性不確定的均勻分布的區(qū)域中。線性不確定性線段的終結(jié)點(diǎn)為（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)是均勻分布時(shí)，且f(t)=1 時(shí)，計(jì)算公式如下：

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

3.2 UK-means 算法的評估實(shí)驗(yàn)

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

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

（2）記錄+不確定性（改進(jìn)UK-means）

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

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

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

表1 實(shí)驗(yàn)結(jié)果

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

4 結(jié)語

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