View Full Version : [FRAGE] - k-NN
Hallo!
Ich bin mir nicht ganz sicher, ob ich den k-NN Algo richtig verstanden hab. Ich bin ein bisschen zu spät in die VO gekommen und die Folien im Skriptum helfen mir auch nicht unbedingt.
Also ich hab mal die einzelnen Klassen untersucht:
http://i17.photobucket.com/albums/b73/WuZweng/efme.gif
Die x-Achse ist die sepal length in cm und die y-Achse ist die petal width in cm. Die 3 Klassen hab ich dann färbig angezeigt. Das sind die besten features zur Unterscheidung (ich hab mir alle Kombinationen angesehen).
So, jetzt meine Fragen: Wie funktioniert der k-NN Algorithmus? Nehm ich jetzt das zweite Set her und schau für jeden Datensatz im zweiten Set, im ersten Set nach den k-nächsten Punkten und klassifizier ihn eben nach der Mehrheit? So hätt ichs verstanden, aber bevor ich mir das antu und es is falsch, frag ich lieber nach.
Eine weitere Frage kann ich mir nicht erklären: Warum kann man nicht gleich in diesem Set die k-nächsten Datensätze suchen? Also für mich ist das ja kein Training, aber wahrscheinlich hab ich eben das Training nicht verstanden.
Bitte um Hilfe!
mfg
Hallo!
Ich bin mir nicht ganz sicher, ob ich den k-NN Algo richtig verstanden hab. Ich bin ein bisschen zu spät in die VO gekommen und die Folien im Skriptum helfen mir auch nicht unbedingt.
Also ich hab mal die einzelnen Klassen untersucht:
http://i17.photobucket.com/albums/b73/WuZweng/efme.gif
Die x-Achse ist die sepal length in cm und die y-Achse ist die petal width in cm. Die 3 Klassen hab ich dann färbig angezeigt. Das sind die besten features zur Unterscheidung (ich hab mir alle Kombinationen angesehen).
So, jetzt meine Fragen: Wie funktioniert der k-NN Algorithmus? Nehm ich jetzt das zweite Set her und schau für jeden Datensatz im zweiten Set, im ersten Set nach den k-nächsten Punkten und klassifizier ihn eben nach der Mehrheit? So hätt ichs verstanden, aber bevor ich mir das antu und es is falsch, frag ich lieber nach.
Genauso ist es. Allerdings mußt Du nicht eine passende Featurekombination wählen. Du nimmst alle 4 Features und suchst Dir die nächsten Punkte im 4-dimensionalen Raum.
Eine weitere Frage kann ich mir nicht erklären: Warum kann man nicht gleich in diesem Set die k-nächsten Datensätze suchen? Also für mich ist das ja kein Training, aber wahrscheinlich hab ich eben das Training nicht verstanden. Bitte um Hilfe!
Hm, könnte man theoretisch schon, man muß halt aufpassen, daß der zu klassifizierende Datensatz nicht bei der Suche nach den k nächsten Nachbarn mit einfließt. Denn der ist klarerweise bei den k nächsten Nachbarn dabei, da er einen Abstand von 0 hat. Anders gesagt, es macht nicht viel Sinn, wenn der zu klassifizierende Datensatz auch im Referenzset enthalten ist.
In der Praxis is es ja so, daß man eine Reihe von Beobachtungen hat, aus denen man das Referenzset (man könnte auch Trainingsset sagen) generiert, d.h. Feature-Vektoren plus Klassenzugehörigkeit. Will man nun einen unbekannten Datensatz klassifizieren, nimmt man dafür das Referenzset zur Hand und sucht die k nächsten Nachbarn.
LG
Sebastian (EFME-Tutor)
Danke buschti!
Also die euklidische Distanz im 4-Dimensionalen Raum berechnen. hmm.. na mal schaun.
Ich meld mich sicher wieder =)
EDIT: Achso einfach Distanz_feature1 + Distanz_feature2 + Distanz_feature3 + Distanz_feature4, nehm ich mal an, oder?
Danke buschti!
Also die euklidische Distanz im 4-Dimensionalen Raum berechnen. hmm.. na mal schaun.
Ich meld mich sicher wieder =)
EDIT: Achso einfach Distanz_feature1 + Distanz_feature2 + Distanz_feature3 + Distanz_feature4, nehm ich mal an, oder?
Nicht ganz, was Du meinst ist die Cityblock/Manhattan-Distanz. Die euklidische Distanz ist wie im zweidimensionalen Fall
sqrt(Distanz_feature1^2 + Distanz_feature2^2 + Distanz_feature3^2 + Distanz_feature4^2)
LG
Sebastian (EFME-Tutor)
Ich dacht's eh so. Also Distanz von alle features mittels euklid und die dann zusammen nochmal mittels euklid.
Aber Cityblock is eh auch erlaubt, zumindest glaub ichs gehört zu haben. Werd aber trotzdem die euklidische nehmen. Danke buschti nochmal!
gn8
Sorry, das war ein blödsinn. Die Distanz zwischen zwei gleichen Features is ja eine einfache Differenz..
Ich hab noch eine Frage zum zweiten Beispiel. Es steht man soll die Gläser nach window-glasses und non-window-classes. Also ich hab mir das so vorgestellt:
Klassifizieren: Wie beim ersten Beispiel und es könnte so aussehen:
[1][1]
[1][1]
[2][1]
[2][4]
[2][5]
usw.
Das erste Feld ist die Klassifikation und das zweite Feld ist die echte Klasse wozu dieser Datensatz gehört. Jetzt sind die window-glasses die Klassen von 1-4 und damit wären die ersten Datensätze richtig Klassifiziert und der letzte falsch, also 20% Fehlerrate. Es ist mir außerdem nicht klar, was wir letztendlich visualisieren sollen.. wieder die Fehlerrate mit 'k' als Laufvariable? Wenn ich nämlich k von 1-214 gehen lass und wieder jedesmal klassifizier, dann dauert das eine ganze Weile.
Ich hab noch eine Frage zum zweiten Beispiel. Es steht man soll die Gläser nach window-glasses und non-window-classes. Also ich hab mir das so vorgestellt:
Klassifizieren: Wie beim ersten Beispiel und es könnte so aussehen:
[1][1]
[1][1]
[2][1]
[2][4]
[2][5]
usw.
Das erste Feld ist die Klassifikation und das zweite Feld ist die echte Klasse wozu dieser Datensatz gehört. Jetzt sind die window-glasses die Klassen von 1-4 und damit wären die ersten Datensätze richtig Klassifiziert und der letzte falsch, also 20% Fehlerrate.
Für den ersten Test mit nur 2 Klassen würde ich es so machen, daß Du eínfach den Datensatz so abänderst, daß alle von 1-4 zu Klasse 1 und alle restlichen zu Klasse 2 gezählt werden. Anders gesagt, Du suchst dir die k nächsten Nachbarn und schaust dann, ob Klasse 1 oder 2 eine Mehrheit darin hat.
Es ist mir außerdem nicht klar, was wir letztendlich visualisieren sollen.. wieder die Fehlerrate mit 'k' als Laufvariable? Wenn ich nämlich k von 1-214 gehen lass und wieder jedesmal klassifizier, dann dauert das eine ganze Weile.
"Visualisieren" in Form eines Plots muß man eigentlich nichts, insbesondere nicht k als Laufvariable. Es genügt wenn man die Fehlerraten angibt, für k=1 und für mindestens 2 weitere k-Werte und jeweils für das 2-Klassen-Problem und das 7-Klassen-Problem.
LG
Sebastian (EFME-Tutor)
Danke, ich habs eh so gemacht.. also im Prinzip einmal für jedes k klassifiziert und dann die Klassen 1-4 und 5-7 getrennt und dann alle einzeln. Mir kommt nur das erste Ergebnis ein bisschen Spanisch vor:
http://i17.photobucket.com/albums/b73/WuZweng/LOOCV2.gif
Irgendwann (ca. bei 100) bleibt die Fehlerrate gleich. Kann das sein? Der Plot für die Klassen als einzelnes schaut richtig aus für mich:
http://i17.photobucket.com/albums/b73/WuZweng/LOOCV.gif
Weiß nicht genau, was Du machst, aber Du scheinst etwas falsch verstanden zu haben. Du nimmst immer einen Trainingsvektor aus den 214 raus und klassifizierst dieses anhand der nächsten Nachbarn in den verbleibenden 213 Trainingsvektoren. Das machst Du 214 mal und die Klassifizierungsrate ist der Anteil der dabei richtig klassifizierten Trainingsvektoren.
Wenn Du das beispielsweise für k=1 und 2 Klassen (1-4 und 5-7) machst, bekommst Du EINE Klassifizierungsrate, nicht 214.
LG
Sebastian (EFME-Tutor)
Was stimmt daran nicht? Das ist die Klassifizierungsrate für Klassen (1-4 und 5-7) mit k=1 bis 214 und das zweite Bild für alle Klassen getrennt. Bei der ersten Aufgabe war es genauso zu lösen.
EDIT: Achja und in jedem der k durchgänge klassifizier ich jeden der 214 Datensätze anhand der nächsten k Nachbarn der verbleibenden 213 Datensätze.
Aso sorry, Du machst das jür jedes k... generell aber bitte Achsen von plots immer beschriften, ansonsten ist nicht immer nachvollziehbar, was eigentlich dargestellt wird.
Wenn die y-Achse Deiner plots die Fehlerrate in Prozent darstellt, dürfte das Ergebnis "grob" schon richtig sein (eher bessere Ergebnisse bei kleinerem k). Generell ist die Fehlerrate aber etwas zu hoch. Bei k=50 bekomme ich eine Fehlerrate von ~0.5 % (2 Klassen) bzw. ~15 % (7 Klassen).
Warum jetzt bei dir die Ergebnisse schlechter sind, ist schwer zu sagen. Verwendest Du die euklidische Distanz?
LG
Sebastian (EFME-Tutor)
0,5%? Verdammt da muss ja was gröberes falsch sein.
Ja ich verwende die euklidische Distanz und zwar etwa so:
length = size(data);
for l=1:length(2)-1
distance = distance + power(data_train(j, l) - data(i, l), 2);
end
dist(i,j) = sqrt(distance);
Also im Prinzip summier ich die quadrate der Differenzen auf, für alle Spalten im Datensatz (Außer ID und der letzten Spalte) und dann nehm ich die Wurzel daraus. Ich nehm an, das müsste passen.
Wenn ich mir aber die Daten im plot anschaue, dann kann ich mir nicht vorstellen, dass 0,5% auch nur irgendwann rauskommen kann. Im Anhang is der Plot mit x = Attribut 2 und y = Attribut 6
0,5%? Verdammt da muss ja was gröberes falsch sein.
Ja ich verwende die euklidische Distanz und zwar etwa so:
length = size(data);
for l=1:length(2)-1
distance = distance + power(data_train(j, l) - data(i, l), 2);
end
dist(i,j) = sqrt(distance);
Also im Prinzip summier ich die quadrate der Differenzen auf, für alle Spalten im Datensatz (Außer ID und der letzten Spalte) und dann nehm ich die Wurzel daraus. Ich nehm an, das müsste passen.
Es geht zwar auch einfacher ohne for-Schleifen (mit dem Befehl sum), aber grundsätzlich ist das schon korrekt.
Mögliche Fehlerquellen sind jetzt noch der Leave-One-Out Mechanismus, das nicht wirklich die k nächsten Nachbarn genommen werden oder die Berechnung der Fehlerrate stimmt nicht.
Wenn ich mir aber die Daten im plot anschaue, dann kann ich mir nicht vorstellen, dass 0,5% auch nur irgendwann rauskommen kann. Im Anhang is der Plot mit x = Attribut 2 und y = Attribut 6
Das mag stimmen für diesen 2-dimensionalen Fall, tatsächlich bekommt man, wenn man nur diese 2 Attribute nimmt, Fehlerraten von über 50 % bei 7 Klassen (hab's grad ausprobiert). Wir sind aber im 9-dimensionalen Raum, und hier sind die Distanzen viel aussagekräftiger (wir benutzen ja alle Features und das bringt uns natürlich mehr, als wenn wir nur einen Bruchteil davon nehmen).
LG
Sebastian (EFME-Tutor)
edit: ok, hab's mir jetzt nochmal angeschaut, und der Fehler scheint eher bei mir zu liegen ;-) Hab nämlich die glass id als feature dazugenommen. Das heißt, Dein Ergebnis scheint richtig zu sein. sorry
Ah, zum Glück.. ich hab schon verzeifelt gesucht.. Ich hab mir noch gedacht, dass du die id mitgenommen hast, denn beim ersten Bsp. gabs keine ID und ich hätte es auch fast mitgezählt. Können wir vielleicht ein bisschen vergleichen?
Bsp1 (erstes File als daten und zweites als trainingsdaten):
k=1: 5.3333 %
k=50: 33.3333 %
k=75: 66.6667 %
Für die zweite Variante isses lustigerweiße gleich an diesen Stellen.. Das Ergebnis sieht dann so aus:
http://i17.photobucket.com/albums/b73/WuZweng/1-1.gif
Beim zweiten Beispiel für 2 Klassen:
k=1: 0%
k=50: 8.8785%
k=100: 23.3645%
k=150: 23.8318%
k=200: 23.8318%
Und für alle Klassen einzeln:
k=1: 0%
k=50: 38.3178%
k=100: 62.1495%
k=150: 67.2897%
k=200: 61.6822%
Die 0% kommen mir sehr suspekt vor, aber vielleicht stimmts ja..
Vielleicht können ja noch andere Leute ihre Ergebnisse posten zum vergleichen.
Ah, zum Glück.. ich hab schon verzeifelt gesucht.. Ich hab mir noch gedacht, dass du die id mitgenommen hast, denn beim ersten Bsp. gabs keine ID und ich hätte es auch fast mitgezählt. Können wir vielleicht ein bisschen vergleichen?
Bsp1 (erstes File als daten und zweites als trainingsdaten):
k=1: 5.3333 %
k=50: 33.3333 %
k=75: 66.6667 %
Ist bei mir genauso.
Beim zweiten Beispiel für 2 Klassen:
k=1: 0%
k=50: 8.8785%
k=100: 23.3645%
k=150: 23.8318%
k=200: 23.8318%
k=1: 3.29 %
k=50: 10.80 %
Und für alle Klassen einzeln:
k=1: 0%
k=50: 38.3178%
k=100: 62.1495%
k=150: 67.2897%
k=200: 61.6822%
k=1: 26.77 %
k=50: 40.85 %
Die 0% kommen mir sehr suspekt vor, aber vielleicht stimmts ja..
Hm, kann es sein, das Du den Testvektor doch noch im Trainingsset mit drin hast?
Das hab ich mich auch schon gefragt, aber ich habs jetzt ausführlich getestet und es wird nicht miteinbegriffen. Es schaut bei mir so aus:
Bsp1:
Klassifikation = classify(data, data_training);
Bsp2:
Klassifikation = classify(data, data);
und in classify hab ich in der Schleife:
if and(j==i, LOOCV==1)
continue;
end
LOOCV ist 1, wenn beide Inputs gleich sind, also im prinzip wenn LOOCV angewandt wird (Bsp2).
Also daran liegts wahrscheinlich nicht.. hmmm
Ich glaub ich habs.. ich überspring zwar, wenn i=j aber die Distanz bleibt dort 0 und damit wirds dazugerechnet.. ich setz dort zusätzlich die Distanz auf 1000 (sollte reichen) und somit passts dann.. im moment bekomm ich
3.2710
9.3458
26.6355
40.6542
Aber die kleine Abweichung kommt daher, da ich durch eine Zahl dividier, die um 1 zu hoch ist, weil ich den einen Vektor nicht dazuzählen darf.. vielleicht hilft das wem anderen auch noch..
Nein, irgendwie kommen wir nicht ganz aufs gleiche..
2.8169
8.9202
26.2911
40.3756
Da hab ich sozusagen (korrekte/213) * 100 gerechnet.. irgendwo hats da noch was, aber ein großes Danke an buschti!
Ok, meine Ergebnisse stimmen auch noch nicht ganz, man muß klarerweise durch 214 und nicht durch 213 dividieren.
Also:
2 Klassen
k=1: 3.27 %
k=50: 10.75 %
7 Klassen
k=1: 26.64 %
k=50: 40.65 %
Also wir sind ziemlich knapp beisammen nur das 10,75 stört mich noch
2 Klassen
k=1: 3.2710
k=50: 9.3458
7 Klassen
k=1: 26.6355
k=50: 40.6542
Also ich glaub die drei passen, nur die 10,75.. naja ich glaub so streng is die Bewertung nicht, oder?
...
Also ich glaub die drei passen, nur die 10,75.. naja ich glaub so streng is die Bewertung nicht, oder?
Nein, ist sie nicht.
Welche Distanzfunktion habt ihr verwendet?
Ich verwende zur Zeit die Euklidische Distanz, und meine Ergebnisse weichen von den hier geposteten doch relativ stark ab. Ich bin mir aber ziemlich sicher, dass ich den k-NN Algorithmus richtig implementiert habe (hab da schon ziemlich viel herumexperimentiert, und zwischenergebnisse geprüft, und, und und, ...).
ich finde die Euklidische Distanz nicht gerade optimal, da aufgrund der unterschiedlichen Wertebereiche bei den Merkmalen, eine ungleich-Gewichtung der Merkmale entsteht. Wenn nämlich ein Merkmal z.B. Werte zwischen 50 und 100 aufweist, und ein anderes Merkmal dagegen Werte zwischen 0 und 1, so würde das zweite Merkmal bei der Klassifizierung praktisch bedeutungslos.
Wie sehe das ganze mit der Mahalanobis-Distanz aus, bzw. wie kommt man auf die Kovarianz-Matrix? Hab das noch nicht ganz verstanden.
Welche Distanzfunktion habt ihr verwendet?
Ich verwende zur Zeit die Euklidische Distanz, und meine Ergebnisse weichen von den hier geposteten doch relativ stark ab. Ich bin mir aber ziemlich sicher, dass ich den k-NN Algorithmus richtig implementiert habe (hab da schon ziemlich viel herumexperimentiert, und zwischenergebnisse geprüft, und, und und, ...).
ich finde die Euklidische Distanz nicht gerade optimal, da aufgrund der unterschiedlichen Wertebereiche bei den Merkmalen, eine ungleich-Gewichtung der Merkmale entsteht. Wenn nämlich ein Merkmal z.B. Werte zwischen 50 und 100 aufweist, und ein anderes Merkmal dagegen Werte zwischen 0 und 1, so würde das zweite Merkmal bei der Klassifizierung praktisch bedeutungslos.
Wie sehe das ganze mit der Mahalanobis-Distanz aus, bzw. wie kommt man auf die Kovarianz-Matrix? Hab das noch nicht ganz verstanden.
Es reicht bei diesem Beispiel schon, einfach die euklidische Distanz zu nehmen, obwohl natürlich die von Dir genannten Probleme damit auftreten.
Eine Möglichkeit ist die z-Standardisierung der Daten. Dabei werden die Daten so transformiert, daß jedes Features Mittelwert 0 und Standardabweichung 1 hat.
Die Anwendung der Mahalanobis-Distanz ist auch eine Möglichkeit. Die Kovarianz-Matrix kann man mit dem Befehl cov() aus den Trainingsdaten schätzen.
LG
Sebastian (EFME-Tutor)
Danke für die Antwort. Ich krieg jetz mittlerweile mit der euklid-Distanz auch die selben Ergebnisse raus. Hatte irgendwie noch einen Fehler beim Zählen der Klassenvorkommnisse. Hab das vorher mit der Funktion hist gemacht, jetz mach ich das mit einer for-Schleife. Hab zwar keine Ahnung, warum da was anderes rauskommt, is halt so :-). Danke für die Erklärung zur Distanz.
Hab da mal eine Frage, weils mich interessiert:
Was sind denn so in der Praxis gängige Fehlerraten von Klassifizierungsalgorithmen. Also wie viel Prozent darf die Fehlerrate sein, dass der Algorithmus als ok angesehen wird, weiß das vielleicht jemand?
und noch etwas (ganz anderes ;)): muss man sich für die Abgabegespräche fixe Zeiten ausmachen, od. geht man einfach während der Übungszeit hin?
Hab da mal eine Frage, weils mich interessiert:
Was sind denn so in der Praxis gängige Fehlerraten von Klassifizierungsalgorithmen. Also wie viel Prozent darf die Fehlerrate sein, dass der Algorithmus als ok angesehen wird, weiß das vielleicht jemand?
Das kann man generell nicht sagen und hängt stark vom Einsatzgebiet ab. Die unterste Grenze ist aber auf alle Fälle, daß der Klassifikator besser als "bloßes Raten" sein muß, d.h. bei 2 Klassen muß die Erkennungsrate über 50 % sein.
In der Praxis macht es oft auch einen Unterschied, was falsch klassifiziert wird. Ein Klassifikator der z.B. Leberflecke auf Hautkrebs untersuchen soll (als Voruntersuchung für den Arzt), sollte nie ein bösartiges Melanom als ungefährlich klassifizieren. Der umgekehrte Fall ist dabei weniger "schlimm".
und noch etwas (ganz anderes ;)): muss man sich für die Abgabegespräche fixe Zeiten ausmachen, od. geht man einfach während der Übungszeit hin?
Man geht einfach zur Übungszeit hin.
LG
Sebastian (EFME-Tutor)
vBulletin® v3.7.1, Copyright ©2000-2008, Jelsoft Enterprises Ltd.