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

Если у меня есть набор из N точек в 2D-пространстве, определяемых векторами X и Y их местоположений. Какой эффективный алгоритм

  1. Выберите фиксированное количество (M) точек для удаления, чтобы максимально увеличить расстояние до ближайшего соседа среди оставшихся точек.
  2. Удалите минимальное количество точек, чтобы наименьшее расстояние до ближайшего соседа среди оставшихся точек было больше фиксированного расстояния (D).

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

В моем случае я обычно имею дело с 1000–10 000 баллов и могу удалить 50–90% баллов.


algorithm nearest-neighbor
person Noam Ross    schedule 12.11.2013    source источник
comment
Один, вероятно, несовершенный алгоритм: найдите две ближайшие точки, удалите точку с наименьшим следующим NND, повторяйте, пока не дойдете до M или D.   -  person Noam Ross    schedule 12.11.2013
comment
Другой вариант, предложенный @berkeleymalagon в твиттере: вычислить все попарные расстояния один раз, отсортировать все пары по расстоянию и удалить точки из самых коротких пар, которые находятся в наименьшем количестве пар.   -  person Noam Ross    schedule 12.11.2013
comment
Мне приходит в голову, что для случая (2), если я вычисляю полную матрицу расстояний, каждая точка будет членом ряда пар с расстояниями ‹D. Затем мне нужно выбрать точки, которые входят в наибольшее количество пар, таким образом, чтобы они дополняли друг друга, чтобы минимизировать количество выбранных точек.   -  person Noam Ross    schedule 13.11.2013
comment
Хорошо, это означает, что случай (2) является классической проблемой установки покрытия. А как насчет случая (1)?   -  person Noam Ross    schedule 13.11.2013
comment
Случай (1) кажется мне чем-то вроде задачи о рюкзаке, в которой играют с нецелыми весами.   -  person Richard    schedule 24.05.2016
comment
Вы еще что-нибудь знаете о своих очках? Распределяются ли они равномерно-случайным образом в виде сетки, ожидаете ли вы кластеризации и т. Д.?   -  person Richard    schedule 24.05.2016

Ответы (3)


arrow_upward
1
arrow_downward

Вам не нужно хранить (или вычислять) всю матрицу расстояний: триангуляция Делоне должна эффективно (O(n log n) худший случай) дает вам ближайших соседей вашего набора точек. Вы также должны иметь возможность эффективно обновлять его при удалении точек.

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

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

person comingstorm    schedule 12.11.2013
comment
Я попробую это. Однако в моем случае я могу убрать 50-90% точек. Я посмотрю, как этот метод работает в этом случае. - person Noam Ross; 13.11.2013

arrow_upward
1
arrow_downward

Ноам

Один из способов - разбить ваше 2D-пространство на N разделов. Внутри каждого раздела определите среднюю позицию для каждого X, Y. Затем выполните алгоритм ближайшего соседа по усредненным точкам. Затем повторите тест ближайшего соседа на полном наборе точек совпадающих разделов.

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

person Andrew - OpenGeoCode    schedule 12.11.2013

arrow_upward
1
arrow_downward

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

Итак, что бы я сделал, так это. Сначала определите расстояние до ближайшего соседа для каждой точки. Назовем это P_in. Затем определите максимальное расстояние каждой точки до ее M ближайших соседей, назовите это P_iM. Если P_in больше P_iM для любой точки, то ее можно исключить из анализа. Обычно, если у вас есть одна точка, которая находится на расстоянии 10 от любой другой точки, и у вас есть другая точка, которая находится на расстоянии 9 от ближайших M точек, тогда вам следует удалить первую точку.

В зависимости от уровня кластеризации или размера M это может немного уменьшить ваш набор данных.

person Robert Wilson    schedule 12.11.2013