Agnès Braud
email: agnes.braud@unistra.fr

Xavier Dolques
email: xavier.dolques@laposte.net

Marianne Huchard
email: marianne.huchard@lirmm.fr

Florence Le Ber
email: florence.leber@engees.unistra.fr

Generalization effect of quantifiers in a classification based on Relational Concept Analysis

Keywords:

Relational Concept Analysis (RCA) has been designed to classify sets of objects described by attributes and relations between these objects. This is achieved by iterating on Formal Concept Analysis (FCA). It can be used to discover knowledge patterns and implication rules in multi-relational datasets. The classification output by RCA is a family of lattices whose graphical representation facilitates the analysis by an expert. However, RCA comes with specific complexity issues. It iterates on the building of interconnected concept lattices, so that each concept in a lattice might be the cause of generating other concepts in other lattices. In complex analyses, it relies on the successive choice of scaling operators which affects the size and the understandability of the results. These operators are based on a set of quantifiers which are studied in this paper: we indeed focus on the comparison of scaling quantifiers and highlight a generality relation between them. Our theoretical proposition is complemented by an experimental evaluation of the exploration space size, based on a real dataset upon watercourses. This work is intended for data analysts, to provide them with an overview on the different strategies offered by RCA.

Generality relation

Introduction

Many data are inherently relational, and several approaches have been implemented to explore such data [START_REF] Džeroski | Multi-relational data mining: an introduction[END_REF]. Among them, Relational Concept Analysis (RCA) is a descriptive approach based on Formal Concept Analysis (FCA) that both builds a classification (a lattice of formal concepts) for each category of objects contained in a dataset, and allows to obtain implication rules including relations between objects [START_REF] Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF][START_REF] Priss | Relational concept analysis: Semantic structures in dictionaries and lexical databases[END_REF]. RCA has been applied to multi-relational datasets from various domains, e.g. for analyzing the quality of watercourses [START_REF] Nica | Exploring temporal data using relational concept analysis -an application to hydroecology[END_REF],

for the fuzzy semantic annotation of web resources [START_REF] De Maio | Formal and relational concept analysis for fuzzy-based automatic semantic annotation[END_REF], or for the analysis and reengineering of software models [START_REF] Dolques | Fixing Generalization Defects in UML Use Case Diagrams[END_REF] or semantic wikis [START_REF] Shi | Mining for Reengineering: An Application to Semantic Wikis Using Formal and Relational Concept Analysis[END_REF].

RCA, as FCA, comes with a major challenge, linked to the fact that dealing with complex (relational, but also fuzzy, or multi-polar) data produces huge and complex results. Many methods have been proposed to reduce the lattice size, either by reducing the original data, e.g. by granular reduction [START_REF] Wu | Granular computing and knowledge reduction in formal contexts[END_REF] or by projection [START_REF] Singh | m-polar fuzzy graph representation of concept lattice[END_REF], or by reducing the number of concepts to be built, e.g., by thresholding [START_REF] Stumme | Efficient data mining based on formal concept analysis[END_REF], or by using AOC-posets [START_REF] Dolques | Performance-friendly rule extraction in large water data-sets with AOC posets and relational concept analysis[END_REF] -always trying to keep the principal results.

Another way is to help the user navigate within the results and select interesting concepts, based on various measures [START_REF] Buzmakov | Is Concept Stability a Measure for Pattern Selection?[END_REF][START_REF] Belohlavek | Selecting important concepts using weights[END_REF]. In RCA, the user is given the chance to orientate the search while it is running, so that a specific problem is to help him/her making the choice of the direction search. This is the question we focus on, which has received few attention until now.

We are indeed interested in providing experts with tools that can help deepening the understanding of the data and the analysis. Our experience has shown that RCA can be useful for knowledge extraction, and more precisely relational data exploration [START_REF] Dolques | Relational Concept Analysis for Relational Data Exploration[END_REF], even by a non computer scientist domain expert with little training. This comes from several features of RCA:

• lattices, which is the output of RCA, have a graphical representation as a Hasse diagram (see for example Fig. 2). Firstly, this graphical represen-tation facilitates the understanding of the relations between categories of objects. Secondly, this representation organizes relational concepts contained in the dataset in a way that helps the navigation between them when performing the analysis;

• the implication rules highlight existing correlations;

• the process is iterative, providing temporary interpretable results, thus allowing to tune the analysis during the process in case the expert realizes that it is interesting to orientate the analysis in one direction or another. RCA applies on a set of object-attribute relations that describe objects of a given type by a set of attributes, and object-object relations that represent the links between two categories of objects (possibly the same category). The main idea is to transform object-object relations into relational attributes thanks to so called scaling quantifiers. Scaling quantifiers are actually used to quantify a relation between a given object and a subset of objects (a concept extent) it is linked to through the given relation. The generated relational attributes can then be added to the initial object-attribute relation. The combination of a scaling quantifier, a relation, and a set of concepts is called a scaling operator and it is applied to a given object-attribute relation in order to extend it with new information.

The RCA process thus allows the user to make different choices at each step of the iterative process in order to focus the exploration of the data:

• the object-attribute relations or object-object relations to add or remove from the analysis;

• the object-object relations to transform so as to create new relational attributes;

• the corresponding scaling quantifiers (the scaling quantifier assigned to an object-object relation can be changed and several scaling quantifiers can even be assigned at one step to an object-object relation).

On the one hand, these choices enrich the process, allowing to perform a wider range of analyses. On the other hand, it may be difficult to decide which choice to make, and moreover results including relational information are more abundant and may be harder to understand for data analysts so that they may be lost in results, especially when the scaling quantifiers vary from one step to another. In a previous work, we have proposed an adaptation of RCA to explore relations in a guided way, by defining exploratory paths, allowing to increase the performance and the pertinence of the results [START_REF] Dolques | Relational Concept Analysis for Relational Data Exploration[END_REF].

In this paper, our purpose is to further improve the data exploration with RCA. We focus on theoretical aspects deepening the understanding of the RCA process. These results can be used to help the data analyst to understand the current outputs and to make choices for the next step, thus guiding her/him in its analysis. This research is also a theoretical basis for improving the navigation and visualization of RCA results (some tuning facilities are already integrated in the RCAexplore tool 1 ). More precisely, the aim of this paper is to compare the scaling quantifiers used in RCA, focusing on a generality relation between them. Variants of the scaling quantifiers (existential, universal and contains) are considered and their effects on RCA results are studied. The generality relation on scaling quantifiers is formalized and proved for the different quantifiers. The resulting hierarchy of quantifiers can then be used as a guide to help an analyst forecast the kind of results she/he will obtain. An illustrative example, and some numerical results are given on a dataset from the Fresqueau2 project.

The paper is organized as follows. Section 2 motivates the usage of formal concepts provided with their specialization partial order, gives the background of this work and the principles of RCA-based data exploration. Section 3 presents the core of our proposition. Section 4 describes experimental results on a real dataset upon watercourses. Related work is discussed in Section 5 and Section 6 concludes the paper with some perspectives.

Background

In this section, we motivate the use of formal concepts in knowledge discovery (Section 2.1), then we introduce the basics for Formal Concept Analysis (Section 2.2) and for Relational Concept Analysis (Section 2.3).

Formal concepts in knowledge discovery

In her paper in the 40th anniversary volume of Annual Review of Information Science and Technology [START_REF] Priss | Formal concept analysis in information science[END_REF], Uta Priss nicely introduces formal concepts as describing "a natural feature of information representation which is as fundamental to hierarchies and object/attribute structures as set theory or relational algebra are for relational databases". She explains that the notions of concept "extension" and concept "intension" are adapted from philosophy, and that "the basic FCA structures have been rediscovered over and over by different researchers and in different settings.", fostering the idea of its inherent universality. Roots of formal concepts and concept lattices were introduced in 1940 by G. Birkhoff [START_REF] Birkhoff | Lattice Theory[END_REF], and developed by M. Barbut and B. Monjardet [17] to cite just a few, and the FCA terminology and conceptual approach have been fully developed since 1982 following R. Wille [START_REF] Wille | Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts, Ordered Sets, Ivan Rival Ed[END_REF] vision.

Formal concepts help in forming object/attribute groups and building hierarchical structures on these groups, with strong mathematical properties, such as the duality of objects versus attributes or the canonicity of the building: for a given object set description, a unique concept lattice is built, contrarily to most approaches in conceptual clustering that are approximate. The hierarchical structure and the groups highlight many properties such as frequent patterns, attribute implications, mutual exclusion within attribute groups, or object similarities. Querying through concept lattices helps organize groups (concepts) of similar answers that can be navigated through the specialization structure [START_REF] Ferré | Reconciling expressivity and usability in information access -from filesystems to the semantic web[END_REF].

They also help in reformulating queries when the answer set is empty. All these qualities explain the spread of FCA in domains such as information retrieval [START_REF] Codocedo | Formal concept analysis and information retrieval -A survey[END_REF], recommendation systems [START_REF] Ignatov | Fca-based recommender models and data analysis for crowdsourcing platform witology[END_REF], or machine learning [START_REF] Kuznetsov | Learning of simple conceptual graphs from positive and negative examples[END_REF][START_REF] Kuznetsov | Machine learning and formal concept analysis[END_REF]. Furthermore, FCA emphasizes the visualization of concepts and their partial ordering which is meaningful for knowledge discovery and data exploration. When lattices are too complex, they are not fully displayed to the user. To give a few examples, in Credo [START_REF] Carpineto | Exploiting the potential of concept lattices for information retrieval with CREDO[END_REF], the lattices are displayed through a kind of explorer akin to file explorers, and the hierarchy can be expanded; in Carpineto and Romano [START_REF] Carpineto | ULYSSES: A lattice-based multiple interaction strategy retrieval interface[END_REF] fish-eye displays help to focus on specific parts; in [START_REF] Greene | Visualizing and exploring software version control repositories using interactive tag clouds over formal concept lattices[END_REF], smart tag clouds allow the expert to navigate into the lattice.

FCA can be applied to various forms of data, going from the simplest one (objects described by binary attributes) to more complex ones, including numerical data [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF], labeled graphs [START_REF] Kuznetsov | Learning closed sets of labeled graphs for chemical applications[END_REF], interval data [START_REF] Kaytoue-Uberall | Two complementary classification methods for designing a concept lattice from interval data[END_REF], hierarchical attributes [START_REF] Carpineto | Exploiting the potential of concept lattices for information retrieval with CREDO[END_REF], composite attributes [START_REF] Bertaux | Identifying Ecological Traits: A Concrete) FCA-Based Approach[END_REF], fuzzy data [START_REF] Belohlávek | Fuzzy galois connections[END_REF], multi-dimensional data [START_REF] Konecny | Triadic concept lattices in the framework of aggregation structures[END_REF][START_REF] Ignatov | Triadic formal concept analysis and triclustering: searching for optimal patterns[END_REF] or pattern structures [START_REF] Ganter | Pattern structures and their projections[END_REF]. Multi-relational data are taken into account within the RCA framework, which extends the purpose of FCA [START_REF] Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF][START_REF] Priss | Relational concept analysis: Semantic structures in dictionaries and lexical databases[END_REF].

The Uta Priss's web page3 gathers a number of FCA softwares, some of them being available online. There is a rich literature about algorithms as [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF], as well as analysis tools such as specific metrics dedicated to formal concepts relevance evaluation [START_REF] Kuznetsov | On interestingness measures of formal concepts[END_REF]. Thanks to its properties and available softwares, FCA has been used for applications in a wide range of domains, such as Software engineering [START_REF] Tilley | A survey of formal concept analysis support for software engineering activities[END_REF], Linguistics [START_REF] Osswald | Induction of Classifications from Linguistic Data[END_REF], chemical graphs [START_REF] Kuznetsov | Learning closed sets of labeled graphs for chemical applications[END_REF], water datasets [START_REF] Bertaux | Identifying Ecological Traits: A Concrete) FCA-Based Approach[END_REF], candidate CV exploration in recruitment [START_REF] Greene | Cvexplorer: identifying candidate developers by mining and exploring their open source contributions[END_REF], Organised Crime monitoring [START_REF] Domdouzis | A social media and crowdsourcing data mining system for crime prevention during and post-crisis situations[END_REF] or symbol recognition [START_REF] Guillas | A generic description of the concept lattices' classifier: Application to symbol recognition[END_REF].

Concept Lattices

Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] is based on lattice theory and can be used in particular to discover knowledge in data. This section begins by explaining the simplest form, which extracts an ordered set of concepts from a binary dataset, called an object-attribute context (or formal context), composed of objects described by attributes. An objectattribute context K is a 3-tuple (G, M, I), where G is an object set, M an attribute set, and I ⊆ G × M an object-attribute relation. Figure 1 (left-hand side) shows an object-attribute context K Ingredients = (G Ingredients , M Ingredients , I Ingredients ) which describes ingredients by their origin (e.g. vegetable, meat, etc.) or preparation form (e.g. sauce). Let C K be the set of all concepts built from K. Given two formal concepts

K Ingredients dairy vegetable meat sauce cream × × mozza × goatcheese × emmental × fourmeambert × onion × basilic × tomatosauce × × olive × mushroom × ham × chicken × bacon × CIngredients0
C 1 = (E 1 , I 1 ) and C 2 = (E 2 , I 2 ) of C K , the concept generalization order C is here defined by C 1 C C 2 if and only if E 2 ⊆ E 1 (and equivalently I 1 ⊆ I 2 ) 4 . C 1 C C 2 means that C 1 is more general than C 2 , or equivalently C 1 is a superconcept of C 2 , or C 2 is a subconcept of C 1 . The set C K , provided with
the generalization order is the concept lattice L K =(C K , C ) associated with K.

Besides, the fact that C 1 C C 2 is represented with C 1 above C 2 in the lattice diagrams.

Figure 1 (right-hand side) shows the concept lattice L 0 Ingredients associated with context K Ingredients (the 0 exponent will be explained later in the paper).

Let us notice that to simplify the notation, we will write L 0

Ingredients rather than L 0 KIngredients . As every attribute is top-down inherited, and every object is bottom-up inherited, the representation is usually simplified. It shows an attribute (resp. an object) only in the highest (resp. lowest) concept where it appears (this concept is the introducing concept). In Fig. 1, the vegetable attribute is introduced in CIngredients3 and is inherited by its subconcepts:

CIngredients5 and CIngredients2. Furthermore the cream object is introduced in CIngredients6 concept, and inherited by CIngredients6 superconcepts: CIngredients7, CIngredients1 and also CIngredients0.

Principles of Relational Concept Analysis (RCA)

Relational Concept Analysis [START_REF] Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF] has been introduced to extend the scope of FCA to multi-relational data encoded in a Relational Context Family (RCF). An RCF is composed of several categories of objects and relations between these objects, respectively described within object-attribute contexts and object-object contexts (also called relational contexts).

Definition 1 (Relational Context Family (RCF)). A Relational Context

Family is a (K, R) pair where: K = {K i } i=1,...,n is a set of K i = (G i , M i , I i ) object-attribute contexts. R = {r j } j=1,...,p is a set of r j relations where r j ⊆ G k × G l for some k, l ∈ {1, . . . , n}. In the following, for a given relation r j , its domain is denoted by dom(r j ) and its range is denoted by ran(r j ).

To illustrate RCA, we use the RCF presented in Tab. 1, composed of: three object-attribute contexts, K People , K Pizzas , and K Ingredients , corresponding to three categories of objects; two object-object contexts, r likes and r hastopping , that represent in extension the corresponding object-object relations and that show respectively which pizzas people like, and which ingredients are on top of pizzas. Let us note that K People and K Pizzas do not have any specific attribute, however for K Pizzas identity attributes have been created leading to a diagonal

× × × × × margherita × × × × threecheese × × × × fourcheese × × × × × furtrader × × × × × × × × × vege × × × × simple ×
table. This is because K Pizzas is the range of a relation, and we will explain later in this section the benefits of such a modeling for the RCA process.

To deal with relational data, RCA works by enriching object-attribute contexts with new attributes, called relational attributes. For each K objectattribute context, the idea is to capture in these attributes an additional information coming from the relations that have K as domain. For example, one could add in K People attributes about the kind of pizzas liked thanks to r likes object-object relation that has dom(r likes ) = K People .

More precisely, RCA transforms an object-object context r, that has K as domain, into new relational attributes in K quantifying the relation between objects of r and concepts formed on objects of ran(r). The type of quantification captured depends on the choice of scaling quantifier.

Definition 2 (Relational attribute). A relational attribute is an expression qr(C), where q ∈ Q is a scaling quantifier, r a specific relation, and C a specific concept whose extent contains objects from ran(r).

Q ⊇ {∃, ∃∀, ∃⊇} and other quantifiers will be introduced later (Section 2.5). The objective is to go beyond a simple description by attributes like "has-topping: mozza". For example, RCA allows to identify the group of dairy ingredients, then the group of pizzas that have at least one dairy ingredient, and finally, the group of people that like pizzas that have at least one dairy ingredient by composition of several object-object relations. In this example, "at least" is a kind of scaling quantifier (∃ quantifier). Other quantifiers would give attributes like "all ingredients are dairy ingredients" ("for all" quantifier: ∃∀) or "contains all the dairy ingredients" ("contains all" quantifier: ∃⊇). Let us note that in a more general version of RCA, several quantifiers could be applied to r and ρ(r) would denote a set of quantifiers associated with r.

Table 2 presents the result of the application of the existential scaling quantifier to relation r hastopping , using the concepts of L 0 Ingredients shown in Fig. 1. First columns correspond to the initial object-attribute context on pizzas, namely K Pizzas . The attributes of the last 8 columns are the obtained relational attributes, which encode relations between pizzas and groups of ingredients. Relational attribute ∃r hastopping (CIngredients1) is thus assigned to threecheese pizza because this pizza has at least one of the (dairy) ingredients grouped in concept CIngredients1. Figure 2 shows the corresponding lattice L 1

Pizzas . The pizzas classification initially showed only trivial (singleton) groups, each one corresponding to a pizza, because K Pizzas is a diagonal table. Thanks to the added relational attributes, the lattice now contains new relevant groups such as CPizzas9 which groups pizzas with at least one dairy ingredient (as we said, these ingredients are grouped in CIngredients1). Let us note that thanks to the diagonal of K Pizzas , single pizzas can be used in relational attributes based on relation r hastopping through singleton concepts, so that relational attributes can bring information related to a single pizza.

Extending an object-attribute context

Adding relational attributes to an object-attribute context is done through a scaling operation, based on a scaling quantifier. In order to provide a generic definition of this operation, a generic function κ is introduced which maps a scaling quantifier q, a relation r and an object subset in the range of r to an object subset from the domain of r.

κ : Q × R × i=1,...,n 2 Gi → i=1,...,n 2 Gi
κ returns the group of domain objects that are connected for r and q with a certain group of range objects. For example, κ(∃, r hastopping , {mozza, goatcheese, emmental , fourmeambert}) = {auvergne, margherita, threecheese, four cheese, furtrader }. The reader can check that every pizza of the image {auvergne, margherita, threecheese, fourcheese, furtrader } has at least one of the toppings of {mozza, goatcheese, emmental , fourmeambert}. More specifically, for r, q and a concept C, κ(r, q, C) is the set of objects that own the relational attribute qr(C). In our example, C is CIngredients1.

∃ hastopping(CIngredients1) ∃ hastopping(CIngredients2) ∃ hastopping(CIngredients3) ∃ hastopping(CIngredients4) ∃ hastopping(CIngredients5) ∃ hastopping(CIngredients6) ∃ hastopping(CIngredients7) auvergne × × × × × × × margherita × × × × × × threecheese × × × × × fourcheese × × × × × furtrader × × × × × × × × vege × × × × × simple × × × × ×
The generic notion of scaling operator, an operator that yields a relational extension of a context K k = (G k , M k , I k ) along a relation r, a scaling quantifier q and a concept set C l , can now be defined as follows.

K k = (G k , M k , I k ) and K l = (G l , M l , I l ) two object-attribute contexts, r ⊆ G k × G l a relation, C
l the set of concepts on K l , and q a scaling quantifier.

The scaling operator S (r,q),C l over K k yields the partial relational extension

S (r,q),C l (K k ) = (G + , M + , I + )
, where the elements are as follows:

G + = G k , M + = {q r(c) | c ∈ C l }, and
I + = c∈C l κ(q, r, E xtent(c)) × {q r(c)}.
The relational extension of an object-attribute context K k is obtained by extending it with all the partial relational extensions generated from the relations that have K k as a domain and their assigned scaling operator. Thus, let us consider an RCF that contains only the above-mentioned context K k , the context K l and relation r with dom(r) = K k and ran(r) = K l . The relational extension of K k when assigning quantifier q to r is the union of the initial and

derived contexts K k ∪ S (r,q),C l (K k ) = (G k , M k ∪ M + , I k ∪ I + ).
Table 2 shows the relational extension of context K Pizzas , when considering ρ(r hastopping ) = ∃ and the concept set of L 0 Ingredients lattice of Fig. 1. If an additional relation connecting pizzas to another kind of objects, for example, r servedin , connecting pizzas to restaurants, was in the dataset, then the relational extension of K Pizzas would also include the scaling upon r servedin .

The general case is defined as follows:

Definition 4 (Relational extension of a context K k = (G k , M k , I k )). Un- der Def. 3, let R k = {r j , 1 ≤ j ≤ p k |dom(r j ) = G k } be the set of relations with domain G k .
Let ρ be a mapping from R to Q which associates a scaling quantifier to each object-object relation r j . Let L be a set of concept lattices containing, for every r j ∈ R k , a lattice L ran(rj ) where the concepts group objects of the range of r j . The relational extension of context K k consists in apposing to K k the respective scaling upon each r j ∈ R k :

E ρ,L (K k ) = K k | S (r1,ρ(r1)),C ran(r 1 ) (K k ) | . . . | S (rp k ,ρ(rp k )),C ran(rp k ) (K k )
The relational extension of the whole K is composed of all the relational extensions of all K i in K.

Definition 5 (Relational extension of an RCF).

Under the previous definitions, the relational extension of K is:

E * ρ,L (K) = {E ρ,L (K 1 ), . . . , E ρ,L (K n )}
With the lattices built at the initial step (step 0), and with the mapping ρ = {(r likes , ∃∀), (r hastopping , ∃)}, the relational extension of K would be composed of the relational extensions of K People , K Pizzas and K Ingredients . The relational extension of K People is presented in Fig. 3 (bottom-left-hand side), with the corresponding lattice L 1 People on the right-hand side (exponent 1 stands for step 1). The relational extension of K Pizzas has been shown in Tab. 2. The relational extension of K Ingredients is simply K Ingredients , because there is no outgoing relation. At this step, there is no pizza groups; since everybody likes more than one pizza, the relational extension of K People obtained after the application of scaling operator S (r likes ,∃∀),C 0 Pizzas (C 0 Pizzas being the set of concepts corresponding to K Pizzas at step 0) has only empty columns except one, corresponding to ∃∀r likes (CPizzas0) (Fig. 3, bottom-left-hand side).

The whole construction process consists in building a finite sequence of contexts and concept lattices. The lattices at one step are used to calculate the relational extensions for the next step. The last sequence is obtained when the lattice family at one step is isomorphic to the one from the previous step and the extended contexts are unchanged (keeping the same scaling quantifier for a given relation). The variable L previous stores the concept lattices built at the previous step. Two external algorithms, not described here, compute respectively a concept lattice associated with a formal context (fca algorithm) and whether two concept lattices are isomorphic (isomorphic algorithm). The reader can easily find these algorithms in the literature [START_REF] Kuznetsov | Comparing Performance of Algorithms for Generating Concept Lattices[END_REF][START_REF] Haviv | On the Lattice Isomorphism Problem[END_REF].

Lines 10-11, each L is initialized with an empty concept lattice (represented by an empty set).

The instructions from lines 12-17 describe the RCA iterative process. First (Line 13), L previous keeps the current lattices before their modification. Then for every i, 1 ≤ i ≤ n, K[i] receives the relational extension computed with K i and the current concept lattices (Line 15). New lattices are built (Line 16), based on the current relational extensions. The algorithm stops when all the built lattices are the same at two successive steps. For efficiency purpose, due to its incremental monotonous nature, the algorithm can be implemented by updating at each step the lattices and the relational extensions, rather than computing them from scratch at lines 15-16.

L[i] ← ∅ 12: repeat 13: L previous ← L 14:
for i from 1 to n do 15:

K[i] ← E ρ,L previous (Ki) // Ki ∈ K 16: L[i] ← FCA(K[i]) 17: until ∀i ∈ {1, . . . , n}, isomorphic(L[i], L previous [i]) 18:
end Algorithm 1: RCA process, adapted from [START_REF] Hacene | Soundness and completeness of relational concept analysis[END_REF] The RCA process time complexity is detailed in [START_REF] Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF]. By using the worst-case complexity known for concept lattice building and adding the cost of the scaling operations, the time complexity is in O(n step * n cm * n om * (n am + n om )), where: n step is the step number (which is the least common multiple of the circuit lengths in the data model), n cm is the number of concepts in the largest lattice (in the whole process), n om is the number of objects in the largest extended context, n am is the number of objects in the largest context. that all the pizzas they like contain at least one individual from CIngredients1

(dairy ingredients).

Various Scaling Quantifiers

We define here some quantifiers that we have informally introduced in the previous section, and their variants: the existential quantifier ∃, the universal strict scaling quantifier ∃∀, the contains strict quantifier ∃⊇, a general containspercent quantifier ∃⊇ ≥n% and a general universal-percent quantifier ∃∀ ≥n% .

These last scaling quantifiers come in various levels, according to application needs, to quantify the strength of the link between objects from a set and objects from another set, or to handle noisy results. In the following definitions, we consider two object-attribute contexts K = (G, M, I) and K r = (G r , M r , I r ), and a relation r, where dom(r) = G, and ran(r

) = G r ; C r is the concept set built on K r , n a percent-value, n ∈ [0, 100]. For o ∈ G, the image set of o is denoted by r(o) = {o 2 ∈ G r |(o, o 2 ) ∈ r}.
Definition 6 (Existential scaling). For every object o ∈ G and every concept

C i ∈ C r , if r(o) ∩ E xtent(C i ) = ∅,

Exploring data with RCA

As explained above, RCA is designed for extracting knowledge patterns and classifications in data that conform to a model similar to a UML class diagram, given through a relational context family. For example, a data analyst may begin with a query pattern which assigns ∃ to r likes and ∃ to r hastopping . Let us recall that (non-trivial) ingredient concepts correspond to categories (dairy, vegetable, etc.). When the corresponding relational extensions are built, the obtained (non-trivial) pizza concepts are groups of pizzas that have at least one ingredient from a specific category; the obtained (non-trivial) people concepts are groups of people who like at least one pizza in a group that has at least one ingredient from a specific category. The concept lattices exhaustively give these people and pizza groups, in a classified way, that shows for example (see Fig. 2)

that having at least one meat ingredient (∃r hastopping (CIngredients4)) implies having at least one dairy ingredient (∃r hastopping (CIngredients1)); such knowledge is supported by the lattice generalization order on the concepts introducing the relational attributes (CPizzas9 C CPizzas12 in lattice L 1 Pizzas ). However, the data analyst may consider that the information obtained is not satisfactory and decide to use different quantifiers, but for that purpose it is useful to have an idea of the effect of such a change. Thus, when exploring data with RCA, a main problem is to choose the scaling quantifiers to use, and eventually to compare lattices built with different combinations of quantifiers.

We propose below a variation on the primitive RCA algorithm which aims to sketch the way the impact of the changes in the scaling quantifiers can be measured. It is presented in two parts. Algorithm 2 presents a skeleton of exploratory RCA. It includes at Line 21 an optional sub-algorithm (Algorithm 3) which allows the expert to measure the impact that different scaling quantifier selections would have in the next step, before choosing one. In Algorithm 2, Lines 16-19 consist in asking the expert to select the object-attribute contexts, the relations and the algorithms to build the conceptual structure (the concept lattice, the AOC-poset or an Iceberg concept lattice), that she/he finds appropriate for her/his analysis. Line 20 is used to memorize in IC previous the indices of the object-attribute contexts that have already been computed in one previous step and check the consistency of the chosen relations. Indeed, a constraint for selecting relations at Line 19 is that for any r ∈ SR, with r ⊆ O i × O j , the respective K i , K j are in SC and j ∈ IC previous , meaning that a conceptual structure (concept lattice, AOC-poset, Iceberg lattice) has been built in a previous step (which is not necessarily the immediately preceding step). Then Line 22, the expert selects a scaling quantifier for each selected relation. Lines 23-25, the relational extensions and the new conceptual structures are computed. Line 26 shows that the expert can stop at every step.

Algorithm 3 (SeeImpact) measures the impact of changes of scaling quan-

tifiers. It computes a table UncertaintyChanges. UncertaintyChanges[e][i]

is the difference between the concept number of lattice i at the preceding step for i ∈ I SC do 26:

K[i] ← E ρ,L previous (Ki) 27: L[i] ← ConceptStruct(K[i]) 28: until select STOP 29:
end Algorithm 2: RCA process adapted to exploration and measure impact of changes in scaling quantifiers, adapted from [START_REF] Hacene | Soundness and completeness of relational concept analysis[END_REF] and the concept number of lattice i at the current step using the set of scaling quantifiers of step e. Line 11, the expert selects a number of scaling quantifier alternatives he wants to analyze. Line 12-17, an alternative e is examined.

Then the relational extension and the conceptual structures are built (resp. Line for i ∈ I SC do 15:

K impact [e][i] ← E ρe,L previous (Ki) 16: L impact [e][i] ← ConceptStruct(K impact [e][i]) 17: UncertaintyChanges[e][i] = #Cpts(L impact [e][i]) -#Cpts(Lprevious[i]) 18:
Print UncertaintyChanges and metrics min, max, average, standard deviation for e varying on i 19: end Algorithm 3: Process for measuring the impact of different scaling quantifier selections ("Cpts" is a shortcut for Concepts)

These algorithms aim to give a support for the expert to measure the impact of the scaling quantifiers when RCA is conducted in an exploratory manner. This paper will now focus on understanding the foundations of the quantifiers behaviors and guiding the navigation.

Understanding quantifier generalization

In this section, we examine a generality relation between the previously introduced scaling quantifiers. We first define a generality relation A between relational attributes. The comparison of relational attributes can be defined on different relations and concepts as long as all relations have the same domain.

We first introduce the generality relation, and we illustrate it on an example restricted to one relation. Then we examine how this generality relation enlightens the relations between the lattices built with the different scaling operators.

The generality relation

Let us first define the generality relation on relational attributes.

Definition 11 (Generality relation

A on relational attributes). Let a 1 = q 1 r 1 (C 1 ) and a 2 = q 2 r 2 (C 2 ) be two relational attributes such that r 1 ⊆ G 3 × G 1 , r 2 ⊆ G 3 × G 2 , E xtent(C 1 ) ⊆ G 1 and E xtent(C 2 ) ⊆ G 2 : a 1 is more general than a 2 (written a 1 A a 2 ) if {a 2 } ⊆ {a 1 } .
The generality relation on scaling quantifiers can then be introduced as follows. A scaling quantifier q 1 is more general than a scaling quantifier q 2 , if the combination of q 1 with any relation r/concept C couple yields a relational attribute more general than with the other quantifier q 2 . Definition 12 (Generality relation S on scaling quantifiers). Let q 1 and q 2 be two scaling quantifiers; q 1 is more general than q 2 (written q 1 S q 2 ) if ∀r, ∀C, q 1 r(C) A q 2 r(C). Some generality relations can be observed between the previously defined scaling quantifiers as depicted by Fig. 5. We detail in the following these generality relations for the various scaling quantifiers.

Proposition 1. ∀n 1 , n 2 ∈ [0, 100[, ∃∀ ≥n1% S ∃∀ ≥n2% if n 1 ≤ n 2 .
Proof. Let r ⊆ G 1 × G 2 be an object-object relation, C a concept from the lattice built on the object-attribute context (G 2 , M 2 , I 2 ), a 1 = ∃∀ ≥n1% r(C), a 2 = ∃∀ ≥n2% r(C) with n 1 ≤ n 2 .

(o 2 ) ∩ E xtent(C)| = |E xtent(C)| then o 2 ∈ {∃⊇r(C)} . If |r(o 2 )| > 100|E xtent(C)| n1
then we have a counter-example for ∃∀ ≥n1% S ∃⊇ ≥n2% . we are able to build a counter-example for any combination of n 1 and n 2 , hence proving that the quantifiers are not comparable.

Illustration of the generality relation

In this section, we introduce an example to illustrate the generality relation presented in the previous section and the way its understanding may help exploring data. It is reduced to the observation of a single relation for which we can show several quantifier combinations. The example will follow the evolution of the extent of a concept introducing a relational attribute involving both this relation and the same target concept when using different scaling quantifiers.

For a given relation r, this corresponds to the task of an expert interested in knowing the group of objects of the r domain that are connected (in various ways determined by the scaling quantifiers) to a specific group of objects (concept) from the r range.

Table 3 shows an object-attribute context of dishes described by their main ingredient type (fish, meat, cheese) and an object-attribute context of wines described by their color, production area and flavor. Table 4 presents the matchesWith relation between dishes and wines, which is alternatively represented graphically in Fig. 6.

× × Gewurztraminer × × PinotGris × × Sylvaner × × Tokay × × Klevner × × × RomaneeConti × × × Mandourelle × × × Lestabel × × × Montrose × × × Bressades × × ×
Figure 7 presents the concept lattice of the object-attribute context of wines (Tab. 3 bottom). In this concept lattice, Concept_Wine_5 represents famous white wines produced in Alsace region (France). We will focus on relational attributes with that concept as target but based on different quantifiers, of the form qr matchesWith (Concept_Wine_5).

The observed scaling quantifiers are in Q = { ∃⊇=∃⊇ ≥100% , ∃⊇ ≥60% , ∃⊇ ≥30% , ∃∀=∃∀ ≥100% , ∃∀ ≥60% , ∃∀ ≥30% , ∃=∃⊇ ≥0% =∃∀ ≥0% } (see Fig. 5). Figure 8 shows 7 concepts, extracted from the 7 concept lattices built with the scaling opera- tors based on these 7 scaling quantifiers; each of these concepts introduces the relational attribute qr matchesWith (Concept_Wine_5). In the left branch of the • Concept_Dish_7 introduces ∃⊇r matchesWith (Concept_Wine_5); it represents the dishes that match with all Alsatian white wines.

FriedChicken × × × × Paella × × × × × BeefStew × × × Raclette × × × × × × × × OssoBucco × × SalmonPekan × × CodBrandade × × × × × × × × × × × CheeseSouffle × × × × × × × VealBlanquette × ×
• Concept_Dish_15 introduces ∃⊇ ≥60% r matchesWith (Concept_Wine_5); it represents the dishes that match with at least 60% of the Alsatian white wines.

• Concept_Dish_24 introduces ∃⊇ ≥30% r matchesWith (Concept_Wine_5); it represents the dishes that match with at least 30% of the Alsatian white wines.

• Concept_Dish_20 introduces ∃r matchesWith (Concept_Wine_5); it represents the dishes that match with at least one Alsatian white wine.

In the right branch of the diagram, going again from the top to the bottom (from specific to general quantifiers):

• Concept_Dish_6 introduces ∃∀r matchesWith (Concept_Wine_5); it represents the dishes that match only with Alsatian white wines.

• Concept_Dish_10 introduces ∃∀ ≥60% r matchesWith (Concept_Wine_5); it represents the dishes such that more than 60% of the matches are with Alsatian white wines.

• Concept_Dish_11 introduces ∃∀ ≥30% r matchesWith (Concept_Wine_5); it represents the dishes such that more than 30% of the matches are with Alsatian white wines.

In this diagram, the triangles indicate the dishes which are newly introduced by the concept compared to the upper (more specific) ones. It is easy to see the phenomenon of extent increase when going top-down, that is, from the use of a specific to a more general quantifier. Additionally, it can be seen that all extents are different which is the general case. In some special cases, two different qr(C),

for the same r and C, may be introduced in concepts with the same extent. The extent increase corresponds to constraint relaxing, for example when the user finds that the answer he obtained with a quantifier is too restricted and he accepts to use a different, more general, quantifier.

For example, a waiter may want to propose a set of dishes to a group of tourists in a restaurant in Strasbourg, which matches with all Alsatian white wines, in order to offer a large local wine choice. He would first apply quantifier ∃⊇. But the only dish which matches with all Alsatian white wines is

CodBrandade. Notice that CodBrandade matches also with some red and rosy wines (so that it is not in Concept_Dish_6), meaning that if one tourist does not like white wine, he can have a wine adapted to his dish. Thus the waiter could relax the constraint and use the quantifier ∃⊇ ≥60% , and obtain CodBrandade, P aella, and Raclette. This means that these dishes, even not matching with all the (same) Alsatian white wines, have great affinity with that type of wine.

The constraints may yet be relaxed by using ∃⊇ ≥30% or ∃. The same process can be done in the other generalization branch, but the interpretation is slightly different. If the waiter applies ∃∀, he will obtain dishes that match only with Alsatian white wines. This means an even greater affinity of the dish (here SalmonP ekan) to Alsatian white wines, thus no possibility to propose another wine to the tourist who does not like white wine. If this is too restrictive, the ∃∀ ≥60% quantifier will allow to propose dishes that match with many white wines and not many other types of wines, thus allowing to focus the choice for the tourist who does not like white wine.

The observed property about extent increase when generalizing a scaling quantifier is given below.

Property 1 (Extent inclusion based on generalization). For two relational attributes q g r(C) and q s r(C) with q g S q s , the extent of the concept introducing q g r(C) includes the extent of the concept introducing q s r(C).

This property enables us to compare the lattices obtained with two scaling quantifiers q g and q s such that q g S q s .

Impact of the generality relation on the concept lattices

Let us denote by L final K (q) the final concept lattice computed by RCA on object-attribute context K = (G, M, I) with quantifier q applied to relation r (with domain G). We have the following property that shows how concept lattices built using q g and q s can be compared. It is then exemplified based on Fig. 9 that shows the projection of L final Dish (∃∀ ≥60% ) to L final Dish (∃∀ ≥30% ).

Property 2 (Projection). Let us consider an RCF, an object-attribute context K = (G, M, I) of the considered RCF, and two scaling quantifiers q g and q s , with q g S q s . There is a mapping from concepts of L final K (q s ) to concepts of L final K (q g ) such that:

• A concept of L final K (q s ) which introduces a simple (non relational) attribute is mapped to the concept of L final K (q g ) which introduces the same simple attribute. The concept extents are the same. The concept intent may be different.

• A concept of L final K (q s ) which introduces a relational attribute q s r(C) is mapped in L final K (q g ) to the concept which introduces the relational attribute q g r(C). The concept extent may be larger for the concept introducing q g r(C).

• A concept C of L final K (q s ) with an empty simplified intent is mapped in

L final K (q g ) to the lowest concept which includes C extent.
Let us illustrate the different mappings and justify the property. For the first category of concepts of L final K (q s ), introducing no relational attribute, we have for example: Concept_Dish_2 of L final Dish (∃∀ ≥60% ) mapped to Concept_Dish_2 of L final Dish (∃∀ ≥30% ). Both introduce the attribute f ish. For this category, the set of objects that have the simple attribute cannot change. This is sufficient to establish the property.

For the second category of concepts of L final K (q s ), introducing a relational attribute q s r(C), we have for example: Concept_Dish_10 of L final Dish (∃∀ ≥60% ) mapped to Concept_Dish_11 of L final Dish (∃∀ ≥30% ). Concept_Dish_10 of L final Dish (∃∀ ≥60% ) introduces ∃∀ ≥60% matchesW ithConcept_Wine_5 and Concept_Dish_5 of L final Dish (∃∀ ≥30% ) introduces ∃∀ ≥30% matchesW ithConcept_Wine_5. In this category, due to the generality relation between relational attributes, the set of objects that have q s r(C) will also have q g r(C). Thus there will be a concept in L final K (q g ) introducing q g r(C) with an extent larger than the extent of the concept in L final K (q s ) which introduces q s r(C).

For the third concept category of L final K (q s ), an example is given by the mapping of Concept_Dish_9 of L final Dish (∃∀ ≥60% ) to Concept_Dish_2 of L final Dish (∃∀ ≥30% ). Concept_Dish_9 of L final Dish (∃∀ ≥60% ) extent is {Paella, SalmonPekan}, Concept_Dish_2 of L final Dish (∃∀ ≥30% ) extent is {Paella, CodBrandade, SalmonPekan}. In this case, the objects that are in the extent of the concept will have the inherited simple attributes and the inherited relational attributes of the form q s r(C). Then they will also inherit the relational attributes of the form q g r(C) in L final K (q g ). Thus they will continue sharing attributes in L final K (q g ) and there will be a concept in L final K (q g ) whose extent will contain them. This projection organizes the space in which a final user can move, by relaxing, or enforcing, or changing the constraints on the groups of objects. It also guides (and traces) the user to move between the concepts of the different concept lattices. The lattices are useful for exploring around a concept with the same scaling quantifier.

Implementation

The quantifiers presented in this paper have been implemented and tested in RCAExplore5 tool. It implements a modular version of RCA where core elements, such as concept generator algorithms and scaling operators, have several alternatives that can be controlled interactively by the user. RCAExplore has been developed in Java as part of the Fresqueau project to explore new ways for extracting knowledge from watercourses quality data. Some features of the tool have already been published. In [START_REF] Dolques | Relational Concept Analysis for Relational Data Exploration[END_REF] we present the interactive process and in [START_REF] Dolques | Performance-friendly rule extraction in large water data-sets with AOC posets and relational concept analysis[END_REF] we present the use of AOC-posets as an alternative to concept lattices.

AOC-posets have been introduced for several FCA applications. Given a concept lattice (C K , C ), its associated AOC-poset (for Attribute-Object-Concept poset) is the suborder restricted to the set of object-concepts (which introduce at least one object) and attribute-concepts (which introduce at least one attribute).

Lattice computation may have high complexity in time and space, as the size of the lattice may rise up to 2 min(|G|,|M |) concepts. The size of an AOC-poset is bounded by |G| + |M |. This significant size difference is observed in practice [START_REF] Dolques | Performance-friendly rule extraction in large water data-sets with AOC posets and relational concept analysis[END_REF][START_REF] Miralles | Class model normalization -outperforming formal concept analysis approaches with aoc-posets[END_REF]. Particular implication rules (implication rules having a premise containing one attribute) are extracted in the context of Fresqueau project in [START_REF] Dolques | Performance-friendly rule extraction in large water data-sets with AOC posets and relational concept analysis[END_REF],

on a variant of the dataset used in the current paper. AOC-posets and Iceberglattices are compared for this task, and the results highlight that, although RCA is impracticable when Iceberg-lattices are used, the use of AOC-posets makes RCA perfectly applicable in this case. In [START_REF] Miralles | Class model normalization -outperforming formal concept analysis approaches with aoc-posets[END_REF], with additional figures given in the companion presentation 6 , RCA enables to normalize UML class models in order to remove their redundancies and highlight relevant new abstractions. The method is applied to 15 UML class models corresponding to the successive versions of an information system on Pesticides and to 4 Java programs in the domain of human resource management. The models are true models coming from a public organism which works in the environment domain (IRSTEA7 ) and from industry (Berger Levrault8 ). The results show that there are no time computation problems and that the use of the AOC-posets makes the method practical for design experts (that have to analyze the extracted new abstractions) and far more efficient than with lattices.

Samples

Physicochemical parameters

Taxons

Life traits modalities values abundance affinity The AOC-poset is sufficient to recover the entire object-attribute context, and for several tasks, such as building non-redundant classifications or finding implication rules with premise composed of a single attribute. Note that Iceberg lattices can also be used in order to limit the exploration space, using threshold on concepts and thus losing more or less information [START_REF] Stumme | Efficient data mining based on formal concept analysis[END_REF][START_REF] Stumme | Computing iceberg concept lattices with Titanic[END_REF].

For illustration purpose, we rely on data collected during the Fresqueau project which aimed to study biological and physico-chemical parameters sampled in waterbodies, in order to assess and monitor the hydrobiologic quality of running waters [START_REF] Berrahou | A quality-aware spatial data warehouse for querying hydroecological data[END_REF]. Data were collected from various French databases such as the ones proposed by the Eau France portal 9 . In the following we consider a dataset dealing with taxons 10 , life traits which are taxon characteristics, physico-chemical parameters, and water samples. This dataset was used in the Based on this dataset, we study the link between the scaling quantifiers and the number of generated concepts, that represent the exploration space in which an expert moves during his/her analysis tasks. We compare the number attribute, while taxons are described by their taxon parents. The last column in these two tables indicates the generalization order on quantifiers as shown in Fig. 5.

The variations show the effect of scaling quantifiers on relaxing or reinforcing the constraints, and thus on expanding or reducing the data exploration space.

To simplify our illustration, we applied the same quantifier to all object-object relations, but of course, during an analysis, the object-object relations may be associated to different quantifiers that besides may change according to the analysis steps. Nevertheless, using the "extreme" combination of quantifiers (∃ versus ∃∀), our study shows the borders of the exploration space.

Related Work

Multi-relational data have been studied in the domain of Formal Concept Analysis from several perspectives. In the earliest approaches [START_REF] Liquière | Structural Machine Learning with Galois Lattice and Graphs[END_REF][START_REF] Prediger | The Lattice of Concept Graphs of a Relationally Scaled Context[END_REF][START_REF] Ganter | Pattern structures and their projections[END_REF], graphs connecting objects are classified, while in RCA, objects are classified depending on their relations to other objects. More recently, relational data have been dealt with logical concept analysis [START_REF] Ferré | Arbitrary Relations in Formal Concept Analysis and Logical Information Systems[END_REF]. The concepts' intents may then contain relational attributes such as (∃r.f ). Meta-relations are also built for navigating from a concept to another. But, contrarily to RCA, no iteration is performed. In [START_REF] Baader | A finite basis for the set of EL-implications holding in a finite model[END_REF], authors compute a basis of general concept inclusions in Description Logics EL gf p where cyclic concept definition has close connections with RCA. In [START_REF] Krmelova | Boolean Factor Analysis of Multi-Relational Data[END_REF],

they extract tuples of boolean factors from the various data tables. Several connection schemas can be applied that are similar to the scaling operators of RCA. Compared to RCA, the boolean factors are only a part of the formal concepts that can be built from the object-attribute tables, and the approach does not iterate and cannot propagate knowledge. In [START_REF] Kötters | Concept Lattices of a Relational Structure[END_REF], a Galois connection (and the derived concept lattice) is introduced to query sets of objects connected by relations. Only existential queries are expressed and there is no iteration, thus no possibility to progressively find the concepts. Ferré [START_REF] Ferré | A Proposal for Extending Formal Concept Analysis to Knowledge Graphs[END_REF] proposes an extension of FCA to knowledge graphs: in this framework, a context is a conceptual graph G with various relations and entities; a concept extent is a set of k-tuples of entities (k = 1, ...n) and the corresponding intension is a graph pattern, i.e. a generalized graph from G that is matched by the extent tuples. A family of lattices is built from G, with a lattice for each arity k. Kötters [START_REF] Kötters | Intension Graphs as Patterns over Power Context Families[END_REF] investigates the relations between power context families in PCF M and intension graphs in IG M , both based on the set of attribute sets M . He shows that the pattern structure ((G) n , IG n M , δ n ) where G is a set of objects (from a power context family), and δ n maps a n-uplet to a windowed intension graph, allows to build a lattice that corresponds to the lattice built from an RCA process.

Generalization is widely used in Machine Learning in order to efficiently search the space of possible solutions (hypotheses) [START_REF] Mitchell | Generalization as search[END_REF]. Besides, quantifiers are commonly used to query or extract knowledge from relational data. The Inductive Logic Programming (ILP) field is concerned with the development of methods for relational data mining [START_REF] Džeroski | Multi-relational data mining: an introduction[END_REF]. Methods that are based on logical formalisms use the existential quantifier. Nevertheless, the structuration of the search space in ILP while using both the existential and the universal quantifier has been studied theoretically in [START_REF] Goncalves | Handling Quantifiers in ILP[END_REF]. Our work has been inspired from this one, but while ILP quantifies variables, RCA quantifies relations. Aggregates and complex aggregates [START_REF] Vens | Refining aggregate conditions in relational learning[END_REF][START_REF] Charnay | Incremental construction of complex aggregates: Counting over a secondary table[END_REF]] also allow to perform quantification. They rely on aggregate functions (e.g., max , count) that can have some restrictions on the objects whose value is aggregated. Our definitions on generalization of scaling operators follow the idea of the one used for hypotheses in ILP [START_REF] Džeroski | Multi-relational data mining: an introduction[END_REF] and the one used for concepts in FCA. A set of quantifiers similar to the one of RCA has been introduced a long time ago in logic and linguistics as generalized quantifiers, and are studied in the field of databases to extend SQL [START_REF] Badia | Efficient implementation of generalized quantification in relational query languages[END_REF].

Many variants of FCA have been developped to deal with multivariate, interval or fuzzy or rough data [START_REF] Poelmans | Fuzzy and rough formal concept analysis: a survey[END_REF]. Similarly, variants of RCA could be developped to deal with e.g. fuzzy relational data, but as far as we know, no work has been done in this field. Links between FCA and rough sets (RS), when formulated between two universes, have been widely studied [START_REF] Yao | A comparative study of formal concept analysis and rough set theory in data analysis[END_REF][START_REF] Atif | Some relationships between fuzzy sets, mathematical morphology, rough sets, f-transforms, and formal concept analysis[END_REF]. Indeed, both theories attempt to formalize the notion of concept. In [START_REF] Yao | A comparative study of formal concept analysis and rough set theory in data analysis[END_REF], the operators of FCA and of RS are compared: the author states that the set X consists of necessary given relational attribute can be seen as an approximation of the extent of this concept. Besides, since RCA allows relations between G r and several objects sets, which are themselves linked, several nested approximations are built for E xtent(C i ). Furthermore, using various scaling quantifiers can be related to probabilistic rough sets [START_REF] Ma | Probabilistic rough set over two universes and rough entropy[END_REF] or the variable precision rough set model described in [START_REF] Shen | Variable precision rough set model over two universes and its properties[END_REF]. Finally, our aim is to analyse the effect of these scaling quantifiers in the RCA framework, where iterative algorithms allow to build explicit hierarchies of concepts from complex relation schemas, even with cycles.

RCA has been used for analysis and reengineering of UML elements, namely in class diagrams and in use case diagrams [START_REF] Dolques | Fixing Generalization Defects in UML Use Case Diagrams[END_REF]. In [START_REF] Moha | Refactorings of Design Defects Using Relational Concept Analysis[END_REF], RCA is used to exploit relations between methods and attributes to detect and fix design defects. It is used to learn model transformations in [START_REF] Saada | Generation of Operational Transformation Rules from Examples of Model Transformations[END_REF]. In [START_REF] Azmeh | Selection of Composable Web Services Driven by User Requirements[END_REF], relations between abstract tasks in an abstract orchestration are used to classify relevant Web services to instantiate the tasks. Other applications can be found in ontology engineering [START_REF] Bendaoud | Formal Concept Analysis: A unified framework for building and refining ontologies[END_REF][START_REF] Rouane-Hacene | Supporting Ontology Design through Large-Scale FCA-Based Ontology Restructuring[END_REF]. In [START_REF] Dolques | Relational Concept Analysis for Relational Data Exploration[END_REF], we proposed an adaptation of RCA to explore relations in a guided way in order to increase the performance and the pertinence of the results. A variant of RCA is used in [START_REF] Dolques | Performance-friendly rule extraction in large water data-sets with AOC posets and relational concept analysis[END_REF] for extracting rules from watercourse datasets. These applications show that RCA is useful for data analysis, and it is thus interesting to provide tools to better explain its functioning, especially when interacting with an analyst.

Conclusion

Relational data are rich of many information for data analysts. Among the possible ways to analyze such data, Relational Concept Analysis focuses on classifying objects of several categories taking into account their connections in an interdependent manner. It builds hierarchies of concepts, that are groups of objects (of the same category) similar with respect to their attributes and their relationships to other groups of objects (of another or the same category).

The relationships between objects and groups, or among groups, are captured by relational attributes that conform to specific scaling quantifiers. The choice of scaling quantifiers by the analyst determines the kind of knowledge patterns and classifications that are learnt from the dataset.

In this paper, we have compared the scaling operators according to a generality relation. Understanding this generality relation is a necessary step for helping the data analyst to forecast the kind of results she/he may obtain and to navigate between the multiple analysis possibilities. Based on a real dataset, we have shown that the possibility to use different scaling quantifiers is relevant for extracting various information levels. To summarize, our main contributions concern:

• A formal definition of all percent scaling quantifiers used in RCA.

• A generality relation between relational attributes in RCA, based on the derived relational attributes.

• An illustrative scenario which shows how the method can be used.

• An illustration on real data, showing the effect of the chosen quantifiers on the result size.

Furthermore, this theoretical exploration is a first step to a guide for the RCA user with quantifiers. Indeed, it provides a basis for visualization tools that show the lattices and their connections, or that highlight the analysis path (summaries of the choices that are made at each step).

As future work, we would like to study the generality relation between more complex sequences of scaling operators, and to analyze the case where data contain cycles. We also plan to enhance the existing software RCAExplore for exploiting these results on generalization in RCA. In particular we are developing an interface, in order to guide the experts in the choice of a scaling operator at each step of the RCA process in an interactive way. We plan to study how anticipating the effect of scaling quantifiers on the size of lattices can guide the analysis process of various datasets. We are also studying a possible combination between RCA and propositionalization approaches and will deepen the comparison between RCA, granularity computing, and rough sets.

Figure 1 :

 1 Figure 1: Object-attribute context K Ingredients , lattice L 0 Ingredients

Figure 2 : 2 Definition 3 (

 223 Figure 2: Lattice of pizzas at step 1 L 1Pizzas , built from Tab. 2

Figure 3 :

 3 Figure 3: Lattice L 0 People (top/left), lattice L 0 Pizzas (top/right), context resulting from the scaling operation S (r likes ,∃∀),C 0 Pizzas (K People ) (bottom/left), lattice L 1 People (bottom/right)

Figure 4 :

 4 Figure 4: Lattice of people (L 3 People ) (step 3 of RCA)

Definition 7 (

 7 then the relational attribute ∃r(C i ) is added to the attribute set of o. This operation is called existential scaling on K, C r and r.For example, ∃r hastopping (CIngredients1) from Tab. 2 is assigned to pizzas (objects from dom(r hastopping )) that have at least one of the dairy ingredients grouped in CIngredients1. Universal strict Scaling). For every object o ∈ G and every conceptC i ∈ C r , if r(o) = ∅ and r(o) ⊆ E xtent(C i ), then relational attribute ∃∀r(C i ) is added to the attributes of o.For example, in Fig.4relational attribute ∃∀r likes (CPizzas9) in the intent of concept CPeople2, indicates that objects (people) in the extent of this concept only like pizzas grouped in concept CPizzas9, namely pizzas that have at least one of the dairy ingredients (grouped in CIngredients1).Definition 8 (Contains strict Scaling). For every object o ∈ G and every conceptC i ∈ C r , if E xtent(C i ) = ∅ and E xtent(C i ) ⊆ r(o), then the relational attribute ∃⊇r(C i ) is added to the attributes of o.Definition 9 (Universal-Percent Scaling). For every object o ∈ G and every conceptC i ∈ C r , if more than n percent of r(o) is included in E xtent(C i ) (i.e. |r(o) ∩ E xtent(C i )| ≥ n|r(o)|/100), and |r(o) ∩ E xtent(C i )| > 0 then the relational attribute ∃∀ ≥n% r(C i ) is added to the attributes of o. Definition 10 (Contains-Percent Scaling). For every object o ∈ G and every concept C i ∈ C r , if more than n percent of E xtent(C i ) is included in r(o) (i.e. |r(o) ∩ E xtent(C i )| ≥ n|E xtent(C i )|/100), and |r(o) ∩ E xtent(C i )| > 0, then the relational attribute ∃⊇ ≥n% r(C i ) is added to the attributes of o.

1 : 19 :

 119 Algorithm RCA-explore 2: In: (K, R) an RCF 3: Out: L array [1, . . . , n] of lattices 4: Internal: K array [1, . . . , n] of contexts 5: Internal: L previous array [1, . . . , n] of lattices of the preceding step 6: Internal: IC previous indices of the object-attribute contexts that have already been computed in any previous step 7: Internal: SR set of object-object contexts selected by the user 8: Internal: SC set of object-attribute contexts selected by the user 9: Internal: I SC indices of object-attribute contexts selected by the user 10: Calls: ConceptStruct algorithm, which returns the chosen conceptual structure: the concept lattice, the AOC-poset or an Iceberg concept lattice associated with a context 11: Note: select is an expert action 12: ------13: begin 14: IC previous ← ∅ 15: for i from 1 to n do 16: select a subset SC ⊆ K of object-attribute contexts 20: select a subset SR ⊆ R of relations 21: select an algorithm ConceptStruct for each Ki ∈ SC 22: IC previous ← IC previous I SC 23: Call SeeImpact -Algorithm 3 24:select the scaling quantifier ρ(r) for each r ∈ SR 25:

  15 and Line 16), then UncertaintyChanges[e][i] can be computed.Line 18 shows results to the expert. 1: Algorithm SeeImpact 2: In: Variables of Algorithm RCA-explore Lines 2-25 3: Out: UncertaintyChanges array [1, . . . , np][1, . . . , n] of values indicating the difference between the concept number at the preceding step and at the current step using an alternative set of scaling quantifiers 4: Internal: np the selected number of alternatives that the expert wants to investigate 5: Internal: K impact array [1, . . . , np][1, . . . , n] of contexts 6: Internal: L impact array [1, . . . , np][1, . . . , n] of lattices 7: Calls: ConceptStruct algorithm, which returns the chosen conceptual structure: the concept lattice, the AOC-poset or an Iceberg concept lattice associated with a context 8: Note: select is an expert action 9: ------10: begin 11: select np a number of alternatives the expert wants to investigate 12: for e from 1 to np do 13:select the quantifier ρe(r) for each r ∈ SR 14:

Figure 5 :Proposition 3 .

 53 Figure 5: Generality relation on quantifiers (left), and illustration: relation r between object o and concept C extent, where C is a concept of a concept lattice on ran(r) (right)

+ 1

 1 By assigning |E xtent(C)| = 100 n2 and |r(o 2 )| = 100

Figure 6 :

 6 Figure 6: Graphical representation of matchesWith relation

Figure 7 :

 7 Figure 7: Concept lattices of wines built from object-attribute context in Tab. 3 (right-hand side)

Figure 8 :

 8 Figure 8: Concepts introducing the relational attribute q matchesWith(Concept_Wine_5) in the different lattices of Q = { ∃⊇, ∃⊇ ≥60% , ∃⊇ ≥30% , ∃∀, ∃∀ ≥60% , ∃∀ ≥30% , ∃}

Figure 9 :

 9 Figure 9: Projection of concept lattice of dishes with ∃∀ ≥60% (left) to the concept lattice of dishes with ∃∀ ≥30% (right)

Figure 10 :

 10 Figure 10: Relational schema used for experiments on the watercourse quality dataset

Fresqueau project to extract

  knowledge about physico-chemical values and their link to life traits modalities, e.g. finding the characteristics of taxons that live in water streams with a given physico-chemical quality. The water samples have been taken from monitoring stations at different dates between 2005 and 2009, that were considered representative by the biologists. The station names are anonymized. The dataset is available online 11 , it has been analyzed with the 2015 RCAexplore version 12 .

  properties of an object in X while X = {y ∈ M |∀x ∈ G(xIy ⇒ x ∈ X)} consists of sufficient properties, and an object of X has at least one property in the set X = {y ∈ M |∃x ∈ G (xIy ∧ x ∈ X)}. Object, resp. attribute oriented formal concepts can be defined by using both operators and . The set of pairs (X, Y ) where X = Y and Y = X , resp. X = Y and Y = X forms a lattice, as does the set of pairs (X, Y ) where Y = X and X = Y in the FCA framework. Furthermore using scaling quantifiers to build relational attributes between objects and a concept in RCA can be related to the theory of rough sets over two universes. More precisely, let us consider G and G r two object sets in a relational context family, and r the binary relation on G × G r . Then, the lower approximation of a concept extent E xtent(C i ) ⊆ G r is E xtent(C i ) = {o ∈ G : r(o) ⊆ E xtent(C i )}, that is all the objects of G having ∃∀r(C i ) as relational attribute; the upper approximation ofE xtent(C i ) is: E xtent(C i ) = {o ∈ G : r(o) ∩ E xtent(C i ) = ∅}, that is all the objects of G having ∃r(C i ) as relational attribute. Accordingly, the set of objects linked to a concept with a

Table 1 :

 1 RCF composed of people, pizza and ingredient categories, with object-object relations likes (or r likes ) and hastopping (or r hastopping )

	K P eople Arthur John	K P izzas	auvergneId	margheritaId	threecheeseId	fourcheeseId	furtraderId	vegeId	simpleId	K Ingredients cream mozza goatcheese emmental		dairy × × × ×	vegetable	meat	sauce ×
	Alice	auvergne	×							fourmeambert		×
	Juliet	margherita		×						onion				×
	Nancy	threecheese			×					basilic				×
	Ellen	fourcheese				×				tomatosauce			×	×
		furtrader					×			olive				×
		vege						×		mushroom				×
		simple							×	ham					×
										chicken				×
										bacon				×
				r likes	auvergne	margherita	threecheese	fourcheese	furtrader	vege	simple
				Arthur	×	×	×	×	×
				John				×	×
				Alice		×				×	×
				Juliet		×		×	×		×
				Nancy						×	×
				Ellen			×	×
		r hastopping	cream	mozza	goatcheese	emmental	fourmeambert	onion	basilic	tomatosauce	olive	mushroom	ham	chicken	bacon
		auvergne

Table 2 :

 2 Relational extension of K

	K Pizzas	auvergneId	margheritaId	threecheeseId	fourcheeseId	furtraderId	vegeId	simpleId	∃ hastopping(CIngredients0)

Pizzas : K Pizzas is concatenated with its derived context S (r hastopping ,∃),C Ingredients (K Pizzas ), based on the existential scaling of r hastopping

  Proposition 4. ∀n 1 , n 2 ∈ [0, 100[ the relational scaling quantifiers ∃∀ ≥n1% and ∃⊇ ≥n2% are not comparable according to S .Proof. According to definition 12 the quantifiers are not comparable if both ∃∀ ≥n1% S ∃⊇ ≥n2% and ∃⊇ ≥n2% S ∃∀ ≥n1% hold for at least one counterexample. Let us define an RCF where both properties are verified: G 1 is an object set from an object-attribute contextK 1 , o 1 , o 2 ∈ G 1 two objects, r ⊆ G 1 × G 2 arelation where G 2 is the object set of a context K 2 , and C a concept from the concept set C 2 of K 2 . 100 n2 then we have a counter-example for ∃⊇ ≥n2% S ∃∀ ≥n1% . If o 2 is such that |r

If o 1 is such that |r(o 1 )| = |r(o 1 ) ∩ E xtent(C)| = 1 then o 1 ∈ {∃∀r(C)} . If |E xtent(C)| >

Table 3 :

 3 Dish and Wine object-attribute contexts

	K Dish			fish	meat	cheese
	FriedChicken		×
	Paella			×
	BeefStew			×
	Raclette				×
	OssoBucco			×
	SalmonPekan	×
	CodBrandade	×
	CheeseSouffle			×
	VealBlanquette		×
	KWine	white	red	rosy	alsacian	burgundy	languedoc	flowery	fruity
	Riesling

Table 4 :

 4 matchesWith relation between dishes and wines

	r matchesWith	Riesling (Ri)	Gewurztraminer (G)	PinotGris (PG)	Sylvaner (S)	Tokay (T)	Klevner (K)	RomaneeConti (Ro)	Mandourelle (Ma)	Lestabel (L)	Montrose (Mo)	Bressades (B)

Table 5

 5 sums up the projections between concepts of L final Dish (∃∀ ≥60% ) (left column) and L final Dish (∃∀ ≥30% ) (right column).

Table 5 :

 5 Mapping from L final Dish (∃∀ ≥60% ) to L final Dish (∃∀ ≥30% )

	Concept number in L final Dish (∃∀ ≥60% ) Concept number in L final Dish (∃∀ ≥30% )
	Introducing a simple attribute
	2	2
	3	3
	1	1
	Introducing relational attributes
	4	4
	10	11
	8	12
	0	0
	Empty simplified intent
	9	2
	7	9
	5	5
	6	1

Table 7 :

 7 Size of the contexts and AOC-posets for Taxons and Water samples at step 3

			Taxons Water samples
		#objects	392	1702
		#attributes	392	0
		Taxons	Water samples Generalization
		#concepts	#concepts
	∃⊇	832			2005	↓
	∃⊇ ≥60%	832			2015	↓
	∃⊇ ≥30%	832			2071	↓
	∃	832			3742
	∃∀ ≥30%	368			2183	↑
	∃∀ ≥60%	293			2013	↑
	∃∀	293			2013	↑
	For high levels (level5)	Taxons	Water samples Generalization
		#concepts	#concepts
	∃⊇		288		731	↓
	∃⊇ ≥60%		288		733	↓
	∃⊇ ≥30%		288		812	↓
	∃		288		923
	∃∀ ≥30%		287		626	↑
	∃∀ ≥60%		252		270	↑
	∃∀		252		247	↑
	Then the second table shows the numbers of concepts obtained with different
	quantifier choices on the whole RCF. The highest numbers are obtained, as
	expected, for ∃ quantifier (resp. 832 taxon concepts and 3742 water sample
	concepts), and they decrease when more general quantifiers are used. Using
	∃⊇ and its percent versions, the numbers of concepts decrease until reaching
	respectively 832 for taxons and 2005 for water samples. Using ∃∀ and its percent
	versions, the numbers of concepts decrease until reaching respectively 293 for
	taxons and 2013 for stations.
	The third table shows the numbers of concepts obtained with different quan-
	tifier choices on the RCF restricted to the object-object relations corresponding
	to the highest value (5) for physico-chemical, abundance and affinity levels.
	The highest numbers are obtained, as expected, for ∃ quantifier (resp. 288

http://dolques.free.fr/rcaexplore/

http://engees-fresqueau.unistra.fr/presentation.php?lang=en

http://www.upriss.org.uk/fca/fcasoftware.html

We borrow the C notation for subsumption from Inductive Logic Programming.

http://dolques.free.fr/rcaexplore

http://www.lirmm.fr/ huchard/Documents/Papiers/miralles2015.pdf

http://www.irstea.fr/en/accueil

https://www.berger-levrault.fr/

http://www.eaufrance.fr

taxons represent animals or plants, at different levels as species, genuses or families

https://www.lirmm.fr/ huchard/Documents/Papiers/latticedataset-taxons-hierarchy.rcft

https://www.lirmm.fr/ huchard/Documents/Papiers/rcaexplore-20151012.jar

Acknowledgements.. This work was partially funded by ANR11_MONU14 and ONEMA. We warmly acknowledge Corinne Grac (UMR7362 LIVE -ENGEES) for advices about the dataset, and Amirouche Ouzerdine (Université de Montpellier) for preparing the dataset.

of generated concepts when using the various quantifiers.

The relational schema used to parameterize the experiments is presented in Fig. 10. Samples have been taken at various river sites and various dates.

Water samples are described by five object-object relations representing different levels of physico-chemical parameter values and five object-object relations representing different levels of abundance of taxons. Physico-chemical parameters can be magnesium, chloride, organic carbon, ... and are described (in an object-attribute relation) by several categories (metals, pesticides, ...). Taxons are described by their parents at different hierarchical levels, e.g. Acanthoceras has for parent Chaetocerotales and Coscinodiscophyceae (the direct parent of Chaetocerotales). Life traits are for example microhabitats, maximal sizes, reproduction modes, respiration modes, etc. Taxons are described by five object-object relations representing different levels of affinity with the life traits modalities, e.g. Acentrella has an affinity level 1 for the modality "tegument" and an affinity level 2 for the modality "gill" of trait "respiration modes".

In these experiments we use AOC-posets. Table 6 presents the size of the contexts and AOC-posets for physico-chemical parameters and life traits modalities at step 0 (they will not change in the following steps because they have no outgoing relations). The 40 physico-chemical parameters are described by their identity (40 attributes) and 12 classes (metals, pesticides, ...). The 116 life traits modalities are described only by their identity (the relation is a diagonal).