k-Nearest Neighbors ist ein Verfahren des Machine Learning, das einen neuen Fall so einordnet wie die k ähnlichsten bekannten Fälle. Es gibt kein Training im eigentlichen Sinn: Das Verfahren merkt sich die Beispiele und vergleicht bei jeder Anfrage.
- k-Nearest Neighbors (k-nächste Nachbarn)
Ein Verfahren, das einen neuen Fall so einordnet wie die k ähnlichsten bekannten Fälle.
Beispiel: „Mit k gleich fünf ordnete k-Nearest Neighbors die Anfrage der Kategorie zu, die bei vier der fünf Nachbarn stand.“Was eingestellt wird: die Zahl der betrachteten Nachbarn und das Maß für Ähnlichkeit. Ein kleines k reagiert empfindlich auf Ausreißer, ein großes verwischt die Grenzen.
Die Kosten liegen nicht im Training, sondern in der Anfrage: Jede Einordnung vergleicht gegen alle gespeicherten Beispiele.
Warum das Verfahren wieder auftaucht
Weil die Vektorsuche darauf beruht. Eine Suche in einer Vektordatenbank sucht die nächsten Nachbarn eines Embeddings und ist damit dasselbe Verfahren unter anderem Namen. Was dort als Ähnlichkeitssuche läuft, ist der Nachbarschaftsvergleich aus dem Lehrbuch, nur auf Millionen Einträgen und mit Näherungen.
Was die Näherungen damit zu tun haben
Sie machen es benutzbar. Ein genauer Vergleich gegen Millionen Einträge dauert zu lange, und deshalb arbeiten die verbreiteten Vektorbestände mit Verfahren, die fast immer die richtigen Nachbarn finden und selten danebenliegen. Diese Ungenauigkeit ist eingebaut und steht in den Einstellungen als Abwägung zwischen Tempo und Treffsicherheit.
Wofür es als Lernverfahren taugt
Für kleine Bestände und für den ersten Versuch. Es ist in wenigen Zeilen gebaut, braucht keine Einstellungen außer zwei und liefert einen Vergleichswert, gegen den sich jedes aufwendigere Modell messen lassen muss. Wer dieses Verfahren nicht schlägt, braucht das größere nicht.
Wo es scheitert
Bei vielen Merkmalen. In hochdimensionalen Räumen rücken alle Abstände zusammen, und der Begriff des nächsten Nachbarn verliert an Bedeutung. Dagegen hilft eine Verringerung der Merkmale vorher, und genau deshalb stehen beide Verfahren in Lehrbüchern meist nebeneinander.