Process mining with alpha++ algorithm
2 likes2,509 views
Dokumen ini menganalisis dan menerapkan algoritma process mining Alpha, Alpha+, dan Alpha++ untuk merekonstruksi proses bisnis dari log event yang ada. Implementasi dilakukan secara manual dan menggunakan perangkat lunak ProM. Algoritma Alpha++ mampu mendeteksi ketergantungan implisit yang tidak dapat dideteksi algoritma Alpha dan Alpha+."
Process mining with alpha++ algorithm
- 1. 2013 Analisa dan Implementasi Proses Bisnis Menggunakan Algoritma Alpha, Alpha+, dan Alpha++ Audit Perangkat Lunak Dokumen ini digunakan untuk memenuhi Pra UAS Mata Kuliah Audit Perangkat Lunak yang diampu oleh Prof. Ir. Riyanarto Sarno, SE, MSc, PhD Oleh Fadlika Dita Nurjanto 5110100132 Kelas Audit A Jurusan Teknik Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya
- 2. A. Pendahuluan Process mining bertujuan untuk mengesktrak informasi dari event log dari sebuah case dengan tujuan untuk menangkap proses bisnis yang telah tereksekusi. Process mining sangatlah berguna dalam situasi di mana kejadian direkam tetapi tidak ada sistem yang mengarahkan orang-orang untuk bekerja dengan prosedur yang sesuai. Salah satu contohnya adalah proses yang terjadi dalam diagnosis rumah sakit di mana diagnosa yang dilakukan selalu dicatat di sistem informasi rumah sakit, tetapi alur proses tidak selalu sesuai dengan prosedur yang ada. Salah satu jenis algoritma process mining sederhana yang dapat digunakan untuk menangkap proses bisnis dari event log yang adalah adalah algoritma Alpha. Dalam pelaksanaannya, algoritma Alpha memiliki berbagai kekurangan, yang nantinya akan diperbaiki oleh algoritma Alpha+ dan Alpha++. B. Implementasi Pada percobaan kali ini akan ditunjukkan contoh implementasi algoritma Alpha, Alpha+ dan Alpha++. Implementasi akan dilakukan secara manual kemudian dibandingkan dengan hasil implementasi mining event log dengan menggunakan Tools ProM. Untuk itu, langkah pertama yang dilakukan adalah menentukan contoh case yang akan digunakan pada laporan berikut ini. Case yang digunakan pada percobaan kali ini adalah sebagai berikut : CASE 1 : A C D H O W P S T V CASE 2 : A C D H O W Q S U V CASE 3 : A C F N R CASE 4 : A C F Z Y R CASE 4 : A C F Z Y R CASE 4 : A C F Z Y R CASE 4 : A C F Z Y R CASE 5 : A C F Y Z R CASE 5 : A C F Y Z R CASE 5 : A C F Y Z R CASE 5 : A C F Y Z R CASE 6 : A C D H G H O W P S T V CASE 7 : A C D H G H O W Q S U V CASE 8 : A C E I L W P S T V CASE 9 : A C E J L W Q S U V CASE 10 : A C D H G H G H O W Q S U V CASE 11 : A B B C F N R CASE 12 : A B B C D H O W P S T V Dari case tersebut, akan dilakukan percobaan dengan menggunakan 3 algoritma, yaitu Alpha, Alpha+, dan Alpha++.
- 3. 1. Algoritma Alpha Langkah-langkah yang digunakan dalam Algoritma Alpha untuk menemukan Workflow Net / Petri Net dari case yang sudah diberikan adalah sebagai berikut : 1) 2) 3) 4) 5) 6) 7) 8) Membuat sekumpulan transisi dari event log pada Workflow net ( ) Membuat sekumpulan transisi output dari source place pada Workflow net ( ) Membuat sekumpulan transisi input dari sink place pada Workflow net ( ) Pada langkah ke-4 dan 5, digunakan untuk menentukan place dari Workflow net yang sudah ditemukan. Pada langkah ke-4 algoritma 留 menentukan Transisi mana yang berelasi secara casual. Sehingga untuk setiap tuple (A, B) setiap transisi di set A akan berelasi secara causal pada semua transisi di set B. Dan tidak ada relasi di antara A dan B yang saling mengikuti (follow) satu sama lain Set hasil dari langkah-4 diperbaiki dengan hanya mengambil elemen yang paling besar. Langkah ke-5 menentukan jumlah pasti places yang dimiliki oleh Workflow net. Places yang sebelumnya diidentifikasi dibuat. Masing-masing place dihubungkan dengan transisi input/output yang bersesuaian. Algoritma kemudian mengembalikan Workflow net yang diperoleh dari langkahlangkah sebelumnya. Detail langkah-langkah dalam Algoritma 留 adalah sebagai berikut: 1) Membuat Sekumpulan Transisi di Workflow net ( ) Dari event log di atas, didapatkan transisi pada workflow adalah sebagai berikut: A B C D E F G H I J L O P Q R S T U V X Y Z Persamaan yang digunakan untuk mencari { adalah | 2) Membuat Transisi Output Source Place Pada Workflow net ( ) { | Persamaan yang digunakan adalah Transisi output yang dihasilkan adalah A 3) Membuat Transisi Input Sink Place Pada Workflow net ( { | Persamaan yang digunakan adalah ) N
- 4. Transisi input yang dihasilkan adalah R dan V 4) Algoritma 留 Menentukan Transisi Mana Yang Berelasi Secara Casual Persamaan yang digunakan adalah { | 5) Menentukan Jumlah Pasti Places yang Dimiliki Oleh Workflow net Persamaan yang digunakan adalah { | Dari langkah 4 dan 5, tuple yang dihasilkan adalah sebagai berikut : (A), (B, C) p1 (B) one loop (C), (D, E, F) p2 (D), (H) p3 (E), (I, J) p4 (F), (N, Y, Z) p5 (H), (G) p? (H), (O) p6 (I, J), (L) p7 (L), (W) p8 (O), (W) p9 (W), (P, Q) p10 (P, Q), (S) p11 (S), (T, U) p12 (T, U), (V) p13 (N), (R) p14 (Z, Y), (R) p15 Total place yang diketahui ada 15 place. 6) Membuat Place yang Sudah Teridentifikasi Sebelumnya Persamaan yang digunakan pada tahap ini adalah { { . Place yang sudah teridentifikasi adalah sebagai berikut : |
- 5. p1 p6 p11 p2 p7 p12 p3 p8 p13 i o p4 p9 p14 p5 p10 p15 7) Menghubungkan place-place yang ada dengan input dan output yang tersedia Setelah place-place sudah teridentifikasi, langkah berikutnya adalah menghubungkan sehingga menjadi Petrinet yang saling terhubung. Perbandingan implementasi case dengan menggunakan plugin Alpha Miner di Prom 6.2. Tahap-tahapnya adalah sebagai berikut. Dalam contoh berikut, digunakan file XES yang merepresentasikan event log dari case yang dijalankan. File XES diimport lewat ProM 6.2 dan kemudian dianalisa
- 6. dengan menggunakan plugin Alpha Algorithm. Hasilnya adalah Petrinet yang terbentuk dan merepresentasikan workflow pada case yang dijalankan.
- 7. Perlu diperhatikan, ada 1 event yang tidak terhubung dengan event yang lainnya. Event ini adalah event B, di mana pada event log terlihat bahwa event B bersifat length-one-loop sehingga tidak dapat terdeteksi jika menggunakan algoritma Alpha. Kekurangan ini akan ditangani oleh algoritma Alpha+.
- 8. 2. Algoritma Alpha+ Algoritma Alpha+ merupakan algoritma perbaikan dari kekurangan pada algoritma Alpha biasa. Kekurangan-kekurangan algoritma Alpha antara lain adalah : length-one-loop, length-two-loop, invisible task, duplicate task, implicit places, dan non-free-choice. Algoritma Alpha+ ini memperbaiki kekurangan algoritma Alpha pada bagian short-loop, di mana salah satu jenisnya adalah length-one-loop. Implementasi kali ini menggunakan case yang sama dengan case yang digunakan pada implementasi algoritma Alpha sebelumnya. Casenya adalah sebagai berikut : CASE 1 : A C D H O W P S T V CASE 2 : A C D H O W Q S U V CASE 3 : A C F N R CASE 4 : A C F Z Y R CASE 4 : A C F Z Y R CASE 4 : A C F Z Y R CASE 4 : A C F Z Y R CASE 5 : A C F Y Z R CASE 5 : A C F Y Z R CASE 5 : A C F Y Z R CASE 5 : A C F Y Z R CASE 6 : A C D H G H O W P S T V CASE 7 : A C D H G H O W Q S U V CASE 8 : A C E I L W P S T V CASE 9 : A C E J L W Q S U V CASE 10 : A C D H G H G H O W Q S U V CASE 11 : A B B C F N R CASE 12 : A B B C D H O W P S T V Seperti diketahui sebelumnya pada hasil dari implementasi algoritma Alpha ada beberapa event yang terisolir dari event-event yang lain karena bersifat length-one-loop sehingga pada sebuah case dapat dijalankan lebih dari 1 kali. Langkah-langkah pada implementasi Algoritma Alpha+ adalah sebagai berikut : 1) Menentukan event log yang akan dianalisa ( ). pada kasus kali ini adalah {ACDHOWPSTV, ACDHOWQSUV, ..., ABBCDHOWPSTV} 2) Mengidentifikasi Length-one-loop yang terjadi pada transisi-transisi dalam sebuah case ( ). Perhatikan pada yang ada, ada beberapa case memiliki length-one-loop. Length loop yang ditemukan antara lain = {B} pada Case 12 {ABBCDHOWPSTV} 3) Dengan menggunakan algoritma Alpha, kita identifikasi place yang terbentuk berdasarkan hubungan causal dan direct succession antara transition-transition yang ada. Dari place yang ada, identifikasi place yang memiliki arc akses langsung ke . Disimbolkan dengan . yang berhasil diidentifikasi adalah = {p1 B}
- 9. 4) Menghapus seluruh length-one-loop transition menggunakan algoritma Alpha. Pada kasus kali ini, N, O, P, Q, R, S, T, U, V, X, Y, Z} untuk kemudian diproses = {A, C, D, E, F, G, H, I, J, L, 5) Menemukan Place Dengan Menggunakan Algoritma Alpha Dengan menggunakan Algoritma Alpha, cari place yang digunakan untuk menghubungkan transition yang ada. . Place yang ditemukan adalah = {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15}. 6) Penggabungan Struktur Transition Kemudian dilakukan penggabungan struktur transition antara struktur yang dihasilkan oleh algoritma Alpha dengan daftar transition yanng bersifat length-oneloop. Rumus yang digunakan adalah D, E, F, G, H, I, J, L,N, O, P,Q ,R, S, T, U, V, X, Z} . Sehingga = {A, B, C, 7) Penggabungan Transition Dengan Place Arc yang telah dihasilkan oleh algoritma Alpha disimpan dan digabungkan dengan . Rumusnya adalah Ditemukan = {Ap1, p1B, Bp1, p1C, Cp2, p2D, p2E, p2F, Dp3, p3H, Hp6, p6O, Op9, p9W, p2E, Ep4, p4I, Ip7, p4J, Jp7, p7 L, Lp8, p8W, Wp10, p10P, p10Q, Pp11, Qp11, p11S, Sp12, p12T, p12U, Tp13, Up13, p13V, Fp5, p5N, p5Y, p5Z, Np14, p14R, Yp15, Zp15, p15R} 8) Penggambaran Ulang Workflow Dari penggabungan transition dan place yang telah dilakukan sebelumnya, SWF yang terbentuk adalah sebagai berikut.
- 10. Arc berwarna merah merupakan arc yang baru terbentuk menggunakan Algoritma Alpha+. Berikutnya adalah perbandingan implementasi Algoritma Alpha++ dengan menggunakan tool ProM. Tool ProM yang digunakan adalah ProM 5.2, di mana plugin Alpha+ tidak tersedia di ProM 6.2. ProM 6.2 digunakan untuk mengkonversi format data XES menjadi MXML untuk kemudian akan digunakan di ProM 5.2.
- 12. Terbukti bahwa Algoritma Alpha+ dapat menangani short-loop pada sebuah proses bisnis. 3. Algoritma Alpha++ Algoritma Alpha++ digunakan untuk menangani kekurangan Algoritma Alpha++ dalam menemukan implicit dependency pada sebuah Petrinet. Algoritma Alpha++ juga dapat membentuk konstruksi yang bersifat non-free-choice construct. Pada kali ini akan dilakukan implementasi algoritma Alpha++ dengan kasus sama seperti Algoritma Alpha dan Alpha++.
- 13. Langkah-langkah yang digunakan untuk mengimplementasikan Algoritma Alpha++ adalah sebagai berikut : Cek event log yang akan diproses. Event log yang diimplentasikan pada kasus ini adalah {ACDHOWPSTV, ACDHOWQSUV, ..., ABBCDHOWPSTV}. Ini berdasarkan analisa di Algoritma Alpha+. Mendeteksi length-one-loop yang terjadi pada sebuah case. Length-one-loop terjadi beberapa kali di case. Salah satunya adalah case terahir : ABBCDHOWPSTV. Terlihat L1L yang ditemukan adalah {B}. Hilangkan length-one-loop pada transition yang terjadi. Berikutnya adalah mengidentifikasi place yang terkoneksi pada L1L transitions. Pada kasus ini = {B}. yang diidentifikasi adalah {A, C, D, E, F, G, H, I, J, L, N, O, P, Q, R, S, T, U, V, X, Y, Z} Buat Petrinet menggunakan algoritma Alpha sehingga Petrinet yang terbentuk adalah sebagai berikut : Kemudian dengan menggunakan langkah-langkah yang ada pada algoritma Alpha+, gabungkan length-one-loop sehingga konstruksinya berubah dan menghasilkan Petrinet sebagai berikut :
- 14. Langkah berikutnya adalah menemukan dan mendeteksi seluruh implicit ordering relation yang ada. Rumusnya adalah Implicit ordering yang ditemukan adalah sebagai berikut : I P J Q P T Q U Implicit dependency yang ditemukan diintegrasikan pada workflow net, sehingga menjadi seperti berikut :
- 15. Dependency yang ditemukan memiliki garis berwarna hijau. Langkah berikutnya adalah melakukan eliminasi pada implicit dependency yang terjadi. Rumus yang digunakan adalah sebagai berikut : Setelah dieliminasi, hasil petrinetnya adalah sebagai berikut :
- 16. Sebagai perbandingan, implementasi dilakukan menggunakan ProM 5.2. Langkahlangkahnya adalah sebagai berikut : Langkah berikutnya adalah menganalisa menggunakan plugin Alpha++
- 17. Hasilnya adalah sebagai berikut
- 18. C. Kesimpulan Algoritma Alpha merupakan algoritma dasar yang dapat digunakan untuk menganalisa dan menghasilkan pola activity dari sebuah case. Algoritma Alpha sendiri memiliki kekurangan, antara lain : length-one-loop, length two loop, invisible task, duplicate task, implicit dependencies dan non-free-choice. Pembaharuan algoritma Alpha adalah algoritma Alpha+ yang dapat menangani short loop seperti length-one-loop yang tidak terdeteksi oleh algoritma Alpha. Selain itu ada juga algoritma Alpha++ yang dapat menangani implicit dependency yang mungkin terjadi pada sebuah event log yang telah dijalankan. Dengan hasil analisa implicit dependency ini, dapat terjadi sebuah alternatif cara yang dapat diterapkan dalam proses bisnis dan mendukung keputusan strategis.