一种基于查询主题相关性的PageRank改进算法

【 摘 要 】 PageRank基于链接分析计算页面的权威度，衡量网页的权威性，实现搜索结果的等级排序。文章针对传统PageRank存在的主题漂移问题提出了一种基于查询主题相关性的改进算法。通过引入搜索页面与查询主题的相关性度量，有效地抑制了传统pagerank算法的主题漂移问题，并通过实例加以验证。

【 关键词 】 页面等级；相似度；特征项

【 中图分类号 】 TP3 【 文献标识码 】 A

1 引言

随着信息技术的迅猛发展，互联网成为了人们获取信息的重要途径。通过搜索引擎，用户便能检索到大量的信息，而庞大的结果网页中，真正对用户有用的信息并不多，用户要从结果网页中找到自己真正关心的页面有时需要花费大量的时间。Sergey Brin和Lawrence Page于1998年提出的PageRank算法为搜索引擎提供了变革技术。该算法以页面的链接结构为基础，以权威度作为衡量页面等级的指标，简单、高效是一种独立于查询的页面等级排序算法。全球最大的搜索引擎Google吸收了该算法作为结果网页排序的核心技术。由于PageRank算法独立于查询，完全建立在链接结构上，忽略页面与查询的相关性，因此容易导致产生主题漂移现象。本文据此提出了一种基于查询主题相关性的改进算法，将搜索页面与查询主题的相关性用相似度来度量，改进后的PageRank算法较传统的PageRank算法在“主题漂移”问题上有明显的改善。

2 PageRank算法的基本原理

PageRank算法基于链接分析计算页面的权威度，衡量网页的权威性，实现搜索结果的等级排序。该算法的有效工作需要两个假设前提。

（1） 网页被引用次数越多，网页的重要度越大或权威性越高；网页被重要的网页引用时，重要度越大或权威性越高。

（2） 假定用户对网页集合中的每一个网页的访问都是随机的，并且跟随网页的向外链接只能是向前浏览，不能回退浏览。此时，浏览另一个网页的概率置为被浏览网页的PageRank值。

文献[1]中给出了传统PageRank算法的计算公式：

PR（B）=（1-d）+d （1）

其中，d是取值在0-1之间的阻尼系数，通常取0.85。它是防止页面的PageRank值过高或过低而引入的平衡因子。PR（Ti）为指向页面B的页面Ti的PageRank值，C（Ti）为Ti页面的出链数。

3 查询主题相关性的PageRank改进算法

鉴于传统PageRank算法得到的权威度容易脱离用户搜索的主题范围，产生搜索结果的主题漂移，我们希望将查询主题与搜索结果页面的相关性同时引入到对链接网页的PangeRank值的迭代计算中，并进而影响对搜索结果的排名。

改进的PageRank算法的基本假设：网页的链接个数越多且与查询主题的相关性越大，其PageRank值越高；网页链接不多但与查询主题相关性大的网页，比被大量网页链接但是与查询主题相关性极小的网页的PageRank值高。

本文采用相似度来度量页面与查询主题的相关性，涉及到如下基本概念：

特征项：是构成文本的基本语言单位。如字、词、词组、短语等，它包含较多的语义信息，能够很好地用来表达文本。例如，可以用d（T1，T2，T3，…，Tm）来表示一个文本d，Ti是文本的个特征项中的第i个特征项的值。

特征项的权值：指一个特征项在文本中所占权重。它反映了该特征项对文本信息的表达能力。

相似度：网页页面（内容）与查询主题间相关性的一种度量。例如，假设有向量v1和v2分别表示网页页面和查询主题，二者之间的相似度可以定义为：Sim（v1，v2）=。

改进算法的主要计算步骤如下：

（1） 提取页面的特征项

页面文本可以看成由大量词条构成的集合，可以从词条中选取包含较强语义信息的特征项来表示页面。为此，可以对Web页面先做一些预处理，如去掉网页中的广告、导航等噪音信息，分离HTML文档的标题、正文、超链接、标签等信息。然后，利用分词技术对预处理结果信息进行分词，用分词结果作为特征项来表示页面。

（2） 构造索引词列表

根据特征项构造索引词列表，提取前出现频率最高的特征项作为系统的索引词，并构造相应的查询主题和页面主题索引词向量空间。

（3） 计算索引词的权值

对每个特征项赋予了一定的权重值，采用TF-IDF（词频-反文档频率）方法计算特征项权重，即：

其中，TFij为特征项Tj在文档di中出现的频率：TFij = 。mj表示特征项Tj在文档di中出现的次数，m表示文档di中包含的特征项总数。IDFij 为逆文档频率指数，其值为log （），nj表示出现特征项Tj的文档数，n表示所有文档总数。对于TF-IDF公式，最常用的是改进公式：

它表示：如果某个特征项在一个文档中出现的频率高，在其它文档中出现频率低，则该特征项包含的信息多，其权重高，获得的权值就大。为了避免出现某些权值过高的现象，可对特征项权值做如下归一化处理：

（4） 用向量表示页面文本和查询主题

将文本搜索器搜索出来的前n个页面表示为d1，d2，d3，...di...，dn，m个索引词表示为k1，k2，k3，...kj，...km，索引词kj在页面di中的权值设为Wij，则这n个页面可以表示成m维空间Rm中的向量，即di=（wi1，wi2，wi3，...wij...，wim）。

由于查询主题涉及的关键词较少，对查询主题的向量表示可以用类内全部元素的质心来刻画。即对查询主题Q，可以用查询得到的前n个页面集的质心来表示：

根据上一节文档和查询主题的向量表示，有：

根据向量间的相似度计算，di和Q之间的相似度计算方即：

将（6）计算出来的页面与查询主题相似度作为权值参与页面的PageRank值计算，所得到的PageRank值将更能反映出网页在查询主题下的更合理排名。

改进算法的模型为：假设某个页面A，T1，T2，…，Tn为指向页面A的页面，参数d是取值在0-1之间的阻尼系数，通常d取0.85，Sim（A，Q）为页面A与查询主题Q之间的相似度，PR（A）表示页面A的PageRank值，则改进后的PageRank算法的计算公式如下：

由于引入了相似度，会降低页面的PageRank值，特别是与查询主题无关或相似度极低的页面的PageRank值将得到有效抑制。由于Sim（A，Q）的取值在0-1之间，算法加入相似度评估后并不影响原有的PageRank算法的收敛性，经过若干次迭代运算，页面的PageRank值仍然会收敛。

下面以一组实例验证改进PageRank算法较传统PageRank算法的优越性。

假设一组页面的链接结构如图1所示。其中，页面T2，T3，T4为基于查询q返回的相关页面，表示链接方向，两种算法计算页面的PageRank值，并返回基于查询q的页面T2，T3，T4的排序。

首先，假设阻尼系数d取0.85，由公式（1）对每个页面赋初始PageRank值1，算法的程序运算结果为：

PR（T1）=0.402403 PR（T2）=0.321021 PR（T3） = 0.593889

PR（T4）=0.529903 PR（T5）= 0.15 PR（T6）=0.60041假定页面T1，T2，T3，T4，T5，T6与查询q的主题相似度分别为0.05，0.7，0.4，0.3，0.01，0.02，根据查询主题相关性的改进PageRank的计算公式（7），假设阻尼系数为0.85，每个页面仍然赋初值1，算法的计算结果为：

PR（T1）=0.179678 PR（T2）=0.216408 PR（T3） = 0.205124

PR（T4）=0.166057 PR（T5）= 0.15 PR（T6）=0.185689

针对查询q返回的三个页面T2，T3，T4的两种实验结果如表1所示。

从数据对比中可知，针对本例的查询q，用传统PageRank算法计算，页面T2获得的排名是第3名，但是该页面具有与查询主题很高的相似度，因此采用改进算法其获得的PageRank值明显增加，并且获得了最高排名。

4 结束语

PageRank是基于Web结构挖掘的链接分析思想提出的，是对结果网页进行等级排序的算法。由于传统PageRank算法完全忽略查询的主题与内容，因此容易导致主题漂移。文中提出的基于查询主题相关性的PageRank改进算法从一定程度上有效地抑制了主题漂移问题，但是改进算法中增加了求得相似度的运算，因此，时间耗费较传统PageRank算法大，今后还可以对算法做进一步的优化和改进，在特征项提取和权值计算方面，希望寻求效率更高的方法，减少时间复杂度，也可通过提高硬件设备的执行效率来改善获取相似度的时间代价。

参考文献

[1] S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search Engine. In seventh International World Wide Web Conference. Brisbane. Australia， 1998.

[2] 张冉，夏素萍.一种基于向量空间模型的主题PageRank算法.电脑知识与技术，Vol.5，No.4，February 2009， pp.883-885.

[3] Meghabghab G. Google's Web Page Ranking Applied to Different Topological Web Graph Structures .Journal of the America Society for Information Science and Technology （JAS1S），2001，52 （9）： 736- 747

[4] R.Lempel，S.Moran.The Stochastic Approach for Link Structure Analysis and the TKC effect[J].Computer Networks，2000，（33）.

[5] 王晓宇，熊方，凌波等.一种基于相似度分析的主题提取和发现算法.软件学报，2003：15791585.

[6] 庞剑锋，卜东波，白硕.基于向量空间模型的文本自动分类系统的研究与实现.计算机应用研究，2001.9（9）：23-26.

[7] 王继成，潘金贵，张福炎.Web文本挖掘技术研究.计算机研究与发展，2000， 37 （5）：513^520.

[8] A.Borodin， G.Roberts， J.Rosenthal， P.Tsaparas. Finding authorities and hubs from link structures on the World Wide Web.In：Vincent Y S， et al. eds.Proceedings of the 10th ACM-WWW International Conference. Hong Kong： ACM Press， 2001：415-429.

[9] E.P.Spertus. Mining Structural Information on the Web. Proc of the Sixth International World Wide Web Conference.1997（4）.

[10] Chakrabarti S， Gerg M， Dom B. Focused Crawling：A New Approach to Topic-Specific Web Resource Discovery. Computer Networks. 1999，31（11）：1623-1640.

[11] Davison B. Recognizing nepotistic links on the web. In： AAAI-2000 Workshop on Artificial Intelligence for Web Search.Austin Texas. AAAI Press， 2000.

[12] 黄世中.GF（2m）域SM2算法的实现与优化[J].信息网络安全，2012，（01）：36-39.

[13] 郎为民， 杨德鹏， 李虎生.智能电网WCSN安全体系架构研究[J].信息网络安全，2012，（04）：19-22.

[14] 王雷.RFID芯片在物联网应用中的设计与研究[J].信息网络安全，2012，（05）：64-67.