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

Ранее  были рассмотрены машины опорных векторов (SVM). Пожалуй, это самый сложный метод классификации из всех описанных в книге. SVM принимает набор данных, состоящий из чисел, и пытается спрогнозировать, в какую категорию он попадает. Можно, например, определить роль игрока в баскетбольной команде по его росту и скорости бега. Для простоты рассмотрим всего две возможности: позиция в нападении, для которой требуется высокий рост, и в защите, где игрок должен быстро перемещаться.

SVM строит прогностическую модель, отыскивая линию, разделяющую две категории. Если отложить по одной оси рост, а по другой – скорость и нанести наилучшие позиции для каждого игрока, то получится диаграмма, изображенная на рис. 12.7. Нападающие представлены крестиками, а защитники – кружками. Также на диаграмме показано несколько линий, разделяющих данные на две категории.

Рис. 12.7. Диаграмма бескетболистов и разделяющие линии

Машина опорных векторов находит линию, наилучшим образом разделяющую данные. Это означает, что она проходит на максимальном расстоянии от расположенных вблизи нее точек. На рис. 12.7 разделяющих линий несколько, но наилучшая из них помечена надписью «Лучшая». Для определения того, где должна пройти линия, необходимы лишь ближайшие к ней точки, они и называются опорными векторами.

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

Переход к ядру

Машины опорных векторов, равно как и другие линейные классификаторы, основанные на использовании скалярного произведения, часто можно улучшить за счет применения техники перехода к ядру (kernel

trick). Чтобы понять ее суть, рассмотрим, как изменилась бы задача, если бы нужно было прогнозировать не позицию, а пригодность игрока для любительской команды, в которой позиции часто меняются. Эта задача более интересна, так как разделение нелинейное. Вам не нужны ни слишком высокие, ни слишком быстрые игроки, поскольку другим было бы трудно играть с ними, но совсем уж низенькие или медлительные тоже ни к чему. На рис. 12.8 показано, как могла бы выглядеть ситуация; здесь кружок означает, что игрок подходит, а крестик – что не подходит.

Рис. 12.8. Диаграмма баскетболистов для любительской команды

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

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

Рис. 12.9. Баскетболисты в полиномиальном пространстве

не всегда возможно. Тут-то и приходит на помощь переход к ядру – вместо того чтобы трансформировать пространство, мы заменяем настоящее скалярное произведение функцией, возвращающей значение, которому скалярное произведение было бы равно после трансформации. Например, вместо выполнения описанной выше полиномиальной трансформации можно было заменить dotproduct(A,B)

на

dotproduct(A,B)**2

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

Использование библиотеки LIBSVM

Ранее мы ознакомились с библиотекой LIBSVM. С ее помощью можно обучить классификатор на некотором наборе данных (чтобы он находил разделяющую линию в трансформированном пространстве), а затем классифицировать новые наблюдения:

>>> from random import randint

>>> # Создать 200 случайных точек

>>> d1=[[randint(-20,20),randint(-20,20)] for i in range(200)]

>>> # Классифицировать точку как 1, если она лежит внутри круга, и как 0 –

>>> # если вне

>>> result=[(x**2+y**2)<144 and 1 or 0 for (x,y) in d1]

>>> from svm import *

>>> prob=svm_problem(result,d1) >>> param=svm_parameter(kernel_type=RBF) >>> m=svm_model(prob,param) >>> m.predict([2,2])

1.0

>>> m.predict([14,13])

0.0

>>> m.predict([-18,0])

0.0

Библиотека LIBSVM поддерживает много ядерных функций, и с ее помощью легко опробовать их все с различными параметрами, чтобы выяснить, какая лучше всего подходит для имеющегося набора данных. Чтобы протестировать модель, можно воспользоваться функцией cross_ validation, которая принимает параметр n и разбивает множество на n подмножеств. Затем каждое подмножество поочередно считается тестовым, а обучение производится на остальных подмножествах. Функция возвращает список ответов, который можно сравнить с исходным списком:

>>> guesses=cross_validation(prob,param,4)

>>> sum([abs(guesses[i]-result[i]) for i in range(len(guesses))])

28.0

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

Сильные и слабые стороны

Машина опорных векторов – очень мощный классификатор; после подбора правильных параметров она работает не хуже, а часто даже лучше любого другого из рассмотренных в книге классификаторов. Кроме того, после обучения классификация новых результатов производится очень быстро, поскольку требуется лишь определить, по какую сторону от разделителя оказалась точка. Преобразовав дискретные величины в числа, вы сможете заставить SVM работать с дискретными и числовыми данными одновременно.

Недостаток заключается в том, что оптимальная ядерная функция и ее параметры зависят от конкретного набора данных, так что всякий раз приходится подбирать их заново. Перебор возможных значений в цикле отчасти решает проблему, но для этого требуется иметь достаточно большой набор данных, чтобы результатам перекрестной проверки можно было доверять. В общем случае метод опорных векторов лучше приспособлен для таких задач, где доступен большой объем данных, тогда как другие методы, скажем деревья решений, дают интересную информацию уже на весьма скромных наборах данных. Как и нейронные сети, SVM представляет собой «черный ящик»; понять ход рассуждений здесь даже сложнее из-за трансформации в многомерное пространство. SVM может дать правильный ответ, но вы никогда не узнаете, как он получен.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100