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.