推荐系统-近邻推荐
  • Jul 12, 2019
  • 8 minutes read

协同过滤

协同过滤重点在于协同，也就是群体互帮互助，互相支持是集体智慧的体现，协同过滤主要依赖用户物品的关系矩阵。通常划分为两类：

  1. 基于记忆的协同过滤
    1. 基于用户的协同过滤
    2. 基于物品的协同过滤
  2. 基于模型的协同过滤

基于用户的协同过滤

User-Based, User to User.

基于用户的协同过滤首先计算相似用户，然后再根据相似用户的洗好推荐物品。

这也是用户聚类的过程，把用户按照兴趣口味聚类成不同的群体，给用户产生的推荐就来自这个群体的平均值。

原理

  1. 准备用户向量。

    • 理论上，从用户关系矩阵中可以给每一个用户得到一个向量。
    • 该向量的维度就是物品的个数。
    • 用户消费过的物品的向量位置为1，反之为0，简单的布尔值。
    • 该向量是一个稀疏向量。

  2. 用每一个用户的向量，两两计算用户之间的相似度，设定一个相似度的阈值或者设定一个最大数量，为每个用户保留与其最相似的用户。

  3. 为每一个用户产生推荐结果。 把与他“臭味相投”的用户们喜欢过的物品汇总起来，去掉用户自己已经消费过的物品，剩下的排序输出就是推荐结果。具体的汇总方式如下：

$$ P_{u,i} = \frac{\sum_{j}^{n} sim_{u,j}*R_{j,i}} {\sum_{j}^{n} sim_{u,j}} $$

整个公式代表的就是相似用户们的态度加权平均值。，等号左边就是计算一个物品i和一个用户u的匹配分数，等号右边分母是把和用户u相似的n个用户的相似度加起来，分子是把这n个用户各自对物品i的态度，按照相似度加权求和。

态度取值最简单就是0，1布尔值，1表示喜欢，0表示没有；如果是评分，可以是0到5的取值。

构造矩阵

在做协同过滤计算时，所用矩阵是稀疏的，很多矩阵元素为0不用存。两种典型的稀疏矩阵存储格式：

  1. CSR：比较复杂，是一个整体编码方式，由数值、列号和行偏移共同编码。
  2. COO：比较简单，每个元素用一个三元组表示（行号、列号、数值）， 只存储有值的元素，缺失值不存储。

相似度计算

如果向量太长，都需要遍历向量计算，循环实现的话时间复杂度太高，因此需要降低相似度计算复杂度，通常主要有：

  1. 对向量采样计算。即降采样100维到10维，然后计算相似度，由Twitter提出，叫DIMSUM算法，已经在Spark中实现。
  2. 向量化计算。避免使用循环实现向量计算，而是转换成向量直接计算，如Python的Numpy。

其次，如果用户量很大，两两之间的计算代价就很大，主要有两个办法来解决:

  1. 将相似度计算拆成Map Reduce任务，将原始矩阵Map成： 键是用户对，值为两个用户对同一个物品的评分之积， Reduce阶段对这些乘积再求和，Map Reduce任务结束后再对这些值归一化。
  2. 不用基于用户的协同过滤。

如果数据量不大，低于100万个，而且矩阵稀疏的话，很多单机版本的工具如KGraph, GraphCHI更快。

推荐计算

直接为每一个用户计算每一个物品的推荐分数是不能接受的，计算次数是矩阵的所有元素个数。因此借助上面计算用户与物品的匹配度公式可以看出：

  1. 只有相似用户喜欢过的物品需要计算。
  2. 把计算过程拆成Map Reduce任务。

一些改进

对于基于用户的协同过滤的常见改进方法主要集中在用户对物品的喜欢程度上：

  1. 惩罚对热门物品的喜欢程度。因为热门得到东西很难反映出用户的真实兴趣，可能是盲目从众、无聊点击的情形，这是群体行为常见特点。
  2. 增加喜欢程度的时间衰减。一般使用一个负指数函数，时间越久，越不感兴趣。

应用场景

基于用户的协同过滤有两个产出：

  1. 相似用户列表
  2. 基于用户的推荐结果。

因此，我们不仅仅可以推荐物品，还可以推荐相似的用户。

基于物品的协同过滤

Item-Based. 首先计算相似的物品，然后再根据用户消费过、或者正在消费的物品为其推荐相似的。

原理

  1. 构建用户物品的关系矩阵，矩阵元素可以是用户的消费行为或者消费后的评价等。
  2. 如果矩阵行代表物品，列代表用户的话，就两两计算行向量之间的相似度，得到物品相似度矩阵，行和列都是物品。
  3. 产生推荐结果，根据推荐场景不同，有两种产生结果的形式：。
    1. 为某一个物品推荐相关物品。
    2. 在个人首页产生类似“猜你喜欢”的推荐结果。

计算物品相似度

从用户物品关系矩阵中得到的物品向量是：

  1. 一个稀疏向量。
  2. 向量的维度是用户，一个用户代表向量的一维，这个向量的总共维度是总用户数量。
  3. 向量各个维度的取值是用户对这个物品的消费结果。
  4. 没有消费过就是0。

计算余弦相似度，分母是计算两个物品向量的长度，求元素值的平方和再开方。分子是两个向量的点积，相同位置的元素值相乘再求和。相似度为1，对应角度为0，相似度为0，对应角度为90。公式如下：

$$ sim(i,j) = \frac{\sum_{k=1}^{n} R_{ik} * R_{jk}}{\sqrt{\sum_{k=1}^{n}R_{ik}^2} \sqrt{\sum_{j=1}^{n}R_{jk}^2}} $$

由于是稀疏向量，大部分为0，求和时不需要计算，点积时只需要计算两个物品的公共用户就行。

一些改进

  1. 物品中心化。把矩阵中的元素，减去对应物品分数的均值（行的均值），可以降低物品中铁杆粉丝群体的非理性因素，如一个明星的电影，粉丝集体打分高。
  2. 用户中心化。把矩阵中的元素，减去对应用户分数的均值（列的均值），先计算每一个用户的评分均值，然后把他打过的所有分数都减去这个均值，将每个人的个人标准统一，目的是在一定程度上仅仅保留偏好，去掉主观成分。

推荐计算

基于物品的协同过滤有两种应用场景：

  1. TopK推荐，如”猜你喜欢“。 当用户访问首页时， 汇总和“用户已经消费过的物品相似”的物品，按照汇总后分数从高到低推出，汇总公式： $$ R_{ui} = \frac{\sum_{j=1}^{m} sim(i,j) * R_{uj}}{\sum_{j=1}^{m}sim(i,j)} $$ 遍历用户u评分过的所有物品m个，而不是所有存在的物品，每一个物品和待计算物品i的相似度乘以用户的评分，加权求和后，除以所有这些相似度总和，得到一个加权平均评分，作为用户u对物品i的分数预测。 这个过程离线完成，去掉用户已经消费过的，保留分数最高额k个结果存储，当用户访问首页时，直接查询出来即可。
  2. 相关推荐。不需要提前合并计算，当用户访问一个物品的详情页面时，或者完成一个物品消费的结果时，直接获取这个物品的相似物品推荐即可。即通常的“看了又看”或者“买了又买”的推荐结果。
Slope One 算法

经典的基于物品推荐，相似度计算无法实时更新，整个过程都是离线计算，且相似度计算没有考虑相似度的置信问题。

Slope One算法针对这些问题，只能用于评分矩阵，不适用于行为矩阵。Slope One算法计算的不是物品之间的相似度，而是计算的物品之间的距离，相似度的反面。

协同过滤中的相似度计算方法

推荐系统中，推荐算法分为两个门派：

  1. 机器学习门派
  2. 相似度门派

相似度的本质

近邻推荐指任意高维空间下的近邻，当用户和物品的特征维度都很高时，要找到用户隔壁的邻居，并不是那么直观。近邻推荐的核心就是相似度计算方法的选择，由于近邻推荐并没有采用最优化思路，所以效果通常取决于矩阵的量化方式和相似度的选择。

与相似度配套的就是距离，两者都是用来量化两个向量在高维空间中的亲疏程度的，是硬币的两面。

相似度门派有一个潜在假设：如果两个物品很相似，也就是距离很近，那么这两个物体就很容易产生一样的动作。

常用相似度计算方法

相似度计算对象是向量，或者叫做高维空间下的坐标，表示这个向量的数值有两种：

  1. 实数值。
  2. 布尔值，0 or 1。

欧式距离

欧式距离是一个欧式空间下度量距离的方法，不适合布尔向量之间。假如在同一个空间下表示的两个n维向量p和q,它们之间的欧式距离计算公式如下：

$$ E(p,q)= \sqrt{\sum_{i=1}^{n}(p_i - q_i)^2} $$

每一个坐标上的取值相减，然后求平方和，最后输出方根。

欧式距离值非负，最大为正无穷，但是通常相似度度娘结果希望是[-1,1]或者[0,1]之间，因此通常需要二次转化，常用距离加1之后取倒数，能把范围转换为0到1的相似度：

$$ \frac{1}{1+E(p,q)} $$

欧式距离度量的是空间中两个点的绝对差异， 适用于分析用户能力模型之间的差异，比如消费能力、贡献内容的能力等。

余弦相似度

度量两个向量之间的夹角，用夹角的余弦值来度量。当两个向量的夹角为0度时，余弦值为1，当夹角为90度时，余弦值为0，为180度时，余弦值为-1，它与向量的长度无关，因为会对向量长度进行归一化。公式如下：

$$ cos(p,q) = \frac{\sum_{i}{p_i q_i}}{\sqrt{\sum_{i} p_i^2} \sqrt{\sum_{i}q_i^2} } $$

背后潜在的思想是：两个向量，只要方向一致，无论程度强弱，都可以视为“相似”。

余弦相似度对绝对值不敏感，有些情况下有问题，改进方法是调整的余弦相似度(Adjusted Cosine Similarity)。就是先计算向量每个维度上的均值，然后每个向量在各个维度上都减去均值后，再计算余弦相似度。

皮尔逊相关度

实际上也是一种余弦相似度，不过先对向量做了中心化，向量p和q各自减去向量的均值后，再计算余弦相似度，公式如下：

$$ R(p,q) = \frac{\sum_{i}^{n}{(p_i-\bar{p})) (q_i-\bar{q})}}{\sqrt{\sum_{i} (p_i-\bar{p})^2} \sqrt{\sum_{i}(q_i-\bar{q})^2} } $$

皮尔逊相关度计算结果范围[-1,1]，-1表示负相关，1表示正相关。实际上在度量两个随机变量是不是在同增同减，或者说变化趋势是否一致。

皮尔逊相关度不适合用作计算布尔值向量之间相关度，因为两个布尔向量对应两个0-1分布的随机变量，这样的随机变量变化只有有限两个取值，根本没有“变化趋势，高低起伏”一说。

杰卡德(Jaccard)相似度

杰卡德相似度是两个集合的交集元素个数在并集中所占的比例。计算方式：

  1. 分子是两个布尔向量做点积计算，得到的就是交集元素个数。
  2. 分母是两个布尔向量做或运算，再求元素和。

余弦相似度适用于评分数据，杰卡德相似度适合用于隐士反馈数据，如用户的收藏行为，计算用户之间的相似度。

本文是《推荐系统三十六式》的读书笔记，仅限个人学习，请勿用作商业用途，谢谢。

Note: Cover Picture

  • RS
    • Previous
    推荐系统-内容推荐
    Next
    推荐系统-矩阵分解