Для чего используется kernel trick в svm

Support Vector Machine (SVM) and Kernels Trick

What is SVM?

Support Vector Machine (SVM) is a type of algorithm for classification and regression in supervised learning contained in machine learning, also known as support vector networks. SVM is more commonly used in classification problems rather than regression.

The SVM algorithm first introduced by Vapnik with colleagues Bernhard Bose and Isabelle Guyon in 1992 as a harmonious series of superior concepts in pattern recognition.

SVM works by using Structural Risk Minimization (SRM) principle which aims to obtain the best hyperplane line that divides data into two class in the input space.

At first SVM works linearly, but then SVM was developed again so that it can work non-linearly by looking for the hyperplane that is used to calculate the distance (margin) between data classes. In SVM application can be applied in linearly and non-linearly classification.

The SVM method is divided into two types based on its characteristics, namely linear SVM and non-linear SVM. Linear SVM is to classify data that can be separated linearly in two classes using soft margins. Linear classification is generally applied to datasets that have lower dimensions, that is, where the dataset has few features to classify. Meanwhile, Non-linear SVM is using the kernel concept in a high-dimensional workspace. The kernel concept is a function used by modifying the SVM algorithm to solve non-linear problems.

The SVM concept is called an attempt to find the best hyperplane that will divide data into two classes in the input space. The main objective of the training process on the SVM concept is to find the location of the hyperplane. SVM method uses the dot product function. The hyperplane is the line used to separate the dataset. Hyperplane can be a line in two dimensions and can be a flat plane in multiple planes. Illustration of determining the best hyperplane in the SVM algorithm. Following is the illustration of the best hyperplane in SVM.

The hyperplane can be obtained by measuring the hyperplane margin, which is the distance between the hyperplane and the closest point of each data class. The closest point that separates the hyperplane is called the support vector.

Linier SVM

Linear classification is generally used on datasets with lower dimensions. The lower dimension of a dataset means that it has fewer features to classify. Hyperplane in both images can be obtained by measuring the distance (margin) between the hyperplane and the closest point in each class.

Examples of cases belonging to the linear classification are to determine whether age and dietary factors affect human health. Where in this case there are only two features that are factors that affect human health, namely the age factor as feature x and thqe food factor as feature y. The following is a visualization of the linear SVM case.

Linear SVM is one of the working principles of SVM which is used for data that can be separated linearly as in the figure below.

So that according to a hyperplane equation is obtained in the linear SVM for positive class:
w. (xi) + b ≤ + 1

Information:
w = weight (weight vector)
x = matrix input value (feature)
b = bias

To calculate the largest margin value, it is done by optimizing the distance value between the hyperplane and the closest point in each class. Quadratic Programming (QP) is used as a formula to find the minimal point of an equation with equation constraints:
τ (w) = 1/2 ‖w‖ ^ 2

Langrage multipliers = αi which has a zero or positive value (αi≥0), where i = 1,2,…, l. So that the Langrange multiplier equation is modified and only contains αi as follows:
∑_ (i = 1) ^ l αi-1/2 ∑_ (i, j = 1) ^ l αi αj yi yj (xi), xj

With,
αi ≥ 0; (i = 1,2,…, l); ∑_ (i = 1) ^ l αi yi = 0

Most of the above calculations obtained a positive αi, where the data correlated with positive αi is called the support vector. So that the following equation is used to determine the results of the new data classification:
Class = sign f (x)

Non-Linier SVM

Non-Linear SVM is another working principle on SVM that is used for data that cannot be separated linearly because of its high dimensions. Non-linear classification is carried out using the kernel concept. The kernel concept in the non-linear case plays a role in determining the classification limits used as a model.

Non-Linear SVM applies the function of the kernel concept to a space that has high dimensions. What is meant by high dimension is that the dataset has more than two features to classify. For example, non-linear classification cases, namely factors that affect human health, consist of age factors, dietary factors, exercise factors, heredity, disease history and stress levels.

In this example, the kernel concept serves to determine the classification boundaries used as a model. Visualization of the non-Linear SVM case can be seen in the following Figure.

The accuracy of the model generated by the process in the SVM algorithm is very dependent on the parameters and kernel functions used. In the use of kernel functions in non-linear SVM is something that needs to be considered because the performance of SVM depends on the choice of kernel function.

Non-linier SVM is implemented in practice using a kernel, so it can separate data with the kernel function it called kernel trick.

The Kernel Trick

SVM can work well in non-linear data cases using kernel trick. The function of the kernel trick is to map the low-dimensional input space and tranforms into a higher dimensional space.

The RBF kernel is the most widely used kernel concept to solve the problem of classifying datasets that cannot be separated linearly. This kernel is known to have good performance with certain parameters, and the results of the training have a small error value compared to other kernels. The equation formula for the RBF kernel function is:

K(x,xi) = exp(-gamma * sum((x – xi^2))

The Gaussian kernel RBF has two parameters, namely gamma and sigma. The gamma parameter has a default value, which is γ = 1 / (2σ) ^ 2. When gamma is high, the points around the data are likely to be considered in the calculation. The sigma parameter is used to find the optimal value for each dataset.

In the RBF kernel function equation, ‖xi-x ‖ is the Euclidean Distance between x1 and x2 in two different feature spaces and σ (sigma) is the RBF kernel parameter that determines the kernel weight. In SVM, sigma parameters need to be adjusted to provide accurate classification results. The default value of the sigma parameter is σ = 1.

A Polynomial Kernel is more generalized form of the linear kernel. In machine learning, the polynomial kernel is a kernel function suitable for use in support vector machines (SVM) and other kernelizations, where the kernel represents the similarity of the training sample vectors in a feature space. Polynomial kernels are also suitable for solving classification problems on normalized training datasets. The equation for the polynomial kernel function is:

This kernel is used when data cannot be separated linearly.
The polynomial kernel has a degree parameter (d) which functions to find the optimal value in each dataset. The d parameter is the degree of the polynomial kernel function with a default value of d = 2. The greater the d value, the resulting system accuracy will be fluctuating and less stable. This happens because the higher the d parameter value, the more curved the resulting hyperplane line.

The concept of the sigmoid kernel is a development of an artificial neural network (ANN) with the equation for the kernel function is:

The Sigmoid kernel has been proposed theoretically for a Support Vector Machine (SVM) because it originates from a neural network, but until now it has not been widely used in practice.

The sigmoid kernel is widely applied in neural networks for classification processes. The SVM classification with the sigmoid kernel has a complex structure and it is difficult for humans to interpret and understand how the sigmoid kernel makes classification decisions. Interest in these kernels stems from their success in classifying with the neural netwotk and logistic regression, specific properties, linearity and cumulative distribution.

The sigmoid kernel is generally problematic or invalid because it is difficult to have positive parameters. The sigmoid function is now not widely used in research because it has a major drawback, namely that the output value range of the sigmoid function is not centered on zero. This causes the backpropagation process to occur which is not ideal, so that the weight of the ANN is not evenly distributed between positive and negative values ​​and tends to approach the extreme values ​​0 and 1.

A linear kernel can be used as normal dot product any two given observations. The equation for the kernel function is:

Finally, that’s it. Hopefully, this section helpful in understanding the concept of SVM and kernel trick for you guys. You may give some comments, thoughts, feedback or suggestions below. Keep learning and stay tuned for more!

Источник

Реализация SVM и ядра SVM с помощью Python Scikit-Learn

A support vector machine (SVM) – это тип алгоритма классификации управляемого машинного обучения. SVM были введены первоначально в 1960-х годах, а затем были усовершенствованы в 1990-х годах. Однако только сейчас они становятся чрезвычайно популярными благодаря своей способности достигать блестящих результатов. SVM реализуются уникальным образом по сравнению с другими алгоритмами машинного обучения.

В этой статье мы рассмотрим, что такое алгоритмы машин опорных векторов, краткую теорию, лежащую в основе машины опорных векторов, и их реализацию в библиотеке Scikit-Learn Python. Затем мы перейдем к продвинутой концепции SVM, известной как Kernel SVM, а также реализуем ее с помощью Scikit-Learn.

Простой SVM

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

Рис. 1: Множественные Границы Принятия Решений

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

Рис. 2: Граница принятия решения с опорными векторами

Существует сложная математика, связанная с поиском опорных векторов, вычислением маржи между границей принятия решения и опорными векторами и максимизацией этой маржи. В этом уроке мы не будем вдаваться в подробности математики, а скорее посмотрим, как SVM и Kernel SVM реализуются с помощью библиотеки Python Scikit-Learn.

Реализация SVM с помощью Scikit-Learn

Набор данных, который мы будем использовать в этом разделе, совпадает с тем, который мы использовали в разделе классификации учебника “Дерево решений”.

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

Импорт библиотек

Следующий скрипт импортирует необходимые библиотеки:

Импорт набора данных

Данные доступны для скачивания по следующей ссылке:

Данные доступны для скачивания по следующей ссылке:

Подробная информация о данных доступна по следующей ссылке:

Подробная информация о данных доступна по следующей ссылке:

Загрузите набор данных по ссылке Google Drive и сохраните его локально на своем компьютере. В этом примере CSV-файл для набора данных хранится в папке “Datasets” диска D на моем компьютере с Windows. Скрипт считывает файл с этого пути. Вы можете изменить путь к файлу для вашего компьютера соответствующим образом.

Для чтения данных из CSV-файла проще всего использовать метод read_csv библиотеки pandas. Следующий код считывает данные банкнот банка в фрейм данных pandas:

Исследовательский Анализ Данных

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

На выходе вы увидите (1372,5). Это означает, что набор данных банкнот содержит 1372 строки и 5 столбцов.

Чтобы получить представление о том, как на самом деле выглядит наш набор данных, выполните следующую команду:

Результат будет выглядеть следующим образом:

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

Предварительная обработка данных

Предварительная обработка данных включает в себя (1) Разделение данных на атрибуты и метки и (2) разделение данных на обучающие и тестовые наборы.

Чтобы разделить данные на атрибуты и метки, выполните следующий код:

Во второй строке в переменной y хранится только столбец class. В этот момент времени переменная X содержит атрибуты, а переменная y содержит соответствующие метки.

Для этого выполните следующий сценарий:

Обучение алгоритма

Делать Прогнозы

Оценка алгоритма

Вот код для поиска этих метрик:

Результаты

Результаты оценки следующие:

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

Ядро SVM

В предыдущем разделе мы видели, как простой алгоритм SVM может быть использован для нахождения границы решения для линейно разделимых данных. Однако в случае нелинейно разделимых данных, таких как показанные на рис. 3, прямая линия не может быть использована в качестве границы принятия решения.

Рис. 3: Нелинейно Разделяемые данные

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

В основном ядро SVM проецирует нелинейно разделяемые данные нижних измерений на линейно разделяемые данные более высоких измерений таким образом, что точки данных, принадлежащие к разным классам, распределяются по разным измерениям. Опять же, в этом есть сложная математика, но вам не нужно беспокоиться об этом, чтобы использовать SVM. Скорее всего, мы можем просто использовать библиотеку Scikit-Learn Python для реализации и использования SVM ядра.

Реализация SVM ядра с помощью Scikit-Learn

Реализация SVM ядра с помощью Scikit-Learn аналогична простой SVM. В этом разделе мы будем использовать знаменитый набор данных iris для прогнозирования категории, к которой относится растение, на основе четырех атрибутов: ширина чашелистика, длина чашелистика, ширина лепестка и длина лепестка.

Набор данных можно загрузить по следующей ссылке:

Набор данных можно загрузить по следующей ссылке:

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

Источник

Реализация SVM и Kernel SVM с помощью Scikit-Learn в Python

Машина опорных векторов (SVM) – это тип алгоритма классификации машинного обучения с учителем. SVM были впервые представлены в 1960-х годах, а затем были усовершенствованы в 1990-х годах. Однако только сейчас они становятся чрезвычайно популярными благодаря своей способности достигать блестящих результатов. SVM реализованы уникальным способом по сравнению с другими алгоритмами машинного обучения.

В этой статье мы увидим, что такое алгоритмы опорных векторных машин, краткую теорию опорных векторных машин и их реализацию в библиотеке Python Scikit-Learn. Затем мы перейдем к расширенной концепции SVM, известной как Kernel SVM, а также реализуем ее с помощью Scikit-Learn.

Простая SVM

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

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

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

За поиском векторов поддержки, вычислением разницы между границей решения и векторами поддержки и максимизацией этой разницы стоит сложная математика. В этом руководстве мы не будем вдаваться в детали математики, мы скорее увидим, как SVM и Kernel SVM реализуются через библиотеку Python Scikit-Learn.

Реализация SVM

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

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

Импорт библиотек

Следующий скрипт импортирует необходимые библиотеки:

Импорт набора данных

Загрузите набор данных на Google Диск и сохраните его локально на своем компьютере. В этом примере CSV-файл для набора данных хранится в папке «Datasets» на диске D на моем компьютере с Windows. Скрипт читает файл по этому пути. Вы можете соответствующим образом изменить путь к файлу на вашем компьютере.

Чтобы прочитать данные из файла CSV, самый простой способ – использовать метод read_csv библиотеки pandas. Следующий код считывает данные банкнот в фреймворке pandas:

Исследовательский анализ данных

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

В выводе вы увидите (1372,5). Это означает, что набор данных банкноты состоит из 1372 строк и 5 столбцов.

Чтобы понять, как на самом деле выглядит наш набор данных, выполните следующую команду:

Результат будет выглядеть так:

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

Предварительная обработка данных

Предварительная обработка данных включает в себя (1) разделение данных на атрибуты и метки и (2) разделение данных на наборы для обучения и тестирования.

Чтобы разделить данные на атрибуты и метки, выполните следующий код:

В первой строке приведенного выше сценария все столбцы фрейма данных bankdata сохраняются в переменной X, за исключением столбца «Класс», который является столбцом метки. Метод drop() удаляет этот столбец.

Во второй строке в переменной y сохраняется только столбец класса. На данный момент переменная X содержит атрибуты, а переменная y содержит соответствующие метки.

После того, как данные разделены на атрибуты и метки, последним шагом предварительной обработки является разделение данных на обучающие и тестовые наборы. К счастью, библиотека model_selection библиотеки Scikit-Learn содержит метод train_test_split, который позволяет нам легко разделять данные на обучающие и тестовые наборы.

Для этого выполните следующий скрипт:

Обучение алгоритму

Мы разделили данные на обучающие и тестовые наборы. Пришло время обучить нашу SVM на обучающих данных. Scikit-Learn содержит библиотеку svm, которая содержит встроенные классы для различных алгоритмов SVM. Поскольку мы собираемся выполнить задачу классификации, мы будем использовать класс классификатора опорных векторов, который записан как SVC в библиотеке svm Scikit-Learn. Этот класс принимает один параметр – тип ядра. Это очень важно. В случае простой SVM мы просто устанавливаем этот параметр как «linear», поскольку простые SVM могут классифицировать только линейно разделяемые данные. Мы увидим нелинейные ядра в следующем разделе.

Метод соответствия класса SVC вызывается для обучения алгоритма на обучающих данных, которые передаются в качестве параметра методу соответствия. Выполните следующий код для обучения алгоритма:

Прогнозы

Для прогнозирования используется метод прогнозирования класса SVC. Взгляните на следующий код:

Оценка алгоритма

Матрица неточностей, точность, отзыв и меры F1 являются наиболее часто используемыми метриками для задач классификации. Библиотека показателей Scikit-Learn содержит методы классификации_report и confusion_matrix, которые можно легко использовать для определения значений этих важных показателей.

Вот код для поиска этих показателей:

Полученные результаты

Результаты оценки следующие:

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

Ядро SVM

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

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

По сути, SVM ядра проецирует нелинейно разделяемые данные более низких измерений на линейно разделяемые данные более высоких измерений таким образом, что точки данных, принадлежащие разным классам, распределяются по разным измерениям. Опять же, здесь задействована сложная математика, но вам не нужно беспокоиться об этом, чтобы использовать SVM. Скорее мы можем просто использовать библиотеку Python Scikit-Learn для реализации и использования SVM ядра.

Реализация Kernel SVM

Реализация Kernel SVM с помощью Scikit-Learn аналогична простой SVM. В этом разделе мы будем использовать известный набор данных радужной оболочки глаза, чтобы предсказать категорию, к которой принадлежит растение, на основе четырех атрибутов: ширина чашелистика, длина чашелистика, ширина лепестка и длина лепестка.

Остальные шаги являются типичными шагами машинного обучения и требуют очень небольшого объяснения, пока мы не дойдем до той части, где мы обучаем нашу SVM ядра.

Импорт библиотек

Импорт набора данных

Предварительная обработка

Тестовый сплит

Обучение алгоритму

Для обучения SVM ядра мы используем тот же класс SVC библиотеки svm Scikit-Learn. Разница заключается в значении параметра ядра класса SVC. В случае простой SVM мы использовали «linear» в качестве значения параметра ядра. Однако для ядра SVM вы можете использовать гауссово, полиномиальное, сигмоидальное или вычислимое ядро. Мы их реализуем, чтобы увидеть, какое из них лучше подходит для нашей задачи.

1. Полиномиальное ядро

В случае полиномиального ядра вы также должны передать значение параметра степени класса SVC. Это в основном степень многочлена. Посмотрите, как мы можем использовать полиномиальное ядро для реализации SVM ядра:

Прогнозы

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

Для этого выполните следующий сценарий:

Оценка алгоритма

Как обычно, последний шаг любого алгоритма машинного обучения – это вычисление полиномиального ядра. Выполните следующий скрипт:

Выходные данные для ядра SVM с полиномиальным ядром выглядят следующим образом:

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

2. Ядро Гаусса

Посмотрите, как мы можем использовать полиномиальное ядро для реализации SVM ядра:

Чтобы использовать ядро Гаусса, вы должны указать ‘rbf’ в качестве значения для параметра ядра класса SVC.

Прогнозирование и оценка

Результат Kernel SVM с гауссовым ядром выглядит так:

3. Сигмовидное ядро

Наконец, давайте использовать сигмоидное ядро для реализации Kernel SVM. Взгляните на следующий скрипт:

Чтобы использовать сигмоидное ядро, вы должны указать «сигмоид» в качестве значения для параметра ядра класса SVC.

Прогнозирование и оценка

Выходные данные Kernel SVM с ядром Sigmoid выглядят следующим образом:

Сравнение производительности ядра

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

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

Заключение

В этой статье мы изучили, как простые, так и ядерные SVM. Мы изучили интуицию алгоритма SVM и то, как его можно реализовать с помощью библиотеки Scikit-Learn в Python. Мы также изучили различные типы ядер, которые можно использовать для реализации SVM ядра. Я предлагаю вам попробовать реализовать эти алгоритмы на реальных наборах данных, доступных на таких сайтах, как kaggle.com.

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

Источник