Self-Organizing Map (SOM)

The self-organizing map [Koh95,Bis95] is a popular topology preserving clustering algorithm with nice visualization properties. For simplicity, we only use a 1-dimensional line topology. Also, 2-dimensional or higher dimensional topologies can be used. To generate $k$ clusters we use $k$ cells in a line topology and train the network for $m = 5000$ epochs or 10 minutes (whichever comes first). All experiments are run on a dual processor 450 MHz Pentium using the SOM implementation in the Matlab neural network tool-box. The resulting network is subsequently used to generate the label vector $\mathbf{\lambda}$ from the index of the most activated neuron for each sample. The complexity of this incremental algorithm is $O(n \cdot d \cdot k \cdot m)$ and mostly determined by the number of epochs $m$ and samples $n$.