协同过滤（collaborative filtering）是一种在推荐系统中广泛使用的技术。该技术通过分析用户或者事物之间的相似性，来预测用户可能感兴趣的内容并将此内容推荐给用户。

这里的相似性可以是人口特征的相似性，也可以是历史浏览内容的相似性，还可以是个人通过一定机制给与某个事物的回应。比如，A和B是无话不谈的好朋友，并且都喜欢看电影，那么协同过滤会认为A和B的相似度很高，会将A喜欢但是B没有关注的电影推荐给B，反之亦然。

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

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

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

技术提升

技术要学会分享、交流，不建议闭门造车。一个人走的很快、一堆人可以走的更远。

文章中的完整源码、资料、数据、技术交流提升， 均可加知识星球交流群获取，群友已超过2000人，添加时切记的备注方式为：来源+兴趣方向，方便找到志同道合的朋友。

方式①、添加微信号：mlc2060，备注：来自 获取推荐资料
方式②、微信搜索公众号：机器学习社区，后台回复：推荐资料

算法原理

UserCF算法主要是考虑用户与用户之间的相似度，给用户推荐和他兴趣相似的其他用户喜欢的物品。

俗话说"物以群分，人以类聚"，人们总是倾向于跟自己志同道合的人交朋友。同理，你朋友喜欢的东西你大概率也可能会喜欢，UserCF算法正是利用了这个原理。

举个例子，如果要给一个用户A推荐物品，可以先找到与A最为相似的用户B，接着获取用户B最喜欢的且用户A没有听说过的物品，并预测用户A对这些物品的评分，从中选取评分最高的若干个物品推荐给用户A。

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

1. 找到与目标用户兴趣相似的用户集合

2. 找到这个集合中的用户最喜欢的，且目标用户还未接触过的物品推荐给目标用户

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

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

对于用户u和用户v，令N(u)代表用户u喜欢的物品合集，令N(v)代表用户v喜欢的物品合集。N(u)∩N(v)代表的是用户u和用户v都喜欢的物品，N(u)∪N(v)代表的是用户u和用户v喜欢的物品的合集，那么可以利用以下公式来简单计算相似度:

上述公式叫做Jaccard公式，直观上理解就是，将用户u与用户v都喜欢的物品的数量除以他们喜欢物品的总和，如果u和v喜欢的物品是一模一样的，则u和v的相似度为1。

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

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

利用余弦相似度计算公式可以得到如下结果：

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

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

算法工作流程

接下来，我们用一个简单例子演示一下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)，当用户量很大的时候，计算非常耗时,在实际运用中不可取。

观察一下相似度计算公式会发现，其实如果用户没有共同喜欢的物品（比如表中的用户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，因此也被分到了一起。

那这么做的目的是什么呢？回顾一下上面说的用户相似度计算方法，可以看到无论是哪一种方法，所以我们的目的就是为了快速地求出任意用户之间的交集。

由此可以建立下面的用户喜爱物品交集矩阵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

	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共同喜欢的物品在他们总共喜欢物品中占据的比例。

比如，两个用户都购买了时下热门物品，这并不能说明他们兴趣相似，因为热门物品是绝大多数人都会买的东西。换句话说，两个用户对冷门物品采用过相同的行为更能说明他们兴趣的相似度。

在下一节的代码实践中，分别实现了基于这两种相似度计算的UserCF算法。

代码实践

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

• 训练阶段
• 推荐阶段

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

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

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

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

训练阶段

数据预处理，建立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)

推荐阶段

下面代码实现了推荐的功能，函数最后会返回一个逆序排列的dict，里面包含了UserCF算法筛选出来的推荐物品：

    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])

部分核心代码

下面的代码实现推荐核心功能，修改“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

    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


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，里面包含了给用户推荐的电影以及用户对每部电影的感兴趣程度，按照逆序排列。

运行结果如下：