Манхэттенское расстояние
Манхэттенское расстояние (также известное как расстояние городских кварталов, метрика L1, расстояние такси) — это метрика, используемая в геометрии, математическом анализе, информатике и теории информации для измерения расстояния между двумя точками в пространстве. В отличие от евклидова расстояния (метрики L2), которое вычисляется как кратчайшая прямая линия между точками, манхэттенское расстояние определяется как сумма абсолютных разностей их координат. Название происходит от планировки районов Манхэттена в Нью-Йорке, где улицы и проспекты образуют прямоугольную сетку, и кратчайший путь между двумя точками по такой сетке (без диагональных перемещений) равен именно манхэттенскому расстоянию.
Определение и математическая формулировка
Для двух точек в n-мерном пространстве с координатами \( A = (x_1, x_2, \dots, x_n) \) и \( B = (y_1, y_2, \dots, y_n) \) манхэттенское расстояние \( d_1(A, B) \) вычисляется по формуле:
\[ d_1(A, B) = \sum_{i=1}^{n} |x_i - y_i| \]
где \( |x_i - y_i| \) — абсолютная разность координат по i-му измерению. В двумерном случае (на плоскости) формула упрощается до:
\[ d_1(A, B) = |x_1 - y_1| + |x_2 - y_2| \]
Свойства метрики
Манхэттенское расстояние удовлетворяет всем аксиомам метрики:
- Неотрицательность: \( d_1(A, B) \geq 0 \), причём равенство нулю достигается только при \( A = B \).
- Симметричность: \( d_1(A, B) = d_1(B, A) \).
- Неравенство треугольника: \( d_1(A, B) \leq d_1(A, C) + d_1(C, B) \) для любой точки C.
В отличие от евклидова расстояния, манхэттенское расстояние является выпуклой функцией и не инвариантно относительно вращения системы координат: поворот сетки может изменить значение расстояния между двумя точками.
История и происхождение названия
Термин «манхэттенское расстояние» вошёл в обиход в середине XX века, хотя сама концепция использовалась и ранее. Название связано с планировкой Манхэттена, одного из пяти боро Нью-Йорка, где улицы (streets) и проспекты (avenues) образуют почти идеальную прямоугольную сетку. В такой системе кратчайший путь между двумя точками, который можно пройти пешком или на автомобиле (без диагональных улиц), равен сумме горизонтальных и вертикальных перемещений. Альтернативные названия — «метрика такси» (taxicab metric) и «расстояние L1» — подчёркивают аналогию с движением такси по прямоугольной сети улиц.
Математически метрика была формализована в рамках линейной алгебры и функционального анализа как частный случай Lp-пространств (норм Lp). В частности, манхэттенское расстояние соответствует норме L1, в то время как евклидово — норме L2.
Сравнение с евклидовым расстоянием
Манхэттенское расстояние и евклидово расстояние (метрика L2) являются двумя наиболее распространёнными способами измерения расстояния в пространстве. Основные различия:
| Характеристика | Манхэттенское расстояние (L1) | Евклидово расстояние (L2) | ||||
|---|---|---|---|---|---|---|
| Формула для двух точек (2D) | \( | x_1 - y_1 | + | x_2 - y_2 | \) | \( \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2} \) |
| Геометрическая интерпретация | Длина пути по прямоугольной сетке | Длина прямой линии | ||||
| Чувствительность к выбросам | Меньше (линейная зависимость) | Больше (квадратичная зависимость) | ||||
| Инвариантность к вращению | Нет | Да | ||||
| Вычислительная сложность | Простое сложение | Требуется извлечение квадратного корня |
В некоторых задачах манхэттенское расстояние может быть более адекватной мерой, чем евклидово, особенно когда движение ограничено прямоугольной сеткой или когда требуется устойчивость к выбросам.
Применение
В информатике и машинном обучении
Манхэттенское расстояние широко используется в задачах классификации и кластеризации, особенно в алгоритмах, основанных на метриках:
- K-ближайших соседей (KNN): при работе с данными, где признаки имеют разную природу или когда важно учитывать все измерения равномерно (без усиления влияния больших отклонений).
- K-средних (K-means): в некоторых вариантах кластеризации для данных с прямоугольной структурой.
- Метод опорных векторов (SVM): в ядрах, основанных на L1-норме.
- Обнаружение выбросов: метрика L1 менее чувствительна к экстремальным значениям, что делает её полезной для робастных методов.
В обработке изображений и компьютерном зрении
В задачах сравнения изображений, поиска похожих паттернов и распознавания образов манхэттенское расстояние часто используется как мера сходства между векторами признаков (например, гистограммами цветов или текстур). Оно эффективно для бинарных изображений и при работе с пиксельными сетками.
В теории информации и статистике
В статистике манхэттенское расстояние применяется как альтернатива евклидову расстоянию для анализа данных с большим количеством выбросов или в задачах, где важна робастность. В теории информации оно связано с расстоянием Хэмминга для двоичных строк: расстояние Хэмминга — это частный случай манхэттенского расстояния для двоичных векторов (количество несовпадающих битов).
В транспортном моделировании и логистике
При моделировании движения в городах с прямоугольной сеткой улиц (например, в Нью-Йорке, Чикаго, Мельбурне) манхэттенское расстояние используется для оценки кратчайших маршрутов и времени в пути. В задачах маршрутизации (например, в задаче коммивояжёра) метрика L1 может быть более реалистичной, чем евклидово расстояние.
В геометрии и физике
В некоторых областях физики, особенно в теории относительности и квантовой механике, манхэттенское расстояние встречается как частный случай метрики пространства-времени (например, в пространствах Минковского). В комбинаторной геометрии оно используется для изучения свойств многогранников и решёток.
Примеры и иллюстрация
Рассмотрим две точки на плоскости: \( A(1, 2) \) и \( B(4, 6) \).
- Евклидово расстояние: \( \sqrt{(4-1)^2 + (6-2)^2} = \sqrt{9 + 16} = \sqrt{25} = 5 \).
- Манхэттенское расстояние: \( |4-1| + |6-2| = 3 + 4 = 7 \).
Таким образом, манхэттенское расстояние всегда больше или равно евклидову, за исключением случаев, когда точки лежат на одной горизонтальной или вертикальной линии (тогда расстояния совпадают). В общем случае, для двух точек в n-мерном пространстве выполняется неравенство: \( d_1 \geq d_2 \).
Связь с другими метриками
Манхэттенское расстояние является частным случаем Lp-метрик, где p = 1. Другие важные случаи:
- L2-метрика (евклидово расстояние) — p = 2.
- L∞-метрика (чебышёвское расстояние) — p → ∞, где расстояние равно максимальной абсолютной разности координат.
- L0-метрика — расстояние, равное количеству ненулевых разностей (часто используется для разреженных данных).
Все Lp-метрики являются частными случаями норм в функциональном анализе.
Критика и ограничения
Несмотря на широкое применение, манхэттенское расстояние имеет ряд недостатков:
- Неинвариантность к вращению: поворот системы координат может существенно изменить значения расстояний, что делает метрику непригодной для задач, где ориентация не фиксирована.
- Зависимость от масштаба: если признаки имеют разные единицы измерения, манхэттенское расстояние может быть искажено без предварительной нормализации данных.
- Неравномерность: для точек, расположенных под углом 45 градусов к осям, манхэттенское расстояние может быть значительно больше евклидова, что в некоторых контекстах не соответствует интуитивному представлению о «близости».
Источники
- Деза, М., Деза, Е. (2012). Энциклопедия расстояний. Springer.
- Кратцер, К. (2009). Введение в метрические пространства. Wiley.
- Рассел, С., Норвиг, П. (2010). Искусственный интеллект: современный подход. Prentice Hall.
- Харт, П., Нильссон, Н., Рафаэль, Б. (1968). «Формальное основание для эвристического определения минимальных путей». IEEE Transactions on Systems Science and Cybernetics.
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →