1
00:00:05,177 --> 00:00:06,399
[MUSIC]. 
So let's talk about the k-means 

2
00:00:06,399 --> 00:00:09,870
clustering algorithm. 
This algorithm has some weaknesses, but 

3
00:00:09,870 --> 00:00:14,310
it's very, very, very popular. 
In part because it's so simple to 

4
00:00:14,310 --> 00:00:16,300
understand. 
So it's a really good one to be very 

5
00:00:16,300 --> 00:00:19,170
familiar with. 
So the k in k-means refers to the number 

6
00:00:19,170 --> 00:00:22,260
of clusters you're looking for. 
Which is the first and perhaps most 

7
00:00:22,260 --> 00:00:24,485
prominent weakness, is that you have to 
know this upfront. 

8
00:00:24,485 --> 00:00:29,140
Okay, so imagine you had data scattered 
in two dimensions. 

9
00:00:29,140 --> 00:00:34,529
Two dimensional data scattered as in the 
slide, and you're trying to find two 

10
00:00:34,529 --> 00:00:38,600
clusters. 
The way you begin is take the centroid of 

11
00:00:38,600 --> 00:00:42,180
each cluster and drop it into this space 
randomly. 

12
00:00:42,180 --> 00:00:47,305
As an in, initial guess as to where that, 
where that cluster would be centered. 

13
00:00:47,305 --> 00:00:54,558
Okay, so maybe we'd say, [SOUND] here and 
here. 

14
00:00:54,558 --> 00:01:01,130
Okay, and then the algorithm proceeds as 
follows, for each point, in the data set, 

15
00:01:01,130 --> 00:01:03,532
figure out which of these two centroids 
it's closer to. 

16
00:01:03,532 --> 00:01:08,480
This is closer this one. 
This one, is about, about half way, but 

17
00:01:08,480 --> 00:01:22,130
probably this one. 
An this one's about half, but we'll say 

18
00:01:22,130 --> 00:01:30,660
it's over here. 
And then, so this is our initial guess of 

19
00:01:30,660 --> 00:01:32,750
the clustering. 
We think that all these points belong to 

20
00:01:32,750 --> 00:01:34,860
this cluster, and all these points belong 
to this cluster. 

21
00:01:36,680 --> 00:01:42,020
So now you take the average of all the 
positions in that cluster to compute a 

22
00:01:42,020 --> 00:01:45,300
new centroid value and then move the 
centroid there. 

23
00:01:45,300 --> 00:01:51,740
So for example, here, this one will shift 
this way, and this one will shift sort of 

24
00:01:51,740 --> 00:02:06,170
this way. 
So in the second iteration, our points, 

25
00:02:06,170 --> 00:02:11,030
our two centroids might look, like this. 
And then we just repeat the process. 

26
00:02:11,030 --> 00:02:22,748
So for every data point, figure out which 
centroid it's closer to, hm, about half 

27
00:02:22,748 --> 00:02:33,920
way, but why don't we put it there. 
And this is our, guess at time equals 

28
00:02:33,920 --> 00:02:40,400
two, for the clusters. 
And now once again av, average all the 

29
00:02:40,400 --> 00:02:43,110
positions within that cluster to find the 
new centroid. 

30
00:02:43,110 --> 00:02:46,728
And so here, these two points will pull a 
little in that direction but most of the, 

31
00:02:46,728 --> 00:02:51,930
most of the points are this way, so it'll 
probably shift that way a little bit. 

32
00:02:51,930 --> 00:02:55,840
And similarly with this one, it'll shift 
this way. 

33
00:02:55,840 --> 00:03:11,154
And so at time 3, we have a centroid 
there and we have this centroid here. 

34
00:03:11,154 --> 00:03:20,268
And now the close, once again assign the 
points to the closest centroid and 

35
00:03:20,268 --> 00:03:30,246
recompute the, the new centroid values. 
So, this one will finally shift into the 

36
00:03:30,246 --> 00:03:32,793
middle, here. 
This one will finally shift, perhaps, a 

37
00:03:32,793 --> 00:03:40,712
little bit this way. 
And then, in time equals 4, we can repeat 

38
00:03:40,712 --> 00:03:51,690
once more. 
And find that the centroids in this case 

39
00:03:51,690 --> 00:03:55,140
don't move that much on the next 
iteration. 

40
00:03:55,140 --> 00:03:58,720
And so once all the movements of all the 
centroids is below a certain threshold. 

41
00:03:58,720 --> 00:04:00,380
They haven't moved much things don't 
change much. 

42
00:04:00,380 --> 00:04:05,620
Things have settled down, we stop the 
algorithm and that's our, that's our 

43
00:04:05,620 --> 00:04:08,300
clustering. 
And so in this case all of these points 

44
00:04:08,300 --> 00:04:12,420
will be assigned to this cluster, and all 
of these points will be assigned to this 

45
00:04:12,420 --> 00:04:17,060
cluster. 
So you can paralyze this algorithm by 

46
00:04:17,060 --> 00:04:20,130
splitting the data items across multiple 
machines. 

47
00:04:20,130 --> 00:04:23,350
And one of the key ideas here is that the 
number of centroids is pretty small, or 

48
00:04:23,350 --> 00:04:24,920
at least small enough to fit in memory, 
right? 

49
00:04:24,920 --> 00:04:27,830
It's not you're not just really looking 
for billions of clusters. 

50
00:04:28,960 --> 00:04:34,030
And so you can broadcast those to every 
Map task in same MapReduced set up. 

51
00:04:34,030 --> 00:04:37,910
So, in the Map phase, the mappers look at 
these data points and they have access to 

52
00:04:37,910 --> 00:04:40,078
all the centroids. 
And they can figure out which ones each, 

53
00:04:40,078 --> 00:04:45,660
which one each data point is closest to 
and then send that to the reduced phase. 

54
00:04:45,660 --> 00:04:49,200
according to the cluster that it was 
assigned to, okay? 

55
00:04:49,200 --> 00:04:52,350
And so all that can happen in parallel. 
And then on the reduce side there was 1 

56
00:04:52,350 --> 00:04:56,712
reduce task per cluster, and it can 
computer the new centroid value. 

57
00:04:56,712 --> 00:05:02,440
And so there's a bit of a weakness here, 
because 1 reduced task could have a lot 

58
00:05:02,440 --> 00:05:05,200
of work to do, because it might have most 
of the data points. 

59
00:05:05,200 --> 00:05:08,910
And that can be a problem but in 
principle things are balanced. 

60
00:05:08,910 --> 00:05:11,257
You might get a pretty good parellel 
speed up. 

61
00:05:11,257 --> 00:05:15,030
And the other weakness with this 
MapReduced implementation is that there 

62
00:05:15,030 --> 00:05:17,630
is no direct support for this iterative 
nature of k-means. 

63
00:05:17,630 --> 00:05:19,150
We have to repeat this over and over 
again. 

64
00:05:19,150 --> 00:05:22,510
So, you'd have to have some sort of 
external driver program that will keep 

65
00:05:22,510 --> 00:05:26,770
kicking off MapReduce jobs one at a time. 
And we'll talk more about this in the 

66
00:05:26,770 --> 00:05:30,510
final week of lectures. 
So summarizing the weaknesses of k-means, 

67
00:05:30,510 --> 00:05:33,350
first of all you have to know the number 
of clusters up front. 

68
00:05:33,350 --> 00:05:37,550
You have a fair amount of sensitivity to 
the initial starting conditions in that 

69
00:05:37,550 --> 00:05:39,710
there's no unique solution. 
To be on the starting condition you may 

70
00:05:39,710 --> 00:05:42,429
get a different answer. 
And there's also some sensitivity to the 

71
00:05:42,429 --> 00:05:46,520
stopping threshold. 
There's, as is always the case, there's 

72
00:05:46,520 --> 00:05:49,280
been a lot of work on, repairing these 
various problems. 

73
00:05:49,280 --> 00:05:53,250
But when someone just says k-means 
unqualified, they're typically talking 

74
00:05:53,250 --> 00:05:56,650
about the algorithm we just described, 
which is sensitive to these issues.