（计算机软件与理论专业论文）中文短语相似度计算方法研究及应用.pdf

摘要 文本相似度计算作为中文信息处理中的一项基础性技术，被广泛应用到文本 分类、文本聚类、信息检索等多个领域，长期以来受到了众多学者的关注和研究。 在信息大爆炸所带来的大量文本信息的数据堆积中，很大一部分是短文本数据或 短语数据，因此，在短文本数据信息的处理问题上，短语的相似度计算变得越来 越重要。本文就是针对中文短语信息的处理问题，提出了一种新的中文短语相似 度计算方法。在算法的设计过程中，本文分析了短语间相匹配文字的位置、匹配 位置的偏移值、匹配文字长度等多种因素，提媳了中文短语闻相似度的计算公式， 并给出了该算法的实现代码。 曝绕中文短语相似度计算问题，本文主要做了以下几方面王作： 首先，研究了多种文本相似度计算方法，并分析了文本相似度计算的现状和 几种经典的文本相似度算法，对其适用领域和优缺点进行了剖析：分析了文本相 似度计算在文本聚类中的应用和凡种文本聚类方法。 其次，在对现有文本相似度计算方法分析研究的基础上，针对短语级别文本 的信息处理润题，提出了一种新的中文短语相似度计算方法，然后对该方法的合 理性进行了检验，并通过将不同的文本相似度算法用于同一种聚类算法，对本文 提出的方法的有效性进行了检验。 最后，将中文短语相似度计算方法用于高校培养计划管理系统中的相似课程 排查模块，实现了相似课程的聚类，并对整个系统进行设计实现。 本课题的研究及其成果对于中文信息处理中的多个领域尤其是中文短语的处 理问题，都有一定的参考价值和良好的应用前景。 关键字：信息处理；文本聚类；中文短语相似度；匹配偏移；相似课程排查 a bs t r a c t a saf u n d a m e n t a lt e c h n o l o g yi nc h i n e s ei n f o r m a t i o np r o c e s s i n g ，t h ec a l c u l a t i o n o ft e x ts i m i l a r i t yi s a p p l i e di ns u c hf i e l d sa st e x tc l a s s i f i c a t i o n ，t e x tc l u s t e r i n ga n d i n f o r m a t i o nr e t r i e v a la n ds oo n ，w h i c hh a sb e e nc o n c e r n e da n ds t u d i e db ym a n y s c i e n t i s t sf o ral o n gt i m e i nt h eh u g et e x td a t ab r o u g h tb yh i g h l yd e v e l o p m e n to ft h e i n f o r m a t i o nt e c h n o l o g y , al a r g em a j o r i t yo fw h i c ha r es h o r tt e x to rp h r a s e s o ，d u r i n g t h es h o r tt e x ti n f o r m a t i o np r o c e s s i n g ，t h ep r o b l e mo fp h r a s es i m i l a r i t yc a l c u l a t i o n b e c o m e sm o r ea n dm o r ei m p o r t a n t 。t h i sp a p e ra d d r e s s e san e wa l g o r i t h mf o rc h i n e s e p h r a s es i m i l a r i t yt og i v eas o l u t i o nt ot h ep r o b l e mo fi n f o r m a t i o np r o c e s s i n ga b o u t c h i n e s ep h r a s e 。i nt h ep r o c e s so fa l g o r i t h m sd e v e l o p m e n t ，t h i sp a p e ra n a l y z e st h e p h r a s em a t c h i n gl o c a t i o n ，t h e o f f s e tv a l u e so fm a t c h i n gl o c a t i o n ，t h el e n g t ho f m a t c h i n gt e x ta n do t h e rf a c t o r s t h e naf u n c t i o no nc h i n e s ep h r a s es i m i l a r i t y c a l c u l a t i o ni sp u tf o r w a r d ，a n di t si m p l e m e n t a t i o np r o c e s si sd e s c r i b e d a r o u n dt h ec a l c u l a t i o no fc h i n e s ep h r a s es i m i l a r i t y ，t h ec o n t r i b u t i o n so ft h i s p a p e ra r e 髂f o l l o w s ： 。 f i r s t l y , s e v e r a lt e x ts i m i l a r i t ya l g o r i t h m sa r er e s e a r c h e d t h ep r e s e n to fp h r a s e s i m i l a r i t ya n dc l a s s i ca l g o r i t h m so np h r a s es i m i l a r i t ya r ea n a l y z e da n di t sa p p l i c a t i o n f i e l d sa n dc h a r a c t e r i s t i c sa r es t u d i e d t h ea p p l i c a t i o ni nt e x tc l u s t e r i n go nt e x t s i m i l a r i t yc a l c u l a t i o na n ds o m et e x tc l u s t e r i n ga l g o r i t h m sa r ei n t r o d u c e d s e c o n d l y , b a s e do na n a l y s i sa n dc o m p a r i s o nw i t hc o m m o n l yu s e da l g o r i t h m so f t h es i m i l a r i t yc a l c u l a t i n g ，an e wc h i n e s ep h r a s es i m i l a r i t yc a l c u l a t i o nm e t h o di sp u t f o r w a r d t h e nt h ea l g o r i t h m s r e a s o n a b i l i t yi st e s t e d b yp u t t i n gd i f f e r e n t t e x t s i m i l a r i t ya l g o r i t h m si nt h es a m ec l u s t e r i n gm e t h o d ，t h ea l g o r i t h m se f f i c i e n c yi s t e s t e d 。 f i n a l l y , t h ea l g o r i t h mo nc h i n e s ep h r a s es i m i l a r i t yi sa p p l i e di nt h em o d u l eo f s i m i l a rc o u r s e sr e t r i e v a la n de l i m i n a t i o no fas c h o o lt r a i n i n gp l a nm i s ，w h i c hr e a l i z e s t h ec l u s t e r i n go fs i m i l a rc o u r s e s a l s o ，t h ee n t i r es y s t e mi sd e s i g n e da n di m p l e m e n t e d t h er e s e a r c ha n di t so u t c o m ew i l lh a v ev a l u a b l er e f e r e n c ea n dg o o da p p l i c a b l e p r o s p e c tt om a n yf i e l d si nc h i n e s ei n f o r m a t i o np r o c e s s i n ge s p e c i a l l yi nt h ep r o b l e mo f c h i n e s ep h r a s ep r o c e s s i n g k e yw o r d s ：i n f o r m a t i o np r o c e s s i n g ；t e x tc l u s t e r i n g ；c h i n e s ep h r a s es i m i l a r i t y ； m a t c h i n go f f s e t ；s i m i l a rc o u r s e sr e t r i e v a la n de l i m i n a t i o n n 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：王蘧湟日期：口髟年 月飞嵋- ，扣 ，) 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打。 ) 作者签名： 王耋啦 导师签名： 日期：口萨广月札日 日期：彤年3 - 月z ，日 1 1 研究背景及意义 第一章绪论 信息大爆炸的不断延续使得信息量成指数级增长，为了能够从这些巨量的信 息中获得所需的信息，就必须对这些信息进行分析和处理。信息技术的发展从某 种程度上表明一个国家乃至整个人类社会的发展程度，若不能充分掌握、利用信 息这一极其重要的资源，无论对个人还是对社会都会造成巨大的损失。没有良好 的信息处理方法，面对浩瀚的信息海洋就无从获得所需信息，就会茫然而不知所 措。为了使信息获得过程更高效、更准确，对信息处理方法的研究十分必要，特 别是对更高效更准确的信息处理算法的研究。 文本信息处理是一门与语言学、计算机科学、心理学、数学、控制论、信息 论、声学、自动化技术等多种学科相联系的边缘交叉性学科。随着科学技术的发 展，文本信息处理技术已被应用到社会生活的各个层面，它涵盖了文本分类、文 本聚类和信息检索等内容。 文本相似度计算是信息处理中一项基础而重要的内容，它被广泛应用于信息 检索、信息压缩、文本分类、文本聚类、机器翻译、自动问答系统等多个领域。 例如，在信息检索中，相似度更多的是反映文本与用户查询在意义上的符合程度； 在文本分类中，相似度用于衡量待分类文本与样本间的相似程度；在文本聚类中， 相似度阀值被用来作为划分类别的界限；在基于实例的机器翻译中，相似度主要 用于衡量文本中词语的可替换程度；在自动问答中，相似度反映的是句子之间语 义上的匹配程度；而在多文档文摘系统中，相似度可以反映出局部主题信息的拟 合程度。可见，文本相似度计算的应用范围相当广泛，对文本相似度计算的研究 具有极其重要的意义。 1 2 中文文本相似度计算的现状 对相似度的概念出现过很多不同的定义，在语义学、哲学和信息理论中都被 广泛的讨论。2 0 0 1 年，d e k a n gl i n 和p a t r i c kp a n t e l 从信息论的角度给出了一个统 一的、与应用领域无关的相似度的非形式化定义。他们认为，a 与b 之间的相似 度一方面与它们的共性相关，共性越多，相似度越高；另一方面与它们的区别相 关，区别越大，相似度越低；当a 与b 完全相同时，相似度达到最大值。 文本的相似度计算研究的是用什么样的方法度量两个文本之间相似程度的问 题，它是自然语言处理、信息检索、文本分类、文本聚类等研究中比较重要的环 节。学术界对相似度的划分大致有两种方法：一是根据相似度在相似算法中的级 别不同，把相似度分为局部相似度和整体相似度；二是根据相似度所体现的知识 l 含量的不同，把相似度大体分为表层的基于句法的相似度和深层的基于语义的相 似度。， 若按计算方法所针对的文本级别划分，文本相似度计算的现状如下： 1 大粒度文本相似度计算 在大粒度文本( 例如篇章、段落等) 的相似度计算上，普遍使用基于向量空 间模型( v e c t o rs p a c em o d e l ，v s m ) 的方法。传统的基于向量空间模型的方法是 由g e r a r ds a l t o n 和m c g i l l 于1 9 6 9 年提出的，它的基本思想是把文档简化为以特 征项的权重为分量的向量表示，通过词频统计和向量降维计算相似度。基于向量 的文本相似度计算方法是最常用的文本相似度计算方法，该方法将要比较的文本 根据文本中的词语将文本映射为n 维空间向量，然后通过比较向量间的关系来确 定文本间的相似度，其中最为常用的方法是计算向量间的余弦系数，但传统向量 空间模型缺点是模型中各词语间相互独立，无语义上的关系。为此，广义向量空 间模型( g e n e r a l i z e dv e c t o rs p a c em o d e l ，g v s m ) 就利用文本而不是用词来表示 词间关系。挪威a g d e r 大学的v l a d i m i ro l e s h c h u k 等人提出基于o n t o l o g y 的文本 相似度比较方法，将本体论引入了文本相似度计算，它能计算文本的语义相似度。 学者c h r i sh q d i n g 采用隐性语义索引模型l s i ( l a t e n ts e m a n t i ci n d e x i n g ) 方法， 先从全部的文档集中生成一个标引项一文档矩阵，该矩阵的每个分量为整数值， 代表某个特定的标引项出现在某个特定文档中次数。然后将该矩阵进行奇异值分 解，较小的奇异值被剔除。结果奇异向量以及奇异值矩阵用于将文档向量和待比 较文本向量映射到一个子空间中，在该空间中，来自标引项一文档矩阵的语义关 系被保留，同时标引项用法的变异被抑制。最后，可以通过标准化的内积计算来 计算向量之间的夹角余弦，根据这个值来比较文本间的相似度。 2 句子相似度计算 对于句子层面，国外对其相似度的研究主要集中在字符串的匹配方面，像最 长公共子序列( l c s ) 算法、1 9 9 8 年的基于编辑距离及其扩展算法的相似串模糊 匹配n ，和同年提出的m c w p a 字符串快速比较算法b ，等。在国内，对于汉语句子的 相似度计算主要是以词语为基本处理单元，通过计算相同词语所占的比重确定句 子之间的相似度，有些方法在此基础上结合了句子的结构信息来计算。1 9 9 8 年穗 志方、俞士汶提出了基于骨架依存树的语句相似度计算模型并用于基于实例的机 器翻译“，：2 0 0 2 年李素建基于知网和：同义词词林，提出了语句相关的定量 计算模型，；2 0 0 3 年，李伟等抽取文本中的关键句以及关键句中的关键词用于文 本相似度计算，吕学强等考虑词形相似度和词序相似度两个因素，提出了句子相 似模型和最相似句子的查找算法 ，秦兵等采用t f i d f 法和基于语义的方法，面 向常问问题集计算问句的相似度，；2 0 0 4 年车万翔等利用改进编辑距离的方法进 行中文相似句子的检索饽，崔桓等在基于网络的问答系统中综合考虑关键词的顺 2 序、关键词之间的距离、以及阕旬和答案长度等信息，用于计算其相似度“帕；2 0 0 5 年金博等在词汇语义相似度的基础上，为不同词性的词赋与不同的权重来综合评 定句子的相似度，。由于目前句子结构分析精度的限制，句子相似度的计算不能 达到很好的效果。 3 组块相似度计算 组块是介于句子秘词语之闻的一种文本缀别，对于组块相似度的研究毙较晚。 由于自然语言具有复杂性和不确定性，所以完全句法分析可望而不可及，面向真 实文本的汉语句法分析在可预期的将来几乎没有实现的可能。因此，浅层句法分 析即组块分析m ，将成为自然语言处理的一个新的发展趋势。组块分析致力于识别 句子中某些结构相对简单、儇有重要意义的成分，不以完整的句法分析作为目标。 组块分析一方面可以为完全旬法分析提供支持，另一方面组块分析本身也可以满 足一些信息基于知网的句子相似度计算的研究处理需求。组块( c h u n k ) 一词 最初在认知心理学中提出，a b e n y 在1 9 9 1 年将组块引入自然语言处理领域。组块 是指文本中一些句法上相关、表达一定概念的块。它在词语和句子之间起到承上 启下的作用，组块分析以及组块相似度计算对文本相似度计算、甚至蠢然语言处 理具有重要意义。目前有两类组块相似度的计算方法，一类是在词语相似度计算 的基础上，借用句子相似度的计算方法计算组块之闻的相似度。文献【5 】中就提出 了词语相似度和相关度的定量计算方法，在此基础上计算句子的相似度，并通过 对组块的中心词语赋予一个较高的权重，用于组块的相似度计算。2 0 0 5 年骆正华、 樊效忠等提出了对语块相似度的计算方法n 莉，这类方法极少考虑不同类型组块的 特点以及构成组块的中心语和修饰语所起的不同作用。由于汉语中不同类型的组 块有不同的特点，组块中的不露词语对整体也具有不同的贡献，因此，句子相似 度计算方法并不适合组块之间的相似度计算。另一种方法是同年由夏天在博士学 位论文孛提出的，该方法根据组块类型的特征为组块孛的中心语和修饰语分配不 同的权重，用两个组块中词相似程度的平均值作为组块的相似度”。这种方法在 计算时考虑了组块的类型，并对组块中的不同成分区别对待，有一定的合理性。 但是该方法要涉及到大量权重的主观指定，如果权重不合理就不能体现该算法的 优越性。此外对组块中心成分和修饰成分的区分也比较困难。 4 词语相似度计算 词语层面的相似度研究已有很长的历史，并且对于汉语词语相似程度的度量 化计算已经产生了一些较有代表性的方法，像字面相似度计算方法、谲素相似度 计算方法，以及最近较为典型的基于语义词舆的计算方法。同时，对于基于统计 的相似度计算，也有学者做了一些尝试。基于字面的相似度计算方法实现比较简 单，不需要其他资源的支撑，但对于词语这种级别的文本来说，文字数量很少， 只通过字面就没法很好的体现同义、近义词语间的相关性。基于语义词典的相似 3 度计算方法从词所表达的概念出发，从语义角度计算词语的相似度，计算结果与 人的主观判断较为接近。然而该方法对语义词典的依赖性较大，语义词典的词汇 量、组织方式、概念的表达方式、更新速度等直接决定了计算的效采。此外，单 纯依靠语义词典无法计算词典中不包含的词( 未登陆词) 的相似度，所以必须考 虑语义词典的扩展问题。基于统计的方法将词汇的上下文信息的概率分布作为词 语语义相似度计算的参照，能够对词汇闻的语义相似性进行比较精确的度量。但 是，这种方法要依赖训练所用的语料库，计算量大，计算方法复杂，丽且基于统 计的词汇相似度计算受数据稀疏和数据噪声的干扰较大。总的来说，目前基于统 计的方法与基于语义词典的方法相比效果还不够理想。国外的词语相似度计算方 法主要包括：基于构成字符的相似度计算方法、基于w o r d n e t 等语义词典的计算 方法、基予词典注释的方法、基于大规模语料库统计的方法和基于搜索引擎的方 法。在这些方法中，基于构成字符的计算方法和基于语义词典的方法与汉语词语 相似度计算中的字面相似度算法和语义词典的方法类似，而后三种方法属于基于 统计的方法。国内近几年也有相关研究成果，如文献【1 5 。l s 】。 i 3 存在的问题及解决方法 随着豆连网的飞速发展和信息传播手段的不断进步，在很多企业和机构积累 了海量的数据中有很大一部分是短文本数据或短语数据，如数据库字段信息、长 文档中的关键词等。对于中文短语信息处理问题，中文短语的相似度计算无疑是 项必要的研究。虽然文本相似度计算问题已经被国内外广大学者研究了很长时 间，到现在已经有很多种文本相似度计算方法产生，并且有些方法取得了很好的 效果，但是这些算法都有它所针对的具体问题、文本级别，都有其适用的领域， 在这个应用中取得良好效果的方法在遇到新的阀题时不一定适用或者效果并不 好。总的来说，现有的文本相似度计算方法用于中文短语的相似度计算存在以下 不足：一是由于短语中文本所体现的关键词非常少，用基于统计的方法对词进行 统计没有意义，并且基于统计的方法预处理工作繁琐；二是基于语义理解的方法 对语义库的依赖性较强，计算效率不高，难以在短时间内对短语文本的相似度计 算得到很大提高。所以这两点决定了用现有的方法来解决中文短语的相似度计算 闯题是不实际的。 中文短语不同予英文字符串，两个英文字符串( 或单词) 之间的相同字符对 于研究两个字符串意思的相似度没有任何意义，但对中文短语间的相似度则有所 不同。因为汉字能比英文字符体现更多的信息含量，两个中文短语若存在相同的 汉字，那么它们的意思就很可能相近，所以，用基于匹配的思想，综合考虑短语 问相匹配文字的位置、匹配位置的偏移值、匹配文字的长度等因素来设计中文短 语的相似度计算方法是合理的，也是可行且有现实意义的。 4 1 4 本文组织结构 第一章阐述了课题的研究背景及意义，分析了中文文本相似度计算的现状： 针对现有文本相似度计算方法在中文短语相似度计算上的不足，提出了解决问题 的着手点；然后对文章结构作了介绍。 第二章研究分析了几种比较经典的中文文本相似度计算方法，阐述了文本相 似度计算在文本聚类中的应用和几种文本聚类算法。 第三章提出了一种新的关于中文短语相似度计算的方法，并给出了算法的实 现，然后对算法的合理性和有效性进行了检验。 第四章主要介绍了高校培养计划管理系统的有关内容和中文短语相似度计算 方法在该系统相似课程排查模块中的应用。 文章最后总结了本文所做的工作，并提出了下一步研究目标。 5 第二章中文文本相似度计算问题分析 中文文本相似度计算是中文信息处理中的基础性问题，对于该问题的研究将 有助于了解当今中文文本相似度计算的现状及发展趋势，也可以发现该技术目前 存在的不足。同时，通过研究其在某领域的应用，可以了解到该技术在信息处理 中的地位和重要性。 2 1 几种中文文本相似度计算方法 本节介绍了几种经典的中文文本相似度计算方法的思想和适用领域，并对其 优缺点进行了阐述。 2 1 1 基于向量空间模型的t f - id f 方法 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 是近年来使用较多且效果较好的 一种信息检索模型。在v s m 中，文档被看作是由相互独立的词条组( t l ，t 2 ，t n ) 构成，对于每一词条t i ，根据其在文档中的重要程度赋以一定的权值w i ，并将 t l ，t 2 ，t n 看成一个n 维坐标系中的坐标轴，w l ，w 2 ，w n 为对应的坐标值。这样 f l 了( t l ，t 2 9 o9 t n ) 分解而得的正交词条矢量组就构成了一个文档向量空间，文档则映 射成为空间中的一个点。对于所有文档和用户查询都可映射到此文本向量空间， 用词条矢量( t n ，w l ，t 2 ，w 2 ，t 。，w n ) 来表示，从而将文档信息的匹配问题转化为向 量空间中的矢量匹配问题。假设用户查询为q ，被检索文档为d ，两者的相似程 度可用向量之间的夹角来度量，夹角越小，说明相似度越高。 t f i d f ( t e r mf r e q u e n c yi n v e r t e dd o c u m e n tf r e q u e n c y ) 方法是被广泛用于文 本相似度计算的基于向量空间模型的计算方法，该方法综合考虑了不同的词在所 有文本中的出现频率( t f 值) 和这个词对不同文本的分辨能力( i d f 值) 。假设所 有文本中包含的词为w l ，w 2 ，w n ，则每一个文本都可以用一个n 维的向量t _ - ( t n ，t 2 9 o*o 9 t n ) 来表示。其中，t i ( 1 i n ) 的计算方法为：设n 为w i 在这个文本中出 现的个数，m 为其它所有文本中含有w i 的文本的个数，m 为文本的总数，那么 t i = n xl o g ( m m ) 。从这个式子中可以看出，出现次数多的词将被赋予较高的n 值， 但这样的词并不一定具有较高的t 值。像汉语中“的 字，出现的频率非常高， 即t f 值( n 值) 很大，但由于“的 在很多文本中都出现，它对于我们分辨各个 文本并没有太大的帮助，它的i d f 值( 1 0 9 ( m m ) ) 将是一个很小的数。因此，这 种方法综合地考虑了一个词的出现频率和这个词对不同文本的分辨能力。用同样 的方法，可以计算目标文本的n 维向量t = ( t l ，t 2 ，t n ) 。得到t 和t 后，它 们所对应的两个文本之间相似度就可以t 和t 这两个向量之间夹角的余弦值来表 示。相似度的计算方法有多种，常用的相似度计算方案有内积法、d i c e 系数法、 6 j a c c a r d 系数法和余弦系数法等。 设文本t = ( t l ，t 2 9 + o - ，t n ) ，t = ( t i ，t 2 ，t n ) ，上述方法计算t 与t 之间相 似度的公式分别是： 内积法 s i m ( t ，丁) = z z ( 2 1 ) j = l d i c e 系数法 2 z 霉。 ，j s i m ( t ，z ) = 了上l - ( 2 2 ) 7 ：2 + z 丘 j a c c a r d 系数法 余弦系数法 s i m ( t ，r ) = n 乃2 + j 3 l s i m ( t ，丁) = z 宰z l = l ( 2 3 ) ( 2 4 ) 基于向量空间模型的t f i d f 的不足之处在于：只有当文本所包含的词语足够 多时采用该方法效果才较好。因为它是一种基于统计的方法，只有当文本包含的 词数较多时，相关的词才会重复出现，这种统计的效果才会体现出来。所以该方 法适用于包含词条数目较多的大粒度文本。 2 1 2 隐性语义索引法。一 隐性语义索引( l a t e n ts e m a n t i ci n d e x i n g ，l s i ) 们作为一种i r 向量空间技术， 被证实比在s a l t o n 的s m a r t 系统中使用的传统向量空间技术性能更好。其原理 是利用矩阵理论中的“奇异值分解 ( s i n g u l a r i t yv a l u ed e c o m p o s i t i o n ，s v d ) 技术。 词频矩阵转化为奇异矩阵：首先从全部的文档集中生成一个标引项一文档矩阵， 该矩阵的每个分量为整数值，它代表某个特定的标引项出现在某个特定文档中的 次数。然后将该矩阵进行奇异值分解，较小的奇异值被剔除。结果奇异向量以及 奇异值矩阵用于将文档向量和查询向量映射到一个子空间，在该空间中，来自标 引项一文档矩阵的语义关系被保留，同时标引项用法的变异被抑制。最后，可以 7 一巧 一 。 一乃 了汹 z 一 一 一拉 通过标准化的内积来计算向量之间的夹角余弦，进而根据计算结果比较文本间的 相似度。下面说明一下l s i 的关键内容： 首先是文档的表示。标引项一文档矩阵x 有t 行d 列，每行表示每个标引项 在文档中的出现情况，每列表示集合中的每个文档。s v dx = t o s o d o 一，结果t o 是一个t x m 矩阵，它的标准正交列称为左奇异向量；s o 是一个m x m 的正奇异值 按降序排序的对角矩阵：d o 是一个d x m 的矩阵，其标准正交列称为右奇异向量； m 为矩阵x 的秩。 l s i 中的关键创新在于只保留s o 中的k 个最大的奇异值，而将其它的值置为0 。 k 的值是设计时的一个参数，其取值通常在1 0 0 至2 0 0 之间。原来的x 矩阵可以 用x 来近似，x = t s d l ，t 是一个含有标准正交列的t x k 矩阵，s 是一个正定的 k x k 对角矩阵，d 是一个含有标准正交列的d x k 矩阵。 第二步是文档的匹配。我们可以将矩阵x 1 看成一个从列向量x a ( 描述某个 单一文档或查询) 到一个内积列向量( 可以用于计算夹角余弦相似度) 的线性函 数。利用s v d 将x t 扩展为x t x q = d o s o t o t x q 。将该式看成由d o s 。i 和毋寸，这两 个线性函数的合成对帮助我们理解很有用。首先考虑s n j 口，该操作将待比较文本 投影到由左奇异向量生成的m 维空间上。本质上，t 0 1 矩阵将t 维文档向量空间中 的文档向量投影到一个m 维的文档特征空间。因为每个奇异值都是正定的，s _ 是 一个真正的对角矩阵。因此s 0 - 矩阵通过分别调节每个特征而在文档特征空间上重 新调节。综合到一起来看，mx t 矩阵s n ”是从文档向量空间到文档特征空间的一 个投影，在投影过程中加入了这样的想法，在估计文档相似性时，一些特征比另 一些特征更重要。一旦文档特征向量可用，d x m 矩阵d 。s 。i 可以用来计算我们想要 的内积。具体地，可以计算文档向量空间中的m 维向量”x 和d 。s o 一2 的每一行向 量之间的内积。d o s 。i 的每行可以解释成被投影到文档特征空间且与x q 一样重新调 整的文档向量。 l s i 引入的唯一变化就是从s o 中剔除小奇异值，因为与小奇异值相关联的特 征实际上在计算相似度时并不相关，将它们包括进来将降低相关性判断的精确度。 保留下来的特征是那些对文档向量在m 维空间中的位置有较大影响的特征。剔除 小的奇异值将文档特征空间变为文档概念空间。剔除小的奇异值将s v d 变为x = t s d l ，然后可以计算文档的内积向量x ”x 。：d s t 。x 口，概念向量之间使用内积的 夹角余弦计算相似度的方法比原来基于源文本向量的相似度计算方法更可靠，这 也是使用l s i 方法的主要原因。 l s i 的缺点在于它的效果依赖于上下文信息，过于稀疏的语料不能很好的体现 其潜在的语义，所以该方法适用于上下文联系紧密的较长文本。 2 1 3 基于属性论的文本相似度计算方法 属性论方法是冯嘉礼教授在人工智能领域独创的方法，其理论在垃圾邮件过 8 滤、网络入侵检测、股票预测、智能组卷等方面都有成功的应用k 一”。 1 属性论介绍 属性论是以神经科学的实验结果为基础，从哲学和逻辑学的基本原理出发， 以人类认识的心理过程为基础，以先进的数学理论范畴论为工具，充分利用人工 智能、思维科学、认知科学及计算机科学的有关结论来构建一个既能适应人类思 维的数值化需要，又能适应人类的非数值化需要的数学模型。属性论是建立在既 有的事实基础上的一门理论，这些事实主要有以下几点： ( 1 ) 任何事物都是以其自身的属性反映其本身； ( 2 ) 事物的属性是由感觉神经元有选择地进行分门别类检测和编码的： ( 3 ) 事物的复杂属性是被分解为简单属性的组合以后才被相应检测单元所检 测和编码的； ( 4 ) 事物诸属性是被整合后而被知觉和记忆贮存的； ( 5 ) 事物某整合属性的部分诱发，可导致该整合属性的整体诱发。 2 属性重心剖分模型 - ， 定义1 设事物m ( x ) 、n ( x ) 分别表示事物x 的不同属性，用八表示合取算子， 则用m ( x ) a n ( x ) 表示属性的合取过程，令s ( x ) = m ( x ) 八n ( x ) ，则称s ( x ) 为合属 性，而m ( x ) 和n ( x ) 称为素属性，我们也以合属性代表事物x 。 设事物x 的属性集p ( x ) = e o ( x ) ，e l ( x ) ，e n ( x ) ) ，则有如下的定义： 定义2 设n 维单纯形k = ( e o ，e l ，e n ) ，其顶点为属性集p x 中的第n + 1 个属性 e j ( x ) ，则k 为属性多面体。在k 的第一次重心剖分k ( 1 ) 中，r + 1 个属性的整合属性 e i o 八e i l 八八e i ，置放在由这r + 1 个属性所构成的维单纯形的重心剖分点上，记为 p ( s i ，) ，且p ( s i ，) = e i o 八e i l 八e i ，。依次类推，这样的模型称之为属性重心剖分模型。 设事物p ( x ) - - ( t l ，t 2 ，t 3 ) ，其中t l 、t 2 、t 3 为p ( x ) 的素属性，则用属性重心剖 分模型可表示如图2 1 所示幢】 记 e o at l 图2 1 属性重心剖分模型 其中t l 、t 2 、t 3 构成了属性坐标系的三个坐标轴，三角形aa b c 的重心代表 了事物p ( x ) 。 3 属性重心剖分模型在文本相似度计算中的应用 9 设文本d 中共使用了m 个标引词，这m 个标引词记为t l ，t 2 ，t m 。表示为： d = ( tn ，t 2 ，t m ) ，用户的每一次查询文本q 可用等长的向量表示，即：q = ( t i ，t 2 ，t m ) 。令w i ，w 2 ，w m 分别为标引词t l ，t 2 ，t m 的权重，权重的大小反映 了该词在文本中的重要程度，其取值范围为【o ，l 】，值越大说明该词越能够代表文 本的内容，反之，越不能代表文本内容。这样，文本及用户给出的查询式可分别 表示如下： d = ( 。，：，) q - ( w , ，z ，) 其中，w d l w d 2 ，w d m 分别为词t l ，t 2 ，t m 在文本d 中的权重， w q l ，w q 2 ，- - - , w q m 分别为用户给出词t ! , t 2 ，t m 的权重。 定义3 文本向量d = ( w o , ，w d 2 ，w d m ) 所确定的多面体的重心称为文本重心， 表示为g d = ( g a l l ，g d 2 ，g d m ) = ( w d l m ，w d 2 m ，w d m m ) 。 定义4 查询式向量q = ( w q l ，w q 2 ，w q m ) 按重心坐标的置放法则加到属性重，f i , 坐标系中，得到查询式向量所构成的多面体的重心点，我们称之为查询重心 g q 2 ( 踟i ，g q 2 ，g q m ) 5 ( w qt m ，w q 2 m ，w q m m ) 。 。 在同一属性坐标系中，作出文本d 与查询q 的属性坐标表示，如图2 2 所示。 b b o a ? at 1 j 。 图2 2 文本在属性坐标系中的表示 连结查询重心g q 与坐标原点o 之间的连接线o o 。称为查询重心线，查询重 心线交aa b c 于点m ，则距离r ( g q ，m ) 可以用来衡量文本d 与用户查询q 之间的 相似度大小，距离越大，则相似度越小；距离越小，则相似度越大，即距离r ( g q ，m ) 是与相似度成反比。匹配函数f 用来表示相似度的大小。根据上述分析，匹配函 数应具备以下几个条件： ( 1 ) 当文本d 与查询式q 完全匹配时，距离r ( g 。，m ) 为0 ，f 为1 ； ( 2 ) 当文本d 与查询式q 完全无关时，距离r ( g 。，m ) 为l ，f 为0 ； ( 3 ) 当文本d 与查询式q 有关时，f 取值区间为( o ，1 ) 。 从对属性重心剖分模型的定义及构造方法来看，属性论方法能较准确、较全 面的反映文本的内容，因此在计算两文本相似度的精确度上有较好的效果。同时， 1 0 文本属性重心剖分模型还能通过坐标点与坐标点之间的距离计算关键词与关键词 的相关性，通过坐标点与单纯形的关系计算关键词与文本的相关度，通过单纯形 与单纯形的关系计算文本与文本的相似性，因此，利用文本属性重心剖分模型能 表达较多的语义信息，它为相似度的处理方法提供了另一种可能。该方法被提出 后被应用到了多个领域，像垃圾邮件过滤系统、网络入侵检测系统、0 1 背包问题、 高考招生模型等等。 一 2 1 4 基于汉明距离的文本相似度计算方法 基于汉明距离的文本相似度计算方法是2 0 0 1 年由张焕炯、王国胜等人提出的 n ”。汉明距离是信息论中的一个基本概念，它描述了两个n 长码子x = ( x l x 2 x k x a ) 与y = ( y l y 2 y k y 。) 之间的距离，其计算方法如公式( 2 5 ) 所示： l d ( 毛y ) = & o 儿 ( 2 5 ) k = l 其中，o 表示模2 加运算，x k o ，l ，y k e o ，1 ) 。d ( x ，y ) 表示两码字在相同 位置上不同码符号的数目的总和，它能够反映两码字之间的差异，可作为提供码 字之间的相似程度的客观依据。该方法将文本中的关键词、文摘等信息排列成一 个有n 位序列的码字，文本信息就用这些码字表示，使文本与码字建立1 1 对应 的关系。同样，查询式也用码字表示。比如文本w l ，它可以表示成 w l = ( 1 0 0 ll1 0 0 0 1 0 1 0 0 0 1 ) ，查询式c 表示为c = ( o l0 0 1l0 0 0 1l1 0 10 1 0 o ) 。这里的0 和1 分别表示相对应的文本信息的状态，0 表示文本在这个分量位置上的信息是 没有的，1 表示文本在这一分量位置上的信息是有的，反之也可以类似规定。因此 对于原来的文本集合，它可以1 1 对应于码字的集合，研究文本集合中的文本的 相似关系，就用码字之间的汉明距离来表示。具体地，若设文本w l 对应的码字为 m l ，查询式对应的码字为m 2 ，则这两码字之间的距离可用公式( 2 5 ) 计算。对 于d ( m l ，m 2 ) 来说，它们之间的距离介于0 和n 之间，当文本与查询式用n 位码字 表示完全不同时，距离为n ，当文本与查询式码字完全相同时，距离为o ，它定量 的描述了文本之间的差异程度。 以该理论为基础进行相似度计算时，可先确定文本集对应的码字集，对于不 同的文本或文本与查询式之间，设m l = ( x l x 2 x 3 x k x n ) ，m 2 = ( y l y 2 y 3 y k y n ) ，那 么基于汉明距离的相似度计算如公式( 2 6 ) 所示： l s i m ( m t ，m 2 ) = 1 一o 儿 ( 2 6 ) 其中x k 、y k 分别表示文本w i 对应的码字m l 和查询式w 2 对应的码字m 2 中第 k 位的分量，或者为0 或者为l ，o 就是模2 加运算。计算机来进行模2 加运算非 常方便，可以达到极快的速度。 l l 用公式( 2 6 ) 刻溺文本相似度是合理的。 首先，它的计算结果介于o 与1 之间，当两个文本完全相似时，s i m ( m i ，m 2 ) 的值为l ，当两个文本完全不相似时值为0 ，它确实反映了文本之间的差异，而且 也与传统的欧氏空间中求向量夹角余弦的方法相一致。例如，设文本集霜对应的 码字集为觑，码长l o 位，即n = 1 0 ，那么其中的文本w l 对应的码字为m l 燃 ( 1 0 0 1 1 0 0 0 1 0 ) ，文本w 2 对应的码字为m 2 - - ( 1 1 0 0 1 1 0 0 1 ) ，那么由公式( 2 6 ) 计算 得到文本w l 与w 2 之间的相似度为s i m ( m l ，m 2 ) = 1 - 0 6 = 0 4 。这说明这两个文本之 间的相似程度为0 4 ，也就是说，它们其中的4 个位置上的信息是一致的，相似度 函数定量描述了文本之间的差异性。与其它的文本相似度计算公式相比较，因该 方法只是利用模2 加等运算，其方便性是不言丽喻的，它完全避开了诸如在欧氏 空间中求相似度的大量乘法运算，因此，可大大地提高速度。 其次，它跳出了传统的借用空间的理念，丽是用码字的方法来表征文本信息 的特征，可以不仅限于关键字等孤立的信息，这为联合的描述文本的信息提供了 可能。 但是，从对文本处理到计算完成所用的时闻来看，该方法并没有表面所显示 的那么方便快捷，因为该方法在提取文本码字和将文本与码字集合对应时的工作 量比较大，从某种意义上说用予大数据集文本分类、聚类工作比较繁琐，效率并 不高。 2 。1 。5 基于压缩稀疏矩阵矢量