亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        一種改進的PageRank算法

        2013-08-11 07:12:58安徽工程大學(xué)計算機與信息學(xué)院安徽蕪湖241000
        關(guān)鍵詞:迭代法工具箱權(quán)威

        徐 京,陶 皖 (安徽工程大學(xué)計算機與信息學(xué)院,安徽 蕪湖241000)

        21世紀(jì),搜索引擎成為獲取信息的重要工具。而隨著Web數(shù)量的急劇增加,搜索引擎如何以較快的速度給用戶提供權(quán)威的相關(guān)網(wǎng)頁。下面,筆者將提出一種改進的PageRank算法,即在傳統(tǒng)的PageRank算法[1]中加入MapReduce和Gauss-Seidel,以減少迭代次數(shù),減少時間消耗,提高并行效率。

        1 PageRank算法

        PageRank算法用于計算網(wǎng)頁的權(quán)威值,該值是Google對檢索的網(wǎng)頁進行排序的一個重要依據(jù)[2]。PageRank算法由Sergey Brin和Larry Page在1998年4月舉行的第7屆國際萬維大會 (WWW7)上提出[3]。PageRank的基本思想如下:網(wǎng)頁A鏈向網(wǎng)頁B是網(wǎng)頁A對網(wǎng)頁B的認可,視為網(wǎng)頁A對網(wǎng)頁B投了一票。一個網(wǎng)頁得票越多,網(wǎng)頁的權(quán)威值越大。網(wǎng)頁i的權(quán)威值Pi按照以上的思想化為公式:

        其中,Oj是網(wǎng)頁j的鏈出數(shù)目。

        互聯(lián)網(wǎng)鏈接結(jié)構(gòu)的形成都是自發(fā)和無序的,可能存在沉淀現(xiàn)象:一些網(wǎng)頁簇只鏈向簇內(nèi)的其他一些網(wǎng)頁,而不鏈向簇外的網(wǎng)頁;傳遞進來的PageRank值滯留在網(wǎng)頁簇內(nèi)部,不能傳遞出去。解決辦法是:設(shè)定瀏覽者會隨機選擇一個鏈接繼續(xù)瀏覽的概率是d,設(shè)定瀏覽者不通過鏈接,而跳到另一個隨機網(wǎng)頁的概率是1-d。所得的公式為:

        PageRank算法計算時使用冪迭代法,根據(jù)上述公式得出迭代公式為:

        其中,P為各個網(wǎng)點的PageRank值,是n行1列矩陣;E是一個全為1的n×n方陣;A是鏈接矩陣,每行和為1,即把每行做求和分解,Aij表示節(jié)點i鏈向節(jié)點j。

        由于鏈接結(jié)構(gòu)的自發(fā)和無序性,矩陣A存在“黑洞效應(yīng)”:網(wǎng)絡(luò)鏈接圖中存在入度為0的網(wǎng)頁,經(jīng)過有限次迭代后,該鏈接圖中的所有網(wǎng)頁的PageRank值均為0。解決方法:對于沒有外鏈的網(wǎng)點,設(shè)定鏈接圖中其余所有的網(wǎng)點都是它的外鏈,即在鄰接矩陣中,某行全為0,則將全部元素值設(shè)為1/N。所得公式為:

        PageRank公式即為:

        PageRank算法中使用的冪迭代法[4],計算簡單但收斂速度慢,時間消耗較大。對于這個問題一些學(xué)者提出使用MapReduce并行處理,減少時間消耗。

        2 MapReduce介紹

        MapReduce是Google提出的一個軟件架構(gòu),是一種處理海量數(shù)據(jù)的并行編程模式,用于大規(guī)模數(shù)據(jù)集 (通常大于1TB)的并行運算[5]。MapReduce分為 “Map(映射)”階段和 “Reduce(化簡)”階段。MapReduce過程:首先將輸入文件分成互相獨立的N塊,每塊分配給一個執(zhí)行Map函數(shù)的處理器,Map:(in_key,in_value)→ {(keyj,valuej)|j=1…k}}。執(zhí)行Reduce函數(shù)的處理器將每個 Map函數(shù)所產(chǎn)生的中間結(jié)果進行合并,Reduce:(key,[value1,…,valuem])→ (key,final_value)。各個執(zhí)行Reduce函數(shù)的處理器也可以并行[3]。

        3 算法改進及實現(xiàn)

        3.1 算法改進

        結(jié)合了MapReduce的PageRank算法已在一定程度上減少了時間消耗,為進一步減少時間消耗,筆者將結(jié)合了MapReduce的PageRank算法再結(jié)合Gauss-Seidel,在并行的基礎(chǔ)上減少迭代次數(shù),從而進一步減少時間消耗。

        1)Jacobi迭代法 PageRank算法使用的冪迭代法實質(zhì)是特殊的Jacobi迭代法。

        DX =b的Jacobi計算公式[6]如下:

        式中,D 為系數(shù)矩陣且非奇異,dii≠0;b= (b1,b2,…,bnT)。當(dāng)dii=1,bi=0時Jacobi迭代法即為PageR-ank算法中的冪迭代法。即PageRank算法中的冪迭代法可轉(zhuǎn)化為求方程組(P-E)X=0。

        Jacobi計算簡單但收斂速度慢,而Gauss-Seidel收斂快于Jacobi,所以下面將討論把鄰接矩陣轉(zhuǎn)化為大型稀疏矩陣線性方程組后采用MapReduce并行編程方法和Gauss-Seidel相結(jié)合,使迭代次數(shù)更低,并行效率更高。

        2)Gauss-Seidel迭代法 系數(shù)矩陣D為非奇異,且dii≠0。DX =b的Gauss-Seidel的計算公式[6]如下:

        Gauss-Seidel迭代可以看成是對Jacobi迭代的一種改進[7]。Gauss-Seidel使用最新信息計算,收斂快,減少了迭代次數(shù)。

        3.2 算法的具體實現(xiàn)

        按照MapReduce編程方法,MapReduce函數(shù)首先對矩陣進行分塊處理,將m至n列分為一塊,其中n>m。然后由Master節(jié)點將各個分塊矩陣和序號為m至n的頁面的初始權(quán)威值分派給各個Map worker節(jié)點。根據(jù)Gauss-Seidel的迭代次數(shù)少的優(yōu)點,在 Map函數(shù)中使用Gauss-Seidel迭代方法。Gauss-Seidel迭代:計算時,使用(j<i)和(j≥i)。因為Pj(k+1)中的j<i,所以只要順序循環(huán),將上輪循環(huán)所得的值Pj(k+1)(j<i)放入下輪循環(huán)中參與計算即可[7]。Map函數(shù)處理完成后,由Master節(jié)點將結(jié)果分配給Reduce worker節(jié)點。Reduce函數(shù)所得的結(jié)果即為各個Web頁面的權(quán)威值。偽代碼如下:

        4 結(jié)果與評價

        使用Matlab、分布式計算工具箱和ncm工具箱[8.9]模擬改進后的PageRank算法。分布式計算工具箱用在4核處理器計算機上模擬Hadoop平臺下的MapReduce,ncm工具箱中的Harvard500(訪問哈佛大學(xué)的網(wǎng)頁,所生成的網(wǎng)絡(luò)連接關(guān)系)作為測試改進的PageRank算法所用的數(shù)據(jù)集。Harvard500數(shù)據(jù)集包含500個節(jié)點和2636個鏈接。

        使用ncm工具箱中的所提供的500個節(jié)點。用Power Method和改進的PageRank算法:Gauss-Seidel Method,用不同迭代精度進行迭代,選取4個處理機最大的迭代次數(shù)進行比較,如表1所示。

        表1 不同精度所得迭代次數(shù)

        圖1 迭代次數(shù)比較曲線

        Power Method和Gauss-Seidel Method迭代次數(shù)比較的曲線如圖1所示。由表1和圖1可以得出:隨著計算精度的提高,Gauss-Seidel Method迭代速度快的優(yōu)勢越來越明顯。由此得出:當(dāng)Web頁面越來越龐大時,改進的PageRank算法優(yōu)勢越來越明顯,即計算各個網(wǎng)頁的權(quán)威值時間減少,效率提高。

        [1]Page L,Brin S,Motwani R,et al.The PageRank citation ranking:Bring order to the Web [N].Stanford Digital Libraries Working Paper,1998.

        [2]Amy N L,Carl D M.Deeper Inside PageRank [J].Internet Mathematic,2005,1 (3):335-380.

        [3]Liu Bing.Web數(shù)據(jù)挖掘 [M].俞勇,薛貴榮,韓定一 (譯).北京:清華大學(xué)出版社,2009.

        [4]吳家麒,譚永基.PageRank算法的優(yōu)化和改進 [J].計算機工程與應(yīng)用,2009,(16):56-58.

        [5]劉鵬 .云計算 [M].北京:電子工業(yè)出版社,2011.

        [6]李慶揚,王能超,易大義 .數(shù)值分析 [M].北京:清華大學(xué)出版社,2008.

        [7]向令,王鵬 .并行迭代算法的研究及應(yīng)用 [J].成都信息工程學(xué)院學(xué)報,2007(S):109-111.

        [8]Cleve B M.Matlab數(shù)值計算 [M].喻文健 (譯).北京:機械工業(yè)出版社,2006.

        [9]張德豐 .MATLAB數(shù)值分析與仿真案例 [M].北京:清華大學(xué)出版社,2011.

        猜你喜歡
        迭代法工具箱權(quán)威
        迭代法求解一類函數(shù)方程的再研究
        各大權(quán)威媒體聚焦流翔高鈣
        跟蹤督察:工作干得實 權(quán)威立得起
        權(quán)威發(fā)布
        電影(2017年6期)2017-06-24 11:01:26
        Matlab曲線擬合工具箱在地基沉降預(yù)測模型中的應(yīng)用
        迭代法求解約束矩陣方程AXB+CYD=E
        預(yù)條件SOR迭代法的收斂性及其應(yīng)用
        權(quán)威的影子
        小說月刊(2015年1期)2015-04-19 02:04:19
        求解PageRank問題的多步冪法修正的內(nèi)外迭代法
        搜狗分號工具箱 輸入更便捷
        日本一区二区高清在线观看| 日本xxxx色视频在线观看免费| 国产一区二区三区最新地址| 日本一区二区三区四区高清不卡| 亚洲综合日韩精品一区二区| 蜜桃视频一区二区在线观看| 99久久人妻精品免费二区| 无码国产一区二区三区四区| 婷婷综合缴情亚洲狠狠| 韩国无码精品人妻一区二| 一区二区三区在线观看人妖| 涩涩鲁精品亚洲一区二区| 中文字幕日韩精品一区二区三区| 一本一道av中文字幕无码| 免费视频一区二区| 亚洲天堂免费成人av| 久久国产精品亚洲婷婷片| 成人亚洲精品777777| 国产在视频线精品视频| 成人午夜免费无码视频在线观看| 杨幂Av一区二区三区| 天堂av一区二区麻豆| 国产激情视频在线观看大全| 亚洲色大成网站www永久| 免费人妻精品一区二区三区| 色狠狠av老熟女| 美女高潮流白浆视频在线观看| 亚洲高清国产拍精品熟女| 国产手机在线观看一区二区三区| 99久久婷婷国产综合精品电影| 国产一在线精品一区在线观看| 亚洲偷自拍另类图片二区| 日本久久精品在线播放| 精品久久一区二区三区av制服| 免费国产a国产片高清网站 | 真人无码作爱免费视频禁hnn| 先锋影音av资源我色资源| 久久国产精品免费一区二区| 丝袜美腿一区在线观看| 99久久国产精品网站| 天堂中文在线资源|