Jak działa metoda redukcji wymiarów t-SNE?

t-sne

– Hej tatusiu, co dzisiaj robiłeś?– spytała się Jagódka

– Dzisiaj wykorzystałem inną metodą do redukcji wymiarów niż ostatnio.

– A po co?

– Pamiętasz jak ostatnio mówiliśmy o przykładzie wyboru zabawek? [LINK]

– Tak – uśmiechnęła się

– To tym razem można byłoby to zrobić inaczej. Z tych pięciu zabawek: trzech pand i dwóch sióstr cel był by wybrać tylko dwie. Tym razem zamiast szukać najróżniejszych można byłoby szukać najbardziej podobnych. Dzięki temu na wycieczkę można byłoby wziąć dwie siostry: Annę i Elsę by te siostry mogły się ze sobą bawić.

– Nie wiem po co Ci tatusiu tyle różnych metod – powiedziała Jagódka.

– Po to, by je poznać i zawsze móc dobierać najlepszą do danego problemu – odpowiedziałem i po czym uśmiechnąłem się.

W poprzednim poście opisałem jak działa PCA, którego historia sięga według niektórych źródeł nawet 1901 roku. W tym wpisie omówię alternatywną metodę redukcji wymiarów t-SNE opracowaną przez Laurens van der Maatens i Geoffrey Hinton w 2008 roku.

Co to jest t-SNE?

Skrót t-SNE oznacza stochastyczna metoda porządkowania sąsiadów w oparciu o rozkład t (t-Distributed Stochastic Neighbor Embedding). Jest to nieliniowa i nienadzorowana technika stosowana przede wszystkim do eksploracji i wizualizacji danych wielowymiarowych.

Ogólna idea działania t-SNE

Algorytm t-SNE oblicza miarę podobieństwa między parami w przestrzeni o dużych wymiarach i przestrzeni o małych wymiarach. Następnie próbuje zoptymalizować te dwie miary podobieństwa. Mówiąc prościej, to t-SNE daje intuicję w jaki sposób dane są rozmieszczone w przestrzeni.

Również warto wspomnieć, że t-SNE można użyć do wybrania liczby klastrów w przypadku zagadnienia klasteryzacji. Jednak warto mieć na uwadze, że t-SNE nie jest podejściem grupującym i służy wyłącznie do eksploracji.

Ale jak t-SNE działa?

Super opowiedział o tym Josh Stramer na YouTube. W poniższym przykładzie wykorzystam jego wizualizacje by nie wymyślać koła na nowo :).

Weźmy jako przykład zbiór 12 punktów należących do trzech klas (niebieskie, czerwone i pomarańczowe).

tsne

Dla uproszczenia wyjaśniania metody podzielmy sposób działania algorytmu na mniejsze kroki.

Krok 1. Wyliczenie podobieństw wszystkich naszych danych

Na początku określamy zasięg w ramach którego będziemy patrzeć na punkty. Zasięg ten (możecie myśleć jako zakres kuli w wielowymiarowej przestrzeni) określić można za pomocą tzw. perplexity. Najczęściej zakres parametru wynosi od 5 do 50.

W naszym przykładzie jest na tyle mało danych, że możemy przyjąć wyliczania podobieństw między wszystkimi punktami.

Wybieramy pierwszy dowolny punkt (zaznaczony na szaro). Następnie wyliczamy odległość między nim a wybranym innym punktem. Dla tego szarego punktu rysujemy wyśrodkowany w tym punkcie rozkład normalny. A teraz nanosimy na niego wybrany wczesnej punkt zgodnie z wyliczoną odległością.

tsne

Dzięki używaniu rozkładu normalnego to jeśli punkty są daleko od siebie mają małe podobieństwo, a jeśli blisko to duże.

tsne

Tą operacje powtarzamy dla wszystkich punktów w wcześniej określonym zasięgu.

tsne

Mając wyliczone te dystanse naniesione na rozkład normalny zamieniamy je na zestaw prawdopodobieństw wszystkich punktów (skalujemy by wszystkie wartości sumowały się do 1). Daje to tam zestaw prawdopodobieństw wszystkich punktów.

tsne

Oczywiście to ćwiczenie powtarzamy dla wszystkich punktów w naszym zbiorze.

Krok 2. Wyliczenie losowych podobieństw

Tutaj jest ten element, który sprawia że nie można odtworzyć wyników t-SNE (moim zdaniem największa wada tej metody).

Dosłownie losowo rysujemy jak projekcja będzie wyglądać w mniejszym wymiarze (taki wymiar jaki określimy). W tym przypadku zmieniamy przestrzeń dwu-wymiarową (2D) na jedno-wymiarową (1D).

tsne

Następnie można już powiedzieć, że krok 2 jest bardzo podobny do kroku 1, ale zamiast zastosowania rozkładu normalnego użyty jest rozkładu t Studenta o jednym stopniu swobody, który jest również znany jako rozkład Cauchy’ego. Czyli :

a) wyliczenie wszystkich odległości

tsne

b) wyliczenie podobieństw

tnse

c) wyliczenie drugiego zestawu prawdopodobieństw w przestrzeni niskiego wymiaru (warto zwrócić uwagę, że ta macierz była losowa dlatego nie będzie tak ładnie uporządkowana jak pierwotna).

tsne

Warto dodać jeszcze, że autorzy metody zarekomendowali wybór rozkładu t-Studenta, ponieważ ma cięższe ogony niż rozkład normalny. Ciężkie ogony tak naprawdę pozwalają na lepsze modelowanie odległych od siebie punktów.

tsne

Krok 3.  Odzwierciedlenie zestawów prawdopodobieństw.

Ostatnim krokiem jest to, że chcemy, aby ten zestaw prawdopodobieństw z przestrzeni niskiego wymiaru jak najlepiej odzwierciedlał te z przestrzeni wysokiego wymiaru. Tak naprawdę chcemy, aby te dwie struktury zestawów były podobne.

tsne

Różnicę między rozkładami prawdopodobieństwa przestrzeni mierzymy za pomocą dywergencji Kullbacka-Lieblera (KL). Daje ono podejście asymetryczne, które skutecznie porównuje wartości obu macierzy prawdopodobieństw.  Dodatkowo metoda używa gradientu, aby zminimalizować naszą funkcję kosztu KL.

tsne

t-SNE vs PCA

Dla porównania zebrałem największe różnice pomiędzy dwoma metodami:

  • PCA jest techniką matematyczną, ale t-SNE jest probabilistyczny. Czasami w t-SNE różne przebiegi z tymi samymi hiperparametrami mogą dawać różne wyniki, podczas gdy dla PCA zawsze będzie to ten sam wynik. I moim zdaniem to jest największa wada t-SNE.
  • PCA jest techniką liniowej redukcji wymiarów, która dąży do maksymalizacji wariancji. Zatem polega gównie wy różne punkty umieszczać daleko od siebie w reprezentacji niższego wymiaru. Może to prowadzić do kiepskiej wizualizacji szczególnie w przypadku nieliniowych struktur, np. struktura naleśnika.
  • t-SNE w przeciwieństwie do PCA zachowuje odległości pomiędzy parami odwzorowując nieliniowość i jest w stanie zinterpretować złożoną zależności wielomianową między cechami
  • t-SNE jest drogi obliczeniowo. W przypadku większych próbek (>100.000) i dużej ilości wymiarów (>100) wyliczenie t-SNE może potrwać nawet kilka godzin, gdzie PCA zakończy się w kilka sekund lub minut.

Przykłady

Znamy teorię, która stoi za t-SNE. Zatem przejdźmy do dwóch przykładów rozpoczynając od wczytania odpowiednich bibliotek:

import matplotlib.pyplot as plt
import seaborn as sns

from sklearn.manifold import TSNE
from sklearn import datasets

from mpl_toolkits.mplot3d import Axes3D

1) Swissroll

Są to dane w specyficzny sposób układający się w zwinięty naleśnik.

swissroll, color = datasets.make_swiss_roll(n_samples=5000, noise=0.1, random_state=42)

Sprawdźmy jeszcze jak te dane wyglądają w rzucie trójwymiarowym (3D).

fig = plt.figure(figsize=(10, 7))
ax = fig.add_subplot(111, projection='3d')

print(f'Rozmiar danych (shape): {swissroll.shape}')
ax.scatter(swissroll[:,0], swissroll[:,1], swissroll[:,2], marker='x', c=color);
swissroll

Teraz zobaczmy jak zwiększając „perplexity” zmienia się wygląd wizualizacji.

 for perplexity in [5, 10, 30, 50]:
    print(f'Perplexity = {perplexity}')
    X_tsne = TSNE(learning_rate=100, perplexity=perplexity).fit_transform(swissroll)
    fig = plt.figure(figsize=(10, 10))
    ax = plt.axes(frameon=False)
    plt.setp(ax, xticks=(), yticks=())
    plt.subplots_adjust(left=0.0, bottom=0.0, right=1.0, top=0.9, wspace=0.0, hspace=0.0)
    plt.scatter(X_tsne[:, 0], X_tsne[:, 1], c=color, marker="x")
    plt.show();
t-sne
t-sne

Na powyższym przykładzie w miarę łatwo dostrzec, że zwiększając zasięg sąsiadów coraz ładniej dane są „rozwałkowywane” w przestrzeni 2D.

2) Porównanie banków

Pamiętacie przykład z PCA? Wykorzystałem tutaj te same dane by porównać wyniki:

import pandas as pd
from sklearn.preprocessing import MinMaxScaler, StandardScaler, LabelEncoder

def apply_scalers(df, columns_to_exclude=None):
    if columns_to_exclude:
        exclude_filter = ~df.columns.isin(columns_to_exclude) 
    else:
        exclude_filter = ~df.columns.isin([]) 
    for column in df.iloc[:, exclude_filter].columns:
        df[column] = df[column].astype(float)

    df.loc[:, exclude_filter] = StandardScaler().fit_transform(df.loc[:, exclude_filter])
    return df

df = apply_scalers(pd.read_excel('../data/data.xlsx', sheet_name='dataframe'), columns_to_exclude=['Nazwa'])

oraz zwizualizujmy sobie wyniki tak jak wcześniej:

import pandas as pd
import seaborn as sns

import plotly.plotly as py
import plotly.graph_objs as go
from plotly.offline import download_plotlyjs, init_notebook_mode, plot, iplot

init_notebook_mode(connected=True)

# kolumny do wykluczenia (te na których nie chcemy PCA)
exclude_filter = ~df.columns.isin(['Nazwa']) 

X_tsne = TSNE(learning_rate=10, perplexity=5).fit_transform(df.loc[:, exclude_filter])

trace0 = go.Scatter(
    x = X_tsne[:, 0],
    y = X_tsne[:, 1],
    text=df['Nazwa'],
    textposition="top center",
    name = 'Piony',
    mode = 'markers+text',
    marker = dict(
        size = 10,
        color = 'rgb(228,26,28)',
        line = dict(
            width = 1,
            color = 'rgb(0, 0, 0)'
        )
    )
)

data = [trace0]

layout = dict(title = 'Podobieństwo Banków na podstawie t-SNE'
             )

fig = dict(data=data, layout=layout)
iplot(fig, filename='styled-scatter')
t-sne

Wyszły bardzo ciekawe wyniki! Okazuje się, że te wyniki grup zbliżonych do siebie Banków są bardzo zbliżone do metody PCA.

Powodzenia w Waszych redukcjach wymiarów!

Pozdrawiam serdecznie

podpis Mirek
.

2 Comments on “Jak działa metoda redukcji wymiarów t-SNE?”

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *