Editorial Ilmu Komputer & AI
Open AccessOA2026
Penemuan Petri Net Bottom-Up Terpandu Monotonisitas: Kerangka Kerja SPECpp
Pendekatan bottom-up untuk penemuan proses yang memanfaatkan sifat monotonisitas place guna mengatasi ruang kandidat yang eksponensial
Leah Tacke genannt Unterberg; Lisa L. Mannel; Wil M. P. van der Aalst· 2026· DOI 10.48550/arXiv.2608.09398
Masalah inti
Penemuan proses adalah salah satu tantangan utama dalam process mining. Petri net sangat menarik karena konstruksi lokal yang sederhana dapat mengekspresikan perilaku kompleks, termasuk konkurensi. Meskipun perilaku globalnya mungkin sulit dianalisis, setiap place dapat dicirikan secara efisien menggunakan sifat monotonisitas, sehingga memungkinkan penemuan bottom-up. Berbeda dari pendekatan top-down seperti Inductive Miner, yang bergantung pada konstruksi yang telah ditentukan untuk sekuens, pilihan, loop, dan konkurensi, pendekatan yang diusulkan memungkinkan struktur semacam itu muncul secara organik dan dapat memanfaatkan kekuatan ekspresif penuh Petri net, termasuk konstruksi free-choice dan dependensi jangka panjang. Tantangan utamanya adalah jumlah place kandidat dan kombinasinya yang eksponensial. Para penulis menyajikan kerangka kerja SPECpp, yang mengimplementasikan strategi untuk memperoleh model berkualitas tinggi di bawah batasan waktu dan sumber daya. SPECpp mendukung eksperimen cepat dan digunakan untuk mengevaluasi strategi tersebut menggunakan data peristiwa sintetis maupun nyata.
Inovasi
Para penulis mengevaluasi SPECpp menggunakan data peristiwa sintetis maupun nyata. Data sintetis memungkinkan eksperimen terkendali untuk menilai dampak berbagai strategi terhadap kualitas model dan waktu komputasi. Data peristiwa nyata menguji penerapan kerangka kerja dalam situasi praktis. Hasilnya menunjukkan bahwa SPECpp dapat memperoleh model berkualitas tinggi di bawah batasan waktu dan sumber daya. Pendekatan bottom-up berhasil menemukan konstruksi free-choice dan dependensi jangka panjang yang mungkin terlewat oleh metode top-down seperti Inductive Miner. Jumlah place kandidat yang eksponensial dikelola melalui strategi yang diimplementasikan, sehingga memungkinkan penemuan model kompleks tanpa konstruksi yang telah ditentukan. Kemampuan kerangka kerja untuk mendukung eksperimen cepat memfasilitasi perbandingan berbagai strategi dan trade-off-nya.
Penemuan proses adalah salah satu tantangan utama dalam process mining. Petri net sangat menarik karena konstruksi lokal yang sederhana dapat mengekspresikan perilaku kompleks, termasuk konkurensi. Meskipun perilaku globalnya mungkin sulit dianalisis, setiap place dapat dicirikan secara efisien menggunakan sifat monotonisitas, sehingga memungkinkan penemuan bottom-up. Berbeda dari pendekatan top-down seperti Inductive Miner, yang bergantung pada konstruksi yang telah ditentukan untuk sekuens, pilihan, loop, dan konkurensi, pendekatan yang diusulkan memungkinkan struktur semacam itu muncul secara organik dan dapat memanfaatkan kekuatan ekspresif penuh Petri net, termasuk konstruksi free-choice dan dependensi jangka panjang. Tantangan utamanya adalah jumlah place kandidat dan kombinasinya yang eksponensial. Para penulis menyajikan kerangka kerja SPECpp, yang mengimplementasikan strategi untuk memperoleh model berkualitas tinggi di bawah batasan waktu dan sumber daya. SPECpp mendukung eksperimen cepat dan digunakan untuk mengevaluasi strategi tersebut menggunakan data peristiwa sintetis maupun nyata.
Kerangka kerja SPECpp mengadopsi strategi penemuan bottom-up. Alih-alih memecah event log secara rekursif menggunakan konstruksi process tree yang telah ditentukan, kerangka ini terlebih dahulu mengidentifikasi place kandidat—struktur Petri net lokal—lalu menggabungkannya menjadi model lengkap. Faktor pemungkin utamanya adalah penggunaan sifat monotonisitas untuk mencirikan setiap place secara efisien. Sebuah place dalam Petri net dapat dijelaskan melalui pre-set dan post-set transisinya. Monotonisitas memungkinkan evaluasi apakah place kandidat valid terhadap event log tanpa memeriksa semua marking yang mungkin secara menyeluruh. Secara formal, untuk place dengan pre-set dan post-set , place tersebut valid jika untuk setiap trace dalam log, jumlah kemunculan transisi di yang menyala sebelum transisi di memenuhi batasan monotonisitas tertentu. Kerangka kerja ini mengimplementasikan strategi untuk menangani jumlah place kandidat dan kombinasinya yang eksponensial, termasuk pruning, ranking, dan kombinasi inkremental. Arsitektur keseluruhannya diilustrasikan di bawah ini:
Mengapa penting
Kerangka kerja SPECpp merepresentasikan pergeseran signifikan dari penemuan proses top-down ke bottom-up. Dengan memanfaatkan sifat monotonisitas, kerangka ini mencirikan setiap place secara efisien, sehingga ruang kandidat yang eksponensial menjadi tertangani. Hal ini memungkinkan penemuan Petri net yang memanfaatkan kekuatan ekspresif penuh dari formalisme tersebut, termasuk konstruksi yang sulit ditangkap dengan pola yang telah ditentukan. Tantangan utamanya tetap ledakan kombinatorial place kandidat dan kombinasinya. Strategi yang diimplementasikan dalam SPECpp mengatasinya melalui pruning, ranking, dan penggabungan place secara inkremental. Evaluasi pada data sintetis dan nyata menunjukkan efektivitas kerangka kerja, tetapi juga menyoroti perlunya penelitian lebih lanjut tentang skalabilitas dan kualitas model yang ditemukan. Kemampuan untuk mendukung eksperimen cepat menjadi kekuatan utama, memungkinkan peneliti mengeksplorasi berbagai strategi dan konfigurasi. Pekerjaan selanjutnya dapat berfokus pada optimalisasi langkah kombinasi dan integrasi sifat monotonisitas tambahan untuk lebih mengurangi ruang pencarian.
Siapa yang sebaiknya membaca
Praktisi dan peneliti ilmu komputer
Membuka konten member…