Penambangan Itemset Frekuen ECLAT
- Diperkenalkan oleh
- Mohammed J. Zaki
- Tahun
- 2000
- Jenis
- Frequent-itemset mining algorithm (vertical format)
- Keluarga
- Pattern mining
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
ECLAT, diperkenalkan oleh Mohammed Zaki pada tahun 2000, menambang itemset frekuen menggunakan representasi data vertikal: alih-alih memindai transaksi, ia menyimpan untuk setiap item himpunan ID transaksi (tidset) yang memuatnya, dan menghitung dukungan (support) itemset apa pun dengan menginterseksikan tidset.
Pendekatan berbasis interseksi secara mendalam (depth-first) ini cepat dan efisien memori, alternatif untuk pemindaian horizontal Apriori dan pohon FP-Growth.
Intuisi di balik metode
Sebagian besar penambang itemset berpikir baris demi baris: item apa saja yang ada di setiap transaksi? ECLAT membalik tabelnya. Untuk setiap item, ia menyimpan daftar transaksi yang memuatnya. Sekarang dukungan pasangan item hanyalah ukuran tumpang tindih kedua daftar mereka — interseksi himpunan sederhana — dan Anda tidak pernah memindai ulang basis data. Untuk menemukan itemset frekuen yang lebih panjang, interseksikan daftar itemset yang lebih pendek. Menjelajahi secara mendalam ini dan memangkas setiap kali interseksi menjadi terlalu kecil secara efisien menghitung semua itemset frekuen.
Sejarah
Mohammed Zaki memperkenalkan ECLAT dan paradigma penambangan vertikal dalam karya yang berpuncak pada makalah IEEE TKDE tahun 2000 tentang penambangan asosiasi yang dapat diskalakan, kemudian menyempurnakannya dengan diffset (dECLAT). Ia bergabung dengan Apriori (1994, generasi kandidat horizontal) dan FP-Growth (2000, berbasis pohon) sebagai salah satu dari tiga keluarga kanonik algoritma itemset frekuen, masing-masing menukar pemindaian, memori, dan kepadatan data secara berbeda. ECLAT tetap menjadi pilihan standar dalam perangkat lunak penambangan data.
Kapan digunakan
Gunakan ECLAT untuk penambangan itemset frekuen ketika pendekatan vertikal berbasis interseksi sesuai dengan data — seringkali sangat cepat pada kumpulan data padat dan menghindari pemindaian basis data berulang, menjadikannya alternatif yang kuat untuk Apriori dan setara dengan FP-Growth. Ia bersinar ketika tidset berukuran sedang dan muat di memori, dan varian diffset menangani data padat dengan baik. Biayanya: tidset untuk item frekuen bisa besar dan memakan banyak memori pada kumpulan data jarang yang besar, interseksi perantara menambah overhead, dan seperti semua penambangan berbasis dukungan, ia sensitif terhadap ambang batas dukungan minimum. Seperti biasa, itemset frekuen hanyalah tahap pertama; aturan asosiasi dengan kepercayaan/lift dihasilkan setelahnya. Pilih di antara ECLAT, FP-Growth, dan Apriori berdasarkan kepadatan data dan memori.
Batasan dan pertimbangan
- Tidset untuk item frekuen bisa besar, memakan memori pada kumpulan data besar.
- Hasil interseksi perantara menambah overhead memori/waktu.
- Kurang intuitif dibandingkan representasi horizontal (Apriori).
- Sensitif terhadap ambang batas dukungan minimum, seperti semua penambangan itemset.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Dukungan dihitung oleh interseksi tidset yang cepat — tidak ada pemindaian basis data berulang.
- Pencarian mendalam dengan kelas ekuivalensi awalan menggunakan kembali pekerjaan dan melokalkan memori.
- Seringkali sangat efisien pada kumpulan data padat, kompetitif dengan FP-Growth.
- Optimasi diffset selanjutnya mengurangi biaya memori dan interseksi.
Penerapan
- Penambangan asosiasi keranjang belanja dan ritel.
- Analisis kemunculan bersama web dan clickstream.
- Penemuan kemunculan bersama frekuen dalam bioinformatika.
- Tugas itemset frekuen apa pun yang mengutamakan pendekatan vertikal berbasis interseksi.
- Kumpulan data transaksional padat di mana ECLAT diffset unggul.
Cara kerjanya
Cara kerjanya
Basis data ditransformasi sekali ke dalam format vertikal: setiap item dipetakan ke tidset-nya, himpunan ID transaksi di mana ia muncul. Ini adalah struktur data kunci — semua pekerjaan selanjutnya adalah operasi himpunan pada tidset, bukan lintasan pada transaksi asli.
Rumus
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}Dukungan itemset adalah kardinalitas interseksi tidset itemnya — jumlah transaksi yang memuat semuanya. Penghitungan menjadi interseksi, yang cepat, dan item tunggal frekuen (yang tidset-nya cukup besar) menjadi benih pencarian.
Rumus
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |Itemset diperluas dengan menginterseksikan tidset: tidset dari X ∪ {y} adalah interseksi tidset dari X dan {y}. ECLAT menjelajahi kisi itemset secara mendalam dalam kelas ekuivalensi (itemset berbagi awalan), sehingga interseksi digunakan kembali dan pencarian tetap lokal.
Rumus
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}Ekstensi dipertahankan hanya jika tidset-nya (dan karenanya dukungannya) memenuhi ambang batas dukungan minimum; jika tidak, cabang tersebut dipangkas (anti-monotonisitas: tidak ada superset yang bisa frekuen). Diffset — hanya menyimpan perbedaan antara tidset — adalah optimasi umum yang selanjutnya mengurangi memori dan biaya interseksi.
Rumus
\text{keep extensions with } \text{support} \ge \text{minsup}Kesalahan umum
- Menambang data jarang yang sangat besar di mana tidset membengkakkan memori — pertimbangkan diffset atau FP-Growth.
- Menetapkan dukungan minimum terlalu rendah dan menghasilkan jumlah itemset yang tidak dapat dikelola.
- Membingungkan itemset frekuen dengan aturan asosiasi (aturan adalah langkah terpisah).
- Mengabaikan varian diffset pada data padat di mana ia sangat membantu.
Pertanyaan yang sering diajukan
Bagaimana ECLAT berbeda dari Apriori dan FP-Growth?
Ketiganya menemukan itemset frekuen. Apriori menggunakan format horizontal dengan generasi kandidat dan banyak pemindaian; FP-Growth mengompresi data ke dalam pohon dan menambang secara rekursif; ECLAT menggunakan format tidset vertikal dan menghitung dukungan dengan menginterseksikan daftar ID transaksi secara mendalam. ECLAT dan FP-Growth menghindari pemindaian berulang Apriori.
Apa itu tidset?
Tidset (himpunan ID transaksi) adalah daftar transaksi yang memuat item atau itemset tertentu. ECLAT menyimpannya secara vertikal dan menghitung dukungan itemset sebagai ukuran interseksi tidset itemnya, mengubah penghitungan menjadi interseksi himpunan.
Apa itu diffset?
Diffset hanya menyimpan perbedaan antara tidset itemset dan tidset induknya, bukan tidset lengkap. Pada data padat, ini secara drastis mengurangi biaya memori dan interseksi, memberikan varian dECLAT keunggulan efisiensi yang substansial.
Metode terkait
Sumber
Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.
Buka referensi DOIDisalin.