Estimating Generalized Dunn's Cluster Validity Indices for Big Data

Abstract

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(pn2), 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 experiment..