Introduction

This manual gives a brief description of Emergent Self-Organizing Maps and visualizations like the U-Matrix. We explain how to use them for data mining using the Databionics ESOM Tools, see also [Ultsch, Moerchen 2005]. The first section briefly introduce ESOM. The following sections give a step by step tour of a typical usage for data mining involving:

1. Preprocessing
2. Training
3. Visualization
4. Data Analysis
5. Clustering
6. Projection
7. Classification

We also provide a German manual that is shorter and not as up to date.

Emergent SOM

For a detailed explanation of SOM, see [Kohonen 1995]. We will give a very brief introduction here.

We assume the training data is a set of points from a high dimensional space, called the data space. A SOM basically consists of a set of prototype vectors in the data space and a topology among these prototypes. The most common topology is a 2-dimensional grid where each prototype (neuron) has four immediate neighbors. The positions on the grid form the map space. Further two distance functions are needed, one for each space. The Euclidean distance is commonly used for the data space and the Cityblock distance for the map space. The process of SOM training adapts the grid of prototype vectors to the given data creating a 2-dimensional projection that preserves the topology of the data space.

A central operation in SOM training is the update of a prototype vector by a vector of the training data. The prototype vector of the neuron is drawn closer to a given vector in the data space. Further, prototypes in the neighborhood of the neuron are also drawn in the same direction but with less emphasis. The emphasis and the size of the neighborhood are reduced during training.

The two most common training algorithms are Online and Batch training. Both search the closest prototype vector for each data point (the bestmatch). In Online training the bestmatch is immediately updates, while in Batch training the bestmatches are first collected for all data points and then the update if performed collectively.

Emergence is the ability of a system to develop high level structures by the cooperation of many elementary processes. In self organizing systems the structures evolve within the system without external influences. Emergence is the appearance of high level phenomena that can not be derived from the elementary processes. Emergent structures offer a more abstract description of a complex system consisting of low level individuums. A popular example of an emergent phenomenon is the so called La Ola wave in a sports stadium. A large number of people perform the simple task of standing up and waving for a short moment. In this way a wave rolling through the crowd is formed. The wave is not visible at the moment of being part of it, only from a distance.

Transferring the principles of self organization into data analysis can be done by letting multivariate data points organize themselves into homogenic groups. A well known tool for this task that incorporates the above mentioned principles is the Self-Organizing Map (SOM). The SOM iteratively adjusts to distance structures in a high dimensional space and gives a low dimensional projection that preserves the topology of the input space as good as possible. Such a map can be used for unsupervised clustering and supervised classification.

The power of self organization that allows the emergence of structure in data is, however, often neglected. We think this is in part due to a misusage of Self-organizing Maps that is widely spread in the scientific literature. The maps used by most authors are usually very small, consisting of somewhere between a few and some tens of neurons.

Also the concept of border less maps (e.g. toroid maps [Ultsch 2003b]) to avoid border effects is rarely used. Using small SOM, is almost identical to a k-Means clustering with k equal to the number of nodes in the map. The topology preservation of the SOM projection is of little use when using small maps. Emergent phenomena involve by definition a large number of individuums, where large means at least a few thousand. This is why we use large SOMs and called them Emergent Self-Organizing Maps (ESOM) [Ultsch 1999] to emphasize the distinction. It has been demonstrated, that using ESOM is a significantly different process from using k-Means [Ultsch 1995].

When using supervised neural nets, e.g. multi layer perceptrons trained with Backpropagation, a common concern is the model size. Too small neural nets have low accuracy, while too large nets are prone to over-fitting. Note, that this is not the case with ESOM. Using larger maps does not really increase the degrees of freedom in the same sense, because the neurons are restricted by the topology preservation of the map. Using large maps should rather be viewed as increasing the resolution of the projection from the data space onto the map.

Preprocessing

A very important step prior to ESOM training is preprocessing of the data. For each feature the empirical probability distribution should be analyzed e.g. with histograms or kernel density estimates. If the distribution is skewed we recommend using non linear transformations (e.g. log) to make is more symmetric. Outliers can be detected e.g. using box plots or statistical tests. These extreme values can be interesting in some applications, but they should be removed prior to SOM training because they will severely distort the grid and can hide the more interesting clustering structure. The correlation among features is another important aspect. If several features are highly correlated, this may introduce unwanted emphasis of this aspect of the data. The Pearson correlation coefficient and scatter plots can be used to detect correlation. Some features can then be discarded. Finally, for meaningful distance calculations, the means and variances of the features should be made comparable. This is commonly done using the z-transformation to have zero mean and unit variance for all inputs and thus provide an equal weighting in distances. For more information see e.g. [Hand et al. 2001].

The complete process of preprocessing is beyond the scope of the Databionic ESOM Tools. But we do provide the possibility to normalize the values by pushing the one of the buttons in the toolbar of the data tab. Z-transform applies column-wise normalization to zero mean and unit variance. Robust ZT does the same but uses robust estimates of mean and variance. Finally, to [0,1] rescales each column to range from zero to one.

Training

After starting up the ESOM Analyzer (with the start menu or the command esomana) you need to load the data in the application with the File->Load *.lrn menu item. The data needs to be in the *.lrn format, basically tab separated values in a text file. The menu item Tools->Training opens up the training dialog. The options are explained here.

Press Start to train the ESOM. The output of the training program will be shown, e.g. the epoch and the current quantization error. You can cancel the process by pressing the Stop button. When the training is finished press the Close button to return to the main window.

Visualization

This section describes how ESOM can be visualized and analyzed using the tools in the View tab at the bottom.

Data Analysis

The data tab displays the loaded data file (*.lrn) and optionally the loaded names (*.names) and classification (*.cls). The data entries, column names, and dataset names can be edited in place. The changes can be saves to *.lrn and *.names files with the menu items in the file menu.

The mouse can be used with the Ctrl and Shift keys to select table entries in the usual manner. The corresponding bestmatches on the map will be highlighted. You can also select bestmatches on the map with the mouse using the selection tool (the rightmost toolbar button automatically activated along with the data tab). The mouse tool can be used to draw a line around a set of bestmatches. Keeping the left mouse button pressed creates a freehand line, several clicks with the left mouse button create a polygon. Pressing the right mouse button finishes the line by connecting the end with the beginning. Using the mouse with the Ctrl pressed can be used to select additional points without discarding the previous selection. Selecting points with the Shift key pressed will remove them from the current selection. The popup menu offers more options for selection. The hide/show button can be used to toggle the display of the selection without discarding it.

The data table popup menu can be used to remove the selected data points. This is useful if you identify high dimensional outliers. On a U-Matrix these will be visible by a large mountain range surrounding a single or a few bestmatches. After outlier removal you should retrain the ESOM with the remaining data. The File->Selection menu items can be used to store the selection in a separate *.lrn file of create a classification with the selection in class 1 and the rest in class 0.

Clustering

The clustering of the ESOM can be performed at two different levels. First, the bestmatches and thus the corresponding data points can be manually grouped into several clusters. Secondly, the neurons can be clustered. This way regions on the map representing a cluster can be identified and used for classification of new data. In neither case all elements need to be labeled.

Projection

The projection of data onto an ESOM means finding the bestmatches for each data point. This task can be performed by loading an ESOM (*.wts) or using newly trained ESOM, loading a new data file (*.lrn) and selecting the menu item Tools->Project. The bestmatches will be calculated, displayed on the map and can be saved using the menu item File->Save (*.bm).

Classification

The class mask created by clustering the neurons of an ESOM can be used for classification. Each bestmatch and thus the accompanying dataset(s) is assigned to the class of the region it resides in. Bestmatches not covered by a class mask are placed in the default class 0. Classification can be performed by loading bestmatches (*.bm) or using the bestmatches of a newly trained ESOM and loading or creating a class mask (*.cls) with the menu item File->Class mask->Load. Selecting the menu item Tools->Classify will label all bestmatches and display the result as colors on the map and in the Classes tab. The classification can be saved using the menu item File->Save (*.cls).

Reference

Training Parameters

input file	The input *.lrn file, set automatically.
output files	The generated output files, set automatically. The *.wts file contains the weights of the trained ESOM, the *.bm lists the positions of the bestmatches, and the *.umx file stores the heights of a U-Matrix.
training algorithm	Online training: The bestmatch for a data vector is searched and the neighborhood on the map is updated immediately. Batch training: The bestmatches for all data vectors are searched, a map update is then performed collectively. If several data vectors share a bestmatch, the update is performed with the mean of the data vectors. Batch training is a little faster than Online but can have negative effects on cluster representation [Noecker et. al 2006]. Slow Batch training: Batch without calculating the mean vector. This is not faster than Online and only useful for demonstration purposes. k-Batch training: Batch version with update after p percent (see below) instead of all data vectors. Faster than Online and good cluster representation [Noecker et. al 2006]. Hybrid-Batch training: Batch training with an intermediate epoch of Online training whenever less than p percent (see below) of all bestmatches are assigned a single data vector.
k for k-Batch as percentage of data set	Percentage of all data vectors that is processed between map updates.
threshold for Hybrid-Batch as percentage of map size	The minimum percentage of data points that is required to be placed on a different bestmatches. Other wise one epoch of Online learning is performed.
number of rows in map	The vertical size of the ESOM grid.	The product of rows and columns, i.e. the number of neurons should be at least 1K neurons. The ratio of rows and columns should be significantly different from unity.
number of columns in map	The vertical size of the ESOM grid.
number of training epochs	The number of iterations over the training data.
search method for bestmatches	standard bm search: Exhaustive search over the whole map. 'quick learning' local search: Local search within current radius + a constant (see below) around the last bestmatch of each data vector [Kinouchi et. al 2003]. variant of 'quick learning': Local search within 2*(current radius + constant). 'much faster learning' local search: Local search around the last bestmatch of each data vector with radius equal to the distance to the second but last bestmatch [Cuadros-Vargas et al. 2003]. variant of 'much faster learning': Local search within 2*(distance of last 2 bestmatches). local search with constant radius: Local search within a fixed radius (see below) around the last bestmatch for each data vector.
radius for local bm search methods	If the 'quick learning' bestmatch search strategies are active this is the constant that is added to the current radius of the learning neighborhood. If the 'local search with constant radius' is active this is the fixed search radius.
weight initialization method	The prototypes of the ESOM can be initialized randomly by Uniform random numbers from the interval [min, max]. Uniform random numbers from the interval [mean-2*std, mean+2*std]. Gaussian random numbers with same mean and std as the corresponding feature. or by sampling the hyper plane spanned by the first two principal components of the data. The latter should only be used with planar grids (see below).
data space distance function	The distance function to use for bestmatch search. The Lp distances are available for p = 1/4,1/3,1/2,1(=Manhattan),2(=Euclid),3,4,inf(=Maximum). Further you can select the Cosine and Correlation distances. All distances are available as a version ignoring missing values (NaN). If you data does not have missing values, the using the plain version will be faster.
start value for radius	The initial value for the radius of the neighborhood around each neuron used for updating. Should be on the order of half the smaller length of the grid.
final value for radius	The final value for the radius of the neighborhood around each neuron used for updating. Use 1 for a high level of detail of the final map and larger values for more emphasis of coarser structures.
cooling strategy for radius	The radius of the neighborhood is cooled down during training. You can choose the function for the radius w.r.t. to the training episode. linear cooling exponential, i.e. fast in the beginning, slow towards the end linear with lead in/out. The radius is kept constant for the first 20% of the epochs and then cooled down linearly to the final values at 80% of the epochs. no cooling: not recommended for the radius.
start value for learning rate	The initial value for the learning rate used for updating.
final value for learning rate	The final value for the learning rate.
cooling strategy for learning rate	Same as for the radius, no cooling is possible though.
map grid (and grid distance)	The topology of the ESOM grid the the distance function in the map space. There are two topologies: with borders or toroid/border-less grids. The toroid topology avoids border effects by connections the top of the map to the bottom and the left to the right (see images). The distance functions on the grid correspond to the shape of the neighborhood: Manhattan (diamond), Euclidean (circle), Maximum (square).	Planar topology with borders.	Toroid topology without borders.
	Note: we only use quad-grids where each neuron hat four immediate neighbors. The popular hex-grid with six immediate neighbors is implemented in the training part of the Databionics ESOM Tools but not in the visualizations part. Recent studies indicate the the shape of the map is more important for topology preservation than the number of immediate neighbors [Ultsch 2005].	Quad-grid neuron placement.	Hex-grid neuron placement.
neighborhood kernel function	The weighting kernel of the neighborhood used for updating. bubble: constant value in complete neighborhood. cone: linear decay from center to edge of neighborhood. epanechikov: quadratic decay from center to edge of neighborhood. gaussian: gaussian bell shaped kernel. mexican hat: mexican hat shaped kernel.	Cooling functions plotted from center to edge of neighborhood.
permute data patterns	The data points are shuffled before each new training episode. Recommended.
save *.wts and *.bm every n-th epoch	This can be used to create an animation of ESOM training with the slide show function.
save *.umx for each *.wts	For convenience a U-Matrix can be saved for each *.wts file.

# comment
#
% n
% m
% s1		s2			..		sm
% var_name1	var_name2		..		var_namem	
x11		x12			..		x1m
x21		x22			..		x2m
.		.			.		.
.		.			.		.
xn1		xn2			..		xnm

# comment
#
% n
%c_1 s_1   r_1     g_1     b_1
%c_2 s_2   r_2     g_2     b_2
%...
%c_m s_m   r_m     g_m     b_m
id_1	cl_1
id_2	cl_2
..    ..
..    ..
..    ..
id_n	cl_n

% n
key_1	short_1   long_1
key_2	short_2   long_2
..    ..
..    ..
..    ..
key_n	short_n   long_n

#	comment
#	
#
% k l
% m
w001		w002		..	w00m
w011		w012		..	w01m
w021		w022		..	w02m
.	 	.		..	 .
w0(l-1)1	w0(l-1)2	..	w0(l-1)m
w101		w102		..	w10m
w111		w112		..	w11m
.	 	. 		..	 .
w1(l-1)1	w1(l-1)2	..	w1(l-1)m
.	 	. 		.. 	 .
.	 	.		.. 	 .
w(k-1)(l-1)1	w(k-1)(l-1)2	..	w(k-1)(l-1)m

(0,0)	(0,1)	(0,2)	...	(0,l-1)
(1,0)	(1,1)	(1,2)	...	(1,l-1)
...

0	1	2	...	l-1
l	l+1	l+2	...	2l-1
...

% k l
% n
index1		k1	l1
index2		k2	l2
.		.	.
.		.	.
indexn		kn	ln

% k l
h11	h21	h31	..	hk1
h12	h22	h32	..	hk2
.	 .	 .	..	 .
.	 .	 .	.. 	 .
h1l	h2l	h3l	..	hkl