МЕТОД K -БЛИЖАЙШИХ СОСЕДЕЙ (K-NEAREST NEIGHBOR) Метод решения задачи классификации, который относит объекты к классу, которому принадлежит большинство из k его ближайших соседей в многомерном пространстве признаков. Это один из простейших алгоритмов обучения классификационных моделей. Число k – это количество соседних объектов в пространстве признаков, которое сравнивается с классифицируемым объектом.
МЕТОД K -БЛИЖАЙШИХ СОСЕДЕЙ
АЛГОРИТМ Для классификации каждого из объектов тестовой выборки необходимо последовательно выполнить следующие операции: Вычислить расстояние до каждого из объектов обучающей выборки, Отобрать k объектов обучающей выборки, расстояние до которых минимально, Класс классифицируемого объекта это класс, наиболее часто встречающийся среди k ближайших соседей.
ЭВКЛИДОВО РАССТОЯНИЕ
НОРМАЛИЗАЦИЯ
ПРОСТОЕ НЕВЗВЕШЕННОЕ ГОЛОСОВАНИЕ
ВЗВЕШЕННОЕ ГОЛОСОВАНИЕ
ПРИМЕНЕНИЕ kNN ДЛЯ РЕГРЕССИОННЫХ ЗАДАЧ
ПРИМЕР: ИРИСЫ ФИШЕРА 150 цветков трех классов: Два параметра: длина чашелистика и длина лепестка. Два новых цветка со следующими значениями длины чашелистика и лепестка: 5,3 и 1,6 ( цветок 1 ), 6,1 и 4,8 ( цветок 2 ). Iris SetosaIris VersicolourIris Virginica
ИРИСЫ ФИШЕРА: ДИАГРАММА РАЗМЕЩЕНИЯ КЛАССОВ
ИРИСЫ ФИШЕРА: ПРОСТОЕ НЕВЗВЕШЕННОЕ ГОЛОСОВАНИЕ Объект ЧашелистикЛепесток РасстояниеКласс Цветок 15,31,6-- A5,31,50,1Iris Setosa B5,21,50,14Iris Setosa C5,21,50,14Iris Setosa Класс цветка 1 : Iris Setosa
ИРИСЫ ФИШЕРА: ПРОСТОЕ НЕВЗВЕШЕННОЕ ГОЛОСОВАНИЕ Объект ЧашелистикЛепесток РасстояниеКласс Цветок 26,14,8-- A6,14,70,14Iris Versicolour B64,80,1Iris Virginica C6,24,80,1Iris Virginica Класс цветка 2 : Iris Virginica
ИРИСЫ ФИШЕРА: ВЗВЕШЕННОЕ ГОЛОСОВАНИЕ Класс цветка 2 : Iris Virginica
ДОСТОИНСТВА МЕТОДА kNN Программная реализация алгоритма относительно проста. Возможность модификации алгоритма. Алгоритм устойчив к аномальным выбросам. Возможность интерпретации результатов работы алгоритма.
НЕДОСТАТКИ МЕТОДА kNN Набор данных, используемый для алгоритма, должен быть репрезентативным. Необходимость хранить обучающую выборку целиком. В простейших случаях метрические алгоритмы имеют крайне бедный набор параметров, что исключает возможность настройки алгоритма по данным. Затраты в производительности велики, поскольку нам необходимо вычислить расстояния между каждым экземпляром и всеми пробными экземплярами.
ПРИМЕНЕНИЕ МЕТОДА kNN Распознавание текста, Сельское хозяйство, Финансы, Медицина, Обнаружение мошенничества, QSAR.
ПОСТРОЕНИЕ МОДЕЛИ В R preProc
ВЫБОРКА ПО РАСТВОРИМОСТИ РЕЗУЛЬТАТЫ
ВЫБОРКА ПО МУТАГЕННОСТИ РЕЗУЛЬТАТЫ 22