3D кластеризация Алгоритм

Question

Постановка задачи: У меня есть следующая проблема:

Есть более миллиарда точек в 3D-пространстве. Цель состоит в том, чтобы найти верхние N точек, которые имеют наибольшее количество соседей в заданном расстоянии R. Другое условие состоит в том, что расстояние между любыми двумя точками этих верхних N точек должно быть больше R. Распределение этих точек не является однородным. Очень часто в некоторых областях пространства содержится много очков.

Цель: Чтобы найти алгоритм, который может хорошо масштабироваться для многих процессоров и требует небольшого объема памяти.

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

Answer 1

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

Я думаю, что стоит исследовать locality-sensitive hashing. Я думаю, что разделение точек равномерно, а затем применение такого рода LSH к каждому набору должно быть легко параллелизуемо. Если вы разработали свой алгоритм хэширования таким образом, чтобы размер ведра определялся в терминах R, кажется вероятным, что для заданного набора точек, разделенных на ведра, точки, удовлетворяющие вашим критериям, скорее всего, будут существовать в самых полных ковшиках.

Выполняя это локально, возможно, вы можете применить какую-то стратегию сокращения карты, чтобы объединить пространственные ведра из разных параллельных прогонов алгоритма LSH поэтапно, используя тот факт, что вы можете начать чтобы исключить части вашего проблемного пространства путем дисконтирования целых ведер. Очевидно, что вам нужно быть осторожным в случаях кросс, которые охватывают разные ведра, но я подозреваю, что на каждом этапе слияния вы можете применять различные размеры/смещения ковша, чтобы удалить этот эффект (например, выполнить слияние пространственно эквивалентных ковшей, а также как соседние ведра). Я считаю, что этот метод можно использовать для того, чтобы небольшие требования к памяти (т. Е. Вам не нужно хранить гораздо больше, чем сами точки в любой момент, и вы всегда работаете на небольших (ish) подмножествах).

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

Еще одна мысль, которую я имел, заключалась в том, что это может касаться поиска metric k-center. Это определенно не такая же проблема, но, возможно, некоторые из методов, используемых при решении, применимы в этом случае. Проблема в том, что это предполагает, что у вас есть metric space, в котором можно вычислить метрику расстояния - в вашем случае, однако, наличие миллиарда точек делает нежелательным и трудным выполнить любой глобальный обход (например, сортировка расстояний между точки). Как я уже сказал, просто мысль, и, возможно, источник дальнейшего вдохновения.

Answer 2

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

3 шага: квантовать, поле, K-означает.

1) квантовать: уменьшить входные координаты XYZ, чтобы сказать 8 бит каждый, , взяв 2^8 процентилей X, Y, Z отдельно. Это ускорит весь поток без значительной потери деталей. Вы могли сортировать все 1G точки, или просто случайный 1M, , чтобы получить 8-бит x0 < x1 < ... x256, y0 < < y1 ... y256, z0 < < ... z1 z256 с 2^(30-8) точек в каждом диапазоне. К карте float X -> 8 бит x, развернутый бинарный поиск быстрый — см. Bentley, Pearls p. 95.

Добавлено: Kd trees разделить любое облако точек в различных размеров коробки, каждая из которых ~ Leafsize указывает — гораздо лучше, чем расщепление X Y Z, как указано выше. Но вам нужно будет свернуть свой код дерева Kd , чтобы разделить только первые, скажем, 16M-боксы, и сохранить только числа, а не точки.

2) box: подсчитать количество точек в каждом 3d поле, [xj .. xj + 1, yj .. yj + 1, zj .. zj + 1]. Средний квадрат будет иметь 2^(30-3 * 8) точек; Распределение будет зависеть от того, насколько сложны данные. Если некоторые боксы слишком большие или слишком много очков, вы можете a) разделите их на 8, b) Отследите центр точек в каждой коробке, по всей стране просто возьмите среднюю середину поля.

3) K-means clustering на центрах ящиков 2^(3 * 8). (Google параллельно «к означает» -> 121K хиты.) Это сильно зависит от K ака Ncluster, а также на вашем радиуса R. Грубый подход будет расти heap из говорят 27 * Ncluster коробки с большинство очков, , затем возьмите самые большие, подверженные ограничению радиуса. (Я хотел бы начать с Minimum spanning tree, затем удалить K-1 длинные ссылки, чтобы получить кластеры K.) Смотрите также Color quantization.

Я бы сделал Nbit, здесь 8, параметр с самого начала.

Какой у вас Ncluster?

Добавлено: если ваши точки движутся во времени, см. collision-detection-of-huge-number-of-circles на SO.

Answer 3

Просто идея. Создайте граф с заданными точками и ребрами между точками, когда расстояние < R.

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

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

Answer 4

Использовать Octree. Для трехмерных данных с областью ограниченного значения, которая очень хорошо масштабируется для огромных наборов данных.

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

Разделение на каждом уровне в 8 ящиков (2^d для d = 3) работает очень хорошо. И так как вы можете остановиться, когда в ячейке слишком мало очков, и постройте более глубокое дерево, где есть много очков, которые должны соответствовать вашим требованиям достаточно хорошо.

Для получения более подробной информации см Википедии:

https://en.wikipedia.org/wiki/Octree

В качестве альтернативы, вы можете попробовать построить R-дерево. Но R-дерево пытается сбалансировать, что затрудняет поиск наиболее плотных областей. Для вашей конкретной задачи это недостаток of Octree на самом деле полезен! R-дерево прикладывает большие усилия для того, чтобы глубина дерева была одинаковой везде, так что каждая точка может быть найдена примерно в одно и то же время. Тем не менее, вас интересуют только плотные районы, которые будут найдены на самых длинных путях в Octree, даже не глядя на реальные моменты!

Answer 5

Я также предлагаю использовать октет. Рамка OctoMap очень хороша при работе с огромными облаками 3D-точки. Он не сохраняет все точки напрямую, но обновляет плотность заполнения каждого узла (ака 3D-окна). После того, как дерево построено, вы можете использовать простой итератор, чтобы найти узел с наивысшей плотностью. Если вы хотите моделировать плотность точек или распределение внутри узлов, OctoMap очень легко принять.

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