The 13th Intl Conf on Formal Concept Analysis Formal Concept Analysis and
Applications FCA&A 2015
Nerja (Malaga), Spain
June 23{26, 2015 (an ICFCA workshop)
Proceedings of FCA&A 2015 (co-located with ICFCA 2015) c Manuel Ojeda-Aciego, Jaume Baixeries, Christian Sacarea, Editors This work is subject to copyright. All rights reserved. Reproduction or publication of this material, even partial, is allowed only with the authors' and editors' permission.
Manuel Ojeda-Aciego, aciego@uma.es Depth- rst Search for Pseudo-intents through Minimal Transversals : : : : : Alexandre Bazin Edit Operations on Lattices for MDL-based Pattern Summarization : : : : : Keisuke Otaki and Akihiro Yamamoto An Approach Towards Classifying and Navigating RDF data based on Pattern Structures : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Mehwish Alam and Amedeo Napoli Subdirect Decomposition of Contexts into Subdirectly Irreducible Factors Jean-Francois Viaud, Karell Bertet, Christophe Demko, and Rokia Missaoui Context-Dependent Deductive and Inductive Reasoning Based on Good Diagnostic Tests : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Xenia Naidenova and Vladimir Parkhomenko Concept Lattices of RDF Graphs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Jens Kotters Variability representation in product lines using concept lattices: feasibility study with descriptions from Wikipedia's product comparison matrices : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Jessie Carbonnel, Marianne Huchard, and Alain Gutierrez 1 17 33 49 65 81 93 Formal Concept Analysis (FCA) is a mathematical eld rooted in lattice and order theory which, although being of such a theoretical nature, has proved to be of interest to various applied elds such as Knowledge Discovery and Data Mining, Database Theory, Data Visualization, and many others. The 13th International Conference on Formal Concept Analysis (ICFCA) took place from the 23th to the 26th of June, 2015 in Nerja (Malaga), Spain, organized by members of the Universidad de Malaga. The International Workshop on Formal Concept Analysis and Applications (FCA&A) was organized in conjunction to ICFCA, and consisted of the seven works included in this volume. Our deepest gratitude goes to all the authors of submitted papers, the Program Committee members, and the external reviewers. Working with the e cient and capable team of local organizers was a constant pleasure. We are deeply indebted to all of them for making this conference a successful forum on FCA. Last, but not least, we are most grateful to the organizations that sponsored this event: the Universidad de Malaga, Andaluc a Tech (International Campus of Excellence), the Patronato de Turismo de la Costa del Sol and the Area de Turismo del Ayuntamiento de Nerja, all in Spain. Finally, we would like to emphasize the great help of EasyChair for making the technical duties easier. June 2015
Abstract. The enumeration of pseudo-intents is a long-standing problem in which the order plays a major role. In this paper, we present new algorithms that enumerate pseudo-intents in orders that do not necessarily respect the inclusion relation. We show that, confirming established results, this enumeration is equivalent to computing minimal transversals in hypergraphs a bounded number of times. 1
Formal concept analysis, as a field of applied mathematics, is interested in the
patterns that can be found in data taking the form of a set of objects described
by attributes. Among these patterns are the implications, relations between
attribute sets A and B representing the fact that every object described by A is
also described by B. As often with this type of relation, interest revolves around
a small, non redundant set of implications. Such a set, the Duquenne-Guigues
basis, is constructed using the notion of pseudo-intent. Indeed, computing the
Duquenne-Guigues basis, and thus all the implications in a data set, is
equivalent to enumerating all the pseudo-intents. In [
Our algorithms enumerate pseudo-intents incrementally, i.e. given a formal context and a set of previously found implications, they return a new pseudointent. In order to do this, we define new conditions under which a pseudo-intent P can be recognized using the lower covers of P in the lattice of attribute sets closed under the implications already found. This allows us to build algorithms that, instead of starting from ∅ and adding attributes to construct sets, start from > and remove attributes, resulting in a depth-first search in the lattice.
We show that both constructing and recognizing a pseudo-intent can be done
by computing a bounded number of times the minimal transversals of some
hypergraph, which makes it easy to bound the delay and isolate special, easier
cases. This result establishes a link with the proof in [
We start by recalling in Section 2 the basic definitions of FCA and results on the enumeration of pseudo-intents and minimal transversals. In Section 3, we present the definition of a recognizable pseudo-intent that we use along with the properties needed for our algorithms. Finally, Sections 4 and 5 are dedicated to the two algorithms, an example and a brief study of their delay. 2 2.1
Basics In formal concept analysis, data takes the form of a formal context. A formal context is a triple C = (O, A, R) in which O is a set of objects, A is a set of attributes and R ⊆ O × A a relation that maps attributes to objects. An object o ∈ O is said to be described by an attribute a ∈ A if (o, a) ∈ R. Together with the context, there are two ·0 operators defined as ·0 : 2O 7→ 2A ·0 : 2A 7→ 2O O0 = {a ∈ A | ∀o ∈ O, (o, a) ∈ R}
A0 = {o ∈ O | ∀a ∈ A, (o, a) ∈ R}
Their composition ·00 is a closure operator. A set of attributes A = A00 closed under ·00 is called an intent. 2.2
Implications An implication is a relation between two attribute sets A and B, noted A → B. It is said to hold in the context if and only if A0 ⊆ B0 or, in other words, if and only if every object described by A is also described by B. A set I of implications is a basis if and only if every implication that holds in the context can be derived from I using Armstrong’s rules :
B ⊆ A , A → B
A → B A ∪ C → B ∪ C , A → B, B → C
A → C
A pseudo-intent (or pseudo-closed set ) P is a set of attributes that contains
the closure of all its subsets and is not an intent. The set B = {P → P 00 | P
is a pseudo-intent} is the implication basis with the minimum cardinality and
is called the Duquenne-Guigues basis [
I(A) = A++...+ (up to saturation) A◦ = A ∪ {C | B → C ∈ I and B ⊂ A}
I−(A) = A◦◦...◦ (up to saturation)
It is known that intents are closed under both B−(·) and B(·), whereas a pseudo-intent P is closed under B−(·) and I(·) for I ⊆ B \ {P → P 00}.
An attribute set Y is said to be a generator of an attribute set X under
I(·) (resp. I−(·)) if I(Y ) = X (resp. I−(Y ) = X). It is a minimal generator
if there is no generator Z of X such that Z ⊂ Y . We will use GenI (X) to
denote the set of all minimal generators of a set X under I(·). The complexity
of computing the minimal generators of a set has been studied in [
We shall use ΦI to denote the lattice of attribute sets closed under I(·) ordered by the inclusion relation. For an attribute set A, the set of pseudointents P in I such that P ⊆ A and P 00 6⊆ A will be denoted by PI (A). 2.4
Minimal Transversals
The problem of computing minimal transversals in hypergraphs or, equivalently,
the prime conjunctive normal form of the dual of a Boolean function (otherwise
called monotone dualization), have been largely studied in the literature [
Given a hypergraph H = (E, V) where E is a set of edges and V ⊆ 2E is a set of vertices, a transversal T ⊆ E is a set of edges such that ∀V ∈ V, T ∩ V 6= ∅. A transversal is minimal if none of its subsets is a transversal. We shall use T r(V ) to denote the set of minimal transversals of a set of vertices V . For example, T r({ace, bce, cde}) = {c, e, abd}.
The problem of computing all the minimal transversals of a hypergraph can
be solved in quasi-polynomial total time [
In this work, we cannot presuppose the nature of the hypergraph and so we
are interested in the general case. The problem still being actively studied, we
will suppose that we have a blackbox algorithm nextTrans that enumerates
the minimal transversals of a set of vertices X. We suppose, for ease of writing,
that the transversals Ti this algorithm enumerates in some arbitrary order T1 <
T2 < ... < Tn with nextTrans(Ti, X) = Ti+1 and nextTrans(Tn, X) = ∅.
For example, Berge Multiplication [
We know that an attribute set is a pseudo-intent if and only if it contains the
closure of all its subsets that are pseudo-intents. As for the problem of recognizing
pseudo-intents, two cases have been studied. When only a context and a set A
are provided, checking whether A is a pseudo-intent is coNP-complete [
In this paper, we are interested in enumerating pseudo-intents in orders that do not extend the inclusion and, as such, we cannot suppose that we know the closure of all the subsets of a set before attempting to recognize its pseudoclosedness. Hence, we propose to consider the problem of recognizing a pseudointent A given a context and a set of subsets of A that is not necessarily complete. Proposition 1. An attribute set A ∈ ΦI is a pseudo-intent if A 6= A00 and all its lower covers in ΦI are closed.
Proof. Let us suppose that A is not closed and that all its lower covers are closed. Let B be a lower cover of A and X be a subset of A. If B ⊂ X, then I(X) = A and X00 = A00. If X ⊆ B and X00 6⊆ B, then B cannot be closed and we have a contradiction. Therefore, X00 ⊆ B. Since the closure of every subset of A is either A00 or contained in A, the set A is a pseudo-intent.
This proposition states that some pseudo-intents can be recognized in ΦI only by looking at their lower covers. As such, when I is a subset of the DuquenneGuigues basis, a new pseudo-intent can be found by looking in ΦI for sets that only have intents as lower covers. Definition 1. A pseudo-intent that can be recognized using Proposition 1 with a set of implication I is said to be recognizable. The set of all the implications that are recognizable with I is denoted by Rec(I).
Proposition 2. ∀I ⊂ B, Rec(I) 6= ∅ Proof. Let P be minimal among pseudo-intents that are not premises of implications in I. If there is a lower cover X of P in ΦI that is not closed, then there is a set A ⊂ X in ΦI such that A → A00 holds in the context. If A00 ⊆ P , then P is not minimal. If A00 6⊆ P , then P is not a pseudo-intent. Both cases lead to contradictions so all the lower covers of P are closed and P is recognizable from I. Since we have I ⊂ B, the set of pseudo-intents that are not a premise of I is not empty, so it has minimal elements. Hence, the set of pseudo-intents that are recognizable from I is not empty if I ⊂ B.
We have that, even though some unknown pseudo-intents may not be recognizable, there are always additional recognizable pseudo-intents for any subset of the Duquenne-Guigues basis. This ensures that we are able to enumerate all the pseudo-intents with an algorithm that finds recognizable ones. Proposition 3. Let A and B be two elements of ΦI . The set B is a lower cover of A if and only if B = A \ C with C a minimal transversal of GenI (A). Proof. Let C be minimal such that ∀G ∈ GenI (A), G∩C 6= ∅. For any attribute i ∈ A \ C, the set (A \ C) ∪ {i} = A \ (C \ {i}) contains a minimal generator of A because of the minimality of C. Therefore, any B between A \ C and A is such that I(B) = A and cannot be in ΦI . Hence, A \ C is a lower cover of A.
Let B be a lower cover of A in ΦI . By definition, I(B ∪ {i}) = A for any attribute i ∈ A \ B so there is a subset C of A such that i ∈ C and (C \ {i}) ⊆ B that is a minimal generator of A.
This proposition states that the lower covers of a set can be computed from
and depend on its minimal generators. As such, the number of lower covers can be
exponential in the number of minimal generators which can itself be exponential
in the size of the attribute set [
Definition 2. For any two attribute sets A and B, we say that B is reachable from A if and only if B ⊂ A and there is an ordering x1 < x2 < ... < xn of the elements of A \ B such that, for every m < n, A \ {x1, x2, ..., xm} is not closed under I.
In other words, B is reachable from A if you can obtain B by removing attributes from A and only go through sets that are not closed under I. Evidently, minimal reachable sets are elements of ΦI .
Proposition 4. An attribute set A ∈ ΦI is a minimal recognizable pseudointent if and only if A is not an intent and all the minimal attributes sets reachable from A are intents. Algorithm 1 reachableSets(A) Proof. If A is a minimal recognizable pseudo-intent, then every subset of A in ΦI is an intent. Thus every minimal reachable set is an intent.
Let us suppose that every minimal reachable subset of A is an intent and A 6= A00. For any set X reachable from A and any attribute set P ⊆ X, if P 00 6⊂ A, then X cannot be an intent. Every minimal reachable subset of A being an intent, A contains the closure of all its subsets so it is a pseudo-intent. If P is a pseudo-intent that is not in I, subsets of A \ {i} with i ∈ P 00 \ P cannot be intents so either P or a superset of P in ΦI that is not an intent is reachable from A. Hence, A is a minimal recognizable pseudo-intent.
A minimal recognizable pseudo-intent can therefore be recognized by computing the sets of its minimal reachable subsets. These minimal reachable sets can be computed using Algorithm 1. By definition, reachable sets can be computed by removing from A attributes that play a role in the logical closure, i.e. attributes in minimal generators of pseudo-intents P ⊂ A such that P 00 6⊆ A \ X for some A \ X reachable from A. The minimal transversals T make up all the possible ways to remove minimal generators of pseudo-intents and, thus, all the sets T such that for every Y ⊂ T , A \ Y cannot be logically closed. As such, removing minimal transversals of the generators of pseudo-intents used in the logical closure of a set produces a reachable set. The set A \ T is not always logically closed so the algorithm is recursively applied until an element of ΦI is reached.
The algorithm is not optimal as some reachable sets can be computed multiple times and the sets reachable from a set A that is not an element of ΦI could be computed directly from PI (A) instead of its direct subsets. However, it is sufficient to give us an upper bound of the runtime. For each recursive call, the algorithm computes PI (A \ {i}) for every attribute i ∈ A. For each of these attributes, it then computes the minimal transversals of S There is another recursive call for each pseudo-intent founPd∈mPIis(Asi\n{gi}s)oGtehneIr(uPn)-. time is bounded by O(|A| × |I| × T ) where T is the complexity of computing the transversals.
In the rest of this paper, we will suppose that we have an algorithm nextReach that enumerates minimal reachable sets in the same fashion as nextTrans. 4
We want to incrementally compute the pseudo-intents in a formal context. In
the beginning, we only have the formal context (O, A, R) and an empty set of
implications I. The corresponding ΦI is the boolean lattice of subsets of A. In
order to find a first pseudo-intent, we can look for a recognizable set (Proposition
1) in ΦI . We know that a non-closed set contains a pseudo-intent. Thus, we can
start with A and recursively remove attributes as long as we obtain non-closed
sets. When we cannot remove attributes without obtaining an intent, the set is
a recognizable pseudo-intent and we have a first implication. This corresponds
to the algorithm presented in [
Proposition 5. nextP I(A, I) returns either A or a pseudo-intent that is not in I.
Proof. Let X be a set in ΦI . If X00 6= X, then there is a pseudo-intent P ⊆ X. If a lower cover of X is not closed, then there is a pseudo-intent X ⊂ S. The algorithm returns the first set it finds that has all its lower covers closed. If this set is not A, then it is not closed and is thus a pseudo-intent.
Algorithm 3 uses Algorithm 2 to enumerate pseudo-intents iteratively until it returns A. It is sound but not complete, as exemplified below. Algorithm 2 nextP I(A, I) Let us consider an arbitrary context for which the Duquenne-Guigues basis is {de → bde, bc → bcd, ac → abcd, be → bde, bcde → abcde}. We want to find its pseudo-intents using Algorithm 3 :
The set of implications is initially empty. We start with abcde.
It has a single minimal generator, itself. The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recursively with it.
The set bcde has a single minimal generator, itself. The first minimal transversal of Gen(bcde) is b. The set bcde \ b = cde is not an intent so we continue recursively with it.
The set cde has a single minimal generator, itself. The first minimal transversal of Gen(cde) is c. The set cde\c = de is not an intent so we continue recursively with it.
The set de has a single minimal generator, itself. The first minimal transversal of Gen(de) is d. The set de \ d = e is an intent. The second and last minimal transversal is e. The set de \ e = d is an intent. The algorithm returns de as the first pseudo-intent which gives us I = {de → bde}.
We start again with abcde. It has a single minimal generator, acde. The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recursively with it.
The set bcde has a single minimal generator, cde. The first minimal transversal of Gen(cde) is c. The set bcde \ c = bde is an intent. The second minimal transversal is d. The set bcde \ d = bce is not an intent so we continue recursively with it.
The set bce has a single minimal generator, itself. The first minimal transversal of Gen(bce) is b. The set bce \ b = ce is an intent. The second minimal transversal is c. The set bce \ c = be is not an intent so we continue recursively with it.
The set be has a single minimal generator, itself. The first minimal transversal of Gen(be) is b. The set be \ b = e is an intent. The second and last minimal transversal is e. The set be \ e = b is an intent. The algorithm returns be as the second pseudo-intent which gives us I = {de → bde, be → bde}.
We start again with abcde. It has two minimal generators, acde and abce. The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recursively with it.
The set bcde has two minimal generators, bce and cde. The first minimal transversal of Gen(cde) is c. The set bcde \ c = bde is an intent. The second minimal transversal is bd. The set bcde \ bd = ce is an intent. The third and last minimal transversal is e. The set bcde \ e = bcd is an intent. The algorithm returns bcde as the third pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde}.
We start again with abcde. It has two minimal generators, cde and bce. The first minimal transversal of Gen(abcde) is bd. The set abcde \ bd = ace is not an intent so we continue recursively with it.
The set ace has a single minimal generator, itself. The first minimal transversal of Gen(ace) is a. The set ace \ a = ce is an intent. The second minimal transversal is c. The set ace \ c = ae is an intent. The third minimal transversal is e. The set ace \ e = ac is not an intent so we continue recursively with it.
The set ac has a single minimal generator, itself. The first minimal transversal of Gen(ace) is a. The set ac \ a = c is an intent. The second and last minimal transversal is c. The set ac\c = a is intent. The algorithm returns ac as the fourth pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde, ac → abcd}.
We start again with abcde. It has three minimal generators, ace, cde and bce. The first minimal transversal of Gen(abcde) is c. The set abcde \ c = abde is an intent. The second minimal transversal is e. The set abcde \ e = abcd is an intent. The third and last minimal transversal is abd. The set abcde \ abd = ce is an intent. The algorithm ends.
The algorithm has found four pseudo-intents but is unable to find the set bc when considering the minimal transversals, and thus the sets, in that particular order. Indeed, knowing be → bde and de → bde makes bcde recognizable and blocks every path from abcde to bc in ΦI . Finding bc before either de or be solves the problem. The nature of Algorithm 2 makes it easy to bound the delay between finding two pseudo-intents. As the algorithm starts from A and removes attributes until it ends, it performs a maximum of |A| recursive calls before finding a pseudointent. In a call, three different tasks are performed : computing the closure of a set, computing the set of minimal generators and computing the set of all lower covers. The closure of a set is known to be computable in polynomial time. Computing GenI (A) is done in time polynomial in the size of the output. The computation of all the lower covers of A, as we have seen in Section 2.4, can be performed in quasi-polynomial total time, i.e. in time quasi-polynomial in the size of n = |GenI (A)| and m = |T r(GenI (A))| (note that the size of m itself is n bounded by n [18]). Hence, the delay is in O(|A| × (C + G + T )) with C 2 the complexity of computing a closure, G the complexity of computing minimal generators and T the complexity of computing the lower covers. Algorithm 4 nextM inP I(A, I)
An interesting point of detail is that the algorithm does not necessarily enumerate all the intents. When all the upper covers of an intent A in ΦI are intents themselves, A cannot be reached by the algorithm anymore. In particular, if A ∪ {i} = (A ∪ {i})00 for every i ∈ A \ A, we are sure that A will never be considered. In the previous example (see Figure 3), we see that the intents abd, ab, ad, bd, de and ∅ are never considered because they do not appear as lower covers of sets. We suppose that this property helps reduce the runtime on dense contexts with a high number of intents.
The problem with Algorithm 3 is that there are some pseudo-intents it cannot compute. Among those leftover pseudo-intents, there is necessarily at least one that is minimal. We have shown in Proposition 4 that a minimal recognizable pseudo-intent P can be recognized through the minimal sets reachable from P . Those reachable sets can themselves be obtained by computing the transversals of the sets of minimal generators of the pseudo-intents involved in the logical closure of the different P \ {i} (Algorithm 1). Algorithm 4 uses these properties to compute a minimal recognizable pseudo-intent. In a manner similar to that of Algorithm 2, the algorithm starts with A and enumerates the minimal reachable sets. Once one that is not an intent is found, the algorithm is recursively applied. The algorithm ends when it finds a set with only intents as minimal reachable sets. The main difference between Algorithm 2 and Algorithm 4 is that the former performs a depth-first search in the lattice ΦI while the latter performs it in the directed graph in which the nodes are the elements of ΦI and the edges are the pairs in the “reachable” relation.
Proposition 6. Algorithm 4 returns either A or a minimal pseudo-intent that is not in I. loves * L A loves loves *
A
L R L loves * A
L A loves loves
A
L loves dislikes loves
A
M R F L T L
R hates
loves loves loves subj said A
pred obj likes * L M
A F
T loves said pred
subj obj
loves dislikes * A
M loves pred obj
subj said Man loves
F T
M * dislikes dislikes subj said loves T F
Man
R F T L F T pred obj
L R A F T L R FT
L F R T A M loves loves
A L
M * A
M loves
said L M
A F likes pred obj
subj likes
pred obj lobscouse
Sailor jested type type subj
F loves loves dislikes dislikes
M
T
Gentleman Englishman
pred subj type said name name obj "Tom"
Fig. 6. Concepts of the RDF graph glue node’s counterpart in the lower graph can be identified by its extent). To put this differently: in every triple graph, the asterisk concepts are part of the description of the non-asterisk concepts, but not vice versa.
The extent of a concept reveals how its pattern intent can be obtained.
Consider for example the concept with extension {R, F, T }, which is part of the
top left triple graph. The extension tells us that the pattern intent is the (core
graph of the) component of the pattern product (R, G2)×(F, G1)×(T, G1), which
contains the vertex (R, F, T ), and (R, F, T ) becomes the designated variable. The
diagram also shows that {R, T } is a generating set for this extent, because it
is not contained in a concept extent of the triple graph’s lower neighbors, and
so (R, G2) × (T, G1) already produces the same pattern. As was described in
[
Product patterns could also be computed directly from the triples in Turtle notation (Fig. 1), by combining triples with each other. Informally, we could write triple graphs as sets of triples (x : κ(x), p : κ(p), y : κ(y)) (borrowing from RDF and CG notation), and compute the product triples by taking suprema componentwise, like so: ∨ = (F : >, p : type, y1 : Englishman) (T : >, p : type, y2 : Gentleman) ([ FT ] : >, [ pp ] : type, [ yy12 ] : Man).
However, one would still have to identify and minimize connected components.
Note that the property and class hierarchies in our example are trees. So the attribute concepts of K are closed under suprema, and each concept label can be expressed by a single attribute. The suprema of properties may be of type ”Resource”. Such arcs are removed from the patterns; it can be shown (using the product property) that the resulting patterns can still be considered MSQs. 4
We have identified two components of the RDF graph in Fig. 1, and this corresponds to our understanding that objects are ”connected” if they contribute to the same instance of a situation. The notion of connectedness deserves closer examination, however. Let us first observe that the notion of strong connectivity is not the right one, because the second to top concepts in Fig. 6 (we might name them ”Lover” and ”Beloved”) would not have been created under this notion. But also, we can in general not rely on weak connectivity alone. If it had been stated explicitly that all persons are of type ”Person”, all persons would be connected through that class node.
Clearly, objects do not contribute to the same situation just on the basis of belonging to the same class, or having equal property values, like being of the same age. So connectedness of patterns should not rely on properties, classes or values. In this paper, no further requirements have been made, but if Liam liked lobscouse (a traditional sailors’ dish), this would have not been sufficient because all objects would be connected through the lobscouse node. From a machine perspective, there is no indication in the RDF data (or the schema) that ”ex:lobscouse” is of a different quality than ”ex:Tom” or ”ex:Mary”. A system that generates patterns from automatically acquired data without proper preprocessing would possibly generate a large number of meaningless (and unnecessarily large) concepts because of such insubstantial connections, unless it can be guaranteed that some standard for making such distinctions is applied on the level of the ontology language.
Further questions may include if and how real-world objects should be connected through objects of spoken language; on what basis we could allow a pattern like the one describing the set of all wifes older than their husband, and at the same time keep meaningless comparison of values from having an impact on concept formation; or if pattern connection should be described in terms of edges rather than nodes, and if we can classify or characterize the kind of relations which contribute to pattern formation. It seems that, when dealing with pattern concepts, questions of philosophical ontology may have (at least subjectively) measurable impact through the notion of connectedness. 5
In Sect. 2, the category theoretical framework for lattices of pattern concepts has
been applied to triple graphs, and we will now show how it is applied to simple
concept graphs. In [
In [
A datasource for the schema K~ is a power context family D~ = (D0, D1, D2, . . . ) for which the attribute implications described by Ki =: (Hi, Ni, Ji) are satisfied in Di =: (Gi, Mi, Ii), i = 0, 1, 2, . . . , and Ni ⊆ Mi holds. We can represent D~ by an abstract concept graph D = (G0, Si≥1 Gi, id, γD) with γD(u) := ((uIk ∩ Nk)Jk , uIk ∩ Nk) ∈ B(Kk) for u ∈ Gk. Let us furthermore define ExtD(κ(u)) := Ext(κ(u))JkIk for u ∈ V ∪ E. If we define a realization of G =: (V, E, κ, ν) over D as a map with ρ(u) ∈ ExtΔ(κ(u)) for all u ∈ V ∪ E and ρ(e) = (ρ(v1), . . . , ρ(vk)), we obtain that the realizations ρ of G over D are precisely the morphisms ρ : G → D. This means that product patterns for abstract concept graphs can be interpreted as MSQs, as was mentioned at the end of Sect. 1.
Triple graphs are now obtained as a special case of concept graphs: We define a power context family D~ where D0 is a supercontext of K0 which in addition contains all objects (having only the ”Resource” attribute), and where D3 = (T, ∅, ∅) represents the set of triples.
In Relational Concept Analysis, concept lattices for different kinds of
interrelated objects are generated by an iterative algorithm and, as in Fig. 6,
illustrations displaying graphs of concepts have been given [
In [
In the section on connectedness, we have seen that ontological considerations stand in a direct relation to the quality of computed concepts. As a first consequence, although the idea of treating all kinds of resources in a homogeneous way seemed appealing, triple graphs must be replaced by some other formalization which reflects the importance of the distinction between instances and classes/properties. While such questions naturally arise in the setting of pattern concepts, they seem to have no obvious analogy for standard FCA, where intents are sets of attributes. Pattern concepts have thus the potential to further and substantiate a perspective on FCA as a branch of mathematical modeling, where the entities to be modeled are not ”real world” systems but rather systems of concepts. Future work may be concerned with extensions of RDF/RDFS which support this perspective.
Jessie Carbonnel, Marianne Huchard, and Alain Gutierrez LIRMM, CNRS & Universit´e de Montpellier, France jessiecarbonnel@gmail.com surname.lastname@lirmm.fr Abstract. Several formalisms can be used to express variability in a product line. Product comparison matrix is a common and simple way to display variability of existing products from a same family, but they lack of formalisation. In this paper, we focus on concept lattices, another alternative already explored in several works to express variability. We first propose a method to translate a description from existing product comparison matrices into a concept lattice using Formal Concept Analysis. Then, we propose an approach to represent the case where a product family is described by other product families with interconnected lattices using Relational Concept Analysis. Because of the combinatorial aspect of these approaches, we evaluate the scalability of the produced structures. We show that a particular structure (AOC-poset) possesses interesting properties for the studies that we envision. 1
In product line engineering [
Among existing formalisms, the most common is Product Comparison
Matrices (PCMs). PCMs describe product properties in a tabular form. It is a simple
way to display features of products from a same family and to compare them.
However, there is no existing format or good practices to design these PCMs.
Therefore, cells in PCMs lack of formalisation and it is difficult to perform
automatic and efficient processing or analysis on them [
Formal Concept Analysis (FCA) and concept lattices have already been
studied to express variability [
Concept lattices formal and structural aspects make them good candidates to apply automatic or manual processing including product comparison, research by attributes, partial visualisation around points of interest, or decision support. But the exponential growth of the size of concept lattices can make them difficult to exploit. In this paper, we will study the dimensions of these structures and try to find out if depicting product line variability with concept lattices provides structures that can be exploited from a perspective of size. For this, we will build in a first phase concept lattices from existing descriptions. Because there are abundant and focus on both products and features, we will extract descriptions from PCMs. Besides, we can find PCMs that possess a feature whose value domain corresponds to a set of products described by another PCM. It is a special case where a product family is described by another product family. In a second phase, we will model this case by interconnecting concept lattices obtained from the descriptions of these two PCMs using Relational Concept Analysis.
In this paper, we want to answer these questions: How can we represent the variability expressed by a PCM with a concept lattice? To what extent can we model the case where a product family is described by another product family with RCA? Can we efficiently exploit structures obtained with FCA and RCA with regard to their size?
The remainder of this paper is organised as follows. In Section 2, we will review Formal Concept Analysis and propose a way to build a concept lattice from a PCM’s description. In Section 3, we will study how to represent the case where a product family is described by another product family with Relational Concept Analysis. Then, in Section 4, we will apply these two methods on Wikipedia’s PCMs to get an order of magnitude of the obtained structure size. Section 5 discusses related work. Section 6 presents conclusion and future work.
This section proposes an approach to represent with a concept lattice the variability originally expressed in a PCM.
Concept lattices and AOC-posets
Formal Concept Analysis [
A formal context is a 3-tuple (O, A, R) where O and A are two sets and R ⊆ O × A a binary relation. Elements from O are called objects and elements from A are called attributes. A pair from R states that the object o possesses the attribute a. Given a formal context K = (O, A, R), a concept is a tuple (E, I) such that E ⊆ O and I ⊆ A. It depicts a maximal set of objects that share a maximal set of common attributes. E = {o ∈ O|∀a ∈ I, (o, a) ∈ R} is the concept’s extent and I = {a ∈ A|∀o ∈ E, (o, a) ∈ R} is the concept’s intent. Given a formal context K = (O, A, R) and two concepts C1 = (E1, I1) and C2 = (E2, I2) from K, C1 ≤ C2 if and only if E1 ⊆ E2 and I2 ⊆ I1. C1 is a subconcept of C2 and C2 is a superconcept of C1. When we provide all the concepts from K with the specialisation order ≤, we obtain a lattice structure called a concept lattice.
We represent intent and extent of a concept in an optimised way by making elements appear only in the concept where they are introduced. Figure 7 represents a concept lattice having simplified intent and extent. We call object-concept and attribute-concept the concepts which introduce respectively at least an object or an attribute. In Figure 7, Concept 7 and Concept 2 introduce neither attributes nor objects: their simplified intent and extent are empty. If they are not necessary, we can choose to ignore these concepts. Attribute-Object-Concept poset (AOC-poset) from a formal context K is the sub-order of (CK ,≤) restricted to object-concepts and attribute-concepts. Figure 4 presents the AOC-poset matching the concept lattice from Figure 7. In our case, interesting properties of concept lattices with regard to variability are preserved in AOC-posets: this smaller structure can be used as an alternative to concept lattices. A PCM describes a set of products from a same family with variable features in a tabular way. Figure 1 presents a PCM which describes four products against two features, taken from Wikipedia.
We notice that the cells of this PCM lack of formalisation: in this, different values have the same meaning (Object-Oriented and OO ) and it seems that there are no rules on the use of value separator (’,’ or ’&’ or ’and’). Language Standardized Java Yes Perl No Php No C# Yes
Paradigm
Functional, Imperative, OO
Functional & Procedural & Imperative Functional, Procedural, Imperative and Object-Oriented
functional, procedural, imperative, Object Oriented Fig. 1. Excerpt of a Product Comparison Matrix on programming languages (http://en.wikipedia.org/wiki/Comparison of programming languages, July 2014)
Processing PCMs to get formal context If we want to automatically build concept lattices from this kind of descriptions, we need to make the cell values respect a format in order to extract and process them. In [17], authors identify height different types of cell values: – yes/no values that indicate if the criterion is satisfied or not, – constrained yes/no values when the criterion is satisfied under conditions, – single-value when the criterion is satisfied using this value, – multi-values when several values can satisfy the criterion, – unknown value when we do not know if the criterion is satisfied, – empty cell, – inconsistent value when the value is not related to the criterion, – extra information when the cell value offers additional informations.
We clean each type of cells as follows. Empty cells are not a problem, even though they indicate a lack of information. Inconsistent values should be detected, then clarified or erased. Unknown values and extra informations will be simply erased. Other types of cells could have either one single value or a list of values. We will always use a coma as value separator. Values with the same meanings will be written in the same way. Once we have applied these rules on a PCM, we consider that this PCM is cleaned. A cleaned PCM can own three types of features: – simple boolean, – constrained boolean, – non-boolean.
Since automatic process is difficult on original PCMs, we clean them manually. When we clean the PCM in Figure 1, we obtain the PCM in Figure 2.
We can now automatically extract values from cleaned PCMs to generate formal contexts. Given a set of objects and a set of binary attributes, a formal context is a binary relation that states which attributes are possessed by each object. In summary, we want to convert a set of multivalued features (PCM) into a set of binary attributes (formal context).
Scaling technique [
Paradigm Functional, Imperative, Object-Oriented
Functional, Procedural, Imperative Functional, Procedural, Imperative, Object-Oriented
Functional, Procedural, Imperative, Object-Oriented
Fig. 2. PCM in Figure 1 cleaned manually because of empty cells, the fact that an object does not possess an attribute could also mean that the cell from the PCM was left blank. To be more precise, we can choose to generate two attributes: one to indicate that the object possesses the feature, and one to indicate that the object does not possess the feature. Constrained boolean features can be processed in the same way than simple boolean features by producing one or two attributes, with the difference that we can keep constraints in the form of attributes. Non-boolean features will simply produce an attribute per value or group of values. We applied scaling technique on the cleaned PCM of Figure 2 and got the formal context in Figure 3. e g a u g n a
L Java x Perl Php C# x :sedY :odN teend irzead irzead iloan lrau itev i-rO tandS tandS tcnuF rceodP Ireapm jtcebO
x x x x x x x x x x x x
x x x x
Fig. 3. Formal context obtained after scaling the cleaned PCM in Figure 2 The structure of concept lattices and AOC-posets permits to highlight interesting properties from variability point of view: they classify objects depending on their attributes and emphasise relations between these attributes (e.g. require, exclude). For instance: attributes introduced in the top concept are owned by all objects; attributes which are introduced in the same concept always appear together; if an object o1 is introduced in a sub-concept of a concept introducing an object o2, o1 possesses all the attributes of o2 and other attributes; two objects introduced in the same concept possess the same attributes. Feature models show part of this information, mainly reduced to relations between attributes, as they do not include the products in the representation.
Figure 7 represents the concept lattice from the formal context of Figure 3. Figure 4 represents the AOC-poset from the formal context of Figure 3. In these two structures, we can see that: all languages permit to write programs according to functional and imperative paradigms; the product Php has all the attributes of Perl in addition to the attribute Object Oriented ; all standardised languages are object-oriented.
This section proposes an approach to model the case where a PCM possesses a feature whose value domain corresponds to a set of products described by another PCM.
Modeling interconnected families of products with RCA We illustrate the modeling of interconnected families of products with an extension of our example. We can find on Wikipedia a PCM on Wikisoftwares that refers to Programming Languages: we want to structure wikisoftwares according to programming languages in which they are written. We assume a PCM about wikisoftwares that owns a boolean feature Open Source and a constrained boolean feature Spam Prevention. We applied Section 2 approach and obtained the formal (objects-attributes) context in Figure 5. Figure 8 presents the concept lattice associated with the context in Figure 5.
Wikisoftware OS:Yes OS:No SP:Yes SP:No SP:Captcha SP:Blacklist TeamPage x x x Socialtext x MindTouch x x DokuWiki x x x EditMe x x x
Fig. 5. Objects-attributes context of Wikisoftwares
Relational Concept Analysis (RCA) [
We want to express the relation isWritten between objects of Wikisoftwares and objects of Programming languages. TeamPage and EditMe are written in Java, SocialText in Perl, DokuWiki in Php and Mindtouch in both Php and C#. We link each wikisoftware with corresponding programming languages in an objects-objects context, and we present it in Figure 6.
isWritten Java Perl Php C# TeamPage x Socialtext x MindTouch x x DokuWiki x
EditMe x Fig. 6. Objects-objects context expressing the relation between objects of Wikisoftwares and Programming languages
Processing interconnected families of products Given an objects-objects context Rj = (Ok, Ol, Ij ), there are different ways for an object from Ok domain to be in relation with a concept from Ol. For instance: an object is linked (by Ij ) to at least one object of a concept’s extent (existential scaling); an object is linked (by Ij ) only to objects of a concept’s extent (universal scaling). For each relation of R, we specify which scaling operator is used.
In RCA, objects-attributes contexts are extended according to objects-objects contexts to take into account relations between objects of different sets. For each objects-objects context Rj = (Ok, Ol, Ij ), RCA extends the objects-attributes context of the set of objects Ok by adding relational attributes according to concepts of the lattice associated with the objects-attributes Ol. Each concept c from Ol gives a relational attribute q r :c where q is a scaling operator and r is the relation between Ok and Ol. A relational attribute appears in a lattice just as the other attributes, with the difference that it can be considered like a reference to a concept from another lattice.
As shown on the example, data are represented in a Relational Context Family (RCF), which is a tuple (K, R) such that K is a set of objects-attributes contexts Ki = (Oi, Ai, Ii), 1 ≤ i ≤ n and R is a set of objects-objects contexts Rj = (Ok, Ol, Ij), 1 ≤ j ≤ m, with Ij ⊆ Ok × Ol. Given an objects-attributes context K = (O, A, I), we define rel(K) the set of relations (objects-objects contexts) of R which have O for domain, and ρ a function which associates a scaling operator to each objects-objects context of R. For each step, we extend the context K by adding relational attributes from each context of rel(K): we obtain the complete relational extension of K. When we compute the complete relational extension of each context of K, we obtain the complete relational extension of the RCF.
RCA generates a succession of contexts and lattices associated with the RCF (K, R) and ρ. In step 0, RCA generates lattices associated with contexts of K. K0 = K. In step e + 1, RCA computes complete relational extension of the Ke contexts. The obtained extended contexts (Ke+1) possess relational attributes which refer to concepts of lattices obtained in the previous step.
In our example, the RCF is composed of Wikisoftware, Programming Language and of the objects-objects context isWritten. When we compute the complete relational extension of this RCF, we extend the objects-attributes context of Wikisoftware with relational attributes which refer to each concept of Programming language. Figure 7 and Figure 8 represent lattices of Wikisoftware and Programming language at step 0. Figure 9 presents the concept lattice from the extended objects-attributes context of Wikisoftwares, at step 1. In this example, we cannot go further than step 1.
Fig. 9. Concept lattice of Wikisoftwares, step 1
In Figure 9, relational attributes are read like references to concepts in the lattice of Programming languages at step 0 (Figure 7). An extended concept lattice gives us the same kind of informations that are emphasised in a basic concept lattice, but it takes into account attributes from other product families. This brings a new dimension to research and classification of products from a same family. In our example, it permits us to select a wikisoftware depending on the paradigm of its programming language. In Figure 9, we can read for instance: – DokuWiki (concept 1) is written in a programming language characterised by concepts 6, 7, 8, 3, 5 and 0 of Programming languages, corresponding to attributes Standardized:No, Procedural, Functional, Object Oriented and Imperative; – Team Page and EditMe are equivalent products because they are introduced in the same concept (same attributes and same relational attributes); – a wikisoftware not Open Source is written in a standardised language; – an Open Source wikisoftware is written in an unstandardised language.
Until now, we proposed a first method to obtain a concept lattice from a PCM’s description and a second method to depict the case where features possess their own PCM with interconnected lattices. In this section, we evaluate these two methods on existing PCMs from Wikipedia to get an order of magnitude of the obtained structures size.
The number of generated concepts from a formal context depends on the number of objects, the number of attributes and the form of the context: this number can reach 2min(|O|,|A|) with a lattice, and |O| + |A| for an AOC-poset.
In the following tests, we generate both concept lattices and AOC-posets to emphasise the impact of deleting concepts which introduce neither attributes nor objects on the size of the structure. Each test was made twice, a first time with full formal contexts (scaling technique giving two attributes for each boolean feature, and keeping constraints in the form of attributes for constrained boolean features) and a second time with reduced fomal contexts (scaling technique giving one attribute for each boolean feature).
Scalability for non-connected PCMs (FCA) Firstly, we analysed 40 PCMs from Wikipedia without taking into account relations between products. These 40 PCMs were converted into formal contexts with the method of Section 2. Results are presented in Figure 10. We have analysed 1438 products, generated 4639 binary attributes and 26002 formal concepts.
Most of the concept lattices possess between 50 and 300 concepts, but some of them can reach about 5000 concepts: this number is very high, and it would be difficult to quickly process these data. Reduced contexts (blue plots) give smaller structures, but some of them remain considerable. Thus, results of AOC-posets are encouraging: the highest number of concepts obtained is 161. Most of them possess between 30 and 60 concepts.
Scalability for connected PCMs (RCA) Secondly, we made the same type of tests on structures which have been extended with a relation, using method of Section 3. We wanted to realise these tests on a quite important number of relationships. Yet, it is simple to find PCMs on Wikipedia but it is more difficult to automatically find relationships between these PCMs. To simulate relations between PCMs we used in the first test,
Mean Median Minimum Maximum First Quartile Third Quartile Fig. 10. Box plots on the number of concepts obtained with concept lattices (top) and AOC-poset (bottom), from full formal contexts (green) and reduced formal contexts (blue) we choose to automatically generate random objects-objects contexts based on two existing relations we found on Wikipedia. We analysed these relations and found out that about 75% of objects are linked to at least another object and that 95% of linked objects are linked to a single other object. We formed 20 pairs of objects-attributes contexts and generated object-objects contexts for each pair according to our analysis.
Results are presented in Figure 11. Concept lattices are huge (some can reach 14000 concepts) whereas AOC-poset remain relatively affordable (about 200 concepts).
These results match with the products used in a very simplified form for illustrating the approach. In real data, the first existing relation is between LinuxDistribution (77 objects, 25 features) and FileSystem (103 objects, 60 features). With a lattice, we obtain 1174 concepts (full context) and 1054 concepts (reduced context). With an AOC-poset, we obtain 188 then 179 concepts. The second relation is between Wikisoftware (43 objects, 12 features) and Programming Language (90 objects, 5 features). With a lattice, we obtain 282 concepts (full context) and 273 concepts (reduced context). With an AOCposet, we obtain 87 and then 86 concepts. All the datasets (extracted from Mean Median Minimum Maximum First Quartile Third Quartile
Lattices (F) Lattices (R) AOC-posets (F) AOC-posets (R) 2263.5 878.2 89.95 72.55 793 194 82 61.5 61 24 33 16 14083 7478 201 189 359.25 108.25 67.5 47.25 2719.5 597.75 101.25 87.25 Fig. 11. Box plots on the number of concepts obtained with formal contexts extended with RCA wikipedia and generated) are available for reproducibility purpose at: http: //www.lirmm.fr/recherche/equipes/marel/datasets/fca-and-pcm.
According to these results, we can deduce that the concept lattices obtained possess a majority of empty concepts (which introduce neither attributes nor objects): AOC-poset appears like a good alternative to generate less complex structures, and keeps variability informations in the same way that concept lattices. These results on product description datasets, that are either real datasets, or datasets generated with respect to existing real one profile, allow us to think that is is realistic to envision using FCA and RCA for variability representation within a canonical form integrating features and products. 5
To our knowledge, the first research work using Formal Concept Analysis to
analyse relationships between product configurations and variable features to
assist construction of a product line has been realised in Loesh and Ploederer
[
In the domain of product lines, another category of works is interested in
identification of features in source code using FCA [
Finally, a last category of works study feature organisation in FM with FCA.
Some approaches [
In this paper, we analyse the feasibility of using Formal Concept Analysis and Concept Lattices as a complement to Product Comparison Matrices to represent variability in product lines. We propose a method to convert a description from a product comparison matrix to a concept lattice using the scaling technique. We also propose a way to model the special case where a product family is described by another product family with Relational Concept Analysis. We obtain interconnected lattices that bring a new dimension to research and classification of products when they are in relation with other product families.
Subsequently, we realise series of tests to determine an order of magnitude of the number of concepts composing the structures obtained firstly with FCA by converting PCMs into formal contexts, and secondly with RCA by introducing relations between these contexts. In these tests, we compare two structures: concept lattices which establish a sub-order among all the concepts and AOCposets which establish a sub-order among the concepts which introduce at least an attribute or an object. It seems that most of the concepts do not introduce any information and AOC-poset appears like a more advantageous alternative, in particular for presenting information to an end-user. Concept lattices are useful too, when they are medium-size, and for automatic data manipulations. We also show the effect of two different encoding of boolean values.
In the future, we will use the work of [
8. Ganter, B., Wille, R.: Formal concept analysis - mathematical foundations.
Springer (1999) 9. Griss, M.L., Favaro, J., Alessandro, M.d.: Integrating Feature Modeling with the RSEB. In: Proceedings of the 5th International Conference on Software Reuse. pp. 76–. ICSR ’98, IEEE Computer Society, Washington, DC, USA (1998), http: //dl.acm.org/citation.cfm?id=551789.853486 10. Hac`ene, M.R., Huchard, M., Napoli, A., Valtchev, P.: Relational concept analysis: mining concept lattices from multi-relational data. Ann. Math. Artif. Intell. 67(1), 81–108 (2013) 11. Kang, K.C., Cohen, S.G., Hess, J.A., Novak, W.E., Peterson, A.S.: Feature-oriented domain analysis (foda) feasibility study (November 1990) 12. Kang, K.C., Kim, S., Lee, J., Kim, K., Shin, E., Huh, M.: Form: A feature-oriented reuse method with domain-specific reference architectures. Ann. Software Eng. 5, 143–168 (1998) 13. Loesch, F., Ploedereder, E.: Restructuring variability in software product lines using concept analysis of product configurations. In: Proc. of the 11th IEEE ECSMR. pp. 159–170 (2007) 14. Niu, N., Easterbrook, S.M.: Concept analysis for product line requirements. In:
Proc. of the 8th AOSD 2009. pp. 137–148 (2009) 15. Ryssel, U., Ploennigs, J., Kabitzsch, K.: Extraction of feature models from formal contexts. In: Proc. of ACM SPLC ’11. pp. 4:1–4:8 (2011) 16. Salman, H.E., Seriai, A., Dony, C.: Feature-to-code traceability in a collection of software variants: Combining formal concept analysis and information retrieval.
In: Proc. of the14th IEEE IRI. pp. 209–216 (2013) 17. Sannier, N., Acher, M., Baudry, B.: From comparison matrix to variability model: The wikipedia case study. In: Proc. of the 28th IEEE/ACM ASE 2013. pp. 580–585 (2013) 18. Shatnawi, A., Seriai, A.D., Sahraoui, H.: Recovering architectural variability of a family of product variants. In: To appear in Proc. of the 14th ICSR (2015) 19. Xue, Y., Xing, Z., Jarzabek, S.: Feature location in a collection of product variants.
In: Proc. of the 19th IEEE WCRE. pp. 145–154 (2012) 20. Yang, Y., Peng, X., Zhao, W.: Domain feature model recovery from multiple applications using data access semantics and formal concept analysis. In: Proc. of the 16th IEEE WCRE. pp. 215–224 (2009)