## 3 Population-Based Clustering Algorithms
### Pg-Km
Then, \(10^{4}\) repetitions of K-Means were executed and the following quantities monitored: (a) the minimal value of the SSE cost (SSE\({}_{\text{min}}\)), (b) the corresponding Cluster Index (CI) value (see Section 2.5) (CI\({}_{\text{min (SSE)}}\)), (c) the minimal value of the observed CI (CI\({}_{\text{min}}\)) and the corresponding value of the SSE cost (SSE\({}_{\text{min(CI)}}\)), (d) the emerging average CI value

Figure 3: The A3 synthetic dataset [24]. \begin{table}
\begin{tabular}{c c c c} \hline
**Dataset** & **N** & **D** & **K** \\ \hline _Bridge_ & 4096 & 16 & 256 \\ _House_ & 34,112 & 3 & 256 \\ _Miss America_ & 6480 & 16 & 256 \\ _Olitetti_ & 400 & 4096 & 40 \\ _UrbanGB_ & 360,177 & 2 & 469 \\ \hline \end{tabular}
\end{table} 
Table 5: The fourth group of real-world datasets. (avg_CI) and (e) the success_rate, that is, the number of runs which ended with a CI \(=~{}0\), divided by \(10^{4}\). In addition, the Parallel Execution Time (PET), in sec, needed by Repeated K-Means to complete its runs was also observed. Table 6 collects all the achieved results. The experimental data in Table 6 clearly confirm the superior behavior ensured by GKM++ seeding, which makes RKM capable of outperforming the scenarios where K-Means++ (KM++) or the uniform random (Unif) centroids initialization is adopted. The observed average CI and the success rate are worth being noted. As one case see in Table 6, it always happens that the minimum CI value occurs at the minimum SSE cost. The RKM\({}^{\text{GKM++}}\) results in Table 6 comply with the results reported, e.g., in [9; 11]. Table 7 collects the results observed when using PB-KM with the parameter values J \(=~{}25\) and R\({}_{1}~{}=~{}3\) adopted in the first step (see Algorithm 4), and the value R\({}_{2}~{}=~{}40\) used for the second step. Only the PET was annotated for the first step, which creates the population of candidate solutions. The second-step results clearly confirm that PB-KM is able to correctly solve the A3 dataset. In fact, a success_rate of 100% and CI \(=~{}0\) were observed. The SSE minimal value coincides with that obtained with RKM\({}^{\text{GKM++}}\) in Table 6.

Results in Table 7 also show how the execution time of PB-KM outperforms that achievable by straight Repeated K-Means (see Table 6). The same results of minimal \(SSE\) and CI, and a 100% success_rate were also observed when using R\({}_{2}~{}=~{}10\). In reality, one single recombination iteration is sufficient for obtaining the minimal SSE and CI. All of this was precisely confirmed by using the PB-RS recombination on the same population created by PB-KM. The following sections report the experimental results collected by applying PB-KM/PB-RS to the four groups of selected datasets. A common point of all the experiments concerns using the GKM++ seeding method both in the first step of the population set-up and in the second step of recombination. ### First Group of Synthetic Datasets (Table 2)

Table 8 shows the experimental results collected when applying PB-KM to all the benchmark datasets reported in Table 2 (entries are preliminary scaled down by the overall maximum). It is worth noting that all these datasets have a success_rate of 0% when clustered by Repeated K-Means together with uniform random seeding, as also documented \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **RKM\({}^{\text{Unif}}\)** & **RKM\({}^{\text{KM++}}\)** & **RKM\({}^{\text{GKM++}}\)** \\ \hline SSE\({}_{\text{min}}\) & 7.44 & 6.74 & 6.74 \\ CI\({}_{\text{min}}\) (SSE) & 1 & 0 & 0 \\ CI\({}_{\text{min}}\) & 1 & 0 & 0 \\ SSE\({}_{\text{min}}\) (CI) & 7.44 & 6.74 & 6.74 \\ avg\_CI & 6.58 & 4.17 & 1.62 \\ success\_rate & 0\% & 0.01\% & 5.8\% \\ PET(s) & 103 & 154 & 990 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Clustering experimental results on the A3 dataset.