94_2012,48(6)Computer Engineering and Applications計算機工程與應用新的PageRank優(yōu)化算法蔣永輝,吳洪麗JIANG Yonghui, WU Hongli海南師范大學信息科學技術學院,?？?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在搜索過程中重復性地把當前受歡迎的網頁放在搜索結果的首要位置，而不受歡迎的網頁被大多數用戶忽略的問題，采用了一種改進的評估函數及有效的用戶模型,獲得了一個新的PageRank優(yōu)化算法。實驗結果表明，該算法達到了較好的公平性。關鍵詞: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具有實現簡單.易于理解等優(yōu)點?；赑age-可以假設把網頁p展示給所有的用戶來測定該網頁的質量。Rank的有效性”,很多搜索引擎采用了PageRank作為其網頁例如，在100個用戶中,假設有90個用戶在訪問網頁p后會喜排名算法。PageRank 能夠很好地捕捉高質量的網頁,從而使歡它,則它的質量Q(p)即為0.9。下一節(jié)將討論在沒有用戶反大多數用戶對Google和其他的搜索引擎所返回的查詢結果滿饋的情況下如何測定該網頁的質量。，意程度較高”。但是, PageRank會出現“富者更富”問題,搜索引擎會將等該定義是對網頁真實質量的- -個合理評價標準"。在實級高的網頁返回給用戶,而等級低即使高質量的網頁卻被大際中,某個用戶可能對一個網頁評價很高,而另-用戶可能覺多數用戶忽略,對于新產生的高質量的網頁更是如此，其原因得該網頁完全沒用.因此當對一一個網頁有不同的評價的時候，是在一-開始新產生的網頁還未被搜索引擎索引。這些網頁可選取對該網頁評價高的用戶的投票是較為合理的。能被用戶永久忽略,從長期來看,這也會在總體上降低搜索結2.2 測定網頁質量果的質量"。根據上節(jié)定義,如果想精確地測定-一個網頁的質量,就需針對這個問題.本文提出了一種形式化框架.通過建立近要大量真實用戶訪問該網頁并從他們那里得到反饋。但這顯似于真實合理的用戶模型來分析網頁的真實質量來糾正搜索然是不可能做到的.因此需要在沒有用戶參與的情況下測定引擎的“偏見”,然后以一種實用的方法來消除內在的網頁質個網頁的質量:量問題,以避免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優(yōu)化算法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可以看出在一個網頁剛被創(chuàng)建時, 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第一次被創(chuàng)建時的受歡迎度。其證明如下: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優(yōu)化算法,來評估-一個網 頁的質量,網頁受歡迎度對時間的導數與網頁(下轉154頁)1542012 , 48(6)Computer Engineering and Applications計算機工程與應用如圖5所示,本文方法對于檢驗樣本具有更強的泛化能[2] 劉燕南收視率指標在電視節(jié)目價值評價中的地位[].新聞學與傳力,而且隨眷樣本數量增加其優(yōu)勢更加明顯。進一步將該算[3]熊華明，謝長生，夏征字電視節(jié)目綜合評估與預警系統(tǒng)的設計與播學, 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:傳統(tǒng)超球分類方法支持向量個數 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] 張晶,白冰,蘇勇基于貝葉斯樹絡的電視節(jié)目收視率預測研究[]算量呈現幾何增長。而傳統(tǒng)超球分類方法由于將每類樣本用[10]涂娟娟基于數據挖掘技術的電視節(jié)目收視率預測研究[D].江蘇科學技術與工程,2007.7(19)4099-5102.超球結構進行描述,這樣不會使計算量隨樣本與分類數量增鎮(zhèn)江:江蘇科技大學,2007.加而增長過快,尤其在樣本數量較大,類別較多時,其優(yōu)勢更[]涂娟娟.劉同明基于決策樹的電視節(jié)目收視率預測模型[D.微計為明顯。半模糊核聚類算法盡可能留下處于邊緣位置的樣本算機信息,2007,23:251-252.(通過數據的半模糊化處理) ,而使其只選擇可能成為超球球[12] Hart J,Kanlber M.數據挖掘:概念與技術[M].范明,盂小蜂,譯面支持向量的樣本進行訓練，因而在保持較高分類精度基礎北京:機械工業(yè)出版社,2001.上訓練時間進-步縮短。[13]黃鳳崗,宋克歐.模式識別MJ哈爾濱:哈爾濱工程大學出版社，4結語[14] 沈清.湯霖模式識別導論[M].長沙:國防科技大學出版社, 1991.本文針對收視率數據預測特點,提出了半模糊核聚類分[15] 張莉，周偉達,焦李成核聚類算法[小.計算機學報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.機基礎上進-步減少了計算量。實驗表明,該方法在具有超[17]朱美琳,劉向東,陳世福用球結構的支持向量機解決多分類問球支持向量機分類器優(yōu)點的同時,有效提高了訓練速度和分題[].南京大學學報:自然科學版。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算法的優(yōu)化和改進[]計算機工程與應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.