Exponentially Consistent K-Means Clustering Algorithm Based on Kolmogrov-Smirnov Test
Tiexing Wang, Donald J. Bucci, Yingbin Liang, Biao Chen, Pramod K. Varshney
Abstract
This paper studies clustering using a Kolmogorov-Smirnov based K-means algorithm. All data sequences are assumed to be generated by unknown continuous distributions. The pairwise KS distances of the distributions are assumed to be lower bounded by a certain positive constant. The convergence analysis of the proposed algorithms and upper bounds on the error probability are provided for both known and unknown number of clusters. More importantly, it is shown that the probability of error decays exponentially as the sample size of each data sequence goes to infinity, and the error exponent is only a function of the pairwise KS distances of the distributions. the analysis is validated by simulation results.
BibTeX
@inproceedings{icassp2018_exponentiallycon,
title = {Exponentially Consistent K-Means Clustering Algorithm Based on Kolmogrov-Smirnov Test},
author = {Tiexing Wang and Donald J. Bucci and Yingbin Liang and Biao Chen and Pramod K. Varshney},
booktitle = {ICASSP 2018},
year = {2018}
}