推荐系统中的协同过滤算法

前言

如果你对这篇文章感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

概述

协同过滤是一种推荐算法，其通常建模为 m m m 个用户， n n n 个物品，只有部分用户和部分物品之间有评分数据，其它评分是空白的，此时就要求我们用已有的部分稀疏数据来预测空白的部分，找到评分最高的物品推荐给用户。

协同过滤通常有三种类型：

• 基于用户 (user-based)：考虑用户之间的相似度，基于相似用户的喜好，预测目标用户对相应物品的评分（可能带给用户惊喜）；
• 基于物品 (item-based)：考虑物品之间的相似度，基于目标用户对某些物品的评分，预测相似度高的类似物品；
• 基于模型 (model-based)：用各类机器学习算法进行解决，是目前最主流的协同过滤类型。

基于模型的协同过滤

【1】关联算法：对用户购买物品的所有历史记录进行数据挖掘，找出常出现的关联物品集，即频繁项集

• 常见算法有 Apriori、FP Tree、PrefixSpan

【2】聚类算法：基于用户聚类，将用户按照某距离度量划分成不同目标人群；或基于物品聚类，推荐用户喜爱物品的相似物品

• 常见算法有 K-Means、BIRCH（层次方法聚类）、DBSCAN、谱聚类

【3】分类算法：将用户评分高低分成多段，用分类模型来学习

• 常见算法有逻辑回归、朴素贝叶斯、支持向量机

【4】回归算法：直接预测用户的评分，用回归模型来学习

• 常见算法有线性回归、回归树、支持向量回归

【5】矩阵分解：将稀疏矩阵分解成 P ⊤ Q P^\top Q P⊤Q 形式，再将其用于推荐

• 常见算法有 FunkSVD、BiasSVD、SVD++、Factorization Machine、Tensor Factorization

【6】图模型：将用户之间的相似度放到一个图模型中进行考虑

• 常见算法有 SimRank 系列算法和马尔可夫模型算法

【7】神经网络：用神经网络模型来做回归任务

基于矩阵分解的协同过滤方法

以 FunkSVD 算法为例，其将期望得到的矩阵 M M M 进行如下分解：
M m × n = P m × k ⊤ Q k × n , M_{m \times n}=P_{m \times k}^\top Q_{k \times n}, Mm×n​=Pm×k⊤​Qk×n​,

其中 m i j m_{ij} mij​ 表示第 i i i 个用户对第 j j j 个物品的评分，当得到矩阵 P P P 和 Q Q Q 后，就可以对矩阵 M M M 任意一个空白位置 m i j m_{ij} mij​，通过 p i ⊤ q j p_i^\top q_j pi⊤​qj​ 计算得到。随后可以通过求解如下优化问题得到 P P P 和 Q Q Q：
arg ⁡ min ⁡ P , Q ∑ i , j ( m i j − p i ⊤ q j ) 2 + λ ( ∥ p i ∥ 2 2 + ∥ q j ∥ 2 2 ) , \mathop{\arg \min }\limits_{P,Q} \sum_{i, j}\left(m_{i j}-p_i^\top q_j\right)^2+\lambda\left(\left\|p_i\right\|_2^2+\left\|q_j\right\|_2^2\right), P,Qargmin​i,j∑​(mij​−pi⊤​qj​)2+λ(∥pi​∥22​+∥qj​∥22​),

其中 λ \lambda λ 为正则化系数。上述优化问题可以通过梯度下降进行求解。基于 FunkSVD，后续有许多改进算法，如 BiasSVD 和 SVD++，整体的分解形式差别不大，优化目标有略微区别，本文不再过多介绍。

参考资料

• 协同过滤推荐算法总结
• 矩阵分解在协同过滤推荐算法中的应用