英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

---

基于改进遗传算法的聚焦爬虫URL分析模型

摘要-这篇论文分析了现有聚焦爬虫的URL分析模型及其优缺点，然后我们提出了一种基于改进遗传算法的URL分析模型，对选择算子、交叉算子和变异算子进行了优化。 引入用户查询以构造虚拟文档参与遗传过程。 采用 Rockchio 反馈学习算法对主题向量进行修正，并计算主题对主题文本的相关度。实验表明，改进的遗传算法能够有效地收集主题页面。

关键词-聚焦爬虫; url 分析模型; 遗传算法

1.介绍

随着互联网上信息的爆炸式增长，通用搜索引擎面临着索引规模、更新速度和个性化需求等诸多挑战。 面对这些挑战，适合特定主题和个性化检索的垂直搜索引擎被提出以满足新的需求。基于聚焦爬虫的垂直搜索引擎是搜索引擎研究的热点和难点。

通用搜寻引擎的目的是尽可能多的搜集信息网页，其中网页的搜寻顺序和搜寻网页的主题并不是主要的关注点。它消耗了大量的系统资源和网络带宽。同时，资源的消耗并不会为收集的页带来更高的利用率。聚焦爬行器通过尽可能快速地遍历和尽可能多地收集与预定主题相关的网页来提高所收集网页的利用率。

聚焦爬虫最重要的问题是如何提出一个有效的URL分析模型来衡量新URL所指向的网页是否与预定的主题相关。测量结果对垂直搜索引擎的资源利用率和准确性具有重要意义。

2.相关工作

A.基于内容分析的 url 分析模型

De Bra等人提出了FishSearch模型。这个模型是从仿生学和生物群体智能演化而来的。在这个算法中，网络爬虫被模拟成海里的鱼。当鱼类找到与食物相关的信息时，它们开始繁殖，并扩大它们的数量。它们可以用这种方式捕食更多的食物。 当食物减少(没有相关信息) ，或环境恶化（没有足够的带宽）时，种群便被迫减少，个体便逐渐消失。该算法的核心是如何根据用户感兴趣的主题种子地址和主题关键词的变化，自适应地更新和维护等待爬行的URL队列。

该方法具有模型简化和动态搜索的优点。但也存在一些缺点，如相关度的值是离散的，值的数量很少(只有三个值，即0,0.5,1) ，相关度只有字符串匹配；通过分配的权重难以准确计算主题相关度。在URL队列中，不同类型的URL之间的优先级差异很小。

SharkSearch模型是FishSearch模型的改进版本，改进主要在于相关度计算。SharkSearch模型的相关度不是离散的，而是在0到1之间连续的。与FishSearch模型相比，SharkSearch模型更准确。

1. 基于链接分析的 url 分析模型

PageRank模型的基本思想是，如果一个页面被许多其他页面引用，那么这个页面可能就是重要的页面。如果一个页面被一个重要的页面引用，那么该页面可能也是一个重要的页面，即使该页面没有被引用很多次。一个页面的重要性被平均分配并传递到它所引用的页面。PageRank值是页面重要性的量化等级。根据网页之间的链接信息迭代计算该顺序。链接信息是相对静态的，不考虑网页使用的动态信息。

假设有一个页面i，同时F(i)是i指向的网页，B(i)是指向i指向的网页。假设N(i)=|F(i)|,那么N(i)是页面i的输出度（页面i指向的外部链接的数目），d 是常数（值通常为0.85）。页面i的PageRank值的计算公式如下:

（1）

PageRank模型是一种离线机制，既能快速响应用户的请求，又不需要为在线搜索过程支付额外的时间成本。但同时也存在一个重要的问题，即相似度的计算不是针对查询，排序中的网页是预先下载的，因此，如果最重要的网页不在结果页集中，PageRank算法就无法得到它们;同样，对于基于特定主题的用户查询，一些与主题无关但权重较高的网页在返回结果中排名靠前，即主题漂移现象。

HITS模型将重要页面分为两类: 权限页面和 hub 页面。权限页面涉及已知的权限页面，中心页面提供指向权限页面的链接集涉及一个或多个常规页面。 一般来说，好的中心通常指向许多好的权限页面，好的权限页面通常指向许多好的中心页面。

HITS算法利用了集线器和权限之间的交互。HITS算法的步骤如下:

将查询q转化为一般的基于相似度的搜索引擎，然后搜索引擎返回多个页面，以前n个页面作为根集（RootSet），即为S。然后通过将被S提及的页面和S引用的页面加入到S中，将S扩展为一个更大的集合T，作为基集（BaseSet）。 首先，为T中的每个页面分配一个非负权重 ap 和中心权重 hp，并使用相同的常量初始化所有ap和hp。

权重和中心权重迭代地根据(2)计算:

（2）

HITS算法的缺点是依赖于用户查询，计算量大，不能满足实时性的要求。另外，如果在基本集合中有少量与查询主题无关的页面，但是它们是紧密联系的，HITS算法的结果可能涉及到这些页面，那么主题漂移就出现了。

Allan borodin等人提出了这样的O操作:Hub值等于Hub指向的页面权限的平均值。这是Hub Average模型。

Allan borodin等人还指出，当计算一个页面的权威值时，所有指向该页面的网页的hub值的贡献不应该涉及，因为有些网页是作弊或存在其他因素，贡献只涉及那些hub值大于平均值的网页。这是中心阈值方法。Hub值的计算只涉及第一个K权限页面的贡献，而不是所有指向权限阈值模型的页面。全阈值模型是中心阈值法和权限阈值模型的结合。

3.网页预处理

在对网页文档进行主题相关性分析之前需要对网页进行预处理。预处理的目的是对网页文档进行一定程度的形式化表示。正式的相关计算应有利于后续的相关计算。

本文介绍了在对网页文档进行预处理时，将向量空间模型作为形式化表示的基础。向量空间模型的基础是，文件可以完全由文件中出现的所有单词及其出现的次数来表示，而不考虑文件中单词的位置或它们之间的相对顺序。

A.特征提取
特征提取最常用的特征提取方法是文档频率(文档频率，DF) :

DF(t)=文档发生特征的数量t/训练集中所有文档的数量（3）

DF的优点是计算复杂度较低。DF的评价函数建立在小频率特性包含少量信息的假设基础上，但该假设是不完全的。因此，通常DF并不直接用于实践，而是作为评估其他评价函数的标准。

在研究消息过滤、文档分类及信息抽取时，与DF值较高的词汇相比，DF值较低的词汇通常涉及更多的信息，因此不应完全删除。

针对DF依赖于高频词的缺点，采用文档频率比（DFR）对DF进行改进，公式如下:

（4）

在这个公式中N是训练集中所有文档的编号，ni是Ci范畴中文档的编号，DFi是Ci范畴中涉及t字的文档的编号，DFrsquo;i是除Ci范畴以外其他范畴中涉及t字的文档编号。

由于矢量文档中提取的每个特征词对矢量文档语义描述的贡献不同，因此每个特征词需要赋予一定的权重来表示这些特征词在文档矢量中的不同重要程度。 本文采用TF-IDF方法计算特征词的权重:

（5）

Weighti 表示文档中特征词的权重值，tfi 表示特征词在文档中出现的频率，n 表示文档集中文档的数量，dfi 表示文档集中涉及特征词的文档的频率，nfi 表示文档向量的维度。

4.改进的遗传算法

前面提到的传统聚焦爬虫URL分析模型存在的问题是，在按照预定主题搜索相关网页的过程中，往往容易得到局部最优解，即只是在相关网页周围爬行，导致一些通过相关度较低的超链接连接在一起的相关网页无法爬行，从而降低了聚焦爬虫的有效覆盖范围。

遗传算法是一种基于进化论和分子遗传学的全局随机搜索算法，其突出特点是隐含并行性和有效利用全局信息的能力，能够有效地找到全局最优解跳局部最优解，这是爬虫URL分析模型需要的重点。

但遗传算法也存在一些缺点，如不能利用系统的反馈，当解达到一定程度时会产生大量不必要的冗余迭代，局部搜索能力弱，也可能得不到最优解。

针对当前普通聚焦爬虫的爬行策略，一般由编辑器提供网页内容，从而产生一些与网页预定主题无关的信息。过去聚焦爬虫采用遗传算法时，经常使用整个网页文档进行遗传过程，导致在遗传过程中容易产生主题漂移。

针对上述问题，本文从以下几个方面对遗传算法进行了改进:

1. 编码

传统遗传算法中使用的二进制编码不适用于形式化表示基于向量空间模型的文档向量。本文采用基于权重的浮动编码，对浮动编码进行了一定程度的优化。

个体的遗传算法是文档载体（过滤关键字及其权重），每个基因代表一个关键字，个体代表一组关键字。

本文用一个长整数识别关键词，用浮点数对权重进行编码。用户模板的关键词向量是C=lt;c1，c2，c3，... cngt;，W=lt;w1，w2，w3，... wngt;。该算法以平均权重降序排列的关键词构造向量，权重较大的关键词大多位于向量的前面，在交叉操作中不易被打破，有利于算法的收敛。

1. 适应度函数

遗传算法的目的是找出最能反映过滤要求的关键词，不管反映过滤要求的关键词是否主要由主题向量决定，因此相关度作为适应度函数。

利用主题向量与相关文档之间相关性的平均值作为适应度函数。

（6）

其中P是用户模板，Di是伪关联反馈中的第i个文档，n是伪关联反馈中文档的数量。

1. 构造虚拟文档

用户查询是用户感兴趣的主题的描述方式，传统的主题描述方式完全由编辑器提供，这在一定程度上偏离了用户的需求。引入用户查询为网页构建虚拟文档，用虚拟文档代替网页文档参与遗传过程，最后得到最优解来修改主题描述。这样不仅可以避免网页文档内容与主题无关对遗传过程的干扰，而且可以使主题描述更贴近用户的需求。

虚拟文档是基于用户日志中的搜索引擎查询日志为查询构造虚拟文档的向量空间模型，虚拟文档是由查询中的关键字组成的文本向量。

给定一组 web 页面D，V表示搜索日志中查询所涉及的一组词汇，T={ t1 t2 ...tm }是从V中选择的索引词汇集。为任何web页面d属于D，Q（d）称为 d的虚拟文档是至少访问 d 一次的查询集。对于d，索引项ti(tf 值)的频率等于Q（d）中涉及t的查询中访问d的总次数。那么d的查询表示可以定义为: d={C1,C2,C3,...,Cm}，其中Ci是分配给索引项ti的TF-IDF的权重。

假设在搜索引擎的用户日志中，当用户查询的条件是q时，通过查询点击页面u的次数是f(q，u)，那么三个（q，u，f(q，u)）被称为记录。如图1所示，五个查询由四个关键字组成，t1，t2，t3和 t4。在查询中:t1，用户点击文档 doc1和 doc3的次数分别为2和3。 根据用户日志中的日志记录信息，以用户查询的关键词为组件构造四维虚拟文档向量，每个向量维度的顺序为 t1、 t2、 t3和 t4。 例如，doc3中的 t1维度是3 1=4，即当用户查询中涉及到 t1时点击 doc3的总次数。

图1虚拟文档举例

D.改进的选择操作符

选择的目的是选择需要在项目中复制的项目。 通常是根据适合度来选择的。 适合度越大的项目被选择的可能性越大。确保好项目能传给下一代。传统的选择方法是基于轮盘赌法。

轮盘赌法的基本思想是基于相对适应度来确定被选项的可能性。

（7）

在这个公式中，项目i被选择的可能性为 pi，项目i的适合度为fi，群体的fi 累计适合度为fi。

显然，适应度越高的项目越有可能被选中。但是，这种方法存在一个问题: 在进化的初级阶段，适应度很高的项目被选择的可能性很高。所以它复制了很多后代。这使得可能与主题相关的网页不再进化，那么搜索就只是局部最优。

针对这一问题，本文提出采用双选择算子:

(1)预选择操作

交叉和变异前的选择操作采用传统的轮盘赌方法。

(2)后选择操作

只有当新一代的个体适合度大于其父亲的适合度时，产生的后代个体才能取代其父亲并传给下一代。否则，父代中的个体仍然是下一代群体。由于子代个体与父代个体之间的代码结构具有相似性，该实现方法只是用相似的代码结构替换了一些子代个体，从而提高了达到最优解的速度。

具体方法是: 交叉操作后，根据适合度将子代和父代个体按降序排列。前几个被选中进入下一代。经过突变操作后，选择父代和子代适合度高的个体进入下一代群体。

E.改进的交叉算子

生物学上的杂种优势意味着父代差异越大，后代就会越好。遗传算法的主要思想来源于自然界中的遗传现象。为此，将自然界中的杂种优势引入遗传算法中: 差异较大的父代个体比两个相似的父代个体更有可能获得新模型下的后代。因此，利用差异较大的父代个体进行交叉是获得新模型的有效途径。

本文所用的确定父代个体相似性的方法是计算父代个体染色体中相同基因的数目。 当数量小于一定阈值时，认为父母个体是不同的，可以进行交叉操作。

F.改进的变异算子

基于一定的变异率 pm，在染色体中选择一个基因，然后改变基因的特征。。变异不仅保证了引入有效的遗传物质来维持种群多样性，而且适当地提高了遗传算法的搜索效率。

对于浮点编码的对象，在实现变异操作时，传统的方法首先利用随机数选择变异的个体和个体的位置。然后，该方法在[0,1]中随机生成一个数字，以替换发生突变的位置。例如:w1(0.60.70.90.030.1)，突变后: w1(0.

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[239400]，资料为PDF文档或Word文档，PDF文档可免费转换为Word