An efficient algorithm to discover colossal closed itemsets in high dimensional data

Abstract

The current trend of data collection involves a small number of observations with a very large number of variables, known as high dimensional data. Mining these data produces an explosive number of smaller item sets which are less important than colossal (large) ones. As the trend in Frequent Itemset Mining is moving towards mining colossal item sets, it is important to understand the challenges in order to formulate a better method that is faster in running time, more scalable and able to produce useful and interesting knowledge. For this reason, this thesis has proposed two new algorithms; RARE and RARE II, which mine colossal closed item sets. Both algorithms apply a minimum cardinality threshold to limit the search space and a closure computation method that does not require storage of previously discovered item sets for duplicates checking. These approaches improved both memory and time requirement of the algorithms to finish mining tasks. Algorithm RARE searches the row set lattice in breadth-first manner which resulted to a reduced itemset intersections compare to other state-of-the-art algorithms, CARPENTER and IsTa. Although the different threshold used in CARPENTER and IsTa make direct comparison with RARE difficult, RARE proved to be better. In terms of memory usage, RARE need only one-third of CARPENTER’s and one-tenth of IsTa’s, while require the least running time to discover 100% of closed item sets in the dataset. Meanwhile, RARE II further reduced itemset intersections by evaluating only the closed row sets in order to mine the next closed item sets, which resulted to an improved run time by more than 50% compare to RARE.