Grupowanie na wyjściu t-SNE

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?

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).

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

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

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ą:

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.

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:

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):

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:

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:

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.

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ą:

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 ):

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:

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:

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ć .

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.

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

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.

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.

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.