（管理科学与工程专业论文）基于sdd中文农业网页搜索系统的设计与实现.pdf

摘要 由于我国数字鸿沟的存在，农业信息的获得非常困难，特别是急需农业科技信息和市场信息 的企业、部门、农户，他们通过传统的综合搜索引擎，在这些海量的信息中，搜索一个准确的信 息已非常困难，而使用通用的搜索引擎则搜索到很多无关的信息。要实现信息的精确搜索，就需 要研究专业的搜索引擎。因此，针对于中文农业网页，研发专业化的搜索引擎，实现农业信息的 精确搜索是本文研究的出发点。 本文通过研究背景的分析提出了一种“二次主题漂移”检索模式。详细介绍了全文检索与语 义检索技术，为后面的研究奠定技术基础，提出了基于s d d 算法的语义检索技术实现方法。根 据s d d 算法，构建了一个实验系统来验证s d d 算法处理大规模文档的能力，同时利h j 国家农业 科学数据中心1 0 个主题数据库中的l o 万条记录，来进一步验证“二次主题漂移”技术的可行性。 最后介绍了基于s d d 中文农业网页搜索系统的设计与实现，包括系统的结构与功能以及实际运 行的情况。 本文的主要成果： ( 1 ) 研究并实践“二次主题漂移”检索模式，可以有效提高用户检索应用的体验。 ( 2 ) 研究分析s d d 算法，找出了该算法在w i n d o w s 平台上的运行瓶颈，并提出了性能改进 的具体方法。 ( 3 ) 构建了基于s d d 算法的中文农业信息检索实验系统，验证大规模文档集rs d d 算法的 可行性和“二次主题漂移”模式的可行性。 ( 4 ) 设计并实现了一个基于s d d 中文农业网页搜索系统。 关键词：s d d ，二次主题漂移，信息检索 a b s t r a c t a s ( h ce x i s t e n c e0 fd i g i t a ld i v i d e g e n i n ga 曲c u l t u r a li n f o f | t l a n o nw a sv e r yd i m c u n ，e s p e c i a l l yf o r 山ee n 蛔 p r i s e 、d c p n t 、f a r l l rw h i c hd e s i r e dm ea g 订c u l t u r a 圭s c i e n c ei n f o n n a t i o na f l dm 啦e t i n f o r r n a t i o nm o s t l y ，b u ti nt h e s eg r a t cc a p a c i t yi i l f o 脚a t i o nm e yu s e dt i i en a d i t i o n a li n t e g r a t es e a r c h e n g i n e ，n o to n l ys e a r c h i n ga na c c u r a t ci n f m 撕o nw a rd i m c u l tb u ta l s ot h e yg o tm a n yn o tr e l e v a n t i n f o n n a t i o n f 0 rc h 蛆g i n gt l l i sd e v e l o p i n ga l ls p e c 试s e a r c hc n g i n ew a sv e r yn c c e s s a r y ， s oa c c o r d i n g t t l ec h i n e s ew c bp a g e ，d e v d o p i n ga ns p e c 试s e a r c he n g i n ea b o u ta g r i c u l n l f a l t or e a l i z et h ea c c u m t e s e a r c hw a s 廿l et h e s i ss t a nd o i n t t h r o u g ht h ea 1 1 a l y z co f s e a r c hb a c k 伊o u n d ，m e “t w ot h e r n es 1 1 i f t ”s e a r c hr n o d e lw a s i s s u e d 1 1 1 ef u l l - t e x ta 1 1 ds e m 柚d cr e m e v a lt c c h n o l o g yw a si n t r o d u c e di nd e t a i lt h em e t l o dw h i c hi s b a s e do n 血es d ds e m a m i cr e i e v a lt e c h n 0 1 0 9 yw a sm e n o n e do nt h a t t l l e nt h ee x p e r i m e n ts y s t e m w a sb u i l tt 0v a l i d a t et l l ec 印a c i t yo fi i n p r o v e ds d do n 】a r g es c a kd o c u f n e n t sa n df c a s i b i l i t y0 f “t w o t h e n l cs h i f t r n o d e lw h i c ht o o kt h ea d v a n t a g eo fah u n d f e d 吐l o u s 蛐dr e c o r d sw h i c hc o m e 仃o mt e n m e m ed a t ab a s eo ft t i en 撕o n a l a g r i c u l t u r a ls c i e n c ec e n t e ra t1 船t ，w ei n t r o d u c e d 廿1 ed e s i g l la n d r e a l i z a 旺0 no fc h i n e s e a g r i c u l t u r a lw 曲p a g e ss e a r c hs y s t e mb a s e d o nt h e s d d ，i n c l u d i n g c o n s t n l 嘶o n 、f u n c t i o n sa n dm n i l i 】唱i na c n o n t h em a i nr e s u h s ： ( 1 ) r e s e a r c h i n g 粕dp r a c t i c i l l g 山e “t w ot l l e 腓s h i f t ，m o d e l ，e m c i e n n yi m p m v e 恤e x p 刮e n c eo f u s e rs e a r c ha p p l i c a t i o n ( 2 ) a n a l y z i n gt 1 1 es d da r i t h 脚n c 、f l n d i n g 叫t 吐l eb o n l e - n e c ka n d1 0 0 k i n go u tm ei m p r o v e r i l c n t n l e t l l o d ( 3 ) b u i l d i n gt 1 1 ee x p e r i 研l ts y s t e mb a s e do nt l l es d da l l dv “d a d n g 血ef c a s i b i l i t yo nl a 瑁es c a l e d o c u m e n t sa n d “t w ot h e i n es 1 1 i 甜i n o d d ( 4 ) d e s i g n i l l ga i l dr c a l i z i n gm ec h i n e s ea g r i c u l t i l r a lw c bp a g e ss e a r c hs y 咖mb a s e do nt 1 1 es d d k e y w o r d s ：s 加，t w ot l l 咖es h 汛，i n f o n n a t i 帅r e t r i e v a l 英文缩略表 英文缩写 a p i a j a x b ，s c o m j a c o b j s p h t m l h r r p i i s m l s i s v d s d d u r l 英文全称 a p p c a t i 0 p m g m 删n gh l t e r f a c e a s ”c h r o n o u sj a v a s 州p ta 1 1 d 咀一 b r o w s e r ，s e n ，e r c o r r l p h 0 n e n to b j e c tm o d d j a v ac o m b r i d 窖e j a v a s e r v e r p a g e h y p e rt 奴tm a i 【e u pl a n g u a g e h y p e rt e x t r r a n s p o n 胁o c o l i n t e m e ti n f b r m a t i o ns e r v i o e h f o 啪a t i o nr e n i e v a l l a t e n ts e “1 a n d ch l d e x s i n g u l a r v a 】u ed e c 伽叩o s i n o n s e n d d i s c r c t ed e c o m p o s i d o o fm a t r i x u l l j f o n nr e s o u r c el o c a t o r v 中文名称 应用程序接口 异步j a v a s c r i p t 与x m l 浏览器朋务器 组件对象模型 j a v a c o m 桥 j a v a 服务器脚本 超文本标记语言 超文本传输协议 互联网信息发布服务 信息检索 潜在语义索引 奇异值分解 半离散矩阵分解 统一资源定位器 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人己经发 表或撰写过的研究成果，也不包含为获得中国农业科学院或其他教育机构的学位或证 书而使用过的材料。与我一同工作过的同志对本研究所做的任何贡献均己在论文中作 了明确的说明并表示了谢意。 研究生签名 奖孚也时间纱饰6 年月苦日 关于论文使用授权的声明 本人完全了解中国农业科学院有关保留、使用学问论文的规定，即：中国农业科 学院有权保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩 印和扫描等复制手段保存、汇编学位论文。同意中国农业科学院可以用不同方式在不 同媒体上发表、传播学位论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 导师签名： 裟浆 闯( 司幻 n 时问：渺年月6 同 时间：碲g 月名日 中国农业科学院硕士学位论文 第一章弓【言 1 1 研究背景 第一章引言 搜索引擎是为解决用户要在信息海洋里查找信息困难这个问题而出现的技术，己成为互联网 上非常重要的网络导航服务。目前，w e b 网上拥有超1 0 0 亿的静态网页。而当前的通用搜索引擎 所能检索的网页一般不超过w e b 网的3 0 叫0 ，即使是用户最多的g 0 0 9 1 e ，其检索的网页也只 在3 0 亿左右。另一方面，、e b 技术的发展使更多的网页以动态形式存在，形成所谓的隐藏w 曲 网，据估计这部分的信息是整个静态w 曲空间的5 0 0 倍以上，而且有递增的趋势。由于搜索引擎 在b 舱m e t 中所具有的重要地位，它一直就是用户关心的热点之一，也是备家相关公司全力开发 的技术焦点。 根据中国互联网络信息中心( c n n i c ) 于2 0 0 5 年7 月发布的第1 6 次中国互联网络发展状 况统计报告，目前，国内上网用户总量已达到1 0 3 亿，而在“用户经常使用的网络服务，功能” 中，“搜索引擎”以6 4 ，5 的选择率排在第三位，仅次于“电子邮件”( 9 1 3 ) 和“浏览新闻” ( 7 9 3 ) 。同时，搜索引擎还是“用户得知新网站”的最主要的途径( 8 4 5 ) 和“用户在互联 网上获取信息”的最常用的方法( 5 8 2 ) 。不仅在中国，放眼世界，互联网搜索业务也呈现出q 强劲的增势。根据石城研究机构的预测，2 0 0 5 年，全球收费搜索服务市场的规模将达到4 0 亿美 元，而在未来三年内，市场规模每年将以3 5 的速度增长( 洪小文，2 0 0 5 ) 。 由于我国数字鸿沟的存在，农业信息的获得非常困难，特别是急需农业科技信息和市场信息 的企业、部门、农户，他们通过传统的综合搜索引擎，如g o o g l e 、百度等，并不能迅速找到自己 想要的信息。据不完全统计，在农业领域现有各种网站约1 万个涉及农、林、牧、渔、水利、 气象、农垦、乡镇企业、及其他农业部门，网页共计1 5 0 万篇，在这些海量的信息中，搜索一个 准确的信息已非常困难，而使用通用的搜索引擎则搜索到很多无关的信息，其根本原因在于网站 中的大量信息是以非结构化的形式存在，要实现信息的精确搜索，就需要研究专业的搜索引擎。 因此，针对于中文农业网页，研发专业化的搜索引擎，实现农业信息的精确搜索是本文研究的出 发点之一。 “国家农业科学数据中心”是由国家科技部“科学数据共享工程”支持建设的数据中心试点 之一，由中国农业科学院农业信息研究所主持建设。农业科学数据中心是以满足国家和社会对农 业科学数据共享服务需求为目的，立足于农业部门，以数据源单位为主体，以数据中心为依托， 通过集成、整合、引进、交换等方式汇集国内外农业科技数据资源，并进行规范化加工处理，分 类存储在农业领域形成拥有1 2 大类6 0 个主体数据库6 0 0 个数据库( 集) 的农业科学数据资源 中心，然后通过网络向全社会提供共享服务。“农业科学数据中心”的用户主要通过农业科学数 据中心的网站来定位、查询和下载所需要的农业科学数据。 由于国家农业科学数据中心是通过w e b 上的数据库来提供服务的，在这庞大的数据资源中， 信息检索是查询和发现数据的重要手段，如何给用户提供一个良好的w e b 数据库群检索手段是 项目小组努力的目标，这也是本研究的另外一个出发点。 中国农业科学院硕士学位论文第一章b f 言 1 2 信息检索的相关性理论 “利用搜索工具获取有用信息”业己成为互联网用户的主流选择。那么，是不是说，互联 网搜索技术与应用、商业模式与用户需求已然臻于成熟了呢? 答案是否定的。事实上，自上个世 纪末至今，在互联网数据搜索与挖掘技术领域尚未出现那种足阻测定刷新用户体验的“革命性创 新”( 洪小文，2 0 0 5 ) 。 信息检索的核心羹豢鬟瑾熊罕型型 ；酬懿醛嗣建窜癯囊牡b 枣霪出鼎毽苗刊淄：薹聃塑 疆省嗡篓蠹譬羹誊赢囊群酌菜统囊2 矧蠹蛰号丽博7 蠹弱裹亟薹孕萋二委酬哥黔嚣裂幂套专藉蒜 篓列臼“尚蠹峰商甄鼋理壤李宇丽， 藿谢函鬻f 串和蠢峨若f 羹蒜旦诱蕃鬻飞謦醛；一蟹爵墓“川：皋= 础j 鬻8 磊孺砭孽i r 掸肖 薹影星囊疆铋膳赔疆= 翼蕈主磊篙错坦嚣翌苍季眭些鏊零眷醣静，甜睇8 位字节为基础的索引文 件格式，使 得兼容系统或者不同平台的应用能够共享建立的索引文件。 在传统全文检索引擎的倒排索引的基础上，实现了分块索引，能够针对新的文件建立小文 件索引，提升索引速度。然后通过与原有索引的合并，达到优化的目的。 优秀的面向对象的系统架构，使得对于l u c e n e 扩展的学习难度降低，方便扩充新功能。 设计了独立于语言和文件格式的文本分析接口，索引器通过接受t o k e n 流完成索引文件的 创立，用户扩展新的语言和文件格式，只需要实现文本分析的接口。 已经默认实现了一套强大的查询引擎，用户无需自己编写代码即使系统可获得强大的查询 能力，l u c e n e 的查询实现中默认实现了布尔操作、模糊查询( f u z z ys e a r c h ) 、分组查询等等。 面对已经存在的商业全文检索引擎，l u c e n e 也具有相当的优势。首先，它的开发源代码发行 方式( 遵守a p a c h es of t w a r el i c e n s e ) ，在此基础上程序员不仅仅可以充分的利用l u c e n e 所提 供的强大功能，而且可以深入细致的学习到全文检索引擎制作技术和面相对象编程的实践，进而 在此基础上根据应用的实际情况编写出更好的更适合当前应用的全文检索引擎。在这一点上，商 业软件的灵活性远远不及lu c e n e 。其次，l u c e n e 秉承了开放源代码一贯的架构优良的优势，设 计了一个合理而极具扩充能力的面向对象架构，程序员可以在l u c e n e 的基础上扩充各种功能， 比如扩充中文处理能力，从文本扩充到h 1 札、p d f 等等文本格式的处理，编写这些扩展的功能不 仅仅不复杂，而且由于l uc e n e 恰当合理的对系统设备做了程序上的抽象，扩展的功能也能轻易 的达到跨平台的能力。最后，转移到a p a c h e 软件基金会后，借助于a p a c h e 软件基金会的网络平 台，程序员可以方便的和开发者、其它程序员交流，促成资源的共享，甚至直接获得已经编写完 备的扩充功能。最后，虽然l u c e n e 使用j a v a 语言写成，但是开放源代码社区的程序员正在不懈 的将之使用各种传统语言实现( 例如n e tf r a 口l e r k ) ，在遵守l u c e n e 索引文件格式的基础上， 使得l u c e n e 能够运行在各种各样的平台上，系统管理员可以根据当前的平台适合的语言来合理 的选择( 李宇，2 0 0 3 ) 。 2 1 2l u c e n e 系统结构分析 l u c e n e 作为一个优秀的全文检索引擎，其系统结构具有强烈的面向对象特征。首先是定义了 一个与平台无关的索引文件格式，其次通过抽象将系统的核心组成部分设计为抽象类，具体的平 2 、检索需求转换 为查询关键词 4 、返回数据 匹配的结果 圈1 - 1 传统m 系统模壅 r g 1 - 1t h et h m 6 0 且ims y s 蛔mm 0 d e l 问题的症结在于传统的检索模型性中( 如图l l 所示) 的三个基本假设中的两个环节出现了 问题： 用户以关键词提交查询请求。 采用关键词匹配技术来生成结果文档集。 这两个部分方法虽然简单，但是可能会导致信息检索工作出现问题。以关键词作为用户的查 询请求，排除了用户个体的差异性。即只要用户使用了相同的关键词作为查询请求，便可认为用 户具有相同的检索意图，把用户认为是静态的，而根据用户相关性的观点，用户的需求情境是一 个典型的动态变化过程，用户的检索需求是跟用户内在的知识储备、经验、认知状态以及情绪等 紧密相连的。以标引词为基础的检索通常会形成这样一种观念：文献的语义和用户信息需求的语 义可以用标引词集合来表示。这就把问题过于简单化了，因为用标引词集合来代替文档的时候会 丢失很多原来的语义。 如何解决这个问题呢? 本文提出要围绕用户信息需求，以用户为中心，通过“二次主题漂移” 技术来逼近用户检索需求。当然。要完全满足用户的信息需求，建立一个大而全、精而准的检索 系统是一个非常难的过程，本文仅选取中文农业网页检索作为研究的对象，并把“二次主题漂移” 技术贯穿在系统设计和实现中，企望研究结果能够对中文信息检索研究起到一定的推动作用。 1 3 2 主要研究内容 本文的研究包括四个方面的内容。 ( 1 ) 提出以满足用户需求为中心的“二次主题漂移”检索模式实现路线图 “二次主题漂移”检索模式是把全文检索与语义检索结合起来，以满足用户检索需求为中心， 通过逐步逼近的方法实现信息检索的一种技术。 首先，利用全文检索技术来实现第一次主题漂移，即从“关键词”到“文档”的漂移，把用 几个关键词来表示用户信息检索需求漂移到用一篇文档来表示用户的需求。全文检索的优势在于 4 中国农业科学院硕士学位论文第一章引言 悠久、内涵丰富，自然语句歧义、缩略倒置等诸多语义结构使得这方面的研究进晨缓慢。而且这 个问题即使使用人工智能等方法能够解决，计算机所推理出的用户检索需求也是落后于当前用户 的情境点，因此本文把这类问题的解决直接交给用户，首先使用全文检索这种数据检索的方式， 根据用户输入的关键词，匹配出能代表检索主题的文档集，在文档集的基础上由用户根据自己当 前的情境点，来选择文档作为一个新的查诲清求，从用户需求的角度上来说，当用户选择了菜一 个文档的时候，应该说，这篇文档一定程度上接近了用户的检索需求，本文认为这是实现从“关 键词”到“文档”的“第一次主题漂移”，即认为用这个“文档”可以更好地表示用户当前的检 索需求。 “文档”到“文档”第二次主题漂移 在完成了“第一次主题漂移”的基础上，也就是说用户所选择的文档在一定程度上接近了用 户的检索需求，那么通过把这篇具有完整语义的文档作为新的查询请求，通过文档相似性的分析， 检索出与这个文档匹配的文档集应该说这个文档集中的文档更趋近于用户的检索需求，本文称 之为“第二次主题漂移”。反复循环“二次漂移”这个过程，就能够快速地完成用户的查询请求。 “第二次主题漂移”的核心是通过文挡逻辑视图的不断优化，使得文档的索引文件中的数学结构 能够较好地体现文档相关性这一重要特性，从而在对代表用户选择的检索文档进行匹配运算时能 够较好地返回文档来。由于文档逻辑视图便于计算机实现且数学模型构建相对容易，目前这方面 的进展很多一主要有布尔模型、向量模型和概率模型，这三种模型又称为经典模型。随着时间的 推移，经典模型又发展出各自新的数学模型，其中潜在语义索引( l s i ) 正是本文所感兴趣的一 种数学模型，研究该数学模型以及解决该模型当前所面临的问题也正是本文的切入点和主要工 作。 1 4 论文的写作框架 首先通过研究背景的分析在绪论中提出“二次主题漂移”检索模式。第二章综述全文检索与 语义检索技术，为后面的研究奠定技术基础。第三章提出基于s d d 算法的语义检索技术实现方 法，第四章根据第三章介绍的s d d 算法，构建一个实验系统，验证s d d 算法处理大规模文档的 能力，以及利用国家农业科学数据中心1 0 个主题数据库中的1 0 万条记录，来进步验证二次 主题漂移”检索模式的可行性。第五章介绍基于s d o 中文农业礴页搜索系统的设计与实现，包 括系统的结构与功能，以及实际运行的情况。 7 亮显示由于可以增加检索用户有效性体验而被普遍认可。本文在处理检索结果的时候，为了提高 用户的有效性体验，对显示结果高亮问题进行了一些探索。 高亮问题主要在检索结果的两个部分，一个是检索结果的标题；另一个是内容概述。 标题部分由于l u c e n e 提供的接口直接可以返回原文档的标题，因此本文通过在输出的过程 中在标题内进行关键词查找，匹配成功后通过格式控制达到高亮的效果。 概述部分由于l u c e n e 提供的接口对原文档的只是取定长，因此无法满足本文在整篇文档内 匹配查询的需要。为解决检索文档内容的高亮显示，本文采取了以时间换空间和窗口游动的办法， 在l u c e n e 内部对抽取文档内容的最大默认值是2 0 0 字节，本文考虑实际需要将改值扩大了1 0 0 倍，达到2 0 0 0 0 字节，网页内容一般不会超过这个数值，而且从实际的使用情况看还是可以满足 需要的。窗口游动的办法是在取出全部内容的基础上同样进行字符串匹配，尤其在多关键词查询 的时候，对文档内容进行多次查询并将单个关键词的查找位置前后各取2 0 字节，然后进行字符 串的拼接作为结果显示。在实际的使用中，这两种做法虽然增加了计算量，但是由于采用的b ，s 结构，计算得负担全部由服务器端完成，客户端仅能看到显示的结果，因此保障用户查询体验上 还是可以满足需求的。 网站直达功能 l u c e 在设计之初是作为一个a p i 接口提供给其他系统调用的，尤其是在作为网站内部的 检索，索引的文件都是指向网站服务器本地硬盘上的文件。因此，提供的u r l 超链接地址取得 是本地系统文件的路径属性，不利于本文想耍提供搜索引擎时的网站直达功能。根据l u c e n e 构 建索引时将文件路径名作为u r l 的特点，本文把自主开发的“网页制动抓取软件工具”作了针 对性的修改，将网页名作为文件名保存，由于u r l 中使用的一些字符不能作为文件名来创建， 本文采取用“ 、) 、【、】”这四个u r l 中不可能使用到的特殊字符在构建索引前进行替换，在返 回检索结果时反替换的办法，达到网站直达的功能。在网页抓取的过程中，为防止重复抓取的问 题，雌前采用的是u r l 唯一性原则，而根据实际的经验即使不同的u l 也最后也可能被网站解析 生共同的首页面。为解决这个问题，在实践中通过“网页标题名+ 网页”长度的办法，每个抓取 网页的线程都在线程内维护一个“网页标题名+ 网页+ u d ”的列表来进行重复网页的甄别。 2 1 4 全文检索的不足 实际上，无论对文档标引的质量如何，对用户检索的满足率都不可能百分之百。例如，用户 检索关于陈毅在抗日战争中活动的文档，采用对标引词( 主题词、关键词) 字段的检索就很难满 足检索要求，只有在全文检索才能满足检索目的。因此，无论对文档的标引和分类如何，全文检 索的功能都是不可替代的。然而，由于全文检索是直接对“原文”的检索，检索时会产生误检， 大量的检索降低了全文检索的查准率，同时由于作者用词的不统一，同义词繁多，全文检索的蠢 全率也受到影响。所以，解决这些问题是刻不容缓的： ( 1 ) 提高查全率 用词的不统一，影响了用户的查全。例如，查找“非典型肺炎”，由于不同的文档使用的词 汇不同，如“非典型肺炎”、“s a r s ”、“非典”等，只用某一词查找就可能出现漏检，如果让用 中国农业科学院硕士学位论文 第二章全文检索与语义检索 档d 可以表示为d ( d 。，d 2 ，d 3 。d i l ) ，其中二元随机变量x i 表示索引项t i 是否在该文档中出现， 如果出现，则x i l l ，否则x i = o 。( 2 ) 在一个文档中，任意一个索引项的出现与否不会影响到其他 索引项的出现，它们之间互相独立。 从本质上讲，信息检索是一种具有不确定性的决策判断过程。经典概率模型清楚地认识到了 这种不确定性( 或相关性) ，剥用概率论原理，通过赋予索引词某种概率值来表示这些词在相关 文档集合和非相关文档集合中的出现频率，然后计算某一给定文档于某一给定用户提问相关的概 率并做出检索决策。不同于布尔模型和向景空间模型，概率模型具有一种内在的相关反馈机制， 它把检索处理过程看作是一个不断逼近并最终确认命中文档集合的过程，并通过运用某种归纳式 学习方式实现系统对检索结果的优化与完善。但就其自身来说，仍然存在着一些局限性。例如， 各种参数估计难度较大；索引词的权值计算方法为0 ，l 式，没有考虑词频等加权因素；沿用了索 引词之间相互独立的基本假定等。 在上面讨论的m 方法中，本文只使用了文档的很少一部分信息用于确定相关性。尽管这些 方法存在固有的缺陷，但它们却常常能够达到可以接受的正确率，这主要是因为一个文档的所有 文本中包含了大量的冗余信息。接下来，本文将介绍近年来一种试图从文档中获得更多信息、获 得更好性能的方法。 2 2 2 隐含语义索引( l s i ) 模型 隐含语义索引l s i ( l 矗t e n ts e m m 廿ch d e x i n g ) 是1 9 8 8 年s t d i l m a i s 等人提出的一种新的信 息检索代数模型，它主要是为了克服以上三种传统的信息检索模型基于字、词匹配带来的局限性。 l s i 通过统计手段，可以把虽然不含查询字符串却相关的文档提取出来，经过转换后，相关的词 汇会经由文件所包含的内容而产生关联，和概念检索”有相同之处。使用l s i 技术就意味着搜索 引擎在检索网页时，试图把某些查询术语和其潜在概念联系起来。例如，把i m a c 和苹果公司的 电脑联系起来。 l s i 可以看成是一种扩展的向量空间模型。它利用统计计算导出的概念索引进行信息检索， 而不是传统的索引字、词。l s i 基于这样一种断言，即文档库中存在隐含的语义结构，这种语义 由于被文档中词的语义和形式上的多样性掩盖而不明显，其工作原理是利用矩阵理论中的“奇异 值分解( s 、，d ) ”技术，将词频矩阵转化为奇异矩阵：首先从全部的文档集中生成一个标引项一 文档矩阵，该矩阵的每个分量为整数值，代表某个特定的标引项出现在某个特定文档中次数，然 后l s i 对源文档的词一文档矩阵进行奇异值分解，将该矩阵进行奇异值分解，较小的奇异值被剔 除，取前k 个最大的奇异值及其对应的奇异矢量构成一个新矩阵来近似表示源文档库的词一文档 矩阵。结果奇异向量以及奇异值矩阵用于将文档向量和查诲向量映射到一个子空间中，在该空间 中，来自标引项一文档矩阵的语义关系被保留，同时标引项用法的变异被抑制。最后，可以通过 标准化的内积计算来计算向量之间的夹角余弦相似度，再将文档按与查询的相似度降序排列。由 于新矩阵消减了词和文档之间语义关系的模糊度，从而更有利于信息检索。针对一些1 髓c 文档 库的实验结果和初步的理论分析证实了基于l s i 的信息检索系统的优越性。 1 4 中国农业科学院硕士学位论文 第二章全文检索与语义检索 l s i 给文档检索过程增加了一个重要步骤。这种信息检索技术除了能够记录一个文档包含哪 些关键词之外，还可以把一个文档集合作为一个整体来检查，看看还有哪些文档包含这些关键词。 l s i 认为，若文档含有大量的共同单词，则可表明这些文档在语义上具有很大的一致性或相近性， 反之则说明这些文档在语义上的关系较远。这种方法虽然简单，却能够和人在阅读文章内容，然 后对一个文档集合进行归类的方式上有着惊人的吻合。虽然l s i 检索算法无法理解单词的具体含 义，但它对信息的这种检索方式却能够让它看起来似乎有惊人的智能。 对于一个通过l s i 技术检索的数据库，当用户查询时，搜索引擎会查看它对每个文档内容的 单词计算出的相似性值，然后把它认为最符合用户查询要求的文档返回给用户。由于即使不具有 共同的关键词，但根据l s l 分析的结果，两个文档之间在语义上很接近，所以采用l s i 技术的搜 索结果无需严格匹配，只需在语义上与查询词语匹配即可。当对用户查询的某一查询条件没有包 含关键词的文档与之严格匹配时，l s i 往往返回一些虽然根本不包含查询关键词，但内容却与查 询条件相关的文档搜索结果。假如用户已经通过l s i 技术对一些数学方面的文章进行过检索，又 假如n 维r 流形”拓扑”这三个术语在这些文章中一同出现过多次，那么l s i 算法将会注意到这三 个术语在语义上具有相近性。当用户查询“n 维流形”时，l s i 不但返回一组包含“n 维流形”这个查 询词语的文章，还会把虽然不包含这个词语，但含有“拓扑”这个词的文章结果一并返回给用户。 这是l 司为虽然l s i 对数学一无所知，但通过对大量文章的检查已经教会它知道这三个术语之间是 有关联的。所以利用这一信息对搜索结果进行了拓展，改进检索效果。 与前面儿种传统的检索模型相比，l s i 模型的优势表现在： ( 1 ) 词和文档同处于一个空间，l s i 应用更具灵活性。查询既可以是词和文档，也可以是词 和文档的组合，甚至表示为多主题。当然，返回给用户的也可以是词，而非仅仅为通常的文档。 ( 2 ) 向量空间中每一维的含义发生了很大的变化，它反映的不再是词的简单出现频度和分 布关系，而是强化的语义关系。 ( 3 ) 用低维词、文档向量代替原有词、文档向量，可以由乡的处理大规模文档库。 ( 4 ) 便于实现自动文档检索、查询构成以及相关反馈。 2 3 l s i 数学描述 2 3 1 符号 本文采用了d e e n e s t e r 等人引入的符号。标引项文档矩阵x 有f 行( 每行表示每个标引项在 文档中的出现情况) d 列( 每列表示集合中的每个文档) 。s v dx = t 0 s 0 d o t ，结果t 0 是一个f m 的 矩阵，它的标准正交列称为左奇异向量；s o 是一个m m 的正奇异值按降序排序的对角矩阵；d 。 是一个d m 的矩阵，其标准正交列称为右奇异向最。m 为矩阵x 的秩。图2 2 对x 的s v d 作 了描述( 王斌，2 0 0 2 ) 。 2 3 4 概念空间 表2 】概括了d s ”和t s ”的行、列的解释。它说明文档和标引项概念空间是等价的。在一 个文档只含有一个标引项的情况f ，这一点很容易理解。在此情况下，t s “2 的行实实在在对麻于 这个标引项，该行包含了标引项的概念空间。由于s 1 7 。是一个线性操作，因此每个文档向量只 是单标引项文档向量的简单求和。因此，每个文档概念向量是每个标引项向量的线性组合。进一 步来说，在线性组合中，每个文档概念向量指定了应用于每个标引项向量的系数。换句话说，标 引项概念空间和文档概念空间是等价的，文档置于文档中标引项位置的质心( 于斌，2 0 0 2 ) 。 表2 - 1 ts v d 中行列的解释 h b l e 2 1 皿e 既p l a l n o f s v d 咖u 衄皿d m w l矩阵l行 列 l t s “。i标引项概念向最 标引项向量空间基准向量 id s “i 文档概念向量文档向量空间基准向量 2 3 5 小结 本章讨论了信息检索的传统方法以及语义检索的最近进展。按短语标引可以在花费更多更精 细的预处理( 如全部或部分语法分析) 的情况下提高少许正确率，召回率( 可达2 0 ) 。l s i 可以提高 正确率，召回率，但是需要两个前提；( a ) 一个用于建立标引项文档矩阵、实施s v d 的可用训练语 料库；( b ) 人量的计算时问，因为一个m n 矩阵的s v d 时间比m 、n 中较小值的多项式时间还 多。总的看来，信息检索研究比较集中在n i p 、l s i 以及神经网络等方法上。 1 8 图2 2 ：x 的奇异值分解 h g 2 - 2t h e 商n g u i n rd o m p 0 商6 0 no f x 通过t 0 、s o 、d o ，x 可以精确地重构。l s i 中的关键创新在于只保留s o 中的t 个最大的奇异 值，而将其他的值置为0 。t 的值是设计时的一个参数。t 的取值通常在1 0 0 至2 0 0 之间。原来的 x 矩阵可以用x 来近似，x d t s d ，t 是一个含有标准正交列的f t 矩阵，s 是一个正定的t 女 对角矩阵，d 是一个含有标准正交列的d k 矩阵。图2 3 对x 的s v d 作了描述( 王斌，2 0 0 2 ) 。 2 3 2 文档匹配 n i _ j 鹭2 3 ：掣的奇异值分解 n g 2 3 t 缸es i 雌l j l 盯d 忧o 。p 0 耐右蛐d f x l s i 的有效性依赖于s v d 可从文档集的标引项频率向量中抽取关键特征。为了更好地理解这 一点，首先有必要给出一个关于构成s v d 的三个矩阵的操作性解释。在源向量空间表示中，x l x 是文档向量的内积d d 对称矩阵( 即计算文档之间的两两相似度) ，其中每个文档利用标引项频率 向量表示。这种矩阵的一个用途是支持文档集合的聚类分析。x l x 矩阵的每一列都是x 矩阵相应 列的文档向量与每个文档向量的内积集合。于是，文档j 和文档的夹角余弦相似度可以计算公 式( 1 ) ： + y7 i 。扎 c o s ( f ，) = 11 兰! 当；： 。 ：。f ；：。只 因此，可以将矩阵义。看成一个从列向量k ( 描述某个单一文档或查询) 到一个内积列向量( 可 以用于计算夹角余弦相似度) 的线性函数( 即x 1 ) ( q 中的d 个分量代表d 个文档分别和强的相似度) 。 利用s v d 将x 扩展，x ) ( q = d o s 0 t o t ) ( q 。将该式看成由d 0 s 0 ”和s 0 1 7 w 这两个线性函数的合成 对帮助用户理解很有用。首先考虑s 0 1 7 1 f 。该操作将查询向量投影到由左奇异向最生成的m 维 空间上。本质上，t 0 。矩阵将f 维文档向量空间中的文档向量投影到一个m 维的文档特征空间。 因为每个奇异值都是正定的，s o ”是一个真正的对角矩阵。因此s o ”矩阵通过分别调节每个特征 1 6 x 中国农业科学院硕士学位论文 第三章s d d 算法及其改进 算法中，内部循环当条件卢5 靠与翥嚣接近常量时。或者最大内部循环数可以满足。从表达 式( 4 ) 可以推导出表达式( 6 ) 忙w 纠呲一篙措 这两种标准可以同时使用。无论什么时候达到固定点，内部循环就结束了。内部循环保证是递增 的，因为没有循环会使剩余变大，只有几个可能的向量x 和y 。图3 2 显示了s d d 产生相似矩阵 的算法。s 肋近似算法将产生近似矩阵m 当满足条件k = l 【l a x 或者l a a tj 2 晖血 2 f o rk = l ，2 k ，w i l i l c a p m ，d o 1 c h 0 0 s e ys o m a t 黾y 0 2 f 0 r l = l ，2 ，l n 一，w h i l e 口 d 孟，d o 1 s e ts _ 墅 ； s 0 1 v e 一臀时艇 2 s _ 坐 蚓一臀髓脚“ ，卜镒 4 i f l 1 ：口坐竺 b s 8 卜b e n dl _ l o o d 3 上 一工，y 一) ， 2 1 4 ，幺卜畿 5 a t 一a 女一l + d z i ) ，： 6 尺“一r 女一d 女工t y ： 7 ，p 一p i 一声 e n d k - l o o p i f 也+ 。l i ， 0 r 。0 ，f o ra l l ks u c h t l l a t 尺。o 图3 2s 加计算流程 砷9 3 2 1 i l ec o m p u e o o f s d d 相反，单个元素( 血，x t ，y - ) 都存储下来了。类似的，m + 1 在步骤2 6 中可以应用在图3 2 中的步骤( 2 2 1 ) ，( 2 2 2 ) ，( 2 2 3 ) 和( 2 4 ) 中而不用显示生成它。 3 2 2s d d 算法的收敛性证明 本节将证明，由s 叻算法生成的剩余范式在一定条件下严格递减，有s d d 算法产生的近似矩 阵线形收敛于原矩阵。 引理一；( o l e a r y d p e l e g ，1 9 8 3 ) 由s d d 算法产生的剩余矩阵满足0 r + l k o 。这个结果从 表达式( 6 ) 得出。有几种策略可以用来初始化向量y ，在s 叩算法步骤( 1 ) 中： ( 1 ) 最大元素法。初始化y k = e ，j 是包含最大量值的项在剩余矩阵r k 中。最大初始化 计划产生线形收敛算法，但是当风隐含的存储为a _ a t 时计算量非常巨大。 ( 2 ) 循环初始化。设定y k = e t ，i = ( km o dn ) + 1 。不幸的是，收敛效果为n 步线性。 ( 3 ) 门限值初始化。依然循环遍历每个向量，但是只有当满足该向量与剩余矩阵乘积大于 均值时才选择，s 叻可以保证至少有一个向量满足这个不等式，根据f 范式的定义，尽管艮是被 隐式存储的这个门限值却很容易计算，只需要把r k 和一个向萤相乘，而且，如果第一个选择的向 量被选择的话，就不会有额外的计算，因为计算出来的向量s = r k 被用在内部循环中。 ( 4 ) s v d 使用一个r k 的左奇异向量的离散版本，对应于最大奇异值，来初始化迭代。如果 整数限值在表达式( 1 ) 上取消的话这个奇异值是最优的，并且可以生成一个离散近似通过找到 y 。y 满足离散近似于v 。也就是说找到一个向量y 作为表达式( 7 ) 的解： i n i n l 萝一v 0 2 j t ) ，s “，多兰y | i ) ，0 ， ( 7 ) 定理三：( k o l d a 1 9 9 7 ) 由s 叻算法按照最大元素法生成的序列a k ，在范德蒙行列式上初始化 收敛于a ，而且，收敛程度至少为线性。证明如下： 为不失去一般性，假定风! = o ，无论k 为何值：否则的话，这个算法将结束在一个精确解。 考虑一个 司定索引值k ，然后，找到在风中最大量值的坐标( x ，y ) 。然后按照最大初始化算法选 择y = e ，因为内部循化的第一部分选择最优向量x ，这个选择必须与x = e 一样，所以 ( 8 ) 毗脚 篙 r 一铲比出忱 中国农业科学院硕士学位论文 第三章s d d 算法及其改进 k 川冲川；一饺揣 的形式来描述页面内容，类似于文章摘要，简要说明本页的内容。 ( 6 ) 网页的正文部分：在咖源文件中正文部分以 表示开始，以 表示 结束。 ( 7 ) 文本标记：超文本标记中所包含的信息主要体现在对文档中不同位置的关键词的重要程 度予以不同的标识。 在对文档进行特征提取前，首先需要进行文本信息的预处理。这里主要包括去除禁用词表， 中文文档的分词处理等。在中文文档中，停用词表是指不构成词的单字，如“的”，“是”，“啊”， 和不能作为特征相的高频词组，如“其中”，“那么”。去除停用词表可以减小分词词典规模。并 能有效的提高检索效率。 从英文单词的多种形式中提取出基本词干的过程被称作s t e 向n g 。英文动词在使用时，有 过去时、一般现在时、先在进行时等多种事态变化