Überblick über die hierarchische Clusteranalyse

Bevor wir uns mit der hierarchischen Clusteranalyse befassen, versuchen wir zunächst zu verstehen, was ein Cluster ist. Und was ist Clusteranalyse? Ein Cluster ist eine Sammlung von Datenobjekten. Die Datenpunkte in einem Cluster sind einander ähnlicher und unterscheiden sich von den Datenpunkten im anderen Cluster. Die Clusteranalyse ist im Grunde eine Gruppierung dieser Datenpunkte in einem Cluster. Clustering ist eine Art von unbeaufsichtigtem maschinellem Lernalgorithmus, bei dem keine trainingsbezogenen Datensätze vorhanden sind. Es gibt verschiedene Arten der Clusteranalyse. Eine davon ist das hierarchische Clustering.

Hierarchisches Clustering hilft beim Erstellen von Clustern in der richtigen Reihenfolge / Hierarchie. Beispiel: Das häufigste alltägliche Beispiel ist, wie wir unsere Dateien und Ordner in unserem Computer nach der richtigen Hierarchie ordnen.

Arten der hierarchischen Clusterbildung

Hierarchisches Clustering wird weiter in zwei Typen unterteilt: Agglomeratives Clustering und Divisives Clustering (DIANA).

Agglomeratives Clustering

In diesem Fall von Clustering erfolgt die hierarchische Zerlegung mithilfe einer Bottom-up-Strategie. Dabei werden zunächst atomare (kleine) Cluster erstellt, indem jeweils ein Datenobjekt hinzugefügt und am Ende zu einem großen Cluster zusammengeführt wird, wobei dieser Cluster alle Kündigungsbedingungen erfüllt. Diese Prozedur ist iterativ, bis alle Datenpunkte unter einem einzigen großen Cluster zusammengefasst sind.

AGNES (AGglomerative NESting) ist eine Art von agglomerativem Clustering, bei dem die Datenobjekte auf der Basis von Ähnlichkeit zu einem Cluster zusammengefasst werden. Das Ergebnis dieses Algorithmus ist ein baumbasiertes strukturiertes Dendrogramm. Hier wird anhand der Distanzmetriken entschieden, welche Datenpunkte mit welchem ​​Cluster kombiniert werden sollen. Grundsätzlich erstellt es eine Distanzmatrix und sucht nach dem Paar von Clustern mit der geringsten Distanz und kombiniert sie.

Die obige Abbildung zeigt Agglomerative vs. Divisive Clustering

Basierend darauf, wie der Abstand zwischen den einzelnen Clustern gemessen wird, können 3 verschiedene Methoden verwendet werden

  • Einzelverbindung : Hierbei wird der kürzeste Abstand zwischen den beiden Punkten in jedem Cluster als Abstand zwischen den Clustern definiert.
  • Vollständige Verknüpfung : In diesem Fall wird der größte Abstand zwischen den Punkten in jedem Cluster als Abstand zwischen den Clustern betrachtet.
  • Durchschnittliche Verknüpfung: Hier wird der Durchschnitt zwischen jedem Punkt in einem Cluster zu jedem anderen Punkt im anderen Cluster berechnet.

Lassen Sie uns nun über die Stärken und Schwächen von AGNES sprechen. Dieser Algorithmus hat eine zeitliche Komplexität von mindestens O (n 2 ) und eignet sich daher nicht gut für die Skalierung. Ein weiterer großer Nachteil ist, dass alles, was getan wurde, niemals rückgängig gemacht werden kann, dh wenn wir einen Cluster in einem früheren Stadium von falsch gruppieren Der Algorithmus wird dann nicht in der Lage sein, das Ergebnis zu ändern / zu modifizieren. Aber dieser Algorithmus hat auch eine positive Seite, da viele kleinere Cluster gebildet werden. Er kann beim Entdeckungsprozess hilfreich sein und eine Objektreihenfolge erzeugen, die bei der Visualisierung sehr hilfreich ist.

Divisives Clustering (DIANA)

Diana steht im Grunde genommen für Divisive Analysis; Dies ist eine andere Art von hierarchischem Clustering, bei der im Grunde genommen das Prinzip des Top-Down-Ansatzes (Inverse von AGNES) angewendet wird, bei dem der Algorithmus mit der Bildung eines großen Clusters beginnt und den unähnlichsten Cluster rekursiv in zwei unterteilt. Alle ähnlichen Datenpunkte gehören zu ihren jeweiligen Clustern. Diese Divisionsalgorithmen führen zu sehr genauen Hierarchien als der agglomerative Ansatz, sind jedoch rechenintensiv.

Die obige Abbildung zeigt den schrittweisen Vorgang des Divisive Clustering

Mehrphasiges hierarchisches Clustering

Um die Qualität von Clustern zu verbessern, die durch die oben genannten hierarchischen Clustertechniken erzeugt werden, integrieren wir unsere hierarchischen Clustertechniken mit anderen Clustertechniken. Dies wird als mehrphasiges Clustering bezeichnet. Es gibt folgende verschiedene Arten von Mehrphasen-Clustern:

  • BIRCH (Balanced Iterative Reducing and Clustering unter Verwendung von Hierarchien)
  • ROCK (RObust Clustering mit Links)
  • CHAMÄLEON

1. Ausgewogenes iteratives Reduzieren und Clustering mithilfe von Hierarchien

Diese Methode wird hauptsächlich zum Clustering großer Mengen numerischer Daten verwendet, indem unser hierarchisches / Mikro-Clustering in der Anfangsphase und das Makro-Clustering / iterative Partitionieren in der späteren Phase integriert werden. Diese Methode hilft bei der Überwindung des Skalierbarkeitsproblems, mit dem wir in AGNES konfrontiert waren, und der Unfähigkeit, das, was zuvor getan wurde, rückgängig zu machen. BIRCH verwendet in seinem Algorithmus zwei wichtige Konzepte

ein. Clustering-Funktion (Hilft bei der Zusammenfassung des Clusters)

CF ist definiert als (n - Anzahl der Datenpunkte im Cluster, die lineare Summe von n Punkten, die quadratische Summe von n Punkten). Wenn Sie das Feature eines Clusters auf diese Weise speichern, vermeiden Sie, dass detaillierte Informationen darüber gespeichert werden, und CF ist für verschiedene Cluster von Natur aus additiv.

CF 1 + CF 2 = 1+ n 2, LS 1 + LS 2, SS 1 + SS 2 >

b. Clustering-Featurebaum (hilft bei der Darstellung eines Clusters als Hierarchie)

Der CF-Baum ist ein ausgeglichener Baum mit dem Verzweigungsfaktor B (maximale Anzahl von Kindern) und dem Schwellenwert T (maximale Anzahl von Unterclustern, die in Blattknoten gespeichert werden können).

Der Algorithmus arbeitet grundsätzlich in 2 Phasen; In Phase 1 wird die Datenbank durchsucht und ein speicherinterner CF-Baum erstellt. In Phase 2 wird der Cluster-Algorithmus verwendet, der beim Clustering der Blattknoten hilft, indem die Ausreißer entfernt werden (spärliche Cluster) und der Cluster mit maximaler Dichte gruppiert wird. Der einzige Nachteil dieses Algorithmus ist, dass er nur den numerischen Datentyp verarbeitet.

2. Robustes Clustering mithilfe von Links

Link ist definiert als die Anzahl der gemeinsamen Nachbarn zwischen zwei Objekten. Der ROCK-Algorithmus ist eine Art Clustering-Algorithmus, der dieses Konzept der Verknüpfung mit dem kategorialen Datensatz verwendet. Da wir wissen, dass die Algorithmen für die Entfernung gemessener Cluster keine qualitativ hochwertigen Cluster für den kategorialen Datensatz bereitstellen, werden bei ROCK auch die Nachbarschaften der Datenpunkte berücksichtigt, dh, wenn zwei Datenpunkte dieselbe Nachbarschaft aufweisen, handelt es sich um diese wahrscheinlich im selben Cluster gehören. Der Algorithmus erstellt im ersten Schritt einen spärlichen Graphen unter Berücksichtigung der Ähnlichkeitsmatrix mit dem Konzept der Nachbarschafts- und Ähnlichkeitsschwelle. Im zweiten Schritt wird die agglomerative hierarchische Clustering-Technik für das spärliche Diagramm verwendet.

3. Chamäleon

Diese Art des hierarchischen Clustering-Algorithmus verwendet das Konzept der dynamischen Modellierung. Fragen Sie sich, warum es dynamisch heißt? Es wird als dynamisch bezeichnet, da es die Fähigkeit besitzt, sich automatisch an die internen Cluster-Eigenschaften anzupassen, indem es die Cluster-Ähnlichkeit bewertet, dh wie gut die Datenpunkte innerhalb eines Clusters und in der Nähe von Clustern verbunden sind. Einer der Nachteile von Chamäleon besteht darin, dass die Verarbeitungskosten zu hoch sind (O (n 2 ) für n Objekte ist die Zeitkomplexität im ungünstigsten Fall).

Bildquelle - Google

Fazit

In diesem Artikel haben wir gelernt, was ein Cluster ist und was eine Clusteranalyse ist. Verschiedene Arten hierarchischer Clustering-Techniken haben ihre Vor- und Nachteile. Jede der besprochenen Techniken hat ihr eigenes Plus und Minus. Bevor wir mit einem Algorithmus fortfahren, müssen wir unsere Daten mit der richtigen explorativen Datenanalyse verstehen und den Algorithmus mit Vorsicht auswählen.

Empfohlene Artikel

Dies ist eine Anleitung zur hierarchischen Clusteranalyse. Hier diskutieren wir die Übersicht, das agglomerative Clustering, das divisive Clustering (DIANA) und das mehrphasige hierarchische Clustering. Weitere Informationen finden Sie auch in den folgenden Artikeln

  1. Hierarchisches Clustering in R
  2. Clustering-Algorithmus
  3. Cluster
  4. Clustering-Methoden
  5. Clustering im maschinellen Lernen
  6. Hierarchisches Clustering | Agglomeratives & Divisives Clustering

Kategorie:

Große Daten