# Performance of Parallel K-Means Algorithms in Java
## 2 Background on K-Means
### About the Initialization Methods  
Different initialization methods have been proposed and evaluated for K-Means [3; 17; 18]. Each method is characterized by its computational complexity and its ability to enable an \"optimal\" clustering solution. Both stochastic and deterministic initialization methods were studied. A deterministic method can generate a (hopefully good) final solution after just one execution run. Generally speaking, initial centroids should be chosen so as to  
1. exclude outlier points;
2. be located in regions of high density of local data points;
3. be far from each other so as to avoid, e.g., (since \(K\) is fixed) splitting a homogeneous dense cluster, thus degrading the clustering accuracy. Of course, although it is easy and efficient to also apply to large datasets, the random initialization method addresses none of the abovementioned points. As a consequence, the quality of the generated clustering can be poor. Nonetheless, the reason why the random initialization method is most often used, is tied to the fact that by repeating the execution of K-Means many times, a \"good\" clustering solution eventually emerges among the various achieved solutions, as one which minimizes the objective function. Let \(D\left(x_{i}\right)\) denote the minimal distance of the point \(x_{i}\) to existing centroids (during the initialization process, the number of centroids \(L\) increases, gradually, from 1 to \(K\)). The K-Means++ method starts by assigning a random point in the dataset as the first centroid \(c_{1}\) (\(L=1\)). Then, a new point \(x_{j}\) can be chosen as the next centroid with probability  
\[p\left(x_{j}\right)=\frac{D\left(x_{j}\right)^{2}}{\sum_{i=1}^{N}D\left(x_{i} \right)^{2}}\]  
After that \(L\) is incremented, and the process is continued until \(L=K\) centroids are defined. K-Means++ is an example of an initialization method that tries only to choose centroid points in the dataset that are far from each other (point 3. above). The method is stochastic because, since the use of probabilities, it necessarily has to be repeated multiple times to generate a stable initialization. A notable example of an initialization method which is robust to outliers and addresses all the above-mentioned tree points, is ROBIN (ROBust INitialization) [3; 16], which can  
Figure 1: Sequential operation of K-Means. be turned to behave deterministically. ROBIN is based on the Local Outlier Factor (\(LOF\)), originally introduced by [PERSON] et al. in [PERSON] et al. (2019) which can be assigned to points of the dataset. \(LOF\) takes into account a density notion around a given point and among close points and permits to filter out outliers during the centroid initialization. The modus operandi of ROBIN is summarised in Figure 2, whereas the formal definition of \(LOF\) is shown in Figure 3.  
The operation of the ROBIN algorithm in Figure 2 and the \(LOF\) definition in Figure 3 depend on the parameter \(mp\), that is the _minimum number of points_ in the \"nearest\" neighborhood of a point \(x_{i}\). Such a parameter is directly related to the \(k\)-_distance-neighborhood_ introduced in [PERSON] et al. (2019). Upon \(mp\) is based the composition of the neighborhood set \(N_{mp}(x_{i})\) which can be established when a new nearest point to \(x_{i}\) is met such that at least \(mp\) points were previously already found to be closer to \(x_{i}\). Hence, the cardinality of the neighborhood set \(\left|N_{mp}(x_{i})\right|\) is necessarily expected to be \(\geq mp\). As it emerges from Figure 3, the \(LOF\) value takes into account not only the density of a point \(x_{i}\), but also the _reciprocal_ density of points _near_ to \(x_{i}\). In fact, for not outlier points, the density of \(x_{i}\) and that of neighbor points should be almost equal. Therefore, a point is a candidate for the next centroid, provided its \(LOF\) is _close_ to \(1\). Values of \(LOF\gg 1\) denote outliers. As in [PERSON] et al.