Odhiambo Dickson

Owuor
email: dowuor@strathmore.edu

Thomas Runkler
email: thomas.runkler@siemens.com

Anne Laurent
email: anne.laurent@umontpellier.fr

A Metaheuristic Approach for Mining Gradual Patterns

Keywords: Genetic Algorithm, Local Search, Particle Swarm Optimization, Search Space, Swarm Intelligence, Random Search

Swarm intelligence is a discipline that studies the collective behavior that is produced by local interactions of a group of individuals with each other and with their environment. In Computer Science domain, numerous swarm intelligence techniques are applied to optimization problems that seek to efficiently find best solutions within a search space. Gradual pattern mining is another Computer Science field that could benefit from the efficiency of swarm based optimization techniques in the task of finding gradual patterns from a huge search space. A gradual pattern is a rule-based correlation that describes the gradual relationship among the attributes of a data set. For example, given attributes {G, H} of a data set a gradual pattern may take the form: "the less G, the more H" (simply denoted as {G ↓ , H ↑ }). In this paper, we propose a numeric encoding for gradual pattern candidates that we use to define an effective search space. In addition, we present a systematic study of several meta-heuristic optimization techniques as efficient solutions to the problem of finding gradual patterns using our search space.

Introduction

Swarm-based optimization algorithms, most of which mimic the collective intelligence of groups of simple agents, have demonstrated excellent efficiency in solving many optimization problems [START_REF] Wahab | A comprehensive review of swarm optimization algorithms[END_REF]. According to [START_REF] Abdel-Basset | Chapter 10 -metaheuristic algorithms: A comprehensive review[END_REF], swarm-based optimization algorithms belong to the subcategory of metaphor-based algorithms in the class of metaheuristic algorithms.

Metaheuristic algorithms are computational intelligence models that are used to solve complex optimization problems. In this paper, we focus on the task of generating gradual pattern candidates as an optimization problem. Gradual pattern mining is a data mining field in Computer Science that deals with describing attributes/variables/features of data sets using rules such as: "the higher the temperature, the less vehicle traffic" . We provide a detailed description of gradual pattern mining in Section 2.

Gradual pattern (GP) mining has many applications especially in domains that seek to find correlational knowledge about variables of a data set. For instance, in [START_REF] Fan | Discovering gradual patterns in building operations for improving building energy efficiency[END_REF], GP mining is applied in the discovery of the gradual relationship between numerical building variables in order to improve building efficiency.

One key challenge experienced in GP mining is in the task of identifying candidate rules. This involves combining different kinds of variations (increasing and decreasing) for each rule that correlates two or more variables [START_REF] Jorio | Fast extraction of gradual association rules: A heuristic based method[END_REF][START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF].

However, the task of identifying these candidates may be modelled into a search space problem onto which metaheuristic algorithms may be applied.

In this paper, we propose a search space such that each point is a numeric digit that encodes a GP candidate. Our experiment results show that our numeric encoding produces a lean search space metaheuristic algorithms to explore. The results also rank the computational efficiency of these algorithms in the task of finding best GP candidates from the search space.

The main contributions of this study are described as follows:

• We propose a numeric encoding that allows us to build a lean search space for GP candidates.

• We develop metaheuristic algorithms and compare their performances in exploring search spaces based on our numeric encoding and those based on other encodings.

Background

In Computer Science, a search space may be described as "an expanse that is defined by the set of all feasible solutions through which an algorithm may iterate" [START_REF] Obitko | Visualization of genetic algorithms in a learning environment[END_REF][START_REF] Patel | Analysis of search space in the domain of swarm intelligence[END_REF]. In GP mining, a search space (known to be a lattice) holds all possible candidates that may be validated to be relevant GPs.

The subject of mining GPs (also referred to as gradual rules) has been studied by many researchers. To begin with, there exists different notions of gradual rules. Of particular interest, is the notion of applying Rescher-Gaines implication in order to measure gradualness. For instance, given two attributes A 1 and A 2 , fuzzy sets M and N defined on A 1 and A 2 respectively. If M (A 1 ) be the membership degree of A 1 in M , then the rule can be expresses as "A 1 is in M implies A 2 is in N ". In such expressions, we use Rescher-Gaines implication:

A 1 → RG A 2 =      1 if M (A 1 ) ≤ N (A 2 )
0 else [START_REF] Wahab | A comprehensive review of swarm optimization algorithms[END_REF] Starting from the above notions, [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF] formalizes 2 main kinds of gradual rules of the form "the more/less A 1 is in M , the more/less A 2 is in N ". The first kind (known as pure gradual rules), verifies a rule by evaluating properties between individual objects. The second kind (known as gradual dependence) verifies a rule by comparing the properties between objects. In this paper, we deal with pure gradual rules.

For the purpose of facilitating comprehension of this paper, we use a sample data set with 3 attributes and 4 objects or tuples (as shown in Table 1) to introduce GP mining. For instance, using these 3 attributes {age, sessions, marks} we may formulate approximately 20 GP candidates like {age ↑ , sessions ↓ }, {sessions ↓ , marks ↑ }, {age ↑ , sessions ↓ , marks ↑ } among others. To clarify, only GP candidates whose computed frequency support exceed a specified user-defined threshold may be verified as relevant GPs [START_REF] Laurent | Graank: Exploiting rank correlations for extracting gradual itemsets[END_REF][START_REF] Owuor | Efficiently mining large gradual patterns using chunked storage layout[END_REF]. Generally, frequency support may be defined as: "the proportion of ordered objects in a data set that verify a particular GP". For instance, the GP candidate {sessions ↑ , marks ↑ } is verified by the first 3 objects (out of the 4 objects) of the data set (shown in Table 1) if they are taken in ascending order. This is due to the fact that the object values of the attributes {sessions, marks} subsequently increase in the first 3 objects with the exception of the fourth object values. Therefore, in this case the frequency support may be computed to be 3/4 or 0.75. In view of this example, it is noticeable that the number of GP candidates is directly proportional to the number of a data set's attributes. According to [START_REF] Jorio | Fast extraction of gradual association rules: A heuristic based method[END_REF][START_REF] Owuor | Efficiently mining large gradual patterns using chunked storage layout[END_REF] (in GP mining), deterministic algorithms that have to find and validate each GP candidate are computationally overwhelmed when applied on data sets with large attribute sizes.

However, an effective search space S gp may be defined such that every point in the search space represents a possible GP candidate. In addition, it is possible to iterate through the search space using a non-deterministic algorithm to find candidates which are validated by computing their frequency support.

Definitions and Notations

We give some definitions of gradual patterns as provided in [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF][START_REF] Laurent | Graank: Exploiting rank correlations for extracting gradual itemsets[END_REF][START_REF] Owuor | Mining fuzzy-temporal gradual patterns[END_REF][START_REF] Owuor | Mining fuzzy temporal gradual emerging patterns[END_REF][START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF].

For example, let D be a data set with attributes {age, sessions, marks} and objects {obj1, obj2, obj3, obj4} (as shown in Table 2). Definition 1.1. (Gradual Item). A gradual item is a pair at v : where at is an attribute and v is a gradual variation such that v ∈ {↑, ↓}. ↑ denotes an increasing variation and ↓ denotes a decreasing variation.

For example, age ↑ can be interpreted as "the higher the age".

Definition 1.2. (Gradual Pattern).

A gradual pattern GP is a set of gradual items such that GP = {at v 1 , ..., at v n }. For example, {age ↑ , sessions ↓ , marks ↑ } is a GP that can be interpreted as "the higher the age, the less session numbers, the higher the marks obtained."

The quality of a gradual item or gradual pattern is measured by its frequency support. The frequency support of a gradual pattern sup(GP ) may be defined as: "the proportion of object couples that respect the gradual variations given collectively by all the items in the pattern". For instance, let A be an attribute of data set D which has a total of k objects and o be an object in D such that A(o) denotes the value A takes for o, (o, o ) denotes an object pair in D (which is a transaction data set derived from D and it holds the set of all object pair combinations). The gradual item [START_REF] Laurent | Graank: Exploiting rank correlations for extracting gradual itemsets[END_REF][START_REF] Clémentin | A novel algorithm for extracting frequent gradual patterns[END_REF].

A ↓ holds if ∀(o, o ) ∈ D , A(o) > A(o )
Therefore, support of a GP can be defined by the formula that follows.

sup(GP ) = 1 |D | • |{(o, o ) ∈ D /A(o) * A(o )}|, (2)
where * ∈ {<, >}. Given a user-specified threshold σ, a GP is said to be frequent if:

sup(GP ) ≥ σ. (3)
For example, in Table 2, the gradual item {sessions ↑ } and the GP {age ↑ , sessions ↑ } are both respected by 3/6 object pairs (i.e. {(obj1, obj2), (obj1, obj3), (obj2, obj3)}). Therefore, the frequency support is 0.5 in both scenarios.

We adopt the following notation in the rest of the paper. Let X = {gp 1 , gp The remainder of the paper is organized as follows: we review related literature in Section 3; we define a lean search space for GP candidates built on top of our numeric encoding in Section 4; we describe a meta-heuristic approach for the problem of mining gradual patterns in Section 5; we present our experimental study in Section 6; finally, we conclude and give future directions concerning the study in Section 7.

Review of Literature

Many approaches for efficiently mining GPs have been proposed by numerous researchers. [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF] describes an Apriori-based algorithm for extracting gradual dependency from data sets using different classes of fuzzy sets. However, according to [START_REF] Jorio | Fast extraction of gradual association rules: A heuristic based method[END_REF], this approach is limited to extracting GPs of length 3. Instead of using object pairs to verify GPs, [START_REF] Jorio | Fast extraction of gradual association rules: A heuristic based method[END_REF] proposes an ordered data set as an alternative.

In reality, none of the approaches proposed by [START_REF] Jorio | Fast extraction of gradual association rules: A heuristic based method[END_REF] and [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF] consider the problem of reducing the number of GP candidates that an algorithm has to verify.

In view of Equation 2 and 3, it is easy to confirm that the most computationally intensive task in GP mining involves computing frequency support in order to verify/validate GP candidates by comparing their support values against a user-specified threshold.

In fact, the higher the number of GP candidates to be validated, the more computational resources required by a GP mining algorithm [START_REF] Owuor | Mining fuzzy temporal gradual emerging patterns[END_REF][START_REF] Clémentin | A novel algorithm for extracting frequent gradual patterns[END_REF][START_REF] Negrevergne | Paraminer: a generic pattern mining algorithm for multi-core architectures[END_REF][START_REF] Owuor | Gradual pattern mining tool on cloud[END_REF].

Meta-heuristic based algorithms may be harnessed to accomplish the task of efficiently searching for best GP candidates without having to evaluate all the candidates in the search space. In this study, we investigate LS, RS, GA, PSO algorithms for this task.

Random search (also known as pure random search) algorithms are stochastic algorithms that select and evaluate candidates from a search space independently, and the objective function has no effect on the strategy used to pick the next candidate (i.e. each candidate is selected out of pure randomness) [START_REF] Solis | Minimization by random search techniques[END_REF][START_REF] Zabinsky | Pure Random Search and Pure Adaptive Search[END_REF][START_REF] Zabinsky | Random Search Algorithms[END_REF]. RS is a simple and effective approach to frequent pattern mining problems. Therefore, it is surprising how scarcely it has been applied to the problem of searching for frequent pattern candidates.

Local search (also known as neighborhood search) is a meta-heuristic which tries to find optimal solutions by considering the neighbors of current solutions.

In a typical combinatorial optimization problem, a search space is defined by a finite set of feasible candidates, each candidate has a cost, and the goal is to find a candidate with the minimum (or maximum) cost [START_REF] Fränti | Randomised local search algorithm for the clustering problem[END_REF][START_REF] Hoos | Stochastic local search: Foundations and applications[END_REF][START_REF] Ishibuchi | Multi-objective genetic local search algorithm[END_REF][START_REF] Johnson | How easy is local search?[END_REF]. In the realm of pattern mining, a research study conducted by [START_REF] Hossain | Stochastic local search for pattern set mining[END_REF] show that LS algorithms are computationally more efficient than systematic search methods in searching for good quality frequent patterns.

Genetic algorithm is an evolutionary algorithm inspired by natural selection systems. The main operators of GA are selection, crossover and mutation:

where, selection operation allows GA to sample the fittest candidates from the search space (or population), crossover and mutation operations allow strong GA candidates to mate and produce stronger (or better) candidates [START_REF] Holland | Adaptation in natural and artificial systems[END_REF][START_REF] Koza | Genetic programming: on the programming of computers by means of natural selection[END_REF][START_REF] Mirjalili | Genetic Algorithm[END_REF].

In the realm of frequent pattern mining, research studies conducted by [START_REF] Kabir | Comparative analysis of genetic based approach and apriori algorithm for mining maximal frequent item sets[END_REF] and [START_REF] Saravanan | A novel approach for sequential pattern mining by using genetic algorithm[END_REF] prove that GA-based approaches surpus their classical counterparts in computational performance.

Particle swarm optimization is a swarm based optimization technique (originally proposed by [START_REF] Kennedy | Particle swarm optimization[END_REF]) that is inspired by the analogy of social interaction and communication (i.e. fish schooling or bird flocking). PSO simulates the movements of swarms in order to iteratively optimize a combinatorial optimization problem [START_REF] Rajamohana | Hybrid approach of improved binary particle swarm optimization and shuffled frog leaping for feature selection[END_REF]. In the realm of frequent pattern mining, research studies con-ducted by [START_REF] Mishra | Particle swarm optimization based fuzzy frequent pattern mining from gene expression data[END_REF] and [START_REF] Shruti | Fuzzy frequent pattern mining from gene expression data using dynamic multi-swarm particle swarm optimization[END_REF] Recall that every ant in each group is attracted to the path with the highest intensity of pheromone. Initially, the ants select paths haphazardly; but, after a few iterations ants that select shortest paths (illustrated as darker) reach their destinations faster while depositing pheromones. Therefore, ants coming in the opposite direction will find these paths more attractive than the longer paths.

In the realm of GP mining, a research study conducted by [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF] proposes and describes an approach that applies an ant colony optimization (ACO) approach to efficiently search for GP candidates whose frequency support values exceed a user-specified threshold value. According to [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF][START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF][START_REF] Runkler | Ant colony optimization of clustering models[END_REF][START_REF] Stützle | Max-min ant system[END_REF], ACO-based approaches imitate the positive feedback reinforcement behavior of ants as they search for food to solve combinatorial optimization problems.

In [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF], an ACO variant called 'max-min ant system' (initially proposed by [START_REF] Stützle | Max-min ant system[END_REF]) is applied to the case GP mining. For instance given attributes {a, b, c} of a data set, a search space may be represented such that each point is a path that connects gradual items {a ↑ , a ↓ , b ↑ , b ↓ , c ↑ , c ↓ } as shown in Figure 1. Each path represents a GP candidate; therefore, the path that is most travelled by ants becomes the best GP candidate.

Additionally, the study conducted by [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF] implement a GA-based approach and a PSO-based approach that efficiently search for best GP candidates whose frequency support exceed a user-specified threshold value. For case of GA and PSO, [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF] proposes a bitmap encoding to represent each point of a search space as a combination of bits. For instance given attributes {a, b, c} of a data set, a search space may be represented such that each point or candidate is encoded as a (3 × 2) bitmap. Figure 2 illustrates a bitmap encoding of GP candidate In the final analysis, [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF] presents experimental results which show that ACObased, GA-based and PSO-based techniques computationally out-perform traditional techniques in mining for GPs. Unlike the traditional techniques, these meta-heuristic based techniques do not need to evaluate all possible GP candidates in the search space.

{a ↑ , b ↓ , c ↑ }. ↑ ↓ {c} 1 0 {b} 0 1 {a} 1 0

Constructing a Numeric Search Space for GP Candidates

In this section, we propose and describe a numeric encoding for GP candidates in Section 4.1; we propose and describe how these encodings may be used to define a search space with lower and upper bounds in Section 4.2; and, we describe an objective function that computes the fitness (or cost) of any selected GP candidate in Section 4.3.

A Numeric Encoding for GP Candidates

Generally, the task of extracting GPs begins with generating GP candidates.

This step is followed by that of computing the support of the candidates (using the formulas described in Section 2) in order to test if they are frequent

or not [START_REF] Owuor | Efficiently mining large gradual patterns using chunked storage layout[END_REF]. Depending on the number of attributes in a data set, the possible number of GP candidates may grow exponentially. This growth may easily computationally overwhelm those algorithms that test every possible GP candidate [START_REF] Owuor | Efficiently mining large gradual patterns using chunked storage layout[END_REF][START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF][START_REF] Clémentin | A novel algorithm for extracting frequent gradual patterns[END_REF]. 2. Where A denotes age, S denotes sessions and M denotes marks attributes of the data set in Table 2. Due to space constraints, omit GPs:

{} {A ↑ } {A ↓ } {S ↑ } {S ↓ } {M ↑ } {M ↓ } {A ↑ , S ↑ } {A ↑ , S ↓ } {A ↑ , M ↑ }{A ↑ , M ↓ } {A ↓ , S ↑ } {A ↓ , S ↓ } {A ↓ , M ↑ }{A ↓ , M ↓ }{S ↑ , M ↑ } {S ↑ , M ↓ } {S ↓ , M ↑ } {A ↑ , S ↑ , M ↑ } {A ↑ , S ↑ , M ↓ } {A ↑ , S ↓ , M ↑ } {A ↑ , S ↓ , M ↓ } {A ↓ , S ↑ , M ↑ } {A ↓ , S ↑ , M ↓ } {A ↓ , S ↓ , M ↑ }
{S ↓ , M ↓ } and A ↓ , S ↓ , M ↓ }.
In this paper, we propose and use meta-heuristic approaches (described in Section 5) to efficiently learn frequent GP candidates without testing all individuals in the search universe. In this section, we propose and demonstrate a numeric model that effectively encodes all possible GP candidates (of any given data set) in a search universe within an upper and a lower bound.

To begin with, we mention that a search space for GP candidates is made up of individuals that are formed by arranging a specific set of gradual items in different combinations; and, this set of gradual items is derived from the data set's attribute set. It is important to highlight that the complementary notion of GPs permits the existence of 2 gradual items for every attribute [START_REF] Clémentin | A novel algorithm for extracting frequent gradual patterns[END_REF].

For instance, the data set in Table 2 with the attribute set {age, sessions, marks}, allows for 6 gradual items to exist: {age ↑ , age ↓ , sessions ↑ , sessions ↓ , marks ↑ , marks ↓ }. And, Figure 3 is a lattice diagram (or search space) of all possible candidates that may be formed from these 6 gradual items.

Different from the lattice diagram representation, we propose a numeric model that may be used to encode each GP candidate in the search universe as a bit vector (or bit array/string or bit set) as illustrated in Table 3. denotes sessions and M denotes marks attributes of the data set in Table 2.

Bit vector GP

(bgp) Candidate

101000 {A ↑ , S ↑ } 100100 {A ↑ , S ↓ } 100010 {A ↑ , M ↑ } 100001 {A ↑ , M ↓ } 011000 {A ↓ , S ↑ } 010100 {A ↓ , S ↓ } 010010 {A ↓ , M ↑ } 010001 {A ↓ , M ↓ } 001010 {S ↑ , M ↑ } 001001 {S ↑ , M ↓ } (a)
Bit vector GP

(bgp) Candidate 000110 {S ↓ , M ↑ } 000101 {S ↓ , M ↓ } 101010 {A ↑ , S ↑ , M ↑ } 101001 {A ↑ , S ↑ , M ↓ } 100110 {A ↑ , S ↓ , M ↑ } 100101 {A ↑ , S ↓ , M ↓ } 011010 {A ↓ , S ↑ , M ↑ } 011001 {A ↓ , S ↑ , M ↓ } 010110 {A ↓ , S ↓ , M ↑ } 010101 {A ↓ , S ↓ , M ↓ } (b)
To put it another way, it is possible to compute the length of a bit vector whose individual bits may be toggled in order to provide different encodings for different GP candidates in the search universe, as illustrated in Definition 3.1. in the search universe as gradual bit vectors (as shown in Table 3).

Defining a Search Space Based on Numeric Encoding

With attention to the numeric encoding (described in Definition 3.1), it is easy to observe that gradual bit vectors may also represent binary numbers (in the base-2 numeral/positional system) within a specific range [START_REF] Harris | Digital design and computer architecture[END_REF][START_REF] O'regan | Binary Number System[END_REF]. A lower bound and an upper bound for this range may easily be defined by the minimum and the maximum bit vectors respectively.

For example, the lower and upper bounds of gradual bit vectors of size 6 may be defined by the values 000000 and 111111 respectively. Notably, (in Table 3) all gradual bit vectors are located within the bounds of these two values.

A part from the binary numeral system, there exist numerous positional numeral systems that may be used in computational arithmetic. The conventional decimal numeral system (which uses 10 digits 0, 1, .., 9) is one of most popular number systems in use among various research domains [START_REF] O'regan | Binary Number System[END_REF]. We can convert each gradual bit vector into its decimal value and hexadecimal value equivalent.

For example, the bit vectors in Table 3 may be converted into their decimal value equivalents as shown in Table 4. We observe that all positions of the decimal values (that represent the gradual bit vector) lie within the bounds Therefore, we may define a GP search space based on numeric encoding as:

"an interval S gp of integer numbers within the bounds of a and b such that, for any x ∈ S gp , a ≤ x ≤ b".

Our numeric encoding simplifies the computation of determining the values of bounds a and b respectively. In the case of lower bound a: it is easy to verify that for any data set with at least 2 attributes, the smallest decimal value that corresponds to valid bit vector is 5. For this reason, it is true that a = 5 always.

In the case of upper bound b, we propose a different approach for computing its value based on the size of the attribute set of a data set. Using Table 4, we observe that the largest value of a bit vector representing a 2-attribute data set is 1010, and that of a 3-attribute data set is 101010, and that of a 4-attribute data set is 10101010, and so forth. Therefore, b can be computed from the sum of odd binary digits times their power of 2 (2 n ) as shown in Equation ( 4).

b = |AT | i=1 2 2i-1 , (4)
where |AT | is the number of attributes. Therefore, we may define S gp as:

S gp = x ∈ Z 5 ≤ x ≤ |AT | i=1 2 2i-1 . (5)
It is interesting to note that the search space proposed in [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF] is based on

[|AT | × 2]
binary encoding. Therefore, its dimensions are huge compared to our proposed search space. For example, given 3 attributes, the search space based on binary encoding allows algorithms to traverse almost (2 6 = 64) possible candidate combinations, while our proposed search space allows algorithms to traverse only (42-5 = 37) candidates. The numeric encoding reduces the search space by almost half of that which was proposed in [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF].

However, not all gradual bit vectors correspond to valid GP candidates.

For example, using the data set in Table 2, 001111 is an invalid GP candidate since it represents conflicting gradual items (i.e., {sessions ↑ , sessions ↑ , marks ↑ , marks ↑ }). In such scenarios, GP algorithms ignore such candidates.

Our proposed numeric search space (although to a lesser amount than the binary search space) still includes some invalid GPs. Using the lattice diagram in Figure 3, we learn that a data set with 3 attributes yields only 20 valid GP candidates. Therefore, our search space contains 17 invalid GP candidates that should be ignored by mining algorithms.

Computing Candidates' Fitness

Each gradual bit vector should be associated with a fitness/cost value. The fitness value should allow these algorithms to learn (using a probabilistic search) which gradual bit vector encodes the GP candidate with the highest frequency support (described in Section 2).

In this paper, we state that the gradual bit vector with the smallest fitness (or cost) value is the best candidate. Given this point, we observe that there exists a relationship between frequency support of a candidate and fitness. Therefore, a slight modification of Equation 2 may yield an objective function for determining the fitness of GP candidates. Therefore, the objective function may be defined by the inverse of the concordant object pairs count as shown in Equation 6.

f itness(b gp ) = 1 |{∀(o, o ) ∈ D : A(o) * A(o )}| . ( 6
)
For example, given the data set in Table 2, we construct some gradual bit vectors and compute their decimal value equivalents and their fitness values as shown in Table 5. {(obj1, obj2), (obj1, obj3), (obj1, obj4), (obj2, obj3)}. Therefore, the support is 0.67 (see Equation 2) and the fitness value is 0.25 (see Equation 6). As shown in Table 5, the GP {A ↑ , S ↑ } has the lowest fitness value and highest support in comparison to GPs {A ↑ , M ↓ } and {A ↓ , S ↑ , M ↑ }.

Metaheuristic Algorithms for GP Extraction

In this section, we propose 4 meta-heuristic algorithms (i.e., LS, RS, GA, PSO) to the problem of finding best GP from the search space proposed in Section 4.3.

LS-GRAD and RS-GRAD Algorithms

We propose RS-GRAD algorithm for GP extraction and it is based on a random search algorithm which is a technique whose optimization strategy is based on a purely stochastic process. In every iteration, random search algorithms are designed to modify the current solution by a random factor [START_REF] Zabinsky | Pure Random Search and Pure Adaptive Search[END_REF].

Similarly, we propose LS-GRAD algorithm for GP extraction and it is based on a stochastic hill climbing algorithm. Hill climbing technique is an iterative technique that starts from an arbitrary solution and attempts to find a better neighboring solution. A hyper-parameter known as 'step-size' controls how far the search for a neighboring solution is allowed to go [START_REF] Nolle | On a hill-climbing algorithm with adaptive step size: Towards a control parameter-less black-box optimisation algorithm[END_REF].

The main steps of LS-GRAD algorithm and RS-GRAD algorithm are illustrated in Algs. 1(a) and 1(b) respectively.

LS-GRAD Algorithm:

best GP ← ∅ bestcost ← ∞ Sgp ← def ineSpace(AT ) REPEAT T times : bgp ← neighborSearch(Sgp, bgp, step) cost ← objectiveF unction(bgp) IF (cost ≤ bestcost) THEN : bestcost ← cost best GP ← decodeGP (bgp) (a)
RS-GRAD Algorithm:

best GP ← ∅ bestcost ← ∞ Sgp ← def ineSpace(AT )
REPEAT T times : As shown in Alg. 1(a), LS-GRAD algorithm defines a search space S gp such that each point is encoded as numeric digit that represents a GP candidate and it iterates T times. In each iteration, the algorithm:

• finds a neighbor of the current selected bit vector candidate b gp in search space S gp and this neighbor becomes the selected candidate (using neighbor Search() function);

• evaluates fitness of the selected candidate (using objectiveF unction()).

As shown in Alg. 1(b), RS-GRAD algorithm defines a search space S gp such that each point is encoded as numeric digit that represents a GP candidate and it iterates T times. In each iteration, the algorithm:

• randomly selects a bit vector candidate from search space S gp (using selectRandomBitV ector() function);

• evaluates fitness of the selected candidate (using objectiveF unction()).

Computational Complexity of LS-GRAD and RS-GRAD

We use big-O notation [START_REF] Cormen | Introduction to algorithms[END_REF][START_REF] Vaz | Automated big-o analysis of algorithms[END_REF] to analyze the computational complexity of LS-GRAD and RS-GRAD algorithms. For every candidate that is selected, both LS-GRAD and RS-GRAD algorithms compute fitness using the objective F unction() (or fitness function described in Section 4.3). We recall that the formula proposed for computing the fitness function (see Equation 6) is a variant of the formula used for computing frequency support (see Equation 2). Therefore, the computational complexities of implementing these two functions are fairly similar. According to [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF], given a data set with a attributes and n objects, the task of computing the fitness of a GP candidate composed of k gradual items

(where k ≤ a) has a complexity of O(k • n 2 ).
Another key point is that in both LS-GRAD and RS-GRAD algorithms, the tasks of implementing functions like def ineSpace(), decodeGP (), neighbor Search() and selectRandomBitV ector() have small and almost constant computational complexities relative to the task of the objectiveF unction(). Therefore, it is acceptable to simplify the big-O analysis to focusing on computationally intensive tasks (i.e. objectiveF unction()). Given these points, if both LS-GRAD and RS-GRAD algorithms iterate T times, their computational complexities are relatively of the same equivalence -that is O(T • k • n 2 ).

GA-GRAD and PSO-GRAD Algorithms

We propose GA-GRAD algorithm for GP extraction and it is built on top of GA which is an optimization technique that is inspired by Darwin's theory about evolution [START_REF] Obitko | Visualization of genetic algorithms in a learning environment[END_REF]. GA techniques are initiated with a population of solutions (also called chromosomes). Existing solutions are selected according to their fitness and they mate to reproduce offsprings whose fitnesses are better.

Through this reproduction operation GA techniques efficiently find best solutions to combinatorial optimization problems. Specifically, GA uses the following operators in order to improve the fitness of the offsprings:

• Crossover: passing of good genes to next generation. γ denotes the parameter that controls crossover rate.

• Mutation: random changes in genes during crossover. µ denotes the parameter that controls mutation rate.

Similarly we propose PSO-GRAD algorithm for GP extraction and it is built on top of PSO which is an optimization technique that is inspired by collective behavior and movements of swarms (especially as they search for food). PSO techniques are initialized with a population of particles and in every iteration each particle moves to a new position whose cost/fitness is better than its current position [START_REF] Mishra | Particle swarm optimization based fuzzy frequent pattern mining from gene expression data[END_REF].

A PSO algorithm performs a constant search for best position in a search space. Particles are generated and they are randomly assigned positions from a uniform distribution with the search space; the algorithm moves particles with a certain calculated velocity in every iteration. Personal best position (p i and global best position (gbest) are the best position visited so-far by the i-th particle and the best position visited so far by any particle in the swarm [START_REF] Piotrowski | Population size in particle swarm optimization[END_REF].

PSO uses the following operators:

• Current direction/velocity: determines the movement of each particle.

• Personal best position (p i ) and cognitive component (coef p ): coef p coefficient gives the importance of personal best value.

• Team/global best position (gbest) and social component (coef g ): coef g co-efficient gives the importance of global best value.

The main steps of GA-GRAD algorithm and PSO-GRAD algorithm are illustrated in Algs. 2(a) and 2(b) respectively.

GA-GRAD Algorithm:

best GP ← ∅ bestcost ← ∞ Sgp ← def ineSpace(AT ) pop ← initializeP op(npop, Sgp)
REPEAT T times :

C ← f indBestCandidates(pop) Cnew ← crossover(C, γ)
For bgp in Cnew DO :

pop ← pop + bgp cost ← objectiveF unction(bgp) IF (cost ≤ bestcost) THEN : bestcost ← cost best GP ← decodeGP (bgp) bgp ← mutate(bgp, µ) pop ← pop + bgp cost ← objectiveF unction(bgp) IF (cost ≤ bestcost) THEN : bestcost ← cost best GP ← decodeGP (bgp) (a)
PSO-GRAD Algorithm:

best GP ← ∅ bestcost ← ∞ Sgp ← def ineSpace(AT ) pop ← initializeP op(nparticles, Sgp) pbestpop ← pop gbestc ← pbestpop[0]
REPEAT T times :

For i in range nparticles DO :

costi ← objectiveF unction(pop[i]) costp ← objectiveF unction(pbestpop[i])
costg ← objectiveF unction(gbestc)

IF (costi ≤ costp) THEN : pbestpop[i] ← pop[i] IF (costi ≤ costg) THEN : gbestc ← pop[i] IF (costg ≤ bestcost) THEN : bestcost ← costg best GP ← decodeGP (gbestc)
For i in range nparticles DO : As shown in Alg. 2(a), GA-GRAD algorithm is initialized to a population pop having npop candidates and each candidate is a gradual bit vector b gp within search space S gp . The algorithm iterates T times and in each iteration it:

pop[i] ← moveP
• selects 2 of the best candidates from population pop (using f indBest Candidates() function);

• performs a crossover function using these 2 candidates in order to reproduce 2 offsprings (using crossover() function at a rate of γ);

• evaluates the fitness of the offsprings (using objectiveF unction());

• mutates each offspring's bit vector (using mutate() function at a rate of µ) and evaluates their fitness;

• adds the offsprings to population pop.

As shown in Alg. 2(b), PSO-GRAD algorithm is initialized to a population pop having n particles and each particle's position represents a gradual bit vector within search space S gp . In addition, a global best particle gbest c is initialized.

The algorithm iterates T times and in each iteration, it:

• evaluates the fitness of all particles' positions in the population and the fitness of the global best particle's position (using objectiveF unction());

• for each particle's position if the fitness value is lower than the fitness value of its personal best position in history, set the personal best position to this position;

• replace the global best particle position with any particle position whose fitness value is lower than the laters;

• moves each particle by a velocity vel towards its personal best at a rate of coef p and towards the global best particle at a rate of coef g .

Computational Complexity of GA-GRAD and PSO-GRAD

We use big-O notation [START_REF] Cormen | Introduction to algorithms[END_REF][START_REF] Vaz | Automated big-o analysis of algorithms[END_REF] to analyze the computational complexity of GA-GRAD and PSO-GRAD algorithms. Similar to LS-GRAD and RS-GRAD algorithms, we take the computational complexity of a single objectiveF unction() (implemented by GA-GRAD and PSO-GRAD algorithms) as equivalent to O(k• n 2 ). Again, comparable to GA-GRAD and PSO-GRAD algorithms, we ignore functions whose computational complexities are small and almost constant relative to the objectiveF unction().

GA-GRAD algorithm is initialized to a population of npop candidates where only 2 candidates are selected in every iteration. Again, the algorithm evaluates the fitness of 2 crossed offsprings and 2 mutated offsprings in every iteration.

Therefore, in 1 iteration the computational complexity of GA-GRAD algorithm

is equivalent to O(4 • k • n 2 ) and in T iterations it is equivalent to O(4 • T • k • n 2 ) 20
PSO-GRAD algorithm is initialized to a population of n particles. In each iteration, the algorithm evaluates the fitness of all these particles together with the fitness of their historical personal best and global best particle. Therefore, in 1 iteration the computational complexity of PSO-GRAD algorithm is equivalent

to O{(2n + 1) • k • n 2 } and in T iterations it is equivalent to O{(2n + 1) • T • k • n 2 }.

Experiments

In this section, we present an experimental study of the computational performance of our algorithms. Specifically, we analyze the performance and behavior of the algorithms when exploring search spaces based on either a bitmap encoding (initially proposed in [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF]) or a numeric encoding (proposed in Section 4). The aim of this experiment is to establish which search space is simpler for meta-heuristic algorithms.

In addition to this, we compare the computational performance of the metaheuristic algorithms in mining GPs. All experiments were conducted on a HPC (High Performance Computing) platform Meso@LR 1 . We used one node made up of 14 cores and 128GB of RAM.

Source Code

The Python source code of our algorithms is available at the GitHub repository https://github.com/owuordickson/swarm_gp.git. The Python package for installing these algorithms is available at the PyPi repository through this link: https://pypi.org/project/so4gp/.

Data Set Description

Table 6 briefly describes the features of the data sets used in our experiments for evaluating the performance of our algorithms. All these data sets are numeric data set. We performed a data cleaning task (on all the data sets) that involved omitting objects with one or more missing values and omitting attributes whose The HCV data set is a data set that contains laboratory values of blood donors of healthy individuals and individuals infected with Hepatitis C or Fibrosis or Cirrhosis together with demographic values (i.e. age, sex) [START_REF] Hoffmann | Using machine learning techniques to generate laboratory diagnostic pathways-a case study[END_REF]. The CPX data set is a spatio-temporal data set containing county-level records of weekly chickenpox cases in Hungary between the years of 2005 and 2015 [START_REF] Rozemberczki | Chickenpox cases in hungary: a benchmark dataset for spatiotemporal signal processing with graph neural networks[END_REF].

The C2K data set is a data set that holds records of Cargo 2000 airfreight tracking and events for a period of 5 months. The C2K data set has 98 attributes and 3942 objects (some with missing values) [START_REF] Metzger | Comparing and combining predictive business process monitoring techniques[END_REF]. The AQY data set is a data set that contains records of a gas multi-sensor device (i.e. hourly averages of gas concentrations) deployed on a field in an Italian city [START_REF] Vito | On field calibration of an electronic nose for benzene estimation in an urban pollution monitoring scenario[END_REF].

The BCR data set is composed of 10 predictors and a binary variable indicating the presence or absence of breast cancer. The predictors are recordings of anthropometric data gathered from the routine blood analysis of 116 participants [START_REF] Patrício | Using resistin, glucose, age and bmi to predict the presence of breast cancer[END_REF]. The HPC data set describes the electric power consumption in one household (located in Sceaux, France) between 2006 and 2010 [START_REF] Dua | UCI machine learning repository[END_REF].

The APS data set holds data of the Air Pressure System (APS) collected from heavy Scania trucks in their daily usage [START_REF] Gondek | Prediction of failures in the air pressure system of scania trucks using a random forest and feature engineering[END_REF]. The DIR and OMD data sets are obtained from OREMES's data portal3 that recorded swell sensor signals of 4 buoys near the coast of the Languedoc-Roussillon region in France between 2012 and 2019 [START_REF] Bouchette | OREME: the coastline observation system[END_REF].

Parameter Tuning

In order to obtain the highest efficiency from GA-GRAD, PSO-GRAD and LS-GRAD algorithms, careful tuning of their respective parameters is required.

We utilize a Bayesian optimization approach proposed by [START_REF] Snoek | Practical bayesian optimization of machine learning algorithms[END_REF] to achieve this task. Firstly, we determine the appropriate maximum value of iterations T (see Section 5) for all the algorithms when applied to all the data sets described in Section 6.2. As can be seen in Figure 4, we observe that none of the algorithms exceeds 10 iterations when applied on any data set. Therefore, we set the maximum value of iterations to 20 in order to how smoothly each algorithm's plot settles in Section 6.4. Secondly, for each algorithm we determine the optimum values of their respective parameters when applied on different data sets by using the automated Bayesian optimization approach [START_REF] Snoek | Practical bayesian optimization of machine learning algorithms[END_REF]. Figures 5,[START_REF] Obitko | Visualization of genetic algorithms in a learning environment[END_REF][START_REF] Patel | Analysis of search space in the domain of swarm intelligence[END_REF] show a plot of specific parameters against different data sets for GA-GRAD, PSO-GRAD and LS-GRAD algorithms respectively. From results displayed in these figures, it is can be de- For this reason, in order to reach maximum the efficiency of each our algorithms in our experimental analysis presented in Section 6.4, we tune their respective parameters to different values according to the data set involved.

Experiment Results

In this section, we present our experiment results which reveal the computational behavior of LS-GRAD, RS-GRAD, GA-GRAD, PSO-GRAD algorithms when applied to the data sets described in Section 6. In Section 6.4.1, we perform a Wilcoxon test to determine which search space better suites our algorithms. We conduct 2 experiments on the 4 algorithms: one using bitmap encoding to construct search spaces in and, another using numeric encoding to construct search spaces.

In Section 6.4.2, we compare the distribution of valid GPs and invalid GPs extracted from various data sets by our algorithms using the numeric-based search space against the bitmap-based search space. In Section 6.4.3, we conduct an experiment that compares the performance of our algorithms using the numeric-based search space against other existing GP mining algorithms

Experiment 1: Wilcoxon Test on Search Spaces

The Wilcoxon test is a non-parametric measure that compares the differences between at most 2 paired groups of data [START_REF] Carrasco | Recent trends in the use of statistical tests for comparing swarm and evolutionary computing algorithms: Practical guidelines and a critical review[END_REF]. In this study, we evaluate the effect of different search spaces (i.e., numeric-based and bitmap-based) on our algorithms' run-time durations in different data sets. The dependent variable is the run-time duration measured on a continuous scale. The Wilcoxon test uses the following null and alternative hypotheses:

• Null hypothesis (H 0 ): the mean run-time for each group is equal.

• Alternative hypothesis: (H a ): one group's mean run-time is different from the other. Table 7 shows the mean run-times for each algorithm on the numeric-based and bitmap-based search space. Using these values, the results of the Wilcoxon test are shown in Table 8. In Figures 8 and9, we observe that the distribution of GP candidates is almost uniformly spread across the entire numeric-based search space; while, data sets have large number of attributes in comparison to the other data sets;

this explains why the distribution of candidates diagonally cuts across the numeric search space. GA-GRAD algorithm does not find any valid GP using the bitmap-based search space from APS and C2K data sets. (as shown in Figure 16 (b)), with the exception of AcoGRAD and GRAANK, all the other algorithms consume almost the same amount of memory. However, GRAANK's memory consumption grows exponentially when applied on APS and DIR data sets; thus, yielding a 'Memory Error'.

In Figure 17 In Figure 17 (b), we observe that GRAANK algorithm generates the most number of invalid GPs especially in C2K, AQY and HCV data sets. It is interesting to observe that our meta-heuristic algorithms generally generate very few invalid GPs. However, we also observe that GA-GRAD and PSO-GRAD algorithms generate slightly more number of invalid GPs than RS-GRAD and LS-GRAD algorithms.

6.5. Discussion of Results

Search Space

The Wilcoxon test results presented in Table 8 show low p-value (less than 0.05) for GA-GRAD and PSO-GRAD algorithms. This implies that there is sig-nificant differences in the run-time durations when these 2 algorithms are using the bitmap-based search space versus when they are using the numeric-based search space. From Table 7, we observe that al 4 algorithms have faster runtimes in most data sets when using the numeric-based search space. This makes the numeric-based search space more effective than its counterpart especially in the case of PSO-GRAD and GA-GRAD algorithms.

Again in Section 6.4.2, we observe that in the scatter plots of GA-GRAD and PSO-GRAD algorithms, GP candidates are more uniformly spread in the numeric-based search space than in the bitmap-based search space. This implies that the numeric-based search space allows these algorithms to explore more areas of the search space. Furthermore, these 2 algorithms do not find any valid GP from data sets with large numbers of attributes using the bitmapbased search space (i.e., APS and C2K). This may confirm the inefficacy of the bitmap-based search space especially when used on data sets with large numbers of data sets.

However, LS-GRAD and RS-GRAD algorithms seem to have almost similar distribution of GP candidates and little differences in run-time durations in both search spaces. In order to break the tie in favor of the numeric-based search spaces, we focus on the APS and C2K data sets. We observe in Figures 12 and 14 that both algorithms do not find any valid GP in the APS data set.

Although LS-GRAD algorithm finds valid GPs from C2K data set using both search spaces, it does so at the expense of a longer run-time in the bitmap-based search space (see Table 7). In fact, the run-time is almost 3 times as long in comparison to the numeric-based search space.

Execution Run-time

We observe that generally PSO-GRAD and GA-GRAD algorithms have longer run times than LS-GRAD and RS-GRAD algorithms. Specifically, PSO-GRAD followed by GA-GRAD algorithms have the longest run times in all the search spaces. This may be due to the fact that for every search iteration, PSO-GRAD and GA-GRAD algorithms evaluate more than one candidate GP.

Recall (from Section 5.2 and Section 5.1) that the task of evaluating GP candidates is the most computationally intensive task. Therefore, the more GP candidates that are evaluated by the objective function in every search iteration, the higher the computational complexity of the algorithm.

Extracted Patterns

We observe that generally GA-GRAD, PSO-GRAD and RS-GRAD algorithms extract more GPs than LS-GRAD algorithm. This phenomenon may be attributed to the fact PSO-GRAD and GA-GRAD algorithms generally evaluate higher number of candidates per every iteration in comparison to LS-GRAD and RS-GRAD algorithm, which in turn improves their chances of finding more valid GPs. However, we mention that our proposed metaheuristic algorithms are not guaranteed to find all frequent GPs in each data set. In reality, their searches only focus and converge to candidates in the search space that extract the GPs with the highest support (also referred to as best GPs), which is a subset of the frequent GPs.

In contrast, the classical GRAANK (initially proposed by [START_REF] Laurent | Graank: Exploiting rank correlations for extracting gradual itemsets[END_REF]) is a complete GP mining algorithm; in the sense that, it tests all possible candidates in the search space and extracts all the frequent GPs. In fact, our experiments reveal that GRAANK algorithm extracts the most number of valid GPs (especially in C2K data set); however, this comes with the downside of a higher run-time, an exponential growth of memory consumption (especially for APS and DIR data sets), and a generation of the huge numbers of invalid GPs.

Given these points, we recommend GRAANK algorithm as the suitable algorithm for extracting GPs from small data sets and, we recommend our proposed metaheuristic algorithms (i.e., GA-GRAD, PSO-GRAD, LS-GRAD and RS-GRAD) as the suitable algorithms for extracting GPs from large data sets (especially those with huge numbers of attributes).

Conclusion and Future Works

In this research study, we examine the problem of finding valid gradual patterns from a huge search space without having to test every candidate. We identify stochastic, evolutionary and swarm based optimization techniques as one of the efficient techniques for solving this problem. We define a lean search space based on numeric encoding that can easily be explored by these algorithms to find valid GPs.

In our experimental study, we compare the performances of LS-GRAD, RS-GRAD algorithms, GA-GRAD and PSO-GRAD algorithms in exploring gradual pattern search spaces based on bitmap encoding verses those based on numeric encoding. The experiment results reveal that all the algorithms find best gradual patterns at shorter run-times from search spaces built on numeric encoding.

This may imply that the numeric encoding builds search spaces that are leaner and easier to explore by meta-heuristic algorithms than the bitmap encoding.

In future, an even more effective encoding for gradual pattern candidates may be envisioned that allows gradual patterns to be extracted using machine learning techniques. It may also be interesting to explore the possibility of further reducing the search space of candidates so that algorithms generate even fewer invalid gradual patterns.

Figure 2 :

 2 Figure 2: An example of a bitmap encoding for a GP candidate {a ↑ , b ↓ , c ↑ }. Where ↑ denotes 'increasing' and ↓ denotes 'decreasing'.

Figure 3 :

 3 Figure 3: A lattice diagram showing the search space universe for GPs based on the attributes of Table 2. Where A denotes age, S denotes sessions and M denotes marks attributes of the

of 5 and 42 (

 42 which are the lower and the upper bound values respectively).

  bgp ← selectRandomBitV ector(Sgp) cost ← objectiveF unction(bgp) IF (cost ≤ bestcost) THEN : bestcost ← cost best GP ← decodeGP (bgp) (b) Alg. 1: (a) LS-GRAD algorithm, (b) RS-GRAD algorithm.

  article(velocity, pbestpop[i], gbestc, coefp, coefg) (b) Alg. 2: (a) GA-GRAD algorithm, (b) PSO-GRAD algorithm.

1

  https://meso-lr.umontpellier.fr objects are either non-numeric values or time-stamp values. All these data sets were retrieved from the UCI Machine Learning Repository 2[START_REF] Dua | UCI machine learning repository[END_REF].

Figure 4 :

 4 Figure 4: Determining the appropriate maximum value of iterations (T ). Where GaGRAD denotes GA-GRAD, PsoGRAD denotes PSO-GRAD, PlsGRAD denotes LS-GRAD, PrsGRAD denotes RS-GRAD.

Figure 5 :Figure 6 :

 56 Figure 5: GA-GRAD parameters: (a) initial parent population, (b) offspring proportion (pc) and crossover γ parameter, (c) mutation µ and σ parameters.

Figure 7 :

 7 Figure 7: LS-GRAD's step-size parameter.

2 .

 2 All experiments involve performing at least 3 repeated test runs on each algorithm and the results are a mean of the repeated test runs of each algorithm on each data set. A single test run allows each algorithm to execute 20 iterations (T = 20) in each search space. In every iteration, all the algorithms try to find the best GP candidate among those provided by each search space.

Figure 8 :

 8 Figure 8: GA-GRAD's candidates from APS, C2K, DIR and OMD data sets using numericbased and bitmap-based search spaces.

Figure 9 :

 9 Figure 9: GA-GRAD's candidates from AQY, HPC, HCV and CPX data sets.

Figure 12 :

 12 Figure 12: LS-GRAD's candidates from APS, C2K, DIR and OMD data sets using numericbased and bitmap-based search spaces.

Figure 13 :

 13 Figure 13: LS-GRAD's candidates from AQY, HPC, HCV and CPX data sets using numericbased and bitmap-based search spaces.

Figure 14 :

 14 Figure 14: RS-GRAD's candidates from APS, C2K, DIR and OMD data sets using numericbased and bitmap-based search spaces.

Figure 15 :

 15 Figure 15: RS-GRAD's candidates from AQY, HPC, HCV and CPX data sets using numericbased and bitmap-based search spaces.

Figure 17 :

 17 Figure 17: Comparison of number of GPs extracted by each algorithm.

Table 1 :

 1 A sample data set showing details of students who took part in a graded course.

	age sessions marks
	23	2	55
	32	4	64
	40	5	78
	25	5	48

Table 2 :

 2 A sample data set, D, showing details of participants who took part in a training.

	obj# age sessions marks
	obj1	23	2	55
	obj2	32	4	64
	obj3	40	5	78
	obj4	25	5	48

  2 , ..., gp n } denote a set of GPs extracted from a data set D. Any GP in X is denoted as relevant if and only if sup(gp i ) ≥ σ, where i ≤ n. The GP in X that has the highest support is denoted as the best GP. An invalid GP is one that is composed of 2 or more conflicting gradual items (i.e., {age ↑ , marks ↓ , age ↓ }).

Table 3 :

 3

Gradual bit vectors of GP candidates in a search universe. Where A denotes age, S

  Definition 3.1. (Gradual Bit Vector). A bit array b gp of size k that encodes a GP candidate; such that k = (2 • |AT |), where AT is the attribute set of a data set.For example, we derive a set of 6 gradual items from the attribute set {age, sessions, marks} of the data set in Table2(i.e. {age ↑ , age ↓ , sessions ↑ , sessions ↓ , marks ↑ , marks ↓ }). From this, we construct a gradual bit vector of size 6 (i.e 111111) where each binary digit represents the position of each gradual item and if the gradual item is present or absent.

For instance, if items {age ↑ } and {marks ↑ } are the only gradual items present in a GP candidate, then the gradual bit vector may be updated as 100010. Using this numeric model, it is possible to represent all GP candidates

Table 4 :

 4 Decimal values of bit vector encodings obtained from Table3.

	Bit	Decimal Hexa	Bit	Decimal Hexa
	Vector	Value	Value	Vector	Value	Value
	101000	40	28	000110	06	06
	100100	36	24	000101	05	05
	100010	34	22	101010	42	2A
	100001	33	21	101001	41	29
	011000	24	18	100110	38	26
	010100	20	14	100101	37	25
	010010	18	12	011010	26	1A
	010001	17	11	011001	25	19
	001010	10	A	010110	22	16
	001001	09	09	010101	21	15
		(a)			(b)

Table 5 :

 5 A table illustrating the association between bit vectors, GP candidates, decimal values and fitness values respectively. Where A denotes age, S denotes sessions and M denotes marks attributes of the data set in Table2.Using Table2, the pattern {A ↑ , S ↑ } is respected by 4 out of 6 object pairs:

	Bit	GP	Decimal Fitness
	vector Candidate	value	value
	101000 {A ↑ , S ↑ }	40	0.25
	100001 {A ↑ , M ↓ }	33	0.5
	011010 {A ↓ , S ↑ , M ↑ }	26	1.0

Table 6 :

 6 Experiment data sets.

	Data set	#objects used	#attributes	Domain	Source
	Breast Cancer (BCR)	116	10	Medical	[45]
	Hepatitis C (HCV)	615	14	Medical	[46]
	Chickenpox (CPX)	521	20	Zoonosis	[47]
	Cargo 2000 (C2K)	3942	98	Transport	[48]
	Air Quality (AQY)	9358	15	Environment	[49]
	APS Data (APS)	2474	171	Vehicle	[50]
	Omnidir (OMD)	2000	11	Coastline	[51]
	Directio (DIR)	8075	21	Coastline	[51]
	Power Consumption (HPC)	10001	9	Energy	[44]

Table 7 :

 7 Summary of run-times of algorithms on different data sets. Where Ga denotes GA-GRAD Pso denotes PSO-GRAD, Prs denotes RS-GRAD, Pls denotes LS-GRAD algorithms respectively and NU denotes the numeric-based search space, BM denotes the bitmap-based search space. For instance Ga-NU implies GA-GRAD using the numeric-based search space.

	Data	Ga-NU	Ga-BM	Algorithms' mean run-times Pso-NU Pso-BM Pls-NU Pls-BM	Prs-NU	Prs-BM
	APS	243.12	543.65	335.65	1711.50	133.88	253.88	53.17	179.40
	AQY	346.30	653.78	439.62	487.62	60.69	98.26	59.20	51.09
	C2K	165.80	422.08	136.93	416.10	23.18	60.14	22.67	43.79
	DIR	1475.00	3516.75	828.90	1193.25	226.18	376.28	222.38	187.98
	HPC	495.55	1632.75	489.70	628.88	114.78	96.68	92.06	77.50
	OMD	293.98	767.12	123.00	135.65	38.08	52.42	35.28	29.86
	HCV	0.77	1.05	0.47	0.48	0.22	0.21	0.19	0.15
	CPX	1.73	2.34	1.61	1.58	0.33	0.31	0.28	0.22
	BCR	0.36	0.39	0.52	0.48	0.08	0.09	0.08	0.07

Table 8 :

 8 Wilcoxon test on efficacy of search space

	Algorithm	Results
	GA-GRAD	test statistic = 0, p-value = 0.0039
	PSO-GRAD	test statistic = 5, p-value = 0.0391
	LS-GRAD	test statistic = 10, p-value = 0.1641
	RS-GRAD	test statistic = 16, p-value = 0.4961
	6.4.2. Experiment 2: Comparing Candidate GPs from Search Spaces
	Here, we seek to discover which search space allows our algorithms to yield a
	better distribution in favor of valid GPs. Every candidate that each algorithm
	generates, is evaluated to check if it is valid or invalid. Figures 8, 9, 10, 11,
	12, 13, 14, 15 are scatter plots of position against fitness/validity of candidates,
	where valid GPs are labelled as 'True' and invalid GPs are labelled as 'False'.

https://archive.ics.uci.edu/ml/index.php

https://data.oreme.org

https://meso-lr.umontpellier.fr

Acknowledgment

This work has been realized with the support of the High Performance Computing Platform: MESO@LR 4 , financed by the Occitanie / Pyrénées-Méditerranée Region, Montpellier Mediterranean Metropole and Montpellier University.

GRAD algorithm does not find any valid GP using the bitmap-based search space from APS and C2K data sets. Again in Figures 10 and11, we observe that the distribution of candidates are directed towards a single point in the case of the numeric-based search space.

Experiment 3: Comparative Analysis

In this experiment, we compare the performance of our algorithms in terms of run-time duration, memory consumption and number of extracted GPs against: GRAANK initially proposed by [START_REF] Laurent | Graank: Exploiting rank correlations for extracting gradual itemsets[END_REF] and ACO-GRAANK proposed by [START_REF] Owuor | Ant colony optimization for mining gradual patterns[END_REF].

We clarify the following: (1) There exists other GP mining algorithms that rely on a tree-based search for candidates; such as, GRITE proposed by [START_REF] Laurent | Pgp-mc: Towards a multicore parallel approach for mining gradual patterns[END_REF] and ParaMiner proposed by [START_REF] Negrevergne | Paraminer: a generic pattern mining algorithm for multi-core architectures[END_REF]. The gradualness semantic of such algorithms (which is focused on an ordered precedence graph of objects) is different from those under investigation in this study (which extend GRAANK), in that they rely on a breath-first search and use a gradualness semantic focused on concor- In Figure 16 (a), we observe that AcoGRAD has the longest run-time when applied on data sets with large number of attributes (i.e., APS and C2K).

However, AcoGRAD and GRAANK algorithms have the shorter run-times than PSO-GRAD and GA-GRAD algorithms when applied on data sets with few attributes (i.e., HPC, OMD, AQY). LS-GRAD and RS-GRAD algorithms have the shortest run-times across all the data sets. In terms of memory consumption


Alexander Shen

Individual codewords

Algorithmic information theory translates statements about classes of objects into statements about individual objects; it defines individual random sequences, effective Hausdorff dimension of individual points, amount of information in individual strings, etc. We observe that a similar translation is possible for list-decodable codes.

Let B n be the set of n-bit strings. The Hamming distance d(x, y) between two strings x, y ∈ B n is the number of coordinates where strings x and y differ. A set C ⊂ B n is an (e, L)-list-decodable code if for every y ∈ B n there are at most L strings x such that x ∈ C and d(x, y) e. In this definition e and L are two numbers (e is the number of allowed errors and L is the length of the list of possible decoded strings). If we know that some bit string x from C (a codeword of the code C) is transmitted through a channel that changes at most e positions, and see the changed string y, we can find (at most) L possible candidates for x.

Being a list decodable code is a property of a code as a set. It makes no sense to ask whether an individual string is a codeword (an element of some list decodable code) or not. Indeed, Boolean cube has many automorphisms: xor with a fixed string preserves Hamming distance and can map any string to any other one.

It turns out that we can define individual codewords in the framework of the algorithmic information theory.

Definition. A string x ∈ B n is an (e, L)-codeword if C(x|y) log L for every y ∈ B n such that d(x, y) e.

Here C(x|y) stands for the plain Kolmogorov complexity of x given y (see, e.g., [START_REF] Shen | Kolmogorov complexity and algorithmic randomness[END_REF]). We also use C(x) for plain (unconditional) complexity of x, and apply C to arbitrary finite objects (in particular, codes that are finite sets of strings).

The two-sided connection between this notion and the standard definition of list-decoding codes is provided by the following two (obvious) propositions.

Proposition 1. For every n, e, and L, the set of all (e, L)-codewords is an (e, O(L))-listdecodable code.

Proof. Indeed, for a given y there are at most 2 log L+O(1) = O(L) strings such that C(x|y) log L, and all the (e, L)-codewords such that d(x, y) e, are among them. These propositions show that the set of (e, L)-codewords is a maximal list-decodable code (that includes every other list-decoding code with some degradation in the parameters, depending on the other code's complexity). Note that if there exists a list decoding code with some parameters, there exists also a simple list decoding code with almost the same parameters. This code can be found by searching all subsets; the only thing we have to know are the parameters. If we agree to consider only values of L that are powers of two (losing factor 2), the complexity of the (e, L)-list-decodable code of maximal size is O(log n). In this way we get the following result: Proposition 3. Assume that there exists an (e, L)-decodable code of cardinality at least 2 k . Then there exists an (e, L • poly(n))-codeword of complexity at least k.

Proof. Let L ′ be the maximal power of 2 that does not exceed L. Knowing log L ′ , e, n and k (all of them can be specified by O(log n) bits), we search for (e, L ′ )-list-decodable code of size at least 2 k . The first code with this property has complexity O(log n), so Proposition 2 guarantees that all its codewords are (e, 2 log L ′ +O(log n) )-codewords, and log L ′ = log L + O(1). Since there are at least 2 k codewords in this code, one of them has complexity at least k.

The correspondence works in both directions:

Proposition 4. Assume that there exist an (e, L)-codeword of complexity at least k. Then there exists an (e, O(L))-decodable code of cardinality at least 2 k-O(log n) .

Proof. The property of being a (e, L)-codeword is (computably) enumerable given e and L: for a given x, we check all the strings y such that d(x, y) e and wait until we find that C(x|y) log L for all of them. We may again assume without loss of generality that L is a power of 2 and therefore the parameters have complexity O(log n). We know that there exist an (e, L)-codeword of complexity at least k, so there are at least 2 k-O(log n) different (e, L)-codewords (otherwise each of them could be specified by its ordinal number in the enumeration plus O(log n) bits for e and L). According to Proposition 1, they form an (e, O(L))-list decodable code. Propositions 3 and 4 show that the question "how large can be an (e, L)-decodable code made of n-bit strings" can be reformulated as "how complex can be an (e, L)-codeword of length n", with a small change in parameters. This does not help much, since the answer to this question is well known (see, e.g., the historical account in [START_REF] Guruswami | List Decoding of Error-Correcting Codes[END_REF] and [START_REF] Ромащенко | Заметки по теории кодирования. 2-е изд[END_REF] for the proofs). Moreover, the argument uses random codes and it is not clear whether one can prove the existence of individual codewords of high complexity without going through combinatorial translations. Still this translation gives us one more example of correspondence between combinatorial and complexity languages.

Proposition 2 .

 2 Let C ⊂ B n be an (e, L)-list-decodable code. Then every element of C is an (e, L2 C(C)+O(log n) )-codeword. Proof. Consider an arbitrary string y ∈ B n . The assumption guarantees that there are at most L strings x ∈ C such that d(x, y) e. Each of them can be specified (in addition to condition y and code C) by the ordinal number in this list of length L, i.e., by O(log L) bits. Therefore, if d(x, y) e, the complexity C(x|y) is bounded by C(C) + log L + O(log log L). The last term O(log log L) is the encoding overhead for the pair (C, ordinal number): recall that C(u, v) C(u) + C(v) + O(log C(v)). Note also that O(log log L) is O(log n) unless log L is much bigger than n, and the statement is trivial in the latter case.