Algoritma Apriori merupakan sebuah algoritma pencarian pola dalam teknik data mining untuk menumukan aturan assosiatif antara suatu kombinasi item-set yang mempunyai suatu nilai keseringan tertentu sesuai kriteria atau filter yang di inginkan.
Algoritma ini pertama kali diperkenalkan oleh R. Agarwal dan R Srikant pada tahun 1994 untuk mencari frekuensi tertinggi dari suatu database.
Nah, pada kesempatan ini kita akan belajar lebih dalam mengenai Algoritma Apriori dari pengertian, cara kerja, rumus dan contoh penerapannya.
Pengertian Algoritma Apriori
Algoritma Apriori adalah salah satu bagian dari sebuah metode Association Rule pada data mining yang berfungsi untuk mencari frequent item ( itemset ) pada transaksional database.
Association rule mining merupakan teknik data mining untuk menemukan aturan assosiatif antara suatu kombinasi item. Contoh analisis pembelian di suatuh market, dapat diketahui berapa besar kemungkinan seseorang pelanggan membeli roti bersamaan dengan susu.
Cara kerja Algoritma Apriori
Algoritma ini menggunakan pendekatan “button-up” untuk menentukan itemset paling sering muncul. Pendekatan ini menggunakan Breadth-firs search dan struktur data Hash tree untuk menghitung kandidat itemset secara efisien. Pendekatan bootom up dimulai dari setiap item dalam daftar itemset.
- Tentukan minimum support.
- 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 minum support, apabila telah memenuhi minimum support, 1-itemset tersebut akan menjadi pola frekuensi tinggi.
- Iterasi 2 : untuk mendapatkan 2-itemset, harus dilakukan kombinasi dari k-itemset sebelumnya, kemudian scan database lagi untuk menghitung item-item yang memuat support. itemset yang memenuhi minimum support akan dipilih sebagai pola frekuensi tinggi dari kandidat.
- Tetapkan nilai K-itemset dari support yang telah memenuhi minimum support dari K-itemset.
- Lakukan proses untuk iterasi selanjutnya hingga tidak ada lagi K-itemset yang memenuhi minum support.
Rumus Algoritma Apriori
Metodologi dasar analisis terbagi menjadi dua tahap yaitu.
1. Analisa Pola Frequensi tinggi
Tahapan ini mencari kombinasi item yang memenuhi syarat minimum dari nilai support dalam database. Nilai support sebuah item diperoleh dengan rumus sebagai berikut.
Sementara itu nilai support dari dua item diperoleh dari rumus sebagai berikut.
Proses untuk mendapatkan frekuensi itemset yaitu.
- Join (penggabungan), proses ini dilakukan dengan cara pengkombinasian item dengan item yang lainnya hingga tidak dapat terbentuk kombinasi lagi.
- Prune (pemangkasan), hasil dari item yang telah dikombinasikan kemudian dipangkas dengan menggunakan minimum support yang telah ditentukan oleh pengguna.
2. Pembentukan Aturan Asosiasi
Setelah semua pola frekuensi tinggi ditemukan, barulah cari aturan asosiasi yang memenuhi syarat minimum untuk confidence dengan menghitung confidence aturan assosiatif A → B. Nilai confidence dari hasil aturan A → B diperoleh dari rumus berikut.
Istilah-Istilah Terdapat Pada Association Rule
Adapun istilah-istilah terdapat pada association rule sebagai berikut.
- E adalah himpunan yang akan diteliti. Contoh { asparagus, kacang polong, .., tomat }.
- D adalah himpunan seluruh transaksi yang akan digunakan. Contoh {Transaksi 1, transaksi 2, …, transaksi 14}.
- Proper subset adalah himpunan bagian murni. Contoh ada himpunan A = { a, b, c}, Proper subsetnya ialah himpunan 1 unsur dan himpunan 2 unsur. Untuk lebih jelas berikut penjelasan dari himpunan A.
- Himpunan kosong = {}.
- Himpunan 1 unsur = { a }, { b }, { c }.
- Himpunan 2 unsur = { a, b }, { a, c }, { b, c }
- Himpunan 3 unsur = { a, b, c }
- Itemset adalah himpunan item atau item-item di E. Contoh ada suatu himpunan E = { a, b, c } item setnya adalah { a }; { b }; { c }; { a, b }; { a, c }; { b,c }.
- K-itemset adalah itemset 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 }.
- Itemset frekuensi adalah jumlah transaksi di I yang mengandung jumlah itemset tertentu. Intinya jumlah transaksi yang membeli suatu itemset, contoh.
- Frekuensi item set yang sekaligus membali kacang polong dan brokoli adalah 3.
- Frekuensi item set yang membeli sekaligus membeli kacang polong, labu dan tomat adalah 2.
- Frekuen itemset adalah itemset yang muncul sekurang-kurangnya “sekian” kali di D ( minimum support ). Kata “sekian” minimum dalam suatu transaksi.
- Fk atau K-itemset adalah himpunan semua frekuen itemset yang terdiri dari K item. Contoh beras, telur, minyak adalah 3 itemset ( dinotasikan sebagai K-itemset )
Kelebihan Algoritma Apriori
- Aturan yang dihasilkan intuitif dan mudah dikomunikasikan ke pengguna awam.
- Sederhana dan mudah dipahami di antara algoritma asosiasi.
- Tidak memerlukan data berlabel karena merupakan algoritma unsepersived.
- Dapat menemukan semua aturan dengan support dan confidence yang ditentukan.
Kekurangan Algoritma Apriori
- Perlu melakukan pemindaian penuh seluruh database. Hal ini membuat proses pada algoritma apriori berjalan sangat lama dan lambat serta menghabisakan banyak sumber daya.
- Membutuhkan banyak perhitungan jika itemset sangat besar dan nilai support minimal dipertahankan seminimal mungkin.
- Karena perlu melakukan pemindaian penuh, kompleksitas waktu dan ruang dari algoritma apriori adalah O (2D) yang berarti sangat tinggi. Simbol D emwakili lebar horizontal yang ada dalam database.
Contoh Penerapan Algoritma Apriori
- Bidang Kesehatan, digunakan untuk menemukan reaksi obat untuk pasien.
- Ecommerce, digunakan untuk menganalisis keranjang belanja dan membantu menemukan produk yang dapat dibeli bersama.
- Auto Complate, fitur yang digunakan salah satunya saat pengguna mengetikan suatu kata, program akan menampilkan daftar kata-kata berikutnya, yang paling banyak memiliki assosiai pada kata yang diketik.
- Restoran, digunakan oleh restoran cepat saji dalam menentukan paket menu makanan atau minuman yang ada direstoran mereka berdasarkan pola beli konsumen.
Kesimpulan
Algoritma Apriori adalah algoritma yang digunakan dalam data mining untuk menemukan pola asosiasi dalam kumpulan data. Algoritma ini bekerja dengan mencari item-item yang sering muncul bersama dalam transaksi atau dataset, sehingga dapat membantu mengidentifikasi hubungan atau asosiasi antara item-item tersebut.
Keunggulan utama dari Algoritma Apriori adalah kemampuannya untuk mengatasi dataset yang besar dan kompleks. Dengan cara ini, algoritma ini dapat digunakan dalam berbagai aplikasi, seperti analisis pembelian pelanggan, rekomendasi produk dan pemahaman perilaku konsumen.
Namun, penting untuk dicatat bahwa Algoritma Apriori juga memiliki beberapa keterbatasan, termasuk penggunaan sumber daya komputasi yang signifikan dan sensitivitas terhadap jumlah item yang besar dalam dataset. Oleh karena itu, pemilihan parameter yang tepat dan pemahaman yang baik tentang data yang digunakan sangat penting dalam mengimplementasikan Algoritma Apriori.
Artikel ini merupakan bagian dari seri artikel belajar Kecerdasan Buatan dan jika ada ide topik yang mau kami bahas silahkan komen di bawah ya..
