Wer sind meine Nachbarn? Dieser Artikel beschreibt einen sehr einfachen Algorithmus für Klassifikationen, den k-Nächste-Nachbarn-Algorithmus (kurz kNN). Wie bereits in den Grundzügen maschinellen Lernens erklärt, dienen Klassifikationen dazu, neue Daten in eine der gelernten Klassen einzuteilen. Damit dient dieser Algorithmus dem gleichen Zweck, wie der Bayes-Klassifikator. In diesem Artikel erfährst du die grundlegende Funktionsweise von kNN, sowie dessen Ein- und Ausgaben und Vor- und Nachteile. Viel Spaß beim Lernen!
Eingaben und Ausgaben
Die Trainingsdaten bei kNN bestehen aus ihren Merkmalen und ihrer Klasse. Hinzu kommt noch der Parameter k, der die Anzahl der Nachbarn bestimmt, die berücksichtigt werden sollen. Die Menge an Trainingsdaten bildet gleichzeitig auch die Grundlage für das Modell, um nicht klassifizierte Daten zuordnen zu können. Bei der Anwendung von kNN sollte von vornherein klar sein, wie der Abstand zwischen zwei Datenpunkten bestimmt wird. Im Beispiel unten wird der euklidische Abstand als Maß verwendet, sprich die Länge der direkten Verbindung.
Grundlegende Funktionsweise
Die Grundidee von kNN ist, dass Datenpunkte mit der selben Klassen ähnliche Merkmale haben. Deshalb wird im Umkehrschluss angenommen, dass ein Datenpunkt die selbe Klasse wie seine nächsten Nachbarn hat. Um die Klasse eines unbekannten Punktes zu bestimmen, werden somit zunächst die k naheliegendsten Nachbarn gesucht (beispielsweise drei Nachbarn). Dann wird überprüft welche Klasse unter den Nachbarn am häufigsten vertreten ist. Diese Klasse wird dann auch dem unbekannten Datenpunkt zugewiesen.
Rechts ist ein Beispiel zu sehen. Die Grafik zeigt Premium-Kunden (blau) und Nicht-Premium-Kunden (grün) in einem Koordinatensystem. Die untere Achse gibt die Anzahl der Käufe an und die y-Achse zeigt das umgesetzte Geld eines Kunden. Nun gilt es beispielsweise herauszufinden, ob es sich lohnt, für den Kunden mit dem Fragezeichen Werbung für das Premiumangebot zu schalten. Dafür werden seine drei naheliegendsten Nachbarn betrachtet. Davon sind zwei Premium-Kunden und somit kann angenommen werden, dass sich auch dieser Kunde für Premium entscheiden wird. Sprich es lohnt sich Werbung zu schalten.
Vorteile und Nachteile
Ein großer Nachteil ist, dass kNN sehr langsam werden kann. Das liegt daran, dass die Gesamtheit der Trainingsdaten bei jeder neuen Prognose nach den Nachbarn durchsucht werden muss. Gehen also die Menge an Trainingsdaten in den Bereich der Gigabyte oder Petabyte, kann kNN trotz starker Rechner sehr schnell an Geschwindigkeit verlieren. Ein weiterer Nachteil ist, dass bei kNN angenommen wird, dass alle Attribute gleich relevant sind. Dem kann durch Gewichtung der Merkmale beziehungsweise durch die Wahl eines anderen Abstandsmaßes entgegengewirkt werden.
Dennoch wird kNN in der Praxis angewendet. Das liegt vor Allem daran, dass kNN sehr schlicht und schnell verständlich ist und darüber hinaus oft sehr akkurate Ergebnisse liefern kann.
Links und Referenzen
- Prof. Dr. Heiko Paulheim: Vorlesungsunterlagen Data Mining - Classification Part 1. Universität Mannheim, 2017.
- Lillian Pierson: Data Science für Dummies. Wiley VCH-Verlag, 2009.
- Pang-Ning Tan, Michael Steinbach, Vipin Kumar: Introduction to Data Mining. Pearson, 2006.
Kommentar schreiben