Sei .
Sei eine abzählbare Menge.
Sei ein gelabelter Datensatz mit und .
Als KNN-Algorithmus (k-nächste-Nachbarn, en. k-nearest-neighbour) bezeichnen wir ein Klassifikationsmodell, bei dem zur Vorhersage einer Klasse die unter den Nachbarn eines Punktes am häufigsten auftretende Klasse gewählt.
Die Nachbarn eines Punktes können beispielsweise anhand eines gelabelten Datensatzes ermittelt werden.
Als KNN-Klassifikator definieren wir:
Definition: Größte-Klasse-Funktion
Sei eine abzählbare Menge.
Sei eine Multimenge mit .
Als Größte-Klasse-Funktion definieren wir:
bestimmt also diejenige Klasse , die in der Multimenge am häufigsten vorkommt.
Falls es nicht die eine häufigste Klasse gibt, weil mehrere Klassen gleichhäufig vorkommen, so wird zufällig eine Klasse aus der Menge der am häufigsten vorkommenden Klassen gewählt.
Die Größte-Klasse-Funktion kann bspw. durch Einbeziehen der Abstände zum Datenpunkt oder andere Gewichtungsmethoden erweitert werden.
Anmerkung
Verallgemeinerung des KNN-Klassifikators
Wir können den KNN-Klassifikator verallgemeinern, indem wir bspw.
ein anderes Abstandsmaß als die Euklidische Norm wählen
Über- und Unteranpassung des KNN-Klassifikators
Für den KNN-Klassifikator gilt:
kleinere Werte für können zu Überanpassung führen.
größere Werte für können zu Unteranpassung führen.
Nachteile des KNN-Klassifikators
KNN ist sensibel gegenüber verschieden skalierten Merkmalen und profitiert stark von der z-Transformation.
Bei großen Datensätzen können sowohl die Laufzeit als auch die Speicherkomplexität des Algorithmus groß sein, da der gesamte gegebene Datensatz
im Speicher gehalten
und durchsucht werden muss.
KNN-Klassifikator mit scikit-learn
In Python erhalten wir einen KNN-Klassifikator mit durch: