用户差别化和主题敏感的PageRank算法

马海波，杨楠，于新兴

(大连交通大学 软件学院，辽宁 大连 116028)*

0 引言

据中国互联网络信息中心发布的第28次“中国互联网络发展状况统计报告”，截止2011年6月，中国共有网民4.85亿，搜索引擎用户3.86亿，中国现有网站183万个.2008年谷歌官方博客称其拥有1万亿幅网页页面的索引量.由这些数据不难看出，互联网成为现代共享信息的主要载体，无论网站、网页数量还是用户数量都特别巨大，搜索引擎在搜索信息方面占据主要地位.从用户行为上看，多数用户在使用搜索引擎的搜索结果时只会点击搜索出来的前2页中10到20个高相关度的搜索结果.因此如何将最能满足用户需求的页面排列在搜索结果的前面变得至关重要.

在网页排序算法中，最著名的是1998年由Sergey Brin和Lawrence Page提出的基于链接分析的 PageRank网页排序算法［1］.然而 PageRank算法本身存在一些不足之处，如常见的主题漂移、对新生成的网页所给予的PR值较低等问题.

几乎所有的现行网页排序方法都没有对用户进行差别化看待，关注的重点只是网页重要程度本身，依据该重要程度进行排序，而没考虑到不同用户兴趣、关注点、需求上的差异.对所有用户，由相同的查询词得到同样的搜索结果，显然很难满足有不同个性、不同兴趣的用户需求.

本文针对PageRank算法的未将用户差别化看待和主题漂移的问题，提出来一种基于用户差别化和主题敏感的PageRank算法的网页排序方法.

1 PageRank算法

PageRank算法是基于网页间链接和基于用户的随机冲浪模型的，主要思想是为每个网页设定一个PR值，用来标识该网页的重要程度.链接到其他网页则相当于为该网页投了一票，该票的权值为源网页将自身的PR值依所有出度链接数量平均分配而得到，这样将网页间的关系看做是图的结构，经过矩阵间迭代计算得到每个网页的PR值.公式如下:

式中，PR(A)表示欲计算网页A的PR值;Ti为有链接到网页A的页面;PR(Ti)为Ti页面的PR值;d为阻尼因子，通常取0.85.

由于PageRank算法将一个网页的PR值，以平均分配的方式分发给每个出度的链接页面，而没有考虑到链接出去的页面主题与本页面的相关程度，从而在多次迭代后造成主题漂移问题［2］.

2 对PageRank算法主题漂移问题的改进

针对主题漂移问题，很多人在PageRank算法上来进行改进，如Taher H.Haveliwala等提出的Topic-Sensitive PageRank(TH-PageRank)算法［3］和Matthew Richardson 等提出的 MP-PageRank［4］，黄德才等提出的TS-PageRank［5］都是通过改变平均传递PR值的方式，一定程度上修正主题漂移问题.

本文主要对TH-PageRank算法进行改进.TH-PageRank算法公式如下:

其主要思想为将每个网页按照Open Directory Project(ODP)分类，将每个网页分成16个主题，Aj为该网页在每个主题下的相关度，计算出的PRj(p)为该主题下的PR值，其他参数含义同式(1).从而使得每个网页都有16个对应主题的PR值.

在用户查询时，算法根据用户输入词和查询的上下文条件，用式(3)计算出每个网页最终的PR值.

式中，qj为查询词对应的每个主题下的相关度;PR(p)为最终该网页在此查询词下的PR值.

虽然TH-PageRank算法在一定程度上解决了主题漂移的问题，但是其同样存在一些不合理的地方:

(1)对用户查询词进行分主题计算相关度时，需要依据查询的上下文条件，但在应用中很难有足够多的上下文条件供计算.查询词过少，形成了查询词的主题模糊，无法准确的判断查询词的主题相关度，从而影响最终网页的PR值和排序结果;

(2)搜索引擎极高的响应速度源自对数据的离线计算，搜索时只进行查询和简单的排序.计算出查询词的主题相关度后，需要对所有查询到的网页重新在线计算PR值.对于可以达到上亿级别的搜索结果全部重新在线计算PR值，这将是不可行的;

生物浮床是利用浮床作为载体在池塘水面种植具有特定功能且易于在水中生长的植物，其原理是利用浮床植物根部吸收、转化、吸附、滤过养殖系统中残留的氮、磷及有机物质转化成植物生长所需要的营养物质，从而达到净化水质和优化池塘生态系统的一种水体修复技术。同时，浮床植物根部形成的“泌氧与耗氧”环境是微生物生长繁殖的良好场所，且使得整个池塘养殖系统中微生物菌群的结构与功能多样性得到有效调节。其中，浮床植物的选择是浮床池塘养殖建立的关键性因素。

(3)仅有16个主题，粒度过小，过于粗糙，较难反映网页真实的信息.

3 基于用户差别化对主题敏感的PageRank算法的改进

用户之间具有兴趣爱好、性别、年龄、工作、背景阅历、生活地点、对事物关注点等等差别.现如今的搜索引擎只关注网页的重要程度，没有对用户不同的需求加以区分，导致对于不同的用户，只要查询词相同就会返回相同的搜索结果，忽略了用户个性需求的.

比如体育爱好者搜索Jordan时，应该将篮球明星Jordan相关网页排序结果提前，爱好购物的用户搜索Jordan时，其意愿更倾向于Jordan品牌的服饰，地理和旅游爱好者在搜索Jordan时，如果将约旦这个国家的风土人情介绍排列在搜索结果的前面，将更会满足用户的需求.再比如汽车爱好者在搜索QQ时希望得到QQ汽车的相关信息，爱好网络聊天的用户搜索QQ会返回一款IM.当用户搜索附近的麦当劳时，返回的应该是本地的麦当劳信息，如果返回的是其他地点的麦当劳信息，即便PR值再高，也难以满足用户的需求.

这样就需要对用户的兴趣、爱好等信息进行搜集，可通过主动和被动两种方式.

主动方式:谷歌、百度等主要搜索引擎都有用户登录功能，可以在保护用户隐私的前提下，主动要求用户提交兴趣爱好、年龄、性别、工作、生活地点等个性信息，并可以随时进行提交、修改，当然提交的信息越多越具体，将更能反映用户真实的需求.

被动方式:在经过用户允许下，记录登录用户的搜索时查询词的记录，统计用户的网络收藏夹等信息.

式中，D表示每个用户独有的一个主题相关度向量;Wtn为该用户在第n个主题中的兴趣程度.

TF(D，T)为词项T在同主题关键词库中出现的次数，即词频.IDF为倒排文档频率，即含有T的用户信息文档数的倒数.式(6)、(7)都是为防止某些奇异词对W计算结果的干扰而进行的变型.

每个用户兴趣主题相关度的向量随着主动和被动方式对用户信息的搜集而进行改变.有此公式，得到了用户针对不同主题的喜好程度的排序.并不仅限于记录16个主题的爱好程度，将16个主题改变为可扩展的主题集，可以添加用户上网时所处网络，生活地点，关注网页类型等扩展信息.用户所在网络可以解决联通、电信访问对应网络服务器响应速度差异问题，生活地点则更好的满足用户实际需求，网页类型分为具有时效性和非时效性［9］，可以对用户信息的记录区分用户更倾向于关注的网页类型.

针对TH-PageRank算法的粒度较小的问题，采用扩展的主题集，记录和用户兴趣信息对应的信息，如服务器网络类型，网页信息是否具有地域性，传统PageRank算法下的PR值等.对提取的网页关键词，运用式(8)、(9)、(10)计算出该网页的主题相关度向量.初步计算网页PR值的公式为:

与原公式相比，这里提供的是可扩展的主题集，不再局限于16个主题，主题相关度为该维向量值在n维向量值中的百分比.func()函数［10］依据关键词在网页不同的位置，分配不同的权重值.式(11)中j为预先设定的阈值.如果网页在某些主题下的PR值特别小，则将其置0.

输入查询词后的计算方式也不同于TH-PageRank算法.首先在对每个关键词生成索引的时候记录每个主题下前500页面的平均PR值.具体执行方式如图1所示.

图1 搜索查询词时网页排序流程图

4 实验验证分析

算法可行性:对于网页的PR值采用离线计算的方式，针对特定用户的查询词，只进行比较、有限数量值间的排序，保障了搜索引擎的响应速度.在对网页PR值存储上，空间扩大了主题集中主题个数的倍数，为有限数量，对空间复杂度影响不大.

由于多数网页的主题集中在1～3个之间，通过对主题特别小的PR值置0操作，减少噪音，形成网页主题PR值间的稀疏矩阵.无论在运算还是存储上都具有很高的效率.

依据用户提供的信息和式(4)、(5)、(6)、(7)计算出该用户在不同主题下的兴趣程度.由图2可以看出，用户对计算机和网络、新闻、地域性的事物比较关注.在此情况下可以判定，用户兴趣主题为计算机网络、新闻、地域性的事物.

图2 用户在不同主题下的兴趣程度

当用户查询词为社交网络时，返回的10个页 面在不同主题下的PR值如附表所示.

附表 依据本文算法计算出的网页在不同主题下的PR值

如果按照传统的PageRank算法对网页进行排序的结果为:5，2，7，9，1，6，10，3，4，8

用本文的算法对网页进行排序的结果为:10，3，6，2，4，5，7，9，1，8

可以看出对于查询词“社交网络”，页面5具有较高的传统PageRank算法下的PR值，但其所属的主题着重于从科学研究的角度描述社交网络，这对于一个在科学方面没用兴趣的用户来说，虽然其有较高的重要程度，但并不是用户的真正需求.相反页面10虽然在传统方法上没有较高的重要程度，但其是从计算机网络方面对社交网络进行描述的，将会更加符合用户的需求.同时本算法还具有可扩展性的优势，与不同用户的需求结合紧密.

5 结论

本文的算法考虑了对于同一查询词，不同个性用户之间的不同的实际需求，对用户进行差别化看待，结合改进后的主题敏感的PageRank算法，一定程度上解决了PageRank算法的主题漂移问题，提高了网页排序的准确程度和用户的满意程度.

根据本文的算法，在进一步的工作中，为了能准确的获得用户的个性需求，应该通过对算法的大范围应用，进一步研究用户主动提交的个人兴趣的关键词达到何种程度的数量和广度，才可以对本算法进行应用.本文对扩展的主题已经提出了一些可行的设想，需要在应用中进一步对主题进行扩展.式(11)中阈值j的在不同主题和不同的查询结果的取值，需要在大量的运用中结合实际经验，给出较准确的取值.本算法基于PageR-ank算法，应用中便于移植和切换算法，在具有大量用户的全文检索领域具有较好发展前景.

［1］Sergey Brin and Lawrence Page.The PageRank Citation Ranking:Bring Order to the Web［C］.Stanford University:Computer Science Department，1998.

［2］高琪，张永平.PageRank算法中主题漂移的研究［J］.微计算机信息，2010，89(9):117-119.

［3］HAVELIWALA.Topic-Sensitive PageRank:A Context-Sensitive Ranking Algorithm for Web Search［J］.IEEE，2007，18:365-368.

［4］RICHARDSON，DOMINGOS P.The intelligent surfer:probabilistic combination of link and content informaion in PageRank［J］.Advances in Neural Information Processing Systems，2002，14:1441-1448.

［5］黄德才，戚华春，钱能.基于主题相似度模型的TSPageRank算法［J］.小型微型计算机系统，2007，28(3):510-514.

［6］JENEI S.Structure of left-continuous triangular norms with strong induced negations:(II)Rotation-annihilation construction［J］.J.Appl.Non-Classical Logics，2001，11(3-4):351-366.

［7］JENEI S.Structure of left-continuous triangular norms with strong induced negations:(III)Construction and decomposition［J］.Fuzzy Sets and Systems，2002，128(2):197-208.

［8］JENEI S.A note on the ordinal sum theorem and its consequence for the construction of triangular norms［J］.Fuzzy Sets and Systems，2002，126(2):199-205.

［9］王勇，刘奕群，张敏，等.基于用户兴趣分析的网页生命周期建模［C］.第三届全国信息检索与内容安全学术会议，2008.

［10］宋聚平，王永成，尹中航，等.对网页PageRank算法改进［J］上海交通大学学报，2003，37(3):21-25.