搜索
分类号密级IUDC编号中国科学院博士学位研究生学位论文聚类/分类理论研究及其在文本挖掘中的应用卜东波指导教师李国杰院士研究员白硕研究员中国科学院计算技术研究所申请学位级别博士学科专业名称计算机组织与体系结构论文提交日期2000年10月论文答辩日期学位授予单位中国科学院计算技术研究所答辩委员会主席中国科学院计算技术研究所学位论文iii致谢我来到计算所求学已经六年了，如果说在这六年的时间里，学业上还有尺寸之进的话，我想这是和众多良师益友的帮助分不开的。李国杰院士是我的博士导师，“求真”“务实”，是李老师的科学理念，也是他向我们强调的昀多的话。李老师不仅注重向学生传授知识，而且更加注重激发学生的创造力和想象力。在每两周一次的讨论班上，李老师都要听取学生的工作进展和心得体会，向我们讲解如何做学问、如何养成良好的科学素养。因此我们的讨论班始终洋溢着一种良好的科研气氛，大家致力于真理的探讨，兼收并蓄，无门户之见，师生“燃烧着学习的热望”。我这六年里，都是在白硕老师的具体指导下工作和学习的。老师渊博的知识和富有魅力的大师风范，给我以很深的影响，也是我今后努力追求的目标和方向。总记得迸发新思路时老师眼睛中闪亮的光芒，总记得老师作讲演时迷人的风采，总记得和老师讨论问题时的那种心领神会、灵犀一点......这些都是我脑海永存的图象。前人说过，师生之间的默契恰似“如鱼在水”，其中的喜悦是外人所不能体会的。我遇良师，内心的喜悦也是如此啊！自动化所的王珏老师也给我以很大的帮助和教诲。在当今的社会里，王珏老师是为数不多的能够潜心做学问的学者之一，不为名利所惑，不为金钱所动，醉心于学术之中，始终追求那种“今夕明其道”的喜悦，这也是我们敬佩王珏老师的原因之一。王珏老师不仅学识渊博，而且对待我们这些后学晚辈也非常热情，经常给我们以鼓舞和激励。而对于常生高山仰止情绪的青年来说，又有什么能比热情的鼓励更催人奋进的呢？古人云：明师不可期，意思是说一个人遇到明师是可遇而不可求的事情。而我同时得到三位明师的教诲，实在是一件值得庆幸的事啊！NCIC-Motorola联合实验室的贺思敏博士是我的学长，也是我科研道路上的好友。对于学术上的很多问题，我们都有着相同或相近的看法。很多奇思妙想，都是从和他的谈话聊天中得到启发的，而这种自由自在、身心放松的闲聊，中国科学院计算技术研究所学位论文iv也许就是思维迸发灵感火花的昀佳时刻吧！感谢我的同学毛永捷和陈明宇，我们共同在计算所度过了六年的时光，心意相通，志趣相投，我为有这样的高手同学而感到自豪，他们是我昀好的朋友。感谢教育处的诸位老师，他们在这六年里给了我很多的帮助和照顾。感谢软件室的程学旗博士、郭莉、余志华、梁英、赵洁、邓晶博士以及已远赴加拿大的赵刚、李晔，想起他们就会想起我们共同构建“天罗信息检索平台”和“天联代理服务器系统”的时光，以及我们携手奋进、带动软件室从小到大逐步发展的艰辛历程。感谢易靖、许洪波、吴赣以及谢华刚、沙瀛、庞剑峰、杨志峰、张泽峰、朱茂盛等诸位师弟，还有黄园园、熊锦华、向泓等，感谢他们给我的帮助，以及他们带来的青春朝气。特别感谢我的父母，是他们哺育我成长，引导我树立远大的志向；感谢我的姐姐和小妹，是她们多年来辛勤工作支持我求学、勉励我进取，在我身上也寄托了她们的期望。以她们的聪明和勤奋，如果能有象我一样的好运气，相信一定会做的比我好，我希望这篇论文没有辜负她们多年来对我的关怀和期望。深情感谢我的妻子刘萍女士。是她陪伴我度过了昀艰难的日子，是她给本来单调的0/1世界带来那么多欢乐，在我灰心沮丧时是她鼓励我充满勇气，我要衷心地对她说声：谢谢！中国科学院计算技术研究所学位论文v摘要如何让Internet更好地为人类服务，是未来几年的一个真正挑战。一方面是人们对快速、准确而全面获取信息的渴望，而另一方面却是Internet上信息的纷繁芜杂，在这两者之间架设一座桥梁的确是一个巨大的挑战。基于人工智能的信息内容的自动聚类、分类和文摘，以及深层次的“知识检索”为迎接这个挑战提供了新的支撑技术。本文的目标就是在信息检索的背景下，从理论、算法和应用三个层次来讨论聚类和分类技术。本文首先全面分析了聚类和分类算法的关键技术，总结了在统计、机器学习和模式识别等领域的聚类/分类算法。本文随后从理论的层面来剖析聚类/分类算法。我们发现聚类过程实际上是在样本集上定义一种特定的等价关系，一个逐渐加细的等价关系序列和聚类谱系图是相对应的，不同的等价标准就导致了不同粒度的聚类结果。从信息粒度的角度看待聚类和分类，就能更清楚地看出它们之间的相通之处---聚类是在一个统一、均匀的粒度下进行计算，而分类是在非均匀粒度下进行计算。由此出发，还可以定义一种衡量特征空间与分类先验知识之间协调程度的定量度量，并发展了一种崭新的、基于粒度的分类算法，实验结果表明这种分类算法有很好的泛化能力。从拟物的角度出发，我们提出了一种针对实数变量样本的聚类算法。选定了特征空间之后，实际上就是把和领域相关的样本集转化成特征空间中的一群点。把这些点想象成物理世界中一群质点，它们除了坐标不同之外，其他方面没有任何的不同。这样，在由各质点形成的引力场中，从等势面的包含关系导出存在一种奇妙的拓扑结构，现今关于化学键的研究表明正是这种拓扑结构构成了化学键。从粒度的角度看，这种逐级包含的拓扑结构恰好又相应于一个逐渐加细的等价关系序列，使用这种拓扑结构进行聚类得到很好的效果。对于名义尺度变量的样本，我们则使用“规则+例外”和昀小描述复杂度的原理，提出了一种利用优化技术的聚类算法。名义尺度变量，比如：颜色取中国科学院计算技术研究所学位论文vi值为“红”、“绿”、“兰”等，无法象实数变量那样定义加、减、乘、除等运算，因此有必要发展新的算法。受RoughSets中“规则+例外”策略的启发，我们从描述复杂性的角度，把聚类问题转化成求样本集的昀小描述长度的优化问题，使用优化技术昀终得到一个较好的聚类方案。本文昀后介绍了在文本处理中如何实际应用聚类算法。相对于关系数据库中的样本来讲，文本实际上是一个无结构的字符流。要想进行聚类/分类操作，首要任务就是选取特征，定义文本在各个特征上的权重，从而在特征空间中表示文本。我们观察到文本和特征项的重要性之间存在着这样的一种对偶关系：●一个重要的文本就是包含许多重要词的文本；●一个重要的词就是经常出现在重要文本中的词；这种对偶关系实际上是对重要性的一个循环定义，无法各自独立地定义文本和词的重要性。我们使用迭代的策略来打破这种循环，并证明了这种迭代过程是收敛的。实际上，如此定义的特征项恰好反映了文本集中昀重要的概念，在Dumais的隐性语义检索中称为隐含概念。使用隐含概念空间以替代原始的词空间，得到了良好的实验结果。[关键词]聚类/分类信息粒度势场拓扑结构聚类谱系图描述复杂性昀小描述长度规则+例外主特征向量隐含概念中国科学院计算技术研究所学位论文viiABSTRACTIt’sarealchallengeforustomakeInterneteasiertouse.TheinformationinInternetisinshortoforganization,andfullofamassofpages,andontheotherside,peoplewanttoobtaintheinformationquicklyandaccurately.Thetechniqueofclustering,classificationandabstractingbasedonAI,andso-called“KnowledgeIndexing”technique,seemedasgoodapproachestosolvesuchproblems.Thisthesisaimstodiscusstheclustering/classificationtechniqueswiththebackgroundofinformationretrieval.Atfirst,wesummarizethekeytechniquesusedtodoclustering/classificationindifferentfieldssuchasstatistics,machinelearning,patternrecognition,etc.Weproposedanewclassificationalgorithmbasedontheoremof“informationgranularity”.Wefoundthatclusteringcorrespondswithaspecialequivalentrelationonthesampleset,andaseriesofequivalentrelationwithdifferentinformationgranularitycorrespondwithaclusteringdiagram.Fromtheviewofgranularity,thingismoreclearthatclusteringisaprocedureinauniformgranularity,whileclassificationindifferentgranularities.Afterselectingtermstorepresentthesample,wecantreatthesamplesaspointsinthetermspace,whichhasthesameweightanddifferentcoordinate.Let’sconsidertheenergyfieldconstructedbytheuniversalgravity,wecanobtainatopologystructurefromtherelationamongequilibriumcurvewithdifferentenergy.Andthetopologystructureiscorrespondingwithaspecialclusteringdiagram.Weproposedanewclusteringalgorithmbasedonthetopologystructure,whichshowsgoodperformanceintheexperiment.Forthesamplewithnominalvariables,itisdifficulttodefinethefitfuloperationsuchasadd,minus,multiplyanddivision.Fromtheviewofminimumdescriptionlengthandtheoremof“Rules+Exception”,weproposedaclustering中国科学院计算技术研究所学位论文viiialgorithmwhichtreattheclusteringproblemasanoptimizingonewhichaimstogettheminimumdescriptionofthesampleset.Theexperimentresultshowsthealgorithmisveryfastandalwaysfindstheshortestdescriptionofthesampleset.Weproposedanewalgorithmtocomputeoutanewconceptspaceinsteadoftheoriginaltermspaceintextclustering.Thereisabasiccycleindefiningtheimportanceoffilesandwords.Animportantfileisonecontainingmoreimportantwords,andanimportantissuchonethatoccursmorefrequentlyinimportantfiles.Weuseaniterationproceduretoobtainthewei