Suggest edit — k-means clustering

Title

Name

Note

---
title: "k-means clustering"
type: concept
source: https://www.jemoka.com/posts/kbhk_means_clustering/
confidence: high
status: active
---

constituents dataset \(\qty {x^{(1)}, \dots, x^{(n)}}\) number of clusters \(k\) requirements Initialize cluster centroids \(\mu_{1}, &hellip;, \mu_{k}\) randomly, and repeat:
assigning points \(x^{(i)}\) to cluster centers \(c^{(i)}\): for each \(i \in [1, \dots N]\), write \(c^{(i)} = \arg\min_{j} \norm{x^{(i)}- \mu_{j}}^{2}_{2}\) update centroids: for each \(j \in [1 \dots k]\), write \(\mu_{j} = \frac{\sum_{i=1}^{n} \mathbbm{1}\qty {c^{(i)}=j} x^{(i)}}{\sum_{i=1}^{n} \mathbbm{1}\qty {c^{(i)}=j}}\) additional information some ways to pick better centroid sample the data points as the initial centroids k-means++ k-means++ pick uniform data point to be first centroid pick next centroid w.r.t. probability proportional to distance to the previous centroid squared distortion function Consider the following function:
\begin{equation} J\qty(c, \mu) = \sum_{i=1}^{n} \norm{x^{(i)}- \mu_{c^{(i)}}}^{2} \end{equation}
Adding more clusters will reduce this function, and at some point we will reach a regime where this function reaches minima. There will be a point where we reach an &ldquo;elbow&rdquo; where decreases is no longer as dramatic.