Clustering under composite generative models

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

doi:10.1109/CISS.2018.8362256

Clustering under composite generative models

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

Department of Electrical Engineering & Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

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 language	English (US)
Title of host publication	2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1-6
Number of pages	6
ISBN (Electronic)	9781538605790
DOIs	https://doi.org/10.1109/CISS.2018.8362256
State	Published - May 21 2018
Event	52nd Annual Conference on Information Sciences and Systems, CISS 2018 - Princeton, United States Duration: Mar 21 2018 → Mar 23 2018

Other

Other	52nd Annual Conference on Information Sciences and Systems, CISS 2018
Country/Territory	United States
City	Princeton
Period	3/21/18 → 3/23/18

Keywords

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

ASJC Scopus subject areas

Artificial Intelligence
Computer Networks and Communications
Information Systems

Access to Document

10.1109/CISS.2018.8362256

Cite this

Wang, T, Bucci, DJ, Liang, Y, Chen, B & Varshney, PK 2018, Clustering under composite generative models. in 2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018. Institute of Electrical and Electronics Engineers Inc., pp. 1-6, 52nd Annual Conference on Information Sciences and Systems, CISS 2018, Princeton, United States, 3/21/18. https://doi.org/10.1109/CISS.2018.8362256

@inproceedings{2e72578efe834540ac1f33687a5e9e77,

title = "Clustering under composite generative models",

abstract = "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.",

keywords = "composite distributions, K-means algorithm, Kolmogorov-Smirnov distance, probability of error",

author = "Tiexing Wang and Bucci, {Donald J.} and Yingbin Liang and Biao Chen and Varshney, {Pramod K.}",

year = "2018",

month = may,

day = "21",

doi = "10.1109/CISS.2018.8362256",

language = "English (US)",

pages = "1--6",

booktitle = "2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "52nd Annual Conference on Information Sciences and Systems, CISS 2018 ; Conference date: 21-03-2018 Through 23-03-2018",

}

TY - GEN

T1 - Clustering under composite generative models

AU - Wang, Tiexing

AU - Bucci, Donald J.

AU - Liang, Yingbin

AU - Chen, Biao

AU - Varshney, Pramod K.

PY - 2018/5/21

Y1 - 2018/5/21

N2 - 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.

AB - 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.

KW - composite distributions

KW - K-means algorithm

KW - Kolmogorov-Smirnov distance

KW - probability of error

UR - http://www.scopus.com/inward/record.url?scp=85048555402&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048555402&partnerID=8YFLogxK

U2 - 10.1109/CISS.2018.8362256

DO - 10.1109/CISS.2018.8362256

M3 - Conference contribution

AN - SCOPUS:85048555402

SP - 1

EP - 6

BT - 2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 52nd Annual Conference on Information Sciences and Systems, CISS 2018

Y2 - 21 March 2018 through 23 March 2018

ER -

Clustering under composite generative models

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this