乌吉斯古愣+刘晓影+鄢楚平

摘  要： 面对海量的网络新闻信息，为了能更加准确与全面地从中发现用户感兴趣的话题，提出一种基于事件关联网络的用户兴趣话题发现算法。该算法建立了代表事件之间关联关系的事件关联网络，基于该事件关联网络，采用链接分析技术度量用户对不同新闻事件感兴趣的程度，从而采用针对新闻特定语义架构的改进Single?pass聚类算法发现用户感兴趣的话题。此外，采用Bootstrapping算法，实现对相关兴趣领域词汇的语义扩展。实验表明，该算法能够更加准确而全面地获取用户感兴趣的话题。

关键词： 话题识别; 链接分析; 用户兴趣; Bootstrapping算法; 关联网络

中图分类号： TN711?34; TP391            文献标识码： A                          文章编号： 1004?373X（2015）06?0007?06

Algorithm to find topics that users are interested based on network associated with events

WU Jisiguleng， LIU Xiao?ying， YAN Chu?ping

（No.15 Research Institute， China Electronics Technology Group Corporation， Beijing 100083， China）

Abstract：Being faced of massive Internet news information， to improve the accuracy of detecting the topics that the users are interested， a topic detection algorithm based on the network associated with the events is proposed  for users interest. The algorithm established an event?related network representative of relevance relationship among news events. The link analysis technique is used to measure the degree of user interest in the news， so as to identify the topics that the users are interested by using an improved Single?pass clustering algorithm based on news specific semantic structure. In addition， Bootstrapping algorithm is adopted to achieve the related interest words semantic extensions. The experiment result shows that the algorithm can more accurately and comprehensively get the topics that the users are interested.

Keywords： topic recognition; link analysis; user interest; Bootstrapping algorithm; associated network

0  引  言

随着互联网的迅速发展，网络信息量爆炸式增长，导致人们处理和使用这些庞大的信息变得越来越困难。面对网络信息过载，如何快速准确地获取人们感兴趣的新闻话题，并对这些新闻话题进行有效地组织、处理和分析，是当前信息处理领域研究的一个重点，其研究成果具有重要的意义。

话题识别与跟踪技术正是在这种情况下所产生。针对不同话题识别任务的特点，新闻话题识别的研究可分为热点话题识别[1?3]、敏感话题识别[4?5]、领域话题识别[6]和用户兴趣话题识别[7]四个方面。关于用户兴趣话题识别方面的研究相对较少，Kurtz等人所提出的系统[7]，基于个人配置文件提取用户兴趣过滤新闻文本，从而采用改进的话题聚类算法获取用户感兴趣的话题。该算法在基于新闻文本自身所携信息进行过滤时，易遗漏某些同样需关注的相关话题。为解决该类问题需充分考虑事件关系，关于事件关系识别，杨雪蓉等人提出了一种基于核心词和实体推理的事件关系识别方法[8]。该方法明显优于单基于事件语义的事件关系识别方法，但当面对大量的网络热点新闻事件时，该算法中事件线索集的构建有限，因为对部分事件无法构建虚拟相关事件集合。为了有效提高大规模互联网数据中用户兴趣话题识别的准确率，避免对相关兴趣新闻事件的遗漏，本文提出一种符合新闻特定语义结构的事件多维关联关系计算方法识别事件关系，从而构建事件加权关联网络。基于该事件关联网络，采用连接分析技术综合考虑各新闻事件之间的关联关系，对新闻集按照用户感兴趣的程度进行排序，获取用户感兴趣的新闻事件，进而通过改进的single ?pass聚类算法获取用户感兴趣的话题。此外，针对用户兴趣的动态变化特性，本文只需用户择感兴趣的兴趣领域标签即可。实验表明，该算法能达到较高的准确率，使人们能对感兴趣的话题具有全面而准确地认识。

1  算法提出

本文提出的基于事件关联网络的用户兴趣话题发现算法中引入了新闻事件兴趣度值的概念，表示用户想要关注某新闻事件的程度。该算法可分为以下四个步骤：第一，基于自主可扩展的知识库，对不同兴趣领域词汇进行扩展;第二，构建由新获取到的新闻事件与用户感兴趣的历史新闻事件组成的事件加权关联网络;第三，基于所构建的事件关联网络，采用链接分析技术，通过计算每个新闻事件的兴趣度值获取用户感兴趣的新闻集。最后，在所得用户感兴趣的新闻集上，基于新闻文本特有的语义框架，采用改进的聚类算法获取用户感兴趣的话题。

1.1  构建可扩展领域知识库

通常用户所能提供的兴趣词数量较为有限，为能更好地把握用户兴趣需求，本文通过采用Bootstrapping半监督机器学习算法[9]构建可自主扩展的知识库，将少量不同兴趣领域词集扩展为能够较全面代表用户兴趣需求的兴趣词集。关于知识库的自主扩展，人工选取新闻语料中少量不同兴趣领域的中心词作为种子词集，从大量的新闻语料库中提取有效词作为待标注词集，自动地进行知识学习，从而实现知识库中不同兴趣领域词汇的扩展。

共现关系与相似关系是建立可扩展知识库的基础，本文分别基于Wordnet与Google检索计算词之间的语义相似度值和共现关系值，将语义相似度值和共现关系值作为每轮新扩展兴趣词的二维置信度。基于Bootstrapping算法，逐步对新获取的新闻词汇进行标注，实现知识库中不同兴趣领域的有效词、相似词对和共现词对的自主扩展。具体算法如下：

输入：用户提供的少量兴趣词集

输出：基于知识库扩展后的能较全面代表用户兴趣的兴趣词集

（1） 将用户提供的少量兴趣词赋予兴趣度值x，初始赋值为1，作为初始种子词集W;

（2） 从领域知识库中获取实词，作为待标注词集U;

（3） 基于领域知识库，计算U中每个词与W中词的语义相似度值Si和共现度值Gi，分别作为二维置信度;

（4） 将置信度较高的前n个词，作为新增种子词集N，扩展原始种子词集为W+N;

（5） 对新增加的n个种子词，基于置信度值和对应的原始兴趣种子词，计算其兴趣度值x;

（6） 重复第（3）～（5）步，直至符合算法结束条件，获取最终的种子词集FW;

该方法中用户只需选择感兴趣的兴趣领域标签即可，有效避免了用户兴趣的动态变化特性所带来用户兴趣判断不准确。随着新输入新闻语料的增多，知识库扩展的效果将更加全面与准确。

1.2  构建事件关联网络

大量的互联网新闻数据中，每一篇新闻报道代表一个新闻事件。大量的事件之间存在着纷繁复杂的关联关系。仅基于事件所携主要信息计算事件的兴趣度值，易忽略同样需关注的相关事件。构建事件关联网络，综合考虑事件间的关联因素，有助于更加准确和全面地获取用户感兴趣的话题。

事件关联网络中，每个节点代表一个新闻事件，将事件兴趣度值作为节点的权重;每个边代表两个事件之间的相关联程度，将事件在时间、人物（或机构）、地点和行为四个维度上的相关程度作为边的四维权重。采用命名实体识别技术获取新闻中表示地点、人物（或机构）和行为的词，基于新闻的实时性，视新闻报道的时间为事件的近似时间，计算事件在时间、人物（或机构）、地点和行为四个维度上的相关程度，即关联网络中边的四维权重，从而综合考虑事件之间在以上四个维度的关联程度。事件各维关联度的计算公式如下：

（1） 事件时间关联度计算

如果两个事件发生的时间差值在一定的范围内，则认为这两个事件在时间上是关联的。关联的强度与发生时间的间隔有关。时间的间隔越短，关联的强度越强。具体计算公式如式（1）所示：

[Reltime（T1，T2）=time（T1）-time（T2）maxTi，TjΔtime（Ti，Tj）] （1）

式中：[time（T1）]，[time（T2）]分别表示事件[T1]，[T2]的时间;[Ti]和[Tj]是任意相关事件。[Reltime（T1，T2）]的值在[0，1]。

（2） 事件人物（或机构）关联度计算

如果两个事件中涉及的人物（或机构）相同或具有较高的相似度或共现率，则认为这两个事件在人物（或机构）上是关联的，关联的强度以相同人物（或机构）为最强。基于改进的词集相似度计算公式，获取事件的人物（或机构）关联度值，具体计算公式如式（2）所示：

[Relobject（T1，T2）=object（T1）?object（T2）object（T1）?object（T2）]    （2）

式中：[object（T1）]、[object（T2）]为事件中涉及的人名（或机构名称）的集合，集合中的元素可以重复;[object（T1）?object（T2）]表示两个事件中重复出现的人名（或机构名称）和具有较高相似度或共现率的人名数量;[object（T1）?object（T2）]表示两个事件中总共涉及的人名数量，[Relobject（T1，T2）]的值在[0，1]。

（3） 事件地点关联度计算

基于改进的词集相似度计算公式，获取事件的地点关联度值，具体计算公式如式（3）所示：

[Rellocate（T1，T2）=locate（T1）?locate（T2）locate（T1）?locate（T2）]     （3）

式中：[locate（T1）]，[locate（T2）]为事件中涉及的地名集合，集合中的元素可以重复;[locate（T1）?locate（T2）]表示两个话题中重复出现的地名和具有较高相似度或共现率的地名数量;[locate（T1）?locate（T2）]表示两个事件中总共涉及的地名数量;[Rellocate（T1，T2）]的值在[0，1]。

（4） 事件行为关联度计算

如果两个事件中涉及的行为相同，或是相近的，则认为这两个事件在行为上是关联的。关联的强度以相同行为为最强。事件的行为关联度值通过度量新闻事件中除表示时间、地点、人物以外的特征词间的语义相似度得到。具体计算公式如式（4）所示：

[Relact（A1，A2）=12（w∈A1（maxSim（w，A2）·IDF（w））w∈A1IDF（w）+                            w∈A2（maxSim（w，A1）·IDF（w））w∈A2IDF（w））] （4）

式中：A1和A2是表示话题行为的特征词集合， [maxSim（w，A）*IDF（w）]是词w与特征词集A中语义最相近的词的语义相似性;[IDF（w）]反映了词包含信息量的多少。英国国家语料库（British National Corpus）被用来统计[IDF（w）]。

1.3  计算事件兴趣度值

基于事件关联网络计算用户对某一新闻感兴趣的程度，所采取的链接分析从两个方面展开：一是考虑当前新获取的事件间的关联影响，如果某一事件与其他用户感兴趣的新闻事件关联关系越紧密，则认为该事件的事件兴趣度值越高;二是考虑用户感兴趣的相似的历史新闻事件对当前事件的影响，认为相似的事件通常具有相近的事件兴趣度。另外，在每次对新获取的事件兴趣度度量时，将兴趣度较高的事件保留起来作为历史新闻事件。

对新获取的新闻事件，在事件关联网络中分别从时间、对象（人物或组织）、空间和行为这四个维度来分析事件的兴趣度值。首先，对网络中代表新获取新闻事件的节点赋予表示其事件兴趣度值的初始权重[SEvent（t）]，具体计算公式如式（5）所示：

[SEvent（t）=a1?Stime（t）+a2?Sobject（t）+                a3?Sspace（t）+a4?Sact（t）]  （5）

式中：[a1]，[a2]，[a3]，[a4]分别表示时间、人物（或机构）、地点和行为兴趣度在事件兴趣度计算所占权重;[Stime（t）]，[Sobject（t）]，[Sspace（t）]和[Sact（t）]分别表示通过与用户扩展兴趣词集的匹配，新闻事件特征词集中兴趣度值最高的表示时间、人物（或机构）、地点和行为的词的兴趣度值。

然后，为分析事件之间的关联影响，在建立的事件关联网络上，采用随机游走模型，分析事件的兴趣度。关联网络中所有事件的集合表示为T={t1，t2，…，tn}，ti是关联图中的事件。无向图G=<v，ET，EO，ES，EA>是根据事件间的相关度建立的关联图，其中V是包含n个事件的节点的集合，等于T;ET、EO、ES、EA分别是新闻事件节点在时间、对象、空间、行为上的边的集合，若两节点间的相关度大于给定阈值，则有边存在，它是v×v的一个子集。对新爬取到的新闻事件在多维度相关事件影响下的事件兴趣度[SEvent（t）]的计算公式如式（6）所示：

式中：[a1]和[a5]，[a2]和[a6]，[a3]和[a7]，[a4]和[a8]分别表示在时间、空间、对象和行为上的权重，取值范围为（0，1]，[i=18ai=1]，且[0<ai<1];[Stime（t）]和[Stime（w）]，[Sobject（t）]和[Sobject（w）]，[Sspace（t）]和[Sspace（w）]，[Sact（t）]和[Sact（w）]分别是事件在时间、空间、对象（人物或组织）、行为这四个维度上的初始兴趣度值。[Reltime（t，w）]，[Relobject（t，w）]，[Relspace（t，w）]，[Relact（t，w）]反映了事件在时间、对象（人物或组织）、空间、和行为这四个维度上的相关联程度。

基于式（6）计算事件兴趣度值，将事件兴趣度值大于特定阈值的新闻事件，归为用户感兴趣的新闻事件集，获取用户感兴趣的事件集。

1.4  用户兴趣话题识别

针对网络热点新闻话题中难以区分一个话题下的多个子话题现象，本文采用一种基于LDA（Latent Dirichlet Allocation）模型的改进的Single?Pass聚类算法对1.3节中所获取的用户感兴趣的新闻进行聚类，从而获取用户兴趣话题。应用LDA模型对新闻文档进行建模[10]，使用Single?Pass聚类算法生成话题，并针对新闻文本特有的语义架构，在Single?Pass聚类算法中的文本相似性将同时利用向量相似性和命名实体相似性。

计算向量相似性，采用基于有效词库的方法，文本的向量维度一般能够达到上万维，消耗了大量的计算资源。故采用LDA模型，LDA不仅能发掘文本中隐含的主题信息，同时能够将文本表示成主题分布的过程看作是将文本用低维度向量表示的过程，即LDA能够很大程度上对高维文本向量进行降维处理。LDA模型参数中K代表将在文本集合中设定的K个主题，将每一个文本向这K个主题上去映射，转换成一个K维的向量，向量的每一个维度对应一个主题。如此，原本基于有效词库用高维文本向量表示的文本即可用K维的低维文本向量进行表示。从而，易通过计算两个K维向量的夹角获取这两个文本之间的向量相似度。然而，仅仅考虑向量相似度是不够的，新闻数据集中包含有很多十分相似的话题，比如“中日关系系列话题”，“世界杯比赛系列话题”，“自然灾害相关话题”等，这些话题从内容相似性上来说非常的相近，因此可以推断出经过LDA主题模型表示后，这些文本之间的区别体现得仍然不是特别全面。故，引入命名实体相似度的计算，通过得到两个文本的命名实体集合，基于新闻特有的语义框架[11]，分别基于1.2节中的式（1）～式（4）计算两个新闻文本在时间、人名（或组织名）、地名和行为四个方面的相似度，实现对话体更加精准划分聚类。

2  实验分析

2.1  实验数据

通过网络爬虫收集自Retuers网站 （http：//www.reuter s.com/）的英文数据集，作为实验所用的英文数据集，包含2014年1月—2014年6月的18 000篇新闻，如表1所示，涵盖了国际、经济、政治、军事、社会、科技等多个领域。

构建可供用户选择的兴趣分类标签集，分别有自然灾害、医疗疾病、食品安全、事故、领土纷争、恐怖主义、信息安全、能源、政治和腐败等标签。每个标签下人为标注少量的领域中心词作为初始种子词。标注人员根据兴趣选取不同标签，如表2所示。每位标注人员分别在6组数据集上标注出其感兴趣的话题，构建标准的测试数据集。

表1 测试数据集

表2 用户所选兴趣标签

2.2  评价标准

本实验中使用准确率、召回率和F值对该算法进行评估。准确率表示一个被识别出的用户感兴趣的新闻话题是用户感兴趣的可能性。召回率表示识别出的用户感兴趣的新闻话题与用户实际感兴趣的话题的比率;F指标是为了同时考察召回率和准确率所提出，F指标把准确率和召回率统一到一个指标。

基于该算法在6组数据集上依次进行实验时，将上一组数据中所得用户感兴趣的新闻事件作为下一组实验所构建的事件关联网络中的历史新闻事件。例如，在数据集3上进行实验，构建事件关联网络时，将数据集1，2上所得用户感兴趣的新闻事件作为该关联网络中的历史新闻事件。

2.3  实验结果分析

在已标注的6组测试数据集上，经过参数调试，取1.4节所提聚类算法中向量相似度阈值rv=0.375、命名实体相似度阈值rn=0.475和LDA模型中主题个数K=120时，可获取最优话题聚类结果。同时，对所构建的事件关联网络，将节点间在时间、人物、地点和行为4个纬度上的关联度阈值Rt，Ro，Rl和Ra分别设置为0.325，0.15，0.15和0.275可得最佳新闻事件过滤效果。

基于以上参数设定，为验证该算法的有效性，采用用户1提供的兴趣标签，分别在6组数据集上依次进行试验。将加入事件关联网络后的用户兴趣话题发现算法与加入事件关联网络前的用户兴趣话题发现算法进行对比。加入事件关联网络前，基于式（5）计算每篇新闻兴趣度值，并对每篇新闻的兴趣度值做归一化处理，设置兴趣度阈值为0.5，大于该阈值的新闻归为用户感兴趣的新闻。两组实验结果分别如表4所示。

表4 实验结果

从以上实验结果可知，仅基于文本自身所携关键词集的用户兴趣话题发现算法准确率并不是很高，并且随着数据量的增加其准确率会明显下降。从6组测试数据上的两组实验结果可知，引入事件关联网络后，用户兴趣话题识别的准确率，召回率和F值都有明显提高;并且，随着数据量的增加，基于事件关联网络的用户兴趣话题发现算法能够维持在一个较高的准确率。通过对所识别出的用户兴趣话题内容分析，可知该算法能对相关兴趣话题有更加全面的识别，与更加精准的划分。表5为基于用户1所选兴趣标签，在数据集5，6上所获取的部分兴趣话题的代表性特征词集实例。

表5 特征词集

为进一步验证关联网络中时间、人物、地点和行为每个维度对事件关联关系的影响，在6组测试数据集上分别将式（6）中，表示时间、空间、对象和行为上的权重[a1]和[a5]，[a2]和[a6]，[a3]和[a7]，[a4]和[a8]依次设为0，其他三维取均值，并与四个维度取均值时所获实验效果进行对比。实验所得用户兴趣话题识别的准确率，召回率和F值如图1～图3所示，在充分考虑新闻事件在时间、人物、地点和行为上的关联度时可达最优的实验效果。

<E：＼王芳＼现代电子技术201506＼现代电子技术15年38卷第6期＼Image＼30T1.tif>

图1 准确率对比

<E：＼王芳＼现代电子技术201506＼现代电子技术15年38卷第6期＼Image＼30T2.tif>

图2 召回率对比

<E：＼王芳＼现代电子技术201506＼现代电子技术15年38卷第6期＼Image＼30T3.tif>

图3 F值对比

实际上，某些需关注新闻事件本身所包含的兴趣关键词并不多，主要原因为该类事件可能是由某兴趣话题所衍生出的新话题，或是与兴趣话题有着较强相互影响关系的其他话题，这时仅基于文本自身所携兴趣关键词信息，将无法准确判断该类新闻事件。引入事件关联网络后，该类新闻事件因和某些具有较高兴趣度值的事件有着较强的关联关系，基于1.3节中的链接分析模型，计算新闻的兴趣度值，获取用户感兴趣的新闻事件集。从而基于改进的聚类算法获得用户兴趣话题。综上，该算法能够有效地适用于大数据量情况下的用户兴趣话题的识别，且取得了较为理想的实验结果。

3  结  语

针对用户兴趣话题识别中话题识别不全与误差较大的问题，本文所提基于事件关联网络的用户兴趣话题发现算法中充分考虑了海量信息中新闻事件之间的复杂关联关系，将其与基于新闻文本自身所携用户兴趣信息的文本过滤算法有机结合，获取用户感兴趣的新闻事件集，有助于识别出同样需关注的相关感兴趣的话题。并提出了一种基于LDA模型的改进的single?pass聚类算法最终获取用户感兴趣的话题。实验结果表明，针对网络中的大量新闻数据，该算法只需用户选择感兴趣的相关领域标签，并通过引入基于新闻文本特有语义框架的事件关联网络，能够较为准确而全面地获取用户感兴趣的话题。

参考文献

[1] 张玥，张宏莉.基于关联性的热点话题识别[J].智能计算机与应用，2014（3）：55?59.

[2] MA Hui?fang. Hot topic extraction using time window [C]// Proceedings of 2011 International Conference on Machine Learning and Cybernetics （ICMLC）. Guilin， China： [s.n.]， 2011： 56?60.

[3] YOU Bo，  LIU Ming，  LIU Bing?quan， et al. Detecting hot topics in technology news streams [C]// Proceedings of 2012 International Conference on Machine Learning and Cybernetics （ICMLC）. Xian， China： [s.n.]， 2012： 1968?1974.

[4] ZHAO Li?yong， ZHAO Chong?chong，PANG Jing?qin， et al.  Sensitive topic detection model based on collaboration of dynamic case knowledge base [C]// Proceedings of 20th IEEE International Workshops on Enabling Technologies： Infrastructure for Collaborative Enterprises （WETICE）. Paris： IEEE， 2011： 156?161.

[5] ZHAO Li?yong， LI Ai?min. A novel system for sensitive topic detection and alert assessment [C]// Proceedings of  2011Eighth International Conference on Fuzzy Systems and Knowledge Discovery （FSKD）. Shanghai， China： [s.n.]， 2011： 1751?1755.

[6] DAI Xiang?ying， CHEN Qing?cai， WANG Xiao?long，et al. Online topic detection and tracking of financial news based on hierarchical clustering [C]// Proceedings of International Conference on Machine Learning and Cybernetics （ICMLC）. Qingdao，2010： 3341?3346.

[7] KURTZ A J， MOSTAFA J. Topic detection and interest tracking in a dynamic online news source [C]// Proceedings of Joint Conference on Digital Libraries. [S.l.]： [s.n.]， 2003： 122?124.

[8] 杨雪蓉，洪宇，马彬，等.基于核心词和实体推理的事件关系识别方法[J].中文信息学报，2014，28（2）：100?108.

[9] VETTER T， JONES M J， POGGIO T. A bootstrapping algorithm for learning linear models of object classes [C]// Proceedings of 1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Juan： IEEE， 1997： 40?46.

[10] 赵爱华，刘培玉，郑燕.基于LDA的新闻话题子话题划分方法[J].小型微型计算机系统，2013，34（4）：732?737.

[11] 林雪能.基于语义框架的话题检测与跟踪技术研究[D].北京：北京邮电大学，2012.