Est-il possible de trouver des centroïdes de cluster dans les moyennes du noyau K?
Supposer ${x_1, \ldots, x_N}$ sont les points de données et nous devons trouver $K$ clusters utilisant Kernel K Means.
Que le noyau soit $Ker$ (ne pas confondre avec $K$ nombre de clusters)
Laisser $\phi$ être le mappage implicite induit par ce noyau.
Maintenant si $\phi$étaient de dimension finie, il n'y avait pas de problème. Cependant, supposons$phi$ être de dimension infinie, tel a induit par le noyau RBF
Maintenant, partout où j'ai lu sur les moyens du noyau K, cela dit seulement que nous pouvons faire des moyens du noyau K en utilisant
$||\phi(x_i) - \phi(x_j)||^2 = Ker(x_i, x_i) + Ker(x_j, x_j) - 2Ker(x_i, x_j) \;\; \ldots(1)$
Je comprends cela, mais ce n'est pas si simple pour mon cerveau et personne ne donne un algorithme explicite pour le noyau K, ce qui me laisse les doutes suivants:
Dans quel espace initialisons-nous les centroïdes K? Dans l'espace d'origine, ou l'espace induit par$\phi$? Je suppose que nous initialisons dans l'espace d'origine uniquement parce que nous ne pouvons même pas comprendre les points de données dans l'espace induits par$\phi$ Supposons que nous initialisions aléatoirement ces $K$ centroïdes $\mu_1, \ldots \mu_K$dans l'espace d'origine uniquement. (Veuillez me corriger si je présume mal)
Après l'initialisation, nous devons affecter chaque point de données à l'un des clusters. Supposons que nous voulions attribuer$x_n$ à un cluster, cela peut être facilement fait en utilisant (1) pour calculer $\mu_k$ = $\text{arg min}_j\; ||\phi(x_n) - \phi(\mu_j)||^2$
Après avoir attribué des clusters, comment calculer les nouveaux centres de gravité? Evidemment, je ne peux pas prendre de sens dans l'espace induit par$\phi$ comme il est dimensionnel infini, que dois-je faire maintenant?
Quel est le contournement de ce problème? Je suppose que nous n'avons pas du tout à stocker les centres de gravité. Mais je ne vois pas comment y parvenir.
J'ai lu Trouver les centres de cluster dans le clustering kernel k-means
Cependant, la réponse du wiki de la communauté n'explique pas où $(1)$ vient de.
Réponses
Les k-moyennes du noyau sont équivalentes aux k-moyennes régulières opérant dans l'espace des fonctionnalités induit par le noyau. Par conséquent, les centres de gravité vivent dans l'espace des fonctionnalités qui, comme vous l'avez mentionné, peut être de dimension infinie. Lors de la formulation d'un algorithme d'apprentissage à l'aide de l'astuce du noyau, nous n'avons jamais besoin de toucher directement l'espace des fonctionnalités. Toutes les opérations dans l'espace des fonctionnalités sont effectuées implicitement à l'aide de la fonction noyau. Ainsi, nous ne traitons jamais directement les centres de gravité dans les k-means du noyau. Au lieu de cela, nous travaillons avec les attributions de cluster, comme je l'expliquerai ci-dessous.
K-means dans l'espace des fonctionnalités
L'algorithme de Lloyd est la méthode standard pour résoudre (approximativement) le problème des k-moyennes. Voici une généralisation qui fonctionne directement dans l'espace des fonctionnalités. Laisser$X = \{x_1, \dots, x_n\}$ être les points de données et $\phi(\cdot)$ être une fonction qui mappe un point de l'espace d'entrée dans l'espace d'entités.
- Initialiser $K$ grappes $C_1, \dots, C_K$, où chaque cluster $C_j$ est un ensemble contenant $n_j$ points, et chaque point est membre d'exactement un cluster.
Répétez jusqu'à la convergence (pas de changement d'appartenance au cluster):
Pour chaque cluster $C_j$, le centroïde (dans l'espace des fonctionnalités) est:
$$\mu_j = \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \tag{1}$$
Pour chaque point $x_i$, trouve l'index $a_i$ du cluster dont le centre de gravité est le plus proche (dans l'espace des fonctionnalités).
$$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}$$
- Mettez à jour les clusters. Chaque point devient membre du cluster avec le centre de gravité le plus proche:
$$C_j = \{x_i \mid a_i = j\}$$
Remarque: $\langle \cdot, \cdot \rangle$désigne le produit intérieur. Équation$(3)$découle de la relation entre la norme et le produit intérieur. Le premier terme$\langle \phi(x_i), \phi(x_i) \rangle$ ne dépend pas du cluster afin que nous puissions le supprimer, donnant l'équation $(4)$.
Utiliser l'astuce du noyau
Supposons que nous ayons une fonction noyau $k(\cdot, \cdot)$qui calcule les produits internes dans l'espace des fonctionnalités. Donc$k(x, x') = \langle \phi(x), \phi(x') \rangle$. Nous pouvons remplacer les produits internes dans l'algorithme ci-dessus par des évaluations de fonctions du noyau, fonctionnant ainsi implicitement dans l'espace des fonctionnalités. C'est ce qu'on appelle l'astuce du noyau.
Tout d'abord, combinez les étapes 2 et 3 en remplaçant la définition des centroïdes dans l'équation $(1)$ dans la recherche du centroïde le plus proche dans l'équation $(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}$$
Puisque le produit interne est bilinéaire, nous pouvons le réécrire comme suit:
$$\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}$$
Remplacez les produits internes par des évaluations des fonctions du noyau:
$$\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}$$
Pour chaque point $x_i$, cela indique comment trouver le cluster avec le centre de gravité le plus proche, sans calculer explicitement les centres de gravité dans l'espace des fonctionnalités. Il peut être remplacé par les étapes 2 et 3 de l'algorithme ci-dessus.