# Approximating a set with fixed number of elements

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.

(Edited in light of the comments below.)

-
What is a one-dimensional set? – Qiaochu Yuan Feb 19 '10 at 16:48
What is a point? What is close? – Jonas Meyer Feb 19 '10 at 16:50
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? – Pete L. Clark Feb 19 '10 at 16:57
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| – Nemanja Feb 19 '10 at 17:01
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. – Harald Hanche-Olsen Feb 19 '10 at 17:02

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).

-
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. – Nemanja Feb 20 '10 at 4:46
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. – Suresh Venkat Feb 20 '10 at 6:30
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) – Suresh Venkat Feb 20 '10 at 6:31
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. – Nemanja Feb 20 '10 at 10:48
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. – Suresh Venkat Feb 20 '10 at 17:45

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.

-
Thanks for Hausdorff metric. I don't get exactly what is the significance of my representation of a set ? – Nemanja Feb 19 '10 at 17:15
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. – Pete L. Clark Feb 19 '10 at 17:17
In light of the OP's more recent comment above -- that S is finite -- I withdraw my above comment. – Pete L. Clark Feb 19 '10 at 17:26

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.

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