Slope One是一种基于物品的协同过滤算法，在2005年的paper《Slope One Predictors for Online Rating-Based Collaborative Filtering》被提出，用于预测用户对某一给定的物品的评分。

依然使用上一篇中提到的自己编造的少量评分数据来描述该算法的运作机制。

首先依然是加载数据和生成用户物品关系矩阵如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import pandas as pd
import numpy as np


data_url = 'https://gist.githubusercontent.com/guerbai/3f4964350678c84d359e3536a08f6d3a/raw/f62f26d9ac24d434b1a0be3b5aec57c8a08e7741/user_book_ratings.txt'
df = pd.read_csv(data_url, sep = ',', header = None, names = ['user_id', 'book_id', 'rating'])
user_count = df['user_id'].unique().shape[0]
item_count = df['book_id'].unique().shape[0]
user_id_index_series = pd.Series(range(user_count), index=['user_001', 'user_002', 'user_003', 'user_004', 'user_005', 'user_006'])
item_id_index_series = pd.Series(range(item_count), index=['book_001', 'book_002', 'book_003', 'book_004', 'book_005', 'book_006'])

def construct_user_item_matrix(df):
    user_item_matrix = np.zeros((user_count, item_count), dtype=np.int8)
    for row in df.itertuples():
        user_id = row[1]
        book_id = row[2]
        rating = row[3]
        user_item_matrix[user_id_index_series[user_id], item_id_index_series[book_id]] = rating
    return user_item_matrix

user_item_matrix = construct_user_item_matrix(df)
print (user_item_matrix)
[[4 3 0 0 5 0]
 [5 0 4 0 4 0]
 [4 0 5 3 4 0]
 [0 3 0 0 0 5]
 [0 4 0 0 0 4]
 [0 0 2 4 0 5]]

构造物品评分差异矩阵

接下来生成两个shape为(item_count, item_count)的矩阵differential_matrix与weight_matrix。
前者记录物品两两之间的被评分差异情况，后者记录对某两个物品共同评分的人数，用于之后的计算做加权。

以上面user_item_matrix举例来讲，index为2与4的item的共同评分人数为2(index为1与2的用户)，则计算这两者的评分差异为:
((4-4)+(5-4))/2 = 0.5，故在differential_matrix[2][4]的位置填上0.5，同时在weight_matrix[2][4]的位置填上2。
同时，反过来，differential_matrix[4][2]的值为-0.5，而weight_matrix[4][2]的位置依然为2，这种相对应的位置不需要重复计算了。

下面的函数接受一个用户物品关系矩阵，按照上述方法计算出这两个矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def compute_differential(ratings):
    item_count = ratings.shape[1]
    differential_matrix = np.zeros((item_count, item_count))
    weight_matrix = np.zeros((item_count, item_count))
    for i in range(item_count):
        for j in range(i+1, item_count):
            differential = 0
            i_rating_user_indexes = ratings[:, i].nonzero()[0]
            j_rating_user_indexes = ratings[:, j].nonzero()[0]
            rating_i_j_user = set(i_rating_user_indexes).intersection(set(j_rating_user_indexes))
            user_count = len(rating_i_j_user)
            if user_count == 0:
                continue
            for user_index in rating_i_j_user:
                differential += ratings[user_index][i] - ratings[user_index][j]
            weight_matrix[i][j] = user_count
            weight_matrix[j][i] = user_count
            differential_matrix[i][j] = round(differential/user_count, 2)
            differential_matrix[j][i] = -differential_matrix[i][j]
    return differential_matrix, weight_matrix

differential_matrix, weight_matrix = compute_differential(user_item_matrix)

print ('differential_matrix')
print (differential_matrix)
print ('-----')
print ('weight_matrix')
print (weight_matrix)
differential_matrix
[[ 0.   1.   0.   1.   0.   0. ]
 [-1.   0.   0.   0.  -2.  -1. ]
 [-0.   0.   0.   0.   0.5 -3. ]
 [-1.   0.  -0.   0.  -1.  -1. ]
 [-0.   2.  -0.5  1.   0.   0. ]
 [ 0.   1.   3.   1.   0.   0. ]]
-----
weight_matrix
[[ 0.  1.  2.  1.  3.  0.]
 [ 1.  0.  0.  0.  1.  2.]
 [ 2.  0.  0.  2.  2.  1.]
 [ 1.  0.  2.  0.  1.  1.]
 [ 3.  1.  2.  1.  0.  0.]
 [ 0.  2.  1.  1.  0.  0.]]

进行评分预测

得到上述两个矩阵后可以根据用户的历史评分，为其进行未发生过评分关联的某物品的评分预测。

比如要为index为1的用户user_002预测其对index为3的物品item_004的评分，计算过程如下：
先取出该用户看过的所有书，index分别为[0, 2, 4];
以index为0的物品item_001开始，查differential_matrix[3][0]值为-1，表示item_004平均上比item_001低1分，以该用户对item_001的评分为5为基准，5+(-1)=4，则利用item_001可对item_004做出的评分判断为4分，查weight_matrix表知道同时评分过这两个物品的用户只有一个，置信度不够高，使用4*1=4，这便是加权的含义；
但这还没完，再根据index为2、4的item分别做上一步，并将得到的值加和为15，作为分子，分母为每次计算的人数之和，即加权平均，为4；
最后得此次预测评分为15/4=3.75。

下面的函数接受五个参数，分别为三个矩阵，用户id，物品id，结果为预测值。

1
2
3
4
5
6
7
8
9
def predict(ratings, differential_matrix, weight_matrix, user_index, item_index):
    if ratings[user_index][item_index] != 0: return ratings[user_index][item_index]
    fenzi = 0
    fenmu = 0
    for rated_item_index in ratings[user_index].nonzero()[0]:
        fenzi += weight_matrix[item_index][rated_item_index] * \
            (differential_matrix[item_index][rated_item_index] + ratings[user_index][rated_item_index])
        fenmu += weight_matrix[rated_item_index][item_index]
    return round(fenzi/fenmu, 2)
1
predict(user_book_matrix, book_differential, weight_matrix, 1, 3)
3.75

新的评分数据

当某用户对某个其之间未评分过的物品进行一次新的评分时，需要更新三个矩阵的值。令人欣喜的是，Slope One的计算过程使得这种更新非常迅速，时间复杂度仅为O(x)，其中x为该用户之前评过分的所有物品的数量。

理所当然要在user_item_matrix填入评分值，此外，对此index为i的物品，需要与那x个物品依次组合在weight_matrix中将值增加1。同理differential_matrix也只需要累计上新的差值即可。
一个用户评价过的物品数目是很有限的，这种更新模型的方法可谓飞快。

1
2
3
4
5
6
7
8
9
10
11
def update_matrices(user_index, item_index, rating):
    rated_item_indexes = user_item_matrix[user_index].nonzero()[0]
    user_item_matrix[user_index][item_index] = rating
    for rated_item_index in rated_item_indexes:
        old_weight = weight_matrix[rated_item_index][item_index]
        weight_matrix[rated_item_index][item_index] += 1
        weight_matrix[item_index][rated_item_index] += 1
        differential_matrix[rated_item_index][item_index] = (differential_matrix[rated_item_index][item_index] \
            * old_weight + (user_item_matrix[user_index][rated_item_index] - rating)) / (old_weight + 1)
        differential_matrix[item_index][rated_item_index] = (differential_matrix[item_index][rated_item_index] \
            * old_weight + (rating - user_item_matrix[user_index][rated_item_index])) / (old_weight + 1)

评价

简单易懂：参见代码；
存储：存储上除了user_item_matrix，还需要存下differential_matrix与weight_matrix，为节省空间，可以只存后两者的对角线的右上部分即可；
预测时间复杂度：用户评价过的物品数为x，由predict代码，则做一次预测的时间复杂度为O(x)；
更新时间复杂度：当用户新进行一次评分时，由update_matrices代码，时间复杂度为O(x);
新用户友好：当用户仅进行少量评分时，即可为其进行较高质量的推荐。

参考

《Slope One Predictors for Online Rating-Based Collaborative Filtering》
Slope One wiki