Process mining with alpha++ algorithm

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

2013

Oleh

Fadlika Dita Nurjanto

5110100132

Kelas Audit A

Jurusan Teknik Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya

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 :

Dari case tersebut, akan dilakukan percobaan dengan menggunakan 3 algoritma, yaitu

Alpha, Alpha+, dan Alpha++.

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 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

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) Membuat sekumpulan transisi dari event log pada Workflow net ( )

2) Membuat sekumpulan transisi output dari source place pada Workflow net ( )

3) Membuat sekumpulan transisi input dari sink place pada Workflow net ( )

4) 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

5) 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.

6) Places yang sebelumnya diidentifikasi dibuat.

7) Masing-masing place dihubungkan dengan transisi input/output yang bersesuaian.

8) Algoritma kemudian mengembalikan Workflow net yang diperoleh dari langkah-

langkah 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:

Persamaan yang digunakan untuk mencari adalah

{ |

2) Membuat Transisi Output Source Place Pada Workflow net ( )

Persamaan yang digunakan adalah { |

Transisi output yang dihasilkan adalah

3) Membuat Transisi Input Sink Place Pada Workflow net ( )


A B C D E F G H I J L N

O P Q R S T U V X Y Z

A

Transisi input yang dihasilkan adalah dan

4) Algoritma α Menentukan Transisi Mana Yang Berelasi Secara Casual


5) Menentukan Jumlah Pasti Places yang Dimiliki Oleh Workflow net


Dari langkah 4 dan 5, tuple yang dihasilkan adalah sebagai berikut :

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 :

R V

(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

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

p1

p2

p3

p4

p5

p6

p7

p8

p9

p10

p11

p12

p13

p14

p15

o

i

dengan menggunakan plugin Alpha Algorithm. Hasilnya adalah Petrinet yang

terbentuk dan merepresentasikan workflow pada case yang dijalankan.

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+.

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 :

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}

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 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

4) Menghapus seluruh length-one-loop transition untuk kemudian diproses

menggunakan algoritma Alpha. Pada kasus kali ini, = {A, C, D, E, F, G, H, I, J, L,

N, O, P, Q, R, S, T, U, V, X, Y, Z}

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-one-

loop. Rumus yang digunakan adalah . Sehingga = {A, B, C,

D, E, F, G, H, I, J, L,N, O, P,Q ,R, S, T, U, V, X, Z}

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.

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.

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++.

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 :

Langkah berikutnya adalah menemukan dan mendeteksi seluruh implicit ordering

relation yang ada. Rumusnya adalah

Implicit ordering yang ditemukan adalah sebagai berikut :

Implicit dependency yang ditemukan diintegrasikan pada workflow net, sehingga

menjadi seperti berikut :

I P

J Q

P T

Q U

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 :

Sebagai perbandingan, implementasi dilakukan menggunakan ProM 5.2. Langkah-

langkahnya adalah sebagai berikut :

Langkah berikutnya adalah menganalisa menggunakan plugin Alpha++

Hasilnya adalah sebagai berikut

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.

Process mining with alpha++ algorithm

Documents