Learning to Cluster via Same-Cluster Queries

Clustering is a fundamental problem in data analytics and sees numerous applications across many areas in computer science. However, many clustering problems are computationally hard, even for approximate solutions. To alleviate the computational burden, Ashtiani et al. (Ashtiani et al., 2016) introduced weak supervision into the clustering process. More precisely, they allow the algorithm to query an oracle which can answer same-cluster queries, that is, whether two elements (points in the Euclidean space) belong to the same cluster. The oracle can, for example, be a domain expert in the setting of crowdsourcing. It was shown in (Ashtiani et al., 2016) that the $K$-means clustering can be solved computationally efficiently with the help of a small number of same-cluster queries using the oracle.

The initial work by Ashtiani et al. (Ashtiani et al., 2016) relies on a strong “data niceness property” called the $\gamma$-margin, which requires that for each cluster $C$ with center $\mu$, the distance between any point $p\not\in C$ and $\mu$ needs to be larger than that between any point $p\in C$ and $\mu$ by at least a constant multiplicative factor $\gamma>1$ sufficiently large. This assumption was later removed by Ailon et al. (Ailon et al., 2018b), who gave an algorithm which, given a parameter $K$, outputs a set $C$ of $K$ centers attaining a $(1+\epsilon)$-approximation of the $K$-means objective function. There has been follow-up work by Chien et al. (Chien et al., 2018) in the same setting, replacing the $\gamma$-margin assumption with a new assumption on the size of the clusters. However, there are still two critical issues in this line of approach:

1. (1)

   In (Ailon et al., 2018b; Chien et al., 2018), it is assumed that the total number of clusters $K$ in the true clustering is known to the algorithm, which is unrealistic in many cases.

2. (2)

   In (Ailon et al., 2018b; Chien et al., 2018), it is assumed that the optimal solution to the $K$-means clustering is consistent with the true clustering (i.e., when we have ground truth labels for all points). This assumption is highly problematic, since the ground-truth clustering can be arbitrary and very different from an optimal solution with respect to a fixed objective function such as the $K$-means.

In this paper, we aim to remove both assumptions. We shall design algorithms that find the approximate centers of the true clusters using same-cluster queries, in the setting that we do not know in advance the number of clusters in the true clustering and the true clustering has no relationship with the optimal solution of a certain objective function. We obtain our result at a small cost: our sample-based algorithm may not be able to find the centers of the small clusters which are very close to some big identified clusters; we shall elaborate on this shortly.

To specify what we mean by finding all big clusters, we need to introduce a concept called reducibility. Several previous studies (Kumar et al., 2010; Jaiswal et al., 2014; Ailon et al., 2018b) on the $K$-means/median clustering problem assumed that after finding $K$ main clusters, the residual ones satisfy some reducibility condition, which states that using the $K$ discovered cluster centers to cover the residual ones would only increase the total cost by a small $(1+\epsilon)$ factor. Similarly, we consider the following reducibility condition, based on the usual cost function.

Intuitively, this reducibility condition states that the clusters outside $I$ will be covered by the centers of the clusters in $I$ with only a small increase in the total cost.

Our goal is to find a subset of indices $I$ such that the set of true clusters in $X$ is $\epsilon$-reducible w.r.t. $I$.

Note that in this formulation, we do not attempt to optimize any objective function; instead, we just try to recover the approximate centroids of a set of clusters to which all other clusters are reducible. Inevitably we have to adopt a distance function in our definition of irreducibility, and we choose the widely used $D^{2}$ (Euclidean-squared) distance function so that we can still use the $D^{2}$-sampling method developed and used in the earlier works (Arthur and Vassilvitskii, 2007; Jaiswal et al., 2014; Ailon et al., 2018b). The $D^{2}$-sampling will be introduced in Definition 2.

To facilitate discussion, we list in Table 1.1 the commonly used notations in our algorithms and analyses. A cluster $i$ is said to be “discovered” if any point in $X_{i}$ has been sampled and “recovered” when the approximate centroid $\tilde{\mu}_{i}$ is computed. As discussed in the preceding paragraph, it is possible that the total number of recovered clusters, $K$, is less than the total number of discovered clusters, $L$, and that $L$ is less than the true number of clusters.

We also conduct an extensive set of experiments demonstrating the effectiveness of our algorithms on both synthetic and real-world data; see Section 6.

We further extend our algorithms to the case of a noisy same-cluster oracle which errs with a constant probability $p<1/2$. This extension has been deferred to Appendix D of the full version of this paper.

We remark that since our algorithms target sublinear (i.e., $o(\left|X\right|)$) number of oracle queries, in the general case where the shape of clusters can be arbitrary, it is impossible to classify correctly all points in the datasets. But the approximate centers outputted by the algorithms can be used to efficiently and correctly classify any newly inserted points (i.e., database queries) as well as existing database points (when needed), using a natural heuristic (Heuristic 1) that we shall introduce in Section 6. Our experiments show that most points can be classified using only one additional oracle query.

Bressan et al. (Bressan et al., 2020) considered the case where the clusters are separated by ellipsoids, in contrast to the balls as suggested by the usual $K$-means clustering objective. However, their algorithm still requires the knowledge of $K$ and has a query complexity that depends on $n$ (although logarithmically), which we avoid in this work.

Mazumdar and Saha studied clustering $n$ points into $K$ clusters with a noisy oracle (Mazumdar and Saha, 2017a) or side information (Mazumdar and Saha, 2017b). The noisy oracle gives incorrect answers to same-cluster queries with probability $p<1/2$ (so that majority voting still works). The side information is the similarity score between each pair of data points, generated from a distribution $f_{+}$ if the pair belongs to the same cluster and from another distribution $f_{-}$ otherwise. Algorithms proposed in these papers guarantee to recover the true clusters of size at least $\Omega(\log n)$, however, with query complexities at least $\Omega(Kn)$, much larger than what we are interested to achieve in this paper.

Huleihel et al. (Huleihel et al., 2019) studied the overlapping clustering with the aid of a same-cluster oracle. Suppose that $A$ is an $n\times K$ clustering matrix whose $i$-th row is the indicator vector of the cluster membership of the $i$-th element. The task is to recover $A$ from the similarity matrix $AA^{T}$ using a small number of oracle queries.

Finally, we note that same-cluster queries have been used extensively for entity resolution (or, de-duplication) (Wang et al., 2012, 2013; Vesdapunt et al., 2014; Verroios and Garcia-Molina, 2015; Firmani et al., 2016).

In this paper we consider point sets in the canonical Euclidean space $(\operatorname{\mathbb{R}}^{d},\|\cdot\|)$. The geometric centroid, or simply centroid, of a finite point set $X$ is defined as $\mu(X)=\frac{1}{|X|}\sum_{x\in X}x$. It is known that $\mu(X)$ is the minimizer of the $1$-center problem $\min_{c}\sum_{x\in X}\|x-c\|^{2}$. The next lemma provides a guarantee on approximating the centroid of a cluster using uniform samples.

We define the $D^{2}$-sampling of a point set $X$ with respect to a point set $C$ as follows.

In this paper we use a same-cluster oracle, that is, given two data points $x,y\in X$, $\textsc{Oracle}(x,y)$ returns true if $x$ and $y$ belong to the same cluster and false otherwise. For simplicity of the algorithm description, we shall instead invoke the function $\textsc{Classify}(x)$ to obtain the cluster index of $x$, which can be easily implemented using the same-cluster oracle, as shown in Algorithm 2.1. This implies that the number of oracle queries is at most $L$ times the number of samples.

In this section, we improve the basic algorithm by allowing the recovery of multiple clusters in each round. A particular case in which the basic algorithm would suffer from a prodigal waste of samples is that there are in total $K$ clusters of approximately the same size and they are $\epsilon$-irreducible with respect to any subset $I\subset[K]$. In such case, our basic algorithm requires a sample of size $\tilde{O}(K/\epsilon)$ from that cluster, which in turn requires a global sample of size $\tilde{O}(K^{2}/\epsilon)$. Summing over $K$ rounds leads to a total number $O(K^{3}/\epsilon)$ of samples. However, with $\tilde{O}(K^{2}/\epsilon)$ global samples, we can obtain $\tilde{O}(K/\epsilon)$ samples from every cluster and recover all clusters in the same round. This reduces a factor of $K$ in the total number of samples. The goal of this section is to improve the sample/query complexity of the basic algorithm by a factor of $K$ even in the worst case.

To recover an indefinite number of clusters in each round, it is a natural idea to generalize the basic algorithm to identifying a set $W$ of clusters, instead of the biggest one only, from which we shall obtain uniform samples via rejection sampling and calculate the approximate centroids $\{\tilde{\mu}_{j}\}_{j\in W}$. Here we face an ever greater challenge as to how to determine $W$. The naïve idea of including all clusters of $\Phi$-value at least $\Omega(\epsilon/r)$ runs into difficulty: as we sample more points, the value of $r$ may increase and we may need to include more and more points, so when do we stop? We may expect that the value $r$ will stabilize after sufficiently many samples, but it is difficult to quantify “stable” and control the number of samples needed.

Our solution to overcome the above-mentioned difficulty is to split the clusters into bands. To explain this we introduce a few more notations. For each unrecovered cluster $j\notin I$, recall that we defined in (3.2) its conditional sample probability $p_{j}=\Phi(X_{j},C)/\sum_{i\notin I}\Phi(X_{i},C)$; we also define its empirical approximation to be $\hat{p}_{j}=s_{j}/\sum_{i\notin I}s_{i}$, where $s_{i}$ denotes the number of samples seen so far which belong to the cluster $i$. We split $\{\hat{p}_{i}\}_{i\notin I}$ into $L+1$ bands for $L=3\log q$, where the $\ell$-th band is defined to be

for $\ell\leq L$ and the last band $B_{L+1}$ consists of all the remaining clusters $i$ (i.e., $\hat{p}_{i}\leq 1/q^{3}$). We say a band $B_{\ell}$ is heavy if $\sum_{i\in B_{\ell}}\hat{p}_{i}\geq 1/(3L)$. The values $\hat{p}_{i}$ and the bands are dynamically adjusted as the number of samples grows.

Instead of focusing on individual clusters and identifying the heavy ones, we shall identify the heavy bands at an appropriate moment and recover all the clusters in those heavy bands. Intuitively, it takes much fewer samples for bands to stabilize than for individual clusters. For instance, consider a heavy band which consists of many small clusters. In this case, we will have seen most of the clusters in the band without too many samples, although many of the $\hat{p}_{i}$’s may be far off from $p_{i}$’s. The important observation here is that we have seen those clusters; in contrast, if we consider individual clusters, we would have missed many of those clusters and will focus on recovering a few of them, which would cause a colossal waste of samples in the rejection sampling stage, for a similar reason explained at the beginning of this section. Therefore such banding approach enables us to control the number of samples needed.

Our improved algorithm is presented in Algorithm 4.1. Each round remains divided into four phases. Phase 1 remains testing new clusters. Starting from Phase 2 comes the change that instead of recovering only the largest sampled cluster $j$, we identify a subset $W$ of indices of the newly discovered clusters and recover all clusters in $W$. Phase 2 samples more points and identifies this subset $W$ by splitting the discovered clusters into bands and choosing all clusters in the heavy bands. Phase 3 samples more points and finds a reference point $x_{j}^{\ast}$ for each $j\in W$. Phase 4 keeps sample points until each cluster $j\in W$ sees $\Theta(\epsilon^{-1}|W|r)$ points and then calculates the approximate centers $\tilde{\mu}_{j}$ for each $j\in W$. The clusters in $W$ will then be added to $I$ as recovered clusters before the algorithm starts a new round.

A technical subtlety lies in controlling the failure probability in our new algorithm. In the basic algorithm, the failure probability in the $r$-th round is $a_{r}=1/(r\operatorname{poly}(\log r))$. If we recover $w_{r}$ clusters in $r$-th round, this failure probability for each of the $w_{r}$ clusters needs to be $1/(w_{r}a_{r})$, and as a consequence, $\tilde{O}(w_{r}^{2}a_{r})$ samples are needed in the $r$-th round. In the worst case this becomes $\tilde{O}(K^{3})$ samples, the same as in the basic algorithm, when both $w_{r}=\Theta(K)$ and $a_{r}=\tilde{\Theta}(1/K)$. To resolve this, we guess $K=1,2,\dots$ in powers of $2$ and assign $a_{r}$ to be $w_{r}/K$. For each fixed guess $K$, the number of samples is bounded by $\tilde{O}(K^{2})$; iterating over guesses incurs only an additional $\log K$ factor.

The analysis of our improved algorithm follows the same sketch of the basic algorithm and we only present the changes below. All proofs are postponed to Appendix C. The next lemma offers a similar guarantee as Lemma 2.

Next we upper bound the number of samples with a lemma analogous to Lemma 3.

Recall that $Y_{j}$ was defined in (3.3) for all $j\in W$. The following two lemmata are the analogue of Lemmata 4 and 5, respectively.

Now we are ready to prove the main theorem of the improved algorithm.

Our algorithm can be extended to the case where the same-cluster oracle errs with a constant probability $p<1/2$. The full details are postponed to Appendix D in the full version.

In this section, we conduct experimental studies of our algorithms. As we mentioned before, all previous algorithms need to know $K$ and it is impossible to convert them to the case of unknown $K$ (with the only exception of (Chien et al., 2018)). In particular, we note the inapplicability of the $k$-means algorithm and the algorithm in (Ailon et al., 2018b).

• •

  The $k$-means algorithm is for an unsupervised learning task and returns clusters which are always spherical, so it is undesirable for arbitrary shapes of clusters and it makes sense to examine the accuracy in terms of misclassified points. Our problem is semi-supervised with a same-cluster oracle, which can be used to recover clusters of arbitrary shapes and guarantees no misclassification. The assessment of the algorithm is therefore the number of discovered clusters and the number of samples. Owing to the very different nature of the problems, the $k$-means algorithm should not be used in our problem or compared with algorithms designed specifically for our problem.

• •

  The algorithm in (Ailon et al., 2018b) runs in $k$ rounds and take $2^{12}k^{3}/\epsilon^{2}$ samples in the first step of each round. With $k=10$ and $\epsilon=0.1$, it needs to sample in each round at least $4\times 10^{8}$ points, usually larger than the size of a dataset. (Our algorithm can be easily simplified to handle such cases, see the subsection titled “Algorithms” below.)

The only exception, the algorithm in (Chien et al., 2018), is just simple uniform sampling and whether or not $K$ is known is not critical. This uniform sampling algorithm will be referred to as Uniform below.

For synthetic datasets, we generate $n$ points that belong to $K$ clusters in the $d$-dimensional Euclidean space. Since in the real world the cluster sizes typically follow a power-law distribution, we assign to each cluster a random size drawn from the widely used Zipf distribution, which has the density function $f(x)\propto x^{-\alpha}$, where $x$ is the size of the cluster and $\alpha$ a parameter controlling the skewness of the dataset. We then choose a center $\mu_{i}$ for each cluster $i\in[K]$ in a manner to be specified later and generate the points in the cluster from the multivariate Gaussian distribution $N(\mu_{i},\sigma^{2}I_{d})$, where $I_{d}$ denotes the $d\times d$ identity matrix.

Now we specify how to choose the centers. In practice, clusters in the dataset are not always well separated; there could be clusters whose centers are close to each other. We thus use an additional parameter $p$ to characterize this phenomenon. In the default setting of $p=0$, all centers of the $K$ clusters are drawn uniformly at random from $[0,b]^{d}$. When $p>0$, we first partition the clusters into groups as follows: Think of each cluster as a node. For each pair of clusters, with probability $p$ we add an edge between the two nodes. Each connected component of the resulting graph forms a group. Next, for each group of clusters, we pick a random cluster and choose its center $\mu$ uniformly at random in $[0,b]^{d}$. For each of the remaining clusters in the group, we choose its center uniformly at random in the neighborhood of radius $\rho$ centered at $\mu$.

We use the following set of parameters as the default setting in our synthetic datasets: $n=10^{6}$, $K=100$, $\alpha=2.5$, $\sigma=0.3$, $b=5$, $d=10$ and $\rho=0.1$.

We also use the following two real-world datasets.

• •

  Shuttle ²²2https://archive.ics.uci.edu/ml/datasets/Statlog+(Shuttle).: it describes the radiator positions in a NASA space shuttle. There are 58,000 points with 9 numerical attributes, and 7 clusters in total.

• •

  Kdd ³³3http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.: this dataset is taken from the 1999 KDD Cup contest. It contains about 4.9M points classified into 23 clusters. The original dataset has 41 attributes. We retain all numerical attributes except one that contains only zeros, resulting in 33 attributes in total.

Each feature in the real world datasets is normalized to have zero mean and unit standard deviation.

Recall that in our basic and improved algorithms, we always “ignore” the samples belonging to the unrecovered clusters in the previous rounds, which will not affect our theoretical analysis. But in practice it is reasonable to reuse these “old” samples in the succeeding rounds so that we are able to recover some clusters earlier. Because of such a sample-reuse procedure, the practical performance difference between the Basic and Batched algorithms becomes less significant. Recall that in theory, the main improvement of Batched over Basic is that we try to avoid wasting too many samples in each round by recovering possibly more than one cluster at a time. But still, as we shall see shortly, Batched outperforms Basic in all metrics, though sometimes the gaps may not seem significant.

We also report the error of the approximate centroid of each recovered cluster. For a recovered cluster $X_{i}$, let $\mu_{i}$ be its centroid and $\hat{\mu}_{i}$ be the approximate center. We define the centroid approximation error to be $\left(\Phi(X_{i},\hat{\mu}_{i})-\Phi(X_{i},\mu_{i})\right)/\Phi(X_{i},\mu_{i})$.

For Basic and Batched, we further compare their running time and round usage. We note that a small round usage is very useful if we want to efficiently parallelize the learning process.

Finally, we would like to mention one subtlety when measuring the number of same-cluster queries. Since all algorithms that we are going to test are sampling based, and for each sampled point we need to identify its label by same-cluster queries, which, in the worst case, takes $k$ queries, where $k$ is the number of the discovered clusters so far. In practice, however, a good query order/strategy can save us a lot of same-cluster queries. We apply the following query strategy for all tested algorithms.

We will also use this heuristic to test the effectiveness of approximate centers for classifying new points. That is, for a newly inserted point $q$, we count the number of same-cluster queries needed to correctly classify $q$ using the approximate centers and Heuristic 1.

The authors would also like to thank the anonymous referees for their valuable comments and helpful suggestions. Yan Song and Qin Zhang are supported in part by NSF IIS-1633215 and CCF-1844234.