How to reduce number of points for clustering

Question

Description

I have to find number of clusters for 1D data. All clusters are assumed to have a gaussian distribution (so there is a big number of same points). I have a robust "agglomerative clustering + EM"-based algorithm which is able to find cluster centers.

Problem

The number of clusters varies (in different data sets) from $1$ to $10$, but number of points in my 1D datasets varies from hundreds to hundreds of thousands. And that is the problem, because my algorithm is running pretty slow for high number of points.

Questions

Is there any simple method how to reduce number of points? The accuracy of cluster centers does not matter for me, I just only want to have fast detection.

Is it OK to select each k-th point and apply clustering algorithm on that selection. Or do I need something else like counting number of same points and leave out some percent of same points?

Answer 1

You don't need to reduce your data set. Instead, you probably need to improve your implementation.

One-dimensional data should not be handled with the average clustering techniques. Because these techniques were designed for multivariate data.

One-dimensional data is special. It can be sorted consistently in $O(n \log n)$, and then you can use various algorithms in $O(n)$ time. A naive implementation of e.g. hierarchical ("agglomerative") clustering is $O(n^3)$ and that will of course kill you with large data. By any means avoid distance matrixes. They kill scalability.

1. Sort your data

2. Improve your algorithm to exploit this.

You may also want to look at classic statistical approaches for this problem, such as kernel density estimation. Consider using local density maxima as clusters.