В этой серии статей мы подробно разберем алгоритм K-Nearest Neighbor (KNN).
Начнем с того, что K-NN классифицируется как алгоритм машинного обучения с учителем. Для тех, кто хочет понять алгоритмы машинного обучения с учителем и без учителя, здесь является ссылкой на то же самое. Короче говоря, контролируемое обучение имеет определенную метку класса.
Прежде чем углубляться в детали KNN, давайте сначала поймем, что мы имеем в виду под проблемой классификации и проблемой регрессии.
Рассмотрим пример набора данных titanic. Набор данных Titanic считается «привет, мир!» вид проекта в области машинного обучения. Задача этой задачи - определить, выжил ли человек в катастрофе по определенным признакам. Итак, учитывая множество характеристик, таких как возраст человека, пол, билет в какой класс он / она купил и т. Д., Мы должны предсказать, выжил человек или нет. Например, Если человек женского пола или ребенок, вероятность его выживания выше. Итак, мы должны классифицировать одну из двух меток класса, то есть выжить или нет. Поскольку существует два возможных исхода, ее также называют проблемой 2-классной классификации или бинарной классификацией. Теперь предположим, что вы только что прокатились на такси с помощью одного из онлайн-агрегаторов кабин. Когда поездка будет завершена, вам будет предложено оценить свое впечатление от поездки. Эта рейтинговая система помогает компании понять работу водителя, ответственного за поездку. Итак, есть (скажем) 5 возможных вариантов выбора: очень плохо, плохо, средне, хорошо, очень хорошо. Основываясь на вашем опыте, вы выбираете один из 5 предложенных вариантов. Здесь вы пытаетесь отнести свой опыт поездки к одной из 5 возможных категорий. Поскольку возможное количество категорий больше двух, это называется классификацией по нескольким классам. .
Давайте перейдем к пониманию, что такое проблема регрессии? В двух приведенных выше примерах моя метка класса имела конечный набор значений, таких как «выжил» или «нет» или оценка впечатления от поездки среди 5 возможных меток класса. Но в случае регресса у нас нет этого конечного набора меток классов. Позвольте мне пояснить это на примере. Вам даются такие характеристики, как вес, возраст, пол некоторых учеников, и цель состоит в том, чтобы предсказать рост учеников. В этом случае рост учеников не принадлежит конечному набору метки класса. Это число с действительным значением, которое может принимать любое значение в определенном диапазоне. Такие проблемы, в которых метка класса является действительным числом, называется проблемой регрессии.
KNN можно использовать как для классификации, так и для решения задач регрессии. Сначала мы поймем KNN с точки зрения классификации.
Рассмотрим пример ниже.
У нас есть набор красных и зеленых точек. Мы замечаем, что красные точки принадлежат метке класса A, а зеленые - метке класса B. С учетом этих точек мы получили еще одну точку желтого цвета. Задача / цель состоит в том, чтобы классифицировать эту желтую точку, также называемую точкой запроса, в одну из меток класса.
Определение KNN в терминах непрофессионала:
KNN расшифровывается как K ближайших соседей. Где K - целое число, указывающее количество ближайших соседей, которые необходимо учитывать. K может принимать любое целочисленное значение от 1 до n, где n = no. точек в наборе данных. Итак, мы рассматриваем K ближайших соседей точек запроса и проводим большинство голосов по этим ближайшим соседям. Метка класса с наибольшим количеством голосов назначается точке запроса.
Вернемся к приведенному выше примеру. Предположим, у меня K = 3, поэтому мы должны идентифицировать 3 ближайших соседа точки запроса (как мы определяем этих соседей, мы увидим в следующем разделе этой статьи). Когда мы рассматриваем 3 ближайших соседа, из 3 ближайших соседей 2 принадлежат классу B, а 1 принадлежит классу A. Исходя из большинства, мы классифицируем точку запроса как класс B. Теперь давайте рассмотрим K = 7. Значит, вместо 3 ближайших соседей, теперь мы будем рассматривать 7 ближайших соседей. Когда мы рассматриваем 7-NN, мы получаем 4 ближайших соседа, принадлежащих классу A, и 3 ближайших соседа, принадлежащих классу B. Теперь, следуя классу большинства, мы классифицируем точку запроса как класс A.
Вы можете задаться вопросом, что только что произошло? Когда мы выбрали K = 3, мы классифицировали точку запроса как класс B, а когда мы выбрали K = 7, метка класса изменилась на A. Это так сбивает с толку. Как мне определить, какое значение «K» выбрать?
Не волнуйтесь, скоро мы ответим на все ваши вопросы. А пока я просто хочу убедиться, что вы понимаете интуицию, лежащую в основе KNN. Скоро мы поймем, как определять ближайших соседей, а также как выбирать наилучшее значение «K».
Как найти ближайших соседей?
Один простой и прямой ответ на поставленный выше вопрос - вычислить расстояние между точками. Мы разберемся с четырьмя основными мерами расстояния, чтобы рассчитать расстояние между точками.
1. Евклидово расстояние
Рассмотрим пример ниже:
Точка A = (X_21, Y_21)
Точка B = (X_22, Y_22)
d = длина кратчайшей линии от точки A до B = евклидово расстояние между точками A и B.
Евклидово расстояние - это квадратный корень из суммы квадратов расстояния между двумя точками. Это также известно как норма L2. В следующих статьях мы увидим, что такое нормы L1 и L2.
2. Манхэттенское расстояние
Манхэттенское расстояние - это сумма абсолютных значений разностей между двумя точками.
3. Расстояние Хэмминга
В основном используется при обработке текста, когда у нас есть двоичный или логический вектор. Проще говоря, он сообщает нам, совпадают ли две категориальные переменные или нет. Рассмотрим ниже, например. где расстояние Хэмминга между:
4. Расстояние Минковского.
Расстояние Минковского используется для нахождения сходства расстояний между двумя точками. Когда p = 1, оно становится манхэттенским расстоянием, а когда p = 2, оно становится евклидовым расстоянием.
Это методы измерения расстояния, которые в основном используются для расчета расстояния между точками для определения ближайших соседей.
Вы можете спросить, а есть ли что-нибудь еще? Я имею в виду, что я понимаю часть измерения расстояния, но есть ли другой способ понять ближайших соседей? И ответ ДА!
До сих пор мы измеряли ближайших соседей с точки зрения расстояния, как насчет того, чтобы измерить их с точки зрения «угла»?
Разрешите познакомить вас с концепцией «косинусоподобия и косинусного расстояния»
Косинусное подобие рассматривает угол (θ) между двумя точками и равен cos (θ). . Рассмотрим пример ниже:
A и B - две точки данных, а θ - угол между ними. Можно с уверенностью сказать, что если расстояние между двумя точками увеличивается, угол между ними будет увеличиваться, а по мере увеличения угла между ними cos (θ) уменьшается. означает, что их косинусоидальность уменьшается.
Рассмотрим пример ниже:
У нас есть 3 вектора - x1, x2 и x3.
Косинус-подобие (x1, x2) = cos (θ)
Косинус-подобие (x1, x3) = 1 (поскольку, θ = 0 и cos ( 0) = 1)
Косинусное расстояние (x1, x2) = 1 - cos (θ)
Косинусное расстояние между (x1, x3) = 1–1 = 0 (поскольку cos (θ) = 1
Итак, наблюдения, с точки зрения евклидова расстояния, ясно показывают, что расстояние d13 ›d12
Но при сравнении косинусного расстояния cos-dist (x1, x3) ‹cos-dist (x1, x2)
Из приведенных выше наблюдений довольно ясно, что cos-sim или cos-dist используют угол между векторами, а не геометрическое расстояние.
Есть ли связь между евклидовым подобием и косинусоподобием?
да. Есть, и это дается следующим образом:
Евклидово расстояние в квадрате между x1 и x2 = 2 * (1 - cos (θ))
Чтобы понять подробное математическое доказательство того же самого, перейдите по этой ссылке.
В заключение, мы хорошо разобрались в K-NN. Мы также рассмотрели различные меры расстояния и косинусоидальность, чтобы понять, как вычисляются ближайшие соседи и как они связаны.
Дополнительные материалы для чтения:
Изучая эту тему, я наткнулся на блестящую статью Криса Эммери. Я бы порекомендовал вам один раз посетить эту ссылку
В следующей статье мы разберемся с ограничениями KNN, случаями его сбоев и узнаем, как выбрать правильное значение «K».
А пока желаю вам удачи!
