Das Ziel der Clusteranalyse besteht wie bereits beschrieben darin, ähnliche Objekte eines Datensatzes zu einem Cluster zusammenzuführen. Dabei stellt sich zunächst die Frage, wie die Ähnlichkeit zweier Objekte überhaupt definiert werden sollte.
Im Allgemeinen können sehr unterschiedliche sogenannten Ähnlichkeitsmaße verwendet werden. Eine spezielle Klasse von Ähnlichkeitsmaßen, auf die wir zurückgreifen werden, sind Abstandsmaße: Je näher zwei Objekte beieinander liegen, desto ähnlicher sind sie. Aber auch hier gibt es viele Möglichkeiten, von denen wir einige vorstellen.
Das bekannteste Abstandsmaß ist die Euklidische Metrik. Wie aus der Schule bekannt, wird der Abstand zwischen zwei Punkten und folgendermaßen bestimmt:
Es handelt sich dabei um die Länge, die man mit einem Lineal messen kann. Die Metrik lässt sich auch für Vektoren (Objekte) mit einer beliebigen Anzahl an Variablen (Merkmalen) berechnen:
Es sei bemerkt, dass beim k-Means-Algorithmus in der Regel die quadrierte Euklidische Metrik als Abstandsmaß eingesetzt wird.
Je nach Anwendungsfall kann es aber auch sinnvoll sein, ein anderes Abstandsmaß zu verwenden. Die Manhattan-Metrik beispielsweise ist folgendermaßen definiert:
Der Name ist motiviert durch die Länge eines kürzesten Weges zwischen zwei Kreuzungen im Straßengitter von Manhattan:
Die Länge der Linie A entspricht dem Abstand nach der Euklidischen Metrik. Die Länge des Linienzuges B entspricht dem Abstand nach der Manhattan-Metrik.
Schließlich kann auch die Maximum-Metrik eingesetzt werden, die folgendermaßen definiert ist:
Welches Abstandsmaß bei der Clusteranalyse verwendet werden sollte, kann nicht pauschal beantwortet werden. Die Wahl der Metrik ist in Abhängigkeit der Eigenschaften der vorliegenden Daten zu treffen.
Bei den Beispielen und Abbildungen in den nachfolgenden Abschnitten werden wir vor allem auf die Euklidische Metrik zurückgreifen. Diese hat den Vorteil, dass sich Datensätze mit zwei Merkmalen (Punkte in der Ebene) visuell geeignet darstellen lassen.
