In clustering algorithm selection, we are given a massive dataset and must
efficiently select which clustering algorithm to use. We study this problem in
a semi-supervised setting, with an unknown ground-truth clustering that we can
only access through expensive oracle queries. Ideally, the clustering
algorithm's output will be structurally close to the ground truth. We approach
this problem by introducing a notion of size generalization for clustering
algorithm accuracy. We identify conditions under which we can (1) subsample the
massive clustering instance, (2) evaluate a set of candidate algorithms on the
smaller instance, and (3) guarantee that the algorithm with the best accuracy
on the small instance will have the best accuracy on the original big instance.
We provide theoretical size generalization guarantees for three classic
clustering algorithms: single-linkage, k-means++, and (a smoothed variant of)
Gonzalez's k-centers heuristic. We validate our theoretical analysis with
empirical results, observing that on real-world clustering instances, we can
use a subsample of as little as 5% of the data to identify which algorithm is
best on the full dataset.

在半监督环境中，通过引入聚类算法准确性的大小泛化概念，我们可以通过对较小的实例集进行评估，并保证在原始大型实例上具有最好准确性的算法也在小实例上具有最好准确性。