Question 1

How does *K*-means++ algorithm enhance the initialization process as compared to the standard *K*- means algorithm? Figure from the original question paper Let $k : \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}$ be a valid kernel function such that $k(x, y) = \phi(x)^T\phi(y)$, where $\phi : \mathbb{R}^d \to \mathbb{R}^D$, where $d < D$. Define $$k_1(x, y) = \frac{100k(x, y)}{\sqrt{k(x, x)k(y, y)}}.$$ Find $\phi_1 : \mathbb{R}^d \to \mathbb{R}^D$ such that $k_1(x, y) = \phi_1(x)^T\phi_1(y)$. **Note:** $||x||_2 = \sqrt{x^Tx}$.