K vecino más cercano en python

Question

Me gustaría calcular el vecino más cercano a K en python. ¿Qué biblioteca debería usar?

Answer 1

Creo que deberías usar scikit ann.

Hay un buen tutorial sobre el más cercano 0ightybour here.

De acuerdo con la documentación:

Ann es una envoltura pitón generada TRAGO-aproximado para el vecino más cercano (ANN) Biblioteca (http://www.cs.umd.edu/~mount/ANN/), desarrollado por David M. Monte y Sunil Arya. ann proporciona una implementación kdtree inmutable (a través de ANN) que puede realizar k-vecino más cercano y k aproximado

Answer 2

scipy.spatial.cKDTree es rápido y sólido. Para obtener un ejemplo de su uso para la interpolación NN, consulte (ejem) inverse-distance-weighted-idw-interpolation-with-python en SO.

(si se puede decir por ejemplo: "Tengo puntos 1M en 3D, y quiero k = 5 vecinos más cercanos de 1k nuevos puntos", que podría obtener mejores respuestas o ejemplos de código.
¿Qué desea hacer con los vecinos una vez que los has encontrado?)

Answer 3

Escribí un script para comparar FLANN y scipy.spatial.cKDTree, no pude obtener el contenedor ANN para compilar. Puede probar esto por su cuenta para ver qué funcionará para su aplicación. El cKDTree tuvo un tiempo de ejecución comparable para mi caso de prueba con FLANN, FLANN fue ~ 1.25x más rápido. Cuando aumenté testSize, FLANN fue ~ 2 veces más rápido que cKDTree. Parece que FLANN sería más difícil de integrar dependiendo del proyecto, ya que no forma parte de un paquete python estándar.

import cProfile 
from numpy import random 
from pyflann import * 
from scipy import spatial 

# Config params 
dim = 4 
knn = 5 
dataSize = 1000 
testSize = 1 

# Generate data 
random.seed(1) 
dataset = random.rand(dataSize, dim) 
testset = random.rand(testSize, dim) 

def test1(numIter=1000): 
    '''Test tree build time.''' 
    flann = FLANN() 
    for k in range(numIter): 
     kdtree = spatial.cKDTree(dataset, leafsize=10) 
     params = flann.build_index(dataset, target_precision=0.0, log_level = 'info') 

def test2(numIter=100): 
    kdtree = spatial.cKDTree(dataset, leafsize=10) 
    flann = FLANN() 
    params = flann.build_index(dataset, target_precision=0.0, log_level = 'info') 
    for k in range(numIter): 
     result1 = kdtree.query(testset, 5) 
     result2 = flann.nn_index(testset, 5, checks=params['checks']) 

import cProfile 
cProfile.run('test2()', 'out.prof') 

Answer 4

Es nativa en scipy si usted está mirando para hacer un enfoque kd-árbol: http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html#scipy.spatial.KDTree