## 2 Related Work
### Centroids Initialization Methods  
As has been pointed out, e.g., in [5; 6; 7], initial centroids should be defined in such a way to not coincide with outliers or noise data points. In addition, centroids should be far away from one another. This requirement avoids splitting a big real cluster into multiple smaller clusters. Different seeding methods for the initialization of centroids are defined in the literature. A few of these methods are described in the following. \(Unif\). The uniform random seeding is the default method K-Means and Random Swap use. Centroids are initialized through a uniform random selection of \(K\)_distinct_ points of the dataset \(X\):  
\[\{\mu_{j}\gets x_{i},\ i\ =\ unif\_rand(1..N)\}_{j\ =\ 1}^{K}\]  
\(Unif\) is simple to apply, but it does not guarantee the properties mentioned above of centroids are fulfilled. Only when centroids are selected near the optimal positions, the clustering solution delivered by K-Means locates close to the optimal one. Consequently, using K-Means with \(Unif\) seeding typically requires the algorithm to be repeated a certain number of times (Repeated K-Means or K-Means with Restarts). The more the independent repetitions are, the higher the chance of finding a solution near the optimal one is. In any case, if \(R\) are the repetitions of the K-Means, the solution that minimizes the \(SSE\) objective cost is identified as the \"best\" one among the \(R\) runs. Let, in the following, \(D(x_{i})\) be the minimal distance of point \(x_{i}\) from the currently defined \(L\) centroids, \(1\leq L\leq K\). \(Maximin\). The first centroid is established by selecting a point in the dataset by uniform random. Each subsequent centroid is a point \(x_{i}\in X\) with maximal \(D(x_{i})\) from the currently defined centroids. The method is continued until all the \(K\) centroids are defined. Similarly to \(K\)_-Means++_ (see below), the method tends to define centroids far away from one another and with a similar linear computational cost (\(O(KND)\)). \(K\)_-Means++_. This seeding method [18] initializes centroids incrementally and probabilistically, as shown in Algorithm 2. ```
1. Establish the first centroid through a uniform random selection: \(\mu_{1}\gets x_{j},\ j\gets unif\_rand(1..N),\ L\gets 1\)
2. For each point \(x_{i}\), define the probability \(\pi(x_{i})\) of being chosen as the next centroid as: \(\pi(x_{i})\ =\ \frac{D(x_{i})^{2}}{\sum_{i=1}^{N}D(x_{i})^{2}}\) Use a random switch based on the newly computed values of \(\{\pi(x_{i})\}_{i=1}^{N}\), for choosing a point \(x^{*}\in X\), not previously selected, as the next centroid \(L\gets L+1,\ \mu_{L}\gets x^{*}\)
3. If \(L<K\), repeat from step 2. ```  
**Algorithm 2** The K-Means++ seeding method. _K-Means++_ is known to be a good seeding method. It tends to distribute the centroids in the data space more evenly, ensuring that they are located far away from each other. _Greedy K-Means++_. This method is a refinement of \(K\)_-Means++_[11; 12; 14]. Its operation is illustrated in Algorithm 3. A uniform random choice in the dataset defines the first centroid. From the second centroid onward, \(S\) attempts are executed to ensure the next candidate centroid is not only distinct and far away from the already chosen points but will also contribute with a minimal cost increment (the greedy step) in the centroid configuration. As suggested in [11], in our work too, the adopted value of the parameter \(S\) is \(\lfloor 2+logK\rfloor\), which represents a trade-off between careful seeding and the required computational cost \(O(KSND)\). It is worth noting that, although the improved seeding, GKM++ has a greater computational cost than K-Means++ and, unfortunately, it cannot guarantee that the chosen centroids hit the optimal positions. However, as an important benefit confirmed experimentally, some centroids (\"_exemplars_\"), in different configurations, can be positioned close to ground truth centroids.