Algorithmus zum Ermitteln der Gesamtmasse von "Granola Bar" -ähnlichen Strukturen?

Ich bin ein planetarwissenschaftlicher Forscher und ein Projekt, an dem ich arbeite, sind N- Körpersimulationen von Saturnringen. Das Ziel dieser speziellen Studie ist es, zu beobachten, wie Partikel unter ihrer eigenen Schwerkraft zusammenklumpen und die Gesamtmasse der Klumpen gegen die mittlere Geschwindigkeit aller Partikel in der Zelle zu messen. Wir versuchen herauszufinden, ob dies einige Beobachtungen der Cassini- Raumsonde während der Sommersonnenwende im Saturn erklären kann, als große Strukturen Schatten auf die fast kantigen Ringe werfen sahen. Unten sehen Sie einen Screenshot, wie ein bestimmter Zeitschritt aussieht. (Jedes Teilchen hat einen Durchmesser von 2 m und die Simulationszelle selbst hat einen Durchmesser von etwa 700 m.)

Der Code, den ich verwende, gibt die mittlere Geschwindigkeit bereits bei jedem Zeitschritt aus. Was ich tun muss, ist, einen Weg zu finden, um die Masse der Partikel in den Klumpen und NICHT die Streupartikel zwischen ihnen zu bestimmen. Ich kenne die Position, Masse, Größe usw. jedes Partikels, aber ich weiß nicht so leicht, dass beispielsweise die Partikel 30.000 bis 40.000 zusammen mit 102.000 bis 105.000 einen Strang bilden, der für das menschliche Auge offensichtlich ist.

Der Algorithmus, den ich schreiben muss, muss also ein Code mit möglichst wenigen vom Benutzer eingegebenen Parametern sein (aus Gründen der Reproduzierbarkeit und Objektivität), der alle Partikelpositionen durchläuft, herausfindet, welche Partikel zu Klumpen gehören, und dann berechnet Masse. Es wäre großartig, wenn es dies für "jeden" Klumpen / Strang tun könnte, im Gegensatz zu allem über der Zelle, aber ich glaube nicht, dass ich es wirklich brauche, um sie zu trennen.

Das einzige, woran ich dachte, war eine Art N ² -Distanzberechnung, bei der ich die Entfernung zwischen jedem Partikel berechnet habe und wenn sich die nächsten 100 Partikel beispielsweise innerhalb einer bestimmten Entfernung befinden, wird dieses Partikel als Teil von a betrachtet Cluster. Aber das scheint ziemlich schlampig zu sein und ich hatte gehofft, dass Sie CS-Leute und Programmierer eine elegantere Lösung finden könnten?

Herausgegeben mit Meiner Lösung: Was ich tat , war eine Art Nearest-Neighbor / Cluster - Ansatzes zu nehmen und tun , um die Quick-n-dirty N ² Implementierung zuerst. Nehmen Sie also jedes Partikel, berechnen Sie den Abstand zu allen anderen Partikeln, und der Schwellenwert für in einem Cluster war, ob sich N Partikel innerhalb des Abstands d befanden (zwei Parameter, die leider a priori festgelegt werden müssen, aber wie von einigen gesagt wurde) Antworten / Kommentare, ich würde nicht durchkommen, wenn ich einige davon nicht hätte).

Ich habe es dann beschleunigt, indem ich nicht die Entfernungen sortiert habe, sondern einfach eine Suche in der Reihenfolge N durchgeführt und einen Zähler für die Partikel innerhalb von d inkrementiert habe . Dann habe ich einen "dummen Programmiererbaum" hinzugefügt (weil ich weiß so gut wie nichts über Baumcodes). Ich teile die Simulationszelle in eine festgelegte Anzahl von Gittern auf (beste Ergebnisse bei einer Gittergröße von ≈7 d ), wobei das Hauptgitter mit der Zelle ausgerichtet ist und ein Gitter in x und y um die Hälfte und die beiden anderen um die Hälfte versetzt sind 1/4 in ± x und ± y . Der Code teilt dann die Partikel in die Gitter auf, wobei für jedes Partikel N nur die Abstände zu den anderen Partikeln in dieser Zelle berechnet werden müssen.

Wenn dies ein echter Baum wäre, müsste ich theoretisch N * log ( N ) anstelle von N ² Geschwindigkeiten bestellen . Ich bin irgendwo dazwischen gekommen, wo ich für eine Teilmenge mit 50.000 Partikeln eine 17-fache Geschwindigkeitssteigerung und für eine Zelle mit 150.000 Partikeln eine 38-fache Geschwindigkeitssteigerung erzielt habe. 12 Sekunden für die erste, 53 Sekunden für die zweite, 460 Sekunden für eine 500.000-Teilchen-Zelle. Dies ist eine vergleichbare Geschwindigkeit wie die Zeit, die der Code benötigt, um den Zeitschritt der Simulation 1 vorwärts auszuführen. Das ist an dieser Stelle also angemessen. Oh - und es ist voll verlegt, so dass es so viele Prozessoren braucht, wie ich darauf werfen kann.

Mein erster Vorschlag ist, Ihr Problem in zwei Probleme aufzuteilen: Erstens, finden Sie heraus, was Sie wollen, und dann, wie Sie effizient erreichen, was Sie wollen. Sie können nicht effizient etwas bekommen, das Sie noch nicht definiert haben. Ich werde einige Ideen in diese Antwort aufnehmen, die Ihnen helfen können, diese Definition zu finden. Ich schlage vor, Sie setzen die Ideen, die Sie zuerst mögen, ineffizient um, wenden sie auf einige nicht zu große Datensätze an, werten die Ergebnisse manuell aus, passen Ihre Definition an und wiederholen sie (möglicherweise stellen Sie hier eine andere Frage), bis Sie zufrieden sind Ihre Definition. Danach schlage ich vor, dass Sie eine weitere Frage stellen, wie Sie das Ergebnis Ihrer Definition effizient berechnen können (falls Sie immer noch Hilfe benötigen).

Lassen Sie uns also sehen, was mit unserer intuitiven Vorstellung von einem "Strang" korrespondieren würde. Ihre Stränge scheinen aus ungefähr gleichmäßig verteilten Punkten zu bestehen. Sie sollten dies jedoch überprüfen, indem Sie ein vergrößertes Bild (des Originaldatensatzes) erstellen. Die Auflösung Ihres Bildes ist zu niedrig, um mit Sicherheit sagen zu können, dass die Punkte tatsächlich ungefähr gleichmäßig verteilt sind . Ich gehe davon aus, dass sie für diese Antwort sind.

Eine anfängliche Idee könnte sein, den nächsten Nachbarn von jedem Punkt zu betrachten. Wählen wir einen Punkt X, nennen wir seinen nächsten Nachbarn Y und setzen D als Abstand zwischen X und Y. Wir betrachten dann den Kreis C um X mit dem Radius D * A, wobei A ein Abstimmungsparameter ist, sagen wir A = 3. Wenn X Teil eines Strangs ist, erwarten wir, dass für jeden Punkt Z in C der Abstand von Z zu seinem nächsten Nachbarn W ungefähr gleich D ist. Wenn er erheblich kürzer ist, sagen Sie mehr als A (oder vielleicht einen anderen Parameter) B) dann ist X anscheinend nahe an Punkten, die viel näher beieinander liegen als an X, also ist X wahrscheinlich nicht Teil eines Strangs.

Dieses Kriterium ist jedoch nicht vollständig. Es gibt nur ein Kriterium zum Erkennen einer "Grenze" zwischen Bereichen, die dicht mit Punkten sind, und Bereichen, die weniger dicht mit Punkten sind. Wir müssen noch Punkte zu Strängen zusammenfassen.

Es gibt eine Funktion in Ihrem Bild, die zeigt, dass dies nicht einfach ist. In der unteren rechten Ecke Ihres Bildes befindet sich ein relativ großer Bereich mit vielen Streupunkten. Diese Streupunkte sind selbst ungefähr gleichmäßig verteilt. Wenn wir also alle Punkte im umliegenden Strang (und alle anderen Punkte) entfernen würden, würden wir erwarten, dass ein Strangerkennungsalgorithmus diesen Satz von Streupunkten als Strang kennzeichnet! Wir müssen daher vorsichtig sein, wenn wir unsere Cluster bilden.

Eine Idee könnte sein, Folgendes zu tun. Wir werden auf diesen Punkten ein Diagramm erstellen, wobei die Eckpunkte die Punkte und Kanten sind, die anzeigen, dass zwei Punkte eine ähnliche Dichte haben. Für jeden Punkt überprüfen wir das obige Kriterium. Wenn es ausgecheckt wird, verbinden wir X mit einer Kante mit allen Punkten in C. Wenn es nicht ausgecheckt wird, fügen wir keine Kante hinzu und markieren X als 'streunend'. Nachdem wir dies für jeden Punkt getan haben, betrachten wir die Menge der verbundenen Komponenten. Diese sollten aus einer einzelnen (im Fall Ihres Bildes, aber andere Datensätze können mehrere) verbundenen Komponenten bestehen, die aus allen Punkten in Strängen bestehen, plus (möglicherweise viel) mehr Komponenten, die aus einzelnen Streupunkten und diesen "Streusträngen" bestehen. Diese Streustränge weisen jedoch Punkte auf, die als "streunend" markiert wurden, sodass Sie einfach alle Komponenten ignorieren können, die einen Punkt enthalten, der als "streunend" markiert wurde.

Diese Idee birgt die Gefahr, dass Sie ein Feature haben, bei dem die Dichte eines Strangs bei der Bewegung entlang des Strangs progressiv abnimmt, bis die Dichte so gering ist, dass es sich nur um eine Reihe von Streupunkten handelt. Da unser Kriterium "lokal" ist, kann es sein, dass es dies nicht erkennt und diese Streupunkte als Teil des Strangs markiert. Ich bin mir nicht sicher, ob dies ein Problem sein wird: Ich schätze, die meisten Streupunkte sollten vom Kriterium erfasst werden, da Änderungen in der Dichte in Ihrem Bild ziemlich abrupt erscheinen.

Wenn dieses Problem auftritt, können Sie eine Alternative zur reinen Entnahme der angeschlossenen Komponenten versuchen. Für jeden Punkt X berechnen wir die Entfernung zum nächsten Nachbarn D (X). Wir beginnen am Punkt mit minimalem D (X) und führen ein BFS durch (oder DFS , die Reihenfolge spielt keine Rolle). Wir addieren jeden Punkt Y, dessen D (Y) nicht viel größer ist als das D (X) (um einen einstellbaren Faktor), mit dem wir begonnen haben. Wenn wir auf einen Punkt Y stoßen, der ein zu großes D (Y) hat, entfernen wir die Kante (X, Y), markieren Y als "streunend" und tun so, als ob wir Y in unserem BFS nie besucht hätten. Wenn es richtig eingestellt ist, sollte dies das oben beschriebene Problem verhindern.

Eine alternative Idee zur Behebung dieses Problems ist etwas lokaler: Sie könnten ein BFS durchführen und das niedrigste D (X) verfolgen (ich verwende D (X) als Maß für die Dichte um einen Punkt), das höchstens bei 10 liegt BFS-Schritte zuvor, und wenn wir auf ein Y mit einem D (Y) stoßen, das viel größer ist als dieses D (X), tun wir dasselbe wie die andere (potenzielle) Lösung, die ich angeboten habe.

Als Haftungsausschluss: Alle oben genannten Ideen, die ich mir gerade ausgedacht habe, ich weiß nicht wirklich, ob dieses spezielle Problem zuvor untersucht wurde, so dass ich möglicherweise nur Unsinn sprießen kann. Probieren Sie einfach die Ideen aus (ob meine oder Ihre eigenen), die für Sie vernünftig klingen, und prüfen Sie, ob sie wirklich funktionieren, und konzentrieren Sie sich dann darauf, sie effizient umzusetzen.

Mithilfe der modularen Zerlegung können Sie einen Baum erstellen, der alle Partikel enthält, während Blätter und obere Knoten diese gruppieren. Basierend auf diesem Baum können Sie Kennzahlen definieren, die auf jeden Knoten von der Wurzel bis zu den Blättern nach unten angewendet werden. Sie stoppen diese Abwärtsbewegung, wenn die Messungen benutzerdefinierte Schwellenwerte erreichen. Eine solche Messung kann die Dichte der konvexen Hülle aller Partikel in einem Cluster sein.

Ich denke, Sie sind auf der Suche nach einem Algorithmus zum maschinellen Lernen von Clustern.

Diese Seite aus dem Python SciKit Learn Toolkit enthält Bilder, die darauf hindeuten, dass der DBSCAN-Algorithmus (Wikipedia) genau das ist, wonach Sie suchen. Es scheint ideal zu sein, da der Eingabeparameter die Nachbarschaftsgröße ist, während die meisten anderen Cluster-Algorithmen die Anzahl der Cluster wünschen, die Sie im Voraus nicht kennen würden.

"Ein dichtebasierter Algorithmus zur Entdeckung von Clustern in großen räumlichen Datenbanken mit Rauschen" Ester, M., HP Kriegel, J. Sander und X. Xu, In Proceedings der 2. Internationalen Konferenz über Wissensentdeckung und Data Mining, Portland, OR AAAI Press, S. 226–231. 1996

Ich habe über dieses Problem nachgedacht. Ich bin kein Physikexperte, also nimm es mit.

Es scheint, dass es nicht der Abstand zwischen den Partikeln ist, der zur Bestimmung der Klumpen zählt. Es ist wichtig, ob sich die Gravitationsfelder überlappen oder nicht.

Nehmen Sie ein Teilchen P und bestimmen Sie, welche anderen Teilchen überlappende Schwerkraftfelder haben.

Dann nimm eins von denen und mache dasselbe. Ihr Ziel ist es nicht, alle Partikel in der Ansammlung zu finden, sondern ihre Grenzen zu finden.

Wiederholen Sie diesen Vorgang, bis alle Klumpen gefunden wurden.

Nun gehe zurück und bestimme die Masse der Klumpen. Sie haben Streupartikel beseitigt, und Sie können die Büschelgrenzen verwenden, um die Masse zu finden.

Ich bin mir nicht sicher, ob das hilft, aber es ist alles, was ich mir vorstellen kann.

Sie können am Ende jedes Zeitschritts die Daten in ein Diagramm konvertieren, den minimalen Spannbaum berechnen und dann Kanten entfernen, die einen bestimmten Schwellenwert überschreiten. Das sollte Ihnen Klumpen und eine einfache Möglichkeit bieten, die Partikel in jedem Klumpen durchzuzählen.