# Performance of Parallel K-Means Algorithms in Java
## 4 Experimental Results  
The Java-based K-Means (KM) algorithms were thoroughly checked on different datasets, real-world or synthetic. It was ensured that, starting from the same initial centroids, the four versions of the developed solutions, namely the Serial Stream KM (\(SSKM\)), the Parallel Stream KM (\(PSKM\)), the Standalone Theatre KM (\(STKM\)) and the Parallel Theatre KM (\(PTKM\)), always and exactly generate the same final centroids and with the same number of convergence iterations. For demonstration purposes, the following considers the US Census Data 1990, downloaded from the UCI Machine Learning Repository [24]. The dataset (see also Table 1) contains \(N=2458285\) data records each one with \(D=68\) numerical categorial attributes. Different clustering solutions were studied for the chosen dataset (see the \(K\) number of assumed centroids in the Table 1), under the deterministic version of the ROBIN initialization method (see Section 2.1). Performance measurements are documented in the author's preliminary work (ICICT 2022, Springer LNNS, ISSN: 2367-3370) using some synthetic datasets when the number N of data points increases and the random initialization method (see Section 2) is adopted. All the execution experiments were carried out on a Win10 Pro, Dell XPS 8940, Intel i7-10700 (8 physical cores which with the hyperthreading give support to 16 threads), [EMAIL_ADDRESS] GHz, 32 GB Ram, Java 17 with the default JVM configuration parameters (e.g., 4 GB for the maximum exploitable heap memory size). Table 1 collects the values of some basic parameters. It is useful to note that the value \(P=16\) is implicitly and automatically exploited by Java when working with \(PSKM\). Performance comparison was also explicitly set for the case of PTKM. Some preliminary runs were devoted to studying the K value of K-means, which can minimize the SSD cost (sum of squared distances objective function--see Section 2). Figure 9 depicts the so-called \"Elbow\" curve, i.e., the SSD vs.K, which is often used to understand the values of K to adopt, and Figure 10 shows the number of emerged iterations required for convergence, i.e., it vs.K. The execution performance was then investigated by varying the K value from 10 to 120, as shown in Table 2.  
For the purpose of the performance comparison work, documented in Table 2, the deterministic pre-selection of the initial centroids of the ROBIN method was preferred. In particular, the initial centroids, for each value of \(K\), were saved on disk and reused (by re-loading) without regenerating them when executing the various versions of the K-Means algorithm. As in [19], it emerged that the determination of the \(LOF\) factor for outlier data points, is not much sensitive to the value of \(MP\) (see Table 1). The value \(MP=10\) was used. Table 2 reports the measured serial elapsed time (\(SET\)) and the parallel elapsed time (\(PET\)) for the various versions of K-Means and for the chosen values of \(K\) which minimize the \(SSD\) cost (see Figure 9). Each measure is the average of five runs which, although the deterministic evolution of K-Means due to the adopted ROBIN initialization method, are required to smooth out uncertainties of the underlying Operating System. As one can see from Table 2, the parallel Stream-based solution (\(PSKM\)) is capable of delivering a good execution performance, with the burden of choosing the parallelism-degree, splitting the dataset in segments and processing them concurrently by separate threads is completely left to the Java runtime system. The emerged speedup for the Stream-based solutions, that is the ratio between the \(SET_{SSKM}\) and the \(PET_{PSKM}\), is shown in the column \(Speedup_{S}\) and it reaches a value about 11 in the case \(K=80\). The corresponding observed times when the Theatre-based solutions are used, are indicated in the second part of Table 2, confirming a speedup of 10.63 in the scenario with \(K=120\).