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.
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?