Self-Organizing Map with Generating and Moving Neurons in Visible Space
Kanta Tachibana and Takeshi Furuhashi
Dept. of Computational Science and Engineering, Graduate School of Engineering, Nagoya University, Furou-cho, Chikusa, Nagoya 464-8603, Japan
Kohonen’s Self-Organizing feature Map (SOM) is used to obtain topology-preserving mapping from high-dimensional feature space to visible space of two or fewer dimensions. The SOM algorithm uses a fixed structure of neurons in visible space and learns a dataset by updating reference points in feature space. The mapping result depends on mapping parameters fixed, which are the number and visible positions of neurons, and parameters of learning, which are the learning rate, total iteration, and the setting of neighboring radii. To obtain a satisfactory result, the user usually must try many combinations of parameters. It is wasteful, however, to set up every possible combination of parameters and to repeatedly run the algorithm from the beginning because the computation cost for learning is large, especially for a large-scale dataset. These problems arise due to the fixing of two types of mapping parameters, i.e., the number and visible positions of neurons. The high computation cost is mainly in the calculation of distances from each sample to all reference points. At the beginning of learning, reference points should be adjusted globally to preserve the topology well because they are initially set far from optimal positions in feature space, e.g. randomly. Such many reference points subdivides feature space into unnecessarily fine Voronoi regions. To avoid this computational waste, it is natural to start learning with a small number of neurons and increase the number of neurons during learning. We propose a new SOM method that varies the number and visible positions of neurons, and thus is applicable also to visible torus and sphere spaces. We apply our proposal to spherical visible space. We use central Voronoi tessellation to move visible positions for two reasons: to tessellate visible space evenly for easy visualization and to level the number of neighboring neurons and better preserve topology. We demonstrate the effect of generating neurons to reduce computation cost and of moving visible positions in visualization and topology preservation.
-  D. Alahakoon and S. K. Halgamuge, “Dynamic self-organizing maps with controlled growth for knowledge discovery,” IEEE Transaction on Neural Networks, 11(3), pp. 601-614, May 2000.
-  J. Blackmore and R. Miikkulainen, “Incremental grid growing: Encoding high-dimensional structure into a two-dimensional feature map,” In Proc. of the IEEE International Conference on Neural Networks (ICNN93), pp. 450-455, 1993.
-  J. Blackmore and R. Miikkulainen, “Visualizing high-dimensional structure with the incremental grid growing neural network,” In Proc. of the 12th International Conference on Machine Learning, 1995.
-  Q. Du, V. Faber, and M. Gunzburger, “Centroidal voronoi tessellations: Applications and algorithms,” Society for Industrial and Applied Mathematics Review, 41(4), pp. 637-676, October 1999.
-  B. Fritzke, “Let it grow – self-organizing feature maps with problem dependent cell structure,” In T. Kohonen, K. Mäkisara, O. Simula, and J. Kangas (Eds.), Artificial Neural Networks, Vol.I, pp. 403-408, Amsterdam, Netherlands, North-Holland, 1991.
-  B. Fritzke, “Unsupervised clustering with growing cell structures,” In International Joint Conference on Neural Networks (IJCNN91), Vol.II, pp. 531-536, July 1991.
-  B. Fritzke, “Growing cell structures – a self-organizing network for unsupervised and supervised learning,” Neural Networks, 7, pp. 1441-1460, 1994.
-  B. German, “Glass identification database,” September 1987.
available from ics.uci.edu at the directory /pub/machine-learningdatabases/glass/.
-  S. Kaski and K. Lagus, “Comparing self-organizing maps,” Lecture Notes in Computer Science, 1112, pp. 809-814, 1996.
-  K. Kiviluoto, “Topology preservation in self-organizing maps,” In Proc. International Conference on Neural Networks (ICNN’96), Vol.1, pp. 294-299, 1996.
-  T. Kohonen, “Automatic formation of topological maps of patterns in a self-organizing system,” In Proc. 2nd Scand. Conf. on Image Analysis, pp. 214-220, 1981.
-  T. Kohonen, “Self-organized formation of topologically correct feature maps,” Biological Cybernetics, 43(1), pp. 59-69, January 1982.
-  T. Kohonen, “The speedy som,” Report a33, Helsinki University of Technology, Faculty of Information Technology, Laboratory of Computer and Information Science, 1996.
-  T. Kohonen, “Self-Organizing Maps,” Springer, 3rd edition, 2001.
-  T. Kohonen, J. Hynninen, J. Kangas, and J. Laaksonen, “Som_pak: The self-organizing map program package,” Report a31, Helsinki University of Technology, Faculty of Information Technology, Laboratory of Computer and Information Science, Rakentajanaukio 2C, SF-02150 Espoo, Finland, January 1996.
-  S. P. Lloyd, “Least squares quantization in pcm,” IEEE Transactions on Information Theory, IT-28(2), pp. 129-137, March 1982.
-  D. Nakatsuka and M. Oyabu, “Application of spherical som in clustering,” In Workshop on Self-Organizing Maps (WSOM03), pp. 203-207, 2003.
-  D. Polani, “Organization measures for self-organizing maps,” In T. Kohonen, (Ed.), Proc. Workshop on Self-Organizing Maps (WSOM97), pp. 280-285, 1997.
-  J. S. Rodrigues and L. B. Almeida, “Improving the learning speed in topological maps of patterns,” In Proc. of International Neural Networks Conference (INNC’90), pp. 813-816, 1990.
-  J. S. Rodrigues and L. B. Almeida, “Neural Networks: Advances and Applications,” chapter Improving the convergence in Kohonen topological maps, pp. 63-78. North-Holland, The Netherland, 1991.
-  A. Sangole and G. K. Knopf, “Visualization of randomly ordered numeric data sets using spherical self-organizing feature maps,” Computers & Graphics, 27, pp. 963-976, 2003.
-  K. Sugihara, “Robust gift wrapping for the three-dimensional convex hull,” J. Comput. Syst. Sci., 49(2), pp. 391-407, 1994.
-  K. Tachibana and T. Furuhashi, “A method to evaluate topological information for self-organizing maps,” In Proc. of Joint 3rd International Conference on Soft Computing and Intelligent Systems and 7th International Symposium on advanced Intelligent Systems (SCIS&ISIS2006), pp. 2210-2213, 2006.
-  D. J. Watts, “A simple model of global cascades on random networks,” In Proc. of the National Academy of Sciences of the United States of America (PNAS), Vol.99, pp. 5766-5771, April 2002.