电子商务中的个性化算法

Jul 07

Rex分享 个性化推荐, 电子商务, 算法 4 Comments

声明：以下介绍纯属科普性质的，有些说法可能达不到学术上的严谨要求，全为更好的理解。

一、基于内容推荐
基于内容的推荐（Content-based Recommendation）是信息过滤技术的延续与发展，它是建立在项目的内容信息上作出推荐的，而不需要依据用户对项目的评价意见，更多地需要用机器学习的方法从关于内容的特征描述的事例中得到用户的兴趣资料。在基于内容的推荐系统中，项目或对象是通过相关的特征的属性来定义，系统基于用户评价对象的特征，学习用户的兴趣，考察用户资料与待预测项目的相匹配程度。用户的资料模型取决于所用学习方法，常用的有决策树、神经网络和基于向量的表示方法等。
基于内容的用户资料是需要有用户的历史数据，用户资料模型可能随着用户的偏好改变而发生变化。 基于内容推荐方法的优点是：

1. 不需要其它用户的数据，没有冷开始问题和稀疏问题。
2. 能为具有特殊兴趣爱好的用户进行推荐。
3. 能推荐新的或不是很流行的项目，没有新项目问题。
4. 通过列出推荐项目的内容特征，可以解释为什么推荐那些项目。
5. 已有比较好的技术，如关于分类学习方面的技术已相当成熟。

缺点是要求内容能容易抽取成有意义的特征，要求特征内容有良好的结构性，并且用户的口味必须能够用内容特征形式来表达，不能显式地得到其它用户的判断情况。

二、协同过滤推荐
协同过滤推荐（Collaborative Filtering Recommendation）技术是推荐系统中应用最早和最为成功的技术之一。它一般采用最近邻技术，利用用户的历史喜好信息计算用户之间的距离，然后利用目标用户的最近邻居用户对商品评价的加权评价值来预测目标用户对特定商品的喜好程度，系统从而根据这一喜好程度来对目标用户进行推荐。协同过滤最大优点是对推荐对象没有特殊的要求，能处理非结构化的复杂对象，如音乐、电影。
协同过滤是基于这样的假设：为一用户找到他真正感兴趣的内容的好方法是首先找到与此用户有相似兴趣的其他用户，然后将他们感兴趣的内容推荐给此用户。其基本思想非常易于理解，在日常生活中，我们往往会利用好朋友的推荐来进行一些选择。协同过滤正是把这一思想运用到电子商务推荐系统中来，基于其他用户对某一内容的评价来向目标用户进行推荐。
基于协同过滤的推荐系统可以说是从用户的角度来进行相应推荐的，而且是自动的，即用户获得的推荐是系统从购买模式或浏览行为等隐式获得的，不需要用户努力地找到适合自己兴趣的推荐信息，如填写一些调查表格等。
和基于内容的过滤方法相比，协同过滤具有如下的优点：

1. 能够过滤难以进行机器自动内容分析的信息，如艺术品，音乐等。
2. 共享其他人的经验，避免了内容分析的不完全和不精确，并且能够基于一些复杂的，难以表述的概念（如信息质量、个人品味）进行过滤。
3. 有推荐新信息的能力。可以发现内容上完全不相似的信息，用户对推荐信息的内容事先是预料不到的。这也是协同过滤和基于内容的过滤一个较大的差别，基于内容的过滤推荐很多都是用户本来就熟悉的内容，而协同过滤可以发现用户潜在的但自己尚未发现的兴趣偏好。
4. 能够有效的使用其他相似用户的反馈信息，较少用户的反馈量，加快个性化学习的速度。

虽然协同过滤作为一种典型的推荐技术有其相当的应用，但协同过滤仍有许多的问题需要解决。最典型的问题有稀疏问题（Sparsity）和可扩展问题（Scalability）。

三、基于关联规则推荐
基于关联规则的推荐（Association Rule-based Recommendation）是以关联规则为基础，把已购商品作为规则头，规则体为推荐对象。关联规则挖掘可以发现不同商品在销售过程中的相关性，在零售业中已经得到了成功的应用。管理规则就是在一个交易数据库中统计购买了商品集X的交易中有多大比例的交易同时购买了商品集Y，其直观的意义就是用户在购买某些商品的时候有多大倾向去购买另外一些商品。比如购买牛奶的同时很多人会同时购买面包。
算法的第一步关联规则的发现最为关键且最耗时，是算法的瓶颈，但可以离线进行。其次，商品名称的同义性问题也是关联规则的一个难点。

四、基于效用推荐
基于效用的推荐（Utility-based Recommendation）是建立在对用户使用项目的效用情况上计算的，其核心问题是怎么样为每一个用户去创建一个效用函数，因此，用户资料模型很大程度上是由系统所采用的效用函数决定的。基于效用推荐的好处是它能把非产品的属性，如提供商的可靠性（Vendor Reliability）和产品的可得性（Product Availability）等考虑到效用计算中。
五、基于知识推荐
基于知识的推荐（Knowledge-based Recommendation）在某种程度是可以看成是一种推理（Inference）技术，它不是建立在用户需要和偏好基础上推荐的。基于知识的方法因它们所用的功能知识不同而有明显区别。效用知识（Functional Knowledge）是一种关于一个项目如何满足某一特定用户的知识，因此能解释需要和推荐的关系，所以用户资料可以是任何能支持推理的知识结构，它可以是用户已经规范化的查询，也可以是一个更详细的用户需要的表示。
六、组合推荐
由于各种推荐方法都有优缺点，所以在实际中，组合推荐（Hybrid Recommendation）经常被采用。研究和应用最多的是内容推荐和协同过滤推荐的组合。最简单的做法就是分别用基于内容的方法和协同过滤推荐方法去产生一个推荐预测结果，然后用某方法组合其结果。尽管从理论上有很多种推荐组合方法，但在某一具体问题中并不见得都有效，组合推荐一个最重要原则就是通过组合后要能避免或弥补各自推荐技术的弱点。
在组合方式上，有研究人员提出了七种组合思路：

1. 加权（Weight）：加权多种推荐技术结果。
2. 变换（Switch）：根据问题背景和实际情况或要求决定变换采用不同的推荐技术。
3. 混合（Mixed）：同时采用多种推荐技术给出多种推荐结果为用户提供参考。
4. 特征组合（Feature combination）：组合来自不同推荐数据源的特征被另一种推荐算法所采用。
5. 层叠（Cascade）：先用一种推荐技术产生一种粗糙的推荐结果，第二种推荐技术在此推荐结果的基础上进一步作出更精确的推荐。
6. 特征扩充（Feature augmentation）：一种技术产生附加的特征信息嵌入到另一种推荐技术的特征输入中。
7. 元级别（Meta-level）：用一种推荐方法产生的模型作为另一种推荐方法的输入。

主要推荐方法的对比

各种推荐方法都有其各自的优点和缺点，见表1。

注：本着不重复发明轮子的思想，以上部分内容转自http://www.guwendong.cn/post/2006/methods_for_recommender_system.html 但这个作者也应该转自某处吧，也为我见过里面原封不动的话。

下面是本人对于前文中提到的问题的一些解释：

1. 稀疏性问题：由于每个用户只对很少的商品做出评价，所以得到的用户相似性就不够准确，寻找相似邻居不可靠。

2. 冷开始问题：在加入一个新的项目的时候，没人评价，可定也不会有人推荐。

3. 奇异发现问题：系统一般推荐给用户的都是些熟悉的商品，而用户真正需要的是不熟悉的商品。

4. 新用户问题：在系统还不了解用户的时候无法推荐，所以如何尽快了解用户变得尤其重要。

5. 健壮性问题：用户评价可能充斥着生产厂家和竞争对手的“假评价信息”，所以系统应该具有某种健壮型来抵御假数据。

slope one 算法介绍

Apr 14

Rex分享 slope one, taste, 算法 1 Comment

1. 关于slope one的前世今生我就不多说了，Beyond Search 说的很清楚了。（其实我就是从他的Blog开始研究个性化推荐的）
2. 关于slope one算法要实现的目标和一个简单的实例Beyond Search也说了，我这里就接着他的稍微深入一些。
3. 更实际的例子：
4. 
5. 首先计算item1和item2的平均差值，((5-3)+(3-4))/2=0.5，还有item1和item3的平均差值，就是5-2=3，然后推算lucy对item1的评分，根据item1和item2的平均差值来看lucy对item1的评分可能为2+0.5=2.5，同理根据item1和item3的平均差值lucy对item1的评分可能为5+3=8.
6. 现在如何取舍那？使用加权平均数应该是一种比较好的方法， （因为2.5是根据两个值推算的，8是通过一个只推算的）
7. slope one 算法差不多真的就是这么简单了！
8. 有一个开源的Java程序taste里面有一个完整的slope one算法的实现，包括程序和一个关于grouplens数据的实例程序（或者说是验证程序……）。
9. 个人觉得slope one 很好、很强大呀！足够简单，推荐准确度也不逊色与其他复杂的推荐算法（当然，这个东西更大程度上取决与数据样本）。而且taste程序写的也很不错，稍加改造应该就可以用了。
10. 相关链接：Beyond Search 的文章、wikipedia、Slope One Predictors for Online Rating-Based Collaborative Filtering

窥视豆瓣的算法

Mar 20

Rex分享 算法, 豆瓣 No Comments

豆瓣一直是中国web2.0的楷模，它神奇的“猜”功能吸引了无数的粉丝。他到底为什么有这么神奇的能力那？古老的读心术吗？当然不是，这全部得力于他的推荐算法。

所谓推荐算法就是利用用户的一些行为，通过一些数学算法，推测出用户可能喜欢的东西。推荐算法主要分为两种（还有一些可能不在本文讲述的范围内）基于内容的推荐和基于协同过滤的推荐。基于内容的推荐比较容易理解，他是通过两样东西的内容之间的相关性进行推荐。比如说，A喜欢一篇400字文章，里面出现了“豆瓣”这个词100次。哪么系统就会推荐一些同样出现了“豆瓣”这个词很多次的文章给A。这就是基于内容的推荐，他的好处是比较好理解、简单、高效，缺点就是只能用来推荐文章等一些文字的东西。对于图片等一些多媒体的内容就无从下手了。

基于协同过滤的推荐算法，正好弥补了这个缺点，他理论上可以推荐世界上的任何一种东西。图片、音乐、样样可以。协同过滤算法主要是通过对未评分项进行评分预测来实现的。不同的协同过滤之间也有很大的不同。

基于用户的协同过滤算法

这种算法基于一个这样的假设“跟你喜好相似的人喜欢的东西你也很有可能喜欢。”所以基于用户的协同过滤主要的任务就是找出用户的最近邻居，从而根据最近邻居的喜好做出未知项的评分预测。这种算法主要分为3个步骤：

一，用户评分。可以分为显性评分和隐形评分两种。显性评分就是直接给项目评分（例如给豆瓣里的书籍评分），隐形评分就是通过评价或是购买的行为给项目评分（例如在当当购买了什么东西）。

二，寻找最近邻居。这一步就是寻找与你距离最近的用户，测算距离一般采用以下三种算法：1.皮尔森相关系数。2.余弦相似性。3调整余弦相似性。调整余弦相似性似乎效果会好一些。

三，推荐。产生了最近邻居集合后，就根据这个集合对未知项进行评分预测。把评分最高的N个项推荐给用户。

这种算法存在性能上的瓶颈，当用户数越来越多的时候，寻找最近邻居的复杂度也会大幅度的增长。因而这种算法无法满足及时推荐的要求。基于项的协同过滤解决了这个问题。

基于项的协同过滤算法

根基于用户的算法相似，只不过第二步改为计算项之间的相似度。由于项之间的相似度比较稳定可以在线下进行，所以解决了基于用户的协同过滤算法存在的性能瓶颈。

豆瓣应该采用的就是基于项的协同过滤算法。但是他不可能只使用一种算法，肯定是综合了许多的算法。至于都有什么算法，比例是什么。那只有豆瓣的工程师知道，我们是猜不出来的。

设计“好友“

Mar 01

Rex互联网 UE, 算法, 豆瓣 2 Comments

放假前就看了一系列的关于”好友“设计的文章。总想也以此为题写点什么，但是一拖就拖到了下一年。

引起这一系列他讨论的是”白鸦“发表的《常见功能设计之 “好友”》，里面主要思想就是，好友是单向的，加谁好友是我个人的自由，跟对方无关。所以他基本不赞同99%的”需要对方验证才能添加对方为好友”的做法。（最近看的一本书《small worlds》也提到了好友关系的不对称性）

后来，麦田为好友是双向还是单项做了一个分类，认为对于非专业的交友网站，或者网站主要业务不是建立在“好友”关系之上的网站，９９％的好友关系是单向的。而麦田所做的蚂蚁网就不能采用这种”轻盈“的单项好友的模式。原因是蚂蚁网是”已推荐为核心“的网络应用。推荐必须建立在双方相互确认的条件下。（这一点我本人不是很同意，具体的看法一会儿再说）

魏武挥又发表看法《好友 粉丝 偶像》，提出了所谓”好友，粉丝，偶像“的观点。认为双方认证的才是”好友“，单方面添加的是”粉丝“，单方面被添加的是”偶像“。他的观点应该是提倡单向好友的，并认为好友、粉丝、偶像这三种在单项好友模式下产生的三种状态都有其存在的意义。并且深化了麦田的观点”单向好友不是为了关系，而是为了阅读。“

白鸦借豆瓣改版又写了一篇blog：《再说“双向”好友。(谈豆瓣好友改版)》。借豆瓣的好友问题再一次的强调双向好友不符合人们的现实生活规律。

其实在讨论这个问题前，一定要解决另外一个问题。那就是什么才是网站里所谓的“好友”？只有弄清楚这个东西才能用现实中的规则来优化好友的功能。

先说一下网站里成为好友的几种情况：

1. A加B为好友单纯的是为了使自己的“好友”数遥遥领先与其他人，而事实上A根本不认识B，甚至没有说过半句话。
2. A因为B的某个东西（例如blog）开始想了解一下他，所以加B为好友，产生一些接触，之后两个人有没有了联系。但他们依然是“好友”。
3. A因为B的某个东西（例如blog）开始想了解一下他，所以加B为好友，然后两人一拍即合、相见恨晚。从此两个人成为紧密联系的“好友”
4. A认为B是他的偶像，加B为“好友”。目的是想了解偶像的动态。
5. A和B以前就认识，理所应当的加为好友。

从这5中情况来看只有3和5才是我们现实中说的好朋友，而其他的情况只是两个人或多或少的存在某种联系而已。所以我下的结论是网站中的好友关系只是一种联系人的关系，并非好朋友。

基于”好友并非好朋友“这个基础，我认为大家讨论的好友应该是单向的还是双向的问题就比较好解决了。举个例子说：

1. 我的手机里有几百个联系人，里面有我的朋友，同学，老师…………，里面有一些电话我会拨，但是有一些我是永远不会的（比如说，各科老师的电话，我是在有紧急需要的时候才打的但是这种情况极少）。这些人都是我的”好友“。但是老师那里99.99%没有我的号码。这说明了：”好友“有近有远，而且绝不是对称。
2. 我虽然可以确定老师那里99.99%没有我的号码，但是我不能去看他的电话本确认。因为每个人的联系人是一种隐私。
3. 我经常受到一些垃圾短信（我想是因为我的号码外泄被某人加为”好友“了）。但是我没有办法阻止他给我发短信，我只能在我的手机里面装一个短信防火墙来屏蔽它。只又一次说明”好友“绝对是单向的，而且我们无法阻止他人联系我，我所能做的只是在我这边阻止他。
4. 我的QQ里面有分组，但是我很难把同学和朋友分成两组。这一点还是我的手机做的最好（WindowsMobile），在我查找联系人的时候他会自动的把最近联系过的的联系人放在前面。所以说“好友”的的亲密程度不是自己可以分得清的，但是可以通过算法提供一个较为实用的排序。

通过对这个手机联系人案例的分析，我们完全可以肯定：”好友“绝对是单向的。对于大家讨论的单项好友的一些弊端，我认为是因为没有建立一个好的好友模型的原因。下面就是我根据手机联系人建立的一个好友模型：

原理很简单就是在每个人的前面加一个代理机器人，用它来屏蔽一些我不想要的消息。这个代理机器人的功能有：

1. 屏蔽未知联系人消息、
2. 屏蔽特定联系人消息、
3. 只向好友通知消息、
4. 向指定好友发送消息、
5. ……

使用这个好友模型就可以解决之前大家提出的问题。例如，麦田提出来的蚂蚁网推销员问题。A加B为好友，B没有加A。A推荐东西给B并没有任何动机问题，因为A认为B是他的好友。如果B觉得这是垃圾信息，完全可以用代理机器人屏蔽他（可能默认的规则就是屏蔽）。换个角度，如果B推荐给他的好友，这个信息当然不会推荐给A，因为B没有加A，甚至B根本不知道A加他为好友。还有麦田提出的一个顾虑：

“需要用户在内心建立两个模型：1，真正的好友（双向）；2订阅关系的好友（单向）。我认为，这样会为用户增加困扰，得不偿失。”

我觉得不然，用户更多的困扰因该是：好友太多，或者是没有好友。我提出的模型可以解决“好友太多和好友太少”的困扰。而真正的好友（双向）一定不会很多（现实中也是这样），没有人会去奢求太多。