High-utility itemset mining for subadditive monotone utility functions
share
High-utility Itemset Mining (HUIM) finds itemsets from a transaction database with utility no less than a user-defined threshold where the utility of an itemset is defined as the sum of the utilities of its items. In this paper, we introduce the notion of generalized utility functions that need not be the sum of individual utilities. In particular, we study subadditive monotone (SM) utility functions and prove that it generalizes the HUIM problem mentioned above. Moving on to HUIM algorithms, the existing algorithms use upper-bounds like `Transaction Weighted Utility' and `Exact-Utility, Remaining Utility' for efficient search-space exploration. We derive analogous and tighter upper-bounds for SM utility functions and explain how existing HUIM algorithms of different classes can be adapted using our upper bound. We experimentally compared adaptations of some of the latest algorithms and point out some caveats that should be kept in mind while handling general utility functions.
READ FULL TEXT