PERBANDINGAN KINERJA METODE FPCFI DAN ReLIM UNTUK DATA STREAM MINING BERPRAPROSES SLIDING WINDOW
SYACHRUDIN
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2010
PERBANDINGAN KINERJA METODE FPCFI DAN ReLIM UNTUK DATA STREAM MINING BERPRAPROSES SLIDING WINDOW
SYACHRUDIN
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2010
ABSTRACT
SYACHRUDIN. Performance Comparison of FPCFI and ReLIM Methods for Data Stream Mining with Sliding Window Preprocess. Supervised by MUSHTHOFA. Recently, data stream mining has been widely studied for its increasing application potentials. Data stream is an example of data which is real-time, continuous, ordered sequence of items with various update rates and is potentially unlimited in the amount of data. Data stream mining is important for applications that require complete frequency information as well as high time and space efficiencies. Because of the characteristics of data stream which have potentially unlimited amount of data, algorithms which give good performance and results are required. This research uses sliding window technique for preprocessing data stream. The data stream mining techniques which are used for extracting patterns between generated itemsets are FPCFI and ReLIM. The patterns to be mined are the closed frequent itemsets. The performances of the algorithms will be compared using ANOVA.The data used in this research includes Webdocs and Accidents. FPCFI required a higher time usage i.e. 0.47s, 0.78s, 1.08s, and 1.39s for sliding window sizes 5, 10, 15, and 20, while ReLIM required 0.43s, 0.73s, 1.02s, and 1.31s on Webdocs dataset. Similar results are also obtained for the Accidents dataset. From these results we conclude that FPCFI require significantly higher time usage compared to ReLIM. Keywords : data stream mining, sliding window, FPCFI algorithm, ReLIM algorithm
Judul
:
Nama NIM
: :
Perbandingan Kinerja Metode FPCFI dan ReLIM untuk Data Stream Mining Berpraproses Sliding Window Syachrudin G64066023
Menyetujui:
Pembimbing,
Mushthofa, S.Kom., M.Sc.
Mengetahui: Ketua Departemen Ilmu Komputer,
Dr. Ir. Sri Nurdiati, M.Sc. NIP. 19601126 198601 2 001
Tanggal Lulus :
PRAKATA Bismillahirahmanirrahim, Alhamdulillahi Rabbil ’alamin, puji dan syukur penulis panjatkan kepada Allah SWT atas limpahan rahmat dan karuniaNya sehingga penulis dapat menyelesaikan skripsi dengan judul Perbandingan Kinerja Metode FPCFI dan ReLIM untuk Data Stream Mining Berpraproses Sliding Window ini. Shalawat serta salam juga penulis ucapkan kepada junjungan kita Rasulullah SAW beserta seluruh sahabat dan umatnya hingga akhir zaman. Dalam menyelesaikan karya tulis ini penulis mendapatkan banyak sekali bantuan, bimbingan dan dorongan dari berbagai pihak. Oleh karena itu, penulis ingin mengucapkan terima kasih kepada pihakpihak yang telah membantu menyelesaikan skripsi ini, antara lain : •
Kepada Bapak dan Ibu tercinta yang selalu memberikan motivasi, dukungan dan doanya. Terima kasih atas semangat dan kasih sayangnya.
•
Bapak Mushthofa, S.Kom., M.Sc., selaku dosen pembimbing.
•
Bapak Hari Agung Adrianto, S.Kom., M.Si., selaku dosen penguji I.
•
Ibu Annisa, S.Kom., M.Kom., selaku dosen penguji II.
•
Seluruh dosen IPB yang telah memberi banyak ilmu kepada penulis.
•
Erika Puri Handayani yang selalu memberikan perhatian dan dukungannya kepada penulis.
•
Seluruh staf karyawan Departemen Ilmu Komputer FMIPA IPB.
•
Bapak Indra Yogi, Bapak Fathurrohman, Ibu Ayi, Ibu Intan, Ibu Metty dan Ibu Susanah sebagai rekan kerja yang telah memberikan banyak motivasi kepada penulis.
•
Andriana Nurwitasari dan Nurul Khaerani selama konsultasi bersama.
•
Lucky Irwansyah, Dwi Agusta M, Seta Baehera, Muhamad Haikal, Deni Kurniawan, Agung Manunggal, Jeffry Pianov, Siti Nurhasanah, Eka Marliana, Rika Indriani, Ahmad R Holili, Fahrizal, Pangudi, Abdul Rosyid dan seluruh teman-teman Ilkom Ekstensi Angkatan 1 yang tidak mungkin penulis sebutkan satu per satu.
Akhir kata, penulis berharap semoga skripsi ini dapat bermanfaat dan berguna bagi semua pihak yang membutuhkan, Amin.
Bogor, Maret 2010
Syachrudin, A.Md
RIWAYAT HIDUP Penulis dilahirkan di Bekasi tanggal 23 Maret 1986, anak ketiga dari tiga bersaudara dari pasangan Bapak Patonih MAS dan Ibu Ma’niah. Penulis menyelesaikan masa studinya di Sekolah Menengah Umum Negeri 6 Bekasi pada tahun 2003. Pada tahun 2003 penulis diterima di Institut Pertanian Bogor sebagai mahasiswa Fakultas Matematika dan Ilmu Pengetahuan Alam, Departemen Ilmu Komputer Program Studi D3 Informatika melalui jalur reguler dan menyelesaikan studinya pada tahun 2006. Pada tahun yang sama penulis melanjutkan studinya di Departemen Ilmu Komputer Institut Pertanian Bogor Program Studi S1Ilmu Komputer Penyelenggaraan Khusus.
DAFTAR ISI Halaman DAFTAR GAMBAR .....................................................................................................................vi DAFTAR TABEL .........................................................................................................................vi DAFTAR LAMPIRAN..................................................................................................................vi PENDAHULUAN .......................................................................................................................... 1 Latar Belakang .......................................................................................................................... 1 Tujuan Penelitian ...................................................................................................................... 1 Ruang Lingkup .......................................................................................................................... 1 Manfaat ..................................................................................................................................... 1 TINJAUAN PUSTAKA ................................................................................................................. 1 Data mining............................................................................................................................... 1 Data stream ............................................................................................................................... 1 Data stream mining ................................................................................................................... 2 Frequent pattern mining ........................................................................................................... 2 Closed frequent itemset ............................................................................................................. 2 Association rule......................................................................................................................... 3 Window ..................................................................................................................................... 3 FP–Tree .................................................................................................................................... 3 Algoritme FP-Growth ............................................................................................................... 4 Global closed frequent itemsets tree ......................................................................................... 4 FPCFI ....................................................................................................................................... 5 ReLIM ....................................................................................................................................... 5 Closed frequent itemset pada ReLIM......................................................................................... 6 Analysis of variance (ANOVA) .................................................................................................. 7 METODE PENELITIAN ............................................................................................................... 7 Data ........................................................................................................................................... 7 Praproses dengan sliding window ............................................................................................. 8 FPCFI ....................................................................................................................................... 8 ReLIM ....................................................................................................................................... 8 Analisis hasil ............................................................................................................................. 8 Lingkungan implementasi dan eksperimen ............................................................................... 9 HASIL DAN PEMBAHASAN....................................................................................................... 9 Implementasi algoritme ............................................................................................................. 9 Sliding window ........................................................................................................................ 10 Analysis of variance ................................................................................................................ 11 Hasil ANOVA pada dataset .................................................................................................... 11 KESIMPULAN DAN SARAN..................................................................................................... 12 Kesimpulan ............................................................................................................................. 12 Saran ....................................................................................................................................... 12 DAFTAR PUSTAKA ................................................................................................................... 12
DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Contoh closed itemsets ........................................................................................................... 2 Contoh sliding window ........................................................................................................... 3 FP –Tree pembacaan transaksi 1 ............................................................................................ 4 FP –Tree pembacaan transaksi 2 ............................................................................................ 4 FP –Tree utuh ......................................................................................................................... 4 Contoh GCFIT........................................................................................................................ 5 Pseudocode FPCFI ................................................................................................................ 5 Tahap pertama ReLIM ............................................................................................................ 6 Tahap kedua ReLIM dari prefix B. .......................................................................................... 6 Tahap ketiga ReLIM dari prefix D .......................................................................................... 6 Tahap terakhir ReLIM dari prefix C ........................................................................................ 6 Pseudocode closed frequent itemset pada ReLIM................................................................... 6 Tahapan metode penelitian ..................................................................................................... 7 Diagram nilai rata-rata kinerja untuk dataset Webdocs ........................................................ 10 Diagram nilai kinerja untuk dataset Accidents ..................................................................... 11
DAFTAR TABEL Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13
Transaksi dalam sebuah dataset ............................................................................................. 4 Frekuensi kemunculan itemset terurut .................................................................................... 4 Transaksi items terurut ........................................................................................................... 4 Frequent itemset terbentuk ..................................................................................................... 4 Transaksi pada window pertama yang akan diterapkan algoritme ReLIM .............................. 6 Frekuensi kemunculan itemset terurut .................................................................................... 6 Transaksi items terurut ........................................................................................................... 6 Hasil sliding window ............................................................................................................ 10 Hasil sliding window ............................................................................................................ 10 Hasil rata-rata waktu pada percobaan dataset Webdocs ....................................................... 10 Hasil rata-rata waktu pada percobaan dataset Accidents ...................................................... 11 Hasil ANOVA dataset Webdocs............................................................................................ 11 Hasil ANOVA dataset Accidents .......................................................................................... 12
DAFTAR LAMPIRAN Halaman 1 2 3 4 5 6 7 8 9
Gambar subset lattice closed itemsets dengan minimum support count = 3 ......................... 14 Hasil lama waktu pemrosesan pada setiap tahap dalam algoritme pada dataset Webdocs dalam satuan detik ................................................................................................................ 15 Hasil lama waktu pemrosesan pada setiap tahap dalam algoritme pada dataset Accidents dalam satuan detik ................................................................................................................ 16 Contoh kode halaman yang sering diakses pada suatu halaman website dengan batas minimum support sebesar 50% ............................................................................................. 17 Hasil penggalian closed frequent itemset pada dataset Webdocs dengan batas minimum support 50% ......................................................................................................................... 18 Hasil penggalian association rule pada dataset Webdocs dengan batas minimum support 50% dan minimum confidence 60% ........................................................................ 19 Contoh kode faktor-faktor yang sering menyebabkan kecelakaan dengan tingkat resiko kecelakaan 90% .................................................................................................................... 20 Hasil penggalian closed frequent itemset pada dataset Accidents dengan batas minimum support 90% ......................................................................................................................... 21 Hasil penggalian association rule pada dataset Accidents dengan batas minimum support 90% dan minimum confidence 90% ........................................................................ 22
vi
PENDAHULUAN Latar Belakang Data stream adalah contoh data yang bersifat real-time atau secara langsung, kontinyu, tersusun secara berurutan dari item yang ada, memiliki update rates yang bervariasi dan jumlahnya yang mungkin secara potensial tidak terbatas. Menambang data stream untuk menemukan pengetahuan yang menarik, dinilai penting untuk banyak aplikasi. Data stream biasanya didapatkan dari sistem yang bersifat real-time, komunikasi antar jaringan, lalu lintas internet, transaksi online dari sebuah pasar keuangan ataupun industri retail, dan juga lingkungan dinamis lainnya. Data stream membutuhkan algoritme penambangan yang tetap menjaga efisiensi waktu dan ruang yang tinggi karena kemungkinan jumlahnya yang tidak terbatas. Dalam menambang pola yang sering muncul pada data stream, ada kecenderungan belum digunakannya teknik pada tahap praprosesnya. Penambangan dilakukan secara langsung tanpa dilakukannya tahapan praproses terlebih dahulu. Dengan begitu, akan mucul suatu kemungkinan bahwa proses penambangan akan membutuhkan waktu yang lebih lama dan memori yang lebih besar. Dengan melihat latar belakang tersebut, ada sebuah teknik yang dapat digunakan untuk melakukan praproses data pada data stream yaitu sliding window. Karena sifat data stream yang memiliki jumlah yang mungkin secara potensial besar atau tidak terbatas, maka diperlukan sebuah algoritme yang dapat memberikan hasil dan kinerja yang baik. FPCFI atau Frequent Pattern Closed Frequent Itemsets dan ReLIM atau Recursive Elimination adalah algoritme penggalian data yang termasuk kedalam teknik association analysis. Penggunaan teknik tersebut menghasilkan bentuk closed frequent itemset yang memiliki nilai support. Penelitian ini mencoba melihat algoritme mana yang memilliki kinerja lebih baik dalam sebuah data stream. Perbandingan dilakukan dengan menggunakan 2 faktor yaitu algoritme itu sendiri dan juga ukuran sliding window. Tujuan Penelitian Tujuan dari penelitian ini adalah membandingkan kinerja algoritme Frequent Pattern Closed Frequent Itemsets dan Recursive Elimination dengan terlebih dahulu melakukan praproses sliding window pada data stream.
Ruang Lingkup Ruang lingkup penelitian yang dilakukan adalah sebagai berikut: 1. Penerapan algoritme FPCFI dan ReLIM dilakukan pada 2 data yaitu Webdocs dan Accidents yang diperlakukan sebagai data stream. 2. Penggalian meliputi confidence serta support suatu item terhadap item yang lain. 3. Ukuran sliding window yang diterapkan pada dataset diantaranya adalah 5, 10, 15 dan 20. 4. Perbandingan yang diukur adalah penggunaan waktu yang dibutuhkan oleh suatu algoritme dalam memproses data. Manfaat Penelitian ini diharapkan dapat dijadikan sebuah referensi terhadap pemilihan algoritme dalam menambang informasi pada data stream. Penelitian ini juga memberikan sedikit gambaran mengenai praproses sliding window pada suatu dataset. TINJAUAN PUSTAKA Data mining Data mining merupakan suatu proses untuk menemukan pola-pola yang menarik dari data yang berukuran besar yang disimpan didalam basisdata, data warehouse, atau sarana penyimpanan yang lain (Han & Kamber 2006). Secara umum data mining terbagi menjadi dua kategori yaitu: 1. Predictive data mining Memprediksi nilai dari atribut tertentu berdasarkan nilai atribut yang lain dan juga menemukan pola dari data untuk membuat prediksi. Classification, Regression, dan Deviation adalah teknik dalam predictive mining. 2. Descriptive data mining Menemukan karakteristik penting dari suatu basis data. Clustering, Association Rule, dan Sequential mining adalah beberapa contoh dari teknik descriptive mining. Data stream Data stream adalah transaksi yang tersusun secara beraturan yang datang tepat pada waktunya. Berbeda dengan data yang ada pada 1
basisdata statis biasa, data stream memiliki beberapa karakteristik. Pertama, data tersebut bersifat kontinyu, tak terhingga atau tak terbatas dan biasanya datang dengan kecepatan yang tinggi. Kedua, volume dari data stream berukuran besar. Ketiga, penyebaran data pada data stream biasanya berganti seiring dengan waktu (Nan & Gruenwald 2006). Data stream dapat dikelompokkan menjadi dua yaitu (Nick & Divesh 2005): • Transactional data stream, berupa catatan interaksi antar item. Contohnya seperti Credit Card, pembelian oleh konsumen dari penjual. Telekomunikasi, panggilan telepon oleh penelepon kepada pihak penerima. Web, sumber daya yang diakses oleh client pada server. • Measurement data stream, berupa evaluasi pengamatan dari suatu keadaan. Contohnya seperti IP Network, lalu lintas yang terjadi pada router interface. Iklim bumi seperti temperatur dan kelembapan pada stasiun cuaca. Data stream mining Tidak jauh berbeda dengan data mining, data stream mining merupakan suatu proses untuk menemukan pola-pola yang menarik namun data yang akan diproses merupakan data yang berupa data stream. Tidak seperti data biasanya, data stream masuk dan keluar dari sebuah sistem komputer secara kontinyu dan dengan tingkat pembaharuan data yang memiliki rataan yang berbeda. Biasanya data tersebut bersifat sementara, cepat berubah, berukuran sangat besar, dan memiliki potensial untuk tidak terbatas (Han & Kamber 2006). Metodologi yang dapat digunakan untuk praproses data stream, diantaranya adalah (Han & Kamber 2006): 1. 2. 3. 4. 5. 6.
pattern mining adalah proses untuk menemukan pola yang sering muncul pada dataset (Han & Kamber 2006). Secara tidak langsung dalam melakukan proses frequent pattern mining terjadi juga proses pencarian frequent item. Berdasarkan dari lengkap tidaknya pola yang akan diekstrak dari dataset, ada beberapa cara untuk melakukan proses pengekstrakan tersebut, diantaranya adalah (Han & Kamber 2006): • • • • • • •
Complete set of frequent itemsets Closed frequent itemsets Maximal frequent itemsets Constrained frequent itemsets Approximate frequent itemsets Near-match frequent itemsets Top-k frequent itemsets
Closed frequent itemset Dalam analisis asosiasi, koleksi nol atau lebih item disebut itemset. Jika itemset berisi k item, maka disebut k-itemset. Contoh, {A, B, C} adalah 3-itemset. Set null atau kosong adalah itemset yang tidak berisi item. Jumlah transaksi yang mengandung suatu itemset adalah support count. Sebuah itemset disebut frequent jika support count dari itemset tersebut sudah memenuhi atau lebih besar dari nilai minimum support (Tan et al. 2006). Itemset memiliki 2 tipe yaitu superset dan subset. Superset adalah itemset parent dari sebuah itemset, sedangkan subset adalah child atau bagian dari itemset. Sebuah itemset X bersifat closed pada sebuah dataset S apabila tidak terdapat superset dari X yaitu Y yang nilai frequent-nya sama dengan itemset X (Han & Kamber 2006). Contoh closed itemsets dapat dilihat pada Gambar 1.
Random Sampling Sliding Window Histogram Multiresolution Methods Sketches Randomized Algorithms
Pada pembahasan kali ini, akan digunakan metodologi sliding window untuk melakukan praproses data stream yang ada sebelum dilakukan proses lebih lanjut. Frequent pattern mining Frequent pattern adalah pola (seperti itemsets, subsequences, atau substructures) yang sering muncul pada dataset. Jadi, Frequent
Gambar 1. Contoh closed itemsets. Dari Gambar 1, semua itemsets bersifat closed, kecuali itemset {b} dan {d, e}. Hal itu karena {b} adalah subset dari {b, c}, dimana keduanya memiliki nilai support yang sama yaitu 3 atau 30%. Sedangkan untuk {d, e}, itemset {d, e} adalah subset dari {a, d, e}, 2
keduanya juga memiliki nilai support yang sama yaitu 4 atau 40%. Untuk gambar subset lattice yang sesuai dengan Gambar 1 diatas, dapat dilihat pada Lampiran 1. Gambar kotak berwarna merah merupakan closed itemsets, gambar kotak berwarna biru merupakan frequent itemsets dan kotak berwarna putih merupakan itemsets yang tidak frequent (Borgelt 2005). Maka, closed frequent itemset adalah jika pada suatu itemset bersifat closed dan juga frequent pada sebuah dataset (Han & Kamber 2006). Association rule Association rule adalah salah satu teknik dalam data mining yang bertujuan untuk mengekstrak hubungan yang menarik, pola– pola yang sering muncul, hubungan kumpulan item di dalam suatu database atau datawarehouse yang berisi record transaksi (Zhao et al. 2003). Terdapat dua hal utama yang melandasi teknik ini yaitu support dan confidence (Zhao et al. 2003). Kekuatan aturan asosiasi dapat diukur dengan support dan confidence. Support menentukan seberapa sering aturan tersebut diterapkan dalam dataset, sedangkan Confidence menentukan frekuensi item dalam Y muncul dalam transaksi yang mengandung X (Tan et al. 2006). Jika itemset X = {A, B} dan Y = {A, B, C} maka X U Y = {A, B, C}, maka support dapat dihitung dengan menerapkan rumus sebagai berikut, dimana X U Y adalah itemset gabungan antara itemset X dan Y dan N adalah banyaknya transaksi (Tan et al. 2006):
Nilai Confidence dapat dihitung dengan menggunakan rumus sebagai berikut (Tan et al. 2006):
Window Window terdiri atas tiga model, diantaranya adalah landmark window, damped window, dan sliding window (Zhu & Shasha 2001). Sliding window adalah teknik pemrosesan data stream dengan cara penghitungan dari data terbaru atau dengan kata lain, setiap data yang datang, langsung diproses (Han & Kamber 2006).
Gambar 2. Contoh sliding window. Sliding window akan menghasilkan window dari data yang ada, proses pembuatan window tersebut memiliki rumus: S=T-W+1 S merupakan banyaknya window yang terjadi. T merupakan jumlah banyaknya transaksi atau itemset dan W merupakan ukuran window yang diinginkan. Jika ukuran sliding window adalah W dan waktu pada saat window tersebut berada yaitu t, maka window yang diproses adalah pada window [t - W + 1] pada waktu ke t. Ketika waktu berganti, window akan tetap berukuran W dan berpindah seiring waktu t (Zhu & Shasha 2001). FP–Tree FP–Tree atau Frequent Pattern Tree merupakan suatu algoritme yang dirancang untuk mengatasi kendala bottleneck pada proses penggalian data dengan algoritme Apriori (Zhao et al. 2003). Definisi dari FP–Tree dijelaskan sebagai berikut (Han & Kamber 2006): • Terdiri atas sebuah root dengan label “null”, sekumpulan subtree yang menjadi child dari root dan sebuah tabel frequent header. • Setiap node dalam FP–Tree mengandung tiga informasi penting, yaitu: label item, menginformasikan jenis item yang terdapat pada node tersebut, support count, merepresentasikan jumlah lintasan transaksi yang melalui simpul tersebut dan pointer penghubung yang menghubungkan label item yang sama antar lintasan dalam FP–Tree yang ditandai dengan garis putus – putus. • Isi dari setiap baris dalam tabel frequent– header terdiri atas label item dan head of nodelink yang menunjuk ke node pertama dalam FP–Tree yang menyimpan label item tersebut. FP–Tree merupakan suatu struktur data berbentuk tree yang menyimpan item–item yang 3
frequent atau nilainya yang lebih besar dari minimum support yang diberikan. Berikut ini merupakan contoh pembangunan FP–Tree pada window pertama dengan nilai minimum support sebesar 2 atau 40% sebagai berikut: Tabel 1. Transaksi dalam sebuah dataset Transaksi 1 2 3 4
Items B, C A, B A, C, D A, C, D
Gambar 4. FP –Tree pembacaan transaksi 2.
Dalam proses pemindaian pertama akan dihasilkan 1–itemset. Hasil 1–itemset yang didapatkan adalah: Tabel 2. Frekuensi kemunculan itemset terurut Itemset A C B D
Support 3 3 2 2
Setelah dilakukan pemindaian pertama, didapat hasil 1-itemset yang memiliki frekuensi minimum support count = 2 adalah seperti berikut ini: { (A : 3), (C : 3), (B : 2), (D : 2) } (angka setelah karakter “:” menunjukkan nilai support count-nya. Kemudian transaksi akan diurutkan kembali, dari item yang memiliki support count yang paling besar sampai yang nilainya memenuhi nilai minimum support-nya. Tabel 3. Transaksi items terurut Transaksi 1 2 3 4
Items C, B A, B A, C, D A, C, D
Gambar 3 sampai 5 mengilustrasikan pembangunan FP–Tree setelah pembacaan transaksi 1, 2, dan keseluruhan FP–Tree yang terbentuk.
Gambar 5. FP –Tree utuh. Algoritme FP-Growth Algoritme FP–Growth merupakan salah satu algoritme penggalian data yang akan membangkitkan suatu struktur data Tree atau yang disebut dengan FP–Tree. Algoritme ini melibatkan tiga langkah utama (Han & Kamber 2006), yaitu: 1. Tahap pembangkitan kondisional pattern base. 2. Tahap pembangkitan kondisional FP– Tree. 3. Tahap pencarian frequent itemset. Sehingga jika FP–Tree pada Gambar 4 menjadi masukan untuk algoritme FP–Growth, maka akan menghasilkan frequent itemset yang terdapat pada Tabel 4. Tabel 4. Frequent itemset terbentuk Item A B C D
Frequent Itemset {A} {B} {C}, {C,A} {D}, {D,C},{D,A},{D,C,A}
Global closed frequent itemsets tree
Gambar 3. FP –Tree pembacaan transaksi 1.
Global Closed Frequent Itemsets Tree (GCFIT) adalah suatu struktur data yang berbentuk tree yang menyimpan hasil dari closed frequent itemset. GCFIT terdiri atas tree yang sudah tersusun secara berurutan dan tabel hash. Ada dua tipe node didalam prefix tree, node tertutup (closed nodes) dan node perantara (intermediary nodes) yang menjadi penghubung dari node yang tertutup (Fujiang et al. 2008)
4
Tabel hash menyimpan semua pointer yang menunjuk pada node yang tertutup didalam prefix tree dan menggunakan tuple (support) sebagai kuncinya. Apabila ada dua closed frequent itemset yang terletak pada jalur yang sama masing-masing memiliki prefix yang sama, nilai dari support yang diambil adalah nilai support yang lebih besar.
Gambar 7. Pseudocode FPCFI.
Gambar 6. Contoh GCFIT. Gambar 6 adalah contoh dari GCFIT, dimana menyimpan closed frequent itemsets. Node yang berbentuk kotak adalah tipe node tertutup dan node yang berbentuk oval adalah tipe node perantara. FPCFI Frequent Pattern Closed Frequent Itemsets (FPCFI) adalah suatu proses untuk menemukan pola yang sering muncul dari sebuah dataset, dimana pola tersebut merupakan pola dari itemset yang bersifat closed dan frequent (Fujiang et al. 2008). Algoritme FPCFI merupakan salah satu algoritme penggalian data yang merupakan pengembangan dari algoritme FP-Growth yang menggunakan struktur data FP-Tree dan akan membangkitkan suatu struktur data tree yaitu Global Closed Frequent Itemsets Tree. Algoritme ini, mencakup dua langkah utama, yaitu: 1. Tahap penggalian itemset.
closed
frequent
2. Tahap pembuatan GCFIT dari hasil pencarian closed frequent itemset dengan FP-Growth. Gambar 7 merupakan pseudocode dari pencarian closed frequent itemset algoritme FPGrowth.
GCFIT yang terbentuk dari proses algoritme FPCFI hanya merupakan gambaran hasil akhir dari proses yang dilakukan oleh algoritme FPCFI, bukan seperti tree pada FP-Tree, dimana tree tersebut nantinya akan diterapkan algoritme FP-Growth. ReLIM Algoritme Recursive Elimination (ReLIM) merupakan salah satu algoritme untuk mencari itemset yang sering muncul, dimana idenya didasari oleh algoritme FP-Growth (Borgelt 2005). Algoritme ini bekerja tanpa struktur tree atau struktur data yang kompleks. Kekuatan utamanya bukan pada kecepatannya, tapi dengan strukturnya yang simpel. Algoritme ini memiliki skema pemrosesan sebagai berikut (Borgelt 2005): a. Menghapus semua item dari transaksi yang secara individual tidak frequent (yang tidak muncul sebanyak minimum support yang diinginkan). b. Memilih seluruh transaksi yang mengandung item yang paling tidak frequent dari yang frequent. c. Menghapus item yang tidak frequent ini dan diulangi untuk mendapatkan data. d. Memindahkan item yang sudah diproses dan juga dari database dari semua transaksi, kemudian kembali lagi ke proses awal. Penjelasan berikut ini merupakan contoh skema pemrosesan dengan algoritme ReLIM.
5
Tabel 5. Transaksi pada window pertama yang akan diterapkan algoritme ReLIM Transaksi 1 2 3 4
Items B, C A, B A, C, D A, C, D
Dalam proses pemindaian pertama akan dihasilkan 1–itemset. Hasil 1–itemset yang didapatkan dapat seperti berikut ini:
Gambar 10. Tahap ketiga ReLIM dari prefix D.
Tabel 6. Frekuensi kemunculan itemset terurut Itemset A C B D
Support 3 3 2 2
Setelah dilakukan pemindaian pertama, didapat hasil 1-itemset yang memiliki frekuensi minimum support count = 2. Kemudian transaksi akan diurutkan kembali, dari item yang memiliki support count yang paling kecil atau yang nilainya memenuhi nilai minimum support-nya sampai yang memiliki support paling besar. Tabel 7. Transaksi items terurut Transaksi 1 2 3 4
Items B, C B, A D, C, A D, C, A
Gambar 8 sampai 11 merupakan representasi dari dataset yang sudah dikurangi dan diurutkan dari yang paling kecil sesuai nilai frequent itemnya.
Gambar 11. Tahap terakhir ReLIM dari prefix C. Gambar 11 memperlihatkan prosedur dari metode recursive elimination dengan modifikasi dari daftar transaksi (gambar bagian kiri) dan konstruksi dari daftar transaksi dari proses rekursif (gambar bagian kanan). Algoritme ini bekerja tanpa pembentukan tree ataupun pemrosesan transaksi secara langsung lalu mengelompokkannya kedalam single linked list. Kelebihan dari pendekatan ini adalah dimana struktur data yang diperlukan sangat simpel dan transaksi tidak perlu direpresentasikan, sehingga dapat menghemat memori pada saat proses pengulangannya. Closed frequent itemset pada ReLIM Proses pencarian closed frequent itemset pada ReLIM, hampir sama dengan langkah pencarian closed frequent itemset pada algoritme FPCFI. Perbedaannya, pada algoritme ReLIM, tidak ada langkah kedua, yaitu proses pembentukan tree. Hal tersebut dapat terjadi karena pada algoritme ReLIM, tidak ada proses pembuatan tree. Gambar 12 merupakan kode untuk pencarian closed frequent itemset pada ReLIM.
Gambar 8. Tahap pertama ReLIM.
Gambar 12. Pseudocode closed frequent itemset pada ReLIM. Gambar 9. Tahap kedua ReLIM dari prefix B. 6
Analysis of variance (ANOVA) ANOVA adalah metode statistik yang digunakan untuk menguji kesamaan beberapa rata-rata secara sekaligus. Uji yang digunakan dalam ANOVA adalah uji F karena dipakai untuk pengujian lebih dari 2 sampel (Walpole 1995). ANOVA dapat digolongkan kedalam beberapa kriteria, yaitu: 1. Klasifikasi 1 arah (One Way ANOVA) ANOVA klasifikasi 1 arah merupakan ANOVA yang didasarkan pada pengamatan 1 kriteria.
kedua algoritme tersebut untuk mencari closed frequent itemset. Selain itu, akan dilihat seberapa besar pengaruh penentuan ukuran sliding window terhadap sebuah data stream dalam tahapan praproses. Penelitian ini diharapkan juga, akan memberikan informasi tentang cara kerja algoritme FPCFI dan ReLIM sehingga dapat menentukan metode yang efisien dalam mengekstrak data stream. Dalam melakukan penelitian ini, akan dilakukan dengan beberapa langkah dan digambarkan dalam suatu metode penelitian sesuai Gambar 13.
2. Klasifikasi 2 arah (Two Way ANOVA) ANOVA klasifikasi 2 arah merupakan ANOVA yang didasarkan pada pengamatan 2 kriteria. 3. Klasifikasi banyak arah (Multivariate ANOVA) ANOVA banyak arah merupakan ANOVA yang didasarkan pada pengamatan banyak kriteria. Tabel ANOVA digunakan sebagai acuan untuk melihat faktor-faktor apa saja yang menentukan suatu algoritme memiliki kinerja yang lebih baik. Dalam penentuan hipotesa, akan dibandingkan nilai F Hitung dengan nilai F Tabel. Nilai F Tabel juga tergantung dari nilai α dan derajat bebas. Nilai α merupakan besar dari luas daerah penolakan atau taraf nyata pengujian. Cara pengambilan keputusan dari hipotesa yang dibuat adalah dengan membandingkan nilai F Hitung dengan F Tabel. Jika nilai F Hitung berada dalam nilai penerimaan F Tabel (F Hitung < F Tabel), maka dapat disimpulkan bahwa hipotesa H 0 diterima atau rata-rata tingkat efisiensi waktunya sama atau tidak berbeda nyata. Sedangkan jika nilai F Hitung berada diluar nilai penerimaan F Tabel (F Hitung > F Tabel), maka dapat disimpulkan bahwa hipotesa H 1 diterima atau rata-rata tingkat efisiensi waktunya tidak sama atau berbeda nyata. METODE PENELITIAN Penelitian ini dilakukan untuk membandingkan kinerja dari algoritme FPCFI dan ReLIM pada data stream. Dataset yang akan diproses dengan kedua algoritme tersebut, terlebih dulu akan melalui tahapan praproses dengan menggunakan teknik sliding window. Penelitian ini akan mencatat berapa lama waktu yang dibutuhkan oleh proses utama dari
Gambar 13. Tahapan metode penelitian. Data Contoh dataset yang akan digunakan pada penelitian kali ini merupakan contoh data stream. Dataset yang digunakan sebagai data testing adalah dataset Webdocs dan Accidents. Dataset tersebut berbentuk ASCII atau dituliskan dengan angka-angka. Dataset tersebut telah digunakan pada penelitian yang berkaitan dengan data stream, seperti penelitian Yun Chi (2004). Dataset tersebut diunduh dari situs http://fimi.cs.helsinki.fi/data/. Dataset Webdocs mewakili dataset yang berukuran sedang dan untuk Accidents mewakili ukuran dataset yang lebih besar. Dataset Webdocs merupakan data yang dibangun dari koleksi jaringan dokumen web html. Semua dokumen halaman web sebelumnya disaring dengan memindahkan html tags dan kata yang biasa digunakan (stopwords), dan juga dengan mengaplikasikan algoritme stemming. Selanjutnya pada setiap dokumen akan dibuat distinct transaction yang mengandung semua distinct terms (items) yang muncul bersamaan dengan dokumen itu sendiri. Dataset ini berisi 27.452 transaksi. Dataset Accidents merupakan data yang didapatkan dari “Analysis Form for Traffic Accidents” di Belgia, yaitu berisi setiap kecelakaan lalu lintas yang mengakibatkan luka-luka dan kematian pada jalan utama di 7
Belgia. Dataset ini memiliki 340.184 transaksi rekaman kecelakaan lalu lintas. Dataset ini mengandung banyak sumber informasi dari berbagai keadaan, beberapa diantaranya adalah kondisi lalu lintas (ramai, sedang, sepi), kondisi lingkungan (cuaca, penerangan, waktu kecelakaan), kondisi jalan (permukaan jalan, rintangan), kondisi manusianya (kelelahan, alkohol) dan kondisi geografis (lokasi, karakteristik fisik). Ada 572 nilai atribut yang berbeda yang direpresentasikan pada dataset ini. Rata-rata ada 45 atribut yang terisi untuk setiap kecelakaan pada dataset ini. Praproses dengan sliding window Dataset yang ada akan diproses dengan menggunakan sliding window. Dataset akan ditransformasikan sesuai dengan ukuran window yang dipilih. Dataset akan dibagi menjadi window-window. Banyaknya window yang akan terbentuk, didapat dari hasil pengurangan antara banyaknya transaksi dengan masukan ukuran window, kemudian ditambah satu.
untuk mengekstrak data yang bersifat closed frequent itemset. 3. Melakukan proses pembacaan file teks, filtering, sorting, dan recoding item, kemudian transaksi yang tidak sesuai dengan karakteristik pencarian akan direduksi. 4. Membuat struktur FP-tree dan membangkitkan frequent pattern yang bersifat closed frequent itemset. ReLIM Pada tahap ini, akan dilakukan juga proses penggalian closed frequent itemset. Pemindaian akan dilakukan pada dataset yang didapat dari hasil praproses data dengan sliding window. Selanjutnya akan dibangkitkan semua kemungkinan closed frequent itemset-nya yang sudah memenuhi nilai minimum support-nya dengan menggunakan algoritme ReLIM. Secara umum tahapan-tahapan yang terdapat pada ReLIM adalah sebagai berikut:
Pembacaan dataset menjadi window dilakukan secara bergeser menurun, dimulai dari transaksi yang paling awal sampai dengan transaksi yang paling baru. Window akan dibentuk sesuai dengan ukuran window yang dimasukan. Ukuran window yang akan diterapkan pada dataset adalah 5, 10, 15 dan 20. Penggunaan ukuran window yang berbeda tersebut, diharapkan dapat menghasilkan output yang bervariasi, sehingga dapat memberikan hasil analisis yang bervariasi pula. Setelah semua proses dilakukan, maka akan terbentuk dataset yang telah diproses dengan sliding window.
1. Menentukan nilai dari minimum support ReLIM dari contoh dataset yang akan diproses.
FPCFI
4. Singly linked list yang bersifat closed frequent akan dibangkitkan dan dari hasil singly linked list yang terbentuk, akan dibuat frequent pattern yang bersifat closed frequent itemset.
Pada tahap ini, akan dilakukan proses penggalian closed frequent itemset. Pemindaian akan dilakukan pada dataset yang didapat dari hasil praproses data dengan sliding window. Nantinya akan dibangkitkan semua kemungkinan closed frequent itemset-nya yang sudah memenuhi nilai minimum support-nya dengan menggunakan algoritme FPCFI. Secara umum tahapan-tahapan yang terdapat pada FPCFI adalah sebagai berikut: 1. Menentukan nilai dari minimum support FPCFI dari contoh dataset yang akan diproses. 2. Melakukan proses frequent pattern dengan menggunakan fungsi FPCFI
2. Melakukan proses frequent pattern dengan menggunakan fungsi ReLIM, yaitu dengan pembentukan single linked list terlebih dahulu, untuk mengekstrak data yang bersifat closed frequent itemset. 3. Melakukan proses pembacaan file teks, filtering, sorting, dan recoding item, kemudian transaksi yang tidak sesuai dengan karakteristik pencarian akan direduksi.
Analisis hasil Hasil dari pengujian yang didapatkan dari algoritme penggalian data dalam penelitian ini akan dikaji. Pengkajian dilakukan dengan melihat hasil yang didapat dari proses penggalian dengan algoritme yang digunakan. Proses penggalian dilakukan dengan membuat rancangan percobaan. Faktor-faktor yang menjadi landasan untuk rancangan percobaan adalah algoritme itu sendiri dan juga ukuran window yang digunakan pada praproses dataset dengan sliding window. Proses penggalian juga diulangi sampai 3 kali pengulangan untuk 8
melihat perbedaan atau variasi yang terjadi pada saat proses penggalian dilakukan. Hasil yang didapatkan akan dianalisis dengan menggunakan metode ANOVA. Proses ANOVA yang dilakukan pada hasil penggalian tersebut diharapkan dapat memberikan suatu kesimpulan yang dapat menunjukkan perbedaan kinerja algoritme dalam penggalian closed frequent itemset pada dataset yang digunakan. Oleh karena itu, dibuat hipotesa untuk membantu dalam mengambil kesimpulan. Hipotesanya adalah: H 0 : Setiap algoritme pada setiap ukuran sliding window memberikan rata-rata tingkat efisiensi waktu yang sama atau tidak berbeda nyata dalam menentukan closed frequent itemset. H 1 : Ada suatu algoritme pada suatu ukuran sliding window yang memberikan rata-rata tingkat efisiensi waktu yang tidak sama atau berbeda nyata dalam menentukan closed frequent itemset. Kedua hipotesa tersebut merupakan acuan untuk menentukan kesimpulan pada hasil ANOVA yang telah didapatkan. Lingkungan implementasi dan eksperimen Lingkungan implementasi dari penelitian ini menggunakan sistem operasi Windows 7 dan bahasa pemrograman C++ dan kompiler GNU C++. Lingkungan eksperimen untuk aplikasi yang diujicobakan pada penelitian ini adalah pada perangkat keras dengan spesifikasi: processor Intel Core 2 Duo, Ram 3 GB DDR2, HDD 320 GB. HASIL DAN PEMBAHASAN Data yang akan diproses, terdiri atas 2 contoh data yang sering digunakan untuk penelitian data stream mining. Data yang berukuran sedang diwakili oleh dataset Webdocs dan data yang berukuran besar diwakili oleh dataset Accidents, kedua data tersebut juga bertipe file teks. Masing-masing dataset tersebut memiliki karakteristik utama yang sama, dimana setiap transaksinya dipisahkan menjadi bentuk baris, kemudian masing-masing item pada transaksi tersebut dipisahkan oleh karakter spasi. Implementasi algoritme Penelitian ini menggunakan program untuk melakukan pemrosesan dalam mendapatkan closed frequent itemset. Program ini merupakan adaptasi dari program yang dibuat pada penelitian mengenai frequent pattern mining
(Borgelt 2005). Fitur utama program ini adalah melakukan praproses sliding window dan melakukan pencarian closed frequent itemset. Program ini diimplementasikan dengan menggunakan bahasa pemrograman C++. Fungsi yang digunakan dalam program ini, mencakup fungsi untuk input output file dan juga fungsi rekursif. Contoh fungsi input output file adalah membaca sebuah teks file dan juga menuliskan hasil dari pemrosesan kedalam sebuah file teks. Program ini terdiri atas 2 algoritme untuk melakukan pencarian closed frequent itemset, yaitu dengan berbasis FP-Growth dan juga pencarian closed frequent itemset dengan recursive elimination. Perbedaan utama dari kedua algoritme tersebut adalah pada FPCFI terdapat fungsi untuk membuat FP-Tree, sedangkan pada ReLIM, fungsi untuk membuat FP-Tree tersebut tidak ada. Fungsi utama dari program kedua program tersebut adalah fungsi untuk filtering, sorting, dan recoding items serta reducing transaction. Fungsi untuk filtering items melakukan proses pemindahan terhadap transaksi yang telah dibaca dari suatu file teks, menjadi item-item terpisah untuk setiap transaksinya. Fungsi recoding items melakukan proses penghitungan nilai support dari masing-masing item. Sedangkan untuk fungsi sorting items adalah proses untuk mengurutkan item pada setiap transaksi sesuai dengan besar nilai support item tersebut. Setelah proses tersebut selesai, selanjutnya fungsi reducing transaction dilakukan. Fungsi ini melakukan proses pengurangan transaksi yang tidak memenuhi nilai minimum support. Terdapat juga fungsi rekursif untuk melakukan pengecekan terhadap masing-masing transaksi, apakah transaksi tersebut tergolong closed frequent itemset atau tidak pada kedua program tersebut. Pengecekan transaksi tersebut yaitu dengan melihat terlebih dahulu nilai prefix dari sebuah itemset dan nilai banyaknya item. Apabila nilai prefix-nya tidak sama dengan nilai itemset pada saat dilakukan pengecekan, maka itemset tersebut bersifat closed. Selain itu, program ini juga mengambil fungsi yang berhubungan dengan sistem, yaitu fungsi clock. Fungsi ini digunakan untuk menghitung berapa durasi waktu yang dibutuhkan oleh suatu fungsi atau fungsi utama pada tiap-tiap program untuk melakukan proses tersebut.
9
Sliding window Sliding window pada dataset Webdocs dan Accidents dilakukan dengan memasukkan ukuran nilai sliding window. Nantinya, ukuran tersebut akan menjadi nilai input bagi program untuk menentukan berapa besar lebar dari window untuk membaca transaksi yang ada pada dataset. Banyaknya transaksi dari dataset Webdocs adalah 27.452 dan banyaknya transaksi dari dataset Accidents adalah 340.183. Tabel 8 dan 9 menunjukkan hasil sliding window pada dataset Webdocs dan Accidents. Tabel 8. Hasil sliding window Ukuran Sliding Window 5 10 15 20
Dataset Webdocs Jumlah Jumlah Window Transaksi 137240 27448 274430 27443 411470 27438 548660 27433
Tabel 9. Hasil sliding window Ukuran Sliding Window 5 10 15 20
Dataset Accidents Jumlah Jumlah Window Transaksi 1700895 340179 3401741 340174 5102536 340169 6803281 340164
Dari hasil sliding window kedua dataset pada Tabel 8 dan 9 kecenderungan jumlah transaksi yang terbentuk menurut ukuran sliding window dari transaksi awal adalah kurang lebih N kali dari transaksi awal dan kecenderungan jumlah window yang terbentuk adalah banyaknya transaksi dikurangi N, dimana N adalah ukuran sliding window yang diujicobakan. Hal itu juga berpengaruh pada besar ukuran dari file. Hasil percobaan dataset Dataset Webdocs yang telah didapat dari proses sliding window selanjutnya akan diproses kembali dengan algoritme FPCFI dan ReLIM. Proses percobaan dilihat dari 2 faktor, yaitu ukuran sliding window dan algoritme. Dataset akan diujicobakan untuk tiap-tiap ukuran sliding window dan juga setiap algoritme. Proses percobaan akan diulangi sebanyak 3 kali. Hasil yang dicatat dari percobaan tersebut adalah lama waktu pemrosesan pada setiap tahap yang ada pada setiap algoritme dan total waktunya. Tabel 10 merupakan hasil pencatatan ratarata waktu total pencarian closed frequent
itemset dari dataset Webdocs. Hasil lama waktu pemrosesan pada setiap tahap dalam algoritme dan pengulangannya dapat dilihat pada Lampiran 2. Tabel 10. Hasil rata-rata waktu pada percobaan dataset Webdocs Sliding Window 5 10 15 20
Algoritme FPCFI ReLIM 0.47 0.43 0.78 0.73 1.08 1.02 1.39 1.31
Pada Tabel 10, rata-rata total lama waktu proses pencarian closed frequent itemset untuk algoritme ReLIM, terlihat lebih baik dibandingkan dengan algoritme FPCFI. Daftar kode 1-itemset dari dataset Webdocs dapat dilihat pada Lampiran 4 sedangkan hasil penggalian closed frequent itemset secara keseluruhan dapat dilihat pada Lampiran 5. Hasil penggalian diatas, menggunakan FPCFI dengan ReLIM dengan batas minimum support 50%.
Gambar 14. Diagram nilai rata-rata kinerja untuk dataset Webdocs. Dari Gambar 14, terlihat bahwa semakin kecil ukuran sliding window, maka semakin sedikit pula waktu yang dibutuhkan oleh algoritme untuk melakukan proses penggalian. Pada Lampiran 2, dari keempat ukuran sliding window yang diujicobakan, waktu pemrosesan tahap filtering, sorting dan recoding items, pada dataset Webdocs untuk algoritme FPCFI terlihat sama atau lebih baik daripada algoritme ReLIM walaupun tidak berbeda nyata. Jika dilihat dari tahap reducing transaction, hal sebaliknya terjadi, terlihat bahwa algoritme ReLIM lebih baik daripada algoritme FPCFI, walaupun juga tidak terlalu jauh selisihnya. Hasil association rule dari dataset Webdocs dengan minimum support 50% dan minimum confidence 60% dapat dilihat pada Lampiran 6. Dari hasil association rule yang didapat, salah satu kesimpulan yang dapat ditarik adalah 10
“Kemungkinan diaksesnya halaman depan suatu situs setelah mengakses halaman teknologinya, memiliki tingkat kemungkinan 95.6%”, untuk rule “Halaman Teknologi → Halaman Depan”(49 → 122) sebesar 95.6%. Setelah dataset Accidents juga telah diproses dengan sliding window, selanjutnya akan diproses kembali dengan algoritme FPCFI dan ReLIM. Tabel 11 merupakan hasil pencatatan rata-rata waktu total pencarian closed frequent itemset dari dataset Accidents. Hasil waktu pemrosesan pada setiap tahap dalam algoritme dapat dilihat pada Lampiran 3. Tabel 11. Hasil rata-rata waktu pada percobaan dataset Accidents Sliding Window 5 10 15 20
Algoritme FPCFI ReLIM 8.18 6.89 17.53 13.12 24.72 20.93 35.18 27.13
Hasil rata-rata total lama proses pencarian closed frequent itemset pada dataset Accidents yang terdapat pada Tabel 11 untuk algoritme ReLIM menunjukkan indikasi bahwa, semakin besar ukuran sliding window, maka semakin terlihat pengaruh cepat atau tidaknya kinerja algoritme tersebut pada dataset, hal itu juga terjadi pada dataset Webdocs. Hasil penggalian diatas, menggunakan FPCFI dengan ReLIM dengan batas minimum support 50%.
tahap reducing transaction, algoritme ReLIM masih unggul dalam perolehan waktu yang jelas lebih sedikit daripada algoritme FPCFI. Daftar kode 1-itemset dari dataset Accidents dapat dilihat pada Lampiran 7 sedangkan hasil penggalian closed frequent itemset secara keseluruhan dapat dilihat pada Lampiran 8. Hasil association rule dari dataset Accidents dengan minimum support 90% dan minimum confidence 90% dapat dilihat pada Lampiran 9. Dari hasil association rule yang didapat, salah satu kesimpulan yang dapat ditarik adalah “Kemungkinan terjadinya kecelakaan yang disebabkan oleh mengendarai kendaraan dengan kecepatan tinggi kemudian disertai dengan faktor manusia yang lengah / ceroboh, memiliki tingkat resiko 99.8%”, untuk untuk rule “Mengendarai dengan kecepatan tinggi → Lengah / Ceroboh”(18 → 12) sebesar 99.8 %. Analysis of variance Dalam menentukan algoritme mana yang memiliki kinerja yang lebih baik, digunakan suatu teknik metode statistik untuk menentukannya. ANOVA dengan uji F digunakan untuk melihat sekaligus menentukan algoritme mana dari kedua algoritme tersebut, yang memunyai kinerja yang lebih baik. ANOVA yang digunakan pada percobaan kali ini adalah ANOVA yang bersifat 2 arah, karena terdapat 2 faktor yang mempengaruhi percobaan tersebut, yaitu sliding window dan algoritme. Proses penggalian diulangi sampai 3 kali pengulangan untuk melihat perbedaan atau variasi waktu yang didapatkan pada saat proses penggalian dilakukan. Hasil yang akan diproses dengan uji ANOVA merupakan rata-rata total waktu yang dibutuhkan dalam penggalian closed frequent itemset dari 3 kali pengulangan. Hasil ANOVA pada dataset
Gambar 15. Diagram nilai kinerja untuk dataset Accidents. Pada Gambar 15, hal yang sama juga terjadi seperti pada dataset Webdocs, dimana terlihat juga bahwa semakin kecil ukuran sliding window, maka semakin sedikit pula waktu yang dibutuhkan oleh algoritme untuk melakukan proses penggalian.
Nilai α atau yang ditentukan sebagai taraf nyata adalah 5% atau 0,05. Penentuan nilai F Tabel, dilihat dari tabel distribusi F-ratio yang sering digunakan untuk ANOVA, disesuaikan dengan nilai derajat bebas dan juga nilai taraf nyatanya. Tabel 12 merupakan hasil ANOVA untuk dataset Webdocs. Tabel 12. Hasil ANOVA dataset Webdocs
Hasil pada tahap filtering, sorting dan recoding items, pada dataset Accidents yang terdapat pada Lampiran 3, terlihat indikasi yang sama dengan dataset Webdocs. Begitu juga pada 11
Pada Tabel 12, nilai F Hitung (Algoritme) > F Tabel (F1), berarti F1 berada di luar daerah penerimaan F Tabel, begitu juga dengan nilai F2, F Hitung (Sliding Window) > F Tabel (F2), berarti hipotesa H 0 yang ditolak dan hipotesa H 1 yang diterima. Tabel 13. Hasil ANOVA dataset Accidents
Pada Tabel 13, nilai F Hitung (Algoritme) > F Tabel (F2), berarti F1 berada di luar daerah penerimaan F Tabel, sedangkan untuk nilai F2 berada didalam daerah penerimaan F Tabel atau F Hitung (Sliding Window) < F Tabel (F2), berarti hipotesa H 0 yang diterima dan hipotesa H 1 yang ditolak. Dari kedua hasil ANOVA, masing-masing dataset secara keseluruhan memberikan hasil yang sama, yaitu menerima hipotesa H 1 dan menolak hipotesa H 0 . Hal tersebut terjadi karena nilai F Hitung yang didapat, berada di luar nilai penerimaan F Tabel. Namun terdapat pengecualian pada dataset Accidents untuk nilai F Hitung (Sliding Window), karena nilainya berada pada nilai penerimaan F Tabel, yang berarti ukuran sliding window memberikan ratarata tingkat efisiensi waktu yang sama atau tidak berbeda nyata. KESIMPULAN DAN SARAN Kesimpulan Penelitian ini dilakukan dengan dua tahap utama yaitu tahap sliding window dan pencarian closed frequent itemsets. Kedua tahap tersebut diterapkan pada 2 data yang berbeda, yaitu: Webdocs dan Accidents. Tahap sliding window adalah tahap praproses dataset untuk membagi dataset menjadi window-window yang nantinya akan diproses lebih lanjut. Tahap pencarian closed frequent itemset menggunakan dua algoritme, yaitu algoritme FPCFI yang menggunakan basis FP-Growth dan algoritme ReLIM. Nilai hasil kinerja dari algoritme pada tiap-tiap dataset yang didapatkan dari penelitian, dianalisa dengan menggunakan ANOVA dengan uji F. Berdasarkan hasil yang didapatkan dari percobaan sebanyak 3 kali, semakin besar data yang diujicobakan, maka semakin terlihat pengaruh suatu algoritme dan ukuran sliding window dalam memberikan suatu hasil.
Semakin besar ukuran sliding window, maka semakin terlihat pengaruh kinerja algoritme tersebut pada dataset. Semakin kecil ukuran sliding window, semakin cepat pula proses pencarian closed frequent itemset pada window tersebut, karena sedikitnya jumlah transaksi yang akan dihitung. Oleh sebab itu, sliding window yang lebih baik adalah sliding window yang berukuran lebih kecil. Dari hasil uji ANOVA, faktor algoritme memberikan rata-rata tingkat efisiensi waktu penggalian closed frequent itemset yang tidak sama atau berbeda nyata pada kedua dataset. Hal yang berbeda ditunjukkan pada faktor ukuran sliding window, yang memberikan ratarata tingkat efisiensi waktu yang sama atau tidak berbeda nyata, hanya pada dataset Accidents. Dari percobaan yang dilakukan pada penelitian ini, faktor yang berpengaruh dalam memberikan efisiensi waktu dalam penggalian closed frequent itemset adalah faktor algoritme, sedangkan faktor ukuran sliding window tidak terlalu berpengaruh. Oleh karena itu secara tidak langsung, algoritme ReLIM memiliki kinerja yang lebih baik daripada FPCFI tetapi tanpa dipengaruhi oleh faktor ukuran sliding window. Saran Penelitian ini dapat dikembangkan lebih lanjut lagi dengan menggunakan teknik praproses window yang lain seperti landmark window dan damped window. Metodologi praproses data stream yang lain juga dapat digunakan, seperti metodologi random sampling, histogram, sketches dan yang lainnya, untuk melihat apakah hasil yang terbentuk sama, dan juga apakah pemrosesannya lebih baik daripada menggunakan teknik sliding window. Proses pengekstrakan frequent itemset dengan cara lain yang sering digunakan dalam data stream mining seperti maximal frequent itemsets juga dapat digunakan, untuk melihat apakah kinerja yang didapatkan, lebih baik daripada yang didapatkan pada penelitian ini. DAFTAR PUSTAKA Ao. Fujiang, Jing. Du, et al. 2008. An Efficient Algorithm for Mining Closed Frequent Itemsets in Data Streams. School of Computer Science, National University of Defense Technology. China. Borgelt, Christian. 2005. Keeping Things Simple: Finding Frequent Item Sets by Recursive Elimination. School of
12
Computer Science, Otto-von-Guericke University of Magdeburg.Germany. J. Han and M. Kamber. 2006. Data Mining: Concepts and Techniques. San Francisco, CA: Morgan Kaufmann. J. Nan, Le Gruenwald. 2006. CFI-Stream: Mining Closed Frequent Itemsets in Data Streams.Proc of KDD’06. K. Nick, Divesh Srivastava. 2005. Data Streams Query Processing. Tan P, Michael S. dan Vipin K. 2006. Introduction to Data Mining. Addison Wesley. Walpole, Ronald E. 1995. Introduction To Statistics. Mcmillan. Y. Chi, H. Wang, et al. 2004. Maintaining Closed Frequent Itemsets over a Stream Sliding Window.Proc of ICDM’04. Zhao
Q, Sourav S. Bhowmick. 2003. Association Rule Mining: A survey, Singapore: Nanyang Technological University.
Zhu Y, Dennis S. 2001. StatStream : Statistical Monitoring Of Thousands Of Data Streams in Real Time, USA: New York University.
13
LAMPIRAN
Lampiran 1 Gambar Subset Lattice closed itemsets dengan minimum support count = 3
14
Lampiran 2 Hasil lama waktu pemrosesan pada setiap tahap dalam algoritme pada dataset Webdocs dalam satuan detik Ulangan ke-1 Algoritme FPCFI pada dataset Webdocs Proses Ukuran Sliding Window 5 10 15 filtering, sorting dan recoding items 0.18 0.27 0.36 reducing transactions 0.28 0.5 0.71 creating frequent pattern tree 0 0 0 TOTAL 0.46 0.77 1.07
20 0.45 0.91 0 1.36
Algoritme ReLIM pada dataset Webdocs Ukuran Sliding Window Proses 5 10 15 filtering, sorting dan recoding items 0.18 0.28 0.36 reducing transactions 0.23 0.45 0.67 TOTAL 0.41 0.73 1.03
20 0.46 0.84 1.3
Ulangan ke-2 Algoritme FPCFI pada dataset Webdocs Proses Ukuran Sliding Window 5 10 15 filtering, sorting dan recoding items 0.18 0.27 0.36 reducing transactions 0.28 0.5 0.71 creating frequent pattern tree 0 0 0 TOTAL 0.46 0.77 1.07
20 0.45 0.91 0 1.36
Algoritme ReLIM pada dataset Webdocs Ukuran Sliding Window Proses 5 10 15 filtering, sorting dan recoding items 0.18 0.28 0.36 reducing transactions 0.23 0.44 0.63 TOTAL 0.41 0.72 0.99
20 0.46 0.84 1.3
Ulangan ke-3 Algoritme FPCFI pada dataset Webdocs Proses Ukuran Sliding Window 5 10 15 filtering, sorting dan recoding items 0.19 0.28 0.37 reducing transactions 0.29 0.52 0.73 creating frequent pattern tree 0 0 0 TOTAL 0.48 0.8 1.1
20 0.48 0.98 0 1.46
Algoritme ReLIM pada dataset Webdocs Ukuran Sliding Window Proses 5 10 15 filtering, sorting dan recoding items 0.2 0.28 0.38 reducing transactions 0.27 0.45 0.65 TOTAL 0.47 0.73 1.03
20 0.47 0.86 1.33
15
Lampiran 3 Hasil lama waktu pemrosesan pada setiap tahap dalam algoritme pada dataset Accidents dalam satuan detik Ulangan Ke-1 Algoritme FPCFI pada dataset Accidents Ukuran Sliding Window Proses 5 10 15 20 filtering, sorting dan recoding items 1.28 2.56 3.9 5.58 reducing transactions 7.5 16.46 20.42 32.67 creating frequent pattern tree 0.15 0.21 0.25 0.38 TOTAL 8.93 19.23 24.57 38.63 Algoritme ReLIM pada dataset Accidents Ukuran Sliding Window Proses 5 10 15 20 filtering, sorting dan recoding items 2.27 2.9 4.4 5.18 reducing transactions 6.66 11.28 17.92 22.56 TOTAL 8.93 14.18 22.32 27.74 Ulangan Ke-2 Algoritme FPCFI pada dataset Accidents Ukuran Sliding Window Proses 5 10 15 20 filtering, sorting dan recoding items 1.2 2.4 3.71 4.68 reducing transactions 6.14 14.28 22.01 27.44 creating frequent pattern tree 0.11 0.18 0.28 0.33 TOTAL 7.45 16.86 26 32.45 Algoritme ReLIM pada dataset Accidents Ukuran Sliding Window Proses 5 10 15 20 filtering, sorting dan recoding items 1.25 2.42 4.1 5.16 reducing transactions 4.87 9.77 16.68 20.84 TOTAL 6.12 12.19 20.78 26
Ulangan Ke-3 Algoritme FPCFI pada dataset Accidents Ukuran Sliding Window Proses 5 10 15 20 filtering, sorting dan recoding items 1.2 2.39 3.41 4.99 reducing transactions 6.85 13.9 19.94 29.11 creating frequent pattern tree 0.12 0.21 0.25 0.37 TOTAL 8.17 16.5 23.6 34.47 Algoritme ReLIM pada dataset Accidents Ukuran Sliding Window Proses 5 10 15 20 filtering, sorting dan recoding items 1.17 2.58 3.78 5.51 reducing transactions 4.44 10.42 15.9 22.15 TOTAL 5.61 13 19.68 27.66
16
Lampiran 4 Contoh kode halaman yang sering diakses pada suatu halaman website dengan batas minimum support sebesar 50% Itemset
Support (%)
Keterangan
122
81.6
Halaman Depan
8
80.3
Halaman Berita
49
66.0
Halaman Teknologi
516
51.1
Halaman Olahraga
124
52.4
Halaman Kesehatan
17
Lampiran 5 Hasil penggalian closed frequent itemset pada dataset Webdocs dengan batas minimum support 50% Closed Frequent Itemset 124 122 124 516 122 516 49 8 122 49 8 49 122 49 8 122 8 122
Support 50.9 52.4 50.3 51.1 58.0 59.6 63.1 66.0 70.3 80.3 81.6
18
Lampiran 6 Hasil penggalian association rule pada dataset Webdocs dengan batas minimum support 50% dan minimum confidence 60% No
Item I
1
516
2
49 8
3
124
4
49
5
49
6
49
7
8
8
122
9
122
10
8
11
122
→
Item II
Support (%)
Confidence (%)
→
122
50.3
98.4
→
122
58.0
97.3
→
122
50.9
97.1
→
122
63.1
95.6
→
8
59.6
90.3
→
8 122
58.0
87.9
→
122
70.3
87.5
→
8
70.3
86.2
→
49
63.1
77.3
49
59.6
74.2
→
124
50.9
62.4
→
19
Lampiran 7 Contoh kode faktor-faktor yang sering menyebabkan kecelakaan dengan tingkat resiko kecelakaan 90% Itemset
Support (%)
Keterangan
17
100
Mengantuk
12
99.8
Lengah / Ceroboh
18
99.7
Mengendarai dengan kecepatan tinggi
16
97.7
Ban Pecah
31
93.5
Kelelahan
20
Lampiran 8 Hasil penggalian closed frequent itemset pada dataset Accidents dengan batas minimum support 90% Closed Frequent Itemset 31 16 18 12 17 31 16 18 12 31 16 18 17 31 16 18 31 16 12 17 31 16 12 31 16 17 31 16 31 18 12 17 31 18 12 31 18 17 31 18 31 12 17 31 12 31 17 31 16 18 12 17 16 18 12 16 18 17 16 18 16 12 17 16 12 16 17 16 18 12 17 18 12 18 17 18 12 17 12 17
Support 91.5 91.6 91.6 91.6 91.7 91.7 91.8 91.8 93.2 93.2 93.2 93.2 93.3 93.3 93.5 93.5 97.4 97.4 97.5 97.5 97.6 97.6 97.7 97.7 99.6 99.6 99.7 99.7 99.8 99.8 100.0
21
Lampiran 9 Hasil penggalian association rule pada dataset Accidents dengan batas minimum support 90% dan minimum confidence 90% No
Item I
1
18
2
18
3
12
4
18
5
18 12
6
31 16 18 12
7
31 16
8
16
9
16
10
16
11
16
12
16
13
16
14
16
15
16 12
16
16 18
17
16 18
18
16 18
19
16 18 12
20
31
21
31
22
31
23
31
24
31
25
31
26
31
27
31
28
31
29
31
30
31
31
31
32
31
→
Item II
Support (%)
Confidence (%)
12
99.6
99.9
→
12 17
99.6
100
→
17
99.8
100
→
17
99.7
100
→
17
99.6
100
→
17
91.5
99.9
→
12 17
91.7
99.9
→
18
97.5
99.8
→
12
97.6
99.9
→
18 12 17
97.4
99.7
→
18 12
97.4
99.7
→
18 17
97.5
99.8
→
12 17
97.6
99.0
→
17
97.7
100
→
17
97.6
100
→
12
97.4
99.9
→
12 17
97.4
99.9
→
17
97.5
100
→
17
97.4
100
→
16
91.8
98.2
→
16 12 17
91.7
98.1
→
16 12
91.7
98.1
→
16 17
91.8
98.2
→
16 18 17
91.6
98.0
16 18
91.6
99.8
→
18 12 17
93.2
99.7
→
18 12
93.2
99.7
→
18 17
93.2
99.7
→
12 17
93.3
99.8
→
18
93.2
99.7
→
12
93.3
99.8
→
17
93.5
100
→
→
22
Lanjutan No
Item I
33
31 18
34
31 18
35
31 12
36
31 18
37
31 18 12
38
31 16
39
31 16
40
31
41
31 16
42
31 16
43
31 16
44
31 16 18
45
31 16 18
46
31 16
47
31 16 18
48
31 16 12
→
Item II
Support (%)
Confidence (%)
→
12 17
93.2
99.7
→
12
93.2
100
→
17
93.3
100
→
17
93.2
100
→
17
93.2
100
→
18 12
91.6
98.0
→
18 12 17
91.5
99.7
→
16 18 12
91.6
98.0
→
18 17
91.6
99.8
→
18
91.6
99.8
→
12
91.7
99.9
→
12
91.6
100
→
17
91.6
100
→
17
91.8
100
→
12 17
91.5
99.9
17
91.7
99.9
→
23
