DeepECT: det dybe indlejrede Klyngetræ

vi evaluerer vores foreslåede metode DeepECT på fire almindeligt anvendte dybe læringsdatasæt: MNIST, USPS, Fashion-MNIST og Reuters. Tabel 1 viser statistikken over alle datasæt, der anvendes i forsøgene. MNIST og USPS er begge billeddatasæt, der indeholder håndskrevne cifre. Fashion-MNIST datasættet indeholder billeder af modeprodukter, såsom billeder af tøj, sko og tasker. Reuters datasæt indeholder nyhedsartikler i fire topkategorier, og vi bruger den samme repræsentation som beskrevet i .

eksperimentel opsætning

vi fokuserer vores eksperimenter på evalueringen af vores nye klyngelag. Derfor afholder vi os fra at bruge mere detaljerede autoencoder-arkitekturer. I stedet bruger vi den samme generiske fuldt tilsluttet autoencoder layout for alle eksperimenter, som anvendes i . Som tidligere nævnt forventer vi, at alle metoder vil vinde lige fra mere sofistikerede og domænespecifikke arkitekturer. Imidlertid er en standard autoencoder-arkitektur tilstrækkelig til at vise levedygtigheden af DeepECT sammenlignet med baseline-konkurrenterne. Derfor, vi bruger den samme generiske autoencoder-arkitektur, som foreslået i, og som også bruges i med det formål at klynge det indlejrede rum. Den fremadgående indkoder i denne arkitektur har dimensionerne d-500–500–2000–10, og dekodernetværket har et spejlet layout. Vi bruger ReLU-aktiveringer og det gennemsnitlige kvadratiske fejlrekonstruktionstab fra EKV. (1).

vi træner ti autoencodere for hvert datasæt og bruger de samme forududdannede netværk til alle eksperimenter og sammenligningsmetoder. Brug af disse forududdannede autoencodere sikrer, at hver metode har de samme startbetingelser for det indlejrede rum, og at variationer i klyngekvaliteten ikke kun stammer fra kvalitativt forskellige autoencodere. Opsætningen før træning svarer til den, der er beskrevet i . Vi præ-træne autoencoders som denoising autoencoders med en 20% korruption Sats. Først udfører vi en lagvis præ-træning med frafald efter hvert lag (med en hastighed på 20%) og 20.000 trin pr. Derefter finjusterer vi hele netværket til 50.000 trin uden frafald. Vi bruger kun inputkorruption til præ-træning og ikke til den faktiske optimering af DeepECT og dens basismetoder. For alle eksperimenter bruger vi Adam (læring \({\hboks {rate}}=0.0001\), \(\beta _1=0,9, \beta _2=0,999\)) som optimering algoritme og en mini-batch størrelse på 256 prøver. Til den kombinerede optimering træner vi for yderligere 50.000 iterationer for at sikre konvergens.

for DeepECT viste vores indledende eksperimenter med syntetiske data, at opdeling af træet hvert 500 optimeringstrin giver lovende resultater, og mere udvidede trinstørrelser øgede ikke ydeevnen yderligere. Af denne grund holder vi denne tidsplan uden at justere den til eksperimenterne på virkelige datasæt. Det samme gælder for den beskæringstærskel, der er nævnt i sekt. 2.7. For MNIST, Fashion-MNIST og USPS dyrker vi træerne, indtil de indeholder tyve bladknuder. For Reuters datasæt indstiller vi det maksimale antal bladknudepunkter til tolv, fordi det har færre sandhedsklynger. På denne måde har vi to gange og tre gange det faktiske antal klynger. Vi betragter disse værdier som tilstrækkelige til at fange væsentlige strukturer i de valgte datasæt med henblik på dette papir. Vi bruger det samme antal bladknudepunkter til de hierarkiske baseline-metoder.

plottene viser en prøve af originale MNIST-cifre og en tilfældigt forstærket version

for billeddatasætene eksperimenterede vi desuden med augmentation-udvidelsen DeepECT + Aug. Vi starter med de samme forududdannede autoencodere som i de andre eksperimenter. Yderligere holder vi os til den samme optimeringsplan som beskrevet ovenfor for eksperimenterne med de ikke-forstørrede versioner af deepect. I hver iteration bruger vi den originale mini-batch og dens forstærkede modstykke til at optimere tabsfunktionen i EKV. 9, i stedet for det ikke-forstærkede tab i EKV. 6. Vi opretter den udvidede version af hvert billede af en mini-batch ved at anvende on-the-fly en tilfældig affine transformation. Affine-transformationen roterer tilfældigt og skærer billedet i området \(\) grader. Det bevæger også cifferet tilfældigt op til to billedpunkter i enhver retning. Figur 5 viser et eksempel på denne forøgelse for MNIST.

evalueringsmetoder

vi evaluerer klyngehierarkiet for DeepECT med dendrogram renhed (DP) og bladrenhed (LP) mål. Vi beskriver begge nedenfor. Endvidere vurderer vi klyngetræet mod flade baseline metoder. Til dette bruger vi den velkendte normaliserede gensidige information (NMI) og clustering nøjagtighed (ACC) . Vi inkluderer disse for fuldstændighed og for at vise, at DeepECT også er konkurrencedygtig i scenarier, hvor man forventer en flad klyngestruktur og kender det faktiske antal klynger i datasæt. For at bestemme en k-klyngepartition fra et klyngetræ bruger vi tildelingerne til de k-noder, der var bladnoder efter de første \(k-1\) splittelser.

Dendrogram renhed

dendrogram-renhedsmålet kan bruges til at evaluere klyngetræet mod en flad jord sandhedspartition. Det er den forventede renhed af undertræet, der er givet af den mindst almindelige forfædreknude for to tilfældigt samplede datapunkter i samme klasse. Det er 1.0 hvis og kun hvis alle datapunkter, der tilhører en klasse I jordens sandhed, er tildelt et rent undertræ, og det nærmer sig 0 for tilfældigt genererede træer.

den eksplicitte formel er defineret I som:

hvor \(C_1, \ dots, C_K\) er de datapunktsæt, der svarer til jorden sandhedsklasser, \({\tekst {lca}}(H, y)\) er den mindst almindelige stamfaderknude for H og y i klyngetræet, \({\tekst {dan}} (Å)\) er det sæt datapunkter, der er tildelt noden å i klyngetræet, \({\tekst {pur}}(S, T) = |S \cap T| / | S|\) er renhedsmålet, og \({\mathcal {P}} = \{(S,y) \mid \eksisterer C \i \{C_1, \dots , C_K\}: S,y \i C \kile \ne Y\}\) er sæt af alle datapunktpar, der tilhører samme klasse. Dendrogramrenheden kan beregnes effektivt og præcist i en bottom-up rekursion på klyngetræet.

Bladrenhed

udover at bruge dendrogram renhed introducerer vi en anden foranstaltning, som vi kalder bladrenhed (LP). Det er den vægtede gennemsnitlige renhed af bladknudepunkterne med flertalsklassen af de objekter, der er tildelt en bladknude, givet ved formlen:

hvor \({{\mathcal {L}}} _{{\mathcal {D}}}\) er det sæt sæt, der indeholder de datapunkter, der er tildelt bladnoderne.

Træhøjdeafhængighed af Renhedsmål

sammenligning af dendrogram og bladrenhed af to klyngetræer er kun direkte mulig, hvis begge træer har det samme antal bladknuder. Imidlertid kan undertræer altid kollapses i bladknuder for at opfylde dette krav. Derfor, vi kollapser bund-op-koblingstræerne i basislinjemetoderne—i rækkefølgen af sammenkobling-ved at komprimere undertræer i bladknudepunkter, indtil vi har det samme antal fletningstrin tilbage som split-noder i de nedadrettede træer i DeepECT og Bisecting-K-midler. Denne proces sikrer, at begge metoder er sammenlignelige med de hierarkiske evalueringsforanstaltninger.

hierarkiske Klyngebaselinjer

som en basislinje til evaluering af de hierarkiske egenskaber klynger vi de indlejrede data med de klassiske hierarkiske klyngealgoritmer, der halverer-k-midler (AE + halverer), single-linkage (Ae + Single) og complete-linkage (ae + Complete). Da ingen af disse klassiske algoritmer kan optimere det indlejrede rum, undersøger vi også den enkle ide om at kombinere den flade indlejrede klyngealgoritme IDEC med single-linkage og complete-linkage. IDEC er en metode, der kombinerer klyngelaget af DEC med genopbygningstabet af autoencoderen. Først kører vi IDEC med antallet af klynger indstillet til en værdi, der er højere end det forventede antal klynger—i vores tilfælde indstiller vi det lig med det maksimale antal bladnoder, vi bruger til DeepECT. Derefter betragter vi disse IDEC-klyngecentre som repræsentanter for de tildelte datapunkter og forsøger at gendanne en hierarkisk klyngestruktur ved at udføre single-linkage og complete-linkage på klyngecentrene (IDEC + Single og IDEC + Complete). En lignende teknik foreslås i for klassisk, ikke-indlejrede indstillinger med k-midler i stedet for IDEC.

flad Klyngebaselinjer

som en basislinje til evaluering af ydeevnen for DeepECT i en flad klyngeindstilling bruger vi k-midler på de indlejrede data fra den forududdannede autoencoder (AE+k-midler) og IDEC . Hvis vi ignorerer fordelene ved mere domænespecifikke og sofistikerede autoencoder-arkitekturer, er IDEC i øjeblikket en af de bedste indlejrede klyngemetoder. I modsætning til DeepECT er vi nødt til at indstille det faktiske antal klynger i jorden sandhed under optimering for IDEC og k-midler. Endvidere sætter vi Idec ‘ s hyperparameter til genopbygningstabet til 0,1 som beskrevet i .

generelle resultater

de generelle resultater—i gennemsnit over de ti forududdannede autoencodere-til den hierarkiske evaluering ved hjælp af dendrogramrenhed og bladrenhedsmål for DeepECT og de hierarkiske baselinealgoritmer er vist i tabel 2. DeepECT producerer konsekvent klyngetræer af høj kvalitet og er den mest effektive algoritme med en bred margin. Vi kan også se, at udvidelsen yderligere forbedrer resultaterne betydeligt for MNIST og USPS. Resultaterne af DeepECT med og uden forstørrelsesudvidelsen for Fashion-MNIST-datasættet er ens, fordi datasætforfatterne valgte at forbehandle alle billeder, således at hvert modeelement har en normaliseret repræsentation. Resultaterne af de klassiske metoder kan forklares ved deres manglende evne til at forbedre indlejringen. Bladrenhedsværdierne for deepect indikerer, at metoden er i stand til at skabe homogene underpopulationer. Hvis vi sammenligner bladrenhedsværdierne for DeepECT og de hierarkiske IDEC + Center-linkage—varianter med de andre basislinjers bladrenhedsværdier, kan vi se, at den kombinerede optimering af klyngedannelse og autoencoder—af begge metoder-faktisk forbedrer homogeniteten af lokale strukturer. IDEC + Center-linkage er imidlertid heller ikke i stand til at udtrække en sammenhængende hierarkisk struktur.

tabel 3 viser de eksperimentelle resultater for de flade klyngesammenligningsmetoder baseret på de samme præuddannede autoencodere. Da vi bruger de samme forududdannede autoencodere, kan vi direkte se indflydelsen fra det respektive klyngemål. Både IDEC og DeepECT drager fordel af den kombinerede optimering sammenlignet med k-means, som ikke kan optimere indlejringen. Tabel 4 viser resultaterne af flere centroid-baserede klyngemetoder taget fra den respektive publikation. Flere detaljer om disse metoder findes i sekt. 4. Vi kan se, at DeepECT også fungerer godt sammenlignet med disse metoder. Vi kan dog også se, at autoencoder-arkitekturen påvirker klyngeresultatet betydeligt. For eksempel adskiller DBC sig kun fra DEC ved brug af en konvolutionel autoencoder, men opnår overlegne resultater. Alligevel er den valgte autoencoder-arkitektur uafhængig af det valgte klyngelag.

selvfølgelig er denne sammenligning af fladklyngemål og DeepECT uretfærdig over for sidstnævnte, fordi de konkurrerende metoder får det rigtige antal klynger under optimering, mens for DeepECT bruger vi kun disse oplysninger under evaluering. Ikke desto mindre kan vi se, at den almindelige version af DeepECT kan følge med disse metoder med hensyn til rå NMI-og ACC-foranstaltninger, og at augmentation-udvidelsen DeepECT + Aug viser betydelige forbedringer i forhold til resultaterne af deepect, fordi den kan ignorere kendte invariancer inden for dataene. Disse resultater viser, at DeepECT også er konkurrencedygtig i scenarier, hvor man forventer en flad klyngestruktur, men ikke kender antallet af klynger og inspicerer klyngetræet rekursivt.

detaljeret evaluering

i dette afsnit ser vi nærmere på de resulterende DeepECT-træer for ovenstående datasæt. Da USPS—datasætets resultater er sammenlignelige med MNIST—som begge repræsenterer håndskrevne cifre-udelader vi disse resultater for kortfattethed.

MNIST-resultater

et nærmere kig på de resulterende DeepECT-træer til MNIST-datasættet viser nogle spændende egenskaber ved forskellige underpopulationer inden for de håndskrevne cifre. To illustrative eksempler er vist i Fig. 6 og kan findes i den almindelige og udvidede udvidelse af DeepECT. Node renheden af de afbildede undertræer for cifferet 7′ er 98% og indeholder næsten alle forekomster af denne klasse. Den indeholder to bladknuder. En bladknude viser syvere med en lille tværstang, som det almindeligvis er skrevet i Europa, den anden bladknude viser dette ciffer, da det mere almindeligt er skrevet i USA. Det andet undertræ indeholder næsten alle forekomster af cifferet ‘2’ med en renhed på 97%. Dette undertræ indeholder også to bladknuder, hver med specifikke egenskaber. Den første bladknude indeholder forekomster, der er mere krøllede og har en karakteristisk sløjfe i bunden. Den anden bladknude indeholder en mere ‘strømlinet’ version af dette ciffer, der ligner karakteren ‘S.’ de viste undertræer bygger et naturligt hierarki for det respektive ciffer, og man kan let forestille sig, at disse fund kan være af interesse for en forsker. Anden form afhængig grupperinger af cifre kan også findes i lavere dele af træet, for eksempel, de skriftlige versioner af cifrene ‘4’ og ‘9’ deler mange karakteristika. Derfor kan de ofte findes grupperet som et undertræ, der kun indeholder disse tocifrede typer.

plottene viser to ekstraherede undertræer fra interessante underpopulationer af MNIST-datasættet fundet af DeepECT. Dette er cifrene syv (med og uden en midterste tværstang) og to (en krøllet og en ‘strømlinet’ version, der ligner mere karakteren ‘å’). De viste cifre er tilfældigt samplet

Reuters resultater

Reuters datasæt indeholder fire ubalancerede topkategorier (etiketter på første niveau) med følgende klassedistribution: samarbejde/industri med 44%, regering/Social med 24%, markeder med 24% og økonomi med 8%. Dette datasæt er forklaret mere detaljeret i . Kategorierne for hver nyhedsartikel blev valgt manuelt og er derfor til en vis grad subjektive. Desuden har hver topkategori flere yderligere overlappende underkategorier (etiketter på andet niveau)-og underkategorier (etiketter på tredje niveau)—hvor over 96% af artiklerne tilhører to eller flere underkategorier. Tabel 5 viser et DeepECT-resultat for dette datasæt. Vi kan se, at de to første splittelser adskiller det meste af regeringen/Social—undertræet, der starter ved node 3-og Markets—undertræet, der starter ved node 5—kategorierne fra de to andre kategorier. Regeringen / det sociale undertræ adskiller sig derefter yderligere i emner i underkategorierne såsom sport, krig og kriminalitet, indenrigs-og international politik. Markedskategorien adskiller sig også yderligere i forskellige aspekter af de respektive underkategorier. For eksempel vedrører bladknudepunkterne i de sidste to rækker forskellige underkategorier af Underkategorimarkederne. Bladknudepunkterne i midten er for det meste relateret til virksomhed/industri og økonomi. De er ikke så godt adskilt som de to andre undertræer. Men selv der kan vi finde interessante bladknuder. For eksempel deler den syvende bladknude (række) fra toppen nyhedsartikler mærket med underkategorierne Performance (of Corporate/Industrial) og The Economic Performance (of Economics), og det synes rimeligt at forvente relaterede ord for disse to underkategorier.

Fashion-MNIST resultater

diagrammet viser et klyngetræ til Fashion-MNIST-datasættet. Hver bladknude viser tilfældigt samplede objekter, der er tildelt den. Etiketterne er fortolkninger af forfatterne. De farvede områder fremhæver de tre dominerende undertræer, der repræsenterer tre typer objekter, der findes i datasættet: tasker, tøj, og sko

Fashion-MNIST indeholder ti forskellige klasser af tøj, sko og tasker, nemlig T-shirt/top, bukser, pullover, kjole, frakke, sandal, skjorte, sneaker, taske og ankelstøvle. Et resulterende klyngetræ af vores metode er vist i Fig. 7. Bladknudepunkterne er repræsenteret som tilfældigt samplede objekter, der er tildelt det. Etiketterne for hver node er vores fortolkning baseret på de objekter, der er tildelt den respektive node. Vi kan se, at DeepECT fandt et helt naturligt udseende hierarki inden for dette datasæt. For det første er billederne opdelt i tre kategorier: tøj, sko og tasker. Vi fremhævede disse undertræer med farvede områder. Inden for hvert undertræ kan vi finde naturlige hierarkier. Kategorien af poser skelner mellem poser uden synlig rem/håndtag, poser med små håndtag og poser med skulderrem. Ground truth skelner ikke mellem disse typer poser og tildeler dem alle til samme klasse. Tøjkategorien er først opdelt i bukser og tøj til overkroppen. Disse er derefter igen opdelt i korte og lange ærmer. Her skal længden af ærmet ses i forhold til den samlede længde af det respektive tøj, fordi hvert element er normaliseret til at fremstå af samme størrelse inden for billedet, dvs., kjoler og skjorter ser ud til at være af samme størrelse. Sko kategorien viser også nogle interessante egenskaber. For det første skelnes der mellem mindre og større sko. De mindre sko er derefter yderligere opdelt i sandaler og sneakers. De større sko har enten en flad sål, en lille hæl eller er højhælede. Opbygning af hierarkiet baseret på disse funktioner løber mod jorden sandhedsklasser af sneakers, sandaler og ankelstøvler. Ikke desto mindre er det—fra et udseende perspektiv—et gyldigt og informativt hierarki for sko.

anvendelighed til Forudsigelsesopgaver på MNIST

vi evaluerer også DeepECT i en forudsigelsesopgave. Derved holder vi autoencoders og klyngeoptimeringsproceduren som beskrevet ovenfor. I modsætning til den eksperimentelle evaluering ovenfor bruger vi kun de første 50.000 prøver (træningssæt) af datasættet MNIST under klyngetræoptimeringen. Efter optimering vurderer vi klyngetræets klyngepræstation på de tidligere usete, resterende 20.000 datapunkter (testsæt).

i dette eksperiment får vi til testindstillingen en dendrogram renhed på \(0.73 \ pm 0,08\) og en bladrenhed på \(0,85\pm 0,06\), hvilket er et lille fald i forhold til værdierne i tabel 2. Ikke desto mindre er resultatet robust nok til at give mulighed for begrænsede label-forudsigelser af tidligere usete datapunkter direkte af klyngetræet. I de fleste tilfælde træner vi imidlertid en klassifikator baseret på de fundne klyngestrukturer. Det samme gælder for selve indlejringen, hvor vi for eksempel kan bruge det overvågede autoencoder-tab til at forbedre den fundne indlejring.

Eksperimentoversigt

sammenfattende mener vi, at de viste eksperimenter på fire virkelige datasæt tydeligt viser nytten og effektiviteten af DeepECT-klyngetræet. At finde denne slags strukturer og vælge det detaljeringsniveau, der skal analyseres, gør DeepECT til en værdifuld metode for dataforskere.