确定两个类是否线性可分(2D 中的算法) [英] Determine whether the two classes are linearly separable (algorithmically in 2D)

问题描述

有两个类，我们称它们为 X 和 O.属于这些类的许多元素分布在 xy 平面中.这是一个示例，其中两个类不是线性可分的.不可能画一条直线来完美地划分线的每一侧的 X 和 O.

There are two classes, let's call them X and O. A number of elements belonging to these classes are spread out in the xy-plane. Here is an example where the two classes are not linearly separable. It is not possible to draw a straight line that perfectly divides the Xs and the Os on each side of the line.

一般如何判断两个类是否线性可分?.我对一种算法感兴趣，该算法对元素的数量或其分布不做任何假设.最低计算复杂度的算法当然是首选.

How to determine, in general, whether the two classes are linearly separable?. I am interested in an algorithm where no assumptions are made regarding the number of elements or their distribution. An algorithm of the lowest computational complexity is of course preferred.

推荐答案

如果你分别找到 X 点和 O 点的凸包(即你有两个单独的凸包)然后你只需要检查包的任何部分是否相交或是否有一个包被另一个包起来.

If you found the convex hull for both the X points and the O points separately (i.e. you have two separate convex hulls at this stage) you would then just need to check whether any segments of the hulls intersected or whether either hull was enclosed by the other.

如果发现两个船体完全不相交，则两个数据集在几何上是可分离的.

If the two hulls were found to be totally disjoint the two data-sets would be geometrically separable.

由于根据定义，外壳是凸的，因此任何分隔符都是一条直线.

Since the hulls are convex by definition, any separator would be a straight line.

有一些有效的算法可以用来寻找凸包(qhull 算法基于O(nlog(n)) quickhull 方法我认为)，并为一个段集(sweepline 在 O(nlog(n)))，所以总的来说，一个高效的O(nlog(n))算法应该是可能的.

There are efficient algorithms that can be used both to find the convex hull (the qhull algorithm is based on an O(nlog(n)) quickhull approach I think), and to perform line-line intersection tests for a set of segments (sweepline at O(nlog(n))), so overall it seems that an efficient O(nlog(n)) algorithm should be possible.

这种方法也应该通过形成凸包和执行相交测试推广到一般的k-way分离测试(你有k组对象)每组.

This type of approach should also generalise to general k-way separation tests (where you have k groups of objects) by forming the convex hull and performing the intersection tests for each group.

它也应该适用于更高的维度，尽管相交测试将开始变得更具挑战性......

It should also work in higher dimensions, although the intersection tests would start to become more challenging...

希望这会有所帮助.

这篇关于确定两个类是否线性可分(2D 中的算法)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！