Презентация на тему «Метод k-ближайших соседей»

Метод k-ближайших соседей

к.х.н. Варламова Екатерина Владимировна

Метод k-ближайших соседей (K-nearest neighbor)

2

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

Метод k-ближайших соседей

3

Алгоритм

4

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

Эвклидово расстояние

5

Нормализация

6

Простое невзвешенное голосование

7

Простое невзвешенное голосование

8

Взвешенное голосование

9

Взвешенное голосование

10

Применение knn для регрессионных задач

11

Пример: Ирисы фишера

12

150 цветков трех классов: Два параметра: длина чашелистика и длина лепестка. Два новых цветка со следующими значениями длины чашелистика и лепестка: 5,3 и 1,6 (цветок 1), 6,1 и 4,8 (цветок 2).

Iris Setosa

Iris Versicolour

Iris Virginica

Ирисы фишера: Диаграмма размещения классов

13

Ирисы фишера: Простое невзвешенное голосование

14

Класс цветка 1: Iris Setosa

Объект

Чашелистик

Лепесток

Расстояние

Класс

Цветок 1

5,3

1,6

-

-

A

5,3

1,5

0,1

Iris Setosa

B

5,2

1,5

0,14

Iris Setosa

C

5,2

1,5

0,14

Iris Setosa

Ирисы фишера: Простое невзвешенное голосование

15

Класс цветка 2: Iris Virginica

Объект

Чашелистик

Лепесток

Расстояние

Класс

Цветок 2

6,1

4,8

-

-

A

6,1

4,7

0,14

Iris Versicolour

B

6

4,8

0,1

Iris Virginica

C

6,2

4,8

0,1

Iris Virginica

Ирисы фишера: взвешенное голосование

16

Класс цветка 2: Iris Virginica

Достоинства метода knn

17

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

Недостатки метода knn

18

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

Применение метода knn

19

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

Построение модели в R

20

preProc <- preProcess(x, method=c("scale", "center")) x <- predict(preProc, x) set.seed(42) cv <- createFolds(y, 5, returnTrain=TRUE) trControl <- trainControl(method="LGOCV", index=cv, savePredictions=TRUE, preProcOptions=NULL) knnGrid <- data.frame(k=seq(1,20,2)) m.knn <- train(x, y, method="knn", trControl=trControl, tuneGrid=knnGrid)

Выборка по растворимости Результаты

21

Выборка по мутагенности Результаты

22

22