## 3 Population-Based Clustering Algorithms
### Pg-Km
Worms_64d is characterized by 25 clusters with data points with 64 dimensions. The geometrical shapes of the worm \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Dataset** & **N** & **D** & **K** \\ \hline \(A3\) & 7500 & 2 & 50 \\ \(S3\) & 5000 & 2 & 15 \\ \(Dim1024\) & 1024 & 1024 & 16 \\ _Unbalance_ & 6500 & 2 & 8 \\ _Birch1_/2 & 100,000 & 2 & 100 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The first group of synthetic datasets [24]. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Dataset** & **N** & **D** & **K** \\ \hline \(Musk\) & 6598 & 166 & 2 \\ _MiniBooNE_ & 130,064 & 50 & 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The second group of real-world datasets. datasets are determined by starting at a random position and moving in a random direction. At any moment, the points follow a Gaussian distribution, whereby the variance gradually increases step-by-step. In addition, movement direction is continually changed according to an orthogonal direction. In Worms_64d, though, the orthogonal direction gets randomly re-defined at every step. Clustering of worm datasets was investigated in [26] using an enhanced and careful density peak-based algorithm [27]. Birch3 was analyzed, e.g., in [9; 11; 12]. Such previous results will be used as a reference to assess the accuracy of the clustering solutions documented in this paper. To compare with the results in [11; 12], the three datasets will be processed by first scaling down the data entries by the overall maximum. The fourth group (see Table 5) comprises some challenging real-world datasets, many of which are without ground truth information. Clustering difficulties arise from the large number of data points, \(N\), the number of point features, \(D\), and the number of needed clusters, \(K\). \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Dataset** & **N** & **D** & **K** \\ \hline _Birch3_ & 100,000 & 2 & 100 \\ _Worms\_2d_ & 105,600 & 2 & 35 \\ _Worms\_64d_ & 105,000 & 64 & 25 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: The third group of synthetic datasets [24]. Figure 1: The Birch3 dataset [24]. Figure 2: The Worms_2d dataset [24]. The non-binarized version of the Bridge dataset, the 8 bits per color version of the House dataset, and the frame 1 vs. 2 version of Miss America dataset, were downloaded from the [24] repository. They all refer to image data processing. The image facial recognition problem of the Olivetti dataset, from the AT&T Laboratories Cambridge, handles 40 human subjects, each portrayed in 10 different poses. Every facial photo is stored by \(64\times 64~{}=~{}4096\) pixels. The UrbanGB is a large dataset consisting of geographical coordinates of car accidents in Great Britain's urban areas. The dataset can be downloaded from [28]. The solutions for the Olivetti and UrbanGB reported in [11; 12] were used to infer \"ground truth\" information about the datasets. In all the cases, though, the \(SSE\) cost and its evolution vs. the real time can be used for comparison purposes. As in [11; 12], the datasets of the fourth group are processed without scaling, except for the \(UrbanGB\) where the first dimension of the data entries are scaled down by a factor of 1.7. The following simulation experiments were executed on a Win11 Pro platform, Dell XPS 8940, Intel i7-10700 (8 physical cores), [EMAIL_ADDRESS] GHz, 32 GB RAM and Java 17. ### Clustering the A3 Dataset

For a preliminary study, the \(A3\) dataset was chosen (see Table 2 and Figure 3). The goal was to compare the performance of classical Repeated K-Means driven by different seeding methods, to that it was achievable with PB-KM. In particular, \(A3\) was first clustered via Repeated K-Means (RKM) separately fed by uniform random \(\left(\text{RKM}^{\text{Unif}}\right)\), K-Means++ (RKM\({}^{\text{KM++}}\)) and Greedy K-Means++ \(\left(\text{RKM}^{\text{CKM++}}\right)\) seeding procedure.