论文部分内容阅读
摘 要：作为主题网络蜘蛛搜索策略的核心部分，主题相关性判断算法是网络蜘蛛能够围绕设定主题进行聚焦检索的关键。本文针对现有基于链接结构的相关性算法PageRank算法的不足，提出了基于网页主题相关度的改进PageRank算法。理论分析和实验表明，相对于传统的信息采集策略，改进的策略在准确率和召回率方面具有明显的优势。
关键词：PageRank，相关性；算法
中图分类号：TP391.3 文献标识码：A
An Approach to Algorithm Based on PageRank Topical Correlativity
ZHANG Li-shuo1， LI Xin1， XU Meng2
1.Henan Institute of Engineering，Henan Zhengzhou 451191；2.Nanjing Bank，Jaingsu Nanjing 210008)
Key words: PageRank；correlativity；algorithm
主题型搜索引擎,就是以构筑某一专题领域或学科领域的因特网信息资源库为目标,智能地在互联网上搜集符合设定专题或满足学科需要的信息资源。主题相关性算法是主题搜索引擎中网络蜘蛛信息采集策略的关键部分，是提高主题网络蜘蛛信息采集效率和准确性的基础。本文对基于链接结构的相关性算法进行研究，在传统的PageRank算法的基础上，根据主题网页的分布特征，引入主题预测相关度加权，使主题网络蜘蛛对网页中潜在的与主题相关性大的链接优先爬行。通过对主题相关性算法的研究，实现了对主题网络蜘蛛爬行方向的前瞻性指导，防止“主题漂移”现象的发生。
1 主题搜索引擎中相关性算法概述
在主题搜索引擎中，网络蜘蛛信息采集的目标是尽可能多地发现并采集与主题相关的信息，而忽略或丢弃与主题不相关或相关性不大的信息[1]。因此，相关性算法在主题网络蜘蛛的信息采集策略中具有至关重要的作用。相关性算法分为基于网页内容的相关性算法和基于链接结构的相关性算法[2] [3]。本文主要介绍基于链接结构的相关性算法。
主题网络蜘蛛信息采集以网页间的链接关系为基础，而网页间的链接关系错综复杂，因此如何选择有效的链接(路径)进行爬行是主题网络蜘蛛信息采集策略中又一关键技术。通常采用基于链接结构的相关性算法，对主题网络蜘蛛的爬行方向进行指导。目前，PageRank算
法和Hits算法是最常见的基于链接结构的相关性分析算法。
2 PageRank算法
PageRank算法是在1998年由斯坦福大学的Sergey Brin和Lawrence Page提出来的[4] ，是目前最大的商业搜索引擎Google采用的链接分析排序算法。
PageRank算法源于传统的文献引文分析方法，即一篇文献的质量可以通过其它文献对其引用的数量来衡量，被引用的次数也会越多，文献质量就越高；同理，网络上网页被其他网页引用的频率越高，该网页的重要性也越高。通过揭示网页之间的引用关系(链接关系)，可以衡量出一个网页在网络上的重要水平(pagerank)。PageRank算法基于以下两个前提[5]：
①一个网页被其他网页多次引用，则它可能很重要；一个网页虽然没有被多次引用，但是被重要的网页所引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。
②假定用户开始时随机地访问网页集合中的一个网页，并根据网页中包含的链接继续浏览，则用户浏览下一个网页的概率就是被浏览网页的pagerank值。
根据PageRank算法，计算某一网页pagerank值的方法如公式2.1所示。
PA（A）=+d(2.1)
其中，A为某待评价网页，T1,T2，…，Ti，…Tn表示A的链入网页，C（Ti）表示网页Ti中链出网页的数量；PR(A)、PR(Ti)分别表示网页A和网页Ti的pagerank值；d为阻尼系数，用来表示用户因疲劳厌倦或其他原因，停止根据网页中的链接继续浏览的概率，取值在0和1之间（通常为0.85）；C为网络上网页的总量，由于网页总数巨大，因此在实际计算中可以忽略(1-d)项。
计算网页的pagerank值时，首先要对网页的初始pagerank值进行初始化，然后使用公式2.1迭代计算，直至网页pagerank值趋于稳定，即收敛于一个相对固定的数时，计算结束。
PageRank算法能较好地反映出网页的权威性，可以有效地从网页的链接结构中发掘出重要的网页。然而，PageRank算法也存在很大的不足。从公式2.1中可以直观地发现，对于每一个网页A的链入网页Ti，只有PR(TI)( 的pagerank值传递给了网页A，即在传统的PageRank算法中，网页的pagerank值是基于链接平均传递的。PageRank算法仅仅对网页的链接结构进行分析，没有区分网页中的超链接与该网页的主题是否相关，常常导致采集到的网页虽然具有较高的pagerank值，却与主题无关的现象（主题漂移现象）发生。
3 PageRank算法改进
3.1算法改进
本文对基于链接结构的相关性算法进行分析，并在此基础上针对PageRank算法在主题搜索中的缺陷，引入了主题预测相关度加权，使网页重要度能够基于链接关系向主题相关度大的方向传递。改进后算法的pagerank值计算方法如公式3.1所示。
PR(A)'=+dR(TA)PR(T)' (3.1)
其中，A为某待评价网页，T1,T2，…，Ti，…Tn为网页A的已采集链入网页，数量为n；PR(A)'、PR(Ti)'分别为网页A和网页Ti的pagerank值；C'为已采集的主题相关网页的总量；d为阻尼系数，取值0.85；R(Ti,A)为网页A的主题相关度预测值。
根据主题网页的站点主题分布特征可知，相同主题的网页更倾向于聚集在一起；根据主题网页的Hub和Linkage/Sibling Locality特征可知，网页重要度可以由指向该网页的重要度和数量来衡量。因此，R(Ti,A)可以由公式3.2进行预测。
R(Ti,A)= (3.2)
其中，sim(Ti,T)为网页A的链入网页Ti的主题相关度。
在公式3.2中，网页的主题相关度预测值由该网页的链入网页主题相关度和链入网页的数量决定，链入网页的数量越多，预测值越高；链入网页的主题相关度越高，预测值也越高。主题相关度预测值不仅体现了网页的主题相关度，而且也体现了网页所具有的权威性，即预测值高的网页可能在该主题中具有较高的权威，应该被主题网络蜘蛛优先爬行。
改进的算法基于以下两个假设：
①一个被大量主题相关网页群所指向的网页的重要性，应该大于一个由少量主题相关的网页群所指向的网页的重要性。
②一个被大量主题无关网页群所指向的网页的重要性，应该小于一个由少量主题相关的网页群所指向的网页的重要性。
假设S为已采集的网页集合(包括网页A)，n为集合S中网页的数量，t为S中的任一网页，则改进后的PageRank算法描述如下：
Improved_PageRank( ){
/* 所有网页的初始重要度 设为1/n */
initialize( )；
j=1；
DO{
/*对网页集合S中的所有网页的PageRank值进行计算*/
FOR EACH t IN S
PR(t)'=+dR(T,t)PR(T)';
/* 进行归一化处理 */
PR(t)=;
/* 计算迭代的差量，以衡量是否达到收敛的要求 */
φ=|PR(t)-PR(t)-1|;
j++；
}WHILE（ ）
}
3.2改进的PageRank算法用于主题相关性预测
链接过滤指基于网页间的链接关系，从网页中筛选出一系列潜在的主题相关度大的链接，供主题网络蜘蛛爬行。链接过滤模块使主题网络蜘蛛能对潜在的与主题相关性大的链接优先爬行，为主题网络蜘蛛能够围绕主题进行信息的聚焦采集提供保证，从而可以有效地避免“主题漂移”现象的发生。
经过网页过滤后，把符合主题要求的网页存入数据库时，需要对网页中的链接进行过滤。本文采用改进的PageRank算法对该网页的中包含的链接进行主题相关性预测，并根据预测结果筛选出符合主题要求的链接，加入到待爬行URL队列中。在利用公式3.1对网页中的链接的主题相关性(即公式3.1中的网页A的重要性)进行评价时，由于包含该链接的网页(即公式3.1中的各个)均为已采集页面，这些网页的主题相关度(即公式3.2中的)已经在网页过滤模块中计算出来，因此在链接过滤过程中可以直接使用，保证链接过滤计算的低计算复杂度。
4 实验结果与分析
本文分别对传统的信息采集策略(使用传统的PageRank算法)和改进的信息采集策略(使用改进的PageRank算法)在采集准确率、资源召回率两个方面进行测试，并根据测试结果对两种策略进行评价。
4.1测试环境
本测试是在实验室硬件和软件环境下完成的。
硬件环境：CPU Core2 2.00GHz、内存 DDR1.00GB、硬盘 120GB
软件环境：操作系统 Windows XP、开发语言 Java(JDK5.0)
开发工具 Eclipse3.1、数据库 SQL Server2000 SP4
4.2测试方案
①测试网页集的选取
利用Google的高级搜索功能，将搜索区域限制为http：//2008.sina.com.cn(新浪网的奥运栏目)，分别对足球、篮球、排球、田径、游泳、射击、体操、举重8个比赛项目进行检索，并选取各项目的前100个网页，组成测试网页集。
②测试方法
将主题网络蜘蛛的初始搜索URL设置为http：//2008.sina.com.cn，分别使用传统策略和改进后的策略进行网页采集，并记录两种策略采集到的网页在测试网页集合中的命中次数，测试结果如表4-1所示。
③结果分析
从测试结果可以发现，改进后的策略的网页命中率明显高于传统策略命中率。相对于传统策略，改进的策略优化了链接过滤技术，使网页的召回率得到显著提高，从而可以较好地防
止“主题漂移”现象的发生。
5 结束语
PageRank算法是应用最广泛相关性计算方法，本文研究了基于链接结构的相关性算法，对PageRank算法的思想和优缺点进行分析，针对主题搜索引擎对信息的具体要求，进行了改进。在PageRank算法的基础上，引入主题预测相关度加权，使网页的重要度基于链接关系向主题相关度大的方向传递。将改进的PageRank算法应用于本文的链接过滤模块中，保证主题网络蜘蛛能对潜在的主题相关度大的链接优先爬行。实验中采集准确率相对于传统策略有明显的提高，说明改进的策略具有较高的主题信息采集效率。
参考文献:
[1]刘强国.主题搜索引擎设计与研究[D].成都：电子科技大学，2006.
[2]陈杰.主题搜索引擎中网络蜘蛛搜索策略研究[D].杭州：浙江大学，2006.
[3]曹红.林业主题搜索引擎研究[D].北京：北京林业大学，2005.
[4]A.Arasu，J.Novak，A.Tomkins，et al.PageRank computation and the structure of the Web：Experiments and algorithms[A].ACM.proceedings of the 11th International WWW Conference[C].NewYork，USA：ACM Press，2002.
[5]黄德才，戚华春，钱能.基于主题相似度模型的TS-PageRank算法[J].小型微型计算机系统，2007，3(28)：510～514.
关键词：PageRank，相关性；算法
中图分类号：TP391.3 文献标识码：A
An Approach to Algorithm Based on PageRank Topical Correlativity
ZHANG Li-shuo1， LI Xin1， XU Meng2
1.Henan Institute of Engineering，Henan Zhengzhou 451191；2.Nanjing Bank，Jaingsu Nanjing 210008)
Key words: PageRank；correlativity；algorithm
主题型搜索引擎,就是以构筑某一专题领域或学科领域的因特网信息资源库为目标,智能地在互联网上搜集符合设定专题或满足学科需要的信息资源。主题相关性算法是主题搜索引擎中网络蜘蛛信息采集策略的关键部分，是提高主题网络蜘蛛信息采集效率和准确性的基础。本文对基于链接结构的相关性算法进行研究，在传统的PageRank算法的基础上，根据主题网页的分布特征，引入主题预测相关度加权，使主题网络蜘蛛对网页中潜在的与主题相关性大的链接优先爬行。通过对主题相关性算法的研究，实现了对主题网络蜘蛛爬行方向的前瞻性指导，防止“主题漂移”现象的发生。
1 主题搜索引擎中相关性算法概述
在主题搜索引擎中，网络蜘蛛信息采集的目标是尽可能多地发现并采集与主题相关的信息，而忽略或丢弃与主题不相关或相关性不大的信息[1]。因此，相关性算法在主题网络蜘蛛的信息采集策略中具有至关重要的作用。相关性算法分为基于网页内容的相关性算法和基于链接结构的相关性算法[2] [3]。本文主要介绍基于链接结构的相关性算法。
主题网络蜘蛛信息采集以网页间的链接关系为基础，而网页间的链接关系错综复杂，因此如何选择有效的链接(路径)进行爬行是主题网络蜘蛛信息采集策略中又一关键技术。通常采用基于链接结构的相关性算法，对主题网络蜘蛛的爬行方向进行指导。目前，PageRank算
法和Hits算法是最常见的基于链接结构的相关性分析算法。
2 PageRank算法
PageRank算法是在1998年由斯坦福大学的Sergey Brin和Lawrence Page提出来的[4] ，是目前最大的商业搜索引擎Google采用的链接分析排序算法。
PageRank算法源于传统的文献引文分析方法，即一篇文献的质量可以通过其它文献对其引用的数量来衡量，被引用的次数也会越多，文献质量就越高；同理，网络上网页被其他网页引用的频率越高，该网页的重要性也越高。通过揭示网页之间的引用关系(链接关系)，可以衡量出一个网页在网络上的重要水平(pagerank)。PageRank算法基于以下两个前提[5]：
①一个网页被其他网页多次引用，则它可能很重要；一个网页虽然没有被多次引用，但是被重要的网页所引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。
②假定用户开始时随机地访问网页集合中的一个网页，并根据网页中包含的链接继续浏览，则用户浏览下一个网页的概率就是被浏览网页的pagerank值。
根据PageRank算法，计算某一网页pagerank值的方法如公式2.1所示。
PA（A）=+d(2.1)
其中，A为某待评价网页，T1,T2，…，Ti，…Tn表示A的链入网页，C（Ti）表示网页Ti中链出网页的数量；PR(A)、PR(Ti)分别表示网页A和网页Ti的pagerank值；d为阻尼系数，用来表示用户因疲劳厌倦或其他原因，停止根据网页中的链接继续浏览的概率，取值在0和1之间（通常为0.85）；C为网络上网页的总量，由于网页总数巨大，因此在实际计算中可以忽略(1-d)项。
计算网页的pagerank值时，首先要对网页的初始pagerank值进行初始化，然后使用公式2.1迭代计算，直至网页pagerank值趋于稳定，即收敛于一个相对固定的数时，计算结束。
PageRank算法能较好地反映出网页的权威性，可以有效地从网页的链接结构中发掘出重要的网页。然而，PageRank算法也存在很大的不足。从公式2.1中可以直观地发现，对于每一个网页A的链入网页Ti，只有PR(TI)( 的pagerank值传递给了网页A，即在传统的PageRank算法中，网页的pagerank值是基于链接平均传递的。PageRank算法仅仅对网页的链接结构进行分析，没有区分网页中的超链接与该网页的主题是否相关，常常导致采集到的网页虽然具有较高的pagerank值，却与主题无关的现象（主题漂移现象）发生。
3 PageRank算法改进
3.1算法改进
本文对基于链接结构的相关性算法进行分析，并在此基础上针对PageRank算法在主题搜索中的缺陷，引入了主题预测相关度加权，使网页重要度能够基于链接关系向主题相关度大的方向传递。改进后算法的pagerank值计算方法如公式3.1所示。
PR(A)'=+dR(TA)PR(T)' (3.1)
其中，A为某待评价网页，T1,T2，…，Ti，…Tn为网页A的已采集链入网页，数量为n；PR(A)'、PR(Ti)'分别为网页A和网页Ti的pagerank值；C'为已采集的主题相关网页的总量；d为阻尼系数，取值0.85；R(Ti,A)为网页A的主题相关度预测值。
根据主题网页的站点主题分布特征可知，相同主题的网页更倾向于聚集在一起；根据主题网页的Hub和Linkage/Sibling Locality特征可知，网页重要度可以由指向该网页的重要度和数量来衡量。因此，R(Ti,A)可以由公式3.2进行预测。
R(Ti,A)= (3.2)
其中，sim(Ti,T)为网页A的链入网页Ti的主题相关度。
在公式3.2中，网页的主题相关度预测值由该网页的链入网页主题相关度和链入网页的数量决定，链入网页的数量越多，预测值越高；链入网页的主题相关度越高，预测值也越高。主题相关度预测值不仅体现了网页的主题相关度，而且也体现了网页所具有的权威性，即预测值高的网页可能在该主题中具有较高的权威，应该被主题网络蜘蛛优先爬行。
改进的算法基于以下两个假设：
①一个被大量主题相关网页群所指向的网页的重要性，应该大于一个由少量主题相关的网页群所指向的网页的重要性。
②一个被大量主题无关网页群所指向的网页的重要性，应该小于一个由少量主题相关的网页群所指向的网页的重要性。
假设S为已采集的网页集合(包括网页A)，n为集合S中网页的数量，t为S中的任一网页，则改进后的PageRank算法描述如下：
Improved_PageRank( ){
/* 所有网页的初始重要度 设为1/n */
initialize( )；
j=1；
DO{
/*对网页集合S中的所有网页的PageRank值进行计算*/
FOR EACH t IN S
PR(t)'=+dR(T,t)PR(T)';
/* 进行归一化处理 */
PR(t)=;
/* 计算迭代的差量，以衡量是否达到收敛的要求 */
φ=|PR(t)-PR(t)-1|;
j++；
}WHILE（ ）
}
3.2改进的PageRank算法用于主题相关性预测
链接过滤指基于网页间的链接关系，从网页中筛选出一系列潜在的主题相关度大的链接，供主题网络蜘蛛爬行。链接过滤模块使主题网络蜘蛛能对潜在的与主题相关性大的链接优先爬行，为主题网络蜘蛛能够围绕主题进行信息的聚焦采集提供保证，从而可以有效地避免“主题漂移”现象的发生。
经过网页过滤后，把符合主题要求的网页存入数据库时，需要对网页中的链接进行过滤。本文采用改进的PageRank算法对该网页的中包含的链接进行主题相关性预测，并根据预测结果筛选出符合主题要求的链接，加入到待爬行URL队列中。在利用公式3.1对网页中的链接的主题相关性(即公式3.1中的网页A的重要性)进行评价时，由于包含该链接的网页(即公式3.1中的各个)均为已采集页面，这些网页的主题相关度(即公式3.2中的)已经在网页过滤模块中计算出来，因此在链接过滤过程中可以直接使用，保证链接过滤计算的低计算复杂度。
4 实验结果与分析
本文分别对传统的信息采集策略(使用传统的PageRank算法)和改进的信息采集策略(使用改进的PageRank算法)在采集准确率、资源召回率两个方面进行测试，并根据测试结果对两种策略进行评价。
4.1测试环境
本测试是在实验室硬件和软件环境下完成的。
硬件环境：CPU Core2 2.00GHz、内存 DDR1.00GB、硬盘 120GB
软件环境：操作系统 Windows XP、开发语言 Java(JDK5.0)
开发工具 Eclipse3.1、数据库 SQL Server2000 SP4
4.2测试方案
①测试网页集的选取
利用Google的高级搜索功能，将搜索区域限制为http：//2008.sina.com.cn(新浪网的奥运栏目)，分别对足球、篮球、排球、田径、游泳、射击、体操、举重8个比赛项目进行检索，并选取各项目的前100个网页，组成测试网页集。
②测试方法
将主题网络蜘蛛的初始搜索URL设置为http：//2008.sina.com.cn，分别使用传统策略和改进后的策略进行网页采集，并记录两种策略采集到的网页在测试网页集合中的命中次数，测试结果如表4-1所示。
③结果分析
从测试结果可以发现，改进后的策略的网页命中率明显高于传统策略命中率。相对于传统策略，改进的策略优化了链接过滤技术，使网页的召回率得到显著提高，从而可以较好地防
止“主题漂移”现象的发生。
5 结束语
PageRank算法是应用最广泛相关性计算方法，本文研究了基于链接结构的相关性算法，对PageRank算法的思想和优缺点进行分析，针对主题搜索引擎对信息的具体要求，进行了改进。在PageRank算法的基础上，引入主题预测相关度加权，使网页的重要度基于链接关系向主题相关度大的方向传递。将改进的PageRank算法应用于本文的链接过滤模块中，保证主题网络蜘蛛能对潜在的主题相关度大的链接优先爬行。实验中采集准确率相对于传统策略有明显的提高，说明改进的策略具有较高的主题信息采集效率。
参考文献:
[1]刘强国.主题搜索引擎设计与研究[D].成都：电子科技大学，2006.
[2]陈杰.主题搜索引擎中网络蜘蛛搜索策略研究[D].杭州：浙江大学，2006.
[3]曹红.林业主题搜索引擎研究[D].北京：北京林业大学，2005.
[4]A.Arasu，J.Novak，A.Tomkins，et al.PageRank computation and the structure of the Web：Experiments and algorithms[A].ACM.proceedings of the 11th International WWW Conference[C].NewYork，USA：ACM Press，2002.
[5]黄德才，戚华春，钱能.基于主题相似度模型的TS-PageRank算法[J].小型微型计算机系统，2007，3(28)：510～514.