1 概述
什么是协同过滤 (Collaborative Filtering, 简称 CF)?
首先想一个简单的问题,如果你现在想看个电影,但你不知道具体看哪部,你会怎么做?
大部分的人会问问周围的朋友,看看最近有什么好看的电影推荐,而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。
协同过滤算法又分为基于用户
的协同过滤算法和基于物品
的协同过滤算法
2 案例需求
如下数据是各用户对各文档的偏好:
用户/文档 | 文档A | 文档B | 文档C | 文档D |
---|---|---|---|---|
用户A | √ | √ | 推荐 | 推荐 |
用户B | √ | √ | √ | |
用户C | √ | √ | √ | |
用户D | √ | √ |
现在需要基于上述数据,给A用户推荐一篇文档
3 算法分析
3.1 基于用户相似度的分析
直觉分析:“用户A/B”都喜欢物品A和物品B,从而1]“用户A/B”的口味最为相近
因此,为“用户A”推荐物品时可参考“用户B”的偏好,从而推荐D
这种就是基于用户的协同过滤算法UserCF指导思想
3.2 基于物品相似度的分析
直觉分析:物品组合(A,D)被同时偏好出现的次数最多,因而可以认为A/D两件物品的相似(其实BD组合出现次数也最多,真实的推荐应该根据A用户的A文档推荐结果汇总B文档推荐结果,然后评分取前N名)度最高。从而,可以为选择了A物品的用户推荐D物品。
这种就是基于物品的协同过滤算法ItemCF指导思想
4 算法要点
4.1 指导思想
这种过滤算法的有效性基础在于:
- 用户偏好具有相似性,即用户可分类。这种分类的特征越明显,推荐准确率越高
- 物品之间具有相似性,即偏好某物品的人,都很可能也同时偏好另一件相似物品
4.2 两种CF算法适用的场景
什么情况下使用哪种算法推荐效果会更好?
不同环境下这两种理论的有效性也不同,应用时需做相应调整。
- 如豆瓣上的文艺作品,用户对其的偏好程度与用户自身的品位关联性较强;适合UserCF
- 而对于电子商务网站来说,商品之间的内在联系对用户的购买行为影响更为显著。
5 算法实现
总的来说,要实现协同过滤,需要一下几个步骤:
- 收集用户偏好
- 找到相似的用户或物品
- 计算推荐
5.1 收集用户偏好
用户有很多方式向系统提供自己的偏好信息,而且不同的应用也可能大不相同,下面举例进行介绍:
用户行为 | 类型 | 特征 | 作用 |
---|---|---|---|
评分 | 显式 | 整数量化值[0,n] | 可以得到精确偏好 |
投票 | 显式 | 布尔量化值0 | 1 |
转发 | 显式 | 布尔量化值0 | 1 |
保存书签 | 显式 | 布尔量化值0 | 1 |
标记书签Tag | 显式 | 一些单词 | 需要进一步分析得到偏好 |
评论 | 显式 | 一些文字 | 需要进一步分析得到偏好 |
点击流 | 隐式 | 一组点击记录 | 需要进一步分析得到偏好 |
页面停留时间 | 隐式 | 一组时间信息 | 噪音偏大,不好利用 |
购买 | 隐式 | 布尔量化值0 | 1 |
5.2 原始偏好数据的预处理
用户行为识别/组合
在一般应用中,我们提取的用户行为一般都多于一种,关于如何组合这些不同的用户行为,比如,可以将用户行为分为“查看”和“购买”等等,然后基于不同的行为,计算不同的用户 / 物品相似度。
类似于当当网或者京东给出的“购买了该图书的人还购买了 …”,“查看了图书的人还查看了 …”
喜好程度加权
根据不同行为反映用户喜好的程度将它们进行加权,得到用户对于物品的总体喜好。
一般来说,显式的用户反馈比隐式的权值大,但比较稀疏,毕竟进行显示反馈的用户是少数;同时相对于“查看”,“购买”行为反映用户喜好的程度更大,但这也因应用而异。
数据减噪和归一化
① 减噪:用户行为数据是用户在使用应用过程中产生的,它可能存在大量的噪音和用户的误操作,我们可以通过经典的数据挖掘算法过滤掉行为数据中的噪音,这样可以是我们的分析更加精确。
② 归一化:如前面讲到的,在计算用户对物品的喜好程度时,可能需要对不同的行为数据进行加权。但可以想象,不同行为的数据取值可能相差很大,比如,用户的查看数据必然比购买数据大的多,如何将各个行为的数据统一在一个相同的取值范围中,从而使得加权求和得到的总体喜好更加精确,就需要我们进行归一化处理。最简单的归一化处理,就是将各类数据除以此类中的最大值,以保证归一化后的数据取值在 [0,1] 范围中。
形成用户偏好矩阵
一般是二维矩阵,一维是用户列表,另一维是物品列表,值是用户对物品的偏好,一般是 [0,1] 或者 [-1, 1] 的浮点数值。
5.3 找到相似用户或物品
当已经对用户行为进行分析得到用户喜好后,我们可以根据用户喜好计算相似用户和物品,然后基于相似用户或者物品进行推荐,这就是最典型的 CF 的两个分支:基于用户的 CF 和基于物品的 CF。这两种方法都需要计算相似度,下面我们先看看最基本的几种计算相似度的方法。
5.4 相似度的计算
相似度的计算,现有的几种基本方法都是基于向量(Vector)的,其实也就是计算两个向量的距离,距离越近相似度越大。
在推荐的场景中,在用户 - 物品偏好的二维矩阵中,我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度,或者将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度。
CF的常用方法有三种,分别是欧式距离法、皮尔逊相关系数法、余弦相似度法。
为了测试算法,给出以下简单的用好偏好数据矩阵:
行表示三名用户,列表示三个品牌,对品牌的喜爱度按照1~5增加。
用户 | 苹果 | 小米 | 魅族v |
---|---|---|---|
zhangsan | 5 | 5 | 2 |
Lisi | 3 | 5 | 4 |
wangwu | 1 | 2 | 5 |
(1)欧氏距离法
就是计算每两个点的距离,比如Nike和Sony的相似度 。
数值越小,表示相似度越高。
def OsDistance(vector1, vector2):
sqDiffVector = vector1-vector2
sqDiffVector=sqDiffVector**2
sqDistances = sqDiffVector.sum()
distance = sqDistances**0.5
return distance
(2)皮尔逊相关系数
两个变量之间的相关系数越高,从一个变量去预测另一个变量的精确度就越高,这是因为相关系数越高,就意味着这两个变量的共变部分越多,所以从其中一个变量的变化就可越多地获知另一个变量的变化。如果两个变量之间的相关系数为1或-1,那么你完全可由变量X去获知变量Y的值。
- 当相关系数为0时,X和Y两变量无关系。
- 当X的值增大,Y也增大,正相关关系,相关系数在0.00与1.00之间
- 当X的值减小,Y也减小,正相关关系,相关系数在0.00与1.00之间
- 当X的值增大,Y减小,负相关关系,相关系数在-1.00与0.00之间
- 当X的值减小,Y增大,负相关关系,相关系数在-1.00与0.00之间
相关系数的绝对值越大,相关性越强,相关系数越接近于1和-1,相关度越强,相关系数越接近于0,相关度越弱。
在python中用函数corrcoef实现,具体方法见参考资料
(3)余弦相似度
通过测量两个向量内积空间的夹角的余弦值来度量它们之间的相似性。0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。两个向量有相同的指向时,余弦相似度的值为1;两个向量夹角为90°时,余弦相似度的值为0;两个向量指向完全相反的方向时,余弦相似度的值为-1。在比较过程中,向量的规模大小不予考虑,仅仅考虑到向量的指向方向。余弦相似度通常用于两个向量的夹角小于90°之内,因此余弦相似度的值为0到1之间。
def cosSim(inA,inB):
num = float(inA.T*inB)
denom = la.norm(inA)*la.norm(inB)
return 0.5+0.5*(num/denom)
注:本案例基于皮尔逊相关系数法实现
5.5 计算推荐
UserCF基于用户相似度的推荐
计算推荐的过程其实就是KNN算法的计算过程
ItemCF基于物品相似度的推荐
算法思路
- 构建物品的同现矩阵
- 构建用户对物品的评分矩阵
- 通过矩阵计算得出推荐结果
推荐结果=用户评分矩阵*同现矩阵
实质:计算各种物品组合的出现次数