Algoritma FP-Growth

Algoritma FP-Growth adalah cara alternatif untuk menemukan itemsets sering tanpa menggunakan generasi calon, sehingga meningkatkan kinerja. Untuk begitu banyak menggunakan membagi-dan-menaklukkan strategi  . Inti dari metode ini adalah penggunaan struktur data khusus bernama sering-pola pohon (FP-pohon), yang mempertahankan informasi asosiasi itemset.

Dengan kata sederhana, algoritma ini bekerja sebagai berikut: pertama kompres database masukan menciptakan sebuah instance FP-Tree untuk mewakili item sering. Setelah langkah pertama membagi database dikompresi menjadi satu set database kondisional, masing-masing terkait dengan satu pola yang sering. Akhirnya, masing-masing database tersebut ditambang secara terpisah. Menggunakan strategi ini, FP-Growth mengurangi biaya pencarian mencari pola singkat rekursif dan kemudian concatenating kemudian dalam pola yang sering panjang, menawarkan selektivitas yang baik.

Dalam database besar, itu tidak mungkin untuk memegang FP-pohon di memori utama. Sebuah strategi untuk mengatasi masalah ini adalah untuk pertama partisi database menjadi satu set database yang lebih kecil (disebut database diproyeksikan), dan kemudian membangun sebuah FP-pohon dari masing-masing database yang lebih kecil.

Sumber: Buku Konsep Data Mining