How does the K-Means Algorithm Work?

Data Science, AI and ML
,
#1

The working of the K-Means algorithm is explained in the below steps:

Step-1: Select the number K to decide the number of clusters.

Step-2: Select random K points or centroids. (It can be other from the input dataset).

Step-3: Assign each data point to their closest centroid, which will form the predefined K clusters.

Step-4: Calculate the variance and place a new centroid of each cluster.

Step-5: Repeat the third steps, which means reassign each datapoint to the new closest centroid of each cluster.

Step-6: If any reassignment occurs, then go to step-4 else go to FINISH.

Step-7 : The model is ready.

Let’s understand the above steps by considering the visual plots:

Suppose we have two variables M1 and M2. The x-y axis scatter plot of these two variables is given below:

K-Means Clustering Algorithm

  • Let’s take number k of clusters, i.e., K=2, to identify the dataset and to put them into different clusters. It means here we will try to group these datasets into two different clusters.
  • We need to choose some random k points or centroid to form the cluster. These points can be either the points from the dataset or any other point. So, here we are selecting the below two points as k points, which are not the part of our dataset. Consider the below image:
    K-Means Clustering Algorithm
  • Now we will assign each data point of the scatter plot to its closest K-point or centroid. We will compute it by applying some mathematics that we have studied to calculate the distance between two points. So, we will draw a median between both the centroids. Consider the below image:
    K-Means Clustering Algorithm

From the above image, it is clear that points left side of the line is near to the K1 or blue centroid, and points to the right of the line are close to the yellow centroid. Let’s color them as blue and yellow for clear visualization.

K-Means Clustering Algorithm

  • As we need to find the closest cluster, so we will repeat the process by choosing a new centroid . To choose the new centroids, we will compute the center of gravity of these centroids, and will find new centroids as below:
    K-Means Clustering Algorithm
  • Next, we will reassign each datapoint to the new centroid. For this, we will repeat the same process of finding a median line. The median will be like below image:
    K-Means Clustering Algorithm

From the above image, we can see, one yellow point is on the left side of the line, and two blue points are right to the line. So, these three points will be assigned to new centroids.

K-Means Clustering Algorithm

As reassignment has taken place, so we will again go to the step-4, which is finding new centroids or K-points.

  • We will repeat the process by finding the center of gravity of centroids, so the new centroids will be as shown in the below image:
    K-Means Clustering Algorithm
  • As we got the new centroids so again will draw the median line and reassign the data points. So, the image will be:
    K-Means Clustering Algorithm
  • We can see in the above image; there are no dissimilar data points on either side of the line, which means our model is formed. Consider the below image:
    K-Means Clustering Algorithm

As our model is ready, so we can now remove the assumed centroids, and the two final clusters will be as shown in the below image:

K-Means Clustering Algorithm