TY - GEN
T1 - Exponentially Consistent K-Means Clustering Algorithm Based on Kolmogrov-Smirnov Test
AU - Wang, Tiexing
AU - Bucci, Donald J.
AU - Liang, Yingbin
AU - Chen, Biao
AU - Varshney, Pramod K.
N1 - Funding Information:
This material is based upon work supported in part by the Defense Advanced Research Projects Agency under Contract No. HR0011-16-C-0135 and by the Dynamic Data Driven Applications Systems (DDDAS) program of AFOSR under grant number FA9550-16-1-0077.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/9/10
Y1 - 2018/9/10
N2 - 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.
AB - 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.
KW - Clustering
KW - Exponential consistency
KW - K-means algorithm
KW - Kolmogorov-Smirnov distance
KW - Probability of error
UR - http://www.scopus.com/inward/record.url?scp=85048524455&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048524455&partnerID=8YFLogxK
U2 - 10.1109/ICASSP.2018.8461730
DO - 10.1109/ICASSP.2018.8461730
M3 - Conference contribution
AN - SCOPUS:85048524455
SN - 9781538646588
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 2296
EP - 2300
BT - 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018
Y2 - 15 April 2018 through 20 April 2018
ER -