Textprobe: Kapitel 3.3, Inkrementelles Clustering: Das Clustering ist ein wichtiges Teilproblem des Data Mining, das von der deskriptiven Modellierung (Abschnitt 2.1) zugeordnet wird. Beim Clustering werden Objekte einer Datenbank in apriori unbekannte Gruppen, als Cluster bezeichnet, so eingeteilt, dass die Objekte in einem Cluster möglichst ähnlich zueinander und die Objekte in verschiedenen Clustern möglichst unterschiedlich voneinander sind. Aktuelle Herausforderungen für Clustering-Algorithmen in Bezug auf immer größere und komplexere Datenmengen werden in diskutiert. Eine Möglichkeit zur Leistungssteigerung wird neben verbesserten Indexstrukturen, Datenkompression und anderen Ansätzen in der Entwicklung inkrementeller Clustering-Algorithmen gesehen. In diesem Abschnitt sollen einige der bekanntesten Vertreter dieser Verfahren vorgestellt werden. Eine Auswahl an existierenden Algorithmen zum inkrementellen Clustering zeigt Abbildung 9 (siehe Abbildung 9: Inkrementelle Algorithmen zum Clustering).. Darin werden zu den, im folgenden Abschnitt vorgestellten, Klassen von Clustering-Verfahren, einige Vertreter zusammen mit deren inkrementellen Varianten dargestellt. Nach einer kurzen Einführung in das Clustering im Abschnitt 3.3.1 werden die dargestellten Varianten in den darauf folgenden Abschnitten beschrieben. Grundlagen des Clustering: Es existieren drei unterschiedliche Klassen von Verfahren, auf denen existierende Clustering-Algorithmen aufbauen: Partitionierende Verfahren, Dichte-basierte Verfahren, Hierarchische Verfahren. Die partitionierenden Verfahren, deren bekanntester Vertreter der k-Means Algorithmus ist, zerlegen eine Datenmenge in eine festgelegte Anzahl von k Clustern, wobei jeder Cluster mindestens ein Objekt enthalten muss und jedes Objekt genau einem Cluster zugeordnet ist. Im ersten Schritt bestimmt der k-Means Algorithmus k zufällig gewählte Punkte, die cluster center, und ordnet dann jedes Objekt der 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.