基于网页内容和时间反馈的 PageRank 算法改进.doc

《基于网页内容和时间反馈的 PageRank 算法改进.doc》由会员分享，可在线阅读，更多相关《基于网页内容和时间反馈的 PageRank 算法改进.doc（5页珍藏版）》请在三一办公上搜索。

1、精品论文推荐基于网页内容和时间反馈的 PageRank 算法改进程建，房鸣 北京邮电大学计算机学院，北京 （100876） E-mail:chengjian08摘 要：搜索引擎的相关排序是搜索引擎的核心之一。分析 PageRank 算法后，指出其偏重 旧网页、没有考虑网页的重要性、无法判断网页内容的相似性等不足。结合 TCPageRank 算法和 PageRank-Time 算法优点，提出了一种改进的算法。该算法即考虑网页内容相关性，又 考虑网页的发布时间。从分析网页的内容的相似性上避免主题漂移；从网页发布的时间考虑 新网页的 PR 值，即旧网页下沉，新网页上浮。实验结果表明改进的排序算法符合

2、互联网的信息更新模型，提高了网页排序质量。 关键词：PageRank；时间反馈；VSM；搜索引擎 中图分类号：TP311.11引言搜索引擎是目前最流行的网络信息检索工具之一。根据中国互联网络信息中心最新调研 结果显示，2008 年中国互联网用户突破二亿，而且有超过 80%的用户使用搜索引擎作为他 们从网络上搜索信息的主要手段。因此，搜索引擎的发展对于推动互联网的进一步发展具有 相当的意义。然而，目前这些搜索引擎还存在着很大的局限性，最新调查结果显示，搜索结 果排序欠佳、搜索结果杂乱是主要因素。网页排序的方法主要有两大类：一种是基于网页内容分析进行排序，一种是基于互联网 的超链接结构分析进行排序

3、。基于内容的排序源于传统的信息检索，万维网搜索以其巨大的 数据规模对传统信息检索技术提出了新的挑战。而基于链接分析的排序才将互联网搜索与传 统的信息检索区分开来，适用于互联网大规模数据的检索。基于链接的算法主要有 PageRank 算法和 HITS 算法等。论文第二部分介绍 PageRank 算法及其改进的 PageRank 算法。第三部分详细说明改进 的 PageRank 算法。第四部分算法实验分析。第五部分总结全文。2PageRank算法2.1 PageRank算法原理PageRank 算法借鉴了传统情报检索理论中的引文分析方法：当网页 A 有一个链接指向 网页 B，就认为网页 B 获得了

4、一定的分数，该分值的多少取决于网页 A 的重要程度，即网 页 A 的重要性越大，网页 B 获得的分数就越高。由于互联网上的链接相互指向的复杂度， 该分值的计算过程是一个迭代过程，最终网页将按照所得的分数进行排序并检索。PageRank 算法模拟一个用户随机的遍历网络，设用户随机的到达一个网页的概率为 d 或者随机的沿着链接往下遍历的概率为 1-d，更进一步的假设该用户不会沿着刚才的链接返 回到已访问过的网页。因而每一个网页被访问的概率就是 PageRank 值，其计算公式如下：- 5 -PR(v) = (1 d ) + d * PR(u) / NuuBv（1）其中 PR(v)是网页的页面级别，

5、d 为介于(0,1)区间的衰减系数，一般取 0.85 左右，Bv 为指向 网页 v 的其它网页，Nu 是网页 u 中向外指出的链接数目。2.2 PageRank算法的缺点由于 PageRank 算法是离线计算这个网络的 PageRank 值，在用户查询时仅仅根据关键 字匹配获得网页集合，然后排序推荐给用户，因此具有很高的响应速度，并且搜索引擎 Google 中的成功也证明该算法是高效、合理的。但由于仅仅利用了网络的链接结构，该算 法还存在不少的缺点：(1) 从 PageRank 算法以及随机漫游模型中可以看出，在迭代过程中权值是按当前网页 的出度平均分配的，即在权值分配中平等对待链出的每个网页

6、，没有考虑网页的相对重要性。(2) PageRank 算法无法区分网页中的超链接是和网页主题相关还是不相关，即无法判断 网页内容上的相似性，这样就容易导致出现主题漂移问题。比如，Google，Yahoo 是互联网 上最受欢迎的网页，拥有很高的 PageRank 值。这样，如果用户输入一个查询关键字时，这 些网页往往也会出现在该查询的结果集中，并会占据很靠前的位置，而事实上这个网页与用 户的查询主题有时并不太相关。(3) PageRank 算法偏重旧网页，因为新网页刚被放到 Internet 上不久，由于时间短暂， 许多其他网页还没有指向它，通过公式(1)计算 PR 值就很低。在搜索引擎返回的结

7、果中往往 就会排到较后的位置，可能正好与用户的需求恰恰相反，因为很多情况下用户想看到较新的 网页。2.3 PageRank算法的改进2.3.1TCPageRank算法网页间的链接反映的是一种认可关系，网页 A 中有链接指向网页 B，说明网页 B 的内 容与 A 相关或具有一定的价值，同一网页中不同链接指向的网页的内容与当前网页内容的 相关程度是有差别的。基于此思想,Ingongngam 等人提出了以主题为中心的 PageRank(Topic Centric,简称 TCPageRank)算法，该算法指出网页权值的分配应和网页内容的相似度成正比， 被链接的网页内容与当前网页的内容越相似分配到的权值

8、比重就越大。改进后的 PageRank 的计算公式为：PR(v) = (1 d ) + d * PR(u) *Wcontent / NuuBv（2）其中 Wcontent 代表网页 V 和网页 U 内容相似度所占的权重，Bv 为指向网页 v 的其它网页，Nu 是网页 u 中向外指出的链接数目，关于 Wconten 的计算会在下章详细介绍。在 PageRank 算法中被大量链接的知名网站会获取较高的权重，相对于某个特定的查询， 即使他们它们与查询微弱相关也会排在结果的前列，这种现象称为主题漂移。主题漂移现象 使得查询的相关性遭到很大的破坏。TCPageRank 算法根据网页内容的相关性来分配权值

9、可 以有效的解决主题漂移现象。该算法解决 PageRank 算法缺点(2)。2.3.2PageRank-Time算法戚华春等人提出了 PageRank-Time 算法，该算法考虑新网页，即考虑网页的发布日期。 把网页的发布日期引入 PageRank 算法，使在网络上存在比较长时间的网页慢慢沉下去，新 的网页能迅速浮上来。但由于现在很多网页是由程序自动生成的，并且大量的 HTML 网页 的格式不规范，很难从网页中提取到该网页的发布时间。因此把网页的存在时间通过搜索引 擎搜索的周期数来表征。这一转换的核心思想是基于这样一个事实：一般而言，搜索引擎的搜索周期为半个月到一个月，如果一个网页存在的时间较

10、长，那它将在每个搜索周期里都将被搜索到(在同一个搜索周期里不管搜索到该网页几次,都算作 1 次)。即页面的存在时间反比于搜索引擎搜索到 该页面的次数 T。网页的时间反馈因子 Wt：Wt=e/T 其中 Wt 为网页的时间反馈因子，T 为 一个网页被搜索引擎访问的周期次数；e 为常数，它的取值受到式(1)中 d 的影响，且也和搜 索引擎的搜索周期相关。因此改进后的 PageRank 算法的公式为：PR(v) = (1 d ) + d * PR(u) / Nu + e / TuBv（3）在该算法中引入时间反馈因子，使网页的发布时间长短影响网页 PR 值的大小，改进的 算法有利于旧网页下沉，新网页上浮

11、。解决了 PageRank 算法缺点(3)。3改进的PageRank算法3.1 改进的公式TC-PageRank 算法根据网页的内容相关性分配权值，可以有效的解决主题漂移现象，却 没有考虑网页的发布时期；PageRank-Time 加入了时间反馈因子，考虑了网页的发布日期对 PR 值的影响，却没有考虑网页内容的相关性，容易产生主题漂移现象。本文综合以上两种算法的优点，从网页内容相关性方面和网页发布时间方面，提出改进 的 PageRank 算法：PR(v) = (1 d ) + d * PR(u) *Wcontent / Nu + e / TuBvWcontent = Wuv / xOu Wux

12、（4）其中 Wcontent 代表网页 V 和网页 U 内容相似度所占的权重，Bv 代表指向网页 V 的集合，Ou 代表网页 U 链接出的网页集合，Wvu 代表两个网页的内容的相似度，采用 VSM。3.2 向量空间模型（VSM）VSM 空间向量模型表示文档。两个文档的相似性由表示文档的向量内积进行计算。假 设网页 u 和 v 的文档向量为 U=(u1,u2,um)，V=(v1,v2,vm)，那么它们的相关程度为mW (v, u) =U *V uivi= i =1 | U | | V |mm ui 2 vi 2i =1i =1其中 ui 和 vi 为某个关键词 i 在网页 u 和 v 中的权值，

13、此权值按照 TF-IDF 算法来计算,定义关键词 i 在文档 j 中的权值为 wij：Wij = tfij * lg( N / dfi )其中 tfij 是关键词 i 在文档 j 中出现的次数，dfi 表示包含关键词 i 的文档数量，N 表示文档总数。3.3 改进的VSM由于网页采用了半结构化的HTML语言，其包含有丰富的结构信息，故在抽取网页的主 题内容时应加以利用。位于，以及等标记之内的关键词无 疑应该重视,赋予较大的权重系数。因此对于关键词在网页中的权重修正为：Wij=a*Wij 3.0a = 2.0 1.8 1.0在链接文字中在head / title / H 1 / H 2标记中 在

14、meta标记中其它4算法实验分析4.1 衡量标准为了综合考察和衡量算法的效率，我们用召回率和准确率作为主要的评价标准。所谓召 回率是指一次搜索结果中集中符合用户要求的数目和用户查询相关的总数目之比；所谓准确 率是指以一次搜索集中符合用户要求的数目和该次搜索结果的总数之比。即召回率 = 符合用户要求的数目 用户查询相关的数目准确率 = 符合用户要求的数目 搜索结果的总数目4.2 实验方法和结果分析为了验证上述改进的算法，网络爬虫从新浪新闻站( 为了验证时间对PR的影响，分为不同的时间段下载新闻网页，网站上的分类包括国内，国 外，社会，军事等，共计下载了 7000 多个新闻网页。通过选取若干个关键

15、词进行查询，计 算各个算法的准确率和召回率。实验结果如表 1 所示，3 种不同的算法准确率和召回率的比 较如图 1 所示：表 1实验结果序号算法准确率召回率1TCPageRank42.1%50.8%2PageRank-Time44.3%53.1%3改进的 PageRank50.6%60.4%7060504030201001 2 3准确率 召回率图 13 种不同算法准确率和召回率的比较从上述实验结果可以看出，TCPageRank 算法的准确率和召回率比较差，是因为它虽然按照页面相关性分配权值，但是新闻网站的实时性比较高，即新闻更新的速度较快，用户希 望看到最新的新闻；PageRank-Time

16、算法考虑网页的发布时间，虽然有一定的主题漂移，但 是新闻网站更看重新闻的时效性，所以它的准确率和召回率较好；改进的 PageRank 算法考 虑了页面的相关性和网页的发布时间，即防止了主题漂移又兼顾了新发布的网页，所以改进 算法的准确率和召回率都有比较明显的提高。由于改进的算法要计算关联网页的相似度和网页的时间反馈因子，与 TCPageRank 算法 和 PageRank-Time 算法比较，提高了时间复杂度，但是这些运算都是离线进行的，不会影响 用户的体验，因此是可以接受的。5结束语在改进的算法中，结合了 TCPageRank 算法和 PageRank-Time 算法优点。实验表明，改 进的

17、算法有利于旧网页的下沉，新网页的上浮，这一点符合互联网的信息更新模式，同时防 止网页主题的漂移，提高了准确率与召回率。在以后的进一步研究中，还需要完善和优化该 算法，提高搜索匹配程度，尽可能的将用户最需要的结果排在返回结果的最前端。参考文献1 宋聚平，王永成等。对网页 PageRank 算法的改进j。上海交通大学学报，2003，37(3):397-4002 戚华春，黄德才等。具有时间反馈的 PageRank 改进算法j。浙江工业大学学报，2005，33(3):272-275 3 钱功伟，倪林等。基于网页链接和内容分析的改进 PageRank 算法j。计算机工程与应用，2007，43(21):1

18、60-1644 原福永，张园园。基于链接分析的相关排序方法的研究与改进j。计算机工程与设计，2007，28(7)：1630-16315 杜光芹，张化祥。基于超级链接结构和向量空间模型的网页排序算法研究j。人工智能与知识工程，2006，4：106-108Web-based content and timing of feedback to improve the PageRank algorithmCheng Jian, Fang MingSchool of Compute Science and Technology,Beijing University of Posts and Teleco

19、mmunication, Beijing (100867)AbstractSearch engine ranking is one of the cores. After analyzing the advantages and disadvantages of the PageRank algorithm, combined with TCPageRank algorithm and PageRank-Time Algorithm advantage,pose an improved algorithm. The improved algorithm not only considers t

20、he relevance of Web content, but also the time of web page. The algorithm analyses web content on the similarity of the subject to avoid drift and consider PR value by the pages of time, that is, the old pages go down, the new pages go up. The results show that the improved ranking algorithm is accord with the Internet information model and improve the quality of the pages ranking.Keywords: PageRank; time feedback; VSM; search engine