阅读 842

[零基础入门推荐系统]基于用户和基于物品的协同过滤方法(python代码实现)

1. 前言: 为什么会有该系列?

最近,打算写《零基础入门推荐系统》系列,为了系统地介绍推荐系统知识,以及加强基础的实践能力。

该系列将结合一些书籍,比如项亮的《推荐系统实践》,由于项亮的推荐系统实践更偏项目以及工程设计,对排序模型介绍比较少,为了弥补这一不足,《零基础入门推荐系统》会更多地介绍一些基础排序模型,比如FM,DeepFM,DIN等模型。当然,每个模型会结合数学原理和python代码进行介绍,强化理论知识和实践能力。

推荐系统简介

推荐系统的目标是根据用户的历史,社交,上下文环境等信息去判断用户当前感兴趣的内容。

推荐系统一般包含四个环节:召回,粗排序,精排序,重排。

召回的算法有:ItemCF,UserCF,关联规则,Embedding,序列匹配,同类型收集等。

排序算法有:策略规则,线性模型,线性模型结合树模型,因子分解机模型,深度学习模型等。

在这里插入图片描述

以下将介绍两种召回模型:基于用户的协同过滤模型,基于物品的过滤模型。

2. 推荐系统的几种评测指标

对用户uu推荐NN个物品(记为R(u)R(u)), 记用户uu在测试集上喜欢的物品集合为T(u)T(u), 然后可以通过准确率,召回率,覆盖率,流行度来评测推荐算法的精度。

2.1 召回率Recall

 Recall =uR(u)T(u)uT(u)\text { Recall }=\frac{\sum\limits_{u}|R(u) \cap T(u)|}{\sum\limits_{u}|T(u)|}

召回率描述在真实用户-物品评分记录中推荐物品的比例。

具体的代码:

def recall(true, pred):
    """
    recall value = |true == pred|/len(true)
    :param true: dict, {user:[item1, item2]
    :param pred: dict, recommend list for each user. e.g.{user:[(user2, similarity)]}
    :return: 
    >>> true = {"u1":["item1", "item2"]}
    >>> pred = {"u1":[("u2", 0.6), ("u3", 0.1)]}
    """
    pred_true = 0
    all_true = 0
    print("pred",pred)
    for user, items in pred.items():
        for item in items:
            v, _ = item[0], item[1]
            if v in true[user]:
                pred_true += 1
        all_true += len(true[user])
    if all_true == 0:
        return 0
    return pred_true*1.0 / all_true
复制代码

2.2 精度Precision

 Precision =uR(u)T(u)uR(u)\text { Precision }=\frac{\sum_{u}|R(u) \cap T(u)|}{\sum_{u}|R(u)|}

精度描述在推荐列表中用户实际喜欢物品的比例。

def precision(true, pred):
    """
    precision value = |true == pred|/len(pred)
    :param true: dict, {user:[item1, item2]
    :param pred: dict, recommend list for each user. e.g.{user:[(user2, similarity)]}
    >>> true = {"u1":["item1", "item2"]}
    >>> pred = {"u1":[("u2", 0.6), ("u3", 0.1)]}
    :return:
    """
    pred_true = 0
    all_pred = 0
    for user,items in pred.items():
        for item in items:
            v, _ = item[0], item[1]
            if v in true[user]:
                pred_true += 1
            all_pred += 1
    if all_pred == 0:
        return 0
    return pred_true*1.0 / all_pred
复制代码

2.3 覆盖率 Coverage

 Coverage =UnUR(u)I\text { Coverage }=\frac{\left|U_{n \in U} R(u)\right|}{|I|}

描述最终推荐列表中的商品占总共商品的比例。如果所有的物品都被推荐给至少一个用户,那么覆盖率就是100%。

def coverage(actual_items, recommend_items):
    """
    coverage = len(set(pred))/len(set(actual_items))
    :param actual_items: set(), all items.
    :param recommend_items: set(), all recommend items
    :return:
    >>> actual_items = set("item1", "item2")
    >>> recommend_items = set("item1")
    """
    if len(set(actual_items)) == 0:
        return 1
    return (len(set(recommend_items))*1.0)/len(set(actual_items))
复制代码

2.4 流行度 Popularity

描述推荐的物品是否很热门,这侧面反映推荐的新颖度。 定义,用户看过这个物品,该物品的流行度+1。

def popularity(user_cf, train, test, N, K):
    """
    popularity means how many people have watched it. Log transformation is applied for stability.
    :param user_cf: recommend system.
    :param train: dict, the train set.
    :param test: dict, the test set.
    :param N: select top N items to recommend.
    :param K: select the moset K similar users.
    :return:
    >>> train = {"user":["item1", "item2"]}
    >>> test = {"user2":["item2"]}
    """
    item_popularity = dict()
    for user, items in train.items():
        for item in items:
            item_popularity[item] = item_popularity.get(item,0)+1
    ret = 0
    n = 0
    for user in test.keys():
        recommend_list = user_cf.recommend(user, N, K)
        for item,sim in recommend_list:
            ret += math.log(1 + item_popularity[item])
            n += 1
    if n == 0:
        return 0
    ret = ret*1.0/n
    return ret
复制代码

物品的流行度分布满足长尾分布,为了让流行度的平均值更加稳定,增加了log变换。

3. 基于领域的算法

3. 1 基于用户的协同过滤算法

步骤: (1)找到和目标用户兴趣相似的用户集合;

(2)根据该集合中用户喜欢的,且目标用户之前没见过的物品推荐给目标用户;

步骤(1)中衡量两个用户的相似度,可以通过以下公式计算:

wuv=N(u)N(v)N(u)N(v)w_{{uv}}=\frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}

其中,N(u)N(u)表示用户uu曾经有过正反馈的物品集合,令N(v)N(v)为用户vv曾经有过正反馈的物品集合。

或者通过余弦相似度:

wuv=N(u)N(v)N(u)N(v)w_{u v}=\frac{|N(u) \cap N(v)|}{\sqrt{|N(u)| \cdot |N(v)|}}

在实际的计算中,由于很多用户之间并没有对同样的物品产生过行为,即N(u)N(v)=0|N(u) \cap N(v)| = 0, 也就是说数据是稀疏的。

因此,我们首先经历物品到用户的倒排表,也就是每个物品保存对该物品产生行为的用户列表, 再进行计算用户间的相似度。

步骤(2)对目标用户进行推荐物品:

p(u,i)=vS(u,K)U(i)warrvip(u, i)=\sum_{v \in S(u, K) \cap U(i)} w_{\mathrm{ar}} r_{v i}

其中, S(u,K)S(u, K) 包含了和用户uu兴趣最接近的KK个用户,U(i)U(i)是对物品ii有过行为的用户集合, wuvw_{uv} 是用户 uu 和用户vv的兴趣相似度, rvir_{vi}代表用户vv对物品ii的兴趣。 如果使用单一行为的隐反馈数据,即无法获取用户对物品的评价,rvi=1r_{vi}=1.

用户相似度计算的改进 UserCF-IIF

之前用户相似度对不同的物品的权重都一样,但是两个用户对冷门物品采取过同样的行为更能说明他们兴趣的相似度。

wuv=iN(u)N(v)1log(1+N(i))N(u)N(v)w_{u v}=\frac{\sum_{i \in N(u) \cap N(v)} \frac{1}{\log( 1+|N(i)| )}}{\sqrt{|N(u)| \cdot |N(v)|}}

其中, 1log(1+N(i))\frac{1}{\log( 1+|N(i)| )} 惩罚了用户uu和用户vv共同兴趣列表中热门商品对他们相似度的影响。

缺点: 由于用户数目越来越大,计算用户兴趣相似度矩阵越来越困难,运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系。 其次,基于用户的协同概率很难对推荐结果作为解释。

3. 2 基于物品的协同过滤算法

基于物品的协同过滤算法应用广泛。 基于物品的协同过滤算法分成两步: (1)计算物品之间的相似度; (2)根据物品的相似度和用户的历史行为给用户生成推荐列表;

步骤(1)中,

wij=U(i)U(j)U(i)w_{{ij}}=\frac{|U(i) \cap U(j)|}{|U(i) |}

其中,N(i)N(i)表示喜欢物品ii的用户集合,令U(i)U(j)U(i) \cap U(j)为同时喜欢物品ii和物品jj的用户集合。上述公式统计喜欢物品ii 中有多少比例的用户也喜欢物品jj.

上述公式存在一个问题,如果物品jj很热门,那么wijw_{ij}会接近于1,造成任何物品都会和热门的物品有很大的相似度。

为了避免推荐热门的物品,挖掘长尾信息,定义:

wij=U(i)U(j)U(i)U(j)w_{{ij}}=\frac{|U(i) \cap U(j)|}{\sqrt{|U(i) | \cdot |U(j)|}}

上述公式惩罚了物品jj的权重,减轻了热门物品和很多物品相似的可能性。

步骤(2)中,ItemCF 通过以下公式计算用户uu对一个物品jj的兴趣:

puj=iN(u)S(j,K)wjiruip_{u j}=\sum_{i \in N(u) \cap S(j, K)} w_{j i} r_{u i}

其中, N(u)N(u) 是用户uu 喜欢的物品集合, S(j,K)S(j, K)是和物品jj 最相似的KK个物品的集合, wjiw_{ji} 是物品jjii的相似度, ruir_{ui} 是用户uu 对物品 ii的兴趣。(对于隐反馈数据集,如果用户u对物品 i 有过行为,即可令 rui=1r_{ui}=1.)

物品相似度计算的改进 ItemCF-IUF

之前物品相似度对不同的用户的权重都一样,但是存在比较活跃的用户,买书并非出于自身的兴趣,这些用户对于他购买的书两两相似度的贡献应该远远小于不是很活跃但出于个人兴趣购买的用户。

IUF(Inverse User Frequence),即用户活跃度对数的倒数的参数,认为活跃用户对物品相似度的贡献应该小于不活跃的用户:

wij=nU(i)U(j)1log1+U(n)U(i)U(j)w_{i j}=\frac{\sum_{n \in U(i) \cap U(j)} \frac{1}{\log 1+|U(n)|}}{\sqrt{|U(i)| \cdot |U(j)|}}

其中, 1log(1+U(i))\frac{1}{\log( 1+|U(i)| )} 惩罚了用户ii和用户jj共同兴趣列表中热门商品对他们相似度的影响。

物品相似度的归一化

考虑到不同类别的相似度的单位应该一致,应该对物品相似度进行归一化。

比如,有两件物品A和B,如果A类物品之间的相似度是0.5, B类物品之间的相似度是0.6, A和B类间的相似度是0.2。 在这种情况下, 一个用户喜欢了10个A类和10个B类商品,ItemCF会推荐更多的B类商品。但归一化后,A类物品之间的相似度变成1,B类物品相似度也变成1,系统推荐A类物品和B类物品的数目会大致相等。因此,相似度的归一化可以提高推荐的多样性。

wij=wijmaxjwijw_{i j}^{\prime}=\frac{w_{i j}}{\max _{j} w_{i j}}

哈利波特问题 一开始,亚马逊网使用ItemCF会发现推荐的物品大多数和《哈利波特》有关,这是因为这本书太热门了,购买任何一本书的人几乎都会购买它。这导致了热门物品会获得比较大的相似度。

改进的方案是,增加对热门物品的惩罚:

wij=U(i)U(j)U(i)1αU(j)αw_{i j}=\frac{|U(i) \cap U(j)|}{|U(i)|^{1-\alpha}|U(j)|^{\alpha}}

其中,α[0.5,1]\alpha \in [0.5,1], 通过提高α\alpha,就可以惩罚热门的物品jj.

如果α=0.5\alpha = 0.5, 这就是标准的ItemCF算法。

一般,α\alpha 越大, 覆盖率会提高和流行度会减轻,但是,精确率和召回率会变差。

4. 实践

4.1 MovieLens数据集介绍

MovieLens是电影评分的集合,有各种大小。 数据集命名为1M,10M和20M,是因为它们包含1,10和20百万个评分。

为了方便实验集测试,本次实验使用了1 million的数据集。 下载链接:https://grouplens.org/datasets/movielens/

数据集一共包含三个文件:

users.dat 用户属性文件

UserID::Gender::Age::Occupation::Zip-code
复制代码

movies.dat 电影本身属性文件

MovieID::Title::Genres
复制代码

ratings.dat 用户给电影文件

UserID::Gender::Age::Occupation::Zip-code
复制代码

4.2 基于用户的协同过滤实验

把选择top相似用户个数KK设定80, 选择推荐给目标用户的商品数量NN选择30。

训练集和测试集按0.8:0.2比例进行划分。

class UserCF(object):
    """
    用户协同过滤,根据相似用户推荐内容
    """
    def train(self, user_items):
        """
        训练模型
        :return:
        """
        self.user_items = user_items
        # 计算用户的协同矩阵
        self.user_sim_matrix = self.user_similarity(user_items)
        #self.user_sim_matrix = self.improved_user_similarity(user_items)
        return self.user_sim_matrix

    def improved_user_similarity(self, user_items):
        """
        improved method of calculating the similarity. UserCF-IIF
        :param user_items: {user1:[movie1,movie2], user2:[movie1]}
        :return:
        """
        # build inverse table for item_users
        item_users = dict()
        for u, items in user_items.items():
            for i in items:
                if i not in item_users:
                    item_users[i] = set()
                item_users[i].add(u)

        # calculate co-rated items between users.
        C = dict()
        N = dict()
        for item, users in item_users.items():
            # each user u and user v both like the same item, similarity add 1/log(1+U(item))
            for u in users:
                N[u] = N.get(u,0) + 1
                if u not in C:
                    C[u] = dict()
                for v in users:
                    if v == u:
                        continue
                    C[u][v] = C[u].get(v,0) + 1/math.log(1+len(users))

        # calculate final similarity matrix W
        W = dict()
        for u, related_users in C.items():
            if u not in W:
                W[u] = dict()
            for v, cuv in related_users.items():
                W[u][v] = cuv / math.sqrt(N[u] * N[v])

        return W



    def user_similarity(self, user_items):
        """
        calculate the similarity between users.
        :param user_items: {user1:[movie1,movie2], user2:[movie1]}
        :return:
        """
        # build inverse table for item_users
        item_users = dict()
        for u, items in user_items.items():
            for i in items:
                if i not in item_users:
                    item_users[i] = set()
                item_users[i].add(u)

        # calculate co-rated items between users.
        C = dict()
        N = dict()
        for item, users in item_users.items():
            for u in users:
                N[u] = N.get(u,0) + 1
                if u not in C:
                    C[u] = dict()
                for v in users:
                    if v == u:
                        continue
                    C[u][v] = C[u].get(v,0) + 1

        # calculate final similarity matrix W
        W = dict()
        for u, related_users in C.items():
            if u not in W:
                W[u] = dict()
            for v, cuv in related_users.items():
                W[u][v] = cuv / math.sqrt(N[u] * N[v])

        return W

    def recommend(self, user, N, K):
        """
        recommend item according to user.
        :param user:
        :param N: the number of recommend items
        :param K: the number of most similar users
        :return:  recommend items dict, {item: similarity}
        """
        already_items = set(self.user_items.get(user, set()))
        recommend_items = dict()
        for v, sim in sorted(self.user_sim_matrix.get(user,dict()).items(), key=lambda x:-x[1])[:K]:
            for item in self.user_items[v]:
                if item in already_items:
                    continue
                recommend_items[item] = recommend_items.get(item,0) + sim
        recommend_item_list = sorted(recommend_items.items(), key=lambda x:-x[1])[:N]
        return recommend_item_list

    def recommend_users(self, users, N, K):
        """

        :param users: test set of users.
        :param N: the number of recommend items
        :param K: the number of most similar users
        :return: dict, {user:[movie1, movie2]}
        """
        recommend_result = dict()
        for user in users:
            recommend_item_list = self.recommend(user, N, K)
            recommend_result[user] = recommend_item_list
        return recommend_result

复制代码

实验结果:

准确率召回率覆盖率流行度
UserCF0.21650.23920.31327.0319
UserCF-IIF0.21810.24100.32147.0057

结论:UserCF-IIF模型在各项性能优于 UserCF, 偏向考虑冷门物品来衡量两个用户的相似度更加合理。

测试不同的K值对UserCF模型的影响

K准确率召回率覆盖率流行度
100.18560.20510.59226.7205
200.20440.22590.47976.8417
300.21150.23370.4266.9025
400.21480.23740.39066.9431
500.21590.23860.36996.9729
600.2170.23980.34796.9961
700.21670.23950.32477.016
800.21650.23920.31337.032
900.21660.23930.30027.0469
1000.21610.23880.28987.0595

结论:随着K值(目标用户相似的其他用户个数)的增大,模型的准确率和召回率会先增大,后减少;覆盖率和流行度在K值较小的时候,效果更好。

4.3 基于物品的协同过滤实验

class ItemCF(object):
    """
    物品协同过滤,根据用户浏览过的物品推荐相似物品
    """
    def train(self, user_items, alpha=0.5, normalization=False):
        """
        训练模型
        :return:
        """
        self.user_items = user_items
        # 计算物品的协同矩阵
        #self.item_sim_matrix = self.item_similarity(user_items, normalization=True)
        #self.item_sim_matrix = self.improved_item_similarity(user_items)
        self.item_sim_matrix = self.improved_item_similarity2(user_items, alpha=alpha, normalization=normalization)

        #print(self.item_sim_matrix)

        return self.item_sim_matrix

    def improved_item_similarity(self, user_items, normalization=False):
        """
        :param user_items: {user1:[movie1,movie2], user2:[movie1]}
        :return: W: {items1: {item2: sim12, item3:sim13}}
        """
        # calculate co-rated users between items.
        C = dict()
        N = dict()
        for user, items in user_items.items():
            for i in items:
                N[i] = N.get(i,0) + 1
                if i not in C:
                    C[i] = dict()
                for j in items:
                    if i == j:
                        continue
                    C[i][j] = C[i].get(j,0) + 1/math.log(1+len(items))

        # calculate final similarity matrix W
        W = dict()
        for i, related_items in C.items():
            if i not in W:
                W[i] = dict()
            for j, cij in related_items.items():
                W[i][j] = cij / math.sqrt(N[i] * N[j])

        if normalization:
            for i, item_list in W.items():
                item_list = [item/max(item_list) for item in item_list]
                W[i] = item_list
        return W

    def improved_item_similarity2(self, user_items, alpha=0.5, normalization=False):
        """
        Solution for Harry Potter problem.
        :param user_items: {user1:[movie1,movie2], user2:[movie1]}
        :return: W: {items1: {item2: sim12, item3:sim13}}
        """
        # calculate co-rated users between items.
        C = dict()
        N = dict()
        for user, items in user_items.items():
            for i in items:
                N[i] = N.get(i,0) + 1
                if i not in C:
                    C[i] = dict()
                for j in items:
                    if i == j:
                        continue
                    C[i][j] = C[i].get(j,0) + 1/math.log(1+len(items))

        # calculate final similarity matrix W
        W = dict()
        for i, related_items in C.items():
            if i not in W:
                W[i] = dict()
            for j, cij in related_items.items():
                # if N[i] < N[j]:
                W[i][j] = cij / (N[i]**(1-alpha) * N[j]**alpha)
                # else:
                #     W[i][j] = cij / (N[j] ** (1 - alpha) * N[i] ** alpha)

        if normalization:
            for i, item_list in W.items():
                item_list = [item/max(item_list) for item in item_list]
                W[i] = item_list
        return W

    def item_similarity(self, user_items, normalization=False):
        """
        :param user_items: {user1:[movie1,movie2], user2:[movie1]}
        :return: W: {items1: {item2: sim12, item3:sim13}}
        """
        # calculate co-rated users between items.
        C = dict()
        N = dict()
        for user, items in user_items.items():
            for i in items:
                N[i] = N.get(i,0) + 1
                if i not in C:
                    C[i] = dict()
                for j in items:
                    if i == j:
                        continue
                    C[i][j] = C[i].get(j,0) + 1

        # calculate final similarity matrix W
        W = dict()
        for i, related_items in C.items():
            if i not in W:
                W[i] = dict()
            for j, cij in related_items.items():
                W[i][j] = cij / math.sqrt(N[i] * N[j])

        if normalization:
            for i, item_sim_dict in W.items():
                max_val = max(item_sim_dict.values())
                #print(max_val)
                for j,sim in item_sim_dict.items():
                    item_sim_dict[j] = sim/max_val


        return W

    def recommend(self, user, N, K):
        """
        recommend item according to the history items of users.
        :param user:
        :param N: the number of recommend items
        :param K: the number of most similar users
        :return:  recommend items dict, {item: similarity}
        """
        already_items = set(self.user_items.get(user, set()))
        recommend_items = dict()

        for i in already_items:
            for j, sim in sorted(self.item_sim_matrix.get(i,dict()).items(), key=lambda x:-x[1])[:K]:
                if j in already_items:
                    continue
                recommend_items[j] = recommend_items.get(j,0) + sim
        recommend_item_list = sorted(recommend_items.items(), key=lambda x:-x[1])[:N]
        return recommend_item_list

    def recommend_users(self, users, N, K):
        """

        :param users:
        :param N:
        :param K:
        :return: dict, {user:[movie1, movie2]}
        """
        recommend_result = dict()
        for user in users:
            recommend_item_list = self.recommend(user, N, K)
            recommend_result[user] = recommend_item_list
        return recommend_result

复制代码

实验结果:

准确率召回率覆盖率流行度
ItemCF0.18240.20150.23237.2028
ItemCF-IUF0.18480.20420.22097.2635

结论:和ItemCF相比, ItemCF-IUF稍微提高了准确率和召回率,提高了覆盖率,流行度提高了(一些实验中,流行度也会减少,具体看实验数据集);说明,不活跃用户对物品相似度的贡献比活跃用户的贡献大的假设能提升模型性能。

测试不同的K对模型ItemCF的影响

K准确率召回率覆盖率流行度
100.19580.21630.356.984
200.19650.21710.2927.0805
300.19530.21580.27437.129
400.19160.21170.26237.1589
500.18920.2090.25337.1762
600.18690.20650.2467.1908
700.18460.2040.2377.1987
800.18250.20160.23247.2028
900.18130.20030.22367.2069
1000.17920.1980.22347.2083

结论:同样和UserCF模型一样,合理选择K值,才会让模型在准确率和召回率更佳,在本实验中ItemCF最佳的K是20左右,UserCF最佳的K是60左右。

测试ItemCF归一化的影响

模型(K=20)准确率召回率覆盖率流行度
Item-CF0.19650.21710.2927.0805
ItemCF-Norm0.20160.22280.34677.009

结论:对不同类别的物品相似度进行归一化能提升模型的性能。

测试不同惩罚流行度系数α\alpha对ItemCF的影响

α\alpha准确率召回率覆盖率流行度
0.40.19350.21370.20987.2609
0.50.20.2210.27767.1514
0.60.19880.21970.36616.9496

结论:普通的ItemCF算法的准确率和召回率最高,但是覆盖率和新颖度都不高,经过给热门物品更大惩罚后,模型的覆盖率和流行度得到改善。

5. 结论

(1)推荐系统评测指标除了介绍的准确率,召回率,覆盖率,流行度,还可以是用户满意度,多样性,新颖性,惊喜度,信任度,实时性,健壮性,商业目标等。 (2)UserCF的推荐更社会化,反映用户所在兴趣群体中物品的热门程度; ItemCF的推荐更加个性化,反映了用户自己的兴趣传承,但在技术角度上,如果物品更新的速度很快(比如新闻推荐中),ItemCF维护的物品相关度的表也需要更新很快,实践难度会很大。 在这里插入图片描述 这两种算法经过优化后,最终得到的离线性能其实是近似的。

完整的代码见GitHub 零基础入门推荐系统系列


参考:

  1. Github RecSys/Recommend System.ipynb;
  2. 推荐系统实践