TP 11: PCA et $K$-Means

Link

$K$-means

Distortion:

\[J(\mu,Z) ≝ \sum_{i=1}^n \sum_{k=1}^K Z_{ik}\Vert x_i-\mu_k \Vert^2\]

L’algorithme K-means consiste en une minimisation alternée entre $\mu$ et $Z$ :

1. Choix d’une matrice $\mu$ de manière aléatoire
2. Etape 1: Minimisation de $J$ par rapport à $Z$ (revient à assigner chaque point $x_i$ au cluster le plus proche)
3. Etape 2: Minimisation de $J$ par rapport à $\mu$ : $\mu_k = \frac{\sum_i Z_{ik}x_i}{\sum_i Z_{ik}}$
4. Etape 3: Revenir à l’étape 1 jusqu’à convergence.

1) Montrer que l’étape 2 de l’algorithme correspond à l’annulation du gradient de $J$ par rapport à chacun des $\mu_k$ avec $Z$ fixé.

\[\frac{\partial J}{\partial μ_k}(μ_k, K) = \frac{\partial}{\partial μ_k} \left( \sum_{i=1}^n Z_{ik}\Vert x_i-\mu_k \Vert^2\right) = - 2 \sum_{i=1}^n Z_{ik} (x_i - μ_k)\]

Donc

\[\begin{align*} & \quad \frac{\partial J}{\partial μ_k}(μ, K) = 0 \\ ⟺ & \quad \sum_{i=1}^n Z_{ik} x_i - μ_k \left(\sum_{i=1}^n Z_{ik}\right) = 0 \\ ⟺ & \quad \mu_k = \frac{\sum_i Z_{ik}x_i}{\sum_i Z_{ik}} \\ \end{align*}\]