¿Cuál es la forma más eficiente de calcular la distancia (euclidiana) del vecino más cercano para cada punto de una matriz?

Tengo una lista de 100k (X, Y, Z) puntos y me gustaría calcular una lista de distancias vecinas más cercanas. El índice de la distancia correspondería al índice del punto.

He investigado PYOD y escaneo de vecinos, pero parece que requieren "enseñanza". Creo que mi problema es más simple que eso. Para cada punto: encuentre el vecino más cercano, calcule la distancia.

Datos de ejemplo:

points = [
     (0             0   1322.1695
      0.006711111   0   1322.1696
      0.026844444   0   1322.1697
      0.0604        0   1322.1649
      0.107377778   0   1322.1651
      0.167777778   0   1322.1634
      0.2416        0   1322.1629
      0.328844444   0   1322.1631
      0.429511111   0   1322.1627...)]

Calcular k = 1 distancias vecinas más cercanas

Formato de resultado:

results = [nearest neighbor distance]

Resultados de ejemplo:

results = [
0.005939372
0.005939372
0.017815632
0.030118587
0.041569616
0.053475883
0.065324964
0.077200014
0.089077602)
]

Actualizar:

He implementado dos de los enfoques sugeridos.

  1. Use scipy.spatial.cdist para calcular las matrices de distancias completas
  2. Use un vecino X más cercano en el radio R para encontrar un subconjunto de distancias vecinas para cada punto y devolver el más pequeño.

Los resultados son que el Método 2 es más rápido que el Método 1, pero tomó mucho más esfuerzo implementarlo (tiene sentido).

Parece que el factor limitante para el Método 1 es la memoria necesaria para ejecutar el cálculo completo, especialmente cuando mi conjunto de datos se acerca a 10 ^ 5 (x, y, z) puntos. Para mi conjunto de datos de 23k puntos, toma ~ 100 segundos capturar las distancias mínimas.

Para el método 2, la velocidad se escala como n_radius ^ 2. Es decir, "radio vecino al cuadrado", lo que realmente significa que el algoritmo escala ~ linealmente con el número de vecinos incluidos. Usando un Radio de ~ 5 (más que suficiente aplicación dada), tardó 5 segundos, para el conjunto de 23k puntos, para proporcionar una lista de minutos en el mismo orden que los propios point_list. La matriz de diferencia entre la "solución exacta" y el Método 2 es básicamente cero.

Gracias por la ayuda de todos!

0
Cole Pierson 3 oct. 2019 a las 21:15

3 respuestas

La mejor respuesta

Similar a la respuesta de Caleb, pero podría detener el ciclo iterativo si obtiene una distancia mayor que alguna distancia mínima anterior (lo siento, no hay código).

Solía programar videojuegos. Se necesitaría demasiada CPU para calcular la distancia real entre dos puntos. Lo que hicimos fue dividir la "pantalla" en cuadrados cartesianos más grandes y evitar el cálculo de la distancia real si el Delta-X o Delta-Y estaba "demasiado lejos" - Eso es solo resta, así que tal vez algo así para calificar donde el Euclediano real ¿Se necesita un cálculo métrico de distancia (se extiende a n dimensiones según sea necesario)?

EDITAR: expandir los comentarios de selección de pares de candidatos "demasiado lejos". Por brevedad, asumiré un paisaje 2D. Tome el punto de interés (X0, Y0) y "dibuje" un cuadrado nxn alrededor de ese punto, con (X0, Y0) en el origen.

Revise la lista inicial de puntos y forme una lista de puntos candidatos que estén dentro de ese cuadrado. Al hacerlo, si el DeltaX [ABS (Xi-X0)] está fuera del cuadrado, no hay necesidad de calcular el DeltaY.

Si no hay puntos candidatos, agrande el cuadrado e itere.

Si hay exactamente un punto candidato y está dentro del radio del círculo incrustado por el cuadrado, ese es su mínimo.

Si hay "demasiados" candidatos, reduzca el cuadrado, pero solo necesita volver a examinar la lista de candidatos desde esta iteración, no todos los puntos.

Si no hay "demasiados" candidatos, calcule la distancia para esa lista. Al hacerlo, primero calcule DeltaX ^ 2 + DeltaY ^ 2 para el primer candidato. Si para candidatos posteriores el DetlaX ^ 2 es mayor que el minumin hasta ahora, no es necesario calcular el DeltaY ^ 2.

El mínimo de ese cálculo es el mínimo si está dentro del radio del círculo inscrito por el cuadrado.

De lo contrario, debe volver a una lista de candidatos anterior que incluya puntos dentro del círculo que tenga el radio de ese mínimo. Por ejemplo, si terminó con un candidato en un cuadrado de 2x2 que resultó estar en el vértice X = 1, Y = 1, la distancia / radio sería SQRT (2). Regrese a una lista de candidatos anterior que tenga un cuadrado mayor o igual a 2xSQRT (2).

Si se justifica, genere una nueva lista de candidatos que solo incluya puntos dentro del cuadrado +/- SQRT (2). Calcule la distancia para esos puntos candidatos como se describió anteriormente, omitiendo cualquiera que exceda el mínimo calculado hasta ahora.

No es necesario hacer la raíz cuadrada de la suma del Delta ^ 2 hasta que tenga un solo candidato.

Cómo dimensionar el cuadrado inicial, o si debería ser un rectángulo, y cómo aumentar o disminuir el tamaño del cuadrado / rectángulo podría verse influenciado por el conocimiento de la aplicación de la distribución de datos.

Consideraría algoritmos recursivos para algo de esto si el lenguaje que está utilizando lo admite.

0
Mark Diaz 19 oct. 2019 a las 19:13

¿Qué te parece esto?

from scipy.spatial import distance

A = (0.003467119 ,0.01422762 ,0.0101960126)
B = (0.007279433  ,0.01651597  ,0.0045558849)
C = (0.005392258  ,0.02149997  ,0.0177409387)
D = (0.017898802  ,0.02790659  ,0.0006487222)
E = (0.013564214  ,0.01835688  ,0.0008102952)
F = (0.013375397  ,0.02210725 ,0.0286032185)

points = [A, B, C, D, E, F]
results = []
for point in points:
    distances = [{'point':point, 'neighbor':p, 'd':distance.euclidean(point, p)} for p in points if p != point]
    results.append(min(distances, key=lambda k:k['d']))

Los resultados serán una lista de objetos, como este:

results = [
    {'point':(x1, y1, z1), 'neighbor':(x2, y2, z2), 'd':"distance from point to neighbor"},
...]

Donde point es el punto de referencia y neighbor es el vecino más cercano al punto.

0
Reinstate Monica 3 oct. 2019 a las 18:36

La opción más rápida disponible para usted puede ser scipy.spatial.distance.cdist, que encuentra las distancias por pares entre todos los puntos en su entrada. Si bien encontrar todas esas distancias puede no ser el algoritmo más rápido para encontrar los vecinos más cercanos, cdist se implementa en C, por lo que es probable que se ejecute más rápido que cualquier cosa que intente en Python.

import scipy as sp
import scipy.spatial
from scipy.spatial.distance import cdist

points = sp.array(...)
distances = sp.spatial.distance.cdist(points)

# An element is not its own nearest neighbor
sp.fill_diagonal(distances, sp.inf)

# Find the index of each element's nearest neighbor
mins = distances.argmin(0)

# Extract the nearest neighbors from the data by row indexing
nearest_neighbors = points[mins, :]

#  Put the arrays in the specified shape
results = np.stack((points, nearest_neighbors), 1)

Teóricamente, podría hacer que esto se ejecute más rápido (principalmente combinando todos los pasos en un algoritmo), pero a menos que esté escribiendo en C, no podrá competir con SciPy / NumPy.

(cdist se ejecuta en Θ (n 2 ) tiempo (si el tamaño de cada punto es fijo), y en cualquier otra parte del algoritmo en tiempo O (n), así que incluso si intentaste optimizar el código en Python, no notarías el cambio para pequeñas cantidades de datos, y las mejoras quedarían ensombrecidas por cdist para obtener más datos).

0
jirassimok 5 oct. 2019 a las 20:03
58224771