Multi-objective Boolean grey wolf optimization based decomposition algorithm for high-frequency and high-utility itemset mining

1.   Introduction

In data mining, frequent itemset mining is the process of retrieving a frequently used itemset from a transaction database to determine the relationship among the individual items to improve productivity. For example, in a supermarket database, identifying frequently purchased combinations of items will lead the investor to buy more stock of the items together and thus improve the supplies, which will result in more profit. This identification also helps to promote the itemset with attractive offers, so that the likelihood of purchase in a shop will be increased significantly. Due to this advantage, a significant number of researchers have contributed to frequent itemset mining to find the best combined itemsets ^[1].

In general, an itemset can be termed as a frequent itemset if and only if its appearance in the database is not less than the user specified value ($mi{n}_{freq})$. However, considering only the frequency of an itemset does not lead to an optimal discovery of the itemset which gives us the most profit. Users who check for more profit may feel that frequency based mining alone is not that effective. Utility is another consideration for improving profits, as used in what is usually called high-utility itemset mining (HUIM) ^[2], which counts the profit achieved through every itemset in the transaction database. In this utility mining, every item has a profit value and a number of occurrences in the database. An itemset can be termed as a high-utility itemset if and only if its profit in the database is not less than the user specified value ($mi{n}_{util})$.

Most of the studies on itemset mining consider either frequency or utility. In other words, the two factors are considered as separate objectives. With this perspective, if an itemset needs to be discovered with high frequency and high utilization, a set of solutions which cross the minimum threshold for frequency must first be discovered, and then the minimum threshold value of utility will be applied to obtain an itemset. With this procedure, there may be a possibility of obtaining empty sets if the transaction database is very large. Also, applying an algorithm twice to solve a problem is not computationally efficient. For example, an itemset with high-frequency items may have a very low utility value, and vice versa. Hence, addressing this as a multi-objective optimization problem is worthy.

Evolutionary algorithms, based on evolution in nature, perform well in terms of solving optimization algorithms in multi-objective solution space. Algorithms such as the genetic algorithm ^[3], particle swarm optimization ^[4], the ant colony optimization algorithm ^[5], the cuckoo search algorithm ^[6], etc. are prominent evolutionary methods for solving optimization problems. This work extends the work of Pazhaniraja et al. (2020), which sought to perform high utility itemset mining with the Boolean grey wolf optimization algorithm (BGWO) ^[7]. In this work, the BGWO is modeled to solve the multi-objective optimization problem of high-frequency and high-utility mining using decomposition factor.

The grey wolf optimization algorithm (GWO) organizes the roles in the wolf pack according to the pack hierarchy ^[8]. GWO is used in many optimization tasks since it has fewer constraints and does not need imitative knowledge in the first search. This inventive technique is simple and accomplishes a balanced diversification and intensification procedure over the search area ^[9]. GWO has quickly garnered a broad research audience from many fields. Recently, a multi-objective GWO (MOGWO) was developed to solve optimization problems with various and competing objectives ^[10]. MOGWO integrates a static auxiliary archive for preserving and retrieving Pareto optimal solutions. The societal and hunting behaviors of grey wolves are then simulated using this algorithm. Even though MOGWO has outperformed other multi-objective optimizers, there remains potential for further development.

The contributions of this research work are as follows:

● An effective multi-objective Boolean grey wolf optimization algorithm (MOBGWO) has been designed and developed to handle binary-based multi-objective optimization problems.

● Effective Boolean operators are designed to handle the generation of feasible solutions that include stochastic randomness and uncertainty in solution generation to maintain non-determinism.

● The proposed MOBGWO model is utilized for HFUI from a multi-objective perspective considering frequency and utility of the itemset.

The proposed algorithm has been analyzed by evaluating it with different sizes of datasets, from small to extremely large datasets. The formulated MOBGWO model is compared with other standard techniques to prove the significance of the proposed algorithm. The motivating factor for proposing a multi-objective optimization algorithm is the "No Free Lunch Theorem" proposed by Wolpert, D. H., and Macready, W. G., in 1997 ^[11]. As per Wolpert's theorem, there exists no single algorithm that can solve all optimization problems. When we compare the performances of all optimization algorithms, the performance averages will be equal to one another. This is the base motivation of our proposed algorithm. However, there are a significant number of approaches for solving multi-objective optimization problems, and every individual problem has its own features to be handled which are not generic in nature. Our proposed algorithm addresses one such aspect of itemset mining in this research work.

The rest of the work is structured as follows: Section 2 discusses related studies on recent algorithms that have been proposed for HFUI. Section 3 illustrates the multi-objective problem formulation of HFUI. Section 4 discusses the proposed multi-objective Boolean grey wolf optimization based decomposition algorithm for performing HFUI. Section 5 deals with the experimental evaluation of the formulated model, and the final section concludes the paper with future directions.

2.   Literature survey

In 1994, Agrawal and Srikant formulated the frequent itemset mining problem ^[12] and solved it using the Apriori algorithm. Since then, several approaches have been framed and proposed, such as Partition-1 ^[13], FP-Growth ^[14], Eclat ^[15] and KDCI ^[16]. These techniques are effective only for mining that does not care about profit, since high frequency may not always lead to high profit. Hence, in 2004, Huo et al. ^[17] formulated utility-based itemset mining, through which they discovered a high-utility itemset from the transaction database. In a proposal by Lie et al. ^[18], the items are pruned to reduce the cost of computation, and the method uses the transaction-weight utility property. Since then, several approaches have been proposed ^{[19,20,21,22,23]} for performing high-utility itemset mining. When there exists a greater number of itemset on the perspective of either frequent or utility there exists a problem which are all to be preserved. To address this problem, an effective top $k$ high utility itemset mining algorithm was proposed which utilizes a threshold value ^[24,25], and some open-source software tools were also proposed ^[26].

The approaches of traditional algorithms are effective, but the exhaustive search-based models are highly time-consuming processes. Meanwhile, stochastic optimization models using evolutionary techniques are intended to solve the optimization issues in appropriate ways with computational efficiency. The first such approach for HUIM is the genetic algorithm ^[27], which uses a ranked mutation model for mining high-utility itemsets (HUIs). Using particle swarm optimization, the discrete particle swarm optimization algorithm was proposed for HUIM, and some of the same authors later proposed a binary version of the particle swarm optimization algorithm for mining HUIs ^[28,29]. Another model, called an ant colony system ^[30], has been proposed for HUIM, in which processes such as the two-way pruning model were imposed for effective handling of a transaction database for the mining process.

In a similar way, several approaches have been presented for performing HUIM and high-frequency and high-utility mining. Evolutionary algorithms are not only intended to solve mining problems but are also used in other research domains such as mathematical benchmark functions and many more. Other applications can be found in ^{[31,32,33,34]}. The intention of this research is to propose an effective multi-objective model for performing HFUI.

The choice of GWO has been made based on its simplicity and the wide usage of the algorithm for solving various applications in different domains from both single-objective and multi-objective perspectives. Some of the applications include a routing problem in a dual supply chain which considers both the price and the duration of delivery from a case study on a construction material supplier in 2022 by Abbaspour et al. ^[35]. In 2022, Asgari et al. proposed a multi-objective variant of GWO for analyzing a solar based tri-generation system ^[36]. In 2022, Hasanzadeh et al. proposed another multi-objective variant of GWO for solving the combination of solid oxide fuel cell with other hybrid and standalone gas turbines ^[37]. However, based on the "No Free Lunch Theorem" ^[7], our proposed algorithm is developed to perform multi-objective HFUI.

In 2022, Xuan Liu, Genlang Chen and Wanli Zuo ^[38] proposed the EMSFUI-D and EMSFUI-B algorithms to identify high utility itemsets. These algorithms holds two different pruning mechanisms to rule out the least utilized items without considering them for fitness evaluation. High average-utility itemset mining involves evaluating a quantitative consumer transactional database in order to discover high average-utility itemsets, or groupings of items with high average usefulness. In 2022, Le. B. et al. ^[39] proposed to mine frequent HAUI that involves evaluating a quantitative consumer transactional database in order to discover high average-utility itemsets, or groupings of items with high average usefulness. In 2023, Luna et al. ^[40] proposed top-k high utility itemset mining through genetic algorithms for performing high utility itemset extraction. It directs the search process by evaluating the usability of each item to provide initial solutions and combines solutions appropriately, hence lowering runtime and memory usage. However, the effective mechanism to identify high utility itemset mining is still in debate, and, as per the statement of the No Free Lunch theorem, the proposed algorithm is being used for identifying the high utility itemset from a different objective's perspective.

3.   System design

In this section a detailed description of frequency and utility itemset mining is given along with an example model. Based on this problem definition, the objectives of the problem are also given in this section.

3.1.   Problem formulation of high frequency and high utility itemset mining

Let us consider Table 1 as a transaction database ($D$) consisting of eight transactions $T$ = {${t}_{1}, {t}_{2}, {t}_{3}, {t}_{4}, {t}_{5}, {t}_{6}, {t}_{7}, {t}_{8}$}, each with a unique $id$ ranging from 1 to 8. In general, a transaction database consists of $m$ finite sets of transactions $T$ = {${t}_{1}, {t}_{2}, \dots, {t}_{m}$} in which each transaction has a varied number of items in it. As a single set, the number of distinct items ($n$) in all the transactions is represented as $I = \left\{{i}_{1}, {i}_{2}, \dots, {i}_{n}\right\}$. A transaction can be named as a supporting transaction when a set of items ($X$) is presented in that transaction. The supporting transactions of the itemset is the number of overall transactions that contains the itemset $X$, and it can be represented as ${D}_{X}.$ The itemset $X$ is a frequent itemset if $\mathit{freq}\left(X\right)\ge mi{n}_{sup}$, where $mi{n}_{sup}$ is the threshold value specified by the user, and $\mathit{freq}\left(X\right)$ denotes the total number of transactions that contain itemset $X$.

In Table 1, the items are represented as pairs of item names and numbers. For example, in transaction ${t}_{1}$, the term $\left(a, 3\right)$ denotes that the item $a$ is utilized 3 times in transaction ${t}_{1}$. Likewise, in every transaction, each item is specified with a utilization value of the item which is used in that transaction, ${t}_{id}$. The overall efficacy of each transaction is given as $W\left({t}_{id}\right)$ in the last column of Table 1.

In Table 1, there are 10 distinct items in the transaction database ($D$) $I = \left\{a, b, c, d, e, f, g, h, i, j\right\}$ and eight transactions $T$ = {${t}_{1}, {t}_{2}, {t}_{3}, {t}_{4}, {t}_{5}, {t}_{6}, {t}_{7}, {t}_{8}$}. For example, let us consider an itemset $X = \left\{a, b\right\}$. The supporting transactions of itemset $X$ in database $D$ are ${D}_{X} = \left\{{t}_{1}, {t}_{2}, {t}_{3}, {t}_{6}, {t}_{8}\right\}$, and thus $\mathit{freq}\left(X\right) = \frac{\left|{D}_{X}\right|}{\left|T\right|}$, which is $\frac{5}{8}$ for the itemset $\left\{a, b\right\}$. The itemset $X$ can be termed as a frequent itemset if $mi{n}_{freq}$ is set in the interval (0 to 0.6).

The weight of an item in a transaction is represented as $W\left({t}_{id}, i\right)$. For example, the weight of item $a$ in transaction ${t}_{1}$ is 3. Similarly, for weight of an itemset $X$ in a transaction ${t}_{i}$ can be represented as $W\left({t}_{id}, X\right)$. For example, the weight of itemset $X = \left\{a, b\right\}$ in the transaction ${t}_{1}$ is $W\left({t}_{1}, a\right)+W\left({t}_{1}, b\right) = 3+4 = 7$.

In a similar way, the utility of an itemset ($X$) in the entire transaction database $D$ can be represented as follows:

For example, in transaction database $D$, $util\left(\left\{a, b\right\}, D\right) = \frac{7+21+11+14+21}{18+225+18+15+23+16+6+27} = \frac{74}{348} = 0.21$. Similarly, $util\left(\left\{b, e\right\}, D\right)$ is 0.61. If $m{in}_{util}$, through which high utility itemsets can be defined, is set to 0.5, itemset $\left\{b, e\right\}$ will be denoted as a high utility itemset, and the itemsets $\left\{a, b\right\}$ will be discarded. Similarly, the other high utility itemset in the transaction database $D$ are identified as $util\left(\left\{a, e\right\}, D\right) =$ 0.60, $util\left(\left\{c, e\right\}, D\right)$ = 0.62, $util\left(\left\{a, b, e\right\}, D\right)$ = 0.63, $util\left(\left\{a, c, e\right\}, D\right)$ = 0.60, $util\left(\left\{b, c, e\right\}, D\right)$ = 0.62 and $util\left(\left\{a, b, c, e\right\}, D\right)$ = 0.64.

3.2.   Multi-objective formulation for high frequency and high utility itemset mining

In high frequency and high utility itemset mining, the two factors of frequency of an itemset and its utility in the database can be observed as two different objectives in a multi-objective optimization model, as discussed here. The two factors are considered as two different objectives based on the inference as follows:

Theorem 1. In a transaction database D, a high-utility itemset may have low frequency, and a low-utility itemset may have high frequency.

Proof: From Table 1, in a transaction database $D$, the frequency of item {a} is 0.8, and its utility is 0.05. In this example, the frequency of the itemset meets the user constraint when $mi{n}_{freq}$ is set to 0.5. However, the utility does not meet the user constraint when $mi{n}_{util}$ is set to 0.5. On the other hand, if the itemset $X$ is $\{a, e\}$, then the frequency of $X$ in the transaction database $D$ is 0.2, and its utility is 0.60. Thus, the utility of the itemset $X$ satisfies the user constraint, whereas the frequency does not, provided that $mi{n}_{freq} = mi{n}_{util} = 0.5$. Thus, the transformation of high frequency and high utility itemset mining into a multi-objective optimization is valid.

Hence, the objectives of the problem can be represented as follows:

4.   Multi-objective Boolean grey wolf optimization based decomposition algorithm

In this section, detailed descriptions of the standard grey wolf optimization algorithm (GWO), the conversion of the standard GWO into the Boolean GWO and the multi-objective Boolean GWO with decomposition algorithm for performing multi-objective high frequency and high utility itemset mining are given.

4.1.   Standard GWO

In the past decade, bio-inspired optimization algorithms have been applied by researchers to solve a number of significant optimization problems, including combinatorial problems such as the Traveling Salesman Problem, knapsack problems, virtual machine placement in cloud computing, etc. They have such wide applications because they possess simplicity, such as straightforward implementation irrespective of gradient information. One such optimization algorithm is the grey wolf optimization algorithm ^[8]. It is inspired from the social behavior of wolves, as they possess good leadership and high-level hunting strategies toward their prey. They are among the high-level predators and work in groups with sizes varying from 5 to 12 naturally.

The wolves are further classified as Alpha, Beta, Delta and Omega wolves. Alpha wolves ($\alpha$) are responsible for decision making, and it is the most dominant wolves' category when compared to other categories of wolves. These wolves instruct the other wolves of the group. Alpha wolves are responsible for production of new wolves. Beta wolves ($\beta)$ are the wolves with the category next to the Alpha wolves. These wolves help the Alpha wolves in planning. Beta wolves will assume leadership of the wolves' group in the absence of Alpha wolves. In the presence of Alpha wolves, these Beta wolves will act as the responding wolves for the decisions made by the Alpha wolves. In the third category are the Delta wolves ($\delta$). These wolves are the subordinate wolves in the pack and are the next level of wolves. These wolves fall under the classifications of elders, sentinels, hunters, scouts and caregivers. As the last category of wolves, the Omega wolves ($\omega$) are the lowest ranking wolves and play the role of scapegoat. They obey the instructions provided by all other wolves in the group.

The formation of GWO is based on tracking, chasing and approaching the prey of the wolves. The wolves perceive, encircle and harass the prey until the prey's movement stops. Then, they attack the prey in an effective manner. The GWO is effective for exploration and the exploitation phase of a search strategy in solution space. However, the standard GWO is proposed for solving continuous optimization problems such as mathematical benchmark problems, tension/compression spring design, welded beam design, etc. HFUI, on the other hand, is a binary based solution representation in which the conventional operators of standard GWO will not be very effective for generation of new solutions for the next iterations. Hence, Pazhaniraja et al. proposed a Boolean based grey wolf optimization algorithm ^[7] for performing HUI mining. In the next section, a description of BGWO is given in brief.

4.2.   Boolean based grey wolf optimization algorithm

In this section, the Boolean based GWO is described in brief. It is highly recommended to visit the origin of this algorithm in ^[7]. For further proper understanding of this paper a brief note is given as follows: There are, in total, 5 Boolean operators used in BGWO which replace the conventional operators in the standard GWO for processing the HFUI problem. The representation of a solution is first given in this section, through which the further processing can be applied.

4.2.1.   Solution representation

From the example of Table 1, the database $D$ consists of eight transactions $T = \left\{{t}_{1}, {t}_{2}, \dots, {t}_{8}\right\}.$ In the first transaction, out of 10 distinct items, only 4 items, namely, $\{a, b, c, d\}$, are included. This can be represented as a set $D\left({t}_{1}\right) = \left[1\; \; 1\; \; 1\; \; 1\; \; 0\; \; \; \; \; \; \; \; 0\; \; 0\; \; 0\; \; 0\; \; 0\right]$ which shows that items $\{a, b, c, d\}$ are included, and items {$e, f, g, h, i, j$} are not included. In this way, the whole database can be represented as follows:

where ${T}_{d}$ denotes the row of the transaction, and $\{a, b, c, d, e, f, g, h, i, j\}$ specifies the column items.

4.2.2.   De Morgan's AND ($\Lambda$)

De Morgan's law specifies a sequence of conversion rules that includes valid rules of inference. In a De Morgan's AND gate, the resultant factor will be 1 if any input value holds 0, and the output value will be 0 if both the input values are 1. A 2-bit input model of a De Morgan's AND gate is shown in Table 2.

4.2.3.   Difference ($⊝$)

The Boolean difference gives output in two vectors, namely, Difference and Borrow. For a 2-bit input, the borrow will return as 1 only if the first bit is 0 and the second bit is 1. In all other cases, the value of borrow will be 0. For the difference vector, the output will be one if and only if only one of the inputs is 1; otherwise, the result will be 0. Table 3 shows the values of 2-bit vectors.

4.2.4.   Binary Adder ($\mathrm{♁}$)

Table 4 shows the input and output of the 2-bit input model of Binary Adder. Like the Difference operator, this Binary Adder also returns two different vectors, namely, Sum and Carry. Carry will return 1 only if both the inputs are 1. For Sum, the output will be 1 if and only if only one of the inputs is 1; otherwise, the resultant will be 0.

4.2.5.   Multiplexer (with uncertainty) ($\bowtie$)

A multiplexer of ${2}^{n}$ inputs has $n$ select lines, which are used to select which input line to send to the output. (${\boldsymbol{S}}_{{\bf{0}}}$). A generalized equation for the Multiplexer is given below. In our model the multiplexer is responsible for the uncertainty factors $A$ and $C$.

There are two coefficient components, A and C, in the suggested model. The uncertainty factors are caused by these two components. These two factors are responsible for the stochastic randomness during the search process.

4.2.6.   2-bit circular shift (left and right) ($\mapsto, ↤$)

The process of moving the last element in a tuple to the first place while shifting all other entries to the next position, or carrying out the opposite operation, is known as circular shift. A two-bit circular shift alternates between two places.

4.3.   Multi-objective Boolean grey wolf optimization based decomposition algorithm for HFUI

For solving multi-objective optimization problems, the proposed Boolean GWO is integrated with a decomposition-based optimization model. In decomposition, the problem is divided into subproblems which can be solved in an effective manner. In this section, the Boolean GWO is modeled to perform multi-objective HFUI. After the population initialization, the problem is divided into subproblems, and it proceeds by the finding of neighbors. Later, the solutions are evolved to next generation iteration.

4.3.1.   Initialization strategy

In general, optimization algorithms start with an initial population in a random manner. However, initializing in a random manner for itemset mining will often lead to infeasible solutions. For example, there is no combination of items $\{b, g\}.$ Suppose a solution is generated as [0, 1, 0, 0, 0, 0, 1, 0, 0, 0] and sent for fitness calculation; it will return a value 0. If this is chosen to be a crossover solution, then the generation of a child solution will also be ineffective. Thus, for an effective initialization, two things are required: 1. The generated solutions should indicate a valid itemset combination from the database. 2. The generated solutions after the search strategy through BGWO should also be a valid itemset. If these two conditions are met, then the convergence of optimal solutions in a shorter number of iterations is highly possible in the search strategy. Hence, two selection strategies are adopted from Multi-Objective Evolutionary Algorithm based Decomposition (MOEA/D) based HFUI mining.

Transaction Itemset: The transaction-itemset utility can be denoted as $util\left({t}_{i}\right).$ The sum of all transaction utilities can be computed as $\sum _{i = 1}^{\left|D\right|}util\left({t}_{i}\right).$ Individuals can be selected based on the probability of $\frac{util\left({t}_{i}\right)}{\sum _{i = 1}^{\left|D\right|}util\left({t}_{i}\right)}$

Meta-Itemset: Likewise for meta-itemsets, let us consider that there are 10 meta-itemsets in the transaction database $D$, namely, $\left\{a\right\}, \mathrm{ }\left\{b\right\}, \mathrm{ }\left\{c\right\}, \mathrm{ }\left\{d\right\}, \mathrm{ }\left\{e\right\}, \mathrm{ }\left\{f\right\}$, $\left\{g\right\}, \left\{h\right\}, \left\{i\right\}\mathrm{a}\mathrm{n}\mathrm{d}\left\{j\right\}$. The frequency of items can be calculated as $freq\left({M}_{i}\right).$ The collective calculation of frequencies can be computed as $\sum _{i = 1}^{\left|M\right|}freq\left({M}_{i}\right).$ Now, the choice if an individual can be selected is based on the probability $\frac{freq\left({M}_{i}\right)}{\sum _{i = 1}^{\left|M\right|}freq\left({M}_{i}\right)}$.

4.3.2.   Creation of subproblems

Let us consider that there are ${N}_{Pop}$ individuals in the population. ${N}_{Pop}$ subproblems are generated as follows:

are the evenly spread vectors in which each $\lambda$ corresponds to 2 values, namely, ${\lambda }_{i} = ({\lambda }_{i}^{1}, {\lambda }_{i}^{2})$ where the 2 refers to the number of objectives that satisfy ${\lambda }_{i}^{1}+{\lambda }_{i}^{2} = 1$. These subproblems are then solved using Tchebycheff method ^[41] which is formulated as

where ${z}^{\mathrm{*}} = ({z}_{1}^{\mathrm{*}}, {z}_{2}^{\mathrm{*}})$ is the reference point that records the maximum value for individual fitness function.

4.3.3.   Finding neighbors

After the creation of subproblems, the solutions used to find their neighbors for further processing. Euclidian distance for every subproblem with other subproblem is computed and then sort the individual's based on the Euclidian distance in descending order. Then extract the first $NB$ number of individuals and name it as the neighbours of every corresponding individual.

4.3.4.   Dominant determination

In Section 3.2 description of multi-objective optimization model is given, and the domination strategy that identifies the solutions with better results in different objective functions is defined. In this section, the pseudocode of dominant determination is given. A solution $x$ can be termed as a non-dominant solution iff none of the objective value of that solution is lesser than the other solution's objective values. The pseudocode is given in Algorithm 1.

Table 5 represents the parameters used in Algorithms 1 and 2 and the respective variables that represent the parameters. Algorithm 1 represents the dominance identification model. In Algorithm 2, the actual working procedure of the Boolean multi-objective optimization-based decomposition algorithm is presented.

After calculating the domination of individuals, the solution for the next generation is computed using BGWO, which is given in Algorithm 2. In the later part, once again, the decomposed cost and determination of domination of individuals are computed to update the external population (EP).

4.3.5.   Working model of MOBGWO

In the initial phase, three different random binary vectors are generated, namely, $\overrightarrow{a}, {\overrightarrow{r}}_{1}, {\overrightarrow{r}}_{2}$, which are the basic blocks for the construction of coefficient factors $\overrightarrow{A}, \overrightarrow{C}$ respectively. For the construction of coefficient vector $\overrightarrow{A}$, a Boolean operation "AND" gate is used between the vector $\overrightarrow{a}$ with left two-bit circular shift and a difference vector between $\overrightarrow{a}$ and ${\overrightarrow{r}}_{1}$. Similarly, the coefficient vector $\overrightarrow{C}$ is prepared by right two-bit circular shift on ${\overrightarrow{r}}_{2}.$

In the population initialization phase, every solution vector (${\overrightarrow{\psi }}_{i}$) is prepared randomly, and its respective fitness values are also calculated using two objective functions, namely, ${f}_{1}$ and ${f}_{2}$. The best fitness value is recorded in the variable $\mathcal{z}$.

A subset of vectors 𝜆 is generated for decomposing the problem based on the number of objectives. This vector is responsible for the weightage given to the objectives for every solution. Since a different combination strikes out during the iteration, the combinations will have high probability to end up with optimal Pareto front solutions.

For every solution, the near neighbor solutions (i.e., $T$ solutions) are identified based on the Euclidian distance between the 𝜆 vector representations of every solution. Then, for every solution, the decomposed cost will be identified as ${g}_{i}$. Now, the domination factor of every solution is identified based on Algorithm 1.

Based on the default threshold values to segregate the wolves as alpha, beta and gamma wolves, the solution is sorted based on the decomposition cost of every solution. Then, from sorted solution index 1 to ${L}_{1}$, the solutions will be treated as Alpha wolves. From ${L}_{2}$ (i.e., ${L}_{1}$+1) to ${L}_{3}$, the individuals will be treated as beta wolves, and the rest will be treated as Gamma wolves. Now, the evolution of wolves from one generation to the next generation will be carried out based on the Boolean operations described in Section 4.2.

After the identification of optimal solutions from the generated solutions, the best will be promoted for the further iteration evolution. The process will be continued till it reaches the maximum number of iterations, and the optimal solution will be registered at the end of the algorithm from the external population archive ($EP)$. Figure 1 shows the flowchart of the proposed MOBGWO.

5.   Experimental evaluation

In this section, the experimental setup for evaluation of the proposed algorithm, the datasets used for evaluation, the performance metrics for evaluation, and the results analysis are discussed in detail.

5.1.   Experimental setup and dataset

The formulated technique was executed in MATLAB v9.2 in a system configured with a Core i7 9th generation processor, 8 GB of RAM and a 1 TB HDD. The model bounds are shown in Table 6. The performance of the proposed algorithm is compared with existing multi-objective models, such as MOEA-HFUI ^[42], HUI-Miner ^[23], HUIM-ACS ^[30], FP-Growth ^[14], TKU-Miner ^[43], UBP-Miner ^[44] and BOEA-HFUI ^[45]. For evaluating the proposed algorithm, 12 real datasets were downloaded from the SPMF repository ^[46]. The details of the datasets are given in Table 7. None of the datasets holds the weight of each item in any transaction. Hence, the distribution of weights of each item is done based on the previous works ^[20,23,43] that generated the weight values for each item in the range 1 to 1000.

5.2.   Performance metrics

Two performance indicators, namely, Hypervolume ^[47] and coverage ^[48], were used to measure the formulated technique in a multi-objective solution space.

Hypervolume (HV): It is utilized to calculate the convergence and diversity of the population in the given solution space. Larger values of hypervolume indicate better performance of the algorithm.

Coverage (Cov): It determines the diversity in population of the algorithm. It can be mathematically represented as

where N indicates the total number of items and ${N}_{d}$ indicates the different items present in the external population. Larger values of coverage indicate better diversity achieved by the algorithm.

5.3.   Experimental analysis

The results of the proposed algorithm are compared with the other standard algorithms in terms of non-dominated solutions achieved from the multi-objective perspective, the curve of Pareto front solutions and the values achieved in terms of coverage and hypervolume for the given solution space.

Figure 2 shows the non-dominated solutions and their curves achieved with respect to the two objectives, namely, frequency and utility of the itemset. The achieved solutions are plotted in the graph for all 12 real time datasets which were obtained from the SPMF data repository.

The total number of non-dominated solutions achieved using MOBGWO for HFUI on the datasets Chess, Connect, Accidents, Mushroom, Foodmart, OnlineRetail, USCensus, Pamp, KDDcup99, Susy, BMS-Web-View-1 and Powerc were 12, 14, 10, 6, 6, 7, 13, 22, 24, 21, 10 and 11, respectively. The comparison of the achieved solutions over the existing algorithms are shown in Figure 3.

In Figure 3, the initialization strategy of the proposed algorithm is examined. Four different initialization strategies were being tested over a small number of datasets, namely, the Chess, Connect and Accidents datasets. Both the HV and Coverage were examined to fix the optimal initialization strategy. The compared models include MOBGWO-HFUI (rand), which represents the random generation of solutions irrespective of their infeasibility. The next model is MOBGWO-HFUI (Trans), which represents the probability initialization strategy through the transaction-itemset model. The next model is MOBGWO-HFUI (Meta), which represents the probability initialization strategy through the meta-itemset model. Finally, a hybrid initialization model MOBGWO-HFUI was used which is the fusion of Trans and Meta itemset initialization. This model holds half of the population with Trans and the other half with the meta itemset initialization model. The inferences and the analysis are discussed in this section.

From Figure 3 it can be inferred that both on convergence and diversity preservation the hybrid initialization model outperforms the existing initialization models. Figure 3(a), (c), (e) shows the performance of different initialization models for the performance indicator HV for the dataset Chess, Connect and Accident, respectively. Similarly, Figure 3(b), (d), (f) shows the performances of different initialization models for the performance indicator coverage for the datasets Chess, Connect and Accident, respectively. From the observation of Figure 3, it is worth it to use the hybrid initialization strategy for further implementation of the proposed algorithm.

Figure 4 shows the non-dominant solution set plot with respect to frequency and utility of the itemset obtained. There are 12 subplots showing the performance graphs of all algorithms for the 12 real time datasets, as indicated from the $a$ to $l$ subgraphs.

From Figure 4, on comparing the counts of non-dominant individuals, the following inferences are obtained. For the Chess dataset, the number of obtained non-dominant individuals for the algorithm MOEA-FHUI was 12, for HUIM-ACS was 5, for FP Growth was 6, for TKU Miner was 4, for HUI-Miner was 3, for UBP-Miner was 4, for BOEA-HFUI was 6 and for MOBGWO-HFUI was 12. Similarly, from the subgraphs we can perceive that the proposed algorithm obtained a greater number of Pareto front solutions when compared with the existing algorithms.

Tables 8 and 9 show the performance indicator values Coverage and Hypervolume, respectively. The values of the indicators range from 0 to 1. As the number approaches 1, it indicates the improvement of the algorithm. In Tables 8 and 9, a $\pm$ sign indicates the results in the range specified. The other three symbols (+ / - / ≈) indicate better, worse and equal performance compared to our proposed algorithm.

From Table 8, it is evident that the proposed algorithm outperforms the existing algorithms in eight datasets out of 12. Next to the proposed algorithm, MOEA-HFUI outperforms our proposed algorithm in 2 datasets, namely, Accidents and Powerc. The proposed algorithm performs significantly equally to the existing algorithm MOEA-HFUI in five datasets, namely, Chess, Connect, Mushroom, KDDcup99 and Susy. In Foodmart dataset TKU-Miner outperforms all existing algorithms including our proposed algorithm. On BMS-Web-View-1 dataset HUI-Miner, HUIM-ACS and our proposed MOBGWO-HFUI perform equally and achieve the maximum value 1. On comparing the proposed algorithm results with UDP-Mnier, the results effectively for 10 datasets out of 12 and on comparing with BOEA-HFUI proposed algorithm outperforms in eight different datasets out of 12.

From Table 9, the proposed algorithm MOBGWO-HFUI outperforms all the existing algorithm in eight datasets. The existing algorithm MOEA-HFUI outperforms the proposed algorithm on three datasets, namely, Mushroom, Foodmart and Susy dataset. The existing algorithm MOEA-FHUI significantly performs equally with our proposed algorithm MOBGWO-HFUI with Chess, Accidents, Pamp, KDDcup99 and Powerc datasets. On comparing the proposed algorithm results with UDP-Miner, the results are effective for 11 datasets out of 12 except BMS-Web-View dataset, and on comparing with BOEA-HFUI, the proposed algorithm outperforms in nine different datasets out of 12.

5.4.   Statistical analysis–Wilcoxon signed rank test on MOBGWO-HFUI vs other state-of-art algorithms

In Tables 10 and 11, we utilized non-parametrical pairwise Wilcoxon signed rank test comparing MOBGWO-HFUI with other existing algorithms on 12 real time datasets to demonstrate impact difference. "+" denotes the cases in which the Null Hypothesis ${H}_{0}$ is rejected, and the proposed MOBGWO-HFUI shows superior performance to the compared algorithm. "=" indicates that there exists no statistical difference between the compared algorithms. "-" indicates that ${H}_{0}$ is rejected, and MOBGWO-HFUI has worse performance than the other existing technique. At the end of each table, the overall cases of pairwise comparison are given. The p-values that fall below 1.76E-6 are rounded.

From Table 10 it is evident that the proposed algorithm is effective when compared to the other existing state of art algorithms. On analyzing the Wilcoxon signed rank test on Coverage values, MOBGWO-HFUI outperforms FP-Growth on all datasets. With HUI-Miner and HUIM-ACS, MOBGWO-HFUI competes equally on one dataset, and in the remaining 11 datasets MOBGWO-HFUI outperforms both the algorithms with significant differences. On competing with TKU-Miner, the proposed MOBGWO-HFUI outperforms in 10 different datasets, but TKU-Miner outperforms MOBGWO-HFUI in FoodMark and OnlineRetail datasets. With respect to MOEA-FHUI, MOBGWO-HFUI outperforms on 9 different datasets, competes equally with 1 dataset and loses on the other 2 datasets. Competing with UDP-Miner, MOBGWO-HFUI outperforms in 10 datasets, competes equally with one BMS-View dataset and lost to chess dataset in all the runs. Competing with BOEA-FHUI, MOBGWO-HFUI outperforms in eight datasets, competes equally with Connect dataset and loses to Accidents, PowerC and KDDcup99 datasets marginally. Overall, the performance of MOBGWO-HFUI is significant in positive aspects.

From Table 11 it is evident that the proposed algorithm is effective when compared to the other existing state of art algorithms. On analyzing the Wilcoxon signed rank test on Hypervolume values, MOBGWO-HFUI outperforms FP-Growth, HUIM-ACS and HUI-Miner on all datasets. On competing with TKU-Miner, proposed MOBGWO-HFUI outperforms in 11 different datasets, but TKU-Miner outperforms MOBGWO-HFUI in FoodMark dataset. With respect to MOEA-FHUI, MOBGWO-HFUI outperforms on 9 different datasets and loses on the other 3 datasets. Competing with UDP-Miner, MOBGWO-HFUI outperforms in nine datasets out of 12. Competing with BOEA-FHUI, MOBGWO-HFUI outperforms in eight datasets and lost to 4 other datasets marginally.

6.   Conclusions

In this paper, a multi-objective Boolean grey wolf optimization based decomposition technique was introduced for solving the high-frequency and high-utility itemset mining problem by addressing both the frequency and utility as objectives in a simultaneous manner. For solving this problem, the high-frequency and high-utility itemset problem was modeled in a multi-objective domain space with 2 objectives. Then, a Boolean based grey wolf optimization algorithm was modeled to solve the multi-objective optimization problem using decomposition factor. The decomposition factor solves the problem by breaking the problem into subproblems. In this scenario the multi-objective problem has been broken into subproblems and solved effectively. To evaluate the proposed algorithm, two performance indicators, namely, Hypervolume and coverage, were used to find the convergence and diversity achieved through the algorithm in the given solution space. Seven different multi-objective algorithms were tested in the same testbed to determine the impact of the proposed algorithm. A total of 12 real time datasets were used to prove the significance. statistical analysis using the Wilcoxon signed rank test shows the significance of the proposed algorithm over other existing algorithms. From all the classical, statistical analysis and interpretation of results in the above sections, it is proven that the proposed algorithm is effective when compared with the existing algorithms. The future direction of this research work can be extended with a greater number of objectives in itemset mining.

Acknowledgments

This research was supported by Princess Nourah bint Abdulrahman University Researchers Supporting Project number (PNURSP2023R195), Princess Nourah bint Abdulrahman University, Riyadh, Saudi Arabia.

Conflict of interest

The authors declare no conflicts of interest.