NSC: A New Progressive Sampling Algorithm

Abstract. As the size of the databases increases, machine learning algorithms face more demanding requirements for efficiency and accuracy. Rather than analyzing all the data, an alternative approach is to use only a small subset trying to achieve competitive results with less resources. Progressive sampling follows this approach, starting with a small sample of data and increasing the size progressively until the accuracy (or other performance measure) cannot be improved. Progressive sampling aims for equivalent accuracies obtained with all the data but with significantly less resources. This paper introduces a new progressive sampling algorithm called NSC which: (i) defines an initial data set with a simple to evaluate measure and close to the sample size where the accuracy no longer improves, (ii) proposes a sampling schedule which is more aggressive than arithmetic sampling but more conservative than the standard geometric sampling with a geometric factor of 2, and (iii) introduces a termination criterion based on an adaptive local linear regression algorithm and on the complexity of the machine learning algorithm used to generate models. It is shown experimentally that NSC consistently outperforms both arithmetic and geometric sampling on several databases.