推荐引擎相关算法

表oso_user_ratings的结构如下：
CREATE TABLE `oso_user_ratings` (
  `user_id` varchar(32) NOT NULL,
  `item_id` int(11) NOT NULL,
  `rating` decimal(14,4) NOT NULL DEFAULT '0.0000',
  KEY `item_id` (`item_id`),
  KEY `user_id` (`user_id`,`item_id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

表oso_slope_one的结构：
CREATE TABLE `oso_slope_one` (
  `item_id1` int(11) NOT NULL,
  `item_id2` int(11) NOT NULL,
  `times` int(11) NOT NULL,
  `rating` decimal(14,4) NOT NULL,
  KEY `item_id2` (`item_id2`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

1.表oso_user_ratings中的数据结构
select * from oso_user_ratings;
user_id item_id rating
111    1    1.0000
111    2    0.2000
112    1    1.0000
112    2    0.5000
113    1    0.3300
113    2    0.6600
113    3    1.0000

2.表oso_slope_one中的数据结构

表oso_slope_one中的数据的算法
private function _initSlopeOneTableByPHP()
    {        
        /**
         * Get distinct item_id
         */
        $sql = 'SELECT DISTINCT item_id FROM oso_user_ratings';
       //从表oso_user_ratings中取出不重复的item_id
        $rs = $this->_db->query($sql);
        while ($itemId = $rs->fetchColumn())
        {
            //分别将每一个item_id，与其它的item_id作一下对比，然后将计算以后的数据导入到表oso_slope_one中
            $slopeOneSql = 'insert into oso_slope_one (select a.item_id as item_id1,b.item_id as item_id2,count(*) as times, sum(a.rating-b.rating) as rating from oso_user_ratings a,oso_user_ratings b where a.item_id = '
                         . $itemId
                         .' and b.item_id != a.item_id and a.user_id=b.user_id group by a.item_id,b.item_id)';
            $this->_db->query($slopeOneSql);
        }
    }

这个sql语句的大致含义就:
取出不重复的item_id，循环获取同一个用户(a.user_id=b.user_id) 对不同歌曲(b.item_id != a.item_id)的打分的比率的差值，然后保存到表oso_slope_one中。

表oso_slope_one中的所有数据
select * from oso_slope_one;
item_id1 item_id2 times rating
1    2    3    0.9700
1    3    1    -0.6700
2    1    3    -0.9700
2    3    1    -0.3400
3    1    1    0.6700
3    2    1    0.3400

3.2中的sql语句中的数据分析
select a.item_id as item_id1,b.item_id as item_id2,count(*) as times, sum(a.rating-b.rating) as rating from oso_user_ratings a,oso_user_ratings b where a.item_id = '1' and b.item_id != a.item_id and a.user_id=b.user_id group by a.item_id,b.item_id

item_id1 item_id2 times rating
1    2    3    0.9700
1    3    1    -0.6700

表示
同时有3人为item_id为1与2的歌曲打分
同时有1人为item_id为1与3的歌曲打分
times字段表示同时为item_id为1与2的歌曲打分的次数
rating字段表示同时为item_id为1与2的歌曲打分的差值的和，差值为正说明1比2受欢迎，为负说明2比1受欢迎。

差值越小，说明item_id2的打分越高，则表示item_id2越受欢迎

打分越高，说明歌曲越受欢迎

其它的两个以此类推：
SELECT a.item_id AS item_id1,b.item_id AS item_id2,COUNT(*) AS times, SUM(a.rating-b.rating) AS rating FROM oso_user_ratings a,oso_user_ratings b WHERE a.item_id = '2' AND b.item_id != a.item_id AND a.user_id=b.user_id GROUP BY a.item_id,b.item_id
item_id1 item_id2 times rating
2    1    3    -0.9700
2    3    1    -0.3400

select a.item_id as item_id1,b.item_id as item_id2,count(*) as times, sum(a.rating-b.rating) as rating from oso_user_ratings a,oso_user_ratings b where a.item_id = '3' and b.item_id != a.item_id and a.user_id=b.user_id group by a.item_id,b.item_id

item_id1 item_id2 times rating
3    1    1    0.6700
3    2    1    0.3400

4.为了加深理解，看下面的sql语句
对上述3中的sql语句作了一下改进，select改成了a.*,b.*，去掉了group by a.item_id,b.item_id，其它的是一样的。

看了下面sql语句的输出结果以后，相信对协同过滤算法的理解又加深了一步。

a.select a.*,b.* from oso_user_ratings a,oso_user_ratings b where a.item_id = '1' and b.item_id != a.item_id and a.user_id=b.user_id

user_id item_id rating user_id item_id rating
111    1    1.0000    111    2    0.2000(用户111听了歌曲1与2)
112    1    1.0000    112    2    0.5000(用户112听了歌曲1与2)
113    1    0.3300    113    2    0.6600(用户113听了歌曲1与2)
113    1    0.3300    113    3    1.0000(用户113听了歌曲1与3)

b.SELECT a.*,b.* FROM oso_user_ratings a,oso_user_ratings b WHERE a.item_id = '2' AND b.item_id != a.item_id AND a.user_id=b.user_id

user_id    item_id    rating    user_id    item_id    rating
111    2    0.2000    111    1    1.0000(用户111听了歌曲2与1)
113    2    0.6600    113    1    0.3300(用户113听了歌曲2与1)
113    2    0.6600    113    3    1.0000(用户113听了歌曲2与3)
112    2    0.5000    112    1    1.0000(用户112听了歌曲2与1)

c.SELECT a.*,b.* FROM oso_user_ratings a,oso_user_ratings b WHERE a.item_id = '3' AND b.item_id != a.item_id AND a.user_id=b.user_id

user_id    item_id    rating    user_id    item_id    rating
113    3    1.0000    113    1    0.3300(用户113听了歌曲3与1)
113    3    1.0000    113    2    0.6600(用户111听了歌曲3与2)

有了上面的数据，实现电子商务中的买了商品xxx的用户也买了商品xxx，浏览了商品xxx的用户也浏览了商品xxx的功能就比较容易了，此时我们可以把item_id理解为商品的id:
1.当用户购买了商品1时，可以向他(她)提示，买了商品1的用户也买了商品3,2。
2.当用户在浏览商品2时，可以向他(她)提示，浏览了商品2的用户也浏览了商品3,1

5.根据item id给用户推荐指定的信息(基于item_id的协同过滤)
按照item_id2分组，按sum(rating/times)进行顺排，取前面的几个值。

根据插入到表oso_slope_one中时的sql语句，因为已经按照两个item_id进行分组了(group by a.item_id,b.item_id)，item_id1与item_id2相同时在表oso_slope_one中只可能存在一条记录的，item_id1相同的行中应该是不可能出现item_id2相同的，所以下面的sql语句加不加group by item_id2结果都是一样的。

2010-2-26 下面是我的测试，下面两个sql语句返回的结果是完全一样的。
select item_id2 from oso_slope_one where item_id1 = '272987' group by item_id2 order by sum(rating/times) limit 10;

select item_id2 from oso_slope_one where item_id1 = '272987' order by rating/times limit 10;

将item_id1换为264315后就不一样了(主要是当item_id1为264315时，有两行rating/times的值均为-0.97140000)，奇怪，最后知道为什么了，原因如下：
1.select中如果有两列(item_id2,rating/times)，则结果及排序完全一样(有group by及没有group by的情况)。
2.select中如果只有一列item_id2,则结果一样，排序有两个不一样(有group by及没有group by的情况
主要就是rating/times相同的两条记录排序不一样，其它的均一样
select item_id2,sum(rating/times) from oso_slope_one where item_id1 = '264315' group by item_id2 order by sum(rating/times) limit 10;

7698    -0.99390000
37836    -0.98680000
5156    -0.97830000
3791    -0.97140000
6195    -0.97140000
43160    -0.96970000
19803    -0.96870000
16356    -0.96380000
133117    -0.96380000
60923    -0.95660000

select item_id2,rating/times from oso_slope_one where item_id1 = '264315' order by rating/times limit 10;

7698    -0.99390000
37836    -0.98680000
5156    -0.97830000
3791    -0.97140000
6195    -0.97140000
43160    -0.96970000
19803    -0.96870000
16356    -0.96380000
133117    -0.96380000
60923    -0.95660000

public function getRecommendedItemsById($itemId, $limit = 20)
    {
        $sql = 'select item_id2 from oso_slope_one where item_id1 = '
             . $itemId
             . ' group by item_id2 order by sum(rating/times) limit '
             . $limit;
        return  $this->_db->fetchCol($sql);
    }

分别根据item_id为1,2,3时的推荐结果，sum(raging/times)的值越小的越排在前面。
SELECT item_id2 FROM oso_slope_one WHERE item_id1 = '1' GROUP BY item_id2 ORDER BY SUM(rating/times) LIMIT 10;

item_id2
3
2

SELECT item_id2 FROM oso_slope_one WHERE item_id1 = '2' GROUP BY item_id2 ORDER BY SUM(rating/times) LIMIT 10;
item_id2
3
1

SELECT item_id2 FROM oso_slope_one WHERE item_id1 = '3' GROUP BY item_id2 ORDER BY SUM(rating/times) LIMIT 10;
item_id2
2
1

6.基于用户的协同过滤
基于用户的协同过滤算法如下，经过项目中实际应用，发现按照基于用户的协同过滤得出来的结果不太准确，而且当用户数增多，用户听的歌曲越来越多的时候，直接读取数据库的效率非常低下，性能是一个非常大的问题。

比如有315813个音乐用户，表oso_user_ratings中的记录数为2316730，表oso_slope_one中的记录数为 58846482，二百多万条记录的表与五千多万条记录的表联合查询你想想效率能高吗？即使把这些数据库查询改成缓存来处理，代价也是非常高的，最重要的是推荐结果也不是很准，所以基于用户的协同不推荐使用。

这篇文章的大概意思跟我上述说的是差不多的，Amazon用的是基于Item的协同过滤技术。

基于用户的协同推荐算法随着用户数量的增多，计算量成线性加大，其性能会越来越差。而对于 Web 应用系统，响应速度绝是影响用户体验的最重要因素之一。这一点极大的限制了基于用户的协同过滤技术在实际系统中的使用。Amazon 更多地使用了基于项目（Item-based）的协同过滤技术，而且随着 Amazon 的成功，Item-based 方法也大为流行起来。豆瓣主要使用的也是 Item-based 方法。Via

  /**
     * Get recommended items by user's id
     *
     * @param int $userId
     * @param int $limit
     * @return array
     */
    public function getRecommendedItemsByUser($userId, $limit = 20)
    {
        $sql = 'select s.item_id2 from oso_slope_one s,oso_user_ratings u where u.user_id = '
             . $userId
             . ' and s.item_id1 = u.item_id and s.item_id2 != u.item_id group by s.item_id2 order by sum(u.rating * s.times - s.rating)/sum(s.times) desc limit '
             . $limit;
         return  $this->_db->fetchCol($sql);
    }

7.潘多拉（Pandora）和友播（Yobo）侧重基于内容层面的过滤，而Last.fm、豆瓣、8box更侧重协同过滤方式。

关于基于内容的过滤，以潘多拉为例，大致意思如下：

Pandora 弄了一个音乐基因组工程的技术后台，这些基因抓住了每首歌曲独一无二的特质——从旋律、调式、节奏，到配器、编曲、歌词，当然，还有声乐融合的奇妙世界。它关注的不是乐队看起来如何，他们应该从属于什么类型，或者谁买了他们的唱片——它关注的是每首歌听起来究竟如何。
　　在过去5年多的时间里，我们仔细聆听了10000名不同艺术家的歌曲，每次分析一首歌的某一种音乐特质。我们夜以继日地推进这项工作，尽力涵盖那些来自全世界各个工作室、俱乐部和车库的新鲜作品。Via

我的理解：如果旋律，调式，节奏等这些内容不好提取出来，歌词、歌曲的曲风、歌曲的歌手等这些歌曲的属性还是可以提取出来的，这样可以根据歌词、歌曲的曲风、歌曲的歌手等属性来向用户推荐相关的歌曲。

基于内容过滤的系统其优点是简单、有效。其缺点是特征提取的能力有限，过分细化，纯基于内容的推荐系统不能为客户发现新的感兴趣的资源,只能发现和客户已有兴趣相似的资源。这种方法通常被限制在容易分析内容的商品的推荐，而对于一些较难提取出内容 的商品，如音乐CD、电影等就不能产生满意的推荐效果。Via

我的理解：如果某正在听王菲的歌，如果按照歌手来推荐，则推荐结果中只是出现王菲的歌曲，这样不能为用户发现新的感兴趣的资源(也许此用户还喜欢韩红的歌、蔡依林的歌等等)，推荐结果的面有点窄。

8.协同过滤（Collaborative Filtering）技术，是推荐系统中应用最为广泛的技术之一，它基于一组兴趣相同的用户进行推荐。协同过滤基于这样的假设：为用户找到他真正感兴趣的内容的好方法是，首先找他与他兴趣相似的用户，然后将这些用户感兴趣的内容推荐给此用户。这个基本思想是不是和现在颇为流行的“口碑传播(word-of-mouth)”有点儿 类似？其实这个非常直观，相信大家都有体会，在现实生活里，对自己最有效的信息，往往是来自于朋友们的推荐。Via

我的理解，比如用户a听过歌曲传奇，用户b也听过歌曲传奇，同时用户b也听过歌曲天路，则将天路推荐给用户a，没准用户a喜欢这首歌。

9.三种推荐方式
当我们知道自己要什么的时候，我们要做的是“Search”，比如我喜欢易中天的《品三国》，我可以 google一下，看看它会给我些什么不一样的东西。这个时候，我的目的很明确，Search 围绕我的目的，可以作很多。但更多的时候，我其实并不是明确地知道自己想要什么，我只是无聊，我不知道应该 Search 什么，我就是想随便“翻翻”。这个“翻翻”就是 Alex 文章里面说到的 “Browse”。Alex 提到了很重要的一点，在 “Browse” 的状态下，用户“需要一些建议”（open to suggestions）。这正是需要 Recommender Systems 发挥作用的时候！

Alex 总结了 3 种推荐模式，它完全是从应用的角度划分的，但基本是可以和我之前提到的学术界的 3 种划分相对应的。

1. 个人化推荐（personalized recommendation）—— 基于个人以前的行为模式进行推荐。
2. 社会化推荐（social recommendation）—— 基于和你相似用户以前的行为模式进行推荐。
3. 项推荐（item recommendation）—— 基于项本身进行推荐。

当然还有这 3 种混合模式的推荐。而且通常下，一个好的推荐系统，必然也是多种推荐方法相混合。觉得推荐模式的是数据！我们不讨论 Alex 的划分。他分析了 3 个非常成功的案例：Amazon、Pandora和 Del.icio.us。

Amazon 是当之无愧的“推荐之王（King of recommendation）”，无论是从推荐的实际效果还是从对推荐的重视程度上来看，都很难再找出一个能和 Amazon 比肩的应用。“据说（rumored）” Amazon 30% 的销售是依靠推荐带来的！Amazon 自然是根据需要选择了不同的推荐方法，Alex 的分析基本正确。Via

我的理解：
1.个人化推荐，比如我在某音乐网站听过王菲、张信哲、孙燕姿、梁静茹、齐秦的歌曲，则推荐结果中应该出现的是此5个歌手的歌曲或与此5个歌手风格类似的歌曲。
2.不知道是不是基于用户的协同过滤算法？
3.不知道是不是基于Item的协同过滤算法？

10.推荐引擎的价值

The Art, Science and Business of Recommendation Engines清晰地解释了推荐引擎的价值——是在线企业差异化竞争的利器。

原文指出用户上网行为分成两类：搜索和浏览。当消费者清楚地知道自己要找什么商品时，他的上网行为是搜索；如果用户并不清楚要找什么，只是逛一逛，此时他是在浏览，这是商家抓住消费者的有利时机，因为他并没有决定要买什么，他愿意听多种建议，推荐该粉墨登场了。

根据The Art, Science and Business of Recommendation Engines，推荐方式分成四类：

• 个性化推荐（Personalized recommendation），根据某个人过去的消费行为推荐商品。
• 社会化推荐（Social recommendation），根据类似的消费者的过去的消费行为推荐商品。当前社交网络(SNS)正被热炒，提高用户注册量、增加用户活跃程度是 SNS发展的第一阶段，这个阶段也许即将结束了，下一个阶段是挖掘用户行为数据和社交关系图谱，用户在SNS系统中的活动数据是一个宝库，如果利用合适的 算法进行挖掘，社会化推荐就更有效了。
• 物品推荐（Item recommendation），根据物品（商品）的特性进行推荐
• 上述三种方式的结合

The Art, Science and Business of Recommendation Engines以使用Amazon的体验为例详细讲解了上述四类推荐的案例。Via

我的理解：

1.个性化推荐，与9中是一样的。
2.社会化推荐，此处的社会化推荐与9里面的社会化推荐的解释不太一样，感觉此处的社会化推荐更加合理一些。

3.物品推荐，应该就是基于Item的协同过滤。

11.

基于内容和基于协同过滤两种方式的区别

无论从用户还是服务提供者的角度出发，这两种推荐方式都有各自明显的优劣。如果采用“基于内容的过滤”，那么在完成内容和用户互相匹配的过程中，就可能出现“越读越窄”、“越听越窄”、“越看越窄”的问题，提供的内容完全与用户兴趣点相吻合，而没有发散。

“协同过滤”在很大程度上避免了这个问题，但是他需要用户达到一定数量级之后才能发挥出网站创建者预想的效果，这种“网络效应”使得同一市场上的后来者很难找到切入的机会。而用户一旦不能得到“好处”，可能迅速离去，而来不及提“利他”的后话。

 

基于Amazon研究

据称，Amazon 有35%的页面销售源自于她的推荐引擎。

Amazon的推荐引擎，是一个需要用户一定参与的系统，用户的输入将对推荐的内容起到指导作用；如果指导有方，则会提供更符合个人品味的推荐。

她会记录你已在Amazon购买的历史、你最近的浏览历史（根据活跃度调整，可拒绝此类跟踪），并需要主动告知引擎你对某些商品的打分（此打分不同于评价，只用于推荐引擎、且对他人不可见），和你已拥有的商品（用于排除这个推荐）。根据这些数据来做出判断

另外，Amazon的推荐引擎并不只有这一块内容，在浏览、tag、商品页面都有很多推荐，可以说推荐无处不在。从她的功能点来看，似乎可以分为三块内容：以人为着眼点、以物为着眼点以购物过程为着眼点。同时还采用了跨类推荐，对不同类的按热度排列。

基于豆瓣的研究

大家可以看这里http://www.slideshare.net/clickstone/ss-2756065。 

基于八音盒的研究

八宝盒（www.8box.cn）是一个基于音乐分享及偏好而建立起来的SNS服务, 利用多年积累研发的推荐引擎，8box能帮你找到可能喜欢的音乐，帮你分析出哪些用户是你的音乐“同好”。八音盒通过你推荐、试听、打分、评论音乐的过程，学习你的口味，并依此帮助过滤出你喜欢的音乐。发现音乐的最好途径是通过你的同好。八音盒能够根据你的口味，推荐相似的用户给你。应该说“个性化推荐引擎 –IntelliProvider”是音乐八音盒的技术基石。

简单的来说，8box推荐音乐的依据有三种：

1.依靠音乐本身的属性信息判断音乐的相关性，做出推荐。

2.依靠听众对这个音乐的评价和反映来推断音乐的相关性，做出推荐。

3.依靠分析用户的行为，发掘出用户的音乐同好，从而做出推荐。

基于遗传学的推荐系统-潘朵拉（Pandora）

音乐染色体组项目的推出，目的在于把音乐解析成为最基本的基因组成。它的基本想法是：我们因为音乐的某些特性喜欢音乐－－那么为什么不能根据音乐的某些相似之处设计出一套推荐系统呢？这类推荐系统应该属于基于产品的推荐。但具有深刻创新意义的是，产品（音乐产品）的相似性，通过“基因”组成来衡量。

这种“即刻满足感”是很难抗拒的。因为pandora 了解音乐相似性背后的因素，它不需要了解用户的好恶，就可以把用户黏住。确实，pandora 需要把握用户的口味或记忆－－但这正是蕴藏在音乐本身的dna中了。当然pandora有时并不完美，会播放不对用户口味的音乐。但这很少发生。

基于标签的推荐系统-Del.icio.us

非常简明的推荐系统，它指基于一个基因－－那就是一个标签。 

Via

12.当当网的推荐算法

Item to Item
    Item based Personalized Recommendation
User to User
    User based Personalized Recommendation
Content to Content
    Content based matching
Association Rules
    Classical Data Mining algorithm
Social Recommendation
    Friends based Personalized Recommendation

参考：
http://www.baidu.com/s?wd=%CD%C6%BC%F6%CF%B5%CD%B3%A1%A1%CB%E3%B7%A8

转载自:

http://iamcaihuafeng.blog.sohu.com/146684978.html

体验新版博客