DeepECT: Der Deep Embedded Cluster Tree

Wir bewerten unsere vorgeschlagene Methode DeepECT anhand von vier häufig verwendeten Deep-Learning-Datensätzen: MNIST, USPS, Fashion-MNIST und Reuters. Tabelle 1 zeigt die Statistiken aller in den Experimenten verwendeten Datensätze. MNIST und USPS sind beide Bilddatensätze, die handgeschriebene Ziffern enthalten. Der Datensatz Fashion-MNIST enthält Bilder von Modeprodukten, z. B. Bilder von Kleidung, Schuhen und Taschen. Der Reuters-Datensatz enthält Nachrichtenartikel in vier Hauptkategorien, und wir verwenden die gleiche Darstellung wie in beschrieben .

Versuchsaufbau

Wir konzentrieren unsere Experimente auf die Evaluierung unserer neuen Clusterschicht. Daher verzichten wir auf aufwändigere Autoencoder-Architekturen. Stattdessen verwenden wir für alle Experimente dasselbe generische, vollständig verbundene Autoencoder-Layout wie in . Wie bereits erwähnt, erwarten wir, dass alle Methoden gleichermaßen von anspruchsvolleren und domänenspezifischen Architekturen profitieren würden. Eine Standard-Autoencoder-Architektur reicht jedoch aus, um die Lebensfähigkeit von DeepECT im Vergleich zu den Basiskonkurrenten zu zeigen. Daher, Wir verwenden dieselbe generische Autoencoder-Architektur, wie in vorgeschlagen und auch zum Clustern des eingebetteten Raums verwendet. Der Vorwärtsgeber in dieser Architektur hat die Abmessungen d-500–500–2000–10 , und das Decodernetzwerk hat ein gespiegeltes Layout. Wir verwenden ReLU-Aktivierungen und den mittleren quadratischen Fehlerrekonstruktionsverlust aus Gl. (1).

Wir trainieren zehn Autoencoder für jeden Datensatz vor und verwenden dieselben vortrainierten Netzwerke für alle Experimente und Vergleichsmethoden. Die Verwendung dieser vortrainierten Autoencoder stellt sicher, dass jede Methode die gleichen Startbedingungen für den eingebetteten Raum hat und dass Variationen in der Clustering-Qualität nicht nur von qualitativ unterschiedlichen Autoencodern herrühren. Das Pre-Training-Setup ähnelt dem in . Wir trainieren die Autoencoder als rauschunterdrückende Autoencoder mit einer Korruptionsrate von 20% vor. Zuerst führen wir ein schichtweises Pre-Training mit Dropout nach jeder Schicht (mit einer Rate von 20%) und 20.000 Schritten pro Schicht durch. Dann optimieren wir das gesamte Netzwerk für 50.000 Schritte ohne Ausfall. Wir verwenden Eingabemethoden nur für das Pre-Training und nicht für die eigentliche Optimierung von DeepECT und seinen Baseline-Methoden. Für alle Experimente verwenden wir Adam () \({\hbox {)}}=0.0001\), \(\ beta _1=0,9, \beta _2=0,999\)) als Optimierungsalgorithmus und eine Mini-Batch-Größe von 256 Proben. Für die kombinierte Optimierung trainieren wir zusätzliche 50.000 Iterationen, um die Konvergenz sicherzustellen.

Für DeepECT zeigten unsere ersten Experimente mit synthetischen Daten, dass das Aufteilen des Baums alle 500 Optimierungsschritte vielversprechende Ergebnisse liefert und erweiterte Schrittgrößen die Leistung nicht weiter erhöhen. Aus diesem Grund halten wir diesen Zeitplan ein, ohne ihn für die Experimente an realen Datensätzen anzupassen. Gleiches gilt für die in Abs. 2.7. Für MNIST, Fashion-MNIST und USPS züchten wir die Bäume, bis sie zwanzig Blattknoten enthalten. Für den Reuters-Datensatz legen wir die maximale Anzahl von Blattknoten auf zwölf fest, da er weniger Ground-Truth-Cluster enthält. Auf diese Weise haben wir das Zwei- und Dreifache der tatsächlichen Anzahl von Clustern. Wir betrachten diese Werte als ausreichend, um wesentliche Strukturen der ausgewählten Datensätze für den Zweck dieses Papiers zu erfassen. Wir verwenden die gleiche Anzahl von Blattknoten für die hierarchischen Basismethoden.

Die Diagramme zeigen eine Stichprobe der ursprünglichen MNIST-Ziffern und eine zufällig erweiterte Version

Für die Bilddatensätze haben wir zusätzlich mit der Augmentationserweiterung DeepECT + Aug experimentiert. Wir beginnen mit den gleichen vortrainierten Autoencodern wie in den anderen Experimenten. Darüber hinaus halten wir uns an den gleichen Optimierungsplan wie oben für die Experimente mit den nicht erweiterten Versionen von DeepECT beschrieben. In jeder Iteration verwenden wir den ursprünglichen Mini-Batch und sein erweitertes Gegenstück, um die Verlustfunktion in Eq zu optimieren. 9, anstelle des nicht vergrößerten Verlustes in Gl. 6. Wir erstellen die erweiterte Version jedes Bildes eines Mini-Batches, indem wir im laufenden Betrieb eine zufällige affine Transformation anwenden. Die affine Transformation dreht und schert das Bild zufällig im Bereich von \ (\) Grad. Außerdem wird die Ziffer zufällig um bis zu zwei Pixel in eine beliebige Richtung verschoben. Abbildung 5 zeigt ein Beispiel für diese Augmentation für MNIST.

Bewertungsmethoden

Wir bewerten die Clusterhierarchie von DeepECT mit dem Dendrogrammreinheit (DP) und Blattreinheit (LP) messen. Wir beschreiben beide unten. Darüber hinaus bewerten wir den Clusterbaum anhand von Flat Baseline-Methoden. Dazu verwenden wir die bekannten Normalized Mutual Information (NMI) und Clustering Accuracy (ACC) . Wir fügen diese der Vollständigkeit halber hinzu und zeigen, dass DeepECT auch in Szenarien wettbewerbsfähig ist, in denen man eine flache Clusterstruktur erwartet und die tatsächliche Anzahl der Cluster im Datensatz kennt. Um eine k Clusterpartition aus einem Clusterbaum zu bestimmen, verwenden wir die Zuweisungen zu den k Knoten, die nach den ersten \(k-1\) Splits Blattknoten waren.

Dendrogramm-Reinheit

Das Dendrogramm-Reinheitsmaß kann verwendet werden, um den Clusterbaum gegen eine flache Grundwahrheitspartition zu bewerten. Es ist die erwartete Reinheit des Unterbaums, die vom Knoten mit dem kleinsten gemeinsamen Vorfahren für zwei zufällig abgetastete Datenpunkte derselben Klasse angegeben wird. Es ist 1.0 genau dann, wenn alle Datenpunkte, die zu einer Klasse in der Grundwahrheit gehören, einem reinen Unterbaum zugewiesen sind, und es nähert sich 0 für zufällig generierte Bäume.

Die explizite Formel ist definiert als:

wobei \(C_1, \dots, C_K\) die Datenpunktmengen sind, die den Ground Truth-Klassen entsprechen, \({\text {lca}}(x,y)\) der kleinste gemeinsame Ahnenknoten von x und y im Clusterbaum ist, \({\text {dan}}(z)\) die Menge von Datenpunkten ist, die dem Knoten z im Clusterbaum zugewiesen sind, \({\text {pur}}(S,T) = /S \/ T/ | | S/\) das Reinheitsmaß ist, und \({\mathcal {P}} = \{(x,y) \mid \exists C \in \{C_1, \dots , C_K\}: x,y \in C \wedge x \ne y\}\) ist die Menge aller Datenpunktpaare, die zur selben Klasse gehören. Die Reinheit des Dendrogramms kann effizient und genau in einer Bottom-up-Rekursion auf dem Clusterbaum berechnet werden.

Blattreinheit

Neben der Verwendung der Dendrogrammreinheit führen wir ein weiteres Maß ein, das wir Blattreinheit (LP) nennen. Es ist die gewichtete durchschnittliche Reinheit der Blattknoten w.r.t. zur Mehrheitsklasse der einem Blattknoten zugeordneten Objekte, gegeben durch die Formel:

wobei \({{\mathcal {L}}} _{{\mathcal {D}}}\) die Menge der Mengen ist, die die den Blattknoten zugewiesenen Datenpunkte enthalten.

Baumhöhenabhängigkeit der Reinheitsmaße

Der Vergleich von Dendrogramm und Blattreinheit zweier Clusterbäume ist nur direkt möglich, wenn beide Bäume die gleiche Anzahl von Blattknoten haben. Unterbäume können jedoch immer in Blattknoten reduziert werden, um diese Anforderung zu erfüllen. Daher reduzieren wir die Bottom-up-Verknüpfungsbäume der Baseline-Methoden — in der Reihenfolge der Verknüpfung —, indem wir Unterbäume in Blattknoten komprimieren, bis wir die gleiche Anzahl von Zusammenführungsschritten wie Split-Knoten in den Top-Down-Bäumen von DeepECT und Bisecting-K-means haben. Dieser Prozess stellt sicher, dass beide Methoden mit den hierarchischen Bewertungsmaßnahmen vergleichbar sind.

Hierarchische Clustering-Baselines

Als Basis für die Bewertung der hierarchischen Eigenschaften clustern wir die eingebetteten Daten mit den klassischen hierarchischen Clustering-Algorithmen bisecting-k-means (AE + Bisecting), single-linkage (AE + Single) und complete-Linkage (AE + Complete). Da keiner dieser klassischen Algorithmen den eingebetteten Raum optimieren kann, untersuchen wir auch die einfache Idee, den flachen eingebetteten Clustering-Algorithmus IDEC mit Einzelverknüpfung und vollständiger Verknüpfung zu kombinieren. IDEC ist eine Methode, die die Clusterschicht von DEC mit dem Rekonstruktionsverlust des Autoencoders kombiniert. Zuerst führen wir IDEC mit der Anzahl der Cluster auf einen höheren Wert als die erwartete Anzahl von Clustern aus — in unserem Fall setzen wir sie auf die maximale Anzahl von Blattknoten, die wir für DeepECT verwenden. Dann betrachten wir diese IDEC-Clusterzentren als Vertreter der zugewiesenen Datenpunkte und versuchen, eine hierarchische Clusterstruktur wiederherzustellen, indem wir eine Einzelverknüpfung und eine vollständige Verknüpfung für die Clusterzentren durchführen (IDEC + Single und IDEC + Complete). Eine ähnliche Technik wird für klassische, nicht eingebettete Einstellungen mit k-means anstelle von IDEC vorgeschlagen.

Flache Clustering-Baselines

Als Basis für die Bewertung der Leistung von DeepECT in einer flachen Clustering-Umgebung verwenden wir k-Means für die eingebetteten Daten des vortrainierten Autoencoders (AE +k-means) und IDEC . Wenn wir die Vorteile domänenspezifischerer und ausgefeilterer Autoencoder-Architekturen ignorieren, ist IDEC derzeit eine der besten Embedded-Clustering-Methoden. Im Gegensatz zu DeepECT müssen wir bei der Optimierung für IDEC und k-means die tatsächliche Anzahl der Cluster in der Ground Truth festlegen. Ferner setzen wir den Hyperparameter von IDEC für den Rekonstruktionsverlust auf 0,1, wie in beschrieben .

Allgemeine Ergebnisse

Die allgemeinen Ergebnisse—gemittelt über die zehn vortrainierten Autoencoder-für die hierarchische Auswertung mit Dendrogrammreinheit und Blattreinheit Maßnahmen für DeepECT und die hierarchischen Baseline—Algorithmen sind in Tabelle 2 gezeigt. DeepECT erzeugt konstant Clusterbäume von hoher Qualität und ist mit Abstand der leistungsfähigste Algorithmus. Wir können auch sehen, dass die Augmentationserweiterung die Ergebnisse für MNIST und USPS erheblich verbessert. Die Ergebnisse von DeepECT mit und ohne Augmentationserweiterung für den Fashion-MNIST-Datensatz sind ähnlich, da die Datensatzautoren alle Bilder so vorverarbeitet haben, dass jeder Modeartikel eine normalisierte Darstellung aufweist. Die Ergebnisse der klassischen Methoden können durch ihre Unfähigkeit erklärt werden, die Einbettung zu verbessern. Die Blattreinheitswerte für DeepECT zeigen, dass die Methode in der Lage ist, homogene Subpopulationen zu erzeugen. Wenn wir die Blattreinheitswerte von DeepECT und den hierarchischen IDEC + Center-Linkage-Varianten mit den Blattreinheitswerten der anderen Baselines vergleichen, können wir sehen, dass die kombinierte Optimierung von Clustering und Autoencoder — beider Methoden — tatsächlich die Homogenität lokaler Strukturen verbessert. Die IDEC + Center-Verknüpfung ist jedoch auch nicht in der Lage, eine kohärente hierarchische Struktur zu extrahieren.

Tabelle 3 zeigt die experimentellen Ergebnisse für die Flat-Clustering-Vergleichsmethoden, die auf denselben vortrainierten Autoencodern basieren. Da wir dieselben vortrainierten Autoencoder verwenden, können wir den Einfluss des jeweiligen Clustering-Ziels direkt erkennen. Sowohl IDEC als auch DeepECT profitieren von der kombinierten Optimierung im Vergleich zu k-means, die die Einbettung nicht optimieren können. Tabelle 4 zeigt die Ergebnisse von mehr Zentroid-basierten Clustering-Methoden aus der jeweiligen Veröffentlichung. Weitere Details zu diesen Methoden finden Sie in Abschnitt. 4. Wir können sehen, dass DeepECT auch im Vergleich zu diesen Methoden eine gute Leistung erbringt. Wir können jedoch auch sehen, dass die Autoencoder-Architektur das Clustering-Ergebnis erheblich beeinflusst. Zum Beispiel unterscheidet sich DBC von DEC nur durch die Verwendung eines Faltungsautoencoders, erzielt jedoch überlegene Ergebnisse. Die ausgewählte Autoencoder-Architektur ist jedoch unabhängig von der ausgewählten Clusterschicht.

Natürlich ist dieser Vergleich von flachen Clustering-Zielen und DeepECT gegenüber letzterem unfair, da die konkurrierenden Methoden bei der Optimierung die wahre Anzahl von Clustern erhalten, während wir bei DeepECT diese Informationen nur bei der Auswertung verwenden. Nichtsdestotrotz können wir sehen, dass die gewöhnliche Version von DeepECT mit diesen Methoden in Bezug auf rohe NMI- und ACC-Messungen mithalten kann und dass die Augmentationserweiterung DeepECT + Aug wesentliche Verbesserungen gegenüber den Ergebnissen von DeepECT zeigt, da sie bekannte Invarianzen innerhalb der Daten ignorieren kann. Diese Ergebnisse zeigen, dass DeepECT auch in Szenarien wettbewerbsfähig ist, in denen man eine flache Clusterstruktur erwartet, aber die Anzahl der Cluster nicht kennt und den Clusterbaum rekursiv inspiziert.

Detaillierte Auswertung

In diesem Abschnitt werfen wir einen genaueren Blick auf die resultierenden DeepECT-Bäume für die obigen Datensätze. Da die Ergebnisse des USPS-Datensatzes mit denen von MNIST vergleichbar sind — da beide handgeschriebene Ziffern darstellen – lassen wir diese Ergebnisse der Kürze halber weg.

MNIST-Ergebnisse

Ein genauerer Blick auf die resultierenden Schnittbäume für den MNIST-Datensatz zeigt einige aufregende Eigenschaften verschiedener Subpopulationen innerhalb der handgeschriebenen Ziffern. Zwei Ausführungsbeispiele sind in Fig. 6 und kann in der gewöhnlichen und erweiterten Erweiterung von DeepECT gefunden werden. Die Knotenreinheit der dargestellten Teilbäume für die Ziffer 7′ beträgt 98% und enthält fast alle Instanzen dieser Klasse. Es enthält zwei Blattknoten. Ein Blattknoten zeigt Siebener mit einer kleinen Querstange, wie es in Europa üblich ist, der andere Blattknoten zeigt diese Ziffer, wie es in den USA häufiger geschrieben wird. Der zweite Teilbaum enthält fast alle Instanzen der Ziffer ‘2’ mit einer Reinheit von 97%. Dieser Unterbaum enthält auch zwei Blattknoten mit jeweils spezifischen Merkmalen. Der erste Blattknoten enthält Instanzen, die lockiger sind und im unteren Teil eine markante Schleife aufweisen. Der zweite Blattknoten enthält eine schlankere Version dieser Ziffer, die wie das Zeichen ‘Z’ aussieht. Die gezeigten Teilbäume bilden eine natürliche Hierarchie für die jeweilige Ziffer, und man kann sich leicht vorstellen, dass diese Ergebnisse für einen Forscher von Interesse sein können. Andere formabhängige Zifferngruppen finden sich auch in den unteren Teilen des Baums, zum Beispiel, Die schriftlichen Versionen der Ziffern ‘4’ und ‘9’ haben viele Eigenschaften. Folglich können sie oft als Unterbaum gruppiert gefunden werden, der nur diese beiden Zifferntypen enthält.

Die Diagramme zeigen zwei extrahierte Teilbäume aus interessanten Subpopulationen des MNIST-Datensatzes, die von DeepECT gefunden wurden. Dies sind die Ziffern sieben (mit und ohne mittlere Querstange) und zwei (eine lockige und eine ‘stromlinienförmige’ Version, die eher dem Zeichen ‘Z’ ähnelt). Die angezeigten Ziffern werden zufällig abgetastet

Reuters-Ergebnisse

Der Reuters-Datensatz enthält vier unausgewogene Top-Kategorien (First-Level-Labels) mit der folgenden Klassenverteilung: Industrie / Industrie mit 44%, Regierung / Soziales mit 24%, Märkte mit 24% und Wirtschaft mit 8%. Dieser Datensatz wird in ausführlicher erläutert . Die Kategorien für jeden Nachrichtenartikel wurden von Hand ausgewählt und sind daher in gewissem Maße subjektiv. Darüber hinaus hat jede Top-Kategorie mehrere zusätzliche überlappende Unterkategorien (Second-Level—Labels) – und Unter-Unterkategorien (Third-Level—Labels) – mit über 96% der Artikel, die zu zwei oder mehr Unterkategorien gehören. Tabelle 5 zeigt ein DeepECT-Ergebnis für diesen Datensatz. Wir können sehen, dass die ersten beiden Splits den größten Teil des Government / Social—Unterbaums ab Knoten 3 – und Markets—Unterbaums ab Knoten 5—Kategorien von den anderen beiden Kategorien trennen. Der Teilbaum Regierung/ Soziales differenziert sich dann weiter in Themen der Unterkategorien wie Sport, Krieg und Kriminalität, Innen- und Außenpolitik. Die Kategorie Märkte unterscheidet auch weiter in verschiedene Aspekte der jeweiligen Unterkategorien. Zum Beispiel betreffen die Blattknoten in den letzten beiden Zeilen verschiedene Unterkategorien der Unterkategorie Rohstoffmärkte. Die Blattknoten in der Mitte beziehen sich hauptsächlich auf Unternehmen / Industrie und Wirtschaft. Sie sind nicht so gut getrennt wie die anderen beiden Teilbäume. Doch auch dort können wir interessante Blattknoten finden. Zum Beispiel teilt der siebte Blattknoten (Zeile) von oben Nachrichtenartikel, die mit den Unterkategorien Leistung (von Unternehmen / Industrie) und Wirtschaftsleistung (von Wirtschaft) gekennzeichnet sind, und es scheint vernünftig, verwandte Wörter für diese beiden Unterkategorien zu erwarten -Unterkategorien.

Mode-MNIST Ergebnisse

Das Diagramm zeigt einen Clusterbaum für das Fashion-MNIST-Dataset. Jeder Blattknoten zeigt zufällig abgetastete Objekte an, die ihm zugewiesen sind. Die Etiketten sind Interpretationen der Autoren. Die farbigen Bereiche markieren die drei dominanten Teilbäume, die drei Arten von Objekten im Datensatz darstellen: Taschen, Kleidung und Schuhe

Der Mode-MNIST enthält zehn verschiedene Klassen von Kleidung, Schuhen und Taschen, nämlich T-Shirt / Top, Hose, Pullover, Kleid, Mantel, Sandale, Hemd, Sneaker, Tasche und Stiefelette. Ein resultierender Clusterbaum unseres Verfahrens ist in Abb. 7. Die Blattknoten werden als zufällig abgetastete Objekte dargestellt, die ihm zugewiesen sind. Die Beschriftungen jedes Knotens sind unsere Interpretation basierend auf den Objekten, die dem jeweiligen Knoten zugewiesen sind. Wir können sehen, dass DeepECT innerhalb dieses Datensatzes eine völlig natürlich aussehende Hierarchie gefunden hat. Zunächst werden die Bilder in drei Kategorien unterteilt: Kleidung, Schuhe und Taschen. Wir haben diese Unterbäume mit farbigen Bereichen hervorgehoben. Innerhalb jedes Unterbaums finden wir natürliche Hierarchien. Die Kategorie der Taschen unterscheidet zwischen Taschen ohne sichtbaren Gurt / Griff, Taschen mit kleinen Griffen und Taschen mit Schultergurt. Die Grundwahrheit unterscheidet nicht zwischen diesen Arten von Taschen und ordnet sie alle derselben Klasse zu. Die Kategorie Kleidung wird zunächst in Hosen und Kleidung für den Oberkörper unterteilt. Diese sind dann wieder in kurze und lange Ärmel unterteilt. Hier muss die Länge des Ärmels relativ zur Gesamtlänge des jeweiligen Kleidungsstücks gesehen werden, da jedes Element normalisiert ist, um innerhalb des Bildes von der gleichen Größe zu erscheinen, d.h., Kleider und Hemden scheinen von der gleichen Größe zu sein. Die Schuhkategorie zeigt auch einige interessante Eigenschaften. Zunächst werden kleinere und größere Schuhe unterschieden. Die kleineren Schuhe werden dann weiter in Sandalen und Turnschuhe unterteilt. Die größeren Schuhe haben entweder eine flache Sohle, einen kleinen Absatz oder sind hochhackig. Der Aufbau der Hierarchie basierend auf diesen Merkmalen läuft den Ground Truth-Klassen von Sneakers, Sandalen und Stiefeletten entgegen. Dennoch ist es – aus Sicht des Aussehens – eine gültige und informative Hierarchie für Schuhe.

Anwendbarkeit für Vorhersageaufgaben auf MNIST

Wir bewerten DeepECT auch in einer Vorhersageaufgabe. Dabei behalten wir die Autoencoder und das Clustering-Optimierungsverfahren wie oben beschrieben bei. Im Gegensatz zur obigen experimentellen Auswertung verwenden wir bei der Clusterbaumoptimierung nur die ersten 50.000 Samples (Trainingssatz) des Datensatzes MNIST. Nach der Optimierung bewerten wir die Clusterleistung des Clusterbaums auf den bisher nicht sichtbaren, verbleibenden 20.000 Datenpunkten (Testsatz).

In diesem Experiment erhalten wir für den Testsatz eine Dendrogrammreinheit von \(0.73\pm 0,08\) und einer Blattreinheit von \(0,85\pm 0,06\), was ein leichter Abfall gegenüber den Werten in Tabelle 2 ist. Nichtsdestotrotz ist das Ergebnis robust genug, um begrenzte Label-Vorhersagen von zuvor nicht gesehenen Datenpunkten direkt durch den Clusterbaum zu ermöglichen. In den meisten Fällen würden wir jedoch einen Klassifikator basierend auf den gefundenen Clusterstrukturen trainieren. Gleiches gilt für die Einbettung selbst, wo wir beispielsweise den überwachten Autoencoder-Verlust verwenden können, um die gefundene Einbettung zu verbessern.

Zusammenfassung der Experimente

Zusammenfassend sind wir der Meinung, dass die gezeigten Experimente an vier realen Datensätzen den Nutzen und die Effektivität des DeepECT-Clusterbaums deutlich zeigen. Das Auffinden solcher Strukturen und die Auswahl des zu analysierenden Detaillierungsgrades machen DeepECT zu einer wertvollen Methode für Data Scientists.