K Means Clusturing

Understand what it does

Example Process of K-means:

1. Initialization: Choose K random data points as initial centroids.
2. Assignment: Assign each data point to the nearest centroid.
3. Update: Recalculate the centroids -> mean of the assigned points.
4. Repeat: Continue until convergence (when centroids don’t change significantly anymore).

This plot is showing how each iteration leading to finding the best centroid and best clusture. now read each 4 process mentioned below and visit this fig mentioned above we will understand easily.

How does we select K value

first we calculate wcss value the formula given below in simple word this is nothing but sum of square of distance between nearest centroid(cluster)

and where ever we find the elbow point in graph of wcss that will be our k value. in this case k will be 4.

.Do you know why in starting the value is max since we chose random value as our centroid then it is very clear to have large distance and in further iteration we are decreasing the distance.

Get Yahia’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

. In this graph you can see there is point where WCSS became constant it means we cannot decrease WCSS further more so we can choose it as our k value.

. Why WCSS should be small.

• Large WCSS: Indicates poor clustering, with points far from centroids and clusters that are spread out or overlap.
• Small WCSS: Indicates good clustering, with points close to centroids, resulting in tight, well-defined clusters.

Assignment

After choosing the value of K (the number of clusters), we randomly initialize K centroids. Then, we calculate the distance of each data point from all K centroids. Each data point is assigned to the centroid (or cluster) that has the smallest distance. This process groups the points into clusters.

UPDATE

Next, we calculate the average (mean) of all the points assigned to each cluster. This average becomes the new centroid for each cluster.

Repeat

The process of assigning points to the nearest centroid and recalculating the centroids is repeated until the centroids no longer change, which indicates that the algorithm has converged.

.if you are confuse how much time we have to repeat this process let me tell you after some iteration we will see your centroid will not move much it nearly become constant.

Random Initialazation Trap

how centroid are selected

The random initialization trap in K-means occurs when the initial centroids are chosen randomly, which can lead to:

1. Poor convergence: The algorithm may get stuck in suboptimal solutions.
2. Different results: Running K-means multiple times with different initializations can produce varying results.
3. Slow convergence: It may take many iterations to converge or fail to converge to the best solution.

To avoid this, techniques like K-means++ are used for smarter initialization of centroids.

Limitations of K-means clustering

1. Need to specify K: You must predefine the number of clusters, which can be difficult if the optimal K is unknown.(solution is WCSS)
2. Sensitivity to initialization: Randomly initialized centroids can lead to suboptimal solutions or poor convergence.(solution is K-means++)
3. Assumes spherical clusters: K-means assumes clusters are spherical and equally sized, which isn’t always true for complex data shapes.
4. Sensitive to outliers: Outliers can significantly affect the centroids, leading to inaccurate clusters.
5. Non-convergence: It may converge to a local minimum, not necessarily the global optimum.(solved by chosen by first good centroid)
6. Scalability: K-means can be slow with very large datasets or high-dimensional data.