K-Means Clustering Algorithm
K-Means is an unsupervised learning algorithm used to form clusters or groups of similar data. It works on unlabeled data and identifies patterns by grouping similar points based on their distance to centroids.
Steps in K-Means Algorithm:
Step 1: Choose the number of clusters, K. This can be done randomly or by using methods like the Elbow Method.
Step 2: Randomly initialize K centroids (one for each cluster).
Step 3: For each data point, calculate the distance to each centroid. Assign the point to the cluster with the closest centroid.
Step 4: Recalculate the mean of the points in each cluster — this mean becomes the new centroid.
Repeat steps 3 and 4 until: The centroids no longer change significantly, or a maximum number of iterations is reached.
Challenges in K-Means:
Two main issues often arise:
- Choosing the value of K
- Choosing initial centroids
Both can significantly affect the performance and accuracy of the clustering.
How to Choose the Value of K?
If we choose K randomly, it might be:
- Too small → Merged clusters (not enough separation)
- Too large → Extra, unnecessary clusters
To solve this, one commonly used technique is the Elbow Method.
Elbow Method:
Used to find the optimal number of clusters (K).
Step 1: Start with K = 1 and compute the first centroid.
Get Farah Maqbool’s stories in your inbox
Join Medium for free to get updates from this writer.
Step 2: Calculate the distance of each point to its centroid, square these distances, and sum them up. This is called the WCSS (Within-Cluster Sum of Squares).
- Lower WCSS = Better clustering
- Higher WCSS = Poor clustering
Step 3: Repeat this process for different values of K (e.g., K = 1 to 10). Then, plot K vs. WCSS.
Look for an “elbow point” in the graph the point after which increasing K doesn’t significantly reduce the WCSS. That point is considered the optimal K.
How to choose centroids?
Choosing centroids randomly can cause issues like:
- You might choose bad starting point
- The final clusters might be not optimal
- Different results every time you run it (non-deterministic)
To solve this we have K-Mean++ which is improved version of K-Mean
K-Mean++:
An Improved version of K-Means for choosing better initial centroids. It chooses the centroid in strategically unlike K-Mean which chooses centroid randomly.
Here how it works:
- Choose the first cluster center randomly from the data points.
- For each data point, compute the distance to the nearest center already chosen.
- Square those distances to get D(x)² for each point x.
- Use those squared distances to compute selection probabilities:
- A point that is farther from any center gets a higher chance of being picked.
- The probability for a point x is:
- After selecting the initial centers K-Means++ performs clustering the same way as K-Means.
- Assign each data point to the nearest cluster center.
- Recalculate cluster centers by finding the average of all points in each cluster.
- Repeat the steps until the cluster centers do not change or a fixed number of iterations is reached
