Hello everyone.
Welcome back to Mining
of Massive Datasets.
In this lecture, we're going to cover
a very important topic, clustering.
We're going to kick off our discussion of
clustering by looking at some applications
of clustering that tell you why we
need clustering in the first place.
Then we're going to look at
the overview of the most common methods
used for clustering.
The basic problem of
clustering is quite simple.
We have a cloud of data points.
Here you see data points
in two dimensions.
And we'd like to get some understanding of
the structure of the data points beyond
just seeing them in the two dimensions.
For example,
it's intuitively clear by looking at
these points that there
are three groups of points here.
There's a group of points
that group together here.
There's another group here.
And there's a third group here.
And it looks like we have two outliers
that don't fall into any of the groups.
The rule of clustering is
to find groups like this.
Except in much higher dimensional
spaces than two dimensions.
More formally, given a set of points and
a notion of distance between points,
we want to group the points together
into a number of clusters or groups.
And you want to group them together so
that members of a cluster are close or
similar to each other using the notion of
distance that we've defined previously.
And members of different clusters
are far away from each other or
dissimilar from each other.
Usually, the points that we'll be dealing
with will live in high-dimensional space.
A space with thousands or
hundreds of dimensions.
And similarity will be defined
using a distance measure, from,
from among the distance measures
that we have covered earlier,
such as Euclidean, Cosine,
Jaccard or edit distance.
Going back to our example, here we have
points in a two-dimensional space.
And let's say our distance
measure is Euclidean.
Observe that points in the group
that are highlighted are close to
each other by cleanly distance, and
are closer to each other than they
are to points outside this group.
We'll call this group a cluster.
Similarly, we have two more
clusters based on a similar notion.
And finally, we have these two outliers
that are not close to any of the clusters.
Now it, that example looked easy, but
in general, clustering is a hard problem.
For example,
here we have a group of points, and
you can see that, the-the different colors
actually denote, different clusters,.
But the problem you'll notice is that,
unlike the previous example where the
clusters were cleanly separated from each
other, in this case, the clusters
actually overlap with each other.
For example, there are some blue points
that are among the orange points here and
some among the green points here.
And you can notice that the clusters
are kind of smeared over and
mixed into each other.
It's hard to find clear boundaries between
the clusters, as in the previous example.
So these are a kind of real problems
that we are going to tackle when we
deal with clustering in the real world.
So why is clustering hard?
Clustering two dimensions
actually looks quite easy.
Clustering small amounts
of data also looks easy.
And in most cases,
looks are actually not deceiving.
Clustering in two dimensions, or
small amounts of data,
is actually very, very easy.
The clutter starts when you
create a number of dimensions.
Many applications don't involve two,
but 10s or
100s or 1,000s or
even 10s of 1,000s of dimensions.
And high-dimensional spaces
are fundamentally different from
low-dimensional spaces.
The problem is that in high-dimensional
spaces, almost all pairs of
point are at approximately
the same distance from each other.
And so, it's not intuitively
clear how to group them together.
These problems have become a pattern as
we work with high-dimensional spaces.
Let's look at some real applications,
starting with SkyCat.
SkyCat is a catalog of two billion
astronomical objects, and each object is
represented by its radiation signature
in seven dimensions of frequency bands.
The problem is to take these
seven dimensional data points and
cluster them into real world objects
such as galaxies, stars, quasars and
so on which are most similar to each
other than they are to other things.
As a second example let's
look at Clustering CD's.
Now intuitively,
music divides into categories, and
customers prefer a few categories or
genres of music.
But what are categories really, right?
We'd like to represent a CD by
a set of customer who bought it.
And we'd like to say that similar CDs
have similar sets of customers, and
CDs magically group or cluster together
based on the customers they have.
For example,
there might be a group of CDs that are,
you know, that are classical music,
and they have a, a,
a group of customers who
are classical music aficionados.
And there's another group of CDs that
are punk rock that are bought by
a different set of people.
Another example is Clustering Documents.
We'd like to group together
documents on the same topic.
But what's a topic, really?
A topic is just a set of words
that appear together frequently.
Now documents with similar sets of
words may be about the same topic.
Right, so
we want to cluster documents based on
their similarity in the space of words.
A dual problem is to find
topics instead of documents.
A topic is just a group of words
that co-occur in many documents.
So we could instead look at words
in the space of documents and
cluster those rather than clustering
documents in the space of words.
And they do that with find topics,
instead of document clusters.
Let's talk briefly about
distance measures.
We've looked at varied distant measures,
such as Cosine, Jaccard, and Euclidean.
And depending on the way we represent the
objects that we are clustering, one or,
one or the other of these distance
measures may be more appropriate.
For example, let's look at our
examples of documents or music.
And different ways of
representing documents lead to
different distance measures.
We might represent a document
as a set of birds or
a bag of birds that appear in a document.
In this case, the appropriate
difference measure to use is
a Jaccard distance since
we're dealing with sets.
Alternatively, we can think of a document,
as a point in the space of words.
Here there's one dimension for
each word, and
each document is an N dimensional point.
The dimension i is 1 if the word i
appears in the document, and 0 otherwise.
Since we represented documents by points,
the natural distance measure here,
you clearly in distance
between the points in space.
Alternatively, we can think of a document
as a vector in the space of words.
A document is a vector from the origin
to the vector x one through x N,
where x i is one if word i appears
in the document, and zero otherwise.
Think about documented vectors.
The natural distance measured.
If the angle between the vectors or
the cosine distance.
Notice that each different way
of representing the same object.
These naturally to defend
the distance measure and
depending on the application,
a certain representation of
distance measured might make
more sense than another.
Now that we understand distance measures,
here is an overview of the important
methods of clustering.
The two important methods of
clustering are Hierarchical methods and
Point assignment methods.
And within Hierarchical methods,
we can either go bottom up or top down.
Bottom up methods, or
agglomerative methods, start with each
point in, in a cluster by itself.
Now once we have each point
in a cluster by itself,
we repeatedly combine the two nearest
clusters into a single cluster,
and we stop at some point and
we have a set of clusters.
Divisive or top down methods
initially place all the points in
the same cluster and then keep recursively
splitting the clusters until we end up
with the desired number of clusters.
Point assignments methods
work differently.
In Point assignment methods,
you always maintain a set of clusters,
let's say k clusters at any point in time,
and
then you repeatedly assign
a point to its nearest cluster.
And we proceed until each point
is assigned to some cluster.