Sergei O Kuznetsov

Amedeo Napoli

Sebastian Rudolph

Lucas Bourneuf
email: lucas.bourneuf@inria.fr

Justine Reynaud

Yannick Toussaint

Christian Jäkel

Stefan E Schmidt

Tobias Gäbel-Hökenschnieder

Thorsten Pfeiffer
email: thorsten.b.pfeiffer@gmail.com

Three Approaches for Mining Definitions from Relational Data in the Web of Data

Keywords: Relational data, Formal Concept Analysis, Redescription mining, DBpedia Analogy, analogical reasoning, analogical proportion, analogy in lattices, formal concept analysis tolerance relation, formal concept analysis, direct product, factor analysis, rectangle cover, square cover Generalized metric, supermodular

Concept Analysis (see http://www.fca4ai.hse.ru/).

Invited Talk Inductive Reasoning with Conceptual Space Representations

Zied Bouraoui

Zied Bouraoui CRIL CNRS & Université Artois

Lens, France bouraoui@cril.univ-artois.fr Abstract. Structured knowledge is playing an increasingly important role in areas such as natural language processing and information retrieval. Such applications differ from the settings that have traditionally been considered in the field of knowledge representation, in that they require knowledge bases with a wide coverage, even if that means accepting some inaccuracies. In this talk, I will present some methods for knowledge base completion. At the center of this work are conceptual spaces, which are geometric representations of knowledge that were proposed by Gärdenfors (2000) as an intermediate representation level between symbolic and connectionist representations. In conceptual spaces, objects from a domain of interest are represented as points in a metric space, and concepts are modeled as convex regions. I will first present how to learn conceptual space representations from data, and then introduce some inductive reasoning techniques that use conceptual spaces together with an efficient Bayesian inference machinery that allows us to find plausible missing facts and rules from a given knowledge base.

An Answer Set Programming environment for high-level specification and visualization of FCA 1 Introduction

Large scale data production requires availability of high-level visualizations for their exploration. This is usually performed by building generic visualization models, that users may later use to explore their data. Thus, software environments oriented towards data mining use efficient implementations of data structures and their visualizations. For instance, in Formal Concept Analysis, LatViz is a lattice visualization software, allowing end-user to explore the lattice structure efficiently [1]. Lattice Miner builds and visualize Galois lattices and provides data mining tools to explore data [15]. FCA Tools Bundle consists in a web interface exposing multiple FCA-related tools for contexts and (ternary) concept lattices exploration [14]. In-Close algorithm reference implementation provides a concept trees visualization of contexts encoded in standard formats [3]. All these tools work with a formal model that provides an abstract view and a fixed search space on the data. Users cannot work on the model itself, they are expected to use the implemented methods, not to design new ones. In contrast, this paper introduces Biseau, a software focused on designing and exploring elements of the data structure, rather than the data itself. In this L. Bourneuf approach, data are only a support to the model validity, and the user's aim is the proper design of a general model. Biseau is a general purpose model builder that relies on graphs and logic languages.

Graphs are rendered in multiple ways, using field-specialized softwares like Cytoscape [21] in biology, graph-specific softwares (like LatViz for lattices), or more generalist like Tulip [4]. Another generic approach is dot, a graph description language specified by the graphviz software, which provides a gallery of visualization engines [6]. Dot is the internal graphical language used by Biseau (see Section 3).

Together with a graph data structure, Biseau offers a logical view of the associated exploration methods. A pure declarative language is used for this purpose, Answer Set Programming (ASP). It allows users to transcript the formal properties they are looking for in a straightforward way (see Section 2). ASP has already been applied to FCA to accomplish expressive query languages for formal contexts [12], later extended to n-adic FCA and improved with additional membership constraints, in order to handle large context exploration [20]. In our approach, ASP is also used for visualization.

Biseau is supplied with a graphical user interface and a command line interface to write an ASP encoding. Biseau uses this encoding as a script to generate the dot files and the resulting visualizations. The main interest of Biseau is therefore to build graph visualizations directly from formal relations. Biseau is not only dedicated to lattices, and their (efficient or scalable) exploration. It provides instead a general purpose programming environment that is able to visualize any ordered structure. Biseau is therefore suited for rapid design and easy testing of works or extensions in the framework of FCA. It is freely available under the GNU/GPL license 1 .

The structure of this paper is as follows. Sections 2 and 3 quickly present the ASP and dot languages used by Biseau. Section 4 explains how Biseau takes advantage of these languages to allow the user to build models. Section 5 proposes as a case study the reconstruction of the Galois lattice. Section 6 shows how Biseau can easily handle some of the FCA extensions typically used in FCA applications as knowledge processing [19]. Finally the paper concludes by some insights about Biseau interest when used in FCA and in artificial intelligence.

Answer Set Programming

The following presentation of ASP is taken from [5]. For an in-depth dive into the language, the reader is redirected to [8].

ASP is a form of purely declarative programming oriented towards the resolution of combinatorial problems [17]. It has been successfully used for knowledge representation, problem solving, automated reasoning, and search and optimization. Unlike Prolog, ASP handles cross-references of rules, enabling the writing of code much closer to the specification. In the sequel, we rely on the input language of the ASP system Potassco (Potsdam Answer Set Solving Collection [8]) Fig. 1: ASP program encoding the context in Table 1, in the form of rel/2 relations between objects and attributes. The last line yield links/2 atoms that are compiled by Biseau as edges in the output dot file.

L. Bourneuf

We used the Potassco system [9] that proposes an efficient implementation of ASP. ASP processing implies two steps, grounding and solving. The grounder generates a propositional program replacing variables by their possible values. The solver is in charge of producing the stable models (answer sets) of the propositional program. Of course, a dedicated algorithm for a specific problem will be generally more efficient than its equivalent compact ASP encoding. However, ASP systems are useful for the design of prototypes. It is an attractive alternative to standard imperative languages that enable fast developments.

adult child female male boy woman man alice

× bob × × × eve × × × john × × ×
Table 1: Formal context of human relations.

Graph Drawing With Dot

Dot is a graph description language, allowing one to generate a graph visualization from the definition of its content [6]. Dot enables the control of precise visual properties, such as node and edge labelling, position, shape, or color. For instance, the dot line woman [color="blue"] will color in blue the node labelled woman. The full language is defined by the graphviz graph visualization software, which provides multiple engines to interpret and compile dot encoded files to other formats, including images. Figure 2 shows an example of a working dot description, which given to a graphviz engine yields the visualization in Figure 3.

Digraph biseau_graph {

node [penwidth="0.4" width="0.1"];

edge [penwidth="0.4" arrowhead="none"]; john->boy; john->male; john->child; eve->female; eve->woman; eve->adult; bob->man; bob->adult; bob->male; alice->female; } Fig. 2: Dot encoding of the graph in Figure 3.

An ASP environment for high-level specification and visualization of FCA Fig. 3: Visualization of the relations described by context in Table 1.

From ASP to Dot With Biseau

Biseau allows the user to write some ASP encoding and retrieve in real-time the corresponding graph visualization. To achieve this, it implements an ASP to dot compiler and a Graphical User Interface that helps writing the ASP encoding and that performs automatically all necessary compilations. As explained in Section 2, a given ASP encoding yields stable models consisting of true facts, which can be represented by atoms like link(woman,human). For each stable models found from the ASP user encoding, Biseau will convert atoms into dot lines. For instance, the ASP atom link(woman,human) will translate to woman -> human in the dot output. This controlled vocabulary will be only partially explored in Section 5, but note that it maps the full dot language, including colors, shapes, and general graph options. A complete documentation is available online 2 .

Because of the use of ASP to yield the dot description, the graph is therefore defined in intension: instead of describing manually all objects and properties, the user specify their definitions, and let the ASP solver infers all necessary relations. More generally, Biseau internal process can be seen as a compilation from ASP models to dot, then from dot to image (the last one being delegated to graphviz software, as seen in Section 3). As a matter of example, the ASP encoding in Figure 1 will be compiled to the dot description in Figure 2, itself compiled to the image in Figure 3. If the ASP expression color(A,blue):-rel(_,A). was added to the ASP encoding in Figure 1, the final figure would show in blue all attributes nodes. The reader familiar with software engineering may recognize the use of ASP as a metamodel, and dot as the model.

Biseau can be extented with scripts, units of ASP (or Python) code to add to (or run on) the user encoding. They may expose some options to tune their behavior. Moreover, user can implement and add its own scripts to Biseau, allowing him (and others he shares with) to encapsulate ASP or Python programs that behave accordingly to their preferences. Biseau is shipped with scripts related to FCA, for data extraction from standard format like SLF or CXT, concept mining or lattice visualization (as shown in Section 5).

L. Bourneuf

Build and Visualize Galois Lattices With Biseau

This section shows how to build FCA basic mathematical relations in order to get a visualization of the Galois lattice in Biseau. The context in Table 1 will be used as case study, encoded in ASP using rel/2 atoms as shown in the first five lines of Figure 1.

Mining the Formal Concepts

In a formal context defined by objects O, attributes A, and the binary relation R ⊆ O × A, a formal concept is a pair (X, Y ), such as:

X = {y ∈ Y |(x, y) ∈ R ∀x ∈ X} (1)
Y = {x ∈ X |(x, y) ∈ R ∀y ∈ Y } (2)
Where X ⊆ O and Y ⊆ A. The search for formal concepts in ASP can be expressed like in the above definition:

ext(X):-rel(X,_) ; rel(X,Y): int(Y). int(Y):-rel(_,Y) ; rel(X,Y): ext(X).

rel(X,_) fixes variable X as the first term of a relation, i.e. an object. Notation rel(X,Y): int(Y) ensure that there is a relation between X and all attributes of the intent. As a consequence, ext(X), the extent, holds for all objects in relation with all attributes of the intent. The second rule is a symmetric definition for the concept's intent. For those familiar to Prolog, note that such a program would lead to an infinite loop. The treatment of loops is a nice feature of ASP that gives access to a fixed-point semantics. ASP search comes with the guarantee that all minimal fixed points will be enumerated. Therefore, each answer set is a different concept, or the supremum or infimum (where extent or intent are empty sets). To avoid the yield of supremum (infimum), one may include a constraint specifying that extent (intent) must include at least one element.

These models/concepts can be aggregated in order to produce an encoding containing ext/2 (and int/2) atoms, where ext(N,A) (int(N,A)) gives an element of N-th concept's extent (intent). This numbering is arbitrary and serves no other purpose than identifying the different concepts.

Galois lattice

A Galois lattice is defined by the partial order on the concepts, i.e. a graph with concepts as nodes, and an edge between a concept and its successors in the ordering:

% Shortcut to infimum, supremum and concepts identifiers. c(N):-ext(N,_). c(N):-int(N,_). % Ordering of two concepts: the first has all objects of the second. Fig. 4: Visualization of the Galois Lattice of context in Table 1 using Biseau, with extent and intent shown for each node/concept. Fig. 5: Visualization of the Galois Lattice of context in Table 1 using Biseau, with reduced labelling.

Object and Property Oriented Concept Lattices

Following definitions from [23], it is also possible to encode the mining of object oriented concepts (X, Y ) defined by X = Y ♦ and Y = X , such as:

Y ♦ = y∈Y Ry X = {y ∈ A|Ry ⊆ X}
With Ry = {x ∈ O|(x, y) ∈ R}.

% Any object linked to an attribute in the intent is in the extent . ext(X):-rel(X,Y) ; int(Y). % Objects in the complementary set of the extent. not_ext(Nx):-rel(Nx,_) ; not ext(Nx). % The intent is made of attributes exclusively linked to objects of the extent . int(Y):-rel(_,Y) ; not rel(Nx,Y): not_ext(Nx).

The code for property-oriented concepts is similar, and both replace the encoding in section 5.1.

Iceberg Lattices

The iceberg lattice, loosely defined as the Galois lattice stripped of all concepts with a too small support (i.e. number of objects in their extents) [22], can be built by discarding any model containing too few objects in his extent. For instance, the Figure 3 of [22], reproduced in this paper in Figure 6, shows the iceberg lattice of the running example MUSHROOMS database of nbobj objects with a minimal support of minsupp%. It can be reproduced by discarding models using a constraint: This constraint can be generated by Biseau knowing the number of objects and the minimal support.

n-adic FCA

n-adic FCA [16] can be encoded the same way as regular FCA, by extending the number of parameters for rel atoms. For instance, in triadic FCA, conditions are given as the third argument of rel/3 atoms, such as rel(O,A,C) is true when the relation between object O, attribute A and condition C holds. Triadic concepts can thus be generated using the following encoding: ext(X):-rel(X,_,_) ; rel(X,A,C): int(A), cnd(C). int(X):-rel(_,X,_) ; rel(O,X,C): ext(O), cnd(C). cnd(X):-rel(_,_,X) ; rel(O,A,X): ext(O), int(A).

Pattern Structures

As introduced in [7], a pattern structure is a generalization of FCA applied on attributes structured in semi-lattices. Pattern concepts are pairs of objects and lattices, producing the expected pattern lattice. This technics have been applied to gene expression data [13]. Here, we reproduce the pattern lattice construction for an example of non-binary data from the same publication: The use of the meta-programming directives #min and #max allows us to retrieve the minimal and maximal value associated to the extent. Therefore, interval(C,Min,Max) stands for the minimal and maximal values on condition C, e.g. 5 and 6 for condition 1 when extent is {1, 2, 5}. Unlike the concept model seen in Section 5.1, this model relies on an explicit choice rule for the extent with subsequent constraints to ensure its maximality. Line 2 generates an answer set for each element of the power set of the object set. Following lines will discard answer sets that are not infinum, supremum or concept. Line 4 associate for each condition the minimal and maximal values over the extent. Line 7 selects an object and a condition such as they are associated to a value in the interval. Line 9 selects all objects that are valid for all conditions, and line 11 ensure that they belong to the extent.

The code in section 5.2 can be reused without modifications to produce and show the resulting pattern lattice.

Discussion & Conclusion

Using the ASP language in the Biseau environment, some well-known FCA structures (Galois, object-oriented, iceberg, integer pattern lattices) have been reconstructed. The main contribution of Biseau lies into the straightforward use of the structure specifications to produce a simple code and a proper visualization. To achieve that feat, Biseau is compiling a controlled subset of ASP atoms to dot lines, effectively building a dot formatted file that is compiled to an image by graphviz software. By letting the user manipulate the visualization with the full power of ASP, Biseau enables definition of graphs in intension. This gives an abstract access to dot expressions and lets the user focus on the fast prototyping of data exploration and the elaboration of mathematical properties. In other words, Biseau allows user to work on the model in which data are processed, instead of providing an implementation of a single model to be used on particular data, as usually performed in field-specialized softwares.

ASP limits lies into the absence of float numbers handling, and scaling problems inherited from the total grounding of data before solving. However, Potassco

An ASP environment for high-level specification and visualization of FCA system users may benefit from several extensions of the language like linear programming [18] or propagators [10], allowing one to take advantage of other programming paradigms, or improving performances by an iterative replacement of bottlenecks by dedicated algorithms. For instance, the standard concept mining can be replaced by an implementation of the in-close algorithm [2].

Biseau current state is a very simple proof of concept, and therefore miss a lot of features typically found in Integrated Development Environments, that could help user to write, understand and debug produced ASP code.

Future work will focus on the Biseau generalization : other languages like GML allow to describe graphs, some are field-specific, and some enable outsourcing of the visualization to other (field-)specialized softwares. Future development of Biseau could provide support for ASP advanced features, and embedding of more scripts for FCA and its extensions.

Introduction

In this work, we are interested in checking the completeness and the quality of RDF data in the linked open data (LOD), and the potential to discover definitions from these sets of linked data. Such definitions can be reused in the design of Knowledge Bases (KBs). This challenge is of main importance when we consider the masses of data which are currently published in LOD.

At an abstract level, we can view the current problem as follows. We have at hand a set of interconnected objects -objects connected by relations-just as an ABox in a description logics (DL) framework [2], and the objective is to classify the objects with respect to and in compliance with the connections they are involved in. Objects are classified in the same class, actually an extension, as soon as they share common elements. This sharing can be strict -elements are the same-or soft -elements are similar. Finally, we obtain a set of classes, possibly partially ordered, and their associated descriptions. These descriptions are important if not mandatory as they are a basis for building the definitions of classes. Definitions are considered as sets of necessary (NC) and sufficient conditions (SC) used for classifying new objects. If x is an instance of class Red then x has color red (NC), and conversely, if x has color red then x is an instance of class Red (SC).

Continuing the analogy with DLs, the idea in this paper is to build and apply induction rules having the form: r(x, y) and y : C then x : ∃r.C. This means that given a relation such as r(x, y) between objects x and y, with y instance of class C, then we infer that x is an instance of a class say D whose description includes the expression ∃r.C, i.e. instances of D are related to instance(s) of C.

In this work, we aim to build definitions from RDF data. To this end, we use three approaches including Formal Concept Analysis (FCA), redescription mining and translation rule discovery. Then the main operations that we should perform are (i) the preparation of the data, (ii) the discovery of definitions, (iii) the evaluation of the quality of definitions. To compare the three algorithms, we run experiments on data extracted from DBpedia. This paper is in continuation of a line of research work on the discovery of definitions within RDF triples in the linked open data. The originality in this paper is to compare three approaches which are not based on the same principles but which can complement each other. Moreover, to the best of our knowledge, this is one of the first papers where such a study and comparison is drawn at a theoretical and practical level.

The paper is organized as follows. In the second section, we present the data on which we will be working and the basis of the classification process in the linked open data. The third section details the three classification approaches and their application. The following section is related to the experiments which have been carried out for evaluating the three approaches. Finally, a discussion, related and future work conclude the paper.

Data representation

In this section, we present basics of linked open data, and how we represent RDF triples as a formal context.

Linked Open Data

Linked open data (LOD) are relational data that can be seen as a set of interconnected knowledge bases (KB). A KB relies on two main components, a TBox which defines the schema of the KB and includes the concept definitions and the ABox which introduces individuals and the expressions in which individuals are involved. The basic units in a KB are RDF triples s, p, o , which encode subjectpredicate-object assertions. The elements of a triple can be a resource uniquely identified, a literal (values like strings, dates or integers) or a blank node (existential quantifier). For the sake of simplicity, in this paper we consider that s, p, o ∈ U × U × U , where U is the set of all identified resources. Resources can refer to any object or abstraction and are identified by a URI (Uniform Resource Identifier). A URI is an address that is composed of two parts. The first part is the namespace, which indicates from which KB the resource comes from. The LOD can be queried thanks to SPARQL queries. For example, the query SELECT ?x WHERE {?x rdf:type ex:C 0 } returns all the instances of C 0 . Considering the example in Figure 1b, only ex : x 0 is returned.

Formal Concept Analysis and RDF data

We rely on Formal Concept Analysis (FCA) from [6] . . e n , where the e i is an expression of the form ∃r.x. To this end, we are searching for two sets of attributes C ⊆ M C and D ⊆ M D such that their derivations are the same (C = D ). For example, in Figure 1, we have {C 0 } = x 0 and {∃r 1 :x 1 , ∃r 2 :x 2 } = x 0 . Thus, the definition C 0 ≡ ∃r 1 :x 1 ∃r 2 :x 2 can be constructed. Since data may be incomplete, it is possible that there is no equality between the derivations of a class and the derivation of its description, i.e.

{C i } = {∃r : x j } . Therefore, we need to find some kind of approximation. This is allowed by the three algorithms presented in next section.

Rule mining algorithms

In this section, we briefly present the three approaches we are interested in, namely association rule mining, redescription mining and translation rule mining. Interested reader may refer to the original publications for further explanations.

Association rules

The goal of association rule mining [7] is to find dependencies between attributes. An association rule between two sets of attributes A and B, denoted A → B means that A ⊆ B . This rule has a confidence which can be considered as a conditional probability:

conf(A → B) = |A ∩ B |
|A | where (.) corresponds to the derivation operator. Confidence is used as a quality measure of the rule. An association rule is valid if its confidence is superior to a given threshold θ. When conf

(A → B) = 1, the rule is an implication, denoted byA ⇒ B. If B ⇒ A, then A and B form a definition, denoted by A ≡ B.
Since the confidence is not symmetric, A → B can be valid but B → A not valid. Potentially, an association rule A → B can be considered together with its reverse B → A, and we can wonder how far they are from being implications. Accordingly, we introduce the notion of a quasi-definition which is to definition what association rule is to implication.

Definition 1 (Quasi-definition). Given two sets of attributes A, B and a user-defined threshold θ, a quasi-definition

A ↔ B holds if A → B, B → A and min(conf(A → B), conf(B → A)) θ
The algorithm Eclat [11] is one of the existing algorithms for enumerating frequent itemsets. From frequent itemsets, association rules can be enumerated. Here, we use Eclat as implemented in the Coron system1 for computing association rules. It exhaustively enumerates all the association rules that hold w.r.t. a given threshold. Here, we rely on Eclat to mine association rules.

Since we want to provide definitions of classes, we are interested in rules

X → Y such that X ⊆ M C and Y ⊆ M D or, conversely, X ⊆ M D and Y ⊆ M C .
Given a rule R: X → Y , the consequent can be decomposed into two rules

R C : X → Y C and R D : X → Y D where Y C = Y ∩ M C and Y D = Y ∩ M D respectively. Since Y C ⊆ Y , Y ⊆ Y C , thus |X ∩ Y | |X ∩ Y C |, which means that if R holds, then R C holds. Similarly, if R holds, then R D holds.
We take advantage of this property to keep the quasi-definitions we are interested in. For example, ∃r 1 :x 1 , C 0 → ∃r 2 :x 2 is not kept because the antecedent include both categories and descriptions. On the other hand, ∃r 1 :x 1 → {∃r 2 :x 2 , C 0 } can be decomposed into R 1 : ∃r 1 :x 1 → ∃r 2 :x 2 and R 2 :

∃r 1 :x 1 → C 0 .
The rule R 2 is kept. If its converse is valid, we obtain the quasi-definition

C 0 ↔ ∃r 1 :C 1 .

Redescriptions

Redescription mining [8] provides multiple characterizations of a given set of entities. Contrasting association rules, redescriptions rely on the separation of the set of attributes into views. The set of all views corresponds to a partition of the set of attributes. We work here with two views, corresponding to the two kinds of attributes we distinguished: M C and M D .

The similarity between the sets of attributes, coming from two different views, is measured thanks to the Jaccard coefficient:

jacc(A, B) = |A ∩ B | |A ∪ B |
where (.) corresponds to the derivation operator. We say that the redescription holds if the Jaccard coefficient is above a given threshold. Contrary to confidence, the Jaccard coefficient is symmetric. A redescription with a Jaccard coefficient equal to 1 corresponds to a definition as introduced in the previous section. A redescription is necessarily a quasi-definition. Indeed,

min(conf(A → B), conf(B → A)) jacc(A, B).
Example 1. Given the context Figure 1, the two views are distinguished by the vertical line in gray. From this context, {C 0 } ↔ {∃r 1 :x 1 , ∃r 2 :x 2 } is a redescription with a Jaccard coefficient of 1.

The algorithm ReReMi [5] is used in this work to mine redescriptions. It searches for a pair of attributes-one in each view-that may constitute a definition and tries to extend it by adding one attribute at each step. More than binary data, ReReMi also handles numerical and categorical data. It also enables to consider Boolean functions including conjunctions, disjunctions and negations over the attributes. Here, we only use a binary dataset and conjunctions of attributes in order to compare the results with the other algorithms.

Translation rules

The algorithm Translator [10] also relies on two views and searches for a set of associations between these two views, but the construction of the associations is based on a different approach, that is minimum description length (MDL).

The associations consist in rules that enable building one context from the other, as shown in Figure 2. The set of rules has to be compact and representative. In one hand, it should cover most of the data. In the other hand, the rules have to be as small as possible in term of attributes. To check these two constraints, Translator relies on MDL. Given K = (G, M, I) a context and

X ⊆ M Context K1 a b c d 1 × × 2 × × 3 × × × 4 × × e f g h 1 × × 2 × × 3 × × × 4 ×
Temp.

e f g h 1 × × 2 3 4 × Mask Context K2 e f g h 1 × × 2 × × 3 × × × 4 × × Goal: translate K1 into K2 and K2 into K1 Rules r1 : a, b → g, h r2 : c → f Fig. 2:
Translator is searching for a set of rules that enables transforming

K 2 into K 1 and K 1 into K 2 .
Here we represent only the construction of

K 2 from K 1 .
For each object in K 1 and for each rule, if the object has all the attributes of the condition, then all the attributes of the conclusion are added to K 2 .

a set of attributes, the length of X w.r.t. K corresponds to the minimum number of bits required in order to encode X. That is:

L(X) = - x∈X log 2 P (x | K) where P (x | K) = | x | | G | .
In [10], the authors compare the mining process to a translation task. A rule is considered as a translation from one context to an other. The underlying idea is that, with enough translation rules, one can build the first context from the other and vice versa. The general idea is depicted Figure 2. The errors introduced in the target context are fixed with a mask. Thus, the size of the mask corresponds to the number of errors added. The algorithm Translator compute rules step by step. At the beginning of the process, the mask corresponds to the target context. The algorithm searches for the rule which has the best trade-off between lowering density of the mask and not being too long, i.e. the rule which maximizes ∆:

∆(X → Y ) = L(Mask -) -L(Mask + ) Information gain -L(X ∪ Y ) Rule length
where Mask + corresponds to the items added to the mask (errors introduced by the rule) and Mask -corresponds to items removed from the mask (errors fixed by the rule). Rules are added while ∆ > 0.

The mask is updated each time a rule is added. Since the information gain depends on the mask, the quality ∆ of a rule depends on the rules that are already found. Thus, Translator is the only algorithm which takes into account rules already found to choose which rule is added.

Related work

In [1], authors rely on association rule mining to provide a navigation space over RDF resources. To this end, they search for implications and rank them w.r.t. the confidence of their converse. Our work is in the continuity of this one: our purpose is the same, but here we use two other approaches and compare them.

The AMIE algorithmn, extended to AMIE+ [4], is a reference for mining rules in KBs. Those rules have the form B 1 ∧ B 2 ∧ . . . B n-1 ⇒ B n where B i is a relation between two objects r(x i , x j ). Authors add a constraint: all the variables have to appear twice in the rule, in different atoms. Our work is distinct from this one in two manners. We consider rules and their converse, and we do not focus on relations (i.e. predicates), but on the pair (predicate, object).

In a survey, Sertkaya [9] presents papers trying to bridge the gap between FCA and ontologies. In ontologies, the knowledge is constructed with top-down approaches (e.g experts who encode knowledge of a domain). At the contrary, in FCA, knowledge is discovered with a bottom-up approach, starting from facts and trying to generalize them. Thus, one way to take advantage of FCA is to allow bottom-up construction of ontologies and to complete existing ontologies. This is what is done in our approach: we start from RDF statements and try to find definitions of classes.

In [3], an extension to FCA for conceptual graphs, called G-FCA, is proposed. Compared to RDF graphs, conceptual graphs (CG) are oriented bipartite graphs. The two kinds of nodes are classes and relations. Contrasting RDF graphs which only consider binary relations, CGs handle n-ary relations. The approach enables to find projected graph patterns. A projected graph pattern is a pair containing a graph query and a set of candidate solutions. It is similar to a SPARQL query where the graph query is the intent and the candidate solutions are the extent. This work is complementary to our work in the sense that, instead of dealing with rule mining, it considers the full lattice.

Experiments

We run our experiments on DBpedia data, which is one of the most important knowledge bases of the linked open data, built from Wikipedia. We are interested in categories of DBpedia, that is, resources in the range of the relation dct:subject. Categories are a specific kind of classes. They are built from specific Wikipedia pages which lists other pages (for example the page Category:Smartphones2 ). The advantage of considering these categories instead of common classes is that there are much more categories than classes, and the only information about them provided in DBpedia is which resources belong to each category. Thus, finding why some resources are gathered together (for example, "because they all are smartphones") is an interesting challenge.

To this end, we extracted a subset of DBpedia thanks to a SPARQL query. The triples extracted are transformed in a context as presented in section 2.2. We run algorithms which are introduced above, then, we compare and evaluate the extracted quasi-definitions. Both data and results are available online

Methodology

We extracted four different subsets of triples, of different size and different domains, from DBpedia, with SPARQL queries. All the queries follow the same pattern. The datasets correspond to the categories Smartphones, Sports_cars, Turing_Award_laureates and French_films. Statistics of the datasets are provided Table 1.

For each dataset, the partition of the attributes is constructed as follows:

M C is the subset of attributes whose predicate is dct:subject whereas M D is the set of attributes whose predicate differs from dct:subject. For Eclat, since both attributes of classes and descriptions are in the same context, the input data is one file which contains the context in a tabular format. For ReReMi and Translator, the input data are two tabular files.

Results

Each algorithm returns an ordered set of quasi-definitions. Each quasi-definition is manually evaluated by three phD students familiar with linked open data, playing the role of experts. Given a definition C 0 , . . . , C n ↔ D 0 , . . . , D m from a dataset X, each evaluator answers the question " Taking X as a reference, is it true that belonging to C 0 and C 1 . . . and C n and having the properties D 0 and D 1 . . . and D m is equivalent ? " The final evaluation is the majority between the experts. Experts gave the same answer in 95.4% of the cases. If evaluated true, the quasi-definition is added to the set of definitions (see Fig. 3). The comparison between the algorithms is based on definitions (i.e. quasidefinition evaluated as true by at least 2 experts) that have been extracted and categories that have been defined. Figure 4 shows two Venn diagrams for each dataset: one for the number of definitions extracted and one for the number of categories defined. In the dataset Turing_Award_laureates, for example, there are 22 definitions only extracted by Eclat and 8 definitions extracted by both Eclat and Translator. Eclat extracted 30 definitions in total. A category is considered as defined as soon as it appears in a definition. Therefore, in one definition, there can be one or more categories considered as defined. In order to be more readable, namespaces have been removed.

Discussion

Hereafter, we will denote B X cand the set of all the quasi-definitions extracted by the algorithm X and B X def the set of quasi-definitions from B X cand evaluated true by the experts, i.e. the set of definitions extracted by X. The set B cand denotes the set of all the quasi-definitions definitions extracted, regardless the algorithm. Similarly, B def denotes the set of all the definitions extracted.

Precision, recall and completeness

The precision of an algorithm X is

|B X def | |B X cand |
. The precision of ReReMi has a high variability (from 33% to 75%) and is overall the weakest, especially for the dataset French_films. The precision of Eclat is stable (from 64% to 72%).

Translator has the best precision which is always over 74%. The recall could be defined as |B X def | |B def | . However, it cannot be used as a performance measure. Indeed, some of the definitions overlap (i.e. have attributes in common in both sides). This is the case for the rules R6 to R10 in Figure 3 : all the rules define the category McLaren_vehicules. Whereas Translator extracts only one rule (R8), ReReMi extracts 2 rules (R6 and R7) and Eclat extracts 9 rules (only 3 of them, R8 to R10, are reported here).

Given the valid quasi-definitions, the uncompleteness of the KB can be measured as the number of triples which can be inferred from the quasi-definitions and that are not already in the KB. For example, given the rule Pathé_Films ↔ (distributor Pathé), if a resource r belongs to Pathé_Films (i.e. r, subject, Pathé_Films ∈ KB), then the triple r, distributor, Pathé is expected to be in the KB. Conversely, if the triple r, distributor, Pathé belongs to the KB, then r, subject, Pathé_Films is expected to be in the KB. Figure 4c counts, for each dataset, the number of inferred triples that were not in the KB.

Shape and interpretation of the rules

From Figure 4, 70% of the categories defined by Eclat or Translator are defined by both algorithms. However, Translator extracts much less rules than Eclat (until 16 times less for the dataset Smartphones). This is due to the extraction process of association rules: if the rule A → B has the same support as the rule A → {B, C}, then only the rule A → {B, C} is kept. However, if the support of A → B is higher, both rules are kept. Consequently, Eclat mines rule which can differ from only one attribute (R9 and R10), contrary to Translator (only R8). by ReReMi is that it mines smaller definitions than definitions mined by Eclat and Translator wrt the number of attributes. On average, definitions mined by ReReMi have 1 or 2 attributes on each side whereas definitions mined by Eclat and Translator have 3 categories and 4 descriptions. These differences raise the question of the semantics of the conjunctions. Indeed, the semantics of the conjunctions in the definitions mined by ReReMi differs from the one in definition mined by Eclat and Translator. For example, in rule R15, the attribute (a, Device) can be removed without repercussion on the meaning. On the opposite side, in definition R14, no attribute can be removed without changing the meaning of the definition. That is, all the attributes are necessary. In our approach, it seems more interesting to consider only attributes that are necessary in the definition. Thus, R14 is better than R15 according to the ease of interpretation.

Conclusion

In this paper, we compared three algorithms to find definitions in the linked open data. Each algorithm has its specificities and we verified that these specificities are reflected in the results of our experiments. We showed that, despite their very different approaches, Eclat and Translator extract a lot of identical rules. At the opposite, ReReMi, in spite of a quality measure very similar to Eclat, extracts shorter rules. The advantage of each algorithm depends on the goal of the user. In our experiments, Eclat is the algorithm which defines the most of the categories, at the cost of a huge number of quasi-definitions extracted. Translator extracts significantly less quasi-definitions but defines less categories. ReReMi, despite a low number of categories defined, offers definitions easier to understand which do not include attributes that do not contribute to the definition.

Relational proportions between objects and attributes

Nelly Barbot 1 , Laurent Miclet 1 , and Henri Prade 2

Introduction

A statement such as "Carlsen is to chess as Mozart is to music" introduces Carlsen as a precocious virtuoso of chess, a quality that Mozart is well known to have concerning music. It relates two types of items, here people and activities. It is an example of what we call relational proportions which are statements of the form "object A has the same relationship with attribute a as object B with attribute b". This can be viewed as a special case of analogical proportions which are statements of the form "A is to B as C is to D". In the case where A, B, C, D are items which can be represented in terms of the same set of features, a formal definition has been proposed for analogical proportions in the setting of Boolean logic and then extended using multiple-valued logic for handling numerical features [2,9], by stating that "A differs from B as C differs from D and B differs from A as D differs from C".

The nature of relational proportions suggests to handle them in the setting of formal concept analysis. This leads us to the question of defining analogical proportions between formal concepts. The paper first recalls the definition of analogical proportions in non distributive lattices, as already presented in [4]. Then it brings original material, firstly by studying the links between analogical proportions between formal concepts and analogical proportions between objects or attributes. It also shows how relational proportions can be obtained in a formal context from the identification of an analogical complex.

Analogical proportions: basics and formalization

Analogical proportions are usually characterized by three axioms. The first two axioms acknowledge the symmetrical role played by the pairs (x, y) and (z, t) in the proportion 'x is to y as z is to t', and enforce the idea that y and z can be interchanged if the proportion is valid, just as in the equality of two numerical ratios where means can be exchanged. This view dates back to Aristotle. A third (optional) axiom, called determinism, insists on the uniqueness of the solution t = y for completing the analogical proportion in t: (x : y :: x : t). These axioms are studied in [1].

Definition 1 (Analogical proportion). An analogical proportion (AP) on a set X is a quaternary relation on X, i.e. a subset of X 4 . An element of this subset, written (x : y :: z : t), which reads 'x is to y as z is to t', must obey the following axioms:

1. Reflexivity of 'as': (x : y :: x : y) 2. Symmetry of 'as': (x : y :: z : t) ⇔ (z : t :: x : y) 3. Exchange of means: (x : y :: z : t) ⇔ (x : z :: y : t)

Then, thanks to symmetry, it can be easily seen that (x : y :: z : t) ⇔ (t : y :: z : x) should also hold (exchange of the extremes). According to the first two axioms, four other formulations are equivalent to the canonical form (x : y :: z : t). Finally, the eight equivalent forms of an analogical proportion are: (x : y :: z : t), (z : t :: x : y), (y : x :: t : z), (t : z :: y : x), (z : x :: t : y), (t : y :: z : x), (x : z :: y : t) and (y : t :: x : z).

With respect to this axiomatic definition of AP, Stroppa and Yvon [3] have given another definition, based on the notion of factorization when the set of objects is a commutative semigroups. From these previous works, Miclet et al. [4] have derived the following definitions in the lattice framework. Definition 2. A 4-tuple (x, y, z, t) of a lattice (L, ∨, ∧, ≤) 4 is a Factorial Analogical Proportion (FAP) (x : y :: z : t) iff:

x = (x ∧ y) ∨ (x ∧ z) x = (x ∨ y) ∧ (x ∨ z) y = (x ∧ y) ∨ (y ∧ t) y = (x ∨ y) ∧ (y ∨ t) z = (z ∧ t) ∨ (x ∧ z) z = (z ∨ t) ∧ (x ∨ z) t = (z ∧ t) ∨ (y ∧ t) t = (z ∨ t) ∧ (y ∨ t) Definition 3. A 4-tuple (x, y, z, t) of (L, ∨, ∧, ≤) 4 is a Weak Analogical Propor- tion (WAP) when x ∧ t = y ∧ z and x ∨ t = y ∨ z. It is denoted x : y W AP z : t.
In the case of a distributive lattice (e.g. a Boolean lattice), this alternative definition is equivalent to the FAP. But, in general, a FAP is a WAP and the converse is false, which explains the use of adjective "weak" [4].

Example 1. Let us consider a finite set Σ and the associated Boolean lattice (2 Σ , ∪, ∩, ≤). When saying of subsets x, y, z, t of Σ that "x is to y as z is to t", we express that x differs from y in the same way as z differs from t. For example, if x = {a, b, e} and y = {b, c, e}, we see that to transform x into y, we have to remove a and add c. Now, if z = {a, d, e}, we can construct t with the same operations, to obtain t = {c, d, e}. In more formal terms, with this definition, the following properties are asked to x, y, z and t (with x\y = x∩¬y): x\y = z\t and y \ x = t \ z, which are equivalent to x ∩ t = y ∩ z and x ∪ t = y ∪ z. These relations linking x, y, z, t are clearly symmetrical, and satisfy the exchange of the means. Hence it is a correct definition of the AP in the Boolean setting [2].

The next proposition gives a simple example of FAP in a lattice. Proposition 1. Let y and z be two elements of a lattice, the proportion y : y ∨ z :: y ∧ z : z is a FAP. We call it a Canonical Analogical Proportion (CAP).

Proof. The first equality of Definition 2, namely y = (y ∧ (y ∨ z)) ∨ (y ∧ (y ∧ z)), is true since the right member is equal to (y) ∨ (y ∧ z) = y. The verification of the three other equalities of Definition 2 is similar, using the absorption laws.

Analogical proportions in FCA

In order to derive more specifically the AP notion in a Formal Concept Analysis framework (FCA), we first recall some basic elements of FCA, before studying the relations between several kinds of AP and their characterization in FCA. The set of all formal concepts is equipped with a partial order (denoted ≤) defined as: (o 1 , a 1 ) ≤ (o 2 , a 2 ) iff o 1 ⊆ o 2 (or, equivalently, a 2 ⊆ a 1 ). Then it is structured as a lattice, called the concept lattice of R.

Formal concept analysis

Example 2. The concept lattice of the following context R is shown in Figure 1.

a1 a2 a3 a4 a5 a6 a7 a8 a9 o1 × × × × × × o2 × × × × × × o3 × × × × × × o4 × × × × × × o5 × × × × × × × × ×
The following preliminaries are simple consequences of the definition of concept lattice and the Main Theorem of Formal Concepts [5,6]. They allow for a quick demonstration of propositions in the next section.

Weak and strong analogical proportions in FCA

Since concepts are associated to a set of attributes and objects, the main objectives of this section are to relate the AP definitions with these sets and to study the links the AP on concept lattice and AP on object or attribute sets.

Proposition 2. Let x, y, z and t be four concepts, one has:

(x ∨ t = y ∨ z iff a x ∩ a t = a y ∩ a z ) and (x ∧ t = y ∧ z iff o x ∩ o t = o y ∩ o z ).
As consequence, (x : y W AP z : t) iff a x ∩a t = a y ∩a z and o x ∩o t = o y ∩o z .

Proof. From Preliminary 2, x∨t = y ∨z implies a x ∩a t = a y ∩a z and conversely, a x ∩ a t = a y ∩ a z implies a x∨t = a y∨z . Thus, x ∨ t = y ∨ z using Preliminary 3.

The proof of the second equivalence can be done in a similar manner. We give now a proposition which leads us to a corollary in which is defined yet another analogical proportion between formal concepts, the strongest of all. Proposition 4. Let x, y, z and t be four concepts, if (a x ∪ a t = a y ∪ a z and o x ∪ o t = o y ∪ o z ) then the FAP x : y :: z : t holds.

Proof. a x ∪ a t = a y ∪ a z implies that a x = (a x ∩ a y ) ∪ (a x ∩ a z ). It results that, using Preliminaries 1 and 2,

o x = (a x ) ↓ = (a x ∩ a y ) ↓ ∩ (a x ∩ a z ) ↓ . Then, o x = (a x∨y ) ↓ ∩ (a x∨z ) ↓ = o x∨y ∩ o x∨z = o (x∨y)∧(x∨z)
and Preliminary 3 permits to obtain x = (x ∨ y) ∧ (x ∨ z).

In a same way, from

o x ∪ o t = o y ∪ o z , we get that o x = (o x ∩ o y ) ∪ (o x ∩ o z ) and a x = (o x ) ↑ = (o x ∩ o y ) ↑ ∩ (o x ∩ o z ) ↑ . Then, a x = (o x∧y ) ↑ ∩ (o x∧z ) ↑ = a x∧y ∩ a x∧z = a (x∧y)∨(x∧z) .
Thus, x = (x∧y)∨(x∧z). All the equalities of Definition 2 are similarly checked.

Corollary 1. Let x, y, z and t be four concepts, the following two conjunctions are equivalent:

a x ∪ a t =
⊥ : z (which is a CAP) but o y ∪ o z = o ∪ o ⊥ and a y ∪ a z = a ∪ a ⊥ .
Example 3. In the Boolean lattice displayed in Figure 1, concepts x, y, u and v form a FAP but are not in SAP. Indeed, a x : a y :: a u : a v does not hold. However, without changing the lattice, the formal context can be reduced to

a1 a2 a3 a4 o1 × × × o2 × × × o3 × × × o4 × × ×
and the reduced representation of x, y, u and v gives (x : y SAP u : v):

a1 a2 a3 a4 ax × × ay × × au × × av × × o1 o2 o3 o4 ox × × oy × × ou × × ov × ×
These observations stem from the fact that the FAP and WAP between concepts are directly related to the lattice whereas the Boolean AP between object or attribute sets directly depends on the formal context.

Formal concepts and relational proportion

From a RP to concepts in AP

In this section, we study if we can deduce from a relational proportion "A is the B of a", or "A is to a as B is to b", formal concepts in WAP and an analogical complex from this knowledge.

As an example, we have found in a web magazine3 the following proportion "Massimiliano Alajmo is the Mozart of Italian cooking". The background knowledge allowing to understand this relational proportion is the following: music and Italian cooking are disciplines practiced by humans, such disciplines can be practiced with different levels of ability, Mozart is a musician and Mozart is a genius in music discipline. Since the quality "to be a genius" is not possessed by everybody, there must exist many "ordinary gifted" musicians. Then, the background knowledge can be expressed by the following formal context:

a1 a2 a3 o1 × × o2 × ×
where o 1 stands for Mozart, o 2 for one of "ordinary gifted" musicians, a 1 is the attribute "practices music", a 2 "is a genius" and a 3 "has an ordinary ability". Now, when the new data "Alajmo is the Mozart of Italian cooking" is introduced, the knowledge extends as follows: Alajmo practices Italian cooking, and he has something in common with Mozart that is not Italian cooking. The relational proportion is a reduced form of "Alajmo is to Italian cooking as Mozart is to music". Since Mozart has only the other attribute "Genius", Alajmo must have it. Moreover, since cooking is a discipline practiced by humans, there must exist some ordinary gifted Italian cook. At last, we must introduce the notion of non-genius in our universe. If we do not, we implicitly suppose that everybody is a genius for some activity. The knowledge is now as follows

a1 a2 a3 a4 o1 × × o2 × × o3 × × a4 × ×
where o 3 stands for Alajmo, o 4 an ordinary gifted Italian cook and a 4 Italian cooking. This context is called the analogical context. Considering the associated concept lattice, the closest analogical proportion to "Alajmo is the Mozart of Italian cooking" is ({o

3 }, {a 2 , a 4 }) : ({o 4 }, {a 3 , a 4 }) W AP ({o 1 }, {a 1 , a 2 }) : ({o 2 }, {a 1 , a 3

Analogical complex

In the previous paragraph, it turns out that the analogical context is an interesting pattern, from which we can extract relational proportion. A more general definition of this pattern, named analogical complex, has been given in [7].

An analogical complex is a subcontext of a formal context described by:

× × × × × × × × associated with the binary matrix AS =    0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0   . Matrix AS
exhibits characteristic pattern of a Boolean analogical proportion [2] and is called an analogical schema. We write AS(i, j) if its value at row i and column j is 1.

Definition 4. Given a formal context (O, A, R), a set of objects o ⊆ O, o = o 1 ∪ o 2 ∪ o 3 ∪ o 4 , a set of attributes a ⊆ A, a = a 1 ∪ a 2 ∪ a 3 ∪ a 4 ,
∀i ∈ [1, 4], ∀o ∈ o i , ∀j ∈ [1, 4], ∀a ∈ a j , ((o, a) ∈ R) ⇔ AS(i, j). 2.
The context is maximal with respect to the first property (⊕ denotes the exclusive or and \ the set-theoretic difference):

∀o ∈ O \ o, ∀i ∈ [1, 4], ∃j ∈ [1, 4], ∃a ∈ a j , ((o, a) ∈ R) ⊕ AS(i, j). ∀a ∈ A \ a, ∀j ∈ [1, 4], ∃i ∈ [1, 4], ∃o ∈ o i , ((o, a) ∈ R) ⊕ AS(i, j).
An analogical complex is complete if none of sets a 1 , . . . , a 4 , o 1 , . . . , o 4 are empty.

Comments.

1. In order to simplify the notations, the Cartesian products o 1 × . . . × o 4 and a 1 × . . . × a 4 are respectively denoted o 1,4 and a 1,4 . 2. In [7], it has been shown that the set of the analogical complexes of any formal context is itself structured as a lattice.

Example 4. Let us consider a subcontext, called SmallZoo, extracted from the Zoo data base [8], it has been shown in [7] that 24 analogical complexes (18 complete ones) can be derived, like the following complete one:

SmallZoo hair feathers eggs milk airborne aquatic predator toothed a0 a1 a2 a3 a4 a5 a6 a7 o0 aardvark × × × × o1 chicken × × × o2 crow × × × × o3 dolphin × × × × o4 duck × × × × o5 fruitbat × × × × o6 kiwi × × × o7 mink × × × × × o8 penguin × × × × o9 platypus × × × × × a1 a2 a3 a4 a5 a0 a3 a7 a1 a2 a4 o1 o1 × × × o2 × × × o2 o5 × × × × o3 o8 × × × o4 o7 × × × ×
From the analogical complex structure, we derive a formal definition of a relational proportion. Definition 5. Let (o 1,4 , a 1,4 ) be a complete analogical complex in a formal context, the following sets of objects and attributes are said to be in the formal relational proportion (o 1 is to a 3 as o 2 is to a 2 ), and we write: (o 1 ˜a3 ˜˜o 2 ˜a2 ).

Comments.

1. The reduced form of the relational proportion would be (o 1 is the o 2 of a 3 ). 2. From the same complex, we can extract the 4 following formal relational proportions o 1 ˜a4 ˜˜o 3 ˜a1 , o 2 ˜a4 ˜˜o 4 ˜a1 and o 3 ˜a3 ˜˜o 4 ˜a2 . Since the operator ˜˜is commutative, it gives a total of 8, but permuting the extreme and the means in a relational proportion may lead to awkward phrasings.

Example 5. Let us take the complex from SmallZoo described above. It implies all attributes but a 6 (predator) and objects o 1 and o 2 (chicken and crow), o 5 (fruitbat), o 8 (penguin) and o 7 (mink). From this context, the RP in reduced form "a fruitbat is the mink of airborne animals" can be derived for instance, meaning that fruitbat and mink have hair, are toothed and produce milk, but that the mink is aquatic at the contrary of the fruitbat. Of course, the interest of such phrases has to be taken in context: the SmallZoo data base is supposed to be the only knowledge.

WAP and analogical complex

In this section we explore the links between WAP between concepts and complete analogical complex, and then the formal relational proportion. First, we are interested in defining a non degenerated WAP, called complete, forbidding inclusion between two of its concepts. It is a key notion for building WAPs between concepts with a sound cognitive interpretation. Definition 6. Let us consider (x : y W AP z : t), this WAP is complete when

1. either (a x ∩ a y ) \ a ∩ , (a x ∩ a z ) \ a ∩ , (a y ∩ a t ) \ a ∩ and (a z ∩ a t ) \ a ∩ are nonempty (called complete WAP through attributes), 2. or (o x ∩o y )\o ∩ , (o x ∩o z )\o ∩ , (o y ∩o t )\o ∩ and (o z ∩o t )\o ∩ are nonempty (called complete WAP through objects).
where

a ∩ = a x ∩ a y ∩ a z ∩ a t and o ∩ = o x ∩ o y ∩ o z ∩ o t .
Proposition 5. 1. A complete WAP is an antichain of concepts. 2. For a complete WAP through attributes, (x ∨ y), (x ∨ z), (y ∨ t) and (z ∨ t) are in antichain. Similarly, for a complete WAP through objects, (x ∧ y), (x ∧ z), (y ∧ t) and (z ∧ t) are in antichain. 3. A FAP in antichain forms a complete WAP through attributes and objects, and reciprocally.

Proof. 1. Let us suppose that (x : y W AP z : t) and x ≤ y. From Preliminary 2, we get a x ∩ a y = a x∨y . Then a x ∩ a y = a y and using Proposition 2

a x ∩ a z = (a x ∩ a y ) ∩ a z = a x ∩ (a y ∩ a z ) = a x ∩ (a x ∩ a t ) = a x ∩ a t = a ∩ .
Thus, a x ∩ a z \ a ∩ = ∅ and (x : y W AP z : t) is not a complete WAP.

2. From a complete WAP through attributes, a x∨y = a x ∩ a y and three analog equalities hold. Due to this completeness, there is no inclusion between a x∨y , a x∨z , a z∨t and a y∨t . The associated concepts are then in antichain.

3. Let us consider the FAP x : y :: z : t where {x, y, z, t} is an antichain. From Proposition 2, we have

x = (x ∧ y) ∨ (x ∧ z) and x = (x ∨ y) ∧ (x ∨ z)
a ∩ = a x ∩ a y ∩ a z ∩ a t = a x ∩ a t o ∩ = o x ∩ o y ∩ o z ∩ o t = o x ∩ o t
due to Proposition 2 and the fact that a FAP is a WAP. Therefore, we have

a x∧y \ (a x ∩ a t ) ⊆ a x ∩ a y \ a ∩ . Moreover, a x∧y \ (a x ∩ a t ) = a x∧y \ a x∨t is nonempty. Indeed, a x∧y \ a x∨t = ∅ implies that x ∨ t ≤ x ∧ y which is impossible since {x, y, z, t} is an antichain. Similarly, we can prove that o x ∩ o y \ o ∩ = ∅.
Reciprocally, let us take a complete WAP through attributes and objects. From the previous properties, {x, y, z, t} is an antichain, as well as {x ∨ y, x ∨ z, y ∨ t, z ∨ t} and {x ∧ y, x ∧ z, y ∧ t, z ∧ t}. Therefore, these 12 concepts are distinct and it can be proved that they generate a Boolean sublattice. Because of the distributivity of this sublattice, the WAP (x : y W AP z : t) is then a FAP.

In order to derive relational proportion from an analogical proportion between concepts, we consider a complete WAP through attributes (a similar reasoning can be done from a complete WAP through objects) and introduce a process to extract an analogical complex.

Due to the completeness, sets

a 1 = (a z ∩ a t ) \ a ∩ , a 2 = (a y ∩ a t ) \ a ∩ , a 3 = (a x ∩ a z ) \ a ∩ and a 4 = (a x ∩ a y ) \ a ∩
are nonempty. We also define o 1 = o x the set of objects proper to x (that appear in o x but not in the objects of y, z and t) and similarly

o 2 = o y , o 3 = o z and o 4 = o t .
By construction, every object of o 1 is in relation with every attribute of a 3 ∪ a 4 . It is also the case between o 2 and a 2 ∪ a 4 , o 3 and a 1 ∪ a 3 , o 4 and a 1 ∪ a 2 . For all the other combinations, for instance o 1 and a 1 , for any o ∈ o 1 , there exists a ∈ a 1 such that o and a are not in relation. However, these properties do not guarantee that the subcontext (o 1,4 , a 1,4 ) is an analogical schema, even if it is a closed schema. Indeed, it can exists an object o ∈ o i in relation with an attribute a ∈ a j , where (i, j) ∈ {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3,4), (4,3), (4,4)}. In such a case, either a or o is removed and this postprocessing permits to obtain an analogical schema. But this schema is not necessarily a complex, since the associated subcontext may be not maximal. Then a second postprocessing maximises the schema into complex, adding new attributes and/or objects chosen among those which do not appear in a x ∪ . . . ∪ a t nor o x ∪ . . . ∪ o t . Finally, we check that the resulting analogical complexes are complete.

This method can lead to several complexes, according to the choices in both postprocessings. This set of complexes is a sub-lattice of the lattice of complexes.

Example 6. In SmallZoo, x = ({o 1 , o 2 , o 4 }, {a 1 , a 2 , a 4 }), y = ({o 5 }, {a 0 , a 3 , a 4 , a 7 }), z = ({o 4 , o 8 }, {a 1 , a 2 , a 5 }), t = ({o 7 , o 9 }, {a 0 , a 3 , a 5 , a 6 }) are concepts in com- plete WAP through attributes. At the beginning, o 1 = {o 1 , o 2 }, o 2 = {o 5 }, o 3 = {o 8 }, o 4 = {o 7 , o 9 }, a 1 = {a 5 }, a 2 = {a 0 , a 3 }, a 3 = {a 1 , a 2 } and a 4 = {a 4 }
and, due to the relation between o 9 and a 2 , the first postprocessing can remove (either o 9 or) a 2 :

a5 a0 a3 a1 a2 a4 o1 × × × o2 × × × o5 × × × o8 × × × o7 × × × o9 × × × × a1 a2 a3 a4 a5 a0 a3 a1 a4 o1 o1 × × o2 × × o2 o5 × × × o3 o8 × × o4 o7 × × × o9 × × ×
After removing a 2 , the right table is an analogical schema and we can check that it is maximal in SmallZoo. Note that if we had chosen to remove o 9 , the postprocessings would have produced the analogical complex previously detailed in Example 4. For example, from the complete analogical complex described above, we can derive the following relational proportion: "the chicken and the crow are to the feathers as the fruitbat is to the hair, the milk and the teeth". It makes sense when considering that all these animals share the attribute "airborne".

Likewise, another proportion from the same complex is "the fruitbat is to the airborne animals as the mink and the platypus are to the aquatic animals" (fruitbat, mink and platypus share the attributes hair and milk). The reduced form "the fruitbat is the mink of airborne animals" is the same as that of Example 5, Section 4.2, although the complexes involved are slightly different.

Conclusion

The paper has shown how relational proportions can be identified in a formal context. Relational proportions offer a basis for concise forms of explanations. Indeed, if B has some well-known features, the proportion "object A is to attribute a as object B is to attribute b" provides an argument for stating that "object A is the B of a", when A possesses these well-known features also, as in "Carlsen is the Mozart of chess". It is worth pointing out that two cognitive capabilities, namely conceptual categorization and analogical reasoning can be handled together in the setting of formal concept analysis. This introductory presentation has left aside the algorithmic side (based on the identification of formal complexes), which is discussed in the long version of the paper [10].

Our study of proportions between concepts explores a simple and fixed relation between concepts in a single lattice. It would be interesting to connect it with the general framework of Relational Concept Analysis (see e.g., [11]), and with a recent proposal based on antichains [12].

Following the pioneering work of Rumelhart and Abrahamson [13], a number of recent woks in computational linguistics (e.g., [14]) have been using a parallelogram-based modeling of analogical proportions in numerical settings, where words are represented by vectors of great dimension. Bridging this computational view of analogical proportions with the work presented here is certainly a challenging task for the future.

MDL for FCA: is there a place for background knowledge?

Tatiana Makhalova 1,2 , Sergei O. Kuznetsov 1 , and Amedeo Napoli 2

1 National Research University Higher School of Economics, 3 Kochnovsky Proezd, Moscow, Russia 2 LORIA, (CNRS -Inria -U. of Lorraine), BP 239

Vandoeuvre-lès-Nancy, France tpmakhalova@hse.ru, skuznetsov@hse.ru, amedeo.napoil@loria.fr Abstract. The Minimal Description Length (MDL) principle is a powerful and well founded approach, which has been successfully applied in a wide range of Data Mining tasks. In this paper we address the problem of pattern mining with MDL. We discuss how constraints -background knowledge on interestingness of patterns -can be embedded into MDL and argue the benefits of MDL over a simple selection of patterns based on measures.

Introduction

Formal Concept Analysis (FCA) is a formalism that can be applied to Knowledge Discovery and Data Mining. It is used commonly for solving a wide range of tasks: from pattern mining to design of ontologies.

Even controlled application of FCA in practice may result in exponentially large output, which entails additional steps aimed at reducing / selecting a small subset of concepts. The reduction of the number of formal concepts may be done during pre-/postprocessing stages.

In this paper we propose to combine two of the most common concept filtering approaches: the Minimal Description Length principle (MDL) [2,6,7,12] and measure-based selection [8]. This combination tries to take the advantages of both methods and reduces the drawbacks of each one.

The idea of MDL is to select a subset of patterns that ensures the best compression of data. It has been embedded into FCA in a number of ways: for defining how many factors to use in Boolean matrix factorization (BMF) [3,10,11] or to get more diverse itemsets in frequent pattern mining (FIM) [1,9,13] or to select triclusters [14]. Being threshold-free, MDL provides a succinct nonredundant set of concepts. However, it has some shortcomings. Since the length minimisation is at least NP-complete, the implementation of MDL is based on heuristics. The selected itemsets cannot be interpreted easily by experts.

Unlike MDL, the selection of itemsets based of values of some measure is easy to interpret. A measure reflects the assumption on interestingness of patterns. Selecting the best itemsets w.r.t. the chosen measure one obtains patterns with the desired characteristics. However, this approach requires threshold and returns a lot of similar patterns.

In this paper we use the Krimp algorithm as an implementation of MDL principle to improve measure-based selection. Krimp is based on greedy covering of data by a set of patterns (subsets of attributes) called candidate set. The patterns in a candidate set are ordered w.r.t. the pattern length and its frequency. We propose to use different interestingness measures to order candidates. This modification allows for embedding background knowledge, i.e., our assumptions on interestingness. The aim of the ordering w.r.t. different measures is to improve measure-based pattern selection rather than to compress data the best. Using a preferable ordering one gets a good compression as well as only those patterns that satisfy defined constraints.

The rest of the paper has the following structure. In Section 2 we briefly recall the main notions of FCA. In Section 3 we describe the MDL principle and discuss how interestingness measures can be used within MDL. The benefits of our approach are discussed in Section 4, where we compare MDL-based with threshold-based measure selection. Section 5 gives the conclusion and discuss the direction of future work.

Formal Concept Analysis: Basic Notions

Here we briefly recall FCA terminology [5].

A formal context is a triple (G, M, I), where G = {g 1 , g 2 , ..., g n } is called a set objects, M = {m 1 , m 2 , . . . , m k } is
A = {m ∈ M | ∀g ∈ A : gIm} B = {g ∈ G | ∀m ∈ B : gIm}
A is the set of attributes common to all objects of A and B is the set of objects sharing all attributes of B. An object g is said to contain a pattern (set of items or itemset) B ⊆ M if B ⊆ g . The double application of (•) is a closure operator, i.e. (•) is extensive, idempotent and monotone. Sets A ⊆ G, B ⊆ M , such that A = A and B = B , are said to be closed.

A (formal) concept is a pair (A, B), where A ⊆ G, B ⊆ M and A = B, B = A. A is called the (formal) extent and B is called the (formal) intent of the concept (A, B). A formal concept is said to cover set of objects A and set of attributes B. A partial order is defined on the set of concepts as follows:

(A, B) ≤ (C, D) iff A ⊆ C (D ⊆ B), a pair (A, B) is a subconcept of (C, D), while (C, D) is a superconcept of (A, B).
The number of formal concepts can grow exponentially w.r.t. the size of a formal context, i.e., the number of objects in G and attributes in M . We say that a set of patterns S covers objects in G if B∈S B = G, where B ⊆ M . We are interested in a small set of patterns (intents) S that covers all objects and most of their attributes, i.e.,

B∈S {gIm | g ∈ B , m ∈ B} ≈ |I|.
Example. Let us consider a toy example. A formal context is given in Figure 1 (1). We consider 3 sets of itemsets (intents): S 2 = {{abc}, {bcde}, {de}, {cde}, {ac}}, S 3 = {{bc}, {de}, {ac}} and S 4 = {{c}, {de}}. The corresponding coverings of the context are given in Figure 1 (2-4). The intensity of colors is proportional to the number of times a particular "cross" is covered by intents. In our example "crosses" are covered by intents from 0 to 4 times. We count not only the number of intents, but also the number of covered "crosses", we call this value the rate of a cover relation, or RCR = |"crosses" that covered at least once|/|I|. It can be seen from the covering given in Figure 1 that S 3 (Figure 1, ( 3)) provides the best covering w.r.t. the number of itemsets (intents) and the rate of covered elements in the object-attribute relation. The Minimal Description Length principle allows for covering with a substantial rate of "crosses" in I by a small number of patterns. In the next section we use MDL in a more general framework, i.e., in pattern mining. Intents of formal concepts, in turn, can be considered as patterns of a special kind.

Minimal Description Length: Basic Notions

MDL is aimed to find a subset of patterns that compresses data the best. In our study we use Krimp [13] as a practical implementation of this principle. In Section 3.1 we give a short description of it and in Section 3.2 we discuss how background knowledge can be embedded into MDL.

MDL in Practice: the Krimp Algorithm

The input of the algorithm is a dataset and a list of patterns (that are computed on the same dataset). The patterns are ordered w.r.t. their length and frequency. The result of Krimp is a two-column code table that consists of patterns and their encoding lengths (an examples of code tables are given in Figure 2). The objective of Krimp is minimization of the function

L(D, CT ) = L(D | CT ) + L(CT | D), (1)
where

L(D | CT )
(B) = -log (u(B)/U ) is inversely proportional to the usage u(B) = |{t ∈ D | B ∈ cover(t, CT )} |.
The usage shows how many times B is used to cover objects in D, U = B∈CT u(B) is the total usage of itemsets. We leave the details on itemset storage out of scope of this paper and take into account the compression related to a particular choice of itemsets, i.e., we use the simplified version of the lengths:

L(D | CT ) = g∈D B∈cover(g,CT ) l(B) = - B∈CT u(B) log u(B) U , L(CT | D) = B∈CT l(B) + code(B).
A code table is incrementally computed. At the beginning it contains only single-attribute patterns {{m} | m ∈ M }. A set of patterns -candidates in the code table -are ordered w.r.t. their length (intent cardinality) and frequency (extent cardinality). At each step the best candidate is added to the code table if its usage allows for smaller encoding length, otherwise it is removed from the code table and the candidate set.

Example. Let us consider how Krimp selects patterns using the running example (the context is given in Figure 1, (1)). Here we represent the context as a set of transactions, see Figure 2, (1). The main stages are given in Figure 2, (2)(3)(4). As candidates we use intents of formal concepts with the size of intent and extent exceeding 1. We sort them first by the size of intent and then by the size of extent (in descending order). Let us consider some steps of the algorithm.

Initial state (Figure 2, (2)): the code table consists of single-attribute patterns. Usage is equal to frequency. Sets of attributes in the dataset are covered by single-attribute patterns.

First step (Figure 2, (3)): An attempt to add the top pattern from the candidate set. Pattern ac is used to cover object g 1 , g 4 and g 5 (Figure 2,(3)), the usage of single attributes a and c decreases by 3. The description length (see Formula 1) is computed for the updated code table and covering. Since the inclusion of ac into the code table provides smaller description length, ac is accepted for the code table.

Further, the top patterns one by one are used to minimize the description length.

Last step (Figure 2, (4)): The last candidate bc can cover only object g 2 (since subsets bc are partially covered by other members of the code table). It is not added since its inclusion in the code table does not provide better compression (i.e. smaller description length). The subset of MDL-optimal patterns is {{ac}, {de}}. Fig. 2. The main stages of the Krimp algorithm. "Covering" tables show the dataset with covering by itemsets from the corresponding code table above the covering, (•) depicts an itemset that covers some attributes of an object. CT is a two-column code table, where "IS" and"U" stand for itemsets and their usage in greedy covering, respectively. "CS" is a candidate set.

MDL in Practice: Compression under Constraints

The implementation of the MDL principle is based on heuristics and allows for the solution which is close to the optimal one. In practice, there exist several ways to select subsets of patterns that have almost the same size and ensure good compression. Thus, it becomes difficult to explain why a particular subset was chosen.

More than that, by selecting a subset of patterns one is interested in patterns that have particular properties, e.g., being stable w.r.t. noise, have high probability under certain condition, etc. Despite proper interpretability, the application of interestingness measures requires a threshold and results in a redundant set of patterns (quite similar patterns). As interestingness measures of concept (A, B) we took frequency f r(B) = |A|, i.e. the size of extent, length len(B) = |B|, i.e., the size of the intent, and lift lif t(B) = b∈B P r(b)/P r(B),

where P r(•) = |(•) |/|G|.
In our study we combine the measure-based selection with Krimp to get a threshold-free approach that provides a small non-redundant subset of patterns having desired properties. The modified approach works as follows. First, all patterns are sorted w.r.t. chosen interestingness measures. Then the ordered set is considered as a candidate set. The greedy covering strategy (Krimp) is applied to select the most interesting and diverse patterns. The original workflow and the adapted version that is used in the paper are given in Figure 3. Apply greedy strategy to cover data length and frequency

Compute closed (frequent) patterns

Reorder patterns w.r.t.

Apply greedy strategy to cover data an interestingness measure Fig. 3. The workflow for pattern mining by the original Krimp and its adapted version.

In the next section we show how the embedding of background knowledge (i.e. reordering of patterns w.r.t. interestingness measures) affects the results of pattern mining.

MDL in Closed Itemset Mining

In the worst case a concept lattice contains an exponential number of partially ordered intents (concepts), the application of MDL allows for the selection of a small subset of intents. Our experiments show that the application of the MDL principle allows for significant reduction in the number of patterns (up to 5% of the formal concepts, see Table 2). In the context of measure-based pattern mining, the application of MDL makes the measure-based selection threshold-free. More than that, a set of the MDL-optimal patterns has better characteristics than the top-n patterns. First of all, almost the same concepts (intents) are removed from the set of selected patterns. In our experiments we call this property "non-redundancy". For a set of patterns to be "non-redundant" means to have the following characteristics: differ from the most similar pattern in the set (i.e., distance to the 1st nearest neighbor), make shallow hierarchy by inclusion B 1 ⊂ B 2 ⊂ . . . ⊂ B n (i.e., average length of the longest paths built from partially ordered itemsets) and do not have a lot of more general patterns

B i ⊂ B, i ∈ [1, k] (the rate of patterns with children).
If we compare the sets of top-n and MDL-optimal patterns of the same size we will see, as a side effects of the "non-redundancy", that MDL-optimal patterns cover in total more data ("crosses" in a formal context) being diverse and interesting w.r.t. a given measure.

It is clear to see that MDL approach not only dispenses from predefined thresholds but also filter out similar interesting patterns and provides more comprehensive data description.

We examine the following orders of patterns:

area f r lif t(B) = f r(B) • lif t(B), area len f r(B) = len(B) • f r(B), area len lif t(B) = len(B) • lif t(B)
and sequential ordering by len and f r, len and lif t, lif t and len (the patterns 4). An example of ordering for frequent closed itemsets (frequency is greater than 2) for the running example is given in Table 1. The discretized datasets from LUCS-KDD repository [4] were used in the study, the parameters of the datasets are given in Table 2. We split each dataset into 10 parts and in each of 10 experiments we use 9 of them as a training set and one part as a test set.

In this section we compare characteristics of MDL-optimal with top-n itemsets, patterns in both sets are ordered w.r.t. the same interestingness measure. The size of a set of top-n itemsets is equal to the size of a set of MDL-optimal patterns. The scheme of computing these sets is given in Figure 4. We compare the sets of patterns within the following properties: non-redundancy, data covering and representativeness.

Non-redundancy

By redundant set of patterns we mean a set of patterns that contains a lot of similar itemsets. We measure redundancy by three parameters: average distance to the 1st nearest neighbor, average length of the longest paths built from partially ordered itemsets, and average number of itemsets that have at least one more general itemset (child).

Distance to the 1st nearest neighbor. To compute this parameter we represent patterns as binary vectors and take into account the smallest Euclidean distance between each pattern and the remaining patterns in the pattern set. The average value for a pattern set is taken as the average distance to the 1st nearest neighbor.

A set containing a lot of similar patterns will have low average values, see Figure 5 (1) for an example. As it can be seen from Figure 6 (1), the MDL principle provides much more distinctive itemsets. Top-n concepts have a lot of similar patterns, while MDLoptimal ones are pairwise distinctive (w.r.t. Euclidean distance).

Average length of the longest paths built from partially ordered itemsets. The patterns can be partially ordered by inclusion, i.e. B 1 ⊂ B 2 ⊂ . . . ⊂ B n , where B n is the most specific patters and B 1 is the most general one. We call this ordered sequences paths. If B n ⊆ g then B i ⊆ g is guaranteed for all i ∈ [1, n -1]. Longer paths contain more patterns describing the same objects. Thus, a long path can be considered as an indicator of redundancy. In other words, these patterns characterize the same objects at different levels of abstraction and contain only a few new details w.r.t. the nearest neighbors in the path. Short paths correspond to "flat" structures with more varied patterns. An example of comparison of two tiny pattern sets is given in Figure 5,(2).

As we see in Figure 6 (b), for ordering w.r.t. len (see len f r and len lif t) the MDL priciple does not provide any benefits, while its application to area len sep and area sep lif t, lif t len f r allows for more flattened structures, even more flattened than with len. It means that pattern mining with area len sep and area sep lif t, lif t len f r can be significantly improved by the application of MDL. The average length of the longest paths is 2.5.

S3

(2) The longest paths built on partially ordered patterns (by inclusion).

--bc de ac

The rate of pattern with children is 0.

- - + + + ac abc de cde de ac bcde cde, de
The rate of pattern with children is 3/5. (3) The rate of patterns with children (i.e. more general / short patterns). Fig. 5. Non-redundancy measures computed for patterns set given in Figure 1. The set S3 (column 1) is better than S2 (column 2) w.r.t. all the parameters: the average distance is higher, the average length of the longest paths and the rate of patterns with children are smaller.

(1) Distance to the 1NN (2) The average path lengths

(3) Rate of patterns with children.

Fig. 6. Non-redundancy parameters: (1) the average distance to the 1st nearest neighbor for itemsets selected with MDL and top-n itemsets; (2) the average length of the longest paths computed on the chain of itemsets formed by inclusion of its attributes;

(3) the average rate of itemsets with children. On the X-axis is different orderings of patterns, on the Y -axis is the values of the listed above non-redundancy parameters for MDL-optimal set (blue) and top-n (green) set of the same size.

Average number of itemsets with children (more general itemsets). This parameter characterizes the uniqueness of patterns in a set, absence of the second pattern B 2 ⊂ B 1 that characterizes the same subset as a more specific one. This parameter is related to the previous measure, but it indicates just an amount of itemsets having at least one more general itemset. An example of computing this parameter is given on Figure 5, (3). The results of experiments (see Figure 6, (c)) show that the MDL principle selects more distinctive itemsets than top-n itemsets.

Data coverage

A subset of selected patterns can be considered as a concise representation of a dataset. Thus, it is important to know how much information is lost by compression. We measure this parameter by the rate of covered attributes. Values close to 1 correspond to the lossless compression.

The average covering rate is given in Figure 7 (1). With the same number of patterns MDL ensures better covering. For area f r lif t, area len f r and area len lif t MDL-optimal set covers much more data than top-n patterns.

Itemset typicality (representativeness)

In our experiments we also address typicality of patterns. In this study we measure it by the usage of patterns. To compute usage we consider the ordered patterns (in case of MDL, top patterns are those that have the shortest encoding length, for top-n they are top-patterns w.r.t. a chosen measure). The ordered patterns are used one by one to cover data. The attributes are covered only ones (disjoint covering by patterns). The number of times a patterns is used in the covering is its usage, thus the usage does not exceed the pattern frequency. For example, in Figure 2 (4), the frequency of bc is 2, but it can be used only one time to cover (b)(c)(de), since in (ac)(b) only b is left to cover.

It should be noted that it is not obvious which values are better. The usage serves to characterize a subset of patterns. The high values correspond to a subset of common patterns, while low values indicates that a subset contains less typical, but still interesting (w.r.t. interestingness measures) patterns.

Figure 7(2) shows the average usage for MDL-optimal and top-n patterns. The usage of MDL-optimal patterns is almost the same for different orders while the usage of top-n is dependent on ordering.

Conclusion

In the paper we propose a new approach to the measure-based pattern mining. It can be considered as an "implementation of the MDL principle under constrains" or "embedding of background knowledge (on interestingness) into MDL". We took the Krimp algorithm as a basic implementation of MDL and studied a range of interestingness measures within it.

The proposed approach is a threshold-free method for the selection of a small set of patterns having desired properties. The chosen patterns are diverse and varied, they cover almost all attributes of objects.

The studied Krimp algorithm can be changed further to improve (closed) pattern mining as follows. The greedy strategy may be relaxed, i.e., overlapping patterns can be used to cover an object. Some additional mechanism may be proposed to deal with noisy data (missed values).

Introduction

A tolerance relation or simply a tolerance is a reflexive and symmetric binary relation τ on a non-empty finite set V . The pair (V, τ ) =: T is called tolerance space. An introduction to tolerance spaces together with applications can be found in [10] and [11].

For a tolerance τ on V , a non-empty subset S ⊆ V induces a square in τ if S × S ⊆ τ . If S is maximal with respect to set inclusion, then S × S defines a maximal square.

The set of all maximal squares of T is denoted by Sq(T) and determines the tolerance τ , that is τ = Sq(T). But often not all squares are necessary to cover τ . This motivates the definition of the square cover number, sc(T), of a tolerance space T, as the minimal number of maximal squares necessary to cover τ .

sc(T) :

= min{k | ∃ S ⊆ Sq(T), τ = S, |S| = k}. ( 1
)
In [7] the direct product (defined in Section 2) of tolerance spaces was treated by means of formal concept analysis, which lead to the conjecture: Conjecture 1. Let T 1 and T 2 be tolerance spaces. For their direct product

T 1 × T 2 it holds that sc(T 1 × T 2 ) = sc(T 1 ) + sc(T 2 ).
When we analysed Conjecture 1, it turned out that it is not valid in general. Still, we will provide a sufficient condition for this conjecture to hold (Section 5). The meta framework for this will be formal concept analysis, introduced in Section 2, together with some tools from graph theory (Section 4). Additionally, we will treat the rectangle cover number of the direct product of formal contexts in Section 3 and Section 6 provides example classes of tolerance spaces for which the square cover number and rectangle cover number are equal. Lastly, Section 7 analyses a construction principle for tolerance spaces, which is based on formal contexts.

Formal Concept Analysis

In this section, we will provide the definitions and facts from formal concept analysis (see [5]) that will be used in the sequel.

A formal context (or in short context) is a triple K = (G, M, I), where the incidence I ⊆ G × M is a binary relation. For A ⊆ G and B ⊆ M , we define two derivation operators: Let ∪ denote the disjoint union of sets. We define four binary operations on contexts

A I := {m ∈ M | ∀a ∈ A : (a, m) ∈ I} = a∈A {a} I , B I := {g ∈ G| ∀ b ∈ B : (g, b) ∈ I} =
K 1 = (G 1 , M 1 , I 1 ) and K 2 = (G 2 , M 2 , I 2 ). The direct product K 1 × K 2 := (G 1 × G 2 , M 1 × M 2 , I 1 × I 2 ) with ((g, h), (m, n)) ∈ I 1 × I 2 :⇐⇒ (g, m) ∈ I 1 or (h, n) ∈ I 2 , the cardinal product K 1 × K 2 := (G 1 × G 2 , M 1 × M 2 , I 1 × I 2 ) with ((g, h), (m, n)) ∈ I 1 × I 2 :⇐⇒ (g, m) ∈ I 1 and (h, n) ∈ I 2 , the direct sum K 1 ⊕ K 2 := (G 1 ∪ G 2 , M 1 ∪ M 2 , I 1 ∪ I 2 ∪ G 1 × M 2 ∪ G 2 × M 1 ),
and the disjoint union

K 1 ∪ K 2 := (G 1 ∪ G 2 , M 1 ∪ M 2 , I 1 ∪ I 2 ).
The two products fulfill De Morgan laws

(K 1 × K 2 ) c = K c 1 × K c 2 and (K 1 × K 2 ) c = K c 1 × K c 2 , ( 2
)
the relation I 1 × I 2 can be expressed as

I 1 × I 2 = (G 1 × M 1 ) × I 2 ∪ I 1 ×(G 2 × M 2 ), (3)
and we will denote the incidence relation of the direct sum by

I 1 ⊕ I 2 .
A context K is crossed, if the adjacency matrix A I of its incidence I has at least one full row and one full column. If A I has at least one empty row and one empty column, we say that K is co-crossed. In case of two crossed contexts, we can express the concept lattice of the cardinal product as the direct product (in terms of Universal Algebra) of each factors concept lattice (see [3]).

B(K 1 × K 2 ) ∼ = B(K 1 ) × B(K 2 ). ( 4
)
The concept lattice of the direct sum is isomorphic to the direct product of each components concept lattice too1 .

B(K 1 ⊕ K 2 ) ∼ = B(K 1 ) × B(K 2 ). (5)
Let P = (P, ≤ P , 0 P , 1 P ) and L = (L, ≤ L , 0 L , 1 L ) be bounded posets such that P ∩ L = ∅. The poset S = (S, ≤, 0, 1), with P * := P \{0 P , 1 P }, L * := L\{0 L , 1 L }, S * := P * ∪ L * , S := S * ∪ {0, 1} and ≤:=≤ P ∪ ≤ L ∪{0} × S ∪ S × {1}, is called the horizontal sum of (P, L) and is denoted by P + L := S.

For the disjoint union of two contexts, the resultant concept lattice is the horizontal sum of each components concept lattice.

B(K 1 ∪ K 2 ) ∼ = B(K 1 ) + B(K 2 ). (6)
Next, since a concept (A, B) with non-empty sets A and B induces a maximal rectangle A × B in I, we define the rectangle cover number (see also [12]), rc(K), of a context K as

rc(K) := min{k | ∃ F ⊆ B(K), I = (A,B)∈F A × B, |F| = k}. ( 7
)
The Boolean rank, r B (C), of an n × m Boolean matrix C is the least integer k such that Boolean m × k and k × n matrices with C = A • B exist (see [1]). In [1] it is implicitly shown that:

rc(K) = r B (A I ). (8)
Lastly, we recall some aspects of dimension theory. For a concept lattice B(K), its 2-dimension, dim 2 (B(K)), is the smallest number of chains of cardinality 2 in whose direct product it can be order-embedded. Since the n-fold direct product of chains of cardinality 2 is isomorphic to the powerset lattice of the n-element set n, there exists φ :

B(K) → P(n) with (A, B) ≤ (C, D) ⇐⇒ φ(A, B) ≤ φ(C, D). A Ferrers relation is a relation F ⊆ G×M such that (g, m), (h, n) ∈ F implies (g, n) ∈ F or (h, m) ∈ F . This is equivalent to B(G, M, F ) being a chain. The length l of F is defined as l(F ) = |B(G, M, F )| -1. For a context K its Ferrers 2-dimension, fdim 2 (K), is the smallest number of Ferrers relations F t , t ∈ T with l(F t ) < 2, so that I = t∈T F t .
The above defined dimensions are equal and are related to the rectangle cover number via the complementary context, that is:

rc(K) = fdim 2 (K c ) = dim 2 (B(K c )). ( 9
)

The Rectangle Cover Number of the Direct Product of Formal Contexts

In this section, we will treat the rectangle cover number of the direct product of two contexts K 1 and K 2 . From Identity 3, it follows that rc(K 1 × K 2 ) ≤ rc(K 1 ) + rc(K 2 ). We will provide a sufficient condition for equality. Therefore, we will need a proposition about the Ferrers 2-dimension of the direct sum of two contexts. This proposition and its use in Theorem 1 is inspired by [14].

Proposition 1. For the direct sum of two contexts

K 1 = (G 1 , M 1 , I 1 ) and K 2 = (G 2 , M 2 , I 2 ), it holds that fdim 2 (K 1 ⊕ K 2 ) = fdim 2 (K 1 ) + fdim 2 (K 2 ).
Proof. The claim follows from Identity 9 with interchanged roles of K and K c , and the structure of the relation (I 1 ⊕ I 2 ) c depicted in Figure 1.

I1 ⊕ I2 M1 M2 G1 I1 G1 × M2 G2 G2 × M1 I2 (I1 ⊕ I2) c M1 M2 G1 I c 1 ∅ G2 ∅ I c
2 Theorem 1. Let K 1 and K 2 be co-crossed contexts. For the rectangle cover number of their direct product it holds that:

rc(K 1 × K 2 ) = rc(K 1 ) + rc(K 2 ).
Proof. First, we notice that K c 1 and K c 2 are crossed contexts. From Proposition 1, and Identity 2, 4, 5 and 9, we conclude that

rc(K 1 × K 2 ) = fdim 2 ((K 1 × K 2 ) c ) = fdim 2 (K c 1 × K c 2 ) = dim 2 (B(K c 1 × K c 2 )) = dim 2 (B(K c 1 ) × B(K c 2 )) = dim 2 (B(K c 1 ⊕ K c 2 )) = fdim 2 (K c 1 ⊕ K c 2 ) = fdim 2 (K c 1 ) + fdim 2 (K c 2 ) = rc(K 1 ) + rc(K 2 ).
Remark 1. In case that the hypothesis for both factors to be co-crossed does not hold, the simplest example to consider would be I := ({g}, {m}, {g} × {m}). It is crossed and for any non-empty context K, it holds that rc(K × I) = 1 < rc(K) + 1 = rc(K) + rc(I).

Without providing a formal definition, we restate Theorem 1 for Boolean matrices. Since in this case the term direct product would not be appropriate, we will use the established notion Cartesian sum from graph theory (see [9]). Identity 8 implies: Corollary 1. Let A 1 and A 2 be Boolean matrices with at least one empty row and one empty column. For the Boolean rank of their Cartesian sum it holds that r B (A

1 × A 2 ) = r B (A 1 ) + r B (A 2 ).

Edge Clique Covers of Simple Graphs

In order to analyse the square cover number of tolerance spaces, we will use some results from graph theory which will be introduced in this section. A graph is considered as a relational structure G = (V, E) with vertex set V and an irreflexive, symmetric binary relation The edge clique cover number of a graph G, θ e (G), is the smallest number of cliques such that their edges cover the edges of G. For a graph with n vertices, we have that θ e (G) ≤ ⌊n 2 /4⌋, in which equality holds for the graph K ⌊n/2⌋,⌈n/2⌉ (see [13]).

E ⊆ V × V . Let E ref denote
θ e (K ⌊n/2⌋,⌈n/2⌉ ) = ⌊n 2 /4⌋. ( 10
)
The following proposition relates θ e to the square covering number.

Proposition 2. Let G be a graph and T be a tolerance space. It holds that

θ e (G) = sc(G ref ) and sc(T) = θ e (G T ).
Another graph parameter related to cliques is the vertex clique cover number,

θ v (G)
, that is the smallest number of cliques, such that their vertices cover all vertices of G.

Lastly, we describe the concept lattice of a graph G and the relationship between graph homomorphisms (edge preserving maps) and certain maps between concept lattices of graphs. In [15], concept lattices of graphs are studied under the name neighborhood ortholattice. It is shown that B(G) is a complete ortholattice, that is a complete bounded lattice with an involutory antiautomorphism c, such that x ≤ c(x) implies x = 0. We define an abstract orthogonality relation through

x ⊥ y :⇐⇒ x ≤ c(y).
An orthomap between complete ortholattices preserves order and orthogonality, and maps only the bottom element of the domain lattice to the bottom element of the codomain lattice. The next theorem relates graph homomorphisms to orthomaps.

Theorem 2 ([15]

). A graph homomorphism from G 1 to G 2 exists if and only if there exists an orthomap from B(G 1 ) to B(G 2 ). Furthermore, it is shown in [15] that the concept lattice of K n is isomorphic to the powerset lattice of an n-element set: B(K n ) ∼ = P(n).

The Square Cover Number of the Direct Product of Tolerance Spaces

This section treats Conjecture 1, i.e., for tolerance spaces T 1 and T 2 :

sc(T 1 × T 2 ) = sc(T 1 ) + sc(T 2 ).
First, similar to Remark 1, we see that Conjecture 1 is false for an arbitrary tolerance space T 1 , and T 2 = ({v}, {v}, {v} × {v}). Second, due to Identity 3, it always holds that sc(T 1 × T 2 ) ≤ sc(T 1 )+sc(T 2 ). The question for which tolerance spaces equality holds remains. An analogue to Theorem 1 can not exist, since tolerance spaces, due to their reflexivity, can not be co-crossed.

In order to be able to make use of the the rectangle cover number, we will relate the square cover number, sc(T), to the rectangle cover number, rc(T). Since every square is also a rectangle, it holds that for any tolerance space, the rectangle cover number is less or equal to the square cover number. rc(T) ≤ sc(T). (11) But, the reverse inequality is wrong in general. To see this, we notice that rc(T) = r B (A τ ) ≤ |V | (see [1]). Consequently, a tolerance space with square cover number larger than |V | would provide a counter example. From Identity 10 and Proposition 2, we conclude that 6 = sc(K ref 2,3 ) > rc(K ref 2,3 ) = 5 (see Fig. 3). This motivates the following definition.

Definition 1. We will say that a tolerance space T has the balanced covering property (in short BCP) if sc(T) = rc(T).

This definition leads immediately to:

Theorem 3. Let T 1 and T 2 be tolerance spaces with the BCP, such that rc(T 1 × T 2 ) = rc(T 1 ) + rc(T 2 ). It follows that sc(T 1 × T 2 ) = sc(T 1 ) + sc(T 2 ).

Proof. It always holds that sc(T 1 × T 2 ) ≤ sc(T 1 ) + sc(T 2 ). From the BCP of T 1 and T 2 , and Inequality 11, we conclude the reverse direction

sc(T 1 ) + sc(T 2 ) = rc(T 1 ) + rc(T 2 ) = rc(T 1 × T 2 ) ≤ sc(T 1 × T 2 ).

Tolerance Spaces with the balanced covering property

In this section, we will provide examples of tolerance spaces which have the BCP.

Example 1. The following is inspired by [8]. A covering H ⊆ P(V ) of V is irredundant if H\{X} is not a covering of V for any X ∈ H. An irredundant covering induces the tolerance τ H := {X ×X | X ∈ H} with underlying tolerance space T H := (V, τ H ). It follows that sc(T H ) ≤ |H|. Since, H is an irredundant covering, for every X ∈ H there exists v ∈ X, such that X × X is the only maximal square which is covering (v, v). Hence, the squares X × X with X ∈ H are mandatory (see [1] for mandatory factors in the sense of factor analysis) for every covering of τ H , which implies sc(T H ) = rc(T H ) = |H|. Furthermore, note that tolerances induced by irredundant coverings can be considered as the reflexive closure of graphs G with θ e (G) = θ v (G) (see [2] Theorem 1) and that equivalence relations are a special case of such tolerances.

Next, we will describe the structure of the graphs G = (V, E) whose underlying relation E is the complement of a tolerance induced by an irredundant covering.

Theorem 4. Let T = (V, τ ) be a tolerance space and G = (V, E) the graph defined through G := T c . If the tolerance τ is induced by an irredundant covering

H ⊆ P(V ) with |H| = n, then G is a connected graph with K n as a retract 2 .
Proof. In [8] it is shown that B(G) is an atomistic boolean lattice if τ is induced by an irredundant covering. Since we only consider finite tolerance spaces, this means that B(G) is isomorphic to a powerset lattice. We denote the isomorphism by Φ and show that it is an orthomap.

Since it is an isomorphism it preserves order and only the bottom element of the domain lattice is mapped to the bottom element of the codomain lattice. Consequently, just the preservation of orthogonality is left to show:

x ⊥ y ⇒ x ≤ c(y) ⇒ Φ(x) ≤ Φ(c(y)) = c(Φ(y)) 3 ⇒ Φ(x) ⊥ Φ(y).
The same holds for the inverse Φ -1 so that we have orthomaps B(G) → P(n) and P(n) → B(G). Theorem 2 implies the existence of two graph homomorphisms

φ 1 : G → K n and φ 2 : K n → G. Since φ 2 must be an embedding, it can be defined such that φ 1 • φ 2 = id G holds.
Lastly, we notice that G must be connected. Otherwise B(G) would be equal to the horizontal sum of the connected components of G (see Identity 6). But B(G) ∼ = P(n) implies that for n ≥ 3 and n = 1, the concept lattice B(G) can not 2 A graph G is a retract of H if there exist graph homomorphisms φ : G → H and ψ : H → G such that the composite ψ • φ is the identity on G. 3 The last equality is a consequence of the fact that the isomorphic image of an orthocomplemented lattice is again an orthocomplemented lattice. Just define c(Φ(x)) := Φ(c(x)). Since the powerset lattice has a unique orthocomplementation, this is the only possible choise for c.

be horizontally decomposed. For n = 2, the graph G must have two connected components such that their concept lattice is a chain. This is a contradiction, since the underlying relation of a graph can not be a Ferrers relation.

Example 2.

In this example we generalize the construction of (K ⌊n/2⌋,⌈n/2⌉ ) ref (see Section 4 and Figure 3). For this purpose let K be a context. We consider T := (K ∪K d ) ref , the reflexive closure of the union of K and K d . This construction yields the reflexive closure of a bipartite graph with disjoint vertex sets G and M , such that we draw a line from g ∈ G to m ∈ M whenever gIm holds. It follows that every element of I induces a maximal clique in this bipartite graph and hence a maximal square in (I ∪ I -1 ) ref (Fig. 4). In [6] the concepts of B(T) are , where E X denotes the identity on X . Example 3. A further example is the symmetrization K s of a context K (see [7]). It is defined as

(I ∪ I -1 ) ref : G M G EG I M I -1 EM characterized. Let {a}, A ⊆ G
K s := K ⊕ K d = (G ∪ M, G ∪ M, I ∪ I -1 ∪ G × G ∪ M × M ) (Fig. 5). Every concept (A, B) of K induces a maximal square (A ∪ B) × (A ∪ B).
More generally, every concept of K s has the form (A ∪ D, B ∪ C), in which (A, B) and (C, D) are concepts of K. Hence, a minimal rectangle cover of K induces a set of maximal squares which cover I and I -1 , but G × G and M × M may not be covered. It follows that rc(K) ≤ rc(K s ) ≤ rc(K) + 2 and that rc(K) ≤ sc(K s ) ≤ rc(K) + 2. If sc(K s ) = rc(K), the BCP sc(K s ) = rc(K s ) follows from Inequality 11.

K s G M G G × G I M I -1 M × M A graph G with G c = K ⊕ K d consists
of two empty graphs on G and M , such that their vertices are symmetrically connected via K c

Construction of Tolerance Spaces

In this section, we will analyse a construction principle for tolerance spaces which is based on formal contexts. Example 2 and 3 suggest that we consider a triple (A, K, B) with tolerance spaces A = (G, G, α), B = (M, M, β) and a context K = (G, M, I). That triple defines the tolerance space T := (G∪M, I ∪I -1 ∪α∪β) (Fig. 6). The interaction of α, I and β determines the structure of the tolerance space. This fact can be interpreted as a bipartite graph defined through I, such that α and β are tolerance relations on the disjoint vertex sets (Fig. 7). In the context of clique partitions of graphs, this was already observed in [4].

If I is the empty relation, then rc(T) = rc(A)+rc(B) and sc(T) = sc(A)+sc(B). For ||G| -|M || ≤ 1 and I = G × M , as well as α, β equal to the identity relation, the square cover number sc(T) is maximal. In this case, an increase of the elements of α and β can only reduce the square cover number. Generally, if I has many edges, more edges in α and β are necessary for a small square cover number, because one has to connect the edges of I into just a few maximal squares.

For arbitrary I, α and β, we state the following theorem.

Conclusion

This paper analysed rectangle covers of the direct product of formal contexts. If the contexts are co-crossed, then the rectangle cover number of the direct product is equal the sum of each factors' rectangle cover number.

In the next step, we treated the square cover number of the direct product of tolerance spaces. If each factor has the balanced covering property (BCP), which means that its square cover number is equal to its rectangle cover number, then additivity of the rectangle cover number with respect to the direct product transfers to the square cover number.

Lastly, we provided a variety of examples for tolerance spaces which have the BCP, analysed the corresponding graphs and introduced a construction principle for tolerance spaces based on formal contexts.

The theory and practice of coupling formal concept analysis to relational databases

Jens Kötters and Peter W. Eklund † †School of Information Technology Deakin University, Geelong, Australia

Abstract. In Formal Concept Analysis, a many-valued context is a collection of objects described by attributes that take on more than binary values, such as age (as integers or ranges of integer values) or color (a list or even a hierarchy of color combinations). Conceptual scaling is the process by which such a many-valued context is transformed into a formal context, by associating a concept lattice with the many-valued context. A many-valued context can be compared to a single table in a relational database populated with multiple rows and non-binary values. A generalization of conceptual scaling as a relational database as a whole should take into account the relations between objects, as expressed by means of foreign keys. Previous approaches to scaling a relational database (e.g. relational scaling) take such relations into account, but either do not maintain a separation between objects and values, which is characteristic for the unary case, or result in unary contexts only. In the approach presented in this paper, the use of n-ary scales is suggested, whereby a relational database is transformed into a family of n-ary contexts (a so called power context family). This paper describes the fundamentals of a Web application that allows connection to a relational database, its scaling interactively into a power context family, and navigation within that context family.

Keywords: Formal concept analysis, relational databases, conjunctive queries, data navigation, power context families, conceptual scaling.

Background and Motivation

In a previous paper [12], a variant of Formal Concept Analysis was introduced that uses conjunctive queries as concept intents, and resulting tables as concept extents. The resulting complete lattice of these conjunctive-query/table pairs1 is a mathematical model of the information space over a relational database (accessible through conjunctive querying). Conjunctive queries correspond to a subset of logical formulas over a relational signature Σ (i.e. Σ is the query vocabulary), and thus have interpretations in a relational structure, which represents the database.

When representing a database by a relational structure, we have to decide whether the carrier set should consist of table entries or table rows. The importance of this decision is that it determines what the query variables represent; queries will then either be formulated in the domain calculus or in the tuple calculus(cf. [1, p.74]). The domain calculus is a natural choice if all database tables represent relations (not just technically, but also conceptually) between objects. We might then employ a simple one-to-one correspondence between databases and relational structures: the n-column tables are precisely the n-ary relations in the relational structure, and the query vocabulary Σ is the set of table names, which are used as n-ary predicates.

In practice, databases are centered around object tables in the ORM-style, and the above modeling option does not reflect how users conceptualize database content. Because objects are represented by table rows, these should constitute the carrier set, so that the relational structure provides interpretations for the tuple calculus (which is also used by SQL [1, p.74]). But, unlike in the hypothetical case above, there is no immediate suitable choice of relations. While the signature Σ should express conditions in a WHERE-clause, meaningless comparisons (e.g. t.age = t.shoe size) should be eliminated in the formation of concepts.

In this paper, we propose a method to build meaningful query vocabulary around a relational database with reasonable effort. To this end, we utilize an alternative formalization [13] of the conjunctive-query lattice model [12] consistent with Wille's concept graphs [18], work which relates FCA to Sowa's Conceptual Graphs [17]. In particular, the relational database is represented by a power context family [18], i.e. by a sequence of formal contexts.

Power context families and relational structures correspond to each other in an almost trivial way: the columns of the n-th context correspond to n-ary relations, i.e. its attributes are the n-ary symbols of Σ. But the change of formalism encourages to think about databases in terms of conceptual scaling [5, Section 1.3]. Conceptual scaling is a method of deriving a formal context from a manyvalued context, which can be seen as a database table with value columns only (no foreign keys). Huchard et. al. [10] have presented a way to obtain a context family from a database (a set of many-valued contexts, together with binary inter-object relations), but only unary contexts (where attributes represent object properties) are obtained. The idea of scaling a database into a power context family has been formulated under the title of relational scaling [14,8], but the domain calculus has been used, which may have been the reason for a conflation of objects and values, in so doing destroying the analogy to conceptual scaling. Our scaling approach adheres to the analogy by maintaining a clear separation between objects and values, which in turn leads to generic and reusable scales so that (after the initial creation of scales) scaling a database can be done on a point-and-click basis.

Section 2 describes the graph representation of conjunctive queries that is used throughout this paper. The SQL translation of graphs is detailed in Sect. 3. The scaling approach is described in Section 4. The scales are not only used for the creation of the power context family; they define facets, which control the user options in a navigation application. Navigation in the power context family is discussed in Section 5. In this context, we revisit previous work on concept graphs and propose a new definition.

Conjunctive Queries

Conjunctive queries are a natural subset of database queries with nice theoretical properties [6]. Different representations for conjunctive queries are in popular use, including tableaux, formulas and Datalog rules [1]. In this paper, we represent conjunctive queries with windowed intension graphs [13] (similar to conceptual graphs [17]). An example windowed intension graph is shown in Fig. 2. This represents a query for 20th-century-born British authors who published in the 21st century. The rectangles are called object nodes and the rounded rectangles relation nodes. All object nodes of a query take on the role of variables. Colored nodes represent the subject(s) of the query; they are called subject nodes. Only object nodes can be subject nodes. The window represents the choice of subject nodes; so it can be thought of as a window into the data. Every object node carries a sort label, and a subject node carries in addition a marker, so that the combined label is of the form sort/marker. Every subject node is associated with a column in the result table, and the marker specifies the name of that column. The available sorts are precisely the table names in the database.

Each relation node is connected to object nodes by n ≥ 1 outgoing arrows, labeled from 1 to n. A node with n outgoing arrows is said to have arity n. Two or more arrows may point to the same object node. A relation node carries one or more labels of the form facet:attribute. An attribute is a name for an n-ary relation, and a facet acts as a namespace for attributes. The label facet:attribute states that attribute applies to the objects at the end of the arrow tips (the i-th arrow points to the i-th argument). If a node label comprises two or more attributes, they must belong to the same facet.

A relation sort is an n-tuple (s 1 , . . . , s n ) of table names. A facet only provides attributes of a single relation sort (s 1 , . . . , s n ), which means that its attributes may only occur on n-ary relation nodes whose i-th arrows point to objects of sort s i (i = 1, . . . , n). The nationality and DOB facets of Fig. 2 provide unary relations on Authors, pubdate provides unary relations on Books and wrote binary relations from Authors to Books.

Formally, an intension graph (cf. Fig. 1) is a 4-tuple (V, E, ν, κ) where V is the set of object nodes, E is the set of relation nodes, ν(e) := (v 1 , . . . , v n ) is the n-tuple of object nodes connected to e ∈ E, and κ(u) is the label on the node u ∈ V ∪ E. In the original definition of intension graphs [13], ν was required to be injective, so it was omitted. This is convenient for theory, but multiple edges make sense when working with facets.

A windowed intension graph is formalized as a pair (λ, G), where G is an intension graph and λ : X V G is a partial map from a set X of markers to the object nodes of G.

SQL Translation

A facet c provides an SQL-interpretation of its attributes by means of a function Φ c , which maps an attribute a to a WHERE-condition Φ c (a) in the syntax of the target database. If the attribute a has sort (s 1 , . . . , s n ), then Φ c (a) contains the placeholders t 1 , . . . , t n , which have to be replaced by the respective arguments in every concrete case. The expressions below interpret the attributes of the graph in Fig. 2 in terms of the schema of the database in Fig. 3.

Φwrote(wrote) ≡ t1.id = t2.author (1)
Φ nationality (GB) ≡ t1.nationality="GB"

Φ DOB (20C) ≡ t1.date of birth BETWEEN "1999-01-01" AND "1999-12-31"

Φ pubdate (21C) ≡ t1.publication date BETWEEN "2000-01-01" AND "2099-12-31" (4)

To obtain a result table as in Fig. 3, we have to specify in addition how the objects of each sort (i.e. the rows of each table) are printed. This is achieved by fixing an output expression Ω s for each sort s. For the sorts of the database in Fig. 3 we specify

Ω Author ≡ CON CAT (t1.f irst name, " ", t1.last name) , (5)
Ω Book ≡ t1.title . (6)
The SQL translation of a windowed intension graph is thus given by a statement of the following form:

SELECT DISTINCT Ω sort(u1) (u 1 ) AS x 1 , ...,

Ω sort(um) (u m ) AS x m FROM sort(v 1 ) AS v 1 , ..., sort(v n ) AS v n
WHERE Φ c1 (a 1 )(v 11 , ..., v 1n1 ) AND ...

AND Φ c k (a k )(v k1 , ..., v kn k ) (7)
In eqn. (7), the object nodes are represented by variables v 1 , . . . , v n , and the FROM-clause can be seen as a variable declaration, which declares v i to be of sort sort(v i ). In SQL terminology, v i is called a table alias. The WHERE-clause contains for each attribute c j : a j a WHERE-condition Φ cj (a j )(v j1 , . . . , v jnj ), where Φ cj (a j )(v j1 , . . . , v jnj ) denotes substitution of t i by the applicable table alias v ji . The FROM-WHERE-part realizes the query's underlying intension graph (cf. Fig. 1). The SELECT-clause defines an output column for each marker x i on a subject node u i . In SQL terminology, x i is called a column alias. So far, result tables display objects, but no values are shown beyond those that occur in the output expression (cf. Fig. 3). In a navigation application user interface (cf. Sect. 5), we envision relation nodes as controls to show in addition (or hide) the column values associated with a facet, by modifying the SELECTclause in eqn. (7). These additional columns are not part of the concept extent, but they are of course informative. In the next section, we make precise how facets are associated with column values.

Database Scaling

A syntactic interpretation defines the symbols of a given signature by expressions over another signature (cf. [4]). The attributes provided by a facet c can be understood as symbols of a relational signature. The SQL-interpretation Φ c is in this sense a syntactic interpretation: namely it interprets the attributes of c in a given database schema S (which is not exactly a signature, but the databasetheoretic analogue).

Each facet c defines a context K c . This is how the extension of the attribute a of K c is defined:

SELECT Ω s1 (t 1 ), . . . , Ω sn (t n ) FROM s 1 AS t 1 , . . . , s n AS t n WHERE Φ c (a)(t 1 , . . . , t n ) (8)
Using eqns. ( 5) and (3) in eqn. ( 8), the 20C column in Fig. 4 is obtained. In this manner, the contexts for the DOB and pubdate facets (Figs. 4 and 7) and nominal scales (Fig. 8) [5]. The scale that underlies the DOB and pubdate facets is the Centuries scale in Fig. 11. The scales that we use to scale databases (i.e. generate context families from databases) should describe values that can occur in a database column; for the Centuries scale, these are ISO 8601 dates. Of course, it is generally not efficient or even possible to represent scales in the computer as cross-tables; we would expect the Centuries scale to describe all possible dates that can occur in a column, and not just the 17 dates of Fig. 11. A scale for a database must be able to produce an SQL definition for an attribute. The SQL definition for the 20C attribute is z 1 BETWEEN "1999-01-01" AND "1999-12-31" ,

where z 1 , z 2 , z 3 , . . . are variables reserved for values. A facet binds a scale to one or more columns (each variable z i is bound to a column). The Centuries scale is a unary scale, so its attributes are described by a single variable z 1 . The DOB facet binds z 1 to the Author.date of birth column (which yields Φ DOB , cf. ( 3)), whereas pubdate binds z 1 to Book.publication date. 2 . Scales encode the actual logic, whereas a facet merely translates a relation between values into a relation between objects, by means of a syntactic substitution that is specified by the binding. The scale interface and facet class are shown in Fig. 12.

Examples for binary scales are equality scales (Fig. 9), which have been used in a prototype to generate binary single-column contexts for foreign keys, or distance scales (Fig. 10), which can be used to measure spatial distance between objects, or time spans between events. A comparison to the classic unary scales (Figs. 7 and8) shows that these binary scales are in the same spirit.

A syntactic interpretation provides, in addition to symbol definitions, a formula that defines the carrier of the derived structure (cf. [4]). In our scaling approach, this is the object set of the derived context. We call this formula a domain expression and denote it by Φ c ( * ), where * is a special symbol. The domain expression for the contexts in Figs. 4 and 5 is a sort restriction. Ideally, the domain expression would also be a WHERE-condition, but SQL requires special treatment in this case. However, a WHERE-condition is allowed in addition to the sort restriction. The domain expression for the wrote facet is "t1.id=t2.author", where t1 is an Author and t2 is a Book. On top of this, the wrote facet uses a distance scale, bound to Author.date of birth and Book.publication date, to measure at what age an author wrote a particular book. A facet supports renaming of attributes to allow for more expressive attribute names than the generic names provided by the scales. The context derived from the wrote facet is the bottom context in Fig. 6.

The contexts that are derived from the facets can be assembled into a power context family (Fig. 6). Working with power context families is more convenient for mathematical investigations, whereas working with the contexts derived from the facets (as in Figs. 4 and5) is more convenient for practical work. As with the scales, it is not necessary that the power context family, or individual facets, are explicitly constructed. The power context family has been realized in a prototype as a virtual layer around the database, although the computation of refinement options (cf. Section 5) required an additional query, and SQL does not adequately support all types of scales (such as taxonomies), which may require post-processing of result tables.

≤1 ≤2 ≤3 ≤4 ≤5 1 × × × × × 2 × × × × 3 × × × 4 × × 5 × Fig. 7. Ordinal Scale Nominal =1 =2 =3 =4 =5 1 × 2 × 3 × 4 × 5 × Fig. 8. Nominal Scale Equality = (1,1) × (1,2) (1,3) (2,1) (2,2) × (2,3) (3,1) (3,2) (3,3) × Fig. 9. Equality Scale Distance =0 ≤1 ≤2 (1,1) × × × (1,2) × × (1,3) × (2,1) × × (2,2) × × × (2,3) × × (3,1) × (3,2) × × (3,3) × × ×

Navigation using Projectional Concept Graphs

The ideas of the previous sections can be turned to account in a navigation application. The viability of its core features has already been explored in a prototype; a full version will be presented in an upcoming paper.

The application provides for two roles, user and admin. In the admin role, one can connect to an existing database, view its schema and a list of available scales, bind scales to database columns (thus scaling the database) and store the binding, together with the database connection info, in a file (i.e. the database can be read-only). A binding, together with the database that it references, constitutes a virtual power context family.

In the user role, one can choose from a list of available power context families to navigate in. Note that the user does not need to know that the power context family originates from a relational database, and indeed, there could be different back ends for different sources of data, such as RDF or object-oriented databases (although we have only worked this out for relational databases with SQL access). Different user interfaces are possible, but it is instructive to assume that a conjunctive query looks to the user like the graph in Fig. 2. As mentioned in Sect. 2, it is formalized by a windowed intension graph (λ, G).

A solution of an intension graph G in a power context family K is formalized by a map ϕ : G → K from object nodes to objects (of the context K 0 ). The set of all solutions is denoted by S(G, K). For a windowed intension graph (λ, G), the rows in the result table are the maps λ • ϕ with ϕ ∈ S(G, K). In the following, we introduce projectional concept graphs as a basic structure for navigation.

Definition 1 (Projectional Concept Graph).

A projectional concept graph is a 5-tuple (V, E, ν, κ, ext K ) comprised of an intension graph G := (V, E, ν, κ) and its extension map

ext K (v) := {ϕ(v) | ϕ ∈ S(G, K)} ( 10
)
for a given power context family K with S(G, K) = ∅ (i.e. ext K (v) = ∅ for all v ∈ V ). We call ext K (v) the node extent of v.

The node extent of the Author node in Fig. 1 is the extent of the windowed intension graph in Fig. 2. It is thus an extent in the lattice B 1 ( K) of unary concepts over the power context family K (cf. [13]). Therefore, projectional concept graphs should indeed be considered concept graphs.

Considering node extents rather than whole result tables spares the user going through large result tables; the navigation approach allows however to place windows of arbitrary size on the graph, if the specific combinations of objects in the solution are of interest.

Refinement options are given by a triple (E + , κ + , θ + ). For each v ∈ V , E + (v) is a set of facets for which a new relation node can be connected to v, extending the graph structure. For each u ∈ V ∪ E, κ + (u) is a set of scale concepts which can replace κ(u). And θ + is a set of pairs of object nodes in the graph which can be merged. All refinement options lead to a refined projectional concept graph that has at least one solution in K.

Related Work

Concept graphs and power context families were defined by Wille [18]. Relational context families, used in Relational Concept Analysis (RCA) developed by Huchard et. al, [9] are similar to power context families but define different contexts for objects of different sorts. The contexts derived from facets in this paper represent facets of such sort contexts. Faceted navigation on the basis of FCA was suggested by Priss [15] and later developed by Eklund and Ducrou [3]. In RCA, conceptual scaling is generalized to relations but produces unary contexts only. The idea of scaling databases into power context families was formulated by Prediger and Wille [14] and expanded on by Hereth [8]. The scales presented there correspond to facets in our work; a central idea to conceptual scaling, the translation of properties of values into properties of objects, is not reflected in this work, but is addressed by the scales in our work.

From the beginning, conceptual graphs have been considered as a database interface [16]. Their translation into logical formulas, stated by Sowa [17], seems to imply that an interpretation as conjunctive queries is intended for conceptual graphs with variables. An SQL translation of Wille's concept Graphs, which treats concept graphs as conjunctive queries, is described by Groh and Eklund [7]. Interpretations were provided by a power context family, but it was encoded in a database (which imposes a particular format), not derived from the database, so scaling (as we define it here) was not involved. Both object and relation nodes were considered variables, whereas in the present work, only object nodes are considered variables.

An intension graph can be thought of as Wille's abstract concept graph (see [18, p. 300]). A concept graph (in the standard definition) defines in addition a realization which, like the extension map in Def. 1, assigns to each object node a nonempty set of objects. In a concept graph, the elements of the sets (v) can be freely combined to obtain solutions, whereas for projectional concept graphs, each element of (v) is part of some solution.

The navigation approach of Sect. 5 has been described in [11]. FCA-based navigation in relational data is also the subject of [2].

Conclusion

This paper describes the fundamental theory of a Web application that allows connection to a relational database, its scaling interactively into a power context family, and navigation within that context family. The conceptual scaling approach used is based on a syntactic interpretation of attributes, which results in an FCA-based method to build suitable query vocabulary around a relational database. Generic and reusable scales allow easy database scaling on a pointand-click basis. Scales constitute facets in a faceted-navigation approach based on projectional concept graphs, which are a new class of concept graphs.

Introduction

Generalized metrics recently have become of increased interest for modeling directed distances with values in qualitative measurement spaces including ordered monoids and lattices. In [8] generalized metrics are proposed which turned out to be relevant for formal concept analysis and closure operators (see [4], [9], [10]).

In this paper, we will apply generalized metrics in order to compare ratings, that is comparing the rating methodologies of different rating agencies with different result scales. We analyze suitable result scales for the rating process and show that ratings are not limited to chain lattices but can as well use certain semimodular lattices as target. The paper also considers applications to formal concept analysis covering the extensional as well as the intensional point of view.

For our approach supermodularity plays an important role, which goes beyond ideas of measurement associated with Dempster-Shafer-Theory (see [10]).

A prior result on generalized metrics

In this section we recall a theorem on generalized metrics (compare [8]). We start with It is not quite obvious if functorial maps can be extended from ≤ P to the superset P × P , which gives rise to the following Question: For a given ∆ : ≤ P -→ M , does there exist a generalized quasi-metric d : P × P -→ M w. r. t. (P, M) which extends ∆ such that d| ≤ P = ∆?

We find a positive answer and sufficient conditions in the following Theorem 1 ( [8]) Let P = (P, ≤ P ) be a lattice and let M = (M, * , ε, ≤) be an ordered monoid. If a map ∆ : ≤ P -→ M is weakly positive, supermodular and functorial w. r. t. (P, M), then

d : P × P -→ M, (p, q) → ∆(p ∧ q, q)
is a GQM w. r. t. (P, M).

Application to ratings

In this section we formalize the rating process and show how to compare ratings from different sources.

Let O be a finite set of objects to be rated, prominent examples are financial entities which issue debt. There are different (credit) rating agencies applying different ratings, where a (credit) rating is a mapping A : O → C(n):={0, . . . , n}. "0" represents the lowest (credit) quality, "n" the highest, and C(n) is called rating scale. It is clear that C(n) is a complete lattice, naturally and totally ordered by "≤", and n is called length of the chain C(n). Our goal is to compare the results of two different rating agencies. The two agencies rate the same objects but they apply different rating methodologies, which leads to the Question: Given two ratings A and B from different sources, which one is more progressive?

Progressive in this context means systematically giving a better rating to the same set of objects. Such "optimism" might lead to an underestimation of the underlying risks compared to the less progressive view since the more progressive view tends to ask for a lower risk premium. where the natural rank function in a chain is given by rank := s, s ∈ S We immediately notice:

-Run through all embeddings

E i : C(k) → C(n) -Calculate E i • A and D(B, E i • A) for each embedding E i -Pick (one of ) the E i with minimal distance D(B, E i • A)
Comments: This algorithm is based on the implicit assumption, that both rating agencies are subject matter experts and "know what they are doing", which is reflected in building the minimum of the distances over all possible embeddings. No (subjective) expert opinion or management discretion is needed to decide before hand on the best possible embedding: instead, the algorithm increases objectivity in the sense that the best embedding is chosen purely based on the input data.

Generalized targets for ratings

So far, we only have used finite chains -i.e. totally ordered sets -for the rating process. In this section we will generalize the target sets of the rating process, another application of Theorem 1 will help us to answer the following Questions: Are we limited to totally ordered sets? What about more general lattices as target of ratings? Which lattices will work?

The idea is to use Theorem 1 to "extend" the distances defined above, which essentially compares positions in a finite chain. To this end, we need Definition 6 (Jordan-Dedekind chain condition) A poset P is said to satisfy the Jordan-Dedekind chain condition if any two maximal chains between the same elements of P have the same finite length, where a chain C ⊆ P is called maximal if, for any chain

D ⊆ P , C ⊆ D implies C = D.
If p, q ∈ P with p ≤ q, then p, q are contained in at least one chain in P . In order to measure a distance ∆ between p and q using the natural rank function as introduced in Definition 4, we can take any maximal chain between p and q, and the Jordan-Dedekind chain condition makes sure that this procedure is independent of choice of the maximal chain, and thus the following is well defined: ∆(p, q) := length(C) = rank(q) (in C) for any maximal chain C with p, q ∈ C.

The lattice depicted in Figure 1 violates the Jordan-Dedekind chain condition and serves as counter example: the chain on the left side yields ∆(x∧y, x∨y) = 2, the chain on the right would yield 3 as distance ∆ between x ∧ y and x ∨ y.

Generalized metrics with applications to ratings and formal concept analysis Slightly more general formulated, in a poset P with Jordan-Dedekind chain condition which has a smallest element 0 P we can define rank(q) in the same way for every element q ∈ P as length(C) for any maximal chain containing 0 P and q. This rank function ∆ : P → N ∪ {0} is weakly positive and functorial. If ∆ happens to be also supermodular, then applying Theorem 1 all together we get Corollary 1 Let P be a lattice with Jordan-Dedekind chain condition and supermodular rank function ∆. Then d : P × P -→ M, (p, q) → ∆(p ∧ q, q) is a GQM w. r. t. (P, N ∪ {0}). Furthermore, given two ratings A, B : O → P ,

x y z x ∧ y = x ∧ z x ∨ y = x ∨ z
D + (A, B) := o∈O: A(o)≤B(o) rank B(o) -rank A(o) is a also a GQM w. r. t. (O, N ∪ {0}).
Remark: The Jordan-Dedekind chain condition per se is not enough, as we can deduct from the lattice depicted in Figure 2.

T. Gäbel-Hökenschnieder, T. Pfeiffer, and S. E. Schmidt

p ∧ t p ∧ q q ∧ t p q t d(p, t) = rank(p) -rank(p ∧ t) = 3 -0 = 3 d(p, q) = rank(p) -rank(p ∧ q) = 3 -2 = 1 d(q, t) = rank(q) -rank(q ∧ t) = 3 -2 = 1
Hence, d(p, t) = 3 > 2 = d(p, q) + d(q, t), and d is not a triangular metric. So with the help of Corollary 1 we can give a positive answer: not only simple chains are suitable targets for the rating process, much more, there is the huge class of lattices which allow for a (finite) Jordan-Dedekind chain condition together with a supermodular rank function as rating targets. In particular, modular lattices of finite length will work very well, where a lattice is called modular if it does not contain a sublattice of the form in Figure 1.

But we are not limited to modular lattices. In Figure 3 there is an example of a lower semimodular lattice which is not modular. This behavior of the rank function is somewhat typical, as we can see by the following characterization of lower semimodular lattices:

Theorem 2 Let L be a lattice bounded from below such that any chain between any two elements of L is finite. L is lower semimodular if and only if L possesses a rank function r such that ∀x, y ∈ L:

rank(x) + rank(y) ≤ rank(x ∨ y) + rank(x ∧ y).
L is modular if and only if ∀x, y ∈ L :

rank(x) + rank(y) = rank(x ∨ y) + rank(x ∧ y).
Proof: this is the dual version of Theorem 2.27 from [1].

So lower semimodular lattices, bounded from below such that any chain between any two elements is finite, are exactly the appropriate class of lattices for our purposes.

Furthermore, we can generalize the scaling Algorithm 1 to this class of lattices using rank preserving mappings, where a mapping ϕ between two lattices L and L , which both possess a well-defined rank function, is called rank preserving if rank(u) ≤ rank(v) implies rank(ϕ(u)) ≤ rank(ϕ(v)) for all u, v ∈ L.

Input: O a finite set, ratings A : O → L, B : O → L for lower semimodular lattices L, L , where the finite number of elements of L is denoted by n, and k denotes the number of elements of L such that k ≤ n.

Algorithm 2 (Extended scaling with minimal distance) --Run through all rank preserving injections E

i : L → L -Calculate E i • A and D(B, E i • A) for each embedding E i -Pick (one of ) the E i with minimal distance D(B, E i • A)
Actually, this algorithm is the same as Algorithm 1, but applied to rank preserving injections instead of order preserving embeddings.

An example with only two rank preserving injections is depicted in

Application to concept lattices

In order to keep the paper self-contained, we give a very short summary of formal concept lattices:

A formal context is a triple K = (G, M, I), where G is a set of objects, M is a set of attributes, and I ⊆ G × M is a binary incidence relation that expresses which objects have which attributes. For subsets X ⊆ G of objects and subsets Y ⊆ M of attributes, one defines the following mappings between the power sets of G and M :

-G ⊇ X → X = {m ∈ M : (x, m) ∈ I for every x ∈ X}, and dually

-M ⊇ Y → Y = {g ∈ G : (g, y) ∈ I for every y ∈ Y }. Clearly, X 1 ⊆ X 2 implies X 1 ⊇ X 2 and Y 1 ⊇ Y 2 implies Y 1 ⊆ Y 2 . By a formal concept of the context K is understood a pair (X, Y ) with X ⊆ G, Y ⊆ M such that X = Y and Y = X.
The set X is called the extent of the concept, and the set Y is referred to as intent of the concept. (X 1 , Y 1 ) is called a subconcept of (X 2 , Y 2 ) if X 1 ⊆ X 2 , and we write (X 1 , Y 1 ) (X 2 , Y 2 ). The class BK of all formal concepts of a given context K turns out to be ordered by , and even to be a complete lattice (cfr. Theorem 3 in chapter 1 of [9]), where supremum resp. infimum of two formal concepts are defined by

-(X 1 , Y 1 ) ∨ (X 2 , Y 2 ) = ((X 1 ∪ X 2 ) , Y 1 ∩ Y 2 ), resp. -(X 1 , Y 1 ) ∧ (X 2 , Y 2 ) = (X 1 ∩ X 2 , (Y 1 ∪ Y 2 ) )
The lattice BK is called concept lattice of the context K = (G, M, I).

One consequence is that the mapping G ⊇ X → X ⊆ G is a closure mapping, and therefore #(X) ≤ #(X ), where #(A) is the count measure of a set A, i.e. counting the number of elements of A. After these preparations we can derive

Proposition 1 For α := (A 1 , A 2 ), β := (B 1 , B 2 ) ∈ BK with α ≤ β, the map ∆ : ≤ BK -→ N ∪ {0}, (α, β) → ∆(α, β) := #(B 1 -A 1 ). ( 1
)
is functorial, weakly positive and supermodular.

Generalized metrics with applications to ratings and formal concept analysis

Proof. Let γ := (C 1 , C 2 ) such that α ≤ β ≤ γ.
-Firstly, we can calculate

∆(α, γ) = #C 1 -#A 1 = (#C 1 -#B 1 ) + (#B 1 -#A 1 ) = ∆(β, γ) + ∆(α, β).
Secondly, we see that

∆(α, α) = #(A 1 -A 1 ) = #∅ = 0.
Hence, ∆ is functorial.

-∆ is weakly positive, since 0 ≤ ∆(α, β) holds for all α, β ∈ BK.

-To show that ∆ is supermodular, we start to calculate ∆(α ∧ β, β) and ∆(α, α ∨ β) separately:

∆(α ∧ β, β) = ∆ (A 1 ∩ B 1 , (A 2 ∪ B 2 ) ), (B 1 , B 2 ) = # B 1 -(A 1 ∩ B 1 ) = #B 1 -#(A 1 ∩ B 1 ). ∆(α, α ∨ β) = ∆ (A 1 , A 2 ), (A 1 ∪ B 1 ) , A 2 ∩ B 2 ) = # (A 1 ∪ B 1 ) -A 1 )) = # A 1 ∪ B 1 ) -#A 1 .
Consequently, since X → X is a closure mapping:

∆(α ∧ β, β) = #B 1 -#(A 1 ∩ B 1 ) = #(A 1 ∪ B 1 ) -#A 1 ≤ # A 1 ∪ B 1 ) -#A 1 = ∆(α, α ∨ β).
Hence, ∆ is supermodular.

All together, we now can introduce a generalized metric for concept lattices as follows:

Theorem 3 Let ∆ be as in (1) and

α := (A 1 , A 2 ), β := (B 1 , B 2 ) ∈ BK.
Then the map

d : BK × BK -→ N ∪ {0}, (α, β) → d(α, β) := ∆(α ∧ β, β) is a GM.
Proof. This is a consequence of Proposition 1 together with Theorem 1.

In our considerations we have focused on the extent. Likewise, there is also an intensional point of view for generalized metrics. In general, there are always two types of generalized metrics:

1 d ext (α, β) := #(B 1 -A 1 ) 2 d int (α, β) := #(B 2 -A 2 )
6 Conclusions

-In order to compare ratings, we propose a sound directed metric in order to measure how progressive or conservative ratings are.

-Scaling: For chains S, S of different size we propose an algorithmic solution.

-Posets as target: As target other then simply chains there is the huge class of lattices which allow for a (finite) Jordan-Dedekind chain condition together with a supermodular rank function. In particular, lower semimodular lattices of finite length will work very well. Also, our scaling algorithm based on minimal distances extends to this class of lattices.

-Formal concept analysis: Our concept of generalized metrics carries over to concept lattices, where we can cover the extensional as well as the intensional point of view. Introduction Binary decision systems (choosing one among two possibilities) are usually more interpretable and clearer than more complex systems (choosing one among k) and for many data structures, the binary case is the standard case. For instance, in machine learning, decision trees [3] can be dened with any number of children per nodes, but one generally uses binary decision trees. Moreover, the use of decision trees for prediction can be seen as recursively asking whether a particular individual has or not a chosen attribute hence nodes can be seen as sets of individuals sharing some attribute(s). As formal concepts are elements of concept lattices which also represent objects with common attributes, concept lattices and decision trees are strongly linked : concept lattices can be seen as a collection of overlapping decision trees [2].

We study binary lattices associated with formal contexts. By binary, we mean a concept lattice such that each formal concept covers at most two other concepts and is covered by at most two concepts. We will focus on binarizable lattices, i.e. lattices which can be embedded into a binary lattice. This is similar to the transformation of a non-binary node in a decision tree into an equivalent sequence of binary nodes. In a concept lattice, this amounts to adding some new formal concepts and modifying some existing concepts by adding some objects and/or attributes.

We show in this paper that binarizable lattices are exactly crown-free lattices. Crown-free lattices are an interesting case of lattices as they only have a polynomial number of elements, admit strong properties and a convenient graphical representation [4], [5]. These lattices are equivalent to totally balanced hypergraphs which can be seen as a generalization of trees (they are hypergraphs with no special cycle) and can be characterized by a sequence of trees [7]. This paper is organized as follows: the next section contains basic results and denitions linked to crown-free lattices and formal concept analysis. Section 3 presents our algorithm of binarization of a crown-free set system used to prove the equivalence between crow-free and binarisable lattices. Section 4 gives an illustrative example of binarization applied to formal concept analysis. Finally, Section 5 concludes and gives some topics of future research.

Preliminaries

In this paper, all the sets, posets and lattices are nite.

A poset (partially ordered set) is a pair (A, ≤) such that A is a nonempty set and ≤ a reexive, antisymetric, transitive binary relation on A. (A, ≥) is called the dual of (A, ≤).

Denition 1. A poset (A, ≤) can be embedded into a poset (B, ≤) if there exists f : A → B such that for all A 1 , A 2 ∈ A, A 1 ≤ A 2 if and only if f (A 1 ) ≤ f (A 2 )
In a poset (A, ≤), we note ≺ the covering relation :

∀U, V ∈ A, U ≺ V (V covers U or U is covered by V ) if and only if U < V and X ∈ A, U < X < V .
One can then represent a poset by its Hasse diagram. On such a diagram, each element of A is represented by a node and U, V ∈ A are linked by a segment going upward if and only if U ≺ V .

A poset (L, ≤) is a lattice if inf{U, V } (the largest element that is smaller than or equal to U and V , written U ∧ V and also called the meet of U and V ) and sup{U, V } (the smallest element that is larger than or equal to U and V , written U ∨ V and also called the join of U and V ) exist for all U, V ∈ L.

In formal context analysis, a formal context is a triplet K = (G, M, I) with G a set of objects, M a set of attributes and I ⊆ G × M a binary relation. Denition 2. A formal concept associated with a formal context K = (G, M, I), is a pair (A, B) with:

A ⊆ G, B ⊆ M {y ∈ M |∀x ∈ A, xIy} = B {x ∈ G|∀y ∈ B, xIy} = A A is called an extent and B is called an intent.
The concept lattice L K associated with a formal context K is the lattice of all concepts of the formal context with

(A 1 , B 1 ) ≤ (A 2 , B 2 ) if and only if A 1 ⊆ A 2 and B 2 ⊆ B 1 .
An example of a concept lattice is represented in Figure 1 with blue semicircles representing attributes and black semicircles representing objects and Table 1 gives the concepts of this formal context. We will call extent 1 lattice of a concept lattice the lattice (A, ⊆) with A the set of extents of the formal concepts and intent lattice the lattice (B, ⊆) with B the set of intents. These two lattices are the dual of each other and the concept lattice can be seen as merging them hence working on the intent lattice or on the extent lattice is equivalent to working on the concept lattice.

c1 c2 c3 c4 c5 c6 c7 c8 r1 × × × r2 × × × r3 × × × × × r4 × × r5 × × ×
The intent lattice and the extent lattice of a concept lattice are lattices whose elements are subsets of the same set. They are set systems. Denition 3. S is a set system on a set V if :

S ⊆ 2 V , S is closed under intersection (i.e. A ∈ S, B ∈ S =⇒ A ∩ B ∈ S),
S has a minimum and a maximum element.

Note that all the denitions given in this paper for lattices (embdedded, binary, crown-free, ...) can be extended to set systems as for a given set system S, (S, ⊆) is a lattice.

Formal contexts can also be represented as matrices, rows being the objects and columns the attributes they can have. Table 2 gives the matrix associated with the concept lattice of Figure 1 (with 1 replaced by × symbols and 0 replaced by a blank for readability purposes).

Moreover, every nite lattice L = (L, ≤) can be associated with a formal context K L ([1], [6]) such that its concept lattice L K L is equivalent to the initial lattice.

We will focus on a particular type of lattices : crown-free lattices (i.e. lattices with no crown). Denition 4. A crown is a poset (X 1 , X 1 , . . . , X n , X n ) such that for all i ≥ 2, X i < X i-1 , X i < X i and X 1 < X n , X 1 < X 1 and there is no other comparability relation between these elements.

⊥ r2 r1 c5 r3 r5 r4 c7 c6 c4 c2 c8 c3
Fig. 1: Concept lattice associated with the formal context of Table 2 The Hasse diagrams of a 3-crown and of an n-crown are given in Figure 2. The concept lattice represented in Figure 1 does not contain any crown. One can In binary decision trees, each internal node has exactly two children. More generally, binary trees are trees such that each node has at most two children. Moreover the structure of tree implies that every node has only one parent. The use of a decision tree is based on the simple idea to ask successive yes/no questions about an individual in order to classify it according to the known individuals. We extend the denition of these binary structures to lattices, taking into account that elements of a lattice can be covered by more than one element. In these structures, yes/no questions about a single attribute are replaced by a question about two dierent attributes. An object can then have only one of the two attributes or both of them.

remark that if (L, ≤) is a 3-crown free lattice, for all A, B, C ∈ L, A ∧ B ∧ C ∈ {A ∧ B, A ∧ C, B ∧ C}. X 1 X 2 X 3 X1 X2 X3 (a) 3-crown X 1 X 2 X n-2 X n-1 X n X1 X2 X3
Denition 5. Let L = (L, ≤) be a nite lattice. L is said to be binary if

∀v ∈ L, v = ⊥ =⇒ |{u ∈ L | u ≺ v}| ≤ 2 |{w ∈ L | v ≺ w}| ≤ 2
If only the rst condition is respected, L is said to be lower-binary.

We will characterize binary lattices and those which can be embedded into a binary lattice. Denition 6. Let L = (L, ≤) be a nite lattice. L is binarizable if and only if there exists a lattice L = (L , ≤) such that L can be embedded in L and L is binary.

We will rst prove that binarizable lattices are crown-free (Proposition 8). The intuition of this result can be summarized as follows : considering an element Y covering more than three elements, in an attempt to binarize the lattice, Y would cover two elements Y and Y which must be the joins of the incomparable elements they cover. We show that in a crown, Y = Y or Y = Y which is not possible. The intuition is easy to understand on a 3-crown. For example in Figure 2, it is impossible to create the union of X 1 and X 2 without X 3 . Property 7. Let L = (L, ≤) be a nite lattice and

X 1 , X 1 , . . . , X n , X n ∈ L. If (X 1 , X 1 , . . . , X n , X n ) is a crown of L then (X 1 , X 1 ∨ X 2 , . . . , X n , X n ∨ X 1 ) is a crown of L.
Proof. We show that X i ∨ X i+1 X j for all j = i, i + 1 mod n. Indeed, X i X j and X i+1 X j by denition of a crown hence X i ∨ X i+1 X j . Moreover X j X i by denition of a crown. Yet for all i ≤ n, X i ≤ X i and

X i+1 ≤ X i hence X i ∨ X i+1 ≤ X i . Hence X j X i ∨ X i+1 . Hence X j X i ∨ X i+1 .
We will therefore only consider cycles of the form (X 1 , X 1 ∨ X 2 , . . . , X n , X n ∨ X 1 ) in the proofs. Proposition 8. Let L = (L, ≤) be a nite lattice. If L is binarizable then L is crown-free.

Proof. We rst show that any binary lattice is crown-free by induction on the size of the crown. Suppose (L, ≤) is a binary lattice containing a 3-crown. Let

(X 1 , X 1 ∨ X 2 , X 2 , X 2 ∨ X 3 , X 3 , X 3 ∨ X 1 ) a 3-crown and Y = sup(X 1 , X 2 , X 3 ) = sup(X 1 ∨X 2 , X 2 ∨X 3 , X 3 ∨X 1 ). (L, ≤) is binary so Y covers at most two elements Y and Y and {X i ≤ Y ∪ Y } = {X 1 , X 2 , X 3 }. Y is the supremum of X 1 ∨ X 2 , X 2 ∨ X 3 , X 3 ∨ X 1 and Y ≺ Y, Y ≺ Y hence,
by the pigeonhole property, we can suppose without loss of generality that

X 2 ∨ X 3 ≤ Y and X 3 ∨ X 1 ≤ Y . Hence X 1 < Y and X 2 < Y so X 1 ∨ X 2 ≤ Y hence Y ≥ Y which is a contradiction.
Suppose that any (L, ≤) containing a crown of size inferior or equal to n -1 (with n > 3) is not binary. Let (L, ≤) a binary lattice containing an n-crown.

Let (X 1 , X 1 ∨ X 2 , . . . X n , X n ∨ X 1 ) a crown and Y = sup(X 1 , . . . X n ). (L, ≤) is Y X1 X2
...

. Y = sup(X 1 , . . . , X n ) hence 1 ≤ |{X i ≤ Y |i ≤ n}| < n and 1 ≤ |{X i ≤ Y | i ≤ n}| < n. Y is binary hence {X i ≤ Y | i ≤ n} ∪ {X i ≤ Y | i ≤ n} = {X i | 1 ≤ i ≤ n} so we can suppose without loss of generality that |{X i ≤ Y | i ≤ n}| ≥ 2. Suppose moreover that X 1 Y . Let j = min{i ≤ n | X i ≤ Y } and j = max{i ≤ n | X i ≤ Y }. (X j , X j ∨ X j +1 mod n , X j +1 mod n . . . , X n , X n ∨ X 1 , X 1 , X 1 ∨ X 2 , X 2 . . . , X j , Y
) is a crown of size inferior or equal to n -1 and superior to 3. Indeed for all i < j and for all i > j , X i Y . Hence the lattice has a crown of size inferior or equal to n -1 hence by induction hypothesis the lattice is not binary. By denition of embedding and of a crown, for all lattice (L, ≤) containing a crown, if (L, ≤) can be embedded in (L , ≤) by a function f , then

(X 1 , X 1 , . . . X n , X n ) is a crown in (L, ≤) if and only if (f (X 1 ), f (X 1 ), . . . , f (X n ), f (X n )) is a crown in (L , ≤).
By the previous result, if (L , ≤) has a crown then (L , ≤) is not binary hence if (L, ≤) has a crown, (L, ≤) is not binarizable.

In this proof we only used the fact that for all Y in a binary lattice, Y covers at most two elements. If Y is covered by more than 3 elements, the same proof can be applied to the dual of the lattice in which Y covers more than 3 elements.

We will now show that any crown-free lattice can be embedded in a binary lattice (Proposition 14). We will work on set systems associated with lattices and use Algorithm 1 in order to transform any crown-free set system into a lower-binary set system. Each non-binary element is transformed into a binary one by creating unions of some of the elements it covers. In order to keep the closure under intersection of the set system, the elements used to created the new elements have to be chosen wisely. Denition 9. Let {X 1 , . . . , X n } be a set of incomparable subsets of the same set. X i and X j are said to be of maximal intersection among {X 1 , X 2 , . . . X n } if and only if there does not exist

k = i, j such that X i ∩ X j X i ∩ X k or X i ∩ X j X j ∩ X k .
One step of the process is illustrated in Figure 3.

Algorithm 1: Lower-binarization of a crown-free set system Data: S a set system Result: B(S) a set system such that every element covers at most two other elements and S can be embedded into B(S)

1 B(S) = S 2 for Y ∈ S do 3 C = {X ∈ B(S) | X ≺ Y } 4 while |C| > 2 do 5 Find Xi, Xj of maximal intersection among C 6 B(S) = B(S) ∪ {Xi ∪ Xj} 7 C = C ∪ {Xi ∪ Xj}\{Xi, Xj} 8 return B(S)
The process adds as few elements as possible to the set system to make it binary. Indeed, if an element Y covers k elements X 1 , . . . , X k , our construction adds exactly k -2 elements.

The following technical lemmas will be used to prove Proposition 13. Note that all these lemmas only require the set system to have no 3-crowns and not to be crown-free. Lemma 10. Let L be a set system with no 3-crown and {X 1 , . . . , X n } ⊂ L a set of incomparable elements of L.

Let X i and X j of maximal intersection among {X 1 , . . . X n }.

Then,

∀l ∈ {1, . . . , n}, X l ∩ (X i ∪ X j ) = X i ∩ X l or X j ∩ X l Proof. Let X i , X j of maximal intersection among {X 1 , . . . , X n }. L has no 3-crowns, so X i ∩ X j ∩ X l ∈ {X i ∩ X j , X i ∩ X l , X j ∩ X l }. X i and X j are of maximal intersection so X i ∩ X j X l ∩ X i and X i ∩ X j X l ∩ X j . Hence X i ∩ X j ∩ X l ∈ {X i ∩ X l , X j ∩ X l } i.e. X j ∩ X l ⊆ X i ∩ X l or X i ∩ X l ⊆ X j ∩ X l . Yet ∀l, X l ∩ (X i ∪ X j ) = (X i ∩ X l ) ∪ (X j ∩ X l ) Hence ∀l, X l ∩ (X i ∪ X j ) = X i ∩ X l or X j ∩ X l ⇐⇒ X j ∩ X l ⊆ X i ∩ X l or X i ∩ X l ⊆ X j ∩ X l
Lemma 11. Let L be a set system with no 3-crown and {X 1 , . . . , X n } ⊂ L the set of elements covered by Y ∈ L. Taking X i , X j , two elements of maximal intersection among {X 1 , . . . X n } :

∀Z ∈ L\ {X 1 , . . . , X n , Y } , Z ∩ (X i ∪ X j ) ∈ L ∪ {X ∪ Y }. Proof. If Z ∩ X i ⊆ X j then Z ∩ (X i ∪ X j ) = Z ∩ X j . As L is closed under intersection, Z ∩ X j ∈ L. The same goes for X j . Suppose now Z ∩ X i \ {X j } = ∅ and Z ∩ X j \ {X i } = ∅. Hence X i ∩ X j ⊆ Z, as L has no 3-crowns. So X i ∩ X j ⊆ Z ∩ Y . If Y ⊆ Z, the result is obvious. If Z Y or Z Y then Z ∩ Y Y so there exists k such that Z ∩ Y ⊆ X k as Y exactly covers the elements (X 1 , . . . , X n ). X i ∩ X j ⊆ Z ∩ Y ⊆ X k and X i , X j are of maximal intersection so k = i or k = j. Hence Z ∩ Y ⊆ X i (or symmetrically Z ∩ Y ⊆ X j ) which leads to Z ∩ Y ⊆ Z ∩ X i so Z ∩ Y ⊆ Z ∩ (X i ∪ X j ). Moreover as X i ∪ X j ⊆ Y , Z ∩ (X i ∪ X j ) ⊆ Z ∩ Y , by double inclusion Z ∩ (X i ∪ X j ) = Z ∩ Y . Yet Z ∩ Y ∈ L as L is closed under intersection, which completes the proof.
Lemma 12. Let L be a set system with no 3-crown and {X 1 , . . . , X n } ∈ L the set of elements covered by Y ∈ L. For all X i , X j of maximal intersection among {X 1 , . . . , X n }, all elements of {X 1 , . . .

X n } ∪ {X i ∪ X j } \ {X i , X j } are incomparable.
Proof. We prove that for all

k = i, j, X i ∪ X j X k . As, for all k = i, j, X i , X j and X k are incomparable, X i X k and X j X k hence X i ∪ X j X k . As L has no 3-crown, X i ∩ X j ∩ X k ∈ {X i ∩ X j , X i ∩ X k , X j ∩ X k } so as X i and X j are of maximal intersection, X i ∩ X j ⊂ X i ∩ X k and X i ∩ X j ⊂ X j ∩ X k . So X i ∩ X j ∩ X k ∈ {X i ∩ X k , X j ∩ X k }. Suppose X i ∩ X j ∩ X k = X i ∩ X k . We then have X i ∩ X k ⊆ X j . Moreover, as (X 1 , . . . X n ) are incomparable, there exists x ∈ X k such that x / ∈ X j . X i ∩ X k ⊆ X j hence x / ∈ X i . So there exists x ∈ X k , x / ∈ X i ∪ X j so X k X i ∪ X j .
Proposition 13. Algorithm 1 applied on a set system S returns a set system B(S) such that:

for all X ∈ B(S), X covers at most two elements, S ⊆ B(S), for all X ∈ S, X is covered by the same number of elements in S and in B(S).

Proof. By Lemma 10 and 11, creating new elements as described in the construction preserves the closure under intersection of the system. Lemma 10 shows that the intersection of any element of the considered part of the system and the new element is already in the system and Lemma 11 shows the same for other elements. Moreover, the minimum element and the maximum element are unchanged as the algorithm only adds unions of two elements hence the system is a set system. Lemma 12 shows that if X i and X j are chosen from the set of incomparable elements {X 1 , . . . , X n } covered by an element Y to create a new element, the only changes in the covering relation of the system are X i ∪X j ≺ Y , X i ≺ X i ∪ X j and X j ≺ X i ∪ X j . Hence, no new crown is added and the set system is still crown-free. Moreover, for k = i, j, X k is not anymore covered by Y but by X i ∪ X j which keeps unchanged the number of covering elements of X k . The other elements are unchanged. Lemma 12 also proves that the process can be iterated if the set system still has no 3-crowns.

The algorithm ends when all elements of the initial system cover at most two elements. Moreover, the elements added by the construction cover exactly two elements by construction. Proposition 14. Let L = (L, ≤) be a nite lattice. If L is crown-free then L is binarizable.

Proof. Let (A, ⊆) be the extent lattice of K L (the formal context associated with L). Algorithm 1 can be applied on the set system A. By Proposition 13, the obtained set system B(A) is such that A ⊆ B(A) and B(A) is lower-binary. Moreover L can trivially be embedded in the lattice L = (B(A), ⊆).

Let (B, ⊆) be the intent lattice of L . By Proposition 13, B(B), the result of Algorithm 1 applied on B, is binary. Finally, L can be embedded in the binary lattice L = (B(B), ⊆) so L can also be embedded into L by transitivity of the embedding.

Propositions 8 and 14 prove the main result of this paper. Theorem 15. Let (L, ≤) be a nite lattice. (L, ≤) is binarizable if and only if (L, ≤) is crown-free. 4 Example

We will now apply our binarization algorithm on a small concept lattice. Table 3a gives a small formal context describing some animals to apply our algorithm.

The formal concepts associated with this context are given in Table 3b. The representation of the Hasse diagram of the concept lattice associated with this formal context (Figure 4) gives an easy way to see non-binary formal concepts.

Here, the concept representing the duck is covered by three concepts and the concept representing the attribute swim covers three concepts. This representation also shows that the lattice is crown-free so it it binarizable and our algorithm can be applied.

A binarization of the set system associated with the extent lattice of this concept lattice gives the Hasse diagram given in Figure 5a with the new latent node (a new attribute) represented as a rectangle. We deliberately ignore the fact that the element ⊥ is not binary as binarizing it would not increase interpretability or help using the model in machine learning. The Hasse diagram associated with a binarization of the extents and of the intents is represented in Figure 5b and is associated with the formal context of Table 4. The process creates two new formal concepts : one associated with a new object obj (which could be interpreted as the existence of a bird eating seeds, for example a canary) and one associated with a new attribute att (which suggests the existence of an attribute allowing to distinguish salmon, shark, barracuda and crocodile from frog and duck) and modies scale teeth swim y seed feather 3b other formal concepts using this new attribute and object. The binarization process does not give a unique solution. Indeed, att could have been associated with a new concept {(shark, f rog, barracuda, crocodile, duck), (teeth, att, swim)} instead of {salmon, shark, barracuda, crocodile), (scale, att, swim)} as the two intersections concerned are incomparable. This allows to make interactive systems giving the user dierent choices to binarize each concept. The model can then be used in the same way a decision tree is used : beginning from the top of the lattice, a new element is propagated in the nodes asking at each node whether it has the attribute of the right child or of the left child of the current node beforce classifying it as close to some known concept.

air salmon × × shark × × barracuda × × × frog × × crocodile × × × eagle × × × ostrich × × × duck × × × × × (a)
× × × shark × × × barracuda × × × × frog × × crocodile × × × × eagle × × × ostrich × × × ob j × × × × duck × × × × ×

Conclusion

We presented a simple and ecient algorithm to transform a crown-free set system into a binary one. This construction allows us to prove the equivalence between binary lattices and crown-free ones. Our algorithm can be easily used in formal context analysis in order to modify a concept lattice to obtain a binary one, adding some objects and attributes. Moreover, our algorithm can be independently applied on the intents only or on the extents only or on both. The system being binary, it is easy to interpret and understand. The equivalence between binary lattices and crown-free ones makes of crown-free lattices a perfect candidate to extend machine learning ideas developped in decision trees to more complex systems. Indeed, it can then be used in machine learning to predict the class of a given object by propagating it in the concept lattice recursively asking whether the object has or not the attribute represented by the predecessor of the concept in the lattice. Moreover, the binarization we proposed is not unique but always adds the same number of elements to the lattice, which allows the development of interactive systems to build the model. Topics for future work include :

a top-down process to build binary lattices inspired from decision trees, machine learning applications of lattice structures, study of the interest of intersecting classes in the machine learning perspective and the classication one.

Introduction

CrossCult (http://www.crosscult.eu) is a European project whose idea is to support the emergence of a European cultural heritage by allowing visitors in different cultural sites (e.g. museum, historic city, archaeological site) to improve the quality of their visit by using adapted computer-based devices and to consider the visit at a European level. Such improvement can be accomplished by studying, among others, the possibility to build a dynamic recommendation system. This system should be able to produce a relevant suggestion on which part of a cultural site may be interesting for a specific visitor.

Here, our objective is to study a dynamic recommendation system for visitors in a museum. Given a new visitor V n , the task is to suggest a museum item that may be interesting for him/her. Based on how a suggestion is made to a new visitor V n , a recommendation system can be classified into one of the three following categories [1]:

-Content-based recommendations: The system makes a suggestion based only on the previous visited items of V n . For example, if V n visited mostly the items from prehistoric era, then the system recommends another item from that era.

-Collaborative recommendations: The system looks for previous users who have similar interest to V n , and makes a suggestion based on their visited items. For example, if many of V n 's similar users have visited item I, then the system recommends this item. -Hybrid approaches: The combination of content-based and collaborative approaches.

Our method belongs to the second category (collaborative recommendation).

First we group all previous users based on their visit trajectories using biclustering. When V n arrives, we try to find a G s , i.e. a group of visitors who shares a similar interest to V n . Then, based on the behavior of the visitors in G s , we can suggest one item that may be interesting for V n .

In this paper we will recall an approach in [6] that uses partition pattern structures to obtain biclusters with constant (or similar) values on the columns. Then we will propose an alternative approach that relies on this approach to mine another type of biclusters: those with coherent evolution on the columns (CEC biclusters). This bicluster type is useful when we are dealing with a dataset of trajectories where each trajectory corresponds to an ordered list of items. Furthermore, the mining of CEC biclusters can be related to sequential pattern mining, which we will explore in this paper.

This paper is organized as follows. First, we mention some related works about recommendation in Section 2. Then the basic background on biclustering is given in Section 3. Section 4 explains how to perform biclustering using partition pattern structures. The application of biclustering to recommendation systems will be presented in Section 5. Finally, we conclude our paper and outline some future works in Section 6.

Related work

In this section, we will describe related work about recommendation systems, biclustering, and Formal Concept Analysis (FCA).

FCA has been studied in collaborative movie recommendations for a user by looking at the ratings given by other users. In [5], FCA is used to generate a lattice from a binary matrix (with users as rows and movies as columns) as the formal context. This matrix is derived from a rating dataset which is binarized, such that the matrix contains only the information whether a user has rated a movie. The lattice is then drawn to select some neighbors -i.e. users who have rated the same movies as the new user -regardless of the rating values. In this way, the exhaustive search of neighbors can be avoided. The neighbors' ratings can be then studied to recommend movies rated by the neighbors but not yet rated by the new user.

Pattern structures [8,13] are a generalization of FCA, where the objects have more complex descriptions (e.g. sequence, graph, etc.). FCA was also extended into Triadic Concept Analysis, and it was shown in [13] that triadic concepts are in 1-1-correspondence with maximal biclusters of similar values.

Partition pattern structures are an instance of the pattern structure framework. They were used in a collaborative movie recommendation [7] by identifying similar-column biclusters within the rating matrix. Such a bicluster corresponds to a set of users with similar rating behavior (hence similar interest) across a set of movies. Therefore, to recommend a movie to a new user, there is a search for biclusters whose users have similar interest to him/her. Then, a recommendation is given by looking at the movies rated by users in the biclusters but not yet rated by the new user. Using the real MovieLens data, a study was also conducted based on Boolean matrix factorization [2].

Moreover, recommendation systems based on FCA and/or biclustering have been applied to other real world problems such as detection of future advertising terms for a company [10], educational orientation of Russian school graduates [11], and idea recommendation at a crowdsourcing project of Witology company [9]. Furthermore, a unified taxonomy of biclustering methods was proposed in [12].

Biclustering

In this section, we will recall the basic background and discuss illustrative examples of the different types of biclusters as described in [14]. We consider a dataset composed of a set of objects, each of which has values over a set of attributes. This dataset can be represented as a numerical matrix, where each cell ij indicates the value of object i w.r.t. attribute j.

One may be interested in finding which subset of objects possesses the same values w.r.t. a subset of attributes. Regarding the matrix representation, this is equivalent to the problem of finding a submatrix that has a constant value over all of its elements (example in Table 1). This task is called biclustering with constant values, which is a simultaneous clustering of the rows and columns of a matrix. Other than constant values, the bicluster approach also focused on finding other types of submatrices, as shown in Table 2. A bicluster with constant columns (rows) is a submatrix where each column (row) has the same value, as illustrated in Table 2a (Table 2b, resp.).

In a bicluster with additive coherent values, the value of each cell ij follows the equation γ + α i + β j , where γ is a constant, α i is a constant value for row i, and β j is a constant value for column j. For example, if γ = 1, (α 1 , α 2 , α 3 , α 4 ) = (3,2,4,6), and (β 1 , β 2 , β 3 , β 4 ) = (0, -2, 1, -1), then we can obtain the bicluster

Biclustering with Constant Columns

A partition d = {p i } of a set G is a collection of p i ⊆ G such that: pi∈d p i = G and p i ∩ p j = ∅ whenever i = j.

(

) 1
Notice that when calculating the initial partitions, missing values can produce overlapping partitions (i.e. p i ∩ p j = ∅). Consider the dataset given by Table 3 that has G = {g 1 , g 2 , g 3 , g 4 } as the set of objects and M = {m 1 , m 2 , m 3 , m 4 , m 5 } as the set of attributes. Here we can define a partition mapping δ : M → D. The partition is based on the fact that the values of the attribute are equal for all objects in a subset. For example, δ(m 1 ) = {{g 1 , g 2 }, {g 3 , g 4 }} because G is partitioned as such regarding the value of m 1 , whereas δ(m 4 ) = {{g 1 , g 2 }, {g 1 , g 3 , g 4 }}. This partition overlaps on g 1 since this object has a missing value on m 4 . Intuitively, g 1 can be grouped with either {g 2 } or {g 3 , g 4 } w.r.t. m 4 .

Table 3. A dataset with 4 objects and 5 attributes m1 m2 m3 m4 m5 g 1 1 5 3 ? 7 g 2 1 1 4 2 7 g 3 2 5 4 5 3 g 4 2 5 4 5 7

The space D of all partitions over G is a complete lattice, where the meet and join of two partitions d 1 = {p i } and d 2 = {p j } are defined as:

d 1 d 2 =   i,j p i ∩ p j   + (2) d 1 d 2 =   pi∩pj =∅ p i ∪ p j   + (3)
where (.) + is a closure that preserves only the maximal components in d. For example, δ(m 1 ) δ(m 4 ) = {{g 1 , g 2 }, {g 1 }, {g 3 , g 4 }} + = {{g 1 , g 2 }, {g 3 , g 4 }}, and

δ(m 1 ) δ(m 4 ) = {{g 1 , g 2 }, {g 1 , g 2 , g 3 , g 4 }, {g 1 , g 3 , g 4 }} + = {{g 1 , g 2 , g 3 , g 4 }}.
The order between any two partitions is given by the subsumption relation:

d 1 d 2 ⇐⇒ d 1 d 2 = d 1 (4)
Given a set of attributes M, a partition space D, and a mapping δ, a partition pattern structures for constant-column biclustering is determined by the triple (M, (D, ), δ). A pair (A, d) is then called a partition pattern concept (pp-concept) iff A = d and d = A, where:

A = m∈A δ(m) A ⊆ M (5)
d = {m ∈ M|d δ(m)} d ∈ D (6)
For any partition component p ∈ d, each pair (p, A) corresponds to a constantcolumn bicluster. For example, from the concept ({m 1 , m 4 }, {{g 1 , g 2 }, {g 3 , g 4 }}), two biclusters can be obtained: ({g 1 , g 2 }, {m 1 , m 4 }) and ({g 3 , g 4 }, {m 1 , m 4 }).

Biclustering with Coherent Evolution on the Columns

In a dataset of movie ratings, bicluster with constant columns is useful to identify a set of users with the same taste regarding a set of movies. Another interesting problem arises, e.g. when the dataset contains watching order. In that case, we may be interested in finding a set of users who watch a set of movies in the same order. This problem corresponds to CEC biclustering, where the objective is to find a set of rows which has coherent evolution over a set of columns, as previously described in Section 3. In the current section, we will explain the possible application of partition pattern structures to discover CEC biclusters. Consider the dataset given by Table 4, with the set of attributes G = {g 1 , g 2 , g 3 , g 4 , g 5 }. First, we have to list each pair of attributes and the partition according to the pair's evolution. For the pair p 1,2 = (m 1 , m 2 ), the partition is {{g 1 , g 3 }, {g 2 , g 4 , g 5 }} because in g 1 and g 3 , m 1 is less than m 2 , whereas in g 2 , g 4 , and g 5 , m 1 is greater. As in Subsection 4.1, missing values generate an overlapping partition. For instance, the pair p 1,4 gives rise to the partition is {{g 1 , g 2 , g 5 }, {g 2 , g 3 , g 4 }}. Furthermore, two columns with the same value (e.g. g 3 in m 4 and m 5 ) can also produce an overlapping partition because, by our definition of CEC bicluster in Section 3, they satisfy m 4 ≤ m 5 and m 5 ≤ m 4 . Therefore, the partition for p 4,5 is {{g 1 , g 2 , g 3 }, {g 2 , g 3 , g 4 , g 5 }}. Some pairs and their partitions are listed in Table 5.

Since a CEC partition is defined by at least two attributes, the partition mapping becomes γ : P → D. For instance, γ(p 1,2 ) = {{g 1 , g 3 }, {g 2 , g 4 , g 5 }}. As in Subsection 4.1, given a set of attribute pairs P, a partition space D, and the mapping function γ, a partition pattern structures for coherent-evolution biclustering is determined by the triple (P, (D, ), γ). A pp-concept is a pair (B, d) such that B = d and d = B, where:

B = p∈B γ(p) B ⊆ P (7)
d = {p ∈ P|d γ(p)} d ∈ D (8)
Here, the extent of a pp-concept is a set of attribute pairs. We can obtain a CEC bicluster in a pp-concept if there is a clique among the attributes in the pairs. For example, consider the pp-concept ppc 1 with extent {p 1,2 , p 1,3 , p 2,3 } and intent {{g 1 , g 3 }, {g 5 }, {g 2 , g 4 }}. Its extent forms a clique among m 1 , m 2 , and m 3 , since all pairings of any two of those attributes are included.

If a pp-concept (B, d) contains a set of attributes A that forms a clique, then each pair (p, A), for any partition component p ∈ d, corresponds to a CEC bicluster. For example, from ppc 1 , we can obtain bicluster ({g 1 , g 3 }, {m 1 , m 2 , m 3 }).

Comparison with Sequential Pattern Mining

A sequence is an ordered list s 1 s 2 . . . s m , where s i is an itemset {i 1 , . . . , i n }. A sequence s = s 1 s 2 . . . s m is a subsequence of s = s 1 s 2 . . . s n , denoted by s s , if there exist indices 1 ≤ i 1 < i 2 < . . . < i m ≤ n such that s j ⊆ s ij for all j = 1 . . . m and m ≤ n. For example, the sequence {a}{d} is a subsequence of {a, b}{a, c, d} , while sequence {c}{d} is not.

Notice that the problem of retrieving CEC biclusters can be thought of as a particular type of sequential pattern mining where each itemset is composed by only one item, i.e. the sequences are an ordered list of items. Mining sequential patterns means retrieving frequent subsequences (i.e., subsequences that are present in more than n sequences) and for which there exist many efficient algorithms [16,15].

The CEC biclustering differs from sequential pattern mining when we allow overlaps in the partitions. Consider Table 4 as a sequential dataset. Each number in row x column y corresponds to the itemset when item y appears in the sequence x. For example, the sequence of object g 3 is {m 4 , m 5 }{m 1 }{m 2 }{m 3 } .

Let us consider items m 1 , m 4 , and m 5 . According to sequential pattern mining, g 3 is different from g 4 , because m 4 and m 5 appear in the same itemset in g 3 . On the other hand, according to CEC biclustering with overlaps, g 3 is similar to g 4 , because in both objects m 5 ≤ m 4 ≤ m 1 .

Recommendation

In the context of CrossCult, we are working on a visitor dataset that comprises several trajectories in a museum. Within this project, our main objective is to build a dynamic recommendation system for new visitors. This system should be able to suggest a museum item to visitors based on their trajectories and by looking at the trajectories of previous visitors. Also, it should be able to update the suggestion as they move inside the museum.

Matrix as order of interest

For each item in the museum, we can measure (e.g. by rating, duration of visit, etc.) their level of interestingness from a set of visitors. An example is shown in Table 6, where the number in cell xy is the ranking of item y according to visitor x. Here we have 3 visitors (v 1 , v 2 , and v 3 ) in the database and 1 target visitor (v a ). Among the existing visitors, only v 1 has complete values over all five items. According to this visitor i 1 is the best, followed by i 2 , i 3 , i 4 , and the worst i 5 . For v 2 (v 3 ), the order of interest of i 2 (i 4 resp.) is not known.

The target visitor (v a ) has visited only three items, with the same order of preference in i 1 and i 2 . This visitor will be included in the bicluster ({v 1 , v 2 , v a }, {i 1 , i 2 , i 3 }). The other two members of this bicluster do not agree on the order of interest of i 4 and i 5 . Hence, we should suggest i 5 to him/her, since one visitor (v 2 ) similar to him/her ranked it first.

Matrix as order of visit

Consider the dataset given by Table 7 about 4 visitors in a museum with 7 items. As explained in Subsection 4.3, this table can be regarded as a sequential dataset. The numbers in row x indicate the path of visitor v x . For example, the path of

v 2 is i 6 → i 1 → i 4 → i 2 → i 3 → i 7 → i 5 .
Now we have a new visitor v a who recently arrives to the museum. He/She visits i 3 , followed by i 4 . Our task is to recommend a new item to her, by studying Table 7. Order of visit of 7 items, observed from certain visitors i1 i2 i3 i4 i5 i6 i7 v1 1 2 3 4 5 6 7 v2 2 4 5 3 7 1 6 v3 4 2 1 5 6 3 7 v4 7 3 1 4 2 6 5 va ? ? 1 2 ? ? ?

the CEC biclusters over the first four visitors. Some of those biclusters are listed in Table 8. From B7, we can see that all four visitors visit i 7 after i 2 . In B3, v 1 and v 3 follow the same order w.r.t. {i 3 , i 4 , i 5 , i 7 }: i 3 → i 4 → i 5 → i 7 . These two visitors also agree in the order of items {i 1 , i 4 , i 5 , i 7 }, as seen in B4. Those CEC biclusters can be studied to give a recommendation to v a by focusing on those visitors that are similar to him/her. Thus, we can propose a recommendation strategy that follows sequential patterns in the dataset. The idea behind is the following: if many visitors have the path i a → i b → i c , then we should recommend item i c to a visitor who has done i a → i b .

Since v a has path i 3 → i 4 , we focus on the CEC biclusters that have those two items, i.e. B1, B2, and B3. One of those biclusters (B2) has a different ordering (i 3 after i 4 ), and thus we filter it out. Then, in B3 for example, the path is i 3 → i 4 → i 5 → i 7 . Therefore, we can recommend i 5 to v a .

Conclusion

In this work, we have explored an approach to build collaborative recommendation strategy for visitors in a museum. This strategy takes into account the order of interest or the order of visit for each visitor, and we showed how to use CEC biclustering to obtain a set of similar visitors. We also presented a technique for mining CEC biclusters based on FCA using partition pattern structures. This recommendation strategy can be applied to any dataset where the order of items is relevant.

As future work, we intend to explore recommendations based on the order of visit. The problem to be solved is how to model visitors who visit a single item multiple times (for example, i 1 , i 2 , and back to i 1 ).

Another noteworthy question is how to measure the "score" of each bicluster in order to rank recommendations for a new visitor. Ranking candidate items was studied in [3] for constant-value biclusters, and it is possible to extend this work to CEC biclusters. Moreover, further comparisons of CEC biclustering and sequential pattern mining should be investigated, in particular, regarding their complexities and their results. Finally, an implementation of the CEC biclustering using partition pattern structures and an empirical study on real-world data should be performed to measure its complexity and efficiency.

Combining Concept Annotation and Pattern Structures for Guiding Ontology Mapping

Pierre Monnin 1 , Amedeo Napoli 1 , and Adrien Coulet 1,2

Introduction

An ontology is a formal representation of a particular domain [8], consisting of two parts: an assertion component (ABox) and a terminological component (TBox). In the TBox, classes and predicates between classes are defined while in the ABox, individuals instantiate classes and predicates. For example, the drug codein can be considered as an individual instantiating the class Analgesics. Nevertheless, there is a need for structure between ontologies. Indeed, individuals of an ABox may instantiate classes from several ontologies. For example, in the medical domain, individuals representing diseases may instantiate classes of several ontologies of diseases, such as MeSH (Medical Subject Headings), ICD-9-CM and ICD-10-CM (International Classification of Diseases version 9 and 10, Clinical Modification). Corresponding classes from distinct ontologies may be mapped thanks to equivalence relationships resulting from an alignment process [5]. This alignment may be either a manual review by an expert or a semiautomatic process.

On the other hand, within an ontology, additional knowledge and structuring may be discovered. Thus, the ABox of an ontology may also contains predicate assertions, i.e., relations between individuals. For example, in DrugBank, a database of drug information, a drug can be associated with a gene, indicating an interaction between them. Thereby, the gene VKORC1 is indicated to be an inhibitor of the drug warfarin. Genes and drugs instantiate classes of ontologies, such as ATC (Anatomical Therapeutic Chemical Classification System) for drugs and GO (Gene Ontology) for genes. Therefore, from the predicate assertions, we could discover classes of drugs and genes frequently associated as domain and range of a predicate. Such domain and range associations could be interesting as they may indicate common properties of the gene class or the drug class.

In this article, we aim at addressing both of the aforementioned use cases, (i) suggesting equivalence relationships between ontology classes and (ii) discovering classes frequently associated in domain and range of a predicate, with Formal Concept Analysis (FCA) [7]. FCA is a well-founded mathematical framework adapted to knowledge engineering purposes [1,3,4] that groups objects w.r.t. their common attributes in formal concepts. The association of an attribute to an object is expressed thanks to a binary relationship. Formal concepts are organized by a partial order in a hierarchical structure called a lattice. In a previous work [9], we introduced an extension of FCA, called Concept Annotation, allowing to compare the hierarchical structure of the lattice with the class hierarchy of an ontology for possible refactoring. The main interest of Concept Annotation resides in adding a third dimension to a previously generated lattice without changing its structure. The main contribution of the present article is to extend the initial definition of Concept Annotation by (i) associating multiple Concept Annotations with formal concepts, and (ii) using a formalism similar to Pattern Structures [6] to express the annotations. Pattern Structures are another extension of FCA dealing with objects having complex (non binary) descriptions (e.g., graphs, numerical values, classes of an ontology). In the following, we assume that the reader is familiar with the basics of FCA and Pattern Structures.

This article is organized as follows. In Section 2, necessary basics about ontologies are recalled. In Section 3, we present the initial definition of Concept Annotation as well as our proposed extension. Then, in Sections 4 and 5, we illustrate the combination of Concept Annotation and Pattern Structures by, respectively, suggesting equivalence relationships between classes and discovering classes frequently associated as domain and range of a predicate. Finally, in Sections 6 and 7, we discuss the results we obtain on the two considered use cases as well as the next challenges to tackle.

Basics about Ontologies

An ontology is a formal representation of a particular domain [8]. It is composed of two parts, the TBox and the ABox. The TBox defines classes and relationships between them. We denote C(O) the set of classes of the ontology O. Classes of an ontology are instantiated by individuals of the ABox. These individuals can also be involved in instantiation of relationships (such as the drug-gene relationship in DrugBank previously explained).

Classes of an ontology are organized in a partial order by a subsumption relation denoted by ⊑. Considering two classes C and D, C ⊑ D states that every instance of C is also an instance of D. The least common subsumer (sometimes named the lowest common ancestor) of two classes C 1 and C 2 of an ontology is the most specific class subsuming both C 1 and C 2 . It is denoted by lcs(C 1 , C 2 ).

In EL ontologies where no cycle appears, the lcs of two classes always exists [2]. Considering a set of classes C n = {C 1 , C 2 , . . . , C n }, we define the set of the most specific classes of C n as min

C n = {C ∈ C n | ̸ ∃ D ∈ C n , D ⊑ C}.

Concept Annotation

Concept Annotation is an extension of FCA that we introduced in a previous work [9]. In this section, we first recall basics about our initial work and then present the proposed extension.

Basics about Concept Annotation

In Concept Annotation, standard FCA is applied on a formal context to build a concept lattice. Then, for each formal concept, an annotation is computed, adding a third dimension to each concept.

For example, in [9], a lattice is built from a formal context (G, M, I) where G is a set of individuals from the ABox of an ontology O and M is a set of predicates of this ontology. (g, m) ∈ I indicates that the individual g is involved in a relationship whose predicate is m. Then, classes of the TBox instantiated by the individuals in G are added as annotation. The resulting hierarchy formed by the lattice and the annotations is compared to the class hierarchy of the ontology. To compute the annotation, we defined a derivation operator (•) ⋄ : 2 G → 2 C(O) , where 2 C(O) corresponds to the powerset of the set of classes of the ontology. Considering a formal concept (A, B) where A is a set of individuals, the annotation is defined thanks to the derivation operator as follows:

A ⋄ = ∩ g∈A {C | O |= C(g)} 3
. Intuitively, it corresponds to the set of all classes of O instantiated by all individuals in A.

Combining Concept Annotation and Pattern Structures

In this paper, we propose to combine Concept Annotation with Pattern Structures. Indeed, such combination will allow us to only keep as annotation the most specific classes instantiated by all individuals.

To do so, we define a function δ : 2 G → 2 C(O) that associates an individual from G with the set of the most specific classes of the ontology O that this individual instantiates. Formally, given g

∈ G, δ(g) = min {C ∈ C(O) | O |= C(g)}.
δ(g) is considered as the description of the individual g. Given two individuals, g 1 , g 2 ∈ G, we define a similarity operator ⊓ to compare their two descriptions as follows:

δ(g 1 ) ⊓ δ(g 2 ) = min {lcs(C 1 , C 2 ) | ∀ (C 1 , C 2 ) ∈ δ(g 1 ) × δ(g 2 )}
The use of the least common subsumer allows to compute the most specific classes of the ontology that both g 1 and g 2 instantiates. Finally, given a formal concept (A, B), we annotate it thanks to the new derivation operator (•)

• : 2 G → 2 C(O) defined as A • = g∈A δ(g).
In the following sections, the defined functions and operators will be restricted to specific ontologies. Thus, δ i , ⊓ i and (•) •i will only be applicable to classes of an ontology O i .

Suggesting Mappings between Classes of Ontologies

In this section, we illustrate the combination of Concept Annotation and Pattern Structures with the use case of suggesting equivalence relationships between classes of two ontologies, denoted by O 1 and O 2 . To generate these mappings, we consider individuals that instantiate classes of both O 1 and O 2 . They also instantiate classes of another ontology, denoted by O ref , that is considered in this setting as the reference ontology, i.e. the feature we consider to build the original classification of the set of instances. In order to avoid complexity problems, we keep O ref of a small size.

Annotating the Concept Lattice with O 1 and O 2

In this next step, classes from O 1 and O 2 are considered for annotating the concept lattice. To this aim, we define two annotations (one per ontology) using the formalism defined in Subsection 3.2. Thereby, we use two functions δ 1 and δ 2 to associate an individual g with the set of the most specific classes from O 1 and O 2 that this individual instantiates. ⊓ 1 and ⊓ 2 are used to compute the similarity between descriptions of two individuals w.r.t. the two considered ontologies O 1 and O 2 . Finally, to compute the two annotations for each pattern concept (A, D), two derivation operators (•)

•1 : 2 G → 2 C(O1) and (•)

•2 : 2 G → 2 C(O2) are defined as follows:

A •1 = 1 g∈A δ 1 (g) A •2 = 2 g∈A δ 2 (g)
As a result, for each pattern concept (A, D), an annotated pattern concept

(A, D, A •1 , A •2 ) is obtained where A •1 (resp. A •2
) is the set of the most specific classes of O 1 (resp. O 2 ) that all individuals in A instantiate.

Reading Mappings from the Lattice

Let us consider an annotated pattern concept (A, D, A •1 , A •2 ). From the previous definitions, we know that A •1 ⊆ C(O 1 ) contains the set of the most specific classes of O 1 that all individuals in A instantiate. Similarly, A •2 ⊆ C(O 2 ) contains the set of the most specific classes of O 2 that all individuals in A instantiate. Therefore, considering each pair of classes (C 1 , C 2 ) ∈ A •1 × A •2 , we know that they are instantiated by the same set of individuals, i.e., individuals in A. Therefore, an equivalence relationship is suggested between C 1 and C 2 , based on the instances of the two classes.

Discovering Associated Classes as Domain and Range of a Predicate

In this section, we illustrate how Concept Annotation and Pattern Structures could be used to discover the most specific classes frequently associated as domain and range of a predicate from its instantiations in an ABox. Such domain and range characterization could indeed indicate common behavior at the class level. For example, considering DrugBank, a gene can be involved with a drug in a relationship whose action is specified (e.g., inhibitor, antagonist). Such relationships correspond to assertions of a predicate. As drugs instantiate classes of ATC and genes instantiate classes of GO, we could discover that instances of a GO class, considered as a family of genes, are frequently indicated as inhibitors of instances of an ATC class, considered as a family of drugs.

In the following paragraphs, we consider individuals, instantiating classes of an ontology O 1 , that are involved in relationships with other individuals, instantiating classes of an ontology O 24 .

Classifying Relationships in a Concept Lattice

First, a classification of relationships is established. O2) are defined as follows:

(•) •1 : 2 G → 2 C(O1) and (•) •2 : 2 M → 2 C(
A •1 = 1 g∈A δ 1 (g) B •2 = 2 m∈B δ 2 (m)

It is noteworthy that (•)

•2 is applied on the intent of the formal concept. As a result, each formal concept (A, B) is replaced by the annotated concept (A, B, A •1 , B •2 ) where A •1 (resp. B •2 ) is the set of the most specific classes of O 1 (resp. O 2 ) that all individuals in A (resp. in B) instantiate.

Reading the Domain and Range of a Relation from the Annotated Lattice

Let us consider an annotated concept (A, B, A Along the hierarchy of the lattice, the two annotations A •1 and B •2 behave in the opposite way. Indeed, A •1 , computed on the extent, contains more specific classes when the number of individuals in the extent decreases, i.e., when browsing the lattice top to bottom. On the contrary, B •2 , computed on the intent, contains more specific classes when the number of individuals in the intent decreases, i.e., when browsing the lattice bottom to top. Consequently, in annotated concepts at the top of the lattice, general classes of O 1 will be involved in domains and specific classes of O 2 will be involved in ranges. In annotated concepts at the bottom of the lattice, specific classes of O 1 will act as domain and general classes of O 2 will act as ranges. Therefore, this structure could be of interest in an interactive setting with an expert. Indeed by browsing the lattice depending on her specific constraints on the domains or ranges to discover, the expert could leverage on the lattice order to obtain more general or specific classes involved.

Discussion

Regarding the suggestion of equivalence relationships between classes of two ontologies, the approach needs to be validated on a real dataset where mappings already exist. One main identified drawback is that the current annotation process works under the Closed World Assumption. Thus, mappings are suggested considering that all instantiations are correct and none is missing. As many datasets are under the Open World Assumption, the suggested mappings may only be applicable on the considered set of individuals but may not be applied to other sets of individuals. Therefore, there is a need to validate the suggested mappings with an expert. One next challenge would be to define a new derivation operator to compute an annotation working under the Open World Assumption.

The original lattice is built from the set of individuals and the classes of a reference ontology O ref . However, other features could be considered for this original classification, such as the relationships involving the individuals, similarly to our previous work [9]. The choice of the features to consider are of importance as they impact the original lattice, which is the the "pivot" structure from which equivalence relationships are suggested. One user can then choose the specific features to consider to guide the generated mappings. In the proposed approach, equivalence relationships are suggested by considering annotated concepts separately. Nevertheless, the subsumption relations between concepts could be considered to suggest mappings of the form of subsumption relations between classes of the two considered ontologies. Such setting could therefore be used to align and structure folksonomies of various users in a social network.

Finally, the suggestion of mappings may not be the only use case of interest for the proposed setting. Indeed, by annotating the original lattice with classes of different versions of the same ontology, concept drift could be highlighted. For example, a semantic change in the classes between two versions of an ontology would be indicated by discovering in the annotations that the same set of individuals does not instantiate the same classes between the two versions.

Regarding the use case of discovering classes frequently associated as domain and range of a predicate, we could also benefit from an experiment on a real dataset. In this setting, as previously mentioned, there is an issue in selecting the interesting domains and ranges. Additionally to the interactive discovery process previously mentioned, various metrics could be considered to highlight interesting annotated concepts. For example, notions of support or confidence based on the cardinal number of the extent and / or intent could be of interest here. Similarly to the suggestion of equivalence relationships, this work does not benefit from the subsumption relations between formal concepts. Such relations could be used to build a hierarchical organization of associations of domains and ranges. However, as the two annotations behave in opposite ways, this hierarchy should not be read as an order.

Conclusion

In this paper, we combine Concept Annotation with the formalism of Pattern Structures. To illustrate our approach and its interest, we consider two use cases: suggesting equivalence relationships between classes of two ontologies and discovering classes frequently associated as domain and range of a predicate. The formalism of Pattern Structures is an advantage compared to our original work on Concept Annotation as it enables more complex annotations, using descriptions of objects and similarity operations. Moreover, we illustrate some other annotation possibilities: multiple annotations for one concept and annotations computed on the intent instead of the extent. As a result, starting from a concept lattice considered as a "pivot" structure, it is possible to obtain a complex structure representing or highlighting several relations between its components. The next challenges lies in experimenting our approach on real datasets and formalizing the properties of the annotation.

Introduction

Galois connections of different types as well as closure and kernel operators play important role not only in mathematics [14] but also in analysis of relational data, for example, object-attribute tables also known as transactional databases [13,[START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF][START_REF] Zaki | Data Mining and Analysis: Fundamental Concepts and Algorithms[END_REF], information systems [16,[START_REF] Wolski | Galois connections and data analysis[END_REF], formal contexts [18,[START_REF] Kuznetsov | Galois connections in data analysis: Contributions from the soviet era and modern russian research[END_REF], useritem rating matrices [9,[START_REF] Ignatov | Boolean matrix factorisation for collaborative filtering: An fca-based approach[END_REF], etc.

Thus, it has been shown that Boolean matrix factorisation performed by means of Galois operators on user-item binary matrix (obtained from user-item rating matrix under proper scaling) is not worse than ordinary SVD to capture similarity between users and items in terms of MAE, Precision and Recall [START_REF] Ignatov | Boolean matrix factorisation for collaborative filtering: An fca-based approach[END_REF]. The so called concept lattice, an ordered hierarchy of maximal submatrices (users, items) generated by Galois operators, has been proposed as a global search space for nearest neighbours of users and items [9]; however, such a lattice might be huge even for sparse input rating matrices and its generating is costly in terms of time and storage memory. An interesting attempt to scale this approach and form only necessary relevant neighbourhoods of users and items via Galois operators has been done in [5].

However, a systematic study of those useful connections and operators as well as their variants suitable for Collaborative filtering has not been performed yet. In this study, we introduce and discuss Galois operators for collaborative filtering setting to form neighbourhoods of users and items (as well as their sets in group recommendation scenario) and sets of prospective relevant items to rank by means of ordinary user-based (or item-based) approaches.

The remainder of the paper consists of five sections. In Section 2, we recall several definitions of Galois or derivation operators from Formal Concept Analysis and the associated closure operators. In Section 3, we explain how the existing operators can be used to form neighbourhoods of users (items) for a target user (item) as well as sets of prospective relevant items to recommend. Section 6 presents several simple experiments with user-based and item-based approaches where the formed neighbourhoods and sets of items used as parameters. Section 7 discusses related work and Section 8 concludes the paper.

Galois connections and related operators

First, we give the definition of Galois connection.

Let ϕ : P → Q and ψ : Q → P be maps between two ordered sets (P, ≤) and (Q, ≤). The pair of such maps is called a Galois connection between the ordered sets if: a. p 1 ≤ p 2 ⇒ ϕp 1 ≥ ϕp 2 ; b. q 1 ≤ q 2 ⇒ ϕq 1 ≥ ϕq 2 ; c. p ≤ ψϕp and q ≤ ϕψq.

The operators ϕ and ψ are called Galois operators. Let us define concrete version of Galois operators as it is done in Formal Concept Analysis (FCA) [18] over relational object-attribute tables but in collaborative filtering setting. Here, the role of objects is played by users and the role of attributes by items.

Let us consider a triple (U, I, R) called formal context in FCA, where U is a set of users, I is a set of items, and R ⊆ U × I. A pair (u, i) ∈ R iff user u ∈ U rated (liked or browsed) item i ∈ I.

In this case, for a subset of users X ⊆ U and a subset of items Y ⊆ I Galois operators (prime or derivation operators), (•) : 2 U → 2 I and (•) : 2 I → 2 U , are defined as follows: X = {i | uRi for all u ∈ X}, Y = {u | uRi for all i ∈ Y }.

In fact, X is the set of items that every user from X rated and Y are those users, who rated every item from Y .

One may check that two operators (•) form a Galois connection between (2 U , ⊆) and (2 I , ⊆).

Moreover, one may prove that (•) is a closure operator, i.e. for X, Z ⊆ U (or for X, Z ⊆ I).

1. X ⊆ Z ⇒ X ⊆ Z (monotony); 2. X ⊆ X (extensity); 3. X = X (idempotency).

A monotone and idempotent operator op(•) on 2 U is called a kernel operator iff for X ⊆ U : op(X) ⊆ X (intensity). Operators with intensity property play important role in Social Choice Theory since they help to select relevant alternatives from their input set [4]. We provide an example of kernel operator in section 3.

Let us discuss the meaning of several important properties of the introduced Galois operators in terms of Collaborative Filtering domain.

For X, X 1 , X 2 ⊆ U (similarly for Y, Y 1 , Y 2 ⊆ I):

4. X 1 ⊆ X 2 ⇒ X 2 ⊆ X 1 (antitony); 5. X = X .

The fourth property means that the more users we add to the initial set X 1 , the less is the number of their co-rated items (this property have been exploited in classic itemset mining algorithm, Apriori, in [2]). To understand the meaning of the remaining properties we need to discuss the interpretation of the result of (•) to X ⊆ U . The first prime returns the set X of all co-rated items for users from X, the second prime returns the set X of all users who rated all items from X . In fact, this set X may become larger than X or remain the same (Property 2). If we have a group of users Z and its subgroup X, then after looking at the items that X and Z rated, i.e. X and Z , we obtain by Property 4 that the set of items X is larger or equal to Z . By applying Property 4 one more time, we obtain that X is a subgroup of Z or equal to it. Property 2 says that by passing through items X co-rated by X, we may obtain some more users who rated all items X as well, i.e. our overlooked neighbours at the beginning. The third property says that it is not necessary to look at the co-rated items of the group X since everyone who rated all items from X is in X . That is X is a fixed point of operator (•) . These fixed points correspond to the called formal concepts in FCA, i.e. pairs (X , X ) for X ⊆ U (for itemsets they are defined similarly).

In collaborative filtering setting, for a particular target user u from U we are mainly interested in {u} , the items rated by u, and {u} , all users from U , who rated all items {u} . However, if we would require to show new items that those users also rated, applying the prime operator one more time, we would obtain {u} = {u} , i.e. nothing to potentially recommend. One of the remedies would be to delete u from {u} and obtain ({u} \ {u}) \ {u} , however we prefer to examine a richer set of possible alternatives and study their properties.

Connections for Collaborative Filtering

Let (U, I, R) be a formal context, then for a subset of users X ⊆ U and a subset of items Y ⊆ I then neighbourhood-forming operators, (•) : 2 U → 2 I and (•) : 2 I → 2 U , are defined as follows: X = {i | uRi for some u ∈ X}, Y = {u | uRi for some i ∈ I}. In fact, X can be considered as a query "show me all that have been bought by at least some user from X for X ⊆ U ; Y is interpreted as all users that bought at least one item from Y for Y ⊆ I. Theorem 1. For X, Z ⊆ U (similarly for X, Z ⊆ I) the following properties fulfil:

-If X ⊆ Z then 1. X ⊇ Z (antitony); 2. X ⊇ Z (antitony); 3. X ⊆ Z (monotony); -4. X ⊆ X (extensity); 5. X ⊇ X (intensity); 6. X ⊆ X (extensity); -7. X = X (idempotency); 8. X = X (idempotency); 9. (•) is not idempotent. In what follows, we mainly concentrate on one target user u, its neighbours founded by double combination of the derivation and neighbourhood forming operators, and items potentially relevant for that user obtained by triple combinations of those operators. Lemma 1. For u ∈ U : u = u (similarly for i ∈ I).

Theorem 2. For u ∈ U the following inclusions hold:

u = u ⊆ u = u = u = u = u ⊆ u = u .
Thus, every triple operator on the left hand side from u does not bring new items in comparison to those that u is rated. So, potentially we are interested in those from the right hand side, namely, u and u .

Since we should eliminate the target user u from the set of his neighbours and his rated items from the set of potentially relevant items. Let us introduce two final neighbourhood forming operators:

N ij (u) = u ij \ u and N ijk (u) = u ijk \ u i , where i, j, k ∈ { , }. There is also an option to subtract u from its neighbourhood as soon as possible in the chain of operators applied to u. So, there is one more variant for forming potentially relevant items:

N -u ijk (u) = (u ij \ u) k \ u i , where i, j, k ∈ { , }. The neighbours of the target user will be considered as {u} m \ {u} for a given operator. This operator is useful because we exactly specify the number of neighbours, thereby solving the problem of the lack of neighbours or presence of too many of them. Then, we take the k nearest of these neighbours by the other measure (e.g. cossim). Since we will look for new items for the prediction in the set ({u} m \ {u}) \ {u} , we may need to solve the optimisation problem in this case for m and k choice w.r.t. MAE or Precision and Recall.

Algorithm

1. Find neighbours to the target user u using one of the following methods:

-{u} \ {u} -{u} \ {u} -{u} m \ {u}.

2. Find the set of top k nearest neighbours to the target user u among the neighbours found at the previous step using a measure of similarity sim. Denote this set by N k 3. Find new items for the user u using the method:

(N k \ {u}) \ {u} 4. Make a prediction of the rating for each items found in the previous step.

Choose top n of them, if necessary.

Since steps 1 and 3 have been considered, let us discuss steps 2 and 4.

Similarity measure

Note that this step is not necessary, but useful. The number of neighbours found at the first step can be large, which leads to fewer items for the recommendation.

For our experiments, we will use the cosine measure of similarities. This measure is recognised as one of the best estimators of users' similarity [19]. Let u, ũ ∈ U , r u,i and r ũ,i be the ratings of item i ∈ I by users u and ũ, respectively, and the vector r u = (r u,1 , r u,2 , . . . , r u,n ) be the vector of user ratings u. Then we define the cosine measure of users' similarity cossim : U 2 → [0, 1] as follows 1 :

cossim(u, ũ) = r u • r ũ r u r ũ = i∈I r u,i r ũ,i i∈I (r u,i ) 2 i∈I (r ũ,i ) 2 .

Rating prediction

The predicted rating ru,i for an item i ∈ I by a user u ∈ U is a weighted combination of selected neighbours ratings, which is calculated as a weighted deviation from the average ratings of the neighbours. The general prediction formula is below:

ru,i = ru + ũ∈U (r ũ,irũ ) sim(u, ũ) ũ∈U | sim(u, ũ) | .

6 Experiments

Data

For test the model, we used data from the GroupLens 2 web site [20]. The data was collected through the MovieLens3 recommender service during the sevenmonth period from September 19th, 1997 through April 22nd, 1998. This data has been cleaned up -users who had less than 20 ratings were removed from this data set. This data set consists of:

-100 000 ratings (1-5) from 943 users on 1682 movies.

-Each user has rated at least 20 movies.

The data represents 100 000 lines of the form:

| user id | item id | rating | timestep |.
1 the formula should be adjusted by considering only commonly rated items in the numerator in case of missing ratings by u or ũ 2 https://grouplens.org/datasets/movielens/

Testing models

We will test the models based on the algorithm described in Section 5. Since these algorithms different only in the initial obtaining of the neighbours of the target user, we denote them as , , and m.

Model For this experiment, after applying all the operators, we took top k = 5 of the nearest neighbours by the cosine similarity measure. The result can be observed in table 1 Further studies of this model were not carried out since unacceptable tradeoff between such low values of Precision and Recall. The problem with this model is that we have neighbours only for < 3% users, and according to our Galois operator we have {∅} = I. Thus, we get the same predicted rating for all available movies, equals the average rating of the target user. Therefore we obtain low values of Precision and Recall.

Model

For this experiment, after applying all the operators, we took top k = 5 of the nearest neighbours by the cosine measure. The result can be observed in table 2: Further studies of this model were not carried out. In this model, we have a very good Precision, but its Recall does not suit us. This is due to the fact that in this case we have too many neighbours. The average number of neighbours From this experiment we can conclude that Precision varies slightly and Recall has a small increase in the larger sample. However, we have at least one recommendation for ≈ 97.3% users. That can be considered as an acceptable result since in most cases even a few recommendations is enough.

Slope One

For comparison, we took a well-known model Slope One [START_REF] Lemire | Slope one predictors for online rating-based collaborative filtering[END_REF]. In a reputed survey [10] it was shown that this model is one of the best for offline predicting the rating of items, while in our test we see how this model works for making recommendations.The result can be observed in table 5. This model works worse than ours. This is due to the fact that we do not limit the set of items for prediction.

We can see in figure 5, that sorting by the top n predicted ratings does not give strong effect on the precision of the recommendation by SlopeOne.

Related Work

To the best of our knowledge, the first paper that uses Formal Concept Analysis (FCA) and Galois Connections for Collaborative Filtering was [9]. Later on, a paper on concept-based biclustering for making recommendations over firms-terms contextual advertising problem appeared [START_REF] Ignatov | Concept-based Recommendations for Internet Advertisement[END_REF] based on a prior study on the same datset from Yahoo! (former Overture) with spectral clustering techniques [START_REF] Zhukov | Spectral clustering of large advertiser datasets[END_REF]; its latest version with revisited experiments and study of biclustering properties is presented in [START_REF] Ignatov | Concept-based biclustering for internet advertisement[END_REF]. In parallel, maximal-inclusion biclusters (in fact, formal concepts) were used in similar collaborative filtering scenario [START_REF] Symeonidis | Nearestbiclusters collaborative filtering based on constant and coherent values[END_REF] based on BiMax algorithm from [START_REF] Prelic | A systematic comparison and evaluation of biclustering methods for gene expression data[END_REF]. A reincarnated study in explicit FCA-terms was done in [6] with large real commercial datasets like PayPal. FCA-based biclusters were also used [21] for recommender system to facilitate educational orientation of Russian school graduates. In [START_REF] Ignatov | Recommendation of ideas and antagonists for crowdsourcing platform witology[END_REF]23], the authors used concept-based biclustering for making recommendations for crowdsourcing platform Witology to find similar user's ideas and the so-called users-antagonists for stronger team building.

As for interval-like ratings ranges, recommendations based on pattern structures [17] (an extension of FCA-approach for complex data) were firstly intro- duced and compared with SlopeOne approach in [START_REF] Ignatov | RAPS: A recommender algorithm based on pattern structures[END_REF]. Another attempt to build interval-based biclusters on MovieLens data was done in [11].

Since after its success in the NetflixPrize competition, a widely accepted method for Recommender Systems is matrix factorization [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF], the question on whether Boolean Matrix Factorisation (BMF) provides a competitive approach here emerged. The first answer was received in two works [START_REF] Nenova | An fca-based boolean matrix factorisation for collaborative filtering[END_REF][START_REF] Ignatov | Boolean matrix factorisation for collaborative filtering: An fca-based approach[END_REF], where BMFbased solution was compared with Singular Value Decomposition for Collaborative Filtering in terms of MAE and demonstrated equal quality. In the subsequent paper [3], BMF was studied against SVD (compared in terms of MAE, Precision and Recall) over matrices extended by user's and item's features representing the so-called context-aware approach. The main advantages of BMF lie in its high interpretability and promising efficiency of bit-wise Boolean operations whereas its main drawback resides in higher complexity due to combinatorial nature of the optimal number of factors determination (the cover or dimension problem) [8,7].

A separate venue is recommendation for Folksonomies based on higher order extenstions of FCA; let us cite only one recent paper with a detailed introduction of the problem [START_REF] Jelassi | Towards more targeted recommendations in folksonomies[END_REF].

As an unexpected example, FCA-based collaborative filtering can be also used as an ensemble technique to suggest a proper classifier within classification framework [START_REF] Kashnitsky | Can fca-based recommender system suggest a proper classifier?[END_REF].

An interested reader may also refer to a tutorial on FCA for Information Retrieval (IR) [22] and related fields with examples of FCA-based recommender systems as well as a survey on FCA for IR [12].

Conclusion

The obtained results seems to be a promising attempt to rethink neighbourhoodbased methods in terms of Galois connections and see their theoretical comprehensiveness and limits.

The problem of finding items that the user has not yet looked at, but should see in the near future is relevant for many models. We have managed to treat this problem with the help of Galois operators. Thus this paper being not only an interesting theoretical exercise, again indirectly confirmed the hypothesis: users who rate the same items tend to rate other items similarly.

As for possible venues of the forthcoming work one may take: 1) group recommendations by means of Galois operators; 2) explicit decomposition of m operator into a combination of two operators from the set of users to the set of items and vice versa; 3) extensive set of experiments with other large real datasets and more recent nearest-neighbours based techniques [1]; 4) scalability issues. A richer set of possible neighbourhood forming operators can be potentially found in [15].

Fig. 6 :

 6 Fig. 6: Iceberg lattice with a minimal support of 85% of the MUSHROOMS database.Figure extracted from [22].

  Fig. 6: Iceberg lattice with a minimal support of 85% of the MUSHROOMS database.Figure extracted from [22].

  such as rel(O,S,V) holds when object O in situation S has an expression value of V. Similarly to section 5.1, we can enumerate the pattern concepts: % Choose a subset of objects as the extent . { ext(O): rel(O,_,_) }. % The intervals of extent . interval(C,Min,Max):-rel(_,C,_) ; Min=#min{V,O: rel(O,C,V), ext(O)} ; Max=#max{V,O: rel(O,C,V), ext(O)}. % Object is valid on Condition. valid_on(O,C):-rel(O,C,V) ; interval(C,Min,Max) ; Min<=V ; V<=Max. % Object is valid for all Conditions. valid(O):-rel(O,_,_) ; valid_on(O,C): rel(_,C,_). % Avoid any model that do not include maximal number of objects. :-not ext(O) ; valid(O).

  Relational data. ex:x0 ex:r1 ex:x1 . ex:x0 ex:r2 ex:x2 . ex:x0 rdf:type ex:C0 . ex:x1 rdf:type ex:C1 . ex:x2 rdf:type ex:C2 . (b) RDF data.

Fig. 1 :

 1 Fig. 1: Relational data, the associated set of RDF triples and the formal context built from RDF triples.

  in order to compare the approaches. Given G a set of objects, M a set of attributes and I ⊆ G × M a binary relation between G and M , (G, M, I) is a formal context. Derivation operators (denoted . ) for a set of entities X ⊆ G and a set of attributes Y ⊆ M are X = {m ∈ M | ∀x ∈ X, xIm} and Y = {g ∈ G | ∀y ∈ Y, gIy}. From RDF data describing a KB, we build a formal context where G is the set of subjects of the triples (i.e. G = {s | s, p, o ∈ KB}) and M is the set of pairs (predicate, object) that appear in the RDF data (i.e. M = {(p, o) | s, p, o ∈ KB}). The incidence relation is defined as sI(p, o) ⇔ s, p, o ∈ KB. The set of attributes is a partition of two sets: M = M C ∪M D and M C ∩M D = ∅. The set M C is the set of all attributes (p, o) such that p = rdf:type. Since all the resources in the range of rdf:type are classes, M C corresponds to the set of all the classes we are trying to define. Hereafter, an attribute (rdf : type, C) will simply be denoted C. The set M D is the set of all attributes (p, o) such that p = rdf:type. Hereafter, an attribute (p, o) ∈ M D will be referred as a description and denoted ∃p : o where o is an abbreviation of an abstract class containing only o. Considering the example Figure 1b, the associated context is presented Figure 1c. Our goal is to build definitions of classes of the form C ≡ e 1 e 2 .

Turing_Award_laureatesRSports_carsRFrench_filmsRFig. 3 :

 3 Fig. 3: Definitions extracted by Eclat, ReReMi and Translator for each dataset.In order to be more readable, namespaces have been removed.

Fig. 4 :

 4 Fig. 4: Definitions extracted, categories defined, and triples inferred by Eclat(E), ReReMi(R) and Translator(T) for each dataset.

FCA

  starts with a binary relation R defined between a set O of objects and a set A of attributes. The tuple (O, A, R) is called a formal context. The notation (o, a) ∈ R or oRa means that object o has attribute a. We denote o ↑ = {a ∈ A|(o, a) ∈ R} the attribute set of object o and a ↓ = {o ∈ O|(o, a) ∈ R} the object set having attribute a. Similarly, for any subset o of objects, o ↑ is defined as {a ∈ A|a ↓ ⊇ o}. Then a formal concept is defined as a pair (o, a), such that a ↓ = o and o ↑ = a. One calls o the extension of the concept and a its intension.

Preliminary 3

 3 Let o (resp. a) be a subset of O (resp. A), there exists at most one concept x such that o x = o (resp. a x = a).

  }) which translates into "Mozart is to some ordinary musician as Alajmo is to some ordinary cook".More formally, from the relational proportion "o 1 is the o 2 of a", we can derive an analogical context as above. It is composed of objects o 1 and o 2 , described by four attributes: a is possessed by o 1 and not by o 2 , ã is possessed by o 2 and not by o 1 , b is possessed both by o 1 and o 2 and b is some attribute not possessed by o 1 nor o 2 . Secondly we complete the context with two objects o 3 and o 4 that are the complements of o 2 and o 1 with respect to the four attributes. The resulted context is the analogical context where a 1 = b, a 2 = a, a 3 = ã and a 4 = b.

  and a binary relation R, the subcontext (o, a) forms an analogical complex (o 1,4 , a 1,4 ) iff 1. the binary relation is compatible with the analogical schema AS:

  which are equivalent to a x = a x∧y ∩a x∧z and o x = o x∨y ∩o x∨z thanks to Preliminary 2. Similarly, a y = a x∧y ∩ a y∧t and o x = o x∨y ∩ o y∨t and

  called a set attributes and I ⊆ G × M is a relation called incidence relation, i.e. (g, m) ∈ I if the object g has the attribute m. The derivation operators (•) are defined for A ⊆ G and B ⊆ M as follows:

  of objects with S2 = {{abc}, {bcde}, {de}, {cde}, {ac}}. of objects with S4 = {{c}, {de}}. RCR = 10/15.

Fig. 1 .

 1 Fig. 1. Formal context and its coverings.

  A formal context from Figure 1, (1) represented as a set of transactions Covering (a)(b)(c) (b)(c)(d)(e) (d)(e) (a)(c)(d)(e) (a)(c) (2) Initial state. Covering (ac)(b) (b)(c)(d)(e) (d)(e) (ac)(d)(e) (ac) (3) The state after adding ac to the code table.

  Covering(ac)(b) (b)(c)(de) (de) (ac)(de) (ac) (4)The last step. bc is not added to the code table.

  Reorder patterns w.r.t.

Fig. 4 .

 4 Fig. 4. The principle of computing MDL-optimal and top-n sets of patterns

  ac ac deThe average length of the longest paths is 1.

( 1 )

 1 Fig. 7. Pattern set parameters: (1) the average covering rate of itemsets (i.e. the rate of crosses covered by patterns); (2) the average itemset usage (reflects typicality/representativeness of patterns). On the X-axis is different orderings of patterns, on the Y -axis is the covering rate and the average itemset usage for MDL-optimal set (blue) and top-n (green) set of the same size.

  b∈B {b} I . If A I = B and B I = A, the pair (A, B) is called a formal concept (or in short concept) with extent A and intent B. The set of all formal concepts of K is denoted by B(K) and defines the concept lattice B(K), via the order (A 1 , B 1 ) ≤ (A 2 , B 2 ) :⇔ A 1 ⊆ A 2 . The complementary context is defined as K c = (G, M, I c ) := (G, M, (G×M )\I) and the dual context as K d := (M, G, I -1 ), with the inverse relation I -1 := {(m, g) ∈ M × G | (g, m) ∈ I}.

Fig. 1 .

 1 Fig. 1. The relation I 1 ⊕ I 2 and (I 1 ⊕ I 2 ) c of the direct sum of K 1 and K 2 .

  the reflexive closure of E. The reflexive closure of G is defined as G ref := (V, E ref ). It follows that the graph G ref defines a tolerance space. On the contrary, let T be a tolerance space, then G T denotes the underlying graph. As usual, K n denotes the complete graph with n vertices and K m,n the complete bipartite graph with disjoint vertex sets A and B, such that |A| = m and |B| = n. An n-clique (or just clique) of G is a complete subgraph K n ≤ G. Every clique of a graph G induces a clique in the reflexive closure G ref and every isolated vertex of G induces a 1-clique in G ref . The difference between cliques and reflexive cliques is that the latter one can be identified with a formal concept and especially with a maximal square in E ref in the sense of tolerance relations.

Figure 2

 2 provides an example.

Fig. 2 .

 2 Fig. 2. The reflexive closure of a 4 cycle is depicted.

Fig. 3 .

 3 Fig. 3. The graph K 2,3 and the adjacency matrix of K ref 2,3 .

Fig. 4 .

 4 Fig. 4. The reflexive closure of I ∪ I -1, where E X denotes the identity on X .

  and {b}, B ⊆ M . The following types of concepts can occur. First, concepts which represent a row or column in (I ∪ I -1 ) ref , ({a}, {a} ∪ A I ), ({b}, B I ∪ {b}), ({a} ∪ B, {a}), (A ∪ {b}, {b}), and second concepts from B(K), that is (A, A I ), (B, B I ), as well as the above mentioned squares ({a} ∪ {b}, {a} ∪ {b}). It follows that for |G| + |M | < |I|, we have that rc(T) = |G| + |M | < sc(T) = |I|. In the next step we remove elements from I until |G| + |M | = |I|, which gives us rc(T) = sc(T) ≤ |G| + |M |. If |G| + |M | > |I|, it still holds that rc(T) = sc(T).

Finally, we

  notice that a graph G with G c = (K ∪ K d ) ref consists of complete graphs K |G| and K |M | , such that their vertices are symmetrically connected through the context K c .

Fig. 5 .

 5 Fig. 5. The symmetrization of K.

Fig. 6 .Fig. 7 .

 67 Fig. 6. The triple (A, K, B) defines the tolerance space T. τ : G M G α I M I -1 β

Theorem 5 .

 5 Let (A, K, B) be defined as above. For A, C ⊆ G and B, D ⊆ M , let A × B and C × D be subsets of I. If A × C ⊆ α and D × B ⊆ β, then (A∪D)×(B ∪C) is a rectangle of the underlying tolerance space. This rectangle is maximal if A, B, C and D are maximal with respect to the above stated inclusions. For A = C and B = D a (maximal) square is induced.Proof. If C × D ⊆ I, then D × C ⊆ I -1 .The rest of the proof is graphical (Fig.8).

Fig. 8 .BCorollary 2 .

 82 Fig. 8. The structure of maximal rectangles.C A A B

Fig. 1 .Fig. 2 .

 12 Fig. 1. Intension Graph of the statement "20th-century-born British authors who published in the 21st century"

  0

Fig. 10 .Fig. 11 .Fig. 12 .

 101112 Fig. 10. Distance Scale

  Input: O a set, a finite chain S := C(n) = {0, . . . , n}, two ratings A, B : O → S Definition 4 (Rating B is progressive given rating A) D + (A, B) := o∈O: A(o)≤B(o) rank B(o)rank A(o)

Fig. 1 :

 1 Fig. 1: A lattice violating the Jordan-Dedekind chain condition

Fig. 2 :

 2 Fig. 2: A complete lattice satisfying the Jordan-Dedekind chain condition but bearing a non triangular metric based on the rank function

1 Fig. 3 :

 13 Fig. 3: A non modular lattice satisfying the Jordan-Dedekind chain condition

Figure 4 .

 4 Should we pick ϕ(1) = a and ϕ(2) = b or should we opt for the other possibility ϕ(1) = b and ϕ(2) = a? Based on data, we would pick the possibility with the minimum distance.

3 LFig. 4 :

 34 Fig. 4: Lattices L, L which allow only for two rank preserving injections ϕ : L → L

Fig. 2 :

 2 Fig. 2: Hasse diagram of a crown

Fig. 3 :

 3 Fig. 3: Binarization

Fig. 4 :

 4 Fig. 4: Hasse diagram of the lattice associated with Table 3b

Fig. 5 :

 5 Fig. 5: Hasse diagram of binarization of the lattice associated with Table 3b

4. 1

 1 Classifying Individuals w.r.t. O ref in a Concept Lattice The first step is to build a concept lattice classifying the individuals w.r.t. the classes of O ref they instantiate. To this aim, we use the pattern structure (G, (2 C(O ref ) , ⊓ ref ), δ ref ). G is the set of individuals and 2 C(O ref ) is the powerset of the set of classes of O ref . δ ref and ⊓ ref are defined as in Subsection 3.2 w.r.t. the classes of O ref . From this pattern structure definition, we obtain pattern concepts (A, D) organized in a concept lattice, where A ⊆ G is a set of individuals and D ∈ 2 C(O ref ) is a set of the most specific classes of O ref that all individuals in A instantiate.

Property 2 .

 2 X, Z ⊆ U ⇒ X ⊆ Z (monotony of (•) ) (similarly for X, Z ⊆ I). Now we have 2 2 combinations of operators (•) and (•) to form neighbours, and 2 3 operator combinations to list potentially relevant items. Let us figure it out theoretically which of the proposed combinations are relevant for collaborative filtering.

Corollary 1 .

 1 Operator (•) is a kernel operator (antitone, extensive, and idempotent).

4

  Similarity measure inspired by Galois operatorsGiven two users u, ũ ∈ U , define for them a measure of similarity as ρ :U 2 → N, ρ(u, ũ) = |{u, ũ} |.For each user, we will reorder all users in ascending order:ρ(u, u 1 ) ≤ ρ(u, u 2 ) ≤ • • • ≤ ρ(u, u n ). So,each user u generates its renumbering of the set U . Let us define the neighbourhood-forming operator (.) m : U → 2 U as follows: {u} m = m i=1 {u i }. Property 3. ∀u ∈ U |{u} | ≤ m ≤ |{u} | ⇔ {u} ⊆ {u} m ⊆ {u}

Fig. 1 .

 1 Fig. 1. Precision and Recall by m for the model m

Table 4 .

 4 Precision and Recall for the model m over 1M MovieLens dataset top n recommendation Precision Recall time, sec all 61.4% 13.1% 25.7

Fig. 2 .

 2 Fig. 2. F1 score by m for the model m

Fig. 3 .

 3 Fig. 3. Precision and Recall by k for the model m

Fig. 4 .

 4 Fig. 4. F1 score by k for the model m

Fig. 5 .

 5 Fig. 5. Precision and Recall for SlopeOne over 100K MovieLens dataset

1

  Inductive Reasoning with Conceptual Space Representations (Invited Talk) Zied Bouraoui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 An Answer Set Programming environment for high-level specification and visualization of FCA Lucas Bourneuf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table 1 :

 1 Statistics of the datasets extracted with the SPARQL query. D is one of the four domains, whereas the predicate owl:objectProperty ensures that ?o is a resource, and not a literal nor a blank node.

	SELECT DISTINCT * WHERE { ?s ?p ?o . ?s dct:subject dbc:C . ?p a owl:ObjectProperty . }	D Turing_Award 2 642 Triples Objects |MC | |MD| 65 503 857 Smartphones 8 418 598 359 1 730 Sports_cars 9 047 604 435 2 295 French_films 121 496 6 039 6 028 19 459

3

.

Table 2 :

 2 Evaluation of the results. For each dataset, the number of quasidefinitions extracted (|B cand |) and evaluated true (|B def |) are reported, along with the average number of categories (|C i |) and descriptions (|D i |) per rule.

	(a) Turing_Award_laureates	(b) French_films
	X |B cand | |B def | B X def / B X cand |Ci|-|Di|	Eclat ReReMi Translator 47 12 11 30 9 9 .64 .75 .85 2-4 1-1 3-5	X |B cand | |B def | B X def / B X cand |Ci|-|Di|	Eclat ReReMi Translator 132 52 31 95 30 23 .72 .68 .74 2.8-4.5 1.3-1.4 2.6-4.1
	(c) Sports_cars	(d) Smartphones
	X |B cand | |B def | B X def / B X cand |Ci|-|Di|	Eclat ReReMi Translator 810 98 41 521 57 31 .64 .58 .76 4.3-7.8 1.6-1.8 3.1-3.1	X |B cand | |B def | B X def / B X cand |Ci|-|Di|	Eclat ReReMi Translator 546 36 93 371 12 89 .68 .33 .96 2.8-4.4 1.2-1.1 2.3-4.2

  , a 3 , a 4 , a 7 , a 8 , a 9 } {o 2 , o 5 } {a 1 , a 3 , a 4 , a 5 , a 7 , a 9 } {o 3 , o 5 } {a 1 , a 2 , a 4 , a 6 , a 8 , a 9 } {o 4 , o 5 } {a 1 , a 2 , a 3 , a 5 , a 6 , a 9 } Given two concepts x = (o x , a x ) and y = (o y , a y ), one has (o x ∪ o y ) ↑ = a x ∩ a y and (a x ∪ a y ) ↓ = o x ∩ o y . Given two concepts x = (o x , a x ) and y = (o y , a y ), one has o x ∪ o y ⊆ o x∨y , o x ∩ o y = o x∧y , a x ∪ a y ⊆ a x∧y and a x ∩ a y = a x∨y .

				{o 1 , o 2 , o 3 , o 4 , o 5 } {a 9 }
			{o 1 , o 2 , o 3 , o 5 } {a 4 , a 9 }	{o 1 , o 2 , o 4 , o 5 } {a 3 , a 9 }	{o 1 , o 3 , o 4 , o 5 } {a 2 , a 9 }	{o 2 , o 3 , o 4 , o 5 } {a 1 , a 9 }
	{o 1 , o 2 , o 5 } {a 3 , a 4 , a 7 , a 9 }	x	{o 1 , o 5 } {a 2 {o 2 , o 4 , o 5 } {a 1 , a 3 , a 5 , a 9 } {o 1 , o 3 , o 5 } {a 2 , a 4 , a 8 , a 9 } {o 1 , o 4 , o 5 } {a 2 , a 3 , a 9 } {o 2 , o 3 , o 5 } {a 1 , a 4 , a 9 } y z t	u	{o 3 , o 4 , o 5 } {a 1 , a 2 , a 6 , a 9 }	v
				{o 5 } {a 1 , . . . , a 9 }
		Fig. 1. The formal concept lattice of R (it is a Boolean lattice).
	Preliminary 1 Preliminary 2

  Proposition 3. Let x, y, z and t be four concepts, if (a x : a y :: a z : a t or o x : o y :: o z : o t ) then x : y W AP z : t.Proof. Let x, y, z and t be four concepts such that a x : a y :: a z : a t , or equivalently a x ∩ a t = a y ∩ a z and a x ∪ a t = a y ∪ a z (the APs between the subsets of attributes correspond to FAPs in the Boolean lattice of (2 A , ∪, ∩, ⊆)). Thanks to Proposition 2, a x ∩a t = a y ∩a z is equivalent to x∨t = y ∨z. Moreover, using Preliminary 1, we have (ax ∪ a t ) ↓ = o x ∩ o t and (a y ∪ a z ) ↓ = o y ∩ o z . Thus, a x ∪ a t = a y ∪ a z implies o x ∩ o t = o y ∩ o z .In the case where o x : o y :: o z : o t , the proof is similar since we also have (o x ∪o t ) ↑ = a x ∩a t and (o y ∪o y ) ↑ = a y ∩a z . }, {a 1 , a 3 }), z = ({o 3 }, {a 2 , a 4 }) and t = ({o 4 }, {a 1 , a 2 , a 5 }) are in WAP, due to Proposition 2. However, the Boolean APs a x : a y :: a z : a t and o x : o y :: o z : o t are both false. The WAP between concepts is less restrictive than the AP between sets of attributes: in a WAP, objects are allowed to possess attributes which are not shared by any other object concerned in the WAP.

	Comments. The converse is false. Let us consider the following formal context
	a1 a2 a3 a4 a5
	o1 o2 × o3 o4 × × ×	× × × ×	×
	its concept lattice is displayed on Figure 2. Concepts x = ({o 1 }, {a 3 , a 4 }), y = {o 1 } {a 3 , a 4 } {o 2 } {a 1 , a 3 } {o 3 } {a 2 , a 4 } {o 4 } {a 1 , a 2 , a 5 } {o 1 , o 2 , o 3 , o 4 } ∅ x y z t ({o 2 ∅ {o 1 , o 2 } {a 3 } {o 1 , o 3 } {a 4 } {o 2 , o 4 } {a 1 } {o 3 , o 4 } {a 2 } z t x y
	{a 1 , a 2 , a 3 , a 4 , a 5 }

⊥ Fig.

2

. In this lattice, x, y, z and t are in WAP but ax : ay :: az : at and ox : oy :: oz : ot are both false. Besides, x , y , z and t are in WAP and o x : o y :: o z : o t is true, but a x : a y :: a z : a t and the FAP x : y :: z : t are both false.

  a y ∪ a z and o x ∪ o t = o y ∪ o z a x : a y :: a z : a t and o x : o y :: o z : o t Let x, y, z and t be such that a x ∪ a t = a y ∪ a z and o x ∪ o t = o y ∪ o z , Proposition 4 implies the FAP x : y :: z : t, and then x : y W AP z : t. Hence, using Proposition 2, we have a x ∩ a t = a y ∩ a z and o x ∩ o t = o y ∩ o z . Consequently, a x : a y :: a z : a t and o x : o y :: o z : o t . The converse is trivial.Comments. From Corollary 1, a x : a y :: a z : a t and o x : o y :: o z : o t imply the FAP x : y :: z : t. However, the reciprocal is false. Let us consider the concept lattice displayed in Figure2: we have the FAP y :::

	This characterizes a particular case of FAP between concepts that we call a Strong
	Analogical Proportion (SAP). It is denoted x : y SAP z : t. In other words,
	four concepts in analogical proportion on attributes and on objects are said to be
	in strong analogical proportion.
	Proof.

  is the length of the dataset D = {g | g ∈ G} encoded with the code table CT and L(CT | D) is the length of the code table CT computed w.r.t. D. The objects are encoded by disjoint patterns in a greedy manner, i.e., starting from the top elements of CT. The length of pattern B is computed using an optimal prefix code given by Shannon entropy, i.e., the length l

Table 1 .

 1 Values of interestingness measures and ordering of patterns for the running example from Figure1, (1). An alternative ordering is given in (•), to select one ordering among the altervative ones additional rules are required to set.

	Concepts (A, B)	fr |A|	len |B|	area (len × fr)	patterns ordered w.r.t. length and frequency values of measures	patterns ordered w.r.t. area len fr values of measures
	({1245},{c}) 4 1 ({234},{de}) 3 2 ({145},{ac}) 3 2 ({12},{bc}) 2 2 ({24},{cde}) 2 3	4 6 6 4 6	{cde}; 3,2 {de} ({ac}); 2,3 {ac} ({de}); 2,3 {bc}; 2,2 {c}; 1,4	{de} ({ac}, {cde}); 6 {ac} ({de}, {cde}); 6 {cde} ({de}, {ac}); 6 {c} ({bc}); 4 {bc} ({c}); 4

Table 2 .

 2 Characteristics of datasets

	dataset	nmb. of	nmb. of	nmb. of	Number of MDL-optimal area area area len len	lift
		obj.	attr.	concepts	fr lift	len fr	len lift	fr	lift	len
	breast	699	16	702 36.0 32.2	20.4 37.3 37.3 33.5
	car	1 728	25	12 420 868.4 849.2 138.6 714.6 847.7 698.3
	ecoli	336	29	690 58.8 55.9	16.4 64.9 65.6 55.9
	iris	150	19	183 31.1 28.9	12.9 34.8 34.6 26.3
	led7	3 200	24	3 808 108.0 118.3	64.2 108.7 108.7 130.3
	pima	768	38	2 769 110.1 106.3	35.9 120.6 112.1 101.7

  Euclidean distances to the 1st nearest neighbors. The average distance for S3 is longer then for S4, thus S3 contains for diverse patterns.

	binary representation (abcde) bc 01100 de 00011 ac 10100 The average distance is (2 + 2 nearest neighbor Euclidean distance ac √ 2 bc(ac) 2 bc √ 2 √ 2)/3.	S2 bcde 01111 binary representation (abcde) cde 00111 abc 11100 ac 10100 de 00011 The average distance is nearest neighbor cde bcde (de) ac abc cde √ 2.	Euclidean distance √ 2 √ 2 √ 2 √ 2 √ 2
	(1)

  5) can be derived from the database. The SQL definitions of the attributes 19C, 20C and Context for the pubdate facet 21, which occur in both contexts, are not defined in the facets. Instead, every facet imports its attributes from exactly one underlying scale. A scale in FCA is a formal context which describes values; examples are ordinal scales (Fig.

		pubdate	19C	20C	21C
	DOB Lewis Carroll Virginia Woolf × 19C × Douglas Adams Neil Gaiman J. K. Rowling Stephen King Dan Brown Fig. 4. Context for the DOB facet 20C 21C × × × × ×	Alice in Wonderland × To the Lighthouse Hitchhiker's Guide Harry Potter 7 The Casual Vacancy Trigger Warning The Shining Doctor Sleep The Da Vinci Code Inferno	× × ×	× × × × × ×
		Fig. 5.

Table 1 :

 1 Example of formal concepts (associated with Table 2)

Table 2 :

 2 Example of a cross table associated with Table

Table 3 :

 3 Animal example formal context

	scale	teeth	att	swim	y	seed	feather	air
	salmon

Table 4 :

 4 Binarized formal context

Table 1 .

 1 A bicluster with constant value (shaded)

	1 1 4 3 5
	1 1 2 5 1
	3 3 4 2 1

Table 4 .

 4 A dataset with 5 objects and 5 attributes

	m1 m2 m3 m4 m5
	g 1 1 2 3 4 5
	g 2 4 2 1 ? 3
	g 3 2 3 4 1 1
	g 4 5 4 2 3 1
	g 5 2 1 5 4 3

Table 5 .

 5 Some examples of partitions overTable 4 Pair Partition p 1,2 {{g 1 , g 3 }, {g 2 , g 4 , g 5 }} p 1,3 {{g 1 , g 3 , g 5 }, {g 2 , g 4 }} p 1,4 {{g 1 , g 2 , g 5 }, {g 2 , g 3 , g 4 }} p 2,3 {{g 1 , g 3 , g 5 }, {g 2 , g 4 }} p 2,5 {{g 1 , g 2 , g 5 }, {g 3 , g 4 }}

Table 6 .

 6 Order of interest of 5 items, observed from certain visitors

	i1 i2 i3 i4 i5
	v1 1 2 3 4 5
	v2 3 ? 4 2 1
	v3 2 4 3 ? 1
	va 1 1 2 ? ?

Table 8 .

 8 Some CEC biclusters in Table7

	# Visitors	Items (in order)
	B1 v1	i1, i2, i3, i4, i5, i6, i7
	B2 v2	i6, i1, i4, i2, i3, i7, i5
	B3 v1, v3	i3, i4, i5, i7
	B4 v1, v3	i1, i4, i5, i7
	B5 v1, v4	i3, i5, i6
	B6 v2, v3	i6, i1, i4, i5
	B7 v1, v2, v3, v4 i2, i7

  To this aim, we consider the formal context (G, M, I) where G is the set of individuals instantiating classes from O 1 and M is the set of individuals instantiating classes from O 2 . Given g ∈ G, and m ∈ M , (g, m) ∈ I if and only if a relationship between g and m exists. Standard binary FCA is applied on this formal context to generate the associated formal concepts organized in a concept lattice. In the DrugBank example, G is the set of genes and M is the set of drugs. Considering g ∈ G and m ∈ M , we have (g, m) ∈ I if and only if a relationship between the gene g and the drug m exists in DrugBank.Consider a formal concept(A, B) from the concept lattice. A ⊆ G is a set of individuals instantiating classes of O 1 and B ⊆ M is a set of individuals instantiating classes of O 2 .From the definition of the derivation operators in FCA, we know that every individual in A is in relationship with every individual in B. To find the most specific ontology classes involved as domain and range of the predicate, two annotations for formal concepts are defined (one per ontology) using the formalism defined in Subsection 3.2. We use two functions δ 1 and δ 2 to associate an individual with the set of the most specific classes from O 1 and O 2 that this individual instantiates. δ 1 is applied on individuals g ∈ A and δ 2 is applied on individuals m ∈ B. ⊓ 1 and ⊓ 2 are used to compute the similarity between descriptions of two individuals w.r.t. the two considered ontologies O 1 and O 2 . Finally, to compute the two annotations for each formal concept (A, B), two derivation operators

	5.2 Annotating the Concept Lattice with O 1 and O 2

  •1 , B•2 ). Every individual in A is in a relationship with every individual in B. Furthermore, A •1 is the set of the most specific classes of O 1 that all individuals in A instantiate. Similarly, B •2 is the set of the most specific classes of O 2 that all individuals in B instantiate. Therefore, from this annotated concept, for the considered predicate, classes from A •1 as domain are associated with classes from B •2 as range.

Table 1 .

 1 : Precision and Recall for the model over 100K MovieLens dataset

	top n recommendation Precision Recall time, sec
	1	1.8% 0.01% 6.28
	2	0.8% 0.06% 6.28
	3	0.7% 0.08% 6.28
	. . .	. . .	. . .	. . .
	all	7.2%	99%	6.28

Table 2 .

 2 Precision and Recall for the model over 100K MovieLens dataset

	top n recommendation Precision Recall time, sec
	1	97.6% 0.5%	1.51
	2	97.4% 0.6%	1.51
	3	97.6% 0.7%	1.51
	. . .	. . .	. . .	. . .
	all	97.1% 0.9%	1.51

Table 5 .

 5 Precision and Recall for SlopeOne over 100K MovieLens dataset

	top n recommendation Precision Recall time, sec
	1	3.5%	0.2%	7.66
	3	8.1%	1.2%	7.66
	5	10.2% 2.5%	7.66
	10	13.1% 6.8%	7.66
	. . .	. . .	. . .	. . .
	all	7.7% 100%	7.66

https://gitlab.inria.fr/lbourneu/biseau

https://gitlab.inria.fr/lbourneu/biseau/blob/master/doc/user-doc.mkd

% The number of ext/1 atoms must not fall behind the minimal. :-{ext(_)} < nbobj * minsupp/100.

http://coron.loria.fr/

https://en.wikipedia.org/wiki/Category:Smartphones

https://gitlab.inria.fr/jreynaud/DefinitionMiningComparison

http://www.slate.fr/story/43841/massimiliano-alajmo

The condition to be crossed is not necessary for Identity 5.

The actual concept lattices have been defined as certain sub-lattices C[{x1, . . . , xn}].

Direct specification of Φc(a) in the facet (thus by-passing scales) is not supported.

C(g) indicates that g is an instance of C in the Description Logics formalism

It is not necessary for O1 and O2 to be distinct.

https://movielens.umn.edu

Acknowledgements

This work has been conducted with the support of "Région Lorraine" and "Délégation Générale de l'Armement".

Acknowledgments. Finally, we want to express our thanks to the anonymous referees for their suggestions to improve our paper.

Acknowledgments

This work is supported by the PractiKPharma project, founded by the French National Research Agency (ANR) under Grant No.: ANR-15-CE23-0028, and by the Snowball Inria Associate Team.

Acknowledgements The first author would like to thank our colleagues either for their piece of advice or earlier contribution, Rakesh Agrawal, Marat Akhamtnurov, Shlomo Berkovskiy, Vladimir Bobrikov, Ivo Düntsch, Chandan Reddy, Mehdy Kaytoue, Sergei Kuznetsov, Denis Kornilov, Maria Mikhailova, Amedeo Napoli, Elena Nenova, Alexander Tuzhilin, and Konstantin Vorontsov.

The work was supported by the Russian Science Foundation under grant 17-11-01294 and performed at National Research University Higher School of Economics, Russia.

-(R, +, 0, ≤) and (R + , * , 1, ≤) under the natural ordering of the real numbers;

-for any set E, (P(E), ∪, ⊆, ∅) and (P(E), ∩, ⊆, E); -a meet-semilattice (L, ∧, 1 L , ≤ L ) bounded from above by 1 L and a joinsemilattice (L, ∨, 0 L , ≤ L ) bounded from below by 0 L .

In order to distinguish the respective order relations, in the following we will use the symbol "≤ P " for the order relations of a given poset P and "≤" of a given ordered monoid M, respectively:

Definition 2 ( [8]) Let P = (P, ≤ P ) be a poset and M = (M, * , ε, ≤) be an ordered monoid. A mapping

-for all p ∈ P : ∆(p, p) = ε, -for all p, t, q ∈ P with p ≤ P t ≤ P q : ∆(p, t) * ∆(t, q) = ∆(p, q). Furthermore, ∆ is called weakly positive, if ε ≤ ∆(p, q) for all (p, q) ∈ ≤ P .

In case P = (P, ≤ P ) is a lattice, ∆ is called supermodular w. r. t. (P, M) (resp. modular), if ∆(p ∧ q, q) ≤ ∆(p, p ∨ q) (resp. equality) holds for all p, q ∈ P .

So far, functorial mappings are only defined on the order relation ≤ P ⊆ P ×P . In order to extend functorial mappings from the ordering ≤ P to its superset P × P , we need Definition 3 ([8]) Let P be a set, and M = (M, * , ε, ≤) be an ordered monoid.

A function d :

If in addition, (A3) holds, d is a generalized metric (GM) w. r. t. (P, M):

(A3) for all (p, q) ∈ P × P : d(p, q) = ε = d(q, p) =⇒ p = q

Generalized metrics with applications to ratings and formal concept analysis -D + (A, B) is well defined and finite if O is finite: since there are only finitely many objects to be rated, we do not need to worry about non finite or even non countable sets.

A little less obvious is the following property:

To see this we apply Theorem 1 as follows:

The set O of all ratings O : A → S is endowed with a natural order:

O is even a lattice where

.

for all real numbers a, b, ∆ + is even a modular map.

Applying Theorem 1, thus D + , which is the the extension of ∆ + , is triangular.

and B is more progressive than A. In order to measure a symmetric distance between ratings, we proceed as follows: We will use D to derive a brute-force algorithm to solve the following issue: Rating scales do not need to be identical since different raters might use different rating scales:

Question: how can we compare ratings in case the rating scales are of different length?

The algorithm we propose will use embeddings (order preserving injections) of one chain into the other and minimize the distance D over all possible embeddings. For example, there are 3 possibilities of embedding C(1) into C(2), and 6 possibilities of embedding C(1) into C(3).

Algorithm 1 (Scaling with minimal distance) -

Binary Lattices

Célia Châtel, François Brucker, Pascal Préa Aix Marseille Univ, Université de Toulon, CNRS, LIS (UMR 7020), Marseille, France École Centrale Marseille {celia.chatel, francois.brucker, pascal.prea}@lis-lab.fr Abstract. A concept lattice is said to be binary if every formal concept covers at most two other concepts and is covered by at most two. These particular lattices can be seen as a generalization of decision trees (which rely on binary yes/no decisions). A non-binary lattice is binarizable if and only if it can be embedded into a binary lattice. We show in this paper that crown-free lattices are exactly binarizable ones. We also provide an algorithm which binarizes any crown-free concept lattice by adding and modifying a minimum number of concepts. in Table 2c. Similarly, we can obtain a bicluster with multiplicative coherent values as shown in Table 2d using a constant for each row and each column. The main difference is that, instead of adding, we multiply them. Another interesting type is the CEC bicluster, also known as order-preserving submatrix [4]. In this type of bicluster, each row induces the same linear order across all columns. For example, in the bicluster in Table 2e, each row follows column1 ≤ column2 ≤ column4 ≤ column3. Moreover, a bicluster with coherent evolution on the rows can be defined similarly, as shown in Table 2f.

Those different types of biclusters are useful when we are interested in identifying a group of people who behave similarly according to a set of attributes. This group identification is necessary in the task of collaborative recommendation, because in the process of making a suggestion to a person, we first identify the people who are similar to him/her. As suggested in [3] the bicluster-based recommendation may give a better performance than state-of-the-art recommendation algorithms.

Biclustering Using Partition Pattern Structures

Biclustering has many common elements with FCA. In FCA, from a binary matrix we try to find a maximal submatrix whose elements are 1. In other words, the objective is to identify maximal constant-value biclusters (but only for biclusters whose values are 1). Hence, a formal concept can be considered as a bicluster of objects and attributes. Furthermore, formal concepts are arranged in a concept lattice, that can describe the hierarchical relation among all biclusters.

Consider the matrix given by Table 3, where we are interested in finding constant-column biclusters. We recognize that the values of m 1 "break" the objects into two sets: {g 1 , g 2 } and {g 3 , g 4 }. The same "break" is also obtained from the values of m 4 . In particular, we can see that the pair ({g 1 , g 2 }, {m 1 , m 4 }) corresponds to a constant-column bicluster. Therefore, it is possible to mine this type of bicluster using this "breaking" -or "partitioning" -technique. Moreover, this technique can be performed using partition pattern structures -an extension of FCA.

In this section, first we will recall the constant-column biclustering approach using partition pattern structures [6]. After that, we will explain the possibility to perform CEC biclustering based on this approach.

Training/test set split procedure

We will partially imitate online testing when only a part of information on ratings for test users is known, as our operators are more focused on building recommendations than on forecasting ratings. We will follow the bimodal crossvalidation procedure from [START_REF] Ignatov | A new cross-validation technique to evaluate quality of recommender systems[END_REF]. To do this, we first find the sets U hidden and I hidden , where:

-U hidden is a randomly selected 20% of all users U , -I hidden is a randomly selected 20% of all items I.

Then we hide all the information about the ratings at the intersection (U hidden , I hidden ) as shown below and call this matrix trainset

where r u,i is the rating item i by users u or * if this user did not rate this item yet.

Similarly, testset is a matrix containing all the hidden information. Each experiment will be carried out 100 times to eliminate the dependence on random partitioning.

Adjusted Precision and Recall

We used standard measures to compare studied models: Precision and Recall.

They can be defined as follows:

where for user u ∈ U hidden :

-{relevant} is the set of all items that the user u rated, -{retrieved} is the set of all items that we recommended to the user u.

Note special cases:

is more than half of the total number of users U . Therefore, the cosine measure does not correctly give us top k nearest neighbours, e.g., 100% of similarity for the only one commonly rated item. After applying our Galois operator, we get that for ≈ 93% users we have nothing to recommend.

Model m For this experiment, top m = 50 of the nearest neighbours by measure based on the Galois connection was taken and then top k = 5 of the nearest neighbours by the cosine measure were selected.The result can be observed in table 3: This model produced acceptable results, and thus we can work with it. We have at least one recommendation for ≈ 87.3% users. It can be considered normal for our model. The maximum possible number of recommendations for the user on average is 3-4 movies. So we do not have high recall for all of recommendations. Possibly, this problem should be solved in the transition to larger data (like 10M ratings) or its portion with moderately large profiles of users. Also note that Precision is not greatly reduced by recommending a large number of movies. This is unusual for most recommendation systems. So we can immediately recommend to the user u all the movies that fall into the set (N k \ {u}) \ {u} and do not predict the ratings for these movies. Now we need to understand whether it is necessary to solve the optimisation problem. To do this, we first look at how the values of Precision, Recall, and F 1 score change, fixing k, where F 1 score is considered according as follows: F 1 = 2 P recision•Recall P recision+Recall . Then fixing m and see how the Precision and Recall change in depending on k.

We can see from figures 1, 2, 3, and 4 that the Precision is directly proportional to m and k, and the Recall is inversely proportional to m and k. Therefore, it is not necessary to solve an optimisation problem for any of the parameters.

Next, we experimented with the MovieLens dataset composed by 1M ratings and look at the results. For this experiment, top m = 100 of the nearest neighbours by measure based on the Galois operators and then top k = 10 of the nearest neighbours by the cosine measure were taken. We have found out