SlopeOne 算法基本原理
目录
- 1. 基本定义
- 2. SlopeOne方案
- 3 加权Slope One方案
- 4 两极Slope One方案
1. 基本定义
| 符号 | 表示的意义 | 例子 |
|---|---|---|
| u u u | 对于给定的用户，将这个用户的对物品的不完全评分数组称为 e v a l u a t i o n evaluation evaluation,这个 e v a l u a t i o n evaluation evaluation表示用户对物品的评分 | u = < u i , u j , u k > u = <u_i,u_j,u_k> u=<ui,uj,uk> 数组 u u u表示用户对物品 i i i, j j j, k k k的评分数组 |
| u i u_i ui | 表示用户对物品 i i i的评分 | |
| u A i u_{Ai} uAi | 表示用户 A A A对物品i的评分 | |
| S ( u ) S(u) S(u) | 表示用户的评分数组 u u u中包含的物品子集 | 例如对于数组 u = < u i , u j , u k > u=<u_i,u_j,u_k> u=<ui,uj,uk>， S ( u ) = { i , j , k } S(u)=\{i,j,k\} S(u)={i,j,k}表示用户有行为的关系的物品集合 |
| χ \chi χ | 表示训练数据中用户评分数组的集合 | χ = { u A , u B , u C } \chi = \{u_A,u_B,u_C\} χ={uA,uB,uC} |
| c a r d ‾ ( S ) car\underline{d}(S) card(S) | 表示物品集合 S S S 中，物品元素的个数 | c a r d ‾ ( S ) = c a r d ‾ ( { i , j , k } ) = 3 car\underline d(S)=car\underline d(\{i,j,k\})=3 card(S)=card({i,j,k})=3 |
| u ‾ \overline{u} u | 表示用户评分数组 u u u的平均评分 | u ‾ = ∑ i ∈ S ( u ) u i c a r d ‾ ( S ( u ) ) \overline u=\frac{\sum_{i\in S(u)}u_i}{car\underline d(S(u))} u=card(S(u))∑i∈S(u)ui |
| S i ( χ ) S_i(\chi) Si(χ) | 表示在训练集 χ \chi χ中所有包含物品 i i i的的评分数组 | S i ( χ ) = { u ∣ i ∈ S ( u ) } S_i(\chi) = \{u \mid i \in S(u) \} Si(χ)={u∣i∈S(u)} |
2. SlopeOne方案
在SlopeOne方案中基本思路如图Fig1.1。
在图Fig1.1中，给出了两个用户 U s e r A User A UserA和 U s e r B User B UserB以及两个物品 I t e m I Item I ItemI和 I t e m J Item J ItemJ。在上图中可以得到一个稀疏评分矩阵
| I t e m Item Item i i i | I t e m Item Item j j j | |
|---|---|---|
| U s e r A User A UserA | 1.0 1.0 1.0 | 1.5 1.5 1.5 |
| U s e r B User B UserB | 2.0 2.0 2.0 | ? ? ? |
根据上述的稀疏矩阵，需要我们预测 U s e r B User B UserB对于 I t e m Item Item j j j的评分。采用SlopeOne方案对评分预测的计算结果如下。
u B j = u B i − ( u A i − u A j ) = 2.0 − ( 1.0 − 1.5 ) = 2.5 ( 2.0 ) u_{Bj}=u_{Bi}-(u_{Ai}-u_{Aj})=2.0-(1.0-1.5)=2.5 \qquad\qquad\qquad\quad (2.0) uBj=uBi−(uAi−uAj)=2.0−(1.0−1.5)=2.5(2.0)
根据SlopeOne评分预测方案，我们进一步扩展数据集中用户的数目和物品的数目，得到如下表所示的评分矩阵。
| I t e m Item Item i i i | I t e m Item Item j j j | I t e m Item Item k k k | I t e m Item Item l l l | I t e m Item Item m m m | |
|---|---|---|---|---|---|
| U s e r A User A UserA | 1.5 1.5 1.5 | 1.0 1.0 1.0 | 1.2 1.2 1.2 | 1.0 1.0 1.0 | 2.0 2.0 2.0 |
| U s e r B User B UserB | 2.0 2.0 2.0 | ? ? ? | 4.0 4.0 4.0 | 2.1 2.1 2.1 | 4.0 4.0 4.0 |
| U s e r C User C UserC | 4.0 4.0 4.0 | 2.1 2.1 2.1 | 3.5 3.5 3.5 | 3.1 3.1 3.1 | 2.6 2.6 2.6 |
| U s e r D User D UserD | 3.0 3.0 3.0 | 2.3 2.3 2.3 | 2.0 2.0 2.0 | 2.1 2.1 2.1 | 1.0 1.0 1.0 |
| U s e r E User E UserE | 1.0 1.0 1.0 | 2.4 2.4 2.4 | 2.0 2.0 2.0 | 1.1 1.1 1.1 | 3.0 3.0 3.0 |
基于上述图Fig1.1给出的Demo，我们将两个用户两个物品的情况扩展到多个用户以及多个物品的情况。那么对于稀疏矩阵中所有 I t e m Item Item在所有用户下共同出现的评分差值计算结果如下。
| 物品 | I t e m Item Item i i i | I t e m Item Item j j j | I t e m Item Item k k k | I t e m Item Item l l l | I t e m Item Item m m m |
|---|---|---|---|---|---|
| I t e m Item Item i i i | — | 0.425 | -0.24 | 0.42 | -0.22 |
| I t e m Item Item j j j | -0.425 | — | 0.225 | 0.125 | -0.2 |
| I t e m Item Item k k k | 0.24 | -0.225 | — | 0.66 | 0.02 |
| I t e m Item Item l l l | -0.42 | -0.125 | -0.66 | — | -0.67 |
| I t e m Item Item m m m | 0.22 | 0.2 | -0.02 | 0.67 | — |
评分矩阵的不同物品评分差值的结果计算方式如公式2.1所示。
d e v i j = ∑ u ∈ S i ( χ ) ∩ S j ( χ ) u i − u j c a r d ‾ ( S i , j ( χ ) ) ( 2.1 ) dev_{ij}=\sum_{u\in S_i(\chi) \cap S_j(\chi)} \frac {u_i-u_j} {car\underline d(S_{i,j}(\chi))} \qquad\qquad\qquad\quad (2.1) devij=u∈Si(χ)∩Sj(χ)∑card(Si,j(χ))ui−uj(2.1)
通过公式2.1可以计算得到所有物品之间总的评分差，那么根据评分矩阵预测 U s e r User User B B B对 I t e m Item Item j j j的评分计算方式如公式2.2所示。
P ( u j ) = ∑ i ∈ S ( u B ) ( d e v i j + u i ) c a r d ‾ ( S ( u B ) ) ( 2.2 ) P(u_j)= \frac {\sum_{i\in S(u_B)}(dev_{ij}+u_i)}{car\underline{d}(S(u_B))} \qquad\qquad\qquad\quad (2.2) P(uj)=card(S(uB))∑i∈S(uB)(devij+ui)(2.2)
根据上述公式计算得到 U s e r User User B B B对 I t e m Item Item J J J的评分计算如下
P ( u j ) = ( 2.0 − 0.425 ) + ( 4.0 − ( − 0.225 ) ) + ( 2.1 − ( − 0.125 ) ) + ( 4.0 − 0.2 ) 4 = 2.95625 ( 2.3 ) P(u_j)=\frac {(2.0 - 0.425) + (4.0-(-0.225)) +(2.1-(-0.125)) + (4.0-0.2) } {4}=2.95625 \qquad\qquad (2.3) P(uj)=4(2.0−0.425)+(4.0−(−0.225))+(2.1−(−0.125))+(4.0−0.2)=2.95625(2.3)
我们将公式(2.2)的分子累加部分拆开，得到的结果为：
P ( u j ) = ∑ i ∈ S ( u ) d e v i j c a r d ‾ ( S ( u ) ) + ∑ i ∈ S ( u ) u i c a r d ‾ ( S ( u ) ) ≈ u ˉ + ∑ i ∈ S ( u ) d e v i j c a r d ‾ ( S ( u ) ) ( 2.4 ) P(u_j)= \frac {\sum_{i\in S(u)}dev_{ij}}{car\underline{d}(S(u))} + \frac {\sum_{i\in S(u)}u_i}{car\underline{d}(S(u))}\approx\bar{u}+\frac {\sum_{i\in S(u)}dev_{ij}}{car\underline{d}(S(u))} \qquad\qquad (2.4) P(uj)=card(S(u))∑i∈S(u)devij+card(S(u))∑i∈S(u)ui≈uˉ+card(S(u))∑i∈S(u)devij(2.4)
对于上述情况，前提条件是在用户评分 u u u中所有被评分的物品 i i i 都与需要被评分的物品 j j j 存在共现关系，在大的数据集合下，我们用物品已经观影用户的物品平均评分，代表所有与 I t e m Item Item J J J共同出现的物品的平均评分,从而进行近似表示。
3 加权Slope One方案
在基本Slope One算法的基础上，没有考虑到物品之间贡献次数带来的关系。例如有三个物品I，J，K，现在需要预测对于物品K的评分。给出User A对于I和对J物品的评分如下，以及I与K，J与K的评分差和共现次数。
- User A对Item的评分
| I t e m Item Item i i i | I t e m Item Item j j j | I t e m Item Item k k k | |
|---|---|---|---|
| User A | 3.5 | 2.4 | ? |
- Item I和J的共现次数和平均评分差别
| I t e m Item Item i i i | I t e m Item Item j j j | |
|---|---|---|
| 共现次数 | 1000 | 30 |
| Item K 评分偏差 | 0.5 | 0.2 |
如果根据原来的slopeOne计算方式，对评分的计算策略如下所示：
P ( u k ) = 2.95 + 0.5 + 0.2 2 = 2.95 + 0.35 = 3.3 ( 3.1 ) P(u_k)=2.95 + \frac {0.5 + 0.2 }{2}=2.95 + 0.35 = 3.3 \qquad\qquad (3.1) P(uk)=2.95+20.5+0.2=2.95+0.35=3.3(3.1)
在上述分析中，我们可以发现Item I和Item J与Item K共现的次数无论是多少，最终考虑的都是平均评分差，那么没有用到物品之间共现次数这个数据。在此基础之上，采用的加权slopeOne将共现次数引入到预测器中。我们认为一个物品和目标物品共现次数越多，更适合作为一个预测器，或者说所预测出来的得分置信度更高得到加权的SlopeOne方案如下所示。
P ( u j ) = ∑ i ∈ S ( u ) − { j } ( d e v j , i + u i ) c j , i ∑ i ∈ S ( u ) − { j } c j , i ( 3.2 ) P(u_j)=\frac { \sum_{i\in S(u)-\{j\}} (dev_{j,i}+u_i) c_{j,i}} {\sum_{i \in S(u)-\{j\}} c_{j,i}} \qquad\qquad (3.2) P(uj)=∑i∈S(u)−{j}cj,i∑i∈S(u)−{j}(devj,i+ui)cj,i(3.2)
根据上述公式计算得到User A对物品K的评分，计算方式如下所示：
P ( u j ) = 1000 ∗ ( 3.5 + 0.5 ) + 30 ∗ ( 2.4 + 0.2 ) 1000 + 30 = 3.9592 ( 3.3 ) P(u_j)=\frac {1000 * (3.5 + 0.5) + 30 * (2.4 + 0.2)}{1000 + 30} = 3.9592 \qquad\qquad (3.3) P(uj)=1000+301000∗(3.5+0.5)+30∗(2.4+0.2)=3.9592(3.3)
4 两极Slope One方案
通过上述加权的方式，对于头部流量的Item是具有优势的，这一部分Item出现的频率相对来说比较高。在下一步的方案中讨论的两极SlopeOne模式采用了一种新得评分预测方式。
在两极slopeOne的实现中，我们将预测分为两个部分：
- 用户喜欢的物品
- 用户不喜欢的物品
并在此基础之上采用加权SlopeOne进行计算，利用用户喜欢的物品和不喜欢的物品预测对物品的评分。
首先给出一个从0~10 的评分范围，在给出的评分范围中，可能认为去中间值5作为阈值比较合理，这样的话我们将用户对Item评分大于5的表示为喜欢，小于5的表示为不喜欢，如果用户的评分是均匀分布的话，这样的设置会有一个较好的效果。然而在电影评分中70%的评分数据大概集中在中间位置。当我们希望这个喜欢和不喜欢的阈值划分适用于所有的用户(无论是倾向于高分评价用户，低分评价用户，两极评分用户)的时候，我们取每一个用户对物品的平均评分作为评分标准。
例如一个积极的用户，这样的用户可能对所有的物品都有较高的评分，那么对于低于他们平均评分的数据我们认为他们是不喜欢的。因此通过这个阈值，使得所有的用户都有合理的喜欢物品数和不喜欢物品数目。
根据上述Fig 1.1中的图示，那么在两极slopeOne中，我们需要如果通过 I t e m Item Item J J J和 I t e m Item Item I I I之间的共现次数来计算User B对 I t e m Item Item J J J的评分。我们首先需要将用户分成喜欢这个物品和不喜欢这个物品两个用户组。
在SlopeOne方案中，对于物品的预测评分约束要求的更加严格。首先对于物品而言，只有对于两个g共现的物品都喜欢或者是两个物品都不喜欢的用户，我们才说这样的评分是有效的。也就是，一个用户对两个物品的评分在喜好上趋于一致的时候我们才说用用户对其中一个物品的一个评分去预测另外物品的一个评分是可靠的。其次，对于用户而言，只有一个用户对 I t e m Item Item I I I和 I t e m Item Item J J J同时表现出相同的喜好的时候，这个 I t e m Item Item I I I才会用来去预测 I t e m Item Item J J J的评分。
为了进一步解释上诉的例子，我们给出如下五个用户对五个物品的评分。
| I t e m Item Item i i i | I t e m Item Item j j j | I t e m Item Item k k k | I t e m Item Item l l l | I t e m Item Item m m m | u ‾ \overline u u | |
|---|---|---|---|---|---|---|
| U s e r A User A UserA | 1.5 1.5 1.5 | 1.0 1.0 1.0 | 1.2 1.2 1.2 | 1.0 1.0 1.0 | 2.0 2.0 2.0 | 1.34 1.34 1.34 |
| U s e r B User B UserB | 2.0 2.0 2.0 | ? ? ? | 4.0 4.0 4.0 | 2.1 2.1 2.1 | 4.0 4.0 4.0 | 3.025 3.025 3.025 |
| U s e r C User C UserC | 4.0 4.0 4.0 | 2.1 2.1 2.1 | 3.5 3.5 3.5 | 3.1 3.1 3.1 | 2.6 2.6 2.6 | 3.06 3.06 3.06 |
| U s e r D User D UserD | 3.0 3.0 3.0 | 2.3 2.3 2.3 | 2.0 2.0 2.0 | 2.1 2.1 2.1 | 1.0 1.0 1.0 | 2.08 2.08 2.08 |
| U s e r E User E UserE | 1.0 1.0 1.0 | 2.4 2.4 2.4 | 2.0 2.0 2.0 | 1.1 1.1 1.1 | 3.0 3.0 3.0 | 1.9 1.9 1.9 |
根据上面的表格，在 U s e r A User A UserA的行为评分数据中，只有 { i , m } \{i,m\} {i,m}和 { j , k , l } \{j,k,l\} {j,k,l}这两组共现是有效的。
将每一个用户分为喜欢用户和不喜欢用户，能够使得用户的数目增加。然后，我们需要注意的在两极方案通过严格的评分限制会减少在预测用户评分时候的共现次数。在用户评分的稀疏矩阵中，还要通过划分喜欢用户和不喜欢用户来提高准确度确实是不符合我们的直觉，但是如果考虑将不相关的物品在一起共同出现，可能引入更多的问题。至关重要的是，两极slope One方案没有从用户 A A A喜欢 I t e m Item Item K K K和用户 B B B不喜欢 I t e m Item Item K K K中预测任何东西
为了形式化描述，我们将每一个用户的评分数组 u u u分为两个评分集合：
| 符号 | 形式化描述 | 含义 | 表示作用 |
|---|---|---|---|
| S l i k e ( u ) S^{like}(u) Slike(u) | { i ∈ S ( u ) ∣ u i > u ‾ } \{i \in S(u) \mid u_i > \overline{u}\} {i∈S(u)∣ui>u} | 表示在用户评分数组中大于平均评分的评分组成的物品评分数组 | 用户喜欢的 I t e m Item Item评分 |
| S d i s l i k e ( u ) S^{dislike}(u) Sdislike(u) | { i ∈ S ( u ) ∣ u i < u ‾ } \{i \in S(u) \mid u_i < \overline{u}\} {i∈S(u)∣ui<u} | 表示在用户评分数组中小于平均评分的物品评分组成的评分数组 | 用户不喜欢的 I t e m Item Item评分 |
在上述描述的基础上对于每一组共现物品评分集合都可以分为两个部分，这两个部分分别是同时喜欢 I t e m Item Item i i i和 I t e m Item Item J J J的一级同时不喜欢 I t e m Item Item I I I和 t e m tem tem J J J的用户 e v a l u a t i o n s evaluations evaluations,具体的形式化描述如下。
S i , j l i k e = { u ∈ χ ∣ i , j ∈ S l i k e ( u ) } ( 4.1 ) S^{like}_{i,j}=\{u\in \chi \mid i,j\in S^{like}(u)\} \qquad\qquad (4.1) Si,jlike={u∈χ∣i,j∈Slike(u)}(4.1)
S i , j d i s l i k e = { u ∈ χ ∣ i , j ∈ S d i s l i k e ( u ) } ( 4.2 ) S^{dislike}_{i,j}=\{u \in \chi \mid i,j \in S^{dislike}(u)\} \qquad\qquad (4.2) Si,jdislike={u∈χ∣i,j∈Sdislike(u)}(4.2)
使用这两个评分集合我们可以计算喜欢 I t e m Item Item I I I和 I t e m Item Item J J J的用户对这两个物品的评分差计算方式为。
d e v j l i k e , i = ∑ u ∈ S j , i l i k e ( χ ) u j − u i c a r d ‾ ( S j , i l i k e ( χ ) ) ( 4.3 ) dev^{like}_j,i= \sum_{ u \in S^{like}_{j,i}(\chi)} \frac {u_j-u_i}{car\underline d(S^{like}_{j,i}( \chi))} \qquad\qquad (4.3) devjlike,i=u∈Sj,ilike(χ)∑card(Sj,ilike(χ))uj−ui(4.3)
同样地对于同时不喜欢$Item I I I和 I t e m Item Item J J J的用户评分差的计算方式如下。
d e v j d i s l i k e , i = ∑ u ∈ S j , i d i s l i k e ( χ ) u j − u i c a r d ‾ ( S j , i d i s l i k e ( χ ) ) ( 4.4 ) dev^{dislike}_j,i= \sum_{ u \in S^{dislike}_{j,i}(\chi)} \frac {u_j-u_i}{car\underline d(S^{dislike}_{j,i}( \chi))} \qquad\qquad (4.4) devjdislike,i=u∈Sj,idislike(χ)∑card(Sj,idislike(χ))uj−ui(4.4)
那么根据上述的描述可知，如果我们需要基于一个 I t e m Item Item i i i预测一个 I t e m Item Item J J J的评分，那么有两种方式具体如下所示。
P ( u j ) = { d e v j , i l i k e + u i , u i > u ‾ d e v j , i d i s l i k e + u i , u i < u ‾ ( 4.5 ) P(u_j)=
\qquad\qquad (4.5) P(uj)={devj,ilike+ui,devj,idislike+ui,ui>uui<u(4.5)
从而得到两极SlopeOne方案，实现用户对物品的评分计算如下图所示。
P b p S l ( u ) j = ∑ i ∈ S l i k e ( u ) − { j } p j , i l i k e c j , i l i k e + ∑ i ∈ S d i s l i k e ( u ) − { j } p j , i d i s l i k e c j , i d i s l i k e ∑ i ∈ S l i k e ( u ) − { j } c j , i l i k e + ∑ i ∈ S d i s l i k e ( u ) − { j } c j , i d i s l i k e ( 4.6 ) P^{bpSl}(u)_j = \frac {\sum_{i \in S^{like}(u)-\{j\}}p_{j,i}^{like} c_{j,i}^{like} + \sum_{i \in S^{dislike}(u)-\{j\}} p_{j,i}^{dislike}c_{j,i}^{dislike}} {\sum_{i \in S^{like}(u)-\{j\}}c_{j,i}^{like} + \sum_{i \in S^{dislike}(u)-\{j\}}c_{j,i}^{dislike}} \qquad\qquad (4.6) PbpSl(u)j=∑i∈Slike(u)−{j}cj,ilike+∑i∈Sdislike(u)−{j}cj,idislike∑i∈Slike(u)−{j}pj,ilikecj,ilike+∑i∈Sdislike(u)−{j}pj,idislikecj,idislike(4.6)
更多问题可以关注：查叔笔录