Fast Noise Removal for $k$-Means Clustering

Sungjin Im Mahshid Montazer Qaem Benjamin Moseley

University of California at Merced University of California at Merced Carnegie
Mellon University

Xiaorui Sun Rudy Zhou

University of Illinois at Chicago Carnegie Mellon University

###### Abstract

This paper considers $k$-means clustering in the presence of noise. It is
known that $k$-means clustering is highly sensitive to noise, and thus noise
should be removed to obtain a quality solution. A popular formulation of this
problem is called _$k$ -means clustering with outliers_. The goal of $k$-means
clustering with outliers is to discard up to a specified number $z$ of points
as noise/outliers and then find a $k$-means solution on the remaining data.
The problem has received significant attention, yet current algorithms with
theoretical guarantees suffer from either high running time or inherent loss
in the solution quality. The main contribution of this paper is two-fold.
Firstly, we develop a simple greedy algorithm that has _provably_ strong worst
case guarantees. The greedy algorithm adds a simple preprocessing step to
remove noise, which can be combined with any $k$-means clustering algorithm.
This algorithm gives the first pseudo-approximation-preserving reduction from
$k$-means with outliers to $k$-means without outliers. Secondly, we show how
to construct a coreset of size $O(k\log n)$. When combined with our greedy
algorithm, we obtain a scalable, near linear time algorithm. The theoretical
contributions are verified experimentally by demonstrating that the algorithm
quickly removes noise and obtains a high-quality clustering.

##  1 Introduction

Clustering is a fundamental unsupervised learning method that offers a compact
view of data sets by grouping similar input points. Among various clustering
methods, $k$-means clustering is one of the most popular clustering methods
used in practice, which is defined as follows: given a set $X$ of $n$ points
in Euclidean space111The input space can be extended to an arbitrary metric
space. $\mathbb{R}^{d}$ and a target number of clusters $k$, the goal is to
choose a set $C$ of $k$ points from $\mathbb{R}^{d}$ as centers, so as to
minimize the $\ell_{2}$-loss, i.e., the sum of the squared distances of every
point $x\in X$ to its closest center in $C$.

Due to its popularity, $k$-means clustering has been extensively studied for
decades both theoretically and empirically, and as a result, various novel
algorithms and powerful underlying theories have been developed. In
particular, because the clustering problem is NP-hard, several constant-factor
approximation algorithms have been developed (Charikar and Guha, 1999; Kanungo
et al., 2004; Kumar et al., 2004; Feldman et al., 2007), meaning that their
output is always within an $O(1)$ factor of the optimum. One of the most
successful algorithms used in practice is $k$-means++ (Arthur and
Vassilvitskii, 2007). The algorithm $k$-means++ is a preprocessing step used
to set the initial centers when using Lloyd’s algorithm (Lloyd, 1982). Lloyd’s
algorithm is a simple local search heuristic that alternates between updating
the center of every cluster and reassigning points to their closest centers.
$k$-means++ has a provable approximation guarantee of $O(\log k)$ by carefully
choosing the initial centers.

$k$-means clustering is highly sensitive to noise, which is present in many
data sets. Indeed, it is not difficult to see that the $k$-means clustering
objective can vary significantly even with the addition of a single point that
is far away from the true clusters. In general, it is a non-trivial task to
filter out noise; without knowing the true clusters, we cannot identify noise,
and vice versa. While there are other clustering methods, such as density-
based clustering (Ester et al., 1996), that attempt to remove noise, they do
not replace $k$-means clustering because they are fundamentally different than
$k$-means.

Consequently, there have been attempts to study $k$-means clustering in the
presence of noise. The following problem formulation is the most popular
formulation in the theory (Chen, 2008; Charikar et al., 2001; McCutchen and
Khuller, 2008; Guha et al., 2017), machine learning (Malkomes et al., 2015;
Chawla and Gionis, 2013; Li and Guo, 2018) and database communities (Gupta et
al., 2017). Note that traditional $k$-means clustering is a special case of
this problem when $z=0$. Throughout, for $x,y\in\mathbb{R}^{d}$, we let
$d(x,y)$ denote the $\ell_{2}$ distance between $x$ and $y$. For a subset of
points $Y$, let $d(x,Y):=\min_{y\in Y}d(x,y)$.

######  Definition 1 ($k$-Means with Outliers).

In this problem we are given as input a subset $X$ of $n$ points in
$\mathbb{R}^{d}$, a parameter $k\in\mathbb{N}$ (number of centers), and a
parameter $z\in\mathbb{N}$ (number of outliers). The goal is to choose a
collection of $k$ centers, $C\subseteq\mathbb{R}^{d}$, to minimize:
$\sum_{x\in X_{z}(C)}d^{2}(x,C)$ , where $X_{z}(C)\subseteq X$ is the subset
of $n-z$ input points with the smallest distances to $C$.

Because this problem generalizes $k$-means clustering, it is NP-hard, and in
fact, turns out to be significantly more challenging. The only known constant
approximations (Chen, 2008; Krishnaswamy et al., 2018) are highly
sophisticated and are based on complicated local search or linear program
rounding. They are unlikely to be implemented in practice due to their runtime
and complexity. Therefore, there have been strong efforts to develop simpler
algorithms that offer good approximation guarantees when allowed to discard
more than $z$ points as outliers (Charikar et al., 2001; Meyerson et al.,
2004; Gupta et al., 2017), or heuristics (Chawla and Gionis, 2013).
Unfortunately, the aforementioned algorithms with theoretical guarantees
suffer from either high running time or inherent loss in solution quality.

In contrast , concurrently with our work, Bhaskara et al. (2019) developed a
simple algorithm for $k$-means with outliers that gives a good approximation
guarantee when allowed to discard more than $z$ outliers or use more than $k$
centers, which we discuss in more detail when we describe our results.

###  1.1 Our Results and Contributions

The algorithmic contribution of this paper is two-fold, and further these
contributions are validated by experiments. In this section, we state our
contribution and discuss it in detail compared to the previous work.

#### Simple Preprocessing Step for Removing Outliers with Provable Guarantees:

In this paper we develop a simple preprocessing step, which we term NK-means,
to effectively filter out outliers. NK-means stands for noise removal for
$k$-means. Our proposed preprocessing step can be combined with _any_
algorithm for $k$-means clustering. Despite the large amount of work on this
problem, we give the _first_ reduction to the standard $k$-means problem. In
particular, NK-means can be combined with the popular $k$-means++. The
algorithm is the fastest known algorithm for the $k$-means with outliers
problem. Its speed and simplicity gives it the potential to be used in
practice. Formally, given an $\alpha$-approximation for $k$-means clustering,
we give an algorithm for $k$-means with outliers that is guaranteed to discard
up to $O(kz)$ points such that the cost of remaining points is at most
$O(\alpha)$ times the optimum that discards up to exactly $z$ points. While
the theoretical guarantee on the number of outliers is larger than $z$ on
worst-case inputs, we show that NK-means removes at most $O(z)$ outliers under
the assumption that every cluster in an optimal solution has at least $3z$
points. We believe that this assumption captures most practical cases since
otherwise significant portions of the true clusters can be discarded as
outliers. In actual implementation, we can guarantee discarding exactly $z$
points by discarding the farthest $z$ points from the centers we have chosen.
It is worth keeping in mind that all (practical) algorithms for the problem
discard more than $z$ points to have theoretical guarantees (Charikar et al.,
2001; Meyerson et al., 2004; Gupta et al., 2017; Bhaskara et al., 2019).

When compared to the concurrent work of Bhaskara et al. (2019), our work
differs in two main ways. Firstly, our algorithm consists of a pre-processing
step that can be combined with any $k$-means algorithm, such as $k$-means++,
while theirs consists of a modification to the standard $k$-means++ algorithm.
Further, our algorithm throws away a multiplicative $O(k)$-factor extra
outliers in the worst case and uses no extra centers, while in their work they
prove a trade-off between extra outliers and extra centers. In particular,
they obtain a $O(\log k)$ approximation for $k$-means with outliers using an
extra multiplicative $O(\log k)$ outliers and no extra centers, and a
$O(1)$-approximation using an extra multiplicative $O(1)$ outliers and
centers.

#### New Coreset Construction:

When the data set is large, a dominant way to speed up clustering is to first
construct a coreset and then use the clustering result of the coreset as a
solution to the original input. Informally, a set of (weighted) points $Y$ is
called a coreset of $X$ if a good clustering of $Y$ is also a good clustering
of $X$ (see Section 4.1 for the formal definition of coreset.)

The idea is that if we can efficiently construct such $Y$, which is
significantly smaller than $X$, then we can speed up any clustering algorithm
with little loss of accuracy. In this paper, we give an algorithm to construct
a coreset of size $O(k\log n)$ for $k$-means with outliers. Importantly, the
coreset size is independent of $z$ and $d$ \- the number of outliers and
dimension, respectively.

#### Experimental Validation:

Our new coreset enables the implementation and comparison of all potentially
practical algorithms, which are based on primal-dual (Charikar et al., 2001),
uniform sampling (Meyerson et al., 2004), or local search (Chawla and Gionis,
2013; Gupta et al., 2017). It is worth noting that, to the best of our
knowledge, this is the first paper to implement the primal-dual based
algorithm (Charikar et al., 2001) and test it for large data sets. We also
implemented natural extensions of $k$-means++ and our algorithm NK-means. We
note that for fair comparison, once each algorithm chose the $k$ centers, we
considered all points and discarded the farthest $z$ points. Our experiments
show that our NK-means consistently outperforms other algorithms for both
synthetic and real-world data sets with little running time overhead as
compared to $k$-means++.

###  1.2 Comparison to the Previous Work

#### Algorithms for $k$-Means with Outliers:

To understand the contribution of our work, it is important to contrast the
algorithm with previous work. We believe a significant contribution of our
work is the algorithmic simplicity and speed as well as the theoretical bounds
that our approach guarantees. In particular, we will discuss why the previous
algorithms are difficult to use in practice.

The first potentially practical algorithm developed is based on primal-dual
(Charikar et al., 2001). Instead of solving a linear program (LP) and
converting the solution to an integer solution, the primal-dual approach only
uses the LP and its dual to guide the algorithm. However, the algorithm does
not scale well and is not easy to implement. In particular, it involves
increasing variables uniformly, which requires $\Omega(n^{2})$ running time
and extra care to handle precision issues of fractional values. As mentioned
before, this algorithm was never implemented prior to this paper. Our
experiments show that this algorithm considerably under-performs compared to
other algorithms.

The second potentially practical algorithm is based on uniform sampling
(Meyerson et al., 2004). The main observation of Meyerson et al. (2004) is
that if every cluster is large enough, then a small uniform sample can serve
as a coreset. This observation leads to two algorithms for $k$-means
clustering with outliers: (i) (implicit) reduction to $k$-means clustering via
conservative uniform sampling and (ii) (explicit) aggressive uniform sampling
plus primal-dual (Charikar et al., 2001). In (i) it can be shown that a
constant approximate $k$-means clustering of a uniform sample of size $n/(2z)$
is a constant approximation for $k$-means clustering with outliers, under the
assumption that every cluster has size $\Omega(z\log k)$. Here, the main idea
is to avoid any noise by sampling conservatively. Although this assumption is
reasonable as discussed before, the real issue is that conservative uniform
sampling doesn’t give a sufficiently accurate sketch to be adopted in
practice. For example, if there are $1\%$ noise points, then the conservative
uniform sample has only $50$ points. In (ii), a more aggressive uniform
sampling is used and followed by the primal dual (Charikar et al., 2001). It
first obtains a uniform sample of size $\Theta(k(n/z)\log n)$; then the
(expected) number of outliers in the sample becomes $\Theta(k\log n)$. This
aggressive uniform sampling turns out to have very little loss in terms of
accuracy. However, as mentioned before, the primal-dual algorithm under-
performs compared to other algorithms in speed and accuracy.

Another line of algorithmic development has been based on local search (Chawla
and Gionis, 2013; Gupta et al., 2017). The algorithm in Chawla and Gionis
(2013) guarantees the convergence to a local optimum, but has no approximation
guarantees. The other algorithm (Gupta et al., 2017) is an
$O(1)$-approximation but theoretically it may end up with discarding $O(kz\log
n)$ outliers. These local search algorithms are considerably slower than our
method and the theoretical guarantees require discarding many more points.

To summarize, there is a need for a fast and effective algorithm for $k$-means
clustering with outliers.

#### Coresets for $k$-Means with Outliers:

The other main contribution of our work is a coreset for $k$-means with
outliers of size $O(k\log n)$ \- independent of the number of outliers $z$ and
dimension $d$.

The notion of coreset we consider is related to the concept of a _weak
coreset_ in the literature - see e.g. Feldman and Langberg (2011) for
discussion of weak coresets and other types of coresets. Previous coreset
constructions (some for stronger notions of coreset) have polynomial
dependence on the number of outliers $z$ (Gupta et al., 2017), inverse
polynomial dependence on the fraction of outliers $\frac{z}{n}$ (Meyerson et
al., 2004; Huang et al., 2018), or polynomial dependence on the dimension $d$
(Huang et al., 2018). Thus, all coresets constructed in the previous work can
have large size for some value of $z$, e.g. $z=\Theta(\sqrt{n})$, or for large
values of $d$. In contrast, our construction is efficient for _all_ values of
$z\in[0,n]$ and yields coresets of size with no dependence on $d$ or $z$.

###  1.3 Overview of Our Algorithms: NK-means and SampleCoreset

Our preprocessing step, NK-means, is reminiscent of density-based clustering.
Our algorithm tags an input point as light if it has relatively few points
around it. Formally, a point is declared as light if it has less than $2z$
points within a certain distance threshold $r$, which can be set by binary
search. Then a point is discarded if it only has light points within distance
$r$. We emphasize that the threshold is chosen by the algorithm, not by the
algorithm user, unlike in density-based clustering. While our preprocessing
step looks similar to the algorithm for $k$-center clustering (Charikar et
al., 2001), which optimizes the $\ell_{\infty}$-loss, we find it surprising
that a similar idea can be used for $k$-means clustering.

It can take considerable time to label each point light or not. To speed up
our algorithm, we develop a new corest construction for $k$-means with
outliers. The idea is relatively simple. We first use aggressive sampling as
in Meyerson et al. (2004). The resulting sample has size $O(\frac{kn}{z}\log
n)$ and includes $O(k\log n)$ outliers with high probability. Then we use
$k$-means++ to obtain $O(k\log n)$ centers. As a result, we obtain a high-
quality coreset of size $O(k\log n)$. Interestingly, to our best knowledge,
combining aggressive sampling with another coreset for $k$-means with outliers
has not been considered in the literature.

###  1.4 Other Related Work

Due to the vast literature on clustering, we refer the reader to Aggarwal and
Reddy (2013); Kogan et al. (2006); Jain et al. (1999) for an overview and
survey of the literature. $k$-means clustering can be generalized by
considering other norms of loss, and such extensions have been studied under
different names. When the objective is $\ell_{1}$-norm loss, the problem is
called $k$-medians. The $k$-median and $k$-mean clustering problems are
closely related, and in general the algorithm and analysis for one can be
readily translated into one for the other with an $O(1)$ factor loss in the
approximation ratio. Constant approximations are known for $k$-medians and
$k$-means based on linear programming, primal-dual, and local search (Arya et
al., 2004; Charikar et al., 2002; Charikar and Guha, 1999). While its
approximation ratio is $O(\log k)$, the $k$-means++ algorithm is widely used
in practice for $k$-means clustering due to its practical performance and
simplicity. When the loss function is $\ell_{\infty}$, the problem is known as
$k$-centers and a $3$-approximation is known for $k$-centers clustering with
outliers (Charikar et al., 2001). For recent work on these outlier problems in
distributed settings, see Malkomes et al. (2015); Li and Guo (2018); Guha et
al. (2017); Chen et al. (2018).

##  2 Preliminaries

In this paper we will consider the Euclidean $k$-means with outliers problem
as defined in the introduction. Note that the $\ell_{2}$-distance satisfies
the _triangle inequality_ , so for all $x,y,z\in\mathbb{R}^{d}$, $d(x,z)\leq
d(x,y)+d(y,z)$. Further, the _approximate triangle inequality_ will be useful
to our analyses (this follows from the triangle inequality): $d^{2}(x,z)\leq
2d^{2}(x,y)+2d^{2}(y,z)\quad\forall x,y,z\in\mathbb{R}^{d}$. Given a set of
centers $C\subset\mathbb{R}^{d}$, we say that the _assignment cost_ of $x\in
X$ to $C$ is $d^{2}(x,C)$. For $k$-means with outliers, a set, $C$, of $k$
centers naturally defines a clustering of the input points $X$ as follows:

######  Definition 2 (Clustering).

Let $C=\\{c_{1},\dots,c_{k}\\}\subset\mathbb{R}^{d}$ be a set of $k$ centers.
A clustering of $X$ defined by $C$ is a partition $C_{1}\cup\dots\cup C_{k}$
of $X_{z}(C)$ satisfying: For all $x\in X_{z}$ and $c_{i}\in C$, $x\in
C_{i}\iff d(x,C)=d(x,c_{i})$, where ties between $c_{i}$’s are broken
arbitrarily but consistently.

In summary, for the $k$-means with outliers problem, given a set $C$ of $k$
centers, we assign each point in $X$ to its closest center in $C$. Then we
exclude the $z$ points of $X$ with the highest assignment cost from the
objective function (these points are our outliers.) This procedure defines a
clustering of $X$ with outliers.

Notations: For $n\in\mathbb{N}$, we define $[n]:=\\{1,\dots,n\\}$. Recall that
as in the introduction, for any finite
$Y\subset\mathbb{R}^{d},x\in\mathbb{R}^{d}$, we define: $d(x,Y):=\min_{y\in
Y}d(x,y)$. For any $x\in\mathbb{R}^{d},X\subseteq\mathbb{R}^{d},r>0$, we
define the $X$-ball centered at $x$ with radius $r$ by $B(x,r):=\\{y\in X\mid
d(x,y)\leq r\\}$. For a set of $k$ centers, $C\subset\mathbb{R}^{d}$, and
$z\in\mathbb{N}$, we define the _$z$ -cost_ of $C$ by
$f_{z}^{X}(C):=\sum_{x\in X_{z}(C)}d^{2}(x,C).$ Recall that we define
$X_{z}(C)\subset X$ to be the subset of points of $X$ excluding the $z$ points
with highest assignment costs. Thus the $z$-cost of $C$ is the cost of
clustering $X$ with $C$ while excluding the $z$ points with highest assignment
costs. As shorthand, when $z=0$ – so when we consider the $k$-means problem
without outliers – we will denote the $0$-cost of clustering $X$ with $C$ by
$f^{X}(C):=f^{X}_{0}(C)$. Further, we say a set of $k$ centers $C^{*}$ is an
_optimal $z$-solution_ if it minimizes $f_{z}^{X}(C)$ over all choices of $k$
centers, $C$. Then we define $Opt(X,k,z):=f_{z}^{X}(C^{*})$ to be the optimal
objective value of the $k$-means with outliers instance $(X,k,z)$.
Analogously, for the $k$-means without outliers problem, we denote the optimal
objective value of the $k$-means instance $(X,k)$ by $Opt(X,k)$.

##  3 NK-means Algorithm

In this section, we will describe our algorithm, NK-means, which turns a
$k$-means algorithm without outliers to an algorithm for $k$-means with
outliers in a black box fashion. We note that the algorithm naturally extends
to $k$-medians with outliers and general metric spaces. For the remainder of
this section, let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbb{R}^{d}$,
$k\in\mathbb{N}$ , and $z\in\mathbb{N}$ define an instance of $k$-means with
outliers.

Algorithm Intuition: The guiding intuition behind our algorithm is as follows:
We consider a ball of radius $r>0$ around each point $x\in X$. If this ball
contains many points, then $x$ is likely not to be an outlier in the optimal
solution.

More concretely, if there are more than $2z$ points in $x$’s ball, then at
most $z$ of these points can be outliers in the optimal solution. This means
that the majority of $x$’s neighbourhood is real points in the optimal
solution, so we can bound the assignment cost of $x$ to the optimal centers.
We call such points heavy.

There are $2$ main steps to our algorithm. First, we use the concept of heavy
points to decide which points are real points and those that are outliers.
Then we run a $k$-means approximation algorithm on the real points.

Formal Algorithm: Now we formally describe our algorithm NK-means. As input,
NK-means takes a $k$-means with outliers instance $(X,k,z)$ and an algorithm
for $k$-mean without outliers, $\mathcal{A}$, where $\mathcal{A}$ takes an
instance of $k$-means as input.

We will prove that if $\mathcal{A}$ is an $O(1)$-approximation for $k$-means
and the optimal clusters are sufficiently large with respect to $z$, then NK-
means outputs a good clustering that discards $O(z)$ outliers. More precisely,
we will prove the following theorem about the performance of NK-means:

######  Theorem 1.

Let $C$ be the output of $\textsc{NK-means}(X,k,z,\mathcal{A})$. Suppose that
$\mathcal{A}$ is an $\alpha$-approximation for $k$-means. If every cluster in
the clustering defined by $C^{*}$ has size at least $3z$, then
$f_{2z}^{X}(C)\leq 9\alpha\cdot Opt(X,k,z)$.

######  Corollary 1.

Let $C$ be the output of $\textsc{NK-means}(X,k,z,\mathcal{A})$. Suppose that
$\mathcal{A}$ is an $\alpha$-approximation. Then $f_{3kz+2z}^{X}(C)\leq
9\alpha\cdot Opt(X,k,z)$.

In other words, NK-means gives a pseudo-approximation-preserving reduction
from $k$-means with outliers to $k$-means, where any $\alpha$ approximation
for $k$-means implies a $9\alpha$ pseudo-approximation for $k$-means with
outliers that throws away $3kz+2z$ points as outliers.

Algorithm 1 for $k$-means with outliers

$\textsc{NK-means}(X,k,z,\mathcal{A})$

1: Suppose we know the optimal objective value $Opt:=Opt(X,k,z)$

2: Initialize $r\leftarrow 2(Opt/z)^{1/2}$, $Y\leftarrow\emptyset$

3: for each $x\in X$ do

4: Compute $B(x,r)$

5: if $\lvert B(x,r)\rvert\geq 2z$ then

6: Mark $x$ as heavy

7: end if

8: end for

9: for each $x\in X$ do

10: if $B(x,r)$ contains no heavy points then

11: Update $Y\leftarrow Y\cup\\{x\\}$

12: end if

13: end for

14: Output $C\leftarrow\mathcal{A}(X\setminus Y,k)$

###  3.1 Implementation Details

Here we describe a simple implementation of NK-means that achieves runtime
$O(n^{2}d)+T(n)$ assuming we know the optimal objective value, $Opt$, where
$T(n)$ is the runtime of the algorithm $\mathcal{A}$ on inputs of size $n$.
This assumption can be removed by running that algorithm for many guesses of
$Opt$, say by trying all powers of $2$ to obtain a $2$-approximation of $Opt$
for the correct guess.

For our experiments, we implement the loop in Line 3 by enumerating over all
pairs of points and computing their distance. This step takes time
$O(n^{2}d)$. We implement the loop in Line 9 by enumerating over all elements
in $B(x,r)$ and checking if it is heavy for each $x\in X$. This step takes
$O(n^{2})$. Running $\mathcal{A}$ on $(X\setminus Y,k)$ takes $T(n)$ time. We
summarize the result of this section in the following lemma:

######  Lemma 1.

Assuming that we know $Opt$ and that $\mathcal{A}$ takes time $T(n)$ on inputs
of size $n$, then NK-means can be implemented to run in time $O(n^{2}d)+T(n)$.

##  4 Coreset of Near Linear Size in k

In this section we develop a general framework to speed up any $k$-means with
outliers algorithm, and we apply this framework to NK-means to show that we
can achieve near-linear runtime. In particular, we achieve this by
constructing what is called a coreset for the $k$-means with outliers problem
of size $O(k\log n)$, which is _independent_ of the number of outliers, $z$.

###  4.1 Coresets for k-Means with Outliers

Our coreset construction will leverage existing constructions of coresets for
$k$-means with outliers. A coreset gives a good summary of the input instance
in the following sense:

######  Definition 3 (Coreset for $k$-Means with Outliers).

222Note that our definition of coreset is parameterized by the _number_ of
outliers, $z$, in contrast to previous work such as Meyerson et al. (2004) and
Huang et al. (2018), whose constructions are parametereized by the _fraction_
of outliers, $z/n$.

Let $(X,k,z)$ be an instance of $k$-means with outliers and $Y$ be a (possibly
weighted) subset of $\mathbb{R}^{d}$. We say the $k$-means with outliers
instance $(Y,k,z^{\prime})$ is an $(\alpha,\beta)$-coreset for $X$ if for any
set $C\subset\mathbb{R}^{d}$ of $k$-centers satisfying
$f_{\kappa_{1}z^{\prime}}^{Y}(C)\leq\kappa_{2}Opt(Y,k,z^{\prime})$ for some
$\kappa_{1},\kappa_{2}>0$, we have
$f_{\alpha\kappa_{1}z}^{X}(C)\leq\beta\kappa_{2}Opt(X,k,z)$.

In words, if $(Y,k,z^{\prime})$ is an $(\alpha,\beta)$ coreset for $(X,k,z)$,
then running any $(\kappa_{1},\kappa_{2})$-approximate $k$-means with outliers
algorithm on $(Y,k,z^{\prime})$ (meaning the algorithm throws away
$\kappa_{1}z^{\prime}$ outliers and outputs a solution with cost at most
$\kappa_{2}Opt(Y,k,z^{\prime})$) gives a
$(\alpha\kappa_{1},\beta\kappa_{2})$-approximate solution to $(X,k,z)$.

Note that if $Y$ is a weighted set with weights
$w:Y\rightarrow\mathbb{R}_{+}$, then the $k$-means with outliers problem is
analogously defined, where the objective is a weighted sum of assignment
costs: $\min\limits_{C}\sum_{y\in Y_{z}(C)}w(y)d^{2}(y,C)$. Further, note that
NK-means generalizes naturally to weighted $k$-means with outliers with the
same guarantees.

The two coresets we will utilize for our construction are k-means++ (Aggarwal
et al., 2009) and Meyerson’s sampling coreset (Meyerson et al., 2004). The
guarantees of these coresets are as follows:

######  Theorem 2 (k-means++).

Let $\textsc{k-means++}(X,k)$ denote running k-means++ on input points $X$ to
obtain a set $Y\subset X$ of size $k$. Further, let $Y_{1},\dots Y_{k}$ be the
clustering of $X$ with centers $y_{1},\dots,y_{k}\in Y$, respectively. We
define a weight function $w:Y\rightarrow\mathbb{R}_{+}$ by $w(y_{i})=\lvert
Y_{i}\rvert$ for all $y_{i}\in Y$. Suppose $Y=\textsc{k-means++}(X,32(k+z))$.
Then with probability at least $0.03$, the instance $(Y,k,z)$ where $Y$ has
weights $w$ is an $(1,124)$-coreset for the $k$-means with outliers instance
$(X,k,z)$.

######  Theorem 3 (Sampling).

Let $S$ be a sample from $X$, where every $x\in X$ is included in $S$
independently with probability
$p=\max(\frac{36}{z}\log(\frac{4nk^{2}}{z}),36\frac{k}{z}\log(2k^{3}))$. Then
with probability at least $1-\frac{1}{k^{2}}$, the instance $(S,k,2.5pz)$ is a
$(16,29)$-coreset for $(X,k,z)$.

Observe that k-means++ gives a coreset of size $O(k+z)$, and uniform sampling
gives a coreset of size $O(\frac{kn}{z}\log n)$ in expectation. If $z$ is
small, then k-means++ gives a very compact coreset for $k$-means with
outliers, but if $z$ is large – say $z=\Omega(n)$ – then k-means++ gives a
coreset of linear size. However, the case where $z$ is large is exactly when
uniform sampling gives a small coreset.

In the next section, we show how we can combine these two coresets to
construct a small coreset that works for all $z$.

###  4.2 Our Coreset Construction: SampleCoreset

Algorithm 2 Coreset Constuction for $k$-Means with Outliers

$\textsc{SampleCoreset}(X,k,z)$

1: Let
$p=\max(\frac{36}{z}\log(\frac{4nk^{2}}{z}),36\frac{k}{z}\log(2k^{3}))$.

2: if $p>1$ then

3: Output $Y\leftarrow\textsc{k-means++}(X,32(k+z))$.

4: else

5: Let $S$ be a sample drawn from $X$, where each $x\in X$ is included in $S$
independently with probability $p$.

6: Output $Y\leftarrow\textsc{k-means++}(S,32(k+2.5pz))$

7: end if

Using the above results, our strategy is as follows: Let $(X,k,z)$ be an
instance of $k$-means with outliers. If $p>1$, then we can show that
$z=O(k\log n)$, so we can simply run k-means++ on the input instance to get a
good coreset. Otherwise, $z$ is large, so we first subsample approximately
$\frac{kn}{z}$ points from $X$. Let $S$ denote the resulting sample. Then we
compute a coreset on $S$ of size $32(k+2.5pz)$, where we scale down the number
of outliers from $X$ proportionally.

Algorithm 2 formally describes our coreset construction. We will prove that
SampleCoreset outputs with constant probability a good coreset for the
$k$-means with outliers instance $(X,k,z)$ of size $O(k\log n)$. In
particular, we will show:

######  Theorem 4.

With constant probability, SampleCoreset outputs an $(O(1),O(1))$-coreset for
the $k$-means with outliers instance $(X,k,z)$ of size $O(k\log n)$ in
expectation.

###  4.3 A Near Linear Time Algorithm for k-Means With Outliers

Using SampleCoreset, we show how to speed up NK-means to run in near linear
time: Let $Y$ be the result of $\textsc{SampleCoreset}(X,k,z)$. Then, to
choose $k$ centers we run $\textsc{NK-means}(Y,k,z,\mathcal{A})$ if $p>1$;
otherwise, run $\textsc{NK-means}(Y,k,2.5pz,\mathcal{A})$, where $\mathcal{A}$
is any $O(1)$-approximate $k$-means algorithm with runtime $T(n)$ on inputs of
size $n$.

######  Theorem 5.

There exists an algorithm that outputs with a constant probability an
$O(1)$-approximate solution to $k$-means with outliers while discarding
$O(kz)$ outliers in expected time $O(kdn\log^{2}n)+T(k\log n)$.

##  5 Experiment Results

This section presents our experimental results. The main conclusions are:

  * •

Our algorithm NK-means almost always has the best performance and finds the
largest proportion of ground truth outliers. In the cases where NK-means is
not the best, it is competitive within 5%.

  * •

Our algorithm results in a stable solution. Algorithms without theoretical
guarantees have unstable objectives on some experiments.

  * •

Our coreset construction SampleCoreset allows us to run slower, more
sophisticated, algorithms with theoretical guarantees on large inputs. Despite
their theoretical guarantees, their practical performance is not competitive.

| Primal-Dual |  $k$-means– | Local Search | Uniform Sample | NK-means
---|---|---|---|---|---
run time > 4hrs | 9/16 | 1/16 | 8/16 | 0/16 | 0/16
precision < 0.8 | 2/16 | 0/16 | 0/16 | 4/16 | 0/16
total failure | 11/16 | 1/16 | 8/16 | 4/16 | 0/16
Table 1: Failure rates due to high run time or low precision.

The experiments shows that for a modest overhead for preprocessing, NK-means
makes $k$-means clustering more robust to noise.

Algorithms Implemented: Our new coreset construction makes it feasible to
compare many algorithms for large data sets. Without this, most known
algorithms for k-means with outliers become prohibitively slow even on
modestly sized data sets. In our experiments, the coreset construction we
utilize is SampleCoreset. More precisely, we first obtain a uniform sample by
sampling each point independently with probability $p=\min\\{\frac{2.5k\log
n}{z},1\\}$. Then, we run $k$-means++ on the sample to choose $k+pz$ centers –
the resulting coreset is of size $k+pz$.

Next we describe the algorithms tested. Besides the coreset construction, we
use $k$-means++ to mean running $k$-means++ and then Lloyd’s algorithm for
brevity. For more details, see Supplementary Material E. In the following, “on
coreset” refers to running the algorithm on the coreset as opposed to the
entire input. For fair comparison, we ensure each algorithm discards _exactly_
$z$ outliers regardless of the theoretical guarantee. At the end of each
algorithm’s execution, we discard the $z$ farthest points from the chosen $k$
centers as outliers.

Algorithms Tested:

  1. 1.

NK-means (plus $k$-means++ on coreset): We use NK-means with $k$-means++ as
the input $\mathcal{A}$. The algorithm requires a bound on the objective
$Opt$. For this, we considered powers of 2 in the range of $[n\min_{u,v\in
X}d^{2}(u,v),n\max_{u,v\in X}d^{2}(u,v)]$.

  2. 2.

$k$-means++ (on the original input): Note this algorithm is not designed to
handle outliers.

  3. 3.

$k$-means++ (on coreset): Same note as the above.

  4. 4.

Primal-dual algorithm of Charikar et al. (2001) (on coreset): A sophisticated
algorithm based on constructing an approximate linear program solution.

  5. 5.

Uniform Sample (conservative uniform sampling plus $k$-means++): We run
$k$-means++ on a uniform sample consisting of points sampled with probability
$1/(2z)$.

  6. 6.

$k$-means– (Chawla and Gionis, 2013) on coreset: This algorithm is a variant
of the Lloyd’s algorithm that executes each iteration of Lloyd’s excluding the
farthest $z$ points.

  7. 7.

Local search of Gupta et al. (2017) (on coreset) : This is an extension of the
well-known $k$-means local search algorithm.

Experiments: We now describe our experiments which were done on both synthetic
and real data sets.

#### Synthetic Data Experiments

We first conducted experiments with synthetic data sets of various parameters.
Every data set has $n$ equal one million points and $k,d\in\\{10,20\\}$ and
$z\in\\{10000,50000\\}$. Then we generated $k$ random Gaussian balls. For the
$i$th Gaussian we choose a center $c_{i}$ from $[-1/2,1/2]^{d}$ uniformly at
random. These are the true centers. Then, we add $n/k$ points drawn from
$\mathcal{N}(c_{i},1)$ for the $i$th Gaussian. Next, we add noise. Points that
are noise were sampled uniformly at random either from the same range
$[-1/2,1/2]^{d}$ or from a larger range $[-5/2,5/2]^{d}$ depending on the
experiment. We tagged the farthest $z$ points from the centers
$\\{c_{1},\ldots,c_{k}\\}$ as ground truth outliers. We consider all possible
$16$ combinations of $k,d,z$ values and the noise range.

Each experiment was conducted $3$ times, and we chose the result with the
minimum objective and measured the total running time over all $3$ runs. We
aborted the execution if the algorithm failed to terminate within $4$ hours.
All experiments were performed on a cluster using a single node with 20 cores
at 2301MHz and RAM size 128GB. Table 1 shows the number of times each
algorithm aborted due to high run time. Also we measured the recall, which is
defined as number of ground truth outliers reported by the algorithm, divided
by $z$, the number of points discarded. The recall was the same as the
precision in all cases, so we use precision in the remaining text. We choose
$0.8$ as the threshold for the acceptable precision and counted the number of
inputs for which each algorithm had precision lower than $0.8$. Our algorithm
NK-means, $k$-means++ on coreset, and $k$-means++ on the original input all
had precision greater than $0.99$ for all data sets and always terminated
within $4$ hours. The $k$-means++ results are excluded from the table. Details
of the quality and runtime are deferred to the Supplementary Material E.

|  Skin-5 |  Skin-10 |  Susy-5 |  Susy-10 |  Power-5 |  Power-10 | KddFull
---|---|---|---|---|---|---|---
NK-means | 1 | 1 | 1 | 1 | 1 | 1 | 1
0.8065 | 0.9424 | 0.8518 | 0.9774 | 0.6720 | 0.9679 | 0.6187
56 | 56 | 1136 | 1144 | 363 | 350 | 1027
$k$-means– | 0.9740 | 1.5082 | 1.2096 | 1.1414 | 1.0587 | 1.0625 | 2.0259
0.7632 | 0.9044 | 0.8151 | 0.9753 | 0.6857 | 0.9673 | 0.6436
86 | 89 | 672 | 697 | 291 | 251 | 122
$k$-means++ | 1.0641 | 1.4417 | 1.0150 | 1.0091 | 1.0815 | 1.0876 | 1.5825
coreset | 0.7653 | 0.9012 | 0.8622 | 0.9865 | 0.7247 | 0.9681 | 0.3088
| 39 | 37 | 462 | 465 | 177 | 142 | 124
$k$-means++ | 0.9525 | 1.6676 | 1.0017 | 1.0351 | 1.0278 | 1.0535 | 1.5756
original | 0.7775 | 0.8975 | 0.8478 | 0.9814 | 0.7116 | 0.9649 | 0.3259
| 34 | 43 | 6900 | 6054 | 689 | 943 | 652
Table 2: Experiment results on real data sets with $\Delta=5,10$. The top,
middle, bottom in each entry are the objective (normalized relative to NK-
means), precision, and run time (sec.), resp. Bold indicates the best in the
category.

#### Real Data Experiments

For further experiments, we used real data sets. We used the same
normalization, noise addition method and the same value of $k=10$ in all
experiments. The data sets are Skin-$\Delta$, Susy-$\Delta$, and
Power-$\Delta$. We normalized the data such that the mean and standard
deviation are $0$ and $1$ on each dimension, respectively. Then we randomly
sampled $z=0.01n$ points uniformly at random from $[-\Delta,\Delta]^{d}$ and
added them as noise. We discarded data points with missing entries.

Real Data Sets:

  1. 1.

Skin-$\Delta$ (ski, ). $n=245057$, $d=3$, $k=10$, $z=0.01n$. Only the first
$3$ features were used.

  2. 2.

Susy-$\Delta$ (sus, ). $n=5$M, $d=18$, $k=10$, $z=0.01n$.

  3. 3.

Power-$\Delta$ (pow, ). $n=2049280$, $d=7$, $k=10$, $z=0.01n$. Out of $9$
features, we dropped the first $2$, date and time, that denote when the
measurements were made.

  4. 4.

KddFull (kdd, ). $n=4898431$, $d=34$, $k=3$, $z=45747$. Each instance has $41$
features and we excluded $7$ non-numeric features. This data set has $23$
classes and $3$ classes account for $98.3\%$ of the data points. We considered
the other $45747$ data points as ground truth outliers.

Table 2 shows our experiment results for the above real data sets. Due to
their high failure rate observed in Table 1 and space constraints, we excluded
the primal-dual, local search, and conservative uniform sampling algorithms
from Table 2; all results can be found in Supplementary Material E. As before,
we executed each algorithm $3$ times. It is worth noting that NK-means is the
_only_ algorithm with the worst case guarantees shown in Table 2. This gives a
candidate explanation for the stability of our algorithm’s solution quality
across all data sets in comparison to the other algorithms considered.

The result shows that our algorithm NK-means has the best objective for all
data sets, except within $5\%$ for Skin-5. Our algorithm is always competitive
with the best precision. For KddFull where we didn’t add artificial noise, NK-
means significantly outperformed other algorithms in terms of objective. We
can see that NK-means pays extra in the run time to remove outliers, but this
preprocessing enables stability, and competitive performance.

##  6 Conclusion

This paper presents a near linear time algorithm for removing noise from data
before applying a $k$-means clustering. We show that the algorithm has
provably strong guarantees on the number of outliers discarded and
approximation ratio. Further, NK-means gives the first pseudo-approximation-
preserving reduction from $k$-means with outliers to $k$-means without
outliers. Our experiments show that the algorithm is the fastest among
algorithms with provable guarantees and is more accurate than state-of-the-art
algorithms. It is of interest to determine if the algorithm achieves better
guarantees if data has more structure such as being in low dimensional
Euclidean space or being assumed to be well-clusterable (Braverman et al.,
2011).

##  7 Acknowledgments

S. Im and M. Montazer Qaem were supported in part by NSF grants CCF-1617653
and 1844939. B. Moseley and R. Zhou were supported in part by NSF grants
CCF-1725543, 1733873, 1845146, a Google Research Award, a Bosch junior faculty
chair and an Infor faculty award.

## References

  * (1) Kdd cup 1999 data.  URL http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.
  * (2) Individual household electric power consumption data set.  URL https://archive.ics.uci.edu/ml/datasets/Individual+household+electric+power+consumption.
  * (3) Skin segmentation data set.  URL https://archive.ics.uci.edu/ml/datasets/Skin+Segmentation.
  * (4) SUSY data set.  URL https://archive.ics.uci.edu/ml/datasets/SUSY.
  * Aggarwal et al. (2009) Ankit Aggarwal, Amit Deshpande, and Ravi Kannan.  Adaptive sampling for $k$-means clustering.  In _RANDOM_ , pages 15–28, 2009.
  * Aggarwal and Reddy (2013) Charu C. Aggarwal and Chandan K. Reddy.  _Data Clustering: Algorithms and Applications_.  Chapman and Hall/CRC, 2013.
  * Arthur and Vassilvitskii (2007) David Arthur and Sergei Vassilvitskii.  $k$-means++: the advantages of careful seeding.  In _SODA_ , pages 1027–1035, 2007.
  * Arya et al. (2004) Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit.  Local search heuristics for k-median and facility location problems.  _SIAM Journal on computing_ , 33(3):544–562, 2004\.
  * Bhaskara et al. (2019) Aditya Bhaskara, Sharvaree Vadgama, and Hong Xu.  Greedy sampling for approximate clustering in the presence of outliers.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada_ , pages 11146–11155, 2019.
  * Braverman et al. (2011) Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and Brian Tagiku.  Streaming k-means on well-clusterable data.  In _Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011_ , pages 26–40, 2011.
  * Charikar and Guha (1999) Moses Charikar and Sudipto Guha.  Improved combinatorial algorithms for the facility location and k-median problems.  In _40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039)_ , pages 378–388. IEEE, 1999.
  * Charikar et al. (2001) Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan.  Algorithms for facility location problems with outliers.  In _SODA_ , pages 642–651, 2001.
  * Charikar et al. (2002) Moses Charikar, Sudipto Guha, Éva Tardos, and David B Shmoys.  A constant-factor approximation algorithm for the k-median problem.  _Journal of Computer and System Sciences_ , 65(1):129–149, 2002.
  * Chawla and Gionis (2013) Sanjay Chawla and Aristides Gionis.  $k$-means-: A unified approach to clustering and outlier detection.  In _ICDM_ , pages 189–197, 2013.
  * Chen et al. (2018) Jiecao Chen, Erfan Sadeqi Azer, and Qin Zhang.  A practical algorithm for distributed clustering and outlier detection.  In _Advances in Neural Information Processing Systems_ , pages 2248–2256, 2018.
  * Chen (2008) Ke Chen.  A constant factor approximation algorithm for $k$-median clustering with outliers.  In _SODA_ , pages 826–835, 2008.
  * Ester et al. (1996) Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu.  A density-based algorithm for discovering clusters in large spatial databases with noise.  In _AAAI_ , pages 226–231, 1996.
  * Feldman and Langberg (2011) Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In Lance Fortnow and Salil P. Vadhan, editors, _Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011_ , pages 569–578. ACM, 2011.  doi: 10.1145/1993636.1993712.  URL https://doi.org/10.1145/1993636.1993712.
  * Feldman et al. (2007) Dan Feldman, Morteza Monemizadeh, and Christian Sohler.  A ptas for k-means clustering based on weak coresets.  In _Proceedings of the twenty-third annual symposium on Computational geometry_ , pages 11–18. ACM, 2007.
  * Guha et al. (2017) Sudipto Guha, Yi Li, and Qin Zhang.  Distributed partial clustering.  In _Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures_ , pages 143–152. ACM, 2017.
  * Gupta et al. (2017) Shalmoli Gupta, Ravi Kumar, Kefu Lu, Benjamin Moseley, and Sergei Vassilvitskii.  Local search methods for k-means with outliers.  _PVLDB_ , 10(7):757–768, 2017.  doi: 10.14778/3067421.3067425.  URL http://www.vldb.org/pvldb/vol10/p757-Lu.pdf.
  * Huang et al. (2018) Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu.  Epsilon-coresets for clustering (with outliers) in doubling metrics.  In Mikkel Thorup, editor, _59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018_ , pages 814–825. IEEE Computer Society, 2018.  doi: 10.1109/FOCS.2018.00082.  URL https://doi.org/10.1109/FOCS.2018.00082.
  * Jain et al. (1999) A. K. Jain, M. N. Murty, and P. J. Flynn.  Data clustering: A review.  _ACM Computing Surveys_ , 31:264–323, 1999.
  * Kanungo et al. (2004) Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu.  A local search approximation algorithm for $k$-means clustering.  _Comput. Geom._ , 28(2-3):89–112, 2004.
  * Kogan et al. (2006) Jacob Kogan, Charles Nicholas, Marc Teboulle, et al.  _Grouping multidimensional data_.  Springer, 2006.
  * Krishnaswamy et al. (2018) Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep.  Constant approximation for k-median and k-means with outliers via iterative rounding.  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018_ , pages 646–659, 2018.  doi: 10.1145/3188745.3188882.  URL https://doi.org/10.1145/3188745.3188882.
  * Kumar et al. (2004) Amit Kumar, Yogish Sabharwal, and Sandeep Sen.  A simple linear time (1+ $\varepsilon$) -approximation algorithm for k-means clustering in any dimensions.  In _Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science_ , FOCS ’04, pages 454–462, Washington, DC, USA, 2004. IEEE Computer Society.  ISBN 0-7695-2228-9.  doi: 10.1109/FOCS.2004.7.  URL http://dx.doi.org/10.1109/FOCS.2004.7.
  * Li and Guo (2018) Shi Li and Xiangyu Guo.  Distributed $k$-clustering for data with heavy noise.  In _Advances in Neural Information Processing Systems_ , pages 7838–7846, 2018.
  * Lloyd (1982) Stuart P. Lloyd.  Least squares quantization in PCM.  _IEEE Transactions on Information Theory_ , 28(2):129–136, 1982.
  * Malkomes et al. (2015) Gustavo Malkomes, Matt Kusner, Wenlin Chen, Kilian Weinberger, and Benjamin Moseley.  Fast distributed $k$-center clustering with outliers on massive data.  In _NIPS_ , pages 1063–1071, 2015.
  * McCutchen and Khuller (2008) Richard Matthew McCutchen and Samir Khuller.  Streaming algorithms for $k$-center clustering with outliers and with anonymity.  In _APPROX_ , pages 165–178, 2008.
  * Meyerson et al. (2004) Adam Meyerson, Liadan O’callaghan, and Serge Plotkin.  A k-median algorithm with running time independent of data size.  _Machine Learning_ , 56(1-3):61–87, 2004.

## Supplementary Material for: Fast Noise Removal for $k$-Means Clustering

##  Appendix A Analysis of NK-means

The goal of this section is to prove Theorem 1. For the remainder of this
section, let $C^{*}$ denote the optimal $z$-solution and $C$ denote the output
of $\textsc{NK-means}(X,k,z,\mathcal{A})$. Again, let $Opt:=Opt(X,k,z)$.

We first show the benefits of optimal clusters having size at least $3z$.

######  Claim 1.

For each optimal center $c^{*}\in C^{*}$, let $x(c^{*})\in X$ be the closest
input point to $c^{*}$. If the cluster defined by $c^{*}\in C^{*}$ has size at
least $3z$, then $d(x(c^{*}),c^{*})\leq(\frac{Opt}{3z})^{1/2}$.

###### Proof.

Assume for contradiction that $d(x(c^{*}),c^{*})>(\frac{Opt}{3z})^{1/2}$. Thus
for each input point $x\in X$ that is assigned to center $c^{*}$ in the
optimal solution, we have $d^{2}(x,c^{*})>\frac{Opt}{3z}$. There are at least
$3z$ such points, so we can lower bound the assignment cost of these points by
$3z(\frac{Opt}{3z})=Opt$. This is a contradiction. ∎

######  Lemma 2.

If the cluster defined by $c^{*}\in C^{*}$ in the optimal solution has size at
least $3z$, then $x(c^{*})$ is heavy.

###### Proof.

Assume for contradiction that $x(c^{*})$ is light, so $\lvert
B(x(c^{*}),r)\rvert<2z$. However, at least $3z$ points are assigned to $c^{*}$
in the optimal solution, so there are at least $z+1$ such points outside of
$B(x(c^{*}),r)$.

Let $x\notin B(x(c^{*}),r)$ be such a point that is assigned to $c^{*}$ in the
optimal solution. By the triangle inequality, we have:

$d(x,x(c^{*}))\leq d(x,c^{*})+d(x(c^{*}),c^{*})$

, which implies $d(x,c^{*})\geq r-d(x(c^{*}),c^{*})\geq
2(Opt/z)^{1/2}-(1/3)^{1/2}(Opt/z)^{1/2}\geq(Opt/z)^{1/2}$.

We conclude that for at least $z+1$ points assigned to $c^{*}$ in the optimal
solution, their assignment costs are each at least $Opt/z$. This is a
contradiction. ∎

Now using this result, we can upper bound the number of outliers required by
$\textsc{NK-means}(X,k,z,\mathcal{A})$ to remain competitive with the optimal
$z$-solution (we will show that this quantity is upper bounded by the size of
$Y$ at the end of $\textsc{NK-means}(X,k,z,\mathcal{A})$.)

######  Lemma 3.

At the end of $\textsc{NK-means}(X,k,z,\mathcal{A})$, $\lvert Y\rvert\leq
3z\\#\\{\text{optimal clusters of size less than $3z$}\\}+2z$.

###### Proof.

Let $C^{*}=\\{c_{1}^{*},\dots,c_{k}^{*}\\}\subset X$.

For each $x\in X$, we will classify points into two types:

  1. 1)

$d(x,C^{*})\leq(Opt/z)^{1/2}$:

We have that $x$ satisfies $d(x,C^{*})=d(x,c^{*})\leq(Opt/z)^{1/2}$ for some
$c^{*}\in C^{*}$. If the cluster defined by $c^{*}$ has size at least $3z$,
then by Lemma 2, $x(c^{*})$ is heavy.

Further, $d(x,x(c^{*}))\leq
d(x,c^{*})+d(x(c^{*}),c^{*})\leq(Opt/z)^{1/2}+(1/3)^{1/2}(Opt/z)^{1/2}\leq
2(Opt/z)^{1/2}$, so $x(c^{*})\in B(x,r)$. Thus, we will not add $x$ to $Y$ if
its nearest optimal cluster has size at least $3z$.

  2. 2)

$d(x,C^{*})>(Opt/z)^{1/2}$:

We claim that there are at most $2z$ such $x\in X$ satisfying
$d(x,C^{*})>(Opt/z)^{1/2}$. Assume for contradiction that there are at least
$2z+1$ points $x\in X$ with $d(x,C^{*})>(Opt/z)^{1/2}$. At most $z$ of these
points can be outliers, so the optimal solution must cluster at least $z+1$ of
these points. Thus we can lower bound the assignment cost of these points to
$C^{*}$ by:

$(z+1)r^{2}=(z+1)(Opt/z)>Opt$

This is a contradiction.

We conclude that $Y$ includes no points of type 1 from clusters of size at
least $3z$, at most $3z$ points from each cluster of size less than $3z$, and
at most $2z$ points of type 2. ∎

######  Corollary 2.

If every optimal cluster has size at least $3z$, then at the end of
$\textsc{NK-means}(X,k,z,\mathcal{A})$, $\lvert Y\rvert\leq 2z$.

It remains to bound the $\lvert Y\rvert$-cost of $C$. Recall that the $\lvert
Y\rvert$-cost of $C$ is the cost of clustering $X$ with $C$ excluding the
$\lvert Y\rvert$ points of largest assignment cost.

Intuitively, we do not need to worry about the points in $X$ that are
clustered in both the $\lvert Y\rvert$-solution $C$ and the $z$-solution
$C^{*}$ – so the points in $X_{\lvert Y\rvert}(C)\cap X_{z}(C^{*})$, because
such points are paid for in both solutions.

We must take some care to bound the cost of the points in $X$ that are
clustered by the $\lvert Y\rvert$-solution $C$ but are outliers in the
$z$-solution $C^{*}$, because such points could have unbounded assignment
costs to $C^{*}$. Here we will use the following property of heavy points:

######  Lemma 4.

Let $x\in X$ be a heavy point. Then there exists some optimal center $c^{*}\in
C^{*}$ such that $d(x,c^{*})\leq 2r$.

###### Proof.

Assume for contradiction that $d(x,c^{*})>2r$ for every $c^{*}\in C^{*}$.
However, $x$ is heavy, so $\lvert B(x,r)\rvert\geq 2z$. At least $z$ points in
$B(x,r)$ must be clustered by the optimal $z$-solution $C^{*}$.

Consider any such $x^{\prime}\in B(x,r)\cap X_{z}(C^{*})$. By the triangle
inequality, we have

$2r<d(x,C^{*})\leq d(x,x^{\prime})+d(x^{\prime},C^{*})\leq
r+d(x^{\prime},C^{*})$

This implies $d(x^{\prime},C^{*})>r$. Thus we can lower bound the assignment
cost to $C^{*}$ of all points in $B(x,r)\cap X_{z}(C^{*})$ by:

$\sum\limits_{x^{\prime}\in B(x,r)\cap
X_{z}(C^{*})}d^{2}(x^{\prime},C^{*})>zr^{2}=4Opt$

This is a contradiction. ∎

Now we are ready to prove the main theorem of this section.

###### Proof of Theorem 1.

By Corolloary 2, we have $f_{2z}^{X}(C)\leq f^{X\setminus Y}(C)$.

Further, by construction, $C$ is an $\alpha$-approximate $k$-means solution on
$X\setminus Y$. Then

$f^{X\setminus Y}(C)\leq\alpha f^{X\setminus Y^{*}}\leq\alpha f^{X\setminus
Y}(C^{*}),$

so it suffices to show that $f^{X\setminus Y}(C^{*})\leq 9\cdot Opt$.

We will consider two types of points:

  1. 1)

$x\in(X\setminus Y)\cap X_{z}(C^{*})$, so points in $X\setminus Y$ that are
also clustered in the optimal $z$-solution $C^{*}$:

We have

$\displaystyle\sum\limits_{x\in(X\setminus Y)\cap X_{z}(C^{*})}d^{2}(x,C^{*})$
$\displaystyle\leq\sum\limits_{x\in
X_{z}(C^{*})}d^{2}(x,C^{*})=f_{z}^{X}(C^{*}).$

  2. 2)

$x\in(X\setminus Y)\cap(X\setminus X_{z}(C^{*}))$, so points in $X\setminus Y$
that are outliers in the optimal $z$-solution $C^{*}$:

Observe that by definition, $\lvert X\setminus X_{z}(C^{*})\rvert=z$, so there
are at most $z$ such $x$. By Lemma 2, for each such $x\in(X\setminus
Y)\cap(X\setminus X_{z}(C^{*}))$, we have $d^{2}(x,C^{*})\leq 4r^{2}$. Thus,

$\sum\limits_{x\in(X\setminus Y)\cap(X\setminus
X_{z}(C^{*}))}d^{2}(x,C^{*})\leq z(4r^{2})=8f_{z}^{X}(C^{*}).$

We conclude that $f^{X\setminus Y}(C^{*})\leq
f_{z}^{X}(C^{*})+8f_{z}^{X}(C^{*})=9f_{z}^{X}(C^{*})$, as required. ∎

##  Appendix B Analysis of Coreset Construction and Near Linear Time Algorithm

The goal of this section is to prove Theorems 4 and 5. In our proof, we will
use Theorems 2 and 3. For proofs of these theorems, see Sections C and D.

###### Proof of Theorem 4.

We consider $2$ cases: $p>1$ and $p\leq 1$.

If $p>1$, then $Y=\textsc{k-means++}(X,32(k+z))$. Because $p>1$, we have
$\max(36\log(\frac{4nk^{2}}{z}),36k\log(2k^{3}))>z\Rightarrow z=O(k\log n)$.
Then $\lvert Y\rvert=O(k+z)=O(k\log n)$, as required. Further, by Theorem 2,
$(Y,k,z)$ is a $(1,124)$-coreset for $(X,k,z)$ with constant probability.

Otherwise, if $p\leq 1$, then $Y=\textsc{k-means++}(S,32(k+2.5pz))$. Thus,
$\lvert Y\rvert=O(k+pz)=O(k\log n)$, as required. By Theorem 3, with
probability at least $1-\frac{1}{k^{2}}$, $(S,k,2.5pz)$ is an
$(16,29)$-coreset for $(X,k,z)$. For the remainder of this analysis, we assume
this condition holds. We also know that $(Y,k,2.5pz)$ is a $(1,124)$-coreset
for $(S,k,2.5pz)$ with constant probability. Assume this holds for the
remainder of the analysis.

Let $C$ be a set of $k$ centers satisfying
$f^{Y}_{2.5\kappa_{1}pz}(C)\leq\kappa_{2}Opt(Y,k,2.5pz)$. Because
$(Y,k,2.5pz)$ is an $(1,124)$-coreset for $(S,k,2.5pz)$, this implies:

$f^{S}_{2.5\kappa_{1}pz}(C)\leq 124\kappa_{2}Opt(S,k,2.5pz)$

Because $(S,k,2.5pz)$ is an $(16,29)$-coreset for $(X,k,z)$, we conclude:

$f^{X}_{16\kappa_{1}z}(C)\leq 29\cdot 124\kappa_{2}Opt(X,k,z)$

Thus $(Y,k,2.5pz)$ is an $(O(1),O(1))$-coreset for $(X,k,z)$. ∎

###### Proof of Theorem 5.

The approximation guarantees follow directly from Theorems 1 and 4.

To analyze the runtime, note that we can compute $S$ in time $O(n)$. It is
known that $\textsc{k-means++}(X,k)$ takes $O(kdn)$ time (Arthur and
Vassilvitskii, 2007; Aggarwal et al., 2009). Thus the runtime of SampleCoreset
is dominated by the runtime of k-means++ in both cases when $p>1$ and $p\leq
1$, which takes $O((k\log n)dn)$ time.

Note that $Y$ has size $O(k\log n)$ in expectation, so by Lemma 1, NK-means
can be implemented to run in time $O(k^{2}d\log^{2}n)+T(k\log n)$ on $Y$ in
expectation. ∎

##  Appendix C Proof of Theorem 2

Our proof of Theorem 2 relies on the following lemma which is implicit in
Aggarwal et al. (2009):

######  Lemma 5.

Let $Y=\textsc{k-means++}(X,32k)$. Then $f^{X}(Y)\leq 20\cdot Opt(X,k)$ with
probability at least $0.03$.

######  Corollary 3.

Let $Y=\textsc{k-means++}(X,32(k+z))$. Then $f^{X}(Y)\leq 20\cdot Opt(X,k,z)$
with probability at least $0.03$.

###### Proof.

Let $C^{*}$ be the optimal solution to the $k$-means with outliers instance
$(X,k,z)$. Note that $X\setminus X_{z}(C^{*})$ is the set of outliers in the
optimal solution, so $\lvert X\setminus X_{z}(C^{*})\rvert\leq z$.

Then we have $f^{X}_{z}(C^{*})\geq f^{X}(C^{*}\cup(X\setminus
X_{z}(C^{*}))\geq Opt(X,k+z)$. Combining this inequality with the above lemma
gives the desired result. ∎

Using the above corollary, we can prove Theorem 2 by a moving argument:

###### Proof of Theorem 2.

Let $Y=\textsc{k-means++}(X,32(k+z))$ with weights $w$ as defined in the
theorem statement. By the above corollary, we have $f^{X}(Y)\leq 20\cdot
Opt(X,k,z)$ with constant probability. We assume for the remainder of the
proof that this condition holds.

Let $C$ be any set of $k$ centers such that
$f^{Y}_{\kappa_{1}z}(C)\leq\kappa_{2}Opt(Y,k,z)$. We wish to bound
$f^{X}_{\kappa_{1}z}(C)$.

Note that by definition of $w$, $\sum\limits_{y\in Y}w(y)=n$, and each weight
is an integer. Thus for the remainder of the proof we interpret $Y$ as a
multiset such that for each $y\in Y$, there are $w(y)$ copies of $y$ in the
multiset.

It follows, we can associate each $x\in X$ with a unique $y(x)\in Y$ such that
$d^{2}(x,y(x))=d^{2}(x,Y)$ (so $y(x)$ is a unique copy of the center that $x$
is assigned to in the clustering of $X$ with centers $Y$.)

Now we partition $X_{\kappa_{1}z}(C)$ into two sets:

$X^{\prime}:=\\{x\in X\mid x\in X_{\kappa_{1}z}(C),y(x)\in
Y_{\kappa_{1}z}(C)\\}$ $X^{\prime\prime}:=\\{x\in X\mid x\in
X_{\kappa_{1}z}(C),y(x)\notin Y_{\kappa_{1}z}(C)\\}$

For each $x\in X_{\kappa_{1}z}(C)$, we want to bound its assignment cost.
There are two cases:

  1. 1)

$x\in X^{\prime}$:

We can bound $d^{2}(x,C)\leq 2d^{2}(x,y(x))+2d^{2}(y(x),C)$. Note that
$y(x)\in Y_{\kappa_{1}z}(C)$, so we can bound the assignment cost
$d^{2}(y(x),C)$.

  2. 2)

$x\in X^{\prime\prime}$:

Note that because $y(x)\notin Y_{\kappa_{1}z}(C)$, and
$X_{\kappa_{1}z}(C),Y_{\kappa_{1}z}(C)$ are the same size, we can associate
$y(x)$ with a unique element in $Y_{\kappa_{1}z}(C)$, say $y(x^{\prime})\in
Y_{\kappa_{1}z}(C)$ such that $x^{\prime}\notin X_{\kappa_{1}z}(C)$.

Note that $x^{\prime}$ is not assigned in the $\kappa_{1}z$-solution $C$, but
$x$ is assigned, so we can bound:

$d^{2}(x,C)\leq d^{2}(x^{\prime},C)\leq
2d^{2}(x^{\prime},y(x^{\prime}))+2d^{2}(y(x^{\prime}),C)$

By summing over all $x\in X_{\kappa_{1}z}(C)$ and applying the above bounds,
we have:

$\displaystyle f^{X}_{\kappa_{1}z}(C)$ $\displaystyle=\sum\limits_{x\in
X^{\prime}}d^{2}(x,C)+\sum\limits_{x\in X^{\prime\prime}}d^{2}(x,C)$
$\displaystyle\leq 2\sum\limits_{x\in
X^{\prime}}(d^{2}(x,y(x))+d^{2}(y(x),C))$
$\displaystyle\qquad+2\sum\limits_{x\in
X^{\prime\prime}}(d^{2}(x^{\prime},y(x^{\prime}))+d^{2}(y(x^{\prime}),C))$
$\displaystyle=2f^{X}(Y)+2f^{Y}_{\kappa_{1}z}(C)$ $\displaystyle\leq 2\cdot
20\cdot Opt(X,k,z)+2\kappa_{2}Opt(Y,k,z)$

An analogous argument gives that $Opt(Y,k,z)\leq 2\cdot 20\cdot
Opt(X,k,z)+2\cdot Opt(X,k,z)$.

We conclude that $f^{X}_{\kappa_{1}z}(C)\leq(40+84\kappa_{2})Opt(X,k,z)$,
where we may assume $\kappa_{2}\geq 1$. This gives the desired result. ∎

##  Appendix D Proof of Theorem 3

The proof of Theorem 3 closely follows Meyerson et al. (2004) and is given
here for completeness. Note that the key difference is that rather than
sampling elements uniformly from $X$ with replacement as in Meyerson et al.
(2004), instead we sample each element of $X$ independently with probability
$p$. In this section let $C^{*}=\\{c_{1}^{*},\dots,c_{k}^{*}\\}$ be an optimal
$z$-solution on $X$ with clusters $C_{1}^{*},\dots,C_{k}^{*}$ such that
$C_{i}^{*}$ is the set of points assigned to center $c_{i}^{*}$. Let
$n_{i}:=\lvert C_{i}^{*}\rvert$ denote the size of cluster $i$.

Further, let $S$ be a sample drawn from $X$ of size $s$ as in SampleCoreset,
and let $C$ a set of $k$ centers satisfying
$f^{S}_{2.5\kappa_{1}pz}(C)\leq\kappa_{2}Opt(S,k,2.5pz)$ for some constants
$\kappa_{1},\kappa_{2}>0$.

The goal of this section is to prove that the sample $S$ gives a good coreset
of $X$ for the $k$-means with outliers problem. We begin with some definitions
that will be useful to our analysis:

######  Definition 4 (Large/Small Clusters).

We say a cluster $C_{i}^{*}$ of the optimal solution is large if $\lvert
C_{i}^{*}\rvert\geq\frac{z}{k}$ and small otherwise.

######  Definition 5 (Covered/Uncovered Clusters).

Let $A:=S_{2.5pz}(C^{*})\cap S_{2.5\kappa_{1}pz}(C)$, so $A$ is the set of
points in $S$ that are assigned in the $2.5pz$-solution $C^{*}$ and in the
$2.5\kappa_{1}pz$-solution $C$.

We say a large cluster $C_{i}^{*}$ is covered if $\lvert C_{i}^{*}\cap
A\rvert\geq\frac{1}{2}\lvert C_{i}^{*}\cap S\rvert$ and uncovered otherwise.

Intuitively, in our analysis we want to show that most of the large clusters
are covered, because the large clusters make up the majority of the points. In
order to obtain a good summary of the whole point set, it suffices to obtain a
good summary of the large clusters.

We quantify this notion of a good summary by defining a division of $X$ into
bins with respect to the centers, $C^{*}$.

######  Definition 6 (Bin Division).

Let $b\in\mathbb{N}$. The $b$-bin division of $X$ with respect to a set of $k$
centers, $C$, is a partition $B_{1},\dots B_{b}$ of $X$ such that $B_{1}$
contains the $\frac{n}{b}$ points in $X$ with the smallest assignment costs to
$C^{*}$, $B_{2}$ contains the next $\frac{n}{b}$ cheapest points, and so on.
More formally, the partition $B_{1},\dots,B_{b}$ satisfies:

  * •

$\lvert B_{i}\rvert=\frac{n}{b}$ for all $i\in[b]$

  * •

$\max\limits_{x\in B_{i}}d^{2}(x,C)\leq\min\limits_{x\in B_{i+1}}d^{2}(x,C)$
for all $i\in[b-1]$

For the remainder of this section, let $B_{1},\dots,B_{b}$ denote the bin
division of $X$ with respect to the optimal $z$-solution $C^{*}$, where
$b=\frac{n}{z}$ (so each bin has size $z$.)

The following lemma shows that our sample size is sufficiently large to obtain
a good representation of each bin and each large cluster.

######  Lemma 6.

With probability at least $1-\frac{1}{k^{2}}$, the following both hold:

  1. 1)

For all $i\in[b]$, $\lvert S\cap B_{i}\rvert\in[0.75pz,1.25pz]$

  2. 2)

For every large cluster $C_{i}^{*}$, $\lvert S\cap C_{i}^{*}\rvert\geq
0.75pn_{i}$

###### Proof.

We will use the following standard Chernoff bounds, where
$X=\sum\limits_{i\in[n]}X_{i}$ is the sum of $n$ i.i.d. random variables
$X_{i}\sim Ber(p)$. For any $\delta\geq 0$, $Pr(\lvert X-pn\rvert\geq\delta
pn)\leq 2exp(\frac{-\delta^{2}pn}{2+\delta})$ and $Pr(X\geq(1-\delta)pn)\leq
exp(\frac{-\delta^{2}pn}{2+\delta})$.

We bound the failure probability for each bin and each large cluster. For all
$i\in[b]$, we have $Pr(\lvert\lvert S\cap B_{i}\rvert-
pz\rvert\geq\frac{1}{4}pz)\leq exp(-\frac{1}{36}pz)$. For all large clusters
$C^{*}_{i}$, we have $Pr(\lvert S\cap
C^{*}_{i}\rvert\leq(1-\frac{1}{4})pn_{i})\leq exp(-\frac{1}{36}pn_{i})\leq
exp(-\frac{1}{36}p\frac{z}{k})$.

Now by union bounding over the failure events for each bin and large cluster,
the probability that Condition 1 or 2 does not hold is upper bounded by:

$\frac{n}{z}2\cdot exp(-\frac{1}{36}pz)+k\cdot exp(-\frac{1}{36}p\frac{z}{k})$

Because $p\geq\frac{36}{z}\log(\frac{4nk^{2}}{z})$ and $p\geq
36\frac{k}{z}\log(2k^{3})$, the first and second terms are both upper bounded
by $\frac{1}{2k^{2}}$, respectively. ∎

For the remainder of this section, we assume that both Conditions 1 and 2
hold. Now we will formalize the idea that it suffices to get a good
representation of the large clusters, because we can simply throw away the
remaining points as outliers by increasing the number of outliers by a
constant factor.

######  Lemma 7.

Let $X^{\prime}=X_{covered}$, where $X_{covered}$ is the union of all covered
large clusters (so $X^{\prime}$ excludes all small clusters, all uncovered
clusters, and all outliers in the optimal $z$-solution on $X$.)

Then $f^{X}_{(9+7\kappa_{1})z}(C)\leq f^{X^{\prime}}(C)$.

###### Proof.

It suffices to show that $\lvert X_{small}\cup(X\setminus X_{z}(C^{*}))\cup
X_{uncovered}\rvert\leq(9+7\kappa_{1})z$.

By definition $\lvert X_{small}\rvert\leq z$ (because each small cluster has
at most $\frac{z}{k}$ points and there are at most $k$ small clusters), and
$\lvert X\setminus X_{z}(C^{*})\rvert\leq z$, so it remains to bound the size
of $X_{uncovered}$.

Recall that $A=S_{2.5pz}(C^{*})\cap S_{2.5\kappa_{1}pz}(C)$, so $\lvert
A\rvert\geq s-2.5pz-2.5\kappa_{1}pz$. This implies $\lvert S\setminus
A\rvert\leq 2.5pz(1+\kappa_{1})$.

By definition, a cluster $C_{i}^{*}$ is uncovered if $\lvert C_{i}^{*}\cap
A\rvert<\frac{1}{2}\lvert C_{i}^{*}\cap S\rvert$. This implies $\lvert
C_{i}^{*}\cap S\rvert\leq 2\lvert C_{i}^{*}\cap(S\setminus A)\rvert$

By summing over all uncovered clusters, we have:

$\displaystyle\lvert X_{uncovered}\cap S\rvert$ $\displaystyle\leq 2\lvert
X_{uncovered}\cap(S\setminus A)\rvert\leq 2\lvert S\setminus A\rvert\leq
5pz(1+\kappa_{1})$

Further, by Condition 2, for every large cluster $C_{i}^{*}$, we have $\lvert
S\cap C_{i}^{*}\rvert\geq 0.75pn_{i}$, which gives
$n_{i}\leq\frac{4}{3}\frac{1}{p}\lvert S\cap C_{i}^{*}\rvert$. This holds for
every uncovered cluster, so we can upper bound:

$\lvert X_{uncovered}\rvert\leq\frac{4}{3}\frac{1}{p}\lvert X_{uncovered}\cap
S\rvert\leq\frac{20}{3}z(1+\kappa_{1})$

Combining these bounds gives:

$\displaystyle\lvert X_{small}\cup X_{uncovered}\cup(X\setminus
X_{z}(C^{*}))\rvert$ $\displaystyle\leq$ $\displaystyle
z+z+\frac{20}{3}z(1+\kappa_{1})$ $\displaystyle=$
$\displaystyle(2+\frac{20}{3}(1+\kappa_{1}))z\leq(9+7\kappa_{1})z$

∎

Now it suffices to bound the cost of clustering all the covered clusters,
which we do so with a standard moving argument:

######  Lemma 8.

$f^{X^{\prime}}(C)\leq
2f^{X}_{z}(C^{*})+\frac{32}{3}\frac{1}{p}(f^{S}_{2.5pz}(C^{*})+f^{S}_{2.5\kappa_{1}pz}(C))$

###### Proof.

By the approximate triangle inequality:

$f^{X^{\prime}}(C)\leq
2f^{X^{\prime}}(C^{*})+2\sum\limits_{i\in[k]}n_{i}d^{2}(c_{i}^{*},C),$

where the first term accounts for moving each point in $X^{\prime}$ to its
closest center in $C^{*}$, and the second term accounts for moving each point
from its respective center in $C^{*}$ to the nearest center in $C$.

Note that $X^{\prime}\subset X_{z}(C^{*})$, so $f^{X^{\prime}}(C^{*})\leq
f^{X_{z}(C^{*})}(C^{*})=f^{X}_{z}(C^{*})$.

It remains to bound $2\sum\limits_{i\in[k]}n_{i}d^{2}(c_{i}^{*},C)$. By a
standard averaging argument, for any covered cluster $C_{i}^{*}$:

$d^{2}(c_{i}^{*},C)\leq\frac{1}{\lvert C_{i}^{*}\cap A\rvert}\sum\limits_{x\in
C_{i}^{*}\cap A}(2d^{2}(x,c_{i}^{*})+2d^{2}(x,C))$

Because $C_{i}^{*}$ is covered, $\frac{1}{\lvert C_{i}^{*}\cap
A\rvert}\leq\frac{2}{\lvert C_{i}^{*}\cap S\rvert}$. Further, by Condition 2,
we have $\lvert C_{i}^{*}\cap S\rvert\geq 0.75pn_{i}$.

Using these results, we can bound
$2\sum\limits_{i\in[k]}n_{i}d^{2}(c_{i}^{*},C)\leq\frac{32}{3}\frac{1}{p}\sum\limits_{i\in[k]}(Q_{i}+R_{i})$,
where we define $Q_{i}:=\sum\limits_{x\in C_{i}^{*}\cap A}d^{2}(x,c_{i}^{*})$
and $R_{i}:=\sum\limits_{x\in C_{i}^{*}\cap A}d^{2}(x,C)$.

Recall that $A=S_{2.5pz}(C^{*})\cap S_{2.5\kappa_{1}pz}(C)$, so:

$\displaystyle\sum\limits_{i\in[k]}Q_{i}=\sum\limits_{x\in X^{\prime}\cap
A}d^{2}(x,C^{*})\leq\sum\limits_{x\in A}d^{2}(x,C^{*})$ $\displaystyle\leq
f^{S}_{2.5pz}(C^{*})$

Analogously we can show $\sum\limits_{i\in[k]}R_{i}\leq
f^{S}_{2.5\kappa_{1}pz}(C)$. Combining these bounds gives the desired result.
∎

Note that by definition of $C$, we have
$f^{S}_{2.5\kappa_{1}pz}(C)\leq\kappa_{2}Opt(S,k,2.5pz)\leq\kappa_{2}f^{S}_{2.5pz}(C^{*})$.

We require one more lemma to prove Theorem 3, because we must relate the
$2.5pz$-cost of clustering $S$ with $C^{*}$ to the $z$-cost of clustering $X$
with $C^{*}$. To do this we use the fact that the bins are approximately
equally-represented:

######  Lemma 9.

$f^{S}_{2.5pz}(C^{*})\leq 1.25pf^{X}_{z}(C^{*})$

###### Proof.

By Condition 1, no bin contributes more than $1.25pz$ elements to $S$, so
$S_{2.5pz}(C^{*})$ excludes all of $S\cap B_{b-1}$, $S\cap B_{b}$.

Thus $S_{2.5pz}(C^{*})\subset\bigcup_{i\in[b-2]}S\cap B_{i}$, so we have
$f^{S}_{2.5pz}(C^{*})\leq\sum\limits_{i\in[b-2]}f^{S\cap B_{i}}(C^{*})$.

Further, by definition of the bin division $B_{1},\dots,B_{b}$, we have
$f^{X}_{z}(C^{*})=\sum\limits_{i\in[b-1]}f^{B_{i}}(C^{*})$, and for any
$i\in[b-2]$:

$\max\limits_{x\in S\cap B_{i}}d^{2}(x,C^{*})\leq\min\limits_{x\in
B_{i+1}}d^{2}(x,C^{*})$

Our strategy will be to charge each point in $S\cap B_{i}$ to a point in
$B_{i+1}$. Observe $\lvert B_{i}\rvert=z$ for all $i$ and by Condition 1,
$\lvert S\cap B_{i}\rvert\leq 1.25pz$. This implies $f^{S\cap
B_{i}}(C^{*})\leq 1.25pf^{B_{i+1}}(C^{*})$ for all $i\in[b-2]$.

We conclude:

$\displaystyle f^{S}_{2.5pz}(C^{*})\leq\sum\limits_{i\in[b-2]}f^{S\cap
B_{i}}(C^{*})$ $\displaystyle\leq$ $\displaystyle
1.25p\sum\limits_{i\in[b-2]}f^{B_{i+1}}(C^{*})\leq 1.25pf^{X}_{z}(C^{*})$

∎

Now we are ready to put these lemmas together to prove Theorem 3:

###### Proof of Theorem 3.

By Lemma 6, with probability at least $1-\frac{1}{k^{2}}$, both Conditions 1
and 2 hold. For the remainder of the proof, suppose both conditions hold.

Now by chaining Lemmas 7 and 8, we have:

$\displaystyle f^{X}_{(9+7\kappa_{1})z}(C)\leq f^{X^{\prime}}(C)\leq
2f^{X}_{z}(C^{*})$
$\displaystyle+\frac{32}{3}\frac{1}{p}(f^{S}_{2.5pz}(C^{*})+f^{S}_{2.5\kappa_{1}pz}(C))$

Applying the definition of $S$,
$f^{S}_{2.5\kappa_{1}pz}(C)\leq\kappa_{2}f^{S}_{2.5pz}(C^{*})$:

$\displaystyle f^{X}_{(9+7\kappa_{1})z}(C)\leq f^{X^{\prime}}(C)\leq
2f^{X}_{z}(C^{*})$
$\displaystyle+\frac{32}{3}\frac{1}{p}(1+\kappa_{2})f^{S}_{2.5pz}(C^{*})$

Finally, we apply Lemma 9 to obtain:

$\displaystyle f^{X}_{(9+7\kappa_{1})z}(C)$ $\displaystyle\leq
2f^{X}_{z}(C^{*})+\frac{32}{3}\frac{1}{p}(1+\kappa_{2})(1.25pf^{X}_{z}(C^{*}))$
$\displaystyle=(\frac{46}{3}+\frac{40}{3}\kappa_{2})Opt(X,k,z)$

We may assume $\kappa_{1},\kappa_{2}\geq 1$, which completes the proof. ∎

##  Appendix E Other Experiment Results

###  E.1 Algorithms Implemented

We discuss each algorithm’s implementation in more detail. When we ran
$k$-means++, Lloyd’s, $k$-means–, we terminated the execution when the
objective improves less than a 1.00001 factor.

  1. 1.

NK-means (plus $k$-means++ on coreset). We added NK-means to $k$-means++ as a
preprocessing step. See Algorithm 1 for its pseudo-code. Since we had to guess
the value of $Opt$, we considered all possible values that are power of 2 in
the range of $[n\min_{u,v\in X}d^{2}(u,v),n\max_{u,v\in X}d^{2}(u,v)]$.
Occasionally, when $z$ was almost as big as $n/k$, NK-means discarded almost
all points – such cases were considered as failure. However, if the guessed
value of $Opt$ is sufficiently large, NK-means discards no points. Therefore,
essentially this algorithm should be as good as running $k$-means++ on the
coreset directly.

  2. 2.

$k$-means++ (on the original input). The coreset is not used in this
algorithm. So, we run $k$-means++ on the original input.

  3. 3.

$k$-means++ (on coreset). This algorithm runs $k$-means++ on the coreset.

  4. 4.

Primal-dual of Charikar et al. (2001) (on coreset). The primal-dual algorithm
Charikar et al. (2001) is executed on the coreset. This algorithm is quite
involved, and therefore, we only provide the parameters we chose to run the
algorithm. For the whole algorithm description, see Charikar et al. (2001).
The algorithm requires us to guess the value of $Opt$. As in the
implementation of NK-means, we considered all possible values that are power
of 2 in the range of $[n\min_{u,v\in X}d^{2}(u,v),n\max_{u,v\in
X}d^{2}(u,v)]$. This algorithm is based on a reduction to the facility
location problem where one is allowed to choose as many centers as needed, but
has to pay a (uniform) cost for using each center. Thus, another binary search
is needed on the facility (center) opening cost. Each outlier cost is set to
$Opt/(2z)$.

  5. 5.

Uniform Sample (conservative uniform sampling plus $k$-means++): $k$-means++
was executed on a uniform sample consisting of points sampled with probability
$1/(2z)$.

  6. 6.

$k$-means– Chawla and Gionis (2013) on coreset. This algorithm is a variant of
the Lloyd’s algorithm that executes each iteration of Lloyd’s excluding the
farthest $z$ points. That is, the algorithm repeats the following: it bring
back all input points, excludes the farthest $z$ points from the current
centers, reassigns each remaining point to the closest center, and then
recomputes the center of each cluster.

  7. 7.

Local search of Gupta et al. (2017) (on coreset). In principle, this algorithm
may end up with discarding $\Omega(zk\log n)$ points. However, it was observed
that it never discarded more than $2z$ points in experimentation. We adopt the
practical implementation of the algorithm described in Gupta et al. (2017).
When the algorithm converges we enforce the farthest $z$ points to be the
outliers.

###  E.2 Experiment Results

In this section we present all experiment results.

($d,k,z$) | NK-means | Primal | coreset $k$- | original | Local |  $k$- | Uniform
---|---|---|---|---|---|---|---
| Dual | means++ |  $k$-means++ | Search | means– | Sample
(10,10,10K) | 333 |  $>$ 4hrs | 223 | 110 | 347 | 357 | 14
(10,10, 50K) | 89 | 5400 | 33 | 126 | 143 |  $>$ 4hrs | 14
(10, 20, 10K) | 864 |  $>$ 4hrs | 667 | 249 | 3712 |  $>$ 4hrs | 20
(10, 20, 50K) | 214 |  $>$ 4hrs | 102 | 718 | 3355 |  $>$ 4hrs | 20
(20, 10, 10K) | 6576 | 5759 | 306 | 141 | 500 | 519 | 24
(20, 10, 50K) | 145 | 5855 | 58 | 180 | 269 |  $>$ 4hrs | 24
(20, 20, 10K) | 1590 |  $>$ 4hrs | 1232 | 270 | 6698 | 7787 | 36
(20, 20, 50K) | 361 |  $>$ 4hrs | 203 | 1173 | 5278 |  $>$ 4hrs | 36
Table 3: The running time (sec.) for synthetic data sets with noise sampled from $[-1/2,1/2]^{d}$. ($d,k,z$) | NK-means | Primal | coreset $k$- | original | Local |  $k$- | Uniform
---|---|---|---|---|---|---|---
| Dual | means++ |  $k$-means++ | Search | means– | Sample
(10,10,10K) | 285 | 11271 | 129 | 406 | 247 | 4039 | 13
(10,10, 50K) | 126 | 7638 | 35 | 772 | 154 | 154 | 14
(10, 20, 10K) | 860 |  $>$ 4hrs | 585 | 900 | 3966 | 3970 | 20
(10, 20, 50K) | 280 |  $>$ 4hrs | 103 | 1742 |  $>$ 4hrs |  $>$ 4hrs | 20
(20, 10, 10K) | 415 | 13973 | 153 | 557 | 328 | 5658 | 25
(20, 10, 50K) | 220 | 11356 | 60 | 1032 | 269 |  $>$ 4hrs | 25
(20, 20, 10K) | 1235 |  $>$ 4hrs | 742 | 1050 | 6278 | 6629 | 36
(20, 20, 50K) | 474 |  $>$ 4hrs | 184 | 2079 | 4967 |  $>$ 4hrs | 36
Table 4: The running time (sec.) for synthetic data sets with noise sampled from $[-5/2,5/2]^{d}$. ($d,k,z$) | NK-means | Primal | coreset $k$- | original | Local |  $k$- | Uniform
---|---|---|---|---|---|---|---
| Dual | means++ |  $k$-means++ | Search | means– | Sample
(10,10,10K) | 1.0002 | - | 12.6865 | 1.0318 | 1.2852 | 1.2852 | 1.1501
(10,10, 50K) | 1.7474 | 61.2273 | 1.7475 | 1.8293 | 1.2351 | - | 144.8253
(10, 20, 10K) | 1.0002 | - | 8.3791 | 1.0141 | 1.2949 | - | 1.4066
(10, 20, 50K) | 6.9265 | - | 33.7886 | 29.9914 | 1.2444 | - | 352.9934
(20, 10, 10K) | 1.0002 | 94.9299 | 48.5067 | 1.0392 | 1.1547 | 1.1547 | 1.1499
(20, 10, 50K) | 2.4857 | 1.1048 | 2.4857 | 2.6371 | 1.1293 | - | 76.9656
(20, 20, 10K) | 1.0002 | - | 1.0422 | 1.0369 | 1.1532 | 1.1532 | 1.3261
(20, 20, 50K) | 1.8725 | - | 1.8768 | 42.7528 | 1.1166 | - | 491.5800
Table 5: The objective value for synthetic data sets with noise sampled from $[-1/2,1/2]^{d}$. ($d,k,z$) | NK-means | Primal | coreset $k$- | original | Local |  $k$- | Uniform
---|---|---|---|---|---|---|---
| Dual | means++ |  $k$-means++ | Search | means– | Sample
(10,10,10K) | 1.0002 | 1.1138 | 67.8622 | 62.6428 | 1.1152 | 1.1152 | 1.1363
(10,10, 50K) | 1.0017 | 82.2102 | 168.1054 | 101.0163 | 1.1678 | 1.1678 | 107.6996
(10, 20, 10K) | 1.0002 | - | 58.4918 | 74.9860 | 1.1264 | 1.1264 | 1.3842
(10, 20, 50K) | 1.0018 | - | 172.8086 | 188.8177 | - | - | 348.5592
(20, 10, 10K) | 1.0002 | 1.0410 | 128.6235 | 45.5434 | 1.0432 | 1.0432 | 1.1440
(20, 10, 50K) | 1.0013 | 1.0932 | 159.8269 | 151.0288 | 1.0907 | - | 217.1559
(20, 20, 10K) | 1.0002 | - | 119.9495 | 98.5209 | 1.0404 | 1.0404 | 1.3629
(20, 20, 50K) | 1.0016 | - | 200.1431 | 242.0977 | 1.0535 | - | 454.5076
Table 6: The objective value for synthetic data sets with noise sampled from $[-5/2,5/2]^{d}$. ($d,k,z$) | NK-means | Primal | coreset $k$- | original | Local |  $k$- | Uniform
---|---|---|---|---|---|---|---
| Dual | means++ |  $k$-means++ | Search | means– | Sample
(10,10,10K) | 1 | - | 0.9999 | 1 | 1 | 1 | 1
(10,10, 50K) | 1 | 0.7586 | 1 | 1 | 1 | - | 0.5983
(10, 20, 10K) | 1 | - | 0.9999 | 1 | 1 | - | 1
(10, 20, 50K) | 0.9998 | - | 0.9956 | 0.9980 | 1 | - | 0.0768
(20, 10, 10K) | 1 | 0.7070 | 1 | 1 | 1 | 1 | 1
(20, 10, 50K) | 1 | 1 | 1 | 1 | 1 | - | 0.8830
(20, 20, 10K) | 1 | - | 1 | 1 | 1 | 1 | 1
(20, 20, 50K) | 1 | - | 1 | 0.9999 | 1 | - | 0.2312
Table 7:  The precision/recall value for synthetic data sets with noise sampled from $[-1/2,1/2]^{d}$.  ($d,k,z$) | NK-means | Primal | coreset $k$- | original | Local |  $k$- | Uniform
---|---|---|---|---|---|---|---
| Dual | means++ |  $k$-means++ | Search | means– | Sample
(10,10,10K) | 1 | 1 | 1 | 1 | 1 | 1 | 1
(10,10, 50K) | 1 | 1 | 1 | 1 | 1 | 1 | 1
(10, 20, 10K) | 1 | - | 1 | 1 | 1 | 1 | 1
(10, 20, 50K) | 1 | - | 1 | 1 | - | - | 0.9999
(20, 10, 10K) | 1 | 1 | 1 | 1 | 1 | 1 | 1
(20, 10, 50K) | 1 | 1 | 1 | 1 | 1 | - | 1
(20, 20, 10K) | 1 | - | 1 | 1 | 1 | 1 | 1
(20, 20, 50K) | 1 | - | 0.9999 | 1 | 1 | - | 1
Table 8: The precision/recall value for synthetic data sets with noise sampled from $[-5/2,5/2]^{d}$. | NK-means |  $k$- | coreset $k$- | original | Uniform | Primal | Local
---|---|---|---|---|---|---|---
| means– | means++ |  $k$-means++ | Sample | Dual | Search
Skin-5 | 1 | 0.9740 | 1.0641 | 0.9525 | 1.1273 | 1.1934 | 0.9746
0.8065 | 0.7632 | 0.7653 | 0.7775 | 0.7575 | 0.7636 | 0.7632
56 | 86 | 39 | 34 | 1 | 1274 | 86
Skin-10 | 1 | 1.5082 | 1.4417 | 1.6676 | 1.4108 | 1.1197 | 1.5082
0.9424 | 0.9044 | 0.9012 | 0.8975 | 0.9346 | 0.9473 | 0.9044
56 | 89 | 37 | 43 | 1 | 1931 | 89
Susy-5 | 1 | 1.2096 | 1.0150 | 1.0017 | 1.1816 | 1.2093 | 1.1337
0.8518 | 0.8151 | 0.8622 | 0.8478 | 0.7622 | 0.8558 | 0.8151
1136 | 672 | 462 | 6900 | 97 | 4261 | 672
Susy-10 | 1 | 1.1414 | 1.0091 | 1.0351 | 1.1611 | 1.2474 | 1.1414
0.9774 | 0.9753 | 0.9865 | 0.9814 | 0.9816 | 0.9808 | 0.9753
1144 | 697 | 465 | 6054 | 98 | 5075 | 697
Power-5 | 1 | 1.0587 | 1.0815 | 1.0278 | 1.2814 | 1.2655 | 1.0587
0.6720 | 0.6857 | 0.7247 | 0.7116 | 0.7943 | 0.6481 | 0.6857
363 | 291 | 177 | 689 | 19 | 2494 | 291
Power-10 | 1 | 1.0625 | 1.0876 | 1.0535 | 1.2408 | 1.2299 | 1.0625
0.9679 | 0.9673 | 0.9681 | 0.9649 | 0.9821 | 0.9634 | 0.9673
350 | 251 | 142 | 943 | 19 | 3097 | 251
KddFull | 1 | 2.0259 | 1.5825 | 1.5756 | 1.1527 | 2.6394 | 2.0259
0.6187 | 0.6436 | 0.3088 | 0.3259 | 0.5855 | 0.5947 | 0.6436
1027 | 122 | 124 | 652 | 104 | 844 | 122
Table 9: Experiment results on real-world data sets with $\Delta=5,10$. The
top, middle, bottom in each entry are the objective (normalized relative to
NK-means), precision, and run time (sec.), resp.