Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say you have a set of numbers S and you want to obtain subsets of $S$, $s_1,s_2,\ldots, s_i$, where $i < N$.

Is there a particular operation that will group the numbers that are "close to each other"?

I will give an example to clarify the question:

Let's say you have a set $S$ which contains $\{1.4, 2, 2.5, 2.7, 14, 16, 49, 57, 58\}$

And let's say that you can have maximum of $N=4$ subsets.

So, you might end up with a result that looks like this:

$s_1 = \{1.4, 2, 2.5, 2.7\}$
$s_2 = \{14, 16\}$
$s_3 = \{49\}$
$s_4 = \{57, 58\}$

I am looking for either the name what such a problem would be called (which I can then use to research and write an algorithm). If you can provide a simple solution, even better.

Thank you for any help with this.

share|improve this question
    
set-theory is not the tag. The algorithm will depend on what you mean by "close". –  Aryabhata Oct 5 '10 at 14:59
3  
Sounds like "clustering"... –  J. M. Oct 5 '10 at 15:05
1  
And big thank you to jug for providing the answer. That is a very elegant solution. It does not require any recursion or special analysis. I think that's exactly what I'm looking for. –  chaimp Oct 5 '10 at 15:17
3  
Jug's answer makes sense, but it's not "the" answer. In some applications it would not be optimal. For instance, let S have 100 values in the interval [0,1], 100 values in [2,3], 100 values in [4,5], 100 values in [6,7], and one value of 10. If the objective is to minimize the sums of squares to the centers of the clusters, 10 must be clustered with the values in [6,7] even though the gap is largest. It merely turns out in the particular example of the OP, the clustering is so strong that any remotely reasonable algorithm will work. –  whuber Oct 5 '10 at 15:57
1  
@whuber: I agree. That's why I posted it just as a comment. It's maybe "the" most trivial approach (which might be anyway enough for jeffp). @jeffp: Even if you won't implement the methods in the answer of whuber, I'd recommend to accept his answer (or whatever better answer will be posted), as it provides a better solution in general. –  j.p. Oct 5 '10 at 16:13

2 Answers 2

up vote 8 down vote accepted

There are many solutions to this problem extant, each rediscovered many times. Search "statistical clustering methods" or "cluster analysis." A particularly nice one for your problem is called "K-means". This was rediscovered by cartographers (!) where it is called "Jenks' method" (and is worth mentioning because it's used by some popular mapping software, so perhaps more people have heard of this than of any other method). The idea behind K-means is to minimize the population-weighted sum of variances of the subsets.

BTW, the challenge in most clustering algorithms lies in determining the number of clusters; usually that needs to be specified (as $N = 4$ in this example) or at least hinted at by the user. For instance, there always exists a minimum K-means solution: partition $S$ into singletons. If you require $i < n$, merge the two nearest neighbors but leave all the other singletons as they are: the sum of variances is then just one-quarter the square of the smallest difference among the $x_i$.

share|improve this answer
1  
+1 "Clustering" is the keyword –  leonbloy Oct 5 '10 at 15:44
1  
I remembered "clustering", but forgot "k-means". Thanks! –  J. M. Oct 5 '10 at 15:55

There is a somewhat related operation, condensation, in the theory of linear orderings. For example, you can take a linear ordering and identify any two elements $x,y$ which are connected by some finite chain, i.e. there are elements $x = v_1,\ldots,v_n = y$ such that $v_1 < \cdots < v_n$ and there are no elements 'in between', i.e. no $z$ such that $v_i < z < v_{i+1}$. This will compress all copies of $\mathbb{Z}$ and $\mathbb{N}$ (or its opposite) to a single point.

This particular condensation can be used to (de)construct all countable linear orders, if I remember correctly. There are also some other condensations, take a look at Rosenstein's Linear orderings.

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.