1. UKM Learning and Research Repository
2. Master Thesis / Tesis Master
3. Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Title:	Graph based association rules mining using triangle counting approach
Authors:	Yazan Alaya Jameel Al-Khassawne (P49112)
Supervisor:	Azuraliza Abu Bakar, Assoc. Prof. Dr.
Keywords:	Data mining Computer algorithms Universiti Kebangsaan Malaysia -- Dissertations Dissertations, Academic -- Malaysia
Issue Date:	14-Oct-2011
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.,“Certification of Master’s/Doctoral Thesis” is not available,Master Information Technology
Pages:	85
Call Number:	QA76.9.D343K483 2011 3 tesis
Publisher:	UKM, Bangi
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.