A combined measure for quantifying and qualifying the topology preservation of growing self-organizing maps

The Self-Organizing Map (SOM) is a neural network model that performs an ordered projection of a high dimensional input space in a low-dimensional topological structure. The process in which such mapping is formed is defined by the SOM algorithm, which is a competitive, unsupervised and nonparametric method, since it does not make any assumption about the input data distribution. The feature maps provided by this algorithm have been successfully applied for vector quantization, clustering and high dimensional data visualization processes. However, the initialization of the network topology and the selection of the SOM training parameters are two difficult tasks caused by the unknown distribution of the input signals. A misconfiguration of these parameters can generate a feature map of low-quality, so it is necessary to have some measure of the degree of adaptation of the SOM network to the input data model. The topology preservation is the most common concept used to implement this measure. Several qualitative and quantitative methods have been proposed for measuring the degree of SOM topology preservation, particularly using Kohonen's model. In this work, two methods for measuring the topology preservation of the Growing Cell Structures (GCSs) model are proposed: the topographic function and the topology preserving map.     

A directed batch growing approach to enhance the topology preservation of self-organizing map

The growing self-organizing map (GSOM) possesses effective capability to generate feature maps and visualizing high-dimensional data without pre-determining their size. Most of the proposed growing SOM algorithms use an incremental learning strategy. The conventional growing approach of GSOM is based on filling all available position around the candidate neuron which can decrease the topology preservation quality of the map due to the misconfiguration and twisting of the map which could be a consequence of unexpected network growth and improper neuron addition and weight initialization. To overcome this problem, in this paper we introduce a batch learning strategy for growing self-organizing maps called DBGSOM which direct the growing process based on the accumulative error around the candidate boundary neuron. In the proposed growing approach, just one new neuron is added around each candidate boundary neuron. The DBGSOM offers suitable mechanisms to find a proper growing positions and allocating initial weight vectors for the new neurons.The potential of the DBGSOM was investigated with one synthetic dataset and six real-world benchmark datasets in terms of topology preservation and mapping quality. Experimental results showed that the proposed growing strategy provides an enhanced topology preserved map and reduces the susceptibility of twisting compared to GSOM. Furthermore, the proposed method has a better clustering ability than GSOM and SOM. According to the lower number of neurons generated by DBGSOM, it needs less time to learn the manifold of the data points compared to GSOM.     

Controlling the spread of dynamic self-organising maps

The growing self-organising map (GSOM) has recently been proposed as an alternative neural network architecture based on the traditional self-organising map (SOM). The GSOM provides the user with the ability to control the spread of the map by defining a parameter called the spread factor (SF), which results in enhanced data mining and hierarchical clustering opportunities. When experimenting with the SOM, the grid size (number of rows and columns of nodes) can be changed until a suitable cluster distribution is achieved. In this paper we highlight the effect of the spread factor on the GSOM and contrast this effect with grid size change (increase and decrease) in the SOM. We also present experimental results in support of our claims regarding differences between GSOM and SOM.     

Quantifying the neighborhood preservation of self-organizingfeature maps

It is shown that a topographic product P, first introduced in nonlinear dynamics, is an appropriate measure of the preservation or violation of neighborhood relations. It is sensitive to large-scale violations of the neighborhood ordering, but does not account for neighborhood ordering distortions caused by varying areal magnification factors. A vanishing value of the topographic product indicates a perfect neighborhood preservation; negative (positive) values indicate a too small (too large) output space dimensionality. In a simple example of maps from a 2D input space onto 1D, 2D, and 3D output spaces, it is demonstrated how the topographic product picks the correct output space dimensionality. In a second example, 19D speech data are mapped onto various output spaces and it is found that a 3D output space (instead of 2D) seems to be optimally suited to the data. This is an agreement with a recent speech recognition experiment on the same data set.     

Cluster identification and separation in the growing self-organizing map: application in protein sequence classification

Growing self-organizing map (GSOM) has been introduced as an improvement to the self-organizing map (SOM) algorithm in clustering and knowledge discovery. Unlike the traditional SOM, GSOM has a dynamic structure which allows nodes to grow reflecting the knowledge discovered from the input data as learning progresses. The spread factor parameter (SF) in GSOM can be utilized to control the spread of the map, thus giving an analyst a flexibility to examine the clusters at different granularities. Although GSOM has been applied in various areas and has been proven effective in knowledge discovery tasks, no comprehensive study has been done on the effect of the spread factor parameter value to the cluster formation and separation. Therefore, the aim of this paper is to investigate the effect of the spread factor value towards cluster separation in the GSOM. We used simple k-means algorithm as a method to identify clusters in the GSOM. By using Davies–Bouldin index, clusters formed by different values of spread factor are obtained and the resulting clusters are analyzed. In this work, we show that clusters can be more separated when the spread factor value is increased. Hierarchical clusters can then be constructed by mapping the GSOM clusters at different spread factor values.     

基于生长的自组织映射的数据挖掘

在数据挖掘应用中,基于自生成神经网络的方法被认为是比基于固定网络方法更好的一种替代方法。介绍了自组织映射(SOM)算法和生长的自组织映射(GSOM)模型,证明了GSOM的功能可以扩展成最近原型分类,并给出了其在数据挖掘中的一个应用。     

ParaGro: a learning algorithm for growing parallel self-organizing maps with any input/output dimensions

Self-organizing maps (SOM) have become popular for tasks in data visualization, pattern classification or natural language processing and can be seen as one of the major contemporary concepts for artificial neural networks. The general idea is to approximate a high dimensional and previously unknown input distribution by a lower dimensional neural network structure so that the topology of the input space is mapped closely. Not only is the general topology retained but the relative densities of the input space are reflected in the final output. Kohonen maps also have the property of neighbor influence. That is, when a neuron decides to move, it pulls all of its neighbors in the same direction modified by an elasticity factor. We present a SOM that processes the whole input in parallel and organizes itself over time. The main reason for parallel input processing lies in the fact that knowledge can be used to recognize parts of patterns in the input space that have already been learned. Thus, networks can be developed that do not reorganize their structure from scratch every time a new set of input vectors is presented, but rather adjust their internal architecture in accordance with previous mappings. One basic application could be a modeling of the whole–part relationship through layered architectures.

The presented neural network model implements growing parallel SOM structure for any input and any output dimension. The advantage of the proposed algorithm is in its property of processing the whole input space in one step. All nodes of the network compute their step simultaneously, and are, therefore, able to detect known patterns without reorganizing. The simulation results support the theoretical framework presented in the following sections.     

双目立体视觉和GSOM相结合的机器人自主地图构建方法

双目立体视觉和自组织可增长特征映射图GSOM(Growing Self-organizing Map)相结合的机器人地图构建方法首先利用双目立体摄像机采集图像,借助双目立体视觉处理技术,将采集到的图像信息转化成神经网络的训练样本;然后利用GSOM的地图绘制算法,通过不断增加新的神经元实现网络规模的增长,用441个SOM神经元便表示了2000个样本点的环境特征信息的拓扑地图,体现了对输入样本分布的逼近特性;实验结果表明双目立体视觉和GSOM相结合的机器人自主地图构建方法可行,并表现出类似生物的自主智能行为。     

Dynamic self-organizing maps with controlled growth for knowledgediscovery

The growing self-organizing map (GSOM) algorithm is presented in detail and the effect of a spread factor, which can be used to measure and control the spread of the GSOM, is investigated. The spread factor is independent of the dimensionality of the data and as such can be used as a controlling measure for generating maps with different dimensionality, which can then be compared and analyzed with better accuracy. The spread factor is also presented as a method of achieving hierarchical clustering of a data set with the GSOM. Such hierarchical clustering allows the data analyst to identify significant and interesting clusters at a higher level of the hierarchy, and continue with finer clustering of the interesting clusters only. Therefore, only a small map is created in the beginning with a low spread factor, which can be generated for even a very large data set. Further analysis is conducted on selected sections of the data and of smaller volume. Therefore, this method facilitates the analysis of even very large data sets.     

Continuous state/action reinforcement learning: A growing self-organizing map approach

This paper proposes an algorithm to deal with continuous state/action space in the reinforcement learning (RL) problem. Extensive studies have been done to solve the continuous state RL problems, but more research should be carried out for RL problems with continuous action spaces. Due to non-stationary, very large size, and continuous nature of RL problems, the proposed algorithm uses two growing self-organizing maps (GSOM) to elegantly approximate the state/action space through addition and deletion of neurons. It has been demonstrated that GSOM has a better performance in topology preservation, quantization error reduction, and non-stationary distribution approximation than the standard SOM. The novel algorithm proposed in this paper attempts to simultaneously find the best representation for the state space, accurate estimation of Q-values, and appropriate representation for highly rewarded regions in the action space. Experimental results on delayed reward, non-stationary, and large-scale problems demonstrate very satisfactory performance of the proposed algorithm.     

TASOM: a new time adaptive self-organizing map

The time adaptive self-organizing map (TASOM) network is a modified self-organizing map (SOM) network with adaptive learning rates and neighborhood sizes as its learning parameters. Every neuron in the TASOM has its own learning rate and neighborhood size. For each new input vector, the neighborhood size and learning rate of the winning neuron and the learning rates of its neighboring neurons are updated. A scaling vector is also employed in the TASOM algorithm for compensation against scaling transformations. Analysis of the updating rules of the algorithm reveals that the learning parameters may increase or decrease for adaptation to a changing environment, such that the minimum increase or decrease is achieved according to a specific measure. Several versions of the TASOM-based networks are proposed in this paper for different applications, including bilevel thresholding of grey level images, tracking of moving objects and their boundaries, and adaptive clustering. Simulation results show satisfactory performance of the proposed methods in the implemented applications.     

Self-organizing feature maps with self-adjusting learningparameters

Presents an extension of the self-organizing learning algorithm of feature maps in order to improve its convergence to neighborhood preserving maps. The Kohonen learning algorithm is controlled by two learning parameters, which have to be chosen empirically because there exists neither rules nor a method for their calculation. Consequently, often time consuming parameter studies have to precede before a neighborhood preserving feature map is obtained. To circumvent those lengthy numerical studies, here, a method is presented and incorporated into the learning algorithm which determines the learning parameters automatically. Therefore, system models of the learning and organizing process are developed in order to be followed and predicted by linear and extended Kalman filters. The learning parameters are optimal within the system models, so that the self-organizing process converges automatically to a neighborhood preserving feature map of the learning data.     

Yet another algorithm which can generate topography map

This paper presents an algorithm to form a topographic map resembling to the self-organizing map. The idea stems on defining an energy function which reveals the local correlation between neighboring neurons. The larger the value of the energy function, the higher the correlation of the neighborhood neurons. On this account, the proposed algorithm is defined as the gradient ascent of this energy function. Simulations on two-dimensional maps are illustrated.     

`Neural-gas'' network for vector quantization and its application totime-series prediction

A neural network algorithm based on a soft-max adaptation rule is presented. This algorithm exhibits good performance in reaching the optimum minimization of a cost function for vector quantization data compression. The soft-max rule employed is an extension of the standard K-means clustering procedure and takes into account a neighborhood ranking of the reference (weight) vectors. It is shown that the dynamics of the reference (weight) vectors during the input-driven adaptation procedure are determined by the gradient of an energy function whose shape can be modulated through a neighborhood determining parameter and resemble the dynamics of Brownian particles moving in a potential determined by the data point density. The network is used to represent the attractor of the Mackey-Glass equation and to predict the Mackey-Glass time series, with additional local linear mappings for generating output values. The results obtained for the time-series prediction compare favorably with the results achieved by backpropagation and radial basis function networks.     

Three‐dimensional map building for mobile robot navigation environments using a self‐organizing neural network

In recent years, mobile robots have been required to become more and more autonomous in such a way that they are able to sense and recognize the three‐dimensional space in which they live or work. In this paper, we deal with such an environment map building problem from three‐dimensional sensing data for mobile robot navigation. In particular, the problem to be dealt with is how to extract and model obstacles which are not represented on the map but exist in the real environment, so that the map can be newly updated using the modeled obstacle information. To achieve this, we propose a three‐dimensional map building method, which is based on a self‐organizing neural network technique called “growing neural gas network.” Using the obstacle data acquired from the 3D data acquisition process of an active laser range finder, learning of the neural network is performed to generate a graphical structure that reflects the topology of the input space. For evaluation of the proposed method, a series of simulations and experiments are performed to build 3D maps of some given environments surrounding the robot. The usefulness and robustness of the proposed method are investigated and discussed in detail. © 2004 Wiley Periodicals, Inc.     

Topology constraint free fuzzy gated neural networks for patternrecognition

A novel topology constraint free neural network architecture using a generalized fuzzy gated neuron model is presented for a pattern recognition task. The main feature is that the network does not require weight adaptation at its input and the weights are initialized directly from the training pattern set. The elimination of the need for iterative weight adaptation schemes facilitates quick network set up times which make the fuzzy gated neural networks very attractive. The performance of the proposed network is found to be functionally equivalent to spatio-temporal feature maps under a mild technical condition. The classification performance of the fuzzy gated neural network is demonstrated on a 12-class synthetic three dimensional (3-D) object data set, real-world eight-class texture data set, and real-world 12 class 3-D object data set. The performance results are compared with the classification accuracies obtained from a spatio-temporal feature map, an adaptive subspace self-organizing map, multilayer feedforward neural networks, radial basis function neural networks, and linear discriminant analysis. Despite the network's ability to accurately classify seen data and adequately generalize validation data, its performance is found to be sensitive to noise perturbations due to fine fragmentation of the feature space. This paper also provides partial solutions to the above robustness issue by proposing certain improvements to various modules of the proposed fuzzy gated neural network.     

Finding the right pixel size

This paper discusses empirical and analytical rules to select a suitable grid resolution for output maps and based on the inherent properties of the input data. The choice of grid resolution was related with the cartographic and statistical concepts: scale, computer processing power, positional accuracy, size of delineations, inspection density, spatial autocorrelation structure and complexity of terrain. These were further related with the concepts from the general statistics and information theory such as Nyquist frequency concept from signal processing and equations to estimate the probability density function. Selection of grid resolution was demonstrated using four datasets: (1) GPS positioning data—the grid resolution was related to the area of circle described by the error radius, (2) map of agricultural plots—the grid resolution was related to the size of smallest and narrowest plots, (3) point dataset from soil mapping—the grid resolution was related to the inspection density, nugget variation and range of spatial autocorrelation and (4) contour map used for production of digital elevation model—the grid resolution was related with the spacing between the contour lines i.e. complexity of terrain. It was concluded that no ideal grid resolution exists, but rather a range of suitable resolutions. One should at least try to avoid using resolutions that do not comply with the effective scale or inherent properties of the input dataset. Three standard grid resolutions for output maps were finally recommended: (a) the coarsest legible grid resolution—this is the largest resolution that we should use in order to respect the scale of work and properties of a dataset; (b) the finest legible grid resolution—this is the smallest grid resolution that represents 95% of spatial objects or topography; and (c) recommended grid resolution—a compromise between the two. Objective procedures to derive the true optimal grid resolution that maximizes the predictive capabilities or information content of a map are further discussed. This methodology can now be integrated within a GIS package to help inexperienced users select a suitable grid resolution without doing extensive data preprocessing.     

Curvilinear component analysis: a self-organizing neural networkfor nonlinear mapping of data sets

We present a new strategy called "curvilinear component analysis" (CCA) for dimensionality reduction and representation of multidimensional data sets. The principle of CCA is a self-organized neural network performing two tasks: vector quantization (VQ) of the submanifold in the data set (input space); and nonlinear projection (P) of these quantizing vectors toward an output space, providing a revealing unfolding of the submanifold. After learning, the network has the ability to continuously map any new point from one space into another: forward mapping of new points in the input space, or backward mapping of an arbitrary position in the output space.     

基于Voronoi地图表示方法的同步定位与地图创建

针对基于混合米制地图机器人同步定位与地图创建 (Simultaneous localization and mapping, SLAM)中地图划分方法不完善的问题, 提出了基于Voronoi地图表示方法的同步定位与地图创建算法VorSLAM. 该算法在全局坐标系下创建特征地图, 并根据此特征地图使用Voronoi图唯一地划分地图空间, 在每一个划分内部创建一个相对于特征的局部稠密地图. 特征地图与各个局部地图最终一起连续稠密地描述了环境. Voronoi地图表示方法解决了地图划分的唯一性问题, 理论证明局部地图可以完整描述该划分所对应的环境轮廓. 该地图表示方法一个基本特点是特征与局部地图一一对应, 每个特征都关联一个定义在该特征上的局部地图. 基于该特点, 提出了一个基于形状匹配的数据关联算法, 用以解决传统数据关联算法出现的多重关联问题. 一个公寓弧形走廊的实验验证了VorSLAM算法和基于形状匹配的数据关联方法的有效性.     

Self-Organizing Map Formation with a Selectively Refractory Neighborhood

Decreasing neighborhood with distance has been identified as one of a few conditions to achieve final states in the self-organizing map (SOM) that resemble the distribution of high-dimensional input data. In the classic SOM model, best matching units (BMU) decrease their influence area as a function of distance. We introduce a modification to the SOM algorithm in which neighborhood is contemplated from the point of view of affected units, not from the view of BMUs. In our proposal, neighborhood for BMUs is not reduced, instead the rest of the units exclude some BMUs from affecting them. Each neuron identifies, from the set of BMUs that influenced it in previous epochs, those to whom it becomes refractory to for the rest of the process. Despite that the condition of decreasing neighborhood over distance is not maintained, self-organization still persists, as shown by several experiments. The maps achieved by the proposed modification have, in many cases, a lower error measure than the maps formed by SOM. Also, the model is able to remove discontinuities (kinks) from the map in a very small number of epochs, which contrasts with the original SOM model.