Seminar Hasil Tugas Akhir
APLIKASI PENGGALIAN POLA SEKUENSIAL INTERVAL WAKTU FUZZY PADA PROSES BISNIS ERP MENGGUNAKAN ALGORITMA FP-GROWTH-PREFIXSPAN Application of Fuzzy Time-Interval Sequence Pattern Mining of ERP Business Process using FP-Growth – PrefixSpan Algorithm Oleh : Muhammad Sidratul Muntaha Al-Mutawakkil Alallah 1210 100 701
Dosen Pembimbing: Dr. Imam Mukhlash, S.Si, MT. Matematika FMIPA ITS 2014
Abstrak Perkembangan teknologi yang semakin pesat mengakibatkan makin banyaknya pengelolaan data terkomputerisasi. Dengan semakin kompleksnya proses bisnis, teknologi manajemen proses bisnis seperti ERP (Enterprise Resource Planning) dan sejenisnya makin banyak digunakan. Hal ini mengakibatkan ketersediaan data makin melimpah sehingga penggalian dan pencarian informasi dari sekumpulan data tersebut akan menjadi sebuah pengetahuan berharga. Data mining merupakan proses ekstraksi informasi atau pola penting dalam basis data berukuran besar. Metode data mining yang akan digunakan dalam Tugas Akhir ini adalah metode penggalian pola sekuensial (sequence pattern mining) menggunakan algoritma FP-Growth – PrefixSpan. Selain itu, digunakan juga pendekatan fuzzy untuk menangani interval waktu dari data yang dianalisis sehingga pola sekuensial yang dihasilkan berupa pola sekuensial interval waktu fuzzy (fuzzy time-interval sequence pattern). Penerapan metode ini dalam proses bisnis ERP (Enterprise Resource Planning) menghasilkan pola sekuensial interval waktu fuzzy. Hasil analisis menunjukkan bahwa terdapat pengaruh minimum support terhadap pola yang dihasilkan. Selanjutnya, hasil dari analisis tersebut bisa digunakan sebagai bahan pertimbangan dalam analisis proses bisnis. Kata Kunci - Data Mining, Proses Bisnis, FP-Growth, PrefixSpan, Fuzzy time-interval sequence pattern.
Bab I Pendahuluan
Pendahuluan 1.1 Latar Belakang (I)
1 2 3 4
• Perkembangan teknologi komputer yang semakin pesat mengakibatkan makin banyaknya pengelolaan data terkomputerisasi sehingga ketersediaan data makin melimpah.
• Dengan semakin kompleksnya proses bisnis, teknologi manajemen proses bisnis seperti Enterprise Resource Planning (ERP) dan System Application and Product in Data Processing (SAP) telah banyak digunakan.
• Timbulnya permasalahan ketika beberapa perusahaan dengan proses bisnis berbeda ingin bergabung bersama.
• Data mining merupakan salah satu solusi terbaik dalam menggali dan memperoleh informasi dari sekumpulan data.
Pendahuluan 1.1 Latar Belakang (II) Data Mining
Untuk menemukan informasi penting dalam database
Tugas
Klasifikasi Clustering
Mengelompokkan sebuah sampel baru pada himpunan kelas yang sebelumnya telah diketahui Pengelompokan sampel-sampel ke dalam kelompok sampel yang sama
Sequence Pattern
Penemuan pola keterurutan suatu event pada waktu tertentu
Association Rule
Penemuan pola intra transactional dalam database terjadi hanya pada sebuah event
Pendahuluan 1.1 Latar Belakang (III)
Penelitian sebelumnya terkait hal pengklasteran pada proses bisnis ERP berdasarkan kesamaannya yang menjelaskan bahwa dalam mengukur nilai kesamaannya digunakan metric penggabungan antara kemiripan semantik dan struktur.
Pendahuluan 1.1 Latar Belakang (IV)
Oleh karena itu penulis ingin mengangkat topik penelitian tersebut lagi sebagai Tugas Akhir dengan teknik data mining yang berbeda yang diberi judul “Aplikasi Penggalian Pola Sekuensial Interval Waktu Fuzzy pada Proses Bisnis ERP menggunakan algoritma FP-Growth (PrefixSpan)”.
Pendahuluan 1.2 Rumusan Masalah Bagaimana menggali pola sekuensial interval waktu fuzzy pada proses bisnis menggunakan algoritma FP-Growth – PrefixSpan?
Berapa banyak pola sekuensial yang dihasilkan dari proses bisnis yang memenuhi nilai batas (minimum support) tertentu jika menggunakan metode penggalian pola sekuensial (sequence pattern mining)?
Bagaimana pengaruh nilai minimum support terhadap penggalian pola sekuensial?
Pendahuluan 1.3 Batasan Masalah Data yang digunakan merupakan data event log proses bisnis yang sudah dinormaliasasi sebelumnya. Data tersebut didapat dari sebuah penelitian terkait proses bisnis ERP. Metode penggalian pola sekuensial yang akan diterapkan juga menerapkan pendekatan Fuzzy melalui interval waktu dari data yang dianalisis. Algoritma PrefixSpan yang digunakan hanya sebagian saja karena kehomogenan data.
1.4 Asumsi Masalah Istilah linguistik yang ditentukan untuk menentukan derajat keanggotaan dari variabel linguistik interval waktu adalah Short (sebentar), Middle (sedang), dan Long (lama). Interval waktu fuzzy yang dihasilkan oleh suatu kejadian tidak dipengaruhi dengan nilai interval waktu fuzzy pada kejadian sebelumnya.
Pendahuluan 1.5 Tujuan Tujuan dari tugas akhir ini adalah membuat suatu perangkat lunak yang memuat Fuzzy Time-Interval Sequence Pattern Mining sehingga dapat digunakan untuk mencari pola sekuensial yang menarik dari proses bisnis sebuah perusahaan.
1.6 Manfaat Mengetahui pola proses bisnis yang efisien. Mempermudah perusahaan dalam mencari alternatif model proses bisnis yang baru dan bermanfaat. Sebagai salah satu referensi penggunaan Sequence Pattern Mining.
Bab II Tinjauan Pustaka
2.1 Data Mining Data mining merupakan proses ekstraksi informasi atau pola yang penting dalam basis data berukuran besar (Han & Kamber 2001). Data mining merupakan penggunaan algoritma dalam proses Knowledge Discovery in Database (KDD) untuk menemukan pola yang bermanfaat (Goharian & Grossman 2003).
2.2 Knowlege Discovery in Database (KDD) Knowledge Discovery in Database (KDD) adalah proses menemukan informasi yang berguna serta pola-pola yang ada dalam data (Goharian & Grossman 2003).
2.3 Pola Sekuensial (I) Pola sekuensial adalah daftar urutan dari sekumpulan item. Pola transaksi atau event yang terjadi dalam model proses bisnis biasanya tergambarkan dalam sebuah pola sekuensial. Pola sekuensial mengindikasikan bahwa transaksi biasanya terjadi secara serial terhadap waktu. Diberikan sebuah minimum_support bilangan bulat positif sebagai support threshold, sebuah sequence 𝛼𝛼 disebut pola sekuensial dalam basis data sequence 𝑆𝑆 jika 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑡𝑡𝑠𝑠 𝛼𝛼 ≥ 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚_𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠.
2.4 Algoritma PrefixSpan Mulai
Input Minimum Support (0 s/d 1)
Menggali frequent item/pola sekuensial panjang-1
Terbentuk Pola Ya Membangun basis data terproyeksi tidak Menggali pola sekuensial panjang-x (x>1)
Ya Terbentuk Pola tidak Pola Sekuensial Dihasilkan
Selesai
2.5 Himpunan Fuzzy (I)
Lotfi A. Zadeh (1965) pertama kali memperkenalkan himpunan Fuzzy sebagai cara matematis untuk merepresentasikan ketidaktepatan. Jika X adalah kumpulan objek yang dinotasikan dengan X, maka himpunan fuzzy A dalam X adalah himpunan pasangan berurutan: 𝐴𝐴 = 𝑥𝑥, 𝜇𝜇𝐴𝐴 (𝑥𝑥) | 𝑥𝑥 𝜖𝜖 𝑋𝑋
𝜇𝜇𝐴𝐴 (𝑥𝑥) disebut fungsi/derajat keanggotaan atau tingkat keanggotaan (juga tingkat kompetibelitas atau tingkat kebenaran) dari 𝑥𝑥 di A yang memetakan X ke keanggottan ruang semesta M. (Ketika M hanya memuat dua titik 0 dan 1, maka A bukan fuzzy dan 𝜇𝜇𝐴𝐴 (𝑥𝑥) identik dengan fungsi karakteristik dari himpunan non-fuzzy). Range dari fungsi keanggotaan adalah himpunan bagian dari bilangan riil yang mempunya supremum terbatas. Anggota dengan derajat keanggaotan nol umumnya tidak didaftar/disebutkan.
2.5 Himpunan Fuzzy (II) Variabel linguistik merupakan variabel fuzzy yang dibuat acuan untuk menilai suatu hal. Misalkan variabel linguistik “UMUR” memiliki tiga penilaian linguistik yaitu muda, dewasa, tua dan usia lanjut yang masing-masing memiliki fungsi keanggotaan tersendiri. Fungsi keanggotaan (membership function) adalah suatu fungsi yang menunjukkan pemetaan titik-titik input data ke dalam derajat keanggotaannya. Ada beberapa fungsi yang dapat digunakan untuk mendapatkan derajat keanggotaan keanggotaan, seperti triangular, trapezoidal, gaussian dan semacamnya.
Bab III Metode Penelitian
Metode penelitian Studi Pustaka
Laporan
Ekstraksi Data
Pengolahan Data
Pengujian
Perancangan Interface
Bab IV Analisis dan Perancangan Sistem
4.1 Analitis Sistem 4.1.1 Deskripsi Perangkat Lunak Perangkat lunak yang dimaksud di sini adalah aplikasi penggalian pola sekuensial interval waktu fuzzy menggunakan algoritma FP-Growth (PrefixSpan). Aplikasi ini dibuat untuk membantu user dalam melakukan proses penggalian pola sekuensial pada proses bisnis. Aplikasi ini hanya bisa digunakan untuk data homogen proses bisnis, karena ruang pencarian pola sekuensial dalam algoritma aplikasi ini masih dibatasi menyesuaikan data yang diperoleh penulis saat ini. Selain itu, aplikasi penggalian pola sekuensial ini memanfaatkan DBMS MySQL untuk membaca basis data, baik mulai saat pra pemrosesan data sampai penggalian data. DBMS di sini hanya sebagai media penyimpanan sementara bagi data yang akan diolah atau dianalisis.
4.1.2 Pemodelan Analitis (I) Use Case Diagram
4.1.2 Pemodelan Analitis (II) Activity Diagram
4.2 Perancangan Perangkat Lunak 4.2.1 Perancangan Proses Tujuan dari perancangan proses ini adalah untuk memberikan penjelasan tentang proses-proses yang dilakukan terhadap data awal yang diperoleh, sehingga data tersebut nantinya dapat dipakai dalam pemrosesan data mining. Dalam hal ini terdapat dua perancangan proses, yaitu proses pre-processing data dan proses data mining
Bab V Hasil dan Pembahasan
5.1 Pengaruh Minimum Support Dalam proses pencarian pola sekuensial interval waktu fuzzy dibutuhkan suatu nilai yang disebut minimum support. Syarat suatu pola dikatakan pola sekuensial jika pola tersebut memiliki nilai support ≥ minimum support. Maksud dari penentuan nilai minimum support sendiri adalah memfilter pola sekuensial yang ada dalam basis data sequence yang nilai supportnya tinggi.
5.2 Hubungan Minimum Support dan Pola Sekuensial Berikut tabel hasil pengujian, hubungan antara minimum support dengan banyak pola sekuensial yang dihasilkan. Tabel 5.1 Hubungan minimum support dengan Pola Sekuensial Minimum Support
Pola Sekuensial
Running Time
0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1
82 29 21 17 12 12 12 12 3
35 menit 21 detik 12 menit 6 detik 8 menit 36 detik 7 menit 13 detik 2 menit 56 detik 2 menit 56 detik 2 menit 57 detik 3 menit 2 detik 37 detik
Grafik untuk Tabel 5.1 disajikan sebagaimana di bawah ini: 90 80
Pola Sekuensial
70 60 50 40 30 20 10 0 0.2
0.3
0.4
0.5
0.6 0.7 Minimum Support
0.8
0.9
1
Dari gambar di atas dapat dilihat bahwa grafiknya monoton turun. Hal tersebut berarti semakin besar nilai minimum support yang ditentukan maka semakin sedikit pola sekuensial yang dihasilkan. Dengan kata lain nilai minimum support berbanding terbalik dengan pola sekuensial interval waktu fuzzy yang dihasilkan. Semakin sedikit pola sekuensial interval waktu fuzzy yang dihasilkan saat nilai minimum support semakin tinggi disebabkan karena semakin banyak pola sekuensial yang nilai supportnya di bawah nilai minimum support.
5.3 Hubungan Minimum Support dan Running Time Berikut tabel hasil pengujian, hubungan antara minimum support dengan banyak running time aplikasi program. Tabel 5.2 Hubungan minimum support dengan Pola Sekuensial Minimum Support
Pola Sekuensial
Running Time
0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1
82 29 21 17 12 12 12 12 3
35 menit 21 detik 12 menit 6 detik 8 menit 36 detik 7 menit 13 detik 2 menit 56 detik 2 menit 56 detik 2 menit 57 detik 3 menit 2 detik 37 detik
Grafik untuk Tabel 5.2 disajikan sebagaimana di bawah ini: 2500
waktu (detik)
2000
1500
1000
500
0 0,2
0,3
0,4
0,5 0,6 0,7 Minimum Support
0,8
0,9
1
Dari gambar di atas dapat dilihat bahwa grafiknya monoton turun. Hal tersebut juga berarti semakin besar nilai minimum support yang ditentukan maka waktu yang dibutuhkan untuk mencari pola sekuensial interval waktu fuzzy semakin sedikit. Dengan kata lain nilai minimum support juga berbanding terbalik dengan running time.
5.4 Analisis Data Uji Pada pengujian ini digunakan 4 nilai minimum support, yaitu 0.3, 0.4, 0.5, dan 0.8, dan 1 Berikut diberikan tabel pola sekuensial interval waktu fuzzy untuk keempat minimum support yang diinputkan.
Tabel 5.3 Pola Sekuensial min_sup=1 Pola Sekuensial
Support
Register
1
AnalyzeDefect
1
Register,short,AnalyzeDefect
1
Tabel 5.4 Pola Sekuensial min_sup 0.8a Pola Sekuensial Register AnalyzeDefect TestRepair InformUser ArchieveRepair Register,short,AnalyzeDefect Register,long,TestRepair Register,long,InformUser Register,long,ArchieveRepair Register,short,AnalyzeDefect, long,TestRepair Register,short,AnalyzeDefect, long, InformUser Register,short,AnalyzeDefect, long, ArchieveRepair
Support 1 1 0,998 0,998 0,905 1 0,909 0,949 0,905 0,910 0,949 0,905
Tabel 5.4 Pola Sekuensial min_sup 0.8 Pola Sekuensial Register AnalyzeDefect Repair(Complex) TestRepair InformUser ArchieveRepair Register,short,AnalyzeDefect Register,long,TestRepair Register,long,InformUser Register,long,ArchieveRepair
Support 1 1 0,596 0,998 0,998 0,905 1 0,909 0,949 0,905
Register,short,AnalyzeDefect,short, AnalyzeDefect
0,57
Register,short,AnalyzeDefect, long,TestRepair
0,910
Register,short,AnalyzeDefect, long, InformUser
0,949
Register,short,AnalyzeDefect, long, ArchieveRepair Register,short,AnalyzeDefect,short, AnalyzeDefect,long,TestRepair
0,905 0,743
Register,short,AnalyzeDefect,short, AnalyzeDefect,long,TestRepair,long,InformUser
0,776
Register,short,AnalyzeDefect,short, AnalyzeDefect,long,TestRepair,long,ArchieveRepair
0,902
5.4 Analisis Pola Sekuensial Untuk masing-masing minimum support yang sudah ditentukan, pola sekuensial interval waktu fuzzy maksimal menghasilkan proses bisnis. Dalam hal ini diambil pola sekuensial interval waktu fuzzy untuk minimum support=0,8 sebagaimana gambar yang tersaji di bawah ini: Register
short
Analyze Defect
long
Register
short
Analyze Defect
long
Register
short
Analyze Defect
long
Archive Repair Test Repair Inform User
5.4 Analisis Pola Sekuensial
(II)
Hasil dari penemuan pola-pola proses bisnis seperti di atas bisa dijadikan bahan pertimbangan bagi sebuah perusahaan apalagi ingin mengganti atau memperbarui model proses bisnisnya, baik itu menyangkut interval waktu antar proses ataupun model proses itu sendiri. Hal ini menjadi penting saat sebuah perusahaan lain ingin bergabung dengan perusahaan yang bersangkutan. Pencarian pola proses bisnis semacam ini selanjutnya bisa membantu atau memberikan solusi terhadap perusahaan terkait proses bisnis apa saja dari kedua perusahaan yang bisa digabungkan.
Bab VI Kesimpulan
Kesimpulan Berdasarkan analisis terhadap hasil pengujian program, maka dapat diambil kesimpulan sebagai berikut: ◦ Penggalian Pola Sekuensial Interval Waktu Fuzzy telah berhasil diimplementasikan pada data proses bisnis. ◦ Dengan menggunakan pendekatan fuzzy melalui interval waktu dapat disimpulkan bahwa pola sekuensial yang didapat semakin sedikit karena minimum support yang digunakan berdasarkan nilai fuzzy interval waktu. ◦ Nilai minimum support berpengaruh pada hasil dan lama pencarian pola sekuensial interval waktu fuzzy. Minimum support terbaik adalah jika sequence memiliki nilai support tinggi dan mencakup hampir seluruh event atau kejadian dari proses bisnis. ◦ Hasil dari penggalian pola sekuensial bisa dijadikan bahan pertimbangan untuk mengubah atau memperbarui proses bisnis yang ada.
Daftar Pustaka [1]
Jung J.Y., Bae J., and Liu L., “Hierarchical Clustering of Business Process Models”, SCC 2008, IEEE International Conference on Volume 2, pp 613-616, 2008. [2] Connolly TM, Begg CE. 2002. Database System: A Practical Approach To Design, Implementation, and Management.England:Addison Wesley. [3] Han J. and Kamber M. 2006. Data Mining: Concept and Technique. 2nd Edition. San Diego, USA: Morgan-Kauffman. [4] Weske, Mathias. 2007. “Business Process Management Concepts, Languages, Architectures”. Springer Berlin Heidelberg New York. [5] Pei J, Han J. 2004. Mining Sequential Patterns by Pattern Growth: The PrefixSpan Approach. Volume 16 No. 10 Oktober 2004. [6] Agrawal R, Srikant R. 1995. Mining Sequential Patterns. [7] Pei J, Han J. 2004. Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach. Volume 16 No. 10. [8] Zimmermann, H.-J 2010. “Fuzzy Set Theory”.Volume 2. [9] Chen Yen-Liang, Huang Cheng-Kui. Discovering fuzzy time-interval sequential patterns in sequence database. [10] Ardyanto A. 2011. “Mengenal Apa itu Proses Mining”. http://netsains.net/2011/06/mengenalapa-itu-process-mining/. Diakses tanggal 06 Februari 2014 Pukul 12:02 WIB. [11] Saikhu A, Hariadi V. 2012. “Klasifikasi Event Pada Process Logs Menggunakan Model Regresi Logistik ”. Makalah KNSI-2012. [12] Sarno R, Pamungkas E.W, Ginardi H. 2013. Clustering of ERP Business Process Fragments.
