信息内容安全：话题检测新方法

话题检测意在检测出新事件的出现，并将新来的新闻报道归入不同的事件簇。通常的聚类可看做是基于全局信息的聚类，即在整个数据集合上进行聚类，但话题检测中用到的聚类是以增量方式进行的。话题检测可以看做是一种按事件的聚类，它作为一种增量聚类，可以划分为两个阶段：首先是识别出新事件的出现；其次是将描写先前遇到的新闻报道归入相应的事件簇。由于话题检测是一种特殊的文本聚类过程，因此在介绍常用的探测方法之前，我们首先介绍聚类分析的基本原理。聚类分析是数据挖掘中的一个很活跃的研究领域，常用的聚类分析算法可以被分为基于划分的方法、基于分层的方法、基于密度的方法和基于网格的方法等。

聚类算法的基础是聚类准则的确定，假定有一组样本（x₁，x₂，…，x_N），要求把它确切地分成（ω₁，ω₂，…，ω_M）个类，可以存在多种分类，如果要评价各种聚类算法的优劣就必须定义一个准则函数。这样，聚类问题就变成对这个准则函数求极值的问题，这里介绍3种准则：误差平方和准则、与最小方差有关的准则以及散布准则。

（1）误差平方和准则。误差平方和准则是聚类分析中最简单而又广泛应用的准则，其准则函数为

式中，C为聚类数，f_i为第i个聚类中心域的样本集：

N_i是f_i中的样本数，使J最小化的聚类就是最合理的聚类。

当每一类的样本都很密集，而各类之间又有明显的分离，使用这种准则进行聚类可获得较好的效果，否则使用这种准则得到的效果就不太令人满意。

当各类中的样本数目相差很大而类间距离较小时，有可能把样本数目多的一类一拆为二，这样聚类的结果，误差平方和准则函数J比保持完整时微小，因此有可能发生错误聚类。

（2）与最小方差有关的准则。经过简单的代数运算，可以将上述J的表达式中均值向量m_i消去，得到另一种准则函数表示形式：

式中，C是聚类数，N_i是第i个聚类域中的样本数，S_i是相似性算子，是第i类点间距离平方的平均，是以欧氏距离作为相似性度量的。

若以非尺寸的相似性函数S（x，x′）来取代相似性算子S_i中的欧氏距离

（3）散布准则。第i类的均值向量：

总平均向量：

第i类的散布矩阵：

类内散布矩阵：

类间散布矩阵：

总散布矩阵：

根据以上定义可以推出，总散布矩阵等于类内散布矩阵与类间散布矩阵之和，总散布矩阵与如何划分类别无关，仅与全部样本有关，但类内和类间散布矩阵都与类别划分有关。这两矩阵有一互补关系，因此使类内散布矩阵最小就是使类间散布矩阵最大。

研究者常采用的算法有Single-pass法、K均值法、Constructive-competition法和基于层次的方法等，下面分别给予介绍：

1.Single-pass法

Single-pass法简单高效，具有较快的执行速度，不足之处是探测结果依赖于语料被处理的顺序。该算法依次处理输入文档，一次一篇，以增量的方式进行动态聚类，第一篇新闻报道被表示为事件模板，每一个后续的报道和它前面的所有事件模板进行匹配，根据相似度度量，报道被分配给最相似的事件，并且此时的事件模板需要重新计算。如果该报道和所有事件模板的相似度度量均小于某一阈值，则将该报道表示为一个新的事件种子。不同的阈值设置可以得到不同颗粒度大小的事件簇。

参考文献[19]中也用到了一种基于Single-pass的话题检测法，Single-pass法的一个关键步骤是关于当前文档和事件模板的相似性测度，参考文献[19]将基于“日”的时间距离引入到了当前文档和事件模板的相似性测度中，之所以采用基于日而不是基于“时”、“分”等，是考虑到不同的新闻媒体对同一事件的同一发展阶段的报道受多种因素的影响多少会存在一定的时间差，这中差别虽然一般不大（多数在一日之内）但也不能忽略其对利用时间信息的话题检测系统性能的影响，采用基于“日”的时间距离在某种程度上可以消除这种时间差所造成的不利影响。基于“日”的时间距离定义为如下：

Distance _i（d_i，ET）=min（|data_d-data_EventB|，|data_d-data_EventE|）（4-12）式中，由data_d是当前报道的标注时间，data_EventB是事件ET发生的时间，data_EventE是事件的结束时间。当前新闻报道d_i和事件模板的相似度，定义为

CMU的研究者采用了一种带有时间窗的Single-pass法进行事件的探测^[20]，新闻报道向量和事件模板之间的相似度计算采用两种基于时间惩罚函数的向量夹角余弦度量。第一种是计算在时间窗口之内的报道向量和事件模板之间的相似度，计算公式如下：{^当_其时他间窗内存在属于事件c的报道时（4-14）

第2种方法认为报道向量和事件模板之间的相似度应该随着当前报道和其属于的事件模板最近报道成员之间的报道数量的增加而降低，计算公式如下：当时间窗内存在属于事件c的报道时其他（4-15）

式中，i是当前报道s和属于事件簇c的最近报道之间的报道数；m是时间窗口内当前报道s之前的新闻报道数。Umass的研究者采用了一种改进的Single-pass法^[21]，系统中使用一组信度值表示文档，信度值由tf×idf生成。对于任意文档d和事件簇c，信度值为

d_i=belief（q_i，d，c）=0.4+0.6×tf×idf（4-16）

式中，

tf为特征q_i出现在文档中的次数，df为语料集中出现特征的文档数，dl为文档的长度，avgdl为语料集中的平均文档长度，而|c|为语料集中的文档数量。

2.K均值法

K均值法是一种适用面广、效率高的基于划分的非层级聚类，它使聚类域中所有样本到聚类中心的距离平方和最小。该算法由以下步骤组成^[22]：

步骤1：任意选择k个初始聚类中心Z₁（1），Z₂（1）…Z_k（1），一般选择给定样本集的前K个样本作为初始聚类中心；

步骤2：第K次迭代，若‖x-Z_j（k）‖<‖x-Z_i（k）‖，式中i=1，2，…，k，i≠j，则x∈f_j（k），f_j（k）位聚类中心是Z_j（k）的样本集。于是分配各样本x到k个聚类域；

步骤3：由第二步的结果，计算新的聚类中心(www.xing528.com)

这样使f_j（k）中的所有点到新的聚类中心的距离平方和最小，即使如下误差平方和准则函数最小。

步骤4：若z_j（k+1）=z_j（k）算法收敛，程序结束。否则转到步骤2。

聚类中心数K、初始聚类中心的选择、样本输入的次序，以及数据的几何特性等均影响K均值算法的进行过程。对这些算法虽然无法证明其收敛性，但当模式类之间彼此远离时这个算法所得的结果是令人满意的。

K均值算法对脏数据很敏感，例如在K均值算法中，用欧氏距离作为样本距离度量时经常会出现某类中只有一个样本数据的情况，因为这个孤立样本离其他的样本点都很远，而且它很可能是噪声数据。一种利用L_i范式的K均值变种可以避免这个问题。

该公式的好处在于其对外部孤立点不敏感，所以L_i空间的聚类倾向于相同大小的聚类集合，并且采用称为medoid的点^[23]代替上面提到的聚类中心。两者的区别在于medoid是最接近中心的实际样本点，而原来的聚类中心是样本均值。

K均值算法的迭代次数为常数，因此它的算法复杂度为O（n）。另外，针对样本数据与几个聚类中心都相等的情况，有两种解决措施，一是随意将其判定为某个类别，二是稍微对该样本数据加入一些扰动信息，从而避免“等距”情况的出现。

BNN采用一种增量K均值算法^[24]探测新闻事件。和传统K均值聚类不同的是，BBN采用的算法不需要事先确定聚类簇数，为了比较新闻报道之间的相似性，它采用一种或然性文档相似性测度和一种传统的向量空间测度，前者也称为BBN事件发现测度，该测度产生于贝叶斯规则：

其中P（C|S）指当前报道属于事件簇C的概率，p（C）指任一篇新报道和聚类簇C相关的先验概率，而p（s_n）指报道词条s_n的发生概率，p′（s_n|c）指平滑概率。平滑处理过程如下：

Dragon也使用K均值法进行在线话题检测，并且引入“报道本底距离”和“衰变词条”等概念来改善探测效果，该词条实际上是一个衰变参数，通过调节衰变参数和全局阈值，在线探测系统的性能也随之改变。

3.Constructive-competition法

Constructive-competition法是一种新颖的话题检测法，该算法简单描述如下：

步骤1：在输入阶段，分别确定出期望聚类中心数dc、学习速率和其初始值η0、当前聚类中心数cc、最大迭代次数T、当前迭代序号t和阈值δ；

步骤2：constructive阶段：

Do while cc<>dc

（1）

（2）如果差异值大于设定的闭值，则产生一新的聚类中心，即

更新聚类中心的权重；否则

（3）转向式（4-24）；

步骤3：competition阶段：

t←0

do while η<>0

η（t）←η₀（1-t/T）

（1）将分配给，；

（2）更新权重，；

（3）标准化权重，，t←t+1。

由以上算法可以看出，该算法可概括为两个阶段：“constructive阶段”和“competition阶段”。在前一阶段，利用余弦夹角公式来确定某样本和已存在的聚类中心之间的差异值，只要该差异值大于某经验阈值就增加新的聚类中心直到发现期望的聚类中心数。而在后一阶段，每当有新的实例出现时，通过相似度的计算来确定各类别中的“胜者”，并且只有“胜者”才有资格更新其权值，通过聚类中心之间的竞争使得每个已经发现的聚类中心移向最优聚类中心。

4.基于层次的方法

基于层次的聚类可以分为两种：凝聚的方式和分割的方式，取决于聚类层次结构的形成是自底向上的还是自顶向下的。

凝聚的方式是一种自底向上的方法，将每一条记录看作一个类，然后根据一些规则将它们聚合成越来越大的类，直到满足一些预先设定的条件。大多数的层次聚类方法属于这一类。分割的方式是一个与凝聚的方式相反的过程，将整个数据库作为一个大的类，然后按照一些规则将这个类分成小的类，直到满足一些预定的条件，例如类的数目到了预定值，最近的两个类之间的最小距离大于设定值。

参考文献[25]介绍了一种基于层次聚类的话题检测方法，首先构建一个二进制树形网络，每个节点代表一个文档类，根节点表示整个文档集，然后算法将每个叶节点分割成两个子节点，循环执行该步骤，直到某个给定的预设条件得到满足。在决定某节点是否应该分割时用到了分散函数，该函数测试同一类簇中的样本之间的聚合度。而具体实施分割操作时则使用主方向和超平面分割，二者是基于词条-文档矩阵获取的。

层次聚类虽然比较简单，但是在选择凝聚或者分割点的时候经常会遇到一些困难，这个是非常关键的，因为一旦记录被凝聚或者分割以后，下一步的工作是建立在新形成的类的基础之上的。因此，如果其中任何一步没有做好的话，就会影响最终聚类的结果。

除了以上提到的方法之外，UPenn还采用最近邻聚类策略表示每类事件簇，该方法首先将每篇报道单独视为一个事件簇，当事件簇A中的任一报道和事件簇B中的任一报道的相似度超过一指定阈值，则将两个事件簇合并为一类。如果某篇新闻报道不能归入任何一个已知的事件簇，则将其作为对某个新事件的首次报道，并为它建立一个新事件簇。