PDF《一种改进的 PageRank 算法》

2012 年第21 卷第2期216 经验交流 Experiences Exchange 关性.即:权威网页上的内容相关性要大于非权威网 页上内容相关性. 在链接关系的基础上,加入页面与查询主题的相 关性权重, 以使得所产生的 PageRank 值高的页面是针 对用户查询主题的,这就形成了加权 PageRank 算法. 在加权 PageRank 算法中有: Wa v Win v u Wout v u = ? (4) 其中, ( ) ( , ) q G u Iv Win v u Iq ? = ? , ( ) ( , ) q G u Ov W out vu Oq ? = ? (5) Win(v,u)和Wout(v,u)分别表示基于出度和入度的 权重因子, Iv 和Ov 分别是网页 v 的入度和出度, Wa(v) 可以有衡量网页权威性的其他任何算法计算,Wr(v) 是用网页内容间相关的程度来衡量相关性的比例,假设W(v,u)表示网页 v 和网页 u 的相关性程度值,那么 有: ( ) ( ) ( , ) ( , ) r v q G u W v u W W q u ? = ? (6) 加权 PageRank 的实际意义可以解释为: 假设网页 上有一个主题查询者,它从初始页面出发,按照页面 链接前进,从不执行后退操作.对于没个页面来说, 浏览者对此页面中的每个链接感兴趣的概率是和此链 接主题的相关性成正比的.如果有很多页面指向一个 页面,那么这个页面的 PageRank 值就会高,但加权的 PageRank 不一定高,和页面中大部分都为主题相关的 页面有关;

如果加权的 PageRank 很高的页面指向它, 这个页面的加权 PageRank 也会很高. 在以主题为中心的 PageRank 算法中根据页面内 容将其归类为不同的主题,然后针对不同的主题进行 相似度的计算,主要步骤为:首先确定主题的类别, 将常见查询内容归纳总结,创建主题列表.然后把数 据库中的网页和主题列表中的不同主题匹配,匹配过 程是通过采用 VSM 空间向量的模型进行计算, 通过计 算可以得到该网页相对于各个主题的相似度得分,从 而可以明显提高主题相关度.两个文档的相似性则由 表示文档的向量内积来进行计算.假设网页 u 和v的文档向量分别表示为 U=(u1,u2,…,um), V=(v1,v2,…vm), 那么他们的相关程度可以表示为

1 2

2 1

1 ( , ) m i i i m m i i i i uv U V W v u U V u v = = = ・ = = ? ? ? ? (7) 其中 ui 和vi 是关键词 i 在网页 u 和v中的权值,一般 按照经典的 TF-IDF 算法计算,定义关键词 i 在文档 j 中的权值 wij,则有 wij=tfijlg(N/dfi),其中 tfij 表示关键词 i 在文档 j 中出现的次数,dfi 是包含关键词 i 的文档数 量,N 表示文档总数.

5 实验结果分析 利用网络蜘蛛程序在 http://news.sohu.com 在网络 上爬行一段时间后,获取了

25784 张新闻网页.网页 内容可以分为国内、国际、财经、体育、历史等.本 实验中改进的 PageRank 算法与经典的 PageRank 算法, 加权 PageRank 算法,以主题为中心的 PageRank 算法 进行比较分析.我们输入保障性住房,利比亚,足球, 个人所得税,抗日战争作为关键词.取搜索前

200 个 作为标准结果集.通过人工评价查询的网页与要查找 的主题的内容相关性.实验结果数据见图 1. 图1各关键词在不同算法查询下的相关网页数 其中横坐标

1 2

3 4

5 分别代表的关键词: 保障性住房、 利比亚、足球、个人所得税、抗日战争.纵坐标表示 的是搜索结果中与要查询的主题相关的网页数量.两 条条形柱分别表示在改进的 PageRank 算法和经典的 PageRank,加权 PageRank 算法,以主题为中心的 PageRank 算法下的实验结果. 同时为了比较查询结果的优劣,本文还考察了查 准率,由于一般情况下用户只会关注前二十页的查询 结果,所以本文仍然取前