DeepECT: The Deep Embedded Cluster Tree

Valutiamo il nostro metodo proposto DeepECT su quattro set di dati di deep learning comunemente usati: MNIST, USPS, Fashion-MNIST e Reuters. La tabella 1 mostra le statistiche di tutti i set di dati utilizzati negli esperimenti. MNIST e USPS sono entrambi dataset di immagini contenenti cifre scritte a mano. Il set di dati Fashion-MNIST contiene immagini di prodotti di moda, come immagini di abbigliamento, scarpe e borse. Il set di dati Reuters contiene articoli di notizie in quattro categorie principali e utilizziamo la stessa rappresentazione descritta in .

Configurazione sperimentale

Concentriamo i nostri esperimenti sulla valutazione del nostro nuovo livello di clustering. Pertanto, ci asteniamo dall’utilizzare architetture di autoencoder più elaborate. Invece, usiamo lo stesso layout autoencoder completamente connesso generico per tutti gli esperimenti, come usato in . Come accennato in precedenza, ci aspettiamo che tutti i metodi otterrebbero ugualmente da architetture più sofisticate e specifiche del dominio. Tuttavia, un’architettura autoencoder standard è sufficiente per mostrare la fattibilità di DeepECT rispetto ai concorrenti di base. Quindi, usiamo la stessa architettura autoencoder generica, come proposto in e che viene anche utilizzata allo scopo di raggruppare lo spazio incorporato. L’encoder feedforward in questa architettura ha le dimensioni d-500–500–2000–10, e la rete di decodificatore ha un layout speculare. Usiamo attivazioni ReLU e la perdita di ricostruzione dell’errore quadrato medio da Eq. (1).

Pre-addestriamo dieci autoencoders per ogni set di dati e usiamo queste stesse reti pre-addestrate per tutti gli esperimenti e metodi di confronto. L’utilizzo di questi autoencoder pre-addestrati garantisce che ogni metodo abbia le stesse condizioni di partenza per lo spazio incorporato e che le variazioni nella qualità del clustering non derivino semplicemente da autoencoder qualitativamente diversi. La configurazione pre-allenamento è simile a quella descritta in . Pre-addestriamo gli autoencoders come denoising autoencoders con un tasso di corruzione del 20%. In primo luogo, eseguiamo un pre-allenamento a livello con dropout dopo ogni livello (con un tasso del 20%) e 20.000 passi per strato. Quindi, mettiamo a punto l’intera rete per 50.000 passaggi senza abbandono. Utilizziamo la corruzione degli input solo per il pre-training e non per l’ottimizzazione effettiva di DeepECT e dei suoi metodi di base. Per tutti gli esperimenti, usiamo Adam (learning \ ({\hbox {rate}}=0.0001\), \(\beta _1 = 0.9, \ beta _2=0.999\)) come algoritmo di ottimizzazione e una dimensione mini-batch di 256 campioni. Per l’ottimizzazione combinata, ci alleniamo per ulteriori 50.000 iterazioni per garantire la convergenza.

Per DeepECT, i nostri esperimenti iniziali con dati sintetici hanno mostrato che suddividere l’albero ogni 500 passaggi di ottimizzazione produce risultati promettenti e dimensioni dei passaggi più estese non hanno ulteriormente aumentato le prestazioni. Per questo motivo, manteniamo questo programma senza adattarlo per gli esperimenti sui set di dati del mondo reale. Lo stesso vale per la soglia di potatura menzionata nella sez. 2.7. Per MNIST, Fashion-MNIST e USPS, coltiviamo gli alberi fino a quando non contengono venti nodi fogliari. Per il set di dati Reuters, impostiamo il numero massimo di nodi foglia a dodici perché ha meno cluster di verità di terra. In questo modo, abbiamo due volte e tre volte il numero effettivo di cluster. Consideriamo questi valori sufficienti per catturare le strutture essenziali dei set di dati selezionati ai fini di questo documento. Usiamo lo stesso numero di nodi foglia per i metodi di base gerarchici.

Le trame mostrano un campione di cifre MNIST originali e una versione aumentata in modo casuale

Per i set di dati dell’immagine, abbiamo inoltre sperimentato l’estensione di aumento DeepECT + Aug. Iniziamo con gli stessi autoencoders pre-addestrati come negli altri esperimenti. Inoltre, ci atteniamo allo stesso programma di ottimizzazione descritto sopra per gli esperimenti con le versioni non aumentate di DeepECT. In ogni iterazione, usiamo il mini-batch originale e la sua controparte aumentata per ottimizzare la funzione di perdita in Eq. 9, invece della perdita non aumentata in Eq. 6. Creiamo la versione aumentata di ogni immagine di un mini-batch, applicando al volo una trasformazione affine casuale. La trasformazione affine ruota casualmente e taglia l’immagine nell’intervallo di gradi \ ( \ ). Inoltre, sposta la cifra in modo casuale fino a due pixel in qualsiasi direzione. Figura 5 mostra un esempio di questo aumento per MNIST.

Metodi di valutazione

Valutiamo la gerarchia dei cluster di DeepECT con la misura dendrogram purity (DP) e leaf purity (LP). Descriviamo entrambi di seguito. Inoltre, valutiamo l’albero del cluster rispetto ai metodi di base piatti. Per questo, usiamo il ben noto normalized Mutual information (NMI) e clustering accuracy (ACC). Includiamo questi per completezza e per dimostrare che DeepECT è anche competitivo negli scenari, in cui ci si aspetta una struttura cluster piatta e conosce il numero effettivo di cluster nel set di dati. Per determinare una partizione k cluster da un albero di cluster, usiamo le assegnazioni ai nodi k che erano nodi foglia dopo la prima divisione \(k-1\).

Purezza del dendrogramma

La misura di purezza del dendrogramma può essere utilizzata per valutare l’albero del cluster rispetto a una partizione di verità piana. È la purezza prevista del sottoalbero data dal nodo antenato meno comune per due punti dati campionati casualmente della stessa classe. È 1.0 se e solo se tutti i punti dati appartenenti a una classe nella verità di terra sono assegnati a un sottoalbero puro e si avvicina a 0 per gli alberi generati casualmente.

La formula esplicita è definita in as:

dove \(C_1, \dots , C_K\) sono i dati del punto di imposta corrispondente a terra la verità classi, \({\text {lca}}(x,y)\) è il minimo comune antenato nodo di x e y in cluster-tree, \({\text {dan}}(z)\) è l’insieme di punti dati assegnati al nodo z in cluster-tree, \({\text {pur}}(S,T) = |S \cap T| / | S|\) è la purezza misura, e \({\mathcal {P}} = \{(x,y) \mid \esiste C \in \{C_1,\ dots , C_K\}: x,y \in C \wedge x\ ne y\}\) è l’insieme di tutte le coppie di punti dati che appartengono alla stessa classe. La purezza del dendrogramma può essere calcolata in modo efficiente e preciso in una ricorsione bottom-up sull’albero del cluster.

Leaf Purity

Oltre a utilizzare la purezza del dendrogramma, introduciamo un’altra misura che chiamiamo leaf purity (LP). È la purezza media ponderata dei nodi foglia w.r. t. alla classe di maggioranza degli oggetti assegnati a un nodo foglia, data dalla formula:

dove \({{\mathcal {L}}} _{{\mathcal {D}}}\) è l’insieme di insiemi contenenti i dati dei punti assegnati ai nodi foglia.

L’altezza degli alberi Dipende dalle misure di purezza

Confrontare il dendrogramma e la purezza delle foglie di due alberi cluster è possibile solo se entrambi gli alberi hanno lo stesso numero di nodi fogliari. Tuttavia, i sottoalberi possono sempre essere compressi in nodi foglia per soddisfare questo requisito. Pertanto, comprimiamo gli alberi di collegamento bottom-up dei metodi di base-nell’ordine del collegamento-comprimendo sottoalberi in nodi foglia fino a quando non abbiamo lo stesso numero di passaggi di unione rimasti come nodi divisi negli alberi top-down di DeepECT e Bisecting-K-means. Questo processo assicura che entrambi i metodi sono comparabili w. r. t.le misure di valutazione gerarchica.

Linee di base del clustering gerarchico

Come linea di base per la valutazione delle proprietà gerarchiche, raggruppiamo i dati incorporati con i classici algoritmi di clustering gerarchico bisecting-k-means (AE + Bisecting), single-linkage (AE + Single) e complete-linkage (AE + Complete). Poiché nessuno di questi algoritmi classici può ottimizzare lo spazio incorporato, esploriamo anche la semplice idea di combinare l’algoritmo di clustering integrato piatto IDEC con single-linkage e complete-linkage. IDEC è un metodo che combina lo strato di clustering di DEC con la perdita di ricostruzione dell’autoencoder. Innanzitutto, eseguiamo IDEC con il numero di cluster impostato su un valore superiore al numero previsto di cluster—nel nostro caso, lo impostiamo uguale al numero massimo di nodi foglia che usiamo per DeepECT. Quindi, consideriamo questi centri cluster IDEC come rappresentanti dei punti dati assegnati e cerchiamo di recuperare una struttura gerarchica di clustering eseguendo single-linkage e complete-linkage sui centri cluster (IDEC + Single e IDEC + Complete). Una tecnica simile è proposta per le impostazioni classiche e non incorporate con k-means invece di IDEC.

Baseline di clustering Flat

Come linea di base per valutare le prestazioni di DeepECT in un’impostazione di clustering flat, utilizziamo k-means sui dati incorporati dell’autoencoder pre-addestrato (AE+k-means) e IDEC . Se ignoriamo i vantaggi di architetture di autoencoder più specifiche e sofisticate, IDEC è attualmente uno dei migliori metodi di clustering embedded. In contrasto con DeepECT, dobbiamo impostare il numero effettivo di cluster nella verità di terra durante l’ottimizzazione per IDEC e k-means. Inoltre, abbiamo impostato l’iperparametro di IDEC per la perdita di ricostruzione a 0.1 come descritto in .

Risultati generali

I risultati generali—mediati sui dieci autoincoders pre-addestrati—per la valutazione gerarchica utilizzando le misure di purezza del dendrogramma e della purezza delle foglie per DeepECT e gli algoritmi gerarchici di base sono mostrati nella Tabella 2. DeepECT produce costantemente alberi di cluster di alta qualità ed è l’algoritmo più performante con un ampio margine. Possiamo anche vedere che l’estensione di aumento migliora ulteriormente i risultati considerevolmente per MNIST e USPS. I risultati di DeepECT con e senza l’estensione augmentation per il set di dati Fashion-MNIST sono simili perché gli autori del set di dati hanno scelto di pre-elaborare tutte le immagini in modo tale che ogni elemento di moda abbia una rappresentazione normalizzata. I risultati dei metodi classici possono essere spiegati dalla loro incapacità di migliorare l’incorporamento. I valori di purezza delle foglie per DeepECT indicano che il metodo è in grado di creare sottopopolazioni omogenee. Se confrontiamo i valori di purezza delle foglie di DeepECT e le varianti gerarchiche IDEC + Center-linkage con i valori di purezza delle foglie delle altre linee di base, possiamo vedere che l’ottimizzazione combinata del clustering e dell’autoencoder—di entrambi i metodi—migliora effettivamente l’omogeneità delle strutture locali. Tuttavia, il collegamento centrale IDEC + non è in grado di estrarre una struttura gerarchica coerente.

La tabella 3 mostra i risultati sperimentali per i metodi di confronto del clustering piatto basati sugli stessi autoencoders pre-addestrati. Poiché utilizziamo gli stessi autoincoder pre-addestrati, possiamo vedere direttamente l’influenza del rispettivo obiettivo di clustering. Sia IDEC che DeepECT beneficiano dell’ottimizzazione combinata rispetto a k-means, che non può ottimizzare l’incorporamento. La tabella 4 mostra i risultati di più metodi di clustering basati su centroidi presi dalla rispettiva pubblicazione. Maggiori dettagli su questi metodi possono essere trovati in Sez. 4. Possiamo vedere che DeepECT funziona anche bene rispetto a questi metodi. Tuttavia, possiamo anche vedere che l’architettura autoencoder influenza notevolmente il risultato del clustering. Ad esempio, DBC differisce da DEC solo dall’uso di un autoencoder convoluzionale ma raggiunge risultati superiori. Tuttavia, l’architettura autoencoder selezionata è indipendente dal livello di clustering selezionato.

Naturalmente, questo confronto tra obiettivi di clustering flat e DeepECT è ingiusto nei confronti di quest’ultimo, perché ai metodi concorrenti viene dato il vero numero di cluster durante l’ottimizzazione, mentre per DeepECT, utilizziamo queste informazioni solo durante la valutazione. Tuttavia, possiamo vedere che la versione ordinaria di DeepECT può tenere il passo con questi metodi in termini di misure NMI e ACC grezzi e che l’estensione di aumento DeepECT + Aug mostra miglioramenti sostanziali rispetto ai risultati di DeepECT, perché può ignorare le invarianze note all’interno dei dati. Questi risultati mostrano che DeepECT è competitivo anche negli scenari, in cui ci si aspetta una struttura di cluster piatta, ma non conosce il numero di cluster e ispeziona l’albero dei cluster in modo ricorsivo.

Valutazione dettagliata

In questa sezione, diamo uno sguardo più da vicino ai DeepECT-trees risultanti per i set di dati di cui sopra. Poiché i risultati del set di dati USPS sono paragonabili a quelli di MNIST—poiché entrambi rappresentano cifre scritte a mano—omettiamo questi risultati per brevità.

Risultati MNIST

Uno sguardo più attento ai DeepECT-trees risultanti per il set di dati MNIST mostra alcune proprietà interessanti di diverse sottopopolazioni all’interno delle cifre scritte a mano. Due esempi illustrativi sono mostrati in Fig. 6 e può essere trovato nell’estensione ordinaria e aumentata di DeepECT. La purezza del nodo dei sottoalberi raffigurati per la cifra 7 ‘ è del 98% e contiene quasi tutte le istanze di questa classe. Contiene due nodi fogliari. Un nodo foglia mostra sette con una piccola traversa come è comunemente scritto in Europa, l’altro nodo foglia mostra questa cifra come è più comunemente scritto negli Stati Uniti. Il secondo sotto-albero contiene quasi tutte le istanze della cifra ‘ 2 ‘ con una purezza del 97%. Questo sottoalbero contiene anche due nodi fogliari, ciascuno con caratteristiche specifiche. Il primo nodo foglia contiene istanze che sono più ricci e hanno un ciclo distintivo nella parte inferiore. Il secondo nodo foglia contiene una versione più “snella” di questa cifra, simile al carattere “Z”. I sotto-alberi mostrati costruiscono una gerarchia naturale per la rispettiva cifra, e si può facilmente immaginare che questi risultati possano essere di interesse per un ricercatore. Altri raggruppamenti di cifre a seconda della forma possono essere trovati anche nelle parti inferiori dell’albero, ad esempio, le versioni scritte delle cifre ‘4’ e ‘9’ condividono molte caratteristiche. Di conseguenza, spesso possono essere trovati raggruppati come un sotto-albero contenente solo questi due tipi di cifre.

I grafici mostrano due sotto-alberi estratti da interessanti sottopopolazioni del set di dati MNIST trovato da DeepECT. Queste sono le cifre sette (con e senza una barra centrale) e due (una versione riccia e una “snella”, che assomiglia più al carattere “Z”). Le cifre mostrate vengono campionate in modo casuale

Risultati Reuters

Il dataset Reuters contiene quattro categorie top sbilanciate (etichette di primo livello) con la seguente distribuzione di classi: Cooperate/Industrial con il 44%, Government/Social con il 24%, Markets con il 24% ed Economics con l ‘ 8%. Questo set di dati è spiegato in modo più dettagliato in . Le categorie per ogni articolo di notizie sono state scelte a mano e sono, quindi, in una certa misura soggettive. Inoltre, ogni categoria superiore ha diverse sottocategorie aggiuntive sovrapposte (etichette di secondo livello)-e sottocategorie (etichette di terzo livello)—con oltre il 96% degli articoli appartenenti a due o più sottocategorie. La tabella 5 mostra un risultato DeepECT per questo set di dati. Possiamo vedere che le prime due divisioni separano la maggior parte del sottoalbero governativo/sociale a partire dal nodo 3—e del sottoalbero dei mercati a partire dalle categorie del nodo 5 dalle altre due categorie. Il sottoalbero governo/sociale si differenzia ulteriormente in argomenti delle sottocategorie come sport, guerra e crimine, politica interna e internazionale. La categoria dei mercati si differenzia ulteriormente in diversi aspetti delle rispettive sottocategorie. Ad esempio, i nodi foglia nelle ultime due righe riguardano diverse sottocategorie dei mercati delle materie prime della sottocategoria. I nodi foglia nel mezzo sono per lo più legati a Corporate/Industriale ed economia. Non sono così separati come gli altri due sotto-alberi. Eppure, anche lì, possiamo trovare interessanti nodi fogliari. Ad esempio, il settimo nodo foglia (riga) dalla parte superiore condivide articoli di notizie etichettati con le prestazioni delle sottocategorie (di Corporate/Industrial) e le prestazioni economiche (di Economics) e sembra ragionevole aspettarsi parole correlate per queste due sottocategorie.

Risultati Moda-MNIST

Il diagramma mostra un albero di cluster per il set di dati Fashion-MNIST. Ogni nodo foglia mostra oggetti campionati in modo casuale ad esso assegnati. Le etichette sono interpretazioni degli autori. Le aree di colore sottolineano le tre dominante sotto-alberi che rappresentano tre tipi di oggetti presenti nel dataset: borse, scarpe, vestiti,

La Moda-MNIST contiene dieci diverse classi di vestiti, scarpe e borse, vale a dire T-shirt/top, pantaloni, pullover, abito, cappotto, sandalo, camicia, scarpa, borsa, e ankle boot. Un albero di cluster risultante del nostro metodo è mostrato in Fig. 7. I nodi foglia sono rappresentati come oggetti campionati casualmente assegnati ad esso. Le etichette di ogni nodo sono la nostra interpretazione in base agli oggetti assegnati al rispettivo nodo. Possiamo vedere che DeepECT ha trovato una gerarchia dall’aspetto completamente naturale all’interno di questo set di dati. Innanzitutto, le immagini sono suddivise in tre categorie: vestiti, scarpe e borse. Abbiamo evidenziato questi sotto-alberi con aree colorate. All’interno di ogni sotto-albero, possiamo trovare gerarchie naturali. La categoria di borse distingue tra borse senza cinturino/manico visibile, borse con manici piccoli e borse con tracolla. La verità a terra non distingue tra questi tipi di borse e li assegna tutti alla stessa classe. La categoria dei vestiti è prima divisa in pantaloni e vestiti per la parte superiore del corpo. Questi sono poi di nuovo partizionati in maniche corte e lunghe. Qui, la lunghezza della manica deve essere vista rispetto alla lunghezza totale del rispettivo capo perché ogni articolo è normalizzato per apparire della stessa dimensione all’interno dell’immagine, cioè, abiti e camicie sembrano essere della stessa taglia. La categoria di scarpe mostra anche alcune caratteristiche interessanti. In primo luogo, si distinguono scarpe più piccole e più grandi. Le scarpe più piccole sono poi ulteriormente divise in sandali e scarpe da ginnastica. Le scarpe più grandi hanno una suola piatta, un tacco piccolo o sono col tacco alto. Costruire la gerarchia basata su queste caratteristiche corre contro le classi di verità a terra di scarpe da ginnastica, sandali e stivaletti. Tuttavia, è—dal punto di vista dell’aspetto-una gerarchia valida e informativa per le scarpe.

Applicabilità per le attività di previsione su MNIST

Valutiamo anche DeepECT in un’attività di previsione. In tal modo, manteniamo gli autoencoders e la procedura di ottimizzazione del clustering come descritto sopra. In contrasto con la valutazione sperimentale di cui sopra, usiamo solo i primi 50.000 campioni (training set) del dataset MNIST durante l’ottimizzazione dell’albero del cluster. Dopo l’ottimizzazione, valutiamo le prestazioni di clustering dell’albero del cluster sui restanti 20.000 punti dati (set di test) precedentemente non visti.

In questo esperimento, otteniamo per il test impostato una purezza dendrogramma di \(0.73\ pm 0.08\) e una purezza fogliare di \(0.85 \ pm 0.06\), che è un leggero calo rispetto ai valori della Tabella 2. Tuttavia, il risultato è abbastanza robusto da consentire previsioni limitate di etichette di punti dati precedentemente non visti direttamente dall’albero del cluster. Tuttavia, nella maggior parte dei casi, addestreremmo un classificatore in base alle strutture di cluster trovate. Lo stesso vale, per l’incorporamento stesso, dove possiamo utilizzare, ad esempio, la perdita di autoencoder supervisionato per migliorare l’incorporamento trovato.

Riepilogo degli esperimenti

In sintesi, riteniamo che gli esperimenti mostrati su quattro set di dati reali mostrino chiaramente l’utilità e l’efficacia dell’albero del cluster DeepECT. Trovare questo tipo di strutture e selezionare il livello di dettaglio da analizzare rendono DeepECT un metodo prezioso per gli scienziati dei dati.