Лабораторные работы по СМПР

Метрические алгоритмы

1. Алгоритм классификации "1NN":

Классифицируемый объект относим к тому классу, к которому принадлежит ближайший по заданной метрике "сосед" из выборки:

В реализованном методе выбрана евклидова метрика.
В качестве выборки был взят набор "Ирисы Фишера"
Карта классификации выглядит следующим образом:

2. Алгоритм классификации "kNN" k-ближайших соседей:

Все объекты выборки сортируются по удаленности от классифицируемого объекта. Выбираются k ближайших соседей. Классифицируемый объект относим к тому классу, который количественно преобладает среди выбраных k соседей:

Оптимальное количество соседей было выбрано по критерию скользящего контроля с исключением объектов по одному (leave-one-out) LOO. Дла каждого объекта обучающей выборки проводится классификация по k ближайшим соседям. Для данной реализации алгоритма график LOO выглядит следующим образом:

На графике видно, что LOO минимально при значении k=6. Карта классификации для алгоритма 6NN выглядит следующим образом:

3. Алгоритм классификации "kwNN" k-ближайших взвешенных соседей:

Недостатоком алгоритма kNN является то, что он относит классифицируемый объект к классу, количество представителей которого преобладает среди k соседей. Алгоритм kwNN подразумевает то, что каждый i-й сосед имеет определенную ценность и вносит свой вклад в классификацию объекта. Для определения веса подойдет какая-нибудь строго-убывающая последовательность, например Сам алгоритм выглядит так:

• отсортировать объекты выборки по удаленности от классифицируемого объекта
• выбрать k ближайших соседей
• каждому классу прибавить вес i-го соседа

Параметр q можно выбрать по критерию LOO.

Для алгоритма 6wNN график LOO выглядит так:

Хорошо видно, что LOO для алгоритма kwNN, где k = 6 и q = 0.05 значительно меньше чем для алгоритма kNN.

Карта классификации выглядит следующим образом:

Преимущетсво алгоритма kwnn над knn демонстрируется на следующих изображениях:

слева алгоритм kwnn, справа - knn

4. Алгоритм классификации "метод парзеновского окна":

Данный метод отличается от kwNN тем, что весовая функция зависит не от ранга соседа, а от расстояния от классифицируемого объекта до объекта выборки и параметра h(ширины окна) и функции ядра. Вокруг точки строится окрестность радиуса h и после выбирается тот класс, суммарный вес которого больше в этой окрестности.

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

Карта классификации выглядит следующим образом:

Карта для прямоугольного ядра:

Карта для треугольного ядра:

Карта для квартичного ядра:

Карта для ядра Епанечникова:

Карта для Гауссовского ядра:

6. Линии уровня нормального распределения":

N-мерным нормальным распределением будет называться распределение с плотностью:

где μ - математическое ожидание, а Σ - матрица ковариации

Если признаки некоррелированны, то матрица ковариации имеет диагональный вид, а линия плотности имеет форму эллипсоида

Если признаки коррелированы, то матрица не диагональна, а линии уровня имеют форму эллипсоида, оси которого повернуты относительно системы координат

Если признаки имеют одинаковую дисперсию, то эллипсоиды являются сферами

7. Подстановочный алгоритм (plug-in):

Суть алгоритма заключается в востановлении параметров нормального распределения μ и Σ по следующим формулам для каждого класса

Демонстрация будет проводиться на выборке из 100 элементов кадого класса.

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

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

В данном случае ковариационные матрицы равны и разделяющая поверхность больше походит на прямую

7. Наивный байесовский классификатор:

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

Карта классификации:

8. ADALINE:

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

Настройка линейного классификатора происходит методом минимизации эмпирического риска

Метод стохастического градиента - это итерационный процесс, на каждом шаге которого сдвигаемся в сторону, противоположную вектору градиента 𝑄′(𝑤, 𝑋ℓ)) до тех пор, пока вектор весов 𝑤 не перестанет изменяться, причем вычисления градиента производится не на всех объектах обучения, а выбирается случайный объект (отсюда и название метода «стохастический»), на основе которого и происходят вычисления. В зависимости от функции потерь, которая используется в функционале эмпирического риска, будем получать различные линейные алгоритмы классификации.

Схема обучения ADALINE соответствует схеме обучения линейного классификатора методом стохастического градиент

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

.

Производная берётся по w и равна .
Получили правило обновления весов на каждой итерации метода .

Пример работы:

9. Правило Хебба:

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

Пример работы: