python - 如何使用Scipy的Kd-tree函数来加速K-Nearest Neighbors(KNN)

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 5 年前。

Improve this question

我正在寻找使用Scipy's Kd-tree加速 KNN 搜索，但我不清楚如何格式化数据以 1)- 创建树和 2)- 使用树来加速我的搜索。

为了详细说明，我有一个 Netflix 训练数据的 pandas 数据框，它由用户列、他们评分的每个电影项目以及他们给出的评分组成(见下文)。使用此训练数据，我现在通过计算测试用户的最近邻 (KNN) 来预测测试用户的评分。最近邻是使用 PIL 逊相关系数计算的，而不是欧氏距离。一旦计算出最近的邻居，我想使用最近的邻居来预测/猜测测试用户的评分。

但是，我的用户和电影列表很大(Netflix 数据)，计算数千部电影中数千名用户的最近邻居在计算上变得不可行。 Kd 树方法已被建议作为加速 K 最近邻的方法。

有没有办法使用 Scipy 的 Kd 树来加速这种方法？如果是这样，数据需要采用什么格式才能利用 Kd 树方法？我知道有一个内置的 Ski-kit 学习功能可以解决这个问题，但我需要能够独立实现它。

Goal: predict user 1 rating on movie 10 by finding most similar users 

Training data
user    movie   rating
2         7      5.0
3        10      3.0
4         4      1.0
50     3363      2.0
50       7       3.0
83      50       4.0
83       7       5.0
etc

Answer 1

Scipy 的 KD 树仅支持 p-范数度量(例如 p=2 是标准欧几里德距离)。如果您想要更一般的指标，scikit-learn 的 BallTree支持许多不同的指标。特别是correlation metric与 Pearson 相关系数相关，因此您可以使用该指标将您的算法建立在高效搜索的基础上。

也就是说，如果有数千个维度，基于树的方法通常并不比暴力破解更好。更好的是使用某种近似算法，例如局部敏感哈希，以及为相关距离设计的哈希函数。