（计算机软件与理论专业论文）基于潜在语义分析的智能搜索技术研究.pdf

e n g t h e i n t e l l i g e n ts e a r c ht e c h n o l o g y b a s e d o nl a t e n ts e m a n t i c a n a l y s i s c a n d i d a t e w a n gy a n g s u p e r v i s o r p r o f y i ng u i s h e n g a c a d e m i cd e g r e ea p p l i e df o r m a s t e ro fe n g i n e e r i n g s p e c i a l i t y c o m p u t e rs o f t w a r ea n dt h e o r y d a t eo fs u b m i s s i o n j a n u a r y 2 0 10 d a t eo fo r a le x a m i n a t i o n m a r c h 2 010 u n i v e r s i t y h a r b i ne n g i n e e r i n gu n i v e r s i t y f i l 学位论文原创性声明 本人郑重声明 本论文的所有工作 是在导师的指导下 由 作者本人独立完成的 有关观点 方法 数据和文献的引用已在 文中指出 并与参考文献相对应 除文中己注明引用的内容外 本论文不包含任何其他个人或集体已经公开发表的作品成果 对 本文的研究做出重要贡献的个人和集体 均已在文中以明确方式 标明 本人完全意识到本声明的法律结果由本人承玛 作者 签字 矽 印 日期 加r 矧易月 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定 即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学 哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索 可采用影印 缩印或扫描等复制手段保存和汇编本 学位论文 可以公布论文的全部内容 同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学 涉密学位论文待解密后适用本声明 本论文 日在授予学位后即可口在授予学位1 2 个月后 口 汇编等 一 7一 存 游 鍪蝴 行 节伸 淄 撕纠 挝 刷矽 b 立日关有交送 日 送 日 学 大x缈1诗太场j 程力 工 年 滨 厂 p t 7 一 善 铜 字矿 厶日 奎 哈 签 由 0 者期 后 作日 密解 近年来互联网飞速发展 已经发展成为包含多种信息资源 站点遍布全 球的巨大动态信息服务网络 为用户提供了一个极具价值的信息源 搜索引 擎为用户提供了友好的检索接口 能帮助人们从浩瀚的数据中抽取出对用户 有用的信息 能极大地节省用户的查询时间 互联网上绝大多数的信息是以文本的形式保存的 互联网上文本信息的 指数级增长给搜索引擎技术带来了巨大的挑战 人们越来越难以快速准确地 从网上搜索到相关信息 由于自然语言中多词同义 一词多义等不确定性因 素存在 相同概念可以有多种不同的表述方式 传统的基于关键词字符匹配 的搜索引擎中 参与匹配的只有外在的表现形式 而非它们所表达的全部概 念 用户很难简单地用关键词或关键词串来真实地表达真正需要查询的内容 把搜索引擎技术从关键词匹配的层面提高到语义的层面 从语义意义上智能 地认知和处理用户的查询请求成为当前搜索引擎技术的研究热点 本文从智能搜索建模的角度出发结合潜在语义分析技术 研究了搜索引 擎中文档处理 查询处理以及最后的信息匹配处理 在此基础上 对潜在语 义空间中权值从概率角度进行了分析与改进 使其更能体现出文档间 文档 与词汇间的语义关系 对用户查询进行语义扩展 补充了用户输入信息不足 或与索引词汇不匹配的问题 对用户搜索结果不理想进行调整 提出二次搜 索的策略改善搜索结果使其更贴近用户要求 最后文本设计并实现了基于潜 在语义分析的智能搜索系统验证了算法可以在一定程度上搜索引擎对语义的 理解 并获得较高的准确率与查准率 关键词 搜索引擎 潜在语义分析 奇异值分解 查询扩展 p w o r l d w h i c hp r o v i d e s u s e r sw i t hav a l u a b l es o u r c eo fi n f o r m a t i o n s e a r c h e n g i n e so f f e ru su s e r f r i e n d l ys e a r c hi n t e r f a c e st h a tc a nh e l pp e o p l ea c q u i r eu s e f u l i n f o r m a t i o nf r o mh u g ed a t a w h i c hc a l ls a v eal o to f t i m ef o ru s e r sq u e r y t h ev a s tm a j o r i t yo fi n f o r m a t i o no nt h ei n t e m e ti ss a v e di nt h ef o r mo ft h e t e x t t h ee x p o n e n t i a lg r o w t ho ft e x tm e s s a g eh a sb r o u g h tg r e a tc h a l l e n g e st ot h e s e a r c he n g i n et e c h n o l o g y d u et om u l t i w o r ds y n o n y m s p o l y s e m ya n do t h e r u n c e r t a i n t i e st h a te x i s ti nn a t u r a ll a n g u a g e t h es a m ec o n c e p tc a nh a v em a n y d i f f e r e n tp a t t e r n so fe x p r e s s i o n t h et r a d i t i o n a ls e a r c he n g i n e sb a s e do nk e y w o r d s m a t c h i n gs i m p l yu s ek e y w o r d so rk e y w o r ds t r i n g sr a t h e rt h a nt h eg e n u i n ec o n c e p t w h i c ht h eu s e r sw a n tt oe x p r e s s t h u s s e a r c he n g i n e sn e e dt od e v e l o pi n t o s e m a n t i cl e v e lf r o mk e y w o r d sm a t c h i n g r e c o g n i z i n ga n dd e a l i n gu s e r q u e r y i n t e l l i g e n t l yi ns e a r c he n g i n et e c h n o l o g yh a v ec o m e i n t of o c u s t h i sp a p e rg i v e sr e s e a r c ho nd o c u m e n tp r o c e s s i n g q u e r yp r o c e s s i n ga n dt h e f i n a lm a t c ho fi n f o r m a t i o np r o c e s s i n gi ns e a r c he n g i n e sc o m b i n e dl a t e n ts e m a n t i c a n a l y s i st e c h n i q u ef r o mt h ef v i e wo fi n t e l l i g e n ts e a r c hm o d e l i n g o nt h i sb a s i s w o r dw e i g h tv a l u e si nt h el a t e n ts e m a n t i cs p a c ea r ea n a l y z e da n di m p r o v e di nt h e p r o b a b i l i s t i cs e n s e s oi tc a nb e t t e rr e f l e c tt h es e m a n t i cr e l a t i o n sb e t w e e nw o r d s a n dd o c u m e n t s n e x t u s e r q u e r i e sa r ee x p a n d e dt oc o m p l e m e n tt h el a c ko f i n f o r m a t i o nw h i c ht h eu s e r sg i v eo rm i s m a t c hb e t w e e nu s e r s w o r d sa n di n d e x v o c a b u l a r y i na d d i t i o n s e c o n ds e a r c hs t r a t e g yw a sp r o p o s e di nt h ep a p e r t o e n h a n c et h es e a r c hr e s u l t st ob ec l o s e rt ou s e rr e q u i r e m e n t sw h e nu s e r sn o t s a t i s f i e dw i t ht h e i rf i r s tr e s u l t i nt h ee n d t h ei n t e l l i g e n ts e a r c h i n gs y s t e mb a s e d t 幺f 目录 第l 章绪论 1 1 1 课题的研究背景及意义 1 1 2 国内外研究现状 2 1 3 研究内容及论文结构 5 第2 章智能搜索相关技术 7 2 1 智能搜索技术 7 2 2 信息检索模型 1 1 2 3 潜在语义分析模型 1 4 2 3 1 潜在语义分析的基本思想 1 4 2 3 2 奇异值分解 15 2 3 3 潜在语义分析模型示例 1 6 2 4 本章小结 2 0 第3 章智能搜索系统建模 2 1 3 1 智能搜索系统建模概述 2 1 3 2 文档处理模块 2 2 3 2 1 文档分词与词性标注 2 2 3 2 2 文档关键词选取 2 3 3 2 3 词汇 文档矩阵生成 2 4 3 2 4 索引生成 2 5 3 3 查询处理模块 2 8 3 3 1 查询分词与关键词选取 2 8 3 3 2 查询扩展 2 8 3 3 3 查询向量生成 2 9 3 4 匹配处理模块 2 9 3 4 1 词汇 文档矩阵的更新 一3 0 一 3 4 2 相似性度量 3 2 3 4 3 二次搜索 3 2 3 5 本章小结 3 3 第4 章基于潜在语义分析的算法 3 4 4 1 潜在语义空间中权重计算方法 3 4 4 1 1 潜在语义空间权值计算方法 3 4 4 1 2 概率权值法 3 5 4 2 潜在语义空间的构造 3 8 4 3 基于语义的查询扩展算法 3 9 4 3 1 词汇间相关性的计算 3 9 4 3 2 基于查询内容的扩展词选取策略 4 0 4 3 3 扩展词的权值确定 4 2 4 4 二次搜索策略 4 3 4 5 本章小结 4 5 第5 章潜在语义分析系统实现与评价 4 6 5 1l s a 搜索系统总体设计 4 6 5 2l s a 搜索系统设计与实现 4 7 5 2 1l s a 搜索系统文档集的选取 4 7 5 2 2l s a 搜索系统的实现 4 7 5 3 实验结果与分析 4 9 5 3 1 概率权值法实验 4 9 5 3 2 查询扩展实验 5 2 5 4 本章小结 5 3 结论 5 4 参考文献 5 6 攻读硕士学位期间发表的论文和取得的科研成果 6 0 致 射 6 l 1 1 课题的研究背景及意义 文字的出现是人类文明的重要标志之一 中国古代的活字印刷以及西方 现代印刷技术出现促进了人们对信息的获取与传播 对信息文本内容的理解 和应用是知识得以传播的主要手段 如今信息时代 因特网等飞速发展的技 术手段促使文本的出版 保存以及传播更加简便快捷 文本不仅仅指存在于 纸质媒介上的文字信息 它还涵盖计算机可处理的电子文档 这些文本包括 含有文本对象的电子文档以及以文本内容为主的各种文本组织形式 例如 网页 电子邮件 博客 短信等 随着i n t e r n e t 爆炸式增长 万维网已经发展成为包含多种信息资源 站 点遍布全球的巨大动态信息服务网络 为用户提供了一个极具价值的信息源 搜索引擎为用户提供了友好的检索接口 能帮助人们从浩瀚的数据中抽取出 对用户有用的信息 能极大地节省用户的查询时间 调查数据显示 目前有 6 8 2 的人经常使用搜索引擎 是目前仅次子电子邮件的网络应用 另有4 1 的人通过搜索引擎进入购物网站 8 4 6 的新网站是通过搜索引擎被发现 搜索引擎技术能帮助人们从浩瀚的数据中抽取出对用户有用的信息 能极大 地节省用户的查询时吲1 8 同时 科学证明 搜索引擎是未知状态下发现目 标信息的最有效方式 这些数据足以表明 先进的搜索引擎技术对于网民和 商业用户来说 都是极具实用价值的 日益增长信息的方便获取拓宽了人们视野 与此同时 海量的信息也引 发了诸多新的问题 例如 由各个网页间的不断转载造成的文本信息严重冗 余 由现有较为有限的查找手段造成无法精确找出淹没在浩瀚的繁杂信息之 中的有用信息 垃圾邮件以及垃圾短信泛滥 互联网上有害信息传播造成的 信息污染1 2 3 1 互联网上绝大多数的信息是以文本的形式保存的 互联网上文本信息的 r 素存在 相同概念可以有多种不同的表述方式 传统的基于关键词字符匹配 的搜索引擎中 参与匹配的只有外在的表现形式 而非它们所表达的全部概 念 用户很难简单地用关键词或关键词串来真实地表达真正需要查询的内容 把搜索引擎技术从关键词匹配的层面提高到语义的层面 从语义意义上智能 地认知和处理用户的查询请求成为当前搜索引擎技术的研究热点 1 2 国内外研究现状 信息检索是伴随科学技术的迅猛发展和信息量的巨大增长而发展起来的 研究与应用领域 3 l 随着人类信息生产的能力超过了人力对信息的处理 组 织和吸收能力 信息检索出现了一个重要分支即智能搜索 且战略地位日益 重要 信息检索的发展经历了三个大阶段 手工信息检索 机械信息检索和 计算机信息检索 1 5 其中计算机信息检索出现最晚 迅速发展成为信息的智 能搜索 1 9 5 4 年 美国海军兵器中心图书馆以i b m 7 0 1 设计并开发了计算机信息 搜索系统 它标志着智能信息搜索阶段的开始 进入8 0 年代 美国c o m e l l 大学c h r i sb u c k l e y 及其研究组人员开发研制 了s m a r t 系统 早期的版本用于i b m7 0 9 4 与i b m3 6 0 机器上 采用批处 理方式 其后又对s m a r t 系统使用c 语言进行了重写 在u n i x 操作系统下 运行 s m a r t 的实现涉及到许多理论 模型及技术 但主要特色在两方面 即空间向量模型及操作上的相关反馈 其思想为 对训练语料集a 设计一 个词语 文本矩阵 行表示文本中出现的词 列表示文本 当给定初始查询向 量后 矩阵a 通过查询转换 计算用户提问与训练集a 矩阵间的相似度 s m a r t 系统已应用于医疗 航空 图书管理等许多行业m 19 8 9 年 由a p p l ec o m p u t e r d o w j o n e s t h i n k i n gm a c h i n e d 和k p m g p e a tm a r w i c h 四家公司联合开发了广域信息服务器w a i s 它是i n t e m e t 上广 2 哈尔滨工程大学硕士学位论文 泛使用的最强有力的全文搜索系统 国际上一些著名的研究机构 例如美国 健康研究院 n m 美国技术与标准研究所 n i s t 等均采用w a i s 建立了 各自的全文数据库及搜索索系统 目前 国际上采用w a i s 系统在i n t e m e t 网络上建立的全文数据库及检索系统有5 0 0 多个 涉及到生物 天文 地理 农业 人文等各类信息 w a i s 系统软件在程序结构上由建立索引 实现检 索和服务器三部分组成 首先建立索引时对原始信息进行分析 抽提 整理 归纳 并建成字典库 根据字典库中的所有字 词 建立一个大的倒排文件 4 5 然后再根据不同的格式对原始信息集合抽提出一个文档以及相应的标题 文字等信息 建立标题文件 资源描述文件 目录文件等多级索引结构 搜 索时根据资源描述文件向服务器提交连接请求 服务器则判定客户是否有权 查询此系统 如果有权则建立服务器与客户端的连接 否则拒绝查询请求 1 9 9 1 年 美国m a s s a c h u s e t t s 大学依据推理网络研制出i n q r e r y 系统 它把信息搜索看成是事实的推理与证明过程 这个推理网络是一个有向图 节点表示有效事实 边表示事实间的依赖关系 从事实y 到事实x 的边表示 y 含有x 或y 导出x y 为x 的父节点 在网络中 每个节点都有一个链 矩阵 用来计算给定节点的父节点的概率 系统沿着有向图的边 依次分析 各节点的概率 最终将得到相对于用户提问的最后概率 输出时则按概率大 小把文件显示给用户 4 6 1 i n q r e r y 系统的提出 为智能信息搜索技术提供 了新的解决问题的思路 起到了极其重要的作用 2 0 0 1 年 卡耐基梅隆大学 c m u 开发设计并公布了l e m u rt o o l k i t 它 是一个新兴的实验系统 其特点是在信息搜索中引入了语言模型 更重要的 是 它不仅是一个完整的搜索系统 而且是以工具包的形式提供的 l e m u r t o o l k i t 的设计目标是促进和帮助在文本信息检索和语言模型方面的研究 包 括特定目标搜索 分布式搜索 跨语言搜索 文摘系统 信息过滤和文本分 类等各方面技术的研究 工具包支持对大规模文本数据建立索引 对文档和 查询构建简单的语言模型 同时实现了基于语言模型的智能搜索系统 整个 系统用c 和c 语言实现 可在u n i x 和w i n d o w s 系统下运行 4 引 的出自校园的搜索引擎 从1 9 9 7 年l o 月开始一直运行至今 天网 在增量 搜索技术 快速搜索技术 海量信息存储技术等方面都具有较强的优势 中科院的信息检索小组主要针对文本信息的检索开展研究 多次参加 t r e c 会议 取得了很好的研究成果 其开发的天罗检索系统在很多国家重 要的信息部门得到了广泛的应用 目前主要的研究方向包括w e b 信息的获 取 w e b 信息搜索等 中科院信息分析小组的研究主要集中在大规模多源异 构信息的分析与挖掘方面 主要包括文本分类与聚类 信息过滤 个性化服 务 自然语言问答和浅层自然语言处理等 小组研制了一系列文本信息加工 处理的实验平台 目前实验平台可以通过主页中 成果演示 进行演示 值 得一提的是小组开展的公开源码计划 其中的高性能分词系统i c t c l a s 得 到了研究人员的广泛认同与使用 哈工大信息检索研究室成立于2 0 0 1 年3 月 研究方向包括文本检索 问 答系统 自动文摘 文本挖掘和语言分析等 研究室以语言分析为基础研究 以文本过滤为应用研究 以信息抽取为语言分析从句子理解向篇章理解的延 伸 以句子检索为在语言分析和篇章理解的支持下的智能化精准检索技术 此外 中国学者乔鸿亮博士2 0 0 2 年开发了一个以现代语言技术为主导的 智能搜索引擎 并在2 0 0 5 年创办l e x x e 搜索 他提出互联网搜索引擎主要使 用的是符号计算 s y m b o l i cc o m p u t i n g 而l e x x e 最为根本的换代技术就在 于语言计算 l i n g u i s t i cc o m p u t i n g 上 两者的主要区别在于后者能把用户 所打入的文字以及所目录过的网页中的文字当作语言来处理 而不是符号来 处理 它已经有了相当的语言理解能力 通过以上对现有信息搜索发展的说明 基于语义的智能搜索系统是计算 机科学技术 计算机网络发展的需要 是人类与计算机自然交流的需要 是 用户更加方便 有效使用信息的需要 智能搜索系统的研究对于提高搜索的 4 r 1 1 1 1 应用前景 1 3 研究内容及论文结构 本文细致地研究了智能搜索技术以及潜在语义分析模型 提出了本文基 于潜在语义分析的智能搜索系统的建模方案 具体包括以下几点创新 1 本文探讨了基于潜在语义分析的信息检索模型 针对于该模型物理 意义不十分明确 提出概率权值法改善这个不足 概率权值法使得词汇 文档 矩阵有更明确的物理意义 可以很好的反映出词汇与文档之间 文档与文档 之间的语义关系 进而搜索结果更接近用户的查询需求 2 针对在信息搜索过程中用户查询语句简短或者查询词与目标文档中 的索引词不匹配的情形 提出基于语义的查询扩展算法进一步的改善了查询 结果不准确不全面的问题 查询扩展是指在原有用户查询语句的基础上加入 与之相关的新词 形成新的 语义更明确的用户查询 3 由于用户在搜索信息时目的不明确或者知识不足很可能造成遗漏查 询信息 从而使得返回结果不理想 对此 本文还提出二次搜索策略弥补该 缺陷 在二次搜索中 系统将以用户提交的文档为标准选择与该文档相似程 度大的相关文档返回给用户 保证了系统查询的准确性 本文的具体组织安排如下 第1 章介绍了搜索引擎的发展历史与发展趋势以及当前的研究热点 叙 述了智能信息搜索技术的国内外研究现状 并给出本文的内容结构及创新点 第2 章介绍智能搜索的相关技术以及信息检索模型的概念 并详细地分 析了潜在语义分析模型 第3 章详细论述了智能搜索系统的建模思想并给出具体的实施方案 系 统分为三大功能模块查询处理模块 文档处理模块 匹配处理模块 第4 章重点讲述了系统建模过程中的基于概率的概率权值计算方法 查 询扩展算法以及二次搜索策略 6 智能搜索技术是结合了人工智能等技术的新一代搜索技术 智能搜索技 术要求能提供传统的快速检索 相关度排序等功能 还能提供内容的语义理 解 用户角色登记 用户兴趣自动识别 智能信息化过滤和推送等功能 智 能搜索引擎设计追求的目标是 根据用户的请求 从可以获得的网络资源中 检索出对用户最有价值的信息 智能搜索引擎具有信息服务的智能化 人性 化特征 允许用户采用自然语言进行信息的搜索 为他们提供更方便 更确 切的搜索服务 2 1 智能搜索技术 1 搜索引擎 搜索引擎是指根据一定的策略 运用特定的计算机程序搜集互联网上晦 信息 在对信息进行组织和处理后 为用户提供检索服务的系统 搜索引擎并不真正搜索互联网 它搜集的实际上是预先整理好的网页索 引数据库 真正意义上的搜索引擎 通常指的是收集了互联网上几千万到几 十亿个网页中的每一个词 即关键词 进行索引 建立索引数据库的全文搜 索引擎 当用户查找某个关键词的时候 所有在页面内容中包含了该关键词 的网页都将作为搜索搜索结果被搜出来 在经过复杂算法进行排序后 这些 结果将按照与搜索关键词的相关度高低 依次排列 现在的搜索引擎已经普遍使用超链接分析技术 除了分析索引网页本身 的内容 还分析索引所有指向该网页的链接的u r l a n c h o rt e x t 甚至链接 周围的文字 所以 有时即使某个网页a 中并没有个词语 比如 信息传递 如果网页b 用链接指向这个网页a 那么用户搜索 信息传递 是也能找到 网页a 而且如果有越多的网页的 信息传递 链接指向网页a 那么网页 a 在用户搜索 信息传递 时也会被认为更相关 排序也会越靠前 l 哈尔滨工程大学硕士学位论文 按照搜索引擎的工作原理 大致可以分为四个步骤 从互联网上抓取网 页 建立索引数据库 在索引数据库搜索 对搜索结果的处理和排序 智能搜索引擎基于自然语言的检索形式 是建立在大规模的知识库基础 上 用一个强有力的推理机 根据用户所提供的以自然语言表达的检索要求 进行分析 然后形成检索策略进行搜索 用户只需把自己的要求输入计算机 就可以得到检索结果 使用户可以从繁琐的检索规则中解脱出来 自然语言 查询是智能搜索引擎的一个研究领域 自然语言查询从用户接口上分为两种 一种是输入自然语言的句子 把它切分并抽出多对组词 构成一个有限状态 机 然后去数据库进行匹配 对每一次检索出的记录进行频率累加 经过几 次检索后 按照命中频率进行排序 把最终的检索结果返回给用户 这只是 对查询请求进行了自然语言分析 另外一种是对目标文档也进行自然语言分 析 这不仅涉及到分词技术 词法分析 语法分析 语义分析 还涉及到篇 章结构的分析 就是要理解文章的意思 技术难度较大 目前还基本没有成 功应用于商业的模型 2 语义网 万维网 w o r dw i d ew e 由于其信息量的急剧增加 已造成严重的信息 超载 很多用户查找 访问 呈现 维护信息的难度也极大增加 这是因为 信息主要是用自然语言来表达的 在可用信息和支持用户查找 使用信息的 工具之间 一个巨大的鸿沟已经出现了 语义网是对未来网络的设想 在这 样的网络中 w 曲上的资源附加上计算机可以理解的内容 信息都被赋予了 明确的含义 便于计算机处理 即给出一种计算机能够理解的表示资源的手 段 使机器能够自动地处理和集成网上可用的信息 4 9 1 1 语义w e b 的含义 语义w e b 并没有严格的定义 t i mb e m e r s l e e 对语义w e b 做了这样的 描述 语义万维网并不是一个独立的万维网 而是对当前万维网的扩展 语 义w e b 上的信息具有定义良好的含义 使得计算机之间以及人类能够更好的 彼此合作 8 2 基于语义w e b 的知识表示和推理 语义w e b 依赖于将内容同形式化的意义表示对应起来 传统的知识表示 一直努力于将知识形式化 2 9 因此为设计语义w e b 的语言提供了一个很好的 起点 然而 w e b 的特性对传统的知识表达工作是一个挑战 需要从一个新 的角度来看语义w e b 上的知识表示 语义w e b 的研究目前还主要侧重于知 识表示与推理方面 语义w e b 上的知识表示和推理需要考虑以下问题 传统 的知识表示通常是集中式 w e b 是分布式的 由于对信息缺少集中控制 容 易出现同义和一词多义现象 此外信息的可靠性也得不到保证 w e b 的开放 性和动态性使推理系统需要采用开放世界假设 o p e nw o r l d a s s u m p t i o n 推 理较复杂 w e b 的数量巨大 累计起来的知识库也将使推理很难进行 3 语义w e b 的体系结构 由于语义w e b 的知识表示具有分布性 同时又具有应用上的通用性 语 义w e b 需要一个统一的框架满足分布性 安全性以及互操作性 t i m b e m e r s l e e 提出的语义w e b 体系结构是学术界公认的标准框架 语义w e b 的体系结构参见图2 1 在语义w e b 的七层结构中 x m l r d f 以及本体三层主要用于表示语 义信息 因而是语义w e b 系统的核心和关键技术 基于语义网的搜索技术中重要的发展趋势是以本体推理为基础的知识型 语义搜索 这一类型的语义搜索以本体构建的知识库为主体 通过本体知识库 推理实现知识发现型的语义搜索 1 0 1 根据搜索对象的不同有概念搜索和关联搜 索 由于语义w e b 技术尚不成熟 w e b 搜索也处于不断探索阶段 语义搜索 将在未来的一段时间内一直是一项非常艰巨而又十分具有挑战性的工作 9 哈尔滨工程大学硕士学位论文 图2 1 语义网体系结构 3 自然语言处理 自然语言处理是计算机科学领域与人工智能领域中的一个重要方向 它 研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法 实 现人机间自然语言通信 或实现自然语言理解和自然语言生成是困难 其根 本原因是自然语言文本和对话的各个层次上广泛存在的各种各样的歧义性或 多义性 自然语言处理技术主要用于文本的内容分析 关键技术主要包括词 法分析 句法分析 语义分析和语用分析等 句法分析是判断词的结构 类别和性质的过程 词法分析的第一步是分 词 分词是后续进一步处理的基础 词法分析另一个重要任务是标注每个词 在上下文句子中的词性 词性标注也经过了从规则方法到统计方法的过程 句法分析是将线性的此序列转变成某种句法结构的过程 语义分析的主要目 标是确定每个语言单位在文中的某种语义类以及这些语言单位之间的语义关 系 4 1 4 2 智能搜索技术中常常使用到的自然语言处理技术包括去除停止词 取词 根 词性标注 词义消歧 句法分析 命名实体识别 指代消解等 自然语 言处理资源包括的则是w o r d n e t 和h o w n e t 这样的词典 研究者们还将自然 语言处理针对信息搜索任务进行优化 例如用于信息搜索结果的智能显示 1 0 用于获取用户查询的上下文信息从而把最佳结果返回给用户 3 2 1 2 2 信息检索模型 信息检索的基本原理与机制是系统对文档集合与查询集合的匹配与选 择 要更准确 更严密地表述 论证这一原理 要有效地实现这一机制 就 要依靠数学土具 即需要建立信息检索的数学模型 运用数学的语言和工具 对信息检索系统中的信息及其处理过程加以翻译和抽象 表述为某种数学公 式 它被演绎 推理 解释和实际检验 反过来指导信息检索实践f 6 3 4 1 简 单的讲 信息检索系统可以表达成图2 2 所示模型 文档查询 图2 2 信息检索模型示意图 1 布尔模型 在这种模型中 候选查询文档d 由关键词的逻辑组合表达式表示 用户 查询q 由布尔表达式表示 那么 相关度r d q d q 即当d q 成 立时 r d q 1 否则 r d q o 例如 d c o m p u t e r 八g r a p h i c s 八i n t e r f a c e 八u s e r q c o m p u t e r 入 g r a p h i c svi n t e r f a c e i f d qt h e nr d q 1 这种方法的主要问题是 相关度为二值逻辑 要么为1 要么为o 也就 是说 候选文档与用户查询语句要么相关 要么无关 这在实际情况下是不 合理的 另外 作为终端用户 一般很难正确快速的给出用户查询语句的布 尔表达式 9 1 2 向量空间模型 向量空间模型的基本思想是 整个向量空间由不包含停用词的关键词构 1 1 一 丽2 d q 筹协3 s i m d q 蘸尚 一 其实 还有很多方法用于度量两个向量之间的相似性 这里不再一一赘述 3 概率模型 概率模型的基本思想是 给定查询语句q 候选文档d 用r 表示d 和 o 相关 r 表示d 和o 不相关 那么 估计概率p rd q 和p rid q 根据概率p rd q 或p rd q 大小 选取搜索的文档 根据贝叶斯公式 尸 r i q p d i r 反 q z i 互p 广 r q o cp l r q p l r q 2 5 假定文档 x 其中 寞端 那么 h p 1 p 1 一而 l f p d r q r i p x l i 瓦 而p 工 o 匮 俨而 2 6 兀q 产 1 q 1 刮 2 7 f f 文档与查询的相关度 即删 矽 g 刺 亿8 假设一组训练样本共有 个文档 其中r r 个与查询q 相关的文档 一 足个不相关的文档 r 个相关文档中有n 个文档包含关键词矗 盈一n 个文档 不包含关键词 一尼个不相关文档中有刀f n 个包含关键词 一r f n i 厂f 个不包含关键词珞 如表2 1 所示 表2 1 训练样本数目关系 相关文档不相关文档 数量r fn r 包含矗的文档数nn i r i 不包含岛的文档数尺f nn r i n i r i 于是 得到相关度 邶翩 g 渊 p g 警鬻亿9 概率模型在理论上具有良好的数学基础 但在不作化简的情况下 实现 起来比较困难 其有效性收到很多因素的影响 2 7 4 语言模型 语言模型在很多问题上有着广泛的应用 因此演变出许多模型 如文档 模型 查询模型 差异模型和翻译模型等 1 3 r 1 1 文档模型的基本思想是 假定查询q 是由文档d 的概率模型产生的 并 由此对文档进行排序 给定查询q q l q e q 3 孙 g f 为查询词 和文档d 那 么模型的任务包括 建立文档的语言模型m d 根据概率p qim d 对文档 进行排序 查询模型的基本思想是 假定查询q q l q e q 3 q m 文档d 均采样自一个 未知的相关模型r r 刻画了q 和d 在查询相关文档中的概率分布 从相关 模型r 经过k 次采样 观察到查询q 估计第k 1 次采样观察到文档中的词 w 的概率 4 0 j 差异模型的基本思想是 通过对计算文档模型和查询模型之间的 k u l l b a c k l e i b l e r 差异 k l 距离 根据k l 距离大小对候选文档进行排序 因此 该模型的主要任务包括 估计文档模型p qjm d 以及查询模型p wr c 计算文档模型和查询模型的k l 距副1 7 翻译模型的基本思想 把查询q q l q e q 3 q m 看作是文档d 在同一语言 内的翻译 并根据翻译的概率大小对候选文档进行排序 4 2 3 潜在语义分析模型 潜在语义分析 l a t e n ts e m a n t i ca n a l y s i s 或者潜在语义索引 l a t e n t s e m a n t i ci n d e x 是1 9 8 8 年s t d u m a i s 等人提出了一种新的信息检索代数模 型 是用于知识获取和展示的计算理论和方法 它使用统计计算的方法对大 量的文本集进行分析 从而提取出词与词之间潜在的语义结构 并用这种潜 在的语义结构 来表示词和文本 到达消除词之间的相关性和简化文本向量 实现降维的目的 2 3 1 潜在语义分析的基本思想 潜在语义分析的基本思想是 把高维的向量空间模型 v s m 表示中的 文档映射到低维的潜在语义空间中 这个映射是通过对词汇 文档矩阵的奇异 值分解 s v d 来实现的1 2 1 4 因为每个文档可以看做以词语为维度的空间中的一个点 一个带有语义 的文档出现在这个空间中 所以它的分布绝对不是随机的 而是服从某种语 义结构 同样每个词语也可以看做为以文档为维度的空间中的一个点 文档 的语义是由一个个的词语够成的 而词语又要放到其所在文档中去理解 体 现了一种 词语一文档 双向的概率关系跚 这种语义结构对词语的出现 和文档的构成发挥作用 潜在的隐藏于文本当中 但是由于文档内容的不确 定和词语使用的任意性等因素的存在 导致这种潜在的语义结构并不明显 8 1 l s a 利用奇异值分解降秩的方法处理文档和词语 以达到信息抽取和去除噪 声的目的 向量空间模型 v s m 中文档使用高维向量表示 而是l s a 不同 于v s m 而是将文档的高维表示投影在低维的潜在语义空间中 减小了问题的 规模 并且使得原本稀疏的数据不再稀疏 进而呈现出潜在的语义结构 3 5 1 其蕴含的思想是通过语义处理给定词的所有上下文 提取决定词语语义相关 性的相互相互制约关系 2 3 2 奇异值分解 奇异值分解 s i n g u l a rv a l u ed e c o m p o s i t i o n s v d 是潜在语义分析的基 础理论 它是数理统计中常用的方法之一 在不受限的最小立方问题 矩阵 阶次估计和规范相关分析等问题的解决方案中广泛使用 定义 设a 是聊 玎实矩阵 称1 1 阶方阵a r a 的非负特征值的算术平方根 为矩阵a 的奇异值 定理 设a r 秩为r 则存在m 阶正交矩阵u 和1 1 阶正交矩阵v 使得 u r a v i 0 l oo j 称彳 u i 言三i y r 为矩阵a 的奇异值分解 文本信息检索应用的是一种特殊形式的奇异值分解 因为在文本信息检 索问题中需要进行奇异值分解的矩阵一般都是高维稀疏矩阵 假设词汇 文档矩阵a 是m 行n 列的矩阵 其中m n 且r a n k a r r 哈尔滨工程大学硕士学位论文 则a 为m x n 的稀疏矩阵 由奇异值分解定理 可得a 的奇异值分解为 口 口q m xm 躅m x d 图2 3 奇异值分解示意图 2 3 3 潜在语义分析模型示例 下面用一个简单的示例来说明l s i 在信息搜索中应用的效果 由于本示 例的样本数较少 无法体现出权重的统计意义 因此在此不考虑对词汇进行 词汇 文档矩阵的加权因素 假设有9 个文档 分为两类c 与m 内容如表 2 2 所示 表2 2 小型文档集 标号文本内容 c lh u m a nm a t c h i n gi n t e r f a c ef o rl a ba b c c o m p u t e ra p p l i c a t i o n s c 2a s u r v e yo f u s e ro p i n i o no f c o m p u t e rs y s t e mr e s p o n s et i m e c 3 t h ee p su s e ri n t e r f a c em a n a g e m e n ts y s t e m c 4 s y s t e ma n dh u m a ns y s t e me n g i n e e r i n gt e s t i n go fe p s c 5r e l a t i o no fu s e r p e r c e i v e dr e s p o n s et i m et oe r r o rm e a s u r e m e n t m lt h eg e n e r a t i o no fr a n d o m b i n a r y u n o r d e r e df l e e s m 2t h ei n t e r s e c t i o ng r a p ho fp a t h si nf l e e s m 3 g r a p hm i n o r si v w i d t h so ft r e e sa n dw e l l q u a s i o r d e r i n g m 4 g r a p hm i n o r s as u r v e y 1 6 条目c 1c 2c 3c 4c 5m 1m 2m 3m 4 h u m a n10 0 1 000oo i n t e r f a c el010o0o00 c o m p u t e r 11oo00o0o u s e r0l1o100oo s y s t e r n ol12ooo0o r e s p o n s e 01oo10ooo t a m e0loo1o ooo e p soolloo 0oo s e r v e y o 1 o0 0o0o1 t r e e s 0 0 0 0 0 l l1o g r a p h 000oool1l n u n o r s0ooooo011 即 x 根据公式对x 进行奇异值分解后得到 1 7 o o 0 o o o 0 o 1 o 1 1 0 o o 0 0 o o 0 0 1 l 1 o 0 o o 0 0 o o 0 1 1 o o 0 0 o o o o o o 1 o o o o o l o 1 1 o o o 0 o 1 0 0 o 2 o 0 l o o 0 0 o 1 0 1 1 o o 1 0 o 0 o 0 0 l l 1 1 1 o 1 0 0 0 1 l 1 o 0 0 o o o 0 o o r o s o d o o 2 2 一o 1 l 0 2 9 0 4 1 0 1 l 一0 3 40 5 2 0 0 6 0 4 1 0 2 0 一 0 0 70 1 4 0 5 50 2 80 5 0一0 0 7 0 0 1 0 1 l 0 2 40 0 4 0 1 6 一o 5 9 0 1 l o 2 5 一o 3 00 0 60 4 9 0 4 00 0 6 0 3 40 1 00 3 30 3 80 0 0o o oo 0 1 0 6 4 0 1 7 0 2 70 1 l o 2 7o 1 1 o 3 0一0 1 4 0 2 1o 2 7 o 0 10 4 9 0 0 40 6 2 o 0 30 4 5 3 3 4 2 5 4 o 2 0 o 0 6 o 6 1o 1 7 0 4 6 0 1 3 0 5 4 0 2 3 0 2 8o 1 l 0 0 00 1 9 o 0 1o 4 4 o 0 2o 6 2 0 0 8o 5 3 0 3 6 0 4 3 0 4 3 o 3 3 0 1 8 0 2 3 o 2 2 0 1 4 2 3 5 1 6 4 o 11 一o 5 0 o 2 1 o 5 7 0 5 1 0 1 0 o 1 9 o 2 5 o 0 8 0 3 3 0 0 7 0 0 7 o 1 9 一o 0 3 o 0 3 o 0 0 一o 0 1 1 5 0 o 9 5 0 0 3 0 0 4 o 2 7 o 1 5 0 0 2 o 0 2 o 0 l o 0 3 一o 1 6 o 0 8 o 0 8 o 1 l 一0 5 4 o 5 9 一o 0 7 一o 3 0 1 3 1 o 0 5 一o 2 1 o 3 8 一o 2 l o 3 3 0 3 9 o 3 5 o 1 5 一o 6 0 如果只保留x 的前两个奇异值 那么 1 8 一o 2 1 一o 1 7 一o 1 7 o 2 7 o 0 8 0 3 9 o 1 1 o 2 8 o 8 5 0 1 7 0 2 8 o 2 8 o 0 3 0 4 7 一o 2 9 o 1 6 0 3 4 o 5 6 o 3 6 0 0 3 一o 0 2 一o 0 2 一o 0 2 0 0 4 0 2 5 0 6 8 0