EFFICIENT ALGORITHM FOR FREQUENT PATTERN MINING AND IT’S APPLICATION IN PREDICTING PATTERN IN WEB USAGE DATA

Abstract

Frequent Pattern Mining, the task of finding sets of items that frequently occur together in a dataset, has been at the core of the field of data mining for the past many years. With the tremendous growth of data, users are expecting more relevant and sophisticated information which may be lying hidden in the data. Data mining is often described as a discipline to find hidden information in a database. It involves different techniques and algorithms to discover useful knowledge lying hidden in the data. In this thesis, we propose an efficient algorithm for finding the frequent patterns which is the extension of IP tree algorithm. Also we prove its effectiveness over various previous algorithms like Aprioi, FPGrowth, CATS tree, Can tree. Apriori is the first popular algorithm for frequent patterns but it makes use of multiple database scan that make it inefficient for large database. To improve the drawback of Apriori algorithm, prefix-tree based algorithms have become popular. However most of the prefix tree based algorithms still suffer with either more execution time or take more memory. For e.g. FP Growth algorithm still requires two database scans and Can tree takes large memory. Our proposed algorithm constructs a FP tree like compact tree structure only for the frequent items in the database with only one database scan. It firstly store transactions in a lexicographic order tree and then restructured the tree by sorting the frequent items in a frequency-descending order and prune the infrequent items from each path. We evaluate the performance of the algorithm using both synthetic and real datasets, and the results show that the proposed algorithm is much more time efficient and take less memory than the previous algorithms.