## 2 Related Work
### Lloyd's K-Means  
Algorithm 1 illustrates the operation of classical K-Means. In step 1, the data points of the dataset to assume as the initial centroids are established by a seeding procedure (e.g., uniform random, see also Table 1 of basic notations). In step 2, the data points are partitioned according to current centroids. In particular, each point \(x_{i}\) is assigned to the cluster \(C_{j}\), of which the representative centroid, \(\mu_{j}\), is nearest to \(x_{i}\):  
\[\mu_{j}\ =\ nc(x_{i}),\ j\ =\ argmin_{1\leq h\leq K}(d(x_{i},\mu_{h}))\]  
where \(d(x_{i},\mu_{h})\) expresses the Euclidean distance between \(x_{i}\) and \(\mu_{h}\) data points. In step 3, centroids get updated as the mean of the clusters' belonging points:  
\[\mu^{\prime}_{j}\ =\ \frac{1}{\left|C_{j}\right|}\sum_{x_{i}\in C_{j}}x_{i}\]  
Steps 2 and 3 are re-executed until a stop condition holds. For example, when the updated centroids \(\{\mu^{\prime}_{j}\}_{j=1}^{K}\) practically \"coincide\" (according to a certain numeric tolerance) with the previous ones \(\{\mu_{j}\}_{j=1}^{K}\), the K-Means exits for reached convergence, otherwise, the \begin{table}
\begin{tabular}{c l} \hline \hline
**Symbol** & **Description** \\ \hline \(N\) & number of data points (vectors) \(x_{i}\) in the dataset \(X\) \\ \(D\) & number of dimensions (coordinates or features) for each data point \\ \(K\) & number of clusters/centroids \\ \(d(x_{i},x_{j})\) & Euclidean distance between data points \(x_{i}\) and \(x_{j}\) \\ \(C_{1}\ldots C_{K}\) & partition clusters \\ \(\mu_{1}\ldots\mu_{K}\) & representative centroids of clusters \\ \(nc(x_{i})\) & nearest centroid to data point \(x_{i}\) \\ \(L\) & the number of currently defined centroids in a seeding method \\ \(D(x_{i})\) & minimal distance of \(x_{i}\) to the currently existing centroids \\ \(SSE\) & Sum-of-Squared Errors objective function \\ \(nMSE\) & normalized mean of \(SSE\), also referred to as distortion \\ \(Unif\) & uniform random seeding method \\ \(KM++\) & K-Means++ seeding method \\ \(GKM++\) & Greedy-K-Means++ seeding method \\ \(S\) & number of attempts in GKM++ for identifying the next centroid \\ \(CI\) & Cluster Index—an external measure of clustering accuracy \\ \(<\!C_{j},P_{j}\!\!>\) & a solution of a clustering algorithm, i.e., a pair of a centroids vector and corresponding partition labels of clusters belonging data points \\ \(PB-KM\) & proposed Population-Based K-Means clustering algorithm \\ \(PB-RS\) & proposed Population-Based Random Swap clustering algorithm \\ \(\wp\) & population of \(J\ast K\) centroids in PB-KM/PB-RS algorithms \\ \(J\) & number of “best” solutions initially put in the \(\wp\) \\ \(R_{1}\) & number of repetitions of K-Means in the 1 st step of PB-KM \\ \(R_{2}\) & number of repetitions of K-Means in the 2 nd step of PB-KM \\ \(T\) & number of iterations of Random Swap in the 1 st step of PB-RS, for defining each of the J candidate population \\  & solutions; also the number of iterations of Random Swap in the 2 nd step of PB-RS for achieving a careful solution \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Basic notations. stop condition occurs after the maximum number of iterations of steps 2 and 3 is finished. In any case, the new centroids \(\{\mu^{\prime}_{j}\}_{j=1}^{K}\) become the current centroids, \(\{\mu_{j}\}_{j=1}^{K}\). ```
Input: the dataset \(X\) and the number of clusters \(K\). Output: final centroids and corresponding partitions. 1. Initialization. Use some seeding method (e.g., uniform random) to choose \(K\) data in \(X\) as initial centroids. 2. Partitioning. Assign data points of \(X\) to clusters according to the nearest centroid rule. 3. Update. Redefine centroids as the mean points of the clusters resulting from step 2. 4. Check termination. If the termination condition does not hold, repeat from 2.