论文部分内容阅读
摘要：演化趋势检测能提前获取话题的演变轨迹，有效提高决策者对于话题舆情处理的主动性和预判性。针对该需求，该文深入研究新闻话题的演变过程，利用K-means算法对专题新闻报道集进行聚类，得到新闻话题演化阶段的不同类簇，并且采用Text Rank方法提取各个新闻话题演化阶段的有效关键词，然后基于时间信息，整理生成话题演化趋势。该文以百度百科相关词条的客观描述作为评判标准进行算法评测，实验结果表明本文算法具有较高的准确性。
关键词： 话题演化； 演化趋势； 趋势检测； K-means； Text Rank
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）02-0052-03
Abstract：The evolutionary trend detection can obtain the topic evolution track in advance， and it can effectively improve the initiative and anticipation of the decision for the resolution of the public opinion on the news topic. According to the requirement， this paper studies the evolution of news topic firstly， using k-means algorithm for clustering of special news and getting different clusters for different stages of news topic evolution. And then we extract the keywords existing in various stages of news topic evolution with Text Rank model to represent the topic evolution trend based on temporal information in news pages. Finally， this paper takes the objective description of the relevant entries of Baidu encyclopedia as the evaluation criteria for the assessment of the algorithm， and the experimental results show that the algorithm is of high precision.
Key words：topic evolution； evolution trend； trend detection； K-means； Text Rank
新闻话题是指一个热点事件及与之相关的所有事件活动的集合[1]。新闻话题演化趋势是指一个新闻话题发生后，随着时间推进，事态演变从开端、发展、高潮、结局及其影响的完整过程，符合人类认识事物的逻辑顺序。按照这样的逻辑顺序整理出来的网络新闻，简洁明了地展现出新闻话题的演化规律。新闻话题的演变趋势对于网络舆情研究具有重要研究意义和应用价值，学术界近几年开始出现有关话题演化研究的工作[2-5]，并日益得到研究学者的关注。通过趋势检测能帮助人们了解新闻话题的前因后果，同时话题演化的各个阶段的差异充分体现了新闻事件的事态发展，有效提高决策者对于新闻事件处理的主动性和预判性[6]。例如，图1反映了从2002年11月至2003年3月有关SARS疫情的新闻报道中我们抽取出的前5个关键词的变化趋势，不难看出，随着时间的推移，疫情越发严重，事态越发紧急。
显然，如果政府部门能够及时、准确地掌握该话题的演化轨迹，就能针对话题各个阶段采取相应的应对措施，特别包括网络舆情的监控，有效地对重大公共突发事件进行全面管控，避免或者减轻突发事件对社会带来的不利影响。针对该需求，本文提出了面向网络新闻的话题演化趋势检测模型，通过对专题新闻聚类划分出新闻话题不同发展阶段的类簇，对新闻类簇进行关键词抽取，根据新闻报道中的时间信息，整理生成专题新闻集合的话题演变轨迹，有效挖掘出新闻话题的演化过程，有助于提高政府及相关部门应对社会突发事件的决策力。
1 话题演化趋势检测
本文根据话题演化研究的实际需要，对专题新闻文档进行话题演化趋势检测，采用图2所示的研究流程先后完成新闻文档预处理、新闻话题聚类、话题演化特征抽取以及话题演化序列构建等关键研究任务。
2.1 新闻话题聚类
对文档进行聚类时，可以根据需要将新闻话题划分成相应数量的类簇。话题演化聚类结束后，将目标新闻话题相关的新闻文档序列组织成一系列类簇，每个类簇代表一个话题演化阶段，而整个新闻文档序列则全面体现了目标新闻话题的演化轨迹。K-means算法是最为经典的基于划分的聚类方法，K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果[7]。一般都采用均方差作为标准度量函数，如公式1所示。k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开，输出结果是k个类簇的集合。
它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。假设有k个群组Si， i=1，2，...，k。μi是群组Si内所有元素xj的重心，或叫中心点。
假设要把样本集分为S个类别，算法描述如下：
（1）适当选择S个类的初始中心； （2）在第k次迭代中，对任意一个样本，求其到S个中心的距离，将该样本归到距离最短的中心所在的类；
（3）利用均值等方法更新该类的中心值；
（4）对于所有的S个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。
该算法的最大优势在于简洁快速，算法的关键在于初始中心的选择和距离公式。
2.2 话题演化特征抽取
多篇新闻报道聚类后，类簇的核心思想（话题）是由文中的词项来体现。通过词语间的语义关系分析，找出最能代表该类簇核心内容的特征词项。为了弥补传统方法（TF-IDF模型）只计算文中词语词频而没有考虑词项之间语义关系的不足，本文通过构建词项间的Text Rank模型[8]，分析多文档间词项的语义关系，抽取出有效关键词。
Text Rank与Google提出的Page Rank非常类似，它本质是在以词汇作为顶点、词之间关联作为带权或无权，有向或无向边的图上进行random walk的过程[9]。Text Rank模型表示为一个带权有向图G=（V，E），由点集合V和边集合E组成，E是V×V的子集，图中两点i，j之间的权重为Wji。对于一个给定的点Vi，In（Vi）为指向该点的点集合，Out（Vi）为点Vi指向的点集合。点Vi的分数定义为：
其中，d为阻尼因数，取值范围为0到1，代表从图中某一特定点指向其他任一点的概率。在使用Text Rank算法计算图中点的分数时，需要给图中的点指定任意的初值并递归计算知道某个词语分数收敛，收敛后每个点都获得一个分数，代表该点在图中的重要性。需要注意，点的最后分数不受给定初值的影响，点的初值只影响该算法达到收敛的迭代次数。根据基于图排序算法的基本理论，可以在具有语义关系的词语之间连线构建Text Rank模型。根据词语之间的相互“投票”，递归计算词语分数，选择分数较大的词语为重要词语，其中不和任何词语有连线的词语为孤立点。例如，“2009年鹤岗新兴煤矿爆炸事故”专题新闻文本的词语序列，通过Text Rank模型计算得到词项间的关联关系（图3所示）。
构建Text Rank模型是根据待选关键词词语之间的语义相似关系大小来决定是否在两个词语之间建立边。因此，Text Rank图是带权无向图，边的权重为两个词语之间的关联度，通过词语间的投票递归计算出权重，关键词的选取按分数序列从高到低选择，选取范围可以根据需要设置。
2.3 话题演化序列构建
新闻作为一种流数据，新闻话题具有明确的动态变化性，话题随着时间的发展而演化，反映了新闻事态阶段性渐变的过程。当用户关注某个新闻话题时，都希望能从了解新闻话题事件的缘由开始，逐步深入到事件的发展、高潮，最终到话题事件的结束，整个逻辑顺序就是新闻话题完整的动态演化[10]。本文将对基于时间模式和基于逻辑模式的话题演化序列构建展开研究。
网络新闻报道具有高时效性的特点，在构建基于时间模式的话题演化序列时，本文采用新闻发布时间作为构建的标准。例如，对“2009年鹤岗新兴煤矿爆炸事故”的142篇新闻报道，统计整理出该话题随时间渐变的完整过程，如图4所示。从基于时间的演化轨迹不难发现随着时间的推移，新闻话题发生演变，事件中心发生改变，主要体现在话题特征（关键词）的变化。
新闻话题聚类后形成不同的类簇，但由于特定话题相关的新闻报道的主题是一致的，因此其中类簇中包含大量的“共性词”。例如“新兴煤矿瓦斯爆炸事故”专题新闻聚类后形成五个类簇，在五个类簇中的关键词中，“事故、煤矿、爆炸、矿工”等词语的分数都较高，属于该主题的共性关键词。因此，在分析每个类簇的特征时，选择除去“共性词”以外评分较高的词语作为这类新闻报道特征词。同时，本文根据百度百科中相应话题（事件）的话题目录（如图5所示）为标准构建基于逻辑模式的话题演化序列。显然，新闻话题的内容描述是按照事件发展的逻辑顺序建立的，因此，基于话题目录构建话题类簇能够直接反映话题的演化过程。
3 实验结果与分析
为了评测本文算法的有效性，我们利用从网易爬取的同一个专题（“2009年鹤岗新兴煤矿爆炸事故”）的新闻进行话题演化趋势检测算法的实验分析。数据集包括同一专题下12个月（2009年11月21日至2010年12月2日）的142篇新闻文档，评测标准是通过人工对比在线知识库（百度百科）相应话题的内容描述进行评判。
3.1 话题演化序列检测结果
在构建基于时间模式的话题演化序列时，我们采用新闻发布时间作为构建的标准，表1给出了基于时间模式的话题“2009年鹤岗新兴煤矿爆炸事故”随时间演变的检测结果。
随着时间的推移，新闻话题发生演变，其特征词也在发生变化，2009年11月21日至2009年11月24日，重大事故发生，迅速成为社会热点，人们对事故原因调查、搜救、伤员医治情况比较关心，国家相关部门也很重视，该时段的新闻报道占比高达74.7%。随着事态发展，人们的关注重心转移到了赔偿、国家相关部门的措施上，关注度有所下降。最后，相关责任人的处理，媒体的报道量较少。
不难发现，由于聚类模式的差异导致两种检测方法得到的类簇具有明显区别，在话题特征的选择上存在较大出入。因此，为了进一步评测两种方法的性能优劣，我们对基于时间模式的话题演化趋势检测方法和基于逻辑模式的话题演化趋势检测方法进行了对比分析，具体讨论见下一节。
3.2 对比实验分析
首先，我们根据百度百科的相关话题内容对两种逻辑模式的话题演化趋势检测方法进行了对比实验分析，结果如表3所示。
观察表3的数据可以发现，基于逻辑模式的话题演化趋势检测结果具有一定的合理性，性能较基于时间模式的话题演化趋势检测方法有大幅提升。同时，将基于逻辑模式的话题演化序列与百度百科相关话题的描述进行对比分析，不难发现，该序列对于整个新闻话题的“现场工作指导”、“搜救”、“事故原因调查”、“赔偿”方面的内容都有所覆盖，但在“善后”的最终伤亡数据方面的话题相关性还有所欠缺。另外，由于抽取关键词以后，话题由权重较高的独立词组集合表示，事实数据没有具体呈现。因此，话题演化序列在展现方式上没有对伤亡人员数字、赔偿金额方面做详细阐述。然而，本文认为基于逻辑模式的话题演化趋势检测结果的重点是总结出新闻话题的发展阶段，对专题新闻进行整理，去除冗余报道，让用户了解到最直观简洁的而又最全面的新闻报道。因此该方法在实现自动化分析新闻话题演化趋势方面具有积极意义。 参考文献：
[1] 赵华，赵铁军，于浩. 面向动态演化的话题检测研究[J]. 高技术通讯，2006，16（12）：1230-1235.
[2] 于满泉， 骆卫华， 许洪波， 等. 话题识别与跟踪中的层次化话题识别技术研究[J]. 计算机研究与发展， 2006， 43（3）： 489-495.
[3] Blei D， Lafferty J. Dynamic Topic Models[C]//Proceedings of the International Conference on Machine Learning （ICML）， Pittsburgh， PA， USA， 2006， 113-120.
[4] Li B， Li W， Li Q. Enhancing Topic Tracking with Temporal Information[C]//Proceedings of ACM SIGIR， Seattle， Washington， USA， 2006， 667-668.
[5] Wang X， McCallum A. Topic over Time： A Non-markov Continuous-time Model of Topical Trends[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， Philadelphia， PA， USA， 2006， 424-433.
[6] 洪宇，张宇，刘挺，李生. 话题检测与跟踪的评测及研究综述[J]. 中文信息学报，2007， 21（6）： 71-87.
[7] Yu Bao Liu， Jia-Rong Cai， Jian Yin， Ada Wai-Chee Fu. Clustering Text Data Streams[J]， JCST， 2008， 23（1）： 112-128.
[8] 陈宏，陈伟. 基于突发特征分析的事件检测[J]. 计算机应用研究，2011， 28（1）： 117-120.
[9] Pearson， K. The Problem of the Random Walk[J]. Nature. 1905， 72：294.
[10] 赵旭剑. 中文新闻话题动态演化及其关键技术研究[D]. 中国科学技术大学，2012.
关键词： 话题演化； 演化趋势； 趋势检测； K-means； Text Rank
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）02-0052-03
Abstract：The evolutionary trend detection can obtain the topic evolution track in advance， and it can effectively improve the initiative and anticipation of the decision for the resolution of the public opinion on the news topic. According to the requirement， this paper studies the evolution of news topic firstly， using k-means algorithm for clustering of special news and getting different clusters for different stages of news topic evolution. And then we extract the keywords existing in various stages of news topic evolution with Text Rank model to represent the topic evolution trend based on temporal information in news pages. Finally， this paper takes the objective description of the relevant entries of Baidu encyclopedia as the evaluation criteria for the assessment of the algorithm， and the experimental results show that the algorithm is of high precision.
Key words：topic evolution； evolution trend； trend detection； K-means； Text Rank
新闻话题是指一个热点事件及与之相关的所有事件活动的集合[1]。新闻话题演化趋势是指一个新闻话题发生后，随着时间推进，事态演变从开端、发展、高潮、结局及其影响的完整过程，符合人类认识事物的逻辑顺序。按照这样的逻辑顺序整理出来的网络新闻，简洁明了地展现出新闻话题的演化规律。新闻话题的演变趋势对于网络舆情研究具有重要研究意义和应用价值，学术界近几年开始出现有关话题演化研究的工作[2-5]，并日益得到研究学者的关注。通过趋势检测能帮助人们了解新闻话题的前因后果，同时话题演化的各个阶段的差异充分体现了新闻事件的事态发展，有效提高决策者对于新闻事件处理的主动性和预判性[6]。例如，图1反映了从2002年11月至2003年3月有关SARS疫情的新闻报道中我们抽取出的前5个关键词的变化趋势，不难看出，随着时间的推移，疫情越发严重，事态越发紧急。
显然，如果政府部门能够及时、准确地掌握该话题的演化轨迹，就能针对话题各个阶段采取相应的应对措施，特别包括网络舆情的监控，有效地对重大公共突发事件进行全面管控，避免或者减轻突发事件对社会带来的不利影响。针对该需求，本文提出了面向网络新闻的话题演化趋势检测模型，通过对专题新闻聚类划分出新闻话题不同发展阶段的类簇，对新闻类簇进行关键词抽取，根据新闻报道中的时间信息，整理生成专题新闻集合的话题演变轨迹，有效挖掘出新闻话题的演化过程，有助于提高政府及相关部门应对社会突发事件的决策力。
1 话题演化趋势检测
本文根据话题演化研究的实际需要，对专题新闻文档进行话题演化趋势检测，采用图2所示的研究流程先后完成新闻文档预处理、新闻话题聚类、话题演化特征抽取以及话题演化序列构建等关键研究任务。
2.1 新闻话题聚类
对文档进行聚类时，可以根据需要将新闻话题划分成相应数量的类簇。话题演化聚类结束后，将目标新闻话题相关的新闻文档序列组织成一系列类簇，每个类簇代表一个话题演化阶段，而整个新闻文档序列则全面体现了目标新闻话题的演化轨迹。K-means算法是最为经典的基于划分的聚类方法，K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果[7]。一般都采用均方差作为标准度量函数，如公式1所示。k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开，输出结果是k个类簇的集合。
它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。假设有k个群组Si， i=1，2，...，k。μi是群组Si内所有元素xj的重心，或叫中心点。
假设要把样本集分为S个类别，算法描述如下：
（1）适当选择S个类的初始中心； （2）在第k次迭代中，对任意一个样本，求其到S个中心的距离，将该样本归到距离最短的中心所在的类；
（3）利用均值等方法更新该类的中心值；
（4）对于所有的S个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。
该算法的最大优势在于简洁快速，算法的关键在于初始中心的选择和距离公式。
2.2 话题演化特征抽取
多篇新闻报道聚类后，类簇的核心思想（话题）是由文中的词项来体现。通过词语间的语义关系分析，找出最能代表该类簇核心内容的特征词项。为了弥补传统方法（TF-IDF模型）只计算文中词语词频而没有考虑词项之间语义关系的不足，本文通过构建词项间的Text Rank模型[8]，分析多文档间词项的语义关系，抽取出有效关键词。
Text Rank与Google提出的Page Rank非常类似，它本质是在以词汇作为顶点、词之间关联作为带权或无权，有向或无向边的图上进行random walk的过程[9]。Text Rank模型表示为一个带权有向图G=（V，E），由点集合V和边集合E组成，E是V×V的子集，图中两点i，j之间的权重为Wji。对于一个给定的点Vi，In（Vi）为指向该点的点集合，Out（Vi）为点Vi指向的点集合。点Vi的分数定义为：
其中，d为阻尼因数，取值范围为0到1，代表从图中某一特定点指向其他任一点的概率。在使用Text Rank算法计算图中点的分数时，需要给图中的点指定任意的初值并递归计算知道某个词语分数收敛，收敛后每个点都获得一个分数，代表该点在图中的重要性。需要注意，点的最后分数不受给定初值的影响，点的初值只影响该算法达到收敛的迭代次数。根据基于图排序算法的基本理论，可以在具有语义关系的词语之间连线构建Text Rank模型。根据词语之间的相互“投票”，递归计算词语分数，选择分数较大的词语为重要词语，其中不和任何词语有连线的词语为孤立点。例如，“2009年鹤岗新兴煤矿爆炸事故”专题新闻文本的词语序列，通过Text Rank模型计算得到词项间的关联关系（图3所示）。
构建Text Rank模型是根据待选关键词词语之间的语义相似关系大小来决定是否在两个词语之间建立边。因此，Text Rank图是带权无向图，边的权重为两个词语之间的关联度，通过词语间的投票递归计算出权重，关键词的选取按分数序列从高到低选择，选取范围可以根据需要设置。
2.3 话题演化序列构建
新闻作为一种流数据，新闻话题具有明确的动态变化性，话题随着时间的发展而演化，反映了新闻事态阶段性渐变的过程。当用户关注某个新闻话题时，都希望能从了解新闻话题事件的缘由开始，逐步深入到事件的发展、高潮，最终到话题事件的结束，整个逻辑顺序就是新闻话题完整的动态演化[10]。本文将对基于时间模式和基于逻辑模式的话题演化序列构建展开研究。
网络新闻报道具有高时效性的特点，在构建基于时间模式的话题演化序列时，本文采用新闻发布时间作为构建的标准。例如，对“2009年鹤岗新兴煤矿爆炸事故”的142篇新闻报道，统计整理出该话题随时间渐变的完整过程，如图4所示。从基于时间的演化轨迹不难发现随着时间的推移，新闻话题发生演变，事件中心发生改变，主要体现在话题特征（关键词）的变化。
新闻话题聚类后形成不同的类簇，但由于特定话题相关的新闻报道的主题是一致的，因此其中类簇中包含大量的“共性词”。例如“新兴煤矿瓦斯爆炸事故”专题新闻聚类后形成五个类簇，在五个类簇中的关键词中，“事故、煤矿、爆炸、矿工”等词语的分数都较高，属于该主题的共性关键词。因此，在分析每个类簇的特征时，选择除去“共性词”以外评分较高的词语作为这类新闻报道特征词。同时，本文根据百度百科中相应话题（事件）的话题目录（如图5所示）为标准构建基于逻辑模式的话题演化序列。显然，新闻话题的内容描述是按照事件发展的逻辑顺序建立的，因此，基于话题目录构建话题类簇能够直接反映话题的演化过程。
3 实验结果与分析
为了评测本文算法的有效性，我们利用从网易爬取的同一个专题（“2009年鹤岗新兴煤矿爆炸事故”）的新闻进行话题演化趋势检测算法的实验分析。数据集包括同一专题下12个月（2009年11月21日至2010年12月2日）的142篇新闻文档，评测标准是通过人工对比在线知识库（百度百科）相应话题的内容描述进行评判。
3.1 话题演化序列检测结果
在构建基于时间模式的话题演化序列时，我们采用新闻发布时间作为构建的标准，表1给出了基于时间模式的话题“2009年鹤岗新兴煤矿爆炸事故”随时间演变的检测结果。
随着时间的推移，新闻话题发生演变，其特征词也在发生变化，2009年11月21日至2009年11月24日，重大事故发生，迅速成为社会热点，人们对事故原因调查、搜救、伤员医治情况比较关心，国家相关部门也很重视，该时段的新闻报道占比高达74.7%。随着事态发展，人们的关注重心转移到了赔偿、国家相关部门的措施上，关注度有所下降。最后，相关责任人的处理，媒体的报道量较少。
不难发现，由于聚类模式的差异导致两种检测方法得到的类簇具有明显区别，在话题特征的选择上存在较大出入。因此，为了进一步评测两种方法的性能优劣，我们对基于时间模式的话题演化趋势检测方法和基于逻辑模式的话题演化趋势检测方法进行了对比分析，具体讨论见下一节。
3.2 对比实验分析
首先，我们根据百度百科的相关话题内容对两种逻辑模式的话题演化趋势检测方法进行了对比实验分析，结果如表3所示。
观察表3的数据可以发现，基于逻辑模式的话题演化趋势检测结果具有一定的合理性，性能较基于时间模式的话题演化趋势检测方法有大幅提升。同时，将基于逻辑模式的话题演化序列与百度百科相关话题的描述进行对比分析，不难发现，该序列对于整个新闻话题的“现场工作指导”、“搜救”、“事故原因调查”、“赔偿”方面的内容都有所覆盖，但在“善后”的最终伤亡数据方面的话题相关性还有所欠缺。另外，由于抽取关键词以后，话题由权重较高的独立词组集合表示，事实数据没有具体呈现。因此，话题演化序列在展现方式上没有对伤亡人员数字、赔偿金额方面做详细阐述。然而，本文认为基于逻辑模式的话题演化趋势检测结果的重点是总结出新闻话题的发展阶段，对专题新闻进行整理，去除冗余报道，让用户了解到最直观简洁的而又最全面的新闻报道。因此该方法在实现自动化分析新闻话题演化趋势方面具有积极意义。 参考文献：
[1] 赵华，赵铁军，于浩. 面向动态演化的话题检测研究[J]. 高技术通讯，2006，16（12）：1230-1235.
[2] 于满泉， 骆卫华， 许洪波， 等. 话题识别与跟踪中的层次化话题识别技术研究[J]. 计算机研究与发展， 2006， 43（3）： 489-495.
[3] Blei D， Lafferty J. Dynamic Topic Models[C]//Proceedings of the International Conference on Machine Learning （ICML）， Pittsburgh， PA， USA， 2006， 113-120.
[4] Li B， Li W， Li Q. Enhancing Topic Tracking with Temporal Information[C]//Proceedings of ACM SIGIR， Seattle， Washington， USA， 2006， 667-668.
[5] Wang X， McCallum A. Topic over Time： A Non-markov Continuous-time Model of Topical Trends[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， Philadelphia， PA， USA， 2006， 424-433.
[6] 洪宇，张宇，刘挺，李生. 话题检测与跟踪的评测及研究综述[J]. 中文信息学报，2007， 21（6）： 71-87.
[7] Yu Bao Liu， Jia-Rong Cai， Jian Yin， Ada Wai-Chee Fu. Clustering Text Data Streams[J]， JCST， 2008， 23（1）： 112-128.
[8] 陈宏，陈伟. 基于突发特征分析的事件检测[J]. 计算机应用研究，2011， 28（1）： 117-120.
[9] Pearson， K. The Problem of the Random Walk[J]. Nature. 1905， 72：294.
[10] 赵旭剑. 中文新闻话题动态演化及其关键技术研究[D]. 中国科学技术大学，2012.