DeepECT: Arborele Cluster încorporat adânc

evaluăm metoda propusă DeepECT pe patru seturi de date de învățare profundă utilizate în mod obișnuit: Mnist, USPS, Fashion-mnist și Reuters. Tabelul 1 prezintă statisticile tuturor seturilor de date utilizate în experimente. MNIST și USPS sunt ambele seturi de date de imagine care conțin cifre scrise de mână. Setul de date Fashion-MNIST conține imagini ale produselor de modă, cum ar fi imagini de îmbrăcăminte, încălțăminte și Genți. Setul de date Reuters conține articole de știri din patru categorii de top și folosim aceeași reprezentare descrisă în .

configurare experimentală

ne concentrăm experimentele pe evaluarea noului nostru strat de clustering. Prin urmare, ne abținem de la utilizarea arhitecturilor autoencoder mai elaborate. În schimb, vom folosi același aspect generic complet conectat autoencoder pentru toate experimentele, așa cum este utilizat în . Așa cum am menționat anterior, ne așteptăm ca toate metodele să câștige în mod egal din arhitecturi mai sofisticate și specifice domeniului. Cu toate acestea, o arhitectură autoencoder standard este suficientă pentru a arăta viabilitatea DeepECT în comparație cu concurenții de bază. Prin urmare, folosim aceeași arhitectură autoencoder generică, așa cum este propusă și care este utilizată și în scopul grupării spațiului încorporat. Codificatorul feedforward din această arhitectură are dimensiunile d-500–500–2000–10, iar rețeaua de decodare are un aspect oglindit. Folosim activările ReLU și pierderea medie de reconstrucție a erorii pătrate din Eq. (1).

pregătim zece autoencodere pentru fiecare set de date și folosim aceleași rețele pre-instruite pentru toate experimentele și metodele de comparație. Utilizarea acestor autoencodere pre-instruite asigură că fiecare metodă are aceleași condiții de pornire pentru spațiul încorporat și că variațiile calității clusterului nu provin doar din autoencodere calitativ diferite. Configurația de pre-formare este similară cu cea descrisă în . Noi pre-tren autoencoders ca denoising autoencoders cu o rată de corupție 20%. În primul rând, efectuăm un pre-antrenament în strat cu abandon după fiecare strat (cu o rată de 20%) și 20.000 de pași pe strat. Apoi, reglăm întreaga rețea pentru 50.000 de pași fără abandon. Folosim corupția de intrare doar pentru pre-instruire și nu pentru optimizarea efectivă a DeepECT și a metodelor sale de bază. Pentru toate experimentele, folosim Adam (learning \({\HBox {rate}}=0.0001\), \(\beta _1=0,9, \ beta _2 = 0,999\)) ca algoritm de optimizare și o dimensiune mini-lot de 256 de probe. Pentru optimizarea combinată, ne pregătim pentru 50.000 de iterații suplimentare pentru a asigura convergența.

pentru DeepECT, experimentele noastre inițiale cu date sintetice au arătat că împărțirea arborelui la fiecare 500 de pași de optimizare dă rezultate promițătoare, iar dimensiunile mai extinse ale pasului nu au crescut și mai mult performanța. Din acest motiv, păstrăm acest program fără a-l ajusta pentru experimentele pe seturi de date din lumea reală. Același lucru este valabil și pentru pragul de tăiere menționat în sectă. 2.7. Pentru Mnist, Fashion-Mnist și USPS, creștem copacii până când conțin douăzeci de noduri de frunze. Pentru setul de date Reuters, am setat numărul maxim de noduri de frunze la doisprezece, deoarece are mai puține clustere de adevăr la sol. În acest fel, avem de două ori și de trei ori numărul real de clustere. Considerăm aceste valori suficiente pentru a capta structurile esențiale ale seturilor de date selectate în scopul acestei lucrări. Folosim același număr de noduri de frunze pentru metodele de bază ierarhice.

parcelele arată un eșantion de cifre mnist originale și o versiune mărită aleatoriu

pentru seturile de date de imagine, am experimentat suplimentar extensia de augmentare DeepECT + Aug. Începem cu aceleași autoencodere pre-instruite ca și în celelalte experimente. Mai mult, rămânem la același program de optimizare descris mai sus pentru experimentele cu versiunile non-augmentate ale DeepECT. În fiecare iterație, folosim mini-lotul original și omologul său augmentat pentru a optimiza funcția de pierdere în Eq. 9, în loc de pierderea non-augmentată în Eq. 6. Creăm versiunea augmentată a fiecărei imagini a unui mini-lot, aplicând în zbor o transformare afină aleatorie. Transformarea afină se rotește aleatoriu și forfecă imaginea în intervalul de grade \ ( \ ). De asemenea, se mișcă cifra aleatoriu până la doi pixeli în orice direcție. Figura 5 prezintă un exemplu al acestei augmentări pentru MNIST.

metode de evaluare

evaluăm ierarhia clusterului DeepECT cu măsurarea purității dendrogramei (DP) și a purității frunzelor (LP). Descriem ambele mai jos. Mai mult, evaluăm arborele de cluster împotriva metodelor de bază plate. Pentru aceasta, folosim binecunoscutele informații reciproce normalizate (NMI) și precizia clusterului (ACC) . Le includem pentru completitudine și pentru a arăta că DeepECT este, de asemenea, competitiv în scenarii, unde se așteaptă o structură plană de cluster și cunoaște numărul real de clustere din setul de date. Pentru a determina o partiție de cluster k dintr-un arbore de cluster, folosim atribuirile nodurilor k care au fost noduri de frunze după prima împărțire \(k-1\).

puritatea Dendrogramei

măsura purității dendrogramei poate fi utilizată pentru a evalua arborele cluster în raport cu o partiție de adevăr la sol plat. Este puritatea așteptată a subarborului dată de cel mai mic nod strămoș comun pentru două puncte de date eșantionate aleatoriu din aceeași clasă. Este 1.0 dacă și numai dacă toate punctele de date aparținând unei clase din adevărul solului sunt atribuite unui sub-copac pur și se apropie de 0 pentru copacii generați aleatoriu.

formula explicită este definită în as:

unde \(c_1, \dots , C_K\) sunt seturile de puncte de date corespunzătoare claselor de adevăr de la sol, \({\text {LCA}} (x, y)\) este cel mai puțin comun nod strămoș al lui x și y din arborele clusterului, \({\text {dan}} (z)\) este setul de puncte de date atribuite nodului z din arborele clusterului, \({\text {pur}}(S, T) = |S \cap T| / | S|\) este măsura purității, iar \({\mathcal {P}} = \ {(x, y) \mid \există C \în \{c_1,\ dots , C_K\}: x,y \în C \wedge x\ ne y\}\) este setul tuturor perechilor de puncte de date care aparțin aceleiași clase. Puritatea dendrogramei poate fi calculată eficient și precis într-o recursivitate de jos în sus pe arborele clusterului.

puritatea frunzelor

pe lângă utilizarea purității dendrogramei, introducem o altă măsură pe care o numim puritatea frunzelor (LP). Este puritatea medie ponderată a nodurilor frunzelor w.r. T. la clasa majoritară a obiectelor atribuite unui nod de frunze, dată de formula:

unde \({{\mathcal {l}}} _{{\mathcal {D}}}\) este setul de seturi care conțin punctele de date atribuite nodurilor frunze.

dependența înălțimii copacilor de puritate măsoară

Compararea dendrogramei și a purității frunzelor a doi arbori de cluster este posibilă numai dacă ambii copaci au același număr de noduri de frunze. Cu toate acestea, subarborii pot fi întotdeauna prăbușiți în noduri de frunze pentru a îndeplini această cerință. Prin urmare, restrângem copacii de legătură de jos în sus ai metodelor de bază-în ordinea legăturii-prin comprimarea subarborilor în noduri de frunze până când avem același număr de pași de îmbinare rămași ca nodurile divizate în copacii de sus în jos ai deepect și Bisecting—k—means. Acest proces asigură faptul că ambele metode sunt comparabile cu măsurile de evaluare ierarhică.

linii de bază ierarhice de grupare

ca linie de bază pentru evaluarea proprietăților ierarhice, grupăm datele încorporate cu algoritmii clasici de grupare ierarhică bisecting-k-means (ae + Bisecting), single-linkage (ae + Single) și complete-linkage (ae + Complete). Deoarece niciunul dintre acești algoritmi clasici nu poate optimiza spațiul încorporat, explorăm și ideea simplă de a combina algoritmul de clustering încorporat plat IDEC cu o singură legătură și o legătură completă. IDEC este o metodă care combină stratul de clustering al DEC cu pierderea reconstrucției autoencoderului. În primul rând, rulăm IDEC cu numărul de clustere setat la o valoare mai mare decât numărul așteptat de clustere—în cazul nostru, îl setăm egal cu numărul maxim de noduri de frunze pe care le folosim pentru DeepECT. Apoi, considerăm aceste centre de cluster IDEC ca reprezentanți ai punctelor de date atribuite și încercăm să recuperăm o structură ierarhică de grupare prin efectuarea unei legături unice și a unei legături complete pe centrele de cluster (IDEC + Single și IDEC + Complete). O tehnică similară este propusă în pentru setările clasice, non-încorporate, cu mijloace k în loc de IDEC.

linii de bază flat Clustering

ca bază pentru evaluarea performanței DeepECT într-o setare flat clustering, folosim k-means pe datele încorporate ale autoencoderului pre-instruit (ae+k-means) și IDEC . Dacă ignorăm avantajele mai multor arhitecturi autoencoder specifice domeniului și sofisticate, IDEC este în prezent una dintre cele mai bune metode de clustering încorporate. Spre deosebire de DeepECT, trebuie să setăm numărul real de clustere în adevărul solului în timpul optimizării pentru IDEC și k-means. Mai mult, am setat hiperparametrul IDEC pentru pierderea reconstrucției la 0,1 așa cum este descris în .

rezultate generale

rezultatele generale—mediate pe zece autoencodere pre-instruite—pentru evaluarea ierarhică folosind măsuri de puritate a dendrogramei și de puritate a frunzelor pentru deepect și algoritmii ierarhici de bază sunt prezentate în tabelul 2. DeepECT produce în mod constant arbori de cluster de înaltă calitate și este algoritmul de cea mai bună performanță cu o marjă largă. De asemenea, putem vedea că extensia de augmentare îmbunătățește considerabil rezultatele pentru MNIST și USPS. Rezultatele DeepECT cu și fără extensia de augmentare pentru setul de date Fashion-Mnist sunt similare, deoarece autorii setului de date au ales să pre-proceseze toate imaginile astfel încât fiecare articol de modă să aibă o reprezentare normalizată. Rezultatele metodelor clasice pot fi explicate prin incapacitatea lor de a spori încorporarea. Valorile purității frunzelor pentru DeepECT indică faptul că metoda este capabilă să creeze subpopulații omogene. Dacă comparăm valorile purității frunzelor de DeepECT și variantele ierarhice Idec + Center-linkage cu valorile purității frunzelor celorlalte linii de bază, putem vedea că optimizarea combinată a clustering și autoencoder—a ambelor metode—îmbunătățește într-adevăr omogenitatea structurilor locale. Cu toate acestea, IDEC + Center-linkage este, de asemenea, incapabil să extragă o structură ierarhică coerentă.

Tabelul 3 prezintă rezultatele experimentale pentru metodele de comparare a clusterelor plate bazate pe aceleași autoencodere pre-instruite. Deoarece folosim aceleași autoencodere pre-instruite, putem vedea direct influența obiectivului de grupare respectiv. Atât IDEC, cât și DeepECT beneficiază de optimizarea combinată în comparație cu mijloacele k, care nu pot optimiza încorporarea. Tabelul 4 prezintă rezultatele mai multor metode de clustering bazate pe centroizi preluate din publicația respectivă. Mai multe detalii despre aceste metode pot fi găsite în Sect. 4. Putem vedea că DeepECT funcționează bine și în comparație cu aceste metode. Cu toate acestea, putem vedea, de asemenea, că arhitectura autoencoder influențează considerabil rezultatul grupării. De exemplu, DBC diferă de DEC numai prin utilizarea unui autoencoder convoluțional, dar obține rezultate superioare. Cu toate acestea, arhitectura autoencoder selectată este independentă de stratul de clustering selectat.

desigur, această comparație a obiectivelor de clustering plat și DeepECT este nedreaptă față de acestea din urmă, deoarece metodele concurente primesc numărul real de clustere în timpul optimizării, în timp ce pentru DeepECT, folosim aceste informații doar în timpul evaluării. Cu toate acestea, putem vedea că versiunea obișnuită a DeepECT poate ține pasul cu aceste metode în ceea ce privește măsurile brute NMI și ACC și că extensia de augmentare DeepECT + Aug prezintă îmbunătățiri substanțiale față de rezultatele DeepECT, deoarece poate ignora invarianțele cunoscute din cadrul datelor. Aceste rezultate arată că DeepECT este, de asemenea, competitiv în scenarii, unde se așteaptă o structură plană a clusterului, dar nu cunoaște numărul de clustere și inspectează arborele clusterului recursiv.

evaluare detaliată

în această secțiune, aruncăm o privire mai atentă asupra arborilor deepect rezultați pentru seturile de date de mai sus. Deoarece constatările setului de date USPS sunt comparabile cu cele ale MNIST—deoarece ambele reprezintă cifre scrise de mână—omitem aceste rezultate pentru concizie.

rezultate MNIST

o privire mai atentă asupra arborilor deepect rezultați pentru setul de date MNIST arată câteva proprietăți interesante ale diferitelor subpopulații din cifrele scrise de mână. Două exemple ilustrative sunt prezentate în Fig. 6 și pot fi găsite în extinderea obișnuită și augmentată a DeepECT. Puritatea nodului subarborilor descriși pentru cifra 7 ‘ este de 98% și conține aproape toate instanțele din această clasă. Conține două noduri de frunze. Un nod de frunze prezintă șapte cu o bară transversală mică, așa cum este scris în mod obișnuit în Europa, celălalt nod de frunze arată această cifră, deoarece este mai frecvent scris în SUA. Al doilea sub-arbore conține aproape toate instanțele cifrei ‘2’ cu o puritate de 97%. Acest sub-arbore conține, de asemenea, două noduri de frunze, fiecare cu caracteristici specifice. Primul nod de frunze conține instanțe care sunt mai curbate și au o buclă distinctivă în partea de jos. Al doilea nod de frunze conține o versiune mai ‘simplificată’ a acestei cifre, arătând ca personajul ‘Z.’ subarborii arătați construiesc o ierarhie naturală pentru cifra respectivă și se poate imagina cu ușurință că aceste descoperiri pot fi de interes pentru un cercetător. Alte grupări de cifre în funcție de formă pot fi găsite și în părțile inferioare ale arborelui, de exemplu, versiunile scrise ale cifrelor ‘4’ și ‘9’ au multe caracteristici. În consecință, ele pot fi adesea găsite grupate împreună ca un sub-arbore care conține doar aceste două tipuri de cifre.

parcelele arată doi sub-arbori extrași din subpopulații interesante ale setului de date MNIST găsit de DeepECT. Acestea sunt cifrele șapte (cu și fără bara transversală mijlocie) și două (o versiune cretă și o versiune simplificată, care seamănă mai mult cu personajul ‘Z’). Cifrele afișate sunt eșantionate aleatoriu

rezultate Reuters

setul de date Reuters conține patru categorii de top dezechilibrate (etichete de prim nivel) cu următoarea distribuție de clasă: cooperează/Industrial cu 44%, Guvern/Social cu 24%, piețe cu 24% și economie cu 8%. Acest set de date este explicat mai detaliat în . Categoriile pentru fiecare articol de știri au fost alese manual și, prin urmare, sunt într-o oarecare măsură subiective. Mai mult, fiecare categorie de top are mai multe subcategorii suplimentare suprapuse (etichete de nivelul doi)-și subcategorii (etichete de nivelul trei)-cu peste 96% din articole aparținând a două sau mai multe subcategorii. Tabelul 5 prezintă un rezultat DeepECT pentru acest set de date. Putem vedea că primele două diviziuni separă cea mai mare parte a sub—arborelui guvernamental/Social începând de la nodul 3-și sub—arborele piețelor începând de la nodul 5—categorii de celelalte două categorii. Sub – arborele guvernamental / Social se diferențiază apoi în continuare în subiecte ale subcategoriilor, cum ar fi sportul, războiul și criminalitatea, politica internă și internațională. De asemenea, categoria de piețe se diferențiază în continuare în diferite aspecte ale subcategoriilor respective. De exemplu, nodurile frunze din ultimele două rânduri se referă la diferite subcategorii ale piețelor de mărfuri din subcategorie. Nodurile frunzelor din mijloc sunt în mare parte legate de corporații/industriale și economie. Ele nu sunt la fel de bine separate ca celelalte două sub-copaci. Cu toate acestea, chiar și acolo, putem găsi noduri de frunze interesante. De exemplu, al șaptelea nod de frunze (rând) din partea de sus Împărtășește articole de știri etichetate cu performanța subcategoriilor (corporative/industriale) și performanța economică (a economiei) și pare rezonabil să ne așteptăm la cuvinte înrudite pentru aceste două subcategorii.

rezultate Fashion-MNIST

diagrama prezintă un arbore cluster pentru setul de date Fashion-MNIST. Fiecare nod de frunze prezintă obiecte eșantionate aleatoriu atribuite acestuia. Etichetele sunt interpretări ale autorilor. Zonele colorate evidențiază cei trei subarbori dominanți reprezentând trei tipuri de obiecte găsite în setul de date: genți, haine și încălțăminte

Fashion-MNIST conține zece clase diferite de haine, încălțăminte și genți, și anume tricou/top, pantaloni, pulover, rochie, haină, sandale, cămașă, adidaș, geantă și botină. Un arbore cluster rezultat al metodei noastre este prezentat în Fig. 7. Nodurile frunzelor sunt reprezentate ca obiecte eșantionate aleatoriu atribuite acestuia. Etichetele fiecărui nod sunt interpretarea noastră bazată pe obiectele atribuite nodului respectiv. Putem vedea că DeepECT a găsit o ierarhie cu aspect natural în acest set de date. În primul rând, imaginile sunt împărțite în trei categorii: haine, pantofi și Genți. Am evidențiat acești sub-copaci cu zone colorate. În fiecare sub-copac, putem găsi ierarhii naturale. Categoria de genți distinge între Genți fără curea/mâner vizibil, Genți cu mânere mici și Genți cu curea de umăr. Adevărul de la sol nu face distincție între aceste tipuri de pungi și le atribuie tuturor aceleiași clase. Categoria de haine este mai întâi împărțită în pantaloni și haine pentru partea superioară a corpului. Acestea sunt apoi din nou împărțite în Mâneci scurte și lungi. Aici, lungimea mânecii trebuie văzută în raport cu lungimea totală a îmbrăcămintei respective, deoarece fiecare articol este normalizat pentru a apărea de aceeași dimensiune în imagine, adică., rochiile și cămășile par a fi de aceeași dimensiune. Categoria de pantofi prezintă, de asemenea, câteva caracteristici interesante. În primul rând, se disting pantofii mai mici și mai mari. Pantofii mai mici sunt apoi împărțiți în sandale și adidași. Pantofii mai mari au fie o talpă plată, un toc mic, fie sunt cu toc înalt. Construirea ierarhiei pe baza acestor caracteristici se desfășoară împotriva claselor de adevăr la sol de adidași, sandale și botine. Cu toate acestea, este—din perspectiva aspectului—o ierarhie validă și informativă pentru pantofi.

Aplicabilitate pentru sarcinile de predicție pe MNIST

de asemenea, evaluăm DeepECT într-o sarcină de predicție. Astfel, vom păstra autoencoders și procedura de optimizare clustering așa cum este descris mai sus. Spre deosebire de evaluarea experimentală de mai sus, folosim doar primele 50.000 de eșantioane (set de instruire) ale setului de date MNIST în timpul optimizării arborelui cluster. După optimizare, evaluăm performanța de clustering a arborelui cluster pe cele nevăzute anterior, rămânând 20.000 de puncte de date (set de testare).

în acest experiment, obținem pentru setul de testare o puritate a dendrogramei de \(0.73\ pm 0,08\) și o puritate a frunzelor de\(0,85\ pm 0,06\), ceea ce reprezintă o ușoară scădere comparativ cu valorile din tabelul 2. Cu toate acestea, rezultatul este suficient de robust pentru a permite predicții limitate ale etichetelor punctelor de date nevăzute anterior direct de arborele clusterului. Cu toate acestea, în majoritatea cazurilor, am instrui un clasificator bazat pe structurile de cluster găsite. Același lucru este valabil și pentru încorporarea în sine, unde putem utiliza, de exemplu, pierderea autoencoderului supravegheat pentru a îmbunătăți încorporarea găsită.

Rezumatul experimentelor

în rezumat, credem că experimentele prezentate pe patru seturi de date din lumea reală arată clar utilitatea și eficacitatea arborelui cluster DeepECT. Găsirea acestor tipuri de structuri și selectarea nivelului de detaliu care trebuie analizat fac din DeepECT o metodă valoroasă pentru oamenii de știință de date.