algoritma eclat

SISTEM BASIS DATA

ALGORITMA ECLAT

KELOMPOK 3

SERTI LONDONGALLO (H12110002)

KRISTI W. SAIYA (H12110255)

BRYAN NAWANJAYA ARTIKA (H12110275)

ABADI GUNAWAN AZIS (H12110287)

UNIVERSITAS HASANUDDIN

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

JURUSAN MATEMATIKA

2013

Latar Belakang

• Algoritma Association Rule dengan Apriori kurang baik bilaterdapat banyak pola kombinasi data yang sering muncul (banyakfrequent pattern), banyak jenis item tetapi pemenuhan minimumsupport rendah.• Algoritma Association Rule dengan Apriori membutuhkan waktuyang cukup lama karena scanning database dapat dilakukanberulang-ulang untuk mendapatkan frequent pattern yang ideal.• FP-Tree (Frequent Pattern – Tree) merupakan suatu algoritmayang dirancang untuk mengatasi kendala bottleneck pada prosespenggalian data dengan algoritma Apriori (Zhao et al. 2003).

Ide gagasan FP-Tree

• Pemampatan data dengan model struktur data pohon untukmenghindari pengulangan scanning database.• Tanpa memerlukan candidate generation• Dilanjutkan dengan proses algoritma FP-growth yang dapatlangsung mengekstrak frequent Itemset dari FP tree yang telah

Algoritma Eclat dalam FP Tree

terbentuk dengan menggunakan prinsip divide and conquer.

Definisi Frequent Pattern – Tree (FP – Tree)

• Terdiri atas sebuah root dengan label ‘null’, sekumpulan subtreeyang menjadi child dari root dan sebuah tabel frequent header.• Setiap node dalam FP-Tree mengandung tiga informasi penting.yaitu label item, menginformasikan jenis item yangdirepresentasikan node tersebut, support count, merepresentasikanjumlah lintasan transaksi yang melalui node tesebut, dan pointerpenghubung yang menghubungkan node-node dengan label itemsama antar-lintasan, ditandai dengan garis panah putus-putus.• Isi dari setiap baris dalam tabel frequent header terdiri atas labelitem dan head of nodelink yang menunjuk ke node pertama dalamFP-Tree yang menyimpan label item tersebut.

Proses untuk mendapatkan Frequent Itemsetdilakukan dalam 2 tahap

• Pembentukan Frequent Pattern – Tree (FP-Tree)• Ekstrak Frequent Itemset hasil dari FP-Tree denganmenggunakan algoritma FP-Growth

Algoritma FP Growthdibagi dalam 3 tugas utama

1. Tahap Pembangkitan Conditional Pattern Base

Conditional Pattern Base merupakan subdatabase yang berisi prefix path (lintasan prefix) dan suffix pattern (pola akhiran). Pembangkitan

conditional pattern base didapatkan melalui FP-tree yang telah dibangun sebelumnya.

2. Tahap Pembangkitan Conditional FP-tree

Pada tahap ini, support count dari setiap item pada setiap conditional pattern base dijumlahkan, lalu setiap item yang memiliki jumlah support count lebih besar sama dengan minimum support count akan dibangkitkan dengan conditional FP-tree.

3. Tahap Pencarian frequent itemset

Apabila Conditional FP-tree merupakan lintasan tunggal (single path), maka didapatkan frequent itemset dengan melakukan kombinasi item untuk setiap conditional FP-tree. Jika bukan lintasan tunggal, maka dilakukan pembangkitan FP-growth secara rekursif.

CONTOH

MENENTUKAN 1 ITEMSET YANG SERING DIKUNJUNGI

TID Items1 {A,B}2 {B,C,D}3 {A,C,D,E}4 {A,D,E}5 {A,B,C}6 {A,B,C,D}7 {B,C}8 {A,B,C}9 {A,B,D}10 {B,C,E}

FP-Tree Bersyarat pada E

FP-Tree bersyarat pada F

0

10

20

30

40

50

60

70

80

90

100

0 0.5 1 1.5 2 2.5 3

Support threshold(%)

Ru

n t

ime(s

ec.)

D1 FP-grow th runtime

D1 Apriori runtime

DAFTAR PUSTAKA

Christian BorgeltDepartment of Knowledge Processing and Language EngineeringSchool of Computer Science, Otto-von-Guericke-University of Magdeburg

Universit¨atsplatz 2, 39106 Magdeburg, Germany

Erwin*, Analisis Market Basket Dengan Algoritma

Apriori dan FP-Growth

Jurusan Teknik Informatika, Fakultas Ilmu Komputer, Universitas Sriwijaya

http:\\www.wikibooks.com\The Eclat Algorithm