Clustering under composite generative models

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

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

2 Scopus citations


This paper studies clustering of data samples generated from composite distributions using the Kolmogorov-Smirnov (KS) based K-means algorithm. All data sequences are assumed to be generated from unknown continuous distributions. The maximum intra-cluster KS distance of each distribution cluster is assumed to be smaller than the minimum inter-cluster KS distance of different clusters. The analysis of convergence and upper bounds on the error probability are provided for both cases with known and unknown number of clusters. Furthermore, it is shown that the probability of error decays exponentially as the number of samples in each data sequence goes to infinity, and the error exponent is only a function of the difference of the inter-cluster and intra-cluster KS distances. The analysis is validated by simulation results.

Original languageEnglish (US)
Title of host publication2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781538605790
StatePublished - May 21 2018
Event52nd Annual Conference on Information Sciences and Systems, CISS 2018 - Princeton, United States
Duration: Mar 21 2018Mar 23 2018


Other52nd Annual Conference on Information Sciences and Systems, CISS 2018
Country/TerritoryUnited States


  • composite distributions
  • K-means algorithm
  • Kolmogorov-Smirnov distance
  • probability of error

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Information Systems


Dive into the research topics of 'Clustering under composite generative models'. Together they form a unique fingerprint.

Cite this