基于后缀树的海量短文本聚类技术研究

《基于后缀树的海量短文本聚类技术研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于后缀树的海量短文本聚类技术研究硕士学位论文基于后缀树的海量短文本聚类技术研究LARDGE-SCALESHORTTEXTCLUSTINGTECHNIQUESBASEDONSUFFIXTREE叶爽哈尔滨工业大学2011年12月国内图书分类号：TP391.1学校代码：10213国际图书分类号：621.3密级：公开工学硕士学位论文基于后缀树的海量短文本聚类技术研究硕士研究生：叶爽导师：叶允明教授申请学位：工学硕士学科：计算机科学与技术所在单位：深圳研究生院答辩日期：2011年12月授予学位单位：哈尔滨工业大学ClassifiedIndex:

2、TP391.1:621.3ThesisfortheMasterDegreeinEngineeringLARDGE-SCALESHORTTEXTCLUSTINGTECHNIQUESBASEDONSUFFIXTREECandidate：ShuangYeSupervisor：Prof.YunmingYeAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerScienceandTechnologyAffiliation：ShenzhenGraduateSchoolDateo

3、fDefence：December,2011Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工学硕士学位论文摘要随着互联网的高速发展，快餐文化越来越普及。互联网上大量的信息越来越多的以短文本的形式出现，搜索引擎的返回结果和微博等都是这种形式的信息的代表。尤其是微博，在最近的国内国外的重大事件中，微博作为最主要的人们的沟通方式之一，在互联网中占据了越来越重要的位置。传统的文本聚类算法在处理这类新的问题时往往出现处理速度慢，处理的效果不够好等问题，无法满足实际需

4、要。基于后缀树的聚类算法是区别于传统聚类算法的一种新的文本聚类算法。该算法在较小的时间复杂度内取得了较好的聚类效果。针对现在数据规模的不断扩大和对算法效果更好的实际需求，本文对基于后缀树的聚类算法进行了深入的分析，通过遍历后缀树的基本簇生成了文本集的极小子集。基于这个极小子集，可以对整个数据集的特性进行判别，从而在避免大规模计算的基础上得到对文本集的估计。将极小子集应用到传统的Single-Pass算法中，本文提出了新的文本聚类算法ST-SP*算法。该算法首先按照STC算法构建后缀树，并对生成的基本簇进行打分。然后基于这个打分对基本簇进

5、行排名，并筛选出排名靠前的满足一定条件的K个簇作为整个数据集的极小子集。利用这个子集，本文计算出了适合Single-Pass算法的阈值。进一步的基于这个阈值，采用Single-Pass算法可以很快的对数据集进行较好的聚类。实验表明，采用以上算法可以较准确的找到Single-Pass算法的阈值，克服Single-Pass算法阈值确定的难题。进一步分析发现，通过将极小子集作为Single-Pass算法的初始簇进行聚类，可以在线性复杂度内，取得更好的聚类效果。本文的后续部分讨论了极小子集的合理性问题，并提出将极小子集的思想应用到K-means

6、算法中，用于K值的确定或者初始簇的确定等。基于上述分析和实验，极小子集可以应用到的其它聚类算法中。基于以上的研究成果，本文设计并实现了一个包含ST-SP*算法的短文本聚类的实验原型系统，包括文本信息读取模块、预处理模块、算法模块和评估模块等模块，为进行相关的算法实验和研究提供了一个基础平台。关键词：后缀树；极小子集；短文本聚类-I-哈尔滨工业大学工学硕士学位论文AbstractWithrapidlydevelopmentoftheinternet,thecultureoffast-foodisspreadingaway.Thereisg

7、rowinginformationexperiencedinthewebwithshorttextform,suchasresultsreturnedbysearchenginesandmicroweblog.Especiallyforthemicroweblog,whichbecomesthemostsignificantcommunicateway,playsanimportantroleinrecentevent.Classicaltextclusteringalgorithmshavemettheproblemssuchasth

8、espeedofthealgorithmsareslowandtheresultsarenotsatisfiedtherequirement.Thealgorithmsbasedonsuffixtreeha