在计算上确定两组点是否线性可分的最有效方法是应用线性规划。GLTK非常适合这个目的，几乎每一种高级语言都为其提供了一个接口——R、Python、Octave、Julia 等。

关于建议使用 SVM 的答案：

使用 SVM 是验证线性可分性的次优解决方案，原因有两个：

1. SVM 是软边距分类器。这意味着线性核 SVM 可能会适应一个分离平面，即使它实际上可能也不能完美分离。如果您随后检查错误率，它将不为 0，并且您将错误地得出这两个集合不是线性可分的结论。这个问题可以通过选择一个非常高的成本系数 C 来减轻 - 但这本身的计算成本非常高。

2. SVM 是最大边距分类器。这意味着该算法将尝试找到一个分离平面，该平面将两个类分开，同时尽可能远离两者。同样，这是一个不必要地增加计算工作量的特征，因为它计算的东西与回答线性可分性问题无关。

假设您有一组点 A 和 B：

然后，您必须在以下条件下最小化 0：

（下面的 A 是一个矩阵，而不是上面的点集）

“最小化 0”有效地意味着您不需要实际优化目标函数，因为这对于确定集合是否线性可分不是必需的。

最后 ( ) 定义了分离平面。

如果您对 R 中的工作示例或数学详细信息感兴趣，请查看此内容。

好吧，支持向量机 (SVM) 可能就是您正在寻找的东西。例如，具有线性 RBF 内核的 SVM 将特征映射到更高维度的空间，并尝试通过线性超平面分离类别。这是一个很好的SVM 短视频，说明了这个想法。

您可以使用搜索方法包装 SVM 以进行特征选择（包装模型），并尝试查看您的任何特征是否可以线性分离您拥有的类。

使用 SVM 有很多有趣的工具，包括LIBSVM、MSVMPack和Scikit-learn SVM。

如果存在，线性感知器保证能找到解决方案。这种方法对大尺寸无效。在计算上确定两组点是否线性可分的最有效方法是应用@Raffael 提到的线性规划。

一个快速的解决方案是解决感知器。在 Matlab 中使用 Perceptron 解决的示例代码在这里