This is more of a "help me complete my knowledge", rather than a direct question.

Consider the a binary classification of two clouds of point (in general multiple categories, but let's keep it simple for the sake of our conversation).

I am looking for measures of quantifying the clean-ness/well-formed-ness/separability of data points.

Like the first figure below looks more separable that the 2nd one.

enter image description here

enter image description here

Here are a bunch of things I have seen. Could you add more to my list?

  • margin:

$$ \gamma = \max_{w, b} \min_i y_i (\mathbf{w}.\mathbf{x}_i + b), y_i \in \{\pm 1\} $$

  • distance between means: $$ d_{centers} = \|\mu_1 - \mu_2\| $$ where $$ \begin{cases} \mu_1 = \frac{1}{| \{i: y_i = +1\} |}\sum_{i: y_i = +1} x_i \\ \mu_2 = \frac{1}{| \{i: y_i = -1\} |}\sum_{i: y_i = -1} x_i \end{cases} $$

  • Min distance between pairs of points. $$ d_{avg} = \frac{1}{|\{i: y_i = 1 \}||\{j: y_j = -1 \}|} \sum_{i \text{ s.t. } y_i = +1, j \text{ s.t. } y_j = -1} \|\mathbf{x}_i - \mathbf{x}_j\| $$

  • Average distance between pairs of points. $$ d_{\min} = \min_{i \text{ s.t. } y_i = +1, j \text{ s.t. } y_j = -1} \|\mathbf{x}_i - \mathbf{x}_j\| $$


The minimum and average distance between points are both vulnerable to outliers. Another possibility is the median distance between points.

edit: Some more explanation:
Take either the first or second image and add a red-point at (1000,1000). Do you want this single point to have a big effect on the overall distance between the red and blue clouds? If you don't, the mean-distance will give undesirable results in this case.
Alternatively, consider a red-cloud contained in the unit-circle centered on (-1000,-1000) and a blue cloud in the unit circle centered on (1000, 1000). Suppose we add a single red-point at (1000,1000), do you want this to massively decrease the distances between the clouds? Because the minimum distance will do that.
Using the median distance between points, neither situation will change the distance between clouds by much. Whether that is desirable depends on the specific application.

  • $\begingroup$ Could you write these more formally? Specifically how you define "outliers"? $\endgroup$ – Daniel Oct 21 '16 at 17:14
  • $\begingroup$ @Daniel See edit $\endgroup$ – dimpol Oct 24 '16 at 8:54

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.