1
$\begingroup$

Lets assume I have two sets of points, each characterized as being "A" or "B", respectively, that are in a Euclidean plane. Theoretically these two sets are samplings from a space that has boundaries. Now I want to construct a boundary. So I want to construct the simplest curve that divides the two sets of points.

A simple example would be a space where x< 0 is the A region, x>0 is the B region. Generate 100 random points in a unit box centered on the origin. Now you want to find a line that divides the "A" points from the"B" points (forgetting that you know what the original answer was). How would you do this?

How would you do this in general?

Improve this question
$\endgroup$
5
  • $\begingroup$ Are A and B finite or not? what if e.g. A is the set of points with rational coortinates and B is its complement? $\endgroup$
    – Pietro Majer
    Commented Jul 2, 2012 at 17:39
  • $\begingroup$ There certainly are sets of points for which this would generate either an infinite in complexity or non-definable boundary. However, in this case, A and B are finite. For heuristic purposes one can assume that they are actually random points drawn from two domains that do have a well-defined boundary between them. (e.g. the interior and exterior of a circle in a plane.) Currently I am considering something functional, but less than completely satisfying involving convex hulls and subtractions of the overlaps. $\endgroup$
    – Carolyn
    Commented Jul 2, 2012 at 17:53
  • 2
    $\begingroup$ If you need to do this in practice, this is known as a binary classification problem. The fashionable tool at the moment is a support vector machine. en.wikipedia.org/wiki/Support_vector_machine $\endgroup$
    – Douglas Zare
    Commented Jul 2, 2012 at 18:02
  • $\begingroup$ Does it matter if I have five sets of points? And one set is completely bound by the other sets? Can SVMs still address this problem? $\endgroup$
    – Carolyn
    Commented Jul 2, 2012 at 23:46
  • 1
    $\begingroup$ Yes, they can help. It is no longer a binary classification problem, but there are a few standard ways to use multiple binary SVMs, and knowledge of the specific properties of the set may give you reasons to choose one method over another. $\endgroup$
    – Douglas Zare
    Commented Jul 3, 2012 at 0:55

2 Answers 2

Reset to default
3
$\begingroup$

Assuming the size of A and B are less than 10000 points, I would use a Support Vector Machine with a Gaussian Kernel.

http://en.wikipedia.org/wiki/Support_vector_machine

Improve this answer
$\endgroup$
0
$\begingroup$

This is not directly responsive to your question, but it might be relevant to what you're trying to accomplish.

Suppose you find a curve that correctly classifies all 100 of your points. You'd like this curve to have a high probability of correctly classifying a large fraction of the points in the much larger sample from which your 100 points were drawn.

In particular, suppose you'd like your curve to have probability at least $1-\delta$ of correctly classifying a fraction at least $1-\epsilon$ of that larger set of points (where $\delta$ and $\epsilon$ are some fixed --- and presumably small --- constants).

A sufficient condition for this is

$$100 > {N\over\epsilon}Log(1/\delta)$$

where $N$ is the maximum number of points that can always be successfully separated by some member of your class of allowable curves. E.g. if you restrict your curves to be lines, then $N=3$, because any 3 points, no matter how they are labeled $A$ and $B$, can be successfully separated by a line.

I wish I could remember where I learned this, so that I could point you to a source. I have a reasonably powerful (but perhaps faulty) memory that Scott Aaronson had something to do with it.

Improve this answer
$\endgroup$

You must log in to answer this question.

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