Welcome back to Mining
of Massive Datasets.
We continue our discussion
of clustering by looking at
hierarchical clustering methods.
To refresh our memory in hierarchical
clustering, you can either bottom or
top down.
In bottom up methods, each point,
each data point is initially
in a cluster of its own.
At each step we find the two
closest clusters and
combine them into a single cluster.
In divisive methods, all the data points
are in a single cluster to begin with,
and we recursively split
the cluster as we go along.
In this lecture, we're going to
focus on the agglomerative or
the bottom-down approach,
where we start with each data point as is
its own cluster and
then combined clusters.
The ideas in the lecture can be easily
adapted to divisive methods as well.
The key operation in hierarchical
agglomerative clustering is to
repeatedly combine the two nearest
clusters into a larger cluster.
There are three key questions
that we've to answer in order to
build a hierarchical clustering algorithm.
Those three important
questions are the following.
How do you represent a cluster
of more than one data point?
We need,
we need a representation of a cluster, so
that we can figure out which
clusters are close to each other.
And that brings us to the second question,
which is how do you determine
the nearness of clusters, so that we
can combine the two nearest clusters?
The third question is, as we,
as we keep going along combining clusters,
when do you decide to stop and
produce a final output?
So, we look at each of these
three questions in turn.
Let's start with a simpler
case of a Euclidean space.
In Euclidean space,
we can always average two points,
and the average is also a point
in the Euclidean space.
This gives us a simple answer
to the question of how do
you represent a cluster of many points?
We can represent the cluster
by its centroid,
which is the average of its points.
And to determine the nearness of clusters,
we just measure the cluster distances by
measuring the distances between
the centroids of the clusters.
An example will make this clear, here we
have six points in a Euclidean space.
These the, the these O's represent
data points in a Euclidean space,
and we're going to apply
an agglomerative clustering methods.
initially, let's say we determine
that these points, 1, 2 and
2, 1, are the closest points.
We combine them into a single cluster.
And now we're going to represent
this cluster by its centroid.
To compute its centroid, we have to
compute the average of the two points,
which is just the average
along every dimension.
So, the average of the points 1,
2 and 2, 1 is the point 1.5,
1.5 which is the centroid of
this newly created cluster.
Now we have, five clusters, remember
we started with each data point as its
own cluster, and we have combined two of
the data points into the single cluster.
So now, we have five clusters.
Now we need to find,
the nearest pair of clusters.
And as it turns out,
the nearest pair of clusters is
the pair of points 4,1 and 5,0.
And once you've created this cluster,
we then represent it by its centroid.
Now, the centroid of this
cluster is the point 4.5, 0.5.
Now, the 4.5 is obtained just by averaging
the x coordinates of the two points and
the 0.5 is obtained by averaging
the y coordinates which are 1 and 0.
So now, we have four clusters, okay?
And as we go along merging clusters,
we create this this artifact
called a dendrogram.
And the dendrogram shows how we merge
data points and clusters as we go along.
In the first step, we merge the, the two
blue data points, and in the second
step we merge the two green data points,
and that's what the dendrogram indicates.
Now, in the next step,
we determine that the two closest
clusters are the cluster with centroid 0,
0 and cluster with centroid 1.5, 1.5.
And we and we can measure we do this just
by measuring the distance between (0,
0) and (1.5, 1.5), and
finding that to be the shortest
distance between any pair of clusters.
Once we do that, we can combine the three
points, (1, 2), (2, 1) and (0, 0),
into a single cluster and we can represent
it by its centroid, which is 1,1.
Now, to determine the, that
the centroid of this combined cluster,
we have to average all three points,
1,2, 2,1 and 0,0.
And the average in the x you know,
in the x axis is 0 Plus 1 plus
2 which is 3 divided by 3 gives you 1,
and similarly along the way axis.
So now we have three clusters,
one cluster centroid 1,1,
another with centroid 5,3, and
the third was centroid 4.5, 0.5.
And when we measure the inter cluster
distances between these three centroids,
we determine that the the two
closest are 5, 3 and 4.5, 0.5.
So, we can combine those, and
that new cluster has centroid 4.7, 1.3.
Now, we are reduced to two clusters,
and we have no choice at this point but
to merge these two clusters.
So, either we can stop at this point and,
and output these two clusters or
we can decide to merge them further and
create a single large cluster.
And now, a single cluster doesn't
make a lot of sense because we,
our goal was to end up with you know group
the points to many different clusters.
But on the other hand, even if we do
merge these two clusters and create
a single large cluster, the dendrogram
actually shows the order in which these
merges the merges happen, and it contains
very useful information in many cases.
For example, if the data point's
actually represent you know,
of species of of, of different animals,uh,
then the dendrogram represents the family
tree of how these species evolved.
Now, there was the easier Euclidean case
of hierarchical agglomerative clustering.
But what if you have
a non-Euclidean space?
The problem with
a non-Euclidean space is that,
it's not possible to average points and
create a centroid.
The centroid may not be a,
a valid point in a non-euclidean space.
So, the only points or locations we
can talk about in a non-euclidean
space are the points themselves.
There is no concept of average, and
therefore we cannot continue to using the,
the centroid to represent a cluster.
So instead, we have to use a different,
concept, called a clustroid.
And a clustroid is a datapoint that's
closest to the other point in the cluster.
So, once we use clustroids
instead of centroids, and
we look at an example of clustroids in the
next slide, we can determine the nearness
of clusters by treating the clustroid
exactly as if it were the centroid.
And we can measure the distance
between two clusters,
we are measuring the distance
between the clustroids instead of
measuring the distance
between their centroids.
Here's a cluster on three data
points in a Euclidean space.
Now, the centroid,
which we saw how to compute,
is just the average of all these
data points in the cluster.
The x here marks the centroid
of the three data points shown.
Notice that the x is
actually a data point that
was not among the original three
data points in, in the cluster.
It's an artificial point that we
created to represent the, the cluster.
Now, the problem in non-Euclidean
spaces is that we cannot create this
artificial point.
And therefore, we just have to
pick one of the three points as
the clustroid to represent the cluster
instead of using x, the centroid.
So, in this case, for
example, we might pick the,
the points shown at the clustroid
to represent the cluster,
because intuitively,
it's in the middle of the cluster, and
it's close, and it sort of seems to
be equidistant from the other points.
And therefore we've picked the,
the highlighted point as the clustroid.
Notice that the clustroid is
actually an existing datapoint.
It's not the centroid, but for
all practical purposes we can treat it
as a centroid in clustering algorithms.
Now we've defined the Clustroid to
be the point that is closest to
the other points within the cluster.
Now how exactly do we define
this notion of closest point?
It turns out that there are multiple ways
of defining the notion of closest when we
are picking the Clustroids.
For example,
we might want to pick the point that is at
the smallest maximum distance to
other points, by which we mean,
we measure the distance between
every pair of points, and
then we find a point such that the maximum
distance between that point and
any other point in the cluster
is as small as possible.
Instead, we might look at the point
with the smallest average distance to
the other points, or we might look at
the point with the smallest sum of
squares distance to other points and
pick that as a clustroid.
Depending on the application, one or
the other of these notions of clustroid
might make more sense than the others.
So far we've addressed the, the first two
of three key questions of clustering,
the first being,
how do you represent a cluster?
And the second being,
how do you represent,
how do you determine
the distance between clusters?
We now turn to point three,
or the termination condition.
How do you know when to stop
clustering and produce an output?
The first approach is to pick
a number k up front, and
stop when we have k clusters.
Now, this approach makes sense when
we know up front that the data falls
naturally into k classes.
For example, the data might be about,
galaxies and
quasars, and we know that there
are naturally two classes, galaxy and
quasar, and
once we have two clusters, we stop.
The second approach,
when we don't know the number k up front,
is to keep clustering and, and
stop when the next merge of clusters
would create a bad cluster.
Now,how do you define a bad cluster?
We define a notion called cohesion, which
measures the goodness of a cluster and
when the cohesion value falls below
a certain level, you've created a bad
cluster and we stop when the next
merge would create a bad cluster.
How, how exactly do we define
this notion of cohesion?
There are multiple approaches
to defining cohesion.
The first approach to cohesion is to
use the diameter of the merged cluster.
Now, the diameter of the merged cluster is
the maximum distance between any pair of
point in the cluster.
We might decide to stop
clustering when the diameter of
a newly merged cluster exceeds
a certain preset threshold.
The second approach is to use radius.
The radius is the maximum distance of a
point from the centroid or the clustroid.
And we might decide to stop clustering,
then we would produce a cluster of
greater than a certain threshold radius.
The third approach is to
use a density based model.
Now a density of a cluster is the number
of points per unit volume of the cluster.
One way of defining density is
to simply divide the number of
points in the cluster by the diameter or
the radius of the cluster.
We might instead divide the number
of points by a power of area such as
a square or a cube.
And at a point where the next merge would
create a cluster with a density lower than
a certain piece of threshold, we would
stop merging, and produce a final output.
Notice that in each case, we set a
predefined threshold either for diameter,
radius, or density, and stop when the next
merge would violate that threshold.
We turn now to implementation of
hierarchical agglomerative clustering.
At each step in hierarchical clustering,
we need to find the closest pair
of clusters and merge them.
In order to find the closest
pair of clusters,
we need to compute pairwise distances
between all pairs of clusters.
Since we start with each point
in its own cluster initially,
there are order n clusters,
where n is the number of points, and
therefore computing pairwise
distances takes time order n squared.
Over all we might have to do order n steps
of merging, and therefore the overall
complexity of hierarchical agglomerative
clustering is order n cubed.
[SOUND] Now if you do a careful
implementation using priority queues,
you can reduce the complexity
to order n squared log n.
N-squared log in though
is still too much for
really big data sets
that don't fit in memory.
When n is of the order of millions,
order n squared log in,
can get out of hand pretty soon.
That's why hierarchical clustering
is not commonly used for
really big data sets
that don't fit in memory.
It's primarily used for
small data sets that do fit in memory.
When we have very large
disk-resident data sets,
we use other methods of clustering,
which we turn to next.