Approximating Dunn's cluster validity indices for partitions of big data

Abstract

Dunn's internal cluster validity index is used to assess partition quality and subsequently identify a "best" crisp partition of n objects. Computing Dunn's index (DI) for partitions of n p-dimensional feature vector data has quadratic time complexity O(pn 2 ), so its computation is impractical for very large values of n. This note presents six methods for approximating DI. Four methods are based on Maximin sampling, which identifies a skeleton of the full partition that contains some boundary points in each cluster. Two additional methods are presented that estimate boundary points associated with unsupervised training of one class support vector machines. Numerical examples compare approxi..