推荐系统（基本方法+评估指标+工具）

• 基本方法
  • Neighborhood-based item-item
  • Model-based 矩阵分解
  • 针对隐式反馈的矩阵分解方法
• 评估指标
  • Error
  • Percentile-rank
  • Hit Radio at NN or HRNN
• 工具
• 参考资料

基本方法

1 Neighborhood-based (item-item)

参考文献：Item-based Collaborative Filtering Recommendation Algorithms

根据与item i 相似的 k 个 items，估计出对item i 的评分。采用加权平均的方法，如下，

sij 为 item i 与 item j 的相似度， rui 为 user u 对 item i 的评分。

r̂ ui=∑j∈Sk(i;u)sijruj∑j∈Sk(i;u)sij

相似度的计算有多种方式，例如余弦相似度，皮尔森相关系数等。

当然，还可以用 user-user 估计，但是users 数目往往很大，不适合较大规模数据。

2 Model-based （矩阵分解）

参考文献：Matrix Factorization Techniques for Recommender Systems

基于相似度的方法只能找出相似的items，意味着向一个看了动作片的人推荐更多动作片。但现实情况是，喜欢看动作片的人可能不仅仅喜欢动作片，也喜欢爱情片，或者爱情动作片。这就需要挖掘出潜在因素来进行推荐（latent factors）。

将 user-item 评分矩阵分解为 user_features x item_features。

由于R矩阵是非常稀疏的，有大量缺失值，如果使用传统SVD分解需要填补缺失值。这样做有两个缺点：1. 填补什么值？会造成不准确；2. 填补后变成稠密矩阵，计算量大增。于是采用忽略缺失值的方法，最小化 least square。但要注意防止 overfitting，加入正则化项（与模型复杂度成正比）。

Lost function：

minp∗,q∗∑(u,i)(rui−pTuqi)2+λ(||pu||2+||qi||2)

可使用SGD（随机梯度下降）求解。每次只用一个样本下降梯度，所以求导时去掉求和符。

同理可以得到 qi 的迭代式。迭代式如下：

for each (u, i):

eui=rui−qTuqi

3 针对隐式反馈的矩阵分解方法

参考文献：Collaborative Filtering for Implicit Feedback Datasets

方法2 主要是针对显示反馈（explicit feedback）的数据。如果你只有用户观看记录（隐式反馈），那么就需要修改一下方法。主要思想是将隐式反馈转化为置信度(confidence)。例如，如果只有用户观看时长，我们可以将观看比例作为评分 rui ，然后转为置信度：

cui=1+αrui

置信度表示，如果用户观看得越久，我们就越相信他是喜欢这部片的。

然后得出修改后的 Lost function，

minx∗,y∗∑(u,i)cui(pui−xTuyi)2+λ(∑u||xu||2+∑i||yi||2)

其中 pui 取值为0，1。（看了则为1，没看则为0）。

求解：

同样可以使用SGD求解，但需要注意的是，这里使用的是隐式反馈，user-item 矩阵就变得不那么稀疏了，因为用户事件可能会非常多（例如点击）。SGD 每次迭代都需要使用所有 user-item pair 进行梯度下降，由于数据变稠密了，计算量就会增加。针对此问题，可以使用 ALS (Alternating Least Square) 求解。与SGD不同，每次更新 X 先固定 Y ，也就转化为 least square 问题，然后交替更新 X 与 Y 。

xu=(YTCuY+λI)−1YTCup(u)

每轮迭代更新：

xu=(YTY+YT(Cu−I)Y+λI)−1YTCup(u)

yi=(XTX+XT(Ci−I)X+λI)−1XTCip(i)

评估指标

有在线评估与离线评估，由于我只做做实验，所以这里就简单介绍离线评估指标。

Error

此法适用于显式反馈评分，很直接，就是计算预测评分与实际评分之间的误差。

MAE

MAE=1N∑|ri−r̂ i|

RMSE

RMSE=1N∑(ri−r̂ i)2‾‾‾‾‾‾‾‾‾‾‾‾‾‾√

然而评分误差指标并不适用于隐式反馈数据，因为用户没有实际评分。可用percentile-rank 和 hit radio评估。

Percentile-rank

我们可以对每个用户给出一个items 推荐列表，如果测试集中的items排得越靠前，说明推荐性能越好。Collaborative Filtering for Implicit Feedback Datasets

Hit Radio at N (or HR@ N )

测试集中，能够落在推荐列表中的 top N 之中的记录数，占总测试记录数的比例。换言之，就是推荐的前 N 个 items 中，有多少是能够命中用户实际偏好的。

Hit Ratio at N, or HR@n, is a way of calculating how many “hits” you have in an n-sized list of ranked items. A “hit” could be defined as something that the user has clicked on, purchased, or saved/favourited (depending on your context). The value of n that you pick will also matter: do you want your hits to appear in the first 10 results, or the first 10,000?

工具

优化问题的求解主要可用两种方法：1. SGD（随机梯度下降）；2. ALS （alternatting least square）。那种方法更好呢？需要视情况而定。对于ALS 方法，速度比较快的应该是implicit。此包是用Cython 写的，多线程，OpenMP 并行化，满负载啪啪，对稀疏矩阵的分解进行了优化，我跑实验也用它。

与 implicit 类似的还有 fastFM。

还有quora编写的工具 qmf。

推荐工具的一个 summary：list of rec sys

参考资料

博客：

A Gentle Introduction to Recommender Systems with Implicit Feedback 里面有提到用implicit 加速ALS训练。

Explicit Matrix Factorization: ALS, SGD, and All That Jazz （比较 SGD 和 ALS，含公式推导）

Implementing your own Recommender Systems in Python using Stochastic Gradient Descent 一个tutorial，介绍SGD。

[A Programmer’s Guide to Data Mining](http://guidetodatamining.com/) 此书对推荐系统有一些简单的介绍。