确定这两个类是否可线性分离(在2D中算法)

Question

确定这两个类是否可线性分离(在2D中算法)

Håv*_*hus 16 algorithm math classification machine-learning

有两个类,我们称之为X和O.属于这些类的许多元素在xy平面中展开.下面是两个类不可线性分离的示例.无法绘制直线,在线的每一侧完美地划分X和Os.

两个类的成员分布在xy平面上

一般来说,如何确定两个类是否可线性分离？.我对一种算法感兴趣,该算法不对元素的数量或它们的分布做出假设.当然优选最低计算复杂度的算法.

Answer 1

Dar*_*rda 16

如果您分别找到了X点和O点的凸包(即在此阶段你有两个单独的凸包),那么你只需要检查船体的任何部分是否相交或者是否有一个船体被另一个包围.

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

由于船体根据定义是凸的,因此任何分隔器都是直线.

有迹象表明,既可以采用查找凸包有效的算法(该qhull算法是基于O(nlog(n)) quickhull方法我认为),并执行交线测试为一组段(的扫掠迹线在O(nlog(n))),所以总体看来一个有效的O(nlog(n))算法应该是可能的.

这种类型的方法还应该通过形成凸包并对每个组执行相交测试来推广到一般的k-way分离测试(其中您有k对象组).

它也应该在更高的维度上工作,尽管交叉测试将开始变得更具挑战性......

希望这可以帮助.

我收回了很棒的评论.该问题可以表示为具有两个变量的LP,并且通过Megiddo和Dyer的算法在时间O(n)中求解. (2认同)

Answer 2

Aas*_*set 5

这是一个我很确定可以工作的天真算法（如果是这样，表明问题不是 NP 完全的，正如另一篇文章声称的那样），但如果它可以更有效地完成，我不会感到惊讶：如果存在分隔线，则可以移动和旋转它，直到它碰到两个 X 或一个 X 和一个 O。因此，我们可以简单地查看与两个 X 或一个相交的所有可能的线X 和一个 O，看看它们中是否有任何一条是分割线。因此，对于每个O(n^2)对，迭代所有n-2 个其他元素以查看是否所有 X 都在一侧，所有 O 都在另一侧。总时间复杂度：O(n^3)。