基于k-means的中文文本聚类算法的研究与实现

《基于k-means的中文文本聚类算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西北大学硕士学位论文基于k-means的中文文本聚类算法的研究与实现姓名：张睿申请学位级别：硕士专业：计算机软件与理论指导教师：刘晓霞20090601摘要在机器学习、数据挖掘等领域得到普遍应用的k-means算法由于具有时间复杂度低的优点，在文本聚类领域也得到了广泛的应用。论文对文本聚类的相关技术与算法进行研究，针对文本数据高维性和稀疏性的缺点，改进了文本聚类中的特征选择方法，以及与k-means相关的算法，并在此基础上设计并实现了一个中文文本聚类原型系统。主要工作有：1)聚类领域进行特征选择时由于缺乏类信息而难以选择出最具类区分能力的特征词。在文档频率，单

2、词贡献度两种特征选择方法的基础上，利用贪心算法对特征进行增量选择。实验表明改进的算法可以在保证聚类质量的前提下过滤更多的特征词。2)文本数据高维性和稀疏性的特点使得文本对象间的相似度不易度量，根据文本间的相似度为k-means算法选择的始聚类中心时可能不能很好的代表整个文本集。针对该缺点，对k．means算法中的初始化问题，提出一个改进的初始聚类中心选择方法。实验表明改进的方法选择到初始聚类中心比较分散且代表性好。3)为了提高聚类中簇的质量，通过引入共享最近邻相似度中邻居的概念，对bisectingk-means算法进行改进，实验结果表明该算法的聚类质量较原

3、算法有一定的提高。在以上研究工作的基础上，实现了基于k-means的中文文本聚类原型系统。通过实验对系统中的各个算法进行了评测和比较。关键词：文本聚类，k-means，bisectingk。means，共享最近邻AbstractAsawidelyusedalgorithminmachinelearninganddata-mining，k-meansisalsousedindocumentclusteringforitslowtimecomplexity．Thispapermainlyfocusonthehowtoimprovetheperformanceof

4、documentclusteringalgorithm．Basedonexistingresearch,improvedk-meansalgorithmsandnewfeatureselectionmethodareproposed．DesignandimplementaChinesedocumentclusteringSystemonthebasisoftheproposedalgorithms．Worksachievedinthispaperareasfollow：1)Itishardtoselectfeaturesforunsupervisedfeat

5、ureselectionmethodsusedinclusteringduetothelackofclasslabelinformation．Basedondocumentfrequencyandtermcontribution，greedyalgorithmisintroducedtoselectfeaturesincrementally．Experimentsshowthattheproposedmethodcanremovemorefeaturesthantraditionalmethodswithoutdegradingtheclusteringqu

6、ality．2)Inordertoimprovetheclusteringqualityofk—means，wellseparatedinitialcentroidsshouldbeselected．Initialcentroidsareaurallyhardtoselectduetothehighdimensionalityandsparsenessofdocumentdata．Anewmethodforselectinginitialcentroidsisproposed．Experimentshowthatthecentroidsselectedbyt

7、heproposedmethodarewellseparatedandwithhighrepresentative．3)Inordertoimproveclustersqualityofthebisectingk-means，neighborusedinsharednearestneighborisintroduced．Experimentsshowthattheimprovedalgorithmperformsbetterthantheoriginalone．Designandimplementadocumentclusteringsystemusingt

8、healgorithmmentionedabove．