Spektrale Relaxation

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

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.

Spektrale Relaxation arbeitet auf einem vollständigen, ungerichteten Graphen ${\displaystyle G:=(V,E)}$. Jeder Knoten ${\displaystyle v\in V}$ des Graphen stellt einen Punkt der Punktewolke dar. Jede Kante ${\displaystyle e\in E}$ ist mit einem Gewicht ${\displaystyle 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 ${\displaystyle n}$ Punkten, so ist das Ziel, eine Menge ${\displaystyle C}$ von ${\displaystyle n}$ Kanten so auszuwählen, dass die Summe der Kantengewichte möglichst klein ist:

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