基于贝叶斯分类器的主题爬虫研究

减小字体 增大字体 作者:邹永斌 陈兴蜀 王文贤  来源:www.zhonghualunwen.com  发布时间:2009-10-13 00:29:56

  0引言
  
  随着互联网上资源的几何级数增长,对网络信息的采集面临着索引规模、更新速度和个性化需求等多方面的挑战[1]。针对这种情况,目前对主题爬虫的研究渐渐成为网络数据挖掘领域最热门的方向之一。主题爬虫是一种特殊的爬虫,其主要目标是在有限的时间与网络带宽限制下尽可能多地采集与指定主题相关的高质量网页,忽略与主题无关或低质量的网页。因此,实现主题爬虫的关键在于如何判断网页与主题的相关性。判断网页的主题相关度主要有两种方式,即基于链接分析和基于内容分析。基于链接分析的方法基于网页之间的链接来对其有直接或间接链接关系的对象作出评价。PageRank算法[2]和HITS算法[3]是最常见的链接分析算法,两者都是通过对网页间链接度的递归和规范化计算得到每一个网页的重要度评价。目前的主题爬虫大多采用基于链接分析的方法实现,实验表明,这种方法更适合发现权威网页,而不适合发现主题资源,而且其计算量一般都很大,严重影响了爬行器的爬行速度。
  基于网页内容的分析方法指的是利用网页内容(文本、数据等资源)特征进行的网页评价方法。这种方法的核心在于文本聚类算法的实现,常用的聚类算法有朴素贝叶斯、支持向量机(SVM)以及神经网络等。其中,朴素贝叶斯的分类精度较高,且运行速度较快,能够很好地满足主题爬虫对速度和准确度的要求。本文通过对网络爬虫与聚类算法的研究,实现了一个基于朴素贝叶斯分类器的主题爬虫。经实验表明,爬虫的运行性能良好。
  
  1 系统设计
  
  主题爬虫是对普通爬虫的扩展,它在普通爬虫的基础上增加了特征提取和相关度分析模块。特征提取模块提取页面的特征并将其表示成一个带权的向量,而相关度分析模块则将页面的特征与目标主题进行相关度分析,并根据分析结果确定链接的优先级。优先级高的链接将被优先处理,从而能够保证与主题的相关度最高的高质量页面能够在短时间内被获取。
  主题爬虫的运行过程(图1)如下:a)输入需要爬行的主题和起始站点;b)相关度分析模块对输入的主题进行分析,得到目标主题的向量表示;c)爬虫从URL队列中获取最佳站点地址并下载相应页面;d)分析页面,提取出其中的链接与链接所在的上下文;e)提取链接上下文的特征,得到其带权的向量表示;f)相关度分析模块计算链接上下文与目标主题的相关度,并根据相关度大小计算链接的优先级;g)跳至c)重新开始循环。
  1.1 URL队列
  URL队列是爬虫的待执行任务列表,它保存了未访问页面的URL。URL队列的底层是由动态数组实现的,数组的元素根据未访问URL的估计优先级来进行排序,优先级相同的未访问URL则根据发现的顺序进行排序。如果所有的URL优先级相同或者没有优先级,URL队列的默认实现采用的是FIFO队列,而广度优先爬虫则仅仅是本文所实现的最佳优先爬虫的一种特例。
  每次爬行一个页面时,优先级最高的URL从队首获得。该URL所对应的页面被下载后,页面中的链接将被提取出来并根据启发式算法计算其优先级,然后加入到URL队列的优先级队列中。为了防止URL队列中出现重复的链接,还另外保存了一个hash表以供查询,如图2所示。
  根据可用的内存数量可以决定URL队列的最大容量。由于目前的PC普遍拥有大容量内存,保存10万条以上URL的URL队列并不少见,本文在所有实验中采用的URL队列大小均为10万。在爬行过程中URL队列会很快被填满,假设每个页面有7条链接,那么在爬行完成1万个页面时,URL队列中大约会有6万条URL[4]。如果链接的数量超过了URL队列的最大容量(max),URL队列中仅保存max个优先级最高的URL,其余的URL将被忽略。如果爬虫发现当它需要下一个URL时URL队列为空,则爬行过程中止。
  如果存在有大量URL指向同一个网页的情况,则爬虫很可能被陷入[5]。缓解这种问题的一种方法是限制爬虫可以从一个域名中获取到的网页数量。在本文的解决方案中,URL队列保证对于所爬行的k(如100)个页面均来自k个不同的域名。这种方法的优点是使爬虫给网站服务器造成的负载被大幅减小,而且所爬行的页面内容更加多样化。
     1.2 爬行历史
  爬行历史是一个已经被爬虫下载过的URL列表,其中还包括了下载URL的时间,它展示了一个页面到另一个页面的爬行路径。当URL所指向的页面被下载后,该URL将被加入到爬行历史中。爬行历史可以被用来进行爬行后的分析,例如,可以为每个页面关联一个值,从而表示一些特殊事件(如发现了一些特别的资源)。为了在爬行完成后可以利用爬行历史进行数据分析,爬行历史在爬行完成时将被保存在磁盘上。
  每当一个页面被下载时,它可以被缓存以供进一步处理。本文实现了一个页面仓库用来将爬行过的页面保存成独立的文件,为此,每一个页面需要映射到一个惟一的文件名。通过使用一个低碰撞率的hash函数(为了确保文件名惟一),将页面的URL映射成一个字符串,而该字符串就作为保存页面的文件名。本文采用MD5算法来为每个URL生成一个128 bit的hash码,该128 bit的hash值被转换成16进制的32个字符,从而得到文件名,如http://www.scu.edu.cn/的内容被保存在名为355bd40a1cffbb871d1fce0048a19972的文件中。页面仓库还可以被用来检查一个URL所指向的文件是否已经存在。如果页面仓库缓存了以前爬行的页面,这些页面没有必要重新从网络

[1] [2] [3]  下一页

Tags:

作者:邹永斌 陈兴蜀 王文贤
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论