Метрика Минковского

Метрика Минковского — это семейство метрик (функций расстояния) в многомерном пространстве, обобщающее такие известные метрики, как евклидова, манхэттенская и метрика Чебышёва. Названа в честь немецкого математика Германа Минковского, который внёс значительный вклад в геометрию чисел и теорию относительности. Метрика Минковского определяется в пространстве Rⁿ, где каждая точка представляет собой кортеж из n действительных чисел.

Определение

Метрика Минковского порядка p (где p — действительное число, p ≥ 1) между двумя точками x = (x₁, x₂, ..., xₙ) и y = (y₁, y₂, ..., yₙ) в n-мерном пространстве задаётся формулой:

\[ d_p(x, y) = \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{1/p} \]

Здесь p — параметр, определяющий тип метрики. При p = 1 получается метрика Манхэттена (или метрика городских кварталов), при p = 2 — классическая евклидова метрика, а при p → ∞ — метрика Чебышёва (или метрика максимума). Для p < 1 данное выражение не удовлетворяет аксиоме треугольника и, следовательно, не является метрикой.

Свойства

Метрика Минковского обладает следующими основными свойствами, характерными для всех метрик:

1. Неотрицательность: d_p(x, y) ≥ 0 для всех x, y, причём d_p(x, y) = 0 тогда и только тогда, когда x = y.
2. Симметричность: d_p(x, y) = d_p(y, x) для всех x, y.
3. Неравенство треугольника: d_p(x, z) ≤ d_p(x, y) + d_p(y, z) для всех x, y, z. Это свойство выполняется для p ≥ 1, что доказывается с помощью неравенства Минковского.

Кроме того, метрика Минковского является однородной: для любого скаляра λ ≥ 0 выполняется d_p(λx, λy) = λ·d_p(x, y). Она также инвариантна относительно параллельного переноса: d_p(x + a, y + a) = d_p(x, y).

Частные случаи

Метрика Манхэттена (p = 1)

При p = 1 метрика принимает вид суммы модулей разностей координат:

\[ d_1(x, y) = \sum_{i=1}^{n} |x_i - y_i| \]

Эта метрика называется «манхэттенской» из-за аналогии с расстоянием, которое необходимо пройти по прямоугольной сетке улиц (как в районе Манхэттен в Нью-Йорке). Она широко используется в задачах машинного обучения, особенно в алгоритмах k-ближайших соседей и при анализе данных с категориальными признаками.

Евклидова метрика (p = 2)

При p = 2 метрика совпадает с обычным евклидовым расстоянием:

\[ d_2(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2} \]

Это наиболее распространённая метрика, используемая в геометрии, физике, компьютерной графике и многих других областях. Она соответствует интуитивному представлению о расстоянии в трёхмерном пространстве.

Метрика Чебышёва (p → ∞)

При стремлении p к бесконечности метрика Минковского переходит в метрику Чебышёва (или метрику максимума):

\[ d_{\infty}(x, y) = \max_{i} |x_i - y_i| \]

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

Применение

Метрика Минковского находит применение в различных областях науки и техники:

• Машинное обучение и анализ данных: используется как функция расстояния в алгоритмах кластеризации (k-средних, DBSCAN), классификации (k-ближайших соседей) и при построении рекомендательных систем. Выбор параметра p позволяет адаптировать метрику под конкретную задачу и тип данных.
• Геоинформационные системы: применяется для расчёта расстояний между точками на карте, особенно при использовании прямоугольной сетки координат (например, в городских планировках).
• Компьютерное зрение и обработка изображений: метрика Минковского используется для сравнения гистограмм, текстур и других признаков изображений.
• Теория информации: при анализе расстояний между вероятностными распределениями и в задачах сжатия данных.
• Логистика и транспорт: метрика Манхэттена применяется для оптимизации маршрутов в городах с прямоугольной планировкой улиц.

Обобщения и родственные понятия

Метрика Минковского является частным случаем более общего понятия — нормы Минковского в векторном пространстве. Норма Минковского порядка p определяется как:

\[ \|x\|_p = \left( \sum_{i=1}^{n} |x_i|^p \right)^{1/p} \]

Для p ≥ 1 эта норма удовлетворяет всем аксиомам нормы. Пространство Rⁿ с нормой Минковского называется Lp-пространством.

Существует также метрика Минковского для p < 1, которая не является метрикой в строгом смысле, но иногда используется в задачах, где требуется подчеркнуть различия по отдельным координатам (например, в анализе выбросов). Однако в таких случаях неравенство треугольника нарушается, и расстояние может не соответствовать интуитивному представлению.

Критика и ограничения

Несмотря на широкое применение, метрика Минковского имеет ряд ограничений:

• Чувствительность к масштабу: метрика не инвариантна к изменению масштаба координат. Если признаки имеют разные единицы измерения (например, килограммы и метры), необходимо предварительное нормирование данных.
• Корреляция признаков: метрика предполагает независимость координат, что не всегда выполняется на практике. В таких случаях более подходящими могут быть метрики, учитывающие корреляцию, например, махаланобисово расстояние.
• Выбор параметра p: оптимальное значение p зависит от конкретной задачи и требует эмпирического подбора. Неправильный выбор может привести к ухудшению качества моделей машинного обучения.
• Вычислительная сложность: при больших размерностях пространства и больших значениях p вычисление метрики может быть ресурсоёмким.

Источники

1. Минковский Г. «Геометрия чисел» (Geometrie der Zahlen). — Лейпциг, 1896.
2. Колмогоров А. Н., Фомин С. В. «Элементы теории функций и функционального анализа». — М.: Наука, 1976.
3. Hastie T., Tibshirani R., Friedman J. «The Elements of Statistical Learning». — Springer, 2009.
4. Deza M. M., Deza E. «Encyclopedia of Distances». — Springer, 2009.