## Introduction

The simplest and most fundamental cluster analysis is the partitioning method, which organizes the objects(i.e. Data points) into several mutually exclusive groups or clusters. So the K-means Clustering algorithm uses partitioning methods to cluster unlabeled data. It clusters the n objects or data points into k number of clusters. It is an unsupervised machine learning algorithm.

So let me explain this by an example of small dataset .

So we are going to group above unlabeled data into different clusters. Let take k=3, i.e we group these data points into three clusters.

K-means algorithm uses centroid based partitioning technique and the centroid is basically the mean of the objects (or data points).

An objective function is used to assess the partitioning quality so that objects within a cluster are similar to one another but dissimilar to objects in other clusters. which is the sum of squared error between all objects and the centroid.

## How does the k-means algorithm work?

**Step 1:** First, it randomly selects centroid of the objects, each of which initially represents a cluster mean or center.

**Step 2:** Now, for each of the remaining objects, based on the Euclidean distance between the data points and the centroid assign each data point to its closest center. So the object is assigned to that cluster to which it is most similar.

Here the points near to red centroid, is assign in red cluster and so on.

**Step 3: **Now** **for each cluster, it computes the new mean by taking the average of all the points assigned to that cluster. All the data points are then reassigned using the updated means.

**Step 4:** Repeat Step 2 and 3 until none of the cluster assignments change or until the assignment is stable.

So, we get the final clusters.

## How to choose the value of k (i.e the number of clusters)?

We run the algorithm using different value of k and plot it against Sum of Squared Error(SSE) in a graph. And by using elbow method we choose the value of k (i.e. the elbow point).

Here k=3 is the optimum value of k that will cluster the data points optimally.

## Code

`import pandas as pdimport numpy as npimport matplotlib.pyplot as plt#creating datasetdf = pd.DataFrame({ 'x': [39, 36, 30, 52, 54, 46, 55, 59, 63, 70, 66, 63, 58, 23, 14, 8, 19, 7, 24], 'y': [12, 20, 28, 18, 29, 33, 24, 45, 45, 52, 51, 52, 55, 53, 55, 61, 64, 69, 72]})np.random.seed(200)#number of clustersk = 3#randomly select centroidscentroids = { i+1: [np.random.randint(0, 80), np.random.randint(0, 80)] for i in range(k)}#plot in figureplt.scatter(df['x'], df['y'], color='k')colmap = {1: 'r', 2: 'g', 3: 'b'}for i in centroids.keys(): plt.scatter(*centroids[i], color=colmap[i], marker='x', s=80)plt.xlim(0, 100)plt.ylim(0, 100)plt.show()`

Here we create dataset using pandas dataframe and randomly choose centroids, and plot it in figure.

`#Creating a function which has dataset and centrods as a parameter#Which calculate distance between each data points and the centroids def assignment(df, centroids): for i in centroids.keys(): #Formula of Euclidean Distance # sqrt((x1 - x2)^2 - (y1 - y2)^2) df['distance_from_{}'.format(i)] = ( np.sqrt( (df['x'] - centroids[i][0]) ** 2 + (df['y'] - centroids[i][1]) ** 2 ) ) centroid_distance_cols = ['distance_from_{}'.format(i) for i in centroids.keys()] df['closest'] = df.loc[:, centroid_distance_cols].idxmin(axis=1) df['closest'] = df['closest'].map(lambda x: int(x.lstrip('distance_from_'))) df['color'] = df['closest'].map(lambda x: colmap[x]) return df#call the functiondf = assignment(df, centroids)#head() will display initial 5 rowsprint(df.head())#after calculating plot it again with new dfplt.scatter(df['x'], df['y'], color=df['color'], edgecolor='k')for i in centroids.keys(): plt.scatter(*centroids[i], color=colmap[i], marker='x', s=80)plt.xlim(0, 100)plt.ylim(0, 100)plt.show()`

To calculate Eucledian distance between data points and centroid we create an function called ‘assignment’. And assign the points to the closest centroid.

`#To update or recalculate the centroids we create another function 'update'import copyold_centroids = copy.deepcopy(centroids)def update(k): for i in centroids.keys(): centroids[i][0] = np.mean(df[df['closest'] == i]['x']) centroids[i][1] = np.mean(df[df['closest'] == i]['y']) return kcentroids = update(centroids)#Again plot the updated centroids and the data points ax = plt.axes()plt.scatter(df['x'], df['y'], color=df['color'], alpha=1, edgecolor='k')for i in centroids.keys(): plt.scatter(*centroids[i], color=colmap[i], marker='x', s=80)plt.xlim(0, 100)plt.ylim(0, 100)for i in old_centroids.keys(): old_x = old_centroids[i][0] old_y = old_centroids[i][1] dx = (centroids[i][0] - old_centroids[i][0]) * 0.75 dy = (centroids[i][1] - old_centroids[i][1]) * 0.75 plt.show()`

Here, we calculate mean of newly formed cluster and update the centroids.

`df = assignment(df, centroids)# Plot resultsplt.scatter(df['x'], df['y'], color=df['color'], edgecolor='k')for i in centroids.keys(): plt.scatter(*centroids[i], color=colmap[i], marker='x', s=80)plt.xlim(0, 100)plt.ylim(0, 100)plt.show()`

`#If is there any changes in updated centroids, the loop will stopwhile True: closest_centroids = df['closest'].copy(deep=True) centroids = update(centroids) df = assignment(df, centroids) if closest_centroids.equals(df['closest']): breakplt.scatter(df['x'], df['y'], color=df['color'], edgecolor='k')for i in centroids.keys(): plt.scatter(*centroids[i], color=colmap[i], marker='x', s=80)plt.xlim(0, 100)plt.ylim(0, 100)plt.show()`

If there is no changes in updated centroids, the loop will stop.

## Conclusion

Although K-Means algorithm is simple and easy to understand or it take less computation time, but it has many issues. i.e it cannot find arbitrarily shaped clusters, it cannot be work efficiently in large datasets, and it is vulnerable to outliers and noise.