Hi, and welcome to this third and
final talk about clustering.
In the first video we have seen
the clustering in general.
In the second, we talked about Today
we are going to see, in more details,
the self organizing maps, a powerful tool
to both cluster and visualize your data.
We go through how it works, and
we see the different kind of analysis
that we can perform with this model.
Self organizing the maps are also
called the colon maps from the name of
the Finnish professor, Teuvo Kohonen.
It can be considered
the father of this model.
In few words, some learn to recognize
a group of similar input vectors in such
a way that neurons physically near each
other respond to similar input vectors.
Basically they map all the points in
a high dimensional input space from a high
dimensional input space to a 2 or
3D target space preserving,
as much as possible, the distance and
proximity relationship.
Self organizing maps are widely used in
data analysis especially for clustering
a data visualization model estimation,
and probability density estimation.
Now, let's see the topology.
A SOM consists of neurons
located on a regular grid and
this grid usually have a rectangular or
a hexagonal structures.
Neurons are connected to adjacent
neurons by a neighbored relation.
And, for example, in the, in, in these two
figures are shown the neighbors of
the units marked with a black dot.
And as you can see, the structure
also change the neighbor set.
For example, with the hexagonal grid, each
neurons has, six first-level neighbors.
While, in this case,
with the rectangular grid,
they have eight neighbors of first level.
And when the neighbor is reduced to zero,
the SOM acts like [INAUDIBLE].
Now, let's see the prototypes,
because each cell can also,
each cell is represented by a prototype.
That is also called the weight vector, and
it is d-dimensional, where d is
the dimension of the input space.
So basically each map unit can
be thought as having two sets of
coordinates in the input space,
the prototype vectors.
In the output space:
the position on the map.
Now, let's briefly see
how the training is done.
It resemble vector quantization
algorithms like [INAUDIBLE].
And in each training step, one sample
each from the input data set is chosen.
Then the distances between x and
all the other units are computed.
The neuron closest to
the input vector is called,
is said to, to,
to be its best matching unit or BMU.
Then, after finding the best matching
unit, the weight vectors are updated so
that the best matching unit is moved
closer to the input in the vector space,
as shown in this figure,
where you can see that the BMU and
also its topological neighbors are all
moved to answer the sample vector x.
In, with this model
the clustering is performing,
is performed by having several units
competing for the current object.
Actually it employs both the competitive
and cooperative learning.
It's competitive because
the prototype vector most similar to
the input vector is modified,
the best matching unit.
And cooperative because not only
the best matching unit is modified but
those sites topological neighbors.
The fifth figure show an example
of how the map can learn the data.
On the left there is an initial
configuration with the data vector in red,
and they are completely separated
from the map that is in a,
in a, on the upper right corner.
And after few iteration
on the right you can
see how the maps start actually
covering the input space.
So this is the SOM update
rules that uses a function
h that is called the neighbor function and
find the kernel around the winner unit.
Another important parameter is alpha
that corresponds to the learning rate.
H is non-increasing function of time and
double the distance of unit
i from the linear unit c.
And the training officially
performed in two phases.
First we tune them up approximately to
the same space as the input data and
then we fine tune it.
Now in this slide, there is a list
of parameters that have to be
tweaked when you want to
use self-organizing maps.
For example, we need to choose
the map size and its topology.
As a rule of thumb,
if n is the number of samples,
we can choose a number of units equal
to five by the square root of n.
Prototypes can also be
initialized in different way.
For example, randomly or
drawing them from the input data.
Like basically, like we have also
seen with the [INAUDIBLE] and
the training can be sequential
where some pose are presented to
the map one at a time or can be batched.
So the data set is presented as a whole
and then we need to fix learning rate,
we need to choose the name
of the function and radiant.
Now let's see what data mining
questions we can ask for
using the self organizing maps.
So the most most important are how to find
clusters, which components are the most
discriminating, how do the parameters
relate to the cluster?
And the with some,
we also have several ways to
visually answer these questions,
and we'll see them in a moment.
So, first,
lets talk briefly about labeling that we
have already discussed
in the previous videos.
If we know the place value for some subset
of data, we can use it as a gold standard
and and and for example we can assign
each cell to the class most represented.
Now and important tool in data analysis
using self organizing maps are the so
called hit histograms that show the
distribution of the data set on the map.
They are formed by taking a data set,
finding the best match unit of
each data sample, and
increasing a counter in a map unit each
time that unit is, is the best matching
unit of one of the input samples.
It's also very useful and
easy way to visualize our how our
goals stand on the spread of the map.
For example using colors
to encode the glasses.
In this example there
are three classes and
you can see that the red one is
actually very well separated.
But yea there's two,
they tend to stay to some overlap.
This is actually a distribution of
the Iris data set created by Fisher.
When one class is actually linearly
separable from the other two
is of often used as a, as a benchmark.
Now, to show the class structure,
we can use unify the matrix or
U-matrix that shows distance
between neighboring units.
This visualization has much more
units than the real map as you
can easily see because also the distances
between map units are shown.
Now, with self-organizing maps,
we can also visualize the map
parameter by parameter.
So, this visualization is
called component planes, and
with the component planes, we can show
the values of the prototype vector for
each parameter, and we can use them for
correlation hunting.
For example, we have the U-matrix and
then the four component place planes and
from, from this data
set we can easily see that the two
in the bottom are highly correlated.
And we can also infer with some of
the properties regarding a Iris data
set, in this case.
[SOUND] Right, now,
with this method, we can also
answer another important
question in data mining.
Which parameters are the most important
in discriminating between classes?
Basically, we can derive the relative
weight of each variable in each math unit.
In this example, we can see that
the second parameter in green,
the histogram in green, is very prominent
in the upper part of the map and
so as to, to discriminate
between the classes really well.
Now, we have seen how to
locate a sample on the map,
but how accurate is this localization?
Of course, all the samples are located
somewhere on the map, but, likely,
we can compute two types of errors that
tell us if this mapping is good or not.
Besides the best mention unit we can
also compute the second best matching
unit and the worst matching unit.
We can expect that the stable
clustering would have the first and
second best unit close to each other,
and far from the worst matching unit.
And this can be quantified by using
the average quantization error and
the topographical error.
The average quantization error
measures the distance from
each data vector and
its best matching unit.
Like in the figure on the, on the right,
the, the, the, the straight
line that is in the quantization error of
that data point, and of those data points.
And and you can see that the,
the sample on the top is a very,
very high quantization,
quantization error, and so
its localization is not good.
Then there is the topographic
error measure,
that the topographic error that measure
the percentage of data vectors or, for
which the best matching unit and second
best matching unit are not adjacent units.
So this error gives an overall idea
of the goodness of the whole map.
Now, another data mapping
technique that you can apply using
the self organizing map,
uses the trajectories.
In few words, if our examples are ordered,
for example forming a timed series,
their response on the map can be
tracked at different times and
so we can visually see how a data
point goes from a class to
another where some parameters change or
evolve.
Now finally in this video we have seen
the self organizing maps and how they can
be used to ask some important data mining
questions, like how to class your data.
Which components are the most important?
How to locate the new objects?
And then we have also describe
the two types of errors that will
pass understand the quality of the class
setting, and of the single localization.
And we have briefly talked about
trajectories and now self-organizing maps
can use to, for a time series and
to see how an object evolve.
And this conclude the clustering series.
Thank you for watching.