Python中的K最近邻算法

Question

我想在Python中计算K最近邻居算法，应该使用哪个库？

- sramij

Answer 1

我认为你应该使用scikit ann。

这里有一个关于最近邻的好教程：这里。

根据文档：

ann是Approximate Nearest Neighbor（ANN）库的SWIG生成的Python包装器（http://www.cs.umd.edu/~mount/ANN/），由David M. Mount和Sunil Arya开发。ann提供了一个不可变的kdtree实现（通过ANN），可以执行k-nearest neighbor和approximate k

- Sandro Munda

---

+1 这个库非常易于使用。 - Björn Lindqvist

scikit.ann和scikit-learn不是同一个东西。即使使用easy_install编译scikit.ann也很困难（因为它需要swig），所以scikit-learn是更好的解决方案。 - mrgloom

scikit ann 的链接已经失效。 - Rose Perrone

ANN和KNN不同（这个问题最初是关于KNN的）。 - Rajarshee Mitra

Answer 2

以下是一个脚本，用于比较scipy.spatial.cKDTree和pyflann.FLANN。您可以自行测试并确定哪个更适合您的应用程序。

import cProfile
import numpy as np
import os
import pyflann
import scipy.spatial

# Config params
dim = 4
data_size = 1000
test_size = 1

# Generate data
np.random.seed(1)
dataset = np.random.rand(data_size, dim)
testset = np.random.rand(test_size, dim)

def test_pyflann_flann(num_reps):
    flann = pyflann.FLANN()
    for rep in range(num_reps):
        params = flann.build_index(dataset, target_precision=0.0, log_level='info')
        result = flann.nn_index(testset, 5, checks=params['checks'])

def test_scipy_spatial_kdtree(num_reps):
    flann = pyflann.FLANN()
    for rep in range(num_reps):
        kdtree = scipy.spatial.cKDTree(dataset, leafsize=10)
        result = kdtree.query(testset, 5)

num_reps = 1000
cProfile.run('test_pyflann_flann(num_reps); test_scipy_spatial_kdtree(num_reps)', 'out.prof')
os.system('runsnake out.prof')

- Chris Flesher

Answer 3

scipy.spatial.cKDTree 是一个快速且稳定的工具。如果您需要使用它进行最近邻插值的示例，请参见 Stack Overflow 上的 inverse-distance-weighted-idw-interpolation-with-python。

（如果您能说出例如“我有 1M 个三维点，并希望找到 1k 个新点的 k=5 个最近邻居”，您可能会得到更好的答案或代码示例。
一旦找到邻居，您想要用它们做什么？）

- denis

Answer 4

如果您想使用kd-tree方法，可以在scipy中本地实现：http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html#scipy.spatial.KDTree

- Max Bileschi