# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 4 Same Cluster Queries
### An Algorithm Using Few SCQs
#### 4.2.1 The Algorithm  
We first observe that Corollary 1, in addition to the condition used to simulate same-cluster queries in Lemma 9, implies another useful property that we can use to reduce the number of high-cost queries. Intuitively, under the same conditions of Lemma 9, we have that every point is closer to all points in its own cluster than to any of the points outside. Corollary 3: _For any \(\gamma\)-perturbation-stable metric space \((X,d)\) that has \(\gamma\)-radius optimal clusters, with \(\gamma\geq 2\), the following holds. For every optimal cluster \(C^{*}\), every \(x,y\in C^{*}\) and \(z\
otin C^{*}\), it holds that \(d(x,y)<d(x,z)\)._  
Proof. : Let \(x,y,z\) be arbitrary points of \(X\), with \(x,y\) in the same cluster \(C^{*}\) with centroid \(c^{*}\). Then, we have that  
\[d(x,y)\leq(\gamma-1)d^{(X)}_{\min}\leq(\gamma-1)d(x,c^{*})<d(x,z)\]  
where the last inequality is given by Corollary 1. Remark 6 (main intuition). : _Corollary 3 means that, in order to identify a cluster \(C^{*}_{i}\), instead of its optimal centroid, we can simply determine an arbitrary point \(x_{i}\) and assign this point as a (representative) centroid of that cluster \(C^{*}_{i}\), for all \(k\) clusters. Then, we can map every other points to the closest (representative) centroid._  
The above result suggests the following natural algorithm (the implementation of the single steps is described below together with the analysis): \begin{tabular}{l l} \hline \hline \multicolumn{2}{|l|}{**Coupon-Collector Clustering:**} \\
1. & Extract random points from \(X\) until we obtain one centroid for each cluster; \\
2. & Having one centroid per cluster, extract an additional \(m\) random points to \\  & get \(C=\Theta(\log n)\) centroids per cluster; \\
3. & Map all the remaining points in \(X\) to the closest centroid. \\ \hline \hline \end{tabular}   
The idea is to pick random points from \(X\) until we have a different centroid for each cluster, and then simply map all the remaining points to the closest centroid. In the first step, for every new point we extract, we use the (exact) same-cluster query \(SCQ_{H}\) to determine whether this point belongs to one of the clusters for which we already have found one point. Analysis of the First Step  
The analysis is based on the well-known Coupon Collector's Problem (CCP) [32; 33]. In this step, we can safely extract points _with_ a replacement as in the CCP problem (see Lemma 11 below) since extracting the same point more than once has no effect on the stopping condition (all clusters have at least one point, and having more than one point or the same point several times does not affect this step). Lemma 11: _Consider the process in which we repeatedly draw a coupon from a finite collection of \(k\) coupons according to a probability distribution \(\mathbf{p}=(p_{1},p_{2},\ldots,p_{k})\), meaning that, at every step, \(p_{h}\in(0,1)\) is the probability of picking the \(h\)-th coupon. Then, the following bounds on the expected number of steps \(\mathcal{C}(\mathbf{p})\) required to collect at least \(c\) copies of each of the \(k\) coupons are known (for \(p_{1}\leq p_{2}\leq\cdots\leq p_{k}\)). For the (approximately) uniform case, that is, \(p_{i}=\Theta(\frac{1}{k})\),_  
\[\mathcal{C}(\mathbf{p})=\Theta(k\log k)\]and, more in general, the following upper bounds hold (see [32])_  
\[\mathcal{C}(\mathbf{p})\leq\frac{H_{k}}{p_{1}}=O(\frac{\log k}{p_{1}});\qquad \mathcal{C}(\mathbf{p})\leq\sum_{j=1}^{k}\frac{1}{j\cdot p_{j}};\qquad\mathcal{ C}(\mathbf{p})\leq\sum_{j=1}^{k}1/\left(\sum_{\ell=1}^{j}\frac{1}{p_{\ell}}\right)\]  
_where \(H_{k}\) is the \(k\)-th harmonic number._  
**Lemma 12**. : _The expected number of exact SCQs in Step 1 of the Coupon-Collector Clustering algorithm is \(O(kC(\mathbf{p}))\), where \(\mathbf{p}=(p_{1},p_{2},\ldots,p_{k})\) is given by \(p_{i}=n_{i}/n\) and \(n_{i}=|C_{i}^{*}|\), and \(C_{1}^{*},\ldots C_{k}^{*}\) being the optimal \(k\)-clustering,_  
Proof.