4
$\begingroup$

I have a set S of real numbers, and I would like to create a new set R with exactly n real numbers (not necessarily from the set) that represent it best.

What I mean by best?

Well, I have query that asks for given point what is the closest point from S to that point, and when I ask same thing for set R I would like to have best fit to the real answers.

To be specific, how do I minimize the Hausdoff distance between S and R?

I hope I've been clear enough in what i want. I've heard of mathoverflow, so I said to myself why wouldn't I ask for help there.

Thank you in advance.

(Edited in light of the comments below.)

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ What is a one-dimensional set? $\endgroup$
    – Qiaochu Yuan
    Commented Feb 19, 2010 at 16:48
  • $\begingroup$ What is a point? What is close? $\endgroup$
    – Jonas Meyer
    Commented Feb 19, 2010 at 16:50
  • 1
    $\begingroup$ I am guessing that the OP's sets are subsets of the real numbers (one-dimensional) equipped with the standard distance function. To me, the only thing which is really unclear (and I am not a statistician) is what "best fit" means. What exactly are you trying to minimize? $\endgroup$
    – Pete L. Clark
    Commented Feb 19, 2010 at 16:57
  • $\begingroup$ Yes, by one dimensional set I've meant subset of the real numbers. And yes, standard distance function. I am trying to minimize average error e.g. if my answer on set R is x and answer on set S would be y, I am trying to minimize average value of |x - y| $\endgroup$
    – Nemanja
    Commented Feb 19, 2010 at 17:01
  • 3
    $\begingroup$ I am guessing that we are talking about sets of real numbers here, but that is not very important. Look at the definition of Hausdorff distance (en.wikipedia.org/wiki/Hausdorff_distance). If $h$ is the Hausdorff distance between $R$ and $S$, then for any $x$, $|\operatorname{dist}(x,R)-\operatorname{dist}(x,S)|\le h$, and $h$ is the smallest such number. So the question should perhaps be about minimizing Hausdorff distance. $\endgroup$
    – Harald Hanche-Olsen
    Commented Feb 19, 2010 at 17:02

3 Answers 3

Reset to default
5
$\begingroup$

This is the $k$-center problem (or in your notation, the $n$-center problem). you're given a set $S$ of points, and you want to find a set $R$ of $n$ points such that the set of balls of radius $r$ around each point in $R$ cover all of $S$, and $r$ is minimized.

Your metric space is the line, so this problem is relatively easy to solve. Here's a two-step approach: First, "guess" the optimal solution r (ie. pick some value of r). Now go from left to right, assigning centers greedily, which is to say, as far away from the previously placed center as possible, while covering all points. If you use up $n$ points before covering all of $S$, your guess was wrong, and you need to restart with a larger value of r. Else, you're done.

Now of course $r$ is a real number, but there are only discretely many "guesses", since the optimal r must be such that there are two points at distance exactly $r$ from a center (otherwise r is not optimal). so the total set of choices of r is merely the set constructed from measuring the pairwise distances and halving them.

All of this assumes you're in algorithms-land, which means that you have reasonable ways of representing points and comparing them.

p.s this algorithm is well known (not original).

Improve this answer
$\endgroup$
7
  • $\begingroup$ great. thank you. so by doing this i would get my error to be maximum r. But, if i don't restrict myself to choosing centers from the given set, i could get r/2, right? I could just chose from every ball (a0 - r, a0 + r), a0 + r/2 for my center and then I would get error of maximum r/2. $\endgroup$
    – Nemanja
    Commented Feb 20, 2010 at 4:46
  • $\begingroup$ The above method doesn't limit you to centers chosen from the input set. The greedy sweep just finds the furthest location on the real line. $\endgroup$
    – Suresh Venkat
    Commented Feb 20, 2010 at 6:30
  • $\begingroup$ In general though it is true that by picking from the input set, you are no worse than a factor 2 away from the optimal radius (via the triangle inequality) $\endgroup$
    – Suresh Venkat
    Commented Feb 20, 2010 at 6:31
  • $\begingroup$ right, but i definitely wouldn't want to go trough the "whole" real line, so going through the input set would be the best way. $\endgroup$
    – Nemanja
    Commented Feb 20, 2010 at 10:48
  • $\begingroup$ with the greedy algorithm you don't. the points you choose are on the real line, but their locations are discrete, and fixed by the input. A similar argument to the one that bounds the number of guesses implies that the only points you need to examine are those that are the midpoint of a pair of points from the input. so there are only n-choose-2 points to examine. $\endgroup$
    – Suresh Venkat
    Commented Feb 20, 2010 at 17:45
0
$\begingroup$

You can measure the distance between closed sets using the Hausdorff metric. Two closed sets will have distance 0 iff they are the same set.

To compute the best approximation will probably depend quite a bit on how your (hopefully closed) set is represented.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for Hausdorff metric. I don't get exactly what is the significance of my representation of a set ? $\endgroup$
    – Nemanja
    Commented Feb 19, 2010 at 17:15
  • $\begingroup$ I suspect that this is not a useful answer to the OP's question (note that he clarifies it in one of the comments above). Also note that the Hausdorff distance is defined only between compact (not just closed) subsets of a complete metric space, and the OP did not say that his set S is compact. Indeed, the Hausdorff distance between a bounded set and an unbounded set is infinite. $\endgroup$
    – Pete L. Clark
    Commented Feb 19, 2010 at 17:17
  • $\begingroup$ In light of the OP's more recent comment above -- that S is finite -- I withdraw my above comment. $\endgroup$
    – Pete L. Clark
    Commented Feb 19, 2010 at 17:26
0
$\begingroup$

I'd use k-means clustering (with k = n) to find the n centroids and use these centroids as the set R.

k-means minimizes the expected L2 distance (i.e. $|x-c|^2$, not $|x-c|$, in case that's important -- in many cases it's not) between a point and its centroid. If all of your new testing points are in the training set, then the ideal distance (in S) would be 0, and the new distance (in R given by the centroids) will be minimized by k-means. If your testing points are different from the training points, but come from the same distribution, then this will minimize an upper bound on the distance.

In principle, k-means clustering is NP-hard in most cases. One particular algorithm (called k-means algorithm) seems to work well in many practical cases.

Improve this answer
$\endgroup$
2
  • $\begingroup$ the k-means algorithm doesn't even minimize the expected $\ell_2$ distance btw. it's merely a local optimization heuristic. $\endgroup$
    – Suresh Venkat
    Commented Feb 19, 2010 at 20:16
  • $\begingroup$ Thanks. I corrected some terminology to account for that. $\endgroup$
    – user3035
    Commented Feb 19, 2010 at 20:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .