Metodologi Algoritma A Priori 1
Kusrini, 2Emha Taufiq Luthfi Jurusan Sistem Informasi, 2Jurusan Teknik Informatika 1, 2 STMIK AMIKOM Yogykakarta 1,2 Jl. Ringroad Utara Condong Catur Sleman Yogyakarta 1
Metodologi dasar algoritma a priori analisis asosiasi terbagi menjadi dua tahap : 1. Analisa pola frekuensi tinggi Tahap ini mencari kombinasi item yang memenuhi syarat minimum dari nilai support dalam database. Nilai support sebuah item diperoleh dengan rumus berikut:
Support ( A) =
Jumlah transaksi mengandung A Total Transaksi
sedangkan nilai support dari 2 item diperoleh dari rumus 2 berikut :
Support ( A, B ) = P ( A ∩ B )
Support ( A, B ) =
∑
Transaksi mengandung A dan B
∑ Transaksi 1 2 3 4 5 6 7 8 9 10
Transaksi Tabel 1. Transaksi Item yang dibeli Susu, Teh, Gula Teh, Gula, Roti Teh, Gula Susu, Roti Susu, Gula, Roti Teh, Gula Gula, Kopi, Susu Gula, Kopi, Susu Susu, Roti, Kopi Gula, Teh, Kopi
Sebagai contoh, ada database dari transaksi belanja pasar swalayan seperti ditunjukkan dalam Tabel 1 Data pada Tabel 1 dalam database transaksional biasa direpresentasikan dalam bentuk seperti tampak pada Tabel 2
Tabel 2. Representasi Data Transaksi dalam Database Transaksional Transaksi Item yang dibeli 1 Susu 1 Teh 1 Gula 2 Teh 2 Gula 2 Roti 3 Teh 3 Gula 4 Susu 4 Roti 5 Susu 5 Gula 5 Roti 6 Teh 6 Gula 7 Gula 7 Kopi 7 Susu 8 Gula 8 Kopi 8 Susu 9 Susu 9 Roti 9 Kopi 10 Gula 10 Teh 10 Kopi Dan bila kita bentuk dalam bentuk tabular, data transaksi akan tampak seperti pada Tabel 3. Tabel 3. Format Tabular Data Transaksi Transaksi Teh Gula Kopi Susu Roti 1 1 1 0 1 0 2 1 1 0 0 1 3 1 1 0 0 0 4 0 0 0 1 1 5 0 1 0 1 1 6 1 1 0 0 0 7 0 1 1 1 0 8 0 1 1 1 0 9 0 0 1 1 1 10 1 1 1 0 0 Misalkan D adalah himpunan transaksi yang direperesentasikan dalam Tabel 1, dimana masing-masing transaksi T dalam D merepresentasikan himpunan item yang berada dalam I. I adalah himpunan iterm yang dijual {Teh, Gula, Kopi, Susu, Roti}. Misalkan kita memiliki himpunan items A (misal Susu dan Gula) dan himpunan item lain B (misal Kopi). Kemudian aturan asosiasi akan berbentuk
Jika
A, maka B ( AÆB)
Dimana antecedent A dan consequent B merupakan subset dari I, dan A dan B merupakan mutually exclusive dimana aturan Jika A maka B
tidak berarti Jika B maka A
Definisi ini tidak berlaku untuk aturan trivial seperti : Jika beans dan Squash
Maka beans
Seorang analis mungkin hanya akan mengambil aturan yang memiliki support dan/atau confidence yang tinggi. Aturan yang kuat adalah aturan-aturan yang melebihi kriteria support dan/atau confidence minimum. Misalnya seorang analist menginginkan aturan yang memiliki support lebih dari 20% dan confidence lebih dari 35%. Sebuah itemset adalah himpunan item-item yang ada dalam I, dan k-itemset adalah itemset yang berisi k item. Misalnya {Teh, Gula) adalah sebuah 2-itemset dan {Teh, Gula, Roti) merupakan 3-itemset. Frequent Itemset menunjukkan itemset yang memiliki frekuensi kemunculan lebih dari nilai minimum yang telah ditentukan (ф). Misalkan ф = 2, maka semua itemset yang frekuensi kemunculannya lebih dari atau sama dengan 2 kali disebut frequent. Himpunan dari frequent k-itemset dilambangkan dengan Fk. Tabel 4 berikut ini menujukkan calon 2-itemset dari data transaksi pada Tabel 1.
Table 5.4. Calon 2-itemset Kombinasi Jumlah Teh, Gula 5 Teh, Kopi 1 Teh, Susu 1 Teh, Roti 1 Gula, Kopi 3 Gula, Susu 4 Gula, Roti 2 Kopi, Susu 3 Kopi, Roti 1 Susu, Roti 3 Dari data tersebut diatas, jika ditetapkan nilai ф = 3 maka F2 =
{ {Teh, Gula}, {Gula, Kopi}, {Gula, Susu}, {Gula, Roti}, {Kopi, Susu}, {Susu, Roti}}
Table 5.5. Calon 3-itemset Kombinasi Jumlah Teh, Gula, Kopi 1 Teh, Gula, Susu 1 Gula, Susu, Kopi 2 Gula, Susu, Roti 0 Gula, Kopi, Roti 0 Kopi, Susu, Roti 1 Kombinasi dari itemset dalam F2 dapat kita gabungkan menjadi calon 3-itemset. Itemsetitemset dari F2 yang dapat digabungkan adalah itemset-itemset yang memiliki kesamaan dalam k-1 item pertama. Calon 3-itemset yang dapat dibentuk dari F2 seperti tampak pada Tabel 5. Dengan demikian F3 = {{Gula, Susu, Kopi}}, karena hanya kombinasi inilah yang memiliki frekeunsi kemunculan >= ф. 2. Pembentukan aturan Asosiasi Setelah semua pola frekuensi tinggi ditemukan, barulah dicari aturan asosiasi yang memenuhi syarat minimum untuk confidence dengan menghitung confidence aturan assosiatif A Æ B Nilai confidence dari aturan AÆ B diperoleh dari rumus berikut:
Confidence = P( B | A) =
∑
Transaksi mengandung A dan B
∑
Transaksi mengandung A
Dari F3 yang telah ditemukan, dapat dilihat besarnya nilai support dan confidence dari calon aturan asosiasi seperti tampak pada Tabel 6. Tabel 6. Calon Aturan Asosiasi dari F3 Aturan Confidence Jika membeli Gula dan Susu 2/4 50% Maka akan membeli Kopi Jika membeli Gula dan Kopi 2/3 67% Maka akan membeli Susu Jika membeli Kopi dan Susu 2/3 67% Maka akan membeli Gula Misalkan ditetapkan nilai confidence minimal adalah 60% maka aturan yang bisa terbentuk adalah aturan dengan 2 antecedent berikut: Jika membeli Gula dan Kopi Maka akan membeli Susu Jika membeli Kopi dan Susu Maka akan membeli Gula
Sementara itu calon aturan asosiasi dari F2 bisa dilihat pada Tabel 7
Table 5.7. Aturan Asosiasi Aturan Confidence Jika membeli Teh 5/5 100% Maka akan membeli Gula Jila membeli Gula 5/8 62.5% Maka akan membeli Teh Jika membeli Gula 3/8 37.5% Maka akan membeli Kopi Jika membeli Kopi 3/4 75% Maka akan membeli Gula Jika membeli Gula 4/8 50% Maka akan membeli Susu Jika membeli Susu 4/6 67% Maka akan membeli Gula Jika membeli Gula 2/8 25% Maka akan membeli Roti Jika membeli Roti 2/4 50% Maka akan membeli Gula Jika membeli Kopi 3/4 75% Maka akan membeli Susu Jika membeli Susu 3/6 50% Maka akan membeli Kopi Jika membeli Susu 3/6 50% Maka akan membeli Roti Jika membeli Roti 3/4 75% Maka akan membeli Susu
dan aturan asosiasi final terurut berdasarkan Support x Confidence terbesar dapat dilihat pada Table 5.8. Tabel 8. Aturan Asosiasi Final ATURAN
SUPPORT
CONFIDENCE
Jika membeli Teh Maka akan membeli Gula
50%
100%
Jila membeli Gula Maka akan membeli Teh Jika membeli Susu Maka akan membeli Gula Jika membeli Kopi Maka akan membeli Gula Jika membeli Kopi Maka akan membeli Susu Jika membeli Roti Maka akan membeli Susu Jika membeli Gula dan Kopi Maka akan membeli Susu Jika membeli Kopi dan Susu Maka akan membeli Gula
50%
62.50%
SUPPORT x CONFIDENCE 50.0% 31.3%
40%
67%
30%
75%
30%
75%
30%
75%
26.8% 22.5% 22.5% 22.5%
20%
67%
20%
67%
13.4%
13.4%
Contoh implementasi algoritma a priori dalam aplikasi dibahas secara detail dalam buku “Algoritma Data Mining” Daftar Pustaka Kusrini dan Luthfi, E. T., 2009, Algoritma Data Mining, Andi Offset, Yogyakarta
