网页抽取技术和算法

　　网页抽取技术和算法

　　基于机器学习的网页抽取

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

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

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

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

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

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

　　下面会提及一些论文，但请不要按照论文里自己的实验数据来判定算法的优劣，很多算法面向初期网页设计（即以表格为框架的网页），还有一些算法的实验数据集覆盖面较窄。有条件最好自己对这种算法进行评测。

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

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

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

　　

广告...(8字)

正文...(500字)

页脚...(6字)

　　程序将其转换为token序列：

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

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

　　根据打分规则和里面的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版本开始)中，实现了一种第一类算法，可以到官网直接下载源码使用。

　　2. 基于分类器的网页抽取算法（第二类机器学习抽取算法）

　　实现基于分类器的网页抽取算法（第二类算法），大致流程如下：

　　对于网页抽取，特征的设计是第一位的，具体使用哪些分类器有时候并不是那么重要。在使用相同特点的情况下，使用决策树、SVM、神经网路等不同的分类器不一定对抽取疗效导致很大的影响。

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

　　

xxxx

xxxxxxxx

xxx

xxxxx

xxxx

　　如果训练集中只有五六个网站的页面，很有可能这种网站的正文都是里面这些结构，而刚好在特点设计中，有两个特点是：

　　假设使用决策树作为分类器，最后的训练出的模型太可能是：

　　如果一个节点的标签类型为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新闻）,那么我们就选择这个站点上疗效最好的算法，对这个未知网页进行抽取。

　　3 .基于网页模板手动生成的网页抽取算法

　　基于网页模板手动生成的网页抽取算法（第三类算法）有很多种。这里列举一种。在《URL Tree: Efficient Unsupervised Content Extraction from Streams of Web Documents》中，用多个相同结构页面（通过URL判定）的对比，找出其中优缺，页面间的共性的部份是非正文，页面间差异较大的部份有可能是正文。这个挺好理解，例如在一些网站中，所有的网页脚注都相同，都是备案信息或则版权声明之类的，这是页面之间的共性，因此算法觉得这部份是非正文。而不同网页的正文常常是不同的，因此算法辨识出正文页较容易。这种算法常常并不是针对单个网页作正文抽取，而是搜集大量同构网页后，对多个网页同时进行抽取。也就是说，并不是输入一个网页就可以实时进行抽取。