[MUSIC] To start with,
let's discuss divisive clustering. And in pictures, what we can think
of is that at some granularity, our data can be pretty well
described as a set of clusters. So maybe it could even be described
as a set of elliptical clusters using the type of mixture models, in particular
mixture of Gaussians we described before. But then when we dig down to a finer
granularity, what we see is that each individual cluster is actually better
described as a set of clusters itself. And we can keep recursing this idea
where we take each cluster at a given granularity, dig down and
specify it as a set of clusters itself. And this is what divisive clustering does. So as an example, one very straightforward approach is to just
recursively apply R k-means algorithm. So one application that you're
going to look at in your assignment is clustering Wikipedia articles,
which we've looked at in past assignments. But here we're going to take the set
of all these Wikipedia articles and then we're going to apply k-means,
which is k equals 2, as an example. So just split into two clusters, and maybe
at the first split, what we see is that k-means separates all these articles
into articles about athletes and articles about non-athletes. Of course these are learn clusters, we
don't have these labels, these are things that we infer digging down and looking
into the contents of these clusters. Okay, well then we recurse
this process where for each one of these clusters we run
k-means with k equals 2 again. And so maybe at the next level, we have the following set of clusters
where there is a cluster for specific athletes for baseball or
athletes for soccer and ice hockey. And then when we look at the non-athlete
cluster, that splits into a cluster for musicians, artists and actors. And another one's for scholars,
politicians and government officials. And then we can think about
recursing this process. So, for example, maybe we want to
further split the cluster that's about soccer players and ice hockey players to
get at a granularity that better matches what we'd like to come out
of our clustering procedure. Okay, well,
when we're doing divisive clustering, there are a number of
choices that we have to make. One is we have to think about what
algorithm are we going to apply at every step of this recursion. So the example we just walked through
was applying k-means at every step. So doing a clustering at one level. Digging down into each
one of those clusters. Applying k-means again and
again and again and again. Well another question is how many
splits to be made at each level. So that's equivalent to saying what
is the value of k we should use in our k-means recursion. In the example that we just looked at, we
were using k equals 2 at every level, but that's a choice that we have to specify. And finally, we have to decide
when to continue splitting or stopping this process. And there are a number of heuristics that
people look at for the stopping criterion. One is to think about whether
a cluster falls below a certain size. So there are fewer members in that cluster
than its pre-specified threshold, and then if that condition is satisfied, you
would just stop splitting that cluster. Another is to look at
the spread of the cluster. So if the distance from the cluster center to the furthest point in that
cluster falls below some threshold, then you say okay,
well it's a compact enough cluster for what I'm hoping to get out, and
then you stop splitting that cluster. Or another heuristic is to
just continue splitting until the number of clusters that
you've pre-specified is reached. But of course in this case you
get back to having to pre-specify how many clusters you want. Which might have been the thing you
were trying to avoid in the first place. But all of these are just heuristics and often a lot of application-specific
intuition has to come into play and sometimes some manual intervention to
really get at the type of granularity you want to come out of
the hierarchical clustering. [MUSIC]