OCEAN: Fast Discovery of High Utility Occupancy Itemsets

摘要

Frequent pattern mining has been widely studied in the past decades and has been applied to many domains. In particular, numerical transaction databases, where not only the items but also the utility associated with them are available in user transactions, are useful for real applications. For example, customer mobile App traffic data collected by mobile service providers contains such information. In this paper, we aim to find frequent patterns that occupy a large portion of total utility of the supporting transactions, to answer questions like "On which mobile Apps do the customers spend most of their data traffic?" Towards this goal, we define a measure called utility occupancy to measure the contribution of a pattern within a transaction. The challenge of high utility occupancy itemset discovering is the lack of monotone or anti-monotone property. So we derive an upper bound for utility occupancy and design an efficient mining algorithm called OCEAN based on a fast implementation of utility list. Evaluations on real world mobile App traffic data and other three datasets show that OCEAN is efficient and effective in finding frequent patterns with large utility occupancy.