Clustering to the Fewest Clusters Under Intra-Cluster Dissimilarity Constraints

This paper introduces the equiwide clustering problem, where valid partitions\nmust satisfy intra-cluster dissimilarity constraints. Unlike most existing\nclustering algorithms, equiwide clustering relies neither on density nor on a\npredefined number of expected classes, but on a dissimilarity threshold. Its\nmain goal is to ensure an upper bound on the error induced by ultimately\nreplacing any object with its cluster representative. Under this constraint, we\nthen primarily focus on minimizing the number of clusters, along with potential\nsub-objectives. We argue that equiwide clustering is a sound clustering\nproblem, and discuss its relationship with other optimization problems,\nexisting and novel implementations as well as approximation strategies. We\nreview and evaluate suitable clustering algorithms to identify trade-offs\nbetween the various practical solutions for this clustering problem.\n