Метод опорных векторов (SVM) | Data Science

Продолжаем цикл статей про Топ-10 data mining алгоритмов. Сегодня у нас на проводе интересный алгоритм дата майнинга - метод опорных векторов.

Метод опорных векторов (SVM - Support vector machines) использует гиперплоскость, чтобы классифицировать данные по 2 классам. На верхнем уровне SVM выполняет те же операции, что и C4.5, но с одним отличием - SVM не использует деревья решений.

Гипер-что? Гиперплоскость - это функция, например, уравнение для линии y = mx + b. На самом деле, для простой классификационной задачи с 2 параметрами гиперплоскость может быть линией.

Как оказалось-

SVM позволяет спроецировать ваши данные в пространство большей размерности. Когда данные спроецированы-

-SVM определяет лучшую гиперплоскость, которая делит данные на 2 класса.

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

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

Что представляют собой шары, стол и палочка? Шары представляют собой данные, а красный и синий цвета - два класса. Палка представляет собой самую простую гиперплоскость, то есть линию.

А как же самая крутая часть?

SVM самостоятельно определяет функцию гиперплоскости.

Что, если все гораздо сложнее? Верно, часто так и происходит. Если шары перемешаны друг с другом, то простая палка тут не поможет.

Вот что нужно сделать:

Быстро поднимите стол - шары взлетят в воздух. Пока шары находятся в воздухе и в правильных положениях, вы можете разделить красные и синие большим куском бумаги.

Вы можете подумать, что это жульничество:

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

Как SVM это делает? Использование нуль-пространства (ядра) матрицы дает нам отличный инструмент для работы в пространствах более высокой размерности. Большой лист бумаги по-прежнему называется гиперплоскостью, но теперь это функция плоскости, а не линии. Как заметил Ювал Мерхав (Yuval Merhav) - раз мы перешли в третье измерение, то гиперплоскость должна стать плоскостью.

Вот визуализация, которая неплохо помогает понять принцип работы SVM:

На Reddit есть 2 отличных треда по этой теме, на подфорумах ELI5 и ML.

Как шары на столе или в воздухе соотносятся с реальными данными? Шар на столе имеет местоположение, которое можно определить по координатам. Например, шар может отстоять на 20 см от левой грани стола и на 50 - от нижней. Другими словами, координаты (x,y) шара имеют значения (20,50) [правильнее было бы сказать: (50,20)]. Координаты x и y формируют двумерное измерение.

Вот что получается:

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

В результате:

SVM отображает эти параметры в высшее измерение, а затем находит гиперплоскость, чтобы разделить классы.

Термин «отступ» (margin) часто ассоциируется с SVM. Что это? Маржа гиперплоскости - это расстояние между гиперплоскостью и 2 ближайшими точками данных каждого класса. В примере с шарами и столом маржей называется расстояние между палкой и ближайшим красным и синим шариком.

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

Откуда SVM получил свое название? Гиперплоскость равноудалена от красного и синего шаров. Эти шары - точки данных, которые называются опорными векторами (support vectors), потому что они поддерживают гиперплоскость.

Требует ли этот метод обучения или он самообучающийся? Этот метод требует обучения. Чтобы показать SVM, что такое классы, используется набор данных - только после этого он оказывается способен классифицировать новые данные.

Почему именно SVM? SVM, наряду с C4.5 - это два метода, которые нужно попробовать в первую очередь. Но, согласно теореме No Free Lunch («бесплатных завтраков не бывает»), не существует универсального метода для решения задач классификации. Должен добавить, что слабыми сторонами этого метода являются необходимость выбора ядра и плохая интерпретируемость.

Где он используется? Есть множество реализаций SVM. Самые популярные - это scikit-learn, MATLAB и разумеется libsvm.

Источник

Ещё одно видео-объяснение метода опорных векторов

How SVM (Support Vector Machine) algorithm works

Тьюториал по методу опорных векторов можно найти здесь.

А вот ещё один гайд по SVM.

И, наконец, заметки по методу опорных векторов от знаменитого специалиста по машинному обучению из Стенфорда Andrew Ng.

Реализация метода опорных векторов в R

Общий вид (пакет svm {e1071})

## S3 method for class 'default':
svm((x, y = NULL, scale = TRUE, type = NULL, kernel =
"radial", degree = 3, gamma = if (is.vector(x)) 1 else 1 / ncol(x),
coef0 = 0, cost = 1, nu = 0.5,
class.weights = NULL, cachesize = 40, tolerance = 0.001, epsilon = 0.1,
shrinking = TRUE, cross = 0, probability = FALSE, fitted = TRUE,
..., subset, na.action = na.omit))

Краткую документацию о параметрах и аргументах можно посмотреть здесь.

Примеры с использованием Iris

data(iris) attach(iris) ## classification mode # default with factor response: model <- svm(Species ~ ., data = iris) # alternatively the traditional interface: x <- subset(iris, select = -Species) y <- Species model <- svm(x, y) print(model) summary(model) # test with train data pred <- predict(model, x) # (same as:) pred <- fitted(model) # Check accuracy: table(pred, y) # compute decision values and probabilities: pred <- predict(model, x, decision.values = TRUE) attr(pred, "decision.values")[1:4,] # visualize (classes by color, SV by crosses): plot(cmdscale(dist(iris[,-5])), col = as.integer(iris[,5]), pch = c("o","+")[1:150 %in% model$index + 1]) ## try regression mode on two dimensions # create data x <- seq(0.1, 5, by = 0.05) y <- log(x) + rnorm(x, sd = 0.2) # estimate model and predict input values m <- svm(x, y) new <- predict(m, x) # visualize plot(x, y) points(x, log(x), col = 2) points(x, new, col = 4) ## density-estimation # create 2-dim. normal with rho=0: X <- data.frame(a = rnorm(1000), b = rnorm(1000)) attach(X) # traditional way: m <- svm(X, gamma = 0.1) # formula interface: m <- svm(~., data = X, gamma = 0.1) # or: m <- svm(~ a + b, gamma = 0.1) # test: newdata <- data.frame(a = c(0, 4), b = c(0, 4)) predict (m, newdata) # visualize: plot(X, col = 1:1000 %in% m$index + 1, xlim = c(-5,5), ylim=c(-5,5)) points(newdata, pch = "+", col = 2, cex = 5) # weights: (example not particularly sensible) i2 <- iris levels(i2$Species)[3] <- "versicolor" summary(i2$Species) wts <- 100 / table(i2$Species) wts m <- svm(Species ~ ., data = i2, class.weights = wts)

Метод опорных векторов (SVM) в Питоне

Широко используемая библиотека для реализации данного метода в Python - scikit-learn (про неё мы упоминали выше, там есть ссылка на документацию). И реализация метода идёт по стандартному сценарию «загрузка библиотеки - создание объектов - подгонка модели (обучение) - прогноз». Рассмотрим примеры.

#Загрузка библиотеки from sklearn import svm #Предположим, что у нас есть X (predictor) и Y (target) для обучающей выборки, а также x_test(predictor) для test_dataset # Создаём SVM классификационный объект model = svm.svc(kernel='linear', c=1, gamma=1) # Используемые параметры можно варьировать, об этом позже. Далее нужна подгонка модели model.fit(X, y) model.score(X, y) #Прогноз predicted= model.predict(x_test)

Как настроить параметры в SVM?

Производительность модели зависит от используемых параметров в функции. Давайте рассмотрим полную структуру:

sklearn.svm.SVC(C=1.0, kernel='rbf', degree=3, gamma=0.0, coef0=0.0, shrinking=True, probability=False,tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=-1, random_state=None)

Важными параметрами с рассматриваемой точки зрения являются С, kernel и gamma.

Kernel (ядро) отвечается за гиперплоскость и может принимать значения -linear- (для линейной), -rbf-,-poly- (для нелинейной) и другие. Рассмотрим на примере:

import numpy as np import matplotlib.pyplot as plt from sklearn import svm, datasets # импортируем набор данных (например, возьмём тот же iris) iris = datasets.load_iris() X = iris.data[:, :2] # возьмём только первые 2 признака, чтобы проще воспринять вывод y = iris.target C = 1.0 # параметр регуляризации SVM svc = svm.SVC(kernel='linear', C=1,gamma=0).fit(X, y) # здесь мы взяли линейный kernel # создаём сетку для построения графика x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1 y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1 xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h)) plt.subplot(1, 1, 1) Z = svc.predict(np.c_[xx.ravel(), yy.ravel()]) Z = Z.reshape(xx.shape) plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8) plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired) plt.xlabel('Sepal length') # оси и название укажем на английском plt.ylabel('Sepal width') plt.xlim(xx.min(), xx.max()) plt.title('SVC with linear kernel') plt.show()

Вот примерно такое получаем (видите разделяющие линии - этот вид мы указали в kernel):

Теперь сменим параметр у kernel на rbf (расшифровывается как radial basis function):

svc = svm.SVC(kernel='rbf', C=1,gamma=0).fit(X, y)

Имеем теперь скруглённые границы:

Если признаков относительно много (>1000), то рекомендуется использовать linear lernel, т.к. более вероятно, что данные будут хорошо разделяться именно линиями в наборах большой размерности. При использовании параметра rbf необходимо провести кросс-валидацию параметров, чтобы избежать переобучения (over-fitting).

Теперь перейдём к гамме. Говоря простыми словами, gamma - это ширина rbf ядра (kernel). Она участвует в подгонке модели и может являться причиной переобучения. Рассмотрим поведение нашего графика при значениях gamma = 0, 10, 100:

svc = svm.SVC(kernel='rbf', C=1,gamma=0).fit(X, y)

Теперь про С. С - параметр регуляризации. Он в том числе контролирует соотношение между гладкой границей и корректной классификацией рассматриваемых точек.

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

Источник: datascientist.one

Комментарии: