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 9
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 paruparu, 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.
10
Gambar II.1.
Bayesian network [NEA04]
Representasi nilai dari masing-masing simpul pada BN tersebut diberikan pada gambar berikut.
Node
Nilai
H B L F C
Gambar II.2.
h1 h2 b1 b2 l1 l2 f1 f2 c1 c2
Keterangan Ada riwayat merokok (H=history) Tidak ada riwayat merokok Bronkhitis ada (B=Bronkhitis) Bronkhitis tidak ada Kanker paru-paru ada (L=lung) Kanker paru-paru tidak ada Kelelahan ada (F=Fatique) Kelelahan tidak ada Hasil uji sinar-X terhadap kanker paru-paru positif (C=Cancer) Hasil uji sinar-X terhadap kanker paru-paru negatif
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. 11
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:
P (b1, h1, f 1, c1) P (b1 | h1, f 1, c1) = = P (h1, f 1, c1)
∑ P(b1, h1, f 1, c1, l ) .....................................(II.1) ∑ P(b, h1, f 1, c1, l ) l
b ,l
Yang dalam hal ini,
∑
berarti penjumlahan b dan l untuk semua kemungkinan nilai-
b,l
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
12
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 13
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 14
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]].
15
Mutual information antara dua simpul A dan B didefinisikan sebagai berikut [CHE97]:
I(Xi , X j ) =
P( xi , x j )
∑ P( x , x ) log P( x ) P( x ) ...................................................(II.3) i
xi , x j
j
i
j
dan conditional mutual information didefinisikan sebagai berikut [CHE97]:
I ( X i , X j | c) =
∑
P( xi , x j , c) log
xi , x j , c
P( xi , x j | c) P( xi | c) P( x j | c)
.................................(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.
16
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 dseparation, 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
17
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 BD-E terblok pada D
•
C dan D d-separated oleh {B} karena chain C-B-D terblok pada B dan chain C-ED 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)
18
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
Gambar II.5.
C
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. 19
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 20
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 masingmasing 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. C
A
A
Gambar II.6.
B
C
E
A
B
E
D
D
(a)
(b)
C
C
B
E
A
B
E
D
D
(c)
(d)
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. 21
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. 22
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 cutset 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 23
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. 24
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].
25
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. 26
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.
27
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.
28
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
29
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, 30
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 31
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.
32
id_pelanggan 1 1 2 2 2 3 4 4 4 5
Gambar II.9.
waktu_transaksi 29 Juni ‘93 30 Juni ‘93 10 Juni ‘93 15 Juni ‘93 20 Juni ‘93 25 Juni ‘93 25 Juni ‘93 30 Juni ‘93 25 Juli ‘93 12 Juni ‘93
item 30 90 10,20 30 40,60,70 30,50,70 30 40,70 90 90
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 1 2 3 4 5
Gambar II.10.
sequence pelanggan 〈(30), (90)〉 〈(10,20), (30), (70,60,40)〉 〈(30, 70, 50)〉 〈(30), (70, 40), (90)〉 〈(90)〉
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)〉.
33
