（计算机应用技术专业论文）基于概念语义分析的文本聚类研究.pdf

摘要随着信息社会尤其是互联网的发展，人们对文本检索的要求越来越高。对传统关键词匹配技术的改进，智能检索研究已经成为热点，并将是支撑下一代互联网的核心技术之一，将语义计算技术应用于文本检索是智能检索的重要方向。基于知网的词汇语义计算方法揭示了词汇间的语义信息。根据文本的向量空间模型描述形式，采用了基于“知网的词汇语义计算方法来计算两篇文章向量的相关性。聚类分析作为一种数据挖掘的重要手段，在文本挖掘中起重要的作用，文本聚类实际上是对文本内容的聚类( 如比亚大学开发的多文档自动文摘系统) 。传统的基于文本关键字的向量空间模型( v s m ) ，用m 个关键字构成的文档向量d i = d l i ，d 2 i ，“i 表示文档集中的一个文档，但是这种方法存在一定的问题。表现在向量空间应用矢量内积计算文本向量空间的相似度，把词语看成了独立的元素，词语之间没有联系，不能明确表达文本语义内容。其次，语义的向量空间模型只是对文本中存在的词语进行匹配，忽略词语中的一词多义以及一个文本语义的多种表示方法。目前，词条集合并不能完全准确地反映文本的语义，可以通过改变文本聚类的途径来对文本的语义进行聚类。文本通过知网的内容来构建概念语义树，消除一词多义和一义多词及一个文本语义的内容可以有多种表达方式等问题的歧义性，将语义相近的文档实现基于内容的聚集。本文基于知网的语义结构，构建了具有添加和删除特点的语义树，使概念的匹配粒度实现细化，并给出了概念语义树匹配算法，实验结果证明了算法的有效性，更好的解决“关键字障碍”和语义歧义性问题，提高查全率。关键字：语义分析；概念匹配；语义树；知网；相关度a b s t r a c tw i t ht h ed e v e l o p m e n to fn e t w o r k ，m ed e m a n d i n go fs e a r c h i n gf o rt e x th a sb e e nr i s e n i n t e l l i g e n ts e a r c h ，an e wt e c l m o l o g yi m p r o v e do nc l a s s i ck e y w o r d sm a t c h j n g ，h a sb e c o m eah o t s p o t i tw i l lb et h ec o r et e c l u l o l o g vo ft h en e x tn e 似o r l ( a n do n eo ft h ei m p o r t a n td i r e c t i o n so fi t 印p l i e ss e m a t i cc o m l t i n gt e c h n o l o g yt ot h es e a r c h i n gf o rt e x t t h eg l o s s a r ys e m a t i cc o u n t i n gt e c l l l l 0 1 0 9 yb a s e do nw o r | m e tr e v e a l st h es e m a t i ci n f o m a t i o n 锄o i 培t h eg l o s s a r y i tc a l c u l a t e s 也er e l a t i v i 四o ft w op a p e r sb yt h ed e s c r i p t i o nf o m so ft e x tv e c t o rs p a c e c l u s t e r i n ga n a l y s i si sa ni m p o i r c a n tm e a n so fd a t am i n i n g ，i ti si m p o r t a l l ti 1 1t e x tm i 血n g t e x tc l u s t e r i n gi sa c t u a l l yt h ec l u s t e r i n go ft e x tc o n t e n t s ( f o re x a n 叩l e ：m em u t i - f i l ee s s a ys y s t e mo fb i y au 1 1 i v e r s i t y ) i nt h ec l a s s i c a lv e c t o rs p a c em o d e l ( v s m ) b a s e do nt e x tk e y w o r d s ，d o c u m e mv e c t o rd i = d l i ，d 2 i ，d m i w a sc o m p o s e do fmk e y w o r d st os t a t eo n ed o c 啪e n to ft h ed o c u m e n ts e t e ；u tt h e r ea r ep r o b l e m si nt h i sm e t l l o d f i r s t ，i tt a k e st h ew o r d sa si n d e p e n d e n te l e m e n t sa n dt h e r ea r en or e l a t i o n s k p sb e t w e e nt h e m 、v h e nc a l c u l a t i n gt 1 1 es i i i l i l 撕哆o ft e x tv e c t o rs p a c e sb yi 彻e rp r o d u c to fv e c t o r i tc a l l tc l e a r l ye x p r e s st h es e m a i l t i cm e a m n go ft h et e x t s e c o n d ，t 1 1 es e m a l l t i cv s mj u s tm a t c h e st h ee x p l i c i tw o r d s 印p e a r di nt h et e x t s ，i g n o r i n gm u l t i p l em e 砌n g so fa 、v o r da n dv 撕o u se x p r e s s i o n so ft e x ts e m a n t i c s t h es e to fv o c a b u l a l we m r i e sc a n te x a c t l vr e n e c tt h es e m a n t i c so ft e x t s b u ti tc a nc l u s t e rt h es e m a n t i c so ft h et e x t sb yc h a n 百n gt h em e t h o do ft e x tc l u s t e r i n g t h es e m a n t i ct r e ec o n s i s t so fc o n t e n t so fh o wn e tt oe l i m i n a t et h e 锄b i g u i t i e so fw o r d sa n dc l u s t e rs e m a n t i cs i m i l a rd o c u m e n t sb a s e do nc l u s t e r i n go fc o n t e n t s i nt m sp a p e ls e m a n t i ct r e e sw m c hh a v ea c c e s s i o na 1 1 dd e l e t i o na r ee s t a b l i s h e db a s e do nh o w n e tt oi m p l e m e n t 伊a n u l 撕t yc o n c e p tm a t c h i n g t h ec o n c e p ts e m a n t i ct r e em a t c h i n ga r i t h n l e t i ci sp r e s e n t e d t h ee f f i c i e n c yo f 耐t l u l l e t i ci sp r o v e db yt h er e s u l to ft h ee x p e r i m e n ta n dt h ep r o b l e mo f ”k e yw o r do b s t a c l e ”a n ds e m a n t i c 锄b i g u i 够c a nb es o l v e dm u c hb e t t e rb yt h ea r i t h m e t i c t h er e c a l lr a d i oi si m d r o v e d k e yw o r d s ：s e m a n t i cr e l e v a n c y ；c o n c e p tm a t c h i n g ；s e m a t i ct r e e ；h o wn e t ；s e m a n t i cs i m i l 撕t ) r ；i i学位论文使用授权书本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技东北师范大学硕士学位论文己i吉丁i口随着计算机的广泛应用和i n t e m e t 的普及，人们所需的信息量急剧增长。信息量的增加给人们带来了很大方便，但是同时也带存在一个信息过量的问题。数据的大量涌入，大大增加了我们获取所需信息的难度。面对如此大量、纷繁复杂的信息，人们越来越希望能够在已有的数据分析的基础上进行科学研究、商业决策或企业管理n ：。在现实生活中，文本是信息最重要的载体，事实上，研究表明信息有8 0 包含在文本文档中心3 。特别在互联网上，文本数据广泛地存在于各种形式，如新闻报道、电子图书、研究论文、数字图书馆、网页、电子邮件等等。面对大量杂乱的文本数据，为了便于工作，人们经常遇到的问题是，如何对文本进行分类、比较，评估文本的相关性和重要性，以及发现众多文本的模式与趋势。目前人们想通过数据挖掘来解决这个问题。文本挖掘属于数据挖掘这一交叉学科的一个具体领域，它的主要任务是分析文档数据库的内容，发现文档数据集中概念、文档之间的相互关系和作用，抽取有效、新颖、有用、可理解的、散布在文本文件中的有价值的知识，并利用这些知识更好地组织信息。文本挖掘处理的是非结构化的文本信息，而不是通常数据挖掘中采用的结构化数据信息。文本挖掘的主要研究内容包括关联分析、文本分类、文本聚类等，。要实现对大量文本的自动分类，可以采用文本分类和文本聚类两种方法。文本分类是在分析文本内容的基础上将多篇文本分成一个或多个类别。它通常由两个阶段组成：训练阶段和分类阶段h 3 。在训练阶段，从训练文本中学习分类知识，建立分类器模型：在分类阶段根据分类器将输入文本分到最可能的类别中。从这个过程可以看出，分类需要事先存在的人工分类好的训练数据。但是，在信息变化莫测的今天，常常会出现新的数据很难用己有的分类体系来处理。如果重新进行分类，就必须重新建立分类好的训练文档集，而获得大量带有类别标注的样本的代价是很大的，这时聚类的方法就显得很重要。聚类( c l u s t e r i n g ) 又称聚类分析( c l u s t e r i n ga n a l y s i s ) ，是最重要的无教师学习的方法。聚类是一个将数据集划分为若干类的过程，并使得同一个类的数据对象具有较高的相似性，而不相同类中的数据对象则具有较大的相异性。聚类与分类不同在于，在分类问题中，已经事先知道对象的分类属性，分类的工作就是根据训练样本将每一个对象分别属于哪一类标记出来，而聚类分析的输入数据集是一组未标记的对象，也就是说此时输入的对象还没有被进行任何分类，聚类的目的是根据一定的规则，合理地进行分组或聚类，并用显式或隐式的方法描述不同的类别瞄1 。由于分析可以采用不同的算法，所以对于相同的数据集合可能有不同的划分。聚类是无指导学习的方法，分类是有指导学习的方法，两者所采用的方法相差甚远，并且聚类的时间复杂度要比分类大得多。聚类是无教师的机器学习，它是一种应用于知识发现与数据挖掘的分析手段，它按照事物的某些属性，将事物分成多个类或簇，使得在同一类别中的事物相似度达到最大，1东北师范大学硕士学位论文不同类别间的事物相似度尽量小哺。聚类作为一种非监督型的知识发现方法，不需要任何事先的训练数据，而仅仅按照相似度原则，将一组数据划分为事先未知的分类状态，因而是一种有效的，得到广泛应用的模式识别与知识发现的方法。在文本聚类中，短文档聚类存在高维稀疏性问题，导致了文档的查全率低下，本文基于这一问题在知网结构下进行概念语义分析，提出节点关键词映射知网关键词的匹配法，来解决高维稀疏性问题。文本聚类的方法大致可分为层次凝聚法和平面划分法两种类型盯8 3 传统的基于文本关键字的向量空间模型( v s m ) ，用m 个关键字构成的文档向量d j = d l i ，d 2 j ，“i ) 表示文档集中的一个文档，这种方法存在一定的问题。表现在向量空间应用矢量内积计算文本向量空间的相似度，把词语看成了独立的元素，词语之间没有联系，不能明确表达文本语义内容。其次，语义的向量空间模型只是对文本中存在的词语进行匹配，忽略词语中的一词多义以及一个文本语义的多种表示方法。知网( h o wn e t ) 是一个以汉语和英语的词语所代表的概念为描述对象，以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库，知网是面向计算机的双语常识知识库。目前，词条集合并不能完全准确地反映文本的语义，可以通过改变文本聚类的途径来对文本的语义进行聚类。文本通过知网的内容来构建概念语义树，消除一词多义和一义多词及一个文本语义的内容可以有多种表达方式等问题的歧义性，将语义相近的文档实现基于内容的聚集。文本通过知网的内容来构建概念语义树，进行概念语义分析，消除一词多义、一义多词及一个文本语义内容可以有多种表达方式等问题的歧义性，并通过细粒度计算来解决稀疏性问题，提高查全率，从而将语义相近的文档实现基于内容的聚类本文。本文的结构如下：第一章，绪论主要介绍了研究背景及意义、文本聚类概念及本文的研究目标及主要工作；第二介绍了文本聚类的主要因素；第三章：语义树及语义的相关度问题；第四章：介绍概念离线语义树和动态语义树的构建、查询及公式；第五章：实验部分，给出了实验结果以及实验分析，并对该工作进行总结，并提出了进一步研究设想，从而为后续研究提供了基本思路。2东北师范大学硕士学位论文1 1 研究背景及意义第一章绪论2 1 世纪，计算机技术和网络通信技术正在推动人类各方面的进步，互联网已经成为人们不可缺少的信息来源。目前，网络资源数据增长速度飞快，人们要获取所需的信息要花费很多时间，所以，如何快速准确获取信息成为焦点。传统的信息搜索技术存在着这局限性，已经不能适应目前增加的大量文本数据处理，文本挖掘( t e x tm i n i n g ) 成了数据挖掘的一个很有前途的研究方向。文本处理的特殊性，不能像数据库中的数据，文本处理需要有自然语言理解的支持，目前机器对自然语言理解还存在很多歧义问题，因此文本挖掘还不能很好的表达理解的层次。文本数据挖掘中的概念与方法有很多是直接来源于传统的数据挖掘技术。数据挖掘技术是一种从大量数据中提取其潜在信息的方法论。聚类分析是文本挖掘的主要手段之一，他的主要作用是：1 ) 通过对检索结果的聚类，将检索到的大量网页以一定的类别提供给用户，使用户能快速定位查找的目标；2 ) 自动生成分类目录；3 ) 通过相似网页的归并便于分析网页的共性。其中的一个重要的应用方面就是聚类。对于文本数据来说，聚类就是尝试将不同的文档按照其内在的信息进行归类，使得聚类之后的各类文档，在同一个类中文档具有最大的相似性，而处于不同的类中的文档具有最大的差异性n 川。从数学角度来看，文本聚类是一个映射的过程，它将未标明类别的文本映射到根据文本内容自发形成的类别当中，该映射可以是一对一映射，也可以是一对多的映射，因为通常一篇文本可以同多个类别相关联。用数学公式( 卜1 ) 表示如下：厂：彳一b ；( 卜1 )其中，么为等待聚类的文本集合，b 为聚类系统中的类别集合；文本聚类作为基础研究，对已有网络信息资源的组织和检索起到很大作用。过去都是通过人工完成文档分类，费时费力。利用计算机进行文本分类是一种有效的方法。综上所述，文本聚类随着网络快速发展而得到重视和发展，文本聚类技术将成为人工智能领域一个重要的研究课题。目前，国内很多学者对中文文本分类进行了深入研究，如黄萱箐h 5 。等提出一种基于机器学习的、独立于语种的文本分类模型。周水庚h 明等在论述隐含语义索引的理论基础，研究了隐含语义索引在中文文本处理中的应用。李荣陆h 铂等使用最大熵模型对中文文本分类进行研究。张剑h 副等提出一种以w b r dn e t 语言本体库为基础，建立文本的概念向量空间模型作为文本特征向量的特征提取方法。对于中文文本分类的研究已经做了很多工作，中文与英文存在本质上的不同，中文存在多义词、同义词等等复杂情况，但是对东北师范大学硕士学位论文于多义词、同义词等问题也是可以解决的，本文提出了一种方法来解决了这个难题。1 2 聚类分析1 2 1 聚类的概念聚类( c l u s t e r i n g ) 就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类或簇( c l u s t e r ) 的过程。聚类所生成的类是对象的集合，这些对象与同一个类中的对象彼此相似，与其它类中的对象相异。聚类的严格数学描述如下旧3被研究的样本集为e ，类c 定义为e 的一个非空子集，即cce 且c 西聚类就是满足下列两个条件的类c 1 ，c ：，c r 的集合1 c 1u c ：u ug = e2 c ，r 、c ，= 咖( 对任意f ，)由第一个条件可知，样本集e 中的每个样本必定属于某个类；第二个条件可知，样本集e 中的每个样本最多只属于一个类。定义1 阳给定由一些元组组成的数据库d = “，f ：，乙) 和整数值尼，则聚类问题就是定义一个映射厂：d 一 1 ，七) ，其中第i 个元组i 被映射到第j 个簇k ，中去。第j 个簇k ，由所有被映射到该簇中的元组组成，即k ，= l 厂( i ) = k ，1 ，七，f ，d ) 。定义2 哺0 1 给定由一些元组组成的数据库d = 乞，。) 以及两个元组f ，t d 之间的相似性度量s 砌( r ，f ，) 和整数值k ，则聚类问题就是定义一个映射厂：dj 1 ，j j ) ，其中第，个元组，被映射到第j 个簇k ，中去，1 ，忌。给定簇k ，对于v 7 ，1 ，f ，后，和t 仨七，。有s f 聊( ，1 ，f ，。) s f 所( 1 ，i ) 。聚类分析也称群分析、点群分析，它是研究分类问题的一种多元统计方法h 9 。j 引。它和判别分析都属于分类方法，判别分析属于“训练学习”分类，而聚类分析属于“自我学习的分类。聚类分析根据分类对象不同分为q 型聚类和r 型聚类4 旷5 3 3 ：q 型聚类是指对样本进行聚类，可以用来预测，样本分布划分等；r 型聚类是指对变量进行聚类( 分类处理) ，用于变量的选择。1 2 2 聚类的应用领域如上所述，聚类分析是数理统计中研究“物以类聚”的一种方法，它是多元分析的一个分支，目前已被用于信息检索1 62 | 、模式识别哺3 6 4 | 、机器学习阳5 蚓、图像处理铂等研究领域。在各种领域，可以从时间上聚类，也可以从地域上聚类，还可以从其他因素上进行聚类。聚类分析根据样本的属性和特征等方法来定样本间的关系，按自然程度，客观程度进行聚类，从而得到合理结果。4东北师范大学硕士学位论文1 3 文本聚类1 3 1 文本聚类研究背景文本聚类的映射规则是系统根据已经掌握的每个文本若干数据信息，计算出文本之间的近似程度，再根据文本与各个自动聚集形成的类别之间的相似程度，逐渐将每个文本和各个类别联系起来。具体而言，通常的认识是将不同的文档按照各自的主题进行聚类，聚类之后的文档在同一个类中具有相同或近似的主题，不同的类则代表不同的主题。文本聚类技术在对大规模文本集的组织、浏览、文本集的层次归类的自动生成等方面有非常重要的应用，诸如通过对检索文档聚类，为用户呈现有组织的和可理解的结果；在文档集中聚类文档( 电子图书馆) ；自动的( 或半自动的) 创建文档类别目录( y a h o o ) ；以及通过在相关的子集( 聚类) 而不是在整个文档集中检索文档，以获得高效的信息检索。文本聚类的方法包括了决策树n 2 3 | 、统计方法n 4 1 引、神经网络n6 1 、启发式逻辑n 7 1以及基于规则的系统鲫等其他方法。这些方法分别来自不同的研究领域，包括数据库( d b ) 、信息检索( i r ) 、人工智能( a i ) 中的机器学习( m l ) 与自然语言处理州l p ) n 引。对于任意一种聚类技术来说，都包含了以下四个方面的概念：一种数据的表示模型一种相似度测量方法一种聚类模型一种采用上述数据模型以及相似度测量方法建立聚类的聚类算法目前，文本聚类领域的研究主要集中在以下几个方面：( 1 ) 对大规模文本集进行有效数学模型化的问题，主要与语言文字的特性相关；( 2 ) 在无指导的情况下确定文本集中文本主题数目的问题，也就是说如何确定聚类之后所形成的累的数目；( 3 ) 在算法的时间复杂度和准确度上做平衡的问题。根据对文本数据建立表示模型方式以及相似度测量方式的不同，可以将现有的文本聚类方法分成两类：不考虑文本语序( 基于单词) 进行建模和计算相似度的聚类方法和考虑文本语序( 基于短语) 进行建模和计算相似度的聚类方法。1 3 2 概述及分类将文本进行归类的方法有两种：文本聚类和文本分类。文本分类是一个有指导的学习过程。一个已经被人工标注的训练文本集合，寻找文本属性和文本类别之间的关系关系模型( 称为分类规则) ，然后用学习得到的关系模型对新文本进行自动的类别判断。所以说文本分类一般分为训练和分类两个阶段。东北师范大学硕士学位论文图1 1 文本分类学习阶段图1 2 文本分类分类阶段文本聚类与分类的不同之处在于，文本聚类是一个无人指导的学习过程，没有预先定义好的主题类别，在每一个类中，文本间具有尽可能大的相似性，而不同类之间，具有最大的非相似性。也就是说，文本分类需要人工给予计算机一段时间，等其掌握了学习规则后在自学；而文本聚类不需要人工给时间，计算机能通过观察来学习。文本聚类的步骤：图1 3 文本聚类步骤1 3 3 文本聚类的定义定义1 1 ：文本聚类( t e x tc l u s t e r i n g ) 是对一个给定的文本集合d = 吐，吃，吨) 进行划分，从而得到一个类的集合c = c l ，c 2 ，吒) ，其中c ，cd ( = 1 ，2 ，尼) ，使得对v 谚( 谚d ) ，j 巳( 巳c ) 且巧c ，同时使得代价函数厂( c ) 达到最小。文本聚类的一般过程可以用图1 1 表示：文档图1 4 文本聚类的流程1 3 4 文本聚类的算法分类通过定义1 1 ，对一个文本对象矿，并没有规定其归属的类的数目，一个文本对象可以仅仅属于一个类，也可以属于多个类。这样就可以把聚类算法划分为两类“1 l ：分别为硬聚类和软聚类。6东北师范大学硕士学位论文目前聚类算法可以分为以下几类：1 划分法划分算法h 2 ：给定一个有n 个元组或者记录的数据集，构造k 个分组，每一个分组代表一个聚类( k d ，则取d ( b ，p ，) = d 。注：d ( p ，p ，) = m a x l d ( p 1 ，p 2 ) ，d ( p 2 ，p 1 ) 】( 3 5 )概念是根据多个义原组成的义原项来解释，每个概念主要分为4 部分义原，它们按从主到次的顺序对概念进行描述。在义原的体系结构中，每个义原与其它树中的义原也会存在一定关系，因此义原体系结构增加了横向联系，这样就存在义原的横向关联扩展。综上所述分析，对各项因素加权平均即可得出词相关度，记为r ，公式b 43 为：r ( w 】，w 2 ) = m a x l 叩。窆卢，l n q ( s ，是) + 叩：i1 一坐妥型l + r 7 ，e ( s ，曼)( 3 删li ：ljj = ll“j式中7 7 1 + 叩2 + ，7 3 = 1 ；女口7 7 3 为o 时，7 7 】+ 叼2 = l 。3 4 本章小结本章介绍了语义树及语义相关度，语义树为二叉树，在本章开始对二叉树进行了简单的介绍，语义树的主要特点是“即用即造”可以离线构建也可以在动态构建。语义相关度是一个模糊的概念，没有明确的客观标准可以衡量。语义相关度与语义相似度是两个不同的概念，但两者之间有着密切的联系，语义相关度是由义原的相似度与关联度所决定。通过“知网”了解了概念，概念由多个义原所组成的义原项来加以解释，每个概念主要分为4 部分义原，在对概念与词进行比较的时候主要就是对这4 部分义原进行比较，来实现文档的比对。东北师范大学硕士学位论文第四章概念语义树及公式本文提出了概念语义树的构建及相似度公式( 4 1 ) ，在词的向量空间模型里存在“关键词障碍”的问题，在自然语言文本中广泛存在一词多义，一义多词以及一个文本语义的内容可以有多种表达方式等问题。这样使得基于词语向量空间模型的查询和文本的语义匹配性不能达到最佳。本文应用了语义树，在文中将构建一个概念语义树来解决语义匹配的问题，实现基于语义的查询。语义树口。是按照某种规则在有向二叉树的每个结点上都标记有一个合式公式而构成。4 1 构造概念语义树语义树模型的构造有离线构造语义树h j 和动态构造语义树。4 1 1 离线构造语义树设r s i m ( p ，q ) 为概念p 与词q 之间的相似度值，对任意给定的概念p ，采用树状的模型来表达概念p 与所有其它概念的关系，如图1 所示。pppq 1q mqaq lq mq lq iq mbc图4 1 离线语义树在图4 1 中，以概念p 为根结点，词q 为叶结点，两者之间的路径权值是概念与词的相似度。从q ，到q ，的所有词都是按照词与概念p 之间的相似度来排序的，与p 相似度越高的词在最左边，以满足下式：r & m ( p ，9 1 ) r 所聊( p ，9 2 ) r 研聊( p ，g ，) r 辩聊( p ，g 。)在图4 1 三棵树中，确定相似度的方法。首先，保留了从左起到m 个词，其余的词丢弃；其次从级到g 。的相似度区间为( 1 o 4 ) ，对保留的m 个词进行在次划分，具体分为g 。到g f ，研到，定义9 1 到g ，的相似度区间为( 1 o 6 ) ，g ，到吼的相似度区间为( 0 6 o 4 ) 。本文是将b 树进行在次划分，这样可以更进一步的对语义度进行比较，东北师范大学硕士学位论文提高文本与文本集的聚类效果。构造离线语义树的算法如下。在文档集d 中，p 为概念向量空间 p 1 ，p 2 ，p n )b u i l d p s t ( t )输入：查询文档q ，q 为词向量空间 q l ，q 2 ，q 。)输出：b u i l d p s t ( t7 )i f1 s i m ( p ，q m ) 0 4t h e n ；r e t u mq m ；e l s er e m o v e ( t ，q m ) ；i fs i m ( p ，q i ) s n ( p ，q m ) 0 4 ；0 4 s i m 0 ，q i ) us i m 0 ，q m ) 1 ；i f0 6 s i m ( p ，q i ) s 1t h e n ；0 4 茎s i m ( p ，q m ) 0 6 ；t 1 1 e np s t ( t ) ；离线语义树的结构是根据特定的应用来构造的，p 为初始的概念向量，作为整个语义树的根结点。4 1 2 动态构造语义树通过知网我们知道概念是由义原组构成的，先设定p = ( a p ：，见) 表示初始的义原组向量，其中玎的值是随机的，岛为第f 个义原组。通过p 这个初始义原组向量构造语义树c s t m ( c o n c e p ts i m i l a r i t yt r e em o d e l ) ，田聊( p ，v ，) 中的v 代表语义树的层数，代表语义树每个元素( 其中还包含i b e s t 和m b e s t ) ，也就是每个相对根节点都连接着至少聊个叶节点来构造语义树。如图4 3 所示。这样语义树由多个i b e s t 树和m _ b e s t 树在不同层次上构建起来，通过这棵语义树可以容易获得根节点概念与叶节点词之间的相似度值。具体定义如下：i 根节点p 与它的叶节点q 之间的路径是指节点p 到节点q 的路由。i i 根节点p 与它的叶节点q 之间的路径的权值是所有在路径上的树枝的权值相乘，权值在构造i - b e s t 树和m _ b e s t 树时给定。iji 根节点p 和它的叶节点q 之间的最短路径是指他们的之间的最大权值的路径。i v 根节点p 和它的叶节点q 之间的相似度是指他们之间的最短路径的权值。在概念语义树中，路径越短，越靠近左侧说明他们就越相似。p 为一个概念集，q为词汇集，通常多个词汇可以映射到一个概念下，但是概念对词汇解释的程度是不同的，所以出现了概念与词之间的相似度问题。2 0东北师范大学硕士学位论文原始查询霎。1一、一p 。p 。+ 1 6 ： 1心p、八八、八ji 八ji 儿ji图4 2 动态语义树c s t m第二层第v 层概念语义树( c s t m ) 算法如下：设p 为概念向量( p l ，p 2 ，p n )输入：q 为词向量( q l ，q 2 ，q n )输出：s i m v a l u e ；t e m p v a l u ei f1 r ( p ，q m ) 0 4 ；1 s i m ( p ，q m ) 0 4t h e nr e t u mq me l s ei fr ( p ，q i ) r ( p ，q m ) 0 4 ；0 4 r ( p ，q i ) ur ( p ，q m ) 1 ；e l s ei fs i m ( p ，q i ) s i m ( p ，q m ) 0 4 ；0 4 s i m ( p ，q i ) us i m ( p ，q m ) 1 ；i fr ( p ，q m ) 0 4 ；f o r ( i - 0 ，i s i m ；i + + ) s v a l u e + = s i m i )i fs v a l u e 0 4 r e t u ms i m v a l u e = s v a l u e )e l s ei fr ( p ，q m ) o 4t h e nr e t u mf a l s ei fr ( p ，q i ) 0 6 ；f o r ( i _ 0 ，i s i m ；i + + ) s v a l u e + = s i m i )层一第虿囊惶惶忆。八二一、十，、=0q东北师范大学硕士学位论文i fs i m ( p ，q i ) 0 6 ； r e t u ms i m v a l u e = s v a l u e )i f( r ( p ，q i ) o 6 ，s i m ( p ，q i ) o 6 ) t e m p v a l u e = a l u e ；t e m p i n d e x = i ；s i m v a l u e = s v a l u e ；s i m v a l u e 气e m p i n d e x ；)i f r ( p ，q i ) o 4 ，s v a l u e o 4f o rs i mp 气r + ( 1 一t ) ks v a l u ei fs i m a o 4t h e nr e t 啪t r u ee l s ef a i s e4 2 相似度计算公式第三章我们介绍了语义相关度的定义及意义，根据语义相关度，对每个义原进行划分，根据语义相关度，对每个义原进行划分，在纵向与横向两个方面求出相关度可以更加准确的描述概念间的关系。以下给出了相关度与相似度的公式：( 4 一1 ) 。脚捌= 一降，冉鼢机( 一掣 饥圳洚，r ( 删) = 蝴l 叩，卢，兀q ( s 神机l1 一半il；1ir ”一”一1 、f4 1 、j f 脚( p ，g ) = 5 f 朋( p ，q ，)式( 4 1 ) 中，为义原项s ，s 的第一基本义原，d 为横向关联影响的深度q ( s ：，是) 表示的4 个部分义原，卢，( 1 f 4 ) 是可调节的参数，且卢1 + 卢2 + 卢3 + p 。= 1 ，届卢2 卢，卢。是h 。到h 。对总体相似度的影响，只有屈有较大的权值，j 咖( p ，吼) 是概念p 和词g ，之间的相似度，以下给予证明。证明：1 对p ，g 两个集合，卢p ，口g ，如果a 卢，a = 卢，卢是a 的祖先，那么可以说明p 与g 相似( s e m i p a r t o f ) 。2 定义p 的属性为鸭= ( ，厶，l ，q ，d 2 ，q ) ，p 的值域为尸d l ，定义域为飓，其中尸d 】2 ( ，厶，l ) ，瑚。( d 1 ，q ，q ) ；对任意元素a ，g l ，v ，如果( f ，) p 。，那么( f ，) g 。，所有说p 。与g l 语义相似。3 任意的元素p ，与吼，vf ，如果f 码，飓，所以f 鹏，瑚。，则称p 。与g l 语义相似。匹配度( m a t c h i n gm e a s u r e m e n t ) 公式：m m ：竺! 翌：垡2 ! ! 二1 2 竺塑! 旦：塑( 4 2 )f 为查询过程中所定义的阈值，尼为语义树的路径长度( 尼= 1 0 ) ，d 为所要查询文东北师范大学硕士学位论文档的路径，公式( 4 2 ) 把相关度与相似度相结合而得所要求出综合匹配度。通过上述证明对公式( 4 1 ) 的可行性进行了求证，概念向量p 与词向量g 通过相似度和相关度求得。有要查询的文档时，把文档设为m ，w 的文档向量为( w ，w ，w 。) ，根据公式( 4 1 ) 对文档向量w 与印进行计算，对其所得的相似度与相关度进行匹配度的计算从而对节点关键词与知网匹配关键词比较，只有两个值都高的时说明w 与g 是相似的，再求文档w 与概念p 的相似度与相关度。公式( 4 1 ) 是根据向量相似度扩展公式( 3 1 ) 和语义相关度公式( 3 6 ) 推理而来并加以证明，公式( 3 一1 ) 求得的是词与关键词向量之间的相似度而公式( 3 6 ) 考虑了概念义原的相似度和并联度的关系，本文的公式结合上两个公式的优点而成，在对概念与词之间进行比较是不仅仅考虑其相似度还要想到其相关度，这样就可以避免了相关度高而相似度低的情况，并且从纵向跟横向两个角度来求得相关度，当相似度达到要求数值的时候而相关度也大于等于该数值，才会进行下一步的比对，否则要对该词进行删除，根据通过细粒度计算来解决文档稀疏性问题，可以提高概念与词之间匹配度从而提高文档之间的匹配度，从而提高了文本聚类的分类效果。4 3 本章小结介绍了文档聚类的结构图，概念语义树及相似度公式( 4 1 ) 做了详细介绍，并给出了匹配度公式( 4 2 ) ，概念语义树及基于知网中概念的关系来对语义树间各个结点进行比较，在比较过程中，对相似度值给定的范围的分类更细致，语义树具有即用即造的特点，概念不是只代表单个一个词，而是代表一个类。相似度公式不仅对概念间的相似度作比对，还结合了相关度，从多方面考虑了概念间的关系，本文将语义相关度与相似度相结合算出语义匹配度( m a t c h i n gm e a s u r e m e n t ) ，通过细粒度计算来解决文档中存在的稀疏性问题，从而提高文档的查全率，得到更好的聚类的效果。东北师范大学硕士学位论文5 1 实验环境第五章实验总结与性能分析本文实验的硬件环境：c p u ：酷睿2t 7 1 0 0 ；内存：1 g ；硬盘：1 1 0 g5 4 0 0 印s ；操作系统为w i n d o w s p r o f e s s i o n a ls p 2 ；软件环境lp a r s e r ：j d o m l 0 ；数据库管理系统：m i c r o s o rs q ls e r v e r2 0 0 0s p 4 ；开发工具：c + + 6 0 。5 2 实验过程本实验是x m l 文档为实验例子，在实验中我们构建了一个以学校为例子的x m l 文档，根据这个例子与库中已存在的文档进行比较，当多取值不同时，实验结果有一定改变。实验一：输入x m l 文档：一一学校一大学二师范大学一计算机学院 网络2 4东北师范大学硕士学位论文 高校，大学，政府，银行，公司】【大专，高职，高校，中专，大学】【东北师范大学，北京师范大学，华东师范大学，长春师范学院，师范学校】【计算机系，计算机，计算机科学，计算机公司，历史学院】 二! 至薹茎三二卜r 网络理论，网络技术，通信技术，网络安全，网络通信，图5 1 输入x m l 文档5 3 实验结果本文应用相关度与相似度相结合的方法从横向与纵向两个方面进行比较求得概念相似度。图5 1 中给出x m l 文档树的相对应的概念语义向量，并以c o l l e g e 一计算机学院为例进行比较。c o l l e g e 一计算机学院：匹配度公式计算机学院j ：l 一计算机系，所得的相似度为0 7 2匹配度公式计算机学院上一计算机，相似度为o 3 9 2在构建语义树时，本文对相似度进行了进一步的划分，当相似度 0 3 时将删除，相似度0 3 时再次求其相似度，相似度0 6 时直接进行下一级的比较。通过上面例子看出，在比较时计算机系会直接返回。给定实验参数b ，a 求得相似度的值如表一。本文算法是基于概念的相似度进行比对，图5 3 可以看出本文的算法可以比较准确给出概念与词之间关系，通过上图可以看出第一义原的大小觉得这词之间相似度的关系。当卢12 0 4 8 卢72 0 2 5 卢32 0 2 卢4 。o 0 7d = 1 6 时实验结果如下：2 5东北师范大学硕士学位论文表一：r ( p ，g ) 2 0 4 时实验结果比对图节点关键词知网匹配关键词匹配度( o 4 )撒二高中o 4 3 1 3 6大学0 6 4 8 7 6 8大学。学校0 6 9 6 8”3 蕊大专0 1 5 2高校0 6 8 8、职业学校0 2 1 8 4东北师范大学o 6 6 9 1 2北京师范大学0 7 1 5 0 4华东师范大学0 6 6 8 8师范学院0 8 3 7 7 6白城师范学院o 4 5 2 9 6吉林师范大学o 6 7 9 3 6长春师范学院o 4 1 6 4计算机系0 7 2计算机0 3 9 2计算机科学o 6 0 4 1 6计算机学报o 3 3 2网络技术0 8 2 8网络理论0 8 6 2 4网络教程o 8 6 6 4通信技术0 4 0 8网络安全0 7 9 7 6一网络通信0 7 9 7 62 6东北师范大学硕士学位论文表二：r ( p ，g ) 2 0 5 5 时实验结果比对图节点关键词知网匹配关键词匹配度( o 5 5 )计算机学院-计算机系0 5 7师范大学-师范学院0 6 5 9 9 2陷网络技术0 6 5 1网络理论0 6 7 5 8网络教程o 6 8 1 3图5 2m m = o 5 5 时的结果图2 7东北师范大学硕士学位论文图5 3m m = 0 4 时的结果图图5 2 的实验数据对比，说明本文的方法取得了较好的效果，当第一义原越大相似度也就越大，本文的方法所得出来的比较数值比较平缓，本实验中所得各个概念之间的相似度为得到的结果为上图。还是以该文档为例，在实验中个概念之间当相似度为0 4时，所得的文档相似度为0 7 ，表三给出了相对应的参数值。实验二：输入文档一一削一苹果一面包一巧克力2 8东北师范大学硕士学位论文 吃切，砍，苹果，刀，皮】【刀，皮，橘子，苹果，牛奶蛋糕，苹果，巧克力，报纸，饼干 糖，饮料，水果糖，白糖面包，报纸，蛋糕，饮料，刀图5 4 输入姗l 文档当卢1 = o 3 2 卢2 = o 3 卢3 = o 2 5 卢42 0 1 7a = 1 6 时实验结果如下：表三实验结果比对2 9东北师范大学硕士学位论文图5 5m m = 0 4 时的结果图由表中数据可以看出，文献6 相似度算法得出的相似度的粒度大相似度较低，如“面包”和“报纸”的相似度比“面包”和“苹果”的要高；在相关度算法得出的相关度比相似度有改善，但“面包”和“巧克力”的相关度完全一样。在本文提出算法中得出的结果粒度小相似度高。实验三：输入文档- 一宾馆一吉林省宾馆一人民大街3 0东北师范大学硕士学位论文饭店，宾馆，大酒店山宾馆，时尚宾馆，吉林省宾馆，】咱由大路，人民大街，新民大街，南湖大路】图5 6 输入x m l 文档当p 1 = o 4 卢2 = o 2 5 卢3 = o 2 卢4 2 0 1 5a = 1 6 时实验结果如下：图5 7 删_ 0 4 时的结果图东北师范大学硕士学位论文图5 8m m = 0 6 时的结果图实验三构建了简单的x m l 文档，在进行比较时，概念间的相似度的取值仍然是0 4和0 6 两个值，当相似度取值为0 4 时，所得的相似度为o 8 ；当取值为0 6 是，所得的结果为0 7 。实验二说明了，当相似度取值小是，所得的文档相似度会大，但是检索到的内容可能不会很理想，当相似度取值比较大，所得的结果反而比较好。实验四：不相似文档本实验还做了不相似文本的比较，还是以上个x m l 文档为例子，但是数据库中的文档有所改变，但是数据集中还是包括x m l 文档中的概念词，在实验中，x m l 文档中的各个概念跟数据库中的概念进行比较，每个单独的概念都找到了相似的数据，但是整个档比较时就没有发现相似文档。3 2东北师范大学硕士学位论文5 4 实验分析图5 9 不相似文档实验结果本文通过对两个相似文档和一个不相似文档进行了实验并加以分析，实验中分别对两个相似文档在相似度为0 4 和o 6 两种情况下得到的数据进行如下分析。1 当相似度为0 4 是，概念向量与每个词向量间的相似度很大，而且很接近，所得的整体文档的相似度也相对比较大，这样