ANALISIS DAN IMPLEMENTASI ALGORITMA FREQUENT PATTERN GROWTH* (FP-GROWTH*) UNTUK MENDAPATKAN FREQUENT ITEMSET PADA DATA MINING ASSOCIATION RULE THE ANALYSIS AND IMPLEMENTATION OF FREQUENT PATTERN GROWTH* (FP-GROWTH*) ALGORITHM TO OBTAIN FREQUENT ITEMSET IN

ABSTRAKSI: Masalah utama pada data mining association rule adalah bagaimana menemukan kaidah asosiasi yang mengidentifikasi keterhubungan diantara kumpulan item. Ada dua langkah yang dilakukan untuk mendapatkan kaidah asosiasi : mencari frequent itemset dan membangkitkan kaidah asosiasi dari frequent itemset tersebut. Karena proses mendapatkan frequent itemset membutuhkan proses komputasi yang lama, maka masalah ini menjadi fokus dalam berbagai penelitian.Diantara algoritma pencarian frequent pattern, FP-Growth menerapkan strategi pencarian dengan menggunakan struktur yang sederhana dan memiliki kinerja yang tinggi karena hanya memerlukan dua kali pemeriksaan pada basis data. Selanjutnya, dilakukan perbaikan pada pendekatan pattern-growth untuk mendapatkan kinerja yang lebih baik pada proses pencarian pattern. FP-Growth* merupakan teknik baru berbasis array yang mengurangi penelusuran pada FP-tree. Tugas akhir ini mengimplementasikan dan menyajikan hasil eksperimen dari kedua algoritma ini menggunakan Borland Delphi 7.Hasil eksperimen menunjukkan bahwa algoritma FP-Growth* lebih cepat dibandingkan algoritma FP-Growth terutama pada dataset sparse. Akibat penggunaan teknik array, FP-Growth* menggunakan memori lebih besar dibandingkan FP-Growth tetapi ukuran array yang digunakan jauh lebih kecil dibandingkan ukuran FP-tree.Kata Kunci : Data mining, frequent itemset, FP-tree, FP-growth, FP-growth*.ABSTRACT: The main problem in data mining is the discovery of association rules that identify relationships among sets of items. There are two steps in mining association rules: finding the frequent itemsets and generating association rules from them. Since the mining of frequent itemsets is computationally expensive, most of the research attention has been focused on it.Among frequent pattern discovery algorithms, FP-Growth employs search strategy using compact structure resulting in a high performance algorithm that requires only two database passes. Hereinafter, further improvements can be made to the pattern-growth approach for better performance of the mining process. The FP-Growth* is a novel array-based technique that reduces the need to traverse FP-tree. This final project implement and present experimental result of these two algorithm build in Borland Delphi 7.The result of experiment shows that the FP-growth* algorithm run faster than FP-Growth especially for sparse datasets. Due to the use of array technique, FP-Growth* uses more memory than FP-Growth but far smaller than the size of FP-tree.Keyword: Data mining, frequent itemset, FP-tree, FP-Growth, FP-Growth*