Spektrale Relaxation

Spektrale Relaxation (meist engl. spectral relaxation) ist ein Algorithmus der hierarchischen Clusteranalyse.

Die Clusteranalyse dient dazu, natürliche Ballungen in einer Punktewolke zu finden. Im Fall der spektralen Relaxation kann man sich die Punktewolke anschaulich als Netz vorstellen: Jeder Punkt ist mit jedem anderen durch eine Schnur verbunden. Die spektrale Relaxation zerschneidet dieses Netz nun in zwei möglichst gleich große Netze.

Datenstruktur

Spektrale Relaxation arbeitet auf einem vollständigen, ungerichteten Graphen G: = (V,E). Jeder Knoten $v \in V$ des Graphen stellt einen Punkt der Punktewolke dar. Jede Kante $e \in E$ ist mit einem Gewicht d(e) versehen; dieses Gewicht ist ein Distanzmaß und spiegelt wider, wie ähnlich sich die durch die Knoten vertretenen Punkte sind.

Besteht die Punktewolke aus n Punkten, so ist das Ziel, eine Menge C von n Kanten so auszuwählen, dass die Summe der Kantengewichte möglichst klein ist:

$C := \{ \{ e_{1}, ..., e_{n} | e_{i} \in E \} | \sum_{e \in C} d(e) \rightarrow \min \}$