Больше центров богу центров. Вновь о центре масс, медиане и не только

sevabashirov — 31.03.2025 В ТГ недавно вновь зашел разговор о центрографии, в рамках которого затронута проблема недостаточного понимания терминов "центр масс" и "медианный центр" (также известный как геометрический, но так могут и другие точки называть). Помимо прикрепленного коммента к предыдущему посту по соответствующему тегу раскрываю тему отдельно.

Перенесемся для начала с небес Земли на сферическое абстрактное евклидово пространство в вакууме (для начала, да-да). Центром масс по определению является точка со средневзвешенными значениями каждой из декартовых координат исходного множества объектов (если все они одной массы - то берется обычное среднее арифметическое). Для непрерывного тела суммирование заменяется интегрированием, но сути это не меняет. Из-за простоты вычислений именно этот центр - самый "хайповый", его может рассчитать даже школьник (тоже средневзвешенный). Иногда даже без калькулятора, одно из свойств - центр масс совокупности двух объектов лежит на прямой, соединяющий центры каждого из них, причем расстояния до этих центров обратно пропорциональны массам объектов.

Но для нас более важное свойство - центр масс минимизирует сумму квадратов расстояний до объектов (опять-таки, взятых с их весами, впрочем для упрощения можно считать, что вместо объекта с N-кратной массой в одной точке находится N обычных объектов - это именно так и работает). Сильное заявление, доказывать его я конечно не буду - в конце концов, все мы homo googlens. Впрочем, доказательство не то что бы сложное, особенно если вспомнить, что квадрат расстояния - это сумма квадратов его декартовых составляющих, Пифагор не даст соврать.

А вот медианный центр - это как раз-таки точка минимума суммы расстояний (а не их квадратов). Ну или среднего расстояния, что то же самое. Для точек на одной прямой он совпадает со статистическим понятием медианы, откуда и название. За исключением специфического случая - когда все точки на одной прямой, их четное количество, а расстояние между средней по счету парой точек ненулевое - медианный центр, как и центр масс, определяется однозначно благодаря тому, что функция суммы расстояний - выпуклая (в ней может быть лишь одна точка минимума, и это собственно она и есть).

В различных прикладных задачах, включая базовую "логистическую" - найти место размещения условного склада, минимизируя транспортные издержки по доставке до потребителей - геометрическая медиана является естественным решением, практическая же польза от центра масс проявляет себя скорее в физике, если надо оценить воздействие всего множества объектов как единого целого. Но есть проблема - не существует явной формулы для нахождения медианного центра, приходится прибегать к итерационным алгоритмам, постепенно приближаясь к нему в пределах заданной точности (впрочем, они не слишком сложные и многие из них быстро сходятся).

На примере хорошо видно, что медианный центр (желтый) тяготеет к наиболее плотному скоплению исходных объектов, а центр масс (синий) - наоборот, отклоняется в сторону наиболее массивных "протуберанцев", что в целом логично, если вспомнить о квадратах расстояний (самые отдаленные точки тянут одеяло на себя сильнее).


И теперь настает пора вернуться на грешную сферическую (ну почти) Землю. Поскольку все исходные объекты - что бы мы ни считали, территорию, население или экономику - распределены вдоль поверхности планеты, "честные" центры будут "зарыты" на определенную глубину. Однако ничто не мешает либо а) заменять хорды дугами больших кругов, находя центры путем суммирования расстояний или их квадратов, либо б) выводить расчетный центр отвесно на поверхность Земли, т.е. говоря сейсмологическим языком, заменять гипоцентр эпицентром. Два способа в общем случае приводят к разным результатам; для практичной медианы естественнее пойти по первому пути, поскольку весь земной быт, и транспортные пути в частности, повторяют кривизну планеты. Для центра масс - в целом все равно, но вторым способом заметно быстрее считать (достаточно формул перевода сферических координат в прямоугольные и назад).

Впрочем, влияние кривизны Земли становится существенным для крупных государств, частей света, а для сравнительно компактных территорий аппроксимация плоскостью даст малоотличимый результат. Насколько я понимаю, этим и воспользовался южноафриканский дата-блогер Адриан Фрит, составляя наглядную карту двух типов центров населения ЮАР и всех ее провинций. Кстати, у него на сайте еще много материалов, включая несколько хорошо исполенных карт, ранее попадавшихся на глаза. Короше, наш слоняра. И взаимная топология центров более чем видна - медианы ближе к сгусткам плотности, центры масс указывают на направление более разреженных, но длинных "хвостов" расселения.



Карта своей идеей отсылает к старому посту с рассуждениями о практической пользе решении задачи медианной кластеризации - нахождении не 1, а нескольких пунктов, расположенных таким образом, чтобы сумма расстояний от каждого человека до ближайшего из пунктов была минимальной. В этом случае всё пространство разбивается на ячейки Вороного - чем не прообразы административных единиц. Задача эта не из легких, наиболее общее решение предполагает элементы брутфорса - многократный запуск итерационного алгоритма, начинающегося от рандомных точек, заменяющихся на медианы получающихся ячеек Вороного до тех пор, пока процесс не сойдется, и дальнейший выбор среди получившихся кандидатур.

И здесь возникает вопрос: а точно ли наилучшим образом оптимизирует транспортные издержки именно медиана? Иными словами, всё ли мы делаем правильно, принимая за аксиому, что затраты прямо пропорциональны расстоянию? В идеальном мире, где из любого пункта А в любой пункт В можно добраться буквально по прямой (геодезической, т.е. по большому кругу) и с постоянной скоростью - да. Но до идеала человечеству, вестимо, еще пахать и пахать.

В действительности транспортная система организована таким образом, что средняя путевая скорость возрастает вместе с расстоянием, которое необходимо преодолеть, по двум объективным причинам: 1) вынужденные потери скорости на разгон и торможение, доля которых в общем времени снижается с его ростом (и увеличивается доля "плато" максимальной скорости), 2) комбинирование различных видов транспорта для оптимального преодоления различных отрезков пути, при этом чем транспорт более "дальнодействующий", тем он очевидно быстрее (самый типичный пример - основной отрезок пути преодолевается на самолете, а отрезки от заданных пунктов до аэропортов - более медленным наземным транспортом).

График зависимости скорости от времени может быть разным (см. ниже) - треугольным, трапециевидным, многоступенчатым, даже синусоидальным. Суть же в том, что с увеличением времени проходимый путь (площадь под графиком скорости, если не забыли школьную программу) растет не линейно, а быстрее - в "треугольном" случае, когда максимальная и средняя скорости прямо пропорциональны времени, зависимость пути от времени выходит квадратичной, иными словами - издержки, которые требуется минимизировать при поиске оптимального центра, пропорциональны квадратному корню от расстояния. То есть в обратную сторону от медианы, нежели центр масс. Впрочем, степень 0,5 - тоже идеализированный случай, на деле можно ожидать степенную зависимость с показателем, колеблющимся от 0,5 до 1.



В целом ничего не мешает рассчитать знакомым способом и "логистический центр", возводя расстояния до точек в нужную степень менее единицы, казалось бы. Но беспощадная математика говорит, что в этом случае функция перестает быть выпуклой, а значит, у нее может появляться несколько локальных минимумов, и привычным алгоритмом последовательного приближения легко можно приблизиться куда-то не туда. Этот факт очевиден даже на простейшем примере двух точек с координатами 0 и 1 - если сумма (первых степеней) расстояний до них в любой точке отрезка равна 1, сумма квадратов расстояний минимальна в центре (2*0,5^2 = 0,5, когда как в самих точках 1^2+0 = 1), а вот сумма даже 0,99...-х степеней расстояния на всем отрезке превосходит единицу, имея в его середине не минимум, а максимум.

При этом минимумы получаются в самих точках, и это характерно не только для данного случая: локальные минимумы действительно тяготеют к самим объектам, пусть даже не всегда это тяготение пересиливает общий градиент поля воздействия других точек и вместо минимума получается лишь изгиб. Весьма похоже на гравитационную модель, причем чем больше скопление точек, либо чем единичная точка массивнее, тем в большей степени она ведет себя как "черная дыра" для функции суммы, увеличивая вероятность, что глобальный минимум будет непосредственно на ней. Однако у этого есть и плюсы, в противовес усложнениям расчета - с практической точки зрения иметь логистические центры в населенных пунктах, еще и наиболее крупных, очевидно удобнее, чем строить склад в чистом поле между ними.

Для степени 0,5 (т.е. квадратного корня из расстояния) все-таки попробовал найти глобальные минимумы. Для населения Земли, центр масс которого сейчас в Афганистане, а медианный центр - в Пенджабе, минимальная сумма корней ожидаемо попадает в Дели (и если бы не политика прямых авиасообщений, вносящая существенную неевклидовость в расчеты - между Индией и Китаем нет прямых рейсов - индийская столица была бы наилучшим кандидатом для места международных саммитов). В России же (где центр масс ползет на запад по Татарстану, а медиана - по Мордовии) аналогичный центр попадает... вы, конечно, будете смеяться, но в Москву. Если крупнейший город сравнительно недалеко от медианного центра, такое неизбежно.

А вот задача кластеризации территории по такой скорректированной метрике, с учетом возникающей в ней чисто математической естественности выделения центров притяжения... Звучит весьма грантопривлекательно. Продолжение, надеюсь, следует.

Оставить комментарий

Популярные посты:

• Ранее
• Архив