2017年5月23日 Pagerank 算法背景、原理、矩陣化計算 2.3.1Pagerank 算法背景伴隨著全球計算機信息技術的飛速發展，通過互聯網搜尋來獲取信息給用 戶的生活帶來了巨大的便利。但是人們怎樣才能在浩瀚的信息海洋中快速搜尋 到有用的信息呢？ 1988年，Google公司的創始人、Stanford大學計算機博士 Lawrence Page和Sergey Brin合作共同研究出了 Pagerank算法[85]，通過這種算 法能對搜索引擎上的網頁的相關性和重要性進行排名，從而在信息篩選方面給 用戶提供便利。伴隨著Google公司在全世界范圍內取得巨大成功，Pagerank算 法也成為全球經典的十大數據挖掘算法及改變未來的九大算法之一。互聯網上 龐大的網頁群之間彼此鏈接存在著十分復雜的相關性，Pagerank算法正是基于 網頁的鏈接關系來進行網頁的排序，網頁的重要度高低直接決定著其排名的高 低。2.3.2Pagerank 算法原理Pagerank算法是單純依據頁面之間的復雜鏈接關系來進行重要度計算，每 個頁面的重要度指標為其Pagerank值（下文將簡稱PR值)，重要度高的頁面將 對應較高的PR值，而不太重要的網頁將對應較低的PR值。表2.1是部分國內 網站的PR值排名。通過表格可知PR值與網頁的反鏈數有關，所謂反鏈數即從 其他網頁導入本網頁的鏈接數量（在有向圖中稱為入度）。一般來講反鏈數越多 (入度越大），其PR值也越大，但通過表格統計發現騰訊網的反鏈數為1252835 個，在所有網頁中是最多的，但是其PR值僅僅排在第三位，這是因為頁面的 PR值不僅與其反鏈數有關，還與被鏈接過來網頁的重要度有關。就像在由多個 社會個體組成的社會關系網絡中衡量個體的社會影響力，不僅需要朋友越多， 而且還要朋友質量越高才代表個體的社會地位越高。所以Pagemnk算法的主要原理是：如果頁面A能夠鏈接到頁面B，那么將 認為頁面A傳遞給頁面B —個重要度值（PR值），此值的大小取決于頁面A的 重要度（PR值）以及其出鏈數，并假設任何頁面的重要度都被平均傳遞到它所 鏈接的頁面。由于網頁之間存在相互鏈接關系，這個計算過程會一直迭代下去， 最后根據頁面迭代后的平穩PR值進行排序。基于這一思想，將整個互聯網系 統抽象成一個有向圖G= (V，E)，其中將n個頁面抽象成網絡圖的節點V，用有向邊E代表頁面之間的鏈接關系。若網頁'、％、...Vk是鏈入到網頁A的頁面 節點，那么網頁A的PR值PR(A)計算公式為：式（2.4)中PR(Vi)和CCV；)為分別為頁面節點'的PR值和出度；根據 Pagerank算法原理我們可以總結出：①鏈入到頁面A的網頁數量k越大，頁面A的PR值就會越大，頁面A的重要度越大；②頁面A的鏈入頁面乂、％、...'的重要度越大，頁面A會受它們的影響變得更重要；③頁面節點\的出度越大，即CCVD越大，那么頁面節點A從頁面節點乂處 分得的PR值越少。公式（2.4)假設當用戶在瀏覽頁面\時，下一個瀏覽頁面是均勻地選擇下一個其所指向的頁面。Pagemnk算法可以用隨機沖浪模式來進行刻畫[85]，用戶 在互聯網上隨機瀏覽網頁，那么網頁的重要度和網頁被訪問的概率成正比，得 到的PR值就是網頁被訪問的概率和網頁排序的依據。如圖有6個頁面A、B、 C、D、E、F，假如初始PR值都是1，那么： 圖中頁面節點重要度排名依次是B、A、C、E、F、D，圖2.7所示的有向 圖是一種非常理想的情況，節點的重要度只能沿著有向邊進行傳遞，是否任何 有向圖經過反復迭代后會達到平穩狀態呢？顯然不會，由若干個節點組成的有 向圖中，如果存在以下3種情況，那么節點的PR值將不會收斂。①如果存在強連通圖（圖中任意節點相互可達）只有入鏈沒有出鏈，我們 稱這種情況為等級下沉（Rank sinks)如圖2.9所示，網頁節點D、E、F組成的強連通圖只有入鏈沒有出鏈，那么來自其他節點的PR值進入強連通圖后會一 直停留，無法進入節點A、B、C。最終的結果是節點D、E、F的PR值會一直 增大，直到節點A、B、C的PR值為0，那么PR值的計算將失去意義。②如果有向圖中存在節點F只有鏈入的頁面節點，并且出度為0,如圖2.10 所示，我們稱之為等級泄露（Rank leaks)，那么頁面訪問將被困在頁面節點F， 頁面節點A、B、C、D、E的PR值終將會變為0，而節點F的PR值將達到最 大，顯然這種情況也無法通過迭代獲得平穩的PR值。③有向圖中存在節點F的出度和入度都為0，我們稱之為孤立節點，如圖 2.11，那么按照公式（2.4)，節點F的PR值將會為0,但是頁面F還有被用戶 訪問的可能，顯然PR值為0不符合實際。其中PR (A)為網頁A的PR值，n為總頁面的數量，'、、...'代表能夠鏈入A的頁面，CCX)為頁面節點\的出度，d為阻尼因子，它是為了避免等級 下沉或登記泄露而設立的緩沖因子，它代表頁面沿著鏈接方向進行傳遞的概率為d，谷歌公司一般取為d=0.85，每條鏈接對應傳遞的PR值都是 考慮到孤立節點的存在，賦予每個頁面節點一個PR初始值^^。2.3.3PR值的矩陣化計算當有向圖中節點比較少時，可以通過解方程組的方式進行節點的PR值計 算，但是當節點數量比較龐大時，這種方法就顯得難以實現。Pagerank算法假 設用戶所瀏覽的網頁與過去的瀏覽歷史無關，依賴現有的瀏覽狀態，可以看作是一個馬爾可夫過程，那么對于n個頁面和鏈接關系組成的有向圖G = (V，E)，其鄰接矩陣C中元素為1的個數為有向圖的鏈接數，將矩陣C每行元素除以此 行元素的總和（行元素全為0除外）會得到一個矩陣C'，矩陣Cf每行元素之 和都為1，那么矩陣C'可以看作是馬爾科夫轉移概率矩陣。圖2.7所示的有向 圖的鄰接矩陣及轉移概率矩陣分別為：若指定一個n維向量P，向量的分量分別代表各個網頁節點的PR值，Px+1表示第（x+1)次迭代所得到的各個網頁的PR值所組成的（nxl)矩陣，用概率轉 移矩陣計算PR值的公式為：其中E為（nxl)階矩陣并且元素全為1，設S為指定的迭代收斂平穩閥值， 取各網頁節點的初始PR值P1，迭代計算當滿足|PX+1-PX|<S時，迭代結束。 所以Pagemnk算法的實現過程可以通過如圖2.12所示的算法流程圖來進行刻畫。本文采摘自“基于故障率相關的加工中心的可靠性及風險評估”，因為編輯困難導致有些函數、表格、圖片、內容無法顯示，有需要者可以在網絡中查找相關文章！本文由海天精工整理發表文章均來自網絡僅供學習參考，轉載請注明！ ? 上一篇 加工中心故障相關性分析下一篇 ? 基于故障率相關的加工中心的可靠性及風險評估主要內容及技術路線