# Efficient Utility Tree-Based Algorithm to Mine High Utility Patterns Having Strong Correlation

Authors: Rashad Saeed; Azhar Rauf; Fahmi H. Quradaa; Syed Muhammad Asim
Journal: Complexity
 (2021)

---

## Abstract

High Utility Itemset Mining (HUIM) is one of the most investigated tasks of data mining. It has broad applications in domains such as product recommendation, market basket analysis, e-learning, text mining, bioinformatics, and web click stream analysis. Insights from such pattern analysis provide numerous benefits, including cost cutting, improved competitive advantage, and increased revenue. However, HUIM methods may discover misleading patterns as they do not evaluate the correlation of extracted patterns. As a consequence, a number of algorithms have been proposed to mine correlated HUIs. These algorithms still suffer from the issue of the computational cost in terms of both time and memory consumption. This paper presents an algorithm, named Efficient Correlated High Utility Pattern Mining (ECoHUPM), to efficiently mine the high utility patterns having strong correlation items. A new data structure based on utility tree (UTtree) named CoUTlist is proposed to store sufficient information for mining the desired patterns. Three pruning properties are introduced to reduce the search space and improve the mining performance. Experiments on sparse, very sparse, dense, and very dense datasets indicate that the proposed ECoHUPM algorithm is efficient as compared to the state-of-the-art CoHUIM and CoHUI-Miner algorithms in terms of both time and memory consumption.


---

## Body

## 1. Introduction

We live in a data age where a huge amount of data is generated from different devices every day. It is expected that 463 exabytes of data will be generated on a daily basis by 2025 [1]. Data mining has received a great deal of attention in order to transform data into useful information, due to the exponentially explosive growth of data [2]. Pattern mining is a type of unsupervised data mining approach, which aims to find useful, interesting, and meaningful patterns that can be used to support decision-making [3, 4]. Different pattern mining techniques are used to mine different types of patterns, including frequent patterns [5], high utility patterns [6], sequential patterns, trends, outliers, and graph structures [2, 6].Frequent itemset mining (FIM) aims to extract patterns containing items that frequently appear in transactional database. [7]. This task has been tremendously studied and remains to this day a very active research area as it has several applications in domains such as market basket analysis, product recommendation, text mining, e-learning, bioinformatics, and web click stream analysis [3, 8, 9]. Even though the mining of frequent pattern is useful, it depends on the assumption that all items in the dataset are equally important (e.g., weight or profit). Nevertheless, this assumption is not true for several real-life applications [6, 10]. For instance, the pattern bread,milk in a transaction database may be extremely frequent but it may not be interesting as it may produce a low profit. In different circumstances, numerous patterns like champagne,caviar may yield a higher profit even if they are not frequent [11]. To overcome this limitation of FIM, an emerging research area is High Utility Itemset Mining (HUIM) which aims to find high utility or important patterns [2, 6].HUIM takes into account the weight of items in the database and their quantities in each transaction. The goal of HUIM is to find all patterns having utility not less than minimum utility threshold. Recently, HUIM has become a very active research area as it generalizes the problem of FIM and has the same wide applications [12–15].The algorithms of HUIM are divided into two main categories. The first category is called Two-Phase algorithms [11, 16]. These types of algorithms generate candidates in the first phase, and then, in the second phase, they calculate the utility of each candidate in order to derive HUIs. However, due to the huge number of candidates generated in the first phase, these algorithms may suffer from the problem of time and memory consumption. The second category is One-Phase algorithms [6, 10, 17]. The algorithms of this category try to overcome the above issue by utilizing different data structures to store sufficient information for mining the desired patterns without candidate’s generation and utilize various pruning properties to reduce the search space.One critical downside of High Utility Itemset Mining methods is that they generally extract patterns with a high utility, but the items that make up these patterns are weakly correlated. For marketing decisions, such patterns are either useless or misleading [18–23]. For instance, with market basket analysis application, the current algorithm of High Utility Pattern Mining may find that buying a pen and a 60-inch plasma TV is a high utility itemset, since these items generally create a high profit when purchased together. However, these items are weakly correlated and rarely sold together. Hence, it would be a mistake to use this pattern to promote TV to customers who buy pen [11, 21].To address the above-stated issue, few numbers of algorithms have been developed to mine Correlated High Utility Itemsets, such as HUIPM [19], FDHUP [21], FCHMbond [22], FCHMall-confidence [22], CoHUIM [20], and CoHUI-Miner [24]. These algorithms differ from each other in the measures used to evaluate the interestingness of the extracted patterns, the data structures, and pruning properties that they used to reduce the search space and improve the mining performance. In [20, 24], a projected database has been utilized to reduce the database and improve the efficiency of correlated HUIs mining. The projected database is effective, but it suffers from the computational cost in terms of running time and memory consumption.In order to address such issue in mining Correlated High Utility Itemsets, this study proposes a new algorithm named Efficient Correlated High Utility Pattern Mining (ECoHUPM). In the proposed algorithm, new efficient data structures and pruning properties are introduced to mine the desired patterns in efficient manner. The main contributions of this paper are summarized as follows:(i)
It proposes a novel algorithm, ECoHUPM, which adopts the divide-and-conquer approach and employs UTtree structure which is an extended form of FP-tree [25].(ii)
New data structure based on UTtree named CoUTlist is proposed to store sufficient information for mining the desired patterns in one phase without candidate’s generation.(iii)
The proposed algorithm introduces several pruning properties to reduce the search space and improve the mining performance.(iv)
An experimental performance evaluation of the proposed algorithm is conducted on sparse, very sparse, dense, and very dense datasets. The performance of the proposed ECoHUPM algorithm is compared with CoHUIM and CoHUI-Miner algorithms for Correlated High Utility Itemset Mining. Experimental results show that the proposed ECoHUPM algorithm is better than the state-of-the-art CoHUIM and CoHUI-Miner algorithms in terms of both time and memory consumption.The rest of this paper is organized as follows: In Section2, we review the literature associated with HUIM and CoHUIM. Next, we introduce the mathematical preliminaries and state the problem in Section 3. In Section 4, we explain the proposed algorithm in detail. Section 5 gives details of the experimental setup and analyzes the results. Section 6 concludes the work of this paper.


## 2. Related Works

This section reviews the literature on HUIM and the CoHUIM.


### 2.1. High Utility Itemset Mining (HUIM)

Yao and Hamilton defined the problem of HUIs mining in 2004 [26]. They developed UMining algorithm for mining the itemset having high utility. UMining is an approximate algorithm and may fail to extract all HUIs. Hence, in order to extract the complete set of HUIs, Liu et al. [16] developed a Two-Phase algorithm. In the Two-Phase algorithm, a novel upper bound pruning property named TWU (Transaction Weighted Utilization) has been proposed to reduce the search space. The Two-Phase algorithm mines the HUIs in two phases. In the first phase, it generates the candidate HUIs with their TWU not less than the minimum utility threshold. Then, in the second phase, it calculates the utility of each candidate by scanning the database again to drive the HUIs. However, the Two-Phase algorithm suffers from the issue of time and memory efficiency. The main reason is that a huge number of candidates may be generated in the first phase.In [27], a new method based on tree structure called HUP-tree is proposed to mine HUIs. It integrates the Two-Phase procedure and FP-tree concept to construct a compressed tree structure for utilizing the TWU property. This approach mines HUIs in three steps: (1) constructs the tree, (2) generates the candidate’s patterns, and then (3) identifies the HUIs from the list of candidates. The mining performance of this algorithm is affected by the number of conditional trees constructed during the whole mining process and the traversal cost of each conditional tree. Hence, this algorithm suffers from the time and memory consumption due to the generation of a huge number of conditional trees and candidate patterns as well [28].In order to improve the efficiency of HUIs mining, several algorithms have been developed. To extract HUIs without candidates generation, Liu and Qu proposed HUI-Miner algorithm [29]. HUI-Miner utilizes utility-list structure to store sufficient information for mining the HUIs in one phase. Then Fournier-Viger et al. developed an algorithm named FHM [30], which introduced EUCS (Estimated Utility Cooccurrence Structure) and EUCP (Estimated Utility Cooccurrence Pruning) to improve the HUIs mining performance. HUP-Miner [31] extended the HUI-Miner to speed up utility list by utilizing a look-ahead strategy and pruning the search space by database partitioning. Chen and An [32] proposed PHU-Miner which is a parallel version of HUI-Miner. A novel algorithm named ULB-Miner was developed [33], in which improved utility list has been proposed, called utility-list buffer, for speeding up the utility-list join operation and reducing the memory consumption. A new projection-based algorithm, named MAHI [34], has been proposed to speed up the discovery of HUIs by utilizing a MAprun (Matrix-based pruning strategy).For mining HUIs without the need to set the minimum utility threshold, Tseng et al. [35] developed two types of efficient algorithms named TKU (mining Top-K Utility itemsets) and TKO (mining Top-K utility itemsets in One phase) to extract top-K high utility itemsets. However, they remain expensive in terms of both runtime and memory usage. Hence, Duong et al. [12] designed a novel algorithm named kHMC to extract the top-K HUIs more effectively. The kHMC utilizes three strategies called COV, RIU, and CUD to reduce the search space and thus improves the mining performance. Recently, Gunawan et al. [36] developed an algorithm based on binary particle swarm optimization for optimizing the search for HUIs without setting the minimum utility threshold beforehand. Instead, the minimum utility threshold is determined as a postprocessing step.Although High Utility Pattern Mining has several applications, it has some limitations. As a consequence, many extensions of High Utility Pattern Mining appeared in the literature such as Incremental Utility Mining [37, 38] which aims to extract HUPs from dynamic databases, On-Shelf High Utility Pattern Mining [39–41] in which the shelf time of items is considered, and Concise Representations of High Utility Patterns (e.g., Maximal Itemsets [42, 43] and Closed High Utility Itemsets [44–47]) that aim to extract a small list of meaningful HUPs.


### 2.2. Correlated High Utility Itemset Mining (CoHUIM)

A number of correlation measures have been suggested in the data mining literature which are used for association analysis, such as bond, all-confidence, any-confidence [48, 49], coherence [50] and Kulczynsky [51]. As the traditional algorithms of High Utility Itemset Mining do not consider the correlation of the extracted patterns, they may lead to noninteresting or misleading patterns. In such a case, they usually discover itemsets having high utility, but these itemsets may contain weakly correlated items.In order to extract more interesting patterns and to avoid misleading patterns resulting from the traditional methods of HUIs mining, a number of algorithms have been proposed to mine Correlated High Utility Itemset by utilizing both utility and correlation measures. Ahmed et al. [19] first proposed an algorithm named High Utility Interesting Pattern Mining (HUIPM) with strong frequency affinity for mining interesting patterns in high utility itemset, in which the relation among items is meaningful. The HUIPM algorithm introduced a new data structure named Utility Tree based on Frequency Affinity (UTFA) as an efficient data structure to store sufficient information required for mining the desired patterns. While a new pruning property named Knowledge Weighted Utilization (KWU) has been proposed in this algorithm to reduce the search space, the HUIPM algorithm recursively creates a number of conditional trees to generate candidates and then derive interesting patterns. This procedure is time-consuming. Thus, Lin et al. [21] developed a new algorithm named fast algorithm for mining discriminative high utility patterns (FDHUP) to improve HUIPM. In the FDHUP algorithm, two data structures called Element Information table (EI table) and Frequency Utility table (FU table) have been proposed to store required information for mining the DHUP efficiently. New pruning property is based on summation of affinitive utility and the remaining affinitive utility has been introduced to reduce the search space.Fournier-Viger et al. [22] developed Fast Correlated High Utility Itemset Miner (FCHM) algorithm for integrating the concept of correlation in High Utility Itemset Mining in order to extract profitable patterns that are highly correlated. Two versions of the algorithm have been proposed, FCHMbond and FCHMall-confidence, which are based on bond and all-confidence measures that are already used for measuring frequent correlated patterns [48, 50, 52]. The FCHM algorithm is based on HUI-Miner [29], in which the utility-list structure has been utilized, while TWU and strategy based on summation of initial and remaining utility have been used as pruning properties to reduce the search space. Moreover, FCHMbond and FCHMall-confidence utilize the antimonotonicity property of the bond and all-confidence measures, respectively, for further improving the mining performance.Gan et al. [18, 20] proposed two algorithms to extract correlated purchase behaviors by considering the correlation and utility measures. The first algorithm [20] is named Correlated High Utility Itemset Mining (CoHUIM), while the second one [18] is Correlated high Utility Pattern Miner (CoUPM). Both algorithms use the Kulczynsky (abbreviated as Kulc) measure [51] in conjunction with utility measure to evaluate the interestingness of the desired patterns. The CoUPM utilizes the utility-list structure which is introduced in [29] as a data structure to store information required to mine the desired patterns. Meanwhile, an efficient projection mechanism and a sorted downward closure property are developed in CoHUIM to reduce the database size.Vo et al. [24] suggested an algorithm, called CoHUI-Miner, to efficiently extract Correlated High Utility Itemset. The CoHUI-Miner applies the database projection mechanism to reduce the database size. Furthermore, it proposes a new concept called the prefix utility of projected transactions to directly calculate the utility of itemset.Table1 shows a summary of the Correlated High Utility Itemset Mining algorithms and their features.Table 1
Summary of Correlated High Utility Itemset Mining algorithms and their features.
No. of phasesAlgorithmMeasuresData structuresPruning propertiesTwo phasesHUIPM [19]UTFAKWUCoHUIM [20]Utility and FAProjected databaseTWUOne phaseFDHUP [21]Utility and KulczynskyEI table with FU table(1) TWU(2) Sum of AU and RAUFCHMbond [22]Utility and bondUtility list(1) TWU(2) Sum of iutil and rutil(3) Antimonotonicity of bondCoHUIM [20]Projected databaseTWUCoUPM [18]Utility and KulczynskyUtility list(1) TWU(2) Sum of iutil and rutilCoHUI-Miner [24]Projected database with prefix utility


## 2.1. High Utility Itemset Mining (HUIM)

Yao and Hamilton defined the problem of HUIs mining in 2004 [26]. They developed UMining algorithm for mining the itemset having high utility. UMining is an approximate algorithm and may fail to extract all HUIs. Hence, in order to extract the complete set of HUIs, Liu et al. [16] developed a Two-Phase algorithm. In the Two-Phase algorithm, a novel upper bound pruning property named TWU (Transaction Weighted Utilization) has been proposed to reduce the search space. The Two-Phase algorithm mines the HUIs in two phases. In the first phase, it generates the candidate HUIs with their TWU not less than the minimum utility threshold. Then, in the second phase, it calculates the utility of each candidate by scanning the database again to drive the HUIs. However, the Two-Phase algorithm suffers from the issue of time and memory efficiency. The main reason is that a huge number of candidates may be generated in the first phase.In [27], a new method based on tree structure called HUP-tree is proposed to mine HUIs. It integrates the Two-Phase procedure and FP-tree concept to construct a compressed tree structure for utilizing the TWU property. This approach mines HUIs in three steps: (1) constructs the tree, (2) generates the candidate’s patterns, and then (3) identifies the HUIs from the list of candidates. The mining performance of this algorithm is affected by the number of conditional trees constructed during the whole mining process and the traversal cost of each conditional tree. Hence, this algorithm suffers from the time and memory consumption due to the generation of a huge number of conditional trees and candidate patterns as well [28].In order to improve the efficiency of HUIs mining, several algorithms have been developed. To extract HUIs without candidates generation, Liu and Qu proposed HUI-Miner algorithm [29]. HUI-Miner utilizes utility-list structure to store sufficient information for mining the HUIs in one phase. Then Fournier-Viger et al. developed an algorithm named FHM [30], which introduced EUCS (Estimated Utility Cooccurrence Structure) and EUCP (Estimated Utility Cooccurrence Pruning) to improve the HUIs mining performance. HUP-Miner [31] extended the HUI-Miner to speed up utility list by utilizing a look-ahead strategy and pruning the search space by database partitioning. Chen and An [32] proposed PHU-Miner which is a parallel version of HUI-Miner. A novel algorithm named ULB-Miner was developed [33], in which improved utility list has been proposed, called utility-list buffer, for speeding up the utility-list join operation and reducing the memory consumption. A new projection-based algorithm, named MAHI [34], has been proposed to speed up the discovery of HUIs by utilizing a MAprun (Matrix-based pruning strategy).For mining HUIs without the need to set the minimum utility threshold, Tseng et al. [35] developed two types of efficient algorithms named TKU (mining Top-K Utility itemsets) and TKO (mining Top-K utility itemsets in One phase) to extract top-K high utility itemsets. However, they remain expensive in terms of both runtime and memory usage. Hence, Duong et al. [12] designed a novel algorithm named kHMC to extract the top-K HUIs more effectively. The kHMC utilizes three strategies called COV, RIU, and CUD to reduce the search space and thus improves the mining performance. Recently, Gunawan et al. [36] developed an algorithm based on binary particle swarm optimization for optimizing the search for HUIs without setting the minimum utility threshold beforehand. Instead, the minimum utility threshold is determined as a postprocessing step.Although High Utility Pattern Mining has several applications, it has some limitations. As a consequence, many extensions of High Utility Pattern Mining appeared in the literature such as Incremental Utility Mining [37, 38] which aims to extract HUPs from dynamic databases, On-Shelf High Utility Pattern Mining [39–41] in which the shelf time of items is considered, and Concise Representations of High Utility Patterns (e.g., Maximal Itemsets [42, 43] and Closed High Utility Itemsets [44–47]) that aim to extract a small list of meaningful HUPs.


## 2.2. Correlated High Utility Itemset Mining (CoHUIM)

A number of correlation measures have been suggested in the data mining literature which are used for association analysis, such as bond, all-confidence, any-confidence [48, 49], coherence [50] and Kulczynsky [51]. As the traditional algorithms of High Utility Itemset Mining do not consider the correlation of the extracted patterns, they may lead to noninteresting or misleading patterns. In such a case, they usually discover itemsets having high utility, but these itemsets may contain weakly correlated items.In order to extract more interesting patterns and to avoid misleading patterns resulting from the traditional methods of HUIs mining, a number of algorithms have been proposed to mine Correlated High Utility Itemset by utilizing both utility and correlation measures. Ahmed et al. [19] first proposed an algorithm named High Utility Interesting Pattern Mining (HUIPM) with strong frequency affinity for mining interesting patterns in high utility itemset, in which the relation among items is meaningful. The HUIPM algorithm introduced a new data structure named Utility Tree based on Frequency Affinity (UTFA) as an efficient data structure to store sufficient information required for mining the desired patterns. While a new pruning property named Knowledge Weighted Utilization (KWU) has been proposed in this algorithm to reduce the search space, the HUIPM algorithm recursively creates a number of conditional trees to generate candidates and then derive interesting patterns. This procedure is time-consuming. Thus, Lin et al. [21] developed a new algorithm named fast algorithm for mining discriminative high utility patterns (FDHUP) to improve HUIPM. In the FDHUP algorithm, two data structures called Element Information table (EI table) and Frequency Utility table (FU table) have been proposed to store required information for mining the DHUP efficiently. New pruning property is based on summation of affinitive utility and the remaining affinitive utility has been introduced to reduce the search space.Fournier-Viger et al. [22] developed Fast Correlated High Utility Itemset Miner (FCHM) algorithm for integrating the concept of correlation in High Utility Itemset Mining in order to extract profitable patterns that are highly correlated. Two versions of the algorithm have been proposed, FCHMbond and FCHMall-confidence, which are based on bond and all-confidence measures that are already used for measuring frequent correlated patterns [48, 50, 52]. The FCHM algorithm is based on HUI-Miner [29], in which the utility-list structure has been utilized, while TWU and strategy based on summation of initial and remaining utility have been used as pruning properties to reduce the search space. Moreover, FCHMbond and FCHMall-confidence utilize the antimonotonicity property of the bond and all-confidence measures, respectively, for further improving the mining performance.Gan et al. [18, 20] proposed two algorithms to extract correlated purchase behaviors by considering the correlation and utility measures. The first algorithm [20] is named Correlated High Utility Itemset Mining (CoHUIM), while the second one [18] is Correlated high Utility Pattern Miner (CoUPM). Both algorithms use the Kulczynsky (abbreviated as Kulc) measure [51] in conjunction with utility measure to evaluate the interestingness of the desired patterns. The CoUPM utilizes the utility-list structure which is introduced in [29] as a data structure to store information required to mine the desired patterns. Meanwhile, an efficient projection mechanism and a sorted downward closure property are developed in CoHUIM to reduce the database size.Vo et al. [24] suggested an algorithm, called CoHUI-Miner, to efficiently extract Correlated High Utility Itemset. The CoHUI-Miner applies the database projection mechanism to reduce the database size. Furthermore, it proposes a new concept called the prefix utility of projected transactions to directly calculate the utility of itemset.Table1 shows a summary of the Correlated High Utility Itemset Mining algorithms and their features.Table 1
Summary of Correlated High Utility Itemset Mining algorithms and their features.
No. of phasesAlgorithmMeasuresData structuresPruning propertiesTwo phasesHUIPM [19]UTFAKWUCoHUIM [20]Utility and FAProjected databaseTWUOne phaseFDHUP [21]Utility and KulczynskyEI table with FU table(1) TWU(2) Sum of AU and RAUFCHMbond [22]Utility and bondUtility list(1) TWU(2) Sum of iutil and rutil(3) Antimonotonicity of bondCoHUIM [20]Projected databaseTWUCoUPM [18]Utility and KulczynskyUtility list(1) TWU(2) Sum of iutil and rutilCoHUI-Miner [24]Projected database with prefix utility


## 3. Fundamental Concepts

This section presents preliminary concepts related to the problem of Correlated High Utility Itemset Mining. We adopted the definitions presented in previous work [53].Definition 1.
(quantitative database). LetI = i1,i2,…,im be a set of items and for each item ip∈I1≤p≥m profit unit (External Utility) denoted as prip in each transaction each item is associated with internal utility (Quantity) denoted as qip,Td. A quantitative database D=T1,T2,…,Tn contains a set of transactions.
Table2 shows the transactional database, while Table 3 shows external utilities for the items in Table 2.Table 2
A transactional database.
TIDTransactionT1{a: 2, b: 6, c: 2, d: 2, e: 6}T2{a: 3, b: 2, c: 3, d: 2}T3{a: 3, c: 2, d: 2, e: 3, g: 3}T4{a: 4, c: 4, d: 4, e: 12, f: 12}T5{a: 3, c: 4, d: 3, f: 4}T6{a: 2, c: 3, d: 2, f: 3}T7{b: 2, c: 4, d: 2}T8{b: 5, c: 3, d: 3, e: 5}T9{d: 3, g: 1}T10{a: 6, c: 5}T11{a: 2, c: 2}Table 3
External utility.
abcdefg3441541Definition 2.
Utility of an itemip in each transaction Td is denoted by uip,Td and is defined as uip,Td=qip,Td×prip, where prip is the external utility of an item ip and qip,Td is the quantity of an item ip in transaction Td.
For example,ub,T1=6×4=24.Definition 3.
Utility of an itemsetX in the transaction Tdis denoted by uX,Td and is defined as uX,Td=∑ip∈X&X∈Tduip,Td, that is, the sum of the utilities of all items inside pattern X in transaction Td.
For example,ubc,T1=ub,T1+uc,T1=6×4+2×4=32.Definition 4.
Utility of an itemsetX in the quantitative database D is denoted by uX and is defined as uX=∑X∈Td&Td⊆DuX,Td, that is, the sum of the utilities of itemset X in all transactions containing it.
For example,ubc =  ubc,T1+ubc,T2+ubc,T7+ubc,T8 = 32 + 32+ 24 + 20 = 108.Definition 5.
An itemsetX is called high utility itemset if uX≥minUtil, where minUtil is the minimum utility threshold.
For example, for the data presented in Table2 with minUtil = 90, {bc} is high utility itemset.Definition 6.
Utility of a transactionTd is denoted by tuTd and is defined as the sum of the utilities of all items inside transactionTd. tuTd=∑ip∈Tduip,Td.
For example, the utility of transactionT8 is calculated as tuT8=ub,T8+uc,T8+ud,T8+ue,T8=20+12+3+25=60.Definition 7.
The Transaction Weighted Utilization (TWU) of an itemsetX in database D is defined as TWUX=∑X∈Td&Td⊆DtuTd.
For example,TWUbc=tuT1+tuT2+tuT7+tuT8=70+31+26+60=187.Definition 8.
An itemsetX is called High Transaction-Weighted Utilization Itemset (HTWUI) if TWUX≥minUtil, where minUtil is the minimum utility threshold.
For example, with minUtil = 90, an itemset (bc) is HTWUI.
Different measures have been used to evaluate the interestingness of the HUIs, such as frequency affinity, bond, all-confidence, and Kulczynsky. Kulczynsky measure was recommended in [2] and has been used in [18, 20, 24]. Kulczynsky (abbreviated as Kulc) is a null-invariant measure; it is not influenced by the null transactions and is used to evaluate the inherent correlation of patterns [48, 51].Definition 9 (support).
The support of an itemsetX in the transactional database D is denoted by supX and is defined as the proportion of transactions in the database which are matched by X. SupX=countX/n, where n is the total number of transactions in the database.
For example, for the data in Table2, supa=8/11=0.727.Definition 10.
The correlation between items inside an itemsetX based on the Kulc measure is defined as the mean of the conditional probabilities of items:(1)KulcX=1k∑ip∈XsupXsupip,where k is the number of items inside X.
For example, for the data in Table2, Kulcab=1/2supab/supa+supab/suppb=1/20.181/0.727+0.181/0.363=0.375.Definition 11.
Correlated High Utility Itemset). For a given quantitative databaseD with minimum utility threshold (minUtil) and minimum correlation threshold (minCor), the Correlated High Utility Itemset is an itemset X such that uX≥minUtil&CorrX≥minCorr.


## 4. Proposed Algorithm

In order to address the need for more efficient algorithm for mining Correlated High Utility Itemsets, we propose a new algorithm named Efficient Correlated High Utility Pattern Mining (ECoHUPM). This section presents the proposed ECoHUPM algorithm in detail, the data structures that it utilizes to store sufficient information for mining the desired patterns, and the pruning properties that are used to reduce the search space and improve the mining performance.


### 4.1. Database Revising

The proposed ECoHUPM algorithm revises the input database in its first step. First, Property1 [16] is used to remove all 1-itemsets with their TWU less than minimum utility threshold. For instance, for the data presented in Table 2, with minUtil = 90, “g” item is removed as its TWUg=tuT3+tuT9=27+4=31<minUtil. Second, in each transaction, the utility of each item is computed through the formula quantity ×  profit as is stated in Definition 2. Third, items in each transaction are sorted in the descending order of their support and the total utility is assigned to each transaction. Table 4 shows the items in the descending order of their support, while Table 5 shows the revised database.Table 4
Items’ support.
cdabefg10984432Table 5
The revised database.
TIDTransactionTWUT1{c: 8, d: 2, a: 6, b: 24, e: 30}70T2{c: 12, d: 2, a: 9, b: 8}31T3{c: 8, d: 2, a: 9, e: 15}34T4{c: 16, d: 4, a: 12, e: 60, f: 40}132T5{c: 16, d: 3, a: 9, f: 16}44T6{c: 12, d: 2, a: 6, f: 12}32T7{c: 16, d: 2, b: 8}26T8{c: 12, d: 3, b: 20, e: 25}60T9{d: 3}3T10{c: 20, a: 18}38T11{c: 8, a: 6}14


### 4.2. Search Space

The proposed ECoHUPM algorithm utilizes a set-enumeration tree as a search space, whose efficiency has been verified in pattern mining [29]. Reversed depth-first search traversal is adopted as shown in Figure 1 to facilitate the search tree. Note that the ECoHUPM uses the support descending order to revise database and then to construct the UTtree. Hence, with reversed depth-first search, the mining order for the running example is f≺e≺b≺a≺d≺c.Figure 1
Set-enumeration tree with reversed depth-first traversal.Definition 12.
Given a set-enumeration tree and itemsetX represented by a node N, a set of nodes with their ancestors N are called the extensions (supersets) of X.
For thek-itemset (itemset containing k items), we denote its extensions containing k+i items as i-extension of the itemset. By adopting reverse depth-first traversal, any extension of itemset X is a combination of X with the item(s) before X.
For instance, in the set-enumeration tree represented in Figure1, itemset debf is 2-extension of bf, while itemset cdebf is 3-extension of bf.


### 4.3. Utility Tree and Correlation Utility-List Structures

Once the database is revised, the proposed ECoHUPM algorithm constructs the utility tree (UTtree). A UTtree is a concise structure that stores sufficient information for facilitating the mining of Correlated High Utility Itemsets in a single phase. It is an extended form of FP-tree [25], where each node consists of four fields: label, interLink, parentLink, and utList. The label refers to the item’s label,interLink points to the next node of the same item, parentLink points to the parent node, and utList is a dictionary that stores both a transaction’s ID as keys and item’s utility in each transaction as values.A UTtree is constructed with only one scan of the revised database as is shown in Algorithm 1. First, the tree is initialized by creating theRoot node. Then the transactions are processed one by one, as shown in lines 1 and 2. The information of each transaction is inserted into the tree by calling insertTreeTi,itemsList,Nd function as shown in line 3. The function insertTreeTi,itemsList,Nd is executed as follows: First, the items of the current transaction Ti are sorted in itemsList, and the first item is stored in firstItem. Then, if the current node Nd has N child such that N.label=firstItem, update N.utList dictionary by adding Ti key with ufisrtItem,Ti value; else create node N such that N.label=fisrtItem, N.parentLink points to Nd, N.interLink points to the previous node of the same label, and N.utList=Ti:ufisrtItem,Ti. Thereafter, while the list of remaining items itemsList1: is not empty, call the function insertTreeTi,remainingItems,N recursively. Finally, after inserting the information of the last transaction, the final UTtree is returned (line 5).For the revised database presented in Table4, Figure 2 shows the UTtree after inserting the first transaction. First, the tree is initialized by the Root node, and then node c is created with label=c, parentLink=Root, and utList=T1:8. Then, node d is created with label=d, parentLink=c, and utList=T1:2. Node a is created with label=a, parentLink=d, and utList=T1:6. Node b is created with label=b, parentLink=a, and utList=T1:24. Node e is created with label=e, parentLink=b, and utList=T1:30. As the current transaction is the first transaction, interLink of all nodes points to the items holding the same label in the header table. Similarly, the second and third transactions are inserted into the UTtree as shown in Figure 3. The final UTtree after inserting the last transaction is shown in Figure 4.Figure 2
UTtree after insertingT1.Figure 3
UTtree after insertingT3.Figure 4
The final UTtree after insertingT11.Besides adopting UTtree, new condensed data structure named CoUTlist is proposed to store sufficient information for mining the superset patterns without needing to scan the UTtree multiple times.Definition 13.
The Correlation Utility list (CoUTlist) of an itemsetX contains a set of elements, where each element represents node called a suffix where itemset X appears. In the CoUTlist, each element has four fields:(i)
nodeNo is a unique identifier number for each node, which is used as a sequence number, for example, (1, 2, …, n).(ii)
nodeSupp stores the total number of transactions, where itemset X occurred in the current node N. nodeSupp=countN.utList.keys.(iii)
nodetUtility stores the total utility of itemset X in the current node N. nodetUtility=sumN.utlist.values.(iv)
prefixPath is a dictionary, where the keys are the labels of the parent nodes of the current node, and the values are the summation of the utilities of each parent node in the current path. prefixPath = Parent1:value1,Parent2:value2,…,Parentn:valuen, where Parenti is the parent node in the current path and valuei=sumParenti.utList.values for the keys in N.utList.keys.


#### 4.3.1. The CoUTlist of 1-Itemset

Given a UTtree and itemip, we denote the set of nodes labeled ip as suffixes and the set of the parent nodes in the current path as prefixPath. The CoUTlist of 1-itemset ip is denoted as CoUTlistip and is constructed as follows: ∀N∈suffixes, if P1,P2,…,Pn∈prefixPath, P1,P2,…,Pn are the parents of N; then construct a quadruple (nodeNo, nodeSupp, nodeUtility, prefixPath), and append it to CoUTlistip.Figure5 shows how the CoUTlist of an item a denoted as CoUTlista is constructed. Based on the UTtree shown in Figure 3, there are two nodes: for those whose N.label=a, we denote the first node as suffix1 and the second node as suffix2. According to Definition 13, the first element of the CoUTlist(a) represents suffix1, with nodeNo = 1, nodeSupp=countN.utList.kesy=6, nodeUtility=sumN.utList.values=6+9+9+12+9+6=51, and preffixPath = d:ud,T1+ud,T2+ud,T3+ud,T4+ud,T5+ud,T6,c:uc,T1+uc,T2+uc,T3+uc,T4+uc,T5+uc,T6 = d:15,c:72. The second element of the CoUTlist(a) represents suffix2, with nodeNo = 2, nodeSupp=countN.utList.kesy=2, nodeUtility=sumN.utList.values=18+6=24, and path = c:uc,T10+uc,T11 = c:28. Subsequently, the elements of suffix1 and suffix2 formalized CoUTlist(a) as shown in Figure 6.Figure 5
CoUTlist of 1-itemset construction.Figure 6
CoUTlist of item {a}.In the same manner, the CoUTlist of the remaining 1-itemsets are constructed as shown in Figure7.Figure 7
The CoUTlist of the remaining 1-itemsets.


#### 4.3.2. The CoUTlist ofk-Itemset

Let itemsetX =  Ik,Ik−1,…,I2,I1 be an extension of itemset Y  = Ik−1,…,I2,I1. We denote the element in CoUTlist(Y) as Ynode and the element in CoUTlistX as Xnode.Definition 14.
Itemxi is after itemset X if xi is after all items in X. Here the keys {represent items} in prefixPath of Ynode are sorted according to the mining order which is the ascending order on their supports and are denoted as X≺xi.
For example, we have the first node of the CoUTlist off itemset, ead≺c.Definition 15.
Given an itemsetY  = Ik−1,…,I2,I1, the CoUTlist of its superset X =  Ik,Ik−1,…,I2,I1 is constructed as follows: ∀Ynodein CoUTlistY, if Ik∈ the prefixPath of Ynode, add Ynode to the CoUTlistX such that(i)
nodeNo = nodeNo of Ynode(ii)
nodeSupp = nodeSupp of Ynode(iii)
nodeUtility = nodeUtility + prefixPathIk of Ynode(iv)
prefixPath = {key: value for key, value in the prefixPath of Ynode, if key∈X≺Ik}
Figure8 shows how the CoUTlist of da itemset and CoUTlist of ca itemset are constructed from the CoUTlist of a itemset. It further shows how the CoUTlist of cda itemset is constructed from the CoUTlist of da itemset. The CoUTlist(a) is [[1, 6, 51, ‘d’: 15, ‘c’: 72], [2, 2, 24, ‘c’: 28]]. As item d has only appeared in the first element of CoUTlist(a), only one element is added to the CoUTlist(da), whose nodeNo = 1, nodeSupp = 6, nodeUtility = 51 + 15 = 66, and prefixPath = c: 72. On the other hand, item c has appeared in the two elements of CoUTlist(a); hence, two elements are added to the CoUTlist(ca). The first element is with nodeNo = 1, nodeSupp = 6, nodeUtility = 51 + 72 = 123, and prefixPath = { }, while the second element is with nodeNo = 2, nodeSupp = 2, nodeUtility = 24 + 28 = 52, and prefixPath = { }. Similarly, the CoUTlist(cda) is constructed from the CoUTlist(da). As item c has appeared in the element of CoUTlist(da), this element is added to the CoUTlist(cda) with nodeNo = 1, nodeSupp = 6, nodeUtility = 66 + 72 = 138, and prefixPath = { }.Figure 8
Constructing the CoUTlist ofk-itemset.


### 4.4. Pruning Properties

Alongside adopting Property1 (TWU) [16], three new pruning properties are introduced in the proposed ECoHUPM algorithm and applied to reduce the search space.Property 1.
Transaction-Weighted Upper Bound Property (TWU) is already introduced in [16]. The proposed algorithm utilizes the TWU property [16] to remove all 1-itemsets having TWU less than minUtil threshold.
LetX be a k-itemset, and let Y be a (k − 1)-itemset such that Y⊂X. If X is HTWUI, Y is HTWUI as well. This means that if an itemset is Low Transaction-Weighted Utilization Itemset (LTWUI), all its supersets will be LTWUIs as well. Hence, this property can be used to reduce the search space by removing LTWUIs with their supersets from the search space.Property 2.
The first proposed pruning property is Upper Bound property based on summation of Utility and the Path Utilities (UBUPU).
Given an itemsetY, if uY plus puY is less than the minimum utility threshold minUtil, Y and any superset of Y are not CoHUIs.Proof.
LetX be a superset of Y; we know the following.
The utility ofY is calculated as the sum of the nodes’ utilities in the CoUTlistY.(2)uY=∑Ynode∈CoUTlistYnodeUtility,for example, ua = 51 + 24 = 75.
The path utility ofY itemset is calculated as the sum of the prefixes’ utilities stored in the prefixpath in the CoUTlistY.(3)puY=∑Ynode∈CoUTlistYsumprefixPath.values,for example, pua = [(15 + 72) + (28)) = 115.
SinceY⊆X,(4)UX≤uY+puY,for example, uda  = 66, uca = 175, and ucda  = 138. All values ≤ua + pua  = 75 + 115 = 190.Property 3.
The second proposed pruning property is Lower Bound property based on the Node Utility (LBNU). As the CoUTlist of each itemsetX is a list of elements (nodes), where each element represents a set of transactions containing X, on the contrary to the utility list [18, 22] or projected database [20, 24], where each element represents a single transaction, with CoUTlist, there is a possibility that the utility of some itemsets exceeds the minUtil in some elements of their CoUTlists, and thus the following lower bound property based on the nodeUtility is formed.
Consider an itemsetX: ∀Xnode∈ CoUTlistX, if nodeUtility≥minUtil, then all possible combinations of itemsets in the current path are considered high utility itemsets (Figure 9).Figure 9
The CoUTlist of {ae} itemset.Proof.
Let CoUTlistX be the correlation utility list of itemset X, and ∀Xnode∈ CoUTlistX, we know the following:The set of parent nodes in the current path is denoted asP1,P2,…,Pn.uP1+X =  nodeUtility + prefixPathP1.Hence,ui−itemset+X≥nodeUtility≥minUtil, where i∈1,n).For example, for the running example, withmminUtil = 90, as shown in Figure 9, in the CoUTlist(ae), the nodeUtility of the second element = 96 ≥minUtil. Hence, all possible combinations of itemsets in the current path dae, cae, and cdae are considered high utility itemsets.Property 4.
The third proposed pruning property is Sorted-Reversing Downward Closure (SRDC) property based on Kulc measure, which is used as a correlation measure in the proposed ECoHUPM algorithm. By adopting reverse depth-first traversal, eachk-itemset is in this form Ik,Ik−1,…,I2,I1, and because these items are sorted based on their support descending order, the sorted-reversing property based on Kulc measure is formed as(5)kulcIkIk−1Ik−2,…,I1≤kulcIk−1Ik−2,…,I1.Proof.
LetX =  Ik,Ik−1,…,I2,I1 be a superset of Y = Ik−1,…,I2,I1; we know that(6)supX≤supY,supIk−1≤supIk.
Hence,(7)KulcX=1ksupXsupIk+supXsupIk−1+⋯+supXsupI1≤KulcY=1k−1supYsupIk−1+supYsupIk−2+⋯+supXYsupI1.
Note that the proposed SRDC property is similar to the sorted downward closure (SDC) property which was employed in [20, 24]. However, SDC cannot be applied directly in the proposed ECoHUPM algorithm, because, in [20, 24], the items are sorted in the ascending order of their supports. Meanwhile, in ECoHUPM, the items are sorted in the descending order of their supports.
The proposed UBUPU and SRDC properties are employed to reduce the search space by removing all supersets of eachY itemset if kulcY < minCorr or sumuY,puY < minUtil. On the other hand, the proposed LBNU property is employed to improve the searching efficiency as follows: in each element in the CoUTlist of Y itemset, if nodeUtility is equal to or greater than minUtil, all possible supersets of Y in the current path are considered as HUIs. Hence, ECoHUPM needs only to calculate the correlation of each superset X in the current path without needing to make sure that uX or sumuX+puX exceeds minUtil.
Figure10 shows how these three properties help significantly in reducing the search space and thus improve the mining performance. For example, with minCorr = 0.4 and minUtil = 90, since kulcef = 0.29 < minCorr, ef and all its supersets are removed from the search space based on the proposed SRDC property. Similarly, the itemsets bf, abe, and ab are removed along with their supersets from the search space according to the proposed UBUPU and SRDC properties. As nodeUtility of the second element of CoUTlistae is greater than minUtil, all its supersets in the current path dae, cae, and cdae are considered HUIs as stated in the proposed LBNU property, and thus ECoHUPM only needs to calculate their Kulc values to examine whether they are Correlated HUIs or not (Algorithm 1).Figure 10
Pruning search space.Algorithm 1: Algorithm for constructing UTtree.
Input: The revised Database RDOutput: The UTtreeInitialization: Create Root node to initialize the tree(1)
for each transaction Ti in RDdo(2)
itemsList← Items of Ti(3)
Call insertTreeTi,itemsList,Root(4)
end for(5)
returnUTtreeFunction: insertTree Ti,itemsList,Nd(1)
firstItem←itemsList0(2)
ifNd has Nchild such that N.label=firstItemthen(3)
Update theutList of N(4)
else(5)
Create new nodeN for the firstItem(6)
N.parentLink←Nd(7)
N.interLink points to the nodes whose label is firstItem(8)
remainItems←itemsList1:(9)
ifremainItems is not null then(10)
Call insertTreeTi,remainItems,N(11)
end if(12)
end if


### 4.5. ECoHUPM Algorithm

Using the UTtree and the CoUTlist, we developed an efficient algorithm named ECoHUPM for mining Correlated High Utility Itemsets. ECoHUPM adopts reverse depth-first traversal for set-enumeration tree searching and employs the pruning properties to reduce the search space. The pseudocode of ECoHUPM is shown in Algorithm2.Algorithm 2: ECoHUPM algorithm.
Input: Database D, minUtil, and minCorr.Output: All Correlated High Utility Itemsets.(1)
ScanD to obtain the revised database RD;(2)
itemsList← the set of unique items in RD sorted on their support descending order;(3)
Execute the Algorithm1 to construct UTtree for the RD;(4)
whileitemsList not NULL do(5)
X← the last item in itemsList;(6)
from the header table of theUTtree follow the interLink of the nodes labeled X to construct the CoUTlistX;(7)
ifuX≥minUtilthen(8)
CoHUPs←CoHUPs∪X(9)
end if(10)
ifuX+puX≥minUtilthen(11)
Call search (X, CoUTlistX, minUtil, minCorr)(12)
end if(13)
itemsList←itemsList-X(14)
end while(15)
returnCoHUPsThe input for ECoHUPM is databaseD including transactional database with external utility along with minUtil, as a given minimum utility threshold, and minCorr, as a given minimum correlation threshold. In line 1, the ECoHUPM preprocess database D to obtain the revised database RD, and then it stores the set of unique items sorted in the descending order of their support in itemsList (line 2). Then it runs Algorithm 1 to construct the UTtree by performing one scan of the RD (line 3).Lines 4 to 15 state the procedure of extracting the Correlated High Utility Itemsets. For each loop started by line 4, ECoHUPM finds all Correlated HUIs that are supersets of itemX. Lines 5 and 6 construct the CoUTlist of 1-itemset X with the help of interLink and parentLink of nodes whose label is X in the UTtree as is illustrated in Section 4.3.1. As the correlation value of each 1-itemset is 1, lines 7 to 9 add X itemset to the CoHUPs list if its utility is equal or greater than minUtil. Line 10 employs the proposed UBUPU property by examining the summation of utility and path utilities of an itemset X. If the sumuX+puX is less than minUtil, all its supersets will be pruned using the proposed UBUPU property. Otherwise, the function search is called to search its supersets (line 11). This procedure is recursively performed for all 1-itemsets to discover Correlated High Utility Itemsets (Algorithm 3).Algorithm 3: Algorithm for searching the list of extensions of itemset X.
Function: search (X, CoUTlistX, minUtil, minCorr)(1)
HUprefixList←∅(2)
prefixList←∅(3)
for each Xnode∈CoUTlistXdo(4)
for each Pi∈prefixPathdo(5)
ifnodeUtility≥minUtilthen(6)
HUprefixList←HUprefixList∪Pi(7)
end if(8)
ifPi∉prefixListthen(9)
prefixList←prefixList∪Pi(10)
end if(11)
end for(12)
end for(13)
for each Pi∈prefixListdo(14)
itemset←Pi + X;(15)
Scan theCoUTlisX to construct the CoUTlistitemset(16)
ifKulcitemset≥minCorrthen(17)
ifPi∈HUprefixListthen(18)
CoHUPs←CoHUPs∪itemset(19)
Call search(itemset, CoUTlistitemset, minUtil, minCorr)(20)
else(21)
ifuitemset≥minUtilthen(22)
CoHUPs←CoHUPs∪itemset(23)
end if(24)
ifuitemset+puitemset≥minUtilthen(25)
Call search (itemset, CoUTlistitemset, minUtil, minCorr)(26)
end if(27)
end if(28)
end if(29)
end forThe functionsearchX,CoUTlistX,minUtil,minCorr is used to search the whole list of extensions of itemset X in order to discover all correlated high utility supersets. It scans CoUTlistX node by node to find all possible prefixes (lines 1–12). If the utility of the current node nodUtility is equal to or greater than minUtil, all prefixes in the prefixPath of the current node are added to the list of high utility prefixes HUprefixesList (lines 5 to 7). All unique prefixes are added to the prefixList (lines 8 to10). Then the procedure in lines 13 to 29 is performed for each prefix Pi in prefixList. First, 1-extension itemset of X is formed such that itemset =  Pi + X (line 14) and its CoUTlist is constructed (line 15). Line 16 implements the proposed SRDC property to remove the itemset with all its supersets from the search space if its Kulc value is less than minCorr. Lines 17 to 19 employ the proposed LBNU property to add an itemset to the list of CoHUPs if current Pi is in the HUprefixList and search function is called to search all its supersets. Otherwise, lines 21 to 23 add an itemset to the list of CoHUPs if its utility is equal to or greater than minUtil, while lines 24–26 employ the proposed UBUPU property to remove the itemset with all its supersets if its utility plus path utilities is less than minUtil; otherwise, search function is called to search its supersets.


## 4.1. Database Revising

The proposed ECoHUPM algorithm revises the input database in its first step. First, Property1 [16] is used to remove all 1-itemsets with their TWU less than minimum utility threshold. For instance, for the data presented in Table 2, with minUtil = 90, “g” item is removed as its TWUg=tuT3+tuT9=27+4=31<minUtil. Second, in each transaction, the utility of each item is computed through the formula quantity ×  profit as is stated in Definition 2. Third, items in each transaction are sorted in the descending order of their support and the total utility is assigned to each transaction. Table 4 shows the items in the descending order of their support, while Table 5 shows the revised database.Table 4
Items’ support.
cdabefg10984432Table 5
The revised database.
TIDTransactionTWUT1{c: 8, d: 2, a: 6, b: 24, e: 30}70T2{c: 12, d: 2, a: 9, b: 8}31T3{c: 8, d: 2, a: 9, e: 15}34T4{c: 16, d: 4, a: 12, e: 60, f: 40}132T5{c: 16, d: 3, a: 9, f: 16}44T6{c: 12, d: 2, a: 6, f: 12}32T7{c: 16, d: 2, b: 8}26T8{c: 12, d: 3, b: 20, e: 25}60T9{d: 3}3T10{c: 20, a: 18}38T11{c: 8, a: 6}14


## 4.2. Search Space

The proposed ECoHUPM algorithm utilizes a set-enumeration tree as a search space, whose efficiency has been verified in pattern mining [29]. Reversed depth-first search traversal is adopted as shown in Figure 1 to facilitate the search tree. Note that the ECoHUPM uses the support descending order to revise database and then to construct the UTtree. Hence, with reversed depth-first search, the mining order for the running example is f≺e≺b≺a≺d≺c.Figure 1
Set-enumeration tree with reversed depth-first traversal.Definition 12.
Given a set-enumeration tree and itemsetX represented by a node N, a set of nodes with their ancestors N are called the extensions (supersets) of X.
For thek-itemset (itemset containing k items), we denote its extensions containing k+i items as i-extension of the itemset. By adopting reverse depth-first traversal, any extension of itemset X is a combination of X with the item(s) before X.
For instance, in the set-enumeration tree represented in Figure1, itemset debf is 2-extension of bf, while itemset cdebf is 3-extension of bf.


## 4.3. Utility Tree and Correlation Utility-List Structures

Once the database is revised, the proposed ECoHUPM algorithm constructs the utility tree (UTtree). A UTtree is a concise structure that stores sufficient information for facilitating the mining of Correlated High Utility Itemsets in a single phase. It is an extended form of FP-tree [25], where each node consists of four fields: label, interLink, parentLink, and utList. The label refers to the item’s label,interLink points to the next node of the same item, parentLink points to the parent node, and utList is a dictionary that stores both a transaction’s ID as keys and item’s utility in each transaction as values.A UTtree is constructed with only one scan of the revised database as is shown in Algorithm 1. First, the tree is initialized by creating theRoot node. Then the transactions are processed one by one, as shown in lines 1 and 2. The information of each transaction is inserted into the tree by calling insertTreeTi,itemsList,Nd function as shown in line 3. The function insertTreeTi,itemsList,Nd is executed as follows: First, the items of the current transaction Ti are sorted in itemsList, and the first item is stored in firstItem. Then, if the current node Nd has N child such that N.label=firstItem, update N.utList dictionary by adding Ti key with ufisrtItem,Ti value; else create node N such that N.label=fisrtItem, N.parentLink points to Nd, N.interLink points to the previous node of the same label, and N.utList=Ti:ufisrtItem,Ti. Thereafter, while the list of remaining items itemsList1: is not empty, call the function insertTreeTi,remainingItems,N recursively. Finally, after inserting the information of the last transaction, the final UTtree is returned (line 5).For the revised database presented in Table4, Figure 2 shows the UTtree after inserting the first transaction. First, the tree is initialized by the Root node, and then node c is created with label=c, parentLink=Root, and utList=T1:8. Then, node d is created with label=d, parentLink=c, and utList=T1:2. Node a is created with label=a, parentLink=d, and utList=T1:6. Node b is created with label=b, parentLink=a, and utList=T1:24. Node e is created with label=e, parentLink=b, and utList=T1:30. As the current transaction is the first transaction, interLink of all nodes points to the items holding the same label in the header table. Similarly, the second and third transactions are inserted into the UTtree as shown in Figure 3. The final UTtree after inserting the last transaction is shown in Figure 4.Figure 2
UTtree after insertingT1.Figure 3
UTtree after insertingT3.Figure 4
The final UTtree after insertingT11.Besides adopting UTtree, new condensed data structure named CoUTlist is proposed to store sufficient information for mining the superset patterns without needing to scan the UTtree multiple times.Definition 13.
The Correlation Utility list (CoUTlist) of an itemsetX contains a set of elements, where each element represents node called a suffix where itemset X appears. In the CoUTlist, each element has four fields:(i)
nodeNo is a unique identifier number for each node, which is used as a sequence number, for example, (1, 2, …, n).(ii)
nodeSupp stores the total number of transactions, where itemset X occurred in the current node N. nodeSupp=countN.utList.keys.(iii)
nodetUtility stores the total utility of itemset X in the current node N. nodetUtility=sumN.utlist.values.(iv)
prefixPath is a dictionary, where the keys are the labels of the parent nodes of the current node, and the values are the summation of the utilities of each parent node in the current path. prefixPath = Parent1:value1,Parent2:value2,…,Parentn:valuen, where Parenti is the parent node in the current path and valuei=sumParenti.utList.values for the keys in N.utList.keys.


### 4.3.1. The CoUTlist of 1-Itemset

Given a UTtree and itemip, we denote the set of nodes labeled ip as suffixes and the set of the parent nodes in the current path as prefixPath. The CoUTlist of 1-itemset ip is denoted as CoUTlistip and is constructed as follows: ∀N∈suffixes, if P1,P2,…,Pn∈prefixPath, P1,P2,…,Pn are the parents of N; then construct a quadruple (nodeNo, nodeSupp, nodeUtility, prefixPath), and append it to CoUTlistip.Figure5 shows how the CoUTlist of an item a denoted as CoUTlista is constructed. Based on the UTtree shown in Figure 3, there are two nodes: for those whose N.label=a, we denote the first node as suffix1 and the second node as suffix2. According to Definition 13, the first element of the CoUTlist(a) represents suffix1, with nodeNo = 1, nodeSupp=countN.utList.kesy=6, nodeUtility=sumN.utList.values=6+9+9+12+9+6=51, and preffixPath = d:ud,T1+ud,T2+ud,T3+ud,T4+ud,T5+ud,T6,c:uc,T1+uc,T2+uc,T3+uc,T4+uc,T5+uc,T6 = d:15,c:72. The second element of the CoUTlist(a) represents suffix2, with nodeNo = 2, nodeSupp=countN.utList.kesy=2, nodeUtility=sumN.utList.values=18+6=24, and path = c:uc,T10+uc,T11 = c:28. Subsequently, the elements of suffix1 and suffix2 formalized CoUTlist(a) as shown in Figure 6.Figure 5
CoUTlist of 1-itemset construction.Figure 6
CoUTlist of item {a}.In the same manner, the CoUTlist of the remaining 1-itemsets are constructed as shown in Figure7.Figure 7
The CoUTlist of the remaining 1-itemsets.


### 4.3.2. The CoUTlist ofk-Itemset

Let itemsetX =  Ik,Ik−1,…,I2,I1 be an extension of itemset Y  = Ik−1,…,I2,I1. We denote the element in CoUTlist(Y) as Ynode and the element in CoUTlistX as Xnode.Definition 14.
Itemxi is after itemset X if xi is after all items in X. Here the keys {represent items} in prefixPath of Ynode are sorted according to the mining order which is the ascending order on their supports and are denoted as X≺xi.
For example, we have the first node of the CoUTlist off itemset, ead≺c.Definition 15.
Given an itemsetY  = Ik−1,…,I2,I1, the CoUTlist of its superset X =  Ik,Ik−1,…,I2,I1 is constructed as follows: ∀Ynodein CoUTlistY, if Ik∈ the prefixPath of Ynode, add Ynode to the CoUTlistX such that(i)
nodeNo = nodeNo of Ynode(ii)
nodeSupp = nodeSupp of Ynode(iii)
nodeUtility = nodeUtility + prefixPathIk of Ynode(iv)
prefixPath = {key: value for key, value in the prefixPath of Ynode, if key∈X≺Ik}
Figure8 shows how the CoUTlist of da itemset and CoUTlist of ca itemset are constructed from the CoUTlist of a itemset. It further shows how the CoUTlist of cda itemset is constructed from the CoUTlist of da itemset. The CoUTlist(a) is [[1, 6, 51, ‘d’: 15, ‘c’: 72], [2, 2, 24, ‘c’: 28]]. As item d has only appeared in the first element of CoUTlist(a), only one element is added to the CoUTlist(da), whose nodeNo = 1, nodeSupp = 6, nodeUtility = 51 + 15 = 66, and prefixPath = c: 72. On the other hand, item c has appeared in the two elements of CoUTlist(a); hence, two elements are added to the CoUTlist(ca). The first element is with nodeNo = 1, nodeSupp = 6, nodeUtility = 51 + 72 = 123, and prefixPath = { }, while the second element is with nodeNo = 2, nodeSupp = 2, nodeUtility = 24 + 28 = 52, and prefixPath = { }. Similarly, the CoUTlist(cda) is constructed from the CoUTlist(da). As item c has appeared in the element of CoUTlist(da), this element is added to the CoUTlist(cda) with nodeNo = 1, nodeSupp = 6, nodeUtility = 66 + 72 = 138, and prefixPath = { }.Figure 8
Constructing the CoUTlist ofk-itemset.


## 4.3.1. The CoUTlist of 1-Itemset

Given a UTtree and itemip, we denote the set of nodes labeled ip as suffixes and the set of the parent nodes in the current path as prefixPath. The CoUTlist of 1-itemset ip is denoted as CoUTlistip and is constructed as follows: ∀N∈suffixes, if P1,P2,…,Pn∈prefixPath, P1,P2,…,Pn are the parents of N; then construct a quadruple (nodeNo, nodeSupp, nodeUtility, prefixPath), and append it to CoUTlistip.Figure5 shows how the CoUTlist of an item a denoted as CoUTlista is constructed. Based on the UTtree shown in Figure 3, there are two nodes: for those whose N.label=a, we denote the first node as suffix1 and the second node as suffix2. According to Definition 13, the first element of the CoUTlist(a) represents suffix1, with nodeNo = 1, nodeSupp=countN.utList.kesy=6, nodeUtility=sumN.utList.values=6+9+9+12+9+6=51, and preffixPath = d:ud,T1+ud,T2+ud,T3+ud,T4+ud,T5+ud,T6,c:uc,T1+uc,T2+uc,T3+uc,T4+uc,T5+uc,T6 = d:15,c:72. The second element of the CoUTlist(a) represents suffix2, with nodeNo = 2, nodeSupp=countN.utList.kesy=2, nodeUtility=sumN.utList.values=18+6=24, and path = c:uc,T10+uc,T11 = c:28. Subsequently, the elements of suffix1 and suffix2 formalized CoUTlist(a) as shown in Figure 6.Figure 5
CoUTlist of 1-itemset construction.Figure 6
CoUTlist of item {a}.In the same manner, the CoUTlist of the remaining 1-itemsets are constructed as shown in Figure7.Figure 7
The CoUTlist of the remaining 1-itemsets.


## 4.3.2. The CoUTlist ofk-Itemset

Let itemsetX =  Ik,Ik−1,…,I2,I1 be an extension of itemset Y  = Ik−1,…,I2,I1. We denote the element in CoUTlist(Y) as Ynode and the element in CoUTlistX as Xnode.Definition 14.
Itemxi is after itemset X if xi is after all items in X. Here the keys {represent items} in prefixPath of Ynode are sorted according to the mining order which is the ascending order on their supports and are denoted as X≺xi.
For example, we have the first node of the CoUTlist off itemset, ead≺c.Definition 15.
Given an itemsetY  = Ik−1,…,I2,I1, the CoUTlist of its superset X =  Ik,Ik−1,…,I2,I1 is constructed as follows: ∀Ynodein CoUTlistY, if Ik∈ the prefixPath of Ynode, add Ynode to the CoUTlistX such that(i)
nodeNo = nodeNo of Ynode(ii)
nodeSupp = nodeSupp of Ynode(iii)
nodeUtility = nodeUtility + prefixPathIk of Ynode(iv)
prefixPath = {key: value for key, value in the prefixPath of Ynode, if key∈X≺Ik}
Figure8 shows how the CoUTlist of da itemset and CoUTlist of ca itemset are constructed from the CoUTlist of a itemset. It further shows how the CoUTlist of cda itemset is constructed from the CoUTlist of da itemset. The CoUTlist(a) is [[1, 6, 51, ‘d’: 15, ‘c’: 72], [2, 2, 24, ‘c’: 28]]. As item d has only appeared in the first element of CoUTlist(a), only one element is added to the CoUTlist(da), whose nodeNo = 1, nodeSupp = 6, nodeUtility = 51 + 15 = 66, and prefixPath = c: 72. On the other hand, item c has appeared in the two elements of CoUTlist(a); hence, two elements are added to the CoUTlist(ca). The first element is with nodeNo = 1, nodeSupp = 6, nodeUtility = 51 + 72 = 123, and prefixPath = { }, while the second element is with nodeNo = 2, nodeSupp = 2, nodeUtility = 24 + 28 = 52, and prefixPath = { }. Similarly, the CoUTlist(cda) is constructed from the CoUTlist(da). As item c has appeared in the element of CoUTlist(da), this element is added to the CoUTlist(cda) with nodeNo = 1, nodeSupp = 6, nodeUtility = 66 + 72 = 138, and prefixPath = { }.Figure 8
Constructing the CoUTlist ofk-itemset.


## 4.4. Pruning Properties

Alongside adopting Property1 (TWU) [16], three new pruning properties are introduced in the proposed ECoHUPM algorithm and applied to reduce the search space.Property 1.
Transaction-Weighted Upper Bound Property (TWU) is already introduced in [16]. The proposed algorithm utilizes the TWU property [16] to remove all 1-itemsets having TWU less than minUtil threshold.
LetX be a k-itemset, and let Y be a (k − 1)-itemset such that Y⊂X. If X is HTWUI, Y is HTWUI as well. This means that if an itemset is Low Transaction-Weighted Utilization Itemset (LTWUI), all its supersets will be LTWUIs as well. Hence, this property can be used to reduce the search space by removing LTWUIs with their supersets from the search space.Property 2.
The first proposed pruning property is Upper Bound property based on summation of Utility and the Path Utilities (UBUPU).
Given an itemsetY, if uY plus puY is less than the minimum utility threshold minUtil, Y and any superset of Y are not CoHUIs.Proof.
LetX be a superset of Y; we know the following.
The utility ofY is calculated as the sum of the nodes’ utilities in the CoUTlistY.(2)uY=∑Ynode∈CoUTlistYnodeUtility,for example, ua = 51 + 24 = 75.
The path utility ofY itemset is calculated as the sum of the prefixes’ utilities stored in the prefixpath in the CoUTlistY.(3)puY=∑Ynode∈CoUTlistYsumprefixPath.values,for example, pua = [(15 + 72) + (28)) = 115.
SinceY⊆X,(4)UX≤uY+puY,for example, uda  = 66, uca = 175, and ucda  = 138. All values ≤ua + pua  = 75 + 115 = 190.Property 3.
The second proposed pruning property is Lower Bound property based on the Node Utility (LBNU). As the CoUTlist of each itemsetX is a list of elements (nodes), where each element represents a set of transactions containing X, on the contrary to the utility list [18, 22] or projected database [20, 24], where each element represents a single transaction, with CoUTlist, there is a possibility that the utility of some itemsets exceeds the minUtil in some elements of their CoUTlists, and thus the following lower bound property based on the nodeUtility is formed.
Consider an itemsetX: ∀Xnode∈ CoUTlistX, if nodeUtility≥minUtil, then all possible combinations of itemsets in the current path are considered high utility itemsets (Figure 9).Figure 9
The CoUTlist of {ae} itemset.Proof.
Let CoUTlistX be the correlation utility list of itemset X, and ∀Xnode∈ CoUTlistX, we know the following:The set of parent nodes in the current path is denoted asP1,P2,…,Pn.uP1+X =  nodeUtility + prefixPathP1.Hence,ui−itemset+X≥nodeUtility≥minUtil, where i∈1,n).For example, for the running example, withmminUtil = 90, as shown in Figure 9, in the CoUTlist(ae), the nodeUtility of the second element = 96 ≥minUtil. Hence, all possible combinations of itemsets in the current path dae, cae, and cdae are considered high utility itemsets.Property 4.
The third proposed pruning property is Sorted-Reversing Downward Closure (SRDC) property based on Kulc measure, which is used as a correlation measure in the proposed ECoHUPM algorithm. By adopting reverse depth-first traversal, eachk-itemset is in this form Ik,Ik−1,…,I2,I1, and because these items are sorted based on their support descending order, the sorted-reversing property based on Kulc measure is formed as(5)kulcIkIk−1Ik−2,…,I1≤kulcIk−1Ik−2,…,I1.Proof.
LetX =  Ik,Ik−1,…,I2,I1 be a superset of Y = Ik−1,…,I2,I1; we know that(6)supX≤supY,supIk−1≤supIk.
Hence,(7)KulcX=1ksupXsupIk+supXsupIk−1+⋯+supXsupI1≤KulcY=1k−1supYsupIk−1+supYsupIk−2+⋯+supXYsupI1.
Note that the proposed SRDC property is similar to the sorted downward closure (SDC) property which was employed in [20, 24]. However, SDC cannot be applied directly in the proposed ECoHUPM algorithm, because, in [20, 24], the items are sorted in the ascending order of their supports. Meanwhile, in ECoHUPM, the items are sorted in the descending order of their supports.
The proposed UBUPU and SRDC properties are employed to reduce the search space by removing all supersets of eachY itemset if kulcY < minCorr or sumuY,puY < minUtil. On the other hand, the proposed LBNU property is employed to improve the searching efficiency as follows: in each element in the CoUTlist of Y itemset, if nodeUtility is equal to or greater than minUtil, all possible supersets of Y in the current path are considered as HUIs. Hence, ECoHUPM needs only to calculate the correlation of each superset X in the current path without needing to make sure that uX or sumuX+puX exceeds minUtil.
Figure10 shows how these three properties help significantly in reducing the search space and thus improve the mining performance. For example, with minCorr = 0.4 and minUtil = 90, since kulcef = 0.29 < minCorr, ef and all its supersets are removed from the search space based on the proposed SRDC property. Similarly, the itemsets bf, abe, and ab are removed along with their supersets from the search space according to the proposed UBUPU and SRDC properties. As nodeUtility of the second element of CoUTlistae is greater than minUtil, all its supersets in the current path dae, cae, and cdae are considered HUIs as stated in the proposed LBNU property, and thus ECoHUPM only needs to calculate their Kulc values to examine whether they are Correlated HUIs or not (Algorithm 1).Figure 10
Pruning search space.Algorithm 1: Algorithm for constructing UTtree.
Input: The revised Database RDOutput: The UTtreeInitialization: Create Root node to initialize the tree(1)
for each transaction Ti in RDdo(2)
itemsList← Items of Ti(3)
Call insertTreeTi,itemsList,Root(4)
end for(5)
returnUTtreeFunction: insertTree Ti,itemsList,Nd(1)
firstItem←itemsList0(2)
ifNd has Nchild such that N.label=firstItemthen(3)
Update theutList of N(4)
else(5)
Create new nodeN for the firstItem(6)
N.parentLink←Nd(7)
N.interLink points to the nodes whose label is firstItem(8)
remainItems←itemsList1:(9)
ifremainItems is not null then(10)
Call insertTreeTi,remainItems,N(11)
end if(12)
end if


## 4.5. ECoHUPM Algorithm

Using the UTtree and the CoUTlist, we developed an efficient algorithm named ECoHUPM for mining Correlated High Utility Itemsets. ECoHUPM adopts reverse depth-first traversal for set-enumeration tree searching and employs the pruning properties to reduce the search space. The pseudocode of ECoHUPM is shown in Algorithm2.Algorithm 2: ECoHUPM algorithm.
Input: Database D, minUtil, and minCorr.Output: All Correlated High Utility Itemsets.(1)
ScanD to obtain the revised database RD;(2)
itemsList← the set of unique items in RD sorted on their support descending order;(3)
Execute the Algorithm1 to construct UTtree for the RD;(4)
whileitemsList not NULL do(5)
X← the last item in itemsList;(6)
from the header table of theUTtree follow the interLink of the nodes labeled X to construct the CoUTlistX;(7)
ifuX≥minUtilthen(8)
CoHUPs←CoHUPs∪X(9)
end if(10)
ifuX+puX≥minUtilthen(11)
Call search (X, CoUTlistX, minUtil, minCorr)(12)
end if(13)
itemsList←itemsList-X(14)
end while(15)
returnCoHUPsThe input for ECoHUPM is databaseD including transactional database with external utility along with minUtil, as a given minimum utility threshold, and minCorr, as a given minimum correlation threshold. In line 1, the ECoHUPM preprocess database D to obtain the revised database RD, and then it stores the set of unique items sorted in the descending order of their support in itemsList (line 2). Then it runs Algorithm 1 to construct the UTtree by performing one scan of the RD (line 3).Lines 4 to 15 state the procedure of extracting the Correlated High Utility Itemsets. For each loop started by line 4, ECoHUPM finds all Correlated HUIs that are supersets of itemX. Lines 5 and 6 construct the CoUTlist of 1-itemset X with the help of interLink and parentLink of nodes whose label is X in the UTtree as is illustrated in Section 4.3.1. As the correlation value of each 1-itemset is 1, lines 7 to 9 add X itemset to the CoHUPs list if its utility is equal or greater than minUtil. Line 10 employs the proposed UBUPU property by examining the summation of utility and path utilities of an itemset X. If the sumuX+puX is less than minUtil, all its supersets will be pruned using the proposed UBUPU property. Otherwise, the function search is called to search its supersets (line 11). This procedure is recursively performed for all 1-itemsets to discover Correlated High Utility Itemsets (Algorithm 3).Algorithm 3: Algorithm for searching the list of extensions of itemset X.
Function: search (X, CoUTlistX, minUtil, minCorr)(1)
HUprefixList←∅(2)
prefixList←∅(3)
for each Xnode∈CoUTlistXdo(4)
for each Pi∈prefixPathdo(5)
ifnodeUtility≥minUtilthen(6)
HUprefixList←HUprefixList∪Pi(7)
end if(8)
ifPi∉prefixListthen(9)
prefixList←prefixList∪Pi(10)
end if(11)
end for(12)
end for(13)
for each Pi∈prefixListdo(14)
itemset←Pi + X;(15)
Scan theCoUTlisX to construct the CoUTlistitemset(16)
ifKulcitemset≥minCorrthen(17)
ifPi∈HUprefixListthen(18)
CoHUPs←CoHUPs∪itemset(19)
Call search(itemset, CoUTlistitemset, minUtil, minCorr)(20)
else(21)
ifuitemset≥minUtilthen(22)
CoHUPs←CoHUPs∪itemset(23)
end if(24)
ifuitemset+puitemset≥minUtilthen(25)
Call search (itemset, CoUTlistitemset, minUtil, minCorr)(26)
end if(27)
end if(28)
end if(29)
end forThe functionsearchX,CoUTlistX,minUtil,minCorr is used to search the whole list of extensions of itemset X in order to discover all correlated high utility supersets. It scans CoUTlistX node by node to find all possible prefixes (lines 1–12). If the utility of the current node nodUtility is equal to or greater than minUtil, all prefixes in the prefixPath of the current node are added to the list of high utility prefixes HUprefixesList (lines 5 to 7). All unique prefixes are added to the prefixList (lines 8 to10). Then the procedure in lines 13 to 29 is performed for each prefix Pi in prefixList. First, 1-extension itemset of X is formed such that itemset =  Pi + X (line 14) and its CoUTlist is constructed (line 15). Line 16 implements the proposed SRDC property to remove the itemset with all its supersets from the search space if its Kulc value is less than minCorr. Lines 17 to 19 employ the proposed LBNU property to add an itemset to the list of CoHUPs if current Pi is in the HUprefixList and search function is called to search all its supersets. Otherwise, lines 21 to 23 add an itemset to the list of CoHUPs if its utility is equal to or greater than minUtil, while lines 24–26 employ the proposed UBUPU property to remove the itemset with all its supersets if its utility plus path utilities is less than minUtil; otherwise, search function is called to search its supersets.


## 5. Experiment Design

In this section, we present the design of the experiments for performance evaluation. Experiments were performed on a computer with an Intel® CoreTM i7-6600U CPU @ 2.60 GHz (4 CPUs), 2.8 GHz, and 8 GB of memory, running 64-bit Windows 10 Pro. The performance of the proposed ECoHUPM algorithm was compared to that of the CoHUIM and CoHUI-Miner algorithms in terms of both runtime and memory consumption. All algorithms were implemented using Python 3 and Jupyter Notebook.


### 5.1. Datasets Used

We used five standard datasets downloaded from SPMF library [54], two real-life datasets with real utility values (Foodmart and Ecommerce), and three real-life datasets with synthetic utility values (BMS, Chess, and Mushroom). Characteristics of the considered datasets are shown in Table 6.Table 6
Characteristics of the used datasets.
Dataset nameDescriptionTransactions countItems countAverage items count per transactionHas real utility values?Sparse or denseFoodmartDataset of customer transactions from a retail store, obtained and transformed from SQL-Server 2000.4,1411,5594.42YesSparse datasetEcommerceTransactional dataset which contains all the transactions occurring between 01/12/2010 and 09/12/2011 of a UK-based and registered nonstore online retail.14,9753,80315.4YesSparse datasetBMSClick stream data from a web store used in KDD-Cup 2000.59,6024972.51NoVery sparse datasetMushroomPrepared based on the UCI mushrooms dataset.8,12411923NoDense datasetChessPrepared based on the UCI chess dataset.3,1967537NoVery dense datasetminCorr is adapted with three times on each sparse dataset and four times on each dense dataset to evaluate the efficiency of the proposed ECoHUPM algorithm and they are denoted, respectively, as ECoHUPM-minCorr1, ECoHUPM-minCorr2, ECoHUPM-minCorr3, and ECoHUPM-minCorr4. The different three minCorr thresholds are, respectively, set as follows: (1) in Foodmart dataset, 0.1, 0.2, 0.3; (2) in Ecommerce dataset, 0.1, 0.2, 0.3; (3) in BMS dataset, 0.5, 0.6, 0.7; (4) in Mushroom dataset, 0.4, 0.45, 0.5, 0.55; and (5) in Chess dataset, 0.7, 0.75, 0.8, 0.85. Because all algorithms use the same measures to evaluate the interestingness of the extracted patterns, all algorithms resulted in the same number of patterns in all experiments. Tables 7–11 show the total number of Correlated HUIs when minUtil and minCorr are varied in each dataset.Table 7
The total number of Correlated HUIs whenminUtil and minCorr are varied in Foodmart dataset.
minUtil0.000010.000050.00010.00050.001minCorr15344352776475102102258minCorr2195119421893925257minCorr3157515731564915257Table 8
The total number of Correlated HUIs whenminUtil and minCorr are varied in Ecommerce dataset.
minUtil0.00050.00070.00090.00110.0013minCorr14956304018571167799minCorr21345977745592467minCorr3901645479386318Table 9
The total number of Correlated HUIs whenminUtil and minCorr are varied in BMS dataset.
minUtil0.000010.000050.00010.00050.001minCorr142551233788518231minCorr2930510388271190minCorr3539411335251188Table 10
The total number of Correlated HUIs whenminUtil and minCorr are varied in Mushroom dataset.
minUtil0.0050.0060.0070.0080.009minCorr19555993034897718627682922minCorr24809947118457594447343380minCorr32404123633230702264522372Table 11
The total number of Correlated HUIs whenminUtil and minCorr are varied in Chess dataset.
minUtil0.0050.0060.0070.0080.009minCorr1119279119268119261119250119203minCorr24925649245492384923449231minCorr31948519475194691946519463


### 5.2. Runtime

The runtime of the proposed ECoHUPM algorithm was compared with those of two state-of-the-art Correlated HUIs mining algorithms: CoHUIM and CoHUI-Miner. For each dataset, theminUtil threshold was adjusted, and the runtime execution of each algorithm was calculated. Figures 11 and 12 show the results for the sparse and dense datasets, respectively. It can be observed that ECoHUPM is faster than CoHUIM and CoHUI-Miner. Further, it is found that ECoHUPM is significantly faster than CoHUIM on sparse datasets such as Foodmart (up to 12.8 times) and Ecommerce (up to 15.6 times) and on very sparse datasets such as BMS (up to 8.7 times). For the dense datasets, it is observed that, in most cases, the CoHUIM fails to discover the Correlated HUIs when the minUtil and minCorr thresholds are set to low values as is shown on the Mushroom dataset with minCorr = [0.35–0.45] and minUtil = [0.005–0.009]. Meanwhile, when the thresholds are set to high values such as minCorr = 0.5 and minUti = [0.05–0.09], the ECoHUPM is faster than CoHUIM (up to four times). Similarly, on very dense datasets such as Chess, CoHUIM fails to discover the Correlated HUIs with minCorr = [0.7–0.8] and minUtil = [0.005–0.009]. Meanwhile, when the thresholds are set to high values such as minCorr = 85 and minUti = [0.08–0.28], the ECoHUPM is faster than CoHUIM (up to 4.6 times).Figure 11
Runtime for sparse datasets. (a) Foodmart (minCorr = 0.1). (b) Foodmart (minCorr = 0.2). (c) Foodmart (minCorr = 0.3). (d) Ecommerce (minCorr = 0.1). (e) Ecommerce (minCorr = 0.2). (f) Ecommerce (minCorr = 0.3). (g) BMS (minCorr = 0.5). (h) BMS (minCorr = 0.6). (i) BMS (minCorr = 0.7).
(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure 12
Runtime for dense datasets. (a) Mushroom (minCorr = 0.35). (b) Mushroom (minCorr = 0.4). (c) Mushroom (minCorr = 0.45). (d) Mushroom (minCorr = 0.5). (e) Chess (minCorr = 0.70). (f) Chess (minCorr = 0.75). (g) Chess (minCorr = 0.80). (h) Chess (minCorr = 0.85).
(a)(b)(c)(d)(e)(f)(g)(h)On the other hand, the ECoHUPM is faster than the CoHUI-Miner on sparse datasets such as Foodmart and Ecommerce (up to 5 and 2.2 times, respectively) and it is slightly faster on very sparse dataset such as BMS (up to 1.3 times). For dense datasets with low threshold values, the ECoHUPM is significantly faster than the CoHUI-Miner on the Mushroom dataset (up to 3.2 times) and on very dense datasets such as Chess (up to 4.3 times faster). Meanwhile, with high threshold values, the ECoHUPM is slightly faster than the CoHUI-Miner on Mushroom dataset (up to 2.1 times faster) and on Chess dataset (up to 1.4 times faster).The main reason why the ECoHUPM algorithm is always faster than CoHUIM and CoHUI-Miner algorithms is that the novel CoUTlist structure is highly effective in reducing the database size as compared to the projection mechanism used on CoHUIM and CoHUI-Miner algorithms. That is, in the CoUTlist, each element represents a set of transactions where the itemset occurs in the same path. Meanwhile, in the projected database, each element represents a single transaction where the itemset occurs. Moreover, the proposed pruning properties help in reducing the search space.The CoHUIM algorithm performs two phases. It first generates the candidate itemsets whose correlation is equal to or greater than theminCorr threshold, and then it calculates the utility of each candidate. Hence, in all datasets, CoHUIM is much slower than the CoHUI-Miner and the proposed ECoHUPM.The size of the projected database of an itemset increases as the density of the datasets is increased and thus the cost of building the projected database of the supersets is also increased. Thus, the CoHUIM could not find the Correlated HUIs when it was run on Mushroom and Chess datasets with lowminUtil and minCorr thresholds. This is because it suffers from excessive dataset scanning in the second phase.The CoHUI-Miner is a One-Phase algorithm. However, due to the big size of the projected database of each itemset as compared to the CoUTlist especially in dense and very dense datasets, the proposed ECoHUPM is significantly faster than the CoHUI-Miner on Mushroom and Chess datasets.In very sparse datasets, the size of the CoUTlist of each itemset is slightly smaller than the size of the projected database. Hence, the proposed ECoHUPM is slightly faster than the CoHUI-Miner in BMS dataset.


### 5.3. Memory Usage

The comparison of the memory usage of the proposed ECoHUPM against CoHUIM and CoHUI-Miner is shown in Figure13. In this figure, the Y-axis represents the memory usage which is measured by the memory_usage module in Python.Figure 13
Memory usage. (a) Foodmart. (b) Ecommerce. (c) BMS. (d) Mushroom. (e) Chess.
(a)(b)(c)(d)(e)It is observed that the proposed ECoHUPM algorithm consumes less memory as compared to the CoHUIM and CoHUI-Miner in all datasets. More specifically, on the sparse datasets such as Foodmart and Ecommerce, the memory usage of the CoHUIM occupies 1.5 and 3 times the memory of the proposed ECoHUPM, respectively. Meanwhile, on very sparse datasets such as BMS, the memory usage of the CoHUIM occupies 2.2 times the memory of the proposed ECoHUPM.Likewise, on sparse and very sparse datasets such as Foodmart, Ecommerce, and BMS, the CoHUI-Miner occupies 1.07, 1.8, and 1.3 times the memory of the proposed ECoHUPM, respectively. Meanwhile, on dense and very dense datasets such as Mushroom and Chess, the CoHUI-Miner occupies 1.7 and 2.2 times the memory of the proposed ECoHUPM, respectively.


## 5.1. Datasets Used

We used five standard datasets downloaded from SPMF library [54], two real-life datasets with real utility values (Foodmart and Ecommerce), and three real-life datasets with synthetic utility values (BMS, Chess, and Mushroom). Characteristics of the considered datasets are shown in Table 6.Table 6
Characteristics of the used datasets.
Dataset nameDescriptionTransactions countItems countAverage items count per transactionHas real utility values?Sparse or denseFoodmartDataset of customer transactions from a retail store, obtained and transformed from SQL-Server 2000.4,1411,5594.42YesSparse datasetEcommerceTransactional dataset which contains all the transactions occurring between 01/12/2010 and 09/12/2011 of a UK-based and registered nonstore online retail.14,9753,80315.4YesSparse datasetBMSClick stream data from a web store used in KDD-Cup 2000.59,6024972.51NoVery sparse datasetMushroomPrepared based on the UCI mushrooms dataset.8,12411923NoDense datasetChessPrepared based on the UCI chess dataset.3,1967537NoVery dense datasetminCorr is adapted with three times on each sparse dataset and four times on each dense dataset to evaluate the efficiency of the proposed ECoHUPM algorithm and they are denoted, respectively, as ECoHUPM-minCorr1, ECoHUPM-minCorr2, ECoHUPM-minCorr3, and ECoHUPM-minCorr4. The different three minCorr thresholds are, respectively, set as follows: (1) in Foodmart dataset, 0.1, 0.2, 0.3; (2) in Ecommerce dataset, 0.1, 0.2, 0.3; (3) in BMS dataset, 0.5, 0.6, 0.7; (4) in Mushroom dataset, 0.4, 0.45, 0.5, 0.55; and (5) in Chess dataset, 0.7, 0.75, 0.8, 0.85. Because all algorithms use the same measures to evaluate the interestingness of the extracted patterns, all algorithms resulted in the same number of patterns in all experiments. Tables 7–11 show the total number of Correlated HUIs when minUtil and minCorr are varied in each dataset.Table 7
The total number of Correlated HUIs whenminUtil and minCorr are varied in Foodmart dataset.
minUtil0.000010.000050.00010.00050.001minCorr15344352776475102102258minCorr2195119421893925257minCorr3157515731564915257Table 8
The total number of Correlated HUIs whenminUtil and minCorr are varied in Ecommerce dataset.
minUtil0.00050.00070.00090.00110.0013minCorr14956304018571167799minCorr21345977745592467minCorr3901645479386318Table 9
The total number of Correlated HUIs whenminUtil and minCorr are varied in BMS dataset.
minUtil0.000010.000050.00010.00050.001minCorr142551233788518231minCorr2930510388271190minCorr3539411335251188Table 10
The total number of Correlated HUIs whenminUtil and minCorr are varied in Mushroom dataset.
minUtil0.0050.0060.0070.0080.009minCorr19555993034897718627682922minCorr24809947118457594447343380minCorr32404123633230702264522372Table 11
The total number of Correlated HUIs whenminUtil and minCorr are varied in Chess dataset.
minUtil0.0050.0060.0070.0080.009minCorr1119279119268119261119250119203minCorr24925649245492384923449231minCorr31948519475194691946519463


## 5.2. Runtime

The runtime of the proposed ECoHUPM algorithm was compared with those of two state-of-the-art Correlated HUIs mining algorithms: CoHUIM and CoHUI-Miner. For each dataset, theminUtil threshold was adjusted, and the runtime execution of each algorithm was calculated. Figures 11 and 12 show the results for the sparse and dense datasets, respectively. It can be observed that ECoHUPM is faster than CoHUIM and CoHUI-Miner. Further, it is found that ECoHUPM is significantly faster than CoHUIM on sparse datasets such as Foodmart (up to 12.8 times) and Ecommerce (up to 15.6 times) and on very sparse datasets such as BMS (up to 8.7 times). For the dense datasets, it is observed that, in most cases, the CoHUIM fails to discover the Correlated HUIs when the minUtil and minCorr thresholds are set to low values as is shown on the Mushroom dataset with minCorr = [0.35–0.45] and minUtil = [0.005–0.009]. Meanwhile, when the thresholds are set to high values such as minCorr = 0.5 and minUti = [0.05–0.09], the ECoHUPM is faster than CoHUIM (up to four times). Similarly, on very dense datasets such as Chess, CoHUIM fails to discover the Correlated HUIs with minCorr = [0.7–0.8] and minUtil = [0.005–0.009]. Meanwhile, when the thresholds are set to high values such as minCorr = 85 and minUti = [0.08–0.28], the ECoHUPM is faster than CoHUIM (up to 4.6 times).Figure 11
Runtime for sparse datasets. (a) Foodmart (minCorr = 0.1). (b) Foodmart (minCorr = 0.2). (c) Foodmart (minCorr = 0.3). (d) Ecommerce (minCorr = 0.1). (e) Ecommerce (minCorr = 0.2). (f) Ecommerce (minCorr = 0.3). (g) BMS (minCorr = 0.5). (h) BMS (minCorr = 0.6). (i) BMS (minCorr = 0.7).
(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure 12
Runtime for dense datasets. (a) Mushroom (minCorr = 0.35). (b) Mushroom (minCorr = 0.4). (c) Mushroom (minCorr = 0.45). (d) Mushroom (minCorr = 0.5). (e) Chess (minCorr = 0.70). (f) Chess (minCorr = 0.75). (g) Chess (minCorr = 0.80). (h) Chess (minCorr = 0.85).
(a)(b)(c)(d)(e)(f)(g)(h)On the other hand, the ECoHUPM is faster than the CoHUI-Miner on sparse datasets such as Foodmart and Ecommerce (up to 5 and 2.2 times, respectively) and it is slightly faster on very sparse dataset such as BMS (up to 1.3 times). For dense datasets with low threshold values, the ECoHUPM is significantly faster than the CoHUI-Miner on the Mushroom dataset (up to 3.2 times) and on very dense datasets such as Chess (up to 4.3 times faster). Meanwhile, with high threshold values, the ECoHUPM is slightly faster than the CoHUI-Miner on Mushroom dataset (up to 2.1 times faster) and on Chess dataset (up to 1.4 times faster).The main reason why the ECoHUPM algorithm is always faster than CoHUIM and CoHUI-Miner algorithms is that the novel CoUTlist structure is highly effective in reducing the database size as compared to the projection mechanism used on CoHUIM and CoHUI-Miner algorithms. That is, in the CoUTlist, each element represents a set of transactions where the itemset occurs in the same path. Meanwhile, in the projected database, each element represents a single transaction where the itemset occurs. Moreover, the proposed pruning properties help in reducing the search space.The CoHUIM algorithm performs two phases. It first generates the candidate itemsets whose correlation is equal to or greater than theminCorr threshold, and then it calculates the utility of each candidate. Hence, in all datasets, CoHUIM is much slower than the CoHUI-Miner and the proposed ECoHUPM.The size of the projected database of an itemset increases as the density of the datasets is increased and thus the cost of building the projected database of the supersets is also increased. Thus, the CoHUIM could not find the Correlated HUIs when it was run on Mushroom and Chess datasets with lowminUtil and minCorr thresholds. This is because it suffers from excessive dataset scanning in the second phase.The CoHUI-Miner is a One-Phase algorithm. However, due to the big size of the projected database of each itemset as compared to the CoUTlist especially in dense and very dense datasets, the proposed ECoHUPM is significantly faster than the CoHUI-Miner on Mushroom and Chess datasets.In very sparse datasets, the size of the CoUTlist of each itemset is slightly smaller than the size of the projected database. Hence, the proposed ECoHUPM is slightly faster than the CoHUI-Miner in BMS dataset.


## 5.3. Memory Usage

The comparison of the memory usage of the proposed ECoHUPM against CoHUIM and CoHUI-Miner is shown in Figure13. In this figure, the Y-axis represents the memory usage which is measured by the memory_usage module in Python.Figure 13
Memory usage. (a) Foodmart. (b) Ecommerce. (c) BMS. (d) Mushroom. (e) Chess.
(a)(b)(c)(d)(e)It is observed that the proposed ECoHUPM algorithm consumes less memory as compared to the CoHUIM and CoHUI-Miner in all datasets. More specifically, on the sparse datasets such as Foodmart and Ecommerce, the memory usage of the CoHUIM occupies 1.5 and 3 times the memory of the proposed ECoHUPM, respectively. Meanwhile, on very sparse datasets such as BMS, the memory usage of the CoHUIM occupies 2.2 times the memory of the proposed ECoHUPM.Likewise, on sparse and very sparse datasets such as Foodmart, Ecommerce, and BMS, the CoHUI-Miner occupies 1.07, 1.8, and 1.3 times the memory of the proposed ECoHUPM, respectively. Meanwhile, on dense and very dense datasets such as Mushroom and Chess, the CoHUI-Miner occupies 1.7 and 2.2 times the memory of the proposed ECoHUPM, respectively.


## 6. Conclusion

This paper proposed an efficient algorithm named ECoHUPM for mining Correlated HUIs. The ECoHUPM algorithm adopts divide-and-conquer approach and employs UTtree structure which is an extended form of FP-tree. A novel data structure based on the UTtree named CoUTlist is proposed in the ECoHUPM to store sufficient information for mining the desired patterns in an efficient manner. Three new pruning properties have been introduced and applied to reduce the search space and improve the mining performance. The first proposed pruning property isUpper Bound property based on summation of Utility and the Path Utilities (UBUPU), the second one is Lower Bound property based on the Node Utility (LBNU), and the third one is Sorted-Reversing Downward Closure (SRDC) property based on Kulc measure.An extensive experimental evaluation was conducted on five datasets including sparse, very sparse, dense, and very dense datasets. The experimental results show that the proposed ECoHUPM algorithm is efficient as compared to the state-of-the-art CoHUIM and CoHUI-Miner algorithms in terms of both time and memory consumption.



---

*Source: 7310137-2021-07-28.xml*