协同过滤推荐算法的原理及实现

一、协同过滤算法的原理及实现

二、基于物品的协同过滤算法详解

一、协同过滤算法的原理及实现

协同过滤推荐算法是诞生最早，并且较为著名的推荐算法。主要的功能是预测和推荐。算法通过对用户历史行为数据的挖掘发现用户的偏好，基于不同的偏好对用户进行群组划分并推荐品味相似的商品。协同过滤推荐算法分为两类，分别是基于用户的协同过滤算法(user-based collaboratIve filtering)，和基于物品的协同过滤算法(item-based collaborative filtering)。简单的说就是：人以类聚，物以群分。下面我们将分别说明这两类推荐算法的原理和实现方法。
在这里插入图片描述

1.基于用户的协同过滤算法(user-based collaboratIve filtering)

基于用户的协同过滤算法是通过用户的历史行为数据发现用户对商品或内容的喜欢(如商品购买，收藏，内容评论或分享)，并对这些喜好进行度量和打分。根据不同用户对相同商品或内容的态度和偏好程度计算用户之间的关系。在有相同喜好的用户间进行商品推荐。简单的说就是如果A,B两个用户都购买了x,y,z三本图书，并且给出了5星的好评。那么A和B就属于同一类用户。可以将A看过的图书w也推荐给用户B。

在这里插入图片描述

1.1寻找偏好相似的用户

我们模拟了5个用户对两件商品的评分，来说明如何通过用户对不同商品的态度和偏好寻找相似的用户。在示例中，5个用户分别对两件商品进行了评分。这里的分值可能表示真实的购买，也可以是用户对商品不同行为的量化指标。例如，浏览商品的次数，向朋友推荐商品，收藏，分享，或评论等等。这些行为都可以表示用户对商品的态度和偏好程度。
在这里插入图片描述

从表格中很难直观发现5个用户间的联系，我们将5个用户对两件商品的评分用散点图表示出来后，用户间的关系就很容易发现了。在散点图中，Y轴是商品1的评分，X轴是商品2的评分，通过用户的分布情况可以发现，A,C,D三个用户距离较近。用户A(3.3 6.5)和用户C(3.6 6.3)，用户D(3.4 5.8)对两件商品的评分较为接近。而用户E和用户B则形成了另一个群体。

在这里插入图片描述

散点图虽然直观，但无法投入实际的应用，也不能准确的度量用户间的关系。因此我们需要通过数字对用户的关系进行准确的度量，并依据这些关系完成商品的推荐。

1.2欧几里德距离评价

欧几里德距离评价是一个较为简单的用户关系评价方法。原理是通过计算两个用户在散点图中的距离来判断不同的用户是否有相同的偏好。以下是欧几里德距离评价的计算公式。

通过公式我们获得了5个用户相互间的欧几里德系数，也就是用户间的距离。系数越小表示两个用户间的距离越近，偏好也越是接近。不过这里有个问题，太小的数值可能无法准确的表现出不同用户间距离的差异，因此我们对求得的系数取倒数，使用户间的距离约接近，数值越大。在下面的表格中，可以发现，用户A&C用户A&D和用户C&D距离较近。同时用户B&E的距离也较为接近。与我们前面在散点图中看到的情况一致。
在这里插入图片描述

1.3皮尔逊相关度评价

皮尔逊相关度评价是另一种计算用户间关系的方法。他比欧几里德距离评价的计算要复杂一些，但对于评分数据不规范时皮尔逊相关度评价能够给出更好的结果。以下是一个多用户对多个商品进行评分的示例。这个示例比之前的两个商品的情况要复杂一些，但也更接近真实的情况。我们通过皮尔逊相关度评价对用户进行分组，并推荐商品。
在这里插入图片描述

1.4皮尔逊相关系数

皮尔逊相关系数的计算公式如下，结果是一个在-1与1之间的系数。该系数用来说明两个用户间联系的强弱程度。

二、基于物品的协同过滤算法详解

最近参加KDD Cup 2012比赛，选了track1，做微博推荐的，找了推荐相关的论文学习。“Item-Based Collaborative Filtering Recommendation Algorithms”这篇是推荐领域比较经典的论文，现在很多流行的推荐算法都是在这篇论文提出的算法的基础上进行改进的。

一、协同过滤算法描述

推荐系统应用数据分析技术，找出用户最可能喜欢的东西推荐给用户，现在很多电子商务网站都有这个应用。目前用的比较多、比较成熟的推荐算法是协同过滤（Collaborative Filtering，简称CF）推荐算法，CF的基本思想是根据用户之前的喜好以及其他兴趣相近的用户的选择来给用户推荐物品。

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

二、User-based算法与Item-based算法对比

·
CF算法分为两大类，一类为基于memory的（Memory-based），另一类为基于Model的（Model-based），User-based和Item-based算法均属于Memory-based类型，具体细分类可以参考wikipedia的说明。
·
User-based的基本思想是如果用户A喜欢物品a，用户B喜欢物品a、b、c，用户C喜欢a和c，那么认为用户A与用户B和C相似，因为他们都喜欢a，而喜欢a的用户同时也喜欢c，所以把c推荐给用户A。该算法用最近邻居（nearest-neighbor）算法找出一个用户的邻居集合，该集合的用户和该用户有相似的喜好，算法根据邻居的偏好对该用户进行预测。
·
User-based算法存在两个重大问题：
·
1. 数据稀疏性。一个大型的电子商务推荐系统一般有非常多的物品，用户可能买的其中不到1%的物品，不同用户之间买的物品重叠性较低，导致算法无法找到一个用户的邻居，即偏好相似的用户。
·
2. 算法扩展性。最近邻居算法的计算量随着用户和物品数量的增加而增加，不适合数据量大的情况使用。
·
Iterm-based的基本思想是预先根据所有用户的历史偏好数据计算物品之间的相似性，然后把与用户喜欢的物品相类似的物品推荐给用户。还是以之前的例子为例，可以知道物品a和c非常相似，因为喜欢a的用户同时也喜欢c，而用户A喜欢a，所以把c推荐给用户A。
·
因为物品直接的相似性相对比较固定，所以可以预先在线下计算好不同物品之间的相似度，把结果存在表中，当推荐时进行查表，计算用户可能的打分值，可以同时解决上面两个问题。

三、Item-based算法详细过程

·
（1）相似度计算
·
Item-based算法首选计算物品之间的相似度，计算相似度的方法有以下几种：
·
1. 基于余弦（Cosine-based）的相似度计算，通过计算两个向量之间的夹角余弦值来计算物品之间的相似性，公式如下：

在这里插入图片描述
·
其中分子为两个向量的内积，即两个向量相同位置的数字相乘。
·
2. 基于关联（Correlation-based）的相似度计算，计算两个向量之间的Pearson-r关联度，公式如下：

在这里插入图片描述
·
其中表示用户u对物品i的打分，表示第i个物品打分的平均值。
·
3. 调整的余弦（Adjusted Cosine）相似度计算，由于基于余弦的相似度计算没有考虑不同用户的打分情况，可能有的用户偏向于给高分，而有的用户偏向于给低分，该方法通过减去用户打分的平均值消除不同用户打分习惯的影响，公式如下：

在这里插入图片描述
·
其中表示用户u打分的平均值。
·
（2）预测值计算
·
根据之前算好的物品之间的相似度，接下来对用户未打分的物品进行预测，有两种预测方法：
·
1. 加权求和。
·
用过对用户u已打分的物品的分数进行加权求和，权值为各个物品与物品i的相似度，然后对所有物品相似度的和求平均，计算得到用户u对物品i打分，公式如下：
在这里插入图片描述

·
其中为物品i与物品N的相似度，为用户u对物品N的打分。
·
2. 回归。
·
和上面加权求和的方法类似，但回归的方法不直接使用相似物品N的打分值，因为用余弦法或Pearson关联法计算相似度时存在一个误区，即两个打分向量可能相距比较远（欧氏距离），但有可能有很高的相似度。因为不同用户的打分习惯不同，有的偏向打高分，有的偏向打低分。如果两个用户都喜欢一样的物品，因为打分习惯不同，他们的欧式距离可能比较远，但他们应该有较高的相似度。在这种情况下用户原始的相似物品的打分值进行计算会造成糟糕的预测结果。通过用线性回归的方式重新估算一个新的值，运用上面同样的方法进行预测。重新计算的方法如下：
在这里插入图片描述