抖音头条为什么这么火？揭秘推荐系统原理之协同过滤算法

上一篇文章简单介绍了推荐系统的基本原理和分类，本文着重介绍协同过滤的原理与实现~

协同过滤

协同过滤(collaborative filtering)通过利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户感兴趣的信息。

协同过滤算法最大限度的利用用户之间，或物品之间的相似相关性，而后基于这些信息的基础上实行推荐。比如说，你和你的某个好友都喜欢听音乐，而你们所喜欢的曲风都差不多，你的好友对于某一首歌曲的评价很高，而这首歌你还没有听过。那么，我是不是就能将这首歌推荐给你呢？

要实现协同过滤，需要以下3个**步骤**：

  1. 收集用户偏好
  2. 找到相似的用户或物品
  3. 计算推荐

协同过滤在使用过程中可能会遇到样本量太少导致的两个**常见问题**是：

  1. 稀疏性问题——因用户做出评价过少，导致算出的相关系数不准确
  2. 冷启动问题——因物品获得评价过少，导致无“权”进入推荐列表中

因此在对于新用户和新物品进行推荐时，使用一些更一般性的方法效果可能会更好。比如：

  • 给新用户推荐更多平均得分超高的电影；
  • 把新电影推荐给喜欢类似电影（如具有相同导演或演员）的人。

后面这种做法需要维护一个物品分类表，这个表既可以是基于物品元信息划分的，也可是通过聚类得到的。

协同过滤的分类

  1. 基于用户的推荐(通过共同口味与偏好找相似邻居用户，K-邻居算法，你朋友喜欢，你也可能喜欢)

  2. 基于项目的推荐(发现物品之间的相似度，推荐类似的物品，你喜欢物品A，C与A相似，可能也喜欢C)

  3. 基于模型的推荐(基于样本的用户喜好信息构造一个推荐模型，然后根据实时的用户喜好信息预测推荐)

收集用户偏好

用户行为 类型 特征 作用
评分 显式 整数量化值[0,n] 可以得到精确偏好
投票 显式 布尔量化值[0,1] 可以得到精确偏好
转发 显式 布尔量化值[0,1] 可以得到精确偏好
保存书签 显式 布尔量化值[0,1] 可以得到精确偏好
标记标签 显式 一些单词 需要进一步分析得到偏好
评论 显式 一些文字 需要进一步分析得到偏好
点击流 隐式 一组点击记录 需要进一步分析得到偏好
页面停留时间 隐式 一组时间信息 噪声偏大，不好利用
购买 隐式 布尔量化值[0,1] 可以得到精确偏好

收集到原始用户偏好数据后进行预处理：

  • 用户行为识别/组合

在一般应用中，我们提取的用户行为一般都多于一种，关于如何组合这些不同的用户行为，比如，可以将用户行为分为“查看”和“购买”等等，然后基于不同的行为，计算不同的用户 / 物品相似度。

类似于当当网或者京东给出的“购买了该图书的人还购买了 …”，“查看了图书的人还查看了 …”

  • 喜好程度加权

根据不同行为反映用户喜好的程度将它们进行加权，得到用户对于物品的总体喜好。

一般来说，显式的用户反馈比隐式的权值大，但比较稀疏，毕竟进行显示反馈的用户是少数；同时相对于“查看”，“购买”行为反映用户喜好的程度更大，但这也因应用而异。

  • 数据减噪和归一化。

  • 减噪：用户行为数据是用户在使用应用过程中产生的，它可能存在大量的噪音和用户的误操作，我们可以通过经典的数据挖掘算法过滤掉行为数据中的噪音，这样可以使我们的分析更加精确。

  • 归一化：如前面讲到的，在计算用户对物品的喜好程度时，可能需要对不同的行为数据进行加权。但可以想象，不同行为的数据取值可能相差很大，比如，用户的查看数据必然比购买数据大的多，如何将各个行为的数据统一在一个相同的取值范围中，从而使得加权求和得到的总体喜好更加精确，就需要我们进行归一化处理。最简单的归一化处理，就是将各类数据除以此类中的最大值，以保证归一化后的数据取值在 [0,1] 范围中。

  • 形成用户偏好矩阵

一般是二维矩阵，一维是用户列表，另一维是物品列表，值是用户对物品的偏好，一般是 [0,1] 或者 [-1, 1] 的浮点数值。

找到相似的用户或物品

找到相似的用户或物品：计算用户或物品的相似度，找到相似邻居。

相似度计算

User CF 和 Item CF 都依赖于相似度的计算，因为只有通过衡量用户之间或物品之间的相似度，才能找到用户的“邻居”，才能完成推荐。

相似度**可通过计算**欧式距离、皮尔逊相关系数、Cosine相似度、**Tanimoto相关系数**来衡量:

  • 欧几里德距离（Euclidean Distance）
d(x,y)=\sqrt{(∑(xi−yi)^2))}
sim(x,y)=\frac{1}{1+d(x,y)}
  • 皮尔逊相关系数（Pearson Correlation Coefficient）
p(x,y) =\frac{∑x_iy_i−n\overline{x}\overline{y}}{(n−1)S_xS_y} =\frac{n∑x_iy_i−∑x_i∑y_i}{\sqrt{n∑x_i^2−(∑x_i)^2}\sqrt{n∑y_i^2−(∑y_i)^2}}
  • Cosine相似度（Cosine Similarity）
T(x,y) =\frac{x⋅y}{∥x∥^2×∥y∥^2} =\frac{\sum{x_iy_i}}{\sqrt{\sum{x_i^2}}\sqrt{\sum{y_i^2}}}
  • Tanimoto系数（Tanimoto Coefficient）
T(x,y)=\frac{x⋅y}{∥x∥^2+∥y∥^2−x⋅y} =\frac{\sum{xiyi}}{\sqrt{∑x_i^2}+\sqrt{∑y_i^2}−∑x_iy_i}

相似邻居计算

计算出相似度后，可通过**固定数量的邻居**或**基于相似度门槛的邻居**来进行相似邻居的选定。

1. 固定数量的K个邻居

K-neighborhoods：意思很明确，就是按分数高低降序取K个。

用“最近”的K个用户或物品最为邻居。 如下图中的 A，假设要计算点 1 的 5- 邻居，那么根据点之间的距离，我们取最近的 5 个点，分别是点 2，点 3，点 4，点 7 和点 5。但很明显我们可以看出，这种方法对于孤立点的计算效果不好，因为要取固定个数的邻居，当它附近没有足够多比较相似的点，就被迫取一些不太相似的点作为邻居，这样就影响了邻居相似的程度，比如图 1 中，点 1 和点 5 其实并不是很相似。

2. 基于相似度门槛的邻居

Threshord-based neighborhood：取分数K分以上的作为邻居

与计算固定数量的邻居的原则不同，基于相似度门槛的邻居计算是对邻居的远近进行最大值的限制，落在以当前点为中心，距离为 K 的区域中的所有点都作为当前点的邻居，这种方法计算得到的邻居个数不确定，但相似度不会出现较大的误差。如下图中的 B，从点 1 出发，计算相似度在 K 内的邻居，得到点 2，点 3，点 4 和点 7，这种方法计算出的邻居的相似度程度比前一种优，尤其是对孤立点的处理。

Threshold-based neighborhoods要表现的就是“宁缺勿滥”，在数据稀疏的情况下效果是非常明显的。

根据计算相似度的主体不同，可将基于协同过滤的推荐算法分为**基于用户的协同过滤**（UserCF）和**基于物品的协同过滤**(ItemCF)，两者的比较如下表：

UserCF ItemCF
性能 适用于用户较少的场合，如果用户过多，计算用户相似度矩阵的代价变大 适用于物品数明显小于用户数的场合，如果物品很多，计算物品相似度矩阵的代价变大
领域 实效性要求高，用户个性化兴趣要求不高 长尾物品丰富，用户个性化需求强烈
实时性 用户有新行为，不一定需要推荐结果立即变化 用户有新行为，一定会导致推荐结果的实时变化
冷启动 在新用户对少的物品发生行为后，不能立即对他进行个性化推荐，因为用户相似度是离线计算的；新物品上线后一段时间，一旦有用户对物品产生行为，就可以将新物品推荐给其他用户 新用户只要对一个物品产生行为，就能推荐相关物品给他，但无法在不离线更新物品相似度表的情况下将新物品推荐给用户（但是新的item到来也同样是冷启动问题）
推荐理由 很难提供令用户信服的推荐解释 可以根据用户历史行为归纳推荐理由

基于**用户**的协同过滤举例：

用户/物品 物品1 物品2 物品3 物品4
用户A √ √ 推荐
用户B √
用户C √ √ √

用户A和用户C都喜欢物品1和物品3，基于用户的协同过滤算法认为用户A和用户C喜好相似，故将用户C喜欢的物品4推荐给用户A。

基于**物品**的协同过滤举例：

用户/物品 物品1 物品2 物品3
用户A √ √
用户B √ √ √
用户C √ 推荐

物品1和物品3都被用户A和用户B喜欢，基于物品的协同过滤算法认为物品1和物品3类型相似，因用户C喜欢物品1，则将物品3推荐给用户C。

计算推荐

基于用户相似度的推荐

其实就是KNN算法的计算过程。

相似度计算最好使用皮尔逊相关系数和基于相似度门槛的邻居来进行相似用户的选定。

基于物品相似度的推荐

如下例所示：

如上表为用户对电影的评分表，若我想预测用户5对电影1的评分，从而进行推荐决策。(评分大于3.5才推荐)我们可以这样做：

分别计算电影1与电影2、电影3等其他电影的相似度（必要时对评分进行预处理，消除数据差异），记为 $$ sim(1,m) $$ 取两个相似度：最大的和第二大的，分别为0.59,0.410.59,0.41，这就是相似的邻居，然后通过加权计算预测出用户5对电影1的评分为2.6，推荐决策为：不推荐。

以上就是协同过滤算法的基本原理和实现啦，抖音和头条不一定用的是协同过滤，但这个算法是入门推荐系统必备的，基本上简单的系统用上协同过滤就足够啦。

欢迎交流

我整理了一系列的技术文章和资料，在公众号「程序设计实验室」后台回复 linux、flutter、c#、netcore、android、java、python 等可获取相关技术文章和资料，同时有任何问题都可以在公众号后台留言~