É possível encontrar centróides de cluster no kernel K significa?
Suponha ${x_1, \ldots, x_N}$ são os pontos de dados e temos que encontrar $K$ clusters usando Kernel K Means.
Deixe o kernel ser $Ker$ (não confundir com $K$ número de clusters)
Deixei $\phi$ ser o mapeamento implícito induzido por este kernel.
Agora se $\phi$eram de dimensão finita, não havia problema. No entanto, assuma$phi$ ser infinita dimensional, tal induziu pelo kernel RBF
Agora, em todos os lugares que li sobre os meios K do kernel, só diz que podemos fazer os meios K do kernel usando
$||\phi(x_i) - \phi(x_j)||^2 = Ker(x_i, x_i) + Ker(x_j, x_j) - 2Ker(x_i, x_j) \;\; \ldots(1)$
Eu entendo isso, mas não é tão simples para o meu cérebro e ninguém dá um algoritmo explícito para meios de kernel K, o que me deixa com as seguintes dúvidas:
Em que espaço inicializamos os centróides K? No espaço original, ou o espaço induzido por$\phi$? Eu estou supondo que inicializamos no espaço original apenas porque não podemos nem mesmo compreender os pontos de dados no espaço induzidos por$\phi$ Suponha que inicializemos aleatoriamente estes $K$ centróides $\mu_1, \ldots \mu_K$apenas no espaço original. (Por favor, me corrija se eu presumir errado)
Após a inicialização, temos que atribuir cada ponto de dados a um dos clusters. Suponha que queremos atribuir$x_n$ para um cluster, isso pode ser feito facilmente usando (1) para calcular $\mu_k$ = $\text{arg min}_j\; ||\phi(x_n) - \phi(\mu_j)||^2$
Depois de atribuir clusters, como calculo os novos centróides? Obviamente, não posso entender o significado no espaço induzido por$\phi$ como é infinito dimensional, então o que eu faço agora?
Qual é a solução alternativa para esse problema? Estou assumindo que existe uma maneira de não precisarmos armazenar os centróides. Mas não consigo pensar em como fazer isso.
Eu li Encontrando os centros de cluster no cluster k-means kernel
No entanto, a resposta do wiki da comunidade não explica onde $(1)$ vem de.
Respostas
O kernel k-means é equivalente ao k-means regular operando no espaço de recursos induzido pelo kernel. Portanto, os centróides vivem em um espaço de recursos que, como você mencionou, pode ser infinito. Ao formular um algoritmo de aprendizado usando o truque do kernel, nunca precisamos tocar o espaço de recursos diretamente. Todas as operações no espaço de recursos são realizadas implicitamente usando a função de kernel. Portanto, nunca lidamos diretamente com os centróides no kernel k-means. Em vez disso, trabalhamos com as atribuições de cluster, como explicarei a seguir.
K-means no espaço de recursos
O algoritmo de Lloyd é o método padrão para (aproximadamente) resolver o problema de k-means. Aqui está uma generalização que funciona diretamente no espaço de recursos. Deixei$X = \{x_1, \dots, x_n\}$ sejam os pontos de dados e $\phi(\cdot)$ ser uma função que mapeia um ponto do espaço de entrada para o espaço do recurso.
- Inicializar $K$ clusters $C_1, \dots, C_K$, onde cada cluster $C_j$ é um conjunto contendo $n_j$ pontos, e cada ponto é membro de exatamente um cluster.
Repita até a convergência (sem mudança na associação do cluster):
Para cada cluster $C_j$, o centróide (no espaço do recurso) é:
$$\mu_j = \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \tag{1}$$
Para cada ponto $x_i$, encontre o índice $a_i$ do cluster cujo centróide está mais próximo (no espaço de recursos).
$$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}$$
- Atualizar clusters. Cada ponto se torna um membro do cluster com o centróide mais próximo:
$$C_j = \{x_i \mid a_i = j\}$$
Nota: $\langle \cdot, \cdot \rangle$denota o produto interno. Equação$(3)$decorre da relação entre a norma e o produto interno. O primeiro termo$\langle \phi(x_i), \phi(x_i) \rangle$ não depende do cluster para que possamos eliminá-lo, dando a equação $(4)$.
Usando o truque do kernel
Suponha que temos uma função de kernel $k(\cdot, \cdot)$que calcula produtos internos no espaço de recursos. assim$k(x, x') = \langle \phi(x), \phi(x') \rangle$. Podemos substituir produtos internos no algoritmo acima por avaliações de função de kernel, operando assim implicitamente no espaço de recursos. Isso é chamado de truque do kernel.
Primeiro, combine as etapas 2 e 3 substituindo a definição de centróides na equação $(1)$ na pesquisa de centróide mais próxima na equação $(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}$$
Como o produto interno é bilinear, podemos reescrever isso como:
$$\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}$$
Substitua os produtos internos por avaliações de função do kernel:
$$\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}$$
Para cada ponto $x_i$, isso diz como encontrar o cluster com o centróide mais próximo, sem computar explicitamente os centróides no espaço de recursos. Ele pode ser substituído pelas etapas 2 e 3 do algoritmo acima.