An Improved Algorithm for Extracting Frequent Gradual Patterns

2.1Concepts and Definitions

The database described in Table 1 is used to illustrate the concepts and methods for extracting gradual patterns.

For example, in Table 1, A, S and C are items.

In database D in Table 1, A> is linguistically expressed as “increasing age” and A< as “decreasing age”.

M is linguistically interpreted as a conjunction of gradual items. A k-gradual itemsets is an gradual itemset containing k gradual items. For example, the 2-gradual itemset A⩾S⩾ means “the more the age increases, the more the salary increases”.

In the literature, it is often assumed that c(⩾)=⩽, c(⩽)=⩾, c(<)⇒ and c(>)=<. However, as in the work of Berzal et al. (2007), in this work, we will only consider strict inequalities. For example, the gradual itemset A>S< is the complement of the gradual itemset A<S>.

The rule A⩾→S⩾ means “if the age increases, the salary increases”. The fundamental difference between a gradual rule and a gradual pattern is that the gradual rules reflect the causal trends observed in the dataset while the gradual patterns reflect the co-variation trends.

For example, {(p1,p2),(p1,p3),(p1,p4),(p2,p4),(p3,p2),(p3,p4)} is the set of concordant pairs with respect to item A>. In contrast to the concordant pairs, we distinguish the discordant pairs.

Table 2 illustrates the notion of binary matrix of a gradual itemset and the calculation of the binary matrix of a concatenation of itemsets. If LM′ and LM″ are respectively the binary matrices of the itemsets M′ and M″, the matrix LM′M″ of the itemset M′M″ is LM′M″=LM′ANDLM″, where AND is the logical conjunction operator, i.e. LM′M″[i,j]=LM′[i,j]ANDLM″[i,j] for any pair of indexes (i,j).

The extraction of the relevant gradual patterns and rules is based on quality criteria that are based on the concept of support and the concept of trust. The definition of the support concept varies depending on the extraction method. This paper considers the definition based on the notion of concordant pairs.

Table 3 illustrates the notion of gradual support.

Proposition 3 is a consequence of Proposition 2.

2.2Some Approaches to Extracting Gradual Itemsets

The first approach is based on the notion of linear regression (Hüllermeier, 2002). It only considers fuzzy data and rules whose premise and conclusion have a size less than or equal to two. However, the notion of T-norm makes it possible to overcome the size limitation of the premises and conclusions of the gradual rules. This approach makes it possible to extract the gradual rules.

The second approach evaluates the support of a gradual pattern as a function of the number of concordant pairs and the total number of pairs in the database. The support calculation formula proposed in Berzal et al. (2007), corresponds to that of Definition 1. This definition is implemented in the Graank algorithm (Laurent et al., 2009), which extracts frequent gradual patterns. However, in some works, instead of considering half of the total number of pairs in the database, the total number of pairs in the database is considered instead and the support formula becomes:

The third approach evaluates the support of a gradual pattern based on the longest path of its precedence graph. The nodes of the graph are the objects of the database and the arcs translate variations which are in adequacy with the set of comparison operators of the pattern. The graph of precedence of a gradual pattern is a graphic representation of its binary matrix. The Grite algorithm (Di-Jorio et al., 2009c), which extracts frequent gradual patterns, is based on this approach. Like Graank, Grite is based on the Apriori principle. Its weakness comes from the relatively high cost of calculating the longest path of a precedence graph. Therefore, the computational cost of gradual support is high compared to that of Graank. On the other hand, Graank takes into account the magnitude of the distortion for data that do not satisfy the gradual itemsets. Indeed, the deletion of an object can considerably reduce the value of the support and lead to additional calculations in the Grite algorithm.

3.1Presentation of Two Versions of the Proposed Algorithms

Fig. 1

General principle of the new algorithm. In this figure C(i) is the set of all candidates itemsets of size i and CF(i) the set of all frequents itemsets of size i.

Like most pattern discovery algorithms following the Apriori principle, the Graank algorithm performs a breadth-first traversal of the search space to identify frequent gradual itemsets. In this algorithm, the generation of candidate itemsets of size (k+1) is performed by exploiting only gradual and frequent itemsets of size k. To do this, two frequent itemsets of size k are concatenated to form a candidate of size (k+1) if they have (k−1) items in common. The size of a candidate determines his level. For example, if A+S+ and A+C+ are frequent, we concatenate them to obtain the candidate A+S+C+ of size 3, i.e. of level 3. At the k-th iteration, the algorithm generates all candidates of size k from the frequent itemsets of size k−1, then searches for candidates that are frequent. If k=1, the set of candidates is equal to the set of items. The algorithm stops as soon as no frequent itemset is found in an iteration. When k⩾2, the k-th iteration requires a memory area to store all frequent itemsets of level k−1 with their binary matrix and frequent candidates of level k with their binary matrix. The cost of this storage can be important. The binary matrix of a candidate of size k is obtained as a product of two matrices from two frequent itemsets of size k−1. Thus, the binary matrix of a candidate of size k is obtained from (k−1) matrix products. Because of this, the total cost of matrix products can significantly increase the running time of Graank.

The new algorithm presented here attempts to correct Graank’s weaknesses. Compared to Graank, at iteration k⩾3, it reduces the memory space needed to store the itemsets used to generate the candidates and the frequent itemsets discovered at iteration k that will be used at iteration (k+1) to generate the candidates. Moreover, it significantly reduces the number of matrix products needed to determine the binary matrix of a candidate. The first difference between Graank and the proposed algorithm concerns the way candidates are generated. All candidates from size (k+1) up to size 2k are generated only from gradual and frequent itemsets of size k. In this candidate generation approach, two frequent itemsets of size k and having p items in common make it possible to generate a candidate of size (2k−p), between 2k+1 and 2k. The second difference comes from the processing carried out at each iteration as illustrated in Fig. 1. However, we start by searching for all the frequent items before entering the iteration phase. As in Graank, the iterations are numbered starting from 1. However, during iteration k⩾1, instead of searching for all the frequent itemsets of level k as in Graank, we rather search for all the frequent itemsets of the levels 2k−1+1 up to 2k. In the first version of the algorithm, at the k-th iteration, the algorithm generates all candidates whose size is between (2k−1+1) to 2k only from the frequent itemsets of sizes 2k−1 obtained at the k−1 iteration. Then, it goes through all the candidates in ascending order of their level, from level (2k−1+1) to 2k, to select those who are frequent. Like Graank, the proposed algorithm performs a breadth-first traversal of the search space and stops as soon as it encounters the first level which does not contain a frequent candidate. In the second version of the algorithm, at the k-th iteration, the algorithm does not simultaneously store all the candidates whose level varies from (2k−1+1) to 2k. It performs an internal iteration which at each step generates a candidate, calculates its binary matrix and determines if it is frequent. The second version of the algorithm stops at the beginning of iteration k if there is no frequent itemset of size 2k−1.

Algorithm 1

First version of the improved algorithm

Algorithm 2

Second version of the improved algorithm

Algorithms 1 and 2 describe two versions of the improved algorithm. They take as input a database and a minimal support provided by the user, and return the set of frequent gradual patterns. Table 4 describes the list of symbols used in the algorithms. As in Graank, both versions of the proposed algorithm exploit the notion of complementarity to reduce the search space by half. To do this, only itemsets with a positive first term are handled. Both versions search and store all frequent itemsets in main memory. Both versions of the algorithm can be modified in the following way to display each frequent itemset immediately after its discovery and in such a way as to reduce the consumption of main memory:

There are two main differences between Algorithms 1 and 2. The first difference comes from the management of the memory space used to store the candidates of an iteration. During an iteration, Algorithm 1 generates the set of all candidates and selects the frequent ones while Algorithm 2 generates the first candidate and keeps it if it is frequent, then generates the second candidate and retains it if it is frequent, and so on. Thus Algorithm 1 requires an additional memory space to store all the candidates of each iteration while Algorithm 2 does not need such memory space. The key idea of Algorithm 2 is to save memory. The second difference comes from their termination criteria. Algorithm 1 could terminate during one iteration without computing the supports of all candidates in said iteration while Algorithm 2 cannot do this because it calculates the supports of all the candidates of an iteration. As a result, Algorithm 1 generally finishes before Algorithm 2.

3.2Complexity Analysis

This section studies the time and memory complexities of Graank and the proposed algorithms.

Consider a candidate c of level l=2k−1+p for some p and some k, corresponding to the k-th iteration of the new algorithm, such that 1⩽p⩽2k−1. In Graank, c is derived from the concatenation of two frequent itemsets of size (l−1), which in turn are each derived from the concatenation of two frequent itemsets of size (l−2). By transitivity, c comes from the concatenation of 2p frequent itemsets of size 2k−1. The matrix of c comes from a product of two matrices of level (l−1), and each of them comes in turn from two matrices of level (l−2) and so on. On the other hand, in both versions of the proposed algorithm, c is derived from the concatenation of two frequent itemsets of size 2k−1. Moreover, the matrix of c is issued from the product of two matrices of frequent itemsets of level 2k−1. The number of matrix products performed between the first and the k-th iteration for the computation of the matrix of c is k. Therefore, generating candidate c requires (l−1) itemset concatenations and (l−1) matrix products in Graank, while k itemset concatenations and k matrix products are needed in the proposed algorithms. This leads to Lemma 1.

Lemma 1 shows that the CPU cost of generating a candidate and computing its binary matrix is significantly improved.

Lemma 2 shows that, compared to Graank, the overall candidate generation runtime in the proposed algorithms is significantly improved. The overall runtime of the calculation of matrix multiplications is not improved although the execution time for the calculation of the matrix of a single itemset is significantly improved according to Lemma 1.

Denote by MS(k), MS1(k) and MS2(k) the memory space required by the k-th iteration respectively in Graank, in the first and second versions of the proposed algorithm. MS(k), MS1(k) and MS2(k) depend on the storage space of candidate itemsets and frequent itemsets. Here, we evaluate MS(k), MS1(k) and MS2(k). In Graank, at iteration k, after generating a candidate of size k, its gradual support is calculated to know if it is frequent or not before generating the next candidate. Any frequent candidate discovered at iteration k is stored in Fk+. Thus, in Graank, we have:

This is equivalent to:

In (6), the first expression is the memory space required to store all frequent itemsets discovered between levels 1 and (k−2), without storing their matrices. The second expression is the memory space required to store all the frequent itemsets discovered at level (k−1), with their matrices. All frequent itemsets of size (k−1) and their matrices are used to generate all the candidates of size k and their matrices respectively. The third expression is the memory space required to store the current candidate and its matrix, i.e. the one being processed. The fourth expression is the memory space required to store all frequent itemsets of size k and their matrices.

In the first version of the proposed algorithm, iteration k starts by generating and storing all candidates whose size is between 2k−1+1 and 2k. Then, it performs a breadth-search of all candidates, i.e. level by level. The gradual support of the current candidate, i.e. the one being processed, is calculated to know if it is frequent or not. A frequent candidate of size l is stored in Fl+ without its matrix if l<2k and with its matrix otherwise. Once all the candidates of the same level have been processed, their memory space is freed and used to store frequent itemsets. Thus, in the first version of the proposed algorithm, we have:

This is equivalent to:

In the second version of the proposed algorithm, at iteration k, after generating a candidate whose size is between 2k−1+1 and 2k, its support is calculated to know if it is frequent or not before generating the next candidate. If the current candidate, i.e. the one being processed, is frequent and of size l, it is stored in Fl+ without its matrix if l<2k and with its matrix otherwise. Thus, in the second version of the proposed algorithm, we have:

This is equivalent to:

In formula (10), the first, second and third expressions have the same meaning as their counterpart in formula (8). The fourth expression is the memory space needed to store all frequent itemsets whose size is between 2k−1+1 and 2k−1 without their matrices. The fifth expression is the memory space required to store all frequent itemsets of size 2k and their matrices.

Lemma 4 shows that the first version of the proposed algorithm consumes more memory space than the second one which in turn can consume less or more memory space than Graank under certain constraints. However, the first version may stop one iteration before the second. Thus, the first version stops faster than the second. The second version stops at the start of an iteration that has no candidate. Such an iteration k implies that there is no frequent itemset of size 2k−1. The first version stop during an iteration whose some level has no frequent itemset. Such iteration k implies that there is no frequent itemset of size 2k−1+p, 1⩽p⩽2k−1, for some p.

4.1Presentation of Datasets

In this section, we present four types of datasets: one agricultural dataset (Islam et al., 2018), three health datasets (Li and Liu, 2021; Chicco and Jurman, 2020), one economic dataset (Clémentin et al., 2021) and three synthetic datasets (Clémentin et al., 2021).

The agricultural dataset (agricultural-dataset-bangladesh) comes from information collected on 28 agricultural areas of Bangladesh. It provides relationships between soil nutrients, types of fertilizers, types of soil and meteorological information. The soil nutrients were collected on 6 different types of land: flooded land at high altitude, flooded land at medium altitude, medium land, medium low land, flood low land, very low flood land and miscellaneous land. We have 4 types of fertilizers (urea, triple superphosphate, diammonium dhosphate, and MP). The types of soils come from 19 different types of soil and 4 different types of soil information. The meteorological data come from the Bangladesh Meteorological Department (BMD), providing information on average rainfall, maximum and minimum temperature, and humidity from 2008–2017. The complete description of the different attributes are given in Islam et al. (2018). The initial database is composed of 44 attributes and 70 transactions. For experimentation purposes, non-numeric attributes and those with missing values were remove, reducing the number of attributes to 32. The acces link to the agricultural dataset is https://www.kaggle.com/tanhim/agricultural-dataset-bangladesh-44-parameters

The three health datasets are described in the following.

The economic dataset comes from the Nasdaq Financials dataset (fundamentals.csv) (Clémentin et al., 2021). It contains 35 attributes and 300 transactions. Due to memory limitations, only the first 20 attributes and the first 150 transactions were considered in experimentations. The access link of the economic dataset is https://www.kaggle.com/dgawlik/nyse?select=fundamentals.csv.

The three synthetic datasets are C250-A100-50 (Negrevergne et al., 2014), F20Att00Li (Negrevergne et al., 2014) and test (Negrevergne et al., 2014). The access link to all these datasets is https://github.com/bnegreve/paraminer/tree/master/data/gri

The characteristics of these datasets are summarized in Table 5.

4.2Experimental Evaluation of Algorithms

This section compares the performance of the Graank algorithm (Laurent et al., 2009) and the two versions of the proposed algorithms. Experiments were performed on a computer with a Intel(R) Core(TM) i7 CPU M 620 @ 2.67 GHz 2.67 GHz with 6 GB RAM, running on Windows 10 Home 64-bit operating system. The different algorithms are implemented in Java. The purpose of experiments is to compare the runtime as depicted on Figs. 2, 3, 4, 5 and the memory consumption as shown in Figs. 6, 7, 8, 9 for different support threshold values on datasets presented on Section 4.1.

4.2.1Runtime Evaluation of Algorithms

Figure reffig:timeagriculture shows the runtime performance of the three algorithms on the agricultural dataset. The two versions of the proposed algorithm have almost similar execution times and are sometimes at least five times faster than Graank.

Fig. 2

CPU performance on agricultural dataset.

Figure 3 shows the runtime performances of the three algorithms on the three medical datasets. The two versions of the proposed algorithm are globally faster than Graank on medical datasets. Moreover, they are sometimes seven times faster than Graank on the diabete dataset and twice as fast as Graank on fetal health and heart failure datasets. However, for some support threshold values, both versions of the proposed algorithm are slightly slower than Graank. This is due to the matrix multiplication times according to Lemma 2. As with the agricultural dataset, the two versions of the proposed algorithm have nearly similar runtimes on medical datasets.

Fig. 3

CPU performance on medical datasets.

Figures 4, 5 show the runtime performances of the three algorithms on economic and synthetic datasets respectively. Both versions of the proposed algorithms are faster than Graank. On the other hand, the first version is slightly faster than the second one.

Fig. 4

CPU performance on economic dataset.

Fig. 5

CPU performance on synthetic datasets.

In summary, the runtime evaluation shows that Algorithms 1 and 2 outperform Graank in terms of CPU consumption and are sometimes at least 5–7 times faster. Between Algorithms 1 and 2, the advantage goes to Algorithm 1 in terms of CPU consumption.

4.2.2Memory Evaluation of Algorithms

Figure 6 shows the memory consumption on agricultural dataset. The memory consumption of both versions of the proposed algorithm is less than that of Graank for support threshold values which are less than 0.37 and slightly higher otherwise.

Fig. 6

RAM usage on agricultural dataset.

Figure 7 shows memory consumption on medical datasets. The memory consumption of both versions of the proposed algorithm is lower than that of Graank. On the other hand, the second version uses less memory than the first one.

Fig. 7

RAM usage on medical datasets.

Figure 8 shows the memory consumption on the economical dataset. The memory consumption of both versions of the proposed algorithm is lower than that of Graank. Moreover, the second version uses less memory than the first one.

Fig. 8

RAM usage on economic dataset.

Figure 9 shows the memory consumption on synthetic datasets. The memory consumption of both versions of the proposed algorithm is lower than that of Graank on the first two datasets and slightly higher than that of Graank on the third dataset. As with the economic dataset, the second version consumes less memory than the first one.

Fig. 9

RAM usage on synthetic datasets.

In summary, the memory evaluation shows that, in general, Algorithms 1 and 2 outperform Graank in terms of memory consumption and they require sometimes at most half the memory. Between Algorithms 1 and 2, the advantage goes to Algorithm 2 in terms of memory consumption. However, there are marginal cases where Graank consumes less memory than Algorithms 1 and 2. Formula (18) in Lemma 4 characterizes some of the said cases.

4.3Presentation of Some Interesting Patterns

This section presents some interesting patterns extracted from real datasets.