0
$\begingroup$

We have a set X of N elements. We want to get a new set X' having a size M < N.

Choose a first element x from X and put it in X'
for each element x in (X - X')
  Let x' the element from X' which is the closest to x (that is x' = argmin distance(x, x') for all x' in X')
  d = distance(x, x')
  if ( uniform_random([0,1]) < d / f )
     add x to X'

How can I choose the value f such that the size of the set X' at the end will be for instance the half of the size of X (that is, M approximates or equals N/2). I suppose that I should choose f such that the probability d / f equals 1/2 (or approximates 1/2 for most values of d), but how to do that ?

Additional details (that are not necesarily usefull for this question): the elements are actually vectors, and the distance between two vectors is the euclidean distance.

Note that d is not a constant (while f is a constant that I want to fix). d depends on the distance between each element x and its closest element x', so d is not always the same.

Suppose that the order in which we test the elements x is always random. For any set X, if we choose the value of f relatively small then we will get a relatively hight number of elements in the final set X', if we choose the value of f relatively big we will get a relatively small number of elements in the final set X'. If I experimentally vary the value of f many times I can always (for any set X) find a value of f for which the final number of elements in X' approaches N/2. So experimentally I can find a good value for f if I test many times which different values of f, but I want to determine it heuristically (not by testing many times and varying f).

EDIT: By the way, the only one method which seems to give an acceptable results is: let mean_d the mean distance of each x to its nearest x'. We put f = 2mean_d, thus the probability d/f = d/(2mean_d) usually approximate 1/2 if the most of distances d are not far from mean_d. We also put f = (2mean_d)+d' where d' depends on how many distances are higher than mean_d, or f = (2mean_d)-d' where d' depends on how many distances are less than mean_d. Does this make sense ? Do you think it can be improved ?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ This question is lacking several important details. Is X a subset of some sort of structured space, or is it entirely abstract? What is distance? What's the distance between elements a, 6 and "cat"? $\endgroup$
    – Kerrek SB
    Commented Sep 17, 2012 at 18:59
  • $\begingroup$ @KerrekSB we don't care about this details, just suppose you have a function distance(x1,x2) that tells you how x1 is far from x2. Well since you ask for this details, the elements are actually vectors, and the distance between two vectors is the euclidean distance ... $\endgroup$
    – user995434
    Commented Sep 17, 2012 at 19:04
  • $\begingroup$ Should the second line be "for each x in (X - X')? $\endgroup$
    – Kerrek SB
    Commented Sep 17, 2012 at 19:07
  • $\begingroup$ @KerrekSB yes you are right (corrected). $\endgroup$
    – user995434
    Commented Sep 17, 2012 at 19:08
  • $\begingroup$ Well, you should at least say that a notion of distance exists, and that it separates points... $\endgroup$
    – Kerrek SB
    Commented Sep 17, 2012 at 19:09

3 Answers 3

Reset to default
1
$\begingroup$

OK, another answer :)

Size of the set X' clearly depends on the distribution of points, choice of starting points, and random chance.

If the points are always chosen from the same distribution, I'd try drawing |X'| as a function of f and |X|. To do that, I'd just do some monte-carlo simulations.

Also notice that f is a linear function of mean distance between points.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you please explain more this solution ? How do you represent |X'| = Function(f, |X|) what is this Function ? How do you apply monte-carlo simulation on that ? More precisions would be appreciated. $\endgroup$
    – user995434
    Commented Sep 17, 2012 at 20:41
  • $\begingroup$ Something like: Generate set X. calculate it's size, |X|. Calculate mean distance between points, M. choose f' between 0 and 2 (randomly). take f=M*f' . Simulate Your procedure for generating set X'. calculate |X'|=size of X'. Repeat lots and lots of times. Figure out how all these numbers relate. $\endgroup$
    – maniek
    Commented Sep 17, 2012 at 21:52
  • $\begingroup$ You are not using particle filters (monte-carlo simulations) in your description, it's just an experimental determination of f (by trying many times with many values). $\endgroup$
    – user995434
    Commented Sep 18, 2012 at 8:18
0
$\begingroup$

The value of f depends on the set X aty hand, and the order in which You test the elements.

For example, if the elements are points on a line, then testing the elements in order will give You more elements in the final set than testing them in a random order.

In short, it is not possible to choose f that works for any set X.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Suppose that the order in which we test the elements is always random. For any set X, if we choose the value of f relatively small then we will get a relatively hight number of elements in the final set X', if we choose the value of f relatively big we will get a relatively small number of elements in the final set X'. If I experimentally vary the value of f many times I can always (for any set X) get a final number of elements in X' that approaches N/2, and for this value of f the overwhelming majority of the probability values ​​are around 1/2. It thus is possible to choose f heuristically. $\endgroup$
    – user995434
    Commented Sep 17, 2012 at 19:43
  • $\begingroup$ @user995434: If all the elements in X are at a huge distance, no two nearer than, say, 1000000, then a "small value of f" will mean that you never pick any elements. $\endgroup$
    – Kerrek SB
    Commented Sep 17, 2012 at 19:48
  • $\begingroup$ @KerrekSB Here I was talking in a relative way, according to the order of magnitude f the considered distances ... if the value of f is relatively small the probability d/f will always be hight, and each element x will be automatically added to X'. Now if you increase f less elements will be added to X' (because the probability d/f will probably be smaller), and so on ... $\endgroup$
    – user995434
    Commented Sep 17, 2012 at 20:06
0
$\begingroup$

This isn't an answer, but just a thought about your setup.

The outcome seems to depend on the choice of the initial element. For example, if one point was really far out, and all the other points clustered together. If we start with the far point, then the initial d is huge. Thus we can only ever add new points to X' if f is also huge. But if f is huge, then we can never add any subsequent points, since d will henceforth be small.

Perhaps you could describe the larger goal of this algorithm before jumping at a specific implementation?

Another example: Suppose X is the set consisting of the vertices of the standard simplex in n-dimensional Euclidean space, i.e. all vertex pairs have distance 1. Surely f = 2 would be a good solution. Now add to X one really far away point. By the above logic, f = 2 is still a good choice if we start with any of the original points, but if we start with the far point, it won't work. So no choice of f works uniformly for all choices of initial point.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I don't ask for a specific implementation. I want to find a method that allow to determine a value for f which allow the probability to be often (frequently) 1/2. Something like: if we take the elements x in a random order and we compute the mean distance of x to its closest x', then we choose for instance f = mean_d * 2 ... this is just an example which is not necessarily good. $\endgroup$
    – user995434
    Commented Sep 17, 2012 at 19:49
  • $\begingroup$ @user995434: I meant that you have already started us off on something that you believe to be a useful approach. I was suggesting that you instead describe your larger goal in a bigger-picture style. $\endgroup$
    – Kerrek SB
    Commented Sep 17, 2012 at 19:52
  • $\begingroup$ Describing the larger goal is very complicated and not useful for this question to be resolved. I just asked my question in a simple way, and it perfectly reflects what I need. Here I just want to find a method that allow to determine a value for f which allow the probability to be often (frequently) 1/2. Something like: if we take the elements x in a random order and we compute the mean distance of x to its closest x', then we choose for instance f = mean_d * 2 ... this is just an example which is not necessarily good. $\endgroup$
    – user995434
    Commented Sep 17, 2012 at 19:56
  • $\begingroup$ @user995434: I added another thought on why I think your problem has no solution... $\endgroup$
    – Kerrek SB
    Commented Sep 17, 2012 at 20:00
  • $\begingroup$ It is sure that no choice of f works uniformly for all choices of initial point, but there is always some choices which works better than the others. The problem do have a solution (it is verified experimentally). And by the way the datasets of general use that I work with (set X) do not represent special cases like the ones you are mentioning, there is always a value of f which works pretty good for what I want to do (this was verified experimentally ...) $\endgroup$
    – user995434
    Commented Sep 17, 2012 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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