# Finding simplest function to distinguish 2 sets

I wish to find a function that distinguishes $2$ sets. I have m data values in form of n-tuples out of which k are supposed to be mapped to a value less than $0$ and other m-k are supposed to be mapped to a value greater than or equal to $0$. My main Aim is that The function needs to be simple to compute, so not neccessary polynomial.(anything better than a $(m-1)$ degree polynomial in the worst case).

For example for the data$(m=6,k=3,n=2)$;

$A((1,3), (2,5), (12,67))$

$B((3,4), (14,20),(4,6))$

i.e the latter tuples $(x,y)$ belong to set $B$ and the former $3$ belong to set $A$.

Here, my dream (or at least a very good) function would be $f(y,x)=(y/x) -2$ . Which sends A to positive and B to negative values.

Of course i can have a trivial polynomial fit of degree 5 but that thing gets messy when m is large. Since there is lot of freedom on values and nature of function, I m certain something better is achievable. But I am not sure how to do this. And if not a general solution is available, even for the case of n=2 or 3 variables will be very very much appreciated. Even related links without explanation will be of great help.

Thankyou

• Do you want to have a function which works for a fixed given data and any comtellation of $A$ and $B$? So your function should be independent of $A$ and $B$? – sranthrop Oct 31 '14 at 11:36

I have the idea that the function can only be constructed if the sets $A$ and $B$ are well-known. If that is the case you can do it with $1_A-1_B$ where $1_X$ denotes the characteristic function of set $X$.

I would not be surprised if I am overlooking something here. If so then please let me know. Of course I will delete my answer in that case.

• A and B are well known. Actually, I want to use that function to be well defined as sending every element into A or B ($A$ $U$ $B$ is not $R$ ). Characteristic function is defined only on set A and B. – Akash Rupela Oct 31 '14 at 11:30
• If e.g. $A\subset\mathbb R^2$ then $1_A$ (and $1_B$) is defined for every $(x,y)\in\mathbb R^2$. This with $(x,y)\mapsto 1$ if $(x,y)\in A$ and $(x,y)\mapsto 0$ otherwise. – drhab Oct 31 '14 at 11:38

One naïve approach.

You have $k$ points in $\Bbb R^n$ (the set $A$) on which the fucntion is negative and $m-k$ points in $\Bbb R^n$ (the set $B$) on which the function is positive. We also suppose that $A\cap B=\emptyset$.

Take $$g_A(x) = dist (x,A) = \min_{y\in A} (\|x-y\|)$$ $$g_B(x) = dist (x,B) = \min_{y\in B} (\|x-y\|)$$ As for the norm, you can take whichever you like on $\Bbb R^n$.

Now your $f$ can be taken as $$f(x)=g_A(x)-g_B(x).$$ If I'm not mistaken, the cost of this function should be $\mathcal O(mn)$.

Of course, for a known set of points this function is not optimal, but it always works.

• Thankyou. I like your idea. However, The small problem with this is that It essentially traverses the entire data everytime I wish to compute it for a new value. I do not want a polynomial fit for a special case for the same reason. The computational time it takes is essentially same as magnitude of the data. I hope my comment made sense. – Akash Rupela Oct 31 '14 at 11:33
• @sranthrop erm, did you look at the definition of the function $f$? In your case $f(x)=-1$ if $x\in A$ and $f(x)=1$ if $x\in B$. – TZakrevskiy Oct 31 '14 at 11:44
• @AkashRupela I see your point (more or less). As I said, this function is quite naïve. I don't quite see how in general case we can build such a separating function without accessing all data points to compute the value of this function at a given point. – TZakrevskiy Oct 31 '14 at 11:49