Практическое применение алгоритмов SVM в среде А+

Этот документ посвящен подробному описанию того, как применять алгоритмы опорных векторов (Support Vector Machines), реализованные на языке программирования А+, для решения конкретных практических задач. Краткая теория и детали реализации и применения содержатся в статье “Реализация алгоритмов опорных векторов (Support Vector Machines) методом градиентного спуска”.

Полный текст статьи Вы можете найти здесь (файл Word, zip - архив, 380 Кб). Файлы используемых программ (в виде текстовых файлов): Ascent.+, IO.+ и Plot.+.

1. Начало работы

Здесь описывается работа в операционной системе SuSE Linux c использованием редактора XEmacs.

Загружаем в рабочую область s-контекст (он нам понадобится для графического отображения результатов):

$load s

Затем загружаем файл Ascent.+ с указанием пути к нему:

$load ./Work/Ascent.+

< `ok

< /home/sasha/Work/IO.+

< `ok

< /home/sasha/Work/Plot.+

Все необходимые для работы программные файлы загружены в рабочую область А+. Обратите внимание, что файлы IO.+ и Plot.+ должны находится в одной директории с файлом Ascent.+. Вместо расширения .+ эти файлы также могут иметь расширение .txt.

2. Загрузка данных в рабочую область А+

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

Одним из самых простых способов загрузки данных является использование системной функции sys.readmat:

mûsys.readmat{f},

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

Для более удобного ввода данных предназначена программа IO.+. Рассмотрим работу функций ввода данных на примере выборки BUPA liver disorders из UCI Repository of Machine Learning Databases (http://www.ics.uci.edu/~mlearn/MLRepository.html). Эта выборка имеет 345 измерений по 6 признакам, 7-й столбец является столбцом классификации. Структура файла – CSV(Comma Separated Values). Разделителем между элементами здесь является запятая, между строками – возврат каретки. Принадлежность измерения к тому или иному классу обозначается метками 1 или 2 (это т.н. бинарная классификация). ОБРАТИТЕ ВНИМАНИЕ! Для работы алгоритма необходимо, чтобы метками класса являлись +1 и -1, поэтому в любом другом случае необходимо перейти к такому представлению.

Рассмотрим сначала ввод этих данных с помощью функции sys.readmat:

mûsys.readmat './Work/bupa_data.txt'

Переменная m является символьной матрицей размерности

Òm

347 23

Первые и последние строки полученной матрицы выглядят следующим образом:

Для дальнейшей работы необходимо заменить знак возврата каретки на пробел и перейти от символьной матрицы к числовой нужной размерности.

Теперь рассмотрим ввод данных с помощью функций, содержащихся в файле IO.+. Основной функцией является input{file;var;ccol}, где file – символьная строка содержащая путь и имя файла, var – имя переменной, в которую будет производиться присвоение (символьный вектор), ccol – номер столбца классификации (символьный вектор). Последний аргумент указывает на то, какой из столбцов матрицы данных является классификационным, затем проверяется, содержит ли этот столбец только +1 и -1 в качестве элементов, в противном случае программа предлагает перейти к этому виду. Допустимыми значениями аргумента ccol являются none (матрица данных не содержит столбца классификации), last (последний столбец - классификационный) или номер любого столбца. Рассмотрим теперь подробно:

input {'./Work/bupa_data.txt';'S1';'last'}

Программа предлагает заменить элементы столбца классификации:

Use replace function for target column

ã[error] : stop

* classûreplace {class;('1';'2');('1';'¢1')}

* û

В качестве ответа выдается размерность получившейся матрицы:

345 7

Аналогичным образом в некоторых случаях может возникнуть необходимость в ручном определении числа столбцов или переходе от символьных значений признаков к числовым (с заменой переменной class на sizeY и vec соответственно). В процессе ввода обычный знак минус “-” автоматически заменяется на “высокий” минус “¢” , используемый в А+.

Данные, взятые в качестве примера, являются ненормированными. Можно либо использовать уже отнормированные данные, загружаемые из файлов, либо же провести нормировку уже в среде А+. Например, нормировка признаков в диапазоне от 0 до 1 осуществляется в А+ следующими строками (с предварительным разделением данных на собственно столбцы признаков и классификационный столбец):

targetû¢1Ù@1 S1

data1û¢1Õ@1 S1

Òdata1

345 6

Собственно нормировка:

dataû(data1-@1 Ä/data1)ß@1 (Ó/data1)-Ä/data1

Òdata

345 6

Ó/data

1 1 1 1 1 1

Ä/data

0 0 0 0 0 0

Sûdata,@1 target

ÒS

345 7

На этом этап ввода данных закончен и все готово к применению собственно алгоритмов опорных векторов.

3. Применение алгоритмов SVM

Рассмотрим применение на примере этой же выборки BUPA liver disorders. В ней 145 измерений относится к первому классу (метка 1) и 200 – ко второму. Используемые переменные:

S – вся выборка с последним столбцом классификации;

data – только выборка данных;

target – столбец классификации.

Основной функцией программы является Ascent. Она имеет следующий формат вызова:

(alpha1;y1;sv;b;crit;ind;iter;margin)û(Ker Ascent Mode) P,

где

Mode – вложенный вектор, первый элемент – символ, указывающий на вид алгоритма (`hard,`soft_1 или `soft_2, что соответствует алгоритму с жесткой границей, мягкой границей с 1-нормой или 2-нормой соответственно), второй – номер используемого критерия остановки (1,2 или 3). По умолчанию все остальные значения интерпретируются, как `hard и 1;

Ker – функция ядра, может принимать значения Linear, Poly, RBF для линейного, полиномиального и гауссовского ядер соответственно;

P – вложенный вектор из S, kp и C:

S – исходная матрица обучающих данных (по строкам), последний столбец – вектор классификации;

kp – параметр выбранного ядра;

C – параметр алгоритма.

Результатами обучения алгоритма являются:

alpha1 – вектор множителей Лагранжа для опорных векторов,

y1 – классификационный вектор для опорных векторов,

sv – матрица опорных векторов (по строкам),

b – ненормированное смещение,

crit – вектор значений выбранного критерия остановки,

ind – индексы вхождения опорных векторов в исходных данных,

iter – число затраченных итераций,

margin – вектор значений геометрической ширины границы.

Полученное решающее правило имеет вид:

«b+(alpha1«y1)+.«Ker {sv;ôX;kp},

где X – классифицируемые измерения (в виде вектор-строк). В результате получаем метку класса, к которому отнесено данное измерение (+1 или -1).

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

Рассмотрим в качестве примера применение линейного алгоритма SVM с мягкой границей с 1-нормой, С = 5, второй критерий остановки, в качестве обучающей используем всю выборку:

(alpha1;y1;sv;b;crit;ind;iter;margin)û(Linear Ascent (`soft_1;2))(S;0;5)

¢1.707086868

iter

2438

¢1Ùmargin

0.09404624073

Число опорных векторов:

#sv

284

(82.3% от объема выборки, прим.)

Общее число ошибок:

+/(,target)¨«b+(alpha1«y1)+.«Linear{sv;ôdata;0}

105

(30.44%, прим.)

Число ошибок первого (первый класс назван вторым) и второго рода:

+/2=(,target)-«b+(alpha1«y1)+.«Linear{sv;ôdata;0}

(62.1%, прим.)

+/¢2=(,target)-«b+(alpha1«y1)+.«Linear{sv;ôdata;0}

(7.5%, прим.)

Число неграничных (unbounded) опорных векторов:

+/alpha1¨5

(2.3% от объема выборки, прим.)

4. Графическое представление полученных результатов

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

Для любых исходных данных представляет интерес графическое представление поведения критерия остановки и изменения ширины границы на протяжении работы алгоритма.

Для нашего примера:

show `crit is `graph

show `margin is `graph

Рассмотрим графическое представление разделяющей линии для случая двумерных данных. Исходные данные имеют вид (последний столбец - вектор классификации):

1 1 1

1 2 1

2 1 1

2 2 1

3 3 ¢1

3 4 ¢1

4 3 ¢1

4 4 ¢1

Применение функции Ascent с параметрами Ker = Linear (линейное ядро), Mode = (`;) (SVM с жесткой границей, первый критерий остановки), kp = 0 (условный параметр для линейного ядра), C = 10 (параметр алгоритма):

(alpha1;y1;sv;b;crit;ind;iter;margin)û(Linear Ascent (`;))(S;0;10)

Вектор множителей Лагранжа для опорных векторов (SVs):

alpha1

1.46860115 1.312369012

Вектор меток класса для SVs:

1 ¢1

Матрица опорных векторов (по строкам):

2 2

3 3

Ненормированное значение смещения (порога) b:

4.999428417

Вектор значений критерия остановки:

Òcrit

305

Индексы вхождения SVs в исходной матрице точек (номера строк, начиная с 0):

ind

3 4

Число затраченных итераций (число выполнений цикла while):

iter

305

Вектор значений ширины границы (margin):

Òmargin

305

Конечное значение ширины границы:

¢1Ùmargin

0.7071741493

Исходные данные без вектора классификации – data.

Для отображения разделяющей линии предназначена программа Plot.+, основной функцией которой является Solution. Формат вызова функции Solution:

(ans1;ans2)û(Ker Solution F) R,

где аргумент Ker – такой же, как и для функции Ascent, F – решающее правило (символьная строка), R – вложенный вектор S и kp, где S – матрица данных без столбца классификации, kp – то же, что и в функции Ascent. Результатом являются две матрицы, содержащие координаты точек разделяющей линии при переходе от класса с меткой +1 к классу с меткой -1 (ans1) и наоборот (ans2). Обратите внимание, что все аргументы решающего правила должны быть определены в рабочей области заранее.

Пример применения функции Solution для получения координат точек разделяющей поверхности, F = '«b+(alpha1«y1)+.«Ker {sv;ôX;kp}':

(ans1;ans2)û(Linear Solution '«b+(alpha1«y1)+.«Ker {sv;ôX;kp}')(data;0)

Координаты нижней границы (переход от метки +1 к метке -1, движение в положительном направлении оси Y), вектор-строки:

Òans1

100 2

Координаты верхней границы:

Òans2

Применение решающего правила:

«b+(alpha1«y1)+.«Linear {sv;ôdata;0}

1 1 1 1 ¢1 ¢1 ¢1 ¢1

«b+(alpha1«y1)+.«Linear {sv;2.51 2.51;0}

¢1

«b+(alpha1«y1)+.«Linear {sv;2.49 2.49;0}

Графическое представление:

data1û4Ùdata

data2û4Õdata

gû`data1`data2`ans1

show `g is `graph

`data1 has (`style;`scatter;`symbol;`circlefilled)

`.data1

`data2 has (`style;`scatter;`symbol;`circlefilled)

`.data2

`ans1 has (`linecolor;`blue)

`.ans1