论文部分内容阅读
文本聚类是信息检索(Information Retrieval:IR)和数据挖掘(Data Mining:DM)等领域的一个重要研究方向。它是一种无监督的分类方法,根据样本自身的特点分成若干类,使得类内样本的相似性尽可能大、类间样本的相似性尽可能小。常用的系统聚类法聚类比较准确,但计算量很大。对样本数很多且维数很高的问题,这种方法的缺陷更为显现。受迭代方法思想的启发,人们提出了动态聚类法(也称逐步调整法),从而减少了计算量,这种算法的执行与参数设置是否得当密切相关,往往需要对样本数据的物理意义进行必要的分析。在高维且数据量大的情况下,设置合理的参数尤为困难,只能通过多次实验比较来选定;另一方面,聚类的初始数据集和目标函数都是离散量,存在许多局部极值点,而通常的动态聚类法没有判别劣值的机制,因此初始聚类中心和样本输入的次序对最终结果有着很大的影响。 遗传算法(Gentic Algorithm:GA)是一种模拟自然进化过程在全局搜索最优解的方法。本文利用遗传算法来解决对初始解敏感、易陷于局部最优的文本聚类问题,提出了基于遗传算法的动态文本聚类。我们采用二进制编码方式对聚类中心进行编码,以类内中的点与其类中心的欧氏距离作为适应度函数。通过遗传算法的选择、交叉、变异三个算子操作对类中心进行逐步迭代调整,直至适应度函数收敛,得到使聚类划分效果最好的聚类结果。在英文语料库Reuters-21578上的前10个常见类(Top10)实验结果表明:1)该方法可以克服局部极值点的问题;2)聚类结果的评价指标纯度(Purity)也比较好。如何把本方法运用于中文语料库和海量数据集有待我们进一步研究。 本文的创新之处主要有: 1) 在K-均值文本聚类算法的基础上,引入了遗传算法的思想; 2) 验证和分析了本文算法在英文数据集上的聚类性能,并把它与其它聚类算法的性能进行了比较。