2.4 网页搜索算法

2.4.1 网页特征选取

1．主题描述方式

主题蜘蛛需要对搜索目标的主题进行描述，主题描述方式可以分为基于目标网页特征、基于目标数据模式和基于领域概念等三种。

在基于目标网页特征的描述方式中，网络蜘蛛的搜索对象通常是网页，网页特征可以是网页的内容特征，也可以是网页的链接结构特征等。种子样本获取方式可以分为如下三种：

（1）预先给定的初始种子样本。

（2）预先给定的网页分类目录以及与分类目录对应的种子样本。

（3）通过用户行为确定的搜索目标样例，包括用户浏览过程中显示标注的样本、通过用户日志挖掘得到访问模式及相关样本。

在基于目标数据模式的描述方式中，网络蜘蛛的搜索对象是网页上的数据，其网页数据要符合一定的数据模式或者能够映射为目标数据模式。这类数据的典型代表就是电子商务网站的产品信息页面，具有统一的风格，其中的数据表示具有固定格式，并按照一定目录层次结构来组织。

在基于领域概念的描述方式中，通过建立目标领域的词典，从语义角度分析不同特征在某一主题中的重要程度。这种描述方式具有清晰的概念层次以及概念间、属性间的关系定义，能够方便地获得一个词语的同义词或上下义词。

2．特征选取方法

常用的特征选取方法有文档频率（Document Frequency, DF）、信息增益（Information Gain, IG）、互信息（Mutual Information, MI）、卡方检验（Chi-square/χ2, CHI）等。

1）DF

DF表示在训练集中包含某个特征项t的文档数。使用这种方法来衡量特征项重要程度是基于这样一个假设：DF值较小的特征项对分类结果的影响较小。这种方法优先选取DF值较大的特征项，而DF值较小的特征项将被剔除，即特征项按照DF值排序。DF是最简单的特征项选取方法，并且该方法的计算复杂度低，能够胜任大规模的分类任务。

2）IG

IG通过统计某个特征项t在一个文档中出现或不出现的次数来预测文档的类别，IG的计算公式如下：

式中，Pr(ci)表示一个文档属于类别ci的概率；Pr(t)表示特征项t在一个文档内出现的概率；表示特征项t不在一个文档内出现的概率；Pr(ci|t)表示特征项t在属于类别ci的文档内出现的概率；表示特征项t不在属于类别ci的文档内出现的概率。m是文档类别数。G(t)值大则被选取的可能性大，即特征项按照G值排序。

3）MI

MI使用如下公式计算某个特征项t和类别c之间的相关性。

式中，A为t和c同时出现的次数；B为t出现而c没有出现的次数；C为c出现而t没有出现的次数。N为所有文档数。如果t和c不相关，则I（t,c）值为0。如果有m个类别，每个t都会有m个值，取它们的平均值，就可以得到特征选取所需的一个线性序列。I平均值大的特征被选取的可能性大。

4）CHI

使用MI衡量特征项的重要程度时，只考虑到了正相关对特征项重要程度的影响。如果特征项t和类别c反相关，则说明含有特征项t的文档不属于c的概率要大一些，这对于判断一个文档是否不属于类别c也是具有指导意义的。CHI考虑了反相关性，使用如下公式计算特征项t和类别c的相关性。

式中，A为t和c同时出现的次数；B为t出现而c没有出现的次数。C为c出现而t没有出现的次数；D为t和c同时没有出现的次数。N为训练集中的文档数。与MI类似，如果t和c不相关，则χ2(t,c)值为0。与MI相同，如果有m个类别，每个t都会有m个值，取它们的平均，就可以得到特征选取所需的一个线性序列。χ2平均值大的特征被选取的可能性大。

2.4.2 网页搜索算法

为了高效地搜集与主题相关的网页资源，主题蜘蛛应尽可能多地搜集主题相关的网页，并尽可能少地搜集无关的网页，以确保搜集网页的质量。因此，研究人员提出了多种主题定制搜索策略和相关算法，下面介绍几种比较流行的搜索算法。

1．基于链接结构评价的搜索算法

基于链接结构评价的搜索策略是利用Web结构信息来指导搜索，并通过分析Web网页之间相互引用的关系来评价网页和链接的重要性。这种策略的基本思想来自于文献计量学的引文分析理论，将引文分析理论应用于Web环境时，主要采用基于链接结构的评价方法。下面介绍基于这种策略的常用两种搜索算法。

1）PageRank算法

PageRank算法是由Google公司研究人员提出并应用于搜索引擎中。该算法挖掘出网页间链接关系的价值，其挖掘过程也称为链接分析。简单地说，如果网页A链接到B，则表示网页A的编写者对网页B的认可。或者说网页A为网页B投了一票，网页B的重要性被网页A认可。网页重要性可以从三个方面来评价。

（1）认可度越高的网页越重要，即反向链接越多的网页越重要。

（2）反向链接的源网页质量越高，被这些高质量网页链接指向的网页越重要。

（3）链接数越少的网页越重要。

PageRank算法用于计算网页的重要性，对每个链入赋以不同的权值，链接提供的网页越重要，则该链入权值就越高，即当前网页的重要性是由其他网页的重要性决定的。PageRank算法的计算公式如下：

式中，PRn(A)是网页A的级别（即PageRank值）,PRn-1(Ti)是网页Ti的级别，网页Ti存在指向网页A的链接，C(Ti)是网页Ti链出的链接数量，d是阻尼系数，取值在0～1，通过实验找出的最佳值为0.85。

该算法不以站点排序，网页的级别由一个个独立的网页决定，即由链向网页的级别来决定，但每个链入网页贡献的值是不同的。如果Ti网页中链出越多，它对当前网页A的贡献就越小。网页A的链入网页越多，其网页的级别也越高。阻尼系数的使用，减少了其他网页对当前网页A的排序贡献。

该算法可以通过用户上网行为的随机冲浪模型来解释，随机冲浪模型对用户上网行为描述如下：

（1）用户随机选择一个网页作为上网的起始网页。

（2）看完这个网页后从该网页内所含的链接中随机选择一个网页继续浏览。

（3）沿着链接继续浏览，直到对某个主题感到厌倦而重新随机选择另一个网页浏览。如此反复，直到结束。

随机冲浪模型将用户点击链接的行为视为一种不关心内容的随机行为，而用户单击网页内链接的概率完全由网页上链接数量的多少来决定，这也是式（2-4）中PRn-1(Ti)/C(Ti)的原因。一个网页通过随机冲浪模型到达的概率就是链入它的网页上链接被点击概率之和。阻尼系数d的引入是因为用户不可能无限地点击链接，常常因劳累而随机跳入另一个网页。d可以视为用户无限地点击下去的概率，1-d则就是网页本身所具有的网页级别。

PageRank算法主要考虑了链接的结构特征，而忽略了网页内容与主题的相关性，容易出现采集偏离主题的“主题漂移”问题。因此，研究人员提出了一些改进的PageRank算法，如在PageRank算法中考虑了用户从一个网页直接跳转到非直接相邻的但是内容相关的另一个网页的情况等。

2）HITS算法

PageRank算法对于链出的权值贡献是平均的，也就是不考虑不同链接的重要性。而Web链接却具有以下特征：

（1）有些链接只起导航或广告作用，还有些链接具有注释性，只有注释性的链接才用于权威判断。

（2）基于商业或竞争因素考虑，很少有Web网页指向其竞争领域的权威（Authority）网页。

（3）权威网页很少具有显式的描述，比如Google主页不会明确给出Web搜索引擎之类的描述信息。因此，权值的平均分布不符合链接的实际情况。

HITS（Hyperlink-Induced Topic Search）算法定义了另一种网页，称为中心（Hub）网页。Hub网页是提供指向Authority网页链接集合的网页，它本身可能并不重要，或者说没有几个网页指向它，但是Hub网页的确提供了指向某个主题的重要站点链接集合，例如一个课程主页上的推荐参考文献列表。一般来说，好的Hub网页指向很多好的Authority网页，好的Authority网页是有很多好的Hub网页指向的网页。这种Hub与Authority网页之间的相互加强关系，可用于Authority网页以及Web结构与资源的自动发现，这就是Hub/Authority方法的基本思想。

HITS算法是基于Hub/Authority方法的搜索算法，算法如下：

（1）将查询q提交给基于关键字匹配的搜索引擎。搜索引擎返回很多的网页，从中取前n个网页作为根集，用S表示。S满足以下条件：S中网页数量相对较小；S中大多数网页是与查询q相关的网页；S中网页包含较多的Authority网页。

（2）通过向S中加入被S引用的网页和引用S的网页，将S扩展成一个更大的集合T。

（3）以T中的Hub网页为顶点集V1，以Authority网页为顶点集V2,V1中的网页到V2中的网页的链接为边集E，形成一个二分有向图SG=（V1,V2,E）。对V1中的任何一个顶点v，用h(v)表示网页v的Hub值，对V2中的顶点u，用a(u)表示网页的Authority值。开始时h(v)=a(u)=1，对u执行I操作修改它的a(u)，对v执行O操作修改它的h(v)，然后规范化a(u)和h(v)。如此重复计算I、O操作，直到a(u)和h(v)收敛。

I操作为：

O操作为：

每次迭代后需要对a(u)和h(v)进行规范化处理：

I操作反映了如果一个网页有很多好的Hub指向，则权威值会相应地增加，即权威值增加为所有指向它的网页的现有Hub值之和。O操作反映了如果一个网页指向很多好的Authority网页，则Hub值也会相应地增加，即Hub值增加为该网页链接的所有网页的权威值之和。

PageRank和HITS两种算法的共同点是利用网页之间的引用关系来确定链接的重要性，其优点是考虑了链接的结构特征，但也存在一些缺陷：一是忽略了网页与主题的相关性，在某些情况下，会出现搜索偏离主题的“主题漂移”问题，二是在搜索过程中需要重复计算PageRank值或Authority与Hub权值，计算复杂度随访问网页和链接数量的增长呈指数级增长。

2．基于网页内容评价的搜索算法

基于网页内容评价的搜索策略是利用网页文本内容作为领域知识指导搜索，并根据网页文本与主题之间相似度的大小来评价链接价值的高低。下面介绍基于这种策略的两种常用搜索算法。

1）Fish Search算法

Fish Search算法也称为鱼群搜索算法，它将在网络上遍历搜索的网络蜘蛛比喻为海里的一个鱼群，当鱼群找到大量的食物（主题相关网页）之后，这些鱼就变得强壮，并繁殖更多的后代；反之，鱼群就变得虚弱，后代也少。当鱼群找不到食物（无相关网页）或者水被污染（带宽不够）的时候，鱼群就会死亡。该算法的关键是根据用户的种子站点和查询的关键词或短语，将包含查询字符串的网页看作与主题相关，计算该网页与主题的相似度，动态地维护待爬行URL的优先级队列url_queue。

当获取一个网页后，提取该网页所有的URL，这些URL所对应的网页称为孩子网页。如果获取的网页与主题相关，将孩子网页的深度设置成一个预先定义的值，否则将孩子网页的深度设置成一个小于父亲网页深度的值。当这个深度为零时，这个方向的搜索就停止。

按照下列启发策略，将深度大于0的孩子网页的URL加入到url_queue的顶部：

（1）相关网页的前α×width个孩子加入到url_queue的顶部，其中α是预设的大于1的常量。

（2）无关的网页的前width个孩子URL加入到url_queue队列中紧靠着相关网页的孩子节点后面。

（3）剩下的孩子URL加入到url_queue的尾部，它们只有在时间允许的情况下才有可能被搜索。

上述的三种情况可以用一个变量potential_score来等价描述。在情况（1）下，变量设置为1；在情况（2）下，变量设置为0.5；在情况（3）下，变量设置为0。待爬行URL队列按照该变量值来排序，算法伪代码如算法2-1所示。

该算法是一种基于客户端的搜索算法，其优点是模式简单、动态搜索。但也存在一些缺点，例如只使用简单的字符串匹配来分配potential_score的值，并且只有1、0.5、0三个值，分配的值不能完全代表与主题的相似度；在url_queue中，优先级值之间的差别太小，当很多的URL具有相同的优先级，并且在搜索时间受到限制时，可能将后面更重要的网页忽略了；使用width参数来调节删除网页后面的URL个数也不尽合理，有可能导致丢掉很重要的资源。

2）Shark Search算法

Shark Search算法是对Fish Search算法的一种改进，主要改进了网页与查询信息相似度计算方法和potential_score值计算方法，具体改进如下：

（1）在网页与查询信息的相似度计算中引入了向量空间模型，对相似度值进行细化，使其取值在0～1，而Fish Search算法的相似度计算为简单的两值判断，不够细致和精确。

（2）在网页与查询信息的相似度计算中考虑了链接附近的文字（如锚文本及其上下文）所包含的提示信息，使相似度计算更加准确。

由于在孩子节点的potential_score计算中综合考虑了上述两个因素，因此提高了相似度计算的准确性。

基于网页内容评价的搜索策略是根据语义相似度的大小来决定链接的访问顺序，其优点是计算量比较小。然而，由于Web网页不同于传统的文本，它是一种半结构化的文档，其中包含了许多结构信息，Web网页不是单独存在的，网页中的链接在一定程度上反映了网页之间存在着某些关系。采用这种搜索策略的网络蜘蛛忽略了这些信息，因此在链接预测和利用方面存在一些缺陷，容易造成网页的误选。

2.4.3 链接分级搜索

由于网络论坛、博客等互动式网站是网络舆论的主要来源，网民通过在这类网站上发布帖子来表达自己的意见和观点，容易形成网络舆情。因此这类网站成为网络舆情监测和信息采集的主要对象。由于这类网站有别于一般的静态网络，将传统的搜索策略直接用于网络论坛、博客网站信息采集时往往达不到令人满意的效果，需要根据这类网站的特点，采取有针对性的搜索策略。

1．网络论坛、博客网站特点

通过分析各种网络论坛、博客网站自身的结构特点以及链接结构，可以总结出网络论坛、博客网站具有如下特点：

（1）链接种类众多。除了一般用户所关心的文章或帖子对应的链接之外，论坛、博客中还存在着大量的功能性链接和噪声链接。所谓功能性链接是指为了完成某一功能或操作而设置的链接，例如“登录”、“评论”等；而噪声链接是指广告链接之类与用户所关心的文章完全无关的链接。

（2）文章中链接所处层次不固定。有些文章链接可能置于某一目录式板块的索引页，甚至网络论坛、博客网站的首页之上；而另一些文章则置于某一特定的分档之中，如博客网站中博主自己的文章档案链接之下，有效链接所处层次不固定这一现象在博客网站中尤其突出。

（3）链接冗余现象显著。链接冗余是指同一网页与多个链接相对应的现象。这一现象普遍存在于网络论坛、博客网站之中，例如一篇文章中可能引用了一个链接，但是另外一篇文章中可能也引用同一链接，但链接的URL在形式上很可能是完全不同的。

如果网络蜘蛛没有针对网络论坛、博客网站自身的结构特点采用相应的搜索策略，则有可能导致如下方面的问题：一是大量的无效链接被采集；二是由于有效链接往往位于不同的深度层次，影响到采集覆盖率；三是大量的链接冗余现象有可能导致网络蜘蛛陷入采集陷阱之中。

2．链接分级模型

对于网络论坛、博客网站中各种形式的链接，可以将它们抽象成如下的链接类型。

（1）文章链接：网络论坛、博客网站中有效帖子等形式的文章所对应的链接，每一篇文章都有其唯一的链接，该类链接称为文章链接。

（2）博主链接：博客网站一般包含许多注册博主，每一博主有其唯一的链接，该类链接称为博主链接。

（3）板块链接：论坛网站一般可以划分出若干板块，如新闻板块、人文板块、体育板块等，每一板块有其唯一的链接，该类链接称为板块链接。

（4）目录链接：由于博主链接与板块链接比较相似，并且它们都有一个显著特征，即它们所对应的网页中都包含了若干文章链接，因此可以把两者抽象为目录链接，即目录链接=博主链接∪板块链接。

（5）其他链接：将一些功能性链接、噪声链接等与采集主题无关的一类链接称为其他链接。

上述链接类型基本覆盖了网络论坛、博客网站中所有形式的链接。一般情况下，目录链接中往往包含若干文章链接，这些文章链接则是网络蜘蛛所需要采集的重点链接，而其他链接则是网络蜘蛛所应规避的链接。

在此基础之上，可以把网络论坛、博客网站中的链接归纳划分为三种级别：目录链接、文章链接、其他链接。这三种级别的链接基本覆盖了网络论坛、博客网站中所有的链接形式，如图2-9所示。

从图2-9可以看出，网络蜘蛛所关心的文章链接往往包含在一个目录链接之下。因此，可以将上述构成抽象成为网络论坛、博客网站的链接分级模型，即网络论坛、博客网站中包含的大量文章链接都抽象归纳于一个目录链接之下，如图2-10所示。

3．“目录链接-文章链接”搜索策略

根据链接分级模型，网络蜘蛛首先搜索目录链接，去除其他链接的干扰后，再采集目录链接下的文章链接，有助于提高网络蜘蛛的搜索效率。这种搜索方式称为“目录链接-文章链接”搜索策略。

“目录链接-文章链接”搜索策略具有如下优点：

（1）该策略可以使网络蜘蛛的注意力集中在目录链接与文章链接上，从而能够规避无效链接的干扰。

（2）该策略不同于广度优先策略或深度优先策略，在逻辑上规定了两级深度，并限制了各个文章链接之间的干扰，在搜索过程中能够避免搜索陷阱现象的发生。

（3）该策略更加符合人的思维方式，可以融入人工智能方法，提高网络蜘蛛智能化水平，进一步提高搜索效率。

因此，网络蜘蛛在采集网络论坛、博客网站信息时，比较适合采用链接分级模型进行搜索，能够有效地提高搜索效率。