2005-Slope One Predictors for Online Rating-Based Collaborative Filtering

论文原文 -> 链接

文章简介

基于评分的协同过滤是通过其他用户的评分来预测用户对某项物品的评分。我们提出了三种相关的斜率一方案，其预测器形式为 $f(x) = x + b$ ，该方案预先计算了同时对两项物品进行评分的用户之间的评分平均差异。斜率一算法易于实现，查询效率高，准确性合理，并且支持在线查询和动态更新，这使得它们成为现实世界系统的良好候选者。基本的斜率一方案被建议作为协同过滤的新基准方案。通过将用户喜欢的物品与用户不喜欢的物品分开考虑，我们在标准基准数据集 EachMovie 和 Movielens 上实现了与基于内存的较慢方案相竞争的结果，同时更好地满足了协同过滤应用的需求。

特性：

易于实现和维护：所有聚合数据应易于被理解，算法应易于实现和测试；
可即时更新：新增评分应立即改变所有预测；
查询时间高效：查询应快速，可能会以存储为代价；
对首次访问者要求低：评分较少的用户应能收到有效的推荐；
合理准确：方案应与最准确的方案竞争，但准确性的小幅提升并不总是值得在简单性或可扩展性上做出重大牺牲。

本文的目标不是比较大量协同过滤算法的准确性，而是证明Slope One方案同时满足所有五个目标。尽管我们的方案简单、可更新、计算效率高且可扩展，但它们在准确性上与放弃其他一些优势的方案相当。

Slope One算法基于用户间的不同物品“受欢迎度差异”的直观原则。以成对的方式，我们确定一个物品比另一个物品更受欢迎的程度。衡量这种差异的一种方法是简单地减去两个物品的平均评分。反过来，这种差异可以用来预测另一个用户对其中一个物品的评分，前提是他们已经对另一个物品进行了评分。

考虑两个用户 $A$ 和 $B$ ，两个物品 $I$ 和 $J$ 。用户 $A$ 给物品 $I$ 评分为 $1$ ，而用户 $B$ 给物品 $I$ 评分为 $2$ ，同时用户 $A$ 给物品 $J$ 评分为 $1.5$ 。我们观察到物品 $J$ 的评分比物品 $I$ 高 $1.5−1 = 0.5$ 分，因此我们可以预测用户 $B$ 会给物品 $J$ 评分为 $2+0.5 = 2.5$ 。我们称用户 $B$ 为被预测用户，物品 $J$ 为被预测物品。

在训练集中，每个未知评分存在许多这样的差异，我们取这些差异的平均值。这里介绍的斜率一方案家族源于我们选择相关差异以得出单一预测的三种方式。

本文的主要贡献是提出了斜率一协同过滤预测器，并证明它们与基于内存的方案在几乎相同的准确性上具有竞争力，同时更适合协同过滤任务。

文献综述

给定用户的评分，称为打分，表示为一个不完整的数组 $u$ ，其中 $u_i$ 是该用户对项目 $i$ 的评分。
集合 $S(u)$ 是所有在 $u$ 中被评分的项目的子集。
训练集中的所有打分集合为 $\chi$ 。
集合 $S$ 中的元素数量用 $\text{card}(S)$ 表示。
打分 $u$ 中评分的平均值用 $\bar{u}$ 表示。集合 $S_i(\chi)$ 是所有包含项目 $i$ 的打分 $u \in \chi$ 的集合（即 $i \in S(u)$ ）。
给定两个打分 $u$ 和 $v$ ，我们定义标量积 $\langle u, v \rangle$ 为 $\sum_{i \in S(u) \cap S(v)} u_i v_i$ 。
预测结果为 $P(u)$ ，表示一个向量，其中每个分量是对应一个Item的预测值：预测结果隐含地依赖于训练集 $\chi$ 。

PER USER AVERAGE（每位用户的平均值）

P(u) = \bar{u}

BIAS FROM MEAN（从均值偏差）

P(u)_i=\bar{u}+\frac{1}{\operatorname{card}\left(S_i(\chi)\right)} \sum_{v \in S_i(\chi)} (v_i-\bar{v})

ADJUSTED COSINE ITEM-BASED（调整余弦ItemCF）

「2001年的itemCF论文」

\operatorname{sim}_{i, j}=\frac{\sum_{u \in S_{i, j}(\chi)}\left(u_i-\bar{u}\right)\left(u_j-\bar{u}\right)}{\sum_{u \in S_{i, j}(\chi)}\left(u_i-\bar{u}\right)^2 \sum_{u \in S_{i, j}(\chi)}\left(u_j-\bar{u}\right)^2}

P(u)_i = \frac{\sum_{j\in S(u)}|sim_{i,j}|(\alpha_{i,j}u_j + \beta_{i,j})}{\sum_{j\in S(u)}|sim_{i,j}|}

PEARSON

P(u)_i=\bar{u}+\frac{\sum_{v \in S_i(\chi)} \gamma(u, v)\left(v_i-\bar{v}\right)}{\sum_{v \in S_i(\chi)}|\gamma(u, v)|}

\operatorname{Corr}(u, w) = \frac{\langle u-\bar{u}, w-\bar{w}\rangle}{\sqrt{\sum_{i \in S(u) \cap S(w)}\left(u_i-\bar{u}\right)^2 \sum_{i \in S(u) \cap S(w)}\left(w_i-\bar{w}\right)^2}}

\gamma(u, w) = Corr(u, w)|Corr(u, w)|^{\rho - 1}

其中 $\rho = 2.5$ ， $\rho$ 是Case Amplification power。 $\rho$ 减少了数据中的噪声：如果相关性高，例如 $\text{Corr} = 0.9$ ，那么在案例放大后它仍然很高（ $0.9^{2.5} \approx 0.8$ ）；如果相关性低，例如 $\text{Corr} = 0.1$ ，那么它变得可以忽略不计（ $0.1^{2.5} \approx 0.003$ ）。

核心

SLOPE ONE 算法

SLOPE ONE 方案考虑了来自其他用户的评分信息，这些用户对同一项目进行了评分（类似于 ADJUSTED COSINE ITEM-BASED），以及同一用户对其他项目的评分信息（类似于 PER USER AVERAGE）。然而，这些方案还依赖于既不属于用户数组也不属于项目数组的数据点「『文章简介』中的例子」，但这些数据点对于评分预测仍然是非常重要的信息。该方法的许多优势来自于未被考虑的数据。具体来说，只有那些与预测用户对某些共同项目进行评分的用户的评分，以及预测用户也评分的项目的评分才会进入 Slope One 方案的评分预测中。

形式上，给定两个评估数组 $v_i$ 和 $w_i$ ，其中 $i = 1, \ldots, n$ ，我们寻找形式为 $f(x) = x + b$ 的最佳预测器，通过最小化 $\sum_{i} (v_i + b - w_i)^2$ 来预测 $w$ 从 $v$ 。通过对 $b$ 求导并令导数为零，我们得到： $b = \frac{\sum_{i} w_i - v_i}{n}$ 。常数 $b$ 必须选择为两个数组之间的平均差异。

给定一个训练集 $\chi$ ，以及任意两个项目 $j$ 和 $i$ ，它们在某些用户评估 $u$ 中的评分分别为 $u_j$ 和 $u_i$ （记作 $u \in S_{j,i}(\chi)$ ），我们考虑项目 $i$ 相对于项目 $j$ 的平均偏差为：

\text{dev}_{j,i} = \sum_{u \in S_{j,i}(\chi)} \frac{ (u_j - u_i)}{\text{card}(S_{j,i}(\chi))}

注意，任何不同时包含 $u_j$ 和 $u_i$ 的用户评估 $u$ 都不包含在求和中。由 $\text{dev}_{j,i}$ 定义的对称矩阵可以一次性计算并在新数据输入时快速更新。

假设 $\text{dev}_{j,i} + u_i$ 是给定 $u_i$ 时对 $u_j$ 的预测，一个合理的预测器可能是所有此类预测的平均值：

P(u)_j = \frac{1}{\text{card}(R_j)} \sum_{i \in R_j} (\text{dev}_{j,i} + u_i)

其中 $R_j = \{ i \mid i \in S(u), i \neq j, \text{card}(S_{j,i}(\chi)) > 0 \}$ 是所有相关项目的集合。有一种近似方法可以简化这个预测的计算。对于足够密集的数据集，几乎所有项目对都有评分，即对于几乎所有的 $i, j$ ，有 $\text{card}(S_{j,i}(\chi)) > 0$ ，大多数情况下 $R_j = S(u)$ 当 $j \notin S(u)$ 且 $R_j = S(u) - \{ j \}$ 当 $j \in S(u)$ 。由于： $\bar{u} = \sum_{i \in S(u)}\frac{ u_i}{\text{card}(S(u))} \approx \sum_{i \in R_j}\frac{ u_i}{\text{card}(R_j)}$ 对于大多数 $j$ ，我们可以将 SLOPE ONE 方案的预测公式简化为： $P^{S1}(u)_j = \bar{u} + \frac{1}{\text{card}(R_j)} \sum_{i \in R_j} \text{dev}_{j,i}$

值得注意的是，我们实现的 SLOPE ONE 不依赖于用户如何对单个项目进行评分，而仅依赖于用户的平均评分，以及用户评分的项目。

权重 WEIGHTED SLOPE ONE

SLOPE ONE 的一个缺点是没有考虑观察到的评分数目。直观地说，为了预测用户 $A$ 对项目 $L$ 的评分，给定用户 $A$ 对项目 $J$ 和 $K$ 的评分，如果 $2000$ 名用户对项目 $J$ 和 $L$ 进行了评分，而只有 $20$ 名用户对项目 $K$ 和 $L$ 进行了评分，那么用户 $A$ 对项目 $J$ 的评分很可能是项目 $L$ 的一个更好的预测指标，而不是用户 $A$ 对项目 $K$ 的评分。因此，我们将 WEIGHTED SLOPE ONE 预测定义为以下加权平均值：

P^{wS1}(u)_j = \frac{\sum_{i \in S(u) - \{ j \}} (\text{dev}_{j,i} + u_i) c_{j,i}}{\sum_{i \in S(u) - \{ j \}} c_{j,i}}

其中 $c_{j,i} = \text{card}(S_{j,i}(\chi))$ 。

BI-POLAR SLOPE ONE 双极SLOPE ONE

加权有助于优先考虑频繁出现的评分而非不频繁的评分模式，现在将考虑优先考虑另一种特别相关的评分模式。通过将预测分为两部分来实现这一点。使用 WEIGHTED SLOPE ONE 算法，我们从用户喜欢的项目中推导出一个预测，并从用户不喜欢的项目中推导出另一个预测。

给定一个评分范围，例如从 $0$ 到 $10$ ，使用中间值 $5$ 作为阈值并认为评分高于 $5$ 的项目是喜欢的，评分低于 $5$ 的项目是不喜欢的，这似乎是合理的。如果用户的评分分布均匀，这种方法会很好。然而，在 EachMovie 数据中，超过 70% 的评分高于中间值。因为我们希望支持所有类型的用户，包括平衡型、乐观型、悲观型和双峰型用户，我们将用户的平均评分作为用户喜欢和不喜欢的项目的阈值。例如，乐观的用户，他们喜欢他们评分的每个项目，被假设为不喜欢评分低于他们平均评分的项目。这个阈值确保我们的算法对每个用户都有合理数量的喜欢和不喜欢的项目。

通常我们基于用户（如用户 $A$ ）对项目 $I$ 和 $J$ 的评分偏差来预测用户 $B$ 对项目 $J$ 的评分。双极性 SLOPE ONE 方案进一步限制了用于预测的评分集。首先，在项目方面，只考虑两个喜欢项目之间的偏差或两个不喜欢项目之间的偏差。其次，在用户方面，只有那些对项目 $I$ 和 $J$ 都进行了评分并且对项目 $I$ 有相同喜欢或不喜欢的用户对用于预测项目 $J$ 的评分。

将每个用户分为用户喜欢和用户不喜欢实际上使用户数量翻倍。然而，注意到上述双极性限制必然减少了用于计算预测的评分总数。尽管在数据稀疏性问题的情况下，这种减少可能会导致准确性的提高似乎是反直觉的，但未能过滤掉不相关的评分可能会证明更加成问题。至关重要的是，双极性 SLOPE ONE 方案不会从用户 $A$ 喜欢项目 $K$ 而用户 $B$ 不喜欢同一项目 $K$ 的事实中进行预测。

形式化描述

我们将每个评估 $u$ 分成两个评分项目集合：

$S_{\text{like}}(u) = \{ i \in S(u) \mid u_i > \bar{u} \}$ 、 $S_{\text{dislike}}(u) = \{ i \in S(u) \mid u_i < \bar{u} \}$

对于每一对项目 $i, j$ ，我们将所有评估 $\chi$ 分成两个集合：

$S_{i,\text{like},j} = \{ u \in \chi \mid i, j \in S_{\text{like}}(u) \}$ 、 $S_{i,\text{dislike},j} = \{ u \in \chi \mid i, j \in S_{\text{dislike}}(u) \}$

使用这两个集合，我们计算以下喜欢项目和不喜欢项目的偏差矩阵：

\text{dev}_{\text{like},j,i} = \frac{\sum_{u \in S_{j,\text{like},i}(\chi)} (u_j - u_i)}{\text{card}(S_{j,\text{like},i}(\chi))}

基于项目 $i$ 的评分对项目 $j$ 的预测是：

$p_{\text{like},j,i} = \text{dev}_{\text{like},j,i} + u_i$ 或 $p_{\text{dislike},j,i} = \text{dev}_{\text{dislike},j,i} + u_i$

取决于 $i$ 属于 $S_{\text{like}}(u)$ 还是 $S_{\text{dislike}}(u)$ 。

双极性 SLOPE ONE 方案由以下公式给出：

P_{\text{bpS1}}(u)_j = \frac{\sum_{i \in S_{\text{like}}(u) - \{ j \}} p_{\text{like},j,i} c_{\text{like},j,i} + \sum_{i \in S_{\text{dislike}}(u) - \{ j \}} p_{\text{dislike},j,i} c_{\text{dislike},j,i}}{\sum_{i \in S_{\text{like}}(u) - \{ j \}} c_{\text{like},j,i} + \sum_{i \in S_{\text{dislike}}(u) - \{ j \}} c_{\text{dislike},j,i}}

其中权重 $c_{\text{like},j,i} = \text{card}(S_{j,\text{like},i})$ 和 $c_{\text{dislike},j,i} = \text{card}(S_{j,\text{dislike},i})$ 类似于 WEIGHTED SLOPE ONE 方案中的权重。

代码

数据

"""
2005-Slope One Predictors for Online Rating-Based Collaborative Filtering
Code Reproduction
"""

import os
import sys

sys.path.append(os.path.join(os.path.dirname(__file__), ".."))

import copy
import pandas as pd
import numpy as np
from util import sprint
from tqdm import tqdm

data_path = "../DATASETS/MovieLens100K/u.data"
raw = pd.read_csv(
    data_path,
    sep="\t",
    header=None,
    names=["user_id", "item_id", "rating", "timestamp"],
)
sprint(raw.head(), raw.shape)

# Create user-item matrix
n_users = raw.user_id.unique().shape[0]
n_items = raw.item_id.unique().shape[0]
sprint("Number of users =", n_users)
sprint("Number of items =", n_items)

data = copy.deepcopy(raw)
data = data.sort_values(by=["user_id", "item_id"])

ratings = np.zeros((n_users, n_items))
for row in raw.itertuples():
    ratings[row[1] - 1, row[2] - 1] = row[3]
sprint(ratings, ratings.shape)


# deviations
def deviations(ratings):
    n_users, n_items = ratings.shape
    dev = np.zeros((n_items, n_items))
    freq = np.zeros((n_items, n_items))

    for u in tqdm(range(n_users)):
        rated_items = np.where(ratings[u] > 0)[0]
        for i in rated_items:
            for j in rated_items:
                if i != j:
                    dev[i, j] += ratings[u, i] - ratings[u, j]
                    freq[i, j] += 1

    for i in tqdm(range(n_items)):
        for j in range(n_items):
            if freq[i, j] > 0:
                dev[i, j] /= freq[i, j]

    return dev, freq


# slope one
def slope_one_predict(ratings, deviations, frequencies):
    n_users, n_items = ratings.shape
    predictions = np.zeros((n_users, n_items))

    for u in tqdm(range(n_users)):
        rated_items = np.where(ratings[u] > 0)[0]
        u_bar = np.mean(ratings[u, rated_items])
        for j in range(n_items):
            if j not in rated_items:
                sum_card = np.sum(frequencies[rated_items, j])
                if sum_card != 0:
                    predictions[u, j] = (
                        u_bar + np.sum(deviations[rated_items, j]) / sum_card
                    )

    return predictions


# weighted slope one
def weighted_slope_one_predict(ratings, deviations, frequencies):
    n_users, n_items = ratings.shape
    predictions = np.zeros((n_users, n_items))

    for u in tqdm(range(n_users)):
        rated_items = np.where(ratings[u] > 0)[0]
        for j in range(n_items):
            if j not in rated_items:
                sum_card = np.sum(frequencies[rated_items, j])
                if sum_card != 0:
                    predictions[u, j] = (
                        np.sum(
                            (deviations[rated_items, j] + ratings[u, rated_items])
                            * frequencies[rated_items, j]
                        )
                        / sum_card
                    )
    return predictions


# bi-polar slope one
# if rating is greater than 3, it is positive
# if rating is less than 3 and greater than 0, it is negative
like_dislike_threshold = 3

like_ratings = ratings.copy()
like_ratings = np.where(like_ratings < like_dislike_threshold, 0, like_ratings)

dislike_ratings = ratings.copy()
dislike_ratings = np.where(
    dislike_ratings >= like_dislike_threshold, 0, dislike_ratings
)
sprint(like_ratings, like_ratings.shape)
sprint(dislike_ratings, dislike_ratings.shape)

like_dev_matrix, like_freq_matrix = deviations(like_ratings)
dislike_dev_matrix, dislike_freq_matrix = deviations(dislike_ratings)


def bi_polar_slope_one_predict(
    like_ratings, dislike_ratings, like_dev, like_freq, dislike_dev, dislike_freq
):
    n_users, n_items = like_ratings.shape
    predictions = np.zeros((n_users, n_items))

    for u in tqdm(range(n_users)):
        rated_items = np.where(like_ratings[u] > 0)[0]
        for j in range(n_items):
            if j not in rated_items:
                sum_card = np.sum(
                    like_freq[rated_items, j] + dislike_freq[rated_items, j]
                )
                if sum_card != 0:
                    predictions[u, j] = (
                        np.sum(
                            (like_dev[rated_items, j] + like_ratings[u, rated_items])
                            * like_freq[rated_items, j]
                            + (
                                dislike_dev[rated_items, j]
                                + dislike_ratings[u, rated_items]
                            )
                            * dislike_freq[rated_items, j]
                        )
                        / sum_card
                    )
    return predictions


deviations_matrix, frequencies_matrix = deviations(ratings)
sprint(deviations_matrix, deviations_matrix.shape)
sprint(frequencies_matrix, frequencies_matrix.shape)
slope_one_predict_res = slope_one_predict(
    ratings, deviations_matrix, frequencies_matrix
)
sprint(slope_one_predict_res, slope_one_predict_res.shape)

weighted_slope_one_predict_res = weighted_slope_one_predict(
    ratings, deviations_matrix, frequencies_matrix
)
sprint(weighted_slope_one_predict_res, weighted_slope_one_predict_res.shape)

bi_polar_slope_one_predict_res = bi_polar_slope_one_predict(
    like_ratings, dislike_ratings, like_dev_matrix, like_freq_matrix, dislike_dev_matrix, dislike_freq_matrix
)
sprint(bi_polar_slope_one_predict_res, bi_polar_slope_one_predict_res.shape)

2005 - Slope one CF