Clustering with a Reject Option: Interactive Clustering as Bayesian
  Prior Elicitation
  A good clustering can help a data analyst to explore and understand a data
set, but what constitutes a good clustering may depend on domain-specific and
application-specific criteria. These criteria can be difficult to formalize,
even when it is easy for an analyst to know a good clustering when she sees
one. We present a new approach to interactive clustering for data exploration,
called \ciif, based on a particularly simple feedback mechanism, in which an
analyst can choose to reject individual clusters and request new ones. The new
clusters should be different from previously rejected clusters while still
fitting the data well. We formalize this interaction in a novel Bayesian prior
elicitation framework. In each iteration, the prior is adapted to account for
all the previous feedback, and a new clustering is then produced from the
posterior distribution. To achieve the computational efficiency necessary for
an interactive setting, we propose an incremental optimization method over data
minibatches using Lagrangian relaxation. Experiments demonstrate that \ciif can
produce accurate and diverse clusterings.
