Algoritma Apriori: Perhitungan Support, Confidence, dan Lift
Tutorial ini membahas algoritma Apriori dan contoh perhitungannya untuk mencari pola hubungan antar-item pada data transaksi. Contoh yang digunakan adalah market basket analysis sederhana untuk mengetahui item yang sering dibeli bersamaan dan membentuk aturan asosiasi.
Perhitungan dilakukan mulai dari pembentukan kandidat itemset, pencarian frequent itemset berdasarkan minimum support, hingga pembentukan association rule menggunakan confidence dan lift.
Daftar Isi
- Pengertian Algoritma Apriori
- Rumus Support, Confidence, dan Lift
- Data Transaksi
- Minimum Support dan Minimum Confidence
- #01 Pembentukan C1 dan L1
- #02 Pembentukan C2 dan L2
- #03 Pembentukan C3 dan L3
- #04 Pembentukan Association Rule
- #05 Hasil Akhir
- FAQ Apriori
- Referensi
- Source Code Apriori
Pengertian Algoritma Apriori
Algoritma Apriori adalah algoritma data mining yang digunakan untuk menemukan frequent itemset atau kombinasi item yang sering muncul bersama dalam sekumpulan transaksi. Frequent itemset tersebut kemudian dapat digunakan untuk membentuk aturan asosiasi.
Salah satu penggunaan Apriori yang paling umum adalah market basket analysis, yaitu analisis pola pembelian konsumen berdasarkan item yang sering dibeli secara bersamaan.
Rumus Support, Confidence, dan Lift
Support
Support menunjukkan seberapa sering sebuah item atau kombinasi item muncul pada seluruh transaksi.
$$ Support(X) = \frac{\text{Jumlah transaksi yang mengandung } X} {\text{Jumlah seluruh transaksi}} \times 100\% $$
Confidence
Confidence menunjukkan seberapa besar kemungkinan item Y muncul ketika item X muncul.
$$ Confidence(X \rightarrow Y) = \frac{Support(X \cup Y)} {Support(X)} \times 100\% $$
Lift
Lift digunakan untuk mengukur kekuatan hubungan antara antecedent dan consequent.
$$ Lift(X \rightarrow Y) = \frac{Confidence(X \rightarrow Y)} {Support(Y)} $$
- Lift > 1: hubungan positif.
- Lift = 1: hubungan cenderung independen.
- Lift < 1: hubungan negatif.
Data Transaksi
Contoh menggunakan 10 transaksi dengan item Roti, Susu, Telur, Kopi, dan Gula.
| Transaksi | Item |
|---|---|
| T1 | Roti, Susu, Telur |
| T2 | Roti, Susu |
| T3 | Roti, Kopi, Gula |
| T4 | Susu, Telur |
| T5 | Roti, Susu, Telur |
| T6 | Roti, Susu, Kopi |
| T7 | Susu, Kopi, Gula |
| T8 | Roti, Susu, Telur, Kopi |
| T9 | Roti, Telur |
| T10 | Susu, Telur, Gula |
Minimum Support dan Minimum Confidence
- Minimum Support = 30%
- Minimum Confidence = 60%
Itemset dinyatakan frequent jika nilai support-nya minimal 30%. Aturan asosiasi diterima jika confidence-nya minimal 60%.
#01 Pembentukan C1 dan L1
C1 adalah seluruh kandidat 1-itemset. Support setiap item dihitung berdasarkan jumlah transaksi yang mengandung item tersebut.
| Itemset | Jumlah | Perhitungan Support | Support | Status |
|---|---|---|---|---|
| {Gula} | 3 | 3/10 × 100% | 30% | Lolos |
| {Kopi} | 4 | 4/10 × 100% | 40% | Lolos |
| {Roti} | 7 | 7/10 × 100% | 70% | Lolos |
| {Susu} | 8 | 8/10 × 100% | 80% | Lolos |
| {Telur} | 6 | 6/10 × 100% | 60% | Lolos |
Frequent 1-itemset (L1) yang memenuhi minimum support:
| L1 | Support |
|---|---|
| {Gula} | 30% |
| {Kopi} | 40% |
| {Roti} | 70% |
| {Susu} | 80% |
| {Telur} | 60% |
#02 Pembentukan C2 dan L2
C2 dibentuk dengan mengombinasikan item-item yang lolos pada L1 menjadi pasangan 2-itemset. Support kemudian dihitung kembali untuk setiap pasangan.
| Itemset | Jumlah | Perhitungan Support | Support | Status |
|---|---|---|---|---|
| {Gula, Kopi} | 2 | 2/10 × 100% | 20% | Tidak Lolos |
| {Gula, Roti} | 1 | 1/10 × 100% | 10% | Tidak Lolos |
| {Gula, Susu} | 2 | 2/10 × 100% | 20% | Tidak Lolos |
| {Gula, Telur} | 1 | 1/10 × 100% | 10% | Tidak Lolos |
| {Kopi, Roti} | 3 | 3/10 × 100% | 30% | Lolos |
| {Kopi, Susu} | 3 | 3/10 × 100% | 30% | Lolos |
| {Kopi, Telur} | 1 | 1/10 × 100% | 10% | Tidak Lolos |
| {Roti, Susu} | 5 | 5/10 × 100% | 50% | Lolos |
| {Roti, Telur} | 4 | 4/10 × 100% | 40% | Lolos |
| {Susu, Telur} | 5 | 5/10 × 100% | 50% | Lolos |
Frequent 2-itemset (L2) yang memenuhi minimum support:
| L2 | Support |
|---|---|
| {Kopi, Roti} | 30% |
| {Kopi, Susu} | 30% |
| {Roti, Susu} | 50% |
| {Roti, Telur} | 40% |
| {Susu, Telur} | 50% |
#03 Pembentukan C3 dan L3
Kandidat 3-itemset dibentuk dari kombinasi item yang seluruh subset 2-itemset-nya telah lolos pada L2. Prinsip ini merupakan proses pruning pada Apriori.
| Itemset | Jumlah | Perhitungan Support | Support | Status |
|---|---|---|---|---|
| {Kopi, Roti, Susu} | 2 | 2/10 × 100% | 20% | Tidak Lolos |
| {Roti, Susu, Telur} | 3 | 3/10 × 100% | 30% | Lolos |
Frequent 3-itemset (L3) yang memenuhi minimum support:
| L3 | Support |
|---|---|
| {Roti, Susu, Telur} | 30% |
Pada data contoh ini, frequent itemset terbesar yang ditemukan adalah 3-itemset.
#04 Pembentukan Association Rule
Association rule dibentuk dari frequent itemset yang memiliki minimal dua item. Setiap aturan kemudian diuji menggunakan minimum confidence 60%.
| No | Aturan | Support | Confidence | Lift | Interpretasi Lift |
|---|---|---|---|---|---|
| 1 | {Telur} → {Susu} | 50% | 83.33% | 1.0417 | Hubungan positif |
| 2 | {Kopi} → {Roti} | 30% | 75% | 1.0714 | Hubungan positif |
| 3 | {Kopi} → {Susu} | 30% | 75% | 0.9375 | Hubungan negatif |
| 4 | {Roti, Telur} → {Susu} | 30% | 75% | 0.9375 | Hubungan negatif |
| 5 | {Roti} → {Susu} | 50% | 71.43% | 0.8929 | Hubungan negatif |
| 6 | {Telur} → {Roti} | 40% | 66.67% | 0.9524 | Hubungan negatif |
| 7 | {Susu} → {Telur} | 50% | 62.5% | 1.0417 | Hubungan positif |
| 8 | {Susu} → {Roti} | 50% | 62.5% | 0.8929 | Hubungan negatif |
| 9 | {Roti, Susu} → {Telur} | 30% | 60% | 1 | Independen |
| 10 | {Susu, Telur} → {Roti} | 30% | 60% | 0.8571 | Hubungan negatif |
Contoh Perhitungan Confidence
Misalnya aturan {Telur} → {Susu}.
$$ Confidence = \frac{5}{6} \times 100\% = 83.33\% $$
Karena nilai confidence tersebut lebih besar atau sama dengan minimum confidence 60%, aturan dinyatakan memenuhi syarat.
#05 Hasil Akhir Apriori
Dari aturan yang memenuhi minimum confidence, aturan dengan nilai lift terbesar adalah {Kopi} → {Roti} dengan support 30%, confidence 75%, dan lift 1.0714.
Nilai lift lebih besar dari 1 menunjukkan adanya hubungan positif antara antecedent dan consequent.
Ringkasan
Algoritma Apriori mencari pola item yang sering muncul bersama melalui proses pembentukan kandidat dan penyaringan berdasarkan minimum support. Frequent itemset yang terbentuk kemudian digunakan untuk membuat association rule. Kualitas aturan dapat dianalisis menggunakan confidence dan lift.
FAQ Apriori
Apa fungsi minimum support?
Minimum support digunakan untuk menentukan batas minimal kemunculan suatu itemset agar dianggap sering muncul atau frequent.
Apa fungsi minimum confidence?
Minimum confidence digunakan untuk menentukan batas minimal tingkat kepercayaan sebuah association rule.
Apa perbedaan support dan confidence?
Support mengukur seberapa sering itemset muncul pada seluruh transaksi, sedangkan confidence mengukur seberapa sering consequent muncul ketika antecedent terjadi.
Mengapa lift penting?
Lift membantu menilai apakah hubungan antar-item benar-benar memberikan peningkatan kecenderungan. Nilai lift di atas 1 menunjukkan hubungan positif.
Kapan proses Apriori berhenti?
Proses berhenti ketika tidak ada lagi kandidat itemset baru yang dapat dibentuk atau tidak ada kandidat yang memenuhi minimum support.
Referensi
- Agrawal, R. & Srikant, R. (1994). Fast Algorithms for Mining Association Rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB).
- Han, J., Kamber, M. & Pei, J. (2012). Data Mining: Concepts and Techniques, 3rd Edition. Morgan Kaufmann.
Source Code Metode Apriori
Berikut adalah beberapa source code yang menggunakan algoritma Apriori, baik berbasis web maupun desktop.
Ada yang Ditanyakan?
Jika anda masih ada kesulitan atau kekeliruan tentang penjelasan metode di atas, bisa menghubungi kami lewat WA/Email sesuai halaman Kontak.
Jika ingin memiliki file excel dari metode di atas bisa melihat cara download di halaman Download.
Jika ingin memiliki source code dari metode di atas, baik berbasis web maupun desktop bisa melihat daftar harga donasi di halaman Daftar Source Code.
Donasi ini digunakan oleh penulis untuk membayar server dan membeli kopi sembari membuat tutorial Metode/Algoritma lainnya :).
