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

发表于 更新于 分类于 阅读次数： 本文字数： 5.1k 阅读时长 ≈ 5 分钟

一、什么是协同过滤？

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

  • 基于用户相似度进行推荐的协同过滤算法（$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)