In this module we've talked about
a document retrieval task and we've also talked about a notion of clustering where
we're trying to uncover some underlying structure in the data and we talked
about many different areas in which this notion of clustering can be really useful.
So let's go through the workflow for a clustering algorithm.
And if you feel like you already know this at this point because you've seen this
workflow now in two other modules.
Well, wake up!
Because this one's going to be a bit different.
Okay, so let's talk about our training data.
Here, our training data for
a document clustering task is going to be a document ID and
document text table.
So we have a whole bunch of documents.
And we have all the texts associated with each of those.
And then we're gonna extract some set of features.
And we talked about a lot of different ways to represent a document.
But the one that I'll use just as an example here is our tf-idf.
Term frequency-inverse document frequency representation.
And then what we're gonna do is we're gonna try and
cluster our documents based on this representation.
So we're gonna put these features through some machine learning model.
Which in this case is a clustering model.
And we're gonna output for each document a cluster label.
So the output white hat is our cluster label.
Okay, so here's where things get interesting,
because we wanna assess the accuracy of our cluster labels.
Well, in this case we don't have true cluster labels, so
I should say this is our predicted, or estimated, cluster label.
But we don't have a true cluster label to compare against.
So this y here, it does not exist.
And that's because, as we talked about, we're in an unsupervised learning setting.
Unsupervised.
Okay.
So we don't have that but
somehow we wanna assess some measure of accuracy of our clustering.
So let's draw a little picture here which is gonna be our Voronoi tessellation and
our k-means algorithm where we have some set of cluster centers and we have data.
I should say our data look like this, I don't know,
I'm just gonna draw some points here.
And the measure of accuracy that we're gonna use,
the way we're gonna measure our quality is to look at how coherent our clustering is.
So we're gonna look at the distances from each observation to
their assigned cluster center.
And a good clustering algorithm has those distances very small.
Okay, so the goal is to minimize these distances and so what we see is to measure
this accuracy, to measure these distances, what we need is our data.
We need our tf-idf vectors.
So those are gonna come in here, and then we also need the cluster centers.
And so W hat, that's our current estimate of,
that's our model parameter here and the k means algorithm.
It's our cluster, whoops.
Let's see if we can spell that correctly, cluster centers.
That's what W hat represents.
And so of course to measure these distances we also need W hat.
So instead of having actual cluster labels to assess accuracy we're
gonna take our document representation and our cluster centers.
Plug it into this quality measure,
which is looking at distances to cluster centers.
That's our measure of error, though it's not really an error.
It's just a measure of.
Oops.
Just a measure of quality.
So I won't put that word there.
Okay, so I think that's a little confusing.
But let's just write distances to cluster centers.
And then what's our algorithm?
We're talking about k-means as a method of doing clustering.
Of course there are others, but let's focus on k-means, well,
what's k-means doing?
Let's just redraw this diagram, actually, I can just switch to another color.
That will save us some time here.
Well, k-means is trying to minimize this distance, or the sum of these distances,
and the way it's doing that is iteratively it's updating so
this was our W hat that we had before and we're moving it
to a new W hat that represents the center of mass of these points.
So these points are getting shifted.
And this point will go directly on top of that observation
and so this is the work flow of clustering.
Let's just say it at a high level one more time.
We take our documents, we represent them in some way, using either raw word counts,
tf-idf, normalizations of these things.
Lots of different bigrams, trigrams, things we can look at for
our document representation.
Then our clustering algorithm, like k-means is producing clustering labels and
iteratively, we're looping through here again and again updating
our cluster centers, that's the parameters of this clustering model.
By looking at how far our assigned observations are to those cluster centers.
So in this module in contrast to other modules we actually presented you with
some of the algorithmic details behind the methods that we're looking at.
Specifically for clustering, we talked about the k-means algorithm, and then for
our document retrieval task, we also talked about doing nearest neighbor
search, and provided some of the algorithmic details for that, and
you specifically explore that in an ipython notebook for
doing Wikipedia entry retrieval.
So, at this point, you really should be able to go out there and
build a really cool retrieval system for doing news article retrieval.
Or any other really, really, really cool retrieval that I can't think of right now.
But of course there's lots of interesting examples.
So go out there and think of ideas that I can't think of right now.
[MUSIC]