Optimizing Search Space Pruning in Frequent Itemset Mining With Hybrid Traversal Strategies-A Comparative Performance on Different Data Organizations
B. Kalpana, Ruth Naveena Nadarajan · 2007
The task of finding frequent itemsets in a dataset forms the computationally intensive task in association rule mining. The last decade has witnessed a number of state-of-art strategies directed at the Frequent Itemset Mining (FIM) problem. Some of these are hybrid which combine the desirable characteristics of several algorithms. The proposed hybrid strategies employ intelligent heuristics to optimally switch between a bottom up and top down phase to reduce the search space by almost fifty percent.In this paper the performance of the strategies are compared on two dataset organizations. Association rule mining was originally applied in Market Basket Analysis which aims at understanding the behaviour and shopping preferences of retail customers. The knowledge is used in product placement, marketing campaigns and sales promotions.Besides the retail sector, the market basket analysis framework is also being extended to the health and other service sectors. The application of Association rule mining now extend far beyond Market Basket Analysis and includedetection of network intrusion, attacks from the logs of web server and prediciting user traversal patterns on the web. FIM algorithms could be broadly classified as candidate generation algorithms or pattern growth algorithms. Within these categories further classification can be done based on the traversal strategy and data structures used.Apart from these several hybrid algorithms which combine desirable features of different algorithms have been proposed. Apriori Hybrid, VIPER,Max Eclat, KDCI are some of them. Our work has been motivated by the Eclat and Maxeclat(20) ,which is a hybrid strategy . We propose two hybrid strategies which make an intelligent combination of a bottom up and top down search to rapidly prune the search space.The intelligence gained from each phase is powered to optimally exploit the upward and downward closure properties .The strategies are found to outperform the Eclat and Maxeclat as indicated in section VII. In this paper we give a comparitive performance of the strategies on Tidset and the Diffset organizations. Diffsets(21) have