Exponentially Consistent Nonparametric Linkage-Based Clustering of Data Sequences

In this paper, we consider nonparametric clustering of M independent and identically distributed (i.i.d.) data sequences generated from em unknown distributions. The distributions of the M data sequences belong to K underlying distribution clusters. Existing results on exponentially consistent nonparametric clustering algorithms, like single linkage-based (SLINK) clustering and k-medoids distribution clustering, assume that the maximum intra-cluster distance (dL) is smaller than the minimum inter-cluster distance (dH). First, in the fixed sample size (FSS) setting, we show that exponential consistency can be achieved for SLINK clustering under a less strict assumption, dI < dH, where dI is the maximum distance between any two sub-clusters of a cluster that partition the cluster. Note that dI < dL in general. Thus, our results show that SLINK is exponentially consistent for a larger class of problems than previously known. In our simulations, we also identify examples where k-medoids clustering is unable to find the true clusters, but SLINK is exponentially consistent. Then, we propose a sequential clustering algorithm, named SLINK-SEQ, based on SLINK and prove that it is also exponentially consistent. Simulation results show that the SLINK-SEQ algorithm requires fewer expected number of samples than the FSS SLINK algorithm for the same probability of error.