Exponentially Consistent Nonparametric Clustering of Data Streams with Composite Distributions

This paper focuses on nonparametric clustering of data streams generated from unknown distributions. Existing results on exponentially consistent nonparametric clustering assume that the maximum intra-cluster distance (d <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</inf> ) is smaller than the minimum inter-cluster distance (d <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</inf> ). We show that exponential consistency can be achieved for single linkage-based (SLINK) clustering under a less strict assumption, d <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">I</inf> < d <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</inf> , where d <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">I</inf> is the maximum intra-cluster nearest neighbour distance. Note that d <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">I</inf> < d <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</inf> in general. Then, we propose a sequential clustering algorithm based on SLINK. Simulation results show that the sequential SLINK algorithm requires fewer expected number of samples than the fixed-sample size SLINK algorithm for the same probability of error. We also identify examples where k-medoids clustering is unable to find the true clusters, but SLINK is exponentially consistent.