一、基本原理

协同过滤(collaborative filtering)算法是最经典、最常用的推荐算法。其基本思想是收集用户偏好，找到相似的用户或物品，然后计算并推荐。
基于物品的协同过滤算法的核心思想就是：给用户推荐那些和他们之前喜欢的物品相似的物品。主要可分为两步：
(1) 计算物品之间的相似度，建立相似度矩阵。
(2) 根据物品的相似度和用户的历史行为给用户生成推荐列表。

用户购买记录

同时被购买矩阵C的计算

相似度的定义有多种方式，下面简要介绍其中几种：

1、同现相似度

$w_{i,j} = \dfrac{|N(i)\cap N(j)|}{|N(i)|}$

其中，分母 $|N(i)|$ 是喜欢物品 $i$ 的用户数，而分子 $|N(i)\cap N(j)|$ 是同时喜欢物品 $i$ 和物品 $j$ 的用户数。因此，上述公式可以理解为喜欢物品 $i$ 的用户中有多少比例的用户也喜欢物品 $j$ 。
上述公式存在一个问题。如果物品 $j$ 很热门， $w_{i,j}$ 就会很大，接近1。因此，该公式会造成任何物品都会和热门的物品有很大的相似度，为了避免推荐出热门的物品，可以用下面的公式：
$w_{i j}=\frac{|N(i) \cap N(j)|}{\sqrt{|N(i)||N(j)|}}$

这个公式惩罚了物品 $j$ 的权重，因此减轻了热门物品会和很多物品相似的可能性。
另外为减小活跃用户对结果的影响，考虑IUF(nverse User Frequence) ，即用户活跃度对数的倒数的参数，认为活跃用户对物品相似度的贡献应该小于不活跃的用户。
$w_{i j}=\frac{\sum_{u \in N(i) \cap N(j)} \frac{1}{\log 1+|N(u)|}}{\sqrt{|N(i)||N(j)|}}$

为便于计算，还需要进一步将相似度矩阵归一化 $w_{i j}^{\prime}=\frac{w_{i j}}{\max _{j} w_{i j}}$ 。

2、Cosine相似度

$w_{i,j} = cos\theta = \dfrac{N(i)\cdot N(j)}{||N(i)|||| N(j)||} = \dfrac{\sum_{k=1}^{len}(n_{ki} \times n_{kj})}{\sqrt{\sum_{k=1}^{len}n_{ki}^2}\sqrt{\sum_{k=1}^{len}n_{kj}^2}}$
其中 $n_{ki}$ 表示用户 $k$ 对物品 $i$ 的评分。 $w_{i,j}$ 在区间 $[-1,1]$ 内，越接近1表示相似度越高。

def cos_sim(X,Y):
    num = float(X.T*Y)
    denum = np.linalg.norm(X)*np.linalg.norm(Y)
    return 0.5+0.5*(num/denum)

3、欧几里得距离

$X, Y$ 表示空间中的两个点，则其欧几里得距离为：
$d(x, y)=\sqrt{\sum\left(x_{i}-y_{i}\right)^{2}}$
当 $n=2$ 时，即为平面上两个点的距离，当表示相似度时，可采用下式转换：
$\operatorname{sim}(x, y)=\frac{1}{1+d(x, y)}$
距离越小，相似度越大。

def eclud_sim(X,Y):
    return 1.0/(1.0+np.linalg.norm(X-Y))

4、皮尔逊相关系数

一般表示两个定距变量间联系的紧密程度，取值范围为[-1,1]
$p(x, y)=\frac{\sum x_{i} y_{i}-n \overline{x y}}{(n-1) s_{x} s_{y}}=\frac{n \sum x_{i} y_{i}-\sum x_{i} \sum y_{i}}{\sqrt{n \sum x_{i}^{2}-\left(\sum x_{i}\right)^{2}} \sqrt{n \sum y_{i}^{2}-\left(\sum y_{i}\right)^{2}}}$
其中 $s_x,s_y$ 是 $x$ 和 $y$ 的样品标准差

def pears_sim(X,Y):
    if len(X)<3:
        return 1.0
    return 0.5+0.5*np.corrcoef(X,Y,rowvar=0)[0][1]

二、评估指标

将用户行为数据按照均匀分布随机划分为M份，挑选一份作为测试集，将剩下的M-1份作为训练集。为防止评测指标不是过拟合的结果，共进行M次实验，每次都使用不同的测试集。然后将M次实验测出的评测指标的平均值作为最终的评测指标。

1、召回率

对用户u推荐N个物品(记为 $R(u)$ )，令用户u在测试集上喜欢的物品集合为 $T(u)$ ，召回率描述有多少比例的用户-物品评分记录包含在最终的推荐列表中。
$\operatorname{Recall}=\frac{\sum_{u}|R(u) \cap T(u)|}{\sum_{u}|T(u)|}$

2、准确率

准确率描述最终的推荐列表中有多少比例是发生过的用户-物品评分记录。
$\operatorname{Precision}=\frac{\sum_{u}|R(u) \cap T(u)|}{\sum_{u}|R(u)|}$

3、覆盖率

覆盖率反映了推荐算法发掘长尾的能力，覆盖率越高，说明推荐算法越能够将长尾中的物品推荐给用户。分子部分表示实验中所有被推荐给用户的物品数目(集合去重)，分母表示数据集中所有物品的数目。
$\text { Coverage }=\frac{\left|\cup_{u \in U} R(u)\right|}{|I|}$

三、算法实践

采用GroupLens提供的MovieLens数据集，http://www.grouplens.org/node/73。本章使用中等大小的数据集，包含6000多用户对4000多部电影的100万条评分。该数据集是一个评分数据集，用户可以给电影评1-5分5个不同的等级。本文着重研究隐反馈数据集中TopN推荐问题，因此忽略了数据集中的评分记录。

1、包的加载与变量定义

该部分定义了所需要的主要变量，集合采用字典形式的数据结构。

import random
import math 
from operator import itemgetter
import pandas as pd
    
class ItemBasedCF():
    def __init__(self):
        self.n_sim_movie = 20 #相似电影数
        self.n_rec_movie = 10 #推荐电影数
        self.train = {} #训练集
        self.test = {}  #测试集
        self.movie_sim_matrix = {} #相似矩阵
        self.movie_popular = {} #每部电影被看次数
        self.movie_count = 0 #电影数

2、数据加载

读取原始CSV文件，并划分训练集和测试集，训练集占比87.5%，同时建立训练集和测试集的用户字典，记录每个用户对电影评分的字典。

def get_dataset(self,filename,pivot=0.875):
    train_len,test_len = 0,0
    for line in self.load_file(filename):
        user,movie,rating,timestamp = line.split(',')
        if random.random()<pivot:
            self.train.setdefault(user,{})
            self.train[user][movie] = rating
            train_len += 1
        else:
            self.test.setdefault(user,{})
            self.test[user][movie] = rating
            test_len += 1
    print('Load dataset success!')
    print('train set:%s, test set:%s'% (train_len,test_len))

def load_file(self,filename):
    with open(filename,'r') as f:
        for i,line in enumerate(f):
            if i==0:
                continue
            yield line.strip('\r\n')

3、计算相似度矩阵

第一步循环读取每个用户及其看过的电影，并统计每部电影被看过的次数，以及电影总数；第二步计算矩阵C，C[i][j]表示同时喜欢电影i和j的用户数，并考虑对活跃用户的惩罚；第三步根据式\ref{similarity}计算电影间的相似性；第四步进行归一化处理。

def calc_movie_sim(self):
    for user,movies in self.train.items():
        for movie in movies:
            if movie not in self.movie_popular:
                self.movie_popular[movie] = 0
            self.movie_popular[movie] += 1
    self.movie_count = len(self.movie_popular)
    print('Total movies: %d'% self.movie_count)

    for user,movies in self.train.items():
        for m1 in movies:
            for m2 in movies:
                if m1 == m2:
                    continue
                self.movie_sim_matrix.setdefault(m1,{})
                self.movie_sim_matrix[m1].setdefault(m2,0)
                self.movie_sim_matrix[m1][m2] += 1/math.log(1+len(movies))
    print('Build co-rated users matrix success!')

    for m1,related_movies in self.movie_sim_matrix.items():
        for m2,count in related_movies.items():
            if self.movie_popular[m1] == 0 or self.movie_popular[m2] == 0:
                self.movie_sim_matrix[m1][m2] = 0
            else:
                self.movie_sim_matrix[m1][m2] = count / math.sqrt(self.movie_popular[m1]*self.movie_popular[m2])
    print('Calculate movie similarity matrix success!')

    max_w = 0
    for m1,related_movies in self.movie_sim_matrix.items():
        for m2,_ in related_movies.items():
            if self.movie_sim_matrix[m1][m2] > max_w:
                max_w = self.movie_sim_matrix[m1][m2]
    for m1,related_movies in self.movie_sim_matrix.items():
        for m2,_ in related_movies.items():
            self.movie_sim_matrix[m1][m2] = self.movie_sim_matrix[m1][m2]/max_w

4、对用户进行推荐

针对目标用户U，找到K部相似的电影，并推荐其N部电影，如果用户已经看过该电影则不推荐。

def recommend(self,user):
    K = self.n_sim_movie
    N = self.n_rec_movie
    rank = {}
    watched_movies = self.train[user]
    for movie,rating in watched_movies.items():
        for related_movie,w in sorted(self.movie_sim_matrix[movie].items(),key=itemgetter(1),reverse=True)[:K]:
            if related_movie in watched_movies:
                continue
            rank.setdefault(related_movie,0)
            rank[related_movie] += w*float(rating)
    return sorted(rank.items(),key=itemgetter(1),reverse=True)[0:N]

5、评估指标的计算

产生推荐并通过准确率、召回率和覆盖率进行评估。

def evaluate(self):
    print('Evaluateing starting ...')
    N = self.n_rec_movie
    hit,rec_count,test_count = 0,0,0 
    all_rec_movies = set()
    for i,user in enumerate(self.train):
        test_movies = self.test.get(user,{})
        rec_movies = self.recommend(user)
        for movie,w in rec_movies:
            if movie in test_movies:
                hit += 1
            all_rec_movies.add(movie)
        rec_count += N
        test_count += len(test_movies)
    precision = hit/(1.0*rec_count)
    recall = hit/(1.0*test_count)
    coverage = len(all_rec_movies)/(1.0*self.movie_count)
    print('precision=%.4f, recall=%.4f, coverage=%.4f'%(precision,recall,coverage))

结果如下所示，由于数据量较大，相似度矩阵为 $26221\times 26221$ 维，计算速度较慢，耐心等待即可。

Load dataset success!
train set:17498898, test set:2501365
Total movies: 26204
Build co-rated users matrix success!
Calculate movie similarity matrix success!
Evaluateing starting ...
precision=0.1969, recall=0.1090, coverage=0.0832

参考资料

[1]. https://blog.csdn.net/m0_37917271/article/details/82656158
[2]. 推荐系统与深度学习. 黄昕等. 清华大学出版社. 2019.
[3]. 推荐系统算法实践. 黄美灵. 电子工业出版社. 2019.
[4]. 推荐系统算法. 项亮. 人民邮电出版社. 2012.
[5]. 美团机器学习实践. 美团算法团队. 人民邮电出版社. 2018.

木末芙蓉花，山中发红萼。涧户寂无人，纷纷开且落。——王维《辋川集·辛夷坞》

推荐系统（一）：基于物品的协同过滤算法