[MUSIC] K-means might seem like
heuristic algorithm but you can actually view it as an example
of a coordinate descent algorithm. In particular K-means
iterate between two steps. One is assigning observations
to the nearest cluster center. And the other is updating
the cluster centers. Well, this first step where
we assign observations to the nearest cluster center, we can clearly
see from this equation is equivalent to minimizing the given objective. For the second step,
it's a little bit less clear. But we can actually rewrite
this second step as follows, in terms of this minimization
of an objective. In particular minimizing
the sum of the square distances because remember that computing the mean of a set of observations is equivalent
to computing its center of mass and that's exactly what minimizing the sum
of square distances is equivalent to. So now what we see is that we're
iterating between two different steps where each step represents
a minimization of some objective. And so from this we can see that
this is an example of a coordinate descent algorithm. And if the notion of a coordinate descent
algorithm isn't sounding very familiar that's probably because you didn't
take the regression course. That's really, really sad. Go back, take a regression course. No. You don't have to take
the regression course, but if you're not familiar with coordinate,
a center coordinate descent, then you can refer to that course,
and the videos in that course, to get a more detailed explanation
of these types of algorithms. But the idea here in particular
is that we're iterating between minimizing our z variables,
given our mews. So minimizing an objective over our cluster indicators,
given the cluster centers. And then we're looking at a minimization
to find our cluster centers. Given are assigned cluster indicators. Okay, so now let's get back to
this idea of converges of k-means. So first, does this algorithm converge and
if it does, what does it converge to? Well, the first thing to note is that
the k-means objective landscape, is this really complex non-complex thing. So because of that, we can rule out
converging to a global optimum or, at least, being guaranteed, obviously,
to converge to a global optimum. But a question now is do we converge
at least to a local optimum? And because we can cast k-means
as a core net descent algorithm, then we know that we are indeed
converging to a local optimum. But in a lot of problems, like I said, there's a really complicated
landscape to this k-means objective. So there are lots and
lots of local modes and the quality of the solutions between these
local modes can vary quite dramatically. So let's look at an example of this. Here's a data set,
the black points are data points. And what we're showing by these crosses, these colored crosses
are our initialized centers. So here is one initialization
of our k-means algorithm. And then what we're showing in the other
plot with the colored circles, are the labels of the clusters,
after convergence of this algorithm. And convergents of this algorithm, one way to assess that, is just
when our assignments stop changing. And what we see is that we've
taken this little group of observations in the bottom
left hand corner. And we've divided those into two clusters
and then we have this big huge cluster, this blue cluster,
capturing everything else in the data set. But if we initialize our algorithm
with different cluster centers, then we've converge to
a completely different solution. And this one might look
a little bit more reasonable, depending on what the structure
of the data might be. Where we end up with three clusters, each
of which forms a bit tighter of a group, but lets look at another initialization, where here, the groupings actually
look similar, so if we flip back and forth between these two initializations
the groupings look similar. But the cluster labels that we associated
with each of these have swapped around. The pink clusters become the blue and
the blue has become the pink. Well there's nothing specific
to any of our cluster labeled. Cluster one, two or three,
over different initializations, you know what observation gets assigned to cluster
one, or cluster two or cluster three. Doesn't matter what actually is
significant are the groups of observations that are grouped together. So what matters is observation xi and
xj assigned to the same group, whether it's labeled group one,
group two, or group three. Okay, but the other thing to note
here are these observations here, highlighted with this orange circle where
there's really a lot of uncertainty whether they should be in the blue
cluster or this pink cluster. And if you look back
at our other solution. And we're going to flip back and
forth between these. We see that the assignment of
those observations has changed. There's no longer consistency in which
grouping those observations appear. In one case here they are appearing in
the second cluster, the middle cluster, and in the other case they are appearing
in that top right hand side cluster. And this notion of uncertainty in our
clustering is really important and it's something we're going to
come back to in the next module. But the point that we want to emphasize
here is that k-means is very sensitive to initialization and you can actually get
very crazy solutions, even crazier than what we've shown in these few examples
just by converging to a local mode. [MUSIC]