轉：

個人感覺：這篇文章最重要的地方在於實現了基於主題敏感的隨機遊走。這種隨機遊走要比傳統的隨機遊走在推薦演算法裏效果很好。我感覺，這東西可以使用在deepwalk演算法中，修改它原始的隨機遊走過程，再添加點其他的東西，就可以發出一篇很好的論文了。

今天我們講一個下怎麼使用隨機遊走演算法PersonalRank實現基於圖的推薦。

在推薦系統中，用戶行為數據可以表示成圖的形式，具體來說是二部圖。用戶的行為數據集由一個個（u,i）二元組組成，表示為用戶u對物品i產生過行為。本文中我們認為用戶對他產生過行為的物品的興趣度是一樣的，也就是我們只考慮「感興趣」OR「不感興趣」。假設有下圖所示的行為數據集。

其中users集U={A, B, C}，items集I = {a,b,c,d}。則用戶物品的二部圖如下所示：

我們用G(V, E)來表示這個圖，則頂點集V=U∪I，圖中的邊則是由數據集中的二元組確定。二元組（u, i）表示u對i有過行為，則在圖中表現為有邊相連，即e(u,i)。【注意】，本文中我們不考慮各邊的權重（即u對i的興趣度），權重都默認為1。感興趣即有邊相連，不感興趣則沒有邊相連。

那有了二部圖之後我們要對u進行推薦物品，就轉化為計算用戶頂點u和與所有物品頂點之間的相關性，然後取與用戶沒有直接邊相連的物品，按照相關性的高低生成推薦列表。說白了，這是一個圖上的排名問題，我們最容易想到的就是Google的pageRank演算法。PageRank是Larry Page 和 Sergey Brin設計的用來衡量特定網頁相對於搜索引擎中其他網頁的重要性的演算法，其計算結果作為google搜索結果中網頁排名的重要指標。網頁之間通過超鏈接相互連接，互聯網上不計其數的網頁就構成了一張超大的圖。PageRank假設用戶從所有網頁中隨機選擇一個網頁進行瀏覽，然後通過超鏈接在網頁直接不斷跳轉。到達每個網頁後，用戶有兩種選擇：到此結束或者繼續選擇一個鏈接瀏覽。演算法令用戶繼續瀏覽的概率為d，用戶以相等的概率在當前頁面的所有超鏈接中隨機選擇一個繼續瀏覽。這是一個隨機遊走的過程。當經過很多次這樣的遊走之後，每個網頁被訪問用戶訪問到的概率就會收斂到一個穩定值。這個概率就是網頁的重要性指標，被用於網頁排名。演算法迭代關係式如下所示：上式中PR(i)是網頁i的訪問概率（也就是重要度），d是用戶繼續訪問網頁的概率，N是網頁總數。in(i)表示指向網頁i的網頁集合，out(j)表示網頁j指向的網頁集合。

用user節點和item節點替換上面的網頁節點就可以計算出每個user，每個item在全局的重要性，給出全局的排名，顯然這並不是我們想要的，我們需要計算的是物品節點相對於某一個用戶節點u的相關性。怎麼做呢？Standford的Haveliwala於2002年在他《Topic-sensitive pagerank》一文中提出了PersonalRank演算法，該演算法能夠為用戶個性化的對所有物品進行排序。它的迭代公式如下：

我們發現PersonalRank跟PageRank的區別只是用替換了1/N，也就是說從不同點開始的概率不同。u表示我們推薦的目標用戶，這樣使用上式計算的就是所有頂點相對於頂點u的相關度。與PageRank隨機選擇一個點開始遊走（也就是說從每個點開始的概率都是相同的）不同，如果我們要計算所有節點相對於用戶u的相關度，則PersonalRank從用戶u對應的節點開始遊走，每到一個節點都以1-d的概率停止遊走並從u重新開始，或者以d的概率繼續遊走，從當前節點指向的節點中按照均勻分佈隨機選擇一個節點往下遊走。這樣經過很多輪遊走之後，每個頂點被訪問到的概率也會收斂趨於穩定，這個時候我們就可以用概率來進行排名了。

在執行演算法之前，我們需要初始化每個節點的初始概率值。如果我們對用戶u進行推薦，則令u對應的節點的初始訪問概率為1，其他節點的初始訪問概率為0，然後再使用迭代公式計算。而對於pageRank來說，由於每個節點的初始訪問概率相同，所以所有節點的初始訪問概率都是1/N （N是節點總數）。
推薦閱讀：