我的推荐算法之路(1):协同过滤

一、什么是协同过滤?

顾名思义,“协同过滤”就是协同大家的反馈、评价和意见一起对海量的信息进行过滤,从中筛选出目标用户可能感兴趣的信息的推荐过程。其主要分为:

  • 基于用户相似度进行推荐的协同过滤算法(\(UserCF\)
  • 基于物品相似度进行推荐的协同过滤算法(\(ItemCF\)

二、基于用户相似度进行推荐的协同过滤算法(\(UserCF\)

2.1 UserCF流程

  1. 基于历史数据,构建以用户(假设用户总数为 \(m\))为行坐标,物品(物品总数为 \(n\))为列坐标的 \(m×n\) 维的共现矩阵;

  2. 计算共现矩阵两两行向量间的相似性,构建 \(m×m\) 维的用户相似度矩阵;

  3. 若要对用户 \(K\) 进行推荐时,利用其 \(Top\) \(n\) 相似用户的已有评价对目标用户的偏好进行预测,生成最终推荐结果。

    \[R_{u,p} = \frac{\sum_{s \in S}(w_{u,s}*R_{s,p})}{\sum_{s \in S}w_{u,s}}\]

    其中,权重 \(w_{u,s}\) 是用户 \(u\) 和用户 \(s\) 的相似度, \(R_{s,p}\) 是用户 \(s\) 对物品 \(p\) 的评分。

  4. 由以上公式得到用户 \(u\) 对物品的预测得分,进行排序即可得到最终的推荐列表。

2.2 存在的缺点

  • 在互联网应用的场景下,用户数远大于物品数,而 \(UserCF\) 需要维护用户相似度矩阵以便快速找出 \(Top\) \(n\) 相似用户。该用户相似度矩阵的存储开销非常大,而且随着业务的发展,用户数的增长会导致用户相似度矩阵的存储空间以 \(n^2\) 的速度快速增长,这是在线存储系统难以承受的扩展速度。
  • 用户的历史数据向量往往非常稀疏,对于只有几次购买或点击行为的用户来说,找到相似用户的准确度是非常低的,这导致 \(UserCF\) 不适用于那些正反馈获取较困难的应用场景(如酒店预定、大件商品购买等低频应用)。

三、基于物品相似度进行推荐的协同过滤算法(ItemCF

3.1 ItemCF流程

  1. 基于历史数据,构建以用户(假设用户总数为 \(m\))为行坐标,物品(物品总数为 \(n\))为列坐标的 \(m×n\) 维的共现矩阵;

  2. 计算共现矩阵两两列向量间的相似性,构建 \(n×n\) 维的用户相似度矩阵;

  3. 获得用户历史行为数据中的正反馈物品列表;

  4. 利用物品相似度矩阵,针对目标用户历史行为中的正反馈物品,找出相似的 \(Top\) \(k\) 个物品,组成相似物品集合;

  5. 对相似物品集合中的物品,利用相似度分值进行排序,生成最终的推荐列表,物品的相似度分值计算公式如下:

    \[R_{u,p}=\sum_{h \in H} (R_{u,h}*w_{p,h})\]

    其中,\(H\) 是目标用户的正反馈物品集合,\(w_{p,h}\) 是物品 \(p\) 与物品 \(h\) 的物品相似度,\(R_{u,h}\) 是用户 \(u\) 对物品 \(h\) 的已有评分。

四、相似度计算

(1) 余弦相似度。余弦相似度衡量了用户向量 \(i\) 和用户向量 \(j\) 之间的向量夹角大小。显然,夹角越小,证明余弦相似度越大,两个用户越相似。

\[sim(\vec{i},\vec{j})=cos(\vec{i},\vec{j})=\frac{\vec{i}\cdot \vec{j}}{\mid \mid\vec{i}\mid\mid\cdot \mid \mid\vec{j}\mid\mid}\]

(2)皮尔逊相关系数。相比余弦相似度,皮尔逊相关系数通过使用用户平均分对各独立评分进行修正,减小了用户评分偏置的影响。

\[sim(i,j) = \frac{\sum_{p\in P}(R_{i,p}-\overline{R_i})(R_{j,p}-\overline{R_j})}{\sqrt{\sum_{p\in P}(R_{i,p}-\overline{R_i})^2}\sqrt{\sum_{p\in P}(R_{j,p}-\overline{R_j})^2}}\]

五、\(UserCF\)\(ItemCF\) 的应用场景

  • 一方面,由于 \(UserCF\) 基于用户相似度进行推荐,使其具备更强的社交特性,用户能够快速得知与自己兴趣相似的人最近喜欢的是什么。这样的特点使其非常适用于新闻推荐场景。因为新闻本身的兴趣点往往是分散的,相比用户对不同新闻的兴趣偏好,新闻的及时性、热点性往往是其更重要的属性,而 \(UserCF\) 正适用于发现热点,以及跟踪热点的趋势。
  • 另一方面,\(ItemCF\) 更适用于兴趣变化较为稳定的应用,比如在 \(Amazon\) 的电商场景中,用户在一个时间段内更倾向于寻找一类商品,这时利用物品相似度为其推荐相关物品是契合用户动机的。

六、存在缺点及未来展望

  • 热门的物品具有很强的头部效应,容易跟大量物品产生相似性;而尾部物品由于特征向量稀疏,很少与其他物品产生相似性,导致很少被推荐;
  • 为解决上述问题,同时增加模型的泛化能力,矩阵分解技术被提出。该方法在共现矩阵的基础上,使用更稠密的隐向量表示用户和物品,挖掘用户和物品的隐含兴趣和特征,在一定程度上弥补了协同过滤模型处理稀疏矩阵能力不足的问题。
  • 另外,协同过滤仅利用用户和物品的交互信息,无法有效地引入用户年龄、性别、商品描述、商品分类、当前时间等一系列用户特征、商品特征、上下文特征,造成了有效信息的遗漏;
  • 为解决上述问题,推荐系统逐渐发展到以逻辑回归模型为核心、能够综合不同类型特征的机器学习模型的道路上。

七、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 数据集:MovieLens 1M

import pandas as pd
import os

def readMovies(path):
movies = pd.read_table(os.path.join(path, 'movies.dat'), header=None, sep='::', engine='python')
movies.columns = ['MovieID', 'Title', 'Genres']
return movies

def readUsers(path):
""" Age: {1, 'under 18', 18: "18-24", 25: "25-34", 35: "35-44",
45: "45-49", 50: "50-55", 56: "56+",}"""
users = pd.read_table(os.path.join(path, 'users.dat'), header=None, sep='::', engine='python')
users.columns = ['UserID', 'Gender', 'Age', 'Occupation', 'Zip-code']
return users

def readRatings(path):
ratings = pd.read_table(os.path.join(path, 'ratings.dat'), header=None, sep='::', engine='python')
ratings.columns = ['UserID', 'MovieID', 'Rating', 'Timestamp']
return ratings
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# UserCF.py

from moviesData import readMovies, readUsers, readRatings
import pandas as pd
import numpy as np

def reCoMatrix(df, rows, cols): # 生成共现矩阵
print('...Generating co-occurrence matrix...')
coMatrix = np.zeros((rows, cols), dtype=np.int)
for i in range(df.shape[0]):
UserID, MovieID, Rating = df.iloc[i, [0, 1, 2]]
coMatrix[UserID-1, MovieID-1] = Rating
print('...Co-occurrence matrix generation completed!...')
return coMatrix # type: numpyArray (rows, cols)

def cosSimilarity(a, b): # 相似度计算
a_norm = np.linalg.norm(a)
b_norm = np.linalg.norm(b)
return np.dot(a, b) / (a_norm * b_norm)

def reSimilarMatrix(coMatrix, n): # 用户相似度矩阵
print('...Generating Similarity matrix...')
similarMatrix = np.ones((n, n), dtype=np.float)
for i in range(n):
for j in range(i+1, n):
similarMatrix[i, j] = cosSimilarity(coMatrix[i], coMatrix[j])
similarMatrix[j, i] = similarMatrix[i, j]
print('...Similarity matrix generation completed!...')
return similarMatrix # type: numpyArray (n, n)

def sortMatrix(similarMatrix, K, N): # 返回与第K个用户相关的Top N个相似度列表
df = pd.DataFrame(similarMatrix, index=range(similarMatrix.shape[0]), columns=range(similarMatrix.shape[0]))
df = df.iloc[:, K-1].sort_values(ascending=False)
return df[:N] # 与第K个用户最相似的排序结果

def fillScore(coMatrix, sortMatrix): # 计算用户对物品的预测打分
index = list(sortMatrix.index)
score = np.array(sortMatrix.values)[1:]
ans = coMatrix[index][1:]
results = np.sum(np.expand_dims(score, axis=1)*ans, axis=0) / np.sum(score)
return results

if __name__ == '__main__':
pd.set_option('display.max_rows', 1000, 'display.max_columns', None,
'display.float_format', lambda x:"%.2f" % x)
np.set_printoptions(threshold=np.inf)
path = r'C:\Users\QzmVc1\Desktop\MovieLens' # movies/users/ratings

df = readRatings(path)

rows = df['UserID'].max()
cols = df['MovieID'].max()
coMatrix = reCoMatrix(df, rows, cols)
similarMatrix = reSimilarMatrix(coMatrix, coMatrix.shape[0])
df = sortMatrix(similarMatrix, 100, 50)
results = fillScore(coMatrix, df)