Grupowanie na wyjściu t-SNE

77

Mam aplikację, w której przydałoby się skupić hałaśliwy zestaw danych przed wyszukaniem efektów podgrup w klastrach. Najpierw spojrzałem na PCA, ale potrzeba około 30 komponentów, aby uzyskać 90% zmienności, więc grupowanie tylko na kilku komputerach PC wyrzuci wiele informacji.

Następnie spróbowałem t-SNE (po raz pierwszy), co daje mi dziwny kształt w dwóch wymiarach, który jest bardzo podatny na grupowanie za pomocą k-średnich. Co więcej, uruchamianie losowego lasu na danych z przypisaniem klastra, ponieważ wynik pokazuje, że klastry mają dość rozsądną interpretację, biorąc pod uwagę kontekst problemu, pod względem zmiennych, które składają się na surowe dane.

Ale jeśli zamierzam informować o tych klastrach, jak je opisać? K-średnie klastry na głównych komponentach ujawniają osoby, które są blisko siebie pod względem zmiennych pochodnych, które zawierają X% wariancji w zestawie danych. Jakie równoważne stwierdzenie można powiedzieć o klastrach T-SNE?

Być może coś w wyniku:

t-SNE ujawnia przybliżoną przyległość w leżącym u jej podstaw wielowymiarowym kolektorze, więc klastry na niskowymiarowej reprezentacji przestrzeni wielowymiarowej maksymalizują „prawdopodobieństwo”, że przylegające osobniki nie będą w tej samej grupie

Czy ktoś może zaproponować lepszy blurb?

użytkownik_ogólny
źródło
1
Myślałem, że sztuczka polega na opisaniu klastrów na podstawie oryginalnych zmiennych, a nie zmiennych w ograniczonej przestrzeni.
Tim
1
Zgadza się, ale bez zwięzłego, intuicyjnego opisu celu, jaki minimalizuje algorytm przypisywania klastra, mogę być otwarty na zarzuty wyboru algorytmu klastrowania, który ułatwia uzyskanie pożądanych wyników.
generic_user
1
Aby zapoznać się z pewnymi zastrzeżeniami i ładnymi efektami
Tom Wenseleers

Odpowiedzi:

94

Problem z t-SNE polega na tym, że nie zachowuje on odległości ani gęstości. Tylko w pewnym stopniu zachowuje najbliższych sąsiadów. Różnica jest subtelna, ale wpływa na dowolny algorytm oparty na gęstości lub odległości.

Aby zobaczyć ten efekt, po prostu wygeneruj wielowymiarowy rozkład Gaussa. Jeśli zwizualizujesz to, będziesz mieć piłkę, która jest gęsta i staje się znacznie mniej gęsta na zewnątrz, z niektórymi wartościami odstającymi, które mogą być naprawdę daleko.

Teraz uruchom t-SNE na tych danych. Zwykle otrzymasz koło o raczej jednolitej gęstości. Jeśli używasz niskiego zakłopotania, może nawet mieć tam jakieś dziwne wzorce. Ale tak naprawdę nie można już odróżnić wartości odstających.

Teraz sprawmy, by sprawy stały się bardziej skomplikowane. Użyjmy 250 punktów w rozkładzie normalnym przy (-2,0) i 750 punktów w rozkładzie normalnym przy (+2,0).

Dane wejściowe

To powinien być łatwy zestaw danych, na przykład z EM:

Klastrowanie EM

Jeśli uruchomimy t-SNE z domyślnym zakłopotaniem 40, otrzymamy dziwnie ukształtowany wzór:

t-SNE p = 40

Nieźle, ale też nie tak łatwo się skupić, prawda? Trudno będzie ci znaleźć algorytm grupowania, który działa tutaj dokładnie tak, jak chcesz. I nawet jeśli poprosisz ludzi o zgrupowanie tych danych, najprawdopodobniej znajdą tutaj więcej niż 2 klastry.

Jeśli uruchomimy t-SNE ze zbyt małym zakłopotaniem, takim jak 20, otrzymamy więcej takich wzorów, które nie istnieją:

t-SNE p = 20

Spowoduje to klastrowanie np. Z DBSCAN, ale da cztery klastry. Uważaj, t-SNE może produkować „fałszywe” wzory!

Optymalne zakłopotanie wydaje się być dla tego zestawu danych około 80; ale nie sądzę, że ten parametr powinien działać dla każdego innego zestawu danych.

t-SNE p = 80

Teraz jest to przyjemne wizualnie, ale nie lepsze do analizy . Ludzki adnotator mógłby prawdopodobnie wybrać cięcie i uzyskać przyzwoity wynik; K-średnie jednak zawiedzie nawet w tym bardzo łatwym scenariuszu ! Widać już, że informacje o gęstości zostały utracone , wszystkie dane wydają się żyć w obszarze o prawie tej samej gęstości. Gdybyśmy zamiast tego jeszcze bardziej zwiększyliby zakłopotanie, jednolitość zwiększyłaby się, a separacja ponownie by się zmniejszyła.

Podsumowując, użyj t-SNE do wizualizacji (i wypróbuj różne parametry, aby uzyskać coś przyjemnego wizualnie!), Ale raczej nie uruchamiaj później klastrowania , w szczególności nie używaj algorytmów opartych na odległości lub gęstości, ponieważ informacje te były celowo (!) Stracony. Podejścia oparte na grafie sąsiedztwa mogą być w porządku, ale wtedy nie musisz wcześniej uruchamiać t-SNE, po prostu użyj sąsiadów natychmiast (ponieważ t-SNE próbuje zachować ten wykres nn w dużej mierze nienaruszony).

Więcej przykładów

Te przykłady zostały przygotowane do prezentacji artykułu (ale nie można go jeszcze znaleźć w tym artykule, ponieważ eksperymentowałem później)

Erich Schubert i Michael Gertz.
Wewnętrzne osadzenie t-stochastycznego sąsiada na potrzeby wizualizacji i wykrywania wartości odstających - lekarstwo na przekleństwo wymiaru?
W: Materiały z 10. międzynarodowej konferencji na temat wyszukiwania podobieństwa i aplikacji (SISAP), Monachium, Niemcy. 2017 r

Po pierwsze, mamy następujące dane wejściowe:

Ryba

Jak można się domyślić, jest to pochodna obrazu „pokoloruj mnie” dla dzieci.

Jeśli przeprowadzimy to przez SNE ( NIE t-SNE , ale poprzednik):

SNE fish

Wow, nasze ryby stały się całkiem morskim potworem! Ponieważ rozmiar jądra jest wybierany lokalnie, tracimy wiele informacji o gęstości.

Ale naprawdę będziesz zaskoczony wynikami t-SNE:

t-SNE fish

W rzeczywistości wypróbowałem dwie implementacje (ELKI i implementacje sklearn) i obie przyniosły taki wynik. Niektóre odłączone fragmenty, ale każdy z nich wygląda nieco spójnie z oryginalnymi danymi.

Dwa ważne punkty, aby to wyjaśnić:

  1. SGD opiera się na iteracyjnej procedurze udoskonalania i może utknąć w lokalnych optymach. W szczególności utrudnia to algorytmowi „przerzucenie” części danych, które dubluje, ponieważ wymagałoby to przemieszczania punktów przez inne, które powinny być oddzielne. Więc jeśli niektóre części ryby są dublowane, a inne części nie są dublowane, naprawienie tego może być niemożliwe.

  2. t-SNE wykorzystuje rozkład t w rzutowanej przestrzeni. W przeciwieństwie do rozkładu Gaussa stosowanego przez zwykły SNE, oznacza to, że większość punktów będzie się odpychać , ponieważ mają 0 powinowactwo w domenie wejściowej (Gaussian szybko otrzymuje zero), ale> 0 powinowactwo w domenie wyjściowej. Czasami (jak w MNIST) czyni to ładniejszą wizualizację. W szczególności może pomóc „podzielić” zestaw danych nieco bardziej niż w domenie wejściowej. To dodatkowe odpychanie często powoduje, że punkty bardziej równomiernie wykorzystują obszar, co może być również pożądane. Ale tutaj, w tym przykładzie, działanie odstraszające powoduje oddzielenie fragmentów ryby.

Możemy pomóc (w tym zestawie danych zabawki ) w pierwszym problemie, używając oryginalnych współrzędnych jako początkowego położenia, a nie losowych współrzędnych (jak zwykle używane z t-SNE). Tym razem obraz jest sklearn zamiast ELKI, ponieważ wersja sklearn miała już parametr do przekazania początkowych współrzędnych:

Ryba, t-SNE, z oryginalnymi współrzędnymi jako inicjalizacja

Jak widać, nawet przy „idealnym” umieszczeniu początkowym t-SNE „rozbije” rybę w wielu miejscach, które były pierwotnie połączone, ponieważ odpychanie Studenta-t w dziedzinie wyjściowej jest silniejsze niż powinowactwo Gaussa na wejściu przestrzeń.

Jak widać, t-SNE (i SNE też!) Są interesującymi technikami wizualizacji , ale należy się z nimi obchodzić ostrożnie. Wolę nie stosować k-średnich do wyniku! ponieważ wynik będzie mocno zniekształcony, a odległości i gęstość nie zostaną dobrze zachowane. Zamiast tego użyj raczej do wizualizacji.

Erich Schubert
źródło
1
Dziękuję za odpowiedź. Mogę sobie wyobrazić adaptacyjne metody klastrowania oparte na dzielnicach, ale czy są jakieś dobrze rozwinięte metody, które możesz polecić?
generic_user
1
CHAMAELEON jest prawdopodobnie najczęściej cytowany, ale wydaje się, że jest tylko plik binarny dostępny dla podstawowego kroku. Pomysł brzmi nieźle, ale szybko odczujesz te same efekty, które sprawia, że ​​t-SNE jest widoczny. Takich jak tendencja do „flokowania”, jak widać przy p = 20, problemy z piastami i piastami itp.
Erich Schubert
2
@AlexR: Perplexity służy do obliczania podobieństw w przestrzeni wielowymiarowej, którą t-sne próbuje następnie dopasować w 2D. Zmiana zakłopotania oznacza zmianę podobieństw, więc nie rozumiem, w jaki sposób porównywanie powstałych rozbieżności KL może mieć znaczenie.
ameba
1
@AlexR. „Tylko prawdopodobieństwo warunkowe przestrzeni niższych wymiarów zależy od zakłopotania” - to stwierdzenie jest błędne. Zakłopotanie jest używane do wyboru sigm dla eq (1), więc wpływa na cond. probs w pełnej przestrzeni.
ameba
1
Aby zapoznać się z pewnymi zastrzeżeniami i ładnymi efektami
Tom Wenseleers
34

Chciałbym wyrazić nieco odmienne zdanie na temat dobrze argumentowanej (+1) i bardzo pozytywnej odpowiedzi @ErichSchubert. Erich nie zaleca grupowania na wyjściu t-SNE i pokazuje przykłady zabawek, w których może to być mylące. Jego sugestią jest zastosowanie klastrowania do oryginalnych danych.

użyj t-SNE do wizualizacji (i wypróbuj różne parametry, aby uzyskać coś przyjemnego wizualnie!), ale raczej nie uruchamiaj później klastrowania, w szczególności nie używaj algorytmów opartych na odległości lub gęstości, ponieważ ta informacja została celowo (!) utracona.

Doskonale zdaję sobie sprawę ze sposobów, w jakie wyniki T-SNE mogą wprowadzać w błąd (patrz https://distill.pub/2016/misread-tsne/ ) i zgadzam się, że może przynieść dziwne wyniki w niektórych sytuacjach.

Rozważmy jednak kilka rzeczywistych danych wielowymiarowych.

Weź dane MNIST : 70000 jednocyfrowych zdjęć. Wiemy, że w danych jest 10 klas. Klasy te wydają się dobrze rozdzielone dla ludzkiego obserwatora. Jednak grupowanie danych MNIST w 10 klastrach jest bardzo trudnym problemem. Nie znam żadnego algorytmu klastrowego, który poprawnie klastrowałby dane w 10 klastrach; co ważniejsze, nie znam żadnej heurystyki klastrowej, która wskazywałaby, że w danych znajduje się 10 (nie więcej i nie mniej) klastrów. Jestem pewien, że najczęściej stosowane podejścia nie byłyby w stanie tego wskazać.

Ale zamiast tego zróbmy t-SNE. (Można znaleźć wiele liczb t-SNE zastosowanych do MNIST w Internecie, ale często są one nieoptymalne. Z mojego doświadczenia wynika, że ​​konieczne jest przeprowadzanie wczesnej przesady przez dość długi czas, aby uzyskać dobre wyniki. Poniżej używam perplexity=50, max_iter=2000, early_exag_coeff=12, stop_lying_iter=1000). Oto, co otrzymuję, po lewej bez etykiety, a po prawej kolorowe zgodnie z podstawową prawdą:

MNIST t-SNE

Twierdziłbym, że nieoznaczona reprezentacja t-SNE sugeruje 10 klastrów. Zastosowanie algorytmu grupowania opartego na dobrej gęstości, takiego jak HDBSCAN, ze starannie dobranymi parametrami pozwoli na grupowanie tych danych 2D w 10 klastrach.

W przypadku, gdy ktoś wątpi, że lewy wykres powyżej sugeruje 10 klastrów, oto, co otrzymuję dzięki sztuczce „późnej przesady”, w której dodatkowo uruchamiam max_iter=200iteracje exaggeration=4(ta sztuczka jest sugerowana w tym wspaniałym artykule: https://arxiv.org /abs/1712.09005 ):

MNIST t-SNE z późną przesadą

Teraz powinno być bardzo oczywiste, że istnieje 10 klastrów.

Zachęcam wszystkich, którzy uważają, że klastrowanie po t-SNE to zły pomysł, aby pokazać algorytm klastrowania, który osiągnąłby porównywalnie dobry wynik.

A teraz jeszcze bardziej prawdziwe dane.

W przypadku MNIST znamy podstawową prawdę. Rozważ teraz niektóre dane z nieznaną prawdą podstawową. Grupowanie i t-SNE są rutynowo stosowane do opisania zmienności komórek w danych o sekwencji RNA dla pojedynczej komórki. Np. Shekhar i in. W 2016 roku próbowano zidentyfikować skupiska wśród 27000 komórek siatkówki (w genomie myszy znajduje się około 20 000 genów, więc wymiarowość danych wynosi w zasadzie około 20 000; jednak zwykle zaczyna się od zmniejszenia wymiarowości z PCA do około 50). Robią t-SNE i osobno robią klastrowanie (skomplikowany potok klastrowania, po którym następuje łączenie klastrów itp.). Wynik końcowy wygląda przyjemnie:

wprowadź opis zdjęcia tutaj

Powodem, dla którego wygląda tak przyjemnie, jest to, że t-SNE tworzy wyraźnie odrębne klastry, a algorytm klastrowania daje dokładnie te same klastry. Miły.

Jeśli jednak zajrzysz do dodatków, zobaczysz, że autorzy wypróbowali wiele różnych metod grupowania. Wiele z nich wygląda okropnie na wykresie t-SNE, ponieważ np. Duży klaster centralny zostaje podzielony na wiele podklastrów:

wprowadź opis zdjęcia tutaj

Więc w co wierzysz: wynik twojego ulubionego algorytmu klastrowania wraz z ulubioną heurystyką do identyfikacji liczby klastrów lub co widzisz na wykresie t-SNE? Szczerze mówiąc, pomimo wszystkich niedociągnięć t-SNE, wierzę bardziej w t-SNE. W każdym razie nie rozumiem, dlaczego mam w to mniej wierzyć .

ameba
źródło
2
I w ostatnim przykładzie, czy nie jest to zasadniczo to, co zaobserwował @ErichSchubert: możesz uzyskać wizualnie „przyjemne” wyniki - które są oczywiście błędne? Jak w przypadku zakłopotania 20? Czy tSNE lubi oddzielać części (jak u ryb), które nie zostały rozdzielone? Czy wiesz, że klastry, które widzisz, są rzeczywiście osobnymi klastrami? Nie podoba mi się tam ta „czarna skrzynka”. Tak, bardziej wierzymy w takie wątki, ale co, jeśli się mylą?
Anony-Mousse,
1
Cóż, tSNE jest oparty na NN. Należy się z tym zgodzić. tSNE to dobry wybór do wizualizacji NN. Nie zachowuje jednak dobrze podobieństw, dlatego, jak rozumiem, należy go interpretować ostrożnie. Luka w tSNE nie oznacza dużej odległości.
Anony-Mousse,
1
+1 Ciekawe, jak działa UMAP w porównaniu z t-SNE.
Paul
1
@Paul: autor twierdzi, że ma wyższość UMAP, jeśli chodzi o czas obliczeń. W zestawie danych MNIST uważam, że UMAP generuje lepsze osadzanie niż t-SNE, ale nie jestem pewien w innych zestawach danych. O ile mi wiadomo, ostatnio dostępna jest wersja t-SNE CUDA, która jest znacznie szybsza niż poprzednia najszybsza t-SNE, ale nie mogłem zainstalować i przetestować.
SiXUlm
1
@SiXUlm github.com/KlugerLab/FIt-SNE działa znacznie szybciej niż Barnes-Hut t-SNE i często jest szybszy niż UMAP. Ponadto w wielu przypadkach można osiągnąć bardzo podobne osadzenie za pomocą t-SNE przy użyciu kilku dodatkowych poprawek, np. Na MNIST t-SNE z niewielką przesadą daje prawie to samo co UMAP, patrz przykładowy notatnik Python w repozytorium FIt-SNE.
ameba
6

Myślę, że z dużym zakłopotaniem t-SNE może zrekonstruować globalną topologię, jak wskazano w https://distill.pub/2016/misread-tsne/ .

Z obrazu ryby pobrałem próbkę 4000 punktów dla t-SNE. Z dużym zakłopotaniem (2000) obraz ryb został praktycznie zrekonstruowany.

Oto oryginalny obraz. Oryginalny obraz

Oto obraz zrekonstruowany przez t-SNE z zakłopotaniem = 2000. zrekonstruowany obraz t-SNE (zakłopotanie = 2000)

renxwise
źródło
8
Jeśli wybierzesz tak duże problemy, to już nie jest tak naprawdę. Każdy punkt to w przybliżeniu codzienny sąsiad. Nie jest już lokalny. Tak, obraz 2d można następnie w przybliżeniu odtworzyć, ponieważ jest to obraz 2d. Ale wcale nie robienie całej rzeczy jest łatwiejsze.
Anony-Mousse,
1
Moim zdaniem tSNE z dużym zakłopotaniem może zrekonstruować globalną topologię. Obraz 2d jest przykładem, ponieważ jego wewnętrzna wymiarowość wynosi 2. Rzeczywiste zastosowanie tSNE powinno wybrać właściwe zakłopotanie zgodnie z celem uchwycenia cech lokalnych lub globalnych.
renxwise
1
Tak duże zakłopotanie oznacza, że ​​używasz zbyt dużego „jądra” i skutecznie po prostu używasz odległości. Następnie prawdopodobnie degeneruje się do przybliżonego i bardzo drogiego MDS. Następnie użyj MDS. SNE / tSNE naprawdę należy stosować z małymi problemami i lokalnymi dzielnicami.
Erich Schubert
3
Dokładnie. Gdy kłopot jest wystarczająco duży, tSNE jest rzeczywiście zbliżony do MDS, co pokazuje, że tSNE może również uchwycić globalną strukturę. Zatem stwierdzenia, że ​​tSNE może przechwytywać tylko struktury lokalne, są niepoprawne. W odróżnieniu od MDS, tSNE może balansować między strukturami lokalnymi i globalnymi poprzez wybór zakłopotania. Oczywiście wybór zakłopotania zależy od zestawu danych.
renxwise
Czy istnieje jakaś ogólna zasada wyboru prawdopodobnego zakłopotania?
Catbuilts
5

Na podstawie posiadanych przez nas dowodów matematycznych metoda ta może technicznie zachować odległości! dlaczego wszyscy ignorujecie tę funkcję! t- SNE przekształca wielowymiarowe odległości euklidesowe między próbkami w prawdopodobieństwa warunkowe, które reprezentują podobieństwa. Próbowałem t- SNE z ponad 11 000 próbek (w kontekście genomiki) równolegle z różnymi algorytmami klastrowania konsensusowego, w tym klastrami spektralnymi, powinowactwem i, co ważne, z klastrem GMM (który jest algorytmem grupowania opartym na gęstości!). W rezultacie znalazłem bardzo dobry zgodny wynik między dwoma podejściami ( t-SNE vs. algorytmy klastrowania konsensusowego). Wierzę, że zintegrowanie t-SNE z algorytmami klastrowego konsensusu może zapewnić najlepszy dowód na istnienie lokalnych i globalnych struktur danych.

Reza Rafiee
źródło
Czy istnieją parametry, które będą miały wpływ na prawdopodobieństwo zachowania odległości przez t-SNE?
Keith Hughitt
To nie są algorytmy grupowania konsensusu. Klastrowanie konsensusowe jest rodzajem uczenia się w zespole, które agreguje wyniki powtarzania algorytmu klastrowania z pewnymi zmianami parametrów lub danych wejściowych, w celu uzyskania końcowego wyniku klastrowania. Możesz stosować konsensusowe metody klastrowania z klastrami spektralnymi lub GMM, a nawet dowolnym algorytmem klastrowania, ale moja uwaga w twojej terminologii jest trochę odległa, to wszystko :)
Christopher John
1

Możesz wypróbować algorytm klastrowania DBSCAN. Również kłopot z tsne powinien być mniej więcej tego samego rozmiaru co najmniejszy spodziewany klaster.

James LI
źródło
0

Osobiście doświadczyłem tego raz, ale nie z t-SNE lub PCA. Moje oryginalne dane znajdują się w 15-wymiarowej przestrzeni. Używając UMAP do zredukowania go do osadzania 2D i 3D, otrzymałem 2 doskonale i wizualnie oddzielne klastry na wykresach 2D i 3D. Zbyt dobre by było prawdziwe. Ale kiedy „spojrzałem” na oryginalne dane z diagramu trwałości, zdałem sobie sprawę, że istnieje znacznie więcej „znaczących” klastrów, nie tylko 2.

Grupowanie wyników techniki zmniejszania wymiarów musi być wykonywane z dużą ostrożnością, w przeciwnym razie każda interpretacja może być bardzo myląca lub błędna, ponieważ zmniejszenie wymiaru z pewnością spowoduje utratę cech (może głośne lub prawdziwe cechy, ale z góry nie wiem, które). Moim zdaniem możesz ufać / interpretować klastry, jeśli:

  • Klastry w rzutowanych danych odpowiadają / potwierdzają pewną klasyfikację zdefiniowaną a priori (pomyśl o zestawie danych MNIST, gdzie klastry rzutowanych danych bardzo dobrze pasują do klasyfikacji cyfr) i / lub,

  • Istnieje możliwość potwierdzenia obecności tych klastrów w oryginalnych danych przy użyciu innych metod, takich jak diagramy trwałości. Liczenie tylko liczby podłączonych komponentów można wykonać w dość rozsądnym czasie.

SiXUlm
źródło
Dlaczego bardziej zaufałeś „diagramowi trwałości” niż UMAP? Nie sądzę, że patrząc na diagram trwałości można opisać jako „patrząc na oryginalne dane” ...
Ameba
Masz rację. Diagram trwałości pokazuje tylko niektóre cechy oryginalnych danych, najczęściej połączone komponenty, 1-wymiarowe otwory i znacznie rzadziej, 2 lub więcej wymiarowe otwory ze względu na kosztowne obliczenia. Powinienem więc powiedzieć, że mogę tylko częściowo „spojrzeć” na oryginalne dane, patrząc na odpowiedni diagram trwałości. Ale mogę zaufać temu, co obserwuję na tym diagramie trwałości, ponieważ jest on zbudowany bezpośrednio z oryginalnych danych.
SiXUlm
Natomiast za pomocą UMAP lub innych technik redukcji wymiarów pracujemy tylko z rzutowaną / zmodyfikowaną wersją oryginalnych danych. Jak wskazano najczęściej głosowaną odpowiedź, grupowanie może się różnić w zależności od wyboru parametrów.
SiXUlm