SPADE ( SEQUENTIAL PATTERN DISCOVERY USING EQUIVALENCE CLASSES )

Sebelum kita membahas SPADE, kita bahas terlebih dahulu data mining, karena data mining berhubungan dengan SPADE.

1.    Data Mining

Data mining  merupakan proses ekstraksi informasi atau pola dalam  database yang berukuran besar (Han &  Kamber 2006). Salah satu teknik data mining adalah sequential pattern mining yang berguna untuk menemukan pola sekuensial yang terdapat pada  database yang pertama kali diperkenalkan oleh Agrawal dan Srikant pada tahun 1995.

Program data mining melakukan analisis data dan dapat menemukan informasi penting mengenai pola data, yang dapat memberikan kontribusi besar-besaran pada strategi bisnis, knowledgebase, dan penelitian serta riset medical.

Data mining mengandung arti proses meng-extract atau menggali (mining) pengetahuan/ knowledge dari sejumlah besar data dan data mining seringkali disebut juga dengan knowledge mining from database, knowledge data extraction, data/ pattern analysis, data archeology dan data dredging. Selain itu juga data mining sering digunakan oleh banyak orang sebagai sinonm dari Knowledge Discovery in Database atau KDD

2.    SPADE (Sequential Pattern Discovery Using Equivalence Classes)

Pada  database, salah satu data yang sering dijumpai adalah data transaksi. Data transaksi merupakan data konsumen atau pelanggan pada sebuah lembaga komersil maupun non-komersil yang berisi id konsumen, waktu  transaksi, dan item transaksi. Dari data transaksi seperti halnya transaksi supermarket, dapat ditemukan pola sekuensial untuk mengetahui keterkaitan antar barang atau item. 

Salah satu algoritme yang dapat digunakan untuk mengetahui pola sekuensial dari suatu data transaksi yaitu  Sequential Pattern Discovery using Equivalence classes  (SPADE). Algoritme  SPADE  merupakan algoritme  berbasis  candidate generation and test  dan merupakan penyempurnaan dari algoritme penentuan pola sekuensial terdahulu yakni Apriori. Pada perkembangannya, algoritme SPADE masih jarang diimplementasikan sehingga diperlukan  kajian yang lebih dalam dengan harapan bahwa apabila implementasi algoritme  SPADE  berhasil, maka penerapan algoritme berbasis  patterrn growth  akan semakin menarik untuk dilakukan.

Berikut ini akan dibahas mengenai metode dan pola yang digunakan dalam SPADE (Sequential Pattern Discovery Using Equivalence Classes)

a.         Sequential Pattern Mining

Merupakan metode atau cara untuk mencari dan menemukan hubungan antar item yang ada pada suatu dataset.program sequential pattern mining bertujuan untuk menemukan informasi antar item yang slaing berhubungan kedalam benuk rule. Inputan yang digunakan merupakan sekumpulan sequence yang disebut data-sequence. Suatu sequential-pattern juga terdiri daftar dari sekumpulan item.

b.   Pola Sekuensial

Pola sekuensial adalah daftar urutan dari sekumpulan  item.  Sebuah pola sekuensial dikatakan maksimum apabila tidak mengandung pola sekuensial lainnya (Zaki 2001). Sebuah pola sekuensial dengan  k-item   disebut  k-sequence. Sebagai contoh, (A →BC) merupakan sebuah sequence dengan 3-sequence. Panjang sebuah pola sekuensial adalah jumlah item yang terdapat pada pola sekuensial tersebut yang dilambangkan dengan |s|.

Sebuah subsequence s’ dari s dilambangkan dengan s’ ⊆ s. Misalkan, sebuah pola sekuensial a = (a1,a2,...an) merupakan subsequence dari b = (b1,b2,...bm)  dengan integer i1 < i2 < ...in, 1 ≤ ik ≤ m, sehingga a1  ⊆  b1, a2  ⊆  b2, ..., an  ⊆  bm. Sebagai contoh, (A→BC) merupakan subsequence  dari (A→DE→BC) atau (D→AB→BC) tetapi bukan  subsequence  dari (ABC) atau (BC→A).

Misalkan α merupakan sebuah sequence dan D  merupakan sebuah  database. Apabila diberikan sebuah  user-specified threshold  σ yang disebut dengan  minimum support, maka sebuah  sequence  dikatakan  frequent  jika  σ  (α, D) ≥ minimum support. Misalkan D merupakan sebuah database dan Ƒ   merupakan kumpulan dari semua  frequent sequences  dalam  database D. Sebuah  frequent sequence  α  ∈  Ƒ  disebut  maximal frequent sequence  jika untuk masing-masing β ∈ Ƒ , α ≠ β, dan  α  bukan merupakan ⊆ β.   

c.       Pendekatan Hyper-lattice

Hyper-lattice  merupakan pendekatan dasar yang digunakan untuk menguraikan  mining frequent sequences  menjadi submasalah yang lebih kecil (Zaki 2001). Setiap kumpulan dari semua  sequences  disebut struktur hyper-lattice. Dalam struktur ini,  sequences menjadi berlapis yang  berarti bahwa setiap  sequences  dibentuk dengan menambah sebuah  item  baru ke sequences dari layer sebelumnya. Adapun dasar dari teori  hyper-lattice  sebagai berikut (Davey & Priestley 1990)

d.      Algoritma Spade

Algoritma SPADE (Sequential Pattern Discovery using Equivalence classes = Penemuan pola urutan / sekuensial data menggunakan kelas yang ekivalen / sama) adalah sebuah algoritma baru untuk penemuan secara cepat dari pola data yang berurutan. Solusi untuk masalah ini membuat database scan berulang, dan menggunakan suture hash kompleks yang memiliki pengalokasian yang minim. Gambar 1.1. merupakan gambaran singkat dari proses algoritma SPADE.

Gambar 1.1. Algoritma SPADE

A.  Confidence

Confidence  untuk suatu aturan asosiasi X-Y, adalah ukuran keakuratan dari aturan tersebut yang dihitung dari persentase transaksi dalam database yang mengandung X dan juga mengandung Y. Definisi formal dari confidence adalah sebagai berikut:

Apabila nilai  confidence  dari kemungkinan  aturan  lebih besar atau sama dengan  minimum  confidence yang diberikan maka aturan tersebut merupakan aturan yang sesuai dengan output  algoritme  Rule Generation. Algoritme Rule Generation  adalah sebagai berikut : 

Contoh Kasus

Pada gambar 1.2 merupakan contoh database

Dari contoh database pada gambar 1.2, dapat diperoleh data untuk frequent 1-sequences, dengan cara menghitung jumlah kemunculan per items untuk setiap SID, hasil dari proses dapat dilihat pada gambar 1.3.

Gambar 1.3. Hasil proses frequent 1-sequences

Dari gambar 1.3 dapat dicari frequent 2-sequences, dengan cara membandingkan SID dan Time ( EID ) dari setiap items untuk membentuk frequent 2-sequences. Hasil dari proses tersebut dapat dilihat pada gambar 1.4.

Gambar 1.4. Hasil proses frequent 2-sequences

Dari gambar 1.4,dapat dilanjutkan untuk mencari frequent 3-sequences dengan menggunakan hasil dari gambar 1.4

Selanjutnya untuk mencari frequent 4-sequences dengan menggunakan hasil gambar 1.4 sampai hasil tidak dapat di-generate lagi

Metode Spade :

1.      Menghitung  frequent 1-sequences and 2-sequences.

a)      Setelah mengumpulkan semua 2-sequences yang telah dihitung, kemudian user menentukan minimum supportnya. Setelah itu item yang dipilih harus memenuhi minimum supportnya atau item terpilih  lebih besar atau sama dengan  minimum supportnya

ª    untuk frequent 1-sequences item pada gambar 1.3, yang memenuhi nilai minimum support yaitu 2,

ª    untuk frequent 2-sequences pada gambar 1.4, item yang terpilih dari gambar 1.4, yang memenuhi minimum supportnya, yaitu

b) Database diubah dari vertical menjadi horizontal. Sebagai contoh, untuk setiap item I, dan dengan menggunakan field customer dan transaction, katakanlah sebagai (c,t) dimasukkan (i,t) ke dalam list customer c, seperti pada gambar 1.5

Gambar 1.5. proses transformasi database dari vertical ke horizontal

2.      Menjumlahkan frequent sequences dari class

      Gambar 1.6 menunjukkan pseudo-code untuk proses breadth-first dan depth-first search. Inputnya adalah kumpulan dari atoms dari sub-latice S, bersamaan dengan id-listnya. frequent sequences diperoleh dengan cara menggabungkan atau menyilangkan id-lists dari kumpulan atoms dan pengecekan cardinality dari hasil id-lists terhadap min_sup. Sebelum menggabungkan, proses pruning dapat dimasukkan untuk memastikan apakah h semua hasil subsequnce itu benar-benar frequent. Setelah itu, dilanjutkan kepenggabungan id-list.

Gambar 1.6. Pseudo-code untuk breadth-first dan depth-first search

3.      Penggabungan temporal id-list

   Untuk penggabungan id-lisr dengan  2-sequences berdasarkan equivalence class [ B-A] dengan atom set  {B - AB, B - AD, B-  A- A,B- A- D,B - A -  F}.  kalau P digunakan sebagai pengganti prfix B ?  A, maka classnya dapat ditulis ulang [P] D { PB,PD,P- A,P-D,P- F}. hasilnya adalah 2 jenis atoms yang berbeda : yaitu event atoms { PB, PD }, dan sequences atoms { P-  A,P-  D,P- F}. untuk penggabungannya, dihasilkan 3 kemungkinan :

                                            i.            Event atom with event atom: menggabungkan PB dengan PD, dan hasilnya adalah PBD.

                                          ii.            Event atom with sequences atom : menggabungkan PB dengan P- A, dan hasilnya adalah PB- A

                                        iii.            Sequences atom with sequences atom : menggabungkan P- A dengan P- F, maka kemungkinan akan menghasilkan : event atom P - AF, dan dua sequences atoms baru P - A-  F dan P -F-A. special case akan muncul, apabila P - A digabungkan dengan dirinya, yang menghasilkan sequences atom baru, P -  A -  A.

            Berdasarkan gambar 1.7, yang menunjukkan id-list untuk sequences atom P-A dan P - F. untuk menghitung id-list baru untuk mengahsilkan event atom P - AF, diharuskan untuk mengecek equality dari ( sid, cid) setiap pasangan Sebagai contoh, satu-satunya matching pairs adalah {(8,30),(8,50),(8,80)}. Ini di dapat dari gambar   dari penggabungan p - A - F , diperlukan pengecekan untuk temporalnya, sebagai contoh, untuk pasangan(s,t1) dalam L(p? A), kemudian diperiksa apakah ( s,t2) eksis di dalam L(P ? F), dengan t2>t1,artinya item F mengikuti item A untuk input-sequence s. dengan kata lain membentuk pattern P- A-  F, dan pasangan (s,t2) ditambahkan ke dalam pattern’s id-list. Akhirnya, id-list untuk P -  F-  A bisa didapat dengan cara yang sama dengan cara membalik peran dari P-  A dan P -  F hasil final id-lists untuk tiga sequence baru terlihat pada gambar

Gambar 1.7. Penggabungan temporal id-list

4.      Pruning sequences

Pruning algorithma ditunjukkan pada gambar  ditunjukkan sebagai item pertama dari sequences a. Sebelum generating id-list untuk k-sequences β, dilakukan pengecekan untuk semua k subsequences dari panjang k-1 adalah frequent. Kalau hasilnya adalah frequent maka selanjutnya dapat di lakukan penggabungan id-list. Perhatikan bahwa semua subsequences kecuali yang

Terakhir berada di dalam class. Sebagai contoh sequence β = ( D - BF -  A). Ketiga subsequences utama,(D -  BF).(D- B- A) ,and (D -  F -  A) semuanya terletak di dalam class [D].Subsequnce terakhir (BF -  A) dimiliki oleh class[B]. Kalau [B] sudah selesai diproses maka informasi subsequence untuk pruning telah diselesaikan . Lain halnya, kalau [B] belum diproses, maka belum dapat ditemukan apakah (BF -  A) frequent atau tidak maka.partial pruning berdasarkan members dari class yang sama masih memungkinkan. Lebih baik kalau class diproses secara lexicographic secara descending, karena dalam kasus ini,setidaknya untuk semua informasi dapat digunakan untuk pruning. Hal ini dikarenakan items dari event disimpan dan di sorting secara increasing order.Sebagai contoh , kalau ingin mengetes β= ABDF, maka diharuskan untuk mengecek di dalam class [A] kalau ADF adalah frequent, dan karena [B] akan diproses kalau classes sudah diselesaikan sacara reverse lexicographic order, BDF juga bisa dicek apakah frequent atau tidak.

5. Confidence

Confidence  untuk suatu aturan asosiasi X-Y, adalah ukuran keakuratan dari aturan tersebut yang dihitung dari persentase transaksi dalam database yang mengandung X dan juga mengandung Y. Definisi formal dari confidence adalah sebagai berikut:

Oleh :
Kelompok 4 : Riska Savitri
                       Hadijah

                       Laksmi V.C
                       Darwis

Program studi Statistika , Jurusan Matematika , Fakultas Matematika dan Ilmu Pengetahuan Alam , Universitas Hasanuddin , Makassar , 2013