3
$\begingroup$

I have one-dimensional data. I want to find possible natural cutting points (strong slopes) within the data.

For instance, if the data is

1, 2, 3, 2, 2, 3, 4, 2, 80, 90, 80, 85, 91

there would be a cutting point between values (1-4) and (80-91)

I mapped a histogram which gives me an idea, but I'm curious whether a better method exists (especially for large amounts of data, 100k+).

If the distribution of the values in the example above was a function, it would have the highest slope right before 80.

If it helps, I am using R

PS: My data are not necessarily normally distributed, nor are they ordered.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You describe two techniques: one of them relies on the order in which you listed the data and the other (the histogram) does not. Is the ordering meaningful or not? $\endgroup$ – whuber♦ Jul 29 '15 at 16:03
  • 1
    $\begingroup$ Thank you for pointing this out. In this case, the order is NOT relevant $\endgroup$ – rmuc8 Jul 29 '15 at 17:43
  • $\begingroup$ Perhaps the "cutting point" in the title is bit misleading as OP stated the order does not matter. This is clustering problem. $\endgroup$ – Vladislavs Dovgalecs Jul 29 '15 at 21:25
  • $\begingroup$ @xeon yest and no, I have an impression that it is a question on hard rather then fuzzy clustering and so, "cutting point" refers to hard cluster boundaries. $\endgroup$ – Tim♦ Jul 30 '15 at 7:08
4
$\begingroup$

There are several algorithms designed for one-dimensional clustering. Among most widely known are Jenks natural breaks, method designed Fisher (1958) and K-means algorithm. Basically, all the three algorithms are very similar since they aim at minimizing within-cluster sum of squares.

All the (and other) methods are implemented in classInt library for R. Using Fisher method or K-means seems to work well given the limited data sample you provided (see below). Since the algorithms are quite simple, it should not be a problem to run them on larger amounts of data.

library(classInt)

x <- c(1, 2, 3, 2, 2, 3, 4, 2, 80, 90, 80, 85, 91)

classIntervals(x, style = "fisher", n = 2)
## style: fisher
##   one of 7 possible partitions of this variable into 2 classes
##  [1,42) [42,91] 
##       8       5 
classIntervals(x, style = "kmeans", n = 2)
## style: kmeans
##   one of 7 possible partitions of this variable into 2 classes
##  [1,42) [42,91] 
##       8       5

The problematic part of the methods is that, like with any of the clustering approaches, they do not provide you any fool-proof method on deciding about the number of clusters to look for. There are rules of thumb and algorithms (e.g. here, here, or here) that in some cases make the choice simpler, but they are far from perfect and the final choice is always somehow subjective. In many cases the choice is simpler with model-based clustering, where there are available methods for model comparison, however those methods output clustering solutions with fuzzy, rather than "cutting point", boundaries (you could check mixtools package for examples).

Fisher, W. D. (1958). On grouping for maximum homogeneity. Journal of the American Statistical Association, 53, 789–798.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the links and for the effort to make an example. I appreciate this a lot. In this example, I am wondering how this approach can lead me to the conclusion that there is a huge gap between 4 and 80? Do you know of any heuristic to determine a reasonable number of clusters (like distortion with k-means)? $\endgroup$ – rmuc8 Jul 29 '15 at 18:16
  • $\begingroup$ @rmuc8 classIntervals uses by default automatic algorithm that chooses number of clusters using nclass.Sturges that is normally used to choose number of bins for histogram, you could possibly use other such algorithms for this purpose. However like with almost every clustering algorithm the choice always is somehow subjective. Model-based clustering approaches such as FMM's provide criteria for assessing model fit so you could use one of those if needed (stats.stackexchange.com/questions/130805/…). $\endgroup$ – Tim♦ Jul 29 '15 at 19:09
2
$\begingroup$

You can maybe use something from change point detection on time-series data. This could get you started if you are using R.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Please note that this assumes the order matters, but the OP has clarified it does not. $\endgroup$ – whuber♦ Jul 29 '15 at 18:04
  • 1
    $\begingroup$ Ok, then this is a clustering problem. $\endgroup$ – Gumeo Jul 29 '15 at 18:18
  • 1
    $\begingroup$ True. However, I think the answer might be still relevant for others, so please keep it. $\endgroup$ – rmuc8 Jul 29 '15 at 18:18
  • $\begingroup$ Ok, good point! $\endgroup$ – Gumeo Jul 30 '15 at 10:41
  • 1
    $\begingroup$ A related option is to use a Savitzky-Golay filter. That means fitting an approximate curve to the data, and allows you to calculate the derivatives. A change in sign of the 2nd derivative indicates a cutting point. This may be overkill however... $\endgroup$ – dcorney Jul 30 '15 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.