第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 M2M1 (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 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·
·1180· 智能系统学报 第15卷 选择离聚类中心最近的文档作为代表性新闻。 中美经贸摩擦 记使命 4)IAPNA方法。使用增量式扩充吸引度和 团领亭人第十四次峰会 克斯坦进行国事访问 归属度矩阵的增量AP方法对文档进行处理，选 :民共和国进行国事访问 择聚类中心对应的文档作为代表性新闻。 遭遇强降雨 实验中采用向量空间模型22对文档进行表 15.2800% 示，TF-DF方法计算词项权重，为消除不同文档 长度对计算的影响，需要同时对权重做归一化处 理。在对比方法中均使用余弦相似度表征文档 12.4528% 间关系。 43.2105% 文中实验所用平台配置为：Intel(R)Core 6.0377% (TM)i7-6700kCPU@4.00GHz、内存为16GB、操 作系统为Windows10、所有代码基于Python语言 6.0377% 实现。 4.9057% 3.2评价指标 3.0189% 4.1509%4.9057% 考虑主要从聚类质量和选取新闻的代表性程 度两个方面评价算法。聚类评价标准采用标准化 图4人民日报数据集话题分布 互信息(normalized mutual information,NMI)）以及 Fig.4 Topic distribution of People's Daily Online dataset F,值。标准化互信息是被广泛使用的评价聚类 采用北大开源词法分析工具pkuseg2对新闻 效果的方法，可以度量方法输出结果和真实结果 文档进行分词、去停用词以及TF-IDF权重计算。 之间的相似程度，NM的取值范围为[O,1],越靠 因为人工标记的话题数为43，实验过程中设定k- 近1表示方法输出结果与真实结果越相似。本文 means-+的类数为43，标准AP方法偏向参数取默 采用文献[24]中NM1的计算方式。 认中位值。改进single-pass方法相似度阈值为 F,值是分类问题的一个衡量指标，也常用于 0.05,话题合并阈值为0.15。IAPNA方法初始偏 文本聚类评价，是一种同时考虑准确率(preci- 向参数为0.0018。 sion)和召回率(recall)的综合性评价方法，是两者 首先分析AP算法的偏向参数(preference)对 的调和平均数，本文采用文献[17]中准确率、召 文中方法的性能影响。以10天为时间间隔，阻尼 回率、F值的计算方式。 系数设定为0.9，在[0.01,0.1]的范围内，以 针对新闻代表性程度，新定义新闻文档接近 0.001为步长，得到不同偏向参数下的F,值和NMI 度(document proximity,DP)指标来评价提取的代 值，如图5所示。 表性新闻对非代表性新闻的内容覆盖程度，其定 0.80 NMI 义为 0.75 min(dista,distdist) N-nr 0.65 DP=exp-n,) N-nr (4) 0.60 式中：N是文档总数；n,是提取的代表性新闻数； 0.55 dist表示两文档间归一化的欧式距离。新闻文档 0 0.020.040.06 0.080.10 preference 接近度考虑在合理的代表性新闻文档数的情况 下，代表性新闻在内容上对整体新闻流的覆盖程 图5不同preference参数对性能结果的影响 Fig.5 Performance results on with different preference 度，DP值越小，说明提取的代表性新闻在内容上 parameters 的覆盖程度越高。 从图5中可以看到，开始时随着偏向参数的增 3.3实验结果与分析 加，F,和NMI值均不断增加，此时偏向参数过小 通过爬取人民日报2019年6月初到7月中 生成的类数较少，许多不属于同一个事件的文档 旬的时政报道，筛选出530篇长文档，按照报道 被划分到了同一个类中，聚类的准确率较低，因而 发表的时间排序，精确到天。对该新闻数据集 一开始F,值与NMI值较小。偏向参数增加后，不 人工标记了43个事件话题，其数量分布如图4 同的文档开始被分到不同的类中，聚类的准确率 所示。 也开始增加，F,值与NM1值也随之增大。但当偏
选择离聚类中心最近的文档作为代表性新闻。 4) IAPNA 方法[21]。使用增量式扩充吸引度和 归属度矩阵的增量 AP 方法对文档进行处理，选 择聚类中心对应的文档作为代表性新闻。 实验中采用向量空间模型[22] 对文档进行表 示，TF-IDF 方法计算词项权重，为消除不同文档 长度对计算的影响，需要同时对权重做归一化处 理 [23]。在对比方法中均使用余弦相似度表征文档 间关系。 文中实验所用平台配置为： Intel(R) Core (TM) i7-6700k CPU @4.00 GHz、内存为 16 GB、操 作系统为 Windows10、所有代码基于 Python 语言 实现。 3.2 评价指标 考虑主要从聚类质量和选取新闻的代表性程 度两个方面评价算法。聚类评价标准采用标准化 互信息 (normalized mutual information，NMI) 以及 F1 值。标准化互信息是被广泛使用的评价聚类 效果的方法，可以度量方法输出结果和真实结果 之间的相似程度，NMI 的取值范围为 [0, 1]，越靠 近 1 表示方法输出结果与真实结果越相似。本文 采用文献 [24] 中 NMI 的计算方式。 F1 值是分类问题的一个衡量指标，也常用于 文本聚类评价，是一种同时考虑准确率 (precision) 和召回率 (recall) 的综合性评价方法，是两者 的调和平均数，本文采用文献 [17] 中准确率、召 回率、F1 值的计算方式。 针对新闻代表性程度，新定义新闻文档接近 度 (document proximity，DP) 指标来评价提取的代 表性新闻对非代表性新闻的内容覆盖程度，其定 义为 DP=exp( − N −nr nr ) · ∑N−nr j=1 min(distj,1,distj,2 ··· ,distj,nr ) N −nr (4) 式中： N 是文档总数；nr 是提取的代表性新闻数； dist 表示两文档间归一化的欧式距离。新闻文档 接近度考虑在合理的代表性新闻文档数的情况 下，代表性新闻在内容上对整体新闻流的覆盖程 度，DP 值越小，说明提取的代表性新闻在内容上 的覆盖程度越高。 3.3 实验结果与分析 通过爬取人民日报 2019 年 6 月初到 7 月中 旬的时政报道，筛选出 530 篇长文档，按照报道 发表的时间排序，精确到天。对该新闻数据集 人工标记了 43 个事件话题，其数量分布如图 4 所示。 中美经贸摩擦 不忘初心、牢记使命 二十国集团领导人第十四次峰会 习近平将对吉尔吉斯斯坦、塔吉克斯坦进行国事访问 习近平对朝鲜民主主义人民共和国进行国事访问 一带一路 香港事务 多地遭遇强降雨 其他 15.280 0% 12.452 8% 6.037 7% 6.037 7% 4.905 7% 4.150 9% 4.905 7% 3.018 9% 43.210 5% 图 4 人民日报数据集话题分布 Fig. 4 Topic distribution of People’s Daily Online dataset 采用北大开源词法分析工具 pkuseg[25] 对新闻 文档进行分词、去停用词以及 TF-IDF 权重计算。 因为人工标记的话题数为 43，实验过程中设定 kmeans++的类数为 43，标准 AP 方法偏向参数取默 认中位值。改进 single-pass 方法相似度阈值为 0.05，话题合并阈值为 0.15。IAPNA 方法初始偏 向参数为 0.0018。 首先分析 AP 算法的偏向参数 (preference) 对 文中方法的性能影响。以 10 天为时间间隔，阻尼 系数设定 为 0.9 ， 在 [0.01,0.1 ] 的范围内， 以 0.001 为步长，得到不同偏向参数下的 F1 值和 NMI 值，如图 5 所示。 0 0.02 0.04 0.06 0.08 0.10 0.55 0.60 0.65 F1 (NMI) 0.70 0.75 0.80 preference NMI F1 图 5 不同 preference 参数对性能结果的影响 Fig. 5 Performance results on with different preference parameters 从图 5 中可以看到，开始时随着偏向参数的增 加，F1 和 NMI 值均不断增加，此时偏向参数过小 生成的类数较少，许多不属于同一个事件的文档 被划分到了同一个类中，聚类的准确率较低，因而 一开始 F1 值与 NMI 值较小。偏向参数增加后，不 同的文档开始被分到不同的类中，聚类的准确率 也开始增加，F1 值与 NMI 值也随之增大。但当偏 ·1180· 智 能 系 统 学 报 第 15 卷
第6期 陈晓琪，等：增量采样聚类驱动的新闻事件发现 ·1181· 向参数增加到一定的值时，因为所有数据被选为 5种方法的运行时间结果如表2所示，为了 聚类中心的可能性增大了，所以有许多同一类的 进一步分析数据集规模对不同算法运行时间的 文档被分到不同的类中，聚类的召回率降低，此时 影响，除了在人民日报数据集上做运行时间的 F,值和NMI值开始减小。在本实验中，偏向参数 比较之外，还选取中国新闻网2018年1月国内 为0.076时，结果的F,值和NM值达到最大。 时政新闻报道，共2747篇新闻作为实验数据 本文方法与k-means-+、标准AP、改进single- 集。如表2结果所示，随着数据规模的增大，本 pass、IAPNA方法对比实验结果如表1所示，可以 文方法的运行时间增长倍数最低，尤其是相比 看出，本文方法在聚类质量上均优于其他4种方 于其他两种在线方法，本文方法有着更好的运 法，选取文档的重要性程度方面则位于中间位 行效率。 置。本文方法在F,值和NMI值均高于其他4种 方法的同时DP值较小，保证了较好的新闻内容 表25种对比方法的运行时间结果 Table 2 Comparison of the running times of the five methods 覆盖度。 方法 T(530)/s T(2747)/s T/T 表15种对比方法的实验性能结果 本文方法 4.59 14.32 Table 1 Performance comparison of the five methods 65.75 k-means++ 0.76 15.13 19.91 方法 NMI DP/10 本文方法 0.6583 0.7561 0.349 标准AP 1.43 38.88 27.19 k-means++ 0.4832 0.7047 0.781 改进single-pass 27.49 641.87 23.35 标准AP 0.5609 0.7218 0.145 IAPNA 4.56 275.80 60.48 改进single-pass 0.6505 0.7166 0.404 IAPNA 0.5843 0.7457 0.135 3.4 事件发现应用实验 考虑将本文方法应用于年度新闻热点事件发 本文方法、k-means-+、标准AP、改进single- 现中，与权威机构发布的2018年新闻评选结 pass、IAPNA的准确率、召回率、F,值、NMI值和 果进行比较，权威机构评选结果如表3所示。 DP值对比结果如图6所示。5种方法的准确率 较为相近，本文方法和改进single-pass方法的召 表3人民网评选出的2018十大时政新闻 Table 3 Top ten political news published by People's 回率要好于其他方法，综合准确率和召回率，本 Daily Online in 2018 文方法具有最高的F,值。此外，本文方法的NMI 编号 人民网评选出的2018十大时政新闻 值也是最高的，NMI值较高的还有IAPNA方法。 而从代表性新闻的内容覆盖度来看，本文方法的 《中华人民共和国宪法修正案》通过 DP值处于中间位置。AP及基于AP的方法在 2 庆祝改革开放40周年大会举行 DP值上有较好表现，标准AP方法计算与存储均 3 党和国家机构政革顺利推进 不增量，IAPNA则是计算增量、存储不增量，因此 首届中国国际进口博览会举行 在代表点选择上效果较好，本文方法计算与存储 民营企业座谈会召开 均是增量的，不可避免地有信息缺失的影响，但 AP方法的良好性能使得本文方法所得DP值小 6 全国生态环境保护大会召开 于k-means+-+和改进single--pass方法。这也从另 海南全境建设自贸区并探索实行自由贸易港政策 一个角度反映了本文所提DP性能指标的合理 港珠澳大桥正式通车运营 性，可为相关研究提供一个十分有价值的参考。 9 嫦娥四号探测器成功发射 ■本文方法 k-means++ ☑标准AP 10 个税起征点上调 1.0 口改进single-.pass口IAPNA 0.8 爬取中国新闻网2018年国内时政新闻报 道，删除篇幅过短的文章，保留共40106篇 0. 2018年时政新闻报道。以10天为时间片划分数 0 据集，用本文方法获得全年划分的事件类，经过 规模排名得到排名最靠前的10个类，从每个类 precision recall NMI DPE04 中选取本文方法所得代表性新闻以及最靠近代 图65种方法的详细性能对比 表性新闻的30篇新闻作为该类事件的推荐新 Fig.6 Detailed performance comparison of the five methods 闻，对新闻文档进行关键词提取，本实验对
向参数增加到一定的值时，因为所有数据被选为 聚类中心的可能性增大了，所以有许多同一类的 文档被分到不同的类中，聚类的召回率降低，此时 F1 值和 NMI 值开始减小。在本实验中，偏向参数 为 0.076 时，结果的 F1 值和 NMI 值达到最大。 本文方法与 k-means++、标准 AP、改进 singlepass、IAPNA 方法对比实验结果如表 1 所示，可以 看出，本文方法在聚类质量上均优于其他 4 种方 法，选取文档的重要性程度方面则位于中间位 置。本文方法在 F1 值和 NMI 值均高于其他 4 种 方法的同时 DP 值较小，保证了较好的新闻内容 覆盖度。 表 1 5 种对比方法的实验性能结果 Table 1 Performance comparison of the five methods 方法 F1 NMI DP/10−4 本文方法 0.658 3 0.7561 0.349 k-means++ 0.483 2 0.7047 0.781 标准AP 0.560 9 0.7218 0.145 改进single-pass 0.650 5 0.7166 0.404 IAPNA 0.584 3 0.7457 0.135 本文方法、k-means++、标准 AP、改进 singlepass、IAPNA 的准确率、召回率、F1 值、NMI 值和 DP 值对比结果如图 6 所示。5 种方法的准确率 较为相近，本文方法和改进 single-pass 方法的召 回率要好于其他方法，综合准确率和召回率，本 文方法具有最高的 F1 值。此外，本文方法的 NMI 值也是最高的，NMI 值较高的还有 IAPNA 方法。 而从代表性新闻的内容覆盖度来看，本文方法的 DP 值处于中间位置。AP 及基于 AP 的方法在 DP 值上有较好表现，标准 AP 方法计算与存储均 不增量，IAPNA 则是计算增量、存储不增量，因此 在代表点选择上效果较好，本文方法计算与存储 均是增量的，不可避免地有信息缺失的影响，但 AP 方法的良好性能使得本文方法所得 DP 值小 于 k-means++和改进 single-pass 方法。这也从另 一个角度反映了本文所提 DP 性能指标的合理 性，可为相关研究提供一个十分有价值的参考。 0.0 0.2 0.4 0.6 0.8 1.0 本文方法 k-means++ 标准 AP 改进 single-pass IAPNA precision recall F1 NMI DPE04 图 6 5 种方法的详细性能对比 Fig. 6 Detailed performance comparison of the five methods 5 种方法的运行时间结果如表 2 所示，为了 进一步分析数据集规模对不同算法运行时间的 影响，除了在人民日报数据集上做运行时间的 比较之外，还选取中国新闻网 2018 年 1 月国内 时政新闻报道，共 2 747 篇新闻作为实验数据 集。如表 2 结果所示，随着数据规模的增大，本 文方法的运行时间增长倍数最低，尤其是相比 于其他两种在线方法，本文方法有着更好的运 行效率。 表 2 5 种对比方法的运行时间结果 Table 2 Comparison of the running times of the five methods 方法 T1 (530)/s T2 (2 747)/s T2 /T1 本文方法 4.59 65.75 14.32 k-means++ 0.76 15.13 19.91 标准AP 1.43 38.88 27.19 改进single-pass 27.49 641.87 23.35 IAPNA 4.56 275.80 60.48 3.4 事件发现应用实验 考虑将本文方法应用于年度新闻热点事件发 现中，与权威机构发布的 2018 年新闻评选结 果 [26] 进行比较，权威机构评选结果如表 3 所示。 表 3 人民网评选出的 2018 十大时政新闻 Table 3 Top ten political news published by People’s Daily Online in 2018 编号 人民网评选出的2018十大时政新闻 1 《中华人民共和国宪法修正案》通过 2 庆祝改革开放40周年大会举行 3 党和国家机构改革顺利推进 4 首届中国国际进口博览会举行 5 民营企业座谈会召开 6 全国生态环境保护大会召开 7 海南全境建设自贸区并探索实行自由贸易港政策 8 港珠澳大桥正式通车运营 9 嫦娥四号探测器成功发射 10 个税起征点上调 爬取中国新闻网 2018 年国内时政新闻报 道，删除篇幅过短的文章，保留 共 4 0 1 0 6 篇 2018 年时政新闻报道。以 10 天为时间片划分数 据集，用本文方法获得全年划分的事件类，经过 规模排名得到排名最靠前的 10 个类，从每个类 中选取本文方法所得代表性新闻以及最靠近代 表性新闻的 30 篇新闻作为该类事件的推荐新 闻，对新闻文档进行关键词提取，本实验 对 第 6 期 陈晓琪，等：增量采样聚类驱动的新闻事件发现 ·1181·
·1182· 智能系统学报 第15卷 2018年新闻数据集用本文方法进行5次热点事 集。本文方法得到的新闻事件发现结果如表4 件发现工作，最终展示结果为5次实验结果的并 所示。 表4本文方法提取的代表性新闻文档对应关键词及其事件 Table 4 Representative documents and their corresponding events extracted by our method 本文方法得到的热点事件类的重要文档关键词 对应事件 改革、建设、机构、社会主义、贯彻、执行… 党和国家机构改革 脱贫、攻坚、扶贫、精准、发展、贫困人口 脱贫攻坚精准扶贫 代表、委员、宪法、推进、修正案、使命… 《中华人民共和国宪法修正案》 污染、生态、督查、整改、治理、环保部门… 全国生态环境保护大会 国际、贸易、金融、海南、发展、试验区… 海南全境建设自贸区并探索实行自由贸易港政策 上合、组织、峰会、会见、青岛、国际… 上合组织青岛峰会举行 媒体、高考、服务、组织、新闻、情况… 高考 国家、合作、全面、阿联酋、中阿、金砖 习近平主席开启非洲之旅 医疗、违法、长生、发布、审批、涉案… 吉林长春长生公司问题疫苗 遭遇、游船、倾覆、救援、调查、旅游… 游船在泰国普吉岛附近海域倾覆 个人、退休、上调、文件、加减、改革 养老金上调 合作、中非、论坛、会见、峰会、北京… 中非合作论坛北京峰会 大桥、建设、仪式、港澳、启动、活动 港珠澳大桥正式通车运营 国际、博览会、中国、推动、世界、开放… 首届中国国际进口博览会 经济、问题、民营企业、对话、政策、探索 民营企业座谈会 中国、改革、庆祝、成立、时代、振兴… 庆祝改革开放40周年大会 通过与权威机构发布的2018年十大时政新 提取的热点事件中只有3个相似事件包含在 闻评选结果进行比较可以发现，本文方法提取 2018年十大时政新闻评选榜中。 的16个热点事件中有8个相似事件包含在 表5k-means+提取出的代表性新闻文档对应关键词 2018年十大时政新闻评选榜中，分别为党和国 Table 5 Key words of representative documents extracted 家机构改革、《中华人民共和国宪法修正案》、 by k-means++ 全国生态环境保护大会、海南全境建设自贸区并 编号 k-means+得到的热点事件类的重要文档关键词 探索实行自由贸易港政策、港珠澳大桥正式通车 1 代表、改革、推荐、机构、中国、组织… 运营、首届中国国际进口博览会、民营企业座谈 2 研究、院土、科学家、基因、病毒、科研… 会以及庆祝改革开放40周年大会，对应于表3 天安门广场、仪式、北京、升国旗、国旗… 序号1~8。而提取结果中的另外8个事件，除脱 中国、科学家、治疗、研究、量子、突破… 贫攻坚精准扶贫外，均被人民日报盘点为2018 代表、委员、文化、政策、呼吁、传承… 年每月大事件2阿。 6 问题、扶贫、政府、农村、整改、预算… 作为对比，对2018年新闻数据集用k- > 水质、保护、环境、环境监测、治理、管理… means+-+方法进行事件发现工作，结果如表5所 8 高校、中国、人才、大学生、大赛、创新… 示。表5中序号1~3对应的事件为党和国家机构 9 回应、中国、国际、南海、关系、制裁… 改革、2位院士获国家最高科技奖、天安门升旗仪 10 中国、合作、一带一路、建设、国家… 式，序号6~7对应事件为脱贫攻坚精准扶贫、全 案件、监察、监察机关、检方、公安部、专项… 国生态环境保护大会，序号10对应事件为一带一 12 大桥、完成、工程、港澳、开通、世界… 路，序号12对应事件为港珠澳大桥正式通车运 13 精神、工作、红色、时代、举办、发展… 营。序号4、5、8、9、11、13、14、15对应于科学、 14 科学家、突破、太空、载人、执行、黑洞… 文化、教育、军事、监察等领域，但没有特殊的关 专项、执法、整治、违法、生产、违规… 键词能推测出具体的事件。此外，k-means-+方法
2018 年新闻数据集用本文方法进行 5 次热点事 件发现工作，最终展示结果为 5 次实验结果的并 集。本文方法得到的新闻事件发现结果如表 4 所示。 表 4 本文方法提取的代表性新闻文档对应关键词及其事件 Table 4 Representative documents and their corresponding events extracted by our method 本文方法得到的热点事件类的重要文档关键词 对应事件 改革、建设、机构、社会主义、贯彻、执行… 党和国家机构改革 脱贫、攻坚、扶贫、精准、发展、贫困人口… 脱贫攻坚精准扶贫 代表、委员、宪法、推进、修正案、使命… 《中华人民共和国宪法修正案》 污染、生态、督查、整改、治理、环保部门… 全国生态环境保护大会 国际、贸易、金融、海南、发展、试验区… 海南全境建设自贸区并探索实行自由贸易港政策 上合、组织、峰会、会见、青岛、国际… 上合组织青岛峰会举行 媒体、高考、服务、组织、新闻、情况… 高考 国家、合作、全面、阿联酋、中阿、金砖… 习近平主席开启非洲之旅 医疗、违法、长生、发布、审批、涉案… 吉林长春长生公司问题疫苗 遭遇、游船、倾覆、救援、调查、旅游… 游船在泰国普吉岛附近海域倾覆 个人、退休、上调、文件、加减、改革… 养老金上调 合作、中非、论坛、会见、峰会、北京… 中非合作论坛北京峰会 大桥、建设、仪式、港澳、启动、活动… 港珠澳大桥正式通车运营 国际、博览会、中国、推动、世界、开放… 首届中国国际进口博览会 经济、问题、民营企业、对话、政策、探索… 民营企业座谈会 中国、改革、庆祝、成立、时代、振兴… 庆祝改革开放40周年大会 通过与权威机构发布的 2018 年十大时政新 闻评选结果进行比较可以发现，本文方法提取 的 1 6 个热点事件中 有 8 个相似事件包含 在 2018 年十大时政新闻评选榜中，分别为党和国 家机构改革、《中华人民共和国宪法修正案》、 全国生态环境保护大会、海南全境建设自贸区并 探索实行自由贸易港政策、港珠澳大桥正式通车 运营、首届中国国际进口博览会、民营企业座谈 会以及庆祝改革开放 40 周年大会，对应于表 3 序号 1~8。而提取结果中的另外 8 个事件，除脱 贫攻坚精准扶贫外，均被人民日报盘点为 2018 年每月大事件[27]。 作为对比， 对 201 8 年新闻数据集 用 k - means++方法进行事件发现工作，结果如表 5 所 示。表 5 中序号 1~3 对应的事件为党和国家机构 改革、2 位院士获国家最高科技奖、天安门升旗仪 式，序号 6~7 对应事件为脱贫攻坚精准扶贫、全 国生态环境保护大会，序号 10 对应事件为一带一 路，序号 12 对应事件为港珠澳大桥正式通车运 营。序号 4、5、8、9、11、13、14、15 对应于科学、 文化、教育、军事、监察等领域，但没有特殊的关 键词能推测出具体的事件。此外，k-means++方法 提取的热点事件中只 有 3 个相似事件包含 在 2018 年十大时政新闻评选榜中。 表 5 k-means++提取出的代表性新闻文档对应关键词 Table 5 Key words of representative documents extracted by k-means++ 编号 k-means++得到的热点事件类的重要文档关键词 1 代表、改革、推荐、机构、中国、组织… 2 研究、院士、科学家、基因、病毒、科研… 3 天安门广场、仪式、北京、升国旗、国旗… 4 中国、科学家、治疗、研究、量子、突破… 5 代表、委员、文化、政策、呼吁、传承… 6 问题、扶贫、政府、农村、整改、预算… 7 水质、保护、环境、环境监测、治理、管理… 8 高校、中国、人才、大学生、大赛、创新… 9 回应、中国、国际、南海、关系、制裁… 10 中国、合作、一带一路、建设、国家… 11 案件、监察、监察机关、检方、公安部、专项… 12 大桥、完成、工程、港澳、开通、世界… 13 精神、工作、红色、时代、举办、发展… 14 科学家、突破、太空、载人、执行、黑洞… 15 专项、执法、整治、违法、生产、违规… ·1182· 智 能 系 统 学 报 第 15 卷
第6期 陈晓琪，等：增量采样聚类驱动的新闻事件发现 ·1183· 相比之下，本文方法得到的代表性新闻粒度 [4]GENG Xiao,ZHANG Yanmei,JIAO Yuhang,et al.A 更细，提取的关键词中能够包含热点事件的特殊 novel hybrid clustering algorithm for topic detection on 名词，事件发现质量更高。而k-means+方法初 Chinese microblogging[J].IEEE transactions on computa- 始点的选择对结果影响较大，虽然能在一定程度 tional social systems,2019.6(2):289-300. 上划分事件的领域，但是在提取细化的热点事件 [5]GUAN Renchu.SHI Xiaohu,MARCHESE M,et al.Text 上结果较差。 clustering with seeds affinity propagation[].IEEE transac- tions on knowledge and data engineering,2011,23(4): 4结束语 627-637. [6]SHRIVASTAVA S K.RANA J L.JAIN R C.Text docu- 为获得更好的事件发现和代表性新闻抽取性 ment clustering based on phrase similarity using affinity 能，从数据集代表点采样聚类的视角，提出了增 propagation[J].International journal of computer applica- 量采样聚类驱动的事件发现新方法。新方法通过 tions,.2013,61(18):38-44. 引入两层聚类策略、单向文档内容支撑度网络和 [7]ALLAN J,PAPKA R,LAVRENKO V.On-line new event 单向事件内容支撑度网络，结合代表性新闻间基 detection and tracking[Cl//Proceedings of the 21st Annual 于内容支撑度的关系权重计算方法，有效地实现 International ACM SIGIR Conference on Research and 了按照时间顺序组织新闻文档。其中基于信息支 Development in Information Retrieval.Canberra,Aus- 撑度的事件关系权重表示方法，完成了从文档相 tralia.1998:37-45 关性网络到事件相关性网络的转换，有效地约简 [8]赵旭剑，杨春明，李波，等.一种基于特征演变的新闻话 了相似性高的新闻文档流，减少了算法所需的存 题演化挖掘方法).计算机学报，2014,37(4)819-832. 储空间和计算量。 ZHAO Xujian,YANG Chunming,LI Bo,et al.A topic 实验中使用真实新闻数据集进行性能分析， evolution mining algorithm of news text based on feature evolving[J].Chinese journal of computers,2014,37(4): 结果表明，本文方法在文档聚类质量上优于k 819-832 means+-+、标准AP、改进single-pass、IAPNA方 [9]YIN Jianhua,WANG Jianyong.A dirichlet multinomial 法，代表性新闻提取质量上处于中间位置。相比 mixture model-based approach for short text clustering[Cl// 于改进single--pass、IAPNA在线聚类方法，本文方 Proceedings of the 20th ACM SIGKDD International Con- 法有计算时间上的优势。在中国新闻网2018年 ference on Knowledge Discovery and Data Mining.New 全年国内时政新闻文档集上的事件发现实验结 York,USA,2014:233-242. 果表明，新方法可获得非常接近于人工评选的 [10]周楠，杜攀，靳小龙，等.面向舆情事件的子话题标签 结果。 生成模型ET-TAG[J].计算机学报，2018,41(7)： 参考文献： 1490-1503. ZHOU Nan,DU Pan,JIN Xiaolong,et al.ET-TAG:a tag [1]QU Xiaoting,YANG Juan,WU Bin,et al.A news event generation model for the sub-topics of public opinion detection algorithm based on key elements recognition[Cl// events[J].Chinese journal of computers,2018,41(7): Proceedings of 2016 IEEE First International Conference 1490-1503. on Data Science in Cyberspace.Changsha,China,2016: [11]XU Guixian,MENG Yueting,CHEN Zhan,et al.Re- 394-399. search on topic detection and tracking for online news [2]YAN Danfeng,HUA Enzheng,HU Bo.An improved texts[J].IEEE access,2019,7:58407-58418 single-pass algorithm for Chinese microblog topic detec- [12]黄九鸣，吴泉源，张圣栋，等.基于AC-Trie的在线社交 tion and tracking[C]//Proceedings of 2016 IEEE Interna- 网络文本流热点短语挖掘[).电子学报，2016,44(10) tional Congress on Big Data.San Francisco,USA,2016: 2466-2470. 251-258 HUANG Jiuming,WU Quanyuan,ZHANG Shengdong, [3]路荣，项亮，刘明荣，等.基于隐主题分析和文本聚类的 et al.Mining hot phrases on sociai network text streams 微博客中新闻话题的发现，模式识别与人工智能， based on AC-Trie[J].Acta electronica sinica,2016, 2012,25(3):382-387 44(10):2466-2470 LU Rong,XIANG Liang,LIU Mingrong,et al.Discover- [13]CHEN Ling,TU Ding,LV Mingqi,et al.A knowledge- ing news topics from microblogs based on hidden topics based semisupervised hierarchical online topic detection analysis and text clustering[J].Pattern recognition and arti- framework[J].IEEE transactions on cybernetics,2019, ficial intelligence,2012,25(3):382-387. 49(9:3307-3321
相比之下，本文方法得到的代表性新闻粒度 更细，提取的关键词中能够包含热点事件的特殊 名词，事件发现质量更高。而 k-means++方法初 始点的选择对结果影响较大，虽然能在一定程度 上划分事件的领域，但是在提取细化的热点事件 上结果较差。 4 结束语 为获得更好的事件发现和代表性新闻抽取性 能，从数据集代表点采样聚类的视角，提出了增 量采样聚类驱动的事件发现新方法。新方法通过 引入两层聚类策略、单向文档内容支撑度网络和 单向事件内容支撑度网络，结合代表性新闻间基 于内容支撑度的关系权重计算方法，有效地实现 了按照时间顺序组织新闻文档。其中基于信息支 撑度的事件关系权重表示方法，完成了从文档相 关性网络到事件相关性网络的转换，有效地约简 了相似性高的新闻文档流，减少了算法所需的存 储空间和计算量。 实验中使用真实新闻数据集进行性能分析， 结果表明，本文方法在文档聚类质量上优于 kmeans++、标准 AP、改进 single-pass、IAPNA 方 法，代表性新闻提取质量上处于中间位置。相比 于改进 single-pass、IAPNA 在线聚类方法，本文方 法有计算时间上的优势。在中国新闻网 2018 年 全年国内时政新闻文档集上的事件发现实验结 果表明，新方法可获得非常接近于人工评选的 结果。 参考文献： QU Xiaoting, YANG Juan, WU Bin, et al. A news event detection algorithm based on key elements recognition[C]// Proceedings of 2016 IEEE First International Conference on Data Science in Cyberspace. Changsha, China, 2016: 394–399. [1] YAN Danfeng, HUA Enzheng, HU Bo. An improved single-pass algorithm for Chinese microblog topic detection and tracking[C]//Proceedings of 2016 IEEE International Congress on Big Data. San Francisco, USA, 2016: 251–258. [2] 路荣, 项亮, 刘明荣, 等. 基于隐主题分析和文本聚类的 微博客中新闻话题的发现 [J]. 模式识别与人工智能, 2012, 25(3): 382–387. LU Rong, XIANG Liang, LIU Mingrong, et al. Discovering news topics from microblogs based on hidden topics analysis and text clustering[J]. Pattern recognition and artificial intelligence, 2012, 25(3): 382–387. [3] GENG Xiao, ZHANG Yanmei, JIAO Yuhang, et al. A novel hybrid clustering algorithm for topic detection on Chinese microblogging[J]. IEEE transactions on computational social systems, 2019, 6(2): 289–300. [4] GUAN Renchu, SHI Xiaohu, MARCHESE M, et al. Text clustering with seeds affinity propagation[J]. IEEE transactions on knowledge and data engineering, 2011, 23(4): 627–637. [5] SHRIVASTAVA S K, RANA J L, JAIN R C. Text document clustering based on phrase similarity using affinity propagation[J]. International journal of computer applications, 2013, 61(18): 38–44. [6] ALLAN J, PAPKA R, LAVRENKO V. On-line new event detection and tracking[C]//Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Canberra, Australia, 1998: 37−45. [7] 赵旭剑, 杨春明, 李波, 等. 一种基于特征演变的新闻话 题演化挖掘方法 [J]. 计算机学报, 2014, 37(4): 819–832. ZHAO Xujian, YANG Chunming, LI Bo, et al. A topic evolution mining algorithm of news text based on feature evolving[J]. Chinese journal of computers, 2014, 37(4): 819–832. [8] YIN Jianhua, WANG Jianyong. A dirichlet multinomial mixture model-based approach for short text clustering[C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2014: 233−242. [9] 周楠, 杜攀, 靳小龙, 等. 面向舆情事件的子话题标签 生成模型 ET-TAG[J]. 计算机学报, 2018, 41(7): 1490–1503. ZHOU Nan, DU Pan, JIN Xiaolong, et al. ET-TAG: a tag generation model for the sub-topics of public opinion events[J]. Chinese journal of computers, 2018, 41(7): 1490–1503. [10] XU Guixian, MENG Yueting, CHEN Zhan, et al. Research on topic detection and tracking for online news texts[J]. IEEE access, 2019, 7: 58407–58418. [11] 黄九鸣, 吴泉源, 张圣栋, 等. 基于 AC-Trie 的在线社交 网络文本流热点短语挖掘 [J]. 电子学报, 2016, 44(10): 2466–2470. HUANG Jiuming, WU Quanyuan, ZHANG Shengdong, et al. Mining hot phrases on sociai network text streams based on AC-Trie[J]. Acta electronica sinica, 2016, 44(10): 2466–2470. [12] CHEN Ling, TU Ding, LV Mingqi, et al. A knowledgebased semisupervised hierarchical online topic detection framework[J]. IEEE transactions on cybernetics, 2019, 49(9): 3307–3321. [13] 第 6 期 陈晓琪，等：增量采样聚类驱动的新闻事件发现 ·1183·
·1184· 智能系统学报 第15卷 [14]SAYYADI H,RASCHID L.A graph analytical approach [23]DAI Xiangying,HE Yancheng,SUN Yunlian.A two-lay- for topic detection[J].ACM transactions on internet tech- er text clustering approach for retrospective news event nology,2013,13(2:4. detection[C]//Proceedings of 2010 International Confer- [15]CHEN Peixian,ZHANG N L,LIU Tengfei,et al.Latent ence on Artificial Intelligence and Computational Intelli- tree models for hierarchical topic detection[J].Artificial gence.Sanya,China,2010:364-368. intelligence,2017,250:105-124. [24]AMELIO A.PIZZUTI C.Is normalized mutual informa- [16]柏文言，张闯，徐克付，等.一种融合用户关系的自适应 tion a fair measure for comparing community detection 微博话题跟踪方法[J].电子学报，2017,45(6)： methods?[Cl//Proceedings of the 2015 IEEE/ACM Inter- 1375-1381. national Conference on Advances in Social Networks BAI Wenyan,ZHANG Chuang,XU Kefu,et al.A self- Analysis and Mining 2015.Paris,France,2015: adaptive microblog topic tracking method by user rela- 1584-1585. tionship[J].Acta electronica sinica,2017,45(6): [25]LUO Ruixuan,XU Jingjing,ZHANG Yi,et al.PKUSEG: 1375-1381 a toolkit for multi-domain Chinese word segmentation [1刀张斌，胡琳梅，侯磊，等.基于词向量的中文事件发现及 [EB/OL].[2019-06-22]http://axvio.org/abs/1906.11455. 表示.模式识别与人工智能，2018.31(3)：275-282. [26]人民日报社评选.2018国内十大新闻N.人民日报， ZHANG Bin,HU Linmei,HOU Lei,et al.Word embed- 2018-12-29(02). ding based Chinese news event detection and representa- [2]人民日报.9张图速读12个月，带你回顾即将过去的 tion[J].Pattern recognition and artificial intelligence, 2018DB/OL].人民日报微博，[2018-12-26].https:∥ 2018,31(3)275-282. baijiahao.baidu.com/s?id=1620877305413536727 [18]FREY B J,DUECK D.Clustering by passing messages 作者简介： between data points[J].Science,2007,315(5814): 陈晓琪，硕士研究生，主要研究方 972-976 向为大数据知识发现。 [19]谢振平，金晨，刘渊.基于建构主义学习理论的个性化 知识推荐模型[).计算机研究与发展，2018,55(1)： 125-138 XIE Zhenping,JIN Chen,LIU Yuan.Personalized know- ledge recommendation model based on constructivist learning theory[J].Journal of computer research and de- 谢振平，教授.博士生导师.主要 velopment,.2018.55(1:125-138. 研究方向为知识表示与认知学习。主 [20]ARTHUR D.VASSILVITSK II S.K-Means++:the ad- 持或参与完成国家、省部级科研项目 6项，承担产学研合作项目15项。获 vantages of careful seeding[C]//Proceedings of the Eight- 发明专利5项，发表学术论文30余篇。 eenth Annual ACM-SIAM Symposium on Discrete Al- gorithms.New Orleans,USA,2007:1027-1035. [21]SUN Leilei,GUO Chonghui.Incremental affinity propagation clustering based on message passing[J].IEEE 刘渊，教授，博士生导师，主要研 究方向为网络安全、数字媒体。作为 transactions on knowledge and data engineering,2014, 项目负责人完成了省部级科研项目 26(11):2731-2744. 3项。发表学术论文40余篇，出版专 [22]SALTON G,WONG A,YANG C S.A vector space mod- 著1部。 el for automatic indexing[J].Communications of the ACM1975,18(11:613-620
SAYYADI H, RASCHID L. A graph analytical approach for topic detection[J]. ACM transactions on internet technology, 2013, 13(2): 4. [14] CHEN Peixian, ZHANG N L, LIU Tengfei, et al. Latent tree models for hierarchical topic detection[J]. Artificial intelligence, 2017, 250: 105–124. [15] 柏文言, 张闯, 徐克付, 等. 一种融合用户关系的自适应 微博话题跟踪方法 [J]. 电子学报, 2017, 45(6): 1375–1381. BAI Wenyan, ZHANG Chuang, XU Kefu, et al. A selfadaptive microblog topic tracking method by user relationship[J]. Acta electronica sinica, 2017, 45(6): 1375–1381. [16] 张斌, 胡琳梅, 侯磊, 等. 基于词向量的中文事件发现及 表示 [J]. 模式识别与人工智能, 2018, 31(3): 275–282. ZHANG Bin, HU Linmei, HOU Lei, et al. Word embedding based Chinese news event detection and representation[J]. Pattern recognition and artificial intelligence, 2018, 31(3): 275–282. [17] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972–976. [18] 谢振平, 金晨, 刘渊. 基于建构主义学习理论的个性化 知识推荐模型 [J]. 计算机研究与发展, 2018, 55(1): 125–138. XIE Zhenping, JIN Chen, LIU Yuan. Personalized knowledge recommendation model based on constructivist learning theory[J]. Journal of computer research and development, 2018, 55(1): 125–138. [19] ARTHUR D, VASSILVITSKⅡ S. K-Means++: the advantages of careful seeding[C]//Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. New Orleans, USA, 2007: 1027−1035. [20] SUN Leilei, GUO Chonghui. Incremental affinity propagation clustering based on message passing[J]. IEEE transactions on knowledge and data engineering, 2014, 26(11): 2731–2744. [21] SALTON G, WONG A, YANG C S. A vector space model for automatic indexing[J]. Communications of the ACM, 1975, 18(11): 613–620. [22] DAI Xiangying, HE Yancheng, SUN Yunlian. A two-layer text clustering approach for retrospective news event detection[C]//Proceedings of 2010 International Conference on Artificial Intelligence and Computational Intelligence. Sanya, China, 2010: 364−368. [23] AMELIO A, PIZZUTI C. Is normalized mutual information a fair measure for comparing community detection methods?[C]//Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015. Paris, France, 2015: 1584−1585. [24] LUO Ruixuan, XU Jingjing, ZHANG Yi, et al. PKUSEG: a toolkit for multi-domain Chinese word segmentation [EB/OL]. [2019−06−22] http://axvio.org/abs/1906.11455. [25] 人民日报社评选. 2018 国内十大新闻 [N]. 人民日报, 2018−12−29(02). [26] 人民日报. 9 张图速读 12 个月, 带你回顾即将过去的 2018[DB/OL]. 人民日报微博, [2018−12−26]. https:// baijiahao.baidu.com/s?id=1620877305413536727. [27] 作者简介： 陈晓琪，硕士研究生，主要研究方 向为大数据知识发现。 谢振平，教授，博士生导师，主要 研究方向为知识表示与认知学习。主 持或参与完成国家、省部级科研项目 6 项，承担产学研合作项目 15 项。获 发明专利 5 项，发表学术论文 30 余篇。 刘渊，教授，博士生导师，主要研 究方向为网络安全、数字媒体。作为 项目负责人完成了省部级科研项目 3 项。发表学术论文 40 余篇，出版专 著 1 部。 ·1184· 智 能 系 统 学 报 第 15 卷