Алгоритм кластеризации для бумажных мальчиков

Question

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

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

• У вас есть набор уличных адресов, каждый из которых геокодирован.
• Вы хотите сгруппировать адреса так, чтобы каждый кластер был назначен сотруднику доставки.
• Количество лиц, осуществляющих доставку, или кластеров не фиксировано. При необходимости я всегда могу нанять больше сотрудников службы доставки или уволить их.
• Каждый кластер должен иметь примерно одинаковое количество адресов. Однако у кластера может быть меньше адресов, если адреса кластера более распределены. (Можно сформулировать иначе: минимальное количество кластеров, где каждый кластер содержит максимальное количество адресов, а любой адрес в кластере должен быть разделен максимальным расстоянием.)
• Для бонусных баллов, когда набор данных изменяется (адрес добавляется или удаляется) и алгоритм перезапускается, было бы неплохо, если бы кластеры оставались настолько неизменными, насколько это возможно (т.е. это исключает простые k-средства кластеризация, которая носит случайный характер). В противном случае курьеры сойдут с ума.

Итак ... идеи?

UPDATE

График уличной сети, как описано в ответе Арахнида, недоступен.

Answer 1

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

Алгоритм работает со списком, если координаты (x, y) ps указаны как int s. Он также принимает три других параметра:

1. радиус (r): с учетом точки, каков радиус для сканирования ближайших точек
2. макс. Адресов (maxA): каково максимальное количество адресов (точек) на кластер?
3. минимальные адреса (minA): минимальные адреса на кластер

Набор limitA=maxA. Основная итерация: Инициализировать пустой список possibleSolutions. Внешняя итерация: для каждой точки p в ps. Инициализировать пустой список pclusters. Рабочий список точек wps=copy(ps) определен. Рабочая точка wp=p. Внутренняя итерация: , пока wps не пусто. Удалить точку wp в wps. Определите все точки wpsInRadius в wps, которые находятся на расстоянии <<code>r от wp. Сортировать wpsInRadius по возрастанию в соответствии с расстоянием от wp. Оставьте первые min(limitA, sizeOf(wpsInRadius)) баллов в wpsInRadius. Эти точки образуют новый кластер (список точек) pcluster. Добавьте pcluster к pclusters. Удалить точки в pcluster из wps. Если wps не пусто, wp=wps[0] и продолжите внутреннюю итерацию. Завершить внутреннюю итерацию. Список кластеров pclusters получается. Добавьте это к possibleSolutions. Завершить внешнюю итерацию.

У нас есть для каждого p в ps список кластеров pclusters в possibleSolutions. Каждый pclusters затем взвешивается. Если avgPC - это среднее число точек на кластер в possibleSolutions (глобальное), а avgCSize - среднее количество кластеров на pclusters (глобальное), то эта функция использует обе эти переменные для определения вес:

  private static WeightedPClusters weigh(List<Cluster> pclusters, double avgPC, double avgCSize)
  {
    double weight = 0;
    for (Cluster cluster : pclusters)
    {
      int ps = cluster.getPoints().size();
      double psAvgPC = ps - avgPC;
      weight += psAvgPC * psAvgPC / avgCSize;
      weight += cluster.getSurface() / ps;
    }
    return new WeightedPClusters(pclusters, weight);
  }

Лучшим решением сейчас является pclusters с наименьшим весом. Мы повторяем основную итерацию, пока можем найти лучшее решение (меньший вес), чем предыдущее лучшее с limitA=max(minA,(int)avgPC). Завершение основной итерации.

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

Чтобы увидеть, как этот алгоритм ведет себя, это изображение результата на тестовом шаблоне из 32 точек. Если maxA=minA=16, то мы найдем 2 кластера из 16 адресов.

Далее, если мы уменьшим минимальное количество адресов на кластер, установив minA=12, мы найдем 3 кластера по 12/12/8 точек.

И чтобы продемонстрировать, что алгоритм далек от совершенства, вот результат с maxA=7, но мы получаем 6 кластеров, некоторые из которых небольшие. Таким образом, вам все равно придется слишком много угадывать при определении параметров. Обратите внимание, что r здесь только 5.

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

Вывод? Это заняло у меня полдня, это неэффективно, код выглядит уродливо, и это относительно медленно. Но это показывает, что можно получить некоторый результат за короткий промежуток времени. Конечно, это было просто для удовольствия; превратить это во что-то действительно полезное - сложная часть.

Answer 2

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

Однако кластеры могут подвергаться серьезным изменениям только с незначительно отличающимися экземплярами, чего вы и должны избегать. Тем не менее, что-то в VRP-Papers может вдохновить вас ...

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

Для оценки кластеров с использованием графического представления уличной сетки, вероятно, будут получены более реалистичные результаты, чем при соединении точек на белой карте (хотя оба являются вариантами TSP). Если графовая модель недоступна, вы можете использовать таксометрическую метрику (| x_1 - x_2 | + | y_1 - y_2 |) в качестве приближения для расстояний.

Answer 3

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

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

Я предполагаю, что ваша настоящая проблема не имеет ничего общего с доставкой газет ...

Answer 4

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

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

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

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

Answer 5

Это очень быстрый и грязный метод определения того, где лежат ваши "скопления". Это было вдохновлено игрой "Сапер".

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

Переберите каждый квадрат и сохраните количество мест доставки (домов) в каждом блоке. Используйте второй цикл (или какой-нибудь умный метод на первом проходе), чтобы сохранить количество точек доставки для каждого соседнего блока.

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

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

Извлеките максимально допустимое расстояние, которое должен пройти один доставщик за один проход. Затем сделайте то же самое для количества доставок на человека.

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

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

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

Я оставлю процедуру пересчета на ваше усмотрение, но наличие всех текущих маршрутов, кластеров и т. Д. В базе данных позволит вам сохранить все исторические маршруты, а также попробует различные сценарии, чтобы выяснить, как лучше адаптироваться к изменениям. создание наименьших возможных изменений в существующих маршрутах.

Answer 6

Я бы подошел к этому по-другому: рассматривая уличную сеть как граф с ребром для каждой стороны каждой улицы, найдите разбиение графа на n сегментов, каждый не более определенной длины, так, чтобы каждый разносчик газет проезжайте один непрерывный путь от начала до конца своего маршрута. Таким образом, вы избегаете указывать людям маршруты, по которым они должны неоднократно проезжать одни и те же отрезки (например, когда их просят покрыть обе стороны улицы, не охватывая все окружающие улицы).

Answer 7

Это классический пример проблемы, которая заслуживает оптимизированного решения , а не попытки решить для "ОПТИМАЛЬНОГО". В некотором смысле это похоже на « задачу коммивояжера », но вам также нужно сегментировать местоположения во время оптимизации.

Я использовал три разных алгоритма оптимизации, чтобы хорошо влиять на такие проблемы:

1. Имитация отжига
2. Алгоритм Великого Потопа
3. Генетические алгоритмы

Используя алгоритм оптимизации, я думаю, что вы описали следующие "цели":

1. Географическая зона для каждой бумаги мальчик должен быть сведен к минимуму.
2. Количество подписчиков, обслуживаемых каждый должен быть примерно равным.
3. Расстояние, пройденное каждым должно быть примерно равным.
4. (И тот, который вы не заявили, но могли бы имеет значение) Маршрут должен заканчиваться там, где это началось.

Надеюсь, это поможет вам начать!

* Редактировать *

Если вы не заботитесь о самих маршрутах, это исключает цели 3 и 4, описанные выше, и, возможно, позволяет более точно приспособить проблему к вашим бонусным требованиям.

Если вы принимаете во внимание демографическую информацию (такую ​​как плотность населения, коэффициент принятия подписки и коэффициент отмены подписки), вы, вероятно, могли бы использовать описанные выше методы оптимизации, чтобы исключить необходимость повторного запуска алгоритма вообще, когда подписчики приняли или отбросили вашу услугу. Как только кластеры будут оптимизированы, они останутся в равновесии, потому что ставки каждого для отдельного кластера совпадают со скоростями для других кластеров.

Единственный раз, когда вам пришлось бы перезапускать алгоритм, это когда внешний фактор (например, рецессия / депрессия) вызывал изменения в поведении демографической группы.

Answer 8

Вместо того, чтобы кластеризовать модель, я думаю, что вы действительно хотите какой-то вариант модели расположения покрытия, с дополнительным ограничением для покрытия количества адресов, охватываемых каждым объектом. Я не могу найти хорошее объяснение этого в Интернете. Вы можете взглянуть на эту страницу , но они решают ее с использованием площадных единиц, и вы, вероятно, захотите решить ее либо в евклидовом, либо в сетевом пространстве. Если вы хотите что-то найти в формате мертвого дерева, ознакомьтесь с главой 4 «Сеть и дискретное местоположение» Даскина.

Answer 9

Возможно минимальное связующее дерево клиентов, разбитое на множество в зависимости от местности для бумажного мальчика. Примы или Крускал , чтобы получить MST с расстоянием между домами для веса.

Answer 10

Хороший обзор простых кластерных алгоритмов. Хотя есть еще: http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/index.html