第15卷第6期 智能系统学报 Vol.15 No.6 2020年11月 CAAI Transactions on Intelligent Systems Nov.2020 D0:10.11992tis.201912037 增量采样聚类驱动的新闻事件发现 陈晓琪2，谢振平2，刘渊 (1.江南大学人工智能与计算机学院，江苏无锡214122；2.江南大学江苏省媒体设计与软件技术重点实验 室，江苏无锡214122) 摘要：为获得更好的事件发现和代表性新闻抽取性能，引入数据集代表点采样聚类的视角，研究实现了一种 事件发现及表示的集成分析方法。对于给定的新闻流数据，首先引入信息支撑度定义新闻间关系权重和事件 关系权重，并通过引入双层近邻传播算法的迭代构建整体时间流上的单向事件内容支撑度网络，实现代表性新 闻的分层增量采样，进一步考虑以最大相似度划分策略实现代表性新闻上的整体新闻流数据聚类。实验结果 表明，相比于现有相关方法，新方法在大规模新闻流数据上具有显著的计算效率，可提取出新闻流中极有代表 性的新闻，以及获得更好的新闻文档聚类质量，其热点事件发现结果与权威机构评选的重大新闻有极高吻合度。 关键词：新闻流数据：事件发现：代表性新闻：增量采样；信息支撑度；近邻传播；事件网络：分层聚类 中图分类号：TP391 文献标志码：A文章编号：1673-4785(2020)06-1175-10 中文引用格式：陈晓琪，谢振平，刘渊.增量采样聚类驱动的新闻事件发现小.智能系统学报，2020,15(6)：1175-1184. 英文引用格式：CHEN Xiaoqi,XIE Zhenping,LIU Yuan..News event detection driven by incremental sampling clusteringJ.CAAI transactions on intelligent systems,2020,15(6):1175-1184. News event detection driven by incremental sampling clustering CHEN Xiaoqi,XIE Zhenping2,LIU Yuan'2 (1.School of Artificial Intelligence and Computer Science,Jiangnan University,Wuxi 214122,China;2.Jiangsu Key Laboratory of Media Design and Software Technology,Jiangnan University,Wuxi 214122,China) Abstract:For obtaining better performance of event detection and representative news extraction,an integrated analysis method of event detection and representation is proposed by introducing the sampling clustering strategy on news docu- ments.For a given news flow data,first,we present two-weight definitions on the relationships between news and events by introducing an information supporting degree concept and then construct a one-way event content support network on the whole time flow using the iterative algorithm of double-layer nearest affinity propagation to realize layer-by-layer incremental sampling of representative news.Furthermore,overall news clustering was performed by using the maxim- um similarity division strategy.According to our experimental results,compared with existing related methods,the new method has significant computational efficiency for processing large-scale news flow data.It can extract the most rep- resentative news from the news flow and obtain better clustering quality of news documents.Its hot event detection res- ults are highly consistent with the major news selected by the authority. Keywords:news flow data;event detection;representative news;incremental sampling;information supporting degree; affinity propagation;event network,hierarchical clustering 随着互联网的不断发展，网络媒体蓬勃兴起 网新闻用户规模日益庞大，用户需求的多样性和 并成为新闻传播的重要途径之一。近几年，互联 网络信息传播的快捷性使得网络新闻数量呈井喷 收稿日期：2019-12-31 式增长。而另一方面，大量新闻数据并没有能提 基金项目：国家自然科学基金项目(61872166)：江苏省“六大人 高用户获取有效信息的效率，且会因为相似新闻 才高峰”项目(2019 XYDXX-161). 通信作者：谢振平.E-mail:xiezp@jiangnan..edu.cn 过多而增加用户不必要的阅读时间。因此，抽取
DOI: 10.11992/tis.201912037 增量采样聚类驱动的新闻事件发现 陈晓琪1,2，谢振平1,2，刘渊1,2 （1. 江南大学 人工智能与计算机学院，江苏 无锡 214122; 2. 江南大学 江苏省媒体设计与软件技术重点实验 室，江苏 无锡 214122） 摘 要：为获得更好的事件发现和代表性新闻抽取性能，引入数据集代表点采样聚类的视角，研究实现了一种 事件发现及表示的集成分析方法。对于给定的新闻流数据，首先引入信息支撑度定义新闻间关系权重和事件 关系权重，并通过引入双层近邻传播算法的迭代构建整体时间流上的单向事件内容支撑度网络，实现代表性新 闻的分层增量采样，进一步考虑以最大相似度划分策略实现代表性新闻上的整体新闻流数据聚类。实验结果 表明，相比于现有相关方法，新方法在大规模新闻流数据上具有显著的计算效率，可提取出新闻流中极有代表 性的新闻，以及获得更好的新闻文档聚类质量，其热点事件发现结果与权威机构评选的重大新闻有极高吻合度。 关键词：新闻流数据；事件发现；代表性新闻；增量采样；信息支撑度；近邻传播；事件网络；分层聚类 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2020)06−1175−10 中文引用格式：陈晓琪, 谢振平, 刘渊. 增量采样聚类驱动的新闻事件发现 [J]. 智能系统学报, 2020, 15(6): 1175–1184. 英文引用格式：CHEN Xiaoqi, XIE Zhenping, LIU Yuan. News event detection driven by incremental sampling clustering[J]. CAAI transactions on intelligent systems, 2020, 15(6): 1175–1184. News event detection driven by incremental sampling clustering CHEN Xiaoqi1,2 ，XIE Zhenping1,2 ，LIU Yuan1,2 (1. School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi 214122, China; 2. Jiangsu Key Laboratory of Media Design and Software Technology, Jiangnan University, Wuxi 214122, China) Abstract: For obtaining better performance of event detection and representative news extraction, an integrated analysis method of event detection and representation is proposed by introducing the sampling clustering strategy on news documents. For a given news flow data, first, we present two-weight definitions on the relationships between news and events by introducing an information supporting degree concept and then construct a one-way event content support network on the whole time flow using the iterative algorithm of double-layer nearest affinity propagation to realize layer-by-layer incremental sampling of representative news. Furthermore, overall news clustering was performed by using the maximum similarity division strategy. According to our experimental results, compared with existing related methods, the new method has significant computational efficiency for processing large-scale news flow data. It can extract the most representative news from the news flow and obtain better clustering quality of news documents. Its hot event detection results are highly consistent with the major news selected by the authority. Keywords: news flow data; event detection; representative news; incremental sampling; information supporting degree; affinity propagation; event network; hierarchical clustering 随着互联网的不断发展，网络媒体蓬勃兴起 并成为新闻传播的重要途径之一。近几年，互联 网新闻用户规模日益庞大，用户需求的多样性和 网络信息传播的快捷性使得网络新闻数量呈井喷 式增长。而另一方面，大量新闻数据并没有能提 高用户获取有效信息的效率，且会因为相似新闻 过多而增加用户不必要的阅读时间。因此，抽取 收稿日期：2019−12−31. 基金项目：国家自然科学基金项目 (61872166)；江苏省“六大人 才高峰”项目 (2019XYDXX-161). 通信作者：谢振平. E-mail：xiezp@jiangnan.edu.cn. 第 15 卷第 6 期 智 能 系 统 学 报 Vol.15 No.6 2020 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2020
·1176· 智能系统学报 第15卷 大量新闻文档中的重要新闻，以及组织新闻流为 关系的话题追踪方法，实现微博等短文本的事件 新闻事件正成为信息推送服务的关键技术需求。 跟踪。 事件发现技术是信息推送服务的关键技术之 当前有关信息推送服务的研究大多集中在文 一。目前，有关事件发现的大多数方法基于聚类 本聚类的事件发现上，关于事件表示的代表性新 思想实现，包括single-pass算法l-2、k-means算 闻的提取研究还较少，文献[17]的做法是在事件 法B、AP算法B-等。其中主流的一种方法是A- 发现的基础上通过计算得到与聚类中心最相近的 lan等m提出的在线事件发现系统，每当有新的文 文档作为代表性新闻。此外，许多现有方法要求 档到来时，需与已知的事件计算相关度，通过预 保留所有的已处理文档，作为历史信息与新到 先设定的事件相似度阈值判断将该文档嵌入已知 文档进行比较，随着数据规模的扩大以及数据流 事件或生成新的事件。以该方法为基础，研究人 的不断到来，计算量和所需存储空间也会逐渐增 员做出了许多改进工作，主要涉及文本表示形式 大。文本考虑事件发现和事件表示的集成分析 的改进、更多语料特征的利用和文本聚类方法的 兼顾大规模新闻流数据事件发现的可行性，提出 建立。针对现有话题演化挖掘缺乏对话题特征随 一种以代表点选取为核心的增量采样聚类驱动的 时间发展而动态演变的深入分析所导致的挖掘结 事件发现方法，该方法一方面在数据的增量处理 果偏斜问题，赵旭剑等1引入话题特征演变特性 中不断约简非代表性新闻以保证事件发现的效 提出一种新的特征计算模型，利用已有话题文档 率，另一方面以采样获得的代表性新闻为基础实 和最新文档进行话题信息动态扩增，有效修正话 现聚类划分完成新闻事件发现，提供了一种可参 题演化挖掘结果的偏斜。Yin等9针对短文本聚 考的信息推送技术新思路。 类的狄利克雷多项式混合模型，提出了一种折叠 吉布斯抽样算法GSDMM,可自动推断聚类数量， 1方法框架 结果完备性、同质性平衡良好，能够解决短文本 的稀疏高维度问题。周楠等0基于带背景、语言 为获得更好的新闻事件发现和代表性新闻抽 的概率潜在语义分析模型(PLSA with Background 取结果，引入分层增量思想和信息支撑度的信息约 Language,PLSA-BLM),结合关键词聚类发现事件 简策略，提出基于分层增量代表点采样的事件发现 内部子话题，在维基百科等知识库基础上生成事 及表示的集成分析方法，其基本框架如图1所示。 件子话题标签的模型ET-TAG,与已有子话题发 增量采样的代表性新闻提取 现算法相比有更好的性能。Xu等1使用唐森- 香农散度(Jensen-Shannon Divergence)来度量话题 A聚 AP聚类 AD聚着 相似度，引入时间衰减函数来提高相似时间的话 微类集合及 表州 微类集合及 局部代表性 题之间的相似度，改进single-pass算法并结合潜 新集合 新间集 新集合 新闻集合 在狄利克雷分布(latent dirichlet allocation,LDA) 达到有效监测和跟踪话题的目的。 为 件 事件发现的另一个趋势是增量或分层地处理 经类发现后的数据 文档。黄九鸣等四为解决在线社交网络文本流 单向事件内容 支撑度网路G 所含热点短语指向的突发事件和热点话题问题， 道 提出结合AC-Trie前缀树构建的无需分词且适用 还有 构造单向事件内容支 撑度网路G 多种热度度量函数的热点短语挖掘技术。Chen 精 多 等)考虑解决在线主题模型固定话题数、话题重 单向事件内容支撑度 叠问题，因为层次主题模型处理话题重叠的适配 9-上A 一过滤相似新 性，提出了基于知识的半监督层次在线话题检 代表性新博表合 测框架。此外，一些其他方法也被应用于事件发 现。Sayyadi等基于复杂网络思想，提出了基于 已知代表性新间的新闻文档聚类 关键词共现性的KeyGraph话题检测方法。Chen 事件及对应代表性文档： 划分非代表 Topl:事件a对应代表性文档d 等则将层次隐树分析(hierarchical latent tree ana- 性文档 Top2:事件b对应代表性文档d Top3:事件c对应代表性文档d. lysis,.HLTA)引入话题检测，改进期望最大化(ex- pectation-maximization)算法，可以得到更好的主 图1方法框架 题层次结构。柏文言等则开发一种融合用户 Fig.1 Framework of the proposed method
大量新闻文档中的重要新闻，以及组织新闻流为 新闻事件正成为信息推送服务的关键技术需求。 事件发现技术是信息推送服务的关键技术之 一。目前，有关事件发现的大多数方法基于聚类 思想实现，包括 single-pass 算法[1-2] 、k-means 算 法 [3-4] 、AP 算法[5-6] 等。其中主流的一种方法是 Allan 等 [7] 提出的在线事件发现系统，每当有新的文 档到来时，需与已知的事件计算相关度，通过预 先设定的事件相似度阈值判断将该文档嵌入已知 事件或生成新的事件。以该方法为基础，研究人 员做出了许多改进工作，主要涉及文本表示形式 的改进、更多语料特征的利用和文本聚类方法的 建立。针对现有话题演化挖掘缺乏对话题特征随 时间发展而动态演变的深入分析所导致的挖掘结 果偏斜问题，赵旭剑等[8] 引入话题特征演变特性 提出一种新的特征计算模型，利用已有话题文档 和最新文档进行话题信息动态扩增，有效修正话 题演化挖掘结果的偏斜。Yin 等 [9] 针对短文本聚 类的狄利克雷多项式混合模型，提出了一种折叠 吉布斯抽样算法 GSDMM，可自动推断聚类数量， 结果完备性、同质性平衡良好，能够解决短文本 的稀疏高维度问题。周楠等[10] 基于带背景、语言 的概率潜在语义分析模型 (PLSA with Background Language, PLSA-BLM)，结合关键词聚类发现事件 内部子话题，在维基百科等知识库基础上生成事 件子话题标签的模型 ET-TAG，与已有子话题发 现算法相比有更好的性能。Xu 等 [11] 使用唐森− 香农散度 (Jensen-Shannon Divergence) 来度量话题 相似度，引入时间衰减函数来提高相似时间的话 题之间的相似度，改进 single-pass 算法并结合潜 在狄利克雷分布 (latent dirichlet allocation，LDA) 达到有效监测和跟踪话题的目的。 事件发现的另一个趋势是增量或分层地处理 文档。黄九鸣等[12] 为解决在线社交网络文本流 所含热点短语指向的突发事件和热点话题问题， 提出结合 AC-Trie 前缀树构建的无需分词且适用 多种热度度量函数的热点短语挖掘技术。Chen 等 [13] 考虑解决在线主题模型固定话题数、话题重 叠问题，因为层次主题模型处理话题重叠的适配 性，提出了基于知识的半监督层次在线话题检 测框架。此外，一些其他方法也被应用于事件发 现。Sayyadi 等 [14] 基于复杂网络思想，提出了基于 关键词共现性的 KeyGraph 话题检测方法。Chen 等 [15] 则将层次隐树分析 (hierarchical latent tree analysis，HLTA) 引入话题检测，改进期望最大化 (expectation-maximization) 算法，可以得到更好的主 题层次结构。柏文言等[16] 则开发一种融合用户 关系的话题追踪方法，实现微博等短文本的事件 跟踪。 当前有关信息推送服务的研究大多集中在文 本聚类的事件发现上，关于事件表示的代表性新 闻的提取研究还较少，文献 [17] 的做法是在事件 发现的基础上通过计算得到与聚类中心最相近的 文档作为代表性新闻。此外，许多现有方法要求 保留所有的已处理文档[7,14] 作为历史信息与新到 文档进行比较，随着数据规模的扩大以及数据流 的不断到来，计算量和所需存储空间也会逐渐增 大。文本考虑事件发现和事件表示的集成分析， 兼顾大规模新闻流数据事件发现的可行性，提出 一种以代表点选取为核心的增量采样聚类驱动的 事件发现方法，该方法一方面在数据的增量处理 中不断约简非代表性新闻以保证事件发现的效 率，另一方面以采样获得的代表性新闻为基础实 现聚类划分完成新闻事件发现，提供了一种可参 考的信息推送技术新思路。 1 方法框架 为获得更好的新闻事件发现和代表性新闻抽 取结果，引入分层增量思想和信息支撑度的信息约 简策略，提出基于分层增量代表点采样的事件发现 及表示的集成分析方法，其基本框架如图 1 所示。 … 微类集合及 局部代表性 新闻集合 … AP 聚类 … 事件及对应代表性文档： Top1: 事件 a 对应代表性文档 da Top2: 事件 b 对应代表性文档 db Top3: 事件 c 对应代表性文档 dc 构造单向事件内容支 撑度网络 Gt−1 微类集合 Mt 局部代表性 新闻集合 Rt 单向事件内容 支撑度网络 Gt−2 划分非代表 性文档 间隔 Span0 语料 间隔 Span1 语料 间隔 Span2 语料 间隔 SpanT 语料 AP 聚类 AP 聚类 AP 聚类 微类集合及 局部代表性 新闻集合 微类集合及 局部代表性 新闻集合 微类集合及 局部代表性 新闻集合 单向事件内容支撑度 网络 Gt−1上AP聚类， 进一步过滤相似新 闻文档, 得到最终的 代表性新闻集合 是否 还有 语料 Y N 取间隔 Spant 内语料 经微类发现后的数据 事 件 微 类 发 现 流 程 事 件 微 类 聚 合 流 程 已知代表性新闻的新闻文档聚类 ... 增量采样的代表性新闻提取 图 1 方法框架 Fig. 1 Framework of the proposed method ·1176· 智 能 系 统 学 报 第 15 卷
第6期 陈晓琪，等：增量采样聚类驱动的新闻事件发现 ·1177· 方法框架包含两个方面的处理： 向文档内容支撑度网络的基础上对单向事件内容 1)增量采样的代表性新闻提取。本文提出一 支撑度网络进行增量构建；3)单向事件内容支撑 种分层增量的代表性新闻采样方法，如图1所示， 度网络上的相似事件聚合。 将新闻依据时间进行划分，对每个时间片内的新 2.2.1单向文档内容支撑度网络 闻进行AP聚类获得时间片上的事件微类及局部 一般来讲，热点事件的热度高，持续时间长， 代表性新闻，在此过程中增量的依据信息支撑度 因此在相邻的时间片上可能存在内容非常相似的 关系权重计算方法构建单向事件内容支撑度网 两个事件微类，但随着时间的增长，相隔越远的 络，约简非局部代表性新闻。通过在单向事件内 两个报道越不可能同属于一个事件。为此，引入 容支撑度网络上的AP聚类合并同一事件，提取 单向文档关系网络去解释这一现象。单向文档关 出最终的代表性新闻。 系网络将新闻流中的每一篇新闻文档看作网络中 2)已知代表性新闻的新闻文档聚类。在分层 的节点，节点间的边权重由文档间余弦相似度确 增量采样获取的代表性新闻基础上，依照最大相 定，边方向由发表时间上的前序文档指向后序文 似度划分策略，将非代表性新闻分配给一个代表 档，且规定只有相邻时间片上的节点之间存在联 性新闻，完成新闻文档聚类。 系，同一时间片以及不相邻时间片上的节点之间 2增量采样的代表性新闻提取 不直接相联系，相应的网络结构如图2所示。 如图1所示，增量采样的代表性新闻提取包 含事件微类发现阶段和事件微类聚合阶段，事件 微类发现的目的在于通过聚类算法找到一个时间 段内的局部代表性新闻，事件微类聚合的目的在 于将各时间段推选的局部代表性新闻进行合并， 从而推选出整个数据集上的代表性新闻。 2.1事件微类发现 事件微类发现的目的是将一段时间内发表的 新闻文档按照相关性组织为与事件相关的文档集 合，每一个文档集合称为该时间片内的一个事件 微类，并给出如下事件微类代表性新闻概念。 时间片Span-,!时间片Span 时刻T- 时刻T 时刻T 定义1在一个事件微类中，其文档间内容 高度相似，从事件微类中选择一篇文档作为该事 图2单向文档关系网络 件微类的代表性新闻，代表性新闻在内容上与事 Fig.2 One-way document network 件微类中的其他新闻文档高度相似，是事件微类 进一步地，在单向文档关系网络上引人信息 的中心。 支撑度概念，信息支撑度源于建构主义学习理论 为了更方便及准确地找到事件微类的聚类中 中的知识支撑概念，建构主义认为知识是在其 心，采用AP聚类割完成事件微类发现的工作。 他基础知识上通过它们的相互作用而主动构建产 AP算法通过节点间吸引度消息和归属度消息的 生的。迁移到文档产生上，一篇新文档的产生通 传递收敛将相似文档划分到同一类别，其对数据 常需要借鉴和引用已有文档内容，新文档会从旧 的初始值不敏感，且AP算法能选择真实存在的 文档中汲取知识完成自身的知识构建，基于此引 数据点作为聚类中心，从而在寻找事件微类的代 入关于信息支撑度的概念定义。 表性新闻时不再需要额外处理手段，对应的文档 定义2在文档产生中时间上的后序文档会 可以直接作为事件微类的代表性新闻文档。对 对前序文档有一定的借鉴和引用，后序文档中内 应AP算法输入的相似度矩阵的要求，此阶段采 容的构建会一定程度上参考前序文档。信息支撑 用余弦相似度表征新闻文档间的相似性。 度描述了这一知识传递关系，表示有直接关联的 2.2事件微类聚合 前序文档对后序文档在内容上的直接支持程度。 事件微类的聚合主要包含3个步骤：1)定义 信息支撑度是一个单向的指向关系，由前序文档 单向文档关系网络，以及定义引入建构主义信息 指向后序文档，表示由前序文档将知识传递给后 支撑度概念的单向文档内容支撑度网络：2)在单 序文档
方法框架包含两个方面的处理： 1) 增量采样的代表性新闻提取。本文提出一 种分层增量的代表性新闻采样方法，如图 1 所示， 将新闻依据时间进行划分，对每个时间片内的新 闻进行 AP 聚类获得时间片上的事件微类及局部 代表性新闻，在此过程中增量的依据信息支撑度 关系权重计算方法构建单向事件内容支撑度网 络，约简非局部代表性新闻。通过在单向事件内 容支撑度网络上的 AP 聚类合并同一事件，提取 出最终的代表性新闻。 2) 已知代表性新闻的新闻文档聚类。在分层 增量采样获取的代表性新闻基础上，依照最大相 似度划分策略，将非代表性新闻分配给一个代表 性新闻，完成新闻文档聚类。 2 增量采样的代表性新闻提取 如图 1 所示，增量采样的代表性新闻提取包 含事件微类发现阶段和事件微类聚合阶段，事件 微类发现的目的在于通过聚类算法找到一个时间 段内的局部代表性新闻，事件微类聚合的目的在 于将各时间段推选的局部代表性新闻进行合并， 从而推选出整个数据集上的代表性新闻。 2.1 事件微类发现 事件微类发现的目的是将一段时间内发表的 新闻文档按照相关性组织为与事件相关的文档集 合，每一个文档集合称为该时间片内的一个事件 微类，并给出如下事件微类代表性新闻概念。 定义 1 在一个事件微类中，其文档间内容 高度相似，从事件微类中选择一篇文档作为该事 件微类的代表性新闻，代表性新闻在内容上与事 件微类中的其他新闻文档高度相似，是事件微类 的中心。 为了更方便及准确地找到事件微类的聚类中 心，采用 AP 聚类[18] 完成事件微类发现的工作。 AP 算法通过节点间吸引度消息和归属度消息的 传递收敛将相似文档划分到同一类别，其对数据 的初始值不敏感，且 AP 算法能选择真实存在的 数据点作为聚类中心，从而在寻找事件微类的代 表性新闻时不再需要额外处理手段，对应的文档 可以直接作为事件微类的代表性新闻文档。对 应 AP 算法输入的相似度矩阵的要求，此阶段采 用余弦相似度表征新闻文档间的相似性。 2.2 事件微类聚合 事件微类的聚合主要包含 3 个步骤：1) 定义 单向文档关系网络，以及定义引入建构主义信息 支撑度概念的单向文档内容支撑度网络；2) 在单 向文档内容支撑度网络的基础上对单向事件内容 支撑度网络进行增量构建；3) 单向事件内容支撑 度网络上的相似事件聚合。 2.2.1 单向文档内容支撑度网络 一般来讲，热点事件的热度高，持续时间长， 因此在相邻的时间片上可能存在内容非常相似的 两个事件微类，但随着时间的增长，相隔越远的 两个报道越不可能同属于一个事件。为此，引入 单向文档关系网络去解释这一现象。单向文档关 系网络将新闻流中的每一篇新闻文档看作网络中 的节点，节点间的边权重由文档间余弦相似度确 定，边方向由发表时间上的前序文档指向后序文 档，且规定只有相邻时间片上的节点之间存在联 系，同一时间片以及不相邻时间片上的节点之间 不直接相联系，相应的网络结构如图 2 所示。 时刻 Ti−1 时刻 Ti 时刻 Ti+1 … … … … … … 时间片 Spani−1 时间片 Spani … … … … di−2, 0 di−1, 0 di+1, 0 di+1, 1 di+1, 2 di+1, j −1 di+1, j di+1, j+1 di, 0 di, 1 di, j di, j+1 di−1, 1 di−1, 2 di−1, j−2 di−1, j−1 di−1, j di−1, j+1 di−2, 1 di−2, 2 di−2, j di−2, j+1 图 2 单向文档关系网络 Fig. 2 One-way document network 进一步地，在单向文档关系网络上引入信息 支撑度概念，信息支撑度源于建构主义学习理论 中的知识支撑概念[19] ，建构主义认为知识是在其 他基础知识上通过它们的相互作用而主动构建产 生的。迁移到文档产生上，一篇新文档的产生通 常需要借鉴和引用已有文档内容，新文档会从旧 文档中汲取知识完成自身的知识构建，基于此引 入关于信息支撑度的概念定义。 定义 2 在文档产生中时间上的后序文档会 对前序文档有一定的借鉴和引用，后序文档中内 容的构建会一定程度上参考前序文档。信息支撑 度描述了这一知识传递关系，表示有直接关联的 前序文档对后序文档在内容上的直接支持程度。 信息支撑度是一个单向的指向关系，由前序文档 指向后序文档，表示由前序文档将知识传递给后 序文档。 第 6 期 陈晓琪，等：增量采样聚类驱动的新闻事件发现 ·1177·
·1178· 智能系统学报 第15卷 考虑新文档更可能借鉴和引用时间上更近的 定义3单向事件内容支撑度网络构建中， 文档，规定两个相邻时间片上的文档间有直接关 两个相邻时间片上的任意两个局部代表性新闻 联性。这样可考虑所有前一时间片内的文档构成 Ra、Rb间的复合支撑度csup%R定义为 了对下一时间片某一文档d的内容支撑集合，内 容支撑集合对某一文档d的支撑度总和设为1。 min(IM.al.IM) exp (2) 文档间的支撑度定义为 1 supa=sim(d,da)× 式中：Ma为区间[T,T4i)的微类；Ra为Ma产生 djeSpani-1,daE Spani (1) 的局部代表性新闻；M+1b为区间[T#1,T#2)的微 U= ∑sim(d.da) 类；R#b为M1b产生的局部代表性新闻；d.为微 式中：spa表示直接关联的属于时间片集合 类Ma中的文档；d+w为微类M+ib中的文档， Span-1的文档d对属于时间片集合Span,的文档 supx,意义同式(I)中supa的含义。 d。的支撑度；sim(d,d)为两文档的余弦相似度；U 单向事件内容支撑度网络是增量构建的，如 为Span-1内所有文档与文档da的余弦相似度总 图1所示，其构建过程与事件微类发现流程同 和。以信息支撑度为关系权重的单向文档关系网 步。在图3中，当Span:时间片上的事件微类发 络称为单向文档内容支撑度网络。 现完成后，与Span-1时间片上的事件微类做复合 2.2.2单向事件内容支撑度网络 支撑度的计算，将Span,上的微类代表性新闻文 为了在获取代表性新闻文档的过程中不断约 档作为节点加入到Spano,Span1,…,Span-i}上微 简掉非代表性新闻文档以减少计算量和所需存储 类代表性新闻文档构成的单向事件内容支撑度 空间，考虑用事件微类发现阶段产生的局部代表 网络supNet-2上，构建单向事件内容支撑度网络 性新闻去代表微类。相应地，需要将单向文档内 supNet-,1。在这一构建过程中，事件微类发现产 容支撑度网络转化为单向事件内容支撑度网络。 生的非局部代表性新闻在完成复合支撑度的计 同单向文档内容支撑度网络的特征相似，单向事 算后被约简，其包含的特征被整合为复合支撑度 件内容支撑度网络中只有相邻时间片上的局部代 赋予局部代表性新闻，本身不需要参与第二层聚 表性新闻间存在联系，同一时间片以及不相邻时 类运算。当新闻流中的所有文档均处理完成后， 间片上的局部代表性新闻间不直接相联系。为 形成所有局部代表性新闻构成的单向事件内容 此，引入复合支撑度作为单向事件内容支撑度网 支撑度网络，完成对所有非局部代表性新闻文档 络的关系权重。 的约简。 微类M。一 微类M+ 局部代表性新闻 sup 局部代表性新闻 R d.. 时间片Span-1 时间片Span】 时间片Span supNet supNet, 时刻7时间片San,时刻T1时间片Spam, 时刻T2 单向文档内容支撑度网铬 单向事件内容支撑度网络 图3单向文档内容支撑度网络到单向事件内容支撑网络的转化 Fig.3 Transformation from one-way document content support network to one-way event content support network 2.2.3相似事件聚合 需求，同样采用AP算法进行事件微类的聚合。 考虑到单向网络的不对称性和代表点获取的 给定M,-2×M-2维相似度矩阵S,2,M-1×M1维相
d d 考虑新文档更可能借鉴和引用时间上更近的 文档，规定两个相邻时间片上的文档间有直接关 联性。这样可考虑所有前一时间片内的文档构成 了对下一时间片某一文档 的内容支撑集合，内 容支撑集合对某一文档 的支撑度总和设为 1。 文档间的支撑度定义为 supj,a = sim(dj , da)× 1 U dj ∈ Spani−1 , da ∈ Spani U = ∑ dl∈Spani−1 sim(dl , da) (1) supj,a Spani−1 dj Spani da sim(dj , da) U Spani−1 da 式中： 表示直接关联的属于时间片集合 的文档 对属于时间片集合 的文档 的支撑度； 为两文档的余弦相似度； 为 内所有文档与文档 的余弦相似度总 和。以信息支撑度为关系权重的单向文档关系网 络称为单向文档内容支撑度网络。 2.2.2 单向事件内容支撑度网络 为了在获取代表性新闻文档的过程中不断约 简掉非代表性新闻文档以减少计算量和所需存储 空间，考虑用事件微类发现阶段产生的局部代表 性新闻去代表微类。相应地，需要将单向文档内 容支撑度网络转化为单向事件内容支撑度网络。 同单向文档内容支撑度网络的特征相似，单向事 件内容支撑度网络中只有相邻时间片上的局部代 表性新闻间存在联系，同一时间片以及不相邻时 间片上的局部代表性新闻间不直接相联系。为 此，引入复合支撑度作为单向事件内容支撑度网 络的关系权重。 Ri,a Ri+1,b csupRi,a ,Ri+1,b 定义 3 单向事件内容支撑度网络构建中， 两个相邻时间片上的任意两个局部代表性新闻 、 间的复合支撑度 定义为 csupRi,a ,Ri+1,b = exp − min( ∑ |Mi,a|,|Mi+1,b|) di,x∈Mi,a ∑ di+1,y∈Mi+1,b supx,y (2) Mi,a [Ti ,Ti+1) Ri,a Mi,a Mi+1,b [Ti+1,Ti+2) Ri+1,b Mi+1,b di,x Mi,a di+1,y Mi+1,b supx,y supj,a 式中： 为区间 的微类； 为 产生 的局部代表性新闻； 为区间 的微 类； 为 产生的局部代表性新闻； 为微 类 中的文档； 为微类 中的文档， 意义同式 (1) 中 的含义 。 Spani Spani−1 Spani {Span0,Span1,··· ,Spani−1} supNeti−2 supNeti−1 单向事件内容支撑度网络是增量构建的，如 图 1 所示，其构建过程与事件微类发现流程同 步。在图 3 中，当 时间片上的事件微类发 现完成后，与 时间片上的事件微类做复合 支撑度的计算，将 上的微类代表性新闻文 档作为节点加入到 上微 类代表性新闻文档构成的单向事件内容支撑度 网络 上，构建单向事件内容支撑度网络 。在这一构建过程中，事件微类发现产 生的非局部代表性新闻在完成复合支撑度的计 算后被约简，其包含的特征被整合为复合支撑度 赋予局部代表性新闻，本身不需要参与第二层聚 类运算。当新闻流中的所有文档均处理完成后， 形成所有局部代表性新闻构成的单向事件内容 支撑度网络，完成对所有非局部代表性新闻文档 的约简。 … … … … 微类 Mi, a 微类 Mi+1, b 局部代表性新闻 局部代表性新闻 单向文档内容支撑度网络 单向事件内容支撑度网络 … … … … … … … … … … … Ri, a Ri+1, b di, a di, j di, a+1 di+1, b Ri−1, 0 Ri, a Ri, m Ri, n Ri−1, m Ri+1, b Ri+1, m Ri−1, n Ri+1, n di+1, b+1 di+1, b+2 di+1, j−1 di+1, j 时刻 Ti 时间片 时刻 Ti+1 时刻 Ti+2 Spani 时间片 Spani+1 时间片 Spani−1 时间片 Spani 时间片 Spani+1 supa, b supNeti−2 csupRi, a, Ri+1, b supNeti−1 supNeti 图 3 单向文档内容支撑度网络到单向事件内容支撑网络的转化 Fig. 3 Transformation from one-way document content support network to one-way event content support network 2.2.3 相似事件聚合 考虑到单向网络的不对称性和代表点获取的 Mt−2 × Mt−2 St−2 Mt−1 × Mt−1 需求，同样采用 AP 算法进行事件微类的聚合。 给定 维相似度矩阵 ， 维相 ·1178· 智 能 系 统 学 报 第 15 卷
第6期 陈晓琪，等：增量采样聚类驱动的新闻事件发现 ·1179· 似度矩阵S-,依据上述单向事件内容支撑度网 算法2已知代表性新闻的新闻文档聚类 络构建过程，相应的1时刻网络对应相似度矩阵 输入新闻子集流{D,D2,…,Dl,代表性新 S,定义为 闻集globalR; S-(i,j,i≤M-,j≤M- 输出聚类结果{C,C2,…,ClglobaR S,i,)= csupi.j M2<is M-1,j>M1 (3) 0,i>M-1或者i≤M-2,j>M- D←DUD2UUDn fori←1 to globalR do 基于AP算法将相似局部代表性新闻文档划 分为一类，即微类聚合为大的事件类，同样依照 delete globalR[i]from D AP聚类结果选择聚类中心作为最终的代表性新 create Ci←O 闻，只有局部代表性新闻才有可能被选为最终的 end for 代表性新闻。此外，在事件微类发现阶段，期望 fori←-1 to D do 得到更为广泛的事件微类，有助于事件微类聚合 fori←1 to globalR do 过程中得到代表性更强、重要性更高的新闻文 calculate sim(D[il,globalR[il)) 档，因此在事件微类发现阶段，使用文档间相似 end for 度的中位值作为AP算法的偏向参数，但在事件 labelil max(sim(D[i],globalR[i])) 微类聚合阶段需要设置合适的偏向参数。 add D[]to Cuabe 算法1增量采样的代表性新闻提取 end for 输入新闻子集流{D,D2,…,Dn,偏向参数 rerutn (C.C2..Clloba preference; 假设新闻流文档总数为N,时间片数为T,微 输出代表性新闻集globalR。 类发现阶段的局部代表性新闻提取率为P,在文 init lastR←-O,lastCluster←O,G←-0 档规模为N的情况下，标准AP算法复杂度1为 fori←-1 to n do OW2IgW。本文方法复杂度主要考虑AP算法部 ifi=1 分和复合支撑度部分，微类发现阶段AP算法时 根据D获取相似度矩阵S 间复杂度为OWN/T1g(W/T),微类聚合阶段AP lastR,lastClusterAP(S,Smedi) 算法时间复杂度为OW2p21gNp)0<p<1),复合 扩展Goo到GjatRpJauRI 支撑度计算的事件复杂度为ON/T)。考虑N/T else 的规模较小，而p正常情况是一个远小于1的数， 根据D获取相似度矩阵S 相比于直接使用AP算法，文中方法的时间复杂 localR,localCluster-AP(S,preference) 度可以远远降低。 扩展GGMG到GidocalRI+Cx(llocalRI+D 3实验研究 for x1 to localR+GlI do for y1 to localR+Gl do 3.1实验方案 依据式(3)计算G[xy) 以新闻文档为研究对象，为更好地检验算法 (base lastR,lastCluster,localR.localCluster) 性能，实验中采用了以下几种事件发现方法作为 end for 研究： end for 1)k-means+方法2o。使用标准k-means方法 lastR←localR,lastCluster←-localCluster 对所有文档统一进行聚类，初始聚类中心依照相 end if 互较远的准则进行选择。划分的每一个类作为一 end for 个事件，选择离聚类中心最近的文档作为代表性 globalR AP(G,preference) 新闻。 return globalR 2)标准AP方法11。使用标准AP方法对所 2.3已知代表性新闻的新闻文档聚类 有文档统一进行聚类，选择聚类中心对应的文档 通过增量分层采样得到代表性新闻文档后， 作为代表性新闻。 依据最大相似度策略将非代表性新闻文档分配给 3)改进single-pass方法刀。使用时间片分层 一个代表性新闻文档所代表的类，完成所有文档 single-pass在线聚类方法增量地对文档进行处理， 的全局划分，划分的结果即为事件发现的结果。 不同时间片间事件依据话题的相似度进行合并
St−1 St 似度矩阵 ，依据上述单向事件内容支撑度网 络构建过程，相应的 t 时刻网络对应相似度矩阵 定义为 St(i, j) = St−1(i, j), i ⩽ Mt−1, j ⩽ Mt−1 csupi, j , Mt−2 < i ⩽ Mt−1, j > Mt−1 0, i > Mt−1或者i ⩽ Mt−2 , j > Mt−1 (3) 基于 AP 算法将相似局部代表性新闻文档划 分为一类，即微类聚合为大的事件类，同样依照 AP 聚类结果选择聚类中心作为最终的代表性新 闻，只有局部代表性新闻才有可能被选为最终的 代表性新闻。此外，在事件微类发现阶段，期望 得到更为广泛的事件微类，有助于事件微类聚合 过程中得到代表性更强、重要性更高的新闻文 档，因此在事件微类发现阶段，使用文档间相似 度的中位值作为 AP 算法的偏向参数，但在事件 微类聚合阶段需要设置合适的偏向参数。 算法 1 增量采样的代表性新闻提取 输入 新闻子集流 {D1,D2,··· ,Dn} ，偏向参数 preference； 输出 代表性新闻集 globalR。 init lastR ← Ø,lastCluster ← Ø,G ← [] for i ← 1 to n do if i = 1 根据 D1获取相似度矩阵 S lastR,lastCluster ← AP(S,Smedian) 扩展 G0×0 到 G|lastR|×|lastR| else 根据 Di获取相似度矩阵 S localR,localCluster ← AP(S,preference) 扩展 G|G|×|G| 到 G(|localR|+|G|)×(|localR|+|G|) for x ← 1 to ||localR|+|G|| do for y ← 1 to ||localR|+|G|| do 依据式 (3) 计算 G[x][y] (base lastR,lastCluster,localR,localCluster) end for end for lastR ← localR,lastCluster ← localCluster end if end for globalR ← AP(G,preference) return globalR 2.3 已知代表性新闻的新闻文档聚类 通过增量分层采样得到代表性新闻文档后， 依据最大相似度策略将非代表性新闻文档分配给 一个代表性新闻文档所代表的类，完成所有文档 的全局划分，划分的结果即为事件发现的结果。 算法 2 已知代表性新闻的新闻文档聚类 输入 新闻子集流 {D1,D2,··· ,Dn} ，代表性新 闻集 globalR； { C1,C2,··· ,C|globalR| } 输出 聚类结果 。 D ← D1 ∪ D2 ∪ ··· ∪ Dn for i ← 1 to globalR do delete globalR[i] from D create Ci ← Ø end for for j ← 1 to |D| do for i ← 1 to globalR do calculate sim(D[j],globalR[i])) end for label ← i|max(sim(D[j],globalR[i])) add D[j]to Clabel end for rerutn {C1,C2,··· ,C|globalR| } O(N 2 lgN) O(N 2 /T 2 lg(N/T)) O(N 2 p 2 lgN p)(0 < p ≪ 1) O(N 2 /T 2 ) N/T 假设新闻流文档总数为 N，时间片数为 T，微 类发现阶段的局部代表性新闻提取率为 p，在文 档规模为 N 的情况下，标准 AP 算法复杂度[18] 为 。本文方法复杂度主要考虑 AP 算法部 分和复合支撑度部分，微类发现阶段 AP 算法时 间复杂度为 ，微类聚合阶段 AP 算法时间复杂度为 ，复合 支撑度计算的事件复杂度为 。考虑 的规模较小，而 p 正常情况是一个远小于 1 的数， 相比于直接使用 AP 算法，文中方法的时间复杂 度可以远远降低。 3 实验研究 3.1 实验方案 以新闻文档为研究对象，为更好地检验算法 性能，实验中采用了以下几种事件发现方法作为 研究： 1) k-means++方法[20]。使用标准 k-means 方法 对所有文档统一进行聚类，初始聚类中心依照相 互较远的准则进行选择。划分的每一个类作为一 个事件，选择离聚类中心最近的文档作为代表性 新闻。 2) 标准 AP 方法[18]。使用标准 AP 方法对所 有文档统一进行聚类，选择聚类中心对应的文档 作为代表性新闻。 3) 改进 single-pass 方法[17]。使用时间片分层 single-pass 在线聚类方法增量地对文档进行处理， 不同时间片间事件依据话题的相似度进行合并， 第 6 期 陈晓琪，等：增量采样聚类驱动的新闻事件发现 ·1179·