# Improved Outlier Robust Seeding for $k$-means

Amit Deshpande<EMAIL_ADDRESS>
Microsoft Research  India  Rameshwar Pratap<EMAIL_ADDRESS>
IIT Hyderabad  India

###### Abstract

The $k$-means is a popular clustering objective, although it is inherently
non-robust and sensitive to outliers. Its popular seeding or initialization
called $k$-means++ uses $D^{2}$ sampling and comes with a provable $O(\log k)$
approximation guarantee [2]. However, in the presence of adversarial noise or
outliers, $D^{2}$ sampling is more likely to pick centers from distant
outliers instead of inlier clusters, and therefore its approximation
guarantees w.r.t. $k$-means solution on inliers, does not hold.

Assuming that the outliers constitute a constant fraction of the given data,
we propose a simple variant in the $D^{2}$ sampling distribution, which makes
it robust to the outliers. Our algorithm runs in $O(ndk)$ time, outputs $O(k)$
clusters, discards marginally more points than the optimal number of outliers,
and comes with a provable $O(1)$ approximation guarantee.

Our algorithm can also be modified to output exactly $k$ clusters instead of
$O(k)$ clusters, while keeping its running time linear in $n$ and $d$. This is
an improvement over previous results for robust $k$-means based on LP
relaxation and rounding [7], [14] and robust $k$-means++ [10]. Our empirical
results show the advantage of our algorithm over $k$-means++ [2], uniform
random seeding, greedy sampling for $k$-means [5], and robust $k$-means++
[10], on standard real-world and synthetic data sets used in previous work.
Our proposal is easily amenable to scalable, faster, parallel implementations
of $k$-means++ [4, 3] and is of independent interest for coreset constructions
in the presence of outliers [12, 16, 11].

##  1 Introduction

The $k$-means clustering is a popular tool in data analysis and an important
objective in statistics, data mining, unsupervised learning, and computational
geometry. The objective of the $k$-means clustering is to find $k$ centers
that minimize the sum of squared distances of all the points to their nearest
centers, respectively. Given a set $X\subseteq{\mathbb{R}}^{d}$ of $n$ data
points and an integer $k>0$, the $k$-means objective is to find a set
$C\subseteq{\mathbb{R}}^{d}$ of $k$ centers that minimizes

$\displaystyle\phi_{X}(C)=\sum_{x\in X}\min_{c\in C}\left\|x-c\right\|^{2}.$
(1)

Finding optimal solution of the $k$-means objective stated in Equation 1 in
NP-Hard [1]. This problem is NP-Hard even for a restricted instance when all
points are in the plane [19]. However, several efficient approximation
algorithms and heuristics have been developed to address this. The most
popular algorithm for the $k$-means remains Lloyd’s $k$-means method [18],
which is a simple, fast heuristic that starts with any given initial solution
and iteratively converges to a locally optimal solution.

Although the $k$-means problem is well-studied, the algorithms developed for
the problem can perform poorly on real-world data. The reason is that the
real-world datasets contain outliers, and $k$-means objective functions and
algorithms are extremely sensitive to outliers. Outliers can drastically
change the quality of the clustering solution, and therefore, it is important
to consider them while designing algorithms for the $k$-means objective. We
state the objective function of _$k$ -means with outliers_ as follows: given a
set $X\subseteq\mathbb{R}^{d}$ of $n$ points, an integer $k>0$, and the number
of outliers $z$, the objective of the _ $k$-means with outliers_ is to find a
set $C\subseteq\mathbb{R}^{d}$ of $k$ centers that minimizes

$\displaystyle\rho_{X}(C)$ $\displaystyle=\min_{\begin{subarray}{c}Y\subseteq
X\\\ \left|Y\right|=n-z\end{subarray}}\leavevmode\nobreak\ \sum_{x\in
Y}\min_{c\in C}\left\|x-c\right\|^{2}.$ (2)

Problem statement: In this work, we aim to design efficient and practical
approximation algorithms for $k$-means clustering with outliers problem, which
solves the optimization problem stated in Equation 2.

#####  $D^{2}$-sampling for $k$-means:

The $k$-means++ or $D^{2}$-sampling [2] suggests an adaptive sampling
algorithm for $k$-means problem (stated in Equation (1)). In this sampling
approach, the first point is sampled uniformly at random from the given
points, and the sampled point is designated as a cluster center. Then the
second point is sampled with probability proportional to its squared distance
from the first center, and designated as the second cluster center. In
general, in each step, a new point is sampled with probability proportional to
its square distance to the nearest cluster center sampled so far. If we sample
$k$ cluster centers following this distribution, the clustering obtained is
$O(\log k)$-approximation to the global optimum, in expectation. However, a
limitation of $D^{2}$ sampling distribution is that it is extremely sensitive
to outliers. Consider a scenario where $99\%$ of points are well clustered and
the remaining $1\%$ of points are very far away from these clusters. The
$D^{2}$ sampling on this dataset is likely to pick outliers as cluster
centers, and the final clustering results obtained is likely to be very far
away from the optimal clustering. In this work we propose a simple tweak to
$D^{2}$-sampling, making it robust to outliers.

##  2 Our results

We propose a simple initialization for _$k$ -means with outlier_ objective
(stated in Equation 2) using a simple modification of $D^{2}$ sampling. Our
algorithm runs in $O(ndk)$ time and gives $O(\log k)$ approximation guarantee
using $k$ clusters and $O(1)$ bi-criteria approximation guarantee using $O(k)$
clusters. Both these algorithms can be made to output exactly the same number
of outliers as the optimal solution, unlike previous algorithms that need to
discard extra points than the optimal number of outliers. The pseudocode of
our algorithm is presented in Algorithm 1, and the precise statement of our
approximation guarantee appears in Theorems 1, 3. In addition, Table 1 shows a
detailed comparison of our results with previous work.

We perform extensive experiments to compare our proposal with several
baselines and summarise it in Section 5. We use synthetic and real-world
datasets for our experimentation. In synthetic datasets, we synthetically
generated inlier clusters and outliers. In real-world datasets, we consider
two scenarios: a) where we consider small clusters as outliers and b) where we
randomly sample a small fraction of points, and add large Gaussian noise to
their features and consider them as outliers. We used the following four
baselines for empirical comparison – random seeding, $k$-means++ [2], [10],
and [5]. Random seeding and $k$-means++ [2] do not solve $k$-means with
outlier problems. We use them as heuristics, where $k$ points are sampled
using their respective sampling distribution, the farthest few points are
marked as outliers, and the remaining points as inliers on which we compute
our evaluation metrics (precision/recall/clustering cost). Our empirical
findings are as follows: We outperformed on most instances in both the
evaluation metric – precision/recall, and the clustering cost (Equation (2)).
Note that random and $k$-means++ [2] are among the fastest. However, their
performance on precision/recall and clustering cost metrics are significantly
worse on almost all the datasets. The running time of our proposal is observed
to be faster than [10], whereas it remains comparable w.r.t. [5]. To
summarise, our proposal gives both a) theoretical guarantee on the clustering
cost w.r.t. the optimal solution, and b) strong empirical performance by
suggesting a faster and more accurate algorithm for $k$-means with outliers
problem.

##  3 Related work

Outlier detection is a well-studied problem in data mining and statistics [6].
Intuitively, outliers are data points far from their nearest neighbours. One
classical approach to detecting outliers is via the $k$-Nearest Neighbour
algorithm. In statistics, Mahalanobis Distance and Minimum Covariance
Determinant (MCD) [20] are a couple of notable approaches for outliers
detection. Our problem statement is completely different from the one
mentioned here. These methods focus on detecting outliers related to a
distribution/density function, whereas we aim to produce clustering that is
near-optimal in terms of an objective that is defined solely on inliers
(stated in Equation (2)). Another practical heuristic is to first identify and
discard outliers by running these outliers detection algorithms and then run
$k$-means clustering on the remaining points. However, this heuristic doesn’t
provide any theoretical guarantee on its clustering cost w.r.t optimal
clustering over inliers. In what follows, we state some notable results for
$k$-means with outliers problem, and we attempt to compare and contrast our
results with them as follows.

###  3.1 Impractical algorithms with theoretical guarantee

Charikar et. al. [7] suggests a clever modification of $D^{2}$-sampling [2]
and gives a $3$-approximation for the robust $k$-center problem with outliers.
For $k$-median with outliers, they give a $4(1+1/\epsilon)$-approximation in
polynomial time that discards at most $(1+\epsilon)$ times more outliers than
the optimal solution. Their approximation depends on the number of extra
points deleted as outliers, whereas the approximation of our approach is
independent of that. Chen [9] suggest a polynomial time constant factor
approximation to $k$-means and $k$-median with outliers that do not discard
extra outliers. However, the algorithms are not designed to be practical.

[14] give (roughly) $53$-approximation algorithm for $k$-means with $z$
outliers, and output exactly $k$ centers and doesn’t discard any extra
outliers. They use LP relaxation and an iterative rounding approach. [13] give
$(1+\epsilon)$-approximation to $k$-means with $z$ outliers in a fixed
dimensional euclidean space. They use local search and output $(1+\epsilon)k$
centers and discard exactly $z$ outliers. However, both of these algorithms
are not designed to be practical. There are few sampling-based robust coreset
construction techniques [12, 11] which construct small-size coresets and give
$(1+\epsilon)$-approximation to various robust versions of clustering
problems. These algorithms can be considered extensions of sampling-based
techniques focusing on getting close to optimal solutions in polynomial time.

Chen [9] gives an efficient constant factor approximation to $k$-means and
$k$-median with outliers, and their result doesn’t discard any extra outliers.
However, their algorithm is not designed to be practical compared to
$k$-means++ and its variants. The algorithm of Kumar et al. [15] suggest
$(1+\epsilon)$-approximation algorithm for $k$-means with outliers for the
datasets when clusters are balanced and their algorithm discards a slightly
larger fraction of the outliers than the optimal solution. However, their
algorithm is impractical and has an exponential running time in $k$.

###  3.2 Practical heuristic without theoretical guarantee

Scalable $k$-means++ [4] has empirically observed that their sampling
distribution is robust to outliers. [8] suggests a simple modification of
Lloyd’s $k$-means method to make it robust to outliers. However, these methods
do not provide any theoretical justification for their clustering quality.

Result |  Approximation | No. of clusters | No. of outliers |  Practical |  Running time
---|---|---|---|---|---
|  guarantee | in the output | discarded |  algorithm |
This |  $64+\epsilon$ | $(1+c)k$ | $z$ |  Yes |  $O(ndk)$
paper |  $O(\log k)$ | $k$ | $z$ |  Yes |  $O(ndk)$
[5] |  $(64+\epsilon)$ | $(1+c)k$ | $\frac{(1+c)(1+\epsilon)z}{c(1-\mu)}$ |  Yes |  $\tilde{O}(ndk)$
[5] |  $O(\log k)$ | $k$ | $O(z\log k)$ |  Yes |  $\tilde{O}(ndk)$
[10] |  $5$ | $kn/z$ | $O(z)$ |  Yes |  ${O}(ndk)$
[14] |  $(53.002+\epsilon)$ | $k$ | $z$ |  No |  $n^{O({1}/{\epsilon^{3}})}$
[13] |  $(1+\epsilon)$ | $k(1+\epsilon)$ | $z$ |  No |  $kn^{d^{O(d)}}$
[9] |  $O(1)$ | $k$ | $z$ |  No |  $\mathrm{poly}(n,k)$
[7] |  $4(1+1/\epsilon)$ | $k$ | $(1+\epsilon)z$ |  No |  $n^{O(1)}$

Table 1: Comparison with related work on $k$-means clustering with outliers,
where $n$ is the no. of data points, $d$ is the dimension, $k$ is the given
no. of clusters, and $z$ is the given no. of outliers. In [5], $c$ is a given
parameter, and $\mu>0$ is an arbitrary constant. Their algorithm crucially
requires an initial guess of the optimal clustering cost. [7, 9] are about a
closely related problem called $k$-median clustering with outliers.

###  3.3 Practical algorithms with theoretical guarantee

Deshpande et. al. [10] suggest a bi-criteria $O(1)$-approximation algorithm
for $k$-means with $z$ outliers problem. They propose a sampling distribution
consisting of a uniform and $D^{2}$ sampling mixture. They show that if
$O(kn/z)$ points are picked using this distribution, the sampled points
contain a set of $k$ points that gives $O(1)$-factor approximation while
discarding slightly more points than the optimal number of outliers. The
advantage of our proposal over [10] is that we do not discard any extra points
as outliers.

Bhaskara et. al. [5] suggest a bi-criteria approximation algorithm for the
problem. They show that thresholding on the $D^{2}$ sampling distribution
makes it robust to outliers. However, their algorithms crucially require an
initial guess of the optimal clustering cost over the inlier – the very
quantity we want to estimate. With this assumption, they showed the following
two results. In the first, their algorithm output $(1+c)k$ centers and obtain
$(64+\epsilon)$ approximations by discarding ${(1+c)(1+\epsilon)z}/{c(1-\mu)}$
outliers, where $c$ is some parameter, and $\mu$ is a constant. In the second
result, their algorithm outputs exactly $k$ centers and obtains $O(\log k)$
approximations by discarding $O(z\log k)$ outliers. In both cases, the running
time of their algorithm is $\tilde{O}(ndk)$. Our algorithm compares with their
results as follows: [5] requires a guess of the optimal clustering cost over
inliers $(\rho_{X}(C_{\text{OPT}}))$ to compute their sampling distributions.
Note that this is the quantity we want to estimate in $k$-means with outlier
problems. In contrast, we do not require such a guess of the optimal
clustering cost to compute our sampling distributions. Moreover, their
algorithm discards more than $z$ outliers, whereas ours discards only $z$
points as outliers. We summarise our comparison with the related work in Table
1.

##  4 Seeding algorithm for $k$-means with outliers and its analysis

In this section we present our algorithm – Seeding algorithm for $k$-means
with outliers and its theoretical guarantee. We first state (recall) some
notation for convenience.

We denote $X\subseteq\mathbb{R}^{d}$ as the set of $n$ input points, integers
$k,z>0$ denote the number of cluster centers, and the number of outliers,
respectively. We denote by

$\displaystyle\phi_{A}(C)$ $\displaystyle=\sum_{x\in A}\min_{c\in
C}\left\|x-c\right\|^{2},$ (3)

the contribution of points in a subset $A\subseteq X$. Let $C_{\text{OPT}}$ be
the set of optimal $k$ centers for the _ $k$-means with outlier_ problem and
let $Y_{\text{OPT}}$ be the optimal subset of inliers, then

$\displaystyle\rho_{X}(C_{\text{OPT}})$
$\displaystyle=\phi_{Y_{\text{OPT}}}\left(C_{\text{OPT}}\right).$ (4)

In the optimal solution, each point of $Y_{\text{OPT}}$ is assigned to its
nearest center in $C_{\text{OPT}}$. This induces a natural partition of the
inliers $Y_{\text{OPT}}$ as $A_{1}\cup A_{2}\cup\dotsb\cup A_{k}$ into
disjoint subsets, with means $\mu_{1},\mu_{2},\dotsc,\mu_{k}$, respectively,
while $X\setminus Y_{\text{OPT}}$ are the outliers. Therefore,

$\displaystyle\rho_{X}(C_{\text{OPT}})$
$\displaystyle=\phi_{Y_{\text{OPT}}}\left(C_{\text{OPT}}\right)=\sum_{j=1}^{k}\phi_{A_{j}}\left(\\{\mu_{j}\\}\right).$
(5)

We present our algorithm – Seeding algorithm for $k$-means with outliers in
Algorithm 1. Our sampling (stated in Line 5 of Algorithm 1) is a simple
modification of $k$-means++ sampling distribution which is computed by taking
minimum of $k$-means++ sampling distribution and the term
${\eta\cdot\rho_{X}(S_{i-1})}/{z}$, where $\eta$ is a parameter, $z$ is the
number of outliers. Note that the term $\rho_{X}(S_{i-1})$ is the
$k$-clustering cost (see Equations (4), (5)) by considering the $S_{i-1}$
sampled points as cluster centers, and discarding the farthest $z$ as
outliers.

Algorithm 1 Seeding algorithm for $k$-means with outliers.

1: Input: a set $X\subseteq\mathbb{R}^{d}$ of $n$ points, number of outliers
$z$, a parameter $\eta>0$, and number of iterations $t$.

2: Output: a set $S\subseteq X$ of size $t$.

3: Initialize $S_{0}\leftarrow\emptyset$.

4: for $i=1$ to $t$ do

5: Pick a point $x\in X$ from the following distribution: ${\sf
Pr}\left(\text{picking}\leavevmode\nobreak\
x\right)\propto\min\left\\{\phi_{\\{x\\}}(S_{i-1}),\dfrac{\eta\cdot\rho_{X}(S_{i-1})}{z}\right\\}$

6: $S_{i}\leftarrow S_{i-1}\cup\\{x\\}$

7: $i\leftarrow i+1$

8: end for

9: $S\leftarrow S_{t}$

10: return $S$

We note that a large part of our analysis is similar to Bhaskara et al. [5].
However, the key difference is that they need an estimate of
$\rho_{X}(C_{\text{OPT}})$ to calculate their sampling probabilities – the
optimal clustering cost over inliers, the very quantity which we want to
estimate. On the other hand, our sampling scheme does not require any estimate
of $\rho_{X}(C_{\text{OPT}})$ to calculate the sampling probabilities.

Another difference from Bhaskara et al. [5] is that we can set our parameter
$\eta=1$, which allows us to discard exactly $z$ points as outliers, the same
as what the optimal solution discards. Whereas their algorithm cannot discard
exactly $z$ points as outliers because they need to estimate
$\rho_{X}(C_{\text{OPT}})$ which is required to compute the probability
distribution for sampling the points.

Overview of analysis techniques: Our algorithm is a simple modification of
[2], where we perform a thresholding of the $k$-means++ sampling distribution.
This thresholding is controlled by the parameter $\eta$ (Line 5 of Algorithm
1) that ensures that a small number of outliers points are sampled. In our
analysis,  (i)  we monitor the number of sampled points, and the inlier
clusters determined by them (by marking the farthest $z$ points as outliers),
(ii)  the number of so-called wasted iteration due to sampling outliers. We
measure these quantities using different potential functions. We show two
theoretical guarantees on our algorithm depending on the number of points
sampled in Algorithm 1. We state it in the following theorem.

###### Theorem 1

For any constant parameter $\eta\geq 1$, Algorithm 1, with probability at
least $\delta$, satisfies the following guarantee:

  * •

${\sf E}\left[\rho_{X}(S_{k})\right]=O(\log k)\rho_{X}(C_{\text{OPT}}),$ when
the number of iterations  $t=k$.

  * •

$\rho_{X}(S_{t})\leq\frac{(\eta+64)(1+c)\rho_{X}(C_{\text{OPT}})}{(1-\delta)c}$,
when the number of iterations  $t=(1+c)k$.

We start with proving the following lemma.

###### Lemma 2

Suppose after iteration $i$ of Algorithm 1, we satisfy the following two
conditions:

$\rho_{X}(S_{i})>\alpha\rho_{X}(C_{\text{OPT}})\quad\text{and}\quad\sum_{x\in
X}\min\left\\{\phi_{\\{x\\}}(S_{i}),\dfrac{\eta\rho_{X}(S_{i})}{z}\right\\}\leq\gamma\rho_{X}(C_{\text{OPT}}).$

Then there exists $Y\subseteq X$ such that
$\phi_{Y}(S_{i})\leq\gamma\rho_{X}(C_{\text{OPT}})$ and $\left|X\setminus
Y\right|\leq\gamma z/\alpha\eta$.

######  Proof 4.1.

Let $Y=\\{x\;:\;\phi_{\\{x\\}}(S_{i})\leq\eta\rho_{X}(S_{i})/z\\}$. Then we
get

$\sum_{x\in
X}\min\left\\{\phi_{\\{x\\}}(S_{i}),\dfrac{\eta\rho_{X}(S_{i})}{z}\right\\}=\phi_{Y}(S_{i})+\left|X\setminus
Y\right|\frac{\eta\rho_{X}(S_{i})}{z}\leq\gamma\rho_{X}(C_{\text{OPT}}).$

Thus, $\phi_{Y}(S_{i})\leq\gamma\rho_{X}(C_{\text{OPT}})$ and
$\left|X\setminus Y\right|\leq\gamma z/\alpha\eta$, using
$\rho_{X}(S_{i})>\alpha\rho_{X}(C_{\text{OPT}})$.

Suppose only the second condition is satisfied after iteration $i$, then we
can choose any $\alpha$ and still get that either
$\rho_{X}(S_{i})\leq\alpha\rho_{X}(C_{\text{OPT}})$ or otherwise, using both
the conditions in Lemma 2, we have
$\phi_{Y}(S_{i})\leq\gamma\rho_{X}(C_{\text{OPT}})$ for some $Y\subseteq X$
with $\left|X\setminus Y\right|\leq\gamma z/\alpha\eta$. This implies
$\max\\{\alpha,\gamma\\}$ approximation guarantee while discarding at most
$\gamma z/\alpha\eta$ points as outliers instead of $z$. In particular, we can
use $\alpha=\gamma$ and $\eta=1$ to get $\alpha$-approximation while
discarding at most $z$ points as outliers.

We now focus on proving that the second condition is satisfied in expectation.
First, we show that after $t=k$ iterations, we get $\gamma=O(\log k)$.

######  Theorem 3.

After $k$ iterations of Algorithm 1, we get

${\sf E}\left[\sum_{x\in
X}\min\left\\{\phi_{\\{x\\}}(S_{k}),\dfrac{\eta\rho_{X}(S_{k})}{z}\right\\}\right]=O(\log
k)\cdot\rho_{X}(C_{\text{OPT}}).$

Consider any optimal inlier cluster $A$. Below we show that if
$\phi_{A}(S_{i})\geq 64\leavevmode\nobreak\ \phi_{A}(\\{\mu\\})$ then
$\phi_{\\{\mu\\}}(S_{i})\geq\frac{31}{\left|A\right|}\phi_{A}(\\{\mu\\})$ and
there exists a large subset $B\subseteq A$ such that $\phi_{\\{x\\}}(S_{i})$
values for all $x\in B$ are within a small constant factor of each other. In
other words, $D^{2}$ sampling or sampling w.r.t. $\phi_{\\{x\\}}(S_{i})$ has
an approximately uniform probability distribution over $B$.

######  Lemma 4.

Let $A\subseteq X$ be any subset of points with mean $\mu$. Suppose
$\phi_{A}(S_{i})\geq 64\leavevmode\nobreak\ \phi_{A}(\\{\mu\\})$. Then $S_{i}$
satisfies the following two properties:

  1. 1.

$64\leavevmode\nobreak\
\phi_{A}(\\{\mu\\})\leq\phi_{A}(S_{i})\leq\dfrac{64}{31}\left|A\right|\phi_{\\{\mu\\}}(S_{i})$,
therefore,
$\phi_{\\{\mu\\}}(S_{i})\geq\dfrac{31}{\left|A\right|}\phi_{A}(\\{\mu\\})$.

  2. 2.

Let $B=\left\\{x\in
A\;:\;\dfrac{\phi_{\\{\mu\\}}(S_{i})}{3}\leq\phi_{\\{x\\}}(S_{i})\leq\dfrac{7\leavevmode\nobreak\
\phi_{\\{\mu\\}}(S_{i})}{3}\right\\}$. Then, $B$ is a reasonably large subset
of $A$, i.e., $\left|B\right|\geq\dfrac{25}{31}\left|A\right|$.

######  Proof 4.2.

For any $x\in A$ and any $s\in S_{i}$, the triangle inequality gives

$\frac{1}{2}\leavevmode\nobreak\
\left\|\mu-s\right\|^{2}-\left\|x-\mu\right\|^{2}\leq\left\|x-s\right\|^{2}\leq
2\left\|x-\mu\right\|^{2}+2\left\|\mu-s\right\|^{2}.$

Thus, $\frac{1}{2}\leavevmode\nobreak\
\phi_{\\{\mu\\}}(S_{i})-\left\|x-\mu\right\|^{2}\leq\phi_{\\{x\\}}(S_{i})\leq
2\leavevmode\nobreak\ \phi_{\\{\mu\\}}(S_{i})+2\left\|x-\mu\right\|^{2}$.
Summing the right-hand inequality over $x\in A$, we get

$\phi_{A}(S_{i})\leq
2\left|A\right|\phi_{\\{\mu\\}}(S_{i})+2\leavevmode\nobreak\
\phi_{A}(\\{\mu\\})\leq
2\left|A\right|\phi_{\\{\mu\\}}(S_{i})+\frac{1}{32}\leavevmode\nobreak\
\phi_{A}(S_{i}),$

which gives the first property
$\phi_{A}(S_{i})\leq\frac{64}{31}\left|A\right|\phi_{\\{\mu\\}}(S_{i})$. Now
let $B^{\prime}=\\{x\in
A\;:\;\left\|x-\mu\right\|^{2}\leq\frac{1}{6}\phi_{\\{\mu\\}}(S_{i})\\}$. Then
by using triangle inequality for squared norms, we can check that
$B^{\prime}\subseteq B$. Since $\sum_{x\in
A}\left\|x-\mu\right\|^{2}=\phi_{A}(\\{\mu\\})$, Markov’s inequality implies
that $\left|A\setminus B^{\prime}\right|\leq 6\leavevmode\nobreak\
\phi_{A}(\\{\mu\\})/\phi_{\\{\mu\\}}(S_{i})$. Now using the first property
$\phi_{A}(S_{i})\leq\dfrac{64}{31}\left|A\right|\phi_{\\{\mu\\}}(S_{i})$ and
the assumption $\phi_{A}(S_{i})\geq 64\leavevmode\nobreak\
\phi_{A}(\\{\mu\\})$, we get $\left|A\setminus B^{\prime}\right|\leq
6\left|A\right|/31$. Since $B^{\prime}\subseteq B$, we get the second property
$\left|B\right|\geq\frac{25}{31}\left|A\right|$.

The lemma below shows that in each iteration of Algorithm 1, if we pick a
point from an optimal inlier cluster $A$, then we get a $64$-approximation
guarantee for it, in expectation.

######  Lemma 5.

For any $A\subseteq X$ and its mean $\mu$, the point $x$ picked by Algorithm 1
in a single iteration satisfies ${\sf
E}\left[\phi_{A}(S_{i}\cup\\{x\\})\;|\;x\in A\right]\leq
64\leavevmode\nobreak\ \phi_{A}(\\{\mu\\})$.

######  Proof 4.3.

Let $B=\left\\{x\in
A\;:\;\dfrac{\phi_{\\{\mu\\}}(S_{i})}{3}\leq\phi_{\\{x\\}}(S_{i})\leq\dfrac{7\leavevmode\nobreak\
\phi_{\\{\mu\\}}(S_{i})}{3}\right\\}$, as defined in Lemma 4. Suppose
$\frac{7}{3}\phi_{\\{\mu\\}}(S_{i})\leq\eta\rho_{X}(S_{i})/z$. Then for all
$x\in B$, we have
$\min\\{\phi_{\\{x\\}}(S_{i}),\eta\rho_{X}(S_{i})/z\\}\geq\frac{1}{3}\phi_{\\{\mu\\}}(S_{i})$.
Hence,

$\displaystyle\sum_{x\in
A}\min\\{\phi_{\\{x\\}}(S_{i}),\eta\rho_{X}(S_{i})/z\\}$
$\displaystyle\geq\sum_{x\in
B}\min\\{\phi_{\\{x\\}}(S_{i}),\eta\rho_{X}(S_{i})/z\\}$
$\displaystyle\geq\left|B\right|\frac{1}{3}\phi_{\\{\mu\\}}(S_{i})$
$\displaystyle\geq\frac{25}{31}\left|A\right|\cdot\frac{1}{3}\cdot\frac{31}{64}\frac{\phi_{A}(S_{i})}{\left|A\right|}\qquad\text{using
Lemma \ref{lemma:approx-unif}}$ $\displaystyle\geq\frac{\phi_{A}(S_{i})}{8}.$

Therefore, for all $x\in A$, we have

$\frac{\min\\{\phi_{\\{x\\}}(S_{i}),\eta\rho_{X}(S_{i})/z\\}}{\sum_{x\in
A}\min\\{\phi_{\\{x\\}}(S_{i}),\eta\rho_{X}(S_{i})/z\\}}\leq\frac{\phi_{\\{x\\}}(S_{i})}{8\leavevmode\nobreak\
\phi_{A}(S_{i})}.$

In other words, if we sample $x\in A$ as in Algorithm 1 with probability
proportional to $\min\\{\phi_{\\{x\\}}(S_{i}),\eta\rho_{X}(S_{i})/z\\}$ then,
up to a multiplicative factor of $8$, we get a similar upper bound on any
expectation calculated for sampling with probability proportional to
$\phi_{\\{x\\}}(S_{i})$, i.e., $D^{2}$ sampling. Now the proof of Lemma 5 is
immediate using the key lemma about $D^{2}$ sampling from Arthur and
Vassilvitskii [2] stated below.

The following key lemma was used by Arthur and Vassilvitski [2] in their
analysis of $k$-means++ algorithm that uses $D^{2}$ sampling.

######  Lemma 6.

For any $A\subseteq X$ and its mean $\mu$, the point $x$ picked by $D^{2}$
sampling satisfies ${\sf E}\left[\phi_{A}(S_{i}\cup\\{x\\})\;|\;x\in
A\right]\leq 8\leavevmode\nobreak\ \phi_{A}(\\{\mu\\})$.

Proof of Theorem 3 is then similar to that in Theorem $3.1$ of Bhaskara et al.
[5]. We define $U_{i}$ as the number of points in optimal inlier clusters
untouched by Algorithm 1 until step $i$. Further, let $H_{i}$ denote the union
of points in the covered (optimal) clusters until step $i$. Let $w_{i}$ be the
number of wasted iterations, i.e., iterations that pick either outliers
$X\setminus Y_{\text{OPT}}$ or repeat points from already touched inlier
clusters $A_{j}$’s from the optimal solution $Y_{\text{OPT}}=A_{1}\cup
A_{2}\cup\dotsc\cup A_{k}$. We denote $n_{i}$ as the number of uncovered
optimal clusters at iteration $i$.

For brevity we denote

$\xi(U_{i},S_{i}):=\sum_{x\in
U_{i}}\min\left\\{\phi_{\\{x\\}}(S_{i}),\dfrac{\eta\cdot\rho_{X}(S_{i})}{z}\right\\}.$

We define a similar potential function as in Bhaskara et al. [5].

$\Psi_{i}=\frac{w_{i}\cdot\xi(U_{i},S_{i})}{n_{i}}.$

For any $i>0$, we have the following lemma:

######  Lemma 7 (Adapted from Lemma $9$ of [5]).

${\sf E}\left[\xi(H_{i},S_{i})\right]\leq 64.\rho_{X}(C_{\text{OPT}}).$

A proof of the above lemma is similar to that of Lemma $9$ of [5], and follows
from Lemma 5 and 4 along with the inductive argument. We defer it to the full
version of the paper.

######  Lemma 8 (Adapted from Lemma $8$ of [5]).

Let $S_{i}$ be the set of sampled points in the $i$-th iteration, then we have

${\sf
E}\left[\Psi_{i+1}-\Psi_{i}|S_{i}\right]\leq\frac{\alpha\cdot\rho_{X}(C_{\text{OPT}})+\xi(H_{i},S_{i})}{k-i}.$

In Lemma 8, $\alpha$ is a constant mentioned as in Lemma 2. A proof of Lemma 8
is analogous to the proof of Lemma $8$ of [5]. We defer it to the full version
of the paper.

We now conclude a proof of Theorem 3. Its proof completes via combining Lemma
7 and 8, and summing over $0\leq i\leq k-1$.

Further, similar to Bhaskara et al. [5], we can show the following
generalization for $t=(1+c)k$ iterations.

######  Theorem 9.

For any $\delta>0$ and parameters $c,\eta>0$, after $t=(1+c)k$ iterations of
Algorithm 1 we get

$\sum_{x\in
X}\min\left\\{\phi_{\\{x\\}}(S_{t}),\dfrac{\eta\rho_{X}(S_{t})}{z}\right\\}\leq\frac{(\eta+64)(1+c)\rho_{X}(C_{\text{OPT}})}{(1-\delta)c},$

with probability at least $\delta$.

##  5 Experiments

##### Hardware description.

We performed our experiments on a machine having the following configuration:
CPU: Intel(R) Core(TM) i5-3320M CPU @ 2.70GHz x 4; Memory: 8 GB.

##### Baseline algorithms:

We study the performance of our algorithm (Algorithm 1) to find $k$ initial
cluster centers with the following baselines:  (a) $\mathrm{TKM++}$(Greedy
Sampling for Approximate Clustering in the Presence of Outliers) [5],  (b)
$\mathrm{RKM++}$(Robust $k$-means++ [10]),  (c) $\mathrm{KM++}$($k$-means++
[2]) , and  (d) random seeding [18].  Robust $k$-means++ ($\mathrm{RKM++}$)
[10] uses $(\alpha,1-\alpha)$ mixture of uniform and $D^{2}$ sampling
distribution. For a parameter $\delta\in(0,1)$, their algorithm samples
$O(k/\delta)$ points, then $k$ points are picked from this sampled set using
weighted $k$-means++ sampling [10, 4]. We use $\alpha=1/2$ and $\delta=0.1$
for all the experiments. $\mathrm{TKM++}$ [5] requires one parameter – an
initial guess of optimal clustering cost – to derive the probability
distribution on each data point. In their paper they did not mention any
principal way of guessing the clustering cost. For our empirical comparison we
used, the cost $k$-means++ results as an initial guess. Similar to our
algorithm, they also require an error parameter to derive the probability
distribution. In order to have a fair comparison, we used the same value of
the error parameter $\beta$ in both the algorithms.

##### Evaluation metric:

In all the baselines, once we sample the $k$ cluster centers, we mark the
farthest $z$ points as outliers. We then note the clustering cost over inliers
considering the $k$ sampled points as the cluster centers. We note the
minimum, maximum, and average values of the clustering cost are over $10$
repetitions. We also use precision and recall as our evaluation metric. If
$z^{*}$ is the set of true outliers and $z$ is the set of outliers reported by
the algorithm, then precision:=$|z^{*}\cap z|/|z|$, and recall:=$|z^{*}\cap
z|/|z^{*}|$. We also note the seeding time of the baseline algorithms to have
a comparison of their efficiency.

Table 2: Result on Synthetic dataset with $k=20$ and $z=25,50,100$ outliers.
We mark the farthest $25,50$ and $100$ points as outliers, respectively. For
$\mathrm{RKM++}$ we use $\delta=0.1$ and $\alpha=1/2$. We used the parameter
$\beta=0.5$ for both $\mathrm{TKM++}$ and our method. All costs are
multiplicative of $10^{4}$.

Method | $z$ | Precision | Recall | Cost | Time (s)
---|---|---|---|---|---
|  | Max. | Avg. | Med. | Max. | Avg. | Med. | Min. | Avg. | Med. |
$\mathrm{RAND}$ | $25$ | $0.52$ | $0.31$ | $0.30$ | $0.52$ | $0.31$ | $0.30$ | $0.57$ | $1.20$ | $1.05$ | $0.06$
$\mathrm{KM++}$ | $25$ | $0.72$ | $0.53$ | $0.50$ | $0.72$ | $0.53$ | $0.5$ |  0.22 | $0.43$ | $0.41$ | $0.20$
$\mathrm{TKM++}$ | $25$ | $0.88$ | $0.67$ | $0.72$ | $0.88$ | $0.67$ | $0.72$ | $0.25$ | $0.58$ | $0.51$ | $0.92$
$\mathrm{RKM++}$ | $25$ | $0.88$ | $0.82$ |  0.84 | $0.88$ | $0.82$ |  0.84 | $0.25$ | $0.29$ |  0.30 | $6.5$
This work | $25$ |  0.92 |  0.88 |  0.84 |  0.92 |  0.88 |  0.84 |  0.22 |  0.26 |  0.32 | $0.90$
$\mathrm{RAND}$ | $50$ | $0.34$ | $0.18$ | $0.21$ | $0.34$ | $0.18$ | $0.21$ | $1.42$ | $2.65$ | $2.54$ | $0.10$
$\mathrm{KM++}$ | $50$ | $0.80$ | $0.42$ | $0.38$ | $0.80$ | $0.42$ | $0.38$ | $0.31$ | $0.89$ | $0.85$ | $0.23$
$\mathrm{TKM++}$ | $50$ | $0.82$ | $0.76$ | $0.48$ | $0.82$ | $0.76$ | $0.48$ | $0.34$ | $0.37$ | $0.69$ | $0.49$
$\mathrm{RKM++}$ | $50$ | $0.88$ | $0.82$ | $0.83$ | $0.88$ | $0.82$ | $0.83$ |  0.18 |  0.19 |  0.18 | $6.5$
This work | $50$ |  0.92 |  0.88 |  0.84 |  0.92 |  0.88 |  0.84 |  0.22 | $0.26$ |  0.32 | $0.60$
$\mathrm{RAND}$ | $100$ | $0.36$ | $0.20$ | $0.20$ | $0.44$ | $0.24$ | $0.24$ | $0.95$ | $1.71$ | $1.85$ | $0.06$
$\mathrm{KM++}$ | $100$ | $0.68$ | $0.49$ | $0.51$ | $0.82$ | $0.59$ | $0.62$ | $0.25$ | $0.58$ | $0.55$ | $0.19$
$\mathrm{TKM++}$ | $100$ | $0.75$ | $0.49$ | $0.54$ | $0.90$ | $0.59$ | $0.65$ | $0.23$ | $0.71$ | $0.60$ | $0.71$
$\mathrm{RKM++}$ | $100$ |  0.81 |  0.78 |  0.77 |  0.98 |  0.94 |  0.93 | $0.32$ | $0.42$ | $0.41$ | $6.5$
This work | $100$ |  0.77 |  0.76 |  0.74 |  0.93 |  0.91 |  0.89 |  0.18 |  0.22 |  0.21 | $0.93$

###  5.1 Results on Synthetic Data Sets

##### Dataset.

We generate synthetic dataset in the similar way as used in $k$-means++ [2].
We discuss it as follows. We pick $k+z$ uniformly random points from a large
$d$-dimensional hypercube of side length $s=100$. We use $k$ points from them
as means and pick $n/k$ points around each of them from a random Gaussian of
unit variance. This gives a data set of $n+z$ points with $n$ points clustered
into $k$ clusters and the remaining $z$ as outliers.

##### Empirical Evaluation.

We perform experiments on synthetic datasets with values $n=1000,d=2,k=20$ and
the number of outliers $25,50,100$, and we summarise our results in Table 2.

##### Insight.

In almost every scenario our algorithm outperforms with respect to random,
$k$-means++ and $\mathrm{TKM++}$ in terms of both precision/recall, and
clustering cost metric. Our performance was comparable/better on most of the
instances with respect to $\mathrm{RKM++}$. Our algorithm is much faster than
$\mathrm{RKM++}$, and comparable with respect to $\mathrm{TKM++}$, however it
was slightly off with respect to random, $k$-means++.

###  5.2 Results on real world data sets

####  5.2.1 Small clusters as outliers:

In this setting, we consider a few very small clusters as outliers and try to
locate them using our baselines.

##### Results on Shuttle dataset.

Shuttle training data set from UCI Machine Learning Repository [17] contains
$43,500$ points. It has $7$ classes in total. The two smallest classes contain
only $17$ points and we would like to detect these as outliers. We run our
baselines on the Shuttle dataset with $k\in\\{5,10,15\\}$. We summarise our
empirical findings in Table 3.

Table 3: Result on Shuttle dataset considering the two smallest classes as
outliers which contain only $17$ points. We mark the farthest $21,34$, and
$51$ points as outliers when the values of $k$ are $5,10,$ and $15$,
respectively. In both $\mathrm{TKM++}$ and our algorithm, we used the error
parameter $\beta=0.1$. For $\mathrm{RKM++}$ we use $\delta=0.1$ and
$\alpha=1/2$. All costs are multiplicative of $10^{8}.$

Method | $k$ | Precision | Recall | Cost | Time (s)
---|---|---|---|---|---
|  | Max. | Avg. | Med. | Max. | Avg. | Med. | Min. | Avg. | Med. |
$\mathrm{RAND}$ | $5$ | $0.19$ |  0.19 | $0.19$ | 0.23 |  0.23 | $0.23$ | $3.56$ | $3.66$ | $3.63$ | $1.01$
$\mathrm{KM++}$ | $5$ |  0.28 | $0.17$ |  0.23 |  0.35 | $0.21$ |  0.29 | $1.77$ | $2.22$ | $2.27$ | $2.26$
$\mathrm{TKM++}$ | $5$ | $0.23$ | $0.17$ |  0.23 | $0.29$ | $0.21$ |  0.29 | $1.70$ | $2.26$ | $2.23$ | $3.42$
$\mathrm{RKM++}$ | $5$ | $0.26$ | $0.18$ |  0.23 | $0.33$ |  0.23 |  0.29 | $1.85$ |  2.07 |  2.01 | $5.3$
This work | $5$ | $0.23$ |  0.19 |  0.23 | $0.29$ |  0.23 |  0.29 |  1.53 | 2.08 |  2.01 | $3.54$
$\mathrm{RAND}$ | $10$ | $0.14$ | $0.14$ | $0.14$ | $0.29$ | $0.29$ | $0.29$ | $1.55$ | $1.78$ | $1.80$ | $1.54$
$\mathrm{KM++}$ | $10$ | $0.26$ |  0.16 |  0.17 | $0.52$ | $0.31$ |  0.35 | $0.72$ | $0.95$ | $0.92$ | $3.41$
$\mathrm{TKM++}$ | $10$ | $0.26$ | $0.14$ | $0.11$ | $0.52$ | $0.29$ | $0.23$ | $0.73$ | $0.96$ | $0.90$ | $7.35$
$\mathrm{RKM++}$ | $10$ | $0.34$ | $0.15$ | $0.15$ | $0.68$ | $0.30$ | $0.30$ | $0.69$ | $0.85$ | $0.85$ |  11.5
This work | $10$ |  0.35 |  0.16 |  0.17 |  0.70 |  0.32 |  0.35 |  0.56 |  0.65 |  0.64 |  8.7
$\mathrm{RAND}$ | $15$ | $0.13$ | $0.13$ | $0.13$ | $0.41$ | $0.41$ | $0.41$ | $0.80$ | $0.85$ | $0.84$ | $2.15$
$\mathrm{KM++}$ | $15$ | $0.25$ | $0.17$ | 0.19 | $0.76$ | $0.52$ | $0.58$ | $0.39$ | $0.49$ | $0.50$ | $5.25$
$\mathrm{TKM++}$ | $15$ | $0.25$ | $0.17$ | 0.19 | $0.76$ | $0.52$ | 0.58 | $0.36$ | $0.48$ | $0.48$ |  11.20
$\mathrm{RKM++}$ | $15$ | $0.29$ |  0.21 |  0.22 | $0.88$ | $0.64$ |  0.67 | $0.42$ | $0.49$ | $0.49$ |  19.5
This work | $15$ |  0.31 | 0.18 | $0.18$ |  0.94 |  0.55 | 0.52 |  0.27 |  0.31 |  0.31 |  13.12

##### Results on KDDCup Full dataset:

KDDFull [17] This dataset is from $1999$ kddcup competition and contains
instances describing connections of sequences of tcp packets, and have about
$4.9$M data points. We only consider the $34$ numerical features of this
dataset. We also normalize each feature so that it has zero mean and unit
standard deviation. There are $23$ classes in this dataset, $98.3\%$ points of
the dataset belong to $3$ classes (normal $19.6\%$, neptune $21.6\%$, and
smurf $56.8\%$). We consider the remaining small clusters as outliers, and the
number of outliers is $45747$. We run our baselines on the KDDFull dataset
with $k=3,5$ and considering above mentioned $45747$ points as outliers. We
summarise our empirical findings in Table 4.

Table 4: Result on KDDCup dataset with $k=3$ and $k=5$ with $45747$ outliers.
We used the error parameter $\beta=0.1$ for both $\mathrm{TKM++}$ and our
algorithm. For $\mathrm{RKM++}$ we use $\delta=0.1$ and $\alpha=1/2$. All
costs are multiplicative of $10^{7}.$

Method | $k$ | Precision | Recall | Cost | Time (s)
---|---|---|---|---|---
|  | Max. | Avg. | Med. | Max. | Avg. | Med. | Min. | Avg. | Med. |
$\mathrm{RAND}$ | $3$ | $0.64$ |  0.63 |  0.64 | $0.64$ |  0.63 |  0.64 | 2.83 | 4.04 | $4.10$ |  77.1
$\mathrm{KM++}$ | $3$ | $0.64$ | $0.59$ | $0.61$ | $0.64$ | $0.59$ | $0.61$ | $3.29$ | $5.41$ | $4.86$ |  119.2
$\mathrm{TKM++}$ | $3$ | $0.64$ | $0.57$ | $0.61$ | $0.64$ | $0.57$ | $0.61$ | $2.83$ | $5.76$ | $5.83$ |  211.86
$\mathrm{RKM++}$ | $3$ | $0.64$ | $0.62$ | $0.61$ | $0.64$ | $0.62$ | $0.61$ |  2.8 |  2.8 |  2.8 |  295
This work | $3$ |  0.65 |  0.63 |  0.64 |  0.65 |  0.63 |  0.64 |  2.83 | $4.20$ | 4.07 |  225.23
$\mathrm{RAND}$ | $5$ | $0.64$ | $0.57$ |  0.60 | $0.64$ | $0.57$ |  0.60 |  2.48 | $4.23$ | $2.95$ |  100.2
$\mathrm{KM++}$ | $5$ | $0.63$ | $0.54$ | $0.59$ | $0.63$ | $0.54$ | $0.59$ | $2.61$ |  3.27 |  2.83 |  292.1
$\mathrm{TKM++}$ | $5$ | $0.63$ | $0.45$ | $0.44$ | $0.63$ | $0.45$ | $0.44$ | $2.98$ | $3.85$ | $3.63$ |  402.3
$\mathrm{RKM++}$ | $5$ | $0.64$ | $0.58$ | $0.61$ | $0.64$ | $0.58$ | $0.61$ | $2.52$ | $3.8$ | $3.7$ | 600.2
This work | $5$ |  0.65 |  0.60 |  0.60 |  0.65 |  0.60 |  0.60 | $2.54$ | $3.78$ | $3.11$ |  423.1

##### Insight.

For both KDDCup and Shuttle datasets, we noticed that our clustering results
in terms of both – cost and precision/recall metric are significantly better
than that of $\mathrm{TKM++}$, $k$-means++ and random seeding, whereas it is
comparable w.r.t. $\mathrm{RKM++}$. The running time of our algorithm is
faster than $\mathrm{RKM++}$ and $\mathrm{RAND}$ whereas it is comparable with
respect to the other remaining baselines.

####  5.2.2 Randomly sampling a small fraction of points and adding large
Gaussian noise to them

In this setting, we randomly sample a small fraction of points from the
datasets, and add large Gaussian noise to their dimensions. We consider these
points as outliers and and try to locate them using our baselines.

##### Results on Skin Segmentation [17] and Shuttle dataset:

The Skin Segmentation data is constructed over B, G, R color space. Skin and
Non-skin data points are generated using skin textures from face images of
diversity of age, gender, and race people. The dataset consists of $245057$
points and each data point has $4$ attributes. We sample $2.5\%$ of points and
add large Gaussian noise to their features. We summarise our empirical
findings in Table 5.

##### Results on Shuttle dataset:

For the Shuttle dataset, we randomly sample $1000$ points from the dataset and
add large Gaussian noise to their features. We consider them as outliers and
try to locate them using our baseline methods. We summarise our empirical
findings in Table 6.

Table 5:  Result on Skin dataset with $k=20,40,50$. We randomly sample $2.5\%$
of points and add large Gaussian noise to their features. In both
$\mathrm{TKM++}$ and our algorithm, we used the error parameter $\beta=0.1$.
For $\mathrm{RKM++}$ we use $\delta=0.1$ and $\alpha=1/2$. All costs are
multiplicative of $10^{8}.$

Method | $k$ | Precision | Recall | Cost | Time (s)
---|---|---|---|---|---
|  | Max. | Avg. | Med. | Max. | Avg. | Med. | Min. | Avg. | Med. |
$\mathrm{RAND}$ | $20$ | $0.15$ | $0.10$ | $0.10$ | $0.15$ | $0.10$ | $0.10$ | $1.35$ | $1.69$ | $1.69$ |  25.23
$\mathrm{KM++}$ | $20$ | $0.20$ |  0.16 | $0.15$ | $0.20$ |  0.16 | $0.15$ | $1.15$ | 1.23 | 1.23 |  45.08
$\mathrm{TKM++}$ | $20$ | $0.09$ | $0.08$ | $0.08$ | $0.09$ | $0.08$ | $0.08$ | $1.98$ | $2.20$ | $1.91$ |  74.13
$\mathrm{RKM++}$ | $20$ |  0.24 |  0.16 |  0.17 |  0.24 |  0.16 |  0.17 | 1.15 |  1.20 |  1.20 |  123.7
This work | $20$ | 0.23 |  0.16 |  0.17 | 0.23 |  0.16 |  0.17 |  1.10 | $1.35$ | $1.35$ |  85.30
$\mathrm{RAND}$ | $40$ | $0.20$ | $0.13$ | $0.13$ | $0.20$ | $0.13$ | $0.13$ | $0.77$ | $0.96$ | $0.95$ |  31.20
$\mathrm{KM++}$ | $40$ | 0.25 |  0.19 | $0.19$ | 0.25 |  0.19 | $0.19$ | $0.65$ | $0.68$ | $0.69$ |  85.80
$\mathrm{TKM++}$ | $40$ | $0.16$ | $0.12$ | $0.12$ | $0.16$ | $0.12$ | $0.12$ | $0.79$ | $0.87$ | $0.86$ |  125.12
$\mathrm{RKM++}$ | $40$ |  0.26 |  0.19 | $0.19$ |  0.26 |  0.19 | $0.19$ |  0.63 | $0.68$ |  0.65 |  196.3
This work | $40$ | $0.23$ |  0.19 |  0.20 | $0.23$ |  0.19 |  0.20 | 0.64 |  0.66 |  0.65 |  140.21
$\mathrm{RAND}$ | $50$ | $0.15$ | $0.09$ | $0.08$ | $0.15$ | $0.09$ | $0.08$ | $0.71$ | $0.79$ | $0.78$ |  48.53
$\mathrm{KM++}$ | $50$ | $0.22$ | $0.18$ | $0.17$ | $0.22$ | $0.18$ | $0.17$ |  0.51 | $0.54$ |  0.53 |  138.23
$\mathrm{TKM++}$ | $50$ | $0.23$ | $0.19$ | $0.18$ | $0.23$ | $0.19$ | $0.18$ | $0.60$ | $0.66$ | $0.65$ |  204.39
$\mathrm{RKM++}$ | $50$ |  0.29 |  0.22 | 0.18 |  0.29 |  0.22 | 0.18 |  0.51 |  0.53 |  0.53 |  324.39
This work | $50$ |  0.29 |  0.22 |  0.19 |  0.29 |  0.22 |  0.19 | $0.52$ |  0.53 | $0.54$ |  220.39

Table 6:  Results on Shuttle dataset by randomly sampling $1000$ points and
adding large Gaussian noise to their features. In both $\mathrm{TKM++}$ and
our algorithm, we used the error parameter $\beta=0.1$. All costs are
multiplicative of $10^{8}$.

Method | $k$ | Precision | Recall | Cost | Time (s)
---|---|---|---|---|---
|  | Max. | Avg. | Med. | Max. | Avg. | Med. | Min. | Avg. | Med. |
$\mathrm{RAND}$ | $10$ | $0.80$ | $0.70$ | $0.73$ | $0.80$ | $0.70$ | $0.73$ |  0.21 |  0.27 |  0.25 | $1.24$
$\mathrm{KM++}$ | $10$ | $0.81$ | $0.76$ | $0.80$ | $0.81$ | $0.76$ | $0.80$ | $0.29$ | $0.45$ | $0.47$ | $3.32$
$\mathrm{TKM++}$ | $10$ | 0.82 | $0.76$ | $0.80$ | 0.82 | $0.76$ | $0.80$ | $0.29$ | $0.45$ | $0.47$ | $5.36$
$\mathrm{RKM++}$ | $10$ |  0.83 |  0.81 | 0.80 |  0.83 |  0.81 | 0.80 | $0.28$ | $0.36$ | $0.36$ |  10.0
This work | $10$ | 0.82 |  0.81 |  0.81 | 0.82 |  0.81 |  0.81 | $0.29$ | $0.38$ | $0.38$ | $6.32$
$\mathrm{RAND}$ | $20$ | $0.80$ | $0.80$ | $0.80$ | $0.80$ | $0.80$ | $0.80$ |  0.21 |  0.20 |  0.19 | $2.60$
$\mathrm{KM++}$ | $20$ | $0.82$ | $0.72$ | $0.79$ | $0.82$ | $0.72$ | $0.79$ | $0.25$ | $0.28$ | $0.26$ | $7.24$
$\mathrm{TKM++}$ | $20$ | $0.83$ | $0.73$ |  0.81 | $0.83$ | $0.73$ |  0.81 | $0.24$ | $0.27$ | $0.25$ | $7.35$
$\mathrm{RKM++}$ | $20$ |  0.85 |  0.76 | $0.80$ |  0.85 |  0.76 | $0.80$ | $0.22$ | $0.23$ | $0.20$ |  17.4
This work | $20$ | 0.84 | 0.75 | $0.79$ | 0.84 | 0.75 | $0.79$ | $0.23$ | $0.24$ | $0.25$ |  11.23
$\mathrm{RAND}$ | $40$ | $0.80$ | $0.77$ | $0.78$ | $0.80$ | $0.77$ | $0.78$ |  0.12 |  0.14 |  0.14 | $4.94$
$\mathrm{KM++}$ | $40$ | $0.82$ | $0.79$ | $0.78$ | $0.82$ | $0.79$ | $0.78$ | $0.14$ | $0.17$ | $0.17$ | $5.25$
$\mathrm{TKM++}$ | $40$ | 0.83 | $0.79$ | $0.79$ | 0.83 | $0.79$ | $0.79$ | $0.14$ | $0.17$ | $0.17$ | $11.20$
$\mathrm{RKM++}$ | $40$ |  0.84 |  0.80 |  0.82 |  0.84 |  0.80 |  0.82 | $0.13$ | $0.14$ | $0.15$ | $19.70$
This work | $40$ | 0.83 |  0.80 | 0.80 | 0.83 | 0.80 |  0.80 | $0.14$ | $0.16$ | $0.15$ | $13.12$

##### Insight.

For both Skin and Shuttle datasets, we noticed that our clustering results in
terms of precision/recall metric are significantly better than that of
$\mathrm{TKM++}$, $k$-means++ and random seeding on the majority of instances.
However it is comparable with respect to $\mathrm{RKM++}$. The running time of
our algorithm is faster than $\mathrm{RKM++}$ and $\mathrm{RAND}$ whereas it
is comparable with respect to the remaining baselines.

##  6 Concluding remarks and open questions

We suggest an outlier robust seeding for the $k$-means clustering problem. Our
major contribution lies in developing a simple and intuitive tweak to the
$k$-means++ sampling algorithm, which makes it robust to outliers. The running
time of our method is $O(ndk)$, and offers $O(\log k)$ approximation
guarantee. We also gave a bi-criteria approximation algorithm, where our
algorithm samples slightly more than $k$ points as cluster centers, which
consist of a set of $k$ points (as inlier cluster centers) that gives $O(1)$
approximation guarantee. We empirically evaluate our algorithm on synthetic as
well as real-world datasets, and show that our proposal outperforms w.r.t.
$k$-means++ [2], random initialization, and $\mathrm{TKM++}$ [5] algorithm in
both the metric a) precision/recall and b) $k$-means with outliers clustering
cost (Equation 2). However the performance of our proposal remains comparable
to $\mathrm{RKM++}$ [10]. The running time of our algorithm is significantly
faster than the random seeding and $\mathrm{RKM++}$ whereas it is noted to be
comparable w.r.t. $k$-means++ [2], and $\mathrm{TKM++}$ [5]. Our work leaves
the possibility of several open questions: – improving the theoretical bounds
of our proposal, and extending it to other class clustering problems with
outliers setting. Finally, given our proposal’s simplicity, performance, and
efficiency, we hope it will be adopted in practice.

## References

  * Aloise et al. [2009] Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat.  Np-hardness of euclidean sum-of-squares clustering.  _Mach. Learn._ , 75(2):245–248, 2009.  10.1007/s10994-009-5103-0.  URL https://doi.org/10.1007/s10994-009-5103-0.
  * Arthur and Vassilvitskii [2007] David Arthur and Sergei Vassilvitskii.  k-means++: the advantages of careful seeding.  In _Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007_ , pages 1027–1035, 2007.  URL http://dl.acm.org/citation.cfm?id=1283383.1283494.
  * Bachem et al. [2018] Olivier Bachem, Mario Lucic, and Andreas Krause.  Scalable k -means clustering via lightweight coresets.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018_, pages 1119–1127, 2018.  10.1145/3219819.3219973.  URL https://doi.org/10.1145/3219819.3219973.
  * Bahmani et al. [2012] Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, and Sergei Vassilvitskii.  Scalable k-means++.  _Proc. VLDB Endow._ , 5(7):622–633, March 2012\.  ISSN 2150-8097.  10.14778/2180912.2180915.  URL http://dx.doi.org/10.14778/2180912.2180915.
  * Bhaskara et al. [2019] Aditya Bhaskara, Sharvaree Vadgama, and Hong Xu.  Greedy sampling for approximate clustering in the presence of outliers.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 11146–11155. Curran Associates, Inc., 2019.  URL http://papers.nips.cc/paper/9294-greedy-sampling-for-approximate-clustering-in-the-presence-of-outliers.pdf.
  * Chandola et al. [2009] Varun Chandola, Arindam Banerjee, and Vipin Kumar.  Anomaly detection: A survey.  _ACM Comput. Surv._ , 41(3):15:1–15:58, 2009\.  10.1145/1541880.1541882.  URL https://doi.org/10.1145/1541880.1541882.
  * Charikar et al. [2001] Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan.  Algorithms for facility location problems with outliers.  In _Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA._ , pages 642–651, 2001.  URL http://dl.acm.org/citation.cfm?id=365411.365555.
  * Chawla and Gionis [2013] Sanjay Chawla and Aristides Gionis.  _k-means–: A unified approach to clustering and outlier detection_ , pages 189–197.  2013\.  10.1137/1.9781611972832.21.  URL http://epubs.siam.org/doi/abs/10.1137/1.9781611972832.21.
  * Chen [2008] Ke Chen.  A constant factor approximation algorithm for k-median clustering with outliers.  _Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms_ , 01 2008.  10.1145/1347082.1347173.
  * Deshpande et al. [2020] Amit Deshpande, Praneeth Kacham, and Rameshwar Pratap.  Robust k-means++.  In _Proceedings of the Thirty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI 2020, virtual online, August 3-6, 2020_ , page 340, 2020.  URL http://www.auai.org/uai2020/proceedings/340_main_paper.pdf.
  * Feldman and Langberg [2011] Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In _Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011_ , pages 569–578, 2011\.  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 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007_ , pages 11–18, 2007.  10.1145/1247069.1247072.  URL https://doi.org/10.1145/1247069.1247072.
  * Friggstad et al. [2018] Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R. Salavatipour.  Approximation schemes for clustering with outliers.  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018_ , pages 398–414, 2018.  10.1137/1.9781611975031.27.  URL https://doi.org/10.1137/1.9781611975031.27.
  * 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.  10.1145/3188745.3188882.  URL https://doi.org/10.1145/3188745.3188882.
  * Kumar et al. [2005] Amit Kumar, Yogish Sabharwal, and Sandeep Sen.  Linear time algorithms for clustering problems in any dimensions.  In _Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings_ , pages 1374–1385, 2005.  10.1007/11523468_111.  URL https://doi.org/10.1007/11523468_111.
  * Langberg and Schulman [2010] Michael Langberg and Leonard J. Schulman.  Universal epsilon-approximators for integrals.  In _Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010_ , pages 598–607, 2010.  10.1137/1.9781611973075.50.  URL https://doi.org/10.1137/1.9781611973075.50.
  * Lichman [2013] M. Lichman.  Uci machine learning repository.  2013\.
  * Lloyd [2006] S. Lloyd.  Least squares quantization in pcm.  _IEEE Trans. Inf. Theor._ , 28(2):129–137, September 2006.  ISSN 0018-9448.  10.1109/TIT.1982.1056489.
  * Mahajan et al. [2012] Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan.  The planar k-means problem is np-hard.  _Theor. Comput. Sci._ , 442:13–21, 2012.  10.1016/j.tcs.2010.05.034.  URL https://doi.org/10.1016/j.tcs.2010.05.034.
  * Rousseeuw and van Driessen [1999] Peter J. Rousseeuw and Katrien van Driessen.  A fast algorithm for the minimum covariance determinant estimator.  _Technometrics_ , 41(3):212–223, 1999.  10.1080/00401706.1999.10485670.  URL https://doi.org/10.1080/00401706.1999.10485670.