题解思路

构建用户-商品矩阵

首先将输入的用户购买历史转换为用户–商品的二值矩阵。行表示用户，列表示商品，如果用户购买过该商品则对应位置为1，否则为0。

计算Cosine相似度与KNN邻居

使用 scikit-learn 的 NearestNeighbors，设置

• metric='cosine'（返回的距离为 1−cosine_similarity）
• algorithm='brute'
• n_neighbors=4（包括自身在内共4个邻居）

对每个用户调用 kneighbors 得到最近4个邻居，排除自身后实际使用3个邻居，并将距离转换为相似度：

sim = 1.0 - distance

生成推荐

对于每个用户：

1. 遍历3个邻居，将邻居购买但当前用户未购买的商品作为候选
2. 对每个候选商品，记录其与当前用户之间的最大相似度
3. 从候选集中选出相似度最高的商品；若存在多件，则取商品ID最小者
4. 若无任何候选商品，则输出 None，相似度设为 0.000

复杂度分析

• 构建矩阵耗时 $O(NM)$，其中 $N$ 为用户数，$M$ 为商品数。
• KNN 基于 brute force，计算所有用户间距离，时间复杂度 $O(N^2M)$。
• 最后生成推荐阶段，遍历每个用户的3个邻居并筛选商品，时间 $O(NKQ)$（$K=3$，$Q$ 为平均邻居商品数）。
• 整体时间复杂度以 $O(N^2M)$ 为主；空间复杂度为 $O(NM)$。

Python代码

```python
import sys
import numpy as np
from sklearn.neighbors import NearestNeighbors

def main():
    raw = eval(sys.stdin.read())  # 读取输入
    uids = [u[0] for u in raw]
    its = [u[1] for u in raw]

    # 构建商品ID到列索引的映射
    unis = sorted({x for lst in its for x in lst})
    m = {v: i for i, v in enumerate(unis)}

    # 构造用户-商品二值矩阵
    X = np.zeros((len(raw), len(unis)), dtype=int)
    for i, lst in enumerate(its):
        for item in lst:
            X[i, m[item]] = 1

    # KNN模型：包括自身共4个邻居，排除自身后实际使用3个
    knn = NearestNeighbors(n_neighbors=4, metric='cosine', algorithm='brute')
    knn.fit(X)
    dists, idxs = knn.kneighbors(X)

    # 对每个用户生成推荐
    for i, uid in enumerate(uids):
        nbrs = idxs[i][1:]      # 排除自身
        sims = 1 - dists[i][1:] # 转换为Cosine相似度
        seen = set(its[i])
        cand = {}
        # 收集候选商品并记录最大相似度
        for nj, sim in zip(nbrs, sims):
            for item in its[nj]:
                if item not in seen:
                    # 如果商品还没在 cand 中，或者相似度更高，就更新
                    if item not in cand or sim > cand[item]:
                        cand[item] = sim

        # 选择推荐或输出None
        if cand:
            max_sim = max(cand.values())
            rec = min([it for it, s in cand.items() if s == max_sim])
            sc = max_sim
        else:
            rec, sc = None, 0.0

        # 输出格式：[用户ID,推荐商品ID或None,相似度保留3位]
        print(f"[{uid}, {rec}, {sc:.3f}]")

if __name__ == '__main__':
    main()

题目内容

某电子商务平台希望使用机器学习来改善用户的购物体验。他们收集了用户的购买历史数据，希望你 能构建一个推荐系统，为用户推荐他们可能喜欢的商品。

你的任务是，使用$scikit-learn$库，基于用户的购买历史数据，构建一个基于$K$最近邻$(KNN)$的推荐系统，并使用$Cosine$相似度来评估模型的性能。

要求:

$1$.首先要计算用户之间的$Cosine$相似度矩阵，然后在推荐系统中使用基于$KNN$的方法，并且将 $KNN$的距离度量设置为$cosine$。

$2$.$KNN$的邻居数量n_neighbors参数设为$4$，其中包括用户自己，最后在生成推荐时排除自己(即实 际使用$3$个邻居)。

$3$.推荐的商品必须是用户尚未购买过的商品(即排除已购买的商品)。

$4$.如果没有合适的商品推荐(例如用户的邻居没有新商品)，输出结果中应显示$None$和相似度为$0.0$。

$5$.相同相似度情况下，取$ID$最小的商品。

输入描述

输入是一个$list$，每个元素是一个包含两个元素的$list$，第一个元素是用户$ID$，第二个元素是该用户 购买过的商品$ID$的列表。

输出描述

输出是一个$list$，包含三个元素，第一个元素是用户$ID$，第二个元素是预测的用户可能喜欢的商品 $ID$，第三个元素是预测的$Cosine$相似度，保留小数点后$3$位有效数字。

补充说明

(1)可以使用形如$numpy、pandas、sklearn$的第三方代码库。

(2)为了保证唯一性，请严格遵循输入输出描述进行作答。

(3)形如 $sys.stdin$等方法结合$for$循环和$eval$函数即可读取并还原输入数据。

(4)算法使用$brute$，最近邻数量设置为$3$。

样例1

输入

[[1, [101, 102, 103]], [2, [101, 104]], [3, [102, 103, 105]], [4, [101, 103, 105]]]

输出

[1, 105, 0.667]
[2, 102, 0.408]
[3, 101, 0.667]
[4, 102, 0.667]