>>In hierarchical clustering,
we build clusters step by step.
Usually, it's a bottom up strategy,
where you take all of your individual data observations
and you find ways to aggregate them together.
This technique is called an
agglomerative hierarchical clustering approach.
The contrast to that is a divisive hierarchical approach,
which starts with all of your data as one cluster
and then starts breaking that up
into smaller and smaller clusters.
Again, you need some type of dissimilarity measure,
just like you do with k-means method.
One interesting note is, you don't actually need
the information on all the features themselves.
All you need is a distance matrix that shows you
the distances from each object to every other object,
which, essentially, would be an n by n-matrix of distances,
where n is the number of data objects
or the number of observations in your data.
Given this dissimilarity matrix,
you start with the n clusters,
so this is in an agglomerative approach,
you start with n clusters, and then,
you find your element in the matrix
that has the smallest value.
So, this would represent the two data objects
that are closest together.
You take those two data objects,
and you combine them to create a new cluster.
So now, you end up with n minus one clusters of data.
You started with n clusters of data,
each object is its own cluster, and now,
you go in your next step,
you have n minus one clusters of data,
where most of your clusters are single object clusters,
but you have one cluster that has combined two data objects.
You repeat this process over and over again.
Each time that you perform the process,
you have to recalculate the distance between
the resulting clusters of objects and the data points
in other clusters around them.
The distance, or the dissimilarity between two clusters
containing only one data object is very easy:
it's just the dissimilarity of the two objects
specified in the matrix.
However, computing the dissimilarity between clusters
that contain more than one data object
is more complex, and there are multiple ways of doing it.
The centroid method will calculate the distance
between two different clusters as the distance
between the centroid of those two clusters.
Average linkage is based upon the average distance
between all pairs of points of the two clusters.
Single linkage is the distance between the two most
similar data objects of the two clusters.
And, complete linkage is the distance between the two
most dissimilar data objects.
So, you have a picture that kind of looks like this.
The red arrow shows you the centroid technique,
so it's the distance between the centroids.
The green arrow shows you the single linkage technique,
it's the distance between these two closest points.
The blue arrow represents the complete linkage.
The average linkage would be based upon
the average of all pair distances.
Each one of these techniques has characteristics
that are associated with it.
Single linkage can produce what are called chains
in the data, we'll see an example of that later on.
Complete linkage can lead to very compact clusters,
and average linkage also tends to compact clusters.
Taking these two exact data sets
and using single linkage versus complete linkage,
you can see that you end up with very different results.
There's another method called Ward's method.
This method actually takes the number of objects
that are being classified into cluster into account.
It sort of attempts to balance out your clusters themselves.
On this slide, it's just showing an example.
If I take a cluster C that's been combined with C prime,
and now I'm looking at how do I possibly combine it
with cluster C double prime, and so the single linkage,
complete linkage, average linkage, and centroid methods,
we talk about, we've talked conceptually about how you
would do that and these are the formulas
that are associated with that,
as is the Ward function.
Now, the dendrogram is the primary visualization
for hierarchical clustering.
The cluster merging process arranges the data points
in essentially a binary tree.
When two clusters are merged, the distance
between those two objects, or those two clusters,
is represented by the height of the tree
respective to that merging.
So, let's look at an example.
If you have the clustering of these values:
two, 12, 16, 25, 29 and 45,
the various approaches to measure the distance
between the clusters will lead to different dendrograms.
Using the centroid method, we take these objects:
12 and 16, and we'll combine them together
because they're the closest,
and 25 and 29, I guess that would be a tie,
because they're four apart so they're also the closest pair,
and we calculate their centroids.
the centroid of this cluster is 14,
and then now I try to compare the value of 14
with all the other objects and see which is the closest.
Two is the closest value, and so I'll put now
these data into one cluster,
and I'll calculate that overall centroid,
and I'll repeat the process.
So, my value here that represents this set of data
is the value 10, and I'll look to see which cluster
or data point it should be combined with,
and I continue to build this tree.
Another feature of dendrograms is that you can
cut them at different heights.
So, if I were to cut this dendrogram here at this height,
I end up with four clusters.
If I cut this dendrogram at this height,
I end up with two clusters.
So, the distances between clusters
are represented in the heights in these binary trees,
and you can think about cutting these trees
at different locations to produce
different number of clusters.
Under single linkage, I would also
group 12 and 16, and 25 and 29,
but the next step after that,
and you can tell this based upon the heights
of the point where these clusters are merged,
so this is, the next thing that happens is that
this group, 12 and 16, gets merged to this group,
25 and 29, so the different series of events
that occur in the single linkage technique.
Now, these two are being combined,
and the reason why they're being combined is because
the closest point between these two is 16 and 25,
and the difference between 16 and 25 is nine,
whereas the difference between two and 12 is 10,
and the difference between 29 and 45 is 16.
So, these are merged together,
and then I continue the process.
Again, the height of the dendrogram
represents how different two different clusters are.
So, using complete linkage,
I see I have a totally different representation:
12 and 16 are merged together, and then they're merged
with the value two, just like we saw
with the centroid method,
but instead of now adding in this group, 25 and 29,
you can see its closest, with
respect to the complete linkage,
would be the value 45,
so now I have these two different sets of clusters,
but the distance between this cluster and this cluster
is based upon the furthest value,
so a value of 43 in this case, 45 and two are
the two furthest points, and so the distance
between these two clusters is a value of 43,
and that's represented by the height of the dendrogram here
when these two clusters are merged.
Based upon the types of clusters that exist in your data,
you're going to have different shapes of your dendrograms.
If my data looks like this, you can see I definitely have
three very compact clusters, and an associated dendrogram
from a hierarchical technique might look like the following.
You can see that my intra-cluster distance is small,
but my inter-cluster distance is very large,
and so, this is indicative that I actually have
three clusters in my data, so I could use this information
to help guide a k-means clustering, if I wanted to use that.
The dendrogram for this data set
might end up looking like this,
so you can see in this case that I end up with
two sort of basic clusters, where this branch
represents the values here in the middle,
where this branch over here might represent
the outer ring, depending on, of course,
the linkage technique that you use.
If your data is pretty well mixed,
the dendrogram that you end up with
may not be that informative in terms of
the number of clusters that exist in your data.
So, how do you choose the right number of clusters?
With hierarchical clustering, you can specify a minimum
desired distance between two clusters,
and you can stop merging clusters if the closest
two clusters are further apart than this distance.
You can visually inspect the dendrogram,
and essentially find a good cut level,
so, where would you like to cut this
to determine how many clusters that you end up with.
There are more sophisticated techniques:
you can analyze the sequence of distances
during the merging process,
try to find a step in which the distance
between two clusters merged is considerably
larger than the distance of the previous step,
and there are several different heuristics
that will help you with this.
The next technique that we'll look at
is called density based clustering,
and it takes a very different approach
to building clusters than what we've seen so far.