[rec] 推荐系统总结

Sep 8, 2016   #rec  #algorithm  #survey 

本文是对推荐系统相关知识的一个梳理和总结。主要是参考阿里的一篇技术分享ppt。

推荐系统的核心问题是如何评估一个用户(user)对一个物品(item)的评分(喜欢程度)。

场景和指标

推荐系统主要用来解决信息过量负载(information overload)的问题，可以应用多种场景中。如:

音乐，电影

电子商务中商品推荐

个性化阅读

社交好友推荐、朋友圈推荐

基于位置的服务推荐

评价标准：

名称 作用
用户满意度(user satisfaction) 调研或用户反馈；点击率、转化率等
准确率(Accuracy) precision/recall/F-score
覆盖率(Coverage) 长尾分布，尾部物品和用户
多样性(Diversity) 两两之间不相似
新颖性(Novelty) 没听过的物品
惊喜性(Serendipity) ？
用户信任度(Trust)/可解释性(explanation) 推荐理由
鲁棒性/健壮性(Robustness) 哈利波特现象；抗攻击、反作弊
实时性(Real-time/online) 新加入的物品；新的用户行为(实时意图)
商业目标(business target) 一个用户带来多少盈利

影响推荐效果的因素：

  • 用户交互界面(User Interface)（用户感知）

  • 数据（收集and处理）

  • 领域知识（产品定位）

  • 算法迭代

非个性化推荐：热度排行(Popularity)

排行榜算法主要分为：

单一维度的投票；多个维度的综合打分；考虑时间因素(引入衰减权重，如半衰期、冷却定律)；考虑反馈信息(Reddit)；考虑置信度(威尔逊区间)；防止马太效应(MBA)。

这个方法容易实现，可以解决新用户的冷启动问题。但无法对用户做出个性化推荐。通常情况下，可以先对新用户做热度排行推荐，然后根据用户的互动历史，做个性化推荐。

协同过滤(Collaborative Filtering)

它的来源很简单，即朋友之间会互相推荐自己喜爱的产品。基本组成元素有：评分矩阵和相似度度量。

主要分为两大类：

  • Memory-based(neighborhood-based)方法：Item-based/User-based CF

  • Model-based方法：频繁项挖掘/聚类/分类/回归/矩阵分解/RBM/图模型

User-based

计算目标用户的(前k个)相似用户(相似度度量：Pearson,Jaccard,cosine)

找出相似用户喜欢的物品，并预测目标用户对这些物品的评分(knn, regression)

过滤掉目标用户已经消费过的物品

将剩余物品按照预测评分排序，返回top-N物品

Item-based

计算item之间的两两相似性

假设预测用户对item的评分，首先找出用户评分过的物品，根据它们与item的相似度预测用户的的评分

选取用户评分最高的前N个商品进行推荐。

问题1： 比较user-based和item-based？

Item之间的相似性是静态稳定的；而user之间的相似性是动态复杂的。
user-based: 可以帮助用户发现新商品，带来惊喜性。但需要复杂的在线计算，而且无法处理新用户问题。
item-based: 准确性好，便于离线计算；但推荐缺乏多样性。

问题2：协同过滤的优缺点？

优点：模型通用性好，实现简单。
缺点：冷启动问题，数据稀疏性；假定“过去的行为决定现在”，没有考虑具体情景的差异；热门倾向性(Popularity Bias)，很难推荐出小众偏好。

关联规则

基于物品之间的共现性挖掘频繁项，应用场景为：买了又买，看了又看。主要有A-priori和FP-growth两种算法。

支持度：\(s(X,Y) = \frac{包含X,Y的记录数}{总记录数}\)

置信度：\(c(X,Y) = \frac{包含X,Y的记录数}{包含X的记录数}\)

关联规则实现简单，通用性较强，适合商品搭配场景； 在相似商品上的推荐效果往往不如协同过滤好； 注意在变量间关联的解释上，由于一些隐含因素的影响，可能得出完全相反的结论(辛普森悖论)。

ps: 辛普森悖论，两组数据分别讨论时满足某种性质，一旦合并考虑，却可能导致相反的结论。主要原因是数据的不同分组之间基数差异很大（通常一个组相对于其他组来说数量占绝对优势）。一个结论：分析数据时合理地将数据分组很重要。

聚类(Clustering)

可以对用户按爱好分群，商品按相似度聚类。常用的算法有：

  • k-means, 层次聚类

  • Louvain, 基于密度的聚类方法

聚类可以一定程度上解决数据稀疏性问题，但精准度往往不如协同过滤好。

分类/回归

它的基本思想是把评分预测看作一个多分类(回归)问题。常用的分类器有LR,Navie Bayes，把item的特征向量作为模型的输入。

比较通用，可以和其他方法组合，提高预测的准确性；需要大量训练数据，防止过拟合现象。

SVD

它的原理是将(用户,物品)的评分矩阵R，分解成三个矩阵U,S,V。SVD本身要求矩阵必须是稠密矩阵，而评分矩阵非常稀疏；此外，SVD的计算复杂度很高。

于是，就出现了关于SVD的一系列变形，如FunkSVD,BiasSVD,SVD++。具体可参见开源算法包svdfeture。

Item的向量化

向量化的目的是将Item进行知识、概念层次上的表达。常用方法有pLSA,LDA,Word2Vec。

向量化时大多基于行为数据，行为少的item向量化效果不好。

玻尔兹曼机

Boltzmann机：两层神经网络(无输出层)；对称、全连接；每个神经元有0/1(激活/未激活)两种状态，某个时刻的状态是随机的，由一定概率确定。

受限Boltzmann机：受限，层内无连接。

如何对(user,item)进行建模？一个用户一个RBM，共享隐层，权重W和偏置b。

图模型

多用于社交网络中人与人的关系挖掘。方法有SimRank,SimRank++,Markov模型。

借助图的结构的传导性，可以发现协同过滤发现不了的弱相似性，给推荐带来一定的惊喜性。但该模型仍面临数据稀疏性和冷启动问题。

基于内容(Content-based)

内容包括：文本描述（通常用NLP技术挖掘关键词）、Item属性(如电影的主题，职位的行业)、Item特征(如语音信号表示、图像向量表示)

基本组成：item特征向量(如文本的TF-IDF向量)，用户profile向量(根据用户偏好的items来提取)、匹配分(cosine,分类/回归模型)

方面 描述
优点 能够推荐出用户独有的小众偏好
可以一定程度解决数据稀疏问题和item冷启动问题
具有很好的解释性
缺点 如何提取出有意义的特征
很难将不同item的特征组合在一起(邻域思想)
惊喜性
依赖用户profile的准确性

混合方法(Hybrid Approaches)

通常比单个算法好，需要在不同算法之间、理论效果和实际可行性之间权衡。

方法 描述
weighted 加权
switching 切换，确定一个合理的跳进
Mixed 混合
feature combination 特征组合，不同特征组合在一起
feature augmentation 特征扩展，一个模型的输出作为另一个的特征
cascade 级联，粗排 -> 精排

一些新进展

Learning to rank

将排序看做一个ML问题，评价准则为NDCG(normalized discounted cumulative gain)或MRR(mean reciprocal rank)。算法分为三类：Pointwise, Pairwise, Listwise。

页面整体优化(Page Optimization)

关于用户注意力建模的一篇文章Modeling User Attention and Interaction on the Web。

情景推荐(Context-aware)

针对不同推荐场景，情景也有所不同。看电影，是周末还是工作日？订餐，餐厅距离？网购，用户心情？母婴：孩子年龄？

算法主要有张量分解(Tensor Factorization)，分解机(Factorization Machine)。其中后者的效果更好。

深度学习

主要用到的有卷积神经网络(CNN)和循环神经网络(RNN)。

参考链接

常用推荐算法

百分点亿级个性化推荐系统的发展历程和实践架构