（计算机软件与理论专业论文）搜索引擎中初始urls优化研究.pdf

西华大学硕士学位论文 搜索引擎中初始u r l s 优化研究 计算机软件与理论专业 研究生项磊指导教师杜亚军 摘要 当今互联网的信息是海量的，如何从这些海量的信息中获取重要的和用户 查询相关的信息资源是很重要的，个性化搜索引擎在这样的背景下产生了。然 而，当前搜索引擎返回的搜索结果数目非常庞大，要从这么多的结果中找到有 用的信息，有时候显得很困难，如何获得更好的搜索结果，通过好的初始u r l s 更好的帮助用户找到自己感兴趣的信息，是本文的研究重点 搜索引擎的一个重要组成部分就是网络爬行虫，它是搜索引擎不可缺少的 组成部分。本文就是从爬行虫入手，重点讨论爬行虫的爬行起点初始u r i s 的 形成，通过初始u r l s 的个性化达到用户个性化的目的本文依此思路，就初 始u r l s 的获得，做了一系列的工作，并取得了如下研究成果： 1 本文提出了网络爬行虫初始u r l s 侯选集合的形成的基本思想和方法。 根据用户输入查询条件，从著名搜索引擎( a l t a v i s t a d 面e c t h i t ，e x c i t c ， g 0 0 西e ，h o t b o t ，l y c o sa n d 鼬o o ，e t c ) 搜索库中及时返回部分网页作 为初始u r l s 集合侯选集合。具体地，在实现方式上，本文讨论了通过 调用g 0 0 酉e 搜索引擎提供的w e bs e r v i c ea p i 函数，让g 0 0 画e 返回大 量的u i t l s ，作为后续研究工作的起点。 2 本文在有序概念格的概念的理论基础上，提出了通过设定的访问次数下 界得出用户的频繁访问路径，把这些路径按照频繁路径在用户访问路径 中出现的次数大小排序，再结合用户的历史点击获得用户的兴趣u r l s 集合的方法，并给出了其实现的算法，通过实例分析，说明了该方法 的有效性。 3 。本文研究中，提出了基于数据挖掘技术的种子u r l s 集合形成方法，通 过对用户浏览历史及其日志的挖掘形成用户兴趣库，利用1 中的候选集 第1 页 西华大学硕士学位论文 合，进行切词分词处理，形成网页文本向量，通过与用户兴趣向量的相 似度计算获得优化后的兴趣种子u r l s 集合，作为下一次爬行的种子， 也可以直接返回给用户u r l s 集合，供用户点击。 4 。最后本文发展了一个网络爬行虫程序( m y s p i d e r ) ，在西华大学校园 网实验环境中验证了基于数据挖掘技术的种子u r l s 集合形成方法，通 过与g o o g l e 、b a i d u 、l e a r n a b l ec r a w l e r 实验对比，m y s p i d e r 搜索结果 的用户满意度、网页召回率都较其它搜索引擎高，同时通过实验得出 了。m y s p i d e x 通过三次递归爬行返回给用户结果是充足的，合理有效 的”的结论。 关键词；初始u r l s ，元搜索，形式概念分析，数据挖掘，兴趣种子 第页 西华大学硕士学位论文 i n i t i a lu r l s o p t i m i z a t i o n i ns e a r c he n g i n e m a s t e rd e g r e ec a n d i d a t e ：x i a n gl c i s u p e r v i s o r ：d uy a j u n n o w a d a y s ，t h ei n f o r m a t i o no fi n t e r a c ti st r e m e n d o u s , h o wt oa c q u i r et h e i m p o r t a n ta n du s e rr e l e v a n ti n f o r m a t i o ni sv e r yi m p o r t a n tr e s e a r c h s e a r c he n g i n e a p p e a r si nt h i sb a c k g r o u n d h o w e v e r , t h e t o t a ln u m b e ro f s e a r c hr e s u l t si sv e r yl a r g e ， a n di ti sd i f f i c u l tf o ru s e r st of r e dt h eu s e f u li n f o r m a t i o ni nt h o s er e s u l t s h o wd ow e o r g a n i z et h es e a r c hr e s u l ta n dh o wd ow ef i n dt h eu s e f u li n f o r m a t i o n ? h e l p i n gu s e r f i n dt h ei n t e r e s t i n gi n f o r m a t i o n - b yg o o di n i t i a ll l i isi st h er e s e a r c hf o c a lp o i n t o n eo ft h ei m p o r t a n tp a r t si ns e a r c he n g i n ei st h ew e bc r a w l e r , i ti sn o o e s s a r y f o rs e a r c he n g i n et oc r a w lt h ep a g e s t h i sp a p e rb e g i n sw i t hw e bc r a w l e ra n d e m p h a s i z e st od i s c u s st h ei n i t i a lp o i n to fw e bc r a w l i i l g m ci n i t i a lu r l sf o r m i n g w em a k et h ep u r p o s eo fu s e ri n d i v i d u a l i z a t i o nb yi n i t i a lu r l si n d i v i d u a l i z a t i o n a c c o r d i n g t ot h i st r a i no ft h o u g 吣w ed oal o to fr e s e a r c ho nu r l sf o r m i n g ；t h e r e s e a r c hc u m p l i m e n t sa r ed e s c r i b e db e l o w ： 1 t h i sp a p e rp r o p o s e st h eb a s i ct h o u g h ta n dm e t h o do f c a n d i d a t ei n i t i a lu r l s f o r m i n g a c c o r d i n gt ou s e ri n p u tc o n d i t i o n ，p a r t i a lw e bp a g er e t u r n i n gf r o mf a m o u s s e a r c he n g i n e ( a i t a v i s t a ，d i r e c t h i t ，e x c i t e ，g o o g l e ，h o t b o t ，b ，c 憾a n dy a h o o , e t 0i sc o n s i d e r e dt ob ei n i t i a lu r l s i nf a c t , t h i sp a p e rd i s c u s st h a tb yu s i n gg o o g l e w e bs e r v i c ea p i ，w el e tg o o g l er e t u r nal o to fu r l st ob et h es t a r to fc o n s e c u t i v e r e s e a r c hw o r k 2 b yu s i n gt h eo r d e r e dc o n c e p tl a t t i c ep r o p o s e db ya n o t h e rp e r s o n , w eg e tt h e u s e rt r a v e r s ep a t h , e s p e c i a l l yd i s c o v e r i n gf r e q u e n tt r a v e r s a lp a t hb yg i v i n gt h ea c c e s s f r e q u e n c ym i n i m a l w eo r d e rt h e s ep a t h sb ya p p e a r a n c ef r e q u e n c y , t h e n , w eg e tu s e r i n t e r e s ts e e d sb yu s e rc l i c k i n gi no r d e rt op r e p a r ef o rt h ec o n s e c u t i v ec r a w l i n g a t 第页 西华大学硕士学位论文 l a s t , w ep r o p o s et h ea l g o r i t h ma n di n s t a n c e 3 b yd a t am i n i n gt h eu s e rb r o w s e rh i s t o r ya n dl o g , w ea c q u i r et h eu s e r i n t e r e s t s t h e n , w ec o m b i n et h er e s u l t so f1t og e tt h ei n t e r e s t i n gs e e d s , t h e s es e e d s c a nb ec l i c k e dd i r e c t l y , t h a ti st os a y , t h e yc a nn o to n l yb et h es e e d so fn e x tc r a w l i n g b u ta l s ot h er e s u l t sr e t u r n e dt ou s e r s 4 a tl a s t , m yp a p e rd e v e l o p saw e bc r a w l e r ( m ys p i d e r ) , w ec h e c kt h i su r l s s e e d sf o r m i n gm e t h o di nt h ex i h u au n i v e r s i t yw e b ，b yc o m p a r i n gw i t hg o o g l e ， b a l d u l e a r n a b l ec r a w l e r , n er e s u l to fm ys p i d e ri sh i g h e rt h a no t h e rs e a r c he n g i n e i nu s e rs a t i s f a c t i o n , u s e rr e l e v a n c ea n dw e br e c a l lr a t i o , a tt h es a m et i m e , t h e s e e x p e r i m e n t sc o n c l u d e st h a tt h eu s e rr e s u l to fm ys p i d e ra f t e rt h r e et i m e sc r a w l i n g i s e n o u g h ，r a t i o n a l , e f f i c i e n t k e y w o r d s ：i n i t i a lu r l s ，m e t as e a r c h ，f o r m a lc o n c e p ta n a l y s i s ，d a t am i n i n g ； i n t e r e s t i n gs e e d s 第页 西华大学硕士学位论文 申明 本人申明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果。也不包括为获得西华大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献已在论文 中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间指导下取得的，论文成就归西 华大学所有，特此声明。 作者签名：移趸磊刀年石居笋日 名埒歹相 第5 9 页 西华大学硕士学位论文 第1 章绪论 1 1 初始u r l s 集合及其研究酊意义 ( 1 ) 什么是搜索引擎中的初始u r l s 初始u r l s 是网络爬行虫爬行的起点，一个好的爬行策略需要一个好的起 始点，这就是初始种子之所以重要的意义所在! 下面举一个例子来阐述什么是 初始l 限i s 。 网页爬行虫是用来在i n t e m e t 上自动发现和搜集w e b 网页的一个程序， 它从一个起始u r i s 集合出发，沿着网页之间的链接。按照一定的搜索策略 ( 宽度优先或深度优先) 搜集相关阀页网页爬行器已被网络搜索引擎广泛使 用。给定一个初始网页用，网页爬行器从p 0 的u r l 出发，首先取得网页 p 0 ，然后从网页p 0 中提取它所包含的所有u r l p l ，i 2 ，1 3 ，由此类推，提取 出p 4 ，p 5 ，p 6 ，p 7 ，p 8 ，p 9 。其中，p o 是整个爬行的起始点，也就是讨论的 初始神子中的一个u r l ，如图1 1 所示。 f i g a r e1 1i n i t i a lu r l sd e f i n i t i o ne x p r e s s i o n 图1 1 初始u r l s 含义示意图 从图1 1 可以看出p o 是本次爬行的开始，也就是本次爬行的初始种子，后 面爬行的结果直接受这个起始点的影响，个性化的搜索要求初始种子是个性化 的，也就是和用户兴趣相关的，下面分别从这个性化和智能化两个方面进行简 第l 页 西华大学硕士学位论文 单叙述。 ( 2 ) 初始u r l s 对个性化的网页搜索研究的意义 i n t e r a c t 的迅速成长使得网上的信息量猛增，因此互联网日益成为人们获取 信息的手段。基于关键词的搜索引擎技术迎合了人们查询信息的需要。但是返 回给用户的不相关的数据过大，客观上搜索效果依然是有限的。个性化服务因 此应运而生，它主要是通过分析不同用户的兴趣习惯从而实现主动地向不同用 户实现推荐网页的目的。 、 用户访问过的数据是用户描述文件的主要来源之一，用户描述文件可以分 为基于内容和基于链接这两种类型。前者主要采用关键词矢量和分类技术，这 些技术的缺点是有时需要用户显示的信息以及无法准确地表达用户兴趣，例如， “奔驰”和“福特”在关键词的层次是毫不相干的词，然而在有些情况下却表 示著名的汽车公司名称。基于链接的描述文件主要表示为用户浏览模式，如可 以通过目志文件发现用户的浏览页面顺序，它的缺点是无法反映出相应的访问 内容。 基于这两者的缺点，结合两者，取长补短。任何搜索引擎本质上都需要初 始的资源定位符，从这个基点出发向其它的网页扩展，一般的搜索引擎在选择 初始u r l s 时只是考虑到其中的一个方面，在考虑它的时候分别从内容和链接 两个方面出发，基于概念格的用户模型的发现是通过发现用户频繁访问路径推 荐初始u r l s ( 基于链接) ，基于数据挖掘的用户模型是通过发现用户兴趣模型， 通过比较网页主题内容与用户兴趣进行匹配( 基于内容) ，这样才能真正的满足 用户的要求，实现个性化的搜索。 因为爬行虫必须尽可能搜集与用户兴趣相关的网页，所以它需要一系列好 的初始统一资源定位符，这些好的统一资源定位符指向许多相关的网页，作为 网络搜索的初始点，k l e i n b c r g 把这类型的统一资源定位符叫做中心资源定位符。 基于这种考虑，初始资源定位符是很重要的，从它出发扩展得到的网页结果集 就是要返回给用户的结果网页集，由此可以看出从初始种子出发得到的网页集 合要想满足用户的需求，必须在选择初始集合的时候遵循用户的兴趣。 用户的兴趣获得是个性化搜索引擎中，初始u r l s 获得的基础，它也就是 用户的兴趣挖掘，用户的兴趣的跟踪必须有一定的方法，通过一系列的数据挖 掘的方法来得到用户的兴趣，比如说；用户在某一主题上停留的时问；点击网 第2 页 西华大学硕士学位论文 页上的链接的次数；保存或打印网页与否；在文档内部有没有搜索。通过这些 参数计算出网页的权重，把权重高的放在初始u r l s 集合中，进行扩展得到最 终的用户需要的结果网页。所以对初始u r l s 的选择的研究意义在于着眼与用 户的需求，有很大的实际意义基于用户的兴趣选择的初始种子，就能在后续 的爬行的过程中取得很好的个性化效果。 ( 3 ) 初始u r l s 对智能搜索的意义 网络蜘蛛是利用互联网的链接结构获取信息的程序，又名s p i d e r ，它通过网 页的链接地址来寻找网页，从网站的某一个页面( 通常是首页) 开始，读取网 页的内容，找到在网页中其它的链接地址。然后通过这些链接地址寻找下一个 网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果把 整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的 网页都抓取下来。其在搜索引擎中的位置如图1 2 所示。 f i g u r e1 2s e a r c he n g m e s t r u c t u r e 图1 2 搜索引擎结构图 如果在初始u r l s 的选择上能够利用智能的网络蜘蛛来获取这些初始种子， 那么后面的爬行将也是十分智能化的，因为一个好的开始是成功的一半，本文 认为初始种子的选择这个开始超过了一半的功劳 目前网络蜘蛛依据简单可数的几个规则爬行着，从来没有明确的爬行目标。 只会毫无目的地抓取芜杂的信息，处理互联网表层信息，很勤恳但毫无个性 而个性化搜索引擎则需要有智慧的网络蜘蛛，有方向、有目的、有计划地抓取 信息，同时肩负着寻找、发现、定位、提交符合要求的信息的任务。它不仅能 自动自发地自我管理，而且能感知自身所处的环境并做出反应；不仅具备专业 的知识，而且具有学习能力；对信息的处理不仅有广度，而且有深度；不仅有 第3 页 西华大学硕士学位论文 预处理也有后处理。 对网络蜘蛛( s p i d e r ) 的智能化研究主要有：m i c h a e lc h a e 和l - i s i n c h u nc h e n 等使用h o p f i e l d 网络从初始u r l s 出发，将u r l s 集中的每一个u r l 作为网络的 初始层结点，采用u r l s 中的u r l 链接网络的i 瓜i 作为第二层网络的结点，依次 到第n 层，其中上一层结点i 与下一层结点j 的链接权重是对应网页内容相关度， 采用网络的学习与竞争的机制来实现h o p f i e l dn e ts p i d e i 【1 1 1 2 1 ；1 9 9 8 年，c h r i s t o p h e r c y a n g 和j e m i n cy e n 提出模拟退火算法( s i m u l a t e da n n e a h n gs p i d e r ) ，从技术 上解决网络蜘蛛某些的爬行问题p l ；2 0 0 4 年，李学勇等报告了一个基于模拟退 火机制的网络蜘蛛【4 】，避免网络蜘蛛过早陷入w e b 搜索空间中局部最优子空间的 陷阱，利用模拟退火算法在选择优化方面的“非贪婪性”。在网络蜘蛛搜索过程 中，每次除选择价值最优的链接( 简称“最优链接”) 外，还以一定概率有限度 地接收价值次优的链接，随着搜索过程的进行，逐渐使选择次优链接的概率趋 近于0 。克服了现有s p i d e r 搜索方法启发式策略中对t r r l 选择估计的非精确性和 局部性；文献阁中和f o o m e dc r a w l e r l 6 1 的作者提出的搜索算法中在给定的u r l 后，选用一种评价函数对其链接的网页进行评价，选用评价值较高的网页进行 爬行；1 n h er e i n f o r c e m e n tl e a r n i n gs p i d e r t t l 希l l n e r e m e n t a lc r a w l e r t s 】采用增强式学 习算法来实现在网络蜘蛛搜索网页过程中逐步增强爬行的i 限i 与查询词的相关 性，来实现结果逐步与用户的需求接近。 为了提高s p i d e r 的爬行速度，2 0 0 1 年b e m d t h o m a s 开始第一次将人工智能方 法弓l , k s p i d e r 的研究中，分析t s p i d e r 的智能行为，提出了a is p i d e r 的概念1 9 】； 2 0 0 2 年g a u t a mp a n t 等提出了y o u ro w ni n t e l l i g e n tw e bc r a w l e r s l l o l ；为了提高 s p i d e r 的爬行速度，2 0 0 2 年，s h k a p e n y u k 和v l a d i s l a v 设计了d i s t r i b u t e dw e b c r a w l e r l l l i l l z l 。等等这些爬行虫都能很好的对爬行过程中的初试u r l s 的智能化 取到明显的效果，他们愿意在初始u r l s 利用智能化的s p i d e r 去优化它，是觉得 这样做能取到很好的效果 1 2 初始u r l s 集合形成方法研究 现在的搜索引擎五花八门，其中以国内的b a i d u 口刀和国外o o o g l e t 蚓最y j a 们所知和使用，这些都是第二代搜索引擎，s o h u 的s 9 9 0 u 1 3 9 号称自己达到了第 三代搜索引擎智能化，个性化搜索的程度，但是远没有他们所宣称的那样优秀。 第4 页 西华大学硕士学位论文 初始种子的选择，也就是说是它的再次选择优化的方法很多都不同于上面 的通用搜索引擎( g o o g l e ，b a i d u , s o h u ) ，这些搜索引擎都有自己的通用算法，基 于主题的爬行虫f o c u s e dc r a w l e r , t o p i c - s p e c i f i cc r a w l e r 是关于某一个主题的搜 索引擎，也就要求初始u r l s 跟这个主题的相关度也满足某一个阈值；而另外 一种是个性化的搜索引擎，这种搜索需要它们的初始u r l s 是跟某个个别的用 户是相关的，用户的兴趣记录是很重要的，建立用户兴趣库是很重要的，建立 的方法不同，得到的初始种子的好坏程度也是不相同的，因此，建库的同时也 是对初始u r l s 的优化的过程，这种思想在本文的数据挖掘获得初始u r l s 中 有充分体现。 在搜索引擎智能化，个性化，主题化火热研究的形式背景下，f o c u s e d c r a w l e r , t o p i c - s p e c i f i cc r a w l e ra n di n t e l l i g e n tc 扭w l i n g , p e r s o n a l i z e dc r a w l i n g t 3 1 1 1 4 i i l s 1 6 1 的 初始种子的研究应运而生国内外对基于用户和智能的搜索引擎的研究如火如 荼，在国内，卢效峰 2 8 1 在。基于用户选择的搜索引擎的算法研究”中提出使用 平均用户概率的差商来不断校正关键词和页面的相关度，通过与现有搜索引擎 算法的结合，可以取得关键词和页面的最佳相关度，这些相关度的算法等可以 用来对初始u r l s 选择过程中，因为要评定初始u r l s 的好坏可以通过计算相关 度来确定。李振星 2 9 1 等人提出一种基于潜在语义索引的w e b 信息预测采集过滤 方法。在样本文档集潜在语义索引对文档相似计算基础上，构造出用户兴趣模 型，判断页面相关性进行文本过滤，这种语义的过滤方法同样对初始u r l s 的选 择具有借鉴意义；曾春等人1 3 0 1 对个性化服务技术中用户描述文件的表达与更 新、资源描述文件的表达、个性化推荐技术、个性化服务体系结构以及该领域 的主要研究成果进行了综述通过比较现有原型系统的实现方式，详细讨论了 实现个性化服务的关键技术，个性化服务的关键技术可以用到对初始u r l s 集合 进行个性化的处理上杜亚军等人1 3 1 1 分析了关键词搜索引擎的利弊，根据人们 输入信息的不确定性、其在网上检索信息的过程应该是智能化的特点，提出了 提高中文搜索引擎智能能力的方法，这种方法可以用在初始种子的选择上张 玲莉等人1 3 2 1 采用在网站结构图上表现网站使用情况，其中的用户网络行为模式 跟本文的课题研究很相关；厉亮等人1 3 3 】讨论了主题搜索引擎，并且重点探讨了 以敦煌学主题w e b 信息为样本的主题搜索引擎信息采集策略，并给出了一种比 较理想的主题搜索引擎的设计方案，这种主题搜索引擎的设计方案可以用到初 第5 页 西华大学硕士学位论文 始u r l s 的主题分类上，这些中文文献的方法都可以用到对初始u r l s 进行智能 化，个性化的处理。 在国外，在基于主题分类的爬行虫的初始种子的优化方面，a r u n g s l l w 锄叠切 等人提出了一个自学习的主题分类的网络爬行虫，他们提出了一些算法，包括 第一阶段和后面阶段的爬行，第一阶段爬行提高了主题爬行虫的性能，他们建 立知识库去记录爬行虫的经验，在这篇文章中，在建知识库中涉及到初始u r l s 的选择的问题，它使用的是记录相关的初始u r l s ，使得他们能够在作为下一 次爬行的时候能够获得更多的相关的网页；c h a k r o v b a t i 1 4 1 等人定义一种爬行虫， 用户可以为爬行虫选定一些初始的爬行u r l s ，在这种情况下用户需要有一些 背景知识去选择恰当的初始资源定位符；s a n g u kn o h l l 5 】等人提出了一个主题分 类爬行虫技术相关度和使用词频，文档频率去改善相关网页的主要集合。另外 一类是集中式爬行虫，集中式爬行是一种比较新的很有前景的方法，它提高了 专业搜索引擎的召回率，尽管如此，为了扩大集中式搜索的范围，i i a l u n q i n 等 人1 1 6 l 提出了一种新的利用元搜索的方法去提高爬行虫的性能，与此同时，他们 在文献【1 7 】还使用全局算法比如遗传算法去改善集中式爬行的效能h o n g y u l i u 1 8 培人提出了一种用隐式马尔可夫链去建造有学习能力的用户模型，他们相 信他们的爬行虫比一般使用的最好优先策略主题爬行虫要更好，这种用户模型 能够很好的对初始u r l s 集合进行个性化处理。 在个性化的初始u r l s 集合方面，首先必须获得用户的兴趣，只要把用户 的兴趣利用到初始集合中，得到的网页结果集合就是用户想要的，用户的兴趣 可以通过三个途径来获得：首先，显式的获得，比如直接向用户闻及所看内容 的喜好程度或偏好等级；但是显示的获得这些信息有以下几个方面的缺陷的： 用户有时候会提供不一致或不正确的信息用户的兴趣随时问的改变而改变 让用户感觉到额外的负担。其次，隐式的获得，这种方法可以通过数据挖掘 的方法把用户的兴趣挖掘出来，比如，观察用户在在线文档上停留的时间；直 接点击某一个文档链接的次数。再次，部分用户参与，也就是不需要得到很多 用户的信息可以避免用户隐私的暴露这些用户的兴趣的挖掘出来以后可以用 来计算用户文档与网页文档的相似度或者说是某些作为爬行种子集的权重计算 的一种度量。从而得出用户相关的网页结果集。h a d r i e nb u l l o t 等人1 1 9 j 提出了一 种用数据挖掘的方法来挖掘用户的兴趣的新的体系结构，这种体系结构能够通 第6 页 西华大学硕士学位论文 过挖掘用户的兴趣来改善爬行虫增量爬行的性能，可以用它来提高初始u r l s 的优化能力；m i c h a e lc h a l i 等人例提出了一种基于客户端的架构，这种架构采 用了词典和自我组织图两种技术，这两个系统都可以被认为是部分用户参与样 例，用户需要参与爬行的过程，但是他们不需要提供任何隐秘的信息，比如他 们的偏好的信息，最终他们的选择都要映射成初始u r l s 的选择上；m i r c o s p e r e t t a 等人f 2 l 】使用查询词和文摘的网页信息去作为用户模型的参考概念层次， 这种用户模型的建造方法其实质上也可以用来对初始u r l s 集合进行优化，得 到个性化的初试集合；k y u n g - j o o n gk i l n 等人瞄】提出使用模糊概念网络去优化 那些基于链接的方法返回的结果，这种模糊概念网络是基于用户文档记录的， 它也可以用来对初始u r l s 爬行集合进行优化；p a u l - a l e x a n d r u 等人【2 3 】提出了 一种新的算法h u b f i n d e r ，这种新的算法是用来使用新的网络图结构来寻找 相关网页的方法，它也可以用来对初始u r l s 集合进行改造和优化；j u n g h o oc h o 等人【刎定义了几种重要的机制，排序策略和性能进化手段来解决如何使得重要 的网页先被爬行虫爬行的问题，这个问题也就是u r l s 集合选择的问题，可以 把这些方法用在初始u r l s 集合上；c h i n g - c h ih s u 等人口l 提出了一种基于相关 背景图的方法来解决如何为没有访问的网页分配恰当的访问顺序的问题，其实 就是用这种新的方法来解决u r 岱捧序的问题，同样可以用到初始u r l s 的选 择后的排序上。 总结上面文献资料可以看出，初始u r l s 的建立是限定了网页爬虫的爬行 空间范围，是搜索引擎的关键起始点可以从以下三个方面进行讨论： 1 通用搜索引擎：将搜索引擎提供给用户的数据库中的网页按照某种策 略进行排序，比如6 0 0 0 e 的p a g e i a n k ，然后把排在上面的，权重较高 的作为下次爬行的初始种子。在新的网页出现时，再重新更新网页的 权重。 2 个性化搜索引擎：在个性化搜索引擎中，用户的需要是最重要的，初 始u r l s 的形成来源于以下三个方面，第一，当用户是第一次访问网 页时，即它是非注册用户的时候，可以给用户设计一个表单，它的内 容包括：( 1 ) 用户主页，它是用户展现自我的平台，记录这个u r l 及 其主题描述和主要内容的描述；( 2 ) 用户自己感兴趣的网页和起主题 描述，对主要阳容提取其关键词，记录这个主题关键词和相应的u r l s 。 第7 页 西华大学硕士学位论文 第二，用户日志库中存有用户的浏览网页的历史记录，从用户的历史 数据库中可以挖掘出用户的兴趣和它对应的u r l s ，第三，搜索引擎主 动将本次搜索过程中与用户兴趣相符的u r l s 记录下来。这三种u r l s 合起来就构成了个性化搜索引擎的初始u r l s 。 3 基于主题搜索引擎：这种搜索引擎把搜索范围限制在某一个特定的范 围以内，因此，在满足用户的前提下，适合某一部分主题的范围，由 此，这种初始u r l s 的形成过程可以这样描述： ( 1 ) 用户提交关键词，从权威的搜索引擎中去获得p a g e r a n k 和h i t s 值较高的网页，记为u r l 0 。 ( 2 ) 根据用户的需要，通过用户兴趣模型过滤到u r l 0 中与用户不相 关的u r l s ，剩余的记为u r l l 及其主题关键词 ( 3 ) 通过主题关键词与这个现有主题的相似度的计算，得出在大于某 一个阚值的u r l 2 。此u r l 2 就为基于某一个主题的特定用户的 初始种子，根据这个种子去爬行到的网页是满足召回率，准确率 的要求的主题爬行种子 对于第三点，为了能够方便地处理链接和进行主题相关度计算，使系统各组成 模块有机地协调运作，需要使用5 个u r l 队列，每个队列保存着同一种处理状态 的u r l 。 圈 f i g u r e1 3i n i t i a ls e e d ss l a t n st r a n s f e r r i n g 图1 3 初始种子状态转换图 第8 页 西华大学硕士学位论文 ( 1 ) 等待队列：在这个队列中，u r l 等待被爬虫处理，新发现的u r 嵫加人到 该队列。 ( 2 ) 处理队列：爬虫开始处理u r i 肘，被传送到这一队列为了保证同一个 u r 坏能多次被处理，一个u 砌澈处理后，就被移送到错误队列或者抛弃队列 或者完成队列。 ( 3 ) 错误队列：如果在下载网页时发生错误，它的i 瓜i 将被加入到错误队列， 一旦移入错误队列，爬虫不会对它作进一步处理。 ( 4 ) 抛弃队列：如果下载网页没有发生错误，且主题相关度的计算结果小于阈 值，则放入该队列，一旦移入抛弃队列，爬虫不会对它作进一步处理。 ( 5 ) 完成队列：如果下载网页没有发生错误，且主题相关度的计算结果大于或 等于阈值，就要把从中发现的u r l 放人等待队列，处理完毕把它加人到完成队 列，到达这一队列将等待排序模块的处理。同一时间一个u r 【只能在一个队列 中，这也叫做u r l 的状态，图1 3 说明了这些状态的关系以及网页如何从一个状 态转换到另一个状态。 从另外的角度来看，初始种子也可以分为以下三种：( 1 ) 预先给定的初始抓 取种子样本，这种对应于是根据某一个主题的初始种子；( 2 ) 预先给定的网页分 类目录和与分类目录对应的种子样本，如y a h o o ! 分类结构等，对应于那些搜索 引擎门户网站；( 3 ) 通过用户行为确定的抓取目标样例。其中，网页特征可以是 网页的内容特征，也可以是网页的链接结构特征，对应于基于用户模型的个性 化的搜索引擎。 综上所述，国内外针对爬行虫的个性化，特别是爬行虫中重要的初始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 i , s 集的建立是网络蜘蛛智能化的关键所在，本文从几种角 度对比获得初始u r l s 的方法的好坏，从而获得好的搜索起点，为后面的爬行做 第9 页 西华大学硕士学位论文 好充分合理的准备。 1 3 本文的研究内容结构 如何选取初始u r l s 是搜索引擎的重要的步聚，他们是搜索引擎重要组成 部分网络爬行虫的开始点，而返回给用户的结果跟这个初始出发点的关系密切 相关，研究它具有很重要的现实意义 研究内容： 1 通过使用通用搜索引擎，比如g o o g l e 的w e b a p i 服务构建元搜索来获得 一些关于某些类别的初始u r l s 的候选集合 2 对收集回来的候选网页集合，利用切词分词程序表示为文本向量，为后 序的优化做准备。 3 讨论了基于有序概念格用户访问模型的初始u r l s 集合，利用这个格的 模型发现用户频繁访问路径( 链接相关) ，给出相应的算法并推荐给用户选 择，从而获得用户相关的初始种子，为下一步爬行打下基础。 4 基于数据挖掘的用户兴趣模型的初始u r l s 集合，利用数据挖掘中常用 的数据统计，寻找规律的方法，获得用户的兴趣和关于这个兴趣随时间的 改变而改变的反馈公式，得到最新的用户兴趣树，与候选网页进行向量相 似度计算( 内容相关) ，把相似度高的返回给用户 本文以后的内容安捧如下：第二章是元搜索引擎，通过g o o g l e a p i 获得数 据集合，得到u r l s 候选数据集合；第三章是用基于有序概念格的方法来获得 初始u r l s 集合，给出了算法和相关实例：第四章是基于数据挖掘的方法获得 初始u r l s 集合，通过对用户浏览历史及其日志的挖掘形成用户兴趣库，利用 第二章中的候选集合，然后进行切词分词处理，形成网页文本向量，通过与用 户兴趣向量的相似度计算获得优化后的兴趣种子u l 【】匹集合；第五章是实验了 第四章的系统，并做出了评价；第六章总结全文，并展望未来的工作。 整个文章的逻辑结构框图如图1 4 所示： 第1 0 页 西华大学硕士学位论文 f i g u r e l 4 l o g i c f i g u r e o f t h i s p a p e r 图1 4 本文的逻辑框图 第l l 页 西华大学硕士学位论文 第2 章初始u r l s 候选集的构成 元搜索引擎是指通过一些通用搜索引擎提供的a p i 接口，利用w e b 服务返 回相关的网页，作为初始u r l s 集合的候选集合，并为后面的优化选择初始种 子打下一个很好的数据基础。 本章先简要介绍了元搜索引擎的基本结构和分类，然后利用元搜索引擎形 成初始u r l s 侯选集合，为后面的几章作数据铺垫。 2 1 元搜索引擎基本构成 为了更好的说明元搜索引擎的构成，先简单的介绍一下独立搜索引擎的工 作原理和基本构成。独立搜索引擎根据用户的查询请求，按照一定的算法从索 引数据库中查找对应的信息返回给用户。为了保护用户查找信息的精度和新鲜 度，搜索引擎需要建立和维护一个庞大的索引信息数据库。独立搜索引擎中索 引数据库的信息是通过一种叫网络蜘蛛( s p i d e r ) 的程序从互联网中采集得到的 网页。所以，一般独立搜索引擎主要由网络蜘蛛，索引与搜索引擎软件等部分 组成【柏l 。 与独立搜索引擎相比，元搜索引擎不需要维护庞大的数据库，也不需要网 络蜘蛛去采集网页。具体说来，元搜索引擎主要由三部分组成( 如图2 1 所示) ， 即：请求提交代理、检索接口代理、结果显示代理。“请求提交代理”负责实现 用户的。个性化”的设置要求，包括调用哪些搜索引擎，检索时间限制，结果 数量限制等。“检索接口代理”负责将用户的请求“翻译”成满足不同搜索引擎 的“本地化”要求的格式。“结果显示代理”负责所有的元搜索引擎检索结果的 去重、合并、输出处理等 请求提交代理，负责将用户的请求发给独立的搜索引擎一般的元搜索引 擎设定了它所调用的独立搜索引擎，比如w i d e w a y s e a r c h 有些元搜索引擎让用 户自己选择所用的搜索引擎。还有一种通过分析用户的兴趣和网络的实际情况 来选择搜索引擎，这有利于提高用户查询的准确度和对用户的响应速度。如何 智能的选择成员搜索引擎是元搜索引擎的一个关键技术。 检索接口代理，由于不同的搜索引擎所支持的查询方式的不同，比如有些 搜索引擎支持s t e m m i n g 方式，即使是同一种方式，也有不同的表达方法，所以 第1 2 页 西华大学硕士学位论文 必须将元搜索引擎中的查询请求映射到对应的搜索引擎中，而且使得语义信息 不丢失。 结果显示代理，元搜索引擎的结果一般有网页标题，内容摘要，所指向网 页的u r l , 相关度，信息返回时间，所采用的引擎标志等这些搜索结果是多 f i g u r e2 1m e t as e a r c he n g i p r i n c i p l e 图2 1 元搜索引擎原理图 个独立搜索引擎的并集元搜索引擎的结果应该具有多种排序的方式以满足不 同的用户的要求。元搜索引擎常用的排序方式有：相关度排序、时间排序、域 名分类排序、搜索引擎排序等。 元搜索引擎把用户的查询串分配给几个指定的独立搜索引擎，在将各搜索 引擎所得到的结果分级排序，删去重复的内容，然后给出查询结果也就是说 元搜索引擎是建立在独立搜索引擎之上的搜索引擎。 2 2 元搜索引擎分类 元搜索引擎由多种不同的分类方式【4 1 1 1 4 2 l ，如可以根据用户应用的模式、调 用独立搜索引擎的方式来进行分类，根据图2 1 中请求提交代理、检索接口代 理和结果显示代理的复杂度，将元搜索引擎可以分为简单元搜索引擎和复杂元 搜索引擎；根据请求提交代理、检索接口代理和结果显示代理所在的位置不同， 又将复杂元搜索引擎分为桌面型搜索引擎和基于w e b 的搜索引擎。 简单的元搜索引擎，它实际上不能称为搜索引擎。它只是给用户提供一个 第1 3 页 西华大学硕士学位论文 搜索引擎列表，用户可以选择所用的搜索引擎。用户输入查询请求，然后直接 以c g i 方式( ( c o m m o ng a t e w a yi n t e r f a c e ) 是 r r t p 服务器与你的或其它机器上 的程序进行“交谈”的一种工具，其程序必须运行在网络服务器上) 调用对应 的搜索引擎。由于是由用户选择搜索引擎，而且查询只能发送到一个搜索引擎， 所以请求提交代理和检索接口代理的设计就非常简单，可以直接设计在静态网 页中。简单元搜索引擎不进行搜索结果的处理，这就缺省了图2 1 中的结果集 成代理。其实，将简单元搜索引擎叫做搜索引擎列表更合适简单元搜索引擎 设计上的简单性，成为众多网站采用的提供搜索服务的方法 桌面型元搜索引擎，它以程序