推荐算法浅析

推荐系统估计是以后的一个大的方向，应用广泛，根据用户个性化地定制或自动推荐，提高用户体验。像亚马逊首页的商品推荐，以后的搜索推荐等等。最近听了一些讲座和分享，自己也学习了一下，下面做一点总结和分享。

一、推荐系统的分类

1、根据用户历史内容的推荐
现在大部分应用场景还是在用这种方式，像商品推荐根据用户的历史购买情况去做分析，以相似度来排序来进行推荐。

2、根据用户个人喜好的推荐
这种方法一般指通过将用户分为10多个大类(心理学)，在给用户推荐之前，首先确定用户的类别，然后得出用户的喜好(个人认为是根据一些统计学的手段，就像那些星座问题)给用户进行推荐。

二、推荐算法
以下主要介绍4种推荐算法以及他们的优势和劣势：
1、传统协同过滤
一个用户对应一个N维向量，N代表商品的绝对类目数量，向量里面的内容是：正的是购买的和正排序的商品；负的是正排序的商品。 为了补偿畅销的商品， 用向量去乘相反的频率，让不太出名的商品更相关一些。  但对绝大部分用户来说，这个向量是非常稀疏的。
这个算法是基于一部分非常相似的用户，利用余弦算出两个用户的相似度。同时可以从有多少相似的用户买过的商品去推荐商品。
复杂度：最坏的情况O(MN)，M为用户数，N为商品类目数； 但由于平均用户向量的稀疏性，复杂度趋于O(M+N)。
但是当用户和商品数据量超大时，这个算法将遇到严重的性能和可扩展问题。通过对用户随机取样或者排除很少有购买记录的用户来减少M；排除非常流行或者非常不流行的商品与减少N。或者根据商品类目、子分类来对商品空间进行分区处理。 这些都是通过聚集、考虑重要因素分析去减少维度的方法。  但是这些也同时降低了推荐质量。


2、簇模型
也是为了去找相似的用户，通过把用户进行划分成许多段，把这个视为一个分类问题。
算法的目的：把用户分到一组相似用户的分段集合里面。

分段一般是通过使用一个聚集或者其他无监管的学习算法来创建，虽然有一些应用是通过人工地去决定分段。
使用相似矩阵，  因为如果在大型数据集上使用最优的聚集方法是不切实际的， 大多应用都使用多个贪心的分类方法。  从一个只有一个随机被先中的用户的集合开始，重复的通过已经存在的聚集去匹配新的用户，一般有一些条件去做新建或者合并已经存在的聚集。  对于大型数据集而言，取样和维度削减也是需要做的。
一旦算法决定了分段的情况，就会把用户的相似度计算成向量来概述每个分段，然后选出具有最高相似度的分段，对相应用户进行归类。一些算法也会把用户归类到不同的分段中去描述每个关系的力度。
簇模量比传统协同过滤有着更好的线上性能和可扩展性， 因为前者将需要比较的用户数量控制在一个小范围内，而不像后者在整个用户范围。 复杂而又昂贵的分簇计算放在线下去跑。但是推荐质量低。因为通过归类找出来的用户之间不是最巨有相似度的用户，导致推荐的商品也不是最相关的。  不过通过使用大量的细致的好的的归类去提高推荐质量是可行的。但是线上用户归类的代价与传统协同过滤找到相似的用户一样巨大。


3、基于搜索的方法
基于搜索或者基于内容的方法把推荐问题转化成搜索出相关的商品。考虑到用户的购买和喜欢的商品情况，这个算法通过一个搜索查询找出具有相同的关键字的商品。
如果用户有很少的购买量或喜好，这个方法的性能和可扩展性会很好。但是考虑到成千上万的购买量，在所以商品里面去搜索是不现实的。 所以这种算法需要使用数据集的子集或者摘要，但同时降低了推荐质量。总体来看，推荐质量相对而言是低了，搜索出的结果要么很概括，要么很狭窄。 而且这种方式不能帮用户找出他们相关的、有兴趣的新的商品。


4、商品对商品的协同过滤
与找相似用户不同，此方法通过用户的购买情况和喜好找出相似的商品。
为了找出与给定商品相似的匹配，算法使用了一个相似商品表，通过找出用户趋向于想买的商品。  我们构建出商品到商品的矩阵，用这样一种穷举法：

For each item in product catalog, I1
  For each customer C who purchased I1
   For each item I2 purchased by
     customer C
     Record that a customer purchased I1
     and I2
   For each item I2
     Compute the similarity between I1 and I2

此时的向量是商品向量，而不是用户向量

线下相似商品表的计算很费时间，最坏情况：O(N2M)，实际情况接近：O(MN) ——大部分用户有很少的购买。  对购买畅销商品的用户进行取样能以比较小的推荐质量代价来进一步地减少运行时间。


5、可扩展性比较

传统协同过滤：几乎不做线下计算，线上规模与用户、商品类目数量有关。算法对于大规模数据集不实用，除非采取取样、分区等方法来降低推荐质量。

簇模型：能执行大量线下计算，但推荐质量相对比较低。如果想提高质量，增加用户分段会让线上用户分段归类代价昂贵。

基于搜索方法：给关键字建索引可在线下做，但不能提供以用户兴趣的推荐。而且当用户有比较大的购买量的话可扩展性差。

商品到商品的协同过滤：创建昂贵的相似商品表在线下做，算法在线上的部分是在相似商品表里面去找出相似商品。算法规模与商品类目数量、用户数量无关。性能和推荐质量最好。

三、怎么去做推荐系统的一些想法
线下Hadoop云梯上做历史数据的存储和计算，周期性地更新和维护相似度表/矩阵，如果应用对实时性要求比较高，用的时候生成也来得及，毕竟item-to-item这种方式建相似度矩阵所用的时间也是最快的，再加上item分区这些补充手段，来达到目的。再考虑一些优化的话，如果用户的行为比较频繁，将这些表放缓存不太现实。


强大的标签系统——推荐引擎的一种实现
将一群用户或者一堆item打上一个标签，再根据业务条件去做标签间的逻辑运算，将筛选之后的结果索引到搜索引擎，最后通过搜索进行呈现。