Clustering Stable Instances of Euclidean k-means

Introduction

One of the major challenges in the theory of clustering is to bridge the large disconnect between our theoretical and practical understanding of the complexity of clustering. While theory tells us that most common clustering objectives like $k$-means or $k$-median clustering problems are intractable in the worst case, many heuristics like Lloyd’s algorithm or k-means++ seem to be effective in practice. In fact, this has led to the “CDNM” thesis : “Clustering is difficult only when it does not matter”.

We try to address the following natural questions in this paper: Why are real-world instances of clustering easy? Can we identify properties of real-world instances that make them tractable?

One way to model real-world instances of clustering problems is through instance stability, which is an implicit structural assumption about the instance. Practically interesting instances of the $k$-means clustering problem often have a clear optimal clustering solution (usually the ground-truth clustering) that is stable: i.e., it remains optimal even under small perturbations. As argued in , clustering objectives like $k$-means are often just a proxy for recovering a ground-truth clustering that is close to the optimal solution. Instances in practice always have measurement errors, and optimizing the $k$-means objective is meaningful only when the optimal solution is stable to these perturbations.

Multiplicative perturbation stability represents an elegant, well-motivated formalism that captures robustness to measurement errors for clustering problems in general metric spaces ($\gamma=1.1$ captures relative errors of 10% in the distances). However, multiplicative perturbation stability has the following drawbacks in the case of Euclidean clustering problems:

Measurement errors in Euclidean instances are better captured using additive perturbations. Uncertainty of $\delta$ in the position of $x,y$ leads to an additive error of $\delta$ in $\lVert x-y\rVert_{2}$, irrespective of how large or small $\lVert x-y\rVert_{2}$ is.

The amount of stability, $\gamma$, needed to enable efficient algorithms (i.e., $\gamma\geq 2$) often imply strong structural conditions, that are unlikely to be satisfied by many real-world datasets. For instance, $\gamma$-factor perturbation stability implies that every point is a multiplicative factor of $\gamma$ closer to its own center than to any other cluster center.

Algorithms that are known to have provable guarantees under multiplicative perturbation stability are based on single-linkage or MST algorithms that are very non-robust by nature. In the presence of a few outliers or noise, any incorrect decision in the lower layers gets propagated up to the higher levels.

In this work, we consider a natural additive notion of stability for Euclidean instances: the optimal clustering should not change even when each point is moved a Euclidean distance of at most $\delta$. This corresponds to a small additive perturbation to the pairwise distances between the pointsNote that not all additive perturbations to the distances can be captured by an appropriate movement of the points in the cluster. Hence the notion we consider in our paper is a weaker assumption on the instance.. Unlike multiplicative notions of perturbation stability , this notion of additive perturbation is not scale invariant. Hence the normalization or scale of the perturbation is important.

Ackerman and Ben-David initiated the study of additive perturbation stability when the distance between any pair of points can be changed by at most $\delta=\varepsilon\operatorname{diam}(X)$ with $\operatorname{diam}(X)$ being the diameter of the whole dataset. The algorithms take time $n^{O(k/\varepsilon^{2})}=n^{O(k\operatorname{diam}^{2}(X)/\delta^{2})}$ and correspond to polynomial time algorithms when $k,1/\varepsilon$ are constants. However, this dependence of $k\operatorname{diam}^{2}(X)/\delta^{2}$ in the exponent is not desirable since the diameter is a very non-robust quantity – the presence of one outlier (that is even far away from the decision boundary) can increase the diameter arbitrarily. Hence, these guarantees are useful mainly when the whole instance lies within a small ball and the number of clusters is small . Our notion of additive perturbation stability will use a different scale parameter that is closely related to the distance between the centers instead of the diameter $\operatorname{diam}(X)$. Our results for additive perturbation stability have no explicit dependence on the diameter, and allows instances to have potentially unbounded clusters (as in the case of far-way outliers). With some additional assumptions, we also obtain polynomial time algorithmic guarantees for large $k$.

We consider a notion of additive stability where the points in the instance can be moved by at most $\delta=\varepsilon D$, where $\varepsilon\in(0,1)$ is a parameter, and $D=\max_{i\neq j}D_{ij}=\max_{i\neq j}\lVert\mu_{i}-\mu_{j}\rVert_{2}$ is the maximum distance between pairs of means. Suppose $X$ is a $k$-means clustering instance with optimal clustering $C_{1},C_{2},\dots,C_{k}$. We say that $X$ is $\varepsilon$-additive perturbation stable ($\varepsilon$-APS) iff every $\delta$-additive perturbation of $X$ has $C_{1},C_{2},\dots,C_{k}$ as an optimal clustering solution. Note that there is no restriction on the diameter of the instance, or even the diameters of the individual clusters. Hence, our notion of additive perturbation stability allows the instance to be unbounded.

Clusters in the optimal solution of an $\varepsilon$-APS instance satisfy a natural geometric condition — there is an “angular separation” between every pair of clusters.

Let $X$ be an $\varepsilon$-APS instance and let $C_{i},C_{j}$ be two clusters in its optimal solution. Any point $x\in C_{i}$ lies in a cone whose axis is along the direction $(\mu_{i}-\mu_{j})$ with half-angle $\text{arctan}(1/\varepsilon)$. Hence if $u$ is the unit vector along $\mu_{i}-\mu_{j}$ then

The distance between $\mu_{i}$ and the apex of the cone is $\Delta=(\tfrac{1}{2}-\varepsilon)D$. We will call $\Delta$ the scale parameter of the clustering. See Figure 1a for an illustration.

We believe that many clustering instances in practice satisfy the $\varepsilon$-APS condition for reasonable constants $\varepsilon$. In fact, our experiments in Section 7 suggest that the above geometric condition is satisfied for reasonable values e.g., $\varepsilon\in(0.001,0.2)$.

While the points can be arbitrarily far away from their own means, the above angular separation (1) is crucial in proving the polynomial time guarantees for our algorithms. For instance, this implies that at least $1/2$ of the points in a cluster $C_{i}$ are within a Euclidean distance of at most $O(\Delta/\varepsilon)$ from $\mu_{i}$. This geometric condition (1) of the dataset enables the design of a tractable algorithm for $k=2$ with provable guarantees. This algorithm is based on a modification of the perceptron algorithm in supervised learning, and is inspired by . See Section 4 for details on the $k=2$ case.

We consider a natural strengthening of additive perturbation stability where there is an additional margin between any pair of clusters. This is reminiscent of margin assumptions in supervised learning of halfspaces and spectral clustering guarantees of Kumar and Kannan (see Section 1.2). Consider a $k$-means clustering instance $X$ with optimal solution $C_{1},C_{2},\dots,C_{k}$. We say this instance is $(\rho,\Delta,\varepsilon)\text{-separated}$ iff for each $i\neq j\in[k]$, the subinstance induced by $C_{i},C_{j}$ has parameter scale $\Delta$, and all points in the clusters $C_{i},C_{j}$ lie inside cones of half-angle $\text{arctan}(1/\varepsilon)$, which are separated by a margin of at least $\rho$. This is implied by the stronger condition that the subinstance induced by $C_{i},C_{j}$ is $\varepsilon$-additive perturbation stable with scale parameter $\Delta$ even when $C_{i}$ and $C_{j}$ are moved towards each other by $\rho$. See Figure 1b for an illustration. $(\rho,\Delta,\varepsilon)\text{-separated}$ stable instances are defined formally in geometric terms in Section 3.

There is an $\widetilde{O}(n^{2}kd)$-timeThe $\widetilde{O}$ hides logarithmic factors in $n$. algorithm that given any instance $X$ that is $(\rho,\Delta,\varepsilon)\text{-separated}$ with $\rho\geq\Omega(\Delta/\varepsilon^{2})$ recovers its optimal clustering $C_{1},\dots,C_{k}$.

A formal statement of the theorem (with unequal sized clusters) and its proof are given in Section 5. We prove these polynomial time guarantees for a new, simple algorithm (Algorithm 5.1). The algorithm constructs a graph with one vertex for each point, and edges between points that are within a distance of at most $r$ (for an appropriate threshold $r$). The algorithm then finds the $k$-largest connected components and uses the empirical means of these $k$ components to cluster all the points.

In addition to having provable guarantees, the algorithm also seems efficient in practice, and performs well on standard clustering datasets. Experiments that we conducted on some standard clustering datasets in UCI suggest that our algorithm manages to almost recover the ground truth and achieves a $k$-means objective cost that is very comparable to Lloyd’s algorithm and $k$-means++.

In fact, our algorithm can also be used to initialize Lloyd’s algorithm: our guarantees show that when the instance is $(\rho,\Delta,\varepsilon)\text{-separated}$, one iteration of Lloyd’s algorithm already finds the optimal clustering. Experiments suggest that our algorithm finds initializers of smaller $k$-means cost compared to the initializers of $k$-means++ and also recover the ground-truth to good accuracy.

Experimental results and analysis of real-world data sets can be found in Section 7.

Perturbation stability requires the optimal solution to remain completely unchanged under any valid perturbation. In practice, the stability of an instance may be dramatically reduced by a few outliers. We show provable guarantees for a slight modification of Algorithm 5.1 in the setting where an $\eta$-fraction of the points can be arbitrary outliers, and do not lie in the stable regions. Formally, we assume that we are given an instance $X\cup Z$ where there is an (unknown) set of points $Z$ with $|Z|=\eta|X|$ such that $X$ is a $(\rho,\Delta,\varepsilon)\text{-separated}$ instance. Here $\eta n$ is assumed to be less than the size of the smallest cluster by a constant factor. This is similar to robust perturbation resilience considered in . Our experiments in Section 7 indicate that the stability or separation can increase a lot after ignoring a few points close to the margin.

In what follows, $w_{\max}=\max\lvert C_{i}\rvert/n$ and $w_{\min}=\min\lvert C_{i}\rvert/n$ are the maximum and minimum weight of clusters, and $\eta<w_{\min}$.

Given $X\cup Z$ where $X$ is $(\rho,\Delta,\varepsilon)\text{-separated}$ for

and $\eta=\lvert Z\rvert/\lvert X\rvert<w_{\text{min}}$, there is a polynomial time algorithm running in time $\widetilde{O}(n^{2}dk)$ that returns a clustering consistent with $C_{1},\dots,C_{k}$ on $X$.

This robust algorithm is effectively the same as Algorithm 5.1 with one additional step that removes all low-degree vertices in the graph. This step removes bad outliers in $Z$ without removing too many points from $X$.

2 Comparisons to other related work

Awasthi et al. showed that $\gamma$-multiplicative perturbation stable instance also satisfied the notion of $\gamma$-center based stability (every point is a $\gamma$-factor closer to its center than to any other center) . They showed that an algorithm based on the classic single linkage algorithm works under this weaker notion when $\gamma\geq 3$. This was subsequently improved by , and the best result along these lines gives a polynomial time algorithm that works for $\gamma\geq 2$. A robust version of $(\gamma,\eta)$-perturbation resilience was explored for center-based clustering objectives . As such, the notions of additive perturbation stability, and $(\rho,\Delta,\varepsilon)\text{-separated}$ instances are incomparable to the various notions of multiplicative perturbation stability. Furhter as argued in , we believe that additive perturbation stability is more realistic for Euclidean clustering problems.

The exciting results of Kumar and Kannan and Awasthi and Sheffet also gave a determinstic margin-separation condition, under which spectral clustering (PCA followed by $k$-means) This requires appropriate initializers, that they can obtain in polynomial time. finds the optimum clusters under deterministic conditions about the data. Suppose $\sigma=\lVert X-C\rVert^{2}_{op}/n$ is the “spectral radius” of the dataset, where $C$ is the matrix given by the centers. In the case of equal-sized clusters, the improved results of proves approximate recovery of the optimal clustering if the margin $\rho$ between the clusters along the line joining the centers satisfies $\rho=\Omega(\sqrt{k}\sigma)$. Our notion of margin $\rho$ in $(\rho,\Delta,\varepsilon)\text{-separated}$ instances is analogous to the margin separation notion used by the above results on spectral clustering . In particular, we require a margin of $\rho=\Omega(\Delta/\varepsilon^{2})$ where $\Delta$ is our scale parameter, with no extra $\sqrt{k}$ factor. However, we emphasize that the two margin conditions are incomparable, since the spectral radius $\sigma$ is incomparable to the scale parameter $\Delta$.

We now illustrate the difference between these deterministic conditions by presenting a couple of examples. Consider an instance with $n$ points drawn from a mixture of $k$ Gaussians in $d$ dimensions with identical diagonal covariance matrices with variance $1$ in the first $O(1)$ coordinates and roughly $1/d$ in the others, and all the means lying in the subspace spanned by these first $O(1)$ co-ordinates. In this setting, the results of require a margin separation of at least $\sqrt{k\log n}$ between clusters. On the other hand, these instances satisfy our geometric conditions with $\varepsilon=\Omega(1)$, $\Delta~{}\sqrt{\log n}$ and therefore our algorithm only needs a margin separation of $\rho\sqrt{\log n}$ (hence, saving a factor of $\sqrt{k}$)Further, while algorithms for learning GMM models may work here, adding some outliers far from the decision boundary will cause many of these algorithms to fail, while our algorithm is robust to such outliers.. However, if the $n$ points were drawn from a mixture of spherical Gaussians in high dimensions (with $d\gg k$), then the margin condition required for is weaker.

Finally, we note another strand of recent works show that convex relaxations for $k$-means clustering become integral under distributional assumptions about points and sufficient separation between the components .

Preliminaries

A given choice of centers $\mu_{1},\dots,\mu_{k}$ determines an optimal clustering $C_{1},\dots,C_{k}$ where $C_{i}=\set{x}{i=\arg\min_{j}\lVert x-\mu_{j}\rVert}$. We can rewrite the objective as

On the other hand, a given choice for cluster $C_{i}$ determines its optimal center as $\mu_{i}=\frac{1}{\lvert C_{i}\rvert}\sum_{x\in C_{i}}x$, the mean of the points in the set. Thus, we can reformulate the problem as minimizing over clusters $C_{1},C_{2},\dots,C_{k}$ of $\set{x_{i}}$ the objective

Stability definitions and geometric properties

We define an instance parameter, $\beta$, capturing how balanced a given instance’s clusters are.

Given an instance $X$ with optimal clustering $C_{1},\dots,C_{k}$, we say $X$ satisfies balance parameter $\beta\geq 1$ if for all $i\neq j$, $\beta\lvert C_{i}\rvert>\lvert C_{j}\rvert$.

2 Additive perturbation stability

Let $X=\set{x_{1},\dots,x_{n}}$ be a $k$-means clustering instance with unique optimal clustering $C_{1},C_{2},\dots,C_{k}$ whose means are given by $\mu_{1},\mu_{2},\dots,\mu_{k}$. Let $D=\max_{i,j}\left\lVert\mu_{i}-\mu_{j}\right\rVert$. We say that $X^{\prime}=\set{x^{\prime}_{1},\dots,x^{\prime}_{n}}$ is an $\varepsilon$-additive perturbation of $X$ if for all $i$, $\left\lVert x^{\prime}_{i}-x_{i}\right\rVert\leq\varepsilon D$.

Let $X$ be a $k$-means clustering instance with unique optimal clustering $C_{1},C_{2},\dots,C_{k}$. We say that $X$ is $\varepsilon$-additive perturbation stable (APS) if every $\varepsilon$-additive perturbation of $X$ has an optimal clustering given by $C_{1},C_{2},\dots,C_{k}$.

Intuitively, the difficulty of the clustering task increases as the stability parameter $\varepsilon$ decreases. For example, when $\varepsilon=0$ the set of $\varepsilon$-APS instances contains any instance with a unique solution. In the following we will only consider $\varepsilon>0$.

3 Geometric implication of ε𝜀\varepsilon-APS

Let $X$ be an $\varepsilon$-APS $k$-means clustering instance such that each cluster has at least $4$ points. Fix $i\neq j$ and consider clusters $C_{i}$, $C_{j}$ with means $\mu_{i}$, $\mu_{j}$. We fix the following notation.

Let $D_{i,j}=\left\lVert\mu_{i}-\mu_{j}\right\rVert$ and let $D=\max_{i^{\prime},j^{\prime}}\left\lVert\mu_{i^{\prime}}-\mu_{j^{\prime}}\right\rVert$.

Let $p=\frac{\mu_{i}+\mu_{j}}{2}$ be the midpoint between $\mu_{i}$ and $\mu_{j}$.

We can establish geometric conditions that $X$ must satisfy by considering different perturbations. As an example, one could move all points in $C_{i}$ and $C_{j}$ towards each other in the intermean direction a distance of $\varepsilon D$; by assumption no point has crossed the separating hyperplane and thus we can conclude the existence of a margin of width $2\varepsilon D$.

A careful choice of a family of perturbations allows us to prove Proposition 1.1. Consider the perturbation which moves $\mu_{i}$ and $\mu_{j}$ in opposite directions orthogonal to $u$ while moving a single point towards the other cluster parallel to $u$ (see figure 2). The following lemma establishes Proposition 1.1.

For any $x\in C_{i}\cup C_{j}$, $\lVert(x-p)_{(V)}\rVert\leq\frac{1}{\varepsilon}\left(\lVert(x-p)_{(u)}\rVert-\varepsilon D_{i,j}\right)$.

Let $v\in V$ be a unit vector perpendicular to $u$. Without loss of generality, let $a\in C_{i}$ (taking $u$ or $-u$ does not change the inequality). Let $b,c,d\in C_{i}$ such that $a,b,c,d\in C_{i}$ are distinct. Let $\delta=\varepsilon D_{i,j}\leq\varepsilon D$ and consider the $\varepsilon$-additive perturbation $X^{\prime}$ given by the union of

and an unperturbed copy of $X\setminus(C_{i}\cup C_{j})$.

By assumption, $\set{C_{i},C_{j}}$ remain optimal clusters in $X^{\prime}$. We have constructed $X^{\prime}$ such that the new means of $C_{i}$, $C_{j}$ are $\mu_{i}^{\prime}=\mu_{i}-\frac{\delta}{2}v$ and $\mu_{j}^{\prime}=\mu_{j}+\frac{\delta}{2}v$, and the midpoint between the means is $p^{\prime}=p$. The halfspace containing $\mu_{i}^{\prime}$ given by the linear separator between $\mu_{i}^{\prime}$ and $\mu_{j}^{\prime}$ is $\langle x-p^{\prime},\mu_{i}^{\prime}-\mu_{j}^{\prime}\rangle\geq 0$. Hence, as $a^{\prime}$ is classified correctly by the $\varepsilon$-APS assumption,

Then noting that $\langle a-p,u\rangle\geq 0$, we have that $\langle a-p,v\rangle\leq\frac{1}{\varepsilon}\left(\lVert(a-p)_{(u)}\rVert-\delta\right)$. ∎

This geometric property follows from perturbations which only affect two clusters at a time. Our results follow from this weaker notion.

4 (ρ,Δ,ε)𝜌Δ𝜀(\rho,\Delta,\varepsilon)-separation

Motivated by Lemma 3.4, we define a geometric condition where the angular separation and margin separation are parametrized separately. These separations are implied by a stronger stability assumption where any pair of clusters is $\varepsilon$-APS with scale parameter $\Delta$ even after being moved towards each other a distance of $\rho$.

We say that a pair of clusters is $(\rho,\Delta,\varepsilon)$-separated if their points lie in cones with axes along the intermean direction, half-angle $\arctan(1/\varepsilon)$, and apexes at distance $\Delta$ from their means and at least $\rho$ from each other (see figure 1b). Formally, we require the following.

Given a pair of clusters $C_{i}$, $C_{j}$ with means $\mu_{i}$, $\mu_{j}$, let $u=\frac{\mu_{i}-\mu_{j}}{\lVert\mu_{i}-\mu_{j}\rVert}$ be the unit vector in the intermean direction and let $p=(\mu_{i}+\mu_{j})/2$. We say that $C_{i}$ and $C_{j}$ are $(\rho,\Delta,\varepsilon)$-separated if $D_{i,j}\geq\rho+2\Delta$ and for all $x\in C_{i}\cup C_{j}$,

We say that an instance $X$ is $(\rho,\Delta,\varepsilon)$-separated if every pair of clusters in the optimal clustering is $(\rho,\Delta,\varepsilon)$-separated.

k𝑘k-means clustering for k=2𝑘2k=2

In this section, we give an algorithm that is able to cluster $2$-means $\varepsilon$-APS instances correctly.

There exists a universal constant $c\geq 1$ such that for any fixed $\varepsilon>0$, there exists an $n^{O((1/\varepsilon)^{c})}d$ time algorithm that correctly clusters all $\varepsilon$-APS $2$-means instances.

The algorithm is inspired by work in showing that the perceptron algorithm runs in poly-time with high probability in the smoothed analysis setting.

The following well-known theorem bounds the number of total mistakes the perceptron algorithm can make in terms of the sequence’s angular margin.

The number of mistakes made by the perceptron algorithm is bounded above by $(1/\gamma)^{2}$ for

2 A perceptron-based clustering algorithm

Lemma 3.4 gives a lower bound for $\gamma$ in the correctly-centered set $\set{x_{1}-p,\dots,x_{n}-p}$. Thus Lemma 4.3 might suggest a simple algorithm: for each multiset of bounded size and each of its possible labels, compute the cost of the associated clustering, then output the clustering of minimum cost. However, a difficulty arises as the clusters $C_{1}$, $C_{2}$ may not be linearly separable (in particular the separating hyperplane may not pass through the origin). Note that the guarantees of the perceptron algorithm, and hence Lemma 4.3, do not hold in this case. Instead, we will apply the above idea to an instance $Y$, constructed from $X$, in which $C_{1}$, $C_{2}$ are linearly separable and we can efficiently lower bound $\gamma$.

3 Overview of proof of Theorem 4.1

We will lower bound $\gamma$ for a particular instance $Y_{a,b}$ in which $a,b$ have nice properties. The following lemma states that on one of the iterations of its outer for loop, Algorithm 4.4 will pick such points.

There exist points $a\in C_{1}$, $b\in C_{2}$ such that $\langle a-p,u\rangle\leq\Delta/2$ and $\langle b-p,-u\rangle\leq\Delta/2$.

The geometric conditions implied by $\varepsilon$-APS allow us to bound $\delta=\lVert a-b\rVert$ in terms of $\varepsilon,D$. In particular, using this handle on $\delta$, it is possible to prove the following lower bound on $\gamma$.

There exists constant $c_{1}$ such that for any $a,b$ satisfying Lemma 4.5, the corresponding instance $Y_{a,b}$ has

The correctness of Algorithm 4.4 for all $\varepsilon$-APS $2$-means clustering instances in which each cluster has at least $4$ points then follows from Lemmas 4.3, 4.5, and 4.6. On the other hand, the optimal $2$-means clustering where one of the clusters has at most $3$ points can be calculated in $O(n^{4}d)$ time. An algorithm that returns the better of these two solutions thus correctly clusters all $\varepsilon$-APS $2$-means instances, completing the proof of Theorem 4.1. See Appendix A.2 for proofs of Lemmas 4.5 and 4.6.

k𝑘k-means clustering for general k𝑘k

For general $k$, we will require the stronger $(\rho,\Delta,\varepsilon)$-separation. Consider the following algorithm.

Algorithm 5.1 recovers $C_{1},\dots,C_{k}$ for any $(\rho,\Delta,\varepsilon)\text{-separated}$ instance with $\rho=\Omega\left(\frac{\Delta}{\varepsilon^{2}}+\frac{\beta\Delta}{\varepsilon}\right)$ and can be implemented in $\widetilde{O}(n^{2}kd)$ time.

This running time can be achieved by inserting edges into a dynamic graph in order, maintaining connected components and their means using a union-find data structure, and noting that the number of connected components can change at most $n$ times.

In particular, note that this algorithm does not need any prior knowledge of the stability parameters and its running time has no dependence on $\rho$, $\Delta$, or $\varepsilon$.

$S_{i,j}^{(\text{nice})}=\set{x\in S_{i,j}^{(\text{cone})}}{\langle x-\mu_{i},u\rangle\leq 0}$,

$S_{i}^{(\text{good})}=\bigcap_{j\neq i}S_{i,j}^{(\text{nice})}$.

It suffices to prove the following two lemmas. Lemma 5.4 states that the initialization returned by the INITIALIZE subroutine satisfies certain properties when we guess $r=\rho$ correctly. As $\rho$ is only used as a threshold on edge lengths, testing the distances between all pairs of data points i.e. $\set{\lVert a-b\rVert:a,b\in X}$ suffices. Lemma 5.5 states that the ASSIGN subroutine correctly clusters all points given an initialization satisfying these properties.

For a $(\rho,\Delta,\varepsilon)\text{-separated}$ instance with balance parameter $\beta$ and $\rho=\Omega(\beta\Delta/\varepsilon)$, the INITIALIZE subroutine finds a set $\set{a_{1},\dots,a_{k}}$ where $a_{i}\in S_{i}^{(\text{good})}$ when $r=\rho$.

For a $(\rho,\Delta,\varepsilon)\text{-separated}$ instance with $\rho=\Omega(\Delta/\varepsilon^{2})$, the ASSIGN subroutine recovers $C_{1},C_{2},\cdots C_{k}$ correctly when initialized with $k$ points $\set{a_{1},a_{2},\dots,a_{k}}$ where $a_{i}\in S_{i}^{(\text{good})}$.

Suppose $r=\rho$ and consider the graph constructed by Algorithm 5.1. We start by defining the core region of each cluster.

The core regions are defined in such a way that for each cluster $C_{i}$, all points in $C_{i}\cap S_{i}^{(\text{core})}$ belong to a single connected component. Although $S_{i}^{(\text{core})}$ may not contain too many points on its own, the connected component containing $S_{i}^{(\text{core})}$ will contain most (at least $\beta/(1+\beta)$ fraction) of the points in $C_{i}$. Hence, the $k$ largest components will be the connected components containing the $k$ different core regions. Finally, since the connected component containing $S_{i}^{(\text{core})}$ contains most of the points in $C_{i}$, the geometric conditions of $(\rho,\Delta,\varepsilon)$-separation ensure that the empirical mean of the connected component lies in $S_{i}^{(\text{good})}$. The following lemma states some properties of the connected components in our graph. Its proof can be found in Appendix B.1.

Any connected component only contains points from a single cluster.

For all $i,j$, $S_{i}^{(\text{core})}\supseteq S_{i,j}^{(\text{nice})}$. There is a point $x\in C_{i}$ such that $x\in S_{i}^{(\text{core})}\cap S_{i,j}^{(\text{nice})}$.

For all $i,j$, let $A_{i,j}=\set{x\in C_{i}}{\langle x-\mu_{i},u\rangle\leq\beta\Delta}$. Then, $\lvert A_{i,j}\rvert\geq\frac{\beta}{1+\beta}\lvert C_{i}\rvert$.

For all $i$, $S_{i}^{(\text{core})}\cap X$ is connected in $G$.

For all $i,j$, $A_{i,j}$ is connected in $G$.

The largest component, $K_{i}$, in each cluster contains $A_{i,j}$ for each $j\neq i$. In particular, $\lvert K_{i}\rvert\geq\frac{\beta}{1+\beta}\lvert C_{i}\rvert$, and $K_{i}$ contains $S_{i}^{(\text{core})}\cap X$.

Lemma 5.8 states that the $k$ largest components (and hence $\set{a_{1},\dots,a_{k}}$) must belong to different clusters while Lemma 5.9 states that each $a_{i}$ lie inside a good region. Together, they imply Lemma 5.4, i.e. each $a_{i}$ comes from a different good region.

The set of $k$ largest components of $G$ contains the largest component of each cluster.

Let $K_{i}$ be the largest component in $C_{i}$ and let $K_{j}^{\prime}$ be a component in $C_{j}$ that is not the largest. Then by the $\beta$ parameter, $\lvert K_{i}\rvert\geq\frac{\beta}{1+\beta}\lvert C_{i}\rvert>\frac{1}{1+\beta}\lvert C_{j}\rvert\geq\lvert K_{j}^{\prime}\rvert$. It follows that the $k$ largest connected components are $K_{1},K_{2},\dots,K_{k}$. ∎

The mean of points in $K_{i}$ lies in $S_{i}^{(\text{good})}$.

Let $a_{i}$ be the mean of the points in $K_{i}$. As $K_{i}\subseteq S_{i,j}^{(\text{cone})}$ is a convex set, $a_{i}\in S_{i,j}^{(\text{cone})}$. As $K_{i}\supseteq S_{i}^{(\text{core})}\cap X\supseteq S_{i,j}^{(\text{nice})}\cap X$, the points $x\in C_{i}$ not contained in $K_{i}$ have $\langle x-\mu_{i},u\rangle>0$. Noting that $\sum_{x\in C_{i}}\langle x-\mu_{i},u\rangle=0$, it follows that $\langle a_{i}-\mu_{i}\rangle\leq 0$. Hence, $a_{i}\in S_{i,j}^{(\text{nice})}$. As this holds for each $j\neq i$, $a_{i}\in S_{i}^{(\text{good})}$. ∎

2 Proof of Lemma 5.5.

We will show that for any $a_{i}\in S_{i,j}^{(\text{nice})}$, $a_{j}\in S_{j,i}^{(\text{nice})}$, and $x\in C_{i}$, $x$ is closer to $a_{i}$ than to $a_{j}$. The following lemma states some properties of the perpendicular bisector between $a_{i}$ and $a_{j}$. These statements follow from the definitions of the nice regions and the angular separation. Its proof can be found in Appendix B.2.

Suppose $\rho=\Omega(\Delta/\varepsilon^{2})$. Then, for $a_{i}\in S_{i,j}^{(\text{nice})}$ and $a_{j}\in S_{j,i}^{(\text{nice})}$, we have

$\lVert(a_{i}-a_{j})_{(u)}\rVert\geq\frac{\lVert(a_{i}-a_{j})_{(V)}\rVert}{\varepsilon}$,

$\langle\frac{a_{i}+a_{j}}{2}-p,u\rangle\leq\frac{\Delta}{2}$, and

\Big{\lVert}\left(\frac{a_{i}+a_{j}}{2}-p\right)_{(V)}\Big{\rVert}\leq\Delta/\varepsilon.

To prove Lemma 5.5, we rewrite the condition $\lVert x-a_{i}\rVert\leq\lVert x-a_{j}\rVert$ as $\langle x-p-(\tfrac{1}{2}(a_{i}+a_{j})-p),a_{i}-a_{j}\rangle\geq 0$. Then we write each vector in terms of their projection on $u$ and $V$ and use the above lemma to bound each of the terms.

It suffices to show that for any $a_{i}\in S_{i,j}^{(\text{nice})}$, $a_{j}\in S_{j,i}^{(\text{nice})}$, and $x\in C_{i}$, $\lVert x-a_{i}\rVert\leq\lVert x-a_{j}\rVert$. Then by Lemma 5.10 above,

where the first inequality follows because of equality on the first term and Cauchy-Schwarz on the rest. So, for all $a_{i}\in S_{i,j}^{(\text{nice})}$, $a_{j}\in S_{j,i}^{(\text{nice})}$, and $x\in C_{i}$, $x$ is closer to $a_{i}$ than $a_{j}$. ∎

Robust k𝑘k-means

A simple extension of algorithm 5.1 does well even in the presence of adversarial noise for instances with $(\rho,\Delta,\varepsilon)$-separation for large enough $\rho$. Specifically, we consider the following model.

Let $w_{\max}=\max\lvert C_{i}\rvert/n$ and let $w_{\min}=\min\lvert C_{i}\rvert/n$ be the maximum and minimum weight of clusters. We will assume that $\eta<w_{\min}$.

Given $X\cup Z$ where $X$ satisfies $(\rho,\Delta,\varepsilon)$-separation for

$\lvert X\rvert=n$ and $\lvert Z\rvert\leq\eta n$ for $\eta<w_{\min}$, there exists values of $r,t$ such that Algorithm 6.1 returns a clustering consistent with $C_{1},\dots,C_{k}$ on $X$. Algorithm 6.1 can be implemented in $\widetilde{O}(n^{2}kd)$ time.

The proof of this theorem is similar to the proof of Theorem 5.2 and can be found in Appendix C.

Experimental results

We evaluate Algorithm 5.1 on multiple real world datasets and compare its performance to the performance of $k$-means++, and also check how well these datasets satisfy our geometric conditions.

Experiments were run on unnormalized and normalized versions of four labeled datasets from the UCI Machine Learning Repository: Wine ($n=178$, $k=3$, $d=13$), Iris ($n=150$, $k=3$, $d=4$), Banknote Authentication ($n=1372$, $k=2$, $d=5$), and Letter Recognition ($n=20,000$, $k=26$, $d=16$). Normalization was used to scale each feature to unit range.

The cost of the solution returned by Algorithm 5.1 for each of the normalized and unnormalized versions of the datasets is recorded in Table 1 column 2. Our guarantees show that under $(\rho,\Delta,\varepsilon)$-separation for appropriate values of $\rho$ (see section 5), the algorithm will find the optimal clustering after a single iteration of Lloyd’s algorithm. Even when $\rho$ does not satisfy our requirement, we can use our algorithm as an initialization heuristic for Lloyd’s algorithm. We compare our initialization with the $k$-means++ initialization heuristic ($D^{2}$ weighting). In Table 1, this is compared to the smallest initialization cost of 1000 trials of $k$-means++ on each of the datasets, the solution found by Lloyd’s algorithm using our initialization and the smallest $k$-means cost of 100 trials of Lloyd’s algorithm using a $k$-mean++ initialization.

As the ground truth clusterings in our datasets are not in general linearly separable, we consider the clusters given by Lloyd’s algorithm initialized with the ground truth solutions.

Values of $\varepsilon$ for Lemma 3.4. We calculate the maximum value of $\varepsilon$ such that every pair of clusters satisfies the angular and margin separations implied by $\varepsilon$-APS (Lemma 3.4). The results are recorded in Table 2. We see that the average value of $\varepsilon$ lies approximately in the range $(0.01,0.1)$.

Values of $(\rho,\Delta,\varepsilon)$-separation. We attempt to measure the values of $\rho$, $\Delta$, and $\varepsilon$ in the datasets. For $\eta=0.05,0.1$, $\varepsilon=0.1,0.01$, and a pair of clusters $C_{i}$, $C_{j}$, we calculate $\rho$ as the maximum margin separation a pair of axis-aligned cones with half-angle $\arctan(1/\varepsilon)$ can have while capturing a $(1-\eta)$-fraction of all points. For some datasets and values for $\eta$ and $\varepsilon$, there may not be any such value of $\rho$, in this case we leave the corresponding entry blank. These results are collected in Table 3.

The clustering returned by our algorithm recovers well ($\approx 97\%$) the solution returned by Lloyd’s algorithm initialized with the ground truth for Wine, Iris, and Banknote Authentication across normalized and unnormalized datasets.

Acknowledgments

The authors are grateful to Avrim Blum for numerous helpful discussions regarding the perceptron algorithm.

References

Appendix A k𝑘k-means clustering for k=2𝑘2k=2

Let $r=(1/\gamma)^{2}+1$. Consider the performance of the perceptron algorithm on $r$ consecutive runs of the $y_{1},\dots,y_{n}$, i.e., let the input be

A.2 Proof of Lemmas 4.5, 4.6

We state two lemmas that follow immediately from Lemma 3.4 and will be useful for the proofs in this section.

In particular, for $x\in C_{1}$, $\langle x-p,u\rangle\geq\varepsilon D$ and for $x\in C_{2}$, $\langle x-p,u\rangle\leq-\varepsilon D$.

There exist points $a\in C_{1}$, $b\in C_{2}$ such that $\langle a-p,u\rangle\leq\Delta/2$ and $\langle b-p,-u\rangle\leq\Delta/2$.

Note that $\langle\mu_{1}-p,u\rangle=\frac{1}{\lvert C_{1}\rvert}\sum_{x\in C_{1}}\langle x-p,u\rangle$. As $\langle\mu_{1}-p,u\rangle=\Delta/2$, there must be some $a\in C_{1}$ such that $\set{a-p,u}\leq\Delta/2$. The second assertion is proved similarly. ∎

Lemma 4.6

Note that Lemmas A.1 and 4.5 together imply that we cannot have an instance with $\varepsilon>1/2$.

There is no $\varepsilon$-APS $k$-means clustering instance for $\varepsilon>1/2$.

The following lemma bounds $\delta=\lVert a-b\rVert$ in terms of $\varepsilon$, $D$.

Let $a,b\in X$ be points satisfying Lemma 4.5. Then,

For the first inequality, $\left\lVert a-b\right\rVert\geq\lvert\langle u,a-b\rangle\rvert=\lvert\langle u,a-p\rangle-\langle u,b-p\rangle\rvert$. Then by Lemma A.1, $\lVert a-b\rVert\geq 2\varepsilon D$.

For the second inequality, $\left\lVert a-b\right\rVert\leq\left\lVert a-p\right\rVert+\left\lVert p-b\right\rVert$. By assumption, $\langle a-p,u\rangle\leq\Delta/2$. Then by Lemma A.2, $\left\lVert a-p\right\rVert\leq\sqrt{(1+\varepsilon^{2})/\varepsilon^{2}}D/2$. Similarly, $\left\lVert b-p\right\rVert\leq\sqrt{(1+\varepsilon^{2})/\varepsilon^{2}}D/2$. ∎

Finally, we restate and prove Lemma 4.6 below.

There exists constant $c_{1}$ such that for any $a,b$ satisfying Lemma A.2, the corresponding instance $Y_{a,b}$ has

We bound each term in the minimization individually. Let $i\in[n]$, then

From Lemma A.2, $\lvert\langle x_{i}-p,u\rangle\rvert\geq\sqrt{\frac{\varepsilon^{2}}{1+\varepsilon^{2}}}\left\lVert x_{i}-p\right\rVert\geq\frac{\varepsilon}{1+\varepsilon}\left\lVert x_{i}-p\right\rVert$

By Lemma A.2, $\left\lVert x_{i}\right\rVert^{2}\leq 2\left\lVert x_{i}-p\right\rVert^{2}+2\left\lVert p\right\rVert^{2}\leq 2\left\lVert x_{i}-p\right\rVert^{2}+\frac{1}{2}\frac{1+\varepsilon^{2}}{\varepsilon^{2}}{D^{2}}$

From Lemma A.4, $\delta^{2}\leq\frac{1+\varepsilon^{2}}{\varepsilon^{2}}D^{2}$

As $p$ and the origin both lie on the line between $\mu_{1}$ and $\mu_{2}$, $\lvert\langle p,u\rangle\rvert\leq\frac{D}{2}\leq\frac{\delta}{4\varepsilon}$

From Lemma A.1, $\left\lVert x_{i}-p\right\rVert\geq\varepsilon D$

As $\varepsilon\leq 1/2$ by Lemma A.3, we can bound the fraction below by some constant $c_{1}\approx 0.563$. ∎

Appendix B k𝑘k-means clustering for general k𝑘k

Any connected component only contains points from a single cluster.

For all $i,j$, $S_{i}^{(\text{core})}\supseteq S_{i,j}^{(\text{nice})}$. There is a point $x\in C_{i}$ such that $x\in S_{i}^{(\text{core})}\cap S_{i,j}^{(\text{nice})}$.

For all $i,j$, let $A_{i,j}=\set{x\in C_{i}}{\langle x-\mu_{i},u\rangle\leq\beta\Delta}$. Then, $\lvert A_{i,j}\rvert\geq\frac{\beta}{1+\beta}\lvert C_{i}\rvert$.

For all $i$, $S_{i}^{(\text{core})}\cap X$ is connected in $G$.

For all $i,j$, $A_{i,j}$ is connected in $G$.

The largest component, $K_{i}$, in each cluster contains $A_{i,j}$ for each $j\neq i$. In particular, $\lvert K_{i}\rvert\geq\frac{\beta}{1+\beta}\lvert C_{i}\rvert$, and $K_{i}$ contains $S_{i}^{(\text{core})}\cap X$.

Let $x\in C_{i}$ and $y\in C_{j}$. Then $\lVert x-y\rVert\geq\lvert\langle x-y,u\rangle\rvert\geq\rho$, thus no edge connecting points in different clusters is added to $G$.

For $x\in S_{i,j}^{(\text{nice})}$, $\lVert(x-\mu_{i})_{(V)}\rVert\leq\frac{1}{\varepsilon}(\Delta-\lVert(x-\mu_{i})_{(u)}\rVert)$, hence $\lVert x-\mu_{i}\rVert\leq\Delta/\varepsilon$. Recall $\mu_{i}$ is the mean of the points in cluster $C_{i}$. By an averaging argument, $S_{i,j}^{(\text{nice})}\cap X=\set{x\in C_{i}}{\langle x-(\mu_{i}-\Delta u),u\rangle\leq\Delta}$ is nonempty and hence $S_{i}^{(\text{core})}\cap S_{i,j}^{(\text{nice})}$ is nonempty.

$\mu_{i}$ is the mean of the points in cluster $C_{i}$. By an averaging argument, $\lvert A_{i,j}\rvert\Delta-(\lvert C_{i}\rvert-\lvert A_{i,j}\rvert)\beta\Delta\geq 0$. Rearranging, $\lvert A_{i,j}\rvert\geq\frac{\beta}{1+\beta}\lvert C_{i}\rvert$.

For $x,y\in S_{i}^{(\text{core})}$, $\lVert x-y\rVert\leq 2\Delta/\varepsilon$. Thus for $\rho=\Omega(\Delta/\varepsilon)$, the points $S_{i}^{(\text{core})}\cap X$ are connected.

From 2 above, $S_{i,j}^{(\text{nice})}\cap X$ is nonempty; fix such a point $x$. For $y\in A_{i,j}$, $\lVert x-y\rVert^{2}=\lVert(x-y)_{(u)}\rVert^{2}+\lVert(x-y)_{(V)}\rVert^{2}\leq\left((\beta+1)\Delta\right)^{2}+\left((\beta+1)\Delta/\varepsilon\right)^{2}$. Thus for $\rho=\Omega(\beta\Delta/\varepsilon)$, all of $A_{i,j}$ is connected through $x$.

Let $K_{i}$ be the component containing $S_{i}^{(\text{core})}\cap X$. By 2 above, for all $j$ there exists a point $x_{(j)}\in S_{i}^{(\text{core})}$ such that $x_{(j)}\in S_{i,j}^{(\text{nice})}\subseteq A_{i,j}$. Then as $A_{i,j}$ is connected, $K_{i}$ must also contain $A_{i,j}$. As $\lvert K_{i}\rvert\geq\lvert A\rvert$ and $\beta\geq 1$, part 3 above tells us that $K_{i}$ is the largest connected component in $C_{i}$.

B.2 Proof of Lemma 5.10

Suppose $\rho=\Omega(\Delta/\varepsilon^{2})$. Then, for $a_{i}\in S_{i,j}^{(\text{nice})}$ and $a_{j}\in S_{j,i}^{(\text{nice})}$, we have

$\lVert(a_{i}-a_{j})_{(u)}\rVert\geq\frac{\lVert(a_{i}-a_{j})_{(V)}\rVert}{\varepsilon}$,

$\langle\frac{a_{i}+a_{j}}{2}-p,u\rangle\leq\frac{\Delta}{2}$, and

\Big{\lVert}\left(\frac{a_{i}+a_{j}}{2}-p\right)_{(V)}\Big{\rVert}\leq\Delta/\varepsilon.

We have $\lVert(a_{i}-a_{j})_{(V)}\rVert\leq 2\Delta/\varepsilon$. On the other hand, $\rho\leq\lVert(a_{i}-a_{j})_{(u)}\rVert$. Thus the inequality holds for $\rho\geq 2\Delta/\varepsilon^{2}$.

$\langle a_{i}+a_{j}-2p,u\rangle=\langle a_{i}-p,u\rangle+\langle a_{j}-p,u\rangle\leq D_{i,j}/2+(-D_{i,j}/2+\Delta)=\Delta$. Multiplying by $1/2$ gives the desired inequality.

$\lVert(a_{i}+a_{j}-2p)_{(V)}\rVert\leq\lVert(a_{i}-p)_{(V)}\rVert+\lVert(a_{j}-p)_{(V)}\rVert\leq 2\Delta/\varepsilon$. Multiplying by $1/2$ gives the desired inequality.

Appendix C Robust k𝑘k-means

For completeness, we restate Algorithm 6.1 and Theorem 6.2.

Given $X\cup Z$ where $X$ satisfies $(\rho,\Delta,\varepsilon)$-separation for

$\lvert X\rvert=n$, and $\lvert Z\rvert\leq\eta n$ for $\eta<w_{\min}$, there exists values of $r,t$ such that Algorithm 6.1 returns a clustering consistent with $C_{1},\dots,C_{k}$ on $X$. Algorithm 6.1 can be implemented in $\widetilde{O}(n^{2}kd)$ time.

Define the following extended and robust versions of the regions defined in Section 5. Given $i,j$, let $C_{i},C_{j}$ be the corresponding clusters with means $\mu_{i},\mu_{j}$. Let $u=\frac{\mu_{i}-\mu_{j}}{\lVert\mu_{i}-\mu_{j}\rVert}$ be the unit vector in the inter-mean direction.

$S_{i,j}^{(\text{e nice})}=\set{x\in S_{i,j}^{(\text{cone})}}{\langle x-\mu_{i},u\rangle\leq\alpha\Delta}$,

$S_{i}^{(\text{r good})}=\bigcap_{j\neq i}S_{i,j}^{(\text{r e nice})}$.

Again, it suffices to prove the following two lemmas. Lemma C.2 states that the initialization returned by the INITIALIZE subroutine satisfies certain properties when given $r,t$. As in the case of Algorithm 5.1, this algorithm uses $r$ and $t$ as thresholds. Hence, it is possible to guess $r$ from the $\binom{n}{2}$ pairwise edge lengths and $t$ from $[n]$ if necessary. Lemma C.3 states that the ASSIGN subroutine correctly clusters all points given an initialization satisfying these properties.

Given $X\cup Z$ where $X$ is a $(\rho,\Delta,\varepsilon)\text{-separated}$ instance with $\rho=\Omega(\alpha\Delta/\varepsilon^{2})$ and $\eta<w_{\min}$, for the choices of $r$ and $t$ as above, the INITIALIZE subroutine finds a set $\set{a_{1},\dots,a_{k}}$ where $a_{i}\in S_{i}^{(\text{r good})}$