# An Incremental Interesting Maximal Frequent Itemset Mining Based on FP-Growth Algorithm

Authors: Hussein A. Alsaeedi; Ahmed S. Alhegami
Journal: Complexity
 (2022)

---

## Abstract

Frequent itemset mining is the most important step of association rule mining. It plays a very important role in incremental data environments. The massive volume of data creates an imminent need to design incremental algorithms for the maximal frequent itemset mining in order to handle incremental data over time. In this study, we propose an incremental maximal frequent itemset mining algorithms that integrate subjective interestingness criterion during the process of mining. The proposed framework is designed to deal with incremental data, which usually come at different times. It extends FP-Max algorithm, which is based on FP-Growth method by pushing interesting measures during maximal frequent itemset mining, and performs dynamic and early pruning to leave uninteresting frequent itemsets in order to avoid uninteresting rule generation. The framework was implemented and tested on public databases, and the results found are promising.


---

## Body

## 1. Introduction

Association rule mining (ARM) [1] has been widely used as a leading technique in data mining. It is usually utilized in analyzing marketing baskets. ARM commonly employs two main subtasks, namely mining of frequent itemsets to ensure a minimum support threshold and generation of association rules to satisfy a minimum confidence threshold. Most of the studies have addressed the efficiency criterion of frequent itemset mining as it normally entails more resource capacity and computing time [2].Frequent itemsets (FIs) can be mined from transaction databases through one of the traditional algorithms that can be generally grouped into two methods [3]: Apriori-based method, which is used for generating and filtering candidate itemsets such as Apriori algorithm [4], and tree-based method that is normally used for building FP-tree and then mining FIs from the FP-tree such as FP-Growth [5], TRR [6], PrePost+ [7], FIN [8], dFIN [9], and negFIN [10] algorithms. Since Apriori-based methods depend on continuous scanning of the database to generate multiple candidate itemsets, they require high I/O. On the contrary, tree-based methods scan the database only twice, but they need higher memory for constructing multiple sub-trees [2, 11].Generally, the representation of FIs can be either closed frequent itemsets (CFIs) or maximal frequent itemsets (MFIs). An FI is considered a CFI if it has no superset having the same support [12]. CFI algorithms include AprioriClose [13], FP-Close [14], Closet+ [15], CHARM [12], and NEclatClosed [16] algorithms. On the other hand, a given FI is described as an MFI only if any superset of the itemset is not frequent [17, 18]. MFI set is considerably smaller than that of FIs [19]. There are many competent algorithms used for mining MFIs such as MAFIA [20], GenMax [21], FP-Max [22], FP-Max∗ [23], Charm-MFI [24], PADS [25], SelPMiner [19], and CL-Max [26]. The FP-Max [22] and FP-Max∗ [23] algorithms use FP-Growth to build a tree as FP-tree and mine MFIs from the tree based on a bottom-up and divide-and-rule strategy.In dynamic data, when adding an incremental database to the previous databases, some previous FIs become invalid and new FIs appear due to the changes in the support value of some FIs. Generally, the traditional FI mining algorithms are ineffective for incremental data as the entire database is re-mined afresh [2]. Since transaction databases are unceasingly and dramatically growing, incremental FI mining algorithms are needed as useful for making decisions and getting real-time information sought by users.Many attempts have been made for processing incremental data without re-mining the entire updated databases such as FUP [27], FUFP-tree [28], FUFP-tree maintenance [29], FCFPIM [30], FPISC-tree [31], FIUFP-Growth [2], pre-large [32], pre-FUFP [33], and FPMSIM [11] algorithms. It is noteworthy that these algorithms were used for mining incremental FIs. IM_WMFI [17] and IMU2P-Miner [18] have been proposed to deal with incremental MFIs. The drawbacks of these algorithms are that they do not regard the factors of size and time of data entry and, therefore, require re-mining of the updated database. Since new data arrive over time, researchers have been motivated to propose techniques that update the entire model of previously discovered knowledge (PDK), instead of running the algorithms from a scratch, thus presenting a new incremental model such as [34–36], and our proposed framework [37].For association rules, two measures have been used: objective and subjective measures. Objective measures are statistical values, such as support, confidence, all confidence, and left [38]. These measures were used during mining, such as support in the first task and confidence in the second task of ARM. On the other hand, subjective measures, such as unexpectedness [39], actionability [40], and novelty [34, 36, 37], were used to capture the user's belief about the domain. However, these subjective measures were used at post-mining.Our proposed approach is motivated by the increasing need for an efficient MFI algorithm that deals with larger data entry over time. As an extended form of FP-Growth and FP-Max algorithms for mining incremental interesting MFIs, our method uses novelty metrics (NM) as a subjective measure during the process of the mining stage. A major contribution of this proposed framework is handling the time-changing data and user-domain knowledge. This is useful when many databases arrive at various times or from a distributed environment. Certainly, it is desirable to update the discovered frequent itemsets each time new data arrives. Moreover, the incremental nature of the proposed framework makes it valuable to mine interesting frequent items at the current time concerning the previously discovered frequent items more willingly than wholly mining all frequent items. So, dynamic pruning for these frequently discovered itemsets is performed in real time. The objective of dynamic pruning is to save time and reduce search complexity.This study introduces an algorithm, based on a tree structure, for mining interesting MFIs. The major contributions of our work are as follows: (1) extending the FP-Max algorithm for incremental MFI mining; (2) integrating subjective interestingness criterion (novelty measure) during the process of mining for reducing the count of discovered interesting MFIs and subsequently reducing search complexity; and (3) introducing a structure that handles all the items (frequent or infrequent) with related information along with previous discovered IMFIs for use next time to speed up the construction and size of the tree.This study is structured as follows. Section2 reviews the related work. Section 3 introduces the design issues of our approach. Section 4 discusses the experimental settings and results. Section 5 concludes the study.


## 2. Related Work

The concept of association rule mining was introduced by Agrawal et al. in 1993 [1], and the Apriori algorithm was proposed a year later [4] for mining FIs and generating association rules. The algorithm was used to generate and filter candidate itemsets in a level-by-level manner. However, a disadvantage of this method is that it generates several candidate itemsets, which need multiple database scans, thus consuming much time and high I/O. FP-Growth algorithm [5] was presented, using compact data structure as FP-tree to compact all transactions of the database inside the tree. This algorithm scans a database twice only, firstly for finding support for each item and secondly for building the FP-tree. Then, the algorithm recursively builds sub-trees to mine all FIs. A limitation of this algorithm, however, is its need to create multiple sub-trees to mine FIs, which, in turn, require considerable resources and processing time.MFI mining concept was later introduced as in MAFIA [20], FP-Max [22], FP-Max∗ [23], PADS [25], SelPMiner [19], and CL-Max [26]. MAFIA is an MFI method, which uses a bitmap representation to check itemsets’ support information without any database scan. A major disadvantage of this algorithm is that it is inefficient with respect to sparse databases [20]. FP-Max was then proposed to mine all MFIs, and it used FP-tree structure and MFI-tree structure [22]. FP-Max∗ is an FP-tree-based algorithm used for mining MFIs utilizing its own two-dimensional array structure, called FP array to improve mining performance by reducing the number of tree scans [23]. A drawback of these algorithms, however, is that in a dense database, the FP-trees become more compact and thus more memory usage and slower execution time. PADS is another FP-tree-based method that defines and uses a pattern-aware dynamic search order to pre-prune unnecessary operations [25]. It is praised for guaranteeing higher speed compared with the previous approaches. However, it is memory-consuming due to its storing conditional databases and time-consuming due to longer search space [25]. CL-Max is an algorithm, which uses k-means concept for MFI mining [26]. SelPMiner was introduced to utilize the optimizations of the search space pruning through itemset-count tree format [19].Remarkably, all the abovementioned algorithms have to do with static data. Consequently, new methods have been introduced to work on incremental data without re-mining the entire updated databases such as FUP [27], FUFP-tree [28], FUFP-tree maintenance [29], pre-large [32], and pre-FUFP [33] algorithms.Based on the concept of Apriori method, Cheung et al. introduced the FUP algorithm [27] to handle the new database and update FIs efficiently. This algorithm reduces the scans of the database. Based on previously found frequent or infrequent itemsets of the previous databases, the algorithm partitions discovered itemsets from the incremental database into four cases: Case 1: frequent in previous and incremental databases, so frequent in the updated database; Case 2: frequent in the previous database but infrequent in the incremental database, so frequent or infrequent in the updated database; Case 3: infrequent in the previous database but frequent in the incremental database, so frequent or infrequent in the updated database. Only if infrequent, rescanning of previous databases is needed; and Case 4: infrequent in previous and incremental databases, so infrequent in the updated database.However, many researchers preferred to use FP-Growth-based algorithms for better management of frequent itemset search in a dynamic database such as FUFP-tree algorithm, which was introduced as a developed algorithm to effectively deal with new transactions and improve the efficiency of the updated FP-tree structure, by reducing the number of rescans of the previous databases after adding an incremental database [28]. This FUFP-tree was characterized by double action of node insertion and deletion from the tree. The FUFP-tree algorithm [28] handles the itemsets based on the four principles of the FUP algorithm [27]: Case 1: frequent in previous and incremental databases, so support item is updated in header table and FUFP-tree; Case 2: frequent in the previous database but infrequent in incremental database, maybe frequent or infrequent. If frequent, support item is updated in header table and FUFP-tree, else the item from header table and all nodes from FUFP-tree are deleted; Case 3: infrequent in previous databases but frequent in incremental databases, maybe frequent or infrequent. If frequent, the item is placed at the end of the header table and its nodes to the leaf node of a path in the FUFP-tree are added, else nothing is done; and Case 4: infrequent in previous and incremental databases, so nothing is done. Like the FUP algorithm, the FUFP-tree maintenance algorithm improves the FUFP-tree structure after the addition of a new database [29]. An improvement was made to FUFP-tree structure so that when deleting transactions from the databases, the mining performance of incremental association rules was efficiently improved and the execution time was reduced. After updating tree, the algorithm continued to mine all FIs from the updated tree [29]. Pre-FUFP maintenance algorithm was proposed as a modified FUFP-tree algorithm. This algorithm was based on the “pre-large” concept that identified upper and lower support thresholds [33]. Accordingly, the previous databases need not be rescanned if the incremental transactions count is less than the safety number f of new transactions. The f number can be obtained according to the following equation:(1)f=Su−Sld1−Su,where Su is the upper support threshold, Sl is the lower support threshold, and d is the count of transactions in previous databases [33]. The problem with these algorithms is that they were based on a modified FP-tree structure, working on rescanning the whole database and updating and deleting items in the tree for mining incremental FIs from the updated tree [2]. Other algorithms used upper bound as an improved method for the traditional Phi correlation for mining item pairs from static databases based on the Apriori method such as the one proposed by Li et al. [41].Other algorithms used list structure on a dynamic database to mine erasable patterns and high-utility patterns such as IWEL [42], LINE [43], IMSEM [44], VME [45], PRE-HAUIMI [46], and HUI-list-INS [47] algorithms. Some other algorithms were based on the Apriori or tree method [48]. The point of convergence between these studies and this study is that they are incremental, working on frequent pattern mining, using some additional measures of interestingness. However, these studies were concerned with erasable and high-utility patterns using list structure with weighted or pre-large concepts. The main purpose of this study was to develop an FP-Max tree-based algorithm by utilizing subjective and objective measures for mining MFIs from a dynamic database. List structure can be more effective for mining, especially high-utility and erasable patterns, with regard to quantities or profit value conditions and other criteria, which are beyond our research.There was a growing need for more comprehensive methods that can operate on both maximal and incremental frequent itemsets, and several incremental MFI algorithms were proposed [17, 18, 49]. IM_WMFI algorithm [17] used a tree structure to mine WMFIs from incremental databases using weighted criteria of representative patterns and item importance. It scans the entire incremental database only once and extracts fewer number of MFIs. IMU2P-Miner algorithm [18] was introduced for mining MFIs from univariate uncertain dada. This algorithm used a tree structure local array to keep the updates without the need for tree reconstruction as it allows only one path to be updated or added.Interestingness is another feature that has received little attention in the field of incremental MFI mining. Briefly, two interestingness measures are considered: objective and subjective measures. The most considered objective measures that reflect the statistical strength of a pattern are support, confidence, all confidence, and left [38]. They are significantly used to discover only strong rules and, hence, filter out the number of uninteresting patterns. Since these measures failed to reflect user’s knowledge, subjective measures were called to ensure the reduction in the number of the discovered interesting rules only [36]. Novelty measure (NM), as a subjective measure, was presented in [34–36] according to the following equation:(2)NM=S1+S2−2∗K+∑i−1kδC1i,C2iS1+S2,where S1 and S2 are two conjunct sets with cardinalities |S1| and |S2|, respectively. K is the pairs of compatible conjuncts between S1 and S2. δC1i.C2i is the ith pair of compatible conjuncts. Interested readers may refer to [34–37].To the best of our knowledge, SelPMiner and CL-Max are the recent state-of-the art algorithms used for mining MFIs from static databases. IM_WMFI and IMU2P-Miner algorithms are the only recent algorithms that use the tree method for mining MFIs from incremental database. These algorithms used additional objective measures in mining process.In our proposed approach, an integrated algorithm was used. The basic FP-Growth algorithm was adopted to mine FIs from the tree as FP-tree without adjusting the tree structure, and FP-Max algorithm was used for mining all MFIs based on MFI-tree structure. Therefore, there is no need to rescan the previous databases and reconstruct the FP-tree. Added to the incremental nature of our method, NM is used to ensure the reduction in the number of MFIs and, consequently, the number of the discovered interesting rules. Table1 shows the characteristics of the major reviewed algorithms.Table 1
Characteristics of the major algorithms reviewed.
AlgorithmYearTree-basedIncrementalType of FIsUse subj. measureNo. ref.Apriori1994NoNoFIsNo[4]FP-Growth2000YesNoFIsNo[5]FP-Max∗2005YesNoMFIsNo[23]PADS2009YesNoMFIsNo[25]SelPMiner2019YesNoMFIsNo[19]CL-Max2021NoNoMFIsNo[26]FUP1996NoYesFIsNo[27]FUFP-tree2008YesYesFIsNo[28]FUFP-tree maintenance2009YesYesFIsNo[29]Pre-large2001NoYesFIsNo[32]Pre-FUFP2009YesYesFIsNo[33]IM_WMFI2016YesYesMFIsNo[17]IMU2P-Miner2018YesYesMFIsNo[18]Our proposed—YesYesMFIsYes—


## 3. The Proposed Approach

The proposed approach is designed to discover incremental IMFIs, named as IIMFIs, from dynamic database, as shown in Figure1. The proposed approach contains several components to which three functions are added: (1) keeping all items, frequent or infrequent, with their related information; (2) constructing a tree from the discovered IMFIs and current database; and (3) dynamic pruning of uninteresting MFIs. Symbols and notation used in this study are shown in Table 2.Figure 1
General architecture of the proposed framework.Table 2
Notation and meaning.
NotationMeaningTi + 1The new time (current time)Di + 1Current database at Ti + 1nThe total count of transactions in Di + 1DuDi + 1 and all previous databasesMin_SupMinimum support threshold, set by user where ≥0 and ≤1cur_SupThe count of transactions that contains item in Di + 1cur_MinsupThe value integer of Min_Sup in Di + 1incr_SupThe count of transactions that contains item in DUincr_MinsupThe sum of value integer minSup in DU1-Itemset1-Itemset containing name item (key) with cur_Sup, incr_Sup, and incr_MinsupMFIsnewA new maximal frequent itemsetsNMValue of novelty measureminNMThe least value within the NM valuesminNovltyMinimum novelty threshold, set by user where ≥0 and ≤1IMFIsA new interesting maximal frequent itemsetsPD_IMFIsPrevious discovered interesting MFIsPi + 1PD_IMFIs at Ti + 1 containing 1-Items and IMFI listS1Any IMFIs within IMFI listS2A new MFIs|S1|Length (size) ofS1|S2|Length (size) ofS2KCount of similar itemsets ofS1 and S2ConfThe value of confidence for any ruleminConfMinimum confidence threshold, set by user where ≥0 and ≤1The approach acts incrementally firstly by adding any new item to the item list and updating the support and threshold support of each item and, secondly, by adding IMFIs to the list of IMFIs in PD_IMFIs. PD_IMFI structure will be explained in Section3.1. The framework architecture contains five phases: the first phase scans all transactions in Di + 1 to add any new item as 1-Itemset with its cur_Sup or update the incr_Sup and incr_Minsup for each item in Pi + 1. The second phase builds up the tree from previous IMFIs and transactions in Di+1, utilizing FP-Growth algorithm similar to FP-tree structure. As for IMFIs (with its corresponding support), only the associated item with incr_Sup ≥ incr_Minsup or items with cur_Sup ≥ cur_Minsup are added. For each transaction in Di+1, only items in transaction are added to the tree where the item incr_Sup ≥ incr_Minsup, or cur_Sup ≥ cur_Minsup. In the third phase, FP-Max algorithm is used to extract MFIs from the tree using MFI-tree structure. In the fourth phase, dynamic pruning is performed using NM to compare each new MFI with all IMFIs of IMFI list in Pi+1. A new MFIs can be added to the list of IMFIs only if it is interesting; otherwise, it is discarded. In the fifth phase, association rules are generated from IMFIs. The output of this framework is incremental IMFIs and interesting rules. The detailed description of the proposed algorithm will be given in Section 3.5.


### 3.1. PD-IMFI Structure

The objective of PD_IMFIs is to speed up the construction of the tree by adding the previous IMFIs to tree nodes with a counter equal to the support value of IMFIs instead of rescanning previous transactions, thus reducing the size of the constructed tree, through keeping all the items (frequent or infrequent) with related information such as updated support, incremental threshold support, and the list of IMFI, for use next time, and so on.As shown in Figure2, PD_IMFI structure consists of two main parts: 1-Items list and IMFI list. 1-Items list part contains four fields: item_Name, cur_Sup, incr_Sup, and incr_Minsup. item_Name is a key and identifier for each item in PD_IMFIs. cur_Sup is the count of transactions, which contains the item in Di+1. incr_Sup is the sum support of each item in DU. incr_Minsup is the sum minimum threshold support of each item in DU. It is worth noting that cur_Minsup is a temporal condition in Di+1 used to update incr_Minsup. cur_Minsup is calculated according to the following equation [50]:(3)cur_Min sup=min_Sup∗n.Figure 2
PD_IMFI structure.As an example, let the count of transactions in Di+1 = 10, and Min_Sup = 0.5, so cur_Minsup = 0.5 ∗ 10 = 5.Each item in 1-Items list part has an IMFI list, which may be null or have one/more IMFIs. IMFI list part contains two fields: IMFI, referring to an array of associated itemsets as IMFIs, and support, indicating the frequency value of IMFIs in DU.


### 3.2. Incremental MFI Mining

The incremental nature of the proposed approach self-adjusts the minimum support (incr_Minsup) due to the change in the support value (incr_Sup) of each item in 1-Items list as a result of the Di + 1 scan in the first phase, algorithms 1-2. The construction of the tree is based on previously discovered IMFIs in Pi (IMFI list) and transactions in Di + 1, tree starting is null, and fetching is only of IMIFs in Pi that associated item in Pi + 1, if cur_Sup ≥ cur_Minsup, or incr_Sup ≥ incr_Minsup. In the second scan of Di + 1, for each transaction, any item is removed, if item in 1-Items list of Pi + 1 has the value of cur_Sup < cur_Minsup and incr_Sup < incr_Minsup, and items are re-sorted in descending order based on the value of incr_Sup of an item in 1-Items list of Pi + 1. Support in the header table and the counter node can be updated only if it is less than incr_Sup of each item in the 1-Items list part of Pi + 1, as in the second phase, Algorithm 3. As a result, the counter values of nodes are updated. In the third phase, incremental MFIs with updated support are extracted from this tree. Consequently, the Conf value may change as it is related to support.


### 3.3. Incremental Dynamic Pruning of MFIs

One of the main advantages of our approach is its ability to handle dynamic pruning based on NM. The goal is to reduce the count of the MFIs. The framework computes NM according to equation (2). In fact, we do not need to calculate δC1i,C2i in case of association rules, because it is always equal to zero, and it is used in the case of classification. So, equation (2) can be modified as follows:(4)NM=S1+S2−2∗KS1+S2.NM value of new MFIs determines whether it is novel or not. The NM value of these new MFIs is calculated against all the IMFIs in the IMFI list part of PD_IMFIs as follows:(5)NMMFIsnewIMFIslist inPi+1=S1+S2−2∗KS1+S2.As a result of using equation (5) that represents the relationship between S1 and S2, four cases are observed. Case 1: S1 is equal to S2, S1 = S2 and K = |S1| = |S2|. Case 2: S2 is a subset of S1, S2 ∈ S1, K > 0, and K = |S2|. Case 3: S1 is a subset of S2, S1 ∈ S2, K > 0, and K = |S1|. Case 4: S1 is not equal to S2, S1 ≠ S2, K ≥ 0, K < |S1|, and K < |S2|. Cases 1 and 2 are not used in our approach since FP-Max algorithm cancels out any recurrence of FIs in the MFI-tree. Case 3 is not applicable to our approach since the tree-building process removes any IMFIs from IMFI list part when any cur_Sup ≥ cur_Minsup, or incr_Sup ≥ incr_Minsup of items associated with IMFIs in Pi + 1. Only Case 4 is utilized in our approach to calculate the value of NM depending on the value of K, as in the fourth phase, Algorithm 4. After the computation of the NM of each IMFI in Pi + 1, the dynamic pruning is performed by eliminating those new MFIs with NM less than minNovlty as shown in Algorithm 1. For example, let minNovlty = 0.5, a new MFIs = {a,s}, and the three IMFIs in IMFI list, i.e., {{r,m,s}, {r,b,m}, {m,t}}. The NM between a new MFIs is S2 = {a, s} and |S2| = 2 and each IMFI can be calculated and illustrated as in Table 3. Note here that minNM = 0.6. So, minNM > minNovlty, and then, the new MFIs {a, s} are interesting; subsequently, it is added to IMFI list. Suppose later comes a new MFIs = {u,s,m}. The NM between the new MFIs is S2{u,s,m} and |S2| = 3 and each IMFI in IMFI list can be calculated as shown in Table 4. Note here that minNM = 0.2. So, minNM < minNovlty, and then, the new MFIs {u,s,m} are uninteresting; subsequently, it is pruned.Table 3
NM calculation between the new MFIs {a,s} and all IMFIs in IMFI list.
S1|S1|S2|S2|KNMminNM≥minNovlty{r,m,s}3{a,s}21((3 + 2) − (2 × 1))/(3 + 2) = 3/5 = 0.60.6Yes{r,b,m}30((3 + 2) − (2 × 0))/(3 + 2) = 5/5 = 1{m,t}20((2 + 2) − (2 × 0))/(2 + 2) = 4/4 = 1Table 4
NM calculation between the new MFIs {u,s,m} and all IMFIs in IMFI list.
S1|S1|S2|S2|KNMminNM≥ minNovlty{r,m,s}3{u,s,m}32((3 + 3) − (2 × 2))/(3 + 3) = 2/6 = 0.330.2No{r,b,m}31((3 + 3) − (2 × 1))/(3 + 3) = 4/6 = 0.2{m,t}21((2 + 3) − (2 × 1))/(2 + 3) = 3/5 = 0.6{a,s}21((2 + 3) − (2 × 1))/(2 + 3) = 4/4 = 0.6


### 3.4. Generation of Interesting Rules

NM is used in this approach as a determining measure during the pruning process to discover MFIs that are only interesting. As such, NM becomes a crucial constraint within the algorithm to reduce the number of MFIs and subsequently the count of discovered rules. Therefore, only those rules interesting to the user can be generated. Interestingly, the incremental nature of the proposed approach makes it significantly flexible to cope with time-changing data and user-changing beliefs. This enforces its computing functionality with two or more databases arriving at different courses of time with different volumes and from different locations. Hence, incremental updating of the discovered knowledge is a striking feature of the proposed algorithm. However, a keyword for generating the association rules is to identify the measure of Conf. This can be calculated according to the following equation:(6)conf=supportA⟶BsuportA,where support (A ⟶ B) is the number of transactions containing itemsets A and B together, and support (A) is the count of transactions composing itemset A [50].


### 3.5. Proposed Framework Algorithms

As stated earlier, five phases have been proposed by our approach framework representing algorithms 1–4. Algorithm 1 (IIMFI algorithm) includes these phases, which call other algorithms.Phase 1.
First scan of Di + 1. Lines 1–4 in Algorithm 1 explain Phase 1. This phase consists of two tasks.
First Task: a new PD_IMFIs are created as Pi + 1. This is the integration between the previous PD_IMFI Pi and Di + 1. Algorithm 2 (created PD_IMFI algorithm) describes these tasks.
Second Task: the integer value of cur_Minsup is calculated for Di + 1 as to equation (3), and incr_Minsup is updated by increasing its value with cur_Minsup for each item in Pi + 1.Phase 2.
Create a new tree as FP-tree structure. Lines 5–6 in Algorithm 1 explain Phase 2, which calls Algorithm 3 (created tree algorithm), describing Phase 2. This phase consists of three tasks.
First Task: the tree is built by adding the previously discovered IMFIs (along with their corresponding support) of Pi to the tree.
Second Task: the construction of the tree is completed by reading the records from the Di + 1.
Third Task: the support value for each item in the header table and the counter for the nodes in the tree are updated so that it becomes equal to incr_Sup for that item in Pi + 1.
Algorithm 1: Main IIMFI algorithm.
Input:Di + 1Pi // wheni = 0 T0, the P0 is null.useNM // its optional, either true or false. If true call Algorithm 4 to calculate minNM.minNovlty, minSup, minConf are values ≥ 0 and ≤ 1, entered by user.Output:Pi + 1 // a new PD_IMFIs output at now time Ti + 1Phase 1: Create PD_IMFIs as Pi + 1 and incremental support and minimum threshold(1) Pi + 1 = Call Created PD_IMFIs Algorithm (Di + 1, Pi)(2) cur_Minsup = Min_Sup ∗n(3) For each item in Pi + 1 asP(3.1) P. incr_Minsup + = cur_Minsup(4) End forPhase 2: Create of tree, it includes previous IMFIs and transactions in Di + 1(5) tree = null // as structure FP-tree(6) tree = Call Created Tree Algorithm (Pi + 1, Di + 1, cur_Minsup)Phase 3: Find MFIs from tree based on FP-Max algorithm(7) MFI-tree = null(8) For each item from bottom to up in Pi + 1 as P // where from bottom to up as header table with tree(8.1) If P. cur_Sup ≥ cur_Minsup or P. incr_Sup ≥ P. incr_Minsup Then(8.1.1) MFIsnew = null(8.1.2) MFIsnew = call FP-Max Algorithm (tree, MFI-tree)(8.1.3) If useNM = = true Then // Go to Phase 4:Phase 4: Incremental Dynamic Pruning of MFIs(i)MinNMMFIsnewPi+1  = call Interesting Measure Algorithm (Pi + 1, MFIsnew) // to determine the minimum value of the deviation between MFIsnew and all IMFIs in Pi + 1.(ii) IfMinNMMFIsnewPi+1 minNovlty Then(a) Add MFIsnew to P.list_IMFIs in Pi + 1(iii) End if(8.1.4) End ifPhase 5: Generation Association Rules(8.1.5) Call Association Rule Generation Algorithm (MFIsnew, minConf)(8.2) End if(9) End for(10) Return Pi + 1
Algorithm 2: Created PD_IMFI algorithm.
Input:Di + 1, PiOutput:Pi + 1(1) Pi + 1 = Pi(2) For each transactionT in Di + 1 // first scan current database(2.1) For each item I inT(2.1.1) If I is equal item_Name for each item in Pi + 1 as P Then(i) increase value of P. cur_Sup, and P. incr_Sup by 1(2.1.2) Else(i) Create a new item as Pnew with default value fields item_Name = I, cur_Sup = 1, incr_Sup = 1, incr_Minsup = 0, and list_IMFIs = null(ii) add a Pnew to 1-Items list in Pi + 1(2.1.3) End if(2.2) End for(3) End for(4) Re-sort Pi + 1 in descending order by the value of incr_Sup filed.(5) Return Pi + 1
Algorithm 3: Created tree algorithm.
Input:Pi + 1, Di + 1, cur_MinsupOutput:tree // tree is update includes all items in IMFIs and Di + 1(1) For each item in Pi + 1 as P(1.1) If P.list_IMFIs! = null and (P. cur_Sup ≥ cur_Minsup or P.incr_Sup ≥ P.incr_Minsup) Then(a) For each IMFIs in P. list_IMFIs(i) Add all itemsets in IMFIs to new array as arrayTrns(ii) Re-sort items of arrayTrns in descending order as items in Pi + 1(iii) tree = Call FP-Growth algorithm to build tree (arrayTrns, IMFIs.support).(b) End for(c) P.list_IMFIs = null // reset list_IMFIs as null or remove all IMFIs from P.list_IMFIs(1.2) End if(2) End for(3) For each transactionT in Di + 1 // second scan new database Di + 1.(3.1) add all items inT to new array as arrayTrns //where item is equal to item_Name; and cur_Sup ≥ cur_Minsup or incr_Sup ≥ incr_Minsup in Pi + 1.(3.2) Re-sort items of arrayTrns in descending order as Pi + 1.(3.3) tree = Call FP-Growth algorithm to build tree (arrayTrns).(4) End for(5) Update support in header table, and counter nodes on main path to equal incr_Sup for each item in Pi + 1 where the item in header table and node equal item_Name and the same level on main path and Pi.(6) Return treePhase 3.
Extract MFIs from the tree using FP-Max algorithm, conducting bottom-up looping of each item in Pi + 1 where cur_Sup ≥ cur_Minsup, or incr_Sup ≥ incr_Minsup. Lines 7-8.1. 2 in Algorithm 1 explain Phase 3. In line 8.1.3, if useNM is true, then Phase 4 (lines 8.1.3.1-line 8.1.3.2) and Phase 5 are proceeded; else, line 8.1.4 Phase 5 is proceeded (lines 8.1.4.1-8.1.4.2).Phase 4.
Perform dynamic pruning of MFIs using NM constraint. In this phase, one task is to calculate the NM between MFIs and all IMFIs in Pi + 1 and select the minNM value from NM values. Algorithm 4 (interesting measure algorithm) explains the first task. If the minNM ≥ minNovlty, then the MFIs are interesting (IMFIs), so Phase 5 is proceeded, else the MFIs are discarded; thus Phase 3 is processed until the first item in Pi + 1.Phase 5.
This phase runs two tasks.
First Task: the list of IMFIs in Pi + 1 is updated by adding new MFIs to the list, as represented in line 8.1.4, Algorithm 1.
Second Task: rules from MFIs are generated, which have Conf ≥ minConf, by calling association rule generation algorithm, Algorithm 1, line 8.1.5.
Algorithm 4: Interesting measure algorithm.
Input:Pi + 1, MFIsnewOutput:minNM(1) minNM = 1(2) For each Item in Pi + 1 as P(2.1) For each IMFIs in P.list_IMFIs // where P.list_IMFIs not null(2.1.1) NMtemp =S1+S2–2∗k/S1+S2 //where S1 is size of IMFIs, S2 is size of MFIsnew, k is count items of the similar between IMFI and MFIsnew.(2.1.2) If NMtemp < minNM then(a) minNM = NMtemp(2.1.3) End if(2.2) End for(3) End for(4) Return minNM


### 3.6. Time Complexity

Regarding the time complexity of the developed algorithm (IIMFIs), the complexity varied vis-à-vis the algorithmic conditioning of the mining process at three divided times and the total time spent on the incremental database. The first algorithmic step was to call Algorithm 2 to create PD_IMFIs, and the time complexity is O(n × i), where n is the total number of transactions in the databases and i is the number of items in n. The time complexity here is almost similar to all the other algorithms when performed on static databases. However, in the case of incremental databases, the time is less complex in Algorithm 2 of our proposed method compared with other algorithms due to the algorithmic condition that if any item has been already discovered, it needs just the update of P data and not the creation of a new item. As Algorithm 3 was called to create the updated tree, two recursive cycles were involved. The first cycle was to build the tree from the previously discovered MFIs associated only with the items having incremental support cur_Sup value ≥ cur_Minsup value, or incr_Sup ≥ incr_Minsup, and the time complexity here is o(n). The second recursive cycle was used to conduct the second scan of the databases to complete the construction of the tree, and the time complexity for this step is the same as for Algorithm 2, O(n × i). It is to be noted that the tree construction in IIMFIs is much faster and more efficient because the assumed pathways of the tree have already been constructed in the first recursive cycle. The second cycle involved only completion of the tree construction through just updating the counter for each node. The worst time complexity is O(n3) where Algorithm 4 was called within the recursive cycle of Algorithm 1 in case useNM = true, but if useNM = false, Algorithm 4 would not be called and, the time complexity, in this case, is O(n2).


### 3.7. A Detailed Example

Assume D1, D2, and D3 are three databases coming at three different times T1, T2, and T3, as shown in Tables5–7, respectively. The last column (ordered items) in these tables shows the representation of items in descending order according to incr_Sup value for each item in 1-Items list as used in the construction of the tree. Let Min_Sup = 0.5, minNovlty = 0.5, and minConf = 0.7.Table 5
Database D1 at T1.
TidItemsetsOrdered itemsets1A C DC A2B C EB E C3A B C EB E C A4B EB E5A C DC A6B C EB E C7A B C EB E C A8B EB E9A B C EB E C A10B EB ETable 6
Database D2 at T2.
TidItemsetsOrdered itemsets1D C BB C D2B C E GB C E G3D B GB D G4A C D GC D G5B C E GB C E G6A B C E DB C E DTable 7
Database D3 at T3.
TidItemsetOrdered itemsets1E B CB C E2C E B RB C E3G B D A MB M4B A CB C5M R BB M6C B E MB C E MAt T1 Phase 1, P1 is created, all items in D1 to1-Items list with cur_Sup and incr_Sup = support of item in D1 are added, and incr_Minsup is set; here, = cur_Minsup, and the value of cur_Minsup = 0.5 ∗10 = 5. Figure 3(a) shows P1 after Phase 1. Phase 2: the tree is created as shown in Figure 3(b). At T1, the tree is built only from transactions in D1. Phase 3: bottom-up looping of each item in 1-Items list from P1 is started; if cur_Sup ≥ cur_Minsup or incr_Sup ≥ incr_Minsup, it is started from item {A} and then FP-Max is called for mining MFIs, and its output is MFIsnew = {A, C:5}. Phase 4: the value of MinNMA,CIMFIslist is calculated, and its value = 1, because IMFI list for each item in 1-Items list from P1 is null. Then, the value of MinNMA,CIMFIslist ≥ minNovlty (1 ≥ 0.5) is compared; i.e., MFIs {A, C:5} are interesting, so it is added to IMFI list of the item {A}. Phase 5: rules from it are generated where each rule has Conf ≥0.7. Then, phase 3 is proceeded for taking item{C}. The output of this phase is MFIs = {B, C, E:5}. Phase 4: the value of NMBCEAC=2+3−2∗1/2+3=0.6 is calculated, which is the minNM. Then, the value of MinNMBCEIMFIslist ≥ minNovlty (.6 ≥ .5) is compared; thus, MFIs {B, C, E:5} are interesting, so it is added to IMFI list with item {C}. Phase 5: rules from it are generated where each rule has Conf ≥0.7. Then, Phase 3 is proceeded, and item{E} is taken; this phase is not the output MFIs for item{E}, so Phase 4 is not processed; also, item{B} has no MFIs. Figure 3(c) shows P1 after phases 3-4 at T1. Table 8 shows generated rules that have Conf ≥0.7 after phase 5 at T1. (Note) At T1, 9 rules are interesting (1-9) (green color).Figure 3
Example at T1. (a) P1 after phase 1, (b) tree as FP-tree after phase 2, and (c) P1 after phases 3-4.
(a)(b)(c)Table 8
Rules that have Conf ≥0.7 after phase 5 at T1.
No.RuleConfNo.RuleConfNo.RuleConf1A ⟶ C14B ⟶ E17CE ⟶ B12C ⟶ A0.715E ⟶ B18BC ⟶ E13C ⟶ B0.716C ⟶ E0.719C ⟶ BE0.71At T2, Phase 1, P2 = P1 is created, and then, cur_Sup = support of item in D2, incr_Sup+ = cur_Sup, and incr_Minsup + = cur_Minsup are set. At T2, the value of cur_Minsup = 0.5 ∗ 6 = 3. Figure4(a) shows P2 after phase 1. Phase 2: the tree is created. Figure 4(b) shows P2, and Figure 4(c) shows the tree after phase 2. The outcome of phases 3-4 is P2 as Figure 4(d) shows. Phase 5: rules that have Conf ≥0.7 are generated as shown in Table 9. (Note) At T2, only 2 rules are interesting (rule 15 and rule 16) (green color), 14 rules are not interesting, 12 rules undergo change in value Conf (3-14) (red color), and 2 rules experience no change in value Conf (1-2).Figure 4
Example at T2. (a) P2 after phase 1, (b) P2 after phase 2, (c) tree as FP-tree after phase 2, and (d) P2 after phases 3-4.
(a)(b)(c)(d)Table 9
Rules that have Conf ≥0.7 after phase 5 at T2.
No.RuleConfNo.RuleConfNo.RuleConf1A ⟶ C17C ⟶ E0.9113CE ⟶ B12C ⟶ A0.718E ⟶ C114B ⟶ CE0.843B ⟶ C0.859BC ⟶ E115G ⟶ B14C ⟶ B0.9110E ⟶ BC116G ⟶ C15B ⟶ E0.8511BE ⟶ C16E ⟶ B112C ⟶ BE0.91At T3, Phase 1: P3 = P2 is created, and then, cur_Sup = support of item in D3, incr_Sup+ = cur_Sup, and incr_Minsup + = cur_Minsup are set. At T3, the value of cur_Minsup = 0.5 ∗ 6 = 3. Figure5(a) shows P3 after Phase 1. Phase 2: the tree is created. Figure 5(b) shows P3, and Figure 5(c) shows the tree after Phase 2. Figure 4(d) shows P3 after phases 3-4. Phase 5: rules that have Conf ≥0.7 are generated as shown in Table 10. (Note) At T3, only 1 rule is interesting (rule 17) (green color), 16 rules are not interesting, 12 rules undergo change in value Conf (3-14) (red color), and 4 rules undergo no change in value Conf (1,2,15,16). The results of the previous example at three times are summarized in Table 11.Figure 5
Example at T3. (a) P3 after Phase 1, (b) P3 after phase 2, (c) tree as FP-tree after phase 2, and (d) P3 after phases 3-4.
(a)(b)(c)and (d)Table 10
Generated rules that have Conf ≥0.7 after phase 5 at T3.
No.RuleConfNo.RuleConfNo.RuleConf1A ⟶ C17C ⟶ E0.8813CE ⟶ B12C ⟶ A0.718E ⟶ C114B ⟶ CE0.743B ⟶ C0.749BC ⟶ E0.8815G ⟶ B14C ⟶ B0.8810E ⟶ BC116G ⟶ C15B ⟶ E0.7411BE ⟶ C117M ⟶ B16E ⟶ B112C ⟶ BE0.88Table 11
Results of the example at times T1, T2, and T3.
TimeMFIsUninteresting rulesIMFIsInteresting rulesT12929T241622T351711


## 3.1. PD-IMFI Structure

The objective of PD_IMFIs is to speed up the construction of the tree by adding the previous IMFIs to tree nodes with a counter equal to the support value of IMFIs instead of rescanning previous transactions, thus reducing the size of the constructed tree, through keeping all the items (frequent or infrequent) with related information such as updated support, incremental threshold support, and the list of IMFI, for use next time, and so on.As shown in Figure2, PD_IMFI structure consists of two main parts: 1-Items list and IMFI list. 1-Items list part contains four fields: item_Name, cur_Sup, incr_Sup, and incr_Minsup. item_Name is a key and identifier for each item in PD_IMFIs. cur_Sup is the count of transactions, which contains the item in Di+1. incr_Sup is the sum support of each item in DU. incr_Minsup is the sum minimum threshold support of each item in DU. It is worth noting that cur_Minsup is a temporal condition in Di+1 used to update incr_Minsup. cur_Minsup is calculated according to the following equation [50]:(3)cur_Min sup=min_Sup∗n.Figure 2
PD_IMFI structure.As an example, let the count of transactions in Di+1 = 10, and Min_Sup = 0.5, so cur_Minsup = 0.5 ∗ 10 = 5.Each item in 1-Items list part has an IMFI list, which may be null or have one/more IMFIs. IMFI list part contains two fields: IMFI, referring to an array of associated itemsets as IMFIs, and support, indicating the frequency value of IMFIs in DU.


## 3.2. Incremental MFI Mining

The incremental nature of the proposed approach self-adjusts the minimum support (incr_Minsup) due to the change in the support value (incr_Sup) of each item in 1-Items list as a result of the Di + 1 scan in the first phase, algorithms 1-2. The construction of the tree is based on previously discovered IMFIs in Pi (IMFI list) and transactions in Di + 1, tree starting is null, and fetching is only of IMIFs in Pi that associated item in Pi + 1, if cur_Sup ≥ cur_Minsup, or incr_Sup ≥ incr_Minsup. In the second scan of Di + 1, for each transaction, any item is removed, if item in 1-Items list of Pi + 1 has the value of cur_Sup < cur_Minsup and incr_Sup < incr_Minsup, and items are re-sorted in descending order based on the value of incr_Sup of an item in 1-Items list of Pi + 1. Support in the header table and the counter node can be updated only if it is less than incr_Sup of each item in the 1-Items list part of Pi + 1, as in the second phase, Algorithm 3. As a result, the counter values of nodes are updated. In the third phase, incremental MFIs with updated support are extracted from this tree. Consequently, the Conf value may change as it is related to support.


## 3.3. Incremental Dynamic Pruning of MFIs

One of the main advantages of our approach is its ability to handle dynamic pruning based on NM. The goal is to reduce the count of the MFIs. The framework computes NM according to equation (2). In fact, we do not need to calculate δC1i,C2i in case of association rules, because it is always equal to zero, and it is used in the case of classification. So, equation (2) can be modified as follows:(4)NM=S1+S2−2∗KS1+S2.NM value of new MFIs determines whether it is novel or not. The NM value of these new MFIs is calculated against all the IMFIs in the IMFI list part of PD_IMFIs as follows:(5)NMMFIsnewIMFIslist inPi+1=S1+S2−2∗KS1+S2.As a result of using equation (5) that represents the relationship between S1 and S2, four cases are observed. Case 1: S1 is equal to S2, S1 = S2 and K = |S1| = |S2|. Case 2: S2 is a subset of S1, S2 ∈ S1, K > 0, and K = |S2|. Case 3: S1 is a subset of S2, S1 ∈ S2, K > 0, and K = |S1|. Case 4: S1 is not equal to S2, S1 ≠ S2, K ≥ 0, K < |S1|, and K < |S2|. Cases 1 and 2 are not used in our approach since FP-Max algorithm cancels out any recurrence of FIs in the MFI-tree. Case 3 is not applicable to our approach since the tree-building process removes any IMFIs from IMFI list part when any cur_Sup ≥ cur_Minsup, or incr_Sup ≥ incr_Minsup of items associated with IMFIs in Pi + 1. Only Case 4 is utilized in our approach to calculate the value of NM depending on the value of K, as in the fourth phase, Algorithm 4. After the computation of the NM of each IMFI in Pi + 1, the dynamic pruning is performed by eliminating those new MFIs with NM less than minNovlty as shown in Algorithm 1. For example, let minNovlty = 0.5, a new MFIs = {a,s}, and the three IMFIs in IMFI list, i.e., {{r,m,s}, {r,b,m}, {m,t}}. The NM between a new MFIs is S2 = {a, s} and |S2| = 2 and each IMFI can be calculated and illustrated as in Table 3. Note here that minNM = 0.6. So, minNM > minNovlty, and then, the new MFIs {a, s} are interesting; subsequently, it is added to IMFI list. Suppose later comes a new MFIs = {u,s,m}. The NM between the new MFIs is S2{u,s,m} and |S2| = 3 and each IMFI in IMFI list can be calculated as shown in Table 4. Note here that minNM = 0.2. So, minNM < minNovlty, and then, the new MFIs {u,s,m} are uninteresting; subsequently, it is pruned.Table 3
NM calculation between the new MFIs {a,s} and all IMFIs in IMFI list.
S1|S1|S2|S2|KNMminNM≥minNovlty{r,m,s}3{a,s}21((3 + 2) − (2 × 1))/(3 + 2) = 3/5 = 0.60.6Yes{r,b,m}30((3 + 2) − (2 × 0))/(3 + 2) = 5/5 = 1{m,t}20((2 + 2) − (2 × 0))/(2 + 2) = 4/4 = 1Table 4
NM calculation between the new MFIs {u,s,m} and all IMFIs in IMFI list.
S1|S1|S2|S2|KNMminNM≥ minNovlty{r,m,s}3{u,s,m}32((3 + 3) − (2 × 2))/(3 + 3) = 2/6 = 0.330.2No{r,b,m}31((3 + 3) − (2 × 1))/(3 + 3) = 4/6 = 0.2{m,t}21((2 + 3) − (2 × 1))/(2 + 3) = 3/5 = 0.6{a,s}21((2 + 3) − (2 × 1))/(2 + 3) = 4/4 = 0.6


## 3.4. Generation of Interesting Rules

NM is used in this approach as a determining measure during the pruning process to discover MFIs that are only interesting. As such, NM becomes a crucial constraint within the algorithm to reduce the number of MFIs and subsequently the count of discovered rules. Therefore, only those rules interesting to the user can be generated. Interestingly, the incremental nature of the proposed approach makes it significantly flexible to cope with time-changing data and user-changing beliefs. This enforces its computing functionality with two or more databases arriving at different courses of time with different volumes and from different locations. Hence, incremental updating of the discovered knowledge is a striking feature of the proposed algorithm. However, a keyword for generating the association rules is to identify the measure of Conf. This can be calculated according to the following equation:(6)conf=supportA⟶BsuportA,where support (A ⟶ B) is the number of transactions containing itemsets A and B together, and support (A) is the count of transactions composing itemset A [50].


## 3.5. Proposed Framework Algorithms

As stated earlier, five phases have been proposed by our approach framework representing algorithms 1–4. Algorithm 1 (IIMFI algorithm) includes these phases, which call other algorithms.Phase 1.
First scan of Di + 1. Lines 1–4 in Algorithm 1 explain Phase 1. This phase consists of two tasks.
First Task: a new PD_IMFIs are created as Pi + 1. This is the integration between the previous PD_IMFI Pi and Di + 1. Algorithm 2 (created PD_IMFI algorithm) describes these tasks.
Second Task: the integer value of cur_Minsup is calculated for Di + 1 as to equation (3), and incr_Minsup is updated by increasing its value with cur_Minsup for each item in Pi + 1.Phase 2.
Create a new tree as FP-tree structure. Lines 5–6 in Algorithm 1 explain Phase 2, which calls Algorithm 3 (created tree algorithm), describing Phase 2. This phase consists of three tasks.
First Task: the tree is built by adding the previously discovered IMFIs (along with their corresponding support) of Pi to the tree.
Second Task: the construction of the tree is completed by reading the records from the Di + 1.
Third Task: the support value for each item in the header table and the counter for the nodes in the tree are updated so that it becomes equal to incr_Sup for that item in Pi + 1.
Algorithm 1: Main IIMFI algorithm.
Input:Di + 1Pi // wheni = 0 T0, the P0 is null.useNM // its optional, either true or false. If true call Algorithm 4 to calculate minNM.minNovlty, minSup, minConf are values ≥ 0 and ≤ 1, entered by user.Output:Pi + 1 // a new PD_IMFIs output at now time Ti + 1Phase 1: Create PD_IMFIs as Pi + 1 and incremental support and minimum threshold(1) Pi + 1 = Call Created PD_IMFIs Algorithm (Di + 1, Pi)(2) cur_Minsup = Min_Sup ∗n(3) For each item in Pi + 1 asP(3.1) P. incr_Minsup + = cur_Minsup(4) End forPhase 2: Create of tree, it includes previous IMFIs and transactions in Di + 1(5) tree = null // as structure FP-tree(6) tree = Call Created Tree Algorithm (Pi + 1, Di + 1, cur_Minsup)Phase 3: Find MFIs from tree based on FP-Max algorithm(7) MFI-tree = null(8) For each item from bottom to up in Pi + 1 as P // where from bottom to up as header table with tree(8.1) If P. cur_Sup ≥ cur_Minsup or P. incr_Sup ≥ P. incr_Minsup Then(8.1.1) MFIsnew = null(8.1.2) MFIsnew = call FP-Max Algorithm (tree, MFI-tree)(8.1.3) If useNM = = true Then // Go to Phase 4:Phase 4: Incremental Dynamic Pruning of MFIs(i)MinNMMFIsnewPi+1  = call Interesting Measure Algorithm (Pi + 1, MFIsnew) // to determine the minimum value of the deviation between MFIsnew and all IMFIs in Pi + 1.(ii) IfMinNMMFIsnewPi+1 minNovlty Then(a) Add MFIsnew to P.list_IMFIs in Pi + 1(iii) End if(8.1.4) End ifPhase 5: Generation Association Rules(8.1.5) Call Association Rule Generation Algorithm (MFIsnew, minConf)(8.2) End if(9) End for(10) Return Pi + 1
Algorithm 2: Created PD_IMFI algorithm.
Input:Di + 1, PiOutput:Pi + 1(1) Pi + 1 = Pi(2) For each transactionT in Di + 1 // first scan current database(2.1) For each item I inT(2.1.1) If I is equal item_Name for each item in Pi + 1 as P Then(i) increase value of P. cur_Sup, and P. incr_Sup by 1(2.1.2) Else(i) Create a new item as Pnew with default value fields item_Name = I, cur_Sup = 1, incr_Sup = 1, incr_Minsup = 0, and list_IMFIs = null(ii) add a Pnew to 1-Items list in Pi + 1(2.1.3) End if(2.2) End for(3) End for(4) Re-sort Pi + 1 in descending order by the value of incr_Sup filed.(5) Return Pi + 1
Algorithm 3: Created tree algorithm.
Input:Pi + 1, Di + 1, cur_MinsupOutput:tree // tree is update includes all items in IMFIs and Di + 1(1) For each item in Pi + 1 as P(1.1) If P.list_IMFIs! = null and (P. cur_Sup ≥ cur_Minsup or P.incr_Sup ≥ P.incr_Minsup) Then(a) For each IMFIs in P. list_IMFIs(i) Add all itemsets in IMFIs to new array as arrayTrns(ii) Re-sort items of arrayTrns in descending order as items in Pi + 1(iii) tree = Call FP-Growth algorithm to build tree (arrayTrns, IMFIs.support).(b) End for(c) P.list_IMFIs = null // reset list_IMFIs as null or remove all IMFIs from P.list_IMFIs(1.2) End if(2) End for(3) For each transactionT in Di + 1 // second scan new database Di + 1.(3.1) add all items inT to new array as arrayTrns //where item is equal to item_Name; and cur_Sup ≥ cur_Minsup or incr_Sup ≥ incr_Minsup in Pi + 1.(3.2) Re-sort items of arrayTrns in descending order as Pi + 1.(3.3) tree = Call FP-Growth algorithm to build tree (arrayTrns).(4) End for(5) Update support in header table, and counter nodes on main path to equal incr_Sup for each item in Pi + 1 where the item in header table and node equal item_Name and the same level on main path and Pi.(6) Return treePhase 3.
Extract MFIs from the tree using FP-Max algorithm, conducting bottom-up looping of each item in Pi + 1 where cur_Sup ≥ cur_Minsup, or incr_Sup ≥ incr_Minsup. Lines 7-8.1. 2 in Algorithm 1 explain Phase 3. In line 8.1.3, if useNM is true, then Phase 4 (lines 8.1.3.1-line 8.1.3.2) and Phase 5 are proceeded; else, line 8.1.4 Phase 5 is proceeded (lines 8.1.4.1-8.1.4.2).Phase 4.
Perform dynamic pruning of MFIs using NM constraint. In this phase, one task is to calculate the NM between MFIs and all IMFIs in Pi + 1 and select the minNM value from NM values. Algorithm 4 (interesting measure algorithm) explains the first task. If the minNM ≥ minNovlty, then the MFIs are interesting (IMFIs), so Phase 5 is proceeded, else the MFIs are discarded; thus Phase 3 is processed until the first item in Pi + 1.Phase 5.
This phase runs two tasks.
First Task: the list of IMFIs in Pi + 1 is updated by adding new MFIs to the list, as represented in line 8.1.4, Algorithm 1.
Second Task: rules from MFIs are generated, which have Conf ≥ minConf, by calling association rule generation algorithm, Algorithm 1, line 8.1.5.
Algorithm 4: Interesting measure algorithm.
Input:Pi + 1, MFIsnewOutput:minNM(1) minNM = 1(2) For each Item in Pi + 1 as P(2.1) For each IMFIs in P.list_IMFIs // where P.list_IMFIs not null(2.1.1) NMtemp =S1+S2–2∗k/S1+S2 //where S1 is size of IMFIs, S2 is size of MFIsnew, k is count items of the similar between IMFI and MFIsnew.(2.1.2) If NMtemp < minNM then(a) minNM = NMtemp(2.1.3) End if(2.2) End for(3) End for(4) Return minNM


## 3.6. Time Complexity

Regarding the time complexity of the developed algorithm (IIMFIs), the complexity varied vis-à-vis the algorithmic conditioning of the mining process at three divided times and the total time spent on the incremental database. The first algorithmic step was to call Algorithm 2 to create PD_IMFIs, and the time complexity is O(n × i), where n is the total number of transactions in the databases and i is the number of items in n. The time complexity here is almost similar to all the other algorithms when performed on static databases. However, in the case of incremental databases, the time is less complex in Algorithm 2 of our proposed method compared with other algorithms due to the algorithmic condition that if any item has been already discovered, it needs just the update of P data and not the creation of a new item. As Algorithm 3 was called to create the updated tree, two recursive cycles were involved. The first cycle was to build the tree from the previously discovered MFIs associated only with the items having incremental support cur_Sup value ≥ cur_Minsup value, or incr_Sup ≥ incr_Minsup, and the time complexity here is o(n). The second recursive cycle was used to conduct the second scan of the databases to complete the construction of the tree, and the time complexity for this step is the same as for Algorithm 2, O(n × i). It is to be noted that the tree construction in IIMFIs is much faster and more efficient because the assumed pathways of the tree have already been constructed in the first recursive cycle. The second cycle involved only completion of the tree construction through just updating the counter for each node. The worst time complexity is O(n3) where Algorithm 4 was called within the recursive cycle of Algorithm 1 in case useNM = true, but if useNM = false, Algorithm 4 would not be called and, the time complexity, in this case, is O(n2).


## 3.7. A Detailed Example

Assume D1, D2, and D3 are three databases coming at three different times T1, T2, and T3, as shown in Tables5–7, respectively. The last column (ordered items) in these tables shows the representation of items in descending order according to incr_Sup value for each item in 1-Items list as used in the construction of the tree. Let Min_Sup = 0.5, minNovlty = 0.5, and minConf = 0.7.Table 5
Database D1 at T1.
TidItemsetsOrdered itemsets1A C DC A2B C EB E C3A B C EB E C A4B EB E5A C DC A6B C EB E C7A B C EB E C A8B EB E9A B C EB E C A10B EB ETable 6
Database D2 at T2.
TidItemsetsOrdered itemsets1D C BB C D2B C E GB C E G3D B GB D G4A C D GC D G5B C E GB C E G6A B C E DB C E DTable 7
Database D3 at T3.
TidItemsetOrdered itemsets1E B CB C E2C E B RB C E3G B D A MB M4B A CB C5M R BB M6C B E MB C E MAt T1 Phase 1, P1 is created, all items in D1 to1-Items list with cur_Sup and incr_Sup = support of item in D1 are added, and incr_Minsup is set; here, = cur_Minsup, and the value of cur_Minsup = 0.5 ∗10 = 5. Figure 3(a) shows P1 after Phase 1. Phase 2: the tree is created as shown in Figure 3(b). At T1, the tree is built only from transactions in D1. Phase 3: bottom-up looping of each item in 1-Items list from P1 is started; if cur_Sup ≥ cur_Minsup or incr_Sup ≥ incr_Minsup, it is started from item {A} and then FP-Max is called for mining MFIs, and its output is MFIsnew = {A, C:5}. Phase 4: the value of MinNMA,CIMFIslist is calculated, and its value = 1, because IMFI list for each item in 1-Items list from P1 is null. Then, the value of MinNMA,CIMFIslist ≥ minNovlty (1 ≥ 0.5) is compared; i.e., MFIs {A, C:5} are interesting, so it is added to IMFI list of the item {A}. Phase 5: rules from it are generated where each rule has Conf ≥0.7. Then, phase 3 is proceeded for taking item{C}. The output of this phase is MFIs = {B, C, E:5}. Phase 4: the value of NMBCEAC=2+3−2∗1/2+3=0.6 is calculated, which is the minNM. Then, the value of MinNMBCEIMFIslist ≥ minNovlty (.6 ≥ .5) is compared; thus, MFIs {B, C, E:5} are interesting, so it is added to IMFI list with item {C}. Phase 5: rules from it are generated where each rule has Conf ≥0.7. Then, Phase 3 is proceeded, and item{E} is taken; this phase is not the output MFIs for item{E}, so Phase 4 is not processed; also, item{B} has no MFIs. Figure 3(c) shows P1 after phases 3-4 at T1. Table 8 shows generated rules that have Conf ≥0.7 after phase 5 at T1. (Note) At T1, 9 rules are interesting (1-9) (green color).Figure 3
Example at T1. (a) P1 after phase 1, (b) tree as FP-tree after phase 2, and (c) P1 after phases 3-4.
(a)(b)(c)Table 8
Rules that have Conf ≥0.7 after phase 5 at T1.
No.RuleConfNo.RuleConfNo.RuleConf1A ⟶ C14B ⟶ E17CE ⟶ B12C ⟶ A0.715E ⟶ B18BC ⟶ E13C ⟶ B0.716C ⟶ E0.719C ⟶ BE0.71At T2, Phase 1, P2 = P1 is created, and then, cur_Sup = support of item in D2, incr_Sup+ = cur_Sup, and incr_Minsup + = cur_Minsup are set. At T2, the value of cur_Minsup = 0.5 ∗ 6 = 3. Figure4(a) shows P2 after phase 1. Phase 2: the tree is created. Figure 4(b) shows P2, and Figure 4(c) shows the tree after phase 2. The outcome of phases 3-4 is P2 as Figure 4(d) shows. Phase 5: rules that have Conf ≥0.7 are generated as shown in Table 9. (Note) At T2, only 2 rules are interesting (rule 15 and rule 16) (green color), 14 rules are not interesting, 12 rules undergo change in value Conf (3-14) (red color), and 2 rules experience no change in value Conf (1-2).Figure 4
Example at T2. (a) P2 after phase 1, (b) P2 after phase 2, (c) tree as FP-tree after phase 2, and (d) P2 after phases 3-4.
(a)(b)(c)(d)Table 9
Rules that have Conf ≥0.7 after phase 5 at T2.
No.RuleConfNo.RuleConfNo.RuleConf1A ⟶ C17C ⟶ E0.9113CE ⟶ B12C ⟶ A0.718E ⟶ C114B ⟶ CE0.843B ⟶ C0.859BC ⟶ E115G ⟶ B14C ⟶ B0.9110E ⟶ BC116G ⟶ C15B ⟶ E0.8511BE ⟶ C16E ⟶ B112C ⟶ BE0.91At T3, Phase 1: P3 = P2 is created, and then, cur_Sup = support of item in D3, incr_Sup+ = cur_Sup, and incr_Minsup + = cur_Minsup are set. At T3, the value of cur_Minsup = 0.5 ∗ 6 = 3. Figure5(a) shows P3 after Phase 1. Phase 2: the tree is created. Figure 5(b) shows P3, and Figure 5(c) shows the tree after Phase 2. Figure 4(d) shows P3 after phases 3-4. Phase 5: rules that have Conf ≥0.7 are generated as shown in Table 10. (Note) At T3, only 1 rule is interesting (rule 17) (green color), 16 rules are not interesting, 12 rules undergo change in value Conf (3-14) (red color), and 4 rules undergo no change in value Conf (1,2,15,16). The results of the previous example at three times are summarized in Table 11.Figure 5
Example at T3. (a) P3 after Phase 1, (b) P3 after phase 2, (c) tree as FP-tree after phase 2, and (d) P3 after phases 3-4.
(a)(b)(c)and (d)Table 10
Generated rules that have Conf ≥0.7 after phase 5 at T3.
No.RuleConfNo.RuleConfNo.RuleConf1A ⟶ C17C ⟶ E0.8813CE ⟶ B12C ⟶ A0.718E ⟶ C114B ⟶ CE0.743B ⟶ C0.749BC ⟶ E0.8815G ⟶ B14C ⟶ B0.8810E ⟶ BC116G ⟶ C15B ⟶ E0.7411BE ⟶ C117M ⟶ B16E ⟶ B112C ⟶ BE0.88Table 11
Results of the example at times T1, T2, and T3.
TimeMFIsUninteresting rulesIMFIsInteresting rulesT12929T241622T351711


## 4. Experiments and Results

To evaluate the performance of the proposed algorithm (IIMFIs), three experiments were conducted. The first experiment was performed to compare the running time of IIMFI algorithm with two incremental algorithms, namely IM_WMFI and IMU2P-Miner on datasets incrementally, as explained in Section4.1. The second experiment was performed to compare the running time of IIMFI algorithm on static datasets against two state-of-the art static algorithms, namely CL-Max and SelPMiner, as explained in Section 4.2. (Note that in these two experiments, all algorithms discovered the same MFIs, confirming that the results produced by the algorithms in our experiments are complete and correct.) The third experiment was performed to test the effect of NM on reducing the count of the discovered MFIs as described in Section 4.3.All algorithms were coded in Java programming language. The three experiments were run on a PC with an Intel Core i5 2.60 GHz CPU and 4 GB of RAM. The operating system was Windows 10 Pro (64-bit).The experiments were conducted on five datasets from the FIMI repository: URL:http://fimi.ua.ac.be. The datasets are commonly used by researchers in the field of ARM. These datasets are varied between real or synthetic datasets in terms of the number of transactions and the density of the transaction (average length of a transaction in datasets). Table 12 shows the characteristics of these datasets. For the experiment on incremental mining, each dataset was divided into three parts representing T1, T2, and T3, respectively, as shown in Table 13.Table 12
Characteristics of experimental datasets.
DatasetAvr. lengthCount itemsCount trans.T10I4D100K10870100000Mushroom231198124T25I10D10K249299976Accidents33468340183Kosarak841270990002Table 13
Characteristics of datasets parts at three times.
DatasetTimeAvr. lengthCount itemsCount trans.T10I4D100KT11086940000T21086930000T31086830000MushroomT123782708T223632708T3231062708T25I10D10KT1228653400T2269013400T3279173176AccidentsT134412150000T234372100566T33436889617KosarakT1834062400000T2831407300000T3830703290002


### 4.1. Experiment 1 (Runtime Dynamic State)

In this experiment, the computation of runtime of IIMFIs is performed against the well-known incremental IM_WMFI and IMU2P-Miner algorithms as shown in Table14. Note that running time here means the execution time (Sec.), which is the period between the input of dataset and the finish mining for each time: time 1 (T1), time 2 (T2), and time 3 (T3). Total runtime refers to the sum of runtime (Sec.) at T1, T2, and T3. This experiment was used in the first phase to discover MFIs without stepping to the rule generation phase. The experiment calculates the runtime at T1, T2, and T3 on three classified times of given datasets as shown in Table 13 and then compares the total executed runtime of IIMFIs, IM_WMFI, and IMU2P-Miner algorithms as shown in Table 14. (Note) In IIMFI algorithm, useNM = false; subsequently, Algorithm 4 used to calculate NM is not called.Table 14
Runtime at T1, T2, T3, and total runtime (Sec.) for IIMFIs, IM_WMFI, and IMU2P-Miner algorithms on five datasets with different Min_Sup values.
DatasetMin_Sup (%)T1 Runtime (Sec.)T2 runtime (Sec.)T3 runtime (Sec.)Total runtime (Sec.)AlgorithmsAlgorithmsAlgorithmsAlgorithmsIM_WMFIIMU2P-MinerIIMFIsIM_WMFIIMU2P-MinerIIMFIsIM_WMFIIMU2P-MinerIIMFIsIM_WMFIIMU2P-MinerIIMFIsT10I4D100K0.21.931.610.822.281.900.622.792.320.596.995.832.030.40.890.630.550.720.510.420.760.540.432.361.691.400.60.710.440.350.540.340.270.580.360.291.831.140.910.80.650.360.290.480.270.210.470.260.211.600.890.7110.570.290.230.430.210.170.420.210.171.420.710.57Mushroom50.220.210.200.250.240.220.330.310.300.800.760.72100.040.040.040.060.050.050.070.070.060.170.160.14150.020.020.020.020.020.020.020.020.020.070.060.05200.020.010.010.020.020.010.020.020.010.060.050.04250.010.010.010.010.010.010.020.010.010.040.030.03T25I10D10K0.60.571.190.360.893.100.561.134.570.712.598.861.620.80.360.450.200.521.240.290.481.860.271.353.560.7510.330.420.190.510.980.260.471.340.241.322.740.681.20.320.150.150.460.600.210.460.690.211.231.450.561.40.320.080.130.440.300.190.460.530.191.220.900.52Accidents409.817.012.169.076.481.6410.407.431.2829.2820.925.07454.042.781.703.232.231.313.642.511.0510.907.524.06502.201.461.261.541.030.951.551.030.805.293.523.01551.490.961.131.010.650.830.940.610.743.442.222.70601.320.831.070.890.560.760.800.500.643.011.882.47Kosarak0.28.877.396.9310.178.484.519.768.144.3528.8024.0015.790.33.622.781.862.592.001.382.541.951.398.756.734.630.42.371.691.601.761.261.191.691.211.145.824.153.920.52.011.341.361.480.981.021.410.940.994.893.263.370.61.721.081.241.280.800.941.270.800.934.282.683.11Figures6(a)–6(e) reflect the results of the total runtime (Sec.) of the three algorithms on the five datasets with different Min_Sup values. As illustrated in Figure 6(a) that represents the results of the total runtime on T10I4D100K, IIMFI algorithm records the least runtime, especially at Min_Sup = 0.2%, followed by IMU2P-Miner algorithm that takes a reasonable runtime and appears closer to IIMFI algorithm, particularly at Min_Sup = 1.0%, whereas IM_WMFI shows a slowing performance. However, the runtime reduction gap between IIMFIs and IMU2P-Miner and IM_WMFI is not consistent as it declines at higher Min_Sup values. Similarly, on T25I10D10K, as Figure 6(c) shows, IIMFIs outperform the other algorithms at all Min_Sup values. The other algorithms show an oscillated runtime where IM_WMFI almost outpaces IMU2P-Miner at all Min_Sup except at 1.2%, where they almost exploit the same runtime, and at 1.4% where IMU2P-Miner shows better runtime performance. Figure 6(b) reveals that on Mushroom dataset, almost all the three algorithms take the same total runtime. A slight difference occurs at Min_Sup = 5% where IIMFIs appears a little bit faster. At Min_Sup = 25%, however, the total runtime is almost the same for the three algorithms. When operated on Accidents as in Figure 6(d), IIMFIs perform generally well at lower Min_Sup = 40% to 50%, while its performance reverts at the higher Min_Sup = 55% to 60%. On the contrary, IMU2P-Miner shows better performance at higher Min_Sup values, while it slows down at lower Min_Sup values; IM_WMFI stays behind the two, especially at lower Min_Sup values. Figure 6(e) shows the results of the total runtime on Kosarak where IIMFIs score a greater reduction runtime rate at Min_Sup = 0.2% and 0.3%, the same runtime of IMU2P-Miner at 0.4% and 0.5%, and slower than IMU2P-Miner at 0.6. IM_WMFI is generally the slowest at all Min_Sup.Figure 6
Comparing the total runtime of T1, T2, and T3 (Sec.) between IM_WMFI, IMU2P-Miner, and IIMFI algorithms on the datasets. (a) T10I4D100K, (b) Mushroom, (c) T25I100D10K, (d) Accidents, and (e) Kosarak.
(a)(b)(c)(d)and (e)The performance of the three algorithms, IIMFIs, IMU2P-Miner, and IM_WMFI, varies from one dataset to another depending on the characteristics of datasets (Figures6(a)–6(e)). Generally, IIMFI algorithm is faster than IM_WMFI and IMU2P-Miner on all datasets. This may be due to the nature of its incremental tree structure that reduces counting loop and time through maintaining the discovered MIFs of the first time and updating incr_Sup only without rescanning the whole data. Based on the experimental results, IIMFIs generally achieve a higher runtime efficiency rate against other algorithms, particularly on T10I4D100K, T25I10D10K, and Accidents. However, on Mushroom and Kosarak datasets the IIMFI runtime oscillates. We can notice the efficiency of IIMFIs in dealing with high-weight and dense dynamic data as with T10I4D100K and T25I10D10K, where it scores superiority, especially at lower Min_Sup. As shown in Figures 6(c) and 6(d), IIMFIs score higher time efficiency at smaller Min_Sup values due to the count of items and MFIs since T25I10D10K and Accidents are dense datasets. However, at higher Min_Sup, and subsequently, with the high MFI count discovered, it slightly slows. This explains that the count of MFIs is higher at T1, which consequently affects the sum of time needed at T2 and consequently affects the sum of runtime at T3. As shown in Figure 6(a), the higher the Min_Sup value is, the greater the increase in the number of MFIs and, consequently, the less the reduction runtime rate. Since Mushroom is a sparse dataset but with high count items, the difference in runtime consumption is almost the same for the three algorithms (Figure 6(b)). Therefore, at T1 and T2, item number is greater, MFI count is higher, and Min_Sup value is lower. In this case, IIMFI performance is faster because the tree can hold and update the support of MFIs without the need to re-mine MFIs from the tree. It is observed that at Min_Sup = 1.4% on Mushroom, IMU2P-Miner algorithm works well at higher Min_Sup values, which indicates that this algorithm best operates on univariate uncertain dada as it uses a tree structure local array to keep the updates.The evaluation of the execution time of the tested algorithms on dynamic data experimentally revealed that our algorithm was faster than all the other algorithms due to its ability to handle the MFI rule mining problem by updating the tree structure and generating fewer trees and, subsequently, shorter executed time. IM_WMFI took the longest time, especially at lower minimum supports or heavy datasets. This was most likely due to the larger number of the sub-generated trees and the schema of updating structure rules of the algorithm compared with faster mining of our algorithm due to its tree structure that does not allow sub-trees and subsequently admits only new items or updates the cur_Sup, thus reducing the total runtime. It has been experimentally observed that when operating on large and high-weight datasets, IMU2P-Miner and our algorithm ran similarly well as they used similar FP-tree structure rules. This indicated that when the dataset's weight was too high, our algorithm was faster as it did not rescan the whole database, and hence, the runtime required to generate and scan the updated trees in our algorithm was also less than the runtime needed to do the same in the other algorithms because the updated trees in our algorithm were constructed from conditioned MFIs.


### 4.2. Experiment 2 (Runtime Static State)

In this experiment, the computation of IIMFI runtime is performed against CL-Max and SelPMiner static algorithms. Figures7(a)–7(e) show the results of the runtime (Sec.) on the five datasets at a static state. Each dataset has a different Min_Sup value. In this experiment, IIMFI algorithm's useNM = false.Figure 7
Comparing the runtime (Sec.) between CL-Max, SelPMiner, IIMFIs algorithms on the datasets at static state. (a) T10I4D100K, (b) Mushroom, (c) T25I100D10K, (d) Accidents, and (e) Kosarak.
(a)(b)(c)(d)and (e)Experimentally, when comparing the total runtime of the three algorithms, we notice that their performance fluctuates depending on the dataset characteristics and the mining structure of the algorithms whether they are tree-based or not. T25I10D10K and Accidents datasets are dense having an unsymmetrical distribution of the item count and transaction count (929 and 9976 for T25I10D10K; 468 and 340183 for Accidents, respectively) with relatively long patterns (average length is 24 for T25I10D10K and 33 for Accidents), while the datasets T10I4D100K and Kosarak are sparse with a variation of item count and transaction count (870 and 100000 for T10I4D100K; 41270 and 990002 for Kosarak, respectively) and characterized by relatively short patterns (average length is 10 for T10I4D100K and 8 for Kosarak). Mushroom is a sparse dataset characterized by symmetrical distribution of the maximal FPs with relatively long patterns (average length is 23) and small item count and transaction count (119 and 8124, respectively). Regarding the mining structure of the algorithms, IIMFIs and SelPMiner are tree-based, whereas CL-Max is not. Figure7(a) shows the experimental results on T10I4D100K. As T10I4D100K contains smaller number of items, the performance of the algorithms fluctuates so that IIMFIs prove faster than CL-Max algorithm at all Min_Sup and outpace SelPMiner at lower Min_Sup = 0.2% and 0.4%. However, at Min_Sup = 0.6% to 1%, SelPMiner performs faster than IIMFIs and outperforms CL-Max algorithm at all Min_Sup. Also, on T25I10D10K, IIMFI algorithm shows superiority over CL-Max and SelPMiner algorithms at all Min_Sup, as in Figure 7(c). CL-Max algorithm outpaces SelPMiner at Min_Sup = 0.8% to 1.4%, except for 0.6%, where SelPMiner outperforms CL-Max algorithm. As for the performance of the three algorithms on Accidents dataset as illustrated in Figure 7(d), the IIMFI algorithm is generally faster than CL-Max and SelPMiner algorithms at all Min_Sup, while SelPMiner algorithm shows comfortably less runtime than CL-Max at all Min_Sup. When approaching the higher Min_Sup values, they have similar runtime consumption. As for Mushroom dataset ( Figure 7(b)), IIMFIs take less execution time at lower Min_Sup = 5% and 10%, but similar runtime of the other algorithms at higher Min_Sup = 15% to 25%. This may be attributed to the characteristic parameters of Mushroom dataset as sparse but large, having fairly long pattern average, which makes it appropriately workable for all algorithms. Figure 7(e) shows that SelPMiner algorithm has faster pruning than IIMFIs and CL-Max algorithms at all threshold values when implemented on the Kosarak dataset. IIMFIs take the longest time and are outpaced by both SelPMiner and CL-Max algorithms at all threshold values. This may be attributed to the search pattern of SelPMiner algorithm of selective partitioning, based on itemset-count tree, which is apt for compact datasets. Its MFI-tree structure works very well, especially when the dataset is sparse but very large. On the other hand, IIMFIs are working efficiently when a dataset is dense, so that at lower thresholds IIMFIs show an efficient runtime reduction rate compared with SelPMiner and CL-Max algorithms. The overall evaluation of experimental tests shows satisfactory results that our algorithm is still effective and satisfactorily fast.


### 4.3. Experiment 3 (Effect of NM on MFIs and Rules)

In this experiment, we evaluated the effect of the NM on the reduction in MFI count and rules generated from MFIs. The experiment was applied to all the datasets with different multiple Min_Sup. In this experiment, useNM = true is used in the proposed algorithm, utilizing two minNovlty values 0 and 0.2, and minConf = 0.7. Table15 shows the effect of NM on the reduction in MFIs when we applied minNovlty = 0.2. MFIs refer to the count of extracted MFIs without NM; i.e., minNovlty = 0; IMFIs refer to the count of the extracted MFIs with dynamic pruning when minNovlty = 0.2. MFI rules refer to the number of rules generated from MFIs where these rules have Conf ≥ minConf; IMFI rules refer to the number of rules generated from IMFIs where these rules have Conf ≥ minConf. Reduction (-) indicates the effect of NM at minNovlty = 0.2 on the pruning of MFIs and, subsequently, the reduction in the overall rules in each dataset at different Min_Sup values. The results in Table 15 show that since we are dealing with fixed values in static datasets, NM values are generally high.Table 15
Effect of NM on reduction in MFIs and rules when minNovlty = 0.2 and rules having Conf ≥ 0.7.
DatasetMin_Sup (%)MFIsMFI rulesIMFIsIMFI rulesReduction (-)MFIs (%)Rules (%)T10I4D100K0.8432100368992110.93972811289701.0370187189801.13481471298141.23222121000Mushroom51442100530433153077707897105471106131194168846658515321152798131101146593420158670287355358541725105125125672164742T25I10D10K0.23142472080143062635206463510.31949926931011821712968057520.4138242021162125835359689730.5109133108115891022334218930.678798365196613741781691Accidents40762256044218352917186454271001461381855268815021637616879703607455125158785553945666607870363927625061Kosarak0.4467328242725499220.622414202121362540.8127755119688691.08848082464731.2672766426943As Table15 reveals, there is a direct effect of NM on the count of MFIs and rules when minNovlty = 0.2 compared with the case when minNovlty = 0. NM reduces the count of MFIs and rules in all datasets at all dregs of Min_Sup. The highest effect is on T10I4D100K (92%–100%), while the least effect is on Kosarak (4%–9%). The difference in the percentage of the NM effect from one dataset to another is due to the intensity and degrees of Min_Sup in each dataset. It has been found that in some datasets, the effect is direct, i.e., the higher the degree of Min_Sup is, the greater the effect of the NM, as with T10I4D100K and T25I10D10K datasets. However, some of the datasets have the opposite effect; i.e., the higher the Min_Sup is, the lower the impact ratio of NM, as with Mushroom, Accidents, and Kosarak datasets. This is due to the count of MFIs at each Min_Sup and the average length of MFIs in each dataset.


## 4.1. Experiment 1 (Runtime Dynamic State)

In this experiment, the computation of runtime of IIMFIs is performed against the well-known incremental IM_WMFI and IMU2P-Miner algorithms as shown in Table14. Note that running time here means the execution time (Sec.), which is the period between the input of dataset and the finish mining for each time: time 1 (T1), time 2 (T2), and time 3 (T3). Total runtime refers to the sum of runtime (Sec.) at T1, T2, and T3. This experiment was used in the first phase to discover MFIs without stepping to the rule generation phase. The experiment calculates the runtime at T1, T2, and T3 on three classified times of given datasets as shown in Table 13 and then compares the total executed runtime of IIMFIs, IM_WMFI, and IMU2P-Miner algorithms as shown in Table 14. (Note) In IIMFI algorithm, useNM = false; subsequently, Algorithm 4 used to calculate NM is not called.Table 14
Runtime at T1, T2, T3, and total runtime (Sec.) for IIMFIs, IM_WMFI, and IMU2P-Miner algorithms on five datasets with different Min_Sup values.
DatasetMin_Sup (%)T1 Runtime (Sec.)T2 runtime (Sec.)T3 runtime (Sec.)Total runtime (Sec.)AlgorithmsAlgorithmsAlgorithmsAlgorithmsIM_WMFIIMU2P-MinerIIMFIsIM_WMFIIMU2P-MinerIIMFIsIM_WMFIIMU2P-MinerIIMFIsIM_WMFIIMU2P-MinerIIMFIsT10I4D100K0.21.931.610.822.281.900.622.792.320.596.995.832.030.40.890.630.550.720.510.420.760.540.432.361.691.400.60.710.440.350.540.340.270.580.360.291.831.140.910.80.650.360.290.480.270.210.470.260.211.600.890.7110.570.290.230.430.210.170.420.210.171.420.710.57Mushroom50.220.210.200.250.240.220.330.310.300.800.760.72100.040.040.040.060.050.050.070.070.060.170.160.14150.020.020.020.020.020.020.020.020.020.070.060.05200.020.010.010.020.020.010.020.020.010.060.050.04250.010.010.010.010.010.010.020.010.010.040.030.03T25I10D10K0.60.571.190.360.893.100.561.134.570.712.598.861.620.80.360.450.200.521.240.290.481.860.271.353.560.7510.330.420.190.510.980.260.471.340.241.322.740.681.20.320.150.150.460.600.210.460.690.211.231.450.561.40.320.080.130.440.300.190.460.530.191.220.900.52Accidents409.817.012.169.076.481.6410.407.431.2829.2820.925.07454.042.781.703.232.231.313.642.511.0510.907.524.06502.201.461.261.541.030.951.551.030.805.293.523.01551.490.961.131.010.650.830.940.610.743.442.222.70601.320.831.070.890.560.760.800.500.643.011.882.47Kosarak0.28.877.396.9310.178.484.519.768.144.3528.8024.0015.790.33.622.781.862.592.001.382.541.951.398.756.734.630.42.371.691.601.761.261.191.691.211.145.824.153.920.52.011.341.361.480.981.021.410.940.994.893.263.370.61.721.081.241.280.800.941.270.800.934.282.683.11Figures6(a)–6(e) reflect the results of the total runtime (Sec.) of the three algorithms on the five datasets with different Min_Sup values. As illustrated in Figure 6(a) that represents the results of the total runtime on T10I4D100K, IIMFI algorithm records the least runtime, especially at Min_Sup = 0.2%, followed by IMU2P-Miner algorithm that takes a reasonable runtime and appears closer to IIMFI algorithm, particularly at Min_Sup = 1.0%, whereas IM_WMFI shows a slowing performance. However, the runtime reduction gap between IIMFIs and IMU2P-Miner and IM_WMFI is not consistent as it declines at higher Min_Sup values. Similarly, on T25I10D10K, as Figure 6(c) shows, IIMFIs outperform the other algorithms at all Min_Sup values. The other algorithms show an oscillated runtime where IM_WMFI almost outpaces IMU2P-Miner at all Min_Sup except at 1.2%, where they almost exploit the same runtime, and at 1.4% where IMU2P-Miner shows better runtime performance. Figure 6(b) reveals that on Mushroom dataset, almost all the three algorithms take the same total runtime. A slight difference occurs at Min_Sup = 5% where IIMFIs appears a little bit faster. At Min_Sup = 25%, however, the total runtime is almost the same for the three algorithms. When operated on Accidents as in Figure 6(d), IIMFIs perform generally well at lower Min_Sup = 40% to 50%, while its performance reverts at the higher Min_Sup = 55% to 60%. On the contrary, IMU2P-Miner shows better performance at higher Min_Sup values, while it slows down at lower Min_Sup values; IM_WMFI stays behind the two, especially at lower Min_Sup values. Figure 6(e) shows the results of the total runtime on Kosarak where IIMFIs score a greater reduction runtime rate at Min_Sup = 0.2% and 0.3%, the same runtime of IMU2P-Miner at 0.4% and 0.5%, and slower than IMU2P-Miner at 0.6. IM_WMFI is generally the slowest at all Min_Sup.Figure 6
Comparing the total runtime of T1, T2, and T3 (Sec.) between IM_WMFI, IMU2P-Miner, and IIMFI algorithms on the datasets. (a) T10I4D100K, (b) Mushroom, (c) T25I100D10K, (d) Accidents, and (e) Kosarak.
(a)(b)(c)(d)and (e)The performance of the three algorithms, IIMFIs, IMU2P-Miner, and IM_WMFI, varies from one dataset to another depending on the characteristics of datasets (Figures6(a)–6(e)). Generally, IIMFI algorithm is faster than IM_WMFI and IMU2P-Miner on all datasets. This may be due to the nature of its incremental tree structure that reduces counting loop and time through maintaining the discovered MIFs of the first time and updating incr_Sup only without rescanning the whole data. Based on the experimental results, IIMFIs generally achieve a higher runtime efficiency rate against other algorithms, particularly on T10I4D100K, T25I10D10K, and Accidents. However, on Mushroom and Kosarak datasets the IIMFI runtime oscillates. We can notice the efficiency of IIMFIs in dealing with high-weight and dense dynamic data as with T10I4D100K and T25I10D10K, where it scores superiority, especially at lower Min_Sup. As shown in Figures 6(c) and 6(d), IIMFIs score higher time efficiency at smaller Min_Sup values due to the count of items and MFIs since T25I10D10K and Accidents are dense datasets. However, at higher Min_Sup, and subsequently, with the high MFI count discovered, it slightly slows. This explains that the count of MFIs is higher at T1, which consequently affects the sum of time needed at T2 and consequently affects the sum of runtime at T3. As shown in Figure 6(a), the higher the Min_Sup value is, the greater the increase in the number of MFIs and, consequently, the less the reduction runtime rate. Since Mushroom is a sparse dataset but with high count items, the difference in runtime consumption is almost the same for the three algorithms (Figure 6(b)). Therefore, at T1 and T2, item number is greater, MFI count is higher, and Min_Sup value is lower. In this case, IIMFI performance is faster because the tree can hold and update the support of MFIs without the need to re-mine MFIs from the tree. It is observed that at Min_Sup = 1.4% on Mushroom, IMU2P-Miner algorithm works well at higher Min_Sup values, which indicates that this algorithm best operates on univariate uncertain dada as it uses a tree structure local array to keep the updates.The evaluation of the execution time of the tested algorithms on dynamic data experimentally revealed that our algorithm was faster than all the other algorithms due to its ability to handle the MFI rule mining problem by updating the tree structure and generating fewer trees and, subsequently, shorter executed time. IM_WMFI took the longest time, especially at lower minimum supports or heavy datasets. This was most likely due to the larger number of the sub-generated trees and the schema of updating structure rules of the algorithm compared with faster mining of our algorithm due to its tree structure that does not allow sub-trees and subsequently admits only new items or updates the cur_Sup, thus reducing the total runtime. It has been experimentally observed that when operating on large and high-weight datasets, IMU2P-Miner and our algorithm ran similarly well as they used similar FP-tree structure rules. This indicated that when the dataset's weight was too high, our algorithm was faster as it did not rescan the whole database, and hence, the runtime required to generate and scan the updated trees in our algorithm was also less than the runtime needed to do the same in the other algorithms because the updated trees in our algorithm were constructed from conditioned MFIs.


## 4.2. Experiment 2 (Runtime Static State)

In this experiment, the computation of IIMFI runtime is performed against CL-Max and SelPMiner static algorithms. Figures7(a)–7(e) show the results of the runtime (Sec.) on the five datasets at a static state. Each dataset has a different Min_Sup value. In this experiment, IIMFI algorithm's useNM = false.Figure 7
Comparing the runtime (Sec.) between CL-Max, SelPMiner, IIMFIs algorithms on the datasets at static state. (a) T10I4D100K, (b) Mushroom, (c) T25I100D10K, (d) Accidents, and (e) Kosarak.
(a)(b)(c)(d)and (e)Experimentally, when comparing the total runtime of the three algorithms, we notice that their performance fluctuates depending on the dataset characteristics and the mining structure of the algorithms whether they are tree-based or not. T25I10D10K and Accidents datasets are dense having an unsymmetrical distribution of the item count and transaction count (929 and 9976 for T25I10D10K; 468 and 340183 for Accidents, respectively) with relatively long patterns (average length is 24 for T25I10D10K and 33 for Accidents), while the datasets T10I4D100K and Kosarak are sparse with a variation of item count and transaction count (870 and 100000 for T10I4D100K; 41270 and 990002 for Kosarak, respectively) and characterized by relatively short patterns (average length is 10 for T10I4D100K and 8 for Kosarak). Mushroom is a sparse dataset characterized by symmetrical distribution of the maximal FPs with relatively long patterns (average length is 23) and small item count and transaction count (119 and 8124, respectively). Regarding the mining structure of the algorithms, IIMFIs and SelPMiner are tree-based, whereas CL-Max is not. Figure7(a) shows the experimental results on T10I4D100K. As T10I4D100K contains smaller number of items, the performance of the algorithms fluctuates so that IIMFIs prove faster than CL-Max algorithm at all Min_Sup and outpace SelPMiner at lower Min_Sup = 0.2% and 0.4%. However, at Min_Sup = 0.6% to 1%, SelPMiner performs faster than IIMFIs and outperforms CL-Max algorithm at all Min_Sup. Also, on T25I10D10K, IIMFI algorithm shows superiority over CL-Max and SelPMiner algorithms at all Min_Sup, as in Figure 7(c). CL-Max algorithm outpaces SelPMiner at Min_Sup = 0.8% to 1.4%, except for 0.6%, where SelPMiner outperforms CL-Max algorithm. As for the performance of the three algorithms on Accidents dataset as illustrated in Figure 7(d), the IIMFI algorithm is generally faster than CL-Max and SelPMiner algorithms at all Min_Sup, while SelPMiner algorithm shows comfortably less runtime than CL-Max at all Min_Sup. When approaching the higher Min_Sup values, they have similar runtime consumption. As for Mushroom dataset ( Figure 7(b)), IIMFIs take less execution time at lower Min_Sup = 5% and 10%, but similar runtime of the other algorithms at higher Min_Sup = 15% to 25%. This may be attributed to the characteristic parameters of Mushroom dataset as sparse but large, having fairly long pattern average, which makes it appropriately workable for all algorithms. Figure 7(e) shows that SelPMiner algorithm has faster pruning than IIMFIs and CL-Max algorithms at all threshold values when implemented on the Kosarak dataset. IIMFIs take the longest time and are outpaced by both SelPMiner and CL-Max algorithms at all threshold values. This may be attributed to the search pattern of SelPMiner algorithm of selective partitioning, based on itemset-count tree, which is apt for compact datasets. Its MFI-tree structure works very well, especially when the dataset is sparse but very large. On the other hand, IIMFIs are working efficiently when a dataset is dense, so that at lower thresholds IIMFIs show an efficient runtime reduction rate compared with SelPMiner and CL-Max algorithms. The overall evaluation of experimental tests shows satisfactory results that our algorithm is still effective and satisfactorily fast.


## 4.3. Experiment 3 (Effect of NM on MFIs and Rules)

In this experiment, we evaluated the effect of the NM on the reduction in MFI count and rules generated from MFIs. The experiment was applied to all the datasets with different multiple Min_Sup. In this experiment, useNM = true is used in the proposed algorithm, utilizing two minNovlty values 0 and 0.2, and minConf = 0.7. Table15 shows the effect of NM on the reduction in MFIs when we applied minNovlty = 0.2. MFIs refer to the count of extracted MFIs without NM; i.e., minNovlty = 0; IMFIs refer to the count of the extracted MFIs with dynamic pruning when minNovlty = 0.2. MFI rules refer to the number of rules generated from MFIs where these rules have Conf ≥ minConf; IMFI rules refer to the number of rules generated from IMFIs where these rules have Conf ≥ minConf. Reduction (-) indicates the effect of NM at minNovlty = 0.2 on the pruning of MFIs and, subsequently, the reduction in the overall rules in each dataset at different Min_Sup values. The results in Table 15 show that since we are dealing with fixed values in static datasets, NM values are generally high.Table 15
Effect of NM on reduction in MFIs and rules when minNovlty = 0.2 and rules having Conf ≥ 0.7.
DatasetMin_Sup (%)MFIsMFI rulesIMFIsIMFI rulesReduction (-)MFIs (%)Rules (%)T10I4D100K0.8432100368992110.93972811289701.0370187189801.13481471298141.23222121000Mushroom51442100530433153077707897105471106131194168846658515321152798131101146593420158670287355358541725105125125672164742T25I10D10K0.23142472080143062635206463510.31949926931011821712968057520.4138242021162125835359689730.5109133108115891022334218930.678798365196613741781691Accidents40762256044218352917186454271001461381855268815021637616879703607455125158785553945666607870363927625061Kosarak0.4467328242725499220.622414202121362540.8127755119688691.08848082464731.2672766426943As Table15 reveals, there is a direct effect of NM on the count of MFIs and rules when minNovlty = 0.2 compared with the case when minNovlty = 0. NM reduces the count of MFIs and rules in all datasets at all dregs of Min_Sup. The highest effect is on T10I4D100K (92%–100%), while the least effect is on Kosarak (4%–9%). The difference in the percentage of the NM effect from one dataset to another is due to the intensity and degrees of Min_Sup in each dataset. It has been found that in some datasets, the effect is direct, i.e., the higher the degree of Min_Sup is, the greater the effect of the NM, as with T10I4D100K and T25I10D10K datasets. However, some of the datasets have the opposite effect; i.e., the higher the Min_Sup is, the lower the impact ratio of NM, as with Mushroom, Accidents, and Kosarak datasets. This is due to the count of MFIs at each Min_Sup and the average length of MFIs in each dataset.


## 5. Conclusion and Future Work

The study introduces a novel approach for mining incremental interesting MFIs by extending FP-Growth and FP-Max to reduce the scanning time and results of MFIs in datasets arriving at different times. The approach framework is structured in five phases representing the approach algorithm IIMFIs, which constitute the proposed design of this work. The proposed approach is incrementally self-adjusting in nature that integrates the previous and current data by adding and updating only new items or items with clearly defined support and incremental support values. Based on developing a tree structure mining method, the proposed approach has advantageously integrated objective and subjective measure (novelty measure) test in dynamic pruning so that only interesting MFIs are produced and only interesting rules are generated.For evaluation purpose, three experiments were conducted on five datasets to test the efficiency of the proposed IIMFI method. Two experiments were performed to test the runtime efficiency of IIMFIs against two MFI incremental methods and two state-of-the-art static algorithms and an experiment to test the effectiveness of IIMFIs in reducing the number of MFIs and discovered rules by incorporating NM during mining process. The experimental results are promising, revealing that the proposed IIMFI method NM generally has a direct effect on the reduction in MFI count and rules in all datasets at all dregs and Min_Sup. However, the varying effect of IIMFI performance and NM on the number of MFIs differs from one dataset to another, which can be attributed to the nature of the dataset, its average length (density), and number of items.Future work will be on testing the effectiveness of the proposed algorithm on other datasets with different degrees using the concept of “pre-large” to avoid errors in calculating the degree of the incr_Minsup, or using list structure for looking at the price or quantities of the items. More experiments may be conducted to evaluate the impact of subjective measures on objective measures. Future work is also suggested for developing a proposed algorithm that deals with parallel processing of data.



---

*Source: 1942517-2022-07-26.xml*