（计算机软件与理论专业论文）基于用户兴趣本体的初始urls选择方法的研究.pdf

西华大学学位论文独创性声明 i i i iii ir lii i ifi fi iiii y 18 8 4 8 0 4 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任 学位论文作者签名：珈惭l 1 指导 日期：砂f j 。6 - i 日期 西华大学学位论文版权 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。( 保密的论文在解 密后遵守此规定) 学位论文作者签名：露矽饼i 指导教师签名： 怵训小f 日o 。c 卜 西华大学硕士学位论文 摘要 近年来，随着本体技术的迅速发展，因具有良好的概念层次结构和对逻辑推理的支 持，本体在面向知识表达和信息检索方面得到了广泛的应用，并且成为人工智能、语义 w e b 、w e b 挖掘等领域的研究热点。由于w e b 技术的快速发展，其海量数据的复杂性、动 态性和用户主题的普遍性等特点给现有的搜索引擎发展带来了极大的挑战。怎样在w e b 中及时地、有效地、精确地定位用户主题资源是提高搜索引擎的检索效率的研究重点。 本文将搜索引擎与本体技术相结合，提出主题爬行虫入口一初始u r l s 选择方法，并从理 论和实验角度说明初始u r l s 对于主题搜索引擎的重要性。 首先，通过形式概念分析理论，提出用户兴趣本体的构建方法。具体方法：自下向 上合并分类概念格和文档概念格，形成能够表达用户兴趣的优化概念格，通过概念格一 本体转化的l m o a 规则，最终形成用户兴趣本体。该本体构建的目的是通过描述概念及其 间的关系来指导主题爬行虫的行为，选择与主题相关的网页，满足用户的个性化需求。 其次，本文在利用w e b 链接结构的同时，结合用户兴趣本体，提出了基于用户兴趣 本体的初始u r l s 选择方法。该方法的特点是将用户兴趣本体与h i t s 算法相结合，一是 利用本体信息对h i t s 算法获取基础集进行修剪，提高h i t s 算法主题识别能力；二是利用 h i t s 算法得到的权威网页和中心网页描述主题区域，并对用户兴趣本体进行更新，通过 用户兴趣本体加权扩展用户的兴趣主题，使之能准确表达用户兴趣需求；该方法将网 页内容和链接分析同时考虑来发现兴趣主题，通过利用图论相关知识，把寻找“核心主 题区域的问题转化为“在完全有向图查找完全二分有向图”的问题，从而降低了算法 实现的难度；利用用户兴趣本体扩展兴趣主题特征向量，并与权威页面集进行相似度 计算，重新过滤搜索结果得到最终的初始u r l s 。 最后，利用v c 6 o 开发应用程序进行验证。实验( 1 ) 将十组用户查询词集提交给 w i k i p e d i a ，对返回的结果进行处理，构建概念格，并构建用户兴趣本体。实验( 2 ) 实现 基于该本体的初始u r l s 选择方法，目的是通过此爬行虫入口，返回更对与用户相关的信 息。实验表明，通过本文本体构建方法，用户兴趣本体能比较好的表达用户兴趣和知识 背景，并消除其语义模糊性。因此，用户兴趣本体为实现个性化主题搜索奠定了基础。 另外，通过实验评价了本文提出的初始u r l s 选择方法。使用本文方法选择初始u r l s 与任意指定初始u r l s 提交给普通爬行虫，比较爬行虫在下载相同网页的数量中相关网页 数量。另外，通过获取u r l s 的三种方法进行实验对比，证明了本文提出的基于用户兴趣 本体初始u r l s 选择是有效的。 关键词：初始u r l $ ，用户兴趣本体，概念格合并，完全二分有向图，主题区域 基于用户兴趣本体的初始u r l s 选择方法的研究 a b s t r a c t i nr e c e n ty e a r s ，a l o n gw i t ht h er a p i dd e v e l o p m e n to fo n t o l o g y t e c h n o l o g y , o w i n gt oi t s w e l lc o n c e p t u a lh i e r a r c h i c a ls t r u c t u r ea sw e l la si t ss u p p o r to fl o g i c a lr e a s o n i n g ，i th a sb e e n w i d e l yu s e di nt h ek n o w l e d g er e p r e s e n t a t i o na n di n f o r m a t i o nr e t r i e v a l a st h ed r a m a t i c d e v e l o p m e n to fw 曲t e c h n o l o g y , t h ec h a r a c t e r i s t i c sa st h es f r u c t u r e sc o m p l e x i t y , d a t a s d y n a m i s ma n dt h eu s e rt o p i c sg e n e r a l i z a t i o nh a v eb r o u g h tag r e a tc h a l l e n g et ot h ee x i s t i n g s e a r c he n g i n e s i th a sb e c o m et h er e s e a r c hf o c u sh o wt ol o c a t eu s e r s t o p i cr e s o u r c c sf r o mt h e o c e a no fi n f o 瑚t i o ne f f e c t i v e l ya n da c c u r a t e l y 1 1 1 er e s e a r c hc o m b i n e ss e a r c he n g i n e sw i t h o n t o l o g yt h e o r yt op r o p o s et h es e e du r l ss e l e c t i o nm e t h o df o rt h ee n t r a n c eo ft o p i cc r a w l e r f u r t h e r m o r e ，i ti l l u s t r a t e st h ei m p o r t a n c eo fs e e di 瓜i st ot h es e a r c he n g i n e sf r o m e x p e r i m e n t s f i r s t l y , b yf o r m a lc o n c e p ta n a l y s i s ( f c a ) t h e o r y , w ep u tf o r w a r dt h ec o n s t r u c t i o n m e t h o do ft h eu s e r - i n t e r e s to n t o l o g y t h ef e a t u r e sm e t h o d sa r ea sf o l l o w s ：i tm e r g e st h e c o n c e p tl a t t i c e st og e n e r a t et h eo p t i m i z e dc o n c e p tl a t t i c ei na l lu p - b o t t o mf o re x p r e s s i n g u s e r si n t e r e s t s ，t h e nt h r o u g hl m o aa l g o r i t h mo fc o n c e p tl a t t i c e o n t o l o g yt r a n s f o r m a t i o n ， c h a n g et h eo p t i m i z e dc o n c e p tl a t t i c ei n t ot h eu s e r - i n t e r e s to n t o l o g y 硒cp u r p o s eo ft h e u s e r - i n t e r e s to n t o l o g yi st og u i d et h eb e h a v i o ro ft h et o p i cc r a w l e ra n ds e l e c tt h er e l e v a n tw e b p a g e st om e e tt h ep e r s o n a l i z e dn e e d s s e c o n d l y , w h i l eu s i n g 西l i n ks t r u c t u r e ? w ep r o p o s et h em e t h o df o rs e e du r l s s e l e c t i o nb a s e do nu s e ri n t e r e s t t h ef e a t u r e so ft h i sm e t h o d ：i tc o m b i n e su s e ri n t e r e s t w i t hh i t sa l g o r i t h m o nt h eo n eh a n d ，i tu t i l i z e st h eo n t o l o g yi n f o r m a t i o nt op r u n et h eb a s i c s e to fh i t sa l g o r i t h mt oi m p r o v et h ea b i l i t yo fi d e n t i f y i n gh i t sa l g o r i t h mt h e m e s o nt h e o t h e rh a n d ，t h ea u t h o r i z e dp a g e sa n dh u bw c bp a g e sa r eu s e dt od e s c r i p tt o p i c a r e a , u p d a t et h e u s e r - i n t e r e s to n t o l o g y , e x p a n dt h eu s e ri n t e r e s t ，a n dr e p r e s e n tt h eu s e rn e e d sa e e u r a t e l 3 r , c o m b i n i n gt h ew 曲l i n ks t r u c t r ew i t hu s e r - i n t e r e s to n t o l o g y ，a n dt h r o u g ht h eg r a p ht h e o r y ， w ec h a n g et h em e t h o d 。f i n d i n gt h ec o r et o p i ca r e a ”i n t o ”f i n d i n gt h ec o m p l e t eb i p a r t i t e d i r e c t e dg r a p hf r o mt h eb i p a r t i t ed i r e c t e dg r a p h ，a n dr e d u c et h ed i f f i c u l t yo ft h ea l g o r i t h m ； w ee x p a n dt h eu s e ri n t e r e s tf e a t u r ev e c t o rb yu s e r - i n t e r e s to n t o l o g y ，c o m p u t et h es i m i l a r i t y w i mt h ea u t h o r i t yp a g e s ，a n dr e - f i l t e rt h es e a r c hr e s u r st og e tt h es e e du r l s f i n a l l y , t h ee x p e r i m e n t si nt h i sr e s e a r c he m p l o yv c 6 0p r o g r a mt op r o v et h e d e v e l o p a p p l i c a t i o n su s i n gv e r i f i e d e x p e r i m e n t ( 1 ) ：t e nu s e r * sq u e r yw o r d sa l ep r e s e n t e dt o w i k i p e d i a , w eb u i l dt h ec o n c e p tl a t t i c eo nt h er e t u r n e dr e s u l t s ，a n dt h eu s e r - i n t e r e s to n t o l o g y i sc o n s t r u c t e do nt h ec o n c e p tl a t t i c e e x p e r i m e n t ( 2 ) ：w ei m p l e m e n tt h es e e di 瓜i ，ss e l e c t i o n m e t h o dt op r o v i d et h ee n t r a n c ef o rt h ec r a w l i n gi n s e c t sa n dr e t u r nt h em o r eu s e r - r e l a t e d i n f o r m a t i o n e x p e r i m e n t ss h o wt h a tt h eo n t o l o g yc o n s t r u c t i o nb a s e do nc o n c e p tl a t t i c em e g e r 西华大学硕士学位论文 m e t h o dc a ne x p r e s st h eu $ o ri n t e r e s ta n dk n o w l e d g eb a c k g r o u n d r e l a t i v e l yb e t t e ra n d e l i m i n a t et h es e m a n t i ca m b i g u i t y t h e r e f o r e , t h eu s e r - i n t e r e s t o n t o l o g yi sb a s i s f o r p e r s o n a l i z e di n f o r m a t i o nr o t r i e v a l i na d d i t i o n ，w ee v a l u a t et h es e e du r l ss e l e c t i o nm e t h o db ye x p e r i m e n t w es e l e c tt h e s e e du r l st os u b m i t tt h eg e n e r a lc r a w l i n gi n s e c t s ，c r a w l i n gi n s e c t sc o m p a r e dt h en u m b e ro f d o w n l o a d i n gt h e8 8 2 1 1 0p a g en u m b e ro ft h er e l e v a n tp a g e s a f t e rc o m p a r i n ge x p e r i m e n t a l r e s u l t so ft h r e em e t h o d sp r o v et h a tt h ep r o p o s e ds e e du r l sb a s e do nu s e r - s e l e c t o do n t o l o g y i se 丘e c t j v e k e yw o r d s ：s e e du r l s ；u s e r - i n t e r e s to n t o l o g y ；c o n c e p tl a t t i c em e r g e r ；c o m p l e t e b i o g r a p h ；t o p i ca r e a 1 1 基于用户兴趣本体的初始u r l s 选择方法的研究 目录 摘j i l i a b s t r a c t i i 1绪 论一l 1 1 研究动态l 1 1 1基于f c a 的本体合并构建方法研究现状1 1 1 2 初始i 瓜i s 选取研究现状。2 1 1 3 主题区域提取技术研究现状一3 1 。2 研究目的与意义4 1 3 论文结构一5 2 基于概念格合并的用户兴趣本体构建方法。6 2 ，1 形式概念分析一6 2 2 本体相关知识7 2 2 1本体的定义7 2 2 2 领域本体7 2 2 3 基于形式概念分析的本体的构建方法8 2 3 概念格合并的用户兴趣本体构建方法9 2 3 1 概念选择。1 1 2 3 2 概念合并1 3 2 3 3l a t t i c em a p p i n go n t o l g ya l g o r i t h m ( l m o a ) 规则l5 2 4 用户兴趣本体构建实验1 8 2 4 1 实验目的1 8 2 4 2 实验数据18 2 4 3 实验界面1 9 2 4 4 实验过程2 0 2 5 实验结果分析。2 3 3基于用户兴趣本体的初始u r l s 选择2 4 3 1 初始u r l s 选择相关知识2 4 3 1 1 初始u r l s 的特征2 4 3 1 2 初始u m l s 的选择方法2 4 3 1 3图论相关知识2 5 3 1 4 主题提取的模型和算法2 6 3 2 基于用户兴趣本体的主题提取过程2 7 西华大学硕士学位论文 3 2 1h i t s 算法改进2 7 3 2 2 抽取用户兴趣主题区域2 7 3 3 基于用户兴趣本体过滤方法3 0 3 3 1 提取用户兴趣特征向量3 0 3 3 2 基于用户兴趣本体的查询词扩展3 1 3 3 2 1 用户兴趣的概念学习3 1 3 3 2 2 用户兴趣的关系学习3 2 3 3 2 3基于用户兴趣本体的查询词扩展3 3 3 4 获取候选u r l $ 3 5 3 5 获取s e c du r l s 3 6 4 实验过程与评价3 7 4 1 数据集3 7 4 2 系统构建3 8 4 3 实验过程3 9 4 4 初始u r l s 选择结果分析与评价4 2 4 4 1评价指标4 2 4 4 2 对比策略4 3 4 4 3 结果分析4 3 5 结论与展望4 7 5 1本文结论4 7 5 2 研究展望4 7 参考文献4 8 攻读硕士学位期间发表的论文及科研成果5 2 致谢：5 3 v 西华大学硕士学位论文 1 绪论 1 1研究动态 1 1 1基于f c a 的本体合并构建方法研究现状 随着语义网的发展，本体在知识重用、知识共享和建模、信息检索等领域得到了广 泛应用。但是由于领域专家的背景知识、设计偏好和命名规则的不同，以及本体自身分 布式异构的特性，导致在对同一领域进行建模时，设计出的本体存在较大的差异，严重影 响了本体间的交互性，即本体异构。因此，本体合并成为解决本体异构的有效方法。本体 合并是将领域中存在的几个本体合并在一起，并消除概念的重复和模糊性的部分，成为 一个新的领域本体。本体合并的大致操作为通过输入多个( 2 个及其以上) 现存的源本 体，返回一个基于给定源本体的目标本体的过程，该目标本体可以针对不同源本体进行 相互转化。近年来有学者提出了支持合并本体的一些系统和框架，例如o n t o m o r p h 系 统【1 1 、c h i m a e r a 系统 2 1 、p r o t e g e2 0 0 0 中的p r o m p t 算法【3 】等。 通过本体合并技术构建本体已经成为研究热点课题。k k o t i s 等人提出了 h c o n e m e r g e 方法【4 】，该方法充分使用被映射至l j w o r d n e t 中的概念的内涵和逻辑推理机 制合并现有本体。a g u z m a n a r e n a s 等人提出o m ( o n t o l o g y m e r g i n g ) 算法【5 】，该算法在人 工干预下，依赖其背景知识，将特定主题的两个本体合并产生新的本体。t i w a n g 等人 开发了一个基于用户查询的本体知识系统【6 】，该系统使用形式概念分析的方法动态的构 建用户本体，为用户查询提供知识反馈。h a l a n i 提出了一种动态构建本体的方法【7 】， 该方法通过识别、排序、映射、合并几个步骤对在线本体进行处理，重新构建本体。 r c c h e n 等人提出- j f f c a m e r g e 方法来构建模糊本体【s 】，该方法通过合并w o r d n e t 和模 糊形式概念分析( f f c a ) 理论技术来合并相同领域的本体。 形式概念分析( f c a ) 用于概念的发现、排序和图形化表示【删。f c a 中的基本概念是 形式背景、形式概念和概念格。概念格是数据分析和知识表达的有效工具。基于f c a 的 本体构建方法，可以在不受开发者的主观影响下，帮助从给定的数据里自动获取所有隐 含的概念以及概念之间的层次关系，并且用符号表示所有概念，达到了形式化概念模型 的效果，为构建本体提供一种方法指导。o b i t k o 等人提出了一种采用f c a 半自动生成本 体的方法，他认为：概念由属性描述；属性决定概念的层次；可以直接概念格转化为本 体使用p7 。使用类似的理论，h a a v 提出了基于f c a 和规则语言理论基础的半自动化本体 构建方法【5 引。步骤如下：( 1 ) 从特定领域的文本或数据中提取形式背景，其三元组中对 象为具体的文本实体，属性为名词短语；( 2 ) 采用f c a 概念格约减的方法，由形式背景生 基于用户兴趣本体的初始u r l s 选择方法的研究 成概念格作为初始本体；( 3 ) 通过f c a 与规则语言的映射关系，将初始本体转换成h o r n 逻辑；( 4 ) 通过增加的规则和事实来扩展初始本体。 综上所述，本体和f c a 都是对概念进行建模的工具，本体中的概念和f c a 中的属 性具有功能上的相似【4 3 1 。f c a 可以运用于本体工程，用于手工或者半自动化建立本体， 对现有的本体进行合并，实现本体的可视化等等。本体的形式化表示描述概念及其概念 之间的关系，可以使用概念格来表达，如f c a m e r g e 方法【2 引，o n t e x 方法1 4 2 等。因此， f c a 理论为本体合并提供了新的方法和思路。 1 1 2 初始u r l s 选取研究现状 为了减少搜索区域，为网络爬行虫提供一个爬行入口，国内外学者关于初始u r l s 选择的研究取得了一定的成就。k l e i n b e r g 提出了h i t s 算法【9 】，并定义了中心网页和权 威网页的概念。他认为权威网页和中心网页之间的强连通关系可以描述用户查询的主题 区域，并从中心网页集中选择初始u r l s ，可以导出更多的主题信息。该方法充分利用 了网页间的链接关系，然而没有考虑网页内容与查询主题间的语义相关度，从而可能导 致“主题偏离”现象的发生。h e r s o v i c i 和c h a k r a b a r t i 等人认为由于用户个体的兴趣不 同【l o - 1 2 1 ，可以让用户自身为爬行虫指定爬行入口，该方法指定的初始u r l s 可以直接表 达用户当前的兴趣主题。由于涉及到用户交互，这就需要用户能够准确地表达他们的兴 趣主题。但是对于大部分用户来说，这是比较困难的，该方法只适合具有一定知识背景 的专业用户，限制了使用范围，不具有普遍性。a g g a r w a l 开发出一种爬行虫，不需要指 定特定主题初始u r l s ，但许多学者仍然认为只有主题初始u r l s 才能够收集较多的主 题网页【1 6 1 。m e n c z e r 开发了爬行虫i n f o s p i d e r ，其原理为：将用户的查询主题提交给搜 索引擎，其搜索结果中的靠前的网页u r l s 作为初始u r l s 1 3 d 4 】。针对于该方法， m u k h e r j e a 开发了w t m s 系统【1 5 1 。但这种初始u r l s 所获得结果集合仍然不理想。 m e n c z e r 和p a n t 等人通过分类目录来指定初始u r l s 【1 7 - 1 9 , 该目录由领域专家建立，因 此所得到的初始u r l s 具有权威性和普遍性。但是当w e b 分类目录中不包含代表某用户 主题的页面时，爬行虫将耗费巨大的精力在无关性的页面上，极大地影响爬行虫的效率。 r u n g s a w a n g 等人提出一种基于学习的主题爬行虫，该爬行虫通过第一阶段的学习效果 来指导下一阶段的爬行行为【2 0 】。该爬行虫设计的主要思想是：通过h u b 页面可以导出 更多的主题页面，即a u t h o r i t y 页面，计算该页面与主题的相似程度。 杜亚军等人提出了把扩展后的用户查询词分别提交给一组通用搜索引擎，然后进行 相似度的判断，并选取相似度高的页面作为初始u r l s 3 蝴m 】。2 0 0 8 年，他们采用本体 技术，提出基于用户本体的初始u r l s 选择方法h o ，并为不同用户建立自己的兴趣模型， 进一步证明初始u r l s 选择的重要性。以上方法分别从网页内容和链接关系角度提出了 2 西华大学硕士学位论文 初始u r l s 的选择方法，基于这些方法的综合，本文希望结合网页内容和链接关系同时 考虑，提出更加有效的方法来指定初始u r l s 。 2 0 0 9 年，i w t z o n e 等人使用f c a 动态构建基于用户查询的本体模型，结合概念格 提供的内部关系和层次结构，在不用浏览全部页面的情况下，为用户查询提供最佳搜索 结果州。2 0 1 0 年，g s o l s k i n n s b a k k 等人提出用户本体描述文档，该文档作为本体的语义 扩展，它的每一个概念都是通过加权的关键词来描述的，通过该向量和搜索结果的相关 度来获取最佳页面作为初始u r l s l 2 2 。2 0 1 0 年，基于本体模型的支持，s y y a n g 设计了 一主题爬行虫o n t o c r a w l e r ( 2 3 1 ，它能够提供稳定的、精确的查询结果，该爬行虫同样可以 得到比较好的初始u r l s 。总的来说，目前国内外很多研究都表明初始u r l s 对于一个 主题爬行虫的重要性。因此，关于主题爬行虫初始u r l s 的选择方法有很大的研究空间。 1 1 3 主题区域提取技术研究现状 主题区域中包含了某个主题相关的网页信息资源，它能够比较清晰地展示关于该主 题的逻辑结构，例如，y a h o o ! 网站中的层次目录式结构。由于主题的模糊性和广泛性， 针对于同一主题，可能搜索引擎通常会返回成千上万的主题区域。目前，提取主题区域 的方法很多都是基于w e b 的链接结构的。 基于h i t s 算法的主题区域提取 k l e i n b e r g 等人提出h i t s 算法，其目标是使用中心页面和权威页面来描述w e b 链 接p j 。主题区域，则是由于将用户某种共同的偏好与兴趣考虑到网页链接结构的设计中， 使得同一主题的网页链接集中在一起。g i b s o n 使用权威页面和中心页面的链接关系来研 究主题区域 2 4 彩】。该主题区域从链接结构出发，因此网络爬行虫在下载网页时，可以不 关心特定主题，直接进入主题区域根据链接关系进行爬行，尽可能的覆盖所有的主题区 域。另外，对于核心主题的确定，由于权威网页对于主题描述的存在，他们认为可以通 过使用高权威性的相关网页来表示主题区域的主题，整个过程不需要人工参与，就能发 现w e b 中的主题区域及主题特征。 基于二分有向图的主题区域发现 在h i t s 算法中，主题区域的提取通过h u b 网页和a u t h o r i t y 网页的链接结构来实 现的，并通过权威网页内容来描述主题特征，但是这样给定的主题可能不能够满足用户 的兴趣，具有高权威值的网页描述的主题不一定正确，该方法很有可能导致“主题偏离， 现象的产生。为了克服这一困难，k u m a r 等人从二分有向图的角度对互联网上的主题区 域给出了一种明确的定义描述【2 6 1 。他们认为对于特定主题在互联网上存在主题区域，该 主题区域的二分的核必将包含在其中，该二分的核的描述是通过完全二分有向图来描述 的，在二分的核的网页内容所描述的主题即为核心主题。在本文方法的研究中，作者使 3 基于用户兴趣本体的初始u r l s 选择方法的研究 同样的方法来实现主题区域的发现，所不同的是，引入用户兴趣本体来描述特定主题， 免在单纯考虑网页的链接结构所带来的“主题偏离 现象。 另外，对于主题区域发现，也存在许多其他的方法。杨楠等人针对于社区的发现， 过研究二分图的特征，引入x 二分核集来定义w e b 社区的抽取方法 6 2 】。通过基于h i t s 法获取数据集，并构建x 二分图，裁剪后得到工二分核集，即为社区的最小元素。傅 华等人提出了基于主题提取和层次发现的个性化算法 2 7 】，该算法结合按照最大最小 则图的划分方法，层次地发现与用户查询相关的页面集合，利用h i t s 的迭代方法分别 算主题页面集合中每个页面的权威值，并按照权威值大小排序，返回靠前的与查询相 关的权威页面，有效地减少了“主题偏离”现象的产生。梁风凤等人提出了基于服务向 量的语义匹配方法和本体映射机制，将基于o w l - s 描述的w e b 服务本体映射到多维向量 空间中，实现基于服务的描述信息的语义匹配，从而提高w e b 服务发现的准确度【6 1 】。 这一方法主要是结合本体来实现服务信息的个性化搜索，对于本文主题区域的发现提供 了借鉴意义。 1 2 研究目的与意义 随着本体应用的深入以及知识信息的快速膨胀，本体结构变得越来越复杂，信息量 也越来越庞大，对于用户本身，带来更多的使用困难。实际上，用户自身所关注地只是 大型本体中一部分概念，大部分概念对于单个用户来说更多的是负担。因此，为每一个 用户建立描述自身兴趣和特征的本体势在必行。 本文研究重点之一，即：用户兴趣本体模型的构建。在本体构建过程中运用形式概 念分析理论，通过概念格合并的方法来构建用户兴趣本体。该本体希望能够形象描述出 在用户兴趣主题领域中的概念以及概念之间的关系，可以通过这种关系来扩展用户兴趣 主题，使得到的概念能够表达用户需求。 面向主题搜索引擎，要求“主题爬行虫 尽可能多的下载与主题相关的网页，尽可 能少的访问与主题无关的网页。然而，“主题爬行虫 的爬行区域是有限的，它也不可 能在巨大的w e b 中没有规律地下载资源。因此，限定主题爬行虫的爬行范围，即“主 题区域 ，是提高爬行效率的重点。王玉婷等人通过实验证实了在w e b 中，具有相同 主题的网页的链接结构是比较紧密的，即网页链接结构趋向于同一主题 2 1 , 4 8 】。基于这一 思想，作者认为w e b 结构是有一定规律的，有一定的“主题聚集性 。 本文研究重点之二，即：个性化初始u r l s 的选择。为了能够有限的时间内，使主 题爬行虫比较准确地、尽可能多地下载到与用户查询主题相关的资源，本文提出初始 u r l s 选择方法，该初始u r l s 为主题爬行虫提供一个特定的w e b 入口，把主题爬行虫 直接限定到主题区域中下载兴趣网页，降低检索规模，提高爬行效率。 4 西华大学硕士学位论文 1 3 论文结构 本文剩下的章节将组织如下： 第二章：基于概念格合并的用户兴趣本体构建方法。 第三章：基于用户兴趣本体的初始u r l s 选择。 第四章：实验过程与结果评价。 第五章：对全文进行总结，并展望下一步研究工作。 5 基于用户兴趣本体的初始u r l s 选择方法的研究 2基于概念格合并的用户兴趣本体构建方法 文献【2 8 】于2 0 0 1 年首先把形式概念分析( f o r m a lc o n c e p ta n a l y s i s ，f c a ) 的方法 应用到了本体构建中，它将用户文档和现有源本体集合，提取形式背景，并在该形式 背景的基础上剪枝概念格，再借助该概念格转化为本体，从而提高了本体合并的精度。 2 1 形式概念分析 德国w i l l e 教授提出了概念格理论，奠定了形式概念分析的理论基础，实现了概念的 一种形式化描述方法【2 9 1 。形式概念分析，已经在知识挖掘 3 们、逻辑推理【3 2 】和软件工程【3 1 】 等许多方面得到了广泛的应用，下面将本文所用到的形式概念分析的相关知识做一个简 要的介绍。 定义2 1 1 2 9 ( 形式背景) 一个形式背景是由两个集合c 和z 以及之间的关系，组成 的三元组k = ( c ，t ，) c 的元素称为形式对象，丁的元素称为形式属性，z 是c 和r 之 间的二元关系，即j c t 。 针对于形式背景k 之( c ，t ，i ) 为了表达形式概念( a ，b ) ，w i l l e 教授定义了两个函数： c a s c a 。：= f t i vc 彳：( c ，力d ， v b ctb + ：= f c c ivf 艿：( a 力毋 定义2 2 【2 9 1 ( 形式概念) 形式背景k = ( c ，t ，) 上的一个形式概念是二元组( a ，b ) ，其 中a c ，b c l 而且满足a t 铂，b 利称a 是概念( a ，b ) 的外延，b 是概念( a ，b ) 的内涵。 定义2 3 【2 9 1 ( 概念格) 对于形式背景k = ( c ，t ，i ) 中的两个概念q = ( 4 ，蜀) 和 c 2 = ( a 2 ，b 2 ) ，而且c 1 c 2 营b lcb 2 a 13a 2 ，则称概念c l = ( a 1 ，b 1 ) 是 c 2 = ( a ：，b ：) 的超概念，概念c 2 = ( a ：，b ：) 是概念c 1 = ( a 1 ，e ) 的子概念，关系根称为 概念的“层次序”k = ( c ，t ，) 的所有概念用这种序组成的集合所诱导出的格为概念 格。 例2 1 形式背景t = ( 0 ，d ，r ) ，其中o = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ) ，d = w a l k i n g ，s w i m m i n g ， t r i p ，f i s h i n g 二元关系见表2 1 ，其形成的概念格的h a s s e 图( 图2 1 ) 【3 5 1 ，其中属性集 d = a ，b ，c ，d 对应形式背景中的属性集合。为了方便讨论，在以后的讨论中本文将对象 集如 1 ，2 ，4 ) 写成1 2 4 ，将属性集 a ，b ) 写成a b 的形式。 6 西华大学硕士学位论文 鼍 墨 钠曙嚏8 ，一、 _ _鬻鞠戳浮獭瞄“兹 瓣。稻轴雌 盏鬣豳叠藏耐j 鼍于笋溷 洲翱豳磁嗣酾啦矗德 埘 l x 蠲翰翻譬曩积一j瞄溺瑶骊碍寥甥磷臻喇 帮芍氍魏嘞哮铂麓睁霎势 崩穗鞠嗣峪舔 盔蕊翻鳓翻b 盏羞懿糊 4 ， 一 l x瞳x x | 二 鬻埘 x _x羹 t 坶 冀x 表2 1 形式背景 t a b 2 1f o r m a lc o n t e x t l 【l 冀幻隆曲 图2 1 对应的概念格 f i g 2 1c o n c e p tl a t t i c e 自项向下地考察这个概念格，为方便描述，称相邻两个节点中，位于上方的是父节 点( 直接超概念) ，位于下方的叫子节点( 直接子概念) 。图2 1 中，不难看出最顶端的 节点拥有所有对象但拥有的属性最少或为空，最底端节点拥有所有属性但对象最少或为 空。因为概念格中的每个节点的含义是，该节点中所有对象所共有的属性，所以把越多 对象放在一起，能找到的共同点( 即共有属性) 就越少。正好说明概念格结构与本体想 要描述的客观现实是一致的。 2 2 本体相关知识 2 2 1 本体的定义 本体( o n t o l o g y ) ，是以存在为核心的各种领域通过逻辑方法组织的哲学原理的一门理 论，是“对世界上客观事物所进行的系统描述，即存在论 3 3 , 6 0 】。在人工智能领域，最 早被广泛应用的o n t o l o g y 定义是g r u b c r 给出的，“本体概念模型的明确的规范说明 【4 l 】。由于本体来源于哲学家不同的哲学观念，导致了人们对于o n t o l o g y 的不同理解， 使得本体应用演变的十分复杂。o n t o l o g y 的目标是捕获相关领域的知识，提供对该领域 知识的共同理解，确定该领域内共同认可的词汇，并从不同层次的形式化模式上给出这 些词汇( 术语) 和词汇间相互关系的明确定义【4 1 1 。 2 2 2 领域本体 本体( o n t o l o g y ) 是一种存在的系统化解释，用于描述事物的本质【3 3 】。本体包含六个 元素f c ，彳c ，r ，彳，日，x ) 。其中c 表示概念集；彳c 表示每个概念的属性集；足表示关系 集；么尺表示每个关系的属性集；日表示概念层次；z 表示公理集【蚓。 本体实例很多，例如项级本体、领域本体、任务本体、应用本体等。其中，领域本 体( d o m a i no n t o l o g y ) ，是对某个特定领域( 生物，医药等) 分析和建模的结果，即某 7 基于用户兴趣本体的初始u r l s 选择方法的研究 个特定领域中的概念及其概念间的关系，从语义角度表示为对象的集合，用自然语言对 概念进行描述；成为领域内的知识表达、行为策略与推理、及知识共享研究的理论基础 1 3 5 近年来，本体模型的研究已经进入实