PageRank算法论文（通用7篇）
PageRank算法论文 篇1
1 Google search核心pagerank简介
在google的搜索结果中, pagerank值越高的网页排在越前面。网页权重的算法有很多种, pagerank是Google搜索引擎采用的搜索结果排名算法之核心 (Page et al.1998) , 且它把整个互联网当做一个整体来对待, 并最终依靠经典的数学模型精准地得到web上网页的权重。
page rank基于以下的假设 (Page et al., 1998) :
(1) 一个网页被引用 (即反向连结) 的次数越多, 则说明越重要;
(2) 一个网页虽然没有被多次引用, 但是被重要的网页引用, 则它也可能是很重要的;
(3) 一个网页的重要性被平均的传递到它所引用的网页。所以, 为了说明问题的方便, 就引出了下面这个简化了的Page Rank算法。
P (u) = (1-c) +c P (1) /N (1) +……+c P (v) /N (v) 。 (v∈Bu) 。 (Page et al., 1998)
(1-c) 实际上为了克服rank sink。这样可以推导出P= (1-c) e+c MP, 可以推导出P= (1-c) e+c MP, 即P=[ (1-c) ee T/n+c M]P (eTP=n) 。 (Arvind Arasu, 2002)
只需求出矩阵[ (1-c) ee T/n+c M]特征向量P, 就是网页集对应的最终pagerank值, 这同样可以用幂法计算。
2 基于计算器计算的幂法求矩阵特征向量 (pagerank)
现设A= (ai j) n×n有一个完全的特征向量组x1, x2, ……, xn, 其对应的特征值是λ1, λ2, ……, λn。已知A的特征值是单实根1, 即特征值满足条件
|λ1|>|λ2|≥|λ3|≥…≥|λn|
任取一个非零初始向量u0, 由矩阵A构成的向量序列
由于A的完全特征向量组实际上也是n维向量空间的一个基, 因此u0可由x1, x2, ……, xn线性表示, 即有
于是
其中
注意到|λi/λ1|<1 (i=2, 3, …, n) , 故当k→∞时, εk→∞, 因此有uk≈λ1ka1x1。 (Williams, 2011)
由于x1是主特征值1对应的特征向量, 其乘上常数因子1k a1仍为1的特征向量, 故当k充分大时, 迭代向量uk是1的特征向量的近似向量。为了利用迭代向量求出主特征值1的近似值, 设 (uk) i表示uk的第i个分量, 则
这表明两相邻迭代向量对应分量的比值收敛于主特征值, 亦即当k充分大时, 可用两相邻迭代向量的分量比作为主特征值的近似值, 即:
从上面的讨论中可以看到, 如果|1|>1或|1|<1, 迭代向量uk当k→∞时, 其不为零的分量就会趋于无穷大或趋于零。为克服这个缺点, 可以在每步迭代中加上对向量规范化的步骤, 使迭代向量各分量的数量级保持在一个稳定的量级上。
为了避免上述现象发生, 实际使用的迭代公式为:
摘要：关于google search核心pagerank的介绍以及算法推测。
关键词：pagerank,幂法,特征向量
参考文献
[1]Page, L., Brin, S., Motwani, R., Winograd, T., 1998.The Page-Rank Citation Ranking:Bringing Order to the Web.Technical report, Stanford Digital Library TechnologiesProject
[2]Arasu, A., Novak, J., Tomkins, A., Tomlin, J., 2002.Page-Rank Computation and the Strubture of the web:Experi-ments and Algorithms.In Proceedings of the Eleventh Inter-national World Wide Web Conference, Poster Track
[3]Williams, G., 2011.Linear algebra with application Seven edition.Jones and Bartlett Publishers
[4]http://www.5299shop.com/seo/sem/wenda/page-rank-update.html
PageRank算法论文 篇2
网页排序是指按照一定的算法对搜索引擎返回的结果网页进行排序,尽可能地将用户想要的网页排在前面,以便用户优先浏览[1]。网页排序算法的好坏影响着Web信息检索的准确率,是搜索引擎的核心技术之一。传统的基于内容的网页排序算法,随着互联网的迅速发展呈现出了很大的局限性:词语的一词多义往往会破坏到相关度的测量;大量网站的作弊者,使得以词频统计为核心的向量模型的相关度测算开始失效;网页之间存在独有的超链结构没有被利用,导致查询的精确度不高。
目前基于链接结构分析的搜索引擎网页排序算法主要有两类:Brin等人提出的PageRank算法[2]和Kleinberg等人提出的HITS算法[3]。PageRank算法因为是著名搜索引擎Google的核心算法而备受瞩目,这种算法通过对整个互联网结构图进行迭代运算,为搜索引擎所能爬行到的所有网页都赋予一个量化的价值度,并对网页进行了相关权威值的排序处理,从而使相对重要性高的网页排在前面。在分析Page Rank及相关算法的基础上,提出一种能有效提高搜索结果质量的网页排序算法,该算法计算网页类别的相关度,分别给来自不同类别的网页传递的权威值赋予不同的权重,并根据网页中链接所处信息块的重要程度赋予链接传递的权威值相应的权值。
2 PageRank算法分析
链接分析主要基于如下两个重要假设:超文本链接包含了用户对一个网站的判断信息;对一个网站而言,如果其他网站链接到该网站的入链数越多,该网站越重要。以下简要分析PageRank算法基本思想、特点及局限性,并对PageRank算法的一些相关研究进行介绍。
PageRank算法的基本思想是:如果一个页面被许多其他页面引用,则这个页面很可能是重要页面;一个页面尽管没有被多次引用,但被一个重要页面引用,那么这个页面很可能也是重要页面;一个页面的重要性被均分并传递到它所引用的页面。PageRank把Web看成是一个巨大的有向图G=(V,E),结点v∈V代表一个Web页面,有向边(p,q)∈E代表从结点p指向结点q的链接,结点p的出度是指从页面p出发的超链接的总数,而入度是指从所有指向页面p的超链接总数。
3 基于链接分块的PageRank算法
通过上述对PageRank及其相关算法的分析,大多数算法在进行页面排序时,基本上考虑到了网页与主题相关性对传递权威值的影响,但却没能考虑到网页类别的划分可以更有效地计算链接的价值和权威性。如何区分不同类别的网页中的链接对权威值的贡献,是计算网页权威值的一个关键因素;另外,网页中链接由于所处的位置、占据的空间大小或者内容不同而具有不同的重要度,对权威值传递的影响也不同。
基于以上思想,提出将PageRank算法的权威值计算公式将进行如下改进。
3.1 链接块分析
通常人们浏览网页的时候会发现,整个页面被分割成若干信息块,且同一信息块包含内容相似,其中既包含了相关链接块,也包含了大量噪声链接块。相关链接块中包含了与主题相关的链接,该类链接一般是对网页主题信息的进一步说明或扩充。噪声链接块包含了一般与正文主题的无关链接,例如导航链接、网站版权信息链接、服务链接、广告链接等。同一个网页中相关链接传递的权威值要大于噪声链接传递的权威值。通过对大量网页分析发现,网页中相关链接块中的链接往往具有以下几个特点:
(1)链接文字的长度基本上有规律。
(2)链接文字与其所在页面的标题具有相同的关键词。
(3)链接文字一般不会出现某些词,如“首页”,“导航”等。将不出现在相关链接中的特殊词称为相关链接停用词。
(4)链接的URL一般格式较为规整,一般不包含“Java Script”、“mail to”等特殊URL,这里将该类一般不出现在相关链接中的特殊URL称为相关链接停用URL。
根据以上特点对网页中的相关链接块和噪声链接块进行区分,具体区分规则如下:如果链接块中的某个链接符合特点(3)或特点(4),则认为该链接块是噪声块;如果链接块中的所有链接都不符合规则(3)和规则(4),则认为该链接块是相关链接块;如果链接块中的某个链接与特点(2)符合,则认为该链接块是相关链接块。在对网页中的链接块进行区分后,然后对链接块中的链接赋予一个权值w来描述其重要性,假设链接j属于相关链接块,那么w=0.8,如果链接属于噪声链接块,那么w=0.2。
3.2 Page Rank算法的改进
对网页中的相关链接块和噪声链接块进行区分后,根据网页中重要的信息块中的链接传递的重要性高于不重要的信息块中的链接,对PageRank算法做进一步的改进,根据链接所属信息块重要性的不同赋予相应权值w。改进的PageRank算法被称为BPageRank算法。BPageRank算法计算公式如下所示:
其中,wi用来表示链接Ti的块重权值。如果Ti是相关链接块中的链接,则w=0.8,如果Ti是噪声链接块中的链接,则w=0.2。
BPageRank算法在计算权威值时,不仅考虑到了网页分类特性对权威值传递的影响,也考虑了相关链接对权威值传递的影响。
4 实验结果及分析
4.1 实验设置
实验选择“高等教育”作为主题,收集教育类网站30个,无关网站20个组成样本集,共有大约18000个页面;以“研究生”“英语六级”“多媒体教学”“考研”“计算机”5个不同查询词作为测试的输入参数。实验利用基于关键词匹配的算法在样本集中分别产生针对5个查询词的5个结果网页集合,然后再利用PageRank、BpageRank两种算法对5个集合进行排序。
评价指标采用TopN准确率(检索结果中排在前面的N个网页的准确率),即前N个网页中符合要求的网页数与N的比值[5]。根据北京大学的网络与分布系统研究室对北大天网系统的研究发现,用户在第1页点击数占总点击数的47%,本文只对检索结果中排在前面的20个网页的准确率进行分析。至于如何确定给定网页是否符合要求,则是一个非常主观的概念,目前广泛采用的方法仍然是人工评价[4],本文也采用了类似的评价方法:取每个算法的运行结果中排序在前20以内的网页,合并成待评价的网页集,将该集合中的网页以随机的次序提交给10个志愿者进行评价。网页的主体内容是关于查询主题的,则认为是相关网页,相应的评价值为1,否则为0。当网页相关性的评价值之和大于7时,判定该网页为相关网页,否则为不相关网页。
4.2 结果分析
实验结果数据显示,PageRank算法获取主题相关网页的准确率的平均值为51%,BPageRank则把准确率提高到了71%。改进后的网页排序算法BPageRank可以更加准确地判断网页的相关性,返回更加符合查询主题的结果。
5 结语
搜索引擎是检索Web信息的最重要工具,网页排序算法的研究有助于提高搜索引擎的准确率,具有重要意义。提出一个基于PageRank网页排序算法CBPageRank算法,实验结果表明,相对于PageRank算法,该算法能够提高搜索引擎的准确率。从算法复杂度来看,CBPageRank算法的网页分类和网页中链接块分析都是离线完成,因此在线查询时的计算量与PageRank算法完全一样。而离线的计算量相对于PageRank的略有增加。所以CBPageRank是一个可行的,伸缩性好的算法。今后工作重点考虑进一步提高类别之间相关性的计算的精度,结合语义网络的研究,使用语义进行更为有效的分类和相关性计算。
摘要：提出一种基于PageRank的页面排序算法。采用网页类别相关度计算,对来自不同类别网页所传递的权威值赋予相应的权重;根据链接所属信息块重要性的不同,赋予相应权值。实验表明,该算法对提高页面排序质量是有效的。
关键词：页面排序,PageRank,相关度计算
参考文献
[1]肖明军,黄刘生,罗永龙.SHITS:一种基于超链接和内容的网页排序方法.小型微型计算机系统[J],2006,27(12):2177-2180.
[2]Brin S,Page L.The Anatomy of A Large-scale HypertextualWeb Search Engine[J].Computer Networks and ISDN Sys-tems,1998,(33):101-107.
[3]Kleinberg J.Authoritive Sources in A Hyperlinked Environ-ment[J].Journal of the ACM,1999,46(5):604-632.
[4]Bharat K,Henzinger M.Improved Algorithm For Topic Distil-lation in a Hyperlinked Environment[C].Proceeding of 21stAnnual InternationaI ACM SIGIR Conference on Research andDevelopment in Information Retrieva1,1999,46(5):604-632.
PageRank算法论文 篇3
关键词：Web挖掘,搜索排序算法,链接结构,PageRank,相似度
基于链接结构的搜索排序算法是Web结构挖掘技术的产物。搜索引擎将PageRank值与网页搜索结果相似度共同作为搜索结果的排序依据。简单PageRank算法描述如下:将网络看作一个有向图:G=(V,E),其中V是节点网页集[1],E是边(当且仅当存在从页面i到页面j的链接时存在从节点i到节点j的边)集。PageRank的基本思想在于一个页面重要或者有链接指向它的页面多,或者有链接指向它的页面重要或者二者兼而有之。其初始定义如下:
其中Np表示节点p的出度[2]。
在计算PageRank时,一般把它看作一个求矩阵特征向量的过程:M表示G的过渡矩阵,如果存在节点j到节点i的边,则置矩阵中元素mij的值为1/Nj,否则置为0。这样,最终的结果满足:x=Mx。
其中x表示各页面的PageRank构成的向量,由M的构成可知,矩阵M的最大特征值为1,x为1对应的特征向量。这样可以用简单迭代法对上式求解[3]。如果有2个相互指向的网页a,b,他们不指向其它任何网页,另外有某个网页c,指向a,b中的某一个,比如a,那么在迭代计算中,a、b的rank值分布出去而不断的累计,如图1。
用M’代替M进行计算,相当于在G的每两个节点间增加了两条边,这样做的同时也解决了所谓的Rank Sink问题,此时的迭代形式如下:
这样,在保证迭代收敛的同时,也使PageRank的定义变为:
设页面T1,T2,…,TN有链接指向页面A:
此时,PageRank的定义符合随机冲浪模型[4]。
另外还有一些特殊的链接,指向的网页没有向外的链接。PageRank计算时,把这种链接首先除去,等计算完以后再加入,这对原来计算出的网页的rank值影响是很小的[5]。由公式可知计算某个网页的PageRank值总是依赖于其他的相关页面,所以计算PageRank值实际上是一个迭代的过程,计算结果的精确程度依赖于初值的选取和迭代的次数[6]。对于初值一般取1,而为了保证实际应用中这个结果总是收敛的,则加入了阻尼系数d(一般为0.85)。
1 PageRank算法的优化
基于上面对PageRank基本算法的分析,下边讨论的重点不在单个网页的权值,而是考虑整个网站或者说网站中的重要页面的PageRank值,这些页面可能是索引页,中心页或是专门为某些搜索术语优化的页面。
1.1 内部链接
网站PageRank值即为网站内部所有页面PageRank值的和。一个网站的PageRank最大值等于它的页面数量。入站链接可以增加这个最大值,而出站链接则能减少之。所以从根本上来说网页要有一定的质量。下面分析一下网站内部链接如何影响PageRank值,在这里我们考虑的是一个相对独立的网站,入站链接和出站链接的影响暂不考虑在内。
假设一个包含三个网页的网站,没有外部链接。在I II III的情况下,我们为每个网页分配初值1,阻尼系数保持与Google一致(0.85),经过迭代收敛后,得到三种情况的PageRank值如表1。
网站I的PageRank值为0.45,严重浪费了潜在的PageRank值。II的情况稍好一些,总值0.5775比上一个例子有所增加,但仍然只是最大值的一小部分(对于该结构存在的摇摆页情况,在这里不作讨论)。在III的链接结构下,网站达到了PageRank最大值,同样的结果也可以通过环形结果获得:A到B,B到C,C再到A。由此得出针对内部链接结构的第一个优化方法:一般来说,环形链接或者任意两个页面都有相互链接时能达到PageRank大值。考虑到前面说的索引页,有下面两种情况:假设把A作为索引页,有下面两种链接结构,省略计算过程后迭代结果如图3。
两种结构的总值仍然是3(最大值)所以没有浪费。但第II种情况下,A明显损失了PageRank,页面C也损失了一部分PageRank因为A、B分享方式替代了A独享,A通过A->C链接反馈回C的值也就减小。
所以得出第二条优化方法:为了获得索引页的最大PageRank值,其他页面应该尽可能减少相互链接。如果某个页面链接到的页面有回路链接,那么在这个页面上增加一个新的出链接会导致间接损失一部分的PageRank值。如果没有这样的回路,则不会减少PageRank值。这在内部链接中并不十分重要,但在发生到网站外的链接时就不一样了。
1.2 入站链接
入站链接(由网站外部进入的链接)是增加网站PageRank值的方式之一。入站链接来自何处并不重要,例如:如果是一个PageRank值为2的网页的唯一出链接,将得到0.15+0.85(2/1)=1.85的值;而一个100个出链接的PageRank 8网页,得到的是0.15+0.85(7/100)=0.2095。很明显,PR2链接更有效。一旦有PageRank值注入到网站中,计算将需要重新进行。某些页面的值增加,某些保持不变,这依赖于内部链接结构,但肯定不会有页面会损失PageRank值。看下面的例子:假设一个由4个网页:A,B,C,D环形链接组成的网站,在没有入站链接的情况下,可知每个页面PageRank值均为1。这时我们增加一个指向A的入站链接X,我们假设X的PageRank值为常量10,而且X->A的链接是X仅有的出站链接,在阻尼系数为0.5的情况下,得到如图4的入站链接。
可见由X注入的PageRank值0.5*10被分配到了各个网页之中。
若将阻尼系数改变,则可以想象由X注入的PageRank值将增加,网站的PageRank值会有进一步的提升。由上分析可见,任何一个入站链接几乎都可以增加网站的PageRank值。可是怎样利用这个增量却是一个问题。入站链接指向你试图导向的重要页面更有好处,如果PageRank注入到其他页,则会因为内部链接分散到网站中。索引页也会得到提升,但不如直接链接提升得多。直接得到入站链接的页面得到的值最大。第三条优化方法:将网站索引页作为引入入站链接的最佳目标。
1.3 出站链接
出站链接会导致网站PageRank值的消耗。为了抵消这种消耗,需要确保链接是互给的。互惠链接可能得到也可能损失PageRank值,所以交换链接时需要特别小心。
当PageRank值随着指向另一个网站的链接而引出时,内部链接的所有页面都将受到影响。虽然具体的PageRank值变化情况依赖于链接结构,但一般来说给出链接的网页往往是损失PageRank值最大的。因此得出第四条优化策略:出站链接放在PageRank较低的页面,造成的PageRank损失较小。
例如:
成都东软信息职业技术学院此外,action属性甚至可以不必位于form表单而在javascript代码中,而javascript代码可以位于存储路径的js目录下,而该目录一般Google的spider程序都不访问。
基于Robot的搜索引擎从初始网页出发,顺着网页的链接进行查找,当到达一个新网页时就在其
、
参考文献
[1]Jullen G,Stefan MR.Link-based Approaches for Text Retrieval[J].Proceedings of TREC-10,2001:13-16.
[2]李凯,赫枫龄,左万利.PageRank-Pro一种改进的网页排序算法[J].吉林大学学报(理学版),2003,41(2):175-179.
[3]R.Motwani,P.Raghavan.Randomized Algorithms[M].United Kingdom:Cambridge University Press,1995.
[4]Sergey Brin,Lawrence.Page.The anatomy of a large-scale hypersexual web search engine.Proceedings of the Seventh International World Wide Web Conference.page107-117,Brisbane,Australia,April1998.
[5]Taher H.Haveliwala.Efficient Computation of PageRank[J].Stanford University,1999,31.
[6]Krishna B,Andrei B,Monika H,etc.The Connectivity Server:Fast Access to Linkage information on the Web[J].Computer Networks,1998,30(1-7):469-477.
[7]Phil Craven.Google’s PageRank Explained and how to make the most of it[J/OL].http://www.webworkshop.net/,2006.
PageRank算法论文 篇4
Web是人们获取信息的重要资源之一, 传统的搜索引擎在技术上已经不适应海量的Web资源查询, 为解决Web搜索引擎所存在的问题, 人们提出了Web数据挖掘概念, 并在实践中取得了很好的效果。
Web结构挖掘, 简称WSM, 指通过分析不同页面之间的超链接结构, 网页内部的可以用XML、HTML表示成树形结构, 以及文档URL中的目录路径结构等, 发现许多蕴涵在Web内容之外的、对我们有潜在价值的模式和知识的过程。
目前WSM主要应用有:
*搜索引擎查询结果的排序;
*查找相关文档;
*计算Web页面Reputation;
*确定某站点的主要内容和特征;
*Web Crawler的URL爬行的优先顺序。
2. WSM的链接分析技术
用户在Web上使用搜索引擎进行信息搜索时, 最关心的并不是返回结果的多少, 而是检索结果是符合自己的需求。许多研究者发现, Web页面的链接结构是非常丰富和重要的资源, 如果能够充分利用, 可以极大地提高检索结果的质量。
Web页面有三个重要组成部分:网面内容、网页所含的超文本标记及网页间的超链接。一般说来, Web文档中的超链接包含了两种信息:首先, 它为用户提供了浏览Web的导航信息, 用来指引访问者在各页面之间跳转;其次, 页面中的超链接往往是文档作者对于某一文档的推荐, 被推荐的目的文档往往与该文档有相似内容而且被作者所认同。后者构成了链接分析的基础, 即某一文档的重要性不由文档的内容决定, 而取决于被其他文档链接 (或者引用) 的次数。这种评价机制类似于科学论文中的参考文献:被引用次数多的论文其重要性比引用次数少的论文要高。在Web检索中, 除了被其他文档链接的次数外, 链接源文档的质量也是评价被链接文档质量的一个参考因子:被高质量文档链接或者推荐的文档往往具有更高的权威性。这就是Web结构挖掘中基于超链接结构的链接分析技术的理论基础。
3. 独立于查询的算法———PageRank
PageRank算法是Web超链接结构分析中最成功的代表之一, 是评价网页权威性的一种重要工具。搜索引擎Google就是利用该算法和anchor text标记、词频统计等因素结合的方法对检索出来的大量结果进行基于权威值的排序处理, 使最重要的网页出现在结果的最前面。其中, PR值 (权威度) 越高的网页, 在结果中出现的位置越前。
PageRank的理论基础是:忽略掉Web页面上的文本和其它内容, 只考虑页面间的超链接, 把Web看成一个巨大的有向图。
如果页面u包含一个指向页面v的超链接, 即存在link (u, v) 。这里页面间的超链接构成了一个有向图G:对于每个页面构成有向图G的一个节点;当且仅当u中包含指向页面v的超链接时, 存在着从u到v的有向边 (u, v) 。有向图G如图1:
对于节点v来说, 节点b, c, u对于v的权值大小有贡献, 因为这三个节点都存在到v的有向边。指向某一节点的有向边越多, 其节点 (页面) 质量越高。这种简单的算法的主要缺点是仅仅考虑的链接数量———所有的链接都是等价的, 而没有考虑源节点自身的质量即权值高低。Web中文档之间超链接的情况往往是高质量的文档中包含高质量的链接, 源节点的质量对于被链接文档质量评价的作用往往高于数量上的影响。
为了解决链接数量和源节点的质量问题, Sergey Brin和Lawrence Page提出了PageRank算法:某一Web页面的PageRank值等于所有包含指向该页面的源文档的PageRank值与页面链接总数之比的和, 即:
其中d取值是0到1之间的衰减因子, 在Google中取值为0.85;
∑j→v作用于所有链接向网页v的网页集合j (图1中的b、c、u) ;n为有向图G中节点的数目;
outlink (j) 为网页集合j指向所有节点的超链接数目;
PR (v) 为节点v的权威度。
PageRank算法的实现过程为:将网页的URL对应成唯一的整数, 把每一个超链接用其整数ID存放到索引数据库中, 经过预处理 (如去除数据库中的悬摆指针) 之后, 设每一个页面的PR值为1, 通过以上的递归算法计算每一个网页的PR值, 反复进行迭代, 直到结果收敛。
PageRank算法除了对搜索结果进行排序外, 还可以应用到其它方面, 如估算网络流量, 向后链接的预测器, 为用户导航等。
Google是结合文本的方法来实现PageRank算法的, 所以只返回包含查询项的网页, 然后根据网页的PR值对搜索到的结果进行排序, 把PR值最高的网页放置到最前面, 但是如果最重要的网页不在结果网页集中, PageRank算法就无能为力了。
4. 结语
在Web结构挖掘中, 对超链接的分析算法是重要的研究方向。“权威性”是链接分析算法的对页面进行自动分析的重点, 但目前的算法都是对不同的链接赋予相同的权重, 如何根据文本内容的相关性, 为相应的超链接赋予不同的权重, 即把Web内容挖掘和Web结构挖掘进行合理结合, 是一个值得继续深入研究的问题。
摘要：本文首先介绍了Web结构挖掘技术在Web中的应用, 其次陈述了Web结构挖掘技术中的经典链接分析算法PageR-ank, 最后分析了PageRank在网页搜索中具体实现的方法。
关键词：Web结构挖掘,PageRank算法,网页搜索
参考文献
[1]王晓宇, 周傲英.万维网的链接结构分析及其应用综述[N].软件学报, 2003, 14 (10) :1768-1780.
[2]宋建康, 张礼平.Web结构挖掘算法探讨[N].华东理工大学学报, 2003, 28 (5) :537-540.
[3]曹军.Google的PageRankWeb技术剖析[N].情报杂志, 2002, 10:15-18.
PageRank算法论文 篇5
网络就是一个由无数个超链接而连接起来的结构体, 可以说没有超链接就没有网络。Web结构挖掘技术主要就是通过对这些超链接进行分析, 将潜在的语义信息明确表示出来。对用户而言, 他们使用搜索引擎进行搜索不只是希望找到所需要的信息, 而且希望找到高质量的信息, 这些信息具有权威性。搜索引擎怎么确定一个网页是否是权威的呢?这个问题就是Web结构挖掘的问题。Web结构挖掘主要有两种方法: (1) 页面等级算法 (PageRank算法) :页面等级算法先对检索主题进行检索, 然后根据链接关系计算检索结果的页面等级, 一般被重要网页链接的网页被认为是重要的, 被多数网页链接的网页也是重要的, 然后按重要性进行排序后输出; (2) 关键页/权威页算法 (hits算法) :关键页是指那些没有被多个网页链接, 但是它存在着在某个专业领域重要的站点链接, 它主要是起到说明其他文档重要性的作用。权威页是指那些被多个网页链接的网页, 一个关键页往往包含很多权威页的链接。将关键页与权威页的这种联系按照算法计算出来, 就是关键页/权威页方法的主要思想。
搜索引擎通过结构挖掘, 可以使用户优先看到那些比较权威的页面。
2 Web使用挖掘技术在搜索引擎中的应用
Web使用挖掘技术主要体现在对日志的挖掘上, 通过对用户日志信息的分析, 得到数据对象间的内在特征, 并以此为依据进行有目的的信息提取, 将这些信息使用在搜索引擎中, 使得搜索引擎可以按照用户的兴趣偏好优先选择某些网页或者扩充搜索范围, 以使得检索结果更接近用户要求, 提高用户检索的查全率与查准率。
3 PageRank算法思想
PageRank是由Stanford大学的Sergey Birn和Larry Page在《大规模超文本网络搜索引擎的剖析 (The Anatorny of a Large-Scale Hypertextual Web Search Engine) 》一文中首先提出的一种算法, 它在检索到网页后, 按照一定的算法给每个网页一个重要性值, 并按这个重要性值对检索结果进行排序。
PageRank的基本思想是:一个页面被多次引用, 则这个页面很可能是重要的, 假如页面A被页面B引用, 则B就认为A是重要的, 也就相当B于投了A一票, 如果A被多个页面引用, 则就是多个页面投了A的票, 它们都认为A是重要的, 那么A一般是重要的;一个页面尽管没有被多次引用, 但被一个重要的页面引用, 则这个页面很可能也是重要的, 因为PageR-ank算法把一个页面的重要性均分并被传递到它所引用的页面, 这样被重要页面引用的页面就可以分到更多的重要性值, 它被入链推荐的能力就越大。因此, 网页之间的超链接 (引用) 关系在一定程度上能表明Web文档的重要性。
3.1 PageRank算法的数学实现
PageRank完全不重视超链接文本的相关性和网页内容与主题的相关性, 只考虑页面之间的链接关系, 把Web看成是一个巨大的有向图G= (N, E) , 节点n包含于N代表一个Web页面, 有向边 (a, b) ∈E代表从节点a指向节点b的超链接, 节点a的出度是指被页面a引用的页面的总数, 而入度是指所有引用节点a的页面的总数。设b->d表示在图G中, b到d存在一条链接, out (b) 表示b的出链的个数, 那么在当前网页随机选择网页d进行浏览的概率1/out (b) 。假设两个网页之间是否存在链接使用Pb, d表示, 如果存在则Pb, d=1, 不存在则为0, 因此图N中所有两个结点b, d间的连接关系可以用一个n维的矩阵表示, 其中n是总网页节点的个数。由此定义图G的随机过渡矩阵M定义为Mp, q=Pb, d/out (b) 时, 就是一个矩阵求特征向量的过程, 即:
其中x是各个页面的PageRank值的列向量, 这样迭代计算得到的解就是要求的页面的PageRank值, 但是要保证迭代过程是收敛的, 必须保证邻接图M是不可约的, 即N是强连通的, 但是这是不符合实际情况的, 为了解决这个问题, 为每个结点再加上一个数值较小的概率值, 形成一个完全变换图。
其中d为某个概率值。d的作用是, 在任一时间, 一个冲浪者访问某些结点时, 不是顺着链接继续浏览, 而以概率1-d跳到另外一个随机页面。
由此PageRank的计算公式可以定义为:
其中PR (A) :页面A的重要性, 即页面A的PageRank值,
PR (Li) :页面Li的重要性, Li是引用页面A的页面,
Out (Li) :页面Li引用的页面个数,
d:阻尼系数, 一般为0.85。
3.2 影响PageRank的因素
由式3可见, PageRank算法中页面的重要性由引用它的页面的网页重要性以及该页面引用的页面个数决定, Li页面的引用的网页越多, 它对当前页面A的贡献就越小, 反之越大;由于用户在当前网页浏览时也有可能会因为疲劳、厌倦或其它原因选择别的网页去浏览, 而不浏览当前网页的链出网页, 阻尼系数的应用就是为了给这些没有被当前网页链接的网页一个跳转概率。阻尼系数的大小是通过对用户行为进行分析设置的, 在计算PR (PageRank) 值时是一个常数, 所以PR值的大小主要受出链和入链的影响, 如图1所识:
3.2.1 入链计算页面PR值的影响
链入的网页总是能增加当前页面的PR值。如图3。1所示的链接关系, 可以算出这三个页面的PR值都是1。如果增加一个从页面D到页面A的链接, 那么页面A的PR值就会增加d*PR (D) /Out (D) , 其中PR (D) 是页面D的PR值, Out (D) 是D的出链个数, d是阻尼系数, 一般为0.85。
可以得到以下方程组:
解得:
可以看出D页面传递给了网站中A页面的PR值d*PR (D) /Out (D) =0.85*2=1.7。而页面A的PR值的增加又传递给了B, B又传递给C, 最后C的PR值的增加进而又使A的PR值增加。
3.2.2 出链对PageRank值的影响
既然PageRank算法就是基于链接 (引用) 关系的算法, 所以引用和被引用都应该对PR值有影响, 下面我们通过例子说明引用别的网页对PR值的影响。假设刚开始是A、B、C页面组成的如图2所示的去除D的链接关系图, 则容易算出
如图2所示, 有3个如图所示组成链接关系的网页, 加入B引用的一个页面D,
取阻尼因子为0.85, 由图得出如下方程组:
解方程组得:
可以看出如图3.2所示的链接关系, 减少了整个网页的PR值的总和, 即所有页面的PR值总和不收敛, 当然并不是所有的都不收敛, 如图3所示:
假设阻尼系数为0.75, 由图3.3的链接关系可得方程组:
解方程组得:
可以看出, 在没有添加P->Q之间的链接的时候, 每个页面的PR值都是1, 由这四个页面组成的网络的PR值的总和为4, 在P到Q之间链接添加以后, 页面PR值的总和还是4。
由上面两个例子可以看出增加一个对别的网页的引用, 有可能会使页面总PR值不收敛, 也可能是收敛的。
4 改进PageRank算法
由于搜索引擎自身没有办法完全理解用户的意图, 往往只要与搜索主题有一点关系的网页也会被检索到, 这样就导致了搜索的结果条数过多, 而人们只选择排名比较靠前的几个网页进行浏览, 对某大型网搜索引擎进行的统计如表1所示:
调查数据表明:用户对前5页的点击率就占到总点击率的75%, 这就是为什么搜索引擎要将最重要的网页尽量往前排列的原因, 而这个重要性最主要就体现在与主题的相关性方面。一般情况下, 用户看到的只是超链接文本的内容, 而看不到链接出来的网页的具体内容, 而超链接文本在一定程度上也反映了网页的内容, 所以凭主观判断, 应该是超链接文本与搜索主题越相关, 该链接被点击的可能性就越大, 而不是Lawernce Page和Sergey Brin所说的随机从链接中选择一个页面进行浏览。华盛顿大学计算机Matthew Richardson和Pedro Dominggos认为用户从一个网页跳到另一个网页是受到当前网页内容和正在查询的主题的影响的, 所以提出了一个结合链接和内容信息的PageRank算法, 在对现有文献及改进算法的了解了解的基础上, 本改进算法也是从改进PageRank算法与主题的相关性方面进行着手, 根据主题与超链接文本的匹配程度来设置超链接文本相关系数Whyperlink, 根据主题在网页中出现的位置设置内容相关系数Wcontent。
算法思想:假如搜索主题完全和超链接文本匹配, 设置Whyperlink为1, 主题完全包含在超链接文本里, 设置为Whyperlink0.8, 主题部分包含在超链接文本里, 设置Whyperlink0.5, 不包含在超链接文本里, 设置Whyperlink为0.2;由于超链接文本的内容有可能具有欺骗性, 有些广告商为了让更多的用户浏览自己的网页, 使用用户比较喜欢的虚假链接来吸引用户点击, 而网页的内容完全和主题不相关, 所以在分析超链接文本的同时, 加入网页内容中对查询词的分析。参考EPR算法内容权值的设置, 初始内容相关系数Wcontent设为0, 如果搜索主题在
中出现, Wcontent增加1.8, 在搜索主题在中出现, Wcontent增加1.5, 在其他位置出现, Wcontent增加1, 在以上这些位置均未出现的增加0。
那么对某个链接分配的权值就是主题与超链接文本的相关性和内容与主题的相关性的乘积, 因为只有选择了该超链接进行浏览, 判断网页内容是否相关才有意义。
5 实验仿真
整个实验包括数据的采集、预处理、算法计算和实验结果进行比较四个部分。整个实验系统包括数据采集模块、网页预处理模块、建立索引模块、离线计算模块、显示结果模块, 系统结构如图4所示:
实验结果表明, 在链接关系影响不是很大的情况下, 得到的排名也较为理想, 加入相关性因子后, 本来PageRank值较低、排名靠后的网页, 赋予其更高的相关系数后, 排名就往前移了, 比如页面N1本来排名为8, 但在改进的算法中排名为1, 这是因为我们赋予了它跟主题更大的相关性系数, 在PageR-ank算法中过渡矩阵平分链入网页的PR值, 网页N1分到的PR值是链入网页的1/n, 其中n是网页N1的某个入链网页的链出网页个数, 而改进的算法按相关性分配PR值, 网页j分到的PR值是链入网页的α倍。
其中, B (j) 是网页j的某个入链网页的链出网页集合, 是网页j的链接文本与主题的相关性系数, 是网页j内容与主题的相关性系数, 可以看出分配较高的相关性系数, 必然占分配的概率就大, 所以就提高了该分到的链入页面的PR值, 经过无数次循环迭代后, 最终也提高了该页面的PR值。但是得到的排名靠前的网页就是我们需要的网页吗?分配较高相关性系数的网页就是与主题最相关的网页吗?我们通过对实验的网页的分析, 以及网上存在的网页的分析得知:与主题相关的程度基本与我们分配的网页的相关度成正比, 通过多次试验得出的结果显示, 往往排在前面的是跟主题相关度比较大的网页。实验表明改进后的算法是可行的, 是符合人们的期望的。
6 结束语
目前的搜索引擎不能完全帮助人们找到最需要的信息, 存在一些弱点, 新兴的Web数据挖掘技术就是为解决这一难题而出现的, Web数据挖掘根据挖掘对象的不同可以分为3种:结构挖掘、内容挖掘和用户使用挖掘, 其中对超链接文本和网页内容进行的挖掘就是内容挖掘的一个方面。Web内容挖掘也叫文本挖掘, 它是通过对文本进行分析, 可以对网页进行聚集、分类, 帮助人们找到最相关的信息。本文要在原来的结构挖掘比较成熟的PageRank算法中加入内容挖掘的元素, 以使该算法更符合人们的要求。
本文首先对搜索引擎进行了概述, 并由此引出Web数据挖掘的概念, 主要讨论了Web数据挖掘的现状、前景及其在搜索引擎中的应用。Web内容挖掘也就是文本挖掘, 是本文讨论的重点。传统的PageRank算法是基于链接分析的、结构挖掘的算法, 由于该算法完全忽略了内容的相关性, 所以不可避免地导致了“主题漂移”问题的产生。针对这些问题本文提出了一种新的改进的方法, 此算法考虑到用户的点击兴趣 (用户一般倾向于点击超链接文本和主题相关性大的链接) 和文本相关两方面的问题, 并对该算法进行了模拟实验。
鉴于网络资源的庞大, 链接关系的复杂, 考虑到时间仓促, 所以, 本实验采用的是从网络上提取同一主题下的一小部分网页, 并对它们进行了整理和保存相关信息, 由于页面数量比较少, 所以很难和网络上的链接关系保持一致, 实验采用了手动构造链接关系的方法, 在小范围内进行了模拟, 使用程序获取模拟的链接关系图, 并进行了计算。
该算法可能产生问题的地方在于:有些网页链接不一定是规范并且符合常识的, 这样就影响判断出链接文本和主题的相关度, 进而影响整个排名。
由于时间紧张, 模拟环境的有限, 所以改进算法是否在整个网络环境中使用还有待商榷, 并还有可改进之处, 比如有些近义词就无法识别, 以后有时间的话希望能把语义识别加到该算法中, 使排序算法能理解人类的语言, 更加智能化。
参考文献
[1]朱丽红, 赵燕平.Web挖掘研究综述[J].情报技术, 2004 (7) .
[2]Rieardo Baeza-Yates.Paolo Boldi and Carlos Castil-lo.Generalizing PageRank:Damping functions for link-based ranking algorithms[J].ACM.SIGIR'06, 2006 (8) .
[3]江裕民.基于超链接的Web结构挖掘算法的研究[D].陕西:西安电子科技大学, 2006.
PageRank算法论文 篇6
目前在搜索引擎中常用的页面排序方法是PageRank[1]方法,利用web页面间的超链结构来计算每个页面的权重。但是PageR-ank算法会忽略某些页面的内容,一些与用户兴趣无关的知名网站也会被赋予过高的权重。致使用户很难从中快速筛选出真正需要的信息。如果搜索引擎只返回相关度高的重要网页,这样既可以很大程度地节省用户时间,又可以减轻网络流量。
文中提出了一种基于向量空间模型的主题PageRank页面排序算法,结合基于内容和基于链接分析权重各自的特点,构造出主题PageRank算法。
2 PageRank
2.1 PageRank理论模型
PageRank的基本思想来自传统文献计量学中的文献引文分析,即如果一个页面被多次引用,那么这个页面很可能是重要的;如果一个页面尽管没有被多次引用,但是却被一个重要的页面引用,那么这个页面很可能是重要的;一个页面的重要性被均分并传递到它所引用的页面。基于这种思想:设u是一个web页面,Fu是u引用的页面集合,Bu是引用u的页面集合,则网页u的重要性R(u)可定义为:
其中,Nu表示u引用的页面个数,c为规范化因子。
2.2 修正的PageRank算法
公式(1)有一个假设前提:所有的页面链接形成一个强连通图。但是实际的网络超链接环境没有这么理想,会存在一些没有外出链接的独立页面或页面集合,这种页面称之为悬挂页面(dingle page)。因为这种页面没有外出链接,所以在迭代计算的时候页面的重要性时,它不会传出任何重要性,这将导致一个称之为等级泄露(rank sink)的重要问题。为了解决这个问题,必须引入一个等级源[2](rank source)来补充每个页面的PageRank值,以使得PageRank值不完全依赖于网络链接。因为浏览者在网络上浏览网页的过程实际是一个随机的过程,浏览者很少会沿着一个链接向下一直走到底。在每一个页面,浏览者都有可能不再对本页面的链接感兴趣,从而随机选择一个新的页面开始新的浏览。所以修正后的PageRank定义为:
公式(2)中的等级源E一开始是为了修正页面间的等级泄露而设计的,后来Page和Brin又提出了E在调整页面的排列顺序方面的作用。它认为浏览者每一次在随机选择一个新的页面并开始新的浏览时,都会与个人的兴趣有关。于是可以根据不同浏览者的喜好,构造不同的等级源E,从而提出了PageRank在主题个性化方面的应用前景。
3 利用空间向量模型构造个性化的PageRank算法
从上面的分析,我们可以看到主题PageRank的关键就是等级源的构造。通过对每一个页面进行基于主题的分类,然后针对每一个主题分别计算出对应主题的主题性页面等级得分,构造出面向不同浏览者的等级源E。
3.1 VSM
文本的特征表示是文本分类面临的首要问题。向量空间模型VSM[3](Vector Space Mode1)是目前应用最多且效果较好的文本表示法之一。VSM引入了线性代数中的某些概念,主要思想是选出若干独立的词项作特征项,每一篇文档都被映射成多维向量空间中的一个向量,对于所有的文档类和未知文档,都可用此空间中的向量Dj(w1,j,w2,j,…,wt,j)来表示。其中,t是系统中所有特征项的个数。wi,j为特征项ki在文档dj中对应的权值,用以刻画该特征项在描述此文档内容时的重要程度,使用公式进行计算:
其中,tfij表示特征项ki在文档Dj中出现的频率,N代表文档集合中的文档数量,nj代表在文档集合中出现特征项ki的文档数目。
从而将文档信息的表示和匹配问题转化为向量空间中向量的表示和匹配问题来处理。那么,就可以使用向量空间模型来计算文档之间的主题相关程度。这种关系可以定量表示,一般用这两个文档生成的空间向量之间的夹角余弦值来计算。即
3.2 特征项的选择
构成网页中的文本的词汇,数量是相当大的,因此,表示网页的向量空间的维数也相当大,可以达到几万维,所有几万个词汇对网页分类的意义是不同的,因此我们需要进行维数压缩的工作,也就是进行特征项的选取。特征选择的基本思想通常是构造一个评价函数,对特征集的每个特征进行评估。这样每个特征都获得一个评估分,然后对所有的特征按照其评估分的大小进行排序,选取预定数目的最佳特征作为结果的特征子集。
互信息量法[4](mutual information)是一种常用的评价函数,MI用于度量一个消息中两个信号之间的相互依赖程度。在特征选择领域中,特征t和类别C的互信息体现了特征与类别的相关程度。在某个类别C中出现的概率高,而在其它类别中出现的概率低的特征t将获得较高的互信息。MI可表示为:
其中P(w|Ci)是训练语料中特征项W出现在类别Ci中的频率,P(w)是训练语料中特征项W出现的频率。经过比较之后,选择互信息量大与设定阈值的特征项作为该类的类别特征。
3.3 迭代计算PageRank值
为了方便计算网页集合中所有页面的PageRank值,通常采用线性代数的理论,利用公式(2)来计算。把页面的PageRank值表示为向量R,用户的兴趣矩阵表示为E,其中Eij=sim(di,Cj)。那么可以得到,
其中,假设有n个网页,A是一个n×n的矩阵,其元素aij为鼠标点击一次时从i页到j页的概率。最简单的模型是取aij=|Oi|,这说明这意味着无论从哪个网页开始,它通过任一外链接到达其他网页的概率几乎是相同的。
进一步分析公式(5),发现矩阵A某些行的元素可能都是零,所以矩阵A不一定是随机矩阵。这种情况会在网页没有外链接(即aij=0)的情况下发生。许多这样的网页是存在的并被称作悬挂页面。一种简单的解决办法是用e T/n[4]来替代这些零向量,其中e T是元素都为1的行向量。被修正的矩阵A’(现为随机的)可以看作是矩阵A的秩1修正矩阵。令a为悬挂向量,其元素为
那么,A’=A+aeT/n(8
把修正后的A’带入公式(5),得到
由于修正后的A’是随机且不可约的,因此可以保证向量R可以收敛到一个稳定的值,并且该向量与初始值的取值无关。于是可以假设S为初始网页向量,每个分量的值都赋予1/n,然后根据公式(9)反复迭代计算,直到最后得到的PageRank值收敛于一个相对固定的值,Brin和Page的报告中成功迭代的收敛速度是50到100步[2]。
4 实验结果与分析
文中的训练集来自中文自然语言处理开放平台上用于文本分类的语料库,该语料库来自复旦大学计算机信息与技术系国际数据库中心自然语言处理小组。从中选取了计算机、环境和体育3个类别,其中计算机方面的文档有1357篇,环境方面的文档有1217篇,体育方面的有1253个。测试数据来源于使用网络爬虫框架Heritrix抓取得到的5000个页面。为了验证上述改进算法,本文对随机的关键词进行20次查询,在返回的前100个结果中,统计符合
查询的网页篇数,实验的结果如图1所示。
从图1可以看到本次实验使用主题PageRank算法排序的查询精度在45%左右,要好于传统的PageRank算法。
5 总结
本文将VSM文本分析模型引入PageRank算法,构造出基于主题的PageRank算法。并通过实验证明该算法对页面主题分析的能力有了改善,因此查询精度方面也得到了相应的提高。但是在具体使用的时候,该算法的实现还需要进一步完善。在今后的工作中,将就以下两方面问题做出进一步研究:
1)通过引入一些用户兴趣的动态因素(例如用户访问日志),来构造属于每个用户的兴趣集,来计算符合每个用户要求的网页排名。
2)考虑对迭代算法的优化,确保大量主题搜索的效率。
参考文献
[1]Page L,Brin S.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks,1998,30(1-7):107-117.
[2]Page L,Brin S,Motwani R,et al.The PageRank Citation Ranking:Bringing order to the Web[R].Technical report,Computer Science De-partment,Stanford University,1998.
[3]Ricardo B Y,Berthier R N.Moderninformation retrieval[M].北京:机械工业出版社,2005.
[4]Yang Y,Pederson J O.A comparative study on feature selection in text categorization[C].International Conference on Machine Learning(ICML),1997.
PageRank算法论文 篇7
随着信息技术的迅猛发展,互联网成为了人们获取信息的重要途径。通过搜索引擎,用户便能检索到大量的信息,而庞大的结果网页中,真正对用户有用的信息并不多,用户要从结果网页中找到自己真正关心的页面有时需要花费大量的时间。Sergey Brin和Lawrence Page于1998年提出的Page Rank算法为搜索引擎提供了变革技术。该算法以页面的链接结构为基础,以权威度作为衡量页面等级的指标,简单、高效是一种独立于查询的页面等级排序算法。全球最大的搜索引擎Google吸收了该算法作为结果网页排序的核心技术。由于Page Rank算法独立于查询,完全建立在链接结构上,忽略页面与查询的相关性,因此容易导致产生主题漂移现象。本文据此提出了一种基于查询主题相关性的改进算法,将搜索页面与查询主题的相关性用相似度来度量,改进后的Page Rank算法较传统的Page Rank算法在“主题漂移”问题上有明显的改善。
2 Page Rank算法的基本原理
Page Rank算法基于链接分析计算页面的权威度,衡量网页的权威性,实现搜索结果的等级排序。该算法的有效工作需要两个假设前提。
(1)网页被引用次数越多,网页的重要度越大或权威性越高;网页被重要的网页引用时,重要度越大或权威性越高。
(2)假定用户对网页集合中的每一个网页的访问都是随机的,并且跟随网页的向外链接只能是向前浏览,不能回退浏览。此时,浏览另一个网页的概率置为被浏览网页的Page Rank值。
文献[1]中给出了传统Page Rank算法的计算公式:
其中,d是取值在0-1之间的阻尼系数,通常取0.85。它是防止页面的Page Rank值过高或过低而引入的平衡因子。PR(Ti)为指向页面B的页面Ti的Page Rank值,C(Ti)为Ti页面的出链数。
3 查询主题相关性的Page Rank改进算法
鉴于传统Page Rank算法得到的权威度容易脱离用户搜索的主题范围,产生搜索结果的主题漂移,我们希望将查询主题与搜索结果页面的相关性同时引入到对链接网页的Pange Rank值的迭代计算中,并进而影响对搜索结果的排名。
改进的Page Rank算法的基本假设:网页的链接个数越多且与查询主题的相关性越大,其Page Rank值越高;网页链接不多但与查询主题相关性大的网页,比被大量网页链接但是与查询主题相关性极小的网页的Page Rank值高。
本文采用相似度来度量页面与查询主题的相关性,涉及到如下基本概念:
特征项:是构成文本的基本语言单位。如字、词、词组、短语等,它包含较多的语义信息,能够很好地用来表达文本。例如,可以用d(T1,T2,T3,…,Tm)来表示一个文本d,Ti是文本的个特征项中的第i个特征项的值。
特征项的权值:指一个特征项在文本中所占权重。它反映了该特征项对文本信息的表达能力。
相似度:网页页面(内容)与查询主题间相关性的一种度量。例如,假设有向量v1和v2分别表示网页页面和查询主题,二者之间的相似度可以定义为:
改进算法的主要计算步骤如下:
(1)提取页面的特征项
页面文本可以看成由大量词条构成的集合,可以从词条中选取包含较强语义信息的特征项来表示页面。为此,可以对Web页面先做一些预处理,如去掉网页中的广告、导航等噪音信息,分离HTML文档的标题、正文、超链接、标签等信息。然后,利用分词技术对预处理结果信息进行分词,用分词结果作为特征项来表示页面。
(2)构造索引词列表
根据特征项构造索引词列表,提取前出现频率最高的特征项作为系统的索引词,并构造相应的查询主题和页面主题索引词向量空间。
(3)计算索引词的权值
对每个特征项赋予了一定的权重值,采用TF-IDF(词频-反文档频率)方法计算特征项权重,即:
它表示:如果某个特征项在一个文档中出现的频率高,在其它文档中出现频率低,则该特征项包含的信息多,其权重高,获得的权值就大。为了避免出现某些权值过高的现象,可对特征项权值做如下归一化处理:
(4)用向量表示页面文本和查询主题
将文本搜索器搜索出来的前n个页面表示为d3,...di...,dn,m个索引词表示为k1,k2,k3,...kj,...km,索引词kj在页面di中的权值设为Wij,则这n个页面可以表示成m维空间Rm中的向量,即di=(wi1,wi2,wi3,...wij...,wim)。
由于查询主题涉及的关键词较少,对查询主题的向量表示可以用类内全部元素的质心来刻画。即对查询主题Q,可以用查询得到的前n个页面集的质心来表示:
(5)计算相似度
根据上一节文档和查询主题的向量表示,有:
根据向量间的相似度计算,di和Q之间的相似度计算方即:
将(6)计算出来的页面与查询主题相似度作为权值参与页面的Page Rank值计算,所得到的Page Rank值将更能反映出网页在查询主题下的更合理排名。
改进算法的模型为:假设某个页面A,T1,T2,…,Tn为指向页面A的页面,参数d是取值在0-1之间的阻尼系数,通常d取0.85,Sim(A,Q)为页面A与查询主题Q之间的相似度,PR(A)表示页面A的Page Rank值,则改进后的Page Rank算法的计算公式如下:
由于引入了相似度,会降低页面的Page Rank值,特别是与查询主题无关或相似度极低的页面的Page Rank值将得到有效抑制。由于Sim(A,Q)的取值在0-1之间,算法加入相似度评估后并不影响原有的Page Rank算法的收敛性,经过若干次迭代运算,页面的Page Rank值仍然会收敛。
下面以一组实例验证改进Page Rank算法较传统Page Rank算法的优越性。
假设一组页面的链接结构如图1所示。其中,页面T2,T3,T4为基于查询q返回的相关页面,表示链接方向,两种算法计算页面的Page Rank值,并返回基于查询q的页面T2,T3,T4的排序。
首先,假设阻尼系数d取0.85,由公式(1)对每个页面赋初始Page Rank值1,算法的程序运算结果为:
假定页面T1,T2,T3,T4,T5,T6与查询q的主题相似度分别为0.05,0.7,0.4,0.3,0.01,0.02,根据查询主题相关性的改进Page Rank的计算公式(7),假设阻尼系数为0.85,每个页面仍然赋初值1,算法的计算结果为:
针对查询q返回的三个页面T2,T3,T4的两种实验结果如表1所示。
从数据对比中可知,针对本例的查询q,用传统Page Rank算法计算,页面T2获得的排名是第3名,但是该页面具有与查询主题很高的相似度,因此采用改进算法其获得的Page Rank值明显增加,并且获得了最高排名。
4 结束语
Page Rank是基于Web结构挖掘的链接分析思想提出的,是对结果网页进行等级排序的算法。由于传统Page Rank算法完全忽略查询的主题与内容,因此容易导致主题漂移。文中提出的基于查询主题相关性的Page Rank改进算法从一定程度上有效地抑制了主题漂移问题,但是改进算法中增加了求得相似度的运算,因此,时间耗费较传统Page Rank算法大,今后还可以对算法做进一步的优化和改进,在特征项提取和权值计算方面,希望寻求效率更高的方法,减少时间复杂度,也可通过提高硬件设备的执行效率来改善获取相似度的时间代价。
摘要：PageRank基于链接分析计算页面的权威度,衡量网页的权威性,实现搜索结果的等级排序。文章针对传统PageRank存在的主题漂移问题提出了一种基于查询主题相关性的改进算法。通过引入搜索页面与查询主题的相关性度量,有效地抑制了传统PageRank算法的主题漂移问题,并通过实例加以验证。