Article Preview
TopIntroduction
Frequent itemset mining (FIM) (Agrawal & Srikant, 1994; Han, Pei, & Yin, 2000; Zaki, 2000; Uno, Kiyomi, & Arimura, 2004; Singh, Shakya, & Biswas, 2015; Singh, Shakya, & Biswas, 2016b) is one of the fundamental research topics in data mining. Traditional FIM, assumes that item cannot appear more than once in each transaction, and each item has same importance like weight, unit profit, etc. Hiding importance and quantity of an item may also hide some important or relevant information. Hence, FIM not only loses valuable and important information of the itemsets but also generates many irrelevant and unimportant frequent itemsets. To address the issue of quantity, multi-frequency based frequent itemset mining algorithm are proposed Singh, Shakya, and Biswas, 2016a, but only quantity-based mining loose importance of the items. Hence, high utility itemsets (HUIs) (Liu & Qu, 2012; Fournier-Viger, Wu, Zida, & Tseng, 2014; Liu, Wang, & Fung, 2016; Singh, Singh, Kumar, Shakya, & Biswas, 2018) mining emerges as an important topic in data mining. The main goal of HUIs mining is to discover itemsets having a high utility. In HUIs mining, each item can appear more than once in each transaction (e.g., quantity). It also assumed that each item has a utility value (e.g., price or profit).
HUIs mining is essential in several business and scientific applications such as commerce (Shie, Hsiao, Tseng, & Yu, 2011), web-click stream analysis (Chu, Tseng, & Liang, 2008), mobile e-commerce (Li, Huang, Chen, Liu, & Lee, 2008), cross marketing (Yen, & Lee, 2007), user behavior analysis (Shie, Yu, & Tseng, 2013). HUIs are also used to earn the better profit by promoting the sales. However, HUIs mining is more difficult and complex problem compare to FIM mining because HUIs mining does not support downward closure property. Hence, prune the search space in HUIs mining is the difficult task. To tackle this problem, Ying Liu et al. proposed the concept of transaction weighted utility (TWU) to facilitate the performance of the mining task (Liu, Liao, & Choudhary, 2005). However, the TWU is used for overestimation of true or actual utility of an itemset. However, TWU model leads to waste lots of time to compute the utility for itemsets because their level-wise candidate generation. Therefore, algorithms for HUIs mining are generally slower than FIM algorithms.
To overcome the drawbacks of traditional HUIs algorithms, concise HUIs mining algorithms have been introduced. Concise HUIs are more interesting and actionable because they are lossless representation of HUIs. Concise HUIs can be found using closed or length constraints. In length-based concise HUIs mining, the additional length-based thresholds are introduced. This idea of length constraints with minimum utility (min_util) is applicable in many scenarios. Minimum length (min_length) and maximum length (max_length) constraints with min_util HUIs mining serves as a promising solution for the limitation of traditional HUIs mining algorithms. Therefore, length-based HUIs mining is essential for many applications. However, developing efficient algorithms for mining such itemsets is not an easy task. It poses four major challenges as discussed below.
First, the itemsets in HUIs mining neither support to monotonic property nor to anti-monotonic property. FIM techniques with length constraints rely on anti-monotonicity property. Hence, FIM techniques cannot be directly applied to HUIs mining with length constraints.
Second, HUIs mining algorithms consume more time and memory compare to FIM algorithms. Hence, a compact dataset storage structure and an efficient pruning strategy are required.
Third, how to incorporate the concept of length constraints with the HUIs mining. And how to overestimate the upper bounds with length constraints.
Lastly, how to incorporate the length constraints (min_length and max_length) with min_util threshold.
To address these challenges, an efficient utility mining algorithm is needed. The key contributions of this paper are as follows: