# Reducing sample size

I have a large dataset (around $10^6$ samples) and an algorithm that will surely choke on that much data.

Suppose that I have removed duplicates and near-duplicates. What are the well-known techniques for reducing sample size without losing too much of the information possibly encoded in the initial dataset?

I thought about using some clustering algorithm (which scales well with respect to number of clusters, possibly BIRCH) and use the resulting clusters to find $N$ nearest points to cluster centroid. However this feels somehow wrong.

• instead of selecting N nearest points around K cluster centroids, I would set the number of centroids to the desired sample size (K=N) and select only the centroids. also Birch doesn't scale well to high-dimensional data. if you have a lot of features you could try k-means with mini batches. – oW_ Dec 27 '16 at 20:17

## 2 Answers

One method would be to take many subsets of your dataset, i.e. bootstrapping, build your models, perform cross-validation and calculate the average performance. This is a good explanation of how the amount of data affects the model outcomes: https://stackoverflow.com/questions/25665017/does-the-dataset-size-influence-a-machine-learning-algorithm

Play around with the size of your subsets until you start getting stable results.

It depends: Some algorithms would benefit from near duplicates (such as kNN), while some of them use the outliers of clusters to build their rules on (such as SVM).

In my experience it is very important that you understand how your data is structured and what concept you are actually trying to learn, before you settle on a downsampling method.

I recently ran into a problem in which I wanted to predict a certain behavior in time, but local dependecies (spacially as in x,y) kept throwing the algorithm in local optima. Downsampling maximizing distibution over x,y actually increased performance of almost all trained models.