搜索策略產品經理必讀系列—第五講Page Rank算法

0 評論 3771 瀏覽 22 收藏 8 分鐘

搜索引擎中最早網頁搜索結果排序效果比較優的算法就是Google創始人提出的Page Rank算法,作為搜索領域的從業者必須要了解該經典算法的思想。本文結合實際案例一篇講懂Page Rank算法的基本思想,同時還為大家介紹后續優化后的Page Rank算法。

一、基本假設

在正式介紹Page Rank算法前我們先通過實際生活中的一個案例入手。日常我們寫論文時經常會引用別人的論文,某個行業里的經典論文會被大量的論文所引用。如果該論文恰好還被另外一篇經典論文所引用的話,則更加能夠凸顯出該篇論文的重要性和權威性,其實網頁的重要性和權威性也是如此。

于是我們設定以下兩大假設。

數量假設:當一個網頁被其他網頁鏈接的數量越多,入鏈數越大,則該網頁越重要。

如上圖所示,網站“WWW1”被眾多網站引用,形成了鏈接,則說明網站“WWW1”很重要。

  • 質量假設:被高質量的網頁鏈接時,說明被鏈接的網頁質量也很高,權威性也很強。

如上圖所示,網站“WWW8”被高質量網站“WWW1”引用,形成了鏈接,說明網站“WWW8”同樣也很權威。PageRank算法的整體思想都是建立在上述假設上的。

二、Page Rank基本算法

基于以上兩大假設,我們展開介紹Page Rank算法。首先我們將互聯網想象為一個圖網絡,網絡的每一個節點(Node)就是一個個獨立的網頁,如果兩個網頁之間存在超鏈接的關系,則它們兩個之間存在一條有方向的邊(Edge),每個節點向外鏈接的節點數被稱為該節點的出度。

每個節點的Page Rank值(以下簡稱PR值)表示該節點的權威性。我們核心是構建一個用戶在圖網絡中的游走模型,基于游走模型來進行PR值的更新迭代。

上面即為Page Rank算法的基本定義,首先節點 ν_1 的PR值是由鏈接到該節點的其他節點PR值決定的,假設鏈接節點是 ν_2、ν_3 。鏈接的其他節點越多則該節點的PR值越大,所以算法迭代使用累加 ∑ 。需要將節點 ν_2、ν_3 的PR值進行累加,此迭代思路對應著上述的“數量假設”。

鏈接的其他節點PR值越大,則該節點的PR值也越大,對應著上述的“質量假設”。同時 ν_2、ν_3 節點還鏈接其他節點,用戶通過節點 ν_2、ν_3 跳轉到節點 ν_1 的概率為 1/O(ν_j ) , O(ν_j ) 為節點 ν_j 的出度。節點 ν_2、ν_3 的PR值分別乘以 1/O(ν_2 )和1/O(ν_3 ) ,再進行累加即為節點 ν_1 的PR值。我們通過該方式不斷迭代更新節點的PR值,直到最終整個網絡里所有節點的PR值滿足收斂條件。

三、具體案例

下面我們通過一個例子來詳細介紹Page Rank算法的迭代過程。

初始時4個節點的PR值均為1/4。經過第一次迭代,我們得到了 R_1 =[3/8,5/24,5/24,5/24]^T 。我們可以將上述計算過程變成一個矩陣計算,通過矩陣化的表達,可以快速的計算得到PR值。

首先我們基于各個節點的出度構建一個轉移概率矩陣 M ,節點A的出度為3,鏈接了B、C、D三個節點,我們認為節點A轉移到B、C、D節點的概率均為1/3,以此類推我們可以得到一個轉移概率矩陣 M 。那么PR的迭代公式就變為: M*R_t=R_(t+1) 。

如上所示 M*R_1=R_2 ,和我們最上方計算的結果完全一致。但是上述Page Rank基本算法應用時會存在以下兩大問題:

問題一:很多網站并沒有和其他網站建立任何的鏈接,出度為0。這類網站的出現會導致按照上述算法進行 R_i 迭代,最終所有節點的PR值歸于零。

問題二:用戶打開某一個網站后,即使該網站鏈接了其他網站,但是用戶還是可能會隨機打開其他網站,所以沒有鏈接的其他網站轉移概率不應該是0,系統可以設置一個隨機概率。

四、Page Rank優化算法

基于Page Rank基本算法存在的兩大問題上,科學家們又對Page Rank算法進行了優化,優化后的Page Rank算法可以適用于所有的網絡結構,更加貼近于實際用戶瀏覽行為。優化后的算法PR值更新迭代如下:

R_(t+1)=d*M*R_t+(1-d)*E/N

全新迭代公式的業務理解是:用戶在瀏覽網頁時有兩種情況,第一種情況是以概率 d(0≤d≤1) 完全按照原本的轉移概率矩陣進行游走,第二種情況是以概率(1- d )隨機訪問任何其他的節點,每個節點的鏈接概率都是1/N, E 是元素1填滿的N*N矩陣。

d 又被成為阻尼因子, d 的取值一般由經驗決定,正常在0.8-0.9之間。當 d 接近1時,用戶隨機游走主要依照轉移概率矩陣 M 進行;當 d 接近0時,用戶隨機游走主要以等概率隨機訪問各個結點。

雖然目前搜索引擎的排序算法已經優化迭代了很多版本,但是Page Rank算法的核心思想仍然在被使用,也應用到了其他領域。Page Rank是從事搜索領域人士必須要了解的算法之一。

本文由 @King James 原創發布于人人都是產品經理。未經許可,禁止轉載。

題圖來自 Unsplash,基于 CC0 協議

該文觀點僅代表作者本人,人人都是產品經理平臺僅提供信息存儲空間服務。

更多精彩內容,請關注人人都是產品經理微信公眾號或下載App
評論
評論請登錄
  1. 目前還沒評論,等你發揮!