Algoritma FP-Growth: Contoh Perhitungan Manual Lengkap

Tutorial ini membahas algoritma FP-Growth (Frequent Pattern Growth) dengan contoh perhitungan manual lengkap untuk mencari pola pembelian pada data transaksi. Contoh kasus menggunakan lima transaksi minimarket dengan minimum support 60% dan minimum confidence 70%.

FP-Growth mencari frequent itemset tanpa membangkitkan candidate itemset sebanyak Apriori. Data transaksi dikompresi ke dalam FP-Tree, kemudian pola ditambang menggunakan conditional pattern base dan conditional FP-Tree.

---

Daftar Isi

• Pengertian FP-Growth
• Perbedaan FP-Growth dan Apriori
• Istilah Penting
• Rumus Support, Confidence, dan Lift
• #01 Menentukan Data Transaksi
• #02 Menentukan Minimum Support
• #03 Menghitung Frekuensi Setiap Item
• #04 Membentuk F-List
• #05 Mengurutkan Item pada Transaksi
• #06 Membentuk FP-Tree
• #07 Membentuk Conditional Pattern Base
• #08 Membentuk Conditional FP-Tree
• #09 Menentukan Frequent Itemset
• #10 Membentuk Association Rule
• Cara Membaca Lift Ratio
• Kelebihan dan Kekurangan FP-Growth
• Ringkasan
• FAQ FP-Growth
• Referensi
• Source Code FP-Growth

---

Pengertian FP-Growth

FP-Growth adalah singkatan dari Frequent Pattern Growth. Algoritma ini digunakan untuk menemukan frequent itemset dari kumpulan transaksi.

Frequent itemset adalah kombinasi item yang muncul bersama dengan frekuensi minimal tertentu. Hasilnya dapat digunakan untuk membentuk association rule seperti:

pelanggan yang membeli Kopi cenderung juga membeli Popok.

FP-Growth menggunakan struktur pohon bernama FP-Tree (Frequent Pattern Tree). Transaksi yang memiliki prefix sama dapat berbagi jalur sehingga data menjadi lebih ringkas.

Perbedaan FP-Growth dan Apriori

Keduanya memiliki tujuan yang sama, yaitu mencari frequent itemset. Perbedaannya terletak pada cara pencarian pola.

Istilah Penting

Support Count

Jumlah transaksi yang mengandung suatu item atau itemset.

Minimum Support

Batas minimum agar itemset dinyatakan frequent.

F-List

Daftar frequent item yang biasanya diurutkan berdasarkan support count dari terbesar ke terkecil.

FP-Tree

Struktur pohon yang mengompresi transaksi dengan memanfaatkan prefix transaksi yang sama.

Conditional Pattern Base

Kumpulan prefix path yang mengarah ke item tertentu beserta count-nya.

Conditional FP-Tree

FP-Tree yang dibentuk dari conditional pattern base untuk menambang pola yang mengandung suffix tertentu.

Rumus Support, Confidence, dan Lift

Support Count

$$ \sigma(X) = |\{T_i \mid X \subseteq T_i\}| $$

Support

$$ Support(X) = \frac{ \sigma(X) }{ N } $$

Confidence

Untuk rule \(X \rightarrow Y\):

$$ Confidence(X \rightarrow Y) = \frac{ Support(X \cup Y) }{ Support(X) } $$

Lift Ratio

$$ Lift(X \rightarrow Y) = \frac{ Confidence(X \rightarrow Y) }{ Support(Y) } $$

#01 Menentukan Data Transaksi

Contoh menggunakan lima transaksi minimarket.

#02 Menentukan Minimum Support

Minimum support yang digunakan adalah:

$$ MinSupport = 60\% $$

Karena jumlah transaksi adalah 5:

$$ MinSupportCount = 0.6 \times 5 = 3 $$

Artinya, item atau itemset harus muncul minimal 3 transaksi agar dinyatakan frequent.

#03 Menghitung Frekuensi Setiap Item

Contoh Roti

Roti muncul pada T1, T2, T4, dan T5:

$$ \sigma(Roti) = 4 $$

$$ Support(Roti) = \frac{4}{5} = 0.8 = 80\% $$

Contoh Kopi

Kopi muncul pada T2, T3, dan T4:

$$ \sigma(Kopi) = 3 $$

$$ Support(Kopi) = \frac{3}{5} = 60\% $$

Cola hanya muncul 2 kali dan Telur hanya 1 kali. Keduanya tidak mencapai minimum support count 3 sehingga tidak dimasukkan ke FP-Tree.

#04 Membentuk F-List

Item yang memenuhi minimum support diurutkan berdasarkan support count dari terbesar ke terkecil.

Pada support yang sama, tutorial ini menggunakan urutan tetap agar proses mudah direplikasi.

F-List:

Roti → Popok → Susu → Kopi

#05 Mengurutkan Item pada Transaksi

Item yang tidak frequent dihapus. Item yang tersisa kemudian diurutkan mengikuti F-List.

Contoh T2

Transaksi awal:

Roti, Popok, Kopi, Telur

Telur dihapus karena tidak memenuhi minimum support. Hasil akhirnya:

Roti → Popok → Kopi

Contoh T3

Transaksi awal:

Susu, Popok, Kopi, Cola

Cola dihapus, kemudian item diurutkan:

Popok → Susu → Kopi

#06 Membentuk FP-Tree

FP-Tree dibangun dengan memasukkan transaksi terurut satu per satu. Jika suatu transaksi memiliki prefix yang sama dengan jalur yang sudah ada, count node dinaikkan.

Memasukkan T1

T1:

Roti → Susu

Membentuk jalur:

Root → Roti:1 → Susu:1

Memasukkan T2

T2:

Roti → Popok → Kopi

Node Roti sudah ada sehingga count Roti menjadi 2. Cabang berikutnya membentuk:

Roti → Popok:1 → Kopi:1

Memasukkan T4

T4:

Roti → Popok → Susu → Kopi

Jalur Roti → Popok sudah tersedia, sehingga count keduanya bertambah. Node Susu dan Kopi diteruskan di bawah jalur tersebut.

Setelah seluruh transaksi dimasukkan, struktur node FP-Tree dapat dibaca pada tabel berikut.

Bentuk pohonnya secara ringkas:

Root
├── Roti:4
│   ├── Susu:1
│   └── Popok:3
│       ├── Kopi:1
│       └── Susu:2
│           └── Kopi:1
└── Popok:1
    └── Susu:1
        └── Kopi:1

#07 Membentuk Conditional Pattern Base

Mining dilakukan dari item dengan support paling kecil pada F-List. Pada contoh ini item tersebut adalah Kopi.

Conditional Pattern Base untuk Kopi

Dari FP-Tree terdapat tiga node Kopi dengan prefix path:

Path 1: Roti → Popok dengan count 1.

Path 2: Roti → Popok → Susu dengan count 1.

Path 3: Popok → Susu dengan count 1.

Frekuensi item pada conditional pattern base Kopi:

$$ \sigma_{Kopi}(Roti) = 2 $$

$$ \sigma_{Kopi}(Popok) = 3 $$

$$ \sigma_{Kopi}(Susu) = 2 $$

Karena minimum support count adalah 3, hanya item yang memiliki conditional count minimal 3 yang dipertahankan.

#08 Membentuk Conditional FP-Tree

Conditional FP-Tree untuk Kopi

Dari conditional pattern base Kopi, count yang diperoleh adalah:

• Roti = 2 (dihapus)
• Popok = 3 (dipertahankan)
• Susu = 2 (dihapus)

Pada contoh ini hanya Popok yang mencapai minimum support count 3.

Maka conditional FP-Tree untuk Kopi menjadi:

Root
└── Popok:3

Dari sini diperoleh frequent pattern:

$$ \{Popok,\ Kopi\} \quad support\ count=3 $$

Conditional FP-Tree untuk Susu

Conditional frequency untuk Susu:

• Roti = 3 (dipertahankan)
• Popok = 3 (dipertahankan)

Roti dan Popok sama-sama memiliki conditional count 3. Karena itu diperoleh frequent pattern:

• {Roti, Susu} dengan support count 3.
• {Popok, Susu} dengan support count 3.

Kombinasi {Roti, Popok, Susu} hanya muncul 2 kali, sehingga tidak memenuhi minimum support.

#09 Menentukan Frequent Itemset

Setelah seluruh conditional FP-Tree ditambang, diperoleh frequent itemset yang memenuhi minimum support 60%.

Contoh {Popok, Kopi}

Itemset Popok dan Kopi muncul pada T2, T3, dan T4:

$$ \sigma(\{Popok,Kopi\}) = 3 $$

$$ Support(\{Popok,Kopi\}) = \frac{3}{5} = 60\% $$

Contoh {Roti, Susu}

Roti dan Susu muncul bersama pada T1, T4, dan T5:

$$ Support(\{Roti,Susu\}) = \frac{3}{5} = 60\% $$

#10 Membentuk Association Rule

Frequent itemset selanjutnya dapat digunakan untuk membentuk association rule. Tutorial ini menggunakan minimum confidence:

$$ MinConfidence = 70\% $$

Contoh Rule Kopi → Popok

Support Kopi:

$$ Support(Kopi) = \frac{3}{5} = 0.6 $$

Support Popok dan Kopi:

$$ Support(Popok \cap Kopi) = \frac{3}{5} = 0.6 $$

Confidence:

$$ Confidence(Kopi \rightarrow Popok) = \frac{0.6}{0.6} = 1 = 100\% $$

Support Popok:

$$ Support(Popok) = \frac{4}{5} = 0.8 $$

Lift:

$$ Lift(Kopi \rightarrow Popok) = \frac{ 1 }{ 0.8 } = 1.25 $$

Rule ini memenuhi minimum confidence dan memiliki lift lebih besar dari 1.

Cara Membaca Lift Ratio

• Lift > 1: hubungan positif; kemunculan antecedent meningkatkan kemungkinan consequent.
• Lift = 1: antecedent dan consequent cenderung independen.
• Lift < 1: hubungan cenderung negatif.

Pada contoh rule Kopi → Popok, lift sebesar 1.25 menunjukkan asosiasi positif pada dataset contoh.

Lift tetap harus dibaca bersama support dan confidence. Rule dengan confidence tinggi belum tentu menarik apabila consequent memang sangat sering muncul pada hampir seluruh transaksi.

Kelebihan dan Kekurangan FP-Growth

Kelebihan FP-Growth

• Tidak membangkitkan candidate itemset secara eksplisit.
• Mengompresi transaksi menggunakan FP-Tree.
• Efisien untuk dataset dengan banyak pola yang sering muncul bersama.
• Dapat digunakan untuk market basket analysis.
• Hasil frequent itemset dapat dilanjutkan menjadi association rule.

Kekurangan FP-Growth

• Implementasi FP-Tree lebih kompleks dibanding Apriori dasar.
• Struktur tree dapat menjadi besar jika transaksi memiliki sedikit prefix yang sama.
• Minimum support yang terlalu kecil dapat menghasilkan sangat banyak pola.
• Frequent itemset belum tentu langsung memiliki makna bisnis yang kuat.
• Association rule tetap perlu dievaluasi menggunakan confidence, lift, atau ukuran lain.

Ringkasan

FP-Growth dimulai dengan menghitung support setiap item. Item yang tidak memenuhi minimum support dihapus, sedangkan item frequent disusun menjadi F-List.

Transaksi kemudian diurutkan mengikuti F-List dan dimasukkan ke FP-Tree. Mining dilakukan dari item dengan frekuensi rendah melalui conditional pattern base dan conditional FP-Tree.

Pada contoh ini minimum support count adalah 3. Frequent 1-itemset yang diperoleh adalah Roti, Popok, Susu, Kopi.

Salah satu pola yang ditemukan adalah {Popok, Kopi} dengan support 60%. Rule Kopi → Popok memiliki confidence 100% dan lift 1.25 pada dataset contoh.

FAQ FP-Growth

Apa kepanjangan FP-Growth?

FP-Growth adalah Frequent Pattern Growth.

Apa fungsi FP-Growth?

FP-Growth digunakan untuk menemukan frequent itemset atau kombinasi item yang sering muncul bersama dalam transaksi.

Apa perbedaan FP-Growth dan Apriori?

Apriori membangkitkan candidate itemset secara bertahap, sedangkan FP-Growth mengompresi transaksi ke FP-Tree dan menambang pola tanpa candidate generation secara eksplisit.

Apa itu FP-Tree?

FP-Tree adalah struktur pohon yang menyimpan transaksi frequent secara terkompresi dengan menggabungkan prefix yang sama.

Apa itu F-List?

F-List adalah daftar item yang memenuhi minimum support dan telah diurutkan berdasarkan frekuensinya.

Apa itu conditional pattern base?

Conditional pattern base adalah kumpulan prefix path yang menuju suatu item tertentu beserta count masing-masing path.

Apa itu conditional FP-Tree?

Conditional FP-Tree adalah pohon yang dibangun dari conditional pattern base setelah item yang tidak frequent dihapus.

Bagaimana menentukan minimum support count?

Minimum support dalam bentuk proporsi dikalikan jumlah transaksi. Pada contoh ini 60% × 5 = 3 transaksi.

Apa itu confidence?

Confidence menunjukkan seberapa sering consequent muncul ketika antecedent muncul.

Apa itu lift?

Lift membandingkan confidence sebuah rule dengan peluang kemunculan consequent secara umum.

Apakah lift harus lebih dari 1?

Lift lebih dari 1 menunjukkan asosiasi positif. Namun pemilihan rule sebaiknya tetap mempertimbangkan support, confidence, konteks data, dan tujuan analisis.

Apakah FP-Growth termasuk classification?

Tidak. FP-Growth termasuk association pattern mining, bukan algoritma klasifikasi.

Apakah FP-Growth dapat digunakan untuk data penjualan?

Ya. Salah satu penggunaan yang umum adalah market basket analysis untuk melihat item yang sering dibeli bersamaan.

Apakah FP-Growth membutuhkan data label?

Tidak. FP-Growth bekerja pada data transaksi dan tidak membutuhkan target kelas seperti algoritma supervised learning.

---

Referensi

1. Han, J., Pei, J. & Yin, Y. (2000). Mining Frequent Patterns without Candidate Generation. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 1–12.
2. Han, J., Kamber, M. & Pei, J. (2011). Data Mining: Concepts and Techniques, Third Edition. Morgan Kaufmann.
3. Agrawal, R., Imieliński, T. & Swami, A. (1993). Mining Association Rules between Sets of Items in Large Databases. Proceedings of the ACM SIGMOD Conference, 207–216.

---

Source Code FP-Growth

Berikut adalah beberapa source code yang menggunakan algoritma FP-Growth untuk association rule dan market basket analysis.

Ada yang Ditanyakan?

Jika anda masih ada kesulitan atau kekeliruan tentang penjelasan metode di atas, bisa menghubungi kami lewat WA/Email sesuai halaman Kontak.

Jika ingin memiliki file excel dari metode di atas bisa melihat cara download di halaman Download.

Jika ingin memiliki source code dari metode di atas, baik berbasis web maupun desktop bisa melihat daftar harga donasi di halaman Daftar Source Code.

Donasi ini digunakan oleh penulis untuk membayar server dan membeli kopi sembari membuat tutorial Metode/Algoritma lainnya :).