ABSTRAKSI: Penggalian kaidah asosiasi (mining association rules) merupakan salah satu proses data mining untuk menemukan pola dan aturan (rule) dari sekumpulan data yang besar. Pola-pola ini merupakan kumpulan item (itemset) yang sering muncul secara bersamaan (frequent itemset) dalam transaksi pada basis data. Proses pencarian frequent itemset membutuhkan waktu yang sangat lama, oleh karena itu diperlukan suatu algoritma yang bisa mengefisiensi waktu yang dibutuhkan.
Algoritma yang paling populer saat ini adalah algoritma apriori yang menggunakan support base pruning (membuang ruang pencarian dengan batasan nilai support). Algoritma ini memiliki kelemahan ketika kardinalitas pada longest frequent itemset berupa k, membutuhkan sebanyak k pembacaan basis data dan memiliki sifat computation-intensive dalam membangkitkan kandidat itemset dan penghitungan nilai support, khususnya untuk aplikasi yang memiliki nilai support yang sangat rendah dan atau item yang sangat banyak.
Algoritma Cut Both Ways (CBW) menggunakan gabungan beberapa teknik dan menggunakan cutting level (?) untuk membagi ruang pencarian menjadi dua bagian. Strategi top-down untuk menemukan frequent itemset yang berada dibawah cutting level dikombinasikan dengan strategi pencarian breadth first search dan horizontal counting untuk penghitungan nilai support. Sedangkan bottom-up untuk menemukan frequent itemset yang berada diatas cutting level dikombinasikan dengan depth first search dan vertical intersection. Nilai cutting level merupakan nilai rata-rata dari kardinalitas frequent itemset.
Pada tugas akhir ini akan mengimplementasikan proses pencarian frequent itemset dengan menggunakan algoritma Apriori dan CBW. Kemudian membandingkan kinerjanya dengan menggunakan beberapa parameter nilai support.Kata Kunci : mining association rules, itemset, frequent itemset, support, support base pruning, longest frequent itemset, computation-intensive, cutting level, top-down, bottom-up, breadth first search, dept first search, vertical intersection.ABSTRACT: Mining association rules is a data mining process to find rule and pattern from a large database. The pattern can be frequent itemset from the transaction of databases. Frequent itemset generation is most time-consuming process, so we need an algorithm that can be eficient a time consuming.
A most popular algorithm is Arpriori which use support base pruning to prune a vast amount of non-candidate itemsets. This algorithm has disadvantages when the cardinality of longest itemset is k, apriori needs k passes of database scan, and it has. In addition, the apriori algorithm is computation-intensive in generating the candidate itemsets and counting the support values, especially for applications with very low support treshold and/or a vast amount of items.
Cut Both Ways (CBW) combine a various technic and use cutting level (?) to divide a search space into two different part. Top-down strategy combined with breadth first search and horizontal counting, are used to find frequent itemset at below of the cutting level. In the other hand, bottom-up strategy combined with depth first search and vertical intersection, are used to find frequent itemset at upper of the cutting level. Cutting level is an average cardinality of frequent itemsets, expecting that most of the frequent itemsets will apear in this level.
In this final project will implement frequent itemset generation using Apriori and CBW algorithm. Then, compare its performance by using different parameter of minimum support.Keyword: mining association rules, itemset, frequent itemset, support, support base pruning, longest frequent itemset, computation-intensive, cutting level, top-down, bottom-up, breadth first search, dept first search, vertical intersection.