Algoritma Apriori (Association Rule)

Daftar Isi “Algoritma Apriori (Association Rule)“

1. Pengertian Algoritma Apriori
2. Contoh Pemakaian Hasil dari Mempelajari Aturan Asosiasi
3. Definisi-Definisi yang Terdapat Pada Association Rule
4. Langkah atau Cara Kerja Apriori
5. Formula Pencarian Nilai Support & Confidence
6. Latihan Soal 1
7. Latihan Soal 2
8. Latihan Soal 3
9. Latihan Soal 4

1. Pengertian Algoritma Apriori

Algoritma apriori merupakan salah satu algoritma klasik data mining. Algoritma apriori digunakan agar komputer dapat mempelajari aturan asosiasi, mencari pola hubungan antar satu atau lebih item dalam suatu dataset.

Algoritma apriori banyak digunakan pada data transaksi atau biasa disebut market basket, misalnya sebuah swalayan memiliki market basket, dengan adanya algoritma apriori, pemilik swalayan dapat mengetahui pola pembelian seorang konsumen, jika seorang konsumen membeli item A , B, punya kemungkinan 50% dia akan membeli item C, pola ini sangat signifikan dengan adanya data transaksi selama ini.

Penting tidaknya suatu aturan assosiatif dapat diketahui dengan dua parameter, support (nilai penunjang) yaitu persentase kombinasi item tersebut dalam database dan confidence (nilai kepastian) yaitu kuatnya hubungan antar item dalam aturan assosiatif.

Aturan assosiatif biasanya dinyatakan dalam bentuk : {roti, mentega} -> {susu} (support = 40%, confidence = 50%)

Yang artinya : “Seorang konsumen yang membeli roti dan mentega punya kemungkinan 50% untuk juga membeli susu. Aturan ini cukup signifikan karena mewakili 40% dari catatan transaksi selama ini.”

Analisis asosiasi didefinisikan suatu proses untuk menemukan semua aturan assosiatif yang memenuhi syarat minimum untuk support (minimum support) dan syarat minimum untuk confidence (minimum confidence).

Tetapi di lain pihak Apriori memiliki kelemahan karena harus melakukan scan database setiap kali iterasi, sehingga waktu yang diperlukan bertambah dengan makin banyak iterasi. Masalah ini yang dipecahkan oleh algoritma-algoritma baru seperti FP-growth.

2. Contoh Pemakaian Hasil dari Mempelajari Aturan Asosiasi

1. Meletakkan barang-barang yang sering dibeli bersamaan dengan posisi berdekatan atau mudah dijangkau sehingga diharapkan pembeli membeli barang lebih banyak. Cara ini dikembangkan oleh Wal-Mart yang merupakan salah satu pasar swalayan populer di Amerika. Saat itu Wal-Mart menganalisis data yang dimilikinya, dan menemukan bahwa pada hari Jumat sore, pembeli laki-laki yang membeli popok, ternyata cenderung membeli bir. Dari hasil temuan tersebut, Wal-Mart menempatkan bir di dekat tempat penjualan popok, dan alhasil penjualan bir meningkat. Kasus ini menjadi terkenal, karena sebelumnya banyak yang tidak menduga akan ampuhnya data mining.
2. Amazon.com, mengembangkan perekomendasi (recommender), yaitu sebuah program untuk merekomendasikan barang-barang lain kepada pembeli pada saat pembeli melakukan browsing atau membeli suatu barang berdasarkan tingkat keyakinan (confidence).
   

   amazon asosiasi

3. Google mengembangkan fitur auto-complete, yaitu saat pemakai mengetikkan suatu kata, program akan menampilkan daftar kata-kata berikutnya, yang paling banyak memiliki asosiasi pada kata yang diketik

3. Definisi-Definisi yang Terdapat Pada Association Rule

1. E adalah himpunan yang tengah dibicarakan. Contoh: {Asparagus, Beans, …, Tomatoes}

2. D adalah Himpunan seluruh transaksi yang tengah dibicarakan. Contoh: {Transaksi 1, transaksi 2, …, transaksi 14}

3. Proper Subset adalah Himpunan Bagian murni. Contoh:
Ada suatu himpunan A={a,b,c,}
Himpunan Bagian dari A adalah
Himpunan Kosong = {}
Himpunan 1 Unsur = {a},{b},{c}
Himpunan 2 Unsur = {a,b},{a,c},{b,c}
Himpunan 3 Unsur = {a,b,c,}
Proper subset nya adalah Himpunan 1 Unsur dan Himpunan 2 Unsur

4. Item set adalah Himpunan item atau item-item di E. Contoh:
Ada suatu himpunan E={a,b,c,}, Item set nya adalah {a};{b}:{c};{a,b};{a,c};{b,c}

5. K- item set adalah Item set yang terdiri dari K buah item yang ada pada E. Intinya K itu adalah jumlah unsur yang terdapat pada suatu Himpunan. Contoh: 2-item set adalah yang bersifat 2 unsur {a,b},{a,c},{b,c}.

6. Item set Frekuensi adalah Jumlah transaksi di I yang mengandung jumlah item set tertentu. Intinya jumlah transaksi yang membeli suatu item set. Contoh:
Kita gunakan tabel transaksi penjualan sayur di atas
– frekuensi Item set yang sekaligus membeli Beans dan Brocolli adalah 3
– frekuensi item set yang membeli sekaligus membeli Beans, Squash dan Tomatoes adalah 2.

7. Frekuen Item Set adalah item set yang muncul sekurang-kurangnya “sekian” kali di D (minimum support). Kata “sekian” biasanya di simbolkan dengan Ф. Ф merupakan batas minimum dalam suatu transaksi.

8. Fk atau K-itemset adalah himpunan semua frekuen Item Set yang terdiri dari K item, misalnya beras,telur,minyak adalah 3-itemset (Dinotasikan sebagai K-itemset)

4. Langkah atau Cara Kerja Apriori

1. Tentukan minimum support.
2. Iterasi 1 : hitung item-item dari support(transaksi yang memuat seluruh item) dengan men-scan database untuk 1-itemset, setelah 1-itemset didapatkan, dari 1-itemset apakah diatas minimum support, apabila telah memenuhi minimum support, 1-itemset tersebut akan menjadi pola frequent tinggi.
3. Iterasi 2 : untuk mendapatkan 2-itemset, harus dilakukan kombinasi dari k-itemset sebelumnya, kemudian scan database lagi untuk hitung item-item yang memuat support. itemset yang memenuhi minimum support akan dipilih sebagai pola frequent tinggi dari kandidat.
4. Tetapkan nilai k-itemset dari support yang telah memenuhi minimum support dari k-itemset.
5. Lakukan proses untuk iterasi selanjutnya hingga tidak ada lagi k-itemset yang memenuhi minimum support.

5. Formula Pencarian Nilai Support & Confidence

Nilai support sebuah item diperoleh dengan rumus berikut:

support-A

Sedangkan nilai support dari 2 item diperoleh dari rumus berikut:

support-AUB

Setelah semua pola frekuensi tinggi ditemukan, barulah dicari aturan assosiatif yang memenuhi syarat minimum untuk confidence dengan menghitung confidence aturan assosiatif A -> B. Nilai confidence dari aturan A -> B diperoleh dari rumus berikut:

confidence-A-B

6. Latihan Soal 1

Tabel 1. Transaksi yang dibeli

Golden rule (threshold) yang digunakan adalah : 60% atau barang yang dibeli paling sedikit 3.

Untuk mempermudah, nama-nama item di Tabel 1, disingkat dengan diambil huruf awalnya saja, sebagai contoh :
M = Mango
O = Onion
Dan sebagainya.

Tabel 2. Transaksi yang dibeli (2)

Langkah ke-1 : Hitung banyaknya transaksi untuk setiap item. Hati-hati, untuk item O (Onion) dibeli sebanyak 4 biji, namun pembelian O hanya ada 3 transaksi.

Tabel 3. Banyaknya Transaksi per Item

Langkah ke-2 : Berdasarkan golden rule yang telah disebutkan di atas, saring data pada Tabel 3, hanya memilih item yang memiliki transaksi minimal sebanyak 3 transaksi. Item yang banyaknya transaksi kurang dari 3, dibuang. Hasilnya dapat dilihat di Tabel 4.

Tabel 4. Item yang Paling Sering Dibeli

Langkah ke-3 : Buat pasangan item dimulai dari item pertama, yaitu MO, MK, ME, MY. Kemudian dilanjutkan dengan item kedua. Misalnya OK, OE, OY. Perhatikan, OM tidak dibuat karena OM = MO (pasangan yang dibuat dari item pertama).

Tabel 5. Pasangan Item

Langkah ke-4 : Hitung berapa kali suatu pasangan item dibeli bersamaan. Contohnya pasangan MO dibeli secara bersamaan dalam itemset {M, O, N, K, E, Y}. Pasangan MK dibeli bersamaan sebanyak 3 kali yaitu di dalam {M,O,N,K,E,Y}, {M,A,K,E}, dan {M,U,C, K, Y}. Hasilnya dapat dilihat pada Tabel 6.

Tabel 6. Banyaknya Transaksi Pasangan Item

Langkah ke-5 : Gunakan golden rule, hapus semua pasangan item yang banyaknya transaksi kurang dari tiga. Hasilnya adalah pada Tabel 7.

Tabel 7. Transaksi Pasangan Item yang Terbanyak

Langkah ke-6 : Buat pasangan tiga item dengan aturan menggunakan pasangan item pada Tabel 7 yang memiliki huruf awal yang sama yaitu :

• OK dan OE, menjadi OKE
• KE dan KY, menjadi KEY

Kemudian hitung ada beberapa banyaknya transaksi dari pasangan tiga item berdasarkan Tabel 3. Hasilnya dapat dilihat pada Tabel 8.

Tabel 8. Banyak Transaksi 3 Pasang Item

Dalam langkah ini, misalkan ada tiga pasangan item ABC, ABD, ACD, ACE, BCD dan akan dibuatkan pasangan 4 item, carilah 2 huruf awal yang sama. Contoh :

• ABC dan ABD, menjadi ABCD
• ACD dan ACE, menjadi ACDE

Dan seterusnya. Secara umum, carilah pasangan item yang huruf (item) terakhirnya berbeda.

Langkah ke-7 : Gunakan lagi golden rule, dengan membuang pasangan tiga item yang banyaknya transaksi kurang dari 3. Hasilnya tinggal OKE karena KEY hanya dibeli bersamaan dua kali.

Kesimpulan : Tiga item yang sering dibeli bersamaan adalah O, K, dan E.

Untuk mengetahui tingkat keyakinan (confidence), frequent itemset (yaitu {O, K, E}) dapat digunakan untuk mencari aturan-aturan asosiasi antar item di dalam frequent itemset tersebut. Caranya adalah :
1. Itemset dibuatkan himpunan bagiannya. Hasilnya seperti pada contoh di bawah :
• {O}
• {K}
• {E}
• {O, K}
• {K, E}
• {O, E}

2. Cari asosiasi pada semua himpunan bagian yang telah dibuat, misal : {O} => {K, E} artinya : jika O dibeli, bagaimana kemungkinan K dan E akan dibeli pada transaksi yang sama. O dibeli pada 3 transaksi dan di dalam 3 transaksi tersebut, K dan E juga dibeli. Maka keyakinannya adalah :

{O} => {K, E} : keyakinannya adalah 3/3 x 100% = 100%.
{K} => {O,E} : keyakinannya adalah 3/5 x 100% = 60%
{E} => {O,K} : keyakinannya adalah 3/4 x 100% = 75%
{K,E} => {O} : keyakinannya adalah 3/3 x 100% = 100%
{O,E} => {K} : keyakinannya adalah 3/3 x 100% = 100%
{O,K} => {E} : keyakinannya adalah 3/4 x 100% = 100%

7. Latihan Soal 2

Sebuah Supermarket Memiliki data transaksi sebagai berikut :

Gambar 1. Data Transaksi

Misal minimum dari nilai support pola frekuensi tinggi adalah 2.

Iterasi 1

Untuk 1-itemset hitung dan scan database untuk mendapatkan pola frequent dari support.

Gambar 2. Itemset

Dapatkan k-itemset dari support yang memenuhi minimum support, kemudian pilih k-itemset sebagai pola frequent tinggi.

Gambar 3. Pola Frequent

Iterasi 2

Pada iterasi sebelumnya pola frequent dari support telah didapatkan dari 1-itemset, untuk 2-itemset, generate k-itemset dari k-itemset iterasi sebelumnya, dengan melakukan kombinasi dari k-itemset tersebut.

Gambar 4. kombinasi dari k-itemset

C2 adalah itemset dari kombinasi k-itemset dari iterasi sebelumnya, setelah didapatkan k-itemset tersebut, hitung masing-masing item frequent dan scan database dan dapatkan frequent item dari support.

Gambar 5. 2-Itemset

Pengembangan algoritma apriori dengan memangkas k-itemset dengan menghitung suppport dari itemset, salah satu itemset yang tidak muncul dalam database {telur,buncis} dari C2, sehingga dipangkas menjadi lebih menghemat memory.

Iterasi 3

Gambar 6. Kombinasi dari K-Itemset

Gambar 7. 3-itemset dari scan database

Kandidat 3-itemset yang telah memenuhi minimum support, itemset tersebut akan menjadi acuan untuk k-itemset selanjutnya

Iterasi 4

Scan dabatase untuk mendapatkan itemset dari support, itemset yang memenuhi minimum support dipilih sebagai pola frequent tinggi

Gambar 8. Pola Frequent Tinggi

Tidak ada lagi kombinasi yang bisa dibentuk untuk k-itemset berikutnya, proses berhenti, pola frequent tinggi yang ditemukan adalah “roti,mentega,telur,susu”. Langkah berikutnya, bentuk association rules yang memenuhi syarat minimum dengan menghitung confidence association rules A->B

Pembentukan Aturan Assosiatif :

Gambar 9. Aturan Assosiatif

Pembentukan aturan assosiatif cukup penting untuk mendapatkan dan menghitung nilai confidence. perlu diketahui algoritma apriori cukup boros dalam penggunaan memory dan paling banyak menghabiskan waktu saat scanning.

8. Latihan Soal 3

Golden rule / threshold / minimum support = 2

Latihan Soal 3

9. Latihan Soal 4

Ada transaksi seperti yang terlihat dibawah ini.

latihan-soal-apriori-1

1. Pisahkan masing-masing item yang dibeli

latihan-soal-apriori-2

2. Kemudian Buat Tabel seperti dibawah ini:

latihan-soal-apriori-3

3. Kemudian hitung jumlah banyaknya pembelian untuk setiap item.

latihan-soal-apriori-4

4. Tentukan Ф.
Misalkan kita tentukan Ф = 3, maka kita dapat menentukan frekuen itemset. Dari tabel di atas diketahui total Ф untuk transaksi k = 1, semuanya lebih besar dari Ф. Maka:

F1 = {{A}, {B}, {C}, {D}, {E}, {F}, {G}}

Untuk k = 2 (2 unsur), diperlukan tabel untuk tiap-tiap pasang item. Himpunan yang mungkin terbentuk adalah: {A,B}, {A,C}, {A,D}, {A,E}, {A,F}, {A,G}, {B,C}, {B,D}, {B,E}, {B,F}, {B,G}, {C,D}, {C,E}, {C,F}, {C,G}, {D,E},{D,F}, {D,G}, {E,F}, {E,G}, {F,G}.

Tabel-tabel untuk calon 2 item set:

latihan-soal-apriori-5

latihan-soal-apriori-6

Dari tabel-tabel 2 unsur di atas, P artinya item-item yang dijual bersamaan, sedangkan S berarti tidak ada item yang dijual bersamaan atau tidak terjadi transaksi. Σ melambangkan jumlah Frekuensi item set. Jumlah frekuensi item set harus lebih besar atau sama dengan jumlah Frekuensi item set (Σ >= Ф). Dari tabel diatas, maka didapat:

F2 = {{A,B}, {A,F}, {B,D}, {B,F}, {B,G}, {D,G}

Kombinasi dari itemset dalam F2, dapat kita gabungkan menjadi calon 3-itemset. Itemset-itemset yang dapat digabungkan adalah itemset-itemset yang memiliki kesamaan dalam k-1 item pertama. Misalnya {A,B} dan {A,F} memiliki itemset k-1 pertama yg sama, yaitu A, maka dapat digabungkan menjadi 3-itemset baru yaitu {A, B, F}. Untuk k = 3 (3 unsur), himpunan yang mungkin terbentuk adalah: {A, B, F}, {B, D, F}, {B, D,G}, {B, F, G}.

latihan-soal-apriori-7

Dari tabel-tabel di atas, didapat F3 = { }, karena tidak ada Σ >= Ф sehingga F4, F5, F6 dan F7 juga merupakan himpunan kosong.

5. Rule yang dipakai adalah if x then y, dimana x adalah antecendent dan y adalah consequent. Berdasarkan rule tersebut, maka dibutuhkan 2 buah item yang mana salah satunya sebagai antecedent dan sisanya sebagai consequent. Dari langkah 4 didapat 1 buah Fk yaitu F2. F1 tidak disertakan karena hanya terdiri dari 1 item saja. Untuk antecedent boleh lebih dari 1 unsur, sedangkan untuk consequent terdiri dari 1 unsur.

6. Tentukan (ss-s) sebagai antecedent dan s sebagai consequent dari Fk yang telah di dapat berdasarkan rule pada langkah 5. Pada F2 didapat himpunan F2 = {{A,B}, {A,F}, {B,D}, {B,F}, {B,G}, {D,G} Maka dapat disusun:

• Untuk {A,B}:
– Jika (ss-s) = A, Jika s = B, Maka -> If buy A then buy B
– Jika (ss-s) = B, Jika s = A, Maka -> If buy B then buy A
• Untuk {A,F}:
– Jika (ss-s) = A, Jika s = F, Maka -> If buy A then buy F
– Jika (ss-s) = F, Jika s = A, Maka -> If buy F then buy A
• Untuk {B,D}:
– Jika (ss-s) = B, Jika s = D, Maka -> If buy B then buy D
– Jika (ss-s) = D, Jika s = B, Maka -> If buy D then buy B
• Untuk {B,F}:
– Jika (ss-s) = B, Jika s = F, Maka -> If buy B then buy F
– Jika (ss-s) = F, Jika s = B, Maka -> If buy F then buy B
• Untuk {B,G}:
– Jika (ss-s) = B, Jika s = G, Maka -> If buy B then buy G
– Jika (ss-s) = G, Jika s = B, Maka -> If buy G then buy B
• Untuk {D,G}:
– Jika (ss-s) = D, Jika s = G, Maka -> If buy D then buy G
– Jika (ss-s) = G, Jika s = D, Maka -> If buy G then buy D

7. Dari langkah 6, kita mendapatkan 12 rule yang dapat digunakan yaitu
• If buy A then buy B
• If buy B then buy A
• If buy A then buy F
• If buy F then buy A
• If buy B then buy D
• If buy D then buy B
• If buy B then buy F
• If buy F then buy B
• If buy B then buy G
• If buy G then buy B
• If buy D then buy G
• If buy G then buy D

8. Dari langkah 7 dibuat tabel kandidat asosiasi rule untuk 1 antecedent

latihan-soal-apriori-8

9. Hitung support dan confidence.

formula-apriori

Untuk Σ item yang dibeli sekaligus pada If buy A then buy B, ada 3 transaksi. Jumlah seluruh transaksi adalah 10 transaksi, sehingga support-nya adalah:

SUPPORT = 3/10 x 100% = 33,33%

Untuk Σ item yang dibeli sekaligus pada If buy A then buy B, ada 3 transaksi, sedangkan jumlah transaksi yang membeli A adalah 4 transaksi, sehingga confidence-nya adalah:

CONFIDENCE = 3/4 x 100% = 75%

Sehingga di dapat tabel sbb:

latihan-soal-apriori-9

10. Setelah di dapat support dan confidence untuk masing-masing kandidat, lakukan perkalian antara support dan confidence, dimana confidence-nya diambil 70% ke atas, sehingga di dapat tabel sbb:

latihan-soal-apriori-10

11. Setelah didapat hasil perkalian antara support dan confidence, pilihlah yang hasil perkaliannya paling besar. Hasil paling besar dari perkalian perkalian tersebut merupakan rule yang dipakai pada saat menjual. Karena hasil perkalian dari ke-4 penjualan diatas bernilai sama, maka semuanya bisa dijadikan rule.
– Jika membeli A maka akan membeli B dengan support 33,33% dan confidence 75%
– Jika membeli A maka akan membeli F dengan support 33,33% dan confidence 75%
– Jika membeli F maka akan membeli A dengan support 33,33% dan confidence 75%
– Jika membeli F maka akan membeli B dengan support 33,33% dan confidence 75%

Semoga artikel berjudul “Algoritma Apriori (Association Rule)” bisa bermanfaat dan silahkan jika masih ada yang kurang jelas dapat ditanyakan di kolom komentar dibawah ini.

Silahkan Like Fanspage dan Share artikel ini jika menurut kamu bermanfaat untuk kamu dan orang lain.

Artikel Lainnya