## 3 Population-Based Clustering Algorithms
### Pg-Km
Algorithm 5 shows the recombination step of PB-RS. An initial configuration of \(K\) centroids is set up by applying GKM++ to population \(\wp\). The corresponding partition of dataset points is then built and its \(SSE\) cost is defined as the current cost. Then, T swap iterations are executed. The value of T depends on the dataset and the number of clusters \(K\). ```
\(\text{cand}\leftarrow\)GKM++(\(\wp\))  partition \(X\) data points according to cand cost\(\leftarrow\)SSE(\(X\)) repeat T times save cand cand\(\leftarrow\)swap(cand), that is: cs\(\leftarrow\)pj, pj\(\in\wp\), s\(\leftarrow\)unif_rand(1..K), j\(\leftarrow\)unif_rand(1..J * K) refine cand\({}^{\prime}\) by a few K-Means iterations (e.g., 5) new_cost\(\leftarrow\)SSE(cand, \(X\)) if(new_cost\(<\)cost) accept cand\({}^{\prime}\), cand\(\leftarrow\)cand\({}^{\prime}\) cost\(\leftarrow\)new_cost \(\}\) else\(\mid\) restore saved cand and its previous partitioning \(\}\) check the accuracy of candBest by further clustering indexes. ```
**Algorithm 5** The PB-RS recombination step. At each swap iteration, a centroid in the current configuration (_cand_) is randomly selected and replaced by a randomly chosen candidate point taken from the population. It is worth noting that the population remains unaltered during the swap iterations under PB-RS. The initial selection of centroids via GKM++ triggers mutation and crossover operations, respectively, represented by swap operation and K-Means refinement. The cost of the first step of PB-RS can be summarized as \(O(J(KSND+KND+TNKD\)\([KNiO+\tau K+(1-\tau)(N+K)]))\), where for each of the \(J\) solutions, first the cost of GKM++ is accounted, then the cost of partitioning the dataset according to the initial centroids is considered; after that, the cost of the \(T\) swap iterations is added. \(i\) is the small number of iterations of K-Means executed at each swap to optimize the new centroid configuration and \(\tau\) is the probability of accepting the new centroid configuration. If the new configuration is rejected, \(N+K\) is the cost of restoring the previous centroids and associated partitioning. The cost of the second step of PB-RS is similar to that of the first step by considering one single run of Random Swap (\(J~{}=~{}1\)) and that the single seeding of GKM++ is fed from the population and costs \(JK^{2}SD\). The number of swap iterations, \(T\), is expected to depend on the particular adopted dataset. With respect to the standard Random Swap operation [8; 9], PB-RS recombination tends to move more \"directly\", experimentally confirmed, toward a good clustering solution by avoiding many unproductive iterations. This is because at each swap iteration, only a candidate centroid in the population, not a point in the whole dataset, is considered for the replacement of a centroid in the current vector of centroids. ## 4 JAVA Implementation Notes

The realized Java implementation of PB-KM was designed to tackle the important task of facilitating the parallel execution of recurring operations. These include the partitioning and centroids update steps of K-Means (refer to Algorithm 1), the computation of the SSE cost, and the fundamental operations of GKM++, among others. To achieve this, parallel streams and lambda expressions [9; 15; 16; 20] were leveraged. A parallel stream is orchestrated by the fork/join mechanism, allowing for arrays/collections like datasets, populations, centroid vectors and so forth, to be divided into multiple segments. Separate threads are then spawned to process these segments independently, and the results are eventually combined. Lambda expressions serve as functional units specifying operations on a data stream concisely and efficiently. While the use of such popular parallelism can be straightforward in practical scenarios, it necessitates caution from the designer to avoid using shared data in lambda expressions, as this could introduce subtle data inconsistency issues, rendering the results meaningless.