Gibt es einen entscheidungsbaumartigen Algorithmus für unbeaufsichtigtes Clustering?

20

Ich habe einen Datensatz, der aus 5 Merkmalen besteht: A, B, C, D, E. Sie sind alle numerische Werte. Anstatt ein dichtebasiertes Clustering durchzuführen, möchte ich die Daten auf eine entscheidungsbaumartige Weise gruppieren.

Der Ansatz, den ich meine, ist ungefähr so:

Der Algorithmus kann die Daten basierend auf Merkmal C in X anfängliche Cluster aufteilen, dh die X-Cluster können kleine C-, mittlere C-, große C- und sehr große C-Werte usw. aufweisen. Als nächstes unterteilt der Algorithmus unter jedem der X-Cluster-Knoten weiter Die Daten werden basierend auf Merkmal A in Y-Cluster aufgeteilt. Der Algorithmus wird fortgesetzt, bis alle Merkmale verwendet wurden.

Der Algorithmus, den ich oben beschrieben habe, ist wie ein Entscheidungsbaumalgorithmus. Aber ich brauche es für unbeaufsichtigtes Clustering anstatt für überwachte Klassifizierung.

Meine Fragen sind folgende:

  1. Gibt es solche Algorithmen schon? Was ist der richtige Name für einen solchen Algorithmus
  2. Gibt es ein R / Python-Paket / eine Bibliothek, in der diese Art von Algorithmen implementiert sind?
nan
quelle
3
But I need it for unsupervised clustering, instead of supervised classificationDieser Schlüsselbegriff ist zu kurz und erklärt nicht klar, was Sie wollen. Darüber haben Sie beschrieben, was mir als Entscheidungsbaum erscheint. Können Sie jetzt eine ähnliche Passage über die von Ihnen gewünschte Algo geben?
TTNPHNS
1
@ttnphns Hallo, wie Sie wissen, ist der Entscheidungsbaum eine überwachte Methode. Sie bezeichnen jeden Merkmalsvektor als Klasse1 oder Klasse2. Der Algorithmus bestimmt den Schwellenwert für jedes Merkmal basierend auf den bekannten Bezeichnungen. Ich stehe jedoch vor einem Clustering-Problem. Ich kenne nicht die korrekten Bezeichnungen der einzelnen Merkmalsvektoren. Ich möchte einen Algorithmus finden, der automatisch den Schwellenwert für jedes Feature ermittelt, um einen Baum zu erstellen. Auf diese Weise kann das resultierende Clustering leicht wie zB Cluster 1 interpretiert werden: High A-Low B- Medium C- Hoch D - Low E, Cluster 2 als Low A - Hohe B- Medium C- Medium D - Low E.
nan
Verstehe dich nicht ganz gut Nehmen wir CHAIDzum Beispiel den Baum. Sie müssen die abhängige Variable auswählen. Sei es A. Der Algorithmus wählt unter B, C, D, E die Variable aus, die am meisten mit A korreliert, und teilt diese Variable (sagen wir, es ist der Prädiktor, sei D) in zwei oder mehr Kategorien "optimal" ein - damit die Korrelation (Zwischen der kategorisierten Variablen D und der Variablen A wird die Maximierung erreicht. Angenommen, es bleiben 3 Gruppen übrig, D1, D2, D3. Anschließend wird das gleiche Verfahren in jeder Kategorie (Gruppe) von D separat und dem besten Prädiktor unter B, C wiederholt , E ist unter Binning es usw. gesucht. Was genau passt nicht zu Ihnen hier?
TTNPHNS
2
@ttnphns Ich habe gerade dieses Papier gefunden, ich glaube, sie haben das getan, was ich meine. ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/...
nan
1
@nan hast du irgendeine umsetzung solcher bäume gefunden? Sie bieten keinen Link zum Code im Artikel
Alleo

Antworten:

12

Möglicherweise möchten Sie den folgenden Ansatz in Betracht ziehen:

  • Verwenden Sie einen beliebigen Clustering-Algorithmus, der für Ihre Daten geeignet ist
  • Angenommen, der resultierende Cluster besteht aus Klassen
  • Trainiere einen Entscheidungsbaum auf den Clustern

Auf diese Weise können Sie verschiedene Clustering-Algorithmen ausprobieren, aber Sie erhalten für jede eine Entscheidungsbaumannäherung.

Anony-Mousse
quelle
1
stimmen zu, dass dies "angemessen" ist, aber man muss natürlich immer bedenken, dass das Erstellen eines Etiketts aus einem Clustering-Algorithmus kein "tatsächliches" Merkmal einer Beobachtung ist. Abhängig von der Qualität und Art der Clusterbildung wird die eingeführte Verzerrung mehr oder weniger stark bestehen.
NiuBiBang
Können Sie mich auf ein Papier verweisen, in dem diese Strategie erörtert wird?
nCessity
2

Das erste Papier, das mir in den Sinn kommt, ist das folgende: Clustering über Entscheidungsbaumkonstruktion https://pdfs.semanticscholar.org/8996/148e8f0b34308e2d22f78ff89bf1f038d1d6.pdf

Wie bereits erwähnt, sind sowohl "hierarchische" (von oben nach unten) als auch "hierarchische Agglomeration" (von unten nach oben) bekannte Techniken, die unter Verwendung von Bäumen zur Clusterbildung entwickelt wurden. Scipy hat das.

Wenn Sie mit benutzerdefiniertem Code zufrieden sind, weil ich keine Bibliothek kenne, kann ich zwei Techniken empfehlen. Seien Sie gewarnt, dass diese aufgrund der Mechanik, auf die sie angewiesen sind, technisch gesehen keine Cluster bilden. Sie könnten dieses Pseudo-Clustering nennen.

1) Betreut: Dies ist dem Artikel etwas ähnlich (lesenswert). Erstellen Sie ein einzelnes Entscheidungsbaummodell, um ein bestimmtes Ziel zu lernen (Sie entscheiden, was Sinn macht). Das Ziel kann eine zufällig generierte Spalte sein (es muss wiederholt und bewertet werden, welche Iteration die beste ist, siehe unten). Definieren Sie jeden vollständigen Pfad des Baums als "Cluster", da Punkte, die durch diese Reihe von Zweigen fallen, in Bezug auf das Ziel technisch ähnlich sind. Dies funktioniert nur bei einigen Problemen, ist jedoch im großen Maßstab effizient. Sie erhalten K Cluster (siehe unten).

2) Halbüberwacht (irgendwie unbeaufsichtigt, aber mechanisch überwacht), unter Verwendung von # 1: Sie können versuchen, Bäume zu bauen, um Spalten in einem Auslassungsmuster vorherzusagen. dh wenn das Schema [A, B, C] ist, erstellen Sie 3 Modelle [A, B] -> C, [A, C] -> B, [B, C] -> A. Sie erhalten KN-Cluster (siehe unten). N = len (Schema). Wenn einige dieser Funktionen (bei Kategorien) nicht interessant oder zu unausgewogen sind, sollten Sie sie nicht als Ziele verwenden.

Zusammenfassung: Das Modell wählt die Merkmale in der Reihenfolge nach Informationen oder Reinheit aus, und die Cluster basieren nicht auf allen, sondern nur auf wenigen Merkmalen. In diesen Clustern gibt es kein Konzept für die Entfernung, aber Sie könnten sicherlich eines basierend auf den Zentren entwickeln.

Vorteile: Einfach zu verstehen und zu erklären, schnelles Training und Inferenz, funktioniert gut mit wenigen starken Funktionen, funktioniert mit Kategorien. Wenn Ihre Funktionen im Wesentlichen heterogen sind und Sie viele Funktionen haben, müssen Sie nicht so viel Zeit darauf verwenden, zu entscheiden, welche Funktionen für die Distanzfunktion verwendet werden sollen.

Nachteile: nicht Standard, muss geschrieben werden, naive Vorurteile, Kollinearität mit dem Ziel führt zu schlechten Ergebnissen, wenn 1000 gleich wichtige Merkmale nicht gut funktionieren (KMeans mit euklidischem Abstand sind hier besser).

Wie viele Cluster bekommen Sie? Sie müssen das DT-Modell unbedingt so einschränken, dass es nicht zu stark wächst. zB Stellen Sie minimale Proben pro Blatt, maximale Blattknoten (bevorzugt) oder maximale Tiefe ein. Optional können Sie Reinheits- oder Entropiebeschränkungen festlegen. Sie müssen überprüfen, wie viele Cluster Sie erhalten haben, und bewerten, ob diese Methode besser ist als reales Clustering.

Haben die Techniken und Parameter bei Ihnen gut funktioniert? Welches war das Beste? Um dies herauszufinden, müssen Sie eine Cluster-Evaluierung durchführen: Leistungsmetriken, um unbeaufsichtigtes Lernen zu evaluieren

ldmtwo
quelle
2

Was Sie suchen, ist ein divisiver Clustering-Algorithmus.

Die meisten gängigen Algorithmen sind agglomerativ und gruppieren die Daten von unten nach oben. Jede Beobachtung beginnt mit einem eigenen Cluster und Cluster werden zusammengeführt. Divisives Clustering erfolgt von oben nach unten - die Beobachtungen beginnen in einem Cluster, der nach und nach geteilt wird.

Der Wunsch, wie ein Entscheidungsbaum auszusehen, schränkt die Auswahl ein, da die meisten Algorithmen Entfernungen innerhalb des gesamten Datenraums verarbeiten, anstatt jeweils eine Variable aufzuteilen.

DIANA ist der einzige Algorithmus, den ich kenne, und ich denke, er ist wie ein Entscheidungsbaum aufgebaut. Ich würde mich wundern, wenn es da draußen keine anderen gibt.

Sie können einen Standard-Entscheidungsbaumalgorithmus verwenden, wenn Sie die Aufteilungsregel in eine Metrik ändern, die keine definierte abhängige Variable berücksichtigt, sondern eine Clustergütemetrik verwendet.

KirkD_CO
quelle
0

Angenommen, Sie haben k Merkmale und n Punkte. Sie können Zufallsbäume mit (k-1) -Feature und 1 -Feature als abhängige Variable erstellen. Y. Sie können eine Höhe h auswählen, nach der Sie Datenpunkte in Wurzeln haben. Sie können verschiedene Bäume abstimmen. Nur ein Gedanke.

Ankit Swarnkar
quelle