## 3 Population-Based Clustering Algorithms
### Pg-Km
### Time Efficiency of PB-KM

The computational efficiency of the developed tools was assessed, in a case, using the PB-KM recombination step on the Worms_64d dataset (see Table 4), via the GKM++ seeding method, with \(\mathrm{J}\ =\ 40\) and \(\mathrm{R}_{2}\ =\ 200\) repetitions, separately in parallel (the parameter PARALLEL set to true) and sequential \(\mathrm{(PARALLEL\ =\ false)}\) modes. The total elapsed time tET (in msec) for the serial (tET\({}^{S}\)) and parallel (tET\({}^{P}\)) case needed by PB-KM recombination to complete were measured, together with the total number of executed K-Means iterations (respectively tIT\({}^{S}\), tIT\({}^{P}\)), as reported in Table 3.4

From the data in Table 10, the average elapsed time per iteration was computed as \(av\mathrm{ET}_{it}^{S}\ =\ \frac{t\mathrm{ET}^{S}}{t\mathrm{IT}^{S}}\ =\ 292.73\) and \(av\mathrm{ET}_{it}^{P}\ =\ \frac{t\mathrm{ET}^{P}}{t\mathrm{IT}^{P}}\ =\ 43.70\), and the speedup was estimated as

Table 3.5

## 6 Conclusions

This paper proposes two evolutionary-based clustering algorithms: Population-Based K-Means (PB-KM) and Population-Based Random Swap (PB-RS). The two algorithms were inspired by the Recombinator-K-Means [11; 12] and the Genetic Algorithm of [PERSON] [10], plus the use of the careful seeding ensured by the Greedy K-Means++ (GKM++) method [11; 14]. However, PB-KM and PB-RS are based on a simpler, yet effective, approach which rests on two steps. In the first step, a population of J candidate \"best\" centroid solutions is created. The second step recombines the population's centroids toward obtaining a careful solution. This is achieved in PB-KM through a number of independent repetitions of Lloyd's K-Means [2; 3; 4], and in PB-RS by a certain number of iterations of Random Swap [8; 9]. In both cases the starting point is a centroid configuration achieved by applying GKM++ to \begin{table}
\begin{tabular}{c c} \hline
**Worms\_64d** & **PB-KM, 2 nd Step, J=40, \(\mathrm{R}_{2}\)=100** \\ \hline tET\({}^{S}\) (ms) & 4,405,325 \\ tIT\({}^{S}\) & 15,049 \\ tET\({}^{P}\) (ms) & 650,622 \\ tIT\({}^{P}\) & 14,887 \\ \hline \end{tabular}
\end{table} 
Table 10: The sequential and parallel execution of PB-KM recombination on Worms\({}_{64d}\). (8 physical cores). Figure 16: CI vs. time for the UrbanGB dataset. the population. Refinement of the initial solution is then controlled by partitioning the points of the dataset and moving toward minimizing the _Sum of Squared Errors_ (SSE) cost. A key factor of PB-KM and PB-RS concerns their implementation in Java, which is based on parallel streams [9; 15; 16], which enables the exploitation of the parallel computing potential of modern multi/many-core machines. The paper documents the reliable and efficient clustering capabilities of PB-KM and PB-RS by applying them to a collection of challenging benchmark and real-world datasets. Ongoing and future work aims to address the following points. First, it aims to experiment with the two developed algorithms for clustering sets [20; 29] and more in general categorical and text-based datasets. Second, it aims to port the implementations on top of the efficient Theatre actor system [30], which allows for better control and exploitation of the parallel resources of a multi/many-core machine. Third, the aim is to adapt PB-KM by replacing Lloyd's K-Means with the [PERSON] and Wong variation of K-Means [31; 32]. The idea is to experiment with an incremental technique which constrains the switching of a data point from its source cluster to a destination cluster also on the basis of its Silhouette coefficient [33]. The goal is to favor the definition of well-separated clusters. The fourth aim is to compare the two developed algorithms to affinity propagation clustering [34] algorithms, e.g., for studying the seismic consequences caused by earthquakes [35]. In addition, the influence of the method about point distributions in the hypersphere [36] on our described clustering work deserves particular attention. Conceptualization, L.N. and F.C. ; Methodology, L.N.