Real-time Data Mining: Datenmodellierung und Mustererkennung in Echtzeit (PDF)

Datenbasis jeweils dem am nächsten liegenden cluster center zu. Da diese Einteilung in der Regel nicht optimal ist, werden den Objekten im zweiten Schritt näher liegende cluster centers zugeordnet um die Gesamtsumme der Abstände zu verringern. Im Anschluss werden die neuen cluster centers berechnet. Dieser Vorgang wird solange wiederholt, bis keine Änderung in den Clustern mehr auftritt. Der Algorithmus hat eine Laufzeitkomplexität von O(knt) bei t Iterationen. Er arbeitet nur für kleine Datenbanken ausreichend effizient. Für größere Datenbanken, wie VLDBs, verwendet man daher oft sampling-basierte Varianten des k-Means Algorithmus wie z.B. CLARA (Clustering LARge Applications). Inkrementelle Varianten von Clustering Algorithmen konzentrieren sich auf dichte-basierte und hierarchische Verfahren, die im Folgenden beschrieben werden.

Dichte-basierte Verfahren betrachten Cluster als beliebig geformte Gebiete mit einer hohen Konzentration von Objekten in einem d-dimensionalen Raum. Zwischen diesen Clustern befinden sich Regionen, die eine sehr geringe Konzentration von Objekten aufweisen. Die sog. lokale Punktdichte eines Objekts o bezeichnet die Anzahl der Objekte innerhalb einer festgelegten Umgebung um o herum. Eine hohe Konzentration von Objekten wird als eine lokale Punktdichte innerhalb von Clustern definiert, die einen bestimmten Grenzwert überschreitet. Der DBSCAN (Density-Based Spatial Clustering of Applications with Noise)-Algorithmus ist ein Vertreter der dichte-basierten Verfahren, für die auch eine inkrementelle Variante existiert. Diese wird im Abschnitt 3.3.2 vorgestellt.

Bei hierarchischen Clustering-Verfahren wird eine Menge von Objekten hierarchisch in einer Baumstruktur, dem sog. Dendrogramm, angeordnet. Aus dem Baum kann dann eine Clusterstruktur abgeleitet werden, sodass der Cluster an der Wurzel des Baums sämtliche Objekte enthält und die Cluster an den Blättern die einzelnen Objekte enthalten. Jede Stufe in dem Baum entspricht dann einer Clusterstruktur. Um die Baumstruktur zu generieren, werden agglomerative (bottom-up) und divisive (top-down) Methoden unterschieden. Bei den agglomerativen Methoden wird zunächst jedes Objekt einem eigens generierten Cluster zugeordnet. Diese werden dann in den nächsten Schritten zu größeren Clustern zusammengefasst bis zum Schluss nur noch ein einziger übrig ist. Der Großteil der Methoden des hierarchischen Clustering gehört zu dieser Kategorie. Die divisiven Methoden beginnen mit einem großen Cluster, der zunächst alle Objekte enthält. Schritt für Schritt wird dieser dann aufgespaltet, bis alle Cluster atomar sind, also nur noch ein einziges Objekt enthalten. Ein Algorithmus, der Elemente sowohl der dichte-basierten, als auch der hierarchischen Verfahren verwendet, ist der OPTICS (Ordering Points To Identify the Clustering Structure)-Algorithmus. Er kann als Erweiterung des DBSCAN angesehen werden. Die Grundidee des OPTICS und seine inkrementelle Variante, der IncOPTICS, werden in Abschnitt 3.3.3 vorgestellt.