COBRAS: Fast, Iterative, Active Clustering with Pairwise Constraints
  Constraint-based clustering algorithms exploit background knowledge to
construct clusterings that are aligned with the interests of a particular user.
This background knowledge is often obtained by allowing the clustering system
to pose pairwise queries to the user: should these two elements be in the same
cluster or not? Active clustering methods aim to minimize the number of queries
needed to obtain a good clustering by querying the most informative pairs
first. Ideally, a user should be able to answer a couple of these queries,
inspect the resulting clustering, and repeat these two steps until a
satisfactory result is obtained. We present COBRAS, an approach to active
clustering with pairwise constraints that is suited for such an interactive
clustering process. A core concept in COBRAS is that of a super-instance: a
local region in the data in which all instances are assumed to belong to the
same cluster. COBRAS constructs such super-instances in a top-down manner to
produce high-quality results early on in the clustering process, and keeps
refining these super-instances as more pairwise queries are given to get more
detailed clusterings later on. We experimentally demonstrate that COBRAS
produces good clusterings at fast run times, making it an excellent candidate
for the iterative clustering scenario outlined above.
