Definition 1. Gradual item (1, 5–8): It is an attribute. A provided with a comparison operator * ∈ {≤, ≥, <, >} that reflects the direction of variation of the values for this attribute A. It is noted as A*. If * is equal to ≥ (resp. ≤), then A* captures an increasing (resp. decreasing) variation of the values of A.

For example, A^≥, A^≤, and S^≥ are gradual items induced by Table 1. They are interpreted as “the more age increases,” “the more age decreases,” and “the more salary increases.”

Definition 2. Gradual itemset (5–10): A gradual itemset, denoted by {(A_i,*i),i = 1…k} or {A_i^*i, i = 1…k}, is a set of gradual items that expresses a co-variation of the considered items. This set is interpreted semantically as a conjunction of gradual items.

For example, the gradual itemset A^>S^< deduced of Table 1 means that “the more age, the less salary.”

Definition 3. Complementary gradual pattern (1, 5, 9): If a gradual pattern M = {(A_i^*i), i = 1…k}, then its complementary gradual pattern of the same size is denoted c(M). It is defined by c(M) = {(A_i^c(*i)), i = 1…k}, where c(*i) is the complement of the comparison operator *i.

Note: In the previous works (1, 5), c(≤) = ≥, c(≥) = ≤, c(<) = >, c(>) = <.

In Table 1, for example, two gradual patterns A^> and A^>S^< are considered; their complementary is the gradual patterns A^< and A^<S^>.

Definition 4. Inclusion of gradual patterns: The gradual pattern X is included in the gradual pattern Y, noted as X ⊆ Y, if all the gradual items of X are also present in Y.

For example, from Table 1, the gradual pattern A^>S^> is included in the gradual patterns A^>S^>V^> and A^>S^>V^<.

From definitions 3 and 4, we can deduce the two properties allowing a significant pruning of the search space. The first property is the equality property of gradual support (1, 5, 11) and the second is the anti-monotonicity property of gradual support (1, 5, 10, 11).

Definition 5. Lattice of gradual patterns (5). A lattice of gradual patterns is a lattice induced by the set of gradual patterns provided with the inclusion relation. The set of nodes of the lattice is the set of gradual patterns. An arc that goes from a gradual pattern A to a gradual pattern B reflects the inclusion of A in B.

Definition 6. Lattice of gradual patterns with first-term positive: It is a sub lattice of the lattice of gradual patterns that only has as a component the gradual patterns of which at least the first gradual item of each component is positive. They are noted on the form A1≥{A_i^*i }, i = 2…k.

The lattice of gradual patterns is the search space of frequent gradual patterns which is halved by the lattice with the first positive term. To illustrate our point, let us take, for example, Figures 1, 2.

The linear regression technique described by Huller-Meier (12) allows for the extraction of gradual dependences with more support and confidence than the user-specified threshold. This method only takes into account fuzzy data and rules with premise and conclusion numbers less than or equal to two. However, the T-Norm idea, which is part of this technique, allows us to transcend the size restriction of the premise and the conclusion of the rules. The weight of a gradual pattern, also known as Gradual Support (SG) in the method of Berzal et al. (13), is equal to the number of pairs of distinct objects that verify the order imposed by the pattern divided by the P total number of couples of different objects in the database. Thus, Σo,o′∈DxD|o≺Mo′||D|⁢(|D|-1), where M is a gradual pattern and D is the database.

Laurent et al. (10) expand on the technique of Berzal et al. (13), which utilizes the fact that if a pair of objects (o, o’) validates the order established by a gradual pattern, the pair (o’, o) does not.

The gradual support of a gradual pattern M is equal to the length of a maximal path associated with M divided by the entire number of datasets in the so-called maximum pathway approach (9, 11, 14, 15). In this method, we have S⁢G⁢(M)=maxD∈L⁢(M)⁡|D||D|.

Grite serves as the foundation for the SGrite (5, 16) methodology. It prunes the search space by utilizing the support’s anti-monotonicity and complementary patterns properties. The lattice with the first-term positive utilized reduces the search space by half. Another difference between SGrite and Grite is that SGrite only takes one sweep of the dependency graph to compute gradual support, whereas Grite requires two sweeps. She employs two types of gradual support computing algorithms, each of which does a single sweep of the precedence graph.

The two main activities in the SGrite algorithm are the creation of candidates and the computation of the support. As it is run for each candidate, the support calculation is the most requested and CPU-intensive procedure. The SGrite algorithm is built on the following notions. In the definitions that follow, O is the set of objects, and o and o’ are objects.

Definition 7. Adjacency matrix: The adjacency matrix of a gradual pattern M is a bitwise matrix that assigns the values of 1 to every pair of objects (o, o’) if the pair of objects satisfies the pattern M’s order and 0 otherwise.

A pattern’s adjacency matrix generates a dependence graph with nodes that are objects, and nonzero adjacency matrix inputs reflect the dependencies between pairs of nodes.

Definition 8. Father node and son node: Given a pattern M’s adjacency matrix AdjM, for AdjM[o, o’] = 1, we translate the fact that o is the father of o’ and o’ is a child of o.

Definition 9. Isolated node: It is a node that is not linked to another node, i.e., it does not have a father or a son. Considering a pattern M’s adjacency matrix AdjM, the set of isolated nodes is defined by: {o ∈ O| ∀^o’ ∈ O, Adj_M[o, o′] = 0 ∧ Adj_M [o′, o] = 0}.

Definition 10. Root: It is a node that has no parent but is connected to all the other nodes. For the model M’s adjacency matrix Adj_M, the root node-set is formally defined by {o ∈ O| ∀^o’ ∈ O, Adj_M[o, o′] = 1 ∧ Adj_M [o′, o] = 0}.

Definition 11. Leaf: It is a node that does not have a son but is not isolated. Given a pattern M’s adjacency matrix AdjM, the leaves node-set is formally defined by {o ∈ O| ∀^o’ ∈ O, Adj_M[o, o’] = 0 ∃o″∈ O∣Adj_M [o″, o] = 1}.

The SGrite algorithm accepts an adjacency matrix, an object node ∈ O, and a vector of size | O| whose indexes are the objects of O as input. Before running each algorithm, we assume that ∀o ∈ O, Memory[o] = −1. Memory[o] holds the current maximum distance between o and any leaf throughout the execution of each algorithm. Memory[o] holds the ultimate maximum distance between o and any leaf at the end of each algorithm’s execution. The first class of algorithms updates the values of a node’s parents whenever the value of this node changes. The second class of algorithms uses just the final value of a node to update the values of his parents’ nodes. We have four different variants of the SGrite method, namely, SGOpt, SG1, SGB1, and SGB2 (5).

To simplify the description, we will limit 2 partitions and consider a dataset D, which has n items. D is partitioned into two datasets D1 of size n1 and D2 of size n2, such that n = n1 + n2. D1 represents partition 1 of the database containing the n₁ first items, while 2 is the second partition containing the n₂ last items of D.

Definition 12. Partition of a database: It is a part of D which has the same number of transactions as D and which takes a contiguous subset of the items from the dataset D representing the items taken into account in the score. Being denoted by D and I = {i_k} k = 1…n the items, n_k < n, if D_k the kth partition that starts with item number l/l = l < n, we have D_k = (O,I) with I ⊆ I and I = {i_k}_{k = l…l + nk–1}.

Definition 13. Independence of two partitions of a database: Let D₁ = (O, I₁) and D₂ = (O, I₂) be two partitions of a dataset D = (O, I) / I1 ⊂ I, I2 ⊂ I. They are independent iff I₁ ∩ I₂ = Ø.

Example 14. Illustration of partition

Let I = {A, S, V} be the set of attributes of the salary dataset (see Table 1) where A is the age attribute, S is the salary, and V is the vehicle location number attribute.

For example D1 = (O,{A, S}) and D2 = (O,{V}) are two independent partitions of dataset of Table 1.

Order defined on the sets.

Definition 15. Order on items: The order relation on the set of items of a dataset D, denoted by <_I, denotes the natural order relation of appearance of items in D.

For example, in the dataset of Table 1, we will have an order between the items A < I S < I V.

Definition 16. Ordered gradual itemset: An ordered gradual itemset is a gradual itemset that respects the set of items that constitutes the order defined by its position in the set of items for the dataset D = (O, I) considered. Being denoted by M = {A_i^*i }_{i∈{1,2,…,n}} a gradual k-pattern, it is ordered iff ∀j, 1 = j < k, where j represents the index of appearance of the item in the pattern M, and we have A_j < _I A_j+1.

Definition 17. Gradual positive ordered itemset: A positive ordered gradual itemset is an ordered gradual itemset so atleast the first term has increasing variation.

For example, the gradual itemsets A ^> S ^< , A ^< S ^< , A ^> V ^< , and A ^< S ^< V ^< are ordered gradual itemsets. In con- trast, S ^< A ^> is not an ordered gradual itemset, even if it has the same meaning and the same gradual support as A ^> S ^< ordered.

Proposition 18. Total order on two gradual items: When doing a pairwise comparison of gradual items, for example, A11 and A22, if A₁ < _I A₂, then A11 <ImA22 and vice versa, but in the case of A₁ is equal to A₂, the order is induced by the variation associated with each gradual item as follows: if *1 = *2, then A11 <ImA22; if, in contrast, *1 = < and * 2 = > , then A11 <ImA22, so if *1 = > and * 2 = < , then A22 <ImA11.

For example, in Table 1, S ^< <Im S ^>.

Definition 19. Order on two gradual ordered patterns: Let M₁ = { A1_i^*i }_{i = 1…k1}, M₂ = { A2_i^*i }_{i = 1…k2} such that k₁ = k₂ two ordered gradual itemsets (see Definition 16). They are ordered iff ∀k = 1…min(k₁, k₂),A1_k < _I A2_k or A1_k^*k < ^m A2_k^*k (see Proposition 18). Note this order relation between ordered gradual patterns < ^m_I wethenhaveM₁ <ImM₂.

For example, for the gradual itemsets A ^> S ^<, A ^> V ^< respects the following A ^> S ^< <ImA ^> V ^<, which means that the gradual pattern A ^> S ^< is less than A ^>V ^< following this order relation.

Definition 20. Set of ordered gradual patterns: It is a set of gradual patterns ordered by the relation <Im. Being denoted by L_MgO = {Lⁱ_mgo}_{i = 1…n} the set of sets of ordered gradual patterns ∀Lⁱ_mgo ∈ L_MgO such that Lⁱ_mgo = {m_j }_{j = 1…k}, then we have ∀m_j, m_j+1 e Lⁱ_mgo, m_j <Im m_j+1, with j = 1…k −1. Each Lⁱ_mgo is a set of ordered gradual patterns.

The search by partitioning is based on the principle of SGrite, that is to say, one of these optimal variants SGOpt or SG1 (5) on each of the independent partitions considered. Once all the sets of frequent patterns of each of the partitions have been determined and organized by level, according to the sizes of patterns, we must initially merge the gradual patterns of the same level of each partition. The next step is to generate the missing potential candidates by the method described below. This process of determining the frequencies of the whole database goes from a frequent item set of size 1 to the maximum possible size. The steps below always take place in the search space for the lattice at the first positive term. We can summarize the approach in 4 steps:

Example 21. Step 1: collection of frequent gradual pattern by each partition.

Example 22. Step 2: merge the gradual patterns from partitions 1 and 2 (see Tables 2, 3).

Example 23. Final step: Set of frequent gradual patterns of all partitions.

In this phase, we can see that in the gradual 2-patterns those in red color are generated by new patterns formed from items of the 2 partitions.

Example 24. Collection of frequent gradual patterns of Sgrite method.

In the abovementioned notations, the sets mapC^G and IF_k^G all have the two fields: gradual pattern and gradual support(SG), for each of the elements belonging to these sets. The sets mapFr, mapF^G, mapC^G, mapIF_r, and mapI F^G are maps or association tables where the keys are sizes of gradual patterns of each level and the values are a set of k-gradual patterns ordered by the level k considered (i.e., of key k).

Remark: all sets of gradual itemsets contains the positive ordered gradual itemsets.

In algorithm 2, the data structure resultatR has five fields: type Map which represents the indicator on the set choose between mapF^G and mapIF^G, where we will find the gradual item index value of the suffix of the level pattern prefix, Prefix_level maximal; min1 and max1 are the index bounds of over-patterns of Prefix_level in mapF_level^G₊₁; min2 and max2 are the index bounds of the over-patterns of Prefix_level in mapIF^G_level+1. The construction of resultatR is carried out using the function byPrefixFindPositionsMinMax of algorithm 2. The function matrixAdjacency determines the adjacency matrix of the gradual pattern taken as a parameter. The genCandidatOfALevel function generates candidate patterns of size level + 1, following the principle described in step 3-(e) of Section “Partition Working Principle.” In this algorithm, on line 1, the productCartesian function generates a set of patterns resulting from the Cartesian product of the two sets taken as a parameter; here, [get(F_k^p_iⁱ)] [resp. get(F_k^p_iⁱ)] represents the ordered set of the gradual patterns of the level ki of mapFpi(resp. the set of gradual patterns complementary to each pattern of level k_i of mapIF_pi).

The function filterSetByInfrequentSetAndSupportCompute (candidateFusion) allows: (1) to prune first the candidates of its set candidateFusion in parameter, which are supermotif of a inferred pattern of mapIF^G. If the candidate to prune is C_k = {A_i}_{i = i…k} then it generates two new candidates of size k −1, C1_{k –1} = {A_i }_{i = 1…..k –1}, C2_k–1 = {A_i}_{i = 1…k–2} U A_k which are added to the potential candidate list. On the other hand if C k is frequent then, we add C_k at level k of mapF^G and its two frequent sub-patterns C1_k–1, C2_k–1 build exactly as above at level k−1 of ma pF^G. Once candidateFusion = 0 we have completed the process (1) and we have a valid candidate set list. Second, in (2) we have to perform another filtering by support calculation. Here, for any candidate k-pattern C_k = {Ai}_{i = 1…k} of list, C_k ∈ list: if C_k is frequent then we add C_k at level k of mapF^G, and C_1k–1, C_2k–1 at level k_–1 of mapF^G, otherwise delete C k of list and add at the end of the list C_{1 k–1}, C_{2 k–1} as a new candidate in the list. We repeat this process until list = 0.

Note: In each of the algorithms below, before calculating the support of a k-pattern, we check if it does not belong to one or the other sets ma pF_k^G or mapIF_k^G, because indeed the k-pattern may well have been determined during the ascending scan of the search space of the trellis to the first positive term or during the descending scan. The interest is to reduce the number of support computations to the maximum which is a greedy operation.

The method we use is based on SGrite, which itself is an optimized method of Grite in terms of CPU time for extracting gradual patterns. Indeed, the MPSgrite method that we developed in this article has two objectives to achieve. The first objective is to optimize the time for extracting the gradual patterns considered, and the second goal is to reduce the number of gradual patterns extracted. Indeed, in real life, experts in the field say that the fewer patterns extracted, the easier it is to interpret and make decisions. We first opt for an approach of dual traversal of the lattice space to the first positive term from levels 1 to n by SGrite and simultaneously from levels n to 1. The first problem of this combined approach is the generation of the candidates of the maximal set which is of the order of 2^n–1, with n the number of gradual items of the database. Consequently, the generation of candidates will have a higher CPU time cost. In addition, we also note that:

Lemma 25. The greater the number of maximum initial candidates, the higher the determination of the following maximal candidate sets, as well as the operation of fusion of n adjacency matrix composing the n-candidate gradual motifs considered.

Thus, to keep an optimal method of extracting the gradual patterns of the abovementioned maxima, it will be a question of opting for a hybridization method. The base will be based on the choice to be made according to the parameter n number of gradual items. Dataset D of n items, t transactions, and a fixed value p are considered, representing which method to use. Under these conditions, if n is less than or equal to p, then MPSGrite uses the two-way browse method sense, that is, simultaneously ascending and descending from the lattice to a positive term. On the contrary, if n is strictly greater than p, then a bottom- up lattice traversal approach is used which first efficiently generates the lattice of frequent gradual patterns, and then conversely in the descent of the lattice, by “backtracking,” we extract the frequent and maximal gradual patterns.

The search space is limited in each of the components below to the lattice with a positive term. Two components of the hybrid method are required, namely, component 1 and component 2. Component 1 takes place following the path in two simultaneously ascending and descending directions of the positive lattice, and its description is carried out in section “Presentation of the Hybrid Extraction Method for Maximal Gradual Patterns.”

This algorithmic component proceeds in two main steps: In step 1, it is a question of extracting the frequent gradual patterns performed by SGrite. Once this first step is completed its result will be an entry for step 2.

In step 2, we generate the maximum gradual patterns from the frequencies of step 1. During the generation, we must respect the notion of lexicographic order of Apriori, Grite, and SGrite. Let m = n is the size of frequent gradual patterns of maximum cardinality.

In this case, the set of the so-called frequent maximum is initialized by all the frequent gradual m-patterns. Then, one proceeds iteratively to prune the level k−1 of all the subpatterns which allowed the construction of the maximum gradual k-patterns previously determined and purified at iteration k. This process continues in this way until the current processing value of k is 1. In fact, when k = 1, the maximum 1-gradual patterns are determined. This completes the “backtracking” determination of the maximum step patterns.

This part presents the data used for the experiments carried out in this work.

We used a practical database called the weather forecast downloaded from the site http://www.meteo-paris.com/ile-de-france/station-meteo-paris/pro/. The dataset comprises 516 practical data recorded over two days (July 22–23, 2017), which are defined by 26 real numbers including temperature, cumulative rain (mm), humidity (percent), pressure (hPa), wind velocity (km/h), wind perceived temperature, or wind distance traveled (km) (5).

The C250-A100-50 dataset is taken from the site https://github.com/bnegreve/paraminer/tree/master/data/gri. For the reason of memory space, we have reduced the initial number of items from 100 to 12, because, otherwise, the extraction is not possible on our computer.

Winequality-red dataset is taken from the site https://archive.ics.uci.edu/ml/datasets/wine+quality. It is the Wine Quality dataset related to red vinho verde wine samples, from the north of Portugal. The goal is to model wine quality based on physicochemical tests. The dataset’s attributes make use of the following items: volatile acidity, citric acid, fixed acidity, residual sugar, free sulfur dioxide, total sulfur dioxide, density, pH, sulfates, alcohol, and quality (based on sensory data) (scores between 0 and 10).

These two datasets LifeExpectancydevelopped.csv and LifeExpectancydevelopping.csv (5) are also the real datasets taken for the site https://www.kaggle.com/kumarajarshi/life-expectancy- who that are open-access data. The data were as collected from the World Health Organization (WHO) and the United Nations website with the help of Deeksha Russell and Duan Wang. For this life expectancy dataset, attributes 1 and 3 are removed and the rest are used (5). The dataset is designed to answer some key questions such as: do the different predictors I initially select actually affect life expectancy? Should countries with low life expectancy (under 65) increase health spending to increase life expectancy? Is life expectancy related to diet, lifestyle, exercise, smoking, alcohol etc.? Is there a positive or negative relationship between life expectancy and alcohol consumption? Do densely populated countries have a lower life expectancy? How does immunization coverage affect life expectancy? The final merged file (final dataset) consists of 22 columns and 2,938 rows or 20 predictors. All prognostic variables are immunization factors, mortality factors, economic factors, and social factors. Due to the size of the original dataset, we split the data into two groups: LifeExpectancydevelopping.csv for developed countries and LifeExpectancydevelopping.csv for developing countries, where we removed transactions with values empty.

The fundamentals.csv dataset contains metrics extracted from annual SEC 10K fillings (2012–2016), which should be enough to derive most of the popular fundamental indicators. The fundamentals.csv comes from Nasdaq Financials. For this dataset, we have at the beginning 77 attributes. After preprocessing which consisted of removing empty- valued transactions, we derived a dataset with 1,299 transactions and 74 attributes. The removed attributes are the first four: stock symbol, end of period, accounts payable, and accounts receivable, for more information, see https://www.kaggle.com/dgawlik/nyse?select=fundamentals.csv; for reasons related to the characteristics of our small memory computer, we extracted part of the fundamental.csv dataset for the experiments, which gave us a dataset of 300 transactions and 35 attributes. Transactions are the top 300 and attributes are the top 35 (5).

All tests on the datasets presented in the preceding part were performed on an Intel Core T M i7-2630QM CPU running on 2.00 GHz × 8 with 8 GB main memory and Ubuntu 16.04 LTS. We investigated a number of support levels for each dataset and measured the associated execution times (shown in Figures 3, 5, 8, 10, 12, 14, 16, 18), as well as the number of retrieved patterns (shown in Figures 4, 6, 9, 11, 13, 15, 17, 19). In these figures, (N It. X M Tr.) represents the number of items (N) and transactions (M) inside the dataset.