搜索
硕士学位论文支持文本聚类中参数自动设置技术的研究与实现导师：王大玲研究生：张猛二○○五年一月分类号密级UDC学位论文支持文本聚类中参数自动设置技术的研究与实现作者姓名张猛指导教师姓名王大玲教授博士东北大学信息科学与工程学院申请学位级别硕士学科类别工学专业名称计算机软件与理论论文提交日期2005年1月论文答辩日期2005年1月学位授予日期答辩委员会主席评阅人东北大学2005年1月AMasterThesisinComputerSoftwareandTheoryStudyandImplementationofAutomaticParameterSettingforDocumentClusteringByZhangMengSupervisor:ProfessorWangDalingNortheasternUniversityJanuary2005东北大学硕士学位论文独创性声明-I-独创性声明本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：日期：学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。（如作者和导师同意网上交流，请在下方签名；否则视为不同意。）学位论文作者签名：导师签名：签字日期：签字日期：东北大学硕士学位论文摘要-II-支持文本聚类中参数自动设置技术的研究与实现摘要随着数据库中和网络上文本资源、Web页面的激增，人们需要对大量的文本资源进行有效的组织，以有利于信息检索、模式发现、为用户提供推荐服务，以及为进一步的文本分类提供模式基础。于是，文本聚类技术应运而生。文本聚类，即将给定的文本集合划分为多个簇，从而达到簇内文本的主题相关性，簇间文本的主题无关性的目的。文本聚类中首先需对文本进行预处理，将非格式化的文本转化为格式化数据，再使用经典的聚类算法进行聚类。目前主要的文本聚类算法有基于划分的算法，典型的如K-Means和K-Medoids算法；基于层次的聚类算法，典型的如HAC（凝聚的层次聚类算法）；基于神经元网络的算法，如SOMs（自组织映射网络）；以及基于模型的聚类算法。上述算法各有其优缺点，其中大多数算法都需要用户输入关键参数、即阈值（如K-Means、K-Medoids、SOMs和模型方法），而无需参数输入的算法则时间效率过于低下（如HAC）。为解决文本聚类中的参数设置问题，本文提出并实现了支持典型文本聚类算法中参数自动设置的算法。首先，在特征选取方面，本文提出了“最大序列频繁词组”的概念，并通过挖掘最大序列频繁词组获取文本特征，以克服最常用的TFIDF方法忽略了词与词之间关系的缺点，使抽取的特征表示文本内容的准确程度大大提高。在使用K-Means进行文本聚类的研究中，针对K-Means算法在文本聚类中的缺点，本文提出了利用对多次取样聚类以确定参数K的方法，使得参数确定过程自动化；同时在K-Means方法中引入了衰减因子，再划分过程中动态地改变簇均值，以提高聚类质量。为了克服K-Means方法对孤立点敏感性的缺点，并进一步提高聚类的质量和时间效率，本文将基于密度的聚类算法应用于文本对象之上。在基于密度的文本聚类算法中，提出了一种利用曲线拟合自动确定参数的方法，利用自动参数确定技术，对簇进行收缩以得到细化簇。实验表明，参数自动设置技术使文本聚类过程更加自动化，同时提高了文本聚类的质量和效率，产生了很好的聚类结果。【关键字】：数据挖掘、文本聚类、特征选取、参数确定自动化东北大学硕士学位论文Abstract-III-AbstractWiththeincreasingofdocumentresourcesinmultimediadatabaseandWeb,processingdocumentsbyhandnolongermatchestheincreasingspeedandmeetspeople’srequirements.Whatpeopleneedisorganizingdocumentsinaneffectiveform,fortheconvenienceofinformationretrieve,patterndiscoveryandrecommendation,andalsoforthepurposeofpreparingforcategorizingthenewcomingdocuments.Andthencomesthedocumentclusteringtechniques.Documentclusteringistoseparatethedocumentsetintogroups,ineachgroupthedocumentsareofthesameorrelatedtopic.Thepurposeofdocumentclusteringistogeneratetheclustersinwhichdocumentsareofthemosttopic-related,andbetweenwhichdocumentsareofthemosttopic-unrelated.Theworkshavebeendonearetotransformtheunstructureddocumentsintothestructureddataobject,thenapplytheclassicalclusteringalgorithmstothem.Thedocumentclusteringalgorithmsmainlyusedarepartitioningmethod,suchasK-MeansandK-Medoids,hierarchicalmethodsuchasHierarchicalAgglomerativeClustering(HAC),neuralnetworkbasedmethodsuchasSelf-OrganizingMap(SOM),andmodel-basedclusteringalgorithm.Allofthesealgorithmshavetheirdisadvantages,someofthemneedtheinputparametersthataredifficulttosetbyusers,andsomeofthemhavetoolowtimeefficiency.Theconcept“MaximalSequentialFrequentPhrase”isproposedinthisdissertationfirst.ContrarytotheneglectoftherelationshipbetweentermsinTFIDFmethod,MSFPtakestherelationshipintoaccount,andguaranteestheordersbetweenterms.Thismethodcanobtainthebetterqualityintermselection,preparingfortheclusteringinnextstep.Thisdissertationstudiesthemethodstosettheinputparametersindocumentclusteringalgorithmautomatically.ForK-Meansalgorithm,amethodthatdeterminestheinputparameterKbymulti-samplingisproposed.AlsoscalarfactorcomingfromSOMisintroducedintotheclusteringprocess,alteringthemeanvalueineachclusterduringtheseparatingstepinK-Means.ThesetwoimprovementsinducetheK-Meansalgorithmrequiringnoinputparameterandgoodresultperformance.ToeliminatethesensitivitytooutliersinK-Meansandtoimprovetheclusteringefficiencyandperformancefurthermore,density-basedclusteringalgorithmisappliedtodocumentclusteringinthisdissertation.Forthispurpose,onenovelmethod东北大学硕士学位论文Abstract-IV-determiningtheparametersbymultinomialfitisproposed.Andwiththehelpofautomaticparameterssettingmethod,theclusteriscontractedstepbystep,generatingfineclusterfinally.Experimentsshowthattheautomaticparametersettingindocumentclusteringgeneratessatisfiedclusteringresultandimprovestheclusteringefficiency.【KeyWords】:DataMining,DocumentClustering,TermSelection,AutomaticParameterSetting东北大学硕士学位论文目录-V-目录独创性声明.......................................................................................................................I学位论文版权使用授权书...............................................................................................I摘要.........................................................................................................................IIABSTRACT..................................................................................................................III目录..........................................................................................................................V第一章前言....................................................................................................................11.1数据挖掘和文本挖掘........................................................................................11.2文本聚类及其应用.....