1
00:00:00,380 --> 00:00:06,610
Hi, and welcome to this second lecture,
of the series on clustering.

2
00:00:06,610 --> 00:00:12,015
In this video, we'll talk about one
of the most used partitional methods,

3
00:00:12,015 --> 00:00:15,170
k-means, and
we'll go through the algorithm.

4
00:00:15,170 --> 00:00:19,810
We'll see how it works, and how to
choose all the parameters involved in

5
00:00:19,810 --> 00:00:24,640
the clustering, depending what
your problem is, and the shape.

6
00:00:24,640 --> 00:00:25,450
Of your points.

7
00:00:28,060 --> 00:00:31,220
Now, K-Means is an unsupervised
clustering method.

8
00:00:31,220 --> 00:00:36,490
It's a partitioning algorithm, where
we want to assign the data in clusters

9
00:00:36,490 --> 00:00:42,640
defined by the centroids, and the goal is
to minimize the sum of the squared errors.

10
00:00:44,450 --> 00:00:47,160
So let's start with some definitions.

11
00:00:47,160 --> 00:00:52,750
A centroid is the middle of the cluster.

12
00:00:52,750 --> 00:00:57,300
And points are assigned to the cluster
with the nearest centroid.

13
00:00:57,300 --> 00:01:03,580
Medoid are similar to the centroid but
the end they are actual points.

14
00:01:03,580 --> 00:01:08,700
Some times they are preferred to the
centroid, and there is a funny way to say

15
00:01:08,700 --> 00:01:14,320
that a centroid can locate any
item in the middle of a lake.

16
00:01:15,600 --> 00:01:19,440
Now, distances between
clusters can be seen as

17
00:01:19,440 --> 00:01:23,970
the distances between their centroids,
or their medoids as we see in a moment.

18
00:01:25,840 --> 00:01:29,190
Now, an important quantity is
the sum of the squared error,

19
00:01:29,190 --> 00:01:33,390
SSE, and
it's just used to make partitions.

20
00:01:34,430 --> 00:01:40,310
It is the sum of the squared differences
between each observation, and

21
00:01:40,310 --> 00:01:44,890
its cluster's centroid, or
error all the k clusters.

22
00:01:44,890 --> 00:01:49,560
As trivial case, if four cases
within a clusters are identical,

23
00:01:49,560 --> 00:01:51,840
the SSE would be then equal to zero.

24
00:01:53,880 --> 00:01:58,440
Now let's see how it works,
and this is a four steps

25
00:01:58,440 --> 00:02:04,360
schematic representation on why,
on how the K mean algorithms work.

26
00:02:04,360 --> 00:02:09,420
In this example, the data points are shown
in grey in the first figure, and

27
00:02:09,420 --> 00:02:13,830
we want to partition them in
three non empty clusters.

28
00:02:13,830 --> 00:02:17,830
So, the first step is the initialization,
and

29
00:02:17,830 --> 00:02:23,130
so we randomly choose
the three initial means and

30
00:02:23,130 --> 00:02:27,770
they have shown in red, green,
and blue in the first figure.

31
00:02:27,770 --> 00:02:29,170
In the second steps,

32
00:02:29,170 --> 00:02:34,600
clusters are created associating
each object with the nearest mean.

33
00:02:35,680 --> 00:02:43,190
In the third step, the centroid of
each of the clusters is recomp,

34
00:02:43,190 --> 00:02:46,800
is computed again and
becomes the new mean.

35
00:02:46,800 --> 00:02:50,170
Then step two and step three are repeated.

36
00:02:50,170 --> 00:02:52,150
Until convergence.

37
00:02:52,150 --> 00:02:59,250
So in this case the fundamental step is
also referred to as expectation step.

38
00:02:59,250 --> 00:03:03,400
The update step as a maximization step,
making this

39
00:03:03,400 --> 00:03:08,200
algorithm a variant of the generalized
expectation maximization algorithm.

40
00:03:09,960 --> 00:03:13,960
Now note that the partition
in the second step

41
00:03:13,960 --> 00:03:17,650
represent the Voronoi diagram
generated by the means.

42
00:03:17,650 --> 00:03:20,220
Just as a quick reminder to you,

43
00:03:20,220 --> 00:03:26,440
a Voronoi tessellation is a way of
dividing space into a number of regions.

44
00:03:26,440 --> 00:03:30,400
A set of seeds is specified,
and for each seed.

45
00:03:30,400 --> 00:03:33,890
There will be a corresponding
region consisting of

46
00:03:33,890 --> 00:03:37,860
all points closer to that
seed than to any other.

47
00:03:37,860 --> 00:03:40,430
So in the case of k means
the seeds are the means.

48
00:03:41,800 --> 00:03:46,680
Now the 2 figures show two
different Voronoi tessellations for

49
00:03:46,680 --> 00:03:49,610
the same data, but based on different.

50
00:03:49,610 --> 00:03:50,530
Metrics.

51
00:03:50,530 --> 00:03:55,850
Euclidian distance the left and
Monatin distance on the right.

52
00:03:55,850 --> 00:03:59,610
So that's why that choosing
the right distance also is

53
00:03:59,610 --> 00:04:01,870
crucial when apply these methods.

54
00:04:03,890 --> 00:04:09,750
Now results may also vary depending
on the, on the initialization.

55
00:04:09,750 --> 00:04:14,990
And this is an example where you can see,
where you can see that suppose we

56
00:04:14,990 --> 00:04:19,490
have a three original clusters generated
as in the first figure on the top.

57
00:04:20,630 --> 00:04:24,900
And then there are two answer.

58
00:04:26,570 --> 00:04:29,930
Done with different initialization point,
and

59
00:04:29,930 --> 00:04:34,550
they produce an optimal and
a sub-optimal clustering, as you can see.

60
00:04:34,550 --> 00:04:38,650
Of course, a sub-optimal clustering
at some points are misclassified.

61
00:04:38,650 --> 00:04:42,130
Like if you,
if you notice in the optimal clusterings,

62
00:04:42,130 --> 00:04:45,260
there are two blue dots
that actually should be.

63
00:04:45,260 --> 00:04:45,860
Green dots.

64
00:04:45,860 --> 00:04:52,690
But these are just two points in this,
in this sample of over a hundred.

65
00:04:53,780 --> 00:04:57,320
Now k means is a heuristic algorithm, so

66
00:04:57,320 --> 00:05:02,110
there is no guarantee that it will
converge to the global optimum, and

67
00:05:02,110 --> 00:05:06,340
the results may depend on initial
clusters as we have just seen.

68
00:05:06,340 --> 00:05:12,080
But as we did for classification,
we can use early termination criteria to,

69
00:05:12,080 --> 00:05:16,210
to, to stop the con, to stop the,
the algorit, the algorithm.

70
00:05:16,210 --> 00:05:20,118
For example, we can choose
a fixed number of iterations.

71
00:05:20,118 --> 00:05:26,200
This condition limit, limits the run time.

72
00:05:26,200 --> 00:05:30,380
But in some cases can lead
to a poor clustering beca,

73
00:05:30,380 --> 00:05:34,970
because of its inefficient
number of iterations.

74
00:05:34,970 --> 00:05:39,620
Or we can stop when the assignment
of points to clusters does not

75
00:05:39,620 --> 00:05:45,030
change between iterations, except for
cases with the bare local minimum.

76
00:05:45,030 --> 00:05:46,600
This produce.

77
00:05:46,600 --> 00:05:48,470
A good clustering.

78
00:05:48,470 --> 00:05:52,000
But also in this case
runtime can be very long.

79
00:05:52,000 --> 00:05:56,480
Or we can stop when centroids do not
change anymore between iterations.

80
00:06:01,010 --> 00:06:05,370
Now, changing the initialization as
we've already stressed two times,

81
00:06:05,370 --> 00:06:08,090
may change the cluster results.

82
00:06:08,090 --> 00:06:13,250
So, instead of choosing initially
random points as centroids,

83
00:06:13,250 --> 00:06:17,700
there are some model alternatives
that can speed up the computation.

84
00:06:17,700 --> 00:06:20,110
And also lead to better results.

85
00:06:20,110 --> 00:06:25,260
For example, we can place the first
centroid on a data point.

86
00:06:25,260 --> 00:06:30,170
Then the second on a data point that is as
far away as possible from the first and

87
00:06:30,170 --> 00:06:31,520
so on.

88
00:06:31,520 --> 00:06:37,062
A variant to this solution is to
select more than k centroids and

89
00:06:37,062 --> 00:06:40,316
you surely the k must widely spread.

90
00:06:40,316 --> 00:06:44,180
When dealing with categorical
variables remember that we need to

91
00:06:44,180 --> 00:06:45,790
change the means with the modes.

92
00:06:48,670 --> 00:06:52,040
Now, as we have seen in
the previous lectures,

93
00:06:52,040 --> 00:06:55,020
distances are very
important in clustering.

94
00:06:55,020 --> 00:07:01,070
So this, on this slide there is a list
of distances implemented in math lab for

95
00:07:01,070 --> 00:07:02,410
the k-means functions.

96
00:07:03,510 --> 00:07:07,580
So it's the square Euclidian city block or
Manhattan.

97
00:07:07,580 --> 00:07:08,790
Cosine.

98
00:07:08,790 --> 00:07:12,240
Correlation in the hammock
distance that can be used for

99
00:07:12,240 --> 00:07:17,260
binary data, and where the distance
is a percentage of it's, that differ.

100
00:07:17,260 --> 00:07:21,990
And we have similarly talked about
distances in the previous lesson.

101
00:07:25,640 --> 00:07:26,140
Now.

102
00:07:27,220 --> 00:07:32,240
Other choices you need to make when
running a k-means clustering are what to

103
00:07:32,240 --> 00:07:38,540
do with empty sets and
if user not and online updates.

104
00:07:38,540 --> 00:07:42,860
With empty cluster you can
usually treat them as errors, or

105
00:07:42,860 --> 00:07:47,340
you may choose to remove any
cluster that becomes empty.

106
00:07:47,340 --> 00:07:50,250
Or you can choose to create
a new cluster consisting of

107
00:07:50,250 --> 00:07:54,420
the one point farthest from
its centroid if you want to

108
00:07:54,420 --> 00:07:59,620
keep the same number of clusters
during the whole process.

109
00:07:59,620 --> 00:08:03,050
Now the line up date can be
computationally intense for

110
00:08:03,050 --> 00:08:08,320
very large data sets, but guarantees
a solution that is a local minimum.

111
00:08:11,590 --> 00:08:16,860
Now, let's see some some strength and
weakness of K means.

112
00:08:16,860 --> 00:08:19,940
Its a simple algorith, but
can be powerful and for

113
00:08:19,940 --> 00:08:24,260
this it is often used as benchmark or
as a starting point.

114
00:08:24,260 --> 00:08:26,930
It is relatively efficient.

115
00:08:26,930 --> 00:08:30,540
Since the usual, the computational time,

116
00:08:30,540 --> 00:08:36,030
is o of t by k n, where

117
00:08:36,030 --> 00:08:41,910
k is the number of clusters,and the number
of objects, and t the number of iteration.

118
00:08:41,910 --> 00:08:44,620
And usually t is much smaller than n.

119
00:08:45,640 --> 00:08:50,720
On the other hand, it is very
unstable with noisy data, and and

120
00:08:50,720 --> 00:08:53,270
we need to specify K and

121
00:08:53,270 --> 00:08:59,820
also we can have a problem with clusters
of different, of very different sizes.

122
00:08:59,820 --> 00:09:04,630
With the, clusters with the non-globular
shapes, and cluster, and

123
00:09:04,630 --> 00:09:06,990
clusters differing in density.

124
00:09:06,990 --> 00:09:11,780
Now this figure shows the results of
with clusters of different sizes.

125
00:09:13,280 --> 00:09:18,070
And you can tell that, that if, if the,
the clustering is not really that good.

126
00:09:19,180 --> 00:09:22,480
And one solution to this problem could be,

127
00:09:22,480 --> 00:09:26,330
choose a more than three centroids and
then merge the clusters.

128
00:09:28,140 --> 00:09:33,840
These are other two example, where
the standard k-means can perform poorly.

129
00:09:33,840 --> 00:09:39,620
The first one is a,
is a clusters with a different density.

130
00:09:42,020 --> 00:09:45,790
And the second one are non-global
error shapes of clusters.

131
00:09:48,970 --> 00:09:55,800
And that's why we may need the sum pre and
post-processing when applying k means.

132
00:09:55,800 --> 00:09:59,260
The processing involves
the usual processing steps,

133
00:09:59,260 --> 00:10:04,910
feature selection, normalization and we
may also want to try and remove outliers.

134
00:10:05,920 --> 00:10:10,070
In post-processing we may want
to remove small clusters or

135
00:10:10,070 --> 00:10:15,640
split clusters with high SSE or
merge clusters with lower SSE.

136
00:10:19,250 --> 00:10:23,860
Now, let's see a useful measure to
assess the quality of the clustering.

137
00:10:24,980 --> 00:10:30,920
Now the silhouette shows how well
a point is assigned to each cluster, and

138
00:10:30,920 --> 00:10:34,140
the smaller the value
the better is the assignment.

139
00:10:34,140 --> 00:10:38,910
The formula takes into account
the average dissimilarity of

140
00:10:38,910 --> 00:10:43,270
the point with all the other
within its cluster.

141
00:10:43,270 --> 00:10:48,420
And the lowest average dissimilarity
between point and the,

142
00:10:48,420 --> 00:10:52,040
and any other cluster which
the point is not part of.

143
00:10:53,410 --> 00:10:58,490
Now silhouette values range
from minus 1 to plus 1.

144
00:10:58,490 --> 00:11:01,730
And then highs silhouette
value indicates that

145
00:11:01,730 --> 00:11:05,560
the point is well matched
to its own cluster.

146
00:11:05,560 --> 00:11:10,730
And poorly match them to neighboring
clusters and that's what we want.

147
00:11:10,730 --> 00:11:12,740
If most points have a,

148
00:11:12,740 --> 00:11:17,030
a high silhouette, then we can see
that the clustering is appropriate.

149
00:11:17,030 --> 00:11:21,150
If, many points have a low, or
negative silhouette, mind you,

150
00:11:21,150 --> 00:11:25,310
than the clustering solution
may able too many or too few.

151
00:11:25,310 --> 00:11:26,700
Clusters.

152
00:11:26,700 --> 00:11:30,590
So, this criterium can be used
with any distance metric.

153
00:11:32,030 --> 00:11:35,260
And, and as a reminder, for a given point,

154
00:11:35,260 --> 00:11:42,190
the neighboring cluster is
the cluster with the lowest average.

155
00:11:42,190 --> 00:11:45,830
Basically, it's the second
cluster of choice for that point.

156
00:11:49,490 --> 00:11:54,720
Now we have also say,
that determining the number of clusters in

157
00:11:54,720 --> 00:11:59,430
a data set is a frequent problem
in data clustering and it is,

158
00:11:59,430 --> 00:12:03,650
and actually it's a very well
distinct issue from the, from the.

159
00:12:04,830 --> 00:12:08,480
Actual for, from the actual clustering.

160
00:12:08,480 --> 00:12:12,720
So the correct choice of
(K) is often ambiguous.

161
00:12:12,720 --> 00:12:18,860
And can depend for example for, to on
the shape and scale of the distribution.

162
00:12:21,420 --> 00:12:22,630
And in.

163
00:12:24,030 --> 00:12:28,600
Roughly speaking the ultimate
choice of K will balance

164
00:12:28,600 --> 00:12:33,480
between maximum compression of the data,
using a single cluster and

165
00:12:33,480 --> 00:12:37,440
maximum accuracy by assigning each
little point to it's own cluster.

166
00:12:38,650 --> 00:12:43,430
Of course, if we already have
a prior knowledge of number of.

167
00:12:43,430 --> 00:12:47,510
On the number of the clusters
we can just use that.

168
00:12:47,510 --> 00:12:52,350
Even though we have seen that sometimes
it's better to add more centroids and

169
00:12:52,350 --> 00:12:58,150
then merge the clusters, like when
the clusters are of very different sizes.

170
00:13:00,690 --> 00:13:04,810
In this slide are listed some
criteria that can be used to learn k.

171
00:13:04,810 --> 00:13:08,510
We can use the information
criteria approaches

172
00:13:08,510 --> 00:13:12,270
like the Akaike information criteria, or

173
00:13:12,270 --> 00:13:17,230
the Bayesian information criteria or
the Deviance information criteria.

174
00:13:18,380 --> 00:13:22,580
And this, this, we can use those and

175
00:13:22,580 --> 00:13:27,320
it is possible to make a likelihood
function for the class setting model.

176
00:13:27,320 --> 00:13:31,540
That's because these models
are used to do, are used for

177
00:13:31,540 --> 00:13:37,160
constraining the complexity of a range of
models competing to explain the same data.

178
00:13:38,530 --> 00:13:45,120
The Calinski-Harabasz, criteria is based
on the fact that well defined clusters.

179
00:13:45,120 --> 00:13:51,760
Have, a large between cluster variance,
and this mole within cluster variance.

180
00:13:54,550 --> 00:13:59,879
And also the Davis-Bouldin Criterion is
based on a ratio of inter-cluster and

181
00:13:59,879 --> 00:14:02,380
intra-cluster variances.

182
00:14:02,380 --> 00:14:05,650
When applying this index
remember that the optimal

183
00:14:05,650 --> 00:14:10,410
clustering solution is
the smallest Davies-Bouldin index.

184
00:14:11,810 --> 00:14:14,900
Like and
this is an example usually, OK, so

185
00:14:14,900 --> 00:14:21,060
on the left there are, there are,
there is our data set generated.

186
00:14:21,060 --> 00:14:26,330
From three multivariable distributions
with different parameters values.

187
00:14:26,330 --> 00:14:33,200
And the plot on the right shows
the Davies-Bouldin index and

188
00:14:33,200 --> 00:14:38,540
there, there, on the x axis
there is the number of clusters.

189
00:14:38,540 --> 00:14:39,980
And as you can see the,

190
00:14:39,980 --> 00:14:45,070
the minimum is reached when the cluster,
the number of clusters is three.

191
00:14:45,070 --> 00:14:48,640
That's actually the number of
clusters that we want to, to have.

192
00:14:52,300 --> 00:14:58,810
Now K-means is an example of
expectation maximization algorithm.

193
00:14:58,810 --> 00:15:02,830
And lets briefly point out
other alternatives, so for

194
00:15:02,830 --> 00:15:05,900
example, we can use fuzzy c-means.

195
00:15:05,900 --> 00:15:10,770
In fuzzy clustering there
is a fuzzy clustering and

196
00:15:10,770 --> 00:15:15,510
whether every point is a degree
belonging to clusters,

197
00:15:15,510 --> 00:15:18,678
rather than belonging to
completely just one cluster.

198
00:15:18,678 --> 00:15:27,310
Now the K-Medoids or
PAM uses medoids instead of centroids.

199
00:15:27,310 --> 00:15:33,830
And and CLARA also uses medoids and

200
00:15:33,830 --> 00:15:40,740
actually draws multiple samples of the
data set and applies PAM on each sample.

201
00:15:40,740 --> 00:15:44,290
And the output is the best algorithm.

202
00:15:44,290 --> 00:15:51,500
The advantage is it can deal with
the larger data sets than time.

203
00:15:51,500 --> 00:15:54,800
So, finally, in this video,
we will be seeing, in detail,

204
00:15:54,800 --> 00:15:59,950
the K-Means, that is a simple, but
effective, partitioning algorithm, and

205
00:15:59,950 --> 00:16:04,640
we will be seeing how to choose parameters
involved when running an experiment,

206
00:16:04,640 --> 00:16:07,230
like how to initialize the centroids.

207
00:16:07,230 --> 00:16:09,400
What to do with the empty sets?

208
00:16:09,400 --> 00:16:11,640
What distance metric to use?

209
00:16:11,640 --> 00:16:13,900
How to, to choose K.

210
00:16:13,900 --> 00:16:20,980
Then we also very briefly introduce
some alternatives and in the next video.

211
00:16:20,980 --> 00:16:25,170
I'll talk more about a powerful
clustering algorithm that is

212
00:16:25,170 --> 00:16:26,690
the self organizing maps.