第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·