Descarga knn search algorithm comparison - Código fuente knn search algorithm comparison Descargar

knn search algorithm comparison

Otro código fuente

1.0.0

Descargar

Comparación de algoritmo de búsqueda de KNN

El algoritmo de vecinos K-Nears (K-NN), introducido en 1951, se ha utilizado ampliamente para tareas de clasificación y regresión. El concepto central implica identificar las K más similares (vecinos) a un punto de consulta dado dentro de un conjunto de datos y usar estos vecinos para hacer predicciones o clasificaciones. En los últimos años, la importancia de las bases de datos vectoriales e índices de vectores ha crecido, particularmente para la recuperación de la información para admitir modelos de idiomas grandes (LLM) en el procesamiento de conjuntos de datos extensos de texto y otros datos. Un ejemplo destacado de esta aplicación es la generación de recuperación de la generación (RAG).

Este proyecto compara el rendimiento de diferentes algoritmos de búsqueda de K-NN en varios tamaños de datos y dimensiones. Los algoritmos comparados son:

Árbol kd
Bola
Fuerza bruta (KNN completo)
HNSW (mundo pequeño jerárquico navegable)

Explicaciones de algoritmo

Kd-tree (árbol k-dimensional):
- Una estructura de datos de partición espacial para organizar puntos en un espacio K-dimensional.
- Construye un árbol binario dividiendo recursivamente el espacio a lo largo de diferentes dimensiones.
- Eficiente para espacios de baja dimensión (típicamente <20 dimensiones).
- Complejidad promedio de tiempo para la búsqueda: o (log n), donde n es el número de puntos.
- Menos efectivo en espacios de alta dimensión debido a la "maldición de la dimensionalidad". Ejemplo: en un espacio 2D, un árbol KD podría dividir el plano verticalmente, luego horizontalmente, alternando en cada nivel:
```
   y
   |
4  |    C
   |  A   D
2  |    B
   |___________
   0    2    4  x
```
Puntos: A (1,3), B (3,1), C (4,3), D (3,3) Estructura del árbol: Raíz (x = 2) -> Izquierda (y = 2) -> Derecha (x = 3)
Árbol de pelota:
- Una estructura de datos de árbol binario que divide apunta a hiperesfrees anidados.
- Cada nodo representa una pelota (hiperesfera) que contiene un subconjunto de los puntos.
- Más efectivo que el árbol KD para espacios de alta dimensión.
- Complejidad promedio de tiempo para la búsqueda: O (log n), pero con factores constantes más altos que el árbol KD.
- Generalmente funciona mejor que KD-Tree cuando dimensiones> 20. Ejemplo: en un espacio 2D, un árbol de pelota podría crear círculos anidados:
```
   y
   |
4  |    (C)
   |  (A)  (D)
2  |    (B)
   |___________
   0    2    4  x
```
El círculo exterior contiene todos los puntos, los círculos internos dividen subconjuntos.
KNN completo (fuerza bruta):
- Calcula las distancias desde el punto de consulta a todos los demás puntos en el conjunto de datos.
- Fácil de implementar pero computacionalmente caro para grandes conjuntos de datos.
- Complejidad del tiempo: o (n * d), donde n es el número de puntos y D es el número de dimensiones.
- Se vuelve ineficiente a medida que aumenta el tamaño del conjunto de datos o la dimensionalidad.
- Garantizado para encontrar los vecinos más cercanos exactos. Ejemplo: para un punto de consulta Q (2,2) y k = 2:
```
   y
   |
4  |    C
   |  A   D
2  |----Q--B
   |___________
   0    2    4  x
```
Calcule distancias: Qa = 1.41, QB = 1, Qc = 2.24, QD = 1.41 Resultado: los 2 vecinos más cercanos son B y A (o D)
HNSW (mundo pequeño jerárquico navegable):
- Un algoritmo aproximado de búsqueda de vecinos más cercanos.
- Construye una estructura de gráficos de múltiples capas para una navegación eficiente.
- Proporciona una compensación entre la velocidad de búsqueda y la precisión.
- Funciona bien en espacios de alta dimensión y con grandes conjuntos de datos.
- Complejidad promedio de tiempo para la búsqueda: O (log n), pero con mejores constantes que los métodos basados en árboles.
- Permite búsquedas más rápidas sacrificando cierta precisión. Ejemplo: una representación 2D simplificada de capas HNSW:
```
 Layer 2:   A --- C
           |
Layer 1:   A --- B --- C
           |    |    |
Layer 0:   A --- B --- C --- D --- E
```
La búsqueda comienza en un punto aleatorio en la capa superior y desciende, explorando a los vecinos en cada nivel hasta llegar a la parte inferior.

La elección entre estos algoritmos depende del tamaño del conjunto de datos, la dimensionalidad, la precisión requerida y la velocidad de consulta. El árbol KD y el árbol de la pelota proporcionan resultados exactos y son eficientes para dimensiones bajas a moderadas. KNN completo es simple pero se vuelve lento para conjuntos de datos grandes. HNSW ofrece un buen equilibrio entre la velocidad y la precisión, especialmente para datos de alta dimensión o grandes conjuntos de datos.

Instalación

Clon este repositorio:

 git clone https://github.com/yourusername/knn-search-comparison.git
cd knn-search-comparison

Crear un entorno virtual (opcional pero recomendado):

 python -m venv venv
source venv/bin/activate  # On Windows, use `venvScriptsactivate`

Instale las dependencias requeridas:
```
 pip install -r requirements.txt
```
Esto instalará todos los paquetes necesarios enumerados en el archivo requirements.txt .

Uso

Para ejecutar las pruebas de comparación con parámetros predeterminados:

 python app.py

También puede personalizar los parámetros de prueba utilizando argumentos de línea de comandos:

 python app.py --vectors 1000 10000 100000 --dimensions 4 16 256 --num-tests 5 --k 5

Argumentos disponibles:

--vectors : lista de recuentos de vectores para probar (predeterminado: 1000, 2000, 5000, 10000, 20000, 50000, 100000, 200000)
--dimensions : Lista de dimensiones para probar (predeterminada: 4 16 256 1024)
--num-tests : número de pruebas para ejecutarse para cada combinación (predeterminada: 10)
--k : número de vecinos más cercanos para buscar (predeterminado: 10)

El script mostrará una barra de progreso durante la ejecución, dándole una estimación del tiempo restante.

El script se puede interrumpir en cualquier momento presionando Ctrl+c. Intentará salir con gracia, incluso durante las operaciones que requieren mucho tiempo como construir el índice HNSW.

Producción

El script mostrará progreso y resulta en la consola. Después de la finalización, verá:

Un resumen de los resultados para cada combinación de recuento de vectores y dimensiones, que incluyen:
- Build Times para KD-Tree, Ball Tree e HNSW Index
- Tiempos de búsqueda promedio de cada algoritmo
Una tabla de todos los resultados
La ubicación del archivo CSV que contiene resultados detallados

Salida de ejemplo para una sola combinación:

 Results for 10000 vectors with 256 dimensions:
KD-Tree build time:       0.123456 seconds
Ball Tree build time:     0.234567 seconds
HNSW build time:          0.345678 seconds
KD-Tree search time:      0.001234 seconds
Ball Tree search time:    0.002345 seconds
Brute Force search time:  0.012345 seconds
HNSW search time:         0.000123 seconds

La tabla de resultados finales y el archivo CSV incluirán tiempos de compilación y tiempos de búsqueda para cada algoritmo, lo que permite una comparación integral del rendimiento en diferentes recuentos de vectores y dimensiones.