k-Nearest Neighbor(Neigbour)

[Thomas2903]

Hallo!

Ich hab schon sehr viel gegoogelt, aber ich weiß noch immer nicht wie der K-NN Algorithmus funktioniert.

Mir geht es primär darum, wie die Trainings und Testphase abläuft. Was muß man gegeben haben?

Man braucht doch n-Samples, und auch deren zugehörtigkeit zu einer Klasse, richtig? Was passiert genau in der (minimalen) Trainingsphase? Beim Testen wird ja nur ein neues Sample hinzugefügt, und dieses anhand der Nachbarn klassifiziert.

Es wäre super, wenn mir hier jemand helfen könnte. Ich hab schon viel darüber gelesen, also bitte jetzt keine links hier posten. Danke.

Vielen dank für die Hilfe.

lg Thomas

[Klotzkopp]

Man braucht doch n-Samples, und auch deren zugehörtigkeit zu einer Klasse, richtig?

Richtig.

Was passiert genau in der (minimalen) Trainingsphase?

Die Trainingsbeispiele werden gespeichert, das ist alles.

Beim Testen wird ja nur ein neues Sample hinzugefügt, und dieses anhand der Nachbarn klassifiziert.

Beim Testen wird nichts hinzugefügt.

[Thomas2903]

Danke für die Antwort. Leider weiß ich jetzt noch immer nicht was genau passiert, bzw ich bin mir nicht sicher.

Was passiert jetzt genau beim Testen??? Und was bei der Klassifizierung??? Was ist der Input, was der Output?

Sorry, aber ich beschäftige mich jetzt schon einige Zeit damit, und weiß nicht weiter..

[Klotzkopp]

Was meinst du denn mit Testen? Regression?

[Thomas2903]

Beides, Regression und Klassifikation. Mir geht es darum, wie der K-NN Algorithmus genau abläuft. Die Frage ist: WAS passiert, und WIE passiert es.

*Trainingsphase

*Testphase

Was ist mit der Klassifikation?

Sorry, aber ich kenne mich nicht aus.

Edit:

Vllt wäre es besser so zu erklären, als ob jemand noch nie etwas von Maschinellen Lernen gehört hat...

Bearbeitet 14. Juli 2014 von Thomas2903

[Klotzkopp]

Trainingsphase: Trainingsbeispiele speichern

Testphase: Eine Eigenschaft eines Objekts mittels der k nächsten Beispiele ermitteln.

Im Falle der Klassifikation erfolgt das durch Mehrheitsentscheid, bei der Regression durch Berechnung eines Mittelwerts.

[Thomas2903]

Sorry, dass hier vermutlich jemand zum Handkuss kommt, der nichts dafür kann. So gut wie edesmal, wenn ich hier im Forum eine Frage stelle, bekomme ich entweder keine Antwort, oder eine mit der ich nichts anfangen kann. Egal um welches Thema es geht...

[Klotzkopp]

Vielleicht könntest du etwas genauer erklären, wo deine Verständnisprobleme liegen. Ich würde ja Links auf Beispiele posten, aber die wolltest du nicht.

[Thomas2903]

Es geht im genauen darum:

WAS habe ich gegeben? und WIE habe ich es gegeben, in welcher Form.

WAS mache ich damit, und WIE mache ich es.

Schritt für schritt!

Ich denke mir, man hat eine gewisse Anzahl von Samples. Diese müssen bereits vorverarbeitet sein, d. h. diese Samples müssen schon zu bestimmten Klassen klassifieziert sein. Oder werden diese Klassen gelernt??? oder sind diese "Ausgangs"-Klassen gegeben??? Natürlch wäre es möglich Klassen zu lernen, mit einer Dichtefunktion aus der Verteilung der Samples. Aber es geht jetzt hier um den K-NN, nicht mehr.

Wenn man jetzt "neue" Samples klassifizieren will, passiert das ja dadurch, dass man sich die k-Nachbarn anschaut, bei welchen Klassen diese sind. Dort wo am meisten Nachbarn sind, gehört auch das neue Sample. Zusätzlich kann man auch mit der Distanz eine Gewichtung machen.

Also: Was passiert in welcher Phase, und welche Phasen gibt es.

[Klotzkopp]

Ich denke mir, man hat eine gewisse Anzahl von Samples. Diese müssen bereits vorverarbeitet sein, d. h. diese Samples müssen schon zu bestimmten Klassen klassifieziert sein.

Richtig.

Wenn man jetzt "neue" Samples klassifizieren will

Erstens klassifiziert man im Kontext dieses Algorithmus nur ein einziges Objekt, und zweitens wird dieses nicht automatisch zu einem neuen Beispielsample. Du baust da viel mehr in diesen Algorithmus ein, als dieser eigentlich tut.

Zusätzlich kann man auch mit der Distanz eine Gewichtung machen.

Wie du die Distanz berechnest, hängt von der Aufgabenstellung ab. Für den Algorithmus selbst ist es irrelevant.

Ich glaube, wir brauchen ein Beispiel.

Wir haben ein paar Samples. In diesem Fall Personen, von denen wir die Größe und das Geschlecht kennen:

- 175 cm, m

- 169 cm, w

- 185 cm, m

- 166 cm, w

- 172 cm, w

- 168 cm, m

Das "Lernen" besteht darin, dass wir uns diese Beispiele merken.

Jetzt haben wir eine Person X, von der wir zwar die Größe kennen (171 cm), aber das Geschlecht nicht. Wir versuchen daher eine Klassifikation über die 3 nächsten Nachbarn. Das wären diese:

- 169 cm, w

- 172 cm, w

- 168 cm, m

Das Ergebnis der Klassifikation ist also, dass X weiblich ist.

Das ist alles.

[flashpixx]

Ich verweise aber einmal darauf, dass ein kNN nur gut Ergebnisse, sofern die einzelnen Dimensionen sich gut linear trennen lassen, nicht zu hochdimensional und nicht sparse sind. Ist das nicht der Fall, dann sollte man andere Verfahren verwenden. Bei machinellen Lernen ist es essentiell, dass man die Struktur der Daten kennt, mit denen man arbeiten will, ansonsten werden die Algorithmen nur sehr schlechte Ergebnisse erzielen.

@Beispiel: Das Beispiel mit "weiblich" ist mit einem kNN auf der Basis von reellen Vektoren nicht bestimmbar, da männlich / weiblich eine reine Binärentscheidung ist und sich bei einem kNN der zugrunde liegende Vektorraum aus R^n definiert. Die Binärentscheidung basiert aber nicht auf R, somit ist das Beispiel formal nicht mit einem kNN berechenbar.

[Klotzkopp]

Die Binärentscheidung basiert aber nicht auf R, somit ist das Beispiel formal nicht mit einem kNN berechenbar.

Wie sieht denn eine Klassifikation auf Basis von R aus?

[flashpixx]

Wie sieht denn eine Klassifikation auf Basis von R aus?

Man kann das "trickreich" umgehen, man definiert "ein bisschen weiblich / männlich". Das Problem ist eben bei dem binären, dass es unstetig ist. Im Grund hat man ja ein Diracmaß für das Geschlecht, entweder genau männlich oder genau weiblich. Mit Hilfe von Delta-Distribution kann man einfach aus dem binären Abbildung das ganze in R überführen und erhält eine differenzierbare Funktion. Im Limes betrachtet passt es wieder, aber für die Stabilität der kNN Berechnung ist das ganze mittels Delta-Distribution besser.

[Klotzkopp]

Hat das für diesen Algorithmus irgendeine praktische Relevanz?

Für mich klingt das danach, dass man da unbedingt ein mathematisch schlüssiges Modell auf einen primitiven Algorithmus draufpflanzen musste, damit irgendwelche Sätze anwendbar werden oder Beweise funktionieren. Man trickst herum, bis die Mathematik passt, und am Ende kommt doch dasselbe heraus.

[lilith2k3]

[flashpixx]

Hat das für diesen Algorithmus irgendeine praktische Relevanz?

Ja hat es! Die Grundlage in eine Norm und auf einer binären Struktur ist keine Norm (und damit kein Metrik) definiert, d.h. ich kann keinen Abstand in der Dimension Geschlecht berechnen, d.h. der Algorithmus läuft in der von Dir beschriebenen Form nicht bzw. wenn man ihn implementiert stürzt er ab.

Man trickst herum, bis die Mathematik passt, und am Ende kommt doch dasselbe heraus.

Bevor solche Aussagen getätigt werden, wäre es vielleicht erst einmal sinnvoll die Mathematik hinter dem kNN zu verstehen, dann wäre es auch direkt ersichtlich gewesen, dass in Deiner Definition Du keine Norm auf Deinem Datenraum definieren und damit eben den Algorithmus gar nicht benutzen kann

[Klotzkopp]

Die Grundlage in eine Norm und auf einer binären Struktur ist keine Norm (und damit kein Metrik) definiert, d.h. ich kann keinen Abstand in der Dimension Geschlecht berechnen

Ich brauche keinen Abstand in der Dimension Geschlecht, weil das Geschlecht nicht mit in die Abstandsfunktion eingeht. Das Geschlecht ist doch die Eigenschaft, für die ich die Klassenzugehörigkeit suche.

d.h. der Algorithmus läuft in der von Dir beschriebenen Form nicht bzw. wenn man ihn implementiert stürzt er ab.

#include <cmath>

#include <algorithm>

#include <map>


enum Geschlecht { m, w };


struct Person {

	int groesse;

	Geschlecht geschlecht;

};


int abstand(Person a, Person  { return std::abs(a.groesse - b.groesse); }


int main()

{

	Person beispiele[] =

	{

		{ 175, m },

		{ 169, w },

 		{ 185, m },

 		{ 166, w },

 		{ 172, w },

 		{ 168, m }

	};


	const size_t anzahl = sizeof(beispiele) / sizeof(beispiele[0]);


	Person X;

	X.groesse = 171;


	// Nächste Nachbarn durch stumpfes Sortieren nach Abstand ermitteln

	std::sort(beispiele, beispiele + anzahl, [X](Person a, Person  { return abstand(a, X) < abstand(b, X); } );


	int k = 3;


	// Zaehlen, wie of welches Geschlecht unter den k ersten Nachbarn auftritt

	std::map<Geschlecht, int> zaehlen;

	for(int i=0; i<k; ++i)

	{

		++zaehlen[beispiele[i].geschlecht];

	}


	// Hoechste Anzahl suchen

	auto maximum = zaehlen.begin();

	for(auto i=zaehlen.begin(); i != zaehlen.end(); ++i) {

		if(i->second > maximum->second)

			maximum = i;

	}


	X.geschlecht = maximum->first;

}[/code]