Recommendation algorithm

1. 推荐算法定义：

推荐算法是计算机专业中的一种算法.就是利用用户的一些行为,通过一些数学算法,推测出用户可能喜欢的东西.

2. 推荐算法的分类：

角度一(百度百科)：

基于内容的推荐
基于协同过滤的推荐
基于关联规则推荐
基于效用推荐
基于知识推荐
组合推荐

角度二(知乎)：

个性化推荐
- 个性化推荐的两个主要思想八个字概括之：物以类聚、人以群分。主要的方法及变种应该有很多，像协同过滤、基于内容的推荐、基于标签的推荐等等。国内项亮著有《推荐系统实践》，对于解决推荐问题有比较详细的介绍；
非个性化推荐
- “让全局优秀的内容被大家看到”应该算是非个性化推荐，热门榜单/最多观看这类方法可以简单解决这个问题；不同的人对于“好”的理解不一样，换句话说也就是偏好不同，所以推荐新加入的好内容我认为是个性化推荐问题。

角度三(知乎)：

基于内容的推荐算法
- 基于内容的推荐算法，原理是用户喜欢和自己关注过的Item在内容上类似的Item，比如你看了哈利波特I，基于内容的推荐算法发现哈利波特II-VI，与你以前观看的在内容上面（共有很多关键词）有很大关联性，就把后者推荐给你，这种方法可以避免Item的冷启动问题（冷启动：如果一个Item从没有被关注过，其他推荐算法则很少会去推荐，但是基于内容的推荐算法可以分析Item之间的关系，实现推荐），弊端在于推荐的Item可能会重复，典型的就是新闻推荐，如果你看了一则关于MH370的新闻，很可能推荐的新闻和你浏览过的，内容一致；另外一个弊端则是对于一些多媒体的推荐（比如音乐、电影、图片等)由于很难提内容特征，则很难进行推荐，一种解决方式则是人工给这些Item打标签。
协同过滤推荐算法
- 协同过滤算法，原理是用户喜欢那些具有相似兴趣的用户喜欢过的商品，比如你的朋友喜欢电影哈利波特I，那么就会推荐给你，这是最简单的基于用户的协同过滤算法（user-based collaboratIve filtering），还有一种是基于Item的协同过滤算法（item-based collaborative filtering），这两种方法都是将用户的所有数据读入到内存中进行运算的，因此成为Memory-based Collaborative Filtering，
- 另一种则是Model-based collaborative filtering，包括Aspect Model，pLSA，LDA，聚类，SVD，Matrix Factorization等，这种方法训练过程比较长，但是训练完成后，推荐过程比较快。
基于知识的推荐算法
- 基于知识的推荐算法，也有人将这种方法归为基于内容的推荐，这种方法比较典型的是构建领域本体，或者是建立一定的规则，进行推荐。
混合推荐算法
- 混合推荐算法，则会融合以上方法，以加权或者串联、并联等方式尽心融合。当然，推荐系统还包括很多方法，其实机器学习或者数据挖掘里面的方法，很多都可以应用在推荐系统中，比如说LR、GBDT、RF（这三种方法在一些电商推荐里面经常用到），社交网络里面的图结构等，都可以说是推荐方法。

角度四：

图片展角度：

3. Algorithms

3.1 协同过滤推荐(Collaborative Filtering Recommendation)

3.1.1 概要

Collaborative filtering,即协同过滤,最早于1989年提出,直到21世纪才得到产业性的应用。

在微软1998年的关于协同过滤的论文(1)中，将协同过滤分成了两个流派:

Memory-Based
- User-based
- Item-Based
Model-Based
- Aspect Model
- pLSA
- LDA
- clustering
- SVD
- Matrix Factorization
- Bayesian belief nets
- latent semantic
- 使用SVM等的CF算法

(1) 关于Memory-Based的算法

就是利用用户在系统中的操作记录来生成相关的推荐结果的一种方法，主要也分成两种方法:

User-Based : 利用用户与用户之间的相似性，生成最近的邻居，当需要推荐的时候，从最近的邻居中得到推荐得分最高的几篇文章，用作推荐;
Item-Based : 基于item之间的关系，针对item来作推荐，Amazon.com即是使用这种方法，使用一种基本的方法来得到不俗的效果.

实验结果也表明，Item-Based的做法比User-Based更有效2。

对于Memory-Based算法，主要有两个步骤 :

计算相似性
- 第一步，主要是于线下计算item-item或者user-user之间的相似性，主要使用的算法有Correlation-Based，如Pearson correlation [4], Jaccard coefficient[5]等，与Vector Cosine-Based Similarity ，和在实验中被验证具有最好效果的Regression.
进行推荐
- 第二步，则是生成相关的推荐项目的过程。主要是根据上一步得出的最近邻，从其中得出最相关的Top-N个推荐的项目作为结果。这种方法被沿用多年，大多数的推荐系统都是使用这种方法构建的.

(2) 对于Model-Based的算法

使用机器学习中的一些建模算法，在线下对于模型进行预计算，在线上能够快速得出结果。主要使用的算法有:

Aspect Model
pLSA
LDA
clustering
SVD
Matrix Factorization
Bayesian belief nets
latent semantic
使用SVM等的CF算法

(3) 最近几年又提出一种新的分类,content-based,是对于item的内容进行分析,从而进行推荐.

content-based

(4) 而现阶段,比较优秀的一些应用算法,则是将以上几种方法混合使用.

比较说Google News[3]，在它的系统中，使用了一种将Memory-Based与Model-Based两种方法混合的算法来处理。在Google的那篇论文里面，它提到了如何构建一个大型的推荐系统，其中Google的一些高效的基础架构如：BigTable,MapReduce等得到很好的应用.

Memory-Based与Model-Based两种方法混合

(5) 对于大多数的项目而言，推荐系统都不可避免地面临以下几个问题[6]:

1.数据过度松散，当应用变得庞大，数据集开始增大的时候，就会出现这个问题了。可能大量的用户只是评价了一小部分的项目，而大多数的项目是没有进行评分的。这个时候就会出现数据过度松散的问题。
2.同义项目问题，对于同义的项目，在系统中可能具有不同的标识符，对于这些项目之间的相关性就会被忽略。
3.垃圾攻击，对于一些利用系统进行恶意传播的用户，可能会制造一些虚假的评价，造成系统推荐的不正确行为。
4.冷启动问题，对于新使用系统的用户，系统中并没有相关的操作记录，没法生成相关的推荐。

3.1.2 算法介绍

1. 向量之间的相似度度量计算

度量向量之间的相似度方法很多,可以用距离(各种距离)的倒数,向量夹角,Pearson相关系数等

(1) 距离

什么是jaccard？

杰卡德相似系数(Jaccard similarity coefficient)，也称杰卡德指数(Jaccard Index)，是用来衡量两个集合相似度的一种指标。Jaccard相似指数用来度量两个集合之间的相似性，它被定义为两个集合交集的元素个数除以并集的元素个数。

(2) 向量夹角

什么是余弦相似度？

余弦相似度,又称为余弦相似性.通过计算两个向量的夹角余弦值来评估他们的相似度.将向量根据坐标值绘制到向量空间中.如最常见的二维空间.求得他们的夹角,并得出夹角对应的余弦值,此余弦值就可以用来表征这两个向量的相似性.夹角越小.余弦值越接近于1,它们的方向更加吻合,则越相似.余弦值的范围在[-1,1]之间,值越趋近于1,代表两个向量的方向越趋近于0,他们的方向更加一致.相应的相似度也越高.最常见的应用就是计算文本相似度.

对于二维空间根据向量点积公式:

\[cos\theta = \frac{a \cdot b}{\parallel a \parallel \parallel b \parallel}\]

假设向量\(a\), \(b\)的坐标分别为\((x_1,y_1)\), \((x_2,y_2)\):

\[cos\theta = \frac{x_1 x_2 + y_1 y_2}{\sqrt{x_1^{2}+y_1^{2}} \times \sqrt{x_2^{2}+y_2^{2}}}\]

假设向量\(a\), \(b\)的坐标分别为\((x_1,x_2, \ldots, x_n)\), \((y_1, y_2, \ldots , y_n)\):

\[cos\theta = \frac{\sum_{1}^{n}(x_i \times y_i)}{\sqrt{\sum^{n}_{1}x_i^{2}} + \sqrt{\sum_{1}^{n}y_i^{2}}}\]

(3) Pearson相关系数

Pearson相关系数：

\begin{equation} \rho_{X,Y}=\frac{cov(X,Y)}{\sigma_{x}\sigma_{y}}=\frac{E((X-\mu_x)(Y-\mu_y))}{\sigma_{x}\sigma_{y}} \end{equation}

因为:

\[\mu_{x} = E(X),\] \[\sigma^2_{x} = E(X-\mu_x)^2=E(X^2)-E^2(X)\]

所以Pearson相关系数还可以写成下面形式：

\begin{equation} \rho_{X,Y}=\frac{E(XY)-E(X)E(Y)}{\sqrt{E(X^2)-E^2(X)}\sqrt{E(Y^2)-E^2(Y)}} \end{equation}

说明：

Pearson相关系数越接近于1或-1,说明两个变量的线性关系越强.
Pearson相关系数有个特点,它在计算两个向量的相似度时忽略其平均值的差异.比如说有的用户对商品评分普遍偏低,有的用户评分普遍偏高,而实际上他们具有相同的爱好,他们的Pearson相关系数会比较高. 用户1对某一个商品的评分是\(X=(1,2,3)\),用户2对这三个商品的评分是\(Y=(4,5,6)\)，则\(X\)和\(Y\)的Pearson相关系数是\(0.865\)，相关性还是挺高的。

2. 用户评分数据矩阵

User & Item	\(item_{1}\)	\(\ldots\)	\(item_{n}\)
\(user_{1}\)	\(r_{1,1}\)	\(\ldots\)	\(r_{1,n}\)
\(\vdots\)	\(\vdots\)	\(r_{i,j}\)	\(\vdots\)
\(user_{m}\)	\(r_{1,m}\)	\(\ldots\)	\(r_{m,n}\)

3. 基于用户(user-based)的协同过滤

(0) 符号说明

u : 目标用户
U : 和目标用户兴趣相似的用户群体
U(o)
U_{o}
I :
i :

(1) 基本思想:

当一个用户 u 需要个性化推荐时, 可以先找到和他兴趣相似的用户群体 U , 然后把 U 喜欢的、并且 u 没有听说过的物品推荐给 u

(2) 两个步骤:

找到与目标用户 (\(u\)) 兴趣相似的用户集合 (\(U\));
找到这个相似用户集合 (\(U\)) 中相似用户 (\(U_{o}, o = 1, 2,\ldots ,k\)) 喜欢的、并且目标用户 (\(u\)) 没有听说过的物品 (\(I\)) 推荐给目标用户 (\(u\)).

step1. 如果用户 \(u\) 对项目 \(i\) 没有评过分，就找到与用户 \(u\) 最相似的 \(k\) 个相似用户;
step2. 然后用这 \(k\) 个邻居对项目 \(i\) 的评分的加权平均来预测用户 \(u\) 对项目 \(i\) 的评分.

(3) 目的：

预测目标用户 \(u\) 对商品 \(i \in I\) 的评分\(r_{u,i}\)

(3) 发现目标用户兴趣相似的用户集合(群体)

假设:

用户 \(x\) 评分的商品集合为\(I_{x}\), 即用户 \(x\) 喜欢的物品;
用户 \(y\) 评分的商品集合为\(I_{y}\)，即用户 \(y\) 喜欢的物品;
用户 \(x\) 和用户 \(y\) 都有评分的商品并集为\(I_{x,y}\), 即用户 \(x\) 和用户 \(y\) 都喜欢的物品;
目标用户 \(u\) 对所有商品的平均得分为 \(\bar{r}_{u}\)

用户评分数据向量:

\[ \left\{\begin{array}{ll} U_1=(r_{1,1},r_{1,2}, ..., r_{1,n})\\ U_2=(r_{2,1},r_{2,2}, ..., r_{2,n})\\ \ldots\\ U_i=(r_{i,1},r_{i,2}, ..., r_{i,n})\\ \ldots\\ U_j=(r_{j,1},r_{j,2}, ..., r_{j,n})\\ \ldots\\ U_m=(r_{m,1},r_{m,2}, ..., r_{m,n}) \end{array}\right. \]

计算用户 \(x\) 和 \(y\) 之间的相似度:

Jaccard公式

\[Similarity(x, y) = \frac{|I_{x} \cap I_{y}|}{|I_{x} \cup I_{y}|}\]

余弦相似度

\[Similarity(x, y) = \frac{|I_{x} \cap I_{y}|}{\sqrt{|I_{x}| \times |I_{y}|}}\]

Pearson相关系数

\begin{equation} Similarity(x, y) = \frac{\sum_{i\in{I_{xy}}}{(r_{x,i}-\bar{r}_{x})(r_{y,i}-\bar{r}_{y})}}{\sqrt{\sum_{i\in{I_{xy}}}{(r_{x,i}-\bar{r}_{x})^2}\sum_{i\in{I_{xy}}}{(r_{y,i}-\bar{r}_{y})^2}}} \end{equation}

利用上面的相似度度量, 可以计算出所有用户之间的相似度. 得到用户相似度矩阵.

(4) 推荐物品

首先，需要从用户相似矩阵中找出与目标用户 \(u\) 最相似的 \(k\) 个用户, 用集合 \(S(u, k)\) 表示;
然后，将 \(S(u, k)\) 中用户喜欢的物品全部提取出来,并去除目标用户 \(u\) 已经喜欢的物品. 对于每个候选物品 \(i \in I\) , 目标用户 \(u\) 对它感兴趣的程度用如下公式计算：

\[r_{u, i} = \sum_{v \in S(u, k) \cap I_{i}}Simlarity(u, v) \times r_{v, i}\]

其中:\(r_{v, i}\)表示用户\(v\) 对\(i\)的喜欢程度, \(v\)为除去目标用户的其他用户. 在一些需要用户给予评分的推荐系统中，则要代入用户评分。在真实的推荐系统中，只要按\(p(u,i)\)得分排序，取前几个物品就可以了.

\begin{equation} r_{u,i}=\bar{r}_{u}+z\sum_{u'\in{U}}{sim(u,u')(r_{u',i}-\bar{r}_{u'})} \end{equation}

其中：\(z\)是归一化因子, \(z=\frac{1}{\sum_{u'\in{U}}{sim(u,u')}}\)

说明:

这个预测方法充分考虑了用户一向的评分习惯是偏高还是偏低，因为用户\(u\)的近邻对\(u\)产生影响时已经减去了各自的平均值。计算用户\(U_{1}\)和\(U_{2}\)的相似度时并不是去拿原始的评分向量去计算，而是只关注他们的评交集\(I_{x,y}\)，这是因为一个用户只对很少的物品有过评分，这样用户评分向量是个高度稀疏的向量，采用Pearson相关系数计算两个用户的相似度时很不准。

4. 基于物品(item-based)的协同过滤

step1. 如果用户\(i\)对项目\(j\)没有评过分，就把\(r_{i,j}\)置为0。找到与物品\(j\)最相似的k个近邻(采用余弦距离);
step2. 然后用这k个邻居对项目\(j\)的评分的加权平均来预测用户\(i\)对项目\(j\)的评分。

物品得分数据向量:

\[ \left\{\begin{array}{ll} I_1=(r_{1,1},r_{2,1}, ..., r_{n,1})\\ I_2=(r_{1,2},r_{2,2}, ..., r_{n,2})\\ \ldots\\ I_i=(r_{1,i},r_{2,i}, ..., r_{n,i})\\ \ldots\\ I_j=(r_{1,j},r_{2,j}, ..., r_{n,j})\\ \ldots\\ I_m=(r_{1,m},r_{2,m}, ..., r_{n,m}) \end{array}\right. \]

目的:

预测用户\(u\)对商品\(i\)的评分\(r_{u,i}\)

假设:

用户\(u\)对所有商品的平均得分为\(\bar{r}_{u}\)

数据向量变换:

每一项减去各个用户评分的均值：

\[ \left\{\begin{array}{ll} I_1=(r_{1,1}-\bar{r}_{1}, r_{2,1}-\bar{r}_{2}, ... , r_{m,1}-\bar{r}_{m})\\ I_2=(r_{1,2}-\bar{r}_{1}, r_{2,2}-\bar{r}_{2}, ... , r_{m,2}-\bar{r}_{m})\\ \ldots\\ I_a=(r_{1,a}-\bar{r}_{1}, r_{2,a}-\bar{r}_{2}, ... , r_{m,a}-\bar{r}_{m})\\ \ldots\\ I_b=(r_{1,b}-\bar{r}_{1}, r_{2,b}-\bar{r}_{2}, ... , r_{m,b}-\bar{r}_{m})\\ \ldots\\ I_m=(r_{1,n}-\bar{r}_{1}, r_{2,m}-\bar{r}_{2}, ... , r_{m,n}-\bar{r}_{m}) \end{array}\right. \]

用户为\(x\), 商品\(i\)和\(j\)间的相似度采用余弦距离计算:

\begin{equation} sim(i,j)=\frac{\sum_x{(r_{x,i}-\bar{r}_{x})(r_{x,j}-\bar{r}_{x})}}{\sqrt{\sum_x{(r_{x,i}-\bar{r}_{x})^2}\sum_x{(r_{x,j}-\bar{r}_{x})^2}}} \end{equation}

结论:

\begin{equation} r_{u,i}=\frac{\sum_{i'\in{N}}{sim(i,i')r_{u,i'}}}{\sum_{i'\in{N}}{sim(i,i')}} \end{equation}

其中: \(N\)是商品\(i\)的近邻。

说明:

由于物品之间的相似度比较稳定，可以离线先算好，定期更新即可。在电商行业这种算法用的比较多。

5. 混合协同过滤

所谓的混合算法，主体思路还是基于用户的协同过滤，只是在计算两个用户的相似度时又嵌套了item-based CF思想。

度量用户\(i\)和用户\(j\)相似度更好的方法是：

1.用户\(i\)参与评分的项目集合为\(I_i\)，用户\(j\)参与评分的项目集合为\(I_{j}\)，找到它们的并集\(U_{i,j}=I_i\cup{I_j}\)
2.在集合\(U_{i,j}\)中用户\(i\)未评分的项目是\(N_{i}=U_{i,j}-I_{i}\)，采用item-based CF方法重新估计用户\(i\)对\(N_{i}\)中每个项目的评分。
3.这样用户\(i\)和\(j\)对\(U_{i,j}\)的评分就都是非0值了，在此情况下计算他们的相似度。