具有時(shí)間反饋的PageRank改進(jìn)算法

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

2、關(guān)的網(wǎng)頁(yè)的PageRank值時(shí),符合人們的一般期望,是有效的.Seidel迭代算法有利于提高算法效率.關(guān)鍵詞:PageRank;Seidel迭代;時(shí)間反饋;搜索引擎中圖分類號(hào):G202文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):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ù)日益深人生活,使我們面對(duì)的信息出現(xiàn)了爆炸式的增長(zhǎng).1994年,最早的搜索引擎WorldWideWebWorm標(biāo)引了11萬(wàn)網(wǎng)頁(yè),到1997年,搜索引擎所標(biāo)引的網(wǎng)頁(yè)已達(dá)2100M,2000年可標(biāo)引的網(wǎng)頁(yè)已超過(guò)1O億張.著名的搜索引擎Google擁有1O億個(gè)網(wǎng)址,3O億個(gè)網(wǎng)頁(yè),3.9億張圖像,而且,今天仍然以每天超過(guò)100萬(wàn)張的速度在增長(zhǎng).面對(duì)互聯(lián)網(wǎng)如此巨大的信息量,人們開始注意到如何對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行挖掘是一個(gè)重要的問(wèn)題,并對(duì)此展開了大量的研究.本文的論述集中在如何對(duì)網(wǎng)絡(luò)的組織結(jié)構(gòu)和鏈接關(guān)系進(jìn)行挖掘,以產(chǎn)生我們需要的信息.目前基于網(wǎng)絡(luò)的組織結(jié)構(gòu)和鏈接關(guān)系進(jìn)

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

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

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

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

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

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

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

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

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

15、次查詢結(jié)果,發(fā)現(xiàn)新算法提供的推薦網(wǎng)頁(yè)質(zhì)量要好于傳統(tǒng)的PageRank算法,特別一些近期的新聞能迅速出現(xiàn)在推薦結(jié)果中,并且能在推薦結(jié)果中占據(jù)比較靠前的位置.4結(jié)論在新算法中,引入時(shí)間反饋因子,使網(wǎng)頁(yè)的發(fā)布時(shí)間長(zhǎng)短影響網(wǎng)頁(yè)的P尺值大小,這是可行的.并且,實(shí)驗(yàn)顯示,新算法PageRankTimes有利于舊網(wǎng)頁(yè)的下沉,新網(wǎng)頁(yè)的上浮,這與人們的期望是一致的.參數(shù)e的大小不影響最后的P尺值分布,但影響算法迭代的過(guò)程,一般取e一0.15/n(為總的頁(yè)面數(shù))較為合適.參考文獻(xiàn):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àn)維網(wǎng)的鏈接結(jié)構(gòu)分析及其應(yīng)用綜述J.軟件,2003,14(10):17681780.5宋聚平,王永成,尹中航,等.對(duì)網(wǎng)頁(yè)P(yáng)ageRank算法的改進(jìn)J.上海交通大學(xué),2003,37(3):397400.6張嶺,馬范援.加速評(píng)估算法:一種提高Web結(jié)構(gòu)挖掘質(zhì)量的新方法J.計(jì)算機(jī)研究與發(fā)展,2004,4I(I):98103.(責(zé)任編輯:劉巖)(上接第267頁(yè))控制/一,</控制增量/.k/s圖5有PID反饋校正時(shí)的控制量及其增量4結(jié)論在建模過(guò)程中,由于干擾,噪

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