慕課推薦系統筆記
1、個性化召回算法Personal Rank背景與物理意義
1、首先介紹基於圖的個性化召回算法—personal rank的背景。
（1）用戶行為很容易表示為圖
圖這種數據結構有兩個基本的概念—頂點和邊。
在實際的個性化推薦系統中，無論是信息流場景、電商場景或者是O2O場景，用戶無論是點擊、購買、分享、評論等等的行為都是在user和item兩個頂點之間搭起了一條連接邊，構成了圖的基本要素。
實際上這裡user與item構成的圖是二分圖，後面會介紹二分圖的概念以及結合具體的例子展示如何將用戶行為轉換為圖。
（2）圖推薦在個性化推薦領域效果顯著
2、二分圖 二分圖又稱為二部圖，是圖論中的一種特殊模型。設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集（A,B），並且圖中的每條邊（i,j）所關聯的兩個頂點 i 和 j 分別屬於這兩個不同的頂點集（i in A, j in B）,則稱圖G為一個二分圖。
（如果有一種無向圖，它的定點可以分成兩個獨立的集合，並且互不相交，且所有的邊關聯頂點，都從屬於這個集合。那麼這樣的圖可以稱為二分圖。）
則，推薦系統中，user、item恰好滿足兩種獨立的集合，並且用戶行為總是從user頂點到item頂點集合，所以由推薦系統中user和item之間構成的圖就是二分圖。
接下來結合具體實例講解如何將用戶的行為轉化為二分圖。
假設某推薦系統中有4個用戶：A B C D，以及從日誌（log）中發現對如下item有過行為：
即：user A 對 item a、b、d有過行為，userB 對 item a、c有過行為，userC對 item b、e有過行為，userD 對 item c、d有過行為。
首先將user、item分成兩組不相交的集合，如下：
然後，將所有user 對 item 有過行為的進行連線，就可以得到二分圖，如下：
此時問題也就抽象出來了，對於userA 來說，item c 和item e哪個更值得推薦？
這裡共有5個item，其中userA 已經對item a、b、d有過行為，這裡行為是指信息流產品中的點擊或者電商產品中的購買等表示user對item喜歡的這種操作。
那麼personal rank恰恰是這麼一種算法，它能夠結合用戶行為構成的二分圖，對於固定用戶對item集合的重要程度給出排序，也就是說將user A 沒有對item c 和item e有過行為，但是personal rank算法可以給出item c 和item e對於user A來說，哪個更值得推薦。
下面從物理意義的角度來分析一下，從二分圖上如何分析出來item集合對user的重要程度。
3、物理意義 （1）兩個頂點之間連通的路徑數
如果要比較兩個item頂點對固定user的重要程度，只需分別看一下user到兩個item頂點的路徑數，路徑數越多的頂點越重要。
（2）兩個頂點之間連通的路徑長度
同樣路徑數的情況下，總路徑長度越短的頂點越重要。
（3）兩個頂點之間連通路徑經過頂點的出度
這裡解釋一下出度的概念：出度是指頂點對外連接邊的數目。如user A對item a、b、d有過行為，即為有條連接邊，則A的出度為3。如果前兩項都相同，則兩個item對固定user 的重要程度則比較經過頂點所有的出度和，如果出度和越小則越重要。
2、Personal Rank算法example解析
例子分析
1.分別有幾條路徑連通？
首先看A-c 之間有幾條路徑連通：分別是A-a-B-c，A-d-D-c 兩條路徑連通。
再來看A-e 之間有幾條路徑連通：A-b-C-e一條路徑
從這一角度出發，可以知道 c 比 e 重要。
2.連通路徑的長度分別是多少？
首先看A-c 之間有幾條路徑連通：分別是A-a-B-c，A-d-D-c ，長度都為3
再來看A-e 之間有幾條路徑連通：A-b-C-e長度為3
3.連通路徑的經過頂點出度分別是多少?
首先看A-a-B-c這條路徑：A出度是3，a出度是2，B出度是2，c出度是2
再看A-d-D-c這條路徑：A出度是3，d出度是2，D出度是2，c出度是2
再看A-b-C-e這條路勁：A出度是3，b出度是2，C出度是2，e出度是1
實例中這裡我們物理意義得到的結果。接下來使用程序來完成person Rank算法的時候同樣可以得到相同的結論。
雖然 e 的出度和更小，但是由於1中 c 有兩條路徑，且1的優先級更高，所以還是應該推薦 c。
3、Personal Rank算法公式解析
personal rank是可以通過用戶行為劃分二分圖為固定user得到item重要程度排序的一種算法。
1.算法的文字闡述
隨機遊走算法PersonalRank實現基於圖的推薦對用戶A進行個性化推薦，從用戶A節點開始在用戶-物品二分圖random walk，以alpha的概率從A的出邊中，等概率選擇一條遊走過去，到達該頂點後（舉例頂點a），由alpha的概率繼續從頂點a的出邊中，等概率選擇一條繼續遊走到下一個節點，或者（1-alpha）的概率回到頂點A，多次迭代。直到各頂點對於用戶A的重要度收斂。
後續我們在實現person rank算法的時候用不同的alpha值來做實驗，熟悉是Google的pageRank算法的童鞋們可以發現PageRank與person rank算法有極大的相似性。只不過PageRank算法沒有固定的起點。
2.算法的數學公式
把不同item對user的重要程度描述為PR值。
為了便於理解，同樣適用A作為固定起點。user A的PR值初始化為1，其餘節點的PR值初始化為0。
這裡使用 a 節點和 A 節點闡述公式的上半部分和公式的下半部分：
首先看公式的上部分，根據person rank的算法描述，節點a只可能是節點A與節點B,以alpha概率從他們的出邊中等概率的選擇了與節點a相互連的這條邊。
具體來看，從user A出發有3條邊，以3條邊中等概率的選擇了節點a連接的這條邊，以1/3的概率選擇連接節點a；user B以1/2的概率選擇了連接節點a。
結合闡述看一下公式的上半部分：對於不是A節點的PR值，也就是 a 的PR值，那麼首先要找到連接該頂點節點，同時分別計算他們PR值得幾分之幾貢獻到要求節點的PR值。那麼A將自己PR值得1/3貢獻給了 a ，B將自己PR值得1/2貢獻給了 a，分別求和，乘alpha，得到 a 的PR值。
接下來看下半部分：如果要求A節點本身的PR值，首先知道任意節點都會以（1-alpha）的概率回到本身，那麼對於一些本來就與A節點相連的節點，比如這裡的 a 節點或者 b 節點，它們除了以（1-alpha）的概率直接回到A以外；還可以以alpha的概率從自己的出邊中等概率的選擇與A相鄰的這條邊，比如這裡的 a 節點，可以以1/2的概率選擇回到A節點，所以就構成了下半部分的前後兩個部分。
經過分析可以發現，personal rank算法求item對固定user的PR值，需要每次迭代在全圖範圍內迭代，時間複雜度在工業界實際算法落地的時候是不能接受的，所以要讓儘可能多的user並行迭代。結合之前許多其他算法訓練的工業界實現，很容易想到矩陣化實現，下面看personal rank算法的矩陣化實現。
3.算法抽象—矩陣式
假設這裡共有m個user，n個item。
R矩陣是m+n行，1列矩陣，表示其餘頂點對該固定頂點的PR值。當然得到了這個，就得到了固定頂點下，其餘所有頂點的重要程度排序，這裡只需要排出m個user節點。只看n個item節點對該固定頂點的排序。也就得到了該固定頂點下推薦的item。
r0 是m+n行，1列的矩陣，負責選取某一節點是固定節點，它的數值只有1行唯一，其餘行全為0。唯一的行，即為選取了該行對應的頂點為固定頂點。那麼得到的就是該固定頂點下，其餘節點對該固定節點的重要程度的排序。
M 是 m+n行 * m+n列的矩陣，也就是行包含了所有的節點，列也包含了所有的節點。 它是轉移矩陣，數值定義如下：1.第一行第二列的數值距離，如果第一行對應的數值頂點由出邊連接到了第二列的頂點，那麼該值就為第一行頂點的出度的倒數；如果沒有連接邊，那麼就是0。
我們很容易聯想到，第一個式子包含了剛才所說的非矩陣化的personal rank的公式的上下兩部分。
上述公式是本部分中第一個公式，移項、合併同類項之後得到的。
該公式是上一公式兩個同時乘以轉置的之後得到的。
剛才說過，r0是m+n行，1列的矩陣，它能夠選取固定的頂點，得到固定頂點的推薦結果。如果將r0變為（m+n）*（m+n）的矩陣，也就得到了所有頂點的推薦結果。
由於得到的推薦結果是考慮頂點之間的PR值的順序關係，並非一個絕對數值，所以可以將 捨去。所以即為所有頂點的推薦結果。每一列表示該頂點下，其餘頂點對於該頂點的PR值。
但是，需要注意的是，每一個user能夠行為的item畢竟是少數，所以這裡的M矩陣是稀疏矩陣，同樣也是稀疏矩陣。
<code>#-*- coding:utf-8 -*-
from __future__ import division
import operator
import sys
sys.path.append("../utils")
from utils import read
from utils import mat_util
from scipy.sparse.linalg import gmres
import numpy as np
def personal_rank(graph,root,alpha,iter_step,recom_num=10):
'''
使用非矩陣化的方法實現personal rank算法
:param graph: 根據用戶行為得到的圖
:param root: 將要給哪一個用戶推薦
:param alpha: 遊走概率
:param iter_step: 迭代次數
:param recom_num: 推薦數目
:return: dict: key:item_id, value:pr
'''
rank={}
rank={point:0 for point in graph} #將所有頂點的PR值初始為0
rank[root]=1 #固定頂點的PR值為1
recom_result={}
for item_index in range(iter_step):
tmp_rank={} #臨時存放結果
tmp_rank={point:0 for point in graph}
for out_point,out_dict in graph.items(): #對於graph中每一個字典對
for inner_point,value in graph[out_point].items():
#每一個節點的PR值等於所有有邊指向當前節點的節點的PR值的等分
tmp_rank[inner_point]+=round(alpha*rank[out_point]/len(out_dict),4)
if inner_point==root:
tmp_rank[inner_point]+=round(1-alpha,4)
if tmp_rank==rank:
print("out")
break #提前結束迭代
rank=tmp_rank
right_num=0 #記錄實際能推薦的item數
for instance in sorted(rank.items(),key=operator.itemgetter(1),reverse=True):
point,pr_score=instance[0],instance[1]
if len(point.split('_'))<2:
continue #如果不是item，則跳過
if point in graph[root]:
continue #如果這個item用戶已經點擊過，則跳過
recom_result[point]=pr_score
right_num+=1
if right_num>recom_num: #比較實際推薦的item數是否已經達到結果要求返回的item數
break
return recom_result
def personal_rank_mat(graph,root,alpha,recom_num=10):
'''
通過矩陣化計算
:param graph:
:param root:
:param alpha:
:param recom_num:
:return: A*r=r0
'''
m,vertex,address_dict=mat_util.graph_to_matrix(graph)
if root not in address_dict:
return {}
mat_all=mat_util.mat_all_point(m,vertex,alpha) #A
score_dict={}
recom_dict={}
index=address_dict[root]
initial_list=[[0] for i in range(len(vertex))] #初始化r0矩陣 one-hot
initial_list[index]=[1]
r_zero=np.array(initial_list)
res=gmres(mat_all,r_zero,tol=1e-8)[0] #計算線性代數方程定義好誤差
for index in range(len(res)):
point=vertex[index]
if len(point.strip().split('_'))<2:
continue
if point in graph[root]:
continue
score_dict[point]=round(res[index],3)
for instance in sorted(score_dict.items(),key=operator.itemgetter(1),reverse=True)[:recom_num]:
point,score=instance[0],instance[1]
recom_dict[point]=score
return recom_dict
def get_one_user_recom():
'''
計算一個用戶的推薦item的候選集
:return:
'''
graph=read.get_graph_from_data("../data/ratings.csv")
alpha=0.6
user='1'
iter_num=100
recom_result=personal_rank(graph,user,alpha,iter_num,100)
item_info=read.get_item_info("../data/movies.csv")
for itemid in recom_result:
pure_itemid=itemid.split("_")[1]
print(item_info[pure_itemid])
print(recom_result[itemid])
return recom_result
def get_one_user_by_mat():
'''
矩陣化後測試結果
'''
user='1'
alpha=0.8
graph=read.get_graph_from_data("../data/ratings.csv")
recom_result=personal_rank_mat(graph,user,alpha,100)
return recom_result
if __name__=='__main__':
recom_result_base=get_one_user_recom()
recom_result_mat=get_one_user_by_mat()
num=0
for element in recom_result_base:
if element in recom_result_mat:
num+=1
print(num)
/<code>
