Линия разделяет два набора точек

19

Есть ли способ определить, могут ли два набора точек быть разделены линией?

У нас есть два набора точек и если существует линия, разделяющая и такая, что все точки и только на одной стороне линии и все точки и только на другой стороне.B A B A A B BABABAABB

Самый наивный алгоритм, который я придумал, - это построить выпуклый многоугольник для и и проверить их на пересечение. Похоже, временная сложность для этого должна быть как для построения выпуклого многоугольника. На самом деле я не ожидаю каких-либо улучшений в сложности времени, я не уверен, что это вообще можно улучшить. Но, по крайней мере, должен быть более красивый способ определить, есть ли такая линия.B O ( n log h )ABO(nlogh)

ком
источник

Ответы:

19

И Ули, и Дейв Кларк правильно замечают, что это проблема линейного программирования, даже в более высоких измерениях (могут ли эти два набора точек быть разделены гиперплоскостью?), И поэтому она может быть решена за полиномиальное время. Но поскольку ваши точки лежат на плоскости, ваша задача может быть решена за время, где - общее количество точек.nO(n)n

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

  • Если такой линии не существует, то исходные точки неразделимы.

  • Если находится на правильной стороне , то отделяет исходные точки.p

  • Если находится не на той стороне , то либо исходные точки могут быть разделены линией через , либо исходные точки вообще не могут быть разделены . Это условие легко проверить за время [упражнение].p O ( n )ppO(n)

Этот алгоритм выполняется в раз с высокой вероятностью (относительно случайного выбора алгоритма). Для получения более подробной информации см. Оригинальную статью или любое количество онлайн лекций.O(n)

JeffE
источник
Большое спасибо, я собираюсь углубиться в эту статью.
ком
В третьем случае вы утверждаете, что это может быть так, что строка проходит через , как это помогает узнать это? p
Tarrasch
10

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

Когда вы говорите о линиях, я предполагаю, что ваши точки лежат в плоскости. Вам нужно найти значения , и , чтобы для всех точек в наборе , и для всех точек в , . Таким образом, неравенство можно рассматривать как классификатор для множества .w 2 w 3 ( a 1 , a 2 ) A w 1 a 1 + w 2 a 2w 3 ( b 1 , b 2 ) B w 1 b 1 + w 2 b 2 < w 3 w 1 x + w 2 y w 3 Aw1w2w3(a1,a2)Aw1a1+w2a2w3(b1,b2)Bw1b1+w2b2<w3w1x+w2yw3A

Существует множество алгоритмов машинного обучения для определения оптимальной линии (линейная регрессия, логистическая регрессия и т. Д.). Они найдут значения для на основе некоторой метрики ошибки. Затем вы можете проверить, все ли точки правильно классифицированы. То есть, все ли из значений в удовлетворяет уравнение выше и аналогично для . A Bw1,w2,w3AB

Поскольку вас интересует только то, существует ли такая линия, вам нужно было использовать существующие методы (хотя это, вероятно, было бы проще). Просто настройте следующий набор равенств в терминах свободных переменных .w1,w2,w3

w1a1i+w2a2iw3 для каждого, где .i=1,..,|A|A={(a11,a21),,(a1|A|,a2|A|)}

J = 1 , . , , | Б | B = { ( b 1 1 , b 1 2 ) , , ( b | B | 1 , b | B | 2 ) }w1b1j+w2b2j<w3 для каждого, где .j=1,..,|B|B={(b11,b21),,(b1|B|,b2|B|)}

Если эти ограничения согласованы, то существует линия.

Дэйв Кларк
источник
5

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

улы
источник