# 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