Ограниченная кластеризация

Алгоритм кластеризации для кластеров ограниченного размера

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

Чтобы сэкономить на транспортных расходах, они хотят арендовать несколько микроавтобусов. Конечно, чем меньше, тем лучше. Для того, чтобы транспорт был эффективным и приятным, они хотят, чтобы каждая семья держалась вместе в одном микроавтобусе и разбивала семьи по географическому положению, чтобы избежать лишних объездных путей.

Выражаясь математически, у нас есть n семья, где для каждой семьи f количество членов семьи s(f), а количество мест в каждом минивэне m. Допустимое разделение от n семейств на k микроавтобусов - такое, при котором в каждом микроавтобусе общее количество членов семьи не превышает вместимость микроавтобуса. Хорошая перегородка - это такая перегородка, в которой расстояние, преодолеваемое каждым минивэном, сведено к минимуму. Отличный раздел - это раздел, который оптимизирует компромисс между минимизацией количества микроавтобусов и минимизацией расстояния, пройденного каждым микроавтобусом.

Это сообщение содержит псевдокод. Настоящий код можно найти здесь.

Звучит довольно сложно, не так ли?

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

Что можем делать?

Давайте разберем это на два этапа:

Учитывая константу k, найдите (эвристически) наилучшее разделение семейств на k маршрутки.
Найдите лучшее k.

Шаг (1) создаст для нас хорошие разделы, а шаг (2) поможет нам найти отличный раздел.

Шаг I - Кластеризация ограниченных K-средних

Как следует из названия, чтобы найти раздел для данного k, мы будем использовать вариант известного алгоритма Кластеризация K-средних, вдохновленный этой статьей.

Подобно K-средним, мы реализуем итерационный алгоритм, который чередует поиск центроида каждого кластера (шаг update) и присвоение точек ближайшему центроиду (присвоение шаг). В этом варианте шаг присваивания также гарантирует, что кластеры сохраняют свой ограниченный размер.

Давайте будем более точными, и возьмем это сверху. Классический алгоритм K-средних выглядит примерно так:

1    centroids <- random k points
2    do n_iter times:
2.1     clusters <- each point assigned to closest centroid
2.2     centroids <- point closest to center in each cluster
3    return clusters

Теперь, чтобы учесть вариацию ограниченных кластеров, мы изменим шаг 2.1, шаг присваивания следующим образом:

(2.1).1   points <- sort points by weight, in descending order
(2.1).2   for each point in points:
(2.1).2.1    centroids <- sort centroids by distance from point
(2.1).2.2    centroid <- first centroid in centroids for which total
                         weight + point's weight does not exceed m
(2.1).2.3    add point to cluster corresponding to centroid

Вы можете увидеть код здесь.

Еще одна вещь, о которой следует помнить при использовании K-Means, заключается в том, что процесс подвержен нестабильности, и, возможно, локальный минимум, в котором он завершится, сильно зависит от первого случайного предположения.
Поэтому принято выполнять несколько повторов алгоритма и выберите лучший результат. По умолчанию sklearn.cluster.KMeans - 10 повторений, и мы будем следовать этому примеру.

Шаг II - Метод локтя для выбора лучшего K

Хорошо, теперь, когда мы знаем, как найти хорошую перегородку для фиксированного количества маршруток, k, как мы можем найти «лучший» k?

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

К счастью, некоторые умные люди уже много думали об этом, и обычной практикой является использование метода локтя, который примерно такой:

1   min_k <- sum(weights) / max cluster size
2   max_k <- min_k + number of sizes to try
3   for each k between min_k and max_k:
3.1    cost_k, clustrs_k <- Bounded K-Means Clustering
4   l <- line between (min_k, kcost_min_k) and (max_k, cost_max_k)
5   opt_k <- (k, cost_k) of maximal distance from l

Давайте посмотрим, как это выглядит с данными о путешествиях с семьями:

Анализ сложности

Давайте проанализируем одну итерацию нашей кластеризации ограниченных K-средних. Помните, что мы обозначаем: n количество семей, m максимальный размер микроавтобуса, k количество микроавтобусов.

На каждом этапе присваивания у нас есть:
➪ Сортировка точек по весу: n*log(n)
➪ Для каждой точки: сортировать центроиды k*log(k), добавить к первому действующему центроиду k
➪ Итого O(n*log(n) + n*(k*log(k) + k)) = O(n*log(n)*k*log(k))
На каждом этапе обновления:
Максимальное количество точек в каждом кластере равно n или m, если веса являются целыми числами.
Итак, для каждого кластера нам необходимо:
➪ Вычислительный центр кластера: n
➪ Найти ближайшую точку к центру: n
Итак, для всех кластеров: O(k*n)
Следовательно, каждая итерация имеет O(n*log(n)*k*log(k)) сложность.

Если мы выполняем x итераций до сходимости в каждом прогоне кластеризации, и y запускается с разными случайными начальными состояниями, мы получаем O(x*y*n*log(n)*k*log(k)).

Теперь помните, что мы хотим сделать это для разного количества k. Обозначим K как максимальное значение, которое мы хотим попробовать, и z число различных k, тогда мы получим в общей сложности O(x*y*z*n*log(n)*K*log(K)).

Метод локтя имеет линейную сложность в K, что не меняет нашего окончательного результата 😅.

Эпилог

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

Однако я поставил перед собой задачу выйти из зоны комфорта и попросил совета у некоторых коллег и коллег.
К счастью, Ориан Шарони быстро ответил, сославшись на две статьи (Кластеризация ограниченных K-средних + метод локтя), в которых все вместе закончилось.
Это заняло у меня на несколько часов больше, чем я думал да, но решение, которое я придумал, было гораздо более элегантным и, скорее всего, ближе к оптимальному (не тестировал его, но моя интуиция мне так подсказывает).

В заключение, как разработчику алгоритмов, особенно тем, кто работает в сфере быстроразвивающихся стартапов, полезно иметь под рукой методы, когда я просто хочу что-то сделать. Но потом, время от времени, это помогает еще больше исследовать новые идеи, изучать новые методы и расширять мою интеллектуальную библиотеку «перейти к алгоритмам».

Надеюсь, вам понравилось это путешествие со мной, и что сегодня вы также расширили свою интеллектуальную библиотеку 🤓

Ограниченная кластеризация