Medoid Silhouette clustering with automatic cluster number selection
This work addresses the problem of efficient clustering validation for data scientists, but it is incremental as it builds on existing Silhouette and PAM methods.
The paper tackles the challenge of evaluating clustering results by proposing a medoid-based variant of the Silhouette measure, which achieves a 10464× speedup on real data with 30000 samples and k=100 compared to the original PAMMEDSIL algorithm.
The evaluation of clustering results is difficult, highly dependent on the evaluated data set and the perspective of the beholder. There are many different clustering quality measures, which try to provide a general measure to validate clustering results. A very popular measure is the Silhouette. We discuss the efficient medoid-based variant of the Silhouette, perform a theoretical analysis of its properties, provide two fast versions for the direct optimization, and discuss the use to choose the optimal number of clusters. We combine ideas from the original Silhouette with the well-known PAM algorithm and its latest improvements FasterPAM. One of the versions guarantees equal results to the original variant and provides a run speedup of $O(k^2)$. In experiments on real data with 30000 samples and $k$=100, we observed a 10464$\times$ speedup compared to the original PAMMEDSIL algorithm. Additionally, we provide a variant to choose the optimal number of clusters directly.