Как узнать, являются ли данные линейно разделимыми?

21

Данные имеют много функций (например, 100), а количество экземпляров равно 100 000. Данные редки. Я хочу соответствовать данным, используя логистическую регрессию или SVM. Как я узнаю, являются ли объекты линейными или нелинейными, чтобы я мог использовать трюк ядра, если он нелинейный?

Сян Чжан
источник

Ответы:

22

Есть несколько способов определить, являются ли данные линейно разделимыми, некоторые из них выделены в этой статье (1). Предполагая два класса в наборе данных, ниже приведены несколько методов, позволяющих определить, являются ли они линейно разделимыми:

  1. Линейное программирование: определяет целевую функцию, подвергаемую ограничениям, которые удовлетворяют линейной отделимости. Вы можете найти подробности о реализации здесь .
  2. Метод персептрона : персептрон гарантированно сходится, если данные линейно разделимы.
  3. Квадратичное программирование: Целевая функция оптимизации квадратичного программирования может быть определена с ограничением, как в SVM.
  4. Вычислительная геометрия: если можно найти две непересекающиеся выпуклые оболочки, то данные линейно разделимы
  5. Метод кластеризации: если можно найти два кластера с чистотой кластера 100%, используя некоторые методы кластеризации, такие как k-средних, то данные являются линейно разделимыми.

    (1): Элизондо, Д., «Проблема линейной отделимости: некоторые методы тестирования», в Neural Networks, IEEE Transactions on, vol.17, no.2, pp.330-344, March 2006 doi: 10.1109 / TNN. 2005.860871

Шуайб Ахмед
источник
1
Пожалуйста, дайте ссылку (ссылки могут гнить) и хотя бы небольшое объяснение того, какие методы рассматриваются.
Scortchi - Восстановить Монику
2
Благодарю. Хороший ответ (+1). Пакет R safeBinaryRegressionтакже реализует подход линейного программирования.
Scortchi - Восстановить Монику
Который (подход LP) легко интерпретируется геометрически, вычислительно эффективен и общедоступен (как процедуры LP).
user603
3

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

На практике вы должны тренироваться и тестировать одни и те же данные. Если есть такая линия, то вы должны приблизиться к 100% точности или 100% AUC. Если такой линии нет, то обучение и тестирование одних и тех же данных приведут к некоторым ошибкам. Исходя из объема ошибок, стоит или не стоит пытаться использовать нелинейный классификатор.

iliasfl
источник
1

мяNвес,б ||вес||2
s,T я,(вес'Икся+б)Yя1

мяNs,б s
s,T я,(вес'Икся+б)Yя1-s
s0

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

Шридхар Тиагараджан
источник
+1 это геометрическая интуиция, лежащая в основе метода, реализованного в пакете RsafeBinaryRegression
user603
-2

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

Нил Г
источник