The SOM algorithm

The basic idea of SOM is simple yet effective. The SOM defines a mapping from high dimensional input data space onto a regular two-dimensional array of neurons. Every neuron i of the map is associated with an n-dimensional reference vector , where n denotes the dimension of the input vectors. The reference vectors together form a codebook. The neurons of the map are connected to adjacent neurons by a neighbourhood relation, which dictates the topology, or the structure, of the map. The most common topologies in use are rectangular and hexagonal.

Adjacent neurons belong to the neighbourhood Ni of the neuron i. In the basic SOM algorithm, the topology and the number of neurons remain fixed from the beginning. The number of neurons determines the granularity of the mapping, which has an effect on the accuracy and generalization of the SOM.

During the training phase, the SOM forms an elastic net that folds onto the "cloud" formed by input data. The algorithm controls the net so that it strives to approximate the density of the data. The reference vectors in the codebook drift to the areas where the density of the input data is high. Eventually, only few codebook vectors lie in areas where the input data is sparse.

The learning process of the SOM goes as follows:

1. One sample vector x is randomly drawn from the input data set and its similarity (distance) to the codebook vectors is computed by using e.g. the common Euclidean distance measure:
   
   
   
   
2. After the BMU has been found, the codebook vectors are updated. The BMU itself as well as its topological neighbours are moved closer to the input vector in the input space i.e. the input vector attracts them. The magnitude of the attraction is governed by the learning rate. As the learning proceeds and new input vectors are given to the map, the learning rate gradually decreases to zero according to the specified learning rate function type. Along with the learning rate, the neighbourhood radius decreases as well.
   
   The update rule for the reference vector of unit i is the following:
   
   
   
   
3. The steps 1 and 2 together consitute a single training step and they are repeated until the training ends. The number of training steps must be fixed prior to training the SOM because the rate of convergence in the neighbourhood function and the learning rate is calculated accordingly.

After the training is over, the map should be topologically ordered. This means that n topologically close (using some distance measure e.g. Euclidean) input data vectors map to n adjacent map neurons or even to the same single neuron.

Map quality measures

After the SOM has been trained, it is important to know whether it has properly adapted itself to the training data. Because it is obvious that one optimal map for the given input data must exist, several map quality measures have been proposed. Usually, the quality of the SOM is evaluated based on the mapping precision and the topology preservation.

Mapping precision

The mapping precision measure describes how accurately the neurons 'respond' to the given data set. For example, if the reference vector of the BMU calculated for a given testing vector xi is exactly the same xi, the error in precision is then 0. Normally, the number of data vectors exceeds the number of neurons and the precision error is thus always different from 0.

A common measure that calculates the precision of the mapping is the average quantization error over the entire data set:

Topology preservation

The topology preservation measure describes how well the SOM preserves the topology of the studied data set. Unlike the mapping precision measure, it considers the structure of the map. For a strangely twisted map, the topographic error is big even if the mapping precision error is small.

A simple method for calculating the topographic error:

where is 1 if the first and second BMUs of are not next to each other. Otherwise is 0.

Visualizing the SOM

The SOM is easy to visualize and over the years, several visualization techniques have been devised. Due to the inherently intricate nature of the SOM, however, not one of the visualization methods discovered so far, has proven to be superior to others. At times, several different visualizations of the same SOM are needed to fully see the state of the map. From this, in can be concluded that every existing visualization method has its merits and demerits. The rest of this section provides an overview to three of them, two of which visualize the reference vectors while the remaining one visualizes the data histograms.

Visualizing the reference vectors

The Sammon mapping represents the SOM in much the same way as Figure 6 does. The idea is that the originally high-dimensional reference vector space is compressed into two dimensions, making the visualization of the data possible. The Sammon mapping tries to find an optimum non-linear projection for the high-dimensional data so that the resulting vectors projected onto a two-dimensional surface would still retain the same relative mutual Euclidean distances as they did in the higher dimensionality.

Unified distance matrix, or u-matrix, is perhaps the most popular method of displaying SOMs. It represents the map as a regular grid of neurons as illustrated in Figure 9. The size and topology of the map can readily be observed from the picture where each element represents a neuron. First, when generating a u-matrix, a distance matrix between the reference vectors of adjacent neurons of two-dimensional map is formed. Then, some representation for the matrix is selected, e.g. a gray-level image. The colors in the figure have been selected so that the lighter the color between two neurons is, the smaller is the relative distance between them.

Figure 6: The u-matrix visualization of the SOM. The map size is 12 x 8 neurons and the topology is hexagonal. The map has also been labelled.

Visualizing the data histograms

The purpose of a data histogram is to show how input data vectors are clustered by the SOM. The data histogram visualization shows how many vectors belong to a cluster defined by each neuron. The histogram can be generated by using a trained SOM and a data set. The BMU is searched for each data vector, after which a hit counter associated with the BMU is increased by one. There are several possible ways of visualizing the resulting histograms, one of which is shown in Figure 7.

Figure 7: A 3D data histogram visualization. The map size is 12 x 8 neurons and the topology is hexagonal.

Hierarchical SOMs

The input of one SOM can be taken from the output of another. The input can also be formed of several output vectors from many SOMs. This kind of structure is referred to as a hierarchical SOM. The topmost SOM in the structure (see Figure 8) clusters the outputs and provides a means of monitoring the operations of the underlying SOMs. As the SOM hierarchy is traversed upwards, the information becomes more and more abstract.

Figure 8: Hierarchical SOM with the BMUs indicated. The topmost SOM takes input from the outputs of the three lower level SOMs.