推荐算法之协同过滤

原创

刘建银

修改于 2017-07-20 09:44:51

4.4K0

修改于 2017-07-20 09:44:51

文章被收录于专栏：刘建银的专栏

推荐算法在个性化领域有着广泛的应用，粗略统计，所涉及到的学科包括人工智能、机器学习、认知科学、信息抽取、数据挖掘、预测理论、近似理论，甚至是管理科学、市场营销和心理学。所使用的算法除了传统的协同过滤，还包括图模型（Graph Model）、矩阵分解（Matrix Factorization）、奇异值分解（SVD，SingularValue Decomposition）、链接分析（Link Analysis）、回归分析（Regression Analysis），以及机器学习领域各种分类和学习算法。常见的推荐算法分类如表1:

表1 推荐算法分类

推荐算法应用数据分析技术，找出用户最可能喜欢的东西推荐给用户，现在很多电子商务网站都有这个应用。目前用的比较多、比较成熟的推荐算法是协同过滤（Collaborative Filtering，简称CF）推荐算法，CF算法分为两大类，一类为基于memory的（Memory-based），另一类为基于Model的（Model-based），User-based和Item-based算法均属于Memory-based类型。CF的基本思想是根据用户之前的喜好以及其他兴趣相近的用户的选择来给用户推荐物品。

如图1所示，在CF中，用m×n的矩阵表示用户对物品的喜好情况，一般用打分表示用户对物品的喜好程度，分数越高表示越喜欢这个物品，0表示没有买过该物品。图中行表示一个用户，列表示一个物品，Uij表示用户i对物品j的打分情况。CF分为两个过程，一个为预测过程，另一个为推荐过程。预测过程是预测用户对没有购买过的物品的可能打分值，推荐是根据预测阶段的结果推荐用户最可能喜欢的一个或Top-N个物品。

基于用户(User-based)的协同过滤推荐算法原理和实现

基于用户的协同过滤推荐算法是最早诞生的，原理也较为简单。该算法1992年提出并用于邮件过滤系统，两年后1994年被GroupLens用于新闻过滤。一直到2000年，该算法都是推荐系统领域最著名的算法。

基本思想

俗话说“物以类聚、人以群分”，拿看电影这个例子来说，如果你喜欢《蝙蝠侠》、《碟中谍》、《星际穿越》、《源代码》等电影，另外有个人也都喜欢这些电影，而且他还喜欢《钢铁侠》，则很有可能你也喜欢《钢铁侠》这部电影。

所以说，当一个用户 A 需要个性化推荐时，可以先找到和他兴趣相似的用户群体 G，然后把 G 喜欢的、并且 A 没有听说过的物品推荐给 A，这就是基于用户的系统过滤算法。

原理

(1)找到与目标用户兴趣相似的用户集合；(2)找到这个集合中用户喜欢的、并且目标用户没有听说过的物品推荐给目标用户。

1. 发现兴趣相似的用户

通常用Jaccard公式或者余弦相似度计算两个用户之间的相似度。设 N(u) 为用户 u 喜欢的物品集合，N(v) 为用户 v 喜欢的物品集合，那么 u 和 v 的相似度是多少呢：

Jaccard公式：

wuv 代表用户 u 与 v 之间的兴趣相似度，N(u)表示用户 u 曾经喜欢过的物品集合, N(v) 表示用户 v 曾经喜欢过的物品集合。

余弦相似度：

脑补一下数学知识：

两个向量间的余弦值可以很容易地通过使用欧几里得点积和量级公式推导：

鉴于两个向量的属性， A 和B的余弦相似性θ用一个点积形式来表示其大小，如下所示：

产生的相似性范围从-1到1：-1意味着两个向量指向的方向正好截然相反，1表示它们的指向是完全相同的，0通常表示它们之间是独立的，而在这之间的值则表示中度的相似性或相异性。对于文本匹配，属性向量A 和B 通常是文档中的词频向量。余弦相似性，可以被看作是一个规范比较文件长度的方法。在信息检索的情况下，由于一个词的频率（TF-IDF权）不能为负数，所以这两个文档的余弦相似性范围从0到1。并且，两个词的频率向量之间的角度不能大于90°。

假设目前共有4个用户： A、B、C、D；共有5个物品：a、b、c、d、e。用户与物品的关系（用户喜欢物品）如下图所示：

如何一下子计算所有用户之间的相似度呢？为计算方便，通常首先需要建立“物品—用户”的倒排表，如下图所示：

然后对于每个物品，喜欢他的用户，两两之间相同物品加1。例如喜欢物品 a 的用户有 A 和 B，那么在矩阵中他们两两加1。如下图所示：

计算用户两两之间的相似度，上面的矩阵仅仅代表的是公式的分子部分。以余弦相似度为例，对上图进行进一步计算：

到此，计算用户相似度就大功告成，可以很直观的找到与目标用户兴趣较相似的用户。

2. 推荐物品

首先需要从矩阵中找出与目标用户 u 最相似的 K 个用户，用集合 S(u, K) 表示，将 S 中用户喜欢的物品全部提取出来，并去除 u 已经喜欢的物品。对于每个候选物品i，用户 u 对它感兴趣的程度用如下公式计算：

其中rvi 表示用户 v 对i的喜欢程度，在本例中都是为 1，在一些需要用户给予评分的推荐系统中，则要代入用户评分。

举个例子，假设我们要给 A 推荐物品，选取 K = 3 个相似用户，相似用户则是：B、C、D，那么他们喜欢过并且 A 没有喜欢过的物品有：c、e，那么分别计算 p(A, c) 和 p(A, e)：

看样子用户 A 对 c 和 e 的喜欢程度可能是一样的，在真实的推荐系统中，只要按得分排序，取前几个物品就可以了。

整个过程可以用一张图简单的如下：

优点

以使用者的角度来推荐的协同过滤系统有下列优点:

能够过滤机器难以自动内容分析的资讯，如艺术品，音乐等。
共用其他人的经验，避免了内容分析的不完全或不精确，并且能够基于一些复杂的，难以表述的概念（如资讯品质、个人品味）进行过滤。
有推荐新资讯的能力。可以发现内容上完全不相似的资讯，使用者对推荐资讯的内容事先是预料不到的。可以发现使用者潜在的但自己尚未发现的兴趣偏好。
推荐个性化、自动化程度高。能够有效的利用其他相似使用者的回馈资讯。加快个性化学习的速度。

缺点

虽然协同过滤作为一推荐机制有其相当的应用，但协同过滤仍有许多的问题需要解决。比如一些非常流行的商品可能很多人都喜欢，这种商品推荐给你就没什么意义了，所以计算的时候需要对这种商品加一个权重或者把这种商品完全去掉也行。再有，对于一些通用的东西，比如买书的时候的工具书，如现代汉语词典，新华字典神马的，通用性太强了，推荐也没什么必要了。这些都是推荐系统的脏数据，如何去掉脏数据，这是数据预处理的时候事情了，这里就不多说了。整体而言，最典型的问题有

新使用者问题(New User Problem) 系统开始时推荐品质较差
新项目问题(New Item Problem) 品质取决于历史资料集
稀疏性问题（Sparsity）
系统延伸性问题（Scalability）。

基于物品(Item-based)的协同过滤推荐算法原理和实现

item based collaborative filtering称为基于物品的协同过滤算法，简称Item CF，是目前业界应用最广的算法。该算法给用户推荐那些和他们之前喜欢的物品相似的物品。比如，该算法会因为你购买过《数据挖掘导论》而给你推荐《机器学习》。

原理

ItemCF主要分为两步：（1）计算物品之间的相似度；（2）根据物品的相似度和用户的历史行为给用户生成推荐列表。

1物品的相似度

Item-based算法首选计算物品之间的相似度，计算相似度的方法有以下几种：

基于余弦（Cosine-based）的相似度计算，通过计算两个向量之间的夹角余弦值来计算物品之间的相似性，公式如下：

其中分子为两个向量的内积，即两个向量相同位置的数字相乘。

基于关联（Correlation-based）的相似度计算，计算两个向量之间的Pearson-r关联度，公式如下：

其中R(u,i)表示用户u对物品i的打分，Ri表示第i个物品打分的平均值。

调整的余弦（Adjusted Cosine）相似度计算，由于基于余弦的相似度计算没有考虑不同用户的打分情况，可能有的用户偏向于给高分，而有的用户偏向于给低分，该方法通过减去用户打分的平均值消除不同用户打分习惯的影响，公式如下：

其中

表示用户u打分的平均值。

2预测值计算

根据之前算好的物品之间的相似度，接下来对用户未打分的物品进行预测，有两种预测方法：

加权求和。用过对用户u已打分的物品的分数进行加权求和，权值为各个物品与物品i的相似度，然后对所有物品相似度的和求平均，计算得到用户u对物品i打分，公式如下：

其中

为物品i与物品N的相似度，

为用户u对物品N的打分。

2.回归。

和上面加权求和的方法类似，但回归的方法不直接使用相似物品N的打分值

，因为用余弦法或Pearson关联法计算相似度时存在一个误区，即两个打分向量可能相距比较远（欧氏距离），但有可能有很高的相似度。因为不同用户的打分习惯不同，有的偏向打高分，有的偏向打低分。如果两个用户都喜欢一样的物品，因为打分习惯不同，他们的欧式距离可能比较远，但他们应该有较高的相似度。在这种情况下用户原始的相似物品的打分值进行计算会造成糟糕的预测结果。通过用线性回归的方式重新估算一个新的