I have a set of roughly $N\sim50'000$ points in $\mathbb{R}^d$ where $d<50.$ Most of those points are colored black but some (roughly 1% to 5%) are colored red. My goal is to "understand" how and where the red and black points lie in space. There is reason to believe that the red and black points are not distributed uniformly but cluster in some way.
One possible way to make the somewhat fuzzy goals above operational is to find simple sets which separate red and black points. My first, rather naive approach was to find the smallest axis-aligned rectangular box which contains all red points. But this does not work well, since the smallest such box which contains all red points contains all black points as well.
It seems I have to step up the sophistication of the enclosing shapes and be more flexible with the inclusion. The next idea is to determine a simple polytope, defined by a few inequalities (say between three and five) such that a loss function $L$ which penalises classification errors (i.e. red points not enclosed and black points enclosed in the polytope) is minimised. For a $k$-by-$d$ matrix $A$ and a $k$-vector $b$ define the loss function $L_i$ for a point $x_i$ and constants $\alpha, \beta >0$ by: $$ L_i(A,b) = \begin{cases} 0 \text{ if } Ax_i\leq b \text{ and }x_i\text{ is red}\\ \beta \text{ if } Ax_i\leq b \text{ and }x_i\text{ is black}\\ 0 \text{ if } Ax_i> b \text{ and }x_i\text{ is black}\\ \alpha \text{ if } Ax_i> b \text{ and }x_i\text{ is red.}\\ \end{cases}$$ The optimisation is then to find $A$ and $b$ such that $L=\sum_i L_i(A,b)$ is minimised.
This is quite different from a standard convex optimisation problem, where the polytope is given and $x$ to be found which minimises $L$ over the polytope. So my questions are:
- Has this problem been studied and are there references?
- What are possible ways to find an optimal or at least a "good" solution?
- Are there variations of the loss function which make the problem feasible?
- Are there better approaches to generate a simple summary of the shape of the two point clouds?