[MUSIC]. 
So let's talk about the k-means 
clustering algorithm. 
This algorithm has some weaknesses, but 
it's very, very, very popular. 
In part because it's so simple to 
understand. 
So it's a really good one to be very 
familiar with. 
So the k in k-means refers to the number 
of clusters you're looking for. 
Which is the first and perhaps most 
prominent weakness, is that you have to 
know this upfront. 
Okay, so imagine you had data scattered 
in two dimensions. 
Two dimensional data scattered as in the 
slide, and you're trying to find two 
clusters. 
The way you begin is take the centroid of 
each cluster and drop it into this space 
randomly. 
As an in, initial guess as to where that, 
where that cluster would be centered. 
Okay, so maybe we'd say, [SOUND] here and 
here. 
Okay, and then the algorithm proceeds as 
follows, for each point, in the data set, 
figure out which of these two centroids 
it's closer to. 
This is closer this one. 
This one, is about, about half way, but 
probably this one. 
An this one's about half, but we'll say 
it's over here. 
And then, so this is our initial guess of 
the clustering. 
We think that all these points belong to 
this cluster, and all these points belong 
to this cluster. 
So now you take the average of all the 
positions in that cluster to compute a 
new centroid value and then move the 
centroid there. 
So for example, here, this one will shift 
this way, and this one will shift sort of 
this way. 
So in the second iteration, our points, 
our two centroids might look, like this. 
And then we just repeat the process. 
So for every data point, figure out which 
centroid it's closer to, hm, about half 
way, but why don't we put it there. 
And this is our, guess at time equals 
two, for the clusters. 
And now once again av, average all the 
positions within that cluster to find the 
new centroid. 
And so here, these two points will pull a 
little in that direction but most of the, 
most of the points are this way, so it'll 
probably shift that way a little bit. 
And similarly with this one, it'll shift 
this way. 
And so at time 3, we have a centroid 
there and we have this centroid here. 
And now the close, once again assign the 
points to the closest centroid and 
recompute the, the new centroid values. 
So, this one will finally shift into the 
middle, here. 
This one will finally shift, perhaps, a 
little bit this way. 
And then, in time equals 4, we can repeat 
once more. 
And find that the centroids in this case 
don't move that much on the next 
iteration. 
And so once all the movements of all the 
centroids is below a certain threshold. 
They haven't moved much things don't 
change much. 
Things have settled down, we stop the 
algorithm and that's our, that's our 
clustering. 
And so in this case all of these points 
will be assigned to this cluster, and all 
of these points will be assigned to this 
cluster. 
So you can paralyze this algorithm by 
splitting the data items across multiple 
machines. 
And one of the key ideas here is that the 
number of centroids is pretty small, or 
at least small enough to fit in memory, 
right? 
It's not you're not just really looking 
for billions of clusters. 
And so you can broadcast those to every 
Map task in same MapReduced set up. 
So, in the Map phase, the mappers look at 
these data points and they have access to 
all the centroids. 
And they can figure out which ones each, 
which one each data point is closest to 
and then send that to the reduced phase. 
according to the cluster that it was 
assigned to, okay? 
And so all that can happen in parallel. 
And then on the reduce side there was 1 
reduce task per cluster, and it can 
computer the new centroid value. 
And so there's a bit of a weakness here, 
because 1 reduced task could have a lot 
of work to do, because it might have most 
of the data points. 
And that can be a problem but in 
principle things are balanced. 
You might get a pretty good parellel 
speed up. 
And the other weakness with this 
MapReduced implementation is that there 
is no direct support for this iterative 
nature of k-means. 
We have to repeat this over and over 
again. 
So, you'd have to have some sort of 
external driver program that will keep 
kicking off MapReduce jobs one at a time. 
And we'll talk more about this in the 
final week of lectures. 
So summarizing the weaknesses of k-means, 
first of all you have to know the number 
of clusters up front. 
You have a fair amount of sensitivity to 
the initial starting conditions in that 
there's no unique solution. 
To be on the starting condition you may 
get a different answer. 
And there's also some sensitivity to the 
stopping threshold. 
There's, as is always the case, there's 
been a lot of work on, repairing these 
various problems. 
But when someone just says k-means 
unqualified, they're typically talking 
about the algorithm we just described, 
which is sensitive to these issues.