So funktioniert der k-NN-Algorithmus

Schritt 1: Stichprobe

Verwenden Sie den sample_size-Parameter, um die Gesamtanzahl der Datenpunkte anzugeben, die als Stichprobe vom Schulungsdataset genommen werden sollen. Beispiel: Wenn das erste Dataset über 1 000 Datenpunkte verfügt und sample_size auf 100 festgelegt ist, wobei die Gesamtanzahl der Instances 2 beträgt, nimmt jeder Worker Stichproben von 50 Punkten. Es würde eine Reihe von insgesamt 100 Datenpunkten erfasst werden. Die Stichprobenerfassung erfolgt in linearer Zeit in Bezug auf die Anzahl der Datenpunkte.

Schritt 2: Ausführen der Dimensionsreduzierung

Die aktuelle Implementierung des k-NN-Algorithmus verfügt über zwei Methoden der Dimensionsreduzierung. Sie geben die Methode im dimension_reduction_type-Hyperparameter an. Die sign-Methode gibt eine zufällige Projektion an, die eine lineare Projektion mithilfe einer Matrix von zufälligen Zeichen verwendet. Die fjlt-Methode gibt eine schnelle Johnson-Lindenstrauss-Transformation an, eine Methode auf der Grundlage der Fourier-Transformation. Beide Methoden bewahren die L2- und inneren Produktentfernungen. Die fjlt-Methode sollte verwendet werden, wenn die Zieldimension groß ist, und bietet eine bessere Leistung mit CPU-Inferenzen. Die Methoden unterscheiden sich in ihren Rechenkomplexitä. Die sign-Methode erfordert O(ndk)-Zeit, um die Dimension eines Stapels von n Punkten der Dimension d auf eine Ziel-Dimension k zu reduzieren. Die fjlt-Methode erfordert O(nd log(d)) Zeit, doch die beteiligten Konstanten sind größer. Durch die Dimensionsreduzierung werden die Daten verzerrt, wodurch sich die Prognosegenauigkeit verringern kann.

Schritt 3: Erstellen eines Index

Während der Inferenz fragt der Algorithmus den Index nach den k-nearest-neighbors eines Stichprobenpunkts ab. Basierend auf den Verweisen auf die Punkte nimmt der Algorithmus die Klassifizierungs- oder Regressionsprognose vor. Seine Prognose basiert auf den bereitgestellten Klassenbezeichnungen oder Werten. k-NN bietet drei verschiedene Arten von Indizes: einen flachen Index, einen umgekehrten Index und einen umgekehrten Index mit Produktquantisierung. Sie geben den Typ mit dem index_type-Parameter an.

Serialisieren des Modells

Wenn der k-NN-Algorithmus Schulungen abgeschlossen hat, serialisiert er drei Dateien zur Vorbereitung der Inferenz.

• model_algo-1: Enthält den serialisierten Index zur Berechnung der nächsten Nachbarn.

• model_alg-1.labels: Enthält serialisierte Bezeichnungen (np.float32-Binärformat) zum Berechnen der prognostizierten Bezeichnung basierend auf dem Abfrageergebnis aus dem Index.

• model_algo-1.json: Enthält die Modellmetadaten im JSON-Format, in dem die k- und predictor_type-Hyperparameter aus den Schulungen für Inferenz zusammen mit anderen relevanten Zuständen gespeichert werden.

Mit der aktuellen Implementierung von k-NN können Sie die Metadatendatei ändern, um die Art zu ändern, wie Prognosen berechnet werden. So können Sie z. B. k in 10 oder predictor_type in regressor ändern.

{
  "k": 5,
  "predictor_type": "classifier",
  "dimension_reduction": {"type": "sign", "seed": 3, "target_dim": 10, "input_dim": 20},
  "normalize": False,
  "version": "1.0"
}