天津大学2007届本科生毕业设计（论文）
第二章 相关技术背景
2.1 网络爬虫的定义
定义1：网络爬虫是一个自动提取网页的程序，它为搜索引擎从Web上下载网页，是搜索引擎的重要组成部分。通用网络爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL列表；在抓取网页的过程中，不断从当前页面上抽取新的URL放入待爬行队列，直到满足系统的停止条件。
定义2：主题网络爬虫就是根据一定的网页分析算法过滤与主题无关的链接，保留主题相关的链接并将其放入待抓取的URL队列中；然后根据一定的搜索策略从队列中选择下一步要抓取的网页URL，并重复上述过程，直到达到系统的某一条件时停止。所有被网络爬虫抓取的网页将会被系统存储，进行一定的分析、过滤，并建立索引，对于主题网络爬虫来说，这一过程所得到的分析结果还可能对后续的抓取过程进行反馈和指导。
定义3：如果网页p中包含超链接l，则p称为链接l的父网页。
定义4：如果超链接l指向网页t，则网页t称为子网页，又称为目标网页。 主题网络爬虫的基本思路就是按照事先给出的主题，分超链接和已经下载的网页内容，预测下一个待抓取的URL及当前网页的主题相关度，保证尽可能多地爬行、下载与主相关的网页，尽可能少地下载无关网页。
2.2 网页搜索策略介绍
网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先在很多情况下会导致爬虫的陷入(trapped)问题，目前常见的是广度优先和最佳优先方法。
2.2.1 广度优先搜索策略
广度优先搜索策略是指在抓取过程中，在完成当前层次的搜索后，才进行下一层次的搜索。该算法的设计和实现相对简单。在目前为覆盖尽可能多的网页，一般使用广度优先搜索方法。也有很多研究将广度优先搜索策略应用于聚焦爬虫中。其基本思想是认为与初始URL在一定链接距离内的网页具有主题相关性的概率很大。另外一种方法是将广度优先搜索与网页过滤技术结合使用，先用广度优先策略抓取网页，再将其中无关的网页过滤掉。这些方法的缺点在于，随着
5
天津大学2007届本科生毕业设计（论文）
抓取网页的增多，大量的无关网页将被下载并过滤，算法的效率将变低。
2.2.2 最佳优先搜索策略
最佳优先搜索策略按照一定的网页分析算法，预测候选URL与目标网页的相似度，或与主题的相关性，并选取评价最好的一个或几个URL进行抓取。它只访问经过网页分析算法预测为“有用”的网页。存在的一个问题是，在爬虫抓取路径上的很多相关网页可能被忽略，因为最佳优先策略是一种局部最优搜索算法。因此需要将最佳优先结合具体的应用进行改进，以跳出局部最优点。将在第4节中结合网页分析算法作具体的讨论。研究表明，这样的闭环调整可以将无关网页数量降低30%~90%。
2.3 判断相关度算法
主题爬虫的系统组成最初考虑是对页面的过滤，不像普通爬虫对所有页面的链接进行处理，先对页面与受限领域的主题相关度进行分析，只有当其主题相关度符合要求时才处理该页面中的链接，因为如果该页面和本领域比较相关，它所包含的链接和领域相关的几率也较大，这样提高了爬行精度，虽然会遗漏少数页面，但综合效果是令人满意的。因此，主题相关度的分析是主题爬虫设计的关键。 （一）主题相关度计算模型
垂直搜索引擎与通用搜索引擎最大的区别在于垂直搜索引擎是面向某个领域的，因而垂直搜索引擎的网络蜘蛛只采集与主题相关的网页，与主题无关的网页将被丢弃，将此类网络蜘蛛称为主题蜘蛛[6-8]。主题蜘蛛将网页下载到本地后，需要使用基于内容的主题判别方法计算该网页的主题相关度值，主题相关度低于某一阈值的网页被丢弃。主题相关度的计算方法有布尔模型和向量空间模型两种模型算法[10]。
1.布尔模型。在主题判别时，布尔模型是很容易实现的。在布尔模型[9]中，一个文档通过一个关键词集合来表示。同时，某个主题也以关键词集合的形式来表示。在判断文档与某主题的相关度的过程中，相当于是计算两个关键词集合的交集。对基于布尔模型的主题判别模型来说，交集中含有的元素越多，则认为与主题的相关度就越高。
2.空间向量模型。向量空间模型[11]（Vector Space Model）由Salton等人于20世纪60年代末提出，是一种简便、高效的文本表示模型，其理论基础是代数学。与布尔模型不同，向量空间模型把用户的查询要求和数据库文档信息表示成由检索项构成的向量空间中的点（向量），而通过计算向量之间的距离来判定文档和查询之间的相似程度（例如，用它们之间夹角的余弦作为相似性度量）。
6
天津大学2007届本科生毕业设计（论文）
然后，根据相似程度排列查询结果。在向量空间模型中，文档被形式化为n维空间中的向量，把关键词的个数n作为空间向量的维数，每个关键词的权值 作为每一维分量的大小，则主题用向量表示为： A=(a1,a2,?,an),i=1,2,?,n,ai=wi
对于页面进行分析，统计关键词出现的频率，并求出频率之比，以出现的频率最高的关键词作为基准，其频率用xi=1表示，通过频率比，求出其他关键词的频率 ，则该页面对应向量的每一维分量为xiwi。指定一个阈值r，当cos<α，β>=r时就可以认为该页面和主题是比较相关的，r的取值需要根据经验和实际要求确定，如果想获得较多的页面，可以把r设小一点，要获得较少的页面可以把r设的大一点。
（二）布尔模型与空间向量模型分析
布尔模型的主要缺陷在于每个关键词的权重都是一样的，它不支持设定关键词的相对重要性，但是其优点也较为明显，它易于实现，计算代价较小。 向量空间模型最大优点在于它在知识表示方法上的巨大优势。在该模型中，文档的内容被形式化为多维空间中的一个点，以向量的形式给出。也正是因为把文档以向量的形式定义到实数域中，才使得模式识别和其他领域中各种成熟的算法和计算方法得以采用，极大地提高了自然语言文档的可计算性和可操作性。 通过对空间向量模型和布尔模型的介绍，我们知道现在垂直搜索引擎大多采用空间向量模型计算主题相关性。这样极大的提高到主题爬虫的效率，也极大的提高了垂直搜索引擎的应用效率，给客户带来了高效的查询效果。与在进行页面的主题相关度分析后，当其主题相关度符合要求时将处理该页面中的所有链接，但其中的链接指向的页面也可能有许多偏离了主题，这一点在网页的标题上就可以看出，现在大多数网页的标题已经很明显的给出了文本的主要描述对象，所以传统的空间模型策略没有注意到网页标题这个重要的角色。针对此提出了一种基于网页标题的空间向量模型主题相关度计算方法。
7
天津大学2007届本科生毕业设计（论文）
第三章 网络爬虫模型的分析和概要设计
3.1 网络爬虫的模型分析
首先建立URL任务列表，即开始要爬取的URL。由URL任务列表开始，根据预先设定的深度爬取网页，同时判断URL是否重复，按照一定算法和排序方式搜索页面，然后对页面按照一定算法进行分析，并提取相关URL，最后将所得URL返回任务列表。之后将任务列表中URL重新开始爬取，从而使网络爬虫进行循环运行。
3.2 网络爬虫的搜索策略
本文的搜索策略为广度优先搜索策略。如下图3-1所示。
图3-1 广度优先搜索策略示意图
1）定义一个状态结点
采用广度优先搜索算法解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点。不同的问题需要用不同的数据结构描述。
2）确定结点的扩展规则
根据问题所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个
8
天津大学2007届本科生毕业设计（论文）
过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。
广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，...对长度为n+1的任一结点进行扩展之前，必须先考虑长度为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。这里采用的原则是先生成的结点先扩展。
结点的扩展规则也就是如何从现有的结点生成新结点。对不同的问题，结点的扩展规则也不相同，需要按照问题的要求确定。 3）搜索策略
为了便于进行搜索，要设置一个表存储所有的结点。因为在广度优先搜索算法中，要满足先生成的结点先扩展的原则，所以存储结点的表一般设计成队列的数据结构。
搜索的步骤一般是：
（1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。
（2）检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。
（3）检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展......。
最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。
3.3 网络爬虫的主题相关度判断
主题爬虫的系统组成最初考虑是对页面的过滤，不像普通爬虫对所有页面的链接进行处理，先对页面与受限领域的主题相关度进行分析，只有当其主题相关度符合要求时才处理该页面中的链接，因为如果该页面和本领域比较相关，它所包含的链接和领域相关的几率也较大，这样提高了爬行精度，虽然会遗漏少数页面，但综合效果是令人满意的。因此，主题相关度的分析是主题爬虫设计的关键。
9