Wie in der Einleitung beschrieben, untersuchen wir Datensätze, bei denen alle Objekte zwei Werte besitzen, sodass jeder Datensatz auch als Punktmenge in der Ebene angesehen werden kann.
Es sei bemerkt, dass die folgenden Beschreibungen sowie der Algorithmus zur Lösung des Problems auch auf Daten mit einer beliebigen Anzahl an Werten bzw. Merkmalen verallgemeinert werden können.
Ist also eine Punktmenge in der Ebene gegeben, so gibt es unterschiedliche Möglichkeiten, das zugehörige Problem der Clusteranalyse zu formulieren. Wie behandeln in diesem Kurs die folgende Aufgabe:
Die Punktmenge soll derart in k Cluster (Gruppen) aufgeteilt werden, sodass die Summe der quadrierten Abstände von den Cluster-Mittelpunkten zu den einzelnen Punkten des Clusters minimiert wird.
Der Mittelpunkt eines Clusters ist dabei als Schwerpunkt der Punkte zu verstehen, die dem Cluster angehören. Veranschaulicht wird dies anhand der folgenden Abbildungen:
Gegeben ist eine Punktmenge bestehend aus 48 Punkten (oben links), die in drei Cluster aufgeteilt werden sollen. Eine mögliche Lösung zeigt die Darstellung in oben rechts: Die roten Linien veranschaulichen die Abstände von den einzelnen Punkten zum jeweiligen Cluster-Mittelpunkt. Mit anderen Worten gehören alle Punkte mit einem gemeinsamen Cluster-Mittelpunkt demselben Cluster an und können entsprechend farblich markiert werden (unten links). Die Ebene wird dadurch in sogenannte Voronoi-Zellen zerlegt (unten rechts).
Als kleinen Exkurs lässt sich das Problem mathematisch folgendermaßen formulieren: Gegeben sei eine Punktemenge und mit bis beschreiben wir eine (disjunkte) Zerlegung der Punktemenge in Cluster.
Das zuvor beschriebene Problem bedeutet nichts anderes als die Cluster bis derart zu wählen, sodass die Zielfunktion
minimiert wird. Dabei werden mit
die Cluster-Mittelpunkte (bzw. Schwerpunkte der Cluster) bezeichnet.
An dieser Stelle sei direkt bemerkt, dass im Allgemeinen keine Optimallösung gefunden werden kann. Denn obwohl sich das Problem recht einfach formulieren lässt, ist es extrem schwer zu lösen. Der Lösungsansatz der folgenden Abschnitte beschreibt daher ein Verfahren, welches in der Regel eine gute Lösung bestimmt, ohne dabei zu wissen, ob es sich um eine Optimallösung handelt oder nicht.