DeepECT: głęboko osadzone drzewo klastrów

oceniamy naszą proponowaną metodę DeepECT na czterech powszechnie używanych zestawach danych głębokiego uczenia: MNIST, USPS, Fashion-MNIST i Reuters. Tabela 1 przedstawia statystyki wszystkich zestawów danych wykorzystywanych w eksperymentach. MNIST i USP są zestawami danych obrazu zawierającymi Odręczne cyfry. Zestaw danych Fashion-MNIST zawiera obrazy produktów modowych, takich jak obrazy odzieży, obuwia i toreb. Zbiór danych Reuters zawiera artykuły informacyjne w czterech najważniejszych kategoriach i używamy tej samej reprezentacji, jak opisano w .

Konfiguracja eksperymentalna

skupiamy nasze eksperymenty na ocenie naszej nowej warstwy klastrowej. Dlatego powstrzymujemy się od używania bardziej rozbudowanych architektur autoencodera. Zamiast tego używamy tego samego ogólnego, w pełni połączonego układu autoencodera dla wszystkich eksperymentów, jak w . Jak wspomniano wcześniej, spodziewamy się, że wszystkie metody zyskałyby jednakowo z bardziej wyrafinowanych i specyficznych dla domeny architektur. Jednak standardowa Architektura autoencodera jest wystarczająca, aby pokazać żywotność DeepECT w porównaniu do konkurentów bazowych. W związku z tym używamy tej samej ogólnej architektury autoencodera, co zaproponowano w I, która również została użyta w celu klastrowania wbudowanej przestrzeni. Enkoder feedforward w tej architekturze ma wymiary d-500–500–2000–10, a sieć dekodera ma lustrzany układ. Używamy aktywacji ReLU i średniej straty rekonstrukcji błędu kwadratowego z Eq. (1).

wstępnie szkolimy dziesięć autoencoderów dla każdego zbioru danych i używamy tych samych wstępnie przeszkolonych sieci do wszystkich eksperymentów i metod porównawczych. Korzystanie z tych wstępnie przeszkolonych autoenkoderów zapewnia, że każda metoda ma takie same warunki początkowe dla osadzonej przestrzeni i że różnice w jakości klastrowania nie wynikają tylko z jakościowo różnych autoenkoderów. Konfiguracja przedtreningowa jest podobna do opisanej w . Wstępnie szkolimy autoencoderów jako denoising autoencoders z 20% wskaźnikiem korupcji. Po pierwsze, wykonujemy trening przedtreningowy z pominięciem każdej warstwy (z szybkością 20%) i 20 000 kroków na warstwę. Następnie dostroimy całą sieć na 50 000 kroków bez przerwania. Używamy korupcji danych wejściowych tylko do wstępnego treningu,a nie do rzeczywistej optymalizacji DeepECT i jego podstawowych metod. Do wszystkich eksperymentów używamy Adam (learning \({\hbox {rate}}=0.0001\), \(\beta _1=0,9, \beta _2=0,999\)) jako algorytm optymalizacji i mini-partii wielkości 256 próbek. W celu optymalizacji połączonej trenujemy dodatkowe 50 000 iteracji, aby zapewnić konwergencję.

w przypadku DeepECT nasze wstępne eksperymenty z danymi syntetycznymi wykazały, że podział drzewa co 500 kroków optymalizacyjnych daje obiecujące wyniki, a bardziej rozszerzone rozmiary kroków nie zwiększają wydajności. Z tego powodu utrzymujemy ten harmonogram bez dostosowywania go do eksperymentów na rzeczywistych zbiorach danych. To samo dotyczy progu przycinania, o którym mowa w sekcie. 2.7. W przypadku MNIST, Fashion-MNIST i USPS uprawiamy drzewa, dopóki nie zawierają dwudziestu węzłów liści. Dla zbioru danych Reutersa, ustawiliśmy maksymalną liczbę węzłów liścia na dwanaście, ponieważ ma mniej uziemionych klastrów prawdy. W ten sposób mamy dwa razy i trzy razy rzeczywistą liczbę klastrów. Uważamy te wartości za wystarczające do uchwycenia istotnych struktur wybranych zbiorów danych na potrzeby niniejszego artykułu. Używamy tej samej liczby węzłów liści dla hierarchicznych metod bazowych.

wykresy pokazują próbkę oryginalnych cyfr MNIST i losowo powiększoną wersję

w przypadku zbiorów danych obrazu eksperymentowaliśmy dodatkowo z rozszerzeniem augmentation DeepECT + Aug. Zaczynamy od tych samych wstępnie przeszkolonych autoencoderów, co w innych eksperymentach. Ponadto trzymamy się tego samego harmonogramu optymalizacji, jak opisano powyżej w przypadku eksperymentów z nie rozszerzonymi wersjami DeepECT. W każdej iteracji używamy oryginalnego mini-wsadu i jego rozszerzonego odpowiednika, aby zoptymalizować funkcję utraty w korektorze. 9, zamiast nie zwiększonej straty w korektorze. 6. Tworzymy rozszerzoną wersję każdego obrazu mini-partii, stosując w locie losową transformację afiniczną. Transformacja afiniczna losowo obraca i ścina obraz w zakresie \(\) stopni. Ponadto losowo przesuwa cyfrę do dwóch pikseli w dowolnym kierunku. Rysunek 5 pokazuje przykład tego powiększenia dla MNIST.

metody oceny

hierarchię klastrów DeepECT oceniamy za pomocą pomiaru czystości DENDROGRAMU (DP) i czystości liści (LP). Opisujemy oba poniżej. Ponadto oceniamy drzewo klastrów na podstawie płaskich metod bazowych. W tym celu wykorzystujemy dobrze znane znormalizowane wzajemne informacje (NMI) i dokładność klastrowania (ACC). Uwzględniamy je dla kompletności i pokazania, że DeepECT jest również konkurencyjny w scenariuszach, w których oczekuje się płaskiej struktury klastra i zna rzeczywistą liczbę klastrów w zbiorze danych. Aby określić partycję klastra k z drzewa klastra, używamy przypisań do węzłów K, które były węzłami liścia po pierwszych \(k-1\) podziałach.

czystość Dendrogramu

miara czystości dendrogramu może być użyta do oceny drzewa klastra na tle płaskiej ziemi. Jest to oczekiwana czystość sub-drzewa podana przez najmniejszy wspólny węzeł nadrzędny dla dwóch losowo pobranych punktów danych tej samej klasy. Jest to 1.0 wtedy i tylko wtedy, gdy wszystkie punkty danych należące do jednej klasy w gruncie prawdy są przypisane do jakiegoś czystego pod-drzewa i zbliża się do 0 dla losowo generowanych drzew.

Jawna formuła jest zdefiniowana jako:

gdzie \(c_1, \dots, C_K\) są zbiorami punktów danych odpowiadających podstawowym klasom prawdy, \({\text {lca}} (x, y)\) jest najmniejszym wspólnym węzłem nadrzędnym x i y w drzewie klastra, \({\text {dan}}(Z)\) jest zbiorem punktów danych przypisanych do węzła z w drzewie klastra, \({\text {PUR}} (S,T) = | s \cap T / | | S/\) jest miarą czystości i \({\mathcal {P}} = \{(x,y) \mid \exists C \in \{c_1, \dots, C_K\}: x, y \in C \wedge x \ne y\}\) jest zbiorem wszystkich par punktów danych, które należą do tej samej klasy. Czystość dendrogramu można obliczyć efektywnie i dokładnie w rekurencji oddolnej na drzewie klastra.

czystość liści

oprócz stosowania czystości dendrogramu, Wprowadzamy jeszcze jedną miarę, którą nazywamy czystością liści (LP). Jest to ważona-średnia czystość węzłów liściowych w. r. t. do klasy większości obiektów przypisanych do węzła liści, podana wzorem:

gdzie \({{\mathcal {L}}} _{{\mathcal {D}}}\) jest zbiorem zbiorów zawierających punkty danych przypisane do węzłów liści.

zależność wysokości drzewa od miar czystości

porównanie czystości dendrogramu i liści dwóch drzew klastrowych jest bezpośrednio możliwe tylko wtedy, gdy oba drzewa mają taką samą liczbę węzłów liściowych. Jednak sub-drzewa zawsze mogą być zwinięte w węzły liści, aby spełnić ten wymóg. W związku z tym zwijamy bottom-up linkage-drzewa metod bazowych—w kolejności łączenia—przez kompresowanie sub-drzew w węzły liści, dopóki nie mamy takiej samej liczby kroków scalania, jak split-nodes w top-down drzewach DeepECT i Bisecting-k-means. Proces ten zapewnia, że obie metody są porównywalne w. r. t. hierarchiczne środki oceny.

Hierarchical Clustering Baselines

jako punkt bazowy do oceny właściwości hierarchicznych, łączymy osadzone dane z klasycznymi algorytmami hierarchicznego klastrowania bisecting-k-means (AE + Bisecting), single-linkage (AE + Single) I complete-linkage (AE + Complete). Ponieważ żaden z tych klasycznych algorytmów nie jest w stanie zoptymalizować wbudowanej przestrzeni, badamy również prosty pomysł połączenia płaskiego wbudowanego algorytmu klastrowania IDEC z pojedynczym połączeniem i kompletnym połączeniem. IDEC jest metodą, która łączy warstwę klastrowania DEC z utratą rekonstrukcji autoencodera. Najpierw uruchamiamy IDEC z liczbą klastrów ustawioną na wartość wyższą niż oczekiwana liczba klastrów—w naszym przypadku ustawiamy ją na wartość maksymalną liczby węzłów liści, których używamy w Deepeccie. Następnie uważamy te centra klastrów IDEC za przedstawicieli przypisanych punktów danych i staramy się odzyskać hierarchiczną strukturę klastrów, wykonując jedno-powiązanie i kompletne połączenie na centrach klastrów (IDEC + Single i IDEC + Complete). Podobną technikę proponuje się w przypadku klasycznych, Nie osadzonych ustawień Z k-means zamiast IDEC.

Flat Clustering Baselines

jako punkt bazowy do oceny wydajności DeepECT w płaskich Ustawieniach klastrowania używamy k-means na osadzonych danych wstępnie wyszkolonego autoencodera (AE + k-means)I IDEC . Jeśli zignorujemy zalety bardziej specyficznych dla domeny i wyrafinowanych architektur autoencodera, IDEC jest obecnie jedną z najlepszych wbudowanych metod klastrowania. W przeciwieństwie do DeepECT, musimy ustawić rzeczywistą liczbę klastrów w ziemi podczas optymalizacji dla IDEC i k-means. Ponadto ustawiliśmy hiperparametr IDEC dla straty rekonstrukcji na 0,1, jak opisano w .

wyniki Ogólne

wyniki ogólne—uśrednione na podstawie dziesięciu wcześniej przeszkolonych autoenkoderów – do oceny hierarchicznej z wykorzystaniem środków czystości dendrogramu i czystości liści dla DeepECT i hierarchicznych algorytmów bazowych przedstawiono w tabeli 2. DeepECT konsekwentnie tworzy drzewa klastrów o wysokiej jakości i jest algorytmem o najwyższej wydajności z szerokim marginesem. Możemy również zobaczyć, że rozszerzenie augmentacji dodatkowo poprawia wyniki znacznie dla MNIST i USPS. Wyniki DeepECT z i bez rozszerzenia augmentation dla zestawu danych Fashion-MNIST są podobne, ponieważ autorzy zestawu danych zdecydowali się wstępnie przetworzyć wszystkie obrazy, aby każdy element mody miał znormalizowaną reprezentację. Wyniki metod klasycznych można wyjaśnić ich niezdolnością do wzmocnienia osadzania. Wartości czystości liści dla DeepECT wskazują, że metoda jest w stanie stworzyć jednorodne subpopulacje. Jeśli porównamy wartości czystości liści deepect i hierarchiczne warianty IDEC + Center-linkage z wartościami czystości liści innych linii bazowych, zobaczymy, że połączona optymalizacja klastrowania i autoencodera—obu metod – rzeczywiście poprawia jednorodność lokalnych struktur. Jednak IDEC + Center-linkage nie jest również w stanie wyodrębnić spójnej struktury hierarchicznej.

Tabela 3 przedstawia wyniki eksperymentalne dla metod porównywania klastrów płaskich opartych na tych samych wstępnie przeszkolonych autoenkoderach. Ponieważ używamy tych samych wstępnie przeszkolonych autoencoderów, możemy bezpośrednio zobaczyć wpływ danego celu klastrowania. Zarówno IDEC, jak i DeepECT korzystają z połączonej optymalizacji w porównaniu do k-means,które nie mogą zoptymalizować osadzania. Tabela 4 przedstawia wyniki bardziej opartych na centroidach metod klastrowania zaczerpniętych z odpowiedniej publikacji. Więcej szczegółów na temat tych metod można znaleźć w sekcie. 4. Widzimy, że DeepECT działa również dobrze w porównaniu z tymi metodami. Jednak możemy również zauważyć, że architektura autoencodera znacząco wpływa na wynik klastrowania. Na przykład, DBC różni się od DEC tylko użyciem autoencodera konwolutacyjnego, ale osiąga lepsze wyniki. Jednak wybrana Architektura autoencodera jest niezależna od wybranej warstwy klastrowej.

oczywiście to porównanie celów klastrowania płaskiego i DeepECT jest niesprawiedliwe w stosunku do tego drugiego, ponieważ konkurencyjne metody otrzymują prawdziwą liczbę klastrów podczas optymalizacji, podczas gdy w przypadku DeepECT używamy tych informacji tylko podczas oceny. Niemniej jednak widzimy, że zwykła wersja DeepECT może nadążyć za tymi metodami pod względem surowych miar NMI i ACC, a rozszerzenie augmentacji DeepECT + Aug wykazuje znaczną poprawę w stosunku do wyników DeepECT, ponieważ może ignorować znane niezmienności w danych. Wyniki te pokazują, że DeepECT jest również konkurencyjny w scenariuszach, w których oczekuje się płaskiej struktury klastra, ale nie zna liczby klastrów i rekursywnie sprawdza drzewo klastrów.

szczegółowa ocena

w tej sekcji przyjrzymy się bliżej wynikowym drzewom DeepECT dla powyższych zbiorów danych. Ponieważ ustalenia zestawu danych USPS są porównywalne z wynikami MNIST—ponieważ obie reprezentują Odręczne cyfry—pomijamy te wyniki dla zwięzłości.

wyniki MNiSW

bliższe spojrzenie na powstałe drzewa DeepECT dla zbioru danych MNiSW pokazuje ekscytujące właściwości różnych subpopulacji w obrębie odręcznych cyfr. Dwa ilustracyjne przykłady pokazane są na Fig. 6 i można go znaleźć w zwykłym i rozszerzonym rozszerzeniu DeepECT. Czystość węzła przedstawionych pod drzewami dla cyfry 7′ wynosi 98% i zawiera prawie wszystkie instancje tej klasy. Zawiera dwa węzły liściowe. Jeden węzeł liści pokazuje siódemki z małą poprzeczką, jak to jest powszechnie napisane w Europie, drugi węzeł liści pokazuje tę cyfrę, jak to jest powszechnie napisane w USA. Drugie pod drzewem zawiera prawie wszystkie instancje cyfry ” 2 ” o czystości 97%. Pod drzewem tym znajdują się również dwa węzły liściowe, każdy o specyficznych cechach. Pierwszy węzeł liścia zawiera instancje, które są bardziej kręcone i mają charakterystyczną pętlę w dolnej części. Drugi węzeł liściowy zawiera bardziej “opływową” wersję tej cyfry, wyglądającą jak znak “z”. pokazane sub-drzewa budują naturalną hierarchię dla danej cyfry i łatwo można sobie wyobrazić, że te odkrycia mogą być interesujące dla badacza. Inne kształty zależne od grup cyfr można znaleźć również w dolnych częściach drzewa, na przykład pisane wersje cyfr ” 4 ” i ” 9 ” mają wiele cech. W związku z tym często można je znaleźć zgrupowane razem jako sub-drzewo zawierające tylko te dwa typy cyfr.

wykresy pokazują dwa wyodrębnione sub-drzewa z interesujących subpopulacji zbioru danych MNIST znalezionego przez DeepECT. Są to cyfry siedem (z poprzeczką Środkową i bez niej) oraz dwie (wersja kędzierzawa i “opływowa”, wyglądająca bardziej jak znak “Z”). Pokazane cyfry są losowo próbkowane

Reuters wyniki

Reuters dataset zawiera cztery niezrównoważone Top kategorie (etykiety pierwszego poziomu) z następującą dystrybucją klasy: Współpraca/Przemysł z 44%, rząd/społeczny z 24%, rynki z 24% i Ekonomia z 8%. Ten zbiór danych jest wyjaśniony bardziej szczegółowo w . Kategorie dla każdego artykułu zostały wybrane ręcznie i dlatego są w pewnym stopniu subiektywne. Ponadto każda kategoria górna ma kilka dodatkowych nakładających się na siebie podkategorii (etykiety drugiego poziomu)-i podkategorii (etykiety trzeciego poziomu)-z ponad 96% artykułów należących do dwóch lub więcej podkategorii. Tabela 5 pokazuje wynik DeepECT dla tego zestawu danych. Widzimy, że pierwsze dwa podziały oddzielają większość podgrup rządowych/społecznych zaczynających się od węzła 3—i podgrup rynków zaczynających się od węzła 5-Kategorie od pozostałych dwóch kategorii. Podgrupa rządowo-społeczna dzieli się następnie dalej na tematy z podkategorii, takich jak sport, wojna i przestępczość, polityka krajowa i międzynarodowa. Kategoria rynki dodatkowo różnicuje się na różne aspekty poszczególnych podkategorii. Na przykład węzły liści w dwóch ostatnich rzędach dotyczą różnych podkategorii podkategorii rynków towarowych. Węzły liści w środku są głównie związane z korporacją / przemysłem i ekonomią. Nie są one tak dobrze oddzielone jak pozostałe dwa podgatunki. Jednak nawet tam możemy znaleźć interesujące węzły liści. Na przykład, węzeł siódmego liścia (wiersz) z góry dzieli artykuły informacyjne oznaczone podkategoriami wydajność (Korporacja/przemysł) i wydajność ekonomiczna (Ekonomia) i wydaje się rozsądne oczekiwać powiązanych słów dla tych dwóch podkategorii.

Moda-wyniki MNiSW

diagram przedstawia drzewo klastrów dla zbioru danych Fashion-MNIST. Każdy węzeł liści pokazuje losowo wybrane obiekty przypisane do niego. Etykiety są interpretacjami autorów. Kolorowe obszary podkreślają trzy dominujące sub-drzewa reprezentujące trzy rodzaje obiektów znalezionych w zbiorze danych: torby, ubrania i buty

Moda-MNIST zawiera dziesięć różnych klas ubrań, butów i toreb, a mianowicie T-shirt/top, spodnie, sweter, sukienkę, płaszcz, Sandały, koszulę, trampki, torbę i botek. Powstałe drzewo klastrów naszej metody pokazano na Fig. 7. Węzły liści są reprezentowane jako losowo wybrane obiekty przypisane do niego. Etykiety każdego węzła są naszą interpretacją opartą na obiektach przypisanych do danego węzła. Widzimy, że DeepECT znalazł całkowicie naturalnie wyglądającą hierarchię w tym zbiorze danych. Po pierwsze, obrazy są podzielone na trzy kategorie: ubrania, buty i torby. Podkreśliliśmy te sub-drzewa kolorowymi obszarami. W obrębie każdego pod drzewem możemy znaleźć naturalne hierarchie. Kategoria toreb wyróżnia torby bez widocznego paska/rączki, torby z małymi rączkami oraz torby z paskiem na ramię. Prawda gruntowa nie rozróżnia tych rodzajów toreb i przypisuje je wszystkie do tej samej klasy. Kategoria ubrań jest najpierw podzielona na spodnie i ubrania dla górnej części ciała. Są one następnie ponownie podzielone na krótkie i długie rękawy. Tutaj Długość rękawa musi być widoczna w stosunku do całkowitej długości danego ubrania, ponieważ każdy element jest znormalizowany, aby pojawił się w tym samym rozmiarze na obrazie, tj., sukienki i koszule wydają się być tego samego rozmiaru. Kategoria obuwia pokazuje również kilka interesujących cech. Najpierw rozróżnia się mniejsze i większe buty. Mniejsze buty są następnie dalej dzielone na Sandały i trampki. Większe buty mają płaską podeszwę, mały obcas lub są na wysokim obcasie. Budowanie hierarchii opartej na tych cechach przebiega na tle klasy trampek, sandałów i botków. Niemniej jednak—z punktu widzenia wyglądu-jest to ważna i pouczająca hierarchia butów.

zastosowanie do zadań predykcyjnych w MNIST

oceniamy również DeepECT w zadaniu predykcyjnym. W ten sposób zachowujemy autoencodery i procedurę optymalizacji klastrów, jak opisano powyżej. W przeciwieństwie do powyższej oceny eksperymentalnej, podczas optymalizacji drzewa klastrów używamy tylko pierwszych 50.000 próbek (zestaw treningowy) MNIST zbioru danych. Po optymalizacji oceniamy wydajność klastrowania drzewa klastrów na wcześniej niewidocznych, pozostałych 20.000 punktów danych (zestaw testowy).

w tym eksperymencie otrzymujemy dla testu czystość dendrogramu \(0.73\ pm 0,08\) i czystość liści \ (0,85 \ pm 0,06\), co jest lekkim spadkiem w porównaniu do wartości w tabeli 2. Niemniej jednak wynik jest wystarczająco solidny, aby umożliwić ograniczone przewidywanie etykiet wcześniej niewidocznych punktów danych bezpośrednio przez drzewo klastrów. Jednak w większości przypadków szkolilibyśmy klasyfikator na podstawie znalezionych struktur klastrowych. To samo dotyczy samego osadzania, gdzie możemy wykorzystać, na przykład, nadzorowaną utratę autoencodera, aby poprawić znalezione osadzanie.

podsumowanie eksperymentów

Podsumowując, uważamy, że pokazane eksperymenty na czterech rzeczywistych zestawach danych wyraźnie pokazują użyteczność i skuteczność drzewa klastrów DeepECT. Znalezienie tego rodzaju struktur i wybór poziomu szczegółowości do analizy sprawiają, że DeepECT jest cenną metodą dla naukowców zajmujących się danymi.