I have the following data:

      type    distance
0      X      12572
1      X      11229
2      Y      14144
3      A      15781
4      A      15486
5      B      461
6      X      328
7      X      23
8      X      50
9      A      45
10     A      231
11     A      10779
12     X      11433
...      .....

type refers to the data points category. distance is the distance between each data point. That is, the difference between X index 0 and X index 1 is 12572, the difference between the second and third datapoint is 11229, etc.

One can think of this set of datapoints as being along one dimension. The identity (i.e. type) of the datapoint is irrelevant to this problem. I am interested somehow inferring the "clusters" of data points which occurs when datapoints are spaced closely together. In this case, it looks clear that the datapoints from index 5-11 consist of one grouping.

One-dimensional clustering algorithms come to mind. However, there is a natural structure to this dataset; if the distances are less than 10,000, normally there's a cluster. Simply binning by hand might be more important.

Is there a method for this problem based in probabilistic inference? Either there could be a way to infer the "natural" clustering within a given dataset (though that's ill-defined) or perhaps use part of the dataset as a training set?

  • $\begingroup$ The twist in your question is the existence of this prior criterion of 10,000. However, by rephrasing it as "any gap of distance larger than 10,000 must separate the clusters," you can perform a preliminary partition of the data by identifying all such gaps and then separately cluster the data within each component of that partition using the techniques described in the duplicate. $\endgroup$ – whuber May 30 '17 at 13:47
  • $\begingroup$ @whuber "any gap of distance larger than 10,000 must separate the clusters" This is somewhat tautological/circular I feel, and is equivalent to binning. If there are distances less than 10,000, then this is a cluster of points. Once partitioning the data to identify all such gaps as you suggest, isn't the problem then solved? $\endgroup$ – ShanZhengYang May 30 '17 at 13:50
  • $\begingroup$ It's also not clear to me how k-means helps here. k=2? That is, there are two groupings to this data, and then I should mark the identity of each column as either in cluster 1 or cluster 2? $\endgroup$ – ShanZhengYang May 30 '17 at 13:53
  • $\begingroup$ The problem, as you seem to have expressed it, is not solved after splitting across all gaps of 10000 or larger: it remains to cluster the data that have not been split. For instance, in the series 1, 2, 3, 20000, 20001, 20002, 29000, 38000, 38001, you would initially split it into just two series 1,2,3 and 20000, ..., 38001, because there is only one gap larger than 10000. It remains to cluster each of those subseries. There's nothing circular about this approach. But if this is not what you intended to describe, then please feel free to change your post to make the question clearer. $\endgroup$ – whuber May 30 '17 at 14:16
  • $\begingroup$ @whuber I remain confused---I think there's something unclear above. Can you explain what you mean by "subseries", i.e. "It remains to cluster each of those subseries."? In the actual dataset, distances are either around ~10-15K or not. There are no 20K, 38001, etc. $\endgroup$ – ShanZhengYang May 30 '17 at 14:50