1
00:00:00,690 --> 00:00:01,450
Hello everyone.

2
00:00:01,450 --> 00:00:03,190
Welcome back to Mining
of Massive Datasets.

3
00:00:04,420 --> 00:00:08,360
In this lecture, we're going to cover
a very important topic, clustering.

4
00:00:08,360 --> 00:00:11,650
We're going to kick off our discussion of
clustering by looking at some applications

5
00:00:11,650 --> 00:00:15,020
of clustering that tell you why we
need clustering in the first place.

6
00:00:15,020 --> 00:00:18,020
Then we're going to look at
the overview of the most common methods

7
00:00:18,020 --> 00:00:18,670
used for clustering.

8
00:00:22,730 --> 00:00:25,530
The basic problem of
clustering is quite simple.

9
00:00:25,530 --> 00:00:27,290
We have a cloud of data points.

10
00:00:27,290 --> 00:00:29,790
Here you see data points
in two dimensions.

11
00:00:29,790 --> 00:00:32,740
And we'd like to get some understanding of

12
00:00:32,740 --> 00:00:37,180
the structure of the data points beyond
just seeing them in the two dimensions.

13
00:00:37,180 --> 00:00:39,960
For example,
it's intuitively clear by looking at

14
00:00:39,960 --> 00:00:42,600
these points that there
are three groups of points here.

15
00:00:42,600 --> 00:00:46,360
There's a group of points
that group together here.

16
00:00:46,360 --> 00:00:48,420
There's another group here.

17
00:00:48,420 --> 00:00:49,890
And there's a third group here.

18
00:00:49,890 --> 00:00:54,480
And it looks like we have two outliers
that don't fall into any of the groups.

19
00:00:55,670 --> 00:00:59,090
The rule of clustering is
to find groups like this.

20
00:00:59,090 --> 00:01:01,530
Except in much higher dimensional
spaces than two dimensions.

21
00:01:03,370 --> 00:01:08,950
More formally, given a set of points and
a notion of distance between points,

22
00:01:08,950 --> 00:01:13,480
we want to group the points together
into a number of clusters or groups.

23
00:01:13,480 --> 00:01:17,190
And you want to group them together so
that members of a cluster are close or

24
00:01:17,190 --> 00:01:21,330
similar to each other using the notion of
distance that we've defined previously.

25
00:01:21,330 --> 00:01:25,270
And members of different clusters
are far away from each other or

26
00:01:25,270 --> 00:01:26,280
dissimilar from each other.

27
00:01:29,090 --> 00:01:33,610
Usually, the points that we'll be dealing
with will live in high-dimensional space.

28
00:01:33,610 --> 00:01:36,990
A space with thousands or
hundreds of dimensions.

29
00:01:36,990 --> 00:01:40,980
And similarity will be defined
using a distance measure, from,

30
00:01:40,980 --> 00:01:43,190
from among the distance measures
that we have covered earlier,

31
00:01:43,190 --> 00:01:47,210
such as Euclidean, Cosine,
Jaccard or edit distance.

32
00:01:48,510 --> 00:01:53,170
Going back to our example, here we have
points in a two-dimensional space.

33
00:01:53,170 --> 00:01:55,080
And let's say our distance
measure is Euclidean.

34
00:01:56,990 --> 00:02:00,920
Observe that points in the group
that are highlighted are close to

35
00:02:00,920 --> 00:02:02,630
each other by cleanly distance, and

36
00:02:02,630 --> 00:02:06,140
are closer to each other than they
are to points outside this group.

37
00:02:06,140 --> 00:02:07,480
We'll call this group a cluster.

38
00:02:09,000 --> 00:02:13,139
Similarly, we have two more
clusters based on a similar notion.

39
00:02:14,150 --> 00:02:17,780
And finally, we have these two outliers
that are not close to any of the clusters.

40
00:02:22,860 --> 00:02:27,580
Now it, that example looked easy, but
in general, clustering is a hard problem.

41
00:02:27,580 --> 00:02:29,480
For example,
here we have a group of points, and

42
00:02:29,480 --> 00:02:35,050
you can see that, the-the different colors
actually denote, different clusters,.

43
00:02:35,050 --> 00:02:36,480
But the problem you'll notice is that,

44
00:02:36,480 --> 00:02:40,210
unlike the previous example where the
clusters were cleanly separated from each

45
00:02:40,210 --> 00:02:43,180
other, in this case, the clusters
actually overlap with each other.

46
00:02:43,180 --> 00:02:47,960
For example, there are some blue points
that are among the orange points here and

47
00:02:47,960 --> 00:02:49,750
some among the green points here.

48
00:02:49,750 --> 00:02:53,190
And you can notice that the clusters
are kind of smeared over and

49
00:02:53,190 --> 00:02:54,260
mixed into each other.

50
00:02:54,260 --> 00:02:59,160
It's hard to find clear boundaries between
the clusters, as in the previous example.

51
00:02:59,160 --> 00:03:01,940
So these are a kind of real problems
that we are going to tackle when we

52
00:03:01,940 --> 00:03:03,250
deal with clustering in the real world.

53
00:03:06,970 --> 00:03:08,580
So why is clustering hard?

54
00:03:08,580 --> 00:03:10,770
Clustering two dimensions
actually looks quite easy.

55
00:03:11,900 --> 00:03:14,460
Clustering small amounts
of data also looks easy.

56
00:03:14,460 --> 00:03:16,250
And in most cases,
looks are actually not deceiving.

57
00:03:16,250 --> 00:03:17,400
Clustering in two dimensions, or

58
00:03:17,400 --> 00:03:20,330
small amounts of data,
is actually very, very easy.

59
00:03:20,330 --> 00:03:22,860
The clutter starts when you
create a number of dimensions.

60
00:03:25,390 --> 00:03:28,970
Many applications don't involve two,
but 10s or

61
00:03:28,970 --> 00:03:31,680
100s or 1,000s or
even 10s of 1,000s of dimensions.

62
00:03:31,680 --> 00:03:34,415
And high-dimensional spaces
are fundamentally different from

63
00:03:34,415 --> 00:03:35,900
low-dimensional spaces.

64
00:03:35,900 --> 00:03:39,740
The problem is that in high-dimensional
spaces, almost all pairs of

65
00:03:39,740 --> 00:03:43,140
point are at approximately
the same distance from each other.

66
00:03:43,140 --> 00:03:47,230
And so, it's not intuitively
clear how to group them together.

67
00:03:47,230 --> 00:03:50,260
These problems have become a pattern as
we work with high-dimensional spaces.

68
00:03:51,880 --> 00:03:55,550
Let's look at some real applications,
starting with SkyCat.

69
00:03:55,550 --> 00:04:00,750
SkyCat is a catalog of two billion
astronomical objects, and each object is

70
00:04:00,750 --> 00:04:05,720
represented by its radiation signature
in seven dimensions of frequency bands.

71
00:04:05,720 --> 00:04:09,190
The problem is to take these
seven dimensional data points and

72
00:04:09,190 --> 00:04:14,580
cluster them into real world objects
such as galaxies, stars, quasars and

73
00:04:14,580 --> 00:04:17,830
so on which are most similar to each
other than they are to other things.

74
00:04:22,580 --> 00:04:25,307
As a second example let's
look at Clustering CD's.

75
00:04:27,700 --> 00:04:30,950
Now intuitively,
music divides into categories, and

76
00:04:30,950 --> 00:04:36,210
customers prefer a few categories or
genres of music.

77
00:04:36,210 --> 00:04:40,000
But what are categories really, right?

78
00:04:40,000 --> 00:04:44,269
We'd like to represent a CD by
a set of customer who bought it.

79
00:04:45,400 --> 00:04:52,300
And we'd like to say that similar CDs
have similar sets of customers, and

80
00:04:52,300 --> 00:04:56,720
CDs magically group or cluster together
based on the customers they have.

81
00:04:56,720 --> 00:04:59,700
For example,
there might be a group of CDs that are,

82
00:04:59,700 --> 00:05:03,320
you know, that are classical music,
and they have a, a,

83
00:05:03,320 --> 00:05:06,610
a group of customers who
are classical music aficionados.

84
00:05:06,610 --> 00:05:09,650
And there's another group of CDs that
are punk rock that are bought by

85
00:05:09,650 --> 00:05:10,530
a different set of people.

86
00:05:15,400 --> 00:05:17,720
Another example is Clustering Documents.

87
00:05:19,990 --> 00:05:22,960
We'd like to group together
documents on the same topic.

88
00:05:22,960 --> 00:05:24,600
But what's a topic, really?

89
00:05:24,600 --> 00:05:27,460
A topic is just a set of words
that appear together frequently.

90
00:05:29,330 --> 00:05:33,240
Now documents with similar sets of
words may be about the same topic.

91
00:05:33,240 --> 00:05:36,580
Right, so
we want to cluster documents based on

92
00:05:36,580 --> 00:05:38,665
their similarity in the space of words.

93
00:05:38,665 --> 00:05:46,150
A dual problem is to find
topics instead of documents.

94
00:05:46,150 --> 00:05:49,380
A topic is just a group of words
that co-occur in many documents.

95
00:05:49,380 --> 00:05:53,230
So we could instead look at words
in the space of documents and

96
00:05:53,230 --> 00:05:56,860
cluster those rather than clustering
documents in the space of words.

97
00:05:56,860 --> 00:06:00,240
And they do that with find topics,
instead of document clusters.

98
00:06:02,630 --> 00:06:05,340
Let's talk briefly about
distance measures.

99
00:06:05,340 --> 00:06:09,150
We've looked at varied distant measures,
such as Cosine, Jaccard, and Euclidean.

100
00:06:09,150 --> 00:06:13,380
And depending on the way we represent the
objects that we are clustering, one or,

101
00:06:13,380 --> 00:06:16,950
one or the other of these distance
measures may be more appropriate.

102
00:06:16,950 --> 00:06:21,520
For example, let's look at our
examples of documents or music.

103
00:06:21,520 --> 00:06:24,360
And different ways of
representing documents lead to

104
00:06:24,360 --> 00:06:25,449
different distance measures.

105
00:06:26,890 --> 00:06:29,590
We might represent a document
as a set of birds or

106
00:06:29,590 --> 00:06:32,350
a bag of birds that appear in a document.

107
00:06:32,350 --> 00:06:35,270
In this case, the appropriate
difference measure to use is

108
00:06:35,270 --> 00:06:37,530
a Jaccard distance since
we're dealing with sets.

109
00:06:39,030 --> 00:06:43,780
Alternatively, we can think of a document,
as a point in the space of words.

110
00:06:43,780 --> 00:06:45,190
Here there's one dimension for

111
00:06:45,190 --> 00:06:49,630
each word, and
each document is an N dimensional point.

112
00:06:49,630 --> 00:06:55,720
The dimension i is 1 if the word i
appears in the document, and 0 otherwise.

113
00:06:55,720 --> 00:06:59,960
Since we represented documents by points,
the natural distance measure here,

114
00:06:59,960 --> 00:07:02,419
you clearly in distance
between the points in space.

115
00:07:04,930 --> 00:07:08,710
Alternatively, we can think of a document
as a vector in the space of words.

116
00:07:10,050 --> 00:07:14,680
A document is a vector from the origin
to the vector x one through x N,

117
00:07:14,680 --> 00:07:18,509
where x i is one if word i appears
in the document, and zero otherwise.

118
00:07:20,030 --> 00:07:21,630
Think about documented vectors.

119
00:07:21,630 --> 00:07:23,790
The natural distance measured.

120
00:07:23,790 --> 00:07:26,660
If the angle between the vectors or
the cosine distance.

121
00:07:27,770 --> 00:07:33,200
Notice that each different way
of representing the same object.

122
00:07:33,200 --> 00:07:35,940
These naturally to defend
the distance measure and

123
00:07:35,940 --> 00:07:38,710
depending on the application,
a certain representation of

124
00:07:38,710 --> 00:07:41,099
distance measured might make
more sense than another.

125
00:07:43,740 --> 00:07:45,780
Now that we understand distance measures,

126
00:07:45,780 --> 00:07:49,140
here is an overview of the important
methods of clustering.

127
00:07:49,140 --> 00:07:52,310
The two important methods of
clustering are Hierarchical methods and

128
00:07:52,310 --> 00:07:54,050
Point assignment methods.

129
00:07:54,050 --> 00:07:58,230
And within Hierarchical methods,
we can either go bottom up or top down.

130
00:07:58,230 --> 00:07:59,150
Bottom up methods, or

131
00:07:59,150 --> 00:08:04,310
agglomerative methods, start with each
point in, in a cluster by itself.

132
00:08:04,310 --> 00:08:07,360
Now once we have each point
in a cluster by itself,

133
00:08:07,360 --> 00:08:12,860
we repeatedly combine the two nearest
clusters into a single cluster,

134
00:08:12,860 --> 00:08:16,580
and we stop at some point and
we have a set of clusters.

135
00:08:16,580 --> 00:08:20,210
Divisive or top down methods
initially place all the points in

136
00:08:20,210 --> 00:08:24,490
the same cluster and then keep recursively
splitting the clusters until we end up

137
00:08:24,490 --> 00:08:26,520
with the desired number of clusters.

138
00:08:26,520 --> 00:08:28,950
Point assignments methods
work differently.

139
00:08:28,950 --> 00:08:32,130
In Point assignment methods,
you always maintain a set of clusters,

140
00:08:32,130 --> 00:08:34,630
let's say k clusters at any point in time,
and

141
00:08:34,630 --> 00:08:38,400
then you repeatedly assign
a point to its nearest cluster.

142
00:08:39,800 --> 00:08:43,040
And we proceed until each point
is assigned to some cluster.