# Clustering Algorithm with a Greedy Agglomerative Heuristic and Special Distance Measures
## 2 Kohonen Neural Networks for Clustering Problem
### Vector Quantization Networks and Self-Organizing Kohonen Maps  
A Kohonen network [15; 39] is a self-organized neural network that enables us to allocate groups (clusters) of input vectors that have some common features. The Kohonen network (or Kohonen layer) is a single-layer network, each neuron of which is connected to all components of the input vector. The input vector is a description of one of the objects to be clustered. The number of neurons coincides with the number of clusters \(K\) that the network should allocate. Linear weighted adders are used as neurons in the Kohonen network. Each \(j\)-th neuron is described by a vector of weights \(W_{j}=(w_{1j},\,w_{2j},\,\ldots,\,w_{Mj})\), where \(M\) is input vector dimension, \(j=1\,\ldots\,\,K\). The input vector has the form \(X_{i}=(x_{1i},\,x_{2i},\,\ldots,\,x_{Mi})\), \(i=1\,\ldots\,\,N\), where \(N\) is number of objects. According to the methods of adjusting the input weights of the adders and the problems being solved, many varieties of Kohonen networks are distinguished [46]. The most famous of them are:  
1. Vector quantization networks (VQ), closely related to k-means method;
2. Self-organizing Kohonen maps (SOM), which provide a \"topological\" mapping from the input space to the clusters. Neurons in SOMs are organized into a grid (usually two-dimensional);
3. Learning vector quantization networks (LVQ), which include supervised learning and used for classification problems. First two types of Kohonen networks refer to unsupervised learning, considered in this article. Vector quantization consists of replacing a continuous distribution by a finite set of quantizers while minimizing a predefined distortion criterion and may be used to determine groups (clusters) of data sharing common properties [46]. Since vector quantization is a natural application for k-means, the centroids are also referred to as a \"codes\", and the table mapping codes to centroid is often referred to as a \"codebook\". Competition mechanisms are used to train the network according to principle \"winner takes all\", for instance, simple competitive learning (SCL) algorithm [47]. When the vector \(X\) is fed to the network input, the neuron wins, the weight vector of which is the least different from the input vector: \(d(X,W_{cl})=\min\limits_{1\leq j\leq K}d(X,W_{j})\). This problem with \(K\) key vectors \(W_{j}\) in the feature space of the observed data \(X\) in terms of vector quantization is defined as a minimization of encoding distortion, i.e., as minimization problem:  
\[D=\sum\
olimits_{j=1}^{K}\sum\
olimits_{x\in V(j)}\left|\left|x-W_{j}\right| \right|^{2}\ \to min \tag{9}\]  
where \(V(j)\) consists of points \(X_{i}\in X\) closest to \(W_{j}\). The SCL algorithm is in fact the online version of the Lloyd's algorithm. If all data points are known in advance, this algorithm works offline as a batch algorithm (batch vector quantization, BVQ). The k-means method is an intermediate version, where only one data point is randomly chosen, and only the winning centroid is updated as the mean value of its cluster [46]. Thus, we can say that Kohonen networks have an advantage over the k-means model in that they allow organizing the online clustering. Basic version of SCL algorithm is represented in Algorithm 1. ```
0: Set of initial data vectors \(X_{1},\ldots,X_{N}\), where \(N\) is the number of points; set the number of neurons \(K\); \(\eta_{0}\) (\(\eta=\eta_{0}\)), where \(\eta_{0}\) is the initial learning rate; set the step of changing the learning rate \(\Delta\eta\);
1. Set the weight of each neuron \(W_{j}\) (\(j=1,K\))
2. While \(\eta>0\):
3. for \(i=\overline{1,N}\) do
4. for \(j=\overline{1,K}\) do
5. Find the closest neuron \(W_{cl}\) to \(X_{i}\): \(cl=arg\min\limits_{1\leq j\leq K}d\left(X_{i},W_{j}\right)\)
6. Update the closest neuron: \(W_{cl}=W_{cl}+\eta\cdot(X_{i}-W_{cl})\)
7.