1
BAB I PENDAHULUAN
Bab pendahuluan ini membahas tentang latar belakang masalah yaitu fenomena perkembangan data yang terus bertambah tetapi informasi yang dihasilkan monoton, sehingga diperlukan data mining untuk menggali pengetahuan baru yang bermanfaat. Bab ini juga membahas rumusan masalah, tujuan dan manfaat penelitian, batasan masalah serta membahas keaslian penelitian.
1.1 Latar Belakang Data mining adalah proses untuk mengekstraksi atau menggali pengetahuan dari data yang berjumlah besar. Data berskala besar memunculkan fenomena “data rich but information poor”, dimana data yang berjumlah besar tidak diikuti dengan peningkatan informasi yang didapat dari data tersebut. Fenomena itu sering muncul pada sistem penjualan yang dipakai di pasar swalayan, dimana data transaksi terus bertambah setiap hari tetapi hanya menghasilkan laporan transaksi harian yang monoton. Hal ini dikarenakan kurangnya analisa terhadap kumpulan data tersebut. Data mining memungkinkan penemuan pola-pola yang menarik, informasi yang tersembunyi dan kemungkinan informasi berharga pada data berskala besar, yang
1
2
belum diketahui sebelumnya. Informasi tersebut kemudian dapat dipakai untuk proses manajemen pelanggan yang lebih baik. Analisis asosiasi adalah salah satu teknik data mining yang digunakan untuk menemukan hubungan menarik antara suatu kombinasi item yang tersembunyi dalam suatu database. Hubungan ini dapat direpresentasikan dalam suatu bentuk aturan asosiasi (Tan, Steinbach, Kumar, 2004). Analisis asosiasi akan berusaha mengungkap asosiasi antara atribut, yaitu berusaha untuk mengungkap aturan untuk mengukur hubungan antara dua atau lebih atribut. Secara umum aturan asosiasi mempunyai bentuk : 𝑰𝑭 𝒂𝒏𝒕𝒆𝒄𝒆𝒅𝒆𝒏𝒕 𝑻𝑯𝑬𝑵 𝒄𝒐𝒏𝒔𝒆𝒒𝒖𝒆𝒏𝒕
Kekuatan hubungan suatu aturan asosiatif dapat diukur dengan dua parameter yaitu support dan confidence. Support (nilai penunjang) adalah persentase kombinasi item tersebut dalam database dan confidence (nilai kepastian) yaitu kuatnya hubungan antar item dalam aturan asosiatif yang terbentuk oleh metode asosiasi dalam data mining. Metode analisis asosiasi, juga dikenal sebagai market basket analysis, yaitu analisis yang sering dipakai untuk menganalisa isi keranjang belanja konsumen dalam suatu pasar swalayan. Contoh penerapan dari aturan asosiatif adalah analisa pembelian produk pada sebuah toko swalayan, pada analisa itu misalkan dapat diketahui berapa besar kemungkinan seorang pelanggan membeli pensil bersamaan
3
dengan membeli penghapus. Penerapan aturan asosiasi dalam kasus tersebut dapat membantu pemilik toko untuk dipakai sebagai pendukung keputusan dalam penjualan seperti mengatur penempatan barang, mengatur persediaan atau membuat promosi pemasaran dengan menerapkan diskon untuk kombinasi barang-barang tertentu yang sering muncul dalam transaksi. Analisis asosiasi didefinisikan sebagai suatu proses untuk menemukan semua aturan asosiasi yang memenuhi syarat minimum untuk support (minimum support) dan syarat minimum untuk confidence (minimum confidence). Dasar analisis asosiasi terbagi menjadi dua tahap, yaitu analisa pola frekuensi tinggi dan pembentukan aturan asosiasi. Analisa pola frekuensi tinggi mencari kombinasi item yang memenuhi syarat minimum dari nilai support dalam database dan pembentukan aturan asosiasi dengan syarat memenuhi syarat minimum untuk confidence. Algoritma apriori termasuk jenis aturan asosiasi pada data mining yang diusulkan pertama kali oleh R. Agrawal dan R. Srikant pada tahun 1993. Algoritma ini didasarkan pada fakta bahwa apriori menggunakan pengetahuan sebelumnya dari suatu itemset dengan frekuensi kemunculan yang sering. Apriori menggunakan pendekatan iteratif dimana k-itemset digunakan untuk mengeksplorasi (k+1)-itemset (Han&Kamber, 2006). Prinsip metode apriori adalah jika suatu itemset sering muncul (frequent), maka semua subset dari itemset itu juga harus sering muncul dalam suatu database (Tan, Steinbach, Kumar, 2004).
4
Pada algoritma ini calon (k+1)-itemset dihasilkan oleh penggabungan dua itemset pada domain/ukuran k. Calon (k+1)-itemset yang mengandung frekuensi subset yang jarang muncul atau dibawah threshold akan dipangkas dan tidak dipakai dalam menentukan aturan asosiasi (Tan, Steinbach, Kumar, 2004). Contoh dari 2itemset adalah pembelian buku tulis bersamaan dengan pensil, contoh dari 3-itemset adalah pembelian buku tulis bersamaan dengan pembelian pensil dan penghapus, dan seterusnya sampai dengan terpenuhi semua kombinasi (k+1)-itemset yang mungkin. Algoritma apriori mempunyai kelemahan yaitu kurang efisien terhadap database yang bertambah besar. Kinerja algoritma apriori akan melambat karena harus melakukan scanning database yang besar dengan jumlah transaksi yang banyak dan iterasi berulang kali untuk mendapatkan kombinasi frequent itemset sehingga membentuk aturan asosiasi yang tepat. Teknik-teknik modifikasi diperlukan untuk melakukan optimasi terhadap kinerja algoritma apriori sehingga mendapatkan frequent itemset yang baik dalam waktu yang singkat. Combination reduction adalah salah satu teknik untuk pengurangan jumlah kombinasi yang dibentuk dengan cara pembentukan calon kombinasi itemset selanjutnya dari frequent itemset yang telah dibentuk sebelumnya. Jaishree Singh, et al pada tahun (2013) dalam penelitiannya “Improving Efficiency of Apriori Algorithm Using Transaction Reduction” melakukan improvisasi algoritma apriori dengan teknik transaction reduction yaitu mengurangi jumlah transaksi yang jumlah item pertransaksinya tidak memenuhi nilai
5
batas yang ditentukan. Pengurangan transaksi tersebut berdampak pada waktu yang dibutuhkan menjadi lebih cepat pada saat scanning database. Sama halnya dengan teknik transaction reduction, combination reduction juga masih mempunyai kelemahan, yaitu jika kombinasi yang dibentuk masih terlalu banyak maka waktu yang dibutuhkan juga masih lama dalam melakukan iterasi. Perlu pendekatan lain yang digunakan agar mampu membatasi jumlah iterasi. Iteration limitation adalah teknik lain untuk melakukan efisiensi waktu pada algoritma apriori yaitu dengan melakukan pembatasan iterasi sampai nilai batas yang ditentukan. Nilai batas dalam hal ini ditentukan berdasarkan jumlah item yang paling sering muncul dalam setiap transaksi dengan menghitung modus item transaksi dari keseluruhan transaksi yang terdapat dalam database. Nilai tersebut kemudian dijadikan pembatas untuk nilai k dalam k-itemset. Dengan latar belakang tersebut diatas maka dalam penelitian ini akan membahas tentang penerapan algoritma apriori untuk menemukan frequent itemset dalam keranjang belanja. Penggabungan teknik modifikasi juga dilakukan untuk meningkatkan kinerja algoritma apriori yaitu dengan menerapkan combination reduction dan iteration limitation. Penelitian akan membandingkan efisiensi waktu serta kualitas aturan asosiasi yang dihasilkan oleh algoritma apriori tanpa modifikasi dengan algoritma apriori yang menerapkan penggabungan teknik combination reduction dan iteration limitation. Harapan dari penelitian ini adalah mempercepat
6
kinerja algoritma apriori dengan menerapkan penggabungan teknik combination reduction dan iteration limitation dalam menghasilkan frequent itemset yang lebih cepat. Studi kasus dilakukan pada minimarket swalayan “Toko Tujuh Belas” dengan menganalisis database transaksi dari bulan Juli 2011 sampai dengan bulan Oktober 2012 untuk dipakai dalam penerapan algoritma apriori.
1.2 Rumusan Masalah Beberapa hal yang ingin diketahui secara spesifik dalam penelitian ini dapat dirumuskan sebagai berikut : a. Bagaimana penerapan metode asosiasi menggunakan algoritma apriori untuk mencari frequent itemset pada database transaksi ? b. Bagaimana kinerja algoritma apriori dengan penggabungan teknik combination reduction dan iteration limitation yang diukur berdasarkan waktu dan kualitas aturan asosiasi dari frequent itemset yang dibentuk ?
1.3 Tujuan Penelitian Tujuan dari penelitian yang dilakukan adalah sebagai berikut : a. Membuat sistem yang mampu menemukan frequent itemset pada database penjualan dengan menerapkan data mining dengan metode asosiasi menggunakan algoritma apriori.
7
b. Menerapkan penggabungan teknik combination reduction dan iteration limitation untuk meminimalisir waktu yang dibutuhkan dalam menemukan frequent itemset yang lebih baik pada database transaksi yang besar. c. Mengetahui perbadingan kinerja algoritma apriori biasa dengan algoritma apriori yang sudah menerapkan penggabungan teknik combination reduction dan iteration limitation yang diukur dari segi waktu dan kualitas aturan asosiasi dari frequent itemset yang dibentuk.
1.4 Manfaat Penelitian Manfaat yang ingin dicapai dari penelitian ini diantaranya adalah sebagai berikut: a. Hasil dari penelitian ini adalah membuat sistem yang mampu menemukan frequent itemset dari keranjang belanja yang lebih baik dengan menerapkan data mining dengan metode asosiasi menggunakan algoritma apriori dengan penggabungan teknik combination reduction dan iteration limitation. b. Penelitian ini diharapkan memberikan kontribusi dalam berbagai bidang sebagai berikut : 1. Penelitian Memberikan kontribusi pengetahuan berupa solusi untuk optimasi algoritma apriori yang efektif dan efisien pada database yang besar dengan menerapkan modifikasi pada algoritma apriori.
8
2. Perusahaan Mengetahui frequent itemset pada proses transaksi yang terjadi sehingga dapat menerapkan strategi pemasaran yang tepat. 3. Umum Mengetahui
penerapan
data
mining
terutama
metode
asosiasi
menggunakan algoritma apriori pada database transaksi.
1.5 Ruang Lingkup Penelitian Mengingat luasnya bidang penelitian, maka dibuat batasan atau ruang lingkup penelitian sebagai berikut : a. Sistem yang dibuat adalah sistem yang mampu menemukan frequent itemset pada keranjang belanja yang tersimpan pada database transaksi penjualan. b. Metode yang dipakai adalah metode data mining dengan metode asosiasi menggunakan algoritma apriori. c. Beberapa teknik modifikasi dilakukan dengan melakukan pengurangan jumlah kombinasi yang dibangkitkan yang disebut combination reduction. Optimasi kedua adalah dengan pembatasan iterasi (k+1)itemset pada algoritma apriori dengan metode modus yang disebut
9
iteration limitation. Tenik efisiensi algoritma apriori ini akan dijelaskan lebih lanjut pada bab metodologi dan perancangan. d. Sistem dibuat dengan menggunakan bahasa pemrograman PHP dan database MySQL.
1.6 Keaslian Penelitian Penelitian sebelumnya yang sejenis adalah penelitian oleh Jogi Suresh dan T. Ramanjaneyulu dengan judul “Mining Frequent itemsets Using Apriori Algorithm”. Penelitian Suresh dan Ramanjaneyulu (2013) masih menggunakan algoritma apriori klasik yang sudah dikembangkan sebelumnya dan belum menggunakan teknik optimasi untuk memperoleh aturan asosiasi yang lebih efisien. Penelitian lain yang sejenis adalah penelitian yang dilakukan oleh Jiao Yabing (2013) dengan judul “Research of an Improved Apriori Algorithm in Data mining Association Rules”. Jiao Yabing dalam penelitiannya sudah melakukan optimasi terhadap algoritma apriori yaitu dengan melakukan modifikasi dengan cara mengurangi jumlah kandidat pada kandidat itemset Ck. Jaishree Singh, et al pada tahun (2013) melakukan penelitian dengan judul “Improving Efficiency of Apriori Algorithm Using Transaction Reduction”. Penelitian Singh, dkk ini melakukan modifikasi algoritma apriori dengan cara mengurangi jumlah transaksi yang jumlah item pertransaksinya tidak memenuhi nilai batas yang ditentukan. Pengurangan transaksi tersebut berdampak pada efisiensi
10
waktu pada saat scanning database. Penelitian-penelitian yang sudah dilakukan sebelumnya belum ada yang membahas penggabungan teknik pengurangan jumlah kombinasi yang dibangkitkan / combination reduction dengan pembatasan jumlah iterasi (k+1)-itemset dengan metode modus yaitu membatasi nilai k sampai dengan jumlah kombinasi itemset yang paling banyak muncul. Penelitian lain tentang algoritma apriori akan dipaparkan lagi pada bagian state of the art. Berikut adalah fish bone diagram dari penelitian-penelitian sebelumnya yang dipakai dasar untuk penelitian yang akan dilakukan, bagian yang ditandai adalah fokus dari penelitian yang akan dilakukan : Database Dummy data Real data
Metode Asosiasi Apriori FP Growth Frequent itemset
Data reduction Data integration Data cleansing
Combination reduction Iteration limitation Candidate reduction Transaction reduction
Preprocessing
Modifikasi
Gambar 1.1 Fish Bone Menemukan Frequent Itemset Menggunakan Algoritma Apriori
Fishbone pada gambar diatas menggambarkan faktor-faktor pendukung pembentukan frequent itemset yang dibuat berdasarkan penelitian-penelitian sebelumnya. Bagian yang ditandai merupakan fokus dari penelitian ini yang sekaligus
11
menjadi pembeda dari penelitian-penelitian sejenis yang telah dilakukan sebelumnya. Database yang digunakan pada peneilitian ini adalah real data / data riil yang diambil dari database transaksi, sedangkan penelitian lain banyak yang memakai dummy data atau data contoh yang dikarang untuk melakukan ujicoba pada sistem. Metode asosiasi yang digunakan adalah apriori, sedangkan penelitian lain ada yang memakai metode FP Growth atau metode lain dari asosiasi. Prepocessing untuk database menggunakan data cleansing yaitu membersihkan database dari data yang rusak. Metode modifikasi untuk optimasi algoritma apriori menggunakan combination reduction dan iteration limitation yang akan lebih dijelaskan pada bab metodologi dan perancangan.
