搜索
第5章信息资源采集-网络爬虫与Mashup主要内容5.1网络爬虫5.2Mashup5.1网络爬虫5.1.1网络爬虫概述•网络爬虫是负责通过互联网自动抓取网页的系统程序，在抓取的过程中下载Web页面，再根据所得到页面内的超链接关系进一步实现页面抓取，通过不断地这样迭代动作，从而完成Web页面的采集工作。传统网络爬虫结构开始运行后,使用种子URL地址初始化抓取地址池,抓取地址池里的URL地址就是爬虫所要爬行的范围,然后判断任务是否终止,如果是,就直接停止抓取任务;如果不是,就从地址池中取出下一个URL,访问该地址所指向的页面,保存到磁盘上,然后解析网页中的超链接元素,提取出其中的uRL地址,将其添加到抓取地址池中,再返回判断任务是否终止的步骤,如此循环。传统网络爬虫结构存在的问题•传统的网络爬虫都不约而同的避开了网页内容的分析，而是将重点放在了网页的超链接上,这就不可避免的存在一个问题，就是爬虫所抓取的页面是不是用户在搜索时所关心的内容？•所以需要想办法来约束网络爬虫，约束的方法主要是在网络爬虫的爬行范围和抓取对象上实现。约束网络爬虫的方法•限制解析出来的URL地址添加到抓取地址池中，使得符合某种要求的地址才可添加到抓取地址池中；•调整抓取地址池中的URL抓取优先级来对将要抓取的地址进行排序，从而调整抓取网页的顺序。–深度优先–广度优先–最佳优先（1）广度优先算法•广度优先算法(Breadth-First-Search)是一种圆形搜索算法，也称为横向优先搜索。简单的说，就是将网站里的URL地址按照其目录结构分层，并生成一棵树，然后从树的根开始一层一层向下访问，也就是上一层URL比下一层的URL具有较高的抓取优先级。使用广度优先算法对此网站进行爬行访问，所得到的访问路径顺序将会是：访问路径1:A访问路径2:B一C一D访问路径3:E一F一G访问路径4:H一l一J访问路径5:K某网站层次结构广度优先算法存在的问题•如果网络爬虫采用广度优先算法对网站进行访问，它将访问很多不同的网站，具有较大的覆盖面，但是对于每个网站而言，他都会是浅尝辄止，因为较深层次的网页的优先级比较低，网页数量一旦过大，爬虫将很难在短时间内访问这些深层次的网页。所以该算法主要针对于早期的互联网以及限定较小抓取规模的爬行任务。（2）深度优先爬行算法•目前互联网上的网站，其主要内容一般没有处在顶上面的层次，最上面层次里的网页一般是深层次网页的索引，所以深度优先算法主要是为了弥补广度优先算法无法充分获取网页信息的缺点。•深度优先算法简单的说就是从网站的第一层起始页面开始访问，然后再访问此页面链接下一个层次的页面，如此反复,也就是一个链接一个链跟踪下去，直到处理完此链对应的最深层次的页面,才会重新转到起始页的下一个链接上去。如果使用深度优先算法访问此网站，那么它的访问路径顺序会是：访问路径1：A一B一E一H访问路径2：A一B一E一I访问路径3：A一C访问路径4：A一D一F一J一K访问路径5：A一D一G一J一K某网站层次结构深度优先算法每次都是从第一层选择一条线路一直访问到这条线的最底层，然后再从第一层开始选择另外一条线继续访问，但是爬虫就有可能在一个页面上访问多次，这样会降低爬虫的效率。优化后的爬行路径为：访问路径1：A一B一E一H访问路径2：I访问路径3：C访问路径4：D一F一J一K访问路径5：G某网站层次结构深度优先爬行算法存在的问题•深度优先算法最大的特点就是可以获得网站放置在深层次的页面内容，但是缺点也十分明显，因为它非常容易导致爬虫陷入某个网站而出不来，而且其覆盖也比较小，不适合需要访问大面积网站的任务。（3）最佳优先爬行算法•最佳优先算法实际上是前面两种算法的有机结合,并且和网页分析结合在一起。•在网络爬虫使用最佳优先算法访问网页的时候，算法会兼顾爬行深度和广度。例如限制其一般网站的访问深度，或对即将要访问的链接做分析，判断此网页是不是有价值的网页，如果是，就进行访问。•这种算法最大的问题就是如何才能判断一个网页到底是不是有价值的网页。关于这个问题就要使用到页面分析算法了。页面分析算法•基于网络拓扑的分析算法（或链接分析算法）–依靠同类网页之间会相互添加链接指向对方，通过己知网页，对和其有直接或间接链接关系的网页进行评价，以此作为是否抓取的依据。•基于网页内容分析算法–根据网页内容与所要抓取的主题进行相关度评价，将评价高的网页进行抓取保存。PageRank•Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期的搜索系统原型时提出的链接分析算法，是其他搜索引擎和学术界十分关注的计算模型。PageRank算法原理（1）•PageRank的计算充分利用了两个假设：数量假设和质量假设。步骤如下：–在初始阶段：网页通过链接关系构建起Web图，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。–在一轮中更新页面PageRank得分的计算方法：在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。假设所有网站的PageRank的值是均匀分布的。这意味着，如果有N个网站，那么每个网站的PageRank初始值都是1/N。现在假设有4个网站A、B、C、D，则它们的初始PageRank都是0.25，它们的链接关系如下：则初始值PR(A)=PR(B)=PR(C)=PR(D)=0.25，又因为B、C、D都有指向A的链接，因此，它们每人都为A贡献了0.25的PageRank值，重新计算A的PageRank值为：PR(A)=PR(B)+PR(C)+PR(D)=0.75，由于B、C和D并没有外部链接指向它们，因此PR(B)、PR(C)、PR(D)在这次计算中将被赋值为0。反复套用PageRank的计算公式，来看一下，这种情况下PageRank的收敛性，在第二次迭代之后，所有的PageRank值就都是0了：PageRank算法原理（2）•PageRank值计算过程的一般步骤可以概括如下：–为每个网站设置一个初始的PageRank值。–第一次迭代：每个网站得到一个新的PageRank。–第二次迭代：用这组新的PageRank再按上述公式形成另一组新的PageRank。–……PageRank算法原理（3）•由于存在一些出链为0，也就是那些不链接任何其他网页的网，也称为孤立网页，使得很多网页能被访问到。•因此需要对PageRank公式进行修正，即在简单公式的基础上增加了阻尼系数q。–q表示在任意时刻，用户到达某页面后并继续向后浏览的概率，一般取值为0.85。–1-q=0.15就是用户停止点击，随机跳到新URL的概率PageRank算法原理（4）拉里·佩奇和谢尔盖·布林在《TheAnatomyofaLarge-scaleHypertextualWebSearchEngineComputerNetworksandISDNSystems》定义的公式。所以一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。这就是搜索引擎使用它的原因。5.1.2网络爬虫的分类•根据抓取网页的内容是否具有边界性，网络爬虫可分为通用爬虫和主题爬虫。–通用爬虫没有对抓取目标网页内容限定范围，仅仅是从种子网页超链接开始，不断从当前页面上抽取新的超链接放入待爬行队列，直到满足系统的停止爬行条件为止，期间经过简单的去重处理后，就可以形成网页采集库。–主题爬虫（FocusedCrawler）是能够自动识别网络文档主题性，进行在特定主题内抓取网页的智能程序，且能够独立地完成抓取工作和主题决策，采集的主题信息形成领域边界空间，为垂直领域搜索提供主题数据支持。通用网络爬虫的一般工作流程主题爬虫需要解决的问题•主题网络爬虫要较好地完成主题网页抓取，需要解决五个方面的主要问题：–主题内容的描述和定义问题–主题爬行队列的优先访问次序问题–网页主题相关性判定问题–主题网络爬虫的覆盖度问题–主题网络爬虫的精准度与效率之间的平衡问题（1）主题内容的描述和定义问题•对于主题内容的描述和界定是是主题爬虫实现的关键，在网页抓取过程中一定要一个主题参照物，爬行的网页与这个参照物进行比对，如果达到主题相似度就认为该页面属于该主题，爬虫才把该页面列入下载队列。所以如何描述、表达这个主题参照物显得很重要。（2）主题爬行队列的优先访问次序问题•在爬行过程中如何决定各网页之间的访问次序是主题爬虫顺利完成抓取任务的保证，通常是根据已抓取网页和待抓取网页的主题相关度进行加权传递计算得到的，再依据各网页的主题相关度大小来安排爬行优先队列。这种爬行策略与深度优先或广度优先有较大的不同，按照主题相关度大小的访问序列会带来爬行效率的提升，也会提高爬行结果的主题约束性。（3）网页主题相关性判定问题•网页主题相关性判定是主题爬虫的核心，主题判定算法的优劣可以直接决定主题抓取的质量，所以不同的主题网络爬虫间的主要区别就是如何计算待抓取网页的主题相关度。（4）主题网络爬虫的覆盖度问题•主题网页在客观现实情况下是有可能不存在直接链接关系的，两个主题网页之间是存在一定长的不相关页面链接距离的，通常也称之为“主题隧道”，如何穿过隧道而接通主题相关网页，提高主题资源的覆盖度是主题爬虫的一个难点。（5）主题网络爬虫的精准度与效率之间的平衡问题•主题网络爬虫在提高主题约束精准程度的同时，会引入更复杂的主题爬行策略算法，而另一方面又面对的是开发的、海量的和动态更新频繁的Web网络，主题爬行的精准度与完成效率之间往往是矛盾的。所以完成一次主题爬行的时间和效率需要得到控制，需要找到一个主题网络爬虫的精准程度与效率之间的平衡点。5.1.3网络爬虫涉及到的其它技术•DNS解析扩展•并行存取•网页净化•网页消重•内容抽取•中文分词•网页索引5.1.4爬虫领域的一些开源软件•搜索引擎Nutch•Web爬虫Heritrix•Java网页爬虫Jspider•网页抓取/信息提取软件MetaSeeker•主题爬虫Webmagic•……5.2MASHUP5.2.1Mashup概述（1）•Mashup是近几年来迅速发展起来的一种新兴Web开发技术，它可以将来自多个数据源的内容和服务进行创新组合后而创建出的一个全新的Web应用。•2008年，全球权威的IT研究与顾问咨询公司Gartner预测，Mashup将是未来十年中最值得关注的十大战略技术之一。5.2.1Mashup概述（2）•Mashup一词最初源于流行音乐，是指从两首不同的歌曲中混合演唱和乐器的音轨而构成的一首新歌。扩展到互联网领域，Mashup则是一种令人兴奋的交互式Web应用程序。•Wikipedia对Mashup的定义是：“mashup是指一个网页或Web应用，它将来自两个或更多的外部资源的数据或功能结合在一起以创建一个新的服务。Mashup意味着简单、快速的集成，它通常使用开放的API和数据源来创造出原始数据所无法创造的结果。”5.2.1Mashup概述（3）•从广义上讲，我们可以这样理解Mashup的概念：Mashup是一种全新的应用程序开发方法，它允许用户将来自不同来源的内容或服务以一种集成、一致的方式聚合在一起，从而提供单个来源的服务所无法提供的全新增值的服务，而利用这种方法及相关技术开发的Web站点或Web应用程序称为Mashup应用HousingMaps网站最初广为流行的Mashup实例之一是HousingMaps.com。它是一个简单、便捷的房