基于增量文本聚类算法的热点话题检测研究

魏艺泽，郭 慧，时晓旭

（华北科技学院计算机学院，北京东燕郊 065201）

0 引言

网络舆情热点发现（TDT）是一种通过检测与跟踪目标话题的方法，提供对新信息的发现和特定热点的关注。 通过数据收集、预处理、相关性分析和热点跟踪等步骤，自动聚类相关内容，并跟踪新闻事件的发展，为用户提供事件发展的轨迹和态势。 现有的研究技术主要有Single-Pass 聚类算法、KNN 最邻近法、K-means 算法等。

为了能够实现在线话题检测，需要对现有聚类算法进行改进，最常用的增量聚类算法是Single-Pass 算法。 税仪冬等［1］提出了一种结合周期性分类和Single-Pass 聚类话题识别和跟踪方法，通过降低漏检率和错检率，提高了准确性。 方星星，吕永强［2］通过引入子话题中心和时间距离计算公式以及优化耗费函数，显著改善了算法在漏检率、误检率、耗费函数等方面的性能。 张琛等［3］使用了Single-Pass 算法来处理大量的评论语料，并从其中提取出主题信息以展现新冠肺炎期间公众的关注热点。 杨波［4］通过设置高阈值提高了Single-Pass算法的准确性。 孙红光等［5］只对新增加的文本进行处理，提高了Single-Pass 算法的效率。

文本表示是将文本数据转化成结构化数据的方法，TF-IDF（Term Frequency-Inverse Document Frequency）以简单快速被好多学者所用。 罗燕等［6］采用齐普夫定律、特征词的词频以及TF-IDF算法来提取文档关键词。 牛永洁等［7］综合考虑张瑾提出基于TF-IDF、词位置和词跨度的关键词自动提取的方法，在情报关键词提取中有广泛的应用价值。 高楠等［8］提出了一种融合语义特征的TF-IDF 提取方法。 曹义亲等［9］使用TF-IDF算法作为基准进行关键词提取，并结合特征词词频均值化与特征词位置信息对权重算法对其进行改进。 米硕等［10］使用TextRank 算法与TF-IDF算法相结合的方法，提高了关键词提取的性能。

针对传统TF-IDF 方法提取文本特征时无法增量更新以及传统Single-Pass 算法聚类准确率较低的现象，本文提出一种增量的TF-IDF 算法和基于均值计算的Single-Pass 聚类话题检测方法，该方法首先利用提前设置IDF 表的方法，实现了增量获取词向量的功能，再通过均值计算簇中心来提高Single-Pass 算法在聚类时的准确率以及效率。

1 算法框架

研究框架如图1 所示，主要分为三个部分，分别是数据读取与预处理层、文本表示层、舆情分析层。 数据读取与处理层是首先将来自国内影响力比较大的社交平台获取的新闻数据存储到Sqlite3数据库并从数据库中读取出来，然后进行数据清洗、jieba 分词、去停用词。 文本表示层是利用TF-IDF 算法获得上下文向量。 舆情分析层利用Single-Pass 算法基础，根据提取到的特征词，划分子话题，利用均值动态更新类簇中心，提高文本相似度计算的准确性。

图1 算法框架图

2 增量TF-IDF 算法

分词之后，要进行文本特征提取，即识别文本中代表其特征的词项［11］。 TF-IDF 算法在信息检索和文本分类等任务中广泛应用，有效地帮助提取关键信息和识别文本的重要特征。 TF-IDF 的核心思想是：一个词在一个文档中的词频较高，同时在整个文档集合中的逆文档频率较低，则这个词对于该文档的重要性就越高。

由于计算IDF 是根据语料库中文档的数量和包含词汇的文档数量来计算的，所以传统的TFIDF 具有依赖语料库这一局限性，对于先到达的词汇无法估计在之后文本中的出现频率，影响了IDF 值计算的准确性。 另外如果每次都重新计算IDF 值，会耗费时间。 为了解决这个问题，本文通过事先建立语料库的方式来解决此问题。 利用计算公式计算IDF 值，并将其存储为IDF 表，语料库中已包含绝大多数常用词汇，可以满足实验文本的需求，可以有效地避免每次重新计算。 对于新出现的词汇，可以采用最大IDF 值作为估计值，以提高计算效率，并将新出现的IDF 值更新至IDF表中。 具体步骤如下：

（1） IDF 值用于衡量一个特定单词在整个语料库中的普遍重要性。 如果一个单词在整个语料库中出现的文章数较少，那么它在具体的文章中更加稀有和独特，具有很好的区分能力。 将前n天的数据储存成IDF 表，存储成字典形式，计算IDF 值。 其计算式如下［12］：

式中，IDFi值表示第i个IDF 值；代表文档总数；代表文档dj包含分词ti的文档数。

（2） 将预处理好的词计算TF 值，并且从IDF表查找该词的IDF 值，若表中没有该词的IDF 值，则设为该表中的最大值并存入IDF 表中，具体公式如下：

式中，TFij表示分词ti在文档编号dj中出现的频率；分子n代表分词ti在文档dj中出现的次数；分母表示文档dj中所有词出现次数的总和；k代表这个文档的总词数； 代表文档j 的总词数。

（3） 计算TF-IDF 值，具体公式如下：

其中，ti表示单词；dj表示文档；TFij表示单词ti在文档dj的词频；IDF（ti）表示单词在ti的逆文档频率。 在计算过程中，可以先计算出文档dj中每个单词的词频TF（ti，dj），然后从IDF 表中查找对应单词的IDF 值IDF（ti），最后将两者相乘即可得到单词ti在文档dj中的TF-IDF 值TF-IDF（ti，dj）。

3 基于均值计算的Single-Pass 聚类算法

3.1 簇中心的选择

对于网络新闻而言，新闻信息的获得、处理都是实时的。 对于此类问题，增量式的聚类更适用，Single-Pass 方法是增量式聚类方法的代表。 传统的Single-Pass 算法是一种流式处理文本数据的聚类算法，只需依次比较新输入的文本数据与已有类簇的文本相似度，不需要每次对整个文档集合重新聚类，具有实现便捷、易于理解和应用广泛的特点。

但传统的Single-Pass 算法以每个话题的第一篇文章作为簇中心会导致簇的代表性不够强，无法很好地代表整个簇的特征。 第一篇文章可能只是话题中的一个特例，不能很好地代表整个话题的特征。 这样就会导致簇的准确性较低，无法很好地区分不同的话题。 针对传统Single-Pass聚类算法不足，本文提出了基于均值计算的Single-Pass 聚类算法通过动态更新类簇中心，仅仅需要将输入的新文本与该类簇的质心向量比较相似度，就可以判断是否属于该聚类，均值簇中心是根据簇中所有文章的特征值计算得到的，可以更全面地反映簇的特征，可以有效地减少与各个簇比较的次数，降低算法运算复杂度以及提高新文本反应能力。

3.2 话题检测的流程

一个文本及阈值，将新进入话题的文本设为簇中心，后续文本出现时计算该文本与待聚类话题的簇中心的相似度，若相似度大于阈值则将新文档和原话题的簇中心取平均值，更新簇中心；否则新建一个话题并将该文本经过多次迭代计算可以得到多个话题类，完成话题检测。

（1） 按照文本的发布时间顺序从数据库中读出；

（2） 利用正则表达式去掉特殊符号；

（4） 使用哈工大停用词表以及自定义的疫情停用词表对文档去除停用词；

（5） 新话题存在很多与旧话题相近的特征词， 为了改善聚类质量，需要自定义替换词表将意思相近的词相互替换成相同的特征词；

表1 同义词替换表

（6） 通过TF-IDF 算法构造文本向量矩阵V1［v1，v2，v3，…vn］，V2，V3，…，Vn；

（7） 选择语料库的第一条文本作为种子语料，设为第一个话题C0；

（8） 设置相似度阈值S，将依次到来的文本向量与已有话题中的文本向量做余弦相似度计算，余弦相似度的计算公式为：

式中，Vi为文本向量矩阵。

（9） 若相似度小于阈值S则建立新话题Ci（i＝1，2，3，……），并设置进入新话题的第一条文本为簇中心mi，每次新加入的文档仅仅需要与聚类中心进行比较即可；若相似度计算结果大于阈值S则将文本划归到所属话题，并利用均值计算更新簇中心，对于每个簇Ci，其簇中心的更新公式为：

目前基本面情况缺乏推动行情变动的新消息，贸易摩擦是近期主导豆粕价格的重要因素。就目前情况，中美会谈正式释放和缓信号，考虑到市场近日已逐步反映对贸易摩擦和解的预期，加之2018/2019年度全球大豆供给充足，国内大豆、豆粕库存偏高的基本面情况，豆粕价格仍有继续下跌的空间。

（10） 直至所有文本归属到所建立的话题类别中，聚类结束。

4 实验及结果分析

4.1 数据集与实验设置

实验新闻语料库选自微信、腾讯网、天天快报、中国青年网、百度新闻、搜狐新闻等多个平台爬取的2021 年8 月4 日的1000 篇文章，共分为82 个类别，阈值为0.8。 其中包含以下5 个新闻话题：“南航CZ3762 航班通报密切接触者”“河南灾后重建恢复阶段”“特效药伊维菌素能结束新冠疫情系谣言”“单克隆抗体是全球新冠疫情防控研究的热点”以及“外防输入、内防反弹”事件。其中每个话题的报道100 篇。

本文采用的实验环境：操作系统Windows11，开发工具为Pycharm，数据库为SQLite 数据库。

4.2 评价指标

4.2.1 精度评估

为了验证改进算法的有效性，本文采用热点话题检测常用的评价指标准确率P、召回率R 和F 值对话题检测的精度进行评估，其定义如下：

（1） 精确率（Precision）。 表示分类器在预测为正类的情况下，预测正确的比例，计算公式如下：

（2） 召回率（Recall）。 所有实际为正类的文档中，被正确预测为正类的比例，计算公式如下：

（3） 综合评价指标（F1）是精确率和召回率的调和均值，相当于精确率和召回率的综合评价指标，计算公式如下：

上述公式（7）～（9）中，TP代表将实际为正类样本分类成正类样本的个数；TN代表将实际成负类样本分类成负类样本的个数；FP代表将实际为负类样本分类成正类样本的个数；FN代表将实际为正类样本分类成负类样本的个数。

4.2.2 顺序查找

为了验证算法的查找效率，利用顺序查找的方式进行测试。 顺序查找是一种简单直观的查找算法，它逐一比较待查找的元素和数据集中的每个元素，直到找到目标元素或遍历完整个数据集。

4.3 结果与分析

4.3.1 阈值的确定

图2 为利用Single-Pass 算法将舆情文本数据聚类出话题数目随着不同的阈值变化的曲线，选出与人工分类最接近的阈值。

图2 聚类数目随阈值的变化

对依次输入的舆情文本进行建模，并实现增量聚类，聚类个数随相似度的变化如图2，可以看到，随着阈值变大，聚类数目增多，只有相似度极大的文本才会聚成一类。 而随着阈值变小，聚类数目减少。 当阈值为0.8 时最符合事先人工分类的预期结果。 所以选取阈值为0.8 来进行实验。

4.3.2 实验结果

表2 是利用1000 条舆情文本数据，为了验证基于增量TF-IDF 的Single-Pass 聚类算法在改进前后的差异，设计的两组对照实验分别验证算法的聚类质量。

表2 改进的Single-Pass 算法聚类精确率对比表

利用五个不同的话题来验证原始算法和改进算法的聚类质量，用传统Single-Pass 算法聚类得到的结果如表3 所示，用改进的Single-Pass 得到的结果见表4。

表3 传统Single-Pass 算法实验结果

表4 基于均值计算的Single-Pass 算法

为了验证算法在求解质量与传统算法之间的差别，可以看出，在热点话题检测任务上，基于均值计算的Single-Pass 算法在热点话题检测任务上表现出更好的准确率、召回率和F 值。 相较于传统的Single-Pass 聚类算法改进的算法在准确率、召回率、F 值都提高了。 原因是传统的Single-Pass 聚类算法在选取某一话题的所有文本来表示话题类时，随机选取话题中心，通常选取第一个文本成为第一个类别的聚类簇中心，如果第一个文本不太具有代表意义，便不能全面地对一个类中的话题进行很好地阐述，随着文本聚类的进行，被错分的可能性逐渐增加，准确率会下降。 基于均值计算的Single-Pass 算法区别于传统的算法，它不仅计算简单，均值代表了簇中所有数据点的平均位置，能反映出簇的中心趋势。

表5 实验是为了验证算法在求解效率与传统算法之间的差别，评估标准为顺序查找的比较次数。

表5 改进的Single-Pass 算法聚类效率对比表

通过比较传统的Single-Pass 算法和基于均值计算的Single-Pass 算法两者的查找次数，基于均值计算的Single-Pass 算法比较次数减少了。通过实验结果可以看出基于均值计算的Single-Pass 算法能够将文本聚类到更好的话题类别，热点话题聚类效果更好，提高了热点话题聚类的准确率以及聚类的效率。

图3 在传统Single-Pass 聚类算法与改进算法的运行时间对比。

图3 两种算法的运行时间对比图

由图3 可以看出，改进的算法在时间消耗上明显低于传统Single-Pass 聚类算法，原因是改进后的算法中，利用文档向量的平均值作为簇中心可以更好代表整篇文章的主题，相似度大的文章可以通过减少对比次数来归类，在一定程度上提高了算法的运行效率。 传统的算法是利用进入文本的第一个文本作为簇中心，不能很好代表整篇文章，增加了对比的次数。

5 结论

（1） 针对TF-IDF 算法无法实现动态更新的问题，本文通过设置IDF 表对其进行改进。

（2） 针对Single-Pass 算法聚类准确率较低的问题，本文对聚类中心进行了改进，并对两者聚类算法进行对比实验。 结果表明，在热点话题检测任务上，相比于传统的Single-Pass 算法本文提出的计算每个话题簇中若干文档的质心向量作为此话题簇的话题簇代表这一概念，在保证精度的前提下，减少了比较次数，降低了计算复杂度，获得的聚类中心的代表性更强，有效提高了话题检测的准确性。

（3） 本文在使用TF-IDF 进行文本表示时，只关注了词频和文档频率，未能捕捉到词语之间的语义关系和上下文信息，导致在聚类任务中单词的语义信息没有得到有效利用，下一阶段将深入研究。