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.