基于遗传算法的文档聚类算法的设计与仿真(英文)

Design and simulation of a document clustering algorithm based on genetic algorithm

在各种聚类算法中,K-means是一种基于划分的经典算法.但是由于K-means方法对于初始中心点的选择非常敏感,有可能导致聚类结果收敛于局部,本文提出了一种基于遗传算法来对类中心点进行全局寻优的文档聚类算法.在传统相似度计算的方法中,文档相似矩阵为绝大部分元素为0的稀疏矩阵,忽略了关键字之间的部分相似性,影响了文档之间的相似度.为此,本文改变了传统相似度计算的方法,通过关键字之间的部分相似度,设计出更加精确的文档相似度计算公式.在遗传算法的设计中,将K个类中心点组成的矩阵作为初始个体,采用浮点数进行编码;适应度函数采用所有类内距离的均方差之和加1的倒数表示,当类内均方差之和越小,则个体的适应度越大,被选择进入下一代的概率也越大.通过选择、交叉和变异等步骤对聚类的中心点进行反复迭代寻优,最终找到最优的类中心点.通过实验仿真,K-means收敛速度快,聚类的平均目标函数大于genetic algorithm(GA)且正确率明显小于GA.本文提出的GA算法的分类正确率能达到98%以上,与传统的K-means方法相比,聚类的准确性更高,说明本文提出的算法是一种行之有效的文档聚类方法.

Among various document algorithms, K-means is a classical one. However it is a greedy algorithm, which is sensitive to the choice of cluster center and is much easier to result in local optimization. As genetic algorithm （GA） is a global convergence algorithm and the best cluster center can be found easily, a new dynamic document clustering method based on GA is presented in this paper. Reviewing all kinds of traditional document clustering methods, the partial similarity of keywords was not taken into account, so the document similar matrix is a sparse matrix. To some extent, the accuracy of document similarity is influenced. In this paper, some new formulas are given which are improved based on the traditional method. The formulas take the partial similarity of keywords into account, thus improving the accuracy of the calculation of similarity. In this algorithm, the single individual is presented by a matrix which consists of K cluster centers. All individuals are encoded by floating-point numbers. The reciprocal of the sum of mean square deviation of intra class distance plus one is adopted as the fitness function. The smaller the fitness function, the littler probability that the individual can be selected to enter the next generation. The optimal cluster center is finally found by the following iteration process： selection, crossover, mutation and so on. The simulation results show that the accuracy of this classification can reach over 98 percent and the algorithm is superior to K-means in performance. Thus, the algorithm of this paper is an effective method of document clustering.