转载

抓取学习笔记

知识图谱的很重要的原始数据来源还是来自于网站抓取的数据,网站抓取器就是我们常说的Spider。

在互联网上爬来爬去,发现链接,抓取网页,这就是Spider整天做的事情。听起来很简单,但是实际上是困难重重的。

Spider有两个核心任务:选链调度 和 网页抓取。

Spider面临的主要问题有:

  • 压力计算、控制、流量分配:
    • 如何提升对外抓取友好度,减少被封禁。如何评估网站可承受的压力。如何在多用户之间,多种不同的抓取需求之间进行流量分配。
  • 抓取流量有限,需要根据预测合理调度,使收益最大化:
    • 链接发现:需要预测优先CHK哪些页面可能发现更多更好的新链接。
    • 待抓分级:需要在抓取之前预测哪些待抓链接对应的网页质量更高,从而优先抓取。
    • 页面更新:需要预测哪些网页更可能发生了变化(或失效),哪些网页的变化更重要,从而优先CHK。
    • 这些预测通常需要基于对现有数据的挖掘统计,由已抓反馈待抓,由历史调度推测未来调度。在这个过程中会用到大规模数据挖掘,机器学习等方法。
  • 收录控制:互联网上有大量各种重复、垃圾信息,如果不加限制,我们的系统将很快被垃圾占领。需要判断网页的质量,挖掘网页的重复规律,在尽可能早的地方把垃圾和重复控制住。

1、抓取器(Crawler)

最简单的抓取器就是一个实现了HTTP协议的客户端:接收一系列URL,向网站发起抓取,输出一系列网页。但是在实际中,简单的HTTP抓取不能完全满足抓取需求。除了高性能、高并发外,还有如下需求:

  • 多抓取协议支持:目前主要是HTTP和HTTPS。
  • 多种资源类型:多文档、图片、视频。
  • 页面拼接:对内嵌frame页进行抓取拼接。
  • 页面跳转:跳转可以通过HTTP头、HTML meta标签静态实现,也可以通过javascript动态实现。前者容易识别,后者依赖javascript解析,很难精确做到。
  • 页面渲染:像浏览器一样执行javascript代码和css渲染,使输出网页看起来像在浏览器里看到的一样。

页面渲染功能的实现方案一把是基于chrome或者firefox内核实现,但有得必有失,这样会导致性能远差于简单的网页抓取器,并非所有网页都有这么复杂的渲染需求,可以让用户自己根据需要来选择。

另外,在这之前,还要能够保证不被网站封禁,比如控制抓取的频率、验证码破解、登录验证等。这些都是令人头疼的难题。

2、新链拓展

有了抓取器,给定一批链接,可以把网页抓回来。但从哪得到源源不断的链接以持续抓取呢?这就是新链拓展做的事情。

互联网拓朴是一个广泛连接的图,从一个小的核心网页集合出发(例如新浪,hao123),沿着链接可以找到互联网上绝大部分网页。新链拓展模块就是负责从网页上提取出新的链接。新提出的链接合并到老链接集合(原始链接称之为种子)中,从而使抓取可以持续,使爬虫的触角逐渐伸向全网,源源不断地得到新出现的网页链接。

通常情况下,链接是通过解析HTML树中的 <a> 标签得到的。但还有一些其它的提链方式:

  • 链接可能直接以纯文本的形式出现。需要抽取器从文本中正确地截取链接部分。
  • 链接可能由javascript脚本动态生成,甚至需要用户点击操作才能触发生成。这时候需要借助有页面渲染能力的抓取器来解决提链问题了。

另外,对于特定领域的抓取器,比如我们知识图谱,对于某个种子URL,拓展出来的新链是有要求的。例如从网易新闻的频道首页开始抓取,递归抓取(发现/拓展)新闻详情页。这一般通过正则表达式来描述新链拓展的规则。以上面的例子为例:

频道首页的URL格式为:http://news.163.com/domestic/,http://news.163.com/shehui/。所以其对应的正则表达式为:http://news.163.com/[a-z]*/。

新闻详情页的URL格式为:http://news.163.com/15/0630/16/ATCCTD9A00011229.html,http://news.163.com/15/0630/14/ATC89L110001124J.html。所以其对应的正则表达式为:http://news.163.com/[0-9] /[0-9] /[0-9] /. .html。

综上,如果我们想要创建一个全站抓取任务,从频道首页发现新闻详情页,则链接发现规则可以这样配:

入口页面正则:http://news.163.com/[a-z]*/

此入口页面允许的新链正则:http://news.163.com/[0-9] /[0-9] /[0-9] /. .html

那么解析器在分析频道首页时,发现的新链当中,符合新闻详情正则的链接都会被选取,放到种子库当中,供下轮调度使用。

页面解析器(抽取器)也只能针对某些pattern的URL进行页面抽取(通用的页面解析器,如新闻类型的一般准确率不高,很难满足抽取需求)。

3、链接库与网页库

可以持续抓取网页后,我们让这个系统自动跑下去。但是很快我们会发现链接和网页的数量迅速膨胀,简单的文件存储越来越慢,我们需要更高效的存储方式。怎么设计链接库和网页库的存储呢?

链接库的需求:

  • schema支持(定长、变长字段都有)
  • 批量读需求(选取链接)
  • 批量写需求(把新链接合并回链接库)
  • 随机读需求(小量)
  • 记录长度较小,差异不大(平均几百Byte,最大1KB以内)
  • 有大量read-modify-write需求(链接状态的改变需要参考上次的链接状态)

网页库的需求:

  • schema支持(定长、变长字段都有)
  • 批量读需求(建索引库)
  • 批量写需求(spider抓回来的网页入网页库)
  • 随机读需求(小量)
  • 记录长度较大,差异较大(平均几十KB,最大达到几MB级)

网页库数据量比较大,基本都是离线批量的读写应用(偏向于OLAP),所以业界通用做法是存放在HBase中。而对于链接库,则需要比较大量的随机大写,偏向于OLTP,所以DB(需要sharding)或者NoSQL(如ES)比较合适。

4、选链调度

经过源源不断的 网页抓取=>新链扩展 周期循环之后,链接库里面的种子会非常多,但是抓取器每天能够抓取的链接是有限的,这就产生了一个问题:这么多链接究竟应该选哪些来抓取呢?这就是spider调度策略做的事情。

TIPS商业搜索引擎,spider的链接库里会有几千亿链接,但是每天发起抓取的链接量仅能够有几十亿。

调度策略模型

1、广度有限

spider最原始、最基础的调度策略是广度优先。即:优先调度浅层链接。这里的深度并不是指URL的目录深度,而是链接从首页开始的follow深度(即常见的link_depth字段)。 这是符合一般人对网站的浏览习惯的。一般人从首页开始,通过导航链接,层层找到需要的内容。站长也会把一些重点推荐的内容或新内容放在首页或浅层栏目页上。而需要点击N多次才能发现的页面,一般用户很难找到,价值也不高。

2、链接分级

这个也是比较通用的做法,就是为每个种子分配权重(调度优先级),类似于操作系统的进程调度算法。

为了区分不同链接之间的优先级,spider选取时会对链接进行分级:

  • 先根据链接属性计算出权重
  • 再根据权重映射到级别
  • 选取时从高级别向低级别选取
  • 低级别有低保,保证不会被饿死
  • 同级别内随机选取

TIPS五种流量划分

我们希望每个站点上的链接可以按某种优先级排序。排好序后链接选取工作就极简单了,只要按顺序从高到低选即可。但我们发现并不是所有链接之间的优先级都是可比的。链接可以分成一些group,group内可比,group间不可比。

根据链接调度的需求,把链接分成五种流量类型:

  • 覆盖率CHK
  • 覆盖率GET
  • 时效性CHK
  • 时效性GET
  • 更新率CHK

这五种流量类型内部的链接优先级可直接比较,流量类型之间则不可比。流量类型之间的调度通过配比动态计算得到。

3、站点隔离选取

除了对链接根据流量类型进行group,为了体现站点之间的巨大差别,还可以考虑引入站点隔离选取机制。

在站点隔离选取机制下,linkbase按URL字典序(站点部分倒转)排列,相同站点的链接存储在一起。各个站点之间完全独立选取,方便各个站点进行独立的策略控制,避免了相互影响。

调度依赖的属性

链接调度模型定下后,关键是如何更好更快地获取、计算链接相关各种属性,以及尽快地把这些属性生效到线上,影响调度。

待抓链接可以拿到的属性

  • URL长相:有很多文章可以做。
    • 各种聚类:聚类后已抓链接的各种属性统计后都可以反馈到待抓
      • domain
      • stat-pattern
      • keyman-pattern
      • domain+anchor聚类
    • 首页/dir_depth,链接长度
    • 从URL上提取时间
  • 反链/anchor/fresh-pp/page_rank/微博转发
    • anchor-mine:根据anchor挖掘,对linkbase进行操作,对链接进行提权或降权。
  • 前链/link_depth/hub_depth
  • sobar访问
  • 推送链接的meta信息

已抓链接可以拿到的属性

  • 所有待抓链接的属性
  • 抓取反馈
    • 抓取状态:成功/失败,返回码
  • 单页面级特征
    • 页面价值:质量(有效性、丰富度、整洁度),受众
    • 页面类型:索引页/内容页,语义分类:新闻/小说/视频/博客...
    • 页面提取信息:正文、标题、链接、页面发布时间、结构化数据
  • 多页面特征
    • 页面价值:稀缺(重复度)
    • 贡献新链接能力
  • 时间维度特征
    • 抓取历史记录
    • 易变性/易死性
  • 建库反馈
    • 建库级别:vip/se/大度/时效性...
  • 线上反馈
    • 点击、展现

spider调度的目标就是根据这些属性,安排出最优的调度顺序,使用最少的流量,获取最大的收益。

以前数据挖掘模块往往把最终调权的数据直接生成好,灌入link库。但这里面有很多拍脑袋的阈值和人工决策树。机器学习引入调度排序后,会越来越倾向于数据挖掘只产出基础属性,把基础属性回灌到link库中。基础属性怎么用,由机器学习来决定。

一些重要的调度策略

1、待抓链接调度

  • 思路:使用机器学习的方法,根据待抓链接的属性,学习抓取后的页面价值。
  • 难点:
    • 已抓反馈待抓,选择合适的粒度
      • 不要太粗:区分度不够
      • 不要太细:样本数太少
      • 高内聚:对于待预测目标属性,聚类产生的粒度要高内聚。即:聚在一起的链接的目标属性应该接近。
      • 低耦合:不同的聚类之间,目标属性应该有区分度。
    • 提升各种属性的反馈速度
      • 反链、anchor、page_rank等需要反转和迭代的比较难做。架构需要考虑如何更好地支持。

2、索引页调度

索引页的价值在于发现新链接。那么它的价值就要按follow出来的后链进行评价,可以用"母凭子贵"来概括。具体如何评价呢?

  • 人无我有
    • 别人follow不出来的链接,我能follow出来。
  • 人有我精
    • 别人follow出来的链接质量平平,我follow出来的都是优质链接。
  • 人精我快
    • 大家都能follow出来的链接,我比别人抢先一步。

索引页分级主要由index-check模块完成。index-check模块根据link-pair产出的链接对信息,对索引页发现链接的能力进行评估,生成链接贡献度和强度谱数据。产出的索引页分级数据使用modlink回标到linkbase生效。

hubdig模块根据链接贡献度和强度谱数据进一步挖掘出hub页(高质量易变索引页)及hub页分级,以时效性CHK方式进行高频调度。

除此之外,通过pattern之间指向关系挖掘,也可以对索引页的分级产生影响。负责这项工作的模块叫link_uniq。 具体做法如下:

对于资源patternB,考察patternA对patternB的指向关系:patternA => patternB。定义四个衡量标准:

  • uniq度:指向关系中patternB链接集合uniq后数量 / 指向关系对总量
    • 衡量指向关系的重复程度。如果重复度高,意味着调度patternA的链接follow出patternB的链接大部分都是老链接。
  • 覆盖度:指向关系中patternB链接集合uniq后数量 / patternB收录链接总量
    • 衡量通过对patternA中链接的调度,可以发现patternB中多大比例的链接。
  • 贡献度:指向关系中patternB链接集合uniq后数量 / 指向关系中patternA链接集合uniq后数量
    • 衡量对patternA中链接的调度能否起到"四两拨千斤“的效果。
  • 有效度:指向关系中patternA链接集合uniq后数量 / patternA收录链接总量
    • 衡量此挖掘结果对于patternA是否具有统计意义。如果patternA中仅有少量链接follow出patternB,那反馈到全体patternA链接就是错误的。 link-uniq产出低价值指向数据,作用于effect,对中级别索引页进行降权。提升中级别索引页CHK有效性。

同时link-uniq还产出边框数据,作用于EC。用于辅助索引页识别(索引页识别主要看链接块面积,很重要的一点就是去除边框链接块的影响)。 边框的特点:

  • 同功能页面上,边框处于相同位置。边框对应的后链往往重复度很高,即uniq度很低。可以通过这种方式挖掘出每种pattern上的边框块。 但link-uniq挖掘非常耗时,历史上挖掘次数很少,因此产生的效果也不大。如何降低这种大型数据挖掘的成本,使之常态化运行,也是架构方需要考虑的重要问题。

3、更新率调度

有大量存量的内容页,更新哪些呢?主要取决于两点:

  • 变化的概率:变好 | 变差 | 变化
    • 网页特性本身的易变性:不同网页易变性不同。商品信息页,BBS页
    • 已CHK反馈待CHK:同类链接大量变化,可能意味着该链接也有变化
  • 更新的收益:
    • 是否在索引库,在哪个库中?
    • 是否有点击、展现等
    • 如果不在索引中,或者没有点击展现,那么即使不更新,影响也较小

具体排序策略:

  • 更新概率模型
    • 网页自身属性
    • 集合反馈属性
      • 定期pattern聚类挖掘网页变化情况
    • 机器学习:由以上属性计算出网页变化概率
  • 更新收益计算
    • 建库反馈网页在什么索引库中
    • 检索端点击、展现反馈
    • 不同收益给予不同权重
  • 综合计算CHK收益
    • 用(更新概率 * 更新收益)衡量CHK某链接的优先级

选链调度是整个spider最复杂的模块,有很多深度挖掘、机器学习的东东在里面。

原文  http://blog.arganzheng.me/posts/spider-study.html
正文到此结束
Loading...