In response to the need for learning tools tuned to big data analytics, the
present paper introduces a framework for efficient clustering of huge sets of
(possibly high-dimensional) data. Building on random sampling and consensus
(RANSAC) ideas pursued earlier in a different (computer vision) context for
robust regression, a suite of novel dimensionality and set-reduction algorithms
is developed. The advocated sketch-and-validate (SkeVa) family includes two
algorithms that rely on K-means clustering per iteration on reduced number of
dimensions and/or feature vectors: The first operates in a batch fashion, while
the second sequential one offers computational efficiency and suitability with
streaming modes of operation. For clustering even nonlinearly separable
vectors, the SkeVa family offers also a member based on user-selected kernel
functions. Further trading off performance for reduced complexity, a fourth
member of the SkeVa family is based on a divergence criterion for selecting
proper minimal subsets of feature variables and vectors, thus bypassing the
need for K-means clustering per iteration. Extensive numerical tests on
synthetic and real data sets highlight the potential of the proposed
algorithms, and demonstrate their competitive performance relative to
state-of-the-art random projection alternatives.

本文提出了一种用于大数据分析的高效聚类框架 ——SkeVa family，它包括基于 k 均值聚类和核函数聚类的算法，并使用随机采样和一致性 (RANSAC) 思想进行降维和集合简化。此外还引入了一种基于离散度准则的算法。通过在大规模数据集上的实验，发现这些算法与最先进的随机投影方案相比，具有非常良好的竞争性能。