Для начала приведу просто определение, которые мы можете найти в большинстве ресурсов и статей по теме:
Функция d: X *X -> R называется метрикой на множестве X, если для любых x, y, z в X выполняются условия на фото.
Первое условие включает неотрицательность и невырожденность, второе - симметрию, третье - неравенство треугольника. Функция, удовлетворяющая всем условиям кроме невырожденности (то есть допускающая d(x, y) = 0 при x != y), называется псевдометрикой. Нарушение неравенства треугольника превращает функцию в premetric или dissimilarity и делает неприменимыми алгоритмы, опирающиеся на свойство треугольника - например, метрические индексы, BallTree, и большинство теоретических гарантий persistent homology.
🔵Нормы L_p
Семейство расстояний L_p для векторов x, y -> R^n определяется как показано на втором фото. При p = 1 получается манхэттенское расстояние, при p = 2 - евклидово, при p -> inf - расстояние Чебышёва d_inf(x, y) = max_i |x_i - y_i|. Условие p >= 1 необходимо для выполнения неравенства треугольника; при 0 < p < 10 функция метрикой не является.
import numpy as np
def lp_distance(x, y, p):
if np.isinf(p):
return np.max(np.abs(x - y))
return np.sum(np.abs(x - y) p) (1 / p)
x = np.array([1.0, 2.0, 3.0])
y = np.array([4.0, 0.0, 1.0])
for p in [1, 2, np.inf]:
print(f"L{p}: {lp_distance(x, y, p):.4f}")
Выбор p определяет чувствительность к выбросам и устойчивость к шуму. L_1 менее чувствителен к большим компонентам разности и используеться в задачах с тяжёлыми tails распределений, например в robust regression. L_2 удобен для гауссова шума и связан с максимальным правдоподобием при нормальной модели ошибок. L_inf выделяет максимальное покомпонентное отклонение и используется в кейсах с ограничениями на худший случай, в частности в adversarial robustness.
Влияние выбора p на соседей можно промоделировать таким кодом.
from sklearn.neighbors import NearestNeighbors
np.random.seed(0)
X = np.random.randn(1000, 50)
query = np.random.randn(1, 50)
for p in [1, 2, np.inf]:
metric = 'chebyshev' if np.isinf(p) else 'minkowski'
kwargs = {} if np.isinf(p) else {'p': p}
nn = NearestNeighbors(n_neighbors=5, metric=metric, **kwargs).fit(X)
dist, idx = nn.kneighbors(query)
print(f"L{p}: nearest indices = {idx[0]}")
В высокоразмерных пространствах различия между метриками усиливаются: при n -> inf соотношение между максимальным и минимальным расстоянием от фиксированной точки до случайных наблюдений сжимается, причём для меньших p эффект менее выражен (Aggarwal, Hinneburg, Keim, 2001). Это даёт основания предпочитать L_1 или дробные L_p в задачах с десятками и сотнями измерений.
#TDA101