（计算机应用技术专业论文）基于潜在语义索引的中文文本检索研究.pdf

西南交通大学硕士学位论文第l 页 摘要 互联网上绝大多数的信息是以文本的形式保存的，文本信息的爆炸式增 长给信息检索技术带来了巨大的挑战，人们越来越难以快速准确地从网上检 索到相关信息。在目前使用最多的基于关键词的字符匹配检索中，参与匹配 的只有词的外在形式，而日常语言中多词同义、一词多义等不确定性因素的 存在，使得用户很难简单地用关键词或关键词串来真实地表达真正需要检索 的内容。 而潜在语义索引( l s i l a t e n ts e m a n t i ci n d e x i n g ) 模型的出现有效地克服 基于关键词检索无法处理多义词和同义词问题，它具有可计算性强、需要人 参与少等优点。l s i 通过截断的奇异值分解建立潜在语义空间，词汇和文本都 被投影在该空间，进而可以提取词汇间深层次的语义关系，从而呈现出自然 语言中的语义结构，进一步提高了检索性能。 本文围绕着如何利用l s i 技术及其特点进一步提高中文文本检索的性能 展开讨论。首先对l s i 的相关关键技术以及数学基础进行了深度挖掘，对其 在中文文本中的应用进行了举例和深入分析。其次对l s i 的重要优化过程一 一权重计算进行了深入分析，提出了一种基于“非线性函数”和“位置因子 的新权重方案，并对其效果进行了对比验证。然后利用l s i 能够方便计算出 文本和文本相似度的特点，提出了“文本一文本检索 功能，弥补了由于检 索语句较短和输入不准确等问题对检索查准率的影响，能够更好的帮助用户 进行更加有效的检索。最后，开发了“中文潜在语义索引分析系统”作为实 验平台，针对l s i 的每个相对独立的环节专门设计实验方法，以可视化的方 式呈现实验结果，文中所有研究内容都在该系统中作了验证。 关键词：信息检索；潜在语义索引；权重计算；文本一文本检索 西南交通大学硕士学位论文第1 i 页 a bs t r a c t m o s ti n f o r m a t i o no ni n t e r n e ti sb a s e do nt e x t t h ee x p l o s i v eg r o w t ho ft e x t i n f o r m a t i o ni sag r e a tc h a l l e n g et oi n f o r m a t i o nr e t r i e v a l ，m a k i n gi ti n c r e a s i n g l y d i f f i c u l tt of i n du s e f u li n f o r m a t i o no ni n t e r n e tr a p i d l ya n da c c u r a t e l y i nt h em o s t u s e di n f o r m a t i o nr e t r i e v a lb a s e do nk e y w o r d sm a t c h ，w h a tm a t c hi st h ee x p l i c i t r e p r e s e n t a t i o n ，b u tt h e r ee x i s t su n c e r t a i n t yi nn a t u r a ll a n g u a g e s ，s u c ha ss y n o n y m a n dp o l y s e m y i ti sn o te a s yf o ru s e r st o e x p r e s sw h a tt h e yr e a l l yw a n tt or e t r i e v e j u s tw i t hk e y w o r d so rk e y w o r dc h a i n s l a t e n ts e m a n t i ci n d e x i n gm o d e li se a s yt oc a l c u l a t ea n dr e q u i r e sl e s sh u m a n i n t e r v e n t i o n l a t e n ts e m a n t i cs p a c ei se s t a b l i s h e db yt r u n c a t e ds i n g u l a rv a l u e d e c o m p o s i t i o n ，t e r m sa n dd o c u m e n t sa r ep r o j e c t e do n t ot h el s i s p a c e t h e nt h e s e m a n t i c r e l a t i o n s h i p sa m o n gt e r m sa r e a b s t r a c t e dt o p r e s e n tt h es e m a n t i c s t r u c t u r eo fn a t u r a ll a n g u a g e s ，i ti m p r o v e st h er e t r i e v ep e r f o r m a n c e t h et h e s i sf o c u s e so nh o wt o i m p r o v et h ec h i n e s et e x ti n f o r m a t i o nr e t r i e v a l s y s t e mp e r f o r m a n c eb a s e do nl s ia n di t sf e a t u r e s f i r s t l y , t h ek e yt e c h n o l o g ya n d m a t h e m a t i c a lb a s i so fl s lw e r ea n a l y z e d d e e p l y e x a m p l e sw e r eg i v e n a n d a n a l y z e dw h i c ha i m e da tc h i n e s et e x tr e t r i e v a l s e c o n d l y , t h et e r mw e i g h t i n g w h i c hi so fg r e a ti m p o r t a n c ei nl s ii ss t u d i e di nd e t a i l ，a n dan e ww e i g h t i n g d e s i g nb a s e do nn o n l i n e a rf u n c t i o na n dl o c a t i o nf a c t o rw a sp r o p o s e d t h e r e t r i e v a lp e r f o r m a n c eh a sb e e ni m p r o v e df u r t h e r u s i n gt h ec o n c e p tt h a tt h el s i s p a c ec a nc a l c u l a t et h er e l a t i o na m o n g d o c u m e n t sc o n v e n i e n t l y , “d o c - d o cr e t r i e v a l ”i sp u tf o r w a r dt om a k eu e r s r e t r i e v a l m o r ee f f e c t i v e l y i to f f s e t st h ee f f e c t st h a tt h er e t r i e v a ls e n t e n c e sa n di n p u t i n a c c u r a t e l ya f f e c t s t h er e t r i e v a lp r e c i s i o n a tl a s t ，a ne x p e r i m e n t a lp l a t f o r m ， n a m e l y c h i n e s el s ia n a l y s i ss y s t e m ”，h a sb e e nd e v e l o p e d i nt h i ss y s t e m ，e a c h v i t a ll i n ki nl s ii sc o r r e s p o n dt os p e c i a le x p e r i m e n t a lm e t h o d ，a n dp r e s e n t st h e r e s u l tv i s u a l l y a l la s p e c t si nt h ed i s s e r t a t i o na r ee v i d e n c e dw i t he x p e r i m e n t so n t h i ss y s t e m k e y w o r d s ：i n f o r m a t i o nr e t r i e v a l ；l a t e n ts e m a n t i ci n d e x i n g ； t e r mw e i g h t i n g ；d o c d o cr e t r i e v a 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将 本论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密d 使用本授权书。 ( 请在以上方框内打“”) 学位论文作者签名身舷媛 日期： ? ，p 指导老师签名：易乱) 磅 日期：刚f 多i 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进 行研究工作所得的成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的研究成果。对本 文的研究做出贡献的个人和集体，均已在文中作了明确的说明。 本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 根据大量分析，提出了一种基于“非线性函数和“位置因 子 的权重方案。 2 刑用l s i 能够方便计算出文本和文本相似度的特点，提出 了“文本一文本检索功能。 3 独立开发了“中文潜在语义索引分析系统作为实验平台。 西南交通大学硕士学位论文第1 页 第1 章绪论 1 1 信息检索综述 1 1 1 信息检索的发展 信息检索作为一项行为已有很长的历史，我国古代西汉时期的古文经学 家、目录学家刘歆撰写了我国第一部系统目录七略，但作为一个学科来发 展始于2 0 世纪4 0 年代末。1 9 4 9 年美国数学家年c a l v i nw m o o e r s 首次提出 了“信息检索”这个概念1 。 所谓信息检索是指在对信息进行表示、存储、组织和存取的基础上，用 户为处理解决各种问题而查找、识别、获取相关事实、数据、文献的活动及 过程。简单来说就是根据用户的信息需求，从文本集中检索出与用户信息需 求相关的文本子集。信息检索系统由信息组织和信息检索两大部分组成，信 息检索性能的提高需要良好的信息组织。根据这一概念可得出较为狭义的信 息检索定义，即：从大量收集的数据或文本集中，找到与给定的查询请求相 关的恰当数目的数据或文本子集。 信息检索是随着科学技术的发展和信息数量的成倍增长而发展起来的研 究与应用领域。随着人类信息生产的能力超过了人力对信息的处理、组织和 吸收能力，信息检索的战略地位亦日益重要。纵观信息检索的发展，经历了 三个大阶段：手工信息检索、机械信息检索和计算机信息检索。其中计算机 信息检索出现最晚，但发展最为迅速。计算机信息检索起源于2 0 世纪5 0 年 代初。1 9 5 4 年美国海军兵器中心图书馆i b m 7 0 1 机开发计算机信息检索系统， 它标志着计算机信息检索阶段的开始。 而纵观计算机信息检索系统的发展，可以将其发展过程划分为三个阶段。 第一阶段：1 9 7 1 年以前建立的许多信息检索系统，其工作方式是传统的 批处理检索方式，这一阶段的数据存取与数据通信能力都比较差。 第二阶段：1 9 7 1 年以后，产生并发展了联机情报检索系统。如o c l c ， d i a l o g 在线数据库联机检索系统。这一阶段的特点是联机数据库集中管理， 具有完备的数据库联机检索功能，但其数据通信能力较差。 第三阶段：以i n t e m e t 的出现为标志，系统大多采用分布式的网络化管理， 其信息资源的主要特点是：数字形式表达，多媒体和多载体，内容覆盖全社 会领域，分布无序，难以规范化和结构化，内容特征抽取复杂，用户界面要 西南交通大学硕士学位论文第2 页 求高。这些特点导致了信息处理从传统模式想新型模式的转变，如：信息结 构从结构化到非结构化，体系结构从终端主机方式到客户服务器结构方式， 网络环境从局域网到i n t e m e t 等开放网络等。这些变化必将促进信息检索技术 的研究和不断发展，以满足人们对提高信息利用能力的需要。 经过近几十年的发展，计算机信息检索算法得到了充分的发展，从小规 模文献检索到大规模的w e b 信息检索，从实验室到图书馆到大规模的商业应 用，检索质量也同时不断提高，很多大型的商业搜索引擎已经能够较好的满 足用户的需求，实验室中的信息检索理论研究也在不断的进步。 1 1 2 信息检索的基本定义 个基本的检索系统应该包含如图1 1 所示的5 部分： 图1 1 信息检索系统简图 任何学科都离不开最基本的定义和定理。信息检索领域也是如此，这些 基本定义是开展研究的基础，下面就根据“信息检索系统简图对信息检索 中的基本定义p 1 进行简要介绍： 文本( d o c u m e n t ) ：信息检索系统被检索的对象。它是最简洁，最抽象的 人类记载知识的最重要工具。在信息检索领域，文本往往是无结构的，也即 是自然语言生成的文字，而不是像数据库中的结构化数据。 查询向量( q u e r ys t r i n g ) ：信息检索系统据以检索的对象。查询由用户生 成，往往也是自然语言描述的用户信息需求。除了布尔模型之外的其他检索 模型，往往把查询看成一个文本，检索的过程就是找到与查询文本最相关文 本的过程。 文本集( d o c u m e n tc o r p u s ) ：一定数目文本的集合。数据集对信息检索 西南交通大学硕士学位论文第3 页 有特别的意义，检索必须在一个有限的集合内进行。 相关度( s i m i l a r i t y ) ：文本与查询相关程度的表示。相关度是文本满足用 户需求的性质，是一个很难准确定义的概念。对相同的文本，不同的人会有 不同的相关度的判断，即使是相同的人，在不同的时期，也会有不同的判断。 不同的信息检索模型都会提出自己的相关度定义。 排序( r a n k ) ：检索结果往往是一个文本的列表，对大部分检索模型来说， 这个列表是经过相关度排序的，相关度高的文本最先呈现给用户。 1 2 信息检索模型 本节讨论近年来提出的集中最重要的检索模型，其中包括布尔模型，向 量空间模型和概率模型。 布尔检索模型( b o o l e a nm o d e l ) 是最早也是最成熟的检索模型，在传统 的信息检索中有着广泛的应用。它将文本表示成布尔表达式，然后再通过与 用户的查询表达式进行逻辑比较来检索相关文本。标准布尔逻辑模型是二元 逻辑。在布尔模型中，首先要针对文本定义一系列的二元特征变量，这些特 征变量一般是从文本中提取出来的文本索引关键词，有时也包括一些更为复 杂的特征变量，如数据、短语、私人签名和手工加入的描述词等。其次，使 用这些特征变量的集合来表示文本“d i = ( d d ，d ，。) ”，其中，m 是特征 项的个数；d 小为t r u e 或f a l s e ，如果特征项k 在文本d i 内容中出现，就赋予 t r u e 值，反之置为f a l s e 。 在布尔模型中，用户可以根据检索关键词在文本中的布尔逻辑关系，用 “”k ”( a n d ) ，”v ”( d 固，”1 i ( n o t ) ”等逻辑运算符将多个特征词连接成为一个逻 辑表达式来递交查询。匹配函数由布尔逻辑的基本法则确定，通过对文本表 达式与用户查询表达式的逻辑比较进行检索，所检索出的文本或者与查询相 关，或者与查询无关。其检索策略依赖于一个倒排文件，用于指出哪些文本 描述与布尔表达式准确匹配，一个文本当且仅当它能够满足布尔查询式时， 也即：完全匹配时才能将其检索出来。传统的布尔检索模型中没有相关度的 概念，因此不能按照相关度排序输出，后来w a l l e r 等人提出了加权的布尔检 索模型，初步具备了相关度的概念。 到目前为止，布尔模型是最常用的检索模型，因为：由于查询简单，因 此容易理解。通过使用复杂的布尔表达式，可以很方便地控制查询结果。而 且经过某种训练的用户可以容易地写出布尔查询式。但同时，布尔模型被认 西南交通大学硕士学位论文第4 页 为是功能最弱的方式，它很难表示用户复杂的需求，很难控制被检索的文本 数量，很难对输出进行排序，也很难进行自动的相关反馈。 向量空间模型( v e c t o rs p a c em o d e l ) 是上个世纪s a l t o n 等五位学者提出 的一种基于统计的检索模型。假设文档集包含m 个词汇，1 1 个文本，v s m 把 每个词汇看作一个向量，这些词汇被认为是互不相关，然后根据词汇在文本 中的不同的重要程度进行加权，则由这m 个词汇所对应的向量可以生成一个 n 维空间，文本集中的任一文本可被表示为这m 个词汇的向量( 中间大量为 o ) 。同样查询也可被表示为一个m 维的向量，用m 行1 1 列的词汇一文本矩阵 进行直观表示，行向量是词汇向量，列向量是文档向量，这样查询和文档间 的匹配问题就转化为一个向量空间中( 也即：词汇一文本矩阵) 的距离计算 问题，因此，v s m 有了真正的相似度的概念。著名的瓜系统s m a r t 就是一 个v s m 的典型实例。 向量空间模型的优点主要有以下三点：( 1 ) 对词汇进行加权的算法提高了 检索的性能。( 2 ) 部分匹配的策略使得检索的结果文本集更接近用户的检索需 求，克服了布尔模型的缺点。( 3 ) 可以根据文本对于查询串的相似度，通过 c o s i n er a n k i n g 等公式对结果文本进行排序。它简单、快捷，计算复杂性小， 便于处理，且更为直观易懂的特性，受到了广泛的应用。 概率检索模型( p r o b a b i l i s t i cm o d e l ) 则是为了解决检索中存在的一些不 确定性而发展起来的，以数学理论中的概率论为原理的一种检索模型。在此 模型中，文本和用户查询的表示与布尔模型相同。它的基本思想是：对于某 个特定查询，某一文本是否为相关文本可看作一个随机事件。根据先前检索 过程中得到的相关性的先验信息，计算文本集合中每篇文本成为相关文本的 概率，然后根据b a y e s 决策准则决定输出标准，确定哪些文本作为命中文本 输出。 概率检索模型的优点在于它采用严格的数学理论，能够按照相关度概率 对检索结果进行排序，表示和应用较为精确和完善，检索效率要明显优于布 尔模型。缺点在于需要根据用户的相关反馈把文本分为相关和不相关的两个 集合，一般来说很难。 上述几种检索模型中应用最广泛的是布尔检索模型和向量空间模型，其 核心仍然是特征词的机械匹配。参与匹配的只有外在的字符表现形式，没有 考虑词之间的相关性，无法分辨自然语言的语义模糊性，同时忽视了上下文 语境地限制，仅以孤立的关键词来表示文本的内容，因而在很大程度上影响 了信息检索的查准率和查全率。 西南交通大学硕士学位论文第5 页 一方面，不同的查询者，其检索目的、知识背景、语言习惯之间的差异， 会导致他们对同一概念用不同词汇来表达。有国外学者研究发现，词汇运用 的不确定性远远超乎想象，以西文表达为例，两人用相同词汇表达一个人们 熟悉的概念的概率小于2 0 ，这一因素大大降低了检索系统的查全率。例如： “发动机 和“马达”所指为同一事物p 1 ，但由于使用习惯的不同，出现在 不同的文档中。在基于关键词匹配的检索系统中，仅输入“发动机”作为查 询，那些只包含“马达的文本由于不符合匹配的要求不会出现在检索结果 中。另一方面，单个词汇的歧义性表现为一个词汇在不同的语言环境下，或 被不同的人使用，则可能代表不同的含义。因此，仅仅判断文本中是否包含 与提问词“形态”一致的词汇，检出的文本很可能是不准确的，词汇的歧义 现象是影响查准率的潜在因素。 同时还存在，虽然相关文本不一定包含检索词及其同义词，但是内容符 合检索要求。例如：检索词为“电磁感应 ，文本集中包含如下文本“变化着 的电场能产生磁场，变化着的磁场也能产生电场。”，尽管该文本不包含“电 磁感应 一词及其同义词，但是这个文本内容仍然是阐述电磁感应的现象， 因此是“电磁感应”的相关文本。 为了解决以上问题，研究者想出了各种各样的办法，比如：h o w n e t p l ， o n t o l o g y p l 的提出，但归根结底，这些方法采取的大都是将查询信息的概念 通过概念词典或概念网络扩展和联想，得到其相关内涵。但由于概念词典或 概念网络目前仍然需要大量的人工参与，并且可计算性不高等的局限，发展 缓慢。 那么能否找到一种能够自动获取词汇间的语义关系，将词汇和文本以某 种可计算性和可操作性高、某种程度上代表其内在语义的形式表示和存储， 对未来的检索意义重大。潜在语义分析就是这样一种具有以上特点、可用于 信息检索的自然语言统计模型。 1 3 潜在语义索引 1 3 1 潜在语义索引综述 19 88 年，来自b e l lc o m m u n i c a t i o n sr e s e a r c h 、u n i v e r s i t yo fc h i c a g o 和 u n i v e r s i t yo fw e s t e r no n t a r i o 的s u s a nt d u m a i s 、t h o m a sk l a n d a u e r 、s c o t t d e e r w e s t e r 等五位学者共同提出了潜在语义索引( l a t e n ts e m a n t i ci n d e x i n g ， 缩写为l s i ) 这一自然语言处理的方法。也被称为潜在语义分析( l a t e n t 西南交通大学硕士学位论文第6 页 s e m a n t i ca n a l y s i s ，缩写为l s a ) ，本文采用第一种称法。 潜在语义索引的出发点是假设文本中的词汇与词汇之间存在某种联系， 即存在某种潜在的语义结构，这种潜在的语义结构隐含在文本中词汇的上下 文中。在这种结构中，同义词之间具有基本相同的语义结构，多义词必定具 有不同的语义结构。并且采用统计计算的方法，即可对大量的文本进行分析 来寻找这种潜在的语义结构，不需要确定的语义编码，仅依赖于上下文中事 物的联系。用语义结构来表示词汇和文本，达到消除词汇之间的相关性，简 化文本向量的目的。 1 3 2 潜在语义索引的研究概述瞪1 l s i 一经诞生就引起各语种国家学者的广泛注意，在文本检索、文档聚类 分类、信息过滤、信息抽取、自动问答系统、认知科学，数据挖掘等领域得 到了广泛应用，在国外l s i 已逐渐步入商业应用阶段。 在国外研究方面，尤其是针对文本的检索，很具有启发和借鉴意义。得 克萨斯大学的t o d da l e t s c h e 一1 等人比较了向量空间模型和潜在语义分析， 研究了l s i 在大规模文本信息检索中的应用技术。d i a ni w i t t e r 等人提出的 潜在语义空间更新的算法，用于快速计算添加文本或词汇后的近似潜在语义 空间，具有很重要的实用价值。索非亚大学的p r e s l a v n a k o v 比较系统地对比 了潜在语义分析各种权重计算方法下的效果。英国爱丁堡大学的学者p e t e r 则探讨了如何将句法分析引入l s i 中，寻求一种能使l s i 处理那些存在于句 法当中的文本信息的方法。除了截断的奇异值分解之外，还有一些学者研究 了通过其它计算获得潜在语义空间的方法。 潜在语义分析在其它领域重要的应用有：科罗拉多大学的t h o m a s k l a n d a u e r 和他的k a t 团队开发的i n t e l l i g e n te s s a ya s s e s s o r 是l s i 的典 型应用之一，被d i s c o v e r 杂志评价为一个“创新性的进步”。u n i v e r s i t yo f m e m p h i s 智能系统研究所的a r t h u rg r a e s s e r 等人开发的智能辅导系统 a u t o t u t o r p l ，能帮助学生在自然语言交谈和激励下学习某一学科。t e l c o r d i a 公司开发的“t e l c o d i al s ie n g i n e 是潜在语义分析r 模型的一个实验系统， 其中提出的快速检索算法值得借鉴。另外，有报道称，g o o g l e 也正在研究如 何采用l s i 技术，作为搜索引擎和广告服务的算法。 而国内对于潜在语义索引的研究起步相对较晚，其中哈尔滨工业大学、 东北大学、中科院等很多研究单位的相关实验室在这方面做了大量的研究工 西南交通大学硕士学位论文第7 页 作，打下了坚实的基础。 同时，一些研究者对l s i 的研究也提出了自己很好的见解，比如：南京 大学的盖杰p 1 、同济大学的顾榕w 等人分别研究了潜在语义分析在信息检索 中的应用：西安交通大学的何明u “、广西师范大学的黄海英纠等人分别研究 了潜在语义分析在文本分类中的应用。南京理工大学的戚涌纠则研究了潜在 语义分析在w 曲文本自动聚类：尤其是针对特征词权重的设计方面，山西大 学的郑家恒叫等人提出的“成对比较法 ，上海交通大学的韩客松刘等人提 出的“义长”概念，解放军理工大学的刘海峰u 刚等人的把“位置因子作为 特征词加权系数的讨论，对作者在特征词权重方面的设计提供了很有益的思 路。在商业应用上，l s i 已经被应用在国内最有影响的i n t e m e t 化学化工资源 导航站点c h i n u 中，同时取得了比较理想的检索效果。 1 4 本文的研究意义 我国的语言学家对汉字熵的测算p 1 结果为9 6 5 比特，而英文是4 0 3 比特， 法文是3 9 8 比特，一般认为汉字的信息量最大，因而在信息管理和传递中， 中文处于很不利的地位。针对中文信息的一些特点，探索针对中文的检索就 显得非常有必要。 同时，基于潜在语义索引的检索已经被证明是对传统的向量空间技术的 一种改良，可以达到消除词之间相关性，化简文档向量的目的。用潜在语义 索引进行检索，不是基于文档集中表层的词汇信息而是潜在语义结构，其性 能比关键字匹配方法要高出许多。 因此，研究如何利用潜在语义索引技术进行中文文本检索的研究就具有 很重要的实际意义和应用价值。 1 5 论文结构 论文共分六章，按以下方式组织： 第一章绪论，介绍了信息检索的相关模型、重点介绍了潜在语义索引以 及其研究现状和研究意义，并说明了论文结构。 第二章l s i 的基本理论，介绍了l s i 的基本思想、奇异值分解、l s i 的数 学依据和特点，以及文本和词汇的扩充等l s i 的相关基本理论。 第三章中文潜在语义索引的处理，对l s i 在中文样本上进行了实例分析、 介绍了中文l s i 的处理步骤，中文l s i 的特点以及性能评价方法。 西南交通大学硕士学位论文第8 页 第四章潜在语义索引的权重改进，对目前常用的特征词权重设计方案进 行了介绍，针对t f i d f 所存在的不足，提出了一种基于“非线性函数”和“位 置因子”的新权重方案，并对其进行了深入分析。 第五章中文潜在语义索引分析系统的开发，设计开发了用于验证l s i 相 关理论和新权重公式对l s i 的影响的测试系统，对总体设计、各模块功能进 行了详细介绍。 第六章中文潜在语义索引分析系统的测试，从新权重在特征词选择方面 的性能，以及对基于l s i 的系统性能的影响进行了测试分析。 最后对论文的工作进行了总结，并指出了潜在语义索引的研究发展方向。 1 6 本章小结 本章首先对信息检索的发展，信息检索的基本定义和传统模型进行了描 述，然后对本文研究的信息检索模型潜在语义索引的思想及其在国内外 的研究情况进行了阐述，最后提出了本文的研究意义及论文组织。 西南交通大学硕士学位论文第9 页 第2 章潜在语义索引的基本理论 2 1 潜在语义索引的基本思想 潜在语义索引u 使用了向量空间模型的方法来表示词汇一文本矩阵的， 是对向量空间模型的扩展，传统的基于关键词的向量空间模型( v s m ) ，用 a = 。表示m 个词汇和n 个文本构成的文本集合，其中每一行代表一个词 汇向量，每一列代表文本集中的一个文本向量，它的优点在于将非结构化的 文本表示为向量形式，使得各种数学处理成为可能。但是，向量空间模型是 基于词汇之间关系相互独立的基本假设( 正交假设) ，在实际情况下很难得 到满足，文本中出现的词往往存在一定的相关性，在某种程度上会影响计算 的结果。 l s i 则将自然语言中的每个文本视为以词汇为维度的空间中的一个点，认 为一个包含语义的文本出现在这种空间中，它的分布绝对不是随机的，而是 服从某种语义结构。同样地，也将每个词汇视为以文本为维度的空间中的一 个点。文本是由词汇组成的，而词汇又要放到文本中去理解，体现了一种“词 汇一文本 双重概率关系。 l s i 把词汇中的一些不经常的用法，如：一些词汇的误用，或不相关的词 汇偶然出现在一起，还有高频词，低频词等不能代表文本主题的词汇视为“噪 声 ，应当从主要语义结构中排除掉。利用截断的奇异值分解降维的方法，达 到信息过滤和去除噪声的目的。通过对词汇一文本矩阵a 进行截断的奇异值分 解，得到矩阵a 的秩为k 的“近似矩阵”，从数据压缩的角度看，“近似矩阵 是秩为k 的前提下矩阵a 的最d , - - 乘意义上的最佳近似。l s i 不同于v s m 中文 本和词汇的高维表示，而是将文本和词汇的高维表示投影在低维的潜在语义 空间中，缩小了问题的规模，得到词汇和文本的不再稀疏的低维表示，同时 这种低维表示揭示出了词汇一文本之间语义上的联系。 2 2 奇异值分解 潜在语义索引重点应用了矩阵的奇异值分解 2 2 1 ( s i n g u l a rv a l u e d e c o m p o s i t i o n ，s v d ) 。s v d 是数理统计中常用的方法之一，大量应用在不 受限的最小立方问题，矩阵阶次估计和规范相关分析等问题的解决方案中。 西南交通大学硕士学位论文第1 0 页 矩阵的奇异值定义弘引：设a 是m x n 实矩阵，称r l 阶方阵a ra 的非0 特征值的算术平方根为矩阵a 的奇异值。 矩阵的奇异值分解定理：设a er 刖4 ，秩为r ，则存在m 阶正交矩阵u 和n 阶正交矩阵v 使得： u r a y = 陪ol ( 2 - 1 ) 称么= u 陪o i y r ( 2 - 2 ) 为矩阵a 的奇异值分解。 在信息检索中应用的是奇异值分解的种特殊形式，因为在信息检索问 题中需要迸行奇异值分解的矩阵一般都是高阶稀疏矩阵。 不失一般性，假设词汇一文本矩阵a 是m 行n 列的一个稀疏矩阵，其中 m n ，已知r a n k ( a ) - - r 。由奇异值分解定理可得a 的奇异值分解为： a = t o s o 以( 2 - 3 ) 其中：瓦的各列正交且长度为1 ，即譬t o = i 。t o 的列向量称为矩阵a 的左奇异值向量。 瓯称为矩阵a 的奇异值标准型，是一个单值的对角矩阵，即： = d i a g ( 旯l ，如，a 。) ，且有- 九旯，允r + l = = 0 ，其中丑是么的 奇异值。 或的各列正交且长度为l ，即d o = i 。d o 的列向量称为矩阵x 的右 奇异值向量。 一般，对于a = r o s o d 彳，矩阵t o ，s o ，d o 都是满秩阵引，它们表示了 原始矩阵a 的全部信息。s v d 分解的优点在于可以利用较小的矩阵做到了最 优的近似。如果瓯对角线上的元素均按照大小排序，则选取前k 个最大的奇 异值，其余设置为0 ，这样得到的矩阵运算结果记为彳。，是原始矩阵a 的一 个近似值，其秩为k 。可以证明，矩阵a 。是所有秩为k 的矩阵中与a 用f 范数评价时最接近的一个。在黑中引入0 以后，可以通过删除相应的行与列 来化简品，获得了新的对角矩阵s 。同时，取瓦和d 。的前k 个列，分别获得 矩阵t 和d ，则可以构建a 的k 秩近似矩阵彳。 彳a t = t s d r ( 2 4 ) 西南交通大学硕士学位论文第11 页 这是对a 的一个最佳均方逼近的秩为k 的模型，我们用它来估算所需数 据。 降维因子k 值1 的选取关系到语义空间模型的效率，k 值过小会使一些 有用的信息丢失，k 值过大则会使运算量增大，一般选k 时，对于 = d i a g ( ；t i ，2 2 ，l ) ，且有丑如) j r 4 + l = = 0 ，可令k 满足贡献 率不等式： 岸7 以 臼 ( 秒可取4 0 ，5 0 ) ( 2 - 5 ) li 其中，口为包括原始信息的阈值，贡献率不等式是参考因子分析的相应 概念提出的用以衡量k 维子空间对于整个空间的表示程度。 亨嘞7 ：“”。9 ”缆 ，d 。i 貔、“w & 。荔 礴 r rr n 图2 1 词汇一文本矩阵奇异值分解图示 对近似矩阵4 ，t 的行向量称为词汇向量，d 的行向量称为文本向量， 在此基础上进行文本检索和其他文本处理，即为潜在语义索引l s i ，词汇向量 和文本向量可被投影在一个相同的k 低维空间，这个空间就被称为潜在语义 空间。 西南交通大学硕士学位论文第1 2 页 语义维1 语义维2 图2 2 词汇和文本在潜在语义空间上的表示 l s i 通过奇异值分解和取k 秩近似矩阵，一方面有效的解决了同义词和 多义词问题。比如：“电脑 ，“计算机”，“程序 和“植被 这四个词，其中， “电脑和“计算机 是同义词，而“程序是和“电脑，“计算机相关 的词，而“植被则与其它三个词完全无关。在基于关键词的检索系统中， 若文本中没有直接出现“电脑”，则当输入“电脑 一词进行检索时，对于包 含“计算机”的文本和包含“植被的文本都不会被命中。但用户希望在查 询“电脑”时能把关于“计算机的文本找出来，或把关于“程序 的文本 也找出来，只是相关度相对于关于“计算机”的文本要低一些，但绝对不希 望把关于“植被”的文本找出来。 潜在语义索引技术通过奇异值分解得到的潜在语义空间可以很好的表示 这些词之间的内在联系，在此空间，“电脑 ，“计算机”和“程序的上下文 语境在某种程度上基本一致，也即：距离更接近，而和“植被”的距离则较 远，从而，更加凸显了词汇间的语义关系，对于词汇和文本，文本和文本间 也是一样的。 另一方面，一般情况下，k 只需要取一个比较小的值，得到的语义空间就 可以表示原始矩阵a 的大部分关键信息，同时属于“噪音 的信息被去除。 而且k 秩近似矩阵比原来的m n 高维稀疏矩阵的项数小的多，矩阵的压缩降 低了计算的复杂度，有利于提高检索的效率。 西南交通大学硕士学位论文第1 3 页 2 3 潜在语义索引的数学依据 实验表明：潜在语义索引通过奇异值分解，不仅减少了词汇一文本矩阵 的维数，而且大大消减了一直困扰基于关键词的信息检索的文本中的词汇的 同义性和多义性问题，那么，潜在语义索引的数学依据是什么呢? 我们通过 下面的两个关于奇异值分解定理来进行剖析： 定理1 矧：假设a 的奇异值分解由给出，并且有： 如允，以+ l = = 0 ， r ( a ) 并i i n ( a ) 分别表示a 的表示区域和a 的零空间，则有： ( 1 ) 阶特性：r a n k ( a ) = r ，( 4 ) = p 川，。 ，尺( 彳) = s p a n u l ，一，“， ， u = l l 一，“，】，y = 卜。，v ：，y 。】； ( 2 ) 二阶分解性： 彳= u ；丑v - i = l ( 3 ) 规范性：怕旺= 彳+ 置+ + 名，忙8 ：= 。 其中， ”旺和”8 分别代表矩阵的f 范数和谱范数，定理l 说明了单位 向量u i ，1 ，与矩阵a 的关系，同时也体现了矩阵a 的特征值与其范数的关系。 但是，向量 ，u ，u ，对词汇一文本矩阵a 的影响程度是不一样的。因此， 常常需要对矩阵a 的相应的语义空间进行压缩，由于r 个特征值是按大小排序 的，只保留前k 个最大的特征值，即所谓的对a 进行奇异值分解。 所以上面最重要的是奇异值分解的阶特性，它表明可以将矩阵的奇异值作 为矩阵定性分析的定量手段。而奇异值分解的二阶分解性表明，在很多应用 场合中可以对矩阵进行大胆的压缩。 定理1 的三个方面可以用来证明下列定理： 定理2 0 ：假设a 的奇异值分解由式给出，其r = r a n k ( a ) 5p = m i n ( m ，咒) ， 对于任意的k ，定义： k a 。= yu ；丑1 ，j ( 2 - 6 ) 西南交通大学硕士学位论文第1 4 页 那么， r a i 划ni a 一口萨卜4 惦麓+ l + 砖；( 2 - 7 ) ，r a ( 占i ) ：n 川 a b 8 ：= l l 彳一彳t8 ：= 名t + 一；( 2 - 8 ) 这一重要结论表明，由a 的k 个最大的奇异三元组构成的4 是和a 最接近 的k 秩矩阵，换言之，l s i 将词汇一文本矩阵从高秩投影到低秩后，尽可能地 保留了原始矩阵a 的大部分信息含量和查询能力。但是，这还不足以说明为什 么l s i 模型改进了查询能力。为此，c h p a p a d i m i t r i o u 等在一个比较严格的前 提下，得到了下面的一个定理，这个定理能够更加明确地指出l s i 模型确实能 够改进检索性能。 定理3 弘：假设c 为个纯粹的，占可分为包含k 个主题的文本库模型， 而且每一个词汇在某一主题中出现的概率最大为f ，f 为一个大于0 的足够小 的值。若有m 个文本由c 模型产生，则秩为k 的l s i 以( 1 0 ( m 。1 ) ) 的概率0 ( e ) 一偏 向c 。 2 4l s i s v d 的特点 概括起来，与传统的向量空间模型比，l s i 的优点在于： ( 1 ) l s i 利用潜在的语义结构表示词汇和文本，将词汇和文本映射到同一 个k 维的语义空间内，均表示为k 个因子的形式，向量的含义发生了很大的变 化。它反映的不再是简单的词汇出现频率和分布关系，而是强化的语义关系。 在保持了原始的大部分信息的同时，克服了传统向量空间表示方法时产生的 多义词、同义词和单词依赖的现象。同时，在新的语义空间中进行相似度分 析，比使用原始的特征向量具有良好的效果，因为它是基于语义层而不仅是 词汇层。 ( 2 ) 由于词汇和文本在相同的空间，使得l s i 更具灵活性，允许用户使用 自然语言提交查询请求，查询条件可以是独立的词汇，也可以是文本，使得 查询和反馈更容易。 ( 3 ) 用低维的词汇一文本空间代替了原来的词汇一文本空间，可以有效地 处理大规模的文本集，有效地提高了检索的效率和准确率。 ( 4 ) l s i 不同于传统的自然语言处理过程和人工智能程序，它是完全自动 的。所谓自动，就是l s i 不需要人工干预，不需要预先具有语言学或者知觉相 西南交通大学硕士学位论文第1 5 页 似性知识( 不使用人为构造的字典、知识基础、语义网络、文法、词法、句 法剖析器等，它的输入只是原始的未经处理的文本序列) 。它完全是根据普通 数学学习方法，提取合适的维度语义空间，结合其他理论方法，达到有效展 示对象和文本内容的目的。通过对大量的文本分析，l s i 可以自动地模拟人类 的知识获取能力，甚至分类、预测的能力。 潜在语义索引模式以其数学理论严谨、处理文本过程思路清晰得到了信 息检索领域的重视，该方法在语言建模、视频检索等方面取得了较为成功的 应用，在朴素贝叶斯分类模型、k n n 模型和s v m 模型中都被证明是非常有效 的方法。但是，该方法也存在着一些不足之处： ( 1 ) 潜在语义在进行信息提取时，忽视了词汇的语法信息甚至词汇出现的 顺序，它仍然是一种b a g o f - w o r d 方法，即：简单地通过所有词汇向量的线性 总和来产生文本向量，表示文本的含义。但是句子的语法结构包含了词汇之 间更深层次的语义关联信息，忽视这种关联信息在一定程度上影响了潜在语 义对文本内容的把握，虽然潜在语义通过新的空间在一定程度上实现了降维。 ( 2 ) 因子k 值的选取直接关系到语义空间模型的效率，k 值过小则会使一些 有用的信息丢失，k 值过大则会使运算量增加，但是，k 值是一个可变的参数， 对其确定是很困难的，现在还没有特别好的办法来解决。在实际中，人们 般只能通过反复的实验来确定这个值。 ( 3 ) 奇异值分解对存储空间的要求很大，运算的时间复杂度很高。s v d 算 法的时间代价是o ( n 2 k3 ) ，n 是单词数和文本数的乘积，n 随文本数和单词数 的增加而迅速增加，所以s v d 不太适合动态变化的文本集。 2 5 潜在语义索引中相似关系的计