Algoritma Apriori
- Diperkenalkan oleh
- Agrawal, R. & Srikant, R.
- Tahun
- 1994
- Jenis
- Frequent itemset and association rule mining algorithm
- Keluarga
- Machine learning
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Algoritma Apriori, yang diperkenalkan oleh Agrawal dan Srikant pada tahun 1994, merupakan metode fundamental untuk menemukan kumpulan item yang sering muncul (frequent itemsets) dan aturan asosiasi dalam basis data transaksional. Algoritma ini menggunakan pencarian bertahap (level-wise) dengan lebar pertama (breadth-first) yang dipandu oleh properti anti-monoton dari dukungan (support) untuk secara efisien menghitung semua kombinasi item yang sering muncul bersama di atas ambang batas minimum yang ditentukan pengguna, kemudian mengekstrak aturan jika-maka yang dapat diinterpretasikan dari pola-pola tersebut.
Intuisi di balik metode
Pertimbangkan basis data struk (struk belanja) supermarket. Wawasan Apriori adalah properti anti-monoton: jika sepasang produk jarang dibeli bersama, maka tidak ada himpunan yang lebih besar yang mengandung pasangan tersebut yang dapat sering muncul. Hal ini memungkinkan algoritma untuk memangkas ruang pencarian yang secara eksponensial besar dari kemungkinan kombinasi item dengan membangun kandidat lapis demi lapis — dimulai dengan item tunggal, kemudian pasangan, kemudian tripel — dan membuang kandidat apa pun yang subsetnya sudah diketahui tidak sering muncul, bahkan sebelum menghitungnya dalam data.
Sejarah
Rakesh Agrawal dan Ramakrishnan Srikant memperkenalkan algoritma Apriori di VLDB 1994, berdasarkan formulasi masalah penambangan aturan asosiasi oleh Agrawal dkk. pada tahun 1993. Nama tersebut mencerminkan wawasan utamanya: menggunakan pengetahuan sebelumnya tentang kumpulan item (k) yang sering muncul untuk memangkas kandidat pada tingkat k+1. Algoritma ini menjadi tolok ukur kanonik yang mengukur semua algoritma kumpulan item yang sering muncul berikutnya — termasuk FP-Growth (2000) dan Eclat — dan tetap menjadi bab standar dalam buku teks penambangan data dan pembelajaran mesin.
Kapan digunakan
Gunakan Apriori ketika tujuannya adalah untuk menemukan pola kemunculan bersama atau hubungan jika-maka dalam data transaksional atau data kehadiran item biner — analisis keranjang belanja (market basket analysis), ko-endorsement item survei, kemunculan bersama diagnosis medis, atau asosiasi istilah teks. Algoritma ini cocok untuk dataset berukuran sedang di mana transparansi dan interpretasi aturan keluaran menjadi prioritas. Jangan gunakan Apriori ketika basis data transaksi sangat besar (jutaan baris dengan katalog item yang luas), karena pemindaian basis data penuh yang berulang membuatnya lambat dibandingkan dengan FP-Growth; dalam kasus tersebut FP-Growth lebih disukai. Algoritma ini juga tidak sesuai untuk data numerik kontinu tanpa diskretisasi sebelumnya, dan tidak memodelkan arah atau kausalitas.
Batasan dan pertimbangan
- Pemindaian basis data penuh yang berulang membuatnya lambat pada dataset besar — FP-Growth seringkali lebih disukai pada skala besar.
- Menurunkan ambang batas dukungan dapat menghasilkan jumlah kumpulan item dan aturan yang eksponensial, sehingga menyulitkan interpretasi.
- Tidak menangkap urutan temporal, arah, atau hubungan kausal antar item.
- Hasil sensitif terhadap pilihan ambang batas dukungan dan keyakinan, yang memerlukan pengetahuan domain atau penyetelan sistematis.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menghasilkan aturan jika-maka yang sepenuhnya dapat diinterpretasikan dengan dukungan, keyakinan, dan lift yang terkuantifikasi.
- Properti pemangkasan anti-monoton membuat pencarian yang seharusnya eksponensial menjadi dapat dikelola.
- Tidak memerlukan pelabelan data sebelumnya; sepenuhnya tanpa pengawasan (unsupervised).
- Parameter ambang batas (dukungan, keyakinan) memberikan kontrol langsung kepada analis terhadap granularitas aturan.
- Aturan keluaran dapat ditindaklanjuti dan dapat dikomunikasikan kepada pemangku kepentingan non-teknis tanpa latar belakang algoritmik.
- Merupakan karya seminal, banyak dikutip, dan diimplementasikan di hampir setiap pustaka penambangan data utama.
Penerapan
- Analisis keranjang belanja (Market basket analysis): menemukan produk apa yang sering dibeli bersama untuk memandu tata letak rak dan promosi.
- Informatika medis: mengidentifikasi gejala, diagnosis, atau resep obat yang muncul bersama dalam catatan pasien.
- Penambangan penggunaan web (Web usage mining): menemukan halaman atau fitur apa yang cenderung dikunjungi atau diaktifkan pengguna bersama-sama.
- Analisis survei dan kuesioner: mendeteksi item atau respons skala apa yang secara sistematis disetujui bersama.
- Pemula sistem rekomendasi (Recommender system bootstrapping): menghasilkan asosiasi item kandidat sebelum menerapkan penyaringan kolaboratif (collaborative filtering).
- Deteksi penipuan (Fraud detection): mengungkap pola kemunculan bersama yang tidak biasa dalam log transaksi yang menyimpang dari keranjang normal.
Cara kerjanya
Cara kerjanya
Analis memilih dua ambang batas sebelum menjalankan algoritma: dukungan minimum (proporsi transaksi yang harus berisi kumpulan item tertentu agar dianggap sering muncul) dan keyakinan minimum (probabilitas kondisional yang diperlukan agar aturan jika-maka dipertahankan). Kedua nilai ini mengontrol volume dan kekhususan keluaran dan harus dikalibrasi melalui pengetahuan domain atau uji coba eksploratif.
Algoritma melakukan satu pemindaian penuh basis data transaksi untuk menghitung seberapa sering setiap item individual muncul. Hanya item yang dukungannya memenuhi atau melebihi ambang batas dukungan minimum yang disimpan; sisanya dibuang. Kumpulan item tunggal yang sering muncul ini membentuk tingkat kandidat pertama.
Rumus
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}Kumpulan item yang sering muncul yang ditemukan pada tingkat k digabungkan berpasangan untuk membentuk kumpulan item kandidat berukuran k+1. Hanya pasangan yang berbagi k-1 item pertama yang digabungkan, sebuah aturan yang menjaga kumpulan kandidat tetap ringkas. Pemindaian basis data baru menghitung dukungan setiap kandidat.
Sebelum menghitung, setiap kandidat berukuran k+1 diperiksa terhadap semua subset (k)-nya. Jika ada subset yang tidak sering muncul pada tingkat sebelumnya, kandidat tersebut segera dipangkas tanpa membaca data, memanfaatkan properti anti-monoton untuk mengurangi komputasi. Kandidat yang lolos dari langkah pemangkasan ini membentuk tingkat kumpulan item yang sering muncul berikutnya.
Dari setiap kumpulan item yang sering muncul berukuran dua atau lebih, semua kemungkinan aturan jika-maka dihasilkan dengan mempartisi item menjadi anteseden dan konsekuen. Setiap aturan dievaluasi berdasarkan keyakinan — proporsi transaksi anteseden yang juga berisi konsekuen. Aturan di bawah keyakinan minimum dibuang.
Rumus
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}Aturan yang bertahan diurutkan berdasarkan lift, yang membandingkan keyakinan yang diamati dengan frekuensi dasar konsekuen. Lift di atas 1 menandakan bahwa anteseden dan konsekuen muncul bersama lebih sering daripada secara kebetulan; lift mendekati 1 menunjukkan independensi; lift di bawah 1 menunjukkan asosiasi negatif. Aturan dengan lift tertinggi adalah penemuan yang paling dapat ditindaklanjuti.
Rumus
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}Kesalahan umum
- Menetapkan dukungan minimum terlalu rendah dan tenggelam dalam ribuan aturan berkualitas rendah tanpa pemfilteran berdasarkan lift.
- Menginterpretasikan keyakinan tinggi sebagai kausalitas daripada kemunculan bersama — aturan dengan keyakinan tinggi tetapi lift mendekati 1 adalah trivial.
- Menerapkan Apriori pada fitur kontinu tanpa mendiskretisasikannya terlebih dahulu, yang menggelembungkan ruang item dan menurunkan kualitas hasil.
- Melaporkan aturan tanpa memeriksa apakah ukuran sampel kumpulan item cukup besar untuk mempercayai perkiraan dukungan.
- Mengabaikan penghapusan aturan yang tidak informatif (misalnya, aturan yang melibatkan item yang dibeli secara universal seperti kartu loyalitas toko).
Pertanyaan yang sering diajukan
Apa perbedaan antara dukungan (support), keyakinan (confidence), dan lift?
Dukungan adalah proporsi semua transaksi yang berisi kumpulan item — ini mengukur prevalensi. Keyakinan adalah probabilitas kondisional bahwa konsekuen muncul mengingat anteseden — ini mengukur keandalan aturan. Lift adalah rasio keyakinan yang diamati terhadap frekuensi dasar konsekuen; lift di atas 1 menunjukkan asosiasi positif yang sebenarnya daripada kebetulan yang didorong oleh popularitas item.
Kapan saya harus memilih FP-Growth daripada Apriori?
FP-Growth mengompresi basis data menjadi struktur pohon dan menambangnya tanpa pemindaian penuh berulang, membuatnya jauh lebih cepat pada dataset besar atau ketika dukungan minimum rendah. Apriori lebih mudah dipahami dan diimplementasikan serta bekerja dengan baik pada dataset kecil hingga sedang di mana waktu berjalan bukan hambatan.
Bagaimana cara memilih dukungan minimum dan keyakinan minimum?
Tidak ada aturan universal. Praktik umum adalah menjalankan algoritma pada beberapa tingkat dukungan, memplot jumlah kumpulan item yang sering muncul terhadap dukungan, dan memilih nilai di lekukan kurva (elbow). Keyakinan kemudian ditetapkan berdasarkan pertanyaan bisnis atau penelitian — keyakinan lebih tinggi untuk aturan yang sangat penting (mission-critical), lebih rendah untuk penemuan eksploratif. Selalu validasi aturan teratas terhadap keahlian domain.
Bisakah Apriori menangani data numerik atau kontinu?
Apriori memerlukan data kehadiran item biner. Variabel kontinu harus didiskretisasi menjadi bin (misalnya, usia menjadi rendah/sedang/tinggi) sebelum dikodekan sebagai item. Diskretisasi yang buruk dapat sangat mendistorsi aturan yang ditemukan, sehingga strategi pembentukan bin memerlukan pemikiran yang cermat.
Apakah Apriori menyiratkan kausalitas antar item?
Tidak. Aturan asosiasi menangkap kemunculan bersama, bukan kausalitas atau arah. Aturan 'roti → mentega' berarti keduanya sering muncul dalam keranjang yang sama; itu tidak berarti membeli roti menyebabkan seseorang membeli mentega, juga tidak berarti hubungan tersebut asimetris dalam arti kausal apa pun.
Metode terkait
Sumber
Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.
Buka referensi publikasiDisalin.Apriori algorithm. Wikipedia.
Buka referensi publikasiDisalin.