基于用户的协同过滤算法（UserCF）原理以及代码实践

2020-11-04 本文已影响0人 HaloZhang

简介

协同过滤（collaborative filtering）是一种在推荐系统中广泛使用的技术。该技术通过分析用户或者事物之间的相似性，来预测用户可能感兴趣的内容并将此内容推荐给用户。这里的相似性可以是人口特征的相似性，也可以是历史浏览内容的相似性，还可以是个人通过一定机制给与某个事物的回应。比如，A和B是无话不谈的好朋友，并且都喜欢看电影，那么协同过滤会认为A和B的相似度很高，会将A喜欢但是B没有关注的电影推荐给B，反之亦然。

协同过滤推荐分为3种类型：

基于用户(user-based)的协同过滤(UserCF)
基于物品(item-based)的协同过滤（ItemCF算法)
基于模型(model-based)的协同过滤 (ModelCF算法)

本文主要讲述基于用户协同过滤算法的原理以及代码实现。

算法原理

UserCF算法主要是考虑用户与用户之间的相似度，给用户推荐和他兴趣相似的其他用户喜欢的物品。俗话说"物以群分，人以类聚"，人们总是倾向于跟自己志同道合的人交朋友。同理，你朋友喜欢的东西你大概率也可能会喜欢，UserCF算法正是利用了这个原理。举个例子，如果要给一个用户A推荐物品，可以先找到与A最为相似的用户B，接着获取用户B最喜欢的且用户A没有听说过的物品，并预测用户A对这些物品的评分，从中选取评分最高的若干个物品推荐给用户A。

从上述描述可以知道，UserCF算法的主要步骤如下：

找到与目标用户兴趣相似的用户集合
找到这个集合中的用户最喜欢的，且目标用户还未接触过的物品推荐给目标用户

上述是UserCF算法的基本思路，方便读者形成对UserCF算法的整体印象。也许你看了上述文字依然没有思路，没关系，且继续往下看。

首先，根据算法的步骤1，我们自然而然就会提出一个问题，那就是如何度量两个用户之间的相似度？试想一下，我们在现实生活中如何判断两个人是否兴趣相似呢？比如你喜欢打LOL，恰巧你室友也喜欢，那显然你们的共同话题会比较多，因为你们有共同的兴趣爱好。我们刚好可以利用这一点来计算用户之间的相似度。

对于用户u和用户v，令N(u)代表用户u喜欢的物品合集，令N(v)代表用户v喜欢的物品合集。N(u)∩N(v)代表的是用户u和用户v都喜欢的物品，N(u)∪N(v)代表的是用户u和用户v喜欢的物品的合集，那么可以利用以下公式来简单计算相似度:
$W\mu\nu = \frac {|N(\mu) \bigcap N(\nu)|}{|N(\mu) \bigcup N(\nu)|}$
上述公式叫做Jaccard公式，直观上理解就是，将用户u与用户v都喜欢的物品的数量除以他们喜欢物品的总和，如果u和v喜欢的物品是一模一样的，则u和v的相似度为1。

还有另外一种余弦相似度计算公式:
$W\mu\nu = \frac {|N(\mu) \bigcap N(\nu)|} {\sqrt{|N(\mu) \| N(\nu)}|}$
上述公式的分母部分代表的是u喜欢的物品的数量与v喜欢的物品的数量的乘积，而不再是他们之间的交集。

举个简单例子来表明如何计算用户u和v之间的相似度，假如用户u和用户v喜欢的游戏如下表：

用户	喜爱的游戏
u	{英雄联盟, 王者荣耀，绝地求生}
v	{英雄联盟，和平精英}

利用余弦相似度计算公式可以得到如下结果：
$W\mu\nu = \frac {|\{英雄联盟,王者荣耀,绝地求生\} \bigcap \{英雄联盟,和平精英\}|}{\sqrt{\{英雄联盟,王者荣耀,绝地求生\} || \{英雄联盟, 和平精英\}}|} = \frac {1}{\sqrt{6}}$
故，我们可以计算得到用户u和用户v之间的相似度为 $\frac {1}{\sqrt{6}}$ 。

至此，我们已经可以计算任意两个用户之间的相似度了，下一步要做的事情是建立一张用户相似度表，此表中保存了任意两个用户之间的相似度，方便后续挑选出与用户u最相似的若干个用户。

当用户相似度表建立起来了之后，UserCF算法就可以给用户推荐与他兴趣最相似的K个用户喜欢的物品了。那此时又会出现一个问题，假如我们要给用户w进行推荐，并且在用户相似度表中找到了与他最相似的K个用户，这K个用户喜欢的物品有很多，我们怎么知道要推荐哪些物品给用户w呢？此时就涉及到了用户对物品的感兴趣程度，我们当然会把用户最感兴趣的物品推荐给他。故使用以下公式来度量用户u对物品i的感兴趣程度：

$p(\mu, i) = \sum_{\nu \in S(\mu, K) \bigcap N(i)} W\mu\nu R\nu i$
乍一看感觉很复杂，其实不然。
其中 $S(\mu, K)$ 代表的是与用户 $\mu$ 最相似的K个用户，将与用户 $\mu$ 相似的用户列表按照相似度进行排序就可以得到。 $N(i)$ 代表的是对喜欢物品i的用户集合， $W\mu\nu$ 代表的是用户 $\mu$ 和用户 $\nu$ 之间的相似度，这个也可以直接从用户相似度表中得到。 $R\nu i$ 代表用户v对物品i的兴趣，因为使用的是单一行为的隐反馈数据，所以所有的 $R\nu i=1$ 。

对于与用户 $\mu$ 最相似的K个用户，我们分别计算用户 $\mu$ 与这K个用户喜欢的物品集合 $I_n, n \in \{1,2,...,N\}$ 之间的感兴趣程度，得到用户 $\mu$
对这N个物品的感兴趣程度列表，然后将其逆序排序，取前m个物品推荐给用户 $\mu$ ，至此UserCF算法结束。

算法工作流程

接下来，我们用一个简单例子演示一下UserCF的具体工作流程。
下表是我们臆造的原始数据，也称之为User-Item表，即用户-物品列表，记录了每个用户喜爱的物品，数据表格如下：

用户	喜爱的物品
A	{a,b,d}
B	{a,c,d}
C	{b,e}
D	{c,d,e}

接下来我们需要计算用户相似度矩阵，最直观的方法就是，对于用户列表{A,B,C,D},我们对其中两两用户都使用余弦相似度算法计算相似度。这种算法的时间复杂度是O(N^2)，当用户量很大的时候，计算非常耗时,在实际运用中不可取。观察一下相似度计算公式会发现，其实如果用户 $\mu$ 和用户 $\nu$ 没有共同喜欢的物品（比如表中的用户B和用户C），那么他们之间的相似度为0，也就没有必要计算了。
也就是说我们没必要对任意两个用户之间都计算相似度，我们只需要计算那些彼此之间有共同喜爱物品的用户之间的相似度，故首先可以想到建立倒排表，即Item-User表，具体如下：

物品	喜爱它的用户
a	{A,B}
b	{A,C}
c	{B,D}
d	{A,B,D}
e	{C,D}

有了这张表之后，相当于我们将原先零散的用户按照他们喜爱的物品给划分成若干个小圈子。比如用户A、B由于都喜欢物品a，所以被分到了一起。同理，用户C、D都喜欢物品e，因此也被分到了一起。
那这么做的目的是什么呢？回顾一下上面说的用户相似度计算方法，可以看到无论是哪一种方法都要先求出|N( $\mu$ )∩N( $\nu$ )|，所以我们的目的就是为了快速地求出任意用户之间的交集。
由此可以建立下面的用户喜爱物品交集矩阵W：

	A	B	C	D
A	0	2	1	1
B	2	0	0	2
C	1	0	0	1
D	1	2	1	0

其中W[u][v]代表的含义是用户u和用户v都喜爱的物品个数，即|N( $\mu$ )∩N( $\nu$ )|。比如用户A、C都喜欢物品b，所以W[A][C]=1。用户A、B除了喜欢物品a以外，还共同喜欢物品d，因此W[A][B]=2。
由于用户A、B之间的交集和用户B、A之间的交集是一样的，所以此矩阵是一个对称矩阵。
其实这里的W就是相似度计算公式中的分子部分，而每个用户的喜爱列表从之前的User-Item列表中就已经可以得到了，因此我们就可以计算出用户相似度矩阵了，结果如下：

	A	B	C	D
A	0	0.67	0.41	0.33
B	0.67	0	0	0.67
C	0.41	0	0	0.41
D	0.33	0.67	0.41	0

当用户相似度矩阵建立好了之后，我们就可以对用户进行物品推荐了。
比如要对用户C进行物品推荐，通过查表可以知道（上表第四行），用户A和用户D是比较相似的两个用户。
再通过User-Item表查询到用户A喜欢的物品列表{a,b,d}，用户D喜欢的物品列表{c,d,e}，故用户A、D喜欢物品的交集是{a,b,c,d,e}，其中用户C喜欢的列表是{b,e}，为了避免重复推荐用户已经喜欢的物品，所以要先从物品列表中去掉用户C已经喜欢的物品，故最终待推荐的物品列表为{a,c,d}。
此时我们来计算用户C对待推荐物品列表中物品的感兴趣程度：

p(C,a) = W[C][A] = 0.41
p(C,c) = W[C][D] = 0.41
p(C,d) = W[C][A] + W[C][D] = 0.82

接着按照用户C对待推荐物品感兴趣程度对待推荐列表进行逆序排序，得到最终的推荐列表{d,a,c}，我们可以将整个推荐列表或者取前K个物品推荐给用户C。
至此，UserCF算法整体流程结束。
可以看到，算法的输出的最应该推荐给用户C的物品是d，我们不难发现这是因为与用户C最相似的用户A和用户D都喜欢物品d，因此将d推荐给C是比较合理的选择。

相似度算法改进

上述算法使用的是余弦相似度计算公式，但是这个公式过于粗糙，原因是余弦相似度只是简单地计算了用户u和用户v共同喜欢的物品在他们总共喜欢物品中占据的比例。
比如，两个用户都购买了时下热门物品，这并不能说明他们兴趣相似，因为热门物品是绝大多数人都会买的东西。换句话说，两个用户对冷门物品采用过相同的行为更能说明他们兴趣的相似度。因此John.S.Breese提出了以下相似度计算公式：
$W\mu\nu = \frac {\sum_{i \in N(\mu) \bigcap N(\nu) } \frac {1} {log(1+|N(i)|)} }{\sqrt{|N(\mu) \| N(\nu)}|}$
相比余弦相似度公式，这里的分子 $\frac {1} {log(1+|N(i)|)}$ 惩罚了用户u和用户v共同喜欢的热门物品对他们相似度的影响。
在下一节的代码实践中，分别实现了基于这两种相似度计算的UserCF算法。

代码实践

上一节是基于一个非常简易的测试数据集，接下来我们将UserCF算法运用在推荐系统经典数据集MovieLens上。
MovieLens数据集介绍以及数据处理参见链接。

根据之前的介绍，可知整个算法流程分为两个阶段：

训练阶段
推荐阶段

对于训练阶段，可分为以下几步：

数据预处理，建立User-Item表
建立Item-User倒排表
建立用户物品交集矩阵
建立用户相似度矩阵

对于推荐阶段，可分为以下几步：

寻找与被推荐用户最相似的K个用户
计算用户对物品的感兴趣列表并逆序排列

训练阶段

数据预处理，建立User-Item表

我们采用MovieLens数据集中的ratings.dat文件，因为这里面包含了用户对电影的评分数据，注意我们忽略掉评分那一栏，将其简化成用户喜欢或者不喜欢。只要用户有参与过评分的电影，无论分值如何，我们都认为这部电影是用户喜欢的。

注意，ratings.dat里面包含了100多万条评价数据，为了减少训练时间，可以只读取部分数据，本文读取了前29415条数据，即前200个用户的评价数据。ratings.dat原始数据每行包含了4列，本文中只取了’UserID‘、’MovieID‘这两列，关于此数据集的详细介绍请参见链接。

接下来使用以下代码来读取数据并建立User-Item表：

import random
import pandas as pd

def LoadMovieLensData(filepath, train_rate):
    ratings = pd.read_table(filepath, sep="::", header=None, names=["UserID", "MovieID", "Rating", "TimeStamp"],\
                            engine='python')
    ratings = ratings[['UserID','MovieID']]
    train = []
    test = []
    random.seed(3)
    for idx, row in ratings.iterrows():
        user = int(row['UserID'])
        item = int(row['MovieID'])
        if random.random() < train_rate:
            train.append([user, item])
        else:
            test.append([user, item])
    return PreProcessData(train), PreProcessData(test)

def PreProcessData(originData):
    """
    建立User-Item表，结构如下：
        {"User1": {MovieID1, MoveID2, MoveID3,...}
         "User2": {MovieID12, MoveID5, MoveID8,...}
         ...
        }
    """
    trainData = dict()
    for user, item in originData:
        trainData.setdefault(user, set())
        trainData[user].add(item)
    return trainData

建立Item-User倒排表

这里使用了python的dict里面嵌套set来实现倒排表，伪代码如下：

def UserItemTable(userItemTab):
    """
    建立User-Item倒排表
    :param userItemTab: user-item表
    :return:
    """
    item_user = dict()
    for user, items in userItemTab.items():
        for item in items:
            item_user.setdefault(item, set())
            item_user[item].add(user)

建立用户物品交集矩阵

同理，保存用户物品交集的矩阵采用了双重dict来实现。

def UserInterSection(item_user):
    """
    建立用户物品交集矩阵W, 其中C[u][v]代表的含义是用户u和用户v之间共同喜欢的物品数
    :param item_user: item_user 倒排表
    """
    userInterSection = dict()
    for item, users in item_user.items():
        for u in users:
            for v in users:
                if u == v:
                    continue
                userInterSection.setdefault(u, defaultdict(int))
                userInterSection[u][v] += 1  # 将用户u和用户v共同喜欢的物品数量加一

建立用户相似度矩阵

用户相似度矩阵只需要在用户物品交集矩阵的基础上除以用户u和用户v各自喜爱物品列表数量的乘积。

def UserSimMatrix(userItemTab, userInterSection):
    """
    建立用户相似度矩阵
    :param userItemTab: User-Item表
    :param userInterSection: 用户物品交集矩阵
    :return: 
    """
    userSimMatrix = dict() #用户相似度矩阵
    for u, related_user in userInterSection.items():
        for v, cuv in related_user.items():
            nu = len(userItemTab[u])
            nv = len(userItemTab[v])
            userSimMatrix[u][v] = cuv / math.sqrt(nu * nv)

完整代码

下面的代码实现了完整的功能，修改“ratings.dat"文件的路径之后，可以直接运行。


import math
import random
import pandas as pd
from Utils import modelsave
from collections import defaultdict
from operator import itemgetter

def LoadMovieLensData(filepath, train_rate):
    ratings = pd.read_table(filepath, sep="::", header=None, names=["UserID", "MovieID", "Rating", "TimeStamp"],\
                            engine='python')
    ratings = ratings[['UserID','MovieID']]

    train = []
    test = []
    random.seed(3)
    for idx, row in ratings.iterrows():
        user = int(row['UserID'])
        item = int(row['MovieID'])
        if random.random() < train_rate:
            train.append([user, item])
        else:
            test.append([user, item])
    return PreProcessData(train), PreProcessData(test)

def PreProcessData(originData):
    """
    建立User-Item表，结构如下：
        {"User1": {MovieID1, MoveID2, MoveID3,...}
         "User2": {MovieID12, MoveID5, MoveID8,...}
         ...
        }
    """
    trainData = dict()
    for user, item in originData:
        trainData.setdefault(user, set())
        trainData[user].add(item)
    return trainData

class UserCF(object):
    """ User based Collaborative Filtering Algorithm Implementation"""
    def __init__(self, trainData, similarity="cosine"):
        self._trainData = trainData
        self._similarity = similarity
        self._userSimMatrix = dict() # 用户相似度矩阵

    def similarity(self):
        # 建立User-Item倒排表
        item_user = dict()
        for user, items in self._trainData.items():
            for item in items:
                item_user.setdefault(item, set())
                item_user[item].add(user)

        # 建立用户物品交集矩阵W, 其中C[u][v]代表的含义是用户u和用户v之间共同喜欢的物品数
        for item, users in item_user.items():
            for u in users:
                for v in users:
                    if u == v:
                        continue
                    self._userSimMatrix.setdefault(u, defaultdict(int))
                    if self._similarity == "cosine":
                        self._userSimMatrix[u][v] += 1 #将用户u和用户v共同喜欢的物品数量加一
                    elif self._similarity == "iif":
                        self._userSimMatrix[u][v] += 1. / math.log(1 + len(users))

        # 建立用户相似度矩阵
        for u, related_user in self._userSimMatrix.items():
            # 相似度公式为 |N[u]∩N[v]|/sqrt(N[u]||N[v])
            for v, cuv in related_user.items():
                nu = len(self._trainData[u])
                nv = len(self._trainData[v])
                self._userSimMatrix[u][v] = cuv / math.sqrt(nu * nv)

    def recommend(self, user, N, K):
        """
        用户u对物品i的感兴趣程度：
            p(u,i) = ∑WuvRvi
            其中Wuv代表的是u和v之间的相似度， Rvi代表的是用户v对物品i的感兴趣程度，因为采用单一行为的隐反馈数据，所以Rvi=1。
            所以这个表达式的含义是，要计算用户u对物品i的感兴趣程度，则要找到与用户u最相似的K个用户，对于这k个用户喜欢的物品且用户u
            没有反馈的物品，都累加用户u与用户v之间的相似度。
        :param user: 被推荐的用户user
        :param N: 推荐的商品个数
        :param K: 查找的最相似的用户个数
        :return: 按照user对推荐物品的感兴趣程度排序的N个商品
        """
        recommends = dict()
        # 先获取user具有正反馈的item数组
        related_items = self._trainData[user]
        # 将其他用户与user按照相似度逆序排序之后取前K个
        for v, sim in sorted(self._userSimMatrix[user].items(), key=itemgetter(1), reverse=True)[:K]:
            # 从与user相似的用户的喜爱列表中寻找可能的物品进行推荐
            for item in self._trainData[v]:
                # 如果与user相似的用户喜爱的物品与user喜欢的物品重复了，直接跳过
                if item in related_items:
                    continue
                recommends.setdefault(item, 0.)
                recommends[item] += sim
        # 根据被推荐物品的相似度逆序排列，然后推荐前N个物品给到用户
        return dict(sorted(recommends.items(), key=itemgetter(1), reverse=True)[:N])

    def train(self):
        self.similarity()


if __name__ == "__main__":
    train, test = LoadMovieLensData("../Data/ml-1m/ratings.dat", 0.8)
    print("train data size: %d, test data size: %d" % (len(train), len(test)))
    UserCF = UserCF(train)
    UserCF.train()

    # 分别对测试集中的前4个用户进行电影推荐
    print(UserCF.recommend(list(test.keys())[0], 5, 80))
    print(UserCF.recommend(list(test.keys())[1], 5, 80))
    print(UserCF.recommend(list(test.keys())[2], 5, 80))
    print(UserCF.recommend(list(test.keys())[3], 5, 80))

上述代码对测试集中前4个用户进行了电影推荐，对每个用户而言，从与他们相似的80个用户喜欢的电影中挑选出5部推荐。输出结果是一个dict，里面包含了给用户推荐的电影以及用户对每部电影的感兴趣程度，按照逆序排列。

运行结果如下：