K-Nearest Neighbor < Künstl. Intelligenz < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:48 Do 02.02.2012 | | Autor: | natascha |
| Aufgabe | Klassifizieren Sie die neue Instanz (93,8,10) unter Verwendung des k-nearest neighbor Algorithmus und der euklidischen Distanz. Was ist das Problem bei diesem Dataset?
Gegebene Werte:
1) 126, 14, 6, A
2) 102, 6, ,12, A
3) 127, 13, 10, B
4) 99, 8, 6, A
5) 89, 5, 5, A
6) 103, 15, 7, A
7) 112, 17, 12, B
8) 87, 10, 11, A
9) 88, 11, 6, A
10) 93, 8, 10, A |
Guten Tag,
Zuerst einmal denke ich, dass das Problem darin besteht, dass die neue Instanz bereits in der Tabelle vorkommt. Wenn ich ganz normal vorgehe, erinnere ich mich aus dem Unterricht, dass wir zuerst die Distanz von der neuen Instanz zu allen anderen berechnen müssen, deswegen fange ich wie folgt an:
d(new,1) = sqrt(1089+36+16) = 33.78
d(new,2) = 9.43
d(new,3) = 34.36
d(new,4) = 7.746
d(new,5) = 7.07
d(new,6) = 12.57
d(new,7) = 21.1187
d(new,8) = 6.403
d(new,9) = 7.07
d(new,10) = 0
Die kleinste Distanz ist mit dem Eintrag 10 aus der Tabelle, dieser sollte also Root werden des Baumes.
Nun soll das Attribut gewählt werden, anhand welchem ich die Einträge sortiere (wenn grösser als bei Eintrag 10 auf die rechte Seite, und sonst auf die linke Seite).
Stimmt das soweit? Woher weiss ich, welches Attribut ich nehmen soll für das Splitten?
Vielen Dank im Voraus!
Liebe Grüsse,
Natascha
|
|
| |
|
Guten Tag!
Ich wäre echt froh, wenn mir jemand bezüglich dieses Algorithmus helfen könnte. Vielleicht kennt jemand einen LInk zu einem guten BEispiel? Hab gegooglet, aber bis jetzt noch nichts schlaues gefunden. Ich muss diesen Algorithmus unbedingt verstehen! Vielen Dank im Voraus!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:02 Fr 03.02.2012 | | Autor: | sandp |
hey,
hast du irgendwo in deinen Unterlagen einen Pseodocode oder irgendwas ähnliches, dass man die vorgehensweiße des Algorithmus nachvollziehen kann, da man wirklich sehr wenig über den Algorithmus im Internet(und es oft dann auch kleine Unterschiede gibt) findet und ich von dem Algorithmus auch noch nichts gehört habe.
Also dass du am Anfang den Abstand zu allen Instanzen bilden musst, das scheint richtig zu sein, das wird wohl auch der Grund sein warum der Algorithmus nicht so oft angewandt wird, da das ja ziemlich viel Aufwand ist.
Gruß sandp
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 So 05.02.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Hi!
In der Tat findet man recht wenig zur K-Nearest Neighbour Methode, aber im Prinzip ist diese recht einfach:
Man hat eine gegeben Trainingsdatenmenge, wo jedem Punkt (oder allg. jedem Vektor) eine Klasse zugewisen wurde. Das hast Du ja hier auch gegeben.
Der eigentliche Algorithmus sucht nun zu dem Datenvektor c und den passenden Trainingsdaten T die dazugehörige Klasse.
In "Grundkurs Künstliche Intelligenz" von Wolfang Ertel wird das etwas formaler so beschrieben:
NearestNeighbour(M_+,M_-,s)
t = [mm] argmin_{x \in M_+ \cup M_-} \{d(s,x)\} [/mm]
If t [mm] \in M_{+} [/mm] Then Return("+")
else Return("-")
wobei [mm] M_{+} [/mm] die Menge der positiven Testdaten, [mm] M_{-} [/mm] die Menge der negativen Testdaten und s der zu klassifizierende Vektor ist. d bezeichnet hier irgendeine Abstandsmetrik, bei Dir also den euklidischen Abstand.
Jetzt hast Du k nicht gegeben, daher gehe ich davon aus, dass der obrige Algo. ausreicht. (quasi k = 1)
Beim klassischen K-Nearest-Neighbour betrachtet man nun die k nächsten Datenpunkte im Bezug auf d(..).
Überlicherweise führt man dann oben eine Mehrheitsentscheidung duch, falls k > 1 ist. Das heißt, du betrachtetst die k nächsten Nachbarn und gibst die häufigste Klassifikation zurück. (Wenn 2 Nachbar "+" sind und einer "-" bei k = 3, dann gibst Du halt "+" zurück)
Falls diese Anzahl gleich ist, dann gibst Du was zufälliges zurück.
Ich hoffe das hilft ein wenig.
Gruß
Pille
Edit: Bzgl. der Frage was hier problematisch am Datenset ist: Ich würde mir die Punkte mal aufmalen/plotte. Ich vermute(!!) dann wird dabei herauskommen, dass der Abstand zum neuen Punkt von einer Klasse aus geringer als der zu einer anderen ist, obwohl man intuitiv den Punkt der anderen Klassen zugewiesen hätte. Das heißt der Algo. wählt hier eine Klassifierung, die dem Menschen nicht direkt schlüssig erscheint (aufgrund der Testdatenmenge)
|
|
|
|
