有两个类别，我们称之为X和O。这些类别的若干元素分布在xy平面上。下面是一个例子，展示了两个类别在线性上不可分的情况。在这种情况下，不可能画出一条直线，完美地将X和O分开，分别位于直线的两侧。
如何一般性地确定两个类别是否线性可分？ 我对一个算法感兴趣，这个算法不假设元素的数量或分布。当然，优先选择计算复杂度最低的算法。
回答：
如果你分别为X点和O点找到了凸包（即此时你有两个独立的凸包），你只需要检查这些凸包的任何部分是否相交，或者其中一个凸包是否被另一个包围。
如果发现两个凸包完全不相交，那么这两个数据集在几何上是可分的。
由于凸包按定义是凸的，任何分隔线都将是一条直线。
有高效的算法既可以用来寻找凸包（qhull算法基于O(nlog(n))的快速凸包方法，我想），也可以对一组线段进行线线交点测试（扫描线在O(nlog(n))），因此总体来看，似乎可能实现一个高效的O(nlog(n))算法。
这种方法也应该可以推广到一般k-way分离测试（你有k组对象），通过形成凸包并为每一组进行交点测试。
它在更高维度下也应该适用，尽管交点测试会开始变得更加具有挑战性…
希望这对你有帮助。
