概述
协同过滤(Collaborative Filtering)是推荐系统中最经典的方法了，本文做一个简单的概述。
User-based Collaborative Filtering
假设一个场景，我们想买一个东西或者想吃一个东西，但是自己不知道哪种东西比较好，那么通常的选择就是去询问身边有着相似喜好的朋友寻求推荐。这就是基于用户的协同过滤，核心思想就是相似的用户(user)会喜欢相似的物品(item)。
用户数据
为了在用户群体中找到跟自己相似的用户，很明显需要收集所有用户的数据，如所有用户对多个商品的评价，那么该数据的矩阵形状为$(n_{users},n_{items})$。在该矩阵中计算其他所有用户与指定用户的相似度，并使用前$k$个相似用户的数据来做推荐。推荐，肯定是该用户未曾见过或用过的东西，那么需要选出这些相似用户对指定用户未评价过的物品的评价数据，再做下一步计算。
相似用户对物品的加权评价为：相似度$\times$评分；另外，考虑到热门物品与冷门物品在评价人数上的巨大差别，还需要对加权平价做一个归一化的处理：加权评分/评价人数。对指定用户所有未接触过的物品做加权评价求和，按得分排序就得到了一个推荐物品序列。
假设现在有如下评价数据，其中的0为缺失值的填充值：
| item1 | item2 | item3 | item4 | item5 | item6 | |
|---|---|---|---|---|---|---|
| user1 | 2.5 | 3.5 | 3 | 3.5 | 2.5 | 3 |
| user2 | 3 | 3.5 | 1.5 | 5 | 3.5 | 3 |
| user3 | 2.5 | 3 | 0 | 3.5 | 0 | 4 |
| user4 | 0 | 3.5 | 3 | 0 | 4 | 4 |
| user5 | 3 | 4 | 2 | 3 | 2 | 3 |
| user6 | 3 | 4 | 0 | 5 | 3.5 | 3 |
| user7 | 0 | 4.5 | 0 | 4 | 1 | 0 |
现需要针对用户7做推荐。首先计算用户之间的相似度，这里使用：
\[sim=\frac{1}{1+dist_{E}}\]其中$dist_{E}$为欧氏距离。与用户7最相似的前3个用户及其相似度为：
| user5 | user6 | user3 | |
|---|---|---|---|
| user7 | 0.1687 | 0.1652 | 0.1646 |
用户7未接触过的物品为item1、item3和item6，相似用户对其的加权评价数据为：
| sim | item1 | item3 | item6 | |
|---|---|---|---|---|
| user3 | 0.1646 | 2.5*0.1646 | 0 | 4*0.1646 |
| user5 | 0.1687 | 3*0.1687 | 2*0.1687 | 3*0.1687 |
| user6 | 0.1652 | 3*0.1652 | 0 | 3*0.1652 |
| item score | - | 1.4138 | 0.3375 | 1.6607 |
| sim sum | - | 0.1646+0.1687+0.1652 | 0.1687 | 0.1646+0.1687+0.1652 |
| scaling score | - | 2.8349 | 2 | 3.33 |
从上述表中可以发现，对于评价人数较少的item1在计算得分时会处于劣势，为了消除这种劣势，所有的得分还需除以一个可以表征评价人数的相似度和sim_sum。
以上过程实现的是把物品推荐给人，如果对原数据做转置操作，就可以实现把人推荐给物品。
Item-based Collaborative Filtering
从上节过程对应的实现代码中发现，系统需要维护一个大小为$(n_{users},n_{users})$的相似度矩阵，并且每次做推荐都需要在原数据中去查找数据，当然在实现上可以将一些中间数据缓存起来以减少计算。但是注意到，对于大多数系统而言，用户是频繁变化的，但是物品却是稳定的，并且通常用户的数据量远远大于物品数量。所以在通常情况下使用的是基于物品的协同过滤，而不是基于用户的协同过滤。并且在实现上，有几个可以优化的地方。
首先，因为物品数量通常远小于用户数量，所以维护一个物品相似度矩阵肯定比维护一个用户相似度矩阵要好得多；另外，在推荐物品时，通常的推荐数在20个以下，这就大大降低了需要缓存的数据量。
Latent Factor Model
不难发现真实情境下的user-item矩阵是一个$(n_{users},n_{items})$的大型稀疏矩阵，无论是基于用户还是基于物品的协同过滤算法，都需要在这个稀疏矩阵中找到若干个相似对象，这一步是既费时又费空间的操作。实际上，评价数据一般是以table的形式存储在数据库中，所以我们拥有的原数据格式并不是矩阵形式，而是类似于key-val对的多元组形式。
首先引入矩阵分解的概念，形状为$(n_{users},n_{items})$可以表示成两个形如$(n_{users},k)$与$(n_{items},k)^{T}$的矩阵相乘,矩阵中的$k$列表示的是数据中的隐因子(Latent Factor)。那么是不是直接分解user-item矩阵来得到压缩后的两矩阵呢？刚刚说过，原数据并不是矩阵形式；其次，SVD在大型矩阵上的运行速度很慢；最后，如果使用矩阵分解的方法，还需要再构造一个user-item矩阵，相当麻烦。所以使用的是迭代优化的方法来得到两个压缩矩阵。
设用户隐因子矩阵为$p_{(n_{users},k)}$，物品隐因子矩阵为$q_{(n_{items},k)}$，那么user-item矩阵中对应位置的值可以由下式计算：
\[\hat{r}_{ui}=p_{u}q_{i}^{T}\]得到最简单的优化问题为：
\[\min_{p,q} \ \sum\limits_{u,i}(r_{ui}-\hat{r}_{ui})^{2}\]该问题可以使用梯度下降法来解决。注意这种方法并不需要构造user-item矩阵，也不需要维护相似度矩阵，只需要user与item的索引即可从数据库中直接取出$r_{ui}$。
了解了LFM的基本原理之后，我们再引入一些修正。假设所有用户与所有物品之间有一个基准分数，并且用户与物品自身都有着一些影响客观评分的特征，如某个用户要求很高，倾向于给物品打低分；而某些物品则品质极好，更容易获得高分。令全局基准分数为$\mu$，用户的偏好数组为$bias_{user}$，物品的偏好数组为$bias_{item}$，同时结合上述矩阵分解的思想，那么此时对user-item对的预测值为：
\[\hat{r}_{ui}=\mu+b_{u}+b_{i}+p_{u}q_{i}^{T}\]易得带正则项的优化问题为：
\[\min_{b_{u},b_{i},p,q} \ \sum\limits_{u,i}(r_{ui}-\mu-b_{u}-b_{i}-p_{u}q_{i}^{T})^{2}+\alpha(||b_{u}||_{2}+||b_{i}||_{2}+||p||_{2}+||q||_{2})\]令学习率为$\eta$，预测误差$e_{ui}=r_{ui}-\hat{r}_{ui}$，求导得各参数的迭代优化公式(省略常数项)：
\[\begin{aligned} b_{u}&:=b_{u}+\eta(e_{ui}-{\alpha}b_{u}) \\ b_{i}&:=b_{i}+\eta(e_{ui}-{\alpha}b_{i}) \\ p&:=p+\eta(e_{ui}q-{\alpha}p) \\ q&:=q+\eta(e_{ui}p-{\alpha}q) \\ \end{aligned}\]