Please use this identifier to cite or link to this item:
https://ptsldigital.ukm.my/jspui/handle/123456789/476364Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.advisor | Azuraliza Abu Bakar, Professor Dr. | - |
| dc.contributor.author | Al-Khassawne Yazan Alaya Jameel (P49112) | - |
| dc.date.accessioned | 2023-10-06T09:17:06Z | - |
| dc.date.available | 2023-10-06T09:17:06Z | - |
| dc.date.issued | 2011-10-14 | - |
| dc.identifier.other | ukmvital:84157 | - |
| dc.identifier.uri | https://ptsldigital.ukm.my/jspui/handle/123456789/476364 | - |
| dc.description | Association Rules Mining (ARM) is one of data mining task that finds frequent item sets from large transaction database. Searching is the NP-hard problem in ARM since the algorithm needs to search for all possible frequent items before the association rules are generated. Because of the enormous amount of data stored, it was necessary to develop powerful algorithm to deal with data for ARM. Several researches uses graph based representation for ARM of the transaction data to optimize the searching for the frequent patterns. In graph theory, there is an area of graph mining called Triangle Counting Approach. Triangle is the most basic non trivial subgraph. It is a three node fully connected subgraph. Triangle graph has been currently used to uncover the hidden thematic structure of the web and as a feature to assist the classification of web documents. In this approach, the appropriate set of triangles is computed as sub graphs that are believed to be the best representing the whole graph. Searching for triangles that can preserve the important knowledge that the graph holds is critical. The triangle counting approach has not yet used in the graph based ARM algorithm. Therefore, the aim of this study is to adopt the Triangle Counting approach in the graph based ARM. An algorithm of triangle counting for graph based ARM is proposed in order to prune the graph in the search for frequent item sets. Two important stages involved, i) development of the Triangle Counting algorithm to find numbers of triangles and, ii) development of ARM scheme from the triangles obtained in (i). The triangle counting algorithm is based on creating the nested adjacent matrix for the graph and counting the triangles. The De-Morgan Laws is used to create the new graph contains only the nodes and edges of triangles. The second stage involves, the use of the triangles using the bit vector representation obtained from stage one to generate the frequent items thus the association rules. The experiment is conducted towards several benchmark datasets and compared with the standard Apriori and Graph Based ARM algorithm. The performance is measured in terms of the execution time and the accuracy of the rules. The experimental results showed that the execution time of generating association rules is reduced with comparable quality of rules when compared with the previous approaches. The used of Bit-Vector to represent the pruned graph has reduced significantly the used of memory and the multiple scans of database can be avoided. The integration of the triangle counting approach with the graph based ARM has shown the potential improvements in the ARM research. The most important aspect to consider in this study is the preservation of important knowledge yet mining within the pruned search space.,Perlombongan petua sekutuan (PPS) ialah satu dari fungsi perlombongan data yang mencari set item yang kerap dari pangkalan data transaksi yang besar. Gelintaran ialah masalah NP-hard dalam PPS kerana algoritma perlu menggelintar semua item kerap yang mungkin sebelum petua sekutuan boleh dijana. Oleh kerana sejumlah data yang disimpan, algoritma yang berupaya menangani data yang untuk PPS sangat diperlukan. Beberapa penyelidikan menggunakan pewakilan berasaskan graf untuk PPS data transaksi untuk mengoptimumkan pencarian corak kerap. Dalam Teori Graf, terdapat satu bidang dalam perlombongan data yang dipanggil Pendekatan Pengiraan Segitiga. Segitiga ialah subgraf yang paling asas. Ia merupakan graf terhubung sepenuhnya dengan tiga nod. Graf segitiga telah diunakan untuk meneroka struktur tematik tersembunyi dalam web dan sebagai fitur untuk membantu pengelasan dokumen web. Dalam pendekatan ini, set segitiga yang sesuai dikira sebagai sub graf yang dipercayai yang terbaik mewakili keseluruhan graf. Gelintaran keatas segitiga yang boleh mengekalkan penngetahuan penting yang disimpan oleh graf adalah kritikal. Pendekatan pengiraan segitiga ini belum digunakan dalam kajian PPS berasaskan graf. Oleh itu, kajian ini bertujuan menggunakan pendekatan pengiraan segitiga untuk PPS berasaskan graf. Satu algoritma pengiraan segitiga untuk PPS berasaskan graf dicadangkan untuk pengurangan graf dalam pencarian set item kerap. Dua langkah penting terlibat, i) pembangunan algoritma pengiraan segitiga untuk mendapatkan sejumlah segitiga dan, ii) pembangunan skema PPS dari segitiga yang diperolehi dari (i).Algoritma pengiraan segitiga berdasarkan pembentukan matriks bersebelahan tersarang untuk graf dan pengiraan segitiga. Petua De Morgan digunakan untuk membentuk graf baru yang mengandungi hanya node dan laluan segitiga. Langkah kedua melibatkan penggunaan segitiga yang menggunakan pewakilan vector bit yang diperolehi dari langkah pertama untuk menjana item kerap dan seterusnya petua sekutuan. Ujikaji dijalankan keatas beberapa set data piawai dan dibandingkan dengan algoritma Apriori piawai dan algoritma PPS beerasaskan graf. Prestasi algoritma diukur dengan masa larian dan ketepatan petua. Hasil ujikaji menunjukkanmasa larian untuk penjanaan petua sekutuan dikurangkan dengan ketepatan petua yang standing berbanding dengan algoritma perbandingan. Penggunaan vector bit untuk mewakili graf yang ringkas telah mengurangkan penggunaan memori secara signifikan dan imbasan berbilang kali ke pangkalan data juga dapat dielakkan.Integrasi antara pendekatan pengiraan segitiga dengan PPS berasaskan graf menunjukkan potensi pembaikan dalam penyelidikan PPS. Aspek yang paling penting dipertimbangkan dalam kajian ini ialah pemeliharaan pengetahuan penting ketika melombong didalam ruang gelintaran yang kecil.,Master/Sarjana | - |
| dc.language.iso | eng | - |
| dc.publisher | UKM, Bangi | - |
| dc.relation | Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat | - |
| dc.rights | UKM | - |
| dc.subject | Data mining | - |
| dc.subject | Computer algorithms | - |
| dc.title | Graph based association rules mining using triangle counting approach | - |
| dc.type | theses | - |
| dc.format.pages | 85 | - |
| dc.identifier.callno | QA76.9.D343K483 2011 tesis | - |
| dc.identifier.barcode | 001962 | - |
| Appears in Collections: | Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| ukmvital_84157+SOURCE1+SOURCE1.0.PDF Restricted Access | 1.94 MB | Adobe PDF |  View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.