留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于Wang−Landau抽样的主题爬虫方法

刘景发 陈靖岚 赵鹏

刘景发, 陈靖岚, 赵鹏. 基于Wang−Landau抽样的主题爬虫方法[J]. 电子科技大学学报, 2023, 52(4): 578-587. doi: 10.12178/1001-0548.2022183
引用本文: 刘景发, 陈靖岚, 赵鹏. 基于Wang−Landau抽样的主题爬虫方法[J]. 电子科技大学学报, 2023, 52(4): 578-587. doi: 10.12178/1001-0548.2022183
LIU Jingfa, CHEN Jinglan, ZHAO Peng. Focused Crawler Method Based on Wang−Landau Sampling[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(4): 578-587. doi: 10.12178/1001-0548.2022183
Citation: LIU Jingfa, CHEN Jinglan, ZHAO Peng. Focused Crawler Method Based on Wang−Landau Sampling[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(4): 578-587. doi: 10.12178/1001-0548.2022183

基于Wang−Landau抽样的主题爬虫方法

doi: 10.12178/1001-0548.2022183
基金项目: 广东省基础与应用基础研究(2021A1515011974, 2023A1515011344)
详细信息
    作者简介:

    刘景发(1972 – ),男,教授,博士,主要从事信息检索、计算智能、多目标优化等方面的研究

    通讯作者: 赵鹏,E-mail:zhaopeng_159@163.com
  • 中图分类号: TP391

Focused Crawler Method Based on Wang−Landau Sampling

  • 摘要: 针对传统爬虫方法存在搜索易陷入局部最优,且很少考虑结合历史爬行经验对爬行路径进行修正的缺陷,提出一种基于WL抽样的主题爬行方法。该方法分别使用向量空间模型(VSM)和PageRank算法对链接的相关性和重要性进行评价,采用区域竞争策略从具有主题相关或潜在价值的链接集合中选出目标链接。基于概率密度函数,WL抽样算法对侯选集中选出的目标链接进行抽样判断,根据历史统计经验指导爬虫的后续爬行,从而优化搜索路径。实验结果表明,提出的基于WL抽样的主题爬虫方法比其他主题爬虫方法能搜索到更多主题相关的网页,其爬准率和所有下载网页主题相关度的标准差具有明显优势。
  • 表  1  β=0.62时,暴雨灾害主题下各种主题爬虫算法在不同爬行阶段的实验结果比较

    DP算法AccuracyLPARDPSDDPARLPSDLPTime/h
    1000BFS0.32003200.49770.22900.75510.0780
    OPS0.82308230.71430.15750.77220.0642
    FCSA-host0.70107010.67200.15090.74920.0478
    MOACO0.62916290.69570.2810
    FCWSEO0.45424540.71090.1643
    WL0.85208520.66130.07160.68270.0835
    5000BFS0.269013450.43630.23780.74210.0572
    OPS0.770438520.68020.16100.74940.0586
    FCSA-host0.803040150.69530.11990.74220.0452
    MOACO0.704235210.78010.1865
    FCWSEO0.657232860.75900.1767
    WL0.779638980.67790.09290.67910.0802
    10000BFS0.134513450.29660.22260.74210.0572
    OPS0.653365330.62690.21750.75890.0622
    FCSA-host0.762876280.70040.13710.76400.0595
    MOACO0.787278720.77560.1537
    FCWSEO0.807080700.79040.1612
    WL0.850485040.67490.08210.68620.0774
    15000BFS0.202930430.37050.24380.74710.06378.6
    OPS0.610791600.61690.23390.76500.06339.0
    FCSA-host0.7499112480.70030.14710.77120.066511.8
    MOACO0.7912118680.77800.137715.8
    FCWSEO0.8322124830.82010.155812.2
    WL0.8828132420.69170.07840.71220.0820 8.1
    下载: 导出CSV

    表  2  β=0.62时,暴雨灾害主题下各种主题爬虫算法的Friedman ranks比较

    算法 Accuracy LP ARDP SDDP Average
    BFS 6 6 6 6 6
    OPS 5 5 5 5 5
    FCSA−host 4 4 3 3 3.5
    MOACO 3 3 2 2 2.5
    FCWSEO 2 2 1 4 2.25
    WL 1 1 4 1 1.75
    下载: 导出CSV

    表  3  β=0.70时,暴雨灾害主题下各种先进主题爬虫方法的实验结果比较

    算法AccuracyLPARDPSDDPARLPSDLPTime/h
    WSE(2019)0.7334110020.72900.160012.2
    On-ITS(2020)0.7340110100.72950.161913.2
    FCOSA_LG(2022)0.7653114790.75110.14620.80950.058113.1
    OLMOACO(2022)0.7417111260.77810.137516.0
    FCWSEO(2022)0.8108121620.82190.156611.6
    WL(本文)0.8489127340.68220.08970.70020.08918.4
    下载: 导出CSV

    表  4  β=0.70,时暴雨灾害主题下各种主题爬虫方法的Friedman ranks比较

    算法 Accuracy LP ARDP SDDP Average
    WSE 6 6 5 5 5.5
    On-ITS 5 5 4 6 5.0
    FCOSA_LG 3 3 3 3 3.0
    OLMOACO 4 4 2 2 3.0
    FCWSEO 2 2 1 4 2.25
    WL 1 1 6 1 2.25
    下载: 导出CSV

    表  5  台风灾害主题下各种主题爬虫算法在不同爬行阶段实验结果比较

    DP算法AccuracyLPARDPSDDPARLPSDLPTime/h
    1000BFS0.092920.2310.221
    OPS0.3913910.4320.283
    SA0.4144140.5510.212
    WSE0.5715710.6720.123
    On-ITS0.7077070.8110.152
    OLMOACO0.6256250.6810.212
    WL0.7147140.7010.1210.7470.112
    5000BFS0.0713550.2490.222
    OPS0.24812400.4420.241
    SA0.49224600.5910.181
    WSE0.60630300.6640.134
    On-ITS0.80740350.8520.128
    OLMOACO0.76738350.7010.126
    WL0.86843380.7030.1080.7210.104
    10000BFS0.0454480.2120.174
    OPS0.12412400.4310.172
    SA0.42242150.5520.169
    WSE0.70770690.6870.124
    On-ITS0.81281200.7810.112
    OLMOACO0.73773700.7000.088
    WL0.89389270.7010.1210.7230.098
    15000BFS0.0477050.2110.1848.5
    OPS0.08312440.4360.1449.1
    SA0.35853700.5330.16011.1
    WSE0.704105600.6840.12712.2
    On-ITS0.820123000.7920.12313.2
    OLMOACO0.750112500.7000.07515.0
    WL0.873130950.7020.0990.7120.0958.2
    下载: 导出CSV

    表  6  台风灾害主题下7种主题爬虫算法的Friedman ranks比较

    算法 Accuracy LP ARDP SDDP Average
    BFS 7 7 7 7 7
    OPS 6 6 6 5 5.75
    SA 5 5 5 6 5.25
    WSE 4 4 4 4 4.0
    On-ITS 2 2 1 3 2.0
    OLMOACO 3 3 3 1 2.5
    WL 1 1 2 2 1.5
    下载: 导出CSV
  • [1] 中国互联网络信息中心. 中国互联网络发展状况统计报告[EB/OL]. [2022-01-21]. http://www.cnnic.net.cn/NMediaFile/old_attach/P020220721404263787858.pdf.

    China Internet Network Information Center. Statistical report on the development of Internet in China[EB/OL]. [2022-01-21]. http://www.cnnic.net.cn/NMediaFile/old_attach/P020220721404263787858.pdf.
    [2] RAWAT A, BANSAL M. Review paper on focused crawler for categorization[J]. International Journal of Computer Trends & Technology, 2014, 12(3): 141-143.
    [3] DE BRA P M E, POST R D J. Searching for arbitrary information in the WWW: The fish−search for mosaic[C]// World Wide Web Conference. Geneva: [s.n.], 1994: 1-11.
    [4] 程元堃, 廖闻剑, 程光. 词向量聚类加权shark−search的主题爬虫策略研究[J]. 计算机与数字工程, 2018, 46(1): 144-148. doi:  10.3969/j.issn.1672-9722.2018.01.031

    CHENG Y K, LIAO W J, CHENG G. Research on the theme crawler strategy of shark-search weighted by word vector clustering[J]. Computer and Digital Engineering, 2018, 46(1): 144-148. doi:  10.3969/j.issn.1672-9722.2018.01.031
    [5] BRIN S, PAGE L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1-7): 107-117. doi:  10.1016/S0169-7552(98)00110-X
    [6] GAO Q, ZHANG Y P. Study on theme-drift of hyperlink-induced topic search algorithm[J]. Journal of Computer Applications, 2009, 29(11): 3100-3102. doi:  10.3724/SP.J.1087.2009.03100
    [7] 周雪, 刘乃文. 引入主题链接块因子的候选链接搜索策略研究[J]. 计算机与数字工程, 2018, 46(5): 874-878. doi:  10.3969/j.issn.1672-9722.2018.05.006

    ZHOU X, LIU N W. Research on candidate link search strategy with Topic link block factor[J]. Computer and Digital Engineering, 2018, 46(5): 874-878. doi:  10.3969/j.issn.1672-9722.2018.05.006
    [8] SUEBCHUA T, MANASKASEMSAK B, RUNGSAWANG A, et al. Efficient topical focused crawling through neighborhood feature[J]. New Generation Computing, 2018, 36(2): 95-118. doi:  10.1007/s00354-017-0029-8
    [9] 库珊, 刘钊. 基于PageRank与HITS的改进算法的网页排名优化[J]. 武汉科技大学学报, 2019, 42(2): 155-160.

    KU S, LIU Z. Webpage ranking optimization based on the improved algorithm of PageRank and HITS[J]. Journal of Wuhan University of Science and Technology, 2019, 42(2): 155-160.
    [10] 姜琨, 朱磊, 王一川. 基于动态隧道技术的主题爬行策略[J]. 计算机系统应用, 2020, 29(3): 253-260.

    JIANG K, ZHU L, WANG Y C. Topic crawling strategy based on dynamic tunneling technology[J]. Computer System Applications, 2020, 29(3): 253-260.
    [11] HOSSEINKHANI J, TAHERDOOST H, KEIKHAEE S. Anton framework based on semantic focused crawler to support web crime mining using SVM[J]. Annals of Data Science, 2021, 8(2): 227-240. doi:  10.1007/s40745-019-00208-5
    [12] 刘景发, 李新, 蒋盛益. 基于网页空间进化算法的暴雨灾害主题爬虫策略[J]. 计算机工程, 2019, 45(2): 184-190. doi:  10.19678/j.issn.1000-3428.0052035

    LIU J F, LI X, JIANG S Y. Crawler strategy for rainstorm disaster theme based on webpage space evolution algorithm[J]. Computer Engineering, 2019, 45(2): 184-190. doi:  10.19678/j.issn.1000-3428.0052035
    [13] LIU J F, LI X, ZHANG Q S, et al. A novel focused crawler combining Web space evolution and domain ontology[J]. Knowledge-Based Systems, 2022, 243: 108495. doi:  10.1016/j.knosys.2022.108495
    [14] LIU J F, DONG Y, LIU Z X, et al. Applying ontology learning and multi-objective ant colony optimization method for focused crawling to meteorological disasters domain knowledge[J]. Expert Systems with Applications, 2022, 198: 116741. doi:  10.1016/j.eswa.2022.116741
    [15] 荆文鹏, 王育坚, 董伟伟. 自适应遗传算法在主题爬虫搜索策略中的应用研究[J]. 计算机科学, 2016, 43(8): 254-257. doi:  10.11896/j.issn.1002-137X.2016.08.051

    JING W P, WANG Y J, DONG W W. Application research of adaptive genetic algorithm in topic crawler search strategy[J]. Computer Science, 2016, 43(8): 254-257. doi:  10.11896/j.issn.1002-137X.2016.08.051
    [16] 刘景发, 李帆, 蒋盛益. 基于综合优先度和主机信息的暴雨灾害主题退火爬虫算法[J]. 计算机科学, 2019, 46(2): 215-222. doi:  10.11896/j.issn.1002-137X.2019.02.033

    LIU J F, LI F, JIANG S Y. Annealing crawler algorithm for rainstorm disaster theme based on comprehensive priority and host information[J]. Computer Science, 2019, 46(2): 215-222. doi:  10.11896/j.issn.1002-137X.2019.02.033
    [17] 东熠, 刘景发, 刘文杰. 基于多目标蚁群算法的主题爬虫策略[J]. 计算机工程, 2020, 46(9): 274-282. doi:  10.19678/j.issn.1000-3428.0055967

    DONG Y, LIU J F, LIU W J. Focused crawler strategy based on multi−objective ant colony algorithm[J]. Computer Engineering, 2020, 46(9): 274-282. doi:  10.19678/j.issn.1000-3428.0055967
    [18] DU Y J, LIU W J, LV X J, et al. An improved focused crawler based on semantic similarity vector space model[J]. Applied Soft Computing, 2015, 36: 392-407. doi:  10.1016/j.asoc.2015.07.026
    [19] CHEN K W, ZHANG Z P, LONG J, et al. Turning from TF-IDF to TF-IGM for term weighting in text classification[J]. Expert Systems with Applications, 2016, 66: 245-260. doi:  10.1016/j.eswa.2016.09.009
    [20] WANG F, LANDAU D P. Efficient, multiple-range random walk algorithm to calculate the density of states[J]. Physical Review Letters, 2001, 86(10): 2050. doi:  10.1103/PhysRevLett.86.2050
    [21] WANG B W, ZHAO P. An adaptive image watermarking method combining SVD and Wang-Landau sampling in DWT domain[J]. Mathematics, 2020, 8(5): 1-20.
    [22] 曹红英, 田华, 侯杰, 等. 使用王朗道蒙特卡罗算法和机器学习研究伊辛模型相变[J]. 山西大学学报(自然科学版), 2022, 12: 1-9.

    CAO H Y, TIAN H, HOU J, et al. Studying the phase transitions for Ising model through Wang-Landau monte carlo algorithm and machine learning[J]. Journal of Shanxi University (Natural Science Edition), 2022, 12: 1-9.
    [23] LIPOWSKI A, LIPOWSKA D. Roulette-Wheel selection via stochastic acceptance[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(6): 2193-2196. doi:  10.1016/j.physa.2011.12.004
    [24] RAWAT S, PATIL D R. Efficient focused crawling based on best−first search[C]//2013 3rd IEEE International Advance Computing Conference (IACC). [S.l.]: IEEE, 2013: 908-911.
    [25] 王桦. 基于广度优先的主题爬虫的设计与实现[D]. 上海: 复旦大学, 2011.

    WANG H. Design and implementation of theme crawler based on breadth first[D]. Shanghai: Fudan University, 2011.
    [26] 刘景发, 顾瑶平, 刘文杰. 融合本体和改进禁忌搜索策略的气象灾害主题爬虫方[J]. 计算机应用, 2020, 40(8): 2255-2261.

    LIU J F, GU Y P, LIU W J. Focused crawler method combining ontology and improved tabu search for meteorological disaster[J]. Journal of Computer Applications, 2020, 40(8): 2255-2261.
    [27] LIU J F, LI F, DING R Y, et al. Focused crawling strategies based on ontologies and simulated annealing algorithm for rainstorm disaster domain knowledge[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(8): 1189-1205.
    [28] 贺晟, 程家兴, 蔡欣宝. 基于模拟退火算法的主题爬虫[J]. 计算机技术与发展, 2009, 19(12): 55-58. doi:  10.3969/j.issn.1673-629X.2009.12.015

    HE S, CHENG J X, CAI X B. Focused crawler based on simulated anneal algorithm[J]. Computer Technology and Development, 2009, 19(12): 55-58. doi:  10.3969/j.issn.1673-629X.2009.12.015
  • [1] 赵夫群, 戴翀, 耿国华.  基于特征融合的文物碎片模型检索 . 电子科技大学学报, 2021, 50(2): 225-230. doi: 10.12178/1001-0548.2020281
    [2] 巩云超, 李发旭, 周丽娜, 胡枫.  在线社交超网络的信息全局传播模型 . 电子科技大学学报, 2021, 50(3): 437-445. doi: 10.12178/1001-0548.2020401
    [3] 王瑞, 闫方, 逯静, 杨文艺.  运用Dropout-LSTM模型的新冠肺炎趋势预测 . 电子科技大学学报, 2021, 50(3): 414-421. doi: 10.12178/1001-0548.2020403
    [4] 傅家旗, 郭强, 刘建国.  基于有限信息的网络邻接关系识别研究 . 电子科技大学学报, 2019, 48(5): 794-800. doi: 10.3969/j.issn.1001-0548.2019.05.021
    [5] 常文文, 王宏, 化成城, 王翘秀, 原玥, 刘冲.  基于脑功能网络连接的隐藏信息检测研究 . 电子科技大学学报, 2018, 47(5): 775-780. doi: 10.3969/j.issn.1001-0548.2018.05.022
    [6] 伍度志, 杨帆, 赵静.  基于信息熵的加权基因关联网络融合方法 . 电子科技大学学报, 2018, 47(2): 286-291. doi: 10.3969/j.issn.1001-0548.2018.02.020
    [7] 李陶深, 王翼, 黄汝维.  云环境下代理加密模糊检索研究 . 电子科技大学学报, 2018, 47(4): 580-587. doi: 10.3969/j.issn.1001-0548.2018.04.017
    [8] 周冬梅, 陈婷, 赵闻文.  众筹平台的双层网络信息传播模型研究 . 电子科技大学学报, 2018, 47(1): 132-138. doi: 10.3969/j.issn.1001-0548.2018.01.020
    [9] 罗春海, 刘红丽, 胡海波.  微博网络中用户主题兴趣相关性及主题信息扩散研究 . 电子科技大学学报, 2017, 46(2): 458-468. doi: 10.3969/j.issn.1001-0548.2017.02.022
    [10] 张聿博, 张锡哲, 徐超.  基于部分路径的社交网络信息源定位方法 . 电子科技大学学报, 2017, 46(1): 75-80. doi: 10.3969/j.issn.1001-0548.2017.01.012
    [11] 刘韵婷, 井元伟, 张嗣瀛.  基于量化信息的无线传感器网络多声源定位研究 . 电子科技大学学报, 2017, 46(4): 530-533. doi: 10.3969/j.issn.1001-0548.2017.04.009
    [12] 陈玟宇, 贾贞, 祝光湖.  社交网络上基于信息驱动的行为传播研究 . 电子科技大学学报, 2015, 44(2): 172-177. doi: 10.3969/j.issn.1001-0548.2015.02.002
    [13] 阚佳倩, 谢家荣, 张海峰.  社会强化效应及连边权重对网络信息传播的影响分析 . 电子科技大学学报, 2014, 43(1): 21-25. doi: 10.3969/j.issn.1001-0548.2014.01.003
    [14] 周涛.  网络大数据——复杂网络的新挑战: 如何从海量数据获取信息? . 电子科技大学学报, 2013, 42(1): 7-8. doi: 10.3969/j.issn.1001-0548.2013.01.004
    [15] 鲁珂, 赵继东, 吴跃.  新型的图像检索最优实验设计算法 . 电子科技大学学报, 2012, 41(2): 269-273. doi: 10.3969/j.issn.1001-0548.2012.02.019
    [16] 何海江, 陈姝.  由排序支持向量机抽取博客文章的摘要 . 电子科技大学学报, 2010, 39(4): 593-597. doi: 10.3969/j.issn.1001-0548.2010.04.026
    [17] 范自柱, 刘二根, 徐保根.  互信息在图像检索中的应用 . 电子科技大学学报, 2007, 36(6): 1311-1314.
    [18] 汤志伟, 符萍.  基于小波神经网络的信息系统综合评价模型 . 电子科技大学学报, 2005, 34(5): 672-675.
    [19] 张选芳.  Internet网络安全的信息过滤模型分析 . 电子科技大学学报, 2004, 33(3): 270-272.
    [20] 陈洑.  基于GSM网络的GPS车辆信息服务系统解决方案 . 电子科技大学学报, 2003, 32(4): 371-374.
  • 加载中
计量
  • 文章访问数:  3343
  • HTML全文浏览量:  919
  • PDF下载量:  58
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-06-13
  • 修回日期:  2023-01-30
  • 网络出版日期:  2023-09-06
  • 刊出日期:  2023-07-07

基于Wang−Landau抽样的主题爬虫方法

doi: 10.12178/1001-0548.2022183
    基金项目:  广东省基础与应用基础研究(2021A1515011974, 2023A1515011344)
    作者简介:

    刘景发(1972 – ),男,教授,博士,主要从事信息检索、计算智能、多目标优化等方面的研究

    通讯作者: 赵鹏,E-mail:zhaopeng_159@163.com
  • 中图分类号: TP391

摘要: 针对传统爬虫方法存在搜索易陷入局部最优,且很少考虑结合历史爬行经验对爬行路径进行修正的缺陷,提出一种基于WL抽样的主题爬行方法。该方法分别使用向量空间模型(VSM)和PageRank算法对链接的相关性和重要性进行评价,采用区域竞争策略从具有主题相关或潜在价值的链接集合中选出目标链接。基于概率密度函数,WL抽样算法对侯选集中选出的目标链接进行抽样判断,根据历史统计经验指导爬虫的后续爬行,从而优化搜索路径。实验结果表明,提出的基于WL抽样的主题爬虫方法比其他主题爬虫方法能搜索到更多主题相关的网页,其爬准率和所有下载网页主题相关度的标准差具有明显优势。

English Abstract

刘景发, 陈靖岚, 赵鹏. 基于Wang−Landau抽样的主题爬虫方法[J]. 电子科技大学学报, 2023, 52(4): 578-587. doi: 10.12178/1001-0548.2022183
引用本文: 刘景发, 陈靖岚, 赵鹏. 基于Wang−Landau抽样的主题爬虫方法[J]. 电子科技大学学报, 2023, 52(4): 578-587. doi: 10.12178/1001-0548.2022183
LIU Jingfa, CHEN Jinglan, ZHAO Peng. Focused Crawler Method Based on Wang−Landau Sampling[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(4): 578-587. doi: 10.12178/1001-0548.2022183
Citation: LIU Jingfa, CHEN Jinglan, ZHAO Peng. Focused Crawler Method Based on Wang−Landau Sampling[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(4): 578-587. doi: 10.12178/1001-0548.2022183
  • 当今,有效信息变得越来越重要,而网络爬虫正是穿梭于互联网中帮助人们自动获取信息的一把利器。据中国互联网络信息中心第49次调查报告显示[1],截至2021年12月,仅中国网页的数量就已经达到3 350亿个,全球互联网的网页数量更是难以估计,这使得传统搜索引擎很难满足特定用户的需求。因此,如何利用主题爬虫[2]抓取特定领域的数据,从而为特定人群提供个性化推荐已经成为许多学者研究的热点。

    主题爬虫是一种旨在搜集某一领域数据的网络爬虫,它将使用某种策略和网页分析算法来降低传统网络爬虫因大量网页遍历而带来的代价,从而更有效地获取主题相关的信息。目前,主题爬虫的研究主要集中在链接的评价和搜索策略上。链接评价是指对链接相关性和重要性的评价。链接评价方法主要有基于网页内容分析的方法和基于链接结构分析的方法。前者的代表主要有Fish Search[3]和Shark Search[4];后者的代表主要有PageRank算法[5]与HITS(hyperlink−induced topic search)[6]算法。由于基于网页内容分析的主题爬虫方法仅考虑网页、锚文本等文本信息,缺乏对网页链接结构的考虑,所以容易导致爬虫陷入局部最优。基于链接结构分析的主题爬虫应用较为广泛,近年来一些学者进行了深入研究。文献[7]通过在Shark Search算法的基础上引入相关链接块的概念来解决链接的锚文本较为短小、不能准确表明链接指向主题相关性的缺陷。文献[8]以主机目标网站中若干相同目录路径中的页面聚合相关性作为领域相关性特征,提出一种拥有“领域功能”的主题爬虫方法。但该类方法由于未考虑链接的主题相关性,所以爬虫容易产生主题漂移现象[6]。鉴于此,一些学者尝试综合这两类方法来提高链接评价的准确性[9]。另外,搜索策略决定不同价值链接被访问的次序。传统的纯粹基于链接相关性高低的爬行策略难以使爬虫通过具有潜在价值的链接进行网页有效搜索。为提升主题爬虫的隧道穿越能力[10],引导主题爬虫以最小的代价从相关度低的区域跳转到相关度高的区域,文献[11-14]采用智能优化方法来改进爬虫的全局寻优能力。文献[11]为提取和揭示网络犯罪,使用基于蚁群优化的主题爬虫,为Web犯罪挖掘开发一种基于本体的优化方法。文献[12]将多目标优化算法引入主题爬虫,提出了一种基于网页空间进化(WSE)算法的主题爬虫方法。文献[13]进一步将WSE算法和领域本体相结合,提出了一种新的基于WSE的主题爬虫算法(focused crawler combining Web space evolution and ontology, FCWSEO)。在该算法中,通过构建领域本体建立主题模型,使用一种最近最远候选解法挑选Pareto最优链接。文献[14]为克服人工构建本体过程中构建者知识储备和主观意识的限制,提出了一种结合潜狄利克雷分布和Apriori算法的领域本体半自动构建方法。他们基于链接评估的多目标优化模型和改进的多目标蚁群优化算法来指导爬虫的搜索方向。文献[15]通过加入时间因子,动态调节适应度函数和遗传算子,在一定程度上避免了爬虫陷入循环爬行的陷阱。文献[16]结合爬虫记忆历史主机信息和模拟退火算法设计了暴雨灾害主题爬虫。文献[17]应用多目标蚁群算法来选择主题爬虫过程中的Pareto最优链接,进而引导爬虫搜索更多主题相关的页面。本质上,基于智能优化算法的主题爬虫以一定规则或概率接收主题相关度低的页面,具有全局优化的优点。但上述算法在链接搜索次序选择上缺乏对已爬取网页的统计,导致历史经验难以指导后续的网页搜索。特别是当爬虫距离主题相关页面较远时,常常出现主题偏移现象。

    针对上述问题,本文提出一种基于Wang-Landau(WL)抽样的主题爬虫方法。该方法采用一组带有语义权重的向量来描述主题,并使用向量空间模型(vector space model, VSM)[18]分别计算链接对应的锚文本和链接指向网页文本的主题相关度;再利用PageRank算法从链接结构角度评价链接的重要性,进而选定具有潜在价值的链接。基于WL算法,将能量状态密度函数和直方图函数应用于主题爬行策略,通过统计状态密度的变化,决定主题爬虫是否接受目标链接,进而指导爬虫寻找一条合适的主题爬行路径。此外,为防止爬虫接受无关链接而导致主题搜索方向偏移,引入区域竞争策略挑选目标链接,以获得更好的爬行效果。

    • 在主题爬虫过程中,本文综合考虑链接指向网页的主题相关度和链接锚文本主题相关度,并根据链接所在页面的重要性选择具有潜在价值的页面。

    • 在主题爬虫中,一般采用一组特定术语组成的主题词向量TK来描述用户选定的特定主题,假设TK定义如下:

      $$ {\bf{TK}}={{\rm{tk}}_{1}, {\rm{tk}}_{2}, \cdots, {\rm{tk}}_{n}} $$ (1)

      式中,tki(i=1,2,···,n)表示第i个主题词;n为主题词集TK中元素的个数。本文以暴雨灾害和台风灾害为主题,根据领域专家经验和多次对比实验,设置描述暴雨灾害的主题词组分别为暴雨、气象、天气、灾害和预防,描述台风灾害的主题词组分别为台风、风暴潮、暴雨、气压和风力。令wtki为主题词tki的权重,其值主要基于特征提取的主题词权重计算方法和领域专家结合经验设定[12]。在主题词向量确定以后,为计算网页主题相关度,需要确定网页文本特征向量。本文采用IK-Analyzer对网页文本进行分词、去停用词等预处理。将处理之后的网页文本Pj用向量DKj表示:

      $$ {\bf{DK}}_{j}={{\rm{dk}}_{j,1,}, {\rm{dk}}_{j,2}, \cdots, {\rm{dk}}_{j,i}, \cdots, {\rm{dk}}_{j,n}} $$ (2)

      式中,dkj,i表示网页文本Pj中的第i个特征词。对于文本中的某个特征词,它的权重采用词频−逆文档频率(term frequency–inverse document frequency, TF-IDF) [19]方法计算:

      $$ {w_{{\rm{d}}{{\rm{k}}_{j{\text{,}}i}}}} = \frac{{{n_{j,i}}}}{{\displaystyle\sum\limits_k {{n_{j,k}}} }} {{\rm{lg}} }\frac{{{D}}}{{1 + {{{D}}_i}}} $$ (3)

      式中,nj,i表示在网页文本Pj中第i个特征词出现的次数;分母表示文本Pj中所有特征词出现的次数之和;D为当前爬取网页文本总数;Di为包含第i个特征词的网页文本数。某个词的权重越大,说明该词越能代表文档的特征。当词权重为0时,说明该词不出现于该网页。

      对于链接l所在网页Pl,本文采用VSM计算主题向量TK和网页文本特征向量DKl的主题相关度R(Pl):

      $$\begin{split} & R({P_l}) = {\rm{sim}}({\bf{TK}},{\bf{D}}{{\bf{K}}_l}) = \cos < {{\boldsymbol{W}}_{{\bf{TK}}}},{{\boldsymbol{W}}_{{\bf{D}}{{\bf{K}}_l}}} > = \\ &\qquad\qquad \frac{{\displaystyle\sum\limits_{i = 1}^n {{w_{{\rm{t}}{{\rm{k}}_i}}}{w_{{\rm{d}}{{\rm{k}}_{l,i}}}}} }}{{\sqrt {\displaystyle\sum\limits_{i = 1}^n {w_{_{{\rm{t}}{{\rm{k}}_i}}}^2} \displaystyle\sum\limits_{i = 1}^n {w_{_{{\rm{d}}{{\rm{k}}_{l,i}}}}^2} } }} \end{split}$$ (4)

      式中,WTK为用户所指定主题词的权重向量;$ {{\boldsymbol{W}}_{{\bf{D}}{{\bf{K}}_l}}} $为网页文本Pl(或锚文本)的特征权重向量。本文由式(4)分别计算待访问链接l所指向网页的主题相关度和其锚文本的主题相关度,再进行线性加权求和得到链接l的综合主题相关度:

      $$ R(l)= \partial R({\rm{anchor}}_{l})+(1-\partial ) R(P_{l}) $$ (5)

      式中,R(l)表示链接l的综合主题相关度;R(anchorl)和R(Pl)分别为链接l的锚文本anchorl和链接l指向网页Pl的主题相关度;为权重系数。

      由于基于网页文本内容和链接结构分析的主题爬虫方法在各自单独使用时其爬准率往往受限,因此通常相互结合使用,实现互补,进而提高爬虫抓取网页的准确率。此外,上述策略在计算链接优先度后,大多采取最佳优先机制进行网页抓取,该贪心策略往往容易使爬虫陷入局部最优。

    • 从有潜在价值的网页出发,抓取更多主题相关页面,还可以从重要性的角度综合评价网页。一般地,网页的重要性主要由网页链接关系来衡量,本文采用PageRank算法来计算网页的重要性。PageRank算法的思想是通过网页的引用关系来判断网页是否重要,即若某网页被其他网页引用次数越多,就认为该网页越重要,而当某网页被这些重要的网页引用时,该网页也被认为是重要的。本文采用的PageRank计算公式为:

      $$ {\rm{PR}}({P_j}) = (1 - \alpha ) + \alpha \sum\limits_{{P_i} \in {B_j}} {\frac{{{\rm{PR}}({P_i})}}{{|{C_i}|}}} $$ (6)

      式中,PR(Pj)代表网页Pj的PR值;Bj为网页Pj的所有入链页面集;CiPj的入链页面Pi的出链集合;$ \alpha $= 0.85为跳转因子,主要用于表示Web用户有多大概率通过其他网页的出链来访问当前页面,1−$ \alpha $表示用户通过键入URL等方式来直接访问该网页的概率。通过式(6)可给网页赋予一个重要性的量化值。本文将从主题相关度较低的网页中选取重要性值PR≥2的网页作为具有潜在价值的网页,这些网页将有机会在爬行过程中被选中,从而辅助爬虫跳出局部最优,以搜寻更多主题相关的页面。

    • 传统主题爬虫多采用按主题相关度从高到低依次选择链接进行网页抓取。然而,并不是所有的相关页面都聚集在一起,当爬虫始终都抓取相关度高的网页时,容易陷入搜索的局部最优。因此,为实现全局寻优,结合网页主题相关性和重要性评价指标,提出基于Wang−Landau抽样的主题爬虫过程。

    • 基于频率直方图的Wang−Landau(WL)抽样算法[20]是一种蒙特卡洛(Monte Carlo, MC)算法,其理论基础是:状态X被访问的概率与其能量状态密度g(E(X))的倒数成正比,其中E(X)表示状态空间中状态X的能量。传统的MC方法局限于在温度不变的前提下产生正则分布,因此,想获得高质量的解,算法就必须在不同温度条件下多次运行。如模拟退火算法就需要不断地进行退火操作,十分耗时。Wang−Landau抽样算法与温度无关,这使得它可以按照一定的概率接受准则漫步于状态空间,进而获取一个平坦的能量直方图H(X)并得到概率密度函数g(E(X)),即WL抽样算法可从系统中的某个状态出发,逐步统计各个状态的能量,进而发掘整个系统中各个状态能量的分布规律。这与主题爬虫面临的问题场景类似,在网页空间中,各主题相关页面(对应状态空间中的状态)分布未知,人们无法通过互联网的结构去直接设计网页抓取策略。因此,本文将整个互联网中的Web资源看成是系统的状态空间S′,主题相关页面分布于S′中。为了在这个系统中搜寻到更多的主题相关页面,在计算各链接的主题相关度后,通过将上文给出的链接主题相关度R(l)和状态(链接)的能量E(l)相对应,设计基于WL抽样算法的主题搜索策略,即WL抽样算法基于状态密度函数行走于网页空间,并根据历史经验的积累实现对低状态密度函数值链接的有效抽样。

    • 在WL抽样算法的开始,网页空间中所有链接X及其状态密度函数g(E(X))均是未知的。每当访问到一个新的链接X,这个链接的状态密度函数g(E(X))及直方图函数H(E(X))就被置为1。由于本文计算的能量值为链接的主题相关度,所以能量值介于0~1之间。不妨将其划分为50个能量区间,每个能量区间间隔为0.02,即[0, 0.02), [0.02, 0.04),···, [0.98, 1]。为便于描述,将能量区间[$\left\lfloor {E(X)} \right\rfloor $, $\left\lceil {E(X)} \right\rceil $)标记为[E(X)],其中$\left\lfloor {E(X)} \right\rfloor $E(X)所属能量区间的下边界,$\left\lceil {E(X)} \right\rceil $E(X) 所属能量区间的上边界,X为网页空间中某一链接。如E(X)=0.621处于能量区间[0.62, 0.64)中,记为[0.621]。将Wang−Landau抽样算法应用于主题爬虫,其基本思路如下:首先,从种子链接等待队列中选择一个初始链接X1,然后采用区域竞争策略(见2.3节)产生目标链接X2,再根据P(X1$ \to $X2)=min(g(E(X1))/g(E(X2)), 1)=min(eln[g(E1)−g(E2)], 1)的值来判断X2是否接受,这里E1E2分别表示X1X2的综合主题相关度,即E1=E(X1),E2=E(X2)。如果X2被接受,则修改X2的状态密度函数g(E(X2)):令g(E(X2))=fig(E(X2)),其中,fi>1为一个罚因子,同时修改其直方图函数:令H([E(X2)])=H([E(X2)]) + 1;如果链接X2不被接受,则类似修改X1的状态密度函数和直方图函数值。另外,算法的收敛速度由直方图的平坦度控制,而所谓平坦的直方图是指所有H(E(X))的值均不小于直方图的平均值〈H([E(X)])〉的k(0<k<1)倍,k由系统的复杂度和g(E(X))的准确度决定。 在实际操作中要获得一个绝对平坦的直方图非常困难。因此,每1 000步 MC 迭代后,算法将检查直方图是否近似平坦。若H(E)变得近似平坦,即若对于已访问过的能量区间集合S中所有[E],都有H([E])≥kH([E(X)]),则调整修正因子为一个更小的值,即令fi+1=$\sqrt {{f_i}} $i=i+1,若迭代步数L>106,则提前结束爬虫搜索; 否则,将所有访问过的能量区间[E(X)]所对应的H([E(X)]) 置为零,g(E(X))值保留,开始下一次随机行走。此时,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=$\varnothing $;令T=1000,DP=0,LP=0;//DP表示下载网页数,LP表示下载相关网页数;

      2) 从Queue中取出综合主题相关度最高的队头链接X1作为当前链接;将[E1]加入已访问过的能量区间集合S,即令S=S+{[E1]},令直方图函数H([E1])=1,概率密度函数g(E1)=1;

      3) If DP<15 000 && Queue !=$\varnothing $ then

      m=0,转至步骤4);//m用于记录不接受目标链接的次数;

      Else计算爬准率等评价指标,算法结束;

      End If

      4) 采用区域竞争策略(如2.3节)产生目标链接X2并计算其综合主题相关度E2,令L=L+1;

      5) If [E2]$ \notin $S then

      g([E2])=1,H([E2])=1,S=S∪{[E2]},计算接受概率:

      $P({X_1} \to {X_2}) = \min ({{\rm{e}}^{\ln g({E_1}) - \ln g({E_2})}},1) $    

      End If

      6) If random(0,1)< P(X1X2) then

      X1=X2E1=E2,lng(E2)=lnfi+lng(E2),

      H([E2])= H([E2])+1; 转步骤8);

      Else令lng(E1) = lnfi + lng(E1), H([E1]) = H([E1]) + 1,m =m + 1;转步骤7);

      End If

      7) If m≥5 then

      从Queue中取出综合相关度最大的链接作为新的队头链接X1;转步骤8);

      Else 转步骤4);

      End If

      8) 将X1移出Queue,取出X1指向页面的子链接中满足R(l)≥0.2的链接(去重),将这些链接(假设其个数为k1)加入Queue,令DP=DP+k1

      9) For j = 1 to k1 do

      If R(Pj)≥β then //如果子链接j指向网页的主题相关度R(Pj)大于或等于阈值β

      令LP=LP+1;//保存该网页Pj到主题相关网页集中

      End If

      End For

      10) If L%T==0 then

      If 任给[E]∈S,都有H([E])≥ln 2/ln fi then

      fi+1=$ \sqrt{{f}_{i}} $i=i+1,转步骤11);

      Else 转步骤3);

      End If

      End If

      11) If L<106 then

      对于S中所有[E],恢复H([E])=0,而g([E])值保持不变,转步骤3);

      Else 算法提前结束;

      End If

      从上述算法不难看出,算法将以P(X1X2)的概率接受目标链接X2,并以一定的概率接受当前最佳链接,这既避免了算法陷入局部最优,也防止了因跳坑次数太多而增加时间损耗。在将目标链接X2指向页面的子链接加入Queue之前,需要进行去重操作。此外,为提升等待队列中链接的质量,算法将保留子链接中综合主题相关度R(l)≥0.2的链接。目前,WL抽样算法已经成功运用于数字水印中的参数优化[21]、统计物理方向中的相变[22]等问题,这表明WL算法具有适应于求解不同问题的能力。本文将WL抽样算法应用于主题爬虫,使爬行路径得到进一步优化。

    • 在爬行过程中,爬虫需不断地获取新的链接,以便搜索更多主题相关页面。本文提出启发式的区域竞争策略以从链接等待队列中挑选出目标链接。该策略的主要思想为:将等待队列中的链接按链接指向的网页域名归属划分为不同的区域,并从竞争获胜区域中采用轮盘赌策略选定某链接作为目标链接。

      区域竞争策略的具体步骤如下。

      1) 按照域名将链接等待队列Queue中的链接划分为不同的区域。

      2) 选取上述区域中具有最高平均主题相关度的区域Ri (Ri表示按主机信息划分后的第i个区域,i=1, 2, ···, u)作为竞争(competition)获胜区域(winer)。

      3) 采用轮盘赌选择(roulette wheel selection, RWS)[23]策略挑选目标链接,基本过程为:

      ①将获胜区域(winer)中所有链接Xj (j=1, 2, ··· , k)构成候选链接集合C,显然,候选链接集合C中既包含主题相关链接,也包含具有潜在价值的链接(重要性值PR≥2的链接);②对候选链接集合C中的所有链接,根据式(5)采用轮盘赌,选出一个链接为目标链接X2

      本文提出的区域竞争策略与传统的最佳优先搜索(OPS)[24]最大的区别在于将链接等待队列按区域划分后再选择目标链接。这样算法既不会因仅接受主题相关度高的链接,从而导致爬虫易陷入局部最优;也不会因接受一些主题相关度很低的链接,从而导致搜索方向发生主题偏移。另外,该策略也保证WL算法能够在具有主题相关度高的区域进行集中搜索后,依旧能够跳出该区域进行分散搜索,进而提高主题爬虫抽样的多样性。

    • 实验环境:处理器Intel(R)为Core(TM)i7-7700 HQ,CPU为2.80 GHz,RAM为8 GB;开发工具为MyEclipse+JDK1.7+Java语言;分词工具为IK-Analyzer;HTML解析器为Jsoup。

      爬行主题:暴雨灾害和台风灾害。

      实验数据:暴雨灾害的主题词组为暴雨、气象、天气、灾害和预防,权重依次设为0.8、0.1、0.1、0.5和0.3;台风灾害的主题词组为台风、风暴潮、暴雨、气压和风力,权重依次设为0.8、0.5、0.3、0.2和0.2;对暴雨灾害和台风灾害,使用百度进行主题词搜索,对得到的搜索结果结合人工经验分别筛选18个和30个URL作为初始种子链接。

      实验参数:令调节因子=0.3;对暴雨灾害,设置主题相关度阈值β=0.62,对台风灾害,设置主题相关度阈值β=0.67;最大爬取网页数DP=15 000,其余参数均已在前文给出。

      上述这些实验数据和实验参数的设置对爬虫算法的效果有一定影响,其值是参考文献[12, 14]以及通过多次对比实验使爬虫算法达到最好结果而确定的。

    • 为评价爬虫方法的效果,通常使用爬准率(Accuracy)和爬全率(Recall)作为评价指标。因爬全率一般难以计算,本文选用爬准率作为评价主题爬虫效果的主要指标:

      $$ {\text{Accuracy = LP/DP}} $$ (8)

      式中,LP表示下载的主题相关网页数量;DP表示下载的总网页数。本文还使用平均主题相关度(average relevance, AR)和标准差 (standard deviation, SD)来测试爬虫的性能,包括所有下载网页的平均主题相关度(average relevance of all downloaded pages, ARDP)、所有下载网页主题相关度的标准差(standard deviation of topic relevance of all downloaded pages, SDDP)、所有下载主题相关网页的平均主题相关度(average relevance of all downloaded topic-relevant pages, ARLP)和所有下载主题相关网页主题相关度的标准差(standard deviation of topic relevance of all downloaded topic-relevant pages, SDLP):

      $$ \text{A}{\text{R}}_{\text{DP}}=\frac{1}{\text{DP}} \sum _{l=1}^{\text{DP}}R\left({P}_{l}\right) $$ (9)
      $$ \text{S}{\text{D}}_{\text{DP}}=\sqrt{\frac{1}{\text{DP}} \sum _{l=1}^{\text{DP}}\left(R\right({P}_{l})-\text{A}{\text{R}}_{\text{DP}}{)}^{2}} $$ (10)
      $$ \text{A}{\text{R}}_{\text{LP}}=\frac{1}{\text{LP}} \sum _{l=1}^{\text{LP}}R\left({P}_{l}\right) $$ (11)
      $$ \text{S}{\text{D}}_{\text{LP}}=\sqrt{\frac{1}{\text{LP}} \sum _{l=1}^{\text{LP}}\left(R\right({P}_{l})-\text{A}{\text{R}}_{\text{LP}}{)}^{2}} $$ (12)

      式中,R(Pl)表示网页Pl的主题相关度。

    • 针对暴雨灾害主题,本文实现了基于WL抽样的主题爬虫算法,并与文献中的广度优先搜索(breadth first search, BFS)[25]、最佳优先搜索(best first search, OPS)[24]、多目标蚁群优化(multi-objective ant colony optimization, MOACO)[17]、记忆历史主机信息退火爬虫算法(focused crawler based on simulated annealing with host information, FCSA-host)[16]及结合本体的网页空间进化主题爬虫算法(focused crawler combining webpage space evolution and ontology, FCWSEO)[13]进行了对比,如表1所示。评价指标包括爬准率(Accuracy)、下载的主题相关网页数(LP)、所有下载网页的平均主题相关度(ARDP)及其标准差(SDDP)、所有下载相关网页的平均主题相关度(ARLP)及其标准差(SDLP),以及算法运行时间(Time)。由于文献中MOACO和FCWSEO两个算法没有测试ARLP和SDLP两个评价指标,故在表1中未给出相应的结果。

      表1可知,在爬虫初始阶段(DP=1 000),因采用区域竞争策略对种子链接附近中的高度相关区域进行了访问,故WL方法在Accuracy、LP和SDDP上均取得最优结果。OPS算法因每次均接受相关度最高的链接,所以具有最高的ARDP和ARLP,且在Accuracy和LP上的表现仅次于WL方法,而FCSA−host算法获得最优的SDLP。当DP=5 000时,FCSA−host方法在Accuracy、LP和SDLP这3个指标上取得最优结果,在ARDP上MOACO方法对OPS算法实现反超。此后,OPS获取相关页面的能力逐渐降低,并因贪心策略而陷入搜索局部最优。当DP=10 000时,WL方法在Accuracy和LP两个指标上再次反超FCSA−host,同时高于其余对比方法。此时,FCWSEO方法结合本体的优势逐渐显现,在ARDP指标上取得最优效果。随着爬行的深入,当DP=15 000时,WL方法在Accuracy、LP和SDDP这3项指标上均高于其他方法。这是因为,WL方法的随机抽样能力使其始终能稳定地穿越一些潜在价值较高的链接并获取更多的主题相关网页。FCWSEO算法通过最近最远候选解法选择一组Pareto最优链接来更新种子链接库中的链接,这使其在Accuracy和LP两项指标上超过了除WL外的所有方法,且在ARDP上表现最优。MOACO策略通过选择主题爬虫过程中的Pareto最优链接,从而使更多可能指向主题相关页面的链接被接受,这使得它在ARDP和SDDP指标上分别取得了仅次于FCWSEO和WL方法的结果。FCSA−host方法给予了次优链接优先访问的机会,且具有历史记忆能力,这使得它的6项指标值均取得了较好的结果,且在ARLP指标上取得最优结果。当DP=15 000时,本文WL方法的Accuracy值分别比BFS、OPS、FCSA-host、 MOACO和FCWSEO的结果高出335.09%、44.56%、17.72%、11.58%及6.1%。表1显示,本文所提方法在爬准率Accuracy、下载相关网页的数量LP和下载网页主题相关度的标准差SDDP这3个指标上效果最好。不过,在ARDP、ARLP和SDLP指标上,WL方法表现一般,这主要是因为WL方法采用修改的状态密度函数和直方图策略(即每访问一次链接就给予该链接状态密度函数一个惩罚,并将其能量区间直方图函数+1)引导爬虫访问态密度低的区域,有利于爬虫扩大搜索范围,抓取更多主题相关网页,但并不能确保每次都只接受主题相关度高的链接。另外,在运行时间方面,WL方法跟文献中的其他方法相比也具有明显优势或相当。

      表 1  β=0.62时,暴雨灾害主题下各种主题爬虫算法在不同爬行阶段的实验结果比较

      DP算法AccuracyLPARDPSDDPARLPSDLPTime/h
      1000BFS0.32003200.49770.22900.75510.0780
      OPS0.82308230.71430.15750.77220.0642
      FCSA-host0.70107010.67200.15090.74920.0478
      MOACO0.62916290.69570.2810
      FCWSEO0.45424540.71090.1643
      WL0.85208520.66130.07160.68270.0835
      5000BFS0.269013450.43630.23780.74210.0572
      OPS0.770438520.68020.16100.74940.0586
      FCSA-host0.803040150.69530.11990.74220.0452
      MOACO0.704235210.78010.1865
      FCWSEO0.657232860.75900.1767
      WL0.779638980.67790.09290.67910.0802
      10000BFS0.134513450.29660.22260.74210.0572
      OPS0.653365330.62690.21750.75890.0622
      FCSA-host0.762876280.70040.13710.76400.0595
      MOACO0.787278720.77560.1537
      FCWSEO0.807080700.79040.1612
      WL0.850485040.67490.08210.68620.0774
      15000BFS0.202930430.37050.24380.74710.06378.6
      OPS0.610791600.61690.23390.76500.06339.0
      FCSA-host0.7499112480.70030.14710.77120.066511.8
      MOACO0.7912118680.77800.137715.8
      FCWSEO0.8322124830.82010.155812.2
      WL0.8828132420.69170.07840.71220.0820 8.1

      为综合考察6种算法在暴雨灾害主题下的实验效果,表2给出了6种算法在DP=15 000时对4个典型指标Accuracy、LP、ARDP和SDDP应用Friedman测试[13]的结果,用Ranks值表示。其中,Ranks值为1表示对应方法为该指标的最佳结果,6为最差结果。从表2可看出,WL方法除ARDP指标排在第4位外,在Accuracy、LP和SDDP指标上均排在第1位。综合来看,WL方法具有最小的平均Ranks值(Average=1.75),是所有对比方法中性能最好的方法。BFS在各阶段的Ranks值始终最高,故其性能最差。

      表 2  β=0.62时,暴雨灾害主题下各种主题爬虫算法的Friedman ranks比较

      算法 Accuracy LP ARDP SDDP Average
      BFS 6 6 6 6 6
      OPS 5 5 5 5 5
      FCSA−host 4 4 3 3 3.5
      MOACO 3 3 2 2 2.5
      FCWSEO 2 2 1 4 2.25
      WL 1 1 4 1 1.75

      为进一步测试WL方法的性能,在暴雨灾害主题下,设置网页主题相关度阈值β=0.70,最大爬取网页数DP=15 000,运行本文提出的基于WL抽样的主题爬虫算法,并给出各项评价指标Accuracy、LP、ARDP、SDDP、ARLP、SDLP以及运行时间(Time)的结果,与文献中的网页空间进化算法(WSE)[12]、融合本体和改进禁忌搜索策略的主题爬虫方法(On-ITS)[26]、基于全局与局部本体和模拟退火策略的主题爬虫算法(FCOSA_LG)[27]、结合本体学习和多目标蚁群优化方法(OLMOACO)的主题爬虫方法[14]以及融合本体的网页空间进化主题爬虫算法(FCWSEO)[13]的结果对比如表3所示。由于文献中WSE、On-ITS、OLMOACO和FCWSEO这4种算法没有测试ARLP和SDLP这两个评价指标,故在表3中未给出相应的结果。在6种基于智能优化算法的先进主题爬虫方法中,WL方法在Accuracy、LP和SDDP这3个度量指标上均获得最优结果;而FCWSEO在ARDP指标上,FCOSA_LG在ARLP和SDLP两个指标上得到最好结果。在运行时间上,本文WL方法比文献中的算法运行时间明减少或相当,这主要是因为WL方法采用修改的状态密度函数和直方图函数策略更有利于算法爬取主题相关网页,同时WL方法不需要通过本体构造得到主题向量。

      表 3  β=0.70时,暴雨灾害主题下各种先进主题爬虫方法的实验结果比较

      算法AccuracyLPARDPSDDPARLPSDLPTime/h
      WSE(2019)0.7334110020.72900.160012.2
      On-ITS(2020)0.7340110100.72950.161913.2
      FCOSA_LG(2022)0.7653114790.75110.14620.80950.058113.1
      OLMOACO(2022)0.7417111260.77810.137516.0
      FCWSEO(2022)0.8108121620.82190.156611.6
      WL(本文)0.8489127340.68220.08970.70020.08918.4

      为综合考察各种算法效果,表4给出了6种先进爬虫方法在DP=15 000时对4个典型指标Accuracy、LP、ARDP和SDDP应用Friedman测试[13]的结果。表4显示,WL和FCWSEO在所有对比方法中性能最好,FCOSA_LG和OLMOACO两个算法并列排在第三,WSE算法排在最后。

      表 4  当β=0.70,时暴雨灾害主题下各种主题爬虫方法的Friedman ranks比较

      算法 Accuracy LP ARDP SDDP Average
      WSE 6 6 5 5 5.5
      On-ITS 5 5 4 6 5.0
      FCOSA_LG 3 3 3 3 3.0
      OLMOACO 4 4 2 2 3.0
      FCWSEO 2 2 1 4 2.25
      WL 1 1 6 1 2.25

      针对台风灾害主题,设置网页主题相关度阈值β=0.67,本文实现了基于WL抽样的主题爬虫算法,并与文献中的BFS[25]、OPS[24]、模拟退火算法(simulated annealing, SA)[28]、网页空间进化算法(WSE)[12]、结合本体和改进禁忌搜索策略的主题爬虫方法(On-ITS)[26]以及结合本体学习和多目标蚁群优化方法(OLMOACO) [14]进行了结果对比,评价指标包括Accuracy、LP、ARDP、SDDP、ARLP、SDLP和Time,如表5所示。由于文献中其他算法没有测试ARLP和SDLP两个评价指标,故在表中未给出相应的结果。本文给出这两个指标的结果供将来其他算法进行比较。

      表5可知,当DP=1 000和5 000时,WL方法在Accuracy、LP和SDDP上均取得最优结果,在ARDP上其结果略低于On-ITS。由于BFS不对链接进行相关性判断,所以其爬准率始终都很低;而OPS因仅接受相关度最高的链接,易使爬虫陷入局部最优,爬准率逐渐降低;SA根据一定的概率选择主题不相关的网页,从而避免了陷入局部最优,在Accuracy、LP、ARDP、SDDP这4个评价指标上,其结果均优于BFS和OPS方法,但由于该算法主题描述不够准确,其结果劣于其他几种算法。当DP=10 000时,WL方法在Accuracy、LP上取得最优结果,在ARDP上略低于On-ITS方法,在SDDP上低于OLMOACO和On-ITS两种方法。当DP=15 000时,WL方法在Accuracy、LP上的优势继续保持,最终爬准率稳定在87%左右,而BFS、OPS、SA、WSE、On-ITS和OLMOACO方法的爬准率分别为4.7%、8.3%、35.8%、70.4%、82.0%和75.0%。在ARDP指标上,On-ITS的优势保持,而在SDDP指标上,OLMOACO的优势也继续保持。在运行时间上,当下载15 000个网页时,本文WL方法比BFS、OPS、SA、WSE、On-ITS和OLMOACO算法的运行时间明显减少或相当。为综合考察各种算法在台风灾害主题的爬虫效果,表6给出了7种方法在DP=15 000时应用Friedman测试[13]4个典型指标的结果。表6显示,WL方法在Accuracy、LP指标上均排在第一位,在ARDP和SDDP指标上均排在第二位。综合来看,WL方法具有最小的平均Ranks值(Average=1.5),是所有对比方法中性能最好的方法,其余6种算法按平均Ranks值从高到低排序依次是On-ITS、OLMOACO、WSE、SA、OPS和BFS。

      表 5  台风灾害主题下各种主题爬虫算法在不同爬行阶段实验结果比较

      DP算法AccuracyLPARDPSDDPARLPSDLPTime/h
      1000BFS0.092920.2310.221
      OPS0.3913910.4320.283
      SA0.4144140.5510.212
      WSE0.5715710.6720.123
      On-ITS0.7077070.8110.152
      OLMOACO0.6256250.6810.212
      WL0.7147140.7010.1210.7470.112
      5000BFS0.0713550.2490.222
      OPS0.24812400.4420.241
      SA0.49224600.5910.181
      WSE0.60630300.6640.134
      On-ITS0.80740350.8520.128
      OLMOACO0.76738350.7010.126
      WL0.86843380.7030.1080.7210.104
      10000BFS0.0454480.2120.174
      OPS0.12412400.4310.172
      SA0.42242150.5520.169
      WSE0.70770690.6870.124
      On-ITS0.81281200.7810.112
      OLMOACO0.73773700.7000.088
      WL0.89389270.7010.1210.7230.098
      15000BFS0.0477050.2110.1848.5
      OPS0.08312440.4360.1449.1
      SA0.35853700.5330.16011.1
      WSE0.704105600.6840.12712.2
      On-ITS0.820123000.7920.12313.2
      OLMOACO0.750112500.7000.07515.0
      WL0.873130950.7020.0990.7120.0958.2

      表 6  台风灾害主题下7种主题爬虫算法的Friedman ranks比较

      算法 Accuracy LP ARDP SDDP Average
      BFS 7 7 7 7 7
      OPS 6 6 6 5 5.75
      SA 5 5 5 6 5.25
      WSE 4 4 4 4 4.0
      On-ITS 2 2 1 3 2.0
      OLMOACO 3 3 3 1 2.5
      WL 1 1 2 2 1.5
    • 本文提出一种基于Wang−Landau抽样的主题爬行方法。该方法改进了传统主题爬虫因缺乏结合历史爬行经验而难以对爬行路径进行修正的缺陷,避免了爬虫过早陷入局部最优的问题。WL抽样算法根据直方图函数和概率密度函数获取当前网页搜索过程中的统计经验,指导爬虫以一定概率接受目标链接,决定爬虫下一步的搜索方向。同时,考虑到互联网中相关网页大量聚集于具有相同域名站点的特点,本文基于区域竞争策略自适应地生成候选目标链接,以供WL算法抽样选择。实验结果表明,本文提出算法可显著提升爬虫的爬准率,在所有下载网页主题相关度的标准差方面也具有优势。因此,WL方法是一种有效的主题爬虫方法。

参考文献 (28)

目录

    /

    返回文章
    返回