Introducing the Converse k-clustering Problem

In this paper we introduce the converse k-clustering problem as an alternative partitional clustering model. Partitional clustering is a traditional category of clustering methods, where the general formulation is to produce a given k number of clusters that minimize some compactness objective. Since the parameter k is often hard to determine in advance, we argue that in many cases converse k-clustering can be a more appropriate formulation. Given a compactness threshold as constraint, converse k-clustering minimizes the number of clusters k. Such compactness constraints, such as maximum diameter, can be intuitively specified based on domain knowledge in many real world applications. In the paper we also show how conventional combinatorial optimization techniques, such as minimum clique partition, can be adapted to solve converse k-clustering.