Есть ли способ определить, могут ли два набора точек быть разделены линией?
У нас есть два набора точек и если существует линия, разделяющая и такая, что все точки и только на одной стороне линии и все точки и только на другой стороне.B A B A A B B
Самый наивный алгоритм, который я придумал, - это построить выпуклый многоугольник для и и проверить их на пересечение. Похоже, временная сложность для этого должна быть как для построения выпуклого многоугольника. На самом деле я не ожидаю каких-либо улучшений в сложности времени, я не уверен, что это вообще можно улучшить. Но, по крайней мере, должен быть более красивый способ определить, есть ли такая линия.B O ( n log h )
Свойство двух ваших наборов данных заключается в линейной отделимости , просто в том, что есть линия, которая разделяет их. Много машинного обучения посвящено поиску линейных классификаторов , которые представляют собой линии, которые выполняют интересующее вас разделение.
Когда вы говорите о линиях, я предполагаю, что ваши точки лежат в плоскости. Вам нужно найти значения , и , чтобы для всех точек в наборе , и для всех точек в , . Таким образом, неравенство можно рассматривать как классификатор для множества .w 2 w 3 ( a 1 , a 2 ) A w 1 a 1 + w 2 a 2 ≥ w 3 ( b 1 , b 2 ) B w 1 b 1 + w 2 b 2 < w 3 w 1 x + w 2 y ≥ w 3 Aw1 w2 w3 (a1,a2) A w1a1+w2a2≥w3 (b1,b2) B w1b1+w2b2<w3 w1x+w2y≥w3 A
Существует множество алгоритмов машинного обучения для определения оптимальной линии (линейная регрессия, логистическая регрессия и т. Д.). Они найдут значения для на основе некоторой метрики ошибки. Затем вы можете проверить, все ли точки правильно классифицированы. То есть, все ли из значений в удовлетворяет уравнение выше и аналогично для . A Bw1,w2,w3 A B
Поскольку вас интересует только то, существует ли такая линия, вам нужно было использовать существующие методы (хотя это, вероятно, было бы проще). Просто настройте следующий набор равенств в терминах свободных переменных .w1,w2,w3
J = 1 , . , , | Б | B = { ( b 1 1 , b 1 2 ) , … , ( b | B | 1 , b | B | 2 ) }w1bj1+w2bj2<w3 для каждого, где .j=1,..,|B| B={(b11,b12),…,(b|B|1,b|B|2)}
Если эти ограничения согласованы, то существует линия.
источник
Если я правильно помню, опорные векторные машины строят разделяющие гиперплоскости. Если вы выберете измерение гиперплоскость, конечно же, станет прямой. Возможно, вам придется проверить, есть ли дополнительные предположения, которые должны быть выполнены. В двух измерениях весь подход может значительно упроститься, поэтому время выполнения может быть лучше, чем для общего подхода.2
источник