K-ближайшие соседи (KNN) — один из самых простых для понимания алгоритмов машинного обучения. Как и многие другие алгоритмы, KNN был вдохновлен человеческим мышлением.
Представьте на мгновение, что вы держите в руке синюю стеклянную бутылку, которую никогда раньше не видели. Вы поскальзываетесь и внезапно роняете его примерно с 5 футов на бетонный пол внизу. Прежде чем бутылка упадет на землю, вы с полной уверенностью знаете одно: бутылка разобьется. Как вы узнали об этом, хотя никогда раньше не видели «эту» бутылку? В прошлом вы сталкивались с тем, что большинство типов стекла легко ломаются. Ваш разум мгновенно установил связь между прошлым опытом и этим инцидентом, когда бутылка выскользнула из вашей руки.
Если бы бутылка упала с высоты менее 2 футов на поросшую травой землю снаружи, можно было бы предположить, что стекло не разобьется. Ваш разум сравнивает ситуацию с аналогичным прошлым опытом и выбирает состояние, которое возникло чаще всего, что также происходит в KNN.
Как работает КНН?
Это довольно просто. Алгоритм проверяет ближайшее число «k» соседей вокруг данного объекта и предсказывает наиболее повторяющийся класс из этого выбора. Взгляните на изображение ниже. Положим к = 4.
Здесь разные виды цветков ириса нанесены в зависимости от длины и ширины их чашелистиков. Наблюдая за сюжетом, можно увидеть четкое различие между видами по этим двум признакам. Теперь нам дан новый цветок (фиолетовая точка на графике), и нам нужно определить его вид.
K-NN ищет ближайшие точки данных. Если K = 4, ближайшие 4 проблемы идентифицируются на основе их расстояния до новой точки, как показано, и максимальный возникающий класс дается в качестве прогноза. В данном случае 2 из 4 сортов сорта virginica и по одному сорта Setosa и Versicolor. Таким образом, новая точка предсказывается как цветок, относящийся к виду Virginica.
Примечание. В отличие от большинства алгоритмов машинного обучения, которые выполняют обучающую работу при предоставлении обучающих данных, KNN просто сохраняет эти данные, не выполняя фактического обучения. Только на этапе прогнозирования выполняются вычисления для определения ближайших соседей и определения класса. Из-за этого KNN называют «ленивым учеником».
Как рассчитывается расстояние?
Существует несколько методов расчета расстояния. Евклидово расстояние является популярным методом, хотя также можно использовать методы расстояния Манхэттена, Минковского и Хэмминга. Формула для расчета евклидова расстояния приведена ниже.
Давайте теперь рассмотрим наш пример с радужной оболочкой и применим формулу Евклида для вычисления расстояния между двумя точками.
Евклидово расстояние между новой точкой (фиолетовая) и ближайшим образцом для Versicolor (красная) можно рассчитать, как показано ниже.
Как найти наилучшее значение k?
Лучшее значение K не может быть определено заранее и требует проб и ошибок. В каждом конкретном случае это зависит от используемых данных.
Как правило, более высокие значения K приводят к менее четким границам между классами, но также уменьшают влияние шума на классификацию. Наличие больших значений K также делает вычисления более интенсивными и может увеличить погрешность.
Некоторые способы выбора K состоят в том, чтобы выбрать нечетное число, если количество классов (n) равно 2, или установить k=sqrt(n). Хорошее значение K также можно определить с помощью перекрестной проверки.
Плюсы и минусы алгоритма KNN
KNN весьма выгоден, поскольку его легко реализовать и он не требует построения модели, настройки нескольких параметров или дополнительных предположений. Его можно хорошо использовать с классификацией, регрессией, а также для поиска. Однако по мере увеличения объема данных этот алгоритм становится значительно медленнее.
Если вы нашли этот пост полезным, рассмотрите возможность подписаться на меня и присоединиться к среде. Ваше членство поддерживает меня и других писателей, которых вы читаете напрямую.
Спасибо за чтение! Увидимся в будущем посте.
