2.4.1: Cluster

Abbildung 65 zeigt ein Beispiel, in dem die Ähnlichkeit zu verschiedenen Prototypen als Kriterium verwendet wurde, um Tupel in überlappende Teilmengen einzuteilen. Ein ähnliches Verfahren wurde auch in SMART verwendet, wobei dort der Abstand zum Zentroid der Vektoren einer Teilmenge, also zu deren arithmetischem Mittel berechnet wurde.

Abbildung 65: Cluster-Bildung mit der Hamming Distance

Während diese Teilmengen der Grundmenge sich überlappen, können z.B. mit der Single-Link- oder der Complete-Link-Methode disjunkte Zerlegungen einer Menge von Beispielen, zwischen denen eine Ähnlichkeitsfunktion definiert ist, berechnet werden. Beide Methoden sind Bottom-up-Verfahren, die sich nur durch die Definition der Ähnlichkeit zwischen zwei Teilmengen unterscheiden. Zunächst wird für jedes Beispiel einer Sammlung ein eigener Cluster anlegt, der nur dieses Beispiel enthält. Dann werden schrittweise jeweils die beiden Cluster vereinigt, die sich am ähnlichsten sind. Bei der Definition der Ähnlichkeit unterscheiden sich die beiden Verfahren: Bei der Single-Link-Methode wird die Ähnlichkeit zweier Teilmengen als die größte Ähnlichkeit zwischen einem Beispiel aus der einen und einem aus der anderen definiert, während die Complete-Link-Methode die kleinste Ähnlichkeit verwendet. Dieser Schritt kann so lange wiederholt werden, bis schließlich nur noch ein Cluster existiert. Wie bei den streng hierarchischen Klassifikationen ergibt sich auch hier eine Baumstruktur, auf deren Ebenen die Gesamtmenge der Beispiele in unterschiedlich viele (und damit in der Regel unterschiedlich große) Teilmengen zerlegt wird. Die Anzahl der Cluster ergibt sich durch die Anzahl der Vereinigungsschritte.