analytics

Clustering-Algorithmen im Dienste des Data Mining

9. März 2023

Dieses Artikel ist ein Versuch, die jüngsten Fortschritte bei der Entwicklung wirksamer Ansätze für das Clustering von Daten zu systematisieren und einen ganzheitlichen Überblick darüber zu geben. Es ist nicht beabsichtigt, alle Clustering-Algorithmen im Detail zu beschreiben. Im Gegenteil, der Überblickscharakter des Artikels und die angesprochenen Themen werden helfen, sich in der Vielzahl der Clustering-Algorithmen zurechtzufinden.

Einführung

Clustering - die Zusammenfassung ähnlicher Objekte in Gruppen - ist eine der grundlegenden Aufgaben in der Datenanalyse und im Data Mining. Die Liste der Anwendungsbereiche ist lang: Bildsegmentierung, Marketing, Betrugsbekämpfung, Vorhersage, Textanalyse und viele andere. Clustering ist heute oft der erste Schritt in der Datenanalyse. Nach der Identifizierung ähnlicher Gruppen werden andere Methoden angewandt, und für jede Gruppe wird ein eigenes Modell erstellt.

Die Aufgabe des Clustering ist in der einen oder anderen Form in wissenschaftlichen Bereichen wie Statistik, Mustererkennung, Optimierung und maschinelles Lernen formuliert worden. Deshalb gibt es eine Vielzahl von Synonymen für den Begriff "Cluster" - Klasse, Taxon, Ballung.

Bis heute ist die Zahl der Methoden zur Partitionierung von Objektgruppen in Cluster recht groß - mehrere Dutzend Algorithmen und noch mehr deren Modifikationen. Wir sind jedoch an Clustering-Algorithmen im Hinblick auf ihre Anwendung im Data Mining interessiert.

Clustering im Data Mining

Clustering im Data Mining gewinnt an Wert, wenn es als eine der Stufen der Datenanalyse dient, um eine vollständige analytische Lösung aufzubauen. Für einen Analysten ist es oft einfacher, Gruppen ähnlicher Objekte auszuwählen, ihre Merkmale zu untersuchen und für jede Gruppe ein eigenes Modell zu erstellen, als ein allgemeines Modell für alle Daten zu entwickeln. Diese Technik wird im Marketing ständig eingesetzt, um Kunden-, Käufer- und Produktgruppen zu identifizieren und für jede von ihnen eine eigene Strategie zu entwickeln.

Die von der Data-Mining-Technologie verarbeiteten Daten weisen sehr häufig die folgenden wichtigen Merkmale auf:

• Hohe Dimensionalität (Tausende von Feldern) und hohes Volumen (Hunderttausende und Millionen von Datensätzen) von Datenbanktabellen und Data Warehouses;

• Datensätze enthalten eine große Anzahl numerischer und kategorischer Attribute.

Alle Attribute oder Eigenschaften von Objekten werden in numerische und kategorische unterteilt. Numerische Attribute sind solche, die im Raum geordnet werden können, bzw. kategorische Attribute, die nicht geordnet werden können. Zum Beispiel ist das Attribut "Alter" numerisch, während "Farbe" kategorisch ist. Die Zuweisung von Werten zu Attributen erfolgt während der Messungen durch den gewählten Skalentyp und ist im Allgemeinen eine separate Aufgabe.

Bei den meisten Clustering-Algorithmen werden Objekte auf der Grundlage eines bestimmten Maßes für die Nähe (Ähnlichkeit) miteinander verglichen. Ein Abstandsmaß ist ein Wert, der einen Grenzwert hat und mit zunehmender Entfernung von Objekten steigt. Näherungsmaße werden nach bestimmten Regeln "erfunden", und die Wahl der spezifischen Maße hängt von der Aufgabe und dem Maßstab der Messung ab. Der euklidische Abstand, der durch die Formel berechnet wird, wird sehr häufig als Näherungsmaß für numerische Attribute verwendet:

$D(x, y)=\sqrt{\sum_{i}(x-y)^2}$

Für Kategorieattribute sind das Sørensen-Czekanowski-Koeffizient und das Jaccard-Koeffizient üblich:

$(\left|t_{1}\cap t_{2} \right|/\left|t_{1}\cup t_{2} \right|)$

Die Notwendigkeit, große Datensätze im Data Mining zu verarbeiten, hat zur Formulierung von Anforderungen geführt, die der Clustering-Algorithmus nach Möglichkeit erfüllen sollte. Betrachten Sie sie:

1. Möglichst geringe Anzahl von Datenbankdurchläufen;

2. Operation in einem begrenzten Umfang des Computerspeichers;

3. Die Arbeit des Algorithmus kann unterbrochen werden, wobei die Zwischenergebnisse gespeichert werden, um die Berechnungen später fortzusetzen;

4. Der Algorithmus sollte funktionieren, wenn Objekte aus der Datenbank nur im unidirektionalen Cursor-Modus (d.h. im Datensatz-Navigationsmodus) abgerufen werden können.

Ein Algorithmus, der diese Anforderungen (insbesondere die zweite) erfüllt, wird als skalierbar bezeichnet. Skalierbarkeit ist die wichtigste Eigenschaft eines Algorithmus, die von seiner Rechenkomplexität und Softwareimplementierung abhängt. Es gibt aber auch eine umfassendere Definition. Ein Algorithmus wird als skalierbar bezeichnet, wenn die Betriebszeit linear mit der Zunahme der Anzahl der Dateneinträge in der Datenbank steigt, während die Speicherkapazität gleich bleibt.

Es ist jedoch nicht immer notwendig, sehr große Datenfelder zu verarbeiten. Aus diesem Grund wurden in den Anfängen der Theorie der Clusteranalyse die Fragen der Skalierbarkeit der Algorithmen fast vernachlässigt. Es wurde davon ausgegangen, dass alle verarbeiteten Daten in den Hauptspeicher passen würden, das Hauptaugenmerk lag immer auf der Verbesserung der Qualität der Clusterbildung.

Es ist schwierig, ein Gleichgewicht zwischen hoher Clustering-Qualität und Skalierbarkeit zu finden. Daher sollte Data Mining idealerweise sowohl über effiziente Algorithmen zum Clustern von Microarrays als auch über skalierbare Algorithmen zur Verarbeitung großer Datenbanken verfügen.

Clustering-Algorithmen: Glanz und Elend

Es ist also bereits möglich, Cluster-Algorithmen in skalierbar und nicht skalierbar zu unterteilen. Lassen Sie uns mit der Einordnung fortfahren.

Je nach der Methode des Clustering gibt es zwei Arten von Algorithmen: hierarchische und nicht-hierarchische. Klassische hierarchische Algorithmen funktionieren nur bei Kategorieattributen, wenn ein vollständiger Baum verschachtelter Cluster konstruiert wird. Hier sind agglomerative Methoden zur Bildung von Clusterhierarchien üblich - sie führen eine sequentielle Assoziation von Ausgangsobjekten und eine entsprechende Reduzierung der Anzahl von Clustern durch. Hierarchische Algorithmen bieten eine relativ hohe Qualität beim Clustering und erfordern keine vorherige Festlegung der Anzahl der Cluster. Die meisten von ihnen haben eine Komplexität von $O(n^{2})$.

Nicht-hierarchische Algorithmen beruhen auf der Optimierung einer Zielfunktion, die die optimale Aufteilung einer Menge von Objekten in Cluster in einem bestimmten Sinne bestimmt. In dieser Gruppe sind Algorithmen der k-means-Familie (k-means, fuzzy c-means, Gustafson-Kessel) verbreitet, die als Zielfunktion die Summe der Quadrate der gewichteten Abweichungen der Objektkoordinaten von den Zentren der gesuchten Cluster verwenden.

Die Cluster sind entweder kugelförmig oder ellipsoidisch. Bei der kanonischen Implementierung basiert die Funktionsminimierung auf der Methode der Lagrange-Multiplikatoren und ermöglicht es, nur das nächstgelegene lokale Minimum zu finden. Die Verwendung globaler Suchmethoden (genetische Algorithmen) erhöht die Rechenkomplexität des Algorithmus erheblich.

Unter den nicht-hierarchischen, nicht-distanzbasierten Algorithmen ist der EM-Algorithmus (Expectation-Maximization) hervorzuheben. Anstelle von Clusterzentren wird für jedes Cluster eine Wahrscheinlichkeitsdichtefunktion mit entsprechendem Erwartungswert und Varianz angenommen. Die Verteilungsmischung (Abbildung unten) wird nach dem Prinzip der maximalen Wahrscheinlichkeit auf ihre Parameter (Mittelwerte und Standardabweichungen) hin untersucht. Der EM-Algorithmus ist eine Implementierung einer solchen Suche. Das Problem besteht darin, dass vor dem Start des Algorithmus eine Hypothese über die Art der Verteilungen aufgestellt wird, die im gesamten Datensatz schwer zu schätzen sind.

Ein weiteres Problem tritt auf, wenn die Attribute eines Objekts gemischt sind - ein Teil ist vom numerischen Typ und der andere Teil vom Typ Kategorie. Berechnen wir zum Beispiel den Abstand zwischen den folgenden Objekten mit den Attributen (Alter, Geschlecht, Bildungsstand):

{23, männlich, Hochschulbildung}, (1)

{25, weiblich, Schulabschluss}, (2)

Das erste Attribut ist numerisch, die anderen sind kategorisch. Wenn wir einen klassischen hierarchischen Algorithmus mit einem beliebigen Ähnlichkeitsmaß verwenden wollen, müssen wir das Attribut "Alter" in irgendeiner Weise diskreditieren. Zum Beispiel so:

{unter 30, männlich, Hochschulbildung}, (1)

{unter 30, weiblich, Schulabschluss}, (2)

Dabei werden wir sicherlich einige Informationen verlieren. Wenn wir den Abstand im euklidischen Raum definieren, gibt es Probleme mit den Kategorieattributen. Es ist klar, dass der Abstand zwischen "Geschlecht männlich" und "Geschlecht weiblich" 0 ist, da die Werte dieses Attributs in der Benennungsskala liegen. Und das Attribut "Bildungsstand" kann entweder auf der Namensskala oder auf der Ordnungsskala gemessen werden, indem jedem Wert bestimmte Punkte zugewiesen werden.

Welche Option ist die richtige? Was ist, wenn kategoriale Attribute wichtiger sind als numerische Attribute? Es ist Aufgabe des Analytikers, diese Probleme zu lösen. Darüber hinaus gibt es bei der Verwendung des k-means-Algorithmus und anderer ähnlicher Algorithmen Schwierigkeiten beim Verständnis der Clusterzentren der Kategorieattribute, bei der Festlegung der Anzahl der Cluster als Voreinstellung.

Der Optimierungsalgorithmus für die Zielfunktion in nicht-hierarchischen distanzbasierten Algorithmen ist iterativ, und bei jeder Iteration muss die Distanzmatrix zwischen den Objekten berechnet werden. Bei einer großen Anzahl von Objekten ist dies ineffizient und erfordert erhebliche Rechenressourcen. Die Rechenkomplexität der ersten Iteration des k-means-Algorithmus wird auf O(kmn) geschätzt, wobei k, m und n die Anzahl der Cluster, Attribute bzw. Objekte sind. Aber es kann eine riesige Anzahl von Iterationen geben! Der Datensatz muss mehrmals durchlaufen werden.

Die Idee von k-means, kugelförmige oder ellipsenförmige Cluster zu finden, birgt viele Nachteile in sich. Der Ansatz funktioniert gut, wenn die Daten im Raum kompakte Klumpen bilden, die gut voneinander unterscheidbar sind. Wenn die Daten jedoch verschachtelt sind, wird keiner der Algorithmen der k-means-Familie die Aufgabe erfüllen. Der Algorithmus funktioniert auch nicht gut, wenn ein Cluster viel größer als die anderen ist und sie nahe beieinander liegen - es gibt einen "Aufspaltungs"-Effekt eines großen Clusters (Abb. unten).

Die Forschung zur Verbesserung von Clustering-Algorithmen ist jedoch noch nicht abgeschlossen. Der K-Means-Algorithmus hat interessante Erweiterungen entwickelt, um Kategorieattribute (K-Modes) und gemischte Attribute (K-Prototypes) zu behandeln. Zum Beispiel berechnet K-Prototypes die Abstände zwischen Objekten je nach Attributtyp unterschiedlich.

Auf dem Gebiet der skalierbaren Clustering-Algorithmen geht es darum, jeden "zusätzlichen" Durchlauf durch den Datensatz während der Ausführung des Algorithmus zu reduzieren. Es wurden skalierbare K-Means und skalierbare EM-Analogien sowie skalierbare agglomerative Methoden (CURE, CACTUS) entwickelt. Diese modernen Algorithmen benötigen nur wenige (zwei bis zehn) Datenbankabfragen, bevor sie das endgültige Clustering erhalten.

Die Ableitung skalierbarer Algorithmen basiert auf der Idee, die lokale Optimierungsfunktion wegzulassen. Der paarweise Vergleich von Objekten im K-Means-Algorithmus ist nichts anderes als eine lokale Optimierung, da bei jeder Iteration der Abstand vom Clusterzentrum zu jedem Objekt berechnet werden muss. Dies führt zu einem hohen Rechenaufwand.

Mit der globalen Optimierungsfunktion ist das Hinzufügen eines neuen Punktes zum Cluster nicht rechenintensiv: Es wird auf der Grundlage des alten Wertes, des neuen Objekts und der so genannten Clustermerkmale berechnet. Die spezifischen Cluster-Merkmale hängen von dem jeweiligen Algorithmus ab. Auf diese Weise sind BIRCH, LargeItem, CLOPE und viele andere Algorithmen entstanden.

Es gibt also keinen einzigen universellen Clustering-Algorithmus. Bei der Verwendung eines Algorithmus ist es wichtig, seine Stärken und Schwächen zu kennen und die Art der Daten, mit denen er am besten funktioniert, sowie seine Skalierbarkeit zu berücksichtigen.