网页抽取技术和算法

本贴最后更新于 2434 天前,其中的信息可能已经时移世易

网页抽取技术和算法,持续更新。本文由 WebCollector 提供,转载请标明出处。

目录:


一. 网页抽取简介

网页抽取在大多数情况下,指提取网页中的结构化数据。网页抽取技术近十几年方法和工具变化都较快。

常见的网页抽取方法有 :

  • 基于正则表达式的网页抽取
  • 基于 CSS 选择器的网页抽取
  • 基于 XPATH 的网页抽取
  • 基于机器学习的网页抽取

由于 CSS 选择器和 XPATH 都是网页 DOM 树的特征,切较为相似,本教程不介绍基于 XPATH 的网页抽取。本文会着重介绍基于机器学习的网页抽取。


二. 基于正则表达式的网页抽取

利用正则表达式进行网页抽取,是在 html 源码的基础上做字符串级别的检索。要详细了解如何利用正则表达式进行网页抽取,只要了解正则表达式的基本用法即可,与网页特征无关。

基于正则表达式的网页抽取有下面几个缺点:

  • 正则表达式不直观,维护较为困难
  • 对于复杂的页面,正则规则编写较为复杂
  • 正则表达式是字符串级别的信息检索,并没有利用网页的特征(例如 DOM 树中的 CSS 选择器或 XPATH)

由于上面这些缺点,我们不推荐使用正则表达式进行网页抽取。因此这里我们只举一个简单的例子演示正则抽取。

原网页为:

<html>
    <body>
        <h2>(标题)此内容不要被抽取</h2>
        <div class="main">
            (正文)此内容要被抽取
        </div>
        <div class="foot">
            (页脚)此内容不要被抽取
        </div>
    </body>
</html> 

在 html 中我们描述了待抽取的内容。

  String html="<html><body>" +
                "<h2>(标题)此内容不要被抽取</h2>" +
                "<div class=\"main\">(正文)此内容要被抽取</div>" +
                "<div class=\"foot\">(页脚)此内容不要被抽取</div>" +
                "</body></html>";

        //正则表达式中的点(.)代表任意字符,星号(*)代表出现任意次,
        //因此.*表示任意字符串(包括空字符串)
        //.*?中的问号(?)表示.*(任意字符串)的长度尽可能短,
        //如果没有这个限制,抽取结果将变为:
        //(正文)此内容要被抽取</div><div class="foot">(页
        //脚)此内容不要被抽取
        Pattern pattern=Pattern.compile("<div class=\"main\">(.*?)</div>");

        if(matcher.find()){
            //正则表达式里的括号代表group,group(0)代表整个正则表
            //达式匹配的内容,group(n)代表第n个括号中的内容
            System.out.println("抽取结果:"+matcher.group(1));
        }else{
            System.out.println("无抽取结果");
        }

对于结构复杂的网页,正则表达式的设计往往较为困难,上面例子中

xxxxx

包含的是纯文本,但如果 div 中也包含标签,上面的正则表达式就不适用了。例如:

<html>
    <body>
        <h2>xxxxxx</h2>
        <div class="main">
            <p>xxxxx</p>
            <div>xxxxxx</div>
            <p>xxxxxxxx</p> 
        </div>
        <div class="foot">
            xxxxxx
        </div>
    </body>
</html> 

如果仍使用 (.*?) 作为正则表达式抽取,抽取结果会变为 xxxxxxxxxxx,这时就需要重新设计正则表达式,例如 (.*?)\s*(程序里,双引号和 \ 之前要加 \ 进行转义。


三. 基于 CSS 选择器的网页抽取

浏览器在收到服务器返回的 html 源码后,会将网页解析为 DOM 树。CSS 选择器(CSS Selector)是基于 DOM 树的特征,被广泛用于网页抽取。目前最流行的网页抽取组件 Jsoup(Java)和 BeautifulSoup(Python)都是基于 CSS 选择器的。

对于上面的例子:

<html>
    <body>
        <h2>(标题)此内容不要被抽取</h2>
        <div class="main">
            (正文)此内容要被抽取
        </div>
        <div class="foot">
            (页脚)此内容不要被抽取
        </div>
    </body>
</html> 

使用 CSS 选择器将大大提升代码的可读性:

 public static void cssExtract() {
        String html="<html><body>" +
                "<h2>(标题)此内容不要被抽取</h2>" +
                "<div class=\"main\">(正文)此内容要被抽取</div>" +
                "<div class=\"foot\">(页脚)此内容不要被抽取</div>" +
                "</body></html>";

        //Jsoup中的Document类表示网页的DOM树
        Document doc= Jsoup.parse(html);

        //利用select方法获取所有满足css选择器的Element集合
        // (实际是一个Elements类型的对象)
        //由于在本网页的结构中,只会有一个Element满足条件
        // 因此只要返回集合中的第一个Element即可
        Element main=doc.select("div[class=main]").first();

        //main是一个Element对象,这里main对应了网页中
        //的<div class="main">(正文)此内容要被抽取</div>
        //我们调用Element的text()方法即可提取中间的文字
        if(main!=null){
            System.out.println("抽取结果:"+main.text());
        }else{
            System.out.println("无抽取结果");
        }

    }

CSS 选择器有标准的规范,但 Jsoup(Java)和 BeautifulSoup(Python)这些组件并没有完全按照规范实现 CSS 选择器。因此在使用每种组件之前,最好阅读一下组件文档中对于 CSS 选择器的描述。

Jsoup 对于 CSS 选择器实现较好,如希望了解 CSS 选择器的使用,建议阅读 Jsoup 的 CSS 选择器规范文档

浏览器中的 javascript 是直接支持 CSS 选择器的,如果电脑里装有 firefox 或者 chrome,打开浏览器,按 F12(调出开发者界面),随便打开一个网页,选择其中的控制台(Console)标签页,在 Console 里输入

document.querySelectorAll("a")

回车后,发现输出了页面中所有的超链接,document.querySelectorAll(CSS选择器) 获取页面中所有满足 CSS 选择器的元素,放到一个数组中返回。
如果只希望获取第一个满足 CSS 选择器的元素,可以使用 document.querySelector(CSS选择器) 这个方法。
浏览器 js 中的 CSS 选择器与 Jsoup(Java)和 BeautifulSoup(Python)中实现的 CSS 选择器有细微差别,不过大体相同。


四. 基于机器学习的网页抽取

基于正则或 CSS 选择器(或 xpath)的网页抽取都基于属于基于包装器(wrapper)的网页抽取,这类抽取算法的通病就在于,对于不同结构的网页,要制定不同的抽取规则。如果一个舆情系统需要监控 10000 个异构网站,就需要编写并维护 10000 套抽取规则。从 2000 年左右就开始有人研究如何用机器学习的方法,让程序在不需要人工制定规则的情况下从网页中提取所需的信息。

从目前的科研成果看,基于机器学习的网页抽取的重心偏向于新闻网页内容自动抽取,即输入一个新闻网页,程序可以自动输出新闻的标题、正文、时间等信息。新闻、博客、百科类网站包含的结构化数据较为单一,基本都满足{标题,时间,正文}这种结构,抽取目标很明确,机器学习算法也较好设计。但电商、求职等类型的网页中包含的结构化数据非常复杂,有些还有嵌套,并没有统一的抽取目标,针对这类页面设计机器学习抽取算法难度较大。

本节主要描述如何设计机器学习算法抽取新闻、博客、百科等网站中的正文信息,后面简称为网页正文抽取(Content Extraction)。

基于机器学习的网页抽取算法大致可以分为以下几类:

三类算法中,第一类算法是最好实现的,也是效果最好的。

我们简单描述一下三类算法,如果你只是希望在工程中使用这些算法,只要了解第一类算法即可。

下面会提到一些论文,但请不要根据论文里自己的实验数据来判断算法的好坏,很多算法面向早期网页设计(即以表格为框架的网页),还有一些算法的实验数据集覆盖面较窄。有条件最好自己对这些算法进行评测。


4.1 基于启发式规则和无监督学习的网页抽取算法

基于启发式规则和无监督学习的网页抽取算法(第一类算法)是目前最简单,也是效果最好的方法。且其具有较高的通用性,即算法往往在不同语种、不同结构的网页上都有效。

早期的这类算法大多数没有将网页解析为 DOM 树,而是将网页解析为一个 token 序列,例如对于下面这段 html 源码:

<body>
    <div>广告...(8字)</div>
    <div class="main">正文...(500字)</div>
    <div class="foot">页脚...(6字)</div>
</body>

程序将其转换为 token 序列:

标签(body),标签(div),文本,文本....(8次),标签(/div),标签(div),文本,文本...(500次),标签(/div),标签(div),文本,文本...(6次),标签(/div),标签(/body)

早期有一种 MSS 算法(Maximum Subsequence Segmentation)以 token 序列为基础,算法有多个版本,其中一个版本为 token 序列中的每一个 token 赋予一个分数,打分规则如下:

  • 一个标签给-3.25 分
  • 一个文本给 1 分

根据打分规则和上面的 token 序列,我们可以获取一个分数序列:

-3.25,-3.25,1,1,1...(8次),-3.25,-3.25,1,1,1...(500次),-3.25,-3.25,1,1,1...(6次),-3.25,-3.25

MSS 算法认为,找出 token 序列中的一个子序列,使得这个子序列中 token 对应的分数总和达到最大,则这个子序列就是网页中的正文。从另一个角度来理解这个规则,即从 html 源码字符串中找出一个子序列,这个子序列应该尽量包含较多的文本和较少的标签,因为算法中给标签赋予了绝对值较大的负分(-3.25),为文本赋予了较小的正分(1)。

如何从分数序列中找出总和最大的子序列可以用动态规划很好地解决,这里就不给出详细算法,有兴趣可以参考《Extracting Article Text from the Web with Maximum Subsequence Segmentation》这篇论文,MSS 算法的效果并不好,但本文认为它可以代表早期的很多算法。

MSS 还有其他的版本,我们上面说算法给标签和文本分别赋予-3.25 和 1 分,这是固定值,还有一个版本的 MSS(也在论文中)利用朴素贝叶斯的方法为标签和文本计算分数。虽然这个版本的 MSS 效果有一定的提升,但仍不理想。

无监督学习在第一类算法中也起到重要作用。很多算法利用聚类的方法,将网页的正文和非正文自动分为 2 类。例如在《CETR - Content Extraction via Tag Ratios》算法中,网页被切分为多行文本,算法为每行文本计算 2 个特征,分别是下图中的横轴和纵轴,红色椭圆中的单元(行),大多数是网页正文,而绿色椭圆中包含的单元(行),大多数是非正文,使用 k-means 等聚类方法,就可以很好地将正文和非正文分为两类,然后再设计一些启发式算法,即可区分两类中哪一类是正文,哪一类是非正文。

早期的算法往往将 token 序列、字符序列作为计算特征的单元,从某种意义来说,这破坏了网页的结构,也没有充分利用网页的特征。在后来的算法中,很多使用 DOM 树的 Node 作为特征计算的基本单元,例如《Web news extraction via path ratios》、《Dom based content extraction via text density》,这些算法仍然是利用启发式规则和无监督学习,由于使用 DOM 树的 Node 作为特征计算的基本单元,使得算法可以获取到更好、更多的特征,因此可以设计更好的启发式规则和无监督学习算法,这些算法在抽取效果上,往往远高于前面所述的算法。由于在抽取时使用 DOM 树的 Node 作为单元,算法也可以较容易地保留正文的结构(主要是为了保持网页中正文的排版)。

我们在 WebCollector(1.12 版本开始)中,实现了一种第一类算法,可以到官网直接下载源码使用。


4.2 基于分类器的网页抽取算法(第二类机器学习抽取算法)

实现基于分类器的网页抽取算法(第二类算法),大致流程如下:

  • 找几千个网页作为训练集,对网页的正文和非正文(即需要抽取和不需要抽取的部分)进行人工标注。
  • 设计特征。例如一些算法将 DOM 树的标签类型(div,p,body 等)作为特征之一(当然这是一个不推荐使用的特征)。
  • 选择合适的分类器,利用特征进行训练。

对于网页抽取,特征的设计是第一位的,具体使用什么分类器有时候并不是那么重要。在使用相同特征的情况下,使用决策树、SVM、神经网络等不同的分类器不一定对抽取效果造成太大的影响。

从工程的角度来说,流程中的第一步和第二步都是较为困难的。训练集的选择也很有讲究,要保证在选取的数据集中网页结构的多样性。例如现在比较流行的正文结构为:

<div>
    <p>xxxx</p>
    <p>xxxxxxxx</p>
    <span>xxx</span>
    <p>xxxxx</p>
    <p>xxxx</p>
</div>

如果训练集中只有五六个网站的页面,很有可能这些网站的正文都是上面这种结构,而恰好在特征设计中,有两个特征是:

  • 节点标签类型(div,p,body 等)
  • 孩子节点标签类型频数(即孩子节点中,div 有几个,p 有几个…)

假设使用决策树作为分类器,最后的训练出的模型很可能是:

如果一个节点的标签类型为div,且其孩子节点中标签为p的节点超过3个,则这个节点对应网页的正文。

虽然这个模型在训练数据集上可以达到较好的抽取效果,但显而易见,有很多网站不满足这个规则。因此训练集的选择,对抽取算法的效果有很大的影响。

网页设计的风格一致在变,早期的网页往往利用表格(table)构建整个网页的框架,现在的网页喜欢用 div 构建网页的框架。如果希望抽取算法能够覆盖较长的时间段,在特征设计时,就要尽量选用那些不易变化的特征。标签类型是一个很容易变化的特征,随着网页设计风格的变化而变化,因此前面提到,非常不建议使用标签类型作为训练特征。

上面说的基于分类器的网页抽取算法,属于 eager learning,即算法通过训练集产生了模型(如决策树模型、神经网络模型等)。与之对应的 lazy learning,即事先不通过训练集产生模型的算法,比较有名的 KNN 就是属于 lazy learning。

一些抽取算法借助 KNN 来选择抽取算法,可能听起来有些绕,这里解释一下。假设有 2 种抽取算法 A、B,有 3 个网站 site1,site2,site3。2 种算法在 3 个网站上的抽取效果(这里用 0%-100% 的一个数表示,越大说明越好)如下:

网站 A 算法抽取效果 B 算法抽取效果
site1 90% 70%
site2 80% 85%
site3 60% 87%

可以看出来,在 site1 上,A 算法的抽取效果比 B 好,在 site2 和 site3 上,B 算法的抽取效果较好。在实际中,这种情况很常见。所以有些人就希望设计一个分类器,这个分类器不是用来分类正文和非正文,而是用来帮助选择抽取算法。例如在这个例子中,分类器在我们对 site1 中网页进行抽取时,应该告诉我们使用 A 算法可以获得更好的效果。

举个形象的例子,A 算法在政府类网站上抽取效果较好,B 算法在互联网新闻网站上抽取效果较好。那么当我对政府类网站进行抽取时,分类器应该帮我选择 A 算法。

这个分类器的实现,可以借助 KNN 算法。事先需要准备一个数据集,数据集中有多个站点的网页,同时需要维护一张表,表中告诉我们在每个站点上,不同抽取算法的抽取效果(实际上只要知道在每个站点上,哪个算法抽取效果最好即可)。当遇到一个待抽取的网页,我们将网页和数据集中所有网页对比(效率很低),找出最相似的 K 个网页,然后看着 K 个网页中,哪个站点的网页最多(例如 k=7,其中有 6 个网页都是来自 CSDN 新闻),那么我们就选择这个站点上效果最好的算法,对这个未知网页进行抽取。


4.3 基于网页模板自动生成的网页抽取算法

基于网页模板自动生成的网页抽取算法(第三类算法)有很多种。这里例举一种。在《URL Tree: Efficient Unsupervised Content Extraction from Streams of Web Documents》中,用多个相同结构页面(通过 URL 判断)的对比,找出其中异同,页面间的共性的部分是非正文,页面间差别较大的部分有可能是正文。这个很好理解,例如在一些网站中,所有的网页页脚都相同,都是备案信息或者版权申明之类的,这是页面之间的共性,因此算法认为这部分是非正文。而不同网页的正文往往是不同的,因此算法识别出正文页较容易。这种算法往往并不是针对单个网页作正文抽取,而是收集大量同构网页后,对多个网页同时进行抽取。也就是说,并不是输入一个网页就可以实时进行抽取。

注:本文尚在更新中。本文由 WebCollector 提供,转载请标明出处。

  • 爬虫

    网络爬虫(Spider、Crawler),是一种按照一定的规则,自动地抓取万维网信息的程序。

    106 引用 • 275 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...