У меня есть набор двумерных данных, где я хочу найти центры с указанным количеством центров окружностей ( ), которые максимизируют общее количество точек на указанном расстоянии ( ).R
например, у меня есть 10000 точек данных и я хочу найти центры из окружностей, которые захватывают как можно больше точек в радиусе . 5 центров и радиус 10 приведены заранее, а не по данным.N = 5 R = 10
Наличие точки данных внутри круга является двоичным или / или суждением. Если , нет никакой разницы в значении для точки на расстоянии 11 единиц от 100 единиц на расстоянии, так как они оба> 10. Аналогично для того, чтобы быть в пределах круга, нет никакого дополнительного значения для того, чтобы быть около центра против края , Точка данных находится либо в одном из кругов, либо вне.
Есть ли хороший алгоритм, который можно использовать для решения этой проблемы? Похоже, это относится к методам кластеризации, но вместо минимизации среднего расстояния функция «расстояния» равна 0, если точка находится в пределах любой из точек, и 1 - в противном случае.N
Я предпочел бы найти способ сделать это в R, но любой подход был бы оценен.
источник
Ответы:
Это вариация k-средних. Радиус центров не имеет значения, если их считать равными.
Ссылки:
Центры окружностей будут расположены в местах наибольшей вероятности точек.
Классическая процедура K-средних:
Опции:
Почему K-means решает проблему:
Должен быть какой-то аналог «Пуассона с нулевым надуванием», где есть негауссовский компонент, который улавливает равномерное распределение.
Если вы хотели «настроить» вашу модель и были уверены, что было достаточно точек выборки, то вы могли бы инициализировать с помощью k-средних, а затем сделать расширенный регулятор k-средних, который удаляет точки вне радиусов окружностей из соревнования. Это немного нарушило бы ваши круги, но могло бы немного улучшить производительность, учитывая данные.
источник
У кого-то, вероятно, есть лучший формальный алгоритм, но вот один метод грубой силы (хак?). Я бы использовал один из шестиугольных алгоритмов биннинга для вычисления 2D гистограммы. Как
hexbin
вR
.Я бы использовал размер шестиугольника, который примерно описал бы ваш круг радиуса R, а затем отсортировал бы по верхним N корзинам. Если у вас есть
N
четкие далекие контейнеры, отлично. Теперь один из способов - это перемещаться по кругу локально по шкале 2 * R (в направлениях x и y) от центра шестиугольников верхней плотности. Вычислительные плотности могут примерно оптимизировать положение локально. Это будет учитывать тот факт, что шестиугольники не были движущимся окном относительно фиксированного начала.Если все верхние корзины находятся рядом, у вас должен быть более разумный способ перемещения ваших кругов в этой окрестности.
Обратите внимание, что я могу вспомнить несколько угловых случаев, когда такая наивная стратегия потерпела неудачу. Тем не менее, просто отправная точка.
Между тем, я надеюсь, что у кого-то есть лучший алгоритм.
источник
+R
и-R
затем помещает все возможные решения по стеку и выбирает среди них. Например, в вашем1D
примере при ударе28,29,30,31,32
он сдвинет окно до18-28
и38-48
ищет все возможные решения. Тогда внутри них можно искать максимально точечные комбинации. Не уверен, что это поможет? Я пытаюсь понять, можно ли спасти мой наивный алгоритм? :)