Hello everyone and welcome to an introduction to k means clustering in this lecture.
We're going to discuss the K means clustering algorithm which will allow us to cluster and label data
in an unsupervised machine learning algorithm.
You want the full mathematics behind this algorithm.
Go ahead and read Chapter 10 of an introduction.
Just learning k means clustering is an unsupervised learning algorithm meaning it takes an unlabeled
data it's going to attempt to group similar clusters together in your data.
So what is a typical clustering problem look like.
Well a few examples may be things like clustering similar documents together clustering customers based
off of their features trying to perform market segmentation or even trying to identify similar physical
groups.
The overall goal is to divide data into distinct groups such that observations within each group are
similar.
Here you can see a diagram of unlabelled training data and k means clustering trying to attempt to cluster
that data into five distinct clock colored clusters here.
How does the algorithm actually work.
Well you first choosing a number of clusters K and we'll discuss how to choose k later on then you randomly
assign each point in your data to a specific cluster then until the clusters stop changing.
You repeat the following steps for each cluster you're going to compute the cluster centroid by taking
the mean vector points in the cluster.
Then you assign each data point to the cluster for which the centroid is the closest.
Let's go ahead and take a look at the state of visualization or this plotted out visualization of k
means clustering algorithm.
You first start off with just the observations that's shown on the top left then in top center we have
Step 1 of the algorithm.
Each observation is randomly assigned to a cluster in the top right of step 2 A The cluster centroid
are then computed.
These are shown as large colored disks.
Initially these centroid are almost completely overlapping because the initial cluster assignments were
chosen at random in the bottom left.
And step two be each observation is assigned to the nearest centroid in the bottom center.
Step two is once again perform and you can see that we've led to a new cluster centroid and we basically
keep repeating these steps until there's no new clusters meaning data points aren't being reassigned
to a new cluster centroid at the bottom right.
We have the results obtained after about 10 iterations.
Let's discuss choosing a k value as we just saw to perform k means clustering.
We have to decide how many clusters we expect in the data.
The problem of selecting K isn't actually that simple.
There is no easy answer for choosing a best case value.
However one way to try to do it is using something known as the elbow method.
First of all you compute the sum of squared error otherwise known as s s e.
For some values of k for example 2 4 6 8 etc..
The sum of squared errors is defined as the sum of the square distance between each member of the cluster
and its centroid.
If you plot K against the SS e you will see that the air decreases as Kagiso larger.
This is because in the number of clusters increases they should be smaller.
So distortion is also smaller.
The idea of the Elbel method is to choose the K at which the s s e decreases abruptly.
This produces an elbow effect in the graph as you can see in the following picture.
Here we can see an example of a plotted out Elbot method on the X horizontal axis.
We have the K value which stands for the number of clusters you choose for it.
The algorithm on the y axis you have the within groups sum of squares you want to try to choose a K
where you won't get that much more information by increasing the number of clusters Menier are not going
to significantly decrease the within groups.
Sum of squared error by increasing number of clusters.
And that's why this is called the elbow method.
As you can see an elbow occurring around the number.
Let's say six to seven clusters.
That means that's a good number to choose for your clusters.
Again there's no correct value.
So you want to use your domain experience or domain knowledge in whatever field you're working with
in order to try to choose a correct or reasonable k value.
Now if you learned about the theory behind the K means clustering algorithm.
Let's go ahead and move on to showing some examples with Python.
We'll start by showing you how to use sikat learns own built in data generation tools to create some
clusters and then test the Kamins algorithm with sikat learn then for your portfolio project you'll
work for real world data set and try to cluster universities into groups based off of their features
and then you'll see if you can distinguish between private and public schools.
Thanks everyone and I'll see at the next lecture