3. Übung

[jlerch]

Ich mal wieder...

Seh ich es richtig, dass auf Folie 12 (Foliensatz vom 26.10.) mit W nicht die Adjazenzmatrix gemeint ist, sondern die Matrix des Undirected kNN ? Falls nicht, verstehe ich nicht wie wir auf Folie 13 annehmen können, dass L symmetrisch ist.

[Sandra]

Mit W ist die Adjazenzmatrix gemeint, aber die Graphen die in der Vorlesung behandelt wurden sind ja alle ungerichtet, daher ist die Adjazenzmatrix per Definition symmetrisch. Und diese Matrix ist wiederum identisch mit der Matrix des ungerichteten kNN Graphen.

[xAx]

hallo, hab da ne frage zu 2.: sollte das ergebnis der nearest neighbor function nicht vielmehr eine n x k matrix sein?
edit: oder soll die matrix als eintrag eine 0 haben, wenn die entsprechenden vektoren nicht "nah genug" (im sinne der anzahl k) liegen?

[jlerch]

Mit W ist die Adjazenzmatrix gemeint, aber die Graphen die in der Vorlesung behandelt wurden sind ja alle ungerichtet, daher ist die Adjazenzmatrix per Definition symmetrisch. Und diese Matrix ist wiederum identisch mit der Matrix des ungerichteten kNN Graphen.

Ich bin verwirrt. Im ersten Foliensatz taucht auf Folie 51 die Adjazenzmatrix auf ohne auf einen speziellen Graphen einzugehen. Folie 52 wird das auf Directed KNN angepasst und erst danach auf Folie 52 zu Undirected überführt. Inwiefern hatten wir dann nur Ungerichtete? Ist der Ansatz die paarweise Distanz auszurechnen, darauf Directed KNN anzuwenden und den in Undirected zu überführen falsch?

[Sandra]

Das steht ebenfalls auf Folie 50. Da steht, dass der kNN-Graph ungerichtet ist. Dein angegebener Ansatz ist vollkommen korrekt.

[Sandra]

hallo, hab da ne frage zu 2.: sollte das ergebnis der nearest neighbor function nicht vielmehr eine n x k matrix sein?

Nein da kommt eine \(n \times n\) Matrix heraus, sonst muesstest du ja sowohl die Positionen als auch die Distanzwerte zurueck geben. Einfacher ist es da, wenn man die Distanzen direkt an der jeweiligen Position abspeichert.

[xAx]

hätte da leider wieder ein paar fragen:
1.) habe ich die my_nearestNeighbor jetzt richtig verstanden: sei W die ergebnismatrix. dann ist W(i,j) der eukl. abstand zwischen dem i-ten und j-ten Datenpunkt, falls dieser abstand zu den k kleinsten abständen vom Knoten i aus gehört. sonst ist W(i,j) gleich 0 (oder unendlich? jeder punkt hat ja zu sich selbst abstand 0).
2.) Die funktionen aus 3. sollen eine ungewichtete Adjazenzmatrix erstellen, also 1 ~ "verbunden" und 0 ~ "nicht verbunden". sollen die diagonaleinträge 1 oder 0 sein?
3.) zu 4.: sollen wir die gewichte mit dem gauß kernel berechnen? wie wählt man sigma? was passiert, wenn beim mutual graph ein punkt mit keinem anderen verbunden ist? wie sieht dann dessen grad aus (insbesondere in bezug auf die ähnlichkeit/distanz eines punktes zu sich selbst. wird diese aufaddiert?)
danke schonmal im vorraus.

[jlerch]

hätte da leider wieder ein paar fragen:
1.) habe ich die my_nearestNeighbor jetzt richtig verstanden: sei W die ergebnismatrix. dann ist W(i,j) der eukl. abstand zwischen dem i-ten und j-ten Datenpunkt, falls dieser abstand zu den k kleinsten abständen vom Knoten i aus gehört. sonst ist W(i,j) gleich 0 (oder unendlich? jeder punkt hat ja zu sich selbst abstand 0).
2.) Die funktionen aus 3. sollen eine ungewichtete Adjazenzmatrix erstellen, also 1 ~ "verbunden" und 0 ~ "nicht verbunden". sollen die diagonaleinträge 1 oder 0 sein?
3.) zu 4.: sollen wir die gewichte mit dem gauß kernel berechnen? wie wählt man sigma? was passiert, wenn beim mutual graph ein punkt mit keinem anderen verbunden ist? wie sieht dann dessen grad aus (insbesondere in bezug auf die ähnlichkeit/distanz eines punktes zu sich selbst. wird diese aufaddiert?)
danke schonmal im vorraus.

zu 1.) Ich habs so verstanden, dass w(i,j) = 0, wenn keine Verbindung besteht.
zu 2.) Wo liest du, dass die ungewichtet sein soll? Ich habe da die Gewichtung beibehalten.
zu 3.) Gauß Kernel? Ich bin eigentlich davon ausgegangen, dass man hier einfach die Eigenwerte und Eigenvektoren von L=D-W berechnet. W hat man ja bereits durch die Aufgaben 1-3 errechnet. Auf den Eigenvektoren dann gemäß Folie 20 kmeans anwenden. Ich frage mich hier aber noch, ob ich davon ausgehen darf, dass wenn Zi in Cluster 1, dann auch Xi in Cluster 1. Ich sehe hier nichts in den Folien, was auf die ursprünglichen Datensätze Rückschließe zieht.

[Sandra]

hätte da leider wieder ein paar fragen:
1.) habe ich die my_nearestNeighbor jetzt richtig verstanden: sei W die ergebnismatrix. dann ist W(i,j) der eukl. abstand zwischen dem i-ten und j-ten Datenpunkt, falls dieser abstand zu den k kleinsten abständen vom Knoten i aus gehört. sonst ist W(i,j) gleich 0 (oder unendlich? jeder punkt hat ja zu sich selbst abstand 0).[/quote]

korrekt. Aber ich wuerde die restlichen Punkte auf 0 setzen und nicht auf unendlich, sonst kannst du damit ja nicht rechnen. Und die Diagonale sollte null sein, d.h. keine Schleifen.

2.) Die funktionen aus 3. sollen eine ungewichtete Adjazenzmatrix erstellen, also 1 ~ "verbunden" und 0 ~ "nicht verbunden". sollen die diagonaleinträge 1 oder 0 sein?

0

3.) zu 4.: sollen wir die gewichte mit dem gauß kernel berechnen? wie wählt man sigma? was passiert, wenn beim mutual graph ein punkt mit keinem anderen verbunden ist? wie sieht dann dessen grad aus (insbesondere in bezug auf die ähnlichkeit/distanz eines punktes zu sich selbst. wird diese aufaddiert?)
danke schonmal im vorraus.

Ja das sind alles sehr spannende Fragen Du kannst sowohl den Gauss Kernel nehmen als auch einfach 1/0-Werte. Das waere auf jeden Fall einen Bonus wert, wenn man schaut, wie sich das auf das Clustering auswirkt.

Zu einem "guten" sigma gibt es unendlich viele Studien und Ansaetze, die mehr oder weniger gut funktionieren. Ein Ansatz ist zum Beispiel den "Radius" einer Gaussverteilung mit einer Art Minimum spanning tree Heuristik abzuschaetzen, indem man fuer eine Klasse beginnend einen MST erstellt bis man die naechste Klasse erreicht und diese Spannweite fuer das sigma nutzt. Oder man testet an einem kleinen Trainingset zum Beispiel verschiedene 10er Potenzen aus und waehlt dann die beste aus. Es lohnt sich auch mal einen Blick auf die Werte selbst zu werfen. Mit einigen sigmas sind alle Werte nahe 0 oder 1 und demzufolge nicht unterscheidbar. Damit kommt man in der Regel auch schon relativ weit.

@mutual graph: Das kann auftreten, dann hast du eine abgeschnittene Komponente. Im Idealfall will man ja genau so eine Graphenstruktur haben, d.h. alle Bilder von einer Klasse sind untereinander verbunden, aber keine Bilder von unterschiedlichen Klassen. Wenn eine einzelner Knoten abgeschnitten ist, dann hat er Grad null, so wie das auch im Grundstudium gelernt wurde. Welche Aehnlichkeit/Distanz zu sich selbst? Die ist doch null? Du kannst dir doch mal an einem kleinen Graphen genau dieses Szenario mit Matlab ansehen. Wie sieht die Laplacian aus? Wie sehen die Eigenwerte und -vektoren aus? Dann wird einiges klar ist.

[Sandra]

zu 2.) Wo liest du, dass die ungewichtet sein soll? Ich habe da die Gewichtung beibehalten.

Es geht wie gesagt beides.

zu 3.) Gauß Kernel? Ich bin eigentlich davon ausgegangen, dass man hier einfach die Eigenwerte und Eigenvektoren von L=D-W berechnet. W hat man ja bereits durch die Aufgaben 1-3 errechnet. Auf den Eigenvektoren dann gemäß Folie 20 kmeans anwenden. Ich frage mich hier aber noch, ob ich davon ausgehen darf, dass wenn Zi in Cluster 1, dann auch Xi in Cluster 1. Ich sehe hier nichts in den Folien, was auf die ursprünglichen Datensätze Rückschließe zieht.

Was genau ist \(Z_i\)? Wenn damit die Clusterzuordnung zu den Datenpunkten gemeint ist, dann verstehe ich die Frage nicht. Man wendet k-means an und dann erhaelt man fuer jeden Datenpunkt (=image) ein Cllusterzuweisung zurueck und dann schaut man sich anschliessend an, wie hoch die precision oder purity in den Clustern ist. Im Idealfall ist sie eins, genau dann, wenn die beiden Klassen exakt in zwei Cluster aufgesplittet wurden.

[jlerch]

Auf Folie 20 steht, dass die Eigenvektoren von L als Spalten zu einer Matrix V zusammengefasst werden. Die Zeilen werden als Zi bezeichnet und in kmeans geworfen. Was wir ursprünglich wollten ist Xi klassifizieren oder? Nun fehlt mir aber der Zusammenhang zwischen Zi und Xi.

[Sandra]

Ah ich verstehe. Das soll nur verdeutlichen, dass die Daten X in einen anderen Raum abgebildet werden. Es handelt sich dann nicht mehr um die urspruenglichen Daten X mit 10.000 Dimensionen sondern um die Daten Z mit nur noch vielleicht 50 Dimensionen (abhaengig wie viele Eigenvektoren man nutzt). Bild \(X_i\) ist also identisch mit \(Z_i\) nur dass sich die Repraesentation geaendert hat, so dass diese mit einem einfachen Clusteringverfahren wie k-means ganz leicht zu gruppieren sind.

Btw: Ich wurde wegen der Distanzfunktion gefragt, weil sie so langsam laeuft (> 15 min). In diesem Fall reicht es mir, wenn ihr die Distanzfunktion einmal programmiert habt und dann fuer die weiteren Berechnungen pdist von Matlab benutzt.

[xAx]

@mutual graph: Das kann auftreten, dann hast du eine abgeschnittene Komponente. Im Idealfall will man ja genau so eine Graphenstruktur haben, d.h. alle Bilder von einer Klasse sind untereinander verbunden, aber keine Bilder von unterschiedlichen Klassen. Wenn eine einzelner Knoten abgeschnitten ist, dann hat er Grad null, so wie das auch im Grundstudium gelernt wurde.

sry, hab vergessen zu schreiben, dass dann mein problem mit dem random walk laplacian zusammenhängt: hat ein knoten grad 0, dann kann man D = diag(d_i) nicht invertieren. So existieren bei mir bei den testdaten von der homepage selbst bei k = 250 im mutual graph immer noch unverbundene knoten (min(sum(mutual_kNN(X,250),2)) == 0)

Welche Aehnlichkeit/Distanz zu sich selbst? Die ist doch null?.

natürlich ist die distanz eines knotens zu sich selbst 0. aber eingesetzt in die formel für den gaußkernel kommt für exp(0) immer 1 raus. intuitiv finde ich das ok, da ein knoten immer perfekt ähnlich zu sich selbst ist. wenn ich also immer mind. 1 als grad hätte, würde mein oben beschriebenes problem nicht mehr existieren.

[Sandra]

Bei k=250 immer noch unverbundene Knoten? Das ist ja interessant! Ich habe bisher noch nie mit mutual Graphen experimentiert, da der kNN Graph der "Standardgraph" ist und da tritt das Problem ja nicht auf. In diesem Fall sollte man eps auf die Diagonale aufaddieren, dann kann man die Matrix zumindest invertieren. Es waere super, wenn du mal ins Forum die Indizes der unverbundenen Knoten (Bilder) posten koenntest, dann kann ich mal schauen, um welche Bilder es sich konkret handelt, weil ich das ehrlich gesagt fuer diesen Datensatz nicht erwartet haette.

@Diagonale: Ah ... ich verstehe. Du kannst natuerlich auch Grad 1 annehmen, was semantisch eigentlich nicht korrekt ist oder du addierst auf die Diagonale ein eps, wie oben beschrieben, was natuerlich auch irgendwie getrickst ist Das Ergebnis ist aber sehr aehnlich. Du kannst dir das ja mal mit einem kleinen Graphen veranschaulichen mit 6 oder 7 Knoten, wobei einer nicht verbunden ist. Die Eigenvektoren verhalten sich in beiden Faellen erwartungsgemaess.

[Stefano]

Hallo Sandra,

ich habe eine Frage zu den Datensätzen:

Ich nehme an, dass wir nur den zur Übung gehörigen Datensatz verwenden sollen (Apfel und Auto in der Matrix X).

Kann es sein, dass wir auch die Bilder aus der vorigen Cluster-Übung verwenden sollen?


Danke und Gruß
Stefano