So we're going to talk about a different clustering algorithm that,
that at least doesn't have that weird property and it has
some other nice, positive properties. But, it, there's trade-offs. There's
always trade-offs in clustering. So k-means clustering is what we're going to
talk about next. And, and the, the feel, the basic
flow of the algorithm is like this. We're going to first pick
a K. K is going to be the number of clusters
that we're going to try to produce. And the way it's going to
do it is by picking K of the points at random to be centers. And then we're
going to repeat the following process, each center is going to
claim it's closest points. So, we're going to cluster all the
points based on how close they are to the k
centers that we've defined. Then, we're going to recompute, based on
that clustering that we just did. Recompute the centers.
And the center would be the average of the points
in its cluster. And then we're going to tick tock back
and forth. We're going to go back and repeat 'til convergence.
For the new centers claiming their closest points. The new
groups of points computing their average and back and forth
like that. So let's step through an example and then
and then we'll try to analyze what this actually does.
>> Okay, that makes sense.
>> Alright. I'm going to do K equals two. In
this example the same set of points that I
used in the previous example. And I'll just you
know, kind of randomly. Choose two of them to be
the two clusters the red cluster and the green cluster alright?
>> Okay.
>> So that's this, that's this first step done. Now
what we're going to do is each of these centers is going to
claim. Their closest point. So we are going to take all
the points in this space and assign them to one of
the other of these two clusters. And it ends up
looking like this. Alright? So this is now the points that's
closest to the green centers have all been put into
a green blob. The ones that are closest to the red
center, all get put into the red blob.
>> Okay.
>> Okay? So, that's, that's step two. Now what we do is recompute
the centers. So the center of the red blob is still pretty close to
where it was before but if you look at the green blob, the
center of the green blob ought to be to the right. You see that?
>> I do, I do. In fact it should be a lot more
to the right cause there's a whole lot of points on the right.
>> Yeah, though, I did this sort of by eye, so it doesn't, yeah,
you're right. It should be, it should be closer to the clump on the right,
but I, I didn't quite do it that way.
>> Okay.
>> So I moved it just a little bit more to the right. See that?
>> Mm-hm.
>> But now we can repeat this process. We
can say," Okay, now everybody join the group that
you're closest to." And one nice thing that happened
now is that the group of points on the
left all joined together in red and this sort
of weird hammery thing on the right became green.
And now we're going to recompute our centers again.
We're going to say, where's the center of the clusters given
the way that they've been painted. And that, again, move things
a little bit to the right in both cases. We ask
every point to join the team that they're closest to. And
we get that. And that actually turns out to be exactly
the same clustering that we had a moment ago. So when
we recompute the centers, they remain unchanged. And so we've converged.
So it, it seems to have clustered things reasonably given that
I didn't actually run this. I just did it by hand.
>> Okay. Can I ask a question?
>> Oh, please.
>> Okay. You seem to have drawn this in such a way that the centers
are always one of the points. But that's not really meant to do, is it?
>> No, no. It's definitely not what I meant to do. It's it realy is just.
It, it, doesn't. The center is not necessarily
a point that's in the collection of objects.
>> Right.
>> Yeah thanks for pointing that out.
>> Okay, so this makes sense and that
look better than what single linkage clustering, or single
link clustering, or single linkage or whatever it is called, clustering did.
>> At least for this kind of example, yeah, it, it
produced kind of more compact clusters without giant holes in them.
>> M-hm.
>> So so do you have any questions about this? About what it does.
>> Yes. So, so, [LAUGH] I think I might have
some questions Michael. And they may even be questions you'd like
to here. So I asked one question about what the synergy looked like. So I have a
couple of questions, one is does this always converge?
Does it always come up with a good answer?
>> Yes, those are good questions.