PENDAHULUAN Latar Belakang Begitu banyaknya fungsionalitas dalam penggalian data terkadang membuat kita harus memilih secara seksama. Pemilihan fungsionalitas yang tepat dalam melakukan suatu penggalian data menentukan keefektifan serta keefisienan waktu yang dibutuhkan dalam mengekstrak data tersebut. Penggalian data dengan pola asosiasi merupakan salah satu pilihan fungsionalitas yang dapat kita cermati karena kegunaanya yang dapat diterapkan pada berbagai macam situasi seperti e-commerce, klasifikasi, pengelompokan dan lain sebagainya. Dalam penggalian data dengan pola asosiasi ditemukan atribut – atribut yang menunjukkan kondisi di mana atribut – atribut tersebut muncul secara bersama – sama dalam suatu data yang diberikan. Penggalian data dengan pola asosiasi ini lebih sering digunakan dalam pengolahan dan analisis data transaksi, selanjutnya lebih dikenal dengan nama market – basket analysis. Ada beberapa algoritme yang dapat digunakan untuk memperbaiki kinerja penggalian data dengan pola asosiasi, namun algoritme tersebut hanya dapat menangani kondisi tertentu saja dan memiliki kekurangan dalam kondisi lainnya. Sementara itu dalam penggalian data keefektifan serta keefisienan sumber daya yang digunakan sangat diperlukan. Pada penelitian yang dilakukan oleh Woon et al. (2004), penggabungan dua buah algoritme FP – GROWTH dengan FOLDARM pada metode assosiasi menghasilkan sebuah algoritme baru (FOLD - Growth) yang memiliki kinerja yang lebih baik. Algoritme ini menggunakan struktur data SOTrieIT. Kinerja dari algoritme tersebut menghasilkan proses yang lebih fleksibel dan efisien jika dibandingkan dengan algoritme – algoritme aturan asosisiasi lainnya seperti Apriori dan FP Growth. Dengan demikian penggunaan algoritme ini diharapkan dapat memperbaiki kinerja algoritme sebelumnya dan dapat diimplementasikan pada kasus penggalian data transaksi berdasarkan market - basket.
menggunakan struktur data SOTrieIT serta algoritme FOLD - Growth. Ruang Lingkup Ruang lingkup dari penelitian ini adalah : 1
2
Penggunaan metode association rule untuk melakukan proses update menggunakan algoritme FOLD – Growth hanya terbatas pada penambahan data transaksi. Pembahasan meliputi analisis hasil penggalian yang meliputi confidence serta support suatu item terhadap item yang lain.
Manfaat Diharapkan dengan adanya penelitian ini, maka dapat menjadi sebuah referensi terhadap pemilihan algoritme dalam metode association rule. Penelitian ini juga memberikan sedikit gambaran mengenai proses update suatu transaksi saat dilakukan penggalian data.
TINJAUAN PUSTAKA Penggalian Data (Data mining) Data mining adalah proses pencarian suatu korelasi - korelasi baru suatu data yang mempunyai makna, pola dan tren tertentu dengan cara menyelidiki atau meneliti suatu data yang berukuran besar yang terdapat di dalam suatu gudang data dengan menggunakan teknologi pengenalan pola serta teknik statistik dan matematika (Larose 2005). Pola Asosiasi (Association Rule) Pola asosiasi ialah salah satu teknik dalam penggalian data yang bertujuan untuk mengekstrak korelasi yang menarik, pola – pola yang sering muncul, hubungan kumpulan item di dalam suatu basis data atau gudang data yang berisi record transaksi (Zhao et al. 2003). Terdapat dua hal utama yang melandasi teknik ini yaitu support dan confidence (Zhao et al. 2003). Support dari suatu association rule didefinisikan sebagai persentase dari record X Y terhadap seluruh jumlah transaksi di dalam basis data. Support dapat dihitung dengan menerapkan rumus sebagai berikut : Support (XY) =
SupportOfXY TotalNumberOfTransaction
Tujuan Penelitian ini bertujuan untuk menerapkan pemangkasan transaksi dengan
Confidence dari suatu association rule didefinisikan sebagai persentase dari jumlah 1
transaksi yang mengandung X Y terhadap jumlah total transaksi yang mengandung X. Confidence dapat dihitung dengan menggunakan rumus sebagai berikut : Confidence (X|Y) =
Tabel 1 Transaksi dalam database D TID 100
Support(XY) Support(X)
200
FP – Tree 300
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 et al. 2000) : • 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.
400
500
Item Yang Dibeli sabun, rokok, snack, buah, daging, beras, mie, minuman rokok, shampo, snack, sabun, pulpen, mie, tisue shampo, sabun, kamper, minyak, tisue shampo, snack, kabel, lampu, minuman rokok, sabun, snack, kertas, pulpen, minuman, mie, bihun
Item Terurut sabun, snack, rokok, mie, minuman sabun, snack, rokok, mie,shampoo sabun, shampoo
snack, shampo, minuman sabun, snack, rokok, mie, minuman
Proses scanning pertama akan menghasilkan large 1 – itemset yang selanjutnya akan digunakan sebagai dasar dalam pengurutan secara menurun dari transaksi pada basis data D. Hasil 1 – itemset yang didapatkan dapat seperti berikut ini : {(sabun : 4), (snack : 4), (rokok : 3), (mie : 3), (shampoo : 3), (minuman : 3) } (angka setelah karakter “:” mengindikasikan jumlah count - nya). Gambar 1 sampai 3 berikut akan mengilustrasikan pembangunan FP – Tree setelah pembacaan transaksi 100, 200, dan keseluruhan FP – Tree yang terbentuk. Head Table Sabun null
• 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 frequent atau nilainya lebih besar dari minimum support yang diberikan, untuk memperjelas algoritme pembentukan FP Tree maka akan diberikan sebuah contoh pembangunan FP – Tree yang mengacu pada basis data D dengan nilai minimum support sebesar 3 (60%) sebagai berikut :
Snack
Rokok
Sabun : 1
Snack : 1
Mie Rokok : 1 Minum Mie : 1
Minum : 1
Gambar 1 FP – Tree pembacaan transaksi 100.
2
Head Table
terhadap item yang frequent secara menurun.
null
Sabun Sabun : 2
2.
Proses pembuatan tree yang diawali dengan pembuatan ROOT (T). Kemudian menjalankan fungsi insert_tree([p|P],T), di mana p adalah elemen pertama dan P merupakan sisa elemen yang ada dalam daftar transaksi.
Snack Snack : 2 Rokok Rokok : 2 Mie Mie : 2 Sampo Minum : 1
Sampo : 1
Minum
Gambar 2 FP-Tree pembacaan transaksi 200.
Head Table Sabun
Snack
Fungsi insert_tree([p|P],T) dijalankan sebagai berikut: Jika T mempunyai anak N dan (N.itemName = p.itemName), maka naikan counter N sebesar 1. Selainnya buat node N baru dan buat link ke parent. Serta node-nya di kaitkan ke node – node yang mempunya label yang sama. Jika P tidak kosong, panggil fungsi insert_tree(P,N) secara rekursif. 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 et al. 2000), yaitu : a b
Rokok
c
Tahap pembangkitan kondisional pattern base. Tahap pembangkitan kondisional FP – Tree. Tahap pencarian frequent itemset.
Sehingga jika FP –Tree pada Gambar 3 menjadi masukkan untuk algoritme FP – Growth, maka akan menghasilkan frequent item sebagai berikut :
Mie
Sampo
Tabel 2 Frequent Itemset Terbentuk Minum
Gambar 3 FP – Tree utuh.
Contoh di atas merupakan salah satu ilustrasi pembentukan FP – Tree dengan penggunaan nilai minimum support sebesar 3 atau 60%. Algoritme pembentukan FP – Tree ini terdiri dari dua langkah utama (Han et al. 2000), yaitu : 1. Proses scanning basis data untuk menemukan 1 – itemset (L), kemudian itemset L digunakan untuk mengurutkan transaksi
Item
Frequent Item
Shampo
Shampo
Minuman
Minuman / {snack minuman }
Mie
Mie / {sabun snack rokok | mie}
Rokok
Rokok / {sabun snack | rokok }
Snack
Snack / { sabun | snack}
Sabun
Sabun
|
SOTrieIT SOTrieIT atau Sub Ordered Trie Itemset merupakan suatu tree yang dibangun dengan 3
mengekstrak 1 – 2 itemset dari setiap transaksi (Zhao et al. 2003). Prinsip penelusuran dalam SOTrieIT memiliki pendekatan yang sama dengan pencarian dengan metode DFS. Cara penelusuran dilakukan dengan scanning dari node pertama yang paling kiri. Jika support count dari satu item di level ke dua tidak mencukupi dari minimum support maka proses berhenti dan pindah ke level atas lainnya. Jika nilai support count pada level atas sudah tidak lagi mencukupi nilai minimum support, maka proses berhenti dan tree terbentuk. Algoritma pembentukan SOTrieIT bekerja dengan melakukan ekstrasi 1 – 2 Itemset dari setiap transaksi yang dibaca. Tahapan pengerjaan dari algoritma ini secara singkat dijelaskan sebagai berikut (Woon et al. 2002): 1.
Menemukan semua 1 - 2 itemset dari setiap transaksi
2.
Menambahkan node baru pada Trie jika node dengan nilai count ialah 1 (satu) jika node tersebut tidak terdapat pada level 1 dan level 2, jika node sudah terdapat dalam Trie maka dilakukan penambahan nilai count di node tersebut dan dilakukan rebalancing antar node dalam Trie tersebut.
Untuk memperjelas uraian di atas akan diilustrasikan pembangunan SOTrieIT dengan basis data D sebagai berikut (Woon et al. 2002) : Tabel 3 Contoh transaksi dalam basisdata D TID
Items
100
AC
200
BC
300
AB C
400
AB CD
Setelah diperoleh transaksinya, selanjutnya akan dibaca transaksi tersebut dan diekstraksi 1 – 2 itemset-nya. Pada saat transaksi 100 dibaca maka akan diekstrak 1 – itemset : {A, C} dan 2 – itemset : {AC} (Gambar 4 a). Selanjutnya saat pembacaan transaksi 200, sistem akan mengekstrak 1 itemsetnya : {B, C} dan 2 – itemsetnya : {BC} (Gambar 4 b). Langkah ini dilakukan berturut – turut sampai pembacaan transaksi 400, sehingga akan menghasilkan SOTreeIT
yang utuh seperti pada Gambar 5.
ROO
ROO C:1
A :1
C:2
A :1
B :1
C:1
C:1
C:1
(a)
(b)
Gambar 4 (a) Pembacaan transaksi 100 pada SOTrieIT (b) Pembacaan Transaksi 200 pada SOTrieIT. ROOT
B :3
A3
C:4
D :1
C:3
B :2
D: 1
C:3
D: 1
D: 1
Gambar 5 SOTrieIT utuh.
Algoritme FOLD – Growth Algoritme FOLD – Growth merupakan hasil gabungan dari algoritme FOLDARM dan FP – Growth. Pada algoritme ini diharapkan dapat menggabungkan keuntungan dan kebaikan dari 2 (dua) algoritme antara FP – Growth dengan FOLDARM. Algoritme FOLDARM yang memiliki kinerja cepat dalam pengukuran itemset frequent maksimum (Kmax) adalah kecil atau K 10, sedangkan algoritme FP – Growth memiliki kinerja yang cepat pada saat Kmax > 10 (Woon et al. 2004). Dalam algoritme ini terdapat pembagian tahap pengerjaan sebanyak 4 (empat) tahapan utama (Soelaiman et al. 2006). Tahapan utama dalam algoritme FOLD – Growth yaitu : a
b
c
Pengalian L1 (Large 1 - Itemset) dan L2 (Large 2 - Itemset) dengan menggunakan SOTrieIT, Pemangkasan item – item yang tidak frequent dalam transaksi menggunakan L1 dan L2, Membangun FP – Tree menggunakan transaksi – transaksi yang telah dipangkas dan, 4
d
Pengalian itemset frequent dengan algoritme FP – Growth. Mulai
Dalam algoritme FP – Growth penggunaan struktur data FP – Tree memiliki kelemahan saat akan dilakukan proses update suatu data transaksi. Kendala yang terjadi ialah dilakukannya proses scanning basis data awal ditambah data transaksi yang akan ditambahkan atau dihapus. Proses ini akan memperlambat kinerja algoritme dalam proses penggalian. Penggunaan struktur data SOTrieIT akan mempermudah proses penambahan atau pengurangan suatu transaksi terhadap suatu basis data. Penggunaan SOTrieIT dalam mengakomodasi perubahan basis data dapat mengefisienkan usaha yang dilakukan program dalam melakukan perubahan transaksi. Gambar 6 di bawah akan menunjukan algoritme yang digunakan dalam proses update transaksi yang baru (Woon et al. 2002).
Studi Literatur
Pengumpulan Data
DATA
Penggalian L1 & L2
Pemangkasan
Pembangunan. FP - Tree
FOLD GROWTH
Penggalian
Analisis Hasil 1 If a new i is added to the universal itemset Do nothing because the SOTrietIT will be updated the moment a transaction i arrives
Dokumentasi
2 Else if an item j is tremoved from the universal itemset traverse the SOTrieIT to remove all nodes and their child nodes (if any that contain j )
Selesai
Gambar 7 Metode Penelitian. Gambar 6 Algoritme universal update itemset.
METODOLOGI PENELITIAN Penelitian ini dilakukan untuk mendapatkan analisis hasil FOLD – Growth terhadap permasalahan dalam penggalian data transaksi. Penelitian ini diharapkan dapat menjadi pembanding dari penilitian sebelumnya terhadap pilihan algoritme dalam menyelesaikan penggalian data berdasarkan metode Association Rule. Untuk memulai penelitian ini dilakukan beberapa langkah yang harus dijalani dan tertuang dalam suatu Metodologi Penelitian sesuai Gambar 7 berikut.
Studi Literatur Studi literatur dilakukan untuk menambah referensi terkait dengan algoritme FOLD – Growth. Pengumpulan informasi tentang proses – proses dalam algoritme ini dikumpulkan dan didapatkan dari beberapa sumber seperti : buku, jurnal, dan artikel di internet. Pengumpulan Data Data yang dipakai merupakan data transaksi yang berasal dari sebuah toko di daerah Bogor. Data ini merupakan data transaksi penjualan barang kebutuhan sehari – hari seperti : makanan pokok, snack, minuman, keperluan mandi dan lain – lain. Data yang diambil masih berupa transaksi biner sehingga diperlukan proses transformasi kembali supaya data dapat digunakan dengan baik. Data mining Implementasi association rule dengan algoritme FOLD - Growth terhadap data yang telah dilakukan preprocessing melewati beberapa tahap pengerjaan seperti yang dijelaskan pada Tinjauan Pustaka. Pada tahap 5
