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

Расстояние Минковского — это обобщённая метрика, используемая в математике и компьютерных науках для измерения расстояния между двумя точками в многомерном пространстве. Оно является частью семейства метрик, известных как метрики Минковского или L_p-метрики, и включает в себя такие известные метрики, как евклидово расстояние и расстояние Манхэттена. Эта метрика названа в честь немецкого математика Германа Минковского, который внёс значительный вклад в геометрию и теорию относительности.

Формула расстояния Минковского

Для двух точек $P = (x_{1}, x_{2}, \dots, x_{n})$ и $Q = (y_{1}, y_{2}, \dots, y_{n})$ в $n$ -мерном пространстве расстояние Минковского определяется как:

$D (P, Q) = {(\sum_{i = 1}^{n} ∣ x_{i} - y_{i} ∣^{p})}^{1 / p},$

где:

$p$ — параметр, который определяет тип метрики (обычно $p \geq 1$ ).
$∣ x_{i} - y_{i} ∣$ — абсолютное значение разности координат по каждой оси.

Особые случаи расстояния Минковского

При $p = 1$ : Расстояние Манхэттена (L1-метрика):

$D (P, Q) = \sum_{i = 1}^{n} ∣ x_{i} - y_{i} ∣ .$

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

При $p = 2$ Евклидово расстояние (L2-метрика):

$D (P, Q) = \sqrt{\sum_{i = 1}^{n} (x_{i} - y_{i})^{}}$

Это стандартное расстояние, которое мы используем в повседневной жизни для измерения длины прямой линии между двумя точками.

При $p \to \infty$ : Чебышёвское расстояние (L∞-метрика):

$D (P, Q) = \max_{i} ∣ x_{i} - y_{i} ∣ .$

Это расстояние соответствует максимальной разности координат по всем осям.

Свойства расстояния Минковского

Неотрицательность:

$D (P, Q) \geq 0,$

причём $D (P, Q) = 0$ только если $P = Q$ .
Симметричность:

$D (P, Q) = D (Q, P) .$

Неравенство треугольника:

$D (P, R) \leq D (P, Q) + D (Q, R) .$

Зависимость от параметра $p$ :
- Чем больше $p$ , тем больше вес придаётся наибольшей разности координат.
- При $p = 1$ все координаты вносят равный вклад.
- При $p \to \infty$ учитывается только максимальная разность.

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

Машинное обучение:
- Расстояние Минковского используется в алгоритмах классификации и кластеризации, таких как k-ближайших соседей (k-NN), для измерения сходства между объектами.
Компьютерное зрение:
- В задачах обработки изображений расстояние Минковского может использоваться для сравнения пикселей или векторов признаков.
Оптимизация:
- В задачах оптимизации расстояние Минковского помогает измерять отклонения от целевых значений.
Геоинформационные системы (ГИС):
- Расстояние Минковского применяется для анализа пространственных данных, например, для измерения расстояний между объектами на карте.

Пример вычисления

Рассмотрим две точки в двумерном пространстве:

$P = (1, 3)$ ,
$Q = (4, 7)$ .

Расстояние Манхэттена ( $p = 1$ ):

$D (P, Q) = ∣ 1 - 4 ∣ + ∣ 3 - 7 ∣ = 3 + 4 = 7.$

Евклидово расстояние ( $p = 2$ ):

$D (P, Q) = \sqrt{(1 - 4)^{2} + (3 - 7)^{2}} = \sqrt{9 + 16} = 5.$

Чебышёвское расстояние ( $p \to \infty$ ):

$D (P, Q) = \max (∣ 1 - 4 ∣, ∣ 3 - 7 ∣) = \max (3, 4) = 4.$

Преимущества и недостатки

Преимущества:

Гибкость: выбор параметра $p$ позволяет адаптировать метрику под конкретную задачу.
Простота вычисления.

Недостатки:

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

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

Нашли ошибку? Сообщите нам!
Материал распространяется по лицензии CC0 1.0 Universal

17.04.2025
AMD FidelityFX