elasticsearch演算法之推薦系統的相似度演算法(一)
- 2022 年 1 月 27 日
- 筆記
- Elastic search
一、推薦系統簡介
推薦系統主要基於對用戶歷史的行為數據分析處理，尋找得到用戶可能感興趣的內容，從而實現主動向用戶推薦其可能感興趣的內容；
從物品的長尾理論來看，推薦系統通過發掘用戶的行為，找到用戶的個性化需求，從而將長尾商品準確地推薦給需要它的用戶，幫助用戶發現那些他們感興趣但很難發現的商品。
推薦系統使用的是基於鄰域的演算法，一類是基於用戶的協同過濾演算法，另一類是基於物品的協同過濾演算法；
二、數據集準備
我們採用GroupLens提供的MovieLens數據集
These files contain 1,000,209 anonymous ratings of approximately 3,900 movies
made by 6,040 MovieLens users who joined MovieLens in 2000.
使用一下code載入評分文件ml-1m/ratings.dat
def get_ratings():
ratings = pd.read_csv('ml-1m/ratings.dat',
sep='::',
names=['UserID', 'MovieID', 'Rating', 'Timestamp'],
nrows=100000
)
return ratings
我們可以查看前五行的數據情況
rating = get_ratings()
print(rating.head())
UserID MovieID Rating Timestamp
0 1 1193 5 978300760
1 1 661 3 978302109
2 1 914 3 978301968
3 1 3408 4 978300275
4 1 2355 5 978824291
了解一下用戶感興趣的電影數量
rating = get_ratings()
plt.hist(rating['UserID'], bins=100, edgecolor='black')
plt.show()
三、基於用戶的協同過濾演算法
基於用戶的協同過濾演算法是推薦系統中最古老的演算法，該演算法首先需要找到跟當前用戶興趣相似的用戶，然後將找到的用戶感興趣卻不在當前用戶興趣列表的物品推薦給當前用戶；
基於用戶的協同過濾演算法主要分為兩步
- 找到和當前用戶興趣相似的用戶集合；
該演算法基於用戶對物品的歷史的正回饋行為計算用戶興趣相似度；我們給定用戶u、v，令N(u)表示用戶u曾經有過正回饋的物品集合，N(v)表示用戶v曾經有過正回饋的物品集合；我們可以通過餘弦相似度來計算用戶u和v的相似度:
w_{uv} = \frac{N(u) \cap N(v)}{\sqrt {N(u) \cup N(v)}}
例如用戶U對a、b、c有過正回饋記錄，用戶V對a、c有過正回饋記錄；
U a b c
V a c
我們利用餘弦相似度可以計算U和V的興趣相似度
\[w_{UV}=\frac{|\{a,b,c\} \cap \{a,c\}|}{\sqrt {|\{a,b,c\}| |\{a,c\}|}} = \frac{2}{\sqrt{6}}
\]
\]
我們使用如下的user_similarity來計算用戶相似性
def user_similarity(ratings):
matrix = []
rating_groups = ratings.groupby('UserID')
for u_id, u_ratings in rating_groups:
row = []
matrix.append(row)
u_movieIds = u_ratings['MovieID'].values
for v_id, v_ratings in rating_groups:
v_movieIds = v_ratings['MovieID'].values
u_v_movieIds = np.intersect1d(u_movieIds, v_movieIds)
similarity = len(u_v_movieIds)/math.sqrt(len(u_movieIds) * len(v_movieIds))
row.append(similarity)
result = pd.DataFrame(matrix, columns= rating_groups.groups.keys(), index=rating_groups.groups.keys())
return result
rating = get_ratings()
similarity_matrix = user_similarity(rating)
print(similarity_matrix.head(10))
1 2 3 ... 667 668 669
1 1.000000 0.084657 0.115406 ... 0.010504 0.068680 0.076194
2 0.084657 1.000000 0.147945 ... 0.087529 0.161416 0.048839
3 0.115406 0.147945 1.000000 ... 0.085666 0.070014 0.077674
4 0.119898 0.153704 0.152783 ... 0.083438 0.036370 0.000000
5 0.097618 0.125142 0.059708 ... 0.119562 0.142134 0.059131
6 0.163017 0.114939 0.099710 ... 0.063529 0.000000 0.032915
7 0.049341 0.284641 0.150899 ... 0.164817 0.179605 0.099627
8 0.116508 0.201633 0.083139 ... 0.090808 0.113092 0.023525
9 0.200125 0.162482 0.122407 ... 0.118842 0.178069 0.053877
10 0.240081 0.215441 0.216773 ... 0.126021 0.083229 0.096951
[10 rows x 669 columns]
在以上程式碼中直接遍歷所有的用戶進行計算相似性，很多時候由於物品的數量比較多或者每個用戶的興趣關注點比較少，這會導致大量用戶並不存在所謂的並集；我們可以先將數據結構反轉為產品用戶，然後計算不同用戶感興趣的產品總數和相關用戶之間感興趣的產品交集，最後再進行餘弦相似性計算；
import math
import numpy as np
import pandas as pd
def change_user_ratings(rating):
grouped = rating.groupby('MovieID')
result = {}
for movieId,m_rating in grouped:
result[movieId] = m_rating['UserID'].values
df = pd.DataFrame({
'MovieID': result.keys(),
'UserIDs': result.values()
})
return df.set_index(df.columns.values[0])
def cal_count(product_users):
user_counts = {}
rel_user_counts = {}
for movieId, row in product_users.iterrows():
userIds = row['UserIDs']
for uid in userIds:
if uid not in user_counts:
user_counts[uid] = 0
user_counts[uid] += 1
for vid in userIds:
if (uid, vid) not in rel_user_counts:
rel_user_counts[(uid, vid)] = 0
rel_user_counts[(uid, vid)] += 1
user_counts = pd.DataFrame({'UserID': user_counts.keys(), 'Movie_Count': user_counts.values()})
rel_user_counts = pd.DataFrame({'Rel_UserID':rel_user_counts.keys(), 'Movie_Count':rel_user_counts.values()})
return user_counts.set_index(user_counts.columns.values[0]), rel_user_counts.set_index(rel_user_counts.columns.values[0])
def cosin_similarity(user_counts, rel_user_counts):
result = []
for u, u_row in user_counts.iterrows():
row = []
result.append(row)
u_count = u_row['Movie_Count']
for v, v_row in user_counts.iterrows():
v_count = v_row['Movie_Count']
if rel_user_counts.index.isin([(u,v)]).any():
count = rel_user_counts.at[(u,v), 'Movie_Count']
row.append(count/math.sqrt(u_count * v_count))
else:
row.append(0)
return pd.DataFrame(result, index=user_counts.index.values, columns=user_counts.index.values)
def user_similarity(ratings):
rating_users = change_user_ratings(ratings)
user_counts, rel_user_counts = cal_count(rating_users)
s = cosin_similarity(user_counts, rel_user_counts)
return s
ratings = get_ratings()
similarity_matrix = user_similarity(ratings)
print(similarity_matrix.head(10))
1 2 3 ... 667 668 669
1 1.000000 0.084657 0.115406 ... 0.010504 0.068680 0.076194
2 0.084657 1.000000 0.147945 ... 0.087529 0.161416 0.048839
3 0.115406 0.147945 1.000000 ... 0.085666 0.070014 0.077674
4 0.119898 0.153704 0.152783 ... 0.083438 0.036370 0.000000
5 0.097618 0.125142 0.059708 ... 0.119562 0.142134 0.059131
6 0.163017 0.114939 0.099710 ... 0.063529 0.000000 0.032915
7 0.049341 0.284641 0.150899 ... 0.164817 0.179605 0.099627
8 0.116508 0.201633 0.083139 ... 0.090808 0.113092 0.023525
9 0.200125 0.162482 0.122407 ... 0.118842 0.178069 0.053877
10 0.240081 0.215441 0.216773 ... 0.126021 0.083229 0.096951
[10 rows x 669 columns]
- 找到這個用戶集合感興趣的且當前用戶沒有聽說過的物品推推薦給他；
通過以上計算我們得到了用戶相似性的矩陣，接下來我們需要找到跟目標用戶興趣最相似的K個用戶，然後將只有這K個用戶喜歡的物品推薦給目標用戶；這裡我們需要進一步度量目標用戶對特定產品的感興趣程度
在這個公式中，S(u,K)包含和用戶u興趣最接近的K個用戶，N(i)是對物品i有過行為的用戶集合，Wuv 是用戶u和用戶v的興趣相似度，rvi 代表用戶v對物品i的興趣，因為使用的是單一行為的隱回饋數據，所以所有的rvi=1。
\[p(u,i) = \sum_{v \in s(u,K) \cap N(i)} w_{uv} r_{vi}
\]
\]
我們使用以下的recommend方法實現這個推薦
def recommend(ratings,u, matrix, k):
result = pd.Series(dtype='float64');
grouped = dict(list(ratings.groupby('UserID')))
u_ratings = grouped[u][['MovieID','Rating']]
row = matrix.loc[u].sort_values(ascending=False)
for v in row.index:
if u != v:
similarity = row.loc[v]
v_ratings = grouped[v][['MovieID','Rating']]
diff = pd.concat([v_ratings, u_ratings, u_ratings]).drop_duplicates(subset=pd.Index(['MovieID']), keep=False)
for movieId, s_rating in diff.set_index('MovieID').iterrows():
like = similarity * (s_rating['Rating']/5)
s_movieId = str(movieId)
if movieId in result:
result[s_movieId] += like
else:
result[s_movieId] = like
return result.sort_values(ascending=False).head(k)
我們計算推薦給用戶A且其最感興趣的前三件商品；從計算結果可以看到是商品c和e；
ratings = get_ratings()
similarity_matrix = user_similarity(ratings)
recommend_movies = recommend(ratings, 1, similarity_matrix, 10)
print(recommend_movies.head(10))
2049 0.240081
3292 0.212965
1067 0.204131
2559 0.193922
3620 0.168068
963 0.168068
2179 0.165928
2211 0.165928
1817 0.165928
2227 0.165928
dtype: float64
註：由於rating.data的數據實際情況，每個用戶以及每個電影都會有對應的評分，所以第二種演算法並不具有什麼性能優勢，需要根據自己數據的實際情況進行選擇；
