Sergei O Kuznetsov

Amedeo Napoli
email: amedeo.napoli@loria.fr

Francesco Kriegel
email: francesco.kriegel@tu-dresden.de

Diana Troancȃ
email: dianat@cs.ubbcluj.ro

Dominik Brosius
email: dbrosius@uni-koblenz.de

Steffen Staab
email: staab@uni-koblenz.de

Justine Reynaud

Yannick Toussaint

Zina Ait-Yakoub
email: ait.yakoub@hotmail.fr

Yassine Djouadi
email: djouadi@irit.fr

Didier Dubois
email: didier.dubois@irit.fr

Henri Prade
email: henri.prade@irit.fr

Aleksey Buzmakov
email: avbuzmakov@hse.ru

Giacomo Kahn
email: giacomo.kahn@isima.fr

Yannick Loiseau

Olivier Raynaud

Marwa Trabelsi
email: trabelsimarou@live.comnida.meddouri@gmail.com

Nida Meddouri

Mondher Maddouri
email: maddourimondher@yahoo.fr

A Reachability

Keywords: Description Logics, Formal Concept Analysis, Most Specific Consequence, Error Tolerance, General Concept Inclusion, TBox, Interpretation, Model, Stream, Incremental Learning, Automatic Learning 1 Lattice Visualization, Interactive Exploration, Web of Data, Formal Concept Analysis. Linked Data Querying through FCA-based Schema Indexing Linked Data, Formal Concept Analysis, Schema Indexing Formal Concept Analysis, Pattern Structures, Triadic Concept Analysis, Linked Open Data fuzzy FCA, pattern structures, scaling Machine Learning, Classification, Web Usage Mining machine learning, classification, decision tree learning, formal concept analysis, pattern structures Data Mining, Supervised Classification, Formal Concept Analysis

The four preceding editions of the FCA4AI Workshop showed that many researchers working in Artificial Intelligence are deeply interested by a well-founded method for classification and mining such as Formal Concept Analysis (see http://www.fca4ai.hse.ru/). The first edition of FCA4AI was co-located with

Invited Talk Constraint Programming for Constrained Clustering

Christel Vrain

Université d'Orléans INSA Centre Val de Loire, LIFO EA 4022 45067 Orléans, France christel.vrain@univ-orleans.fr Abstract. Several works have shown the interest of declarative frameworks, such as Constraint Programming, SAT, Integer Linear Programming, for Data Mining [9,10,12,8,14,15]. Relying on Constraint Programming (CP) has several advantages: first, its inherent declarativity allows to easily model constraints on the Data Mining problem at hand, second, CP has the ability either to enumerate all the solutions or to find an optimal solution, in case of an optimization problem. Moreover, it relies on constraint propagation, which often allows to efficiently prune the search space. I will mainly focus on constrained clustering [16,7]: user constraints are put on the solutions, thus allowing to get a clustering closer to the one expected by the user. After giving some backgrounds on CP, I will present the seminal work of [9] on CP for itemset mining, its extension to k-pattern set mining under constraints [13] and its application to conceptual clustering. The talk will then mainly be focused on distance-based constrained clustering. I will show how we have modeled this task in CP [1,4,3], the difficulties we have had to face, the solutions we have developed [2,5]. The interest of relying on CP will be illustrated through several extensions [4,6,11]. The work on distance-based constrained clustering in CP is a joint work with T.B.H. Dao and K.C. Duong.

Axiomatization of General Concept Inclusions from Streams of Interpretations with optional Error Tolerance 1 Introduction

Description Logics [2,[6][7][8] are a family of well-founded languages for knowledge representation with a strong logical foundation as well as a widely explored hierarchy of decidability and complexity of common reasoning problems. The several reasoning tasks allow for an automatic deduction of implicit knowledge from given explicitly represented facts and axioms, and many reasoning algorithms have been developed. Description Logics are utilized in many different application domains, and in particular provide the logical underpinning of Web Ontology Language (OWL) [16] and its profiles. An interesting problem is the task of (semi-)automatic generation of terminological axioms, so-called general concept inclusions (GCIs), from given data. For example, in [4,10] Baader and Distel have generalized the construction of implicational bases from so-called formal contexts [12,15] in the field of Formal Concept Analysis [14] to the construction of bases of EL ⊥ -GCIs from interpretations in Description Logics. The main difference of the underlying data structures is that interpretations additionally allow the expression of binary relations between objects, which implies a number of technical and theoretical difficulties that have been solved by them. In case of incompleteness of the input data set, a technique of Attribute Exploration [11][12][13] can be utilized to axiomatize implications in a sound and complete manner. This approach furthermore presupposes an expert in the domain of interest that is able to correctly answer all queries posed to her. In [5,10] Baader and Distel have as well extended this technique from formal contexts to interpretations. A further work in the intersection of Formal Concept Analysis and Description Logics was developed by Rudolph in [20,21]. He generalized Attribute Exploration to Relational Exploration, a technique that processes an interpretation in a multi-step approach where in each step the role-depth of the involved concept descriptions is increased. In particular, Relational Exploration is a sound and complete deduction calculus for GCIs in the Description Logic FLE. A weakness of the exploration methods is the requirement of an expert that is able to truthfully answer all questions posed to it.

In order theory, closure operators (clop) denote mappings in a powerset -or more generally, in a lattice -which are extensive, monotone, and idempotent. Many types of data sets give rise to an induced closure operator in such a way that an implication is valid in the data set if, and only if, it is valid in the closure operator. For example, each formal context (G, M, I) induces the clop X → X II on the powerset ℘(M), and each interpretation (∆ I , • I ) induces the clop C → C II in the lattice of all EL ⊥ -concept descriptions ordered by subsumption and factorized by equivalence ≡. In a recent paper [19], the author investigated how implicational bases for closure operators can be computed in a parallel manner. Furthermore, it was shown that the set of all clops in a complete lattice constitutes a complete lattice itself, and formulae for computing infima and suprema of clops were provided. In this document, we will introduce a closure operator C → C T induced by a TBox T , and will furthermore provide applications for computing bases of GCIs for the infimum as well as the supremum of C → C T and C → C II . This document is structured as follows. Section 2 gives a brief overview on the easy description logic EL ⊥ . Then, Section 3 cites some related work, and recalls important notions. Section 4 introduces the notion of a most specific consequence with respect to a TBox, and shows how to define a closure operator induced by a TBox. Section 5 then discusses applications of infima and suprema of clops induced by interpretations and TBoxes, and Section 7 draws some conclusions. Note that proofs are not included, but the interested reader can find them in the corresponding technical report [17].

The Description Logic EL ⊥

The syntax and semantics of the light-weight description logic EL ⊥ are introduced as follows. Throughout the whole document assume that (N C , N R ) is a signature, i.e., N C is a set of concept names, and N R is a set of role names. An EL ⊥ -concept description is a term that is constructed by means of the following inductive rule:

C ::= ⊥ | | A | C C | ∃ r. C.
A general concept inclusion (abbr. GCI ) is an expression C D where both the premise C as well as the conclusion D are EL ⊥ -concept descriptions. A TBox is a set of GCIs.

The role depth rd(C) of an EL ⊥ -concept description C is inductively defined as follows: An interpretation I := (∆ I , • I ) consists of a non-empty set ∆ I , called the domain, and an extension function • I that maps concept names A ∈ N C to subsets A I ⊆ ∆ I , and maps role names r ∈ N R to binary relations r I ⊆ ∆ I ×∆ I . Then, the extension function is canonically extended to all EL ⊥ -concept descriptions by the following definitions: In case T = ∅ we may ommit the prefix "∅ | =". However, then we have to carefully interpret an expression C D -it either just denotes a general concept inclusion, i.e., an axiom, without stating where it is valid; or it expresses that C is subsumed by D (w.r.t. ∅), i.e., C I ⊆ D I is satisfied in all interpretations I. An analogous hint applies to concept equivalences C ≡ D.

It is readily verified that the subsumption constitutes a quasi-order on the set EL ⊥ (N C , N R ) of all EL ⊥ -concept descriptions over the signature (N C , N R ). Hence, the quotient of EL ⊥ (N C , N R ) with respect to the induced equivalence ≡ is a partially ordered set (a poset). (In the following we will not distinguish between the equivalence classes and their representatives.) The poset is even a bounded lattice. Of course, ⊥ is the smallest element, and is the greatest element. Furthermore, the conjunction corresponds to the infimum operation, and the least common subsumer mapping ∨ corresponds to the supremum operation. Remark that the least common subsumer (abbr. lcs) C ∨ D of two EL ⊥ -concept descriptions C and D is (up to equivalence) uniquely defined by the following conditions: 1. C C ∨ D as well as D C ∨ D, and 2. for each EL ⊥ -concept description E, if C E and D E, then C ∨ D E. It is easy to see that the equivalence ≡ is compatible with both and ∨. In the sequel of this document, we shall denote this bounded lattice by EL ⊥ (N C , N R ) := (EL ⊥ (N C , N R ), ) /≡. For a role-depth bound δ ∈ N, EL ⊥ (N C , N R ) δ is the set of all EL ⊥ -concept descriptions with a role depth of at most δ, and accordingly EL ⊥ (N C , N R ) δ := (EL ⊥ (N C , N R ) δ , ) /≡ symbolizes the corresponding bounded lattice of (equivalence classes of) EL ⊥ -concept descriptions. Note that EL ⊥ (N C , N R ) δ is complete if the underlying signature (N C , N R ) is finite.

Related Work

Baader and Distel introduced a technique for the axiomatization of general concept inclusions that are valid in a given interpretation. More specifically, they interconnected Formal Concept Analysis with Description Logics by defining so-called induced formal contexts such that its canonical base can directly be converted into a base of GCIs for the underlying interpretation. However, there was no possibility to include existing knowledge. For the case where a set of GCIs valid in the given interpretation is available, a solution for the computation of a relative base of GCIs has been proposed in [18]. However, it was not clear how to proceed in presence of an interpretation I and a TBox T where I | = T . This problem will be tackled in the following section.

Beforehand, we recall the notion of a model-based most specific concept description. Let I be an interpretation, and consider a set X ⊆ ∆ I as well as a role-depth bound δ ∈ N. Then an EL ⊥ -concept description C is called a role-depth-bounded model-based most specific concept description (abbr. mmsc) of X with respect to I and δ if the following statements hold: 1. rd(C) ≤ δ, 2. X ⊆ C I , and 3. for all concept descriptions D, if X ⊆ D I , then ∅ | = C D. As an immediate consequence of the definition we infer that the mmsc of X w.r.t. I and δ is unique up to equivalence. Hence, we may speak of the mmsc, and denote it by X I δ . 4 Most Specific Consequences with respect to a TBox For a given EL ⊥ -TBox T , and an EL ⊥ -concept description C, one may ask for a concept description D which is most specific with respect to the condition that C is subsumed by D w.r.t. T . Such a concept description is called most specific consequence, or most specific subsumer (abbr. mss). Note that Distel has investigated a dual notion in [10,Chapter 7], namely that of a minimal possible consequence, which he utilized to constitute an algorithm for the exploration of ontologies, called ABox Exploration. To emphasize this duality, it is reasonable to use the name of a minimal certain consequence.

In this section, the notion of a most specific consequence shall be formally introduced, and necessary as well as sufficient conditions for its existence will be explored. Furthermore, we investigate its relationship to entailment with respect to a TBox. The next section then provides at least one application that utilizes most specific consequences to construct a base of GCIs that are both valid in a given interpretation as well as are entailed by a given TBox.

As an exemplary TBox, consider T := {A ∃ r. A}. It can be readily verified that for each n ∈ N, the concept description (∃ r.) n A is a consequence (i.e., a subsumer) of A with respect to T . However, (∃ r.) n+1 A is more specific than (∃ r.) n A, and thus a most specific consequence of A w.r.t. T does not exist in the description logic EL ⊥ with descriptive semantics (as introduced in Section 2). There are two solutions to tackle this problem of existence of most specific consequences. The first one is to use the extension of EL ⊥ with greatest fixpoint semantics. This extension has been extensively studied in [1,3,10], and in particular it has been shown that this extension can handle terminological cycles (as present in the given TBox T above). In particular, EL ⊥ gfp -concept descriptions are pairs C := (A C , T C ) where T C is a TBox, and A C is a defined concept name of T C . We do not introduce the full machinery of the semantics of EL ⊥ gfp here, but rather refer the interested reader to [1,3]. However, it can be shown that the most specific consequence of the example above indeed exists in EL ⊥ gfp , and is given by (A, T ). It is straight-forward to claim that most specific consequences always exist in EL ⊥ gfp , but nevertheless a corresponding proof is outstanding. Another solution for ensuring the existence of most specific consequences is to restrict the role-depth of the concept descriptions under consideration, as this has been done in [9] to ensure the existence of model-based most specific concept descriptions in EL ⊥ with descriptive semantics. We introduce the following definition. Provided that such role-depth-bounded most specific consequences exist, they are unique up to equivalence, and hence we may then speak of the most specific consequence, and we shall denote it by C T δ for a given concept description C, a TBox T , and a role-depth bound δ. By Definition 1, T | = C C T δ . Furthermore, from T | = C C we conclude that ∅ | = C T δ C. In summary, T | = C ≡ C T δ . Lemma 2. Role-depth-bounded most specific consequences always exist, provided that the signature is finite. Lemma 3. Let T ∪ {C D} be an EL ⊥ -TBox such that D has a role depth of at most δ. Then the following statements are equivalent:

This document does not include a method for the computation of most specific consequences, and leaves this problem open for future research. However, we have shown that their existence is guaranteed in the case of descriptive semantics when the candidate concept descriptions are restricted in their role depth. In particular, the notion defined in Definition 1 always exists. As a next step, we provide a technique that allows for the computation of a TBox from a stream of interpretations and that utilizes those most specific consequences.

Lemma 5. The mapping C → C T δ is a closure operator in the dual of EL ⊥ (N C , N R ) δ .

Axiomatization of General Concept Inclusions from Streams of Interpretations

Consider a setting where a stream of interpretations I n , n ∈ N, can be observed, and furthermore for each time point n ∈ N, a TBox T n shall be constructed such that for each GCI C D, T | = C D if, and only if, I k | = C D for all previous time points k ≤ n. Of course, for the initial moment n = 0, we may simply compute T 0 as a base of GCIs for I 0 , utilizing the approach of Baader and Distel [4,10]. For the following moments n ≥ 1, we may of course also construct a base of GCIs for the disjoint union of the interpretations I 0 , I 1 , . . . , I n . However, since the method requires the construction of so-called induced contexts the size of which may be exponential in the size of the domain of the interpretation, this technique could possibly be infeasible for late time points. Furthermore, it requires the storing of all interpretations observed so far. We want to present another technique for solving the above mentioned task. Please note that this problem was already addressed in [18] for the case of

I n+1 | = T n .
Here, we propose a solution that circumvents this rather restrictive precondition. The infimum of • T and • II is the greatest closure operator below both • T and • II . The following lemma recalls an important property of infima of clops, specifically tailored to the case of implications of concept descriptions, i.e., of general concept inclusions as they are more commonly called. Lemma 6. Let I be an interpretation, T an EL ⊥ -TBox, and C D a general concept inclusion such that both premise and conclusion have a role-depth not exceeding δ. Then the following statements are equivalent: As a conclusion, we infer the following incremental method for the computation of a sequence of TBoxes from a sequence of interpretations:

1. Upon availability of the first observed interpretation I 0 , compute its canonical base of GCIs, as proposed by Baader and Distel in [4,10]. If only concept descriptions up to a certain role depth shall be considered, then the variant described by Borchmann, Distel, et al., in [9] is sufficient. 2. For each new interpretation I n+1 , compute the canonical base of the infimum of the clops that are induced by the current TBox T n as well as by the newly observed interpretation I n+1 .

It is readily verified that -by construction -for each time point n ∈ N, the TBox T n entails a GCI C D if, and only if, C D is valid in the interpretations I 0 , . . . , I n .

Error-Tolerant Axiomatization of General Concept Inclusions from Interpretations

Assume that we were given an interpretation I as well as a TBox T such that I contains observations that may be possibly faulty due to inaccurate generation methods, and that T is certainly valid in the domain of interest, e.g., as it has been hand-crafted by experts.

In particular, we assume that I is not a model of T , i.e., that at least one domain element in I exists which serves as a counterexample against at least one GCI from T . However, we are expected to axiomatize terminological knowledge from I, which is valid in the unknown domain of interest. As a solution, we will construct the implicational base of the supremum of the clops that are induced by I, and by T , respectively. It is then ensured that those implications are considered which are valid for all those domain elements of I that respect the GCIs in T , i.e., that we axiomatize general concept inclusions from I that are compatible with the axioms contained in T . In a certain sense this yields a method for an error correction in I when learning GCIs. We will describe a short motivating example. Define a TBox T and an interpretation I as follows:

N C := {Person,

Person child child

Consider the GCI Car ∃ child. Wheel. Of course, it is valid in I, and furthermore is contained in the canonical base of I when applying the construction from [4,10].

We can show that the above mentioned GCI is also valid II δ T δ for δ ≥ 1:

Car II δ ≡ Car ∃ child. Wheel (Car ∃ child. Wheel) T δ ≡ Car ∃ child. Wheel Person ⊥ ≡ ⊥,
The closure of Car with respect to the supremum is the least common subsumer of those concept descriptions that are closures of both C → C II δ and C → C T δ , as well as are subsumed by Car. It is easy to see that this supremum closure can be computed by an exhaustive repeated application of both closure operators until a fixpoint is reached. As we have seen above, the fixpoint ⊥ is reached after the first iteration, and hence ⊥ is the supremum-closure. However, the GCI is a consequence of the more specific valid GCI Car ⊥, and hence would not have been axiomatized upon construction of the canonical base. In particular, we see that d is not compatible with T -in contrast to the other domain elements e, f, and g. Eventually, Car is a pseudo-closure of the supremum, and hence the canonical base contains the axiom expressing the non-existence of cars.

Conclusion

We have defined the notion of most specific consequences with respect to TBoxes, and considered the corresponding closure operator. We have investigated the interplay of this closure operator induced by a given TBox with the closure operator induced by an interpretation -more specifically, we have shown how their infimum can be utilized for learning from streams of interpretations, and have motivated how their supremum can be used for an error-tolerant axiomatization of general concept inclusions from interpretations in the presence of a hand-crafted TBox that indicates errors in the observed interpretation.

Towards a sequent calculus for formal contexts

Ondrej Krídlo 1 and Manuel Ojeda-Aciego 2 1 University of Pavol Jozef Šafárik, Košice, Slovakia 2 Universidad de Málaga. Departamento de Matemática Aplicada. Spain

Introduction

In real life, one often faces situations in which the underlying knowledge is given as a set of tables which can be interpreted as formal contexts, and we should decide on whether certain contextual information is a consequence from them.

This problem clearly resembles the notion of a formula being a logical consequence of a set of hypotheses, and suggests the possibility or convenience of defining a formal (mathematical) notion of logical consequence between contexts.

The only attempts to introduce logical content within the machinery of Formal Concept Analysis (FCA), apart from its ancient roots anchored in the Port-Royal logic, are the so-called logical information systems and the logical concept analysis [2,9].

Of course, different links between FCA and logic have been studied but, to the best of our knowledge, the problem considered in this paper has not been explicitly studied in the literature. Nevertheless, it is worth to remark that the concluding section of [6] states that dual bonds could be given a proof-theoretical interpretation in terms of consequence relations.

In the present work, we consider the fact that the category ChuCors of contexts and Chu correspondences is *-autonomous, and hence a model of linear logic, in order to build some preliminary links with the conjunctive fragment of this logic.

Partially supported by grants VEGA 1/0073/15 and APVV-15-0091 Partially supported by Spanish Ministry of Science project TIN2015-70266-C2-1-P, co-funded by the European Regional Development Fund (ERDF)

Preliminaries

In order to make the manuscript self-contained, the fundamental notions and their main properties are recalled in this section. Given a formal context B, A, R , the derivation (or concept-forming) operators are a pair of mappings ↑ : 2 B → 2 A and ↓ : 2 A → 2 B such that if X ⊆ B, then ↑X is the set of all attributes which are related to every object in X and, similarly, if Y ⊆ A, then ↓Y is the set of all objects which are related to every attribute in Y .

Definition 2. A formal concept of a formal context C = B, A, R is a pair of sets X, Y ∈ 2 B × 2 A
which is a fixpoint of the pair of conceptforming operators, namely, ↑ X = Y and ↓ Y = X. The object part X is called the extent and the attribute part Y is called the intent. The set of all formal concepts of a context C will be denoted by CL(C), set of all extents or intents of C will be denoted by Ext(C) or Int(C) respectively.

Intercontextual structures

Two main constructions have been traditionally considered in order to relate two formal contexts: the bonds and the Chu correspondences.

Definition 3. Let C 1 = B 1 , A 1 , R 1 and C 2 = B 2 , A 2 , R 2 be two formal contexts. A bond between C 1 and C 2 is any relation β ∈ 2 B 1 ×A 2 such
that, when interpreted as a table, its columns are extents of C 1 and its rows are intents of C 2 . All bonds between such contexts will be denoted by

Bonds(C 1 , C 2 ).
Another equivalent definition of bond between C 1 and C 2 defines it as any relation

β ∈ 2 B 1 ×A 2 such that Ext( B 1 , A 2 , β ) ⊆ Ext(C 1 ) and Int( B 1 , A 2 , β ) ⊆ Int(C 2 )
Dual bonds between C 1 and C 2 are bonds between C 1 and transposition of C 2 . Transposition of any context

C = B, A, R is defined as a new context C * = A, B, R t with R t (a, b) holds iff R(b, a) holds.
The notion of Chu correspondence between contexts can be seen as an alternative inter-contextual structure which, instead, links intents of C 1 and extents of C 2 .

Definition 4. Consider C 1 = B 1 , A 1 , R 1 and C 2 = B 2 , A 2 , R 2 two formal contexts. A Chu correspondence between C 1 and C 2 is any pair ϕ = ϕ L , ϕ R of mappings ϕ L : B 1 → Ext(C 2 ) and ϕ R : A 2 → Int(C 1 ) such that for all (b 1 , a 2 ) ∈ B 1 × A 2 it holds that ↑ 2 ϕ L (b 1 ) (a 2 ) = ↓ 1 ϕ R (a 2 ) (b 1 ).
All Chu correspondences between such contexts will be denoted by

Chu(C 1 , C 2 ).
The notions of bond and Chu correspondence are interchangeable; specifically, we can consider the bond β ϕ associated to a Chu correspondence ϕ from

C 1 to C 2 defined for b 1 ∈ B 1 , a 2 ∈ A 2 as follows β ϕ (b 1 , a 2 ) = ↑ 2 ϕ L (b 1 ) (a 2 ) = ↓ 1 ϕ R (a 2 ) (b 1 )
Similarly, we can consider the Chu correspondence ϕ β associated to a bond ρ defined by the following pair of mappings:

ϕ βL (b 1 ) = ↓ 2 β(b 1 ) ϕ βR (a 2 ) = ↑ 1 β t (a 2 ) for all a 2 ∈ A 2 and o 1 ∈ B 1
The set of all bonds (resp. Chu correspondences) between two formal contexts endowed with the ordering given by set inclusion is a complete lattice. Moreover, both complete lattices are dually isomorphic.

Categorical products in ChuCors

Recall that it is possible to consider a category in which the objects are formal contexts and morphisms between two contexts are the Chu correspondences between them. This category, denoted ChuCors, has been proved to be *-autonomous and equivalent to the category of complete lattices and isotone Galois connections, more results on this category and its L-fuzzy extensions can be found in [4,3,5,7].

Cartesian product in ChuCors

The following definition provides a specific construction of the notion of (binary) cartesian product in the category ChuCors.

Definition 5. Consider C 1 = B 1 , A 1 , R 1 and C 2 = B 2 , A 2 , R 2 two formal contexts. The product of such contexts is a new formal context C 1 × C 2 = B 1 B 2 , A 1 A 2 , R 1×2 where the relation R 1×2 is given by ((i, b), (j, a)) ∈ R 1×2 if and only if (i = j) ⇒ (b, a) ∈ R i for any (b, a) ∈ B i × A j and (i, j) ∈ {1, 2} × {1, 2}.
If we recall the well-known categorical theorem which states that if a category has a terminal object and binary product, then it has all finite products, we need to prove just the existence of a terminal object (namely, the nullary product) in order to prove the category ChuCors to be Cartesian.

Any formal context of the form B, A, B × A where the incidence relation is the full Cartesian product of the sets of objects and attributes is (isomorphic to) the terminal object of ChuCors. Such a formal context has just one formal concept B, A ; hence, from any other formal context there is just one Chu correspondence to B, A, B × A .

The explicit construction of a general product (not necessarily either binary or nullary) is given below: Definition 6. Let {C i } i∈I be an indexed family of formal contexts

C i = B i , A i , R i , the product i∈I C i is the formal context given by i∈I C i = i∈I B i , i∈I A i , R ×I where (k, b), (m, a) ∈ R ×I ⇔ (k = m) ⇒ (b, a) ∈ R k .
It is worth to note that the arbitrary product of contexts commutes with both the concept lattice construction and the bonds between contexts. These two results are explicitly stated below.

Lemma 1. Let C i = B i , A i , R i be a formal context for i ∈ I. It holds that CL( i∈I C i ) is isomorphic to i∈I CL(C i ).
Lemma 2. Let I and J be two index sets, and consider the two sets of formal contexts {C i } i∈I and {D j } j∈J . The following isomorphism holds

Bonds i∈I C i , j∈J D j ∼ = (i,j)∈I×J Bonds(C i , D j ) .
Tensor product Another product-like construction can be given in the category ChuCors.

Note

that if ϕ ∈ Chu(C 1 , C 2 ), then we can consider ϕ * ∈ Chu(C * 2 , C * 1 ) defined by ϕ * L = ϕ R and ϕ * R = ϕ L . Definition 7. The tensor product C 1 C 2 of contexts C i = B i , A i , R i for i ∈ {1, 2} is defined as the context B 1 × B 2 , Chu(C 1 , C * 2 ), R where R (b 1 , b 2 ), ϕ = ↓ 2 ϕ L (b 1 ) (b 2 ).
The properties of the tensor product were shown in [7], together with the result that ChuCors with is symmetric and monoidal. Those results were later extended to the L-fuzzy case in [3]. In both papers, the structure of the formal concepts of a tensor product context was established as an ordered pair formed by a bond and a set of Chu correspondences.

Lemma 3. Let (β, X) be a formal concept of the tensor product C 1 C 2 , it holds that β = ψ∈X β ψ and X = {ψ ∈ Chu(C 1 , C * 2 ) | β ≤ β ψ }.
Due to the monoidal properties of on ChuCors we can add a notion of n-ary tensor product of n formal contexts n i=1 C i of any n formal contexts C i for i ∈ {1, . . . , n}. Hence, it is possible to consider a notion of n-ary bond that we can imagine as any extent of n-ary tensor product.

Definition 8. Let C i = B i , A i , R i be formal contexts for i ∈ {1, . . . , n}. A dual n-ary bond between {C i } n i=1 is an n-ary relation β ⊆ n i=1 B i such that for all i ∈ {1, 2, . . . , n} and any (b 1 , . . . , b i-1 , b i+1 , . . . , b n ) ∈ n j=1,j =i B i it holds that β(b 1 , . . . , b i-1 , (-), b i+1 , . . . , b n ) ∈ Ext(C i ) .
Lemma 4. Let {C 1 , . . . , C n } be a set of n formal contexts and β be some n-ary bond between such contexts. Let D β i be a new formal context defined as

B i , n j=1,j =i B j , R i where R i (b i , (b 1 , . . . , b i-1 , b i+1 , . . . , b n )) = β(b 1 , . . . , b n ) for any i ∈ {1, 2, . . . , n}. Then Ext(D β i ) ⊆ Ext(C i ).
3 Conjunctive linear logic in FCA

One of the main differences between linear and classical logic is the coexistence of two different conjunctions in linear logic, in both cases the underlying semantics is that two actions are possible, or can be executed, but the difference relies on how these actions are actually performed: on the one hand, we have the multiplicative conjunction ⊗ (times) which expresses that both actions will be performed; on the other hand, the additive conjunction & (with) states that, although both actions are possible, actually just one will be performed.

Additive conjunction

The categorical product × on ChuCors plays the role of additive conjunction &. Recall that the product C 1 ×C 2 is defined as

B 1 B 2 , A 1 A 2 , R 1×2 where R 1×2 (b, a) = (i = j) ⇒ (b, a) ∈ R i for all b ∈ B i and a ∈ A j for all i, j ∈ {1, 2}.
The semantics of the additive conjunction is that, in order to perform the action of C 1 × C 2 , we have first to choose which among the two possible actions we want to perform, and then to do the one selected. And this is exactly what happens here. From the previous section about the categorical product of ChuCors, it is known that a concept lattice of a product of formal contexts is equal to a product of concept lattices of the input formal contexts. Hence no interaction or parallel action of input formal contexts occurs in case of the categorical product.

Multiplicative conjunction and dual bonds

Any dual bond between two formal contexts C 1 and C 2 plays a role of multiplicative conjunction ⊗. From the definition of bonds one can see the parallelism of use of input contexts, where every value in the bond, as a relation, is from both extents of input contexts.

The existing isomorphism between Chu correspondences and bonds, and monoidal properties of Chu correspondences which follows from the fact that Chu correspondences form a category, bonds satisfies all properties of conjunction.

In the sense of category theory, any dual bond can be seen as a Galois connection between concept lattices of their input contexts, because of the categorical equivalence between category ChuCors and the category of complete lattices and isotone Galois connections.

In [1,8] one can find that the tensor product is used as multiplicative conjunction, due to its monoidal properties on category of Chu Spaces or on any monoidal category in general. Here, in FCA, the tensor product is a special formal context with nice properties that generates all bonds between the input formal contexts. Hence tensor product shows all possibilities how we can connect or use in parallel two formal contexts.

Sequent calculus

The idea here is to develop a logic between contexts and, specifically, a proof theory for this logic.

We will consider the problem of defining a consequence relation |= which allows for developing formally a sequent calculus between contexts. The relation just defined satisfies the properties of closure operator and, hence, can be considered as a relation of logical consequence between contexts, since any consequence relation can be viewed as a finitary closure operator on a set (of sentences or formulas).

Lemma 5. The relation |= above is a consequence relation.

Recall the notion of sequent of Gentzen calculus. Any sequent is of the form Γ ∆ and has the following meaning: from the conjunction of all hypothesis of Γ follows some formula of ∆. Hence as a conjunction of all contexts we use some n-ary bond between input contexts.

Without entering into the details, the following sequent rules from conjunctive linear logic can be proved in terms of this definition. Hence it is easy to use a full relation as the n-ary bond between C 1 , . . . , C n-1 , D to obtain the following rule.

C 1 , . . . , C n-1 , C n , |= C C 1 , . . . , C n-2 , (C n-1 ⊗ C n ) |= C ⊗-
C 1 , . . . , C n-1 , C n , |= C C 1 , . . . , C n-1 , C n × D |= C
×-right One of the possibilities here is to add to hypothesis a special context, product of two singletons × .

C 1 . . . , C n |= D 1 C 1 . . . , C n |= D 2 C 1 . . . , C n |= D 1 × D 2

Conclusion

We have obtained a preliminary notion of logical consequence relation between contexts which, together with the interpretation of the multiplicative (resp. additive) conjunction as the cartesian product (resp. bond) of contexts, enable to prove the correctness of the corresponding rules of the sequent calculus of the conjunctive fragment of linear logic.

Of course, we are just scratching the surface of the problem of providing a full calculus since we still need to find the adequate context-related constructions to interpret the rest of connectives. This is future work.

Morphisms Between Pattern Structures and Their Impact on Concept Lattices

Lars Lumpe 1 and Stefan E. Schmidt 2 Institut für Algebra, Technische Universität Dresden larslumpe@gmail.com 1 , midt1@msn.com 2 Abstract. We provide a general framework for pattern structures by investigating adjunctions between posets and their morphisms. Our special interest is the impact of pattern morphisms on the induced concept lattices. In particular we are interested in conditions which are sufficient for the induced residuated maps to be injective, surjective or bijective. One application is that every representation context of a pattern structure has a formal concept lattice that is induced by a certain pattern morphism.

Introduction

Pattern structures within the framework of formal concept analysis have been introduced in [3]. Since then they have turned out to be a useful tool for analysing various real-world applications (cf. [3][4][5][6][7]). Our paper extends the concept of representation contexts and interprets them via morphisms, closely related to o-projections as recently introduced and investigated in [2]. In [8], we disussed the meaning of projections of pattern structures, realizing the importance of residual projections. As a matter of fact, our generalization of representation contexts of pattern structures gives rise to residual projections.

Preliminaries

The fundamental order theoretic concepts of our paper are nicely presented in the book on Residuation Theory by T.S. Blythe and M.F. Janowitz (cf. [1]).

Definition 1 (Adjunction). Let P pP,¤q and L pL,¤q be posets; furthermore let f : P Ñ L and g : L Ñ P be maps.

(1) The pair pf,gq is an adjunction w.r.t. pP,Lq if f x ¤ y is equivalent to x ¤ gy for all x P and y L. In this case, we will refer to pP,L, f , gq as a poset adjunction.

(2) f is residuated from P to L if the preimage of a principal ideal in L under f is always a principal ideal in P, that is, for every y L there exists x P s. The following well-known facts are straightforward (cf. [1]).

Proposition 1. Let P pP,¤q and L pL,¤q be posets.

(1) A map f : P Ñ L is residuated from P to L iff there exists a map g : L Ñ P s.t. pf,gq is an adjunction w.r.t. pP,Lq. (2) A map g : L Ñ P is residual from L to P iff there exists a map f : P Ñ L s.t. pf,gq is an adjunction w.r.t. pP,Lq.

(3) If pf,gq and ph,kq are adjunctions w.r.t. pP,Lq with f h or g k then f h and g k.

(4) If f is a residuated map from P to L, then there exists a unique residual map f from L to P s.t. pf, f q is an adjunction w.r.t. pP, Lq. In this case, f is called the residual map of f .

(5) If g is a residual map from L to P, then there exists a unique residuated map g ¡ from P to L s.t. pg ¡ , gq is an adjunction w.r.t. pP, Lq. In this case, g ¡ is called the residuated map of g.

(6) A residuated map f from

P to L is surjective iff f ¥ f id L iff f is injective. (7) A residuated map f from P to L is injective iff f ¥ f id L iff f is surjective. Definition 2.
Let P pP,¤q be a poset and T P. Then (1) The restriction of P onto T is given by P|T : pT,¤ pT ¢Tqq, which clearly is a poset too.

(2) The canonical embedding of P|T into P is given by the map T Ñ P,t Þ Ñ t.

(3) T is a kernel system in P if the canonical embedding τ of P|T into P is residuated. In this case, the residual map ϕ of τ will also be called the residual map of T in P.

The composition κ : τ ¥ϕ is referred to as the kernel operator associated with T in P.

(4) Dually, T is a closure system in P if the cannonical embedding τ of P|T into P is residual. In this case, the residuated map ψ of τ will also be called the residuated map of T in P. The composition γ : τ ¥ψ is referred to as the closure operator associated with T in P.

(5) A map κ : P Ñ P is a kernel operator on P if s ¤ x is equivalent to s ¤ κx for all s κP and x P.

Remark: In this case, κP forms a kernel system in P, the kernel operator of which is κ.

(6) Dually, a map γ : P Ñ P is a closure operator on P if x ¤ t is equivalent to γx ¤ t for all x P and t γP.

Remark: In this case, ϕP forms a closure system in P, the closure operator of which is γ.

The following known facts will be needed for the sequel (cf. [1]) .

Proposition 2. Let P pP,¤q and L pL,¤q be posets.

(1) If f is a residuated map from P to L then f preserves all existing suprema in P, that is, if s P is the supremum (least upper bound) of X P in P then f s is the supremum of f X in L.

In case P and L are complete lattices, the reverse holds too: If a map f from P to L preserves all suprema, that is, f psup P Xq sup L f X f or all X P, then f is residuated. (2) If g is a residual map from L to P, then g preserves all existing infima in L, that is, if t L is the infimum (greatest lower bound) of Y L in L then gt is the infimum of gY in P. In case P and L are complete lattices, the reverse holds too: If a map g from L to P preserves all infima, that is, f pinf P Y q inf L gY f or all Y L, then g is residual.

(3) For an adjunction pf,gq w.r.t. pP,Lq the following hold: (a1) f is an isotone map from P to L.

(a2) f ¥g¥ f f (a3) f P is a kernel system in L with f ¥ g as associated kernel operator on L. In particular, L Ñ P, y Þ Ñ f gy is a residual map from L to L| f P.

(b1) g is an isotone map from L to P.

(b2) g ¥ f ¥g g (b3) gL is a closure system in P with g ¥ f as associated closure operator on P. In particular, P Ñ gL, x Þ Ñ g f x is a residuated map from P to P|gL.

3 Adjunctions and Their Concept Posets Definition 3. Let P : pP,S,σ,σ q and Q : pQ,T,τ,τ q be poset adjunctions. Then a pair pα,βq forms a morphism from P to Q if pP,Q,α,α q and pS,T,β,β q are poset adjunctions satisfying τ ¥α β ¥σ Remark: This implies α ¥τ σ ¥β , that is, the following diagrams are commutative:

P Q T S α β τ σ P Q T S α β τ σ
Next we illustrate the involved poset adjunctions:

P Q T S α α β β τ τ σ σ
Definition 4 (Concept Poset). For a poset adjunction P pP,S,σ,σ q let BP : tpp,sq P ¢S | σ p s σ s pu denote the set of pformalq concepts in P . Then the concept poset of P is given by BP : pP¢Sq | BP , that is, pp 0 , s 0 q ¤ pp 1 , s 1 q holds iff p 0 ¤ p 1 iff s 0 ¤ s 1 , for all pp 0 , s 0 q,pp 1 , s 1 q BP . If pp,sq is a formal concept in P then p is referred to as extent in P and s as intent in P .

From [9] we point out Theorem 1: Theorem 1. Let pα,βq be a morphism from a poset adjunction P pP,S,σ,σ q to a poset adjunction Q pQ,T,τ,τ q. Then pBP,BQ , Φ, Φ q is a poset adjunction for Φ : BP Ñ BQ , pp,sq Þ Ñ pτ β s, β sq and Φ : BQ Ñ BP , pq,tq Þ Ñ pα q, σ α qq.

P Q T S α β τ σ BP BQ Φ Theorem 2.
Under the conditions of the previous theorem the following hold:

(1) If α is surjective then Φ is surjective too.

(2) If β is injective then Φ is injective too.

(3) If α is surjective and β is injective then Φ is an isomorphism from BP to BQ .. Proof. (1) Assume that α is surjective, that is, α ¥α id Q . Then for all pp,sq BP , the second component of pΦ ¥Φ qpp,sq is β σ α q ταα q τq s. This yields Φ ¥Φ id BQ , that is, Φ is surjective. (2) The first component of pΦ ¥Φqpp,sq is α τ β s τ β β s τ s p. Therefore, Φ ¥Φ id BP , which yields Φ being injective.

(3) If α is surjective and β is injective, than Φ and Φ are naturally inverse by ( 1) and

(2), that is, Φ is an isomorphism from BP to BQ . 4 The Impact of Pattern Morphism on Concept Lattices Definition 5. A triple G pG,D,δq is a pattern setup if G is a set, D pD,q is a poset, and δ : G Ñ D is a map. In case every subset of δ G : tδg | g Gu has an infimum in D, we will refer to G as pattern structure. Then the set If G pG,D,δq and H pH,E,εq each is a pattern setup, then a pair pf,ϕq forms a pattern morphism from G to H if f : G Ñ H is a map and ϕ is a residual map from D to E satisfying ϕ ¥δ ε ¥ f , that is, the following diagram is commutative:

C G : tinf D δ X | X Gu
G H E D f ϕ ε δ
In the sequel we show how our previous considerations apply to pattern structures. Theorem 3. Let pf,ϕq be a pattern morphism from a pattern structure G pG,D,δq to a pattern structure H pH,E,εq.

To apply the previous theorem we give the following construction: f gives rise to an adjunction pα,α q between the power set lattices 2 G : p2 G , q and 2 H : p2 H , q via α :

2 G Ñ 2 H , X Þ Ñ f X and α : 2 H Ñ 2 G ,Y Þ Ñ f ¡1 Y.
Further let ϕ ¡ denote the residuated map of ϕ w.r.t. pE,Dq, that is, pE,D,ϕ ¡ , ϕq is a poset adjunction. Then, obviously, pD op , E op , ϕ, ϕ ¡ q is a poset adjunction too.

For pattern structures the following operators are essential:

: 2 G Ñ D, X Þ Ñ inf D δ X : D Ñ 2 G , d Þ Ñ tg G | d δ gu ¥ : 2 H Ñ E, Z Þ Ñ inf E εZ : E Ñ 2 H , e Þ Ñ th H | e εhu
It now follows that pα,ϕq forms a morphism from the poset adjunction

P p2 G , D op , , q
to the poset adjunction Q p2 H , E op , ¥ , q. In particular, pfXq ¥ ϕpX q holds for all X G. We receive the following diagram of adjunctions:

2 G 2 H E op D op α α ϕ ¡ ϕ l
For the following we recall that the concept lattice of G is given by BG : BP and the concept lattice of H is BH : BQ .

Then Theorem 1 yields that the quadruple pBG,BH , Φ, Φ q is an adjunction for

Φ : BG Ñ BH , pX,dq Þ Ñ ppϕdq , ϕdq and
Φ : BH Ñ BG, pZ,eq Þ Ñ pf ¡1 Z, pf ¡1 Zq q. 2 G 2 H E op D op α ϕ ¥ BG BH Φ
By Theorem 2 the following hold:

(1) If f is surjective then Φ is surjective too. (2) If ϕ is injective then Φ is injective too. (3) If f is surjective and ϕ is injective then Φ is an isomorphism from BG to BH .
Theorem 4. Let G pG,D,δq and H pH,E,εq be pattern structure. And let G pG,C G , δ q be the pattern structure induced by G via δ : G Ñ C G , g Þ Ñ δ g. It follows BG BG. Further let pf,ϕq be a pattern morphism from G to H . Then with the notation introduced in the previous theorem, the map Φ from BG to BH is residuated. If f is surjective then so is Φ, if ϕ is injective then so is Φ. If f is surjective and ϕ is injective then Φ is an isomorphism from BG to BH . Definition 6. The representation context of a pattern structure G pG,D,δq w.r.t. a subset M of D is given by KpG, Mq : pG,M,Iq with I : tpg,mq G ¢M | m δ gu.

Theorem 5. Let G pG,D,δq be a pattern structure and let M be a subset of D.

The pattern structure associated with the representation context KpG, Mq is given by

H : pG,2 M , εq with ε : G Ñ 2 M , g Þ Ñ Ó M δ g where Ó M d : tm M | m du for all d D.
In particular, the concept lattice of KpG, Mq is given by BKpG, Mq BH . Using the notation from the previous theorem, pid G , ϕq is a pattern morphism from G to H for ϕ :

C G Ñ 2 M , x Þ Ñ Ó M x. Furthermore, the map Φ from BG to BH BKpG, Mq is a residuated surjection. In case M is join-dense w.r.t. C G (that is, ϕ is injective), Φ is an isomorphism from BG to BKpG, Mq. 2 G 2 G 2 M C G id ϕ X X X X ¥ X X d Ó M d 2 G 2 G 2 M C G id ϕ ¥ BG
BKpG, Mq Φ Remark: Based on the paradigm of concept morphisms, the previous theorem extends and sheds new light on theorem 1 of [3]. We generalize the definition of representation context introduced in [3] by allowing an abitrary subset M of patterns of the underlying pattern structure G as attribute set of the representation context KpG, Mq. It then turns out that KpG, Mq has a formal concept lattice which is induced by a morphism on G . More explicitly, there is a morphism on G to the pattern structure of KpG, Mq which induces a residuated surjection from the concept lattice of G to the concept lattice of KpG, Mq. In case M is join-dense w.r.t. G , the morphism between the concept lattices is an isomorphism (see also Theorem 1 of [3]). Our extension of the concept of representation context gives rise to various constructions of o-projections (as introduced in [2]) on G .

Introduction

Nowadays, understanding big collections of data can have a great impact on advancing different scientific fields. Formal Concept Analysis (FCA) provides a powerful mathematical tool that addresses knowledge processing and knowledge representation [3]. The main advantage of FCA is the intuitive visualization and navigation methods offered by concept lattices. FCA was extended to the triadic case by Lehman and Wille in 1995 [6]. Since then, different theoretical aspects were studied and extended from the dyadic to the triadic case, and trilattices were proposed as a visualization method. However, this type of representation does not support an intuitive navigation method. Moreover, for slightly larger triadic data sets, the complexity of the representation makes any navigation attempt useless. Therefore, the problem of visualization and navigation in triadic conceptual spaces needs to be further analyzed and new approaches have to be found.

Previously, we have proposed two methods of navigating in triadic data. The first approach is based on narrowing down the space of formal concepts according to constraints added by the user. This membership-constraint-based approach was formally described and the theoretical aspects were studied in detail [7]. Moreover, the navigation paradigm was implemented, tested and evaluated [1,9]. This approach, however, generates lists of elements, hence the users cannot visualize the underlying structure of the triconcept set.

The second approach has a local character and is based on appropriately defined dyadic projections. For this purpose, we defined the reachability relation and studied some of its properties, as well as the properties of other resulting structures, such as reachability clusters [8]. In our previous paper, we analyzed the theoretical aspects of the described paradigm and shortly sketched a navigation strategy without going into details about the implementation methods. This paper aims to extend the navigation paradigm and to offer a comprehensive description of strategy behind. Moreover, we show how the structure of the reachability clusters can be used for supporting the local navigation paradigm.

Preliminaries

This section introduces the basic notions of triadic formal concept analysis as well as some of the theoretical aspects of the reachability-based navigation. For a deeper understanding of formal concept analysis we refer the reader to the standard literature [3,6], while a more detailed discussion on the properties of the reachability relation can be found in our previous paper [8].

The fundamental structures of triadic formal concept analysis are those of a triadic formal context and a triconcept. The following definition shows how dyadic projections can be obtained from a triadic context. Definition 3. Every triadic context (K 1 , K 2 , K 3 , Y ) gives rise to the following dyadic contexts: 2) ) with mY (2) (g, b) :⇔ (g, m, b) ∈ Y , and

Definition 1. A triadic formal context, also referred to as a tricontext, is a quadruple K = (K 1 , K 2 , K 3 , Y ) consisting of three sets K 1 , K 2 , K 3 and a ternary relation Y ⊆ K 1 × K 2 × K 3 . The elements of K 1 , K 2 , K 3 are called (formal) object,
K (1) := (K 1 , K 2 × K 3 , Y (1) ) with gY (1) (m, b) :⇔ (g, m, b) ∈ Y , K (2) := (K 2 , K 1 × K 3 , Y (
K (3) := (K 3 , K 1 × K 2 , Y (3) ) with bY (3) (g, m) :⇔ (g, m, b) ∈ Y .
For {i, j, k} = {1, 2, 3} and

A k ⊆ K k , we define K (ij) Ak := (K i , K j , Y (ij)
Ak ), where

(a i , a j ) ∈ Y (ij) Ak if and only if (a i , a j , a k ) ∈ Y for all a k ∈ A k .
Intuitively, the contexts K (i) represent "flattened" versions of the triadic context, obtained by putting the "slices" of (K 1 , K 2 , K 3 , Y ) side by side. Moreover,

K (ij)
Ak corresponds to the intersection of all those slices that correspond to elements of A k .

Next we introduce the notion of reachability relation and reachability cluster.

Definition 4. For (A 1 , A 2 , A 3 ) and (B 1 , B 2 , B 3 ) triadic concepts, we say that (B 1 , B 2 , B 3 ) is directly reachable from (A 1 , A 2 , A 3 ) using perspective (1) and we write

(A 1 , A 2 , A 3 ) ≺ 1 (B 1 , B 2 , B 3 ) if and only if (B 2 , B 3 ) ∈ B(K (23)
A1 ). Analogously, we can define direct reachability using perspectives (2) and (3).

We say that (B 1 , B 2 , B 3 ) is directly reachable from (A 1 , A 2 , A 3 ) if it is directly reachable using at least one of the three perspectives, that is, formally

(A 1 , A 2 , A 3 ) ≺ (B 1 , B 2 , B 3 ) :⇔ [(A 1 , A 2 , A 3 ) ≺ 1 (B 1 , B 2 , B 3 )] ∨ [(A 1 , A 2 , A 3 ) ≺ 2 (B 1 , B 2 , B 3 )] ∨ [(A 1 , A 2 , A 3 ) ≺ 3 (B 1 , B 2 , B 3 )].
Definition 5. We define the reachability relation between two triconcepts as being the transitive closure of the direct reachability relation ≺. We denote this relation by ▹.

For checking whether triconcept (B 1 , B 2 , B 3 ) is directly reachable from triconcept (A 1 , A 2 , A 3 ), we have proposed the following algorithm.

Algorithm 1: Procedure directlyReachable((A 1 , A 2 , A 3 ), (B 1 , B 2 , B 3 )) I f A 1 = B 1 or A 2 = B 2 or A 3 = B 3 then Return true I f A 1 ⊂ B 1 then P e = K (23) A1 I f (B 2 ) ′ Pe = B 3 and (B 3 ) ′ Pe = B 2 then Return true I f A 2 ⊂ B 2 then P i = K (13) A2 I f (B 1 ) ′ Pe = B 3 and (B 3 ) ′ Pe = B 1 then Return true I f A 3 ⊂ B 3 then P m = K (12) A3 I f (B 1 ) ′ Pe = B 2 and (B 2 ) ′ Pe = B 1 then Return true

Return f a l s e

The derivations used in the description of the algorithm are the simple dyadic derivations and the index was added just to highlight that each dyadic derivation corresponds to a different dyadic context. For example, (B 2 ) ′ Pe = B 3 uses the dyadic derivation operator of the context P e .

When studying the properties of the reachability relation, the notion of reachability cluster arises. Intuitively, a reachability cluster is a maximal set of mutually reachable triconcepts. Formally, a reachability cluster is defined as follows. Definition 6. The equivalence class of a triconcept (A 1 , A 2 , A 3 ) with respect to the preorder ▹ on T(K) will be called a reachability cluster and denoted by

[(A 1 , A 2 , A 3 )].
Next, we consider the dyadic context of reachable triconcepts K ▹ .

Definition 7.

Let K = (K 1 , K 2 , K 3 , Y ) be a triadic context. Then we denote with K ▹ = (T(K), T(K), ▹) the formal context of triconcepts with the reachability relation.

While analyzing the correlation between reachability clusters and the dyadic concepts (M, N ) ∈ B(K ▹ ) of the reachability context, we have shown that there is a one-to-one relation between the clusters and the non-empty intersections of the extent and intent from the dyadic concepts M ∩ N . These results give rise to a display method of all reachability clusters that can support the navigation among triconcepts, as detailed in the next sections.

Navigation Strategy

Considering the theoretical aspects highlighted in Section 2 and described in more detail in our previous paper ( [8]), we propose a strategy for navigating among triconcepts inside a reachability cluster as well as between clusters. In addition, as guidance during the navigation, we suggest the use of the cluster structure that shows an overview of the reachable triconcepts. Intuitively, a step of the navigation paradigm consists of moving from one triconcept to another directly reachable triconcept. Hence, by following a navigation path of several steps one can explore the triadic conceptual knowledge landscape.

One problem that has not been solved yet in an efficient manner is how to choose a starting point. Currently, for this purpose, we use a preprocessing step that computes all triconcepts, for example using Trias [4]. Once we have the triconcept set, one can choose a triconcept as a starting point and navigate by choosing one perspective, i.e. one of the three dimensions. However, we highlight the fact that this preprocessing step is not necessary for the rest of the navigation and, if a starting point is chosen using a different method, this time consuming step can be eliminated. The local navigation paradigm is described by the following steps:

-choose a triconcept T = (A 1 , A 2 , A 3 ) and a perspective (i) with i ∈ {1, 2, 3} -compute the derived context K (jk)
Ai of the triadic relation with j, k ∈ {1, 2, 3}\ {i} s.t. j < k -generate the concept lattice of K (jk) Ai -attach as labels to the dyadic concepts in the lattice the corresponding triconcepts by adding the third component -choose one of the triconcepts that are represented by the nodes in the dyadic lattice as a next step

For computing the derived context K (jk)

Ai , one must select from the triadic relation the pairs of elements (a j , a k ) ∈ A j × A k which are in relation with all elements from A i , i.e. (a i , a j , a k ) ∈ Y, ∀a i ∈ A i , assuming, without loss of generality, that i < j < k. Afterwards, the third step consists of generating the concept lattice of the derived context. This can be done using one of the existing FCA tools [2]. In the next step, for a dyadic concept (B j , B k ) of the derived context K (jk) Ai we must identify the corresponding triconcept (B i , B j , B k ) ∈ T(K). Theoretically, this can be done by using the corresponding derivation operator to compute the third component of a triconcept. However, considering that we have already computed all triconcepts, it is more efficient to select the triconcept having the two components B j and B k (which will be unique given the maximality condition) from the triconcept set.

The previously described navigation and visualization paradigm has a local character which is an advantage when considering large contexts. However, one disadvantage of the navigation is that not every triconcept can be reached from every other triconcept, although this seems to be the case in most practical scenarios [8]. Therefore, we believe that it is useful to have an overall view of the navigation clusters' structure in order to understand whereto one can navigate. With that purpose, we obtain the lattice structure of the reachability context K ▹ = (T(K), T(K), ▹) as follows:

-compute the direct reachability relation between triconcepts -compute the transitive closure of the direct reachability relation -represent the concept lattice of clusters For implementing the first step, we can use Algorithm 1 that outputs whether a triconcept is directly reachable from another triconcept. For the second step, the transitive closure of the direct reachability relation ≺ must be computed in order to obtain the reachability relation ▹. This can be done by using one of the existing algorithms that compute the transitive closure of a relation, such as Warshall algorithm ( [11]), Warren algorithm ( [10]), etc.

After obtaining that, the reachability context K ▹ can be formed and we can compute the clusters and the partial order on the cluster set, using the concept lattice of K ▹ . We have shown that each reachability cluster is uniquely identified by the intersection of extent and intent of exactly one dyadic concept of K ▹ . Hence, we can compute the concept lattice of K ▹ and label each node with the intersection of extent and intent, i.e. the corresponding cluster, and no label when the intersection is empty. In the obtained lattice one can visualize the partial order between the clusters. An example illustrating the described procedure for obtaining the cluster structure is presented in Section 4.

Alternatively, we can make use of the directed graph having the triconcepts as vertices and the edges given by the direct reachability relation. Here, we can identify the reachability clusters, as well as deduce the transitive closure of the direct reachability relation as described in Proposition 1. Proposition 1. Let K be a tricontext and G the graph with T(K) as vertices and the edges given by the direct reachability relation. Then, the reachability clusters of K are identified by the strongly connected components of G. Furthermore, for triconcepts T 1 , T 2 ∈ T(K), we have that T 1 ▹ T 2 if, in graph G, there is a directed path from T 1 to T 2 .

Furthermore, the same graph G can be used to deduce the partial order relation between the clusters as described in Proposition 2. Proposition 2. Let K be a tricontext and G the graph with T(K) as vertices and the edges given by the direct reachability relation. If T 1 ∈ C 1 and T 2 ∈ C 2 are two triconcepts from different clusters s.t. in G there is a path from T 1 to T 2 , then we have that C 1 ≤ C 2 . Observe that, considering T 1 and T 2 belong to different clusters, in the case that there is a path from T 1 to T 2 , we cannot have a path from T 2 to T 1 .

However, a disadvantage of the graph-based approach is that it does not output the lattice representation of the clusters, hence an FCA tool has to be used if we want to obtain a visualization of the cluster structure.

An important aspect to keep in mind during the navigation is that not every triconcept is reachable from any other triconcept. In fact, when navigating from a triconcept to another belonging to a different cluster, one cannot navigate back by using the standard navigation method described. For this purpose, we propose the use of a navigation history, allowing the user to go back to a certain triconcept in the previous navigation path.

In conclusion, to support exploration through the dataset, we suggest using both the local visualization method for triconcepts and the visualization of the cluster structure as follows. We compute the lattice showing the cluster structure at the beginning of the navigation and make it available to the user throughout the whole exploration process. Then, at each step of the navigation, when visualizing the concept lattice of the possible next steps, i.e. the directly reachable triconcepts, we highlight all the triconcepts belonging to the same cluster as the current triconcept. In that way, the user can easily choose to navigate within the same cluster or to a different one. Furthermore, looking at the cluster structure in parallel, the user can navigate more easily towards a potential goal of the navigation.

Example

In practice, experiments that we ran on real datasets showed that tricontexts had one single reachability cluster comprising all triconcepts. This leads us to believe, that, in general, real datasets have a high correlation in the data and therefore, all triconcepts are contained in the same reachability cluster. However, theoretically it is possible that a tricontext comprises several reachability cluster. In this section, we present a small example of an artificial context containing more than two reachability clusters and exemplify how the structure of the reachability clusters can be obtained.

Let us consider the following triadic context

K = (G, M, B, Y ), with the ob- ject set G = {g 1 , g 2 , g 3 }, the attribute set M = {m 1 , m 2 , m 3 } and the condition set B = {b 1 , b 2 , b 3 }. b1 m1 m2 m3 g1 × g2 g3 b2 m1 m2 m3 g1 g2 g3 × b3 m1 m2 m3 g1 × × g2 g3
The triconcepts of this context are the following:

T 1 = ({g 3 }, {m 2 }, {b 2 }) T 2 = ({g 1 }, {m 1 }, {b 1 .b 3 }) T 3 = ({g 1 }, {m 1 .m 2 }, {b 3 }) T 4 = ({g 1 , g 2 , g 3 }, {m 1 , m 2 , m 3 }, ∅) T 5 = ({g 1 , g 2 , g 3 }, ∅, {b 1 , b 2 , b 3 }) T 6 = (∅, {m 1 , m 2 , m 3 }, {b 1 , b 2 , b 3 })
The triconcepts are partitioned in clusters the following way:

C 1 = {({g 3 }, {m 2 }, {b 2 })} C 2 = {({g 1 }, {m 1 }, {b 1 .b 3 }), ({g 1 }, {m 1 .m 2 }, {b 3 })} C 3 = {({g 1 , g 2 , g 3 }, {m 1 , m 2 , m 3 }, ∅), ({g 1 , g 2 , g 3 }, ∅, {b 1 , b 2 , b 3 }), (∅, {m 1 , m 2 , m 3 }, {b 1 , b 2 , b 3
})} Then, we obtain the dyadic context of reachability K ▹ as depicted in Figure 1. Moreover, when computing the concept lattice of K ▹ , we obtain a representation of the reachability clusters as depicted in Figure 2. In this lattice, the bottom node corresponds to cluster C 1 , the node in the middle corresponds to cluster C 2 and the upper node corresponds to cluster C 3 . The partial order between the clusters can be read from the lattice the following way: if one can navigate from cluster C 1 to cluster C 2 going upwards, then

K ▹ T 1 T 2 T 3 T 4 T 5 T 6 T 1 × × × × × × T 2 × × × × × T 3 × × × × × T 4 × × × T 5 × × × T 6 × × ×
C 1 ≤ C 2 , so we have that C 1 ≤ C 2 ≤ C 3 .
During the navigation, taking this cluster structure into consideration, one can deduce, for example, that starting from triconcept T 4 you can never reach any of the triconcepts T 1 , T 2 or T 3 . Hence, the structure of the clusters can be of use also when choosing a starting point for the navigation.

Conclusions and Future Work

In this paper, we have extended a navigation paradigm for triadic datasets that helps the user to get an overview of the data and to understand its underlying structure. To this end we described the steps of the navigation among triconcepts based on local dyadic projections and we have shown how the structure of the reachability clusters can be obtained using different methods. Furthermore, we have highlighted the fact that the local navigation paradigm can benefit from the lattice representation of the clusters' structure by offering the user an overview of the underlying data structure. The described navigation paradigm was implemented in a tool suite called FCA Tools Bundle that is described in more detail in an additional paper [5].

In our future work, we plan to combine the reachability-based navigation with the membership-constraint-based navigation into a new improved paradigm in order to solve the problem of choosing a starting point. The reachability-based navigation can offer the visualization support, while the constraints added by the user can be taken into consideration by highlighting the concepts in the local visualization that satisfy the constraints.

FCA Tools Bundle -a Tool that Enables Dyadic and Triadic Conceptual Navigation

Levente Lorand Kis, Christian Sȃcȃrea, and Diana Troancȃ

Babeş-Bolyai University Cluj-Napoca kis lori@yahoo.com, csacarea@cs.ubbcluj.ro, dianat@cs.ubbcluj.ro Abstract. Formal Concept Analysis is a prominent field of applied mathematics handling collections of knowledge -formal concepts -which are derived from some basic data types, called formal contexts by using concept forming operators. One of the strengths of FCA is the elegant, intuitive and powerful graphical representation of landscapes of knowledge as concept lattices. Nevertheless, in case of triadic FCA (3FCA) for more than 20 years there was no automatic tool for graphical representation of triconcept sets. Moreover, the triangular representation of trilattices, used so far in 3FCA has several disadvantages. Besides the lack of clarity in representation, one major disadvantage is that not every trilattice has a triangular diagram representation. In this paper we focus on the problem of locally navigating in triconcept sets and propose a tool which implements this navigation paradigm. To the best of our knowledge this is the first tool which makes navigation in larger triconcepts sets possible, by flipping through a certain collection of concept lattices.

Introduction

The FCA community agrees upon the necessity of having powerful software tools for formal context handling and lattice representation, as well as for other FCA features which are close to the heart of everyone from this community. Moreover, these tools need to be also accessible also to users outside the FCA community and there is plenty of work which has been done in this area. Without being comprehensive, an overview of FCA software was compiled by Priss and can be found on her webpage1 . We will not cite any of these tools, since citing all of them would expand the Bibliography section out of the scope of a workshop paper, and making a citation selection would mean to emphasize some tools and to disregard some others, which again is not the scope of this paper.

Nevertheless, we need to point out that all tools are handling the 'classical' dyadic case or some extensions like patterns structures or relational FCA, while the triadic case is neglected. We do not know any tool able to draw a trilattice diagram or to represent somehow triconcept sets. In our opinion, triadic FCA (3FCA) has a real potential for real life applications once the problem of knowledge representation has been solved in a satisfactory manner. Based on some previous attempts of representing triconcept sets as graphs [9] or using a circular visualization tool [3], we focused on a local navigation paradigm for triconcept sets [8]. This paradigm is meant for exploring triconcept sets by choosing one triconcept (A 1 , A 2 , A 3 ) and locking one of its components (either the extent, or the intent, or the modus) and then using the dyadic projection K ij Ak of related reachable concepts. Brief details on this paradigm are included in Section 2.

In this paper, we present the current state of FCA Tools Bundle, a collection of tools for dyadic and triadic Formal Concept Analysis. The triadic part consists of the implementation of the above-mentioned local navigation paradigm, while the dyadic part contains lattice building and visualization tools. In Section 2 we briefly introduce some preliminaries regarding triadic contexts and the suggested navigation paradigm, while in Section 3 we motivate the implementation of the tool suite. Section 4 describes the features implemented by the tool, while Section 5 presents an example of navigating through a triadic dataset. In Section 6 we describe the architecture of the tool and the technologies as well as the external tools used in the implementation. Finally, Section 7 describes some of the future directions for the development of the tool.

Preliminaries

We focus in this section only on the local navigation paradigm, as it has been introduced in our previous paper [8]. For more, we refer to the standard literature [4,7].

Let K = (K 1 , K 2 , K 3 , Y ) be a tricontext.
There are two types of dyadic projections which can be obtained from K. First, we can 'flatten' K by slicing it and putting all slices side by side:

K (i) := (K i , K j ×K k , Y (i) ), with (a i , (a j , a k )) ∈ Y (i) if and only if (a i , a j , a k ) ∈ Y , where a i ∈ K i , a j ∈ K j , a k ∈ K k and {i, j, k} = {1, 2, 3} are pairwise different.
Another projection is given by 'locking' a subset A k ⊆ K k and intersecting all those slices that correspond to elements of A k . More specifically, for {i, j, k} = {1, 2, 3} and

A k ⊆ K k , we define K (ij) Ak := (K i , K j , Y (ij) Ak ), where (a i , a j ) ∈ Y (ij) Ak if and only if (a i , a j , a k ) ∈ Y for all a k ∈ A k .
In our previous paper, we have studied some theoretical issues regarding triconcepts and these dyadic projections [8] . If (A 1 , A 2 , A 3 ) is a triconcept, then the dimensions i ∈ {1, 2, 3} are called i-perspectives. Performing a dyadic projection after one of these three perspectives, one can observe that there is a one-to-one correspondence between the corresponding dyadic concepts and some triconcepts of the original tricontext K. These triconcepts are called directly reachable using perspective i. The reachability relation is defined as the transitive closure of the direct reachability relation. This enables local navigation in triconcept sets, by iteratively choosing a perspective, then browsing the direct reachable triconcepts set by exploring the subsequent projected dyadic concept lattice and so on. This perspective-locking-and-unlocking procedure gives rise to interesting theoretical questions, partly solved in our previous paper [8]. Of course, the local character of the navigation comes with the cost of loosing overview. Nevertheless, navigating along the reachability relation is synonym to flipping through several concept lattices and investigate connections of triconcept sets which are not visible from the 'classical' trilattice diagram representation. Section 4 describes the practical implementation of this local navigation paradigm in FCA Tools Bundle.

Motivation

The main motivation of developing this tool comes from practical applications of FCA. Some data have an inherent triadic structure, folksonomies being one of the prominent examples, and for these data one can generate either a complete list of triconcepts or one can restrict only to the most frequent [6]. But even data without inherent triadic structure might be investigated from a triadic point of view, which increases the popularity of 3FCA and makes it suitable for more applications. These data can usually be interpreted as many-valued contexts which are then scaled using the ToscanaJ Suite [2]. Using a locally developed plugin called Toscana2Trias, one can build a triadic view on the data directly from ToscanaJ. Triconcepts can be easily computed but without a visualization tool there is no navigation support and hence the applicability of 3FCA remains uncertain.

Making FCA more popular outside of its natural community is another goal which motivates this development. The paradigm introduced in our previous paper seems to be a good starting point, since it enables navigation in triconcept sets by using the natural elegance and expressiveness of concept lattices [8].

Once the paradigm has been set up, several problems had to be overcome. For instance, the well-known node overlapping, which requires manual rearrangement of nodes. For this purpose, we implement a concept lattice generation method that integrates a collision detection functionality. This feature will enable to automatically check when nodes in the diagram are overlapping and rearrange the diagram in such a way that there are no more overlappings, i.e. collisions among the nodes.

Usability and accessibility is another goal of this tool development. Hence it has been developed as an open source project. Furthermore, it is made public as a web site which requires registration, but no other installation process which makes it easy to use.

Last but not least, revival of software development for FCA is in our opinion, a major objective for our community, to which we strongly adhere.

FCA Tools Bundle -Description and Features

The FCA Tools Bundle 2 currently implements features for dyadic and triadic formal concept analysis. The main purpose of the tool is to enable the user to visualize formal contexts of different dimensions in several formats (concept list, concept lattice) and to interact with them.

The tool offers some public contexts for users who want to test the functionalities (see Figure 1) and, in addition, there is an import functionality that allows users to add other dyadic or triadic contexts. The allowed formats for importing a formal context are cxt and csv. The cxt format is the standard format for dyadic contexts, while for triadic context it is a straightforward extension of the format. When using the second format, the csv file must contain only the tuples of the relation from which the context can be reconstructed. The key features offered by FCA Tools Bundle for a dyadic context are to visualize the details of the context, i.e. object set, attribute set, incidences and concept set and to compute and visualize the concept lattice of the context represented in Figure 2.

As mentioned previously, another useful feature offered by the tool is the possibility to avoid overlappings in the concept lattice using a collision detection functionality. After computing the concept lattice, the y coordinate of the nodes is locked, but they are allowed to move freely in their respective layer. Therefore, the user can move the nodes on the x-axis and rearrange them as they find suitable.

Fig. 3: Triconcepts of the hostels context

For a triadic context, one can first visualize the concept list. Figure 3 shows a list of triconcepts from the hostel example given by Glodeanu [5]. In addition, an important functionality, which was not implemented by any previous tool, is a local visualization of parts of the triadic context which enables the navigation paradigm in the triconcept set. One can choose a set of elements (of the same type, i.e. objects, attributes, or conditions) to project on and visualize the concept lattice of the dyadic projection. This functionality can be used for the navigation paradigm based on dyadic projections ( [8]) and a proof of concept will be presented in Section 5.

Example

In a previous paper we defined a local navigation paradigm for triadic contexts based on appropriately defined dyadic projections. In this section we show how FCA Tools Bundle can be used to navigate in a triadic context using this paradigm. For this purpose we consider the hostels context, which was previously defined by Glodeanu [5]. Figure 4

depicts the layered cross-table representation of the hostel context.

As mentioned previously, some of the triconcepts of the hostel context are represented in Figure 3. We choose the triconcept T 1 = ({One, OleB ., GardenB .}, {location, staff , character , safety, cleanliness}, {hostels, hostelbookers}) as a starting point and lock the third perspective, i.e. the set of conditions {hostels, hostelbookers}. The corresponding dyadic projection is depicted in Fig- Here, the triconcept T 1 corresponds to the right-most dyadic concept. Herefrom, one can choose a different triconcept, for example the left-most concept T 2 = ({One, OleB ., OasisB .}, {fun, cleanliness, safety, staff , location} {hostels, hostelbookers}), and project on the object set. The corresponding concept lattice, after this second lock step, is depicted in Figure 6.

× Samay × × × × Oasis B. × × × × × One × × × × Ole B. × × × × Garden B. × × × hostels character safety location staff fun cleanliness Nuevo S. × × Samay × × × × Oasis B. × × × × × × One × × × × × × Ole B. × × × × × × Garden B. × × × × × × hostel- bookers character safety location staff fun cleanliness Nuevo S. × × Samay × × × × × Oasis B. × × × × × One × × × × × × Ole B. × × × × × × Garden B. × × × × ×
6 Architecture of FCA Tools Bundle FCA Tools Bundle is a platform that intends to implement FCA features for the dyadic and triadic case. It has a log-in system which can offer a personalized experience to the user. Therefore, a formal context can be public, i.e. visible to every other user, or private, i.e. visible only to the user who defined it.

There are multiple technologies used in implementing FCA Tools Bundle as well as some external FCA tools that are integrated for using some of the previously implemented FCA algorithms. For computing dyadic concepts a slightly modified version of InClose2 ( [1]) is used. In the triadic case, the Trias algorithm is used for computing the triconcepts [6].

Considering that one of our motivations was to improve visualization methods for concept sets, special attention was given to the concept lattice representation. For this purpose, we used a force-directed approach that tries to position the nodes at somewhat equal distance and with as few intersections among the edges as possible. First, a layer is assigned to each node, which determines its final position on the y-axis of the lattice diagram, i.e. it cannot be changed by dragging the node up or down. For this purpose, we use a concept lattice drawer algorithm proposed by Roland Puntaier3 . Afterwards the forces rearrange the nodes in the concept lattice as follows. Each node has a repulsion force that pushes other nodes away, while simultaneously each line between the nodes acts as a springlike force and attracts pairs of nodes towards each other. This approach seems to produce one of the best outputs for the concept lattice, however, it can still be the case that there are overlappings of nodes. For that reason, we implement a custom collision detection algorithm adapted to the x-axis of the lattice representation, since rearranging the nodes on this axis will be sufficient for avoiding overlappings of the nodes. This algorithm follows the ideas described by Mike Bostock4 and uses the quadtree structure implemented in the D3JS library.

Conclusions and Future Work

In this paper, we presented FCA Tools Bundle, a platform that offers, for now, features of visualization and navigation for dyadic and triadic FCA. We have improved concept lattices generation using a detection collision algorithm, in order to avoid manually arranging the concept lattice for concept visibility. Moreover, we have shown how concept lattices can be used for a triadic navigation paradigm based on appropriately defined dyadic projections.

The development of the tool is ongoing and there are multiple functionalities that we plan to implement in the future, some of which are shortly described in this section. We intend to implement exploration procedures for dyadic as well as triadic FCA, based on implication computation. Moreover, temporal FCA is another branch that lacks user-friendly tools, hence implementing lifetracks and temporal views is another work which needs to be done [10]. Another important case that we plan to consider, since so far it was only implemented in the ToscanaJ Suite, are many-valued contexts. Furthermore, we will relate FCA to pattern structures and implement corresponding algorithms.

In conclusion, we believe that the presented version of FCA Tools Bundle brings an important contribution to the collection of FCA tools, by implementing functionalities of visualization and navigation in triadic concept sets, which, to the best of our knowledge, are not present in any other tool.

Steps Towards Interactive Formal Concept

Analysis with LatViz Mehwish Alam1 , Thi Nhu Nguyen Le 2 , and Amedeo Napoli 2

1. Laboratoire d'Informatique de Paris-Nord, Université Paris 13, Paris, France 2. LORIA (CNRS -Inria Nancy Grand Est -Université de Lorraine) BP 239, Vandoeuvre-lès-Nancy, F-54506, France {alam@lipn.univ-paris13.fr}{thi-nhu-nguyen.le,amedeo.napoli@loria.fr} Abstract. With the increase in Web of Data (WOD) many new challenges regarding exploration, interaction, analysis and discovery have surfaced. One of the basic building blocks of data analysis is classification. Many studies have been conducted concerning Formal Concept Analysis (FCA) and its variants over WOD. But one fundamental question is, after these concept lattices are obtained on top of WOD, how the user can interactively explore and analyze this data through concept lattices. To achieve this goal, we introduce a new tool called LatViz, which implements several algorithms for constructing concept lattices and allows further navigation over lattice structure. LatViz proposes some remarkable improvements over existing tools and introduces various new functionalities such as interaction with expert, visualization of Pattern Structures, AOC posets, concept annotations, filtering concept lattice based on several criteria and finally, an intuitive visualization of implications. This way the user can effectively perform an interactive exploration over a concept lattice which is a basis for a strong user interaction with WOD for data analysis.

Introduction

In the last decade, there has been a huge shift from the Web of Documents to the Web of Data (WOD). Web of Documents represents data in the form of HTML pages which are linked with other HTML pages through hyperlinks. This web of documents has evolved into WOD where all the information contained is represented in the form of entities and relations allowing the semantics to be embedded in the representation of these data. These data are in the form of a (node-arc) labeled graph belonging to several domains such as newspapers, publications, biomedical data etc. The growth in the publication of data sources in WOD has made it an important source of data, which has led towards many challenges pertaining to effective utilization of this data. WOD mainly represents data in the form of Resource Description Framework (RDF) 1 . There are several ways such as data dumps and SPARQL queries to access these data, which can be utilized for several applications, one of which is visualization and interactive exploration for data analysis purposes. Several visualization tools have been developed for this purpose, one of which is LODLive2 [6], where the user can choose data-sets such as DBpedia and Freebase and specify an entity as a starting point for browsing the node-arc labeled graph. Another tool based on graphical display is RelFinder [15], where given several entities the tool automatically finds the paths connecting these entities. The major drawback of LODLive is that after two hops the number of nodes increase and it is hard to visualize the data. Moreover, these tools are good for getting an insight into what RDF graph contains but they are not built for the purpose of knowledge discovery.

In order to provide the user with the ability to perform data analysis and knowledge discovery over such kind of data, there is a need to perform classification, where the obtained classes are further made available to the user for exploration and subjective interpretation. In the current study we use Formal Concept Analysis as the basis for classification. Several studies have already been conducted using FCA and its variants over RDF graphs or its generalization to knowledge graphs. Out of these studies so far RV-Xplorer [3] is the only tool that actually allows interactive exploration of clustered RDF data [2]. The purpose of this paper is to enhance the functionalities discussed in the previous studies. In this study we introduce a new tool LatViz which increases the interpretability of a concept lattice by remarkably improving the user interaction with the concept lattice as compared to existing tools. Various new functionalities have been introduced such as the visualization of Pattern Structures and AOC-posets, concept annotation, filtering concept lattice and pattern concept lattice based on several criteria and finally, an intuitive visualization of implications. This way the user can effectively perform an interactive exploration over a concept lattice which in turn gives a basis for a strong user interaction with WOD for knowledge discovery purposes. In this paper, we detail the important interaction operations implemented in LatViz. In the rest of this paper we refer to "user" as an "expert" as (s)he having basic knowledge about the lattice structure.

The paper is structured as follows: Section 2 introduces a motivating example. Section 3 introduces some of the important functionalities of LatViz, while in Section 4, we discuss some of the related tools already developed and finally Section 5 details the future perspectives of the current work.

Motivating Example

Let us consider that an expert is searching for papers published by a particular team in conferences or journals related to his/her field of research. In order to locate the papers of his/her interest (s)he has to search for specific keywords or authors in the local portal. For getting the view of which kind of papers are contained (s)he has to run a broad query and then narrow down his/her query to obtain papers on specific keywords or authors or group of keywords or authors. The expert will end up running several queries to get what (s)he wants. Moreover, if the expert wants to know the collaborations of the team with other members of the research community outside the team, as well as the diversity and the specialization of the team members, this cannot be directly obtained by simple querying. To obtain such kind of knowledge there is a need to introduce a support for data analysis. Based on this scenario, we show how the expert can be guided thanks to an adapted visualization tool to obtain such information of interest with the help of concept lattices.

3 LatViz for Interactive Exploration of Concept Lattices

User Interface

The display of LatViz resembles Conexp3 , which provides basic functionalities for building a concept lattice. LatViz implements two algorithms for building a concept lattice from a binary context, one of which is introduced in [14]. Another, efficient algorithm for building a concept lattice is AddIntent [20]. A demo of LatViz is available on-line through http://latviz.loria.fr/latviz/.

The concept lattice for the scenario in section 2 was created by mapping the RDF data to a formal context K " pG, M, Iq. The subjects of the triples were considered as the set of objects G, the objects in the RDF triples i.e., keywords and authors were considered as the set of attributes M . In this example, the RDF triples were created from the publications of the Knowledge Discovery (KDD) team in LORIA. The number of objects in the context are 343 and attributes are 1516. Very often huge concept lattices are obtained based on the context size. LatViz provides several interactive operations allowing for reduction of exploration space of the expert. To-date this is the most interactive tool having many unique functionalities such as handling numeric data with the help of interval pattern structures, AOC-posets, filtering concept lattice and implications which provides support for data analysis. Other functionalities such as annotating the lattice, level-wise display of a concept lattice etc. are discussed in many contexts but are not yet directly implemented in the commonly used tools. In the following we detail each of these functionalities for data analysis.

AOC-Posets

AOC-poset is a partially ordered set of the attribute and object concepts, first introduced in [18,19]. The object and attribute concept are referred to as introducers in [5]. Once an attribute is introduced in a concept it is inherited from top to bottom while, dually, an introduced object is "inherited" from bottom to top. During this study, we implement the Hermes Algorithm introduced in [5] for building AOC-Poset from binary context. Figure 1 show the highlighted AOC-Posets of the concept lattice built for the running scenario.

Displaying Concept Lattice Level-wise

AOC-Posets actually reduce exploration space but still a huge number of concepts remain to be observed. LatViz allows the creation of concept lattice levelwise by interaction. When an expert clicks on the top concept, LatViz computes and displays the first level. After that the expert can select the concept for continuing the exploration, then LatViz computes the next level for that concept. In Figure 2, the top image shows the first level of the concept lattice built by selecting the top concept. Then the expert can view the contents of each concept on mouseover. In the running example, expert locates the concept with all the papers of Amedeo Napoli (i.e., K#2), which shows that the total number of documents written by Amedeo Napoli are 152. On selecting this concept, the next level of the lattice originating from the selected concept is computed (shown in the bottom image in Figure 2).

Display Sub/Super-Concepts of a Concept

In case of huge concept lattices sometimes it is hard to keep track of the ordering relations between the concepts. LatViz allows the expert to only highlight sub/super-concepts of a concept. For example, if the expert wants to display all the publications along with the collaborations of the author Amedeo Napoli, (s)he can highlight the associated sub-lattice of the attribute concept of "Amedeo Napoli". Figure 3 shows the highlighted sub-lattice in brown. An expert can highlight the super-concepts connected to a concept. If the expert is looking for all the papers having some keywords common with the paper Knowledge Organization and Information Retrieval Using Galois Lattices having one or more of the keywords in the intent of the concept then (s)he can highlight the sub-lattice of super-concepts associated to it (see Figure 4).

Display/Hide the Sub-lattice

This functionality was partially implemented in RV-Xplorer [3] to reduce the interaction space of the expert. Here the expert can only show the part of the concept lattice in which (s)he is interested. The expert can locate the interesting concept by navigation, containing some intent or extent. If an intent is interesting and the expert marks the concept as interesting then only the sub-concepts of this concept are shown to the expert as the intents are inherited from top to bottom. Dually, if an extent is interesting for the expert then all the super-concepts are shown to the expert as the extent is inherited bottom-top. Previously, the expert highlighted the sub-lattice of the concept containing all the papers of Amedeo Napoli, now if the expert is interested in only the papers of Amedeo Napoli on Knowledge Representation then (s)he can navigate downwards and only see this part of concept lattice by marking it interesting (see Figure 5). Similarly, we previously highlighted all the super-concepts of the concept having the paper entitled Knowledge Organization and Information Retrieval Using Galois Lattices in the extent, Figure 6 only shows the associated sub-lattice to have a clearer view (see Figure 6).

Interval Pattern Structures

Interval Pattern Structures were first introduced in [16] for dealing with numerical data. Consider two descriptions δpg 1 q " xrl 1 i , r 1 i sy and δpg 2 q " xrl 2 i , r 2 i sy, with i P r1..ns where n is the number of intervals used for the description of entities. The similarity operation [ and the associated subsumption relation Ď between descriptions are defined as the convex hull of two descriptions as follows: δpg 1 q [ δpg 2 q " xrminpl 1 i , l 2 i q, maxpr 1 i , r 2 i qsy. Based on this similarity measure interval pattern concept lattice can be built. In the running scenario, three numerical attributes for the papers were used i.e., year of publications, rank of the conference and the number of pages. The ranks of the conferences were con-sidered based on COmputing Research and Education (CORE) rankings 4 . The ranks were A*, A, B, C and other which were coded as 1, 2, 3, 4 and 5 respectively. The final concept lattice generated for the last five years of publications of Knowledge Discovery Team is shown in Figure 7.

Lattice Filtering Criteria

There are two categories of filtering provided by LatViz; one is for the concept lattice created with the binary data and the other one is provided for the pattern concept lattice built with the help of interval pattern structures.

Filtering Concept Lattice. After a concept lattice is built by applying FCA, expert is allowed to set several filtering criteria such as stability, lift, extent size, intent size and finally specific object or attribute names. Let us consider that in the running example, the expert is looking for the papers published by Amedeo Napoli on the topic of pattern structures and FCA. A filter on the number of attributes in the intent is set to 3. The filtered concept lattice obtained over the complete lattice is shown in Figure 8. It further shows the authors with who Amedeo Napoli has worked i.e., Sergei O. Kuznetsov and Mehdi Kaytoue. This part of concept lattice shows the community of authors working with Amedeo Napoli on the topic of pattern structures. Filtering Pattern Concept Lattice. Interval Pattern Concept Lattices can also be filtered by specifying the number of attributes to be considered, the upper and the lower limits for the intervals in the intent of each attribute along with stability, lift and extent size. Let us consider the pattern concept lattice in Figure 7 which is hard to interpret. To make it more readable based on what an expert wants, (s)he is allowed to specify filters. For example, if the expert is looking for a paper published in a conference of a rank 1-4 in the year 2012 -2015 and has the number of pages not less than 2 and no more than 42 then the respective filters can be set for the values of all three attributes. The filtered pattern concept lattice will then only contain the part of lattice needed by the user. Figure 7 shows the concept containing group of papers published from 2014-2015 in conferences with rank 2 having number of pages 2-42.

Attribute Implications

One of the many proposed visualization techniques for implications includes table-based views. The columns in the table represent rule ID, LHS and RHS of the rule, support and confidence measures. These views were used because of the simplicity of storage. However, as the number of rules can be too many it is not very evident for the expert to focus on interesting rules at a simple glance. Another way of visualizing association rules are Matrix Views, where rows represent the LHS and columns represent the RHS of the rules. Support and confidence are displayed by different colors in the intersection of the LHS and RHS. In case of a formal context, the number of objects/attributes can be very big leading to problems in displaying the matrix. By carefully taking into account the above drawbacks, we finally settle on visualizing implications with the help of scatter plots, where the x-axis shows the increasing support and the y-axis shows the increasing lift (as we are considering implications the confidence of the rule is always 100%). Such kind of display helps the expert to single-out the rules (s)he wants to visualize based on the values of support and lift. Figure 10 shows implications of the running example, x-axis keeps the support in percentage and y-axis keeps lift. The number on top of the circle shows the number of rules existing in the same point in the plot. On mouse over, expert can view the implications.

Related Tools

In [2], the authors focus mainly on interactive data exploration over RDF data for interactive knowledge discovery. It clusters RDF triples based on RDF Schema and then allows interactive exploration with the help of RV-Xplorer (Rdf View eXplorer) [3]. It is a tool for visualizing views over RDF graphs mainly for identifying interesting parts of data and allow data analysis. It has also been extended for clustering SPARQL query answers. To-date there have been many other tools developed for reducing the effort of expert in observing and interpreting a concept lattice. Many of the tools have been developed for more specific purposes. CREDO [8] and FooCA [17] are the Web Clustering Engines [7] which take the answers from queries posed against search engines and create a concept lattice which is then displayed to the expert for interaction. CREDO allows only limited interaction, however, FooCA allows the expert to edit the context and iteratively build the concept lattice. CEM [10] is an email manager which allows quick search through the e-mails and usually deals with smaller concept lattices. Camelis [11] is a system based on FCA for the organization of documents allowing several navigation operations. Another set of tools such as Sewelis [13] and Sparklis [12] allows navigation/interaction over knowledge graphs. Many other tools such as Galicia 5 , ConExp and ToscanaJ 6 are developed for academic purposes. LatViz takes the basic functionalities of ConExp and takes it to the another level by providing visualization for many algorithms introduced over time to increase the readability. Moreover, it re-uses the source-code for building concept lattice with the help of the algorithm in [14] from ToscanaJ [4]. It can not only be applied to WOD but it has been extended for interpreting any kind of data.

Discussion and Future Improvements

LatViz is a tool built for allowing expert interaction for data analysis purposes. It provides many new functionalities for reducing the exploration space of the expert and enable him to interpret the results. As a future perspective, we also want to implement other variations of pattern structures such as Pattern Structures introduced for structured set of attributes discussed in [1] and Heterogeneous Pattern Structures [9]. We also want to extend the implementation of implications to association rules. Finally, we also want to take into account matrix factorization.

Introduction

The ease of consuming Linked Open Data (LOD) depends on the availability of schema information. This holds for tasks such as browsing, where a user may not know the structure of the data found in a dataset, or querying, where schema information could be used for query optimization. In the LOD setting a query can be evaluated against the original LOD datasets through query federation or by evaluating it centrally against a LOD crawl. In both scenarios, the efficiency of query evaluation may be improved by identifying those datasets schematically matching the query -maybe partially -while leaving out others.

In the LOD cloud schema information is sparse, as many data items come with incomplete schema information or lack schema descriptions entirely. Methods for schema induction and ontology learning have been studied to remedy this problem ( [4], cf. section 2). A method, that has successfully been used in this context, is Formal Concept Analysis (FCA) (cf. [2], [3], [12]).

To our knowledge, FCA has not been used for constructing indices, that allow a schema-oriented query-to-graph mapping. Particularly, we are not aware of previous work on mapping queries to formal contexts. We expect that FCA will benefit this kind of indexing through the formally sound construction of schemata that are free of external heuristics and concise at the same time. In this paper, we outline an approach for such a schema index and point to future work on an implementation.

Related Work

For our approach to schema indexing, we propose a property-based schema induction using FCA. Property-based type clustering is discussed in literature as a remedy for the schema sparsity in LOD datasets. The feasibility of such approaches has been analyzed in [5]. The authors show that the properties of resources within LOD datasets can be used for deducing resource types. [10] argue for a property-based data access for programming with Linked Data in order to deal with a lack of type descriptions. [6] further corroborate this position, as they argue for property-based concept definitions. In order to ensure quality of such definitions, they propose a system for incorporating interactive user feedback.

Schema induction, the learning of schema information from data, is a way to handle schema sparsity. [11] describes a statistical approach to schema induction through association rule mining on transaction tables. A recent approach is presented in [7]. It combines the mining of property-based entity descriptions and type clustering over these using DBSCAN. An overview over the field of schema/ontology learning is given in [4].

FCA has been applied to problems related to ontology learning. In [3] it has been used for learning taxonomies from natural language text. The authors of [2] and [12] use attribute exploration from FCA for semi-automatic approaches to ontology completion. Lately, [1] used FCA-based association rule mining for completing type definitions given in DBPedia data through further implied information.

We combine the induction of schema with building and providing an index for query-to-graph mapping. An index for subgraph querying is presented in [14]. There the authors make use of a precomputed lattice of subgraphs in order to narrow down the candidates for subgraph queries. An approach similar to ours is demonstrated in [8]. The authors present a schema-based index that is consisting of three layers, each supporting different types of queries. The index is constructed through clustering of RDF type information in a stream-based fashion. The approaches presented in [7], [8] and [12] either introduce heuristics or human oversight or require case specific parameter tuning. We sketch a FCAbased schema index that is free of such external factors and general enough to map the diverse data found in the LOD cloud.

Preliminaries

In the following we give a short introduction to Formal Concept Analysis (FCA), a method for conceptual knowledge discovery and representation, as well as the basics of RDF and SPARQL.

We lend the following definitions 1, 2, 3 from [13]: A formal concept is a pair (A, B) with A = B and B = A. A is the extent, B is the intent of the concept. As in [13], we abbreviate the set of all formal concepts for a formal context as L(G, M, I).

Definition 1 (Formal Context). A formal context K := (G, M, I)
Formal concepts fall naturally into a hierarchy, called a concept lattice, by a subconcept-superconcept-relation defined via the subset relations over G and M , respectively.

Definition 3 (≤). For two concepts

(A 1 , B 1 ), (A 2 , B 2 ) [13] define (A 1 , B 1 ) ≤ (A 2 , B 2 ) ⇔ A 1 ⊆ A 2 (equivalently, ⇔ B 1 ⊇ B 2 ). The pair (L(G, M, I), ≤) is called concept lattice.
RDF Datasources of the LOD cloud contain RDF1 data. For now, we abstract from the possibility of blank nodes in RDF data.

Definition 4 (RDF Graph). Given the set of RDF resource identifiers U and the set of literals L and having the set of RDF terms T := U ∪ L: An RDF graph is a set of RDF triples D ⊆ {< s, p, o > |s ∈ U, p ∈ U, o ∈ T }. We further define the set of all known RDF graphs D := {D|D is a known graph}.

SPARQL A language for formulating graph oriented queries against RDF datasets is SPARQL2 . For this paper, we will focus on Basic Graph Patterns that are used for formalizing graph pattern matching and, thus, are fundamental to SPARQL(cf. [9]). Here, we further assume that queries are only evaluated against the default graph of a datasource.

Definition 5 (Basic Graph Pattern). Given a set V of variable names, a Triple Pattern tp is a triple (s, p, o) ∈ (U ∪V )×(U ∪V )×(T ∪V ). A Basic Graph Pattern (BGP) of a query q is a set containing a number of Triple Patterns. We abbreviate the set of all queries only containing a single BGP as BGP .

With this restriction to single-BGP queries, we define the solution to a query q through matching its BGP against the RDF graph D as q(D) (cf. [9]). We further define a solution to q against a set of graphs D as q(D) := q( D∈D D).

An example for a BGP and a possible solution is given in fig. 1 b),c).

Schema Index

In a query federation system a central query processor accepts and processes queries by dispatching (parts of) the queries to datasets (i.e., computing nodes serving them). In the case of LOD these datasets are graphs. The schema index maps queries onto minimal sets of graphs required for evaluating the given The optimal schema index minimizes the subset of all known RDF graphs to be used for returning the complete solution of a query q:

D i (q) = argmin Dj ⊆D∧q(Dj )=q(D) |D j |. (1)
The improvement of efficiency of query evaluation then depends on the number of graphs left out of D i (q). Judging a graph to be relevant for query evaluation may be based on a schematic match of a query and the graph.

In our approach the matching will be informed by an underlying lattice of property type clusters induced from the graph data via FCA. With our approach, the schema index constructs and maintains a schema lattice covering every graph encountered. We build this lattice by applying FCA on a formal context extracted from an RDF graph. While extracting features given in the graphs, the schema index will also store the set of graphs contributing individual features to the subsequent lattice construction.

Definition 8 (Feature-contributing Graph). For an RDF resource r and a feature p ∈ F , we define a set of feature-contributing graphs as γ(r, p) = {D|p ∈ f (D, r)}. For the features of an intent B, we define the set of contributing graphs as γ (B) = {D|∃p ∈ B, ∃r ∈ U : D ∈ γ(r, p)}.

We conceive the schema index as a pair (L S , Γ ) of the schema lattice L S and a function Γ mapping queries to indexed graphs. In order to look up graphs that a query should be evaluated against, the schema index then derives the queries type information through the Query-Type Map function: Definition 9 (Query-Type Map). The Query-Type Map Θ is a function Θ : BGP → 2 F that maps a query q to a set of intents Θ(q). For a query q the schema index returns the set of schematically appropriate graphs as follows:

Γ (q) = {D|D ∈ γ (B) for some B ∈ Θ(q)}.
For our running example (cf. fig. 1), the graph g ex would be returned for the BGP, as here {ex:title, ex:tracks} constitutes an intent reflected in the query.

Outlook and Conclusion

In this position paper, we sketch the idea of a schema index for a query-to-graph mapping. For constructing the index we aim at an automatic schema induction process through FCA. We hypothesize that FCA is a good method for this use. One, it is independent of external factors, such as expert involvement as in [12] or a task specific parameter tuning as done in [7]. Two, by design it is a method targeting property-based entity descriptions as argued for in [6], [5].

Our proposition is that the schema index returns the graphs necessary for a complete query evaluation: q(Γ (q)) = q(D) (for every query q)

(2)

However, Γ (q) may return graphs that might be disregarded for evaluating BGP. Hence, the proposed schema index is not necessarily optimal. For a future implementation we plan to approximate the optimal case (cf. ( 1)). This must only be done to a degree that is sensible, since potential savings in execution time are being countered by costs for building and looking up the index.

Dominik Brosius and Steffen Staab

Towards a realization of the proposed schema index, we expect to face questions such as for the size of formal contexts as given through the feature domains of a graph. Next steps for our research will also involve empirical analysis of runtime behaviour and scalability of FCA in the LOD use scenario. We have indications that in spite of exponential worst-case complexity, the property-based clustering of data items may lead to empirically acceptable runtime behaviour. A further question in this context is how to efficiently update existing lattices, when, e.g., encountering further features of an object while still ingesting a graph in a stream-based fashion. For such a scenario, we will also look into what lattice construction algorithm to choose. Finally, we plan to address the problems of reducing the size of formal contexts and lattices through appropriate data preparation and cleansing lattices of "noisy" concepts.

Introduction

In this paper, we would like to extend and complete a previous work on the classification of Linked Open Data (LOD) [2]. The basic unit of LOD is the RDF triple which is composed of three elements, namely a subject, a predicate and an object, i.e. (subject, predicate, object). It can be noticed that subjects, predicates and objects can be organized into a partial ordering depending on a specific schema (i.e. RDFS) or an ontology (e.g. YAGO or DBpedia Ontology).

The classification of LOD should take into account the RDF triple as a basic unit and this can be done in several ways. We distinguish ways that relies on a "triples" view of LOD and ways that relies on a "graph" view. Following the lines of [2], we consider an approach which considers triples and which is based on pattern strucures [6]. We complete this approach by integrating the organization of predicates in the classification of RDF triples.

In [2], it was shown how the classification of RDF triples amounts to classify pairs of objects and attributes -as in a binary context-where attributes are partially ordered. Actually, given a subject which corresponds to an object in a binary context, predicates are considered "one by one" and attributes are viewed as "ranges" of the predicates. Attributes are organized within a partial ordering and there are two main ways of dealing with this order. The first one is to consider a "scaling" as in [3,4] where the description of an attribute correspond to the set of its ancestors in the attribute hierarchy, and the similarity between two attributes is given by the minimal elements in the intersection of their descriptions In the second way, it can be shown that pattern structures for structured sets of attributes are very well adapted to solve the problem of classifying RDF triples for analyzing the content of LOD. As it was precised in [6], it can be considered that the description of an attribute is an antichain and the similarity is given by the intersection of antichains (which is actually an alternative way of handling the scaling introduced just above).

Both approaches are discussed in [2], where in addition a specific procedure based on RMQ is used for efficiently computing the intersection of antichains. In the present work we add the "predicate dimension" within RDF triples and we propose first elements for extending our preceding approach by considering the predicate classification. The basics of the approach are detailed but for the moment no experiments are proposed, which is planned in a future work. However, we show that this new proposal is sound and formally consistent.

The paper is organized as follows. First, we present some preliminaries about the web of data and LOD. Then, we recall and discuss the previous approaches for classifying RDF triples or RDF graphs. Finally, we detail and illustrate our new proposal, and prove a main proposition on the similarity of object descriptions.

Web of data

Basically, the web of data consists of resources and relations between those resources. It can be represented as a graph where nodes are resources and edges are relations.

The core of the web of data is the RDF (Resource Description Framework) language, based on graph model where basic units are (subject, predicate, object) triples. These triples, also called RDF statements, describe facts [1].

Definition 1 (RDF Triple). Given a set of URIs U, blank nodes B and literals L, an RDF triple is represented as t

= (s,p,o) ∈ (U ∪ B) × U × (U ∪ B ∪ L), where:
s is called subject, p predicate and o object; -U is the set of all resources identified by a URI (Universal Resource Identifier); -B is the set of resources that are unidentified (called blank node); -L is the set of literals, which are values like strings, dates or integers.

As its name suggests, RDF allows one to describe resources. Resources can refer to any object or thing. For convenience, the terms borrowed from description logics can be used to distinguish different types of resources:

Properties: express binary relationships between any two entities; Classes: represent sets of entities; Instances: entities that belong to a class; Variables: unidentified resources (i.e. blank nodes).

RDF has some specific vocabulary. For example, the property rdf:type enables to declare an instance as belonging to a class. This expression has two parts, separated by a colon. The second part identifies the specific resource of this vocabulary, here "type". The first part, also called prefix, is an abbreviation for "http://www.w3.org/1999/02/22-rdf-syntax-ns#", the namespace which refers to the RDF vocabulary. Each vocabulary has its namespace.

In order to give RDF some structure, schemas are used. Schemas describe constraints on facts. They correspond to the TBox in description logics terms. Each vocabulary may have its own schema, that is a structure between its entities, called its reference schema. The structure of RDF triples is based on RDFS (RDF Schema), bringing additionnal properties such as rdfs:subPropertyOf and rdfs:subClassOf. These two additionnal properties enable to build a hierarchy of relations one the one hand and classes on the other hand. Afterwards, these properties will be denoted subP and subC, respectively. Instances can be linked to the hierarchy of classes, but they are not part of it, since they are related to a class with rdf:type. Thus, in the following, a hierarchy will refer to an orderred set of classes, and instances will be attached to their class (for simplicity, a unique class per instance is considered here).

The language SPARQL offers to run queries on the web of data. A query is composed of RDF triples containing variables. For example, the query SELECT ?x WHERE {?x rdf:type C} returns all the instances of C.

A toy knowledge base, freely inspired by the example of S. Ferré in [5], is presented in Figure 1. The Figures 1b and1d correspond to a set of RDF statements and the associated graph respectively. The Figures 1c and1a represent the background knowledge. Instances of the knowledge base are considered and linked to the class hierarchy.

Reference schemas. Resulting from the linked open data, each data set is connected to others. Thus, hierarchies are not guarantee to be a tree -instances belonging to classes of their schema and to classes of another schemata for example.

In this work, we consider that all the classes on one hand and all the properties on the other hand belong to the same reference schema; that is, have the same namespace. We will also assume that, for any reference schema, there are neither subP nor subC cycle.

Another concern is that, the tree structure is not guaranteed, even if there is no cycle. If C 1 and C 2 are two incomparable classes, both subclasses of C 3 and C 4 that are also incomparable, then, we lost the tree structure and we have a conflict. Here, we suppose that we know how to linearize the hierarchy of each class as the linearization of a product of two partial orderings.

Formal Concept Analysis

Formal Concept Analysis (FCA) [7] is a mathematical framework used for classification and knowledge discovery. As a learning process, FCA allows one to build an ordered set of concepts where objects are classified w.r.t. the attributes that they share.

A lot of extensions have been proposed, and some of them can be usefull to deal with WOD. Two approaches are possible: the first consists in considering the RDF graph itself whereas the second consists in considering the RDF statements.

Classifying the web of data enables to find inconsistencies resulting from the merging of different data sets. It is also a way to discover relationships or implications that are not explicit in any single data set. Moreover, the visual support given by the lattice allows users to easily navigate through hierarchy for exploratory research.

WOD as a set of statements

The first approach consider WOD as a set of RDF triples. This approach is related to the works of [4], [8], [9] and [2].

Classification w.r.t. background knowledge The WOD can be classified through RDF triples. However, in order to be interesting enough, this approach has to take into account background knowledge such as the classes and properties hierarchies. This problem has been developed in [4]. The authors consider a set of documents as objects and a set of terms as attributes. Terms belong to a thesaurus and they are organized in a tree structure. In order to build the lattice, they consider M * the set of terms in the thesaurus, and define an order M * , meaning that "any attribute implies any of its more general attributes." For example, if the term indexing is more specific than information-analysis in the thesaurus and if it is an attribute of a document d, then information-analysis is also an attribute of d. Then, the authors define the intersection ∩ * of two intents m 1 and m 2 as "the most specific attributes in M * that are more general than m 1 and m 2 ." With this new operator, they can build concept lattices taking into account background knowledge. In the following, we will present an extension of this approach.

Triadic Concept Analysis

The triadic concept analysis (TCA) [12] considers an additionnal dimension (the modus). This implies a ternary relation Y ⊆ G × M × B which can be interpreted as "the object g takes the value b under the condition m." The corresponding Galois connections are more complex: they are three and each one corresponds to a dimension expressed in terms of the two others.

Mining triconcepts. TCA is used to describe folksonomies, i.e. communities of users U who can annotate resources R with keywords (tags) T . An example of taxonomy is Bibsonomy, a tool allowing users to manage publications and to tag them. Here a concept would be a group of users tagging a set of resources with identical keywords The algorithm Trias [8] has been proposed to mine tri-concepts. It is based on a projection of the triadic context (U, T, R, Y ) onto a dyadic context (U, (T × R), I). For each concept (A, J) found in (U, (T × R), I) context, a new dyadic context (T, R, J) is built. For each concept (B, C) found, (A,B,C) is a concept of (U, T, R, Y ).

Finding biclusters. In [9], the authors aim to find biclusters in a numerical dataset. The context is similar to a standard formal context, but instead of a binary context, a context with numerical values is considered. In order to have a triadic context, objects and attributes remain the same and the numerical values are transformed into a third dimension by means of an interordinal scaling. A threshold θ is provided and the new dimension is made up of intervals whose range sizes are less or equal to θ.

Limitations. Given that TCA can handle three dimensions, it could be interesting for WOD. However, a simple approach does not take into account the background knowledge. Thus, taking into account the hierarchies implies a scaling. This implies to add all classes in the dimension of subjects and objects, and all properties in the dimension of predicates. This approach works well in the case of biclustering, when a threshold is given, limiting the number of intervals to consider. By contrast, with WOD, such a threshold can hardly be considered. Moreover, having this constraint does not guarantee the scalability.

Pattern structures Pattern structures (PS) [6] are proposed in order to consider data which are not binary data. Attributes then become descriptions which are partially ordered thanks to a similarity operation. Formally, a pattern structure is defined as follows:

Definition 2 (Pattern structure). Let G be a set of objects, (D, ) a semilattice and δ : G → D a mapping. Then (G, (D, ), δ) is called a pattern structure. The new Galois connections are the following:

-A = g∈A δ(g) for A ⊆ G -d = {g ∈ G | d δ(g)} for d ∈ D
Pattern structures are used on triples in [2]. In this work, the authors aim to provide a navigation space over RDF resources. The underlying idea is that, when a resource is a subject in a triple, we can consider that the pair (p,o) is describing this resource. Thus, two resources can be compared regarding how they are described by the triples in which they are subjects. Moreover, there is background knowledge related to objects provided by the properties rdf:type and subC. Considering a set of triples B = (s i , p j , o k ) and a hierarchy of classes, this idea can be materialized in term of formal concepts. To that purpose, a pattern structure (G, (D, ), δ) is constructed as described below.

Entities3 and their descriptions.

The set B of RDF statements is built with a SPARQL query on a specific namespace. The associated reference schema is used to construct the hierarchy of classes from this namespace.

First, resources that are subjects of at least one triple in B are considered as entities of the pattern structure: G = {s 1 , . . . s n }. They will be compared regarding the objects they share for each predicates. Objects can be instances or classes, but here only classes are considered. Indeed, the hierarchy between the objects is based on the property rdfs:subClassOf, but instances are linked to classes with the relation rdf:type. In order to maintain the consistency, objects that are instances are replaced by the class they belong to.

Each

{d x i } {d y j }
where min returns the minimal elements

{d x i } {d y j } = lcs(C(o x i ), C(o y j )) if i = j ∅ else
where lcs returns the most specific superclass This definition is close to the ∩ * used in [4]. The operation between two descriptions corresponds to finding the most specific attribute in M * . Considering only the minimal of the union corresponds to "retaining only the most specific elements of the set generated this way".

Limitations. This work introduces a method to mine triples with pattern structures as in [2]. The main limitation is that, the hierarchy of predicates is not considered.

WOD as a graph

Instead of considering RDF triples, it is possible to consider the associated graph. This is what is done in some approaches like [11], [10] and [5].

Pattern structures for graphs In [11], pattern structures are used to classify graphs. Each graph is considered as an object and the set of all its subgraphs is considered as the description. Thus, the similarity between two graphs is the set af all the subgraphs they have in common.

As this approach is expensive, graphs can be simplified by the mean of projections. That is, instead of considering all the subgraphs of a graph, the description is something simpler like the set of chains of a certain size that compose the graph.

Concept lattices of conceptual graphs

In [5], 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 in one hand and relations in the other hand. Contrary to RDF graphs which consider only binary relations, CGs handle n-ary relations. Projected graph patterns are introduced as concepts. It is similar to a SPARQL query where the graph query is the intent and the candidate solutions are the extent.

Example 1. Given the Figure 1, we have the concept ({(Hope,Arkansas), (Honolulu,Hawaii)}, {(?p, birthPlace, ?x), (?x, city, ?y)}). Note that, the syntax is different from [5], since the example is adapted to RDF. This concept is associated to the query SELECT ?x ?y WHERE { ?p birthPlace ?x . ?x city ?y.} Concept lattices of RDF graphs In [10], in addition to the RDF graph, a formal context corresponding to the background knowledge is considered. This context has a set of resources that are objects and attributes at the same time. Considering one resource as object, its attributes are the set of resources that are "more general" regarding subC and subP properties.

Example 2. Given the knowledge base Figure 1, a part of the formal context could be the following:

City Capital president sameSettingAs Honolulu Hawaii

City × Capital × × president × × sameSettingAs × Honolulu × × × Hawaii
× The extent of the pattern is a set of resources whereas the intent is a triple graph. A triple graph is basically a subgraph and some background knowledge. A morphism between two triples graphs is defined and corresponds to an order on intents. Moreover, a product between triple graphs is defined such that the join of two concepts (i.e. triple graphs) corresponds to their product.

Example 3. Given the knowledge context and the graph pattern corresponding to the triple (Honolulu,capital,Hawaii), the graph corresponding to the triple (Honolulu,city,Hawaii) is more general.

Taking into account the three parts of the triple

In this section, we propose a generalization of [2] : instead of considering subjects described by (predicate,object) pairs, we consider the entire triple as a description.

Entities and descriptions

We suppose that each triple has a unique identifier, like a transaction id. These identifiers are the entities of the pattern structure : G = {t 1 , . . . , t n }. The description of an entity is a mapping to the triple itself, where instances are replaced by the class they belong. As to not complefy the notation, C(s) and C(o) will be written s and o.

Order on descriptions Given the descriptions δ(t i ) = (s i , p i , o i ) and δ(t j ) = (s j , p j , o j ), the partial order on descriptions is defined as follow: δ(s i , p i , o i ) δ(s j , p j , o j ) ⇔ s j subC s i , p j subP p i , o j subC o i Similarity between descriptions The similarity between two triples t i and t j is defined as follow:

δ(t i ) δ(t j ) = (lcs c (s i , s j ), lcs p (p i , p j ), lcs c (o i , o j )) Proposition 1. δ(t i ) δ(t j ) ⇔ δ(t i ) δ(t j ) = δ(t i ). Proof. δ(t i ) δ(t j ) ⇔ s j subC s i , p j subP p i , o j subC o i ⇔ lcs c (s i , s j ) = s i , lcs p (p i , p j ) = p i , lcs c (o i , o j ) = o i ⇔ (lcs c (s i , s j ), lcs p (p i , p j ), lcs c (o i , o j )) = (s i , p i , o i ) ⇔ (s i , p i , o i ) (s j , p j , o j ) = (s i , p i , o i ) ⇔ δ(t i ) δ(t j ) = δ(t i )
Similarity between set of triples The similarity of two triples can be generalized to set of triples. The description of a set of triple T is the set of descriptions of each of its triples :

∆(T ) = {δ(t) | t ∈ T }.
Given two sets of triples T 1 and T 2 , the similarity T 1 T 2 is the set of minimal triples δ(t i ) δ(t j ) for all t i in T 1 and for all t j in T 2 given the order on descriptions.

Conclusion

In this paper we discussed some approaches for dealing with the classification of web of data, and more precisely of sets of RDF triples, i.e. (subject, predicate, object). Actually, this kind of classification process is based on the classification of pairs (subject, attribute) which simulate the RDF triples and where attributes correspond to object triples and are structured within a hierarchy. Here, we proposed an extension to a previous work which takes into account the classification of predicates which was not the case before. We gave a formal presentation of this proposal and for future work we are planning to make a series of experiments which should (hopefully) validate the current approach.

Introduction

Formal Concept Analysis (FCA) considers the classical Galois derivation operator (i.e. the sufficiency operator) for extracting formal concepts organized within a hierarchy (i.e. partial ordering) called the concept lattice. The concept lattice has proved highly useful for knowledge discovery. The knowledge is expressed as attribute implications, that are formulas in the form {a 1 , ..., a n } → {b 1 , ..., b m } where a 1 , ..., a n , b 1 , ... and b m are attributes. It is considered that the underlying semantics is a conjunctive one. Indeed, by {a 1 , ..., a n } → {b 1 , ..., b m }, the interpretation "a 1 " and ... and "a n " → "b 1 " and ... and "b m " is implicitly agreed.

Recently, Dubois and Prade [6] [9] have given a possibility-theoretic reading of formal concept analysis. Beyond the sufficiency operator currently used in FCA, the possibilistic interpretation proposed by these authors allows to consider three other (powerset) operators namely possibility, necessity and dual sufficiency [5] [3]. In this spirit, the aim of this paper is to enlarge the knowledge representation capability of FCA to so-called "disjunctive attribute implications" instead of the conjunctive attribute implications considered by current approaches [1] (introduced in [11]). It will be shown that the proposed approach considers "open-closed" pairs obtained by means of the asymmetric composition (N • Π) of necessity and possibility operators, and then we propose a method for inducing disjunctive attribute implications.

The remainder of the paper is organized as follows. Section 2 gives a background on FCA. The possibility-theoretic view of FCA is discussed in section 3, whereas the next section presents our contribution which highlights the interest of using possibility theory operators in order to induce disjunctive attribute implications from formal contexts. Section 5 presents the same analysis for incomplete formal contexts and finally, Section 6 deals with necessity degrees in uncertain formal contexts.

2 Formal concept analysis: basic notions Formal concept analysis [1] is a lattice-based setting for data analysis and knowledge representation. It relies essentially on a binary relation between a set of objects and a set of attributes. This relation is called a formal context. More formally, a formal context is a triple K = (O, P, R) where O is a set of objects, P a set of attributes and R a binary relation s.t. R ⊆ O × P. xRa means that the object x satisfies the attribute a.

Example 1. We consider an example of formal context K S = (O, P, R) given in Table 1 where O = {John, Maria, Peter, Clara} and P = {Man, Woman, Father, Mother, Parent}. The cross mark × indicates that the related object satisfies the corresponding attribute. Whereas the empty mark indicates the contrary.

The paradigm of formal concept analysis [14] is classically based of an adjoint pair of operators (.) ∆ : 2 O → 2 P and (.) ∆ : 2 P → 2 O (called Galois derivation operator in the literature) defined for two sets X ∈ 2 O and A ∈ 2 P as follows :

A ∆ = {x ∈ O | ∀a ∈ P (a ∈ A ⇒ xRa)} X ∆ = {a ∈ P | ∀x ∈ O (x ∈ X ⇒ xRa)}
That is, A ∆ corresponds to the set of objects that satisfy all attributes in A. Similarly, X ∆ corresponds to the set of of attributes that are satisfied by all objects in X.

A formal concept of K is a pair of closed sets (X, A) with X ⊆ O, A ⊆ P such that X ∆ = A and A ∆ = X. X is called the extent and A the intent of the formal concept (X, A). For instance, ({Clara}, {Woman, Parent, Mother}) is a formal concept of K S . The set of all formal concepts (denoted by B(O, P, R)) equipped with a partial order defined as: (X 1 , A 1 ) (X 2 , A 2 ) if X 1 ⊆ X 2 (or equivalently, A 2 ⊆ A 1 ) forms a complete lattice (denoted by L(O, P, R)).

Formal concepts lattices can be characterized in terms of attribute implications [10]. An attribute implication is an expression A → B where A and B are subsets of attributes (A, B ∈ 2 P ) and it holds in a formal context if A ∆ ⊆ B ∆ (equivalently B ⊆ A ∆∆ ). The semantics of the attribute implication is that, for every object x ∈ O, if every attribute from A applies to the object x, then every attribute from B also applies to x. It is important to remark that the underlying semantics is a conjunctive one. Thus, our objective in the following is to consider additional knowledge in the form of so-called disjunctive attribute implications.

Table 1. Formal context K S .

R Man Woman Father Mother Parent

John × Maria × Peter × × × Clara × × ×

Asymmetric Composition of possibilistic operators

The Galois derivation operator which is at the basis of FCA theory is the operator of sufficiency (.) ∆ . Some time ago, Dubois and Prade [6,9] have highlighted, in the setting of possibility theory, three other powerset derivation operators, namely the possibility operator (denoted (.) Π ), the necessity operator (denoted (.) N ) and the dual sufficiency operator (denoted (.) ∇ ). The two former operators are given in the following:

-(A) Π corresponds to the set of objects that are associated with at least one attribute in A. Formally, we have: N corresponds to the set of objects such that any attribute that satisfies one of them is necessarily in A.

(A) Π = {x ∈ O | ∃a ∈ A, xRa} -(A)
(A) N = {x ∈ O | ∀a ∈ P (xRa ⇒ a ∈ A)} (X) Π and (X) N are dually obtained. Let xRa indicates that object x does not satisfy attribute a. In the particular case where the derivation operators (.) Π , (.) N , (.) ∆ are applied to the complementary context K(O, P, R) (where R = {(x, a) ∈ O × P | xRa}), we will exceptionally use the explicit notation (.) Π K , (.) N K , (.) ∆ K . Given X ⊆ O and X its complementary set (i.e. O \ X), the following recalls some useful properties [5] needed in the rest of the paper.

P 1 : X ∆ K = (X Π ) P 2 : X ∆ K = (X) N P 3 : X 1 ⊆ X 2 ⇒ (X 1 ) Π ⊆ (X 2 ) Π P 4 : X ⊆ ((X) Π ) N P 5 : (X 1 ) Π ∪ (X 2 ) Π = (X 1 ∪ X 2 ) Π P 6 : X 1 ⊆ X 2 ⇒ (X 1 ) N ⊆ (X 2 ) N P 7 : (X) Π = (((X) Π ) N ) Π
These properties are dually satisfied for A ⊆ P.

Let us also denote by NΠ-pair, a formal pair (X, A) s.t. X = A Π and A = X N , where X (resp. A) will be called NΠ-extent (resp. NΠ-intent). It may be remarked that both elements X and A present dual topological properties. Indeed, X is an open element, whereas A is a closed one, achieving then an "open-closed" pair. The set of all NΠ-pairs is denoted by B NΠ , whereas the set B NΠ (Ext) (resp. B NΠ (Int)) corresponds to the set of all NΠ-extents (resp. NΠ-intents). Proposition 1 establishes first a characterization of NΠ-pairs, whereas the proposition 2 gives the algebraic structure of the set B NΠ .

Proposition 1. Let X ∈ 2 O and A ∈ 2 P , (X, A) is an NΠ-pair if and only if (X, A) is a formal concept in K(O, P, R).
Proof. It is proved using properties P 1 and P 2 given in section 3.

It has been already established that the set B NΠ with a partial order (denoted ) defined as (X 1 , A 1 ) (X 2 , A 2 ) if X 1 ⊆ X 2 (or, equivalently, A 1 ⊆ A 2 ) forms a complete lattice, called the NΠ-lattice and denoted by L NΠ . The following proposition gives the infima (greatest lower bound) and the suprema (least upper bound) for a given subset of L NΠ .

Proposition 2. The infima and suprema of a subset (X j , A j ) (j an index set) of L NΠ are given by: j∈J

(X j , A j ) = ( j∈J X j , (( j∈J A j ) Π ) N ); j∈J (X j , A j ) = ( j∈J X j , j∈J A j ).
Proof. This result can be established using Proposition 1, and the fact that (X, A) is a formal concept of K(O, P, R). Example 2. Figure 1 illustrates the L NΠ lattice corresponding to the formal context given in Table 1.

Let us now introduce the mapping µ which associates to each set of attributes A ∈ 2 P , its NΠ-pair such as:

µ : 2 P → B NΠ A → µ(A) = (A Π , (A Π ) N )
The following proposition establishes the mapping µ for a set A of attributes. Being understood that the satisfaction of such an implication is related to the set of all objects in O, we agree that a formal context K(O, P, R) satisfies a disjunctive attribute implication A -→ B if and only if every object that is never satisfied by each attribute from B is also never satisfied by each attribute from A.

Formally, K | = A -→ B, iff ∀x ∈ O, i f b 1 {x} Π ∧ ... ∧ b m {x} Π then a 1 {x} Π ∧ ... ∧ a n {x} Π
For example, the formal context K S given in Table 1 satisfies the disjunctive attribute implication Parent -→ Father ∨ Mother (K S | = Parent -→ Father ∨ Mother).

The following important result can be easily obtained.

Proposition 4. The disjunctive attribute implication A -→ B is valid in formal context K(O, P, R) iff the attribute implication B -→ A is valid in formal context K(O, P, R) iff A ⊆ ((B) Π K ) N K .
Proof. Suppose B -→ A is valid in K. In logical terms, it means ∧ b∈B ¬b → ∧ a∈A ¬a, which is logically equivalent to

∨ a∈A a → ∨ b∈B b. Now, B -→ A is valid in K means A ⊆ B ∆∆ K , that is, A ⊆ (B Π K ) ∆ K iff A ⊆ ((B) Π K ) N K .
A simpler way to assert the satisfaction of a disjunctive attribute implication based on the possibility operator (.) Π is given hereafter.

Proposition 5. Given a formal context K(O, P, R) and A, B ⊆ P, K |

= A -→ B iff for each x ∈ O, B {x} Π or A ⊆ {x} Π .
The disjunctive attribute implications that hold in a formal context K(O, P, R) can be obtained from concept lattice L NΠ . The following proposition illustrates this.

Proposition 6. Given a formal context K(O, P, R), K | = a → B iff (a Π , (a Π ) N ) ≤ (B Π , (B Π ) N )
This means that we have to check in the concept lattice L NΠ whether the NΠ-pairs associated to a are located above the infima of all NΠ-pairs associated to b from B. Example 3. In the following we give the set of disjunctive attribute implications that matches to the formal context given in Table 1 by applying the proposition: {Father→Man, Mother→Woman, Father∨Mother→Parent, Parent→Father∨Mother}

Possible and certain implications in incomplete contexts

The case of incomplete context has been only considered by Obiedkov [13] and by Burmeister and Holzer [2] until now. They have proposed to introduce a third value, denoted "?", in a formal context, which leads to the concept of an incomplete context, sometimes also called three values context. More formally, incomplete context K i (O, P, {+, -, ?}, R i ) where O is the set of objects, P the set of attributes, "+", "-", "?" are the three possible entries of the incomplete context, and R is a ternary relation R ⊆ O × P × {+, -, ?}. The interpretation of the relation R is as follows. Let x ∈ O and a ∈ P:

-(x, a, +) ∈ R : it is known that the object x has the attribute a -(x, a, -) ∈ R : it is known that the object x does not have the attribute a -(x, a, ?) ∈ R : it is unknown, whether the object x has the attribute a or not An incomplete formal context may be viewed as a weighted family of all standard formal contexts obtained by changing unknown entries (x, a, ?) into known ones ((x, a, +) or (x, a, -)). The two extreme cases where all such unknown entries (x, a, ?) are changed into (x, a, -) and the case where all such unknown entries (x, a, ?) are changed into (x, a, +) give birth to lower and upper completions, respectively [8] [4].

In this way, two classical (Boolean) formal contexts, denoted K * (O, P, R * ) and K * (O, P, R * ) are obtained as respective results of the two replacements. More formally:

-

K * (O, P, R * ) is a Boolean formal context such that R * = {(x, a)|(x, a, +) ∈ R i } where A ∆ K * = {x|A ⊆ xR * } is the set of objects certainly having all attributes in A -K * (O, P, R * ) is a Boolean formal context such that R * = {(x, a)|(x, a, +) ∈ R i or (x, a, ?) ∈ R i } where A ∆ K * = {x|A ⊆ xR * }

is the set of objects possibly having all attributes in A.

There exists other intermediate formal contexts by replacing each "?" by "+" or "-" and we obtain exactly 2 n possible formal contexts (n is the number of "?" in the initial formal context). All attribute implications that are obtained from these formal contexts are either possible attribute implications or certain attribute implications. An implication is certain if it is valid in each formal context K j ; this condition may seem hard to verify at first glance. The following theorem solves the problem.

Theorem 1. A -→ B is a certain attribute implication in K i iff A ∆ K * ⊆ B ∆ K * Proof. Assume that A -→ B is not a certain attribute implication in K i and A ∆ K * ⊆ B ∆ K * . But A -→ B is not certain implication =⇒ ∃ a formal context K j |x ∈ A ∆ K j and x B ∆ K j
=⇒ ∃ an object x possibly having all attributes in A and not having the certain attributes in

B =⇒ ∃x ∈ O |x ∈ A ∆ K * and x B ∆ K * =⇒ A ∆ K * B ∆ K * .
Another problem is to determine a possible attribute implication that are holds in at least ont formal context K j , the following theorem facilitates this determination. Proofs are omitted due to space limitations.

Theorem 2. A -→ B is a possible attribute implication in K i iff A ∆ K * ⊆ B ∆ K *
This section also considers disjunctive attribute implications, presented in section 4, in incomplete formal context K i . As in the case of conjunctive attribute implications we distinguish certain disjunctive attribute implications and possible disjunctive attribute implications. Note that (A) Π K * is the set of objects certainly having at least one attribute in A and (A) Π K * is the set of objects possibly having at least one attribute in A. And (A)

Π K *
is the set of objects that certainly never have any attribute in A and (A) Π K * is the set of objects that can never have any attribute in A. We get two major results of this paper.

Theorem 3.

A -→ B is a certain disjunctive attribute implication in

K i iff A Π K * ⊆ B Π K * Theorem 4. A -→ B is a possible disjunctive attribute implication in K i iff A Π K * ⊆ B Π K *

Implications from gradually uncertain contexts

In an uncertain formal context the boxes are filled with a pair (α, β) of degree of necessity. That is to say that (α) is the necessity that the object has the attribute, and (β) is the necessity that the object does not have the attribute. Moreover, we should respect the property min(α, β) = 0 [7]. Pairs (1,0) and (0,1) correspond to completely informed situations where it is known that object has the attribute (ie. +), respectively the object does not have the attribute (ie. -). The pair (0,0) reflects total ignorance (ie. ?), whereas pairs (α, β) s.t. 1 > max(α, β) > 0 correspond to partial ignorance.

Consider a pair of thresholds (u, v) with u > 0 and v > 0. K (u,v) is an incomplete formal context obtained by replacing: all entries of the form (α, 0) such that α ≥ u by (+) all entries of the form (α, 0) such that α < u by (?) all entries of the form (0, β) such that β ≥ v by (-) all entries of the form (0, β) such that β < v by (?) The classical formal context (K (u,v) ) * is obtained by replacing with (+) the pairs (α, 0) such that α ≥ u and all the rest with (-). The classical formal context (K (u,v) ) * is obtained by replacing with (-) the pairs (0, β) such that β ≥ v and all the rest with (+).

Observe that (K (u,v) ) * does not depend on v, and increases when u decreases. (K (u,v) ) * does not depend on u, and increases when v increases. Recall that A ∆ K increases as K increases (in the sense of inclusion). Therefore, A ∆ (K (u,v) ) * increases when v increases. B ∆ (K (u,v) ) * decreases when u increases. An attribute implication A -→ B is more certain with u great and v great such that A ∆ (K (u,v) ) * ⊆ B ∆ (K (u,v) ) * . Therefore, the degree of certainty cert(A -→ B) of the attribute implication is equal to the maximum value w such that A ∆ (K (w,w) ) * ⊆ B ∆ (K (w,w) ) * . In particular, cert(A

-→ B) = 1 iff A ∆ (K (1,1) ) * ⊆ B ∆ (K (1, 1
) ) * that is to say that the certain attribute implications are calculated with the most certain part of the data. Also a possibility degree is attached to the attribute implication such that A ∆ (K (u,v) ) * ⊆ B ∆ (K (u,v) ) * which is all the greater as u and v are greater.

We also consider the disjunctive attribute implications in the uncertain formal context. Observe that (K (u,v) ) * does not depend on v, and increases when u increases, and (K (u,v) ) * does not depend on u, and increases when v decreases. Recall that the disjunctive attribute implication A -→ B is valid in a formal context K if and only if the attribute implication B -→ A is valid in K. Therefore, the degree of certainty cert(B -→ A) is equal to the maximum value w such that B ∆

(K (u,v) ) * ⊆ A ∆ (K (u,v) ) * , equivalent to B Π (K (u,v) ) * ⊆ A Π (K (u,v) ) * , which is equivalently written: A Π (K (u,v) ) * ⊆ B Π (K (u,v) ) * . Also a possibil- ity degree is attached to attribute implication such that A Π (K (u,v) ) * ⊆ B Π (K (u,v) )
* which is all the greater as u and v are greater.

Conclusion

All existing works and approaches pertaining to FCA rely on the use of the classical Galois derivation operator (i.e. sufficiency operator). Thus, these works are based on the complete lattice of all formal concepts obtained using the composition of sufficiency operators. Consequently, induced implications are limited to their conjunctive form. In this paper we propose an approach that enlarges knowledge representation ability to disjunctive attribute implications. Possible links with [12] are to be investigated. The proposed approach considers "open-closed" pairs obtained by means of the asymmetric composition (N • Π) of necessity and possibility operators. We have only focused on composition (.)

NΠ . Further researches should concern the study of other possible compositions of possibilistic composite operators such that (.) Π∆ , (.) ∇∆ , etc.

Introduction

In this paper we deal with Formal Concept Analysis (FCA) and its extensions. FCA is a mathematical formalism having many applications in data mining and knowledge discovery. It starts from a binary table, a so-called formal context (G, M, I), where G is the set of objects, M is the set of attributes, and I ⊆ G×M is a relation between G and M , and proceeds to a lattice of formal concepts [1]. Fuzzy FCA is an extension of standard FCA that allows for fuzzy sets of objects and attributes in order to express uncertainty. Pattern structures is another extension of FCA that allows processing complex data, e.g., graph or sequence datasets. It is a quite general framework and the question if fuzzy FCA can be represented within Pattern Structures and vice versa is still open. In this paper we make a step in this direction and study the connections between pattern structures and fuzzy FCA.

We show how a fuzzy context can be scaled to a "Minimum Pattern Structure" (MnPS), a special kind of pattern structures, that is close to interval pattern structures when considering numerical data. A scaling is needed, since pattern structures deal with crisp sets of objects and, thus, fuzzy extents cannot be expressed within the formalism of pattern structures. For such a kind of scaling we add new objects to the fuzzy context that express objects with uncertain membership in fuzzy sets, allowing expressing fuzzy sets of objects in the formalism of pattern structures. The resulting context is processed by MnPS. This kind of scaling is applicable to fuzzy FCA based on residuated lattices, a special kind of lattices expressing uncertain membership degrees in fuzzy sets. Table 1: A toy dataset of transactions for a supermaket and the related similarity matrix.

(a) A dataset with 5 transactions.

i1 i2 i3 i4 i5 i6 i7 t1 x x x x x t2 x x x x x t3 x x x x t4 x x x t5 x x x x (b) Similarity matrix.
t1 t2 t3 t4 t5 t1 1.000 0.714 0.857 0.429 0.429 t2 0.714 1.000 0.571 0.429 0.429 t3 0.857 0.571 1.000 0.286 0.714 t4 0.429 0.429 0.286 1.000 0.000 t5 0.429 0.429 0.714 0.000 1.000

The rest of the paper is organized as follows. Section 2 describes a running example. Later, in Section 3 we introduce main definitions of fuzzy FCA and pattern structures. The main contribution of this paper is located in Section 4, where we introduce and discuss the scaling procedure of fuzzy FCA to pattern structures. Finally, at the end of the paper we discuss some related works.

Running Example

Let us consider a toy dataset of transactions within a supermarket. It is shown in Table 1a. Every row corresponds to a basket bought by a customer and every attribute corresponds to an item that can be bought in the supermarket. A cross in a cell (i, j) means that in the basket i there is the item j.

For making the example concrete, let us consider a clustering task. When dealing with clustering one typically needs a similarity or a distance measure. Such distance and similarity measures for the purpose of this example could be the fraction of different items shared by two baskets Dist(t 1 , t 2 ) =

|t 1 +t 2 | |M |
and Sim(t 1 , t 2 ) = 1 -Dist(t 1 , t 2 ), where operation '+' between sets is an exclusive OR (a so-called XOR or the symmetric difference, i.e., A+B = (A\B)∪(B \A)). The similarity measure for any pair of transactions is shown in Table 1b. For example, similarity between t 1 and t 2 is equal 0.714. These baskets are different in two items i 4 and i 5 . Thus Dist(t 1 , t 2 ) = 2 7 = 0.286, where 7 is the number of items in the supermarket, and Sim(t 1 , t 2 ) = 1 -Dist(t 1 , t 2 ) = 0.714.

Definitions

Formal concept analysis (FCA) is a formalism for dealing with data mining and knowledge discovery tasks. It starts from a binary context (G, M, I), where G is the set of objects, M is the set of attributes and I ⊆ G × M is a relation between G and M . There are a number of extensions of Formal Concept Analysis (FCA) for dealing with complexity of descriptions, e.g., pattern structures [2], and with uncertainty, e.g., fuzzy FCA [3]. Below we give definitions of this two directions without many details. The interested reader can address the original works on pattern structures and fuzzy FCA for more details and examples.

Fuzzy FCA

Fuzzy FCA works with fuzzy logic instead of crisp-logic, used in standard FCA. There are several generalizations of FCA to the fuzzy case [3]. Here the approach of Belohlavek is considered [4]. In fuzzy logic formulas can be valid up to a certain degree. It means that the formula can be completely valid, completely invalid, or between these two states. This fuzziness in fuzzy FCA is represented by a so-called residuated lattice, where the top of the lattice corresponds to "completely valid" state of the logic and the bottom ⊥ corresponds to "completely invalid" state. Definition 1. A Residuated Lattice is an algebra L = L, ∨, ∧, ⊗, , 0, 1 , where L, ∨, ∧, 0, 1 is a complete lattice; L, ⊗, 1 is a commutative monoid, i.e. ⊗ is commutative, associative, and ∀a(a ⊗ 1 = 1 ⊗ a = a); and ⊗ form an adjiont pair, i.e., a ⊗ b ≤ c ⇔ a ≤ b c.

For the following, L refers to the set of elements of some residuated lattice and L for the residuated lattice itself.

An important residuated lattice based on a linearly ordered set is Göodel residuated lattice, which is used in examples of this paper. In Göodel residuated lattices the fuzzzy implication is defied as following:

a b = a ≤ b b a > b (1)
In the crisp logic the implication → ⊥ is not valid, i.e., → ⊥ = ⊥, while other three possible implications are valid, i.e., → = , ⊥ → = , and ⊥ → ⊥ = . The formula (1) generalizes this behavior. If the premise is less certain than the conclusion, then the implication is valid ( ), otherwise the validity of the implication is equal to the certainty of the conclusion.

In Definition 1 it is required that the fuzzy implication is adjoint (related) with an ⊗-operation. For Göodel residuated lattices the fuzzy implication is adjoint with a ⊗ b = min(a, b).

A fuzzy dataset is encoded by means of a fuzzy context as defined below. Let us now define what is a fuzzy set, the next building block of fuzzy FCA.

Definition 4. Given a crisp set X, a fuzzy set A is a function A : X → L, mapping each element of the crisp set to an element of the residuated lattice. A fuzzy set is denoted as { li∈L / xi∈X }, where x i = X, and for simplicity elements A(x ∈ X) = ⊥ are omitted.

In the fuzzy case of FCA one also defines Galois connections between a fuzzy set of objects A : X → L and a fuzzy set of attributes B : Y → L.

Definition 5 (Derivation Operators). Given a fuzzy context (X, Y, I), a fuzzy set of objects A : X → L, a fuzzy set of attributes B : Y → L, the fuzzy membership for object x ∈ X and for attribute y ∈ Y in the corresponding sets A ↑ and B ↓ are as follows: In particular there is the following fuzzy concept.

A ↑ (y) = ∀x∈X (A(x) I(x, y)) B ↓ (x) =
{ 1.0 / t1 , 1.0 / t2 , 0.286 / t3 }, { 0.714 / t1 , 0.714 / t2 , 0.571 / t3 , 0.429 / t4 , 0.429 / t5 } .

The set of fuzzy concepts is ordered such that (A, B) ≤ (X, Y ) iff A ⊆ X (or dually B ⊇ Y ) forming a complete lattice, called fuzzy concept lattice.

Pattern Structures

A concept lattice L(G, M, I) is constructed from a (binary) formal context (G, M, I) [1]. For non-binary data, such as sequences or graphs, lattices can be constructed in the same way using pattern structures [2]. Derivation operator for a pattern structure (G, (D, ), δ), relating sets of objects and descriptions, is defined as follows:

A := g∈A δ(g), for A ⊆ G d := {g ∈ G | d δ(g)}, for d ∈ D
Given a subset of objects A, A returns the description which is common to all objects in A. Given a description d, d is the set of all objects whose description subsumes d. The natural partial order (or subsumption order between descriptions) on D is defined w.r.t. the similarity operation : c d ⇔ c d = c (in this case we say that c is subsumed by d). The set of all pattern concepts is partially ordered w.r.t. inclusion of extents or, dually, w.r.t. subsumption of pattern intents within a concept lattice, these two anti-isomorphic orders form a lattice, called pattern lattice.

Let us return to the example in Table 1b. Let us consider a special case of pattern structures, a so-called Minimum Pattern Structure (MnPS), that is close to interval pattern structures [5]. MnPS is based on the minimum of two numbers as the similarity operation rather than on the convex hull of two intervals. We will show that MnPS is well adapted for formalizing fuzzy FCA within the framework of pattern structures.

In Table 1b we have the set G as both, a set of objects and a set of attributes. Let us first consider only one attribute. Then the set of descriptions D is just the interval [0, 1] of real numbers and the similarity operation between two descriptions (numbers) is the minimum. When there are several attributes, the set of descriptions is just an element of R |N | , where R is the set of real numbers and N is the set of numerical attributes.

In particular, in our example the set of objects is G. The set D of descriptions is R 5 , since we have 5 numerical attributes. The mapping function δ is given in Table 1b, e.g., δ(t 2 ) = 0.714, 1, 0.571, 0.429, 0.429 . The similarity operation is the component-wise minimum, e.g., the similarity between descriptions of t 2 and t 3 is given by Let us now discuss a possible connection between fuzzy FCA and pattern structures. A certain connection was already proposed in [6]. In particular, every crisply closed subset of objects is an extent of an interval pattern structure.

Here, crisply closed subset of objects means that the fuzzy closure of this set contains no additional objects g with a membership degree coinciding with the top of the residuated lattice, i.e., A(g) = .

Here, we discuss a loss-less scaling from a fuzzy formal context (X, Y, I) to a pattern structure, that allows a more efficient processing than the loss-less scaling to crisp formal context and highlights another connection between fuzzy FCA and pattern structures. Since pattern structures can deal with any kind of descriptions, they should take into account fuzziness on the intent side. However, for the extent side it is not so straightforward, since pattern structures deal only with crisp sets of objects. Accordingly, we should somehow "scale" object sets, in order to express fuzzy sets of objects.

On expressing Fuzziness on the Extent Side of Pattern Structures

A natural way is to scale the object set X from a fuzzy context (X, Y, I) by substituting it with the direct product of the crisp set of objects and the residuated lattice (the degrees of confidence), X × L. For every scaled object from this new set, we should compute a description. Let us consider the scaled description for the pair x, l , where x ∈ X is an object and l ∈ L is the membership degree of this object. The description of this element should correspond to the description of the fuzzy set { l / x }, since x, l is "a model of" this fuzzy set. The derivation operator { l / x } ↑ (y ∈ Y ) = { l / x }(x) I(x, y) = l I(x, y) gives the description of the element x, l and allows computing the fuzzy relation Ĩ between X × L and Y .

Let us return to our example. Let T be the set of transaction IDs. The scaled fuzzy context is partially shown in Table 2. It consist of |T | • |L| = 5 • 7 = 35 objects, 5 attributes and the fuzzy relation between them. Every subset of objects corresponds to a fuzzy set of objects by joining corresponding fuzzy representation for every object. This is made precise in the next subsection.

Relation between fuzzy and pattern extents and intents

Let (X, Y, I) be a fuzzy context with a residuated lattice L and (G, D, δ) be a pattern structure, where G is the scaled set of objects G = X × L. Let us formally define the correspondence between fuzzy sets of objects and scaled sets of objects.

Definition 9 (Object sets equivalence). A fuzzy object set

A : X → L is equivalent to a scaled object set N ⊆ G, denoted as A ∼ N , when (∀ x, l ∈ G)(A(x) ≥ l ⇔ x, l ∈ N )
Then object sets are equivalent when all scaled objects with membership degree smaller than or equal to A(x) (w.r.t. the residuated lattice) are present in the scaled object set. For example, the fuzzy set { 0.286 / t1 , 0.429 / t4 } is equivalent to the scaled set { t 1 , 0.286 , t 4 , 0.429 , t 4 , 0.286 }3 , where g, l ∈ X × L is an element of the direct product of the set of objects and the residuated lattice.

Given a scaled fuzzy context (X × L, Y, Ĩ) we can process it as a minimum pattern structure (X × L, D, δ), where D = L |Y | is a tuple of elements from the residuated lattice L and the semilattice operation is given by the componentwise infimum of L. In particular, we have discussed that for the numerical case, the similarity operation is the component-wise minimum. Indeed, fuzziness on the extent side is expressed by means of scaled object sets, and fuzziness on the intent side is directly processed by the pattern structure. Let us discuss the correspondence between fuzzy intents and patterns. A fuzzy attribute set B is equivalent to a pattern d iff for any attribute y ∈ Y , the membership degree B(y) in the fuzzy set is equal to the value in the pattern tuple in the position corresponding to the attribute y, e.g., the pattern 0.5, 0.7 corresponds to the fuzzy set { 0.5 / y1 , 0.7 / y2 }.

It should be noticed that the definition of equality between fuzzy sets of attributes and patterns is a bijection, while there are scaled sets of objects that have no equivalent fuzzy set of objects. Indeed, there is no equivalent fuzzy set to the scaled set { t 1 , 0.286 , t 4 , 0.429 }, since according to Definition 9 all x, l such that A(x) ≥ l should be in this set. And since we have t 4 , 0.429 in this set, we should also have t 4 , 0.286 in the set. We can notice here that in our particular example the residuated lattice has only the element 0.286 that is smaller than 0.429. By contrast, if we take the real interval [0, 1], then all points smaller than 0.429 should be added to the scaled set.

Let us define equivalence classes of scaled sets of objects in order to have a bijection between the equivalence classes and the fuzzy sets of objects.

Definition 11. A scaled object set N ⊆ G is complete iff a scaled object x ∈ X, l ∈ L belongs to N , then (∀l * ∈ L, l * ≤ l) x, l * ∈ N .
It can be checked that for any scaled object set N ⊆ G there is only one minimal complete superset of N . Let us denote this complete set by φ(N ).

For example, the set N = { t 1 , 0.286 , t 4 , 0.429 } is not complete, since the scaled object t 4 , 0.286 is not in N .

By contrast, N c = φ(N ) = { t 1 , 0.286 , t 4 , 0.429 , t 4 , 0.286 } is complete. Moreover, it can be seen that this set is equivalent to { 0.286 / t1 , 0.429 / t4 } according to Definition 9. Furthermore, it can be checked, that any complete scaled set of objects is equivalent to a fuzzy set and accordingly the function φ(•) defines the required equivalence classes.

Thus an object x, l ∈ G is included in d iff B ↓ (x) ≥ l which is the definition of the equality of a fuzzy set of objects and a scaled set of objects.

Theorem 1 The fuzzy lattice L f corresponding to the context (X, Y, I) and the pattern lattice L p corresponding to the pattern structure (G, D, δ), where G = X × L, D = L |Y | with component-wise minimum as the semilattice operation, and δ( x ∈ X, l ∈ L )(y) = l I(x, y) are isomorphic. The extents and intents of the corresponding concepts are equivalent.

Proof. Let us show, that for any concept in one lattice there is a concept in the other lattice with equivalent extents and intents. Lemmas 2 and 3 are symmetric w.r.t. the type of extents and intents. Accordingly, we can just denote by L 1 and L 2 fuzzy and pattern lattices and prove the theorem in both directions. If we take an intent i 1 from L 1 , we can always find an equivalent pattern p (for simplicity, fuzzy set of attributes is also referred as a pattern). Applying appropriate derivation operators to i 1 and p we get equivalent sets of objects according to Lemma 3. Both sets are closed and are extents of L 1 and L 2 . Applying derivation operators to the extents we get equivalent intents according to Lemma 2. Thus, for any concept of L 1 there is an equivalent concept in L 2 and vice versa.

Application of the Theorem

Let us demonstrate how the theorem works in the running example. The proof is based on search of concepts with equivalent extents and intents. Let us find the scaled concept corresponding to the fuzzy concept (2). In the theorem we start from the intent. It can be seen that { 0.714 /t 1 , 0.714 /t 2 , 0.571 /t 3 , 0.429 /t 4 , 0.429 /t 5 } ∼ 0.714, 0.714, 0.571, 0.429, 0.429 . (3)

For the moment we are not sure that the pattern on the right side is an intent. Accordingly we apply derivation operators to the left and right hand sides and according to Lemma 3 the resulting object sets should be equivalent. Indeed,

{ 1 /t 1 , 1 /t 2 , 0.286 /t 3 } ∼ ∼ { t1, 1 , t1, 0.857 , . . . , t1, 0.286 , t2, 1 , . . . t2, 0.286 , t3, 0.286 }.
On the left side we have the extent of the concept, while on the right side we have a closed scaled set of objects, since the result of the derivation operator is always closed. If we apply the derivation operators to these two sets of objects, we have equivalent patterns according to Lemma 2. In fact we have exactly the patterns from (3). Thus, we have found the scaled concept corresponding to the fuzzy concept. Similarly, we can start from a scaled concept and find the corresponding fuzzy concept.

Discussion and Conclusion

In this paper we highlighted the relation between fuzzy FCA and pattern structures. Our result is related to the work of [6]. Indeed, the authors have shown that extents of crisply closed fuzzy concepts are also closed in the interval pattern structure. In our work, we used the Minimum Pattern Structure that can be considered as a projection of the interval pattern structure. Indeed, let us consider the following component-wise projection. If [a, b] is an interval, than the projection ψ([a, b]) = [a, + inf] changes the IPS to the MnPS. Accordingly the set of extents of the MnPS is the subset of the extents of the IPS. However, in our work we have shown, that the MnPS lattice is isomorphic to a fuzzy lattice under the scaling. It can be seen, that if we do not apply the scaling we generate exactly the lattice of the crisply generated fuzzy concepts. And this set of concepts is the subset of the concepts of the corresponding IPS.

The introduced scaling procedure can be useful, first, for migrating results between pattern structure community and fuzzy FCA community, and, second, for efficient implementation of software dealing with both pattern structures and fuzzy FCA at the same time.

Finally, we notice that such a work naturally raises (as it was already mentioned in [6]) the question of a "two-sided" pattern structure as a generalization of both pattern structures and fuzzy FCA. Some suggestions going in this directions can be found in the work of Soldano et al. [7], where the authors discussed projections applied to the extent side.

Introduction and related work

Event-related data can have the form of a succession of actions or events in chronological order. Data mining of such data has many applications in fields such as security (intrusion detection [1]), marketing (e.g. navigation in e-commerce hierarchy) or ergonomy (study of succession of actions in work-related applications). Those applications require the search of some meaningful patterns in the data. A pattern is a structure that appears with regularity in the data. It can be an itemset, a sequence, a sub-word, an association rule... In this context, meaningful means maximizing some metric, such as the support or the lift. Different algorithms exist to mine either of those. An interesting property for patterns is the closure. A pattern p is closed if there is no pattern p , superset of p and support(p) = support(p ). Formal Concept Analysis (FCA) is a mathematical framework that deals with closed sets. Many algorithms from FCA allow to enumerate closed sets (in the form of concepts) and there exist a number of interesting metrics based on concept lattices such as stability or robustness of a concept.

The enumeration of these patterns alone is not sufficient in many cases and is only one step of a decision-making process. For example, in a context of security, one might want to find meaningful patterns as the first step of classification or prediction. In marketing, one might use patterns to construct groups of consumers or to find interesting association rules.

In [2,3], the authors introduce a tool for classification in the binary case, based on positive and negative examples in concept lattices. However, by using this binary classifier to the 1n case (n being the number of classes), all anonymous behaviours will be classified as contradictory. Other works of mining in FCA include the mining of sequences in [4] and of graphs in [5]. In [6], the authors defined emerging patterns as patterns appearing frequently in a class, but being hard to find in other classes. Confer [7,8] for surveys on emerging patterns. An emerging closed-pattern classifier can be described as an extension to the 1n case of the binary concept lattice classifier, and can be used to predict the class on previously unseen objects. In [9], the authors present another generalisation to n classes of the closed-set based classifier. In particular, the authors introduced the use of the tf × idf for the selection of the closed patterns.

In this paper, we present a tool for classification of sequential data, based on closed-patterns. This tool implements the classifier presented in [9]. We show some results of our tool on a dataset of web navigation logs from more than 3000 users over a six-month period.

This paper is organised as follow: in section 2 we explain the functioning of the classifier and give more details about the tool and its parameters, in section 3 we show a case study and propose a clean dataset for experimentation, finally we conclude and give some perspectives of our work.

Implementation

General parameters

In this section, we describe the classifier implemented by our tool. The tool includes a whole experimental process, from the building of transactions from raw data to detailed results of classification. We mention some of the parameters accepted by each steps.

Building transactions Our tool allows us to group the data into transactions. The transactions can be of fixed size, or created with respect to a time stamp present in the original data. In our case study, the size is fixed and is equal to 10. The data file from where the transactions are built can be of arbitrary size.

Extraction of own patterns

We call own patterns the patterns we believe to be respresentative of each class. For each class, we compute the patterns that verify some property or threshold for a given metric (e.g. support or tf × idf ). With some metrics, the space of those patterns is prunable. The number of patterns we want to keep as well as their maximum size is a parameter. The nature of the pattern is also a parameter: as of today, one can choose between closed itemset or sequence. For a given class c, we denote the set of own patterns by P c .

Profile of a class There exist different ways to compute the profile of a class. In our tool, we chose to define a common vector profile V = c∈C P c that is the union of all own patterns for all classes. We then compute its numerical components for each classes from either the support, the lift or the tf × idf . This vector allows us to embed all classes in a common space. This numerical value can be seen as the distance from the origin of the space, in each dimensions of the vector. For exemple, let α and β two classes. P α = {A, B, C} and P β = {C, D, E} then the vector V = P α ∪ P β will have 5 component (A, B, C, D, E). For each class c, we compute a numerical value k c i for each component, giving

V α = (k α A , k α B , k α C , 0, 0) and V β = (0, 0, k β C , k β D , k β E ).
Profile of an anonymous transaction This step accepts the same parameters as the construction of the profile of a class. We can also choose the number of anonymous transaction that will be submitted to the classifier in the next step. For example, in Fig. 3, the number of anonymous transactions recieved by the classifier goes from 1 to 30.

Identification step

The goal is to guess the class corresponding to an anonymous set of transactions. After the computation of a profile for this anonymous set, we compute the nearest neighbor in the common space defined previously. The tool implements different similarity functions: euclidean distance, cosine similarity, Kulczynski measure, and Dice similarity. The heuristics gain in efficiency when they are provided with a higher number of anonymous transactions that allows them to construct a finer profile for the anonymous user.

Global parameters Other parameters for experimentations include the number of runs, the verbosity level, the format of the data, the possibility to only compute stats on the data, the use of a fuzzy approach and some parameters for binary classification.

Bayesian Classifier Our tool implements two smoothed Bayesian classifiers: a traditional Bayes classifier and a pattern-based Bayes classifier. Those classifiers allow to compare the results during the experimentations.

Fuzzy approach

The inclusion of a pattern in a transaction is a binary measure. When working with own patterns of significant size, this strict inclusion will often be false. We consider a fuzzy approach for the support during the computation step of an anonymous profile. We will use a inclusion level instead of a binary measure. The fuzzy support may then be computed as the average of the inclusion levels on the set of transitions. The fuzzy inclusion level inc(P, T ) can be computed as the proportion of the own pattern P included in the transaction T :

inc(P, T ) = ||P ∩ T || ||P || (1)
To adjust to different cases and be able to represent a wide range of inclusion, from intersection to strict inclusion, we use a transfer function to transform the simple level of inclusion of eq. 1. In the tool, those functions are defined by specifying points on a 2-dimensional space. Two points are fixed, (0, 0) and (1, 1). Some transfer functions are illustrated in Fig. 1. The coordinates of the two points that define the transfer function are configuration parameters. In Fig. 1, the parameters for the inclusion are [(1, 0); (1,0)]. This is equivalent to the binary measure of inclusion. For the intersection, the parameters are [(0, 1); (0, 1)]. Those parameters mean the measure is equal to one as soon as the intersection is not empty. For the simple ratio or a more sigmoidal function, the parameters are resp. [(0, 0); (1, 1)] and [(0.25, 0); (0.75, 1)].

Configuration file

The parameters are given to the tool by a configuration file in .yml format. For the results of our case study, presented in Table 2, the file is presented in Fig. 2.

With this file as argument, the tool will recieve from 1 to 30 anonymous transactions, and run 10 executions. The random seed can be fixed to reproduce experimentations. The data comes from the directory Data/150users, and is in csv format. The transactions are built of fixed size 10. The identification method is H 1 (closed itemsets and tf × idf metric), with at most 40 own closed-patterns of maximum size 5. The similarity measure used is Kulczynski. The profiler is the metric used to compute the numerical coordinate of the common vector. When not specified, the method used for inclusion of the pattern is the strict inclusion.

--name : H1 on csv data verbose -level : WARNING number -of -categories : is to recognise a user amongst n. The classifier has to guess the corresponding user from an anonymous behaviour. If it fails to recognise the declared user, then the identity is not confirmed. In a security context, this situation can lead to restrictions in the system, or to the request of some explicit means of identification. The parameters used in this study are detailed in the configuration file of Fig. 2.

Data description

Our data comes from Blaise Pascal university proxy servers. It consists of 17×10 6 lines of connection logs from more than 3, 000 users and contains the user ID, the time stamp and a domain name for each line. We applied two types of filters on the domain names: blacklist filters and HTTP-request based filters. We used some lists3 of domain names to remove all domains regarded as advertising. We also filtered the data by the status code obtained after a simple HTTP request on the domain name. After those steps, we still have 4 × 10 6 lines. We divide the file between the 3K users to obtain the class files. This dataset is available at http://fc.isima.fr/∼kahngi/cez13.zip. The studies were conducted on the 150 users with the higher number of requests.

Some information about the data is available in Table 1. The table shows some statistics from before preprocessing and after the filters were applied. #U sers represent the number of users, #Sites represents the cardinal of the whole set of websites for all users and Avg#lines/user is the average number of line per user. We can see that the number of users decreases because some users did not have a single line after the filters. Roughly 40% of the websites were deleted by the filters, and the average number of lines by user was divided by 5. [9] show that tf × idf produces better results than the lift or the support. Figure 3 shows the kind of results that can be obtained with our tool. The abscissa is the number of anonymous transactions given to the classifier and the ordinate the accuracy of the different heuristics. The dataset is divided as follows: 2 3 of learning base for the learning step and 1 3 for the identification step. The division is random. Each test session consists of multiple runs of both those steps. That allows us to smooth the results by using the average accuracy. The table generated by our tool contains 15 columns. Those include the number of classes N C , the number of anonymous transactions recieved A, the method used, the average accuracy, the average number of transactions successfully and not successfully classified, the ratio of classified and not classified tests, and the run time in second. T C represents the ratio of classified tests. All this information allows the analysis of various aspects of the result. Some are presented in Table 2.

Conclusion and perspectives

We presented a tool for classification of sequential data. It includes a lot of features in the construction of the transactions, and different parameters and heuristics for classification. The tool is flexible and adaptable to many contexts of classification and types of data. The perspectives of our work are to add others means of classification based on other types of patterns (such as closed-sequences, pattern structures, or class association rules), and other types of metrics (for example structural metrics such as stability). We are also considering the use of aggregation functions other than the average for fuzzy support, such as ordered weighted averaging (OWA) operators [15,16], or some power-means. Moreover, we are considering the integration of different paradigms of user profiles. Another way to construct the profile of a class is using association rules. Class association rules are association rules of the form A → C where C is a class and A a subset of items. They are studied in [17]. By attributing scores to the rules and searching for the premisses of the rule in an anonymous transaction, we could classify the anonymous transaction in a given class.

Interval Pattern Concept Lattice as a Classifier Ensemble

Yury Kashnitsky, Sergei O. Kuznetsov

National Research University Higher School of Economics, Moscow, Russia {ykashnitsky,skuznetsov}@hse.ru Abstract. Decision tree learning is one of the most popular classification techniques. However, by its nature it is a greedy approach to finding a classification hypothesis that optimizes some information-based criterion. It is very fast but may lead to finding suboptimal classification hypotheses. Moreover, in spite of decision trees being easily interpretable, ensembles of trees (random forests and gradient-boosted trees) are not, which is crucial in some domains, like medical diagnostics or bank credit scoring. In case of such "small, but important-data" problems one is not obliged to perform a greedy search for classification hypotheses, and therefore alternatives to decision tree learning techniques may be considered. In this paper, we propose an FCA-based classification technique where each test instance is classified with a set of the best (in terms of some information-based criterion) classification rules. In a set of benchmarking experiments, the proposed strategy is compared with decision tree and nearest neighbor learning.

Introduction

The classification task in machine learning aims to use some historical data (a training set) to predict unknown discrete variables in unknown data (a test set). While there are dozens of popular methods for solving the classification problem, usually there is an accuracy-interpretability trade-off when choosing a method for a particular task. Neural networks, random forests and ensemble techniques (boosting, bagging, stacking etc.) are known to outperform simple methods in difficult tasks. Kaggle competitions also bear testimony for thatusually, winners resort to ensemble techniques, mainly to gradient boosting [13]. The mentioned algorithms are widely spread in those application scenarios where classification performance is the main objective. In Optical Character Recognition, voice recognition, information retrieval and many other tasks typically we are satisfied with a trained model if it has a low generalization error.

However, in lots of applications we need a model to be interpretable as well as accurate. Some classification rules, built from data and examined by experts, may be justified or proved. In medical diagnostics, when making highly responsible decisions (e.g., predicting whether a patient has cancer), experts prefer to extract readable rules from a machine learning model in order to "understand" it and justify the decision. In credit scoring, for instance, applying ensemble techniques can be very effective, but the model is often obliged to have "sound business logic", that is, to be interpretable [10].

In what follows, we introduce some notions from Formal Concept Analysis (FCA) [5] and provide a technique to express decision tree learning in terms of a search for a hypothesis in a concept lattice (section 3). In section 4, we propose an algorithm which by its design guarantees that each test object is classified with a better (in terms of some criterion such as information gain or Gini impurity) rule than in case of applying a decision tree. Finally, we discuss the results of the experiments with several popular datasets (section 5), make conclusions and directions of further work on developing the performed ideas.

Pattern Structures and Projections

Pattern structures are natural extension of Formal Concept Analysis to objects with arbitrary partially-ordered descriptions [4]. As in classical FCA, pattern concepts form a pattern concept lattice. In case it is too computationally demanding to build the whole lattice, projections are used to simplify object descriptions and boost the formation of a pattern concept lattice. Definition 3. A projection [4] of a semilattice (D, ) is a kernel function ψ : D → D, i.e ∀x, y ∈ D :

x y ⇒ ψ(x) ψ(y) (monotonicity) ψ(x) x (contractivity) ψ(ψ(x)) = ψ(x) (idempotence)

3 Interval Pattern Structure Projections

The theoretical part of the proposed approach is based on Formal Concept Analysis and pattern structures, in particular, on Interval Pattern Structures [6] that provide a way to apply FCA techniques to data with numeric attributes. Unfortunately, the size of the concept lattice is usually too large to be used efficiently in learning [11]. Hence, we introduce a so-called discretizing projection on interval pattern structures which helps to build more general object descriptions based on numeric attributes.

i ] i∈[1,m] ) = [max{τ | τ ∈ T i ∪ {-∞, +∞}, τ ≤ a i }, min{τ | τ ∈ T i ∪ {-∞, +∞}, τ ≥ b i }] is called a discretizing projection of a semilattice (D, ).
The discretizing projection, as defined in Def. 4, is a projection according to the definition Def. 3.

Example 1. Consider a toy dataset with only 4 objects and 1 numeric attribute as shown in Fig. 1 (left). In order to apply decision tree learning for some classification task with this dataset, one would apply some discretization method to produce binary attributes from attribute a. Consider the discretization shown in

f + i = |d i ∩ c train | |d i | rtest[i] = {di → f + i } i∈[1,n rules ] ctest[i] = [ n_rules i=1 f + i ≥ fpos * n_rules] end for
In case of a classification task with numeric attributes we apply the same Algorithm 1 for interval pattern structures. To make it tractable, we apply it to projections ψ(P S train ) and ψ(P S test ) of a training and a test interval pattern structure. Here ψ(P S), is a discretizing pattern structure projection as defined in Def. 4.

Experiments

We compare the proposed classification algorithm (denoted as "CoLiBRi" for "Concept Lattice-Based Rule-learner") with Scikit-learn [12] implementations of CART [2], Random Forest [1] and kNN on several datasets from the UCI machine learning repository. We used Gini impurity as a criterion for rule selection and MDL [3] for continuous feature discretization. CART, Random Forest and kNN parameters (min_samples_leaf ∈ [1,10] for tree-based algorithms and k ∈ {1, 2, 5, 15, 30, 50} for kNN) were chosen in stratified 5-fold cross-validation. We built 10 trees for each instance of Random Forest classifier.

Parameter min_supp for "CoLiBRi" was taken equal to CART's min_samples_leaf for each dataset. We used n = 10 classification rules to vote for a test instance label. The described algorithms were implemented in Python 2.7.3 and run on a 4-CPU machine with 4 GB RAM.

The results are presented in Table 1. Each entry stands for the average metric (accuracy or F1-score) in 5 runs of 5-fold cross-validation. In the table, the algorithm with the best performance on each metric is boldfaced. Other algorithm's whose performance is not statistically distinguishable from the best algorithm at p = 0.05 using paired t-tests on the 5 runs are *'ed. The best parameters for each algorithm are mentioned in Table 2.

As it can be seen, the proposed approach performs better than CART and is statistically indistinguishable from RF on most of the datasets. Surprising enough, kNN seems to be the best-performer (on average over all datasets) in terms of accuracy but not F1-score.

Conclusions and further work

In this paper, we have shown how searching for classification hypotheses in a formal concept lattice may yield accurate results while providing interpretable classification rules.

Further we plan to test the proposed strategy in classification tasks such as predicting biological activity (toxicology, mutagenicity, etc.) and telecom client satisfaction where objects have complex descriptions (graphs and sequences correspondingly).

We also plan to introduce some randomization in mining rules for each test instance (as it is done with random forests) in order to further improve the classification quality.

Introduction

The volume of data stored in the web has undergone a significant and a continuous evolution. Several efforts focused therefore on knowledge retrieval (extraction) from data. In [4], the knowledge extraction from data is defined as an acquisition of new knowledge, which is potentially useful, from the hidden facts within great amounts of data. One of the main processes of the knowledge extraction is based on data mining. This operation collects several tasks such as prediction, clustering and supervised classification. The latter can be performed by methods based on neural networks, decision trees, nearest neighbor, support vector machines or Formal Concept Analysis (FCA). Several reasons lead to use the classification method based on FCA, among them the ability of formal concepts to process a significant quantities of data and to simplify the prediction of classes [17].

Supervised classification based on FCA consists in building functions or models called classifiers from data to predict classes for future data. It aims at extracting the classification rules based on the concepts generated previously from data [19,21].

The whole process is performed in two main steps: a training step where a classifier is built to describe a predetermined set of object classes from a training set. A classification step where trained classifiers are used to assign a class to each new object. In this paper, we focus only on supervised classification based on FCA. Particularly, we propose a new taxonomy of classification methods based on FCA. The paper is organized as follows : we present basic notions related to FCA in Sect. 2. Sect. 3 describes new taxonomy of supervised classification methods. In Sect. 4, we make a comparative study of such methods.

Formal Concept Analysis

Originally, FCA is conceived by R.Wille as a "restructuring" of abstract lattice theory, i.e., making it closer to the needs of other branches of science. FCA represents a theoretical background for many applications in computer science. It covers various fields such as linguistics, information retrieval, text mining, knowledge representation and more recently knowledge extraction.

A formal context is represented as a triplet K = (G, M, I) witch relies a finite set of objects G to a finite set of attributes M using binary relation I (I⊆ G × M ) [7]. A formal context can be illustrated by a two-dimensional table where objects are presented by lines and attributes are presented by columns. All possible formal concepts are extracted from a formal context K = (G, M, I). In fact, a formal concept is represented by a pair (A, B) such that A ⊆ G and

B ⊆ M , A ′ = B and B ′ = A where A ′ = {m ∈ M | (g,m) ∈ I ∀ g ∈ A}, i.e.
the set of attributes common to all objects in A, and B ′ = {g ∈ G | (g,m) ∈ I ∀ m ∈ B}, i.e. the set of objects which have all attributes in B. A and B are called, respectively, extent and intent of the concept (A, B) [7]. The set of all concepts can be organized as a complete lattice of formal concepts, called Concept Lattice [7].

Supervised classification based on Formal Concept Analysis

Classification methods based on FCA uses either what we call exhaustive or combinatory approaches. In this section, we describe in detail the approaches and we give an overview of existing methods for each approach.

Exhaustive classification approach

Exhaustive methods are characterized commonly by the use of one single classifier. However, they vary between them according to the criteria used on concepts selection and the size of lattices outlining formal concepts. We distinguish overall methods based on complete lattices and others based on sublattices [21]. Among the works that have focused on the classification using a complete lattice as research space, we can cite GRAND [20], RULEARNER [START_REF] Sahami | Learning classification rules using lattices[END_REF], GALOIS [2], CBALattice [8], NAVIGALA [START_REF] Visani | Navigala: An original symbol classifier based on navigation through a galois lattice[END_REF], HMCS-FCA-SC [5] and SPFC [9].

These methods carried out the validation of the characteristics associated to each concepts in the lattices level by level. The navigation in the lattice of concepts starts from the minimal concept where all the concepts of the lattice are considered as candidates without having an idea on their validity.

GRAND 3 and GALOIS are the first methods which use complete lattices of formal concepts. They build a complete lattice using an incremental algorithm and it updates the lattices by adding new nodes and removing redundant connections. Then, GRAND chooses the more specific rules to be applied for each object [20].

GALOIS also builds a complete lattice in an incremental and ascending way. In the classification step, the system computes the similarity between new object and each concept. The similarity between an object and a concept is the number of common attributes verified by the object [2].

Other classification systems based on FCA are developed following GRAND such as RULEARNER and NAVIGALA. NAVIGALA 4 uses an object context described by numerical vectors of fixed size. These vectors are stored in a discrete table which then becomes binary [START_REF] Visani | Navigala: An original symbol classifier based on navigation through a galois lattice[END_REF]. RULEARNER, in a similar setting, uses a complete concept lattice as a research space in classification rules. During the classification, it uses majority voting to determine the classes of new objects [START_REF] Sahami | Learning classification rules using lattices[END_REF].

CBALattice builds a complete lattice and applies association rules to extract classification rules. The method is incremental and progressive. Every increase in the number of objects, attributes, and classes can be handled efficiently [8].

HMCS-FCA-SC 5 also uses a complete lattice and existing information in formal concepts. However, unlike CBALattice, it aims to create a model of hierarchical classification. In addition of that, HMCS-FCA-SC employs a cosine measure 6 between new example and the selected concepts for classification [5].

After the construction of the lattice, SPFC 7 assigns to each concept a score which indicates the relevance degree of the concepts. Then it looks for neighbors of relevant concepts. The unknown objects will be classified in the classes of their neighbors [9].

The limit of the methods based on complete lattice consists in the exponential complexity of their training algorithms in terms of time and memory resources.

In order to overcome this problem, other efforts such as LEGAL [15], CIBLE [19], CLNN & CLNB [START_REF] Xie | Concept lattice based composite classifiers for high predictability[END_REF], IPR [16], CLANN [START_REF] Tsopzé | Clann: Concept lattice-based artificial neural network for supervised classification[END_REF] and CITREC [3], MCSD-FCA-PS [1] use sublattices instead of complete lattice as search space. A sublattice of concepts is a mathematical structure which represents a part of the concept lattice in a selective way [7]. LEGAL 8 is a method which relies on several training parameters to build a sublattice. During the learning step, it builds an ordered set of concepts based on the class of each instance. The positive and negative instances are the instances labeled by a positive or negative class in the formal context. During classification Legal applies the majority vote [15]. CIBLE 9 operates in two succeeding steps: it starts with the construction of a sublattice from a binary context then it uses a similarity measure for the classification of new objects [19].

CLNN & CLNB 10 methods build a sublattice in a decreasing way. They incorporate then respectively a Naive Bayes classifier and a Nearest Neighbors [START_REF] Xie | Concept lattice based composite classifiers for high predictability[END_REF].

Another classification system CITREC which uses sublattices is proposed in [3]. CITREC builds the lattice starting from a reduced context containing only a representative object of each class [3]. In the classification step CITREC uses the majority vote in the same way as the methods CLNN & CLNB.

On the other side, CLANN 11 starts by building a sublattice in the training step and processes data which have only two classes. It uses then straightforward sublattice to build a neural networks which makes the classification [START_REF] Tsopzé | Clann: Concept lattice-based artificial neural network for supervised classification[END_REF].

MCSD-FCA-PS 12 has the distinction of processing sequential data. Complex sequential data are mapped onto pattern structures whose projections are used to build a pattern concept lattice. In fact, pattern structures are a generalization of formal concept analysis designed to deal with complex objects descriptions when an object is not associated to a set of attributes. MCSD-FCA-PS select relevant patterns that can be used for the classification step [1,13,12].

IPR 13 is a method which introduces the coverage of concepts. It selects from the lattice all the relevant concepts which can help to better classification. The choice of relevant concepts is based on greedy algorithm [16]. Then to classify each new object, IPR searches rules with a premise that coincides with the object attribute. The applied rules are the most weighted rules for the involved object.

The classification methods based on sublattices proceeds in the same way as methods based on complete lattices. However, using sublattices can reduce the substantial number of generated rules and keep the most relevant among them. Such proceeding leads to reduce significantly the training time, however it causes a loss of information.

Several drawbacks are observed in exhaustive methods described above. In fact, besides to the high complexity, using one single weak classifier may not be the best solution for classification. The use of many classifiers can give better results. Subsequently, the researchers move towards the integration and the use of combinatory classification methods which are based on the ensemble methods in order to improve other operations of a low single classifier (a single learner).

Combinatory classification approach

Unlike exhaustive methods which use one classifier, combinatory methods employs many classifiers which are then combined by the techniques of votes.

In this context, various methods have been proposed among them there are methods based on sequential training like BFC [18], BNC [17] and methods based on parallel training such as DNC [17], FPS-FCA [14] and RMCS [10].

The sequential training consists in generating classifiers sequentially. In other words, a classifier is generated only after the generation of its predecessor. For example, BFC 14 builds from a formal context a cover formed only by relevant concepts. The latter is based on boosting which is an adaptive approach based on the use of several classifiers of the same model [11]. These classifiers use voting techniques in order to classify correctly the objects wrongly classified. The idea of BFC consists in assigning, initially, equal weights for the training examples among them subset is selected randomly. At this point, a relevant concept is extracted from a subset by selecting the attribute which minimizes Shannon entropy 15 . BFC generates then a classification rule deducted from the relevant concept (extracted from subset) and updates the weights of training examples. This process is rebuilt recursively to produce the final classifier [18].

The method BNC 16 proceeds similarly to BFC method in generating classifiers and processing training data. However, unlike BFC which makes the processing of binary data, BNC handle nominal data in order to avoid the loss of information following the binary data representation [17].

The parallel training is based on Dagging [11], it consists in dividing data set into many groups. Classifiers are generated from the groups. DNC 17 method handles nominal data. DNC algorithm proceeds as follow: a random data is run in order to create a disjoint groups containing stratified data. A classifier of nominal concept [17] is then created for each group. Finally, the method defines as output a combination of classifiers made by a vote technique [17].

FPS-FCA 18 is a symbolic classification method based on Pattern structures and FCA, witch deal with complex input objects like logical formulas, graphs, strings and tuples of numerical. In presence of large data sets, it offers natural approximation tools (projections) and achieves classification in a parallel way by dividing the initial data set [14,13,6,12].

RMCS 19 generates a set of classifiers parallely. It allows to create a classifier based on its neighbors. The classifier realizes correctly the object classification when it is classified correctly within its neighbors. RMCS starts with the construction of a classification table from a formal context. In this table, RMCS matches a set of classifiers to the objects set existing in the context. Then, RMCS looks for the neighbors of the test set of objects using a metric of similarity and selects classifiers that have the maximum number of neighbors found. The selected classifiers are then recommended for classification [10].

Discussion

As mentioned previously, methods based on FCA are gathered in two main categories: exhaustive methods and combinatory ones. Methods of each category vary from each other in several aspects and share some others. Exhaustive 14 Boosting Formal Concepts 15 The information quantity contained or supplied by a source of information 16 Boosting Nominal Concepts 1 presents exhaustive methods cited previously. In tables 1 and 2, n denote the number of objects and m the number of attributes. In order to identify characteristics of each method, we chose six criteria that seem to be the most distinctive.

Introduction

Functional dependencies (FDs) are well-known constraints in the relational model used to show a functional relation between sets of attributes [10], i.e. when the values of a set of attributes are determined by the values of another set of attributes. They are also used in different tasks within the relational data model, as for instance, to check the consistency of a database, or to guide the design of a data model [9]. Different generalizations of FDs have been defined in order to deal with imprecision, errors and uncertainty in real-world data, or simply, to mine and discover more complex patterns and constraints within data when the semantics of FDs have shown to be too restrictive for modeling certain attribute domains. For example, consider the database in the table above as Note: A longer version of this paper has been accepted at the conference Concept Lattices and their Applications, Moscow, Russia, July 2016. an example4 . Attributes of these 8 tuples are city names, month identifiers, years and average temperatures. From this table, we could expect that the value for average temperature is determined by a city name and a month of the year (e.g. the month of May in Houston is hot, whereas the month of January in Dallas is cold). Therefore, we would expect that this relationship should be somehow expressed as a (functional) dependency in the form city name, month → average temperature. However, while the average temperature is truly determined by a city and a time of the year, it is very hard that it will be exactly the same from one year to another. Instead, we can expect that the value will be similar, or close throughout different years, but rarely the same. Unfortunately, semantics of FDs is based on an equivalence relation and fail to grasp the dependencies among these attributes.

To overcome the limitations of FDs while keeping the idea that some attributes are functionally determined by other attributes, different generalizations of functional dependencies have been defined, as recently deeply reviewed in a comprehensive survey [3]. Actually, the example presented in the last paragraph is a so-called similarity dependency [1,3].

In this paper we present an FCA-based characterization of order-like dependencies, a generalization of functional dependencies in which the equality of values is replaced by the notion of order. Firstly, we show that the characterization of order dependencies in their general definition [7] can be achieved through a particular use of general ordinal scaling [6]. Secondly, we extend our characterization in order to support restricted order dependencies through which other FDs generalizations can be modeled, namely sequential dependencies and trend dependencies [3].

The rest of this paper is organized as follows. In Section 2 we formally introduce the definition of functional dependencies, formal concept analysis and the principle of the characterization of FDs with FCA. In Section 3, we characterize order dependencies in their general definition. We show that our formalization can be adapted to restricted ordered dependencies in Section 4 before to conclude.

Preliminaries

Functional dependencies

We deal with datasets which are sets of tuples. Let U be a set of attributes and Dom be a set of values (a domain). For the sake of simplicity, we assume that Dom is a numerical set. A tuple t is a function t : U → Dom and then a table T is a set of tuples. We define the functional notation of a tuple for a set of attributes X ⊆ U as follows, assuming that there exists a total ordering on U. Given a tuple t ∈ T and X = {x 1 , x 2 , . . . , x n }, we have: t(X) = t(x 1 ), t(x 2 ), . . . , t(x n ) .

Definition 1 (Functional dependency [10]). Let T be a set of tuples (data table), and X, Y ⊆ U. A functional dependency (FD) X → Y holds in T if: Table 1 Example. The table on the right presents 4 tuples T = {t 1 , t 2 , t 3 , t 4 } over attributes U = {a, b, c, d}. We have that t 2 ({a, c}) = t 2 (a), t 2 (c) = 4, 4 . Note that the set notation is usually omitted and we write ab instead of {a, b}. In this example, the functional dependency d → c holds and a → c does not hold.

∀t, t ∈ T : t(X) = t (X) → t(Y ) = t (Y )

Characterization of Functional Dependencies with FCA

It has been shown in previous work that functional dependencies can be characterized with FCA. For example, Ganter & Wille [6] presented a data transformation of the initial set of tuples into a formal context. In this context, implications are in 1-to-1 correspondence with the functional dependencies of the initial dataset.

On the bottom-right figure, we illustrate this characterization with the set of tuples from Table 1 where each possible pair of tuples is an object in the formal context. Attributes remain the same. Object (t i , t j ) has attribute m iff t i (m) = t j (m).

K a b c d (t1, t2) × × (t1, t3) × × × (t1, t4) × (t2, t3) × (t2, t4) × × (t3, t4)
The concept lattice in the bottom right: there are two implications, namely d → c and d → a, which are also the functional dependencies in the original set of tuples. However, this approach implies that a formal context much larger than the original dataset must be processed. It was then shown that this formal context can actually be encoded with a pattern structure [5]: each attribute of the original dataset becomes an object of the pattern structure and is described by a partition on the tuple set. Actually, each block of the partition is composed of tuples taking the same value for the given attribute [8]. For example, in Table 1, the partition describing a is {{t 1 , t 3 }, {t 2 , t 4 }}. Then, the implications in the pattern concept lattice are here again in 1-to-1 correspondence with the functional dependencies of the initial dataset [2]. What is important to notice is that this formalization is possible as a partition is an equivalence relation: a symmetric, reflexive and transitive binary relation. In [1], another kind of dependencies was formalized in a similar way, i.e. similarity dependencies, where the equality relation is relaxed to a similarity relation when comparing two tuples. An attribute is not anymore described by a partition, but by a tolerance relation, i.e. a symmetric, reflexive, but not necessarily transitive binary relation. Each original attribute is then described by a set of tolerance blocks, each being a maximal set of tuples that have pairwise similar values (instead of equal values for classical dependencies).

As we will show next, this way of characterizing FDs and similarity dependencies actually fails for order dependencies, as the relation in this case is not symmetric: it is neither an equality nor a similarity but a partial order in the general case.

3 Characterization of Order Dependencies with FCA Although functional dependencies are used in several domains, they cannot be used to express some relationships that exist in data. Many generalizations have been proposed and we focus in this article on order dependencies [7,3]. Such dependencies are based on the attribute-wise order on tuples. This order assumes that each attribute follows a partial order associated to the values of its domain. For the sake of generality, we represent this order with the symbol x for all x ∈ U. In practice, this symbol will be instantiated by intersections of any partial order on the domain of this attribute, as, for instance, <, ≤, >, ≥, etc. We remark that this order on the set of values of a single attribute does not need to be a total order, although in many different instances, like numeric or character strings domains, this will be the case. Now we formalize operator x (Definition 2) and define accordingly order dependencies (Definition 3).

Definition 2 (Attribute-wise ordering). Given two tuples t i , t j ∈ T and a set of attributes X ⊆ U, the attribute-wise order of these two tuples on X is:

t i X t j ⇔ ∀x ∈ X : t i [x] x t j [x]
This definition states that one tuple is greater -in a sense involving the order of all attributes-than another tuple if their attribute-wise values meet this order. This operator induces a partial order Π X = (T, ≺ X ) on the set T of tuples.

Definition 3 (Order dependency). Let X, Y ⊆ U be two subsets of attributes in a dataset T . An order dependency X → Y holds in T if and only if: ∀t i , t j ∈ T : t i X t j → t i Y t j id a b c t1 1 3 1 t2 2 7 2 t3 3 4 4 t4 5 3 9 t5 4 2 5 t6 3 8 4

Table 2

Example. Consider the table on the right with six tuples and three attributes. Taking a , b and c defined as the ordering ≤. The orders induced by the sets of attributes {a},{b},{c} and {a, b} are:

Πa = (T, ≺a) = {{t1} ≺ {t2} ≺ {t3, t6} ≺ {t5} ≺ {t4}} Π b = (T, ≺ b ) = {{t5} ≺ {t1, t4} ≺ {t3} ≺ {t2} ≺ {t6}} Πc = (T, ≺c) = {{t1} ≺ {t2} ≺ {t3, t6} ≺ {t5} ≺ {t4}} Π ab = (T, ≺ ab ) = {{t1} ≺ {t2} ≺ {t6}; {t1} ≺ {t3}; {t1} ≺ {t4}; {t5} ≺ {t4}}
These orders are such that the order dependency {a, b} → {c} holds. Remark that Definition 3 is generic since the orders that are assumed for each attribute need to be instantiated: we chose ≤ in this example for all attributes, while taking the equality would produce standard functional dependencies.

To achieve the characterization of order dependencies with FCA, we propose to represent the partial order Π X = (T, ≺ X ) associated to each subset of attribute X ⊆ U as a formal context K X (a binary relation on T × T thanks to a general ordinal scaling [6]). Then, we show that an order dependency X → Y holds iff K X = K XY . c t1 t2 t3 t4 t5 t6 t1 Definition 4 (General ordinal scaling of the tuple set). Given a subset of attributes X ⊆ U and a table dataset T , we define a formal context for Π X = (T, ≺ X ) (the partial order it induces) as follows: K X = (T, T, X ) where X = {(t i , t j ) | t i , t j ∈ T, t i X t j }. This formal context is the general ordinal scale of Π X [6]. All formal concepts (A, B) ∈ K X are such that A is the set of lower bounds of B and B is the set of upper bounds of A. Its concept lattice is the smallest complete lattice in which the order Π X can be order embedded.

× × × × × t2 × × × × t3 × × × t4 t5 × t6 × ×
This way to characterize a partial order is only one among several possibilities. However, the choice of formal contexts is due to their versatility, since they can characterize binary relations, hierarchies, dependencies, different orders [6] and graphs [4]. In the next section we will see how this versatility allows us to generalize similarity dependencies. Given the set of attributes X ⊆ U, an associated partial order Π X = (T, ≺ X ) and the formal context (T, T, X ), it is easy to show that the later is a composition of contexts defined as: (T, T, X ) = (T, T, x∈X x ). We can now propose a characterization of order dependencies with FCA. Proposition 1. An order dependency X → Y holds in T iff K X = K XY .

Proof. Recall that K XY = (T, T, XY ) = (T, T, X ∩ Y ). We have that

X → Y ⇐⇒ X = X ∩ Y ⇐⇒ X ⊆ Y ⇐⇒ ∀t i , t j ∈ T, t i X t j → t i Y t j
The fact that the order dependency {a, b} → {c} holds can be illustrated with the formal contexts in Tables 3,4 and 5. We have indeed that K ab = K abc .

Order dependencies and other FDs generalizations. We have seen that the definition of order dependencies replaces the equality condition present in FDs or other similarity measures present in other dependencies, by an order relation. This may suggest that order dependencies and other kinds of FDs generalizations are structurally very similar, whereas this is not the case. Functional dependencies generate a reflexive, symmetric and transitive relation in the set of tuples, i.e. an equivalence relation. Then the set of tuples can be partitioned into equivalence classes that are used to characterize and compute the set of FDs holding in a dataset, as presented in a previous work [2].

In the generalization of functional dependencies that replaces the equality condition by a similarity measure or a distance function, this measure generates a symmetric relation in the set of tuples, but not necessarily a transitive relation. In turn, this implies that the set of tuples can be partitioned into blocks of tolerance instead of equivalence classes, as shown in [1].

In this article, the novelty is that we are dealing with a transitive relation, but not necessarily a symmetric relation. That means that we are not dealing with equivalence classes nor blocks of tolerance any longer, but, precisely, with orders. Since the characterization of these dependencies cannot be performed in terms of equivalence classes nor blocks of tolerance, it requires for a more general approach: general ordinal scaling. Order dependencies allow taking into account the ordering of the values of each attribute when looking for dependencies in data. However, violations of the ordering due to value variations should sometimes not be considered in many real world scenarios. Consider the example given in Table 6: it gives variations on the number of people waiting at a bus station over time.

In such a scenario we can expect that more people will be waiting in the station as time moves on (P eople waiting → T ime). However, at some point, a bus arrives and the number of people waiting decreases and starts increasing again.

It is easy to observe that the order dependency P eople waiting → T ime does not hold as we have the counter-example: t 4 P eople waiting t 3 and t 3 T ime t 4 . However, the gap between the values 77 and 105 is significant enough to be considered as a different instance of the ordering. We can formalize this idea by introducing a similarity threshold θ = 10 for the attribute P eople waiting such that the ordering between values is checked iff the difference is smaller than θ. In this way, the previous counter-example is avoided (restricting the binary relation) along with any other counter-example and we have that the restricted order dependency P eople waiting → T ime holds.

We now formalize the tuple ordering relation, and consequently the notion of restricted order dependencies. Definition 5. Given two tuples t i , t j ∈ T and a set of attributes X ⊆ U, the attribute-wise order on X is: t i * x t j ⇔ ∀x ∈ X : 0 ≤ t j [x]t i [x] ≤ θ x . Definition 6. Let X, Y ⊆ U two sets of attributes in a table T such that |T | = n, and let θ X , θ Y be thresholds values of tuples in X and Y respectively. A restricted order dependency X → Y holds in T iff: t

[X] * X t [X] → t[Y ] * Y t [Y ]
Using these definitions we can encode the tuple ordering relations as formal contexts for any subset of attributes X ⊆ U. Indeed, the binary relations between tuples by operator * X can be encoded in a formal context K * X = (T, T, * X ) * T m t1 t2 t3 t4 t5 t6 t1 x . Moreover, we can use the same rationale we used to mine order dependencies to find restricted order dependencies. Example. For the previous example, we calculate the corresponding formal contexts shown in Tables 7 and8 ( * T m for Time, and * P p for People waiting). It is easy to observe that the restricted order dependency P eople waiting → T ime holds as we have that K * P p = K * P p,T m .

× × × × × × t2 × × × × × t3 × × × × t4 × × × t5 × × t6 ×
Restricted order dependencies and other FDs generalizations. Similarity dependencies (SDs) generalize functional dependencies through the use of a tolerance relation instead of an equivalence relation between values of tuples for a given set of attributes. A tolerance relation is a reflexive, symmetric and non-transitive binary association between two tuples given a threshold θ. In a nutshell, a SD is established between two tuples if their values are within a given distance controlled by the threshold. Such dependencies were studied in a previous work [1]. However, from the perspective of order dependencies, we can request that such distance has a certain polarity. As we have previously discussed, order dependencies arise from anti-symmetric, not necessarily reflexive, and transitive binary relations (<, ≤). Then, it can be expected that using a threshold of distance θ between tuple values for a given set of attributes requires an antisymmetric, non-transitive relation between the values of tuples w.r.t. a set of attributes X, that we have defined as * X . The current approach has the potential to implement some other FD generalizations of such as sequential dependencies and trend dependencies [3]. The latter is actually a particular case of restricted order dependencies where the threshold is applied to an attribute not contained in the attributes of the dependency. Instead, it is applied to a time attribute that allows defining snapshots of a database. In sequential dependencies, the antecedent is a mapping of a set of attributes with a complete unrestricted order (without a threshold). Details on both these dependencies have been left out from this paper for space reasons.

Conclusion

We have presented a characterization of order dependencies with FCA, which can be potentially extended to other types of order-like dependencies, used in different fields of database theory, knowledge discovery and data quality. These dependencies are part of a set of functional dependencies generalizations where equality condition is replaced with a more general relation. In some cases, the equality is replaced by an approximate measure, in other cases, like in order dependencies, by an order relation.

We have seen that order dependencies are based on a transitive, but not necessarily symmetric relation, contrasting similarity dependencies, which are based on a symmetric, but not necessarily transitive relation. It is precisely this formalization in terms of FCA that allows us to find these structural differences between these types of dependencies.

Nevertheless, the present work needs to be extended to other kinds of orderlike dependencies while experimentation needs to be performed in order to verify the computational feasibility of this approach.

as healthy at the time of the analysis. The datasets include a limited number of individuals, a large number of variables or attributes, e.g. molecules or fragments of molecules, and one binary target variable, i.e. developing or not the disease a few years after the analysis.

One important problem here is to distinguish between discriminant and predictive features. A feature is said to be discriminant if it separates individuals in distinct classes, such as for example healthy vs not healthy. A feature is said to be predictive if it enables predicting the evolution of individuals towards the disease a few years later. However, the most discriminant features are not necessarily the best predictive features. Thus, it is essential to compare dierent feature selection methods and to evaluate their capabilities to select relevant features for further use in prediction.

Accordingly, we propose a knowledge discovery process which is based on a combination of numeric-symbolic techniques for dierent purposes, such as noise ltration for avoiding overtting which occurs when the analysis describes random error or noise instead of the underlying relationships, feature selection for reducing dimension, and checking the relevance of selected features w.r.t. prediction. FCA [3] is then applied to the resulting reduced dataset for visualization and interpretation purposes. More precisely, this hybrid data mining process combines FCA with several numerical classiers including Random Forest (RF) [1], Support Vector Machine (SVM) [8], and Analysis of Variance (ANOVA) [2]. RF, SVM and ANOVA are used to discover discriminant biological patterns which are then organized and visualized thanks to FCA.

Actually, the initial problem statement is based on a data table individuals × features. The data preparation step involves ltering methods based on the correlation coecient (Cor) and mutual information (MI) to eliminate redundant and dependent features, to reduce the dimensions of the data table and to prepare the application of RF, SVM and ANOVA. The initial data table individuals × features is transformed into a binary data table features × classication-process in the following way. Ten dierent classications processes (CPs hereafter) are dened and applied to the initial data table. Every CP provides a ranking of features. Then, the N best classied features are kept for being processed by FCA. Actually, a feature is selected when it is ranked among the six rst features. This leads us to a selection of N = 48 features and to a binary data table, 48-features × 10-CPs, which is in turn considered as a formal context for the application of FCA and the construction of concept lattices.

These N = 48 features are shared by all CPs and are interpreted as potential biomarkers of disease development.

Meanwhile, biological experts want to classify the selected features as potential predictive biomarkers, i.e. biomarkers able to predict the disease development a few years before occurrence. Predictive biomarkers can be detected thanks to ROC curves [6]. In the current study, such an analysis produces a short list of the best predictive features which are selected as a core set of biomarkers. Finally, FCA is used again to build the best ranking within this core set of biomarkers and for visualization and interpretation purposes. This is one originality of this paper to present a combination of numerical data mining methods based on RF and SVM with FCA, which in turn is mainly used for interpretation and visualization.

The paper is organized as follows. Section 2 presents preparation and mining of the data for discovering the potential predictive features. Then Section 3 describes experiments performed on real-world metabolomic data set. A discussion and a conclusion complete the paper. 2 The preparation and the mining of metabolomic data All experiments in the following were carried out on a Dell machine running Ubuntu GNU/Linux 14.04 LTS, a 3.60 GHZ × 8 CPU and 16 GB RAM. The data analysis methods are taken from the RStudio software environment (Version 0.98.1103, R 3.1.1). Rstudio is freely available and oers a selection of packages suitable for many dierent types of data 1 .

2.1

The dataset description

The dataset which is analyzed is based on a case-control study from the GAZEL French population-based cohort (20000 subjects). This set includes numeric and symbolic data about 111 male subjects (54-64 years old) free of T2D at baseline. 55 subjects developed T2D at the follow-up belong to class 1 (non healthy or diabetic subjects) while 56 subjects belong to class -1 (controls or healthy subjects). Three thousand features are generated after carrying out mass spectrometry (MS) analysis. After noise ltration, 1195 features are remaining for describing every subject.

The reference dataset is composed of homogeneous individuals considered healthy at the beginning of the study. The binary variable describing the two target classes, i.e. healthy and not healthy, is based on the health status of the same individuals at another time, actually ve years after the initial analysis.

Meanwhile, some individuals developed the disease. Thus, discriminant features which enable a good separation between target data classes (healthy vs. not healthy) are not necessarily the best features predicting the disease development ve years later.

Data preprocessing

Only a few features allow a good separation between the target classes. Therefore, it is necessary to reduce data dimension to select a small number of relevant features for further use in prediction. Reducing the dimensionality of the data is a challenging step, requiring a prior ltering of the initial data. Metabolomic data contain highly correlated features, which can have an impact on feature selection and data mining [4]. Thus, two ltering methods are chosen, namely the In parallel, we apply the the ANOVA method directly on the original dataset as this is a common practice in metabolomics (without any ltering process).

This time, SVM+RFE, RF and ANOVA are directly applied to the original dataset.

1195-features we nally get a binary data table 48-features × 10-CPs. The m/z label of features stands for mass per charge.

Applying FCA on the 48-features × 10-CPs data table considered as a context produces a concept lattice with 272 concepts (Figure 2). This concept lattice illustrates the combination of numerical classication methods with FCA, and allow an interpretation of the relations between features and classication processes, and further on the discriminative and predictive powers of the features. The concept lattice highlights the potential of the feature selection approach for analyzing metabolomic data. It enables discriminating direct and indirect associations, e.g. highly linked metabolites belonging to the same concept. The links between the concepts in the lattice can be interpreted as interdependency between concept and metabolites. (Table 1).

383. This conrms that the most frequent features are not the best predictive ones, as biologically suspected, because the metabolomic analysis is performed 5 years before disease occurrence. Moreover, these best predictive features or potential biomarkers are not belonging to the same concept.

Conclusion and future work

In this paper, we presented a hybrid approach for the identication of predictive biomarkers from complex metabolomic dataset. The nature of metabolomic data, i.e. highly correlated and noisy, leads us to build and analyze reduced datasets for identifying important features to be interpreted as potential biomarkers.

Moreover, the present hybrid approach is based on an original combination of numerical supervised classication methods (mainly RF, SVM and ANOVA) and a symbolic unsupervised method such as FCA. This study shows the interest of such a combination to reveal hidden information in such high dimensional datasets and how FCA can be used for visualization and interpretation purposes.

Based on the resulting lattice, experts in biology will be able to lead a deeper interpretation. Finally, additional experiments on dierent metabolomic datasets are required to conrm the success of this hybrid approach.

  rd(⊥) := rd( ) := rd(A) := 0, rd(C D) := rd(C) ∨ rd(D), and rd(∃ r. C) := 1 + rd(C).

⊥

  I := ∅, I := ∆ I , (C D) I := C I ∩ D I , and (∃ r. C) I := { d ∈ ∆ I | ∃ e ∈ ∆ I : (d, e) ∈ r I and e ∈ C I }. A GCI C D is valid in I if C I ⊆ D I . We then also refer to I as a model of C D, and denote this by I | = C D. Furthermore, I is a model of a TBox T , symbolized as I | = T , if each GCI in T is valid in I. The entailment relation is lifted to TBoxes as follows: A GCI C D is entailed by a TBox T , denoted as T | = C D, if each model of T is a model of C D, too. We then also say that C is subsumed by D with respect to T . A TBox T entails a TBox U, symbolized as T | = U, if T entails each GCI in U, or equivalently if each model of T is also a model of U. Two EL ⊥ -concept descriptions C and D are equivalent with respect to T , and we shall write T | = C ≡ D, if T | = {C D, D C}.

Definition 1 .

 1 Let T be an EL ⊥ -TBox, C an EL ⊥ -concept description, and δ ∈ N a role-depth bound. Then an EL ⊥ -concept description D is called a role-depth-bounded most specific consequence of C with respect to T and δ if it satisfies the following conditions: 1. rd(D) ≤ δ, 2. T | = C D, and 3. for each EL ⊥ -concept description E, if rd(E) ≤ δ and T | = C E, then ∅ | = D E.

1 .

 1 C D is both valid in I as well as entailed by T .2. ∅ | = {C II δ D, C T δ D}. 3. ∅ | = C II δ ∨ C T δ D. 4. C D is valid in the infimum of C → C II δ and C → C T δ .

  Car, Wheel}, N R := {child} T := {∃ child.Person,

2. 1

 1 Context, concept and concept lattice Definition 1. A formal context is any triple C = B, A, R where B and A are finite sets and R ⊆ B × A is a binary relation. It is customary to say that B is a set of objects, A is a set of attributes and R represents a relation between objects and attributes.

Definition 9 .

 9 Two contexts C and D are isomorphic if their concept lattices are isomorphic. Definition 10. Given formal contexts C 1 , . . . , C n , C, we say that C is a consequence of contexts C 1 , . . . , C n , denoted as C 1 , . . . , C n |= C, if C is isomorphic to a bond between all contexts in the left hand side. Specifically, C 1 , . . . , C n |= C if and only if C is isomorphic to some n-ary bond between input formal contexts C 1 , . . . , C n .

  Axiom rule: As a unary bond we use a context itself C |= C Constants rule Due to isomorphism Bonds (C, ) ∼ = Ext(C) where = { }, { }, = we can write the following rule C 1 , . . . , C n |= C , C 1 , . . . , C n |= C ⊗-left From the definition of |= and associativity of tensor product, or of associativity inside of n-ary product, we can write

  right Any dual bond between n-ary and m-ary bonds is an n + m-ary bond between all input formal contexts C 1 . . . , C n |= C D 1 . . . , D m |= D C 1 . . . , C n , D 1 . . . , D m |= C ⊗ D ×-left Due to the distributivity of tensor and categorical product on formal contexts, n-ary bond between C 1 , . . . , C n-1 , C n × D is equal to product of n-ary bonds between C 1 , . . . , C n-1 , C n and C 1 , . . . , C n-1 , D.

  forms a closure system in D and furthermore C G : D|C G forms a complete lattice.

Definition 2 .

 2 attributes and conditions. An element (g, m, b) ∈ Y of the incidence relation is read object g has attribute m under condition b. The triadic concepts, also called triconcepts, of a tricontext K = (K 1 , K 2 , K 3 , Y ) are exactly the triples (A 1 , A 2 , A 3 ) that satisfy A 1 ×A 2 ×A 3 ⊆ Y and which are maximal w.r.t. component-wise set inclusion.

Fig. 1 :

 1 Fig. 1: Dyadic context of reachability K ▹ Fig. 2: Concept lattice of K ▹

Fig. 1 :

 1 Fig. 1: List of dyadic contexts

Fig. 4 :Fig. 5 :Fig. 6 :

 456 Fig. 4: Hostels tricontext

Fig. 1 :

 1 Fig. 1: AOC-Posets.

Fig. 2 :

 2 Fig. 2: Top image shows the first level of the concept lattice, the bottom image shows the second level built by interaction.

Fig. 3 :

 3 Fig.3: The sub-lattice highlighted for the author "Amedeo Napoli".

Fig. 4 :

 4 Fig. 4: Highlighting super-concepts of a concept.

Fig. 5 :

 5 Fig. 5: Showing only sub-lattice of the interesting concept. Fig. 6: Showing only super-concepts of the interesting concept.

Fig. 7 :

 7 Fig. 7: Interval pattern concept lattice for publications.

Fig. 8 :

 8 Fig. 8: Filtered concept lattice obtained from binary context.

Fig. 9 :

 9 Fig. 9: Filtered Pattern Concept Lattice.

Fig. 10 :

 10 Fig. 10: Attribute implications for the running example.

2 Dominik

 2 Brosius and Steffen Staab

  is a triple comprised of a set of objects G, a set of attributes M and an indicidence relation I ⊆ G × M encoding that "g has attribute m" iff gIm. Definition 2 (Formal Concept). For A ⊆ G and B ⊆ M [13] define A := {m ∈ M |∀g ∈ A : gIm}, B := {g ∈ G|∀m ∈ B : gIm}.

Fig. 1 :

 1 Fig. 1: Examples of (a) RDF graphs, (b) a BGP and (c) a solution to the BGP

Definition 6 (

 6 Resource-Feature Map). We define a feature domain F as the set of all known predicates p encountered in D. A resource-feature map f : D × U → 2 F assigns an RDF resource r the set of describing features found in a graph:f (D, r) = {p ∈ F |∃o ∈ T :< r, p, o >∈ D}. Example 1. f (g ex , ex:quadrophenia) = {ex:title, ex:tracks}There are other possible manifestations of such a resource-feature map. For example, one could (also) map the types assigned to resources through rdf:type. Definition 7 (Schema Lattice). We define a graph-covering formal context K := (U, F, I f ) with the set of resources U , the feature domain F and I f := {(r, p)|∃D ∈ D, ∃r ∈ U : p ∈ f (D, r)}. The schema lattice L S = (L(U, F, I f ), ≤) is the lattice constructed from K via FCA.

Fig. 1 :

 1 Fig. 1: Toy knowledge base. The subfigures 1d and 1b illustrate a set of facts (this corresponds to the ABox in description logics terms). Subfigure 1c illustrates the hierarchy of properties w.r.t. the subP relation. The subfigure 1a shows the hierarchy of classes with their instances.

Proposition 3 .Fig. 1 .

 31 Fig. 1. Lattice L NΠ

Definition 2 .

 2 A Fuzzy Relation between two sets X and Y is a function I : X × Y → L, for some residuated lattice L. Definition 3. A Fuzzy Context is a triple (X, Y, I) where X is a set of objects, Y is a set of attributes, I is a fuzzy relation, I : X × Y → L.

Definition 6 .

 6 A fuzzy concept is a pair (A, B), where A is a fuzzy set of objects, A : X → L and B is a fuzzy set of attributes B : Y → L, such that A ↑ = B and A = B ↓ .

Definition 7 .

 7 A pattern structure P is a triple (G, (D, ), δ), where G, D are sets, called the set of objects and the set of descriptions, and δ : G → D maps an object to a description. Respectively, (D, ) is a meet-semilattice on D w.r.t. , called similarity operation such that δ(G) := {δ(g) | g ∈ G} generates a complete subsemilattice (D δ , ) of (D, ).

Definition 8 .

 8 A pattern concept of a pattern structure (G, (D, ), δ) is a pair (A, d), where A ⊆ G and d ∈ D such that A = d and d = A; A is called the pattern extent and d is called the pattern intent.

  714, 1, 0.571, 0.429, 0.429 0.857, 0.571, 1, 0.286, 0.714 = = min(0.714, 0.857), min(1, 0.571), min(0.571, 1), min(0.429, 0.286), min(0.429, 0.714) = 0.714, 0.571, 0.571, 0.286, 0.429 4 From Fuzzy FCA to Pattern Structures with Scaling

Definition 10 .

 10 A fuzzy attribute set B : Y → L is equivalent to a pattern d ∈ D, written as B ∼ d, iff (∀y ∈ Y )(B(y) = d(y)), where d(y) is the value of the tuple d corresponding to the attribute y.

Fig. 1 .

 1 Fig. 1. Different transfer functions

Fig. 2 .

 2 Fig. 2. Configuration file for the case study

Fig. 3 .

 3 Fig. 3. Average accuracy of the different heuristics as a function of the number of anonymous transactions recieved by the classifier.

Definition 1 .Definition 2 .

 12 Let G be a set (of objects), let (D, ) be a meet-semi-lattice (of all possible object descriptions) and let δ : G → D be a mapping between objects and descriptions. Set δ(G) := {δ(g)|g ∈ G} generates a complete subsemilattice(D δ , ) of (D, ), if every subset X of δ(G) has infimum X in (D, ).Pattern structure is a triple (G, D, δ), where D = (D, ), provided that the set δ(G) := {δ(g) | g ∈ G} generates a complete subsemilattice (D δ , ) [4, 9]. Patterns are elements of D. Patterns are naturally ordered by subsumption relation : given c, d ∈ D one has c d ⇔ c d = c. Operation is also called a similarity operation. A pattern structure (G, D, δ) gives rise to the following derivation operators (•) : A = g∈A δ(g) for A ∈ G, d = {g ∈ G | d δ(g)} for d ∈ (D, ). Pairs (A, d) satisfying A ⊆ G, d ∈ D, A = d, and A = d are called pattern concepts of (G, D, δ).

Definition 4 .

 4 Let (G, (D, ), δ) be an interval pattern structure. Let T i = {τ i1 , . . . , τ iti }, i = 1, . . . , m be m sets of real numbers where m is a cardinality of each d ∈ D. Then, ψ( [a i , b

Fig. 1 (

 1 middle). The corresponding concept lattice is shown in the same figure on the right-hand side.

Fig. 1 .

 1 Fig. 1. A toy many-valued context, it's discretization and the corresponding concept lattice.

aAlgorithm 1

 1 ≤ 1.5 a ≤ 3.5 a ≥ 1.5 a ≥ 3a, b]) = [max{τ | τ ∈ T + , τ ≤ a}, min{τ | τ ∈ T + , τ ≥ b}] with T + = {-∞, 1.5, 3.5, +∞} is a projection of the semilattice built for a context that arises from the interordinal scaling of the initial many-valued numerical context. Address to [8] for more details on the link between interordinal scaling -Predict the value of the class attribute for g t as an indicator of the average antecedent of r test [t] being greater or equal to the proportion of positive objects in the training set: c test [i] = [ n_rules i=1 f + i ≥ f pos * n_rules] Concept Lattice-Based Rule-learner (CoLiBRi) Input: P Strain = (Gtrain, ((D, ), ctrain), δtrain) P Stest = (Gtest, (D, ), δtest) min_supp ∈ R + , n rules ∈ N; CbOP S (P S, min_supp) : P S → S; inf : D × ctrain → R; sort(S, inf ) : S → S Output: ctest, rtest ctest = ∅, rtest = ∅ fpos = |c train | |G train | S = {(A, d) : inf (d, ctrain) | A ⊆ Gtrain, d ∈ D, A = d, d = A, |A| ≥ min_supp} = CbOP S (P Strain, min_supp) S = sort(S, inf ) for gt ∈ Gtest do {di} i∈[1,n rules ] = {d | (A, d) ∈ S, g t d}

Proposition 2 .

 2 A restricted order dependency X → Y holds in T iff X → Y ⇐⇒ K * X = K * XYProof. This proposition can be proved similarly to Proposition 1.

1

  https://www.rstudio.com/ coecient of correlation (Cor) and mutual information (MI). Both ltering methods are used to discard correlated features and dependent features.

Figure 1

 1 Figure 1 describes the global classication workow. At the beginning, the ltering methods Cor and MI eliminate highly correlated features. Afterward, two reduced subsets are generated: a rst subset contains 963 features (after Cor ltering) while the second subset contains 590 features (after MI ltering). Both reduced subsets are used as input for the application of RF and SVM classiers.

Fig. 1 .

 1 Fig. 1. Feature selection and dimensionality reduction process.

Four

  features m/z 383, m/z 227, m/z 114 and m/z 165 have a maximal support of 10 (see the maximum rectangle full of 1 in Table 1). There are strong relationships among the 44 remaining features, especially involving m/z 284, m/z 204, m/z 132, m/z 187, m/z 219, m/z 203, m/z 109, m/z 97 and m/z 145. Moreover, among the 48 features, 39 are signicant w.r.t. ANOVA (with a p-value < 0.05).

Fig. 2 .

 2 Fig. 2. The concept lattice derived from the 48 × 10 binary table(Table 1).

Figure 2

 2 Figure 2 shows that the best predictive biomarkers are lying in dierent concepts, depicted by red squares in the lattice. For example, the features m/z 145, m/z 97, m/z 109 and m/z 187 are in the extent of a concept whose intent includes all CPs but SVM-RFE-W. By contrast, the feature m/z 268 belongs to another concept whose intent includes 6 CPs, namely RF-MdGini, RF-MdAcc, MI-SVM-RFE-Acc, MI-SVM-RFE-Kap, SVM-RFE-W, ANOVA-pValue. Here again, the direct visualization through the concept lattice shows the position of the predictive features among the discriminant ones and their associations with CPs. This information is very interesting for the domain experts for choosing the best combinations of feature selection methods that can identify the predictive biomarkers.

  t. f ¡1 tt L | t ¤ yu ts P | s ¤ xu. ¡1 ts P | x ¤ su tt L | y ¤ tu. (4)The dual of L is given by L op pL,¥q with ¥: tpx,tq L ¢L | t ¤ xu. The pair

(3) g is residual from L to P if the preimage of a principal filter in P under g is always a principal filter in L, that is, for every x P there exists y L s.t.

g pf,gq is a Galois connection w.r.t. pP,Lq if pf,gq is an adjunction w.r.t. pP,L op q.

  A description d ∈ D is a pair (p i , O i ) where p i is a predicate and O i is a set of objects in the range of p i . Given an entity s ∈ G, its description is defined as follow: δ(s) = {d s 1 , . . . , d s n } where d s j = (p j , O s j ) with j = {1, . . . , n}. Each elementary description (p i , o j ) is replaced with (p i , C(o j )) where C(o j ) is the class of o j in the reference schema.

	Given two descriptions δ(x) = {d x 1 , . . . , d x n } and δ(y) = {d y 1 , . . . , d y m }, we have δ(x) δ(y) if ∀d x i ∈ δ(x), ∃d y j ∈ δ(y) s.t. i = j and ∀o x i ∈ O x i , ∃o y j ∈ O y j s.t. C(o x i ) subC C(o y j ). Similarity between descriptions. The hierarchy of classes from the ref-
	erence schema is considered. Thus, the similarity between two objects is defined
	as follows:
	δ(x) δ(y) ={d x 1 , . . . , d x n } {d y 1 , . . . , d y m }
	=min
	i∈{1,...,n}
	j∈{1,...,m}

pair (p, o) such that (s, p, o) ∈ B is mapped to a description d ∈ D.

Table 2 :

 2 Scaling of the fuzzy context from table Table 1b to a number-minimum pattern structure.

	t1	t2	t3	t4	t5	t1	t2	t3	t4	t5
	t1, 1.000 1.000 0.714 0.857 0.429 0.429 t1, 0.857 1.000 0.714 1.000 0.429 0.429	• • • t3, 0.429 1.000 1.000 1.000 0.286 1.000
	t1, 0.714 1.000 1.000 1.000 0.429 0.429 • • • t2, 1.000 0.714 1.000 0.571 0.429 0.429 • • • t2, 0.571 1.000 1.000 1.000 0.429 0.429 • • • t3, 1.000 0.857 0.571 1.000 0.286 0.714 • • •	• • • t4, 1.000 0.429 0.429 0.286 1.000 0.000 • • • t4, 0.286 1.000 1.000 1.000 1.000 0.000 • • • t5, 1.000 0.429 0.429 0.714 0.000 1.000 • • • t5, 0.286 1.000 1.000 1.000 1.000 0.000

Table 1 .

 1 Descriptive statistics of the datasetOur tool implements several heuristics. H 0 considers frequent 1-patterns with the best support, H 0 Lif t considers frequent 1-patterns with the best lift, H 1 considers closed k-patterns with the best tf × idf , and B is a smoothed Bayes classifier. The tf × idf is a metric that comes from information retrieval and text mining. It is the product of term frequency and inverse document frequency. It reflects how discriminating a pattern is for a given class. The experiments in

	#U sers #Sites Avg#lines/user
	Raw Data	3388 96184	5082
	After preprocessing 3370 57654	1145
	3.2 Experimental parameters

Table 2 .

 2 Output of the tool

	NC A Method Avg accuracy Min accuracy Max accuracy TC 150 1 H1 0.31266 0.30213 0.32118 75.796%
	150 2	H1 0.34378	0.32827	0.35666	93.335%
	150 5	H1 0.46909	0.4505	0.48996	99.676%
	150 10 H1 0.67352	0.63714	0.69905	100%
	150 20 H1 0.87778	0.85111	0.92	100%
	150 30 H1 0.94833	0.92333	0.96333	100%

Table 1 .

 1 Accuracies and F1-scores in classification experiments with the UCI machine learning datasets. "DT acc" and "DT F1" stand for average 5-run 5-fold CV accuracy and F1 score of the CART algorithm, . . . , "CoLiBRi F1" stands for average 5-run 5-fold CV F1 score of the proposed CoLiBRi algorithm.

	1

Table 2 .

 2 Best parameters in classification experiments with the UCI machine learning datasets. CoLiBRi's min_supp is taken equal to CART's min_samples_leaf for each dataset.

	dataset audiology balance-scale breast cancer car hayses-roth lymph mol-bio-prom nursery primary tumor solar flare soybean spect train tic-tac-toe	DT min_samples_leaf RF min_samples_leaf kNN k 1 1 2 6 1 50 4 3 5 3 2 5 3 1 15 1 1 5 3 3 5 3 4 50 4 4 30 3 1 30 1 1 2 9 5 10 10 3 10

4

  Navigation into Galois Lattice 5 Hierarchical Multi-label Classifier System -FCA with Similarity Cosine 6 the similarity between two vectors with n dimensions by determining the cosine of the angle between them 7 Classification by Selecting Plausible Formal Concepts in a Concept Lattice 8 Learning with Galois Lattice 9 Concept Induction Based Learning 10 Concept Lattices Nearest Neighbors and Concept Lattices Naive Bayes classifier in each node of the sublattice built. CLNN & CLNB use the same technique of vote (majority vote) in the classification step

11

  Concept Lattice-based Artificial Neural Network 12 Mining Complex Sequential Data by means of FCA and Pattern Structures 13 Induction of Production Rules

  17 Dagging Nominal Concepts18 Fitting Pattern Structures to Knowledge Discovery in Big Data19 Recommender based Multiple Classifier System methods generate only one ordinary classifier for the classification of the objects. Table

Table 3 :

 3 (T, T, c )

	ab t1 t2 t3 t4 t5 t6
	t1 t2 t3	× ×	× ×
	t4
	t5 t6	×

Table 4 :

 4 (T, T, ab )

	abc t1 t2 t3 t4 t5 t6
	t1 t2 t3	× ×	× ×
	t4
	t5 t6	×

Table 5 :

 5 (T, T, abc )

Table 7 :

 7 (T, T, * T m ) *

	P p t1 t2 t3 t4 t5 t6
	t1 × × × t2 × × t3 × t4 t5 t6	× × × × × ×

Table 8 :

 8 (T, T, * P p ) *

	T m,P p t1 t2 t3 t4 t5 t6
	t1 t2 t3 t4 t5 t6	× × × × × ×	× × × × × ×

Table 9 :

 9 (T, T, * T m,P p ) which in turn, can be composed from single attributes x ∈ U: * X =

	*
	x∈X

Table 2 .

 2 Table of performance of the best 10 AUC ranked features.

	Name	AUC T-tests
	m/z 145	0.79 1.4483E-6
	m/z 383	0.79 5.0394E-7
	m/z 97	0.78 1.5972E-6
	m/z 325	0.77 2.2332E-5
	m/z 69	0.76 1.2361E-5
	m/z 268	0.75 4.564E-6
	m/z 441	0.75 9.0409E-5
	m/z 263	0.75 5.996E-6
	m/z 187	0.74 9.0708E-6
	m/z 109	0.74 2.6369E-5

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

https://fca-tools-bundle.com

https://gist.github.com/rpuntaie/37a380a84f9843b5dd17

https://bl.ocks.org/mbostock/3231298

http://www.w3.org/RDF/

http://en.lodlive.it/

http://conexp.sourceforge.net/

http://portal.core.edu.au/conf-ranks/

https://sourceforge.net/projects/galicia/

http://toscanaj.sourceforge.net/

Resource Description Framework; http://www.w3.org/TR/rdf-concepts/

http://www.w3.org/TR/sparql11-overview/

The term object is ambiguous: it denotes both the first part of a pattern structure and the last element of an RDF triple.The term entity will be used to denote objects of the pattern structure. The term object remains for the triples.

We notice that t4, 0.429 and t4, 0.286 are two different scaled objects.

Case studyOur case study is about implicit identification in web-browsing. Implicit identification is studied in[10] and in a web-browsing context in[11][12][13][14]. The challenge

http://winhelp2002.mvps.org/hosts.htm and https://pgl.yoyo.org/as.

http://repository.seasr.org/Datasets/UCI/csv/

Graph-based induction

Example from The University of Dayton, that shows the month average temperatures for different cities: http://academic.udayton.edu/kissock/http/Weather/

Acknowledgements. The author gratefully thanks the anonymous reviewers for their constructive hints and helpful remarks.

Acknowledgments

Justine Reynaud is preparing her PhD Thesis with the support of "Région Lorraine" and "Délégation Générale de l'Armement".

Acknowledgement

This research was partially supported by the European Union's "Fonds Européen de Développement Régional (FEDER)" program.

Acknowledgments. This research work has been supported by the SGR2014-890 (MACDA) project of the Generalitat de Catalunya, the MINECO project APCOM (TIN2014-57226-P) and the French National Project FUI AAP 14 Tracaverre.

Isomorphism of fuzzy and pattern lattices

In this subsection we show that our scaling procedure is correct. And the resulting pattern lattice and the fuzzy lattice are isomorphic. Moreover, the extents and intents of these lattices are connected by means of Definitions 9 and 10. The first lemma (a standard property of residuated lattices) shows that fuzzy implications are related if their premises are comparable.

Lemma 1 If there are l 1 , l 2 , l ∈ L such that l 1 ≤ l 2 then

Proof. Let l 2 l = r then according to Def. 1:

Let us now show that starting from two (fuzzy and scaled) equivalent sets of objects the resulting descriptions are also equivalent.

Lemma 2 Given a fuzzy set of objects A : X → L and a scaled set of objects N ⊆ G, such that A ∼ φ(N ), we have A ↑ ∼ N .

Proof. Consider the value of the pattern tuple N corresponding to an attribute y: N (y) = ∀g∈N δ(g) (y). The semilattice operation of the minimum pattern structure corresponds to the infimum in the residuated lattice: Finally let us show, that starting from equivalent fuzzy set of attributes and pattern, the sets of objects given by the derivation operators are also equivalent. Proof. Let us study when object x ∈ X, l ∈ L can be included into d .

and interval pattern structures. The pattern concept lattice corresponding to the discretizing projection ψ([a, b]) is isomorphic to the concept lattice of the discretized context shown in Fig. 1 (middle).

Introducing a discretizing projection is a general way to express any discretizing procedure (essential part of decision tree learning algorithms) in terms of FCA.

Learning with Pattern Concept Lattices

For classification tasks with complex data we propose Algorithm 1. The main idea is to find the classification rule for each test instance that maximizes some information criterion (Gini index, pairwise mutual information etc.). In case of interval pattern structures, by its design, the algorithm guarantees to classify each test instance with at least as good rule (in terms of an information criterion) as a decision tree. We apply a modification of the CloseByOne algorithm [7] to build all pattern concepts -the search space for classification rules.

Let P S train = (G train , ((D, ), c train ), δ train ) and P S test = (G test , (D, ), δ test ) be two pattern structures corresponding to a train and a test set in a classification task. Let CbO P S (P S, min_supp) be the algorithm used to find all pattern concepts of a pattern structure P S with support greater or equal to min_supp. Let inf : D ∪c train → R be an information criterion used to rate classification rules (we use Gini impurity by default). Finally, let min_supp and n_rules be the parameters of the algorithm (the minimal support of each classification rule's premise and the number of rules to be used for prediction of each test instance's class attribute).

With this designations, the main steps of the proposed algorithm are the following:

1. Initialize a list of predicted labels for test instances c test and a dictionary of classification rules r test for each test instance. 2. Calculate the proportion of positive objects in the training set: f pos = |c train | |Gtrain| 3. With the CbO P S algorithm, find S -a dictionary of all pattern concepts (with support greater or equal to min_supp) of a pattern structure P S train Meanwhile, calculate the value of the criterion inf (values in the dictionary S) for each concept intent (keys in the dictionary S). 4. Sort S by its values. 5. For each test instance g t ∈ G test :

-Find first n rules concept intents from S such that (A i , d i ) ∈ S, g t d i , i = 1, . . . , n rules -For each "top-ranked" concept intent d i determine c i -the proportion of positive objects among d i :

A=alphabet of sequence letters

Table 1. Theoretical comparison of exhaustive methods

As shown in Table 1, exhaustive methods have exponential complexity. It is mainly due to a navigation in the totality of the research space.

On the other side, combinatory methods share the classification process in different classifiers a combination method. The problem is thus divided into many sub-problems. Similarly, to Table 1, Table 2 provides a description of combinatory methods. We used the same criteria in two tables for comparative reasons.

Tables 1 and2 show that GRAND, IPR, CITREC, CLANN, BFC and RMCS handle binary data, BNC and DNC manipulate nominal data while CIBLE handle numerical data. However FPS-FCA and MCSD-FCA-PS differ from the previous methods by their capacity to handle complex data like graphs and sequential data. BNC and DNC use the informational gain to select concepts, while IPR and BFC use Shannon entropy. Concerning CLANN, it utilizes heuristic algorithms for the selection.

In classification process, GRAND, CITREC and DNC use the majority voting. The weighted voting is applied in IPR, BFC and BNC. However, CLANN differ from other methods by the use of neural networks.

The combining technique (cf. section 3.2) contributed strongly in optimizing the complexity. In fact, combinatory methods generate classifiers sequentially and have a polynomial logarithmic complexity. Similarly, methods generating parallel classifiers reach a comparable complexity in the order of nmlog(n) for RMCS method, nm/k for FPS-FCA method and n for DNC.

Conclusion

In this paper, we focused on supervised classification of data based on FCA. We presented firstly exhaustive classification methods which are divided into methods based on complete lattices and methods based on sublattices. Secondly, we described combinatory classification methods which are themselves divided into methods based on sequential training and others based on parallel training.

Our future work will be based on the complexity and move towards combinatory methods that offer reasonable complexity, especially methods that generate parallel classifiers.

Contributions to the Formalization of Order-like

Dependencies using FCA Abstract. Functional Dependencies (FDs) play a key role in many fields of the relational database model, one of the most widely used database systems. FDs have also been applied in data analysis, data quality, knowledge discovery and the like, but in a very limited scope, because of their fixed semantics. To overcome this limitation, many generalizations have been defined to relax the crisp definition of FDs. FDs and a few of their generalizations have been characterized with Formal Concept Analysis which reveals itself to be an interesting unified framework for characterizing dependencies, that is, understanding and computing them in a formal way. In this paper, we extend this work by taking into account order-like dependencies. Such dependencies, well defined in the database field, consider an ordering on the domain of each attribute, and not simply an equality relation as with standard FDs.

A Hybrid Approach for Mining Metabolomic Data

Dhouha Grissa 1,3 , Blandine Comte 1 , Estelle Pujos-Guillot 2 , and Amedeo Napoli 3 Abstract. In this paper, we introduce a hybrid approach for analyzing metabolomic data about the so-called diabetes of type 2. The identication of biomarkers which are witness of the disease is very important and can be guided by data mining methods. The data to be analyzed are massive and complex and are organized around a small set of individuals and a large set of variables (attributes). In this study, we based our experiments on a combination of ecient numerical supervised methods, namely Support Vector Machines (SVM), Random Forests (RF), and ANOVA, and a symbolic non supervised method, namely Formal Concept Analysis (FCA). The data mining strategy is based on ten specic classication processes which are organized around three main operations, ltering, feature selection, and post-processing. The numerical methods are mainly used in ltering and feature selection while FCA is mainly used for visualization and interpretation purposes. The rst results are encouraging and show that the present strategy is well-adapted to the mining of such complex biological data and the identication of potential predictive biomarkers.

Keywords: hybrid knowledge discovery, Random Forest, SVM, ANOVA, Formal Concept Analysis, feature selection, discrimination, predication, visualization 1

Introduction

Metabolomics allows the analysis of a biological system by measuring metabolites, i.e. small molecules, present and accessible in the system. Usually dierent techniques are necessary for such an analysis. In particular, one challenge of metabolomics is to identify, among thousands of features, predictive biomarkers, i.e. a measurable indicator of some biological status, of a disease development [7].

This can be viewed as a hard data mining task as data generated by metabolomic platforms are massive, complex and noisy. In the present study, we aim at identifying predictive metabolic biomarkers of future T2D type 2 diabetes development, a few years before occurrence, in an homogeneous population considered

The measure of the importance of each selected feature in the output of the classication process is the purpose of post-processing. There, several measures of interest (accuracy metrics) enable the ranking of the features, namely MdGini, MdAcc, Accuracy and Kappa. MdGini stands for Mean decrease in Gini index is used as an impurity function. MdAcc stands for Mean decrease in accuracy and measures the importance/performance of each feature in the classication.

Kappa is a statistical measure comparing observed accuracy with expected accuracy. The general idea about the use of these metrics is to measure the decrease in accuracy after permutation of the values of each variable. The scores given by these metrics allow to rank the features (highest discriminative power) within each classication process.

On the same basis, when no ltering is applied, post-processing is based on MdGini and MdAcc for RF, on the weight magnitude of features W for SVM+REF, and on the p-value for ANOVA. The p-value determines the statistical signicance of the results when a hypothesis test is performed.

Based on these dierent processes, various forms of results, e.g. feature ranking and feature weighting, and as well multiple sets of ranked features are produced. Actually, 10 sets are generated, corresponding to the dierent CPs and ranking scores. They are denoted by D i , i = 1, . . . , 10 in Figure 1.

For each classication process, a corresponding name is created which describe the set of operations the process is based on. We have the ten following processes: (1) Cor-RF-MdAcc, i.e. ltering with Cor, feature selection with RF and post-processing with MdAcc, (2) Cor-RF-MdGini, (3) Cor-RF-RFE-Acc, (4) Cor-RF-RFE-Kap, (5) MI-SVM-RFE-Acc, (6) MI-SVM-RFE-Kap, (7) RF-MdAcc, (8) RF-MdGini, (9) SVM-RFE-W and nally (10) ANOVA-pValue.

To select the most important features, we retain the 200 rst ranked features, except for ANOVA-pValue where we only selected 107 features with a reasonable p-value for ltering purposes (lower than 0.1). Finally, ten reduced sets of ranked features, i.e. D i , i = 1, . . . , 10, are obtained and should be analyzed for discovering the best features. Then, the visualization of these best features is carried out thanks to FCA.

2.4

Visualization and interpretation with FCA

In this section, we show how to compare the highly ranked features in the reduced subsets D i , i = 1, . . . , 10.

Evaluation and discussion

Considering the 48 most frequent features previously identied, we evaluate their predictive capabilities using ROC curves (Figure 3). This analysis was carried out using the ROCCET tool (http://www.roccet.ca), with calculation of the area under the curve (AUC) and condence intervals (CI), calculation of the true positive rate (T P R), where T P R = T P/(T P +F N ), and the false discovery rate (F DR), where F DR = T N/(T N + F P ). The p-values of these relevant features are also computed using t-test. The analysis based on ROC curves is considered as being one of the most objective and statistically valid method for biomarker performance evaluation [6]. ROC curves are commonly used to evaluate the prediction performance of a set of features, or their accuracy to discriminate diseased cases from normal cases.

Since the number of features to propose as predictive biomarkers should be rather small (because of clinical constraints), we rely on the ROC curves of 2, 3, 5, 10, 20 and 48 of features ranked w.r.t. AUC values. The ROC curves enable identifying this best combination of predictive features. Figure 3 shows that the best performance is given to the 48 features all together (with AU C = 0.867).

But a predictive model with 48 features is not usable for clinical purposes. The set of best features with the smallest p-values and the highest accuracy values is selected and yields a short list of potential biomarkers. For the ten rst features in Table 2, we have AU C = 0.79 and CI = 0.71 -0.9. For the four rst features, we have AU C = 0.75. These high AUC values are witness of a good predictive behavior.

Then we selected as potential biomarkers the 10 rst features with an AUC greater than 0.74 and signicantly small t-test values (< 10E -5) (Table 2).

We compare this subset with the four most frequent features (features whose frequency is 10 in Table 1) and we nd only one feature in common, namely m/z