Medoid Silhouette clustering with automatic cluster number selection
Lars Lenssen Erich Schubert
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.