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

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

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

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

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

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

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

Установите limitA=maxA. Основная итерация: инициализировать пустой список possibleSolutions. Внешняя итерация: для каждой точки p в ps. Инициализировать пустой список pclusters. Определен рабочий список точек wps=copy(ps). Рабочая точка wp=p. Внутренняя итерация: пока wps не пусто. Убрать точку wp в wps. Определите все точки wpsInRadius в wps, которые находятся на расстоянии ‹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 адресов.

_{(источник: paperboyalgorithm на сайте sites.google.com)}

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

_{(источник: paperboyalgorithm на сайте sites.google.com)}

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

_{(источник: paperboyalgorithm на сайте sites.google.com)}

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

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

_{(источник: paperboyalgorithm на сайте sites.google.com)}

_{(источник: paperboyalgorithm на сайте sites.google.com)}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

* Изменить *

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

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

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

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

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

Возможно минимальное остовное дерево клиентов, разбитое на набор в зависимости от местонахождения бумажника. Prims или Kruskal, чтобы получить MST с расстоянием между домами для веса.

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

В основе предлагаемого подхода лежит так называемый меметический алгоритм, который немного похож на генетический Алгоритм, о котором упоминал Стив, однако он не только хорошо исследует пространство решений, но также имеет возможность сосредоточиться на интересных областях, то есть решениях. По крайней мере, я рекомендую прочитать некоторые статьи по этой теме, поскольку меметические алгоритмы - необычный подход, хотя и небольшое предупреждение; это может привести вас к прочтению «Эгоистичного гена», и я до сих пор не решил, было ли это хорошо ... Если алгоритмы вас не интересуют, то, возможно, вы можете просто попытаться выразить свою проблему в соответствии с требованиями формата и использовать исходный код предоставленный код. Соответствующие документы и код можно найти здесь: Многоцелевая кластеризация

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

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

Для людей, которые не живут в США, причина этого может быть не сразу очевидна. В США люди едут по правой стороне дороги, поэтому при повороте направо вам не нужно ждать встречного транспорта, если горит зеленый свет. Кроме того, в США, когда вы поворачиваете направо на красный свет, вам (обычно) не нужно ждать зеленого, прежде чем вы сможете уйти. Если вы всегда поворачиваете направо, вам никогда не придется ждать огней.

Здесь есть статья об этом: http://abcnews.go.com/wnt/story?id=3005890

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

Тривиальный ответ, за который не начисляются бонусные баллы:

Один доставщик на каждый адрес.

• You have a set of street addresses, each of which is geocoded.
  • You want to cluster the addresses so that each cluster is assigned to a delivery person.
  • Количество курьеров или кластеров не фиксировано. Если нужно, я всегда могу нанять больше доставщиков или уволить их.
  • У каждого кластера должно быть примерно одинаковое количество адресов. Однако в кластере может быть меньше адресов, если адреса кластера более разнесены. (Другими словами: минимальное количество кластеров, где каждый кластер содержит максимальное количество адресов, а любой адрес внутри кластера должен быть разделен максимальным расстоянием.)
  • Для бонусных баллов, когда набор данных изменяется (добавляется или удаляется адрес) и алгоритм повторно запускается, было бы неплохо, если бы кластеры оставались как можно более неизменными (т.е. это исключает простую кластеризацию k-средних, которая является случайный характер). Иначе курьеры сойдут с ума.

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

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

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

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

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

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

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

Одним из лучших современных методов кластеризации данных является накопление доказательств. (Фред и Джейн, 2005 г.) Вы делаете следующее:

Дан набор данных с n шаблонами.

1. Используйте алгоритм типа k-средних в диапазоне k. Или используйте набор разных алгоритмов, цель - создать ансамбль разделов.

2. Создайте матрицу совместной ассоциации C размером n x n.

3. Для каждого раздела p в ансамбле:
   3.1 Обновите матрицу совместной ассоциации: для каждой пары шаблонов (i, j), которая принадлежит одному и тому же кластеру в p, установите C (i, j) = C (i, j ) + 1 / н.

4. Используйте алгоритм кластеризации, такой как Single Link, и примените матрицу C в качестве меры близости. Single Link дает дендрограмму, в результате которой мы выбираем кластеризацию с наибольшим сроком службы.

Я предоставлю описания SL и k-средних, если вам интересно.

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

когда газетчики бывают:

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

когда локации:

• Добавлено: То же, локация добавляется к ближайшему маршруту.
• Удалено: только что удалено с маршрута этого мальчика.

Раз в квартал можно было все пересчитать и изменить все маршруты.