Методы кластеризации в логистике: алгоритм K-средних (K-Means) и алгоритм PAM

Алгоритм K-средних (K-Means) — это итерационный метод векторного квантования, предложенный Стюартом Ллойдом в 1957 году. Задача алгоритма заключается в разбиении множества из N многомерных векторов (например, GPS-координат клиентов) на заранее заданное количество K кластеров. Математическая целевая функция метода состоит в минимизации внутрикластерной дисперсии (суммы квадратов евклидовых расстояний от каждой точки до центра ее кластера). Поскольку поиск абсолютного глобального минимума этой функции является NP-трудной задачей, алгоритм Ллойда применяет изящную и молниеносную жадную эвристику, гарантированно сходящуюся к локальному оптимуму за конечное число шагов.

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

Несмотря на свою феноменальную скорость, K-Means имеет фатальный недостаток для реальной логистики: он крайне чувствителен к выбросам (аномальным точкам). Если один клиент находится в сотнях километров от остальных, возведение этого огромного расстояния в квадрат притянет центроид далеко за пределы города, разрушив компактность всего маршрута. Кроме того, центроид K-Means — это виртуальная, абстрактная математическая точка (которая может оказаться посреди озера или леса), что делает невозможным размещение в ней реального склада. Для обхода этих проблем применяется алгоритм K-медианоидов (K-Medoids), самой популярной реализацией которого является алгоритм PAM (Partitioning Around Medoids).

Алгоритм PAM использует в качестве меры расстояния не сумму квадратов, а абсолютное расстояние (Манхэттенскую метрику или L1-норму), что делает его абсолютно робастным (устойчивым) к выбросам. Главное алгоритмическое отличие заключается в том, что центром кластера (медианоидом) всегда обязана быть одна из реально существующих точек данных (реальный клиент или существующий склад). Алгоритм PAM работает по принципу обмена: он берет текущий медианоид и случайную не-медианоидную точку, вычисляет, как изменится общая стоимость доставки (сумма расстояний), если они поменяются ролями. Если общая стоимость падает, обмен фиксируется. Этот процесс перебора делает PAM вычислительно более тяжелым (сложность O(K * (N-K)^2)), но генерируемые им зоны доставки отличаются идеальной топологической ровностью, что позволяет логистическим корпорациям оптимально распределять нагрузку на автопарк в сложнейших урбанистических ландшафтах.