总第231期
2009年第1期
计算机与数字工程
Computer&DigitalEngineeringVol.37No.1
22
基于内容和链接分析的主题爬虫策略
刘 朋 林 泓 高德威
(武汉理工大学计算机科学与技术学院 武汉 430063)
3
摘 要 在分析目前常用的主题爬行策略的基础之上,根据PageRank算法的思想,结合基于文本内容的启发式策略和基于Web超链分析的策略二者之间的优点,提出了一种新的爬行策略,并实现了一个主题爬虫。通过与传统策略的对比,可以得出该策略既可以利用链接分析扩大某个主题的资源覆盖度,又可以保证搜索结果与主题的高度相关。
关键词 主题爬虫 爬行策略 Web挖掘 论文评估中图分类号 TP393
ResearchonCrawlingStrategyofSubjectSearching
SpiderbyContent2BasedandHyperlink2BasedAnalysis
LiuPeng LinHong GaoDewei
(SchoolofComputerScienceandTechnology,WuhanUniversityofTechnology,Wuhan 430063)
Abstract Based
onanalyzingtherecentcrawlingstrategiesofsubjectingsearchingincommonuseandthethinking
inPageRankarithmetic,anewcrawlingstrategywasproposedthathavethemeritsofthetwooftheenlighteningstrategybasedoncontentandthestrategybasedonhyperlinkanalysis.Arealizationschemeofthetopiccrawlerisalsoprovided.Itwaspossibletoenlargetheresourcedegreeofcoveragethroughhypterlinkanalyzingaswellastoensurethesearchingresultshighcorrelatetothesubject.
Keywords topic2focusedcrawler,crawlingstrategy,Webmining,evaluatingpaperClassNumber TP393
1 引言
随着互联网络中信息的爆炸式增长,传统的搜索引擎已经不能满足人们对个性化信息检索服务日益增长的需要。建立面向特定专业领域的主题搜索引擎已经成为搜索引擎新的发展趋势[1]。于是,适应特定主题和个性化搜索引擎的主题网络爬虫便应运而生。
在主题搜索引擎中,网络爬虫以何种搜索策略访问Web以提高效率,是近年来主题搜索引擎研究中的热点问题之一[2],而且由于Web的动态性、异构性和复杂性,就会要求网络爬虫能够高效率地实现Web信息提取,以保证信息的实时性。
2 网络爬虫
网络爬虫是搜索引擎中的核心组成部分,发挥着举足轻重的作用。随着应用的发展和深入,网络爬虫被广泛地应用于多种服务中去,比如站点的结构分析,页面有效性分析以及个性化的信息提取等等。
所谓的主题网络爬虫就是根据一定的网页分析算法过滤与主题无关的链接,保留主题相关的链接并将其放入待抓取的URL队列中;然后根据一定的搜索策略从队列中选择下一步要抓取的网页URL,并重复上述过程,直到达到系统的某一条件
时停止。
3
收稿日期:2008年8月18日,修回日期:2008年9月23日
作者简介:刘朋,男,硕士研究生,研究方向:网络和数据库技术、数据挖掘。林泓,女,硕士,副教授,研究方向:网络数据库技术、数据挖掘。高德威,男,硕士研究生,研究方向:信息挖掘,嵌入式数据库技术。
第37卷(2009)第1期计算机与数字工程 23
3 主题爬行策略
目前常用的主题爬行策略主要有两大类[3]:基于文本内容的启发式策略和基于Web超链评价的策略。基于内容评价的策略以DeBra、Herseovici等人的研究Fish及Shark[4]为代表,其优点是具有较好的理论基础,而且计算比较简单,但是这类方法忽略了链接结构信息,在预测链接价值的准确性方面存在不足。而以PageRank为代表的基于Web链接结构的搜索策略,则通过分析Web页面之间的相互引用来决定网页的重要性,从而决定链接的访问顺序,但是这类方法只考虑了页面之间的引用关系,忽略了页面的主题相关性而且计算量相当大,严重影响了爬虫的爬行速度,因此不适合发现主题资源。但是根据PageRank算法的思想,我们可以联想到怎样评价一篇已经公开发表的论文的影响程度。在科技论文评估体系中广泛采用的方法是统计该论文的被引用的次数,一篇被引用多次的文献在一般情况下比被引用次数少的文献的重要性要高,所以可以将此思想用于评价一个网页的重要性。结合这两种策略的优缺点本文提出了一种基于内容和链接分析的主题爬虫爬行策略,该策略首先利用基于文本内容的启发式策略来选择和预测与主题相似的URL,然后在待爬行的URL队列中,基于内容评价
的网页所指向的超链接数,取消了原有算法中的爬行深度,改为由管理员进行控制。
改进后的Shark启发式算法仍然采用向量空间模型来计算页面与主题关键词向量keysVector
(在专家的参与下建立的能代表特定主题文本内容的一个基准向量)的相关度。计算公式如下: sim
n
(p,
ij
k)=cos
(_p,
_)
k
=
i=1n
∑w
2
3wiq
n
i=1∑wij3
i=1
∑wiq2
其中页面内容向量_p=(w1q,w2q,…,wnq),主题关键词向量_k-(w1j,w2j,…,wnj)。
根据相关度的计算公式我们可以决定一个网页的子网页的URL所属的队列:如果一个页面的主题相关度大于upperLimit该页面的子页面的URL应进入priorQueue。如果一个页面的主题相
关度介于upperLimit和lowerLimit之间,则应该根据子页面的锚文字或者是URL字符串是否包含keysVector中的关键词来判断是否属于pri2orQueue队列。如果满足二者中的一个,则应进入priorQueue队列。如果上述条件都不满足,则由子
节点的预测相关度来决定队列的类型。3.3 新策略中的超链分析
和基于链接分析相结合,来决定待爬行URL的优先级。这样不但可以提高搜索内容与主题的相关度,而且又可以提高主题资源搜索的覆盖率,综合了上文所述爬行策略的优点。3.1 新策略的核心思想
按网页超链接信息来评价网页的重要程度。如果一个网页被其他多个网页所链接,它显然要比很少被链接的网页重要。用网页的超链接信息指导爬行器的爬行方向就避免了爬行的盲目性。在此,可以将网页看作为一个节点,那么一个网页的子网页就是该网页的一个子节点。
给定一个网页P,定义指向网页P的超链接数HyperLinks(P)为Web空间上所有指向网页P的超链接数,在具体实现上,不可能去计算Web空间上所有指向网页P的超链接数,所以用已爬行过的网页去计算指向网页P的超链接数。
新策略是在改进的Shark启发式搜索算法的基础之上,根据被爬行过的网页信息和网页超链接信息来计算待爬行的网页队列中的每个URL被已爬行过的网页所指向的超链接数,爬行器优先选取具有高的超链接数的URL访问。3.2 Shark启发式算法的改进
将Shark算法中的一个待爬行URL队列改为2个待爬行队列,分别是priorQueue(待爬行的相关度高的URL队列)和normalQueue(普通队列)。
增加3种阈值:页面内容相关度阈值的上限值upperLimit和下限值lowerLimit;节点预测相关度
阈值minPrior(priorQueue的最低预测相关度值)和minNormal(normalQueue的最低预测相关度值);锚文本的相关度阈值anchoThreshold。
为了下载更多的相关页面和计算被已爬行过
图1 网页构成的有向图
在图1中已经爬行过的网页集合中有3条指向网页P7的链接和1条指向网页P8的链接,因
24刘 朋等:基于内容和链接分析的主题爬虫策略
=1,否则simContext(childURL)=sim(anchorContext,keysVector);3)计算子节点的遗传相关度:inherited(childURL)=ξ×sim(currentContent,keysVector);4)子节点的预测相关度:
potentialScore(childURL)=β×)× inherited(childURL)+(1-β
第37卷
此网络爬虫应该优先访问网页P7。3.4 新策略的实现方案
通过以上对改进的Shark算法和超链的分析和研究,可以得到基于内容和链接分析的主题爬虫爬行策略需要5个队列:priorQueue,normalQueue,crawledQueue,errorQueue,linksQueue。这5个队列
分别用于存储:待爬行优先级较高的URL;待爬行的普通的URL;已经下载了的URL;预测相关度低于minNormal或者出错的URL;网页之间的链接关系用linksQueue存储,用来计算以爬行网页的链接数。
simContext(childURL);
5)综合值value的计算方法
value=θ×potentialScore(childURL))×HyperLinks(childURL)/N +(1-θ
该策略的关键是如何决定一个节点的子节点的归属队列,其实现方法如上文所述。根据队列的选择算法,就可以得到基于内容和链接分析的主题爬虫爬行的爬行策略: Content2BasedandHyperlink2BasedCrawlingAlgorithm
(){
其中ξ:为遗传衰减度系数β,θ,是调和系数,三个系数的取值都不能超过1。4 试验
基于上述策略和算法的思想开发了一个主题爬虫进行实验。实验是对同一个主题,把通用搜索引擎,基于Shark搜索策略的搜索引擎和本论文设计的主题爬行器搜索到的数据进行对
β=θ=0.85。图2是比。实验参数为:ξ=0.6,对比的结果。
//初始化操作,获得相关参数将已经爬行//的网页队列设置为空
initial();
makeEmpty(crawledQueue);
//将种子URLs加入到priorQueue,因//为种子站点
是由专家选定所以//具有高的优先级
addQueue(priorQueue,seedURLs);if(没有满足某种终止条件){
while(priorQueue.notEmpty|| normalQueue.notEmpty){ URL=priorQueue.getURL(); choosingQueue(URL); URL=normalQueue.getURL(); choosingQueue(URL);
//根据linksQueue来计算待爬行//的URL被以爬行
图2 实验结果对比
上面的分析数据表明,新的主题爬行策略在查询特定主题信息方面与传统的爬行技术相比有着明显的优势,随着网页数量规模的不断增长,新的策略在总体水平上存在着优势。在本策略的实现中还发现,不同的初始种子集合可能导致不同的爬行结果。因此,一个优良种子集的选取也很重要,它可以使系统更快地找到与主题相关的网页,减少盲目爬行过程,提高搜索精度。算法中各种参数和阈值的正确选择对爬行结果也有着重要的影响,如何取值有待于进一步深入研究。
的网页所指的连接数//和每个子节点的预测相关度结合起//来获得value,来重新排列//priorQueue和nor2
malQueue
foreachurlinpriorQueueandnormalQueue
calcutlateValue(url,crawledQueue,
linksQueue,potentialScore); reorderQueue(priorQueue); reorderQueue(normalQueue); }}}
注:
算法中每个子节点的预测相关度计算方法:
1)计算锚文字相关度:simAnchor(childURL)=sim(anchorText,keysVector);
2)计算锚文字上下文内容的相关度:如果simAnchor(childURL)的值大于上文定义的
anchorThreshold则simContext(childURL)
5 结语
本文提出了一种新的基于内容和链接分析的主题爬虫爬行策略,综合考虑了网页内容和网页之间的链接关系对待爬行的URL队列优先级顺序
(下转第80页)的影响,具有较大的应用价值。
80管昌生等:基于角色的动态工作流技术的研究第37卷
2.6.2 动态演化算法
经过对工作流迁移时可能遇到的情况进行分析,可以采用如下动态演化算法,以判定更改后的工作流模型是否能够继续有效的执行,该算法只考虑节点的改变情况,具体的算法步骤如下[8]:
执行有向图匹配算法,查看新旧有向图是否完全匹配;
If拓扑有序序列完全匹配Then
无需任何操作,继续执行;//工作流流程没有修改 Else
Case:增加新的节点
If该节点还未执行Then继续执行;
ElseIf选择回退Then回退到该节点之前重新执行;
Else继续执行;//不选择回退 EndIf EndIf EndCase Case:删除节点
If该节点是挂起时的当前节点Then报错;EndIf If该节点还未执行Then继续执行;
ElseIf选择回退Then回退到该节点之前重新执行;
Else继续执行;//不选择回退 EndIf EndIf EndCase Case:修改节点
If该节点是挂起时的当前节点Then重新执行该节点;EndIf
If该节点还未执行Then继续执行;
ElseIf选择回退Then回退到该节点之前重新执行; Else继续执行;//不选择回退 EndIf EndIf EndCase EndIf
3 结语
本文所讨论的动态工作流模型是以角色为中心的,但除了角色以外,可以实现工作流动态性的支撑技术还有很多,如面向对象技术、分布计算技术、组件技术、协同工作技术、协调理论和专家系统、智能体Agent技术等,这些技术都对工作流系统的发展起着关键性的作用。所以,在今后的研究工作中,将结合上述这些技术来进一步完善文中所研究的基于角色的动态工作流,使其能更好地应用于实际的工作流管理系统中。参考文献
[1]GeorgakopoulosD,HornickM.AnOverviewofWorkflowManagement:FromProcessModelingtoWork2flowAutomationInfrastructure[J].Distributedandparalleldatabases,1995,3(2):119～153
[2]KeithThomasPhalp,PeterHenderson,RobertJohnWalters,etal.RolEnact:role2basedenactablemod2elsofbusinessprocesses[J].InformationandSoftwareTechnology,1998,(40):123～133
[3]AbrahamBernstein.Howcancooperativeworktoolssupportdynamicgroupprocess?Bridgingthespecific2ityfrontier.the2000ACMconferenceonComputersup2portedcooperativework[C].Philadelphia,Pennsylvania,U2nitedStates,2000:279～288
[4]范玉顺.工作流管理技术基础[M].北京:清华大学
出版社,2001
[5]鲍震宁.范玉顺.企业组织模型结构和建模方法研
究[J].北京:计算机工程与应用,2001,23:67～70
[6]付云虹.方俊.基于角色的动态三维组织结构模型[J].长沙:计算技术与自动化,2006,25(2):91～93
[7]李伟平.范玉顺.工作流技术在ERP系统中的应用[J].北京:高技术通讯,2004,(8):56～61
[8]刘道斌.白硕.基于工作流状态的动态访问控制[J].北京:计算机研究与发展,2003,40(3):417～421
(上接第24页)
参考文献
[1]山岚,赵英,徐耀等.专业搜索引擎系统的设计与
[J].计算机工程,2004,(7):32～33
[4]MichaelHerseovici,MichalJacov,YoelleSMaarek.
TheShark2SearchAlgorithm2AnApplication:
TailoredWebSiteMapping[J].ComputerNetworksand
ISDNSystems,1998,(30):317～326
[5]孙建军,张厚生.网络信息资源搜集与利用[M].
实现[J].微计算机信息,2007,2-3:180～181
[2]林彤,江志军.Internet的搜索引擎[J].计算机工程与应用,2000,36(15):160～163
[3]欧阳柳波,李学勇.专业搜索引擎搜索策略综述
南京:东南大学出版社:80～120
