# Heterogeneous Distributed Big Data Clustering on Sparse Grids
## 6 Results
### Clustering Quality and Parameter Tuning  
This work mostly focuses on the performance of our sparse grid clustering approach. Nevertheless, to make our evaluation more realistic, we tuned the clustering parameters of our node-level runs for (nearly) optimal clustering quality. For a more detailed discussion of the achievable level of quality, we refer to prior work which compared sparse grid clustering to other clustering algorithms [21]. A comparison of the sparse grid density estimation to other density estimation methods is available as well [30].  
To assess the quality, we used the adjusted Rand index (ARI) which compares two cluster mappings. Because we know the mapping of data points to clusters of each of our synthetic datasets, these reference cluster mappings were compared to the output of the sparse grid clustering algorithm. The calculated ARI of the node-level experiments is shown in Table 4. These results show that we can nearly perfectly reconstruct the clusters of both datasets with ten clusters. The datasets with 100 clusters are more challenging and would require slightly larger grids for further improvements.  
Even though we know the clusters we want to detect, we still need to find parameter values for the sparse grid clustering algorithm that lead to the desired cluster mapping. Some parameters can be chosen conservatively and then adjusted manually for a higher quality clustering or improved performance. As an initial guess for the sparse grid discretization level, it can be chosen so that the size of the grid is equal to a fraction of the dataset. \(k\) and \(\epsilon\) can be conservatively chosen with 10 and \(10^{-6}\), respectively. However, \(\lambda\) and \(t\) depend on each other and have no obvious default values. We therefore, employ a parameter tuning approach to find values for these two parameters.  
During parameter tuning, we first select a value for the regularization parameter \(\lambda\) and then search for the best pruning threshold \(t\). For each value of \(\lambda\) and \(t\), we make use of the available reference clustering and compute the ARI which we maximize. As search strategies, we implemented an approach with two nested binary searches. The overall best parameter combination encountered is returned as the result.  
The ARI requires a reference solution which, of course, it not available for yet unsolved problems. However, this basic parameter tuning approach can be applied more generally if an application-dependent quality metric is provided to assess a computed clustering. Note that in contrast to other data mining tasks such as regression, there is no well-defined solution independent of the application context. Therefore, this is not a limitation of the sparse grid clustering approach.  
To speed up parameter tuning, our sparse grid clustering implementation allows for reusing of the \(k\)-nearest-neighbor graph and calculated density estimations. As the \(k\)-nearest-neighbor graph is the same independent of all parameters, it can be calculated once overall. Moreover, the density estimation changes only if \(\lambda\) is changed. Thus, the density estimation can be reused while an optimal value for \(t\) is searched. Only the comparably cheap graph pruning operation and the connected component search are performed at every parameter tuning step.