DeepECT: de Deep Embedded Cluster Tree

we evalueren onze voorgestelde methode DeepECT op vier veelgebruikte deep learning datasets: MNIST, USPS, Fashion-MNIST en Reuters. Tabel 1 toont de statistieken van alle datasets die in de experimenten worden gebruikt. MNIST en USPS zijn beide image datasets met handgeschreven cijfers. De Fashion-MNIST dataset bevat afbeeldingen van modeproducten, zoals afbeeldingen van kleding, schoenen en tassen. De dataset van Reuters bevat nieuwsartikelen in vier topcategorieën, en we gebruiken dezelfde representatie als beschreven in .

experimentele opstelling

we richten onze experimenten op de evaluatie van onze nieuwe clusterlaag. Daarom onthouden we ons van het gebruik van meer uitgewerkte auto-encoder architecturen. In plaats daarvan gebruiken we dezelfde algemene volledig aangesloten auto-encoder lay-out voor alle experimenten, zoals gebruikt in . Zoals eerder vermeld, verwachten we dat alle methoden in gelijke mate zouden profiteren van meer geavanceerde en domeinspecifieke architecturen. Een standaard Auto-encoderarchitect is echter voldoende om de levensvatbaarheid van DeepECT ten opzichte van de baseline-concurrenten aan te tonen. Daarom gebruiken we dezelfde generieke auto-encoder architectuur, zoals voorgesteld in en die ook gebruikt in voor het doel van het clusteren van de ingebedde ruimte. De feedforward encoder in deze architectuur heeft de dimensies d-500–500–2000–10, en het decodernetwerk heeft een gespiegelde lay-out. We gebruiken ReLU-activeringen en het gemiddelde kwadraat foutreconstructie verlies van Eq. (1).

we trainen tien auto-encoders voor elke dataset en gebruiken dezelfde voorgetrainde netwerken voor alle experimenten en vergelijkingsmethoden. Het gebruik van deze voorgetrainde auto-encoders zorgt ervoor dat elke methode dezelfde startvoorwaarden heeft voor de ingebedde ruimte en dat variaties in de clustering kwaliteit niet alleen voortkomen uit kwalitatief verschillende auto-encoders. De pre-training setup is vergelijkbaar met die beschreven in . We pre-trainen de auto-encoders als het denoiseren van auto-encoders met een corruptiepercentage van 20%. Eerst voeren we een laag-wise pre-training uit met uitval na elke laag (met een percentage van 20%) en 20.000 stappen per laag. Daarna verfijnen we het hele netwerk voor 50.000 stappen zonder uitval. We gebruiken inputcorruptie alleen voor de pre-training en niet voor de daadwerkelijke optimalisatie van DeepECT en zijn baseline methoden. Voor alle experimenten gebruiken we Adam (leren \({\hbox {rate}}=0.0001\), \(\beta _1 = 0.9, \ beta _2=0.999\)) als het optimalisatiealgoritme en een mini-batchgrootte van 256 monsters. Voor de gecombineerde optimalisatie trainen we voor extra 50.000 iteraties om convergentie te garanderen.

voor DeepECT toonden onze eerste experimenten met synthetische gegevens aan dat het splitsen van de boom om de 500 optimalisatiestappen veelbelovende resultaten oplevert en dat meer uitgebreide stapgroottes de prestaties niet verder verbeterden. Om deze reden houden we dit schema bij zonder het aan te passen voor de experimenten met real-world datasets. Hetzelfde geldt voor de in de sekte genoemde snoeidrempel. 2.7. Voor MNIST, Fashion-MNIST, en USPS, we laten de bomen groeien tot ze twintig bladknopen bevatten. Voor de dataset van Reuters stellen we het maximale aantal bladknopen in op twaalf omdat het minder ground truth clusters heeft. Op deze manier hebben we twee keer en drie keer het werkelijke aantal clusters. We beschouwen deze waarden als voldoende om essentiële structuren van de geselecteerde datasets vast te leggen voor het doel van dit artikel. We gebruiken hetzelfde aantal bladknopen voor de hiërarchische basislijnmethoden.

de plots tonen een voorbeeld van originele MNIST cijfers en een willekeurig vergrote versie

voor de image datasets, we bovendien geëxperimenteerd met de augmentation extension DeepECT + Aug. We beginnen met dezelfde voorgetrainde auto-coders als in de andere experimenten. Verder houden we ons aan hetzelfde optimalisatieschema als hierboven beschreven voor de experimenten met de niet-augmented versies van DeepECT. In elke iteratie gebruiken we de originele mini-batch en de toegevoegde tegenhanger om de verliesfunctie in Eq te optimaliseren. 9, in plaats van het niet-vergrote verlies in Eq. 6. We creëren de vergrote versie van elk beeld van een mini-batch, door on-the-fly een willekeurige affiene transformatie toe te passen. De affiene transformatie draait willekeurig en scheert het beeld in het bereik van \ ( \ ) graden. Ook, het beweegt het cijfer willekeurig tot twee pixels in elke richting. Figuur 5 toont een voorbeeld van deze vergroting voor MNIST.

evaluatiemethoden

we evalueren de clusterhiërarchie van DeepECT met de dendrogram purity (DP) en leaf purity (LP) maat. We beschrijven beide hieronder. Verder evalueren we de cluster boom tegen vlakke basislijn methoden. Hiervoor gebruiken we de bekende normalized mutual information (NMI) en clustering accuracy (ACC) . We nemen deze op voor volledigheid en om aan te tonen dat DeepECT ook competitief is in scenario ‘ s, waar men een platte clusterstructuur verwacht en het werkelijke aantal clusters in dataset kent. Om een K-clusterpartitie van een clusterboom te bepalen, gebruiken we de toewijzingen aan de k-knooppunten die na de eerste \(k-1\) splitsingen bladknopen waren.

dendrogram zuiverheid

de dendrogram zuiverheid maat kan worden gebruikt om de cluster boom tegen een vlakke grond waarheid partitie te evalueren. Het is de verwachte zuiverheid van de subboom die wordt gegeven door de kleinste gemeenschappelijke voorouderknoop voor twee willekeurig bemonsterde gegevenspunten van dezelfde klasse. Het is 1.0 dan en slechts dan als alle datapunten die tot één klasse in de ground truth behoren zijn toegewezen aan een zuivere subboom, en het nadert 0 voor willekeurig gegenereerde bomen.

de expliciete formule wordt gedefinieerd in als:

waar \(C_1, \dots , C_K\) zijn de gegevens van punt overeenstemmen met de grond waarheid klassen, \({\text {lca}}(x,y)\) is het kleinste gemeenschappelijke voorouder knooppunt van x en y in de cluster boom \({\text {dan}}(z)\) is de verzameling van data punten toegewezen aan het knooppunt z in het cluster boom \({\text {pur}}(S,T) = |S \kap T| / | S|\) is de zuiverheid meten, en \({\mathcal {P}} = \{(x,y) \mid \exists C \in \{C_1, \dots , C_K\}: x,y \in C \wedge x \ne y\}\) is de verzameling van alle gegevenspaarparen die tot dezelfde klasse behoren. De zuiverheid van het dendrogram kan efficiënt en nauwkeurig worden berekend in een bottom-up recursie op de clusterboom.

Bladzuiverheid

naast het gebruik van dendrogram-zuiverheid introduceren we een andere maat die we bladzuiverheid (LP) noemen. Het is de gewogen gemiddelde zuiverheid van de bladknopen w. r. t. tot de meerderheid klasse van de objecten toegewezen aan een bladknoop, gegeven door de formule:

waarin \({{\mathcal {L}}} _{{\mathcal {D}}}\) de verzameling van Verzamelingen is die de gegevenspunten bevatten die aan de bladknopen zijn toegewezen.

Hoogteafhankelijkheid van Zuiverheidsmaten

vergelijking van dendrogram en bladzuiverheid van twee clusterbomen is alleen direct mogelijk als beide bomen hetzelfde aantal bladknopen hebben. Echter, sub-bomen kunnen altijd worden ingeklapt in bladknopen om aan deze eis te voldoen. Daarom sluiten we de bottom-up koppeling-bomen van de basislijn methoden—in de volgorde van koppeling—door het comprimeren van sub-bomen in bladknopen totdat we hetzelfde aantal samenvoeging stappen links als split-knooppunten in de top-down bomen van DeepECT en Bisecting-K-middelen. Dit proces zorgt ervoor dat beide methoden vergelijkbaar zijn met de hiërarchische evaluatiemaatstaven.

hiërarchische Clustering basislijnen

als basis voor het evalueren van de hiërarchische eigenschappen, clusteren we de ingebedde gegevens met de klassieke hiërarchische clustering algoritmen bisecting-k-means (AE + Bisecting), single-linkage (AE + Single), en complete-linkage (AE + Complete). Aangezien geen van deze klassieke algoritmen de ingebedde ruimte kan optimaliseren, verkennen we ook het eenvoudige idee van het combineren van de flat embedded clustering algoritme IDEC met single-linkage en complete-linkage. IDEC is een methode die de clustering laag van DEC combineert met het reconstructie verlies van de auto-encoder. Eerst draaien we IDEC met het aantal clusters ingesteld op een waarde hoger dan het verwachte aantal clusters—in ons geval stellen we het gelijk aan het maximale aantal bladknopen die we gebruiken voor DeepECT. Vervolgens beschouwen we deze IDEC-clustercentra als vertegenwoordigers van de toegewezen datapunten en proberen we een hiërarchische clusterstructuur te herstellen door single-linkage en complete-linkage uit te voeren op de clustercentra (IDEC + Single en IDEC + Complete). Een soortgelijke techniek wordt voorgesteld voor klassieke, niet-ingebedde instellingen met k-middelen in plaats van IDEC.

basislijnen voor vlakke Clustering

als basis voor het evalueren van de prestaties van DeepECT in een vlakke clustering, gebruiken we k-middelen op de ingebedde gegevens van de vooraf getrainde auto-encoder (ae+k-middelen) en IDEC . Als we de voordelen van meer domein-specifieke en geavanceerde auto-encoder architecturen negeren, is IDEC momenteel een van de beste embedded-clustering methoden. In tegenstelling tot DeepECT, moeten we het werkelijke aantal clusters in de ground truth instellen tijdens optimalisatie voor IDEC en k-means. Verder zetten we de hyperparameter van IDEC voor het reconstructie verlies op 0,1 zoals beschreven in .

Algemene resultaten

de algemene resultaten—gemiddeld over de tien voorgetrainde auto-encoders—voor de hiërarchische evaluatie met behulp van dendrogram-zuiverheids-en bladzuiverheidsmaten voor DeepECT en de hiërarchische basisalgoritmen zijn weergegeven in Tabel 2. DeepECT produceert consequent clusterbomen van hoge kwaliteit en is het best presterende algoritme met een brede marge. We kunnen ook zien dat de uitbreiding van de augmentatie verder verbetert de resultaten aanzienlijk voor MNIST en USPS. De resultaten van DeepECT met en zonder de augmentatie extensie voor de Fashion-MNIST dataset zijn vergelijkbaar omdat de dataset auteurs ervoor kozen om alle afbeeldingen vooraf te verwerken, zodat elk fashion item een genormaliseerde representatie heeft. De resultaten van de klassieke methoden kunnen worden verklaard door hun onvermogen om de inbedding te verbeteren. De bladzuiverheidswaarden voor DeepECT geven aan dat de methode homogene subpopulaties kan creëren. Als we de bladzuiverheidswaarden van DeepECT en de hiërarchische IDEC + Center-linkage varianten vergelijken met de bladzuiverheidswaarden van de andere basislijnen, kunnen we zien dat de gecombineerde optimalisatie van de clustering en auto—encoder—van beide methoden-inderdaad de homogeniteit van lokale structuren verbetert. Echter, de IDEC + Center-linkage is ook niet in staat om een coherente hiërarchische structuur te extraheren.

Tabel 3 toont de experimentele resultaten voor de platte clustering vergelijking methoden gebaseerd op dezelfde voorgetrainde auto-encoders. Omdat we dezelfde voorgetrainde auto-encoders gebruiken, kunnen we direct de invloed van de respectievelijke clustering doelstelling zien. Zowel IDEC als DeepECT profiteren van de gecombineerde optimalisatie in vergelijking met k-means, die de inbedding niet kunnen optimaliseren. Tabel 4 toont de resultaten van meer centroid-gebaseerde clustering methoden uit de respectieve publicatie. Meer details over deze methoden zijn te vinden in sekte. 4. We kunnen zien dat DeepECT ook goed presteert in vergelijking met deze methoden. We kunnen echter ook zien dat de autoencoder architectuur het clustering resultaat aanzienlijk beïnvloedt. Bijvoorbeeld, DBC verschilt van DEC alleen door het gebruik van een convolutionele auto-encoder, maar bereikt superieure resultaten. Toch is de geselecteerde autoencoder-architectuur onafhankelijk van de geselecteerde clusterlaag.

natuurlijk is deze vergelijking van platte clustering doelstellingen en DeepECT oneerlijk ten opzichte van deze laatste, omdat de concurrerende methoden het werkelijke aantal clusters tijdens de optimalisatie wordt gegeven, terwijl voor DeepECT deze informatie alleen tijdens de evaluatie wordt gebruikt. Niettemin, kunnen we zien dat de gewone versie van DeepECT kan bijhouden met deze methoden in termen van ruwe NMI en ACC maatregelen en dat de augmentatie extensie DeepECT + Aug toont aanzienlijke verbeteringen ten opzichte van de resultaten van DeepECT, omdat het bekende invarianties binnen de gegevens kan negeren. Deze resultaten tonen aan dat DeepECT ook concurrerend is in scenario ‘ s, waar men een platte clusterstructuur verwacht, maar het aantal clusters niet kent en de clusterboom recursief inspecteert.

gedetailleerde evaluatie

in deze sectie nemen we een nadere blik op de resulterende DeepECT-bomen voor de bovenstaande datasets. Aangezien de bevindingen van de USPS-dataset vergelijkbaar zijn met die van MNIST—aangezien beide handgeschreven cijfers vertegenwoordigen—laten we deze resultaten voor beknoptheid weg.

MNIST resultaten

een nadere blik op de resulterende DeepECT-bomen voor de MNIST-dataset toont enkele opwindende eigenschappen van verschillende subpopulaties binnen de handgeschreven cijfers. Twee illustratieve voorbeelden zijn weergegeven in Fig. 6 en kan worden gevonden in de gewone en uitgebreide uitbreiding van DeepECT. De node zuiverheid van de afgebeelde subbomen voor het cijfer 7′ is 98% en bevat bijna alle exemplaren van deze klasse. Het bevat twee bladknopen. Een bladknoop toont zevens met een kleine dwarsbalk zoals het gewoonlijk in Europa wordt geschreven, de andere bladknoop toont dit cijfer zoals het vaker in de VS wordt geschreven. De tweede subboom bevat bijna alle exemplaren van het cijfer ‘2’ met een zuiverheid van 97%. Deze subboom bevat ook twee bladknopen, elk met specifieke kenmerken. De eerste bladknoop bevat instanties die meer krullend zijn en een kenmerkende lus aan de onderkant hebben. De tweede bladknoop bevat een meer ‘gestroomlijnde’ versie van dit cijfer, die eruit ziet als het teken ‘Z.’ De getoonde subbomen bouwen een natuurlijke hiërarchie voor het betreffende cijfer, en je kunt je gemakkelijk voorstellen dat deze bevindingen van belang kunnen zijn voor een onderzoeker. Andere vormen afhankelijk groepen van cijfers kunnen ook worden gevonden in lagere delen van de boom, bijvoorbeeld, de geschreven versies van de cijfers ‘4’ en ‘9’ delen vele kenmerken. Daarom kunnen ze vaak worden gevonden gegroepeerd als een subboom die alleen deze twee cijfertypen bevat.

de percelen tonen twee geëxtraheerde sub-bomen uit interessante subpopulaties van de MNIST dataset gevonden door DeepECT. Dit zijn de cijfers zeven (met en zonder middelste dwarsbalk) en twee (een krullende en een ‘gestroomlijnde’ versie, die meer op het teken ‘Z’lijkt). De getoonde cijfers worden willekeurig bemonsterd

Reuters resultaten

de dataset van Reuters bevat vier onevenwichtige topcategorieën (labels van het eerste niveau) met de volgende klassenverdeling: samenwerking/industrie met 44%, overheid/sociale met 24%, markten met 24% en economie met 8%. Deze dataset wordt in meer detail uitgelegd in . De categorieën voor elk nieuwsartikel werden met de hand gekozen en zijn daarom tot op zekere hoogte subjectief. Verder heeft elke topcategorie verschillende extra overlappende subcategorieën (labels van het tweede niveau)-en sub—subcategorieën (labels van het derde niveau)-waarbij meer dan 96% van de artikelen tot twee of meer subcategorieën behoren. Tabel 5 toont een DeepECT resultaat voor deze dataset. We kunnen zien dat de eerste twee splits het grootste deel van de overheid/sociale—sub-boom te scheiden vanaf het knooppunt 3—en markten—sub-boom te beginnen bij het knooppunt 5—categorieën van de andere twee categorieën. De overheid / sociale subboom onderscheidt zich vervolgens verder in onderwerpen van de subcategorieën zoals sport, oorlog en misdaad, binnenlandse en internationale politiek. De categorie markten onderscheidt zich ook verder in verschillende aspecten van de respectieve subcategorieën. De bladknopen in de laatste twee rijen hebben bijvoorbeeld betrekking op verschillende sub-subcategorieën van de subcategorie grondstoffenmarkten. De bladknopen in het midden zijn meestal gerelateerd aan Corporate/Industrial en Economics. Ze zijn niet zo goed gescheiden als de andere twee subbomen. Maar zelfs daar kunnen we interessante bladknopen vinden. Bijvoorbeeld, de zevende bladknoop (rij) van de top aandelen nieuwsartikelen gelabeld met de sub-categorieën prestaties (van Corporate/Industrial) en de economische prestaties (van de economie) en het lijkt redelijk om verwante woorden te verwachten voor die twee sub-sub-categorieën.

Mode-MNIST resultaten

het diagram toont een clusterboom voor de Fashion-MNIST dataset. Elk bladknooppunt toont willekeurig gesamplede objecten toegewezen aan het. De labels zijn interpretaties door de auteurs. De gekleurde gebieden benadrukken de drie dominante subbomen die drie soorten objecten vertegenwoordigen die in de dataset worden gevonden: tassen, kleding en schoenen

de Fashion-MNIST bevat tien verschillende klassen van kleding, schoenen en tassen, namelijk T-shirt/top, broek, pullover, jurk, jas, sandaal, shirt, sneaker, tas, en enkellaars. Een resulterende cluster boom van onze methode is weergegeven in Fig. 7. De bladknopen worden weergegeven als willekeurig gesamplede objecten die eraan zijn toegewezen. De labels van elk knooppunt zijn onze interpretatie gebaseerd op de objecten die aan het betreffende knooppunt zijn toegewezen. We kunnen zien dat DeepECT een volledig natuurlijk ogende hiërarchie vond binnen deze dataset. Ten eerste zijn de afbeeldingen opgesplitst in drie categorieën: kleding, schoenen en tassen. We hebben deze subbomen gemarkeerd met gekleurde gebieden. Binnen elke subboom kunnen we natuurlijke hiërarchieën vinden. De categorie Tassen maakt onderscheid tussen tassen zonder zichtbare riem/handvat, tassen met kleine handvatten en tassen met schouderband. De ground truth maakt geen onderscheid tussen deze soorten tassen en wijst ze allemaal toe aan dezelfde klasse. De kledingcategorie wordt eerst onderverdeeld in broeken en kleding voor het bovenlichaam. Deze zijn dan weer verdeeld in korte en lange mouwen. Hier moet de lengte van de mouw worden gezien ten opzichte van de totale lengte van het betreffende kledingstuk, omdat elk item is genormaliseerd om te verschijnen van dezelfde grootte binnen de afbeelding, d.w.z. jurken en overhemden lijken van dezelfde grootte te zijn. De schoencategorie vertoont ook enkele interessante kenmerken. Ten eerste worden kleinere en grotere schoenen onderscheiden. De kleinere schoenen worden dan verder verdeeld in sandalen en sneakers. De grotere schoenen hebben ofwel een platte zool, een kleine hak, of zijn hoge hakken. Het bouwen van de hiërarchie op basis van deze functies loopt tegen de grond waarheid klassen van sneakers, sandalen en enkellaarzen. Niettemin is het—vanuit een uiterlijk perspectief-een geldige en informatieve hiërarchie voor schoenen.

toepasbaarheid voor Voorspellingstaken op MNIST

we evalueren ook DeepECT in een voorspellingstaak. Daarbij houden we de auto-encoders en de clustering optimalisatie procedure zoals hierboven beschreven. In tegenstelling tot de experimentele evaluatie hierboven, gebruiken we alleen de eerste 50.000 samples (trainingsset) van de dataset MNIST tijdens de cluster tree optimalisatie. Na optimalisatie evalueren we de clustering prestaties van de cluster boom op de eerder ongeziene, resterende 20.000 datapunten (test set).

in dit experiment krijgen we voor de testset een dendrogram zuiverheid van \(0.73 \ pm 0,08\) en een bladzuiverheid van \(0,85\pm 0,06\), wat een lichte daling is ten opzichte van de waarden in Tabel 2. Toch is het resultaat robuust genoeg om beperkte labelvoorspellingen mogelijk te maken van eerder ongeziene datapunten direct door de clusterboom. In de meeste gevallen zouden we echter een classifier trainen op basis van de gevonden clusterstructuren. Hetzelfde geldt voor de inbedding zelf, waar we gebruik kunnen maken van, bijvoorbeeld, de bewaakte autoencoder verlies om de gevonden inbedding te verbeteren.

experimenten samenvatting

samenvattend denken we dat de getoonde experimenten op vier datasets in de echte wereld duidelijk het nut en de effectiviteit van de DeepECT cluster tree laten zien. Het vinden van dit soort structuren en het selecteren van het te analyseren detailniveau maken DeepECT een waardevolle methode voor gegevenswetenschappers.