Penambangan Aturan Asosiasi (Apriori)
- Diperkenalkan oleh
- Rakesh Agrawal & Ramakrishnan Srikant
- Tahun
- 1994
- Jenis
- Unsupervised pattern discovery algorithm
- Keluarga
- Pattern mining
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Penambangan Aturan Asosiasi adalah teknik penambangan data tanpa pengawasan yang menemukan pola ko-kemunculan di antara item dalam kumpulan data transaksional. Diperkenalkan secara formal oleh Agrawal, Imieliński, dan Swami pada tahun 1993, dan disempurnakan dengan algoritma Apriori yang monumental oleh Agrawal dan Srikant pada tahun 1994, teknik ini mengidentifikasi aturan berbentuk X ⇒ Y — yang berarti transaksi yang mengandung itemset X cenderung juga mengandung itemset Y — yang dikuantifikasi oleh dukungan (support), kepercayaan (confidence), dan pengangkatan (lift).
Intuisi di balik metode
Bayangkan log struk supermarket: jika ribuan pelanggan yang membeli roti dan mentega juga membeli susu, pola itu patut diperhatikan. Penambangan Aturan Asosiasi bekerja seperti pustakawan teliti yang menyisir setiap struk, menghitung seberapa sering kombinasi item muncul bersama, dan memunculkan kombinasi yang melebihi frekuensi minimum. Setelah kelompok yang sering ditemukan, algoritma bertanya: mengingat Anda sudah memiliki item-item ini, seberapa andal itu memprediksi item berikutnya? Logika dua lintasan frekuensi-kemudian-kepercayaan ini adalah inti dari Apriori.
Sejarah
Makalah dasar oleh Agrawal, Imieliński, dan Swami (1993) mendefinisikan masalah aturan asosiasi dalam konteks data transaksi supermarket. Makalah VLDB tahun 1994 oleh Agrawal dan Srikant memperkenalkan algoritma Apriori dan strategi pemangkasannya yang efisien, membuat penambangan skala besar menjadi praktis. Pekerjaan selanjutnya menghasilkan FP-Growth (Han et al., 2000), yang sepenuhnya menghindari pembuatan kandidat, dan ECLAT, yang menambang dalam format data vertikal — menetapkan keluarga algoritma yang kaya yang sekarang menjadi pusat kurikulum penambangan data.
Kapan digunakan
Penambangan Aturan Asosiasi cocok untuk kumpulan data transaksional besar di mana tujuannya adalah untuk menemukan pola ko-kemunculan tanpa variabel target yang telah ditentukan sebelumnya. Ini mengasumsikan item bersifat biner (ada/tidak ada) per transaksi. Ini sesuai untuk analisis keranjang pasar (market basket analysis), sistem rekomendasi, analisis aliran klik web, dan penemuan ko-diagnosis medis. Ini tidak sesuai untuk data kontinu atau ordinal kecuali didiskretisasi terlebih dahulu, untuk kumpulan data dengan dimensi yang sangat tinggi (ruang kandidat eksponensial), atau ketika inferensi kausal daripada asosiatif diperlukan. Alternatif termasuk FP-Growth untuk enumerasi itemset sering yang lebih cepat dan penambangan urutan ketika urutan temporal penting.
Batasan dan pertimbangan
- Ruang kandidat eksponensial: jumlah aturan tumbuh secara kombinatorial dengan jumlah item yang berbeda.
- Kerangka kerja dukungan-kepercayaan dapat menghasilkan aturan yang menyesatkan ketika tingkat dasar item bervariasi secara luas (penyesuaian pengangkatan diperlukan).
- Model transaksi biner memerlukan diskretisasi variabel kontinu, menimbulkan kehilangan informasi.
- Ambang batas dukungan minimum yang tinggi melewatkan aturan langka tetapi berharga; ambang batas rendah menghasilkan ribuan aturan trivial.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Sepenuhnya tanpa pengawasan: tidak memerlukan data berlabel atau target yang telah ditentukan.
- Keluaran yang dapat diinterpretasikan: aturan adalah pernyataan jika-maka yang dapat dibaca manusia dengan dukungan dan kepercayaan yang dikuantifikasi.
- Dapat diskalakan melalui pemangkasan Apriori; varian FP-Growth sepenuhnya menghilangkan pemindaian basis data berulang.
- Agnoistik domain: diterapkan di seluruh ritel, perawatan kesehatan, analitik web, dan bioinformatika.
Penerapan
- Ritel: penempatan produk dan rekomendasi lintas penjualan dari log transaksi titik penjualan.
- Perawatan kesehatan: analisis ko-kemunculan diagnosis, prosedur, atau pengobatan dalam catatan kesehatan elektronik.
- Analitik web: penemuan pola aliran klik untuk rekomendasi halaman dan optimasi navigasi.
- Bioinformatika: identifikasi set gen yang diekspresikan bersama dan motif interaksi protein.
- Keamanan siber: deteksi peristiwa jaringan yang berkorelasi yang menunjukkan pola intrusi.
Cara kerjanya
Cara kerjanya
Algoritma memindai basis data transaksi D untuk menghitung seberapa sering setiap itemset X muncul. Sebuah itemset dinyatakan sering (frequent) — dan ditempatkan di L_k — hanya ketika dukungannya (fraksi transaksi yang mengandungnya) memenuhi atau melebihi ambang batas dukungan minimum (σ_min) yang ditentukan pengguna. Proses dimulai dengan item individual (k=1) dan secara iteratif membangun kumpulan kandidat yang lebih besar.
Rumus
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}Properti anti-monotonik dari dukungan menyatakan bahwa setiap subkumpulan dari itemset yang sering harus sering itu sendiri. Apriori memanfaatkan ini dengan memangkas setiap itemset-k kandidat yang subkumpulan-(k-1)-nya tidak semuanya ada dalam himpunan sering yang terverifikasi L_{k-1}. Ini secara dramatis mengurangi ruang pencarian, menghindari pemindaian basis data yang mahal untuk itemset yang tidak mungkin sering.
Rumus
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_kDari setiap itemset sering X ∪ Y, algoritma menghasilkan aturan X ⇒ Y di mana X dan Y adalah subkumpulan yang saling lepas. Sebuah aturan dipertahankan hanya ketika kepercayaannya — probabilitas kondisional Y diberikan X, dihitung sebagai support(X ∪ Y) / support(X) — memenuhi atau melebihi ambang batas kepercayaan minimum (γ_min). Langkah ini mengubah ko-kemunculan mentah menjadi pernyataan prediktif yang terarah.
Rumus
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}Aturan yang dipertahankan diberi peringkat dan difilter berdasarkan pengangkatan (lift), yang mengukur seberapa mungkin Y muncul bersama X dibandingkan secara kebetulan. Lift > 1 menunjukkan korelasi positif di luar independensi; lift = 1 menunjukkan independensi; lift < 1 menunjukkan korelasi negatif. Ukuran ketertarikan tambahan seperti keyakinan (conviction) dan tuas (leverage) dapat lebih menyempurnakan himpunan aturan untuk penerapan praktis.
Rumus
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}Kesalahan umum
- Menetapkan dukungan minimum terlalu rendah membanjiri analis dengan aturan palsu; pemilihan ambang batas memerlukan pengetahuan domain atau validasi silang.
- Mencampuradukkan asosiasi statistik dengan kausalitas: pengangkatan tinggi tidak menyiratkan bahwa X menyebabkan Y.
- Mengabaikan distribusi frekuensi item: item umum mendominasi aturan dan menyingkirkan asosiasi item langka yang bermakna.
- Memperlakukan kepercayaan saja sebagai metrik kualitas; aturan dengan kepercayaan tinggi tetapi pengangkatan rendah mungkin tidak berkinerja lebih baik daripada peluang acak.
Pertanyaan yang sering diajukan
Apa perbedaan antara dukungan, kepercayaan, dan pengangkatan?
Dukungan mengukur seberapa sering itemset muncul dalam kumpulan data secara keseluruhan. Kepercayaan mengukur probabilitas kondisional dari konsekuen yang diberikan anteseden. Pengangkatan menormalkan kepercayaan dengan frekuensi marjinal konsekuen, mengungkapkan apakah ko-kemunculan melebihi apa yang diharapkan di bawah independensi. Ketiga metrik tersebut diperlukan bersama-sama untuk evaluasi aturan yang kuat.
Bagaimana algoritma Apriori mengurangi biaya komputasi?
Apriori memanfaatkan properti anti-monotonik: jika sebuah itemset tidak sering, maka semua supersetnya juga harus tidak sering. Dengan membuang kandidat apa pun yang subkumpulan-subkumpulannya tidak semuanya diverifikasi sebagai sering, algoritma memangkas sebagian besar ruang pencarian sebelum menghitung, secara drastis mengurangi jumlah lintasan basis data yang diperlukan dibandingkan dengan enumerasi brute-force.
Kapan saya harus menggunakan FP-Growth daripada Apriori?
FP-Growth lebih disukai ketika kumpulan data besar dan ambang batas dukungan minimum rendah, karena ia mengompresi basis data transaksi ke dalam struktur pohon FP yang ringkas dan menambang pola secara langsung tanpa menghasilkan kandidat eksplisit. Ini menghilangkan pemindaian basis data penuh yang berulang, membuatnya jauh lebih cepat daripada Apriori pada kumpulan data padat dengan banyak itemset yang sering.
Metode terkait
Sumber
Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.
Buka referensi DOIDisalin.Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.
Buka referensi publikasiDisalin.