# Clustering Algorithm with a Greedy Agglomerative Heuristic and Special Distance Measures
## 2 Kohonen Neural Networks for Clustering Problem
### Proposed Algorithms
```
Required: Set of initial data \(X_{1},\ldots,X_{N}\), where \(N\) is the number of points; set the number of neurons \(KI\); \(\eta_{0}\) (\(\eta=\eta_{0}\)), where \(\eta_{0}\) is the initial learning rate; set the step of changing the learning rate \(\Delta\SOM-based algorithm with a greedy agglomerative heuristic is represented in Algorithm 4. Batch versions of described algorithms are similar to their online versions except that the neuron weights are recalculated after passing through all sample points. We denote batch version of SCL algorithm as BVQ (as in Ref. [46]) and batch version of SOM algorithm as BSOM. ```
Required: Set of initial data \(X_{1},\ldots,X_{N_{t}}\) where \(N\) is the number of points; set the number of neurons \(KI\); \(\eta_{0}\) (\(\eta=\eta_{0}\)), where \(\eta_{0}\) is the initial learning rate. 1. Increase the number of neurons \(k\) times \(K=k\cdot KI\)
2. Set the weight of each neuron \(W_{j}\) (\(j=1,K\))
3. \(t=0\)
4. While maximum time is not exceeded: \(t\leq T_{max}\):
5. Randomly choose \(X_{i}\) from initial data \(X_{1},\ldots,X_{N_{t}}\). 6. Find the closest neuron \(W_{d}\) to \(X_{i}\): \(cl=arg\underset{1\leq j\leq K}{min}\,d\left(X_{i},W_{j}\right)\)
7. Update the closest neuron \(W_{d}\) and its neighbors \(V(W_{d})\). 8. Here, \(V(W_{cl})\) is the set of indexes in the neighborhood of \(W_{cl}\), including \(W_{cl}\):  
For each \(p\) in \(V(W_{d})\):  
\(W_{p}=W_{p}+\eta(t)\cdot h(t,d\left(W_{p},W_{cl}\right))\cdot(X_{i}-W_{p})\),  
where \(\eta(t)\) is learning rate, \(h(t,d\left(W_{p},W_{cl}\right))\) is neighborhood function. 8. For each neuron \(W_{j}\), calculate sum of distances to the initial data \(X_{1},\ldots,X_{i}\):  
\(S_{j}=\sum\limits_{j=1}^{K}\sum\limits_{q=1}^{i}\left\|W_{j}-X_{q}\right\|^{2}\)
9. If \(K<K1\), THEN remove neuron \(W_{j}\) with the maximum sum of distances \(S_{j}\)
10. \(\eta=\eta-\Delta\eta\)
11. \(t=t+1\)
12. End while
```

**Algorithm 4** SOM-based algorithm with a greedy agglomerative heuristic (SOM-GREEDY)

## 3 Computational Experiment and Analysis

For the experiment, we considered the sample consisting of four different homogeneous batches of electronic radio components [49]. The total number of devices in all batches is 446. We considered various combinations of batches: mixed lots from four, three and two batches. Four-batch mixed lot contains 62 parameters (features), three-batch mixed lot and two-batch mixed lot contain 41 parameters. The difficulty of the sample is that the number of parameters in it is large enough relative to the number of sample elements. Each experiment is performed in online mode and in batch mode. We used different types of distance measures: Chebyshev distance (ChD), Euclidean distance (EuD), squared Euclidean distance (SEuD), Mahalanobis distance (MahD), Manhattan distance (ManD). The choice of the method for initializing the weight coefficients was also different: average, random and with preliminary clustering by the k-means algorithm. Each experiment was run 30 times. Algorithms were implemented in Java. For the computational experiments, we used the following test system: AMD Ryzen 5-1600 6C/12T 3200 MHz CPU, 16 CB RAM. Each experiment took an average of 1 min of computer time. ### Experiments in Online Mode

In this section, we compare the results of the experiment performed with SCL and SCL-GREEDY methods. Experiment with initial number of neurons \(KI\) coinciding with a given number of clusters is marked as SCL; experiments with the initial number of neurons exceeding the specified number of clusters by two (\(K=2\times KI\)) and three (\(K=3\times KI\)) times are marked as SCL-GREEDY(2) and SCL-GREEDY(3).