Machine Learning für Anfänger mit JavaScript: k-Nearest Neighbors

Machine Learning für Anfänger mit JavaScript: k-Nearest Neighbors

Im Machine Learning kommen diverse Algorithmen oder „Modelle“ zum Einsatz. Sie sind meinst sehr komplex aufgebaut und bedienen sich bereits bestehender Konzepte aus der Mathematik und Statistik. Eines dieser Konzepte, habe ich bereits in meinem letzten Beitrag zur Linearen Regression vorgestellt. 

Es gibt allerdings noch einen viel einfacheren Algorithmus der ohne sogar ohne eine ML-Library wie z.B. Tensorflow auskommt – k-Nearest Neighbors.


Berner Sennenhund oder Labrador?

In diesem Beispiel haben wir ein Datenset welches zwei Hunderassen anhand ihres Gewichts und der Schulterhöhe beschreibt: Labrador Retriever und Berner Sennenhunde.

Milo <3, Labrador

Die Daten enthalten die Informationen über die Schulterhöhe (in cm) und das Gewicht (in kg) des jeweiligen Hundes. Jeder Datzensatz enthält außerdem das Label 0 für einen Berner Sennenhund oder 1 für einen Labrador Retriever.

Labrador / Berner Sennenhund Plot

Das Ziel ist es, für eine beliebiges Gewicht x und eine beliebige Schulterhöhe y, die richtige Vorhersage darüber zu bekommen, ob der Hund anhand der historischen Daten, ein Berner Senne oder Labrador ist.


const weightX = [40,42,42.5,48,50,51,37,38.5,42.5,44.5,45.5,46.5,43.5,51.5,52,47.0,49.5,48.0,48.5,50.5,38,30,35,38,32,30,33,36,36,40,41,37,34,32,31.5,35.5,36,37.5,37,40,38,39]

const heightY = [60,62,62,72,70.5,69.5,55,53.5,61,62,62.5,65,65.5,69,70.5,62.5,59,58,61,64,58,52,54,56,50,48,50.5,51.5,57,59,58,55,52,50,51,49,49.5,52,53,55,52,56.5]

const label = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];

k-Nearest Neighbors

Der Algorithmus ist denkbar einfach. Er soll nämlich die benachbarten Punkten zurückgegeben, die in unmittelbarer Nähe zum gesuchten Punkt stehen. Dabei steht k für die Anzahl der Punkte die im Umkreis in Betracht gezogen werden sollen.

const k = 4;

In dem nachfolgenden Beispiel ist k=4. Die Hunderasse wird gesucht für x=39 und y=55.

kNN Klassifizierung

Der Abstand wird nach der bekannten Formel für Länge der Hypothenuse in einem rechtwinkligen Dreieck, berechnet.

Für unseren Fall passen wir die Formel noch etwas an. Denn a und b ergeben sich, aus der Differenz zwischen x und x‘ sowie y und y‘. 

In JavaScript erstellen wir eine Funktion getDistances(dogWx, dogHy) die zwei Parameter erwartet – Gewicht und Schulterhöhe des unbekannten Hundes.

const distances = [];

function getDistances (dogWx, dogHy) {
  for (var i=0; i < weightX.length; i++) {
		
	const dx = weightX[i] - dogWx;
	const dy = heightY[i] - dogHy;
	const d = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
		
	const label = getLabel(i);
		
	const distance = [i, d, label];
	distances.push(distance);
		
	distances.sort(function(a,b) {
		return a[1] - b[1];
	});
  }
}

function getLabel(index) {
	return label[index];
}

Zunächst werden die Abstände berechnet, dann das zugehörige Label über die Funktion getLabel(index) ermittelt. Mit den Informationen über Index, Abstand sowie Label, wird ein Objekt distance erzeugt, welches wiederum in die globale Konstante distances (Array) gepusht wird.

Im letzten Schritt wird das Array nach Abstand (aufsteigend) sortiert. Das testen wir mit dem Punkt 39|55.

getDistances(39,55);
Sortierte Abstände (aufsteigend)

Wir sehen, dass uns die Konsole die sortierten Punkte in absteigender Reihenfolge zurückgibt – genau das was wir wollten.

Prima, jetzt fehlt eigentlich nicht mehr so viel. Wir brauchen nur noch eine Funktion, die die ersten k-Objekte betrachtet und uns anhand der Labels (0=BS, 1=Labbi) sagt ob wir es mit einem Berner Sennen oder einem Labrador zu tun haben.

function getNearestNeighbors(k, testDataX, testDataY) {

	var sum = 0;
	getDistances (testDataX, testDataY);
	
	// 
	for (var i=0; i < k; i++) {
		console.log(distances[i])
		sum += distances[i][2];
	}
	
	const knn = sum / k;
	
	if (knn < 0.5) {
		console.log("Berner Sennenhund");
	} else {
		console.log("Labrador Retriever");
	}
}

Da wir schon bereits über das Array distances, die nötige Sortierung vorgenommen haben, können wir mit einer neuen Schleife k-Durchläufe ausführen um auf die korrekte Anzahl an Objekten zu kommen.

getNearestNeighbors(4, 39, 55);

Die einzige Challenge die es noch gilt zu meistern, ist es die korrekte Klassifizierung durch JavaScript vornehmen zu lassen, anhand der Labels aus unserem sortierten Array. Dieser Schritt ist wichtig, da es durchaus vorkommen kann, dass Punkte aus anderen Klassen in unmittelbarer Nähe zum gesuchten Punkt stehen. Hier muss dann eine Gewichtung vorgenommen werden. 

Da wir nur mit einer 0 und einer 1 arbeiten, können wir mit diesen Werten unsere Gewichtung vornehmen. Im ersten Schritt summieren wird die Label-Werte auf.

Label Werte

Daraus ergibt sich die Rechnung: 1 + 1 + 1 + 0 = 3.

Nun dividieren wir die Summe 3 durch die Anzahl der Punkte k = 4 und erhalten damit 0,75

Da dieser Wert eher an der 1 dran ist, kann damit das Label vorhergesagt werden. In diesem Fall ist der gesuchte Hund also ein Labrador.


Fazit

Mit kNN lassen sich relativ einfach Vorhersagen machen. Außerdem ist das Prinzip simple und verständlich, so dass es vor allem zu Anschauungszwecken häufig eingesetzt wird. 

Auch wenn wir oben nur ein zweidimensionales Datenset verwendet haben, kann kNN ebenfalls auf mehrer Dimensionen angewandt werden. Denn die Formel für die Abstände ändert sich vom Prinzip her nicht. Außerdem können auch deutlich mehr Labels (Klassen) in Betracht gezogen werden. Ein praktisches Beispiel hierfür wäre ein Algorithmus der die Präferenzen von Usern eines Filmportals vergleicht und daraus Film-Empfehlungen generiert.

Titelbild: Photo by Anastasiia Tarasova on Unsplash

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Nächster Beitrag:

Machine Learning für Anfänger mit TensorFlow.js: Lineare Regression

Machine Learning für Anfänger mit TensorFlow.js: Lineare Regression