（计算机应用技术专业论文）基于形式概念分析的主题搜索策略研究.pdf

西华大学硕士学位论文 基于形式概念分析的主题搜索策略研究 计算杌应用技术专业 研究生董占兵指导教师社亚军 摘要 i n t e r n c t 的迅猛增长使得搜索引擎面临前所未有的挑战，搜索引擎如何适应 这种规模的急剧膨胀，成为一个备受关注的问题。如何在浩瀚的网络资源中发 现有用信息促使了搜索引擎的诞生，而作为搜索引擎中重要组成的网络蜘蛛 ( w c bs p i d c o 专门负责采集网络资源进行数据储备。传统的基于整个w e b 的采集 ( s c a l a b l ew 曲c r a w l i n g ) 在网络信息检索中发挥了重要的作用，成为各大门户网 站的首选，然而随着网络资源的爆炸式增长，传统的基于整个w e b 的信息采集 需要采集的页面数量十分浩大，这就需要消耗非常大的系统资源和网络资源， 然而这些资源的消耗并没有换来所采集到的页面的较高利用率，事实上，它们 中有相当大的一部分利用率很低。这是因为，用户往往只关心其中极少量的页 面，并且这些页面往往集中在一个或几个主题内，而采集器采集的大部分页面 对于他们来说是没有用的；另外刷新如此大量的页面需要很长的周期，这就不 能实时反应网络资源的动态变化，造成了一定数量的过期信息；此外传统信息 采集技术由于其采集的规模较大，采集页面内容的杂乱，不能根据用户的特定 信息以及用户感兴趣的主题进行集中式爬行，容易造成主题淡化和许多相关信 息的丢失，多数情况下只能返回一些广泛主题的结果，对明确的特定的主题信 息则返回很少。 面向主题的搜索引擎可以有选择性的抓取与主题相关的网络资源，识别的 依据是一个或一组事先定义的主题，主题特征由样本网页或文本标识，而不仅 仅是关键词。它有效减少了采集页面的数量，增加了采集页面的规整程度，并 能深入剖析用户感兴趣的主题，返回大量高质量相关信息，这不仅能够大大减 少系统对硬件和网络资源的需求，而且还有助于提高抓取的准确率和搜索结果 的更新速度，因而以何种策略去访问w e b ，以期获得更多的相关资源，成为主 第1 页 耍兰盔堂堡主堂焦丝塞 题搜索的研究热点。 本文通过研究现有的主题搜索策略的特点，提出了将形式概念分析这一数 据分析工具应用到主题搜索中，将以往仅仅停留在关键词层面的机械式的、外 在形式的匹配技术提高到概念匹配的层面，从概念的语义关系层次对文本进行 主题相关性分析，通过概念相似度对页面内的u r l 进行主题相关性预测，因而提 出了基于形式概念分析的主题搜索策略。纵观各种搜索策略，将形式概念分析 应用于主题搜索，本文是一个新的尝试，主要的研究内容如下： 1 概念格作为形式概念分析的核心，是一种有力的数据分析工具。本文通 过研究格上概念之间隐含的各种关系以及格结构本身的特点，决定以概念格作 为背景来表示用户查询主题，建立用户兴趣主题模型作为基础格。 2 重点研究了格上概念之间韵继承关系，定义了格上的核心概念和非核心 概念，给出了格上概念距离的计算，并提出了三种通过概念距离计算概念相似 度的方法。 3 提出了基于属性的直接概念匹配方法，给出了虚拟概念的定义，通过在 基础格上寻找虚拟概念位置来获取虚拟概念的相似度值，以此相似度值为依据， 解决了待访问u r l 与主题的相关性判定问题，提出了本文的基于形式概念分析 的主题搜索策略。 4 构建主题搜索系统，获取网络数据，通过平均收成率和f - m e a s u r e 两种 评价指标来检验本文的搜索策略，通过和通用的宽度优先搜索策略进行比较， 得出了本文提出的策略是可行的。 关键词：搜索引擎、主题搜索、形式概念分析、概念格、网络蜘蛛 第页 西华大学硕士学位论文 f o c u s e dw e b c r a w l i n gs t r a t e g yb a s e d o n f o r m a lc o n c e p t a n a l y s i s c o m p u t e ra p p l i c a t i o nt e c h n o l o g y m a s t e rd g r e ec a n d i d a t e ：d o n gz h a n b i n g s u p e r v i s o r ：d uy a j u n a b s t r a c t w i t hi n t e r n e tg r o w i n ge x p o n e n t i a l l y , s e a r c he n g i n ei s e n c o u n t e r i n gs o m e u n p r e c e d e n t e dc h a l l e n g e s h o wt or e s p o n dt ot h i sd r a s t i c a l l ye x p a n d e ds i z eb e 伽m e s an o t i c e a b l e p r o b l e m s e a r c he n g i n eo r i g i n a t e df r o mf i n d i n gu s e f u li ni n m l e l l s ew e b r e s o u r c e s ，w e bs p i d e r , a sai m p o r t a n tp a r to fs e a r c he n g i n e ，m a i n l ya n s w e r sf o r c o l l e c t i n gw e br e s o u r c e st os t o r e s c a l a b l ew e bc r a w l i n ga l w a y sp l a y sai m p o r t a n t r o l ei w e bi n f o r m a t i o nr e t r i e v e s oi ti s e x t e n s i v e l ya d o p t e db ys o m el a r g e m e s h w o r ks t a t i o n s , b u tw i t ht h er a p i dg r o w t ho fw o r l d w i d ew e b s c a l a b l ew e b c r a w l i n gh a st or e t r i e v el a r g en u m b e r so fp a g e s ，t h i sw i l le x h a u s tc u r r e n ts y s t e m r e s o n r o o sa n dn e t w o r kr e s o u r c e s ，b u tn o ta l lt h e s ed a mi sf u l l yu t i l i z e d ，m u c ho f t h e s ei sw a s t e d i nf a c t , n s e lo n l yc o n c e r n e dw i t ht h eu s e f u lp a r to fp a g e sr e t r i e v e d , a n dt h eh e l p f u lp a g e su s u a l l yr e l a t et oo n l ys e v e r a lt o p i c s ，am a j o r i t yo ft h ep a g e s r e t r i e v e da l en o tv a l u a b l et ou s e li na d d i t i o n ，r e f r e s h i n gs u c hv a s tp a g e sn e e d st o s p e n dal o n gt i m ep e r i o d ，t h i sw i l lp r o d u c eal o to fo u t d a t e di n f o r m a t i o n , b e c a u s e w e br e s o u r c e sa r ec o n t i n u o u s l yu p d a t e dw i t hn e wc o n t e n t b e s i d e sb e c a u s eo fa l a r g er e t r i e v i n gs c a l e ，t r a d i t i o n a lc r a w l i n gt e c h n o l o g yr e t u r n sm a n yl i t t e r yp a g e s ，i t c 姐n o tf o c u s1 3 1 1s o m ei n t e r e s t i n gt o p i c s t h i sw i l lr e s u l ti nm i s s i n gs o m er e l e v a n t i n f o r m a t i o na n dr e t u r ns o m ee x t e n s i v et o p i cp a g e s ，t h ei n f o r m a t i o na b o u ts p e c i f i c t o p i ci sl i t t l e t h ef o c u s e dw e bc r a w l i n gi st os e l e c t i v e l ys e e ko u tp a g e st h a ta r er e l e v a n tt oa p r e - d e f i n e ds e to ft o p i c s ，t h e s ef e a t u r et o p i c sa r ed e f i n e dn o to n l yb yk e y w o r d sb u t a l s ob ye x a m p l ep a g e s f o c u s e dc r a w l i n gr e d u c e st h en u m b e ro fr e t r i e v i n gp a g e s ， 第m 页 西华大学硕士学位论文 s i m u l t a n e o u s l yr e g u l a t i n gt h ep a g e sv i s i t e da n dd e e pa n a l y z i n gt h ei n t e r e s t i n gt o p i c s ， s oi to b t a i n sl a r g en u m b e ro fh i 【g h q u a l i t yp a g e s t h i sm e t h o dn o to n l yr e d u c e s r e q u i r e m e n tt oh a r d w a r ea n dn e t w o r kr e s o u r c eb u ta l s oi m p r o v e st h ep r e c i s i o na n d r e f r e s h i n gs p e e d s oi no r d e rt oo b t a i nah i g hc r a w l i n ge f f i c i e n c y ，w h a ts t r a t e g yi s u t i l i z e dt ov i s i tw c bi sc r u c i a lt of o c u s e dw e b c r a w l i n g b yr e s e a r c h i n gt h ec h a r a c t e r i s t i c so fc u r r e n tf o c u s e dc r a w l i n gs t r a t e g i e s ，t h i s p a p e rb r i n g sf o r w a r da p p l y i n gf o r m a lc o n c e p ta n a l y s i st of o c u s e dc r a w l i n g , a n d e n h a n c i n gm a t c ht e c h n o l o g yf r o mt h el e v e lo fm e c h a n i c a la n de x t e r n a lk e y w o r d st o t h el e v e lo fc o n c e p t w ep r e d i c tt h er e l e v a n c ei nt e r m so fs e m a n t i cr e l a t i o nb e t w e e n c o n c e p t s ，t h r o u 曲c o m p u t i n gc o n c e p ts i m i l a r i t yw ec a np i c ko u tr e l e v a n th y p e r l i n k f r o map a g e ，s ot h i sp a p e rp u t sf o r w a r daf o c u s e dw e bc r a w l i n gs t r a t e g yb a s e do n f o r m a lc o n c e p ta n a l y s i s ( f c a ) s k i m m i n go v e rv a r i o u sc r a w l i n gs t r a t e g y , a p p l y i n g f c at of o c u s e dw e bc r a w l i n gi san o v e lm e t h o d ，t h ef o l l o w i n gi st h em a i nr e s e a r c h c o n t e n t ： 1 a st h ec o r eo ff c a , c o n c e p tl a t t i c ei sa p o w e r f u ld a t aa n a l y s i st 0 0 1 t h r o u g h r e s e a r c h i n gt h er e l a t i o nb e t w e e nc o n c e p t sa n dt h ec h a r a c t e r i s t i co fc o n c e p tl a t t i c e ， w ep r e s e n tt h eu s e rs e a r c ht o p i c sb yc o n c e p tl a t t i c es t r u c t u r e , a n de s t a b l i s hn s e r t o p i c a lm o d e l i n ga sab a s i cl a t t i c et om a t c h 2 i nt h i sp a p e rw em a i n l ys t u d yt h es u c c e s s i v er e l a t i o n , a n dd e f i n ec o r e c o n c e p ta n dn o n c o r ec o n c e p t , a n dp r e s e n tt h ec o m p u t a t i o no fc o n c e p td i s t a n c e ， i n t r o d u c et h r e em e t h o d sa b o u tc o m p u t i n gc o n c e p td i s t a n c e 3 w ep u tf o r w a r dd i r e c tc o n c e p tm a t c hm e t h o db a s e d0 1 1a t t r i b u t e ，d e f i n et h e v i r t u a lc o n c e p t t h t o u g hl o o k i n gf o rt h ea p p r o p r i a t el o c a t i o no fv i r t u a lc o n c e p to i l b a s i cl a t t i c et oo b t a i nv i r t u a lc o n c e p t ss i m i l a r i t y ，i nt e r m so ft h i sv a l u ew ec a nf i l t e r t h eu r lu n v i s i t e d , s ot h i sp a p e rp r e s e n t saf o c u s e dc r a w l i n gs t r a t e g yb a s e do n f o r m a lc o n c e p ta n a l y s i s 4 f i n a l l y , e s t a b l i s h i n gf o c u s e dc r a w l i n gs y s t e m ，c o l l e c t i n gw e bd a t a , u t i l i z i n g a v e r a g eh a r v e s t r a t ea n df - m e a s u r et w oe v a l u a t i n gm e t h o d st oc o m p a r ew i t h t r a d i t i o n a lb r e a d t hf i r s ts t r a t e g y ，w ep r o v et h ef e a s i b i l i t yo fo u rs t r a t e g y k e y w o r d s ：s e a r c he n g i n e ，f o c u s e dw e bc r a w l i n g ，f 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 ，w e bs p i d e r 第页 西华大学硕士学位论文 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或 证书雨使用过的材料。与作者一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 作者签名j 雾占幺力7 年厂月始日 导师签名刁比纱绝 第醯页 2 年6 月f 日 西华大学硕士学位论文 第1 章绪论 信息检索是指从数据集中提取出相关文档和信息的过程，在w 曲出现以前 它主要用于数字图书馆的文献资料查询，因为这些文献资料都是经人工录入或 者分类的，所以信息检索在w c b 时代之前是相对简单、成熟的技术。w e b 的 出现改变了人们进行信息检索的方式，搜索引擎成为人们获取信息的主要方式， 信息检索的对象也从结构化的数据转向半结构、无结构化的数据。近年来基于 w e b 的智能化信息检索研究正逐步展开，它将改变并解决目前搜索引擎中遇到 的各种问题和矛盾，提供从信息过渡到知识的检索方式。随着网络以及硬件技 术的飞速提高，人们希望更快更准确地直接获取网络信息，以期匹配网络的变 化速度，这将使得传统的以数据库为基础的信息源转向以w e b 为基础的数据源， 这就需要更加智能化的网络搜索服务技术。 1 1 应用背景 搜索引擎( s e a r c he n g i n e ) 是帮助人们在庞大的w e b 上查找信息的重要工 具。i n t e r n e t 诞生到现在，搜索引擎技术也在不断的完善和发展，从早期的 简单分类目录已经发展到具有复杂算法和庞大集群系统的高级应用服务，一些 搜索引擎已经开始引入了智能化信息检索技术来提高信息收集和查询的质量。 通用搜索引擎在过去的十多年中发挥了其巨大的潜力1 1 叫，将网络这个充斥各种 资源的、杂乱的信息源变成了一个规整的信息数据库，帮助人们方便的检索到 自己想要的信息，成了互联网上除电子邮件以外最多人使用的网上服务。 这些通用搜索引擎的目标就是尽可能多地采集网络资源，甚至是整个w e b 上的资源，而在这一过程中它并不太在意页面采集的顺序和被采集页面的相关 性，希望通过索引尽可能多的w e b 资源去满足各种用户的查询，而付出了巨大 的索引维护代价。但是随着网络资源的爆炸式和无规则增长，索引的规模增长 远远跟不上网络本身的变化速度，相对整个网络，他们仅能够覆盖一小部分。 以g o o g l e 搜索引擎为例，在2 0 0 5 年，他们索引了大约8 0 亿个网页，但这也只 覆盖了网络上静态网页的3 0 9 6 - 4 0 ，更别说数量巨大的动态页面，因此大量隐 藏在网络深处的信息资源并未被索引到。此外，当前主流的搜索引擎中普遍采 用的是全文检索或关键词检索的方式，即在原文中查找用户所指定的词。这种 第1 页 西华大学硕士学位论文 仅仅基于字面的检索机制不可避免地会带来实际检索结果与用户需求之间的偏 差。这种偏差在查准率和查全率两方面表现出来。一方面某些篇章并非论述用 户所关心的主题，而仅仅因为包含了个别词而被错误地查找出来，这种偏差通 常用“查准率”来衡量；另一方面，一些真正与用户查询主题相关的内容却由 于用词的差别而失之交臂，这种偏差通常用“查全率”来衡量。举个简单的例 子，用户希望查找与电脑有关的信息，当他用“电脑”这个词去检索时会发现 许多讲述计算机的文章并没有被查出来，因为这些文章中自始至终都说的是“计 算机”而没有用到“电脑”这个词。虽然人们在检索算法上作了种种改进以求 提高查准率和查全率，但最终发现这两者处于相互矛盾的状态。为了提高查全 率，人们不得不忍受大量的垃圾数据：而要想使检索到的内容都不跑题则往往 意味着遗漏了许多有用的信息。归根结底这是由自然语言语义的模糊性所决定 的，基于词法和语法层次的检索方式当然无法与用户基于对语义的理解所提出 的需求完全吻合。另外用户关心页面往往集中在l 个主题或几个主题内，而通 用搜索引擎返回的大部分页面对于他们来说是没有用的，并且还存在页面刷新 周期较长、不能实时反应网络资源的动态变化、产生了死链接过多和信息滞后 等问题。 在索引覆盖率低的情况下，很多搜索服务在进行文档收集的时候对各个页 面采用的是相同的下载优先级，它导致在最终的索引库中的页面保留了许多参 考价值不高的页面，而一些比较重要的页面却没有被索引到，要解决这个问题， 需要在c r a w l e r 遍历的过程中进行资源质量的判别，优先下载高质量的页面， 按照优先级来建立索引数据库。因而出现了面向主题的搜索引擎，它使用一种 面向主题的爬行策略( f o c u s e dc r a w l i n gs t r a t e g y ) 实时进行w c b 文档质量分 析并确定下载优先级的算法，它在某种程度上弥补了覆盖率低的这一不足。 与通用搜索引擎不同的是，面向主题的搜索引擎拥有更好的查全率和查准 率，因为它能将搜索网页的内容限定在一定的领域里，有效缩减了搜集的范围， 极大的节省了资源并提高了资源的利用率，也缓解了刷新周期问题，能够针对 用户感兴趣的主题进行集中式、深入的搜索，能够发现大量通用搜索无法到达 的区域。另外搜索引擎智能化的目的是具有自然语言理解能力，将检索能力提 升到语义层。但由于自然语言理解需要很高的智能水平，目前在这方面的工作 困难重重，还无法达到对语义的完全理解。在目前的自然语言处理能力基础上， 面向主题的搜索引擎通过引入分类或聚类等人工智能技术，从中获取文本的语 第2 页 西华大学硕士学位论文 义信息，并将之运用在检索中，从而提高信息检索的有效性，因而它也成为第 三代智能搜索引擎研究的热点。 i 2 面向主题搜索的研究现状 面向主题搜索的一个主要问题是以什么顺序访问网页里的链接出口才能搜 索到尽可能多的与查询主题相关的网页，同时尽可能少的访问与主题无关页面。 它需要在搜索的过程中对页面以及其中包含的链接做出主题相关性判定，是一 种边访问边判断的搜索技术，这是主题搜索面临的一个巨大的挑战，因为网络 上的信息并不是规则的，并不是主题相关度高的页面其所含的所有网页的相关 度就大，因为高度相关性的网页上也会有低相关度的页面链接上来。 自1 9 9 4 年搜索引擎问世，面向主题的搜索引擎就已经被提上日程。同年 d c b m 首次提出了一种基于页面内容与查询主题匹配的爬行“f i s h s e a r c h 叫8 j ， 仅考虑了指定的主题关键词形式上的匹配。 一 1 9 9 8 年h e r s o v i c i 改进了“f i s h s e a r c h ”，在匹配的时候考虑了链接的锚文 本和链接周围的信息，提出了“s h a r k - s e a r c h ”1 9 1 。 1 9 9 8 年，s t a n f o r d 大学的c h 0 1 1 0 】提出了一些主题搜索策略。他们通过先搜 集重要程度高的网页使搜集过程更加有效。这种“重要”性主要体现在与查询 请求的相似程度，网页的入度( 即指向这一页的网页数) ，网页的出度( 即这一 网页的链接出口数) ，网页评分( p a g c r a n k ) 和网页的位置特点等方面。一个网 页的网页评分( p a g e r a n k ) 即指向它的网页的p a g e r a n k “j 的加权和。c h o 的研 究比较了这几种衡量方法的区别。他们发现使用网页入度计数的搜集器的表现 近似于深度优先搜索，倾向于优先访问一个“簇”( d u s t e r ) 内的网页，而且不 同的初始网页集合的选取会对最终的结果造成比较大的影响。而使用网页评分 ( p a g e r a n k ) 算法的搜集器则似乎不受这方面的影响，并且较好的结合了深度 优先和广度优先两种方法的优越性。 1 9 9 9 年，c h a k r a b a n i 【1 2 】设计了较完备的面向主题搜索引擎的模型。系统使 用y a h o o 的分类层次目录，同时不同主题下还保存了能真正表达此主题意图的 事例性文本和页面链接，由用户在感兴趣的领域作出标记，作为搜索的主题。 用户可以在测览的时候标识感兴趣的网页，然后按照y a h o o 这种经典分类方法 将该网页分入对应类别中作为样本。该搜索系统主要由三部分组成：搜集器， 分类器( c l a s s i f i e r ) 和被作者称之为“蒸馏器”( d i s t i l l e r ) 的进程。分类器判断 第3 页 西华大学硕士学位论文 一个超文本文档与主题的相关度，将其归入正确的类别中；“蒸馏器”( d i s t i l l e r ) 则在超文本链接分析的基础上，识别出指向大量高相关度页面的目录型网页 ( h u b ) ，这些网页本身含有很少的主题相关信息，但却起到了主题相关页面的 分发作用；搜集器则根据分类器和“蒸馏器”提供的控制信息对未访问队列进 行动态排序。通过试验，他们指出在有限的领竣内挖掘网上资源是可行的；如 果某个网页与主题具有高相关度，可以认为它在网络中的邻居( 即出链接) 也 是相关的。 2 0 0 0 年，d l i g e n f i 提出了基于“语境图”( c o n t e x t 舯p ”的搜索策略i l ”，它 通过构建典型页面的w e b “语境图”( 即真实的网络链接图) 来估计离目标页 面的距离，距离较近的页面较早得到访问。， m e n c z e r 【1 4 1 在2 0 0 1 年的研究评估了几种不同搜集策略的优劣。他们的试验 为1 0 0 个主题分别建立了分类器，以衡量搜集到的网页的相关度。m e n c z e r 指 出一个好的面向主题搜索引擎应该将搜索的范围尽量保持在向量空间中与主题 邻近的区域内。他们总共评估了三种不同的搜集策略： 令b e s t f i r s t 搜集器：优先队列中u r l 对应的优先级是包含该链接的原网页 与主题的相关度，采用了文本信息检索中常用的向量空间模型( v s m ) 【1 5 】求相似度的方法。 p a g e r a n k 搜集器：以网页评分( p a g e r a n k ) 的高低为顺序搜索，每搜集 2 5 个网页重新计算一次评分。 令i n f o s p i d e r s ：使用神经网络算法，考虑链接周围的上下文。 他们的试验发现b e s t f i r s t 表现出性能最优，紧接着是i n f o s p i d e r s ，最后是 p a g e r a n k ，并且他们认为p a g e r a n k 对于主题搜索任务来说，搜索的主题过于 通用化，不能体现具体的主题。b e s t f i r s t 方法能将搜索范围始终限制在搜索主 题周围，因而能获得很好的效果。i n f o s p i d e r s 方法则介于两者之间。 近些年来，也有人提出了基于本体的主题搜索策略，但这些也只能停留在 实验阶段，大部分的研究还是上述方法的不断提高。但总的趋势是搜索技术在 不断地智能化，准确性在不断的提高，从早期的基于关键词的形式化的匹配， 逐步过渡到概念匹配的高度，进而向自然语言理解迈进。但由于机器还不能理 解自然语言，人们正在从事大量的自然语言处理工作的研究，更试图建立语义 网，让机器更好的理解人们的搜索意图，为人们提供更加准确、快捷的搜索服 务。 第4 页 西华大学硕士学位论文 1 3 本文的主要研究内容 面向主题的搜索其实是信息检索技术和信息过滤技术的综合，首先通过网 络蜘蛛依据用户给定的知识去网络上搜集一些基础页面，然后对搜集的页面进 行相关性判断，价值低的页面被过滤掉，对获取的相关页面进行知识的抽取， 然后用这些知识继续去网络上寻找相关页面的一个往复的过程。要想获得满意 的效果，首先就是要理解用户的搜索意图，仅仅停留在关键词的层面还不够， 还需要理解这些关键词所处的具体语境，达到从语义上去理解用户的搜索目的， 然后才能用这些知识去对网页和链接做出正确的相关性判定，进一步提高主题 搜索的准确率。本文正是围绕着这些思想展开的，具体的内容安排如下： 第一章绪论部分，介绍了主题搜索的产生背景和目的，以及其近些年来这 方面研究的进展情况和进一步发展的趋势。 第二章主要介绍了主题搜索中所要涉及的一些核心技术问题和相关知识， 以及主题页面在w e b 上的一些分布特征，以及如何将这些特征应用到主题搜索 策略中，以期取得较好的效果。另外针对这些研究内容，给出了本文的一些思 考，并考虑将这些想法融入到主题搜索中。 第三章讨论了形式概念分析的基本原理及其在主题搜索上的应用，通过建 立概念格的方法构建用户兴趣主题背景，作为搜索匹配的基础。所涉及的内容 有研究格上概念之间的关系、挖掘核心概念和将概念距离转化成概念相似度等。 第四章详细讨论了主题搜索策略的研究思想，在介绍了一些比较流行的搜 索策略的特点之后，提出了本文基于形式概念分析的主题搜索策略，深入讨论 了如何在用户兴趣主题背景格上定位虚拟概念位置的方法，并将三种不同的概 念相似度方法应用到该策略中，形成了l s f 、s s f 、e s p 三种不同的方法。 第五章在本文提出的搜索策略基础上，构建了主题搜索系统，执行此系统， 并和通用搜索策略进行比较，得出了本文提出的策略是可行的，并得出在将概 念距离转化成概念相似度来引导爬行时，不同的收敛和递减速率对爬行性效果 是有影响的，收敛过慢，会引入大量的不相关页面，而收敛速度过快，会在搜 索的过程中过滤掉许多相关的扩展路径，导致较少的备选链接。 最后是总结部分，给出了本文的创新点和相应的成果，并指出了几点需要 进一步研究的方向，来提高本文方法的效果，即一些需要继续深入研究的工作。 第5 页 西华大学硕士学位论文 第2 章主题搜索策略涉及的基本问题及本文的应对策略 主题搜索主要是获取网络上与主题相关的网络资源，一些相关的研究表明， 主题资源在网络上的分布具有一些特征和规律可循，如果将这规律应用到主题 搜索策略中，将会收到事半功倍的效果。本节将介绍主题搜索研究中所涉及到 的些预备知识和存在的问题，并给出了本文解决这些问题的一些想法。 2 1 主题搜索策略与通用搜索策略的比较 主题搜索策略是相对于通用搜索引擎的搜索策略而提出的，通用搜索策略 使用的是一种基于整个w e b 资源的爬取策略，通常使用的是宽度优先或者深度 优先的策略，即碰到链接就抓取其对应的网络资源，在爬行的同时对资源不加 区分和判断，体现一种大而全的思想，如果将其引进主题搜索中，在初始启动 时刻，由于围绕在相关性高的种子页面周围，效果还可以，但随着距离的增加， 向相关页面扩展的能力急剧下降，很快被无关页面包围。而主题搜索策略则对 碰到的每一个网页要区分对待，通过判断其与要抓取的目标的相似性对待访闯 页面进行排序，优先访问有前途的页面，能自己跳出无关页面的包围，努力朝 相关页面的方向扩展。具体的区别见图2 1 。 口p a g e s u n v i s i t e d p a g e s v i s i t e d u n i v e r s a lc r a w l r i gs t r a t e g y ( n ol i n kd i s t n o o n 、 f o c u s e dc r a w l i n gs t r a t e g y ( r e c o n g n i z er e l e v a n tl i n k ) f i g u r e2 1 t h ec o m p a r eo f u n i v e r s a lc r a w l i n gs t r a t e g yw i t hf o c u s e dc r a w l i n gs t r a t e g y 图2 1 通用搜索策略与主题搜索策略的比较 2 2 主题搜索的分类 2 2 1 广泛和具体主题的搜索 按照搜索主题的范围和规模，基于主题的搜索可分为广泛主题的w e b 信息 第6 页 耍兰盔堂塑主兰垡笙銮 搜索和具体主题的w e b 信息搜索。 广泛主题是指那些涵盖面较宽，并且和其他主题相比有较强的独立性的一 类主题，它所包含的概念范围比较大，在网络上的搜索资源数量上也比较大， 因此广泛主题的w e b 信息搜索也称作领域w e b 搜索。由于这类信息搜索所需 要采集的页面数量较多，为了达到较高的召回率，在迸行u r l 过滤的时候所设 定的闽值较低、限制较宽，因此它的页面内容也相对较杂。与之相对应，具体 主题涵盖面较窄，意义较明确，采集规模也较小，一般进行u r l 过滤的时候所 设定的阈值较高、限制较严。这类采集一般可直接服务于用户，提供更加灵活、 针对性更强的服务。， i 2 2 固定和可变主题的w e b 信息搜索 按照搜索时能否指定主题，基于主题的w e b 信息搜索分为固定主题的w e b 信息搜索和可变主题的w e b 信息搜索。 顾名思义，固定主题的w e b 搜索策略在采集前和采集的过程中都不能进行 主题的变更。它一般是针对广泛主题和领域搜索引擎的，不直接服务于用户。 可变主题的w e b 信息采集是指用户在采集前可设定采集主题、在采集过程中可 改变主题的一种采集方式。这类采集往往设定的主题较具体，采集页面的规模 也较, j q 提供给用户的操作方式比较灵活。另外，多个此类信息采集器进行合 作，分别采集不同的主题，能够完成一些更高级和复杂的服务，这种采集方式 能够随用户的主题兴趣的变化而灵活变动，一般应用在可学习的信息采集系统 中。 2 3 主题页面在w e b 上的分布特征 整个w e b 上的页面主题分布是混杂的，但具有同一主题的w e b 页面的分布 却有一些规律，这可能与页面或者网站的设计者有关，具有同一主题的站点或 者页面为了更好地给用户服务，总是想方设法引用一些具有同类主题的站点或 者网页，如此则这些主题页面则聚拢在一起，形成一个簇。但由于网络的随意 性和复杂性，一些非主题的页面也将自己加入其中，造成了有时候这些规律的 失效，但这也正激发了主题搜索的产生，将这些规律应用到主题搜索中，可以 取得好的搜索效果。这些分布规律被总结为四个特性：a u t h o r i t y h u b 特性、 s i b l i n g l i n k a g el o c a l i t y 特性、站点主题特性、t u n n e l 特性。 第7 页 西华大学硕士学位论文 2 3 1a u t h o r i t y h u b 特性 美国康奈尔大学的教授j o nm k l e i n b , r g _ 1 1 6 】发现w e b 上存在大量的h u b 页 面，这种页面不但含有许多o u t l i n k 链接( 指出链接) ，并且这些链接趋向于相关 同一个主题。也就是说，h u b 页面是指向相关主题页面的一个中心，起一种主 题页面的导航作用，它本身包含的主题信息比较少，一般是通过链接结构反映 出来的，因为它包含了许多主题页面对应的超链接。另外，他还定义了权威页 面( a u t h o r i t y ) 的概念，即其它许多页面都认为该页面相关于特定主题且具有价 值的好页面，其中包含了大量能反映主题的信息，即对主题有好的描述。好的 h u b 页面一般指向多个a u t h o r i t y 的页面，并且所指向的a u t h o r i t y 页面越权威 h u b 页面的质量也越好；反过来，h u b 页面的质量越好，它所指向的每个页面 也趋向于越权威。通常把主题在w e b 上的这一特性称为a u t h o r i t y h u b 特性。 2 3 2 s i b l i n g l i n k a g el o c a l i t y 特性 在h u b 特性的基础上，a g g a r w a l 提出了s i b l i n g l i n k a g el o c a l i t y 特性怛”。 1 ) l i n k a g el o c a l i t y ，即某页面是主题页面，则这个页面所指向的链接页面也趋 向于该主题；2 ) s i b l i n g l o c a l i t y ，对于指向某主题页面的页面，它所链谈到的其 它页面也趋向于拥有这个主题。这实际上是h u b 特性的变形，主要是从页面的 设计者设计的角度考虑的。一个页面的设计者趋向于把本页面指向于与本页面 相关的其他页面，帮助用户在浏览本页面的同时，能方便得找到其他的相关页 面。通常把主题在w e b 上的这一特性称为s i b l i n g l i n k a g el o c a l i t y 特性。 2 3 3 站点主题特性 一个站点趋向于说明一个或几个主题，并且那些说明每个主题的页面较紧 密地在此站点内部链接成团，而各个主题团之间却链接较少。这主要与网站的 设计者的设计思路有关，每个网站在设计时都有目标，而这种目标往往就集中 在一个或几个主题中。而网站的浏览者往往也有一定的目的性，这个目的性一 般体现在用户趋向于浏览同一主题的页面。为了满足浏览者的这一需求，网站设 计者需要将相关内容紧密地链接在一起。中科院的余智华在文r 6 1 1 8 1 中具体研 究了站点主题团特性，他首先将站点内的链接分为六类：下行链、上行链、水 平链、交叉链、外向链和框架链，站点内的页面分为四类：主页、索引页面、 第8 页 亘坐盔兰亟主兰垡望茎 内容页面、参考页面，并为每一类链接和页面赋予不同的权重，然后通过向量 空间模型算法为每个页面分类并在站点内部结构特征的基础上，对站点页面 树按照自底向上进行主题聚类。试验结果证明了站点中存在着许多主题页面团。 2 3 4t u n n e l i n g ( 隧道) 效应 在w e b 中还有一类现象，就是主题页面团之间往往需要经过较多的无关链 接才能相互到达。这些无关链接就像一个长长的隧道，连接着两个主题团，如 何穿过低相关度区域进入高相关度信息区域是主题爬行系统需要解决的一个重 要i 口- j 题，f _ s t c r 1 9 】把这种现象称为“隧道技术”( t u n n e l i n g ) 。隧道技术的基本思 想是：当爬行器进入低相关网页区域时，扩大主题范围，而当爬行器重新进入 正常区域时，恢复到原来定义的主题范围。在主题爬行的过程中，t u n n e l i n g 的 存在极大地影响着采集的质量。为了提高采集页面的准确率，就需要提高过滤 相关性判定阈值，而阈值的提高将过滤掉大量的t u n n e l i n g ，使得采集系统很可 能丢失t u n n e l i n g 另一端的主题页面区域，甚至可能会因为找不到相关主题团 而提前终止爬行系统，进而影响了查全率( 或者说资源发现率) 。反过来，为了 提高查全率，就得经过大量的t u n n e l i n g ，需要降低过滤相关性判定阂值，但是 阈值的降低使得混进了大量的无关页面，加大了系统排除不相关页面的负担， 从而大大降低了页面的准确率。这是一个两难问题，但关键还是不能有效地区 别t u n n e l i n g 和其它大量无关页面。事实上，两个主题团之间的隧道数一般较 少，经过少量的跳数，又会很快回到主题页面区域。d b c r g m a r k 提出了一个 建立在统计基础上的解决方案1 2 0 l ，p a n t 贝i j 侧重研究如何扩展爬行范围 2 l l ，隧道 虽然隔离了相关页面，但他有时候却比相关路径能更快的到达相关区域，隧道 技术的难点是何时停止该隧道上的进一步扩展，即在该方向上进一步搜索已没 有必要了。网络可以看作是一种以依靠链接关系组成的图结构，而主题爬行则 是在此图结构上发现重