[MUSIC]

Finally, let's wrap up by providing a few more details on agglomerative clustering.

So one thing worth discussing are,

what are the choices we have to make in agglomerative clustering?

One is, what is the distance metric we're going to use to compute

the pairwise distances between points?

And then the other is, what is the linkage function we're going to use to

compute the resulting distances between pairs of clusters?

And for single linkage, that linkage function is just

the minimum distance between any pair of points appearing in the two clusters.

And finally, another important question is,

where are we going to cut the dendrogram?

So one version of that question is just, where would we place this horizontal cut?

But another thing is that we don't have to make just a horizontal cut,

we can make some weird cut through this tree.

So this is something where really the art of the method comes into play.

And often you have to build in a lot of application-specific information

to think about how to cut the dendrogram.

Well, if you're using hierarchical clustering for some task of visualization

of the data, then often it's preferable to produce a small number of clusters.

So that would define how you'd cut the dendrogram.

But in contrast, if you're trying to do something like outlier detection, where

you want to detect if some data point is very different from other data points,

then you might want to think of other ways of defining the number of clusters,

or equivalently, how to cut the dendrogram.

In this case, one thing you can do is just use a distance threshold,

which is the same method that we described in the previous section.

Or you could do even fancier things, like something called the inconsistency

coefficient, where what you do is, you compare the height of any given merge

to the average height of merges below that point.

Then if that height is much higher than the average heights of merges below,

what it indicates is that that particular merge is merging clusters that are very

far apart relative to what the merges were below that point.

So that might be a reasonable point to cut the dendogram and

keep those clusters as separate clusters.

So just as a little visualization of that,

maybe we have some data points that are fairly far apart.

And then you have this very tightly clustered set of data points here,

and maybe another very tightly clustered set of points here.

Well, if we're just simply cutting the dendrogram based off of a threshold,

you might end up merging these points and keeping these points as a cluster.

But instead, what you might want to do, based on the structure of the data,

is keep these as separate clusters.

Because within that cluster, the distances between points are really, really small,

whereas the distance of this particular merge between these two red clusters

was much larger than the distances of merges within each cluster here.

So this cut of the dendrogram could allow you to do something like the following.

But to be clear, no cutting method is the correct cutting method.

And instead, like we said,

a lot of application-specific intuition or information comes into play.

And a lot of heuristics are often used to determine how to cut the dendrogram.

And the results produced by the hierarchical cluster method,

whatever's output as the set of clusters, is really sensitive,

of course, to how you cut that dendrogram.

You can get very different solutions based on that approach.

So you have to think very carefully about that.

And instead, you can often think about hierarchical clustering as a way

to produce different possible clusterings as you vary a threshold or

as you vary the way in which you cut the dendrogram.

There are also some important computational considerations when we're

thinking about applying hierarchical clustering methods.

So for agglomerative clustering we have to compute distances between every pair of

points when we're going to compute the distances between pairs of clusters.

And this is really, really expensive,

just as we explored in our nearest neighbor method for retrieval.

And you can show that a brute force algorithm for agglomerative clustering has

complexity on the order of N-squared log N, where N is the number of data points.

But just like in nearest neighbors, we talked KD trees and

efficient ways of pruning the search space.

Well, here we can also think about using the triangle

inequality to rule out certain potential merge moves.

And if you do some really fancy things, the best-known algorithm for

performing hierarchical clustering has complexity order N-squared,

instead of N-squared log N, but that's still quite a lot if N is very large.

There are other considerations based off of the structure of your data, too.

So for example, one thing that can happen in single-linkage is something called

chaining, where you can have a sequence of points where the individual

distances between points is really small, and so the points end up getting merged.

But if you look at the resulting cluster, you can have members that are very,

very far away.

And in a lot of applications, having this type of cluster might not be desirable.

So instead, one approach to helping fix this chaining issue

is to consider other linkage functions.

So one thing you can look at is something called complete linkage,

where instead of computing the minimum distance between any set

of points appearing in these two clusters, you look at the maximum distance.

And in this case, if we had looked at the maximum distance in this

really long chain, we wouldn't have ended up merging these clusters,

because that maximum distance would have been very large.

And as an alternative, you can look at something called the Ward criterion,

which looks at the variance of points within a cluster.

But both of these alternative linkage functions end up implicitly imposing,

in essence, shape restrictions on the clusters.

So it does help with this chaining issue, but you get back to things that look

closer to things like the Mitchell or Gaussian type reversal.

It's where you're assuming a specific form that your clusters are going to take, and

in essence kind of trying to rule out some other specific shapes that might actually

be what defines the cluster.

So again, there are just a number of choices you have to make, and

there are implications to those choices.

So think carefully when you're specifying exactly how you're performing

the hierarchical clustering.

But in summary, hierarchical clustering can be really powerful.

It performs clustering at multiple granularities, and

you can get quite descriptive clustering results coming out of this procedure.

[MUSIC]

Agglomerative clustering details

聚类与检索

与讲师见面