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 samples beyond Gaussian distribution, particularly, the clusters with non-convex shape (Beliakov & King, 2006). To this end, we introduce Extreme Value Theory (EVT) to improve the clustering ability of k-means. Particularly, the Euclidean space was transformed into a unique 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. Besides, 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 outperform competitors in most cases.
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.
I 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:
1) 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.
2) 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?
3) 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?
4) 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.
-----
Post-rebuttal:
Thank 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!