0
$\begingroup$

Given a finite set of points in $\mathbb{R}^n$, all at finite distances from each other I would like to remove a certain proportion of points, in such a way as to penalise clustering. For example for $n=1$, given points $\{1, 2, 10, 20\}$ I would want to remove $2$ because that would maximize the distances between the remaining points.

Is there an efficient algorithm/implementation that does this already? My approach would be to:

  1. Work out distances between all points
  2. Sum these distances, and normalize by the number of points squared (since the number of distances grows as the square of the number of points)
  3. Select one point that increases the metric by the greatest amount
  4. repeat

The aim here is to reduce the number of alternatives, whilst trying to preserve diversity. e.g. each point could be a set of instructions on how to run an experiment, but if only a finite number of experiments can be tried, I would like to cover the widest range of options possible.

Improve this question
$\endgroup$
5
  • $\begingroup$ I don't think you can preserve diversity by selectively deleting points. You would preserve diversity by using some type of randomized removal. As far as removing the clustering properties, you could use a fast algorithm, k-means, and then go back and find the most representative point for each cluster, and remove it. Or randomly remove 2 of the top 5 representative points. Or, remove one point from each cluster, then re-cluster and repeat until you have achieved the target "proportion." Natural diversity is destroyed, but the data will have a higher entropy and will be harder to cluster. $\endgroup$
    – Kyle
    Dec 5, 2020 at 23:35
  • $\begingroup$ @kyle thanks. Perhaps I am using the some standard terminology in a wrong way. The point is given an excessively large number of options to try (each point) and a finite number of trials, I would like to choose trials as diverse as possible, i.e. 1 is different from 10, but on the scale of 1-to-10, the difference between 1 and 2 is not important. Using K-means is attractive, but I am not sure how many clusters there may be. There may-be no clusters, or many clusters. I'll try it. Thanks $\endgroup$
    – Cryo
    Dec 5, 2020 at 23:43
  • 1
    $\begingroup$ A huge set of approximate but effective solutions is possible by first clustering the points and then retaining just one point in each cluster (such as the one nearest the cluster center). $\endgroup$
    – whuber ♦
    Dec 6, 2020 at 2:26
  • $\begingroup$ It looks like you really wants to increase uniformity. Use some exchange algorithm. $\endgroup$
    – kjetil b halvorsen ♦
    Jan 12, 2021 at 16:57
  • $\begingroup$ Poisson disc resampling, right? $\endgroup$
    – EngrStudent
    Jan 12, 2021 at 16:58

1 Answer 1

Reset to default
0
$\begingroup$

What you have indicated is a kind of exchange algorithm. Search (this site and the www) for Fedorov exchange algorithm. Since you have used the tag , maybe your points represents trials in some regression experiment. If so, you can give all your points as candidate points to some implementation of an exchange algorithm (or some other algorithm for optimal design), and then search for an optimal design with the wanted number of runs.

If this is some other kind of experimental design, please provide details. For implementations in R see this task view.

Improve this answer
$\endgroup$

Your Answer

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

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