余弦度量和适应度函数改进的聚类方法.pdf

《余弦度量和适应度函数改进的聚类方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第42卷第4期电子科技大学学报Vol.42No.42013年7月JournalofUniversityofElectronicScienceandTechnologyofChinaJul.2013余弦度量和适应度函数改进的聚类方法11112施侃晟，刘海涛，白英彩，宋文涛，洪亮亮(1.上海交通大学电子与电气工程系上海徐汇区200030;2.中国孵化中心杭州310053)【摘要】K-均值算法因其简单和高效性，在文本聚类中占有重要地位。针对传统的K-均值算法对初始点敏感、易陷入局部最优的问题，结合遗传算法已经成为一种趋势。在充分发挥K-均值

2、算法的高效性的同时，该文利用遗传算法的全局自适应优化特点克服了对初始点敏感的问题。同时，以余弦度量评价对象间的相似性并以此构造新的遗传算法适应度函数、收敛准则以及遗传算法种群更新方式，提高了K-均值和遗传算法这种结合方式的聚类精度，并增强了该结合算法的稳定性。关键词遗传算法;适应度函数;K-均值算法;相似性度量;文本聚类中图分类号TP18文献标志码Adoi:10.3969/j.issn.1001-0548.2013.04.017TextClusteringMethodwithImprovedFitnessFunctionandCosi

3、neSimilarityMeasure11112SHIKan-sheng,LIUHai-tao,BAIYin-cai,SONGWen-tao,andHONGLiang-liang(1.CollegeofElectronicandElectricEngineering,ShanghaiJiaotongUniversityXuhuiShanghai200030;2.ChinaIncubatingCenterHangzhou310053)AbstractThetraditionalK-meansalgorithmiswidelyusedbe

4、causeofitssimplicityandefficiency.However,itissensitivetotheinitialpointandeasytofallintolocaloptimum.Inthispaper,weusecosinemeasuretoevaluatethesimilaritybetweenobjectsandconstructanewfitnessfunctionofgeneticalgorithmandthenewconvergencecriterionforK-meansalgorithm.Exp

5、erimentalresultsshowthatthenewmethodenhancestheclusteringaccuracyandstabilityforthecombinationofK-meansandgeneticalgorithm.Keywordsgeneticalgorithm;fitnessfunction;K-meansalgorithm;similaritymeasurement;textclustering文本聚类作为一种无监督的机器学习方法，由并以此构造遗传算法的适应度函数、收敛准则来更于不需要训练过程及预先

6、对文档手工标注类别，因新遗传算法种群，提高了K-均值与遗传算法这种结此具有一定的灵活性，已成为对中文文本信息进行合方式的聚类精度和稳定性。有效地组织、摘要和导航的重要手段，为越来越多1改进的文本聚类算法[1]的研究人员所关注。典型的文本聚类方法有多种，其中K-均值算法因其简单和高效性，在文本聚类中针对K-均值与遗传算法相结合的趋势，给出新占有重要地位[2]，但它对聚类初始中心点的选取比的提高该种结合方式的聚类精度和稳定性的算法设较敏感且易陷入局部最优，文献[3]提出了用语义信计和实际操作步骤。息改善该问题的方法。目前，有研究者将遗传算

7、法1.1相似性度量设计和K-means算法相结合克服初始点敏感问题[4-9]。遗聚类过程中，两个对象间的相似性计算是非常传算法是一种通过模拟自然进化过程搜索最优解的重要的，相似性度量准则的优劣很大程度上影响了方法，它只需检测少量结构就可反映搜索空间较大聚类的效果。在向量空间模型下，可以借助向量之的区域，便于实时处理，同时具有较强的稳健性可间的某种距离表示文本间的相似度。目前研究者已避免陷入局部最优。所以，K-均值与遗传算法的结提出了许多方法来评价同一个特征空间中的两个对合是一种趋势。象间的距离，然而并非所有的度量在各种情况下都本文进一

8、步以余弦度量评价对象间的相似性，是适用的，如对象的数据类型是分类的和连续的情收稿日期：2011−08−29;修回日期：2012−04−18基金项目：国家自然科学基金(61073150)作者简介：施侃晟(1966−)，男，