K-Means Clustering

What is K-Means Clustering?

K-means clustering is amongst the most popular unsupervised machine learning algorithms. Machine learning algorithms roughly divided into three major classes. These classes supervised, unsupervised and reinforcement learning. In supervised setting a data along with its label required in order to have an algorithm work properly.

Whereas in unsupervised type of algorithms the data not required to have labels for the algorithm to find an underlying pattern. In a nutshell, unsupervised algorithms make inferences from the data using only input vectors without considering labels or outcomes. The reinforcement learning algorithms do not fall in these two categories as they work by maximizing a predefined reward function against an action.

Given the fact that k-means clustering is an unsupervised machine learning algorithm, therefore, our discussion will be revolving around the unsupervised machine learning and how k-means work.

K-Means Clustering Formula

The objective of K-means is to group similar data points together. By doing this we come to discover the underlying patterns in the data. More expressively, what we find is that in the whole data which data points relate with each other. On this basis we make groups of such related data points and this is called ‘clustering’.

The number of clusters in which we like to see the data grouped into is provided by us. Let us say we want to see the data grouped/clustered into five distinct groups/clusters. This value is k which is what the algorithm has been named after. The data points are clustered in k groups on the basis of their similarity with each other.

Using the technical jargon the same concept can be understood as follows. The target number k refers to the number of centroids we need to make in the dataset. A centroid is a location which represents the center of a cluster. Simply put, the algorithm works by calculating where to put the center of each cluster

in the data and how far each cluster is stretching from this centeroid/center in the problem space.

The K-Means Clustering algorithm places k number of centroids in the data and allocates every data point to the nearest cluster. While doing so, it tries to keep the centroids as small as possible.

The ‘means’ in the K-means refers to averaging of the data; that is, finding the centroid.

K-Means Pseudo Code

The pseudo code of K-means algorithm is given as follows.

K-Means-Pseudo-Code

Here ‘K’ is the total number of centroids and ‘k’ is the current centroid under consideration. Whereas x(i) is the current data point under consideration.

The first inner loop assigns the most appropriate centroid to the example under consideration i.e x(i) by giving it the index of the centroid from which the example is at the smallest distance apart. The distance calculated using a distance formula as shown below:

distance-calculated-using-a-distance-formula

The ‘k’ for which we get the smallest distance will be the centroid to which this example will be assigned. A more conventional way is to take the square of the distance.

In the second loop of the pseudo code the new position of a centroid calculated. It done by taking average of all the example belonging to this centroid. Consider, if x(1), x(5) and x(7) belong to a centroid (2) then the new position of (2) will be as follows.

distance-calculated-using-a-distance-formula-new-position

We repeat these steps till we have no more position changes occurring in centroids or we run out of maximum iteration limit. A blow by blow working of the algorithm is shown graphically hereunder in Figure 1. The first figure

shows the spread of data. In the next one that is (b), we are randomly choosing two centroids. Whereas in (c) we are assigning a number of examples to each of the two centroids and in (d), the forth one, we are calculating the centroid positions and moving them to their new locations. Finally, in (d), we once again assign the examples to the appropriate centroids.

Progression-of-K-means-clustering-from-(a)-to-(e)
Fig 1. Progression of K means clustering from (a) to (e)

K-Means Clustering in Data Mining:

K means clustering has wide applications in the data mining. It used to identify market segments. A noticeable point is that we do not always have data separated in the format as shown in the upper figures. We may have a continuous spread as shown below in the Figure 5.

Consider that it is representing the data of people against their weight and height parameters. The problem is to segment this data into three chunks so that a T-shirt manufacturer can have small, medium and large t-shirt sized for a specific range of weight and height. This problem is a vanilla data mining problem. Here we are mining for a hidden pattern in the data which will segment it with respect to the weight to height ratio of the given population.

Market-segmentation-of-a-population-for-three-T-Shirt-sized-using-K-means-clustering
Fig.2 Market segmentation of a population for three T-Shirt sized using K-means clustering

Similarly, other applications of K means clustering in data mining found in finding similar or like minded people on social media and rearranging a data center by moving servers close together which tend to have similar activity thus reducing the power consumption and other costs.

K-Means Clustering in Python

Scikit-learn is a very handy Python library for implementing machine learning algorithms. Here we shall be performing a hands-on unsupervised clustering routine on a dummy data using this useful Python package. This code can be run using Jupyter Notebook or Pycharm IDE. For a novice it is recommended to use Anaconda which comes with pre-installed Python packages. This could be got from here. We recommend that you choose Anaconda distribution with Python 3.7 version as it is the latest one. Once installed, on running you get a screen like in below in Figure 3.

Anaconda-3-window
Fig.3 Anaconda 3 window

Click ’Launch’ Jupyter Notebook. This will launch a server and a browser window will open as under in Figure 4. Now, start a new notebook by clicking at New and selecting Python 3. This will open up a new notebook where you can start coding. In order to run each cell press shift+enter. For this example we are clustering the data into two clusters. That is, the value of K is 2.

Jupyter-notebook-in-the-browser-window
Fig 4. Jupyter notebook in the browser window
Jupyter-notebook-in-the-browser-window-steps

K-Means Clustering in R

R is the classic language for data manipulation. Here is a hands-on routine for doing K-means clustering in R. The code credits go here1 . We are using the famous iris dataset which comes pre loaded wit R-Studio. The number of clusters set to three as three species involved.

Launch R-Studio from Anaconda and run the following code in the console line by line as below. In case of having an error saying there is no package called ‘ggplot2’ please click on the adjacent tab of terminal and run this command to install the required package: conda install -c r r-ggplot2. Now run the instruction once again.

K-Means-Clustering-in-R

Note: Line number 8 and 9 (above) are representing one instruction. You can write them in one line as well. R’s console automatically knows that it is a single instruction and on pasting one line it automatically adds a ‘+’ sign so that next line can be added after it to make the instruction complete.

You may also know: Support vector machines and artificial Intelligence.

7 COMMENTS

  1. Heya i am for the first time here. I found this board and I
    find It truly useful & it helped me out a lot.
    I hope to give something back and help others like you aided me.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

4 + 15 =