Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I have a list of numbers I need to group by similarity (differences being 1 between each). For example, in a list of [198, 202, 207, 218, 219, 220], 190 would be put into a list, 202 would be put into another list, 207, into a list, and 218 219 220 into another list.

share|improve this question
1  
Do you just want to put all numbers that are 1 unit apart into the same cluster? Are you just looking for code / how that can be done in R? –  gung Jul 10 at 20:45

2 Answers 2

up vote 3 down vote accepted

Although some clustering algorithms will do this, there's a simpler way: sort the input, create a binary vector indicating whether each neighboring pair is dissimilar or not, prefix that with a 1 for the initial value of the input, and compute its cumulative sum. This creates a new group identifier each time a dissimilar pair is seen.

x <- c(198, 202, 207, 218, 219, 220, 220)
y <- sort(x)
g <- cumsum(c(1, abs(y[-length(y)] - y[-1]) > 1))
by(y, g, identity)

The last line isn't really needed in R: g already holds the essential information. I stuck it there only because a list was requested. Here's what g looks like in the example:

> rbind(g, y)
  [,1] [,2] [,3] [,4] [,5] [,6] [,7]
g    1    2    3    4    4    4    4
y  198  202  207  218  219  220  220

The groups are 1 --> (198), 2 --> (202), 3 --> (207), 4 --> (218, 219, 220, 220).

If you don't want duplicates to appear, clean the input first using unique.

On my system this code groups an input of four million integers in one second. Most of that is spent in the sorting step.

The same algorithm is readily applied on other platforms such as Stata, Matlab, Mathematica, Python, etc.

share|improve this answer

This can be accomplished with hierarchical clustering using the hclust function in R. Here's some example code. The cutree function allows you to specify the distance (height) at which the tree should be cut and returns the cluster for each data point.

numbers_to_cluster <- c(0:10, 20:30, 40:50)
distances_between_numbers <- dist(x = numbers_to_cluster, method = "euclidean")
hierarchical_clustering <- hclust(d = distances_between_numbers, method = "single")
clusters <- cutree(tree = hierarchical_clustering, h = 1)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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