Lineary separate two sets

Question

I have three arrays (it's written in C but that is not important, it could be any language):

  float x[] = {
        0.72, 0.91, 0.46, 0.03, 0.12, 0.96, 0.79, 0.46, 0.66, 0.72, 0.35, -0.16,
        -0.04, -0.11, 0.31, 0.00, -0.43, 0.57, -0.47, -0.72, -0.57, -0.25,
        0.47, -0.12, -0.58, -0.48, -0.79, -0.42, -0.76, -0.77
  };

  float y[] = {
        0.82, -0.69, 0.80, 0.93, 0.25, 0.47, -0.75, 0.98, 0.24, -0.15, 0.01,
        0.84, 0.68, 0.10, -0.96, -0.26, -0.65, -0.97, -0.03, -0.64, 0.15, -0.43,
        -0.88, -0.90, 0.62, 0.05, -0.92, -0.09, 0.65, -0.76      
  };

  int outputs[] = {
      -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
  };

First two arrays are X and Y coordinates of a points on two dimensional plane.

Third array decides if the point is from set 1 or set -1.

I need an algorithm that will linearry separate these two sets of points. I.e. it should return a and b coeficients from this equation:

y = a*x + b

Which is a general line equation.

Look at the first image here:

http://dynamicnotions.blogspot.com/2008/09/single-layer-perceptron.html

To better understanbd what I need.

Answer 1

I've looked at your graphs on the first page, but I am still not clear what you actually want as a result. My guess is you want the best co-efficients for an approximation of a linear line which "best fits" the two groups of points ? It appears your "neural net" for the Perceptron does exactly that, already. Might help to clarify ?

Answer 2

The simple way to find the best fit line (or a polynomial curve) for a set of datapoints is to use a Least Squares method. That page and others linked to it describe the mathematics, and the formulae for a linear least-squares calculation for fitting a straight line is here. However, these pages don't give you potted solutions in your favorite programming language.

Answer 3

Support Vector Machines will do what you want (albeit somewhat difficult to implement)

Answer 4

Hi.

If you want to go back from the perceptron solution, just put in "zero" as the target and solve for what inputs give a zero in the perceptron formula, that's an answer.

More generally you probably want this: http://en.wikipedia.org/wiki/Linear%5Fdiscriminant%5Fanalysis

Answer 5

If you try all linear edges (extrapolated to infinity) of the convex hull of one of the sets, then that should give you a line that separates the two sets, otherwise it's not possible to linearly separate them.