On-shelf utility mining from transaction database

Abstract As an important technique for dealing with transaction database in the field of data mining, utility-driven mining can be used to discover useful patterns (i.e., itemsets, sequences) which have a high utility. However, it has a bias towards the item/object combinations which have more exhibition period since they have more opportunity to generate a high utility. To address this, the on-shelf time period of items need to be considered, thus on-shelf utility mining (OSUM) can be applied in the application which is more closer to the actual situation. Currently several models have been proposed to deal with the OSUM problem, but they still suffer from the requirement that it needs to maintain a massive candidates in memory and to scan database many times. In this paper, we propose two effective one-phase algorithms named OSUMI (On-Shelf Utility Mining from transactIon database) and OSUMI + (the improve version of OSUMI). Both OSUMI and OSUMI + search all itemsets as a set-enumeration tree and discover the on-shelf itemsets with high utility in a more practical way. More precisely, in order to avoid the problems of high memory consumption, two algorithms apply some properties of the concept of on-shelf utility. Besides, two upper-bounds named subtree utility and local utility are applied to early filter out unpromising patterns and then prune the search space. Finally, an extensive experimental study on several real on-shelf datasets shows that our proposed algorithms can be significantly faster than the state-of-the-art algorithm.