具有時間反饋的PageRank改進算法

1、具有時間反饋的PageRank改進算法第33卷第3期2005年6月浙江工業(yè)大學(xué)J0URNALOFZHEJIANGUNIVERSITYOFTECHNOLOGYVo1.33No.3Jun.20050具有時間反饋的PageRank改進算法戚華春,黃德才,鄭月鋒(浙江工業(yè)大學(xué)信息工程學(xué)院,浙江杭州310014)摘要:針對某一類網(wǎng)頁(比如新聞網(wǎng)頁)在互聯(lián)網(wǎng)上發(fā)布時間越長,其信息的重要性將隨之下降這一事實,在傳統(tǒng)的PageRank算法中加入時間反饋因子,實現(xiàn)網(wǎng)頁因發(fā)布時間的長短,其PageRank值也隨之上下浮動.并采用Seidel迭代算法加速迭代收斂過程.實驗結(jié)果表明,改進后的算法在計算這類與發(fā)布時間相

2、關(guān)的網(wǎng)頁的PageRank值時,符合人們的一般期望,是有效的.Seidel迭代算法有利于提高算法效率.關(guān)鍵詞:PageRank;Seidel迭代;時間反饋;搜索引擎中圖分類號:G202文獻標識碼:A文章編號:1006-4303(2005)03027204AnimprovedPageRankalgorithmwithtimefeedbackingQIHuachun,HUANGDecai,ZHENGYuefeng(CollegeofInformationEngineering,ZhejiangUniversityofTechnology,Hangzhou310014,China)Abstract:

3、PageRankisawebpagerankingalgorithmproposedbyGoogle,awellknownsearchengine.Thealgorithmisaniterativeprocessthatdetermineswebpagerankingbasedonpagelinkstructure,orcocitation.PageRankisasuccessful,butnotaperfectalgorithm.Forinstance,anolderpageisalwaysanimportantpagebecausethemoreolderitis,themorelinki

4、npagesithas.Soanewpageisusuallynotimportant.Forthis,wefirstintegratedpagetimeinformationwithPageRankcalculation,andthenemployedSeidel'smethodtospeeduptheconvergenceoftheiterationprocess.Experimentalresultsshowthatthenewalgorithmisgoodandreasonable.Keywords:PageRank;Seideliteration;timefeedbackin

5、g;searchengine引言隨著互聯(lián)網(wǎng)技術(shù)日益深人生活,使我們面對的信息出現(xiàn)了爆炸式的增長.1994年,最早的搜索引擎WorldWideWebWorm標引了11萬網(wǎng)頁,到1997年,搜索引擎所標引的網(wǎng)頁已達2100M,2000年可標引的網(wǎng)頁已超過1O億張.著名的搜索引擎Google擁有1O億個網(wǎng)址,3O億個網(wǎng)頁,3.9億張圖像,而且,今天仍然以每天超過100萬張的速度在增長.面對互聯(lián)網(wǎng)如此巨大的信息量,人們開始注意到如何對網(wǎng)絡(luò)數(shù)據(jù)進行挖掘是一個重要的問題,并對此展開了大量的研究.本文的論述集中在如何對網(wǎng)絡(luò)的組織結(jié)構(gòu)和鏈接關(guān)系進行挖掘,以產(chǎn)生我們需要的信息.目前基于網(wǎng)絡(luò)的組織結(jié)構(gòu)和鏈接關(guān)系進

6、行挖掘的主要算法有兩種L1:(1)PageRank算法2:該算法提取網(wǎng)頁的超鏈接信息,進行離線計算,得出網(wǎng)頁的PR值,并進行排序,以發(fā)現(xiàn)網(wǎng)絡(luò)中最主要的頁面.收疆日期:20041013作者簡介:戚華春(1979一),男,浙江杭州人,碩士研究生,主要研究方向為網(wǎng)絡(luò)應(yīng)用,數(shù)據(jù)挖掘和遺傳算法.第3期戚華春,等:具有時間反饋的PageRank改進算法(2)HITS算法3:該算法將網(wǎng)頁分為錨頁(Hub)和權(quán)威頁(Authority),并通過這兩種網(wǎng)頁相互增強,進行迭代,以最終的網(wǎng)頁權(quán)威值為依據(jù)對結(jié)果進行排序,以發(fā)現(xiàn)網(wǎng)絡(luò)中最主要的頁面.上述兩種算法各有優(yōu)缺點,本文就主要針對PageRank算法的一些不足,提

7、出一個校正的算法PageRankTimes算法.1PageRank算法與缺陷1.1PageRank算法傳統(tǒng)情報檢索理論中的引文分析方法是確定學(xué)術(shù)文獻權(quán)威性的一個重要方法,即根據(jù)引文的數(shù)量來確定文獻的權(quán)威性.PageRank算法的發(fā)明者對網(wǎng)絡(luò)的超鏈接結(jié)構(gòu)和文獻引文機制的相似性進行了研究,借鑒引文分析思想計算網(wǎng)絡(luò)文檔的重要性,利用網(wǎng)絡(luò)自身的超鏈接結(jié)構(gòu)給所有的網(wǎng)頁確定一個重要性等級數(shù).比如,當從網(wǎng)頁A鏈接到網(wǎng)頁B時,就認為"網(wǎng)頁投了網(wǎng)頁B一票",即增加了網(wǎng)頁B的重要性.最后根據(jù)各網(wǎng)頁的得票數(shù)來評定其重要性,以此來幫助實現(xiàn)排序算法的優(yōu)化,而這個重要性的量化指標就是網(wǎng)頁的P尺值.1.

8、2PageRank算法描述PageRank算法的數(shù)學(xué)表示為PR()一(1一)+d?(+而PR(T2)C+.?+C)(1)I(丁】).c(丁2).(丁)/其中:PR()為網(wǎng)頁的PageRank值;丁l,丁2,丁為網(wǎng)頁的鏈入網(wǎng)頁;PR(丁)為網(wǎng)頁丁的PR值,i一1,2,2;C(丁)為網(wǎng)頁丁的鏈出鏈接數(shù)量,i一1,2,72;為衰減因子,0<d<1,通常取值為0.85.通過迭代算法可以計算出P尺()的最終值.1.3PageRank算法的缺陷PageRank算法的主要缺陷是:該算法偏重舊網(wǎng)頁.由式(1)可以看出,決定一個網(wǎng)頁的P尺值的主要因素是指向該網(wǎng)頁的鏈接個數(shù),也就是說一

9、個網(wǎng)頁在網(wǎng)絡(luò)上存在的時間越長,就越有可能被其他更多的網(wǎng)頁所鏈接,按照算法則可以認為舊的網(wǎng)頁比新的網(wǎng)頁更可能具有較高的PR值,舊網(wǎng)頁比新網(wǎng)頁更重要,即PageRank算法偏重舊網(wǎng)頁.但這在實際的網(wǎng)絡(luò)環(huán)境中是有出入的,因為人們更希望看到的是新內(nèi)容,特別是有關(guān)新聞和商務(wù)信息.比如,一個很重要的網(wǎng)頁被放到網(wǎng)絡(luò)上不久,由于時間短暫,許多其他網(wǎng)頁還沒有指向它,那么通過式(1)計算出的網(wǎng)頁P尺值就很低,在搜索引擎返回的結(jié)果中往往會把它排在較后的位置,這正好與用戶的要求相反.所以,PageRank算法需要改進.2算法改進2.1基本思路通過式(1)計算出的網(wǎng)頁PR值并不能很好地反映網(wǎng)頁的實際重要性,當然也就不能

10、很好地滿足用戶需求.面對這個問題,本文認為通過指向某個網(wǎng)頁的超鏈接來計算該網(wǎng)頁的PR值時,應(yīng)該考慮到其他因素,比如網(wǎng)頁的發(fā)布日期.把網(wǎng)頁的發(fā)布日期引入PageRank算法,使在網(wǎng)絡(luò)上存在比較長時間的網(wǎng)頁慢慢沉下去,新的網(wǎng)頁能迅速浮上來.但由于現(xiàn)在很多網(wǎng)頁是由程序自動生成的,并且大量的HTML網(wǎng)頁的格式不規(guī)范,很難從網(wǎng)頁中提取到該網(wǎng)頁的發(fā)布時間.為此,我們把網(wǎng)頁的存在時間通過搜索引擎搜索的周期數(shù)來表征,這一轉(zhuǎn)換的核心思想是基于這樣一個事實:一般而言,搜索引擎的搜索周期為半個月到一個月,如果一個網(wǎng)頁存在的時間較長,那它將在每個搜索周期里都將被搜索到(在同一個搜索周期里不管搜索到該網(wǎng)頁幾次,都算作1

11、次),即頁面的存在時間正比于搜索引擎搜索到該頁面的次數(shù)丁.網(wǎng)頁的時間反饋因子,即一e/T(2)式中:為網(wǎng)頁的時間反饋因子;T為一個網(wǎng)頁被搜索引擎訪問的周期次數(shù);為常數(shù),它的取值受到式(1)中d的影響,且也和搜索引擎的搜索周期相關(guān),是一個實驗數(shù)據(jù).2.2算法的改進在新算法PageRankTimes中,我們加入了時間反饋因子,公式(1)修正為PR()一(1一)+d?(+P而R(T2)C+.+CI(丁1).c(丁2).(丁)/."(3)顯然,式(3)也可以寫為PR+l一(1一)+d?M?PR+W(4)其中,令F為頁面甜的鏈出鏈接集合,N一IF.I,則.一1/,如果有從網(wǎng)頁甜到V的鏈接,反之

12、帆.一0.故根據(jù)線性代數(shù)的知識,因為IIMII一1,所以迭代是收斂的,并且是有限次迭代.?274?浙江工業(yè)大學(xué)第33卷2.3加速收斂的Seidel技巧對于迭代解出的過渡矩陣的特征向量,要用它對關(guān)鍵詞匹配的搜索結(jié)果進行排序,顯然我們關(guān)心的不是它的大小,而是它的方向(甚至只是其各分量的大小順序).由此,可以在不影響特征向量的方向的前提下對進行適當?shù)淖儞Q以加快迭代的收斂速度.簡單迭代法的分量形式為i一1一,z:+,J一1|一i其中,k一1,2,3,n.顯然,在計算時,都已經(jīng)求出,一般地,后計算出的結(jié)果更接近最終結(jié)果.因此可以用這些新值來計算,于是迭代形式變?yōu)閕1=m,z+一1|一i這就是Seidel

13、技巧(計算過程中總是利用最新算出來的值,也稱Seidel迭代法).2.4新算法PageRankTimes描述輸入是:通過搜索引擎搜索網(wǎng)絡(luò),獲得對應(yīng)網(wǎng)絡(luò)子圖的鄰接矩陣A,及對應(yīng)的搜索次數(shù)即時間向量.可以調(diào)整時間向量的值,用于表示網(wǎng)頁存在時間的長短.輸出是:頁面排序的PR值.算法的步驟:(1)獲得網(wǎng)絡(luò)子圖.(2)確定每個URL的查詢周期次數(shù),即時間向量.(3)用每個URL的查詢周期次數(shù)的倒數(shù),計算該網(wǎng)頁的時間反饋因子.(4)按式(3)計算每個分量的PR值.(5)迭代,直至收斂.(6)結(jié)果規(guī)范化輸出.3算法實驗圖1是用于仿真的網(wǎng)絡(luò)子圖(為便于分析,假設(shè)該子圖中的頁面是關(guān)于同一查詢主題的).3.1仿真

14、結(jié)果分析圖2,系列1為時間反饋因子:(1,1,1,1,1,1),用于模擬傳統(tǒng)的PageRank算法,即無時間反饋的情況;系列2為時間反饋因子W一(1,1,1,1/10,1,1),是改進的PageRankTimes算法.圖1實驗網(wǎng)絡(luò)仿真子圖0?5囫系列1口系列0.050l23456Page號圖3取不同e值的效果圖列4列5為驗證新算法的實際有效性,在一個月內(nèi),我們還對新浪網(wǎng)爬行了4次,每次獲得10萬張有效網(wǎng)第3期戚華春,等:具有時間反饋的PageRank改進算法?275?頁,應(yīng)用傳統(tǒng)PageRank算法和新算法分別進行排序運算,然后進行查詢分析.在對比前后4

15、次查詢結(jié)果,發(fā)現(xiàn)新算法提供的推薦網(wǎng)頁質(zhì)量要好于傳統(tǒng)的PageRank算法,特別一些近期的新聞能迅速出現(xiàn)在推薦結(jié)果中,并且能在推薦結(jié)果中占據(jù)比較靠前的位置.4結(jié)論在新算法中,引入時間反饋因子,使網(wǎng)頁的發(fā)布時間長短影響網(wǎng)頁的P尺值大小,這是可行的.并且,實驗顯示,新算法PageRankTimes有利于舊網(wǎng)頁的下沉,新網(wǎng)頁的上浮,這與人們的期望是一致的.參數(shù)e的大小不影響最后的P尺值分布,但影響算法迭代的過程,一般取e一0.15/n(為總的頁面數(shù))較為合適.參考文獻:1CooleyR,MobasherB,SrivastavaJ.Webmining:Informationandpatterndisco

16、veryontheWorldWideWebrA.9thInternationalConferenceonToolswithArtificialIntelligence(ICTAI'97).IEEEComputerSocietyC.1997.558567.2PageL,BrinS,MotwaniR,eta1.Thepagerankcitationranking:BringingordertotheWEBEB/OL./8O9O/pub/199966/199911-11.3JonMK.Authoritativesourcesinahyp

17、erlinkedenvironmentJ.JournaloftheACM,1999,46(5):668677.4王曉宇,周傲英.萬維網(wǎng)的鏈接結(jié)構(gòu)分析及其應(yīng)用綜述J.軟件,2003,14(10):17681780.5宋聚平,王永成,尹中航,等.對網(wǎng)頁PageRank算法的改進J.上海交通大學(xué),2003,37(3):397400.6張嶺,馬范援.加速評估算法:一種提高Web結(jié)構(gòu)挖掘質(zhì)量的新方法J.計算機研究與發(fā)展,2004,4I(I):98103.(責任編輯:劉巖)(上接第267頁)控制/一,</控制增量/.k/s圖5有PID反饋校正時的控制量及其增量4結(jié)論在建模過程中,由于干擾,噪

18、聲和非線性等因素的存在,不可避免的存在著模型失配問題.通常廣義預(yù)測控制通過不斷的在線辨識克服建模誤差,它本質(zhì)上是一種在線建模過程,不僅計算耗時,而且辨識結(jié)果與實際過程之間仍然存在著一定的偏差.文中采用簡單的PID算法作為反饋校正的手段,能夠有校克服建模誤差,減小計算量,取得滿意的控制效果.提出的方法有三個特點:體現(xiàn)了先進控制和經(jīng)典控制的結(jié)合;體現(xiàn)了基于過去誤差的事后控制和基于預(yù)測信息的超前控制的結(jié)合;體現(xiàn)了基于模型控制和基于非模型控制的結(jié)合.基于這一思想的具體控制策略還有待進一步深入研究.參考文獻:1HapogluH,KaracanS,ErtenKzS,eta1.ParametricandnonparametricmodelbasedcontrolofapackeddistillationcolumnJ.ChemicalEngineeringandProcessing,2001,40(6):537544.2張峻,席裕庚.基于幾何分析的約束預(yù)測控制直接算法J.控制與決策,1997,12(2):184187.3毛志忠,楊林.一種解決預(yù)測控制輸人信號受約束問題的方法J.控制與決策,1994,9(2):230233.4席裕庚.復(fù)雜工業(yè)過程的滿意控制J.信息與控制,1995,24(1):143O.5陳增強