Algoritma Apriori

Algoritma Apriori

Algoritma Apriori

Pengertian Algoritma Apriori

Algoritma Apriori adalah bagian dari sebuah metode Association Rule, yang berfungsi untuk menemukan kombinasi item berdasarkan barang yang dibeli oleh pelanggan. Berikut adalah jenis-jenis aturan asosiasi 
  • A priori
  • Generalized Rule Induction
  • Algoritma Hash Based

Association rule mining merupakan teknik data mining untuk menemukan aturan asosiatif antara suatu kombinasi item.contohnya Analisis pembelian di suatu pasar swalayan, dapat diketahui brp besar kemungkinan seorang pelanggan membeli roti bersamaan dengan susu. Dengan kondisi tersebut pemilik swalayan dpt mengatur penempatan barangnya, atau merancang promosi pemasaran dengan memakai kupon diskon utk kombinasi barang tertentu.

Association Rule menjadi terkenal karena aplikasinya utk menganalisis isi keranjang belanja pelanggan di pasar swalayan, Makanya itu sering disebut Market Basket Analysis.
Association Rule juga dikenal salah satu teknik DM yang menjadi dasar dari berbagai teknik DM lainnya

Salah satu tahap analisis asosiasi yang menarik perhatian banyak peneliti untuk menghasilkan algoritma yang efisien adalah analisis pola frekuensi tinggi (frequent pattern mining). Penting tidaknya suatu aturan asosiatif dapat diketahui dgn dua parameter :
  • Support (nilai penunjang)     =  Persentase kombinasi item tsb dlm database.
  • Confidence (nilai kepastian) =  Kuatnya hubungan antar item dalam aturan asosiasi


Contoh :

{roti, mentega}→ {susu} (support=40%, confidence = 50%)

Aturan tersebut artinya ...
  • 50% dari transaksi database yang memuat item roti dan mentega juga membeli susu. 40% dari seluruh transaksi yang ada daii database memuat ketiga item tersebut.
  • “Seorang pelanggan yg membeli roti dan mentega punya kemungkinan 50% untuk juga membeli susu. Aturan tersebut cukup signifikan karena mewakili 40% dari catatan transaksi selama ini”

Metodologi Dasar Analisis Asosiasi

1. Analisis Pola Frekuensi Tinggi

Tahap ini mencari kombinasi item yg memenuhi syarat minimmum dari nilai support dalam database. Nilai support sebuah item diperoleh dengan rumus sbb:

  • Nilai support dari 2 item diperoleh dari rumus 2 berikut:
Support (A,B) = P(A ∩ B)



Sebagai contoh, terdapat database dari transaksi belanja pasar swalayan sbb:


Transaksi
Algoritma A priori


Representasi dalam bentuk database transaksiaonal
Algoritma A priori

Algoritma A priori

Format Tabular
Algoritma A priori


Misalkan,
  • D adalah himpunan transaksi yg dipresentasikan dlm tabel “Transaksi” diatas
  • Dimana setiap transaksi T dalam D mempresentasikan himpunan item yg berada dalam I
  • I adalah himpunan item yg dijual {teh, gula, kopi, susu, roti}
  • Jika kita memiliki himpunan item A (misal Susu dan Gula) dan himpunan lain B (Misal Kopi)

Maka atusan asosiasi akan berbentuk:
  • Dimana antecedent A dan consequent B merupakan subset dari I, dan A dan B merupakan mutually exclusive di mana aturan:
Jika A, maka B tidak berarti Jika B, maka A
  • Definisi diatas tidak berlaku untuk aturan trivial seperti: Jika Beans dan Squash, maka Beans
  • Seorang analis mungkin saja 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 analis menginginkan aturan yang memiliki support lebih dari 20% dan confidence lebih dari 35%.
  • Sebuah itemset adalah himpunan item-item yabg ada dalam I
  • k-itemset adalah itemset yang berisi k item, misalnya:
- {Teh, Gula} adalah sebuah 2-itemset
- {Teh, Gula, Roti} merupakan 3-itemset
  • Frequent Itemset menunjukkan itemset yang memiliki frekuensi kemunculan l
  • 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

Calon 2-itemset


Algoritma A priori

Dari data tersebut, jika ditetapkan nilai Φ =2, maka:
F2 = {{Teh, Gula}, {Gula, Kopi},
        {Gula, Susu}, {Gula, Roti},
        {Kopi, Susu}, {Susu, Roti}}


Calon 3-itemset
Algoritma A priori
Dari calon 3-itemset dari tabel tersebut. 
Terpilih F3 = {{Gula, Susu, Kopi}}
karena hanya kombinasi tersebut 
yang memiliki 
Frekuensi kemunculan >= Φ

2. Pembentukkan Aturan Asosiasi

  • Setelah semua pola frekuensi tinggi ditemukan, kemudian dicari aturan asosiasi yang memenuhi syarat minimum untuk confidence dengan menghitung confidence aturan asosiatif A → B
  • Nilai confidence dari aturan A → B diperoleh dari rumus berikut:

  • Dari F3 yang telah ditemukan, dapat dilihat besarnya nilai support dan confidence dari calon aturan asosiasi.
Algoritma A priori

  • Misalnya, ditetapkan nilai confidence minimal 60%, maka aturan yang bisa terbentuk adalah dengan 2 antecedent berikut:

-Jika membeli Gula dan Kopi, maka akan membeli Susu
-Jika membeli Kopi dan Susu, maka akan membeli Gula

Transaksi
Algoritma A priori

Calon Aturan asosiasi dari F2
Algoritma A priori



Contoh Lain:
Algoritma A priori

Misalnya: Φ = 4, Support = 30 %, Confidence = 70 %
Algoritma A priori


Algoritma A priori

Misalnya: Φ = 4, Support = 30 %, Confidence = 70 % 
Algoritma A priori


Algoritma A priori

Hasilnya :

Φ = 4, Min. Support = 30 %, Min. Confidence = 70 %

Algoritma A priori


Perhitungan diatas adalah contoh perhitungan dalam algoritma Apriori, dimana fungsinya untuk menentukan kombinasi item barang seperti yang telah dijelaskan diatas.



Kata Kunci : Algoritma A priori, Algoritma A priori dalam associaton rule,pengertian algoritma apriori, Skripsi Teknik informatika, contoh skripsi.