Algoritma Apriori: Pengertian, Cara Kerja, Kelebihan, dan Kekurangannya

Algoritma Apriori merupakan salah satu algoritma unsupervised pada data mining, khususnya pada tugas asosiasi. Asosiasi adalah proses menyelidiki hubungan antara satu objek data dengan objek lainnya dalam dataset.

Pada artikel ini kita akan membahas lebih lanjut mengenai algoritma Apriori, dari pengertian, cara kerja, hingga aplikasinya. Simak, ya!

Daftar Isi

Pengertian Algoritma Apriori

Algoritma Apriori adalah algoritma yang digunakan untuk menghitung aturan asosiasi antar objek. Aturan asosiasi menjelaskan bagaimana dua atau lebih objek terkait satu sama lain.

Dengan kata lain, algoritma apriori adalah algoritma berbasis aturan asosiasi yang menganalisis apakah orang yang membeli produk A juga membeli produk B.

Algoritma ini dikemukakan oleh ilmuwan R. Agrawal dan Srikant pada tahun 1994. Algoritma ini kebanyakan digunakan untuk analisis keranjang belanja dan membantu menemukan produk yang dapat dibeli bersama.

Apriori juga dapat digunakan di bidang perawatan kesehatan untuk menemukan reaksi obat untuk pasien.

Pada data mining, algoritma Apriori banyak digunakan untuk menemukan data yang paling sering muncul dalam sebuah database. Item data transaksi pada database membentuk itemset.

Itemset yang paling sering muncul dipilih oleh algoritma Apriori agar dapat digunakan untuk menentukan aturan asosiasi yang menyoroti tren umum dalam database.

Cara Kerja Algoritma Apriori

Untuk menentukan itemset yang paling sering muncul, algoritma Apriori menggunakan pendekatan "bottom-up".

Pendekatan ini menggunakan Breadth-first search dan struktur data Hash tree untuk menghitung kandidat itemset secara efisien.

Sumber: medium.com

Pendekatan bottom up dimulai dari setiap item dalam daftar itemset. Kemudian, kandidat dibentuk dengan self-join (penggabungan). Setiap iterasi, kita memperluas panjang itemset satu item yang membentuk subhimpunan.

Setelah itu dilakukan proses pengujian terhadap subhimpunan. Apabila ditemukan itemset yang berisi subhimpunan yang jarang, maka dilakukan pruning (pemangkasan). Proses dilakukan secara berulang-ulang sampai tidak ada lagi itemset yang berhasil diturunkan dari data.

Langkah-langkah Algoritma Apriori

Berikut ini adalah langkah-langkah dari algoritma Apriori:

Hitung support dari itemset (dengan ukuran k = 1) dalam database. Proses ini akan menghasilkan himpunan kandidat.
Pangkas (pruning) kumpulan kandidat dengan cara menghilangkan item yang memiliki support lebih kecil dari ambang batas (threshold) yang diberikan.
Gabungkan itemset yang paling sering muncul untuk membentuk himpunan berukuran k + 1, dan ulangi himpunan di atas sampai tidak ada lagi itemset yang dapat dibentuk.

Komponen-komponen pada Algoritma Apriori

Pada algoritma Apriori, terdapat 3 komponen penting, yaitu:

Support
Confidence
Lift

Untuk memudahkan penjelasan ketiga komponen tersebut, kita gunakan contoh studi kasus.

Misalkan kita punya 2000 data transaksi pembelian pada sebuah minimarket A. Dari 2000 transaksi tersebut, ada 200 pembelian kopi sachet, dan 500 pembelian minyak goreng.

Dari 500 transaksi pembelian minyak goreng, ada 100 transaksi gabungan antara pembelian kopi sachet dan minyak goreng.

Kita akan coba hitung nilai support, confidence dan lift dari data transaksi tersebut

1. Support

Support menunjukkan popularitas rata-rata produk atau item dalam database. Kita bisa mendapatkan nilai support dengan membagi jumlah total transaksi yang mengandung produk itu dengan jumlah total transaksi.

Misalkan kita ingin menghitung nilai support dari produk kopi sachet, maka rumusnya

Support(kopi) = jumlah transaksi kopi / total transaksi semua produk

Support(kopi) = 200/2000 = 0.1 = 10%

Selanjutnya untuk menghitung nilai support dari produk minyak goreng adalah:

Support(minyak) = jumlah transaksi minyak / total transaksi semua produk

Support(minyak) = 500 / 2000 = 0.4 = 40%

Terakhir nilai support dari kombinasi keduanya yaitu:

Support(kopi dan minyak) = jumlah transaksi kombinasi kopi dan minyak / total transaksi semua produk

Support(kopi dan minyak) = 100 / 2000 = 0.05 = 5%

2. Confidence

Confidence mengacu pada kemungkinan seorang pelanggan membeli kopi sachet dan minyak goreng secara bersamaan.

Untuk menghitung nilai confidence kita perlu membagi jumlah transaksi kombinasi kopi sachet dan minyak goreng dengan jumlah total transaksi kopi.

Rumusnya:

Confidence = jumlah transaksi kombinasi kopi dan minyak / total transaksi kopi

Confidence = 100/200 = 0.5 = 50%

3. Lift

Lift adalah peningkatan rasio penjualan kopi saat kita menjual minyak goreng.

Untuk mendapatkan nilai lift kita dapat menggunakan perhitungan berikut:

Lift = support(kopi dan minyak) / (support(kopi) * support(minyak))

Lift = 0.05 / (0.1 * 0.4) = 1.25

Artinya ketika kita menjual kopi sachet bersama-sama dengan minyak goreng, kemungkinan seseorang membeli keduanya adalah 1.25 kali dibandingkan membeli secara terpisah.

Apabila nilai lift di bawah satu, maka menandakan bahwa pelanggan jarang membeli kedua barang tersebut secara bersamaan.

Sebaliknya, semakin besar nilainya, maka semakin baik kombinasinya dan pelanggan sering membelinya secara bersamaan.

Kelebihan Algoritma Apriori

Adapun kelebihan dari algoritma Apriori adalah sebagai berikut:

Sederhana dan mudah dipahami di antara algoritma asosiasi
Aturan yang dihasilkan intuitif dan mudah dikomunikasikan ke pengguna awam
Tidak memerlukan data berlabel karena merupakan algoritma unsupervised
Algoritmanya lengkap, sehingga dapat menemukan semua aturan dengan support dan confidence yang ditentukan

Kekurangan Algoritma Apriori

Kelemahan dari algoritma apriori di antaranya:

Membutuhkan banyak perhitungan jika itemset sangat besar dan nilai support minimal dipertahankan seminimal mungkin.
Perlu melakukan pemindaian penuh seluruh database. Hal ini membuat proses pada algoritma Apriori berjalan sangat lama dan lambat serta menghabiskan banyak sumber daya.
Karena perlu melakukan pemindaian penuh, kompleksitas waktu dan ruang dari algoritma apriori adalah O(2D), yang berarti sangat tinggi. Simbol D mewakili lebar horizontal yang ada dalam database.

Penutup

Demikian penjelasan singkat mengenai algoritma Apriori. Terima kasih telah membaca tulisan ini dengan tuntas. Semoga paparan di atas dapat membuat Anda lebih mudah memahami algoritma Apriori.

Apabila Anda tertarik dengan artikel serupa, Anda bisa mengunjungi rubrik Machine Learning atau membaca tulisan lainnya mengenai "Loss Function pada Machine Learning"

Referensi:

Trivusi