3.11.3　协同过滤算法
本文所属图书&>&
本书是目前有关数据挖掘在数据化运营实践领域比较全面和系统的著作，也是诸多数据挖掘书籍中为数不多的穿插大量真实的实践应用案例和场景的著作，更是创造性地针对数据化运营中不同分析挖掘课题类型，推出一一对...&&
协同过滤是迄今为止最成功的推荐技术，被应用在很多成功的推荐中。电子商务推荐系统可根据其他用户的评论信息，采用协同过滤技术给目标用户推荐商品。协同过滤算法主要分为基于启发式和基于模型式两种。其中，基于启发式的协同过滤算法，又可以分为基于用户的协同过滤算法和基于项目的协同过滤算法。启发式协同过滤算法主要包含3个步骤：1）收集用户偏好信息；2）寻找相似的商品或者用户；3）产生推荐。
&巧妇难为无米之炊&，协同过滤的输入数据集主要是用户评论数据集或者行为数据集。这些数据集主要又分为显性数据和隐性数据两种类型。其中，显性数据主要是用户打分数据，譬如用户对商品的打分，如图3-4所示。
但是，显性数据存在一定的问题，譬如用户很少参与评论，从而造成显性打分数据较为稀疏；用户可能存在欺诈嫌疑或者仅给定了部分信息；用户一旦评分，就不会去更新用户评分分值等。
而隐性数据主要是指用户点击行为、购买行为和搜索行为等，这些数据隐性地揭示了用户对商品的喜好，如图3-5所示。
隐性数据也存在一定的问题，譬如如何识别用户是为自己购买商品，还是作为礼物赠送给朋友等。
1. 基于用户的协同过滤
基于用户（User-Based）的协同过滤算法首先要根据用户历史行为信息，寻找与新用户相似的其他用户；同时，根据这些相似用户对其他项的评价信息预测当前新用户可能喜欢的项。给定用户评分数据矩阵R，基于用户的协同过滤算法需要定义相似度函数s:U&U&R，以计算用户之间的相似度，然后根据评分数据和相似矩阵计算推荐结果。
在协同过滤中，一个重要的环节就是如何选择合适的相似度计算方法，常用的两种相似度计算方法包括皮尔逊相关系数和余弦相似度等。皮尔逊相关系数的计算公式如下所示：
其中，i表示项，例如商品；Iu表示用户u评价的项集；Iv表示用户v评价的项集；ru,i表示用户u对项i的评分；rv,i表示用户v对项i的评分；表示用户u的平均评分；表示用户v的平均评分。
另外，余弦相似度的计算公式如下所示：
另一个重要的环节就是计算用户u对未评分商品的预测分值。首先根据上一步中的相似度计算，寻找用户u的邻居集N&U, 其中N表示邻居集，U表示用户集。然后，结合用户评分数据集，预测用户u对项i的评分，计算公式如下所示：
其中，s(u, u')表示用户u和用户u'的相似度。
假设有如下电子商务评分数据集，预测用户C对商品4的评分，见表3-6。
表3-6　电商网站用户评分数据集
& 用户&商品1&商品2&商品3&商品4
用户A&4&?&3&5
用户B&?&5&4&?
用户C&5&4&2&?
用户D&2&4&?&3
用户E&3&4&5&?
表中? 表示评分未知。根据基于用户的协同过滤算法步骤，计算用户C对商品4的评分，其步骤如下所示。
（1）寻找用户C的邻居
从数据集中可以发现，只有用户A和用户D对商品4评过分，因此候选邻居只有2个，分别为用户A和用户D。用户A的平均评分为4，用户C的平均评分为3.667，用户D的平均评分为3。根据皮尔逊相关系数公式来看，用户C和用户A的相似度为：
同理，s(C, D) =-0.515。
（2）预测用户C对商品4的评分
根据上述评分预测公式，计算用户C对商品4的评分，如下所示：
依此类推，可以计算出其他未知的评分。
2. 基于项目的协同过滤
基于项目（Item-Based）的协同过滤算法是常见的另一种算法。与User-Based协同过滤算法不一样的是，Item-Based 协同过滤算法计算Item之间的相似度，从而预测用户评分。也就是说该算法可以预先计算Item之间的相似度，这样就可提高性能。Item-Based协同过滤算法是通过用户评分数据和计算的Item相似度矩阵，从而对目标Item进行预测的。
和User-Based协同过滤算法类似，需要先计算Item之间的相似度。并且，计算相似度的方法也可以采用皮尔逊关系系数或者余弦相似度，这里给出一种电子商务系统常用的相似度计算方法，即基于条件概率计算Item之间的相似度，计算公式如下所示：
其中，s(i, j)表示项i和j之间的相似度；freq(ij)表示i和j共同出现的频率；freq(i)表示i出现的频率；freq(j)表示j出现的频率；表示阻力因子，主要用于平衡控制流行和热门的Item，譬如电子商务中的热销商品等。
接下来，根据上述计算的Item之间的相似度矩阵，结合用户的评分，预测未知评分。预测公式如下所示：
其中，pu, i表示用户u对项i的预测评分；S表示和项i相似的项集；s(i, j)表示项i和j之间的相似度；ru, j表示用户u对项j的评分。
3. Item-Based协同过滤实例
在电子商务推荐系统中，商品相似度计算有着很重要的作用。它既可用于一些特定推荐场景，譬如直接根据当前的商品，为用户推荐相似度最高的Top N商品。同时，它还可以应用于个性化推荐，从而为用户推荐商品。电子商务网站收集了大量的用户日志，譬如用户点击日志等。
基于Item-Based协同过滤算法，笔者提出了一种增量式商品相似度的计算解决方案。该算法计算流程如图3-6所示。
其中，商品关系i表示第i天的商品关系数据集。
具体计算步骤如下。
1）获取当天用户点击行为数据，过滤掉一些噪声数据，譬如商品信息缺失等。从而得到用户会话sessionID、商品ID（商品标识）、浏览时间等信息，如表3-7所示。
由于A4的浏览时间和A1、A2、A3相差较大，因此将其过滤掉，这里定义为1800秒，如表3-8所示。
表3-7　用户点击行为日志表
用户会话ID&浏览商品的时间&&&& Item Pairs
100&A1, 20:12&A1, A2&& A1, A3
&A2, 20:13&A2,A1&& A2, A3
&A3, 20:15&A3,A1&& A3, A2
&A4, 23:30
表3-8　过滤后的用户点击行为日志表
浏览商品的时间&&&&& Item Pairs
&&&& A1, 20:12&A1, A2&& A1, A3
&&&& A2, 20:13&A2,A1&& A2, A3
&&&& A3, 20:15&A3,A1&& A3, A2
2）首先，计算任意两种商品之间的共同点击次数。然后，根据基于条件概率的商品相似度计算方法来计算商品的相似度。商品相似度公式如下。
其中，s(i, j)表示项i和j之间的相似度；freq(ij)表示i和j共同出现的频率；freq(i)表示i出现的频率；freq(j)表示j出现的频率。
3）合并前一天计算的商品相似度数据，进行投票判断，选择相似度较大的作为新的商品相似度，从而实现增量式商品相似度计算。
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'您的赞赏，是对我创作的最大鼓励。|赞赏
收藏已收藏 | 55赞 | 2
扫码分享到微信
产品经理一枚，伪文艺青年。
472篇作品3.1m阅读总量
热门问题12345678910Database Error
Error establishing a database connection& & & 转载请注明出处:&
　　个人微博：
　　 一个人想看电影的时候常常会思考要看什么电影呢。这个时候他可能会问周围爱好的人求推荐。现在社会每天都会产生海量的信息。面对这么多信息好多人都不知道什么信息是自己需要的。推荐系统正是起了这么一个作用。推荐系统的应用随处可见。网络购物是一个典型的例子，电子商务的运营商往往会根据用户在网站的行为推荐用户可能会购买的商品。豆瓣FM是做的一个非常好的电台，这个电台能够根据用户的历史行为学习出用户喜欢歌曲的类型，从而给用户推荐歌曲。除此之外还有电影推荐、新闻推荐、博客推荐等等。
　　本文主要介绍协同过滤算法。本博客以后会逐渐介绍一些其他的推荐算法。
& & & 协同过滤算法的出现标志着推荐系统的产生。协同过滤算法包含基于用户的协同过滤算法和基于物品的协同过滤算法。
& & & 基于用户的协同过滤算法基于这样一个事实，如果A和B在电影方面的喜好相同，那么把B喜欢的的电影推荐给A是有道理的。 根据这个事实，基于用户的协同过滤算法出现了。根据这个事实需要求出两个用户的相似度。这个相似度可以是公式1(jaccd)或者公式2(余弦公式)。 如果想计算每两个用户的相似度需要的时间复杂度为O(n*n*d)。n为用户数目，d为商品的数目。
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &&& & & & & & & & & & & & & & & & & & & & & & & & （公式1）
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &&& & & & & & & & & & & & & & & & & & & & & & &（公式2）
& & & 通过公式1或者2我们能得到一个相似度矩阵。然而在很多应用中这个相似度矩阵式非常稀疏的。也就是很多用户相互之间没有对相同的商品产生行为。如果我们直接先把相似度不为0的用户对数求出来，然后只计算这些不为0的用户对，这样子会剩很多复杂度。&用数组C[u][v]记录用户u和v有相同商品行为的数目。首相建立一个倒排表。每个物品都保存被产生过行为的用户。然后对于每个物品所有的用户对数（u,v）,C[u][v]加1。这样结束以后就可以只利用相似度不为0的用户对数了。
　　得到相似度矩阵后利用公式3预测用户u对物品i的感兴趣程度。其中S(u,k)表示与用户u最接近的k个用户N(i)表示对物品i有过行为的用户集合。&wuv 表示用户u和v的相似度，rvi表示用户v对物品i的感兴趣程度。
　　　　　　　　　　　　　　　　　　　　　　 　 & & & & & & & & & & & & & & & &（公式3）
　　到此基于用户的系统过滤算法基本就介绍完了。&公式1和公式2衡量用户的用户相似度其实上是比较粗糙的。举个例子，小时候基本每个人都会买《新华字典》，其实并不能据此说明他们的兴趣相似，然而如果两个人都买了《模式识别》，那么就基本可以肯定他们的兴趣是比较相似的。《新华字典》与《模式识别》的区别在于一个是火爆的物品，一个相对不火爆。因此相似度的计算方式可以修改为公式4。
1/(1+N(i) )惩罚了火爆的物品。
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &（公式4）
& & & &基于物品的协同过滤算法在应用中更频繁。基于物品的协同过滤算法主要基于这样的思想： 如果用户x购买了物品A，那么她很可能会购买与A很相似的物品B（比如A是面膜，B是洗面奶）。这样的话就需要计算物品间的相似度。
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &&& & & & & & & & & & & & & & & & &（公式5）
& & & &i和j分别表示两个物品， 其中N(i) 表示喜欢物品i的人，N(j) 表示喜欢物品j的人。这个公式可以理解购买了i的用户中有多少人购买了j。 这个公式其实有一个问题： 如果物品j是一个特别热门的物品， 那么物品j跟很多物品的相似度都会很高， wij 很可能都会接近1。因此为了避免热门物品造成的这种影响， 我们把公式修改为：
　　 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & && & & & & & & & & & & & & & & & & &（公式6）
& & & & 在得到了物品相似度后， 我们要计算用户u对物品j的兴趣程度：
　　　　　　　　　　　　　　　　　　　　　　　 &&& & & & & & & & & & & &（公式7）
& & & & 其中N(u) 是用户u喜欢的物品集合， S(j,k)是与物品j最相似的k个物品的集合。 wij是物品i和j的相似度。 rui &是用户u对物品i的兴趣度。基本思想就是，如果要计算用户u与物品j的兴趣度， 先找到与j最相似的k个物品，再看用户u与这些物品的感兴趣程度，加权得到用户u对物品j的兴趣程度。
　　　这里需要提出一个问题，如果用户u是一个书商，那么在计算物品相似度的时候，这个书上对他购买书中的任何两本书计算相似的时候都会做出贡献。 其实这事不合理的。 如果他购买了《数据挖掘导论》和一本《红楼梦》，这个信息其实意义不大的， 我们并不能因此而直接地增加这两本书的相似度。 这里我们需要对用户的热度做惩罚。
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & && & & & & & & &（公式8）
& & & & & 公式8是对公式6的修正， 惩罚了热门的用户。
　　　 &上述讨论只是用了无下文的隐性数据。 在计算物品相似度和用户相似度的时候有很多公式。实际应用中发现，基于用户的协同的过滤利用皮尔逊相关系数效果比较好。而基于物品的协同过滤利用余弦相似度效果会比较好。
参考资料：
《推荐系统实战》 &项亮著&
阅读(...) 评论()}