Abstract
The silhouette is one of the most widely used measures to assess the quality of a $k$-clustering of a dataset of $n$ elements, requiring no information beyond the clustering assignment. It is easy to interpret, providing a score to measure the quality of a clustering as a whole or for each element. However, the exact computation of:
- the silhouette of each element of a dataset;
- the global silhouette of the clustering, requires $\Theta(n^2)$ distance calculations, which is extremely prohibitive for massive modern datasets.
Existing approximate methods using $O(n^2)$ distance calculations are heuristics that do not offer provable and controllable guarantees on the quality of their results. We introduce the first rigorous and efficient algorithms to estimate:
- the (local) silhouette of each element of a dataset;
- the (global) silhouette of any metric $k$-clustering.
Our methods, based on sampling, perform $O(nk\varepsilon^{-2}\ln (nk/\delta))$ distance computations, providing estimates with additive error $O(\varepsilon)$ with probability at least $1-\delta$. The parameters $\varepsilon$ and $\delta$ in $(0,1)$ control the trade-off between accuracy and efficiency.
Additionally, we introduce a scalable and distributed design of our methods for the MapReduce and Massively Parallel Computing (MPC) frameworks. Our distributed algorithms use a constant number of rounds and sublinear local memory. Extensive experiments against state-of-the-art approaches demonstrate that our new techniques yield the best trade-off between accuracy and efficiency for both local and global silhouette estimation, scaling efficiently to massive datasets where exact computation is impractical.
Blogger's Review: This research opens new perspectives in silhouette estimation by introducing effective sampling algorithms and distributed computing frameworks, providing practical solutions for handling large datasets. It enhances the efficiency of clustering quality assessment and lays a foundation for future related studies. The effective error control mechanism achieves a good balance between accuracy and efficiency, with broad application prospects.