knn search algorithm comparison herunterladen - knn search algorithm comparison Quellcode Download

knn search algorithm comparison

Anderer Quellcode

1.0.0

Herunterladen

KNN -Suchalgorithmusvergleich

Der 1951 eingeführte K-Nearest-Nachbarn (K-NN) -Algorithmus wurde sowohl für die Klassifizierung als auch für die Regressionsaufgaben häufig verwendet. Das Kernkonzept beinhaltet die Identifizierung der K -ähnlichen Instanzen (Nachbarn) zu einem bestimmten Abfragepunkt innerhalb eines Datensatzes und die Verwendung dieser Nachbarn, um Vorhersagen oder Klassifizierungen vorzunehmen. In den letzten Jahren hat die Bedeutung von Vektordatenbanken und Vektorindizes gewachsen, insbesondere für das Abrufen von Informationen zur Unterstützung großer Sprachmodelle (LLMs) bei der Verarbeitung umfangreicher Datensätze von Text und anderen Daten. Ein herausragendes Beispiel für diese Anwendung ist die ARRAVEAL-AUGmented Generation (RAG).

Dieses Projekt vergleicht die Leistung verschiedener K-NN-Suchalgorithmen über verschiedene Datensatzgrößen und -abmessungen. Die verglichenen Algorithmen sind:

KD-Tree
Ballbaum
Brute Force (volle KNN)
HNSW (hierarchische schiffbare kleine Welt)

Algorithmus Erklärungen

KD-Tree (k-dimensionaler Baum):
- Eine Raum-Partitionierungsdatenstruktur zum Organisieren von Punkten in einem k-dimensionalen Raum.
- Baut einen binären Baum, indem der Raum rekursiv entlang verschiedener Abmessungen aufgeteilt wird.
- Effizient für niedrigdimensionale Räume (typischerweise <20 Abmessungen).
- Durchschnittliche Zeitkomplexität für die Suche: O (log n), wobei n die Anzahl der Punkte ist.
- In hochdimensionalen Räumen weniger wirksam aufgrund des "Fluches der Dimensionalität". Beispiel: In einem 2D-Raum kann ein KD-Tree die Ebene vertikal aufteilen, dann horizontal, wechseln sich auf jeder Ebene:
```
   y
   |
4  |    C
   |  A   D
2  |    B
   |___________
   0    2    4  x
```
Punkte: a (1,3), b (3,1), c (4,3), d (3,3) Baumstruktur: Wurzel (x = 2) -> links (y = 2) -> rechts (x = 3)
Ballbaum:
- Eine Binärbaumdatenstruktur, die sich aufteilt, zeigt in verschachtelte Hypersphären.
- Jeder Knoten repräsentiert einen Ball (Hypersphere), der eine Teilmenge der Punkte enthält.
- Effektiver als KD-Baum für hochdimensionale Räume.
- Durchschnittliche Zeitkomplexität für die Suche: O (log n), jedoch mit höheren konstanten Faktoren als KD-Tree.
- Im Allgemeinen ist es besser als KD-Tree, wenn Abmessungen> 20. Beispiel: In einem 2D-Raum kann ein Ballbaum verschachtelte Kreise erzeugen:
```
   y
   |
4  |    (C)
   |  (A)  (D)
2  |    (B)
   |___________
   0    2    4  x
```
Der äußere Kreis enthält alle Punkte, innere Kreise teilen Untergruppen.
Full Knn (Brute Force):
- Berechnet Entfernungen vom Abfragepunkt zu allen anderen Punkten im Datensatz.
- Einfach zu implementieren, aber rechnerisch teuer für große Datensätze.
- Zeitkomplexität: O (N * D), wobei n die Anzahl der Punkte und d die Anzahl der Dimensionen ist.
- Wird ineffizient, wenn die Datensatzgröße oder -dimensionalität zunimmt.
- Garantiert die genau nächsten Nachbarn finden. Beispiel: Für einen Abfragepunkt Q (2,2) und K = 2:
```
   y
   |
4  |    C
   |  A   D
2  |----Q--B
   |___________
   0    2    4  x
```
Berechnen Sie Abstände: QA = 1,41, QB = 1, QC = 2,24, QD = 1,41 Ergebnis: Nächste 2 Nachbarn sind b und a (oder d)
HNSW (hierarchische schiffbare kleine Welt):
- Ein ungefährer Suchalgorithmus für Nachbarn.
- Erstellt eine mehrschichtige Grafikstruktur für eine effiziente Navigation.
- Bietet einen Kompromiss zwischen Suchgeschwindigkeit und Genauigkeit.
- Funktioniert gut in hochdimensionalen Räumen und mit großen Datensätzen.
- Durchschnittliche Zeitkomplexität für die Suche: O (log n), jedoch mit besseren Konstanten als baumbasierte Methoden.
- Ermöglicht schnellere Suchanfragen, indem Sie einige Genauigkeit opfern. Beispiel: Eine vereinfachte 2D -Darstellung von HNSW -Schichten:
```
 Layer 2:   A --- C
           |
Layer 1:   A --- B --- C
           |    |    |
Layer 0:   A --- B --- C --- D --- E
```
Die Suche beginnt an einem zufälligen Punkt in der oberen Schicht und steigt ab und erkundet die Nachbarn auf jeder Ebene, bis er den Boden erreicht.

Die Auswahl zwischen diesen Algorithmen hängt von der Datensatzgröße, der Dimensionalität, der erforderlichen Genauigkeit und der Abfragegeschwindigkeit ab. KD-Baum und Ballbaum liefern genaue Ergebnisse und sind für niedrige bis mittelschwere Abmessungen effizient. Full KNN ist einfach, wird aber für große Datensätze langsam. HNSW bietet ein gutes Gleichgewicht zwischen Geschwindigkeit und Genauigkeit, insbesondere für hochdimensionale Daten oder große Datensätze.

Installation

Klonen Sie dieses Repository:

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

Erstellen Sie eine virtuelle Umgebung (optional, aber empfohlen):

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

Installieren Sie die erforderlichen Abhängigkeiten:
```
 pip install -r requirements.txt
```
Dadurch werden alle erforderlichen Pakete installiert, die in der Datei requirements.txt aufgeführt sind, einschließlich Numpy, Scipy, Scikit-Learn, HNSWLIB, Tabulat und TQDM.

Verwendung

So führen Sie die Vergleichstests mit Standardparametern aus:

 python app.py

Sie können die Testparameter auch anhand von Befehlszeilenargumenten anpassen:

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

Verfügbare Argumente:

--vectors : Liste der zu testenden Vektorzahlen (Standardeinstellung: 1000, 2000, 5000, 10000, 20000, 50000, 100000, 200000)
--dimensions : Liste der zu testenden Abmessungen (Standardeinstellung: 4 16 256 1024)
--num-tests : Anzahl der für jede Kombination ausgeführten Tests (Standard: 10)
--k : Anzahl der nächsten Nachbarn, nach denen sie suchen sollten (Standard: 10)

Das Skript zeigt während der Ausführung eine Fortschrittsleiste an und gibt Ihnen einen Schätzung der verbleibenden Zeit.

Das Skript kann jederzeit durch Drücken von Strg+c unterbrochen werden. Es wird versuchen, anmutig zu gehen, auch bei zeitaufwändigen Operationen wie dem Aufbau des HNSW-Index.

Ausgabe

Das Skript zeigt den Fortschritt an und führt in der Konsole. Nach Abschluss sehen Sie:

Eine Zusammenfassung der Ergebnisse für jede Kombination von Vektorzahl und Abmessungen, einschließlich:
- Erstellen Sie Zeiten für KD-Tree, Ballbaum und HNSW-Index
- Durchschnittliche Suchzeiten für jeden Algorithmus
Eine Tabelle aller Ergebnisse
Der Ort der CSV -Datei mit detaillierten Ergebnissen enthält

Beispielausgabe für eine einzelne Kombination:

 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

Die endgültige Ergebnistabelle und die CSV -Datei umfassen sowohl Erstellungszeiten als auch Suchzeiten für jeden Algorithmus, der einen umfassenden Vergleich der Leistung über verschiedene Vektorzahlen und -abmessungen hinweg ermöglicht.

Anpassung

Sie können die folgenden Variablen in app.py ändern, um die Testparameter anzupassen:

NUM_VECTORS_LIST : Liste der Vektorzahlen zum Testen
NUM_DIMENSIONS_LIST : Liste der zu testenden Dimensionen
NUM_TESTS : Anzahl der Tests, die für jede Kombination ausgeführt werden sollen
K : Anzahl der nächsten Nachbarn, nach denen sie suchen sollten