基于Wang−Landau抽样的主题爬虫方法.pdf
《基于Wang−Landau抽样的主题爬虫方法.pdf》由会员分享,可在线阅读,更多相关《基于Wang−Landau抽样的主题爬虫方法.pdf(10页珍藏版)》请在咨信网上搜索。
1、基于 WangLandau 抽样的主题爬虫方法刘景发1,陈靖岚1,赵鹏2*(1.广东外语外贸大学信息科学与技术学院广州510006;2.南京信息工程大学计算机与软件学院南京210044)【摘要】针对传统爬虫方法存在搜索易陷入局部最优,且很少考虑结合历史爬行经验对爬行路径进行修正的缺陷,提出一种基于 WL 抽样的主题爬行方法。该方法分别使用向量空间模型(VSM)和 PageRank 算法对链接的相关性和重要性进行评价,采用区域竞争策略从具有主题相关或潜在价值的链接集合中选出目标链接。基于概率密度函数,WL 抽样算法对侯选集中选出的目标链接进行抽样判断,根据历史统计经验指导爬虫的后续爬行,从而优化
2、搜索路径。实验结果表明,提出的基于 WL 抽样的主题爬虫方法比其他主题爬虫方法能搜索到更多主题相关的网页,其爬准率和所有下载网页主题相关度的标准差具有明显优势。关键词网络爬虫;信息检索;暴雨灾害;台风灾害;Wang-Landau 抽样中图分类号TP391文献标志码Adoi:10.12178/1001-0548.2022183FocusedCrawlerMethodBasedonWangLandauSamplingLIUJingfa1,CHENJinglan1,andZHAOPeng2*(1.SchoolofInformationScience&Technology,GuangdongUnive
3、rsityofForeignStudiesGuangzhou510006;2.SchoolofComputer&Software,NanjingUniversityofInformationScience&TechnologyNanjing210044)AbstractAimingattheproblemthatthetraditionalcrawlermethodsareeasytofallintolocaloptimaofthesearchandrarelyconsidermodifyingthecrawlingpathbasedonhistoricalcrawlingexperience
4、,afocusedcrawlermethodbasedonWangLandau(WL)samplingisproposed.Thismethodusesthevectorspacemodel(VSM)andPageRankalgorithmtoevaluatetherelevanceandimportanceoflinks,respectively.Regionalcompetitionstrategyisusedtoselectthetargetlinkfromthelinksetcontainingthetopicrelatedlinksandlinkswithpotentialvalue
5、.Basedonprobabilitydensityfunction,theWLalgorithmisusedtosampletheselectedtargetlinksintheset,andguidesthesubsequentcrawlingofthecrawleraccordingtothehistoricalstatisticalexperience,soastooptimizethesearchpath.TheexperimentalresultsshowthattheWL-basedfocusedcrawlingmethodcansearchmoretopic-relevantw
6、ebpagesthanothermethodsintheliterature,andtheclimbingaccuracyandstandarddeviationoftopicrelevanceofalldownloadedpagesarealsosignificantlyimproved.Key words focused crawler;information retrieval;rainstorm disaster;typhoon disaster;Wang-Landausampling当今,有效信息变得越来越重要,而网络爬虫正是穿梭于互联网中帮助人们自动获取信息的一把利器。据中国互联网
7、络信息中心第 49 次调查报告显示1,截至 2021 年 12 月,仅中国网页的数量就已经达到 3350 亿个,全球互联网的网页数量更是难以估计,这使得传统搜索引擎很难满足特定用户的需求。因此,如何利用主题爬虫2抓取特定领域的数据,从而为特定人群提供个性化推荐已经成为许多学者研究的热点。主题爬虫是一种旨在搜集某一领域数据的网络爬虫,它将使用某种策略和网页分析算法来降低传统网络爬虫因大量网页遍历而带来的代价,从而更有效地获取主题相关的信息。目前,主题爬虫的研究主要集中在链接的评价和搜索策略上。链接评价是指对链接相关性和重要性的评价。链接评价方法主要有基于网页内容分析的方法和基于链接结构分析的方法
8、。前者的代表主要有 FishSearch3和 SharkSearch4;后者的代表主要有 PageRank 算法5与收稿日期:20220613;修回日期:20230130基金项目:广东省基础与应用基础研究(2021A1515011974,2023A1515011344)作者简介:刘景发(1972),男,教授,博士,主要从事信息检索、计算智能、多目标优化等方面的研究.*通信作者:赵鹏,E-mail:zhaopeng_第52卷第4期电子科技大学学报Vol.52No.42023 年 7 月JournalofUniversityofElectronicScienceandTechnologyofChi
9、naJul.2023HITS(hyperlinkinducedtopicsearch)6算法。由于基于网页内容分析的主题爬虫方法仅考虑网页、锚文本等文本信息,缺乏对网页链接结构的考虑,所以容易导致爬虫陷入局部最优。基于链接结构分析的主题爬虫应用较为广泛,近年来一些学者进行了深入研究。文献 7 通过在 SharkSearch 算法的基础上引入相关链接块的概念来解决链接的锚文本较为短小、不能准确表明链接指向主题相关性的缺陷。文献 8 以主机目标网站中若干相同目录路径中的页面聚合相关性作为领域相关性特征,提出一种拥有“领域功能”的主题爬虫方法。但该类方法由于未考虑链接的主题相关性,所以爬虫容易产生主
10、题漂移现象6。鉴于此,一些学者尝试综合这两类方法来提高链接评价的准确性9。另外,搜索策略决定不同价值链接被访问的次序。传统的纯粹基于链接相关性高低的爬行策略难以使爬虫通过具有潜在价值的链接进行网页有效搜索。为提升主题爬虫的隧道穿越能力10,引导主题爬虫以最小的代价从相关度低的区域跳转到相关度高的区域,文献 11-14 采用智能优化方法来改进爬虫的全局寻优能力。文献 11 为提取和揭示网络犯罪,使用基于蚁群优化的主题爬虫,为 Web 犯罪挖掘开发一种基于本体的优化方法。文献 12 将多目标优化算法引入主题爬虫,提出了一种基于网页空间进化(WSE)算法的主题爬虫方法。文献 13 进一步将 WSE
11、算法和领域本体相结合,提出了一种新的 基 于 WSE 的 主 题 爬 虫 算 法(focused crawlercombining Web space evolution and ontology,FCWSEO)。在该算法中,通过构建领域本体建立主题模型,使用一种最近最远候选解法挑选Pareto 最优链接。文献 14 为克服人工构建本体过程中构建者知识储备和主观意识的限制,提出了一种结合潜狄利克雷分布和 Apriori 算法的领域本体半自动构建方法。他们基于链接评估的多目标优化模型和改进的多目标蚁群优化算法来指导爬虫的搜索方向。文献 15 通过加入时间因子,动态调节适应度函数和遗传算子,在一定
12、程度上避免了爬虫陷入循环爬行的陷阱。文献 16 结合爬虫记忆历史主机信息和模拟退火算法设计了暴雨灾害主题爬虫。文献 17 应用多目标蚁群算法来选择主题爬虫过程中的 Pareto 最优链接,进而引导爬虫搜索更多主题相关的页面。本质上,基于智能优化算法的主题爬虫以一定规则或概率接收主题相关度低的页面,具有全局优化的优点。但上述算法在链接搜索次序选择上缺乏对已爬取网页的统计,导致历史经验难以指导后续的网页搜索。特别是当爬虫距离主题相关页面较远时,常常出现主题偏移现象。针对上述问题,本文提出一种基于 Wang-Landau(WL)抽样的主题爬虫方法。该方法采用一组带有语义权重的向量来描述主题,并使用向
13、量空间模型(vectorspacemodel,VSM)18分别计算链接对应的锚文本和链接指向网页文本的主题相关度;再利用 PageRank 算法从链接结构角度评价链接的重要性,进而选定具有潜在价值的链接。基于WL 算法,将能量状态密度函数和直方图函数应用于主题爬行策略,通过统计状态密度的变化,决定主题爬虫是否接受目标链接,进而指导爬虫寻找一条合适的主题爬行路径。此外,为防止爬虫接受无关链接而导致主题搜索方向偏移,引入区域竞争策略挑选目标链接,以获得更好的爬行效果。1网页主题相关度和重要性计算在主题爬虫过程中,本文综合考虑链接指向网页的主题相关度和链接锚文本主题相关度,并根据链接所在页面的重要性
14、选择具有潜在价值的页面。1.1网页主题相关度的计算在主题爬虫中,一般采用一组特定术语组成的主题词向量 TK 来描述用户选定的特定主题,假设 TK 定义如下:TK=tk1,tk2,tkn(1)式中,tki(i=1,2,n)表示第 i 个主题词;n 为主题词集 TK 中元素的个数。本文以暴雨灾害和台风灾害为主题,根据领域专家经验和多次对比实验,设置描述暴雨灾害的主题词组分别为暴雨、气象、天气、灾害和预防,描述台风灾害的主题词组分别为台风、风暴潮、暴雨、气压和风力。令 wtki为主题词 tki的权重,其值主要基于特征提取的主题词权重计算方法和领域专家结合经验设定12。在主题词向量确定以后,为计算网页
15、主题相关度,需要确定网页文本特征向量。本文采用 IK-Analyzer 对网页文本进行分词、去停用词等预处理。将处理之后的网页文本 Pj用向量 DKj表示:DKj=dkj,1,dkj,2,dkj,i,dkj,n(2)式中,dkj,i表示网页文本 Pj中的第 i 个特征词。对于文本中的某个特征词,它的权重采用词频逆文档频率(termfrequencyinversedocumentfrequency,TF-IDF)19方法计算:第 4 期刘景发,等:基于 WangLandau 抽样的主题爬虫方法579wdkj,i=nj,iknj,klgD1+Di(3)式中,nj,i表示在网页文本 Pj中第 i 个
16、特征词出现的次数;分母表示文本 Pj中所有特征词出现的次数之和;D 为当前爬取网页文本总数;Di为包含第 i 个特征词的网页文本数。某个词的权重越大,说明该词越能代表文档的特征。当词权重为 0 时,说明该词不出现于该网页。对于链接 l 所在网页 Pl,本文采用 VSM 计算主题向量 TK 和网页文本特征向量 DKl的主题相关度 R(Pl):R(Pl)=sim(TK,DKl)=cos=ni=1wtkiwdkl,ivtni=1w2tkini=1w2dkl,i(4)WDKl式中,WTK为用户所指定主题词的权重向量;为网页文本 Pl(或锚文本)的特征权重向量。本文由式(4)分别计算待访问链接 l 所指
17、向网页的主题相关度和其锚文本的主题相关度,再进行线性加权求和得到链接 l 的综合主题相关度:R(l)=R(anchorl)+(1)R(Pl)(5)式 中,R(l)表 示 链 接 l 的 综 合 主 题 相 关 度;R(anchorl)和 R(Pl)分别为链接 l 的锚文本 anchorl和链接 l 指向网页 Pl的主题相关度;为权重系数。由于基于网页文本内容和链接结构分析的主题爬虫方法在各自单独使用时其爬准率往往受限,因此通常相互结合使用,实现互补,进而提高爬虫抓取网页的准确率。此外,上述策略在计算链接优先度后,大多采取最佳优先机制进行网页抓取,该贪心策略往往容易使爬虫陷入局部最优。1.2网页
18、重要性计算从有潜在价值的网页出发,抓取更多主题相关页面,还可以从重要性的角度综合评价网页。一般地,网页的重要性主要由网页链接关系来衡量,本文 采 用 PageRank 算 法 来 计 算 网 页 的 重 要 性。PageRank 算法的思想是通过网页的引用关系来判断网页是否重要,即若某网页被其他网页引用次数越多,就认为该网页越重要,而当某网页被这些重要的网页引用时,该网页也被认为是重要的。本文采用的 PageRank 计算公式为:PR(Pj)=(1)+PiBjPR(Pi)|Ci|(6)式中,PR(Pj)代表网页 Pj的 PR 值;Bj为网页 Pj的所有入链页面集;Ci为 Pj的入链页面 Pi的
19、出链集合;=0.85 为跳转因子,主要用于表示 Web 用户有多大概率通过其他网页的出链来访问当前页面,1 表示用户通过键入 URL 等方式来直接访问该网页的概率。通过式(6)可给网页赋予一个重要性的量化值。本文将从主题相关度较低的网页中选取重要性值 PR2 的网页作为具有潜在价值的网页,这些网页将有机会在爬行过程中被选中,从而辅助爬虫跳出局部最优,以搜寻更多主题相关的页面。2基于 WangLandau 抽样的主题爬虫方法传统主题爬虫多采用按主题相关度从高到低依次选择链接进行网页抓取。然而,并不是所有的相关页面都聚集在一起,当爬虫始终都抓取相关度高的网页时,容易陷入搜索的局部最优。因此,为实现
20、全局寻优,结合网页主题相关性和重要性评价指标,提出基于 WangLandau 抽样的主题爬虫过程。2.1WangLandau 抽样算法的基本思想基于频率直方图的 WangLandau(WL)抽样算法20是一种蒙特卡洛(MonteCarlo,MC)算法,其理论基础是:状态 X 被访问的概率与其能量状态密度 g(E(X)的倒数成正比,其中 E(X)表示状态空间中状态 X 的能量。传统的 MC 方法局限于在温度不变的前提下产生正则分布,因此,想获得高质量的解,算法就必须在不同温度条件下多次运行。如模拟退火算法就需要不断地进行退火操作,十分耗时。WangLandau 抽样算法与温度无关,这使得它可以按
21、照一定的概率接受准则漫步于状态空间,进而获取一个平坦的能量直方图 H(X)并得到概率密度函数 g(E(X),即 WL 抽样算法可从系统中的某个状态出发,逐步统计各个状态的能量,进而发掘整个系统中各个状态能量的分布规律。这与主题爬虫面临的问题场景类似,在网页空间中,各主题相关页面(对应状态空间中的状态)分布未知,人们无法通过互联网的结构去直接设计网页抓取策略。因此,本文将整个互联网中的 Web 资源看成是系统的状态空间 S,主题相关页面分布于 S中。为了在这个系统中搜寻到更多的主题相关页面,在580电子科技大学学报第52卷计算各链接的主题相关度后,通过将上文给出的链接主题相关度 R(l)和状态(
22、链接)的能量 E(l)相对应,设计基于 WL 抽样算法的主题搜索策略,即WL 抽样算法基于状态密度函数行走于网页空间,并根据历史经验的积累实现对低状态密度函数值链接的有效抽样。2.2基于 WL 抽样的主题爬虫方法实现E(X)E(X)E(X)E(X)fi在 WL 抽样算法的开始,网页空间中所有链接 X 及其状态密度函数 g(E(X)均是未知的。每当访问到一个新的链接 X,这个链接的状态密度函数g(E(X)及直方图函数 H(E(X)就被置为 1。由于本文计算的能量值为链接的主题相关度,所以能量值介于 01 之间。不妨将其划分为 50 个能量区间,每 个 能 量 区 间 间 隔 为 0.02,即 0
23、,0.02),0.02,0.04),0.98,1。为 便 于 描 述,将 能 量 区 间,)标记为 E(X),其中是 E(X)所属能量区间的下边界,是 E(X)所属能量区间的上边界,X 为网页空间中某一链接。如E(X)=0.621 处于能量区间 0.62,0.64)中,记为0.621。将 WangLandau 抽样算法应用于主题爬虫,其基本思路如下:首先,从种子链接等待队列中选择一个初始链接 X1,然后采用区域竞争策略(见 2.3 节)产生目标链接 X2,再根据 P(X1X2)=min(g(E(X1)/g(E(X2),1)=min(elng(E1)g(E2),1)的值来判断X2是否接受,这里
24、E1和 E2分别表示 X1和 X2的综合 主 题 相 关 度,即 E1=E(X1),E2=E(X2)。如 果X2被接受,则修改 X2的状态密度函数 g(E(X2):令g(E(X2)=fig(E(X2),其中,fi1 为一个罚因子,同时修改其直方图函数:令 H(E(X2)=H(E(X2)+1;如果链接 X2不被接受,则类似修改 X1的状态密度函数和直方图函数值。另外,算法的收敛速度由直方图的平坦度控制,而所谓平坦的直方图是指所有 H(E(X)的值均不小于直方图的平均值H(E(X)的 k(0k106,则提前结束爬虫搜索;否则,将所有访问过的能量区间 E(X)所对应的 H(E(X)置为零,g(E(X
25、)值保留,开始下一次随机行走。此时,g(E(X)将以某一精度收敛于真实值。因实际计算中 g(E(X)的值会变得很大,以至超出双精度数字所能表示的范围,故选用对数式 lng(E(Xi)=ln(fi)+lng(E(Xi)进行更新,这里 i 为 1 或 2。基于WL 抽样的主题爬虫算法伪代码见算法 1。算法 1基于 WL 抽样的主题爬虫算法输入:种子链接输出:下载的网页1)将种子链接加入等待队列 Queue,初始化参数 i=0,f0=e,L=0,S=;令 T=1000,DP=0,LP=0;/DP 表示下载网页数,LP 表示下载相关网页数;2)从 Queue 中取出综合主题相关度最高的队头链接 X1作
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 Wang Landau 抽样 主题 爬虫 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。