GID

How do we verify linear separability with Python?

· Georgios Is. Detorakis · 3 minutes read

Two sets $ A $ and $ B $ in an $ n $ dimensional Euclidean space are linear separable if there exist $ n + 1 $ numbers $ w_i \in \mathbb{R} $ such that every point $ a \in A $ satisfies

$$ \sum_{i=1}^{n}w_i a_i > k, $$

and every point $ b \in B $ satisfies

$$ \sum_{i=1}^{n}w_i b_i < k, $$

where $ k \in \mathbb{R} $ defines a linear border (e.g., a line) between data points of the two sets.

In layperson’s terms, let’s say we have two two-dimensional data sets (e.g., each data point is described by two coordinates, x and y). These two sets are linearly separable if we can draw at least one line that will separate the points of set A from those of set B.

Many times we have to solve a classification or clustering problem. If we could know a priori if the involved sets are linearly separable, we could choose the appropriate classification algorithm. For instance, if the data sets are not linearly separable, we won’t be able to use a linear classifier.

Therefore, one way to know if the sets at hand are linear separable is to compute the convex hull of each set and check if those convex hulls intersect or one contains the other, or they overlap. If any of those three conditions is true, then we know that the two sets are not linearly separable. In Python, we can quickly check that using the function ConvexHull of Scipy. Here is an example:

import matplotlib.pylab as plt

from sklearn.datasets import make_moons, make_blobs
from scipy.spatial import ConvexHull


if __name__ == '__main__':
    S = 8       # size of scatter plot point
    blobs = make_blobs(n_samples=100, centers=2, random_state=13)
    moons = make_moons(n_samples=100)

    fig = plt.figure(figsize=(13, 11))
    ax1 = fig.add_subplot(221)
    Xb, Yb = blobs
    x1b = Xb[Yb == 0]
    x2b = Xb[Yb == 1]
    ax1.scatter(x1b[:, 0], x1b[:, 1], s=S)
    ax1.scatter(x2b[:, 0], x2b[:, 1], c="orange", s=S)
    ax1.set_xticks([])
    ax1.set_yticks([])

    ax2 = fig.add_subplot(222)
    X, Y = moons
    x1 = X[Y == 0]
    x2 = X[Y == 1]
    ax2.scatter(x1[:, 0], x1[:, 1], s=S)
    ax2.scatter(x2[:, 0], x2[:, 1], c="orange", s=S)
    ax2.set_xticks([])
    ax2.set_yticks([])

    ax3 = fig.add_subplot(223)
    ch1 = ConvexHull(x1b)			# Compute the convex hull
    ax3.scatter(x1b[:, 0], x1b[:, 1], s=S)
    ax3.plot(x1b[ch1.vertices, 0], x1b[ch1.vertices, 1], lw=2, c='k')
    ch2 = ConvexHull(x2b)
    ax3.scatter(x2b[:, 0], x2b[:, 1], s=S)
    ax3.plot(x2b[ch2.vertices, 0], x2b[ch2.vertices, 1], lw=2, c='k')
    ax3.set_xticks([])
    ax3.set_yticks([])

    ax4 = fig.add_subplot(224)
    ch1 = ConvexHull(x1)
    ax4.scatter(x1[:, 0], x1[:, 1], s=S)
    ax4.plot(x1[ch1.vertices, 0], x1[ch1.vertices, 1], lw=2, c='k')
    ch2 = ConvexHull(x2)
    ax4.scatter(x2[:, 0], x2[:, 1], s=S)
    ax4.plot(x2[ch2.vertices, 0], x2[ch2.vertices, 1], lw=2, c='k')
    ax4.set_xticks([])
    ax4.set_yticks([])

    plt.savefig("convec_hulls.png")
    plt.show()
Figure 1. Blobs and moons data sets along with their convex hulls. The blobs are linear separable since the convex hull of the blue set does not intersect or overlap with the convex hull of the orange data set. On the other hand, the moons data set is not linear separable.

Figure 1. Blobs and moons data sets along with their convex hulls. The blobs are linear separable since the convex hull of the blue set does not intersect or overlap with the convex hull of the orange data set. On the other hand, the moons data set is not linear separable.