Algorytm znajdowania masy agregatu „Granola Bar” - podobnych struktur?

Jestem badaczem nauk planetarnych, a jednym z projektów, nad którymi pracuję, są symulacje N -pierścieni pierścieni Saturna. Celem tego konkretnego badania jest obserwacja, jak cząstki zbijają się pod własnym ciężarem własnym i mierzą łączną masę grudek w porównaniu ze średnią prędkością wszystkich cząstek w komórce. Próbujemy dowiedzieć się, czy to może wyjaśnić niektóre obserwacje dokonane przez sondę Cassini podczas letniego przesilenia Saturna, gdy zaobserwowano duże struktury rzucające cienie na niemal krawędziowe pierścienie. Poniżej znajduje się zrzut ekranu pokazujący jak wygląda dany czas. (Każda cząstka ma średnicę 2 m, a sama komórka symulacyjna ma około 700 m średnicy.)

The code I'm using already spits out the mean velocity at every timestep. What I need to do is figure out a way to determine the mass of particles in the clumps and NOT the stray particles between them. I know every particle's position, mass, size, etc., but I don't know easily that, say, particles 30,000-40,000 along with 102,000-105,000 make up one strand that to the human eye is obvious.

Tak więc algorytm, który muszę napisać, musiałby być kodem z jak najmniejszą liczbą parametrów wprowadzonych przez użytkownika (dla możliwości replikacji i obiektywności), który przechodziłby przez wszystkie pozycje cząstek, ustalał, które cząstki należą do skupisk, a następnie obliczał masa. Byłoby wspaniale, gdyby mógł to zrobić dla „każdego” kępu / nici w przeciwieństwie do wszystkiego w komórce, ale nie sądzę, że tak naprawdę potrzebuję tego, aby je rozdzielić.

Jedyne, o czym myślałem, to jakieś obliczenie odległości N ^{2, w} którym obliczałbym odległość między każdą cząsteczką, a jeśli powiedzmy, że najbliższe 100 cząstek znajdowało się w pewnej odległości, wówczas cząstka ta byłaby uważana za część grupa. Ale to wydaje się dość niechlujne i miałem nadzieję, że ludzie CS i programiści mogą wiedzieć o bardziej eleganckim rozwiązaniu?

Edytowany ze moje rozwiązanie: Co zrobiłem było podjąć rodzaju najbliższego sąsiedztwa podejścia / klastra i zrobić szybki-n-brudne N ² pierwsze wdrożenie. Więc weź każdą cząsteczkę, oblicz odległość do wszystkich innych cząstek, a próg dla gromady był, czy nie, czy w odległości d znajduje się N cząstek (dwa parametry, które niestety trzeba ustawić a priori , ale jak powiedzieli niektórzy odpowiedzi / komentarze, nie miałem zamiaru uciec od braku niektórych z nich).

Przyspieszyłem to, nie sortując odległości, ale po prostu wykonując rozkaz N wyszukiwania i zwiększając licznik cząstek w obrębie d , i to przyspieszyłem współczynnik sześciokrotnie. Potem dodałem „głupie drzewo programisty” (bo wiem prawie nic o kodach drzew). I dzieli się na komórki symulacji do zadanej liczby siatek (najlepsze wyniki, gdy rozmiar siatki ≈7 d ), w którym główne linie siatki w górę z komórką jedna kratka jest przesunięta o połowę w X i Y , a pozostałe dwa są przesunięte 1/4 w ± x i ± y . Kod dzieli następnie cząstki na siatki, a następnie każda cząstka N musi mieć tylko obliczone odległości od innych cząstek w tej komórce.

Teoretycznie, gdyby to było prawdziwe drzewo, powinienem uzyskać porządek N * log ( N ) w przeciwieństwie do prędkości N ² . Dotarłem gdzieś między nimi, gdzie dla podzbioru 50 000 cząstek miałem 17-krotny wzrost prędkości, a dla komórki 150 000 cząstek, miałem 38-krotny wzrost prędkości. 12 sekund dla pierwszej, 53 sekundy dla drugiej, 460 sekund dla komórki 500 000 cząstek. Są to porównywalne prędkości do tego, ile czasu zajmuje wykonanie kodu w kroku 1 symulacji do przodu, więc w tym momencie jest to uzasadnione. Och - i jest w pełni wątkowy, więc zajmie tyle procesorów, ile tylko mogę.

Moją pierwszą sugestią jest podzielenie twojego problemu na dwa problemy: najpierw wymyśl, co chcesz, a następnie wymyśl, jak skutecznie uzyskać to, czego chcesz. Nie możesz skutecznie uzyskać czegoś, czego jeszcze nie zdefiniowałeś. W tej odpowiedzi przedstawię kilka pomysłów, które mogą pomóc ci znaleźć tę definicję. Sugeruję, abyś najpierw wdrożył nieefektywne pomysły, które ci się podobają, zastosuj je do kilku niezbyt dużych zestawów danych, oceń wyniki ręcznie, dostosuj swoją definicję i powtórz (prawdopodobnie zadając tutaj kolejne pytanie), dopóki nie będziesz zadowolony twoja definicja. Następnie sugeruję, abyś zadał kolejne pytanie, jak efektywnie obliczyć wynik swojej definicji (jeśli nadal potrzebujesz pomocy).

Zobaczmy więc, co odpowiadałoby naszej intuicyjnej idei „nici”. Wygląda na to, że twoje pasma składają się z mniej więcej równomiernie rozmieszczonych punktów, ale powinieneś to sprawdzić, wykonując zbliżenie w powiększeniu (z oryginalnego zestawu danych) - rozdzielczość obrazu jest zbyt niska, aby stwierdzić z całą pewnością, że punkty naprawdę są z grubsza równomiernie rozmieszczone . Zakładam, że są za tą odpowiedzią.

Początkowym pomysłem może być spojrzenie na najbliższego sąsiada każdego punktu. Wybierzmy punkt X, nazwijmy jego najbliższego sąsiada Y i ustawmy D jako odległość między X i Y. Następnie patrzymy na okrąg C wokół X o promieniu D * A, gdzie A jest parametrem strojenia, powiedzmy A = 3. Jeśli X jest częścią nici, oczekujemy, że dla każdego punktu Z w C odległość od Z do najbliższego sąsiada W jest mniej więcej taka sama jak D. Jeśli jest znacznie krótsza, powiedz więcej niż A (lub może jakiś inny parametr B) wtedy X najwyraźniej zbliża się do punktów, które są znacznie bliżej siebie niż do X, więc X prawdopodobnie nie jest częścią nici.

To kryterium nie jest jednak kompletne. Daje jedynie kryterium wykrycia „granicy” między obszarami gęstymi punktami i obszarami mniej gęstymi punktami. Wciąż musimy grupować punkty razem w pasma.

Na twoim zdjęciu jest funkcja, która pokazuje, że to nie jest proste. W prawym dolnym rogu zdjęcia znajduje się stosunkowo duży obszar z dużą ilością zagubionych punktów. Te zbłąkane punkty same w sobie są z grubsza równomiernie rozmieszczone, więc gdybyśmy usunęli wszystkie punkty z pasma wokół niego (i wszystkie inne punkty), wówczas spodziewalibyśmy się, że każdy algorytm wykrywający pasmo oznaczy ten zestaw pasmowych punktów jako pasmo! Dlatego musimy zachować ostrożność przy tworzeniu naszych klastrów.

Pomysł może być następujący. Zrobimy wykres na tych punktach, gdzie wierzchołki są punktami, a krawędzie oznaczają, że dwa punkty mają podobną gęstość. Dla każdego punktu sprawdzamy powyższe kryterium. Jeśli się wyewidencjonuje, łączymy X krawędzią ze wszystkimi punktami w C. Jeśli nie wyewidencjonowuje, nie dodajemy żadnej krawędzi i oznaczamy X jako „zbłąkany”. Po wykonaniu tego dla każdego punktu, bierzemy pod uwagę zestaw połączonych komponentów. Powinny one składać się z jednego (w przypadku twojego obrazu, ale inne zestawy danych mogą mieć wiele) połączonego komponentu składającego się ze wszystkich punktów w pasmach, a także (potencjalnie dużo) więcej komponentów składających się z pojedynczych punktów błąkających się i tych „pasm błąkających się”. Jednak te zbłąkane pasma mają punkty, które zostały oznaczone jako „zbłąkane”, więc możesz po prostu zignorować każdy element zawierający punkt oznaczony jako „zbłąkany”.

Niebezpieczeństwo związane z tą ideą polega na tym, że możesz mieć cechę polegającą na tym, że gęstość nici stopniowo zmniejsza się podczas przesuwania się wzdłuż nici, aż gęstość będzie tak niska, że ​​będzie to tylko zbiór zbłąkanych punktów. Ponieważ nasze kryterium jest „lokalne”, może nie wykryć tego i oznaczyć te zbłąkane punkty jako część pasma. Nie jestem pewien, czy to będzie problem: Myślę, że większość zbłąkanych punktów powinno zostać uwzględnione przez kryterium, ponieważ zmiany gęstości wydają się dość gwałtowne na twoim zdjęciu.

Jeśli ten problem wystąpi, możesz wypróbować alternatywę dla samego połączenia podłączonych komponentów. Dla każdego punktu X obliczamy odległość do najbliższego sąsiada D (X). Zaczynamy od punktu z minimalnym D (X) i wykonujemy BFS (lub DFS , kolejność nie ma znaczenia). Dodajemy dowolny punkt Y, którego D (Y) nie jest znacznie większy niż D (X) (przez przestrajalny czynnik), od którego zaczęliśmy. Jeśli napotkamy punkt Y, który ma zbyt duże D (Y), usuwamy krawędź (X, Y), oznaczamy Y jako „zbłąkane” i zachowujemy się tak, jakbyśmy nigdy nie odwiedzili Y w naszym BFS. Prawidłowe dostrojenie powinno zapobiec problemowi, który opisuję powyżej.

Alternatywny pomysł na rozwiązanie tego problemu działa nieco bardziej lokalnie: możesz zrobić BFS i śledzić najniższe D (X) (używam D (X) jako miary gęstości wokół punktu) napotkanego co najwyżej 10 BFS-kroki wcześniej i jeśli napotkamy Y, które ma D (Y), które jest znacznie większe niż to D (X), robimy to samo, co inne (potencjalne) rozwiązanie, które zaoferowałem.

Jako wyłączenie odpowiedzialności: wszystkie powyższe pomysły, które wymyśliłem na miejscu, tak naprawdę nie wiem, czy ten konkretny problem był już wcześniej badany, więc mogę po prostu wyrastać z bzdur. Po prostu wypróbuj pomysły (moje lub własne), które brzmią dla ciebie rozsądnie i dowiedz się, czy naprawdę działają, i dopiero wtedy skoncentruj się na ich efektywnym wdrażaniu.

Za pomocą rozkładu modułowego można utworzyć drzewo, które będzie zawierało wszystkie cząstki, ponieważ liście i górne węzły będą je grupować. Na podstawie tego drzewa można zdefiniować miary, które będą stosowane do każdego jego węzła, od korzenia do liści w dół. Zatrzymanie tego przejścia w dół następuje, gdy pomiary osiągną progi zdefiniowane przez użytkownika. Jednym z takich pomiarów może być gęstość wypukłego kadłuba wszystkich cząstek w gromadzie.

Myślę, że szukasz algorytmu klastrowego uczenia maszynowego.

Ta strona z zestawu narzędzi Python SciKit Learn zawiera zdjęcia sugerujące, że algorytm DBSCAN (Wikipedia) może być tym, czego szukasz. Wydaje się idealny, ponieważ jego parametrem wejściowym jest wielkość sąsiedztwa, podczas gdy większość innych algorytmów klastrowania chce liczby klastrów, których nie znasz z góry.

„Algorytm oparty na gęstości do odkrywania klastrów w dużych przestrzennych bazach danych z hałasem” Ester, M., HP Kriegel, J. Sander i X. Xu, w toku 2. międzynarodowej konferencji na temat odkrywania wiedzy i eksploracji danych, Portland, OR , AAAI Press, s. 226–231. 1996

Myślałem o tym problemie. Nie jestem ekspertem od fizyki, więc proszę o wyrozumiałość.

Wydaje się, że to nie odległość między cząstkami się liczy, aby określić grudki. To, czy pola grawitacyjne zachodzą na siebie, czy nie.

Weź cząstkę P i określ, jakie inne cząstki mają nakładające się pola grawitacyjne.

Następnie weź jedną z nich i zrób to samo. Twoim celem nie jest znalezienie wszystkich cząstek w kępie, ale znalezienie jej granic.

Powtarzaj to, aż zostaną znalezione wszystkie grudki.

Teraz wróć i określ masę kęp. Pozbędziesz się zbłąkanych cząstek i możesz użyć granic kępy, aby znaleźć masę.

Nie jestem pewien, czy to pomaga, ale to wszystko, co mogłem wymyślić.

Na koniec każdego pomiaru czasu możesz przekonwertować dane na wykres, obliczyć minimalne drzewo opinające, a następnie rozpocząć usuwanie krawędzi przekraczających określony próg. To powinno dać ci grudki i łatwy sposób na wyliczenie cząstek w każdej grudce.