信息采集 参考：W.Bruce Croft等著，刘挺等译. 搜索引擎-信息检索实践. 机械工业出版社，2010.

Presentation on theme: "信息采集 参考：W.Bruce Croft等著，刘挺等译. 搜索引擎-信息检索实践. 机械工业出版社，2010."— Presentation transcript:

1 信息采集 参考：W.Bruce Croft等著，刘挺等译. 搜索引擎-信息检索实践. 机械工业出版社，2010

2 主要内容 信息采集(网络爬虫，Crawler) 重复检测 去除噪声

3 网络爬虫 困难： 规模：网页采集，存在很多特殊问题，最大的问题是互联网的规模。目前“至少”(没人知道多少)有上百亿网页
不受控：不知道一个网站有多少页面，更不知道有哪些页面，有些页面其创建者不希望搜索引擎获取，至少不能频繁地获取以影响网站正常服务 深网：有些数据需要填写表单才能获取

4 网络爬虫 URL(uniform resource locator) 访问网页的过程 组成：协议方案，主机名，资源名
例： 访问网页的过程 域名解析：从域名到IP地址 连接服务器：客户端程序连接IP地址所对应的服务器 发送请求：客户端发送请求(如HTTP请求)到服务器，请求页面 返回信息：服务器先发一个简单的头部信息，再将文件的内容返回给客户端 关闭连接。

5 网络爬虫 从种子集合开始，将种子集合中的URL添加到请求队列。从请求队列中取出 URL，抓取网页，并对网页进行解析，从中提取链接，将有用的URL添加到请求队列中。重复该过程直到队列为空或存储空间用完为止。

6 信息采集的概念 主要是指通过Web页面之间的链接关系从Web上自动获取页面信息,并且随着链接不断向所需要的Web页面扩展的过程，信息采集系统也常常称为Robot, Spider, Crawler等等 信息采集是搜索引擎获得数据来源的过程，地位相当重要 信息采集的目标：快速获得高质量的网页 信息采集是一项十分繁杂和庞大的工程 不同的协议 不同的网络情况 时效性的要求 网页质量的要求 实际上是图的遍历过程 通过种子页面或站点(Seed)，获取更多的链接，将它们作为下一步种子，循环 这个过程一般永远不会结束！

7 信息采集的基本结构 这个部件主要给待采集的URL排序，并根据一定的策略向协议处理器分配URL
主要通过各种Web协议来完成数据的采集。一般来说协议包括HTTP、FTP、Gopher以及BBS 信息采集的基本结构 内容包括已采集页面的Meta信息、Anchor信息、页面的标题、页面的摘要等。获取它们的主要目的是力图在没有对页面内容语义信息进行理解的前提下，尽可能多的挖掘meta、结构等的语义信息，来为从这些页面中提取出来的URL的好坏，给出一个度量。 语义信息解析就是指对文本内容建立简单的索引

8 采集的遍历算法 宽度优先vs. 深度优先 网站采集vs. 全局URL采集 宽度优先：先采集完同一层的网页，再采集下一层网页
深度优先：先沿一条路径采到叶节点，再从同层其他路径进行采集 有研究表明：宽度优先的方法得到的网页集合的重要性更好 网站采集vs. 全局URL采集 网站采集：一个网站一个网站采集 全局URL采集：将所有URL放入一个URL池，从中使用某种方法进行选择 网站采集在支持应用方面灵活性大一些，但是采集效率可能不如全局URL采集，通常的搜索引擎采用全局URL采集的方法。

9 采集网页的更新策略 定期重采：一段时间以后重新采集所有网页，全部采完以后替换原来的网页
增量采集：只按照某种策略采集那些可能新增、变化的网页，并删除那些已经不存在的网页 定期重采非常简单，但是浪费带宽，周期也长；增量采集可以节省带宽，网页更新周期相对较短，但是系统的复杂性增大。 Http协议有个称为HEAD的特殊请求，只返回头信息而不是全部页面，方便检查网页是否更新过。

10 采集网页的速度保证措施 本地DNS解析：把DNS解析任务放在本地机上，即提交的地址都是解析后的IP地址。 多机分布式并行 单机多程序并行
局域网联接多机进行采集并行 广域网分布式采集 单机多程序并行 多进程并行 多线程并行

11 采集网页的质量保证措施 减少重复页面的采集 保证重要页面的高优先级 URL重复的检测和排除 内容重复的检测和排除 入度高的网页相对重要
对于完全重复的网页：MD5算法为每个网页生成一个128位的信息摘要 对于近似网页(Broder,1997)：先规范化为词条数据流，再提取出子字符串(shingle)，比较两个网页中shingle的重叠程度。为每个shigle计算哈希值（64位）。为保证效率，删除其中的大部分shingle（如所有哈希值模m后不为0的，m=25适合web数据） 保证重要页面的高优先级 入度高的网页相对重要 URL浅的网页相对重要 含有被别人广泛映像的内容的网页重要

12 采集中的“礼貌”问题 遵守网站上发布的Robot.txt采集限制协议 文档信息源
User-agent: * Disallow: /private/ Disallow: /other/ Allow: /other/public/ User-agent: FavoredCrawler (对这个爬虫有以下的规则) … Sitemap:… (网站地图：告诉爬虫网页的位置，更新信息等) 文档信息源 类似于网站地图，主要用于描述那是出版物等时间不敏感的资源。 采集时尽量不要太过密集地采集某个网站，这种密集访问类似于DoS攻击，导致普通用户正常浏览网站产生困难。有些网站会严密控制这种密集访问行为。

13 信息采集的研究趋势 基于主题的信息采集 深网数据采集 信息采集及抽取 采集某个领域的数据。选择种子、利用页面中的锚文本、页面分类
深层网络的规模是传统网络规模的100倍(估计) 三类： 私人站点：没有指向它的链接，或者需要进行注册 表单结果：向表单中填写数据后才能进入，如销售机票等 脚本页面：使用javascript，链接并不是以HTML语言给出，而是通过在浏览器中运行javascript生成。 信息采集及抽取 采集后提取结构化信息

14 重复检测 研究表明，在一个大型的信息采集系统中，30%的网页是和另外70%的网页完全重复或近似重复的。
也有估计认为，Web中大概有40%的网页和其他网页重复。 这些重复包括： 抄袭(plagiarism) 垃圾(spam) 镜像(mirror) 种类主要两类：完全重复、近似重复

15 重复检测 – 完全重复 相对简单，例如使用“检验和”(checksumming)技术 根据文档内容计算一个数值。最直接的就是文档中各字节的和
例如：一个含有文本“Tropical fish”的文件，检验和可以是其中各个词符的ASCII的和(包括空格)，即 F+…+68=508 含有相同文本的任意文档，它们会有相同的检验和。 也存在文本包含的字符相同，但顺序不同，计算的检验和也相同。因此，可以考虑更复杂的检验和函数，比如考虑字节出现的位置。

16 重复检测 – 近似重复 如何快速判断近似重复？ 对于有N个文档的集合，判断其中全部的近似重复文档需要文档两两比较，开销为O(N2)
将长文档用它的“指纹(fingerprint)”来表示，减少两文档比较时的开销。

17 重复检测 – 近似重复 指纹生成过程 对文档进行分词，删除不是词的内容，如标点、HTML标签、空格 将词组合成n-gram 选择其中的一些n-gram，用于表示该文档。通常不是随机地选择，因为从内容重复的D1和D2两个文档中随机选择n-gram，重复的可能性比较小。更有效的方法是从事先制订的字符组合中选择以这些字符开始的n-gram。这些n-gram就是指纹。 对被选择出来的n-gram进行散列，以提高检索效率，并减少文档大小。每个n-gram对应一个散列值。(选择n-gram也可根据散列值模P为0的原则来选择) 对散列后的指纹进行倒排索引。方便快速匹配。 对于一个文档，要找其近似重复文档，可以先生成该文档的指纹，再根据指纹查倒排索引。然后根据检索的结果判断重复的指纹数量占总数量的比例，做为文档的重复程度。 基于指纹的方法在效果上并不如基于词表的相似度计算(余弦相似度)，但效率更高。

18 重复检测 – 近似重复 Simhash(Charikar, 2002) Simhash指纹生成过程
吸取了基于词的相似度计算的优点，以及基于散列的指纹技术的高效性。 相似的文档具有相似的散列值。 Simhash指纹生成过程 利用具有权值的特征集合表示文档 对每个词，生成b位的散列值 在b维向量V(文档中全部词，每个词b维)中，分别对每维计算：如果相应位的散列值为1，对相应的特征权值做加法，否则，做减法 所有词处理完后，如果向量中的第i维为正，则最终的b位指纹中第i位为1，否则为0

19 重复检测 – 近似重复 Simhash举例 原始文档：Tropical fish include fish found in tropical environments around the world, including both freshweat and salt water species. 对词加权后：tropical 2 , fish 2, include 1, found 1, environments 1, around 1, world 1, including 1, both 1, freshwater 1, salt 1, water 1, species 1 8位散列： 对权值求和 tropical … fish include found environments … around world including both freshwater salt water species 最终的8位指纹是：

20 重复检测 – 近似重复 Henzinger(2006)使用了基于大规模网页的评价方法评价simhash，他使用的指纹为384位。如果一个网页和另一个网页的simhash指纹中有多于372位是相同的，那么这两个网页就是近似网页。 研究表明，simhash指纹比n-gram指纹方法有更好的效果。 实验 中的simhash python 程序，基本思路如上所述。知道 全部文档的指纹，要比较与某文档d近似重复度最高的(或高于某阈值)的文档，还是要比较全部文档的指纹与d的指纹(做与运算即可)。 为了进一步提高效率，将b位进行分段并索引存储。对于文档d的指纹，首先分段，然后从索引中检索可能近似重复的文档，只与这些文档的指纹进行比较。

21 去除噪声 网页中经常包含文本、链接、图片等，真正的内容块所占的比例并不高，还有其它如广告、版权等信息。

22 去除噪声 基于标签分布(Finn, 2001) 基本思路：网页中主要内容部分的文本会比网页中附加(噪声)内容的文本中含有更少量的HTML标签
右图是 如何找到中间的平坦区域？

23 去除噪声 基于标签分布(Finn, 2001) 检测最大平坦区域 不足：
使用二进制位序列对网页进行表示，bn=1表示第n个词素(汉字、单词)是一个标签，否则bn=0。表示字体变化、标题和表格的标签可以忽略掉，即用0表示，因为它们已经是正文。 主要内容检测可以看成是一个优化问题，即最大化低于i和高于j的标签数量，以及在i和j中间的非标签词素的数量。 𝑛=0 𝑖−1 𝑏𝑛 + 𝑛=𝑖 𝑗 (1−𝑏𝑛) + 𝑛=𝑗+1 𝑁−1 𝑏𝑛 不足： 只有非内容块中文本词素的比例小于标签比例时，上述目标函数才起作用。当然，可以适当增加非标签词素的权重来调整 另外，不能处理网页中有分散的多个内容块的情况。(可以使用窗口来解决)

24 去除噪声 基于网页结构 DOM(文档对象模型)将网页表示为类似于树的结构，可以用来识别网页中的主要部分。
Gupta等(2003)提出一种方法，递归遍历DOM树，使用不同的过滤技术来删除和修改树中的节点，只留下内容部分。HTML中的图片、脚本等很容易用简单的过滤去掉，而复杂的过滤技术用于去除广告、链接等。 BeautifulSoup是python中用于解析网页的重要工具。 不足：复杂，只是根据格式而没考虑语义。例如，HTML中使用表格，有时只是为了网页的布局。解决方法是结合网页的布局和视觉特征。

25 基于视觉特征