High utility itemsets mining with negative utility value: A survey

2.1. Preliminaries and definitions

Let I = {i₁, i₂, …, i _n } be a set of distinct items. Each item i is associated with an external utility (price or unit profit, etc.), denoted as EU (i), which may be the unit profit or price of item i. Each item i is associated with internal utility (quantity) in transaction T _j , denoted as IU (i, T _j ).

Let us consider the transactional dataset shown in Table 1, which will be used as running example. This dataset contains seven transactions (T₁, T₂, …, T₇). It contains five items A, B, C, D and E. The external utilities of items are presented in Table 2. For example, the transactional dataset, T₁ contains four items A, B, D, E and has internal utility 2, 2, 1, 3 respectively. The external utilities of these items A, B, C, D and E are, respectively, 2, -3, 1, 4 and 1. Thus, item B is sold at a loss.

Definition 2.1 (Utility of an item). The utility of an item i in a transaction T _j is denoted as U (i, T _j ) and is defined as U (i, T _j ) = IU (i, T _j ) ×EU (i). The utility of an itemset X in a transaction T _j is denoted as U (X, T _j ) and defined as U (X, T _j ) = ∑_i∈XU (i, T _j ).

For example, the utility of an item A in transaction T₁ is 2 × 2 =4. The utility of an itemset {A, D} in transaction T₁ is 4 + 4 =8. Note that, U (X) may be negative, which means that itemset X has generated a loss (a negative profit). For example, if X is a single item with negative unit profit, then U (X) will always be negative.

Definition 2.2 (Utility of an itemset in dataset). The utility of an itemset X in dataset D is denoted as U (X) and is defined as U (X) = ∑_{X⊆T j ∧T j ∈D} U (X, T _j ).

For example, utility of an itemset {A, D} is U (AD, T₁) +U (AD, T₆) = 8 + 12 = 20.

Definition 2.3 (Transaction utility). The transaction utility of a transaction T _j is denoted as TU (T _j ) and is defined as TU (T _j ) = ∑ U (i, T _j ).

For example, TU of T₁ is U (A, T₁)+ U (B, T₁)+ U (D, T₁) + U (E, T₁) = 4+ (-6) + 4 + 3 =5. Third column of Table 3 shows TU for the running example.

Definition 2.4 (Transaction weighted utilization). The transaction weighted utilization (TWU) of an itemset X is denoted as TWU (X) and is defined as TWU (X) = ∑_{X⊆T j ∧T j ∈D} TU (T _j ).

For example, TWU of item A is T₁+ T₅+ T₆ = 23. TWU value of each item is shown in Table 4.

Property 2.1 ( Pruning using TWU). If TWU of an itemset X is less than minimum utility (min _ util) threshold, then itemset X and all of its supersets are non-HUIs. The min _ util is user defined threshold value.

HUIs mining algorithms use TWU for fulfilling the anti-monotonic property.

Definition 2.5 (High utility itemsets). An itemset X is called a HUIs if utility of X is no less than min _ util. Otherwise, itemset X is a low-utility itemset.

Table 5 shows the HUIs for the running example where min _ util is 10.

The traditional HUIs mining algorithms only can handle positive utility values and can utilize TWU based Property 2.1 to prune the search space. The positive utility mining algorithms cannot be directly applied where negative utility is considered [7]. To handle the problem of mining HUIs with negative utility, HUINIV-Mine utilizes redefined transaction utility (RTU) as well as redefined TWU as described below.

Definition 2.6 (Redefined transaction utility). The redefined transaction utility is denoted as RTU (T _j ) for transaction T _j and is computed as RTU (T _j ) = ∑_EU(x)>0 U (x, T _j ). To calculate RTU, items must be sorted according to descending order to their utility values [7].

For the running example, RTU of T₁ is computed as RTU (T₁)= U (A, T₁) + U (D, T₁) + U (E, T₁) = 4 +4 + 3 = 11. We did not include utility of item B because we calculate RTU by only adding the positive items. RTU (X) ≥ TU (X), because, TU is the summation of all items in a transaction includes negative items whereas RTU is the summation of items have positive utility. Table 3 shows the TU and RTU value of each transaction.

Definition 2.7 (Redefined transaction weighted utility). The redefined transaction weighted utility (RTWU) of an itemset X is defined as RTWU (X) =∑_{X⊆T j ∈D} RTU (T _j ) [7].

For example, RTWU of T₁ is RTU (T₁)+ RTU (T₅)+ RTU (T₆) =11 + 4 +17 = 32. RTWU value of each item is shown in Table 4.

Property 2.2 (Pruning using RTWU) . The RTWU downward closure property states that any superset of a low RTWU itemset is low utility. For an itemset X, if the RTWU (X) < min _ util then X is not a HUIs and all the supersets of itemset X are also not HUIs. The detailed proof of this property can be found in [7, 30].

For example, RTWU of all the items is shown in Table 4.

2.3. Traditional high utility itemsets mining algorithms

Traditional HUIs mining algorithms generate rules from transactional datasets. Transactional datasets usually have a large number of distinct single items and their combinations is also a huge number of itemsets. Therefore, basic HUIs mining algorithms need some upper-bound or search space pruning strategies. In order to address this issue, Liu et al. proposed an algorithm Two-Phase algorithm [34] which proposed TWU based pruning strategy. Algorithms [25, 55] use two-phase model and TWU based pruning strategy. All these two-phase based algorithms suffer from multiple dataset scans and expensive joining operations. In order to overcome these limitations, in 2010, Tseng et al. proposed a tree-based algorithm named UP-Growth [50]. UP-Growth follows popular FIM algorithm FP-Growth [20]. Later on, some other tree-based algorithms are proposed such as [3, 59]. These algorithms are the improved versions of the basic UP-Growth algorithm. UP-Growth or UP-tree based algorithms still suffer from the generation of a lot of candidate itemsets and multiple dataset scans.

To overcome the limitations of tree-based algorithms, Liu et al. proposed HUI-Miner algorithms [32] which used utility-list based data structure. Later on, variations of utility-list and extension of HUI-Miner are proposed to improve the performance such as FHM [16] and HUP-Miner [21]. But utility-list algorithms suffer from generating the candidate itemsets which are not present in datasets. Utility-based algorithms perform worst when utility-list contains an entry for each transaction. To target these issues, Zida et al. proposed an algorithm EFIM [66]. It uses pattern-growth approach to mine HUIs. All the above-discussed algorithms do not work with negative utility value. In real-life, items may occur with negative utility value. To address this problem, HUIs with negative utility based algorithms have been presented. We discuss HUIs mining with negative utility algorithms in the next section.

Level-wise algorithms follow Apriori-like approach for generating candidate such as joining. k-itemsets can generates (k + 1)-candidates. Level-wise approach generates itemsets of length k before length (k + 1)-itemsets. Only two (HUINIV-Mine and TS-HOUN) algorithms are available in the literature to mine HUIs with negative utility using level-wise approach.

HUINIV-Mine: In 2009, Chu et al. proposed an algorithm named HUINIV-Mine [7]. It is the first level-wise algorithm that considers negative utility. It is an extension of the Two-Phase algorithm. It mines HUIs with negative items by following Two-Phase model. HUINIV-Mine presents RTWU based overestimation and pruning strategy. The author demonstrated that HUIs mining with negative utility must have at-least one positive item. Otherwise, utility would be negative and it would not be a HUIs. It is a level-wise algorithm. Hence, it needs to maintain a large number of itemsets in memory to find larger itemsets. It scans dataset three times and mines HUIs.

TS-HOUN: In 2014, Lan et al. proposed an algorithm named TS-HOUN [24]. It is the first algorithm that mines HUIs with negative utility and on-shelf time periods. Using on-shelf time periods, the actual utility values of itemsets in a temporal dataset can be accurately evaluated. Most algorithms consider that items have the same shelf time, i.e., that all items are on sale for the same time period. In real-life, some items are only sold during some short time period (e.g., the summer). TS-HOUN scans dataset three times and efficiently find high on-shelf utility itemsets with negative profit values from temporal datasets. TS-HOUN uses Two-phase based (TWU) pruning strategy to prune the search space. It is an extension of Two-Phase approach. Hence, it needs much runtime and memory space to finish the mining task and generates a lot of candidates.

3.2. Tree-based mining algorithms

Tree-based algorithms are based on set-enumeration tree-based concepts. The candidates can be explored with the use of the lexicographic tree or enumeration tree. The main characteristic of tree-based algorithms is that the enumeration tree (or lexicographic tree) provides a certain order of exploration that can be extremely useful in many scenarios. It is assumed that a lexicographic ordering exists among the items in the dataset. This lexicographic ordering is essential for efficient set enumeration without repetition.

Tree-based mining algorithms mines HUIs by starting from itemset length-1 (as an initial suffix itemset), constructing its UP-tree and performing mining recursively on such a tree. The pattern growth is achieved by the concatenation of the suffix itemset with HUIs from UP-tree. Tree-based algorithms transform the problem of finding long itemsets to search for shorter ones recursively and then concatenating the suffix. Four algorithms (MHUI-BIT-NIP, MHUI-TID-NIP, UP-GNIV and HUSP-NIV) are available in the literature to mine HUIs with negative utility using tree-based approach.

MHUI-BIT-NIP & MHUI-TID-NIP: In 2011, Li et al. proposed two algorithms to mine HUIs with negative item profit over continuous stream transaction-sensitive sliding windows [28]. An efficient data structure LexTree-2HTU (Lexicographical Tree with 2-HTU-itemsets) is presented for maintaining a set 2-HTU (high transaction-weighted utilization)-itemsets from the current transaction-sensitive sliding window. LexTree-2HTU consists of two components, item-information and a set of trees with prefixes. The item-information is bit-vectors and TID-lists for MHUI-BIT algorithm and MHUI-TID algorithm respectively. The prefix is an entry contained in item-information. Bit-vector and TID-list improve the performance of proposed algorithms. The MHUI-BIT-NIP & MHUI-TID-NIP algorithms mine HUIs in three phases: window initialization phase, window sliding phase, and HUIs generation phase. Both algorithms use TWU based search space pruning technique.

UP-GNIV: In 2015, Subramanian et al. proposed an algorithm named UP-GNIV [46] (Utility Pattern-Growth approach for Negative Item Values) to mine HUIs with negative values by using tree-based approach without candidate generation. It is a negative utility version of UP-Growth [50] algorithm. It maintains the information of items in UP-Tree alike proposed in [2]. UP-GNIV proposed two strategies RNU (Removing Negative item Utilities) and PNI (Pruning Negative Itemsets). UP-GNIV calculates the TU using RNU strategies. PNI is applied for mining HUIs. The author checked the performance of the proposed algorithm and the state-of-the-art algorithm HUINIV-Mine using IBM synthetic datasets.

HUSP-NIV: In 2017, Xu et al. proposed high utility sequential itemsets with negative utility value [54]. In high utility sequential itemsets mining, an item occurs more than once in a sequence. None of the state-of-the-art algorithms are suitable for sequential mining. It is the first algorithm that mines high utility sequential itemsets with negative utility. HUSP-NIV is an extension of USPAN algorithm [58]. It uses the same LQS-tree (lexicographic quantitative sequence tree) as USPAN to extract the high utility sequence using I-Concatenation and S-Concatenation mechanisms. I-Concatenation and S-Concatenation mechanisms are adopted from USPAN algorithm to generate new candidate sequences and calculate the utility of sub-nodes based on its super node’s utility. The author demonstrated that the proposed algorithm is the first method of its kind.

EHIN: In 2018, Singh et al. proposed an algorithm for mining HUIs with negative utility by using a patten-growth tree. EHIN reduces the dataset scanning cost by merging the identical transactions. It uses projected dataset based transaction merging techniques to further reduce the dataset scanning cost. EHIN proposed two techniques to prune the search space named redefined subtree and redefined local utility. The author demonstrated that EHIN is up to 28 times faster and consumes up to 10 times less memory than the state-of-the-art algorithm FHN. The author showed the relative runtime and relative memory comparison between EHIN and the state-of-the-art algorithm FHN. The experimental results show that EHIN always performs better for dense datasets.

3.3. Utility-list based mining algorithms

Both the level-wise and tree-based algorithms mine HUIs from a set of transactions in a horizontal data format. Alternatively, mining can also be performed with data presented in a vertical data format like proposed in Eclat [61]. Vertical data format first scan of dataset builds the T _ID set of every single item. The computation is done by intersection of the T _ID sets of HUIs k-itemsets to compute the T _ID sets of the corresponding (k + 1)-itemsets. This process repeats until itemsets fulfill min _ util threshold. In the generation of candidate (k + 1)-itemset from k-itemsets, the merit of this method is that there is no need to scan dataset to find the utility of (k + 1)-itemsets. This is because the T _ID set of each k-itemset carries the complete information required for counting utility. Four algorithms (FHN, GHUM, HUPNU and FOSHU) are available that mine HUIs with negative utility items using utility-list based approach.

FHN: In 2014, Fournier-Viger et al. proposed an algorithm named FHN (Faster High-utility itemset miner with Negative unit profits) [13]. FHN is an extension of FHM algorithm [16]. It utilizes utility-list structure to explore the search space of itemsets. FHN uses a separate utility-list data structure for positive and negative utility values. It also utilizes EUCS (Estimated Utility Co-occurrence Structure) which provides an efficient pruning strategy to limit the search space. The author demonstrated that FHN is up to 500 times faster and uses up to 250 times less memory than the state-of-the-art algorithm HUINIV-Mine. Later, in 2016, an extensive version of basic FHN algorithm was proposed. The extended FHN [30] utilizes LA-Prune strategy which is proposed in [21] to prune the search space. The extended FHN is shown to be 2-3 orders of magnitude faster than HUINIV-Mine.

GHUM: In 2017, Krishnamoorthy et al. proposed an efficient algorithm named GHUM (Generalized High Utility Mining) [22]. GHUM presents a simplified utility-list based data structure to store information of itemsets. It does not use separate utility-list to store items. It sorts the negative items in ascending order using support (frequency) of items to generate candidates efficiently. GHUM adopts and modifies existing pruning strategies U-Prune and LA-Prune [21]. Utility-list based algorithms require expensive intersection operations to evaluate candidate. Therefore, it presents a novel pruning strategy (N-Prune) to significantly reduce the total number of evaluations. It also presents an anti-monotonic property based pruning strategy (A-Prune) for mining HUIs with negative items. GHUM is shown more than an order of magnitude improvement at a fraction of the memory over the current state-of-the-art FHN.

HUPNU: In 2017, Gan et al. proposed an algorithm named HUPNU (mining High-Utility itemsets with both Positive and Negative unit profits from Uncertain databases) to mine HUIs with negative utility value from uncertain datasets [19]. It considers the probability values of items for mining HUIs. It uses a vertical PU±-list (Probability-Utility list with Positive-and-Negative profits) structure to store both negative and positive items. It presents six pruning strategies to reduce the search space, a number of unpromising itemsets can be early pruned when constructing the PU±-list.

FOSHU: In 2015, Fournier-Viger et al. proposed an algorithm FOSHU (Faster On-Shelf High Utility itemset miner) [17] to mine HUIs with negative utility from on-shelf datasets. On-shelf items consider the shelf time of items. It is an extension of FHN algorithm [13]. Hence, it utilizes the utility-list structure to store the information of items. FOSHU mines itemsets in a single phase without generating candidates and also mines all times periods at the same time rather than mining each time period separately unlike USpan [58]. Therefore, it avoids the costly merge operations of itemsets found in each time period.

KOSHU: In 2017, Dam et al. proposed an algorithm KOSHU [8] which is an extension of FOSHU. KOSHU presents a new research issue where negative utility and shelf time of items are considered. KOSHU targets limitations of minimum utility threshold based on-shelf HUIs mining. KOSHU mines top-k high on-shelf utility itemsets (HOUIs). Hence, it allows the user to specify the value of k instead of the min _ util threshold. k is the number of itemsets to be found. KOSHU mines top-k HOUIs in all the time periods at the same time alike FOSHU. KOSHU introduces three novel strategies named EMPRP (efficient estimated co-occurrence maximum period rate pruning) CE2P (Concurrence existing of pair 2-itemset pruning) and PUP (Period utility pruning). KOSHU proposed a threshold raising strategy named RIRU (Relative utilities threshold raising strategy). RIRU is inspired by the traditional top-k HUIs mining strategy named RIU which is proposed by REPT [38].

Both real and synthetic datasets having varied characteristics have been used for experimental results. Two synthetic datasets T10I4D100K and T40I10D100K also used for experiments by most of the algorithms. These datasets also used in the traditional HUIs mining. Table 7 shows the statistical characteristics of the datasets. The external utility or unit profit for items are generated between -1000 to 1000 by using a log-normal distribution [30, 40]. The internal utility or quantity of items are generated randomly between 1 and 5 [16, 49]. We categorize the datasets into two parts, dense and sparse. Dense datasets where all items appear in almost all transactions. Sparse datasets where a few items in the transaction appear. The datasets used in the studied paper can be found on the SPMF website [15].

5.1. Concise high utility itemsets mining with negative utility value

Closed HUIs are the itemsets that do not have superset having the same support count. Discovery of closed HUIs instead of all HUIs reduces the number of itemsets. Hence, closed HUIs are more interesting and actionable because they are a lossless representation of all HUIs. In other words, using closed HUIs, the information about all HUIs including their support can be recovered without scanning the dataset. Closed itemsets are more actionable because they represent the largest set of non repeated HUIs. Recently many closed algorithms for HUIs are proposed [18, 52]. But till now no algorithm has been proposed for mining closed HUIs with negative utility value. Therefore, closed HUIs with negative utility value is a good area to explore.

5.2. Constraint-based high utility itemsets mining with negative utility value

Although mining with negative utility uncovers thousands of HUIs, the user is particularly interested only in long and more actionable itemsets. Many algorithms have been proposed to reduce the total number of itemsets generated based on constraints on the resulting rules. Hence, the users are more interested in constrained HUIs mining. Pei and Han [36] presented many constraints for FIM. These presented constraints can also be pushed into HUIs mining.

Length-based HUIs mining plays an important role in constraint HUIs mining. Two upper bound (minimum length and maximum length) can be defined to mine length HUIs rules. In order to remove the tiny items, user can set the minimum length threshold. Length based HUIs can remove lots of small itemsets and produce more interesting and actionable HUIs. HUIs mining algorithm with length threshold has been presented by Fournier-Viger [14]. But, this work not considers negative utility value. Therefore, the length constraints can be utilized in HUIs mining with negative utility value. In order to find HUIs more efficiently, we need to push the constraint as deep as we can.

5.3. Top-k high utility itemsets mining with negative utility value

Mining HUIs using min _ util is difficult for user because specifying the appropriate min _ util is not an easy task. Hence, top-k HUIs mining problem were proposed. Many top-k HUIs mining algorithms are proposed such as [11, 53] but none of these algorithms can mine HUIs with negative utility value. Therefore, in future, top-k HUIs mining with negative utility can also be explored.

5.4. High utility itemsets mining with negative utility value from data stream

HUIs mining from data stream has many applications such as retail market analysis, wireless sensor networks, and stock market prediction. To handle the huge and dynamic dataset is a challenging task. To handle the data stream and negative utility value only MHUI-BIT-NIP & MHUI-TID-NIP [28] algorithms are proposed. These algorithms follow ordinary lexicographical tree structure. Hence, there are a lot of scope to improve and propose new algorithms for mining HUIs with negative utility from the data stream.

5.5. High utility itemsets mining on big data

The algorithms discussed in this paper do not scale with big data. In literature, no algorithm is available for mining HUIs with negative utility from big data. Big data can be dealt using Multi-core computing, Grid computing, Graphics processing units (GPUs), MapReduce, Apache Hadoop and Spark framework. Some works [4, 65] deal with big data and describe the basic data mining operations on big data. In future, itemsets mining can be done with big data also.

5.6. Other problems

Some other extensions of HUIs with negative utility value mine rich itemsets in various ways, such as fuzzy HUIs mining, periodic HUIs mining, episode HUIs mining, etc. We can be used latest prepossessing techniques to improve the accuracy, completeness, and consistency of the algorithms. Some works [37, 63] show the latest preprocessing techniques that can be utilized with HUIs mining.