浅谈推荐系统

Kaka Chen 2014-03-11

实习君，能不能快点收了我

前言，之前看了july君的推荐引擎算法学习导论与本科室友懒惰啊我君在博客园的文章自己动手写推荐系统后，也读了一部分有关推荐系统的资料和书籍，仅以此博文当做自己对这段时间学习的记录和温习，如有写的不妥之处欢迎批评纠正。因为自己也刚刚是个半吊子的学生，所以只能先梳理一些浅显易懂的内容，具体的实践和推导之后再写。

Reading Recommend

  • Recommender Systems Handbook：水平较高，专题性较强，可惜只找到英文版，建议有一定基础后再啃。~博主暂时还只能处于看Contents的阶段~
  • 集体智慧编程：讲究挖掘和分析web上的数据，Python讲解，入门宝典1.0，适合博主这样的菜比
  • 推荐系统实践：最大优点就是短小精悍，比集体智慧编程更进一步，小白最爱2.0
  • Mahout实战：偏重实践，使用mahout框架，难度较之前基本要大

Brief Content

所谓推荐系统，从字面就能窥得一二，就是“用来做推荐的一组算法或者一个成型的系统”。为什么要推荐？我自己要喜欢什么自己还不知道吗？对，有时候还真不知道，尤其是在数据量巨大的情况下，在一些情况下，用户个人通过搜索引擎来精确定位某一个item或者subject已经是非常困难了，因为很多用户甚至都不知道那些符合自己要求或者兴趣的item的存在，这也是推荐系统（Recommender System，RS）存在的意义。

其中，现在常见的RS可以分成三类：

  • 基于人：根据不同类型的人群进行推荐，颗粒较粗。先将待推荐人的特征记录建模，与已有模型进行比较，选择现有的相似性大的个体感兴趣的item进行推荐。优点是不需要历史数据，没有冷启动问题，同时也不依赖于物品属性。缺点是算法比较粗暴，真实的应用效果一般。

  • 基于资源：这次把建模的重点放在item上，大致与第一个相同，选择一个或几个相似度高的item，然后推荐给对那些item感兴趣的人。这个就需要有item的历史记录，有冷启动问题，而且物品属性很难全部罗列，比较片面。但是可以更好地对用户兴趣建模，精度可以提高。

  • 协同过滤（Collaborative Filtering, CF）：这个是现在用的最多的一类，也是技术要求最高，最值得研究的一类。这一类中还能细分为基于用户的CF，基于项目的CF和基于模型的CF三种，更偏重于细颗粒的特征。

Collaborative Filtering

概括言之，协同过滤是对一大群人和一大堆待推荐的item进行搜索，将人分成品味相近的若干组，将item分为特征相似的若干组，再将这些组相互组合和排名，行成一份item-to-people的推荐表。整个过程分为数据搜集，相似用户和item分类，进行推荐的三步走。

  1. 数据搜集：一般有两种手段，可以是在线读取，如某个用户做了一个对某项item感兴趣的操作，推荐系统就记录一下，还有一种是将大量log文件存在db上，定期读取。读取之后最好还会做一个过滤清洗操作，把一些操作数低于阀值的用户和item的记录去除，或者可以添加一个black/white-list，自定义对一些恶意操作或者无意义操作进行清洗。
  2. 相似用户和item分类：最简单而常用的相似度的计算一般有两种，欧几里得距离和皮尔逊相关度。另外还有Cosine相似度和Tanimoto系数等。
    • 欧式距离：即常见的二维空间两点距离，相似度取其与1的和的倒数，所以其取值范围为0到1，离的越近就认为二者越相似，一般如果有多个共同标记内容，就把这些item的欧式距离求和再去做倒数，但是我在读到这种做法有个问题，就是如果我们不管阀值的情况下有A，B，C三个人，A只对前三个item评分，分别为{2,6,5}，B对前五个item评分，分别为{3,7,7,4,5}，C也对前五个item评分，为{2,6,5,4,4}，如果用简单的欧式距离计算，得到A和B的相似度是1/(1+sqrt(pow(2-3)+pow(6-7)+pow(5-7)))=0.33333，而B和C的相似度是1/(1+sqrt(pow(3-2)+pow(7-6)+pow(7-5)+pow(4-4)+pow(5-4)))=0.3090，不如A与B，但是如果把图像画出来会发现，直观上还是C与B之间的曲线相似度更高，如果之后B和C有更多拟合程度很高的评分出现，这种现象还会更明显，所以欧式计算法对于评分item数量不同的若干人之间的比较效果不好，我不知道有没有深入的解决这问题的办法，回头问一下懒惰啊我。

    • 皮尔逊相关度：可能就是从这个角度想到，皮尔逊相关度就是从曲线拟合度下手，虽然比欧式距离复杂，但是效果好很多。一般会找到两位评论者共同评价过的物品，然后计算两者评分总和和平方和以及评分的乘积之和，最后求得皮尔逊相关系数。计算方法类似方差计算。返回值的在-1和1之间，其中1则表示对每样物品都有完全一样的评价

    ，

    • 余弦相似度Cosine-based Similarity：将两人对某一组共n个item的评分看做一个n维的向量，向量的内积余弦值即为相似度。
    • Tanimoto 系数：类似内积计算的另一种办法。
  3. 进行推荐：在计算完相似度之后，就可以进行推荐操作了，其中又可以以用户或者item分别作为推荐的主要依据。前者是基于用户根据不同item的评分，找到相邻的k个用户，预测当前用户没有的item进行推荐。

后者是找到相似度最近的k个物品，根据用户的历史偏好，预测当前用户还没有偏好的item进行推荐。

Data Clustering

聚类是一种典型的无监督学习方法，没有标准答案，计算目的是将一个巨大冗杂的数据集分割成若干个簇cluster，其中同一个簇内的元素相关程度高，不同簇之间的元素相关程度低。在《集体智慧编程》一书中，介绍的是用分级聚类来构建聚类的树状图，思路就是通过特征向量之间的距离为相似值依据，将最近的两个族群合并为一个新的族群并且以此类推，两两族群合并形成一个层次结构。

一般来说，提到聚类了就不能不提K-means算法了，其思路即在于找到某一个自然聚类的中心，将各个群组之间的均方误差降到最小。大致步骤如下：

  1. 如果我们要把整个数据集分成两个cluster，那么先随机的选择两个点，作为中心位置；
  2. 将数据集中所有的点都依次分配给距离较近的那个“中心点”，得到两个簇；
  3. 根据现有的分布情况，重新计算每个簇的中心位置；
  4. 然后根据新得到的中心点，把1~3步骤再过一遍，直到得到得到结果与上一次相同或者低于某一个阀值

除了K-means外，Canopy聚类算法也很常见，的基本原则是：首先应用成本低的近似的距离计算方法高效的将数据分为多个组，这里称为一个Canopy，我们姑且将它翻译为“华盖”，Canopy 之间可以有重叠的部分；然后采用严格的距离计算方式准确的计算在同一Canopy中的点，将他们分配与最合适的簇中。Canopy 聚类算法经常用于 K 均值聚类算法的预处理，用来找合适的k值和簇中心。

Classification

分类在此的作用就在于要把新获得的item归类到哪一个已有类别的item中，常用的办法是决策树Decision Tree。

其中决策树更像是一个游戏地图，到了某个npc（树节点）处可以和他对话，你的不同的选择会决定你接下去会遇到哪个npc。所以说不同于贝叶斯算法，决策树的构造过程不依赖领域知识，它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。 构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。分裂属性分为三种不同的情况：

1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。

2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。

3、属性是连续值。此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。

构造决策树的关键性内容是进行属性选择度量，属性选择度量是一种选择分裂准则，是将给定的类标记的训练集合的数据划分D“最好”地分成个体类的启发式方法，它决定了拓扑结构及分裂点split_point的选择。属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。常用的建树方法比如ID3，之后祥讲，在此不涉及了。由于决策树的白箱规则，所以可以清晰地看到每个流程的行为，其又是非参数的，可以应付任何连续和类别变量，所以真正使用的时候，很多人都把决策树当做最好的分类算法。

Else Stuff

其实除了上述一些内容外，一个合格的推荐系统还有很多组成部分，比如要对结果做优化，对item可以做搜索，还可以做一些规则的增加比如广告插入，anti-Spam等，因为博主晚上写这篇博客的时候接到了一个公司电面，结果被吐槽了一通，于是只能继续灰溜溜看Java基础去了，其余的内容之后有空了慢慢补充。