# One dimensional clustering (again!)

I know this question has been asked a lot, but my problem is a lot more specific than those questions, and the solutions provided don't seem to apply.

Here's the problem: I have a set of values (reals) and I want to know if there are "obvious" clusters. If there are, I want to know the values in them (to derive various other statistics).

I've seen lots of suggestions on here, mostly boiling down to either Jenk (not applicable because I don't know if there are any "real" clusters, let alone how many) or kernel density estimation. The latter is, in principle, promising, but a bit overkill, especially regarding computation time.

The problem I face is that this A) needs to run on several thousand sets of several thousand data points each in a reasonable time frame on a standard desktop computer, and B) it needs to run on low end computers for many more data points completely transparently (i.e. the application may not noticably freeze, so running in much less than a second - threading is not an option) frequently. This is being implemented in a slow language (imagine javascript on a browser without a current-gen engine on a netbook).

Complexity of kernel density estimation ($O(n^2)$ as I found - just using random sample points is not going to work due to the expected nature of the data) leads me to believe that this approach will fail at least problem B.

The advantage that I have is that I can be very generous in what a "cluster" is. While the data may contain outliers, the clusters I'm looking for are going to be very "obvious", to a human, anyway. One example would be a data set of 50 values with a standard deviation of 4 around 50, 40 values with a standard deviation of 50 around 1000, a couple outliers more or less randomly distributed between those and then a handful values with a low deviation around 10000. It doesn't matter whether the outliers are assigned to a cluster or put into their own, the major information I need is whether such clusters exist and their basic statistical properties (which would then remove the outliers).

I'm currently using an approach for problem A that's just a very simple forward difference estimation using some heuristics on the differences between "expected" clusters. The problem is that this is not going to scale at all to the number of values to be analyzed, and finding the parameters is not going to be globally possible since the data sets are very different (and in fact, my current method might already miss some "clustered" data sets).

So, I guess I could cut this short: Is there a very fast way to find clusters in data sets if it sufficient to ignore any "borderline" cases as just not clustered?

• A couple of clarifying questions: 1) Is your "standard desktop computer" multicore; 2) can you use cloud (i.e., AWS) to parallelize the processing; 3) do you have freedom of what language/environment to use (R, Python, etc.)? – Aleksandr Blekh Feb 22 '15 at 3:02
• KDE may be O(n^2) in the most general case. But if you are willing to use finite kernels instead of Gaussian, it should be only marginally more expensive than sorting your data (e.g. using a sliding window for KDE on dorted data). Have you tried it? How long does it take? Theoretical complexity results are useless in practise, in particular if you know your data is always in the low thousand points. – Anony-Mousse Feb 22 '15 at 8:34
• +1 to @Anony-Mousse. Do not write KDE out. In addition to that, for 1-D data you might want to consider fitting a mixture distribution. First run might be "slow" but afterwards you can use the past fits to initialize your algorithm. Finally, how many data and what time of time-constraints are you looking at? – usεr11852 Feb 22 '15 at 11:57
• @usεr11852 distribution fitting approaches are much harder when the number of clusters isn't known beforehand, and may change over time. – Anony-Mousse Feb 22 '15 at 13:26
• @AleksandrBlekh 1) yes, 2) no, 3) no - one implementation will be in Java (as is the current one), client is undecided, but will be a given. – Desiato Feb 23 '15 at 0:29