Hello and welcome back to the course on Machine Learning.
And in this section we're kicking off the tutorials for hierarchical clustering.
All right so another very interesting topic ahead of us.
And as always let's make the complex as simple and demystify what it's all about.
All right so what is hierarchical clustering.
Well believe it or not.
But if you have points on your scatterplot or
data points like we looked at previously, this is a two dimensional space.
If you apply hierarchical clustering or let's just say H.C.
for short, what will happen is you will get clusters.
Again very, very similar to K-means.
In fact, sometimes as a result, often the results can be exactly
the same as k means clustering, but the whole process is a bit different.
So let's talk about it in a bit more detail.
So the first thing that we need to note is that there's two types
of hierarchical clustering agglomerative and divisive.
So agglomerative is the bottom up approach.
And you'll see in more detail just now what that means.
So we'll be starting at the very bottom and then building our way up.
Divisive is the opposite.
Starting at the top and devising a clusters into multiple.
In this course we'll be focusing on the agglomerative approach, the divisive.
We'll mention it a bit just now when we're talking about agglomerative.
But it's basically the same thing but the other way around.
It's the reverse of the agglomerative.
And if you like, you can definitely research more about the divisive approach.
But for now, we're going to focus on the matter of one.
All right.
So the agglomerative hierarchical clustering how does it work.
Well to start off we're going to break it down into step by step approach.
And then we'll look at an example and manually perform the clustering.
All right so step one in HTK is to make each data point a single point cluster.
So that forms and clusters.
So if you have n data points your first step is to
look at each one of them as an individual cluster.
Then step two is to take the two closest data points and make them one cluster.
So to combine them into one cluster that forms n minus one clusters.
Then step three is to take the two closest clusters out of the ones.
Now that you now have and make them one cluster that forms n minus two clusters.
Then step four is to repeat step three until there is only one cluster.
Basically, just keep repeating step three and combining points into bigger
and bigger and bigger clusters until there's only one huge cluster left.
So you just keep repeating step three and at the end you're done.
So at the end you'll have one huge cluster left.
And how to get from one to 2 or 3 clusters.
How do you get the final result that you actually want?
We'll talk about that in this section as well.
So that's that's the goal of course.
But one thing that stands out here
is the words closest clusters.
Now we've already talked about distances.
And we mentioned Euclidean as you can use Euclidean distance or other distances.
And that's totally fine when you're working with individual points.
But here we're actually going a step even further.
We're talking about
not just the proximity of points, but actually proximity of clusters.
And this is something worth noting.
So I'd like to pause here for a bit.
And or I kind of step to the side and talk about the closeness of clusters
and how you measure
distance between classes, because that
can really affect your algorithm if you're using hierarchical clustering.
So let's talk about that for for a few minutes.
So first of all Euclidean distance just to get this out of the way
once and for all Euclidean distance is in a two dimensional space.
It's calculated like that. So the distance.
So if you got two points P1 with the coordinates x1
and y1 p2 of coordinates x2 and y2, then Euclidean distance
or the length of this line is calculated as x2 minus x1, so that the distance
between the x's squared plus the distance between the y's squared.
So basically and then the you add them up and then you take the square root.
So basically it's a you've got a right angled triangle over here.
And you've got the cat at here.
And you got another one cat at here I hope I'm pronouncing is right.
And then this is the hypotenuse. Right.
So that is how you calculate the distance between the two points.
So it's basic geometry back from high school.
And there you go.
That's, that's just how Euclidean distance is calculated.
And that's what we're going to be working with.
But again
there are other types of distances that you could be invoking in your algorithms.
And it really depends on the scenario
and what exactly how your algorithm is going to be structured.
But in our examples we're going to be working with Euclidean distances
because they're the more natural type of distance.
And now let's talk about the distance between two clusters.
So let's say you have two clusters the red and the blue.
How do you measure the distance between them.
What what is the definition of the distance between two clusters.
It's not a not as obvious
as it might sound at the start, because there can be a couple options.
For instance, you can option one is just take the two closest points
and measure that and call that the distance between the two clusters.
Option two is actually take the two furthest points
and call that the distance between two clusters.
That's also valid approach.
Option three take the average to take the average of all the distances
between the different points in the cluster, so all the combinations
of different points, and take the average of that distance.
Option four is take the distance between the centroids.
So find the centroids and find the distance
between the centroids and call that the distance between the two clusters.
So it's a very important part of
hierarchical clustering what you define as the distance between two clusters.
Because that can significantly impact the output of your algorithm.
Now we're not going to delve much deeper into this.
It's just something to remember to note.
And based on your particular situation, whether it's a business problem
or other type of, data science problem, based on what exactly you think
is the best approach, you're going to need to define that in your algorithm.
So just keep that in mind that for the hierarchical clustering
algorithm, the distance between clusters is a crucial element.
And you need to remember what exactly you're setting at is
you're setting it to be how you defining it in your approach.
All right.
So we've talked about that.
Now let's move back to our example.
So we've already looked at the step by step rules.
And I I'm a big fan of a step by step approach.
Now we have this step by step approach.
And it might have seemed
a bit overwhelming as always, because we didn't have an example.
But now we're going to have that example
and we're going to look at how to build those hierarchical clusters.
So step one make each data point a single point cluster that forms a six clusters.
Let's have a look at that.
You can see every single point is a separate cluster.
Next take the two closest data points and make them one cluster
where we can see that these two points are the closest.
So we're putting them together in one cluster.
Now we have five clusters 123, four.
And these two are one cluster.
All right. Step three.
Take the two closest clusters
out of the ones we had and turn them into one cluster.
So out of the clusters we had because remember each point out of these four.
So if I go back here each point here is a separate cluster.
And this is a cluster.
So now just measure the distances between clusters.
And let's say in our example we're going to be talking about
the distance between clusters as the minimum distance.
So that would be the distance between those two clusters.
That would be the distance that would be that that would be and so on.
So we measure all the distances between clusters.
And you find out that these two are actually the closest clusters.
And you combine them into one cluster.
Next you repeat step three.
So next out of these two clusters out of one, two, three, four clusters.
So you can see we had five. Now we have four.
Every time you reduce the number of clusters
by one out of these four clusters which are the cluster as well the
this seems as the closest cluster.
So we're going to come by that.
Now out of these three clusters which are the cluster.
So it looks like these two are so combining them.
And now we've only got two clusters left.
So the last step would be to combine them
because they are by default they're going to be the closest.
So there we go.
And so that is the end of our algorithm.
That's how it converges.
You've we've gone through the process of create
of going from all points seen as an individual cluster.
So each point is an individual cluster to now we only have one cluster
that combines all of the points.
And so what's the purpose of all of this?
what's the purpose of this exercise?
The way the hierarchical clustering algorithm works is that it
maintains a memory of how we went through this process,
and that memory is stored in a dendrogram.
And that's exactly what we're going to talk in the next tutorial.
And once we've covered the dendrogram it will make total sense
why the hierarchical clustering algorithm does what it does and how it works.
So hopefully you enjoyed today's tutorial.
Can't wait to see you on the next one!
Until then, enjoy machine learning!