Есть ли способ проверить линейную отделимость набора данных двух классов в больших измерениях? Мои векторные векторы 40-длинные.
Я знаю, что всегда могу проводить эксперименты по логистической регрессии и определять скорость попадания в зависимости от частоты ложных тревог, чтобы определить, являются ли эти два класса линейно разделимыми или нет, но было бы хорошо узнать, существует ли уже стандартная процедура для этого.
Ответы:
Итак, машины опорных векторов (SVM), вероятно, то, что вы ищете. Например, SVM с линейным ядром RBF отображает объект в пространство более высокого измерения и пытается разделить классы линейной гиперплоскостью. Это хорошее короткое видео SVM, иллюстрирующее идею.
Вы можете обернуть SVM методом поиска для выбора функции (модель-обертка) и попытаться определить, может ли какая-либо из ваших функций линейно разделить ваши классы.
Есть много интересных инструментов для использования SVM, включая LIBSVM , MSVMPack и Scikit-learn SVM .
источник
e1071пакетsvmсkernel="linear"и смотреть на прогноз в сравнении с фактическим.В вычислительном отношении наиболее эффективный способ решить, являются ли два набора точек линейно разделимыми, - применение линейного программирования. . GLTK идеально подходит для этой цели, и почти каждый язык высокого уровня предлагает интерфейс для него - R , Python, Octave, Julia и т. Д.
Что касается ответа, предлагающего использование SVM :
Использование SVM является неоптимальным решением для проверки линейной отделимости по двум причинам:
SVM являются классификаторами с мягким полем. Это означает, что SVM с линейным ядром может согласиться на разделительную плоскость, которая не разделяется идеально, даже если это действительно возможно. Затем, если вы проверите частоту ошибок, она будет не равна 0, и вы ошибочно заключите, что эти два набора не являются линейно разделимыми. Эту проблему можно смягчить, выбрав очень высокий коэффициент затрат C, но это связано с очень высокими вычислительными затратами.
SVM являются классификаторами максимальной маржи. Это означает, что алгоритм будет пытаться найти разделяющую плоскость, разделяющую два класса, стараясь держаться как можно дальше от обоих. Опять же, это особенность, увеличивающая вычислительные усилия без необходимости, поскольку она вычисляет что-то, что не имеет отношения к ответу на вопрос о линейной отделимости.
Допустим, у вас есть набор точек A и B:
Затем вы должны минимизировать 0 для следующих условий:
(А ниже - это матрица, а не набор точек сверху)
«Минимизация 0» фактически означает, что вам не нужно на самом деле оптимизировать целевую функцию, потому что нет необходимости выяснять, являются ли множества линейно разделимыми.
В конце (
) определяется разделительная плоскость.
Если вы заинтересованы в рабочем примере по R или математическим деталям, проверьте это .
источник
Линейный Перцептрон гарантированно найдет решение, если оно существует. Этот подход не эффективен для больших размеров. В вычислительном отношении наиболее эффективный способ определить, являются ли два набора точек линейно разделимыми, - это применить линейное программирование, как упомянуто @Raffael.
Быстрое решение состоит в том, чтобы решить перцептрон. Код с примером, чтобы решить, используя Perceptron в Matlab здесь
источник