网络舆情热点话题检测聚类算法研究

邓先均 杨雅茜 罗昭 陈旭东 沈小平

摘要：数据聚类是基于某种相似性度量在多维数据中识别自然分组或集群的过程。聚类是许多不同学科的基本过程。 因此，来自不同领域的研究人员正在积极研究聚类问题。文章首先对代表性的基于划分的聚类方法进行了一个概述，在此基础之上，针对网络舆情热点话题检测，文章使用这几个聚类算法进行对比试验，进而分析出更适用于热点话题检测方面的算法。最后对文章的研究进行总结，归纳出本研究的局限性，并指出改进的方向。

关键词：数据聚类；聚类算法；网络舆情；热点话题检测

中图分类号：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.