2010-08-14 10 views
7

Problem Statement: Ich habe folgendes Problem:3D-Clustering-Algorithmus

Es gibt mehr als eine Milliarde Punkte im 3D-Raum. Das Ziel besteht darin, die oberen N Punkte zu finden, die die größte Anzahl von Nachbarn innerhalb der gegebenen Entfernung R haben. Eine weitere Bedingung ist, dass der Abstand zwischen zwei beliebigen Punkten dieser oberen N Punkte größer als R sein muss. Die Verteilung dieser Punkte ist nicht einheitlich. Es ist sehr üblich, dass bestimmte Regionen des Raumes viele Punkte enthalten.

Ziel: Um einen Algorithmus zu finden, der gut zu vielen Prozessoren skalieren kann und eine geringe Speicheranforderung hat.

Gedanken: Normale räumliche Zerlegung ist für diese Art von Problem aufgrund der ungleichmäßigen Verteilung nicht ausreichend. unregelmäßige räumliche Zerlegung, die die Anzahl der Punkte gleichmäßig verteilt, kann uns das Problem helfen. Ich werde es wirklich zu schätzen wissen, wenn jemand etwas Licht auf dieses Problem werfen kann.

+1

Das klingt nach der 3-D-Variante des Set-Covering-Problems !! :-) –

+0

Ihr Problem erinnert mich an "Vector QuantizatioN", die Ihnen einige Ideen geben kann: http://www.data-compression.com/vq.shtml. Auf den ersten Blick sollte das Problem nicht schwer zu lösen sein, wenn Sie diese Einschränkung entfernen * "der Abstand zwischen zwei Punkten dieser oberen N Punkte muss größer sein als R" * - diese Einschränkung verursacht ein großes Problem und erfordert a viel Denken, um es zu überwinden. – SigTerm

Antwort

2

Ich habe keine definitive Antwort für Sie, aber ich habe einen Vorschlag für einen Ansatz, der eine Lösung liefern könnte.

Ich denke, es lohnt sich zu untersuchen locality-sensitive hashing. Ich denke, die Punkte gleichmäßig zu verteilen und dann diese Art von LSH auf jeden Satz anzuwenden, sollte leicht parallelisierbar sein. Wenn Sie Ihren Hashing-Algorithmus so entwerfen, dass die Bucket-Größe in R definiert wird, ist es wahrscheinlich, dass für eine bestimmte Gruppe von Punkten, die in Buckets unterteilt sind, die Punkte, die Ihren Kriterien entsprechen, wahrscheinlich in den vollständigsten Buckets vorhanden sind. Wenn Sie dies lokal ausgeführt haben, können Sie vielleicht eine Art von Map-Reduction-Strategie anwenden, um räumliche Buckets aus verschiedenen parallelen Läufen des LSH-Algorithmus schrittweise zu kombinieren und dabei die Tatsache zu nutzen, dass Sie beginnen können um Teile Ihres Problembereichs auszuschließen, indem ganze Buckets diskontiert werden. Offensichtlich müssen Sie bei Edge Cases, die sich über verschiedene Buckets erstrecken, vorsichtig sein, aber ich vermute, dass Sie bei jeder Merging-Phase unterschiedliche Bucket-Größen/Offsets anwenden können, um diesen Effekt zu entfernen (z. B. das Zusammenführen räumlich äquivalenter Buckets) als benachbarte Eimer). Ich glaube, dass diese Methode verwendet werden könnte, um die Speicheranforderungen klein zu halten (d. H. Sie sollten nicht viel mehr als die Punkte selbst zu einem bestimmten Zeitpunkt speichern müssen, und Sie arbeiten immer auf kleinen (ish) Teilmengen).

Wenn Sie nach einer Art Heuristik suchen, dann denke ich, dass dieses Ergebnis sofort etwas hervorbringen wird, das einer "guten" Lösung ähnelt - d. H. Es wird Ihnen eine kleine Anzahl wahrscheinlicher Punkte geben, die Sie überprüfen können. Wenn Sie nach einer genauen Antwort suchen, müssen Sie einige andere Methoden anwenden, um den Suchraum zu trimmen, wenn Sie beginnen, parallele Buckets zusammenzuführen.

Ein anderer Gedanke, den ich hatte, war, dass dies auf das Finden der metric k-center beziehen könnte. Es ist definitiv nicht das exakt gleiche Problem, aber vielleicht sind einige der Methoden, die zum Lösen verwendet werden, in diesem Fall anwendbar. Das Problem ist, dass Sie davon ausgehen, dass Sie eine metric space haben, in der die Berechnung der Entfernungsmetrik möglich ist - in Ihrem Fall macht es jedoch das Vorhandensein von einer Milliarde Punkten unerwünscht und schwierig, irgendeine Art von globalem Traversal durchzuführen (z. B. Sortieren der Abstände zwischen Punkte). Wie gesagt, nur ein Gedanke und vielleicht eine Quelle weiterer Inspiration.

+0

Dies ist in der Tat sehr ähnlich zum Problem der maximalen Abdeckung. Die Objektfunktion ist anders. Hier gilt es zu minimieren: Summe ((Ci-Ct/K)^2), i = 1, .. K, wobei K die Nummer der Partition ist, Ci die Anzahl der Punkte in Set i und Ct die Zahl Gesamtzahl der Punkte –

+0

Ci ist nicht genau die Variable, die wir optimieren möchten. Aber es sollte nah genug sein. Idealerweise sollte Ci auch die Anzahl der Punkte in seinen nächsten Nachbarzellen auf der Oberfläche enthalten. Da die Zellengröße R ist, muss die Abstandsberechnung nur ihre nächste Nachbarzelle erweitern. –

+0

Eine Idee, die ich mir jetzt vorstelle, ist die Erstellung von LxMxN-Zellen (Länge für jede Zelle ist R). Die Anzahl der Punkte kann für jede Zelle leicht aufgezeichnet werden. Und dann kann ein Cluster-Algorithmus verwendet werden, um die dichten Cluster zu finden. Da es viel zu viele Punkte gibt, ist es unmöglich, den Clustering-Algorithmus für einzelne Punkte durchzuführen. Wir können jedoch die Auflösung der Zählungen in der LxMxN-Zelle reduzieren, indem wir die Zählungen durch eine willkürliche Zahl dividieren. Zum Beispiel Ct/(LMN). Und dann kann ein Greedy-Algorithmus verwendet werden, um die Partition zu erstellen. Ich bin mir nicht sicher, ob das auf dem richtigen Weg ist. –

1

Hier sind einige mögliche Teile einer Lösung. Es gibt verschiedene Möglichkeiten in jeder Phase, die von Ncluster abhängen wird, wie schnell sich die Daten ändern, und was Sie mit den Mitteln machen wollen.

3 Schritte: quantisieren, Box, K-bedeutet.

1) quantisieren: Reduziere die Eingabe XYZ-Koordinaten um jeweils 8 Bits zu sagen, indem 2^8 Perzentile von X, Y, Z getrennt genommen werden. Dies beschleunigt den gesamten Fluss ohne viel Detailverlust. Sie könnten sortieren alle 1G Punkte oder nur eine zufällige 1M, zu erhalten 8-Bit-x0 < x1 < ... x256, y0 < y1 < ... y256, z0 < z1 < ... Z256 mit 2^(30-8) Punkte in jedem Bereich. Um float X -> 8-Bit-x abzubilden, ist die abgerollte binäre Suche schnell — siehe Bentley, Pearls p. 95.

am: Kd trees aufgeteilt jede Punktwolke in unterschiedlich großen Schachteln, jeweils mit ~ Leafsize weist — viel besser als die, wie oben X Y Z spalten. Aber afaik müssten Sie Ihren eigenen Kd-Baumcode rollen, um nur die ersten 16M-Boxen zu teilen, und nur Zählungen behalten, nicht die Punkte.

2) Box: Zählen Sie die Anzahl der Punkte in jeder 3D-Box, [xj .. xj + 1, yj .. yj + 1, zj .. zj + 1]. Die durchschnittliche Box hat 2^(30-3 * 8) Punkte; Die Verteilung hängt davon ab, wie klumpig die Daten sind. Wenn einige Boxen zu groß sind oder zu viele Punkte bekommen, könnten Sie sie in 8, teilen. B) Verfolgen Sie die Mitte der Punkte in jeder Box.

3) K-means clustering auf den 2^(3 * 8) Kastenmitten. (Google parallel "k bedeutet" -> 121k hits.) Dies hängt stark von K aka Ncluster, auch auf dem Radius R. Eine grobe Annäherung mit dem ein heap der sagen 27 * Ncluster Boxen wachsen würde Die meisten Punkte, , nehmen dann die größten unter Ihrer Radius-Einschränkung. (Ich mag mit einem Minimum spanning tree, entfernen Sie dann die K-1 längsten Verbindungen starten K-Cluster zu erhalten.) Siehe auch Color quantization.

Ich würde Nbit, hier 8, einen Parameter von Anfang an machen.

Was ist Ihr Ncluster?

Hinzugefügt: Wenn sich Ihre Punkte in der Zeit bewegen, siehe collision-detection-of-huge-number-of-circles auf SO.

0

Nur eine Idee. Erstellen Sie einen Graphen mit gegebenen Punkten und Kanten zwischen den Punkten, wenn die Entfernung < R.

Die Erstellung dieser Art von Graphen ähnelt der räumlichen Zerlegung. Ihre Fragen können mit der lokalen Suche im Graphen beantwortet werden. Zuerst sind Knoten mit maximalem Grad, und zweitens ist das Finden der maximalen nicht zusammenhängenden Menge von Max-Grad-Vertices.

Ich denke, die Erstellung von Grafik und Suche kann parallel gemacht werden. Dieser Ansatz kann große Speicheranforderungen haben. Die Aufteilung der Domäne und das Arbeiten mit Grafiken für kleinere Volumes kann den Speicherbedarf verringern.

3

Verwenden Sie einen Octree. Für 3D-Daten mit einer begrenzten Wertdomäne, die sehr gut zu großen Datenmengen passt.

Viele der oben genannten Methoden wie Lokalität empfindlich Hashing sind ungefähre Versionen für viel entworfen höhere Dimensionalität, wo man nicht vernünftig mehr aufspalten.

Die Aufteilung auf jeder Ebene in 8 Bins (2^d für d = 3) funktioniert sehr gut. Und da Sie aufhören können, wenn es zu wenige Punkte in einer Zelle gibt, und bauen Sie einen tieferen Baum, wo es viele Punkte gibt, die Ihren Anforderungen ziemlich gut entsprechen sollten.

Weitere Einzelheiten finden Sie Wikipedia:

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

Alternativ können Sie versuchen, einen R-Baum zu bauen. Aber der R-Baum versucht zu balancieren, wodurch es schwieriger wird, die dichtesten Bereiche zu finden. Für Ihre spezielle Aufgabe ist dieser Nachteil des Octree tatsächlich hilfreich! Der R-Baum ist sehr bemüht, die Baumtiefe überall gleich zu halten, so dass jeder Punkt ungefähr zur selben Zeit gefunden werden kann. Sie interessieren sich jedoch nur für die dichten Bereiche, die auf den längsten Wegen im Octree zu finden sind, ohne dass Sie sich noch die eigentlichen Punkte ansehen müssen!

1

Ich würde auch vorschlagen, einen Octree zu verwenden. Das OctoMap Framework ist sehr gut im Umgang mit riesigen 3D-Punktwolken. Es speichert nicht alle Punkte direkt, sondern aktualisiert die Belegungsdichte jedes Knotens (auch 3D-Box genannt). Nachdem der Baum erstellt wurde, können Sie einen einfachen Iterator verwenden, um den Knoten mit der höchsten Dichte zu finden. Wenn Sie die Punktdichte oder Verteilung innerhalb der Knoten modellieren möchten, ist die OctoMap sehr einfach zu verwenden.

Here können Sie sehen, wie es erweitert wurde, um die Punktverteilung mit einem planaren Modell zu modellieren.