Czy można znaleźć centroidy klastrów w środkach jądra K?

Nov 24 2020

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:

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

  2. 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$

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

1 user20160 Nov 24 2020 at 15:17

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.

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

  1. 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}$$

  2. 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}$$

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