2.1. Непривычная длина

Часто (я бы даже сказал, постоянно) при работе с данными нам нужно понимать масштаб
Например, считать длину вектора (тот же k-means на этом и построен)

Как посчитать длину вектора?
Вроде в школе нам давали теорему Пифагора:
$\begin{array}{l}v = (v^1, v^2) \\ ||v|| = \sqrt{(v^1)^2 + (v^2)^2}\end{array}$

Назовём такой способ измерения длины евклидовым
Вроде всё работает, но насколько это универсально?
Представим город, где мы можем ходить только в четырёх направлениях (как в манхэттене), как бы, по клеткам:

Тогда, чтобы измерить длину нашего пути от одной точки до другой, нужно посчитать расстояние по одной координате и сложить с другой:
$||v||_m = |v^1| + |v^2|$

Назовём такой способ подсчёта длины манхэттенским

Чуть более абстрактный пример
Часто нужно ограничить какой-то набор чисел не по сумме его координат или по Пифагору, а просто по максимальной координате
Это чаще всего нужно, чтобы не допускать критических отклонений каждой координаты, которые важнее, чем общие отклонения
Так вот, это тоже можно назвать своего рода подсчётом длины:
$||v||_{max} = max(|v^1|, |v^2|)$

Что объединяет все эти способы?
И вообще, как обобщить наше интуитивное понятие длины?

Ну, во первых, оно должно быть неотрицательным 
Всё же, обычно у нас не бывает что-то длиной -3 метра
Причём, длина равная нулю если и только если сам вектор просто нулевой

Во вторых, нужна согласованность с масштабированием
Мы не просто так вводили умножение на числа, нам бы очень хотелось, чтобы умножив вектор на 2 мы получим в 2 раза более длинный вектор
$\Vert{}\alpha v\Vert{} = \vert{}\alpha\vert{} \cdot \Vert{}v\Vert{}$

Третье свойство не так тривиально, но не менее важно
Пусть мы хотим построить самый короткий маршрут до работы
Понятно, что если нам нужно по дороге забежать в магазин, то путь не может уменьшиться (иначе, мы бы сразу пошли через магазин и получился бы более короткий маршрут)
Оказывается, это очень важное свойство для любой длины
Называется оно "неравенство треугольника" и формально записывается вот так:
$||v + u|| \leq ||v|| + ||u||$

Этих свойств нам хватит
И тут такой же ход, который был сделан при введении векторного пространство
Всё, что удовлетворяет этим трём правилам мы будем называть нормой

Теперь, попробуем понять, что вытекает из этих свойств

Я буду длину называть нормой
Самый часто используемый вариант нормы это p-норма

Те 3 варианта, которые мы обсуждали вначале урока можно обобщить одной формулой:
$$||v||_p =\ \sqrt[p]{ \sum_{i=1}^n{(v^i)^p}}$$*p>=1 (иначе ломается правило треугольника)
Выглядит страшно, но тут всё просто
Мы просто возводим координаты в степень p, суммируем и берём корень p-той степени

Например, обычной евклидово расстояние, то есть, теорема Пифагора - это p-норма с p=2:
$$||v||_p =\ \sqrt[2]{ \sum_{i=1}^n{(v^i)^2}}$$Манхэттенская норма тоже p-норма с p=1:

$$||v|| = \sqrt[1]{\sum_{i=1}^n{ (v^i)^1}} = \sum_{i=1}^n{ {v^i}}$$А max норма получается, если устремить p к бесконечности
Ведь чем больше степень, тем как бы большую роль начинают играть более сильные отклонения
Если сделать этот эффект максимальным, получится та самая max-норма
 

Одной из наиболее часто встречающихся задач анализа данных является кластеризация.

Нам хочется понимать, есть ли в данных скопления и где расположены их центры. Классический алгоритм, решающий эту задачу — k-means.

Сначала случайно раскидывает k центров кластеров по заданному пространству, затем считает расстояния до точек и пересчитывает более оптимальные центры 

При чём тут нормы?

В этом алгоритме критически важно то, как именно мы считаем расстояние. Чаще всего используют family p-норм (нормы Минковского), и выбор p меняет сам смысл «близости»:

• p = 1 ($L_1$-норма, Манхэттенское расстояние):

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

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

  Классический вариант по умолчанию. Считает прямые расстояния («по воздуху»). Формирует красивые сферические кластеры, но чувствителен к сильным выбросам.

• Большие p (например, p = 3, 4 и до бесконечности):

  Такие нормы смотрят на максимальное отклонение среди всех координат точки. Чем больше $p$, тем сильнее алгоритм штрафует за «несоответствие» хотя бы по одному признаку. Это полезно, когда нам важно контролировать допуски по всем параметрам сразу (например, деталь считается неверно кластеризованной, если хотя бы один её размер сильно ушел от нормы).

Важно понимать, что центр нужно для каждой нормы пересчитывать по-разному
Например, для евклидовой, новый центр - среднее арифметическое координат
Для остальных уже не так

Ещё, в норма влияет на "форму" кластеров
При p = 2, всё привычно
Кластеры получаются классическими шаровыми (ведь расстояние как и в реальном мире)
А вот при изменении p "шары" начинают вести себя уже не так интуитивно
При увеличении p шар как бы всё ближе к кубу

Более подробное описание алгоритма и некоторые геометрические детали его работы мы рассмотрим в следующем уроке

На видео сейчас показаны разные "круги" при разных p-нормах

Является ли это нормой?
$v = \sqrt[0.5]{(v^1)^{0.5} + (v^2)^{0.5}}$

 Какой вектор больше по Манхетенской норме?
$\begin{array}{l}v_1 = (0, 3, 4) \\ v_2 = (5, 1, 0) \\ v_3 = (6, 0, 0)\end{array}$