基于改进Single-Pass算法的网络新闻话题发现

孙红光, 高 星, 孙铁利, 杨凤芹, 彭 杨, 冯国忠

( 1. 东北师范大学 信息科学与技术学院, 长春 130117； 2. 智能信息处理吉林省高校重点实验室, 长春 130117； 3. 解放军报社, 北京 100832)

互联网新媒体产生海量的半结构化新闻数据, 具有时效性短、 动态性强和结构不规范等特点. 因此如何有效地从海量数据中发现新闻话题, 是网络新闻话题发现的主要问题. 话题检测与跟踪(topic detection and tracking ,TDT)旨在研究从大量新闻数据流中发现重要信息, 在无人工干预的情况下自动判断数据流的主题[1]. 目前, 这方面的研究已取得了许多成果[2-8]. 话题发现的关键技术为文本聚类, 以话题为粒度发现新事件并了解事件的进展. 其算法有别于传统的文本聚类算法, 需同时考虑语料的时间特性、 动态性和数据来源等因素. 雷震等[9]提出了一种改进K均值算法发现热点话题, 用密度函数法进行聚类中心的初始化, 但该算法当处理新报道时需对所有文档重新计算, 无法保证话题发现的实时性; 张琛等[10]基于词项间语义信息的方法进行话题检测; Amrutha等[11]提出了TDA和TCTR(topic clustering and tweet retrieval)方法对微博进行聚类以发现话题. 本文采用话题发现中应用最广泛的Single-Pass算法实现新闻文本的聚类, 在特征权重的计算、 相似度计算和聚类中心动态更新三方面进行改进, 并应用于网络新闻话题发现的研究中.

1 话题发现及模型

1.1 话题发现

网络话题发现是指将大量讨论同一话题的新闻报道聚合在同一个簇下, 从而更好组织信息的过程. 本文研究网络新闻话题发现技术, 话题发现的处理流程如图1所示. 话题发现主要包括信息采集、 文本预处理、 特征提取、 文本表示、 相似度计算、 文本聚类6个步骤.

图1 网络新闻话题发现处理流程Fig.1 Processing flow for network news topic discovery

1.2 数据预处理及表示模型

首先, 通过主题爬虫系统从新浪新闻网站上爬取一段时间内的新闻报道, 构建新闻语料库. 本文采用中科院分词系统ICTCLAS对新闻语料进行分词并去除停用词. 其次, 文本向量表示是基于中文分词后的词项作为文本的特征向量, 每个向量都是一个维度. 由于文本向量空间维度较大, 因此采用文本特征选择方法进行降维, 降低计算的复杂度.

本文采用向量空间模型(vector space model, VSM)进行新闻文本的表示. 每个新闻文本D表示为n维向量形式：D=(t1,w1,t2,w2,…,ti,wi,tn,wn), 其中：n表示文本D中的特征词总数;ti(1

2 网络新闻话题聚类算法

经典Single-Pass算法实现简单、 处理速度快, 可处理动态数据. 但该算法并未考虑新闻报道的时间特性以及特征词项在新闻标题和正文不同位置对其权重值的影响. 本文充分考虑新闻报道的特性, 即动态性和时间特性等, 对该聚类算法进行如下改进.

2.1 词项权重计算

通常新闻标题能对事件做主要或关键性的描述, 基本体现了新闻的主题. 新闻报道标题的导向性应以具体的方法体现. 而传统的文本表示模型一般都是对新闻的正文内容进行相关处理. 本文考虑词项出现在新闻标题和正文不同的位置信息, 对词项权重的影响也不同, 采用TF-IDF权重计算方法.

由于考虑新闻报道的标题和正文信息, 在统计特征项词频时, 对来自标题的特征项词频乘上一个加权系数α(α≥1), 则文本特征w的词频计算公式为

tfw=α×tft(w)+tfc(w),

(1)

其中tft(w)和tfc(w)分别表示特征项w在标题和正文中的词频.α取值太小不能突出标题中特征项的重要性, 取值太大会抑制正文中绝大部分特征项对文本主题的描述能力, 因此α取值直接影响话题的聚类质量.

本文采用网络新闻报道作为语料库, 其数据特征是增量型的. 因此引入增量df, 即将语料按时间槽分别存储, 在第i个时间槽中词项w的文档频率通过前面的(i-1)个时间槽中所有文档和第i个时间槽的文档中包含w的文档数量进行计算. 采用增量文档频率的方式可提高文档处理的效率, 减少资源耗费. 词项w在时间槽i的文档频率计算公式为

dfi(w)=dfi-1(w)+dfci(w),

(2)

其中：ci表示在时间槽i的新闻报道数量;dfi(w)表示新闻报道集中包含词项w的文档数;dfi-1(w)表示在时间槽i之前出现w的文档数量. 由式(2)可知, 在每个时间槽能动态更新文档频率可体现出新闻语料的动态性和时间特性.

每篇报道d被表示为n维向量空间模型, 这里的n是d中含有特征词项的数量.d中每个词项w权重计算公式为

(3)

其中： weight(w,d)表示在报道d中词项w的权重;tfw表示词项w在文档d中出现的频率;Ni表示在时间i(包括i)之前的所有新闻文档数量. 这里对词项w的词频tf进行了归一化处理, 以防止其偏向长文档.

文本报道d与话题T之间的内容相似度sim(d,T)采用经典余弦公式计算, sim(d,T)的取值在0～1间, 相似度值越大, 表明报道与话题的相似性越高, 其报道就越有可能聚类到该话题下； 反之, 报道属于话题的可能性就越小.

2.2 文本相似度计算

对于新闻报道, 发布时间是其重要因素. 在相似度计算时, 仅考虑文本内容之间的相似度是不够的. 通常对于某个话题中的报道将会持续一段时间, 一篇报道的时间与话题的时间越远, 这篇报道属于该话题的可能性就越小. 所以, 在话题生成过程中应考虑时间因素来改进相似度计算公式, 以提高聚类的精度. 基于该思想, 本文在计算相似度时考虑了时间因素, 定义为

dis=10/(10+lg(dt-tt+1)),

(4)

其中：dt表示新闻报道的发布时间;tt表示话题最后的更新时间(指通过聚类得到的话题中新闻报道最新发布时间). 因此, 本文使用的报道与话题的相似度计算公式为

similarly(d,T)=sim(d,T)×dis.

(5)

由式(5)可知, 在相似度计算中要同时考虑基于内容和时间因素的影响.

2.3 改进的Single-Pass聚类算法

通过聚类算法得到的话题中包含有多篇报道, 采用质心向量, 即求该话题中所有文本特征向量的平均值表示该话题的中心向量. 在计算相似度时, 只需将新的报道与话题的中心向量计算相似度值, 而不需要与话题中的每篇报道都进行相似度值的计算, 这样节省了大量时间, 提高运算效率. 本文对Single-Pass聚类算法进行改进, 改进算法流程如图2所示.

图2 改进的Single-Pass算法流程Fig.2 Flow chart of improved Single-Pass algorithm

3 实验结果及分析

3.1 实验语料及环境

实验语料： 将基于主题的网络爬虫爬取2015-11-01—2015-11-30的新浪新闻数据作为数据集, 分别为国际、 政治、 体育等方面的新闻, 表1列出了各话题及相关新闻报道数量. 实验环境： 操作系统为Windows 7及以上, 基于JAVA平台实现.

表1 网络新闻话题语料库

3.2 评价指标

本文采用TDT评价指标：

漏检率

PM=C/(A+C),

(6)

错检率

PF=B/(B+D),

(7)

其中：A,B分别表示被检测到的相关文档数和不相关文档数;C,D分别表示未检测到的相关文档数和不相关文档数. TDT引入耗费函数对结果进行综合评价, 定义为

Cdet=CMPMP+CFPF(1-P),

(8)

其中：PM和PF分别表示漏检率和错检率；CM和CF分别表示漏检率和错检率系数, 根据经验值一般取CM=1,CF=0.1;P表示某报道属于某话题的先验概率, 一般取值为P=0.02.

3.3 结果分析

本文对选取的600篇新闻文档进行实验分析及参数调整. 实验比较标题中特征加权系数α的不同取值对话题聚类质量的影响, 结果如图3所示. 由图3可见, 当α=3时, 聚类算法的PF和PM取值最小. 因此, 本文中选取α=3. Single-Pass算法中相似度阈值的选取对聚类结果的影响如图4所示.

图3 加权系数α对话题聚类结果的影响Fig.3 Effects of weighting coefficient α on topic clustering results

图4 相似度阈值对聚类结果的影响Fig.4 Effects of similarity threshold on clustering results

由图4可见, 随着阈值的增加, 耗费代价函数在不断减少后开始增长, 本文选取耗费函数值最小点所对应的相似度阈值0.02. 经典Single-Pass聚类算法与改进算法的对比结果如图5所示. 由图5可见, 改进的Single-Pass方法比经典方法的耗费代价小. 本文方法在耗费代价上降低了0.34%, 错检率降低了1.57%. 实验结果表明, 本文方法能更有效、 更准确地实现话题检测.

图5 经典Single-Pass算法与改进算法的对比结果Fig.5 Comparison results between classical Single-Pass algorithm and improved algorithm

综上所述, 本文针对新闻报道的特性, 从三方面对Single-Pass算法进行了研究, 只对新增加的文本进行处理, 提高聚类的效率, 减少资源的耗费, 提高了算法实现话题发现的速度和效果. 实验结果验证了本文方法的可行性.

[1] Wayne C L. Multilingual Topic Detection and Tracking: Successful Research Enabled by Corpora and Evaluation [C]//Proceedings of the 2nd International Conference on Language Resources and Evaluation Conference (LREC). Paris: European Language Resources Association, 2000: 1487-1493.

[2] HE Qi, Chang K, Lim E P. A Model for Anticipatory Event Detection [C]//International Conference on Conceptual Modeling. Berlin: Springer-Verlag, 2006： 168-181.

[3] 韩忠明, 陈妮, 乐嘉锦, 等. 面向热点话题时间序列的有效聚类算法研究 [J]. 计算机学报, 2012, 35(11)： 2337-2347. (HAN Zhongming, CHEN Ni, LE Jiajin, et al. An Efficient and Effective Clustering Algorithm for Times Series of Hot Topics [J]. Chinese Jouranl of Computers, 2012, 35(11)： 2337-2347.)

[4] ZHANG Kuo, ZI Juan, WU Ligang. New Event Detection Based on Indexing-Tree and Named Entity [C]//Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press, 2007： 215-222.

[5] Seo Y W, Sycara K. Text Clustering for Topic Detection [D]. Pittsburgh: Carnegie Mellon University, 2004.

[6] YANG Yiming, Pierce T, Carbonell J. A Study of Retrospective and Online Event Detection [C]//Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press, 1998： 28-36.

[7] ZHANG Zhongfeng, LI Qiudan. QuestionHolic： Hot Topic Discovery and Trend Analysis in Community Question Answering Systems [J]. Expert Systems with Applications, 2011, 38(6)： 6848-6855.

[9] 雷震, 吴玲达, 雷蕾, 等. 初始化类中心的增量K均值法及其在新闻事件探测中的应用 [J]. 情报学报, 2006, 25(3)： 289-295. (LEI Zhen, WU Lingda, LEI Lei, et al. IncrementalK-Means Method Based on Initialisation of Cluster Centers and Its Application in News Event Detection [J]. Journal of the China Society for Scientific and Technical Information, 2006, 25(3)： 289-295.)

[10] ZHANG Chen, WANG Hao, CAO Liangliang, et al. A Hybrid Term-Term Relations Analysis Approach for Topic Detection [J]. Knowledge-Based Systems, 2016, 93: 109-120.

[11] Amrutha B, Mintu P. Keyword Based Tweet Extraction and Detection of Related Topics [J]. Procedia Computer Science, 2015, 46: 364-371.