基于加权LDA和改进Single-Pass聚类算法的热点话题检测方法

摘要

本发明公开了一种基于加权LDA和改进Single‑Pass聚类算法的热点话题检测方法，包括以下步骤：对文本数据进行预处理，包括中文分词、去除停用词和特征词加权；利用加权LDA主题模型对文本数据进行建模，通过挖掘其中的隐主题信息实现特征降维，并对向量化的结果进行过滤去噪；将经特征词加权的LDA主题模型处理后的文本向量化结果使用改进Single‑Pass聚类算法进行聚类；利用话题簇规模和话题簇紧密度计算话题簇的热度值，识别热点话题。本发明检测方法具有算法复杂度低、对文本输入时间顺序依赖性较低等优点。

权利要求

1.一种基于加权LDA和改进Single-Pass聚类算法的热点话题检测方法，其特征在于，包括以下步骤：步骤1：对文本数据进行预处理，包括中文分词、去除停用词和特征词加权；

步骤2：利用特征词加权的LDA主题模型对文本数据进行建模，通过挖掘其中的隐主题信息实现特征降维，并对向量化的结果进行过滤去噪；

步骤3：将步骤2中的经特征词加权的LDA主题模型处理后的文本向量化结果使用改进Single-Pass聚类算法进行聚类，即：

1)传入一个向量化后的文本数据d，如果d是数据集合中的第一篇文本，则新建一个话题簇，如果不是，则等待一个时间段Tn，对该时间段内的文本向量进行首先进行传统Single-Pass聚类；

2)将传统Single-Pass聚类后的结果与前一个时间段的聚类结果进行相似度对比：计算该批文本数据聚类得到的各个话题簇质心向量与已有的各个话题簇中的质心向量之间的相似度；

3)保留该批次文本向量各个话题簇的最大相似度并与阈值比较，如果大于阈值则归入与之相似度最大的原话题，否则新建一个话题；

4)更新话题簇，等待下一批向量化文本数据的传入；

步骤4：利用话题簇规模和话题簇紧密度计算话题簇的热度值，识别热点话题，即：统计步骤3中每个话题簇中的文档数目，并对其进行归一化处理，再按以下方式获取话题簇k的规模ck：其中，|Dk|是指话题簇k中包含的文档数目，|Dmax|指最大话题簇中的文档总数；按以下方式获取话题簇k紧密度uk：其中， 是话题簇k中第m篇文档利用“词频-逆话题频率”方法加权处理后的向量化表示；从话题簇规模和紧密度两个方面综合考虑，得到话题簇的热度，如下式：hot(k)＝η*ck+λ*uk

其中η是话题簇规模的权重，λ是话题簇紧密度的权重，η+λ＝1。

2.如权利要求1所述的基于加权LDA和改进Single-Pass聚类算法的热点话题检测方法，其特征在于，在步骤1中，中文分词具体为：采用中科院汉语分词系统实现文本的分词、词性标注及命名实体识别工作。

3.如权利要求1所述的基于加权LDA和改进Single-Pass聚类算法的热点话题检测方法，其特征在于，第i个特征词ti加权的具体方式为：其中pos(ti)代表特征词ti的词性权重。

4.如权利要求1所述的基于加权LDA和改进Single-Pass聚类算法的热点话题检测方法，其特征在于，还包括步骤5：基于话题词排序算法和文档距离计算对识别出的热点话题进行展示。

5.如权利要求4所述的基于加权LDA和改进Single-Pass聚类算法的热点话题检测方法，其特征在于，所述步骤5中的话题词排序算法具体为：根据步骤4得到的不同热度话题簇，采用“词频-逆话题频率”的方法对每个话题簇内的话题词计算权重，再按权重排序；话题词权重得获取方式为：其中，wi,k是文本中第i个单词wi在话题簇k中的权重， 指的是单词wi分配给话题簇k的次数， 表示包含至少一次单词wi的话题个数。

6.如权利要求4所述的基于加权LDA和改进Single-Pass聚类算法的热点话题检测方法，其特征在于，所述步骤5中的文档距离计算具体为：采用Jensen-Shannon距离DJS来度量dm和dn两个文档之间的相似度，其计算公式为：其中，Q＝(dm+dn)/2，DKL为文档向量之间的相对熵；由此得到话题簇中第m篇文档到簇内其它文档的总距离D(dm)获取方式如下：其中，θm是文档m的文档-主题分布，Dk为话题簇k的文档集合，dm,dn为Dk中的第m篇，第n篇文档。

说明书

基于加权LDA和改进Single-Pass聚类算法的热点话题检测

方法

技术领域

[0001] 本发明涉及热点话题检测技术领域，具体为一种基于特征词加权的隐含狄利克雷分布(Latent Dirichlet Allocation，LDA)主题模型和改进Single-Pass聚类算法的热点话题检测方法。

背景技术

[0002] 热点话题是一段时间内，围绕某一事件的相关新闻报道、微博信息被大量用户讨论和分享，造成该事件被广泛关注，最终形成全网范围内的话题焦点。热点话题检测是舆情监控及引导工作中的重要任务之一，它通过对海量的实时数据进行及时有效的处理，挖掘文本数据中的话题结构，展示当前互联网中用户关注的话题焦点及其相关内容，为舆情监控者及普通用户掌握当前的热点话题发展趋势提供便捷准确的参考。

[0003] 近年来，互联网保持着高速发展的趋势，网络信息容量、网民数量都呈现出爆炸式的增长趋势，网络已经成为人们获取信息的主要渠道。根据中国互联网络信息中心(CNNIC)2019年2月发布的《第43次中国互联网络发展状况统计报告》显示，截至2018年12月，我国网民规模已经达到8.29亿，与2017年相比增长了5653万人，年增长率为3.8％，互联网普及率达到59.6％。随着网络成为人们日常生活中不可或缺的信息传播新媒体，互联网这一“虚拟社会”与真实社会之间的互动越来越频繁，互联网正逐渐呈现出社会化特征。通过互联网传播的信息包含了民众对当前社会各种热点现象及问题的观点和想法，主要涉及政治、军事、科技、经济、体育、娱乐等各个领域。

[0004] 但由于网络中的消息冗余繁杂，仅仅依靠人工查找新闻话题难以应对网络中海量信息的处理并对其中的敏感主题及时做出反应。尤其对于决策者，要监控网络中所有相关的信息是不现实的，如果没有自动化的工具支持，很难及时的做出正确的决断，所以人们希望可以通过计算机来自动获取热门新闻话题，从而提高网络监管能力及处置网络舆情突发事件的能力。更为重要的是，在一些安全机构针对网络犯罪的检测和预防过程中，能快速准确地检测出相关话题并及时应对就显得尤为重要。

发明内容

[0005] 本发明所要解决的技术问题是提供一种基于加权LDA和改进Single-Pass聚类算法的热点话题检测方法，其具有算法复杂度低、对文本输入时间顺序依赖性较低等优点。

[0006] 为解决上述技术问题，本发明采用的技术方案是：

[0007] 一种基于加权LDA和改进Single-Pass聚类算法的热点话题检测方法，包括以下步骤：

[0008] 步骤1：对文本数据进行预处理，包括中文分词、去除停用词和特征词加权；

[0009] 步骤2：利用特征词加权的LDA主题模型对文本数据进行建模，通过挖掘其中的隐主题信息实现特征降维，并对向量化的结果进行过滤去噪；

[0010] 步骤3：将步骤2中的经特征词加权的LDA主题模型处理后的文本向量化结果使用改进Single-Pass聚类算法进行聚类，即：

[0011] 1)传入一个向量化后的文本数据d，如果d是数据集合中的第一篇文本，则新建一个话题簇，如果不是，则等待一个时间段Tn，对该时间段内的文本向量进行首先进行传统Single-Pass聚类；

[0012] 2)将传统Single-Pass聚类后的结果与前一个时间段的聚类结果进行相似度对比：计算该批文本数据聚类得到的各个话题簇质心向量与已有的各个话题簇中的质心向量之间的相似度；

[0013] 3)保留该批次文本向量各个话题簇的最大相似度并与阈值比较，如果大于阈值则归入与之相似度最大的原话题，否则新建一个话题；

[0014] 4)更新话题簇，等待下一批向量化文本数据的传入；

[0015] 步骤4：利用话题簇规模和话题簇紧密度计算话题簇的热度值，识别热点话题，即：

[0016] 统计步骤3中每个话题簇中的文档数目，并对其进行归一化处理，再按以下方式获取话题簇k的规模ck：

[0017]

[0018] 其中，|Dk|是指话题簇k中包含的文档数目，|Dmax|指最大话题簇中的文档总数；按以下方式获取话题簇k紧密度uk：

[0019]

[0020]

[0021] 其中， 是话题簇k中第m篇文档利用“词频-逆话题频率”方法加权处理后的向量化表示；从话题簇规模和紧密度两个方面综合考虑，得到话题簇的热度，如下式：

[0022] hot(k)＝η*ck+λ*uk

[0023] 其中η是话题簇规模的权重，λ是话题簇紧密度的权重，η+λ＝1。

[0024] 进一步的，在步骤1中，中文分词具体为：采用中科院汉语分词系统实现文本的分词、词性标注及命名实体识别工作。

[0025] 进一步的，在步骤1中，第i个特征词ti加权的具体方式为：

[0026]

[0027] 其中pos(ti)代表特征词ti的词性权重。

[0028] 进一步的，还包括步骤5：基于话题词排序算法和文档距离计算对识别出的热点话题进行展示。

[0029] 进一步的，所述步骤5中的话题词排序算法具体为：

[0030] 根据步骤4得到的不同热度话题簇，采用“词频-逆话题频率”的方法对每个话题簇内的话题词计算权重，再按权重排序；话题词权重得获取方式为：

[0031]

[0032] 其中，wi,k是文本中第i个单词wi在话题簇k中的权重， 指的是单词wi分配给话题簇k的次数， 表示包含至少一次单词wi的话题个数。

[0033] 进一步的，所述步骤5中的文档距离计算具体为：

[0034] 采用Jensen-Shannon距离DJS来度量dm和dn两个文档之间的相似度，其计算公式为：

[0035]

[0036] 其中，Q＝(dm+dn)/2，DKL为文档向量之间的相对熵；由此得到话题簇中第m篇文档到簇内其它文档的总距离D(dm)获取方式如下：

[0037]

[0038] 其中，θm是文档m的文档-主题分布，Dk为话题簇k的文档集合，dm,dn为Dk中的第m篇，第n篇文档。

[0039] 与现有技术相比，本发明的有益效果是：

[0040] 1)本发明对话题中的特征词(命名实体)赋予了相比于动词、名词更大的权重，增强了不同主题之间的可区分性和LDA模型的建模能力；

[0041] 2)本发明引入“话题中心”的概念来表示一个话题簇，将文本向量相似度的计算次数降低到话题簇个数的规模大小，算法复杂度与传统Single-Pass聚类算法相比普遍降低了至少十倍以上；

[0042] 3)本发明中改进Single-Pass聚类算法中的文件批处理的方法降低了Single-Pass聚类算法中文本输入顺序对聚类效果的影响，提高了聚类算法的稳定性；

[0043] 4)本发明从话题簇内的文档数目和文档紧密度两个方面考虑，计算话题的热度值，改进了话题的聚类效果。

附图说明

[0044] 图1为本发明的热点话题检测框架图；

[0045] 图2本发明的改进后的Single-Pass算法流程图；

[0046] 图3为本发明的新闻特征词加权与否的困惑度对比；

[0047] 图4为本发明的微博特征词加权与否的困惑度对比；

[0048] 图5为K-means算法、K-means++算法、传统Single-Pass算法和改进的Single-Pass聚类算法运行时间对比(日、周)；

[0049] 图6为使用本发明改进的方法与使用传统的Single-Pass方法的新闻数据困惑度对比；

[0050] 图7为使用本发明改进的方法与使用传统的Single-Pass方法的微博数据困惑度对比。

具体实施方式

[0051] 下面结合附图和具体实施方式对本发明做进一步详细说明。

[0052] 如图1所示，本发明方法输入为中文文本，输出为热点话题(包括排名后的话题词和话题簇代表文档)。首先对文本数据进行预处理，包括分词、停用词过滤、特征词加权等，然后利用LDA主题模型对其建模并对向量化的文本进行过滤去噪；接着基于改进的Single-Pass算法对降维后的文本进行聚类；最后通过热点话题检测方法识别话题簇中的热点话题，并采用话题词排名算法和文档距离计算公式对热点话题进行展示。详述如下：

[0053] 步骤1：文本预处理；本发明的文本预处理包括中文分词、去除停用词和特征词加权几个子步骤。

[0054] 1)中文分词

[0055] 中文句子与英文不同，句子中的词语往往是连接在一起的，为了便于利用LDA主题模型对其进行处理，分词成为文本处理的前提。本发明采用中科院汉语分词系统实现文本的分词、词性标注及命名实体识别工作。

[0056] 2)去除停用词

[0057] 停用词即是无区别能力也无描述能力的词，如“我”、“你”和虚词、介词等。本发明仅保留文档集合中的名词、动词和实体标注词汇，去掉常见的停用词和单个字的词语，利用“词频-逆文本频率”方法计算单词权重，每篇文本仅保留权重占比前75％的单词用于实现文本特征的降维。

[0058] 3)特征词加权

[0059] 利用LDA主题模型实现话题建模的过程实际上就是将文本集合从词空间降维到语义空间。在最初的LDA主题模型中，文本集合中的所有单词都被同等对待，这显然是不合理的，因此本发明在特征提取过程中对命名实体进行了加权处理，第i个特征词ti加权的具体方式为：

[0060]

[0061] 其中pos(ti)代表特征词ti的词性权重。

[0062] 4)微博数据的预处理

[0063] 新闻文本采用以上方式预处理即可，针对微博数据由于更具特征性，可按如下方式更好的预处理：

[0064] a)使用中科院汉语分词系统提供的新词发现功能，利用采集到的微博历史数据，将其每3000条数据分为一组作为新词发现的一组文本输入，找到新词并存入词典文件中。

[0065] b)在调用分词功能之前，首先导入新词词典文件到系统的用户词典中，判断一条微博文本中是否包含标签符号(##)，如果存在，则提取出其中的主题信息，并对该主题信息和标签以外的其它文本信息分别进行分词，得到的结果利用停用词表进行过滤。

[0066] c)在计算特征词权重时，除了保留微博文本中的动词、名词及实体标注词汇以外，还考虑到文本内容中包含的标签信息。通常一条微博中的标签包含有该微博的主题信息，所以在利用“词频-逆文本频率”方法计算特征词权重时，赋予标签文本更高的权重。根据如下方式进行加权处理：

[0067] weight(ti)＝ω1*pos(ti)+ω2*tag(ti)

[0068] 其中，pos(ti)和tag(ti)分表代表第i个特征词ti的词性权重和标签权重，ω1和ω2代表权重因子，本发明取ω1＝ω2＝0.5。改进特征加权的处理方式如下：

[0069]

[0070]

[0071] d)去除文本长度小于5的微博，这种微博内容包含信息量往往很少且很难准确理解其语义信息。

[0072] e)去除内容只包含表情、链接、图片的微博。

[0073] f)对于转发的微博，它通常会在“//”符号后附带转发的原文信息，为了防止文本的重复出现，本发明过滤掉了转发的原文信息，只保留转发的文本内容。

[0074] 普通LDA模型和特征词加权处理后的LDA模型的建模效果对比：为了检测LDA模型通过特征词加权处理后建模的效果，使用困惑度(Perplexity)作为评价指标。困惑度越小表示模型的预测能力越强，模型的推广性能就越高。困惑度计算公式如下：

[0075]

[0076] 其中Dtest表示测试集，|Dtest|表示测试集中的文档数，Nd指文档d的单词数目，p(wd)表示在测试集文档d中每个单词生成的概率。以天为时间片，从每个时间片的数据集中随机选择10％的文档作为测试集，随机选取实2017年12月23日至2017年12月29日的新闻报道和微博文本作为实验数据，分别使用特征词加权处理后的LDA模型和未对特征词加权的LDA模型对训练集建模分析，计算得到新闻困惑度如图3所示，微博困惑度如图4所示。从中可以看出利用特征词加权处理的LDA模型的困惑度均小于未对特征词加权的LDA模型困惑度。这表明对特征词进行加权处理可以提高LDA主题模型的建模能力。由于在特征词加权处理的过程中考虑到命名实体对文本语义的影响，所以利用LDA模型建模的过程中相应特征词的权重会增加，意味着主题-单词分布中对应特征词的分布值也会增大。表1列举了对特征词加权处理前后部分主题的特征词对比情况，从中可以看初对特征词进行加权处理可以有效增加不同主题之间的可区分性。

[0077] 表1 特征词加权前后新闻话题对比

[0078]

[0079] 步骤2：利用特征词加权处理的LDA主题模型对文本数据进行建模，通过挖掘其中的隐主题信息实现特征降维，并对向量化的结果进行过滤去噪；

[0080] 使用步骤1中用特征词加权处理后的LDA主题模型对文本进行建模和采样，得到文档-主题分布参数θ。其中LDA主题在文档上的先验参数α、词语在主题上的先验参数β取经验值α＝50/r，β＝0.01；最优主题数r经贝叶斯方法确定为45。然后文档在各个主题上都会存在一个分布值，值越大表示文档对该话题的贡献越大。然后过滤掉文档-主题分布值小于该阈值的话题，本发明定义文档-主题分布值中最大分布值的一半作为阈值。过滤算法流程描述如下：

[0081]

[0082] 最后将文档-主题分布重新进行归一化处理。

[0083] 步骤3：将步骤2中的经特征词加权的LDA主题模型处理后的文本向量化结果使用本发明提出的改进的Single-Pass聚类算法进行聚类，实现基于文档的主题维度实现话题聚类。

[0084] 本发明中的改进的Single-Pass聚类算法实现的流程如图2所示，改进处在于：用“话题中心”来表示一个话题簇，降低算法计算代价和复杂度；用批量文本处理代替单文本处理，降低文本输入顺序对聚类效果的影响，提高算法稳定性。具体实施方法如下：

[0085] 为了更方便清楚的实施该聚类方法，此处先明确几个概念表示：di为第i篇文档；D＝{d1,d2,...,dM}为M个文档的集合；Tc为相似度阈值，本发明中微博数据的阈值为0.45，新闻数据的阈值为0.32；两个文本向量d1、d2之间的相似度sim(d1,d2)获取方式如下：

[0086]

[0087] 话题中心用质心向量表示，获取方式如下：

[0088]

[0089] 其中，N表示该话题簇的文本总数。话题中心为Ck(k＝1,2,...,s)，它表示每个话题簇。

[0090] 首先，传入一个向量化后的文本数据d，如果d是数据集合中的第一篇文本，则新建一个话题簇。如果不是，则等待一个时间段Tn，对该时间段内的文本向量进行首先进行传统的Single-Pass聚类。再与前一个时间段的聚类结果进行相似度对比：计算该批文本聚类得到的各个话题簇质心向量与已有的各个话题簇中的质心向量之间的相似度，保留该批次文本向量各个话题簇的最大相似度并与阈值比较，如果大于阈值则归入与之相似度最大的原话题，否则新建一个话题。改进的Single-Pass聚类过程结束，更新话题簇，等待后续文档的传入。

[0091] 以特征词加权处理的LDA模型建模后得到的文本向量化结果作为输入，以漏检率、错检率及检测代价作为评价指标，本发明提出的改进算法与K-means、K-means++、传统Single-Pass算法在话题检测中的效果对比如表2。

[0092] 表2 不同算法的话题检测效果对比

[0093]

[0094]

[0095] 从表2中可以得出，本发明提出的改进Single-Pass聚类算法比传统Single-Pass算法得到的话题数更接近真实情况，且漏检率和错检率均低于传统算法。

[0096] 再选3月15日这一日和3月12日至3月18日一周的新闻数据，对于一天的数据，改进算法以两小时为时间片进行一次话题聚类检测，如果两小时内新增数据量达到200条则立即进行一次话题聚类检测；对于一周的数据，则以天为时间片进行话题聚类检测。分别计算利用K-means算法、K-means++算法、传统Single-Pass算法和改进的Single-Pass聚类算法的运行时间，如图5所示。从图中可以看出，与K-means算法相比，利用改进的Single-Pass聚类算法进行热点话题检测的时间复杂度大大降低，主要是因为Single-Pass算法基于增量聚类的思想，不需要在输入新数据后对整个数据集重新聚类，因而提高了话题检测的效率，实验数据显示利用改进的聚类算法节省了约40％的时间。同时从图中也可以观察到，改进的Single-Pass算法运行时间比传统Single-Pass算法稍长一点，这主要是因为改进算法利用批处理的思想，文本数据按时间片分批输入，需要多次聚类，因而运行时间会稍长一点，但改进算法减少了传统算法对于文本输入顺序的依赖性，提高了算法稳定性，所以改进的Single-Pass聚类算法对于热点话题检测依然是有意义的。

[0097] 步骤4：利用话题簇规模和话题簇紧密度计算话题簇的热度值，识别热点话题。

[0098] 首先统计步骤3中每个话题簇中的文档数目，并对其进行归一化处理；然后按如下方式获取话题簇k的规模ck：

[0099]

[0100] 其中，其中，|Dk|是指话题簇k中包含的文档数目，|Dmax|指最大话题簇中的文档总数；按以下方式获取话题簇k紧密度uk：

[0101]

[0102]

[0103] 其中， 是指话题簇k中第m篇文档利用“词频-逆话题频率”方法加权处理后的向量化表示；最后，从话题簇规模和紧密度两个方面综合考虑，得到话题簇的热度，如下式：

[0104] hot(k)＝η*ck+λ*uk

[0105] 其中η是话题簇规模的权重，λ是话题簇紧密度的权重，η+λ＝1。

[0106] 步骤5：基于话题词排名算法和文档距离计算公式对识别出的热点话题进行展示。

[0107] 1)对每个话题簇内的话题词进行排序

[0108] 步骤4中的得到了不同热度的话题簇，然后再采用“词频-逆话题频率”的方法对每个话题簇内的话题词计算权重，再按权重排序。话题词权重得获取方式如下：

[0109]

[0110] 其中，wi,k是文本中第i个单词wi在话题簇k中的权重， 指的是单词wi分配给话题簇k的次数， 表示包含至少一次单词wi的话题个数。

[0111] 2)确定话题的代表性文档

[0112] 选择话题簇中最有代表性的文档来表示一个话题簇，即找到每个话题簇中与其它文档最为相似的文档，并用该文档的标题作为热点话题的展示。此处采用Jensen-Shannon距离(用DJS()表示)来度量两个文档之间的相似度。Jensen-Shannon距离是基于KL(Kullback-Leibler)距离(即相对熵，用DKL()表示)定义的计算公式，主要用于测量两个文档之间概率分布的相似性。KL距离也是用于测量概率分布之间相似性的方法，对于两个文档dm和dn，用KL距离计算其相似性是不对称的，即DKL(dm||dn)≠DKL(dn||dm)。而Jensen-Shannon距离改进了KL距离不对称的缺点，其计算公式如下：

[0113]

[0114] 其中，Q＝(dm+dn)/2，由此得到话题簇中第m篇文档到簇内其它文档的总距离D(dm)获取方式如下：

[0115]

[0116] 其中θm是文档m的文档-主题分布，θn是文档n的文档-主题分布，Dk为话题k的文档集合，dm,dn为Dk中的第m篇，第n篇文档。该公式的计算结果越小，表明该文档在话题簇中与其它文档的相似度越高。

[0117] 对步骤4和步骤5得到的3月15日的新闻和微博文本的代表性文档、话题热度、话题词进行展示，选取话题热度值排名前5的话题结果表3、表4所示。

[0118] 表3 3月15日新闻热点话题展示

[0119]

[0120] 表4 3月15日微博热点话题展示

[0121]

[0122] 图6和图7分别是以随机一周时间的新闻和微博数据为数据输入，基于结合特征词加权和Single-Pass算法改进两个方面对比困惑度的变化情况。通过这两个图可以看出，针对改进的Single-Pass聚类算法的输入文档集合，在其预处理过程中结合特征词加权后，话题检测模型的困惑度更小，也就意味着热点话题检测的效果会更好，从而证明了本发明提出的热点话题检测方法的有效性。