随着互联网的不断发展，网络媒体蓬勃兴起并成为新闻传播的重要途径之一。近几年，互联网新闻用户规模日益庞大，用户需求的多样性和网络信息传播的快捷性使得网络新闻数量呈井喷式增长。而另一方面，大量新闻数据并没有能提高用户获取有效信息的效率，且会因为相似新闻过多而增加用户不必要的阅读时间。因此，抽取大量新闻文档中的重要新闻，以及组织新闻流为新闻事件正成为信息推送服务的关键技术需求。

事件发现技术是信息推送服务的关键技术之一。目前，有关事件发现的大多数方法基于聚类思想实现，包括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所示。

方法框架包含两个方面的处理：

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所示。

进一步地，在单向文档关系网络上引入信息支撑度概念，信息支撑度源于建构主义学习理论中的知识支撑概念^[19]，建构主义认为知识是在其他基础知识上通过它们的相互作用而主动构建产生的。迁移到文档产生上，一篇新文档的产生通常需要借鉴和引用已有文档内容，新文档会从旧文档中汲取知识完成自身的知识构建，基于此引入关于信息支撑度的概念定义。

定义2　在文档产生中时间上的后序文档会对前序文档有一定的借鉴和引用，后序文档中内容的构建会一定程度上参考前序文档。信息支撑度描述了这一知识传递关系，表示有直接关联的前序文档对后序文档在内容上的直接支持程度。信息支撑度是一个单向的指向关系，由前序文档指向后序文档，表示由前序文档将知识传递给后序文档。

考虑新文档更可能借鉴和引用时间上更近的文档，规定两个相邻时间片上的文档间有直接关联性。这样可考虑所有前一时间片内的文档构成了对下一时间片某一文档 ${{d}}$ 的内容支撑集合，内容支撑集合对某一文档 ${{d}}$ 的支撑度总和设为1。文档间的支撑度定义为

$\left\{ \begin{array}{l} {\rm{su}}{{\rm{p}}_{j,a}} = {\rm{sim}}({{{d}}_j},{{{d}}_a}) \times \dfrac{1}{U} \\ {{{d}}_j} \in {\rm{Spa}}{{\rm{n}}_{i - 1}},\quad{{{d}}_a} \in {\rm{Spa}}{{\rm{n}}_i} \\ U = \displaystyle\sum\limits_{{{{d}}_l} \in {\rm{Spa}}{{\rm{n}}_{i - 1}}} {{\rm{sim}}({{{d}}_l},{{{d}}_a})} \\ \end{array} \right. $

(1)

式中： ${\rm{su}}{{\rm{p}}_{j,a}}$ 表示直接关联的属于时间片集合 ${\rm{Spa}}{{\rm{n}}_{i - 1}}$ 的文档 ${{{d}}_j}$ 对属于时间片集合 ${\rm{Spa}}{{\rm{n}}_i}$ 的文档 ${{{d}}_a}$ 的支撑度； ${\rm{sim}}({{{d}}_j},{{{d}}_a})$ 为两文档的余弦相似度； $U$ 为 ${\rm{Spa}}{{\rm{n}}_{i - 1}}$ 内所有文档与文档 ${d_a}$ 的余弦相似度总和。以信息支撑度为关系权重的单向文档关系网络称为单向文档内容支撑度网络。

2.2.2 单向事件内容支撑度网络

为了在获取代表性新闻文档的过程中不断约简掉非代表性新闻文档以减少计算量和所需存储空间，考虑用事件微类发现阶段产生的局部代表性新闻去代表微类。相应地，需要将单向文档内容支撑度网络转化为单向事件内容支撑度网络。同单向文档内容支撑度网络的特征相似，单向事件内容支撑度网络中只有相邻时间片上的局部代表性新闻间存在联系，同一时间片以及不相邻时间片上的局部代表性新闻间不直接相联系。为此，引入复合支撑度作为单向事件内容支撑度网络的关系权重。

定义3　单向事件内容支撑度网络构建中，两个相邻时间片上的任意两个局部代表性新闻 ${R_{i,a}}$ 、 ${R_{i + 1,b}}$ 间的复合支撑度 $ {\rm{csup}}_{{R}_{i,a},{R}_{i+1,b}}$ 定义为

$ {\rm{csup}}_{{R}_{i,a},{R}_{i+1,b}}=\mathrm{exp}\left(-\frac{\mathrm{min}(|{M}_{i,a}|,|{M}_{i+1,b}|)}{{\displaystyle \sum _{{d}_{i,x}\in {M}_{i,a}}{\displaystyle \sum _{{d}_{i+1,y}\in {M}_{i+1,b}}{\rm{sup}}_{x,y}}}}\right)$

(2)

式中： ${M_{i,a}}$ 为区间 $\left[ {{T_i},{T_{i + 1}}} \right)$ 的微类； ${R_{i,a}}$ 为 ${M_{i,a}}$ 产生的局部代表性新闻； ${M_{i + 1,b}}$ 为区间 $\left[ {{T_{i + 1}},{T_{i + 2}}} \right)$ 的微类； ${R_{i + 1,b}}$ 为 ${M_{i + 1,b}}$ 产生的局部代表性新闻； ${d_{i,x}}$ 为微类 ${M_{i,a}}$ 中的文档； ${d_{i{\rm{ + }}1,y}}$ 为微类 ${M_{i + 1,b}}$ 中的文档， ${\rm{su}}{{\rm{p}}_{x,y}}$ 意义同式(1)中 ${\rm{su}}{{\rm{p}}_{j,a}}$ 的含义 。

单向事件内容支撑度网络是增量构建的，如图1所示，其构建过程与事件微类发现流程同步。在图3中，当 ${\rm{Spa}}{{\rm{n}}_i}$ 时间片上的事件微类发现完成后，与 ${\rm{Spa}}{{\rm{n}}_{i - 1}}$ 时间片上的事件微类做复合支撑度的计算，将 ${\rm{Spa}}{{\rm{n}}_i}$ 上的微类代表性新闻文档作为节点加入到 $\{ {\rm{Spa}}{{\rm{n}}_0},{\rm{Spa}}{{\rm{n}}_1}, \cdots ,{\rm{Spa}}{{\rm{n}}_{i - 1}}\} $ 上微类代表性新闻文档构成的单向事件内容支撑度网络 ${\rm{supNe}}{{\rm{t}}_{i - 2}}$ 上，构建单向事件内容支撑度网络 ${\rm{supNe}}{{\rm{t}}_{i{\rm{ - }}1}}$ 。在这一构建过程中，事件微类发现产生的非局部代表性新闻在完成复合支撑度的计算后被约简，其包含的特征被整合为复合支撑度赋予局部代表性新闻，本身不需要参与第二层聚类运算。当新闻流中的所有文档均处理完成后，形成所有局部代表性新闻构成的单向事件内容支撑度网络，完成对所有非局部代表性新闻文档的约简。

2.2.3 相似事件聚合

考虑到单向网络的不对称性和代表点获取的需求，同样采用AP算法进行事件微类的聚合。给定 ${M_{t - 2}} \times {M_{t - 2}}$ 维相似度矩阵 ${{{S}}_{t - 2}}$ ， ${M_{t - 1}} \times {M_{t - 1}}$ 维相似度矩阵 ${{{S}}_{t - 1}}$ ，依据上述单向事件内容支撑度网络构建过程，相应的t时刻网络对应相似度矩阵 ${{{S}}_t}$ 定义为

${{{S}}_t}(i,j) = \left\{ {\begin{array}{*{20}{l}} {{{{S}}_{t - 1}}(i,j),\;\;\;\;\;\;\; i \leqslant {M_{t - 1}},j \leqslant {M_{t - 1}}} \\ {{\rm{csu}}{{\rm{p}}_{i,j}},\;\;\;\; {M_{t - 2}} < i \leqslant {M_{t - 1}},j > {M_{t - 1}}} \\ {0, \;\;\;\;i > {M_{t - 1}} {\text{或者}} i \leqslant {M_{t - 2}},j > {M_{t - 1}} } \end{array}} \right.$

(3)

基于AP算法将相似局部代表性新闻文档划分为一类，即微类聚合为大的事件类，同样依照AP聚类结果选择聚类中心作为最终的代表性新闻，只有局部代表性新闻才有可能被选为最终的代表性新闻。此外，在事件微类发现阶段，期望得到更为广泛的事件微类，有助于事件微类聚合过程中得到代表性更强、重要性更高的新闻文档，因此在事件微类发现阶段，使用文档间相似度的中位值作为AP算法的偏向参数，但在事件微类聚合阶段需要设置合适的偏向参数。

算法1　增量采样的代表性新闻提取

输入　新闻子集流 $ \{{D}_{1},{D}_{2},\cdots ,{D}_{n}\}$ ，偏向参数preference；

输出　代表性新闻集globalR。

${\rm{init}}\;{\rm{lastR}} \leftarrow {\text{Ø}} ,{\rm{lastCluster}} \leftarrow{\text{Ø}},{{G}} \leftarrow []$

${\rm{for}}\;i \leftarrow 1\;{\rm{to}}\;n\;{\rm{do}}$

${\rm{if}}\;i = 1$

根据 ${D_1}$ 获取相似度矩阵S

${\rm{lastR}},{\rm{lastCluster}}\leftarrow {\rm{AP}}({{S}},{{{S}}}_{\rm{median}})$

扩展 ${{{G}}_{0 \times 0}}$ 到 ${{{G}}_{\left| {{\rm{lastR}}} \right| \times \left| {{\rm{lastR}}} \right|}}$

else

根据 ${D_i}$ 获取相似度矩阵S

${\rm{localR}},{\rm{localCluster}}\leftarrow {\rm{AP}}({{S}},{\rm{preference}})$

扩展 ${{{G}}_{\left| G \right| \times \left| G \right|}}$ 到 ${{{G}}_{(\left| {{\rm{localR}}} \right| + \left| G \right|) \times (\left| {{\rm{localR}}} \right| + \left| G \right|)}}$

${\rm{for}}\;x \leftarrow 1\;{\rm{to}}\;\left| {\left| {{\rm{localR}}} \right| + \left| G \right|} \right|\;{\rm{do}}$

${\rm{for}}\;y \leftarrow 1\;{\rm{to}}\;\left| {\left| {{\rm{localR}}} \right| + \left| G \right|} \right|\;{\rm{do}}$

依据式(3)计算 ${{G}}[x][y]$

$ ({\rm{base\; lastR,lastCluster,localR,localCluster}}) $

end for

end for

${\rm{lastR}} \leftarrow {\rm{localR,lastCluster}} \leftarrow {\rm{localCluster}}$

end if

end for

${\rm{globalR}}\leftarrow {\rm{AP}}({{G}},{\rm{preference}})$

return globalR

2.3 已知代表性新闻的新闻文档聚类

通过增量分层采样得到代表性新闻文档后，依据最大相似度策略将非代表性新闻文档分配给一个代表性新闻文档所代表的类，完成所有文档的全局划分，划分的结果即为事件发现的结果。

算法2　已知代表性新闻的新闻文档聚类

输入　新闻子集流 $\{{D}_{1},{D}_{2},\cdots ,{D}_{n}\}$ ，代表性新闻集globalR；

输出　聚类结果 $\left\{ {C_1},{C_2}, \cdots ,{C_{\left| {{\rm{globalR}}} \right|}}\right\}$ 。

$D \leftarrow {D_1} \cup {D_2} \cup \cdots \cup {D_n}$

${\rm{for}}\;i \leftarrow 1\;{\rm{to}}\;\left| {{\rm{globalR}}} \right|\;{\rm{do}}$

${\rm{delete\; globalR}}[i]\;{\rm{ from }}\;D$

${\rm{create }}\;{C_i} \leftarrow {\text{Ø}} $

end for

${\rm{for}}\;j \leftarrow 1\;{\rm{to}}\;\left| D \right|\;{\rm{do}}$

${\rm{for}}\;i \leftarrow 1\;{\rm{to}}\;\left| {{\rm{globalR}}} \right|\;{\rm{do}}$

${\rm{calculate\; sim}}(D[j],{\rm{globalR}}[i]))$

end for

${\rm{label}} \leftarrow i|\max ({\rm{sim}}(D[j],{\rm{globalR}}[i]))$

${\rm{add }}\;D[j]{\rm{ to }}\;{C_{{\rm{label}}}}$

end for

${\rm{rerutn}}\;\{ {C_1},{C_2}, \cdots ,{C_{\left| {{\rm{globalR}}} \right|}}\}$

假设新闻流文档总数为N，时间片数为T，微类发现阶段的局部代表性新闻提取率为p，在文档规模为N的情况下，标准AP算法复杂度^[18]为 $O({N^2}\lg N)$ 。本文方法复杂度主要考虑AP算法部分和复合支撑度部分，微类发现阶段AP算法时间复杂度为 $O({N^2}/{T^2}\lg (N/T))$ ，微类聚合阶段AP算法时间复杂度为 $O({N^2}{p^2}\lg Np)(0 < p \ll 1)$ ，复合支撑度计算的事件复杂度为 $O({N^2}/{T^2})$ 。考虑 $N/T$ 的规模较小，而p正常情况是一个远小于1的数，相比于直接使用AP算法，文中方法的时间复杂度可以远远降低。

3 实验研究 3.1 实验方案

以新闻文档为研究对象，为更好地检验算法性能，实验中采用了以下几种事件发现方法作为研究：

1) k-means++方法^[20]。使用标准k-means方法对所有文档统一进行聚类，初始聚类中心依照相互较远的准则进行选择。划分的每一个类作为一个事件，选择离聚类中心最近的文档作为代表性新闻。

2)标准AP方法^[18]。使用标准AP方法对所有文档统一进行聚类，选择聚类中心对应的文档作为代表性新闻。

3)改进single-pass方法^[17]。使用时间片分层single-pass在线聚类方法增量地对文档进行处理，不同时间片间事件依据话题的相似度进行合并，选择离聚类中心最近的文档作为代表性新闻。

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)以及F₁值。标准化互信息是被广泛使用的评价聚类效果的方法，可以度量方法输出结果和真实结果之间的相似程度，NMI的取值范围为[0, 1]，越靠近1表示方法输出结果与真实结果越相似。本文采用文献[24]中NMI的计算方式。

F₁值是分类问题的一个衡量指标，也常用于文本聚类评价，是一种同时考虑准确率(precision)和召回率(recall)的综合性评价方法，是两者的调和平均数，本文采用文献[17]中准确率、召回率、F₁值的计算方式。

针对新闻代表性程度，新定义新闻文档接近度(document proximity，DP)指标来评价提取的代表性新闻对非代表性新闻的内容覆盖程度，其定义为

${\rm{DP}}\! =\! \exp \Bigg(\! - \frac{{N - {n_r}}}{{{n_r}}}\!\Bigg) \cdot \frac{{\displaystyle\sum\limits_{j = 1}^{N - {n_r}} {\min ({\rm{dis}}{{\rm{t}}_{j,1}},{\rm{dis}}{{\rm{t}}_{j,2}} \cdots ,{\rm{dis}}{{\rm{t}}_{j,{n_r}}})} }}{{N - {n_r}}}$

(4)

式中： $N$ 是文档总数； ${n_r}$ 是提取的代表性新闻数；dist表示两文档间归一化的欧式距离。新闻文档接近度考虑在合理的代表性新闻文档数的情况下，代表性新闻在内容上对整体新闻流的覆盖程度，DP值越小，说明提取的代表性新闻在内容上的覆盖程度越高。

3.3 实验结果与分析

通过爬取人民日报2019年6月初到7月中旬的时政报道，筛选出530篇长文档，按照报道发表的时间排序，精确到天。对该新闻数据集人工标记了43个事件话题，其数量分布如图4所示。

采用北大开源词法分析工具pkuseg^[25]对新闻文档进行分词、去停用词以及TF-IDF权重计算。因为人工标记的话题数为43，实验过程中设定k-means++的类数为43，标准AP方法偏向参数取默认中位值。改进single-pass方法相似度阈值为0.05，话题合并阈值为0.15。IAPNA方法初始偏向参数为0.0018。

首先分析AP算法的偏向参数(preference)对文中方法的性能影响。以10天为时间间隔，阻尼系数设定为0.9，在[0.01,0.1]的范围内，以0.001为步长，得到不同偏向参数下的F₁值和NMI值，如图5所示。

从图5中可以看到，开始时随着偏向参数的增加，F₁和NMI值均不断增加，此时偏向参数过小生成的类数较少，许多不属于同一个事件的文档被划分到了同一个类中，聚类的准确率较低，因而一开始F₁值与NMI值较小。偏向参数增加后，不同的文档开始被分到不同的类中，聚类的准确率也开始增加，F₁值与NMI值也随之增大。但当偏向参数增加到一定的值时，因为所有数据被选为聚类中心的可能性增大了，所以有许多同一类的文档被分到不同的类中，聚类的召回率降低，此时F₁值和NMI值开始减小。在本实验中，偏向参数为0.076时，结果的F₁值和NMI值达到最大。

本文方法与k-means++、标准AP、改进single-pass、IAPNA方法对比实验结果如表1所示，可以看出，本文方法在聚类质量上均优于其他4种方法，选取文档的重要性程度方面则位于中间位置。本文方法在F₁值和NMI值均高于其他4种方法的同时DP值较小，保证了较好的新闻内容覆盖度。

本文方法、k-means++、标准AP、改进single-pass、IAPNA的准确率、召回率、F₁值、NMI值和DP值对比结果如图6所示。5种方法的准确率较为相近，本文方法和改进single-pass方法的召回率要好于其他方法，综合准确率和召回率，本文方法具有最高的F₁值。此外，本文方法的NMI值也是最高的，NMI值较高的还有IAPNA方法。而从代表性新闻的内容覆盖度来看，本文方法的DP值处于中间位置。AP及基于AP的方法在DP值上有较好表现，标准AP方法计算与存储均不增量，IAPNA则是计算增量、存储不增量，因此在代表点选择上效果较好，本文方法计算与存储均是增量的，不可避免地有信息缺失的影响，但AP方法的良好性能使得本文方法所得DP值小于k-means++和改进single-pass方法。这也从另一个角度反映了本文所提DP性能指标的合理性，可为相关研究提供一个十分有价值的参考。

5种方法的运行时间结果如表2所示，为了进一步分析数据集规模对不同算法运行时间的影响，除了在人民日报数据集上做运行时间的比较之外，还选取中国新闻网2018年1月国内时政新闻报道，共2747篇新闻作为实验数据集。如表2结果所示，随着数据规模的增大，本文方法的运行时间增长倍数最低，尤其是相比于其他两种在线方法，本文方法有着更好的运行效率。

3.4 事件发现应用实验

考虑将本文方法应用于年度新闻热点事件发现中，与权威机构发布的2018年新闻评选结果^[26]进行比较，权威机构评选结果如表3所示。

爬取中国新闻网2018年国内时政新闻报道，删除篇幅过短的文章，保留共40106篇2018年时政新闻报道。以10天为时间片划分数据集，用本文方法获得全年划分的事件类，经过规模排名得到排名最靠前的10个类，从每个类中选取本文方法所得代表性新闻以及最靠近代表性新闻的30篇新闻作为该类事件的推荐新闻，对新闻文档进行关键词提取，本实验对2018年新闻数据集用本文方法进行5次热点事件发现工作，最终展示结果为5次实验结果的并集。本文方法得到的新闻事件发现结果如表4所示。

通过与权威机构发布的2018年十大时政新闻评选结果进行比较可以发现，本文方法提取的16个热点事件中有8个相似事件包含在2018年十大时政新闻评选榜中，分别为党和国家机构改革、《中华人民共和国宪法修正案》、全国生态环境保护大会、海南全境建设自贸区并探索实行自由贸易港政策、港珠澳大桥正式通车运营、首届中国国际进口博览会、民营企业座谈会以及庆祝改革开放40周年大会，对应于表3序号1~8。而提取结果中的另外8个事件，除脱贫攻坚精准扶贫外，均被人民日报盘点为2018年每月大事件^[27]。

作为对比，对2018年新闻数据集用k-means++方法进行事件发现工作，结果如表5所示。表5中序号1~3对应的事件为党和国家机构改革、2位院士获国家最高科技奖、天安门升旗仪式，序号6~7对应事件为脱贫攻坚精准扶贫、全国生态环境保护大会，序号10对应事件为一带一路，序号12对应事件为港珠澳大桥正式通车运营。序号4、5、8、9、11、13、14、15对应于科学、文化、教育、军事、监察等领域，但没有特殊的关键词能推测出具体的事件。此外，k-means++方法提取的热点事件中只有3个相似事件包含在2018年十大时政新闻评选榜中。

相比之下，本文方法得到的代表性新闻粒度更细，提取的关键词中能够包含热点事件的特殊名词，事件发现质量更高。而k-means++方法初始点的选择对结果影响较大，虽然能在一定程度上划分事件的领域，但是在提取细化的热点事件上结果较差。

4 结束语

为获得更好的事件发现和代表性新闻抽取性能，从数据集代表点采样聚类的视角，提出了增量采样聚类驱动的事件发现新方法。新方法通过引入两层聚类策略、单向文档内容支撑度网络和单向事件内容支撑度网络，结合代表性新闻间基于内容支撑度的关系权重计算方法，有效地实现了按照时间顺序组织新闻文档。其中基于信息支撑度的事件关系权重表示方法，完成了从文档相关性网络到事件相关性网络的转换，有效地约简了相似性高的新闻文档流，减少了算法所需的存储空间和计算量。

实验中使用真实新闻数据集进行性能分析，结果表明，本文方法在文档聚类质量上优于k-means++、标准AP、改进single-pass、IAPNA方法，代表性新闻提取质量上处于中间位置。相比于改进single-pass、IAPNA在线聚类方法，本文方法有计算时间上的优势。在中国新闻网2018年全年国内时政新闻文档集上的事件发现实验结果表明，新方法可获得非常接近于人工评选的结果。