推荐算法review

    本文将按照作者学习的顺序，对推荐算法进行一个综述性的介绍，可能会有些跳跃性。一则供自己后续不时翻阅，二则分享给读者。传播知识是一件很快乐的事情。

    1. 基于相似度的方法（协同过滤）

    基于相似度的方法是一类最为成功的推荐算法的代表。其在学术上已被广泛研究，并且在电商领域广泛应用。该类方法又可以进一步分为两类：基于用户相似度的推荐算法和基于物品相似度的推荐算法。基于用户相似度的推荐算法的基本假设是：在之前的判断上更相似的用户倾向于在之后的判断上也更相似。因此，对于一个目标用户对某个商品的评分，可以通过同该用户相似的其他用户对该商品的评分来估计。不同于基于用户相似度的推荐算法，基于物品相似度的推荐算法，给用户推荐与该用户之前收集的物品，更相似的物品。有时候，来自不相似的用户或者负面评分的商品也可以在推荐算法中发挥重要的作用，特别是数据集比较稀疏的时候。

    基于用户相似度的推荐算法可以选取和该用户相似度大于某个阈值，或者最相似的前k个用户，其对物品评分的加权和作为该用户对物品评分的估计。通常为了消除用户评分的偏向性，例如有的用户偏向于评分高，有的用户偏向于评分低，会做一个移除均值的操作。

    基于物品相似度的推荐算法类似，选取该用户已评分物品中最相似的物品，加权求和。基于物品相似度的算法相比于基于用户相似度的算法，更加静态，因为物品之间的相似度随时间变化较小，这使得基于物品相似度的推荐算法可以离线计算，缩短推荐结果计算时间。Slope one算法是一个简单的基于物品相似度的算法。其主要思想是去预测用户评分过的商品{a1, a2, ...}和当前需要预测的商品b的评分之差。而商品a和商品b评分之差可以通过用户评分矩阵估计，最简单的方法便是将用户评分矩阵中，所有评价过商品a和b的用户评分之差，相加后再归一化。有了商品a和b评分之差的估计，则可以通过简单的加权操作，计算用户对商品b的评分。

    混合式协同过滤算法，同时考虑用户和物品相似度，从使用结果来看，混合式协同过滤不仅能够提高预测的精确度，对于稀疏数据集还具有更强的鲁棒性。

    在基于相似度的方法中，最关键的问题是如何度量用户或者物品之间的相似度。在有用户显式评分的情况，相似度可以采用某些相关性度量，例如pearson相关系数。在没有用户显式评分的情况下，相似度可以采用基于用户和商品二部图（bipartite graph）计算的相似度，也称为structural similarity。有文章发现基于用户商品二部图结构的相似度比皮尔逊相关系数，能产生更好的推荐结果，特别是在输入数据比较稀疏的情况。基于用户商品二部图结构的相似度可以细分为：基于节点的相似度、基于路径的相似度、基于随机游走的相似度。

    基于节点的相似度：最简单的基于节点的相似度计算，a和b的相似度是二部图中，a和b的公共邻居数量（Common Neighbor），记为CN。可以通俗的理解为：两个用户之间的相似度就是二者共同购买过的商品数量，两个商品之间的相似度即为购买过二者的用户数量。稍微复杂一些，可以考虑a和b在二部图中的度（degree）。例如：Jaccard系数。更精细一些，可以考虑a和b公共邻居的度，给度较大的邻居更低的权值。

    基于路径的相似度：其基本假设是节点a和b，如果有越多的路径相连，越相似。在二部图中，连通同类节点之间的路径长度只能是偶数。

    基于随机游走的相似度：通过在网络中执行随机游走，计算节点之间的相似度。平均往返时间，是从节点a随机游走到达b的平均步程，加上从节点b随机游走返回节点a的平均步程。节点a和b之间的平均往返时间越小，认为节点a和b之间的相似度越大，节点a和b的相似度可以取为平均往返时间的倒数。

SimRank适用于在物品共同出现的拓扑图中，度量两个物品之间的相似度。其基本思想是：如果两个物品被相似的物品引用，那么这两个物品被认为相似。对于有向图中的节点v，I(v)和O(v)分别表示v的入度邻节点集合和出度邻节点集合。物品a和b的相似度可以用以下迭代公式表示：s(a,b)=C/(|I(a)|*|I(b)|)*SUMij[s(Ii(a),Ij(b))]。从迭代公式可以看出：SimRank在基于节点的相似度中公共邻居数量（CN）的基础上，进一步考虑了公共邻居之间可能的相似度。SimRank中相似度传播的方法，和图算法中置信传播、权值扩散思想都类似，就是通过不断迭代，由迭代公式以及0到1之间的衰减因子C，确保最终会收敛到我们期望获得的理想状态。

    相似度计算过程中，除了传统的用户商品交互关系和评分之外，还可以加入用户属性，例如年龄、性别、国籍、地理位置、职业等。也可以考虑商品内容信息，在文献中这也通常被称为基于内容的推荐，该类方法通过分析目标用户过去评估过的商品内容信息给出推荐结果，因此在基于内容的推荐中，推荐问题就是去搜索和目标用户喜欢的商品内容最相近的商品，在信息检索和文本挖掘中，最常用的文本特征是TF和IDF。由于协同滤波没有显式包括商品的特征信息，因此其面临稀疏性和冷启动问题，然而基于内容的推荐却没有考虑用户之间的喜好相似度。多种基于内容的推荐和协同滤波的混合算法被提出，其可以主要分为以下几类：单独基于内容推荐和协同滤波，然后结合二者的推荐结果；将内容特征加入协同滤波模型中；将协同滤波的特征加入基于内容的推荐模型中；发展一个更好的结合内容特征和协同滤波模型的统一模型。然而基于内容的推荐，只有在商品具有丰富的可提取内容信息时，才能有效运用，例如推荐书籍、文章、书签，但是对于视频、音乐、图片，基于内容的推荐就不适用。也可以考虑标注信息，和传统的基于层次结构的分类不同，标注系统允许用户自由的添加关键词，来管理他们的物品集合，这些关键词通常被称为标注，标签。通过标注信息，算法可以很容易的通过标注向量，计算用户和物品的相似度。为了减弱垃圾信息的影响，增强个性化的用户偏好，通常会使用加权的方法去改变标注的重要程度。

    2. 基于降维的推荐算法

    降维的目的是减少相关数据数量的同时，保留主要的信息内容。其通常应用在数据挖掘、机器学习、聚类分析中。大多数的降维方法涉及利用隐式变量的特征提取，隐式变量用于描述数据共现的原因。在选择电影这个场景中，潜在的观众可能会考虑动作片、爱情片或者喜剧片，这些电影分类属性便是用户选择电影的隐式变量，这些隐式变量可以表示成一个向量。如果假设表示电影分类属性的隐式变量维度为K，那么利用降维的方法，用户和电影都可以表示成K维的向量。基于降维的方法特别适用于协同滤波，因此也被称为是基于模型的协同滤波。降维方法包括：奇值分解（SVD）、贝叶斯聚类、概率隐式语义分析（pLSA）、LDA。

转载于:https://my.oschina.net/jhone/blog/514309