# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 1 Introduction  
Clustering is a fundamental and widely studied problem in machine learning and in computational complexity as well. Intuitively, the goal is to partition a given set of points \(X\) (data set) into \(k\) clusters, each cluster corresponding to a group of \"similar\" data according to some underlying distance function \(d(\cdot)\). Though most of the clustering problems are NP-hard in the worst case, for real data, certain (relatively simple) heuristics seem to perform quite well. One theoretical justification to support this empirical observation is that \"real\" instances have some \"nice\" distribution, and some _polynomial-time_ algorithms come with the guarantee that, on these inputs, they return _optimal_ solutions. Along these lines, one successful concept is that of _stability_ of the input, meaning that a \"small\" perturbation of the input does not change the optimal solution (though it may change its value).  
Quite surprisingly, for a rather general class of clustering problems, the following very _simple_ algorithm guarantees _exact_ solutions in stable instances in _polynomial-time_[1, 2, 3] (see also [4] for a nice introduction). Roughly speaking, this algorithm first computes a (_minimum) spanning tree_ over the data pairwise distances or dissimilarities, and then removes a _suitable_ subset of edges to obtain the optimal \(k\)-clustering. The latter step amounts to identify the \(k-1\) edges whose removal partitions the spanning tree into \(k\) clusters (the nodes of the resulting forest) in order to minimize the underlying cost function of the clustering problem (the exact cost function depends on how we define the \"center\" of the clusters and on the distances of the points in the cluster to its center).  
The implicit assumption is that the algorithm is provided with the _correct_ pairwise dissimilarity/distances metric between all pairs of data points. In this work, we take a step further and consider the natural setting where we can only _compare_ distances and these comparisons are also _noisy_. Furthermore, by accessing some type of expensive (expert)oracle, we can make sure that certain comparisons are _correctly_ reported, though these operations are inherently more _expensive_ and thus we would like to use _as few as possible_. In a nutshell, our work considers and combines the following three aspects that are often present in practical machine learning approaches:  
* Using only _ordinal_ information;
* Dealing with _noisy_ data;
* Allowing _expensive_ operations to remove errors.  
This situation arises, for example, in semi-active learning approaches where the pairwise dissimilarity between objects (data points) is _evaluated_ by _humans_ via simple comparison queries (see, e.g., [5; 6; 7] and references therein). These are inherently subject to erroneous evaluations. Moreover, very often, the task is to _compare_ objects and their pairwise dissimilarities. Such queries can also be of varying difficulty and thus more or less informative/costly. It is therefore natural to ask the following questions:  
_Which guarantees are still possible under such model?_  
_What trade-offs between expensive and non-expensive (noisy) operations still allow for finding optimal solutions?_