Detection of locally relevant variables using SOM–NG algorithm

Abstract

The SOM–NG algorithm is a combination of the Self-Organizing Map and the Neural Gas algorithms. It was developed to combine quantization and topological preservation. The algorithm also has a supervised version to create local linear models of scalar fields in the defined Voronoi regions. In this work a new methodology is proposed to use those models as data mining tools. Using visual tools, gradients are analysed to discover the influence of each variable over the output. It does not only allow to select the most relevant variables but also to detect different zones of influence, which can be used to create a set of fuzzy rules. The proposed methodology is proven to be useful to detect locally relevant variables that lead to a better understanding of the data.

Introduction

Prototype based neural networks are trained to obtain a representative set of points with the same characteristics as the original data set, this is called vector quantization. A classic algorithm for this purpose is k-means (MacQueen, 1967) that reassigns them to the mean of the data points included in the Voronoi region they define. In this algorithm only the closest prototype is modified by each data point, so a “winner-takes-all” philosophy is used.

Neural Gas (NG) is another vector quantization algorithm, presented in Martinetz et al. (1993), which reaches an optimum distribution of prototypes. The main difference between NG and k-means is the use of a neighbourhood ranking between prototype vectors and each data point. It is a cooperative–competitive algorithm which avoids local minima. To improve the convergence speed and the robustness of the algorithm, a batch version is presented in Cottrell et al. (2006). NG reaches optimum distributions at the cost of having no order between prototypes, thus it does not offer output maps.

Supervised versions of NG have been also developed, specially for classification. A supervised version based on a combination of NG and Generalized Learning Vectors Quantization (Sato and Yamada, 1995) is defined in Hammer et al. (2005), which updates all the prototypes of the respective class depending on the NG ranking. A different Supervised Neural Gas was developed including the class labels as additional dimensions and weighting them with a mixing parameter in Hammer et al. (2006).

Another important quantization algorithm is the Self-Organizing Map (SOM), also called Kohonen Map (Kohonen, 2001). Instead of using free moving prototypes, its learning rule is based on a predefined lattice and the learning rule depends also on the position of each unit in that lattice and not only on the distance to the data points. This algorithm has suppose a great advance in machine learning because of its many features, mainly the dimensionality reduction and the topological preservation.

In data mining, SOM is widely used for visualization purposes. The main tools for visualization are the component planes and the U-matrix. Component planes are a representation of the predefined lattice with a colour scale for the values of each dimension in the input space. These component planes allow the user to find non-linear relationships between different variables. The U-matrix represents the distance between adjacent prototypes in the lattice, so different clusters can be defined using the boundaries defined by significantly higher distances. A detailed work of the use of U-matrix can be found in Ultsch (2003).

SOM has been used for multiple tasks, and specific modifications were created for different purposes. In order to create a continuous map based on the lattice, an interpolation method, called “Interpolating Self-Organizing Map” (I-SOM) was started in Göppert and Rosenstiel (1993) and developed in different phases until Göppert and Rosenstiel (1997), where a soft interpolating method was used to obtain the “Continuous Interpolating Self-Organizing Map” (CI-SOM) . Both I-SOM and CI-SOM are based on interpolation using the closest prototypes to the winning neuron, i.e. D+1 neurons were required for a D-dimensional data vector. These interpolating SOMs are proposed for function approximation specially if these can be reduced to a low dimension map.

To predict temporal sequences some special versions of SOM were developed, like the Temporal Kohonen Map (TKM), the Recurrent SOM and Recursive SOM. Temporal Kohonen Map, defined in Chappell and Taylor (1993), uses “leaky integrators” to select the best matching unit (bmu), so the previous state is taken in care to select the new winning neuron. Recurrent SOM, proposed in Varsta et al. (1997), applies an IIR filter to the sequence instead of filtering the output. Recursive SOM, described in Voegtlin (2002), uses both the actual map and a copy of the previous one. So a new data entry is a combination of the input vector and a context vector based on the copy of the map in the previous instant. They all have the advantage of using chunks of temporally ordered data instead of having to create a special data set including ordered fields. A more detailed review on temporal extensions can be found in Salhi et al. (2009).

In many fields of knowledge gradients are used for many tasks, e.g. surface reconstruction or optimization algorithms. There are many approaches for estimating the gradient; mathematical literature has different estimation methods based on local estimators designed for specific problems (Meyer et al., 2001, Hazen and Gupta, 2009).

This work is based on a combination of SOM and NG, with the main goal of having better quantization without losing the good properties of having a predefined lattice. This algorithm was presented in Machón-González et al. (2010) and an intermediate behaviour between the free moving prototypes in NG and the rigid order of SOM maps was obtained. As it was an interesting tool for quantization and clustering, a supervised version was developed in Crespo Ramos et al. (2011) using a linear model for each prototype in the codebook.

In this paper coefficients of local linear models get physical meaning as gradient components instead of being just numerical tools for estimation. Gradient norms provide variability and stability information of the represented system.

A description of the algorithm is included in Section 2, after that the new gradient analysis method is proposed in Section 3, experimental testing is performed in Section 4 and finally the results will be discussed in Section 5.