Extreme Value k-means Clustering
Authors: Sixiao Zheng
Yanxi Hou
Yanwei Fu
Jianfeng Feng
Venue:  (2020)
Keywords: unsupervised learning
clustering
k-means
Extreme Value Theory

Abstract: Clustering is the central task in unsupervised learning and data mining. k-means is one of the most widely used clustering algorithms. Unfortunately, it is generally non-trivial to extend k-means to cluster data points beyond Gaussian distribution, particularly, the clusters with non-convex shapes (Beliakov & King, 2006). To this end, we, for the first time, introduce Extreme Value Theory (EVT) to improve the clustering ability of k-means. Particularly, the Euclidean space was transformed into a novel probability space denoted as extreme value space by EVT. We thus propose a novel algorithm called Extreme Value k-means (EV k-means), including GEV k-means and GPD k-means. In addition, we also introduce the tricks to accelerate Euclidean distance computation in improving the computational efficiency of classical k-means. Furthermore, our EV k-means is extended to an online version, i.e., online Extreme Value k-means, in utilizing the Mini Batch k-means to cluster streaming data. Extensive experiments are conducted to validate our EV k-means and online EV k-means on synthetic datasets and real datasets. Experimental results show that our algorithms significantly outperform competitors in most cases.

Under review as a conference paper at ICLR 2020
EXTREME VALUE ME-NS CLUSTERING
Anonymous authors Paper under double-blind review
ABSTRACT
Clustering is the central task in unsupervised learning and data mining. k-means is one of the most widely used clustering algorithms. Unfortunately, it generally non-trivial to extend k-means to cluster data samples beyond Gaussian distribu- tion, particularly, the clusters with non-convex shape (Beliakov & King 2006). To this end, we introduce Extreme Value Theory (EVT) to improve the cluster- ing ability of k-means. Particularly, the Euclidean space was transformed into a unique probability space denoted as extreme value spuce by EVT. We thus pro- pose a novel algorithm called Extreme Value k-means (EV k-means), including GEV k-means and GPD k-means. Besides, we also introduce the tricks to acceler- ate Euclidean distance computation in improving the computational efficiency of classical k- k-maass. Furthermore, our EV k-means is extended to online version, i.e., online Extreme Value k-means, in utilizing the Mini Batch k-means to cluster streaming data. Extensive experiments and online EV k-means on synthetic datasets and real datasets. Experimental re- sults show that our algorithms outperform competitors in most cases.
conducted to validate our EV k-means
INTRODUCTION
Clustering is fundamental and important task in the unsupervised learning (Jain 2010 Rui Xu & Wunsch 2005). It aims clustering data samples of high similarity into the same cluster. The most well-known clustering algorithm is the k-means, whose objective is to minimize the sum of squared distances to their closest centroids. k-means has been extensively studied in the literature, and some heuristics have been proposed to approximate it (Jain 2010 Dubes & Jain 1988). The most famous one is Lloyd's s algorithm (Lloyd] 1982).
The fi-mmaanns algorithm is widely used due to its simplicity, ease of use, geometric intuition (Bottesch cct al. 2016). Unfortunately, its bottleneck is that computational complexity reaches O(nkd) (Rui Xu & Wunsch 2005), since it requires computing the Euclidean distances between all samples and all centroids. The data is embedded in the Euclidean space (Stemmer & Kaplan 2018). which causes the failure on clustering non-convex clusters (Beliakov & King (206)). Even worse, h-means is highly sensitive to the initial centroids, which usually are randomly initialized. Thus, it is quite possible that the objective of k-means converges local minimum, which causes the instability of k-means, and is less desirable in practice. Despite a stable version k-means++ (Arthur & Vassilvitskii 2007) gives a more stable initialization, fundamentally it is still non-trivial extend k-means in clustering data samples of non-convex shape.
To solve these problems, this paper improves the clustering ability of k-means by measuring the similarity between samples and centroids by EVT (Coles et al. 2001). In particular, we consider the generalized extreme value (GEV) (Jenkinson 1955) distribution or generalized Pareto distribution (GPD) (Pickands III et al. 1975 DuMouchel] 1975) to transform the Euclidean space into proba- bility space defined as, extreme value space. GEV and GPD are employed to model the maximum distance and output the probability that distance is an extreme value, which indicates the similarity of a sample to a centroid. Further, we adopt the Block Maxima Method (BMM) (Gumbell 2012)) to choose the maximal distance for helping GEV fit the data. The Leaks-Over-Tie [Leadbetter] 1991) is utilized to model the excess of distance exceeding the threshold, and thus very useful in fitting the data for GPD.
(POT) method
Formally. since both GEV and GPD can measure the similarity of samples and centroids, they can be directly utilized in k-means, i.e, GEV k-means and GPD k-means, which uniformly

---

Under review as a conference paper at ICLR 2020
called Extreme Value k-means (EV k-mmans) algorithm. In contrast to k-means, EV k-means is a probability- bbsed clustering algorithm that clusters samples according to the probability output from GEV GPD. Furthermore, to accelerate the computation of Euclidean distance, We expand the samples and the centroids into two tensors of the same shape, and then accelerate with the high performance parallel computing of GPU.
For clustering steaming data, we propose online Extreme Value k-means based on Mini Batch k- means (Sculley) 2010). When fit the GEV distribution, we use mini batch data as a block. For the fitting of GPD, we dynamically update the threshold. The parameters of GEV or GPD are learned by stochastic gradient descent (SGD) (LeCun et al. 1998).
The main contributions are described as follows. (1) This paper utilizes EVT to improve k-means in addressing the problem of clustering data of non-convex shape. We thus propose the novel Extreme Value k-means, including GEV k-means and GPD k-means. A method for accelerating Euclidean distance computation has also been proposed to solve the bottleneck of k-means.
(2) Under the strong theoretical support provided by EVT, we use GEV and GPD to transform Euclidean space into extreme value space, and measure the similarity between samples and centroids. (3) Based on Mini Batch k-means, We propose online Extreme value k-means for clustering streaming data, which can learn the parameters of GEV and GPD online. We corroborate the effectiveness of EV k-means and online EV k-means by conducting experiments synthetic datasets and real datasets. Experimental results show that EV k-means and online EV k-means significantly outperform compared algorithms consistently across all experimented datasets.
2 RELATED WORKS
k-means and EVT have been extensively studied in the literature in many aspects (Jain 2010 Rui
Xu & Wunsch 2005 De Haan & Ferreira 2007). Previous work on k-means focused on the follow- ing aspects, such as determining the optimal k. initializing the centroids, and accelerating k-means. Bandyopadhyay & Maulik (002); Lin al. (2005); Van der Merwe & Engelbrecht| (2003); Omran ct al. (2005) propose to select the optimal &o value based on the genetic algorithm. Initializing the centroids is hot issue in k-means (Celebi et al. (2013). k-means++ (Arthur & Vassil 2007)
is the most popular initialization scheme. Katsavounidis et al. (1994); Khan & Ahhmad (2004); y; Red- mond & Heneghan (007) proposed density-based initial centroid selection method, that is, selecting the initial cluster center according to the density distribution of the samples. Recently, [Bachem et al.
(2016) propose using Markov chain Monte Carlo accelerate k-means++ sampling. There is also a lot of work focused on solving the computational complexity of k-means. [Hamerly (2010) argued that using triangle inequality can accelerate k-means. (Sinha (2018) showed that randomly sparse the original data matrix can significantly speed up the computation of Euclidean distance. EVT widely used many area, such as natural phenomena, finance, and traffic prediction. In recent years, EVT has many applications in the field of machine learning. However, far too little attention has been paid to the combination of k-means and EVT. Li et al. (2012) proposes using generalized extreme value distribution for feature learning based on k-means. However, our method is signifi- cant different from this method. First, they compute the squared distance from a point to the nearest centroid and form GEV regarding to each point, while compute the distance from centroid all data points and then fit the GEV or GPD regarding to each centroid. Second, their algorithm adds the likelihood function changes the objective function by fitting the GEV or GPD for each centroid and assign the data point to the one with the highest probabilities they belong Finally, this paper also presents GPD k-means and online Extreme Value k-means, which is not stated in this paper.
penalty term into the objective function of k-means, but our algorithm
PRELIMINARIES
3.1 k-MEANS CLUSTERING ALGORITHM
Denote X' = (x) ( Bz..... x.) C &d as the dataset and C = [C1, Oz...., C as a partition of X satisfying C, C,n. 0, j. Let θ {1,, u2,...., 1Ax)) with μ4; Rdd be the centroid of cluster
2

---

Under review as a conference paper at ICLR 2020
C₁ 1 1,2,.... .... k. that is, μ4 |cl Exec,
The sum squared error is defined
& J)C - Σ
a mill
(1)
#EC,
Eq. (T) indicates that the smaller J is, the higher degree of closeness between the samples and their centroids the clusters, so the similarity of the samples in the clusters higher. To find the global minimum of Eq. [ we need to compute all possible cluster partitions, so k-means is an NP-hard problem (Aloise et al., 2009). Lloyd's algorithm (Lloyd, 1982) uses greedy strategy to approxi- mate the Eq. (I) by iteratively optimizing between assigning cluster labels and updating centroids. Specifically, assigning cluster labels, cluster label is assigned to each sample according to the closest centroid. When the centroids are being updated, each centroid is updated to the mean of all samples in the cluster. These two steps loop iteratively until the centroids no longer change.
3.2 EXTREME VALUE THEORY
In this subsection, we first introduce the statistical aspects of sample maximum in Extreme Value Theory (EVT), which is a branch of statistics dealing with the stochastic behavior of extreme events found in the tail of probability distribution. Let X2... .., be sample of independent copy of X with distribution F. It is theoretically interesting to consider the asymptotic behavior of sample
maximum and upper order statistics. More specifically, denote M, maxigisn X; as the sample maximum, whose distribution is
Pr (Mn
Pr
< 2) (')),
R.
On the other hand, the upper order statistics of the sample is related to the survival function over threshold u, which is
Pr(X u u+
1 F(u+x)
P u) = Pr(X u) = 1 T-F((u)
x > 0.
(3)
EVT considers the non-degenerated limit when + in Eq. and 1 xx in Eq 3 by re-scaling the objects, which is presented as the conditions of the maximum domain of attraction for F.
Theorem 3.1 Fisher-Tippedt Theorem (Fisher & Tippett 1928)) distribution function F satis- fis the condition of a maximum domain attraction: if there exists constant & RR and sequences an > 0, Dyy n. E N such that
lim F (an + b.) =xp (- 1 Eor
The shape parameter & is called the extreme value index.
Theorem 3.1 motivates the Block Maxima Method (BMM) (Gumeel 2012): for the block size {1, ......... J. divide the sample into m Ln/s_ blocks length s. Since the data is independent, each block maxima has distribution f* and can be approximated by a three-parametric generalized extreme value distribution (GEV) GGEV (:: p. a. E) when the block size s is large enough and the number of blocks m is sufficient. The class of GEV distributions is defined
11+ I )
1/8
GGEY o. exp
(1+5
T 1
- 0.
(5)
We treat the case = 0 as the limit of g + 0. An equivalent representation of the maximum domain of attraction condition is follows:
Theorem 3.2 (Pickands- (Pickands-Balkema--d dalkema-de Haan Theorem (Balkema & De Haan 1974 A distribu-
tion function F satisfies the condition of maximum domain of attraction: if there exists a constant E E E and positive function (t) such that
- F(u + o(u)=)
lim
(1 (1+E0) (L)+ 1 Ex > 0.
(6)
F(u)
where x² denotes the right end-point of the support of F.
3

---

Under review as a conference paper at ICLR 2020
60
(a) Measuring similarity by GPD
(b) Isacontour of GPD k-means
(c) Surface of GPD k-means
The clustering results of GPD k-means in three isotropic Gaussian blobs. The color of the surface and contour in the figures represent the probability density of GPD. The closer to yellow, the greater the probability density. The closer to blue, the smaller probability density.
Figure I:
The upper order statistics of sample usually provides useful information about the tail of the distribution F. Then Theorem gives rise to an alternative peak-over peal-ovee-thrresholl (POT) approach (Pickands III et al., (975): given sufficient large threshold in Eq. 7 have that, for any X, u, its conditional distribution can be approximated by a two-parametric generalized Pareto distribution (GPD) GGPD(: E), which defined as
1/E
GGPD( a, =1 -1
F F>
Similarly, we treat the case of & = as the limit of { + O.
The POT approach focuses the excess over the threshold to fit the GPD and asymptotically characterize the tail features of the distribution, while the BMM only approximates the GEV distri- bution when is large enough. The BMM only uses a very small amount of dataset, and there may be cases where the submaximal value of one block is larger than the maximum value of the other block, which cannot be utilized. In contrast, POT method uses all data beyond the threshold fit the GPD, making full use of the extreme data. However, there is no winner in theory.
THE EXTREME VALUE k-MEANS ALGORITHM
4.1 MEASURING SIMILARITY EXTREME VALUE THEORY
Measuring similarity with Euclidean distance is the core step of k-means clustering. Similarly, for all clustering algorithms,, how to measure the distance (dissimilarity) or similarity between the samples and the centroids is critical issue (Rui Xu & Wunsch, 2005) it determines the performance of the algorithm. However, due to the properties of Euclidean distance, k-meaas fails for clustering non-convex clusters. Therefore, this paper proposes use the EVT transform the Euclidean space into probability space called the extreme value space. Fig. [(a) demonstrates measuring similarity GEV GPD. The Euclidean distances from 141 and μ4 to 2; much larger than the Euclidean distances from μr and to the most of surrounding samples, i.e. ||= - H1ll2 > |x; #1l12. Di C1 and ||=; - usll22 >> || p3 433122220 x; C3. Therefore, ||x, 11l12 and [x. Mall2 are maximums concerning ||.; p4 2, n. E Ci and ||>; p3||2, E C3 with different degree. We want distribution that can be used to model maximum distance and reflect the probability that distance is belong to cluster, which equivalent to the similarity between the sample and the centroid. Obviously, the EVT a good choice.
As described in Section 3.2. the BMM can be applied to fit the GEV distribution. In order to fit a GEV distribution for each cluster, we first compute the Euclidean distance d, between θ = {FI .2.... p4x and sample x, X. i... di ||2, H4 12,, i E 21.,,..., For the centroid μj, its distances to all samples is denoted by d, = {dif, d2j....,,dd. Then we divided them equally into blocks of size - (possibly the last block with sufficient
21 2.. k). k)-

---

Under review as a conference paper at ICLR 2020
observations can be discarded), and then the maximum value of each block is taken to obtain the block maximum sequence M M = {M, , Mm}
(8)
We use M to estimate the parameters of GEV distributions for cluster Cj. We assume the location parameter zero for the reason that the position of centroids change small in the later stage of clustering. The most commonly used estimating method, maximum likelihood estimation (MLE), implemented to estimate the two parameters of the GEV. The log likelihood function of GEV is derived from Eq. (
-1/E
1
Mi Jj
m
Mf
-m LGEV (Mgi,,)) - log(o,) (1
+
log
1 1+
1+ E
E + 0
5
oj
m
M
M2
(M -m
cxp
EJ =0
(9)
Mi 1 + E3 > when & # We get the estimated value on and E of oj and & by maximizing
LGEV.
Alternatively, we use the POT method model the excess of Euclidean distance dj exceeding threshold u, for centroid μej and fit the GPD. We first compute the excess that is defined as
-d= Uj. dj > Uj y² = {vl v.. v
(10)
where ky is the total number of observations greater than the threshold uy. Then we also implement MLE to estimate the parameters of the GPD. The log likelihood function of GPD can be derived from Eq. 7
R2
1 (GPD(V:o,,E)) -k log - logo - +1+
log(1 + S v)) E, + oj
E
(11)
La = -ký Eog oj 1
Σ V
E =0 0
2 > 0 when Ej 0 and 0 < 5// < Ej when & < 0. We get the estimated value o, and É, of o and E, by maximizing the LGPD. Finally, we can obtain the probability that x; belong to cluster C through the GEV and GPD:
P. = 1 - GGEV (diji مو Pj = 1 - GopD - U.;
(12)
4.2 OPTIMIZATION FOR K-MEANS WITH EVT
The traditional k-means clusters samples in view of the closeness to the centroids of clusters. As described in Section we can model the distribution classes of GEV and GPD to measure the sim- ilarity between the samples and the centroids. Thus we propose GEV k-means and GPD k-means, which are uniformly called the Extreme Value k-means (EV k-means) algorithm. In contrast to k-means, the proposed EV k-means is a probability- based clustering algorithm as it instead clusters samples by the probability output from GEV or GPD. The larger the block size and the threshold of BMM and POT, the smaller the deviation of MLF, but the larger the variance of MLE. Con- versely, the smaller the block size 8 and the threshold u, the larger the deviation of the MI.E, but the smaller the variance of the MLE. How to choose these two hyperparameters has not yet had stan- dard method, and is necessary to comprehensively balance the relationship between deviation and variance in practical applications. Therefore, adaptively. Specificallyy, we first set the hyperparameter a to indicate the percentage of excess for all samples. Then we sort d, from big small, and the u is set to the an-th of sorted dz.
set the block size by grid search and set threshold
The algorithm of GEV k-means has three steps: Given the dataset X. block size s and & initial centroids (obtained randomly using k-means++ algorithm). During the step of fitting GEV
5

---

Under review as a conference paper at ICLR 2020
distribution, we firstly use BMM to select the maximal sample data M for p.j Then, we estimate the GEV parameters og and E, by MLEE using Mj for μa So each cluster has its own independent GEV distribution. In the assigning labels step, each sample is assigned cluster label based on the maximum probability, i.e., X; = arg ma (1.2.... Psj. In the updating centroid step, each centroid is updated to the mean of all samples in the cluster, i.c., p4 = c. Exec, a. There three steps are iterated until the centroids no longer change.
The algorithm of GPD k-means is very similar to GEV k-means, except the fitting GPD distribution step. GPD me-maans use the POT to model the excess y of Euclidean distance d, exceeding threshold u and fit the GPD. Fig. [ and Fig. ] show clustering results of GPD k-means in three isotropic Gaussian blobs and show that the closer to the centroids, the greater the probability density.
4.3 SPEEDING UP
The main bottleneck of the k-means is the computation of Euclidean distances for the reason that the Euclidean distances between all samples and all centroids need to be computed. In naïve implemen- tation, double-layer nested for loop is often used to perform operations on the CPU, which is very slow. This paper proposes matrix X E represents samples consisting of d-dimensional samples, and matrix C' e R represents centroids consisting of k d-dimennional centroids. Secondly, insert a dimension between the two dimensions of matrix X and copy X along the new dimension to tensor X with shape of [n. kt d]. A similar operation for matrix C, adding a new dimension before the first dimension and copy C' along the new dimension tensor C with shape of [n,, k; d]. Finally, the Euclidean distances between all samples and all centroids are Di,; = ||X C E (1,2, n),j E {1, 2..,..... ........)) k} that can be accelerate with the advantages of GPU parallel computing. The overall Extreme Value k-means algorithm is illustrated in Algorithm
proposes an accelerated computation method to solve this bottleneck. Firstly, let
4.4 ONLINE LEARNING FOR CLUSTERING STREAMING DATA
In the era of Big Data, data is no longer stored in memory, but in the form of streams (Bugdary & Maymon 2 Therefore, clustering streaming data is significant and challenging problem. It is indispensable to design an Extreme Value k-menas algorithm that can learn online for clustering streaming data. This paper proposes the online Extreme Value k-means for clustering streaming data based on Mini Batch k-means (Sculley) 2010). When fit the GEV distribution, we use mini batch data as block and choose the maximum value for learning the parameters of GEV online. For the fitting of the GPD, the online EV k-means can dynamically update the threshold u and learn the parameters of GPD online.
The Online Extreme Value k-means algorithm is illustrated in Algorithm The algorithm randomly choose a mini batch contains samples from the data stream each iteration. On the first iteration, initializes the parameters of each GEV or GPD, and initializes centroid C' on the mini batch.
Then compute the Euclidean distances D using the accelerated computation method we proposed, update uy to fan-th of sorted h, and compute the maximum M and excess yj. Because the GEV and GPD parameters have not been updated at the first iteration, so Pij cannot be computed. Therefore, from the second iteration, the algorithm clusters the mini batch samples based on Mini Batch k- means. Finally, the negative log-likelihne ligeeiilloood function of all GEVs or GPDs is summed to obtain L.,. and the L, is minimized by SGD to update the parameters of GEV or GPD, which is equivalent to maximizing Σj=1 Loev (M3; oz Eg) and ΣØ= (
EXPERIMENTS AND RESULTS
5.1 EVALUATION METRICS
We evaluate the performance of the clustering algorithm by three widely used metrics, unsupervised clustering accuracy (ACC) (Cai et al. 2010). normalized mutual information (NMI) (Vinh et al., 2010), and adjusted rand index (ARI) (Vnnh et al. 2010). Note that the values of ACC and NMI are

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Extreme Value k-means
Input: samples X E R number of cluster k block size for GEV k-means, the percentage of excess a for GPD k-means
Output: clusters C Initialize centroid C' R repeat
C3 = =
Perform transformation on X and C' to obtain X and C, and then compute D |X C||2;
for j = 1,2,.... do
// G2V k-means
Obtain M from d., by BMM;
Estimate the áj & by MLE on M
// GPD k-means
Obtain Y from D.,, by POT;
Estimate the وة by MLE on y end
for
1, 1,2 ...,, do arg max (1.2.....) Payt
C2 = C22 U 02
end
for j = 1, ... do
,4 Teg Ezec,
end
until centroids no longer change;
return clusters C;
Algorithm 2: online Extreme Value k-means
Input: samples X E Bnxd number of cluster k. mini-batch size 6, the percentage of excess
Output: centroid C
Initialize U,
= [], =
for 1, 2................... n do M + choose b samples randomly from X;
ift = 1 then
Initialize centroid C E fxd and the parameters of GEVs or GPDs; end
Perform transformation on M and C' to obtain M and C, and compute the D ||M C C| for j do
// online GEV k-means
M (D,))
/ online GPD k-means
h.append( (D. ... DD., > ugl), Sort h from big to small and set uy = h[ttm]];
y DD. > uy] My:
end
if then
for
1.2...., do
A = arg Drgargmase (ermmajee(1... Stj;
N[A = N[A.] +
N A.A.i
C₂, = (1 - Cs.. + 7M.i
end
end
L. = - Dt LORV (M': oj 8,) 6/// // online GEV k-means
;,, Es) // online GPD k-means L, = --=-Vh En= LGrD(y' a
Compute the gradient L. and then update the parameters of the GEV or GPD;
end
return centroid C

---

Under review as a conference paper at ICLR 2020
Figure 2: Visualization of six synthetic datasets shows the result of Extreme Value k-means compared to k-means, k-means++, k-medoid, bidecting k-means and spectral clustering. The results from top to down are the clustering results on the datasets DI, D2, D3, D4, DS and D6, respectively. The nine algorithms from the first column to the ninth column are respectively k-means, k-means++, k-medoid, bidecting k-means, spectral clustering, GEV k-means (RM), GEV k-means (++), GPD k-means (RM), GPD k-means (++).
in the range of 0 to 1, with indicating the best clustering and 0 indicating the worst clustering. The value of ART is in range of -1 to 1, -1 indicates the worst clustering, and 1 indicates the best clustering.
5.2 SYNTHETIC DATASET DEMONSTRATION
We demonstrate our algorithm compared to other algorithms on six two-dimensional synthetic datasets. As illustrated in Fig. 2 there are the clustering results of the datasets D1, D2, D33, D4, D5 and D6 from top to down. DI consists of isotropic Gaussian clusters, each of which has 100 samples. D2 consists of 15 isotropic Gaussian clusters, each of which has 4000 samples. D3 consists of two 'C'-shaped clusters in the same direction, each of which has 250 samples. D4 con- sists of two clusters, each of which has 500 samples including a Gaussian blob and a 'C''shaped region. D5 consists of a Gaussian cluster having 500 samples and 'C' "C'-shaped cluster having 250 samples. The difference between DS and D4 is that the lower cluster in D5 has no "C'-shaped re- gion, and Gaussian blobs has larger variance. In D5,, the upper cluster has 500 samples and the lower cluster has 250 samples. The centroids of GEV k-means and GPD k-means can be initial- ized randomly or using k-means++. Let 'RM' and '++' denote randomly and using k-means++ initialize centroids, respectively. Therefore, there are nine algorithms in this experiment, k k-means, k-means++, k-medoid (Kaufman Rousseeuw 2009), bisecting k-means (Steinbach et al., 2000), spectral clustering (Ng et al., 2002), GEV k-means (RM), GEV k-means (++), GPD k- means (RM), GPD k-means (++), respectively. From the clustering results of the nine algorithms on six different synthetic datasets in Fig. 2 it can be seen that our four algorithms can successfully cluster con- vex and non-convex clusters, but the clustering results of k-means and k-means++ on non-convex but visibly well-separated clusters are completely unsuccessful. In addition, the clustering results k-medoid, bisecting k-means, spectral clustering on D3, D4, D5 is worse than our four algorithms.
5.3 REAL DATASET EXPERIMENT
We evaluated the proposed EV k-means on nine real datasets: iris (n = 150, d = 4, 3), breast cancer
(n 683, d 10, & 2), live disorders (n 145, d 5. k = 2), heart (n = 270, d 13, h: 2), diabctes (n 768, d 8, 2), glass (n 214, d 9, k 6), vehicle (n. 846, 18, k 4).
8

---

Under review as a conference paper at ICLR 2020
Table 1: Results of online Extreme Value k-means on streaming data
ACC
ARI
NMI
ACC
ARI
NMI
ACC
ARI
NMI
Algorithm
iris
breast cancer
liver disorders
k-means
0.8106
0.6053
0.6539
0.9095
0.6679
0.5507
0.5517
0.1233
0.1006
k-means++
0.7613
0.5721
0.6443
0.9105
0.6714
0.5550
0.7069
0.1447
0.1143
k-medoids
0.8040
0.6261
0.6869
0.8395
0.5250
0.4481
0.6214
0.0685
0.0446
bisecting k-means
0.8040
0.6261
0.6869
0.8395
0.5250
0.4481
0.6214
0.0685
0.0446
spectral clustering
0.8453
0.6323
0.6678
0.9367
0.7608
0.6628
0.7034
0.1383
0.1090
GEV k-means (RM)
0,6719
0.4401
0.2916
0.7512
0.2582
0.2632
0.6605
0,0711
0.5279
GEV k-means (++)
0.6610
0.4302
0.1939
0.7587
0.2773
0.2764
0.6619
0.0751
0.3024
GPD k-means (RM)
0.7960
0.5937
0.6637
0.8582
0.5278
0.4520
0.6582
0.099
0.0779
GPD k-maans (++)
0.8036
0.6007
0.6667
0.8604
0.5309
0.4543
0.6623
0.1017
0.0801
heart
diabetes
glass
k-means
0,8174
0.4011
0.3139
0.6591
0.0992
0.0608
0.4336
0,1517
0.2905
k-means++
0.7841
0.3481
0,2712
0.6473
0.0675
0.0422
0.4505
0.1641
0.3117
k-medoids
0.7741
0.3014
0.2443
0.6194
0.0584
0.0427
0.4126
0.1422
0,2705
bisecting k-means
0.7741
0.3014
0,2443
0.6194
0.0584
0.0427
0.4126
0.1422
0.2705
spectral clustering
0.8130
0.3895
0.3053
0.6471
0.0119
0.0034
0.4131
0.1795
0.3010
GEV k-means (RM)
0.6866
0.1906
0.6466
0.6586
0.0438
0.0171
0.4121
0.1166
0.1625
GEV k-means (++)
0.6990
0.2174
0.7719
0.6583
0.0475
0.0171
0,4222
0.1246
0.2277
GPD h-means (RM)
0.7865
0.3412
0.2866
0.6516
0.0874
0.0570
0.4313
0.1798
0.3075
GPD h- means (++)
0.7891
0.3464
0.2920
0.6595
0.0928
0.0608
0.4288
0.1783
0.3072
vehicle
MNIST
CIFARIO
k-means
0.3452
0.0605
0.0901
0.7359
0.7225
0.8350
0.6502
0.6911
0.8464
k-means++
0.3686
0.0803
0.1179
0.8354
0.8242
0,8175
0.9710
0.9740
0,9909
k-medoids
0,3642
0.0783
0.1135
0.7808
0.7422
0.8525
0.7239
0.6947
0.8948
bisecting k-means
0.3642
0.0783
0.1135
0.7808
0.7422
0.8525
0.7239
0.6947
0.8948
spectral clustering
0,4184
0.1188
0.1824
0.9854
0.9679
0.9566
0.7092
0.6442
0.8519
GEV k-means (RM)
0.3430
0.0582
0.1465
0.6228
0.5429
0.6337
0.5532
0.5028
0.9460
GEV k-means (++)
0.3362
0.0593
0.1375
0.6291
0.5584
0.6195
0.6954
0.6449
0.7409
GPD k-means (RM)
0.3452
0.0640
0.1078
0.8962
0.8739
0.9054
0.7816
0.7953
0.9248
GPD k-means (++)
0.3474
0.0657
0.1113
0.9296
0.9081
0.9227
0.9883
0.9887
0.9960
MNIST and CIFARIO. The first seven datasets available from LIBSVM Data website 0 MNIST is dataset comprises 60,000 training gray-scale images and 10,000 gray-scale images of handwritten digits 0 to 9. Each the training images is represented by an 84-dimensional vector obtained by LeNet (LeCun cet al. 1998). So the MNIST dataset we use has 60,000 samples with 84 features belonging to 10 classes, i.c., 60, 000,00044 d 84, = 10. CIFARIO is dataset containing 50,000 taining and 10,000 test color images with 32 32 pixels, grouped into 10 different classes of equal size, representing 10 different objects. Each of training images is represented by 512-dimensional vector extracted by a ResNet-18 (He et al. 2016). Therefore, the CIFARIO we use in the experiment has 50,000 samples with 512 features grouped in 10 classes, i.c., n = 50,0000000 000, d = 84, k 10.
We repeat each experiment 10 times with different random seeds and took the mean of the results of 10 times experiments the final result. In each of the experiments, all algorithms that initialize centroids randomly by using k-means++ start from same initial centroids. The results EV k-means on real datasets are shown Tab. [ As shown in Tab. | our proposed EV k-mcans on some datasets are comparable to other algorithms, and outperform other algorithms on MNIST and CIFARIO.
5.4 STREAMING DATASET EXPERIMENT
We compare online EV k-means with k-means, k-means++, Mini Batch k-means (RM) and Mini Batch k- means (++) MNIST and 10 As illustrated in Tah. 2 the values of the three metrics of online EV k-meaans are slightly smaller than the values of EVV k-means. However, the values of the three metrics of Mini Batch k-means are much smaller than the values k-means. For example, the values of the three metrics of Mini Batch k-means on MNIST are 10%, 17% 8% smaller than the values of k-means. However, the values
http://wwww...cccmddddd/illlilnd qjiin//issymtooosslaaaeett
https//wwww.scc.n...cmmmm tw/

---

Under review as a conference paper at ICLR 2020
Table 2: Results of online Extreme Value k-means on streaming data
ACC
ARI
NMI
ACC
ARI
NMI
Algorithm
MNIST
CIFARIO
k-means
0.8276
0.8164
0.8867
0.7168
0.7153
0,8966
k-means++
0.8583
0.8361
0.8961
1.0000
1.0000
1.0000
Mini Batch k-means (RM)
0.7465
0.6759
0.8167
0.6091
0.5137
0.8355
Mini Batch k-means (++)
0.8244
0.8018
0.8798
1.0000
1.0000
1.0000
GEV k-means (RM)
0.9751
0.9454
0,9344
1. 1,0000
1. 1.0000
0,9460
GEV k-means (++)
0.9758
0.9469
0,9370
1.0000
1.0000
1.0000
GPD k-means (RM)
0.9792
0.9543
0,9418
0.8940
0.8916
0.9644
GPD k-means (+++)
0.9794
0.9547
0,9420
1.0000
1.0000
1.0000
online GEV k-means (RM)
0,9375
0.8705
0.8832
0.8505
0.8511
0.9407
online GEV k-means (++)
0.8478
0.8255
0,8920
1.0000
1 1.0000
1.0000
online GPD k-means (RM)
0.9530
0.8987
0,8921
0.8568
0.8627
0,9400
online GPD k-means (+++
0.9669
0.9286
0.9156
1.0000
1.0000
1,0000
of the three metries of online GVE k-means (RM) on MNIST are 4%, 8%, 5% smaller than the values GVE k-means (RM).
Ww.
8.50
8.0
3.00
075
2008
4000
871
(a) Analysis of speed
(b) Analysis of
(c) Analysis of &
Figure 3: On dataset of Gaussian clusters with 5000 samples, we analyze acceleration method, block size and the percentage of excess a.
5.5 ABLATION STUDY
Fig. ((a] "for loop' means that the Fuclidean distance is computed on CPU using a double-layer nested for loop, and 'Tensor GPU' indicates the use of the acceleration method we proposed. As shown in Fig. (3a] the computational time using the for loop' method increases linearly with the increase of nkdd, Compared to 'oor loop', using the 'Tensor GPU" method significantly accelerate the computation of Euclidean distance for the computational time is almost unchanged with the increase of nıdd. (36) shows that as the block size increases, ACC, ARI, and NMI both show sharp drop first, then gradually risc, and finally remain steady. This confirms the Theorem 3.1, the block size should be large enough, then the distribution function F can approximate the GEV distribution. In the application, this paper suggests that the block size >> z. As shown (())). as a increases, ACC, ARI, and NMI show steady trend. In order meet the conditions of Theorem 3.2, should be relatively small to get large enough u. In the experiment of this paper, we set a to O.I.
CONCLUSIONS
This paper introduces Extreme Value Theory into k-means to measure similarity by transforming the Euclidean space into extreme value space. Based the strong theoretical support provided by EVT, this paper proposes Extreme Value k-means, novel algorithm for the task of k-means clustering. In view of the bottleneck of k-means, this paper proposes practical method to accelerate the computation of Euclidean distance. As for streaming data clustering, this paper presents online Extreme Value k-means that can perform clustering streaming data. We evaluate the performance of our algorithm synthetic datasets and real datasets. The results show that algorithm outperform k-means and k-means++ on all datasets.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. Np-hardness of euclidcan sum-of-squares clustering. Machine learning, 75(2):245-248, 2009.
David Arthur and Sergei Vassilvitskii. k-means++: advantages careful seeding. Proceedings of the eighteenth anmual ACM-SIAM symposium on Discrete algorithms, pp. 1027-1035. Society for Industrial and Applied Mathematics, 2007.
Olivier Bachem, Mario Lucic, Hamed Hassani, and Andreas Krause. Fast and provably good seedings for k-means. In Advances in Neural Information Processing Systems, pp. 55 63, 2016.
August A Balkema and Laurens De Haan. Residual life time great age. The Annals of probability, pp- 792-804, 1974.
Sanghamitra Bandyopadhyay and Ujjwal Maulik. Genetic clustering for automatic evolution of clusters and application image classification. Pattern recognition, 35(6):1197-122 2002.
Gleb Beliakov and Matthew King. Density based fuzzy e-means clustering of non-convex patterns. European Journal of Operational Research, 1733))717-728, 2006.
Thomas Bottesch, Thomas Bühler, and Markus Kächele. Speeding up k-means by approximating euclidean distances via block vectors. In International Conference on Machine Learning, pp. 2578 2586, 2016.
Shlomo Bugdary Shay Maymon. Online clustering by penalized weighted gmm. arXiv preprint arXiv:1902.022. 021.900...22..2222 2019.
Deng Cai, Xiaofei He, and Jiawei Han. Locally consistent concept factorization for document clustering. IEEE Transactions on Knowledge and Data Engineering, 23(6):902 913, 2010.
M Emre Celchi, Hassan A Kingravi, and Patricio A Vela. A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert systems with applications,
2013.
Stuart Coles, Joanna Bawa, Lesley Trenner, and Pat Dorazio. An introduction to statistical modeling of extreme values, volume 208. Springer, 2001.
Laurens De Haan and Ana Ferreira. Extreme value theory: introduction. Springer Science & Business Media, 2007.
Richard C Dubes and Anil K Jain. Algorithms for clustering data, 1988.
William H DuMouchel. Stable distributions in statistical inference: 2. information from stably distributed samples. Journal of the American Statistical Association, 30635,) 1975.
Ronald Aylmer Fisher and Leonard Henry Caleb Tippett. Limiting forms of the frequency distribution of the largest smallest member sample. Mathematical Proceedings of Cambridge Philosophical Society, volume 24, pp. 190. Cambridge University Press, 1928.
Emil Julius Gumbel. Statistics of extremes. Courier Corporation, 2012.
Greg Hamerly. Making k-means even faster. Proceedings of the 2010 SIAM international conference on data mining, pp. 130-140. SIAM, 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Anil K Jain, Data clustering: 50 years beyond k-means. Pattern recognition letters, 31 (1)):5511666, 2010.
Arthur Jenkinson. The frequency distribution of the annual maximum (or minimum) values of meteorological clements. Quarterly Journal of the Royal Meteorological Society, 81(348):158 171, 1955.
Toannis Katsavounidis, C-C Jay Kuo, and Zhen Zhang. A new initialization technique for generalized lloyd iteration. IEFF Signal processing letters, 1(10): 144-146, 1994.
Leonard Kaufman and Peter Rousseeuw. Finding groups in data: an introduction to cluster analysis, volume 344, John Wiley & Sons, 2009.
Shehroz S Khan and Amir Ahmad. Cluster center initialization algorithm for k-means clustering. Pattern recognition letters, 25(11):1293-1302 2004.

---

Under review as a conference paper at ICLR 2020
Malcolm Leadbetter. On basis for "peaks over threshold modeling. Statistics & Probability Letters, 12(4): 357-362, 1991.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-bard based learning applied to document recognition. Proceedings of IEEE, 86(11):2278 222222322, 1998.
Zeyu Li, Oriol Vinyals, Harlyn Baker, and Ruzena Bajesy. Feature learning using generalized extreme value distribution based k-means clustering. In Proceedings the 2 International Conference on Pattern Recog- nition (ICPR2012), pp. 1548-151. IEEE, 2012.
Hwei-Jen Lin, Fu-Was Wen Yang, and Yang- Kao. An efficient ga-based clustering technique. Tamkang Journal of science and Engineering, 8(2): 11,, 2005.
Stuart Lloyd. Least squares quantization in pem. JEEE transactions on information theory, 28(2):129 137, 1982.
Andrew Y Ng. Michael Jordan, and Yair Weiss. spectral clustering: Analysis and an algorithm. Advances neural information processing systems, pp. 849-856, 2002.
Mahamed Omran, Andries Petrus Engelbrecht, and Ayed Salman. Particle swarm optimization method image clustering. International Journal of Pattern Recognition and Artificial Intelligence, 19(03):97--321, 2005.
James Pickands III et al. Statistical inference using extreme order statistics. the Anmals of Statistics, 3(1): 119-1311 1975.
Stephen J Redmond and Conor Heneghan. A method for initialising the k-means clustering algorithm using kd-trees. Pattern recognition letters, 28(8):965 973, 2007.
Rui Xu and D. Wunsch. Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16(3): 645-67 678, May 2005. doi: 10. 2,.1199N
David Sculley. Web-scale k-means clustering. In Proceedings of the 19th international conference on World wide web, pp. 1177 1177-1178. ACM, 2010.
Kaushik Sinha. K-means clustering using random matrix sparsification. International Conference on Ma- chine Learning, pp. 4691-4699, 2018
Michael Steinbach, George Karypis, Vipin Kumar, et al. A comparison of document clustering techniques. In KDD workshop on text mining, volume 400, pp. 525-526. Boston, 2000.
Uri Stemmer and Haim Kaplan. Differentially private k-means with constant multiplicative error. In Advances in Neural Information Processing Systems, pp. 5431-5441, 2018.
DW Van der Merwe and Andries Petrus Engelhrecht. Data clustering using particle swarm optimization. In The 2003 Congress on Evolutionary Computation, 2003. 73C'03., volume 1, pp. 215-220. IEEE, 2003.
Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11 (0ct):2837-2854, 2010.
12


Reviews:
[{"review_id": "SJldIO6ntS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper claims to improve the “clustering ability” of k-means by measuring the similarity between samples and centroids by something known as Extreme Value Theory (EVT). The paper in its current form is extremely difficult to follow. I highlight some of the difficulty: \n\n1. The notion of “clustering ability” of k-means is not well defined in the paper. So, in general there does not seem to be a clear theoretical objective that is being optimised by the suggested algorithm.\n\n2. The algorithm itself is not clear. For example, the block maximum sequence M^j = {M_1, …, M_m} is not clearly understood. What is threshold u_j? \n\nGiven the above, I am unable to evaluate the contribution of the paper. It will help the paper if the authors clearly formalise what is it that they are trying to achieve with their algorithm. After this, there needs to be a much more clear description of the algorithm. I think the above will also help decide whether section 3.2 on Extreme Value Theory is really required for the discussion. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJglh4GrcB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper utilizes EVT to improve k-means, which aims to address the problem of clustering data of nonconvex shape. GEV k-means and GPD k-means are proposed as two kind of  Extreme Value k-means. A method for accelerating Euclidean distance computation has also been proposed to solve the bottleneck of k-means.\nThe proposed idea is novel and the paper is well written. Experimental reaultts are also good to me.\nThere are two concerns which I need the authors to address:\n1. Since the authors claim that they propose to speed up the computation of the Euclidean distances in k-means. However, there is no time cost comparison in the experiments.\n2. Some other variants of k-means should be added for experimental comparison.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlI6ipjqB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers extending the k-means algorithm to allow for finding clusters with non-convex shapes. Particularly, it uses an existing theoretical framework (Extreme Value Theory) to maps a Euclidean space into what it calls the extreme value space, and proposes two Extreme Value k-means algorithms: GEV k-means and GPD k-means. It then provides some empirical results demonstrating their approach.\n\nI have some concerns with the paper's claimed novelties, its empirical evaluation, and its overall presentation, and thus am initially recommending a weak reject. To raise my score, the following concerns should be clarified or addressed:\n\n1) An initial concern is with the claimed novelty of the work. A paper by Li et al. (2012) also uses Extreme Value Theory (EVT) to improve k-means using the Generalized Extreme Value (GEV) distribution. Their algorithm is also called GEV k-means, and is based on an observation that the squared distance from a point to its closest center follows the GEV distribution for large numbers of clusters. From this, it doesn't appear to be the first time that EVT has been used to improve k-means, and it would be good for the authors to contrast their methods in the context of existing work in this direction.\n\n2) Is it generally applicable to measure similarity based on the probability of being an extreme value, compared with classic metrics like Euclidean distance? In other words, would it always be better to do this or are there clear counterexamples where you would not want to measure similarity based on this?\n\n3) In the empirical evaluation, it is said that 10 independent runs were performed, and the maximum result of the 10 runs was reported. I believe it would be more informative to report the mean, or expected performance of the algorithm, as well as some statistic about the mean to ensure any differences are significant. It is not clear whether this maximum can be expected or reproduced, and can negatively be interpreted as the algorithm having considerably higher variability- in other words, it could be the case that the minimum of the 10 runs for the EV methods was also lower than the minimums of classic k-means. Were any statistical tests done to ensure that the larger maximum over the runs was not by chance?\n\n4) The paper has many frequent, but minor, grammatical and spelling errors. As such, it is possible to get the overall message (and didn't strongly impact my score), but it does detract from the paper's overall presentation and quality.\n\n-----\n\nPost-rebuttal:\n\nThank you for your clarifications regarding 1) and 2), and for now reporting the mean. However, there still does not seem to be any statistical significance testing. Further, after reporting the mean and comparing with more methods, the method doesn't seem to perform as well as previously reported. This makes the concern in 2) more prevalent- if the method is not generally applicable, and are likely to help on a problem-specific basis, it would be more informative to characterize *when* one might expect the method to perform better, and support this with empirical results. Based on this, I am maintaining my score, but think the work is interesting and encourage the authors to improve on the paper!", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1xAsmc3FH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose an improved k-means clustering algorithm by using a new similarity measurement method based on extreme value theory. Extreme value theory can better capture the data distribution and thus better handle non-convex situations. Experiments on extensive datasets are conducted to show the effectiveness of the proposed method.\n\nThe paper is well written and easy to understand. However there are some concerns:\n1. There are many clustering methods based on geodesic distance of data points (manifold learning), which are supposed to be better at capturing the non-convex data distribution. Comparisons are suggested.\n2. The datasets used in the experiments are relatively small (n<=50000, and k<=10), what about more clusters?\n3. The results of different methods may be unstable to initialization, more tests and average results are suggested.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper explores extending k-means to allow to clusters with non-convex shapes.

This paper introduces a new algorithm, relying on empirical comparisons to illustrate its contribution. The main issue with the paper is that the empirical claims do not support that the new method is indeed better. The paper claims the new method outperforms the competitors in most cases. However, the original submission reported median performance and when the authors provided mean performance and additional baseline methods (at the reviewers' request) there appear to be little evidence to support the claim. In addition there are no measures of significance provided. The authors provided no commentary to help the reviewers understand the new results. There might be some important speed gains at the cost of final performance, but on the evidence provided we are not able to evaluate the cost in final performance.

The text changes size after section 5.3 and is 9% smaller. Watch out for this formatting issue in future submissions


Decision: Reject