BAB I PENDAHULUAN 1.1 Latar Belakang Apriori merupakan salah satu algoritma yang terkenal dalam mencari frequent pattern dari database transaksi[8]. Prinsip dari algortima Apriori ini adalah jika sebuah itemset frequent maka semua subset dari itemset harus frequent. Namun pada situasi dimana jika ditemukan dataset yang berukuran besar algoritma ini akan mengalami penurunan performansi karena harus melakukan scan database secara berulang ulang. Pada saat ini sebuah metode dalam mencari frequent pattern berbasiskan FP-tree (FP-growth) mempunyai effisiensi yang cukup tinggi dibandingkan dengan pendekatan Apriori[2].
Salah satu keuntungan dari
FP-growth
dibandingkan dengan pendekatan – pendekatan yang lain adalah FP growth di bangun dari sebuah FP tree, dan ukurannya lebih kecil dibandingkan dengan ukuran database yang aslinya dan juga dengan FP growth dapat mengurangi scan database yang berulang ulang dalam proses mining. Algoritma FP-growth menggunakan struktur data yang disebut FP-tree (Frequent Pattern tree) dalam melakukan pencarian frequent pattern[7,13]. Sesuai dengan namanya FP-tree merupakan struktur pohon dimana setiap cabang berisi informasi frequent itemset, dan setiap node menyimpan informasi item dan frekuensinya. Urutan parent dan child dari pohon ini ditentukan oleh frekuensi masing-masing item. Item dengan frekuensi lebih besar akan menjadi parent bagi item dengan frekuensi yang lebih kecil. Begitupula sebaliknya item dengan frekuensi yang lebih kecil akan menjadi child bagi item yang lebih besar. Dengan demikian, yang menjadi daun dari pohon ini adalah item dengan frekuensi yang paling kecil. FP-tree memiliki sebuah header table yang berisi informasi item dan frekuensinya dan memiliki penunjuk ke node yang ada pada tree tersebut. Daftar item pada tabel ini disusun berdasarkan frekuensinya, dimulai dari item dengan
1
2
BAB I PENDAHULUAN
frekuensi terbesar lalu disusul oleh item dengan frekuensi yang lebih kecil dan seterusnya. Setelah header table dan FP-tree dibuat, maka pencarian frequent itemset hanya dilakukan melalui struktur ini, sehingga sampai pada tahap ini pengecekan terhadap database tidak diperlukan lagi. Frequent itemset tingkat berikutnya, diperoleh dengan membuat conditional FP-tree dengan algoritma FP-growth. Algoritma ini bekerja secara rekursif dalam membuat conditional FP-tree . Walaupun kinerja algoritma FP-growth cukup baik, struktur FP-tree kurang sesuai untuk dataset berukuran besar[13]. Solusi dari pernyataan di atas dapat dilakukan dengan melakukan modifikasi pada FP-growth. Modifikasi struktur FP-tree kedalam bentuk tabel memungkinkan dilakukan frequent pattern mining dengan teknik SQL based. Pada Tugas Akhir ini di lakukan studi analisis performansi dan implementasi algoritma SQL based Frequent Pattern Mining dengan FP-growth .
1.2 Perumusan Masalah Dari Penjelasan di atas maka dapat dirumuskan permasalahan pokok diantaranya adalah : 1. Walaupun FP-growth mempunyai kinerja yang lebih baik, namun jika di temui dataset yang berukuran besar, kurang sesuai untuk membangun FPtree di dalam main memory. Bagaimana implementasi integrasi frequent pattern tree dengan RDBMS. 2. Dalam membangun tabel frequent pattern tree pada algoritma SQL based Frequent Pattern Mining dengan FP-growth ini terdapat dua pendekatan yaitu FP dan EFP, meskipun dalam membangun FP-tree pada pendekatan EFP memerlukan tabel tambahan dan ukurannya cenderung lebih besar dari tabel FP-tree, namun pembuatan tabel FP-tree pada pendekatan EFP lebih cepat karena menghindari pengecekan masing-masing
frequent
items seperti yang dilakukan pada pendekatan FP. Bagaimana performansi dari kedua pendekatan ini dalam menangani dataset yang dense maupun yang sparse.
3
BAB I PENDAHULUAN
3. Bagaimana melakukan pengujian dan analisis untuk algoritma SQL based Frequent Pattern Mining dengan FP-growth ini.
1.3 Tujuan Berdasarkan masalah yang telah di definisikan diatas, maka tujuan penulisan Tugas Akhir ini adalah untuk mengimplementasikan SQL based Frequent Pattern Mining dengan FP-growth dalam proses pencarian frequent pattern dan menganalisis bagaimana performansi algoritma ini dalam menangani dataset yang dense maupun yang sparse dilihat dari dua pendekatan yaitu FP dan EFP. Untuk mengukur performansi ini akan digunakan suatu faktor yaitu Efisiensi, dalam hal ini suatu algoritma dikatakan lebih efisien jika algoritma tersebut memerlukan waktu yang lebih sedikit untuk memproses input menjadi output dibandingkan dengan algoritma yang lain.
1.4 Batasan Masalah Dalam Tugas Akhir ini, yang akan dibahas adalah suatu implementasi SQL based Frequent Pattern Mining dengan
FP-growth dengan batasan masalah
sebagai berikut : 1. Tidak menangani pembentukan association rule. 2. Data yang digunakan merupakan data synthetic dan sebuah real dataset yaitu Mushroom. 3. Tidak menangani proses data selection dan preprosessing
1.5 Metodologi Pendekatan sistematis/metodologi yang akan digunakan dalam merealisasikan tujuan dan pemecahan masalah di atas adalah dengan menggunakan langkahlangkah berikut : o Studi Literatur Mempelajari konsep-konsep Data Mining Association melalui pencarian referensi buku-buku, jurnal ilmiah baik dari dalam maupun luar.
4
BAB I PENDAHULUAN
o Pendalaman materi Mendalami materi yang akan digunakan seperti prinsip Apriori, struktur data tree, konsep FP-growth serta SQL based Frequent Pattern Mining dengan FP-growth. o Perancangan dan implementasi Pada perancangan tugas akhir ini digunakan pemodelan terstruktur, kemudian hasil perancangan tersebut di implementasikan dengan menggunakan bahasa pemrograman PHP 4 dan menggunakan basis data MySQL Server 4.1. serta dan Mozilla Firefox web browser. o Analisis dan Evaluasi Menganalisis dengan mengukur hasil implementasi algoritma SQL based Frequent Pattern Mining dengan FP-growth.
1.6 Sistematika Penulisan Tugas Akhir ini akan disusun berdasarkan sistematika pembahasan sebagai berikut:
BAB I
PENDAHULUAN Berisi latar belakang, perumusan masalah, tujuan penelitian, batasan
masalah,
metodologi
pembahasan
dan
sistematika
penulisan. BAB II
DASAR TEORI Berisi berbagai dasar teori yang mendukung dan mendasari penulisan tugas akhir ini
yaitu mengenai konsep data mining,
datamining association rule, dan algoritma yang digunakan dalam association rules. BAB III
PERANCANGAN DAN IMPLEMENTASI Pada perancangan tugas akhir ini digunakan pemodelan terstruktur, kemudian hasil perancangan tersebut di implementasikan dengan menggunakan bahasa pemrograman PHP 4 dan menggunakan basis data MySQL Server 4.1. dan Mozilla Firefox web browser.
5
BAB I PENDAHULUAN
BAB IV
PENGUJIAN DAN ANALISIS Berisi hasil pengujian dan analisis algoritma SQL based Frequent Pattern Mining dengan
FP-growth yang dilihat dari dua
pendekatan yaitu pendekatan FP dan pendekatan EFP serta hasil pengujian dan analisis perbandingan algoritma tersebut dengan hasil penelitian yang lain yaitu FP-growth* . BAB V
PENUTUP Berisi kesimpulan yang diambil dari pembahasan sebelumnya serta memberikan saran untuk penegembangan selanjutnya.
