網(wǎng)絡輿情熱點話題檢測聚類算法研究

鄧先均 楊雅茜 羅昭 陳旭東 沈小平

摘要：數(shù)據(jù)聚類是基于某種相似性度量在多維數(shù)據(jù)中識別自然分組或集群的過程。聚類是許多不同學科的基本過程。 因此，來自不同領域的研究人員正在積極研究聚類問題。文章首先對代表性的基于劃分的聚類方法進行了一個概述，在此基礎之上，針對網(wǎng)絡輿情熱點話題檢測，文章使用這幾個聚類算法進行對比試驗，進而分析出更適用于熱點話題檢測方面的算法。最后對文章的研究進行總結，歸納出本研究的局限性，并指出改進的方向。

關鍵詞：數(shù)據(jù)聚類；聚類算法；網(wǎng)絡輿情；熱點話題檢測

中圖分類號：TP391.1 文獻標識碼：A 文章編號：1007-9416（2018）05-0146-04

1 引言

數(shù)據(jù)聚類是基于某種相似性度量在多維數(shù)據(jù)中識別自然分組或集群的過程，這是模式識別和機器學習中一個重要的處理過程[1]。此外，數(shù)據(jù)聚類也是人工智能的一個核心問題。聚類算法被使用在很多應用中，比如圖像分割、矢量和彩色圖像量化、數(shù)據(jù)挖掘、機器學習等領域[2-4]。數(shù)據(jù)聚類是無監(jiān)督模式識別中的一個難題，因為數(shù)據(jù)中的群集可能具有不同的形狀和大小[5]。

熱點話題指的是在某個時間段內人們比較關注的話題，涉及民生、政治、經(jīng)濟以及文化等方面[6]。熱點話題檢測的核心部分實質上是文本聚類的過程，對于不同的聚類算法對應不同程度的有效性[7]。文章首先對常用的基于劃分的聚類算法進行了一個概述，在此基礎上使用這些算法進行對比試驗，進而選擇出適合熱點話題檢測的算法。

2 基于劃分的聚類技術

2.1 K-MEANS算法

最廣泛使用的基于劃分的算法是K-MEANS聚類方法，K-MEANS優(yōu)化的目標函數(shù)是：

因此，K均值算法最小化簇內距離。K均值算法以K個質心開始（質心的初始值是隨機選擇的或從先驗信息中導出的），然后，將數(shù)據(jù)集中的每個數(shù)據(jù)對象分配給最近的聚類（即最接近的質心）。最后，質心根據(jù)相關的數(shù)據(jù)對象重新計算，重復這個過程，直到收斂。

K均值的隸屬函數(shù)和權重函數(shù)定義如下：

因此，K-MEANS具有很強的隸屬函數(shù)。此外，K-MEANS具有恒定的權重函數(shù)，因此，所有數(shù)據(jù)對象具有同等的重要性。

2.2 模糊C均值算法

K-MEANS的模糊版本稱為模糊C均值（FCM）（有時稱為模糊K均值）。FCM是基于最小平方誤差準則的模糊擴展。FCM優(yōu)于K均值的優(yōu)點是FCM將每個數(shù)據(jù)對象分配給具有某種程度隸屬度（即模糊聚類）的每個聚類，這更適合于數(shù)據(jù)集中聚類之間存在一些重疊的實際應用。FCM優(yōu)化的目標函數(shù)是：

其中是模糊指數(shù)[8]，，增加的值會使算法更加模糊；是第個聚類中第個數(shù)據(jù)對象的隸屬度值，滿足以下約束條件：

因此，F(xiàn)CM具有軟隸屬函數(shù)和恒重函數(shù)。一般來說，F(xiàn)CM表現(xiàn)比K-MEANS更好，并且受數(shù)據(jù)不確定性的影響較小。

2.3 K-調和均值算法

在K-調和均值算法（KHM）中，計算每個聚類中心到每個數(shù)據(jù)對象距離的調和平均值，然后相應地更新簇質心。KHM優(yōu)化的目標函數(shù)是：

因此，KHM具有軟隸屬函數(shù)和變化的權重函數(shù)。KHM為遠離所有質心的數(shù)據(jù)對象分配更高的權重，以幫助質心覆蓋更多的數(shù)據(jù)。

3 網(wǎng)絡輿情熱點話題檢測

3.1 話題檢測與跟蹤評價指標

在話題檢測與跟蹤（Topic Detectionand Tracking，TDT）的評價標準中，有準確率、召回率、漏報率和誤報率4個評價指標[9]，這4個評價指標的定義如下：

（1）準確率（P）：檢索出的關于某個特定話題的相關信息數(shù)量與所有檢索出的信息總數(shù)之比（也被稱為查準率），計算公式為，其中，A為系統(tǒng)正確檢索出的相關信息數(shù)量，B為把不相關的信息錯誤的識別為相關信息的數(shù)量。

（2）召回率（R）：檢索出的關于某個特定話題的相關信息數(shù)量與系統(tǒng)中描述該話題的相關信息總量之比，也稱為查全率，計算公式為，其中，A為系統(tǒng)正確檢索出的相關信息數(shù)量，C為系統(tǒng)未檢索出的相關信息的數(shù)量。

（3）漏報率（M）：系統(tǒng)沒有檢索出的關于某個特定話題的相關信息數(shù)量與系統(tǒng)中描述該話題的相關信息總量之比，計算公式為，其中，A為系統(tǒng)正確檢索出的相關信息數(shù)量，C為系統(tǒng)未檢索出的相關信息的數(shù)量。

（4）誤報率（F）：系統(tǒng)將與某個特定話題不相關的信息錯誤判斷為相關信息的數(shù)量與系統(tǒng)中沒有描述該話題的信息總量之比，計算公式為，其中，B為把不相關的信息錯誤的識別為相關信息的數(shù)量，D為系統(tǒng)未檢索出的不相關信息的數(shù)量。

在對熱點話題檢測中，對于一個TDT系統(tǒng)的性能，我們使用歸一化識別代價這個指標來評價，它通過系統(tǒng)的漏報率和誤報率計算得到，公式如下：

其中：

（1）為系統(tǒng)錯誤檢索代價，它由公式（11）計算得到。

（2）、分別為漏報和誤報的代價，它們的值通常情況下由應用預先給定。在大部分TDT測評任務中，它們分別取10和1，即漏報的代價比誤報代價高很多。

（3）、分別為系統(tǒng)檢索的漏報率和誤報率，它們可以通過系統(tǒng)輸出與標準答案對照的結果計算得到，計算公式是=漏檢數(shù)量/目標數(shù)量、=誤報數(shù)量/非目標數(shù)量。

（4）為一個先驗目標出現(xiàn)的概率，即，表示關于某個話題新聞報道出現(xiàn)的可能性，它的值通常也由相關應用給出。

為了使所得到的性能指標能夠在更有意義的范圍之內，我們將錯誤識別代價做歸一化處理得到。在公式（10）中，分母部分事實上是一個最小的預期代價，它是由系統(tǒng)對每一項識別給出的全部肯定或全部否定猜測而得到的。歸一化處理后的識別代價的最小值為0，表示系統(tǒng)性能最佳，最大值為1，表示系統(tǒng)性能較差。

3.2 話題檢測算法實驗對比

本節(jié)主要通過實驗來驗證和對比以下三種聚類算法的性能：K-MEANS算法、FCM算法和K-調和均值算法。

3.2.1 實驗數(shù)據(jù)

實驗數(shù)據(jù)是通過網(wǎng)絡爬蟲從網(wǎng)易新聞（http：//news.163.com）和今日頭條（https：//www.toutiao.com/ch/news_hot/）上下載了2378篇新聞，包含了14個主題，發(fā)生的時間從2018年2月到2018年3月，涵蓋了政治、經(jīng)濟、生活等多個方面，其事件分布情況如表1所示（每個話題下選前80篇作為訓練集，剩下的作為測試集）。

3.2.2 K-MEANS算法驗證

在K-MEANS算法實驗中，設置隱藏話題的數(shù)量K為14，表2給出了K-MEANS算法對14個話題的檢測準確率、召回率、漏報率、誤報率和。

3.2.3 FCM算法驗證

對實驗數(shù)據(jù)集使用FCM算法，得到對14個話題的檢測準確率、召回率、漏報率、誤報率和，如表3所示。

3.2.4 K-調和均值算法驗證

將FCM算法應用于實驗數(shù)據(jù)集，得到14個話題的檢測準確率、召回率、漏報率、誤報率和，如表4所示。

3.2.5 三種算法性能對比

根據(jù)表2、表3、表4中三種算法的漏報率、誤報率和，分別計算這三種算法的平均漏報率、誤報率和，通過這三項對比三種算法的性能，如表5所示。

從表5我們可以看出，這三種算法性能由高到低排序是：FCM算法、K-MEANS算法、K-調和均值算法，因此，在這三種算法中，選擇FCM算法作為熱點話題檢測算法是比較合適的。

4 總結與展望

文章在對代表性聚類方法進行概述的基礎上，根據(jù)網(wǎng)易和今日頭條2018年度2月和3月兩個平臺的數(shù)據(jù)，提煉出14個主題，選擇FCM、K-MEANS、K-調和均值三種算法對網(wǎng)絡輿情熱點事件在檢測準確率、召回率、漏報率、誤報率和這幾個方面進行對比試驗，最后得出相關結論。文章的局限性在于對信息發(fā)布平臺的選取不全面，同時在對比分析方面聚類算法種類的選擇也存在局限性，因而在接下來的研究中要加以改進。

參考文獻

[1]Jacques， Julien， and Cristian Preda. "Functional data clustering： a survey."Advances in Data Analysis and Classification 8.3 （2014）：231-255.

[2]Schaub M T， O'Clery N， Billeh Y N， et al. Graph partitions and cluster synchronization in networks of oscillators[J]. Chaos，2016，26（9）：094821.

[3]Kandakatla M， Challa L R. Cluster analysis for purpose oriented data mining in large databases[J]. 2017.

[4]Nilashi M， Fard K B， Rahmani M， et al. A Recommender System for Tourism Industry Using Cluster Ensemble and Prediction Machine Learning Techniques[J]. Computers & Industrial Engineering，2017， 109.

[5]Fan W， Bouguila N， Ziou D. Unsupervised Hybrid Feature Extraction Selection for High-Dimensional Non-Gaussian Data Clustering with Variational Inference[J]. IEEE Transactions on Knowledge & Data Engineering，2013，25（7）：1670-1685.

[6]徐維林，張暉，殷玉嬌，等.基于微博的熱點話題跟蹤技術研究[J].電腦知識與技術，2016（13）：186-188.

[7]Lin T， Wei S. The research on document clustering of network hot topics[C]// IEEE International Conference on Computer and Communications. IEEE，2017.

[8]Kim D W， Lee K H， Lee D. Fuzzy cluster validation index based on inter-cluster proximity[J]. Pattern Recognition Letters，2003，24（15）：2561-2574.

[9]Allan， James. TOPIC DETECTION AND TRACKING[J].Information Retrieval，2016.