Eliminar eficientemente filas similares de numpy en sentido de la norma L2
Digamos que tengo un array de numpy, con n filas que son de k dimensiones (matriz n x k). Para facilitar la comprensión, n puede representar el número de observaciones, y k representa las diferentes variables.
Cada columna (variable) está estandarizada de modo que sus valores se encuentren entre 0 y 1.
Puedo calcular fácilmente la distancia l2 entre dos filas (observaciones), y podría eliminar una de ellas especificando un umbral, por debajo del cual considero que la distancia l2 es demasiado baja y estas filas son “demasiado similares”.
Sin embargo, ¿puedo hacer esto para todo el conjunto de datos más rápido que O(n^2)? Me parece ingenuo fijar una fila y comprobar las restantes n-1. Incluso si elimino mientras compruebo cada fila, si el número de filas similares es pequeño, todavía estaría en un tiempo O(n^2) básicamente.
Me imagino cada fila como un punto en un espacio de k dimensiones y básicamente colocando una pequeña bola alrededor de cada uno y viendo qué puntos caen dentro de la bola alrededor de otro punto, ¿algo similar a un algoritmo de agrupamiento por medio de medidas?
davy.ai
Sí, hay una forma más rápida de identificar las filas con distancias L2 bajas en un arreglo de numpy. Un enfoque es utilizar un algoritmo de agrupamiento como K-means o DBSCAN para agrupar filas similares juntas. Estos algoritmos pueden manejar datos de alta dimensionalidad e identificar clusters en una complejidad de tiempo lineal o sublineal, dependiendo del algoritmo específico y su implementación.
Una vez que los clusters han sido identificados, puedes elegir una fila representativa (por ejemplo, el centroide de cada cluster) y eliminar las filas restantes dentro de un umbral de distancia determinado. Este enfoque puede reducir significativamente la cantidad de comparaciones por pares necesarias y puede ser mucho más rápido que O(n^2) en la práctica.
Otro enfoque es utilizar una estructura de datos de árbol de bolas o árbol KD para consultar eficientemente los vecinos más cercanos de cada fila. Estas estructuras de datos pueden identificar rápidamente puntos vecinos dentro de una distancia determinada de un punto dado y se pueden utilizar para identificar eficientemente filas similares en un arreglo de numpy.
En general, hay muchas formas de acelerar el proceso de identificar filas similares en un arreglo de numpy, dependiendo de los requisitos y restricciones específicas del problema en cuestión.