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.


  • 1
    $\begingroup$ 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$? $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Akash Rupela Oct 31 '14 at 11:30
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Akash Rupela Oct 31 '14 at 11:33
  • $\begingroup$ @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$. $\endgroup$ – TZakrevskiy Oct 31 '14 at 11:44
  • $\begingroup$ @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. $\endgroup$ – TZakrevskiy Oct 31 '14 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.