Существует ли алгоритм определения количества элементов в смежных областях?

Question

У меня есть набор точек, которые помещаются в двумерное евклидово пространство. Если расстояние между двумя точками ближе, чем заданный радиус отсечки, то они считаются соседями. Я хотел бы рассчитать количество элементов в смежных областях (например, 1 и 2 являются соседями. Если 2 и 3 также являются соседями, а также 3 и 4, то у нас есть 4 элемента, которые находятся рядом друг с другом).

Я весь день входил в Google как ад, и у меня было много ключевых слов, таких как kd-tree, k - кластеризация, обход графика, заливка флуда и анализ связанных компонентов, но я не могу их всех изучить эта точка. Мне просто нужно какое-то направление, чтобы сосредоточить свои усилия в правильном направлении.

Answer 1

Ваша проблема выглядит как анализ connected component!

Первое, что нужно представлять ваши данные в виде графика, и для этого есть множество библиотек. Возьмем пример в python: вы можете использовать Networkx или Graph-tool. Это просто, поскольку точка может быть представлена ​​как узел. Что касается краев, у вас в основном есть несколько решений.

Вы можете выполнить сравнения грубой силы, которые сравнивают все точки друг с другом. Он будет работать в O (n * (n-1)/2), ok, если набор данных невелик. Если набор данных большой, вы можете использовать разные приближенные алгоритмы (KD-tree, ball-tree), реализованные в Flann или scikit-learn. Обратите внимание, что scikit-learn также дает вам сравнение грубой силы.

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

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

Обратите внимание, что как только ваша проблема представляется в виде графика, на помощь приходит почти 70 лет теории графов. Вы можете проверить, имеют ли некоторые регионы ту же форму, что и другие, используя subgraph isomorphism. Вы можете проверить важность каждой точки в каждом компоненте с помощью centrality measures. Вы также можете разбивать непрерывное на субрегионы без необходимости порогового значения краев с помощью graph partitioning.

У вас может быть живой пример непрерывного графика, разрезанного на несколько разделов на моем blog.

Для аргумента: здесь приведен пример нескольких связанных компонентов, принадлежащих одному и тому же графу (с собственными ребрами).

Answer 2

Это явно проблема теории графов. У вас есть граф, узлы которого состоят из точек и в которых два узла соединены ребром, если их расстояние находится в пределах заданного порога. Вы ищете размеры различных подключенных компонентов. Поиск по ширине - это метод выбора (https://en.wikipedia.org/wiki/Breadth-first_search) для перечисления таких компонентов, хотя, если количество узлов достаточно мало, вы можете использовать алгоритм Варшалла на соответствующей матрице смежности.

Answer 3

То, что вы описываете звучит как алгоритм DBSCAN. Я бы посмотрел ссылку для описания. Это потребует от вас определения расстояния до соседей и минимального количества соседей.

Кроме того, алгоритм DBSCAN эквивалентно нахождения компонент связности графа, где график формируется путем соединения узлов в пределах определенного расстояния, если этот узел имеет минимальное количество соседей. Вы можете решить проблему подключенного компонента графа, используя алгоритмы BFS or DFS.

Answer 4

Если количество точек невелико, просто переверните все пары точек, проверьте их расстояния, и если расстояние меньше порогового значения, сопоставьте эти две точки в структуре данных Union-Find.

Чтобы ускорить это, вы можете выполнить начальный проход по точкам, разделяющим точки на ведра (каждый ковш имеет высоту и ширину, равную порогу); то для каждой точки вам не нужно сравнивать ее со всеми остальными точками - только в каждой другой точке окружения 3x3 ведер.

Возможно, потребуется дополнительное ускорение из-за того, что если точки были разделены на ведра размера (порог * sqrt (2)/2), все точки в одном и том же ковше обязательно должны быть связаны (нет требуется явная проверка расстояния), хотя с этими меньшими ведрами вы должны проверить более крупный (5x5) окружающий район для получения достаточно близких точек.