BI-Methoden (Teil 3): Data Mining im Detail

Hierarchische und partitionierende Clusterverfahren

Basis für die Anwendungen von Clusterverfahren ist die Festlegung geeigneter Ähnlichkeitsmaße. Diese müssen sowohl zwischen je zwei Datensätzen als auch zwischen je zwei Gruppen festgelegt werden. Ein quantitatives Ähnlichkeitsmaß wäre etwa der Euklidische Abstand zwischen den quantitativen Attributwerten, ein qualitatives Ähnlichkeitsmaß die Anzahl der übereinstimmenden Attributwerte zweier Datensätze.

Clusterverfahren lassen sich grundsätzlich in hierarchische und partitionierende Verfahren unterteilen. Das hierarchischen Clustering untergliedert sich wiederum in agglomerative und diversive Methoden.

Beim agglomerativen Verfahren werden mit jedem Iterationsschritt, ausgehend von einzelnen Elementen, die ähnlichsten Daten zusammengefasst. Auf diese Weise entsteht eine neue Partition, deren Clusterzahl geringer ist. Agglomerative Verfahren unterscheiden sich im Wesentlichen in der Definition des Ähnlichkeitsmaßes zwischen den Clustern.

Beim diversiven Verfahren werden ausgehend von einer Gesamtdatenmenge in jedem Schritt die unterscheidbarsten Daten geteilt. Dabei wird die Gesamtdatenmenge in immer kleinere Teilmengen aufgespaltet, bis schließlich die Partition entsteht, deren Cluster aus jeweils den einzelnen Datensätzen besteht. Das diversive Verfahren wird in der Praxis selten angewendet.

Die partitionierenden Verfahren gehen von einer vordefinierten Clusteranzahl aus, wobei jeder Datensatz sukzessive in die Klasse eingeteilt wird, deren Ähnlichkeit zum Datensatz am größten ist. Ein populärer Vertreter ist das k-Means-Verfahren. Weitere Ansätze zur Clusterbildung sind Fuzzy-Methoden oder das Erwartungs-Maximierungsverfahren.