面对大量信息, 读者容易迷失在局部的信息中, 逐渐丧失对信息的全局把控。因此, 构建新闻脉络链成为当今迫切需要解决的问题。构建新闻脉络链是对新闻事件故事发展脉络结构的捕捉, 因此新闻故事发展需要具备很好的逻辑发展特性和可解释性机制。现有脉络链构建研究存在以下三方面的问题: 1) 脉络陷入局部, 没有全局观; 2) 脉络关注主要集中在文档重要性、相关性以及相似性等一维内容层面, 忽视文档之间的二维逻辑连贯语义层面; 3)脉络构建复杂度高, 多数研究为保证脉络的全局特性而对整个数据集进行多次迭代, 缺乏对数据集大小进行有效降级。

基于以上问题, 本文提出一种新闻脉络链构建方法, 将脉络构建视为词覆盖问题, 在依赖新闻内在逻辑性进行词覆盖的同时, 也完成了结构化逻辑且可解释的脉络构建。本文算法可根据读者感兴趣的新闻热点事件, 自动生成该新闻事件的新闻脉络链, 能够帮助读者把控新闻事件的全局发展脉络。例如, 读者对马航(MH370)事件感兴趣, 那么算法给出的可能输出如图1所示。

1 相关工作

信息过载使得研究人员开始寻找各种信息中隐含的故事发展脉络, 比如微博^[1-4], 新闻^[5-7], 论 文^[8-9]以及邮件^[10]。故事生成^[11-12]较早开始对故事脉络进行定义和建模, 但只关注规则模版的设定及其推演。事件检测^[13-14]尝试发现信息中隐含的新闻事件, 但并不尝试将其连接起来形成完整的脉络发展。文献[2-3]尝试解决脉络的连接问题, 但基于局部贪心的思想缺乏全局观。文献[5]构建的是全局脉络, 其代价是需对整个候选新闻集合进行迭代, 严重影响算法的可扩展性。事件追踪^[15]利用有监督的机器学习算法, 将新闻划分到大的新闻子类, 但是需要进行人工标注, 难度大。事件追踪与TDT^[16](主题检测和追踪)的思想类似, 不同之处在于后者将事件追踪抽象为主题追踪。TDT致力于生成文本的故事链, 主要包括五大任务: 故事分段、主题追踪、主题检测、起始故事检测以及链接检测。大部分TDT的研究主要关注文本相关性或者相似性, 在其基础上进行文本分类和聚类, 并未考虑文本间的逻辑转换关系^[17]。文献[18]通过考虑文本间相互作用构建主题结构图, 基于结构图对主题变化趋势进行追踪。类似地, 文献[13-19]通过发现新闻事件子类, 并利用其相互依赖关系构建图结构(动态主题模型), 但是均未考虑图结构的连贯性问题。

MDS (多文本总结)通过选取代表性的句子, 以时序的方式构建时间轴, 完成对文档集合的总结, 为构建脉络提供了一个文本总结的新思路。句子的选择标准方法有很多种, 基本上分为三大类: 一类是句子本身的属性, 比如文献[20]用句子的信息含量(通过最大化信息含量高的词), 文献[21-22]用句子的相关性、覆盖性、连贯性以及多样性, 文献[23]用句子的不确定性, 文献[24]用句子的代表性和差异性; 另一类是句子的结构属性, 文献[19-25]通过构建句子图谱, 使用图谱的中心化句子节点作为候选句子; 第三类是前两类的综合, 文献[26-27]通过矩阵分解对句子进行潜在的语义分析。这三大类方法(包括第三类的潜在语义)以及TDT都无法给生成的脉络结果提供可解释性, 而缺乏可解释机制会大大增加对脉络链的理解难度。

2 算法总体设计 2.1 词覆盖方法

典型的搜索查询任务流程如下: 给定查询词集合q, 搜索引擎在数据库中逐个扫描并返回覆盖查询词q的文档集合。简单归纳可知, 搜索引擎的工作实质上是基于查询词的文档覆盖。新闻脉络链, 其反映的是新闻事件的逻辑发展, 与搜索引擎有相同亦有不同: 相同之处是都可看成文档覆盖问题; 不同之处是文档覆盖的查询词不再是用户输入的新闻事件查询词, 取而代之的是能反映该查询词所对应新闻事件新闻脉络的词集合Q。一旦结果文档集合D能覆盖反映该新闻事件脉络的词集合Q, 那么文档集合D即是结果新闻脉络。对比异同, 新闻脉络链的构建引擎实质上是附加查询词扩展层的搜索引擎。

2.2 设计框架

基于查询词返回结果文档的研究已经很成熟, 因此构建新闻脉络图的关键是快速定位词集合Q, 即完成从新闻事件查询词q到Q的扩展。Q很难通过q的直接扩展得到, 因为在未彻底了解新闻事件前, 无法预先得知Q; 即便了解, 由于理解上的主观性, 也无法确切得知Q。因此, Q只是概念化的词集合, 无从获知。若Q已知, 则新闻脉络已知。由于无法“正面”得知Q, 本文则通过采用不断缩小候选词集合的方法, 不断逼近真实的Q, 从而间接获取Q。

新闻脉络链由许多形如A→B的逻辑转移组成, 其中新闻文档A和B是逻辑转移主体, 逻辑转移词集合“→”代表转移依据, 因此A→B描述新闻文档A依据逻辑词集合W转移到新闻文档B。本算法预先锁定包含逻辑转移主体的文档集合D_c={d₁, d₂, …, d_c}, 然后进一步筛选逻辑主体D_L={d₁, d₂,…, d_m}, 最后具体化转移依据得出最终的W_L={w₁, w₂,…, w_n}, 在逼近Q的同时也完成覆盖Q且结构化Q的过程, 具体流程如图2所示。

2.3 算法描述

2.3.1 时间评论聚类算法

某段时间特别受关注的新闻很可能是新闻事件的转折点, 即所需捕捉候选新闻文档集合, 因此可利用新闻报道的用户关注度来定位新闻事件转折点。用户关注行为有强弱两种: 强用户评论行为和弱用户浏览行为, 一般浏览行为很难准确获取。文献[28]表明用户的评论和浏览行为存在强一致性, 即评论行为越多, 浏览行为也越多, 因此可通过度量评论行为来达到度量评论和浏览行为的目的。

K-means算法^[29]是最简单易行的聚类算法之一, 它能够快速有效地处理大规模数据, 运用十分广泛。本文用二维元组<评论数量, 评论时间>表示样本点xⁱ, 采用K-means对样本集合{x¹, x², …, xⁿ}进行聚类, 剔除小于10个样本的小型类别, 保留剩余类别所有样本点。

2.3.2 文档建模算法

主题模型pLSI^[30]和LDA^[31]广泛用于文档建模领域。给定一篇文档, 形式化描述如下:

$ D = T + N, $

其中T代表低秩主题部分, N代表高斯噪音部分。

但这并不总符合现实情况。如图3(a)所示, 文档中常出现一些频率异常高的词, 因此词频分布误差并不是主题模型所假设的噪音方差小且服从高斯分布, 而是高频噪音误差。高频噪音误差并非没有价值, 相反地, 它恰恰最能反映文档间的差异性。基于此, 如图3(b)所示, 对文档进行低秩主题部分-稀疏高频部分建模, 形式化表示如下:

$ D = A + B, $

其中A代表低秩主题部分, B代表稀疏高频部分。为便于后续描述, 将A表述为主题部分, B表述为稀疏部分。

文档集合D的分离过程是在尽可能用低秩主题模型拟合文档集合的基础上, 最小化S中的非零项个数。只有在尽可能剥离共有主题部分之后, S才能准确描述文档集合中文档之间的差异性部分, 因此分离定义如下:

$ \mathop {\min }\limits_{A,B} \left\{ {\left| {\left| S \right|} \right|{\mathit{\pmb{: A}}} + {\mathit{\pmb{B}}} = {\mathit{\pmb{D }}}且{\rm{ Rank}}({\mathit{\pmb{B}}}) < K} \right\}, $

(1)

其中D∈N^m×n是待分解文档-词频矩阵, m和n分别是文档和词的数量, A, B∈R^m×n对应于主题和稀疏部分, ||·||计算矩阵中非零项的数量。式(1)假设给定文档集合在主题数为K的情况下可对原文档集合进行足够好的描述。最后, 采用RPCA^[32](健壮主成分分析)求解式(1), 得出A和B。

2.3.3 随机游走算法

关系作用传递分为显式和隐式: 显式关系传递指两篇文档包含相同的词; 隐式关系传递指两篇文档中的前一篇包含这个词, 而后一篇文档缺失这个词。后者的隐式关系传递是指同一隐含语义, 在文档中因作者、文章题材等影响而会采取不同表达。比如一篇文章包含律师, 另外一篇包含诉讼或者法庭, 即使后一篇文档通篇不包含律师这个词, 但两篇文章本质上仍隐含转移关系。本文采用随机游走模型来对文档的显式和隐式传递关系进行建模, 如图4(a)所示, 分析d₁→d₄, 显示关系传递为d₁→w₂→d₄, 隐式关系传递为d₁→w₁→d₃→w₄→d₄ 和d₁→w₁→d₃→w₃→d₄。可以看出, 随机游走模型能很好地融合显式和隐式文档关系。

文献[5]定义Influence (d_i, d_j|w), 即两篇文档i和j基于词w的跳转概率, 通过Influence将转移依据在两篇文档转移中的影响进行量化。为了计算Influence (d_i, d_j|w), 文献[5]的定义如下:

$ \prod\nolimits_i {(v) = \varepsilon \cdot 1(v = {d_i}) + (1 - \varepsilon )\sum\nolimits_{(u,\;\;v) \in E} {\prod\nolimits_i {(u)P(v|u)} } } , $

(2)

$ \prod\nolimits_i {^w(v) = \varepsilon \cdot 1(v = {d_i}) + (1 - \varepsilon )\sum\nolimits_{(u,\;v) \in E} {\prod\nolimits_i {(u){P^w}(v|u)} } } , $

(3)

其中∏_i(v)为随机游走的驻留分布, e为控制参数, P(v|u) 为v到u的概率。如果v是文档, u是词, 则P(v|u)是词u在文档中的tf-idf值; 如果v是词, u是文档, 则P(v|u)是归一化u在所有文档中的tf-idf值后得出的值。P^w(v|u)是去除节点w的出边(原始w的出边变为指向w自己, 不再传递重要性给其他节点)后的P(v|u), 即不通过w节点, 节点v到u的概率, 那么通过式(4)即可间接获取Influence(d_i, d_j|w), 即词在文档i和j转移中的贡献, 见图4(b)。本文研究如何进行逻辑转移。鉴于逻辑转移更多发生在文档间的差异部分, 因此两篇文档间发生转移的词w被限定在文档的差异部分包含的词, 这样得出的Influence (d_i, d_j|w) 可更加准确地描述词在文档i和j转移中的逻辑贡献。由于差异部分的稀疏性质, 算法的复杂度可进一步降低, 可扩展性得到加强。

$ {\rm{Influence}}\;({d_i},\;{d_j}|w) = \prod\nolimits_i {({d_j}) - } \prod\nolimits_i {^w({d_j})} \;. $

(4)

2.3.4 链生成算法

两篇文档发生逻辑转移, 相似性是必要条件, 充分条件是文档间必须有差异, 过于相似或者过于不相似都将导致文档间相似和差异的比例不均衡, 直接影响文档间转移的质量。过于相似文档间发生转移类似文本主题聚类, 而聚类并不能反映其逻辑意义。过于不相似文档间发生转移类似随机选取文档进行转移, 得出的结果将因为噪音的影响而失真。因此本文将文档的主题相似作为判定转移的条件(降低噪音), 之后通过差异部分具体量化转移。这种策略将大幅度提高转移结果的准确性。新闻脉络链由多个逻辑转移构成, 因此本算法通过计算文档间主题相似度, 在此基础上建立时序有向图。如图5(a)所示, 节点代表文档, 边的粗细是定义在主题空间的节点间正弦距离, 定义如下:

$ {\rm{sim}}({\bar d_i},\;{\bar d_j}) = \frac{{\mathop \sum \nolimits_{k = 1}^n {d_{ik}} \cdot {d_{jk}}}}{{\sqrt {\mathop \sum \nolimits_{k = 1}^n {d_{ik}} \cdot {d_{ik}}} \sqrt {\mathop \sum \nolimits_{k = 1}^n {d_{jk}} \cdot {d_{jk}}} }}, $

(5)

其中d_i是文档在主题部分A所构成的主题词空间的映射, 也即A_i (矩阵A中的第i行), d_ik是A_ik。过强或过弱的边被剔除(灰色), 假定保留sim(d_i, d_j)∈(α, β)的边, 其中α, β∈(0, 1), 得到有向时序图的两条候选链(图5(b)), 最后筛选出具有最高逻辑连贯指标的结果链。根据木桶效应, 事物逻辑连贯由组成该事物的多个部分中逻辑连贯性最薄弱一环决定, 因此文献[5]将其定义如下:

$ \begin{array}{l} {\rm{Coherence}}\;({d_1},\;...,\;{d_n}) = \mathop {\min }\limits_{i = 1,\;...,\;n} \sum\nolimits_w {{\rm{Influence}}} ({d_i},\;{d_{i + 1}}|w) \cdot \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;1(w \in {d_i} \cap {d_{i + 1}}). \end{array} $

(6)

给定起点文档和重点文档, 即可根据逻辑性指标, 在时序图中遍历找到最佳脉络图, 并附加可解释的转移依据。

3 实验设计 3.1 数据集

本实验使用的数据集来自新浪网新闻专题搜索引擎, 通过抓取基于关键字MH370搜索返回的结果, 得到与马航相关的新闻事件文档集合。对新闻去重后, 对文档集合的评论信息进行分析抓取, 形成最终的原始文档集合, 具体描述见表1。

3.2 时间评论聚类算法有效性验证

通过对新闻-用户评论数据进行K-means聚类分析, 将得到的结果与参照的人工编辑脉络链进行对比, 对假设“某新闻是新闻事件发展转折点的可能性大小正比于用户对该新闻的关注行为强度”做可行性假设。剔除评论数低于1500的样本点, 对原始数据进行聚类并得到多个时间簇, 时间簇所包含的时间点(以天为单位)即预测的新闻核心事件发生日期。对比人工编辑新闻链中新闻文档发表时间发现, 聚类得到的新闻转折点发生时间与人工编辑的基本上吻合, 如图6所示。

从3月8日到12月24日, 共有291个日期, 人工编辑提供17个标准日期答案, 聚类算法提供58个预测日期并命中其中16个, 唯一未命中的是5月9日, 但算法提供非常接近的预测日期5月10日, 因此预测错误可能由新闻的延迟导致。为定量描述聚类算法有效性, 定义召回率和准确率的指标如下:

$ 召回率\;{\rm{ = }}\frac{{算法命中的日期个数}}{{标准答案日期个数}}, $

(7)

$ 准确率\;{\rm{ = }}\frac{{算法命中的日期个数}}{{算法给出的总共预测日期个数}}. $

(8)

通过计算可知, 未做预测之前召回率为1, 准确率为5.84%; 经过利用用户评论信息聚类预测后, 召回率为94.12%, 基本上接近1, 准确率为27.59%, 数据集合数量由2895变为494, 缩小至原来的1/5。在保证不丢失新闻脉络信息的同时, 大大减少了候选新闻数据集合的大小, 数据集的数量级也有大幅度降低, 提升了算法的可扩展性。

3.3 文档建模效果分析

本节实验数据集合为时间聚类方法得到的候选新闻集合。过滤掉词频出现小于10的低频词, 将实验数据集转换成为D∈N^494×1010, 通过RPCA得到矩阵A和B, 预处理新闻集合的具体描述见表2。

图7描述的是源文档d₀: 《马航机场员工推搡中国记者大声骂人竖中指》。利用随机游走模型计算文档d₀到另两篇文档{d₁, d₂}转移中转移依据w(比如推搡)的影响, 可以看出d₀→d₁基于每一个词转移的概率都接近0, 结果是合理的。d₀→d₂基于每个词转移的概率之间差别较大, 选取其中几个影响较大的词: 推搡、员工、中国、道歉、马航, 可以看出结果词能较好地解释两篇文章转移依据(显式和隐式)。至于“记者”没有出现在转移依据中, 是因为“记者”在新闻文档中虽然出现频次高但意义小, 比如“据新华社记者报道”和“记者某某报道”, 因此在分词预处理阶段, 连同词“报道”同时被过滤掉, 不参与后续转移。

3.4 链评价

实验设定α=0.5, β=0.8, 得出候选结果链条Coherence指标最高为0.01008646。限于篇幅, 只列出“本文算法_结果2”及其序号5→序号6文档的转移依据“疑似(7.0305495×10^-4), 残骸(6.433595×10^-4), 祈祷(3.8924068×10^-4), 并非(3.8924022×10^-4), 海面(3.1231903×10^-4)”, 词后的数字代表该词在文档间转移的量化影响, 具体结果如图8所示。

新闻事件逻辑脉络链具有很强主观特性, 比如链的可读性、逻辑性以及可解释性等, 无法类比搜索引擎或者推荐引擎评价的标准和客观。ROUGH系列评价指标是多文本总结领域常用指标, 但它较主观, 不能反映真实的效果。鉴于本文构建脉络链的高主观特性(后续实验已证实, 不同用户对同一脉络结果打分相差很大), 本文通过用户调查对生成的链进行评价。

脉络链构建的工程性质使得相关算法虽然多, 但基本上不公开源码, 因此论文方法不可再现。为避免因个人工程实现原因导致对比算法效果降低, 多角度比较算法效果, 本文算法与3个经典的算法进行比较, 三者分别代表随机性、主题聚类特性以及相关性。

1) 随机选取算法: 代表随机性的思想, 随机选取固定数目的新闻文档作为脉络链的候选文档。

2) K-means聚类算法: 代表主题聚类特性, 在话题追踪领域广泛应用。通过将文档利用主题分量进行描述, 并基于这个主题向量空间进行K-means聚类, 得出聚类簇, 然后选择最靠近类簇中心的文档作为脉络链的候选文档。

3) 最短路径算法: 通过文档的主题余弦相似度构建一个图, 权重为相似度, 寻找权重最大的路径, 这是一个局部算法。

4) 本文算法: 设定链的长度为6, 生成候选链。

本文对20名大学生进行双盲问卷调查, 为其提供5个待评价脉络链(图8及附录), 受调查者需回答两个问题: 一个是知识量, 即读完能够对事件脉络的了解程度; 另一个是逻辑连贯性, 即展示脉络链的逻辑连贯程度。二者分数都是1~5之间的整数。为保证问卷调查的公平和客观, 本文给出两个待评估的链(未将脉络链的可解释加上, 若加上, 效果会更好), 其余3个算法各给出一条脉络链, 并提供人工编辑的脉络链供参考, 结果见表3。

从实验结果可看出, 本文算法得出的两个脉络结果均在知识量方面高于或者略高于其他算法, 逻辑连贯性的指标远高于其他算法, 说明本文算法能在保证较高的知识量的前提下, 较好地捕捉脉络发展之间的逻辑性, 其他结果见附录。

4 结语

基于现有脉络图存在的三方面不足, 本文从词覆盖角度考虑逻辑脉络链生成问题。在保证新闻脉络基本无损的情况下, 利用新闻评论信息对数据集进行5倍压缩。通过对文档进行RPCA建模, 利用主题相似与稀疏差异的思想对文档进行逻辑建模并量化, 形成可解释且具较好逻辑连贯性的脉络链, 解决了贪心相似或者主题聚类的脉络局部化问题。本文方法简单, 最终结果脉络链取决于用户给定的起始和终点文档, 无须每次对整个集合进行迭代。

本文构建脉络链的最终评价标准是逻辑连贯性, 而逻辑连贯性取决于具体转移词的累加。选取哪些词以及累加转移如何计算, 都可由用户个性化指定。如用户喜欢逻辑跳跃缓慢的链, 就返回相邻逻辑转移增长相对平缓的链, 反之亦然。与此同时, 用户也可对词转移的影响进行人为指定。比如用户喜欢某些特定词, 即可人为调高相应词的转移影响, 结果链包含用户喜欢的事件的转移几率就会提高。在为用户生成逻辑连贯且可解释的脉络链的同时, 利用链可解释性的展示可获取用户的反馈, 因此研究如何为用户提供个性化的逻辑脉络链是下一步要做的工作。目前结果链是单链, 反映事件的某一个侧面, 将来可考虑构建成脉络图, 使之包含的信息更加全面。因此, 如何融合多条链, 也是将来要考虑的工作。