DeepECT :Deep Embedded Cluster Tree

vi evaluerer Vår foreslåtte Metode DeepECT på fire vanlige datasett for dyp læring: MNIST, USPS, Fashion-MNIST og Reuters. Tabell 1 viser statistikken over alle datasett som brukes i forsøkene. MNIST og USPS er begge bildedatasett som inneholder håndskrevne sifre. Mote-MNIST datasettet inneholder bilder av mote produkter, for eksempel bilder av klær, sko og vesker. Reuters datasett inneholder nyhetsartikler i fire toppkategorier, og vi bruker samme representasjon som beskrevet i .

Eksperimentelt Oppsett

vi fokuserer våre eksperimenter på evalueringen av vårt nye klyngelag. Derfor avstår vi fra å bruke mer utdypede autoencoder arkitekturer. I stedet bruker vi den samme generiske fullt tilkoblet autoencoder layout for alle eksperimenter, som brukes i . Som nevnt tidligere forventer vi at alle metoder vil få like mye fra mer sofistikerte og domenespesifikke arkitekturer. Imidlertid er en standard autoencoder arkitektur tilstrekkelig til å vise levedyktigheten Til DeepECT sammenlignet med baseline konkurrenter. Derfor bruker vi den samme generiske autoencoder-arkitekturen, som foreslått i og som også brukes i for å samle det innebygde rommet. Feedforward-koderen i denne arkitekturen har dimensjonene d-500–500–2000–10, og dekodernettverket har en speilet layout. Vi bruker ReLU aktiveringer og gjennomsnittlig squared feil rekonstruksjon tap Fra Eq. (1).

vi pre-tog ti autoencoders for hvert datasett og bruke de samme pre-trent nettverk for alle eksperimenter og sammenligningsmetoder. Ved hjelp av disse pre-trent autoencoders sikrer at hver metode har de samme startbetingelser for den innebygde plass og at variasjoner i clustering kvalitet ikke bare stammer fra kvalitativt forskjellige autoencoders. Forhåndsoppsettet ligner det som er beskrevet i . Vi pre-trene autoencoders som denoising autoencoders med en 20% korrupsjon rate. Først utfører vi en lagvis pre-trening med utfall etter hvert lag (med en hastighet på 20%) og 20.000 trinn per lag. Deretter finjusterer vi hele nettverket for 50.000 trinn uten utfall. Vi bruker input corruption bare for pre-trening og ikke for den faktiske optimalisering Av DeepECT og dens baseline metoder. For alle eksperimenter bruker Vi Adam (læring \({\hbox {rate}}=0.0001\), \(\beta _1=0,9, \ beta _2=0,999\)) som optimalisering algoritme og en mini-batch størrelse på 256 prøver. For den kombinerte optimaliseringen trener vi for ytterligere 50 000 iterasjoner for å sikre konvergens.

For DeepECT viste våre første eksperimenter med syntetiske data at splitting av treet hvert 500 optimaliseringstrinn gir lovende resultater, og mer utvidede trinnstørrelser økte ikke ytelsen ytterligere. Av denne grunn holder vi denne tidsplanen uten å justere den for forsøkene på virkelige datasett. Det samme gjelder beskjæringstærskelen nevnt i Sekten. 2.7. FOR MNIST, Fashion-MNIST og USPS vokser vi trærne til de inneholder tjue bladknuter. For Reuters datasett setter vi det maksimale antall bladnoder til tolv fordi det har færre ground truth clusters. På denne måten har vi to ganger og tre ganger det faktiske antall klynger. Vi anser disse verdiene tilstrekkelig til å fange viktige strukturer av de valgte datasettene for formålet med dette papiret. Vi bruker samme antall bladnoder for de hierarkiske baseline-metodene.

tomtene viser et utvalg av originale MNIST sifre og en tilfeldig utvidet versjon

for bildedatasettene eksperimenterte vi i tillegg med forstørrelsesutvidelsen DeepECT + Aug. Vi starter med de samme pre-trente autoencoders som i de andre forsøkene. Videre holder vi oss til samme optimaliseringsplan som beskrevet ovenfor for forsøkene med De Ikke-utvidede versjonene Av DeepECT. I hver iterasjon bruker vi den originale mini-batchen og dens forsterkede motpart for å optimalisere tapsfunksjonen I Eq. 9, i stedet for det ikke-forsterkede tapet I Eq. 6. Vi lager den utvidede versjonen av hvert bilde av en mini-batch, ved å bruke on-the-fly en tilfeldig affine transformasjon. Affine-transformasjonen roterer tilfeldig og skjærer bildet i området \ ( \ ) grader. Dessuten beveger den sifferet tilfeldig opp til to piksler i alle retninger. Figur 5 viser et eksempel på denne økningen FOR MNIST.

Evalueringsmetoder

Vi evaluerer cluster hierarchy Of DeepECT med dendrogram purity (DP) og leaf purity (LP) tiltaket. Vi beskriver begge nedenfor. Videre evaluerer vi klyngetreet mot flat baseline metoder. For dette bruker vi den velkjente normalized mutual information (NMI) og clustering accuracy (ACC) . Vi inkluderer disse for fullstendighet og for å vise At DeepECT også er konkurransedyktig i scenarier, hvor man forventer en flat klyngestruktur og vet det faktiske antall klynger i datasett. For å bestemme en k-klyngepartisjon fra et klyngetre, bruker vi oppdragene til k-nodene som var bladnoder etter de første \(k-1\) splittene.

Dendrogram Purity

dendrogram purity measure kan brukes til å evaluere klyngetreet mot en flat sannhetspartisjon. Det er den forventede renheten av sub-treet gitt av minst felles stamfar node for to tilfeldig samplet datapunkter av samme klasse. Det er 1.0 hvis og bare hvis alle datapunkter som tilhører en klasse i ground truth er tildelt et rent sub-tre, og det nærmer seg 0 for tilfeldig genererte trær.

den eksplisitte formelen er definert i som:

hvor \(C_1, \dots, C_K\) er datapunktsettene som svarer til ground truth-klassene, \({\text {lca}}(x,y)\) er den minst vanlige forfedernoden til x og y i klyngetreet, \({\text {dan}} (z)\) er settet med datapunkter tildelt noden z i klyngetreet, \({\text {pur}}(S, T) = |s \cap T| / | S|\) er renhetsmålet, og \({\mathcal {P}} = \{(x,y) \mid \exists c \ i \{C_1, \dots, C_K\}: x, y \I C \ wedge x \ ne y\}\) er settet av alle datapunktpar som tilhører samme klasse. Den dendrogram renhet kan beregnes effektivt og nøyaktig i en bottom-up rekursjon på klyngen treet.

Leaf Purity

I Tillegg til å bruke dendrogram purity, introduserer Vi et annet mål som vi kaller leaf purity (LP). Det er den vektede gjennomsnittlige renheten til bladnodene w.r. t. til flertallsklassen av objektene tildelt en bladknute, gitt av formelen:

hvor \({{\mathcal {L}}} _{{\mathcal {D}}}\) er settet med sett som inneholder datapunktene tildelt bladnodene.

Trehøydeavhengighet Av Renhetstiltak

Sammenligning av dendrogram og bladrenhet av to klyngetrær er bare direkte mulig hvis begge trærne har samme antall bladnoder. Undertrær kan imidlertid alltid kollapses i bladnoder for å oppfylle dette kravet. Derfor, vi kollapse bottom-up kobling-trær av baseline metoder—i rekkefølgen av kobling-ved å komprimere sub-trær i blad noder før vi har samme antall flette trinn igjen som split-noder i top-down trær Av DeepECT Og Halverer-K-midler. Denne prosessen sikrer at begge metodene er sammenlignbare med de hierarkiske evalueringstiltakene.

Hierarkiske Klyngebaselinjer

som en grunnlinje for å evaluere de hierarkiske egenskapene, klynger vi de innebygde dataene med de klassiske hierarkiske klyngealgoritmene som halverer-k-midler(AE + Halverer), single-linkage (Ae + Single) og complete-linkage (AE + Complete). Siden ingen av disse klassiske algoritmene kan optimalisere det innebygde rommet, undersøker vi også den enkle ideen om å kombinere den flate innebygde klyngealgoritmen IDEC med single-linkage og complete-linkage. IDEC er en metode som kombinerer clustering lag AV DEC med gjenoppbygging tap av autoencoder. FØRST kjører VI IDEC med antall klynger satt til en verdi høyere enn forventet antall klynger—i vårt tilfelle setter vi det lik det maksimale antall bladnoder vi bruker Til DeepECT. Deretter vurderer vi DISSE IDEC-klyngesentrene som representanter for de tildelte datapunktene, og prøver å gjenopprette en hierarkisk klyngestruktur ved å utføre single-linkage og complete-linkage på klyngesentrene(IDEC + Single og IDEC + Complete). En lignende teknikk foreslas i for klassiske, ikke-innebygde innstillinger med k-midler i stedet for IDEC.

Flat Clustering Baselines

som en baseline for å evaluere ytelsen Til DeepECT i en flat clustering innstilling, bruker vi k-midler på de innebygde data av pre-trent autoencoder (AE + k-midler) og IDEC . Hvis VI ignorerer fordelene med mer domenespesifikke og sofistikerte autoencoder arkitekturer, ER IDEC i dag en av de beste embedded-clustering metoder. I motsetning Til DeepECT må vi sette det faktiske antall klynger i bakken sannheten under optimalisering FOR IDEC og k-means. Videre setter vi hyperparameteren TIL IDEC for rekonstruksjonstapet til 0.1 som beskrevet i.

Generelle Resultater

de generelle resultatene-gjennomsnittlig over de ti pre-trente autoencoders – for den hierarkiske evalueringen ved hjelp av dendrogram renhet og bladrenhetsmål For DeepECT og de hierarkiske grunnlinjealgoritmene er vist i Tabell 2. DeepECT produserer konsekvent klyngetrær av høy kvalitet og er den beste algoritmen med en bred margin. Vi kan også se at forstørrelsesutvidelsen ytterligere forbedrer resultatene betydelig for MNIST og USPS. Resultatene Av DeepECT med og uten forstørrelsesutvidelsen for Mote-MNIST-datasettet er like fordi datasettforfatterne valgte å pre-behandle alle bilder slik at hvert moteelement har en normalisert representasjon. Resultatene av de klassiske metodene kan forklares av deres manglende evne til å forbedre embedding. Bladrenhetsverdiene for DeepECT indikerer at metoden er i stand til å skape homogene delpopulasjoner. Hvis vi sammenligner bladrenhetsverdiene Til DeepECT og de hierarkiske IDEC + Center-linkage-variantene med de andre baselinernes bladrenhetsverdier, kan vi se at den kombinerte optimaliseringen av clustering og autoencoder—av begge metodene-faktisk forbedrer homogeniteten til lokale strukturer. IDEC + Center-linkage er imidlertid ikke i stand til å trekke ut en sammenhengende hierarkisk struktur.

Tabell 3 viser eksperimentelle resultater for flat clustering sammenligningsmetoder basert på de samme pre-trent autoencoders. Siden vi bruker de samme pre-trente autoencoders, kan vi direkte se innflytelsen fra det respektive clustering-målet. BÅDE IDEC og DeepECT drar nytte av den kombinerte optimaliseringen sammenlignet med k-means, som ikke kan optimalisere integreringen. Tabell 4 viser resultatene av flere sentroid-baserte klyngemetoder hentet fra den respektive publikasjonen. Flere detaljer om disse metodene finnes i Sekt. 4. Vi kan se At DeepECT også utfører godt i forhold til disse metodene. Vi kan imidlertid også se at autoencoder-arkitekturen påvirker clustering-resultatet betydelig. FOR eksempel, dbc skiller SEG fra DEC bare ved bruk av en convolutional autoencoder, men oppnår overlegne resultater. Likevel er den valgte autoencoder-arkitekturen uavhengig av det valgte klyngelaget.

selvfølgelig er denne sammenligningen av flat clustering mål Og DeepECT urettferdig mot sistnevnte, fordi konkurrerende metoder er gitt det sanne antall klynger under optimalisering, mens For DeepECT bruker vi bare denne informasjonen under evaluering. Likevel kan vi se at Den vanlige Versjonen Av DeepECT kan holde tritt med disse metodene når det gjelder rå nmi-og ACC-tiltak, og at augmentation extension DeepECT + Aug viser betydelige forbedringer over Resultatene Av DeepECT, fordi Den kan ignorere kjente invarianser i dataene. Disse resultatene viser At DeepECT også er konkurransedyktig i scenarier, hvor man forventer en flat klyngestruktur, men ikke vet antall klynger og inspiserer klyngetreet rekursivt.

Detaljert Evaluering

I denne delen ser vi nærmere på De Resulterende DeepECT-trærne for datasettene ovenfor. Siden USPS-datasettets funn er sammenlignbare med MNIST – som begge representerer håndskrevne sifre-utelater vi disse resultatene for korthet.

MNIST-Resultater

en nærmere titt på De Resulterende DeepECT-trærne for MNIST-datasettet viser noen spennende egenskaper av forskjellige delpopulasjoner i de håndskrevne sifrene. To illustrative eksempler er vist I Fig. 6 og kan bli funnet i den vanlige og utvidede utvidelsen Av DeepECT. Noden renhet av de avbildede sub-trær for sifferet 7 ‘ er 98% og inneholder nesten alle forekomster av denne klassen. Den inneholder to bladknuter. En bladknute viser syvere med en liten tverrstang som det er vanlig skrevet I Europa, den andre bladknuten viser dette sifferet som det er mer vanlig skrevet i USA. Det andre undertreet inneholder nesten alle forekomster av sifferet ‘ 2 ‘ med en renhet på 97%. Dette undertreet inneholder også to bladnoder, hver med spesifikke egenskaper. Den første bladknuten inneholder forekomster som er mer krøllete og har en særegen sløyfe nederst. Den andre bladnoden inneholder en mer strømlinjeformet versjon av dette sifferet, som ser ut som tegnet ‘Z.’ de viste undertrærne bygger et naturlig hierarki for det respektive sifferet, og man kan lett forestille seg at disse funnene kan være av interesse for en forsker. Andre form avhengig grupperinger av sifre kan også bli funnet i nedre deler av treet, for eksempel, de skriftlige versjoner av sifrene ‘4’ og ‘9’ dele mange egenskaper. Følgelig kan de ofte bli funnet gruppert sammen som et sub-tre som bare inneholder disse to sifretyper.

tomtene viser to ekstraherte undertrær fra interessante subpopulasjoner AV MNIST datasettet Funnet Av DeepECT. Dette er sifrene syv (med Og uten midtstang) og to (en krøllete Og en strømlinjeformet versjon, som ser mer ut som tegnet ‘Z’). De viste sifrene er tilfeldig samplet

Reuters-Resultater

Reuters-datasettet inneholder fire ubalanserte toppkategorier (første nivå etiketter) med følgende klassefordeling: Samarbeide / Industri med 44%, Regjeringen / Sosial med 24%, Markeder med 24% og Økonomi med 8%. Dette datasettet er forklart mer detaljert i . Kategoriene for hver nyhetsartikkel ble valgt for hånd og er derfor til en viss grad subjektive. Videre har hver toppkategori flere overlappende underkategorier (etiketter på andre nivå)-og underkategorier (etiketter på tredje nivå)-med over 96% av artiklene som tilhører to eller flere underkategorier. Tabell 5 viser Et DeepECT-resultat for dette datasettet. Vi kan se at de to første splittelsene skiller det meste av Regjeringen / Sosial—sub-treet som starter ved node 3-Og Markets-sub-treet som starter ved node 5-kategoriene fra de to andre kategoriene. Regjeringen / Sosial sub-treet skiller seg deretter videre inn i emner av underkategorier som sport, krig og kriminalitet, innenriks og internasjonal politikk. Markedskategorien skiller seg også videre inn i ulike aspekter av de respektive underkategorier. For eksempel er bladnodene i de to siste radene opptatt av forskjellige underkategorier av Underkategorien Råvaremarkeder. Bladnodene i midten er for det meste relatert Til Bedrift / Industri og Økonomi. De er ikke så godt skilt som de to andre undertrærne. Likevel, selv der, kan vi finne interessante bladnoder. For eksempel deler den syvende bladnoden (rad) fra toppen nyhetsartikler merket med underkategoriene Ytelse (Av Bedrift/Industriell) og Økonomisk Ytelse (Av Økonomi), og det virker rimelig å forvente relaterte ord for de to underkategoriene.

Mote-MNIST Resultater

diagrammet viser et klyngetre for Mote-MNIST datasettet. Hver bladknute viser tilfeldig samplede objekter som er tildelt den. Etikettene er tolkninger av forfatterne. De fargede områdene markerer de tre dominerende undertrærne som representerer tre typer objekter som finnes i datasettet: poser, klær og sko

Mote-MNIST inneholder ti forskjellige klasser av klær, sko og vesker, nemlig T-skjorte/topp, bukser, pullover, kjole, frakk, sandal, skjorte, sneaker, bag og ankel boot. Et resulterende klyngetre av vår metode er vist I Fig. 7. Bladnodene er representert som tilfeldig samplede objekter tildelt den. Etikettene til hver node er vår tolkning basert på objektene som er tildelt den respektive noden. Vi kan se At DeepECT fant et helt naturlig utseende hierarki i dette datasettet. Først er bildene delt inn i tre kategorier: klær, sko og vesker. Vi fremhevet disse undertrærne med fargede områder. Innenfor hvert undertre finner vi naturlige hierarkier. Kategorien poser skiller mellom poser uten synlig stropp/håndtak, poser med små håndtak og poser med skulderrem. Bakken sannheten skiller ikke mellom disse typer poser og tildeler dem alle til samme klasse. Klærkategorien er først delt inn i bukser og klær til overkroppen. Disse er så igjen partisjonert i korte og lange ermer. Her må lengden på ermet ses i forhold til den totale lengden på det respektive plagget fordi hvert element er normalisert for å vises av samme størrelse i bildet, dvs., kjoler og skjorter ser ut til å være av samme størrelse. Skokategorien viser også noen interessante egenskaper. For det første utmerker seg mindre og større sko. De mindre skoene er så videre delt inn i sandaler og joggesko. De større skoene har enten en flatsåle, en liten hæl eller høyhælte. Bygge hierarkiet basert på disse funksjonene går mot bakken sannheten klasser av joggesko, sandaler, og ankelstøvletter. Likevel er det—fra et utseendeperspektiv – et gyldig og informativt hierarki for sko.

Anvendelighet For Prediksjonsoppgaver på MNIST

vi evaluerer Også DeepECT i en prediksjonsoppgave. Dermed beholder vi autoencoders og clustering optimization-prosedyren som beskrevet ovenfor. I motsetning til den eksperimentelle evalueringen ovenfor, bruker vi bare de første 50.000-prøvene (treningssett) av datasettet MNIST under cluster tree optimization. Etter optimalisering evaluerer vi clustering-ytelsen til klyngetreet på de tidligere usette, gjenværende 20.000 datapunktene (testsett).

i dette eksperimentet får vi for testsettet et dendrogram renhet av \(0.73 \ pm 0.08\) og en bladrenhet på \(0.85\pm 0.06\), som er en liten nedgang i Forhold til verdiene i Tabell 2. Likevel er resultatet robust nok til å tillate begrensede etikettforutsigelser av tidligere usynlige datapunkter direkte av klyngetreet. I de fleste tilfeller vil vi imidlertid trene en klassifikator basert på de funnet klyngestrukturene. Det samme gjelder for embedding selv, hvor vi kan bruke, for eksempel, overvåket autoencoder tap for å forbedre funnet embedding.

Eksperimenter Sammendrag

oppsummert tror vi at de viste forsøkene på fire virkelige datasett viser tydelig nytten og effektiviteten Til DeepECT-klyngetreet. Å finne slike strukturer og velge detaljnivået som skal analyseres, gjør DeepECT til en verdifull metode for datavitenskapere.