第３６卷　

ＶｏＬ３６　第１１期　

Ｎｏ．１　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１０年６月　

Ｊｕｎｅ　２０１０　

・人工智能及识别技术・　文章编号：１ｏ０ｏ—０４２８（２０１０）１】—’ｏ１６７—＿０３　文献标识码：Ａ　中图分类号：ＴＰ３１１．１３　

基于遗传算法的聚焦爬虫搜索策略　

曾广朴，范会联　

（长江师范学院数学与计算机学院，涪陵４０８　１００）　

摘要：为了提高聚焦爬虫的搜索效率，提出一种结合内容评价和链接结构搜索策略的优点并利用小牛境遗传算法进行全局寻优的搜索策　略。改进遗传算子和小生境遗传算法，将待搜索的网页ＵＲＬ作为遗传个体，采用概率变迁规则和小生境淘汰运算引导搜索方向。实验结　

果证明，与聚焦爬虫的其他实现技术相比，该策略在抓取主题相关网页时具有更高的查准率和查全率。　

关键词：聚焦爬虫；遗传算法；小生境；主题相关度　

Ｓｅａｒｃｈ　Ｓｔｒａｔｅｇｙ　ｏｆ　Ｆｏｃｕｓｅｄ　Ｃｒａｗｌｅｒ　Ｂａｓｅｄ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　

ＺＥＮＧ　Ｇｕａｎｇ—ｐｕ，ＦＡＮ　Ｈｕｉ—ｌｉａｎ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ，Ｙａｎｇｔｚｅ　Ｎｏｒｍａｌ　ＵｎｉｖｅｒｓｉＷ，Ｆｕｌｉｎｇ　４０８　１　００）　

［Ａｂｓｔｒａｃｔ］Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｓｅａｒｃｈ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｆｏｃｕｓｅｄ　ｃｒａｗｌｅ　ｂａｓｅｄ　ｏｎ　Ｎｉｃｈｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ（ＮＧＡ），ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｇｌｏｂａｌ　

ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｓｅａｒｃｈ　ｓｔｒａｔｅｇｙ　ｗｈｉｃｈ　ｃｏｍｂｉｎｅｓ　ｔｈｅ　ａｄｖａｎｔａｇｅｓ　ｏｆ　ｃｏｎｔｅｎｔ　ｅｖａｌｕａｔｉｏｎ　ａｎｄ　ｌｉｎｋ　ｓｔｒｕｃｔｕｌ　ｅ．ＵＲＩ　ｓｅａｒｃｈ　ｄｉｒｅｃｔｉｏｎ　ｉｓ　ｇｕｉｄｅｄ　ｂｙ　

ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｇｅｎｅｔｉｃ　ｏｐｅｒａｔｏｒｓ　ａｎｄ　ＮＧＡ．Ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｏｔｈｅｒ　ａｌｇｏｒｉｔｈｍｓ，ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｉｎｄｉｃａｔｅ　ｔｈａｔ　ｔｈｉｓ　ｓｔｒａｔｅｇｙ　ｈａｓ　ｈｉｇｈｅｒ　ｐｒｅｃｉｓｉｏｎ　ａｎｄ　

ｒｅｃａｌｌ　ｉｎ　ｓｅａｒｃｈｉｎｇ　ｔｈｅ　ｔｏｐｉｃ　ｐａｇｅｓ．　［Ｋｅｙ　ｗｏｒｄｓｌ　ｆｏｃｕｓｅｄ　ｃｒａｗｌｅｒ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｎｉｃｈｅ；ｔｏｐｉｃ　ｒｅｌｅｖａｎｃｙ　

ｌ概述　聚焦爬虫是专为查询某一领域或主题信息而出现的网页　

抓取工具。不同于通用搜索引擎，由于聚焦爬虫抓取的内容　

只限于特定的主题或专门领域，因此其在搜索过程中无须对　

整个Ｗｅｂ进行遍历，只需选择与主题相关的页面进行访问。　

相对于通用网络爬虫，聚焦网络爬虫需要解决的关键问题是　

如何判断一个网页是否与主题相关以及如何根据主题相关度　决定待爬行ＵＲＬ的访问次序以获得更高的查全率和查准率。　

２相关研究工作现状　

２．１小生境遗传算法的基本思想　经典遗传算法的主要问题是容易产生最终并不能保证收　

敛到全局最优解、而是过早地收敛到某个局部极值点的现象。　

出现这一现象的根源在于该算法在进行粗略搜索时容易丢失　

最优解，进行精细搜索时容易陷入局部最优解。因此，需要　

引入一种既能保证种群多样性、又能保证算法高效性的机制。　

近年来人们将生物学中小生境现象引入遗传算法，其最优保　留原则使算法在保证多样性的同时能够保留最优解。　

小生境遗传算法（Ｎｉｃｈｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ＮＧＡ）的基本　思想是＿】Ｊ：首先两两比较群体中各个个体之间的距离，若这　

个距离在预先指定的距离　之内（即在小生境内），再比较两　

者之间的适应度大小，并对其中适应度较低的个体施加一个　

较强的罚函数，从而极大地降低其适应度，这样，在预先指　

定的距离，Ｊ之内的２个个体中较差的个体经处理后适应度变　

得更差，它在后面的进化过程中被淘汰的概率极大，即在距　离￡之内将只存在一个优良个体，从而既维护了群体的多样　

性，又使各个个体之问保持一定的距离，使个体能够在整个　

约束空间中分散开。　

２．２聚焦爬虫研究现状　不同聚焦网络爬虫之问的主要区别之一是如何决定　ＵＲＬ的爬行次序。目前常用的聚焦爬行策略主要有２类Ｌ２Ｉ：　

基于内容评价的搜索策略和基于Ｗｅｂ链接结构的搜索策略。　基于内容评价的搜索策略起源于文本检索中对文本相似度的　评价，主要利用了Ｗｅｂ网页文本内容、ＵＲＬ字符串、锚文字　等文字内容信息，典型的代表是ＢｅｓｔＦｉｒｓｔ算法　Ｊ。该类算法　

的优点是具有较好的理论基础且计算简单。但由于这类方法　

忽略了链接结构信息，因此在预测链接价值的准确性方面存　在一些不足。　以文献【４—５］为代表的基－ｆ　Ｗｅｂ链接结构的搜索策略通过　

分析Ｗｅｂ页面之间的相互引片ｊ关系确定网页的重要性，进而　决定链接访问顺序。其中，ＨＩＴＳ算法通过对网络中链接的分　

析，将相关网页的链接关系作为一个网络拓扑图处理，分析　

Ａｕｔｈｏｒｉｔｙ和Ｈｕｂ　２种页面。Ａｕｔｈｍ‘ｉｔｙ页面的内容具有主题权　

威性，有较强的主题相关度。Ｈｕｂ节点肘主题相关的信息进　行汇总，提供主题及相关主题的信息目录，其本身页面内容　

的相关度不高。通常，好的Ｈｕｂ页是指向许多具有较高的　

Ａｕｔｈｏｒｉｔｙ值的页面；好的Ａｕｔｈｏｒｉｔｙ页是指由许多较高的Ｈｕｂ　值所指向的页面　Ｊ。该方法虽然考虑了链接结构和页面之间　

的引用关系，但忽略了页面与主题的相关性，在某些情况下，　ＨＩＴＳ会出现搜索偏离主题的“主题漂移”问题。　

３基于小生境遗传算法的聚焦爬虫设计　

３　１设计思想　

大量研究结果表明：网络上的信息是按照主题分类的，　

即假如某ｕＲＩ　对应的信息与某主题相关，该ＵＲＬ所在的网　

基金项目：萤庆　教委科学技术研究基金资助项目“网络聚焦爬虫　

研究与设计”（ＫＪ０９　１　３０９）　作者筒介：曾广ｈ￣ｌ，（１９６６－），男，讲师，主研方向：网络信息系统，　

数据挖掘；范会联，副教授、硕士　收稿日期：２００９—１１—１５　Ｅ—ｍａｉｌ：ｆｅｉｙａ～ｃｑ＠ｉ６３．ｃｏｒｎ　

ｌ６７—

　站或目录也可能包含与此土越卡Ｈ关的信息，所以，类似生物　学中的小生境，网页链接一般总是和与自己相类似的内容链　

接在一起。因此，考虑小生境遗传算法的特点并结合基于网　页链接结构的搜索策略和基于内容评价的搜索策略的可取之　

处，本文在聚焦爬虫爬行过程中引入小生境遗传算法引导搜　索过程，将待搜索的网页ＵＲＬ作为遗传个体，采用基于主题　

相关度的适应度函数计算并评估个体适应度，采用概率的变　迁规则和小生境淘汰运算引导它的搜索方向。基于“从优质　

网页链接出去的ＵＲＬ可能还是优质网页”和“链接目标是优　

质网页的ＵＲＬ可能也是优质网页”的原则，从满足主题相关　

度条件的网页中包含的所有链接（即从满足主题相关度条件　

的网页链接出去的ＵＲＬ）中按一定规则抽取新的ＵＲＬ实现交　

叉操作，变异操作则通过从链接目标为满足主题相关度条件　

网页的新ＵＲＬ（即链接目标为满足主题相关度条件网页的　

ＵＲＬ）中选取。最后对完成以上操作后形成的新种群（新的　

ＵＲＬ集合）采用小生境淘汰运算形成下一代进化种群，从而保　证该算法不仅具有较高的局部寻优能力，而且能提高聚焦爬　虫的全局搜索性能。　

３．２主题相关性的判定　本文采用叙词表代替主题词集确立主题，叙词表中用内　

涵相同的一组词表示一个概念，并赋予相同的权值，而不同　

的概念指定不同权值。表示主题的叙词表构造和不同概念权　值的确定在领域专家的协助下结合实际情况和经验采用手工　

设置。　网页的主题相关度采用向量空间模型计算：对用户提问　

所对应的查询表达式或用户预先定义的用于搜索的模板文　件，在领域专家协助下得到检索提问式ｎ维向量　＝　

（ｑ－，ｑ２，…，ｑ　），其中，ｇ，表示第，个查询词在查询表达式中的　

权值。对网页进行中文分词处理，统计主题叙词表中特征词　

在待抓取网页中出现的频率，以出现频率最高的特征词作为　

基准，其频率用１表示，相应求出其他特征词的频率。由于　

网页是一种半结构化的文本，ＨＴＭＬ标记对网页主题的贡献　度不同Ｉ，Ｊ，因此对不同标记修饰的特征词权值表示为Ｘｉ×　ｆ），　其中，Ｘ，为第　个特征词在该网页中出现的频率，设　）代　

表第ｉ个特征词应赋予的权重，本算法对　）的取值定义　

如下：　

ｗ（ｉ）：　５．０＜ｔｉｔｌｅ＞标签修饰　３．０＜ａ＞标签修饰　２．０＜ｍｅｔａ＞标签修饰　１．０其他　

将每一个待抓取网页转化为　维向量　＝　－×　１），　

×　２），…，Ｘｎ￣　ｎ））。这样用户主题和所有网页可以分别映射　

到向量空间口，　上，从而将网页信息与用户需求的匹配问题　

转化为向量空间中的向量匹配问题，则主题相关度的计算公　式为【８１　

Ｓｉｍｉｌａｒｉｔｙ（　，　）：。。　（　，　）：］三！　；．　

√∑吼　×∑ｌ　（ｒ）　

本算法即以主题相关度作为个体适应度函数。　

３．３聚焦爬虫爬行策略　以普通爬虫程序为基础，该搜索策略借助修改选择、交　

叉、变异３个遗传算子和小生境淘汰方法，通过选择操作抓　

取主题相关度网页，通过交叉操作实现深度爬行，通过变异　

操作完成广度爬行，通过小生境淘汰规则过滤同一小生境内　主题相关度较低的网页、避免过早局部收敛，从而优化爬行　

】６８一　路径，保证该搜索策略不仅有较高的查准率，也有较高的查　

全率。具体搜索策略的算法描述如下：　输入初始化种子集合Ｖ、交叉概率Ｐ　、变异概率Ｐ　

小生境淘汰率Ｐ　、主题相关度阂值　输出主题相关度大于Ｓｏ的网页集合ＪＤ和对应的　ｄｏｗｎｌｏａｄｕｒｌ队列　

函数体：　

（１）将集合Ｖ中ＵＲＬ加入待处理队列ｗａｉｔ　ｑｕｅｕｅ中。　

（２）下载待处理队列ｗａｉｔ　中所有　对应的网页，ｑｕｅｕｅ　ＵＲＬ　

相应ＵＲＬ加入已访问队列ｖｉｓｉｔｅｄ　ｑｕｅｕｅ。　

（３）选择操作。计算每个下载成功网页的主题相关度Ｓ，　保存主题相关度大于　的网页，加入集合Ｐ，相应的ＵＲＬ　

加入已下载队列ｄｏｗｎｌｏａｄ　ｕｒｌ。　（４）解析新加入集合Ｐ中的网页，抽取网页中包含的　

ＵＲＬ，对ＵＲＬ进行规范处理后，过滤已下载和重复的ＵＲＬ，　

结果计为　－。分析计算　－中包含的所有ＵＲＬ对应网页各自　

的主题相关度Ｓ，并将结果存入结构为＜ｕｒｌ，　的ｔｅｍｐ　ｈａｓｈＵＲＬ中。　（５）交叉操作。按照主题相关度大小对ｔｅｍｐ　ｈａｓｈＵＲＬ进　

行降序排列后，根据交叉概率Ｐ　从中选出前ｅ个ＵＲＬ作为　

交叉结果集合，记为　，其中，　ｔｅｍｐｈａｓｈＵＲＬ￣ｐ　。　

（６）采集链接目标为　中网页的ＵＲＬ，过滤重复和已爬　行的ＵＲＬ后，结果集记为　。　

（７）变异操作。按照变异概率Ｐ　从　中提取出ｍ个ＵＲＬ　记为集合　，其中，　＝　ｘ　。　

（８）记　＝　Ｕ　。　（９）对　进行小生境淘汰运算，结果加入ｗａｉｔ　。ｑｕｅｕｅ　（１０）清空ｔｅｍｐ　ｈａｓｈＵＲＬ和集合Ｖｌ，ｖ２，　，　，　。　

（１　１）终止条件判断。根据检查ｗａｉｔ　ｑｕｅｕｅ是否为空或已　下载的页面数是否超过用户设定的阈值，或者遗传代数是否　

超过阈值决定是否结束爬行。　

初始化种子集合　的定义：聚焦搜索的初始条件是给定　

与主题对应的检索提问式。将检索提问式提交给通用的搜索　

引擎（如ＷＷＷ．ｇｏｏｇｌｅ．ｃｏｒｎ或ｗｗｗ．ｂａｉｄｕ．ｃｏｒｎ）获得可能相关的　

ＵＲＬ，除去重复的ＵＲＬ，选取前　条记录作为初始化种子集　

合，也可在领域专家的指导下人工筛选出与主题相关的ＵＲＬ　

作为种子集合　ｊ。　

选择操作定义：与遗传算法的目标是找到最优解不同，　聚焦爬虫是要找到所有主题相关度大于预设阈值的网页，因　此，在完成每一代进化后，所有主题相关度大于预设阈值的　

网页都是满足目标要求的，应予以保存。　交叉操作定义：基于“从优质网页链接出去的网页可能　

还足优质网页”的原则（此处的优质网页定义为满足用户查询　条件要求的网页），抽取选择操作步骤中新保存网页中包含的　

ＵＲＬ，过滤网页中版权声明栏和广告信息栏、书签等可能与　

主题无关的链接，剔除已爬行和重复的ＵＲＬ后，按照主题相　

关度大小进行降序排列，选出前ｃ个ＵＲＬ作为交叉结果集合。　变异操作定义：变异操作的目标是扩大相关网页搜索范　

围。基于“链接目标是优质网页的ＵＲＬ可能也是优质网页”　

的原则，搜索采集链接目标为经过选择、交叉后得到网页的　新ＵＲＬ，经过剔除重复及已爬行的ＵＲＬ后，按照变异概率　

Ｐ　提取ｍ个ＵＲＬ作为变异操作结果集。　

小生境淘汰规则定义：根据ＵＲＬ的结构（ｈｔｔｐ：／／＜ｈｏｓｔ＞：　

＜ｐｏｒｔ＞／＜ｐａｔｈ＞）

特点，该算法中将小生境定义为具有相同主机