推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库

推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,第1张

推薦系統實踐--基於用戶的協同過濾算法

http://www.cnblogs.com/qwj-sysu/p/4368874.html

基於鄰域的算法推薦系統中最基本的算法,該算法不僅在學術界得到了深入研究,而且在業界得到了廣泛應用。基於鄰域的算法分為兩大類,一類是基於用戶的協同過濾算法,另一類是基於物品的協同過濾算法。

我們先來看看基於用戶的協同過濾算法,基於物品的協同過濾算法大體思路和基於用戶的差不多,可以自己參考對比學習。

基於用戶的協同過濾算法

每年新學期開始,剛進實驗室的師弟總會問師兄相似的問題,比如“我應該買什么專業書啊”、“我應該看什么論文啊”等。這個時候,師兄一般會給他們做出一些推薦。這就是現實中個性化推薦的一種例子。在這個例子中,師弟可能會請教很多師兄,然后做出最終的判斷。師弟之所以請教師兄,一方面是因為他們有社會關系,互相認識且信任對方,但更主要的原因是師兄和師弟有共同的研究領域和興趣。那么,在一個在線個性化推薦系統中,當一個用戶A需要個性化推薦時,可以先找到和他有相似興趣的其他用戶,然后把那些用戶喜歡的、而用戶A沒有聽說過的物品推薦給A。這種方法稱為基於用戶的協同過濾算法。

基於用戶的協同過濾算法主要包括兩個步驟。

(1) 找到和目標用戶興趣相似的用戶集合。

(2) 找到這個集合中的用戶喜歡的,且目標用戶沒有聽說過的物品推薦給目標用戶。

步驟(1)的關鍵就是計算兩個用戶的興趣相似度。這里,協同過濾算法主要利用行為的相似度計算興趣的相似度。給定用戶u和用戶v,令N(u)表示用戶u曾經有過正反饋的物品集合,令N(v)為用戶v曾經有過正反饋的物品集合。那么,我們可以通過如下的Jaccard公式簡單地計算u和v的興趣相似度或者通過余弦公式:

      jaccard                                                                             余項公式:

推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,第2张                         推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,第3张

 

 

這個一個行為記錄                                             我們可以根據余弦公式計算如下

推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,第4张                             推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,第5张

以余弦相似度為例,實現該相似度可以利用下面的偽代碼:

推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,復制代碼,第6张
def UserSimilarity(train):
W
= dict()
for u in train.keys():
for v in train.keys():
if u == v:
continue
W[u][v]
= len(train[u] & train[v])
W[u][v]
= /= math.sqrt(len(train[u]) * len(train[v]) * 1.0)
return W
推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,復制代碼,第6张

這種方法的時間復雜度是O(|U|*|U|),這在用戶數很大時非常耗時。事實上,很多用戶相互之間並沒有對同樣的物品產生過行為,即很多時候N(u)^ N(v) = 0。上面的算法將很多時間浪費在了計算這種用戶之間的相似度上。如果換一個思路,我們可以首先計算出N(u)^ N(v) != 0 的用戶對(u,v),然后再對這種情況除以分母sqrt(N(u)*N(v)) 。

為此,可以首先建立物品到用戶的倒排表,對於每個物品都保存對該物品產生過行為的用戶列表。令稀疏矩陣C[u][v]= N(u)^ N(v) 。那么,假設用戶u和用戶v同時屬於倒排表中K個物品對應的用戶列表,就有C[u][v]=K。從而,可以掃描倒排表中每個物品對應的用戶列表,將用戶列表中的兩兩用戶對應的C[u][v]加1,最終就可以得到所有用戶之間不為0的C[u][v]

推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,復制代碼,第6张
def UserSimilarity(train):
# build inverse table for item_users
item_users = dict()
for u, items in train.items():
for i in items.keys():
if i not in item_users:
item_users[i]
= set()
item_users[i].add(u)
#calculate co-rated items between users
C = dict()
N
= dict()
for i, users in item_users.items():
for u in users:
N[u]
= 1
for v in users:
if u == v:
continue
C[u][v]
= 1
#calculate finial similarity matrix W
W = dict()
for u, related_users in C.items():
for v, cuv in related_users.items():
W[u][v]
= cuv / math.sqrt(N[u] * N[v])
return W
推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,復制代碼,第6张

 

下面是按照想法建立的稀疏矩陣,對於物品a,將W[A][B]和W[B][A]加1,對於物品b,將W[A][C]和W[C][A]加1,以此類推,掃描完所有物品后,我們可以得到最終的W矩陣,這里的W是余弦相似度中的分子部分,然后將W除以分母可以得到最終的用戶興趣相似度

推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,第10张推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,第11张

得到用戶之間的興趣相似度后,UserCF算法會給用戶推薦和他興趣最相似的K個用戶喜歡的物品。上面右邊公式度量了UserCF算法中用戶u對物品i的感興趣程度:其中,S(u, K)包含和用戶u興趣最接近的K個用戶,N(i)是對物品i有過行為的用戶集合,Wuv是用戶u和用戶v的興趣相似度,Rvi代表用戶v對物品i的興趣,因為使用的是單一行為的隱反饋數據,所以所有的Rvi=1。

如下代碼實現了上面的UserCF推薦算法:

推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,復制代碼,第6张
def Recommend(user, train, W):
rank
= dict()
interacted_items
= train[user]
for v, wuv in sorted(W[u].items, key=itemgetter(1), reverse=True)[0:K]:
for i, rvi in train[v].items:
if i in interacted_items:
#we should filter items user interacted before
continue
rank[i]
= wuv * rvi
return rank
推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,復制代碼,第6张

選取K=3,用戶A對物品c、e沒有過行為,因此可以把這兩個物品推薦給用戶A。根據UserCF算法,用戶A對物品c、e的興趣是:
推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,第14张

用戶相似度計算的改進

如果兩個用戶都曾經買過《新華字典》,這絲毫不能說明他們興趣相似,因為絕大多數中國人小時候都買過《新華字典》。但如果兩個用戶都買過《數據挖掘導論》,那可以認為他們的興趣比較相似,因為只有研究數據挖掘的人才會買這本書。換句話說,兩個用戶對冷門物品采取過同樣的行為更能說明他們興趣的相似度。因此,John S. Breese在論文①中提出了如下公式,根據用戶行為計算用戶的興趣相似度:

推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,第15张

分子中的倒數懲罰了用戶u和用戶v共同興趣列表中熱門物品對他們相似度的影響。N(i)是對物品i有過行為的用戶集合,越熱門,N(i)越大

推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,復制代碼,第6张
def UserSimilarity(train):
# build inverse table for item_users
item_users = dict()
for u, items in train.items():
for i in items.keys():
if i not in item_users:
item_users[i]
= set()
item_users[i].add(u)
#calculate co-rated items between users
C = dict()
N
= dict()
for i, users in item_users.items():
for u in users:
N[u]
= 1
for v in users:
if u == v:
continue
C[u][v]
= 1 / math.log(1 len(users))
#calculate finial similarity matrix W
W = dict()
for u, related_users in C.items():
for v, cuv in related_users.items():
W[u][v]
= cuv / math.sqrt(N[u] * N[v])
return W
推薦系統實踐--基於用戶的協同過濾算法 -开发者知识库,復制代碼,第6张

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复