Машинное обучение вики
Advertisement

Метод ближайших соседей (kNN - k Nearest Neighbours) - метод решения задач классификации и задач регрессии, основанный на поиске ближайших объектов с известными значения целевой переменной.

Идея[]

Метод основан на предположении о том, что близким объектам в признаковом пространстве соответствуют похожие метки.

Для нового объекта метод предполагает найти ближайшие к нему объекты и построить прогноз по их меткам.

Формальное описание[]

Классификация[]

.

Классификация в пограничном случае[]

Когда несколько классов имеют одинаковый ранг, можно сопоставить класс:

  • случайным образом
  • имеющий большую априорную вероятность
  • чей ближайший представитель ближе к
  • для которого среднее значение представителей этого класса среди ближайших соседей ближе
  • чей самый дальний представитель среди ближайших соседей ближе (т.е. класс представлен более компактно)

Регрессия[]

.

Параметры[]

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

Сложность[]

Сложность обучения - . Технически правильным ответом также является , так как требуется запоминать обучающую выборку.

Сложность прогнозирования - для каждого объекта. Если по фиксированной обучающей выборке требуется независимо сделать прогноз для объектов, сложность .

Особенности[]

  • + простой, лёгкий и интерпретируемый
  • + не требуется предобучения
  • + онлайновый
  • - высокая сложность одного прогноза
  • - проклятие размерности

Взвешенный учёт объектов[]

Пусть тренировочная выборка задается объектами

Упорядочим их относительно рассматриваемого объекта х .

Обозначим .

Обычный алгоритм можно записать с помощью C-дискриминантных функций: ,

где .

Тогда алгоритм для классификации записывается как

Тогда мы можем записать со взвешенным учетом объектов через С-дискриминантную функцию. Для случая с весами она принимает вид:.

Для классификации вид алгоритма не изменится. Для регрессии же вид будет следующим:

.

Где - вес(степень важности) -го соседа относительно , не возрастает по , положителен.

Примеры весов[]

Веса, зависящие от индекса:

,

.

Веса, зависящие от расстояния:


,

.

Оптимизации[]

Структурирование пространства признаков

Методы фильтрации обучающей выборки

Ссылки[]

Китов, слайды

И еще слайды Китова

Немного Соколова

Advertisement