  We study the problem of clustering with relative constraints, where each
constraint specifies relative similarities among instances. In particular, each
constraint $(x_i, x_j, x_k)$ is acquired by posing a query: is instance $x_i$
more similar to $x_j$ than to $x_k$? We consider the scenario where answers to
such queries are based on an underlying (but unknown) class concept, which we
aim to discover via clustering. Different from most existing methods that only
consider constraints derived from yes and no answers, we also incorporate don't
know responses. We introduce a Discriminative Clustering method with Relative
Constraints (DCRC) which assumes a natural probabilistic relationship between
instances, their underlying cluster memberships, and the observed constraints.
The objective is to maximize the model likelihood given the constraints, and in
the meantime enforce cluster separation and cluster balance by also making use
of the unlabeled instances. We evaluated the proposed method using constraints
generated from ground-truth class labels, and from (noisy) human judgments from
a user study. Experimental results demonstrate: 1) the usefulness of relative
constraints, in particular when don't know answers are considered; 2) the
improved performance of the proposed method over state-of-the-art methods that
utilize either relative or pairwise constraints; and 3) the robustness of our
method in the presence of noisy constraints, such as those provided by human
judgement.
