Введение
K ближайших соседей — это алгоритм обучения под наблюдением, основанный на предположении, что точки в окрестности (то есть ближайшие точки) принадлежат к одному и тому же классу.
Таким образом, учитывая положительное целое число k и тестовое наблюдение, KNN определяет k ближайших точек, а затем может делать выводы на основе этих ближайших целей.
Обратите внимание, что его можно использовать как для задач классификации, так и для регрессии. В частности, для задачи классификации он оценивает условную вероятность для класса j как долю точек в окрестности, целевое значение которых равно j:
где N0 представляет собой окрестность данного наблюдения. Он классифицирует наблюдение с классом, имеющим самую высокую условную вероятность. В шортах он считается классом большинства в округе!
С другой стороны, в случае регрессии задачи результатом будет просто среднее значение k ближайших целей.
Как выбрать правильное значение k
Выбор k всегда важен, фактически мы должны обратить внимание на два разных сценария:
- маленький k :поскольку вы находитесь очень близко к наблюдению, у вас будет низкая систематическая ошибка, но на вас может повлиять сильная дисперсия из-за наличия некоторых выбросов.
- большой k :если вы расширите свою окрестность, вы будете более устойчивы к выбросам (низкая дисперсия), но в конечном итоге вы получите более высокое смещение, потому что вы, вероятно, будете учитывать точки, которые не так близки.
Компромисс предвзятость-дисперсия всегда за углом!
Хорошо, отлично, но как мы можем выбрать его? К сожалению, абсолютного ответа нет, но мы должны попробовать разные значения.
Обычной практикой является построение эталонной метрики ошибки для различных значений k. Таким образом, вы сможете своими глазами увидеть, как ведет себя ваша модель и какой компромисс может быть выгодным.
Метрики расстояния
Чтобы количественно определить, насколько наблюдение x близко к y, нам нужно определить правильную метрику расстояния. Наиболее распространенные из них:
- manhattan:расстояние между двумя точками равно сумме абсолютных разностей их координат.
- евклидов: вероятно, наиболее часто используемый и определяется как квадратный корень из суммы квадратов разностей координат.
- чебышев: это максимальная абсолютная разница между всеми координатами. Его также называют верхним расстоянием.
Выполнение
Подводя итог, наивный алгоритм довольно прост:
- Для всех тестовых наблюдений вычислить расстояния между ними и всеми тренировочными
- Учитывайте только kближайших точек и сохраняйте их цели
- Если это проблема классификации, возьмите класс большинства, в противном случае возьмите среднее значение ближайших целей.
Полную реализацию можно найти здесь. Во-первых, я хотел бы сообщить скелет класса со всеми методами, которые нам нужно реализовать.
Метод __init__ будет использоваться для определения количества соседей, выбранной метрики и вспомогательного флага для понимания, имеем ли мы дело с проблемой регрессии или классификации. Теперь будем постепенно обогащать код до конца!
Для краткости здесь я сообщил только евклидово расстояние, но в репозитории github вы найдете все реализации.
Более того, поскольку мы можем выбирать из разных метрик, важно проверить, рассматриваем ли мы «действительную»:
Затем мы должны иметь возможность вычислить расстояние, поэтому давайте добавим два других метода: compute_distance()иeuclidean_distance(). Первый будет использоваться для вызова правильного метода расстояния на основе выбранного, а второй (а также те, о которых я не сообщил) будет отвечать за возврат фактического расстояния.
Здесь начинается самое интересное! Мы определили все методы контура, но теперь нам нужно определить чистый метод fit_predict(). Напомним, что в данном случае мы применяем подход грубой силы, но есть и более эффективные решения.
Итак, для каждой контрольной точки мы должны вычислить (и сохранить) все расстояния с тренировочными точками. Затем мы сортируем их и берем только kближайших (т. е. тех, для которых у нас есть наименьшее расстояние).
После этого мы запоминаем только их класс и, наконец, можем сделать наш прогноз как средний или мажоритарный класс для задачи регрессии или классификации соответственно.
Наконец, для полноты картины я сравнил производительность этого алгоритма с реализацией ScikitLearn на наборе данных Iris, и производительность оказалась одинаковой!
Выводы
Этот алгоритм довольно прост, но чрезвычайно эффективен, когда у нас есть умеренное количество функций и образцов. Это было довольно весело и сложно, и я надеюсь, что вы поняли все скрытые проходы!
Если у вас есть какие-либо комментарии, сомнения или отзывы, не стесняйтесь обращаться ко мне в LinkedIn, я буду более чем счастлив ответить! :D
