## Implementasi Algoritma Frequent Growth (FP-Growth) Menentukan Asosiasi Antar Produk
Rangga Yogasuwara * , Ferdiansyah, Andri, Linda Atika
Sistem Informasi, Universitas Bina Darma Palembang, Palembang, Indonesia Email: 1,* ranggayogasuara@gmail.com, 2 ferdi@binadarma.ac.id, 3 andri@binadarma.ac.id , 4 linda.atika@binadarma.ac.id Email Penulis Korespondensi: ranggayogasuara@gmail.com Submitted: 25/09/2022 ; Accepted: 29/09/2022 ; Published: 30/09/2022
Abstrak –Penumpukan data disebabkan oleh banyaknya data transaksi yang disimpan. Dengan memanfaatkan data transaksi penjualan yang ada di dalam database, data tersebut dapat diolah lebih lanjut menjadi informasi yang  berguna bagi manjer untuk mengambil sebuah keputusan. Dengan adanya data mining diharapkan dapat membantu Toko Miring untuk menemukan informasi yang terdapat dalam data transaksi menjadi sebuah pengetahuan (knowledge) yang baru. Association Rule, yaitu prosedur dalam Market Basket Analysis untuk  menemukan hubungan antar item dalam  kumpulan data atau bisa dikatakan association rule ini bertujuan menemukan kumpulan item yang sering muncul dalam waktu bersamaan dan menampilkannya dalam bentuk pola kebiasaan konsumen dalam berbelanja. Algoritma FP-Growth merupakan algoritma yang dapat digunakan untuk menentukan himpunan data yang paling sering muncul (frequent itemset) dalam sebuah data di dalam pencarian frequent itemset dalam sebuah kumpulan data dengan membangkitkan struktur prefix-tree atau sering disebut dengan FP-Tree. Dari hasil pengujian dapat disimpulkan bahwa penerapan data mining menggunakan Algoritma FP-Growth bisa digunakan untuk menganalisa pola belanja konsumen.
Kata Kunci: Penjualan; Data Mining; Association Rules; Frequent Itemset; FP-Growth; FP-Tree
Abstract– Data accumulation is caused by the amount of transaction data stored. By utilizing the sales transaction data in the database, the data can be further processed into useful information for managers to make decisions. With the existence of data mining,  it  is  hoped  that  it  can  help  the  Leaning  Shop  to  find  the  information  contained  in  the  transaction  data  into  new knowledge. Association Rule, which is a procedure in Market Basket Analysis to find relationships between items in a data set or it can be said that this association rule aims to find a collection of items that often appear at the same time and display them in the form of consumer habits in shopping. The FP-Growth algorithm is an algorithm that can be used to determine the data set that appears most often (frequent itemset) in a data, in the search for frequent itemset in a data set by generating a prefix- tree structure or often called the FP-Tree. From the test results it can be concluded that the application of data mining using the FP-Growth Algorithm can be used to analyze consumer spending patterns.
Keywords: Sales; Data Mining; Association Rules; Frequent Itemset; FP-Growth; FP-Tree

## 1. PENDAHULUAN
Di era  globalisasi  saat  ini banyak sekali bidang yang mengalami perkembangan salah satunya adalah di bidang teknologi  informasi  terutama  dalam  dunia  bisnis. Persaingan  pada  dunia  bisnis  sangatlah  ketat,  sebagai  contoh dibidang bisnis minimarket yang saat ini mengalami perkembangan pesat apalagi menggunakan sistem yang lebih modern guna mempermudah dalam perhitungan sehingga dapat mengimbangi kebutuhan masyarakat yang tinggi. Tantangan  utama  bagi  sebuah minimarket yaitu  mengatasi  kebutuhan  konsumen  secara  lebih  efektif  di  tingkat lokal.
Masalah yang muncul adalah untuk menemukan strategi bisnis atau menemukan promosi yang ditargetkan untuk  melayani  pasar  dan  pelanggan  dan  menghindari  kerugian  bisnis,  Dengan  adanya  data mining dapat diharapkan  membantu  Toko  Miring  dapat  membantu  menggali  informasi  yang  terdapat  pada  data  transaksi menjadi  sebuah  pengetahuan  ( Knowledge )  yang  baru.  Sehingga  pemilik  Toko  Miring  dapat  cenderung menjalankan promosi bundling produk untuk meningkatkan penjualan, menemukan hubungan antar produk dan mengaturnya untuk membentuk pola kebiasaan konsumen dalam berbelanja.
Karena itu CV. Toko Miring menganalisis dengan baik perilaku pembelian konsumen untuk produk-produk terpilih untuk menentukan strategi persediaan untuk produk yang dijual, karena produk-produk yang laris dengan saling  berhubungan  masih  belum  tertata  dengan  baik.  Secara  alami,  ini  mengarah  pada  bahwa  strategi penyimpanan masa depan tidak direncanakan dengan baik.
Salah satu teknik data mining yang digunakan adalah Association Rule, merupakan prosedur dalam Market Basic  Analysis yang  menemukan  informasi  berupa  hubungaan  antar  item  dalam  suatu  data  set  dan menampilkannya  dalam  bentuk  pola  yang  menjelaskan  tentang  kebiasaan  konsumen  dalam  berbelanja.  Atau mengetahui sekumpulan item yang dalam waktu bersamaan Contoh nya transaksi pembelian dapat diketahuinya seberapa besar kemungkinan seorang pelanggan akan membeli gula dan susu secara bersamaan [1].
Dalam  penelitian  ini  algoritma  yang  digunakan  adalah Frequent  Pattern  Growth ( FP-Growth )  yang merupakan pengembangan dari algoritma apriori yang sangat efesien dalam pencarian frequent itemset . Algoritma ini menyimpan informasi mengenai frequent itemset dalam bentuk struktur prefix-tree atau biasa disebut FP-Tree . Pada FP-Tree yang terbentuk dapat melihat data transaksi yang memiliki item yang sama, guna dapat mengurangi atau meminimalisir scan database secara berulang dalam proses mining dan dapat juga lebih cepat [2].
Untuk  mengetahui  pola  pembelian  konsumen  Toko  Miring  dalam  penelitian  ini  melakukan  proses  data mining , dari pola yang ditemukan tersebut akan menghasilkan sebuah informasi yang dapat dimanfaatkan pihak Toko  Miring  untuk  mutu  pelayanan  dan  mutu  penjualan  serta  memperoleh  keuntungan  dengan  meminimalisir kerugian.
Untuk permasalahan diatas penulis menggunakan teknik asosiasi yang tepat untuk menentukan barang yang sering  dibeli  bersamaan  berdasarkan  data  transaksi  pembelian  yang  terjadi  di  Toko  Miring.  Sebuah  algoritma Fraquent  Growth ( FP-Growth )  dalam keterkaitan data untuk mendapatkan hasil yang lebih baik. Implementasi data mining untuk memprediksi penjualan dan penempatan persediaan di Toko Miring menggunakan algoritma Fraquent  Growth ( FP-Growth ) yang memiliki hasil penelitian keterkaitan produk gula dan susu cukup kuat  di banding barang lain dengan nilai support 50% dan confidence 75% [3].

## 2. METODOLOGI PENELITIAN

## 2.1 Tahapan Penelitian
Dalam penelitian ini, beberapa tahapan harus dilakukan untuk menemukan hubungan antara satu barang dengan barang  lainnya.  Dimulai  dengan  tahap  pencarian,  pengumpulan  data,  metode  analisis  yang  digunakan,  hasil implementasi, melakukan pengujian, hingga menganalisis sistem yang telah diuji.
1. Tahapan pencarian, pada tahap ini akan dilakukan pencarian data langsung di  Toko Miring. Pencarian data dilakukan dengan proses wawancara dengan manajer Toko Miring.
2. Pencarian informasi berdasarkan segala sesuatu yang berhubungan dengan penelitian ini.
3. Pengumpulan data
4. Menganalisa  data  yang  sudah  didapat  dan  memasukkan  data  yang  sudah  dianalisa  dengan  menggunakan Miscrosoft Excel.
5. Mengimplementasikan peracangan yang sudah dilakukan kedalam perangkat lunak ( RapidMiner )
6. Melakukan pengujian terhadap sistem dengan memasukan data yang sudah di buat.
7. Melakukan analisa terhadap sistem yang telah diuji.

## 2.2 Identifikasi Awal
Identifikasi awal membantu membatasi algoritma fraquent growth ( fp-growth ) untuk berjalan sesuai dengan apa yang telah ditputuskan. Identifikasi awal ini menentukan batas minimum support dan minimum confidence yang digunakan untuk membuat aturan asosiasi ( Association Rule ) serta database transaksi penjualan yang digunakan untuk menguji algoritma frequent growth ( fp-Growth ).

## 2.3 Penerapan Algoritma Fraquent Growth (FP-Growth)
Pengujian  Algoritma frequent  growth ( fp-growth )  untuk  menemukan  pola  hubungan  2 itemset dalam  suatu database pada  transakasi  yang  terjadi  pada  waktu  yang  sama  dan  saling  terkait  dengan  peluang  50-60%  untuk membeli suatu item menggunakan rumus berikut :

## 1. Analisa Pola Frekuensi Tinggi
Pada tahap ini guna mencari kombinasi item yang memenuhi syarat minimum dari nilai support dalam database . Diperoleh dengan rumus berikut
Support (A) = jumlah transaksi mengandung A
Total transaksi (1)
Pada  rumus  tersebut  dijelaskan  bahwa  nilai support (A)  didapatkan  dengan  cara  mencari  jumlah  transaksi mengandung di bagi dengan total transaksi. Sementara itu, nilai support dari 2 item diperoleh dari rumus sebagai berikut.
Support ( A,B ) = P ( 𝐴 ∩ B) (2)
Support ( A,B ) = ∑ Transaksi mengandung A dan B
∑Transaksi (3)
Dari rumus diatas dijelaskan bahwa support (A, B) didapatkan dengan cara transaksi yang mengandung item A dan B di bagi dengan jumlah seluruh transaksi.

## 2. Pembentukan Aturan Asosiasi
Setelah semua pola frekuensi  tinggi  didapatkan barulah dicari  aturan asosiasi  yang memenuhi  syarat  minimum untuk confidence dengan menghitung confidence aturan asosiatif A − > B. Nilai confidence dari aturan diperoleh dari rumus berikut :
Confidence = P( B | A ) = ∑ Transaksi mengandung A dan B ∑Transaksi  mengandung A (4)
Pada rumus diatas dijelaskan bahwa confidence (A, B) diperoleh dengan cara data transaksi

## 3. HASIL DAN PEMBAHASAN

## 3.1 Pengolahan Data
Pengolahan  data  dilakukan  menggunakan  aplikasi database yaitu  Microsoft  Excel  2016.  Data real transaksi penjualan dapat dilihat pada gambar dibawah ini.
Gambar 1. Data Real Transaksi Penjualan Bulan Maret 2022
Selanjutnya  data real transaksi  dikompilasi  menjadi  bentuk  data tabular dan  data  transaksi  penjualan sembako  dikonversikan  kedalam  bentuk  1  dan  0 atau  bentuk  binominal.  1  jika  beli  obat,  0  jika  tidak.  Gambar dibawah menunjukkan hasil konversi data transaksi penjualan menjadi data tabular.
Gambar 2. Tabular Data Transaksi Penjualan Sembako
3.2 FP-Tree
Data Mining menggunakan algoritma Frequent Growth ( FP-Growth ) membutuhkan bantuan dalam membangun FP-Tree yang bertujuan untuk menentukan itemset yang sering digunakan. Pada fase data mining , diambil contoh ( sample ) data untuk membentuk FP-Tree . Contoh data yang diambil sebanyak 30 transaksi penjualan pada bulan Maret tahun 2022. Dengan batas minimum support 0.5 atau sama dengan 50%.
Tabel 1. 30 sample data transaksi bulan Maret 2022 TID Item 1 { A,D,E,G,H,K,L,P,Q,R,S,T } 2 { A,B,C,D,G,I,K,L,M,N,Q,S,T } 3 { A,B,C,D,E,F,G,H,I,J,K,L ,M,O,P,Q,R,S,T} 4 { A,B,C,D,E,G,J,K,L,M,N,Q,R,S,T} 5 {A,B,C,D,E,F,G,H,K,L,M,N,O,Q,R,S,T} 6 { A,B,D,G,H,K,L,M,P,Q,R,S} 7 {A,B,C,E,F,G,H,K,L,M,P,Q,R,S } 8 { A,B,D,F,H,K,L,Q,R,S } 9 {A,B,C,D,K,L,M,N,O,P,Q,R,S} 10 { A,C,D,F,G,K,L,M,Q,R,S } 11 {A,B,C,E,F,G,H,K,L,M,N,O,P,Q,R,S} 12 {A,B,C,D,E,G,H,K,M,N,P,Q,R,S,T } 13 { A,B,C,E,G,K,L,Q,R,S,T } 14 { A,B,C,D,E,G,H,M,N,P,Q,R,S } 15 { A,B,C,E,I,K,L,Q,R,S } 16 {A,B,C,G,H,L,N,Q,R,S } 17 { A,C,L,Q,R,S,T } 18 { A,B,C,E,J,M,N,O,Q,S } 19 { A,E,M,P,Q,S } 20 { A,C,M,N,Q,R,S,T } 21 { A,C,D,M,N,P,Q,R,S }
TID Item 22 { A,D,E,M,N,P,Q,R,S } 23 { A,C,E,J,M,N,Q,R,S } 24 { A,C,J,M,Q,R,S,T } 25 { A,C,E,I,J,L,M,N,Q,S,T } 26 { A,C,E,F,I,K,L,M,O,Q,S,T } 27 { A,I,J,K,L,M,N,Q,R,S,T } 28 { A,D,I,K,L,M,Q,R,S,T } 29 { A,D,I,M,Q,S } 30 { A,G,K,L,M,N,Q,R,S }
Untuk pencarian database tahap pertama digunakan untuk menghitung nilai support masing-masing item dan  memilih item yang  memenuhi  minimum support. Hasil  dari  pencarian database di  ketahui  frekuensi kemunculan tiap item yang ada dalam database serta mengurutkannya berdasarkan dengan frekuensi kemunculan item yang terbesar.
Table 2. Tabel Kemunculan Item Item Frekuensi A 30 Q 30 S 30 M 24 R 23 C 20 L 19 K 18 E 16 N 16 B 15 D 14 G 14 T 13 P 11 H 10 I 8 F 7 J 7 O 6 Tabel 3. Tabel Frequent List Item Frekuensi A 30 Q 30 S 30 M 24 R 23 C 20 L 19 K 18 E 16 N 16 B 15
Setelah  didapatkannya Frequent  List, kemudian  ubah  item  sesuai  Frequent  List  dengan  menghilangkan item D, G, T, P, H, I, F, J, O dan di urutkan dari yang terbesar hingga terkecil pada setiap item transaksi yang ada. Pembuatan FP-Tree berdasarkan ID Transaksi yang akan di beri inisial nomor urut untuk mempermudah proses pembentukan FP-Tree sesuai dengan yang tercantum pada tabel.
Tabel 4. Tabel transaksi yang telah disesuaikan dengan frequent list
TID Item 1 { A,Q,S,R,L,K,E }
TID Item 2 { A,Q,S,M,C,L,K,N,B } 3 { A,Q,S,M,R,C,L,K,E,B } 4 { A,Q,S,M,R,C,L,K,E,N,B } 5 { A,Q,S,M,R,C,L,K,E,N,B } 6 { A,Q,S,M,R,L,K,B } 7 { A,Q,S,M,R,C,L,K,E,B } 8 { A,Q,S,R,L,K,B } 9 { A,Q,S,M,C,L,K,N,B } 10 { A,Q,S,M,R,C,L,K } 11 { A,Q,S,M,R,C,L,K,E,N,B } 12 { A,Q,S,M,R,C,K,E,N,B } 13 { A,Q,S,R,C,L,K,E,B } 14 { A,Q,S,M,K,C,E,N,B } 15 { A,Q,S,R,C,L,K,E,B } 16 { A,Q,S,R,C,L,N,B } 17 { A,Q,S,R,C,L } 18 { A,Q,S,M,C,E,N,B } 19 { A,Q,S,M,E } 20 { A,Q,S,M,R,C,N } 21 { A,Q,S,M,R,C,N } 22 { A,Q,S,M,R,E,N } 23 { A,Q,S,M,R,C,E,N } 24 { A,Q,S,M,R,C } 25 { A,Q,S,M,C,L,E,N } 26 { A,Q,S,M,C,L,K,E } 27 { A,Q,S,M,R,L,K,N } 28 { A,Q,S,M,R,L,K } 29 { A,Q,S,M } 30 { A,Q,S,M,R,L,K,N }
Pembuatan FP-Tree diawali dari TID 1 yaitu { A,Q,S,R,L,K,E }.
Gambar 3. Hasil pembentukan FP-Tree setelah pembacaan TID 1
Setelah pembacaan TID 1 , selanjutnya dilakukan TID 2 yaitu {A,Q,S,M,C,L,K,N,B} sehingga membentuk lintasan {} -> M -> C -> L -> K -> N -> B dengan support count bernilai 1. Walaupun item A ada pada lintasan sebelumnya yaitu TID 1, tetapi karena prefix transaksi tidak sama, Maka TID 2 tidak dapat dipadatkan dan harus membuat lintasan baru.
Setelah  pembuatan FP-Tree selesai  maka  selanjutnya  dilakukan,  algoritma FP-Growth untuk  mencari semua  subsets  yang  memungkinkan  dengan  cara  membangkitkan conditional  FP-Tree dan  mencari frequent itemset.

## 3.3 FP-Growth
Dari perhitungan confidence terhadap pola yang terbentuk diatas, maka Assosiattion Rule yang memenuhi syarat confidence ≥ 0,75 adalah: K → C = 0,75 (jika konsumen membeli Rose Brand Bihun Kaldu Ayam 55Gr, maka membeli Beras Patin Premium 10Kg), H → G (jika konsumen membeli Sasa Tepung Bumbu Kentucky 75Gr maka membeli  Segitiga  Biru  Tepung  Terigu  900Gr),  G → P  (jika  konsumen  membeli  Segitiga  Biru  Tepung  Terigu 900Gr  maka  membeli  Enaak  Susu  Kental  Manis  Coklat  370Gr).  Untuk  membuktikan  kebenaran  hasil  analisa diperlukan sebuah proses pengujian untuk  menguji  kebenaran dari  hasil pengolahan data yang telah dikerjakan secara manual sebelumnya, untuk proses pengujian tersebut kita dapat menggunakan salah satu software aplikasi contohnya seperti Rapidminer, Adapun tampilannya sebagai berikut.
Gambar 5. FP-Growth Pada Rapidminer
Pada  gambar  tersebut  merupakan  proses  menghubungkan fp-growth ,  dan  proses  tersebut  telah  diatur minimum support dan confidence nya.
Gambar 6. Support dan Confidence Menggunakan Rapidminer dari Sample Data Transaksi Penjualan
Gambar 8. Association Rules Dari Rapidminer
Setelah  diuraikan  dari  rule  di  atas,  maka  bisa  diambil  kesimpulan  bahwasannya  konsumen  cenderung membeli item yang saling berhubungan seperti pada :  jika konsumen membeli Rose Brand Bihun Kaldu  Ayam 55Gr, maka membeli Beras Patin Premium 10Kg, dengan nilai confidence 0,75.

## 4. KESIMPULAN
Secara keseluruhan dari data sample transaksi penjualan diperoleh 155 Rule dari 101 rule asosiasi yang memenuhi support dengan  ambang  batas  50%,  Dari  rule  yang  diperoleh  didapatkan  sebuah  informasi  baru  tentang  pola pembelian konsumen. Dan juga bisa digunakan untuk menentukan keputusan persediaan barang dan memberikan paket diskon terhadap pola pembelian produk yang memiliki nilai confidence tinggi sedangkan support yang kecil., Dengan  Algoritma fp-growth dapat  membantu  perusahaan  memantau  stok  barang  yang  sering  dibeli  oleh konsumen sehingga tidak akan terjadi kelangkaan pasokan atau kehabisan.

## REFERENCE
[1] Kusrini and Emha Taufiq Luthfi, Algoritma Data Mining, 1st ed., Theresia Ari Prabawati, Ed. Yogyakarta: ANDI, 2009.
[2] Erwin, "Analisis Market Basket Dengan Algoritma Apriori dan FPGrowth," vol. 4, Juli 2009.
[3] Kennedi  Tampubolon,  Hoga  Saragih,  and  Bobby  Reza,  "Implementasi  Data  Mining  Algoritma  Apriori  Pada  Sistem Persediaan Alat-Alat Kesehatan," Informasi dan Teknologi Ilmiah (INTI), vol. 1, Oktober 2013.
[4] Nugroho Wandi, Rully A Hendrawan, and Ahmad Mukhlason, "Pengembangan Sistem Rekomendasi Penelusuran Buku dengan Penggalian Association Rule Menggunakan Algoritma Apriori (Studi Kasus Badan Perpustakaan dan Kearsipan Provinsi Jawa Timur)," JURNAL TEKNIK ITS, vol. 1, September 2012.
[5] Fajar Astuti Hermawati, Data Mining, 1st ed., Putri Christian, Ed. Yogyakarta: ANDI, 2013.
[6] David Samuel, "Penerapan Stuktur FP-Tree dan Algoritma FP-Growth dalam Optimasi Penentuan Frequent Itemset," Institut Teknologi Bandung, vol. 1, 2008.
[7] Juanta  Madus,  Afriyudi  ,  and  Irwansyah  ,  "Aplikasi  Penentuan  Waris  Pada  Perangkat  Mobile  Menggunakan  Java (J2ME)," Jurnal Ilmiah, April 2012.
[8] Nurjaya Mirwan, Hari Gusmita Ria, and Yusuf Durrachman, "Aplikasi Pencarian Makna Kata Dalam Bahasa Indonesia Dengan Teknologi Java 2 Micro Edition (J2ME)," 2006.
[9] Emha Taufiq Luthfi and Kusrini, Algoritma Data Mining. Yogyakarta: Andi Offset, 2009.
[10] Daniel T Larose, Discovering Knowledge in Data : An Introduction to Data Mining. New Jersey: John Wiley & Sons, 2005.
[11] D. P. Indini, S. R. Siburian, Nurhasanah, and D. P. Utomo, “Implementasi Algoritma DBSCAN untuk Clustering Seleksi Penentuan Mahasiswa yang Berhak Menerima Beasiswa Yayasan,” in Prosiding Seminar Nasional Sosial, Humaniora, dan Teknologi, 2022, pp. 325–331.
[12] D.  P.  Utomo  and  S.  Aripin,  “Penerapan  Algoritma  C5.  0  Untuk  Mengetahui  Pola  Kepuasan  Mahasiswa  di  Masa Pembelajaran Daring,” in Prosiding Seminar Nasional Riset Information Science (SENARIS), 2021, pp. 7–12.
[13] F. Telaumbanua, J. M. Purba, and D. P. Utomo, “Analysis of Online Learning Understanding Patterns at Budi Darma University Using the C5. 0 Algorithm,” IJICS (International J. Informatics Comput. Sci., vol. 5, no. 2, 2021.
[14] R.  Amelia  and  D.  P.  Utomo,  “Analisa  Pola  Pemesanan  Produk  Modern  Trade  Independent  Dengan  Menerepakan Algoritma Fp. Growth (Studi Kasus: Pt. Adam Dani Lestari),” KOMIK (Konferensi Nas. Teknol. Inf. dan Komputer), vol. 3, no. 1, 2019.