## 3 Population-Based Clustering Algorithms
### Pg-Km
```
Stream=DataPoint=pStream= (PARALLEL)?Stream_of(dataset).parallel():Stream_of (dataset); DataPoint s=pStream.map(p ->[  int k=p.getCID);//retrieve partition label (centroid index) of p double d=p.distance(centroids[k]); p.setDist(d'd);//store locally to p the squared distance of p to its (nearest) centroid return p; ).reduce(new DataPoint(), (p1,p2)->[ DataPoint ps=new DataPoint(); ps.setDist(p1.getDist()+p2.getDist()); return ps; ] ); return s.getDist();
```

**Algorithm 7** Java function which calculates the \(SSE\) the cost of a given partitioning. The systematic use of the parallelism in PB-KM/PB-RS purposely reduces the time required, e.g., for computing all the distances between the points and associated centroids which, in turn, can significantly reduce the program execution time on a multi-core machine. ## 5 Experimental Framework

For comparison purposes with Recombinator-K-Means, all the synthetic (benchmark) and real-world datasets used in [11; 12], plus others, were chosen to test the behavior of PB-KM/PB-RS. The datasets are split into four groups. The first group (see Table 2) contains some basic benchmark datasets taken from [24], often used to check the clustering capabilities of algorithms based on K-Means. All the datasets come with ground truth centroids and will be processed, as in [11; 12], by scaling down the data entries by the overall maximum. A brief description of the datasets is shown in Table 2.

The A3 dataset comprises 7500 2-d points distributed across 50 spherical clusters. S3 admits 5000 2-d points divided into 15 Gaussian distributed clusters with limited overlap. As discussed in [5; 6], cluster overlapping is the key factor which can favor centroid movement during K-Means refinement, and then the obtainment of an accurate clustering. Dim1024 is an example of a dataset with high-dimensional points. It contains 1024 Gaussian-distributed points in 16 well-separated clusters. Unbalance is made up of 6500 2-d points split into eight Gaussian clusters, articulated in two neatly separated groups of clusters containing 2000 and 100 points, respectively. Birch datasets contain \(10^{5}\) 2-dimensional points distributed into 100 clusters. In particular, Birch1 places its clusters on a 10 \(\times\) 10 grid. Birch2, instead, puts the clusters on a sine curve. Birch1 and Birch2 have spherical clusters of the same size. The synthetic datasets presented in Table 2 can be studied using classical Repeated K-Means and careful seeding. However, in many cases, only an imperfect solution will emerge from the experiments (see Section 5.1). The second group of datasets (see Table 3) includes two real-world datasets taken from the UCI Repository [25]. _Musk_ concerns a molecule identification problem, whether it is musk or not. Although limited in the number of data points, \(N\), and the number of clusters, \(K\), the dataset admits a high number, \(D\), of features (coordinates) per point, which complicates the identification problem. The _MiniBooNE_ dataset, instead, regards a signals identification problem, whether they are neutrinos or background. In this case, the challenge is represented by both high values of \(N\) and \(D\). The two datasets were also used in [14]. In particular, the solutions documented in [14] will be assumed in this paper as \"golden\" solutions, from which ground truth centroids are inferred and used to qualify the correctness of the solutions achieved via PB-KM/PB-RS. For comparison purposes with the results in [14], the two datasets will be processed by first scaling all the data entries via min-max normalization. The third group of datasets (see Table 4) contains three synthetic datasets achieved from [24] whose good clustering does not necessarily follow from the minimization of the \(SSE\) cost (see also [9]). Birch3 (see Figure 1) differs from the regular Birch1 and Birch2 because it admits clusters with a random size and randomly located in the data space. Worms_2d (see Figure 2) is composed of 35 clusters with 2-dimensional data points.