Keywords

Introduction

The self-organizing map (SOM) also called Kohonen neural network is a competitive learning artificial neural network proposed by Kohonen in 1982 [1]. It is an unsupervised learning method which has both visualization and clustering properties by discovering the topological structure hidden in the data sets. Essentially the goal of a self-organizing map is to map continuous high-dimensional data onto a discrete low (typically one- or two-) dimensional feature map. As a clustering algorithm, the SOM has been applied widely in various fields including pattern recognition, defect inspection and as a data-mining tool to perform classification of high-dimensional data [2, 3]. Research on improving the performance of the SOM has been going on for decades. One of the key issues to overcome is the low speed learning process while obtaining a well trained map. A SOM is well trained if clustering is achieved in a short time and, at the same time, it creates a projection of data into the map strongly related to the distribution of data in the input space. One of the main reasons for this continued research effort is that the amount of data which is to be analyzed can be huge, for instance thousands of high-dimensional image vectors. The simulation of extensive networks with thousands of neurons, each with high-dimensional weights takes relatively much time on state of the art general purpose computers. To solve this problem, this paper presents a fast version of the SOM algorithm and software simulation proves that the SOM has been accelerated to some extent.

The remainder of this paper is organized as follows: Sect. 2 gives a brief overview of related works. Next, Sect. 3 presents the conventional self-organizing map. Section 4 presents our proposed fast self-organizing map algorithm. Section 5 discusses the experimental results on handwritten digit recognition and finally in Sect. 6 the conclusions are drawn.

Related Work

To improve both the efficiency and effectiveness of the conventional SOM algorithm, many approaches have been proposed. A first possibility to reduce the runtime of the SOM is to compute initial values for the feature map instead of choosing them randomly in such a way that the training will be accelerated. In [4] the K-means clustering algorithm is used to select initial values for the weight vectors of the neurons, which subsequently reduces the required amount of training steps. Because the SOM offers multiple opportunities to exploit the parallel computing [5], a second way of handling the computational complexity is to transform the SOM algorithm into a distributed algorithm. Lobo et al. developed a distributed SOM in order to speed up the training of the SOM [6]. In order to shorten the processing time the batch version of the SOM has been used by Yu and Alahakoon [7], this version of the SOM is also more suitable for parallel implementation. A third way of accelerating the neural computations is to design simplified SOM algorithm. The weight update step is simplified by removing the non-linear functions in the following papers [8, 9] and therefore results in a more hardware-friendly version of the SOM algorithm. Nevertheless, these simplified methods suffer from a low recognition accuracy and are hardly effective in complex applications. In this context, a fast SOM algorithm is proposed in this paper which not only speeds up the training process but also promises a similar recognition accuracy with the conventional SOM.

Self-Organizing Map Algorithm

  1. 1.

    Initialization step: At the start of the SOM algorithm, typically all the weights \( w_{j} \) of the neurons are initialized with random values.

  2. 2.

    Compute the distance between the training vector \( X = \{ x_{1} , \ldots , x_{M} \} \) and each neuron \( N_{j} \) with weight \( w_{j} , \) using the Euclidean distance function:

$$ D_{j} = \sqrt {\sum\limits_{i = 1}^{M} {(x_{i} - w_{ji} )^{2} } } $$
(1)
  1. 3.

    Define the winning neuron as the neuron with the minimum distance.

  2. 4.

    Update each neuron according to the following update function:

$$ w_{j} (t + 1) = w_{j} (t) + \alpha (t) \, \cdot N_{j,I(X)} (t) \, \cdot (X - w_{j} (t)) $$
(2)

\( w_{j} (t + 1) \) is the updated weight vector, \( \alpha \left( t \right) \) the learning rate and \( N_{j,I\left( X \right)} (t) \) the topological neighbourhood value at training step t. I(X) is the winning neuron.

  1. 5.

    Update the neighborhood function and the learning rate.

  2. 6.

    Repeat steps 2–5 for the next training vector.

Fast Self-Organizing Map Algorithm

Distance calculation The conventional self-organizing map uses the Euclidean norm as the distance calculating function (see Eq. 1), however because it involves the squaring of values and a square root, the Euclidean distance computation is time-consuming for software prototype and also resource-intensive for hardware implementation. Following [8, 10], we use the Manhattan distance which is computationally simpler for calculating the distance between vectors.

$$ D_{j} = \sum\limits_{i = 1}^{M} {|(x_{i} - w_{ji} )|} $$
(3)

Learning Rate Function The learning rate is typically defined as the following exponential function.

$$ \alpha (t) = \alpha_{0} \cdot exp\left( {\frac{ - t}{{\tau_{\alpha } }}} \right) $$
(4)

Note that because of the multiplication, division and exponential function, this function will cost too much learning time. To reduce the computational complexity imposed by the exponential calculation of the conventional SOM, an alternative formula is selected to substitute the conventional Eq. 4. Actually, this alternative is the first term of the Taylor series expansion of Eq. 4.

$$ \alpha = \alpha_{0} \left( {1 - \frac{t}{T}} \right) $$
(5)

Neighborhood Function When using Kohonen’s self-organizing map, the distance in the feature map between the neurons influences the learning process. A typical neighborhood function is shown in Eq. 6, which decreases not just over time, but also depends on the topological distance of the two neurons in the net.

$$ N_{x,y} (t) = exp\left( {\frac{{ - d_{x,y}^{2} }}{{2\sigma^{2} (t)}}} \right) $$
(6)

Here \( d_{x,y} \) is the distance between node x and node y, more specifically it is the physical distance between the nodes in the feature map and \( \sigma \left( t \right) \) the time dependent value responsible for decreasing the neighborhood size over time.

However our proposed neighborhood function ignores any influence of time and only depends on the topological distance between two neurons, which is computed by the Euclidean norm. For each neuron within the neighborhood size ns, the neighborhood parameter is calculated as shown in Eq. 7. Neurons outside this neighborhood area will not be updated.

$$ N_{x,y} = \left\{ {\begin{array}{*{20}c} {e^{{ - 2d_{x,y}^{2} }} } & {if \, d(x,y) \le ns} \\ 0 & {if \, d(x,y) > ns} \\ \end{array} } \right. $$
(7)

The weight update function depends on both the learning rate function and the neighborhood function. In Fig. 1, respectively the results of the conventional weight update function and our proposed weight update function are shown in the condition of \( \alpha_{0} = 1 ,d_{x,y} = [0,4] ,t = [0,10000]. \) Note that the shapes of the 3D charts based on these functions are similar, which motivates the similarity in performance between both versions. The performance results will be given in the last section.

Fig. 1
figure 1

Comparison of weight update functions. a Proposed weight update function. b Conventional weight update function

Full size image

Case Study: Handwritten Digit Recognition

The performance of the SOM was tested in the field of handwritten digit recognition and the MNIST database was chosen to train and test the feature map [11]. We evaluated the proposed fast SOM by a software simulation on a PC with a general purpose processor clocked at 2.1 GHz and 2 GB of SDRAM. In Fig. 2, the runtime with varying amounts of iterations and varying amounts of neurons is compared between the proposed fast SOM and the conventional SOM respectively. By using the Manhattan distance metric, a simplified learning rate and neighborhood function, no multiplications and exponential computations is required, due to this a reduction in time ranging from 15 to 20 % can be achieved.

Fig. 2
figure 2

Runtime comparison between conventional and fast SOM. a Runtime with different training steps. b Runtime with varying numbers of neurons

Full size image

Furthermore, it is also important to note that the proposed fast SOM algorithm is able to obtain this speed-up while maintaining an accuracy which is similar compared to the conventional SOM. Our fast SOM algorithm outperforms other simplified SOM algorithms such as [8, 9].

In Table 1 the recognition accuracy of the conventional, our fast version and also Pena’s [10] SOMs are shown. These were obtained by various numbers of iterations and each iteration equals training the feature map with 60,000 input vectors. Afterwards, the SOM is tested with 10,000 test samples. Finally the feature maps of the conventional and proposed SOMs are shown in Fig. 3. The neurons of both maps clearly organized themselves and clusters can be distinguished.

Table 1 Recognition accuracy on MNIST database
Full size table
Fig. 3
figure 3

Feature map after training with MNIST dataset. a Feature map of proposed SOM. b Feature map of conventional SOM

Full size image

Conclusion

This paper proposes a fast SOM algorithm for handwritten digit recognition which simplifies the conventional SOM by removing complex computations in the weight distance calculation, the learning rate function and the neighborhood function. After evaluating the performance in software simulation, we conclude that the proposed fast SOM algorithm can reach the goal of accelerating to some extent, maintain similar recognition accuracy compared to the conventional SOM and performs much better than other simplified SOM methods.