¿Es posible encontrar centroides de clúster en las medias del núcleo K?

Nov 24 2020

Suponer ${x_1, \ldots, x_N}$ son los puntos de datos y tenemos que encontrar $K$ clústeres que utilizan Kernel K Means.

Deja que el kernel sea $Ker$ (no confundir con $K$ número de grupos)

Dejar $\phi$ ser el mapeo implícito inducido por este kernel.

Ahora si $\phi$eran de dimensión finita, no había ningún problema. Sin embargo, asuma$phi$ para ser de dimensión infinita, como lo ha inducido el kernel RBF

Ahora, en todos los lugares que he leído sobre los medios del kernel K, solo dice que podemos hacer los medios del kernel K 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)$

Entiendo esto, pero no es tan simple para mi cerebro y nadie da un algoritmo explícito para los medios del kernel K, lo que me deja con las siguientes dudas:

  1. ¿En qué espacio inicializamos los centroides K? En el espacio original, o el espacio inducido por$\phi$? Supongo que inicializamos en el espacio original solo porque ni siquiera podemos comprender los puntos de datos en el espacio inducidos por$\phi$ Supongamos que inicializamos aleatoriamente estos $K$ centroides $\mu_1, \ldots \mu_K$en el espacio original solamente. (Por favor corríjame si asumo mal)

  2. Después de la inicialización, tenemos que asignar cada punto de datos a uno de los clústeres. Supongamos que queremos asignar$x_n$ a un clúster, esto se puede hacer fácilmente usando (1) para calcular $\mu_k$ = $\text{arg min}_j\; ||\phi(x_n) - \phi(\mu_j)||^2$

  3. Después de asignar grupos, ¿cómo calculo los nuevos centroides? Obviamente, no puedo tomar mal en el espacio inducido por$\phi$ como es de dimensión infinita, entonces, ¿qué hago ahora?

¿Cuál es la solución a este problema? Supongo que hay alguna forma de que no tengamos que almacenar los centroides en absoluto. Pero no puedo pensar en cómo lograrlo.

He leído Encontrar los centros de clústeres en la agrupación de k-medias del kernel

Sin embargo, la respuesta de la wiki de la comunidad no explica dónde $(1)$ viene de.

Respuestas

1 user20160 Nov 24 2020 at 15:17

Kernel k-means es equivalente a k-means regulares que operan en el espacio de características inducido por el kernel. Por lo tanto, los centroides viven en un espacio de características que, como mencionaste, puede tener una dimensión infinita. Al formular un algoritmo de aprendizaje utilizando el truco del kernel, nunca necesitamos tocar el espacio de características directamente. Todas las operaciones en el espacio de características se realizan implícitamente utilizando la función del kernel. Por lo tanto, nunca tratamos directamente con los centroides en las k-medias del núcleo. En cambio, trabajamos con las asignaciones de clúster, como explicaré a continuación.

K-medias en el espacio de características

El algoritmo de Lloyd es el método estándar para (aproximadamente) resolver el problema de k-medias. Aquí hay una generalización que funciona directamente en el espacio de características. Dejar$X = \{x_1, \dots, x_n\}$ ser los puntos de datos y $\phi(\cdot)$ ser una función que mapea un punto del espacio de entrada al espacio de características.

  1. Inicializar $K$ racimos $C_1, \dots, C_K$, donde cada grupo $C_j$ es un conjunto que contiene $n_j$ puntos, y cada punto es miembro de exactamente un grupo.

Repita hasta la convergencia (sin cambios en la membresía del clúster):

  1. Para cada grupo $C_j$, el centroide (en el espacio de características) es:

    $$\mu_j = \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \tag{1}$$

  2. Por cada punto $x_i$, encuentra el índice $a_i$ del grupo cuyo centroide es el más cercano (en el espacio de características).

$$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. Actualice los clústeres. Cada punto se convierte en miembro del clúster con el centroide más cercano:

$$C_j = \{x_i \mid a_i = j\}$$

Nota: $\langle \cdot, \cdot \rangle$denota el producto interior. Ecuación$(3)$se deriva de la relación entre la norma y el producto interior. El primer término$\langle \phi(x_i), \phi(x_i) \rangle$ no depende del clúster, por lo que podemos eliminarlo, dando la ecuación $(4)$.

Usando el truco del kernel

Supongamos que tenemos una función de kernel $k(\cdot, \cdot)$que calcula productos internos en el espacio de características. Entonces$k(x, x') = \langle \phi(x), \phi(x') \rangle$. Podemos reemplazar productos internos en el algoritmo anterior con evaluaciones de funciones del núcleo, operando así implícitamente en el espacio de características. A esto se le llama el truco del kernel.

Primero, combine los pasos 2 y 3 sustituyendo la definición de centroides en la ecuación $(1)$ en la búsqueda de centroide más cercana en la ecuación $(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}$$

Dado que el producto interno es bilineal, podemos reescribirlo 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}$$

Reemplace los productos internos con evaluaciones de funciones del 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}$$

Por cada punto $x_i$, esto dice cómo encontrar el grupo con el centroide más cercano, sin calcular explícitamente los centroides en el espacio de características. Se puede sustituir por los pasos 2 y 3 del algoritmo anterior.