推荐系统和协同过滤算法

推荐系统是目前非常流行的机器学习应用。
特征值对机器学习是非常重要的，而对特征值的选择会直接影响到算法的好坏，推荐系统能够自动帮助学习一些优良的特征值，帮助更好的实现算法。

举例说明

以电影评分和推荐电影为例

先定义几个变量：
$n_u$ =用户人数
$n_m$ =电影数量
$r(i,j)=1$ 表示用户 $j$ 评价了电影 $i$
$y(i,j)$ = 用户 $j$ 对电影 $i$ 的评分，只有在 $r(i,j)=1$ 的时候才会有
$m^{(j)}$ =用户 $j$ 评价过的电影数量

首先电影评分分为0-5星。我们有4个用户和5部电影：

电影	Alice(1)	Bob(2)	Carol(3)	Dave(4)
Love at last(1)	5	5	0	0
Romance forever(2)	5	?	?	0
Cute puppies of love(3)	?	4	0	?
Nonstop car chases(4)	0	0	5	4
Swords vs. karate(5)	0	0	5	?

上表中 $n_u=4,n_m=5$ ，电影 $i=1,2,3$ 为爱情片， $i=4,5$ 为动作片，打问号的表示没有评分。

上面的表格中可以看到Alice和Bob对爱情电影评分很高，对动作片评分很低，Carol和Dave则相反。

现在给每部电影添加两个特征值： $x_1$ 表示浪漫指数， $x_2$ 表示动作指数：

电影	Alice(1)	Bob(2)	Carol(3)	Dave(4)	$x_1$ (浪漫)	$x_2$ (动作)
Love at last(1)	5	5	0	0	0.9	0
Romance forever(2)	5	?	?	0	1	0.01
Cute puppies of love(3)	?	4	0	?	0.99	0
Nonstop car chases(4)	0	0	5	4	0.1	1
Swords vs. karate(5)	0	0	5	?	0	1

用矩阵的形式来表示每个电影的特征值:
$x^{(1)}=\left[ \begin{matrix} 0 \\\ 0.9 \\\ 0 \end{matrix} \right], x^{(2)}=\left[ \begin{matrix} 0 \\\ 1 \\\ 0.01 \end{matrix} \right], x^{(3)}=\left[ \begin{matrix} 0 \\\ 0.99 \\\ 0 \end{matrix} \right], x^{(4)}=\left[ \begin{matrix} 0 \\\ 0.1 \\\ 1 \end{matrix} \right], x^{(5)}=\left[ \begin{matrix} 0 \\\ 0 \\\ 1 \end{matrix} \right]$

想要预测问号的值，这是一个线性回归的问题。
对于用户 $j$ 来说，要预测他对电影 $i$ 的评分值，应用线性回归的模型，当通过算法获得来一个参数 $\theta^{(j)}$ ，通过这个参数，计算 $(\theta^{(j)})^T \cdot x^{(i)}$ ，即可预测出评分值。

假设要预测用户1对电影3的评分：用户1的参数 $\theta^{(1)} = \left[ \begin{matrix} 0 \\\ 5 \\\ 0 \end{matrix} \right]$ ，计算他对电影3的评分： $(\theta^{(1)})^T \cdot x^{(3)} = 4.95$ ，即可预测他的评分为5星。

下面就是对每个用户，应用线性回归模型即可预测出他们对电影的评分。

用公式来表示一下：
对一个用户 $j$ ，他的线性回归公式：
$min_{\theta^{(j)}} = \frac{1}{2m^{(j)}} \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2m^{(j)}}\sum_{k=1}^n(\theta_k^{(j)})^2$
这就是常用的线性回归模型。

下面在公式上约去常数 $m^{(j)}$ 项，这并不影响最小化代价函数：
$min_{\theta^{(j)}} = \frac{1}{2} \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{k=1}^n(\theta_k^{(j)})^2$

然后计算所有用户加在一起的代价函数公式：
$min_{\theta^{(1)},...,\theta^{(n_u)}} = \frac{1}{2} \sum_{j=1}^{n_u} \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n(\theta_k^{(j)})^2$

对该公式应用梯度下降求最小值：
当 $k=0$ ：
$\theta_k^{(j)} := \theta_k^{(j)} - \alpha \left( \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})x_k^{(i)} \right)$

当 $k \not= 0$ ：
$\theta_k^{(j)} := \theta_k^{(j)} - \alpha \left( \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})x_k^{(i)} + \lambda\theta_k^{(j)} \right)$

协同过滤（Collaborative Filtering）

在一个电影网站中，很难去获得一部电影的浪漫指数和动作指数是多少，这个参数很难人为的去判断。为了解决这个问题，可以使用特征寻找器（feature finders.）

现在我们不知道电影的特征值是多少, $x^{(i)}=\left[ \begin{matrix} 0 \\\ ? \\\ ? \end{matrix} \right]$ ，但是我们通过某种途径得知用户对各种类型电影的喜爱程度，是喜欢动作电影还是喜欢爱情电影。 $\theta_1$ 表示喜欢爱情电影的参数， $\theta_2$ 表示喜欢动作电影的参数

电影	Alice(1)	Bob(2)	Carol(3)	Dave(4)
Love at last(1)	5	5	0	0
Romance forever(2)	5	?	?	0
Cute puppies of love(3)	?	4	0	?
Nonstop car chases(4)	0	0	5	4
Swords vs. karate(5)	0	0	5	?
$\theta_1$ (浪漫)	5	5	0	0
$\theta_2$ (动作)	0	0	5	5

用矩阵的形式来表示每个用户的关于电影特征的参数值:
$\theta^{(1)}=\left[ \begin{matrix} 0 \\\ 5 \\\ 0 \end{matrix} \right], \theta^{(2)}=\left[ \begin{matrix} 0 \\\ 5 \\\ 0 \end{matrix} \right], \theta^{(3)}=\left[ \begin{matrix} 0 \\\ 0 \\\ 5 \end{matrix} \right], \theta^{(4)}=\left[ \begin{matrix} 0 \\\ 0 \\\ 5 \end{matrix} \right]$

对一个电影 $i$ ，要获得它的特征值 $x^{(i)}=\left[ \begin{matrix} ? \\\ ? \\\ ? \end{matrix} \right]$ ，也可以看作一个线性回归问题。
同样的预测函数可以写作： $h = (\theta^{(j)})^T \cdot x^{(i)} = (x^{(i)})^T \cdot \theta^{(j)}$

那么对一个电影 $i$ ，它的代价函数则是：
$min_{x^{(i)}} = \frac{1}{2} \sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{k=1}^n(x_k^{(i)})^2$

然后计算所有电影加在一起的代价函数公式：
$min_{x^{(1)},...,x^{(n_m)}} = \frac{1}{2} \sum_{i=1}^{n_m} \sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^n(x_k^{(i)})^2$

同样的应用梯度下降来最小化代价函数。

通过上面的说明：
当我们有电影的特征值 $x$ 时，可以预测出用户的属性 $\theta$ ；当有用户的属性 $\theta$ 可以预测出电影的特征值 $x$ ，这样交替运行，就可以使系统更加完善。这就是基本的协同过滤算法。

算法公式

将上面的两个式子合并，同时最小化特征值和参数：
$J(x,\theta)=\frac{1}{2} \sum_{(i,j):r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x_k^{(i)})^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2$

PS：该式子中的 $x$ 和 $\theta$ 都是n维的向量，它们的偏差单元 $x_0$ 和 $\theta_0$ 都被移除了。

算法步骤

随机初始化 $x^{(1)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)}$ 一个很小的值。
使用梯度下降算法来最小化代价函数 $J$ 。

$x_k^{(i)} := x_k^{(i)} - \alpha \frac{\partial}{\partial x_k^{(i)} }J(x,\theta) := x_k^{(i)} - \alpha \left( \sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})x_k^{(i)} + \lambda x_k^{(i)} \right)$

$\theta_k^{(j)} := x_k^{(i)} - \alpha \frac{\partial}{\partial \theta_k^{(j)} }J(x,\theta) := \theta_k^{(j)} - \alpha \left( \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})x_k^{(i)} + \lambda\theta_k^{(j)} \right)$

这样下来可以对用户尚未评分的电影，通过预测评分大小来推荐电影。
对用户已评分的电影，可以根据评分和用户的属性参数来获得更好的电影特征值。

其他应用

协同过滤算法还可以用来推荐相似的产品，假如当用户看了一个电影 $i$ 之后，可以判断其他电影和该电影的相似度来推荐，相似度的公式为 $||x^{(i)} - x^{(j)}||$ ，当该式子越小时相似度越高，就可以据此来推荐电影。

其他事项

在上述电影网站中，除了上面的四个用户，又有一个新用户加入，他没有对任何电影评分，要预测他对某一个电影的评分，通常采用的方法取评过该电影评分的平均值 $\mu$ 来当作预测值。

转载自：
https://codeeper.com/2020/02/07/tech/machine_learning/recommender_system.html

最后编辑于：2020.03.17 16:23:09

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 213,864评论 6赞 494
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,175评论 3赞 387
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,401评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,170评论 1赞 286
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,276评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,364评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,401评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,179评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,604评论 1赞 306
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,902评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,070评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,751评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,380评论 3赞 319
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,077评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,312评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,924评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,957评论 2赞 351