（基础数学专业论文）基于形式概念分析和本体的移动搜索引擎研究.pdf

中央民族人学硕i j 学位论文 例开发实现搜索引擎，有效地提高搜 准确性，为搜索引擎智能化的提升找 语义网，本体，移动搜索引擎 ! 羔嬲必炒 a b s t r s c t f o r m a lc o n c e p ta n a l y s i si sat h e o r yo fd a t aa n a l y s i sw h i c hb a s e do n t h es t r u c t u r eo fl a t t i c e e v e rs i n c ei th a se m e r g e d ，t h i sm e t h o da t t r a c t st h e b r o a da t t e n t i o nf r o mt h er e s e a r c h e r sa c c o r d i n gt ot h ec l e a r ，c o n c i s ea n d c o m p l e t eo fk n o w l e d g ed e s c r i p t i o n n o wi th a sa l r e a d yb e e na p p l i e di n m a n yf i e l d s ，s u c h a ss o f t w a r e e n g i n e e r i n g ，l i b r a r y a n di n f o r m a t i o n s c i e n c e ，d a t am i n i n ge t c t h eo n t o l o g yi st h ed e f i n i t ea n df o r m a ld e s c r i p t i o no ft h es h a r i n g c o n c e p tm o d e l t h eo n t o l o g yi sm a d eu pb yt h er e l a t i o n so f t h ea c c u r a t e l y c o n c e p t s ，p r o v i d i n gt h ec o m m o nu n d e r s t a n d i n ga n dd e s c r i p t i o no fo n e f i e l d t h eo n t o l o g yi su s e db yt h ec o m p u t e ra n dg i v e nt h em a t h e m a t i c e x p r e s s i o n ，a c h i e v i n gt h ei n f e r e n c eo fo n ef i e l d h e n c e ，t h eo n t o l o g yc a n b eu s e dt oi m p r o v et h ed e g r e eo fa c c u r a c yo fi n t e r n e ts e a r c h si n c et h ee m e r g e n c eo fs e a r c he n g i n e si n19 9 0a n da f t e ry e a r so f d e v e l o p m e n ts of a r ，i th a sb e e n o b t a i n e dl o t s o fa c h i e v e m e n t si nt h e i n f o r m a t i o no r g a n i z a t i o n ，i n f o r m a t i o ns e a r c hm o d e la n ds e q u e n c i n g m e t h o d b u tt h es e a r c he n g i n e ss t i l lh a v es o m eo b v i o u sd e f e c t s ，s u c ha s ( 1 ) n o tf u l l yu n d e r s t a n do ft h ec l i e n t s s e a r c hd e m a n d ；( 2 ) t h es e a r c h r e s u l t sa r el i m i t e db yt h es i m p l ei n f o r m a t i o nr e t u m i n g ；( 3 ) s e q u e n c i n g a l g o r i t h mr e l i e so nt h eo u t s i d ef e a t u r eo f t h ed o c u m e n te x c e s s i v e l y t h e s e p r o b l e m sm u s tb e e ns o l v e db yt h en e w m e t h o d 圭叁垦鳖叁兰竺土兰竺堡皇 t h i st h e s i sf o c u s e so nt h es e a r c h f u n c t i o nb a s e do ni m p r o v i n gt h e t r a d i t i o n a lm o b i l es e a r c he n g i n e s t h ef o l l o w i n gi so u rm a i nr e s e a r c h w o r k s ： 1 t h i sp a p e ra n a l y s e st h ed e f e c t so ft h es e a r c he n g i n e s ，i n t r o d u c e s t h em e t h o do ft h eo n t o l o g yw h i c hi se s t a b li s h e db yu s i n gf o r m a lc o n c e p t a n a l y s i s ，a n dg i v e st h eb a s i ce f f e c ta n dv a l u eo fd e s i g n i n gt h es e a r c h e n g m e s 2 t h i sp a p e rg i v e st h ea s s u m p t i o no fr e a l i z i n gt h em o b i l es e a r c h e n g i n e sb yf o r m a lc o n c e p ta n a l y s i sa n do n t o l o g y 3 t h i sp a p e rg i v e st h ee x a m p l eo fs o m em o b i l ep h o n e st or e a l i z e s e a r c h e n g i n e s ，i m p r o v i n gt h ee f f i c i e n c ya n da c c u r a c yo fs e a r c h ，a n d g i v e st h ew a y t op r o m o t ei n t e l l i g e n ts e a r c he n g i n e s k e yw o r d sf o r m a lc o n c e p ta n a l y s i s ，c o n c e p tl a t t i c e s ，s e m a n t i cw e b , o n t o l o g y ，m o b i l es e a r c he n g i n e s i v 中央民族人学顺i ：学位论义 目录 摘要1 a b s t r s c t i i i 目录v 第一章引言l 第一节奉义的研究背景l 第_ 节奉义的t 作2 第二章预备知识3 第一节形式概念分析3 一、序和格基本理论3 二、形式概念分析基本理论6 三、概念格的生成算法l o 第二节语义1 ) c ) 9 与奉体1 3 一、语义网1 3 二、本体l 5 l 、本体概念15 2 、本体构建1 6 第三章搜索引擎的设计与实现1 8 第一节需求分析一1 8 第一节设计过程2 0 第三节实例展示2 2 第四节补允说明3 l 第四章总结与展望3 2 参考文献3 3 攻读学位期间发表的学术论文目录3 6 中央民族大学研究生学位论文作者声明。3 7 到l 谢3 8 v 中央民族大学硕上学位论文 第一节本文的研究背景 第一章引言 互联网的产生和发展为人类带来了一场伟大的信息革命，它彻底改变了信息 生产、信息加工、信息组织、信息获取、信息传播和信息利用的方式。据调查显 示，信息获取是用户上网的主要目的之一，而有超过7 0 以上的用户选择搜索引 擎作为信息获取的主要方式。可见，搜索引擎己成为人们工作、学习乃至网络生 活所不可或缺的“神兵利器 。 人们普遍认为，现代意义上的搜索引擎的祖先是1 9 9 0 年由m o n t r e a l 的 m c g i l l 大学学生a l a ne m t a g e 、p e t e rd e u t s c h 和b i l lw h e e l a n 发明的a r c h i e 。 1 9 9 4 年1 月，第一个既可搜索又可浏览的分类目录e i n e tg a l a x y 上线。 1 9 9 4 年4 月，斯坦福大学的两名博士生，美籍华人杨致远和d a v i df i l o 共同 创办了超级目录索引y a h o o ! 。 1 9 9 9 年，g o o g l e 完成了从a l p h a 版到b e t a 版的蜕变，凭借其具有突破性的 p a g e r a n k 技术和超文本匹配分析技术，g o o g l e 始终保证将最重要的搜索结果首 先呈现给用户。 2 0 0 3 年8 月，中国搜索联盟率先推出第三代智能搜索引擎，并被新浪、搜 狐、网易、t o m 、中国网、2 6 3 及中国搜索联盟等1 4 0 0 家网站采用，改变了国 内搜索引擎市场格局。 2 0 0 4 年陈沛提出了“个性化信息门户”理念，并推出全球第一款桌面搜索 引擎“网络猪 。 经过十几年的风雨历程，搜索引擎进入了高速发展时期，互联网进入搜索引 擎时代。搜索引擎在信息组织方式、信息检索模型、排序方法等方面取得了丰硕 的成果，g o o g l e 的巨大成功便是明证。但尽管如此，搜索引擎仍存在一些明显 的缺点和不足，主要表现在：( 1 ) 对用户的检索需求理解不足：( 2 ) 查询结果仍 中央民族大学硕士学位论文 局限于简单的单信息返回机制；( 3 ) 排序算法过分依赖文档( 页面) 的外表特征。 这些问题的解决必须依靠全新的信息组织理论、信息检索模型以及排序算法【l l 。 形式概念分析，即f c a ( f o r m a lc o n c e p ta n a l y s i s ) 1 2 1 ，是应用数学的一个 分支，其核心的数据结构是概念格，它从外延和内涵两方面对概念进行符号形式 化描述，实现计算机可以理解的语义信息。概念格通过h a s s e 图生动简洁地体现 概念之间的泛化和特化关系。 本体( o n t o l o g y ) 是关于领域知识的概念化、形式化的明确规范，是对领域 知识的共同理解与描述1 3 i 。本体需要以某种基于逻辑的语言来表达，从而完成对 类、属性和关系的详细、精确、一致、良好的表达。本体及其推理能力代表了现 代信息组织特别是网络信息组织的发展趋势，它不仅有利于信息的形式化描述， 而且依据本体这种信息组织方法而建立的检索系统，更能满足用户进行语义检索 特别是智能检索的需要。 形式概念分析建立在完备格理论之上，用形式化的语境将组成本体的概念、 属性以及关系等表述出来，然后根据语境，构造出概念格，即本体，从而清楚地 表达出本体的结构。这种本体构建的过程是半自动化的，在概念的形成阶段，需 要领域专家的参与，识别出领域内的对象，属性，构建其间的关系，在概念生成 之后，可以构造语境，然后利用概念格的生成算法，自动产生本体1 4 , 5 , 6 , 7 ，8 9 l 。利 用本体在概念描述上的确定性及其强大的语义揭示能力在数据层面有力地保证 了推理的有效性，从而为搜索引擎的设计开发提供了契机。 第二节本文的工作 本文从增强传统搜索引擎的搜索功能入手，重点做出以下几点工作： 1 分析了现有搜索引擎的缺点，介绍了使用形式概念分析建立本体的方法， 论述了两者对于设计搜索引擎的基础作用和价值。 2 用形式概念分析和本体作为基础工具，提出利用两者的结合设计实现移 动搜索引擎的构想。 3 以部分手机产品族为实例开发实现移动搜索引擎，有效提高搜索引擎的 检索效率和提升检索的准确性，为搜索引擎智能化的提升找到切实可行的途径。 2 中央民族大学硕士学位论文 第二章预备知识 形式概念分析基于序理论，尤其是基于完备格理论；本体是实现语义网的关 键技术，通过本体可以很好地解决语义网的语义描述和二义性问题。本章的主要 内容就是介绍一些相关的基础知识本章分为两节，第一节介绍形式概念分析方 面的一些基本知识和结论，第二节介绍一些语义网和本体方面的一些基本知识和 结论 第一节形式概念分析 在本节中，作为基础工具之一，我们对形式概念分析进行介绍，首先回顾序 理论和格理论的基本知识，然后介绍一些形式背景、概念和概念格方面的一些基 本知识和结论，最后介绍一种概念格的生成算法。由于篇幅有限，更多知识请参 考文献 2 ，1 1 ，1 2 ，1 3 】 一、序和格基本理论 定义2 1 集合m 和之间的一个二元关系尺是有序二元组沏，刀) 的集合， 其中m m ，胛n ，即尺mxn ，( m ，刀) r ，也经常写作m r n 如果m = n ， 则称尺是m 上的二元关系此外，还用厅1 表示刀的逆关系，即 nr l m 铮m r n 定义2 2 设s 是集合p 上的一个二元关系，且满足下列条件：y x ，y ，z p 。 ( 1 ) xsx ( 自反性) ； ( 2 ) x - y ，ysz 号x sz ( 传递性) ； ( 3 ) xsj ，ysxjx = y( 反对称性) 则s 称为户上的一个偏序( 关系) ，一个集合尸及其上的偏序s 形成的有序二元组 ( 尸；5 ) 称为偏序集 中央民族大学硕士学位论文 在不至混淆的情况下， ( 尸；) 也经常简记为p 定义2 3 设p 是一个偏序集，r ，少p ，称x 被j ，覆盖( 或者j ，覆盖x ) ， 如果z 少且不存在z p 使得r z y 记为x j ， 定义2 4 设p 是一个偏序集，x ，y p ，如果有xsj ，或者有y5x ，称x ， y 是可比较的，否则称为是不可比较的如果p 的一个子集中任何两个元素都是 可比的，则称这个子集为链 定义2 5 设尸是一个偏序集，x ，j ，p ，由xny 的一个长度为”的极大 链指的是序列x = x o x l _ 耽一 h 中央民族大学硕士学位论文 一_ 一 l o e n d l1e n di f ： 12 c 【i 】 h ：i l x ( h ) l | = i ) ； c l a s sp a i r si nb u c k e t s w i t hs a m ec a r d i n a l i t yo ft h e x s e t s ) 1 3 c 。 i o ：f i n i t i a l i z et h ec s e t s 14ft r e a te a c hb u c k e ti na s c e n d i n gc a r d i n a l i t yo r d e r ) 1 5f o ri ：0t om a x i m u mc a r d i n a l i t yd o 1 6f o re a c hp a i rhi nc i 】 1 7 i fx ( h ) f 【 x 牛) ) t h e n m o d i f i e dp a i r 1 8 a d dx 宰t ox ( h ) ； 1 9 a d dht oc 【i 】； 2 0 i fx ( h ) = f 【 x 木 ) t h e ne x i ta l g o r i t h m 2 1e l s e o l dp a i r ) 。 2 2i n t h ； 2 6 m o d i f ye d g e s 2 7f o r j ：0t ol l i n t l - i 2 8f o re a c hh a c d 】 2 9i x ( h 。) ci n t h ai sap o t e n t i a lp a r e n to f h n ) 3 0p a r e n t h n 3 8 e n di f 3 9 e n di f 4 0 e n df o r 4 le n df o r ； 4 2 i fi n t = p ( x 搴 ) t h e ne x i ta l g o r i t h me n d i f 4 3e n di f 4 4e n di f 4 5e n df o r 4 6e n df o r 4 7e n d r e n d a d d 1 2 中央民族大学硕士学位论文 第二节语义网与本体 本体是语义网最核心的技术。在本节中，我们对作为开发实现移动搜索引擎 的另一项基础工具本体进行介绍。首先介绍语义网的相关知识，然后对本体 进行研究，为后面移动搜索引擎的设计做好铺垫。 一、语义网 简单地说，语义网就是带有显式语义信息的万维网，这些语义信息可以被机 器“理解和处理 ，进而从根本上改变目前网络的工作模式以及人们的生活方 式。因此语义网终将会像目前的万维网一样普及，并应用到社会生活的每一个角 落【1 0 】。基于目前的技术发展水平，语义网及其核心技术已经在知识管理、电子 商务和w e b 服务等方面崭露头角，并显式出其独特优势。 w e b 的高速发展使得它很快成为一个庞大的知识库，但同时带来很多问题。 首先，以往的w 曲技术都忽略了计算机的处理作用：计算机在其中主要扮演了 展现信息的作用，而很少参与信息的处理，这使得很多智能应用无法在w e b 上 实现。其次，w e b 规模的快速膨胀使得整个w e b 上大部分有用信息无法得到有 效利用。为解决这些矛盾，近年来提出的语义网就是要通过实现文档语义与文档 结构的分离，达到使文档具有机器可处理的语义，从而解决传统w e b 无法解决 的一些问题。 根据语义网的创始人b e r n e r s l e e 的观点【2 7 1 ，语义网并非是全新的w e b ，而 是对现有w e b 的扩展。它与传统w e b 的不同在于，信息的语义在语义网环境下 能够很好地加以定义，并使得计算机和人类能够更好地协同合作。或者说，语义 网的目标是让w e b 上的信息能够被机器理解，从而实现w 曲信息的自动处理， 以适应w 曲资源的快速增长，更好地为人类服务。 w 3 c 是这样阐述语义网的：将机器能理解的数据发布在w e b 上正成为很多 组织最优先考虑的工作，只有w 曲成为一个自动工具和人能够共享和处理数据 的平台，它的潜能才可能全部发挥。对于w e b 这个范围来说，未来的程序必须 能够共享和处理数据，即使它们是独立设计的。语义网是这样的一个设想：使 w e b 上的数据能以一种可以被机器所理解的方式定义和联系起来，它不仅仅以显 中央民族大学硕士学位论文 示为目的，而是为了自动集成和重用不同平台中的数据。 在语义网环境下，w e b 上定义和链接的数据不仅能显示，而且可以被机器自 动处理、集成和重用。只有当数据不仅可以被人而且可以被机器自动地共享和处 理的时候，w e b 的潜力才发挥到极致。但是，“机器可理解 并不意味着机器能 够理解人类的语言，它只是说明：机器根据明确定义的数据，通过执行明确定义 的操作，来解决明确定义的问题。 现在万维网上的大部分内容都是设计给人阅读的，并不是t 卜计算机程序按网 页的内容自动进行处理。语义网的目的就是扩展当前的万维网，使其能够表达可 以被计算机所理解的语义，以便于人与计算机以及计算机和计算机之问的交互与 合作。 语义网的最大优点就是对网络信息的理解和处理能力。通过加入可以被计算 机理解的语义，从而使得对文本含义的理解并不再是人的专利，利用计算机同样 也可以完成相同的工作。 例如，对于文本“计算机，当我们看到这三个字时，我们首先会想到这 是一个与我们日常学习、工作和生活息息相关的具有实物形态的工具，甚至就是 我们手头正在使用的“东西 ；更进一步，我们知道“计算机一这一文本既不 代表数字，也不代表某一动作，而是一个名词概念；并且就此概念我们可以说出 一系列与之相关的信息，如它的基本组成、配置和功能等。因此，我们可以很好 地理解“计算机 这一文本所代表的含义。而对于机器而言，事情就没有那么简 单了。它非但不知道“计算机 这一文本所代表的一系列含义，甚至连这一文本 代表的是数字还是字符都不知道。因此语义网的主要任务之一，就是要以某种方 式或方法明确地告诉计算机某一文本的具体含义。 再如，对于网上书店关于某本书的介绍，我们可以很容易地分辨哪一项表示 的是书的题名、哪一项表示的是作者，哪些数字表示的是书的售价，哪些数字表 示的是i s b n 号等。但对于计算机而言，事情却远非如此简单。因为它不知道在 关于此书的介绍中，哪一项是书的题名、哪一项是书的作者，甚至连该项表示的 是数字还是字符串都无从知晓。因此语义网的主要目的之一就是要在隐藏的编码 中明确指出每一项的具体含义，从而达到计算机理解的目的。 “理解 只是语义网工作的第一步，更重要的是语义网可以使计算机在理解 1 4 中央民族大学硕士学位论文 之后，根据已有的数据和规则进行逻辑推理和自动处理。这一般是通过智能代理 来完成的。智能代理是一段设计好的程序，它可以帮助人们自动完成某些工作。 例如对于一个用于电子商务的购物代理，当我们把购物需求提交给代理程序以 后，它会在网上自动搜索符号我们条件的商品，并比较其中的不同，根据我们设 定的规则决定目标商店，在验证目标商店的真实性与可靠性之后主动提交订单。 语义网及其具有革命性的智能推理与代理技术，将在很大程度上改变现有互 联网的运行模式甚至人们的生活方式。互联网上数以亿计的网页信息蕴藏着无尽 的资源，它们将通过语义网释放出巨大的能量。 二、本体 本体( o n t o l o g y ) 的概念最初起源于哲学领域，用于研究客观世界的本质。 本体是实现语义网的关键技术，通过本体可以很好地解决语义网的语义描述问 题。在语义网范畴内，本体是关于领域知识的概念化、形式化的明确规范【1 1 。 1 、本体概念 本体最早是一个哲学上的概念。随着人工智能的发展，本体被人工智能界给 予了新的定义。然而，最初人们对本体的理解并不完善，对本体的定义也在不断 地发展变化中。其中最为大家普遍接受的关于本体的定义是，本体是共享概念模 型的明确的形式化规范说明。 本体体现的是共同认可的知识，反映的是相关领域中公认的概念集，它所针 对的是团体而不是个体。本体的目标是捕获相关领域的知识，提供对该领域知识 的共同理解，确定该领域内共同认可的概念，并从不同层次的形式化模式上给出 这些概念和概念之间相互关系的明确定义。我们可以理解为本体就像一部规范的 字典，能够有效的解决语义异构的难题。 定义2 3 2 本体是一个二元组，由概念以及概念之间的关系构成，记作 0 = 。其中c 为概念集合，r 为关系集合【2 引。该结构反映了对领域知识的 基本认知，“概念”和“关系”这两个概念为基本的分析工具。为了以图的形式 把本体的结构展现给用户，需要使用本体推理机制得到一个关系的定义域和值 域，当得到所有关系的定义域和值域时，本体的图结构就展现出来了。 中央民族大学硕士学位论文 在语义网信息组织中，本体的优势和作用主要体现在： ( 1 ) 概念描述。构成本体的概念及其之间的关系是经过精确定义的。 ( 2 ) 语义揭示。本体具有比其他同类工具更强的表达能力，可以揭示更为 丰富的语义关系。 ( 3 ) 一致性。本体作为领域知识的明确规范，可以保证语义表达的一致性， 从而彻底解决一词多义、多词一义和词义含糊现象。 ( 4 ) 推理支持。本体主要是为计算机所使用并可用数学方式表达，在概念 描述上的确定性及其强大的语义揭示能力，在数据层面有力地保证了推理的有效 性。 特定领域的本体能够形式化表达领域中的各种概念及概念之间的关系，从而 将术语的语义表达出来，因而在语义查询和复杂推理方面发挥着重要的作用，这 正是本文借助本体并以此为基础实现搜索引擎的动力所在，也是相比其他形式搜 索引擎的优势所在。 通常，本体需要以某种基于逻辑的语言来表达，从而完成对概念和关系的详 细、精确、一致、良好的表达。一般来说，在语言的表达能力与计算效率之间存 在着一定的平衡：语言的逻辑表达能力越强，其计算复杂度越高，对推理的支持 也会变得相对低效。因此需要在语言的表达能力与有效推理之间进行一定的折 中，在保证语言具有充分的表达能力的同时提供对推理的良好支持。w 3 c 推荐 的标准的本体描述语言o w l ( w e bo n t o l o g yl a n g u a g e ) 在逻辑表达能力和计算效 率之间进行了很好的折中，它是一种基于描述逻辑的具有一定推理能力的用于本 体描述的语言工具。本体及其推理能力代表了现代信息组织特别是网络信息组织 的发展趋势，它不仅有利于信息的形式化描述，而且依据本体这种信息组织方法 而建立的检索系统，更能满足用户进行语义检索特别是智能检索的需要。 2 、本体构建 在基于本体的实际应用中，构建本体是一项基本任务。一方面，所建立的本 体必须满足一定的质量要求，即描述能力是否足够，是否能完整描述领域内的知 识等。另一方面，由于本体构建的过程需要大量的人工参与，因此还需要考虑如 何尽可能减少构建过程中的繁重工作，所以既需要借助优秀的本体编辑工具，也 1 6 中央民族大学硕士学位论文 需要利用现有的技术尝试半自动生成一些本俐4 ，5 ，6 ，7 ，8 ，9 1 。 出于对特定问题域和具体工程需求的考虑，构造本体的过程各不相同。直至 目前，还没有一种标准的本体构建方法。但是，从方法学的角度来看，本体的构 建需要3 个阶段：( 1 ) 本体获取，即知识获取的过程。这需要识别f j 标和范围， 发现领域内关键的概念及关系，给出定义描述并用准确的词汇表达出来。( 2 ) 本 体译码，决定领域知识在概念模型中的结构。即把上一阶段获取的概念用形式化 的语言明确表示出来。先要确立本体中用到的基本词汇，然后选择合适的知识模 型来表达这些词汇。( 3 ) 本体集成，重用原有本体，加快本体开发。 1 7 中央民族大学硕士学位论文 第三章搜索引擎的设计与实现 搜索引擎发展至今在各个方面都取得了丰硕的成果，但尽管如此，仍存在一 些明显的缺点和不足。针对这种现状，本章将