python - scikit - nearest neighbor algorithm

Búsqueda de vecino más cercana: Python

Question

Tengo una matriz bidimensional:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
                [6588253.79, 1933602.89, 212.66, 0, 0],
                 etc...)

Los primeros dos elementos MyArray[0] y MyArray[1] son las coordenadas X e Y de los puntos.

Para cada elemento de la matriz, me gustaría encontrar la forma más rápida de devolver su vecino más cercano en un radio de X unidades. Estamos asumiendo que esto es en el espacio 2D.

Digamos para este ejemplo X = 6 .

He resuelto el problema comparando cada elemento con cada otro elemento, pero esto toma aproximadamente 15 minutos cuando tu lista tiene 22k puntos de longitud. Esperamos eventualmente ejecutar esto en listas de alrededor de 30 millones de puntos.

He leído sobre Kd trees y entiendo el concepto básico, pero he tenido problemas para entender cómo escribirlos.

Answer 1

Gracias a John Vinyard por sugerir scipy. Después de algunas buenas investigaciones y pruebas, aquí está la solución a esta pregunta:

Requisitos previos: Instalar Numpy y SciPy

1. Importar los módulos SciPy y Numpy

2. Haga una copia de la matriz de 5 dimensiones incluyendo solo los valores de X e Y.

3. Cree una instancia de un cKDTree como tal:

   YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100)
   #Play with the leafsize to get the fastest result for your dataset

4. Consulte el cKDTree para el vecino más cercano dentro de 6 unidades como tal:

   for item in YourArray:
       TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6)

   para cada elemento en YourArray , TheResult será una tupla de la distancia entre los dos puntos y el índice de la ubicación del punto en YourArray .