（计算机应用技术专业论文）基于语义相似度的论文文本聚类算法研究.pdf

大连理工大学硕士学位论文 摘要 面对网络上日益增多的论文，如何快速有效地检索出符合使用者需要的论文成为论 文检索所要面临的一个难题。目前常用的方法是基于关键词匹配的方法，该方法查询速 度快，但是没有解决同义词、多义词及词语概念上下位等问题，检索效果不尽如人意。 如果利用文本聚类技术，对检索结果进行进一步的处理，把检索结果集合按照其相关主 题进行划分，生成不同主题的簇，同时删除冗余的项，为用户提供一个清晰的导航。这 将大大的有利于用户发现自己所需的相关论文，提高论文检索的质量。 本文改进了一种基于语义相似度的文本聚类算法( t c u s s 算法) 并将其应用于论 文文本聚类。改进后的算法提出了一种适合论文文本的特征选择方法和聚簇描述方法， 文本数学表示方法和聚类算法通过对t c u s s 算法针对论文文本进行一定改进得到。 在特征选择和聚簇描述中，算法利用论文关键词能较好的表达文章主题这一特点， 结合w o r d n e t 语义词典，围绕关键词所表达的概念进行特征提取，还利用用词典中的同 义词集和计算特征词间的语义相似度分别解决了同义词与多义词问题；在论文文本数学 表示方面，本文采用概念列表表示文本；在词语相似度计算中，用关键词所在概念节点 代替关键词，计算概念节点在w o r d n e t 中的语义距离，根据语义距离计算词语相似度； 文本相似度通过计算特征词间的相似度获得；采用了一种基于语义相似度的文本聚类算 法，该算法结合了图的理论进行聚类分析，避免了算法对聚簇形状的限制；用特征词在 整个聚簇中出现的词频和其在w o r d n e t 中包含的信息量来衡量特征词权重，选取部分权 重大的特征词进行聚簇描述。最后为了检验算法的有效性，设计了一个基于语义相似度 的论文文本聚类系统，并通过自建论文文本数据集上与t c u s s 算法和k m e a n s 算法的 对比实验证明，该算法对于论文文本聚类具有较高的分类正确率，具备一定的实用性。 关键词：文本聚类；语义相似度；概念列表；论文检索 大连理工大学硕士学位论文 r e s e a r c ho nt h e s i st e x tc l u s t e r i n gb a s e do ns e m a n t i cs i m i l a r i t y a b s t r a c t f a c ew i t ht h eg r o w i n gn u m b e ro ft h e s e so nn e t w o r k s ，h o wt oq u i c k l ya n de f f i c i e n t l y r e t r i e v et h et h e s e st h a tu s e r sn e e di sad i f f i c u l tp r o b l e mf o rt h e s i sr e t r i e v a l a tp r e s e n tt h e c o m m o n l yu s e dm e t h o di sb a s e do nt h ek e y w o r d sm a t c h , t h i sm e t h o di n q u i r ys p e e di sq u i c l b u th a sn o ts o l v e dt h ep r o b l e mw h i c hb e g o tb ys y n o n y m ，p o l y s e m ya n dc o n c e p tu p p e ro rl o w e r p o s i t i o n , s ot h er e t r i e v a le f f e c ti sn o te n t i r e l ya sd e s i r e d i fu s i n gt h et e x tc l u s t e rt of u r t h e r p r o c e s s i n gt h er e t r i e v a lr e s u l t ，d i v i s i o nt h er e t r i e v a lr e s u l ta c c o r d i n gt oi t sr e l a t e ds u b j e c t ， p r o d u c e st h ed i f f e r e n tc l u s t e ra c c o r d i n gt os u b j e c t ，d e l e t et h er e d u n d a n ti t e m s ，p r o v i d e sac l e a r g u i d a n c ef o rt h eu s e r , i tw i l lb eg r e a t l yb e n e f i c i a lt ot h eu s e r st of i n dt h er e l e v a n tt h e s i s st h e y n e e d ，s oi tc a ni m p r o v et h eq u a l i t yo fr e l r i e v e dt h e s i s i nt h i st h e s i sw ei m p r o v e dat h e s i st e x tc l u s t e ra l g o r i t h m t h a tb a s e do nt h es e m a n t i c s i m i l a r i t y ( t c u s sa l g o r i t h m ) a n da p p l i e di tt oc l u s t e r i n gt h e s i st e x t t h ei m p r o v e da l g o r i t h m u s e st h ef e a t u r es e l e c t i o nm e t h o d sa n dt h em e t h o df o rd e s c r i p t i o no fc l u s t e r o b t a i nt h em e t h o d o ft e x tm a t h e m a t i c se x p r e s s i o na n dt h ec l u s t e ra l g o r i t h mb yi m p r o v i n gt c u s s a l g o r i t h mi n v i e wo ft h et e x to ft h e s i s i nf e a t u r es e l e c t i o n ，b e c a u s et h ek e y w o r d sc a nn o te x p r e s st h et h e m eo ft h et e x ta r t i c l e b e t t e r , s ow eu n i f i e st h ew o r d n e ts e m a n t i c sd i c t i o n a r y , a c c o r d i n gt ot h ec o n c e p tt h a te x p r e s s e d b y k e y w o r d sf i n i s h e dt h ef e a t u r ee x t r a c t i o n u s i n gt h es y n o n y mc o l l e c t i o ni nw o r d n e ta n dt h e c o m p a r i o nw i t ht h es i m i l a r i t yb e t w e e nf e a t u r ew o r d ss o l v e dt h es y n o n y ma n dt h ep o l y s e m a n t q u e s t i o n ；i nt h et h er e p r e s e n t a t i o no ft e x t ，w er e p r e s e n t st e x tw i t hc o n c e p tl i s t i nt e r m so f s i m i l a r i t yc a l c u l a t i o n ，w eu s et h es y n s e tw h i c hi n c l u d et h ek e y w o r d si n s t e a do ft h ek e y - w o r d s ， c a l c u l a t et h es e m a n t i cd i s t a n c eb e t w e e ns y n s e t si nw o r d n e t ，a n dt h e nw ec a nc a l c u l a t e s i m i l a r i t yo fw o r d si na c c o r d a n c ew i t ht h es e m a n t i cd i s t a n c eb e t w e e ns y n s e t s a c c o r d i n gt o c a l c u l a t e ds i m i l a r i t yb e t w e e nf e a t u r ew o r d sw eg e tt e x ts i m i l a r i t y ；t h e nw eu s e dat e x tc l u s t e r a l g o r i t h mt h a tb a s e do nt h es e m a n t i cs i m i l a r i t y , t h ea l g o r i t h mc l u s t e r st e x t sb a s e do ng r a p h a n a l y s i st ob ei n d e p e n d e n tw i t ht h es h a p eo f c l u s t e r s u s et h ef r e q u e n c yo f f e a t u r ew o r d sa p p e a r i nc l u s t e ra n dt h ei n f o r m a t i o nf e a t u r ew o r d sc o n t a i n e di nw o r d n e tt oc a l c u l a t et h ew e i g h to f f e a t u r ew o r d s ，a n ds e l e c tt h er i g h tp a r to ft h ef e a t u r ew o r d st od e s c r i b e f i n a l l yw ed e s i g n e da s y s t e mb a s e do nt h es e m a n t i cs i m i l a r i t yt h e s i st e x tc l u s t e rt oe x a m i n et h ea l g o r i t h mt h ev a l i d i t y , c o n t r a s tt h ee f f e c t st h ea l g o r i t h mi nt h i st h e s i s ，t c u s sa l g o r i t h ma n dk m e a n sa l g o r i t h ma c t o nas e l f - b u i l tv e r s i o no fad a t as e to ft h e s i s ，r e s u l t ss h o wt h i sa l g o r i t h mi m p r o v e dt h et e x t c l u s t e r sc o r r e c t l y , h a sc e r t a i nu s a b i l i t y 基于语义相似度的论文文本聚类算法研究 k e yw o r d s ：t e x tc l u s t e r i n g ；s e m a n t i cs i m i l a r i t y ；c o n c e p tl i s t ；t h e s e sr e t r i e v a l i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：蒸蕴堡墨塑型鑫丝i 丝兰簦鳘兰簦堡塑迄 作者签名：j 耻乙一日期：耳年土月业日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕士学位论文 1 绪论 1 1 研究背景和意义 在科技飞速进步和教育全面发展的今天，科技论文的数量日益增长而且传播知识 的作用越发重要，成为交流和推广知识的一种重要方式。随着计算机的广泛应用和互 联网的全球化使得通过网络共享论文资源成为主要的方式，网络技术与搜索引擎的发 展已经成了科技工作者方便获取论文资料的重要手段。 论文作为一种较为规范的文本数据，有其固定的书写格式和相对稳定的结构，这对 聚类中的文本分析有一定的帮助。但面对如今w e b 上数量庞大的论文资料，传统的论文 检索大部分都是基于关键词匹配进行检索，由于作为最能体现论文主题的关键词往往受 到数量限制，不能完整的体现论文的主题，而且根据作者思考方式和写作习惯，关键词 也同样存在使论文外延过大的问题，再加之一词多义以及查询词概念上下位的问题，导 致简单的采用关键词匹配使用户往往无法从大量论文资源中快速找到符合要求的论文。 如果利用文本聚类技术，对检索结果进行进一步的处理【l 】，把检索结果集合按照其相关 主题进行划分，生成不同主题的簇，同时删除冗余的镜像页面，为用户提供一个清晰的 导航。这将大大的有利于用户发现自己所需的相关论文，提高论文检索的质量。 1 2 研究现状 聚类算法的研究早在2 0 世纪6 0 年代就开始了，但是受当时各方面条件的限制并没 有太大的发展，直到2 0 世纪9 0 年代才引起了广泛的关注，并取得非常重大的突破，一 大批新的聚类算法被提出，目前仍旧是一个非常热点的问题。但这些算法中大多数不是 针对文本数据提出的，只有少部分能应用于文本聚类。大体上，文本聚类算法大致分为 划分聚类算法、层次聚类算法、基于密度的聚类算法、基于模型的聚类算法和基于网格 的聚类算法、s t c 算法以及其他算法等几大类。目前，应用最多的聚类算法是k m e a l l s 算法、s o m 聚类算法及其改进算法。当然，层次聚类算法和基于密度的聚类方法仍然 应用于聚类的各个领域中。 ( 1 ) 划分聚类方法。 划分的方法( p a r t i t i o n i n g m e t h o d ) 是根据设定的划分数目k ，通过一定的准则将聚类对 象进行划分，使得满足“类内高相似，类间低相似 的聚类原则。通常是基于对象之间 的距离相近，或者相似度较高来划分。其中最常见划分方法是k m e a n s 算法和k m e d o i d s 算法。这两种方法通过多次的迭代，使得对象在划分过程中不断的在聚簇之间移动调整， 以求达到更高的类内相似性。两者的区别在于代表一个聚簇的质心计算方法不同。 基于语义相似度的论文文本聚类算法研究 k - m e a n s 算法常常在文本聚类中使用。这类算法虽然运行时间快，但是存在一些缺点如 受初始簇中心影响较大，要预先指定聚类数k ，容易受孤立点的影响等。 ( 2 ) 层次聚类方法 层次聚类法是对给定数据对象集进行层次的分解。根据层次的分解如何形成，层次 法可以分为凝聚的和分裂的。凝聚的方法也称为自底向上的方法，开始将每个对象作为 一个单独的组，然后相继地合并相近的对象或组，直到所有的组合并为一个，或者达到 一个终止条件。分裂的方法也称为自顶向下的方法，一开始将所有的对象置于一个簇中， 在迭代的每一步中，一个簇分裂为更小的簇，直到最终每个对象在单独的一个簇中或者 达到一个终止条件。代表性的算法有b i r c h ，c u r e ，c h a m e l e o n 等。 ( 3 ) 基于密度的聚类算法 基于密度的方法认为，类别即是向任意方向按相同密度( 对象或者数据点的数口) 扩 张的连通区域，只要临近区域的密度超过某个闭值，就继续聚类。因此基于密度的聚类 算法可以发现任意形状的类别，同时此算法对噪声有自然的抵制作用。这种算法主要需 要考虑数据空间的密度，连通性与边界区。d b s c a n ，o p t i c s 是其中两种有代表性的 方法。 ( 4 ) 基于模型的聚类算法 基于模型的聚类算法试图优化给定的数据和某些数学模型之间的适应性。这样的方 法经常是基于这样的假设：为每一个簇假定了一个模型，然后寻找数据与给定模型的最 佳拟合。这类算法主要分为两类：统计学方法和神经网络方法，著名的自组织特征映射 ( s e l f - o r g a n i z i n gf e a t u r em a p ，s o m ) 就是一种利用了人工神经网络技术的聚类方法【2 1 。 ( 5 ) 基于网格的聚类算法 基于网格聚类方法是把数据对象空间量化为有限数目的单元，以构成一个网络结 构。所有聚类操作都在这个网络结构( 即量化的空间) 上进行。这种方法的主要特点就是 处理时间与数据对象数目无关，但与每维空间所划分的单元数目相关，因此基于网格聚 类方法的处理时间很短。典型算法有s t l n g ，c l i q u e 等。 ( 6 ) 后缀树( s t c ) 聚类算法 后缀树聚类算法：后缀树聚类算法是一种直观的文本聚类算法，它将文本聚类为一组 的依据是文本含有共同的短语。实际上是将文本看成词的序列，充分利用了词与词之间 的距离信息，在寻找文本共同的短语的过程中使用了后缀树这种数据结构。o r e nz a m i r 首先提出了后缀树聚类算法，并且将这种技术运用到搜索结果的可视化中，取得了很好 的效果，具体的算法过程可以参考文献【3 】。搜索引擎c a r r o t 2 中的部分工作也利用了s t c 大连理工大学硕士学位论文 算法实现w e b 搜索结果的聚类，并且指出了s t c 算法的若干不足，但没有对聚类结果 的质量进行评价 4 】。 除了上述常用的聚类分析算法外，在最近的文本聚类研究中，一个比较重要的趋势 是，人们希望脱离原先基于语法层次的相似性聚类，得到能够理解文本内容的聚类方法。 基于概念的文本聚类，以及最近基于语义、语用层次所做的研究都是这一思想的体现。 这种方法能够比较有效地避免基于向量空间模型的算法所带来的常见问题，但是对语义 词典或语义网络的依赖度比较大，而且国内还处在研究阶段，没有很成熟的算法。但是 随着语义词典和语义网络的不断完善和更新，越来越多的人正在投入到这类聚类方法的 研究中。 1 3 存在问题 随着网络上科技论文数量的剧增，越来越多的人通过网络检索需要的论文来获取相 关知识。目前普遍采用的方法就是关键词匹配的方法，这种方法忽略了文章关键词由于 数量有限表现文章主题不完整的问题，而且关键词也存在同义词、多义词以及查询词概 念上下位的问题，导致用户往往无法从大量论文资源中快速找到符合要求的论文，造成 了检索质量不高。 虽然采用文本聚类技术能够有效地提高论文检索的效果，但是目前论文检索中的文 本聚类大都采用向量空间模型来进行文本的数学描述。这种方法引发了一个非常严重的 问题，那就是高维稀疏问题。因为在通常情况下，即使是一个中等规模的文本数据集也 具有几万个单词，这种维度对很多学习算法来说实在是太高了，但是每一个文本通常只 包含所有单词中的极小部分单词，这也就是说，一个文本向量在文本空间中绝大部分的 维度上都是0 ，这使得文本空间异常稀疏，其稀疏程度通常高达9 5 9 9 t 5 , 6 】。高维稀疏 给文本聚类造成了相当大的影响，不仅使得文本聚类具有相当高的时间复杂度，而且会 极大降低文本聚类和文本分类的性斛7 8 】。 除了高维稀疏之外，文本数据还有近义词和多义词两个特有的语言现象。近义词现 象指的是可以用多种不同的方式来描述同一个主题或者内容f 9 】。据f u m a s 等【lo 】的统计发 现，两个人在使用相同的词语来表达同一件事物的概率不超过2 0 ，这个数据说明了近 义词现象的普遍性。然而近义词的存在极大地降低了信息检索的性能，因为在精确匹配 的方式下，使用“篮球”是无法找到“n b a ”、“c b a 等内容的。多义词现象指的是 同一个单词具有多重不同的含义】。比如英文单词”c h i n a ”，它既指“中国”，又有“瓷 器 的意思。多义词最大的损害在于极大降低信息检索的精确度，因为检索“鳄鱼”所 返回的结果中可能既包含介绍鳄鱼这种动物的文章，又包含鳄鱼品牌的服装服饰等文 基于语义相似度的论文文本聚类算法研究 章。近义词现象和多义词现象的存在极大地千扰了文本聚类和文本分类的准确度，使得 文本分类和文木聚类变得非常困难【1 2 1 。 综上所述，高维稀疏、近义词和多义词三个文本数据所特有的问题不仅使得文本聚 类和文本分类具有相当高的时问复杂度，而且极大于扰了聚类和分类学习算法的准确 性，使文本分类和文本聚类的性能急剧下降。 1 4 本文主要工作 本文提出了一种基于语义相似度的论文文本聚类算法。该算法采用语义相似度作为 聚类的依据，避免了采用向量空间模型所带来的高维稀疏问题。同时提出了一种了适合 论文文本聚类的特征提取方法和聚簇描述方法，并在特征提取过程中解决了常见的多义 词和同义词问题；在文本数学表示、词语相似度计算和文本聚类三个步骤中，本文借鉴 了t c u s s 算法【1 3 】，将其做适当调整后应用于论文文本聚类。通过实验对比，本文聚类 方法在论文文本数据集上的聚类效果好予t c u s s 算法和k - m e a n s 算法。本文主要工作 如下： ( 1 ) 简要叙述了文本聚类的发展概况，并阐述了课题的背景、目的、意义及国内外 的研究现状。 ( 2 ) 简要介绍了文本聚类的相关概念，分析了几种常见的文本聚类分析方法及其优 缺点。 ( 3 ) 详细阐述了本文所采用的聚类方法中的特征提取的方法和聚簇描述方法，并将 本文对t c u s s 算法针对论文文本所做的调整进行了细致的说明。 ( 4 ) 实现了本文的聚类算法，并在自建的论文文本数据集上与t c u s s 算法和 k - m e a n s 算法进行了结果比较，验证了本文方法的有效性和其对论文文本优化的效果。 ( 5 ) 对本论文的主要研究工作给出了一个简要的总结，提出进一步的研究方向。 大连理工大学硕士学位论文 2 文本聚类概述 2 1文本聚类定义 文本聚类( t e x t c l u s t e r i n g ) 是对一些无结构或半结构化的文本对象进行自动分类的过 程。主要包括文本数据的预处理、文本相似度度量、文本聚类算法、结果可视化描述等 几方面的工作。与文本分类( t e x t c l a s s i f i c a t i o n ) 不同，文本聚类作为聚类分析技术的一种， 并不需要利用己知数据进行训练学习的过程。 文本聚类技术在文档的自动整理和组织中应用广泛，典型的有如w e b 页面自动归 类，新闻报道自动分类，电子邮件自动分组等。此外，聚类技术在信息检索中也得到应 用，例如对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信剧1 4 1 ；而 n e w s b l a s t e r 1 5 】贝0 是一个新闻报道的自动摘要系统，利用聚类技术对每天的重要新闻进行 聚类，并生成相应的摘要。 2 2 相关概念介绍 2 2 1文本的特征向量 文本的特征向量是通过文档的预处理( 文本分词和文档特征向量的提取) ，将文档用 一维向量表示，这个一维向量即文档的特征向且【1 6 1 。 其形式如下： ( 特征分量i ，特征分量2 ，特征分量3 ，特征分量n ) 2 2 2 文本间的距离 为了定义文本之间的相近或者相似程度，需要定义一些划分类别的计量指标。常用 的统计指标有距离和相似系数。“距离属于相异性测度指标，“相似系数”属于相似 性测度指标。距离和相似系数成反比，如公式( 2 1 ) 。 s i m ( i ，_ ，) = 1 ( 1 + d ) ( 2 1 ) 对于有n 个特征属性的文档集合来说，m 个文档可以看作n 维空间中的m 个点。 为此，可以用点之间的距离来度量文档之间的距离。 最常见的距离度量方法是欧几里距剐17 1 ，其定义为公式( 2 2 ) 。 d = ( m 1 一1 ) 2 + ( 2 一2 ) 2 + + ( 一y 加) 2 ( 2 2 ) 其中，第i 篇文档的特征向量和第j 篇文档的特征向量分别用( w ，w f ：) 和 ( w l ，w ，2 w 加) 表示。其中d 表示文档i 和文档j 之间的距离。 基于语义相似度的论文文本聚类算法研究 2 2 3 权值表示 ( 1 ) 布尔权重( b o o l e a nw e i g h t i n g ) 布尔权重方法是最简单的特征表示方法，如果特征向量的第i 个分量在本篇文档 中出现，则其权重为1 ，否则为0 ，如公式( 2 3 ) 。 r 1 2 ： 其中 当厶 o 时a k 。1 否则口雎20 。 ( 2 3 ) ( 2 ) 词频权重( w o r df r e q u e n c yw e i g h t i n g ) 词频权重【1 8 】也是种非常简单的特征表示方法，它只是简单地将特征i 在文档k 中 出现概率厶作为其特征值，如公式( 2 4 ) 所示。 口膳= 厶( 2 4 ) ( 3 ) t f i d f 权重( t f i d fw e i g h t i n g ) 前两种方法并没有计算特征i 在整个训练集合中出现的概率，一个非常有名的特征 权重表示方法考虑了这一点，它就是t f i d f 方法，如公式( 2 5 ) 所示。 a 髓= 厶宰l o g ( = ) ( 2 5 ) 2 2 4 文本之间的相似系数 对于有n 个特征属性的文档集合来说，m 个文档可以看作n 维空间中的m 个向量。 为此，在聚类时可以用相似系数来度量它们之间的相近程度，用s i m ( i ，j ) 表示第i 个 向量与第j 个向量之间的相似系数，则有以下性质： v f ，_ ，i s i m ( i ，刮1 即绝对值总不大于1 ； v f ，j fs i m ( i ，j ) = s i m ( j ，i ) 即满足对称性。 几种常见的文本间相适度系数： ( 1 ) 余弦系数( c o s i n ec o e f f i c i e n t ) ，如公式( 2 6 ) 。 咖( f ，) ：下鱼些竺( 2 6 ) ：。w i k2 ：。2 ( 2 ) 重叠系数( o v e r l a pc o e f f i c i e n t ) ，如公式( 2 7 ) 。 删，舻面酉- _ 面, w i k w j k ( 2 7 ) ( 3 ) 雅可比系数( j a c c a r dc o e f f i c i e n t ) ，如公式( 2 8 ) 。 大连理工大学硕士学位论文 j 砌( 力2 2 ：；iw a + 2 ：豳= lw k 塑- - e ：= lw l kw k ( 2 - 8 ) 2 2 5 文本类之间的距离 设n 和破是两个文档集合，具有n 个特征属性，即n 个索引词。 常见的度量两个文本类之间距离有如下几种方法： ( 1 ) 最短距离：定义为两类中最近的两个文档间的距离。如公式( 2 9 ) 所示。 j ( d n ，3 2 ) = 熹：螈d ，) ( 2 9 ) ( 2 ) 最长距离：定义为两类中最不相近的两个文档间的距离。如公式( 2 1 0 ) 所示。 墨( d l ，d 2 ) = m a x s ( d l ，d 2 ) i d l d 1 ，d 2 d 2 j ( 2 1 0 ) ( 3 ) 重心距离：定义为两类重心之间的距离。 类的重心是指类中所有文档的平均向量。设d g 为d 的重心，即d g2 磊1 己同nd ，； 则s ( d l ，d ：) = s ( d 1 g ，d 2 g ) ( 4 ) 类平均距离，如公式( 2 1 1 ) 所示。 j ( d i 圳d 2 去：蝙d 从咖d id ，d 2 ) ( 2 11 ) 2 2 6 数据标准化 选用的度量单位将直接影响聚类分析的结果，如果将高度由“米 改成“厘米一， 重量由“克”改成“千克”，就有可能产生不同的聚类结果；为了避免对度量单位的依 赖，数据应当进行标准化，有多种方法，在此介绍三种方法：最4 , 最大规范化，z - - s c o r e 规范化，按小数定标规范化。 ( 1 ) 最小最大规范化：对原始数据进行线型变化，设m i n x 和m i n y 分布为变量x 的 最小和最大值。则最d , 最大规范化通过公式( 2 1 2 ) 计算。 ：粤(maxx,一，)+ewminw n e wn e wm l nn e w m l n ， ( 2 1 2 )= 0 1 j +，i z 1 z j m a x j m l n j 将x 的值w 映射到区间n e w m a x 。，n e w m i n ，】中的。 ( 2 ) z - - s c o r e 规范化：变量x 的值基于x 的平均值和标准差规范化。 x 的值w 被规范化，由式计算：w t ：w - - a 其中，a 和仃分别为x 的平均值和标 仃 准差。 基于语义相似度的论文文本聚类算法研究 ( 3 ) 按小数定标规范化：通过移动x 取值的小数位置进行规范化。 小数的移动位置依赖于x 取值的最大数的绝对值。x 的值w 被规范化为w ，由以下 公式= 丙w 进行计算，其中j 是使得朋缸( 1w ，i ) l 的最小整数。 l u 。 如i - 4 = 9 8 5 ，则j - 3 ，此时= 0 9 8 5 。 2 2 7 文本的表示 人在阅读文章后，根据自身的理解能力和已掌握的知识可以对文章内容的产生模糊 认识。计算机并不具有人类这样的智能，它并不能轻易地“读懂 文章。因此在文本自 动分类中遇到的基本问题是如何将文本表示成计算机可以“理解的方式，从而在这个 基础上进行分类。文本分类的第一步是转化文档( 通常是字符串) 为满足学习算法或者分 类任务输入的表达方式。最常用的文本表示法就是向量空间表示法，这种方法非常简单， 但是引发了高维稀疏的问题。因为本文采用语义相似度作为文本间相似度的度量，因此 为了避免因使用向量空间模型而带来的高维稀疏问题，本文采用适合基于语义相似度的 文本聚类算法的概念列表表示法。为了保证一个文本的概念列表能够很好地反映文本的 主题，本文指出了特征词提取部分针对论文文本所做的改进。 2 3 几种常见的文本聚类算法 目前存在大量的聚类算法。算法的选择取决于文档集合的类型，聚类的目的和应用。 如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现数据 可能揭示的结果。 主要的聚类算法可以分为如下几类：划分的方法【1 9 】，其典型代表算法为k - m e a n s 算 法【2 0 之4 】；基于密度的方法【2 5 2 6 ，其典型代表算法为d b s c a n t 2 7 。o 】；基于模型的方法【3 1 1 ， 典型代表算法为s o m 神经网络【3 2 。3 7 】；层次方法【3 8 ，3 9 】；基于网格的方法【4 0 4 1 1 。下面简要 介绍各类方法，具有代表算法的方法以代表算法为例进行介绍。 2 3 1 划分的方法( k - - m e a n s 算法) ( 1 ) 工作原理 首先随机地选取k 个对象，每个对象初始地代表了一个簇的平均值或中心。对象剩 余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇 的平均值( e l i 重心) 。这个过程不断重复，直到准则函数收敛。 ( 2 ) 算法描述 一8 一 大连理工大学硕士学位论文 任意选择k 个对象作为初始的簇中心； r e p e a t 根据簇中对象的平均值，将每个对象( 重新) 赋给最类似的簇； 更新簇的平均值，即计算每个簇中心对象的平均值； u n t i l 不再发生变化。 ( 3 ) 该算法的适用数据类型，以及时空复杂度 这个算法尝试找出使平方误差最小的k 个划分。当结果簇是密集的，而且簇与簇之 间区别明显时，它的效果较好。对于处理大数据集，该算法是相对高效的，因为它时间 复杂度是d ( ，z 幻) ，其中，n 是所有对象的数目，k 是簇的数目，t 是迭代的次数。 但是k m e a n s 算法只有在簇的平均值被定义的情况下才能使用。这可能不适用于某 些应用，比如设计有分类属性的数据。 ( 4 ) 该算法的优缺点 k - - m e a n s 方法有如下优点： 对数值属性有很好的几何和统计意义； 对顺序不太敏感； 对凸型聚类有较好结果； 可平行运行； 可在任意范数下进行聚类。 k - - m e a n s 方法有如下缺点： 对初始聚类中心选取较敏感，往往得不到全局最优解，而常常得到的是次优解； 关于k 值的确定没有可行的依据； 缺少可伸缩性； 聚类结果有时会失衡。 对“噪声 和孤立点数据是敏感的，少量的该数据能对平均值产生很大的影响。 2 3 2 基于密度的方法( d b s c a n 算法) ( 1 ) 工作原理 只要临近区域的密度( 对象或者数据点的数目) 超过某个阈值，就继续聚类。也就是 说：对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。 这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。 ( 2 ) 算法描述 基于语义相似度的论文文本聚类算法研究 检查数据库中每个对象的s 邻域，如果一个对象p 的占邻域札( ，) 内包含的对象 数目大于等于m i n p t s ，就创建一个包含m 中所有对象的新聚类c 。 检查c 中还未处理过的对象q ，如果q 的s 邻域m ( ，) 包含的对象数目大于 m i n p t s ，就把m ( ，) 中未包含在聚类c 的对象加入聚类c 中。 对剩下的对象做同样的处理，重复，直到没有新的对象可加入聚类c 。 ( 3 ) 该算法适应的数据类型，以及时间复杂度： 该方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。计算复杂度是o ( n 2 ) 。 ( 4 ) 该算法的优缺点 d b s c a n 存在如下的优点： 可以发现任何形状的簇； 可以过滤“噪声 点。 d b s c a n 存在如下的缺点： 随着数据量的增大，需要有很多的内存支持与i 0 开销。 由于使用了全局参数e 和m i n p t s ，因此没有考虑数据密度和类别距离大小的不 均匀性，d b s c a n 很难得到高质量的聚类结果。 2 3 3 基于模型的方法( s o m 神经网络算法) ( 1 ) 工作原理 神经网络方法将每个簇描述为一个标本。标本作为聚类的“原型”不一定对应一个 特性的数据实例或对象。根据某些距离量度，距离近的对象可以被分配给标本与最相似 的簇。被分配给一个簇的对象的属性可以根据该簇的标本的属性来预测。 典型的神经网络方法有自组织特征映射( s e l f - - o r g a n i z i n gf e a t u r e m a p ，s o m ) ，聚类 也是通过若干的单元竞争当前对象来进行的。权重向量最接近当前对象的单元成为获胜 的或活跃的单元。为了更接近输入对象，对获胜单元及其最近的邻居的权重进行调整。 s o m 假设在输入对象中存在一些拓扑结构或顺序，单元将最终在空间中呈现这种结构。 单元的组织形成一个特征映射。s o m 被认为类似于大脑处理过程，对在二维或三维空 间中可视化高维数据是有用的。 s o m 神经网络聚类方法与实际的大脑处理有很强的理论联系。由于较长的处理时 间和数据的复杂性，需要进一步的研究来使他适用于大型数据库。 ( 2 ) 算法描述 初始化网络连接权值( 可取一个较小的随机值) ，设置一个较大的初始邻域。 大连理工大学硕十学位论文 将一个给定的输入向量加载到网络上。 计算输入向量与权值向量的点积，并选择其中的最大者。 更新所选中节点及其邻域节点的连接权值。 重复步骤，直到满足终止条件。 ( 3 ) 算法的时间复杂度 计算复杂度是o ( x y n t ) ；其中x x y 是神经网络的网格点数目，1 1 是输入向量的数目， t 是神经网络的训练次数。 ( 4 ) s o m 聚类算法的优缺点 优点： 一 可以实现实时学习； 网络具有自稳定性； 无须外界给出评价函数； 能够识别向量空间中最有意义的特征； 抗噪音能力强。 缺点： 当训练样本的数目较少时，算法的结果与训练模式输入的次序有关； 由于需要训练竞争层，算法时间效率比较差。 2 3 4 层次聚类方法 ( 1 ) 基本思想 层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次 的方法可以分为凝聚的方法( a g g l o m e r a t i v e ) 和分裂的方法( d i v i s i v e ) 。 凝聚的方法也称作自底向上的方法。以开始将每个对象作为单独的一个组，然后相 继地合并相似的对象或组，直到所有的组合并成一个( 层次上的最上层) ，或者达到一个 终止条件。 分裂的方法也称作自顶向下的方法。以开始将所有的对象置于一个簇中。在迭代的 每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到 一个终止条件。 ( 2 ) 算法描述 凝聚聚类的算法： 将所有的点各自单独形成一个簇： 从现有所有的簇中选择最近( 或者最相似的两个簇) ，进行合并； 基于语义相似度的论文文本聚类算法研究 如果只剩下一个簇或者达到终止条件( 比如达到需要的簇的数目) ，聚类结束，否 则返回。 分裂聚类的方法： 将所有的点形成一个簇； 通过某种策略从现有所有的簇中选择某个簇进行拆分，将该簇拆成2 个簇； 如果已经拆成n 个簇( n 为所有文档数目) 或者达到了终止条件则结束。 2 3 5 基于网格的方法 基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚 类操作都在这个网格结构( 即向量化的空间) 上进行。这个方法的主要优点是它的处理速 度快，其处理时间独立于数据对象的数目，只与向量化空间中每一维的单元数目有关。 2 4 小结 本章主要介绍了文本聚类的定义和一些常用概念，并分析了常见的几种聚类算法的 基本思想和优缺点。 大连理工大学硕士学位论文 3 基于语义相似度的论文文本聚类 本章根据文本聚类的流程对本文提出的聚类方法做了详细的介绍。主要包括文本的 预处理、特征词的选择、概念间语义相似度的计算、文本间语义相似度的计算以及采用 的聚类算法几个方面。同时为了便于各个阶段的介绍，本章首先详细介绍了w o r d n e t 这个词汇数据库的结构组织方式。然后详细阐述了本文采用的特征词选取方法。对于文 本的数学表示，本文改进了t c u s s 算法中的名词概念列表表示法，将概念节点引入到 概念列表中，方便了特征词相似度的计算。对于特征词间的相似度计算这里用其所在概 念节点间的语义相似度来表示，采用混合法【4 2 】来计算概念相似度。文本间的语义相似度 本文通过特征词间的相似度来计算。最后本文采用t c u s s 算法，结合图的理论进行聚 类，并提出了一种聚簇描述的方法。 3 1 w o r d n e t ：一个词汇数据库 3 1 1w o r d n e t 简介 目前存在很多英文的语义网络，例如k o z i m ah 等人的p a r a d i g m e 语义网络【4 3 1 、 c o l l i nf b 等人的f r a m e n e t 语义网络【删以及m i l l e rg 等人的w o r d n e t 语义网络【4 5 】等。 本文采用的w o r d n e t 语义网络。 w o r d n e t 是美国普林斯顿大学的心理学家、语言学家们共同研发的一套用以研究语 言学的词汇参考系统。一般的词典都是按字母表顺序组织的，将拼写相似的单词放到一 起，但是这样组织却使意义相近的单词分散了。尽管这类词典的在线版本可以减轻用户 的查找负担，可是如果仅仅将计算机作为一个快速翻页的工具是非常没有效率的。 w o r d n e t 就是一个将传统词典编纂和现代计算机科学相结合的产物。它的独特之处在于 它是依据词义而不是依据词形来组织词汇信息。w o r d n e t 使用同义词集合( s y n s e t ) 代表 概念( c o n c e p t ) ，词汇关系在词语之间体现，语义关系在概念之间体现。w o r d n e t 构造 的核心是如何表示词汇概念节点，以及在这些概念节点之间建立起各种语义关系。 w o r d n e t 将英语词汇组织为一个同义词集合( s y n s a ) ，每个集合标明一个词汇概念，同 时力图在概念间建