Скажи мне, кто твои соседи, и я скажу тебе, кто ты.

Если вы общались с специалистом по данным или изучаете науку о данных, скорее всего, вы слышали об алгоритме k -Nearest Neighbours (или k -NN , для краткости).

Когда я впервые услышал этот термин на сетевом мероприятии, мне в голову пришло следующее изображение:

К сожалению, алгоритм k -NN предлагает мало информации о ваших соседях, если, конечно, вы не думаете о них как о точках данных.

Что такое алгоритм k -NN?

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

Чтобы сделать это более конкретным, представьте, что вы главный специалист по обработке данных в новой мобильной сети под названием Mobile, Inc. У вас есть набор данных, содержащий информацию о ваших пользователях. Среди других переменных вы знаете возраст своих пользователей, доход (в тысячах долларов США в год) и их план подписки (базовый, плюс или премиум). Первые 10 строк вашего набора данных отображаются ниже:

Один из способов визуализировать, как две числовые переменные (возраст и доход) связаны с категориальной переменной (планом подписки), - это использовать диаграмму разброса с цветовой кодировкой, как показано ниже.

Несмотря на то, что количество точек данных все еще очень мало, кажется, что в данных проявляются некоторые закономерности: есть регионы или кластеры одного и того же класса.

Предположим, у нас появился новый потенциальный клиент, которому 36 лет и который зарабатывает 124 000 долларов США в год. Используя алгоритм k -NN, мы хотим спрогнозировать ее план подписки на основе ее ближайших соседей.

Если мы установим k = 1, алгоритм 1 -NN найдет единственного ближайшего соседа. Поскольку этот сосед является покупателем «Плюс» (синий), алгоритм предсказывает, что новый покупатель также станет покупателем «Плюс».

Однако это было бы плохим выбором для k. Мы ясно видим, что этот сосед «Плюс» является исключением в этом регионе. Фактически, большинство его соседей являются клиентами категории «Премиум». Что, если вместо выбора k = 1 мы установим k = 6?

Используя алгоритм 6 -NN, мы обнаруживаем, что 5 из 6 ближайших соседей принадлежат к классу «Премиум». В результате наш алгоритм машинного обучения предсказывает, что новый клиент выберет план «Премиум».

В считанные секунды торговые представители Mobile, Inc приступили к реализации маркетингового плана, чтобы подчеркнуть преимущества плана Premium для нового клиента. Через несколько минут покупатель становится еще одной красной точкой на диаграмме рассеяния.

Я мог это предвидеть. Действительно ли нам нужен алгоритм машинного обучения?

В предыдущем примере вы могли подумать: Я мог бы угадать план подписки клиента, взглянув на диаграмму разброса! Неужели для этого нужен алгоритм машинного обучения?

Однако представьте, что вместо двух переменных для каждого клиента у вас есть более десятка соответствующих функций (количество детей, кредитный рейтинг, род занятий, почтовый индекс, пол и т. Д.). И вместо нескольких десятков точек данных у вас было несколько тысяч точек данных!

Человеку больше не будет легко выполнять эту задачу по классификации.

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

Однако для приличного компьютера выполнение алгоритма классификации k -NN на наборе данных среднего размера похоже на прогулку по киберпарку.

Как на самом деле работает алгоритм k-NN?

К настоящему моменту вы, вероятно, имеете интуитивное представление о том, что делает k- NN. Но как это работает? Алгоритм k -NN сводится к двум простым концепциям:

  • Евклидово расстояние между двумя точками в n-мерном пространстве
  • статистический режим в наборе значений

Чтобы понять это, давайте кратко остановимся на школьной алгебре. Предположим, что у нас есть две точки на координатной плоскости. Мы можем рассчитать расстояние между этими точками, используя формулу Евклидова расстояния:

Эта формула может быть интуитивно выведена путем визуализации прямоугольного треугольника и применения теоремы Пифагора для определения длины гипотенузы. Например, для точек A и B мы можем вычислить расстояние между ними, как показано ниже:

В более общем смысле, для любых двух точек p и q в n-мерном пространстве мы можем вычислить расстояние между ними, используя следующую формулу (где i представляет собой i -й объект для точек p и q).

Как только алгоритм k -NN находит ближайших k соседей, он выбирает режим (значение, которое появляется наиболее часто) в этом наборе значений. В таблице ниже показано, как алгоритм 6 -NN записывает расстояния до 6 ближайших точек.

Прелесть k -NN в том, что он основан на двух концепциях, которые остаются актуальными в n-мерном пространстве: евклидово расстояние и статистический режим. Следовательно, теоретически мы можем применить алгоритм k -NN к набору данных с x количеством функций.

Однако, учитывая вычислительные ограничения, k -NN становится менее эффективным по мере увеличения количества функций в наборе данных (это выходит за рамки данной статьи, но если вы хотите узнать больше о об этом, дайте мне знать в комментариях ниже).

Как выбрать наилучшее значение k?

Как вы узнали ранее, выбор k может резко изменить предсказательную силу алгоритма. Если k слишком мало, алгоритм классификации, вероятно, будет плохим, поскольку он будет чувствителен к шуму (выбросы в данных).

С другой стороны, если значение k слишком велико, интересующая область будет слишком большой, чтобы найти детализированные шаблоны в данных.

Очевидно, есть золотая середина. Но как его найти?

Короткий ответ заключается в том, что мы можем запустить k -NN с разными значениями для k и проверить, насколько хорошо он предсказывает подмножество данных. Поскольку у нас есть метки для этого подмножества, мы можем сравнить k -NN прогнозы с фактическими значениями в нашем наборе данных. Пробуя разные значения для k, мы можем выбрать алгоритм k -NN с наивысшим уровнем точности.

Похоже, что k = 7 - лучший выбор для прогнозирования планов подписки клиентов на основе текущего набора пользовательских данных.

Резюме

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

Два ключевых вывода из этой статьи:

  • k -NN - это очень мощный алгоритм классификации, который может помочь делать прогнозы относительно новых данных на основе их сходства с существующими точками данных.
  • выбор k имеет большое значение: ваш алгоритм k- NN должен находить детализированные шаблоны в данных, но не быть слишком чувствительным к шуму

Независимо от того, насколько мы заняты, возможно, нам следует не забывать о дружбе с нашими ближайшими соседями. Они могут дать нам полезную информацию о том, кто мы есть.

Спасибо, что прочитали. В этих статьях я пытаюсь объяснить концепции науки о данных доступным и интуитивно понятным способом.

Если эта статья была для вас полезной или у вас есть предложения по новым темам, оставьте комментарий ниже!