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, { ( p 1 , p 2 ) , ( p 1 , p 3 ) , ( p 1 , p 4 ) , ( p 2 , p 4 ) , ( p 3 , p 2 ) , ( p 3 , p 4 ) } 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 L M ′ and L M ″ are respectively the binary matrices of the itemsets M ′ and M ″ , the matrix L M ′ M ″ of the itemset M ′ M ″ is L M ′ M ″ = L M ′ AND L M ″ , where AND is the logical conjunction operator, i.e. L M ′ M ″ [ i , j ] = L M ′ [ i , j ] AND L M ″ [ 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.

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: (3) Supp ( M ) = | { ( o , o ′ ) ∈ D x D ∣ o < M o ′ } | | D | ( | D | − 1 ) . The Graank algorithm is based on the Apriori principle, also known as the generate-test principle, which consists of generating candidate itemsets, calculating the gradual support of said candidates and retaining only those candidates whose support is greater than the minimum support threshold. This algorithm performs a breadth-first search of the search space. During the first iteration, it generates candidates of size 1 and retains only those that are frequent. More generally, in the ( k − 1 )-th iteration, it generates the candidates of size k and selects those that are frequent. The algorithm stops if none of the candidates of an iteration is frequent.

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.

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 2 k 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 ( 2 k − p ), between 2 k + 1 and 2 k. 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 2 k − 1 + 1 up to 2 k . In the first version of the algorithm, at the k-th iteration, the algorithm generates all candidates whose size is between ( 2 k − 1 + 1 ) to 2 k only from the frequent itemsets of sizes 2 k − 1 obtained at the k − 1 iteration. Then, it goes through all the candidates in ascending order of their level, from level ( 2 k − 1 + 1 ) to 2 k , 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 ( 2 k − 1 + 1 ) to 2 k . 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 2 k − 1 .

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.

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

Consider a candidate c of level l = 2 k − 1 + p for some p and some k, corresponding to the k-th iteration of the new algorithm, such that 1 ⩽ p ⩽ 2 k − 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 2 p frequent itemsets of size 2 k − 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 2 k − 1 . Moreover, the matrix of c is issued from the product of two matrices of frequent itemsets of level 2 k − 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 M S ( k ), M S 1 ( k ) and M S 2 ( k ) the memory space required by the k-th iteration respectively in Graank, in the first and second versions of the proposed algorithm. M S ( k ), M S 1 ( k ) and M S 2 ( k ) depend on the storage space of candidate itemsets and frequent itemsets. Here, we evaluate M S ( k ), M S 1 ( k ) and M S 2 ( 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 F k + . Thus, in Graank, we have: (6) M S ( k ) = ∑ l = 1 k − 2 ( | F l + | l ) + | F k − 1 + | ( ( k − 1 ) + n 2 ) + ( k + n 2 ) + | F k + | ( k + n 2 ) .

This is equivalent to: (7) M S ( k ) = ∑ l = 1 k ( | F l + | l ) + | F k − 1 + | n 2 + ( k + n 2 ) + | F k + | n 2 .

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 2 k − 1 + 1 and 2 k . 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 F l + without its matrix if l < 2 k 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: (8) M S 1 ( k ) = ∑ l = 1 l = 2 k − 1 − 1 ( | F l + | l ) + | F 2 k − 1 + | ( 2 k − 1 + n 2 ) + ( 2 k + n 2 ) + ( ∑ l = 2 k − 1 + 1 2 k ( | C l + | l ) + max l = 2 k − 1 + 1 2 k ( | F l + | l ) ) + | F 2 k + | n 2 .

This is equivalent to: (9) M S 1 ( k ) = ∑ l = 1 l = 2 k − 1 ( | F l + | l ) + | F 2 k − 1 + | n 2 + ( 2 k + n 2 ) + ( ∑ l = 2 k − 1 + 1 2 k ( | C l + | l ) + max l = 2 k − 1 + 1 2 k ( | F l + | l ) ) + | F 2 k + | n 2 . In (8), the first expression is the memory space required to store all frequent itemsets discovered between levels 1 and 2 k − 1 − 1, without storing their matrices. The second expression is the memory space required to store all the frequent itemsets discovered at level 2 k − 1 with their matrices. All frequent itemsets of size 2 k − 1 and their matrices are used to generate all candidates whose size is between 2 k − 1 + 1 and 2 k with 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 needed to store all candidates of unprocessed levels and all frequent itemsets whose size is between 2 k − 1 + 1 and 2 k without their matrices. The fifth expression is the memory space required to store all the matrices of frequent itemsets of size 2 k .

In the second version of the proposed algorithm, at iteration k, after generating a candidate whose size is between 2 k − 1 + 1 and 2 k , 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 F l + without its matrix if l < 2 k and with its matrix otherwise. Thus, in the second version of the proposed algorithm, we have: (10) M S 2 ( k ) = ∑ l = 1 l = 2 k − 1 − 1 ( | F l + | l ) + | F 2 k − 1 + | ( 2 k − 1 + n 2 ) + ( 2 k + n 2 ) + ∑ l = 2 k − 1 + 1 l = 2 k − 1 ( | F l + | l ) + | F 2 k + | ( 2 k + n 2 ) . This is equivalent to: (11) M S 2 ( k ) = ∑ l = 1 l = 2 k − 1 ( | F l + | l ) + | F 2 k − 1 + | n 2 + ( 2 k + n 2 ) + ∑ l = 2 k − 1 + 1 l = 2 k ( | F l + | l ) + | F 2 k + | n 2 .

This is equivalent to: (12) M S 2 ( k ) = ∑ l = 1 l = 2 k ( | F l + | l ) + | F 2 k − 1 + | n 2 + ( 2 k + n 2 ) + | F 2 k + | n 2 .

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 2 k − 1 + 1 and 2 k − 1 without their matrices. The fifth expression is the memory space required to store all frequent itemsets of size 2 k 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 2 k − 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 2 k − 1 + p, 1 ⩽ p ⩽ 2 k − 1 , for some p.

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.

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.

This section presents some interesting patterns extracted from real datasets.