Wie bei Klassifikationsaufgaben üblich, benötigen wir Trainingsdaten und Testdaten (jeweils mit bekanntem Klassifikationsergebnis), die auf die gleiche Art und Weise erzeugt bzw. erhoben werden. Unter Verwendung der Trainingsdaten wird das Klassifikationsverfahren nun auf die Testdaten angewandt, um für jedes Objekt (bzw. jeden Punkt) ein (erwartetes) Klassifikationsergebnis zu bestimmen. Ziel ist es, einen möglichst großen Anteil der Testdaten korrekt zu klassifizieren, sodass das bestimmte (erwartete) Klassifikationsergebnis gleich dem bekannten Ergebnis ist.
Die Abbildung zuvor zeigt Trainingsdaten (links) bestehend aus 400 und Testdaten (rechts) bestehend aus 100 Punkten. Das Klassifikationsergebnis ist jeweils anhand der Farbe zu erkennen.
Um einen Punkt der Testdaten unter Berücksichtigung der Trainingsdaten zu klassifizieren, ist die Vorgehensweise bei der Nächste-Nachbarn-Klassifikation folgende: Es werden die k Punkte (bzw. Objekte) der Trainingsdaten bestimmt, die dem zu testendem Punkt am nächsten sind:
Die Abbildung zeigt ein Beispiel anhand von Trainingsdaten bestehend aus 32 Punkten. Der zu testende Punkt ist als Kreuz markiert und es werden die k=5 nächsten Nachbarn bestimmt. Nun wird geschaut, welches Klassifikationsergebnis unter den fünf nächsten Nachbarn am häufigsten ist. Im Beispiel ist dies Blau, sodass der zu testende Punkt (schwarzes Kreuz in der Abbildung) ebenfalls als Blau klassifiziert wird.
In der Regel wird für den Parameter k eine kleine und ungerade Zahl gewählt. Eine ungerade Zahl hat dabei den Vorteil, dass die Wahrscheinlichkeit dafür verringert wird, dass es unter den Nachbarn einen Gleichstand bezüglich der Klassenzugehörigkeit gibt. Sollte dies dennoch der Fall sein, so kann ein weiterer (nächstgelegener) Punkt der Trainingsdaten zur Entscheidungsfindung hinzugezogen werden.
