  Clustering is considered a non-supervised learning setting, in which the goal
is to partition a collection of data points into disjoint clusters. Often a
bound $k$ on the number of clusters is given or assumed by the practitioner.
Many versions of this problem have been defined, most notably $k$-means and
$k$-median.
  An underlying problem with the unsupervised nature of clustering it that of
determining a similarity function. One approach for alleviating this difficulty
is known as clustering with side information, alternatively, semi-supervised
clustering. Here, the practitioner incorporates side information in the form of
"must be clustered" or "must be separated" labels for data point pairs. Each
such piece of information comes at a "query cost" (often involving human
response solicitation). The collection of labels is then incorporated in the
usual clustering algorithm as either strict or as soft constraints, possibly
adding a pairwise constraint penalty function to the chosen clustering
objective.
  Our work is mostly related to clustering with side information. We ask how to
choose the pairs of data points. Our analysis gives rise to a method provably
better than simply choosing them uniformly at random. Roughly speaking, we show
that the distribution must be biased so as more weight is placed on pairs
incident to elements in smaller clusters in some optimal solution. Of course we
do not know the optimal solution, hence we don't know the bias. Using the
recently introduced method of $\eps$-smooth relative regret approximations of
Ailon, Begleiter and Ezra, we can show an iterative process that improves both
the clustering and the bias in tandem. The process provably converges to the
optimal solution faster (in terms of query cost) than an algorithm selecting
pairs uniformly.
