DeepECT: the Deep Embedded Cluster Tree

arvioimme ehdotettua menetelmää DeepECT neljään yleisesti käytettyyn syväoppimisen aineistoon: MNIST, USPS, Fashion-MNIST ja Reuters. Taulukossa 1 esitetään tilastot kaikista kokeissa käytetyistä aineistoista. MNIST ja USPS ovat molemmat kuvatiedostoja, jotka sisältävät käsinkirjoitettuja numeroita. Fashion-MNIST-aineisto sisältää kuvia muotituotteista, kuten kuvia vaatteista, kengistä ja laukuista. Reutersin aineisto sisältää uutisartikkeleita neljässä ylimmässä kategoriassa ,ja käytämme samaa edustusta kuin on kuvattu.

kokeelliset Asetukset

keskitämme kokeemme uuden ryhmittelykerroksen arviointiin. Siksi emme käytä kehittyneempiä autoencoder-arkkitehtuureja. Sen sijaan käytämme samaa yleistä täysin kytketty autoencoder layout kaikille kokeille, jota käytetään . Kuten edellä mainittiin, odotamme, että kaikki menetelmät hyötyisivät yhtä paljon kehittyneemmistä ja toimialakohtaisista arkkitehtuureista. Vakioautokooderiarkkitehtuuri riittää kuitenkin osoittamaan Deepectin elinkelpoisuuden verrattuna peruskilpailijoihin. Näin ollen käytämme samaa yleistä autencoder-arkkitehtuuria, kuten on ehdotettu ja jota käytetään myös sulautetun tilan ryhmittelyyn. Tässä arkkitehtuurissa feedforward-kooderilla on mitat d-500–500–2000–10, ja dekooderin verkko on peilattu asettelu. Käytämme ReLU aktivoinnit ja keskimääräinen potenssiin virhe rekonstruktio tappio taajuuskorjain. (1).

me esikoulutamme kymmenen automaattikoodaajaa kutakin aineistoa varten ja käytämme näitä samoja ennalta koulutettuja verkkoja kaikissa kokeissa ja vertailumenetelmissä. Näiden esikoulutettujen automaattisovittimien avulla varmistetaan, että jokaisella menetelmällä on samat lähtöolosuhteet sulautetulle tilalle ja että ryhmittelyn laadun vaihtelut eivät johdu pelkästään laadullisesti erilaisista automaattisovittimista. Pre-training setup on samanlainen kuin kuvattu . Autokoodaajat on koulutettu 20 prosentin korruptioprosentilla. Ensimmäinen, suoritamme kerros-viisas esikoulutuksen keskeyttämällä jokaisen kerroksen jälkeen (nopeudella 20%) ja 20,000 askelta per kerros. Sitten hienosäädämme koko verkoston 50 000 askelta ilman keskeyttämistä. Käytämme syöttökorruptiota vain esikasvatukseen, emme Deepectin ja sen perusmenetelmien varsinaiseen optimointiin. Kaikissa kokeissa käytämme Adamia (learning \({\hbox {rate}}=0.0001\), \(\beta _1=0.9, \beta _2=0.999\)) optimointialgoritmina ja 256 näytteen minieräkokona. Yhdistettyä optimointia varten harjoittelemme vielä 50 000 iteraatiota lähentymisen varmistamiseksi.

deepectin osalta ensimmäiset kokeet synteettisillä tiedoilla osoittivat, että puun halkaisu 500 optimointivaiheen välein tuottaa lupaavia tuloksia, eivätkä pidemmät askelkoot lisänneet suorituskykyä entisestään. Tästä syystä pidämme tätä aikataulua säätämättä sitä reaalimaailman aineistojen kokeiluja varten. Sama koskee lahkossa mainittua karsimiskynnystä. 2.7. Mnistille, Fashion-MNISTILLE ja USPS: lle kasvatamme puita, kunnes niissä on kaksikymmentä lehtisolmua. Asetimme Reutersin aineistossa lehtisolmujen maksimimääräksi kaksitoista, koska siinä on vähemmän maatotuusklustereita. Näin meillä on kaksi kertaa ja kolme kertaa todellinen määrä klustereita. Pidämme näitä arvoja riittävinä kuvaamaan valittujen aineistojen olennaisia rakenteita tätä paperia varten. Käytämme samaa määrää lehtiä solmuja hierarkkisiin perustason menetelmiin.

tontit näyttävät otoksen alkuperäisistä mnist-numeroista ja satunnaisesti lisätyn version

kuvatiedostojen osalta kokeilimme lisäksi augmentation-laajennusta DeepECT + Aug. Aloitamme samoilla ennalta koulutetuilla automaattikoodaajilla kuin muissakin kokeissa. Lisäksi pidämme kiinni samasta optimointiaikataulusta kuin edellä on kuvattu Deepectin ei-lisätyillä versioilla tehdyissä kokeissa. Jokaisessa iteraatiossa käytämme alkuperäistä mini-erää ja sen täydennettyä vastinetta optimoidaksemme Häviöfunktion Eq: ssa. 9, Sen sijaan ei-augmented menetys Eq. 6. Luomme laajennetun version jokaisesta minierän kuvasta soveltamalla lennossa satunnaista affiinimuunnosta. Affiinimuunnos pyörii satunnaisesti ja leikkaa kuvan välillä \ ( \ ) astetta. Lisäksi se siirtää numeroa satunnaisesti jopa kahteen pikseliin mihin suuntaan tahansa. Kuvassa 5 on esimerkki tästä lisäyksestä MNIST: lle.

arviointimenetelmät

arvioimme deepectin klusterihierarkiaa dendrogram purity (dp) – ja leaf purity (LP) – mittarilla. Kuvailemme molempia alla. Edelleen, arvioimme klusterin puu verrattuna Tasainen perustaso menetelmiä. Tähän käytämme tunnettuja normalisoituja keskinäisiä tietoja (NMI) ja clustering accuracy (ACC). Sisällytämme ne kattavuuden vuoksi ja osoittaaksemme, että DeepECT on kilpailukykyinen myös skenaarioissa, joissa odotetaan tasaista klusterirakennetta ja tiedetään klusterien todellinen määrä aineistossa. Määrittääksemme k-klusteriosion klusteripuusta käytämme tehtäviä k-solmuille, jotka olivat lehtisolmuja ensimmäisen \(k-1\) – jaottelun jälkeen.

Dendrogramin puhtaus

dendrogramin puhtausmittarilla voidaan arvioida klusteripuuta tasamaista totuusosiota vastaan. Se on alapuun odotettu puhtaus, jonka vähiten yhteinen esi-isäsolmu antaa kahdelle satunnaisesti otetulle saman luokan datapisteelle. Se on 1.0 jos ja vain jos kaikki maatotuuden yhteen luokkaan kuuluvat datapisteet on osoitettu jollekin puhtaalle alapuulle, ja se lähestyy arvoa 0 satunnaisesti luoduille puille.

eksplisiittinen kaava määritellään seuraavasti:

missä \(C_1, \dots, C_K\) ovat maanpinnan totuusluokkia vastaavat datapistejoukot, \({\text {lca}} (x, y)\) on klusteripuun X: n ja y: n pienin yhteinen esi-isäsolmu, \({\text {dan}}(z)\) on klusteripuun solmulle z osoitettujen tietopisteiden joukko, \({\text {pur}}(S,T) = |S \cap T| / | S|\) on puhtausmitta, ja \({\mathcal {P}} = \{(x, y) \mid \exists C \in \{C_1, \dots , C_K\}: x,y \in C \wedge x \ne y\}\) on kaikkien samaan luokkaan kuuluvien datapisteparien joukko. Dendrogramin puhtaus voidaan laskea tehokkaasti ja tarkasti klusteripuun alhaalta ylöspäin suuntautuvassa rekursiossa.

lehtien puhtaus

dendrogram-puhtauden lisäksi otetaan käyttöön toinen Mitta, jota kutsumme lehtien puhtaudeksi (LP). Se on lehtisolmujen w.r.t. painotettu keskimääräinen puhtaus lehtisolmulle osoitettujen objektien enemmistöluokalle, joka saadaan kaavalla:

missä \({{\mathcal {L}}} _{{\mathcal {D}}}\) on joukko, joka sisältää lehtisolmuille osoitetut datapisteet.

puiden Korkeusriippuvuus Puhtausmittareista

kahden klusteripuun dendrogramin ja lehtien puhtauden vertailu on suoraan mahdollista vain, jos molemmissa puissa on sama määrä lehtisolmuja. Alapuita voidaan kuitenkin aina romahduttaa lehtisolmuiksi tämän vaatimuksen täyttämiseksi. Siksi romahdamme perustason menetelmien alapuut-linkkausjärjestyksessä-puristamalla alapuut lehtisolmuiksi, kunnes meillä on jäljellä sama määrä yhdistämisvaiheita kuin deepect-ja Bisecting-k-means-yläpuolisten puiden split-solmut. Tämä prosessi varmistaa, että molemmat menetelmät ovat vertailukelpoisia hierarkkisten arviointitoimenpiteiden kanssa.

hierarkkisen ryhmittelyn Perustaso

hierarkkisten ominaisuuksien arviointiperustana yhdistämme sulautetut tiedot klassisiin hierarkkisiin ryhmittelyalgoritmeihin bisecting-k-means (AE + Bisecting), single-linkage (AE + Single) ja complete-linkage (AE + Complete). Koska mikään näistä klassisista algoritmeista ei voi optimoida sulautettua tilaa, tutkimme myös yksinkertaista ajatusta yhdistää Tasainen sulautettu ryhmittelyalgoritmi IDEC yhden linkin ja täydellisen linkityksen kanssa. IDEC on menetelmä, joka yhdistää DEC: n ryhmittelykerroksen ja autokooderin rekonstruktiohäviön. Ensin suoritamme IDEC—testin, jossa klusterien määrä asetetaan oletettua klusterien määrää suurempaan arvoon-meidän tapauksessamme asetamme sen Deepectille käyttämiemme lehtisolmujen enimmäismäärän suuruiseksi. Sitten pidämme näitä IDEC-klusterikeskuksia osoitettujen datapisteiden edustajina ja yritämme palauttaa hierarkkisen klusterirakenteen suorittamalla yhden linkityksen ja täydellisen linkityksen klusterikeskuksiin (IDEC + Single ja IDEC + Complete). Vastaavaa tekniikkaa on ehdotettu klassisille, ei-upotetuille asetuksille, joissa on IDEC: n sijaan k-keinot.

Flat Clustering Baselines

pohjana Deepectin suorituskyvyn arvioimiseksi tasaisella ryhmittelyasetuksella käytämme k-keinoja esikoulutetun autokooderin (ae+k-means) ja IDEC: n sulautettuihin tietoihin . Jos sivuutamme domain-spesifisempien ja hienostuneempien autoencoder-arkkitehtuurien edut, IDEC on tällä hetkellä yksi parhaista sulautetuista ryhmittelymenetelmistä. Toisin kuin DeepECT, meidän täytyy asettaa todellinen määrä klustereita maahan totuus aikana optimointi IDEC ja k-means. Edelleen, asetamme hyperparametri IDEC jälleenrakennustappion 0,1 kuten on kuvattu .

yleiset tulokset

yleiset tulokset-keskiarvona kymmenestä ennalta koulutetusta automaattikoodaajasta—hierarkkisesta arvioinnista käyttäen dendrogram-puhtausmittareita ja lehtien puhtausmittareita Deepectille sekä hierarkkisia perusalgoritmeja on esitetty taulukossa 2. DeepECT tuottaa jatkuvasti korkealuokkaisia klusteripuita ja on laajalla marginaalilla menestynein algoritmi. Voimme myös nähdä, että laajennuksen laajennus parantaa edelleen huomattavasti mnistin ja USPS: n tuloksia. Tulokset DeepECT kanssa ja ilman augmentation laajennus varten Fashion-MNIST aineisto ovat samanlaisia, koska aineisto kirjoittajat päättivät esikäsitellä kaikki kuvat siten, että jokainen muoti kohde on normalisoitu edustus. Klassisten menetelmien tulokset voidaan selittää sillä, että ne eivät kykene tehostamaan embeddingiä. Deepectin lehtien puhtausarvot osoittavat, että menetelmällä pystytään luomaan homogeenisia osapopulaatioita. Jos vertaamme deepectin lehtien puhtausarvoja ja hierarkkisia IDEC + Center-linkage-variantteja muiden peruslinjojen lehtien puhtausarvoihin, voimme nähdä, että ryhmittelyn ja autokooderin—molempien menetelmien—yhdistetty optimointi todellakin parantaa paikallisten rakenteiden homogeenisuutta. IDEC + Center-linkage ei kuitenkaan myöskään pysty irrottamaan yhtenäistä hierarkkista rakennetta.

taulukossa 3 esitetään samoihin ennalta koulutettuihin autokoodereihin perustuvien tasoklusterointimenetelmien kokeelliset tulokset. Koska käytämme samoja ennalta koulutettuja automaattikoodaajia, voimme nähdä suoraan kunkin ryhmittelytavoitteen vaikutuksen. Sekä IDEC että DeepECT hyötyvät yhdistetystä optimoinnista verrattuna k-keinoihin, jotka eivät voi optimoida upotusta. Taulukossa 4 on esitetty centroid-pohjaisten ryhmittelymenetelmien tulokset, jotka on otettu vastaavasta julkaisusta. Tarkempia tietoja näistä menetelmistä löytyy lahkosta. 4. Voimme nähdä, että DeepECT toimii myös hyvin verrattuna näihin menetelmiin. Voimme kuitenkin myös nähdä, että autoencoder arkkitehtuuri vaikuttaa clustering tulos huomattavasti. Esimerkiksi DBC eroaa DEC: stä vain convolutionaarisen autoencoderin avulla, mutta saavuttaa parempia tuloksia. Silti valittu autencoder-arkkitehtuuri on riippumaton valitusta ryhmittelykerroksesta.

tämä tasaisten ryhmittelytavoitteiden ja Deepectin vertailu on tietysti epäreilua jälkimmäistä kohtaan, koska kilpaileville menetelmille annetaan oikea klusterien määrä optimoinnin aikana, kun taas Deepectin kohdalla käytämme tätä tietoa vain arvioinnin aikana. Kuitenkin, voimme nähdä, että tavallinen versio DeepECT voi pysyä näiden menetelmien kannalta raaka NMI ja ACC toimenpiteitä ja että augmentation laajennus DeepECT + Aug osoittaa merkittäviä parannuksia tuloksiin DeepECT, koska se voi sivuuttaa tunnettuja invariances sisällä tietoja. Tulokset osoittavat, että DeepECT on kilpailukykyinen myös skenaarioissa, joissa odotetaan tasaista klusterirakennetta, mutta ei tiedetä klusterien määrää ja tutkitaan klusteripuuta rekursiivisesti.

yksityiskohtainen arviointi

tässä osiossa tarkastellaan tarkemmin edellä mainittujen aineistojen tuloksena syntyneitä Syväpuita. Koska USPS-aineiston havainnot ovat verrattavissa mnist-aineistoon-koska molemmat edustavat käsin kirjoitettuja numeroita-jätämme nämä tulokset pois lyhyyden vuoksi.

Mnist-tulokset

mnist-aineiston tuloksena syntyneiden Syväpuiden lähempi tarkastelu osoittaa käsinkirjoitettujen numeroiden sisältämien eri alapopulaatioiden jännittäviä ominaisuuksia. Kuvassa on kaksi havainnollista esimerkkiä. 6 ja löytyy tavallinen ja lisätty laajennus DeepECT. Kuvattujen osapuiden solmupuhtaus numerolla 7′ on 98%, ja se sisältää lähes kaikki tämän luokan esiintymät. Siinä on kaksi lehtisolmua. Yksi lehtisolmu näyttää seiskat pienellä poikkipalkilla, koska se on yleisesti kirjoitettu Euroopassa, toinen lehtisolmu näyttää tämän numeron, koska se on yleisemmin kirjoitettu Yhdysvalloissa. Toisessa osapuussa on lähes kaikki luvut “2”, joiden puhtausaste on 97%. Tämä alapuu sisältää myös kaksi lehtisolmua, joilla kummallakin on omat erityispiirteensä. Ensimmäinen lehtisolmu sisältää tapauksia, jotka ovat enemmän kihara ja on erottuva silmukka alaosassa. Toinen lehtisolmu sisältää “virtaviivaisemman” version tästä numerosta, joka näyttää merkiltä ” Z. ” esitetyt alapuut rakentavat luonnollisen hierarkian kyseiselle numerolle, ja voidaan helposti kuvitella, että nämä havainnot voivat kiinnostaa tutkijaa. Muunlaisia numeroryhmiä löytyy myös puun alaosista, esimerkiksi numeroiden ‘4’ ja ‘9’ kirjoitetuilla versioilla on monia ominaisuuksia. Tämän vuoksi ne voidaan usein löytää ryhmiteltyinä yhteen alapuuksi, jossa on vain nämä kaksi numerotyyppiä.

palstoilla näkyy kaksi poimittua alapuuta Deepectin löytämän mnist-aineiston mielenkiintoisista alapopulaatioista. Nämä ovat numerot seitsemän (kanssa ja ilman keskellä poikkipalkin) ja kaksi (kihara ja “virtaviivainen” versio, näyttää enemmän merkki “Z”). Näytetyistä numeroista otetaan satunnaisesti näytteitä

Reutersin tulokset

Reutersin aineisto sisältää neljä epätasapainoista yläluokkaa (ensimmäisen tason merkit), joiden luokkajakauma on seuraava: yhteistyö/teollisuus 44%, hallitus/sosiaalinen 24%, markkinat 24% ja talous 8%. Tämä aineisto on selitetty tarkemmin . Kunkin uutisartikkelin Kategoriat on valittu käsin ja ne ovat siten jossain määrin subjektiivisia. Lisäksi jokaisessa ylimmässä luokassa on useita päällekkäisiä alaluokkia (toisen tason merkit) ja alaluokkia (kolmannen tason merkit), ja yli 96 prosenttia tavaroista kuuluu kahteen tai useampaan alaluokkaan. Taulukossa 5 esitetään tämän aineiston DeepECT-tulos. Voimme nähdä, että kaksi ensimmäistä jakoa erottavat suurimman osan hallituksen/sosiaalisen—osapuusta alkaen solmusta 3-ja markkinat—osapuusta alkaen solmusta 5—kategorioista kahdesta muusta luokasta. Hallitus / yhteiskunnallinen alapuu erittelee tämän jälkeen alaryhmien aiheita, kuten urheilua, sotaa ja rikollisuutta, kotimaista ja kansainvälistä politiikkaa. Markkinaluokka myös erittelee edelleen kyseisten alaluokkien eri näkökohtia. Esimerkiksi kahden viimeisen rivin lehtisolmut koskevat hyödykemarkkinoiden alaluokkien eri alaluokkia. Keskellä olevat lehtisolmut liittyvät useimmiten yritys – /teollisuus-ja taloustieteeseen. Ne eivät erotu toisistaan yhtä hyvin kuin kaksi muuta alapuuta. Silti sieltäkin löytyy kiinnostavia lehtisolmuja. Esimerkiksi seitsemännen lehden solmu (rivi) ylhäältä jakaa uutisia merkitty alaluokkien suorituskyky (yritysten/teollisuuden) ja taloudellinen suorituskyky (taloustieteen) ja se näyttää järkevältä odottaa Liittyvät sanat näiden kahden alaluokkien.

Muoti-Mnist tulokset

kaavio näyttää klusterin puu varten Fashion-MNIST dataset. Jokainen lehtisolmu näyttää satunnaisesti otettuja sille osoitettuja objekteja. Etiketit ovat tekijöiden tulkintoja. Värilliset alueet korostavat kolmea hallitsevaa alapuuta, jotka edustavat kolmea aineistosta löytyvää esinetyyppiä: laukkuja, vaatteita ja kenkiä

Muoti-MNIST sisältää kymmenen eri luokkaa vaatteita, kenkiä ja laukkuja, eli T-paita/Toppi, Housut, villapaita, mekko, takki, sandaali, paita, lenkkari, laukku ja nilkkurit. Tuloksena klusterin puu meidän menetelmä on esitetty kuvassa. 7. Lehtien solmut esitetään satunnaisesti otoksina sille osoitettuina kohteina. Kunkin solmun etiketit ovat tulkintamme, joka perustuu kulloiseenkin solmuun osoitettuihin esineisiin. Voimme nähdä, että DeepECT löysi täysin luonnollisen näköisen hierarkian tästä aineistosta. Ensin kuvat on jaettu kolmeen luokkaan: vaatteisiin, kenkiin ja laukkuihin. Korostimme näitä alapuita, joissa oli värillisiä alueita. Jokaisesta alapuusta löytyy luonnollisia hierarkioita. Laukkuluokka erottaa toisistaan kassit, joissa ei ole näkyvää hihnaa/kahvaa, laukut, joissa on pienet kahvat, ja laukut, joissa on olkahihna. Maatotuus ei tee eroa näiden laukkutyyppien välillä ja määrää ne kaikki samaan luokkaan. Vaatekategoria jaetaan ensin housuihin ja ylävartalolle tarkoitettuihin vaatteisiin. Nämä jaetaan taas lyhyisiin ja pitkiin hihoihin. Tässä Hihan pituus on nähtävä suhteessa vastaavan vaatteen kokonaispituuteen, koska jokainen tuote on normalisoitu näyttämään samankokoiselta kuvan sisällä, ts. mekot ja paidat näyttävät olevan samaa kokoa. Kenkäkategoriassa näkyy myös mielenkiintoisia piirteitä. Ensin erottuvat pienemmät ja isommat kengät. Pienemmät kengät jaetaan sitten edelleen sandaaleihin ja lenkkareihin. Isommissa kengissä on joko tasainen pohja, pieni korko tai ne ovat korkeakorkoiset. Näihin piirteisiin perustuvan hierarkian rakentaminen on vastoin tennareiden, sandaalien ja nilkkureiden maastototuusluokkia. Se on kuitenkin—ulkonäön näkökulmasta-pätevä ja informatiivinen hierarkia kengille.

sovellettavuus Ennustustehtäviin MNIST

arvioimme myös deepectiä ennustustehtävässä. Siten pidämme automaattisovittimet ja ryhmittelyn optimointimenettely edellä kuvatulla tavalla. Toisin kuin edellä olevassa kokeellisessa arvioinnissa, käytämme vain 50.000 ensimmäistä näytettä (koulutussarja) aineistosta MNIST klusteripuun optimoinnin aikana. Optimoinnin jälkeen arvioimme klusteripuun Cluster-suorituskyvyn aiemmin näkemättömällä, jäljellä olevalla 20.000 datapisteellä (testisarja).

tässä kokeessa saadaan testijoukolle dendrogram-puhtaus \(0.73\pm 0.08\) ja lehtien puhtaus \(0.85\pm 0.06\), mikä on pieni pudotus taulukon 2 arvoihin verrattuna. Tulos on kuitenkin riittävän vankka, jotta aiemmin näkemättömien datapisteiden rajalliset merkintäennusteet voidaan ennustaa suoraan klusteripuun avulla. Useimmissa tapauksissa kouluttaisimme kuitenkin luokittajan löydettyjen klusterirakenteiden perusteella. Sama pätee myös itse upotukseen, jossa voimme hyödyntää esimerkiksi valvottua automaattikooderin häviötä parannettaessa löydettyä upotusta.

kokeiden Yhteenveto

yhteenvetona katsomme, että esitetyt kokeet neljällä reaalimaailman aineistolla osoittavat selvästi DeepECT-klusteripuun hyödyllisyyden ja tehokkuuden. Tällaisten rakenteiden löytäminen ja analysoitavan yksityiskohtaisuuden valitseminen tekevät Deepectistä arvokkaan menetelmän datatieteilijöille.