一种改进的CURE的事件聚类方法

李静月，徐济成，朱　昊

(中澳科技职业学院信息技术与艺术传媒系， 安徽　合肥　230000)



一种改进的CURE的事件聚类方法

李静月，徐济成，朱昊

(中澳科技职业学院信息技术与艺术传媒系， 安徽合肥230000)

[摘要]一个文档往往包含多个主题的事件，把分散在多个文本中的同一主题事件组织起来依靠传统的文本聚类是无法实现的.本文通过对已有的CURE算法进行分析，根据事件的特征，对代表点的选取和小类合并机制进行改进，实现了一个改进的CURE算法.实验结果表明：改进后的方法在保证执行效率的情况下取得了更好的聚类效果.

[关键词]层次聚类；CURE；代表点；事件聚类 从互联网上获取关于H1N1的文档460篇，这些文章经过提取后，获取关键语句7 589句作为测试语料.人工把句子分成6类，实验采用了查准率P、查全率R和F-Measure综合评价的方法来判断聚类的效果.具体定义如下：

随着计算机的普及和网络的飞速发展，互联网上的各类信息以及各种电子文档资源以空前速度增长.但是，占信息比重最大的文本数据却存在组织无结构的问题，并且散布于网络各个角落，大大降低了网络文本信息的利用效率.如何对文本信息进行有效组织和提取，并分门别类地呈现给用户，是我们面临的一个问题.文本聚类方法可以为各种文本信息处理应用提供有效的处理方法.传统的聚类方法有：划分方法、层次方法、基于密度的方法、网格的方法以及基于模型的方法，此外还有改进的混合聚类方法[1,2].绝大多数聚类算法或者擅长处理球形与相似大小的聚类，或者在存在孤立点时变得比较脆弱.但是，一个文档往往包含多个主题的事件，把分散在多个文本中的同一主题事件组织起来依靠传统的文本聚类是无法实现的.

本文以同一事件的多个相关文本为研究对象，实验文本具有以下主要特点：第一，文本相关性大，同一句式出现较为频繁；第二，句子与事件某一方面的对应关系较为明确.因此把相似的句子归为一类，就可得到关于某一事件的各个侧面信息并分别呈现给用户.CURE[3](Clustering Using Representatives)算法用多个代表点来表示一个类可以发现任何形状的簇，并且在处理孤立点上也更加健壮.本文在借鉴传统的聚类方法的基础上，将CURE方法在代表点的选取和合并策略方面进行改进，同时根据待聚类句子的特征优化句子相似度计算方法.实验证明：本文提出的方法可以提高句子相似度计算和聚类结果的准确性，形成关于各主题的由句子组成的类.

1CURE层次凝聚算法分析

在聚类算法中，类的表达方式有两种：一是用一个点来表示，这个点可以是最靠近均值点的那个实际数据点，也可以使用不存在的均值点.该方法使用于类分布良好、呈现超球形状而且密度大小变化不大的情况.第二是用全部数据点表示，这种方法能发现任意形状的类，但受噪声点影响大，当数据量较大时运行时间很长.CURE[4,5]采用固定个数的点来表示一个类，先从类中选出分布良好、能体现类形状的点，再把这些点向类的中心收缩，得到类的代表点；然后根据类间的相似度来选取要合并的类，在类合并过程中，如果一个类增长太慢，就认为该类中的点是噪声，去掉它.这种方法使得CURE不但能识别任意形状的类，而且能削弱噪声的影响.

CURE方法的实现步骤如下：

1)把每个点当作一类，选取两个距离最近类进行合并.

2)选取类的代表点：落在每个新形成的类中的代表点根据用户定义的一个收缩因子收缩或向类中心移动.

3)删除异常点：如果一个类增长太慢就删除它，在聚类的最后将非常小的簇删除.

但是该算法仍然存在不足，容易把边缘的噪声点选为代表点，而且在小类合并的时候仅考虑两个类中代表点对的最小距离，在一些情况下无法得到好的聚类效果.本文从代表点的选取和合并规则两个方面改进CURE算法.

2改进的CURE聚类方法

2.1　代表点的选取

CURE算法中类代表点通过如下方式产生：第一代表点是距离该聚类中心点最远的数据点，其后的代表点是选取距离前一个选出的代表点距离最远的数据点.然后根据一个特定的分数或收缩因子“收缩”或移动代表点得到最终的代表点.当簇的形状、分布或密度不一致时可能选取不合理的代表点，例如：一个簇中共有20个句子，其中15个句子很相似，另外5个句子散在15个句子周围，利用原有的代表点选取方法，会选择分布稀疏的点作为代表点，一些情况下，这些点很有可能是噪声点.其本质原因在于CURE选取簇边缘的数据点作代表点的概率比较大，而在很多情况下簇边缘的点往往并不能代表簇，并且成为噪声点的概率较大.

基于以上分析，本文对代表点的选取进行了改进.同一句子在一类文章中出现的次数越多，则说明该句子对表达事件主题有重要影响，能很好地描述事件的一个主题；在一个小类中，如果到一个代表点的距离最近的句子总数比较多则说明该代表点是个好的代表点.如果到一个代表点距离最近的句子数只有一个或者很少，则说明该代表点是一个很不好的代表点.设Sm是中心点,则句子Sq到中心点的距离为：

(1)

其中：f为句子在整个文本集中出现的频率，N为当前类中所有句子的出现频率之和，Sim(Sm,Sq)是两个句子的相似度.相似度计算采用基于相同词串和权值的方法.

1)选取小类的中心点作为第一个代表点.

2)在剩余的句子中选取距离已选取的代表点最小距离最大的句子作为新的代表点.不断进行，直到找到c个代表点为止.

2.2　小类合并的改进

CURE在小簇合并时，选择有最近距离代表点对的两个簇进行合并(计算两个小簇的相似度时仅考虑了两个小簇的代表点之间的最小距离).这种策略使得簇的个别代表点可能较严重地影响簇间的相似度，而且这种相似性度量忽略了簇本身的部分信息.

为了尽量避免上述情况发生，本文选择两个直接互相接近的数据点多的类进行合并，用句子相似度来表示代表点之间的距离，相似度越大距离越小.合并策略为：代表点之间的最小距离小于阈值个数k来代表类之间的相关度，k值越大则类间相关度越大.在每次小类的合并时都选出相关度最大的两个类进行合并，然后计算新类的相关度.

2.3　基于CURE的句子聚类流程

根据待聚类句子的特点，先对句子进行预处理，以提高聚类效果.首先，统一命名实体、时间和数字的格式.表达相同内容的词语或者是表达相同类的词语被看作不同项会降低聚类效果.因此，统一人名、数字、机构名、地名和时间短语，只考虑这些词的词性信息而忽视词形的差异.这样能提高关键词抽取效果.其次，对句子中的关键动词进行同义词扩充.句子相似度计算[6]通常采用的是基于词语建立向量空间模型的方法，一个句子可视为n维空间中的一个向量.通过计算向量间的夹角余弦值得到句子相似度[7]，同义词被看成不同的词语降低了句子的相似度，影响了句子聚类的效果.由于句子包含信息量少，汉语句子以字和词语为中心表达意思，在一个句子内可用于聚类的特征少，这直接影响了聚类的效果.为了消除这种影响和减少句子相似度计算的难度，首先对句子中的关键动词进行同义词扩充.同义词扩充使得同一类中的句子包含多种表达形式，而且进行句子相似度计算时不用考虑同义词的计算.

具体步骤如下：

1)预处理：统一人名、机构名、地名、数字以及时间短语，扩充句子中的关键动词和关键名词；

2)把每个句子及其扩充后的句子归为一类，合并含有相同句子的小类.把合并后的类作为初始的聚类数据；

3)在每个类中选取代表点；

4)根据类间距离合并小类；

5)删除异常点.

3实验结果与分析

(2)

(3)

(4)

(5)

(6)其中：N1为自动聚类中正确的属于类i的句子数目，N2为聚类结果中属于类i的所有句子数目，N3为人工标记属于类i的所有句子的数目.P(i)为第i个类的查准率，R(i)为第i个类的查全率.实验结果如表1所示.

表1　句子聚类结果评价

本文根据聚类句子的特点，对其进行同义词扩充，减少了句子相似度计算处理同义词的难度，代表点的选取充分考虑了小类的总体特征和代表点的代表性能，小类合并策略也考虑了小类的总体特征.实验结果表明：改进后的算法能够取得更好的聚类结果.由于句子包含信息量少，汉语句子以字和词语为中心表达意思，在一个句子内可用于聚类的特征少.这直接影响到聚类效果.此外，以命名实体识别、指代消解、词义排歧等多种自然语言处理技术作为基础，但目前的实用系统难以达到满意的效果.这也影响了句子聚类的效果.

4结语

CURE算法能够识别非球形和大小变化比较大的类，而且从两个阶段消除噪声的影响.本文在对同一事件的多个文本分析的基础上对CURE算法进行改进，用于句子聚类：代表点的选取不仅考虑到类的形状，而且考虑句子对描述事件的贡献大小；句子包含信息量少，根据两个类中代表点的最小距离来合并小类很容易丢失类的总体信息.本文在小类合并时充分考虑了小类的总体特征.实验表明，该方法能够取得较好的聚类效果.

[参考文献]

[1]Murty N, Krishna G. A hybrid clustering procedure for concentric and chain-like clusters [J]. International Journal of Computer and Information Sciences, 1981, 10(6): 397-412.

[2]Karpis G, Kumar V, Chameleon .A hierarchical clustering algorithm using dynamicmodeling[J]. Computer, 1999,32: 68-75.

[3]Wang L, Kitsuregawa M. Use link-based clustering to improve web search results [A]. In: proceedings of the second international conference on web information systems engineering [C]. Washington,DC:WISE, 2001：119-128.

[4]倪维健,黄亚楼,李飞 一种基于加权多代表点的层次聚类算法[J]. 计算机科学，2005，32(5)：150-154.

[5]魏桂英,郑玄轩.层次聚类方法的CURE算法研究[J]. 科技和产业，2005(11)：22-24.

[6]王荣波,池哲儒,常宝宝.基于词串粒度及权值的汉语句子相似度 衡量[J]. 计算机工程，2005，31(13)：142-144.

[7]冯晓云.基于云计算的文本聚类算法研究[D]. 南京：南京理工大学，2014：29-33.

(责任编辑穆刚)

An event clustering approach on the improved CURE algorithm

LI Jingyue, XU Jicheng， ZHU Hao

(Department of Information Technology and Media Arts, Anhui ZHONG-AO Institute of Technology, Hefei Anhui 230041, China)

Abstract：A document commonly contains many events with different topics, so it’s really hard for traditional clustering algorithms to organize such events with the same topic in multi-documents. Through the analysis of the feature of traditional CURE algorithm, and according to the feature of the events. This paper proposes an improved CURE algorithm that improved the selecting of representative points and clusters nesting mechanism. The experimental results show that our approach can provide better performance than that of other methods.

Key words：hierarchical clustering; CURE; representative points; event clustering

[中图分类号]TP31

[文献标志码]A

[文章编号]1673-8004(2015)05-0121-04

[作者简介]李静月(1982—)，女，河南安阳人，助教，硕士，主要从事中文信息处理方面的研究.

[基金项目]安徽省级质量工程项目 (2013TSZY088).

[收稿日期]2014-12-31