94_2012,48(6)Computer Engineering and Applications計(jì)算機(jī)工程與應(yīng)用新的PageRank優(yōu)化算法蔣永輝,吳洪麗JIANG Yonghui, WU Hongli海南師范大學(xué)信息科學(xué)技術(shù)學(xué)院,海口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在搜索過程中重復(fù)性地把當(dāng)前受歡迎的網(wǎng)頁(yè)放在搜索結(jié)果的首要位置，而不受歡迎的網(wǎng)頁(yè)被大多數(shù)用戶忽略的問題，采用了一種改進(jìn)的評(píng)估函數(shù)及有效的用戶模型,獲得了一個(gè)新的PageRank優(yōu)化算法。實(shí)驗(yàn)結(jié)果表明，該算法達(dá)到了較好的公平性。關(guān)鍵詞:PageRank算法;評(píng)估函數(shù);用戶模型DOI: 0778.1012-8331.2012.06.028文 章編號(hào):1002 8331(2012)06 0094-02文獻(xiàn)標(biāo)識(shí)碼:A中圖分類號(hào):TP3011引言其中, A,表示用戶第-一次訪問網(wǎng)頁(yè)p就會(huì)對(duì)該網(wǎng)頁(yè)有不錯(cuò)的PageRank算法"是由Brin S和Page L在1998年提出的一評(píng)價(jià), Lp表示用戶喜歡該網(wǎng)頁(yè); Q(p)是-個(gè)條件概率,表示一種用于標(biāo)識(shí)網(wǎng)頁(yè)的等級(jí)/重要性的方法.同其他網(wǎng)頁(yè)排名算法個(gè)用戶在第一一次訪問網(wǎng)頁(yè)p時(shí)就會(huì)喜歡該網(wǎng)頁(yè)。通過該定義,相比. PageRank具有實(shí)現(xiàn)簡(jiǎn)單.易于理解等優(yōu)點(diǎn)。基于Page-可以假設(shè)把網(wǎng)頁(yè)p展示給所有的用戶來(lái)測(cè)定該網(wǎng)頁(yè)的質(zhì)量。Rank的有效性”,很多搜索引擎采用了PageRank作為其網(wǎng)頁(yè)例如，在100個(gè)用戶中,假設(shè)有90個(gè)用戶在訪問網(wǎng)頁(yè)p后會(huì)喜排名算法。PageRank 能夠很好地捕捉高質(zhì)量的網(wǎng)頁(yè),從而使歡它,則它的質(zhì)量Q(p)即為0.9。下一節(jié)將討論在沒有用戶反大多數(shù)用戶對(duì)Google和其他的搜索引擎所返回的查詢結(jié)果滿饋的情況下如何測(cè)定該網(wǎng)頁(yè)的質(zhì)量。，意程度較高”。但是, PageRank會(huì)出現(xiàn)“富者更富”問題,搜索引擎會(huì)將等該定義是對(duì)網(wǎng)頁(yè)真實(shí)質(zhì)量的- -個(gè)合理評(píng)價(jià)標(biāo)準(zhǔn)"。在實(shí)級(jí)高的網(wǎng)頁(yè)返回給用戶,而等級(jí)低即使高質(zhì)量的網(wǎng)頁(yè)卻被大際中,某個(gè)用戶可能對(duì)一個(gè)網(wǎng)頁(yè)評(píng)價(jià)很高,而另-用戶可能覺多數(shù)用戶忽略,對(duì)于新產(chǎn)生的高質(zhì)量的網(wǎng)頁(yè)更是如此，其原因得該網(wǎng)頁(yè)完全沒用.因此當(dāng)對(duì)一一個(gè)網(wǎng)頁(yè)有不同的評(píng)價(jià)的時(shí)候，是在一-開始新產(chǎn)生的網(wǎng)頁(yè)還未被搜索引擎索引。這些網(wǎng)頁(yè)可選取對(duì)該網(wǎng)頁(yè)評(píng)價(jià)高的用戶的投票是較為合理的。能被用戶永久忽略,從長(zhǎng)期來(lái)看,這也會(huì)在總體上降低搜索結(jié)2.2 測(cè)定網(wǎng)頁(yè)質(zhì)量果的質(zhì)量"。根據(jù)上節(jié)定義,如果想精確地測(cè)定-一個(gè)網(wǎng)頁(yè)的質(zhì)量,就需針對(duì)這個(gè)問題.本文提出了一種形式化框架.通過建立近要大量真實(shí)用戶訪問該網(wǎng)頁(yè)并從他們那里得到反饋。但這顯似于真實(shí)合理的用戶模型來(lái)分析網(wǎng)頁(yè)的真實(shí)質(zhì)量來(lái)糾正搜索然是不可能做到的.因此需要在沒有用戶參與的情況下測(cè)定引擎的“偏見”,然后以一種實(shí)用的方法來(lái)消除內(nèi)在的網(wǎng)頁(yè)質(zhì)個(gè)網(wǎng)頁(yè)的質(zhì)量:量問題,以避免PageRank固有的“偏見”問題,并結(jié)合實(shí)驗(yàn)數(shù)據(jù)c. dP(p)Vd(2)設(shè)計(jì)網(wǎng)頁(yè)質(zhì)量評(píng)估器。該質(zhì)量評(píng)估器能有效消除“富者更富”其中,C是-一個(gè)常量, P(p) 表示當(dāng)前網(wǎng)頁(yè)p的受歡迎程度，P(p)問題,使搜索結(jié)果更符合用戶的真實(shí)需求。dP(p)dr表示網(wǎng)頁(yè)p受歡迎程度的增加量。2 NPRO 所涉及的核心方案2.3網(wǎng)絡(luò)用 戶模型在本文的NPRO算法中. PageRank算法以及該算法中所首先以V(p,1)來(lái)度量網(wǎng)頁(yè)的受歡迎程度,即從時(shí)間1開涉及的各種參數(shù),需要根據(jù)具體情況和需要解決的實(shí)際問題始后的單位時(shí)間內(nèi)網(wǎng)頁(yè)p被訪問的次數(shù)。以A(p,1)來(lái)度量用選取合適的取值.這里不做介紹.有興趣請(qǐng)參閱文獻(xiàn)[5]。下面戶熟知度,即在時(shí)間t時(shí),用戶對(duì)網(wǎng)頁(yè)p的熟知度的比例。例詳細(xì)介紹- -下本文的核心方案設(shè)計(jì)。如.到當(dāng)前為止.有100 000個(gè)用戶訪問過網(wǎng)頁(yè)P(yáng) ,且熟知該網(wǎng)2.1 新的網(wǎng)頁(yè)質(zhì)量評(píng)估標(biāo)準(zhǔn)頁(yè),則該網(wǎng)頁(yè)的用戶熟知度A(p,，)就為0.1。需要注意的是,用Q(p)=P(LM)1)戶熟知度表示的是已經(jīng)訪問過該網(wǎng)頁(yè)且能夠確定是否喜歡該中國(guó)煤化工基金項(xiàng)目:海南省教育廳基金資助(No HISK2009-75)。作者簡(jiǎn)介:蔣永輝(1979-),男.硬士生,研究領(lǐng)域:信息檢索、文本挖掘:吳洪畫(1976- -), 女,博士生.MYHCNMH(cn@126.com收稿日期:201008-27;維國(guó)日期:2010-11-09;CNKI出:210302:/://ww.coki nekcmctei.121210210101.,1m)蔣永輝,吳洪麗:新的PageRank優(yōu)化算法2012 ,48(6)95網(wǎng)頁(yè)的用戶數(shù)量.而網(wǎng)頁(yè)受歡迎度表示的是用戶知道該網(wǎng)頁(yè)質(zhì)量關(guān)系如下:且喜歡該網(wǎng)頁(yè)的數(shù)量。因此,在時(shí)間t時(shí),網(wǎng)頁(yè)p受歡迎度為dP(p, l)/dr2(p)=(嚴(yán))Pp.0X1-(p.而(14)P(p.I)=A(p.t). Q(p)(3)dP(p, t)dt2.4網(wǎng)絡(luò)用戶模型分析以l(p,t)表示(4)2 P:UO ,稱為相對(duì)受歡迎度增量函如果知道網(wǎng)頁(yè)P(yáng)的當(dāng)前受歡迎度,就可以估計(jì)出有多少數(shù)。從圖1可以看出在一個(gè)網(wǎng)頁(yè)剛被創(chuàng)建時(shí), P(p,1) 并沒有用戶已經(jīng)訪問了該網(wǎng)頁(yè)。在除去這部分用戶之外,喜歡網(wǎng)頁(yè)p很好地反映出該網(wǎng)頁(yè)的質(zhì)量,然而,訪問該網(wǎng)頁(yè)的用戶大多數(shù)的用戶比例就是Q(p) ,從而可以得出網(wǎng)頁(yè)p受歡迎度的增長(zhǎng)是第一次訪問該網(wǎng)頁(yè)。因此,如果該網(wǎng)頁(yè)是-一個(gè)高質(zhì)量的網(wǎng)幅度,有下式:頁(yè),其受歡迎度會(huì)迅速增大,隨著時(shí)間進(jìn)行.越來(lái)越多的用戶H(p.0=1-56ro.wu4)知道了該剛頁(yè)，其受歡迎度保持不變,且網(wǎng)頁(yè)的質(zhì)量e(p)總是由式(4)可得出網(wǎng)頁(yè)受歡迎度改進(jìn)函數(shù)如下:等于相對(duì)受歡迎度增量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)是網(wǎng)頁(yè)p在零時(shí)刻的受歡迎度,也就是在網(wǎng)頁(yè)p0.15第一次被創(chuàng)建時(shí)的受歡迎度。其證明如下: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)與時(shí)間關(guān)系圖因此(-盧量=( -M2(p)7)4實(shí)驗(yàn)在以上討論中.假設(shè)網(wǎng)頁(yè)的質(zhì)量是基于當(dāng)前該網(wǎng)頁(yè)的受等式(7)稱為菲爾哈斯特等式。該等式的解為:歡迎程度以及對(duì)瞬時(shí)時(shí)間的導(dǎo)數(shù)。在實(shí)踐中,無(wú)法對(duì)瞬時(shí)時(shí)f()=一間進(jìn)行有效測(cè)量,因此,只有在離散時(shí)間點(diǎn)對(duì)PageRank的增量1+Ce"Q(p)t進(jìn)行估計(jì): .期.C是一個(gè)常數(shù)用來(lái)確定邊界條件。因?yàn)閒()=e“I[p,nd,Q(p,t)= nRp(yY44]+ PR(p,t)(15) .PR(p.)所以期, PR(p,t)是網(wǎng)頁(yè)p在時(shí)間1時(shí)刻的PageRank值, OPR(p,t)=efPp.Xd=- !PR(P.t)-PR(p.4_)且0,=1,-4_1.假設(shè)-一個(gè)網(wǎng)頁(yè)其初始質(zhì)1+Ce"Q(p)x量Q為0.4,根據(jù)公式00=0.4 + 0.000 6t ,在t=S00時(shí)達(dá)到0.7,(ECx)CEi0r在每個(gè)時(shí)間間隔測(cè)量網(wǎng)頁(yè)質(zhì)量值,得出真實(shí)的質(zhì)量 受歡迎度上式兩邊同時(shí)對(duì)t進(jìn)行微分,可得- IP(p,1)=-1+Ce-px和估計(jì)質(zhì)量值之間的關(guān)系如圖2所示。從圖中可得出:(1)評(píng)估器Q'可以很好地測(cè)量網(wǎng)頁(yè)的真實(shí)質(zhì)量值。重新整理該式可得(2) Q'對(duì)最終的受歡迎度來(lái)說(shuō)不是-一個(gè)好的預(yù)測(cè)器,例P(p,)=- C2()(10)如,在1= I時(shí)Q'≈0.4 ,但在t= 500時(shí)最終的受歡迎度是0.7。然而,應(yīng)該注意到的是,對(duì)于網(wǎng)頁(yè)p當(dāng)前受歡迎度來(lái)說(shuō)，Q'對(duì)由等式( 10)可以求得常量C,因?yàn)橛谧罱K的網(wǎng)頁(yè)受歡迎度有更好的預(yù)測(cè)?？傊?從總體來(lái)說(shuō),Q2(P)和Q有著相似的總體走勢(shì)。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因此,當(dāng)1→∞時(shí)，P(p,I)- + Q(p) ,網(wǎng)頁(yè)p的受歡迎度最終會(huì)100 200 3000 500趨近于Q(p)。圖2實(shí)際和測(cè)鼠的網(wǎng)貞質(zhì)量值3 NPRO 質(zhì)鼠評(píng)估器的實(shí)現(xiàn)5結(jié)束語(yǔ)中國(guó)煤化工公式(5)所示的受歡迎度改進(jìn)函數(shù)對(duì)時(shí)間的導(dǎo)數(shù)可以用本文提出了MYHCNMHGnk優(yōu)化算法,來(lái)評(píng)估-一個(gè)網(wǎng) 頁(yè)的質(zhì)量,網(wǎng)頁(yè)受歡迎度對(duì)時(shí)間的導(dǎo)數(shù)與網(wǎng)頁(yè)(下轉(zhuǎn)154頁(yè))1542012 , 48(6)Computer Engineering and Applications計(jì)算機(jī)工程與應(yīng)用如圖5所示,本文方法對(duì)于檢驗(yàn)樣本具有更強(qiáng)的泛化能[2] 劉燕南收視率指標(biāo)在電視節(jié)目?jī)r(jià)值評(píng)價(jià)中的地位[].新聞學(xué)與傳力,而且隨眷樣本數(shù)量增加其優(yōu)勢(shì)更加明顯。進(jìn)一步將該算[3]熊華明，謝長(zhǎng)生，夏征字電視節(jié)目綜合評(píng)估與預(yù)警系統(tǒng)的設(shè)計(jì)與播學(xué), 2002(3):30-31.法與其他數(shù)據(jù)挖掘算法進(jìn)行比較,具體如表1所示。實(shí)現(xiàn)[].計(jì)算機(jī)工程與應(yīng)用,2002 ,38(20):215-217.表1不同分類 方法分類效果比較表[4]劉輝.電視收視率預(yù)測(cè)算法研究及軟件實(shí)現(xiàn)[D].上海:上海交通大分類算法性能指標(biāo)數(shù)值學(xué),2008.訓(xùn)練時(shí)間/s4.616標(biāo)準(zhǔn)支持向量機(jī)[5]劉輝,杜秀華，基于ARMA模型的電視臺(tái)收視率預(yù)測(cè)方法設(shè)計(jì)和實(shí)支持向量個(gè)數(shù)4.52(1-v-1算法)現(xiàn)[].控制工程,2009. 156)9-11.分類精度/(%) 99.00訓(xùn)練時(shí)間/s 2.458[6]劉小錚.試談收視事定量預(yù)測(cè)的數(shù)學(xué)模型[EB/0OL.2004)http:傳統(tǒng)超球分類方法支持向量個(gè)數(shù) 3.49//www.jstv.com.分類精度/(%) 98.90[7] Zheng Lilei.Audicnc rating prediction of new TV programs based訓(xùn)練時(shí)間/s 1.912on GM(1,1) envelopment model[C]/Proceedings of IEEE Inter-半模糊核聚類算法支持向量個(gè)數(shù) 3.23national Conference on Grey systems and Inelligent Services,分類精度/(%)2009, 11 :388-391.注:表中數(shù)值均為50次重復(fù)計(jì)算的平均值。[8]白冰,張晶,蘇勇.基于數(shù)據(jù)挖掘的收視率數(shù)據(jù)預(yù)處理方法([]科學(xué)通過表1可以看出,標(biāo)準(zhǔn)支持向量機(jī)( 1-v-1算法)訓(xùn)練時(shí)技術(shù)與工程，2007.7(18):4741-4745.間較長(zhǎng)，這主要是由于其進(jìn)行不同類別之間的兩兩對(duì)比.使計(jì)[9] 張晶,白冰,蘇勇基于貝葉斯樹絡(luò)的電視節(jié)目收視率預(yù)測(cè)研究[]算量呈現(xiàn)幾何增長(zhǎng)。而傳統(tǒng)超球分類方法由于將每類樣本用[10]涂娟娟基于數(shù)據(jù)挖掘技術(shù)的電視節(jié)目收視率預(yù)測(cè)研究[D].江蘇科學(xué)技術(shù)與工程,2007.7(19)4099-5102.超球結(jié)構(gòu)進(jìn)行描述,這樣不會(huì)使計(jì)算量隨樣本與分類數(shù)量增鎮(zhèn)江:江蘇科技大學(xué),2007.加而增長(zhǎng)過快,尤其在樣本數(shù)量較大,類別較多時(shí),其優(yōu)勢(shì)更[]涂娟娟.劉同明基于決策樹的電視節(jié)目收視率預(yù)測(cè)模型[D.微計(jì)為明顯。半模糊核聚類算法盡可能留下處于邊緣位置的樣本算機(jī)信息,2007,23:251-252.(通過數(shù)據(jù)的半模糊化處理) ,而使其只選擇可能成為超球球[12] Hart J,Kanlber M.數(shù)據(jù)挖掘:概念與技術(shù)[M].范明,盂小蜂,譯面支持向量的樣本進(jìn)行訓(xùn)練，因而在保持較高分類精度基礎(chǔ)北京:機(jī)械工業(yè)出版社,2001.上訓(xùn)練時(shí)間進(jìn)-步縮短。[13]黃鳳崗,宋克歐.模式識(shí)別MJ哈爾濱:哈爾濱工程大學(xué)出版社，4結(jié)語(yǔ)[14] 沈清.湯霖模式識(shí)別導(dǎo)論[M].長(zhǎng)沙:國(guó)防科技大學(xué)出版社, 1991.本文針對(duì)收視率數(shù)據(jù)預(yù)測(cè)特點(diǎn),提出了半模糊核聚類分[15] 張莉，周偉達(dá),焦李成核聚類算法[小.計(jì)算機(jī)學(xué)報(bào)2002.25(6);類方法。與傳統(tǒng)方法不同之處在于引入樣本隸屬度概念,并587 -590.通過半模糊核聚類算法得到其隸屬度在傳統(tǒng)超球支持向量(16] David M J,Robert P Wsuppr veotor domin drpio[]Machine Learmning , 2004.54:45-66.機(jī)基礎(chǔ)上進(jìn)-步減少了計(jì)算量。實(shí)驗(yàn)表明,該方法在具有超[17]朱美琳,劉向東,陳世福用球結(jié)構(gòu)的支持向量機(jī)解決多分類問球支持向量機(jī)分類器優(yōu)點(diǎn)的同時(shí),有效提高了訓(xùn)練速度和分題[].南京大學(xué)學(xué)報(bào):自然科學(xué)版。2003.39(2):153-158.類精度，同時(shí)使其訓(xùn)練方法更加符合人們對(duì)于收視率數(shù)據(jù)預(yù)[18]伍忠東，高新波.謝維信基f核方法的模糊聚類算法[D.西安電測(cè)問題的思維習(xí)慣。子科技大學(xué)學(xué)報(bào), 2004,31(4).[19]裴繼紅,范九倫.謝維信.- -種新的高效軟聚類方法:截集模糊C-參考文獻(xiàn):均值聚類算法[小.電子學(xué)報(bào), 1998,26(2):83-86.[1]喻國(guó)明.李彪收視率全效評(píng)估體系研究一以電視劇為例[].新 [20] 王蘭柱中國(guó)電視收視年鑒2010[M].北京:中國(guó)傳媒大學(xué)出版社,聞學(xué)與傳播學(xué), 2009(4):36-38.2010:112-116.(上接95頁(yè))htt//w.oplesseleses/press. 00919.htm.對(duì)許多搜索引擎中當(dāng)前使用的PageRank算法易于出現(xiàn)的“富[3] Mizzaro S.Mesuring the agrement among relevance judge(CV/更富"現(xiàn)象進(jìn)行了改進(jìn)。通過建立有效的網(wǎng)絡(luò)用戶模型獲Proceedings of MIRA Conference.USA:IEEE, 199:672 681.得了大量測(cè)試結(jié)果,并與PageRank算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)41 Harer s Pvriatins in rerevace aseats end 郵measurement of retrieval effectiveness[]Joumal of the American Soci-果表明,本文算法對(duì)存在的問題有明顯改進(jìn),從而為網(wǎng)頁(yè)評(píng)估aty for Informnation Science. 1996.47(1):37-49.提供了更準(zhǔn)確有效的方法。[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算法的優(yōu)化和改進(jìn)[]計(jì)算機(jī)工程與應(yīng)search eninC(CVPocodings of the 7 Intenational World Wide用.2009.45( 16):5中國(guó)煤化工Wab Cofarence. Astalia Bisbane:lbevia Sciace, 198107-17.1 [] 劉惠義.董志勇基MHCNMH(e Method的網(wǎng)[2] Npd search and portal site study(EB/OL].(2008)[2010-07-28].頁(yè)評(píng)估新算法[].計(jì)66-69.