Estimating generalized Dunn's cluster validity indices for big data

© 2018 IEEE. Dunn's internal cluster validity index and its generalizations assess partition quality. For partitions of n samples of p-dimensional feature vector data, all but two of the generalized Dunn's indices (GDIs) have quadratic time complexity O(pn 2 ), so computation is untenable for very large values of n. In this paper, we present two methods for approximating GDIs based on Maximin (MM) Sampling. MM sampling identifies a skeleton of the full partition that usually contains some of the boundary points in each cluster which are used to compute GDIs. We compare our algorithms with a support vector machine based boundary extraction method and a random sampling based estimation method. Our experiments on four real and synthetic datasets show that computing approximations to (three) GDIs with the MM skeleton is both computationally tractable and reliably accurate.