Ordering of the SOM units.

The objective of the SOM is to provide a mapping which preserves the local topology of the input space in the low-dimensional display as faithfully as possible. The preservation of the topology means that nearby inputs are mapped to nearby SOM units.

Assuming that D is the dimension of the input samples, the dimension of the SOM display M can be chosen according to the purpose of the application. The larger M, the more faithful can the neighborhood relations of the input samples preserve, but the more difficult it is to observe the SOM ordering. For simple SOMs, where M=D=1, it can be shown, for example in [Cottrell and Fort, 1987,Erwin et al., 1992a], that under certain conditions on the neighborhood function, the one-dimensional SOM will eventually be ordered so that the SOM weights will form either the sequence  

$$m_1 < m_2 \ldots < m_N \:\:\:\mbox{or}\:\: m_1 \gt m_2 \ldots \gt m_N \:.$$ (4)

For multidimensional SOMs the convergence to an ordered state can be shown only for some special cases. For example, for M=D>1 SOMs organized into a rectangular grid and input $\mbox{\boldmath$x$} \in [0,1]^D$, it is shown in [Flanagan, 1996] that the SOM will attain a dimension-wise ordered state (5) in a finite time with probability one. However, since no absorbing states for the general M=D>1 SOMs are known, the process will also abandon that state in a finite time [Fort and Pages, 1996]. According to [Flanagan, 1996], the M=D>1 SOM is in a dimension-wise ordered state, if for all input dimensions $r = 1, \ldots, M$ holds either  

$$m_{ir} < m_{jr} < m_{kr} \:\:\:\mbox{or}\:\: m_{ir} \gt m_{jr} \gt m_{kr}$$ (5)

for any triple i,j,k of SOM units, if  

$$\mbox{\boldmath$I$}_k - \mbox{\boldmath$I$}_j = \mbox{\boldm... ...dmath$I$}_j - \mbox{\boldmath$I$}_i = \mbox{\boldmath$1$}_r \:.$$ (6)

In (6) the vector $\mbox{\boldmath$I$}_i \in {\cal N}^M$ shows the position of unit i in the SOM grid and the vector $\mbox{\boldmath$1$}_r$ is a M-dimensional vector of zeros except the rth component which equals to one. In (5) the component m_ir refers to the rth component of the weight vector of unit i.

Because no commonly accepted ordering definition is known for the normal case, where D>M>=1, no valid proofs have been given for the general global ordering of the SOM. From the practical point of view, the confirmation of the organization in finite time from random initial state and random sample order is, anyhow, not crucial; it is more interesting to develop ways to produce the desired approximative mapping easily and quickly.