1
00:00:01,310 --> 00:00:06,770
Hi, and welcome to this third and
final talk about clustering.

2
00:00:06,770 --> 00:00:11,180
In the first video we have seen
the clustering in general.

3
00:00:11,180 --> 00:00:17,110
In the second, we talked about Today
we are going to see, in more details,

4
00:00:17,110 --> 00:00:23,420
the self organizing maps, a powerful tool
to both cluster and visualize your data.

5
00:00:23,420 --> 00:00:25,430
We go through how it works, and

6
00:00:25,430 --> 00:00:29,980
we see the different kind of analysis
that we can perform with this model.

7
00:00:29,980 --> 00:00:34,880
Self organizing the maps are also
called the colon maps from the name of

8
00:00:34,880 --> 00:00:37,610
the Finnish professor, Teuvo Kohonen.

9
00:00:37,610 --> 00:00:40,570
It can be considered
the father of this model.

10
00:00:43,570 --> 00:00:49,840
In few words, some learn to recognize
a group of similar input vectors in such

11
00:00:49,840 --> 00:00:56,000
a way that neurons physically near each
other respond to similar input vectors.

12
00:00:57,130 --> 00:01:02,010
Basically they map all the points in
a high dimensional input space from a high

13
00:01:02,010 --> 00:01:07,590
dimensional input space to a 2 or
3D target space preserving,

14
00:01:07,590 --> 00:01:12,520
as much as possible, the distance and
proximity relationship.

15
00:01:12,520 --> 00:01:17,249
Self organizing maps are widely used in
data analysis especially for clustering

16
00:01:17,249 --> 00:01:22,271
a data visualization model estimation,
and probability density estimation.

17
00:01:26,809 --> 00:01:29,130
Now, let's see the topology.

18
00:01:29,130 --> 00:01:34,780
A SOM consists of neurons
located on a regular grid and

19
00:01:34,780 --> 00:01:39,370
this grid usually have a rectangular or
a hexagonal structures.

20
00:01:40,510 --> 00:01:45,120
Neurons are connected to adjacent
neurons by a neighbored relation.

21
00:01:45,120 --> 00:01:48,178
And, for example, in the, in, in these two

22
00:01:48,178 --> 00:01:52,860
figures are shown the neighbors of
the units marked with a black dot.

23
00:01:52,860 --> 00:01:57,360
And as you can see, the structure
also change the neighbor set.

24
00:01:57,360 --> 00:02:03,661
For example, with the hexagonal grid, each
neurons has, six first-level neighbors.

25
00:02:03,661 --> 00:02:08,005
While, in this case,
with the rectangular grid,

26
00:02:08,005 --> 00:02:12,120
they have eight neighbors of first level.

27
00:02:12,120 --> 00:02:20,610
And when the neighbor is reduced to zero,
the SOM acts like [INAUDIBLE].

28
00:02:20,610 --> 00:02:24,110
Now, let's see the prototypes,
because each cell can also,

29
00:02:24,110 --> 00:02:28,170
each cell is represented by a prototype.

30
00:02:28,170 --> 00:02:30,730
That is also called the weight vector, and

31
00:02:30,730 --> 00:02:36,460
it is d-dimensional, where d is
the dimension of the input space.

32
00:02:39,750 --> 00:02:43,490
So basically each map unit can
be thought as having two sets of

33
00:02:43,490 --> 00:02:47,670
coordinates in the input space,
the prototype vectors.

34
00:02:47,670 --> 00:02:50,360
In the output space:
the position on the map.

35
00:02:53,100 --> 00:02:56,240
Now, let's briefly see
how the training is done.

36
00:02:56,240 --> 00:03:00,378
It resemble vector quantization
algorithms like [INAUDIBLE].

37
00:03:00,378 --> 00:03:07,020
And in each training step, one sample
each from the input data set is chosen.

38
00:03:07,020 --> 00:03:12,790
Then the distances between x and
all the other units are computed.

39
00:03:12,790 --> 00:03:17,770
The neuron closest to
the input vector is called,

40
00:03:17,770 --> 00:03:23,040
is said to, to,
to be its best matching unit or BMU.

41
00:03:23,040 --> 00:03:29,300
Then, after finding the best matching
unit, the weight vectors are updated so

42
00:03:29,300 --> 00:03:35,270
that the best matching unit is moved
closer to the input in the vector space,

43
00:03:35,270 --> 00:03:40,370
as shown in this figure,
where you can see that the BMU and

44
00:03:40,370 --> 00:03:46,600
also its topological neighbors are all
moved to answer the sample vector x.

45
00:03:50,020 --> 00:03:56,540
In, with this model
the clustering is performing,

46
00:03:56,540 --> 00:04:01,720
is performed by having several units
competing for the current object.

47
00:04:01,720 --> 00:04:06,060
Actually it employs both the competitive
and cooperative learning.

48
00:04:06,060 --> 00:04:10,434
It's competitive because
the prototype vector most similar to

49
00:04:10,434 --> 00:04:14,246
the input vector is modified,
the best matching unit.

50
00:04:14,246 --> 00:04:18,860
And cooperative because not only
the best matching unit is modified but

51
00:04:18,860 --> 00:04:20,770
those sites topological neighbors.

52
00:04:22,240 --> 00:04:27,960
The fifth figure show an example
of how the map can learn the data.

53
00:04:27,960 --> 00:04:32,900
On the left there is an initial
configuration with the data vector in red,

54
00:04:32,900 --> 00:04:37,520
and they are completely separated
from the map that is in a,

55
00:04:38,680 --> 00:04:40,610
in a, on the upper right corner.

56
00:04:40,610 --> 00:04:43,660
And after few iteration
on the right you can

57
00:04:43,660 --> 00:04:46,810
see how the maps start actually
covering the input space.

58
00:04:50,510 --> 00:04:55,830
So this is the SOM update
rules that uses a function

59
00:04:55,830 --> 00:05:01,720
h that is called the neighbor function and
find the kernel around the winner unit.

60
00:05:01,720 --> 00:05:06,260
Another important parameter is alpha
that corresponds to the learning rate.

61
00:05:06,260 --> 00:05:09,900
H is non-increasing function of time and

62
00:05:09,900 --> 00:05:14,480
double the distance of unit
i from the linear unit c.

63
00:05:15,570 --> 00:05:19,170
And the training officially
performed in two phases.

64
00:05:19,170 --> 00:05:24,690
First we tune them up approximately to
the same space as the input data and

65
00:05:24,690 --> 00:05:25,710
then we fine tune it.

66
00:05:29,130 --> 00:05:33,770
Now in this slide, there is a list
of parameters that have to be

67
00:05:33,770 --> 00:05:37,380
tweaked when you want to
use self-organizing maps.

68
00:05:37,380 --> 00:05:41,620
For example, we need to choose
the map size and its topology.

69
00:05:41,620 --> 00:05:45,470
As a rule of thumb,
if n is the number of samples,

70
00:05:45,470 --> 00:05:50,670
we can choose a number of units equal
to five by the square root of n.

71
00:05:53,490 --> 00:05:57,570
Prototypes can also be
initialized in different way.

72
00:05:57,570 --> 00:06:01,960
For example, randomly or
drawing them from the input data.

73
00:06:03,210 --> 00:06:07,708
Like basically, like we have also
seen with the [INAUDIBLE] and

74
00:06:07,708 --> 00:06:12,294
the training can be sequential
where some pose are presented to

75
00:06:12,294 --> 00:06:15,670
the map one at a time or can be batched.

76
00:06:15,670 --> 00:06:21,050
So the data set is presented as a whole
and then we need to fix learning rate,

77
00:06:21,050 --> 00:06:23,635
we need to choose the name
of the function and radiant.

78
00:06:26,690 --> 00:06:30,550
Now let's see what data mining
questions we can ask for

79
00:06:30,550 --> 00:06:32,960
using the self organizing maps.

80
00:06:32,960 --> 00:06:38,240
So the most most important are how to find
clusters, which components are the most

81
00:06:38,240 --> 00:06:42,970
discriminating, how do the parameters
relate to the cluster?

82
00:06:42,970 --> 00:06:47,970
And the with some,
we also have several ways to

83
00:06:47,970 --> 00:06:52,050
visually answer these questions,
and we'll see them in a moment.

84
00:06:55,260 --> 00:06:59,050
So, first,
lets talk briefly about labeling that we

85
00:06:59,050 --> 00:07:01,750
have already discussed
in the previous videos.

86
00:07:01,750 --> 00:07:09,060
If we know the place value for some subset
of data, we can use it as a gold standard

87
00:07:09,060 --> 00:07:15,420
and and and for example we can assign
each cell to the class most represented.

88
00:07:18,780 --> 00:07:23,860
Now and important tool in data analysis
using self organizing maps are the so

89
00:07:23,860 --> 00:07:29,900
called hit histograms that show the
distribution of the data set on the map.

90
00:07:29,900 --> 00:07:35,030
They are formed by taking a data set,
finding the best match unit of

91
00:07:35,030 --> 00:07:40,130
each data sample, and
increasing a counter in a map unit each

92
00:07:40,130 --> 00:07:46,350
time that unit is, is the best matching
unit of one of the input samples.

93
00:07:46,350 --> 00:07:48,430
It's also very useful and

94
00:07:48,430 --> 00:07:54,680
easy way to visualize our how our
goals stand on the spread of the map.

95
00:07:54,680 --> 00:07:58,260
For example using colors
to encode the glasses.

96
00:07:58,260 --> 00:08:01,180
In this example there
are three classes and

97
00:08:01,180 --> 00:08:05,084
you can see that the red one is
actually very well separated.

98
00:08:05,084 --> 00:08:09,671
But yea there's two,
they tend to stay to some overlap.

99
00:08:09,671 --> 00:08:15,830
This is actually a distribution of
the Iris data set created by Fisher.

100
00:08:15,830 --> 00:08:20,843
When one class is actually linearly
separable from the other two

101
00:08:20,843 --> 00:08:23,480
is of often used as a, as a benchmark.

102
00:08:27,470 --> 00:08:32,600
Now, to show the class structure,
we can use unify the matrix or

103
00:08:32,600 --> 00:08:38,130
U-matrix that shows distance
between neighboring units.

104
00:08:38,130 --> 00:08:41,880
This visualization has much more
units than the real map as you

105
00:08:41,880 --> 00:08:46,908
can easily see because also the distances
between map units are shown.

106
00:08:46,908 --> 00:08:51,370
Now, with self-organizing maps,

107
00:08:51,370 --> 00:08:56,820
we can also visualize the map
parameter by parameter.

108
00:08:56,820 --> 00:09:00,620
So, this visualization is
called component planes, and

109
00:09:00,620 --> 00:09:05,390
with the component planes, we can show
the values of the prototype vector for

110
00:09:05,390 --> 00:09:09,420
each parameter, and we can use them for
correlation hunting.

111
00:09:11,820 --> 00:09:15,300
For example, we have the U-matrix and

112
00:09:15,300 --> 00:09:20,210
then the four component place planes and
from, from this data

113
00:09:20,210 --> 00:09:24,980
set we can easily see that the two
in the bottom are highly correlated.

114
00:09:24,980 --> 00:09:29,960
And we can also infer with some of
the properties regarding a Iris data

115
00:09:29,960 --> 00:09:31,085
set, in this case.

116
00:09:31,085 --> 00:09:36,671
[SOUND] Right, now,
with this method, we can also

117
00:09:36,671 --> 00:09:42,533
answer another important
question in data mining.

118
00:09:42,533 --> 00:09:49,000
Which parameters are the most important
in discriminating between classes?

119
00:09:49,000 --> 00:09:54,900
Basically, we can derive the relative
weight of each variable in each math unit.

120
00:09:54,900 --> 00:09:59,950
In this example, we can see that
the second parameter in green,

121
00:09:59,950 --> 00:10:05,630
the histogram in green, is very prominent
in the upper part of the map and

122
00:10:05,630 --> 00:10:10,380
so as to, to discriminate
between the classes really well.

123
00:10:13,160 --> 00:10:16,540
Now, we have seen how to
locate a sample on the map,

124
00:10:16,540 --> 00:10:19,850
but how accurate is this localization?

125
00:10:19,850 --> 00:10:25,030
Of course, all the samples are located
somewhere on the map, but, likely,

126
00:10:25,030 --> 00:10:31,680
we can compute two types of errors that
tell us if this mapping is good or not.

127
00:10:31,680 --> 00:10:35,840
Besides the best mention unit we can

128
00:10:35,840 --> 00:10:41,080
also compute the second best matching
unit and the worst matching unit.

129
00:10:41,080 --> 00:10:45,240
We can expect that the stable
clustering would have the first and

130
00:10:45,240 --> 00:10:51,120
second best unit close to each other,
and far from the worst matching unit.

131
00:10:53,310 --> 00:10:58,441
And this can be quantified by using
the average quantization error and

132
00:10:58,441 --> 00:11:00,372
the topographical error.

133
00:11:00,372 --> 00:11:04,720
The average quantization error
measures the distance from

134
00:11:04,720 --> 00:11:09,770
each data vector and
its best matching unit.

135
00:11:09,770 --> 00:11:15,090
Like in the figure on the, on the right,
the, the, the, the straight

136
00:11:15,090 --> 00:11:20,520
line that is in the quantization error of
that data point, and of those data points.

137
00:11:20,520 --> 00:11:22,410
And and you can see that the,

138
00:11:23,470 --> 00:11:30,660
the sample on the top is a very,
very high quantization,

139
00:11:30,660 --> 00:11:34,580
quantization error, and so
its localization is not good.

140
00:11:37,300 --> 00:11:39,890
Then there is the topographic
error measure,

141
00:11:39,890 --> 00:11:44,960
that the topographic error that measure
the percentage of data vectors or, for

142
00:11:44,960 --> 00:11:52,040
which the best matching unit and second
best matching unit are not adjacent units.

143
00:11:52,040 --> 00:11:55,840
So this error gives an overall idea
of the goodness of the whole map.

144
00:11:58,330 --> 00:12:01,750
Now, another data mapping
technique that you can apply using

145
00:12:01,750 --> 00:12:06,950
the self organizing map,
uses the trajectories.

146
00:12:06,950 --> 00:12:13,155
In few words, if our examples are ordered,
for example forming a timed series,

147
00:12:13,155 --> 00:12:18,390
their response on the map can be
tracked at different times and

148
00:12:18,390 --> 00:12:22,470
so we can visually see how a data
point goes from a class to

149
00:12:22,470 --> 00:12:25,710
another where some parameters change or
evolve.

150
00:12:29,560 --> 00:12:35,800
Now finally in this video we have seen
the self organizing maps and how they can

151
00:12:35,800 --> 00:12:41,490
be used to ask some important data mining
questions, like how to class your data.

152
00:12:41,490 --> 00:12:45,510
Which components are the most important?

153
00:12:45,510 --> 00:12:47,180
How to locate the new objects?

154
00:12:48,820 --> 00:12:52,790
And then we have also describe
the two types of errors that will

155
00:12:52,790 --> 00:12:57,650
pass understand the quality of the class
setting, and of the single localization.

156
00:12:57,650 --> 00:13:04,050
And we have briefly talked about
trajectories and now self-organizing maps

157
00:13:04,050 --> 00:13:10,420
can use to, for a time series and
to see how an object evolve.

158
00:13:10,420 --> 00:13:14,020
And this conclude the clustering series.

159
00:13:14,020 --> 00:13:14,860
Thank you for watching.