基于遗传算法的文档聚类方法

© 2013年。出版社：Elsevier B.V.信息工程研究院负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectIERI Procedia 4（2013）370 - 3752013年电子工程与计算机科学一种进化的文档聚类Ruksana Akter，Yoojin Chung*韩国外国语大学计算机科学与工程系，韩国龙仁市茂贤旺山，邮编449-791摘要提出了一种基于遗传算法的文本聚类方法。我们将数据集划分为若干组，并分别对每个组应用遗传算法，而不是对整个数据集应用遗传算法。最后，我们将另一个遗传算法阶段应用于早期的结果。这允许摆脱局部极小值，这是使用遗传算法的主要问题之一。我们的建议的另一个优点是，我们不需要像大多数可用方法那样预先指定总聚类。实验结果也表明了我们的方法相比，以前的方法的优越性能。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。信息工程研究院负责评选和同行评议关键词：文档聚类;遗传算法;局部极小值;聚类评价;1. 介绍文档聚类是指将一组文档分成不同的簇，以满足两个目标：第一，相似的文档应被分组在同一簇中，第二，不相似的文档应被放置在不同的簇中。由于互联网对人们的生活方式、工作政策、通信等方面的影响，互联网的影响力不断增加由于易于使用不同的web服务，例如* 通讯作者。联系电话：+82-31-330-4625传真：+82-31-330-4120电子邮件地址：chungyj@hufs.ac.kr。2212-6678 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。信息工程研究所负责的选择和同行评审doi：10.1016/j.ieri.2013.11.053Ruksana Akter和Yoojin Chung / IERI Procedia 4（2013）370371n博客、社交网站、服务提供网站和新闻机构，大量数据被添加到万维网（Web）中。然而，这些数据大多是非结构化的。因此，当用户需要找到一个项目时，他/她需要搜索引擎的支持。在收到请求后，搜索引擎需要返回与搜索主题相关的类似文档。在这里，文档聚类起着很大的作用，以改善结果和复杂性，这样的搜索，因为它聚类相似的文件在一个组。因此，文档聚类是一个很好的研究，并吸引了许多研究人员在信息检索领域[6]。在文献中，许多算法被发现聚类文本文档。K-means [2]-[5]，[7]聚类是最流行的聚类算法之一。它将一组给定的文档聚类为K个不同的组。它非常简单，计算效率高。然而，在K均值聚类中，用户需要预先指定期望的聚类数（K此外，K均值聚类算法从初始（通常是随机的）聚类开始，其性能在很大程度上取决于[7]。近年来，一些建议被发现使用遗传算法[6]。遗传算法是一种优化技术。它遵循随机自然选择的进化原理[8]。已知它可以实现非常好的（接近最优）解决方案，特别是当空间很大且多模态时[9]。虽然遗传算法在文档聚类中的性能优于其他可用的方法[6]，但它可能会收敛到局部最优值。这就是所谓的早熟收敛现象（PCP）[10]。为了避免PCP，提出了一种用于文档聚类的双层遗传算法（DLGC）[11]。然而，如果在第一层中使用的代数变高，则需要非常高的计算。此外，它还需要预先指定集群的数量。提出了一种基于两阶段遗传算法的文本文档聚类进化方法。我们将数据集划分为若干组，并分别对每个组应用遗传算法，而不是对整个数据集应用遗传算法。最后，我们将另一个遗传算法阶段应用于早期的结果。这样就可以摆脱局部最小值。与大多数可用的方法不同，在我们的建议中也不需要预先指定预期的聚类数。实验结果也证明了所提出的方法相比，其他可用的方法具有优越的性能。论文的其余部分是论文组织如下。第2节和第3节中详细描述的拟定程序提供了拟定方法和其他一些可用方法的比较性能。最后，第四部分对本文进行了总结。2. 所提出的方法文本文档聚类算法基本上利用文档中不同术语出现的统计信息（通常是频率）。每个文档都使用这样的统计数据表示，并表示在向量空间中。最后，聚类算法实际上通过将更接近的向量放在同一分区中来划分该空间。文件的主题和内容通常被认为是由文件中的术语表示的。文档中术语的统计数据使用一些度量来表示，例如术语频率（tf），指示术语在文档中出现的次数，或布尔出现，术语是否出现在文档中。另一个衡量标准是逆文档频率（idf），测量不同文档中某个术语的存在。对于项ti，idfi是衡量以色列国防军 （1）第一章 372Ruksana Akter和Yoojin Chung / IERI Procedia 4（2013）370其中，N表示数据集中的文档数量，n表示有多少文档中有术语ti。在我们的建议中，我们使用基于Okapi规则[1]的加权词频，这使得TF和IDF的组合。在文档dj中，ti的项权重为twtf ji. 以色列国防军（2）吉勒吉tfjijiang。你好L哪里lj表示文档长度（总项），并且l表示所有项的平均长度。数据集中的文件我们使用加权词频的向量来表示文档dj，djt wj，twj，.，（3）第一次见面。其中T表示数据集中不同项的总数。因此，文档向量包括整个数据集中存在的所有术语。然而，我们不计算诸如停用词之类的少数术语，因为这些术语通常不表示与文件的内容或主题的任何关系。给定一组文档D = {d1，d2，d3，换句话说，聚类中文档之间的平均距离被最小化。聚类通常由聚类中心表示，称为质心。因此，最终的目标是最小化质心和文档之间的距离在一个集群。在这一点上，我们需要计算文档之间的相似度。不同的相似性度量，例如皮尔逊、余弦、调整后的余弦等，通常用于计算任何两个向量之间的相似程度。在我们的工作中，我们使用余弦相似度来衡量任何两个文件之间的相似程度。两个文档向量dx和dx之间的余弦相似度通过下式测量：余弦_相似度（dx， dy ）Dx. Dy| Dx|. | Dy|（四）其中，分子和分母分别是向量和它们的范数（欧几里得长度）的点积。为了应用遗传算法，我们需要定义一个染色体，它代表一个（候选）解决方案，首先。我们的工作重点是将文档划分为K个簇。换句话说，我们需要找到代表K个聚类的K个质心。因此，我们将染色体chrp定义为K个质心的向量，chrp（cen，cen，. .. ，cenK）。（五）这个定义导致比Choi等人提出的更快的收敛。[11]其中染色体此外，它也更轻处理。这里另一个重要的点是，我们不需要指定K的精确值。相反，类似于Song和Park [6]所使用的方法，我们的方法需要K值的范围[Kmin，Kmax]。因此，在群体中，在我们的方法中可能存在不同长度的染色体。Ruksana Akter和Yoojin Chung / IERI Procedia 4（2013）370373遗传算法通常从生成一个大小为P的初始种群开始，其中包含P染色体我们从数据集中选取质心的值。质心cenk是形成为如下的向量：cenk（c，c，. . 、c和T）（六）其中接收的值是从设置{twv，twv，. .. ，twNv}的不同项权重，相应期限tv存在数据集中的所有文档。然后，我们应用两个阶段的遗传算法对这个人口。在第一阶段，我们将种群分成G个分区，并对每个分区应用一个遗传算法。这种方法导致比DLGC更快的收敛[11]。在这个阶段之后，我们在第一阶段之后更新的染色体上对整个种群应用遗传算法。对于我们的遗传算法，我们选择最合适的染色体进行交叉。我们使用经典的单点交叉。根据高斯分布的概念进行变异。这种算法的选择类似于[12]中使用的算法。我们使用适应度函数为1/DB，其中DB是众所周知的Davies-Bouldin指数[13，14]。我们将终止准则设置为ITR和Smax，其中ITR表示最大迭代次数，Smax是不更新种群的连续迭代次数。3. 绩效评价在这里，我们展示了我们的实验结果，应用我们提出的方法以及其他两个众所周知的方法，即K-means聚类和基于遗传算法的方法（以下简称为GA）提出的宋和公园[6]。为了比较性能，我们采用著名的基准数据库REUTERS-21578。我们的数据集包括来自5个主题的1000个文本，如acq，原油，贸易，谷物和货币外汇。在停止病房删除和词干，有7142项。我们设置遗传算法的参数，如选择，交叉和变异的数量分别为0.6，0.2和0.2。我们设定Smax= 10。对于GA [6]，我们设置ITR= 200。对于我们提出的算法，我们对种群进行五次划分（G= 5），并将第一阶段的ITR设置为25。对于第二阶段，我们设置ITR= 75。这确保了我们的算法所使用的最大迭代次数总共最多为200。我们这样做是为了进行票价比较。Fig. 1.三种不同算法的F-测度。374Ruksana Akter和Yoojin Chung / IERI Procedia 4（2013）370为了量化不同方法的性能，我们采用F-度量度量[15]。F测量值F的计算公式为：精确度和召回率。（七）精确召回图1显示了不同算法的F度量值。它清楚地表明了所提出的方法的优越性。我们还在我们的数据集上应用了潜在语义索引（LSI）[6]，并将维度降低到500。然后我们在结果数据集上运行三个算法。图2显示了结果的F度量。在这里，所提出的方法的性能也明显领先于其他方法。1.00.80.60.40.20.0K-means[6]提出图二、在使用LSI创建的数据集上运行时，三种不同算法的F测量值4. 结论在本文中，我们提出了我们的工作，使用遗传算法的文档聚类。所提出的方法具有所需的无监督聚类的标准，如不需要预先指定所需的集群数量和避免局部极小值的强度。在基准数据集上的实验结果也表明，该方法优于现有的文档聚类方法。作为我们未来的工作，我们希望在这个算法上做更多的工作，使它完全自动化，这样它就不需要指定参数。确认这项工作得到了2012年韩国外国语大学研究基金的支持引用[1] Salton，G.，和Buckley，C.一九八八年自动文本检索中的术语加权方法信息Ruksana Akter和Yoojin Chung / IERI Procedia 4（2013）370375处理和管理。[2] Jain，A.K.，Murty，M.N.，和弗林P.J. 1999年。数据聚类：综述. ACM Computing Surveys，Vol.31，No. 3.第三章。[3] Jain，A.K. 2008.数据聚类：超越K-means的50年第19届国际模式识别会议。佛罗里达州坦帕[4] Jain，A.K.，和Dubes，R.C. 1988.数据聚类算法。普伦蒂斯-霍尔高级参考系列。PrenticeHall，NJ.[5] Duda，R.O.，哈特体育Stork，D.G.两千模式分类，第二版。威利-跨科学公司[6] 宋，W.，Park，S.C. 2009.基于潜在语义索引的文本聚类的遗传算法，计算机与数学及其应用，第57卷，pp. 1901-1907年。[7] Cha，S.M.，和Kwon，K.H. 2001.一种新的多种群遗传算法的迁移方法。韩国信息科学家和工程师协会。[8] 毛利克湾和Bandyopadhyay，S. 2000.基于遗传算法的聚类技术。Pattern Recognition，vol33，no. 9，pp 1455-1465.[9] Srinivas，M.和Patnaik，L.M. 1994.遗传算法中交叉和变异概率的自适应。IEEEtransactions on System，Man and Cybernatics，vol. 24，no. 4，pp. 656-667。[10] 安德烈，J.，Siarry，P.，和Dongon，T. 2001.对标准遗传算法在连续优化问题中抗早熟收敛的一种改进。Advances in Engineering Software，vol. 32，no. 1，pp. 49-60岁。[11] Choi，L.C.，李，J.S.，Park，S.C. 2011.基于双层遗传算法的文档聚类。《计算机与信息科学通信》，第257卷，第257页。212-218[12] 姚X，刘毅，和Lin G. 1999.进化编程变得更快，IEEE Transactions on Evol。计算：第3卷，第82比102[13] Bandyopadhyay，S.，和Mauilk，U. 2001.非参数遗传聚类：有效性指标的比较，IEEE Trans.System Man Cybern.- Part C Applications and Reviews，vol. 31，pp. 120比125[14] 戴维斯，D.L.，和Bouldin，D. W. 1979.一个集群分离措施，IEEE Trans.模式分析。内部：Vol.1，pp. 224-227[15] Fragoudis，D.，Meretakis，D.，和Likothanalus，S. 2005.最佳术语：一种有效的文本分类特征选择算法。知恩图报。系统