Renée El

Melhem Bat

Blaise Pascal

Insa : R Gourdon

M Stéphane

M Gérard Scorletti
email: gerard.scorletti@ec-lyon.fr

Je Remercie

Sihem Amer-Yahia

Moustafa Bensafi

Marc

à remercier Toon Calders, professeur à l'Univesiteit Antwerpe et Tristan Cazenave, professeur à l'Université Paris-Dauphine, d'avoir accepté d'être rapporteurs de ce manuscrit de thèse. Je les remercie particulièrement pour le travail considérable qu'ils ont consacré à la lecture assidue de ce mémoire

List of Tables

The extension of the label dataset from Table 7 to the multi-label dataset version.

Knowledge discovery in databases

With the exponentially growth of data in the world, the need to extract and derive knowledge from this so-called big data is more important than ever. Indeed, smartphones with a GPS tracker are carried in the pocket of billions of people around the world: Tens of billions of trajectories are available. Moreover, the marketing of smart watches makes available a huge amount of health data that are collected from the customers' wrist. In addition, there is a data explosion in science: Numerous scientific data are available in several domains. For example, in biology, several DNA databases have been released to gather nucleotide sequence data from all organisms; genome databases collect genome sequences; or other databases concern the protein structure models. In astronomy, there are databases that gather billions of images taken by telescopes such as Hubble Telescope. With the multiplication of online tools that provide data on almost every application domain, it is now possible to get large amount of data. For instance, one can crawl thousands of physico-chemical properties for tens of thousands of molecules such as the molecular weight, the number of carbon atoms or the unsaturation index.

The goal is now to analyze this available data to elicit some knowledge. For instance, from the images taken by telescopes in the astronomy domain, some planets have been found and the scientists suggest, based on the data they collected, that they are possibly habitable. Deriving knowledge from raw data is a difficult task. For that, a process called Knowledge Discovery in Databases (KDD) has been proposed. This process aims to extract some knowledge from the data that is non trivial, new and actionable by the experts of the domain [START_REF] Brachman | The process of knowledge discovery in databases[END_REF][START_REF] Fayyad | From data mining to knowledge discovery: An overview[END_REF]. Even if this KDD process was defined twenty years ago, it remains relevant to this day.

The KDD process is a user-centered approach. It is composed of five steps, from the selection and the preparation of the data to the interpretation of the results after a data mining task (see Figure 1). This process was guided by the need to analyze large amount of data that was initially studied manually by the experts of the domain. The goal is to transform a raw and low-level data into other forms that might be cleaner and easier to study. The study is performed thanks to the data mining step that is the heart of the KDD process, and the result of this step is visualized and interpreted by the experts to highlight hypotheses and, hopefully, to draw tangible conclusions. Basically, each of the five steps can be defined as follows:

• Selection: This step consists in selecting the data in which we are interested from the raw data that has been collected. The selected data is called the target data. For example, one can select the period of interest, a geographical area or a specific market to analyzed the purchased products.

1 Figure 1: An overview of the KDD process (source: [START_REF] Fayyad | From data mining to knowledge discovery: An overview[END_REF]).

• Preprocessing: This step aims at cleaning and preparing the target data. Missing values can be handled in different ways, such as predicting it with data mining tools. Besides we can cross-check when combining or summarising data from different sources to avoid misinterpretation. Handling the noise within a data is a common task. For instance, in the images taken by telescopes, it is required to reduce the light noise that can bias the interpretation.

• Transformation: Once the data is preprocessed, sometimes, it is required to transform it to be used as the input of the data mining tool. Indeed, some algorithms require the data in a specified format. Besides, a data reduction can be performed to avoid correlated descriptors that are useless and redundant. Feature selection enables to reduce the number of descriptors to only keep the more relevant ones [START_REF] Guyon | An introduction to variable and feature selection[END_REF]. Moreover, when facing numerical descriptors, a discretization is often performed in pre-processing task to turn them nominal.

• Data mining: This is the heart of the KDD process. From the transformed data, an algorithm explores the data and extract interesting patterns from it. There exists several data mining tasks, such as classification that builds a global model on the data or pattern mining that aims to exhibit local models. Also, one can be interested in outliers detection to identify anomalous behavior in the data. In addition, clustering is a popular method that aims to create so-called clusters of objects [START_REF] Berkhin | A survey of clustering data mining techniques[END_REF]. Objects in the same cluster are more similar (belonging to the same class) to each other than to those in other clusters.

• Interpretation/Evaluation: This is the last but not the least step of the KDD process.

From the patterns extracted with the data mining method, it aims at deriving knowledge that is non trivial and actionable by the experts of the domain. For that, the visualization tools are very useful to understand the results.

Within an inter-disciplinary project, we have worked in collaboration with several neuroscientists and chemists to elicit new hypotheses on the structure-odor relationship (SOR) in olfaction. Our methodology follows the KDD process to derive some new knowledge on the SOR problem from raw data collected by the neuroscientists.

Application in neuroscience to elicit new hypotheses on the olfactory percept

Around the turn of the century, the idea that modern, civilized human beings might do without being affected by odorant chemicals became outdated: The hidden, inarticulate sense associated with their perception, hitherto considered superfluous to cognition, became a focus of study in its own right and thus the subject of new knowledge. It was acknowledged as an object of science by Nobel prizes (e.g., [START_REF] Buck | A novel multigene family may encode odorant receptors: a molecular basis for odor recognition[END_REF] awarded 2004 Nobel prize in Physiology or Medicine); but also society as a whole was becoming more hedonistic, and hence more attentive to the emotional effects of odors. Odors are present in our food, which is a source of both pleasure and social bonding; they also influence our relations with others in general and with our children in particular. The olfactory percept encoded in odorant chemicals contribute to our emotional balance and wellbeing: Olfactory impairment jeopardizes this equilibrium.

Neuroscience studies revealed that odor perception results from a complex phenomenon rooted in the chemical properties of a volatile molecule (described by multiple physicochemical descriptors) further detected by our olfactory receptors in the nasal cavity. Indeed, Figure 2 illustrates the process of the olfactory system: When someone smells a flower, the volatile molecules of the flower come to get binding in the olfactory receptors in the nasal cavity. From each receptor, a neural signal is then transmitted to central olfactory brain structures, i.e, the olfactory bulb [START_REF] Joussain | Physicochemical influence on odor hedonics: Where does it occur first?[END_REF]. At this stage, the combination of all these signals generates a complete neural representation, called "odor" that can then be described semantically by various types of perceptual quality (e.g., fruity, floral or woody).

While it is generally agreed that the physicochemical characteristics of odorants affect the olfactory percept, no simple and/or universal rule governing this Structure Odor Relationship (SOR) has yet been identified. Why does this odorant smell of roses and that one of lemon? Considering that the totality of the odorant message was encoded within the chemical structure, chemists have tried for a long time to identify relationships between chemical properties and odors. Topological descriptors, eventually associated with electronic properties or molecular flexibility were tentatively connected to odorants descriptors. However, it is now quite well acknowledged that structure-odor relationships are not bijective, meaning that the chemical space and the perceptual space connections are more subtle than previously thought 1 . For example, very different chemicals trigger a typical "camphor" smell, while a single molecule, the so-called "cat-ketone" odorant, elicit two totally different smells as a function of its concentration [START_REF] De March | Structure-odour relationships reviewed in the postgenomic era[END_REF]. At best, such SOR rules are obtained for a very tiny fraction of the chemical space, emphasizing that they must be decomposed into sub-rules associated with given molecular topologies [START_REF] Delasalle | Structure-odor relationships of semisynthetic β-santalol analogs[END_REF]. As such, this lack of bijective relationship must be handled. It suggests that a simple, universal and perfect rule does probably not exist, but instead, a combination of several sub-rules should be put forward to encompass the complexity of SOR.

During the preparation of this PhD., we applied a data science approach with a view to advancing the state of the art in understanding the mechanisms of olfaction. We created an interdisciplinary synergy between neuroscientists, chemists and data miners to support the emergence of new hypotheses 2 . For that, we applied the KDD process, from data collection to the discovery of new hypotheses on SOR. Basically, the neuroscientists gathered the data from two different Figure 2: The olfactory system (source: [START_REF] Buck | A novel multigene family may encode odorant receptors: a molecular basis for odor recognition[END_REF]). sources: (i) The Dragon 6 software (available on talete.mi.it), and (ii) the well known atlas Arctander [START_REF] Arctander | Perfume and flavor materials of natural origin[END_REF]. The first one provides the values of almost 5, 000 physico-chemicals properties (e.g., the molecular weight or the number of carbon atoms) for thousands of chemical molecules. The latter is an atlas created by scent experts that maps 1, 689 molecules to subset of odors among 74 olfactory qualities such as Fruity, Vanilin, or Camphor. From these two raw data, the neuroscientists pre-processed the data to keep only the molecules that are present in both of them. Moreover, the chemists identified and pointed out a set of 82 physico-chemical properties that have been known or guessed to be discriminant in SOR. Thus, the final data is made of 1, 689 molecules described by 82 physico-chemical properties and associated to an average of 2.88 odors among the 74 olfactory qualities.

Data mining methods can be applied on this transformed data to address the SOR discovery problem, either through the building of predictive models or through rules discovery. One obstacle to this is that olfactory datasets are "complex" (i.e., several thousand of dimensions, heterogeneous descriptors, multi-label, imbalanced classes, and non robust labelling) and, above all a lack of data-centric methods in neuroscience suitable for this level of complexity. The main aim of our study is to examine this issue by linking the multiple molecular characteristics of odorant molecule to olfactory qualities (fruity, floral, woody, etc.) using a descriptive approach (pattern mining). Indeed, a crowd-sourced challenge was recently proposed by IBM Research and Sage called DREAM Olfaction Prediction Challenge [START_REF]Dream olfaction prediction challenge[END_REF]. The challenge resulted in several models that were able to predict especially pleasantness and intensity and 8 out of 19 olfactory qualities in their dataset ("garlic", "fish", "sweet", "fruit", "burnt", "spices", "flower" and "sour") with an average correlation of predictions across all models above 0.5 [START_REF] Keller | Predicting human olfactory perception from chemical features of odor molecules[END_REF]. Although this is a clinical data (the perception is not given by scent experts), these findings are timely and interesting because they show the existence of a predictive relationship between some olfactory qualities and the physicochemical properties of odorant molecules. Nevertheless, to go further into the understanding of the stimulus-percept issue in olfaction, it is important to explain and thus to isolate physicochemical descriptive rules allowing describing these olfactory qualities (based on scent experts' perception). Identifying such physico-chemical rules characterizing odor quality opens a hitherto little explored field in neuroscience research, shedding new lights on olfactory system functioning. 1. This data concerns 6 molecules given by their ID. Each molecule is described by 3 physico-chemical properties: The molecular weight MW, the number of atoms nAT, and the number of carbon atoms. Besides, each molecule is associated to several odors among strawberry, honey and pear. For instance the scent experts state that Molecule 24 smells honey and pear. From this data, the aim is to identify so-called descriptive rules on the physico-chemical properties that are characteristic of odors. For instance, let us consider the rule xr128 ď M W ď 151s, r23 ď nAT ď 29sy Ñ tHoneyu. The Molecules 24, 48, 82 and 1633 support the body of this rule (i.e., xr128 ď M W ď 151s, r23 ď nAT ď 29sy). Thus, 75% of the molecules verifying the body of this rule smell honey, whereas 50% of the molecules in the data are associated to honey. We can state that this rule is interesting since it means that molecules with a molecular weight below 151 and with at least 23 atoms are more likely to smell honey. Finding such a rule allows to derive some hypotheses and, maybe, new knowledge on the structure-odor relationship.

Example 1. Let us consider the example of an olfactory dataset given in Table

Thus, the extraction of rules on SOR in such an olfactory dataset raises several questions. In the next section, we give an overview on these problems and how we resolve them through our two main contributions.

Age range Gender

Supervised descriptive rule discovery

The discovery of hypotheses on the structure-odor relationship is an interesting application for data mining. Indeed, the complex structure of the data combined with the specific goals of the neuroscientists and chemists, highlight several opened issues that have to be solved. In this section, we do not consider the olfactory data but we illustrate pattern mining within a simpler setting: Market basket analysis. Pattern mining has been deeply studied in the three last decades [START_REF] Giacometti | 20 years of pattern mining: a bibliometric survey[END_REF]. Indeed, it is now commonly taught in textbooks and applied in the industry [START_REF] Tan | Introduction to Data Mining[END_REF][START_REF] Zaki | Data Mining and Analysis: Fundamental Concepts and Algorithms[END_REF][START_REF] Aggarwal | Data Mining -The Textbook[END_REF]. The first works on pattern mining dealt with the extraction of frequent itemsets [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] to discover some association rules between itemsets [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]. An itemset is a set of items, i.e., properties of some objects. For instance, a well known application of association rules concerns the market basket analysis: The aim is to extract rules between products of a supermarket that are often bought together by customers. Table 2 is a toy market data: Each line is about the products purchased by a customer. Note that a product is an item, and a set of products forms a so-called itemset. For example, the second customer has bought beers, vegetables and diapers. A popular anecdote about unexpected association rules states that the customers buying diapers tend also to buy beers. In Table 2, the confidence of the association rule Diapers Ñ Beers is 0.75 since three of the four customers who purchased diapers also bought beers. Thus, from everyday data, some association rules are identified and can then be derived into actionable knowledge: A supermarket can either put diapers close to the beers to reduce the time spent by the customers, or to position them diagonally opposite to force the customer to pass through the supermarket shelves to make him buy more products.

Initially, the market basket data is not labeled: Each line of the data gathers the products bought by a customer. However, more and more applications in pattern mining are based on labeled data. In a labeled version of this market basket data, each of the customers can also be associated to a label, for example male or female. Table 3 illustrates the labeled version of the market basket data of Table 2. Thus, we can exhibit some association rules with high confidence for women but that are not supported by men and vice versa: For instance, the confidence of the rule Diapers Ñ Beers is 1 for men (i.e., all men who purchased diapers also bought beers) and 0.5 for women (i.e., half of the women who purchased diapers also bought beers). Alternatively, the labels can concern the age range of the customers (taking values in tr0, 29s, r30, 59s, r60, 99su), and thus we can find some association rules for a specific age range that is no longer true for other age ranges. It leads to the definition of several supervised data mining tasks. Generally, with labeled data, one is interested into learning a model that can state to which of the groups (also called classes) a new object (e.g., a customer or a molecular molecule) belongs: A typical machine learning task [START_REF] Witten | Data mining: practical machine learning tools and techniques[END_REF]. Support vector machine [START_REF] Hearst | Trends & controversies: Support vector machines[END_REF][START_REF] Suykens | Least squares support vector machine classifiers[END_REF] or deep learning [START_REF] Lecun | Deep learning[END_REF] are techniques dealing with labeled data. They aim at building a classification model that can predict the label (or the class) of a new object. However, such efficient learning methods are black boxes: The user does not know why the algorithm predicts a specific label for an object. They do not allow to exhibit intelligible rules that can be interpreted and understood to be actionable. Note that some learning methods propose intelligible models, such as decision trees, but the model may be weak [START_REF] Safavian | A survey of decision tree classifier methodology[END_REF]. Finding such rules is possible with supervised descriptive rule discovery [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF]. The discovery of descriptions which distinguish a group of objects given a target (class) has been widely studied in data mining and machine learning community under several terms (subgroup discovery [START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF], emerging patterns [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF], contrast sets [START_REF] Bay | Detecting group differences: Mining contrast sets[END_REF], hypotheses in formal concept analysis [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]) [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF]. Let us now consider supervised descriptive rule discovery in the wellestablished framework of subgroup discovery (SD) [START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF]. Given a set of objects (e.g., customers) taking a vector of attributes (of boolean, nominal, or numerical type) as a description (e.g., purchased products), and a class label as a target (e.g., gender), the goal is to discover subgroups of objects for which there is a significant difference between the label distribution within the group compared to the distribution within the whole dataset, e.g. considering the difference of precision with the well-known weighted relative accuracy (WRAcc) [START_REF] Lavrac | Rule evaluation measures: A unifying view[END_REF]. In others terms, it searches for descriptive rules that conclude on a single label with possibly few errors.

However, many datasets exhibit objects associated to several labels. For example, in Table 3, each customer is associated to two labels: The gender and the age range. For these so-called multi-labeled data, SD has been generalized into the exceptional model mining (EMM) framework [START_REF] Leman | Exceptional model mining[END_REF] to capture the more complex relationships that exist in the data between the descriptive attributes (e.g., the products) and the class labels (e.g., the gender of the customer). For that, the notion of model has been introduced. Each set of objects induces a specific model that is built on the class labels. Several models have been proposed in the state of the art [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF], e.g., the linear regression between two numerical class attributes [START_REF] Duivesteijn | Different slopes for different folks: mining for exceptional regression models with cook's distance[END_REF], the contingency tables for several class labels [START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF] or the Bayesian networks computed on the class labels [START_REF] Duivesteijn | Subgroup discovery meets bayesian networks -an exceptional model mining approach[END_REF]. The goal of EMM is to extract subgroups of objects for which the model built on the class labels is significantly different from the model induced by the entire dataset. Figure 3 displays a typical EMM instance. The data is displayed on the left. From the entire data, we can compute the model built on the class labels: This is the red curve. In this example, we can consider that the curve represents the power consumption of a population during one day: For the entire population, there is an increase of the power consumption between 7p.m. and 12p.m.. Then, the subset of objects (called the subgroup) in the green area is selected to be analyzed. We compute the model built on the class labels by this subgroup: This is the green curve. Then a quality measure is used to compare these two models. If the quality measure is high, it means that the models are significantly different: The subgroup of objects is said interesting because it behaves differently on the class labels than the entire set of objects. For instance, we have discovered that this subgroup concerns the night workers. 3. Each consumer is labeled with both its gender and its age range. We can use the model of the contingency tables on the two class attributes gender and age range given is Table 4 for all the customers. The subgroup given by the customers that purchased both beers and diapers contains three people. The contingency table induced by this subgroup is given in Table 5. The total variation distance is then used as the quality measure to compare the two contingency tables [START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF]. This distance sums the absolute difference between each pair of cells divided by 2. Thus, the quality measure is: |0.17´0.33|`|0´0|`|0.33´0|`|0.17´0|`|0.33´0.67|`|0´0| 2 " 0.5. 1. Suppose that we use the probability distribution model. It consists to compare the frequency of a label in a subgroup to its frequency in the entire data. For that, we can use the mean of the WRAcc measure of the subgroup for each label [START_REF] Abudawood | Evaluation measures for multi-class subgroup discovery[END_REF]. First, the relative frequencies of the odors strawberry, honey and pear in the data are respectively 0.67, 0.5 and 0.5. Indeed, four molecules among the six molecules of the data are labeled as strawberry. Let us consider the subgroup containing the molecules with a molecular weight below 151 and with at least 23 atoms. This subgroup is given by the description xr128 ď M W ď 151s, r23 ď nAT ď 29sy . This subgroup contains the Molecules 24, 48, 82 and 1633. The relative frequencies of the odors strawberry, honey and pear in this subgroup are respectively 0.5, 0.75 and 0.75. The WRAcc measure of the subgroup for the strawberry is given by: 4 6 ˆp0.5 ´0.67q " ´0, 11. Similarly, the WRAcc measure for honey is 0.17 and for pear is also 0.17. The mean of these 3 measures evaluate the exceptional behavior of the subgroup on the three odors: The quality measure of the subgroup is 0.08.

Example 2. Let us consider Table

Example 3. Consider the olfactory data in Table

In subgroup discovery and exceptional model mining, the enhancements proposed in the recent works can be divided into three categories: (i) The pattern language, (ii) the model with its quality measure and (iii) the algorithmic method to discover the best subgroups. The improvements on the pattern languages deal with the expressiveness of the patterns: From itemsets to numerical attributes, sequences [START_REF] Agrawal | Mining sequential patterns[END_REF], graphs [START_REF] Cook | Mining graph data[END_REF] and so on. The enhancements on the quality measures consist in proposing new models for EMM to elicit different relationships in the data. The algorithmic improvements concern the methods designed to extract efficiently the best patterns 2 where A, B, C and D respectively correspond to the beers, the milk, the vegetable and the diapers. The value in the bottom of each node corresponds to the WRAcc measure of the itemset w.r.t. the male label. w.r.t. the quality measure in an exhaustive or heuristic way. Nevertheless, there are still open issues that were highlighted when discussing our needs for olfactory data analysis.

Contributions

Monte Carlo tree search for pattern mining

In SD/EMM, the algorithms have to explore the set of subgroups, called the search space, to extract the best ones w.r.t. the quality measure, also called local optima. Basically, the search space contains all the possible subgroups defined by their description, i.e., a list of restrictions on the domain of the descriptive attributes (e.g., the physico-chemical properties). Note that a subgroup is either given by its description or by the set of objects it covers, called the extent. The search space is often a lattice since a partial order exists between the descriptions. Figure 5 represents the lattice of Table 2 where A, B, C and D respectively correspond to the beers, the milk, the vegetable and the diapers. The value in the bottom of each node corresponds to the WRAcc measure of the itemset w.r.t. the male label. Note that the WRAcc measure is not an increasing or decreasing function on the lattice: The WRAcc of a node (i.e., an itemset) can be more or less than those of its parents nodes. The itemsets with the maximum values of WRAcc, also called the local optima, are tCu, tA, Cu, tC, Du and tA, C, Du. In this thesis, we illustrate the lattice with the formalism of Figure 6a: The circles are the subgroups given by their description. The top subgroup is the more general subgroup: It contains all the objects of the data. The red circles are the local optima to find from this search space, i.e., the patterns that cover a set of objects that induces a model on the class labels significantly different from those induced by the entire data. The subgroups above the green curve are the subgroups containing at least minSupp objects, where minSupp is called the minimum support threshold. This constraint ensure to enumerate subgroups that are not too small, because subgroups containing few objects do not bring much information. The goal of SD/EMM is to extract the local optima that are above the green curve. The first algorithms proposed for SD were exhaustive, i.e., they enumerate all the possible descriptions by exploring the lattice of the subgroups [START_REF] Klösgen | Explora: A multipattern and multistrategy discovery assistant[END_REF][START_REF] Atzmüller | SD-map -A fast algorithm for exhaustive subgroup discovery[END_REF][START_REF] Lemmerich | Generic pattern trees for exhaustive exceptional model mining[END_REF]. Thus, exhaustive algorithms ensure to extract the local optima. However, they are not scalable for large data or for complex pattern languages (e.g., for numerical descriptive attributes 3 , as is the case for the olfactory dataset). Indeed, the search space growths exponentially with the number of descriptive attributes and the number of objects. For that, recent works have proposed heuristic algorithms to explore the search space. Up to now, there exists three main heuristic methods for SD/EMM: (i) beam search [START_REF] Klösgen | Census data mining, an application[END_REF][START_REF] Van Leeuwen | Non-redundant subgroup discovery in large and complex data[END_REF][START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Van Leeuwen | Discovering skylines of subgroup sets[END_REF], (ii) evolutionary algorithms [START_REF] Del Jesús | Evolutionary fuzzy rule induction process for subgroup discovery: A case study in marketing[END_REF][START_REF] Rodríguez | Searching for rules to detect defective modules: A subgroup discovery approach[END_REF] and (iii) sampling methods [START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF][START_REF] Bendimerad | Unsupervised exceptional attributed subgraph mining in urban data[END_REF]. Beam search is a greedy method that partially explores the search space with several hill climbings run in parallel [START_REF] Lowerre | The HARPY speech recognition system[END_REF]. It proceeds in a top down enumeration of the lattice, and it only explores a beam within the search space by keeping at each level the most promising subgroups. Figure 6b illustrates this heuristic strategy: It drives the exploration to the nearest best subgroups, ignoring lots of local optima. This strategy is the most popular one in SD/EMM [START_REF] Klösgen | Census data mining, an application[END_REF][START_REF] Van Leeuwen | Non-redundant subgroup discovery in large and complex data[END_REF][START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Van Leeuwen | Discovering skylines of subgroup sets[END_REF]. It quickly finds some (but not all) best subgroups. It generally works well when features have a very high discriminant power independently, i.e., when the local optima are "short" patterns. However, this method clearly lacks of exploration due to its greedy principle, especially when local optima are located everywhere in the search space. A second heuristic approach can exploit evolutionary algorithms. They use a fitness function to select which individuals to keep at the next generated population [START_REF] Bäck | Handbook of evolutionary computation[END_REF]. However, these methods need to set a lot of parameters to model the crossover rate, the size of the population, the process to update the generation, etc. Finally, contrary to the two previous heuristic approaches, sampling methods give a result anytime, i.e., a solution is always available. Sampling techniques are gaining interest because they allow direct interactions with the user for using his preferences to drive the search. However, traditional sampling methods used for pattern mining need a given probability distribution over the pattern space: This distribution depends on both the data and the quality measure [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF][START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF]. Each iteration is independent and consists of drawing a pattern given this probability distribution. Moreover, these probability distributions exhibit the problem of the long tail: There are many more uninteresting patterns than interesting ones. Thus, the probability to draw an uninteresting pattern is still high, and not all local optima may be drawn: There are no guarantee on the completeness of the result set. Figure 6c illustrates the principle of sampling methods: Several areas are sampled based on the probability distribution on the pattern space. Some of them contain local optima, but, due to the long tail problem, some sampled areas do not contain any local optimum.

With the so-called pattern explosion when considering frequent subgroups, the existing methods focus on top-k mining algorithms that aim at returning the k best encountered subgroups w.r.t. the quality measure. However, these approaches face the problem of redundancy: A subgroup with a slight change in its description gives a very similar subgroup and thus the quality measure of these subgroups are similar. In Figure 6a, in the area closed to the local optima, there are similar subgroups that are redundant with the local optimum. In top-k mining methods, a similarity measure is used as post-processing step to compare two subgroups to avoid the presence of redundant subgroups in the result set. Several similarity measures have been proposed, based on the similarity of the support (using the Jaccard coefficients) or on their description [START_REF] Van Leeuwen | Non-redundant subgroup discovery in large and complex data[END_REF][START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF].

Contribution 1:

As a first contribution, we propose a new sampling exploration method based on Monte Carlo tree search (MCTS) [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF][START_REF] Browne | A survey of monte carlo tree search methods[END_REF]. It is an iterative method that employs random simulations to guide the exploration of the search space. This method exhibits several advantages w.r.t. existing heuristic approaches in SD/EMM. First, contrary to traditional pattern sampling methods, it does not require any probability distribution on the pattern space: The profile of the search space is learned incrementally. Second, it is based on the exploration / exploitation trade-off provided by the upper confidence bound [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]: This heuristic method aims at exploiting interesting solutions already found in the search space but also exploring few visited parts of the lattice. Besides, contrary to existing methods, we consider all the possible intervals for numerical attributes. Indeed, existing methods (exhaustive methods included) does not handle numerical descriptive attributes: They proceed to a discretization (either as a pre-processing step or on-the-fly during the enumeration on the lattice) on the domain of these attributes to make them ordinal. In our approach, we avoid such a greedy method to handle numerical attributes and enumerate all the possible intervals [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF] which is made possible with MCTS. Finally, this is an anytime pattern mining method that converges to the exhaustive search if given enough computational budget. Figure 6d illustrates the principle of using MCTS for SD/EMM: A search tree is incrementally built from the root of the lattice based on the trade-off between exploring rarely visited areas and exploiting interesting solutions. Given enough time, the result set will contain all the local optima.

Exceptional model mining in multi-label data

Exceptional model mining is the generalization of subgroup discovery that considers multi-label data [START_REF] Leman | Exceptional model mining[END_REF]. Indeed, SD has been defined when each of the objects is associated to one label, e.g., in the market basket data a consumer is either a man or a woman. However, the real world data are often multi-label, e.g., an image can be labeled with several keywords (mountain, sunset, lake, etc.) or in the olfactory data each chemical molecule is labeled with several odors (fruity, spicy, vanilin, etc.). In this case, SD can not be applied and the EMM framework is required. Given a set of objects S, EMM consists in building the model induced by S on the class labels. In the recent works, several model classes have been proposed to exhibit the relationships in the data [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF]. For example, let us consider the market basket data with two nominal target attributes given in Table 3: "Gender" which domain is tmale, f emaleu and "Age group" taking value in tr0, 29s, r30, 59s, r60, 99su. From this data, we used the contingency table between the two target attributes as a model (see Table 4 andTable 5). Then a quality measure is used to compare two contingency tables: The greater the quality measure, the more different the contingency tables. Thus, the goal of this EMM instance is to find out subgroups of customers whose contingency table is significantly different from the contingency table of all the customers in the data. In the olfactory data, we could have applied a model based on Bayesian networks on the odors [START_REF] Duivesteijn | Subgroup discovery meets bayesian networks -an exceptional model mining approach[END_REF]. Indeed, we compute the Bayesian network on the class labels (i.e., the odors) for a subset of molecules, and we use a quality measure to compare it with the Bayesian network on the odors for all the molecules in the data. Thus, a subgroup of molecules is said interesting if its Bayesian network is significantly different from those of the entire data. It means that in the subgroups the correlations between the labels are significantly different from the correlations between the labels in the entire data. Figure 3 illustrated the principle of an EMM instance: The model on the entire data is computed (red curve) and is compared to the model induced by a subset of objects (green curve) with a quality measure. The aim is to extract the set of the top-k subgroups w.r.t the quality measure that does not contain redundant subgroups.

However, for the SOR problem, the experts are not interested in model classes that are built on all the target labels. Indeed, finding a description about a subgroup of molecules that behaves differently from the entire data on all the odors is not actionable since each odor can have an impact. The neuroscientists and the chemists prefer to know that a subgroup of molecules whose model is different w.r.t. a (small) subset of odors. In this way, they can derive some knowledge about a specific subset of odors. This implies a substantial change in the definition of the EMM instance: A subgroup of objects no longer derives one model but several models, i.e., as many models as subsets of class labels. Figure 4 illustrates this change in the EMM setting. From a subset of objects, we can compute several models: One model for each subset of class labels. Thus, we compare each couple of models: For a given subset of class labels L, we compare the model built on L for the subgroup of objects and the model built on L for the entire data. The search space becomes even larger since we have to proceed to the Cartesian product between the 1 3 4 5 6 pattern search space and the power set of the class labels.

Besides, in the olfactory data, there is a high variance in the frequency of the class labels: Some odors such as fruity and floral are much more frequent than other odors such as musty and sandalwood. We say that a label is over-represented in the data if it is much more frequent than other labels. Moreover, the neuroscientists and the chemists require subgroups with as few errors as possible. It means that a subgroup is said interesting w.r.t. a subset of labels L if all the objects in the subgroup are labeled at least with L. In other words, the subgroup should not include objects that are not labeled with L in the data. This property is called the precision of the subgroup. In addition, the subgroup has to be as large as possible: It should contain lots of objects to be relevant. Indeed, it is easier to find small subgroups with a high precision than large subgroup with a good precision. This property is called the recall of the subgroup. Thus, the experts need to find subgroups for which the precision and the recall is high w.r.t. the subset of labels L. For example, in Figure 7, the red molecules (that smell strawberry) are over-represented in the dataset, but it is more interesting having the different subgroups (1), ( 2), ( 3) and ( 4) with high precision, rather than a single huge local subgroup (5) whose precision is much lower but with a good recall. Indeed, the experts of the domain suggest that a simple, universal and perfect rule does probably not exist, but instead, a combination of several sub-rules should be put forward to encompass the complexity of SOR. For molecules that are not over-represented, the extracted subgroups have to foster on both the precision and the recall: e.g., Subgroup ( 6) is interesting for the green molecules that smell herbaceous. Hence, we have to design a new model class that has to take into account: (i) The high variance in the frequency of the class labels, (ii) the precision and (iii) the recall of the subgroup w.r.t. the subset of class labels L.

Contribution 2:

As a second contribution, we propose a new EMM instance that deals with multi-label data. This EMM instance no longer derives one model by subgroups but several models: For each subgroup, as many models as subsets of labels are computed. Then the quality measure compare pairs of models that are built on the same subset of labels. Formally, if there are n different labels in the data, for each subgroup, we have to compute 2 n models, one for each subset of labels L.

Moreover, we propose a new model class called F β that is based on the F 1 score. This model evaluates the precision and the recall of the subgroups w.r.t. a given subset of L. Besides, F β includes a function βp.q that takes into account the frequency of the subset of labels L, i.e., if L is over-represented in the data or not. For that, F β fosters on the precision for over-represented labels and it converges to F 1 for other subsets of labels. In this way, we propose two quality measures that compare the model based on F β for the subgroups and those of the entire data. This contribution, combined with the MCTS-based enumeration, enables to address the SOR problem, namely to extract diverse rules on physico-chemical properties that can explain the presence of diverse subsets of odors.

Application in neuroscience about the Structure-Odor relationship

Eliciting supervised descriptive rules on the structure-odor relationship to derive knowledge is a challenging task in neuroscience. Indeed, a crowd-sourced challenge was recently proposed by IBM Research and Sage called DREAM Olfaction Prediction Challenge [START_REF]Dream olfaction prediction challenge[END_REF]. The challenge resulted in several non intelligible models that were able to predict especially pleasantness and intensity for 8 out of 19 olfactory qualities in their dataset ("garlic", "fish", "sweet", "fruit", "burnt", "spices", "flower" and "sour") with an average correlation of predictions across all models above 0.5 [START_REF] Keller | Predicting human olfactory perception from chemical features of odor molecules[END_REF]. However none descriptive rules have been proposed: The results only suggest that there exists links between some odors and the physico-chemical properties of the molecules. The current limited knowledge on SOR avoids the use of constraint-based pattern mining methods since setting a threshold remains hard. Indeed, the experts of the domain have difficulties to put words on their feelings. Thus, it is required to switch to other pattern mining methods that can handle the implicit expert's preferences. Interactive mining is a new trend of methods that includes the user in the exploration process [START_REF] Dzyuba | Interactive discovery of interesting subgroup sets[END_REF]. It uses the user's preferences as a feedback to guide the exploration of the search space. Interactive mining methods rely on instant mining algorithms, i.e., algorithms that give results anytime. Beam search and sampling methods are instant mining approaches and can be tuned to interactive algorithms.

Contribution 3:

As a third contribution, we implement an interactive online application that allows the user to guide the exploration of the search space based on her preferences. In this application there are some visualization tools to present the results of the method. Based on this interactive platform, the neuroscientists and the chemists are working on the understanding of descriptive rules on the structure-odor relationship. It leads to a deep analysis of the rules, to elicit new hypotheses on the impact of some physico-chemical properties. Moreover, they are trying to combine several rules to improve the cover of a single rule. The results suggest promising perspectives for the understanding of the olfactory percept process.

Structure of the thesis

The thesis is organized as follows. Chapter 2 provides the background about pattern mining and formally defines subgroup discovery and exceptional model mining. In addition, we point out the main issues we propose to tackle in this thesis. Chapter 3 introduces the paradigm of Monte Carlo tree search, the exploration method we employ in our first contribution. We define its principle and its main enhancements proposed in the state of the art. Chapter 4 concerns our first contribution, namely applying MCTS for pattern mining. We formalize the problem and we propose a lot of strategies to adapt the traditional process of MCTS to SD/EMM. We thoroughly 1.5. Structure of the thesis experiment with benchmark datasets to assess the validity of this new exploration method. This contribution has been published in the proceedings of the French conference Extraction et Gestion de Connaissances EGC'17 [START_REF] Bosc | Découverte de sous-groupes avec les arbres de recherche de monte carlo[END_REF] and an extended version is actually under major revision for the Data Mining and Knowledge Discovery journal [START_REF] Bosc | Any-time diverse subgroup discovery with monte carlo tree search[END_REF]. Chapter 5 details our second contribution about EMM with multi-label data. We explain a new EMM instance, that takes into account the high variance in the frequency of the class labels. Therefore, we define both a new model and a quality measure. We proceed to several batches of experiments to show the efficiency of this new EMM instance. This contribution has been published in the proceedings of the French conference Extraction et Gestion de Connaissances EGC'15 [START_REF] Bosc | Vers la découverte de modèles exceptionnels locaux : des règles descriptives liant les molécules à leurs odeurs[END_REF] and the international conference Discovery Science DS'16 [START_REF] Bosc | Local subgroup discovery for eliciting and understanding new structure-odor relationships[END_REF]. Chapter 6 presents the results we obtained combining our two contributions in a real world application, namely the study the structure-odor relationship. We explain the SOR problem and its issues. We detail the data. We propose a study of the different rules computed with our algorithm. We implemented a Web application that enables the user to interact with the algorithm to guide the exploration. This application has been published as a demo paper in the European conference on Machine Learning and Knowledge Discovery in Databases ECML/PKDD'16 [START_REF] Bosc | h(odor): Interactive discovery of hypotheses on the structure-odor relationship in neuroscience[END_REF]. Our collaborators are preparing a paper for the journal in neuroscience PLOS One -Computational Biology. Finally, Chapter 7 gives the conclusions and the perspectives of this thesis. Hermann-Editions, 2014 [START_REF] Bosc | Fouille de motifs séquentiels pour l'élicitation de stratégies à partir de traces d'interactions entre agents en compétition[END_REF].

List of publications

Note that there is one paper in major revision: Chapter 2

• G.

Pattern Mining

This chapter aims at introducing pattern mining and giving the main definitions we use in the rest of this document. First, we detail in Section 2.1 constraint-based pattern mining that has motivated a lot of works since the 90's. In Section 2.2, we define the problems of subgroup discovery (SD) and exceptional model mining (EMM), particular instances of pattern mining in which we are interested in this thesis. In Section 2.3, we discuss the different approaches proposed to solve them. Finally, we consider in Section 2.4 the several issues we finally address.

Constraint-based pattern mining

We formalize the constraint-based pattern mining framework and we introduce its most important research issues [START_REF] Boulicaut | Constraint-based data mining[END_REF][START_REF] Nijssen | Constraint-based pattern mining[END_REF]. Constraint-based pattern mining aims at proposing a generic framework to support the discovery of relevant patterns in data. The two main ideas are as follows. First, we must have the possibility to specify in a declarative way which are the patterns of interest in a given dataset: For that purpose, primitive constraints that are then combined thanks to boolean operators may be used to specify a so-called selection predicate that defines the patterns of interest among the collection of possible patterns, i.e., the sentences of a pattern language. Next, we must be able to compute the specified collection of patterns. This is where we have to discuss about algorithms and combinatorial complexity. This is where the possible enumeration strategies within the search space of the pattern language have to be considered seriously.

Basically, a pattern mining task or query 4 can be formalized as the theory of the data, following the terminology used in [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF]:

T hpD, L, Ωq " tp P L | Ωpp, Dq " trueu D denotes the data, i.e., a set of objects (or instances), L denotes the pattern language, and Ω defines the selection predicate. Typically, such a predicate Ω is a boolean function that returns true if a pattern has to be kept in the result set, i.e., if the specified constraint that is a boolean combination of primitive constraints holds for the pattern. A quite common setting concerns the use of simple primitive constraints that look whether or not a quality measure is above or below a given threshold. One of the most popular example of such a primitive constraint concerns the minimal frequency constraint where the quality measure ϕ of a pattern p P L denotes its number of occurrences in the data: To be frequent and thus to be considered interesting, a pattern frequency must be greater than the minimal frequency threshold. Indeed, such concepts have been studied for many types of data (transactions, sequences, collections of sequences, strings, trees, graphs, etc) and many types of pattern languages.

It is fairly easy to classify most of the existing works in the pattern mining area according to the simple concepts we have just introduced. Indeed, given a (type of) dataset D, many authors contribute to the design or definition of new pattern languages (e.g., itemsets [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], sequences [START_REF] Agrawal | Mining sequential patterns[END_REF] or graphs [START_REF] Cook | Mining graph data[END_REF]) associated to new primitive constraints that can eventually be based on new quality measures (see, e.g., [START_REF] Lavrac | Rule evaluation measures: A unifying view[END_REF]) to specify beforehand pattern relevancy. When the data, the pattern language and the primitive constraints are known, we can talk of a pattern domain.

Once we have a given pattern domain, the question of computing a collection of patterns that satisfy a given selection predicate can be extremely hard to solve. We have to enumerate the search space (sentences from L) to find the correct and complete set of patterns, generally associated to the values of some of their quality measures. For instance, we want to compute every frequent pattern and its frequency. While many exhaustive algorithms have been designed for different pattern domains the last two decades, more and more interesting pattern mining tasks cannot be solved thanks to complete strategies. When it remains feasible, we can achieve scalable complete evaluation by exploiting the properties of the primitive constraints (e.g., the popular anti-monotonicity and monotonicity of many useful primitive constraints) to efficiently prune the search space during classical enumeration strategies (see, e.g., [START_REF] Jeudy | Optimization of association rule mining queries[END_REF][START_REF] Besson | Constraint-based concept mining and its application to microarray data analysis[END_REF][START_REF] Cerf | Closed and noise-tolerant patterns in n-ary relations[END_REF] when considering only a few results from our group in Lyon).

Mining frequent itemsets

A well-studied instance of pattern mining concerns the extraction of frequent patterns in transaction data. Frequent pattern mining aims at extracting substructures that appear in the data with a frequency greater or equal to a specified threshold. The frequent patterns give an overview over the data and are used to highlight the relationships among the data, e.g., while generating association rules [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]. Initially, frequent pattern mining deals with itemsets that have been studied a lot. Let I be a set of items. A transaction is a subset of items t Ď I. The data D is a transaction database, that is a set of transactions D " tt 1 , ..., t n u. An itemset is an arbitrary subset of items p Ď I. The pattern language is the power-set of I, i.e., the set of all itemsets: L " 2 I . We define a k-itemset an itemset of size k, i.e., containing k items. Definition 1 (Extent and support of a pattern). The extent of a pattern p P L in a transaction database D is the set of transactions of D that support the pattern p. Formally, the extent of p is:

ext D ppq " tt P D | p Ď tu
Then, the support of p is the cardinality of its extent, that is the number of transactions that support p:

supp D ppq " |ext D ppq|
Note that, we omit the subscript mentioning the data in these definitions when there is no ambiguity about D.

In frequent pattern mining, the quality measure ϕppq of a pattern p P L is its support suppppq and the selection predicate Ω is true if the support of a pattern p is greater or equal to a minimum support threshold, denoted as minSupp, specified by the user. Formally the selection predicate is Ωpp, Dq " suppppq ě minSupp. A B C D

A 3 B 5 C 4 ∅ 6 D 4 AC 2 AD 3 BC 3 BD 3 AB 2 CD 2 ABD 2 ACD 2 BCD 1 ABC 1 ABCD 1
Figure 8: The lattice induced by the transaction database in Table 6. Each node is an itemset and the number is its support.

Problem 1 (Frequent itemset mining). Given a transaction database D, a set of items I (L " 2 I ) and a minimum support threshold minSupp P N, frequent itemset mining aims at performing the correct and complete extraction of all the frequent itemsets p P L such that suppppq ě minSupp. Note that, in general, it goes further, i.e., both the frequent itemsets and their frequencies have to be extracted. Computing frequent itemsets needs to explore the search space of itemsets. This search space is structured as a lattice p2 I , Ďq. For instance, the lattice of the data in Table 6 is given in Figure 8. Each node of the lattice is an itemset, and the number at the bottom of each node is the support of the itemset. Since there is an exponential number of itemsets w.r.t. the number of items (2 |I| itemsets in the lattice), several algorithms have been proposed to efficiently enumerate this search space 5 . Indeed, a naive exploration that enumerates each itemset is not scalable for large sets of items I. We present two of the main mining methodologies that have been used to enumerate the itemsets, namely (i) the apriori principle and (ii) the FP-Growth strategy.

Example 4. Let us consider the toy transaction database D given in

Apriori principle

The most famous property of the support is anti-monotonicity: If an itemset is frequent, then any of its sub-itemset is frequent [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF]. Conversely, if an itemset is infrequent, any of its super-itemset is infrequent. Formally, let p P L be an itemset and minSupp be the minimum support threshold, if:

• suppppq ě minSupp ñ @p 1 P L, p 1 Ď p, extpp 1 q Ě extppq and supppp 1 q ě minSupp • suppppq ď minSupp ñ @p 1 P L, p 1 Ě p, extpp 1 q Ď extppq and supppp 1 q ď minSupp From this property, the Apriori algorithm is proposed by Agrawal and Srikant to extract the frequent itemsets in a top down approach. Indeed, the first step consists in finding the frequent 1-itemsets (itemsets of size 1). Then, the frequent 1-itemsets are used to generate the candidates for frequent 2-itemsets and the transaction database is used to check which of these candidates are frequent. The frequent 2-itemsets are used to find the frequent 3-itemsets and so on, until there is no more frequent k-itemsets. In many cases, the Apriori algorithm significantly prunes the search space. However, it can suffer from two-nontrivial costs: (i) generating a huge number of candidate sets, and (ii) repeatedly scanning the database and checking the candidates by pattern matching. About a decade later, another kind of exploration method has been proposed, namely the FP-Growth algorithm.

Example 5. Let us consider the transaction database given in

FP-Growth

FP-growth is an efficient and scalable method to find frequent patterns [START_REF] Han | Mining frequent patterns without candidate generation[END_REF]. It allows to extract the frequent itemsets without candidate itemset generation (different from the Apriori algorithm). FP-growth employs a divide-and-conquer principle to extract the frequent patterns. Each recursion processes in two steps: (i) The construction of a data structure called the FP-Tree, and (ii) the extraction of frequent itemsets from the FP-Tree. The first scan of the transaction database derives the ordered list of the frequent 1-itemsets (decreasing order on the support of the frequent items). From this ordered list, the FP-Tree is built. Then, we mine the FP-tree by starting from each frequent 1-itemset, called the suffix, (from the less frequent to the most frequent), constructing its so-called conditional pattern database (CPD). From this conditional pattern base, we can derive its conditional FP-tree, and thus recursively mine this FP-Tree. We then concatenate the frequent patterns found in the FP-Tree with the suffix. 6 with minSupp " 3. Example 6. From the transaction database of Table 6, we compute the ordered list of the frequent 1-itemsets: Br5s; Cr4s; Dr4s; Ar3s. From that we can generate the FP-Tree (see Figure 9): For each transaction of the data, we ordered it w.r.t. the ordered list (e.g., t 1 is tB, D, Au, t 2 is tC, D, Au and so on) and we add the nodes and update the support count if a node already exists in the branch of the tree (e.g., for t 1 , we add the node pB, 1q as a child of the root node, then we add the node pD, 1q as a child of pB, 1q and finally the node pA, 1q becomes a child of node pD, 1q; for t 2 we add the node pC, 1q as child of the root node since the root node does not have the child C expanded yet, then we add pD, 1q to pC, 1q and pA, 1q to pD, 1q; and so on). Based on this FP-Tree, for each frequent 1-itemset, we compute its conditional pattern base, iterating in the reverse order of the list. The CPD of tAu is:

• Br1s; Dr1s • Br1s; Cr1s; Dr1s • Cr1s; Dr1s
Only tDu is frequent in the CPD of tAu: tA, Du is added to the result set. The CPD of tDu is:

• Br2s • Cr1s; Br1s • Cr1s
Only tBu is frequent in the CPD of tDu: tB, Du is added to the result set. The CPD of tCu is:

• Br3s
tBu is frequent in the CPD of tCu: tB, Cu is added to the result set. Finally the result set contains these frequent itemsets: tAu, tBu, tCu, tDu, tA, Du, tB, Cu and tB, Du.

Beyond frequent itemset mining

Although frequent itemset mining enables to derive some knowledge from the data this pattern language lacks of expressiveness. Indeed, nowadays we are facing numerical health data that are collected from smart watches, social networks that are structured as graphs, or even sequences of images that highlight the movement of the celestial bodies in the universe. These data can not be handled with itemsets: They require a more expressive pattern language. In addition, the pattern explosion is a well known property of frequent pattern mining approaches [START_REF] Calders | A survey on condensed representations for frequent sets[END_REF]. Depending on the minimum support threshold, there could be a huge amount of frequent patterns. This makes the interpretation of the results unfeasible. Moreover, the minimal frequency constraint is far from enough to specify interestingness and relevancy: Generally, the frequent patterns are not informative. To answer these different issues, several improvements of frequent itemset pattern mining are proposed in the state of the art, e.g., pattern compression with closed and maximal patterns to reduce the number of extracted patterns, pattern languages with a better expressiveness, or even novel quality measures to evaluate the interestingness of patterns.

Pattern compression

Usually, mining frequent itemsets in a transaction database leads to a huge number of frequent patterns [START_REF] Calders | A survey on condensed representations for frequent sets[END_REF]. This is particularly true when the minimum support threshold minSupp has to be low to avoid the extraction of trivial patterns. Due to the anti-monotonic property of the support, a large frequent pattern has an exponential number of frequent sub-patterns. To tackle this so-called pattern explosion, pattern compression allows to reduce the number of extracted patterns with or without a loss of information. For that, we define the equivalence class of a pattern p P L [121]: Definition 2 (Equivalence class). Given a transaction data D, the equivalence class of an arbitrary itemset p is given by rps " tp 1 P L|extppq " extpp 1 qu. In other words, the equivalence class of a pattern p is the set of patterns for which the extent is exactly the same.

Example 7. The equivalence class of the pattern p 1 " tA, Cu in the transaction database in Table 6 is rp 1 s " ttA, Cu, tA, Du, tA, C, Duu since the extent of all of these itemsets is composed of t 2 and t 6 .

From the definition of the equivalence classes, closed patterns based enumeration has been proposed and has attracted a lot of works especially in the formal concept analysis (FCA) community [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]. Indeed, the closure operator enables to derive only one pattern from the equivalence class.

Definition 3 (Closed pattern).

Each equivalence class has a unique largest element w.r.t. Ď that is called the closed pattern (the most specific pattern). In other terms, p is said to be closed iff Ep 1 such that p Ď p 1 and extppq " extpp 1 q. The non-closed patterns are called generators, and the smallest generators w.r.t. the Ď operator are called the minimal generators.

The set of closed frequent patterns is a compression that does not lose any information about the corresponding frequent patterns. The main algorithms that aim at extracting frequent closed itemsets are CHARM [START_REF] Zaki | CHARM: an efficient algorithm for closed itemset mining[END_REF], Close by One (CbO) [START_REF] Kuznetsov | A fast algorithm for computing all intersections of objects from an arbitrary semilattice. Nauchno-Tekhnicheskaya Informatsiya Seriya 2 -Informatsionnye protsessy i sistemy[END_REF] and its extensions Fast Close by One (FCbO) [START_REF] Krajca | Advances in algorithms based on CbO[END_REF], AddIntent [START_REF] Van Der Merwe | Addintent: A new incremental algorithm for constructing concept lattices[END_REF], and more recently the In-Close approach that is another variant of CbO [START_REF] Andrews | A partial-closure canonicity test to increase the efficiency of cbo-type algorithms[END_REF][START_REF] Andrews | A 'best-of-breed' approach for designing a fast algorithm for computing fixpoints of galois connections[END_REF]. Most of them employ the closure operator with a lexicographical order on the items to ensure a canonical generation of the patterns.

Example 8. In Table 6, let us consider the pattern p 1 " tA, Cu and its equivalence class rp 1 s " ttA, Cu, tA, Du, tA, C, Duu. The closed pattern is the largest itemsets w.r.t. Ď, i.e., tA, C, Du. Given the minimum support threshold minSupp " 3, the set of frequent closed patterns is composed of 6 itemsets: tBu, tCu, tDu, tA, Du, tB, Cu, tB, Du. In this example, using frequent closed patterns enables to remove one pattern from the frequent pattern set, namely a compression of 14%.

The other possibility to compress the frequent pattern set is to use the maximal frequent patterns [START_REF] Burdick | MAFIA: A maximal frequent itemset algorithm for transactional databases[END_REF][START_REF] Gouda | Efficiently mining maximal frequent itemsets[END_REF]. This solution enables to improve the compression rate but it leads to a loss of information: Indeed, it becomes impossible to recover the entire set of frequent patterns from the maximal frequent patterns. The algorithms that aim at extraction maximal frequent patterns are less numerous than for frequent closed patterns: The algorithms MAFIA [START_REF] Burdick | MAFIA: A maximal frequent itemset algorithm for transactional databases[END_REF] and GenMax [START_REF] Gouda | Efficiently mining maximal frequent itemsets[END_REF] are two of the main ones. Definition 4 (Maximal frequent pattern). Given a minimum support threshold minSupp, a pattern p is a frequent maximal pattern in a transaction database D if p is frequent and there is no super-patterns p 1 of p that is frequent. Formally, p is a frequent maximal pattern iff Ep 1 P L such that p Ď p 1 and supppp 1 q ě minSupp.

Example 9. In the same settings than the previous example, the set of maximal frequent patterns contains only 3 itemsets, namely tA, Du, tB, Cu, tB, Du. Indeed, the frequent 1-itemsets tAu, tBu, tCu and tDu are not maximal since there exists super-patterns that are frequent. Thus, the compression rate is 57%, four times better than those of the frequent closed patterns. However, once again, the maximal frequent pattern set does not enable to recover directly the entire set of frequent patterns with their frequencies, whereas the frequent closed pattern set does.

Pattern language

Other improvements concern a growing expressiveness of the pattern language L. Indeed, itemsets mining lacks of expressiveness in most of the real data. Nowadays, the collected data is not only binary. For example, the public opinion polls gather nominal (or categorical) value, the different sensors that are deployed all over the world return numerical values, the data collected in the supermarkets are made of sequences of itemsets, or the interactions in the social networks are represented with graphs. For that, in the previous decades there has been a lot of works that take into account this need for a growing expressiveness of the pattern language. In the following, we briefly present a pattern language for the nominal and numerical attributes. Note that sequential pattern mining has been introduced by Agrawal and Srikant [START_REF] Agrawal | Mining sequential patterns[END_REF] 6 . Besides, graph mining has become an extremely active research domain that has steadily increased for a decade [START_REF] Cook | Mining graph data[END_REF]. Enhancements of graph mining with attributed graphs [START_REF] Moser | Mining cohesive patterns from graphs with feature vectors[END_REF] or dynamic graph [START_REF] Berlingerio | Mining graph evolution rules[END_REF][START_REF] Robardet | Constraint-based pattern mining in dynamic graphs[END_REF] have been studied. Recently, a work has proposed to mine convex polygons with formal concept analysis opening the road to geometrical shapes [START_REF] Belfodil | Mining convex polygon patterns with formal concept analysis[END_REF].

Nominal attributes are the generalization of itemsets where the domain of a nominal attribute is composed of several incomparable values. In the case of itemsets, the nominal attributes are the items, and each item can take the value true (present) or false (missing). Let A " tA 1 , A 2 , . . . u be the set of nominal attributes, the pattern language is the Cartesian product between the domain value DompA i q of each nominal attribute

A i P A: L " Ś A i PA DompA i q.
Handling numerical attributes has motivated several works, in particular in FCA. A numerical pattern is the restriction on the numerical attributes using intervals. Thus let A " tA 1 , A 2 , . . . u be a set of numerical attributes, the pattern language is the set containing the Cartesian product of all the possible intervals for each numerical attributes: L " Ś A i PA rα i , β i s where α i , β i P DompA i q and DompA i q is the domain value of the attribute A i . The numerical patterns are also structured as a lattice [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF][START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF]. Figure 10 illustrates the upper part of the lattice on the numerical attributes of Table 7. Each child of a node consists in restricting the interval of an attribute either by a minimal left change, i.e., the lower bound is set to the next value (in ascending order) taken by this attribute in the data, or by a minimal right change, i.e., the upper bound of the interval is set to the previous value (in ascending order) taken by this attribute in the data. Still, the lattice is much larger than for itemsets, thus many works proceed to a discretization of the numerical attributes, either as a pre-processing task or an on-the-fly during the enumeration, to be equivalent to nominal attributes. However, even if the runtimes are faster, this naive strategy remains greedy and leads to sub-optimal results. In this thesis, we are interested in handling numerical data based on the minimal changes, to ensure the enumeration of all the possible intervals for each numerical attribute.

Quality measure

In addition to the pattern language, one major direction of research concerns the definition of new quality measures. Up to now, we simply present the support measure that is the initial quality measure that has been used in pattern mining. However, the support remains weak to evaluate the interestingness of a pattern. Indeed, the most frequent patterns are not necessary the more interesting because they can be trivial. That is why, scientists have worked and are still working about the definition of new quality measures to capture informative knowledge [START_REF] Lavrac | Rule evaluation measures: A unifying view[END_REF][START_REF] Abudawood | Evaluation measures for multi-class subgroup discovery[END_REF][START_REF] Konijn | Cost-based quality measures in subgroup discovery[END_REF].

Mining frequent itemsets is used to discover association rules in a transaction database. Association rule mining was initially introduced by Agrawal et al. [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]. The aim is to find rules of the form X Ñ Y where X and Y are disjoint itemsets. To evaluate an association rule, two measures are often used, namely the support and the confidence of the rule. An association rule is said interesting if its support is greater or equal to a given minimum support threshold minSupp and its confidence is greater or equal to a given minimum confidence threshold minConf . The confidence of the rule X Ñ Y measures the precision of the rule, i.e. the number of transactions containing X that also contains Y . It is defined as follows:

conf pX Ñ Y q " supppX X Y q supppXq
In addition to the confidence, there are tens of measures that have been already defined to evaluate association rules. For instance, the lift measure of the rule X Ñ Y quantifies the correlation between X and Y and is defined by: liftpX Ñ Y q " supppX X Y q supppXq ˆsupppY q

Constraint

In frequent itemset mining, the constraint consists in setting a minimum support threshold. Thus, a pattern is extracted if its support is greater than this threshold. This an anti-monotonic constraint. In the state of the art of constraint-based pattern mining, there was a trend to exhibit new properties of constraints and how to benefit from them: The relationship of constraint properties and enumeration principles is a fundamental issue. Anti-monotonicity is the first one that was studied with frequent pattern mining. However, there exists several other anti-monotonic constraints: The maximum length of a pattern constraint, the maximum sum of cost constraint, and also the conjunction and the disjunction of anti-monotonic constraints. This property on constraints is not only available for itemsets, but also for other pattern languages, such as sequences or graphs. Anti-monotonic constraints enable to prune efficiently the search space when proceeding to a top-down enumeration: Indeed, if the constraint does not hold for a node, it does not hold for any of its children (a child is a specialization of its parent). Formally for a pattern language L with a partial order ĺ (e.g., for itemsets ĺ is Ě), @p, p 1 P L, p 1 ĺ p, Ωpp, Dq " false ñ Ωpp 1 , Dq " false. This is the principle of the Apriori algorithm [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF][START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF] Close to anti-monotonic constraints, monotonic constraints have been defined. This property can be seen as the negation of anti-monotonicity. If the monotonic constraint holds for a node in the lattice, it holds for all of its specialized patterns, i.e., its children. Formally, for a pattern language L with a partial order ĺ, @p, p 1 P L, p 1 ĺ p, Ωpp, Dq " true ñ Ωpp 1 , Dq " true. The maximum support constraint is monotonic, as well as the minimum size constraint. Similarly to anti-monotonic constraints, with monotonic constraint, an efficient enumeration consists in exploring in a bottom-up approach, i.e., from the more specialized patterns to the more general ones, to efficiently prune the search space [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF][START_REF] De Raedt | A theory of inductive query answering[END_REF].

Several properties have been identified to efficiently handle them during the enumeration by pruning the search space or computing upper bounds [START_REF] Morishita | Traversing itemset lattice with statistical metric pruning[END_REF]. For example, convertible (anti-) monotonic constraints can be considered as (anti-) monotonic by using a specific enumeration: Thus, the previous pruning techniques can be applied. The aim of constraint-based mining is to design generic algorithms that exploit the different properties of the constraints and the pattern language [START_REF] Jeudy | Optimization of association rule mining queries[END_REF][START_REF] Besson | Constraint-based concept mining and its application to microarray data analysis[END_REF][START_REF] Cerf | Closed and noise-tolerant patterns in n-ary relations[END_REF]. However, sometimes it is difficult to state explicitly a constraint. In addition, setting a threshold is known to be hard because it would lead to a pattern explosion if the associated constraint becomes too loose or to the empty set of results if it turns to be too strong. For that, sky-patterns have been proposed: It aims at extracting the best patterns w.r.t. several quality measures by considering the Pareto frontier [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]. This enables to get rid of thresholds.

In summary, the trend in pattern mining is to efficiently extract patterns based on a given pattern language that is interesting w.r.t. quality measures. Association rules are the first attempt to exhibit some correlation in the data. However, recently, more and more datasets are about labeled data, i.e., transactions that are associated to a label. The supervised discovery of patterns that strongly distinguish one class label from another is still a challenging pattern mining task. Finally, pattern mining has become more and more able to extract interesting patterns leading to new knowledge. The model used to represent the data and the exploration methods are much more efficient to handle the existing relationships in the data. In this work, we are interested in the SD/EMM frameworks that enable to find exceptional behaviors within a labeled data.

Mining supervised descriptive rules

The discovery of patterns, or descriptions, which distinguish a group of objects given a target (class label) has been widely studied in data mining and machine learning [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF]. Such descriptive rules can be formalized, among many other choices in AI, in subgroup discovery (SD, [START_REF] Klösgen | Explora: A multipattern and multistrategy discovery assistant[END_REF][START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF]) or exceptional model mining (EMM, [START_REF] Leman | Exceptional model mining[END_REF]). Two similar notions have been formalized independently and then unified by Novak et al. [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF]: Contrast Set mining [START_REF] Bay | Detecting group differences: Mining contrast sets[END_REF] and emerging patterns [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF]. The first one aims to obtain high differences of support between the values of the target variable. The latter extracts patterns with different frequencies in two classes (e.g., the positive and the negative classes) of the target variable. However, both methods and SD are similar and differ partially from the quality measure they use [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF]. Close to SD, Redescription Mining aims to discover redescriptions of the same groups of objects according to different views [START_REF] Ramakrishnan | Turning cartwheels: an alternating algorithm for mining redescriptions[END_REF][START_REF] Van Leeuwen | Association discovery in two-view data[END_REF]. In this work we are interested in the SD/EMM frameworks. The input data is a population of individuals (objects, customers, transactions, . . . ) that embeds a set of descriptors and a set of class (or target) labels (some existing works deal also with numerical target attributes). We now detail both subgroup discovery (SD) and its generalization, the exceptional model mining framework (EMM).

Subgroup discovery

Subgroup discovery (SD) was first introduced in the middle of the 90's [START_REF] Klösgen | Explora: A multipattern and multistrategy discovery assistant[END_REF][START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF]. The aim of SD is to extract subgroups of objects (described by a rule involving descriptors) for which the distribution on the target variable is statistically different from the whole (or, for some authors, the rest of the) population. Although these settings are related to those of a supervised learning task, SD is a descriptive task. A subgroup is a description generalization whose discriminating ability is assessed by a quality measure. Several measures have been proposed to evaluate a pattern w.r.t. a class label: The Weighted Relative Accuracy (WRAcc) [START_REF] Lavrac | Rule evaluation measures: A unifying view[END_REF], the F-Score, the Jaccard coefficients, or the weighted Kullback Leibler divergence (WKL). In the last two decades, different aspects of SD have been widely studied: The pattern language (quantitative, qualitative, etc.), the algorithms that enable the discovery of the best subgroups, and the definition of measures that express the interestingness or relevancy of a pattern. These three points are closely related, and many of the first approaches were ad hoc solutions lacking from easy implementable generalizations (see [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF] for a survey).

Definition 5 (Label dataset). Let O, A and C be respectively a set of objects, a set of attributes, and a set of class labels. The domain of an attribute a P A is Dompaq where a is either nominal or numerical. Each object is associated to a class label from C through class

: O Þ Ñ C. DpO, A, C, classq is a label dataset.
Definition 6 (Subgroup). The description of a subgroup is given by d " xf 1 , . . . , f |A| y where each f i is a restriction on the value domain of the attribute a i P A. The description of a subgroup corresponds to the pattern in the pattern mining setting. A restriction is either a subset of a nominal attribute domain, or an interval contained in the domain of a numerical attribute. The description d covers a set of objects called the extent of the subgroup, denoted extpdq Ď O, and its support is the number of objects in its extent and is defined by supppdq " |extpdq|. Note that, in this thesis, we denote |S| the cardinality of the set S. For simplicity, a subgroup is either given by its intent, i.e., its description d, or by its extent extpdq.

The ability of a subgroup to discriminate a class label is evaluated by means of a quality measure. The latter reflects the difference between the model induced by the subgroup on the target attribute and the model induced by the entire dataset. Basically, the model induced by a set of objects S is the proportion of objects of S associated to one class label l P C. The choice of the measure depends on the application [START_REF] Fürnkranz | Foundations of Rule Learning[END_REF]. There exists several quality measures that are used in SD, e.g., the WRAcc [START_REF] Lavrac | Rule evaluation measures: A unifying view[END_REF], Gini index, entropy or the Weighted Kullback-Leibler divergence (WKL) [START_REF] Abudawood | Evaluation measures for multi-class subgroup discovery[END_REF].

Problem 2 (The SD problem). Given a label dataset DpO, A, C, classq, a quality measure ϕ, a minimum support threshold minSupp and an integer k, SD aims at extracting the top-k best

128 ≤ a ≤ 152 21 ≤ b ≤ 29 9 ≤ c ≤ 12 136 ≤ a ≤ 152 21 ≤ b ≤ 29 9 ≤ c ≤ 12 128 ≤ a ≤ 151 21 ≤ b ≤ 29 9 ≤ c ≤ 12 128 ≤ a ≤ 152 23 ≤ b ≤ 29 9 ≤ c ≤ 12 128 ≤ a ≤ 152 21 ≤ b ≤ 27 9 ≤ c ≤ 12 128 ≤ a ≤ 152 21 ≤ b ≤ 29 10 ≤ c ≤ 12 128 ≤ a ≤ 152 21 ≤ b ≤ 29 9 ≤ c ≤ 11 136 ≤ a ≤ 152 23 ≤ b ≤ 29 9 ≤ c ≤ 12 128 ≤ a ≤ 151 23 ≤ b ≤ 29 9 ≤ c ≤ 12 128 ≤ a ≤ 152 24 ≤ b ≤ 29 9 ≤ c ≤ 12 128 ≤ a ≤ 152 23 ≤ b ≤ 27 9 ≤ c ≤ 12 128 ≤ a ≤ 152 23 ≤ b ≤ 29 10 ≤ c ≤ 12 128 ≤ a ≤ 152 23 ≤ b ≤ 29 9 ≤ c ≤ 11
Figure 10: The upper part of the search space for the data of Table 7.

frequent subgroups w.r.t. ϕ. The quality measure ϕ quantifies a deviation between the model induced by extpdq and O, respectively.

Note that, in the literature, the problem definition of SD can be slightly different from those we use in this thesis. Our definition is equivalent to those given in [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF] in which we include a minimum support constraint in the set of constraints. 7 with objects O " t1, ..., 6u and attributes A " ta, b, cu. Each object is labeled with a class label from C. Considering the proportion class model, the proportion of the target label l 2 within the entire dataset is p l 2 0 " |toPO|classpoq"l 2 u| |O| " 1 2 . Consider the subgroup with description d " xr128 ď a ď 151s, r23 ď b ď 29sy. Note that for readability, we omit restrictions satisfied by all objects, e.g. r9 ď c ď 12s, and thus we denote that extpxyq " O. The extent of d is composed of the objects extpdq " t2, 3, 5, 6u. The distribution model for the target label

Example 10. Consider the label dataset in Table

l 2 in d is p l 2 d " |toPextpdq|classpoq"l 2 u| supppdq " 3
4 . Then we compute if these distribution models are significantly different using the WRAcc measure for the label l 2 : W RAccpd, l 2 q " supppdq |O| ˆpp l 2 d ´pl 2 0 q " 1 6 . The search space of the label dataset given in Table 7 is a lattice whose the top part is presented in Figure 10. We can notice the principle of minimal left and right changes to enumerate all the possible intervals.

The SD problem has been extended in various ways, e.g., according to the pattern language, the algorithmic method to enumerate the search space, or more generally, the quality measure or exceptionality of a model induced by the subgroups. All these improvements can be discussed within the exceptional model mining framework (EMM [START_REF] Leman | Exceptional model mining[END_REF]) that does not consider only one class label per object but several.

Exceptional model mining

Exceptional model mining (EMM) was introduced by Leman et al. [START_REF] Leman | Exceptional model mining[END_REF]. Recently, Duivesteijn et al. have proposed an interesting and complete survey on EMM [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF]. It can be seen as a generalization of SD as it enables one to deal with more complex target concepts. Initially, SD aims at finding subgroups of objects for which the distribution over one value of the target variable deviates substantially from the distribution of the entire population of objects. In EMM, there is no longer one target variable but several ones: The descriptors are split into two sets, the descriptive variables and the target variables. The goal of EMM is to extract subgroups of objects for which the model induced over all the target variables substantially deviates from the model induced by the whole population of objects. Note that, in some works, the model induced by the subgroup has to deviate from the model of the complement set of objects and not the whole population. An illustration of this framework is given in Figure 3.

In this context, we have to override the definition of the label dataset given in Definition 5 as follows:

Definition 7 (Multi-label dataset). Let O, A and C be respectively a set of objects, a set of attributes (either nominal or numerical), and a set of class labels. Each object is associated to a subset of class labels among C by the function class

: O Þ Ñ 2 C that
maps the target labels to each object. We denote a multi-label dataset as DpO, A, C, classq.

In the EMM framework, given a multi-label dataset, the definition of a subgroup remains unchanged: Definition 6 is used. EMM relies on the model induced by a set of objects over the class labels. Many models have been proposed in the literature [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF]: For instance, the probability distribution, a Bayesian Network, a clustering or a classification model over the class labels. Quality measure have been introduced to compare the similarity between the two models (i.e., those of the subgroup and those of the entire dataset), the better the quality measure, the less the similarity, the more interesting the subgroup. Figure 3 illustrates the process of EMM. On the left, the red circles are the objects of the dataset. The green area is the support of a subgroup. The red curve on the middle is the model induced by the entire dataset. The green curve is the model induced by the subgroup. These two models are compared by means of a quality measure. From that we can define the traditional EMM problem: 8 with objects O " t1, 2, 3, 4, 5, 6u, attributes A " ta, b, cu and class labels C " tl 1 , l 2 , l 3 u. Each object is labeled with a subset of class labels from C. Considering the probability distribution model class over the class labels, the aim is thus to find subgroups whose distribution over all the class labels is significantly different from those of the entire set of objects. The distribution of the entire dataset for each class label l 1 , l 2 and l 3 is respectively p l 1 0 " |toPO|l 1 Pclasspoqu| |O| " 3 6 " 0.5, p l 2 0 " 0.67 and p l 3 0 " 0.5. Let us consider the subgroup s with description d " xr128 ď a ď 151s, r23 ď b ď 29sy. The extent of d is extpdq " t2, 3, 5, 6u. The model induced by this subgroup for each class label is

p l 1 d " |toPsupppdq|l 1 Pclasspoqu| supppdq " 2 4 " 0.5, p l 2 d " 1 and p l 3 d " 0.25.
To compare these two models, we choose to use the mean of the WRAcc measures for each label:

ϕpsq " 4 6 ˆ˜pp l 1 d ´pl 1 0 q `pp l 2 d ´pl 2 0 q `pp l 3 d ´pl 3 0 q 3 ¸" 0.03

Algorithms for SD and EMM

SD and its generalization EMM have attracted a lot of works for more than two decades. Both exhaustive and heuristic methods have been used to explore the search space of subgroups.

Exhaustive exploration

The first exploration methods that have been proposed for SD implemented an exhaustive search, i.e., the search space is completely explored ensuring that the best subgroups are found [START_REF] Kavsek | APRIORI-SD: adapting association rule learning to subgroup discovery[END_REF][START_REF] Atzmüller | SD-map -A fast algorithm for exhaustive subgroup discovery[END_REF][START_REF] Atzmüller | Fast subgroup discovery for continuous target concepts[END_REF]. Several pruning strategies are used to avoid the exploration of uninteresting parts of the search space. These pruning strategies are usually based on the monotonic (or anti-monotonic) property of the support or the quality measures.

The first algorithm EXPLORA [START_REF] Klösgen | Explora: A multipattern and multistrategy discovery assistant[END_REF] is an exhaustive approach that employs decision trees. The MIDOS algorithm [START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF] is also based on decision trees with minimum support pruning. These methods are extensions of classification algorithms. The pattern language used to generate the rules is made of conjunctions of pair attribute-value. The target variable is either nominal or binary. Another kind of algorithms extends association rule learner algorithms such as the APRIORI-SD algorithm [START_REF] Kavsek | APRIORI-SD: adapting association rule learning to subgroup discovery[END_REF]. It also employs conjunctions of pairs attribute-value with a nominal target variable. Some exhaustive approaches employ efficient pruning methods to explore the search space. Merge-SD performs large pruning of the search based on bounds [START_REF] Grosskreutz | On subgroup discovery in numerical domains[END_REF]. This algorithm is able to deal with numerical attributes. The BSD algorithm uses a bitset (bitvector) based data structure with a depth-first-search approach [START_REF] Lemmerich | Fast discovery of relevant subgroup patterns[END_REF]. Recently, another approach has been proposed to efficiently perform an exhaustive exploration with a numerical target variable with optimistic estimates on different quality measures [START_REF] Lemmerich | Fast exhaustive subgroup discovery with numerical target concepts[END_REF]. The authors also compared different data structures, e.g., FP-trees or bitset.

Efficient methods for SD deal with the use of efficient data structures, often the well-known FP-growth method [START_REF] Han | Mining frequent patterns without candidate generation[END_REF] and a bitset structure. SD-MAP [START_REF] Atzmüller | SD-map -A fast algorithm for exhaustive subgroup discovery[END_REF] and DpSubgroup are based on FPtrees with a binary and nominal target variable. SD-MAP exploits a minimum support threshold whereas DpSubgroup [START_REF] Grosskreutz | Tight optimistic estimates for fast subgroup discovery[END_REF] employs tight optimistic estimates. SD-MAP* [START_REF] Atzmüller | Fast subgroup discovery for continuous target concepts[END_REF] extends the SD-MAP algorithm to numerical target variables.

To the best of our knowledge, there is only one exhaustive algorithm, namely GP-Growth, that addresses explicitly EMM [START_REF] Lemmerich | Generic pattern trees for exhaustive exceptional model mining[END_REF]. It extends the previous works done with SD-MAP and SD-MAP* for traditional SD. GP-Growth is based on the FP-Growth algorithm that uses the efficiency of the FP-Tree structure. GP-Growth employs a valuation basis that enables to get rid of the previous structure in which the frequency is included in each node in the tree. Thus, the kind of information stored in the valuation basis depends on the model class. Finally, the authors adapted the FP-Growth algorithm where the tree structure called the GP-Tree no longer stores frequencies but valuation bases. So, the algorithm GP-Growth proceeds to the aggregation of valuation bases for each pattern. Note that, this algorithm, as well as SD-MAP and SD-MAP*, uses an equal width discretization to handle numerical attributes. This pre-processing task avoid the exploration of the whole dataset by turning numerical attributes to nominal attributes, and it leads to an non-optimal result set.

Heuristic search

Exhaustive search ensures to extract the best subgroups, however its main drawback is that it is not scalable when the data becomes large. Such data leads to enormous search space making exhaustive search infeasible. Indeed, the more the descriptors, the longer the runtime. Similarly, the more the individuals, the longer the runtime (excepted for FP-growth methods that do not enumerate the individuals). To tackle the runtime issue, heuristic approaches have been used, ensuring a shorter exploration, but there is no guaranties to extract the best subgroups. For that, several heuristics have been used.

Beam search strategy

First, the commonly used search strategy is based on the beam search [START_REF] Lowerre | The HARPY speech recognition system[END_REF]. This heuristic enables to perform a level wise exploration of the search space, avoiding the so-called uninteresting parts, with several hill climbings run in parallel. A beam of a given size (or dynamic size for recent works) is built from the root of the search space. This beam only keeps the best promising subgroups to extend w.r.t. the quality measure ϕ. The first algorithms for SD designed with a beam search strategies are SubgroupMiner [START_REF] Klösgen | Census data mining, an application[END_REF], SD [START_REF] Gamberger | Expert-guided subgroup discovery: Methodology and application[END_REF] and CN2-SD [START_REF] Lavrac | Decision support through subgroup discovery: Three case studies and the lessons learned[END_REF]. Then, the algorithm SD4TS is developed [START_REF] Mueller | Subgroup discovery for test selection: A novel approach and its application to breast cancer diagnosis[END_REF], based on APRIORI-SD. It uses the quality measure of the subgroups to prune the search space.

More recently, several works have been done about beam search for EMM. One of the first heuristic algorithms is developed by van Leeuwen et al. in [START_REF] Van Leeuwen | Non-redundant subgroup discovery in large and complex data[END_REF]. The main point of this work is about redundancy in "Generalized Subgroup Discovery" (see the following Subsection 2.4 for more information about subgroup set discovery). Moreover, the authors present several beam strategies and compare them experimentally. Then, they extended this work [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF]. In this paper, the heuristic algorithm DSSD, Diverse Subgroup Set Discovery, is presented. This algorithm employs a beam search depending on several beam strategies. The experimental study includes a much wider range of datasets with deep comparisons. DSSD acts as a baseline algorithm for both SD and EMM. The following year, the algorithm DSSD is extended with a skyline approach that deals with the issue of redundancy in the top-k approaches [START_REF] Van Leeuwen | Discovering skylines of subgroup sets[END_REF]. We will discuss this redundancy issue in Subsection 2.4 as well.

ROCsearch is a new ROC-based beam search variant for EMM [START_REF] Meeng | Rocsearch -an roc-guided search strategy for subgroup discovery[END_REF]. Following the trend inspired by van Leeuwen et al., the authors have implemented a new selection method for beam search strategies. Indeed, commonly used beam search employs selection strategies that are only based on the quality measure. Some, as in the work of van Leeuwen et al. [START_REF] Van Leeuwen | Non-redundant subgroup discovery in large and complex data[END_REF], try to include others parameters that are able to avoid redundancy. However, these parameters often require thresholds that have to be fixed by the user. Fixing a parameter is well-known to be hard. ROCsearch proposes a new beam search strategy that enables to avoid fixing parameters. The width of the beam is dynamically set, depending on the current state of the previous beam. The selection strategy is based on the ROC space of the subgroups. The authors claim that the diversity of the result set is improved and the redundancy is decreased.

Evolutionary algorithms

The second mainstream of heuristic approaches for SD is about evolutionary algorithms [START_REF] Bäck | Handbook of evolutionary computation[END_REF]. These approaches aim at solving problems imitating the process of natural evolution. Genetic algorithms are a branch of the evolutionary approaches that use a fitness function to select which individuals to keep at the next generated population [START_REF] Holland | Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[END_REF]. SDIGA [START_REF] Del Jesús | Evolutionary fuzzy rule induction process for subgroup discovery: A case study in marketing[END_REF] is one of the first evolutionary algorithms designed for Subgroup Discovery. It is based on a fuzzy rule induction system. A fuzzy rule corresponds to the description of a subgroup, and is written in disjunctive normal form (DNF). Several quality measures are embedded in SDIGA such as support, confidence or sensibility. The objective function is an aggregating function based on several quality measures such as the coverage, the significance, the support or the confidence. EDER-SD [START_REF] Rodríguez | Searching for rules to detect defective modules: A subgroup discovery approach[END_REF] is a sequential covering evolutionary algorithm that produces a hierarchical set of rules. This algorithm extracts subgroups on imbalanced data, and especially the subgroups which target variable is the minority class of the dataset. Similarly to CN2-SD, EDER-SD penalizes the objects that are already covered by other rules (or subgroups). It can be used for numerical target variables. The objective function is based on different quality measures usually used in SD: accuracy, F-Score, sensitivity, . . . GAR-SD [START_REF] Pachón | Multi-objective evolutionary approach for subgroup discovery[END_REF] is an evolutionary multi-objective algorithm. It can work with both discrete and continuous attributes without previous discretization. It is based on the Iterative Rule-Learning approach. The objective function used in GAR-SD uses three different quality measures derived from SD (support, confidence and significance) and three other measures based on the characteristics of the rule. GP3-SD [START_REF] Luna | Discovering subgroups by means of genetic programming[END_REF] is based on a genetic programming algorithm for mining association rules for each value of the target variable. The descriptions of the subgroups are represented thanks to tree structures. Contrary to the previous algorithms, GP3-SD does not employ an Iterative Rule-Learning approach but the elitism for the selection procedure. The objective function is based on the support and the confidence of the rules. MESDIF [START_REF] Berlanga | Multiobjective evolutionary induction of subgroup discovery fuzzy rules: A case study in marketing[END_REF] is a multi-objective genetic algorithm that extracts rules describing subgroups. This algorithm can generate fuzzy and/or crisp DNF rules, for problems with continuous and/or nominal variables. It searches for optimal solution in the Pareto front based on the SPEA2 approach [START_REF] Zitzler | Spea2: Improving the strength pareto evolutionary algorithm[END_REF]. NMEEF-SD [START_REF] Carmona | NMEEF-SD: non-dominated multiobjective evolutionary algorithm for extracting fuzzy rules in subgroup discovery[END_REF] is a multi-objective evolutionary fuzzy algorithm. It is based on NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF], an efficient multi-objective evolutionary algorithm, and on the use of elitism. It allows the user to choose several quality measures as objective functions such as the support, the confidence or even the accuracy.

Sampling methods

Another trend of heuristic search for EMM is about sampling methods. A recent work employs Controlled Direct Pattern Sampling (CDPS) to search for subgroups in the EMM framework [START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF]. CDPS is a sampling method that enables to create random patterns thanks to a procedure based on a controlled distribution [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF]. The authors adapt this sampling methods to EMM to foster subgroups for which the model deviates from those which hold for the whole dataset and with high frequency. More recently, a work employs a sampling method to discover exceptional models induced by attributed graphs [START_REF] Bendimerad | Unsupervised exceptional attributed subgraph mining in urban data[END_REF]. In this work, the authors create a distribution to give more chance to an interesting subgraph to be drawn. The model is based on the characteristics induced by the subgraph. Pattern sampling is attractive as it allows direct interactions with the user for using his/her preferences for driving the search: A result is available anytime. However, traditional sampling methods used in pattern mining need a given probability distribution over the pattern space: This distribution depends on both the data and the measure [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF][START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF]. This probability distribution has to be computed in a pre-processing step. Each iteration is independent and consists of drawing a pattern given this probability distribution. Moreover, these probability distributions exhibit the problem of the long tail: There are many more uninteresting pattern than interesting ones. Thus, the probability to draw an uninteresting pattern is still high, and not all local optima may be drawn: There are no guaranties on the completeness of the result set.

The main issues about descriptive rules mining

Subgroup discovery and its generalization exceptional model mining highlight several issues that have to be addressed to propose correct and efficient approaches for supervised descriptive rule discovery. The existing works focus on the definition of new models with their quality measures to capture more interesting patterns. The issue of diversity in the result set is at the core of heuristic searches: How to ensure a good diversity in the results when applying heuristic exploration methods? In addition, how interactive algorithms can improve the extraction of more interesting subgroups by taking into account the expert's preferences during the exploration? Finally, how to ensure an efficient extraction of the patterns by exhaustive or heuristic searches? In the following, we detail and discuss the existing approaches to handle these issues.

Choosing the appropriate model

EMM is based on a class model, and the aim is to search for subgroups of individuals for which the model induced on the target attributes deviates significantly from the model of the whole dataset (or of the complement of the subgroup). Several models have been proposed in the state of the art [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF], e.g., the linear regression between two numerical class attributes [START_REF] Duivesteijn | Different slopes for different folks: mining for exceptional regression models with cook's distance[END_REF], or the contingency tables for several class labels [START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF] or the Bayesian networks computed on the class labels [START_REF] Duivesteijn | Subgroup discovery meets bayesian networks -an exceptional model mining approach[END_REF]. The choice of the model depends on both the target attributes and the purpose of the application [START_REF] Duivesteijn | Different slopes for different folks: mining for exceptional regression models with cook's distance[END_REF]. The main stream of works about EMM consists of finding new class models to deal with specific datasets and objectives. In [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF], the authors define lots of possible models that have been used. The simplest models deal with the correlation (or association) between two target attributes: The aim is to find subgroups for which the correlation is significantly different from those induced on the entire dataset. One can also be interested in the difference of the linear regression of one numerical target attribute in the subgroups, by comparing for instance the slope of these models. More complex models can also be suitable for specific cases, e.g., the models based on Bayesian networks. In this setting, it is assumed that there are multiple nominal target attributes. A subgroup is considered as interesting if the conditional dependency relations between the target attributes are significantly different in the subgroup from those of the entire dataset. For that, the Bayesian networks of both the subgroups and the entire dataset are compared [START_REF] Duivesteijn | Subgroup discovery meets bayesian networks -an exceptional model mining approach[END_REF]. Recently, a new model has been proposed to handle ranking data. The Rank Correlation Model Class has been introduced to be less sensitive to the outliers that are in the target attributes [START_REF] Downar | Exceptionally monotone models -the rank correlation model class for exceptional model mining[END_REF]. This class model no longer uses the values taken by the target attributes but their rank. This method only works if there are two target attributes that can be ordered (to get the rank of the values): Ordinal or numerical attributes are taken into account.

In our work, since the experts of the domain are interested in descriptive rules that conclude on few labels, we propose a new EMM instance that considers several target subspaces. In other words, from a subgroup, several models are derived: A model is built on each subset of labels. The model we define is based on both the precision and the recall of the subgroup w.r.t. a given target subspace.

Quality measures

Once the model is chosen, it is required to select the quality measure that compares two instances of the models. The quality measure is the core of the method in SD or EMM. Indeed, it enables to quantify the difference between the model induced by the subgroup and those of the entire dataset. The quality measure depends on both the model and the purpose of the application. There exists a large pool of quality measures in the literature [START_REF] Lavrac | Rule evaluation measures: A unifying view[END_REF][START_REF] Abudawood | Evaluation measures for multi-class subgroup discovery[END_REF]. Usually, when the application is specific, it requires to design a new quality measure that enables to encode the needs of the experts, i.e., the so-called subjective interestingness. Konijn et al. present several quality measures when facing datasets with two target attributes: A binary attribute that corresponds to the main class with the values positive or negative and the second target attribute represents a cost [START_REF] Konijn | Cost-based quality measures in subgroup discovery[END_REF]. From that, they designed several cost-based quality measures that enable to find out interesting subgroups for which the cost target attribute differs for positive examples from the cost attribute values of the whole dataset. Moreover, they employ a new exploration method based on the Local Subgroup Discovery (LSD). Contrary to the traditional Descriptive Subgroup Discovery (DSD) that performs a top down exploration by extending the description, LSD enables to zoom in a part of the dataset: It searches for the nearest neighbors of a reference subgroup to detect close subgroups that deviate from this reference group. Thus, the aim is to find out a subgroup that is close to a reference subgroup but for which the cost attribute is really different from this reference subgroup. Duivesteijn et al. employ a new model class for EMM [START_REF] Duivesteijn | Subgroup discovery meets bayesian networks -an exceptional model mining approach[END_REF]. They propose to use the interdependencies of the target variables to quantify the quality of the subgroups. For that, they associate EMM with a model class based on Bayesian networks on the target variables. They design several quality measures to evaluate the distance between two Bayesian networks. In the case of regression models, Duivesteijn et al. proposed to use the Cook's Distance [START_REF] Duivesteijn | Different slopes for different folks: mining for exceptional regression models with cook's distance[END_REF]. The Cook's distance does not require to normalize the attributes. There are also some theoretical upper bounds on this distance that enables to improve the efficiency of this method by pruning. Concerning the Rank Correlation Model Class, Duivesteijn et al. present several correlation measures based on the ranks of the target attributes that enable to compute the exceptional nature of the subgroups (Spearman's Rank Correlation coefficient, Kendall's Tau, . . . ). Recently, exceptional preferences mining has been defined [START_REF] De Sá | Exceptional preferences mining[END_REF] to extract subgroups where the preference relations between subsets (using label ranking) of class labels significantly deviate from those of the entire dataset. Finally, the extracted subgroups have to bring new information to the experts: We are not interested in obvious subgroups. For that, most of the existing works implement a statistically significance test. For that, they test the distribution of a subgroup against the null hypothesis. If the null hypothesis is rejected, it means that the subgroup is significantly informative.

In our work, we propose several quality measures to compare two instances of the model class we introduce. For that, since the distribution of the labels is skewed, we take into account this high variance in the frequency of the labels to compute the quality measure.

Redundancy and diversity

The redundancy is one of the main issues for SD or EMM to ensure enough diversity in the result set. Indeed, once the subgroups have been extracted, the result set contains many duplicates. Indeed, there are several subgroups that are related to the same local optimum: Many variants of the same pattern exist. For example a slightly different interval for a numerical attributes induces a little change in the subgroup of objects. This causes top-k mining algorithms to return highly redundant result sets, while ignoring many potentially interesting results. To avoid the redundancy in the result set and to improve the diversity, many researchers proposed to filter out redundant subgroups. A first attempt was proposed by van Leeuwen et al. [START_REF] Van Leeuwen | Non-redundant subgroup discovery in large and complex data[END_REF]. This work not only considers the subgroups as individual ones but as a set of subgroups. For that they introduced the subgroup set mining task. They proposed a similarity measure to filter out redundant subgroups based on the subgroup descriptions and the extents of the subgroups. They also used this similarity measure to implement several beam selections to take into account the redundancy at each level of the beam search. They introduced the Diverse Subgroup Set Discovery algorithm that implements these methods [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF]. To go further, van Leeuwen et al. also proposed to use skylines methods to deal with redundant subgroups [START_REF] Van Leeuwen | Discovering skylines of subgroup sets[END_REF]. In fact, considering the Pareto front ensures to avoid some of the redundant subgroups of the result set.

In our work, to remove redundancy in the result set, we apply the support-based similarity measure that is used in most of the existing works in SD/EMM. This similarity measure is applied in a post-processing step, to filter out redundant subgroups from the result set.

Algorithmic improvements

Many papers address algorithmic issues for SD and EMM. Considering the exhaustive searches, the major improvement is about the data structure used. The paper of Atzmüller and Puppe [START_REF] Atzmüller | SD-map -A fast algorithm for exhaustive subgroup discovery[END_REF] proposes to use the well known FP-Growth approach to deal with subgroup discovery. It results in great improvements of the efficiency of the extraction in terms of runtime. Moreover, the use of efficient pruning strategies is an alternative to reduce the runtime of the exploration. In [START_REF] Grosskreutz | Tight optimistic estimates for fast subgroup discovery[END_REF], the authors propose to implement tight optimistic estimates to prune uninteresting parts of the search space. They are able to compute an upper bound on the quality measure of a subtree, and if it is too low, they prune this subtree since it will not provide better results. Finally, several algorithms implement the parallelization of the execution of the source code. In this way, the runtime reduces. This parallelization is more or less efficient w.r.t. the exploration method of the search space: Some exploration methods are more likely to be processed in a parallelization way than others. However, most of the recent works have focused on beam search and do not discuss the choice of this greedy method that really poorly explores the search space. In fact, they are able to extract only few local optima from the search space (see Figure 6b)).

Later, we define the completeness issue as the ability of an heuristic method to extract as many local optima as possible. In our work, we propose a new enumeration method based on

Conclusion

Monte Carlo tree search to address the completeness issue [START_REF] Browne | A survey of monte carlo tree search methods[END_REF].

Instant mining and interactivity

A new trend of SD/EMM methods is related to the instant mining approaches. Basically, SD or EMM are frameworks that extract interesting subgroups that are easily understandable and actionable by the experts. The end user, i.e., the expert, is on the core of SD/EMM. The description of the subgroup is constructed to be as simple as possible. In this matter, instant mining methods provide a great advantage to an end user application. For that, sampling approaches are efficient as they provide anytime a solution [START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF]. The longer the time budget, the better the result set. To a lesser extent, beam search and exhaustive search are less able to be considered as instant mining methods. In fact, their greedy approach fails at providing interesting patterns anytime. To go further with instant mining tools, many recent algorithms are designed to interact with the experts. In this way, the expert can guide the exploration to foster on the areas within the search space he/she prefers. Typically, with a beam search, the expert can add or remove some subgroups from the beam. Thus, the exploration of the next level is guided by the expert's preferences [START_REF] Dzyuba | Interactive discovery of interesting subgroup sets[END_REF].

In our work in olfaction, we implement an interactive Web application to take into account the expert's preferences to guide the exploration. This application is used by the neuroscientists and the chemists to elicit new hypotheses on the structure-odor relationship.

Conclusion

Subgroup discovery has attracted a lot of attention since its introduction in the middle of the 90's. Its generalization into the exceptional model mining framework enables to take into account more complex hidden relations in the data. The definition of new models with specific quality measures has widened the scope of applications. Although several issues have been solved (such as the redundancy problem in the result), it remains some open problems that need to be addressed: For example, the development of a new anytime heuristic method that enables to efficiently explore the search space without any knowledge on the distribution of the quality measure over it. Indeed, most of the recent works employ a beam search strategy that greedily explores the search space with several hill climbings run in parallel. Clearly, it can not result in a set of subgroups that covers most of the local optima. As our major contribution, we propose to tackle this issue by developing a new heuristic algorithm for SD/EMM based on Monte Carlo tree search.

Chapter 3

Monte Carlo Tree Search

Monte Carlo tree search (MCTS) is a search method used in several domains for finding an optimal decision. It relies on taking successive random samples of the search space and build or update a tree accordingly [START_REF] Browne | A survey of monte carlo tree search methods[END_REF]. MCTS merges different theoretical results obtained from decision theory, game theory, Monte Carlo and bandit-based methods. We introduce preliminary notions and definitions before developing the basic MCTS algorithm, called UCT. There are lots of works that deal with MCTS. Here, we present only what is needed to understand our contribution in the next chapter. An exhaustive survey about MCTS until 2012 is [START_REF] Browne | A survey of monte carlo tree search methods[END_REF].

Background

Decision theory

Studying which decision to take w.r.t. a set of observations and past actions is one of the most explored problem in the 20 th century [START_REF] Russell | Artificial Intelligence -A Modern Approach[END_REF]. Several models have been implemented to represent and understand such a phenomena. For instance, the Markov Decision Problem (MDP) is applied to model sequential decision problems. This model relies on a set of states S, a set of actions A, a transition model T ps, a, s 1 q that determines the probability to reach the state s 1 from the state s playing the action a, and a reward function Rpsq that evaluates the quality of reaching a state s. Therefore, the decisions are modeled with sequences of state-action pairs ps, aq. The aim is to find policies that specify which action to play from each state. The higher the reward the better the policy.

Game theory

Game theory is the extension of the decision theory in which several agents can interact during the process. Considering a set of states S containing terminal states S T Ď S, the reward function usually assigns to a terminal state a reward among t´1, 0, 1u for a loss, draw or win, and the reward 0 for a non terminal state. Each player's strategy evaluates the probability for a player to choose an action given a specific state. In some cases, the players' strategies can form a so called Nash equilibrium, if none of the players can obtain a better reward by unilaterally switching his/her strategy [START_REF] Russell | Artificial Intelligence -A Modern Approach[END_REF]. The games are described by several properties w.r.t. their characteristics: The zero-sum games (the sum of all the players' rewards is null), the information aspects of the games (complete or not), the determinism (the game contains random transitions or not), sequential games (the actions are chosen sequentially or simultaneously), real time or discrete games, etc. To explore these games, one of the most famous strategy is Minimax that tries to minimize the reward of the opponents while maximizing its own reward.

Monte Carlo methods

Determining which action to play given a specific state can also be computed thanks to sampling methods such as Monte Carlo methods [START_REF] Abramson | Expected-outcome: A general model of static evaluation[END_REF]. This approach is used to approximate the gametheoretic value of an action by performing several simulations of the game from the current state to a terminal state. Then, the player can select the action that experimentally leads to better rewards. However, this naive sampling method does not use the past experiences of choosing an action to bias the choice of the following simulations. For that, the theoretical results obtained with bandit-based methods are useful.

Bandit based methods

The bandit problem is a well known class of sequential decision problems. Considering a multiarmed bandit slot machine containing K arms, the goal is to choose the arm that maximizes the cumulative rewards. Each arm of the machine follows a probability distribution of its reward that is unknown by the player. The aim is to find the arm that proposes the best expected reward by playing as few times as possible. However, the potential rewards can be estimated thanks to the past observations. This leads to an exploration/exploitation trade-off: The player wants to play with the arm that gave the best rewards so far (exploitation), but he has also to play with the other arms that may turn out to be superior in the long run (exploration). For that, the player's regret is considered. After N plays the player's regret is:

R " µ ˚N ´K ÿ j"1 µ j ErT j pN qs where µ ˚" K max j"1
µ j is the best possible expected rewards, µ j is the expected reward of the arm j and ErT j pN qs is the expected number of times the arm j is played in the first N trials. Thus, the regret is the expected loss due to not playing the optimal arm. Determining the optimal arm to play can be done thanks to confidence bounds. For example, the upper confidence bound policy proposed in [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], called UCB1, has an expected logarithmic growth of regret uniformly over N . This policy assumes that the player has to play the arm A j that maximizes:

U CB1pA j q " QpA j q `d 2 ln N N pA j q
where QpA j q is the average reward of the arm A j obtained so far, N pA j q is the number of times the arm A j has been played and N is the overall number of plays. The term QpA j q encourages the exploitation of interesting rewards, whereas the term b 2 ln N N pA j q encourages the exploration of few played actions.

The UCT algorithm

MCTS is a search method used in several domains to find an optimal decision (see [START_REF] Browne | A survey of monte carlo tree search methods[END_REF] for a survey). It merges theoretical results from decision theory [START_REF] Russell | Artificial Intelligence -A Modern Approach[END_REF], game theory, Monte Carlo [START_REF] Abramson | Expected-outcome: A general model of static evaluation[END_REF] Select Expand Roll-out Update

Figure 11: One MCTS iteration (inspired from [START_REF] Browne | A survey of monte carlo tree search methods[END_REF]).

and bandit-based methods [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. MCTS is a powerful method because it allows the joint use of random simulations and a trade-off between exploration of the search tree and the exploitation of an interesting solution based on past observations [START_REF] Browne | A survey of monte carlo tree search methods[END_REF]. Considering a game, e.g., Go, the goal of MCTS is to find the best action to play given a current game state. MCTS proceeds in several (limited) iterations that build a partial game tree (called the search tree) depending on the results of the previous iterations. The nodes represent the game states. The root node is the current game state. The children of a node are the game states accessible from this node by playing an available action. The terminal nodes are the terminal game states. Each iteration, consisting of 4 steps (see Figure 11), leads to the generation of a new node in the search tree (depending on the exploration/exploitation trade-off due to the past iterations) followed by a simulation (sequence of actions up to a terminal node). Any node s in the search tree is provided with two values: The number N psq of times it has been visited, and a value Qpsq that corresponds to the aggregation of rewards of all simulations walked through s so far (e.g., the proportion of wins obtained for all simulations walked through s). The aggregated reward of each node is updated through the iterations and becomes more and more accurate. Once the computation budget is reached, MCTS returns the best move that leads to the child of the root node with the best aggregated reward Qp.q. In the following, we detail the 4 steps of a MCTS iteration applied to a game. Algorithm 1 gives the pseudo code of the most popular algorithm in the MCTS family, namely UCT (Upper Confidence bound for Trees) [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF].

The Select policy

Starting from the root node, the Select method recursively selects an action (an edge) until the selected node is either a terminal game state or is not fully expanded (there remain children of this node that are not yet expanded in the search tree). The selection of a child of a node s is based on the exploration/exploitation trade-off. For that, upper confidence bounds (UCB) are used. They estimate the regret of choosing a non-optimal child. The original UCBs used in MCTS are the UCB1 [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] and one of its variant, namely the UCT:

U CT ps, s 1 q " Qps 1 q `2C p d 2 ln N psq N ps 1 q
where s 1 is a child of a node s and C p ą 0 is a constant (generally, C p " 1 ?

2 ). This step selects the most urgent node to be expanded, called s sel in the following, considering both the exploitation of interesting actions (given by the first term in UCT) and the exploration of lightly explored areas of the search space (e.g., given by the second in UCT) based on the result of past iterations.

The Update policy

The reward ∆ is back-propagated to the root, updating for each parent the number of visits N p.q (incremented by 1) and the aggregation reward Qp.q (the new proportion of wins).

Example 12. Figure 12 presents the first five iterations performed by the UCT algorithm for the TicTacToe game. Let us consider that the player p 1 plays against the player p 2 . p 1 plays with the green circles and p 2 the red crosses. The current state of the game is given in Figure 12a. It is the player p 1 's turn to play. The root of the tree is the current state. It is provided with two values:

The number of times N it has been visited, and the proportion of wins Q. From this current state, the UCT algorithm can be run. The result of the first iteration, consisting of the four steps, is given in Figure 12b. During the first iteration, the method Select returns the root node (since it remains some of its children to expand). From the root node, i.e., the current state of the game, we randomly expand it with a not yet expanded child: The expanded node s exp corresponds to the game state where p 1 plays in the middle cell of the third row. From this expanded node, a simulation is randomly played up to reach a terminal game state. In the case of the first iteration, the simulation reaches the terminal game state in which p 1 wins. The reward ∆ " 1 is back propagated through all the parents of s exp : Thus the value N is incremented by one for all the parent nodes (since we visited these nodes one more time) and the value Q is set to 1 since the simulation leads to a win of p 1 . Note that only the expanded node is stored within the tree, the nodes of the simulation are not stored in the tree. The second iteration consists in expanding the root node with another child that is not yet expanded in Figure 12c. For example, the child in which p 1 plays the cell in the middle of the first row. From this expanded node, a simulation is rolled out until a terminal state in which p 1 looses. The Update method back-propagates the reward by updating the value Q of the root node to 0.5 and increments the number of visits. Figure 12d and Figure 12e are related to the third and fourth iterations. Figure 12f is about the fifth iteration, but in this case, the Select method is a bit different since all the children of the root node are expanded. Thus, it is required to select one of these four children as the selected node s sel . Due to the UCB measure, since all these children have been visited once, the exploration term of the UCB is the same for all the children. The exploitation term determines which child will be selected. Thus the algorithm selects randomly the second or the third child of the root node since they are the node that have led to a win. When the computational budget is reached, p 1 will

Improvements and issues

play the action that leads to the best child of the current game state, i.e., with the child of the root node with the highest value for Q.

Improvements and issues

Monte Carlo tree search has motivated a lot of works for a couple of decades. The UCT algorithm proposes an implementation of a MCTS algorithm that enables to take into account the trade-off between the exploration of few visited parts of the search space and the exploitation of interesting areas by using a generalization of UCB1, namely UCT, in the Select method. The MCTS algorithms are aheuristic (i.e., without any knowledge), anytime (i.e., a solution is always available) and asymmetric (i.e., the expansion of the tree is based on the UCB). In the following, we present several improvements that have been proposed.

The first issue about MCTS is about the trade-off between exploration and exploitation in the enumeration of the search space. Indeed, as it is, MCTS tends to explore more than it exploits. This is partially due to the definition of the UCB but not only. In fact, UCB1 tends to give more importance of the exploration in the first visits of a node since the second term (exploration) of its formula is predominant w.r.t. the first term (exploitation). To tackle this issue, Auer et al. proposed an enhancement of UCB1, called UCB1-Tuned, that reduces the impact of the exploration term of the UCB1 formula [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]:

UCB1-Tunedps, s 1 q " Qps 1 q `g f f e ln N psq N ps 1 q ˆmin ˜1 4 , σ 2 ps 1 q `d 2 ln N psq N ps 1 q
where σ 2 ps 1 q is the variance of the rewards obtained by the child s 1 of the node s so far. Thus, the value exploration factor is at least divided by 2, and if the rewards obtained by the child s 1 are homogeneous, the impact of the exploration term is much more reduced. It means that even if an area of the search space has been lightly explored it is not required to explore it more if the rewards obtained so far during the simulation are similar: We may have a good estimation of the quality of this area. A second solution to tackle the over exploration with MCTS is to proceed to a progressive widening [START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF][START_REF] Coulom | Computing "elo ratings" of move patterns in the game of go[END_REF]: It is not necessary to expand all the children of a node before selecting one of its children. In other words, when using progressive widening, the function Select(s) of Algorithm 1 is replaced by the function of Algorithm 2. This method is based on the following condition that states when it is required to expand the current selected node s based on the number of visits:

t b a N psq `1u ą t b a N psqu
where b usually equals 2 or 4. If this condition holds, the node s is returned as the selected node s sel and another child is expanded. If it does not hold, the Select policy recursively selects a child of s. In this way, it is possible to exploit interesting solutions before expanding (and so exploring) all the children of a node. Given enough time, all the children will be considered and the enumeration would converge to an exhaustive search as well. Now, the question is how to select the child to expand first. Usually, the enhancement RAVE (Rapid Action Value Estimator) is used to efficiently estimate which of the children is the most promising [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF].

While the previous improvements are about the selection and the expansion of a node in the tree, now, we discuss about the back propagation of the rewards. Indeed, as presented in the pseudo code of Algorithm 1, the Update method consists in back propagating both the reward and the number of visits from the expanded node s exp to the root node. However, in the case of Algorithm 2 The Select function using progressive widening.

1: function Select(s) return s 8: end function games (e.g., the Tic Tac Toe game), it is possible to update more than only the path from s exp to the root node. For instance, in Figure 12d that presents the result of the third iteration, the final game state that is reached during the simulation shows that p 1 played in the middle cell of the third row before playing in the right cell of this row. Thus, it could have been interesting (and efficient) to not only update the root node and the expanded node of this iteration, but also the expanded node of the first iteration because this node is the case where p 1 plays in the middle cell of the third row. This enhancement is called All Moves As First (AMAF) and was introduced by Gelly and Silver [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF]. AMAF treats all the actions played during the selection, the expansion and the simulation as if they were played in a selection step. In other word, a child of a node selected during the Select method will be updated if the action leading to this child has been played during the simulation. Besides, Permutation AMAF is an improvement of AMAF in which the update is done for all the paths that can eventually lead to the same final game state reached during the simulation [START_REF] Helmbold | All-moves-as-first heuristics in monte-carlo go[END_REF]. Thus, not only some children are also updated (AMAF), but completely different paths in the tree are updated if they are permutations that can lead to the same final game state. Recently, Cazenave proposed the generalized rapid action value estimation that can use the AMAF values of a parent node if the current node has been lightly explored to have meaningful AMAF statistics [START_REF] Cazenave | Generalized rapid action value estimation[END_REF].

The characteristics of the MCTS algorithms, where each iteration is independent w.r.t. the others, make this approach tractable for parallelisation. In this case, parallelisation can provide great advantages by performing several iterations over the tree in the same time, and thus be able to quickly and efficiently enumerate the search space. In the state of the art, parallelisation for MCTS has been studied from different points of view. First, we can proceed to several parallel simulations from the same expanded node in the tree. This is called leaf parallelisation [START_REF] Chaslot | Parallel monte-carlo tree search[END_REF] or atthe-leaves parallelisation [START_REF] Cazenave | On the parallelization of uct[END_REF]. This allows to sample more efficiently the subspace induced by the expanded node: Several rewards are back propagated and thus the estimation is more accurate. Second, a variant, called root parallelisation, was proposed to directly launch several MCTS in parallel [START_REF] Cazenave | On the parallelization of uct[END_REF][START_REF] Chaslot | Parallel monte-carlo tree search[END_REF]. This enhancement is also called multi-tree MCTS. The information stored in the children of the root node of each MCTS tree is used to select the best action to play. The main advantage over the leaf-parallelisation is that each tree is independent and can be stopped anytime, whereas leaf-parallelisation has to wait for the longer simulation. Lastly, the so-called tree parallelisation enables to run several iterations on the same search tree [START_REF] Chaslot | Parallel monte-carlo tree search[END_REF]. Two variants of tree parallelisation have been proposed: The first consists in using a global mutex on the tree, whereas the second uses several local mutexes on each node of the tree. The first one is used when the simulation are time-consuming w.r.t. the traversal or the update of the tree. The latter is employed in the general case, when there is no guaranties on the run time of the simulations. However, the main drawback of tree parallelisation is that several threads can follow the same path in the tree since the method Select is based on the statistics of the nodes. To tackle this problem, Chaslot et al. gives a temporary penalty to the nodes that are selected by a thread to avoid that they are selected once again by the following threads [START_REF] Chaslot | Parallel monte-carlo tree search[END_REF].

Applications

MCTS algorithms are mainly applied to games, and especially combinatorial games in which traditional methods of artificial intelligence fail. The game Go has become the new benchmark dataset to test AI algorithm [START_REF] Kroeker | A new benchmark for artificial intelligence[END_REF]. Indeed, Go is a traditional 19x19 board game on which 2 players compete against each other. Its branching factor of 250 makes the game Go one of the most difficult board games to play. Go becomes one of the most used dataset to experiment with MCTS algorithms. The program MoGo is the first algorithm for Go that employs MCTS [START_REF] Gelly | A contribution to Reinforcement Learning; application to Computer-Go[END_REF]. This algorithm uses RAVE to improve the efficiency of the exploration of the search tree. It was one of the best programs for playing Go. After that, several programs have been proposed. For instance, the algorithm Fuego, that also uses RAVE, beat a professional Go player. Recently, the Google's team Deep Mind has proposed the best program for the game Go, namely AlphaGo, that is partially based on MCTS [START_REF] Silver | Mastering the game of go with deep neural networks and tree search[END_REF]. This method combines the UCT algorithm and several deep learning tasks that enable to reduce the branching factor and the simulation length. This program beat the professionnal Go player Lee Sedol in March 2016 by winning four among the five games that have been played.

Gaudel and Sebag formalize feature selection as a one-player game and employ the UCT algorithm to solve it with their algorithm FUSE (Feature UCT Selection) [START_REF] Gaudel | Feature selection as a one-player game[END_REF]. This work aims at selecting the features from a feature space that are the more relevant w.r.t. the classification problem. For that, Gaudel and Sebag explore the powerset of the features (i.e., itemsets where the items are the features) with a MCTS method to find the sets of features that minimize the generalization error. Each node of the tree is a subset of feature, and each action consists of adding a new feature in the subset of features. The authors focus on reducing the high branching factor by using UCB1-Tuned and progressive widening with RAVE [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF]. The aim of FUSE is thus to return the best subset of features (the most visited path of the tree), or to rank the features thanks to the RAVE score.

Conclusion

Monte Carlo tree search provides an efficient method to explore a huge search space with a high branching factor. The most famous algorithm, namely UCT, implements a variant of UCB1 that enables to both explore lightly explored areas of the search space but also to exploit interesting solutions encountered so far. Based on this trade-off between the exploration and the exploitation, MCTS algorithms exhibit interesting characteristics:

• They are aheuristic: None prior knowledge on the domain is required. The pattern of the search space is learned incrementally with the number of iterations.

• They are anytime: A solution is always available and the result set keeps on improving with the time. The exploration converges to an exhaustive search if given enough time.

• The expansion of the tree is asymmetric: Based on the exploration/exploitation trade-off performed by the UCB, the tree is expanded in an asymmetric manner.

this highlighting all over the world, MCTS algorithms, to the best of our knowledge, have been seldomly used for other applications than combinatorial games. Gaudel and Sebag have proposed an adaptation of UCT to the combinatorial optimisation problem of feature selection [START_REF] Gaudel | Feature selection as a one-player game[END_REF], but we are not aware of previous attempts to adapt MCTS to pattern mining while it could improve significantly pattern enumeration methods. Indeed, the trade-off between the exploration of few visited parts of the search space and the exploitation of interesting solutions found so far can lead to the discovery of interesting patterns in large search space. Contrary to traditional sampling methods, MCTS algorithms are aheuristic, i.e., there is no need to provide a probability distribution on the pattern space since it is learned incrementally.

Chapter 4

Monte Carlo Tree Search for Pattern Mining

Introduction

Subgroup discovery (SD) is a formal framework that enables to elicit descriptive rules in label data [START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF]. One is given a set of objects associated to descriptions (that form a poset) and a mapping to one or several class labels. A subgroup is a description generalization whose discriminating ability is given by a quality measure (F1-score, accuracy, etc). In the last two decades, different aspects of SD have been widely studied: The description and target languages (quantitative, qualitative, etc.), the algorithms that enable the discovery of the best subgroups, and the definition of measures that express pattern interestingness. These three points are closely related. Many of the first approaches were ad hoc solutions lacking from easy implementable generalizations (see [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF][START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF] for surveys). SD hence faces two important challenges: How to define appropriate quality measures characterizing the singularity of a pattern; How to select an accurate heuristic search technique when an exhaustive enumeration of the pattern space is unfeasible.

In 2008, Lehman et al. introduced a more general framework called exceptional model mining (EMM, [START_REF] Leman | Exceptional model mining[END_REF]) that tackles the first issue. EMM aims to find patterns that cover tuples that locally induce a model that substantially differs from the model of the whole dataset. This framework extends the classical SD settings and leads to a large class of models (i.e., quality measures) and applications, e.g., [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF][START_REF] Bendimerad | Unsupervised exceptional attributed subgraph mining in urban data[END_REF][START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF]. In a similar fashion to other pattern mining approaches, SD and EMM select a heuristic search technique when exhaustive enumeration of the pattern space is unfeasible. The most widely used techniques are beam search [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Meeng | Rocsearch -an roc-guided search strategy for subgroup discovery[END_REF], evolutionary algorithms [START_REF] Del Jesús | Evolutionary fuzzy rule induction process for subgroup discovery: A case study in marketing[END_REF], and recently pattern sampling [START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF][START_REF] Bendimerad | Unsupervised exceptional attributed subgraph mining in urban data[END_REF]. The main goal of these heuristics is to drive the search towards the most interesting parts, i.e., the regions of the search space where patterns maximize a given quality measure (see Chapter 2). However, it often happens that the best patterns are redundant: They slightly differ in terms of their extent (dually intent). While several solutions have been proposed to filter out redundant subgroups, e.g., [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Meeng | Rocsearch -an roc-guided search strategy for subgroup discovery[END_REF], they do not discuss the choice of a beam search even though it causes this drawback. Indeed, a topdown level-wise greedy exploration of the patterns with a controlled level width that penalizes the diversity. Genetic algorithms and pattern sampling techniques are not greedy techniques in general, but the proposals in SD/EMM also face redundancy and diversity issues (see Chapter 2). Moreover, heuristic methods should converge to the result set of an exhaustive search (as many local optima as possible have to be found): They have to maximize the completeness of the result set. Thus, there is still the need for implementing new SD/EMM heuristic exploration paradigms in a way that favors both the patterns diversity (i.e., with less redundancy as possible) and the completeness in the result set. This is the problem we propose to tackle in the present chapter through the use of Monte Carlo tree search (MCTS).

MCTS is a search method [START_REF] Browne | A survey of monte carlo tree search methods[END_REF] mainly used in AI for domains, such as games and planning problems. The strength of MCTS is that it partially explores the search space building a tree in an incremental and asymmetric manner respecting the exploration/exploitation trade-off provided by the upper confidence bounds (UCB) [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF]. MCTS is based on random simulations that are rolled out to explore the search space. Then, the expansion of the tree search depends on the rewards returned by simulations exploiting promising results but also exploring rarely visited parts of the tree. More importantly, the power of random search of MCTS leads to an any-time mining approach, in which a solution is always available, and which converges to an exhaustive search if given enough time and memory. MCTS quickly leads the search towards a diverse pattern set of high quality. In this context, our claims are the following:

• We formalize SD/EMM with an arbitrary pattern language and an arbitrary quality measure as a single-turn single-player game,

• We discuss how the four different existing methods of the UCT algorithm (Select, Expand, RollOut, Update) can be used for a simple description language (itemsets),

• We show how well known notions introduced in the pattern mining literature (DSF enumeration of closed patterns) can be incorporated in a MCTS: It requires to adapt the existing UCBs,

• We explain how our approach is agnostic of the pattern language and it can be instantiated for nominal, numerical and heterogeneous patterns,

• We provide an implementation of pattern mining based on Monte Carlo tree search, called mcts4dm,

• We empirically study our approach on artificial and benchmark data to assess both a better diversity and a high completeness in the result set. It is also where we compare mcts4dm with the main EMM/SD available algorithms.

The rest of this chapter is organized as follows. Section 4.2 reminds the main definitions of SD/EMM and highlights the problem of current search algorithms. Section 4.3 formally introduces SD and EMM as a single-turn single-player game when the patterns are itemsets, and details several ways rooted in pattern mining to solve it. This section also presents the slight adaption to consider numerical and heterogeneous patterns in general. Section 4.4 evaluates the capability of mcts4dm for efficiently finding the most diverse set of interesting patterns of various types. It is then successfully compared to well-known approaches of the literature in Section 4.5 before to conclude.

Subgroup Discovery

Definitions

We briefly recall the main definitions and issues of SD that are essential to make this section self-contained. The definitions of a label data and a subgroup are: A quality measure ϕ is used to evaluate a subgroup. The quality measure reflects the difference between the model induced by the subgroup on the target attribute and the model induced by the entire label dataset. In SD, the model induced by a set of objects S is the proportion of objects of S associated to one class label l P C. The choice of the measure depends on the purpose of the application [START_REF] Fürnkranz | Foundations of Rule Learning[END_REF]. Usually, the Weighted Relative Accuracy (WRAcc) is used in SD [START_REF] Lavrac | Rule evaluation measures: A unifying view[END_REF]. Thus, we recall the SD problem: Problem 2 (The SD problem). Given a label dataset DpO, A, C, classq, a quality measure ϕ, a minimum support threshold minSupp and an integer k, SD aims at extracting the top-k best frequent subgroups w.r.t. ϕ. The quality measure ϕ quantifies a deviation between the model induced by extpdq and O, respectively.

Note that, in the literature, the problem definition of SD can be slightly different from those we use in this section. Our definition is equivalent to those given in [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF] in which we force that the set of constraints includes the minimum support constraint.

SD algorithmic issues

Definition 8 (Subgroup search space). The set of all descriptions is partially ordered and is structured as a lattice. We denote s 1 ă s 2 and say that the subgroup s 1 is more specific than the subgroup s 2 if the description of s 1 is more specific than the one of s 2 w.r.t. the partial order (s 2 is more general than s 1 ). For instance, xr23 ď b ď 29sy is more general than xr128 ď a ď 151s, r23 ď b ď 29sy. Most of the SD/EMM algorithms exploit the lattice of subgroups. 7.

Example 13. To easily recover the figures, we recall the toy label dataset in Table 7 and the lattice given in Figure 10 in the following page. Note that, the domain of a numerical attribute is finite because during the exploration we only consider intervals whose bounds are the values taken in the data. Thus, for each numerical attribute, there are at most |O| different values, i.e., a different one for each object. For each subgroup given by its description, there are 6 possible children: Increasing the lower bound or decreasing the upper bound for each numerical attribute. The top node is the more general description of the subgroups search space: Its extent is O. In the following we consider the lattice of the subgroups as depicted in Figure 6. The nodes (circles) are the subgroups. The local optima (red circles) are the best subgroups w.r.t. the quality measure to extract. The minimum support threshold (green curve) delimits the border between the frequent subgroups and the others. Here, SD aims at extracting the result set containing all the best frequent subgroups (red circles above the green curve) and only them (depending on k).

Issue 1 (Redundancy/Diversity). The quality measure of a subgroup close to a local optimum s ˚in the lattice is similar to -but lower than -the quality measure of s ˚: A slight change in the description of a subgroup s close to s ˚induces -in general -a slight change of the extent of s compared to those of s ˚. It is desirable to avoid extracting the redundant subgroups close to a local optimum: This is the redundancy problem. Figure 6a depicts this phenomena where around each local optimum there is an area that contains redundant subgroups. Several solutions have been proposed for filtering the result set (or, e.g., the beam at each level of a beam search) [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF] by using a similarity measure between patterns (on their support or descriptions) or using heuristic algorithms [START_REF] Bringmann | One in a million: picking the right patterns[END_REF]. In our work, we will use the most popular similarity measure based on the similarity of the extents. Given two subgroups s 1 and s 2 , the similarity measure between s 1 and s 2 is given by the Jaccard coefficient of their extent:

simps 1 , s 2 q " |extps 1 q X extps 2 q| |extps 1 q Y extps 2 q|
Thus, the similarity constraint ensures that given a maximal similarity threshold Θ P r0, 1s, for all subgroups s 1 , s 2 in the result set, simps 1 , s 2 q ď Θ.

Issue 2 (Completeness). When a dataset is too large, an exhaustive exploration of the search space is unfeasible. A heuristic such as beam search allows to explore only a little part of the search space based on a faster but greedy strategy (see Figure 6b). However, beam search comes also with its disadvantages: If some local optima are far away from the root node in the lattice, it is possible that the first levels leading to these optima are weak w.r.t. the quality measure, such that they will be ignored in the search. Sampling method is another popular heuristic approach used in SD/EMM (see Figure 6c). Samplings are based on a probability distribution over the subgroup space that gives more chance to an interesting subgroup to be drawn. Nevertheless, due to the long tail problem (many more subgroups are uninteresting than interesting) lots of uninteresting patterns might be drawn and interesting subgroups might be missed. Completeness entails the notion that all optima should be present in the pattern set result.

One can now define the problem of pattern set enumeration in SD.

Problem 4 (Pattern set discovery). Given DpO, A, C, classq, a quality measure ϕ, a minimum support threshold minSupp, a similarity measure sim, a maximum similarity threshold Θ, an integer k, compute a set of the top-k best patterns w.r.t. ϕ that has as little redundancy (simps 1 , s 2 q ď Θ, for all s 1 , s 2 in the result set) and is as complete as possible.

Pattern mining with MCTS

As previously stated, the problem of SD/EMM consists of finding the frequent patterns that maximize a quality measure ϕ. Let S be the set of all possible patterns. S is ordered thanks to a specialization/generalization hierarchy, a poset pS, ăq which is generally a lattice. The principle of solving the SD/EMM problem with a MCTS is based on the following:

• S corresponds to the set of game states. Each state, or pattern or node of the tree, is given an extent extpsq, a support supppsq and a quality measure ϕpsq. Moreover, we recall that the MCTS method requires that each node is provided with two values: The number of times the node s has been visited N psq, and the average quality of the simulation walked through s so far Qpsq. The initial game state s 0 P S, root of tree, is the most general pattern.

• The actions for generating new game states are defined as pattern restrictions (for deriving pattern specializations/refinements).

• A simulation is a random sequence of actions, or pattern restrictions. A leaf is a maximal frequent pattern, i.e., any of its specializations is infrequent.

Designing a MCTS approach for a pattern mining problem is different than for a combinatorial game. The goal is not to decide, at each turn, what is the best action to play, but to explore the search space of patterns with the benefit of the exploitation/exploration trade-off and the tree that is stored in memory. Consequently, we consider SD/EMM as a single-turn single-player game.

For sake of simplicity, we consider in this section the most simple type of patterns: Itemsets. Obviously, most of our claims are given in the most generic form and can be slightly translated to consider other types of patterns. However, for some definitions, we discuss the case of nominal and numerical attributes. In our experiments, we deal jointly with itemsets, nominal and numerical attributes.

Problem 5 (EMM when descriptions are itemsets). Let I be a set of items. A transaction is a subset of items t Ď I. A transaction database is a set of transactions T " tt 1 , ..., t n u. An itemset is an arbitrary subset of items p Ď I. Its extent is given by extppq " tt P T |p Ď tu, and its support is suppppq " |extppq|. Its evaluation measure ϕppq depends on the quality measure chosen in the EMM instance. The problem is to find the best itemsets w.r.t ϕ.

It follows that the search space is given by S " p2 I , Ďq. The initial pattern is the empty set: s 0 " H. The actions that lead to specializations, or supersets, are the items I. A simulation is a random sequence of item additions. We are now able to specify the strategies of the four steps of the UCT algorithm especially tuned for a SD/EMM problem. Figure 6d is the exploration performed by the MCTS in the lattice of subgroups. Due to the exploration/exploitation tradeoff embedded by MCTS, it suggests both a high diversity and a high completeness in the result set if given enough budget (i.e., enough iterations).

The Select method

The Select method consists of selecting the most promising node s sel in terms of exploration vs. exploitation. For that, the well-known UCT and UCB1 (UCT with C p " 1{2) can be used in our settings. However, more sophisticated UCBs have been designed for single player games. The single-player MCTS (SP-MCTS [START_REF] Schadd | Single-player monte-carlo tree search[END_REF]) adds a third term to the UCB to take into account the variance σ 2 of the rewards obtained by the child so far. SP-MCTS of a child s 1 of a node s is: SP-MCTSps, s 1 q " Qps 1 q `Cd 2 ln N psq N ps 1 q `dσ 2 ps 1 q `D N ps 1 q where the constant C is used to weight the exploration term (it is fixed to 0.5 in its original definition [START_REF] Schadd | Single-player monte-carlo tree search[END_REF]) and the term D N ps 1 q inflates the standard deviation for infrequently visited children (D is also a constant). In this way, the reward of a rarely visited node is considered as less certain: It is still required to explore it to get a more precise estimate of its variance. If the variance is still high, it means that the subspace from this node is not homogeneous w.r.t. the quality measure and then further exploration is needed.

Also, UCB1-Tuned [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] is designed to reduce the impact of the exploration term of the original UCB1 by weighting it with either an approximation of the variance of the rewards obtained so far or the factor 1{4. UCB1-Tuned of a child s 1 of s is:

UCB1-Tunedps, s 1 q " Qps 1 q `g f f e ln N psq N ps 1 q min p 1 4 , σ 2 ps 1 q `d 2 ln N psq N ps 1 q q
If required, the pattern evaluation measure ϕ can be normalized (e.g., for UCT).

The Expand method

The Expand step consists in adding a new node in the search tree. In the following, we present different refinement operators, and how to avoid duplicate nodes in the search tree.

The refinement operators

The simple way to expand the selected node s sel is to choose uniformly an available attribute w.r.t. s sel , that is to specialize s sel into s exp such that s exp ă s sel : s exp is a refinement of s sel .

Definition 9 (Refinement operator).

A refinement operator is a function ref : S Ñ 2 S that derives from a pattern s a set of more specific patterns ref psq such that:

• (i) @s 1 P ref psq, s 1 ă s • (ii)@s 1 i , s 1 j P ref psq, i ‰ j, s 1 i ł s 1 j , s 1 j ł s 1 i
The extent of a refined pattern s 1 P ref psq is included in the extent of the pattern s. Formally, @s i P ref psq, extps 1 q Ď extpsq. Then, suppps 1 q ď supppsq. This is a basic property known as anti-monotonicity of the support.

In other words, a refinement operator gives to any pattern s a set of its specializations, that are pairwise incomparable (an anti-chain). The refine operation can be implemented in various ways given the kind of patterns we are dealing with. Most importantly, it can return all the direct specializations only to ensure that the exploration will, if given enough budget, explore the whole search space of patterns. Furthermore, it is unnecessary to generate infrequent patterns.

Definition 10 (Direct-refinement operator).

A direct refinement operator is a refinement operator directRef : S Ñ 2 S that derives from a pattern s the set of direct more specific patterns s 1 such that:

• (i) @s 1 P directRef psq, s 1 ă s • (ii) Es 2 P S s.t. s 1 ă s 2 ă s
• (iii) For any s 1 P directRef psq, s 1 is frequent, that is suppps 1 q ě minSupp Example 14. First, let us consider EMM when descriptions are itemsets and a pattern s. The direct-refinement operator is given by directRef psq " ts Y i | i P pIzsqu. There are at most |A| " |I| children for a pattern s in the search tree. Second, when dealing with nominal attributes, for each nominal attribute a P A, we can derive |Dompaq| different children: One for each available value of the attribute a. For a pattern s, the direct-refinement operator is directRef psq " ts Y ra i " v j s | a i P pAzAttrpsqq ^vj P Dompa i qu, where Attrpsq is the set of attributes already used in the effective restrictions of s. Finally, for numerical attributes, we can derive two directrefined subgroups for each numerical attribute: Applying the minimal left change (increasing the lower bound of the interval to the next higher value taken in the data) and the minimal right change (decreasing the upper bound of the interval to the next lower value taken in the data) [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF]. Thus, there are at most 2 ˆ|A| children for a pattern s in the search tree.

Definition 11 (The direct-expand strategy). We define the direct-expand strategy as follows: From the selected node s sel , we randomly pick a -not yet expanded -node s exp from directRef ps sel q and we add it in the search tree.

Below, we propose two different strategies that address the usual problem in pattern mining: A pattern s sel can be expanded into a node s exp with the same extent. Most quality measures ϕ used in SD and EMM are solely based on the extent of the patterns [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF][START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF]. However, with the direct-refinement operator, a large number of tree nodes may have the same extent (and thus the same support) as their parent, hence the same quality measure value. This redundancy may bias the exploration and more iterations will be required. For that, we propose to use the notion of closed patterns and their generators. The following definition overrides Definition 2 and Definition 3 considering the generic lattice structure pS, ăq: Definition 12 (Closed descriptions and their generators). The equivalence class of an pattern s is given by rss " ts 1 P S | extpsq " extps 1 qu. Each equivalence class has a unique smallest element w.r.t. ă that is called the closed pattern: s is said to be closed iff Es 1 such that s 1 ă s and extpsq " extps 1 q. The non-closed patterns are called generators.

Definition 13 (Generator-refinement operator).

A generator refinement operator is a refinement operator genRef : S Ñ 2 S that derives from a pattern s the set of more specific patterns s 1 such that:

• (i) @s 1 P genRef psq, s 1 R rss • (ii) Es 2 P SzgenRef psq s.t.
s 2 R rss, -s 2 R rs 1 s, and s 1 ă s 2 ă s • (iii) For any s 1 P genRef psq, s 1 is frequent, that is suppps 1 q ě minSupp Example 15. For itemsets and nominal attributes, the generator-refinement operator of a pattern s is given by: genRef psq " ts 1 P directRef psq | suppps 1 q ‰ supppsqu. In other words, with the generator-refinement operator, the children of a pattern s are the direct-refined patterns that are not in the same equivalence class than s. For numerical attributes, the generator-refinement operator still derives two refined patterns for each attribute: Iteratively applying minimal left (resp. right) changes until the support changes. Definition 14 (The gen-expand strategy). To avoid the exploration of patterns with the same extent in a branch of the tree, we define the gen-expand strategy as follows: From the selected node s sel , we randomly pick a -not yet expanded -refined pattern from genRef ps sel q, called s exp , and add it to the search tree.

Besides, when facing a SD problem whose aim is to characterize a label l P C we can implement an extension of the previous refinement operator based on generators on the extents of both the subgroup and the label.

Definition 15 (Label-refinement operator)

. A label refinement operator w.r.t. l P C is a refinement operator labRef : S Ñ 2 S that derives from a pattern s the set of more specific patterns s 1 such that:

• (i) @s 1 P labRef psq, ext l ps 1 q ‰ ext l psq, with ext l psq " to P extpsq | classpoq " lu

• (ii) Es 2 P SzlabRef psq s.t.
ext l ps 2 q ‰ ext l psq, -ext l ps 2 q ‰ ext l ps 1 q, and s 1 ă s 2 ă s • (iii) For any s 1 P labRef psq, s 1 is frequent, that is suppps 1 q ě minSupp Example 16. For itemsets and nominal attributes, the label-refinement operator of a pattern s w.r.t. the label l P C is given by: labRef psq " ts 1 P genRef psq | supp l ps 1 q ‰ supp l psqu. For numerical attributes, the label-refinement operator still derives two refined patterns for each attribute: Iteratively applying minimal left (resp. right) changes until the number of objects in the extent associated to l is changed.

Definition 16 (The label-expand strategy). From the selected node s sel , when facing a SD problem, the label-expand strategy consists in randomly picking a -not yet expanded -refined pattern from labRef ps sel q, called s exp , and adding it to the search tree.

Avoiding duplicates in the search tree

Previously, we defined several refinement operators to avoid the redundancy within a branch of the tree, i.e., do not expand s sel with a pattern whose extent is the same because the quality measures ϕ will be equal. However, another redundancy issue remains at the tree scale. Indeed, since the pattern search space is a lattice, a pattern can be generated in nodes in different branches of the Monte Carlo tree, that is, with different sequences of actions. For example, with I " ta, b, cu, all permutations of the sequence xa, b, cy could be generated. As such, it will happen that a part of the search space is sampled several times in different branches of the tree. However, the visit count N psq of a node s will not count visits of other nodes that depict exactly the same pattern: The UCB is biased. To tackle this aspect, we implement two methods: (i) Using a lectic order or (ii) detecting and unifying the duplicates within the tree. These two solutions can be used for any refinement operator. Note that, enabling both these solutions is useless since each of them ensures to avoid duplicates within the tree.

Lectic order (LO).

A solution is to generate each pattern only once. The visit count should be then adapted accordingly. First we detail the enumeration procedure. Then, we show how to adapt the visit count in the computation of the UCB.

Pattern enumeration without duplicate is at the core of constraint-based pattern-mining [START_REF] Boulicaut | Constraint-based data mining[END_REF]: The goal of exhaustive search is to output the correct, complete and non-redundant collection of patterns. Most of the time, such a non-redundant exploration is based on a total order on the set of attribute restrictions. This poset is written by pA, Ìq.

Example 17. For itemset patterns, A " I and a lectic order is chosen on I. Usually, it is the lexicographic order, e.g., a Ì b Ì c Ì d for A " ta, b, c, du: Thus, for example, bc Ì ad. A complete and non redundant enumeration of all patterns is then direct. Consider that a node s has been generated with a restriction a i : We can expand the node only with restrictions a j such that a i Ì a j . This total order also holds for numerical attributes by considering the minimal changes (see the work of Kaytoue et al. for further details [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF]).

We can use this technique to enumerate the lattice with a depth-first search (DFS), which ensures that each element of the search-space is visited exactly once. An example is given in Figure 13. However, it induces a strong bias: An MCTS algorithm would sample this tree instead of sampling the pattern search space. In other words, a small restriction w.r.t. Ì has much less chances to be picked than a largest one. Going back to the example in Figure 13 (middle), the item a can be draw only once through a complete DFS; b twice; while c four times (in bold). It follows that patterns on the left hand side of the tree have less chances to be generated, e.g., probpta, buq " 1{6 while probptb, cuq " 1{3. These two itemsets should however have the same chances to be picked as they have the same size. This disequilibrium can be corrected by weighting the visit counts in the UCT with the normalized exploration rate (see Figure 13 (right)).

Definition 17 (Normalized exploration rate). Let S be the set of all possible patterns. The normalized exploration rate of a pattern s is:

ρ norm psq " V total psq V lectic psq " |ts 1 |s 1 ă s P Su| |ts 1 |s Ì s 1 ^s1 ă s P Su|
From this normalized exploration rate we can adapt the UCBs when enabling the lectic order. For example, we can define the DFS-UCT of a child s 1 of a pattern s derived from the UCT as follows:

DFS-UCTps, s 1 q " Qps 1 q `2C p d 2 ln pN psq ¨ρnorm psqq N ps 1 q ¨ρnorm ps 1 q Proposition 1 (Normalized exploration rate for itemsets). For itemsets, let s i be the child of s obtained by playing action a i and i is the rank of a i in pA, Ìq: ρ norm ps i q " 2 p|I|´|s i |q 2 p|I|´i´1q . Proof. Let V lectic ps i q be the size of the search space sampled under s i using a lectic enumeration, and V total ps i q be the size of the search space without using a lectic enumeration. The exploration rate is thus given by ρps i q " N ps i qˆV total ps i q V lectic ps i q . Thus, ρ norm ps i q " V total ps i q V lectic ps i q where V total ps i q " 2 p|I|´|s i |q and V lectic ps i q " 2 p|I|´i´1q for itemsets.

Proposition 2 (Normalized exploration rate for a numerical attribute). For a single numerical attribute a, ρ norm p.q is defined as follows :

• Let s 1 " xα i ď a ď α j y obtained after a left change: ρ norm ps 1 q " 1.

• Let s 1 " xα i ď a ď α j y obtained after a right change. Let n be the number of values from Dompaq in rα i , α j s: ρ norm ps 1 q " n`1 2 . Proof. As explained in the proof of the DFS-UCT for itemsets (Proposition 1), ρ norm psq " V total psq V lectic psq . For a numerical attribute, V total psq " npn `1q{2, i.e. the number of all sub intervals. If s was obtained after a left change, V lectic psq " npn `1q{2 as both left and right changes can be applied. If s was obtained after a right change, V lectic psq " n, as only n right changes can be applied. It follows that ρ norm psq " npn`1q{2 npn`1q{2 " 1 if s was obtained from a left change and ρ norm psq " npn`1q{2 n " n`1 2 otherwise.

Permutation unification (PU).

The permutation unification is a solution that allows to keep a unique node for all duplicates of a pattern that can be expanded within several branches of the tree. This is inspired from Permutation AMAF, a method used in traditional MCTS algorithm to update all the nodes that can be concerned by a play-out [START_REF] Helmbold | All-moves-as-first heuristics in monte-carlo go[END_REF]. A unified node no longer has a single parent but a list of all duplicates' parent. This list will be used when back-propagating a reward. This is made precise in Algorithm 3. Consider that the node s exp has been chosen as an expansion of the selected node s sel . The tree generated so far is explored for finding s exp elsewhere in the tree: If s exp is not found, we proceed as usual; otherwise s exp becomes a pointer to the duplicate node in the tree. In our MCTS implementation, we will simply use a hash map to store each pattern and the node in which is has been firstly encountered.

Algorithm 3

The permutation unification principle.

The RollOut method

From the expanded node s exp a simulation is run (RollOut). With standard MCTS, a simulation is a random sequence of actions that leads to a terminal node: A game state from which a reward can be computed (win/loss). In our settings, it is not only the leaves that can be evaluated, but any pattern s encountered during the simulation is given with its quality measure ϕpsq. Thus, we propose to define the notion of path (the simulation) and reward computation (which nodes are evaluated and how these different rewards are aggregated) separately.

Definition 18 (Path Policy). Let s 1 the node from which a simulation has to be run (i.e., s 1 " s exp ). Let n ě 1 P N, we define a path pps 1 , s n q " ts 1 , . . . , s n u as an ordered list of patterns starting from s 1 and ending with s n such that: @i P t1, . . . , n ´1u, s i`1 is a refined pattern of s i . We denote Pps 1 , s n q the set of all possible paths from s 1 to s n .

• naive-roll-out: A path length n is randomly picked in p1, ..., pathLengthq where pathLength is given by the user (pathLength " |I| by default) using the direct refinement operator.

• direct-freq-roll-out: The path is extended with a randomly chosen restriction until it meets an infrequent pattern s n`1 using the direct refinement operator. s n is a leaf of the tree in our settings.

• large-freq-roll-out overrides the direct-freq-roll-out by using specializations that are not necessarily direct. Several actions are added instead of one to create a new element of the path. The number of added actions is randomly picked in p1, ..., jumpLengthq where jumpLength is given by the user (jumpLength " 1 gives the previous policy). A jump of m direct refinements only requires to explore once the data, whereas m successive direct refinements require to explore m times the data. Thus, this policy will drastically reduce the simulation times yet still properly exploring parts of the search space.

Definition 19 (Reward Aggregation Policy).

Let s 1 the node from which a simulation has been run and pps 1 , s n q the associated random path. Let E Ď pps 1 , s n q be the subset of nodes to be evaluated. The aggregated reward of the simulation is given by: ∆ " aggrptϕpqq@q P Euq P r0; 1s where aggr is a aggregation function. We define several reward aggregation policies:

• terminal-reward: E " ts n u and aggr is the identity function.

• random-reward: E " ts i u with a random 1 ď i ď n and aggr the identity function.

• max-reward: E " pps 1 , s n q and aggr is the maxp.q function

• mean-reward: E " pps 1 , s n q and aggr is the meanp.q function.

• top-k-mean-reward: E " top-kppps 1 , s n qq, aggr is the meanp.q function and top-k(X) returns the k elements with the highest ϕ.

A basic MCTS forgets any state encountered during a simulation. This is not optimal for single player games [START_REF] Björnsson | Cadiaplayer: A simulation-based general game player[END_REF]: A pattern with a high ϕ should not be forgotten as we might not expand the tree enough to reach it. We propose several memory strategies for our concern.

Definition 20 (Roll-out Memory Policy

). A roll-out memory policy specifies which of the nodes of the path p " ps 1 , s n q shall be kept in an auxiliary data structure M .

• no-memory: Any pattern in E is forgotten.

• all-memory: All evaluated patterns in E are kept.

• top-k-memory: A list M stores the best k patterns in E w.r.t. ϕp.q.

The Update method

The back-propagation method updates the tree according to a simulation. Let s sel be the selected node and s exp its expansion from which the simulation is run: This step aims at updating the estimation Qp.q and the number of visits N p.q of each parent of s exp recursively. Note that s exp may have several parents when we enable the permutation unification. The number of visits N p.q is always incremented by one. We consider three ways of updating Qp.q:

• mean-update: Qp.q is the average of the rewards ∆ back-propagated through the node so far (basic MCTS).

• max-update: Qp.q is the maximum reward ∆ back-propagated through the node so far. This strategy allows to identify a local optimum within a part of the search space that contains most of uninteresting patterns. Thus, it gives more chance for this area to be exploited in the next iterations.

• top-k-mean-update: Qp.q average of the k best rewards ∆ back-propagated through the node so far. It gives a stronger impact for the parts of the search space containing several local optima.

We introduced the max-update and top-k-mean-update policies as it may often happen that high-quality subgroups are rare and scattered in the search space. The mean value of rewards from simulations would converge towards 0 (there are too many low quality subgroups), whereas the maximum value (and top-k average) of rewards enables to identify the promising parts of the search space.

Search end and result output

Once the computational budget is reached, or when the tree is fully expanded, the search is stopped. The number of tree nodes equals the number of iterations that have been performed. It remains now to explore this tree and the data structure M built by the memory policy to output the list of diverse and non-redundant subgroups.

Let P " T Y M be a pool of patterns, where T is the set of patterns stored in the nodes of the tree. The set P is totally sorted w.r.t. ϕ in a list ι. Thus, we have to pick the k-best diverse and non-redundant subgroups within this huge pool of nodes ι to return the result set of subgroups R Ď P. For that, we develop a post-processing approach that filters out redundant subgroups from the diverse pool of patterns ι based on the similarity measure sim and the maximum similarity threshold Θ. Recursively, we poll (and remove) the best subgroup s ˚from ι, and we add s to R if it is not redundant with any subgroup in R. This post processing for removing redundancy is often used in the SD/EMM literature [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Meeng | Rocsearch -an roc-guided search strategy for subgroup discovery[END_REF]. It requires however that the pool of patterns has a reasonable cardinality which may be problematic with MCTS. The allowed budget always enables such post-processing in our experiments (up to one million iterations).

How to setup Mcts4Dm?

We first present datasets used for the evaluation of SD and EMM methods in the literature and we propose an artificial data generator that allows to generate datasets with a controlled insertion of interesting patterns. We then experiment with our approach and we report its effectiveness. The experiments were carried out on an Intel Core i7 CPU 2.2 Ghz machine with [START_REF] Belfodil | Mining convex polygon patterns with formal concept analysis[END_REF] Table 9: Benchmark datasets experimented on in the SD and EMM literature.

running under macOS Sierra. To ensure the reproducibility of our results, we made our code and data publicly available 7 . Our MCTS implementation for pattern mining, called mcts4dm is written in Java and is provided with a configuration file to choose any of the strategies introduced in this chapter.

Artificial data generator and benchmark datasets

The main goal of this work is to propose a heuristic approach that is able to output a diverse set of patterns. To evaluate our approach, a ground-truth is needed: All subgroups of a dataset shall be known beforehand such that heuristic search result could be then evaluated. Such a groundtruth is however available only if one is able to run and terminate an exhaustive search, which limits the type of data to be experimented with. Accordingly, we propose (i) to take into account benchmark data for which an exhaustive search is possible, and (ii) to generate artificial data in which interesting subgroups are hidden in noise and other frequent patterns (i.e., a ground-truth is known). In Section 4.5.3 we present a large real life dataset to assess the efficiency of mcts4dm when an exhaustive search is not tractable. Firstly, we gathered the benchmark datasets used in the recent literature of SD and EMM [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Downar | Exceptionally monotone models -the rank correlation model class for exceptional model mining[END_REF][START_REF] Van Leeuwen | Association discovery in two-view data[END_REF][START_REF] Van Leeuwen | Non-redundant subgroup discovery in large and complex data[END_REF][START_REF] Duivesteijn | Exploiting false discoveries -statistical validation of patterns and quality measures in subgroup discovery[END_REF]. Table 9 lists them, mainly taken from the UCI repository, and their properties. Secondly, we adapted the artificial data generator given in [START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF] in which the authors considered an EMM task where the target is a subgraph induced by a subgroup. We modify their generator to produce a dataset with nominal attributes and a binary target (positive and negative class labels).

More specifically, the generator takes the parameters given in Table 10 and works as follows. A numerical object/attribute data table is generated with an additional binary attribute: The target taking a positive or negative value. The number of objects, attributes and attributes values are controlled with the parameters nb_obj, nb_attr and domain_size. Our goal is to hide nb_patterns patterns in noise, so we generate random descriptions of random lengths Ground " td i | i P r1, nb_patternssu. For each pattern, we generate pattern_sup objects positively labeled with a probability of 1 ´noise_rate to be covered by the description d i , and noise_rate for not being covered. We also add pattern_sup ˆout_f actor negative examples for the pattern d i : It will allow patterns with different quality measures (here the WRAcc). Finally, we add random objects until we reach a maximum number of transactions nb_obj.

Experimental framework

We perform a large pool of experiments to assess this new exploration method for pattern mining. For that, we have designed an experimental framework that enables to test the different combinations of factors for all the strategies we introduced in previous sections. Each experiment are run on the nine benchmark datasets. An experiment consists in varying a unique strategy parameter while the others are fixed. Since mcts4dm uses random choices, each experiment is run five times and only the mean of the results is discussed.

The default parameters. For each benchmark dataset, we provide a set of default parameters. Indeed, due to the specific characteristics of each dataset, a common set of default parameters is unsuitable. Table 10 displays the default parameters for each dataset. However, all datasets share a subset of common parameters:

• The maximum size of the result set is set to maxOutput " 50.

• The maximum similarity threshold is set to Θ " 0.7.

• The maximum description length is set to maxLength " 5.

• The quality measure used is ϕ " W RAcc. Note that for each dataset, the experiments consist in finding subgroups deviating on the first target label.

• The SP-MCTS is used as the default UCB.

• The permutation unification (PU) strategy is used by default.

• The refinement operator for the Expand method is set to tuned-min-gen-expand.

• The direct-freq-roll-out strategy is used for the RollOut method

• The reward aggregation policy is set to max-reward.

• The memory policy is set to top-1-memory.

• The update policy is set to max-udpate.

The list of experiments.

Evaluating mcts4dm is performed by means of seven different batches of experiments:

• Section 4.4.3 is about the choice of UCB.

• Section 4.4.4 deals with the several strategies for Expand .

• Section 4.4.5 presents the leverage of all the possibilities for RollOut.

• Section 4.4.6 shows out the impact of the Memory strategy.

• Section 4.4.7 compares the behaviors of all the strategies for Update.

• Section 4.4.8 performs the experiments when varying the computational budget, namely the number of iterations.

• Section 4.4.9 experiments with the completeness of mcts4dm on artificial data when varying the number of iterations.

For simplicity and convenience, for each experiment we display the same batch of figures. For each dataset we show (i) the boxplots of the quality measure ϕ of the subgroups in the result set, (ii) the histograms of the runtime and (iii) the boxplots of the description length of the subgroups in the result set depending on the strategies that are used. In this way, the impacts of the strategies are easy to understand.

The Select method

The choice of the UCB is decisive, because it handles the exploration / exploitation trade-off. Indeed, the UCB chooses which part of the search tree will be expanded and explored. We presented four existing UCBs and we introduced a new one based on the normalized exploration rate to take into account a partial order on the subgroups. Experimenting with these different UCBs has to be done when selecting the exploration method. In fact, we showed that there exists different nodes within the search tree that are exactly the same ones (the search space is explored as a tree but it is a lattice). Handling such a redundancy can be done with either permutation unification (PU) or using a lectic order (LO). Thus, Figure 14(bottom) presents all the strategies we experimented. Comparing the runtime for all the strategies leads to conclude that there is no impact when computing the several UCBs (see Figure 14(a)). Indeed, the impact of the UCBs lies in its computation. However, we can notice that when LO is used, the runtime is lower. This result is expected because with LO, the search space is less large since there is no redundant subgroups. Figure 14(b) depicts the boxplots of the quality measure of the result set when varying the UCB. The results suggest that the UCB1-Tuned and DFS-UCT lead to weaker quality results for several datasets: On the Cal550, Emotions and Yeast datasets, the quality measures of the result sets are worse than the results of other UCBs (see, e.g., Figure 14(b)). This is due to the fact that the search space of these datasets is larger than the others with many local optima, and the UCB1-Tuned is designed to explore less, thus less local optima are found. Besides, the SP-MCTS seems to be more suitable for SD problems: The quality is slightly better than other UCBs for the BreastCancer and Emotions datasets. LO leads to a worse quality in the result set, whereas PU seems to be more efficient. The use of these different UCBs has no impact on the description length of the subgroups within the result set. For some datasets, the permutation unification leads to longer descriptions (see for instance Figure 14(c)).

The Expand method

Considering the Expand method, we introduced three different refinement operators, namely direct-expand, gen-expand and label-expand, and we presented two methods, namely LO and PU, to take into account that several nodes in the search tree are exactly the same. The several strategies are given in Figure 15(bottom). Let us consider the leverage on the runtime of these strategies in Figure 15(a). Once again, using LO implies a decrease of the runtime. Conversely, PU requires more time to run. There is very little difference in the runtime when varying the refinement operator: direct-expand is the faster one, and label-expand is more time consuming.

Considering the quality of the result set varying the expand strategies, we can assume that the impact differs w.r.t. the dataset (see Figure 15(b)). Surprisingly, LO improves the quality of the result set for some datasets (e.g., the Iris dataset in Figure 15(b)). This contradicts what we observe in the Emotions dataset in Section 4.4.3. More generally, the results using label-expand are better than other ones in most of the datasets.

The description length of the extracted subgroups are quite constant when varying the Expand strategies (see Figure 15(c)). With LO, the description lengths are slightly smaller than with other strategies.

The RollOut method

For the RollOut step, we derived several strategies that combine the path policy and the reward aggregation policy in Table 12. Clearly, the experiments show that the runs using the direct re- finement operator (naive-roll-out and direct-freq-roll-out) are time consuming (see Figure 16(a)).

In the BreastCancer data, the runtime is twice longer with the direct refinement operator than with the large-freq-roll-out path policy. In other datasets (e.g., Ionosphere or Yeast), the runtime is even more than 3 minutes (if the run lasts more than 3 minutes to perform the number of iterations, the run is ignored). Besides, it is clear that the random-reward aggregation policy is less time consuming than other strategies. Indeed, with random-reward, the measure of only one subgroup within the path is computed, thus it is faster. Figure 16(b) is about the quality of the result set.

The naive-roll-out and direct-freq-roll-out path policies lead to the worst results. Besides, the quality of the result set decreases with the random-reward reward aggregation policy in other datasets (e.g., Emotions). Basically, these strategies evaluate only random nodes and thus they are not able to identify the promising parts of the search space. Finally, there are not large differences between other strategies.

As it can be seen in Figure 16(c), the description length of the subgroups is not really impacted by the strategies of the RollOut method. The results of the random-reward reward aggregation policy are still different from other strategies: The description length is smaller for the Mushroom dataset. Using large-freq-roll-out with jumpLength " 100 leads to smaller descriptions for the Mushroom dataset. Finally, the description length is however not really influenced by the Roll-Out strategies.

The Memory method

We derived six strategies for the Memory step given in Figure 17(bottom). Obviously, the all-memory policy is slower than other strategies because all the nodes within the path of the simulation have to be stored (see Figure 17(a)). Conversely, the no-memory policy is the fastest strategy. The runtimes of the top-k-memory policies are almost the same.

Figure 17(b) shows that the quality of the result set is impacted by the choice of the memory policies. We can observe that the no-memory is clearly worse than other strategies. Indeed, in the Emotion dataset, the best subgroups are located deeper in the search space, thus, if the solutions encountered during the simulation are not stored it is difficult to find them just be considering direct-freq-roll-out top-5-mean-reward [START_REF] Agrawal | Mining sequential patterns[END_REF] direct-freq-roll-out top-10-mean-reward [START_REF] Andrews | A partial-closure canonicity test to increase the efficiency of cbo-type algorithms[END_REF] direct-freq-roll-out random-reward [START_REF] Andrews | A 'best-of-breed' approach for designing a fast algorithm for computing fixpoints of galois connections[END_REF] large-freq-roll-out (jumpLength " 10q max-reward [START_REF] Arctander | Perfume and flavor materials of natural origin[END_REF] large-freq-roll-out (jumpLength " 10q mean-reward [START_REF] Atzmueller | VIKAMINE -open-source subgroup discovery, pattern mining, and analytics[END_REF] large-freq-roll-out (jumpLength " 10q top-2-mean-reward [START_REF] Atzmüller | Fast subgroup discovery for continuous target concepts[END_REF] large-freq-roll-out (jumpLength " 10q top-5-mean-reward [START_REF] Atzmüller | SD-map -A fast algorithm for exhaustive subgroup discovery[END_REF] large-freq-roll-out (jumpLength " 10q top-10-mean-reward [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] large-freq-roll-out (jumpLength " 10q random-reward [START_REF] Bäck | Handbook of evolutionary computation[END_REF] large-freq-roll-out (jumpLength " 20q max-reward [START_REF] Bay | Detecting group differences: Mining contrast sets[END_REF] large-freq-roll-out (jumpLength " 20q mean-reward [START_REF] Belfodil | Mining convex polygon patterns with formal concept analysis[END_REF] large-freq-roll-out (jumpLength " 20q top-2-mean-reward [START_REF] Bendimerad | Unsupervised exceptional attributed subgraph mining in urban data[END_REF] large-freq-roll-out (jumpLength " 20q top-5-mean-reward [START_REF] Berkhin | A survey of clustering data mining techniques[END_REF] large-freq-roll-out (jumpLength " 20q top-10-mean-reward [START_REF] Berlanga | Multiobjective evolutionary induction of subgroup discovery fuzzy rules: A case study in marketing[END_REF] large-freq-roll-out (jumpLength " 20q random-reward [START_REF] Berlingerio | Mining graph evolution rules[END_REF] large-freq-roll-out (jumpLength " 50q max-reward [START_REF] Besson | Constraint-based concept mining and its application to microarray data analysis[END_REF] large-freq-roll-out (jumpLength " 50q mean-reward [START_REF] Björnsson | Cadiaplayer: A simulation-based general game player[END_REF] large-freq-roll-out (jumpLength " 50q top-2-mean-reward [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] large-freq-roll-out (jumpLength " 50q top-5-mean-reward [START_REF] Bosc | Découverte de sous-groupes avec les arbres de recherche de monte carlo[END_REF] large-freq-roll-out (jumpLength " 50q top-10-mean-reward [START_REF] Bosc | Local subgroup discovery for eliciting and understanding new structure-odor relationships[END_REF] large-freq-roll-out (jumpLength " 50q random-reward [START_REF] Bosc | Vers la découverte de modèles exceptionnels locaux : des règles descriptives liant les molécules à leurs odeurs[END_REF] large-freq-roll-out (jumpLength " 100q max-reward [START_REF] Bosc | Fouille de motifs séquentiels pour l'élicitation de stratégies à partir de traces d'interactions entre agents en compétition[END_REF] large-freq-roll-out (jumpLength " 100q mean-reward [START_REF] Bosc | Mining balanced sequential patterns in RTS games[END_REF] large-freq-roll-out (jumpLength " 100q top-2-mean-reward [START_REF] Bosc | h(odor): Interactive discovery of hypotheses on the structure-odor relationship in neuroscience[END_REF] large-freq-roll-out (jumpLength " 100q top-5-mean-reward [START_REF] Bosc | Any-time diverse subgroup discovery with monte carlo tree search[END_REF] large-freq-roll-out (jumpLength " 100q top-10-mean-reward [START_REF] Bosc | A pattern mining approach to study strategy balance in RTS games[END_REF] large-freq-roll-out (jumpLength " 100q random-reward

Table 12: The list of strategies used to experiment with the RollOut method. the subgroups that are expanded in the search tree. Surprisingly, the all-memory policy does not lead to better results. In fact the path generated during a simulation contains a lot of redundant subgroups: Storing all these nodes is not required to improve the quality of the result set. Only few subgroups within the path are related to different local optima.

As expected in Figure 17(c), the descriptions of the subgroups obtained with the no-memory policy are smaller than those of other strategies. Indeed, with the no-memory policy, the result sets contains only subgroups that are expanded in the search tree, in other words, the subgroups obtained thanks to the Expand method.

The Update method

Figure 18(bottom) presents the different strategies we use to implement the Update method. The goal of this step is to back-propagate the reward obtained by the simulation to the parent nodes. The runtime of these strategies are comparable (see Figure 18(a)). However, we notice that the top-k-mean-update policy is a little more time consuming. Indeed, we have to maintain a list for each node within the built tree that stores the top-k best rewards obtained so far. Figure 18(b) shows the quality of the result set when varying the Update policies. For most of datasets, since the proportion of local optima is very low within the search space, the maxupdate is more efficient than the mean-update. Indeed, using the max-update enables to keep in mind that there is an interesting pattern that is reachable from a node. However, Figure 18(b) presents the opposite phenomena: The mean-update policy leads to better result. In fact, there are a lot of local optima in the Ionosphere dataset, thus the mean-update is designed to find the areas with lots of interesting solutions. Moreover, using the top-k-mean-update leads to the mean-update when k increases.

The description length of the subgroups in the result set are comparable when varying the policies of the Update method (see Figure 18(c)). Indeed, the aim of the Update step is just to back-propagate the reward obtained during the simulation to the nodes of the built tree to guide the exploration for the following iterations. This does not have a significant influence on the length of the description of the subgroups.

The number of iterations

We study the impact of different computational budgets allocated to mcts4dm, that is, the maximum number of iterations the algorithm can perform. As depicted in Figure 19(a), the runtime is linear with the number of iterations. Note that the x-axis is not linear w.r.t. the number of iterations, please refer to the bottom of Figure 19 to know the different values of the number of iterations.

Moreover, as expected, the more iterations, the better the quality of the result set. Figure 19(b) shows that a larger computational budget leads to a better quality of the result set, but, obviously, it requires more time. Thus, with this instant mining exploration method, the user can have some results anytime. Note that for the BreastCancer dataset, the quality decreases from 10 to 100 iterations: This is due to the fact that with 10 iterations there are less subgroups extracted (12 subgroups) than with 100 iterations (40 subgroups), and the mean quality of the result set with 100 iterations contains also subgroups with lower quality measures.

When the number of iterations increases, it leads to a result set containing subgroups with longer description lengths. Figure 19(c) depicts this behavior: The more the iterations, the longer the description length. Indeed, usually, the better the subgroups, the longer the description length. Note that in all the experiments, we limit the description length to at most 5 restrictions to remain interpretable. It is a popular constraint in SD.

The completeness of the result set

In this section we are interested in assessing the completeness of the result set of mcts4dm. For that, we experiment with artificial data to get the ground truth, i.e., to know the percentage of local optima (hidden in the data) the algorithm is able to extract. We use the default parameter for mcts4dm, and we select the gen-expand with the top-10 memory policy. These parameters have been chosen empirically given the results obtained from benchmark datasets in the previous experiments. We set by default a very low minimal support of 10, that is 0.02%. The ability to retrieve patterns is measured with: Definition 21 (Evaluation measure). Let H be the set of hidden patterns, and F the set of patterns found by an MCTS mining algorithm, the quality of the found collection is given by: qualpH, Fq " avg @hPH pmax @f PF pJaccardpsuppphq, supppf qqqq that is, the average of the quality of each hidden pattern, which is the best Jaccard coefficient with a found pattern. We thus measure the completeness. This measure is pessimistic in the sense that it takes its maximum value 1 if and only if all patterns are completely retrieved.

The results of our experiments are given in Figure 20. The impact of the noise is the following: It directly reduces the support of a hidden pattern and thus it requires low minimal supports to find the hidden patterns with success. With minSupp " 50 and no noise, pattern are discovered, however, with noise, the support of a pattern is lower that 50 and thus cannot be found. With minSupp " 10, the search is more tolerant to noise. Note on the Figures 20(a)-(b) that when two lines exactly overlaps, it means that the search space of frequent patterns was fully explored (the tree is fully extended in these cases). To ensure experiment feasibility, we had to reduce the number of hidden objects in the dataset.

With out_f actor " 1, each pattern appears equally often. Varying this parameter allows to hide patterns with different W Racc measures. With 10K iterations, most of the patterns are retrieved, with 100K iterations all of them are found.

Varying the number of hidden pattern highlights the same results: The UCB allows to drive the search towards interesting parts (exploitation) but also rarely visited parts (exploration) of the search space. Hiding more patterns and retrieving all of them may require more iterations in the general case.

Patterns with a high relative support shall be easier to be retrieved as a simulation has more chance to discover them, even partially. We observe that patterns with small support can be retrieved in Figure 20(e) as the minimal support is set to 10 and the support of patterns is higher than 20. No pattern can be found if the minSupp is higher than the support of the hidden patterns.

The number of objects directly influences the computation of the support of each node: Each node stores a projected database that lists which objects belong to the current pattern. The memory required for our MCTS implementation let show a linear complexity w.r.t. the number of iterations. This practical complexity can be higher depending on the chosen memory policy (e.g., in these experiments, the top-10 memory policy was chosen). The time needed to compute the support of a pattern is higher for larger datasets, but it does not change the number of iterations required to find a good result. The memory usage is discussed in Section 4.5.

The number of attributes and the size of attribute domains directly determine the branching factor of the exploration tree. It takes thus more iterations to fully expand a node and to discover all local optima. Here again, all patterns are well discovered but larger datasets require more iterations (figures not shown but similar).

Comparison with existing methods

Let us consider the following existing implementations: SD-MAP*, the most efficient exhaustive search algorithm available to date [START_REF] Atzmüller | SD-map -A fast algorithm for exhaustive subgroup discovery[END_REF] and its implementation in Vikamine [START_REF] Atzmueller | VIKAMINE -open-source subgroup discovery, pattern mining, and analytics[END_REF] ; and CORTANA8 which incorporates different versions of beam-search (standard one, ROC-search, cover-based search [START_REF] Meeng | Rocsearch -an roc-guided search strategy for subgroup discovery[END_REF]). We did not compared to the beam search of DSSD [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF], as a similar implementation is available in Cortana. We also did not compare to genetic algorithms and sampling method yet as we were unable to get the implementations from the authors 9 .

In what follows, we compare these implementations with mcts4dm given a choice of policies and a maximal budget in terms of iterations for (i) finding all hidden patterns in artificial data;

Studying extraction completeness in artificial data

We compare mcts4dm and the default beam-search for their ability to retrieve hidden patterns in artificial data. Note that it is not necessary to compare with SD-MAP* since it is a exhaustive search: The completeness of the result set is maximal. For that matter, we reuse our artificial data generator with the following default parameters: noise_rate " 0.2, out_f actor " 0.15, nb_patterns " 25 pattern_sup " 100, nb_obj " 50000, nb_attr " 25, domain_size " 1000. Again, we measure the quality of an extraction with Definition 21. Results are reported in Figure 21 when varying the out_f actor, the number and the support of hidden patterns. It follows that mcts4dm requires less than 5, 000 iterations to fully retrieve all patterns. Surprisingly, 100 iterations are enough to have similar results with those of beam-search. This is due to the fact that we generated datasets with a large number of attributes and domain sizes (the branching factor): The greedy choices of beam search fail at exploring well the search space. We obtained similar results with the other beam search strategies.

Finding the best pattern in benchmark datasets.

This experiment aims at comparing the best solution found with mcts4dm after a given number of iterations, with the several versions of beam search. We also want to compare with SD-Map.

As SD-Map performs an exhaustive search, it finds the best solution. Table 13(top) summarizes the results (note that the result of mcts4dm are summed up from experiment reports introduced in the previous section).

For SD-Map, we use the following parameters: The WRAcc measure is used; the description length is fixed to 5; the minimum support is fixed in the same way than presented in Table 11 and the maximum size of the result set is 50. Results are given in Table 13(bottom). Surprisingly, the results extracted by SD-Map are not optimal for some datasets. Indeed, SD-Map uses a discretization method to handle numerical attributes. Thus for numerical dataset, the result set obtained with SD-Map may be not optimal and the runtime is biased since it is not exhaustive. On the BreastCancer dataset, mcts4dm extracts a subgroup with a quality measure of 0.21 in 0.185 seconds, whereas the best quality measure with SD-Map is 0.184 and it took 0.7 seconds to find it. Besides, for the TicTacToe dataset, both approaches are able to extract the same best solution, but mcts4dm is faster than SD-Map (0.173s vs 0.85s). However, for some datasets, e.g.Cal500, SD-Map is more efficient than mcts4dm: It finds the best subgroup with a quality measure of 0.029 in 1.05 seconds whereas mcts4dm does not extract it even after 100k iterations in 12.082 seconds (the best solution found so far is 0.027).

To compare with beam-search implementations, CORTANA can be configured with several parameters, such as the the quality measure, the time budget or the minimum support threshold. CORTANA embeds several beam search strategies: The traditional beam search, the ROC-Search [START_REF] Meeng | Rocsearch -an roc-guided search strategy for subgroup discovery[END_REF] and the cover-based beam search (it used the similarity of the supports to choose the subgroups to add into the next beam). We use the following parameters:

• WRAcc measure is used.

• The refinement depth is fixed to 5. Note that the refinement depth is not exactly the description length. Indeed, the refinement depth of rAttribute 1 ă 5s ^rAttribute 1 ă 4s is 2 but its description length is 1.

• The minimum support is fixed in the same way than presented in Table 11.

• The maximum size of the result set is 50.

• The time budget is set to 3 minutes.

• The numeric strategy is set to best.

• 1 thread is used since mcts4dm is not a parallelized implementation yet.

Table 13(middle) gathers the results: The quality of the best subgroup is the same for most of the datasets, but the runtime to find them is much faster with mcts4dm than with the strategies implemented in CORTANA. For few datasets, mcts4dm has a lower quality measure because it needs more iterations to find these best solutions. On the Yeast dataset, none of these three strategies are able to find a solution without exceeding the time budget of 3 minutes, mcts4dm does in less than 1 minute. mcts4dm extracts the best solution with few iterations for many Table 13: The runtime and the maximum of the quality measure with SD-Map.

datasets. When the local optima are deep in the search space, it needs more iterations to find them. The result set of the beam search strategies contains only few local optima among a lot of redundant patterns, whereas mcts4dm extracts more local optima (but still a lot of redundant patterns stored in the tree). This is illustrated in Figure 22: After applying the redundancy post-processing (that is, removing patterns that are too similar to other ones), it remains only one pattern with beam search in BreastCancer and Iris while mcts4dm returns between 15 and 20 patterns. MCTS may require a lot of iterations to find the best pattern (that maximize ϕ) and thus it needs for consequent memory to store the search tree (this is however nowadays a subdued problem as memory gets cheaper and cheaper). Due to its greedy nature, beam search may skip good solutions. When an exhaustive search is not able to complete quickly (see Section 4.5.3, since benchmark datasets are not too large), mcts4dm outputs a result anytime that improves with time.

Studying the efficiency of mcts4dm on a large dataset

Using MCTS for pattern mining is even more efficient when dealing with a real life application. Basically, the real life datasets are more complex and larger than benchmark datasets. We experimented with the olfaction dataset to understand the structure-odors relationships. This dataset contains 1,689 molecules described by 82 physico-chemical properties (e.g., the molecular weight,

Quality

Strategies

Strategies #iterations:

(1)10 ( 2)50 (3)100 ( 4)500 ( 5)1K ( 6)5K ( 7)10K ( 8)50K ( 9)100K the number of carbon atoms, etc.) and associated to odors (e.g., strawberry, woody, etc.). Our goal is to extract subgroups that are characteristic of an odor or a subset of odors. In this experiment, we are only interested in the Musk odor, and we use the F1-score.

Comparison with the SD-Map algorithm. In the previous batch of experiments, all the dataset have been handled by the exhaustive algorithm SD-Map. Basically, the benchmark datasets are quite small, and the necessity of using heuristic searches is not perceptible. However, note that SD-Map uses a discretization method to handle numerical attributes that distorts the results: The run are faster but the result is not optimal. Experimenting SD-Map on the olfaction dataset is not feasible in less than 3 minutes. The run lasts 477.8 seconds and it leads to the best quality measure of F1-Score " 0.45. Conversely, with mcts4dm, we are able to process up to 1 million of iterations in 99, 7 seconds (average over 5 runs) with the best quality measure found is F1-Score " 0.47. Figures 23 presents the results obtained with mcts4dm on the olfaction dataset when varying the number of iterations.

Conclusion

Heuristic search of supervised patterns becomes mandatory with large datasets. However, classical heuristics lead to a weak completeness in the result set: Only few local optima are found. We advocate for the use of MCTS for pattern mining: An aheuristic exploration strategy leading to "any-time" pattern mining that can be adapted with different measures and policies. The experiments show that MCTS provides a much better diversity in the result set than existing heuristic approaches. Interesting subgroups are found thanks to a reasonable amount of iterations and the quality of the result iteratively improves. MCTS is a powerful exploration strategy that can be applied to several, if not all, pattern mining problems that need to optimize a quality measure given a subset of objects.

In this chapter, we apply mcts4dm with the W RAcc measure. However, when facing the SOR problem, it is required to employ a more complex model to capture the interestingness of subgroups. For that, in the next chapter, we are interested in finding subgroups that are relevant for a subset of class labels, called target subspaces. It leads to an increase of the branching factor in the search space. We study how mcts4dm can compute, in this setting, a diverse set of patterns that is also diverse w.r.t. the target subspaces.

Chapter 5

Exceptional Model Mining in multi-label data

Introduction

We are now interested in multi-label data where an object can take several class labels. For that matter, SD has been extended to a richer framework that handles more complicated target concepts, the so-called exceptional model mining approach (EMM) [START_REF] Leman | Exceptional model mining[END_REF]. The idea is the following: A model is built over the labels from the objects in the subgroup and it is compared to the model of the whole dataset by means of a quality measure (Figure 3). The more different the model, the more exceptional and interesting is the subgroup. For example, van Leeuwen and Knobbe compare the label distribution with the Weighted Kullback Leibler divergence (WKL) [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF] and Duivesteijn et al. compare conditional dependency relations between the targets with Bayesian networks [START_REF] Duivesteijn | Subgroup discovery meets bayesian networks -an exceptional model mining approach[END_REF]. There exists many other types of models (e.g., regression, classification, target association) and associated quality measures (see [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF]). The proposed EMM instances for multi-label data consider either the whole set of labels (e.g., compared with the WKL) or each label independently (e.g., SD with the WRAcc), or finally a unique and fixed label subset chosen a priori (e.g. SD with the WRAcc for a label subset only). However, in presence of multi-label data, there are many applications for which one is interested in subgroups that differ from the whole dataset only on subsets of labels, though the interesting subsets of labels are not known beforehand. Typically, descriptive rules that conclude on small label sets provide such sets. As an example, in our case study on SOR, we are interested in rules between physico-chemical properties of odorant molecules (e.g. molecular weight, atom count), the attributes, and perceived smells given by Humans (e.g., fruity, apple, wood) which are the labels. There is a crucial need to discover such rules for a better understanding of the olfactory percept. According to a recent study, some odors can be predicted [START_REF] Keller | Predicting human olfactory perception from chemical features of odor molecules[END_REF], but there is a few knowledge that would explain why a molecule smells an odor or another. On average, each odorant molecule is depicted by 2.33 labels among the set of the 74 possible labels. Assessing a subgroup with regard to either the whole set of labels or each label independently cannot allow to characterize rules involving a subset of labels. For example, Figure 24 shows the label distribution of the best subgroup according to the WKL in our olfaction dataset: It fails at characterizing a small set of labels.

The only solution for applying SD/EMM to successfully extract subgroups characterized by multi-labels is to transform the data. Indeed, when facing a multi-label dataset, either for a supervised or an unsupervised task, the most popular approaches apply standard techniques after a data transformation: Binary Relevance (BR) creates a dataset for each different label (objects are kept, target becomes binary) while Label Powerset (LP) creates a dataset for each set of labels that exists in the data set [START_REF] Tsoumakas | Mining multi-label data[END_REF]. In our settings, BR looses label dependencies (e.g., fruity and apple), but applying LP before classical SD/EMM is totally relevant. It requires however to consider as many datasets as label subsets in the data, that is 1, 800 combinations in our olfaction dataset which could be restricted to 400 deemed as interesting by the neuroscientists who created the dataset. This comes with an explosion of computational needs and an explosion of the number of rules returned to the expert. As explained hereafter, SD/EMM is nowadays shifting towards the heuristic search of a diverse set of subgroups that is large enough to cover interesting label sets, and small enough to be interpreted by an expert. As such, we properly formalize a novel EMM instance to fully take into account multi-label data and all label subsets called target subspaces (Figure 4). It leads to a more complex search space.

It has been now widely admitted that an exhaustive search is impossible in general, even with efficient pruning techniques [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF]: The subgroup search space is large and it is difficult to use the properties of the measures to prune the search space. Accordingly, heuristic approaches are used, mainly based on beam searches [START_REF] Lowerre | The HARPY speech recognition system[END_REF]. It as been studied as the diverse subgroup set discovery problem [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF]: The extracted collection of k subgroups shall be of high quality and the less redundant as possible. Indeed, it often happens -if not always-that the best patterns differ slightly on the objects they cover (or their description in a dual way). The redundancy makes that very few local optima are discovered and the subgroup set is not diversified. A solution is to control each level of the beam search, which can be seen as a set of parallel hill-climbing searches [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF]: The subgroup search space is explored level-wise and each level is restricted to a set of diversified high quality patterns. The diversification is done as follows. Subgroups are sorted according to their quality: The best one is picked and all the next patterns that are too similar (according to similarity of their covers and a threshold) are removed. The first of the next patterns that is not similar is kept, and the process is iterated.

Besides, the problem of completeness of the result set with heuristic approaches has been studied in the previous chapter. The problem we tackle in this chapter concerns the diversity on the target space. This has not been studied yet to the best of our knowledge. Recall that we propose to enhance EMM by considering all target subspaces: It may happen that a subspace contains many subgroups of high quality and diversified in that subspace (the subgroups are very different). Therefore, we need to exploit promising subspaces while still exploring the others to cover many label combinations: This is what we call the diversity in the target space. To ensure the possibility of such a diversity, the search space of subgroups should include the label sets. We show that ensuring the possibility of this diversity forces to reconsider the subgroup search space: Bisets psubgroup, label_setq are explored and should be wisely expanded during the search. We experiment this with the standard beam-search, but also with our pattern sampling technique based on Monte Carlo Tree Search presented in the previous chapter.

Finally, as our goal is to find rules where the consequent is a label set, we also need to reconsider the subgroup quality measure. Generally, one is interested in rules with a high support and a few errors (maximizing the precision). The WRAcc is perfect for that as it expresses the difference between the precision of the subgroup w.r.t. the objects in the rest of the dataset, and it is weighted with the subgroup support. However, in many applications, the label distribution is highly skewed. This is the case of our application in olfaction as it can be observed on Figure 25: Some label subsets are over-represented, others are under-represented. The neuroscientists are also interested in subgroups that involve such under-represented label subsets. Another solution would be to consider both the precision and recall, thus the F 1 measure. However again, this would favor small groups for which it is easier to find descriptions that cover well the label subset. In the best settings, one would favor precision for highly represented label subsets, and both precision and recall for under-represented subsets. We thus propose the F β measure adapted for highly skewed label distributions. Actually, the F β measure generalizes the F 1 measure in a way that β expresses a trade-off between the precision and the recall: We dynamically adjust it during the search, given the target subspace (label subset) that is currently enumerated. This directly impacts a better target diversity in the result set.

• We properly formalize a novel EMM instance to fully take into account multi-label data and all target subspaces.

• This comes with a more complex search space and it enforces new constraints for tractable heuristic searches: We show how to adapt the subgroup search space so that heuristic search, including MCTS on, can be applied efficiently.

• We introduce several pattern quality measures that are able to take into account the skewness of the label distribution and we dynamically consider the label distributions during the search to favor diversity on targets.

• We experiment with these approaches on several benchmark multi-label datasets (the experiments on the olfaction dataset are detailed in the next chapter). Our main result shows that MCTS with a relative F β measure gives the best results in terms of computation time, quality and diversity, both on the description and the target spaces.

The rest of this chapter is organized as follows. The next section recalls some basics of SD/EMM. Section 5.3 formalizes EMM with different target spaces for multi-label rule discovery. Section 5.4 introduces the subgroup search space and the several quality measures that favor target diversity. Section 5.5 develops the different algorithms. Section 5.6 presents our experiments assessing the validity of our approach before a brief conclusion in Section 5.7.

Exceptional model mining and diverse subgroup set discovery

We override the definition of the label dataset with the Definition 7 as follows:

Definition 7 (Multi-label dataset). Let O, A and C be respectively a set of objects, a set of attributes (either nominal or numerical), and a set of class labels. Each object is associated to a subset of class labels among C by the function class : O Þ Ñ 2 C that maps the target labels to each object. We denote a multi-label dataset as DpO, A, C, classq.

In the EMM framework, with a multi-label dataset, the definition of a subgroup remains unchanged. We recall this definition: Definition 6 (Subgroup). The description of a subgroup is given by d " xf 1 , . . . , f |A| y where each f i is a restriction on the value domain of the attribute a i P A. The description of a subgroup corresponds to the pattern in the pattern mining setting. A restriction is either a subset of a nominal attribute domain, or an interval contained in the domain of a numerical attribute. The description d covers a set of objects called the extent of the subgroup, denoted extpdq Ď O, and its support is the number of objects in its extent and is defined by supppdq " |extpdq|. Note that, in this thesis, we denote |S| the cardinality of the set S. For simplicity, a subgroup is either given by its intent, i.e., its description d, or by its extent extpdq.

The aim of EMM is to find subgroups whose model over the class labels is significantly different from the model induced by the entire set of objects O. Several models have been proposed in the state of the art (see Chapter 2 for more details) [START_REF] Duivesteijn | Exceptional model mining -supervised descriptive local pattern mining with complex target concepts[END_REF]. Quality measures have been introduced to compare the similarity between the two models (i.e., those of the subgroup and those of the entire dataset), the better the quality measure, the less the similarity, the more interesting the subgroup [START_REF] Lavrac | Rule evaluation measures: A unifying view[END_REF][START_REF] Abudawood | Evaluation measures for multi-class subgroup discovery[END_REF].

Since the search space of subgroups is too large, it is now widely accepted that an exhaustive search of subgroups, even with efficient pruning techniques, is not tractable for EMM. Heuristic methods are employed, such as beam search. However, it comes with the issue of redundancy of the subgroup set that is extracted. The question is: How to ensure a high diversity in the result set of a heuristic exploration of the search space. This point has been studied as the Diverse Subgroup Set Discovery [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF]. The aim is to extract a diverse subgroup set that is as small as possible to be easily interpretable by the experts. For that, a similarity measure (e.g., Jaccard coefficient between the extent of two subgroups) is used to avoid the extraction of redundant subgroups within the result set. Thus, the problem definition of EMM given Problem 3 is extended with the problem of diverse subgroup set discovery as follows:

Problem 6 (Diverse Subgroup Set Discovery [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF]). Given a multi-label dataset DpO, A, C, classq, a quality measure ϕ , a minimum support threshold minSupp, an integer k, a similarity measure sim, and a maximum similarity threshold Θ, DSSD aims at extracting the diverse set of top-k best frequent subgroups w.r.t. the quality measure ϕ in which there is no similar subgroups, i.e., for all subgroups s 1 , s 2 in the result set, simps 1 , s 2 q ď Θ.

Subgroup set discovery with diversity on target subspaces

By definition, within the EMM framework, the model induced by the subgroup (and those induced by the entire set of objects) is always built over all the class labels. Thus, each subset of objects (or subgroup) derives a unique model. However, a subgroup can be deemed interesting only for the model induced over a subset of class labels because it derives a model completely different from those of the entire set of objects just for this subset of class labels. However, this subset of class labels is unknown a priori. Thus, it is required to explore the label set space, called the target subspaces. This is one of our contribution: We design a new EMM instance to strive subgroups whose model induced over an unknown subset of class labels L Ď C is different from the model induced by the entire dataset over the same subset of class labels L. The process of this new EMM instance is given in Figure 4. The change relies on the construction of the model. There is no longer one but several models derived from the subgroup: One for each target subspace. We need to refine Definition 6 about subgroups for this new EMM instance. Definition 22 (Subgroup in a target subspace). Given a multi label dataset DpO, A, C, classq, a subgroup, denoted s " pd, Lq, is given by its description d and the subset of class labels L Ď C over which the model is built.

We will use the term subgroup in the rest of this chapter though, as it will be always implied that a subgroup is considered in a target subspace. Following the studies in Diverse Subgroup Set Discovery, this new EMM instance that deals with multi-label data should also exhibit a great diversity in the target subspace. Although it may happen that a subspace contains many subgroups of high quality and diversified in that subspace (the subgroups are very different), we need to exploit promising target subspaces while still exploring the others to cover many label combinations: This is what we call the diversity in the target space.

Problem 7 (DSSD with diveristy on target subspaces). Given a multi-label dataset DpO, A, C, classq, a quality measure ϕ, a minimum support threshold minSupp, an integer k, and a similarity measure sim, DSSD aims at extracting the diverse set of top-k best frequent subgroups w.r.t. the quality measure ϕ in which there is no similar subgroups w.r.t. sim and that covers as many target subspaces as possible.

We will still refer to this problem as DSSD, as it implies in the rest of this chapter that diversity is considered both on the description and target subspace.

Quality measures considering the target subspaces

Evaluating a subgroup s " pd, Lq is performed thanks to a quality measure ϕ that computes the difference between the model induced by extpdq over the target subspace L and those induced by O over L. Surveys help understanding how to choose the right measure [START_REF] Fürnkranz | Foundations of Rule Learning[END_REF]. One of the most widely used quality measure for multi-label data is the Weighted Kullback Leibler divergence (WKL) [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF]. The WKL of a subgroup s " pd, Lq is given by:

WKLpd, Lq " supppdq |O| ÿ lPL pp l d log 2 p l d p l 0 q
This measure aims at assessing the deviation between two distributions, i.e., it does not consider only the presence of a label, but it also takes into account the under-representation of a label for a subgroup. Moreover, WKL assumes that the labels are independent: It does not consider the co-occurrences of the labels. This is a strong assumption that is not satisfied in most of the data. Besides, note that WKL is maximized with L " C since it is the sum over the labels in L of positive terms. Thus, WKL can not be used in the settings of Problem 7. Let us now study different measures that can be used for Problem 7.

W RAcc to evaluate the subgroups

The Weighted Relative Accuracy (WRAcc) is a well-known quality measure in EMM. Indeed, it allows to compare the proportion of a subset of labels in a subgroup with the proportion of this subset of labels in the entire dataset. For a subgroup s " pd, Lq, it is given by:

WRAccpd, Lq " supppdq |O| ˆ`p L d ´pL 0 where p L d " |toPextpdq|classpoqĎLu| supppdq (resp. p L 0 " |toPO|classpoqĎLu| |O|
) is the proportion of objects in the subgroup s (resp. in the entire dataset) that are associated to all the labels in L. In other words, WRAcc is the difference between the precision of the rule d Ñ L and those of rule xy Ñ L: The model of a subgroup s is given by the precision of the subset of labels L in extpsq. This difference is weighted by the relative size of the subgroup to avoid the extraction of small subgroups. Note that, we can also consider the Relative Accuracy measure (RAcc) that does not weight the difference:

RAccpd, Lq " p L d ´pL 0
However, in our case study, we are interested in both the precision and the recall of the subgroup. WRAcc or RAcc only foster on the precision of a given subgroup. We can notice that the weighted factor allows to take into account partially the recall by fostering on larger subgroups.

F 1 score to take into account both precision and recall

Given a subgroup s " pd, Lq, the precision is defined by: P pd, Lq " |extpdq X extpLq| supppdq and the recall is given by:

Rpd, Lq " |extpdq X extpLq| supppLq

The F 1 score considers both the precision and the recall of a subgroup s " pd, Lq. The Relative F 1 (RF 1 ) is given by: RF 1 pd, Lq " F 1 pd, Lq ´F1 pxy, Lq

where F 1 pd, Lq " 2 ˆP pd,LqˆRpd,Lq P pd,Lq`Rpd,Lq . Indeed, objects are described by both attributes and class labels, so the F 1 score quantifies both the precision and the recall of the extent of the description w.r.t. the extent of the class labels. Moreover, we can also consider the Weighted Relative F 1 (WRF 1 ), that uses the relative support size of the subgroup to weight RF 1 :

WRF 1 pd, Lq " supppdq |O| ˆRF 1 pd, Lq
However, in most of the datasets, the distribution of class label is imbalanced. Some labels are associated to many objects in the dataset, and others are rarely used to label the data. Taking into account this setting is essential in this new EMM instance because the quality measure of the subgroups related to a frequent subset of class labels can be biased. F 1 does not equally evaluate subgroups related to over-represented subsets of labels and subgroups related to labels that are not over-represented. Empirically, we demonstrate that RF 1 is not effective to discover subgroups related to over-represented labels. F 1 pd, tl 2 uq ´F1 pxy0, tl 2 uq " 0.2. With L " tl 1 , l 2 u, the models are F 1 pd, tl 1 , l 2 uq " 0.66 and F 1 pxy, tl 1 , l 2 uq " 0.5, and thus RF 1 pd, tl 1 , l 2 uq " 0.16. Using WRF 1 as quality measure, the result is WRF 1 pd, tl 2 uq " 4{6ˆRF 1 pd, tl 2 uq " 0.13 and WRF 1 pd, tl 1 , l 2 uq " 4{6ˆRF 1 pd, tl 1 , l 2 uq " 0.11

Example 19. Again, let us consider the toy dataset in

supp(L) x β =200, l β =60 x β =200, l β =20 x β =110, l β =20

An adaptive F β -score for skewed label distributions

The WRAcc focuses, by definition, on the precision of labels and it promotes subgroups in populated target subspaces. The F 1 score makes a trade-off between precision and recall but we demonstrate empirically that this measure promotes subgroups covering few objects with low frequency label combinations. The trade-off lies with the so called F β score which adds a parameter β that allows to tune the importance of the recall.

We propose β to be a function of the support of the considered target subspace L, so that the trade-off can be automatically adapted during the search, βpsupppLqq. The greater supppLq, the closer to zero β is: The precision is fostered in F β for over-represented labels. Conversely, the lower supppLq, the closer to one β is: F β is equivalent to the traditional F 1 score (the harmonic mean of precision and recall) for non over-represented labels. Formally, given two positive real numbers x β and l β , we define the Relative F β score (RF β ) as follows (see also Figure 26): RF β pd, Lq " F β pd, Lq ´Fβ pxy, Lq where F β pd, Lq is defined as follows:

F β pd, Lq " p1 `βpsupppLqq 2 q
ˆP pd, Lq ˆRpd, Lq pβpsupppLqq 2 ˆP pd, Lqq `Rpd, Lq where βpsupppLqq is:

βpsupppLqq " 0.5 ˆˆ1 `tanh ˆxβ ´supppLq l β ˙İntuitively,
for over-represented labels in the data, since it is difficult to find rules with high recall and precision, the experts prefer to foster the precision instead of the recall. They prefer extracting several small subgroups with a high precision than a huge subgroup pd, Lq with plenty of non-L objects. In Figure 7 the red molecules are over-represented in the dataset, but it is more interesting having the different subgroups 1, 2, 3 and 4 with high precision, rather than a single huge local subgroup (5) which precision is much lower. For molecules that are not overrepresented, the measure considers both precision and recall: e.g., subgroup 6 is possible for the green molecules.

Similarly to WRF 1 we can define the Weighted Relative F β score as follows:

WRF β pd, Lq " supppdq |O| ˆRF β pd, Lq
Example 20. Let us take the example of the multi-label dataset in Table 8, with the description d " xr128 ď a ď 151s, r23 ď b ď 29sy again. We consider the F β measure to evaluate a model and RF β to evaluate the subgroup. Since supppl 1 q " 3, supppl 2 q " 4 and supppl 3 q " 3, we set x β " 3.3 and l β " 0.5. The β value for the subset of labels tl 2 u is 0.06 since in this setting, l 2 is over-represented within the dataset. The model induced by d on L " tl 2 u is F β pd, tl 2 uq " 1.

The model induced by the entire dataset is F β pxy, tl 2 uq " 0.67. Thus, ϕpd, tl 2 uq " RF β pd, tl 2 uq " F β pd, tl 2 uq ´Fβ pxy, tl 2 uq " 0.33. With WRF β , we have WRF β pd, tl 2 uq " 4 6 ˆRF β pd, tl 2 uq " 0.22 For the subset of class labels tl 1 , l 2 u, β " 0.99. The models are F β pd, tl 1 , l 2 uq " 0.66 and F β pxy, tl 1 , l 2 uq " 0.5, and thus ϕpd, tl 1 , l 2 uq " 0.16. Using WRF β , the quality measure of s is WRF β pd, tl 1 , l 2 uq " 4 6 ˆRF β pd, tl 1 , l 2 uq " 0.11. Note that for L " tl 1 , l 2 u, RF β and WRF β are equivalent to RF 1 and WRF 1 since L is not over-represented in the data.

Search space explorations

We present the search space of subgroups that needs to be traversed in all target subspaces. We briefly detail an algorithm for exhaustive search as a baseline for some of our experiments. We then present the two heuristic search techniques that we employ in our experiments.

Search space and exhaustive search

In standard SD and EMM, the search space of subgroups is given by the lattice of all possible descriptions pD, Ďq where d 1 Ď d 2 means that subgroup d 1 is more general than d 2 , or equivalently extpd 2 q Ď extpd 1 q. This lattice can be explored either in a depth-first (DFS) or in a breadth-first (BFS) search manner. During the traversal, the quality measure is computed for each subgroup. Contrary to the extent, the monotonic property does not necessary hold for the quality measure. In the end, a redundancy filter based on the similarity function sim and the maximum similarity threshold Θ is applied to output the top-k diverse subgroups.

In our case, we wish to evaluate a description on each of the target subspaces. We need to consider the following search space: D ˆ2C , where C is the set of labels. Hence, a subgroup is always considered in a target subspace in which the quality measure can be computed. Thus, only slight modifications in existing algorithms are required. We override the specialization/generalization relation Ď as follows: pd 1 , L 1 q Ď pd 2 , L 2 q ðñ extpd 2 q Ď extpd 1 q ^L2 Ď L 1

For that, we adapt the algorithm CloseByOne [START_REF] Kuznetsov | A fast algorithm for computing all intersections of objects in a finite semilattice[END_REF] from the Formal Concept Analysis [70] that can handle easily both nominal and numerical attributes [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF]. Without entering into the details, it avoids to generate subgroups having exactly the same support and truly operates an exhaustive search. Indeed, we could have adapted the most efficient subgroup discovery algorithm, SDMap* [START_REF] Atzmüller | Fast subgroup discovery for continuous target concepts[END_REF], but it is not purely exhaustive as it operates greedy cutting of numerical attributes. Moreover, we focus on heuristic search and already shown that MCTS performs better than SDMap* for large search space in the previous chapter.

Heuristic search with Beam-search

Beam search [START_REF] Lowerre | The HARPY speech recognition system[END_REF] is the most popular heuristic technique in SD/EMM. It has been originally adapted to consider the diverse subgroup set discovery problem by Leeuwen and Knobbe [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF]. The subgroup search space is explored level-wise (BFS) and each level is restricted to a set of diversified high quality patterns. The diversification is done as follows. Subgroups are sorted according to their quality: The best is picked and all the next patterns that are too similar (bounded Jaccard coefficient between their support) are removed. The first of the next patterns that is not similar is kept, and the process is iterated.

Adapting beam search considering the search space D ˆ2C with diversity on the target subspaces is done as follows. It starts from the most general subgroup. Next levels are generated by specializing subgroups either by restricting an attribute or by extending the subset of class labels with a new label as long as the quality measure is improved. There are at most |C| `řa i PA |a i |p|a i | `1q{2 possibilities to specialize each subgroup: We can proceed up to |C| extensions of the subset of labels to characterize L and |A| extensions of the description for which we can build up |a i |p|a i | `1q{2 possible intervals for numeric attributes. Note that in beam search, an attribute is refined at most once: We do not restrict an effective restriction anymore. We choose among those only a constant number of candidates to continue the exploration, i.e., the beam width: The beamW idth best subgroups w.r.t. the quality measure. Removing the redundancy is done as in the traditional case, but each subspace is considered separately to avoid to favor few excellent target subspaces: The subgroups are split into groups according to their target subspace, and the diversity filter is operated on each of them.

Sampling patterns with Monte Carlo Tree Search

We propose to sample the subgroup search space D ˆ2C relying on Monte Carlo Tree Search [START_REF] Browne | A survey of monte carlo tree search methods[END_REF]. Indeed, in the previous chapter, we showed that MCTS is able to handle very large search space and outperforms beam search in terms of quality and completeness of the result set when considering basic subgroup discovery and WRAcc. We recall that MCTS is a budget based approach: The more time and memory allocated, the better the result.

As a brief reminder, MCTS iteratively draws a random subgroup description s n from the expanded node s exp , called s 0 in this case, following a path s 0 Ă s 1 Ă s 2 Ă ... Ă s n . The best pattern quality measure found on the path is returned as a reward. s 0 is stored in a memory (the search tree) and the reward is back-propagated in the tree: Each node stores the number of times it was visited and the average quality measure obtained so far. The tree will drive the search for the next iterations (thanks to the upper confidence bound, a formula that expresses a trade-off between exploration and exploitation of the search space [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF]). In other terms, a new node (s 0 ) will be expanded into the tree according to this trade-off.

More specifically, MCTS operates a fixed number of iterations where: (i) It selects the most urgent node, called the selected node and denoted s ´1 in this case (s sel in the previous chapter), in the tree according to the UCB; (ii) it expands this node by randomly selecting one of the direct description specialization s ´1 Ă d 0 (the expanded node also called s exp ), (iii) it simulates a random path s 0 Ă s 1 Ă s 2 Ă ... Ă s n , and (iv) the best reward ϕps i q found on the path is used to update the tree. Each of these four steps can be achieved with many strategies. We use the best settings found for the WRAcc in basic subgroup discovery settings.

Experimental study

The subgroups we consider are equivalent to the so called Multi-label and sparse label-independent rules in [START_REF] Loza Mencía | Learning rules for multi-label classification: a stacking and a separate-and-conquer approach[END_REF]. In this article, the authors have defined a list of 8 types of rules in single and multi-label data. However, they focus on rules where only a single label can appear in the head of the rule and other label can appear in the body. They opt for a kind of binary relevance transformation (each label is learned separately) that is not suitable in our settings and thus is not included in our experimental evaluation. Experiments were carried out on an Intel(R) Core(TM) i7-7700HQ CPU 2.80 GHz machine with 8 GB RAM. All materials are available on https://github.com/guillaume-bosc/EMM_FBeta. After introducing the different datasets, we will answer to the following questions:

• How to tune x β and l β parameters of the F β measure?

• Is the MCTS approach also able to cope with the (Weighted) Relative F β ?

• What is the best measure to ensure the diversity on the target subspaces with MCTS?

• Is that measure also the best for beam search? It will thus advocate that the measure is not dependent of the heuristic.

• Is the (weighted) relative F β ranking the subgroups differently? It will thus empirically show that the other measures are not equivalent.

• How are precision and recall of the subgroup distributed w.r.t. target subspace frequency?

We should observe that the precision-recall trade-off is respected in the result sets: Fostering on precision for over-represented label sets, and also on the recall for the others. 14.

Dataset

Data

We experiment our approach with a set of multi-label datasets from the well-known Mulan repository [START_REF] Tsoumakas | Mulan: A java library for multi-label learning[END_REF]. We also experiment with the olfactory dataset built by a neuroscientist (coauthor of the present work) which is explained in the next chapter where we assess the interest of our approach in a real world scenario. Table 14 gives the properties of each dataset: The number of instances |O|, the number of attributes |A|, the domain of the attributes (nominal or numeric), the number of labels |C|, average number of labels associated to an object (cardinality), its density (the cardinality divided by the number of labels) and the mean and median of the number of objects per label. Figure 27 finally gives the label distribution for each dataset.

How to choose the x β and l β parameters for F β ?

Using F β requires to set the two parameters x β and l β . To choose these two parameters, one needs to answer to the following questions: At what support size a label subspace L is considered as over-represented? What is the speed of transfer from the normal representation state to the over-represented state? They are set thanks to the characteristics of the dataset. An automatic approach is to set x β to the 85 th percentile value and l β to the difference between the 85 th and 80 th percentiles. However, we advise to display the distribution of the frequency of the class labels (as shown in Figure 27) to correctly set up these parameters. The user must keep in mind that when |supppLq| " x β `2l β , β « 0.02 (L is considered thus over-represented and precision is fostered). Analogically, when |supppLq| " x β ´2l β , β « 0.98 (L is considered normal and the F β behaves almost as the F 1 score).

Is MCTS able to consider WRF β ?

Since the search space related to our datasets are too large to employ an exhaustive search, we design two heuristic methods to experiment with DSSD and we study the diversity on target subspaces issue. We show that MCTS using RF β allows to extract a diverse set of non redundant patterns if given enough computational budget (e.g., a given number of iterations). Figure 28 displays the evolution of the quality of the result set with MCTS when varying the number of iterations. We can note that, the more the iterations, the better the quality in the result set. Moreover, we use an exhaustive search in Olfaction to show that MCTS quickly converges to the quality of the result set obtained with the exhaustive search. However, since the search space of this dataset is too large, we randomly picked 2 attributes among the 82 attributes to make the exhaustive search tractable. Figure 28(a) shows that, given enough computational budget, MCTS converges to the quality of the result set obtained by the exhaustive search. From that, it is reasonable to employ MCTS with this new quality measure RF β . Furthermore, on Figures 28(b), we can notice that the quality of the result set still increases with the number of iterations.

Which measure ensures the most diverse result?

We compare the diversity on the target subspaces in the result set. For that, we use MCTS with 100k iterations. We output the top-1000 subgroups when using the different quality measures RAcc, RF Besides, contrary to RF 1 , the measures RAcc and RF β are able to homogeneously evaluate the subsets that are over-represented and non-over-represented. Thanks to the adaptive F β , RF β can either support the precision for the over-represented labels, or both precision and recall for non-over-represented labels. For the non-over-represented labels RAcc does not also foster on the recall of the subgroups. However, with RF 1 , the over-represented subgroups are rarely output in the result set because their recall is low when the precision is high and vice versa.

Moreover, the experiments with the weighted version of these measures lead almost to the same result: W RF β ensures a great diversity on the target subspaces and is able to characterize both over-represented labels and non-over-represented labels. However, the weighted factor fosters more on over-represented labels since the relative support size is greater. Note that when the distribution of the labels is not imbalanced, such as in Emotions, the measures behave in the same way, which is an expected behavior. Finally, Figure 31 displays both the evolution of the diversity on the target space and the value of the quality measure of the subgroups in the result set varying the number k of output patterns. Figures 31(a)-(b)-(c) show that with RAcc or W RAcc there is a few diversity in the target subspace whereas with RF 1 , W RF 1 , RF β and W RF β the diversity is high. Moreover, Figures 31(d)-(e)-(f) display that with the weighted version of these measure, the quality in the result set decreases faster than with the relative version. Indeed, the weighted factor makes the quality measure foster on over-represented subgroups and thus avoid the extraction of non-overrepresented ones even if the precision and the recall is high.

Does RF β also ensure the best diversity?

The previous subsection exhibits that RF 1 , W RF 1 , RF β and W RF β increase the diversity on the target space in the result set. In some cases, we showed that this diversity is also high with RAcc and W RAcc. However, in the previous chapter, we ensured that MCTS leads to a higher completeness of the result set. Indeed, we now consider some results obtained with a beam search. Figure 32 shows that for all the measures, except RF β , there is a low diversity on the target space. Besides, except with RF β , the beam search can not extract more than 300 diverse and non redundant subgroups. Clearly, RF β provides the largest diversity in the result set.

Is the RF β ranking the subgroups differently?

We experiment with the 6 different quality measures, to test if they are equivalent, i.e., they provide the same ranking of subgroups. Since it is not possible to use an exhaustive search, we cannot directly compare the ranking of the subgroups (most subgroups in a result set are not included in another result set). For that, we define an optimistic similarity measure between two result sets based on Jaccard coefficients: We compute the mean of the maximum of the Jaccard coefficients between a couple of subgroups in the two different result sets. Formally we compute meanSimpS 1 , S 2 q " 1 |S 1 | ˆřs 1 PS 1 max s 2 PS 2 Jpsuppps 1 q, suppps 2 qq and then the similarity between two result sets S 1 and S 2 is: maxSimpS 1 , S 2 q " max pmeanSimpS 1 , S 2 q, meanSimpS 2 , S 1 qq Figure 33 displays the matrix of maxSim between the result sets obtained with the different quality measures in CAL500. Clearly, it shows that they do not share the same subgroups in their result set. Thus, the measures are not equivalent. The results are identical for the other datasets.

Does F β dynamically adapt to the label frequency?

We said that for the over-represented labels, we want to support the precision, and that, for other frequencies of labels, we want to take into account both the precision and the recall of the subgroup. To assess the behavior of the measures, we experiment with the measures we use as models, namely Acc, F 1 and F β . From that, we display the precision and the recall of the subgroups. Figure 34 shows two different views of the precision and the recall of the subgroup the precision is fostered, the recall is always low whatever the frequency of L. Concerning F 1 , we support both the precision and the recall, but there are less subgroups in the result set that are related to labels for which the frequency is high because the F 1 score is low. in the result set are plotted in the precision/recall space. Moreover a heatmap is used to show the frequency of the subset of labels L to which the subgroups are related: The points in red are subgroups related to over-represented labels, and the points in blue are subgroups related to under-represented labels. Clearly, Acc does not foster on the recall. Besides, F 1 extracts few subgroups related to over-represented labels (many blue points). Finally, F β behaves as expected: (i) Both over-represented and under-represented labels are covered, i.e., the diversity in the target space is high ; and (ii)for over-represented labels the precision is fostered, and for other labels both recall and precision are taken into account.

Synthesis of the experiments

The parameters x β and l β for the F β measure can be easily set thanks to the distribution of the label frequency. In general, our results suggest that exhaustive search is not tractable because the search space of the datasets is too large, and thus heuristic explorations are needed. MCTS is able to quickly find interesting subgroups with RF β and W RF β . Moreover, the results support the idea that RF β provides a better diversity on the target subspace using either MCTS or a beam

Conclusion

Motivated by a problem in neuroscience and olfaction, we proposed an original subgroup discovery approach to mine descriptive rules characterizing specifically subsets of class labels. For that matter, we revisited the diverse subgroup set discovery problem within the exceptional model mining framework: Each subgroup can be evaluated in different target subspaces, and a quality measure helps to take into account the distribution of the labels overs the dataset. This measure is also effective in heuristic search, e.g., with an enumeration based on Monte Carlo Tree Search, as the results are more diverse, both on the subgroup description and the target subspaces. We showed the effectiveness of this method through a large set of experiments.

Chapter 6

Application in neuroscience for the study of the olfactory percept

The Structure-Odor Relationship

Around the turn of the century, the idea that modern, civilized human beings might do without being affected by odorant chemicals became outdated: The hidden, inarticulate sense associated with their perception, hitherto considered superfluous to cognition, became a focus of study in its own right and thus the subject of new knowledge. It was acknowledged as an object of science by Nobel prizes (e.g., [START_REF] Buck | A novel multigene family may encode odorant receptors: a molecular basis for odor recognition[END_REF] awarded 2004 Nobel prize in Physiology or Medicine); but also society as a whole was becoming more hedonistic, and hence more attentive to the emotional effects of odors. Odors are present in our food, which is a source of both pleasure and social bonding; they also influence our relations with others in general and with our children in particular. The olfactory percept encoded in odorant chemicals contribute to our emotional balance and wellbeing: Olfactory impairment jeopardizes this equilibrium.

Neuroscience studies revealed that odor perception results from a complex phenomenon rooted in the chemical properties of a volatile molecule (described by multiple physicochemical descriptors) further detected by our olfactory receptors in the nasal cavity. A neural signal is then transmitted to central olfactory brain structures [START_REF] Meierhenrich | The molecular basis of olfactory chemoreception[END_REF]. At this stage, a complete neural representation, called "odor" is generated and can then be described semantically by various types of perceptual quality (e.g., fruity, floral or woody). While it is generally agreed that the physicochemical characteristics of odorants affect the olfactory percept, no simple and/or universal rule governing this Structure Odor Relationship (SOR) has yet been identified. Why does this odorant smell of roses and that one of lemon? Considering that the totality of the odorant message was encoded within the chemical structure, chemists have tried to identify relationships between chemical properties and odors. Topological descriptors, eventually associated with electronic properties or molecular flexibility were tentatively connected to odorants descriptors. However, it is now quite well acknowledged that structure-odor relationships are not bijective. For example, very different chemicals trigger a typical "camphor" smell, while a single molecule, the so-called "cat-ketone" odorant, elicit two totally different smells as a function of its concentration [START_REF] De March | Structure-odour relationships reviewed in the postgenomic era[END_REF]. At best, such SOR rules are obtained for a very tiny fraction of the chemical space, emphasizing that they must be decomposed into sub-rules associated with given molecular topologies [START_REF] Delasalle | Structure-odor relationships of semisynthetic β-santalol analogs[END_REF]. As such, this lack of bijective relationship must be handled. It suggests that a simple, universal and perfect rule does probably not exist, but instead, a combination of several sub-rules should be put forward to encompass the complexity of SOR. In this chapter, we describe our data science approach to advance the state of the art in understanding the mechanisms of olfaction and to support the emergence of new hypothesis.

Therefore, we have been combining neuroscience, chemistry and data mining. Indeed, datamining methods can be used to answer the SOR discovery problem, either through the building of predictive models or through rules discovery. One obstacle to this is that olfactory datasets are complex (i.e., several thousand of dimensions, heterogeneous descriptors, multi-label, imbalanced classes, and non robust labelling) and, we suffer from a lack of data-centric methods in neuroscience that would be suitable for this level of complexity. The main aim of our study has been to examine this issue by linking the multiple molecular characteristics of odorant molecule to olfactory qualities (fruity, floral, woody, etc.) using a descriptive approach (pattern mining). Indeed, a crowd-sourced challenge was recently proposed by IBM Research and Sage called DREAM Olfaction Prediction Challenge [START_REF]Dream olfaction prediction challenge[END_REF]. The challenge resulted in several models that were able to predict especially pleasantness and intensity and 8 out of 19 olfactory qualities ("garlic", "fish", "sweet", "fruit", "burnt", "spices", "flower" and "sour") with an average correlation of predictions across all models above 0.5 [START_REF] Keller | Predicting human olfactory perception from chemical features of odor molecules[END_REF]. These findings are timely and interesting because they show the existence of a predictive relationship between certain olfactory qualities and the physicochemical properties of odorant molecules. Nevertheless, to go further into the understanding of the stimulus-percept issue in olfaction, it is important to explain and thus to isolate physicochemical rules allowing describing these olfactory qualities. Identifying such physico-chemical rules characterizing odor quality opens a field that is still little explored in neuroscience research, shedding new light on olfactory system functioning.

Neuroscientists are faced to a series of issues including (i) the lack of large databases containing sufficient number of stimuli described by both physicochemical properties and olfactory qualities, (ii) the large number of dimensions -several thousands -needed to describe the molecules and, above all, (iii) a lack of data-processing methods suitable for this level of complexity. The present chapter proposes to solve these issues by -first -setting up a large database containing more than 1500 odorant molecules described by both of physico-chemical properties and olfactory qualities. Secondly, we make use of such complex heterogeneous data with the aim of deriving new neuro-scientific knowledge or hypotheses such as descriptive models. This is where our new EMM instance based on the MCTS exploration fully makes sense as molecules are associated to several odors, with a highly skewed distribution and a very large search space.

An original olfaction dataset

One prominent methodological obstacle in the field of neuroscience concerns the absence of any large available database (ą1000 molecules) combining odorant molecules described by two types of descriptors: Perceptual ones such as olfactory qualities (scent experts defining a perceptual space of odors), and chemical attributes (chemical space). The dataset provided by the IBM challenge [START_REF] Keller | Predicting human olfactory perception from chemical features of odor molecules[END_REF] is a clinical one, i.e., odorant molecules were not labeled by scent experts. To tackle this issue, the neuroscientists have recently created a new dataset based on the olfactory percept of scent experts. Basically, they gathered the data from two different sources: (i) The Dragon 6 software (available on talete.mi.it), and (ii) the well known atlas Arctander [START_REF] Arctander | Perfume and flavor materials of natural origin[END_REF]. The first one provides the values of almost 5, 000 physico-chemicals properties (e.g., the molecular weight or the number of carbon atoms) for thousands of chemical molecules. The latter is an atlas created by scent experts that maps 1, 689 molecules to subset of odors among 74 olfactory qualities such as Fruity, Vanilin, or Camphor. From such raw data, the neuroscientists pre-processed the data to keep only the molecules that are present in both datasets. Moreover, the chemists identified and pointed out a set of 82 physico-chemical properties that have been known or guessed to be discriminant in SOR. Thus, the final data is made of 1, 689 molecules described by 82 physicochemical properties and associated to at average 2.88 odors among the 74 olfactory qualities. As such, and to the best of our knowledge, the present database is one of the very few in the field that enable quantification and qualification of more than 1, 500 molecules at both, perceptual (neurosciences) and physicochemical (chemistry) levels. The distribution of the 74 olfactory qualities is illustrated in Figure 25.

h(odor): An interactive tool to elicit hypotheses on SOR

We developed an interactive Web application that enables the experts of the domain (e.g., neuroscientists and chemists) to directly interact with the algorithm to guide the exploration of the search space. In other terms, they can use their knowledge to exploit the subgroups that seem to be interesting or to explore some parts of the search space that have been ignored so far. To interact with the algorithm, the user can like or dislike some temporary rules. This feed-back is used to propose new rules that can be more interesting for a given user. The application, called h(odor), is available online with a video tutorial supporting the use case at http://liris.cnrs.fr/dm2l/hodor/.

System architecture

A core module (server) is contacted by a client (Web interface) to initiate the mining algorithm with the given parameters. This core module allows the user to interact/guide the exploration based on the likes/dislikes of the user.

The Core Module

This is the back-end of the h(odor) application. Based on NodeJS, the Core Module is the gateway between the user and the ELMMut algorithm (see next subsection): It is in charge of the interaction. For that, JSON data are sent to and received from the SD algorithm through sockets thanks to a dedicated communication process. Moreover, this module controls the UI to display results extracted from the SD Algorithm and collects the user preferences (like/dislike).

The User Interface (UI)

The front-end of the application, based on Bootstrap and AngularJS, enables the user to select the parameters of the SD Algorithm and to run it. Once the subgroups of the first level of the beam search are extracted (the algorithm is paused waiting the user preferences), the UI displays these subgroups and the user can like/dislike some of them: The liked subgroups are exploited in the next iteration of the algorithm, whereas disliked subgroups are removed from the explored search space. When the algorithm finishes, the UI displays the results.

Use case: Eliciting hypotheses on the Musk odor

We develop a use case of the application from an end user perspective, typically a neuroscientist or a odor-chemist that seeks to extract descriptive rules to study the Structure-Odor Relationships. In this scenario, we consider that the expert wishes to discover rules involving at least the musk odor.

1-Algorithms, parameters and dataset selection

In the Algorithms section of the left hand side menu, the user can choose the exploration method and its parameters. In this use case, we exploit the ELMMut algorithm. It implements a beam search strategy to extract subgroups based on a quality measure. We plan to add the mcts4dm algorithm: It requires to implement the interactive process within the MCTS exploration. Once the exploration method is chosen, we have to select the olfactory dataset as introduced in the previous section, and choose to focus on the musk odor. We decided to set the size of the beam to 50 (the exploration is quite large enough) and the minimum support threshold to 15 (since supppM uskq " 52, at least the subgroups have to cover 30% of the musk odorants). Other parameters are fixed to their default values.

2-Interactive running steps

When the datasets and the parameters have been fixed, the user can launch the mining task clicking on the Start mining button. When the first step of the beam search is finished, the SD Algorithm is paused and the subgroups obtained at this step are displayed to the user. The interaction view in the front-end presents the olfactory qualities involved at this level of the exploration (see Figure 35). Each subgroup is displayed in a white box with the current descriptive rule on the physicochemical descriptors and some quantitative measures. For each subgroup box, the user can select in the top right corner if she likes/dislikes this subgroup. For example, at the first step, the application displays the subgroups extracted at the first level for the Musk odor. As it is a known fact in chemistry that the musk odor involves large molecules, we like the subgroup which description is d " r238.46 ď M W ď 270.41s. After that, we keep on exploring by clicking the Next button. Another interactive step begins, but the expert has no particular opinion so she can jump to the next level.

3-Analysis of the results

Once the algorithm finishes (the quality measures cannot be improved), we can study the table of results. For example, the description of one of the best extracted subgroups s is: r238.46 ď M W ď 0.316sr1 ď nCsp2 ď 7s that involves large odorants. In this subgroup, the interval restriction on the molecular weight M W corresponds to high values, and thus to large molecules. The goal of the h(odor) application is to confirm knowledge and to elicit new hypotheses for the SOR problem. In the case of s, the neuroscientists are interested in understanding why these descriptors (excepted the molecular weight) are involved in the M usk odor. With the h(odor) tool, we can also proceed to rule combination (see Figure 36). Indeed, our experts suggest that a simple, universal and perfect rule does probably not exist, but instead, a combination of several sub-rules should be put forward to encompass the complexity of SOR. The user can manually select several rules in the result set to evaluate the quality of their combination on a graph. Also, h(odor) enables to automatically computes the best combinations of rules w.r.t. the precision and the recall of the combination over the odors10 .

Eliciting new hypothesis on the SOR problem

We presented the interactive Web application h(odor) that enables the user (e.g., the neuroscientist or the chemist) to guide the exploration of the search space. Our experts keep on experimenting with this application. However, h(odor) does not embed the mcts4dm algorithm yet, though it would provide better results than beam search based approaches. Thus, the experts are also analyzing and interpreting the rules provided by mcts4dm to study these raw results before to interact with the algorithm. In this section, we provide some feedback and interpretations given by the experts on the results computed by mcts4dm.

Identification of relevant physicochemical attributes

We consider the experiment on the olfactory dataset (introduced in this chapter) when we use the RF β score, minSupp " 30. A relevant information for neuroscientists and chemists concerns the physicochemical attributes that appear in the descriptive rules. As showed in [START_REF] Khan | Predicting odor pleasantness from odorant structure: pleasantness as a reflection of the physical world[END_REF], the sum of atomic van der Waals volumes, denoted as Sv, is discriminant with regard to the hedonism of an odor, and the higher Sv, the more pleasant an odor. Moreover, the higher the rate of nitrogen atoms (N %), the less pleasant an odor is, consistent with the idea that amine groups (´N H 2 ) are associated with bad odors (such as cadaverine or putrescine). Based on these observations, we find subgroups related to either the Floral or Fruity quality that are characterized by a special range of values with regard to Sv and N %. For example, s 1 " xr3.0 ď N % ď 33.3s r2.7 ď O% ď 33.3s r0.0 ď nR05 ď 1.0s rnRCN " 0.0s, tF ruity, Grapeuy and s 2 " xr6.57 ď Sv ď 43.17s r1.0 ď nN ď 3.0s r1.0 ď nHDon ď 2.0s, tF loraluy are output subgroups. The quality measure of s 1 is 0.23 with a precision of 0.16 and a low recall of 0.5. For s 2 , its quality measure is up to 0.37, its precision is 0.65 and its recall is 0.06. The first subgroup contains in its description the N % attribute associated to a very low percentage, and s 2 includes the Sv attributes with a range of values that corresponds to its higher values. In general, the quality M usk is associated with large and heavy molecules: The molecular weight (M W ) of these molecules is thus high. In the output subgroups, most of those associated to the musk quality include in their description the M W attribute with high values, or any other attribute that is positively correlated with M W , such as SAtot. For example, s 3 " xr27.03 ď M W ď 297.3s r1.0 ď nBM ď 18.0s rnR03 " 0.0s r0.0 ď nCp ď 7.0s r5.0 ď nCrs ď 16.0s rnHDon " 0.0s, tM uskuy with a quality measure of 0.2 (precision: 0.27, recall: 0.25) is about molecules with it molecular weight between 27.03 and 297.3. Moreover, when the quality Musk is combined with the quality Animal, we still have a high molecular weight but there are other attributes with specific range of values: s 4 " xr168.808 ď SAtot ď 464.918sr6.0 ď nCar ď 16.0sr3.261 ď M LOGP ď 4.593s r0.0 ď nCsp2 ď 7.0s, tM usk, Animaluy. This latter topological attribute is consistent with the presence of double bonds (or so-called sp2 carbon atoms) within most of the musky chemical structures, to provide some hydrophilicity.

Providing relevant knowledge on the process of the olfactory percept

Another important information brought by such findings lies in the fact the SOR problem should be viewed and studied thanks to a "multiple description" approach rather than a "one rule for one quality" approach (i.e., bijection). Indeed, a number of odor qualities were described by very specific rules. For example, 44% of the molecules described as camphor can be described by 3 rules physicochemical rules, with a very low rate of false positives (0.06%; molecules being described by the physicochemical rule, but not described perceptively as camphor). Similar patterns were observed for other qualities: e.g., mint (3 descriptive rules; 32% of the molecules described as mint; 0.06% of false positives), ethereal (3; 35%; 0%), gassy (3; 36%; 0.36%), citrus (3; 42%; 0.24%), waxy (3; 43%; 0%), pineapple (3; 48%; 0%), medicinal (3; 49%; 0.30%), honey (4; 54%; 0.06%), sour (3; 56%; 0.36%). Focusing on these qualities, this confirms that a universal rule cannot be defined for a given odorant property, in line with the extreme subtlety of our perception of smells. For example, looking in more details on the produced rules for Camphor (see Figure 37), it appears that one rule is mostly using topological descriptors, while the second rather uses chemical descriptors. The third rule has a combination of these two.

Perspectives in neurosciences and chemistry

The present findings provide two important contributions to the field of neurosciences and chemosensation. First, although the SOR understanding seems to be illusory for some odor qualities, our approach suggests that there exist descriptive rules for some qualities that also highlight the relevance of some physicochemical descriptors (Sv, M W , etc.). Second, the present model confirms the lack of bijective (one-to-one) relationship between the odorant and the odor spaces and it emphasizes that several sub-rules should be taken into account when eliciting structureodor relationships. From these findings, experts in neurosciences and chemistry may generate the following new and innovative hypotheses in the field: (i) explaining inter-individual variability in terms of both behavioral and cognitive aspects of odor perception, (ii) explaining stability in odor-evoked neural responses and (iii) correlating the multiple molecular properties of odors to their perceptual qualities. Our collaborators are preparing a paper for the journal in neuroscience PLOS One -Computational Biology.

Chapter 7

Conclusion and perspectives

Summary

Motivated by a problem in neuroscience and olfaction, we designed a data science approach based on the knowledge discovery in databases process (KDD) to elicit new hypotheses on the structureodor relationship. For that purpose, we studied subgroup discovery (SD) and its generalization exceptional model mining (EMM) to support the discovery of supervised rules that distinguish target labels.

In presence of large data, such as the olfactory dataset that contains lots of numerical descriptors, an exhaustive exploration of the search space is unfeasible. Thus, some heuristic approaches have been used, e.g., beam search, evolutionary algorithms and sampling methods. However, they are not able to propose a high completeness in the result set, i.e., containing many different enough local optima. We advocate for the use of MCTS for pattern mining: An aheuristic exploration strategy leading to "any-time" pattern mining that can be adapted with different measures and policies. The experiments show that MCTS and our mcts4dm algorithm provides a much better completeness in the result set than existing heuristic approaches. Interesting subgroups are found in a reasonable amount of iterations and the quality of the result iteratively improves. In addition, we show that numerical attributes are handled without using greedy discretization either within a pre-processing task or by means of an on-the-fly setting during the enumeration. We enumerate all the possible intervals to ensure that mcts4dm converges to an exhaustive search if given enough time and memory.

Moreover, we proposed an original subgroup discovery instance to mine descriptive rules characterizing specifically subsets of class labels. For that matter, we revisited the diverse subgroup set discovery problem within the exceptional model mining framework: Each subgroup can be evaluated in different target subspaces. A subgroup does not derive one model but several models: One model is built on each subset of class labels. It induces a huge increase of the search space size that can still be handled by the MCTS enumeration. As we face a high variance in the frequency of the class labels in the olfactory dataset (some odors are much more frequent than others), we define a new model F β . It employs a function β that dynamically either fosters on the precision of the subgroups w.r.t. the target subspace if this latter is over-represented is the data, or that converges to the F 1 value score for other target subspaces. We derive several quality measures to compare two instances of our model. This EMM instance is also tractable for a MCTS-based search, as the results are more diverse, both on the subgroup description and the target subspaces. We showed the effectiveness of this method through a large set of experiments.

Finally, the combination of both the enumeration based on MCTS and the new EMM instance is used to elicit new hypotheses on the structure-odor relationship in our olfactory application in collaboration with neuroscientists and chemists. The results suggest new understandings about the links between the physico-chemical properties of a molecule and its odor. The experts of the domain are still working on the results provided by both our algorithm mcts4dm and our interactive Web application h(odor) 11 .

Perspectives

The exploration based on Monte Carlo tree search is essentially used in the artificial intelligence domain to solve games and planning problems. To the best of our knowledge, it is the first attempt to revisit it for pattern mining issues. Thus, it remains many opportunities to improve and to adapt it for other pattern mining tasks than subgroup discovery and exceptional model mining. In this section, we highlight the main issues we plan to study either for the short-term or a long-term perspective.

Improvements of our algorithm mcts4dm

We have showed that our algorithm mcts4dm is able to quickly find a diverse set of patterns with a high quality measure. However, we notice that the memory linearly increases with the number of objects in the data and the number of iterations. This is due to the enumeration of the several projected databases when specializing a description. Indeed, each node of the search tree stores a bitset for the extent of the subgroup related to this node: The more the iterations, the more the nodes in the tree, and thus the more the bitsets. To reduce the impact of both the number of objects and the storage of bitsets with the generation of a node, we are working on a new implementation method that only stores one bitset for the extent for all the nodes. For each iteration, it consists of re-processing the refinements of each selected node during the Select method from the root to the final selected node s sel . This enables to reduce the memory usage but it can be a bit more time consuming since we have to compute the extent and the description of each selected node. However, the implementation of structures storing the data in an efficient way (e.g., ordering the values of numerical attributes and using pointers to the objects that take a specific value) enables to reduce the runtime. In addition to this algorithmic improvement, we plan to implement an interactive version of mcts4dm to extend the interactive Web application h(odor). We also think about using parallelisation for our algorithm to improve its efficiency. Besides, we may also handle the high branching factor we faced in several dataset. We discuss these three improvements in the following.

Interactive version

Our h(odor) application relies on an interactive algorithm allowing the experts to use their knowledge to guide the exploration of the search space. Beam search algorithms are easy to turn interactive by stopping after each level of the exploration to propose to the expert to select which of the subgroups would be extended at the next iteration. However, making mcts4dm interactive would require to study when the algorithm has to be paused to take the expert's feedback, which temporary patterns to output to the user and then how to incorporate the feedback into the search tree. The first point can be solved by pausing the algorithm, say each 1, 000 iterations, or to allow the user to manually interrupt the algorithm when he/she wants. Solving the second issue appears more difficult. After N iterations, mcts4dm has computed at least N patterns and eventually those that are stored during the memory policy. The question is thus, which patterns have to be output to the user to allow him/her to like/dislike. We can randomly sample k subgroups among all the computed ones, or we can sample them based on their quality measure. The third point concerns the use of the expert's feedback in the search tree. A naive solution would be to bias the aggregated value of rewards Qpsq of a liked/disliked subgroup s to improve/decrease its UCB value. However, it also requires to bias all of its parents to reach it from the root if it is liked and conversely avoid it to be selected if it is disliked. In addition, the choice of the node to expand can also be biased to foster on user's preferences. Similarly, during the simulation, the refinements may no longer be randomly picked but biased by the expert's feedback.

Parallelisation

The characteristics of the MCTS algorithm, where each iteration is independent w.r.t. the others, make this approach tractable for parallelisation. Parallelisation can provide great advantages by performing several iterations over the tree in the same time, and thus be able to quickly and efficiently enumerate the search space. There exists three main approaches to employ parallelisation for MCTS algorithm (see Chapter 3): The leaf parallelisation, the root parallelisation and the tree parallelisation [START_REF] Cazenave | On the parallelization of uct[END_REF][START_REF] Chaslot | Parallel monte-carlo tree search[END_REF]. In our settings, we think that the most usefull approach is leaf parallelisation since several parallel simulations are run from the expanded node s exp . It enables to get a more precise overview of the search space rooted by s exp . Besides, this approach does not require to use a mutex on the search tree and the pool of simulations are run together. However, its main drawback is that the iteration is over when all the simulations are completed: The runtime depends on the longer simulation. Another approach would be to split the search space into different parts. In each part a MCTS is run. This method would avoid to put a mutex on the tree but it will not respect the global exploration/exploitation trade-off but instead a local trade-off in each part of the search space: Some less interesting parts would be as exploited as interesting parts. Finally, we are interested to launch several MCTS instances in the search space rooted in different parts of the lattice. Basically, as a pre-processing task, we can project the pattern language into a less complex one (e.g., from sequences to itemsets) in order to find interesting patterns in this less expressive language that would be used as seeds to launch several MCTS instances within the same search tree.

Handling the high branching factor

A well known problem in the MCTS method is that it tends to explore much more than it exploits. Indeed, since MCTS expands all the children of a node before exploiting one of its children, it requires lots of iteration to explore the search space in depth. This is due to the high branching factor. For that the progressive widening method has been proposed [START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF][START_REF] Coulom | Computing "elo ratings" of move patterns in the game of go[END_REF]. Basically, the number of children that have to be expanded before selecting a child depends on the number of visits N p.q. The keypoint in this method is the choice of the child to expand. Indeed, it is better to expand with the best children at the beginning since it requires more iterations to expand all the children. The choice of the child to expand can be done with the Rapid Action Value Estimator (RAVE) [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF][START_REF] Cazenave | Generalized rapid action value estimation[END_REF]. Moreover, in addition to RAVE, we may take into account redundancy in this step: The choice of the child to expand can be based on both RAVE and a measure that states if the considered child is similar to an existing node in the search tree or if it is somehow different from the computed subgroups. Thus, the child having the best RAVE and that is not similar to other patterns has more chance to be chosen than other children.

Handling complex pattern mining issues

As future work, we are also interested in solving some pattern mining problems with MCTS.

In this thesis, we studied supervised rules discovery with subgroup discovery and exceptional model mining. We considered boolean, nominal and numerical attributes. The subgroups are evaluated with one quality measure. However, in pattern mining, there exists different settings and constraints which we plan to solve with our framework based on MCTS. The first one consists in considering more expressiveness in the pattern language. The second is to take into account several quality measures to evaluate a pattern.

Toward more expressiveness in the pattern language

In pattern mining, many pattern languages have been defined and studied: From itemsets to graphs, sequences, or polygons. To handle different pattern languages, it is required to define formally both the search space and the refinement operators. For instance, for the case of sequential pattern mining, several algorithms have been proposed to explore the search space in different ways [START_REF] Han | Frequent pattern mining: current status and future directions[END_REF]. The traditional way to deal with sequential patterns is to use sequence extensions or itemset extensions with projected databases such as PrefixSpan algorithm [START_REF] Pei | Prefixspan: Mining sequential patterns by prefix-projected growth[END_REF]. This is the enumeration method we employed in our previous works on sequential pattern mining to search for imbalanced strategies in electronic sport data. However this enumeration principle is not suitable for a sampling method such as MCTS, since it would not sample the search space uniformly (as for the lectic order itemset mining we discussed in this thesis). The naive way consisting in extending a sequence with an item that can be appended in any existing itemsets or in new ones is possible but the branching factor would burst. Besides, MCTS has already been applied to enumerate convex polygons [START_REF] Belfodil | Mining convex polygon patterns with formal concept analysis[END_REF] and the results suggest that MCTS can handle efficiently more complex pattern languages by defining correct strategies. In addition, we plan to investigate on other pattern languages such as dynamic or attributed graphs, or even 3D graphs. Once again, it requires to adapt the steps of mcts4dm, and especially the Expand and RollOut methods that include the refinement operator.

Towards compressed search trees

As pointed out in the experiments, when local optima are located deeper in the search space, it may require a lot of iterations to reach them. This is even more true when dealing with numerical attributes with a large domain (recall that we consider that the domain of a numerical attribute is made of the different values taken by the objects in the data). Many minimal changes are required (and thus several refinements are performed) to reach a small interval. We proposed a refinement operator based on the generators of the equivalence class that ensures that two nodes in a branch do not have the same support. However, in some cases it is not sufficient. The question is how to compress the search tree, i.e., how to reduce the number of generated nodes, without loss of information? A possible solution would be to incorporate expert's knowledge to prune some parts of the search space that are known to be not interesting. However, we would like to keep the method as generic as possible to be able to apply it to different application domains.

Taking into account the theory developed over the past twenty years in pattern mining (upper bounds, condensed representations, ...) [START_REF] Giacometti | 20 years of pattern mining: a bibliometric survey[END_REF] seems to be the wisest solution to reduce the size of the search tree in the MCTS algorithm. Indeed, several enhancements are defined to reduce the number of generated patterns with or without loss of information.

Multi-objective pattern mining

Up to now, we use one quality measure to evaluate a pattern. However, in some applications, a measure is not enough to quantify the interestingness of a pattern. In pattern mining, the skypatterns have been defined when dealing with patterns evaluated with several measures [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]. In this setting, no thresholds are used: The aim is to extract only the dominant patterns w.r.t. the several measures using the Pareto frontier. This is a multi-objective optimization task. Using several measures in a MCTS means that the reward of each simulation is no longer a value but a set of values, corresponding to the several measures. Then, it is required to study the upper confidence bound formula when selecting a child of a node. Indeed, how to take into account several measures to compute UCB? The aggregated value of the rewards of a node Qp.q requires to be defined with the several measures: The Pareto frontier may be used for that.

Résumé

La découverte de motifs qui caractérisent fortement une classe vis à vis d'une autre reste encore un problème difficile en fouille de données. La découverte de sous-groupes (Subgroup Discovery, SD) est une approche formelle de fouille de motifs qui permet la construction de classifieurs intelligibles mais surtout d'émettre des hypothèses sur les données. Cependant, cette approche fait encore face à deux problèmes majeurs : (i) comment définir des mesures de qualité appropriées pour caractériser l'intérêt d'un motif et (ii) comment sélectionner une méthode heuristique adaptée lorsqu'une énumération exhaustive de l'espace de recherche n'est pas réalisable. Le premier problème a été résolu par la fouille de modèles exceptionnels (Exceptional Model Mining, EMM) qui permet l'extraction de motifs couvrant des objets de la base de données pour lesquels le modèle induit sur les attributs de classe est significativement différent du modèle induit par l'ensemble des objets du jeu de données. Le second problème a été étudié en SD et EMM principalement avec la mise en place de méthodes heuristiques de type recherche en faisceau (beam-search) ou avec des algorithmes génétiques qui permettent la découverte de motifs non redondants, diversifiés et de bonne qualité. Dans cette thèse, nous soutenons que la nature gloutonne des méthodes d'énumération précédentes génère cependant des ensembles de motifs manquant de diversité. Nous définissons formellement la fouille de données comme un jeu que nous résolvons par l'utilisation de la recherche arborescente de Monte Carlo (Monte Carlo Tree Search, MCTS), une technique récente principalement utilisée pour la résolution de jeux et de problèmes de planning en intelligence artificielle. Contrairement aux méthodes traditionnelles d'échantillonnage, MCTS donne la possibilité d'obtenir une solution à tout instant sans qu'aucune hypothèse ne soit faite que ce soit sur la mesure de qualité ou sur les données. Cette méthode d'énumération converge vers une approche exhaustive si les budgets temps et mémoire disponibles sont suffisants. Le compromis entre l'exploration et l'exploitation que propose cette approche permet une augmentation significative de la diversité dans l'ensemble des motifs calculés. Nous montrons que la recherche arborescente de Monte Carlo appliquée à la fouille de motifs permet de trouver rapidement un ensemble de motifs diversifiés et de bonne qualité à l'aide d'expérimentations sur des jeux de données de référence et sur un jeu de données réel traitant de l'olfaction. Nous proposons et validons également une nouvelle mesure de qualité spécialement conçue pour des jeux de donnée multi labels présentant une grande variance de fréquences des labels.

Mots-clés: Découverte de connaissances, règles supervisées, sous-groupes, fouille de modèles exceptionnels, recherche arborescente de Monte Carlo, diversité, olfaction

Abstract

The discovery of patterns that strongly distinguish one class label from another is still a challenging data-mining task. Subgroup Discovery (SD) is a formal pattern mining framework that enables the construction of intelligible classifiers, and, most importantly, to elicit interesting hypotheses from the data. However, SD still faces two major issues: (i) how to define appropriate quality measures to characterize the interestingness of a pattern; (ii) how to select an accurate heuristic search technique when exhaustive enumeration of the pattern space is unfeasible. The first issue has been tackled by Exceptional Model Mining (EMM) for discovering patterns that cover tuples that locally induce a model substantially different from the model of the whole dataset. The second issue has been studied in SD and EMM mainly with the use of beamsearch strategies and genetic algorithms for discovering a pattern set that is non-redundant, diverse and of high quality. In this thesis, we argue that the greedy nature of most such previous approaches produces pattern sets that lack diversity. Consequently, we formally define pattern mining as a game and solve it with Monte Carlo Tree Search (MCTS), a recent technique mainly used for games and planning problems in artificial intelligence. Contrary to traditional sampling methods, MCTS leads to an any-time pattern mining approach without assumptions on either the quality measure or the data. It converges to an exhaustive search if given enough time and memory. The exploration/exploitation trade-off allows the diversity of the result set to be improved considerably compared to existing heuristics. We show that MCTS quickly finds a diverse pattern set of high quality in our application in neurosciences. We also propose and validate a new quality measure especially tuned for imbalanced multi-label data.

Keywords: Knowledge discovery in databases, supervised rules discovery, subgroup discovery, exceptional model mining, monte carlo tree search, diversity, olfaction

9

  Benchmark datasets experimented on in the SD and EMM literature. . . . . . . . 10 Parameters of the artificial data generator. . . . . . . . . . . . . . . . . . . . . . . 11 The default parameters for each dataset. . . . . . . . . . . . . . . . . . . . . . . . 12 The list of strategies used to experiment with the RollOut method. . . . . . . . 13 The runtime and the maximum of the quality measure with SD-Map. . . . . . . . 14 Datasets used for the experiments. . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 3 :Figure 4 :

 34 Figure 3: A typical EMM instance.

Figure 5 :

 5 Figure 5: The lattice induced by Table2where A, B, C and D respectively correspond to the beers, the milk, the vegetable and the diapers. The value in the bottom of each node corresponds to the WRAcc measure of the itemset w.r.t. the male label.

Figure 6 :

 6 Figure 6: Illustration of the different SD search algorithms.

Figure 7 :

 7 Figure 7: Example of groups of molecules based on their odor (represented by the color).

1 Figure 9 :

 19 Figure 9: The FP-Tree of the transaction database in Table6with minSupp " 3.

Figure 3 :

 3 Figure 3: A typical EMM instance.

Problem 3 (Example 11 .

 311 The EMM problem). Given a multi-label dataset DpO, A, C, classq, a quality measure ϕ comparing two instances of a class model, a minimum support threshold minSupp and an integer k, EMM aims at extracting the top-k best frequent subgroups w.r.t. ϕ. The quality measure ϕ quantifies a deviation between the model induced by extpdq and O, respectively. Consider the multi-label dataset in Table

Figure 6 : 9 ≤ c ≤ 11 136 ≤ a ≤ 152 23 ≤ b ≤ 29 9 ≤ c ≤ 12 128 ≤ a ≤ 151 23 ≤ b ≤ 29 9 ≤ c ≤ 12 128 ≤ a ≤ 152 24 ≤ b ≤ 29 9 ≤ c ≤ 12 128 ≤ a ≤ 152 23 ≤ b ≤ 27 9 ≤ c ≤ 12 128 ≤ a ≤ 152 23 ≤ b ≤ 29 10 ≤ c ≤ 12 128 ≤ a ≤ 152 23 ≤ b ≤ 29 9 ≤ c ≤ 11

 69112391223912249122391223101223911 Figure 6: Illustration of the different SD search algorithms.

Figure 10 :

 10 Figure 10: The upper part of the search space for data of Table7.

Figure 13 :

 13 Figure 13: Search space as a lattice (left), DFS of the search space (middle), and the principles of the normalized exploration rate.

Figure 14 :

 14 Figure 14: Impact of the Select strategy.

1 )Figure 15 :

 115 Figure 15: Impact of the Expand strategy.

Figure 16 :

 16 Figure 16: Impact of the Roll-Out strategy.

1 )Figure 17 :

 117 Figure 17: Impact of the Memory strategy.

1 )Figure 18 :Figure 19 :

 11819 Figure 18: Impact of the Update strategy.

  nb_patterns (e) pattern_sup (f) nb_obj

Figure 20 :

 20 Figure 20: qualpH, Fq (Y-axis) for different datasets (X-axis)

Figure 21 :

 21 Figure 21: Comparing the diverstity after a beam search (Cortana) and mcts4dm

Figure 22 :

 22 Figure 22: The top-20 subgroups after filtering out the redundant subgroups for both beam search and mcts4dm.

Figure 23 :

 23 Figure 23: The runtime and the boxplots of the quality of the result set on the olfaction dataset with mcts4dm when varying the number of iterations.

Figure 3 :Figure 4 :Figure 24 :Figure 25 :

 342425 Figure 3: A typical EMM instance.

Figure 26 :

 26 Figure 26: The curves of βpsupppLqq.

Figure 7 :

 7 Figure 7: Necessity of an adaptive measure.

Figure 27 :

 27 Figure 27: Label distribution in the different datasets of Table14.

Figure 28 :

 28 Figure 28: Evolution of the quality of the result set of MCTS varying the number of iterations.

  (d)-(e)-(f)). However, on few datasets, the diversity on the target subspaces is almost the same, e.g., see Figure29(d)-(e)-(f) for Genbase.

Figure 29 :Figure 30 :

 2930 Figure 29: The quality measure and the support of the target subspace of the subgroups within result set obtained with MCTS using the Relative measures. The color of the points is the value of the quality measure of the subgroup given by the heatmap.

Figure 31 :

 31 Figure 31: Comparison between the measures on the extracted top-K. Evolution of the quality measure in the top-K.

  Figures 34(d)-(e)-(f) present another point of view to illustrate this behavior. The subgroups

Figure 32 :

 32 Figure 32: Comparison with a beam search on the Olfaction dataset. .

Figure 33 :

 33 Figure 33: The matrix of the similarity of the result set using different quality measures.

6. 3 Figure 25 :

 325 Figure 25: Olfaction data label distribution.

Figure 35 :

 35 Figure 35: The interaction view of the application. For each step of the beam search, the algorithm waits for the user's preferences (like/dislike). The subgroups are displayed into white boxes. On the right part, complementary information is displayed: Part of value domain of a chosen restriction on a descriptor, and parameters of the run.

  270.41sr´0.931 ď Hy ď ´0.621sr2.714 ď M LOGP ď 4.817sr384.96 ď SAtot ď 447.506sr0 ď nR07 ď 0sr0 ď ARR ď

Figure 36 :

 36 Figure 36: The rule combination that covers the musk odor.

6. 5 .Figure 37 :

 537 Figure 37: The support of three groups involving the camphor odor.

1

  Example of an olfactory dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Market basket data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Labeled version of Table 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 The contingency table of all the customers in Table 3. . . . . . . . . . . . . . . . 5 The contingency table of customers that purchased diapers and beers. . . . . . . .

6 A transaction database. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Toy dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Table 1 :

 1 Example of an olfactory dataset.

	ID	MW	nAT	nC	Odor
	1	150	21	11
	24	128	29	9
	48	136	24	10
	60	152	23	11
	82	151	27	12
	1633	142	27	10

Table 2 :

 2 Market basket data.

	TID	Products
	1
	2
	3
	4
	5
	6

Table 3 :

 3 Labeled version of Table2.

Table 4 :

 4 The contingency table of all the customers in Table3.

	+ 0	+ 30	+ 60
	0.17	0	0.33
	0.17	0.33	0

Table 5 :

 5 The contingency table of customers that purchased diapers and beers.

	+ 0	+ 30	+ 60
	0.33	0	0
	0	0.67	0

  • G. Bosc, J.-F.Boulicaut, C. Raïssi, M. Kaytoue: Découverte de sous-groupes avec les arbres de recherche de Monte Carlo. Fouille de motifs séquentiels pour l'élicitation de stratégies à partir de traces d'interactions entre agents en compétition. In Chantal Reynaud, Arnaud Martin, and René Quiniou, editors, 14èmes Journées Francophones Extraction et Gestion des Connaissances, EGC 2014, Rennes, France, 28-32 Janvier, 2014, volume E-26 of Revue des Nouvelles Technologies de l'Information, pages 359-370.

	In Fabien Gandon and Gilles Bisson, editors, 17èmes Journées Francophones Extraction et
	Gestion des Connaissances, EGC 2017, Grenoble, France, 23-37 Janvier, 2017, volume E-33
	of Revue des Nouvelles Technologies de l'Information, pages 273-284. Hermann-Editions,
	2017 [24].
	• V. Codocedo, G. Bosc, M. Kaytoue, J.-F. Boulicaut, A. Napoli:
	A Proposition for Sequence Mining Using Pattern Structures.
	In Karell Bertet, Daniel Borchmann, Peggy Cellier, and Sébastien Ferré, editors, Formal
	Concept Analysis -14th International Conference, ICFCA 2017, Rennes, France, June 13-
	16, 2017, Proceedings, volume 10308 of Lecture Notes in Computer Science, pages 106-121.
	Springer, 2017 [47].

• G. Bosc, J. Golebiowski, M. Bensafi, C. Robardet, M. Plantevit, J.-F.

Boulicaut

, M. Kaytoue: Local Subgroup Discovery for Eliciting and Understanding New Structure-Odor Relationships. In Toon Calders, Michelangelo Ceci, and Donato Malerba, editors, Discovery Science -19th International Conference, DS 2016, Bari, Italy, October 19-21, 2016, Proceedings, volume 9956 of Lecture Notes in Computer Science, pages 19-34. Springer, 2016 [25]. • G. Bosc, M. Plantevit, J.-F. Boulicaut, M. Bensafi, M. Kaytoue: h(odor): Interactive Discovery of Hypotheses on the Structure-Odor Relationship in Neuroscience. In Bettina Berendt, Björn Bringmann, Elisa Fromont, Gemma C. Garriga, Pauli Miettinen, Nikolaj Tatti, and Volker Tresp, editors, Machine Learning and Knowledge Discovery in Databases -European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part III, volume 9853 of Lecture Notes in Computer Science, pages 17-21. Springer, 2016 [29]. • G. Bosc, M. Kaytoue, M. Plantevit, F. De Marchi, M. Bensafi, J.-F. Boulicaut: Vers la découverte de modèles exceptionnels locaux : des règles descriptives liant les molécules à leurs odeurs. In Benoît Otjacques, Jérôme Darmont, and Thomas Tamisier, editors, 15èmes Journées Francophones Extraction et Gestion des Connaissances, EGC 2015, 27-30 Janvier 2015, Luxembourg, volume E-28 of Revue des Nouvelles Technologies de l'Information, pages 305-316. Hermann-Editions, 2015 [26]. • G. Bosc, P. Tan, J. F. Boulicaut, C. Raissi, M. Kaytoue: A Pattern Mining Approach to Study Strategy Balance in RTS Games. IEEE Transactions on Computational Intelligence and AI in Games 9(2), pages 123-132 [31]. • G. Bosc, M. Kaytoue, C. Raïssi, J.-F. Boulicaut, P. Tan: Mining Balanced Sequential Patterns in RTS Games. In Torsten Schaub, Gerhard Friedrich, and Barry O'Sullivan, editors, ECAI 2014 -21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic -Including Prestigious Applications of Intelligent Systems (PAIS 2014), volume 263 of Frontiers in Artificial Intelligence and Applications, pages 975-976. IOS Press, 2014 [28]. • G. Bosc, M. Kaytoue, C. Raïssi, J.-F. Boulicaut:

  Bosc, J.-F. Boulicaut, C. Raïssi, M. Kaytoue: Anytime Discovery of a Diverse Set of Patterns with Monte Carlo Tree Search. Data Mining and Knowledge Discovery Journal, 48 pages. Major revision, 2017[START_REF] Bosc | Any-time diverse subgroup discovery with monte carlo tree search[END_REF].

Table 6 :

 6 A transaction database.

	TID	items
	t 1	A B	D
	t 2	A	C D
	t 3	B	D
	t 4	B C
	t 5	B C
	t 6

Table 6 .

 6 This data contains 6 transactions identified by their TIDs tt 1 , t 2 , t 3 , t 4 , t 5 , t 6 u. We can suppose that each of these transactions is about the market basket of a customer. The set of items is I " tA, B, C, Du. They can be the products bought by the customers. For example, the transaction t 2 contains the items A, C and D, meaning that the second customer has purchased the products A, C and D. The extent of the pattern p " tB, Cu is extppq " tt 4 , t 5 , t 6 u since p Ď t 4 , p Ď t 5 and p Ď t 6 : There are only three customers that have purchased the products B and C together. Thus, its support is suppppq " 3. Given the minimum support threshold minSupp " 3, the set of frequent itemsets is tAu, tBu, tCu, tDu, tA, Du, tB, Cu and tB, Du.

Table 6 with

 6 minSupp " 3. The first step of the Apriori algorithm consists in finding the frequent 1-itemsets that are tAu, tBu, tCu and tDu. From these frequent 1-itemsets, we generate the candidates for the frequent 2itemsets: tA, Bu, tA, Cu, tA, Du, tB, Cu, tB, Du and tC, Du. For each of this candidate, we scan the database to check if they are frequent: Only tA, Du, tB, Cu and tB, Du are frequent. Then, we generate the candidates for the frequent 3-itemsets: Only tB, C, Du is generated but it is not frequent. The algorithm is stopped and the frequent patterns are tAu, tBu, tCu, tDu, tA, Du, tB, Cu and tB, Du.

Table 7 :

 7 Toy dataset

	ID	a	b	c	classp.q
	1	150 21 11	l 1
	2	128 29 9	l 2
	3	136 24 10	l 2
	4	152 23 11	l 3
	5	151 27 12	l 2
	6	142 27 10	l 1

Table 8 :

 8 The extension of the label dataset from Table7to the multi-label dataset version.

	ID	a	b	c	classp¨q
	1	150	21	11	tl 1 , l 3 u
	2	128	29	9	tl 2 u
	3	136	24	10	tl 2 , l 3 u
	4	152	23	11	tl 3 u
	5	151	27	12	tl

1 , l 2 u 6 142 27 10 tl 1 , l 2 u

  Algorithm 1 UCT: The popular MCTS algorithm.The constant C p can be adjusted to lower or increase the weigh of exploration in the trade-off exploration/exploitation. Note that when C p " 1 2 , this is UCB1. , denoted s exp , of the selected node s sel is added to the tree according to the available actions. The child s exp is randomly picked among all available children of s sel not yet expanded in the search tree.From this expanded node s exp , a simulation is played based on a specific policy. This simulation consists of exploring the search tree (playing a sequence of actions) from s exp until a terminal state is reached. It returns the reward ∆ of this terminal state: ∆ " 1 if the terminal state is a win, ∆ " 0 otherwise.

	2:	create root node s 0 for current state
	3: 4:	while within computational budget budget do s sel Ð Select(s 0 ) The Expand policy
	5: 6: 7: 8: 9: 10: end function s exp Ð Expand(s sel ) ∆ Ð RollOut(s exp ) Update(s exp , ∆) end while return the action that reaches the child s of s 0 with the highest Qpsq A new childThe RollOut policy
	11: function Select(s)
	12:	while s is non-terminal do
	13:	if s is not fully expanded then return s
	14:	else s Ð BestChild(s)
	15:	end if
	16:	end while
	17:	return s
	18: end function
	19: function Expand(s sel )
	20:	randomly choose s exp from non expanded children of s sel
	21:	add new child s exp to s sel
	22:	return s exp
	23: end function
	24: function RollOut(s)
	25:	∆ Ð 0
	26:	while s is non-terminal do
	27:	choose randomly a child s 1 of s
	28:	s Ð s 1
	29:	end while
	30:	return the reward of the terminal state s
	31: end function
	32: function Update(s, ∆)
	33:	while s is not null do
	34:	Qpsq Ð N psqˆQpsq`∆ N psq`1
	35:	N psq Ð N psq	`1
	36:	s Ð parent of s
	37:	end while
	38: end function
	39: function BestChild(s)
	40:	return	arg max

1: function Mcts(budget) s 1 P children of s U CBps, s 1 q 41: end function

Table 7 :

 7 Toy dataset Definition 5 (Label dataset). Let O, A and C be respectively a set of objects, a set of attributes, and a set of class labels. The domain of an attribute a P A is Dompaq where a is either nominal or numerical. Each object is associated to a class label from C through class : O Þ Ñ C.

	ID	a	b	c	classp.q
	1	150 21 11	l 1
	2	128 29 9	l 2
	3	136 24 10	l 2
	4	152 23 11	l 3
	5	151 27 12	l 2
	6	142 27 10	l 1

DpO, A, C, classq is a label dataset. Definition 6 (Subgroup). The description of a subgroup is given by d " xf 1 , . . . , f |A| y where each f i is a restriction on the value domain of the attribute a i P A. The description of a subgroup corresponds to the pattern in the pattern mining setting. A restriction is either a subset of a nominal attribute domain, or an interval contained in the domain of a numerical attribute. The description d covers a set of objects called the extent of the subgroup, denoted extpdq Ď O, and its support is the number of objects in its extent and is defined by supppdq " |extpdq|. Note that, in this thesis, we denote |S| the cardinality of the set S. For simplicity, a subgroup is either given by its intent, i.e., its description d, or by its extent extpdq.

Table 10 :

 10 Parameters of the artificial data generator.

	Name	Description	P small	P medium	P large
	nb_obj	Number of objects	2,000	20,000	50,000
	nb_attr	Number of attributes	5	5	25
	domain_size	Domain size per attribute	10	20	50
	nb_patterns	Number of hidden patterns	3	5	25
	pattern_sup	Support of each hidden pattern	100	100	100
	out_f actor	Proba. of a pattern labeled ´0.1	0.1	0.1
	noise_rate	Proba. of a object to be noisy	0.1	0.1	0.1

Table 11 :

 11 The default parameters for each dataset.

Table 8 :

 8 The extension of the label dataset from Table7to the multi-label dataset version.Example 18. Let us consider the multi-label dataset given in Table8. For the description d " xr128 ď a ď 151s, r23 ď b ď 29sy we can induce 7 different models, one for each subset of C, namely tl 1 u, tl 2 u, tl 3 u, tl 1 , l 2 u, tl 1 , l 3 u, tl 2 , l 3 u and tl 1 , l 2 , l 3 u. With the WRAcc measure: ϕpd, tl 1 uq "4

	ID	a	b	c	classp¨q
	1	150	21	11	tl 1 , l 3 u
	2	128	29	9	tl 2 u
	3	136	24	10	tl 2 , l 3 u
	4	152	23	11	tl 3 u
	5	151	27	12	tl 1 , l 2 u
	6	142	27	10	tl 1 , l 2 u

  Table 8 and the subgroup with description d " xr128 ď a ď 151s, r23 ď b ď 29sy. With L " tl 2 u, the model induced by d is F 1 pd, tl 2 uq " 1. The model induced by the entire dataset is F 1 pxy, tl 2 uq " 0.8. Thus, ϕpd, tl 2 uq " RF 1 pd, tl 2 uq "

	�(supp(L))
	1.4
	1.2
	1
	0.8
	0.6
	0.4
	0.2
	0	50 100 150 200 250 300 350 400

Table 14 :

 14 Datasets used for the experiments.

			|O|	|A|	Domain |C|	cardinality	density	distinct	mean	median
		CAL500	502	68	numeric 174 26	0.15 502	75.14	39
		emotions 593	72	numeric 6		1.8	0.31 27	184.67 170
		enron	1702 1001 nominal 53	3.3	0.06 753	108.49 26
		genbase	662	1186 nominal 27	1.2	0.04 32	30.70	17
		yeast	2417 103	numeric 14	4.2	0.30 198	731.5	659
		Olfaction 1689 82	numeric 74	2.882 0.04 1069 65.80	28
										beta
	0.00 1.00 0.75 0.50 0.25	5.0 CAL500 1 genbase	224.5 86	444.0 171	0 emotions 34 yeast	148 206 264 925 1816	1 enron 2 olfaction	457 286	913 570

  [START_REF] Abramson | Expected-outcome: A general model of static evaluation[END_REF] , RF β , W RAcc, W RF 1 and W RF β . Figures 29-30 display the results. We observe that, in general, RAcc and W RAcc covers few label subspaces compared to RF 1 , W RF 1 , RF β and W RF β . Indeed, in Olfaction, RAcc covers twice less label subspaces than the others (see Figure29

Cette thèse est accessible à l'adresse : http://theses.insa-lyon.fr/publication/2017LYSEI074/these.pdf © [G. Bosc], [2017], INSA Lyon, tous droits réservés

There is a strong inter-and intra-individual variability when individuals are asked about the quality of an odor. There are several explanations: Geographical and cultural origins, each individual repertory of qualities (linguistic), genetic differences (determining olfactory receptors), troubles such as anosmia (see[START_REF] Kaeppler | Odor classification: a review of factors influencing perceptionbased odor arrangements[END_REF][START_REF] Castro | Categorical dimensions of human odor descriptor space revealed by non-negative matrix factorization[END_REF]).

This collaboration is partially supported by the CNRS (Préfute PEPS FASCIDO and the project "Mission pour l'interdisciplinarité") and the Institut rhônalpin des systèmes complexes (IXXI).

The only solution to handle numerical attributes is either to enumerate all the possible intervals[START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF] or to use a discretization in pre-processing task or to use on-the-fly discretization during the enumeration[START_REF] Fayyad | Multi-interval discretization of continuous-valued attributes for classification learning[END_REF]. Note that most of existing works in SD/EMM (exhaustive methods included) employ a naive discretization as pre-processing task that converts numerical attributes into nominal one.

Constraint-based mining is closely related to the inductive database vision where we try to define knowledge discovery processes as sequences of queries[START_REF]Constraint-Based Mining and Inductive Databases[END_REF][START_REF] Dzeroski | Inductive Databases and Constraint-Based Data Mining[END_REF]

Note that the frequent part of the lattice (i.e., patterns that are frequent) is known as the iceberg lattice[START_REF] Stumme | Computing iceberg concept lattices with Titanic[END_REF].

We also worked on sequential pattern mining in the new context of electronic sports, in which an important challenge is to be able to detect game balance issues. For that, we presented an efficient pattern mining algorithm as a basic tool for game balance designers that enables one to search for imbalanced strategies in historical data through the KDD process. This work has been published, inter alia, in the international conference ECAI 2014[START_REF] Bosc | Mining balanced sequential patterns in RTS games[END_REF] and in the journal IEEE TCIAIG[START_REF] Bosc | A pattern mining approach to study strategy balance in RTS games[END_REF]. We do not detail this work in this dissertation. Interested readers may refer to the published papers available at https://hal.archives-ouvertes.fr/hal-01252728/document (IEEE TCIAIG) and https://hal.archives-ouvertes.fr/hal-01100933/document (ECAI 2014).

https://github.com/guillaume-bosc/MCTS4DM

http://datamining.liacs.nl/cortana.html

However, as part of our revision in the journal Data Mining and Knowledge Discovery, it will be done soon.

ˆp 2 4 ´3 6 q " 0, ϕpd, tl 2 uq " 0.22, ϕpd, tl 3 uq " ´0.17, ϕpd, tl 1 , l 2 uq " 0.11, ϕpd, tl 1 , l 3 uq " ´0.11, ϕpd, tl 2 , l 3 uq " 0.06 and ϕpd, tl 1 , l 2 , l 3 uq " 0. Thus the best model induced by the description d is obtained for the subset of labels tl 2 u.

Besides, note that the h(odor) application enables to save all the choices taken by the different users. Indeed, the application stores all the user's actions into log files. The goal here is to use these log files to learn user preferences, not only for a single run of the algorithm[START_REF] Dzyuba | Interactive learning of pattern rankings[END_REF] but for all experiments performed by the users. This kind data (choices made by experts) is hard to collect by simply asking experts and will be explored in future work.

Our collaborators are preparing a submission to PLOS One Computational Biology

Remerciements

search. All these quality measures focus on different subgroups and thus there is no equivalence between each other. Finally, as expected, the F β measure enables to foster the precision for over-represented labels and to support both recall and precision for other label subsets.