Пользователь
0,0
рейтинг
29 сентября 2010 в 20:20

Разработка → Классификация данных методом опорных векторов из песочницы

Добрый день!

В данной статье я хочу рассказать о проблеме классификации данных методом опорных векторов (Support Vector Machine, SVM). Такая классификация имеет довольно широкое применение: от распознавания образов или создания спам-фильтров до вычисления распределения горячих аллюминиевых частиц в ракетных выхлопах.

Сначала несколько слов об исходной задаче. Задача классификации состоит в определении к какому классу из, как минимум, двух изначально известных относится данный объект. Обычно таким объектом является вектор в n-мерном вещественном пространстве . Координаты вектора описывают отдельные аттрибуты объекта. Например, цвет c, заданный в модели RGB, является вектором в трехмерном пространстве: c=(red, green, blue).



Если классов всего два («спам / не спам», «давать кредит / не давать кредит», «красное / черное»), то задача называется бинарной классификацией. Если классов несколько — многоклассовая (мультиклассовая) классификация. Также могут иметься образцы каждого класса — объекты, про которые заранее известно к какому классу они принадлежат. Такие задачи называют обучением с учителем, а известные данные называются обучающей выборкой. (Примечание: если классы изначально не заданы, то перед нами задача кластеризации.)

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

Итак, математическая формулировка задачи классификации такова: пусть X — пространство объектов (например, ), Y — наши классы (например, Y = {-1,1}). Дана обучающая выборка: . Требуется построить функцию (классификатор), сопоставляющий класс y произвольному объекту x.

Метод опорных векторов



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

Идея метода


Идею метода удобно проиллюстрировать на следующем простом примере: даны точки на плоскости, разбитые на два класса (рис. 1). Проведем линию, разделяющую эти два класса (красная линия на рис. 1). Далее, все новые точки (не из обучающей выборки) автоматически классифицируются следующим образом:

точка выше прямой попадает в класс A,
точка ниже прямой — в класс B.



Такую прямую назовем разделяющей прямой. Однако, в пространствах высоких размерностей прямая уже не будет разделять наши классы, так как понятие «ниже прямой» или «выше прямой» теряет всякий смысл. Поэтому вместо прямых необходимо рассматривать гиперплоскости — пространства, размерность которых на единицу меньше, чем размерность исходного пространства. В , например, гиперплоскость — это обычная двумерная плоскость.

В нашем примере существует несколько прямых, разделяющих два класса (рис. 2):



С точки зрения точности классификации лучше всего выбрать прямую, расстояние от которой до каждого класса максимально. Другими словами, выберем ту прямую, которая разделяет классы наилучшим образом (красная прямая на рис.2). Такая прямая, а в общем случае — гиперплоскость, называется оптимальной разделяющей гиперплоскостью.

Вектора, лежащие ближе всех к разделяющей гиперплоскости, называются опорными векторами (support vectors). На рисунке 2 они помечены красным.

Немного математики


Пусть имеется обучающая выборка: .

Метод опорных векторов строит классифицирующую функцию F в виде ,
где — скалярное произведение, w — нормальный вектор к разделяющей гиперплоскости,b — вспомогательный параметр. Те объекты, для которых F(x) = 1 попадают в один класс, а объекты с F(x) = -1 — в другой. Выбор именно такой функции неслучаен: любая гиперплоскость может быть задана в виде для некоторых w и b.



Далее, мы хотим выбрать такие w и b которые максимизируют расстояние до каждого класса. Можно подсчитать, что данное расстояние равно . Проблема нахождения максимума эквивалентна проблеме нахождения минимума . Запишем все это в виде задачи оптимизации:



которая является стандартной задачей квадратичного программирования и решается с помощью множителей Лагранжа. Описание данного метода можно найти в Википедии.

Линейная неразделимость



На практике случаи, когда данные можно разделить гиперплоскостью, или, как еще говорят, линейно, довольно редки. Пример линейной неразделимости можно видеть на рисунке 3:



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

Классифицирующая функция F принимает вид . Выражение называется ядром классификатора. С математической точки зрения ядром может служить любая положительно определенная симметричная функция двух переменных. Положительная определенность необходимо для того, чтобы соответствующая функция Лагранжа в задаче оптимизации была ограничена снизу, т.е. задача оптимизации была бы корректно определена.

Точность классификатора зависит, в частности, от выбора ядра. На видео можно увидеть иллюстрирацию классификации при помощи полиномиального ядра:



Чаще всего на практике встречаются следующие ядра:

Полиномиальное:

Радиальная базисная функция:

Гауссова радиальная базисная функция:

Сигмоид:

Заключение и литература



Среди других классификаторов хочу отметить также метод релевантных векторов (Relevance Vector Machine, RVM). В отличие от SVM данный метод дает вероятности, с которыми объект принадлежит данному классу. Т.е. если SVM говорит "x пирнадлежит классу А", то RVM скажет "x принадлежит классу А с вероятностью p и классу B с вероятностью 1-p".

1. Christopher M. Bishop. Pattern recognition and machine learning, 2006.

2. К. В. Воронцов. Лекции по методу опорных векторов.
Igor @Invision
карма
31,0
рейтинг 0,0
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (27)

  • +6
    Хороший, годный пост на хорошую, правильную тему.
    • 0
      Спасибо!
    • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    «Задача классификации (или, как ее иногда называют, задача кластеризации)»

    Есть разница. При классификации набор классов задан с самого начала, по-моему.
    • 0
      Вы правы, при классификации классы почти всегда известны изначально. Однако же, не всегда.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Поправил, спасибо за уточнение.
      • 0
        В Desicion trees совсем другой алгоритм и совсем другие задачи, поэтому нельзя утверждать что они используются только для классификации, так же как и SVM может использоваться для многих задач: классификации, кластеризации, предсказания свойства
  • +1
    Вот тут www.csie.ntu.edu.tw/~cjlin/libsvm/ есть практический пример и демо
    • 0
      Вроде бы у них на сайте были еще разные интересные data sets для тестирования классификатора.
  • 0
    Было бы хорошо провести параллели с другими популярными и не очень методами э… классификаторов с учителем, вроде CRF, Maxent.
    • +1
      Я еще планирую про классификатор RVM (Relevance Vector Machine) написать. А после этого можно и обзорно-сравнивающую статью сделать.
      • 0
        Про RVM было бы интересно. В целом +1.
  • 0
    А где видео?
    • 0
      Наверное, браузер по каким-то причинам не отображает. Оригинальная ссылка вот.
      • 0
        Спасибо. Теперь кстати и браузер отображает.
  • 0
    Автору плюс. Скажите, а есть ли какие-нибудь критерии выбора ядра. Я имею ввиду какие-либо аналитические методы. Или только на-глаз?
    • +1
      Кстати, на твиттере промелькнуло: 25 типов kernel-функций.
      • +1
        Интересно, надо сохранить на будущее :)
        Я не встречал нормальных работающих методов для выбора ядра. Видел лишь пару статей на тему «имеется конкретное ядро с какими-то параметрами. Как выбрать эти параметры наилучшим способом для уменьшения ошибки классификации.»
        • +1
          Если бы еще и kernel можно было всегда выбрать просто все бы задачи по классификации были бы уже решены) Не бывает универсального классификатора к сожалению. Так что kernel функцию придется всегда выбирать в зависимости от задачи. В целом если feature space уже изначально досточно большой обычно используется линейный kernel (что логично).

          Когда изучала данную тему мне очень помогли слайды from Andrew Moore www.autonlab.org/tutorials/
          (может не самые стильные зато доступные — вообще рекомендую)
          • 0
            Ага, no free lunch theorem :)
            Посмотрел слайды, неплохо написано. И многие интересные темы освещены.
  • +1
    Насколько мне известно, некоторые дополнительные материалы по теме можно найти, например, в книге Фукунга К. «Введение в статистическую теорию распознавания образов».
    Статья хорошая. Статистические методы распознавания сейчас нередко игнорируются в пользу нейронных сетей, а это не всегда правильно.
    • 0
      Спасибо за ссылку, обязательно гляну.
      Да, мне тоже не всегда нравятся нейронные сети :)
    • 0
      Не blackbox единым…
    • 0
      Самая главная статья это В.М. Вапник «The Nature of Statistical Learning Theory»
      • 0
        точнее книга
  • 0
    Только вот в перечислении ядер зачем-то отделено Гауссово ядро от ядра на основе радиально-базисной функции, хотя они эквивалентны. Пруфлинк

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.