next up previous contents
Next: Other Clustering Methods Up: Algorithms Previous: Hypergraph Partitioning (HGP)   Contents

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$.

Alexander Strehl 2002-05-03