Algoritma untuk Menemukan Massa Agregat "Granola Bar" -Seperti Struktur?

Saya seorang peneliti sains planet dan satu proyek yang sedang saya kerjakan adalah N- semua simulasi cincin Saturnus. Tujuan dari penelitian khusus ini adalah untuk menyaksikan partikel-partikel menggumpal di bawah gravitasi diri mereka sendiri dan mengukur massa agregat rumpun versus kecepatan rata-rata semua partikel dalam sel. Kami sedang mencoba mencari tahu apakah ini dapat menjelaskan beberapa pengamatan yang dilakukan oleh pesawat ruang angkasa Cassini selama titik balik matahari musim panas Saturnus ketika struktur besar terlihat melemparkan bayangan pada cincin hampir ujung-ke-atas. Di bawah ini adalah tangkapan layar seperti apa bentuk waktu yang diberikan. (Setiap partikel berdiameter 2 m dan sel simulasi itu sendiri sekitar 700 m.)

Kode yang saya gunakan sudah memuntahkan kecepatan rata-rata di setiap timestep. Yang perlu saya lakukan adalah mencari cara untuk menentukan massa partikel dalam rumpun dan BUKAN partikel liar di antara mereka. Saya tahu posisi setiap partikel, massa, ukuran, dll., Tetapi saya tidak tahu dengan mudah bahwa, katakanlah, partikel 30.000-40.000 bersama dengan 102.000-105.000 membentuk satu untaian yang bagi mata manusia jelas.

Jadi, algoritma yang perlu saya tulis harus berupa kode dengan sesedikit mungkin parameter yang dimasukkan pengguna (untuk replikasi dan objektivitas) yang akan melewati semua posisi partikel, mencari tahu partikel apa yang termasuk rumpun, dan kemudian menghitung massa. Akan lebih bagus jika bisa melakukannya untuk "masing-masing" rumpun / untai yang bertentangan dengan segala sesuatu di atas sel, tetapi saya tidak berpikir saya benar - benar membutuhkannya untuk memisahkan mereka.

Satu-satunya hal yang saya pikirkan adalah melakukan semacam perhitungan jarak N ^{2 di} mana saya akan menghitung jarak antara setiap partikel dan jika, katakanlah, 100 partikel terdekat berada dalam jarak tertentu, maka partikel itu akan dianggap sebagai bagian dari suatu gugus. Tapi itu tampak sangat ceroboh dan saya berharap Anda, orang-orang dan programmer CS mungkin tahu solusi yang lebih elegan?

Diedit dengan saya Solusi: Apa yang saya lakukan adalah untuk mengambil semacam pendekatan tetangga terdekat-/ cluster dan melakukan cepat-n-kotor N ² implementasi pertama. Jadi, ambil setiap partikel, hitung jarak ke semua partikel lain, dan ambang untuk dalam sebuah cluster atau tidak adalah apakah ada partikel N dalam jarak d ( sayangnya, dua parameter yang harus ditetapkan apriori , tetapi seperti yang dikatakan oleh beberapa tanggapan / komentar, saya tidak akan lolos dengan tidak memiliki beberapa dari mereka).

Saya kemudian mempercepatnya dengan tidak menyortir jarak tetapi hanya melakukan pencarian urutan N dan menambah counter untuk partikel dalam d , dan mempercepat hal-hal dengan faktor 6. Kemudian saya menambahkan "pohon programmer bodoh" (karena saya tahu hampir tidak ada tentang kode pohon). Saya membagi sel simulasi menjadi sejumlah set kisi (hasil terbaik ketika ukuran kisi ≈7 d ) di mana kisi-kisi utama berbaris dengan sel, satu kisi diimbangi dengan setengah di x dan y , dan dua lainnya diimbangi dengan 1/4 in ± x dan ± y . Kode kemudian membagi partikel ke dalam kisi-kisi, maka setiap partikel N hanya harus memiliki jarak yang dihitung dengan partikel lain dalam sel itu.

Secara teoritis, jika ini adalah pohon asli, saya harus memesan N * log ( N ) sebagai lawan dari kecepatan N ² . Saya berada di antara keduanya, di mana untuk sub-set 50.000-partikel, saya mendapat peningkatan 17x dalam kecepatan, dan untuk 150.000-partikel sel, saya mendapat peningkatan 38x dalam kecepatan. 12 detik untuk yang pertama, 53 detik untuk yang kedua, 460 detik untuk sel 500.000 partikel. Itu adalah kecepatan yang sebanding dengan berapa lama kode yang diperlukan untuk menjalankan simulasi 1 timestep maju, jadi itu masuk akal pada saat ini. Oh - dan itu sepenuhnya berulir, jadi itu akan membutuhkan prosesor sebanyak yang saya bisa lakukan.

Saran pertama saya adalah untuk memotong masalah Anda menjadi dua masalah: pertama, cari tahu apa yang Anda inginkan dan kemudian cari tahu cara efisien mendapatkan apa yang Anda inginkan. Anda tidak dapat secara efisien mendapatkan sesuatu yang belum Anda tetapkan. Saya akan memasukkan beberapa ide dalam jawaban ini yang dapat membantu Anda menemukan definisi ini. Saya sarankan Anda membuat implementasi ide-ide yang tidak Anda sukai terlebih dahulu, menerapkannya pada beberapa set data yang tidak terlalu besar, mengevaluasi hasilnya dengan tangan, menyesuaikan definisi Anda dan ulangi (mungkin mengajukan pertanyaan lain di sini), sampai Anda puas dengan definisi anda. Setelah itu, saya sarankan Anda mengajukan pertanyaan lain tentang cara menghitung hasil definisi Anda secara efisien (jika Anda masih membutuhkan bantuan).

Jadi, mari kita lihat apa yang sesuai dengan ide intuitif kita tentang 'untai'. Untaian Anda tampaknya terdiri dari titik-titik yang terdistribusi secara kasar, meskipun Anda harus memeriksanya dengan membuat gambar yang diperbesar (dari dataset asli) - resolusi gambar Anda terlalu rendah untuk mengatakan dengan pasti bahwa titik-titik tersebut benar-benar terdistribusi secara seragam secara kasar. . Saya akan menganggap mereka untuk jawaban ini.

Gagasan awal mungkin untuk melihat tetangga terdekat dari setiap titik. Mari kita pilih titik X, panggil tetangga terdekatnya Y dan atur D sebagai jarak antara X dan Y. Kita kemudian melihat lingkaran C di sekitar X dengan jari-jari D * A, di mana A adalah parameter tuning, katakanlah A = 3. Jika X adalah bagian dari untaian, kami berharap bahwa untuk setiap titik Z dalam C, jarak dari Z ke tetangga terdekatnya W hampir sama dengan D. Jika itu secara signifikan lebih pendek, katakan lebih dari A (atau mungkin beberapa parameter lain B) maka X tampaknya dekat dengan titik yang lebih dekat satu sama lain daripada ke X, jadi X mungkin bukan bagian dari untaian.

Namun kriteria ini tidak lengkap. Ini hanya memberikan kriteria untuk mendeteksi 'perbatasan' antara daerah yang padat dengan titik dan daerah yang kurang padat dengan titik. Kita masih harus mengelompokkan poin menjadi untaian.

Ada fitur dalam gambar Anda yang menunjukkan bahwa ini tidak sederhana. Di sudut kanan bawah gambar Anda, ada area yang relatif besar dengan banyak titik nyasar. Stray point ini sendiri terdistribusi secara seragam, jadi jika kita menghapus semua poin di strand di sekitarnya (dan semua poin lainnya), maka kita akan mengharapkan algoritma pendeteksi untai untuk menandai set ini dari stray point sebagai strand! Karena itu kita perlu berhati-hati ketika membuat kelompok kita.

Mungkin ada ide untuk melakukan hal berikut. Kita akan membuat grafik pada titik-titik ini, di mana simpul adalah titik dan ujungnya menandakan bahwa dua titik memiliki kerapatan yang sama. Untuk setiap poin, kami memeriksa kriteria di atas. Jika check out, kami menghubungkan X dengan edge ke semua titik di C. Jika tidak check out, kami tidak menambahkan edge, dan menandai X sebagai 'nyasar'. Setelah melakukan ini untuk setiap titik, kami mempertimbangkan set komponen yang terhubung. Ini harus terdiri dari satu (dalam kasus gambar Anda, tetapi dataset lain mungkin memiliki beberapa) komponen yang terhubung yang terdiri dari semua titik dalam untaian, ditambah (berpotensi banyak) komponen lebih terdiri dari titik-titik nyasar tunggal dan 'untaian strand' ini. Namun, stray stray ini memiliki poin di dalamnya yang telah ditandai sebagai 'stray', jadi Anda bisa mengabaikan komponen yang berisi titik yang telah ditandai sebagai 'stray'.

Bahaya dari ide ini adalah bahwa Anda mungkin memiliki fitur di mana kepadatan untai semakin menurun saat Anda bergerak di sepanjang untai, sampai kerapatan begitu rendah sehingga hanya set poin liar. Karena kriteria kami adalah 'lokal', mungkin tidak mendeteksi ini dan menandai titik-titik nyasar ini sebagai bagian dari untaian. Saya tidak yakin apakah ini akan menjadi masalah: Saya kira sebagian besar poin yang tersesat harus ditangkap oleh kriteria, karena perubahan dalam kepadatan tampaknya cukup mendadak dalam gambar Anda.

Jika masalah ini terjadi, Anda dapat mencoba alternatif untuk hanya mengambil komponen yang terhubung. Untuk setiap titik X, kami menghitung jarak ke tetangga terdekatnya D (X). Kita mulai dari titik dengan minimal D (X) dan melakukan BFS (atau DFS , urutannya tidak masalah). Kami menambahkan titik Y yang D (Y) tidak jauh lebih besar dari D (X) (dengan faktor merdu) yang kami mulai dengan. Jika kita menemukan titik Y yang memiliki terlalu besar D (Y), kita menghapus tepi (X, Y), menandai Y sebagai 'menyimpang' dan bertindak seolah-olah kita tidak pernah mengunjungi Y di BFS kita. Jika disetel ke kanan, ini akan mencegah masalah yang saya jelaskan di atas.

Gagasan alternatif untuk memperbaiki masalah ini bertindak sedikit lebih lokal: Anda bisa melakukan BFS dan melacak D (X) terendah (saya menggunakan D (X) sebagai ukuran kepadatan di sekitar titik) yang paling banyak dijumpai di 10 BFS-langkah sebelumnya, dan jika kita menemukan Y yang memiliki D (Y) yang jauh lebih besar dari D (X) ini, kita melakukan hal yang sama dengan solusi (potensial) lainnya yang saya tawarkan.

Sebagai penafian: semua ide di atas yang saya pikirkan saat ini, saya tidak benar-benar tahu apakah masalah khusus ini telah dipelajari sebelumnya, jadi saya mungkin hanya menumbuhkan omong kosong. Coba saja ide-ide (apakah ide saya atau milik Anda) yang terdengar masuk akal bagi Anda dan cari tahu apakah itu benar-benar berhasil, dan baru kemudian fokus untuk mengimplementasikannya secara efisien.

Menggunakan dekomposisi modular Anda dapat membuat pohon yang akan berisi semua partikel karena daun dan simpul atas akan mengelompok ini. Berdasarkan pohon itu, Anda dapat menentukan ukuran yang diterapkan untuk setiap simpul dari akar ke daun ke bawah. Anda menghentikan traversal ke bawah ini ketika pengukuran mencapai ambang batas yang ditentukan pengguna. Salah satu pengukuran tersebut mungkin adalah kepadatan cembung semua partikel dalam sebuah cluster.

Saya pikir Anda mencari algoritma pembelajaran mesin clustering.

Halaman ini dari perangkat Python SciKit Learn memiliki gambar yang menunjukkan algoritma DBSCAN (Wikipedia) bisa menjadi apa yang Anda cari. Tampaknya ideal karena parameter inputnya adalah ukuran lingkungan, sementara sebagian besar algoritma pengelompokan lainnya menginginkan jumlah cluster, yang tidak akan Anda ketahui sebelumnya.

"Algoritma Berbasis Kepadatan untuk Menemukan Cluster di Database Spasial Besar dengan Kebisingan" Ester, M., HP Kriegel, J. Sander, dan X. Xu, Dalam Prosiding Konferensi Internasional ke-2 tentang Penemuan Pengetahuan dan Penambangan Data, Portland, OR , AAAI Press, hlm. 226–231. 1996

Saya telah memikirkan masalah ini. Saya bukan ahli fisika, jadi bersabarlah.

Tampaknya bukan jarak antara partikel yang diperhitungkan untuk menentukan gumpalan. Apakah medan gravitasi tumpang tindih atau tidak.

Ambil partikel P, dan tentukan partikel apa yang memiliki medan gravitasi yang tumpang tindih.

Kemudian ambil salah satu dari mereka dan lakukan hal yang sama. Tujuan Anda bukan untuk menemukan semua partikel di rumpun, tetapi untuk menemukan batas-batasnya.

Ulangi ini sampai semua rumpun ditemukan.

Sekarang kembali dan tentukan massa rumpun. Anda akan menghilangkan partikel yang tersesat, dan Anda bisa menggunakan batas rumpun untuk menemukan massa.

Saya tidak yakin apakah ini membantu, tetapi hanya itu yang bisa saya pikirkan.

Anda bisa, pada akhir setiap catatan waktu, mengubah data menjadi grafik, menghitung pohon rentang minimum, dan kemudian mulai menghapus tepi yang melebihi ambang batas tertentu. Itu akan memberi Anda rumpun dan cara mudah untuk menghitung melalui partikel di setiap rumpun.