2001 - Item based Collaborative Filtering Recommendation Algorithms

论文原文 -> 链接

文章引言

推荐系统应用知识发现技术，在实时交互过程中为用户提供个性化的信息、产品或服务推荐。这些系统，尤其是基于k近邻协同过滤的系统，在网络上取得了广泛的成功。近年来，可用信息量的巨大增长以及访问网站的访客数量的增加，给推荐系统带来了一些关键挑战。这些挑战包括：生成高质量的推荐、每秒为数百万用户和项目执行大量推荐，以及在数据稀疏的情况下实现高覆盖率。在传统的协同过滤系统中，工作量随着系统中参与者数量的增加而增加。我们需要新的推荐系统技术，能够快速生成高质量的推荐，即使面对非常大的规模问题。为了解决这些问题，我们探索了基于项目的协同过滤技术。基于项目的技术首先分析用户-项目矩阵，以识别不同项目之间的关系，然后利用这些关系间接为用户计算推荐。

本文分析了不同的基于项目的推荐生成算法。我们研究了计算项目间相似性的不同技术（例如，项目间相关性与项目向量之间的余弦相似性），以及从这些相似性中获取推荐的不同技术（例如，加权和与回归模型）。最后，我们通过实验评估了我们的结果，并将其与基本的k近邻方法进行了比较。我们的实验表明，基于项目的算法在性能上显著优于基于用户的算法，同时在质量上也优于现有的最佳基于用户的算法。

文献综述

贝叶斯网络：

贝叶斯网络在「用户偏好变化」相对于「模型更新所需时间较慢」的环境中是实用的，但不适用于用户偏好模型必须快速或频繁更新的环境。

聚类算法：

聚类技术通过识别具有相似偏好的「用户群」来工作。一旦创建了聚类，就可以通过平均该聚类中其他用户的意见来为个人做出预测。
预测是跨聚类的平均值，根据参与程度加权。聚类技术通常比其他方法产生较少的个性化推荐，并且在某些情况下，聚类的准确性比最近邻算法差
然而，一旦完成聚类，性能可能会非常好，因为必须分析的组的大小要小得多
聚类技术也可以作为「最近邻算法」中「缩小候选集」的“第一步”或用于在多个推荐引擎之间分配最近邻计算

图算法：

Horting 是一种基于图的技术，其中节点是用户，节点之间的边表示两个用户之间的相似程度
预测是通过在图上行走以到达附近的节点并结合附近用户的意见来生成的

文章贡献点

本文主要有三个研究贡献：

分析了基于项目的预测算法，并识别了实现其子任务的不同方法。
提出了一个预计算的项目相似性模型，以提高基于项目的推荐系统的在线可扩展性。
对几种不同的基于项目的算法与经典的基于用户的（最近邻）算法进行了质量上的实验比较。

文章核心

Item相似性的计算

在基于物品的协同过滤算法中，一个关键步骤是计算物品之间的相似度，然后选择最相似的物品。计算两个物品 $i$ 和 $j$ 之间相似度的基本思路是首先找出对这两个物品都进行了评分的用户，然后应用相似度计算技术来确定相似度 $s_{ij}$ 。其中矩阵的行代表用户，列代表物品。

余弦相似度

基于余弦的相似度公式如下：

\text{sim}(i, j) = \cos(\vec{i}, \vec{j}) = \frac{\vec{i} \cdot \vec{j}}{\|\vec{i}\|_2 \cdot \|\vec{j}\|_2}

其中， $\cdot$ 表示两个向量的点积， $\|\vec{i}\|_2\$ 和 $\|\vec{j}\|_2\$ 分别表示向量 $\vec{i}$ 和 $\vec{j}$ 的欧几里得范数（即向量的模）。

基于相关性的相似度

基于皮尔逊相关系数的相似度公式如下：

\text{sim}(i, j) = \frac{\sum_{u \in U} (R_{u,i} - \bar{R}_i)(R_{u,j} - \bar{R}_j)}{\sqrt{\sum_{u \in U} (R_{u,i} - \bar{R}_i)^2} \cdot \sqrt{\sum_{u \in U} (R_{u,j} - \bar{R}_j)^2}}

其中：

$R_{u,i}$ 表示用户 $u$ 对物品 $i$ 的评分。
$\bar{R}_i$ 表示物品 $i$ 的平均评分。
$U$ 表示同时对物品 $i$ 和 $j$ 进行评分的用户集合。

调整后的余弦相似度

在基于用户的协同过滤（User-based CF）和基于物品的协同过滤（Item-based CF）中，相似度计算的一个基本区别在于：在基于用户的协同过滤中，相似度是沿着矩阵的行进行计算的，而在基于物品的协同过滤中，相似度是沿着矩阵的列进行计算的，即共同评分集合中的每一对评分对应于不同的用户。在基于物品的情况下使用基本的余弦度量来计算相似度有一个重要的缺点——没有考虑到不同用户之间评分尺度的差异。调整后的余弦相似度通过从每个共同评分对中减去相应用户的平均评分来弥补这一缺点。

根据描述，调整后的余弦相似度（Adjusted Cosine Similarity）公式如下：

\text{sim}(i, j) = \frac{\sum_{u \in U} (R_{u,i} - \bar{R}_u)(R_{u,j} - \bar{R}_u)}{\sqrt{\sum_{u \in U} (R_{u,i} - \bar{R}_u)^2} \cdot \sqrt{\sum_{u \in U} (R_{u,j} - \bar{R}_u)^2}}

其中：

$R_{u,i}$ 表示用户 $u$ 对物品 $i$ 的评分。
$\bar{R}_u$ 表示用户 $u$ 的平均评分。
$U$ 表示同时对物品 $i$ 和 $j$ 进行评分的用户集合。

调整前后的区别在哪儿？

$\bar{R} _u$ 跟 $\bar{R} _i$ 跟就是最大的区别
按照作者所说的， $\bar{R} _u$ 考虑了「不同用户之间评分尺度的差异」

预测

根据上述信息，预测公式 ( P_{u,i} ) 可以表示为：

P_{u,i} = \frac{\sum_{\text{all similar items, } N} (s_{i,N} \cdot R_{u,N})}{\sum_{\text{all similar items, } N} |s_{i,N}|}

其中：

$s_{i,N}$ 是物品 $i$ 和物品 $N$ 之间的相似度。
$R_{u,N}$ 是用户 $u$ 对物品 $N$ 的评分。
公式中的分子是所有相似物品 $N$ 的评分加权和，权重为相似度 $s_{i,N}$ 。
公式中的分母是所有相似物品 $N$ 的相似度绝对值之和，用于缩放加权和，以确保预测值在预定义的范围内。

代码

数据

https://grouplens.org/datasets/movielens/100k/

"""
2001-Item based Collaborative Filtering Recommendation Algorithms
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

# Load data
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)


# Cosine Similarity
def cosine_similarity(ratings):
    sim = ratings.dot(ratings.T)
    norms = np.array([np.sqrt(np.diagonal(sim))])
    # norms / norms.T == np.outer(norms, norms)
    return sim / norms / norms.T


# ratings is a user-item matrix, so we need to transpose it
cosine_similarity_res = cosine_similarity(ratings.T)
sprint(cosine_similarity_res, cosine_similarity_res.shape)


# Correlation-based Similarity
def pearson_similarity_item(ratings):
    mean_ratings = np.mean(ratings, axis=0)  # 每个物品的平均评分
    ratings_diff = ratings - mean_ratings
    sim = ratings_diff.T.dot(ratings_diff)
    norms = np.array([np.sqrt(np.sum(ratings_diff**2, axis=0))])
    return sim / norms / norms.T


pearson_similarity_item_res = pearson_similarity_item(ratings)
sprint(pearson_similarity_item_res, pearson_similarity_item_res.shape)


# Adjusted Cosine Similarity
def pearson_similarity_item_improve(ratings):
    mean_ratings = np.mean(ratings, axis=1)  # 每个用户的平均评分
    ratings_diff = ratings - mean_ratings[:, np.newaxis]
    sim = ratings_diff.T.dot(ratings_diff)
    norms = np.array([np.sqrt(np.sum(ratings_diff**2, axis=0))])
    return sim / norms / norms.T


pearson_similarity_item_improve_res = pearson_similarity_item_improve(ratings)
sprint(pearson_similarity_item_improve_res, pearson_similarity_item_improve_res.shape)


# Prediction
def predict(ratings, similarity):
    dot = ratings.dot(similarity)
    abs_sim = np.sum(np.abs(similarity), axis=0)
    sprint(dot.shape, abs_sim.shape)
    return dot / abs_sim


cosine_prediction_item = predict(ratings, cosine_similarity_res)
sprint(cosine_prediction_item, cosine_prediction_item.shape)

pearson_prediction_item = predict(ratings, pearson_similarity_item_res)
sprint(pearson_prediction_item, pearson_prediction_item.shape)

pearson_prediction_item_improve = predict(ratings, pearson_similarity_item_improve_res)
sprint(pearson_prediction_item_improve, pearson_prediction_item_improve.shape)

2001 - Item CF