SISTEM BASIS DATA

ALGORITMA ECLAT

KELOMPOK 3

SERTI LONDONGALLO (H12110003)

KRISTI W. SAIYA (H12110255)

BRYAN NAWANJAYA ARTIKA (H12110275)

ABADI GUNAWAN AZIS (H12110287)

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS HASANUDDIN

2013

ALGORITMA ECLAT

Algoritma eclat digunakan untuk menampilkan itemset mining. Pola frekuensi itemset mining dapat ditemui pada data seperti jika seorang pelanggan membeli roti, pasti juga akan membeli susu. Jenis pola seperti ini disebut kaidah asosiasi (association rules) dan banyak digunakan pada berbagai aplikasi.

Ide dasar dari algoritma eclat ialah meggunakan interseksi (titik potong) tid set (tid = transaksi id) untuk menghitung support dari calon itemset yang jauh dari subset generasi yang tidak terdapat pada prefix tree.

Berbeda pada apriori yang metode pencarian itemsetnya dari umum ke khusus dan menyebar, metode pencarian alternatif pada algoritma eclat ialah dari khusus ke umum. Artinya proses pencarian itemsetnya dimulai dari yang paling sering dikunjungi ke yang paling jarang dikunjungi tanpa harus meperhatikan urutan. Selain itu proses pencariannya juga secara mendalam (depth). Perbedaannya dapat digambarkan seperti berikut.

APRIORI ECLAT

APRIORI ECLAT

Dalam prosesnya, eclat juga didefinisikan secara rekursif. Artinya proses pencarian itemset yang diinginkan akan terjadi secara berkesinambungan sepanjang masih ada itemset yang tersisa. Ada 2 poin utama dalam algoritma eclat, yakni :

1. Menemukan itemset yang frequent (paling sering dikunjungi) dan2. Melibatkan semua itemset yang tersedia dalam artian secara rekursif.

Metode pembentukan itemset pada algoritma eclat :

1. nyatakan setiap item dalam tabel transaksi id (tid) secara vertical

2. menentukan support (pendukung) dari setiap k-itemset dengan menyilangkan tid-list dari kedua (k-1) subset. Pendekatan penyilangannya dapat dimulai dari atas-bawah, bawah-atas atau gabungan keduanya. Untuk lebih jelasnya dapat dilihat pada gambar berikut ini.

Ù ®

A1456789

B1257810

AB1578

Dari pemaparan di atas dapat dilihat bahwa keuntungan dari algoritma eclat ialah proses perhitungan support lebih cepat dibandingkan dengan apriori. Hai ini dikarenakan proses pencarian itemsetnya secara mendalam dan ketika telah ditemukan itemset yang sering dikunjungi maka proses berakhir.

Berbeda pada apriori yang proses pencariannya secara melebar sehingga hal ini membutuhkan waktu yang cukup lama untuk menentukan itemset yang sering dikunjungi karena metode pencariannya secara menyeluruh (satu-satu). Meskipun telah ditemukan itemset yang sering dikunjungi namun jika masih ada itemset yang belum dieksekusi maka proses akan dilanjutkan. Hal inilah yang menyebabkan proses perhitungan support pada eclat jauh lebih cepat dibandingkan apriori.

Namun di sisi lain, eclat juga memiliki kekurangan yaitu penggunaan memorinya jauh lebih besar dibandingkan apriori. Pada proses pembentukan itemset pada eclat digambarkan secara vertikal. Artinya jika transaksi yang terjadi misalkan 10 kali, dan terdapat 20 itemset, maka proses eksekusi yang terjadi ialah sebanyak itemset yang ada yaitu sebanyak 20 kali eksekusi. Kalau apriori tidaklah demikian, eksekusi terjadi sebanyak transaksi yang ada yaitu 10 kali eksekusi. Hal inilah yang menyebabkan ukuran memori pada eclat lebih besar dibandingkan apriori. Akan tetapi, akan memudahkan untuk mengetahui itemset yang sering dikunjungi pada algoritma eclat.

Untuk memperjelas proses kerja dari algoritma eclat, berikut contoh implementasinya menggunakan FP-Tree.

Dari data di atas terdapat itemset yang tidak memenuhi support count yang telah ditentukan yaitu I, J, L, M, N, O dan P karena hanya muncul 1 kali pada transaksi yang terjadi. Item-item tersebut diabaikan saja sehingga diperoleh itemset yang baru.

HeaderSupp. Count ≥ 2Transaksi

Itemset yang baru setelah pemangkasan

FP-Tree pada transaksi pertama

FP-Tree pada transaksi ke-dua

FP-Tree pada transaksi ke-tiga

FP-Tree pada transaksi ke-empat

FP-Tree pada transaksi ke-lima

FP-Tree pada transaksi ke-enam

FP-Tree pada transaksi ke-tujuh

FP-Tree pada transaksi ke-delapan

FP-Tree pada transaksi ke-sembilan

FP-Tree pada transaksi ke-sepuluh

FP-Tree bersyarat untuk F

Sekarang akan dilakukan eksekusi mulai dari item yang memiliki frekuensi terendah yaitu F. Dari gambar FP-Tree pada transaksi ke-sepuluh terlihat jelas bahwa hanya terdapat satu cabang yang mempunyai ending F. Sehingga diperoleh gambar seperti di atas. Pada tahap ini hanya difokuskan pada cabang yang memiliki ending F dan mengabaikan cabang yang tidak memiliki ending F. Kemungkinan kombinasi subset itemset yang megandung item F yaitu {F} {A,F} {C,F} {E,F} {B,F} {A,C,F}, …, {A,C,E,F}

Pada header baru di atas dapat dilihat bahwa item A, B, C dan E termasuk item yang frekuen atau sering dikunjungi. Namun masih ada item yang juga frekuen yang belum dieksekusi yaitu item D sehingga proses rekursif dilanjutkan.

FP-Tree bersyarat untuk D

Pada tahap ini hanya difokuskan pada cabang yang memiliki ending D dan mengabaikan cabang lainnya tanpa ending D. Sesuai dengan support count yang telah ditentukan pada pohon di atas terdapat beberapa item yang tidak frekuen yaitu D, G dan E. Pada header baru terlihat jelas item A dan C merupakan item yang paling frekuen dari semua item yang ada. Kemungkinan kombinasi subset itemset yang megandung item D yaitu {D} {A,D} {C,D} {A,C,D}.

Berikut ini merupakan contoh implementasi dari algoritma eclat menggunakan program R.

Implementasi

## 1041 transaksi yang terjadi, list di bawah merupakan potongan dari data

## beberapa transaksi yang diduplikasi dimasukkan untuk menghasilkan output

dari algoritma

data = list(

c

("2","3","4","6","7","8","10","12","13","14","16","20","23","32","39","41","46

","52","55","60","64","66","73","75","77"),

c("11","42","72"),

c("14","51"),

c("41","51","65"),

c("22","57","65"),

...)

itemsets <- eclat(data, parameter = list(support = 0.1, minlen=2, tidLists =

TRUE, target="frequent itemsets"))

parameter specification:

tidLists support minlen maxlen target ext

TRUE 0.1 2 5 frequent itemsets FALSE

algorithmic control:

sparse sort verbose

7 -2 TRUE

eclat - find frequent item sets with the eclat algorithm

version 2.6 (2004.08.16) (c) 2002-2004 Christian Borgelt

create itemset ...

set transactions ...[78 item(s), 1041 transaction(s)] done [0.00s].

sorting and recoding items ... [3 item(s)] done [0.00s].

creating bit matrix ... [3 row(s), 1041 column(s)] done [0.00s].

writing ... [4 set(s)] done [0.00s].

Creating S4 object ... done [0.00s].

Output data :

inspect(itemsets)

items support

1 {11,

42,

72} 0.1940442

2 {42,

72} 0.1940442

3 {11,

42} 0.1940442

4 {11,

72} 0.1959654

Analisis

Dari hasil di atas dapat dilihat bahwa terdapat 4 itemset yang frekuen sebagai hasil dari algoritma eclat. Hasil outputnya merujuk pada replikasi dari transaksi {11, 42, 72} yang sering muncul pada data. Hasil outputnya menunjukkan bahwa himpunan transaksi {11, 42, 72},{42, 72}, {11, 42} mempunyai support sebesar 19,40 % dan transaksi {11, 72} mempunyai support sebesar 19.60%. Produk id 11, 42 dan 72 secara berturut-turut mewakili produk Queso Cabrales, Singaporean Hokkien Fried Mee and Mozzarella di Giovanni.

DAFTAR PUSTAKA

http://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Frequent_Pattern_Mining/The_Eclat_Algorithm