Определить, являются ли два класса линейно разделимыми (алгоритмически в 2D)

Question

Существует два класса, назовем их X и O. Ряд элементов, принадлежащих этим классам, расположен в плоскости xy.Вот пример, где два класса не являются линейно разделимыми.Невозможно нарисовать прямую линию, которая идеально разделяет X и O на каждой стороне линии.

Как определить, в общем,два класса линейно разделимы? .Меня интересует алгоритм, в котором не делается никаких предположений относительно количества элементов или их распределения.Алгоритм минимальной вычислительной сложности , конечно, предпочтителен.

Answer 1

Если вы нашли выпуклую оболочку для точек X и O по отдельности (то есть на этом этапе у вас есть две отдельные выпуклые оболочки), вам нужно будет просто проверить, пересекались ли какие-либо сегменты корпусов или был ли один корпус закрыт другим.

Если бы оказалось, что два корпуса полностью не пересекаются, два набора данных будут геометрически разделены.

Поскольку по определению корпуса являются выпуклыми, любой разделитель будет прямой линией.

Существуют эффективные алгоритмы, которые можно использовать как для поиска выпуклой оболочки (алгоритм qhull основан на подходе O(nlog(n)) quickhull , я думаю), так и для выполнения линии тесты пересечения линии для набора сегментов ( развертка при O(nlog(n))), поэтому в целом кажется, что эффективный алгоритм O(nlog(n)) должен быть возможен.

Этот тип подхода должен также распространяться на общие k-way тесты разделения (где у вас есть k групп объектов) путем формирования выпуклой оболочки и выполнения тестов пересечения для каждой группы.

Он также должен работать в более высоких измерениях, хотя испытания на пересечение станут более сложными ...

Надеюсь, это поможет.

Answer 2

В вычислительном отношении наиболее эффективным способом определить, являются ли два набора точек линейно разделимыми, является применение линейного программирования . GLTK идеально подходит для этой цели, и почти каждый язык высокого уровня предлагает интерфейс для него - R , Python, Octave, Julia и т. Д.

---

Давайтескажем, у вас есть набор точек A и B:

Затем вы должны минимизировать 0 для следующих условий:

(Aниже приведена матрица, а не набор точек сверху)

«Минимизация 0» фактически означает, что вам не нужно фактически оптимизировать целевую функцию, потому чтонет необходимости выяснять, являются ли множества линейно разделимыми.

В конце () определяется разделительная плоскость.

---

В случае, если вас интересует рабочий пример в R илиматематические детали, затем проверьте это .

Answer 3

Возможно, к этой проблеме можно применить линейное программирование .Я не уверен в его вычислительной сложности в формальном выражении, но метод успешно применяется для очень больших задач, охватывающих широкий спектр областей.

Answer 4

Вычисление линейного SVM с последующим определением, на какой стороне вычисленной плоскости с оптимальными маргиналами находится каждая точка, будет указано, являются ли точки линейно разделимыми.

Это излишне, но если вам нужно быстро убрать точкуРешение, есть много существующих библиотек SVM, которые сделают это для вас.

Answer 5

Линейный персептрон гарантированно найдет такое разделение, если оно существует.

См .: http://en.wikipedia.org/wiki/Perceptron.

Answer 6

Вот наивный алгоритм, который, я уверен, сработает (и, если это так, показывает, что проблема не является NP-полной, как утверждает другой пост), но я не удивлюсь, если это можно будет сделать. более эффективно: если разделительная линия существует, ее можно будет перемещать и вращать до тех пор, пока она не достигнет двух из X или одного X и одного O. Поэтому мы можем просто посмотреть на все возможные линии, которые пересекают два X ' es или один X и один O, и посмотрите, являются ли какие-либо из них разделительными линиями. Таким образом, для каждой из пар O (n ^ 2) выполните итерацию по всем n-2 другим элементам, чтобы увидеть, все ли X находятся на одной стороне, и все ли О с другой. Общая сложность времени: O (n ^ 3) .

Answer 7

Как упоминает ElKamina, Linear Perceptron гарантированно найдет решение, если оно существует. Этот подход не эффективен для больших размеров. В вычислительном отношении наиболее эффективный способ определить, являются ли два набора точек линейно разделимыми, - это применить линейное программирование.

Код с примером для решения с помощью Perceptron в Matlab: здесь

Answer 8

Хорошо, и Perceptron, и SVM (Машины опорных векторов) могут определить, являются ли два набора данных линейно разделимыми, но SVM может найти Оптимальную Гиперплоскость отделимости.Кроме того, он может работать с n-мерными векторами, а не только с точками.

Используется в таких приложениях, как распознавание лиц.Я рекомендую углубиться в эту тему.

Answer 9

В общем случае эта проблема является NP-трудной, но есть хорошие примерные решения, такие как K-означает кластеризацию .