Efficient Algorithm for Mining High Utility Pattern Considering Length Constraints

Efficient Algorithm for Mining High Utility Pattern Considering Length Constraints

Kuldeep Singh (IIT (BHU), Varanasi, India)
Copyright: © 2019 |Pages: 27
DOI: 10.4018/IJDWM.2019070101

Abstract

High utility itemset (HUI) mining is one of the popular and important data mining tasks. Several studies have been carried out on this topic, which often discovers a very large number of itemsets and rules, which reduces not only the efficiency but also the effectiveness of HUI mining. In order to increase the efficiency and discover more interesting HUIs, constraint-based mining plays an important role. To address this issue, the authors propose an algorithm to discover HUIs with length constraints named EHIL (Efficient High utility Itemsets with Length constraints) to decrease the number of HUIs by removing tiny itemsets. EHIL adopts two new upper bound named sub-tree and local utility for pruning and modify them by incorporating length constraints. To reduce the dataset scans, the proposed algorithm uses transaction merging and dataset projection techniques. The execution time improvements ranged from a modest five percent to two orders of magnitude across benchmark datasets. The memory usage is up to twenty-eight times less than state-of-the-art algorithm FHM+.
Article Preview

Introduction

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:

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 16: 4 Issues (2020): Forthcoming, Available for Pre-Order
Volume 15: 4 Issues (2019): 3 Released, 1 Forthcoming
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing