DeepECT: det djupa inbäddade Klusterträdet

vi utvärderar vår föreslagna metod DeepECT på fyra vanliga djupinlärningsdataset: MNIST, USPS, Fashion-MNIST och Reuters. Tabell 1 visar statistiken över alla dataset som används i experimenten. MNIST och USPS är båda bilddata som innehåller handskrivna siffror. Fashion-MNIST dataset innehåller bilder av modeprodukter, såsom bilder av kläder, skor och väskor. Reuters dataset innehåller nyhetsartiklar i fyra toppkategorier, och vi använder samma representation som beskrivs i .

experimentell inställning

vi fokuserar våra experiment på utvärderingen av vårt nya klusterlager. Därför avstår vi från att använda mer detaljerade autoencoderarkitekturer. Istället använder vi samma generiska helt ansluten autoencoder layout för alla experiment, som används i . Som tidigare nämnts förväntar vi oss att alla metoder skulle vinna lika från mer sofistikerade och domänspecifika arkitekturer. En standard autoencoder-arkitektur är dock tillräcklig för att visa deepects livskraft jämfört med baslinjekonkurrenterna. Därför använder vi samma generiska autoencoder-arkitektur, som föreslås i och som också används för att klustera det inbäddade utrymmet. Feedforward-kodaren i denna arkitektur har dimensionerna d-500–500–2000–10, och avkodningsnätverket har en speglad layout. Vi använder Relu-aktiveringar och den genomsnittliga kvadratiska felrekonstruktionsförlusten från Eq. (1).

vi tränar tio autoencoders för varje dataset och använder samma förutbildade nätverk för alla experiment och jämförelsemetoder. Med hjälp av dessa förutbildade autoencoders säkerställer att varje metod har samma startförhållanden för det inbäddade utrymmet och att variationer i klusterkvaliteten inte bara härrör från kvalitativt olika autoencoders. Förutbildningsinställningen liknar den som beskrivs i . Vi Pre-train autoencoders som denoising autoencoders med en 20% korruption. Först utför vi en lagervis förutbildning med bortfall efter varje lager (med en hastighet på 20%) och 20 000 steg per lager. Sedan finjusterar vi hela nätverket för 50 000 steg utan bortfall. Vi använder input korruption endast för pre-utbildning och inte för den faktiska optimering av DeepECT och dess baslinje metoder. För alla experiment använder vi Adam (learning \({\hbox {rate}}=0.0001\), \(\beta _1 = 0,9, \ beta _2=0,999\)) som optimeringsalgoritmen och en mini-batchstorlek på 256 prover. För den kombinerade optimeringen tränar vi för ytterligare 50 000 iterationer för att säkerställa konvergens.

för DeepECT visade våra initiala experiment med syntetiska data att splittring av trädet varje 500 optimeringssteg ger lovande resultat och mer utökade stegstorlekar ökade inte prestandan ytterligare. Av denna anledning håller vi detta schema utan att justera det för experimenten på verkliga datamängder. Detsamma gäller för beskärningströskeln som nämns i sekt. 2.7. För mnist, Fashion-MNIST och USPS växer vi träden tills de innehåller tjugo bladnoder. För Reuters dataset ställer vi in det maximala antalet bladnoder till tolv eftersom det har färre marksanningskluster. På så sätt har vi två gånger och tre gånger det faktiska antalet kluster. Vi anser att dessa värden är tillräckliga för att fånga väsentliga strukturer för de valda datamängderna för syftet med detta dokument. Vi använder samma antal bladnoder för de hierarkiska baslinjemetoderna.

tomterna visar ett urval av original mnist siffror och en slumpmässigt förstärkt version

för bilddata, vi experimenterade dessutom med förstärkningsförlängningen DeepECT + Aug. Vi börjar med samma förutbildade autoencoders som i de andra experimenten. Vidare håller vi oss till samma optimeringsschema som beskrivits ovan för experimenten med de icke-förstärkta versionerna av DeepECT. I varje iteration använder vi den ursprungliga mini-batchen och dess förstärkta motsvarighet för att optimera förlustfunktionen i Eq. 9, istället för den icke-förstärkta förlusten i Eq. 6. Vi skapar den förstärkta versionen av varje bild av en mini-batch, genom att tillämpa en slumpmässig Affin-transformation. Den affina omvandlingen roterar slumpmässigt och skär bilden i intervallet \ ( \ ) grader. Dessutom flyttar den siffran slumpmässigt upp till två pixlar i vilken riktning som helst. Figur 5 visar ett exempel på denna förstärkning för MNIST.

utvärderingsmetoder

vi utvärderar klusterhierarkin för DeepECT med måttet DENDROGRAM purity (DP) och leaf purity (LP). Vi beskriver båda nedan. Vidare utvärderar vi klusterträdet mot plana baslinjemetoder. För detta använder vi den välkända normalized mutual information (NMI) och clustering accuracy (ACC) . Vi inkluderar dessa för fullständighet och för att visa att DeepECT också är konkurrenskraftigt i scenarier, där man förväntar sig en platt klusterstruktur och känner till det faktiska antalet kluster i dataset. För att bestämma en k-klusterpartition från ett klusterträd använder vi tilldelningarna till k-noderna som var bladnoder efter den första \(k-1\) splittringen.

Dendrogram Purity

dendrogram purity measure kan användas för att utvärdera klusterträdet mot en plan mark sanningspartition. Det är den förväntade renheten hos underträdet som ges av den minst gemensamma förfadernoden för två slumpmässigt samplade datapunkter i samma klass. Det är 1.0 om och endast om alla datapunkter som tillhör en klass i marksanningen tilldelas något rent underträd, och det närmar sig 0 för slumpmässigt genererade träd.

den uttryckliga formeln definieras i som:

där \(C_1, \ dots, C_K\) är de datapunktsuppsättningar som motsvarar marksanningsklasserna, \({\text {lca}} (x, y)\) är den minsta gemensamma förfadernoden för x och y i klusterträdet, \({\text {dan}} (z)\) är den uppsättning datapunkter som tilldelats noden z i klusterträdet, \({\text {pur}} (S, T) = |s \cap T| / | S|\) är renhetsmåttet, och \({\mathcal {p}} = \{(x,y) \mid \existerar C \i \{C_1, \dots , C_K\}: x,y \i C \wedge x \ne y\}\) är uppsättningen av alla datapunktspar som tillhör samma klass. Dendrogramrenheten kan beräknas effektivt och exakt i en bottom-up-rekursion på klusterträdet.

blad renhet

förutom att använda dendrogram renhet, vi införa en annan åtgärd som vi kallar blad renhet (LP). Det är den vägda genomsnittliga renheten hos bladnoderna w.r. t. till majoritetsklassen av de objekt som tilldelats en bladnod, givet med formeln:

där \({{\mathcal {L}}} _{{\mathcal {D}}}\) är den uppsättning uppsättningar som innehåller de datapunkter som tilldelats bladnoderna.

trädhöjd beroende av Renhetsåtgärder

att jämföra dendrogram och bladrenhet hos två klusterträd är endast direkt möjligt om båda träden har samma antal bladnoder. Underträd kan dock alltid kollapsas i bladnoder för att uppfylla detta krav. Därför kollapsar vi botten-upp-länkningsträden i baslinjemetoderna—i länkningsordningen-genom att komprimera underträd till bladnoder tills vi har samma antal sammanslagningssteg kvar som delade noder i DeepECT och Bisecting-K-means. Denna process säkerställer att båda metoderna är jämförbara med de hierarkiska utvärderingsåtgärderna.

hierarkiska kluster baslinjer

som en baslinje för utvärdering av hierarkiska egenskaper, vi kluster inbäddade data med den klassiska hierarkiska kluster algoritmer bisecting-k-means (AE + Bisecting), single-linkage (ae + Single), och complete-linkage (ae + Complete). Eftersom ingen av dessa klassiska algoritmer kan optimera det inbäddade utrymmet, utforskar vi också den enkla tanken att kombinera den platta inbäddade klusteralgoritmen IDEC med enkelkoppling och komplett koppling. IDEC är en metod som kombinerar klusterskiktet av DEC med rekonstruktionsförlusten av autoencoder. Först kör vi IDEC med antalet kluster som är högre än det förväntade antalet kluster—i vårt fall ställer vi in det lika med det maximala antalet bladnoder vi använder för DeepECT. Sedan betraktar vi dessa IDEC-klustercentra som representanter för de tilldelade datapunkterna och försöker återställa en hierarkisk klusterstruktur genom att utföra enkelkoppling och fullständig koppling på klustercentralerna (IDEC + Single och IDEC + Complete). En liknande teknik föreslås i för klassisk, icke-inbäddade inställningar med k-medel istället för IDEC.

Flat Clustering Baselines

som en baslinje för utvärdering av Deepects prestanda i en flat clustering-inställning använder vi k-means på inbäddade data för den förutbildade autoencoder (AE+k-means) och IDEC . Om vi ignorerar fördelarna med mer domänspecifika och sofistikerade autoencoderarkitekturer är IDEC för närvarande en av de bästa inbäddade klustermetoderna. I motsats till DeepECT måste vi ställa in det faktiska antalet kluster i ground truth under optimering för IDEC och k-means. Vidare ställer vi in HYPERPARAMETERN för IDEC för rekonstruktionsförlusten till 0.1 som beskrivs i .

allmänna resultat

de allmänna resultaten-i genomsnitt över de tio förutbildade autoencodersna-för den hierarkiska utvärderingen med dendrogramrenhet och bladrenhetsmått för DeepECT och de hierarkiska basalgoritmerna visas i Tabell 2. DeepECT producerar konsekvent klusterträd av hög kvalitet och är den bästa algoritmen med stor marginal. Vi kan också se att förstärkningsförlängningen ytterligare förbättrar resultaten avsevärt för MNIST och USPS. Resultaten av DeepECT med och utan förstärkningsförlängningen för Fashion-MNIST-datasetet är likartade eftersom datasetförfattarna valde att förbehandla alla bilder så att varje modeobjekt har en normaliserad representation. Resultaten av de klassiska metoderna kan förklaras av deras oförmåga att förbättra inbäddning. Bladrenhetsvärdena för DeepECT indikerar att metoden kan skapa homogena underpopulationer. Om vi jämför bladrenhetsvärdena för DeepECT och de hierarkiska IDEC + Center-linkage—varianterna till de andra baslinjernas bladrenhetsvärden kan vi se att den kombinerade optimeringen av clustering och autoencoder—av båda metoderna-verkligen förbättrar homogeniteten hos lokala strukturer. IDEC + Center-linkage kan emellertid inte extrahera en sammanhängande hierarkisk struktur.

tabell 3 visar de experimentella resultaten för jämförelsemetoderna för platta kluster baserat på samma förutbildade autoencoders. Eftersom vi använder samma förutbildade autoencoders kan vi direkt se påverkan av respektive klustermål. Både IDEC och DeepECT drar nytta av den kombinerade optimeringen jämfört med k-means, som inte kan optimera inbäddningen. Tabell 4 visar resultaten av mer centroid-baserade klustringsmetoder hämtade från respektive publikation. Mer detaljer om dessa metoder finns i sekt. 4. Vi kan se att DeepECT också fungerar bra jämfört med dessa metoder. Vi kan dock också se att autoencoder-arkitekturen påverkar klusterresultatet avsevärt. Till exempel, DBC skiljer sig från DEC endast genom användning av en convolutional autoencoder men uppnår överlägsna resultat. Ändå är den valda autoencoder-arkitekturen oberoende av det valda klusterskiktet.

naturligtvis är denna jämförelse av platta klustermål och DeepECT orättvist mot den senare, eftersom de konkurrerande metoderna ges det verkliga antalet kluster under optimering, medan för DeepECT använder vi endast denna information under utvärdering. Ändå kan vi se att den vanliga versionen av DeepECT kan hålla jämna steg med dessa metoder när det gäller råa NMI-och ACC-åtgärder och att förstärkningsförlängningen DeepECT + Aug visar betydande förbättringar jämfört med resultaten från DeepECT, eftersom den kan ignorera kända invarianser inom data. Dessa resultat visar att DeepECT också är konkurrenskraftigt i scenarier, där man förväntar sig en platt klusterstruktur, men inte känner till antalet kluster och inspekterar klusterträdet rekursivt.

detaljerad utvärdering

i det här avsnittet tar vi en närmare titt på de resulterande DeepECT-träd för ovanstående datamängder. Eftersom USPS dataset resultat är jämförbara med en av MNIST – som båda representerar handskrivna siffror-vi utelämna dessa resultat för korthet.

mnist resultat

en närmare titt på de resulterande DeepECT-träd för mnist dataset visar några spännande egenskaper hos olika subpopulationer inom de handskrivna siffrorna. Två illustrativa exempel visas i Fig. 6 och kan hittas i den vanliga och förstärkta förlängningen av DeepECT. Nodrenheten hos de avbildade underträden för siffran 7 ‘ är 98% och innehåller nästan alla instanser av denna klass. Den innehåller två bladnoder. En bladnod visar sjuor med en liten tvärstång som den vanligtvis skrivs i Europa, den andra bladnoden visar denna siffra som den oftare skrivs i USA. Det andra underträdet innehåller nästan alla instanser av siffran ‘2’ med en renhet på 97%. Detta underträd innehåller också två bladnoder, var och en med specifika egenskaper. Den första bladnoden innehåller instanser som är mer lockiga och har en distinkt slinga längst ner. Den andra bladnoden innehåller en mer’ strömlinjeformad ‘version av denna siffra, som ser ut som karaktären’ Z. ‘ De visade underträden bygger en naturlig hierarki för respektive siffra, och man kan lätt föreställa sig att dessa resultat kan vara av intresse för en forskare. Annan form beroende grupperingar av siffror kan också hittas i nedre delar av trädet, till exempel, de skriftliga versionerna av siffrorna ‘4’ och ‘9’ delar många egenskaper. Följaktligen kan de ofta hittas grupperade som ett underträd som endast innehåller dessa tvåsiffriga typer.

tomterna visar två extraherade underträd från intressanta subpopulationer av MNIST dataset hittades av DeepECT. Dessa är siffrorna sju (med och utan mittstång) och två (en lockig och en ‘strömlinjeformad’ version, som ser mer ut som karaktären ‘Z’). De visade siffrorna samplas slumpmässigt

Reuters resultat

Reuters dataset innehåller fyra obalanserade toppkategorier (första nivå etiketter) med följande klassfördelning: samarbeta/industri med 44%, regering/Social med 24%, marknader med 24% och ekonomi med 8%. Denna dataset förklaras mer detaljerat i . Kategorierna för varje nyhetsartikel valdes för hand och är därför till viss del subjektiva. Vidare har varje toppkategori flera ytterligare överlappande underkategorier (etiketter på andra nivå)—och underunderkategorier (etiketter på tredje nivå)-med över 96% av artiklarna som tillhör två eller flera underkategorier. Tabell 5 visar ett DeepECT-resultat för denna dataset. Vi kan se att de två första splittringarna skiljer det mesta av regeringen/Social—underträdet som börjar vid noden 3-och Markets—underträdet som börjar vid noden 5—kategorierna från de andra två kategorierna. Regeringen / det sociala underträdet skiljer sig sedan ytterligare in i ämnen i underkategorierna som sport, krig och brottslighet, inhemsk och internationell politik. Kategorin marknader skiljer sig också ytterligare åt i olika aspekter av respektive underkategorier. Till exempel är bladnoderna i de två sista raderna berörda av olika underkategorier på underkategorin råvarumarknader. Bladnoderna i mitten är mest relaterade till företag/industri och ekonomi. De är inte lika väl separerade som de andra två underträden. Men även där kan vi hitta intressanta bladnoder. Till exempel delar den sjunde bladnoden (rad) från toppen nyhetsartiklar märkta med Underkategoriernas prestanda (för företag/industri) och den ekonomiska utvecklingen (för ekonomi) och det verkar rimligt att förvänta sig relaterade ord för de två underkategorierna.

Mode-mnist resultat

diagrammet visar ett klusterträd för mode-MNIST dataset. Varje bladnod visar slumpmässigt samplade objekt som tilldelats den. Etiketterna är tolkningar av författarna. De färgade områdena markerar de tre dominerande underträden som representerar tre typer av föremål som finns i datasetet: väskor, kläder och skor

Mode-MNISTEN innehåller tio olika klasser av kläder, skor och väskor, nämligen T-shirt/topp, byxor, pullover, klänning, kappa, sandal, skjorta, sneaker, väska och fotkängor. Ett resulterande klusterträd av vår metod visas i Fig. 7. Bladnoderna representeras som slumpmässigt samplade objekt som tilldelats den. Etiketterna för varje nod är vår tolkning baserad på de objekt som tilldelats respektive nod. Vi kan se att DeepECT hittade en helt naturlig hierarki inom denna dataset. Först är bilderna uppdelade i tre kategorier: kläder, skor och väskor. Vi markerade dessa underträd med färgade områden. Inom varje underträd kan vi hitta naturliga hierarkier. Kategorin påsar skiljer mellan påsar utan synlig rem/handtag, påsar med små handtag och påsar med axelrem. Marksanningen skiljer inte mellan dessa typer av påsar och tilldelar dem alla till samma klass. Klädkategorin delas först in i byxor och kläder för överkroppen. Dessa delas sedan igen i korta och långa ärmar. Här måste hylsans längd ses i förhållande till den totala längden på respektive plagg eftersom varje objekt normaliseras för att visas av samma storlek i bilden, dvs., klänningar och skjortor verkar vara av samma storlek. Skokategorin visar också några intressanta egenskaper. Först utmärks mindre och större skor. De mindre skorna delas sedan vidare i sandaler och sneakers. De större skorna har antingen en platt sula, en liten häl eller är högklackade. Att bygga hierarkin baserat på dessa funktioner går mot marken sanningsklasser av sneakers, sandaler och fotkängor. Ändå är det—ur ett utseendeperspektiv-en giltig och informativ hierarki för skor.

tillämplighet för Prediktionsuppgifter på MNIST

vi utvärderar också DeepECT i en prediktionsuppgift. Därmed behåller vi autoencodersna och klusteroptimeringsproceduren som beskrivits ovan. I motsats till den experimentella utvärderingen ovan använder vi bara de första 50.000-proverna (träningsuppsättningen) av dataset MNIST under klusterträdoptimeringen. Efter optimering utvärderar vi klusterträdets klusterprestanda på de tidigare osynliga, återstående 20.000-datapunkterna (testuppsättning).

i detta experiment får vi för testet en dendrogramrenhet på \(0.73 \ pm 0.08\) och en bladrenhet på \(0.85\pm 0.06\), vilket är en liten droppe jämfört med värdena i Tabell 2. Resultatet är dock tillräckligt robust för att möjliggöra begränsade etikettförutsägelser av tidigare osynliga datapunkter direkt av klusterträdet. Men i de flesta fall skulle vi träna en klassificerare baserat på de funna klusterstrukturerna. Detsamma gäller för själva inbäddningen, där vi till exempel kan använda den övervakade autoencoderförlusten för att förbättra den funna inbäddningen.

Experiments Summary

Sammanfattningsvis tror vi att de visade experimenten på fyra verkliga dataset visar tydligt nyttan och effektiviteten hos DeepECT-klusterträdet. Att hitta denna typ av strukturer och välja detaljnivå som ska analyseras gör DeepECT till en värdefull metod för datavetenskapare.