Graphenreduktion

In einem ersten Schritt wird der Graph reduziert. Ziel ist es dabei, alle Kanten mit zu großen Gewichten aus dem Graphen zu entfernen. Folgende Ansätze gibt es:

${\displaystyle \epsilon }$ Nachbarschaftsgraph

Wenn das Kantengewicht größer als ${\displaystyle \epsilon }$ ist, dann wird diese Kante aus dem Graph entfernt.

k-nn Graphen (${\displaystyle k}$ nächste Nachbarngraphen)

Alle Kanten zu einem Knoten werden nach dem Kantengewicht sortiert. Hat eine Kante ein größeres Kantengewicht als das ${\displaystyle k}$ kleinste Kantengewicht, dann wird diese Kante aus dem Graph entfernt. Die ${\displaystyle k}$-nn Relation ist jedoch nicht symmetrisch, d. h. es kann passieren, dass das Kantengewicht ${\displaystyle w_{ij}}$ kleiner ist als das ${\displaystyle k}$ kleinste Kantengewicht zum Objekt ${\displaystyle o_{i}}$, aber nicht kleiner ist als das ${\displaystyle k}$ kleinste Kantengewicht zum Objekt ${\displaystyle o_{j}}$. Man spricht von einem k-nn Graph, wenn die Kante im Graph bleibt, falls für mindestens eines der Objekte ${\displaystyle o_{i}}$ oder ${\displaystyle o_{j}}$ gilt, dass ${\displaystyle w_{ij}}$ kleiner ist als das ${\displaystyle k}$ kleinste Kantengewicht zum Objekt, d. h. jedes Objekt hat mindestens ${\displaystyle k}$ Kanten. Im Gegensatz dazu enthält ein gemeinsamer k-nn Graph nur die Kante, wenn für beide Objekte gilt, dass ${\displaystyle w_{ij}}$ kleiner ist als das ${\displaystyle k}$ kleinste Kantengewicht der Objekten, d. h. jedes Objekt hat maximal ${\displaystyle k}$ Kanten.

Voll verbundener Graph

Mit Hilfe einer Ähnlichkeitsfunktion werden die Kantengewichte aus den Distanzen zwischen den Objekten berechnet. Ein Beispiel für eine Ähnlichkeitsfunktion ist die gaußsche Ähnlichkeitsfunktion ${\displaystyle s(o_{i},o_{j})=\exp(-{\tfrac {1}{2}}d^{2}(o_{i},o_{j})/\sigma ^{2})}$. Der Parameter ${\displaystyle \sigma }$ kontrolliert die Größe der Nachbarschaft wie auch die Parameter ${\displaystyle \epsilon }$ oder ${\displaystyle k}$.

• Position von 8 Objekten in einem zweidimensionalen Raum.
• Voll verbundener Graph mit den euklidischen Distanzen an den Kanten für die 8 Objekte.
• Distanzmatrix der euklidischen Distanzen für die 8 Objekte.
• ${\displaystyle \epsilon }$ Nachbarschaftsgraph (${\displaystyle \epsilon =5}$ ) für die 8 Objekte.
• k-nn Graph (${\displaystyle k=2}$) für die 8 Objekte. Jeder Knoten hat mindestens zwei Kanten.
• Gemeinsamer k-nn Graph (${\displaystyle k=2}$) für die 8 Objekte. Jeder Knoten hat maximal zwei Kanten. Der Datensatz zerfällt in 3 Zusammenhangskomponenten.
• Laplace-Matrix ${\displaystyle L_{rw}}$ des gemeinsamen k-nn Graphen (${\displaystyle k=2}$) für die 8 Objekte.
• Voll verbundener Graph mit den Werten der gaußschen Ähnlichkeitsfunktion (${\displaystyle \sigma =3}$) an den Kanten für die 8 Objekte.

Laplace-Matrizen

Aus den Kantengewichten wird für die ${\displaystyle n}$ Objekte die (gewichtete) Adjazenzmatrix ${\displaystyle W}$ gebildet. Die Diagonalmatrix ${\displaystyle D}$ enthält auf der Diagonalen die Summe der Kantengewichte, die zu einem Knoten führen (nach der Graphenreduktion). Dann können drei Laplace-Matrizen berechnet werden:

• nicht-normalisierte Matrix ${\displaystyle L=D-W}$,
• die normalisierte Matrix ${\displaystyle L_{sym}=D^{-1/2}LD^{-1/2}}$ und
• die normalisierte Matrix ${\displaystyle L_{rw}=D^{-1}L}$.

Für alle Vektoren ${\displaystyle f\in R^{n}}$ gilt

${\displaystyle {\begin{array}{rcll}f^{T}Lf&=&\displaystyle {\tfrac {1}{2}}\sum _{i,j=1}^{n}w_{ij}\left(f_{i}-f_{j}\right)^{2}&\geq 0,\\f^{T}L_{sym}f&=&\displaystyle {\tfrac {1}{2}}\sum _{i,j=1}^{n}w_{ij}\left({\tfrac {f_{i}}{\sqrt {d_{i}}}}-{\tfrac {f_{j}}{\sqrt {d_{j}}}}\right)^{2}&\geq 0.\\f^{T}L_{rw}f&=&\displaystyle {\tfrac {1}{2}}\sum _{i,j=1}^{n}w_{ij}\left(f_{i}-f_{j}\right)^{2}&\geq 0\\\end{array}}}$

Da die Laplace-Matrizen symmetrisch und positiv-semidefinit sind, sind alle Eigenwerte reellwertig und größer gleich Null. Für die Laplace-Matrix kann man zeigen, dass mindestens ein Eigenwert gleich Null ist. Besteht der Graph aus ${\displaystyle k}$ Zusammenhangskomponenten, dann sind die Laplace-Matrizen Blockmatrizen (siehe Grafik und Matrix oben). Dabei hat jeder Block einen Eigenwert gleich Null. Für die Eigenvektoren zum Eigenwert Null muss ${\displaystyle f^{T}Lf=0}$ sein. Da alle Kantengewichte ${\displaystyle w_{ij}}$ positiv sind, müssen alle Einträge ${\displaystyle f_{i}}$ der Knoten einer Zusammenhangskomponente gleich sein (damit ${\displaystyle f_{i}-f_{j}=0}$ gilt). Analog gilt dies für ${\displaystyle L_{sym}}$, nur dass die Einträge im Eigenvektor mit ${\displaystyle d_{i}}$ gewichtet sind, während für ${\displaystyle L_{rw}}$ die Einträge ${\displaystyle f_{i}}$ im Eigenvektor gleich Eins sind.

Zum Clustern analysiert man die kleinsten Eigenwerte und -vektoren der Laplace-Matrizen.

• Eigenwerte der Laplace-Matrix des Gemeinsamen k-nn Graph (${\displaystyle k=3}$) für die 8 Objekte Daten. Da der Graph aus drei Zusammenhangskomponenten besteht ergeben sich drei Eigenwerte mit dem Wert Null.
• Werte der drei Eigenvektoren zum Eigenwert Null der Laplace-Matrix ${\displaystyle L_{rw}}$. Die Einträge sollten gleich Eins sein, aber die Software reskaliert die Eigenvektoren, so dass sie die Länge Eins haben.
• 3D-Streudiagramm der drei Eigenvektoren zu den Null-Eigenwerten. Die acht Objekte werden an drei Positionen geplottet (overplotting), so dass ein k-Means Clustering die drei Zusammenhangskomponenten perfekt finden kann.