ПРИМЕЧАНИЕ. все рисунки в этом посте были сделаны автором с использованием LATEX, numpy и matplotlib .

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

Евклидово расстояние

Первая и наиболее распространенная формула расстояния — это евклидово расстояние.

Это вычисляется путем нахождения разницы между элементами в списке x и элементами в списке y, вычисления суммы этих различий и извлечения квадратного корня из суммы. Это находит линейное расстояние между двумя точками.

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

Манхэттен Расстояние

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

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

Вы можете более четко увидеть разницу между евклидовым расстоянием и манхэттенским расстоянием на изображении ниже. Формула справа напоминает расстояние от одной улицы до другой в городской сетке, отсюда и название «манхэттенское» расстояние.

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

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

Расстояние Минковского

Эта формула расстояния уникальна тем, что включает как евклидово, так и манхэттенское расстояния как частные случаи, когда p=2 и p=1 соответственно. Использование этой формулы расстояния позволяет нам управлять одной переменной, p, чтобы получить любую формулу.

Обратите внимание, что функция sklearn.neighbors.KNeighborsClassifier использует расстояние Минковского в качестве метрики по умолчанию, скорее всего, из-за ее универсальности. См. scipy.spatial.distance полный список показателей расстояния.

Как правило, более высокое значение p может придавать большее значение большим различиям между значениями функций, в то время как более низкое значение p может отдавать приоритет различиям отдельных функций.

Косинус сходства

Эта метрика чрезвычайно полезна для определения сходства векторов. Если вы посещали уроки линейной алгебры, вы наверняка видели эту формулу раньше.

Это уравнение вычисляет cos(θ), где θ представляет собой угол между двумя ненулевыми векторами признаков. Он включает в себя скалярное произведение двух векторов в числителе, а затем деление его на длину каждого вектора.

В учебнике по линейной алгебре вы можете увидеть похожее уравнение, которое выглядит так:

Это та же самая формула, где вектор x и вектор y представляют два вектора признаков, а значения в знаменателе представляют длины каждого вектора.

Эта формула измеряет сходство двух векторов. Ортогональные векторы, то есть векторы, где cos⁡(θ)≊ 0, не имеют подобия, а векторы, где cos(θ) ≊ 1, имеют наибольшее сходство. Это можно увидеть графически, как показано ниже:

Важно помнить, что диапазон косинуса находится между -1 и 1. Значение -1 указывает на точное различие, 0 указывает на отсутствие сходства, а 1 указывает на точное сходство.

В этом примере сходство по косинусу между двумя векторами составляет -0,7642, что указывает на то, что векторы x и y сильно различаются.

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

На среднем графике, поскольку два вектора кратны друг другу и имеют одинаковое направление, они падают на одну и ту же прямую в 2D-пространстве. Это означает, что они по существу являются одним и тем же вектором, только с разной величиной. Это очевидно, потому что у нас есть 2x = 2y на среднем графике.

Наконец, на третьем графике эти два вектора настолько непохожи, насколько это возможно, с подобием -1. Как и на среднем графике, эти векторы действительно кратны друг другу, поскольку у нас есть -1x= -1y. Ключевое отличие состоит в том, что отрицательное значение изменяет направление вектора y.

Расстояние Хэмминга

Если бы мы хотели классифицировать двоичный вывод, мы хотели бы использовать эту метрику. Функция δ — это дельта-функция Кронекера, которая возвращает 1 или True, если соответствующие элементы x и y равны, и 0, или False, если они не равны. Он измеряет количество позиций, в которых различаются два вектора.

Метрика расстояния Хэмминга обычно используется в различных областях, таких как биология и информатика, которые имеют дело со сравнением последовательности значений. В биологии это можно использовать для чего-то вроде сравнения последовательностей молекул ДНК или РНК.