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

一种基于查询主题相关性的pagerank改进算法.doc—种基于查询主题相关性的PageRank改进算法
【摘要】PageRank基于链接分析计算页面的权威度，衡量网页 的权威性，实现搜索结果的等级排序。文章针对传统PageRank存在的主 题漂移问题提出了一种基于查询主题相关性的改进算法。通过引入搜索页 面与查询主题的相关性度量，有效地抑制了传统PageRank算法的主题漂 移问题，并通过实例加以验证。
［关键词】页面等级；相似度；特征项
［中图分类号】TP3 ［文献标识码】A
1引言
随着信息技术的迅猛发展，互联网成为了人们获取信息的重要途径。
通过搜索引擎，用户便能检索到大量的信息，而庞大的结果网页中，真正 对用户有用的信息并不多，用户要从结果网页中找到自己真正关心的页面 有时需要花费大量的时间。Sergey Brin和Lawrence Page于1998年提出 的PageRank算法为搜索引擎提供了变革技术。该算法以页面的链接结构 为基础，以权威度作为衡量页面等级的指标，简单、高效是一种独立于查 询的页面等级排序算法。全球最大的搜索引擎Google吸收了该算法作为 结果网页排序的核心技术。由于PageRank算法独立于查询，完全建立在 链接结构上，忽略页面与查询的相关性，因此容易导致产生主题漂移现象。 本文据此提出了一种基于查询主题相关性的改进算法，将搜索页面与查询 主题的相关性用相似度来度量，改进后的PageRank算法较传统的PageRank
算法在“主题漂移”问题上有明显的改善。
2 PageRank算法的基本原理
PageRank算法基于链接分析计算页面的权威度，衡量网页的权威性， 实现搜索结果的等级排序。该算法的有效工作需要两个假设前提。
网页被引用次数越多，网页的重要度越大或权威性越高；网页 被重要的网页引用时，重要度越大或权威性越高。
假定用户对网页集合中的每一个网页的访问都是随机的，并且 跟随网页的向外链接只能是向前浏览，不能回退浏览。此时，浏览另一个 网页的概率置为被浏览网页的PageRank值。
文献［1］中给出了传统PageRank算法的计算公式：
PR (B) = (1-d) +d (1)
其中，d是取值在0T之间的阻尼系数，。它是防止页面 的PageRank值过高或过低而引入的平衡因子。PR (Ti)为指向页面B的 页面Ti的PageRank值，C (Ti)为Ti页面的出链数。
3查询主题相关性的PageRank改进算法
鉴于传统PageRank算法得到的权威度容易脱离用户搜索的主题范围, 产生搜索结果的主题漂移，我们希望将查询主题与搜索结果页面的相关性 同时引入到对链接网页的PangeRank值的迭代计算中，并进而影响对搜索 结果的排名。
改进的PageRank算法的基本假设：网页的链接个数越多且与查询主 题的相关性越大，其PageRank值越高；网页链接不多但与查询主题相关 性大的网页，比被大量网页链接但是与查询主题相关性极小的网页的
PageRank 值高。
本文采用相似度来度量页面与查询主题的相关性，涉及到如下基本概 念：
特征项：是构成文本的基本语言单位。如字、词、词组、短语等，它 包含较多的语义信息，能够很好地用来表达文本。例如，可以用d （TL T2, T3,…，Tm）来表示一个文本d, Ti是