基于遗传算法的文本聚类技术研究

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

1、V9‘8S：7工分类号UDC密级编号学位论文基于遗传算法的文本聚类技术研究DocumentCIusteringTechnoIogyBasedonGeneticAIgorithm乐兵指导教师姓名：王明文教授江西师范大学计算机信息工程学院申请学位级别：硕士专业名称：计算机软件与理论论文提交日期：2006年5月论文答辩日期：2006年5月29日学位授予单位和日期：江西师范大学2006年月曰答辩委员会主席：壶墨烂』彳篷菇笙援评阅人二00六年五月摘要文本聚类是信息检索(InfonTlationR晰ieval：IR)和数据挖掘(DataMini

2、ng：DM)等领域的一个重要研究方向。它是一种无监督的分类方法，根据样本自身的特点分成若干类，使得类内样本的相似性尽可能大、类间样本的相似性尽可能小。常用的系统聚类法聚类比较准确，但计算量很大。对样本数很多且维数很高的问题，这种方法的缺陷更为显现。受迭代方法思想的启发，人们提出了动态聚类法(也称逐步调整法)，从而减少了计算量，这种算法的执行与参数设置是否得当密切相关，往往需要对样本数据的物理意义进行必要的分析。在高维且数据量大的情况下，设置合理的参数尤为困难，只能通过多次实验比较来选定；另一方面，聚类的初始数据集和目标函数都是离散量

3、，存在许多局部极值点，而通常的动态聚类法没有判别劣值的机制，因此初始聚类中心和样本输入的次序对最终结果有着很大的影响。遗传算法(GenticAlgor曲m：GA)是一种模拟自然进化过程在全局搜索最优解的方法。本文利用遗传算法来解决对初始解敏感、易陷于局部最优的文本聚类问题，提出了基于遗传算法的动态文本聚类。我们采用二进制编码方式对聚类中心进行编码，以类内中的点与其类中心的欧氏距离作为适应度函数。通过遗传算法的选择、交叉、变异三个算子操作对类中心进行逐步迭代调整，直至适应度函数收敛，得到使聚类划分效果最好的聚类结果。在英文语料库Reu

4、ters．21578上的前10个常见类(ToplO)实验结果表明：1)该方法可以克服局部极值点的问题：2)聚类结果的评价指标纯度(Purity)也比较好。如何把本方法运用于中文语料库和海量数据集有待我们进一步研究。本文的创新之处主要有：1)在K一均值文本聚类算法的基础上，引入了遗传算法的思想；2)验证和分析了本文算法在英文数据集上的聚类性能，并把它与其它聚类算法的性能进行了比较。关键词：文本聚类；遗传算法；维数约简；潜在语义索引；纯度ABSTRACTDocumentcIusteringisoneofmostimportantrcse

5、archtopicininfomationreⅡieval(IR)anddatamilling(DM)．clustering，anunsupervisedcl船sifyingmethods，istheprocessofFoupingtogemersinlilar出唿intoanumberofclusters．Hi∞archicalclusteringm础odcallclusteraccur如1y，butitncedslotsofcalculation，especiallyⅥ，hen廿1enumber蛐dtlIedimensionof

6、samplesarenum盯es．Sti玎edbytlleite啪ceinthemamematics，d”枷icclusteringmethodisinvented，aIlditc锄deducecalculation．Theoperationoft11ed”amicclusteringmetllodissensitivet0t11esetofparameter，whichshould锄alysist11ephysicalm黜softhesample．Sowh朋tllenumber柚dtlledimensionofsamplesare

7、numeres，itistoodi伍cultto∞tpa豫meters．Tbchoicepar锄etersisonlydenpendedonlotsofexperiments，0nomerh锄d，theiIlitialco啦us锄dthetargetfunctionaresepa∞ted，锄d也e佗mayhavesomeexn弓m啪s．H删vever，theusedal剃也mhasnotamechanismtoaVoidmewor∞rc蛐lt．111usttleclusteringresults黜sens“ivetoinitialc

8、lusteringcentersandtheorderofiIlputsalllples．G朗eticalgorimms，motiV戤edbynattlmleVoIution，makeuseofev01utionary叩erators