新的PageRank優(yōu)化算法

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