基于多元词组和数据流聚类的热点话题动态发现

黄贵懿

(重庆文理学院， 重庆　永川　402160)



基于多元词组和数据流聚类的热点话题动态发现

黄贵懿

(重庆文理学院， 重庆永川402160)

[摘要]本文主要通过改进的TF-IDF算法和多元词组动态构建来选择特征关键词，并利用CluStream数据流聚类方法，实现文本主题的动态发现.实验表明，该方法可以较好地发现海量文本信息中不断变化的主题信息，从而达到推荐关联主题、动态监测舆情等目的.

[关键词]多元词组；数据流聚类；TF-IDF；CluStream；热点话题

目前，互联网中的新闻、论坛、博客和微博传播着大量信息，各类文本数量庞大，产生和传播速度极快.如何有效、快速地进行热点话题的挖掘，抽取文本的主题内容，实现对主题内容的动态跟踪，已成为亟待解决的问题.

1主题抽取现状

当前主题信息抽取技术主要分为有监督的学习方法和无监督的学习方法.有监督的学习方法需要利用人工标注的文本进行学习和训练，但在大数据环境下，面对海量文本，人工标注不可能实现，且人工标注的错误率较高，训练结果的识别效果较差.无监督的方法主要有：

1)基于统计的方法.通过计算文本关键词上下文频次和文本间出现情况来确定权重，通过权重的大小来抽取文本的主题词.

2)基于规则的方法.通过对文章、句子进行语法或语义分析，抽取主题信息.

3)基于人工智能的方法.通过计算机对训练语料进行学习，形成抽取模型，再利用学习到的模型开展主题信息抽取[1].

以上几种方法也有其不足之处.一是性能不理想，模型训练时间长或识别速度慢.此外，分词的性能不佳，直接影响识别效果.二是主题抽取不完整.一篇文章往往有几个中心点，现有方法只能发现其一.三是主题准确性不够.现有方法容易出现将文章顺便提及的内容作为主题词进行识别.本文基于多元词组和数据流聚类，来实现对热点话题动态抽取.基本方法分为两个步骤：第一个步骤是在不依赖语料库和训练库的基础上，运用改进后的TF-IDF算法从文本中提取出特征关键词；第二个步骤是运用聚类算法实现主题内容的自动发现.

2特征关键词的提取

文本话题的核心是提取和发现特征关键词，找到最能代表文本内容的词汇.我们通过文本预处理、抽取关键词和多元词组组合等步骤，实现对单个文本主题的初步识别.

2.1文本预处理

1)对机器自动采集到的网页原始文本根据DOM(Document Object Model)文档对象模型，发现和提取核心内容，然后再进行噪声过滤，包括去除链接、导航、网页代码等内容.

2)对文本进行分词操作，根据中文停用词表(有1 208个停用词)和成语词表过滤掉常用词和常用成语.

3)去除文本中的介词和形容词，保留未识别成分的未登录词.

2.2改进TF-IDF方法

文章中词的重要性往往通过其自身出现的频率和词语的代表性来确认.当前国内外处理词语权重的方法有很多，其中比较有代表性的方法是利用TF-IDF函数来计算词语在文章中的权重值.TF-IDF函数提取文档内的高频词语，并计算该词语在整个文档集合中的低文档频率，从而产生出高权重TF-IDF.计算公式如下：

tfTf·idf(wi)=tf·wi·idfwi

(1)

其中：ni是候选关键词Wi出现的次数，termTotal表示分词表中与候选关键词Wi长度相同的词的总词频，dtfwi表示候选关键词wi在词表中的词频.但传统的TF-IDF方法存在着一些弊端，一是计算权值时没有考虑到词语在文档中的位置因素，文章标题或摘要的重要性常常大于文本内容；二是对词本身的长度不敏感，文本中较长词的重要性往往更大；三是对出现频率比较高的领域词无法很好地抽取，对低频的重要人地名信息不够敏感，没有考虑词语组合关系等[2].为此，本文提出一种改进后的TF-IDF算法.

2.2.1指代词加值

文章中常常使用指代词以代表前面的名词，以避免词语重复出现，但指代词的出现极大地影响到对词频的统计.为了避免因指代词影响词频的统计结果，本文将同一句中指代词前序出现的名词或命名实体tf值作重复加值处理，以避免出现遗漏重要关键词的情况.

2.2.2增加位置加权

根据新闻文本的特点，候选关键词出现在标题中往往比在正文中更重要.为此，将出现在标题中的关键词Local(wi)权值调整为2，摘要中出现的关键词权值调整为1.5，反之为1.

2.2.3增加词长加权

词越长往往包含更多的特指信息，比短词或一些特定的命名实体重要性更强，但也并不意味着以简单的词长定权值.为此，改进后的Length(wi)词长加权函数为：

(2)

上式中的min(Len(w1),Len(w2),…,Len(wn))为候选词中长度最小的词长.

2.2.4增加信息量加权

从文本话题分析中发现，人名、地名、机构名等命名实体能够为文本话题提供区分信息，为此，对此类专有名词加大权重值.动词的重要性常常低于名词，对此类词降低权重值.具体计算方法见公式(3)：

(3)

2.2.5综合加权

根据公式(1)、公式(2)和公式(3)，设计一个综合加权公式，对TF-IDF加以改进和完善.wights(wi)为提取词的权值，提取出的词和权值存入候选关键词表中.改进后的TF-IDF表示为：

weights(wi)=tf·wi·idfwi·(Local(wi)+

Length(wi)+Info(wi))/3

(4)

2.3多元词语组合

2.3.1关键词组合

中文命名实体常常由多个词组合而成，然而普通文本经过分词处理后，可能将大量的关键词“碎片化”，从而无法获得较长的命名实体.根据2010年CSSCI关键词库统计，中文关键词中，二元和三元关键词达到83﹪.为此，适当加大初始TF-IDF选取范围，根据关键词的距离Y(Y<2词位)阈值，运用二元的Bi-Gram和三元的Tri-Gram方法，使用改进后的TF-IDF方法重新计算命名实体的权值，并将组合词及权值存入候选关键词表中.

2.3.2特征关键词提取

对候选关键词表中具有包含关系的子关键词进行删除，按词的权值从高到低进行排序，并提取前V个词作为特征关键词(V的值可以根据实际情况调节).

3基于数据流的聚类

3.1算法选择

纵观当前国内外中文热点话题发现的相关研究，有的采用混合聚类的主题词聚类方法识别主题[3]；有的采用匹配和统计相结合利用余弦距离的方法聚类主题；有的通过构建共词矩阵，测算主题词之间的距离来进行聚类[4].本文采取基于关键词的余弦相似度计算来测定文本主题的相似度.

现实中，由于网络信息数据海量出现，产生的数量大且速度极快，使用普通静态聚类方法不仅资源耗费多而且时间很长.为此，我们选择数据流聚类算法，在有限的内存和时间内，经过单遍扫描实现数据的高效聚类，以适应大数据时代的信息分析要求.

当前主要的数据流聚类算法有：1)基于密度的方法(DBSCAN、DENCLUE等)，一般根据距离以相邻的高密度区域形成聚类；2)基于划分的方法，基于传统的划分聚类法加以适当的改进，以适合数据流所要求的单遍扫描和增量聚类；3)基于层次的方法(BIRCH、CURE等)，由聚类特征组成一种树形结构来实现聚类.该方法能在数据单遍扫描下增量地维护、更新聚类特征.4)CluStream算法[5]，是一个典型的层次算法，能够有效保持增量效率.本文综合考虑到需要处理的文本来源于互联网，具备大数据的相应特征，所以采用CluStream算法，以微簇(Micro-clusters)的形式维护统计信息，并在簇特征向量中增加时间变量，以实现对海量信息的聚类.

3.2算法描述

CluStream算法将数据流聚类过程分为在线(on-line)(微聚类)和离线(off-line)(宏聚类)两个部分.在线部分负责实时处理每个新到达的数据记录，并按设定的时间周期保存聚类结果等信息；离线部分主要是利用这些聚类结果，按用户的具体要求分析已保存的聚类信息，并输出最终结果.

我们将数据流视为在t1,t2，…，ti…连续到达的数据点X1,X2，…，Xi，每个xi都是d维的向量(j=1,2,…,d).在t时刻到达的数据点记作xtc，在上述数据流情况下，将微簇看作为2d+3(d是数据维度)的元组，表示为：

(CF2x,CF1x,CF2t,CF1t,n)

(5)

上式中，CF2x为数据值的平方和，CF1x为数据值的和，CF2t为时间戳的平方和，CF1t为时间戳的和，n为集内数据项的数目.

微簇需要按一定的周期存储到磁盘文件中，以便离线查询时使用.但数据流产生的数据量一般很大，不可能将每个时刻产生的微簇记录都保存到磁盘中，所以引入了时间帧结构(Pyramidal Time Frame)，并将时间轴分为不同粒度的时间段，离当前越近，则相应的时间粒度越细.

3.3算法实现步骤

3.3.1初始化簇

首先存储最初始的N个文本，对其特征关键词使用Rocchio方法，计算文本间特征向量值.基于余弦文本相似度计算公式为：

(6)

上式中，di为文本的特征向量，dj为第j类文本的中心向量，wik为文本向量第k维的权重值，wjk为第j类文本向量的第k维的权重值，M为特征向量的维数.

相似度的范围在[-1,1]之间，值越接近于1，说明两个向量的方向更加趋向一致，两个文本间的相似度也越高.然后采用标准的K-means算法对相似度值进行计算，形成q个微簇：M1，M2，…，Mq.

3.3.2在线快速处理

对达到的每一个文本Xik，通过特征关键词先测算Xik与k个微簇中每一个的余弦相似度值，并将其放到相似度值最大的微簇Mk中.如果相似度值低于阈值Z，则另外生成一个带有标志信息的新簇，同时删除一个最早的簇或者合并两个最早的簇，以保持微簇总数量的平衡，并按金字塔式的时间结构将对应时刻的微簇保存到数据表中.

3.3.3离线处理

按查询时间点提取不同时段的聚类情况，生成最终可供显现的聚类结果.

4实验结果

4.1特征关键词提取实验

使用网络爬虫采集2013年4月至5月间3 400余条新浪、腾讯等国内新闻网页作为实验语料，去除网页中的链接，导航等信息，处理成纯文本形式，只包含新闻标题和正文，因为它在反映网络真实环境的同时又具有一定的系统性.对所采集的语料经过PanGuSegment分词系统进行分词，之后我们对分词进行预处理，对相关词进行加权计算后，再利用改进后的TF-IDF算法提取特征关键词.本实验以《凤凰古城商业化的是是非非》这篇2 500字的文章为例，经过分词预处理和关键词提取，选取权值靠前的60个词如表1所示.然后，对词进行二元和三元组合尝试，产生“凤凰古城、收费新政”等新二元词组，列入候选关键词列表中并重新计算权值，最后，按词语在文本中出现的先后顺序排序后，提取20个词作为最终关键词表.

表1　测试数据加权前后的TF-IDF值

4．2数据流聚类实验

对所有候选文章，先读取200篇的特征关键词表，根据文本相似度函数计算距离值，再根据距离值大小，用K-means算法形成10个初始微簇，再依时间顺序逐个读入剩余文本.新闻主题离散性高，在算法中设定了相似度参考阈值，根据相似度值变化情况灵活调整了微簇变化的数量，根据距离值将微簇量控制在10~30间变化，设定存储周期为20 ms，整个测试文本执行完成时间为10 s，基本能够满足快速动态提取主题的要求.

对提取离线结果，选取了最大的5个聚类结果列出，如表2所示.最后，选取每组聚类前两个关键词组组合后，构成热点话题，如表2最后“话题”列所示.测试所提取结果基本与人工提取的文章话题相关度在70﹪以上.

表2　测试数据前5项聚类结果

5结语

本文首先把新闻语料通过PanGuSegment进行自动分词，对分词后的语料进行停用词过滤，根据改进后的TF-IDF关键字提取的方法提取新闻语料库的关键词，对关键词按顺序进行组合和重新计算权值，通过CluStream算法对文本特征词的相似度进行动态聚类.实验结果证明了该方法的准确性、可行性和快速性.在下一步工作中，我们将结合语义的相似度和文本的情感特征继续开展深入研究.

[参考文献]

[1]刘知远.基于文档主题结构的关键词抽取方法研究[D].北京：清华大学,2011.

[2]钱爱兵.中文新闻网页处理与舆情分析[M].南京：南京大学出版社，2012.

[3]王小华,徐宁,谌志群.基于共词分析的文本主题词聚类与主题发现[J].情报科学,2011(11):1621-1625.

[4]史成金,程转流.基于混合聚类的中文词聚类[J].微计算机信息,2010，26(5-3)：222-223.

[5]AGGARWAL C C, HAN J, WANG J , et al.A framework for projected clustering of high dimensional data streams[C]．Proceedings 2004 VLDB ConferenceInProc of Vldb Dong,2004(30)：852-863．

(责任编辑穆刚)

Discovering of text’s hottopic based on the dynamic phrases and stream data mining

HUANG Guiyi

(Chongqing University of Arts and Sciences, Yongchuan Chongqing 402160, China)

Abstract：This paper rapidly find text’s hot topic by the improved TF-IDF algorithm and dynamic phrases that can choose the key words for text.The second, we uses clustering evolving datastreams to get hot topic for the candidate text. Discovering of text topic can detect the most important aspects of the vast information, so as to achieve the monitoring of public opinionrapidly.

Key words：dynamic phrases; data stream clustering; TF-IDF; Clustream; hot topic

[中图分类号]TP391

[文献标志码]A

[文章编号]1673-8004(2016)02-0126-04

[作者简介]黄贵懿(1979—)，男，重庆荣昌人，高级工程师，硕士，主要从事计算机应用与教育技术方面的研究.

[基金项目]全国教育信息技术研究“十二五”规划2014年度青年课题(146242121)；重庆市永川区自然科学基金项目(YCSTC,2014NC2001).

[收稿日期]2015-10-30