Alexandre Millot

Rémy Cazabet

Jean-François Boulicaut

Exceptional Model Mining to support Multi-objective Optimization

Given numerical data about objects defined by descriptive and target attributes, we investigate the discovery of interesting conjunctions of descriptive attribute range of values that are associated to optimized target values. This can be useful across many application domains where one wants to perform Multi-Objective Optimization: the goal is to find the best compromise between the competing objectives that correspond to the di↵erent targets and one expects to learn about the optimal values of the descriptive attributes. For this purpose, we design Exceptional Model Mining instances: we look for subsets of objects -subgroups -whose models deviate significantly from the same models fitted on the whole dataset. A first method, called Exceptional Pareto Front Deviation Mining (EPFDM), characterizes the di↵erences between the Pareto front computed on the original data and the Pareto front computed after removing a subgroup of objects. We discuss in detail the design of a generic quality measure for EPFDM and we provide comprehensive empirical results. We also develop an approach called Exceptional Pareto Front Approximation Mining (EPFAM), whose goal is the discovery of models that approximate exceptionally well the true Pareto front. Beside empirical studies that consider both the qualitative and quantitative aspects of EPFDM and EPFAM, we present a use-case on plant growth recipe optimization in controlled environments, a timely challenge for a smarter agriculture. Exceptional Model Mining Multi-objective Optimization Pareto Subgroup Discovery Pattern Mining Plant Growth Optimization

Introduction

When studying a given process, it is common to collect data about some of its important parameters, say descriptive attribute values, but also to have target attributes that quantify, e.g., a quality or a cost measure. When all the attributes are numerical, we can support the discovery of interesting conjunctions of descriptive attribute range of values that are associated to optimized target values like, e.g., a good trade-o↵ between quality and cost. This can be useful across many application domains where one wants to perform Multi-Objective Optimization (MOO).

For example, the application scenario at the heart of this research is the design of better plant growth recipes in controlled environments. Nowadays, conventional farming methods have to face many tough challenges like, e.g., soil erosion and groundwater depletion. Furthermore, crucial problems related to the climate crisis also stimulate the need for new production systems. The concept of vertical urban farms (see, e.g., AeroFarms, Infarm, Bowery Farming1 ) can be part of a solution. In such farms, plants grow in controlled environments according to recipes that specify the di↵erent growth stages and instructions regarding many parameters (e.g., temperature, humidity, CO 2 , light). Throughout the whole process, automated systems keep track of such parameters and, at the end, values can be assigned to di↵erent objective variables (e.g., yield, taste, energy cost) for each recipe. We can exploit recipe data to optimize the growth process and it is intrinsically a MOO problem. This growth recipe optimization case is an example of a di cult task. The underlying model of the objective functions is unknown and new experiments can not easily be generated due to time and cost constraints. In other terms, typical MOO algorithmsthat require a model of the objective functions and generating a large number of points at each iteration -cannot be used. There is therefore a need for methods that can a data-driven discovery of relevant and exploitable information in such MOO problems.

To support our data mining approaches to MOO, we decided to investigate Exceptional Model Mining (EMM) instances. Hereafter, the descriptive attributes are numerical or categorical ones and we have numerical target attributes. EMM has been introduced over 10 years ago [START_REF] Leman | Exceptional model mining[END_REF]. It is a generalization of subgroup discovery [START_REF] Klösgen | Explora: A multipattern and multistrategy discovery assistant[END_REF][START_REF] Herrera | An overview on subgroup discovery: Foundations and applications[END_REF]. In subgroup discovery, given labeled data, we look for subsets of objects -subgroups -defined by interesting descriptions or patterns according to a quality measure computed on a unique target variable. The measure has to capture discrepancies between the target variable distribution in the subgroup and its distribution in the overall dataset. The greater and more significant the difference, the more interesting the subgroup is deemed. Within a typical EMM setting for a given class of models, we look for subgroups whose models deviate significantly from the same models fitted on the entire dataset. Once a type of data and a language of patterns have been chosen, each new EMM instance and thus type of targeted model requires [START_REF] Carmona | NMEEF-SD: Nondominated multiobjective evolutionary algorithm for extracting fuzzy rules in subgroup discovery[END_REF] suitable quality measures to assess the subgroup interestingness but also, (2) algorithms that can explore the search space to identify good models. Where subgroup discovery is inherently limited to a unique target concept, EMM is able to handle data where two or more targets exist, enabling the discovery of more complex interactions between variables.

MOO is a sub-field of Multi-criteria Decision Making that is focused on find-ing globally optimal solutions for real-life problems that involve a set of usually conflicting objectives. For simple problems, we can use methods that transform the multi-objective optimization problems into single-objective ones and discover a single globally optimal solution. When dealing with more complex scenarios -such as plant growth optimization -scalarization techniques lead to sub-optimal results and using proper MOO methods that yield not one, but a set of optimal solutions is needed. Pareto optimization [START_REF] Deb | Multi-objective optimization[END_REF][START_REF] Zhou | Multiobjective evolutionary algorithms: A survey of the state of the art[END_REF] relies on the dominance between solutions of the objective space. A solution is said to be non-dominated -or Pareto optimal -if it is impossible to improve an objective without degrading another. The set of Pareto optimal solutions is known as the Pareto front. The result of a MOO algorithm then involves not one, but a set of solutions -the Pareto front.

In our previous work [START_REF] Millot | Exceptional model mining meets multi-objective optimization[END_REF], we introduced a first approach to EMM in a MOO context called Exceptional Pareto Front Mining (EPFM). It is based on the discovery of exceptional Pareto front deviations -now called Exceptional Pareto Front Deviation Mining (EPFDM). EPFDM identifies and characterizes the di↵erences between the Pareto front computed on the original dataset and the Pareto front computed after removing a subgroup of objects. It can be used as an exploratory analysis tool to discover interesting pieces of knowledge about MOO problems such as (i) subspaces of the current Pareto front where data might be missing, (ii) subsets of better or worse solutions of the Pareto front with an explicit and concise description in the attribute description space, (iii) anomalous parts of the Pareto front. Suitable measures to estimate the deviations and a first generic quality measure designed for EPFM have been proposed. However, considering only distance-based Pareto front deviations limits the actionability of discovered subgroups.

We build on this previous work and significantly extend it, by further investigating the cross-fertilization between EMM and MOO. We design a generic model class for EPFM. Beside distance-based measures, we also discuss the added value of a new volume-based measure for EPFDM that enables the discovery of interesting deviation models. We also detail the conceptual basis of our generic quality measure, and introduce di↵erent ways to make it more robust. While EPFDM can be used as an exploratory tool to discover interesting knowledge regarding MOO problems, it cannot be consistently exploited to generate new, improved solutions. Therefore, we design an original method called Exceptional Pareto Front Approximation Mining (EPFAM). It supports the discovery of subgroups whose Pareto front approximates exceptionally well the true Pareto front, and whose descriptions can be exploited to generate Pareto optimal solutions with higher probability. Although some important changes have to be made to move from Exceptional Deviation Mining towards Exceptional Approximation Mining, most concepts related to pattern relevancy for EPFDM can be easily reused or adapted for EPFAM.

The added value of both EPFDM and EPFAM is investigated by means of quantitative and qualitative empirical studies. Most of the qualitative empirical evaluations with EPFDM are novel, significantly extending the analysis in [START_REF] Millot | Exceptional model mining meets multi-objective optimization[END_REF]. We also describe in detail a promising EPFM application scenario for the optimization of plant growth recipes in controlled environments. We introduce a realistic growth recipe simulator and show how (i) EPFDM can be used as an exploratory data analysis tool to discover interesting pieces of knowledge, such as a subspace of the objective space where the yield/cost trade-o↵ is worse than in its complement, (ii) EPFAM provides actionable information through its subgroup descriptions and enables the design of new, better growth recipes. Our data and code are made available at https://bit.ly/3EwnWUi.

The remaining of the paper is organized as follows. Section 2 formalizes our mining task. We review the literature in Section 3. In Section 4, we detail our contributions to EPFDM. We then introduce our contribution to EPFAM in Section 5. Section 6 introduces a generic quality measure for EPFM. In Section 7, we present an in-depth empirical evaluation of both EPFDM and EPFAM. Section 8 introduces our application scenario for EPFM in the field of smart agriculture. In Section 9, we discuss the limitations of our work. Finally, Section 10 concludes.

Preliminaries 2.1 Multi-Objective Optimization

The process to be optimized is known thanks to a collected dataset.

A dataset (G, M, T ) is a set of objects G, a set of attributes M and a set of targets T . In a given dataset, M contains real-valued and categorical attributes -the domain of any attribute m 2 M is denoted by Dom(m) -while the domain of each target t 2 T is a finite ordered set. Indeed, the targets can represent continuous or discrete variables, but the finiteness of the data restricts their domain to a finite ordered set. In this work, when numerical attributes are present in a dataset, we consider that a discretization method has to be applied on them as a pre-processing step.

A multi-objective optimization problem can be defined as follows:

M inimize F (x) = (f 1 (x), ..., f n (x)) T , x 2 M
where M is the attribute space and x is an attribute vector. F (x) consists of n objective functions f i : M ! R, i 2 {1, . . . , n}, where R n is the objective space. Given a dataset (G, M, T ), the vectors of objective function values correspond to the targets in T .

The objectives usually conflict with each other and the improvement of one objective might lead to a degradation for others. For this reason, we lack a single solution that optimizes all objectives simultaneously. When no order or relevance can be defined a priori on the di↵erent objectives, a Pareto optimization method is required. It is based on the dominance between solutions of the objective space.

A vector a = (a 1 , . . . , a n ) T is said to dominate a vector b = (b 1 , . . . , b n ) T , denoted a b if and only if 8i 2 {1, . . . , n}, u i  v i and u 6 = v. For example, in Figure 1, A B (i.e., object A dominates object B) since f 1 (A) < f 1 (B) and

f 2 (A) < f 2 (B). A non-dominated solution is called Pareto optimal.
A solution x is called Pareto optimal if and only if @y 2 M such that F (y)

F (x)
The set of all Pareto optimal solutions is called the Pareto Front:

P F = {F (x)|x 2 M |@y 2 M, F (y) F (x)}
Numerous test functions for multi-objective algorithms have been proposed in the literature [START_REF] Zitzler | Comparison of multiobjective evolutionary algorithms: Empirical results[END_REF][START_REF] Deb | Scalable test problems for evolutionary multiobjective optimization[END_REF][START_REF] Huband | A review of multiobjective test problems and a scalable test problem toolkit[END_REF]. The true Pareto front (i.e., ground truth) of these functions is usually known -the quality of a solution set returned by any MOO algorithm can therefore easily be compared to the ground truth -and they are designed such that Pareto front approximation by algorithms is di cult. To illustrate our work and some of its related concepts, we consider the Fonseca-Fleming function [START_REF] Fonseca | Multiobjective genetic algorithms made easy: selection sharing and mating restriction[END_REF] that implies 3 descriptive variables from {x 1 , x 2 , x 3 } and 2 objective functions f 1 and f 2 that both need to be minimized:

f 1 (p) = 1 exp 3 X i=1 ✓ x i 1 p 3 ◆ ! , x i 2 [ 4, 4] f 2 (p) = 1 exp 3 X i=1 ✓ x i + 1 p 3 ◆ ! , x i 2 [ 4, 4]
We generate 5000 random objects using the Fonseca-Fleming function and we retrieve the true Pareto front of the function from jMetal2 . Fonseca is the name of the corresponding dataset. Table 1 provides a toy dataset -with discretized numerical attributes using equal-width with 5 bins -that is a subset of the 5000 random objects of Fonseca.

Table 1: Toy dataset related to the Fonseca-Fleming function. Figure 1 depicts the Pareto front (i.e., the non-dominated solutions) of the Fonseca-Fleming function. Very few points lie close to the Pareto front. This is due to (i) the Pareto front of the Fonseca-Fleming function being hard to approximate, (ii) the random sampling method used to generate the data points, which is not optimal to solve MOO problems.

x 1 x 2 x 3 f 1 f 2 g 1 [-4,-2.4] [2.

Exceptional Model Mining

EMM is a generalization of subgroup discovery that can handle more than one target attribute by using model classes. A subgroup p can be described either by its intent -the description of the subgroup in terms of attribute values -or by its extent -the coverage of the subgroup in the dataset. The intent of a subgroup p is given by p

d = h' 1 , . . . , ' n ↵
where each ' i is a restriction on the domain value of m i 2 M . A restriction for a nominal attribute m i is given by m i = v with v 2 Dom(m i ). The intent p d of subgroup p covers the set of objects denoted ext(p d ) ✓ G. For example, given the toy dataset in Table 1, we could find a subgroup whose intent is hx 1 = [ 0.8, 0.8], x 2 = [ 0.8, 0.8], x 3 = [ 2.4, 0.8]i and whose extent is {g 4 , g 5 }.

In subgroup discovery, we have only one target. The quality of a subgroup is usually defined as the di↵erence between the distribution of the target variable in the subgroup and its distribution over the entire dataset. Since important discrepancies can easily be achieved with small subsets of objects, a factor that takes into account the size of the subgroup can be used as well (see, e.g., the popular Weighted Relative Accuracy measure [START_REF] Lavrac | Subgroup discovery with CN2-SD[END_REF]).

Exceptional Model Mining enables for two or more target variables depending on the chosen model class. In the standard EMM setting, the interestingness of a subgroup p is measured by a numerical value that quantifies the deviation between the model fitted on the subgroup and the model fitted on another subset of the data. There are usually two options for which subset is chosen for comparison: we can compare the model of the subgroup either to the model of its complement or to the model of the whole dataset. Choosing one or the other can lead to very di↵erent results and may depend on the considered application scenario. [START_REF] Duivesteijn | Exceptional model mining[END_REF] show that there is not always a clear-cut best solution.

From an algorithmic perspective, subgroups are explored by progressively specializing their intents, from general to more specific descriptions. At each stage, a specialization operator is applied to create more complex subgroups by addition of a restriction on an attribute.

Related Work

We investigate possibilities for cross-fertilization between EMM and MOO thanks to the computation of Pareto fronts on objects of the dataset. To the best of our knowledge, we were the first to consider EMM based on this concept [START_REF] Millot | Exceptional model mining meets multi-objective optimization[END_REF]. However, closely related topics involving pattern mining and multi-objective optimization have been investigated in the past few years.

Pattern Discovery and Exceptional Model Mining

Subgroup discovery (SD) has been introduced 25 years ago [START_REF] Klösgen | Explora: A multipattern and multistrategy discovery assistant[END_REF] in the Explora discovery assistant. Since then, numerous approaches involving exhaustive [START_REF] Atzmueller | Sd-map -a fast algorithm for exhaustive subgroup discovery[END_REF]) and heuristic algorithms [START_REF] Mampaey | E cient algorithms for finding richer subgroup descriptions in numeric and nominal data[END_REF] were introduced. Early on, research was mainly focused on producing e cient enumeration methods for binary and nominal data [START_REF] Herrera | An overview on subgroup discovery: Foundations and applications[END_REF]. Works on numerical concepts, be it for attributes or target variables, were few and far between. The usual way to deal with such data is to discretize the data as a preprocessing step (see, e.g., [START_REF] Fayyad | Multi-interval discretization of continuous-valued attributes for classification learning[END_REF] even though it leads to loss of information. Over 20 years ago, [START_REF] Aumann | A statistical theory for quantitative association rules[END_REF] introduced the concept of Quantitative Association Rules where a rule consequent is the mean or the variance of a numerical attribute. A rule is then defined as interesting if its mean or variance significantly deviates from that of the overall dataset. Later on, [START_REF] Webb | Discovering associations with numeric variables[END_REF] proposed an extension of such rules called Impact Rules. [START_REF] Jorge | Distribution rules with numeric attributes of interest[END_REF] introduced Distribution Rules, a type of association rules that involves a statistical distribution on the consequent. In this work, a rule is deemed interesting if its target distribution is significantly di↵erent from that of the overall dataset. Their approach however only considers one target and the Kolmogorov-Smirnov test as an interestingness measure.

In the past few years, interest for numerical data took o↵. [START_REF] Lemmerich | Fast exhaustive subgroup discovery with numerical target concepts[END_REF] proposes an exhaustive algorithm for subgroup discovery with numerical target concepts. They introduce several quality measures, algorithms and bounds to mine for high quality subgroups in numerical data. However, the approach is only exhaustive with prior discretization of the numerical attributes, leading to non-optimal results. [START_REF] Meeng | Uni-and multivariate probability density models for numeric subgroup discovery[END_REF] introduced a new type of interestingness measure for numerical targets. They explain that using simple statistical measures such as the mean or the variance is inadequate, and that interesting subgroups can be missed. They argue for the use of probability density models -using techniques such as kernel density estimation and histograms -to discover more diverse types of deviations in the distribution of the targets. Recently, we introduced a new algorithm for optimal subgroup discovery in purely numerical data (i.e., data where both the attributes and the target are numerical) (Millot et al., 2020a). No discretization is needed and the approach provides a guarantee on the optimality of the returned subgroup, at the cost of scalability in certain applications. While much has been done for numerical data with a unique target variable, these approaches cannot deal with complex models involving multiple targets.

Exceptional Model Mining [START_REF] Leman | Exceptional model mining[END_REF][START_REF] Duivesteijn | Exceptional model mining[END_REF] was introduced as a generalization of subgroup discovery for multi-target problems. Several approaches, both heuristic [START_REF] Krak | Exceptional model mining with tree-constrained gradient ascent[END_REF][START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF] and exhaustive [START_REF] Lemmerich | Generic pattern trees for exhaustive exceptional model mining[END_REF] have been developed. In EMM, each problem is linked to a model class and requires a tailored search algorithm. For instance, considering the mining of exceptional correlations [START_REF] Downar | Exceptionally monotone models-the rank correlation model class for exceptional model mining[END_REF] and the mining of exceptional Bayesian networks [START_REF] Duivesteijn | Subgroup discovery meets bayesian networks-an exceptional model mining approach[END_REF] require specific quality measures and search algorithms. Duivesteijn et al. (2012a) take on what they call the "workhorse" of data analysis problems: linear regression. They introduce a new model class for exceptional regression model mining relying on a quality measure based on Cook's distance. Other interesting EMM instances have been investigated. Among them, [START_REF] Duivesteijn | Understanding where your classifier does (not) work-the scape model class for emm[END_REF] and Duivesteijn et al. (2012b) both work with model classes for classification problems. The former approach aims to identify subspaces where a given classifier performs particularly well or badly, giving the user insights on which parts of their classifier they must focus on in the context of model diagnosis and interpretable machine learning. The latter approach aims to identify and exploit exceptional interdependencies between labels in a multi-label classification setting, allowing the improvement of the classifier overall quality. More recently, we also find proposals about the discovery of exceptional (dis-) agreements between groups [START_REF] Belfodil | Deviant: Discovering significant exceptional (dis-) agreement within groups[END_REF], exceptional mediation models [START_REF] Lemmerich | Mining exceptional mediation models[END_REF] and exceptional spatiotemporal behavior [START_REF] Du | Exceptional spatio-temporal behavior mining through bayesian non-parametric modeling[END_REF].

Multi-Objective Optimization

EMM deals with complex interactions between multiple targets, and Multiobjective Optimization (see, e.g., [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF])) is a nice example of a task that involves such complex interactions. While some MOO problems can be solved by transforming them into uni-objective ones, most problems require methods based on Pareto optimization [START_REF] Roijers | A survey of multiobjective sequential decision-making[END_REF]. The goal is then to design algorithms that approximate the true Pareto front of a given problem as well as possible. Most common approaches resort to generic nature-inspired heuristics [START_REF] Zhou | Multiobjective evolutionary algorithms: A survey of the state of the art[END_REF], including the well-known NSGA-II genetic algorithm [START_REF] Deb | Multi-objective optimization[END_REF]. However, their genericity can also be their downfall: finding proper values for the numerous parameters is di cult and mostly involves trial and error, which restricts their usage to settings where the model of the objective functions is known and numerous experiments can be carried out. It is worth noting that since we work with limited data and unknown underlying models, our methods do not compare multi-objective algorithms per se, but rather the end results of MOO processes (i.e., the Pareto fronts).

While algorithms are able to create sets of solutions, quality indicators that allow for the comparison of di↵erent sets of solutions are needed [START_REF] Li | Quality evaluation of solution sets in multiobjective optimisation: A survey[END_REF]. Generally speaking, we find quality indicators that need a reference set of solutions [START_REF] Schutze | Using the averaged haus-dor↵ distance as a performance measure in evolutionary multiobjective optimization[END_REF] to compare new solution sets against, and quality indicators that require a reference point [START_REF] Hansen | Evaluating the quality of approximations to the non-dominated set[END_REF] -such as the Nadir point or the anti-ideal point -to be computed. The comparison of algorithms and quality indicators for MOO approaches is important and numerous benchmark functions with various constraints, such as the Fonseca-Fleming function [START_REF] Fonseca | Multiobjective genetic algorithms made easy: selection sharing and mating restriction[END_REF], have been proposed. It is worth noting that our problem is di↵erent from the selection of a single good solution from a Pareto front as in [START_REF] Fuente | Automatic selection of a single solution from the pareto front to identify key players in social networks[END_REF], since we are interested in identifying exceptional deviations and approximations of Pareto fronts thanks to a description in the attribute space.

Although the literature on Pareto-based MOO is well-supplied, current existing MOO methods have several limitations (i) when the underlying model of the objective functions is unknown, existing approaches can not be used, since new points can not easily be generated, and (ii) typical MOO algorithms require a large number of points to be generated at each iteration, which is antinomic to many real-life scenarios where experiments are limited due to time and cost constraints. There is therefore a need for MOO-based methods that would not su↵er from such limitations.

Cross-Fertilization between EMM and MOO

While both MOO and pattern mining, including both SD and EMM, have been seriously investigated, contributions at the intersection of the two subfields have been few and far between [START_REF] Srinivasan | Evolutionary multi objective optimization for rule mining: A review[END_REF]. Recently, we introduced a generic framework using actionable subgroup discovery to solve optimization problems when the underlying model is unknown (Millot et al., 2020b). However, this was intrinsically dedicated to uni-objective problems. [START_REF] Carmona | NMEEF-SD: Nondominated multiobjective evolutionary algorithm for extracting fuzzy rules in subgroup discovery[END_REF] introduced an evolutionary fuzzy system named NMEEF-SD based on the NSGA-II algorithm to discover interpretable and high quality subgroups. While their approach is interesting, it lacks genericity: it allows for the discovery of subgroups with a good trade-o↵ between a few pre-defined objectives and it focuses on computing the Pareto front at the subgroup level (i.e., they consider the Pareto front of subgroups and not the Pareto front of objects of the dataset). [START_REF] Soulet | Mining dominant patterns in the sky[END_REF] have exploited the notion of skyline queries, introducing the notion of skyline patterns. They focus on mining useful patterns, according to a set of user preferences. Since skyline queries involve multiple constraints of equal importance, a trade-o↵ has to be found between these constraints, which is exactly the subject of MOO. They use the notion of dominance between patterns to look for those that are non-dominated according to the set of constraints. These non-dominated patterns are called skyline patterns, and in MOO terms, they correspond to the set of patterns which lie on the Pareto front. Their approach presents several advantages: (i) it finds patterns which are non-dominated by any other pattern, (ii) it is generic, as it naturally extends to any kind of pattern which can be queried through a skyline query, (iii) the study of the relationships between condensed representations of patterns and skyline pattern mining enables them to compute the set of skyline patterns in an e cient way. [START_REF] Ugarte | Skypattern mining: From pattern condensed representations to dynamic constraint satisfaction problems[END_REF] build on this work, further investigating the relationships between the so-called condensed representations of patterns and skyline pattern mining. As a result, they can build an interesting skypattern mining algorithm based on a dynamic constraint satisfaction problem. The concept of skyline was also exploited in [START_REF] Van Leeuwen | Discovering skylines of subgroup sets[END_REF] to mine for skylines of subgroup sets. They present an exhaustive and a heuristic algorithm for the discovery of top-K subgroup sets that o↵er the best trade-o↵ between quality and diversity. A common thread between all these approaches is the computation of Pareto optimal patterns at the subgroup -and rule/pattern -level (i.e., they consider the Pareto front of subgroups and not the Pareto front of objects of the dataset), while we are interested in the computation of exceptional models whose interestingness is at the object level.

Finally, in [START_REF] Millot | Exceptional model mining meets multi-objective optimization[END_REF], we introduced a first approach to Exceptional Pareto Front Mining (EPFM). Here, we discuss the limits of this preliminary approach -renamed EPFDM -both in terms of quality measure and applications scenarios. We aim to build better, more generic quality measures, and show that the mining of other types of exceptional Pareto front patterns beyond EPFDM can be interesting.

Mining Exceptional Pareto Front Deviations

We want to build a model class for EMM in a MOO setting and we propose to look for exceptional Pareto front deviations. In a given dataset, we define the true Pareto front -denoted P F dataset -as the set of all non-dominated objects over the whole data. In typical EMM approaches, an exceptional model is computed directly on the objects of the subgroup. Then a quality measure is used to measure the deviation between the model built on the subgroup and the same model built on the whole dataset. We assume that we have to work with objective minimization only. When a maximization problem occurs, it is transformed into a minimization one by multiplying the function by -1.

Our goal hereafter is to capture subgroups representing local phenomena with the highest influence on the shape of P F dataset , meaning that we need to measure the e↵ects on P F dataset of removing these objects from the data. Therefore, when a subgroup is generated, we remove all its objects from the dataset. Then, we compute the new Pareto front P F model on the remaining data, called the complement of the subgroup. Finally, we can compute the deviation between P F dataset , the Pareto front for the dataset, and P F model . This first approach to EPFM, based on the discovery of subgroups creating large deviations in the shape of the true Pareto front, is called Exceptional Pareto Front Deviation Mining (EPFDM).

Let us first define which objects of each Pareto front are taken into account when computing distances between Pareto fronts. Given two Pareto fronts P F target and P F ref erence , the Partial Pareto Front P P F (P F target , P F ref erence ) is equal to:

P F target \ P F ref erence
The PPF is defined as the subset of objects of a Pareto front that are not in the set of objects of the other Pareto front.

A PPF can be computed either for P F dataset or for P F model . We have

P P F model = P F model \ P F

Designing Quality Measures for EPFDM

Multi-objective optimization requires algorithms that approximate as well as possible the true Pareto front for any given problem. Many quality measures have been introduced to estimate the quality of the computed Pareto front compared to the true Pareto front or to an ideal point [START_REF] Li | Quality evaluation of solution sets in multiobjective optimisation: A survey[END_REF].

Thanks to some of these measures, the distance between two Pareto fronts can be computed.

In traditional MOO measures, only the non-symmetrical distance from either the true Pareto front to the approximate Pareto front (e.g., Inverted Generational Distance [START_REF] Li | Quality evaluation of solution sets in multiobjective optimisation: A survey[END_REF]) or from the approximate Pareto front to the true Pareto front (e.g., Generational Distance [START_REF] Li | Quality evaluation of solution sets in multiobjective optimisation: A survey[END_REF]) is computed. However, [START_REF] Schutze | Using the averaged haus-dor↵ distance as a performance measure in evolutionary multiobjective optimization[END_REF] show that taking into account both distances provides measures that are more resilient to outliers and uncommonly shaped Pareto fronts. Therefore, we exploit measures that consider both the distance between the partial Pareto front of the subgroup P P F model and the Pareto front of the overall dataset P F dataset , and the distance between the partial Pareto front of the overall dataset P P F dataset and the Pareto front of the subgroup P F model . Then, the largest one is kept as the true distance.

It is important to normalize each of the targets such that they contribute equally to the measure. We normalize each of them to get a value between 0 and 1 using the standard scaling x 0 j = (x j min j )/(max j min j ), where min j and max j are respectively the minimum and maximum of Target j in the dataset.

Our measures are based on the popular Hausdor↵ Distance that estimates how far two subsets of points in a metric space are from each other using Euclidean distances: informally, it is defined as the largest of all the distances from a point in one subset to its closest point in the other subset.

The Hausdor↵ Distance (HD) between P F model and P F dataset is defined as:

HD(P F model , P F dataset ) = max(max(mind(P P F model , P F dataset )), max(mind(P P F dataset , P F model )))
The Median Hausdor↵ Distance (MHD) between P F model and P F dataset is defined as:

MHD(P F model , P F dataset ) = max(med(mind(P P F model , P F dataset )), med(mind(P P F dataset , P F model )))
where mind computes the minimal Euclidean distance from each point of the partial Pareto front to the other Pareto front, max returns the largest value in a set of distances and med returns the median value in a set of distances.

Let us now consider a modified version of the Hausdor↵ Distance, called Averaged Hausdor↵ Distance (AHD) and introduced in [START_REF] Schutze | Using the averaged haus-dor↵ distance as a performance measure in evolutionary multiobjective optimization[END_REF]. The Averaged Hausdor↵ Distance AHD(P F model , P F dataset ) between P F model and P F dataset is:

max 1 N N X i=1 (mind(P P F i model , P F dataset )), 1 M M X i=1 (mind(P P F i dataset , P F model )) !
where N is the number of objects of P P F model and M is the number of objects of P P F dataset . mind computes the minimal Euclidean distance from object i of the partial Pareto front to the other Pareto front. The average of all minimal distances is then computed. Finally, max takes the largest distance of the two.

Although our work has lead us to investigate measures that consider the distance between solution sets, the MOO literature presents numerous ways of estimating the quality of a solution set, including dominance-based, regiondivision based and volume-based quality indicators [START_REF] Li | Quality evaluation of solution sets in multiobjective optimisation: A survey[END_REF]. We propose to exploit a volume-based measure taken from the MOO literature, the so-called Hypervolume (HV ) [START_REF] Zitzler | Multiobjective optimization using evolutionary algorithms-a comparative case study[END_REF]. Contrary to previously introduced distance-based measures, HV does not need a reference set, but a reference point to compute the quality of a given Pareto front. In other words, the concept of Partial Pareto Front is only relevant for distance-based measures, and will not be used with HV .

The Hypervolume HV (P F ) between a given Pareto front P F and its reference point r is:

HV (P F, r) = [ a2P F {x|a x r} !
where is the Lebesgue measure.

Informally, the Hypervolume value of a Pareto front is the area (in two dimensions) or volume (in three or more dimensions) of the area enclosed by the Pareto front and the specified reference point. HV usually takes values between 0 and 1. Typically, the reference point corresponds to the Nadir point. The Nadir point is defined as the vector of the worst possible value of each objective according to the optimal true Pareto front. One issue with the Nadir point is that it cannot be precisely estimated in most scenarios. Indeed, it requires an optimal or near optimal Pareto front to get a good estimate of the worst value of each objective, which is rarely computable in real-life scenarios where the underlying model is known, and clearly impossible to compute when the model is unknown. Figure 3 (left) depicts an example of the Nadir point defined according to the Pareto front in Fonseca. The figure also depicts an example of HV computed between the Pareto front of the dataset and the Nadir point. One issue arises from estimating the reference point this way: numerous objects of the dataset lie outside the area enclosed by the Pareto front and the Nadir point. This is problematic for us since when we mine for subgroups, any object could be part of the Pareto front of a model, even those that lie outside the enclosed area in Figure 3. For this reason, we define our own version of a reference point, that ensures that no object lies outside the enclosed area.

The reference point r((G, M, T )) of a given dataset is defined by:

r((G, M, T )) = ⌦ max(T i ) ↵ i2{1,...,|T |}
Informally, the reference point of a dataset is the vector composed of the worst value for each target in the overall dataset. Figure 3 (right) depicts a comparison between our reference point and the typical Nadir point. This novel reference point ensures that the HV can be properly computed for any subset of a given dataset.

Let us now detail how the HV of a given subgroup is computed in EPFDM. We look for subgroups whose removal produce exceptional deviations of the Pareto front. Therefore, we need to look for subgroups that create the largest di↵erences between the HV of the dataset, and the HV of the complement of the subgroups.

The HV of a given subgroup, denoted by HV dev , is defined as:

HV dev (P F model , P F dataset ) = 1 HV (P F model ) HV (P F dataset )
This way, higher values of HV dev mean larger deviations of the Pareto front and the measure is normalized with values between 0 and 1.

Algorithm

The source code is available at https://bit.ly/3EwnWUi. Detailed explanations of the algorithm are available at [START_REF] Millot | Exceptional model mining meets multi-objective optimization: application to plant growth recipes in controlled environments[END_REF]. Our enumeration algorithm is based on a top-K beam search [START_REF] Duivesteijn | Exceptional model mining[END_REF]. In a simple implementation of beam search, subgroups can be evaluated multiple times due to its candidate generation process. In our beam search, candidates in the beam can only be evaluated once, leading to a small gain in e ciency.

The evaluation part of the process is by far the most costly here. To compute the Pareto front of a subgroup, we employ a greedy approach where each object not in the subgroup is compared to all the objects not in the subgroup to check whether it is dominated by at least one other object. If it is not dominated by any other object, we add it to the Pareto front.

Finally, we implement a simple pruning technique that leads to a large reduction in the number of subgroups that need to be evaluated. For a subgroup to be interesting, its removal has to create a deviation in the shape of the true Pareto front. Due to the nature of the dominance relation, the removal of any object not on the true Pareto front cannot lead to a change in the Pareto front. It means that only subgroups that contain at least one object that belongs to the true Pareto front are of interest. As a result, during our search, we ignore any subgroup and its specializations if it does not contain an object that belongs to the true Pareto front.

Mining Exceptional Pareto Front Approximations

Although EPFDM can be used as an exploratory data analysis tool to discover interesting pieces of knowledge, such as (i) subspaces of the current Pareto front where data could be missing, (ii) subsets of better or worse solutions of the Pareto front, (iii) anomalous parts of the Pareto front, it lacks the capability of providing information that directly enables the design of better solutions. Therefore, we would like a method that can better support the discovery of actionable insights to generate higher quality solutions for MOO problems. We investigate the discovery of exceptionally good approximations of the true Pareto front, called Exceptional Pareto Front Approximation Mining (EPFAM). It provides a nice solution to our problem: with exceptional approximations supported by subgroups and their understandable descriptions, we can generate new, close to Pareto optimal, solutions for a given MOO problem. When we lack expertise, instead of exploring new solutions more or less randomly, hoping for them to o↵er good trade-o↵s, we can exploit a given subgroup description to generate high quality solutions with a higher probability. We once again assume that we have to work with objective minimization, and any maximization problem is transformed into a minimization one. For numerical attributes, we also assume that they have been discretized a priori such that all attributes are binary or categorical.

Our goal hereafter is to discover subgroups whose Pareto front shape is as similar as possible to that of P F dataset . To do this, when a subgroup is generated, we compute its Pareto front P F model . Then, we can assess how good an approximation P F model is with regard to P F dataset . Now that we have defined how models are computed in EPFAM, we need measures to assess their quality.

Designing Quality Measures for EPFAM

While the use of distance-based measures makes sense in the case of EPFDM, it is not always relevant for EPFAM. Indeed, in critical cases where the Pareto front of the subgroup lies entirely on the true Pareto front, the computed distance between the two would either be 0 (e.g., if we do not use the concept of Partial Pareto Front) or it would be an irrelevant value (e.g., in the case where we use Partial Pareto Fronts) non-representative of the actual distance between the fronts. Therefore, we discard distance-based measures and we focus on volume-based measures like HV , that can better represent how similar two Pareto fronts are. The HV of the true Pareto front and its reference point are calculated as detailed in Section 4. Let us detail how the HV of a given subgroup is computed in EPFAM. We now look for subgroups whose Pareto front is an exceptional approximation of the true Pareto front. Therefore, we need to look for subgroups whose HV is as close as possible to that of the dataset.

The HV of a given subgroup, denoted HV approx , is defined as:

HV approx (P F model , P F dataset ) = HV (P F model ) HV (P F dataset )
This way, higher values of HV approx mean better approximations of the Pareto front and the measure is normalized with values between 0 and 1.

Algorithm

The source code is available at https://bit.ly/3EwnWUi. Detailed explanations of the algorithm are available at [START_REF] Millot | Exceptional model mining meets multi-objective optimization: application to plant growth recipes in controlled environments[END_REF]. For the computation of top-K EPFAM, a slightly modified strategy from the one introduced in Section 4 for EPFDM can be used. First, instead of computing the Pareto front of the complement for each subgroup, we compute the Pareto front of the subgroups themselves. Second, in EPFAM, the pruning of the subgroups which do not contain any object that belong to the true Pareto front is only applied if a minimum support constraint is used.

A Generic Quality Measure

Being able to measure the deviation from the true Pareto front may not be enough to mine interesting subgroups. In the literature about EMM quality measures, we usually get measures with the following form: the quality of the subgroup is multiplied by its generality. Indeed, in a typical EMM setting, discovering unusual distributions is easily achieved with small subgroups, therefore there is a need to optimize the generality (i.e., cover) of the discovered subgroups. In the context of EPFDM, we face the opposite problem: unusual distributions are easily achieved with large subsets of the data (e.g., if we find a subgroup covering 80% of the data, it is very likely that its removal will create a large deviation in the Pareto front). Despite the large distance, such subgroups are not interesting. Figure 4 (left) depicts an example of this phenomenon. Therefore, we need to optimize the locality of the subgroups. Furthermore, small subgroups that modify only a small part of the true Pareto front when removed are also not desirable. Indeed, an issue can arise when either outliers are apart of the true Pareto front or when the density of objects is very low close to some part of the Pareto front. In such cases, the removal of subgroups with very few objects on the true Pareto front can create unwanted large deviations in the Pareto front of the model leading to overfitting and trivial subgroups. Figure 4 (right) depicts an example of this phenomenon. Therefore, in EPFDM, we might also be interested in the optimization of the generality of the subgroup with regard to the true Pareto front, i.e., the generality of the model. To summarize, given the previously defined deviation measures, we can get either very large or very small subgroups.

To deal with the first issue (i.e., unwanted large subgroups), let us introduce a locality indicator. The locality indicator of a subgroup p is:

Locality(p) = 1 ⇣ m M ⌘
where M is the total number of objects of the dataset and m is the number of objects of p.

This locality indicator favors smaller subgroups over larger ones. It is especially useful for cases where objects can be removed from a subgroup without modifying the Pareto fronts. However, this indicator might be too strict in some application cases where larger subgroups might be more interesting. Therefore, we add a factor that tunes the importance of the locality indicator.

The locality indicator of a subgroup p, with its importance factor, is:

Locality a (p) = ✓ 1 ⇣ m M ⌘ ◆ a , a 2 [0, 1]
where M is the total number of objects of the dataset, m is the number of objects of p, and a an importance factor.

To deal with the issue of subgroups with few objects on the true Pareto front creating unwanted large deviations in the Pareto front of the model, we propose several solutions. First, let us use the entropy of the split between the objects of the true Pareto front which are not part of the subgroup, and those who are. We also want control over the importance of the entropy, therefore we introduce a factor that tunes its importance.

The weighted entropy of a subgroup p is:

Entropy b (p) = n N lg ⇣ n N ⌘ N n N lg ✓ N n N ◆ ! b , b 2 [0, 1]
where lg denotes the binary logarithm, N is the total number of objects on the true Pareto front, n is the number of objects of p that belong to the true Pareto The coverage of a subgroup p is:

Coverage c (p) = ⇣ n N ⌘ c , c 2 [0, 1]
where N is the total number of objects on the true Pareto front, n is the number of objects of p that belong to the true Pareto front, and c an importance factor. Finally, we can suggest a third way to take into account the generality of the model. We can exploit a minimum support for the percentage of objects of the true Pareto front which are covered by the subgroup. If the minimal support constraint is not satisfied, the subgroup should be discarded.

For a given subgroup p and a minimum support minSupp, we compute the following function MSV :

MSV (p, minSupp) = ( 0, if n N < minSupp 1, if n N minSupp
where N is the total number of objects on the true Pareto front, n is the number of objects of p that belong to the true Pareto front, and minSupp is the userdefined minimum support. The function returns 0 if the minimum support constraint is not satisfied by the subgroup, and 1 otherwise.

We can now define an aggregated measure to take into account the quality of the model, the locality of the subgroup, and the generality of the model.

Our aggregated quality measure q EP F DM for a subgroup p is defined as:

q EP F DM (p) = Deviation(p) ⇥ Locality a (p) ⇥ Generality(p)
where Deviation(p) can be any measure of the deviation quality of p with regard to the true Pareto front, Locality a (p) denotes the locality indicator, and Generality(p) denotes the chosen indicator for the generality of the model (i.e., Entropy b , Coverage c , or MSV ).

The generic quality introduced for EPFDM is applicable to EPFAM, provided that we use an approximation measure instead of a deviation measure in the aggregated measure.

Our aggregated quality measure q EP F AM for a subgroup p is defined as:

q EP F AM (p) = Approximation(p) ⇥ Locality a (p) ⇥ Generality(p)
where Approximation(p) can be any measure of the approximation quality of p with regard to the true Pareto front, Locality a (p) denotes the locality indicator, and Generality(p) denotes the chosen indicator for the generality of the model (i.e., Entropy b , Coverage c , or MSV ).

Although we chose to take an interest in distance-based and volume-based measures for the exceptionality of the Pareto fronts in both EPFDM and EP-FAM, other quality indicators from the MOO literature, like the dominancebased C indicator [START_REF] Zitzler | Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach[END_REF]) could be considered as well.

It is interesting to note that instead of using an aggregated quality measure, we can also exploit the concept of skyline patterns [START_REF] Soulet | Mining dominant patterns in the sky[END_REF] to mine for subgroups that o↵er the best trade-o↵ between deviation (resp. approximation), locality and generality. This alternative method is empirically evaluated in Section 8.3.

Experiments

Let us now consider experiments on both synthetic and real life datasets. The source code and datasets used in our experiments are available at https://bit. ly/3EwnWUi. In the following experiments (i.e., for both EPFDM and EPFAM) and unless specified otherwise, the beam width was set to 10, the search depth to 5, the locality factor to 1, and the MSV function was employed with a minimum support of 0.1. These parameters were chosen to explore the search space as much as possible while favoring the small subgroups and keeping the running times in an acceptable range. When it comes to discretization of the numerical attributes, we apply equal-width, equal-frequency, and binary representations (Meeng and Knobbe, 2021) using 2, 3, 5, 10, 15 and 20 bins on each dataset -except Obesity for which the algorithm could not return results in less than 24 hours when using binary representations with over 3 bins -and we retain only the one that leads to the best models. The numerical descriptive attribute values are then replaced with nominals of cardinality equal to the number of bins. In the figures, both red and orange objects belong to the best subgroup.

Relevance of EPFDM

The goal of this experiment is to show the relevance of our approach to discover exceptional Pareto front deviations. Here, it means finding subgroups whose descriptions in the attribute space provide insights on interesting local parts of the Pareto Front. Let us first use the synthetic dataset Fonseca -based on the Fonseca-Fleming function -introduced in Section 2.1. We compute the best subgroup found by our algorithm with HV dev , HD, AHD and MHD. On this dataset, equal-width discretization was found to be the best method, likely due to the uniform distributions of the variables. Figure 5 depicts the best model for each measure. The best deviation is almost the same for all measures, although the size of the subgroup is quite di↵erent. With HD, we find a model with a large deviation supported by a small subgroup whose description is hx1 = [ 0.8, 0.8],

x2 = [ 0.8, 0.8], x3 = [ 0.8, 0.8]i. Exploiting this subgroup allows for the generation of new objects with a good trade-o↵ between both functions. Since HD, AHD and MHD mine very similar models -likely due to the fact that all 3 measures are based on the Hausdor↵ distance -, we only report the best models found with HV dev and HD for the other experiments. Next, we want to see if EPFDM is able to discover a planted subgroup, i.e., a subgroup known a priori that has been purposefully inserted into the data. We first generate 10 objects whose attribute values belong to the following domains: hx1 2 [0.15, 0.25], x3 2 [0, 0.03], x2 2 [0.45, 0.55]i. This way, we generate a small subset of objects that are all close to each other in the objective space. We then generate a new Fonseca dataset -named FonsecaPlanted -made of 1000 random objects, although we generate the objects so that none of them can a↵ect our planted subgroup. The goal is to see if our algorithm is able to discover a subgroup that not only creates a large deviation when removed, but is also very local Pareto front wise, i.e., all objects are grouped around a small part of the Pareto front. We run our EPFDM method with HV dev and HD, and we report the results in Figure 6.

As can be seen, using EPFDM with HV dev , we were able to retrieve a small subgroup, which actually corresponds to the planted subset. However, with HD, we find a larger subgroup. Although the subgroup also contains the planted sub- set, it also contains numerous other objects that were not expected. Therefore, the HV dev measure might be better suited to discover small local subgroups.

Let us now consider use cases that are less familiar within the MOO community. Here, the data is limited to the available set (i.e., it cannot be easily extended) and the underlying model is unknown, making it impossible to run something else than a Pareto front computation.

The first dataset -named Obesity -records eating habits and physical conditions of people from Mexico, Peru and Colombia. It was downloaded from the UCI repository [START_REF] Dua | UCI Machine Learning Repository[END_REF]. It is made of 2111 observations, 14 descriptive variables and 2 objective variables to be optimized: the height that needs to be minimized and the weight that needs to be maximized. In doing so, we want to identify individuals with a worse height-weight trade-o↵. On this dataset, equal-width discretization was found to be the best method. We compute the best models found with HV dev and HD, and we report the results in Figure 7. The deviations found by the two measures look relatively di↵erent, although the objects from their subgroup are similar. It can be seen when looking at their respective subgroup descriptions: Indeed, we notice that the two descriptions di↵er on only one attribute that can create a large di↵erence in the Pareto front deviation models. We can summarize this di↵erence as follows: the first subgroup represents young people with bad height/weight trade-o↵s, while the second subgroup concerns poor people who use public transportation and have a worse height/weight trade-o↵ than the rest of the population. Let us now consider a third experiment about the trade-o↵ between physical and chemical defense in plant seeds. The dataset named Plant is made of 163 observations. It was extracted from the Datadryad website3 . Each observation described by two variables: the family and the mass of the plant seed. The objective variables are the fiber -physical defense -and the tannin -chemical defense -contents that both need to be maximized. Again, we compute the best subgroup found with the same measures as for Obesity. Here, binary representations was found to be the best discretization method. The results, reported in Figure 8, show two substantially di↵erent deviation models, supported by subgroup descriptions. For HV dev , the subgroup description is hmass < 0.146' i, while for HD, the description is hmass > 0.006, mass < 0.0708i. The first subgroup represents a large subset of plants with no particular observable characteristic, while the second is smaller and involves plants with a restricted weight.

Although we have only considered mining for the best subgroup (i.e., top-1), a relevant task could involve looking for the top-K subgroups. We therefore computed the top-5 subgroups on the Plant dataset with both HV dev and HD, and studied their descriptions. While the first two subgroups were significantly di↵erent for both measures, the others represented slightly modified versions of the first two. This underlines the diversity issue of top-K EMM, and motivates the exploitation of skyline patterns [START_REF] Soulet | Mining dominant patterns in the sky[END_REF] to discover more diverse sets of patterns.

The last dataset named RealEstate has been downloaded from the UCI repository [START_REF] Dua | UCI Machine Learning Repository[END_REF]. It concerns over 400 sales of houses in Taiwan between 2012 and 2013. It is made of 4 descriptive variables (latitude, longitude, house age, and number of convenience stores within walking distance) and 2 objective variables: the price of the house and the distance to the closest massive rapid transit station that both need to be minimized. We compute the best subgroup found by our algorithm with HV dev and HD, and we report the results in Figure 9. Binary representations was found to be the best discretization method here. The measures found di↵erent deviation models. The subgroup description for HV dev is hlatitude < 24.963, longitude < 121.5386, house age > 11.89i while the subgroup description for HD is hlatitude < 24.963, house age > 6.6, number of convenience stores > 5i. The exploitation of these subgroupsi.e., using the constraints on attribute values provided by the description -can lead to finding houses (including their location and characteristics) that o↵er an interesting trade-o↵ between price and distance to the nearest transport station.

Quantitative Evaluation of EPFDM

As the quality measure introduced o↵ers multiple degrees of freedom, it makes sense to look at the running time issues of our process. We first carry out a running time comparison of EPFDM between the 4 proposed deviation measures. To do this, we run our algorithm standard parameters on the four previous datasets for each measure and we report the results in Table 2. The di↵erence in running time between quality measures is small to non-existent on small datasets. However, on a larger dataset like Obesity, HV dev seems to be faster than other measures, while MHD and AHD are closer in running time and HD has the highest execution time. We studied the size of the subgroups, as well as the number of subgroups evaluated by each measure, and found that neither could explain the time discrepancies. The running time di↵erences between measures seem to be pretty small, might not be statistically significant, and could simply be related to more or less e cient implementations. To conclude, choosing one measure or another should not be made according to expected running time e ciency. Let us now discuss the running time e ciency when looking for the locality and the generality. Here, we carry out a comparison on our 4 datasets. For each dataset, we use di↵erent configurations for the evaluation of both the locality and the generality. For the locality of the subgroup, possible values for the importance factor are taken in {0.1,0.5,1}. It is expected that lower (resp. higher) values for the locality factor favor large (resp. small) subgroups. Regarding the MSV function for the generality of the model, possible minimum support values are taken in {0.1,0.3,0.5}. When Coverage or Entropy is selected instead of MSV , the values for the factor that controls the importance of the generality of the model are taken in {0.1,0.5,1}. Results of the empirical study are in Table 3 where loc denotes Locality.

First, we can see that using Entropy or Coverage, regardless of their factor value, seems to yield the worst results in terms of running time. Furthermore, for larger datasets like Obesity, the execution could not finish within 24 hours when using either Entropy or Coverage. Second, it seems that there is no running time di↵erence between algorithm configurations that use either Entropy or Coverage. Configurations using MSV with minimum support of 0.5 yield the fastest execution times: this is indeed expected because the number of potential subgroups to explore gets lower when the minimum support value goes up. We find no notable running time di↵erences between configurations of the locality factor for small datasets. However, with a larger dataset like Obesity, we can see that depending on the chosen minimum support, di↵erent values for the locality factor yield significant running time disparities.

Relevance of EPFAM

The goal here is to investigate the relevance of EPFAM on the same datasets as EPFDM, using HV approx . For each dataset, we report the best approximation of the true Pareto front found according to the algorithm configuration. The best model found for each dataset is depicted in Figure 11. On Fonseca, we can see that the approximation found fits almost perfectly the true Pareto front and the subgroup is very small. Furthermore, the subgroup description which is hx1 = [ 0.8, 0.8], x2 = [ 0.8, 0.8], x3 = [ 0.8, 0.8]i supports the easy generation of very high quality solutions close to the true Pareto front. Indeed, if one wanted to generated new high quality solutions with a high probability, he could sample new data points whose attributes values lie in the intervals of values provided by the subgroup description.

Next, we want to see if we can discover a planted subgroup using EPFAM. We first generate 10 objects whose attribute values belong to the following domains: hx1 2 [ 0.8, 0.8], x2 2 [ 0.8, 0.8], x3 2 [ 0.8, 0.8]i. This way, we generate a small subset of objects with high quality that we want to retrieve. We then generate a new Fonseca dataset -named FonsecaPlanted2 -made of 1000 random objects, although we generate the objects so that none of them can a↵ect our planted subgroup. The goal is to see if our algorithm is able to discover a subgroup that approximates well the true Pareto front. We run our EPFAM method with HV approx and we report the results in Figure 10. As can be seen, with EPFAM we easily discover the planted subgroup, which is the subgroup whose Pareto front best approximates the true Pareto front.

Regarding Obesity, we also find a very good approximation of the true Pareto front, supported by the following description:

h Gender = 'Female', Frequency consumption vegetables = 3, Age 2 [13.953, 23.4], family history with overweight = 'yes', Consumption alcohol = 'Sometimes' i This approximation corresponds to young women with a family history of obesity and alcohol consumption despite their young age. It is however interesting to note that these women have a high frequency of vegetable consumption.

When looking for the best approximation in Plant, we find a good approximation of the Pareto front, supported by the description hf amily = 'Combretaceae', mass > 0.00251i. Therefore, the family of plants known as 'Combretaceae' with a minimum weight of 0.00251 appears as representative for a high quality trade-o↵ between physical and chemical defense in plant seeds.

Finally, we study the best model found on the RealEstate dataset. We again find a very good approximation of the true Pareto front, supported by a very small subgroup whose description is: hlatitude > 24.955, latitude < 24.963, house age > 3.5, number of convenience stores > 5, number of convenience stores < 7i. Exploiting such a subgroup can allow for the easy discovery of houses that o↵er more interesting trade-o↵s between price and distance to the nearest transport station.

It is interesting to note that both EPFDM and EPFAM can find the same exceptional model, but for di↵erent reasons. Indeed, it sometimes happens that the subgroup which creates the largest deviation of the true Pareto front is also the subgroup which best approximates it. Please note that this could be due to us using the same locality and generality parameters for both EPFDM and EPFAM. While this makes sense for fairness of comparison and working without a priori knowledge, using configurations of EPFAM where the generality of the model needs to be maximized could lead to much di↵erent results from those found with EPFDM.

Quantitative Comparison of EPFDM and EPFAM

Since di↵erent configurations of the algorithm have already been considered in Section 4 for several datasets, the same study is not needed for EPFAM. However, studying the running time of EPFAM using HV approx on di↵erent datasets and comparing it to EPFDM using HV dev is relevant. The results of these evaluations are available in Table 4. EPFAM is 2 to 7 times faster than EPFDM on all datasets. It makes sense as the most expensive part of the process is the Pareto front computation of each subgroup, and the Pareto fronts in EPFAM are typically much easier to compute than in EPFDM. Indeed, in EPFDM, the Pareto front is computed on the complement of the dataset once the subgroup has been removed, while for EPFAM the Pareto front is computed on the subgroup itself. Since we generally favor small subgroups, the complement is much larger than the subgroup, hence the computation is faster for EPFDM than for EPFAM. Urban farming enables the growth of plants in fully controlled environments close to the end-consumers [START_REF] Harper | Openag: A globally distributed network of food computing[END_REF]. These farms allow for the removal of pesticides and a significant reduction in water consumption, while being able to optimize both the quantity and quality of plants (e.g., improving the flavor [START_REF] Johnson | Flavor-cyber-agriculture: Optimization of plant metabolites in an open-source control environment through surrogate modeling[END_REF], their chemical proportions [START_REF] Wojciechowska | E↵ects of led supplemental lighting on yield and some quality parameters of lamb's lettuce grown in two winter cycles[END_REF] or their yield (Millot et al., 2020b)). The number of parameters influencing plant growth can be fairly large (e.g., temperature, hygrometry, water pH level, nutrient concentration, LED lighting intensity, CO 2 concentration).

In urban farm environments, these parameters can all be controlled from the moment the crops are planted up to the day of harvest. Not only can experts specify a priori the expected values for these descriptive attributes but the actual values can also be recorded through sensors during the whole plant growth process. There are numerous ways of measuring the relevance of the crop end-product (e.g., cost, yield, size, flavor or chemical properties). In other words, the value of a given crop can be quantified with respect to a few di↵erent numerical objectives. Given the di↵erent growth stages for a given plant, the concept of growth recipe consists in the aggregation of the growth conditions set at each stage, and it can be evaluated by one or several numerical objectives. Our goal is to discover the characteristics of an optimized growth. Experts can then exploit these characteristics to improve recipes. It is worth noting that in the context of plant growth optimization, the underlying model is unknown, preventing the use of traditional genetic or evolutionary methods. Moreover, experiments have to be run in batch (i.e., sets of recipes are tested in parallel) and in very limited occurrences (i.e., the number of recipes for each test set is low) due to time and cost constraints.

Plant Growth Recipe Optimization

Earlier, we tackled the problem of recipe optimization with a single objective, the yield, using subgroup discovery (Millot et al., 2020b). Notice however that looking for better recipes that optimize only the yield in a fully controlled environment may be fairly easy (i.e., using more light, enforcing higher temperatures, etc). It makes little sense to optimize the yield while ignoring other aspects like, for instance, the cost: the recipe optimization problem is intrinsically multi-objective. Here we investigate the optimization of plant growth recipes for any number of objectives by leveraging our contributions on EMM. We expect to extract interesting pieces of information on the Pareto front of recipes, such as hollow parts of the objective space (i.e., zones where more data on recipes is needed), interesting local zones containing very good recipes, anomalous recipes, and subsets of recipes representing a good approximation of the overall model.

A Synthetic Data Generator

We consider urban farm recipe optimization as a main application of our methods, as this research is partially funded by a project on urban farms optimization. However, the project is still in early development and we therefore do not yet have access to real farming data. Yet, we were able to perform an empirical study of our proposed approach on this use-case thanks to a crop simulation model, the Python Crop Simulation Environment PCSE4 simulator. The PCSE was originally designed to build crop simulation models for conventional farming (i.e., crops growing outside in fields, in non-controlled environments). The PCSE process is depicted in Figure 12.

Figure 12: Illustration of the PCSE simulation process. The process takes a set of files as input data, then simulates the growth of the crops, and outputs a file with the day by day evolution of the yield.

To simulate the growth of a given crop, the model needs several files as input. First, the soil file contains information on the physical properties of the soil, such as water retention, hydraulic conductivity and soil workability. Second, it needs a crop file that defines which crop is simulated: it describes the crop growth process according to numerous parameters. Notice that we selected the sugar beet as reference crop for all our experiments hereafter. Next, it needs an agromanagement file, that contains the schedule for agromanagement processes such as irrigation, weeding, nutrient application and pest control. Finally and most importantly for us, it requires a weather file that provides daily values for several weather variables. This file defines important growing conditions of the plants day by day. Normally, it would contain real weather data extracted from one of the sources supported by PCSE. Since we have full control on the Weather file that is used as input of the simulator, we can set our own values for each variable and each day, making it possible to simulate plant growth in controlled conditions. The complete list of variables which can be used to control the environment can be found in Table 5. We can control some of the most important variables that drive the plant growth process. We need to be able to set values for each variable and each day of the plant development. After in-depth investigation of each variable according to the PCSE documentation, we choose values for each variable as follows: IRRAD takes values in [10000,30000], RAIN takes values in [5,[START_REF] Li | Quality evaluation of solution sets in multiobjective optimisation: A survey[END_REF], WIND is taken in [0,20], VAP takes values in [1.1,1.6], TMIN is taken in [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]22] and finally, TMAX takes values in [23,[START_REF] Li | Quality evaluation of solution sets in multiobjective optimisation: A survey[END_REF]. Table 6 depicts an example of recipe considering each day between the planting of the crop and its harvest as a distinct growth stage. Having that many growth stages does not make sense since (i) the growth process for most plants takes weeks to months, (ii) we know from the literature that the growth process of many plants can be split into just three stages. For this reason, we have been splitting the Weather file to consider 3 stages using the following method: (i) we define the number of days of the growth process until harvesting, (ii) we divide this number by 3 (i.e., 3 stages) which defines the length of a stage, (iii) for each stage, we define a unique value for each variable, that will be repeated for as many days as needed in the weather file. An example of the end result of this process for a crop whose growth process takes 300 days is available in Table 7. The PCSE process outputs as result the state of the plant day by day from the time of planting (d 1 ,y 1 ), up to its harvest (d n ,y n ) -see Figure 12. However, while the simulator provides us with the yield, it was not built to output the cost of a given crop. We decide to consider the cost as being an energy cost for each recipe. Thanks to expertise from our partner designing urban farms, we were given access to the detailed energy consumption of their pilot farm for each environment variable. From this data, we were able to apportion the energy consumption among the environment variables of the farm (which are di↵erent from, but close enough to the PCSE variables). However, this information is confidential and cannot be reported here. It was then possible to define an approximate percentage of total energy consumption for each variable of the PCSE model. The results are as follows : RAIN represents 24.61% of the energy cost of a recipe, IRRAD 49.22%, WIND 5.15%, VAP 10.74%, TMIN 5.14% and TMAX 5.14% too. The cost of a recipe is then computed the following way: (i) we normalize variables so that their values fall between 0 and 1, (ii) each variable of the recipe is multiplied by its share of the total energy consumption, (iii) we add the values obtained for each variable and divide the total by the number of stages, such that the final cost of the recipe falls between 0 and 1.

Exploiting EPFM to Optimize Recipes

To apply our EMM approaches to plant growth optimization, we randomly generated 300 recipes of sugar beet using the simulator. Recipes are described by 6 variables (RAIN, IRRAD, WIND, VAP, TMIN, TMAX) and are split into 3 stages (P1, P2, P3), for a total of 18 descriptive variables for each recipe. For each recipe, we extract its yield and compute its cost according to the detailed method. Randomly generated examples of such recipes can be found in Table 8.

We kept the number of recipes low on purpose to simulate a real life urban farm where the number of experiments is limited by numerous constraints. To speed up the computation, we discretize the numerical descriptive attribute values and replace them with nominals of cardinality equal to the number of bins. We use a discretization by means of equal-width with 2 cut points (i.e., 3 bins), as it was the discretization that yielded the best results in terms of quality measure when dealing with datasets involving variables with uniform distributions. In the following experiments, we compute the best models returned by our algorithm for EPFDM with HD and HV dev . Figure 13 depicts the best model found for each measure. The model found with HD is composed of recipes that highly optimize the yield, but show poor performance cost-wise. The description of the subgroup is the following : hIRRAD P 3 = [20000, 30000], T P M AX P 2 = [23, 26.5], IRRAD P 2 = [20000, 30000], T P M AX P 3 = [23, 26.5]i. It supports what can be observed in the figure: with high values of solar irradiation and maximal temperature during most of the growth process, the yield will be optimized, at the price of a very high cost for the recipes. This exceptional model is interesting since it represents a locally interesting part of the Pareto front that can be exploited. Indeed, it seems that this part of the Pareto front contains recipes whose trade-o↵ between yield and cost might not be optimal compared to other parts of the front. This is confirmed by the severe deviation in the Pareto front shape once the subgroup is removed. This information can be exploited: when generating new recipes, we can make sure that they do not fall in the description space of the subgroup, lowering the chances of generating recipes with sub-optimal trade-o↵s. With HV dev , we find a model that creates a large deviation that a↵ects most of the Pareto front. This subgroup is interesting as well. Its description can be exploited to generate new recipes that will provide good trade-o↵s between yield and cost. The models found with HD and HV dev are complementary when generating new recipes: the first one can be used to exclude parts of the search space where bad recipes exist while the second helps to focus on promising parts.

EPFDM is more useful as an exploratory tool that enables the discovery of interesting knowledge for MOO problems and it cannot be relied upon to design new, more optimized growth recipes. EPFAM was designed to directly answer this kind of problem.

Let us now consider the exploitation of EPFAM to iteratively optimize the yield-cost trade-o↵ of recipes. We will use the following method to optimize recipes: (i) we first run EPFAM to find a good approximation of the overall Pareto front of the original set of recipes (ii) we retrieve the description of the corresponding subgroup (iii) we use the description to apply new restrictions on the domain of values of the corresponding variables (iv) we generate a new set of recipes, and back to (i) if the quality has improved su ciently. This simple iterative process exploiting EPFAM can be applied successively until no further optimization can be made. It can be seen as a generic virtuous circle, where each new iteration uses information previously gathered to iteratively improve the targeted process. In this application scenario, we decided to apply this process until we either found two iterations in a row with no improvement in the hypervolume of the dataset or until we reached 10 iterations. Please note that for fair comparison, the hypervolume of each dataset of recipes has to be recalculated after each iteration, since the reference point (built out of the worst values found for each objective out of all the recipes encountered) can change at each generation of a new set of recipes.

The best approximation found can be observed in Figure 14 It is concise and understandable, making it easy to exploit when designing new and hopefully better recipes. We use the description of the best subgroup previously found with EPFAM to apply restrictions on the generation of new recipes. For each environment variable that occurs in the subgroup description, the corresponding restrictions are applied to the values of the newly designed recipes. Then, we generate 300 random new recipes using these restrictions and compute their corresponding yield and cost (in a real-life scenario, it would be equivalent to planting the crops, letting them grow fully according to their new recipes, and then retrieving their yield and cost). The hypervolume of the new dataset is then computed and we check whether it has improved from the previous iteration, which is the case. Following the process, we once again apply EPFAM on the dataset of the second iteration, and so on until we reach 10 iterations or 2 consecutive iterations with no improvement.

In this case, the process reached 10 iterations, and let us have an in-depth discussion about its results. Figure 14 (right) depicts a comparison between the Pareto front of each of the 10 iterations. First, we can see that the Pareto front improves iteration after iteration, and seems to converge after the ninth or tenth iteration. The improvement during the first iterations is substantial, and then, as we get closer to the hidden true Pareto front, the improvement slows down but continues until the last iteration. The only iteration where no improvement was observed is the fourth iteration, which could be due to the inherent randomness of the recipe generation. These observations are confirmed by the numbers available in Table 9. When studying the hypervolume of the di↵erent iterations, we can clearly see a large improvement iteration after iteration, putting aside Iteration 4 where a slight decrease was observed. In the end, the improvement from the first to the last iteration is substantial: the first iteration had a hypervolume of 0.57, while the last iteration of recipes features a hypervolume of 0.88, which represents an improvement of 54% of the quality of the Pareto front. We also observe that the final set of recipes features much better trade-o↵s than the original set, with the average yield going from 0.62 to 0.35, and the average cost going from 0.60 to 0.19. It is interesting to note that while the standard deviation of the cost improves throughout the process, the standard deviation of the yield remains unchanged.

Let us now discuss the improvement of the yield and cost between the start and the end of our optimization process. Table 10 depicts the results. We transformed the normalized values back into their original form, i.e., the yield needs to be maximized and the cost needs to be minimized. As can be seen, the average yield between the original recipes and the final recipes has improved by over 70%. Furthermore, the average cost of each recipe has been lowered by over 30%, allowing us to easily generate recipes with substantially better yield-cost trade-o↵s than originally. Finally, the standard deviation of both variables has decreased, allowing us to generate very good recipes at a higher rate (i.e., less randomness). It confirms the relevance and actionability of our iterative process Although we have demonstrated that our contributions can be exploited to substantially improve the growth of recipes in a multi-objective optimization context, we now want to compare it to a random search method to prove its relevance compared to a well-known search model. Indeed, random search is widely used in numerous optimization applications, such as hyperparameter optimization, and is known for being very simple to understand and providing good results with a relatively limited amount of objects.

To compare those methods, we generate 3000 random recipes, using for each variable the domain of values that were used for the first iteration of our own process. We choose the number 3000 since, in our own process, we ended up generating 3000 recipes (i.e., 300 recipes ⇥ 10 iterations). The goal is then to compare the quality of the 3000 randomly generated recipes with that of the last set of recipes of our process.

Figure 15 depicts the comparison between those 2 sets of recipes. As can be seen, the set of recipes created through our method o↵ers significantly better results than those generated through random search. Moreover, every single recipe generated through our method is better than the Pareto front of the random search (i.e., our 300 recipes are non-dominated by the 3000 random search recipes).

These observations are confirmed by the numbers available in Table 11. Indeed, as can be seen, both the average yield (0.37 vs 0.65) and the average cost (0.18 vs 0.55) of our recipes are much more optimized than those of the random search. Finally, the superiority of our approach is also confirmed by the much better hypervolume of our Pareto front (0.86 vs 0.68). Through this indepth application scenario to plant growth recipe optimization, we have shown (i) the relevance of our method to solve such problems (ii) the actionability of EPFAM (iii) the superiority of our EMM-based approach compared to a random search model. Let us go further on recipe optimization by considering now more than two objectives. We generate 300 new recipes using the same process as described before, but this time we also exploit a third objective provided by the PCSE model for each recipe: the total weight of unusable plants (TWP). Indeed, for each recipe, the model computes the amount of usable (that we call the yield, but it actually corresponds to the total weight of storage organs) and unusable produced plants (that we call TWP, and it actually corresponds to the sum of the weights of leaves and stems).

Once our new recipes generated, we run our EPFDM algorithm with HV dev and we report the best computed model. When dealing with Pareto fronts that are more than two-dimensional, one way to study their characteristics is to use scatter plots and visualize the pair-wise relationship of objectives (see Figure 16). As can be seen on each of the 3 scatter plots, the removal of the subgroup leads to large deviations in all 3 pair-wise relationships that compose the overall Pareto front. It is particularly clear in the yield/cost scatter plot where the removal of the subgroup leads to a worse trade-o↵ between yield and cost. The subgroup can be exploited to generate new recipes that not only o↵er good trade-o↵s between yield, cost and TWP, but also o↵er a better trade-o↵ between yield and cost. Let us use the EPFAM method also. It is used with HV approx and we report the best computed model in Figure 17. We are able to find a small subgroup that approximates very well the overall Pareto front of the problem. It can be used to support the design of new recipes whose trade-o↵ between yield, cost and TWP will be close to or even on the optimal Pareto front.

Exploiting Skyline Patterns for EPFDM

Although we have been using an aggregated quality measure (q EP F DM or q EP F AM ) up to this point, it can be argued that when a quality measure consists in the multiplication of several objectives (deviation or approximation, locality, generality), loss of information and sub-optimal subgroups may be discovered. Furthermore, when using top-K EMM, the value of K can be di cult to choose, and the top subgroups usually lack diversity.

To remedy this problem, we can exploit the concept of skyline patterns [START_REF] Soulet | Mining dominant patterns in the sky[END_REF] to mine for subgroups that o↵er the best trade-o↵ between the di↵erent objectives of our quality measure. Using this method, the optimal number of subgroups returned does not have to be pre-defined, but will instead be a learned parameter of the model. We want to find the skyline of subgroups for EPFDM using HV dev . We choose HV dev since it has shown the best ability to find interesting and actionable subgroups. Furthermore, we choose EPFDM since looking for multiple subgroups in EPFAM makes little sense. Indeed, EPFAM exploits the aggregated measure to support the discovery of very good approximations of the Pareto front: mining a skyline of approximations seems of low interest in that case.

The skyline of subgroups cannot be computed using the algorithm discussed in Section 4. Indeed, since no order can be defined on the quality of subgroups that belong to a skyline, a typical beam search strategy where the best q patterns of each level need to be retrieved would not work. Instead, like in Van Leeuwen and Ukkonen (2013), we explore the specializations of the best q patterns at each search level, we compute the skyline of patterns of each level, and only the specializations of the skyline patterns of the current level are to be explored in the next level. Throughout the exploration, we add only the overall nondominated patterns to the global skyline, which should not be confused with the local skyline of each level.

We use this modified version of beam search with a "dynamic beam-width" to mine for the skyline of exceptional models. The locality factor is set to 1 and the MSV function is used with a minimum support of 0.1, such that we have 2 objectives to maximize: the quality and the locality of the subgroup. Since we expect functions that need to be minimized, we transform each maximization into a minimization one. Figure 18 depicts the skyline of patterns found using this configuration. Most of the discovered skyline patterns have a high locality and a relatively low quality, while some patterns possess a higher quality at the cost of a poorer locality.

Next, we want to compare the quality and the locality of the skyline patterns with the quality and the locality of the top-K subgroups that are found according to our aggregated measure q EP F DM . To do this, we compute the top-K subgroups using the aggregated measure, and we record the subgroup quality and locality values before multiplying them. To make the comparison as fair as possible, we choose K to be the same as the number of previously found skyline patterns, 18 in this case. As can be seen in Figure 18, the found subgroups with the aggregated measure lack diversity between quality and locality and are mostly grouped in the same subspace of the objective space. Furthermore, only one subgroup found by using the aggregated measure dominates the skyline of patterns: it confirms the relevance of skyline pattern mining to find diverse subgroups of high quality.

Finally, we want to estimate the cost of the diversity of patterns mined using Skyline EMM compared to typical top-K EMM in terms of running time. To do this, we record the running time of several configurations of top-K EMM using di↵erent values of beam-width. The results are available in Table 12. We see that the running times of Skyline EMM and top-K EMM cross each other when the beam-width is set to 10, that is the most common configuration used in our experiments throughout this paper. It shows that the diversity of Skyline EMM is obtained without a negative impact on running time.

Table 12: Running time comparison (in seconds) of EPFDM between q EP F DM denoted q and Skyline. bw is the chosen beam width when using q EP F DM .

Skyline q, bw = 1 q, bw = 3 q, bw = 5 q, bw = 10 q, bw = 20 q, bw = 50 Most distance measures are Pareto non-compliant, including the Generational Distance, the Inverted Generational Distance and the Hausdor↵ Distance, which were used in our work for EPFDM. In EPFDM, we considered distance maximization, i.e., the farther the Pareto front is from the true Pareto front, the better the quality measure value. According to the Pareto non-compliance of our measures, a given Pareto front could have a larger distance to the true Pareto front than an other front, even though it dominates that same front.

Fortunately, the hypervolume, which has been considered for both EPFDM and EPFAM is one of the few existing quality indicators that is Pareto compliant. We therefore advise to use the volume-based measures.

Scaling Dependence of Quality Measures

When the considered objectives possess ranges of values that are incommensurable, most quality indicators require a transformation of the objectives so that they can be comparable, i.e., roughly in the same range. This property is called scaling dependence, and distance-based measures are subject to it. Indeed, without scaling of the objectives, some objectives could contribute more than others to the quality indicator values. This is the case for our distance-based measures, which are scaling dependent, meaning that applying a monotone transformation on at least one of the targets could a↵ect the order of solutions (i.e., subgroups) according to our quality measures. This is a known limitation of distance-based indicators in MOO, which is why scaling of the objectives is advised when using EPFDM with these measures. Please note that, to the best of our knowledge, using scaled targets with distance-based quality measures to compare Pareto fronts is relevant, in line with state-of-the-art MOO, and not comparable to treating the problem as single-objective where a unique solution is optimal.

The hypervolume is scaling independent, meaning that no scaling is needed a priori, and that applying monotone transformations on one or more targets would have no e↵ect on the order of the resulting solutions. Once again, the use of our volume-based measures seems more relevant than the distance-based measures for EPFM.

To verify those claims, we ran a scaling dependence analysis of the HD and HV measures on our synthetic plant recipes dataset. For each measure, we retrieved the top 3 subgroups on the two following datasets: (i) the plant recipes dataset used in our other experiments, which includes a scaling (i.e., a monotonic transformation) of the targets according to our proposed method in Section 4, and (ii) the original plant recipes dataset, with the targets left untouched (i.e., no normalization).

With EPFDM, using HD, all 3 subgroups are di↵erent from each other. For example, the best subgroup found on the normalized dataset is: [5, 17.5]i. This confirms the claim that nor-malization of the targets is crucial for distance-based measures, and that applying monotonic transformations can lead to di↵erent results.

With EPFDM and EPFAM, using respectively HV dev and HV approx , we find the exact same top 3 subgroups for both datasets. This confirms the claim that the hypervolume is scaling independent, which makes it more versatile than distance-based measures.

Conclusion

We investigate cross-fertilization between Exceptional Model Mining and Multiobjective Optimization. Doing so, we extend our preliminary results published in [START_REF] Millot | Exceptional model mining meets multi-objective optimization[END_REF]. We build a new model class called Exceptional Pareto Front Mining. While other approaches that link pattern mining to MOO work at the pattern level [START_REF] Carmona | NMEEF-SD: Nondominated multiobjective evolutionary algorithm for extracting fuzzy rules in subgroup discovery[END_REF][START_REF] Soulet | Mining dominant patterns in the sky[END_REF], EPFM is able to find relevant patterns at the object level. Our first approach EPFDM looks for deviations in the shape of the Pareto front created by the absence of a subgroup of objects, compared to the same Pareto front computed on the whole dataset. Our second approach EPFAM looks for subgroups whose Pareto front approximates exceptionally well the true Pareto front.

Through experiments on both synthetic and real life data, we show the relevance of our methods on several di↵erent use cases. EPFDM can be used as an exploratory analysis tool to discover interesting pieces of knowledge about MOO problems. Notably, it can be used (i) to identify a subspace of the current Pareto front where data might be missing, (ii) to select a subset of better or worse solutions of the Pareto front with an explicit and concise description in the attribute description space, (iii) to identify anomalous parts of the Pareto front. EPFAM can be exploited to find exceptionally good approximations of the true Pareto front. In other words, EPFAM enables the generation of high quality solutions with a higher probability.

We present a promising application of EPFM to plant growth recipe optimization in controlled environments like urban farms. This is a relevant context where (i) data can be collected about many descriptive attributes that trace the recipe application (ii) farmer expectation are intrinsically multi-objective. Indeed, optimizing a single objective, say the yield, is rather easy because we can control the climate and thus, for instance, use more light or increase the temperature. In practice, we also need to minimize the cost and/or the needed energy. Both EPFDM and EPFAM have been applied on a simulated recipe optimization scenario, and we have shown how EPFAM can be e↵ectively exploited in a virtuous circle framework to iteratively and e ciently optimize a given process. When considering this use case, we have also considered Skyline Exceptional Model Mining. It o↵ers a better diversity of subgroups over top-K Exceptional Model Mining, and it does not require the number of returned subgroups to be fixed a priori.

As future work, it seems interesting to integrate our method in a fully developed EMM-based iterative optimization process, as it was done in Millot et al.

Figure 1 :

 1 Figure 1: True Pareto front of the Fonseca-Fleming function (in black) and objects of the Fonseca dataset (in grey). A and B are two random objects in the objective space.

  dataset and P P F dataset = P F dataset \ P F model . Figure 2 depicts the PPFs of P F model (left) and P F dataset (right). In our figures, ND stands for normal data point, SG denotes a subgroup, P F dataset represents the best known Pareto front and P F model represents the Pareto front of a subgroup.

Figure 2 :

 2 Figure 2: Partial Pareto fronts of P F model (left) and P F dataset (right) in Fonseca.

Figure 3 :

 3 Figure 3: Hypervolume of Fonseca with the Nadir point (left) and our reference point (right).

Figure 4 :

 4 Figure 4: Examples of undesirable subgroups whose removal creates a large deviation from the true Pareto front: a large subgroup that covers most of the dataset (left), a low entropy subgroup that only a↵ects one object of the true Pareto front (right).

  front, and b an importance factor. The weighted entropy favors balanced splits over unbalanced ones. It returns 0 when the subgroup has no point on the true Pareto front or the subgroup covers the whole true Pareto front. It returns 1 when a perfect 50/50 split is achieved. This way, our quality measure is driven toward finding more relevant subgroups with enough objects on the true Pareto front. Notice that it introduces a bias against subgroups that cover most of the true Pareto front (or the whole Pareto front) although it can be controlled by tuning the importance factor b.Next, as a second way, let us consider how to use the coverage of the subgroup with regard to the global model. Informally, we compute the percentage of objects of the true Pareto front which are covered by the subgroup. Again, an importance factor can be used to control the weight of the generality.

Figure 5 :

 5 Figure 5: EPFDM best deviations on Fonseca with respectively HV dev , HD, AHD and MHD.

Figure 6 :

 6 Figure 6: Best deviations found in FonsecaPlanted using EPFDM with HV dev (left) and HD (right).

h

  Number main meals = 3, Frequency consumption vegetables = 3, Age 2 [13.953, 23.4], family history with overweight = 'yes', Consumption alcohol = 'Sometimes' i for HV dev , and h Number main meals = 3, Frequency consumption vegetables = 3, Transportation used = 'Public Transportation', family history with overweight = 'yes', Consumption alcohol = 'Sometimes' i for HD.

Figure 7 :

 7 Figure 7: EPFDM best deviations on Obesity with HV dev (left) and HD (right).

Figure 8 :

 8 Figure 8: EPFDM best deviations on Plants with HV dev (left) and HD (right).

Figure 9 :

 9 Figure 9: EPFDM best deviations on RealEstate with HV dev (left) and HD (right).

Figure 10 :

 10 Figure 10: Best approximation found in FonsecaPlanted2 using EPFAM with HV approx .

Figure 11 :

 11 Figure 11: EPFAM best approximations with HV approx on Fonseca, Obesity, Plants and RealEstate respectively.

Figure 13 :

 13 Figure 13: EPFDM best models using HD (left) and HV dev (right).

  (left). We find a subgroup whose Pareto front covers a large part of Pareto front of the dataset. Furthermore, the subgroup covers very few recipes. Its description is hIRRAD P 1 = [10000, 20000], T P M AX P 1 = [23, 26.5], W IND P 2 = [0, 10], T P M AX P 2 = [23, 26.5], W IND P 3 = [0, 10]i.

Figure 14 :

 14 Figure 14: Best approximation found using EPFAM in the original dataset (left) and comparison of the Pareto fronts of the 10 iterations of our EPFAM process (right).

Figure 15 :

 15 Figure 15: Comparison of the yield-cost trade-o↵s of the recipes generated through the exploitation of EPFAM with the recipes generated through random search.

Figure 16 :

 16 Figure 16: Scatter plots of the EPFDM best model with HV dev showing the pair-wise relationship between objectives.

Figure 17 :

 17 Figure 17: Scatter plots of the EPFAM best model with HV approx showing the pair-wise relationship between objectives.

Figure 18 :

 18 Figure 18: Skyline of EPFDM and comparison between Skyline and q EP F DM .

  Compliance of Quality MeasuresIn this work we have considered indicators that enable the comparison of Pareto fronts. We worked with distance-based and volume-based quality measures, that have been inspired by the MOO literature on quality indicators for Pareto fronts comparison[START_REF] Li | Quality evaluation of solution sets in multiobjective optimisation: A survey[END_REF]. A well-known limitation of many quality indicators in MOO is their non compliance with the dominance relation. A quality indicator is said to be P areto compliant[START_REF] Knowles | A tutorial on the performance assessment of stochastic multiobjective optimizers[END_REF], if and only if, when comparing two Pareto fronts, the Pareto front that dominates the other also has a better value in terms of the quality indicator. A quality indicator that is Pareto compliant guarantees that it does not contradict the order of Pareto fronts induced by the dominance relation. Given two Pareto fronts A, B and a Pareto compliant indicator, if A is better than B, then B can never dominate A.

  hIRRAD P 2 = [20000, 30000], IRRAD P 3 = [20000, 30000], T P M AX P 2 = [23, 26.5], T P M AX P 3 = [23, 26.5]i While the best subgroup found on the non-normalized data is: hIRRAD P 1 = [10000, 20000], IRRAD P 3 = [10000, 20000], T P M AX P 1 = [26.5, 30], V AP P 1 = [1.1, 1.35], RAIN P 3 =

Table 2 :

 2 Running time comparison (in seconds) of EPFDM on 4 deviation measures.

	Measure Fonseca Obesity Plants RealEstate
	HV dev	175.4	15426	2.37	40.31
	HD	176.1	17866	2.39	41.79
	AHD	175.7	16690	2.39	41.69
	MHD	175.9	16215	2.38	41.70

Table 3 :

 3 Running time comparison (in seconds) of quality measure parameters on 4 datasets using HV dev . "-" means that the execution was not completed after 24 hours (86400 seconds).

		Gen.		MSV			Entropy		Coverage
	Dataset		0.1	0.3	0.5	0.1 0.5	1	0.1 0.5	1
		loc 0.1	179	128	128 178 177 177 177 177 177
	Fonseca	loc 0.5	177	127	127 177 177 177 177 177 177
		loc 1	182	128	128 178 178 177 177 179 178
		loc 0.1 23189 11188 5213	-	-	-	-	-	-
	Obesity	loc 0.5 16595 11021 6350	-	-	-	-	-	-
		loc 1	15426 13159 6443	-	-	-	-	-	-
		loc 0.1	2.4	0.5	0.5	6.7 6.7 6.6 6.6 6.6 6.7
	Plants	loc 0.5	2.4	0.5	0.5	6.6 6.6 6.6 6.6 6.6 6.6
		loc 1	2.4	0.5	0.5	6.7 6.7 6.6 6.6 6.6 6.7
		loc 0.1	41	6	3	108 109 109 113 113 112
	RealEstate	loc 0.5	41	6	3	108 109 109 113 113 112
		loc 1	41	6	3	100 107 109 108 113 113

Table 4 :

 4 Running time comparison (in seconds) of EPFDM using HV dev and EPFAM using HV approx on 4 datasets.

	Dataset Fonseca Obesity Plants RealEstate
	EPFDM	175.4	15426	2.37	40.31
	EPFAM	23.5	2320	0.88	7.69
	8 Optimizing Plant Growth Recipes in Controlled
	Environments

8.1 Vertical Urban Farms and Plant Growth Recipes

Table 5 :

 5 Weather file variable description.

	Name	Description	Unit
	RAIN IRRAD WIND VAP	Precipitation (rainfall or water equivalent in case of snow or hail) Daily global radiation Mean daily wind speed at 2 m above ground level Mean daily vapour pressure	cm • day 1 J • m 2 • day 1 m • sec 1 hP a
	TMIN	Daily minimum temperature	°C
	TMAX	Daily maximum temperature	°C

Table 6 :

 6 Example of Weather file: growing conditions for a given plant day by day.

	Day RAIN IRRAD WIND VAP TMIN TMAX
	d 1	10	23250	15	1.2	15	27
	d 2	12	18250	12	1.4	16.5	23.4
	d 3	14	24560	7	1.35	17.8	21.5
	...	...	...	...	...	...	...
	d n	8	14950	22	1.1	21.1	29.9

Table 7 :

 7 Example of Weather file: growing conditions for a given plant stage by stage.

	Stage	RAIN IRRAD WIND VAP TMIN TMAX
	P 1 (d 1 -d 100 )	11	13250	19	1.39	18	26
	P 2 (d 101 -d 200 )	14	15976	9	1.26	15	21
	P 3 (d 201 -d 300 )	24	28390	18	1.42	19	29

Table 8 :

 8 Examples of growth recipes split in 3 stages (P1, P2, P3), 6 attributes, and 2 objectives (Yield and Cost). R RAIN P 1 IRRAD P 1 ... P 1 RAIN P 2 IRRAD P 2 ... P 2 RAIN P 3 IRRAD P 3 ... P 3 Yield Cost

	r1	10	23250	...	10	23250	...	15	21000	...	22000 0.56
	r2	35	10000	...	5	25000	...	16	19500	...	20500 0.60
	r3	15	17500	...	22	15000	...	30	4000	...	8600	0.65
	r4	18	22800	...	38	17000	...	38	12000	...	14200	0.7

Table 9 :

 9 Comparison of the average, median and standard deviation values of both the yield and the cost, and comparison of the hypervolume between the original set of recipes and the sets of recipes generated at each iteration. Y ield avg Cost avg Y ield med Cost med Y ield std Cost std Hypervolume

	Original recipes	0.62	0.60	0.60	0.59	0.26	0.15	0.57
	Iteration 2	0.55	0.54	0.49	0.51	0.24	0.13	0.61
	Iteration 3	0.61	0.35	0.60	0.35	0.23	0.1	0.73
	Iteration 4	0.54	0.32	0.49	0.33	0.25	0.1	0.70
	Iteration 5	0.48	0.26	0.42	0.26	0.25	0.09	0.76
	Iteration 6	0.44	0.24	0.37	0.24	0.27	0.09	0.80
	Iteration 7	0.41	0.23	0.32	0.22	0.27	0.09	0.84
	Iteration 8	0.36	0.22	0.30	0.22	0.25	0.08	0.86
	Iteration 9	0.38	0.19	0.29	0.19	0.26	0.08	0.87
	Iteration 10	0.35	0.19	0.26	0.19	0.26	0.08	0.88
	to solve MOO problems.

Table 10 :

 10 Comparison of the average, median and standard deviation nonnormalized values of both the yield and the cost between the original and the last set of recipes. Y ield avg Cost avg Y ield med Cost med Y ield std Cost std

	Original recipes	10055	0.54	10640	0.54	7074	0.07
	Iteration 10	17338	0.36	19727	0.36	6849	0.04

Table 11 :

 11 Comparison of the average, median and standard deviation values of both the yield and the cost between our optimized set of recipes and the set of recipes generated through random search. Y ield avg Cost avg Y ield med Cost med Y ield std Cost std Hypervolume

	Iteration 10	0.37	0.18	0.28	0.18	0.25	0.08	0.86
	Random recipes	0.65	0.55	0.64	0.55	0.25	0.14	0.68

https://aerofarms.com/, https://infarm.com/, https://boweryfarming.com/. Accessed on 13/09/2021.

http://jmetal.sourceforge.net/problems.html

https://datadryad.org/stash/dataset/doi:10.5061/dryad.bv5ht

https://pcse.readthedocs.io/en/stable/index.html

(2020b) for the case of a unique objective. It seems like a logical next step to fully exploit EPFM potential for multi-objective optimization.

This research is partially funded by the FUI DUF 4.0 French programme (2017-2021) and a CAF America grant (2020-2021).