Hello everyone, welcome to the course of machine learning with Python. In this video, we shall learn about a clustering algorithm called k means clustering. k means is it partitioning clustering algorithm. The K means algorithm partitions the given data into k clusters. each cluster has cluster center called centroid, K is usually user specified. So, what is the K means algorithm select k points randomly as initial centroids repeat from K clusters like C one c two c k by assigning all points to the closest centroid, we compute the centroid of each cluster using the formula mew suffix ci is equals to one sub mod of ci sum over all exists where x belongs to ci.

Okay, so what is mod of ci it denotes the number of points in cluster I until the centroids don't change or no reassignment of data points in different clusters. We call these convergence criteria. So, In this GIS we will see how k means works. So, as you can see, in each iteration, different data points are getting assigned to different clusters. And these separate separate colors denotes basically the cluster boundaries. And this cross marks denotes the cluster centroid.

As you can see total within clusters sum of square is getting reduced as we increase the number of iterations. So, what is within cluster sum of squares So, total within trust yourself squares is often by the following formula so, let's MUJI is the centroid of cluster chain and the requital keys such clusters then within cluster sum of squares are WC SS is equal to five We compute the distance between the X and Meucci, where x belongs to cluster g that means, we compute the distance between all the points of cluster G to its centroid is square up these these distances and sum it up for all the points in cluster ci, then we do it for all the such clusters that means, from cluster one to cluster key, we some of these and we obtain within cluster sum of squares, okay. So, here distance denote the distance function of users choice, usually we use Euclidean distance.

So, somebody lots about k means as initial centroids are often chosen randomly, the data produced may vary from one run to another K means will converge for more common similarity or dissimilarity measures. Most of the convergence happens in the first few iterations complexity of the algorithm is order of Multiplied by key multiplied by d multiplied by Im where a is equals to the number of data points key is number of clusters, small d denotes the dimension of the data set that means number of features and it denotes the number of iterations, no different runs of Kings algorithm on the same data set can produce very different results. This is one of the limitation of K means clustering. Now, why this happens? This is because random selection of initial centroids So, as you can see, these are the original points for optimal clustering, we may obtain a clustering like this, for suboptimal clustering, where the random initial points can produce a cluster like this.

So, this suboptimal clustering is wildly different from this optimal question. So, this is for round one, we obtain optimal clustering. This is for run to where we operate a sub optimal clustering So, choosing different set of initials incorrect sub produced completely different clustering on the same data set. Now, how we can overcome this limitation, so, we can pre process the data first that means normalize or standardize the data and eliminate the outliers if possible samples a data set and use hierarchical clustering that we shall introduce in the next lecture. To determine the initial set chords see that more than key initial supports and from these select key most widely separated centers after clustering, multiple runs and see that one which gives the minimum WC SS that means within clusters of squares value post processing the data, eliminate small clusters that may represent outliers or noises, split the loose clusters that is clusters with relatively high sum of squared error and merge the clusters that are close that means having relatively low sum of squares now k means faces problem when the clusters are of different sizes.

So, these are the original points and after k means these clusters have been produced as you can see, these are wildly different, okay. So, as the cluster sizes are different gaming's has not performed well in this set of points give me some kidneys also does not work well with the clusters are of different densities. So, these are the original points. So, as you can see this cluster is not densely packed, but these two clusters are densely packed. But, however, Keynes has identified these as clusters. So, YK means does not work well, because of different densities of the clusters k means also does not work well when the clusters are of non spherical shape.

So, as you can see, these two clusters are not of physical shape. So, in this case, the desert produces by k means clustering looks like this. Okay. So, as you can see, it has not understood toward the Underland data distribution and has produced some sort of spherical question over here. Okay, which is different from the original points. So so far, this is our discussion on k means clustering.

In the next video, we shall learn how to implement k means clustering in Python. So thank you. See you in the next lecture.