1
00:00:00,000 --> 00:00:04,660
[MUSIC]

2
00:00:04,660 --> 00:00:06,722
Having overviewed divisive clustering,

3
00:00:06,722 --> 00:00:10,050
let's now spend some time digging
into agglomerative clustering.

4
00:00:11,070 --> 00:00:14,810
And to do this, we're going to look at one
specific example called single linkage,

5
00:00:14,810 --> 00:00:18,620
which is a really common application
of agglomerative clustering.

6
00:00:18,620 --> 00:00:23,220
And here, we start with every data point
in its own cluster, and that's actually

7
00:00:23,220 --> 00:00:26,830
common to all agglomerative clustering
approaches, not just single linkage.

8
00:00:26,830 --> 00:00:29,884
But then we have to think about how
we are going to merge clusters?

9
00:00:29,884 --> 00:00:34,428
And the way we're going to do this is
we're going to look at every single pair

10
00:00:34,428 --> 00:00:36,984
of clusters and for each pair of clusters,

11
00:00:36,984 --> 00:00:40,770
we're going to look at the distance
between these clusters.

12
00:00:40,770 --> 00:00:44,690
So we have to somehow define
a distance between clusters and

13
00:00:44,690 --> 00:00:47,670
the way we do this is through
two different components.

14
00:00:47,670 --> 00:00:49,060
One is the distance function,

15
00:00:49,060 --> 00:00:54,740
and that's going to define a distance
between pairs of individual points.

16
00:00:54,740 --> 00:00:58,530
And the other is through something
called the linkage function, and

17
00:00:58,530 --> 00:01:03,360
that's going to define the distance
between clusters resulting in these

18
00:01:03,360 --> 00:01:06,130
individual pair wise
distances between points.

19
00:01:06,130 --> 00:01:10,300
So in particular for single linkage,
the way we specify this,

20
00:01:10,300 --> 00:01:15,020
you can choose basically any
distance metric that you want, but

21
00:01:15,020 --> 00:01:19,750
the linkage function is going to say,
let's take two clusters, cluster one and

22
00:01:19,750 --> 00:01:22,880
cluster two, just generically
choose those two clusters.

23
00:01:22,880 --> 00:01:26,730
And then look at all the points
within those clusters and

24
00:01:26,730 --> 00:01:30,730
look at the minimum distance
between all these points.

25
00:01:30,730 --> 00:01:34,720
So find the two points that are closest,
one in one cluster,

26
00:01:34,720 --> 00:01:36,820
one in the other cluster, and

27
00:01:36,820 --> 00:01:42,590
define that minimum distance as
the distance between those two clusters.

28
00:01:42,590 --> 00:01:44,440
And so that's the form for single linkage.

29
00:01:44,440 --> 00:01:49,250
And then the way that we choose
to merge any two clusters

30
00:01:49,250 --> 00:01:53,580
is based on the two clusters
that have the minimum distance.

31
00:01:53,580 --> 00:01:56,233
And then we recurse this process where,
again,

32
00:01:56,233 --> 00:02:00,502
we keep taking each one of our clusters,
which now has multiple points in it and

33
00:02:00,502 --> 00:02:04,578
looking at any other cluster, and
looking at the minimum distance between

34
00:02:04,578 --> 00:02:08,395
the points in this orange cluster and
any one of these other clusters,

35
00:02:08,395 --> 00:02:12,602
and then we recurse this process of
computing the distance between every pair

36
00:02:12,602 --> 00:02:16,007
of clusters at existence at that
iteration of the algorithm.

37
00:02:16,007 --> 00:02:20,521
Where remember that distance is
the minimum distance of any set of

38
00:02:20,521 --> 00:02:22,970
points in the two clusters.

39
00:02:22,970 --> 00:02:27,230
And so we keep going and going and
going until at some point

40
00:02:27,230 --> 00:02:31,240
all of the data points are going to
fall into one cluster.

41
00:02:31,240 --> 00:02:34,600
And so what we see is,
just like in divisive clustering,

42
00:02:34,600 --> 00:02:37,710
agglomerative clustering
defines clusters of clusters.

43
00:02:37,710 --> 00:02:41,244
So we have clusters defined
at different granularities.

44
00:02:41,244 --> 00:02:45,809
[MUSIC]