A Farthest First Traversal based Sampling Algorithm for k-clustering

摘要

The farthest-first-traversal (fft) algorithm originally was used by Rosenkrantz et al. in an analysis of heuristics for the traveling salesman problem. This algorithm has been extensively studied for several sampling techniques. In this work, we present a modification of ProTraS algorithm given by Ros and Guillaume, which is also based on the fft algorithm, for sampling datasets for both k-means and k-median clustering algorithms. Unlike ProTraS, proposed algorithm takes the size of samples as an input. The algorithm is implemented in the Spark platform and tested for benchmark datasets. We also estimate the algorithm by comparing with the adaptive sampling and lightweight coreset algorithms, using the adjust Rand index.