Initialize centroids
- Decide the number of clusters $k$.
- Pick $k$ initial centroids (random points or using a smarter method).
- As the initial scenario it gets a random point as the centroid. That centroid is depict by $\mu_1$
- If it divides into 04 clusters, then $k$ value of $4$.
- If there are $k$ no of clusters then there are $\mu_k$ (no of) clusters (centroids are: $\mu_1, \mu_2, ..., \mu_k$).
- Score = distance to the cluster center (centroid) - Smaller better.
Assign points to clusters
- For each data point $X_i$, find the centroid $μ_j$ with the smallest Euclidean distance ($\|X_i - \mu_j\|_2$).
- Here, $||_2$ - Represents the Euclidean distance.
- Set $Z_i = j$ (the cluster index for point $i$).
Update centroids
-
For each cluster $j$, recompute centroid $μ_j$ as the average (mean) of all points assigned to that cluster. (To find the actual centroid, we iteratively update each cluster center by calculating the mean of all data points currently assigned to that cluster.)
-
If $n_j$ is the number of points in cluster $j$, then
$$ \mu_j = \frac{1}{n_j}\sum_{i:Z_i=j} X_i $$
-
Since above equation calculates the centroid of a cluster,
- $X_i$ - A fixed data point.
- $\mu_j$ - The centroid of the $j^{th}$ cluster. Its value changes with each iteration of the algorithm.
- $min_j$ - An operator that finds the minimum value from a set of values indexed by $j$.
- $arg$ - An operator that finds the index ($j$) that corresponds to the minimum value, not the value itself.
- ( If $j$ = 2 then $Z_i$ = 2 )
- $Z_i$ - The cluster assignment for the $i^{th}$ data point
- Example ($Z_{500}$=$3$): The $500^{th}$ data point is in the $3^{rd}$ cluster.
- To update the $j^{th}$ cluster, we need to consider only the data points belongs to the $j^{th}$ cluster
- $n_j$ means the no of data points in the $j^{th}$ cluster.
Repeat
- Go back to step 2 and repeat assignment and update until centroids stop changing (converged) or changes are tiny.
