摘 要： 面对海量的网络新闻信息，为了能更加准确与全面地从中发现用户感兴趣的话题，提出一种基于事件关联网络的用户兴趣话题发现算法。该算法建立了代表事件之间关联关系的事件关联网络，基于该事件关联网络，采用链接分析技术度量用户对不同新闻事件感兴趣的程度，从而采用针对新闻特定语义架构的改进Single?pass聚类算法发现用户感兴趣的话题。此外，采用Bootstrapping算法，实现对相关兴趣领域词汇的语义扩展。实验表明，该算法能够更加准确而全面地获取用户感兴趣的话题。
关键词： 话题识别; 链接分析; 用户兴趣; Bootstrapping算法; 关联网络
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） 事件时间关联度计算
如果两个事件发生的时间差值在一定的范围内，则认为这两个事件在时间上是关联的。关联的强度与发生时间的间隔有关。时间的间隔越短，关联的强度越强。具体计算公式如式（1）所示：
（2） 事件人物（或机构）关联度计算
如果两个事件中涉及的人物（或机构）相同或具有较高的相似度或共现率，则认为这两个事件在人物（或机构）上是关联的，关联的强度以相同人物（或机构）为最强。基于改进的词集相似度计算公式，获取事件的人物（或机构）关联度值，具体计算公式如式（2）所示：
（3） 事件地点关联度计算
基于改进的词集相似度计算公式，获取事件的地点关联度值，具体计算公式如式（3）所示：
如果两个事件中涉及的行为相同，或是相近的，则认为这两个事件在行为上是关联的。关联的强度以相同行为为最强。事件的行为关联度值通过度量新闻事件中除表示时间、地点、人物以外的特征词间的语义相似度得到。具体计算公式如式（4）所示：
1.3 计算事件兴趣度值
基于事件关联网络计算用户对某一新闻感兴趣的程度，所采取的链接分析从两个方面展开：一是考虑当前新获取的事件间的关联影响，如果某一事件与其他用户感兴趣的新闻事件关联关系越紧密，则认为该事件的事件兴趣度值越高;二是考虑用户感兴趣的相似的历史新闻事件对当前事件的影响，认为相似的事件通常具有相近的事件兴趣度。另外，在每次对新获取的事件兴趣度度量时，将兴趣度较高的事件保留起来作为历史新闻事件。
对新获取的新闻事件，在事件关联网络中分别从时间、对象（人物或组织）、空间和行为这四个维度来分析事件的兴趣度值。首先，对网络中代表新获取新闻事件的节点赋予表示其事件兴趣度值的初始权重[SEvent（t）]，具体计算公式如式（5）所示：
基于式（6）计算事件兴趣度值，将事件兴趣度值大于特定阈值的新闻事件，归为用户感兴趣的新闻事件集，获取用户感兴趣的事件集。
1.4 用户兴趣话题识别
针对网络热点新闻话题中难以区分一个话题下的多个子话题现象，本文采用一种基于LDA（Latent Dirichlet Allocation）模型的改进的Single?Pass聚类算法对1.3节中所获取的用户感兴趣的新闻进行聚类，从而获取用户兴趣话题。应用LDA模型对新闻文档进行建模[10]，使用Single?Pass聚类算法生成话题，并针对新闻文本特有的语义架构，在Single?Pass聚类算法中的文本相似性将同时利用向量相似性和命名实体相似性。
2.1 实验数据
构建可供用户选择的兴趣分类标签集，分别有自然灾害、医疗疾病、食品安全、事故、领土纷争、恐怖主义、信息安全、能源、政治和腐败等标签。每个标签下人为标注少量的领域中心词作为初始种子词。标注人员根据兴趣选取不同标签，如表2所示。每位标注人员分别在6组数据集上标注出其感兴趣的话题，构建标准的测试数据集。
表1 测试数据集
表2 用户所选兴趣标签
2.2 评价标准
本实验中使用准确率、召回率和F值对该算法进行评估。准确率表示一个被识别出的用户感兴趣的新闻话题是用户感兴趣的可能性。召回率表示识别出的用户感兴趣的新闻话题与用户实际感兴趣的话题的比率;F指标是为了同时考察召回率和准确率所提出，F指标把准确率和召回率统一到一个指标。
2.3 实验结果分析
基于以上参数设定，为验证该算法的有效性，采用用户1提供的兴趣标签，分别在6组数据集上依次进行试验。将加入事件关联网络后的用户兴趣话题发现算法与加入事件关联网络前的用户兴趣话题发现算法进行对比。加入事件关联网络前，基于式（5）计算每篇新闻兴趣度值，并对每篇新闻的兴趣度值做归一化处理，设置兴趣度阈值为0.5，大于该阈值的新闻归为用户感兴趣的新闻。两组实验结果分别如表4所示。
表4 实验结果
从以上实验结果可知，仅基于文本自身所携关键词集的用户兴趣话题发现算法准确率并不是很高，并且随着数据量的增加其准确率会明显下降。从6组测试数据上的两组实验结果可知，引入事件关联网络后，用户兴趣话题识别的准确率，召回率和F值都有明显提高;并且，随着数据量的增加，基于事件关联网络的用户兴趣话题发现算法能够维持在一个较高的准确率。通过对所识别出的用户兴趣话题内容分析，可知该算法能对相关兴趣话题有更加全面的识别，与更加精准的划分。表5为基于用户1所选兴趣标签，在数据集5，6上所获取的部分兴趣话题的代表性特征词集实例。
表5 特征词集
E：＼王芳＼现代电子技术201506＼现代电子技术15年38卷第6期＼Image＼30T1.tif
图1 准确率对比
图2 召回率对比
E：＼王芳＼现代电子技术201506＼现代电子技术15年38卷第6期＼Image＼30T3.tif
图3 F值对比
实际上，某些需关注新闻事件本身所包含的兴趣关键词并不多，主要原因为该类事件可能是由某兴趣话题所衍生出的新话题，或是与兴趣话题有着较强相互影响关系的其他话题，这时仅基于文本自身所携兴趣关键词信息，将无法准确判断该类新闻事件。引入事件关联网络后，该类新闻事件因和某些具有较高兴趣度值的事件有着较强的关联关系，基于1.3节中的链接分析模型，计算新闻的兴趣度值，获取用户感兴趣的新闻事件集。从而基于改进的聚类算法获得用户兴趣话题。综上，该算法能够有效地适用于大数据量情况下的用户兴趣话题的识别，且取得了较为理想的实验结果。
3 结 语
针对用户兴趣话题识别中话题识别不全与误差较大的问题，本文所提基于事件关联网络的用户兴趣话题发现算法中充分考虑了海量信息中新闻事件之间的复杂关联关系，将其与基于新闻文本自身所携用户兴趣信息的文本过滤算法有机结合，获取用户感兴趣的新闻事件集，有助于识别出同样需关注的相关感兴趣的话题。并提出了一种基于LDA模型的改进的single?pass聚类算法最终获取用户感兴趣的话题。实验结果表明，针对网络中的大量新闻数据，该算法只需用户选择感兴趣的相关领域标签，并通过引入基于新闻文本特有语义框架的事件关联网络，能够较为准确而全面地获取用户感兴趣的话题。
参考文献
[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.
[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.
[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.
