Czy można znaleźć centroidy klastrów w środkach jądra K?
Przypuszczać ${x_1, \ldots, x_N}$ to punkty danych, które musimy znaleźć $K$ klastry używające Kernel K Means.
Niech będzie jądro $Ker$ (nie mylić z $K$ liczba klastrów)
Pozwolić $\phi$ być niejawnym mapowaniem wywołanym przez to jądro.
Teraz jeśli $\phi$były skończone, nie było problemu. Jednak załóżmy$phi$ być nieskończenie wymiarowym, tak wywołało jądro RBF
Wszędzie, gdzie czytałem o jądrze K oznacza, że mówi tylko, że możemy zrobić jądro K oznacza używając
$||\phi(x_i) - \phi(x_j)||^2 = Ker(x_i, x_i) + Ker(x_j, x_j) - 2Ker(x_i, x_j) \;\; \ldots(1)$
Rozumiem, ale nie jest to takie proste dla mojego mózgu i nikt nie podaje jednoznacznego algorytmu dla środka jądra K, co pozostawia mnie z następującymi wątpliwościami:
W jakiej przestrzeni inicjalizujemy centroidy K? W pierwotnej przestrzeni lub przestrzeni wywołanej przez$\phi$? Domyślam się, że inicjalizujemy się w oryginalnej przestrzeni tylko dlatego, że nie możemy nawet pojąć punktów danych w przestrzeni wywołanych przez$\phi$ Załóżmy, że inicjalizujemy je losowo $K$ centroidy $\mu_1, \ldots \mu_K$tylko w oryginalnej przestrzeni. (Proszę mnie poprawić, jeśli źle zakładam)
Po inicjalizacji musimy przypisać każdy punkt danych do jednego z klastrów. Załóżmy, że chcemy przypisać$x_n$ do klastra, można to łatwo zrobić za pomocą (1) do obliczenia $\mu_k$ = $\text{arg min}_j\; ||\phi(x_n) - \phi(\mu_j)||^2$
Jak po przypisaniu klastrów obliczyć nowe centroidy? Oczywiście nie mogę znieść myśli w przestrzeni wywołanej przez$\phi$ ponieważ jest nieskończenie wymiarowy, więc co mam teraz zrobić?
Jakie jest obejście tego problemu? Zakładam, że w jakiś sposób nie musimy w ogóle przechowywać centroidów. Ale nie mogę wymyślić, jak to osiągnąć.
Przeczytałem. Znajdowanie centrów klastrów w klastrach k-średnich jądra
Jednak odpowiedź wiki społeczności nie wyjaśnia, gdzie $(1)$ pochodzi z.
Odpowiedzi
K-średnie jądra są równoważne zwykłym k-środkom działającym w przestrzeni cech wywołanej przez jądro. Dlatego centroidy żyją w przestrzeni cech, która, jak wspomniałeś, może być nieskończenie wymiarowa. Podczas formułowania algorytmu uczenia się za pomocą sztuczki jądra nigdy nie musimy bezpośrednio dotykać przestrzeni funkcji. Wszystkie operacje w przestrzeni funkcji są wykonywane niejawnie przy użyciu funkcji jądra. Dlatego nigdy nie zajmujemy się bezpośrednio centroidami w k-średnich jądra. Zamiast tego pracujemy z przypisaniami klastrów, jak wyjaśnię poniżej.
K-oznacza w przestrzeni funkcji
Algorytm Lloyda jest standardową metodą (w przybliżeniu) rozwiązywania problemu k-średnich. Oto uogólnienie, które działa bezpośrednio w przestrzeni funkcji. Pozwolić$X = \{x_1, \dots, x_n\}$ być punktami danych i $\phi(\cdot)$ być funkcją, która odwzorowuje punkt z przestrzeni wejściowej na przestrzeń cech.
- Zainicjuj $K$ klastry $C_1, \dots, C_K$, gdzie każdy klaster $C_j$ to zbiór zawierający $n_j$ punktów, a każdy punkt należy do dokładnie jednego klastra.
Powtarzaj do konwergencji (bez zmian w członkostwie w klastrze):
Dla każdego klastra $C_j$, środek ciężkości (w przestrzeni elementów) to:
$$\mu_j = \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \tag{1}$$
Za każdy punkt $x_i$znajdź indeks $a_i$ gromady, której środek ciężkości jest najbliżej (w przestrzeni cech).
$$a_i = \arg \min_j \ \|\phi(x_i) - \mu_j\|^2 \tag{2}$$
$$= \arg \min_j \ \langle \phi(x_i), \phi(x_i) \rangle + \langle \mu_j, \mu_j \rangle - 2 \langle \phi(x_i), \mu_j \rangle \tag{3}$$
$$= \arg \min_j \ \langle \mu_j, \mu_j \rangle - 2 \langle \phi(x_i), \mu_j \rangle \tag{4}$$
- Zaktualizuj klastry. Każdy punkt staje się członkiem klastra z najbliższą centroidą:
$$C_j = \{x_i \mid a_i = j\}$$
Uwaga: $\langle \cdot, \cdot \rangle$oznacza iloczyn skalarny. Równanie$(3)$wynika z relacji między normą a produktem wewnętrznym. Pierwszy termin$\langle \phi(x_i), \phi(x_i) \rangle$ nie zależy od klastra, więc możemy go porzucić, podając równanie $(4)$.
Używanie triku z jądrem
Załóżmy, że mamy funkcję jądra $k(\cdot, \cdot)$która oblicza iloczyn iloczynu wewnętrznego w przestrzeni cech. Więc$k(x, x') = \langle \phi(x), \phi(x') \rangle$. W powyższym algorytmie możemy zastąpić iloczyn skalarny obliczeniami funkcji jądra, działając w ten sposób niejawnie w przestrzeni cech. Nazywa się to sztuczką jądra.
Najpierw połącz kroki 2 i 3, zastępując definicję centroid w równaniu $(1)$ do najbliższego centroidu wyszukiwania w równaniu $(4)$:
$$\arg \min_j \ \left \langle \frac{1}{n_j} \sum_{x \in C_j} \phi(x), \frac{1}{n_j} \sum_{x' \in C_j} \phi(x') \right \rangle - 2 \left \langle \phi(x_i), \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \right \rangle \tag{5}$$
Ponieważ iloczyn skalarny jest dwuliniowy, możemy to przepisać jako:
$$\arg \min_j \ \frac{1}{n_j^2} \sum_{x \in C_j} \sum_{x' \in C_j} \langle \phi(x), \phi(x') \rangle - \frac{2}{n_j} \sum_{x \in C_j} \langle \phi(x_i), \phi(x) \rangle \tag{6}$$
Zastąp produkty wewnętrzne ocenami funkcji jądra:
$$\arg \min_j \ \frac{1}{n_j^2} \sum_{x \in C_j} \sum_{x' \in C_j} k(x, x') - \frac{2}{n_j} \sum_{x \in C_j} k(x_i, x) \tag{7}$$
Za każdy punkt $x_i$, to mówi, jak znaleźć klaster z najbliższą centroidą, bez jawnego obliczania centroid w przestrzeni cech. Można go zastąpić krokami 2 i 3 w powyższym algorytmie.