[MUSIC]
Well let's look at an algorithm for doing clustering that uses this
metric of just looking at the distance to the cluster center.
Okay, so here, we see the data that we're gonna wanna cluster.
And this algorithm, which is called the k-means algorithm,
starts by assuming that you are gonna end up with k clusters.
So you specify the number of clusters ahead of time.
So the reason the algorithm is called k-means is we have k clusters, and
we're looking at the means of the clusters, just the cluster centers,
when we're assigning points to the different clusters.
Okay, so let's talk about how we initialize the algorithm.
So the first thing we do is we just one example.
There are many ways to initialize where we put the cluster centers.
We will talk about these things more in-depth later.
But for now,
let's just assume that we randomly assigned three different cluster centers.
If we're going to assume some, three means algorithm here.
And then the first step is we're going to assign every observation
to the closest cluster center.
So this observation here gets assigned to the red cluster.
These observations are all closest to the green cluster, or this green center here.
And these are all closest to the blue center.
And a way to do this is something that's just called a Voronoi tessellation.
So we look at the cluster centers and well, we can do our define,
let me switch again to this magenta color.
So here the cluster centers.
And we can just define these regions here.
And these regions represent areas where any observation we might get,
so any new observation, that's a very bad color on red.
What other colors do I have?
How about white?
Cool, white.
So some new observation I get here, if it falls within this red region,
I know it's closest to this red cluster center.
So that's what these colored regions are representing.
Okay so, that's the first step of the algorithm.
So, what I end up with are observations that are assigned to clusters.
But I just randomly initialize those clusters centers, so I probably don't
believe that that really represents the structure underlying the data.
So what I wanna do is I wanna iterate this process, where I then wanna update what my
definition is of the cluster center based on the observations that I've assigned.
So if you remember this red cluster here,
it just had one observation assigned to it.
So when I go to revise the cluster center for that cluster,
it just moves to the previous observation.
But for this green cluster, if I look at the previous cluster center here,
well I'm gonna move it to the center of mass of all
these observations that have been assigned to the green cluster.
And the center of mass of all of them is here,
so this becomes the new cluster center.
And likewise, I do this for all of the blue observations.
This is the new cluster center for this blue observation.
Okay, so now I have a new set of cluster centers.
And what I can do is redraw this Voronoi tessellation, and
reassign my observations to the nearest cluster center.
And then I iterate this process until convergence.
[MUSIC]