论文部分内容阅读
近年来,随着互联网的飞速发展,网上的信息数据也随之呈指数级增长。为有效应用互联网上的海量数据,人们迫切需要一些有力的组织和管理工具,文本聚类技术正是其中的一种。传统聚类方法的模式是基于对所有对象进行同时处理,一旦有数据更新或有新的数据需处理,算法就必须对整个数据集重新聚类。因而这种模式时间复杂度非常高,且只适合处理静态数据,而不适合动态数据的聚类。增量聚类则可较好地处理动态数据,在数据不断更新或增长的情况下,通过扩充已有的聚类结果,可避免大量重复计算,从而减少处理时间,并最终提高聚类性能。本文提出了一种新的基于簇相合性的文本增量聚类算法,它首先利用WordNet计算出每两个词项之间的语义相似度,在统计词项出现频率时,以一定准则累加与它相近词的出现频率,这样能够更准确地为词项分配频率权重。然后计算每个新增文本与所有已有簇之间的相合性,这不仅是简单地计算文本与簇心之间的相似度,同时还考虑到了每个簇之间的相似性。算法将文本加入到相合性得分最高的簇中,并更新所属簇的簇心、均值、方差等特征信息。为进一步提高聚类性能,一旦增量处理完一部分文本,算法将以同样的方式对其中不确定划分的文本进行重新分配。若有文本仍不能确定其类别,则将它加入到与之有最大相合性的簇中,这种情况并不更新该簇的簇心,以避免错误分类造成的结果偏差。本文工作主要如下:1)使用基于词项语义相似度的文本模型。它不仅统计了每个词项的出现频率,而且还根据词项之间的相似度,增加其近义词的词频,从而更加准确地分配词项频率权重。2)提出基于簇相合性的文本增量聚类算法,并使用一种新的方法来计算文本与簇之间的相合性。算法在20newsgroups数据集上进行实验验证,并与经典聚类算法k-means以及新近提出的基于相似度直方图的增量聚类算法进行了对比;使用的评价指标分别为纯度、熵、归一化互信息。此外,我们还详细分析了阈值对算法性能产生的影响。实验结果表明,三个评价指标均显示,本文提出的算法总体效果要优于对比算法,且相较于k-means,计算时间复杂度也大大降低。