Tengo un marco de datos de pandas con 20K filas y 50 columnas. Quiero encontrar los 5 vecinos más cercanos de cada fila dentro de este marco de datos basado en la distancia euclidiana de las columnas. Entonces, el resultado es una matriz de 20K * 5 donde las columnas son identificadores de los vecinos más cercanos en el marco de datos.

Estoy buscando una solución para hacer esto lo más eficiente posible, preferiblemente usando índices proporcionados por pandas, operaciones paralelas u operaciones vectorizadas. Scipy kd-tree fue bastante lento.

¿Alguna idea?

0
Mohammad 24 nov. 2019 a las 04:49

1 respuesta

La mejor respuesta

De hecho, parece que el árbol kd de Scipy es lento para su caso; Se necesitaron alrededor de 80 ms para consultar un solo punto, lo que supongo que lleva a alrededor de 0.08 * 20_000 = 1600s de tiempo de cálculo total para su conjunto de datos completo.

Otra opción para datos de mayor dimensión (como un conjunto de datos con 50 columnas) podría ser Estructura de datos Ball Tree. Como dice la página del enlace:

Debido a la geometría esférica de los nodos del árbol de bolas, puede superar a un árbol KD en grandes dimensiones, aunque el rendimiento real depende en gran medida de la estructura de los datos de entrenamiento.

Jugando con el siguiente código:

from sklearn.neighbors import NearestNeighbors
import numpy as np

arr = np.random.rand(20_000, 50) * 20
nbrs = NearestNeighbors(n_neighbors = 5, algorithm = 'ball_tree').fit(arr)

%timeit nbrs.kneighbors(arr[:10, :])
# 24.6 ms ± 2.24 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit nbrs.kneighbors(arr[:100, :])
# 209 ms ± 22.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit nbrs.kneighbors(arr[:1000, :])
# 2.02 s ± 226 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Al observar estos %timeit resultados, parece que el algoritmo escala de forma lineal, por lo que para 20k filas probablemente pueda esperar que tome alrededor de 20_000 / 1_000 * 2 = ~ 40s. 40 segundos es mucho más rápido que los ~ 1600 que probablemente pueda esperar de la estructura de datos de kd-tree.

Por último, definitivamente sugiero que leas en profundidad la página de vecinos más cercanos para que comprenda completamente todas las complejidades de los algoritmos que ofrecen.

1
natemcintosh 24 nov. 2019 a las 04:04