Penggalian Top-K Closed Frequent Itemsets Berbasis Algoritma Pemetaan Transaksi

ER, Ngurah Agus Sanjaya (2008) Penggalian Top-K Closed Frequent Itemsets Berbasis Algoritma Pemetaan Transaksi. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 5105201006-Master_thesis.pdf Restricted to Repository staff only Download (34MB)

Abstract

Penggalian kaidah asosiasi sering kali menghasilkan frequent itemsets dalam jumlah yang besar. Penelitian-penelitian terkini telah memberikan suatu alternatif baru berupa penggalian top-k closed frequent itemsets dengan panjang minimum tertentu yang dapat memperkecil ruang pencarian. Di samping itu, nilai minimum support yang telah ditentukan di awal tidak lagi digunakan karena penentuan minimum support sangat tergantung pada karakteristik set data yang digunakan. Dalam penelitian ini dikembangkan suatu algoritma penggalian top-k closed frequent itemsets dengan panjang minimum tertentu yang ditentukan oleh pengguna berbasis algoritma pemetaan transaksi. Proses dimulai dengan pembentukan pohon transaksi (transaction tree) tanpa penentuan minimum support. Dalam pembentukan pohon transaksi, algoritma closed node count digunakan untuk menaikkan minimum support secara dinamis dan memangkas subtree yang tidak frequent (jarang muncul). Setelah pohon transaksi terbentuk, suatu algoritma yang disebut descendant sum digunakan untuk menaikkan minimum support dan memangkas pohon transaksi lebih lanjut. Item-item yang tersisa pada pohon transaksi kemudian dipetakan ke dalam suatu daftar interval transaksi. Item-item yang sama juga digunakan untuk membangun pohon leksikografi (lexicographic tree). Setiap simpul pada pohon leksikografi merupakan satu kesatuan item yang diurutkan secara menurun berdasarkan nilai support. Penggalian top-k closed frequent itemsets dilakukan dengan mengiriskan daftar interval pada pohon leksikografi. Proses penggalian dilakukan dengan menggunakan algoritma depth first search, dimulai dari simpul-simpul yang terletak pada level yang lebih besar atau sama dengan panjang minimum yang diberikan. Suatu proses verifikasi kemudian digunakan untuk menentukan apakah suatu itemset bersifat closed atau tidak. Hasil uji coba menunjukkan bahwa algoritma yang dikembangkan berhasil membangun pohon transaksi tanpa menentukan minimum support terlebih dahulu. Waktu komputasi dan memori yang diperlukan cenderung berbanding lurus dengan nilai top-k yang diberikan, sedangkan pengaruh nilai panjang minimum itemset terhadap waktu komputasi dan penggunaan memori pada data yang diuji coba bervariasi. Proses pembentukan pohon transaksi menghabiskan waktu paling besar dibandingkan dengan waktu yang diperlukan untuk pembuatan daftar interval transaksi dan penggalian pada pohon leksikografi.
==================================================================================================================================
Association rule mining often produces a large number of frequent itemsets. Recent studies have proposed a new alternative for mining top-k closed frequent itemsets with a certain minimum length to reduce the search space. In addition, a predetermined minimum support value is no longer required because its determination depends heavily on the characteristics of the dataset used. In this research, an algorithm for mining top-k closed frequent itemsets with a user-defined minimum length is developed based on a transaction mapping algorithm. The process begins with the construction of a transaction tree without specifying a minimum support value. During the construction of the transaction tree, an algorithm called closed node count is employed to dynamically increase the minimum support and prune infrequent subtrees. After the transaction tree is constructed, another algorithm called descendant sum is used to further increase the minimum support and prune the transaction tree. The remaining items in the transaction tree are then mapped into a transaction interval list. These items are also used to construct a lexicographic tree. Each node in the lexicographic tree represents a set of items ordered in descending order according to their support values. The mining of top-k closed frequent itemsets is performed by intersecting the interval lists along the lexicographic tree. The mining process uses a depth-first search algorithm, starting from nodes whose levels are greater than or equal to the given minimum length. A verification process is then used to determine whether an itemset is closed. Experimental results show that the developed algorithm successfully constructs a transaction tree without requiring a predetermined minimum support value. The required computation time and memory tend to increase proportionally with the given top-k value, whereas the effect of the minimum itemset length on computation time and memory usage varies across the tested datasets. The construction of the transaction tree consumes the largest amount of computation time compared with the time required to create the transaction interval list and perform the mining process along the lexicographic tree.

Item Type:	Thesis (Masters)
Additional Information:	RTIf 005.1 Ngu p
Uncontrolled Keywords:	pohon transaksi, pemetaan transaksi, top-k closed frequent itemsets, transaction tree, transaction mapping, top-k closed frequent itemsets
Subjects:	Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Information Technology > Informatics Engineering > 55101-(S2) Master Thesis
Depositing User:	magang .
Date Deposited:	18 Sep 2026 03:44
Last Modified:	18 Sep 2026 03:44
URI:	http://repository.its.ac.id/id/eprint/144667

Actions (login required)

View Item