網絡輿情熱點話題檢測聚類算法研究

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

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

關鍵詞：數據聚類；聚類算法；網絡輿情；熱點話題檢測

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

1 引言

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

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

2 基于劃分的聚類技術

2.1 K-MEANS算法

最廣泛使用的基于劃分的算法是K-MEANS聚類方法，K-MEANS優化的目標函數是：

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

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

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

2.2 模糊C均值算法

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

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

因此，FCM具有軟隸屬函數和恒重函數。一般來說，FCM表現比K-MEANS更好，并且受數據不確定性的影響較小。

2.3 K-調和均值算法

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

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

3 網絡輿情熱點話題檢測

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

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

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

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

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

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

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

其中：

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

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

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

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

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

3.2 話題檢測算法實驗對比

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

3.2.1 實驗數據

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

3.2.2 K-MEANS算法驗證

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

3.2.3 FCM算法驗證

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

3.2.4 K-調和均值算法驗證

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

3.2.5 三種算法性能對比

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

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

4 總結與展望

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

參考文獻

[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.