## 3 Population-Based Clustering Algorithms
### Pg-Km
\begin{table}
\begin{tabular}{c c} \hline \hline  & **PB\texttext{$-$KM (J=25, R_{1}=3), R_{2}=40$} \\ \hline PET\({}_{1}\)(s) & 6.4 \\ SSE\({}_{\text{min}}\) & 6.74 \\ CI\({}_{\text{min}}\) (SSE) & 0 \\ CI\({}_{\text{min}}\) (\(\text{\text{\text{\text{\text{\text{\text{\text{\text{\text{\text{\text{\text{\text{ \text{ \text{



in [5]. The experimental results confirm that CI \(=\) 0 always occurs at the minimum value of the objective SSE cost. The S3, Dim1024 and Unbalance datasets were studied using J \(=\) 25 and R\({}_{1}\)\(=\) 3 for the first step (three independent repetitions of K-Means are used for defining each solution of the population), and by R\({}_{2}\)\(=\) 40 for the second step (see Algorithm 4). Due to the higher number of clusters \(K\), Birch1 and Birch2 were instead studied by using J \(=\) 20 and R\({}_{1}\)\(=\) 3 for the first step, and R\({}_{2}\)\(=\) 40 for the second step. Table 8 reports the Parallel Elapsed Time (PET) in sec, required by the first and second step of PB-KM. In reality, PB-KM was capable of detecting the \"best\" solution, that is, one with a minimal SSE and CI, just after a few iterations (in some cases after 1 iteration) of the recombination step. All of this was also confirmed by PB-RS recombination. The results (e.g., CI = 0) in Table 8 are the same as reported in [9], where Random Swap was used, and in [11] where the Recombinator-K-Means tool was exploited. ### Second Group of Real-World Datasets (Table 3)

The Musk and MiniBooNE real-world datasets (data entries preliminarily scaled by min-max normalization), together with the ground truth information inferred from the solutions reported in [14], were easily clustered using PB-KM with J \(=\) 25 and R\({}_{1}\)\(=\) 3 for the first step, and R\({}_{2}\)\(=\) 20 for the second step. The results, which coincide with those reported in [11; 12; 14], are shown in Table 9. Very few iterations of PB-RS also confirmed them. ### Third Group of Synthetic Datasets (Table 4)

All the entries of datasets in Table 4 were preliminarily scaled by the overall maximum. The datasets of this group were processed via PB-RS because it provided the most accurate results. The initial population of Birch3 was built using J \(=\) 20 and T \(=\) 5000 swap iterations of Random Swap always seeded by GKM++, requiring a parallel elapsed time of PET \(=\) 5041 s. The recombination step was carried out using \(T\)\(=\) 10,000 iterations. Figure 4 depicts the SSE vs. the real-time PET (s). Figure 5 shows the Cluster Index (recall Birch3 comes with ground truth centroids, see also Section 2.5) CI vs. real-time PET (s). To ensure a proper number of candidate centroids for the Worms_2d/Worms_64d datasets which have \(K\)\(=\) 35 and \(K\)\(=\) 25 clusters, respectively, a population with J \(=\) 40 solutions and T \(=\) 5000 swap iterations was preliminarily created with PB-RS, requiring PET \(=\) 4485 sec for Worms_2d, and a population of J \(=\) 40 solutions and R\({}_{1}\)\(=\) 3 with PB-KM, requiring PET \(=\) 5156 sec for Worms_64. Notably, a CI \(=\) 12 was estimated in [9] by using standard Parallel Random Swap executed for 10\({}^{5}\) iterations, requiring a PET \(=\) 7341 sec. Figure 5 suggests a final value of CI \(=\) 11, after a significantly smaller time. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Dataset** & **min (SSE)** & **CI\({}_{\text{min (SSE)}}\)** & **avg\_CI** & **Success\_Rate** & **PET\({}_{1}\)(s)** & **PET\({}_{2}\)(s)** \\ \hline \(A3\) & 6.74 & 0 & 0 & 100\% & 6.4 & 2.4 \\ \(S3\) & 18.82 & 0 & 0 & 100\% & 1.1 & 0.5 \\ \(Dim1024\) & 5.39 & 0 & 0 & 100\% & 9.4 & 4.0 \\ \(Unbalance\) & 0.65 & 0 & 0 & 100\% & 0.6 & 0.3 \\ \(Birch1\) & 92.77 & 0 & 0 & 100\% & 277.3 & 96.6 \\ \(Birch2\) & 0.46 & 0 & 0 & 100\% & 242.2 & 99.0 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: PB-KM results on the synthetic datasets of Table 2.