Нахождение известного числа центров окружностей, которые максимизируют количество точек на фиксированном расстоянии

10

У меня есть набор двумерных данных, где я хочу найти центры с указанным количеством центров окружностей ( ), которые максимизируют общее количество точек на указанном расстоянии ( ).RNR

например, у меня есть 10000 точек данных и я хочу найти центры из окружностей, которые захватывают как можно больше точек в радиусе . 5 центров и радиус 10 приведены заранее, а не по данным.N = 5 R = 10(Xi,Yi)N=5R=10

Наличие точки данных внутри круга является двоичным или / или суждением. Если , нет никакой разницы в значении для точки на расстоянии 11 единиц от 100 единиц на расстоянии, так как они оба> 10. Аналогично для того, чтобы быть в пределах круга, нет никакого дополнительного значения для того, чтобы быть около центра против края , Точка данных находится либо в одном из кругов, либо вне.R=10

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

Я предпочел бы найти способ сделать это в R, но любой подход был бы оценен.

colonel.triq
источник
Допускается ли перекрытие круга?
curious_cat
1
По сути, это операция соседства (или фокус) с набором растровых данных. Было бы хорошо проверить сайт ГИС, чтобы увидеть, получен ли на него ответ, и изучить пакеты R для проведения растрового анализа.
Энди W
1
Допускается перекрытие окружностей, но точки данных, охватываемые обоими кружками, не будут учитываться дважды. Спасибо за указатель на окрестность / фокусную операцию на наборах растровых данных. Я буду искать что-то в том же духе.
colonel.triq
@ Andy W Хотя целевые операции, естественно, будут вовлечены в решение, этот вопрос выходит за рамки компетенции сообщества ГИС, ИМХО, потому что это действительно (довольно трудная) проблема оптимизации. Это не прямая сетка "найди максимум макс фокальной средней". Я бы порекомендовал держать его здесь некоторое время, а затем, если не было найдено удовлетворительного решения, перейти на сайт, ориентированный на программирование.
whuber
.... или переход на math.overflow? Они могут иметь некоторое понимание этого тоже.
curious_cat

Ответы:

1

Это вариация k-средних. Радиус центров не имеет значения, если их считать равными.

Ссылки:

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

Классическая процедура K-средних:

  1. установить количество кластеров до 5
  2. поместить каждую точку в случайный кластер
  3. для каждого кластера рассчитать среднее положение
  4. для каждой точки рассчитайте расстояние до каждой новой средней позиции
  5. ассоциировать членство с ближайшим кластером
  6. повторять до завершения (итерации, изменение положения или другая метрика ошибки)

Опции:

  • Вы можете использовать некоторую недостаточную релаксацию после 3, когда вы медленно переводите среднее положение в новое положение.
  • это дискретная система, поэтому она не сходится идеально. Иногда это происходит, и вы можете закончить, когда очки перестают менять членство, но иногда они просто немного покачиваются.
  • Если вы создаете свой собственный код (как это должно делать большинство людей), то вы можете использовать приведенное выше P-k-средство в качестве отправной точки и внести некоторые изменения в EM, основываясь исключительно на процентах точек и полностью охваченных кружками.

Почему K-means решает проблему:

  • Это эквивалентно подгонке Гауссовой модели смеси, где ковариации компонентов равны. Центры компонентов смеси будут расположены в местах наибольшего ожидания точек. Кривые постоянной вероятности будут представлять собой круги. Это алгоритм EM, поэтому он имеет асимптотическую сходимость. Членство жесткое, а не мягкое.
  • Я думаю, что если фундаментальное предположение о модели смеси компонентов с равной дисперсией достаточно «близко», что бы это ни значило, этот метод подходит. Если вы просто случайным образом распределяете баллы, это вряд ли подойдет.

Должен быть какой-то аналог «Пуассона с нулевым надуванием», где есть негауссовский компонент, который улавливает равномерное распределение.

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

EngrStudent
источник
Не могли бы вы немного подробнее рассказать о том, как K-means решает эту проблему?
whuber
Спасибо за предложение. Мне все еще не ясно, что подход K-средних решает проблему? Рассмотрим пример трех кластеров нормальных (0,1) генерируемых данных, где центры смещены на 5 единиц или около того. Центры K-средних дают максимальную плотность. Теперь вырежьте некоторые точки с «дырами», чтобы данные, расположенные ближе, чем к центру, были удалены. К-среднее будет по-прежнему показывать примерно те же центры, но если вы пытаетесь получить максимальное покрытие для N = 3, R = 0,5, это явно не правильный ответ (поскольку дырки от бублика не содержат данных). Я что-то неправильно понимаю?
colonel.triq
Рассмотрим ваш вопрос больше для лучшего ответа, когда у меня будет время. Мне нравится разрешать отрицательные веса. Иногда может обрабатывать данные пончики, а также радиальные рациональные полиномы.
EngrStudent
0

У кого-то, вероятно, есть лучший формальный алгоритм, но вот один метод грубой силы (хак?). Я бы использовал один из шестиугольных алгоритмов биннинга для вычисления 2D гистограммы. Как hexbinв R.

Я бы использовал размер шестиугольника, который примерно описал бы ваш круг радиуса R, а затем отсортировал бы по верхним N корзинам. Если у вас есть Nчеткие далекие контейнеры, отлично. Теперь один из способов - это перемещаться по кругу локально по шкале 2 * R (в направлениях x и y) от центра шестиугольников верхней плотности. Вычислительные плотности могут примерно оптимизировать положение локально. Это будет учитывать тот факт, что шестиугольники не были движущимся окном относительно фиксированного начала.

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

Обратите внимание, что я могу вспомнить несколько угловых случаев, когда такая наивная стратегия потерпела неудачу. Тем не менее, просто отправная точка.

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

curious_cat
источник
1
Примерно так может решить проблему, по крайней мере, приблизительно, для одного круга. (Это может быть легко сделано с использованием фокальных отсчетов с помощью ГИС.) Но это не решит проблему с несколькими кругами.
whuber
@whuber: Как насчет решения для одного круга, затем отбрасывания всех точек, которые лежат в этом круге, и повторения исходного алгоритма? Можете ли вы увидеть ситуации, когда это не получится?
curious_cat
R=10,N=20,1,2,20,21,28,29,30,31,32,39,4028,29,30,31,320,1,220,21,28,29,3030,31,32,39,40
@whuber: правда. Вы правы. Хотя в зависимости от структуры входных точек в некоторых (многих?) Случаях жадные и не жадные решения могут быть идентичными или близкими к? Я не знаю.
curious_cat
@whuber: проблема кажется в основном на границах. Что делать , если (несколько , как я уже говорил в моем ответе) один перемещает окно +Rи -Rзатем помещает все возможные решения по стеку и выбирает среди них. Например, в вашем 1Dпримере при ударе 28,29,30,31,32он сдвинет окно до 18-28и 38-48ищет все возможные решения. Тогда внутри них можно искать максимально точечные комбинации. Не уверен, что это поможет? Я пытаюсь понять, можно ли спасти мой наивный алгоритм? :)
curious_cat