Exponentially Consistent K-Means Clustering Algorithm Based on Kolmogrov-Smirnov Test
Tiexing Wang, Donald J. Bucci, Yingbin Liang, Biao Chen, Pramod K. Varshney · 2018
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.