We're now going to look at some real applications of the k-means algorithm.
And by real application, I simply mean looking at some real data.
And this is just to give you a rough idea of what it can do.
Um, and a couple of times I'll- I'll- I'll give you some editorial content
about like basically how amazing it is, is what I'm getting at,
And I'll- I'll say it very sensitively, and we'll see how that works.
Okay, so the first thing is we're gonna look at a very famous dataset, um, uh,
maybe it's two famous, it's the MNIST,
ah, so images of handwritten digits.
So I think this is from the post office or something like that.
And so, um, there's some examples down here.
Uh, these are people writing, ah, digits.
Uh, they've been, had some preliminary processing, you know,
they kind of got them approximately straight and they got about the same size.
Um, but, you know,
they're- and the human doesn't have any problem,
ah, reading these, mostly I should add, right, you know.
Um, so, um, okay,
so here, here are just 25 examples and you look at them and some are clear,
like that, that 3 is pretty clear,
that's pretty clearly a 0.
Um, I don't know if we can find one that looks pretty bad,
ah, I don't know.
They all- they all look pretty good to me.
Okay. So it's a dataset, um,
with 60,000, ah, handwritten digits.
Ah, image, these are images.
Um, each image is 28 by 28 pixels and each entry in that vector, so it's, ah,
represented as a vector of, uh, 28 squared,
784 length, and each one gives you the grayscale intensity.
Um, and we'll take it between 0 and 1 because that's sensible.
I think the actual one's between 0 and 255 for historical reasons,
but we'll take it between 0 and 1.
So for example, that corresponds to a 784 vector and we can look at it,
and by the way, uh,
0 is black and,
ah, so that vector,
if you were to look at it, there'll be a whole lot of entries that are just 0, right?
Um, a few would be 1, right?
Those would be the ones that whatever- whichever the-
or the pixels corresponding to where the white is,
which is where it's drawn, that would- those would be one.
So, um, so you can even imagine in your head what those vectors, uh, would look like.
Okay. So that's a very famous, ah,
very- very famous, uh, dataset.
Um, and these are just 25 examples and just get a picture of what they look like.
Okay. So we're going to run k-means.
Uh, and this is just an experiment,
this is just to be- this is just to run k-means, right?
So what we do, um,
is we- we take 60,000 vectors each of length, or,
uh, I guess more correctly,
I should say dimension 784,
um, and we're going to run k-means on it.
Ah, then that's it. And we're going to ask for, um,
20 different, you know,
partitioning these into 20 different, uh, groups.
Now, I want to add something about this before we get into what actually happens.
Um, I mean, you and I know that there's,
you know, that these are images, they're two-dimensional images.
We know what- we know what digits are and things like that.
Um, you know, k-means is profoundly stupid.
It simply sees a vector of zer- numbers between 0 and 1,
which are grayscale levels.
It has no idea what- it does
has absolutely no idea what a digit is or anything like that.
Okay, so that's just going to mention that.
Okay. So- and we run it 20 times with different,
ah, initial, uh, initial assignments.
And the convergence, uh,
is shown below, right?
And so, um, so here this is just three of them.
Um, I think this red one is the one that ends up
with the worst clustering objective if we were to blow that up,
and the blue one ends up, uh,
with the best clustering objective.
At least the best that we found,
uh, in our 20 runs.
Um, oh, I should add something here.
Um, this shows you immediately that this algorithm is a heuristic, right?
That we know on the red run,
whatever, you know, here,
you ended up with an objective and there is another clustering with a smaller objective.
So it failed to find the minimum- the minimum,
uh, objective value clustering, right?
So, um, it is actually quite likely that the blue is also not the minimum.
The good news here though is,
if it's not the minimum, it's awful close.
Okay. So we'll- we'll just leave it that way, okay?
And you can see it, it- it converges in,
you know, 25 steps or something like that.
Okay? Um, so here the- here are the representatives you find.
Um, now remember, this knows absolutely, we
certainly did not tell it for each digit what the digit was,
like we didn't tell it, for example,
this- this one is an 8,
this one is a 3, this one is a 0, that's a 4.
We didn't,.nothing is there, this is just seven,
you just get- get a vector which is the image, okay?
And if you take a look at what pops out, it's kinda stunning.
Like, um, like that's kind of a 0 right there.
I mean, so most- most of the-
most of the vectors in that cluster actually correspond really to 0.
Um, you know, it kinda discovered, uh,
you know, that's the one- that's a different kind of one, right?
Um, now, some, of course,
bleed across integers, right?
Like that's probably got some 4s in it, and some 9s.
Um, but it's actually kinda cool like these are mostly- these are probably mostly 5s.
Um, so that- that's it.
I had 60,000 vectors and I clustered into 20 groups,
and, you know, each one is probably on the order of 3,000, I don't actually know.
I don't remember, but the point was it clustered them.
And then what you're seeing here is actually the average of all the ones in that group.
And so they're sort of smoothed out, they're
kind of iconic or archetypes, right?
Um, anyway, it's very, uh, ve- very cool.
So the only thing- the only takeaway here,
this actually has no particular, uh,
immediate value, obviously, is just to say that here's an algorithm that took in vectors.
We did not even tell them that the vectors were represented images.
Number 1, um, it has no knowledge that these are images, that's number 1.
Number 2, um, number 2,
not only does it not know that these are images,
it has no idea that these were digits.
Okay? So, um, you know,
it's pretty cool, right?
Um, and- or, uh, I mean,
unless you-unless you do read, let's say, you know,
whatever Hindi script, um,
you would get something similar.
If you- if you just took 50,000 or a million
pictures of Hindi script out would come something handwritten, right,
out would come something that were the chara-
I mean, if- if you knew something about it,
you'd say, oh, that's such and such, that's that.
But anyway, I just think it's kind of amazing here that, uh,
it has actually quote, figured out, ah,
that- that there are these groups of,
well, here it had 20.
But you can see that, ah, you know,
that it actually kind of figured out,
but some of these things are- are,
uh, some- some of these are digits.
Okay. So, um, all right,
so that's- if you're not impressed by this,
then you really aren't quite thinking about what's happened here, right?
Um, yeah.
So I'd encourage you to go look at those vectors and see if
you can say what kind of- what digit it is or something like that, you can't.
That's- that's the hint. Okay.
The next one, and this is a real application now,
this is called topic discovery,
uh, Well, I'll give you an example of it.
Uh, very-very elementary example.
But- but, you know,
people do things much, much more sophisticated,
but this is already kinda sophisticated, it works like this.
What we did is we took 500 Wikipedia articles. They- I can't remember what they were,
maybe the 500, whatever most visited, I- I, whenever they were.
Anyway, we took 500 Wikipedia articles,
and then we took a dictionary with about 4,500 words, 4,400 words, whatever,
something like that, okay?
So what we did is, you represent each of those 500 articles, as you represent it,
uh, as a vector,
which is the word count vector, working on a histogram, actually, right?
So, um, there 's gonna be a lot of 0s in those vectors, right?
Because if there is a 0 in a vector,
it means that that dictionary word did not appear in that article,
and there'll be- I mean,
there are some, obviously,
there's some words like the, and,
but, that kinda of thing which appear in many articles.
But there's- there's like technical terms and stuff like that that
appear only, names might appear only in a few,
okay? So that's it.
Now, I should also mention,
I just want to emphasize how profoundly stupid this is, right?
Uh, so people call this a bag of words model or bag-of-words method.
And the reason it's a bag of word method is cause we
take these article- Wikipedia articles,
they are written in English, right?
So there are actually,
I mean, that there's words.
Those words have meaning.
They're organized sequentially into sentences,
which are organized into paragraphs and maybe even sections.
So the point is, you know,
we read them and we understand what it means, and things like that.
So this thing is so dumb, it destroys sentences.
It does- there is no sections,
there are no paragraphs,
and it's simply literal.
It actually just tells you how often words, uh,
from a dictionary of 4,400 different words,
how often they appeared. That's all it does.
So you could never reconstruct an article from it or something,
or you- you definitely could not run it.
I don't know, Okay. So that's it.
I just- all I'm doing is here is saying- is saying how dumb this is, right?
It- it's pretty dumb,
and you- you could easily imagine,
nothing good is gonna come out of this because,
you know, it's ridiculous, right?
Uh, how- how could you partition Wikipedia articles if you actually do not know
the meaning of words, and have like destroyed
the order in which the words appeared in the document, okay?
All right. that's my preamble. All right.
So we are gonna- we gonna run,
we gonna go-we're gonna partition into nine-nine partitio- into nine groups.
So we have 500 articles.
We're gonna partition them into nine groups,
and what we'll do is we'll run K-means 20 times with 20 different initial assignments,
and what we'll do is here's the convergence for some of these,
um, there's a couple of them.
I think that's the worst one, uh,
the blue is the best one,
and this is just another one.
But there's 20 of them, I'm only showing you 3.
And so the point is we then we take the best clustering.
Oh, by the way, notice that the difference between the best and the worst is, you know,
is the difference between, you know,
6.9 and whatever, 7.2, right?
So not a huge, big deal, okay.
So now we have partitioned 500 articles into nine,
uh, into nine groups, okay?
And just- and remember how dumb this is, right?
That- that K-means has absolutely no clue what those words mean.
Nothing else, just- it just looked at word counts and got 20 groups of vectors there.
Okay. Um, and we'll see what- we'll see what happened.
Um, oh, and we also have the nine representative vectors.
Each of those is a vector of dimension 4423, and it's a word count.
It's like a hist- it's a word count histogram, literally,
it says- it says here's a representative article and here's what it looks like, okay.
So, um, let's look at clusters 1 to 3.
Okay. So, um, what you can do then is you take- let's look at the cluster representative.
So that would be- let's look at Z1.
That's a vector with 4,400 you know,
about 4,400 entries, right?
And we can look at the largest entry.
We could also look at small- oh, the smallest is gonna be about 0.
And we're gonna look at the largest entry,
largest few entries to see what's there,
and here's cluster 1,
and here are the five largest entries in that vector, okay?
That's it. And they're-they're pretty interesting, right?
And these are, by the way, directly interpretable,
0.038 means basically 4%.
So- so but the word- look at the words, they're super interesting,
it's fight, win, event, champion, fighter, okay?
So we recognize these as words as being related, okay?
So, you know, we do because, well,
we understand English and we know what these words mean and things like that.
Please remember this algorithm has no clue what these words mean,
not even the slightest for- for- these are
just numbers like fight is word number, you know, 2173.
Win is word number 1,725.
I mean, I don't- that's all, it knows absolutely nothing else.
So is- this is kind of amazing that this is what came out. Okay,
now, for cluster 1,
we could do something pretty cool.
So I mean, you already have a rough idea of
what- what the things in cluster 1 are gonna be.
But what we can do now is,
we can actually take- we can actually go back to the- the Wikipedia pages and we can say,
show us the articles,
that are closest to the- say,
for example, the cluster 1 representative,
and here are the titles of the articles.
It's in order from the closest to- It's- I mean,
it's the first 10 or something, l don't know, okay.
So they are Floyd Mayweather Junior,
Kimbo Slice, Ronda- actually,
I don't know who- I think it has to do with boxing,
so not that I would know.
But the point is, it kinda makes sense,
like wow, it actually kind of figured something out.
I mean, something emerged, right?
So that clustering is,
I- I don't know, this has to do with like boxing or something. Okay, fine.
Let's look at cluster 2.
Cluster 2 is we go over here,
and here- here are the words, uh,
the most, the words that have the highest value in Z2, okay?
And they are holiday,
celebrate, festival, celebration, calendar.
And once again, the- the,
you know, we recognize these as related, okay,.
So we write that. But the point is this thing knows absolutely nothing.
I mean, so uh, okay.
So it's clear what this is,
let's- and let's look at the articles that are
closest to that representative. They are: Halloween,
Guy Fawkes Night, Diwali, Hanukkah,
Groundhog Day, Rosh Hashanah,
Yom Kippur, Seventh-day Adventist Church.
I don't know how that got in there. That's fine.
Remembrance Day.
Okay, fine. Um, so it's kinda cool and it makes sense.
I mean, this makes a lot of sense, right?
Um, okay, and the third one is- it's got united,
family, party, president, government.
So- and then these would be the kinda things you'd see,
Mahatma Gandhi, Sigmund Freud.
I don't know who Sigmund Freud got there but,
okay, fine, I don't know.
Um, you know, Frederick Douglass, okay, Christopher Columbus,
Fidel Castro, okay, I don't know, Jim Webb next to Fidel Castro, okay.
Okay. So let's look at like, uh,
oh, sorry, I should mention one thing.
Um, in this case,
what we say is that a topic has been discovered.
So we would say that cluster 1 is a topic in our corpus of documents,
and it has just been discovered using nothing but vectors and distance,
and the k-means algorithm.
That's all. It just- it completely discovered, it just discovered the topic, right?
Um, so it's actually kinda cool, um, okay.
Um, all right, so that's the- that- this is the idea then.
Okay. For the next clusters,
again, they all kinda make sense, right?
The first one clearly has to do with singers and singing and things like that.
Cluster 5 has to do with sports,
and it just figured it out.
Just- just figured it out.
Uh, cluster 6, uh,
has to do with- actually,
these are TV series.
Um, it was actually kind of interesting because we're gonna see later
that it-that movies are a separate one, okay?
So here's clusters 7 through 9.
Um, things like; match, win,
championship, team, event, you know,
And cluster 9 is film, million, released, star, character,
and then here are the Wikipedia pages such closest to that cluster representative.
Okay. So-so I'm introducing crazy stuff now.
For example, we can automatically classify new Wikipedia pages.
So somebody makes a new Wikipedia page,
and suppose- let's suppose we stuck with these nine- these nine topics, right?
Because these are, you know, it's clearly,
they're all topical, right?
So if we stuck with these nine topics, um,
and a new Wikipedia page every library day,
lots of new Wikipedia pages are made, right?
And so what you do is you simply do the following.
Um, you calcu- you work- you scan the words-you scan the words, count the words,
you get its histogram,
and then you simply say,
which of our nine representatives are you closest to?
And we're assigning you to that topic. Yeah.
Oh, by the way, I should say that when people really do this,
there's usually a cluster associated with,
I don't know or not any of the other clusters,
right? It's kinda like everything else.
It's the catch-all cluster.
But nevertheless, and that was just completely automated right?
So that just- just- just works this way,
we just kinda go through and stuff like that.
So okay. And again,
I wanna say that if you're not impressed by this,
um, then you're not really understanding what it is.
My point here is that based on,
uh, shockingly little, uh,
about each of these Wikipedia articles, in fact,
all we tell you is the fraction of times 4400 words came up, right?
So I-I just wanna-I wanna say it again because it's-it's worth repeating.
This algorithm has no idea what the meaning of these words are, none, zero.
It has completely- it doesn't understand English,
it does not-we have destroyed in fact the sentences.
There's no paragraphs, there's no syntax,
there is no meaning and yet it has actually discovered,
it has grouped these Wikipedia pages into what we recognize.
We do understand all those things and we recognize
that these are reasonable clusterings, okay.
So it's actually very,
very interesting what- what- what's happened here.
And in fact, it's almost like it's a hint about the material of this class is
that a lot of times stories start with things that are just ridiculous,
like, uh, I'm going to simply count
the number of words in documents and I'm gonna do some- something is gonna happen,
like I'm going to cluster them or I'm gonna make
a prediction or something like that and you'd say, oh,
that is so unsophisticated.
You don't even know what the words mean.
How can anything good come from this, right?
And then the answer is,
that stuff comes out.
Um, so that's- that's kind of a theme of the class.