2003-Amazon recommendations Item-to-item collaborative filtering

论文原文 -> 链接

文件引言

推荐算法最为人所知的应用是在电子商务网站上，它们利用关于客户兴趣的输入来生成推荐商品列表。许多应用程序仅使用客户购买和明确评级的商品来表示他们的兴趣，但它们也可以使用其他属性，包括浏览的商品、人口统计数据、主题兴趣和喜爱的艺术家。在亚马逊网站上，我们使用推荐算法为每位客户个性化在线商店。商店会根据客户兴趣发生根本性变化，向软件工程师展示编程书籍，向新妈妈展示婴儿玩具。点击率和转化率——衡量基于网络和电子邮件广告效果的两个重要指标——远远超过未定向内容，如横幅广告和畅销商品列表。

电子商务推荐算法通常在具有挑战性的环境中运行。例如：

大型零售商可能拥有海量数据，数千万客户和数百万种不同的商品。
许多应用程序要求结果集实时返回，时间不超过半秒，同时仍能生成高质量的推荐。
新客户通常只有极少的信息，仅基于几次购买或产品评级。
老客户可能拥有大量信息，基于数千次购买和评级。
客户数据是易变的：每次互动都提供了宝贵的客户数据，算法必须立即响应新信息。

解决推荐问题有三种常见方法：传统的协同过滤、聚类模型和基于搜索的方法。在这里，我们将这些方法与我们的算法进行比较，我们称之为商品到商品的协同过滤。与传统的协同过滤不同，我们的算法在线计算规模独立于客户数量和产品目录中的商品数量。我们的算法实时生成推荐，可扩展到大规模数据集，并生成高质量的推荐。

「实时推荐」与「能运用到大规模数据集」应该是这篇论文的亮点。

文献综述

传统的协同过滤

传统的协同过滤算法将一个用户表示为一个 $N$ 维的商品向量，其中 $N$ 是商品目录中不同商品的数量
向量对于已购买或正面评价的商品为正，对于负面评价的商品为负。为了补偿畅销商品的影响，算法通常会将向量分量乘以逆频率（即购买或评价该商品的用户数量的倒数），使得不太知名的商品变得更加相关。对于几乎所有用户来说，这个向量非常稀疏
协同过滤生成推荐在计算上是昂贵的。在最坏情况下，它是O(MN)，其中M是用户数量，N是产品目录中的商品数量，因为它检查M个用户，并对每个用户最多检查N个商品。然而，由于平均用户向量非常稀疏，算法的性能往往更接近O(M + N)。扫描每个用户大约是O(M)，而不是O(MN)，因为几乎所有用户向量只包含少量商品，无论目录的大小如何。但有一些用户购买或评价了目录中很大比例的商品，需要O(N)的处理时间。因此，算法的最终性能大约是O(M + N)。
提高性能的方法：
- 随机抽样或丢弃购买量少的用户来减少M，通过丢弃非常受欢迎或不受欢迎的商品来减少N。
- 通过根据产品类别或主题分类对商品空间进行分区，来减少检查的商品数量。
- 降维技术，如聚类和主成分分析，可以大幅减少M或N。
但是会降低算法质量
- 如果算法只检查一小部分用户样本，选定的用户将不太相似于用户。
- 商品空间分区将推荐限制在特定的产品或主题领域。
- 如果算法丢弃最受欢迎或最不受欢迎的商品，它们将永远不会出现在推荐中，而只购买这些商品的用户将不会得到推荐。
- 应用于商品空间的降维技术往往会通过消除低频商品产生相同的效果和副作用。

聚类模型

为了找到与用户相似的用户，聚类模型将用户群体划分为多个细分类别，并将任务视为一个分类问题。
细分类别通常使用聚类或其他无监督学习算法创建，尽管有些算法需要使用手动确定的细分类别的数目。使用相似性度量，聚类算法将最相似的用户分组在一起，形成聚类或细分类别。
在大数据集上进行最优聚类是不切实际的，大多数算法使用各种形式的贪婪聚类生成。这些算法通常从一个初始的细分类别集合开始，这些细分类别通常每个包含一个随机选择的用户。然后，它们反复将用户匹配到现有的细分类别，通常还包含创建新细分类别或合并现有细分类别的机制。
对于非常大的数据集——尤其是高维度的数据集——采样或降维也是必要的。
一旦算法生成了细分类别，它就会计算用户与每个细分类别的汇总向量之间的相似性，然后选择相似性最强的细分类别，并将用户相应地分类。一些算法将用户分类到多个细分类别中，并描述每个关系的强度。
聚类模型比协同过滤具有更好的在线扩展性和性能，因为它们将用户与受控数量的细分类别进行比较，而不是与整个用户群体进行比较。
并且聚类计算是离线运行的。聚类模型将大量用户分组到一个细分类别中，将用户匹配到一个细分类别，然后为了推荐的目的，将该细分类别中的所有用户视为相似用户。
由于聚类模型找到的相似用户并不是最相似的用户，因此它们生成的推荐相关性较低。通过使用大量细粒度的细分类别可以提高质量，但在线用户-细分类别分类的成本几乎与使用协同过滤找到相似用户的成本一样高。

基于搜索

基于搜索或内容的方法将推荐问题视为寻找相关商品的搜索。给定用户的购买和评价商品，算法构建一个搜索查询，以找到由同一作者、艺术家或导演创作的其他热门商品，或具有相似关键词或主题的商品。
例如，如果一个用户购买了《教父》DVD合集，系统可能会推荐其他犯罪剧集、由马龙·白兰度主演的其他剧集，或由弗朗西斯·福特·科波拉执导的其他电影。
如果用户购买或评价的商品很少，基于搜索的推荐算法在扩展性和性能方面表现良好。然而，对于有数千次购买的用户来说，基于所有商品构建查询是不切实际的。算法必须使用数据的子集或摘要，从而降低质量。
在所有情况下，推荐质量都相对较差。推荐往往过于笼统（如最畅销的戏剧DVD标题）或过于狭窄（如同一位作者的所有书籍）。
推荐应该帮助用户找到并发现新的、相关且有趣的商品。由同一作者或同一主题类别的热门商品未能实现这一目标。

核心

基于物品的协同过滤不是将用户与相似的用户匹配，而是将用户购买的和评分的每个物品与相似的物品匹配，然后将这些相似的物品组合成一个推荐列表。
为了确定给定物品的最相似匹配，算法通过查找用户倾向于一起购买的物品来构建一个相似物品表。可以通过遍历所有物品对并为每对物品计算相似度度量来构建一个产品到产品的矩阵。然而，许多产品对没有共同的用户，因此这种方法在处理时间和内存使用方面是低效的。
以下迭代算法通过计算单个产品与所有相关产品之间的相似度提供了一种更好的方法

For each item in product catalog, I1
	For each customer C who purchased I1
		For each item I2 purchased by customer C
			Record that a customer purchased I1 and I2
	For each item I2
		Compute the similarity between I1 and I2

给定一个相似物品表，算法会找到与用户购买和评分的物品相似的物品，聚合这些物品，然后推荐最受欢迎或相关性最高的物品。这种计算非常快速，仅取决于用户购买或评分的物品数量。

代码

数据

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

from collections import defaultdict
import os
import sys

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

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

"""
For each item in product catalog, I1
	For each customer C who purchased I1
		For each item I2 purchased by customer C
			Record that a customer purchased I1 and I2
	For each item I2
		Compute the similarity between I1 and I2
"""

# Load data
"""
use movie lens data
suppose a rating is a purchase
"""
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)

data = copy.deepcopy(raw)


# all products
products = data.item_id.unique()
product = np.sort(products)

product_vector = defaultdict(set)

product_similarity = np.zeros((len(product), len(product)))

# For each item in product catalog, I1
for product_1 in tqdm(product):
    # For each customer C who purchased I1
    users_c = data[data.item_id == product_1].user_id.unique()
    users = np.sort(users_c)
    # For each item I2 purchased by customer C
    for user in users:
        items = data[
            (data.user_id == user) & (data.item_id != product_1)
        ].item_id.unique()
        # Record that a customer purchased I1 and I2
        product_vector[product_1].add(user)
        for product_2 in items:
            product_vector[product_2].add(user)
    # For each item I2
    for product_2 in product_vector:
        if product_1 == product_2:
            continue
        # Compute the similarity between I1 and I2
        # The similarity algorithm could be changed
        similarity = len(product_vector[product_1] & product_vector[product_2]) / len(
            product_vector[product_1] | product_vector[product_2]
        )
        # print(f"Similarity between {product_1} and {product_2} is {similarity}")
        product_similarity[product_1 - 1, product_2 - 1] = similarity
        
sprint(product_similarity, product_similarity.shape)


# ---------------------------------------------------
# accelerate by numpy
# the conclusion is the slower than the pandas version
products = data.item_id.unique()
product = np.sort(products)

product_vector = defaultdict(set)

product_similarity = np.zeros((len(product), len(product)))

np_data = data.to_numpy()
for product_1 in tqdm(product):
    users_c = np_data[np_data[:, 1] == product_1, 0]
    users = np.sort(users_c)
    for user in users:
        items = np_data[
            (np_data[:, 0] == user) & (np_data[:, 1] != product_1), 1
        ]
        product_vector[product_1].add(user)
        for product_2 in items:
            product_vector[product_2].add(user)
    for product_2 in product_vector:
        if product_1 == product_2:
            continue
        similarity = len(product_vector[product_1] & product_vector[product_2]) / len(
            product_vector[product_1] | product_vector[product_2]
        )
        product_similarity[product_1 - 1, product_2 - 1] = similarity
        
sprint(product_similarity, product_similarity.shape)

2003 - Amazon Item CF