Spektrale ClusterbildungEs handelt sich um eine Clustering-Methode, die auf der Graphentheorie basiert. Es unterteilt einen gewichteten ungerichteten Graphen in zwei oder mehr optimale Teilgraphen. Die Teilgraphen sind intern ähnlich und weit voneinander entfernt, um eine Clusterung zu erreichen. Sein Wesen besteht darin, das Clusterproblem in das optimale Partitionierungsproblem des Graphen umzuwandeln. Es handelt sich um einen Punkt-zu-Punkt-Clustering-Algorithmus.

Im Vergleich zu herkömmlichen Clustering-Algorithmen bietet das spektrale Clustering die Möglichkeit, Proben in beliebig geformten Räumen zu clustern und zur globalen optimalen Lösung zu konvergieren. Der Algorithmus definiert eine Affinitätsmatrix basierend auf einer gegebenen Stichprobe, die zur Beschreibung der Ähnlichkeit gepaarter Datenpunkte verwendet wird, berechnet die Eigenwerte und Eigenvektoren der Matrix und wählt geeignete Eigenvektoren aus, um verschiedene Datenpunkte zu clustern. Spektrale Clustering-Algorithmen wurden zunächst in der Computervision, im VLSI-Design und in anderen Bereichen eingesetzt und kamen erst ab 2005 im maschinellen Lernen zum Einsatz.

Merkmale der spektralen Clusterbildung

Spektrales Clustering ist ein weit verbreiteter Clustering-Algorithmus. Es ist besser an die Datenverteilung anpassbar als der K-Means-Algorithmus und verfügt über einen hervorragenden Clustering-Effekt. Gleichzeitig ist der Clusterberechnungsaufwand geringer und die Implementierung nicht kompliziert.

Spektrale Clustering-Methode

Beim Clustering werden Proben sinnvoll in zwei oder K Teile aufgeteilt. Aus der Perspektive der Graphentheorie ist das Clusterproblem äquivalent zum Graphsegmentierungsproblem.

Bei einem Graphen G = (V, E), bei dem die Knotenmenge V jede Stichprobe darstellt und die gewichteten Kanten die Ähnlichkeit zwischen den einzelnen Stichproben darstellen, besteht der Zweck der spektralen Clusterbildung darin, eine sinnvolle Partitionierungsmethode zu finden, sodass die Kantengewichte, die die Teilgraphen nach der Partitionierung verbinden, so niedrig wie möglich und die Gewichte der Kanten innerhalb desselben Teilgraphen so hoch wie möglich sind.

Teilwort: Clustering

Verwandte Wörter / Bedeutung: graphentheorie