新的PageRank优化算法

94_2012,48(6)Computer Engineering and Applications计算机工程与应用新的PageRank优化算法蒋永辉,吴洪丽JIANG Yonghui, WU Hongli海南师范大学信息科学技术学院,海口571158College of Information Science and Technology, Hainan Normal University, Haikou 571158, ChinaJIANG Yonghui, WU Hongli. New PageRank optimization algorithm. Computer Engineering and Applications,Abstract: Search engines repeatedly returm currently popular pages at the top of search results, popular pages tend to get even morepopular, while unpopular pages get ignored by an average user. In order to escape fom this problem, an improved ranking function andeffective Web user model are employed, and a New PageRank Optimization(NPRO) algorithm is provided. Experimental data showthat the provided algorithm can attain unbiased Web ranking.Key words: PageRank; ranking function; user model摘要:为了克服 PageRank在搜索过程中重复性地把当前受欢迎的网页放在搜索结果的首要位置，而不受欢迎的网页被大多数用户忽略的问题，采用了一种改进的评估函数及有效的用户模型,获得了一个新的PageRank优化算法。实验结果表明，该算法达到了较好的公平性。关键词:PageRank算法;评估函数;用户模型DOI: 0778.1012-8331.2012.06.028文 章编号:1002 8331(2012)06 0094-02文献标识码:A中图分类号:TP3011引言其中, A,表示用户第-一次访问网页p就会对该网页有不错的PageRank算法"是由Brin S和Page L在1998年提出的一评价, Lp表示用户喜欢该网页; Q(p)是-个条件概率,表示一种用于标识网页的等级/重要性的方法.同其他网页排名算法个用户在第一一次访问网页p时就会喜欢该网页。通过该定义,相比. PageRank具有实现简单.易于理解等优点。基于Page-可以假设把网页p展示给所有的用户来测定该网页的质量。Rank的有效性”,很多搜索引擎采用了PageRank作为其网页例如，在100个用户中,假设有90个用户在访问网页p后会喜排名算法。PageRank 能够很好地捕捉高质量的网页,从而使欢它,则它的质量Q(p)即为0.9。下一节将讨论在没有用户反大多数用户对Google和其他的搜索引擎所返回的查询结果满馈的情况下如何测定该网页的质量。，意程度较高”。但是, PageRank会出现“富者更富”问题,搜索引擎会将等该定义是对网页真实质量的- -个合理评价标准"。在实级高的网页返回给用户,而等级低即使高质量的网页却被大际中,某个用户可能对一个网页评价很高,而另-用户可能觉多数用户忽略,对于新产生的高质量的网页更是如此，其原因得该网页完全没用.因此当对一一个网页有不同的评价的时候，是在一-开始新产生的网页还未被搜索引擎索引。这些网页可选取对该网页评价高的用户的投票是较为合理的。能被用户永久忽略,从长期来看,这也会在总体上降低搜索结2.2 测定网页质量果的质量"。根据上节定义,如果想精确地测定-一个网页的质量,就需针对这个问题.本文提出了一种形式化框架.通过建立近要大量真实用户访问该网页并从他们那里得到反馈。但这显似于真实合理的用户模型来分析网页的真实质量来纠正搜索然是不可能做到的.因此需要在没有用户参与的情况下测定引擎的“偏见”,然后以一种实用的方法来消除内在的网页质个网页的质量:量问题,以避免PageRank固有的“偏见”问题,并结合实验数据c. dP(p)Vd(2)设计网页质量评估器。该质量评估器能有效消除“富者更富”其中,C是-一个常量, P(p) 表示当前网页p的受欢迎程度，P(p)问题,使搜索结果更符合用户的真实需求。dP(p)dr表示网页p受欢迎程度的增加量。2 NPRO 所涉及的核心方案2.3网络用 户模型在本文的NPRO算法中. PageRank算法以及该算法中所首先以V(p,1)来度量网页的受欢迎程度,即从时间1开涉及的各种参数,需要根据具体情况和需要解决的实际问题始后的单位时间内网页p被访问的次数。以A(p,1)来度量用选取合适的取值.这里不做介绍.有兴趣请参阅文献[5]。下面户熟知度,即在时间t时,用户对网页p的熟知度的比例。例详细介绍- -下本文的核心方案设计。如.到当前为止.有100 000个用户访问过网页P ,且熟知该网2.1 新的网页质量评估标准页,则该网页的用户熟知度A(p,，)就为0.1。需要注意的是,用Q(p)=P(LM)1)户熟知度表示的是已经访问过该网页且能够确定是否喜欢该中国煤化工基金项目:海南省教育厅基金资助(No HISK2009-75)。作者简介:蒋永辉(1979-),男.硬士生,研究领域:信息检索、文本挖掘:吴洪画(1976- -), 女,博士生.MYHCNMH(cn@126.com收稿日期:201008-27;维国日期:2010-11-09;CNKI出:210302:/://ww.coki nekcmctei.121210210101.,1m)蒋永辉,吴洪丽:新的PageRank优化算法2012 ,48(6)95网页的用户数量.而网页受欢迎度表示的是用户知道该网页质量关系如下:且喜欢该网页的数量。因此,在时间t时,网页p受欢迎度为dP(p, l)/dr2(p)=(严)Pp.0X1-(p.而(14)P(p.I)=A(p.t). Q(p)(3)dP(p, t)dt2.4网络用户模型分析以l(p,t)表示(4)2 P:UO ,称为相对受欢迎度增量函如果知道网页P的当前受欢迎度,就可以估计出有多少数。从图1可以看出在一个网页刚被创建时, P(p,1) 并没有用户已经访问了该网页。在除去这部分用户之外,喜欢网页p很好地反映出该网页的质量,然而,访问该网页的用户大多数的用户比例就是Q(p) ,从而可以得出网页p受欢迎度的增长是第一次访问该网页。因此,如果该网页是-一个高质量的网幅度,有下式:页,其受欢迎度会迅速增大,随着时间进行.越来越多的用户H(p.0=1-56ro.wu4)知道了该刚页，其受欢迎度保持不变,且网页的质量e(p)总是由式(4)可得出网页受欢迎度改进函数如下:等于相对受欢迎度增量I(P,1)与其受欢迎度P(p,I)之和,即:Q(p)2(p)=I(P,t)+P(p,I)。P(p,t)=(5)1+[7 e()- ne4fho20卜PLe.0.其中，P(p, 0)是网页p在零时刻的受欢迎度,也就是在网页p0.15第一次被创建时的受欢迎度。其证明如下:0.10由公式(2)和(3)可得P(p,.)=[l-e“[P(,d)dJQ()6)0 255075100125 150用f()替换e[Pp.1Xdt .则P(p,1)与-;出n相等，图1 (p,1). P(p,0)与时间关系图因此(-卢量=( -M2(p)7)4实验在以上讨论中.假设网页的质量是基于当前该网页的受等式(7)称为菲尔哈斯特等式。该等式的解为:欢迎程度以及对瞬时时间的导数。在实践中,无法对瞬时时f()=一间进行有效测量,因此,只有在离散时间点对PageRank的增量1+Ce"Q(p)t进行估计: .期.C是一个常数用来确定边界条件。因为f()=e“I[p,nd,Q(p,t)= nRp(yY44]+ PR(p,t)(15) .PR(p.)所以期, PR(p,t)是网页p在时间1时刻的PageRank值, OPR(p,t)=efPp.Xd=- !PR(P.t)-PR(p.4_)且0,=1,-4_1.假设-一个网页其初始质1+Ce"Q(p)x量Q为0.4,根据公式00=0.4 + 0.000 6t ,在t=S00时达到0.7,(ECx)CEi0r在每个时间间隔测量网页质量值,得出真实的质量 受欢迎度上式两边同时对t进行微分,可得- IP(p,1)=-1+Ce-px和估计质量值之间的关系如图2所示。从图中可得出:(1)评估器Q'可以很好地测量网页的真实质量值。重新整理该式可得(2) Q'对最终的受欢迎度来说不是-一个好的预测器,例P(p,)=- C2()(10)如,在1= I时Q'≈0.4 ,但在t= 500时最终的受欢迎度是0.7。然而,应该注意到的是,对于网页p当前受欢迎度来说，Q'对由等式( 10)可以求得常量C,因为于最终的网页受欢迎度有更好的预测。总之,从总体来说,Q2(P)和Q有着相似的总体走势。P(p,0)= CHT(11)(p, 0)因此C0p)-P(p.可(12).8{整理.上式可得:P(p,l)=(13)0.4Mceasured (Q(p) ， tQmActuale '1+[pp.0-1]e.2 |. Popularity因此,当1→∞时，P(p,I)- + Q(p) ,网页p的受欢迎度最终会100 200 3000 500趋近于Q(p)。图2实际和测鼠的网贞质量值3 NPRO 质鼠评估器的实现5结束语中国煤化工公式(5)所示的受欢迎度改进函数对时间的导数可以用本文提出了MYHCNMHGnk优化算法,来评估-一个网 页的质量,网页受欢迎度对时间的导数与网页(下转154页)1542012 , 48(6)Computer Engineering and Applications计算机工程与应用如图5所示,本文方法对于检验样本具有更强的泛化能[2] 刘燕南收视率指标在电视节目价值评价中的地位[].新闻学与传力,而且随眷样本数量增加其优势更加明显。进一步将该算[3]熊华明，谢长生，夏征字电视节目综合评估与预警系统的设计与播学, 2002(3):30-31.法与其他数据挖掘算法进行比较,具体如表1所示。实现[].计算机工程与应用,2002 ,38(20):215-217.表1不同分类 方法分类效果比较表[4]刘辉.电视收视率预测算法研究及软件实现[D].上海:上海交通大分类算法性能指标数值学,2008.训练时间/s4.616标准支持向量机[5]刘辉,杜秀华，基于ARMA模型的电视台收视率预测方法设计和实支持向量个数4.52(1-v-1算法)现[].控制工程,2009. 156)9-11.分类精度/(%) 99.00训练时间/s 2.458[6]刘小铮.试谈收视事定量预测的数学模型[EB/0OL.2004)http:传统超球分类方法支持向量个数 3.49//www.jstv.com.分类精度/(%) 98.90[7] Zheng Lilei.Audicnc rating prediction of new TV programs based训练时间/s 1.912on GM(1,1) envelopment model[C]/Proceedings of IEEE Inter-半模糊核聚类算法支持向量个数 3.23national Conference on Grey systems and Inelligent Services,分类精度/(%)2009, 11 :388-391.注:表中数值均为50次重复计算的平均值。[8]白冰,张晶,苏勇.基于数据挖掘的收视率数据预处理方法([]科学通过表1可以看出,标准支持向量机( 1-v-1算法)训练时技术与工程，2007.7(18):4741-4745.间较长，这主要是由于其进行不同类别之间的两两对比.使计[9] 张晶,白冰,苏勇基于贝叶斯树络的电视节目收视率预测研究[]算量呈现几何增长。而传统超球分类方法由于将每类样本用[10]涂娟娟基于数据挖掘技术的电视节目收视率预测研究[D].江苏科学技术与工程,2007.7(19)4099-5102.超球结构进行描述,这样不会使计算量随样本与分类数量增镇江:江苏科技大学,2007.加而增长过快,尤其在样本数量较大,类别较多时,其优势更[]涂娟娟.刘同明基于决策树的电视节目收视率预测模型[D.微计为明显。半模糊核聚类算法尽可能留下处于边缘位置的样本算机信息,2007,23:251-252.(通过数据的半模糊化处理) ,而使其只选择可能成为超球球[12] Hart J,Kanlber M.数据挖掘:概念与技术[M].范明,盂小蜂,译面支持向量的样本进行训练，因而在保持较高分类精度基础北京:机械工业出版社,2001.上训练时间进-步缩短。[13]黄凤岗,宋克欧.模式识别MJ哈尔滨:哈尔滨工程大学出版社，4结语[14] 沈清.汤霖模式识别导论[M].长沙:国防科技大学出版社, 1991.本文针对收视率数据预测特点,提出了半模糊核聚类分[15] 张莉，周伟达,焦李成核聚类算法[小.计算机学报2002.25(6);类方法。与传统方法不同之处在于引入样本隶属度概念,并587 -590.通过半模糊核聚类算法得到其隶属度在传统超球支持向量(16] David M J,Robert P Wsuppr veotor domin drpio[]Machine Learmning , 2004.54:45-66.机基础上进-步减少了计算量。实验表明,该方法在具有超[17]朱美琳,刘向东,陈世福用球结构的支持向量机解决多分类问球支持向量机分类器优点的同时,有效提高了训练速度和分题[].南京大学学报:自然科学版。2003.39(2):153-158.类精度，同时使其训练方法更加符合人们对于收视率数据预[18]伍忠东，高新波.谢维信基f核方法的模糊聚类算法[D.西安电测问题的思维习惯。子科技大学学报, 2004,31(4).[19]裴继红,范九伦.谢维信.- -种新的高效软聚类方法:截集模糊C-参考文献:均值聚类算法[小.电子学报, 1998,26(2):83-86.[1]喻国明.李彪收视率全效评估体系研究一以电视剧为例[].新 [20] 王兰柱中国电视收视年鉴2010[M].北京:中国传媒大学出版社,闻学与传播学, 2009(4):36-38.2010:112-116.(上接95页)htt//w.oplesseleses/press. 00919.htm.对许多搜索引擎中当前使用的PageRank算法易于出现的“富[3] Mizzaro S.Mesuring the agrement among relevance judge(CV/更富"现象进行了改进。通过建立有效的网络用户模型获Proceedings of MIRA Conference.USA:IEEE, 199:672 681.得了大量测试结果,并与PageRank算法进行了比较。实验结41 Harer s Pvriatins in rerevace aseats end 邮measurement of retrieval effectiveness[]Joumal of the American Soci-果表明,本文算法对存在的问题有明显改进,从而为网页评估aty for Informnation Science. 1996.47(1):37-49.提供了更准确有效的方法。[5] Wartick S.Boolcan opcrations{M/Information Retrieval:Data Struc-tures and Algorithms.Englewood Cliffs, NJ: Prentice Hall, 1992:264-292.[1] Bria s,Page L.The anstomy of a lange-scale bypertextual Web [6] 吴家麒.谭永基.PageRank算法的优化和改进[]计算机工程与应search eninC(CVPocodings of the 7 Intenational World Wide用.2009.45( 16):5中国煤化工Wab Cofarence. Astalia Bisbane:lbevia Sciace, 198107-17.1 [] 刘惠义.董志勇基MHCNMH(e Method的网[2] Npd search and portal site study(EB/OL].(2008)[2010-07-28].页评估新算法[].计66-69.