PENGGALIAN TOP-K FREQUENT CLOSED CONSTRAINED GRADIENT ITEMSETS TANPA BATASAN MINIMUM SUPPORT PADA BASIS DATA RETAIL

Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009

PENGGALIAN TOP-K FREQUENT CLOSED CONSTRAINED GRADIENT ITEMSETS TANPA BATASAN MINIMUM SUPPORT PADA BASIS DATA RETAIL Dhiani Tresna Absari 1), Arif Djunaidy 2) Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya Email: [email protected], [email protected]

ABSTRAK Penggalian top-k frequent closed itemsets dengan algoritma TFP tanpa menggunakan minimum support merupakan salah satu penelitian yang menarik untuk diaplikasikan dalam analisis asosiasi. Di sisi lain, dalam dunia retail, penggunaan parameter batasan gradient perlu dilibatkan dalam analisis asosiasi agar dapat melakukan penyaringan itemset dengan mengacu pada suatu batasan gradient tertentu, sebagaimana dilakukan dalam algoritma Frequent Closed Constrained Gradient Mining (FCCGM). Namun demikian, FCCGM masih mengharuskan pengguna untuk menentukan nilai minimum support. Sehingga, penggabungan algoritma TFP dan FCCGM menjadi menarik untuk dilakukan. Dalam penelitian ini, algoritma TFP dilakukan modifikasi agar dapat dibangkitkan top-k frequent closed itemset dengan batasan gradient tanpa penentuan nilai minimum support. Hasil modifikasi algoritma, yang disebut top-k frequent closed constrained gradient itemsets, melibatkan beberapa langkah tambahan terhadap algoritma TFP. Tambahan langkah tersebut antara lain berupa pembangkitan nilai minimum support secara dinamis untuk membebaskan pengguna dalam menginisialisasi nilai minimum support tersebut dan langkah perhitungan gradient untuk masing-masing item yang terdapat dalam basis data. Selain itu, modifikasi terhadap tabel global header dilakukan untuk menyimpan hasil perhitungan gradient untuk masing-masing itemnya. Langkah pemangkasan gradient pada FP-Tree yang terbentuk, yaitu pemangkasan item yang tidak memenuhi batasan gradient yang diinginkan, dilakukan tepat sebelum proses penggalian frequent closed itemset dijalankan. Terakhir, modifikasi terhadap langkah pembangkitan hasil penggalian frequent closed itemset dilakukan agar hasil akhir dari frequent closed itemsets dapat disimpan secara terurut berdasarkan nilai gradient dan support tertinggi. Hasil uji coba menunjukkan bahwa program yang dibuat mampu membangkitkan top-k frequent closed itemset dengan nilai gradient dan support tertinggi tanpa batasan minimum support pada basis data retail. Waktu komputasi yang diperlukan untuk membangkitkan top-k frequent closed itemset bergantung pada kedalaman FP-Tree yang terbentuk dari transaksi yang dianalisis. Semakin dalam FPTree terbentuk, maka semakin besar waktu komputasi yang diperlukan untuk melakukan proses penggalian . Kata Kunci: bisnis retail, analisis asosiasi, top-k frequent closed itemsets, batasan gradient. PENDAHULUAN Dunia retail selalu mengalami perkembangan yang sangat pesat. Untuk sebuah retail yang cukup besar, bisa terjadi ratusan transaksi dalam setiap harinya, sehingga


jumlah data yang disimpan sangat besar. Data transaksi ini kemudian disimpan dalam suatu basis data retail yang berupa basis data transaksional dan bersifat jarang (sparse). Pihak manajemen dapat memanfaatkan pengetahuan yang dapat dianalisis dari basis data retail untuk lebih memahami pola kebutuhan pelanggan sehingga dapat membantu dalam pembuatan keputusan bisnis. Salah satu cara analisis yang dapat digunakan adalah dengan menggunakan algoritma TFP. Algoritma yang diusulkan oleh Han dkk ini dapat melakukan penggalian top-k frequent closed itemsets tanpa batasan minimum support. Minimum support pada algoritma ini tidak dipakai dengan tujuan untuk menghindari ketidaktepatan dalam menentukan minimum support yang dapat berdampak pada dihasilkannya kandidat itemset yang kurang memuaskan (Han dkk, 2005). Dalam artikel tersebut, algoritma TFP juga dapat berjalan baik ketika diujicobakan pada basis data jarang yang merupakan sifat dari basis data retail. Dalam perkembangan analisis pada basis data retail, saat ini tidak hanya diperlukan sebuah metode untuk melakukan penggalian terhadap frequent closed itemsets saja tetapi diperlukan juga metode untuk melakukan formulasi query dengan batasan gradient. Gradient yang dimaksudkan disini adalah sebuah ukuran/measure yang ditetapkan seperti profit misalnya. Pada tahun 2006 dikembangkan sebuah algoritma Frequent Closed Constrained Gradient Mining (FCCGM) oleh Wang dkk (Wang, dkk, 2006). Algoritma ini dapat melakukan penggalian terhadap frequent closed itemsets dengan batasan gradient tertentu pada sebuah basis data retail. Hasil analisis terhadap algoritma FCCGM menunjukkan adanya kelemahan yang mendasar yaitu masih digunakannya minimum support sebagai batasan yang harus diinisialisasi. Kelemahan dari penggunaan minimum support sendiri telah disampaikan sebelumnya. Minimum support ditentukan dengan cara intuitif sehingga tingkat ketepatannya pun masih diragukan. Sementara sampai saat ini, belum ada satu penelitian pun yang dapat membantu untuk menentukan minimum support yang tepat bagi sebuah kasus. Pada penelitian ini dilakukan sebuah pengembangan terhadap algoritma TFP sehingga dapat dipakai untuk menggali top-k frequent closed itemsets dengan batasan gradient tanpa batasan minimum support. Selain itu, top-k frequent closed itemset yang dihasilkan juga tidak hanya diurutkan berdasarkan nilai support tertinggi saja seperti yang dihasilkan oleh algoritma TFP, tetapi juga berdasarkan nilai gradient. Hal ini diharapkan dapat membantu manajemen retail jika ingin lebih mengutamakan hasil berdasarkan besarnya profit dibandingkan dengan besar nilai support dari suatu itemset. METODE Algoritma ini dikembangkan dengan cara memodifikasi algoritma TFP sehingga dapat melakukan proses pemangkasan gradient dengan cara yang lebih kuat dan k frequent closed itemset tertinggi yang dihasilkan dapat urut berdasarkan nilai measure diikuti dengan support. Terdapat 2 konsep penting yang berhubungan dengan pengembangan algoritma, yaitu algoritma TFP dan algoritma FCCGM. Algoritma TFP Algoritma TFP menggunakan pendekatan FP-Tree dalam melakukan penggalian itemset dan mensyaratkan inisialisasi terhadap dua buah variabel yaitu k dan min_l. K adalah jumlah frequent closed itemset tertingi yang diinginkan pengguna untuk digali dan min_l adalah panjang transaksi minimal pada frequent closed itemset yang akan digali, dimana min_l >=0. Algoritma TFP tidak memerlukan inisialisasi minimum

ISBN : 978-979-99735-7-3 C-19-2


support. Berbeda dengan inisialisasi minimum support, kedua variabel tersebut mudah dipahami dan ditentukan oleh pengguna sesuai dengan kebutuhan. Konsep penting yang harus dipahami pada algoritma ini adalah pembangkitan minimum support. Ada 2 cara untuk membangkitkan minimum support yaitu dengan Close Node Count Array yang digunakan untuk membangkitkan minimum support pada saat penyisipan transaksi didalam FP-Tree serta Descendant Sum yang digunakan untuk membangkitkan minimum support ketika FP-Tree selesai dibangun [Wang, dkk, 2005]. Dengan cara ini, maka minimum support tidak perlu diinisialisasikan tapi dibangkitkan secara dinamis lewat program. Penggalian terhadap frequent closed itemset dilakukan secara rekursif lewat proses penggalian conditional FP-Tree yang terdapat pada algoritma Mine_ Cond_FPTree. Pembentukan conditional FP-Tree, dilakukan secara top-down terhadap global header table sementara proses penggalian lebih lanjut pada conditional FP-Tree yang terbentuk dilakukan dengan cara bottom-up. Selain itu digunakan beberapa metode pemangkasan daerah pencarian seperti item merging. Selanjutnya hasil penggalian frequent closed itemset akan disimpan dalam sebuah array hasil dan diurutkan berdasarkan count tertinggi. Langkah terakhir adalah menampilkan k itemset tertinggi dari array hasil tersebut. Kesimpulan yang dapat diambil dari hasil analisis terhadap algoritma TFP, adalah sebagai berikut : 1. Algoritma TFP dapat menghasilkan k frequent closed itemset tertinggi dan tidak memerlukan minimum support sebagai inputan. Minimum support akan dibangkitkan secara otomatis sesuai dengan keadaan sebuah basis data yaitu pada saat pembentukan FP-Tree dan pada saat setelah FP-Tree selesai terbentuk. 2. Dari hasil uji coba penelitian, algoritma TFP dapat berjalan dengan baik pada basis data yang bersifat sparse yang merupakan sifat dari basis data retail. 3. Algoritma TFP belum dapat digunakan untuk menggali frequent closed itemset yang memiliki batasan gradient. Algoritma FCCGM Sebuah query yang cukup kompleks yang biasa muncul dalam sebuah basis data retail adalah : barang-barang apakah yang sering dijual bersama sebuah produk TV tertentu yang akan memberikan keuntungan 20% lebih banyak dibandingkan keuntungan rata-rata dari semua jenis TV yang ada ? Masalah tersebut dapat diselesaikan dengan mencari frequent closed itemset dengan batasan gradient lewat algoritma FCCGM. Pada algoritma FCCGM, terdapat 2 buah algoritma yang dijalankan secara berurutan, yaitu: a. Algoritma Top X-Average : algoritma ini digunakan untuk memangkas data yang tidak sesuai dengan batasan gradient yang telah ditetapkan. b. Algoritma LCLOSET : algoritma ini digunakan untuk menggali frequent closed itemset dari hasil yang didapatkan lewat lengkah sebelumnya. Algoritma Top X-Average dan LCLOSET yang keduanya merupakan pembentuk algoritma FCCGM berbasis pada FP-growth (Wang, dkk, 2005). Oleh karena itu, langkah-langkah dari algoritma ini adalah membentuk sebuah FP-Tree dari projected database, pemangkasan data yang tidak memenuhi batasan gradient dengan algoritma Top-X Average dan penggalian frequent closed constrain gradient itemset dengan algoritma LCLOSET.

ISBN : 978-979-99735-7-3 C-19-3


Berdasrkan hasil analisis terhadap algoritma dapat disimpulkan bahwa terdapat kelemahan yang mendasar pad algoritma ini, yaitu masih diperlukannnya batasan minimum support untuk diinisialisasikan oleh pengguna. Padahal seperti yang telah disampaikan pada bagian pendahuluan, penentuan minimum support yang tidak tepat oleh pengguna akan mengakibatkan kesalahan dalam menentukan itemset (Wang dkk, 2005). Aspek Kebaruan Penelitian Berdasarkan dari permasalahan yang telah diuraikan, maka diperlukan sebuah algoritma yang dapat melakukan penggalian terhadap top-k frequent closed constrained gradient itemset tanpa inisialisasi batasan minimum support. Untuk itu pada penelitian ini akan dilakukan pengembangan terhadap algoritma TFP sehingga dapat penggalian Top-K Closed Frequent Contrained Gradient Itemsets pada basis data retail yang memiliki karakteristik : a. Tabel global header yang dapat menyimpan perhitungan rata-rata measure. Untuk memenuhi hal ini, maka tabel global header perlu dimodifikasi. b. Tidak memerlukan inisialisasi minimum support. Untuk keperluan ini dapat menggunakan close node count array dan descendant sum pada algoritma TFP untuk melakukan pembangkitan minimum support secara dinamis seperti yang telah diuraikan pada sub bab 2.1. c. Hasil dari algoritma TFP perlu dimodifikasi agar dapat menyimpan hasil penggalian k frequent closed constrain gradient itemset dengan rata-rata measure dan count yang tertinggi. Dengan memperhatikan 3 hal tersebut diatas diharapkan hasil penggalian top-k frequent closed constrain gradient itemset pada basis data retail akan lebih baik karena tidak lagi memerlukan inisialisasi minimum support. Selain itu algoritma yang akan dikembangkan nanti juga menghasilkan k frequent closed itemset dengan nilai rata-rata measure dan count yang tertinggi. Dalam sub bab berikut ini dijelaskan konsep modifikasi tabel global header yang didalamnya terdapat perhitungan rata-rata measure, penjelasan singkat tentang perhitungan pembangkitan minimum support dan penjelasan modifikasi hasil dari algoritma TFP agar dapat menghasilkan top-k frequent closed constrain gradient itemset. Hal-hal ini merupakan kontribusi dari penelitian yang dilakukan. Pembentukan Modifikasi Tabel Global Header Pada algoritma yang dikembangkan, tabel global header perlu dimodifikasi agar dapat menyimpan perhitungan rata-rata measure. Pemangkasan gradient akan dilakukan berdasarkan rata-rata measure dari sebuah item yang dihitung dengan melibatkan seluruh transaksi yang mengandung item tersebut. Ide dasar dari perhitungan rata-rata measure pada saat pembentukan modifikasi tabel global header adalah sebagai berikut, untuk m buah node dengan label I, rata-rata measure dari I yang disimbolkan sebagai avg(I), merupakan jumlah dari seluruh perkalian antara measure dari sebuah transaksi yang mengadung I dengan jumlah item pada transaksi tersebut, dibagi dengan jumlah item yang terlibat dalam semua transaksi yang mengandung I dalam sebuah basis data retail. Secara matematis perhitungan ratarata mesaure ini dituliskan seperti pada persamaan 1. j

avg ( I ) 

 measure( I , t ) * length(t ) i

i 1

i

j

 length(t ) i 1

i

.......................................(1)

ISBN : 978-979-99735-7-3 C-19-4


Keterangan : I : sebuah item pada basis data retail i : penghitung transaksi yang mengandung item I j : jumlah transaksi yang mengandung I pada basis data retail measure(I,ti) : measure item I pada transaksi ke i length(ti) : panjang transaksi ke i Dengan mengacu pada batasan yang harus dipenuhi oleh algoritma TFP, maka transaksi yang terlibat disini adalah transaksi yang memiliki panjang min_l saja. Sementara I sendiri memiliki support >= minimum support yang berlaku pada saat perhitungan tersebut dilakukan. Tabel 1. Projected Database on e

Sumber : Wang, 2006

Untuk lebih memperjelas pengembangan metode ini, diambil sebuah contoh kasus untuk dapat menentukan rata-rata measure dari itemset pada Tabel 1. Beberapa langkah yang harus dilakukan untuk keperluan ini adalah : a. Melakukan pembacaan satu kali terhadap basis data untuk mengetahui panjang transaksi pada sebuah id transaksi tertentu dan menambahkan kolom panjang transaksi pada basis data retail. Maka untuk contoh kasus dengan mengacu pada Tabel 1, setelah melakukan pembacaan, maka ada informasi baru yang muncul dalam bentuk kolom baru pada Tabel 1, sehingga tabelnya akan menjadi seperti Tabel 2. b. Membentuk modifikasi tabel global header. Berbeda dengan tabel global header pada algoritma FCCGM yang menyimpan informasi id item, support serta jumlah measure untuk id item tersebut sebagaimana dijelaskan pada artikel Wang, dkk (Wang, dkk,2006) dan tabel global header pada algoritma TFP yang terdiri dari Id Item, support dan l-count (Wang, dkk, 2005), maka tabel global header pada algoritma ini informasi yang disimpan untuk masing-masing itemnya adalah : id item, support, average measure per item (avg(I)). Id item adalah id dari sebuah item. Support adalah frekuensi kemunculan sebuah item pada basis data. Average measure item I (avg(I)) adalah average measure dari transaksi I..Berdasarkan basis data retail pada Tabel 2 maka dapat dibentuk tabel global header yang digambarkan dalam Tabel 3. Tabel 2. Projected Database One e dengan Kolom Panjang Transaksi

TID

Set of Items

10 20 30 40 50

a,c,f,m,p a,c,d,f,m,p a,b,c,f,g,m b,f,i b,c,n,p

Ordered Set of Items f,c,a,m,p f,c,a,m,p,d f,c,a,b,m,g f,b,i c,b,p,n

ISBN : 978-979-99735-7-3 C-19-5

Measure 25 39 50 26 45

Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009 Tabel 3. Tabel Global Header

f 4 36.64

C 4 40.27

a 3 38.92

b 3 42.33

m 3 38.92

p 3 36.53

Jika diketahui batasan gradientnya adalah 40, maka hanya item c dan b saja yang dapat melewati batasan gradient. Item f,a,m,p yang kemudian disebut non gradient item dapat dipangkas dari tabel global header. FP-Tree kemudian dibentuk dari transaksi-transaksi yang terdiri dari item-item yang memenuhi batasan gradient. Menghilangkan Minimum Support Sebagai Batasan yang harus Diinisialisaikan Metode pembangkitan minimum support pada algoritma TFP dapat digunakan untuk keperluan ini, sebagaimana yang telah dijelaskan pada sub bab 2.1. Minimum support diinisialisasikan dengan nilai 0 untuk pertama kali dan akan dibangkitkan secara dinamis selama proses pembangunan FP-Tree, yaitu pada saat melakukan penyisipan transaksi pada FP-Tree dengan menggunakan perhitungan close node count. Minimum support kembali dilakukan setelah FP-Tree telah selesai terbentu dengan perhitungan descendant sum. Pemangkasan FP-Tree dilakukan tepat setelah sebuah minimum support dibangkitkan oleh masing-masing perhitungan dengan cara memangkas item pada tabel global header yang memiliki support<minimum support beserta simpulsimpul yang bersesuaian pada FP-Tree. Untuk lebih jelasnya, pembaca dapat mengacu pada artikel asli dari algoritma TFP ini. Modifikasi Hasil Akhir Dalam penjelasan sebelumnya, Algoritma TFP hanya dapat menghasilkan top-k frequent closed itemset. Top-k frequent closed itemset adalah k frequent closed itemset dengan nilai count tertinggi. Oleh karena itu, hasil dari algoritma ini perlu dimodifikasi agar dapat menghasilkan k frequent closed itemset yang memenuhi batasan gradient dengan nilai rata-rata measure dan count tertinggi atau disebut dengan top-k frequent closed constraint gradient itemset (top-k fccgi). Rata-rata measure dijadikan dasar penentuan top-k yang pertama sebelum kemudian diikuti nilai count dikarenakan dalam dunia bisnis, apapun dan berapapun kombinasi itemset bisa jadi tidak akan menjadi masalah, selama itemset tersebut dapat memberikan keuntungan sebesar mungkin bagi perusahaan. Hal ini dapat dijadikan salah satu pertimbangan dalam mengambil keputusan bisnis. Ide yang digunakan untuk memodifikasi hasil ini adalah, setelah melakukan pemangkasan gradient maka proses selanjutnya adalah melakukan penggalian frequent closed itemset. Hasil penggalian ini kemudian ditampung dalam sebuah array dan kemudian diurutkan berdasarkan rata-rata measure diikuti oleh count. Kemudian ditampilkan k pertama dari isi array tersebut, yaitu frequent closed constrain gradient itemset dengan panjang transaksi > min_l. Rancangan Algoritma Algoritma ini merupakan pengembangan algoritma TFP dan dijelaskan lewat diagram alir pada Gambar 1. Beberapa bagian dari algoritma TFP yang dimodifikasi adalah pada pembentukan tabel global header, penambahan langkah pemangkasan gradient sebelum proses penggalian dilakukan serta serta modifikasi pengurutan hasil akhir yang terdapat pada notasi diagram alir berwarna kuning. Karena tidak ada perubahan apapun yang dilakukan pada algoritma Mine_Cond_FPTree, maka penjelasan tentang hal ini dapat langsung merujuk pada referensi asal, yaitu pada artikel tentang algoritma TFP yang dituliskan oleh Wang, dkk pada tahun 2005.

ISBN : 978-979-99735-7-3 C-19-6


UJI COBA DAN ANALISIS HASIL Lingkungan perangkat lunak yang digunakan untuk uji coba dalam penelitian ini menggunakan Sistem Operasi Microsoft Windows Xpdengan bahasa pemrograman menggunakan Borland Delphi 5.0 Lingkungan perangkat keras yang digunakan adalah komputer dengan spesifikasi processor menggunakan Intel Core 2 Duo, kapasitas memori DDR2 1 GB dan Harddisk 80 GB. Pengukuran kinerja dari algoritma yang dikembangkan dilakukan dengan menggunakan sebuah skenario. Skenario ini bertujuan untuk melihat pengaruh nilai min_l dan k terhadap kinerja algoritma yang diukur lewat lama waktu penyelesaian masing-masing proses dan keseluruhan proses. Skenario ini diuji dengan menggunakan 3 buah dataset besar yang bersifat jarang dan dijelaskan pada Tabel 4 dibawah ini. Nama Dataset Mushroom T10I4D100K Gazelle

Tabel 4. Karakteristik Dataset Jumlah Item Jumlah Record 120 8124 1000 100000 497 59601

Gambar 1. Diagram Alir Pengembangan Algoritma Top-K Frequent Closed Itemset dengan Batasan Gradient

ISBN : 978-979-99735-7-3 C-19-7


Berdasarkan hasil uji coba pada beberapa dataset, secara umum dapat disimpulkan beberapa hal. Tabel 5 dan Tabel 6 menunjukkan rekap dari ketiga hasil uji coba tersebut. Tanda panah keatas (↑) menunjukkan adanya kecenderungan hasil uji coba meningkat dan tanda panah kebawah (↓) menunjukkan adanya kecenderungan hasil uji coba menurun. Tabel 5. Rekap Hasil Uji Coba Min_L=10 K MinSup

Mushroom ↑ ↓

↑ Waktu Penggalian

Jumlah Transaksi

Tetap

T10I4D100K Gazelle ↑ ↑ ↓ ↓ ↑

↑

↑

Tetap

Kesimpulan Level pencarian Minimum support turun Minimum support turunpemangkasan sedikitFPTree besar  waktu penggalian naik Minimum support turunsemakin banyak transaksi yang bisa disisipkan ke FP-Tree

Tabel 6. Rekap Hasil Uji Coba K=10 Min_L MinSup

Mushroom ↑ ↓

↑ Waktu Penggalian

Jumlah Transaksi

Tetap

T10I4D100K Gazelle ↑ ↑ ↓ ↓

↓(a)

↑(b)

↓

Tetap

Kesimpulan Anchor Node semakin rendah  Minimum support semakin kecil Minimum support turunpemangkasan sedikitFPTree besar  waktu penggalian naik Min_L semakin besar  semakin sedikit jumlah transaksi terlibat

Dari Tabel 5 dan Tabel 6 dapat dilihat, untuk beberapa hal ada kesimpulan yang menyimpang atau terlalu drastis perubahannya. Hal ini dijelaskan sebagai berikut : a. Minimum support akan mengalami penurunan baik ketika nilai k ataupun min_l dinaikan. b. Waktu penggalian dataset T10I4D100K menyimpang dari kesimpulan dikarenakan jumlah transaksi yang terlibat turun cukup signifikan. Hal ini mengakibatkan waktu penggaliannya pun turun, bukan naik. c. Waktu penggalian dataset Gazelle tidak menyimpang dari kesimpulan tetapi kenaikan yang terjadi cukup drastis, hal ini dikarenakan kedalaman FP-Tree cukup dalam karena panjang transaksi yang terlibat cukup panjang. Hal ini mengakibatkan waktu penggaliannya naik cukup drastis. Berdasarkan kedua hal tersebut didapatkan sebuah kesimpulan baru, bahwa waktu proses penggalian juga akan bergantung pada dua hal, yaitu : 1. Jumlah transaksi yang terlibat. 2. Kedalaman FP-Tree. Pada Gambar 2 dan Gambar 3 berikut diperlihatkan grafik yang dapat menunjukkan perbandingan waktu proses dari ketiga dataset besar yang digunakan.

ISBN : 978-979-99735-7-3 C-19-8


Kesimpulan yang dapat ditarik dari grafik tersebut adalah lama waktu proses program yang dikembangkan akan stabil pada saat menggunakan dataset dengan FP-Tree yang memiliki panjang transaksi yang perbedaannya tidak besar, sesuai seperti karakteristik yang dimiliki dataset Mushroom maupun T10I4D100K.

Total Waktu Proses (Detik)

Perbandingan Lama Total Waktu Proses di Min_L=10 4000 3500 3000 2500 2000 1500 1000 500 0 2

4

6

8

10

12

14

20

K Mushroom

Gazelle

T10I4D100K

Gambar 2. Grafik Perbandingan Total Waktu Proses di Min_L = 10

Total Waktu Proses (Detik)

Perbandingan Lama Total Waktu Proses di K=10 4000 3500 3000 2500 2000 1500 1000 500 0 2

4

6

8

10

12

14

20

Min_L Mushroom

Gazelle

T10I4D100K

Gambar 3. Grafik Perbandingan Total Waktu Proses di K = 10

KESIMPULAN Berdasarkan hasil uji coba yang dilakukan dapat disimpulkan beberapa hal sebagai berikut : 1. Dalam penelitian ini telah berhasil dikembangkan algoritma untuk melakukan penggalian k frequent closed itemset dengan nilai gradient dan support tertinggi tanpa batasan minimum support pada satu set transaksi dalam sebuah basis data retail. Algoritma yang menggunakan pendekatan pembentukan itemset dengan menggunakan struktur data frequent pattern tree (FP-Tree) dan telah berhasil diimplementasikan memungkinkan seorang pengguna, khususnya manajemen retail, untuk mendapatkan k frequent closed itemset tertinggi berdasarkan nilai gradient dan support. Itemset yang didapatkan dapat dimanfaatkan oleh manajemen retail untuk melihat pola kecenderungan kebutuhan pelanggan, yang pada gilirannya akan dapat membantu manajemen dalam proses pengambilan keputusan bisnis. 2. Agar algoritma yang dikembangkan dapat digunakan secara nyata, waktu proses untuk melakukan penggalian frequent closed itemset menjadi penting agar pengguna dapat melakukan analisis secara interaktif untuk mendapatkan k frequent closed itemset tertinggi berdasarkan nilai gradient dan support. Untuk ini, hasil uji coba

ISBN : 978-979-99735-7-3 C-19-9


menunjukkan bahwa total waktu komputasi dari proses untuk memperoleh itemset dimaksud bergantung pada kedalaman FP-Tree yang terbentuk dari transaksi yang dianalisis. Semakin dalam FP-Tree yang terbentuk, maka semakin besar waktu komputasi yang diperlukan untuk melakukan proses penggalian. DAFTAR PUSTAKA Han, J., Wang, J., Yiwen, Y. (2001), “ Mining Frequent Pattern without Candidate Generation: A Frequent Pattern-Tree Approach”, Data Mining and Knowledge Discovery, Kluwer Academic Publisher, Netherland, hal. 53-87. Han, J., Wang, J., Yiwen, Y, Tzevetkov, P. (2002), “Mining Top-K Frequent Closed Patterns Without Minimum Support ”, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), Washington, D.C., USA, hal. 211-218 Hirate, Y., Iwahashi, E., Yamana, H. (2004) , “TF2P-growth: An Efficient Algorithm for Mining Frequent Patterns without any Thresholds”, Proceeding of IEEE ICDM'04 Workshop on Alternative Techniques for Data Mining and Knowledge Discoverey, Brighton,UK Lam, J. (1997), Multi Dimensional Constraint Gradient Mining, Thesis, Simon Fraser University, Canada Pei, J., Han, J., Mao, R.(2000), “CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets”. Proceedings of the 2000 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, Dallas, Texas. Tan, P., Steinbach, M., Kumar, V.(2006), Introduction to Data Mining, Pearson Education, Boston. Wang, J. , Han, J., Pei J. (2003), “CLOSET+: Searching for Best Strategies for Mining Frequent Closed Itemset”, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'03), Washington, D.C., USA, hal. 236-345. Wang, J., Han, J., Lu, Y, Tzevetkov, P. (2005), “Mining Top-K Frequent Closed Patterns Without Minimum Support”, IEEE Transactions on Knowledge and Data Engineering , Vol. 17, No.5, hal. 652-664 Wang, J., Han, J., Pei. J. (2006), “Closed Constraint Gradient Mining in Retail Database”, IEEE Transaction on Knowledge and Data Engineering”, Vol. 18, No. 6, hal. 764-769

ISBN : 978-979-99735-7-3 C-19-10

PENGGALIAN TOP-K FREQUENT CLOSED CONSTRAINED GRADIENT ITEMSETS TANPA BATASAN MINIMUM SUPPORT PADA BASIS DATA RETAIL

Recommend Documents