9

BAB 2

DASAR TEORI

Bab ini berisi konsep yang berhubungan dengan Bayesian network (BN), node

ordering, dan sequential pattern (SP). Penjelasan dimulai dari pendahuluan, konsep

dan teori dasar BN, pendekatan untuk mengkonstruksi struktur BN dari data dengan

metode analisis dependensi. Kemudian diuraikan mengenai konsep dan teori dasar

node ordering yang merupakan kajian utama penelitian. Pada bagian akhir dijelaskan

mengenai konsep dan teori dasar sequential pattern (SP).

2.1. Bayesian Network Pada bagian ini dijelaskan konsep yang berhubungan dengan Bayesian network (BN),

meliputi pendefinisian dan konsep BN, kebebasan kondisional atau conditional

independency test (CI test) serta konsep d-seperation. Dijelaskan juga mengenai

algoritma Three Phase Dependency Analysis Phi (TPDA ∏) yaitu algoritma

pengkonstruksi struktur BN yang menggunakan pendekatan analisis dependensi.

2.1.1. Konsep Dasar Bayesian belief network dikenal juga dengan sebutan belief network atau probalibistic

network, atau Bayesian network. Dalam penulisan ini untuk selajutnya akan

digunakan penamaan Bayesian network yang disingkat dengan BN. Bayesian network

merupakan probabilistic graphical model (PGM) dengan busur berarah yang

digunakan untuk merepresentasikan pengetahuan tentang hubungan kebergantungan

(dependency) atau kebebasan (independency) di antara variabel-variabel dari domain

persoalan yang dimodelkan [HAN06]. BN terdiri dari dua bagian utama, yaitu bagian

struktur graf dan himpunan parameter. Kedua bagian BN tersebut dijelaskan sebagai

berikut:

1. Struktur graf

Struktur graf BN disebut dengan directed acyclic graph (DAG) yaitu graf berarah

tanpa siklus [NEA04]. DAG terdiri dari simpul dan busur. Simpul

merepresentasikan variabel acak, dan busur merepresentasikan adanya hubungan

kebergantungan langsung (dapat pula diinterpretasikan sebagai pengaruh (sebab

akibat) langsung, di antara variabel yang dihubungkannya. Tidak adanya busur

10

menandakan adanya kebebasan kondisional di antara variabel. Penjelasan yang

lebih lengkap mengenai simpul dan busur akan diberikan Bab selanjutnya.

Struktur BN disebut juga sebagai representasi kualitatif yang menyatakan

keterhubungan di antara variabel-variabel yang dimodelkan.

2. Himpunan parameter.

Himpunan parameter mendefinisikan distribusi probabilitas kondisional untuk

setiap variabel. Setiap variabel acak direpresentasikan oleh sebuah simpul. Pada

setiap simpul terdapat tabel yang berisikan distribusi probabilitas kondisional

yang disebut dengan conditional probability table (CPT). Pada setiap sel dari

tabel tersebut berisikan probabilitas kondisional dari nilai-nilai simpul yang

diwakilinya jika diketahui setiap kombinasi nilai semua simpul parent kecuali

pada akar (root). Himpunan parameter disebut juga sebagai representasi

kuantitatif yang menyatakan nilai probabilistik pada variabel-variabel yang

dimodelkan.

BN merepresentasikan hubungan kebebasan kondisional dan kebergantungan antara

satu variabel dengan variabel lain, sehingga dengan memanfaatkan BN, proses

komputasi akan menjadi lebih sederhana dan lebih akurat. [HAN06]. Berikut

diberikan sebuah contoh tentang kondisi medis yang meliputi penyebab, gejala, dan

hasil uji penyakit [NEA04]: sebuah BN dengan simpul H merepresentasikan pernah

atau tidaknya seseorang merokok, simpul B merepresentasikan penyakit bronkhitis,

simpul L merepresentasikan penyakit paru-paru, simpul F merepresentasikan

keletihan, simpul X merepresentasikan hasil uji sinar-X pendeteksi penyakit paru-

paru, dan simpul C merepresentasikan penyakit kanker. BN tersebut ditunjukkan pada

gambar II.1 yang merepresentasikan seseorang yang memiliki riwayat merokok

memiliki pengaruh langsung pada penyakit bronchitis atau kanker paru-paru,

bronkhitis atau kanker paru-paru berpengaruh langsung pada keletihan, dan kanker

paru-paru berpengaruh langsung pada hasil uji sinar-X terhadap penyakit paru-paru.

11

Gambar II.1. Bayesian network [NEA04]

Representasi nilai dari masing-masing simpul pada BN tersebut diberikan pada

gambar berikut.

Node Nilai Keterangan

h1 Ada riwayat merokok (H=history) H h2 Tidak ada riwayat merokok b1 Bronkhitis ada (B=Bronkhitis) B b2 Bronkhitis tidak ada l1 Kanker paru-paru ada (L=lung) L l2 Kanker paru-paru tidak ada f1 Kelelahan ada (F=Fatique) F f2 Kelelahan tidak ada c1 Hasil uji sinar-X terhadap kanker paru-paru positif (C=Cancer) C c2 Hasil uji sinar-X terhadap kanker paru-paru negatif

Gambar II.2. Representasi nilai dari simpul-simpul pada BN pada gambar II.1

Struktur graf pada BN merepresentasikan dua hal yaitu: pengaruh langsung dan tidak

langsung, dan inferensi probabilistik [NEA04]. Adanya representasi hubungan

langsung dan tidak langsung dapat dilihat pada gambar II.1 tersebut yaitu: busur dari

H ke L adalah representasi dari pengaruh langsung akan adanya riwayat merokok

terhadap adanya kanker paru-paru. Tidak adanya busur dari H ke C adalah

representasi dari riwayat merokok tidak mempunyai pengaruh langsung pada pada

hasil uji sinar-X, namun pengaruhnya adalah akibat dari keberadaan kanker paru-paru.

12

Dalam hal representasi inferensi probabilistik yang terdapat pada BN adalah dengan

memanfaatkan pengetahuan tentang keterhubungan di antara variabel yang ada pada

BN, untuk melakukan pengambilan keputusan (inferensi) probabilistik. Inferensi

probabilistik adalah memprediksi nilai variabel yang tidak dapat diketahui secara

langsung dengan menggunakan nilai-nilai variabel lain yang telah diketahui [NEA04].

Inferensi probabilistik pada contoh di atas misalnya menentukan probabilitas

kondisional pasien mengidap bronkhitis jika diketahui pasien tersebut merokok dan

hasi uji sinar-X untuk kanker paru-paru adalah positif [NEA04].

Untuk melakukan inferensi probabilistik maka terlebih dahulu harus diperoleh

diperoleh joint probability distribution (JPD) dari semua variabel yang dimodelkan

[NEA04]. JPD adalah probabilitas semua kejadian variabel yang terjadi secara

bersamaan. Misalnya dengan diketahuinya JPD dari semua variabel pada contoh

tersebut atau P(f,c,b,l,h) dapat dihitung probabilitas kondisional seseorang mengidap

bronkhitis jika memiliki sejarah merokok, mengalami kelelahan, dan hasil uji sinar-X

untuk kanker paru-paru adalah positif, yaitu:

∑∑

==

lb

l

lcfhbP

lcfhbP

cfhPcfhbPcfhbP

,),1,1,1,(

),1,1,1,1(

)1,1,1()1,1,1,1()1,1,1|1( .....................................(II.1)

Yang dalam hal ini, ∑lb,

berarti penjumlahan b dan l untuk semua kemungkinan nilai-

nilainya.

Tanpa menggunakan BN, maka pada contoh tersebut JPD ditentukan langsung

sebagai berikut:

P(f,c,b,l,h) = P(f|c,b,l,h) P(c|b,l,h) P(b|l,h) P(l|h) P(h)...........................................(II.2)

Untuk variable biner (variabel yang bernilai true atau false), JPD tersebut keseluruhan

membutuhkan sebanyak 62 parameter, yaitu dengan perincian 32 (hasil perhitungan

25) parameter untuk menghitung P(f|c,b,l,h), 16 (hasil perhitungan 24) parameter

untuk menghitung P(c|b,l,h), 8 (hasil perhitungan 23) parameter untuk menghitung

13

P(b,l,h), 4 (hasil perhitungan 22) parameter untuk menghitung P(l|h), dan 2 (hasil

perhitungan 21) parameter untuk menghitung P(h).

Jika stuktur BN yang ada pada gambar II.1 digunakan bersama dengan rumus II.2,

maka JPD dapat dinyatakan sebagai P(f,c,b,l,h) = P(f|b,l) P(c|l) P(b|h) P(l|h) P(h)

yang secara keseluruhan membutuhkan 22 parameter, yaitu dengan perincian 8 (hasil

perhitungan 23) parameter untuk menghitung P(f|b,l), 4 (hasil perhitungan 22)

parameter untuk menghitung P(c|l), 4 (hasil perhitungan 22) parameter P(b|h), 4 (hasil

perhitungan 22) parameter untuk menghitung P(l|h), dan 2 (hasil perhitungan 22)

parameter untuk menghitung P(h). Proses penghitungan menjadi lebih sederhana,

karena struktur BN yang sudah terbentuk dapat dimanfaatkan untuk menentukan

simpul parent dari simpul yang sedang diperiksa. Sebagai contohnya, simpul C

memiliki satu simpul parent yaitu L sehingga cukup dihitung nilai dari P(c|l) saja.

Melalui contoh tersebut, peran dari BN terlihat jelas dalam mereduksi jumlah

parameter yang semula sebanyak 62 parameter menjadi hanya 22 parameter. JPD dari

N variabel biner (variabel yang memiliki dua nilai) membutuhkan O(2N) parameter.

Sedangkan dengan menggunakan BN, JPD dan N variabel biner dengan k maksimum

parent dari simpul pada struktur BN hanya membutuhkan O(2kn) parameter [NEA04].

Konstruksi BN dari data dibagi dalam dua tahap, yaitu:

1. Konstruksi struktur atau disebut juga dengan tahap kualitatif, yaitu mencari

keterhubungan di antara variabel-variabel yang dimodelkan.

2. Estimasi parameter atau tahap kualitatif, yaitu menghitung nilai-nilai probabilistik

pada CPT.

Melakukan konstruksi struktur lebih sulit dibandingkan dengan melakukan estimasi

parameter [CHE01[a]]. Kesulitan bertambah jika datanya tidak lengkap, atau dengan

istilah lain ada simpul yang tidak terobservasi (hidden node), atau ada data yang nilai

variabelnya yang tidak diketahui (missing value) [CHE01[a]].

Ada dua pendekatan yang digunakan untuk mengkonstruksi struktur BN [CHE01[a]]

yaitu metode search and scoring dan metode dependency analysis. Masing-masing

metoda ini memandang BN dari sudut yang berbeda. Pada metoda search and

14

scoring, BN dipandang sebagai sebuah struktur yang merepresentasikan JPD dari

variabel-variabel, sedangkan pada metoda dependency analysis, BN dipandang

sebagai sebuah struktur yang merepresentasikan sekumpulan kebebasan kondisional

di antara simpul-simpul.

Berikut ini diberikan penjelasan lebih rinci mengenai kedua pendekatan tersebut:

1. Metode search and scoring.

Pada pendekatan ini algoritmanya memandang masalah konstruksi struktur

sebagai pencarian sebuah struktur yang paling cocok dengan data. Proses

konstruksi dimulai dari sebuah graf tanpa busur, dan kemudian menggunakan

metode pencarian atau searching untuk menambahkan sebuah busur pada graf.

Setelah itu digunakan medote scoring untuk melihat apakah struktur baru lebih

baik daripada struktur sebelumnya. Jika lebih baik, maka busur tetap

ditambahkan, dan berusaha menambahkan sebuah busur yang lain. Proses ini

berlanjut sampai tidak ada struktur baru yang lebih baik daripada struktur

sebelumnya. Algoritma dengan pendekatan ini antara lain algoritma K2 dari

Cooper dan Herkovits, algoritma HCG dari Heckerman [CHE98].

2. Metode dependency analysis.

Pada pendekatan ini, struktur BN dikonstruksi dengan mengidentifikasi hubungan

kebebasan kondisional di antara simpul-simpul. Menggunakan beberapa pengujian

statistik misalnya chi-squared atau mutual information, dapat ditemukan

hubungan kebebasan kondisional di antara simpul-simpul, dan selanjutnya

hubungan tersebut digunakan sebagai batasan untuk mengkonstruksi struktur BN.

Algoritma dengan pendekatan ini misalnya algoritma PC dari Peter Spirtes dan

Clark Glymour, Algoritma TPDA dan TPDA ∏ dari Jie Cheng [CHE98].

Secara umum pendekatan dengan dependency analysis lebih efisien daripada

pendekatan search and scoring untuk network yang memiliki sedikit keterhubungan

di antara simpul-simpulnya. Pendekatan dependency analysis juga dapat

menghasilkan struktur yang tepat jika distribusi probabilitas dari data memenuhi

asumsi berlaku untuk sebuah representasi DAG faithful. Namun algoritma dengan

pendekatan ini membutuhkan jumlah pengujian kebebasan kondisional (conditional

independency test atau CI test) yang eksponensial dan membutuhkan orde tinggi (CI

15

test dengan himpunan kondisi besar). Sebagaimana dijelaskan dalam [CHE98], CI test

dengan himpunan kondisi besar akan reliable jika volume data relatif besar. Pada sisi

lain, meskipun pendekatan search and scoring mungkin tidak menemukan struktur

terbaik karena sifat heuristiknya, pendekatan ini bekerja dengan cakupan model

probabilistik yang lebih luas daripada pendekatan dependency analysis [CHE98].

Sebagai catatan, pada bagian ini tidak dijelaskan secara rinci seluruh konsep dasar

yang berhubungan dengan learning BN seperti graf berarah, chain, path, DAG,

collider dan non-collider, kondisi Markov, dan faithfulness. Penjelasan yang detil

selengkapnya diberikan pada Lampiran A.

2.1.2. Conditional Independency Test (CI Test) Algoritma konstruksi struktur BN dengan pendekatan dependency analysis, adalah

jenis algoritma yang menggunakan CI test untuk menentukan apakah ada kebebasan

kondisional di antara dua variabel acak diskret (variabel yang nilainya terbatas). Salah

satu jenis CI test yang bisa digunakan untuk menghitung kebebasan kondisional pada

variabel acak diskret adalah conditional mutual information test [CHE01].

Untuk mengukur aliran informasi, digunakan teknik pengukuran dengan mutual

information dan conditional mutual information. Pada teori informasi, mutual

information antara simpul A dan B digunakan untuk merepresentasikan informasi

harapan yang diperoleh tentang simpul B, setelah terlebih dahulu diketahui nilai

variabel simpul A. Pada struktur BN, jika ada dua simpul yang saling bergantung, dan

jika nilai dari salah satu simpul telah diketahui maka dapat diketahui nilai dari simpul

lainnya yang saling bergantung. Informasi tersebut bisa diperoleh dengan

menggunakan pengukuran mutual information. Jadi, dengan menggunakan mutual

information di antara dua simpul akan dapat diketahui apakah dua simpul adalah

saling bergantung atau tidak, dan bagaimana kedekatan hubungan simpul-simpul

tersebut [CHE01[a]].

16

Mutual information antara dua simpul A dan B didefinisikan sebagai berikut

[CHE97]:

∑=ji xx ji

jijiji xPxP

xxPxxPXXI

, )()(),(

log),(),( ...................................................(II.3)

dan conditional mutual information didefinisikan sebagai berikut [CHE97]:

∑=cxx ji

jijiji

jicxPcxP

cxxPcxxPcXXI

,, )|()|()|,(

log),,()|,( .................................(II.4)

yang dalam hal ini C adalah himpunan simpul yang telah diketahui nilainya.

Pada saat I(Xi,Xj) memiliki nilai lebih kecil dari sebuah threshold (ambang batas)

tertentu yang dinotasikan dengan ε, maka dapat dikatakan bahwa Xi dan Xj adalah

marginally independent. Pada saat I(Xi,Xj)|C) memiliki nilai lebih kecil dari ε, maka

dapat dikatakan bahwa Xi dan Xj adalah conditionally independent [CHE97].

Pada saat konstruksi struktur BN, algoritma yang digunakan akan mengambil data

yang tersimpan pada tabel di dalam basis data sebagai masukan. Setiap atribut (field)

dari tabel dianggap sebagai variabel, yang masing-masing direpresentasikan dengan

sebuah simpul pada BN. Setiap record pada tabel merupakan instansiasi lengkap dari

variabel yang ada pada domain masalah.

Asumsi yang digunakan pada algoritma yang akan dipakai adalah [CHE97]:

1. Untuk seluruh record, atribut yang ada pada tabel berisikan nilai-nilai yang diskrit

dan tidak ada missing value (data kosong).

2. Seluruh record terjadi secara bebas.

3. Volume data relatif cukup besar untuk melakukan CI test yang representatif.

Asumsi pertama menyatakan bahwa pada sebuah model probabilistik seluruh variabel

acak adalah diskrit dan lengkap. Asumsi kedua menyatakan bahwa semua record

diambil bersifat bebas satu dengan lainnya. Asumsi ketiga untuk menjamin bahwa

keputusan statistik yang dibuat oleh algoritma yang menggunakannya adalah benar.

17

2.1.3. Directional Separation (d-separation) Pada bagian ini dijelaskan konsep d-separation. Konsep d-separation digunakan

untuk mengidentifikasi kebebasan kondisional yang ada pada DAG. Seluruh

penjelasan yang diberikan berikut mengacu kepada [NEA04].

Semua kebebasan kondisional yang diperoleh dari kondisi Markov dapat

diidentifikasi pada DAG dengan konsep d-separation. Sebelum diberikan definisi d-

separation, telah dahulu diberikan definisi berikut:

Definisi II.1. Misalkan G(V,E) adalah sebuah DAG, A ⊆ V, X dan Y adalah simpul berbeda dalam V‐A, dan p adalah sebuah chain antara X dan Y. Maka p diblok oleh A  jika dipenuhi salah satu kondisi berikut [NEA04]: (i) Ada sebuah simpul Z ∈ A pada chain p, dan Z adalah simpul head‐to‐tail pada chain p 

(A C B). (ii) Ada  sebuah  simpul  Z ∈ A pada  chain p, dan  Z  adalah  simpul  tail‐to‐tail pada  chain p 

(A C B). (iii) Ada  sebuah  simpul  Z ∈ A pada  chain p,  yang dalam hal  ini  semua descendant dari  Z 

bukan anggota A, dan Z adalah simpul head‐to‐head (collider/v‐structure) pada chain p (A C B). 

Jika diketahui simpul A, dan mengakibatkan chain tersebut tidak diblok oleh A,

maka chain akan disebut aktif. Pada saat chain aktif, maka lintasan yang terbentuk

disebut dengan lintasan terbuka (open path).

Berikut diberikan definisi d-separation.

Definisi II.2. Untuk sebuah DAG G=(V,E), A ⊆ V, X dan Y adalah simpul berbeda dalam V‐A. X dan Y dikatakan d‐separated oleh A dalam G jika setiap chain antara X dan Y diblok oleh A. 

Sebagai contoh diberikan gambar berikut:

Gambar II.3. DAG yang digunakan untuk mengilustrasikan d-separation

18

Dari DAG pada gambar tersebut dapat dikatakan bahwa:

• A dan E d-separated oleh {B}, karena chain A-B-C-E terblok pada B dan chain

A-B-D-E terblok pada B

• B dan E d-separated oleh {C,D} karena chain B-C-E terblok pada C dan chain B-

D-E terblok pada D

• C dan D d-separated oleh {B} karena chain C-B-D terblok pada B dan chain C-E-

D terblok tanpa simpul apapun

Selanjutnya diberikan definisi.

Definisi II.3. Misalkan G=(V,E) adalah sebuah DAG, dan A, B, dan C merupakan himpunan bagian dari V yang salin disjoin. A dan B dikatakan d‐separated oleh C dalam G,  jika untuk setiap X ∈ A dan Y ∈ B, X dan Y d‐separated oleh C. Hal ini dinotasikan dengan IG(A,B|C). Jika C = ∅ maka IG(A,B) [NEA04] 

Jadi misalkan P adalah JPD dari variabel-variabel di V dan G=(V,E) adalah sebuah

DAG maka (G,P) memenuhi kondisi Markov jika dan hanya jika semua kebebasan

kondisional yang ada pada G benar pada P, yaitu:

IG(A,B|C) ⇒ IG(A,B|C)

Ada sebuah teorema yang penting pada d-separation yaitu:

Teorema II.1. Berdasarkan  kondisi Markov,  sebuah DAG G membawa  semua  dan  hanya kebebasan kondisional yang teridentifikasi oleh d‐separation pada G. 

Distribusi probabilitas tertentu P yang memenuhi kondisi Markov dengan G, bisa saja

mempunyai kebebasan kondisional yang tidak teridentifikasi oleh d-separation.

Beberapa DAG dapat saling ekuivalen, artinya memiliki d-separation yang sama.

Berikut ini diberikan definisi ekuivalensi.

Definisi II.4. Misalkan  G1=(V,E1)  dan  G2=(V,E2)  merupakan  dua  DAG  mengandung himpunan  simpul  V  yang  sama. Maka  G1  dan  G2  disebut  ekuivalensi Markov  jika  untuk setiap tiga himpunan bagian disjoin A, B, C  V, A dan B d‐separated oleh C pada G1 jika dan hanya jika A dan B d‐separated oleh C pada G2, yaitu:  

IG(A,B|C) IG2(A,B|C) 

19

Meskipun definisi tersebut hanya berhubungan dengan properti graf, aplikasi adalah

dalam probabilitas, berdasarkan teorema berikut:

Teorema II.2. Dua  DAG merupakan  ekuivalen Markov  jika  dan  hanya  jika,  berdasarkan kondisi Markov, keduanya mempunyai kebebasan kondisional yang sama [NEA04]. 

Contoh DAG yang saling ekuivalen Markov yaitu pada gambar berikut:

Gambar II.4. DAG-DAG ini merupakan ekuivalen Markov,

Untuk mengidentifikasi ekuivalensi Markov, digunakan teorema berikut:

Teorema II.3. Dua  DAG  merupakan  ekuivalen  Markov  jika  dan  hanya  jika  kedua  DAG tersebut  mempunyai  link  (busur  tanpa  memperhatikan  arah)  yang  sama  dan  himpunan uncoupled head‐to‐head meeting yang sama [PEA89]. 

Teorema tersebut memberikan cara sederhana untuk merepresentasikan kelas

ekuivalen Markov dalam sebuah graf. Graf ini disebut DAG pattern. DAG pattern

dari DAG DAG pada gambar 5 tersebut adalah seperti pada gambar berikut.

H

B L

F C Gambar II.5. DAG pattern yang merepresentasikan kelas ekuivalen Markov

pada gambar II.3 [NEA04]

Dengan menggunakan Markov condition, dapat ditentukan himpunan simpul yang

bebas kondisional jika telah diketahui simpul lainnya pada struktur Bayesian network.

Dengan menggunakan kosep direction dependent separation atau d-separation

[Pearl, 1988] maka hubungan kebebasan kondisional (conditional independency) yang

valid dapat diperoleh secara langsung dari topologi Bayesian network.

20

Dengan demikian konsep d-separation dapat menyatakan seluruh hubungan

kebebasan kondisional yang ada pada Bayesian network [Geiger and Pearl, 1988].

2.2. Three Phases Dependency Analysis Phi (TPDA -∏) Seperti telah dijelaskan pada sub bab sebelumnya bahwa ada dua pendekatan yang

digunakan untuk mengkonstruksi struktur BN, yaitu pendekatan search and scoring

dan pendekatan analysis dependency. Pada pendekatan analysis dependency

dilakukan sejumlah pengujian terhadap kebebasan kondisional yang disebut dengan

CI test. Pengujian dilakukan untuk memeriksa besar aliran informasi yang ada pada

seluruh pasangan simpul yang ada.

Salah satu algoritma dengan pendekatan dependency analysis adalah algoritma Three

Phase Dependency Analysis Phi (TPDA ∏) yang dikembangkan oleh Jie Cheng

[CHE97]. Pada bagian berikut ini akan dijelaskan mengenai algoritma TPDA ∏, tiga

fase pembentukan struktur BN, dan CI test pada setiap fase tersebut. Seluruh

penjelasan yang diberikan mengacu pada [CHE98] dan [CHE01[a]].

2.2.1. Algoritma TPDA ∏ Algoritma TPDA ∏ menerima dua masukan yaitu tabel dari basis data sebagai

sumber data dan informasi node ordering yang lengkap, dan selanjutnya

mengkonstruksi struktur BN sebagai keluarannya. Untuk mengkonstruksi struktur

BN, langkah kerja algoritma TPDA ∏ dibagi menjadi 3 fase. Ketiga fase tersebut

dijelaskan berikut ini.

Ketiga fase pada algoritma TPDA ∏ adalah: fase 1 membuat bagan, fase 2

pemeriksaan busur yang tidak ada, dan fase 3 membuang busur yang tidak perlu. Pada

fase pertama, algoritma akan menghitung mutual information dari masing-masing

pasangan simpul. Nilai mutual information tersebut menyatakan ukuran kedekatan

antar simpul. Dengan memanfaatkan nilai mutual information dan melakukan

pemeriksaan lintasan terbuka, maka kemudian dibuat sebuah bagan dari struktur BN.

Pada fase kedua, algoritma akan melakukan sejumlah pengujian kebebasan

kondisional (CI test), dan menambahkan sebuah busur jika hasil CI test menunjukkan

bahwa pasangan simpul yang diperiksa ternyata tidak bebas kondisional terhadap

21

condition-set tertentu. Hasil dari fase kedua adalah sebuah I-map yang

merepresentasikan sebuah model kebergantungan pokok jika model tersebut adalah

DAG faithful. Pada fase ketiga, masing-masing busur dari I-map diperiksa dengan

menggunakan CI test, dan busur akan dibuang jika kedua simpul tersebut adalah

bebas kondisional. Hasil dari fase ketiga adalah sebuah P-map dari model pokok, jika

model tersebut adalah DAG-faithful.

Berikut ini akan diberikan sebuah ilustrasi yang menggambarkan cara kerja algoritma

yang ada pada tiga fase tersebut. Langkah-langkah detil dan lengkap pada masing-

masing fase tersebut tidak dijelaskan pada bagian ini, namun dijelaskan pada lampiran

B. Diberikan sebuah contoh sederhana sebuah jaringan multi-connected [CHE01[a]].

Sebagai asumsi diberikan sebuah basis data dengan 5 variabel yaitu A, B, C, D, dan E

maka algoritma TPDA ∏ akan menghasilkan struktur BN seperti pada gambar II.6.a.

Proses pembentukan struktur tersebut sesuai dengan fasenya adalah mulai dari gambar

II.6.b, kemudian gambar II.6.c, dan terakhir adalah gambar II.6.d yang merupakan

sebuah struktur akhir BN yang berhasil dikonstruksi.

(d)(c)

(b)(a)

C

B E

D

A

C

B E

D

A

C

B E

D

A

C

B E

D

A

Gambar II.6. Hasil fase 1, 2, 3 dari algoritma TPDA ∏:

(a) Graf sesungguhnya (b) Hasil fase 1

(c) Hasil fase 2 (d) Hasil fase 3

Berikut ini akan dijelaskan ketiga fase berikut, dengan contoh mengacu kepada

gambar II.6.

22

Fase 1: Membuat Bagan.

Pada fase membuat bagan, dilakukan pengukuran mutual information terhadap

seluruh kombinasi pasangan yang mungkin terbentuk dari simpul yang ada.

Kemudian seluruh pasangan simpul yang memiliki nilai mutual information lebih

besar dari ε diurutkan mulai dari pasangan yang memiliki nilai mutual information

terbesar menuju yang terkecil. Asumsikan seluruh pasangan memiliki nilai mutual

information lebih besar dari ε dan setelah diurutkan adalah I(B,D) ≥ I(C,E) ≥ I(B,E) ≥

I(A,B) ≥ I(B,C) ≥ I(C,D) ≥ I(D,E) ≥ I(A,D) ≥ I(A,E) ≥ I(A,C). Pada kondisi nyata

banyaknya pasangan simpul dapat berjumlah lebih sedikit dibandingkan dengan

jumlah seluruh kombinasi pasangan simpul yang dapat dibentuk tanpa

memperdulikan nilai mutual information. Hal ini dapat terjadi karena ada beberapa

pasang simpul yang kemungkinan memiliki nilai mutual information lebih kecil dari ε

yang ditentukan [CHE97].

Selanjutnya pasangan simpul diambil satu demi satu dengan prioritas pada pasangan

yang memiliki nilai mutual information terbesar, dan diperiksa apakah ada atau tidak

lintasan terbuka diantara pasangan simpul tersebut. Jika tidak ada lintasan terbuka

antara pasangan simpul tersebut, maka sebuah busur dibuat untuk menghubungan

pasangan simpul tersebut. Proses tersebut terus dilakukan hingga seluruh pasangan

simpul telah diperiksa. Pada akhir fase ini, akan terbentuk sebuah bagan graf seperti

pada gambar II.6.b dengan hasil yang cukup dekat dengan struktur BN yang

sesungguhnya pada gambar II.6.a. Bila dibandingkan dengan struktur BN

sesungguhnya yang ada pada gambar II.6.a maka ada dua hal yang bisa disimpulkan

sebagai hasil dari fase ini.

Pertama adalah bahwa pada akhir fase 1 tersebut kemungkinan terbentuk busur yang

berlebih atau ada busur yang hilang. Sebagai contoh, pada struktur bagan yang ada

pada graf gambar II.6.b tersebut terlihat bahwa busur (B,E) adalah busur yang

berlebih (wrongly added) dan busur (D,E) adalah busur yang hilang (missing). Kedua

adalah bahwa kemungkinan masih terdapat beberapa pasangan simpul yang memiliki

mutual information lebih besar dari ε namun tidak terhubung langsung, yang dalam

contoh tersebut yaitu {C,D},{D,E},{A,D},{A,E},{A,C}. Selanjutnya bagan yang

dihasilkan pada fase 1 tersebut menjadi basis untuk melakukan fase 2.

23

Fase 2: Memeriksa Busur Yang Hilang

Pada fase 1, masih ada beberapa pasang simpul yang tidak dihubungkan pada struktur

bagan hanya karena sudah terdapat lintasan terbuka di antara pasangan simpul

tersebut. Pada fase 2, digunakan CI test dan d-separation untuk memeriksa apakah

pasangan simpul tersebut seharusnya terhubung atau tidak. Karena hanya ada satu CI

test yang digunakan untuk memeriksa keterhubungan tersebut (arah sudah diketahui

dari informasi node ordering), sehingga cut set yang tepat dapat ditentukan maka

tidak bisa dipastikan apakah keterhubungan tersebut adalah benar-benar perlu, tetapi

bisa dipastikan bahwa tidak akan ada lagi busur yang hilan (missing) pada akhir fase 2

tersebut.

Pada contoh, graf setelah fase 2 ditunjukkan pada gambar II.b.c. Busur (D,E)

ditambahkan sebab D dan E tidak bebas kondisional pada {B}, yang merupakan cut-

set terkecil antara simpul D dan E pada graf terkini. (Cut-set dari suatu graf terhubung

G, adalah himpunan busur yang bila dibuang dari graf G, maka akan mengakibatkan

graf G tidak terhubung). Busur (A,C) tidak ditambahkan karena hasil CI test

mengindikasikan bahwa A dan C adalah bebas jika diketahui cut-set {B}. Busur

(A,D), (C,D), dan (A,E) tidak ditambahkan karena alasan yang sama. Pada gambar (c)

terlihat bahwa graf yang dihasilkan setelah fase 2 berisikan semua busur dari model

yang sesungguhnya, yaitu merupakan sebuah I-map dari model yang sesungguhnya.

Fase 3: Membuang Busur Yang Tidak Perlu.

Seperti telah dijelaskan bahwa pada fase 1 dan fase 2 ada kemungkinan ditemukan

busur yang tidak perlu, maka pada fase 3 ini yang dilakukan adalah membuang

seluruh busur yang tidak perlu tersebut. Sama seperti fase 2, hanya ada satu CI test

yang dilakukan untuk memastikannya, namun pada fase ini keputusan yang telah

dilakukan adalah benar. Alasannya adalah bahwa graf terkini adalah sebuah I-map

dari model yang sesungguhnya, yang tidak ditemukan hingga pada akhir fase 2. Pada

fase 3 busur yang tidak perlu berhasil dibuang, sehingga pada akhir fase ini graf yang

dihasilkan adalah graf yang sesungguhnya [CHE97].

Graf yang dihasilkan pada akhir fase 3 ditunjukkan pada gambar II.6.d, yang

merupakan struktur sesungguhnya dari graf. Busur (B,E) dibuang karena B dan E

24

adalah bebas kondisional jika diketahui {C,D}. Pada akhir fase ini, struktur BN yang

benar berhasil dikonstruksi ditunjukkan oleh gambar II.6.d.

2.3. Node Ordering, Kausalitas, dan Informasi Temporal Pada bagian berikut diberikan penjelasan mengenai node ordering dan hubungannya

dalam kausalitas. Kemudian diberikan juga penjelasan tentang informasi temporal

(keterurutan berdasarkan waktu) dan hubungannya dengan kausalitas. Penjelasan

yang diberikan mengacu kepada [CHE01[a]] dan [PEA01].

Definisi II.5. Pola  kebergantungan  yang  ditemukan  secara  statistik  yang  menyatakan suatu kausalitas harus memiliki arah kausalitas. Sebagai contohnya, diketahui tiga variabel: A, B, dan C, dengan kondisi A dan B saling bergantung, B dan C saling bergantung, dan A dan C  saling bebas. Maka arah kausalitas yang dapat dibentuk hanyalah A B C, yaitu  sesuai dengan konsep d‐separation (definisi II.2) hanya dapat dibentuk oleh head‐to‐head meeting (v‐structure) [PEA01]. 

Lebih lanjut lagi hubungan yang erat antara pola asosiasi tersebut dengan informasi

temporal diberikan pada definisi II.12. Namun sebelumnya, terlebih dahulu akan

diberikan beberapa definisi lain. Definisi berikut adalah menjelaskan hubungan antara

urutan variabel, node ordering, DAG, dan BN.

Definisi II.6. Model  DAG  dengan  urutan  variabel  yang  sering  digunakan  adalah  untuk menyatakan sesuatu yang berhubungan dengan aliran waktu atau temporal dan kausalitas. Dalam  kausalitas,  stuktur  causal Bayesian network dibangun dari model DAG. Model DAG yang  dikonstruksi  dengan  informasi  node  ordering menyatakan  bukan  hanya  kebebasan (independency) saja, tetapi juga kebebasan bersyarat (conditional independencies). [PEA01]. 

Berikut ini diberikan definisi mengenai node ordering.

Definisi II.7. Node ordering adalah domain pengetahuan yang digunakan oleh algoritma konstruksi  struktur  BN  yang  menspesifikasikan  urutan  kausal  dari  simpul‐simpul  yang terdapat pada graf. Pada sebuah informasi node ordering, simpul yang muncul lebih dahulu adalah merupakan sebab dari simpul lainnya muncul kemudian [CHE01[a]]. 

Penulisan notasi node ordering dinyatakan dengan (n1,n2,n3,n4,...,ni). Sebagai contoh,

jika diberikan informasi node ordering adalah (A,B,C,D,E) maka pasangan simpul

yang mungkin dibentuk sesuai dengan urutan penulisannya pada node ordering

tersebut adalah A B, A C, A D, A E, B C, B D, B E, C D, C E, dan

D E. Dalam hal ini simpul A adalah penyebab dari simpul B, dan bukan sebaliknya.

25

Dalam hal keterurutan simpul, suatu simpul yang muncul lebih dahulu pada node

ordering adalah sebagai penyebab dari simpul yang muncul sesudahnya. Jika sebuah

node ordering konsisten dengan model data set, maka node ordering tersebut

dikatakan correct ordering. Sebagai contohnya, pada gambar II.7 adalah suatu

struktur BN dengan dua buah correct ordering yaitu A-B-C-D-E dan A-B-D-C-E.

Gambar II.7. Struktur BN dengan dua correct ordering yaitu

A-B-C-D-B dan A-B-D-C-E

Dalam konteks berpikir manusia, keterurutan waktu diasumsikan sebagai suatu hal

yang selalu ada untuk dapat mendefinisikan hubungan kausalitas. Tidak diragukan

lagi bahwa informasi keterurutan waktu atau disebut juga sebagai informasi temporal

adalah merupakan suatu petunjuk yang digunakan oleh manusia untuk membedakan

bentuk hubungan kausal dan bukan kausal [PEA01]. Namun informasi temporal saja

tidak cukup untuk menentukan penyebab murni. Sebagai contoh, biasanya angka pada

barometer menurun sebelum terjadi hujan. Namun dalam konteks berpikir manusia,

dapat dipastikan bahwa terjadinya hujan bukan akibat dari angka pada barometer yang

menurun [PEA01].

26

Sebelum diberikan definisi penyebab murni, berikut ini diberikan definisi penyebab

potensial.

Definisi II.8. Sebuah  variabel  X  adalah  penyebab  potensial  terhadap  Y,  jika memenuhi kondisi berikut [PEA01]: 1. X dan Y adalah tidak bebas 2. Terdapat sebuah variabel Z dan {S} sehingga 

a. X dan Z bebas jika diketahui S b. Z dan Y tidak bebas jika diketahui S 

Sebagai contohnya, pada gambar II.8 variabel B memenuhi syarat sebagai penyebab

potensial terhadap D, karena memenuhi kondisi (1) B dan D tidak bebas, dan kondisi

(2) Dengan variabel Z=C dan {S}=A, maka B dan C bebas jika diketahui nilai A, dan

C dan D tidak bebas jika diketahui nilai A. Demikian juga C memenuhi syarat sebagai

penyebab potensial dari D (dalam hal ini Z=B dan {S}=A).

Gambar II.8. B dan C adalah penyebab potensial pada D,

dan D adalah penyebab asli pada E

Berikut diberikan definisi penyebab murni.

Definisi II.9. Sebuah  variabel  X  adalah  penyebab  murni  dari  variabel  Y  jika  terdapat sebuah variabel Z  sehingga X dan Y bergantung dalam keadaan apapun, dan ada  {S} yang memenuhi kondisi [PEA01]: a. Z adalah penyebab potensial dari X (sesuai definisi II.7) b. Z dan Y tidak bebas jika diketahui nilai S c. Z dan Y bebas jika diketahui nilai S∪X 

Sebagai contoh, pada gambar II.8 jika diberikan X=D, Y=E, Z=B, dan {S}= ∅ maka

D adalah penyebab murni dari E.

27

Pada definisi II.9 tidak ada pernyataan bahwa informasi temporal diketahui. Jika

informasi temporal diketahui, maka definisi II.9 dapat disederhanakan, karena setiap

variabel yang terjadi mendahului dan bertetangga dengan sebuah variabel X dapat

dikatakan memenuhi syarat sebagai penyebab potensial dari X. Definisi berikut

adalah bentuk sederhana dari definisi II.9 dengan penambahan informasi temporal.

Definisi II.10. Sebuah  variabel  X memiliki  pengaruh  kausal  terhadap  Y  jika  ada  variabel ketiga Z dan ada sebuah {S}, dan keduanya harus terjadi sebelum X yang memenuhi kondisi berikut [PEA01]: a. Z dan Y tidak bebas jika diketahui nilai S b. Z dan Y bebas jika diketahui nilai S∪X 

Terlihat bahwa tidak ada perbedaan antara definisi II.9 dan definisi II.10 kecuali

bahwa pada definisi II.10 ada informasi temporal yang dapat digunakan untuk

menyatakan bahwa Z adalah penyebab potensial dari X. Pada gambar II.8, jika D

diketahui maka Z dan Y akan berubah dari tidak bebas menjadi bebas, yang berarti

bahwa kebergantungan antara Z dan Y adalah melalui X. Dengan adanya informasi

temporal bahwa Z terjadi lebih dahulu dari X, maka dapat disimpulkan bahwa X

adalah penyebab Y [PEA01].

Definisi berikut akan menjelaskan aspek yang harus dipenuhi dalam menetapkan

hubungan kausalitas.

Definisi II.11. Dalam konteks berpikir manusia, hubungan kausalitas harus memenuhi dua aspek  yaitu:  temporal  dan  statistik.  Aspek  temporal  menyatakan  bahwa  sebab  harus mendahului akibat. Sedangkan aspek  statistik adalah untuk menyatakan  suatu  ‘penjelasan ilmiah’  akan  kausalitas  untuk memastikan  bahwa  hanya  secara  statistik  hal  yang  bersifat ilmiah  dapat  dihasilkan  [PEA01].  Artinya  adalah  bahwa  dengan  melakukan  pengujian statistik,  hubungan  kausalitas  dapat  dinyatakan  secara  ilmiah,  dan  pada  setiap  hubungan kausalitas tentu mengandung informasi temporal [PEA01]. 

Definisi II.12. Hubungan kausalitas bersifat asimetris, artinya tidak dapat dibolak‐balik. Jika tidak  ada  informasi  temporal,  akan mustahil  untuk memutuskan manakah  diantara  dua variabel yang saling bergantung yang akan menjadi sebab dan mana menjadi akibat. Hal  ini terjadi karena joint distribution P(x,y) dapat menyatakan x adalah sebab dan y adalah akibat, namun selain itu juga dapat menyatakan bahwa y adalah sebab dan x adalah akibat [PEA01]. Untuk dapat menentukan arah kausalitas pada DAG, maka sedikitnya ada tiga variabel  yang dibutuhkan. Namun dengan adanya  aspek  temporal  yaitu pernyataan bahwa  sebab  selalu mendahului akibat (definisi II.11), kausalitas yang bersifat simetris tidak berlaku lagi.  

28

Definisi II.12 menunjukkan bahwa, dengan bila kebergantungan varibel dapat

ditemukan, maka dengan memanfaatkan informasi temporal selanjutnya dapat

dibentuk kausalitasnya. Sebuah pertanyaan yang dapat diajukan untuk membantu

penjelasan defenisi II.12 tersebut adalah, apakah hubungan kausalitas yang

digambarkan dalam X Y pada kenyataanya dapat bertentangan dengan informasi

temporal yang ditemukan dalam kumpulan data? Jika hubungan kausalitas X Y

dibangun dari data, maka berdasarkan definisi II.11 dan II.12 dapat ditarik suatu

kesimpulan yang kuat terhadap aspek statistik yang dikandung pada suatu hubungan

sebab akibat, bahwa secara ilimiah pertentangan tersebut tidak mungkin terjadi

[PEA01]. Jadi hubungan kausalitas yang dibangun dari data juga merepresentasikan

aspek temporal.

Bagian ini ditutup dengan memberikan sebuah definisi yang kuat untuk menjelaskan

menghubungakan kausalitas dan informasi temporal.

Definisi II.13. Pada  saat menentukan  kausalitas, pengujian  statistik  yang  dilakukan pada kumpulan data secara ilmiah hanya menyatakan hubungan kausalitas yang terkandung pada kumpulan data tersebut, dan tidak ada hubungannya dengan informasi temporal [PEA01]. 

2.4. Sequential Pattern Bagian ini berisi konsep yang berhubungan dengan sequential pattern. Penjelasan

dimulai dari konsep dasar mengenai market basket analysis, elemen dan itemset yang

ada pada transaksi, association rule mining, dan frequent itemset. Pada bagian akhir

dijelaskan tentang teori sequential pattern dan ditutup dengan pemberian sebuah

contoh sequential pattern.

.

2.4.1. Konsep dasar Pada sub bab ini, diuraikan beberapa konsep dasar yang berhubungan dengan

himpunan data yang sering dijadikan sebagai objek penelitian yaitu market basket

data. Kemudian diuraikan juga tentang association rule dan perannya dalam

menemukan frequent itemset dari himpunan data tersebut.

29

Berikut diberikan beberapa definisi:

Definisi II.14. Market  basket  data  adalah  himpunan  data    yang  dijadikan  sebagai  objek penelitan pada area data mining. Market basket analysis adalah proses untuk menganalisis kebiasaan  pelanggan  dalam menyimpan  item‐item  yang  akan  dibeli  ke  dalam  keranjang belanjaannya.  Market  basket  analysis  memanfaatkan  data  transaksi  penjualan  untuk dianalisis  sehingga  dapat  ditemukan  pola  berupa  item‐item  yang  cenderung  muncul bersama dalam sebuah transaksi [HAN06].  

Selanjutnya pola yang ditemukan dapat dimanfaatkan untuk merancang strategi

penjualan atau pemasaran yang efektif, yaitu dengan menempatkan item-item yang

sering dibeli bersamaan ke dalam sebuah area yang berdekatan, merancang tampilan

item-item di katalog, merancang kupon diskon (untuk diberikan kepada pelanggan

yang membeli item tertentu), merancang penjualan item-item dalam bentuk paket, dan

sebagainya. Dengan menggunakan teknologi data mining, analisis data secara manual

tidak diperlukan lagi.

Definisi II.15. Elemen dalam  suatu  transaksi disebut  juga  sebagai  item,  yang merupakan suatu unit objek tekecil. Himpunan elemen disebut  juga sebagai  itemset, tetapi tidak boleh kosong.  Itemset yang berisi k  item  (dengan k adalah banyaknya  item dari sebuah  itemset) disebut k‐itemset. Misalnya,  itemset {computer, software} adalah 2‐itemset atau 2‐elemen. Frekuensi  kemunculan  dari  suatu  itemset  adalah  banyaknya  transaksi  yang  berisi  itemset tersebut  dari  keseluruhan  transaksi,  juga  sering  disebut  hanya  sebagai  frekuensi,  atau support  count,  atau  count dari  itemset.  Suatu  k‐itemset  yang dihitung  support  count‐nya disebut kandidat k‐itemset dan dituliskan dengan simbol Ck.  

Definisi II.16. Association  rule  adalah  aturan  yang  digunakan  untuk mengukur  besarnya asosiasi  atau  keterhubungan  antar  item  dalam  market  basket  data.  Association  rule merupakan uji  statistik  yang merepresentasikan  ukuran  ketertarikan  antar  data.  Terdapat dua ukuran  ketertarikan  (interestingness)   pada  association  rule dalam bentuk X⇒Y  yaitu [HAN06]:  a. support, merepresentasikan persentase transaksi dalam basis data yang berisi kombinasi 

item  X∪Y  (gabungan  dari  himpunan  X  dan  himpunan  Y).  Ini  dapat  dituliskan  dalam bentuk probabilitas, P(X∪Y). 

b. confidence  yaitu  kuatnya  hubungan  antar  item  dalam  aturan  assosiatif,  yang menunjukkan persentasi dari  transaksi yang memuat X yang  juga memuat Y.  Ini dapat dituliskan dalam bentuk probabilitas kondisional, P(X|Y).  

Hubungan itemset dan association rule dijelaskan pada bagian berikut. Sebelumnya

diberikan sebuah definisi tambahan untuk menjelaskan association rule mining.

Definisi II.17. Asssociation  rule mining adalah  teknik  yang menggunakan association  rule, untuk menemukan keterhubungan antar  itemset dalam market basket data. Keterhubungan antar  itemset 

30

yang  ditemukan  selanjutnya  akan  diolah menjadi  sebuah  informasi  yang  dapat  digunakan  dalam membuat  keputusan  strategis,  seperti  pengaturan  penempatan  barang  dalam  rak,  promosi pemasaran lewat katalog, dan penggunaan kupon diskon untuk kombinasi barang tertentu. [HAN06] 

Pada association rule mining, ada dua parameter yang digunakan, yaitu minimum

support threshold (min_sup) dan minimum confidence threshold (min_conf).

Minimum support threshold (min_sup) adalah parameter yang digunakan sebagai

ambang batas untuk menentukan apakah jumlah kemunculan suatu itemset dari

seluruh transaksi dapat diterima atau tidak. Selanjutnya, itemset yang memenuhi

min_sup disebut sebagai frequent itemset. Minimum confidence threshold (min_conf)

adalah parameter yang digunakan sebagai ambang batas untuk menentukan apakah

suatu itemset muncul jika itemset lainnya telah muncul dapat diterima atau tidak.

Hasil akhir association rule mining adalah ditemukannya asosiasi itemset yang

frequent dalam bentuk informasi statistik. Sebagai contoh, nilai probabilitas seorang

pelanggan membeli roti dan susu secara bersamaan, nilai probabilitas seorang

pelanggan akan membeli printer jika telah membeli komputer, atau nilai probabilitas

seorang pelanggan membelanjakan uangnya sebesar jumlah tertentu. Informasi

statistik tersebut selanjutnya dapat dimanfaatkan untuk mendukung keputusan

strategis.

Proses menemukan keterhubungan antar itemset disebut dengan association rule

mining dan sudah diimplementasikan dalam banyak algoritma. Sebagai catatan,

algortima yang menerapkan association rule mining tidak dibahas dalam tulisan ini.

2.4.2. Teori Sequential Pattern Pada sub bab ini diuraikan teori sequential pattern, dan secara umum banyak

mengambil prinsip yang terdapat pada market basket data dan association rule yang

telah dijelaskan pada sub bab sebelumnya.

Definisi II.18. Sequential  pattern  adalah  pola  yang  menggambarkan  urutan  waktu terjadinya peristiwa  [HAN06]. Pola  tersebut bisa ditemukan  jika data yang disimpan  relatif cukup besar, dan objek yang sama dalam jumlah yang relatif besar melakukan beberapa aksi yang  berulang  kali.  Sebagi  contohnya,  pelanggan  yang  memiliki  identitas  yang  tercatat, melakukan transaksi belanja berulang kali pada sebuah toko atau pusat perbelanjaan. 

Dalam sebuah basis data yang menyimpan barket basket data, terdapat data sejumlah

transaksi dan masing-masing transaksi terdiri dari field berupa id_pelanggan,

31

waktu_transaksi, daftar_item. Pada seluruh data yang tersimpan, hanya ada satu transaksi

yang dilakukan oleh satu pelanggan pada satu waktu. Dalam suatu transaksi,

banyaknya item yang dibeli tidak dipertimbangkan, namun diperlakukan sebagai

sebuah variabel biner yang merepresentasikan sebuah item dibeli atau tidak [AGR00].

Untuk lebih memperjelas berbagai notasi yang digunakan dalam konteks sequential

pattern, berikut diberikan sebuah definisi baru terhadap item (elemen), dan itemset

(himpunan elemen).

Definisi II.19. Elemen dalam suatu transaksi disebut sebagai item dan dinotasikan dengan i. Himpunan  elemen  disebut  juga  sebagai  itemset  dan  dinotasikan  dengan  is.  Selanjutnya dapat  dinyatakan  sebuah  itemset  is  adalah  sama  dengan  (i1,  i1,...,ij),  yang  dalam  hal  ini  ij adalah sebuah item. 

Sebagai contoh, misalnya pada sebuah transaksi belanja terdapat dua item, yaitu

komputer dan anti virus, maka akan dibentuk sebuah itemset is berisi (komputer,

antivirus).

Selanjutnya diberikan definisi sequence.

Definisi II.20. Sequence  adalah  himpunan  itemset  yang  telah  tersusun  secara  menaik berdasarkan waktu  terjadinya  [AGR00].  Sebuah  sequence  dinotasikan  sebagai  s  yaitu  ⟨is1 is2...isk⟩,  yang  dalam  hal  ini  isk  adalah  sebuah  itemset.  Pada  sebuah  sequence,  urutan penulisan  himpunan  itemset  harus  diperhatikan,  karena  urutan  penulisan  tersebut merepresentasikan  waktu  terjadinya  seluruh  itemset  yang  menyusun  sebuah  sequence. Pada  sebuah  itemset  yang merupakan  anggota  sebuah  sequence,  urutan  penulisan  item tidak perlu diperhatikan, sehingga bisa dituliskan dengan tidak beraturan.  

Untuk lebih memperjelas pengertian sequence, itemset, item, dan urutan penulisan,

berikut diberikan sebuah contoh pada kasus analisis market basket sebuah tempat

belanja. Diasumsikan bahwa item yang tersedia adalah sebanyak lima jenis yaitu a, b,

c, d, dan e. Pelanggan pertama dalam lima transaksi berturut-turut membeli sejumlah

item sebagai berikut: a, a b c, a c, d, dan c f. Pelanggan kedua dalam empat transaksi

berturut-turut membeli himpunan item sebagai berikut: a d, c, b c, dan a e. Dalam

basis data tercatat data kelima jenis elemen yaitu {a,b,c,d,e,f,g} dan dua sequence

yaitu ⟨a, (abc), (ca), d, (fc)⟩ dan ⟨(ad), c, (bc), (ae)⟩ masing-masing untuk pelanggan

pertama dan pelanggan kedua. Sequence tersebut dibentuk dengan cara mengurutkan

secara menaik berdasarkan waktu transaksi. Pada sequence pertama, himpunan

32

elemen dapat dituliskan sebagai ⟨a, (abc), (ca), d, (fc)⟩ meskipun transaksi yang

terjadi adalah a, a b c, a c, d, dan c f. Hal ini bukanlah sebuah masalah, karena dalam

satu himpunan elemen, urutan elemen tidak dipertimbangkan.

Selanjutnya diberikan definisi maksimal sequence.

Definisi II.21. Suatu sequence dikatakan maksimal,  jika sequence  tersebut  tidak  terdapat pada  sequence  lainnya  [AGR00].  Sebuah  sequence  ⟨a1,  a2, …  ,an⟩ dikatakan  terdapat pada sebuah sequence lainnya ⟨b1, b2, … ,bm⟩ jika ada integer i1 < i2 … < in sehingga a1 ⊆ bi1, a2 ⊆ bi1, ..., an ⊆ bin.  

Untuk lebih memperjelas mengenai maksimal sequence, berikut diberikan sebuah

contoh.Suatu sequence ⟨(3), (4 5), (8)⟩ merupakan bagian dari ⟨(7), (3 8), (9), (4 5 6)

(8)⟩, karena (3) ⊂ (3 8), (4 5) ⊂ (4 5 6) dan (8) ⊂ (8). Suatu sequence ⟨(3) (5)⟩ bukan

merupakan bagian dari sequence ⟨(3 5)⟩ (dan sebaliknya). Item 3 dan 5 pada sequence

pertama dibeli satu setelah yang lainnya. Item 3 dan 5 pada sequence selanjutnya,

dibeli secara bersamaan [AGR00].

Sequential pattern memiliki kaitan yang sangat erat dengan frequent itemset. Pada

contoh tersebut, terlihat bahwa satu sequence terdiri dari satu itemset. Hanya itemset

yang memuhi min_sup yang dapat dijadikan sebuah sequence. Sebagai akibatnya,

seluruh itemset yang terdapat pada seluruh sequence pada sequential pattern adalah

himpunan frequent itemset (itemset yang memenuhi min_sup). Berikut diberikan

sebuah definisi.

Definisi II.22. Pada sequential pattern, seluruh sequence disusun oleh himpunan frequent itemset  yaitu  himpunan  itemset  yang  memenuhi  min_sup.  (frequent  itemset  ada  pada definisi II.15). 

2.4.3. Contoh Sequential Pattern Berikut ini diberikan sebuah contoh yang menjelaskan sequential pattern secara

keseluruhan. Untuk mempersingkat penjelasan, berikut diberikan sebuah gambar yang

berisi data transaksi lima pelanggan dan pada setiap transaksi dicatat id_pelanggan,

waktu_transaksi, dan daftar item. Pada gambar tersebut, seluruh data transaksi telah

dikelompokkan berdasarkan id_pelanggan dan telah diurutkan menaik berdasarkan

waktu_transaksi.

33

id_pelanggan waktu_transaksi item

1 1

29 Juni ‘93 30 Juni ‘93

30 90

2 2 2

10 Juni ‘93 15 Juni ‘93 20 Juni ‘93

10,20 30 40,60,70

3 25 Juni ‘93 30,50,70 4 4 4

25 Juni ‘93 30 Juni ‘93 25 Juli ‘93

30 40,70 90

5 12 Juni ‘93 90

Gambar II.9. Basis data dikelompokkan berdasarkan id_pelanggan

Seluruh transaksi yang dilakukan oleh seorang pelanggan dipandang sebagai satu

sequence. Dalam hal ini masing-masing transaksi berkorespondensi dengan satu

itemset, dan seluruh transaksi yang dirutkan secara menaik berdasarkan waktu

transaksi berkorespondensi dengan sebuah sequence yang membentuk sequence

pelanggan. Gambar berikut memberikan daftar lengkap sequence pelanggan yang

terbentuk.

id_pelanggan sequence pelanggan

1 ⟨(30), (90)⟩ 2 ⟨(10,20), (30), (70,60,40)⟩ 3 ⟨(30, 70, 50)⟩ 4 ⟨(30), (70, 40), (90)⟩ 5 ⟨(90)⟩

Gambar II.10. Sequence pelanggan

Pada tabel tersebut, urutan item yang terdapat pada seluruh itemset tidak

dipermasalahkan, tetapi urutan itemset-itemset yang menyusun sebuah sequence

adalah terurut menaik berdasarkan waktu terjadinya.

Proses menemukan sequential pattern itu sendiri adalah sebuah proses yang

melibatkan algoritma, dan proses ini disebut dengan sequential pattern mining.

Sequential pattern mining tidak dibahas pada bagian ini namun dijelaskan pada

lampiran C. Sebagai hasil akhir proses pada contoh tersebut, jika nilai min_sup adalah

25% maka sequential pattern yang dapat ditemukan adalah ⟨(30), (90)⟩ dan ⟨(30), (40,

70)⟩.