Approximating Dunn’s Cluster Validity Indices for Partitions of Big Data
邓恩指数用于评估聚类质量，但计算复杂度为O(pn²)，不适合大数据。本文提出六种近似方法，其中基于增量邻域最大最小骨架的方法在七个数据集上表现准确且可行。
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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ), 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 approximations to DI based on all six methods. Four experiments on seven real and synthetic data sets support our assertion that computing approximations to DI with an incremental, neighborhood-based Maximin skeleton is both tractable and reliably accurate.