Apakah FPGrowth masih dianggap "canggih" dalam penambangan pola yang sering?

Sejauh yang saya tahu pengembangan algoritma untuk memecahkan masalah Frequent Pattern Mining (FPM), jalan perbaikan memiliki beberapa pos pemeriksaan utama. Pertama, algoritma Apriori diusulkan pada tahun 1993, oleh Agrawal et al. , bersamaan dengan formalisasi masalah. Algoritma ini dapat menghapus beberapa set dari 2^n - 1set (powerset) dengan menggunakan kisi untuk mempertahankan data. Kelemahan dari pendekatan ini adalah kebutuhan untuk membaca kembali database untuk menghitung frekuensi setiap set diperluas.

Kemudian, pada tahun 1997, Zaki et al. mengusulkan algoritma Eclat , yang memasukkan frekuensi yang dihasilkan dari setiap set di dalam kisi. Ini dilakukan dengan menambahkan, pada setiap node kisi, himpunan transaksi-id yang memiliki item dari root ke node yang dimaksud. Kontribusi utama adalah bahwa seseorang tidak perlu membaca kembali seluruh dataset untuk mengetahui frekuensi setiap set, tetapi memori yang diperlukan untuk menjaga struktur data yang dibangun dapat melebihi ukuran dataset itu sendiri.

Pada tahun 2000, Han et al. mengusulkan sebuah algoritma bernama FPGrowth , bersama dengan struktur data prefiks-pohon bernama FPTree. Algoritme mampu memberikan kompresi data yang signifikan, sementara juga memberikan bahwa hanya set item yang sering akan dihasilkan (tanpa generasi kandidat itemset). Ini dilakukan terutama dengan menyortir item dari setiap transaksi dalam urutan menurun, sehingga item yang paling sering adalah item dengan pengulangan paling sedikit dalam struktur data pohon. Karena frekuensi hanya turun saat melintasi pohon secara mendalam, algoritme dapat menghapus item yang tidak sering.

Edit :

Sejauh yang saya tahu, ini dapat dianggap sebagai algoritma canggih, tapi saya ingin tahu tentang solusi yang diusulkan lainnya. Algoritma apa lagi untuk FPM yang dianggap "canggih"? Apa intuisi / kontribusi utama dari algoritma tersebut?

Apakah algoritma FPGrowth masih dianggap "canggih" dalam penambangan pola yang sering? Jika tidak, algoritma apa yang dapat mengekstrak item yang sering muncul dari dataset besar lebih efisien?

Keadaan seni seperti dalam: digunakan dalam praktek atau dikerjakan dalam teori?

APRIORI digunakan di mana-mana, kecuali dalam mengembangkan algoritme itemset baru yang sering. Mudah diimplementasikan, dan mudah digunakan kembali di domain yang sangat berbeda. Anda akan menemukan ratusan implementasi APRIORI dengan kualitas yang bervariasi. Dan sebenarnya mudah untuk membuat APRIORI salah.

FPgrowth jauh lebih sulit untuk diimplementasikan, tetapi juga jauh lebih menarik. Jadi dari sudut pandang akademis, semua orang mencoba meningkatkan FPgrowth - mendapatkan pekerjaan berdasarkan APRIORI yang diterima akan sangat sulit sekarang.

Jika Anda memiliki implementasi yang baik, setiap algoritma memiliki itu bagus dan itu situasi yang buruk menurut saya. Implementasi APRIORI yang baik hanya perlu memindai basis data k kali untuk menemukan semua kumpulan item dengan panjang k . Khususnya jika data Anda cocok dengan memori utama, ini murah. Apa yang bisa membunuh APRIORI adalah terlalu banyak 2-itemet (khususnya ketika Anda tidak menggunakan Trie dan teknik akselerasi serupa, dll.). Ini bekerja paling baik pada data besar dengan jumlah item yang sering yang rendah.

Eclat bekerja pada kolom; tetapi perlu membaca setiap kolom lebih sering. Ada beberapa pekerjaan di diffsets untuk mengurangi pekerjaan ini. Jika data Anda tidak sesuai dengan memori utama, Eclat mungkin menderita lebih dari Apriori. Dengan menjadi lebih dulu, itu juga akan dapat mengembalikan hasil menarik pertama jauh lebih awal dari Apriori, dan Anda dapat menggunakan hasil ini untuk menyesuaikan parameter; jadi Anda perlu lebih sedikit iterasi untuk menemukan parameter yang baik. Tetapi dengan desain, itu tidak dapat mengeksploitasi pemangkasan serapi Apriori lakukan.

FPGrowth memampatkan kumpulan data ke dalam pohon. Ini bekerja paling baik ketika Anda memiliki banyak catatan duplikat. Anda mungkin bisa meraup beberapa keuntungan untuk Apriori dan Eclat juga jika Anda dapat mengubah data Anda dan menggabungkan duplikat menjadi vektor tertimbang. FPGrowth melakukan ini pada tingkat yang ekstrim. Kekurangannya adalah implementasinya jauh lebih sulit; dan sekali pohon ini tidak sesuai dengan memori lagi itu menjadi berantakan untuk diimplementasikan.

Adapun hasil kinerja dan tolok ukur - jangan percaya mereka. Ada begitu banyak hal untuk diterapkan secara tidak benar. Coba 10 implementasi yang berbeda, dan Anda mendapatkan 10 hasil kinerja yang sangat berbeda. Khususnya untuk APRIORI, saya mendapat kesan bahwa sebagian besar implementasi rusak dalam arti kehilangan beberapa kontribusi utama APRIORI ... dan dari mereka yang memiliki bagian-bagian ini dengan benar, kualitas optimisasi sangat bervariasi.

Bahkan ada makalah tentang cara menerapkan algoritma ini secara efisien:

Implementasi Apriori dan Eclat yang Efisien. Lokakarya
Christian Borgelt
untuk Implementasi Penambangan Item Frequent Set (FIMI 2003, Melbourne, FL, USA).

Anda mungkin juga ingin membaca survei ini di domain ini:

• Goethals, Bart. "Survei tentang penambangan pola yang sering." Univ. Helsinki (2003).

• Ferenc Bodon, Sebuah Survei tentang Penambangan Item Sering, Laporan Teknis, Universitas Teknologi dan Ekonomi Budapest, 2006,

• Item yang Sering Ditentukan Penambangan
  Christian Borgelt
  Wiley Ulasan Interdisipliner: Penambangan Data dan Penemuan Pengetahuan 2 (6): 437-456. 2012

Sebagian besar pendekatan Pola Sering baru-baru ini yang saya lihat dalam literatur didasarkan pada mengoptimalkan FPGrowth. Harus saya akui, saya belum melihat banyak perkembangan dalam literatur di FPM selama bertahun-tahun.

Wikibook ini menyoroti banyak varian pada FPGrowth yang ada di luar sana.