Exponentially Consistent K-Means Clustering Algorithm Based on Kolmogrov-Smirnov Test

Tiexing Wang, Donald J. Bucci, Yingbin Liang, Biao Chen, Pramod K. Varshney

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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.

Original languageEnglish (US)
Title of host publication2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2296-2300
Number of pages5
Volume2018-April
ISBN (Print)9781538646588
DOIs
StatePublished - Sep 10 2018
Event2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Calgary, Canada
Duration: Apr 15 2018Apr 20 2018

Other

Other2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018
CountryCanada
CityCalgary
Period4/15/184/20/18

Keywords

  • Clustering
  • Exponential consistency
  • K-means algorithm
  • Kolmogorov-Smirnov distance
  • Probability of error

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Exponentially Consistent K-Means Clustering Algorithm Based on Kolmogrov-Smirnov Test'. Together they form a unique fingerprint.

  • Cite this

    Wang, T., Bucci, D. J., Liang, Y., Chen, B., & Varshney, P. K. (2018). Exponentially Consistent K-Means Clustering Algorithm Based on Kolmogrov-Smirnov Test. In 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings (Vol. 2018-April, pp. 2296-2300). [8461730] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2018.8461730