Дано двумерное пространство. Даны N точек с заданными координатами. Нужно распределит
точки в M зон. В каждую зону нужно поместить количество точек равное целому частном
M/N или M/N+1. Способ определения кому достанется M/N, а кому M/N+1 значения не имеет. Внешний контур зон должен быть выпуклым. Зоны не должны пересекаться, а если это невозможно, то в пересечении зон, не должно быть внутренних точек.
Например,
Следующий вариант плохой
Я затрудняюсь перенести это условие на формальный язык. В реальной задаче (N>5000
M~50) вариант с красными стрелками не подходит, потому что для "коммивояжеров" получится слишком неудобный участок
Похожие вопросы
Поиск геометрического центра группы объектов в 3D пространстве с предварительно
фильтрацией
Какой существует алгоритм для объединения точек в области?
Структура данных для упорядочения двумерных точек
Ссылки по теме
Хабрахабр. Андрей Часовских @andreycha. Обзор алгоритмов кластеризации данных.
Ответы
Ответ 1
Точное решение с доказательством я привести не могу, но могу дать несколько направлений.
Первый вариант
Можно построить частный случай Kd-дерева, когда каждой области принадлежит по 1 точке
а после начать объединять области снизу, используя данное условие. Если точки находятся "близко", то они будут соседями на соседних уровнях, и поэтому объединятся в первую очередь.
Второй вариант
Второй вариант предполагает построение диаграммы Вороного. Для каждой точки находи
ближайшие границы. Области можно объединять только с областями, которые смежные с данными границами. В данном случае будет усеченный перебор, так как в среднем у каждой точки будет мало таких границ. Худший случай - точки расположены строго по гексагональной сетке.
Рекомендую посмотреть "Mark de Berg - Computational Geometry Algorithms and Applications". Там будет описание построения данных структур.
Я бы начал с первого варианта, так как Kd деревья реализуются достаточно просто
информации по ним больше, возможно, даже можно найти пример с объединением по условию, так как эти деревья имеют много применений. Диаграммы Вороного проще "дебажить" графически и есть много реализаций на разных языках, поэтому базу можно быстрее сделать.
Если отталкиваться от "в приоритете близость точек друг к другу и равное количеств
для каждой зоны", то диаграммы Вороного могут быть лучше, так как у них при построени
похожая задача стоит. Возможно, можно доказать транзитивность этого условия между областями. Тогда достаточно будет построить диаграмму второго порядка, их в книге вроде нет, но можно найти несколько статей на эту тему. К сожалению, готовых реализаций для диаграмм высших порядков я не встречал, поэтому придется писать самостоятельно.
Ответ 2
Во-первых, замечу, что выпуклость контуров сама по себе не имеет смысла. Потому ка
контур любого кластера будет выпуклым. Требование выпуклости нужно для определения пересечений.
Вам для кластеризации подойдет алгоритм нечеткой кластеризации c-means, который являетс
модификацией алгоритма k-means. Им обоим для работы требуется заранее знать количество кластеров для поиска, а это как раз ваш случай. Но у c-means есть то преимущество, перед k-means, что он для каждой точки дает нечеткую оценку принадлежности к кластерам.
Оценку пересечений нужно так же сделать нечеткой. То есть нужно знать насколько сильно пересекаются кластеры.
Далее, можно попробовать несколько эвристик:
Модифицировать c-means так, что в случае когда точка "близка" одновременно нескольки
кластерам учитывать пересечение контуров, то есть "приближать" точку к тому кластеру который "уменьшает" пересечение.
Попробовать уменьшить пересечения за счет обмена "близкими" точками между пересекающимс
кластерами. Если кластеры пересекаются, то велика вероятность что и другие их точки также "близки", чем точки из других кластеров.
Чтобы уменьшить пересечение нужно найти "виновников" пересечения и опробовать и
забрать\отдать. При этом если в одном кластере будет нехватать точек, то в другом буде
из избыток. Чтобы этого избежать можно забирать или отдавать точки любым кластерам к которым эти точки близки. В результате возникнет волна обменов, ее нужно остановливать если оценки пересечений начинают ухудшаться.
Так же как и в предыдущем варианте, но попробовать направлять волны обменов дру
на друга чтобы они погасились. То есть волну "изъятия" нужно направлять на волну "отдающуюю".
Для алгоритма k-means очень важен выбор первоначальных центров кластеров. В случа
если в какой-то области получилось много пересечений, то можно перестартовать k-means
приблизив первоначальные центы к пересечениям чтобы они поглотились новыми кластерами. При этом рестарт необязательно выполнять для всех точек, если другие кластеры далено от проблемного места их можно не трогать.
Комментариев нет:
Отправить комментарий