Traditionally, FCA can be used as a tool for eliciting from data a class schema in the form of either a set of attribute implications or a concept lattice. However, such a schema does not necessarily t the point of view of a domain expert for di erent reasons, e.g. noise, errors or exceptions in the data. For example, in the domain of animals, an expert may expect that the rule \mammal implies do not lay eggs" holds, while this may not be the case if the platypus is among the objects in the formal context. In this paper, we propose to bridge the possible gap between the representation model based on a concept lattice and the representation model of a domain expert. The knowledge of the expert is encoded as a set of attribute dependencies or constraints which is \aligned" with the set of implications provided by the concept lattice, leading to modi cations in the original concept lattice. The method can be generalized for generating lattices satisfying constraints based on attribute dependencies and using extensional projections. This method also allows the experts to keep a trace of the changes occurring in the original lattice and the revised version, and to assess how concepts in practice are related to concepts automatically issued from data.
Formal Concept Analysis (FCA) [
Accordingly, in this paper, we introduce a formal method for integrating
expert constraints into concept lattices in such a way that we can maintain the
lattice structure as this structure is e ective in supporting human reasoning [
In this work, we \align" a set of given attribute dependencies with the set of
implications provided by the concept lattice, leading to modi cations in the
original lattice. The method extends the de nition of dependencies between single
attributes introduced in [
The paper is organized as follows. Firstly, we introduce some basic notions that provide the foundations of our work. Next, we detail the method for generating constrained lattices, providing the trace of changes by using projections. Finally, we conclude our work and draw some perspectives over the approach. 2
In the following, we introduce some important de nitions that support our work.
Firstly, we introduce attribute implications and dependencies and secondly, we
describe projections in a concept lattice. For the following de nitions, we use
the notation of FCA in [
Attribute Implication and Dependencies
Implications in a formal context represent dependency relations between
attributes existing in data. In a nutshell, given an implication x ! y we can
understand that \all objects having x also have y". Attribute implications can
be read o directly from a formal context as stated in De nition 1.
De nition 1 (Attribute Implication [
Following De nition 1, attribute implications can be veri ed in the formal
context and in the concept lattice thanks to Propositions 1 and 2.
Proposition 1 ( [
Proposition 2 ( [
() ) 1 ) 6 m hastwolegs(m laysegsg(m)2 canfly(m3) haswinsg(m4) hasfis(nm5) hasfeatehrs( hasmilk(m7) hasbackobne livsinewat ) 9 8) (m (m er Animal bear (g1) x x x carp (g2) x x x x chicken (g3) x x x x x x crab (g4) x x dolphin (g5) x x x x x honeybee (g6) x x x penguin (g7) x x x x x x wallaby (g8) x x x
Table 1: Formal context of animals
For example, the implication m7:has milk ! m8:has backbone holds in the
formal context of Table 1. Di erent from implications, attribute dependencies do
not arise from data. They are dependency relations that experts expect to exist
as attribute implications. In the following, we provide the de nition of attribute
dependencies based on [
De nition 2 (Attribute Dependency [
De nition 3 (Formal Concept Satisfaction & Constrained Posets [
Notice that both collections are partially ordered subsets of the original
lattice L [
m3 m4
(m3’,m3’’)
(m4’,m4’’)
m4 and the trace of changes.
Projections are mathematical functions that allow mapping extents or intents in
a concept lattice into \simpler" extents or intents, called extensional or
intensional projections respectively [
De nition 4 (Extensional Projection [
Let L be a lattice, and be an extensional projection of L, then the set of extents E in L can be divided into two sets: E = fe 2 Ej (e) = eg [ fe 2 Ej (e) eg. The set fe 2 Ej (e) = eg is called the xed point of .
The mapping of a concept in a lattice onto the corresponding concept in the projected lattice can be computed thanks to Proposition 3.
Proposition 3 ([
It is worth noticing that the \projected lattice" which is the set of all projected concepts (or extents) is actually a concept lattice. For our purposes, this adds the bene t that the result of constraining a lattice through a projection preserves the lattice structure. Hereafter, we will refer to the result of constraining the lattice through a projection as a constrained lattice. 3
Projections for Generating Constrained Lattices As previously discussed, in a given formal context, there exists some implications that represent attribute dependencies among attributes. However, implications which can be checked within the concept lattice are usually not in the data. For example, some objects may have missing attribute associations or may have wrongly assigned attributes. In a di erent scenario, an expert may simply want to observe formal concepts aligned through her particular point-of-view of the domain. Thus, often there exists a disagreement between the relations of attributes in the data and the relations of attributes as a domain expert understands them. 3.1
Discussion about Constrained Lattices In order to bridge the disagreement between the representation model based on a concept lattice and the representation model as imagined by a domain expert, we \align" a set of given attribute dependencies with the set of implications provided by the concept lattice. According to De nitions 1 and 2, if an implication x ! y holds in a lattice, then that lattice satis es the attribute dependency x y. To build a lattice satisfying a set of attribute dependencies, we look for a lattice that satis es the corresponding set of attribute implications. In our setting, we want to use a well-founded process based on projections. Thus, we provide a method for projecting the lattice in such a way that the lattice structure is preserved. Moreover, we provide experts with a mapping of concepts in the original lattice onto the corresponding concepts in the revised version to make visible the changes in the lattice. We refer to these mappings as the trace of changes occurring in the original lattice and the revised version. We achieve this by using extensional projections over lattices.
We illustrate this scenario where a lattice L is mapped onto a lattice L1 which is a revised version w.r.t. the attribute dependency x y. Let us call this mapping &.
We observe the following characteristics of &: (i) & reduces the size of the
lattice L because the constrained lattice L1 do not contain formal concepts in
L which do not satisfy the constraints; (ii) In order to get formal concepts in
L satisfying the constraints, & replaces the concept extents in that lattice with
smaller sets of objects which are still extents. This replacement may result in
a loss of information. Hence, the trace of changes should be kept as it may be
useful for domain experts to be aware that some concepts in the lattice will be
lost some important objects. Indeed, (i) and (ii) are consequences of the fact
that & is an extensional projection. & is a special case of projections from [
In the following, we describe how extensional projection is de ned in two di erent cases, namely for a single attribute dependency and for a set of attribute dependencies. 3.2
Projections for Constrained Lattices w.r.t. Dependencies between Attribute Sets Let us consider the problem of nding an extensional projection : L ! L1, where L is a concept lattice which does not satisfy the implication x ! y between attributes x; y 2 M , L1 is the projected lattice of L which satis es the implication x ! y.
The following propositions state the main properties of .
Proposition 4. Let L be a concept lattice which does not satisfy the implication x ! y, then x0 6 y0 =) x0 \ y0 x0.
Proposition 5. Let L be a concept lattice which does not satisfy the implication x ! y, and be an extensional projection of L such that the projected lattice satis es x ! y, then (x0) = x0 \ y0.
Proof. see Appendix
Proposition 5 gives us an important property of to observe changes in lattice L: From lattice L which does not satisfy the implication x ! y, we are going to project x0 in lattice L to x0 \ y0 to get the projected lattice that satis es the implication x ! y. And this follows the properties of projections as (x0) = x0 \ y0 x0.
Given an extensional projection of L such that (x0) = x0 \ y0, extents A in L can be divided into three categories as shown in Fig. 2.
{ Category I contains all extents A that are subsumed by x0 \ y0, i.e. A (x0 \ y0) x0 (x0 \ y0 x0 by Proposition 4). { Category II contains all extents A that are subsumed by x0 but not subsumed by x0 \ y0, i.e. A x0, A 6 (x0 \ y0). { Category III contains extents A that are not in categories I, II, i.e. A 6 x0.
II
III
Consider an element A in Category I. As the objects in the set x0\y0 have both attributes x and y, the concept with extent x0 \ y0 in L satis es the implication x ! y. Because A is subsumed by x0 \ y0, the concept with extent A in L satis es x ! y and remains the same in the projected lattice, i.e. (A) = A. Category I is a component of the xed point of the projection .
Consider an element A in Category III. Because the objects in A do not have attribute x, the concept with extent A in L satis es the implication x ! y and remains the same in the projected lattice, i.e. (A) = A. Category III is also a component of the xed point of the projection .
Consider an element A in Category II. We have: 1) (A) A by the contractive property of projections; 2) As A x0, (A) (x0) by the monotonic property of projections. Moreover, (x0) = x0 \ y0 by Proposition 5. So, (A) x0 \ y0. As a result of 1) and 2), (A) A \ (x0 \ y0).
In order to have the largest xed point, we set (A) = A \ (x0 \ y0). (A) = A \ (x0 \ y0) complies with the properties of projections and the concept with extent (A) satis es x ! y because objects in (A) = A \ (x0 \ y0) have both attributes x and y. This introduces the fact that Category II constrains concepts which are projected in such a way that (A) = A \ (x0 \ y0).
Thus, the projection with the largest xed point given by (x0) = x0 \ y0 is: (A) =
A ( A \ (x0 \ y0) if A x0; A 6 (x0 \ y0);
Example 1. Consider the running example where the expert provides her knowledge in the form of an attribute dependency m3:can fly m4:has wings. According to the data in Table 1: m30=fg3, g5, g6g, m40=fg3, g6, g7g, m30 \ m40=fg3, g6g.
Applying Equation 2, the extensional projection for generating the constrained lattice L1 from the original lattice L is: (A) = ( A \ fg3, g6g if A
A
Fig. 1 depicts the constrained lattice and the trace of changes provided by the projection . In Fig. 1, the formal concepts of the constrained lattice are circled blue. The transformations correspond to: C4 ! C12 (fg3, g5, g6g ! fg3, g6g), C9 ! C18 (fg3, g5g ! g3), and C15 ! C19 (g5 ! ;). The other transformation fg5, g6g ! g6 does not apply as neither fg5, g6g or g6 are extents in lattice L.
An interpretation of the change C4 in L to C12 in L1 according to the semantics of the extensional projection is as follows. According to the data, objects g3:chicken, g6:honeybee are grouped together with object g5:dolphin to form concept C4 whose intent is fm3:can flyg. According to the expert, animals that can y should also have wings (can fly has wings), g5:dolphin should not be grouped together with g3:chicken and g6:honeybee to form a concept. This is better represented by concept C12 whose extent is fg3:chicken, g6:honeybeeg and intent is fm2:lays eggs, m3:can fly, m4:has wingsg. By checking this change, we found that the data contain a noisy element: dolphins can y.
Projections for Constrained Lattices w.r.t. Sets of Dependencies A \naive" way to generate a constrained lattice satisfying a set of dependencies consists in generating rst a constrained lattice for each dependency, and then getting the nal constrained lattice by the intersection of these constrained lattices. A question raised here: is there a \good" way to generate the constrained lattice? In the following, we will show that dependencies should be treated following an order of projections.
De nition 5 ([
De nition 5 states that actually projections can be ordered from \general" to \speci c". If 1 is a projection over the projected lattice of 2, then we say 1 is more speci c than 2 or 2 is more general than 1.
There is a partial order on projections of a lattice given by Proposition 6.
This proposition has been proven in [
Proposition 6 ([
The order on projections for generating constrained lattices can be characterized by Proposition 7.
Proposition 7. Let L be a concept lattice, 1 be an extensional projection of L such that the projected lattice satis es the implication X1 ! Y1, and 2 be an extensional projection of L such that the projected lattice satis es the implication X2 ! Y2, where X1; Y1; X2; Y2 M , we have: 1) If X1 2) If
X2 and Y1 Y2, then 1 2.
2, then the projected lattice given by 1
X2 ! Y2. 3) There exists an extensional projection 3 of L such that 3(L) = 1(L) \ 2(L). 3 gives the constrained lattice that satis es X1 ! Y1 and X2 ! Y2. 1 satis es X1 ! Y1 and
As a result of Proposition 7, given two dependencies between attribute sets, we can order the projections corresponding to these dependencies as follows. First, if one dependency depends on attribute sets that are included in the attribute sets of the other dependency, then the projection of that dependency is more speci c than the projection of the other. Second, if one projection is more speci c than the other, then we can use the more speci c projection for generating the nal constrained lattice . Third, we can use the projection that is the meet of the two projections for generating the nal constrained lattice.
Let us now go back to our scenario of generating a constrained lattice that satis es a set of dependencies. Let L be a concept lattice, and i be an extensional projection of L such that the projected lattice satis es an implication Xi ! Yi, where Xi; Yi M . The set of projections i can be ordered according to the order of projections given by Proposition 7. This order forms a semilattice given by Proposition 6. By Proposition 7, the projection that is the meet of the most speci c projections in this order gives the nal constrained lattice satisfying the set of implications.
According to the order of projections, we have two possible ways of generating constrained lattices. The rst way uses the meet of the most speci c projections in the order of the set of projections to generate the nal constrained lattice. The second way uses all the projections to generate a set of constrained lattices. Applying the rst or the second way to generate constrained lattices depends on what experts need. The rst way using the meet of the most speci c projections to generate the nal constrained lattice is more e cient in computation than the second way using all the projections to generate the corresponding constrained lattices. However, by using the meet of the most speci c projections to generate the nal constrained lattice, the rst way only provides the trace of changes between the original lattice and the nal constrained lattice. In the case experts need all the traces of changes, we need the second way using all the projections to generate the corresponding constrained lattices.
Example 2. Consider the running example where the expert provides her knowledge in the form of a set of dependencies di: d1) fm3, m8g d2) m3 m4, d3) fm1, m2g d4) m4 m3.
fm4g, fm3g,
Let i be the extensional projection for generating the constrained lattice satisfying dependency di, applying Equation 2, we have:
For d1 : 1(A) = ( A \ fg3g if A For d4 : 4(A) = ( A \ fg3, g6g
if A
Lattices in Figs. 3, 4, 5 and 6 depict the constrained lattices and the traces of changes provided by the projections 1, 2, 3, 4 respectively. In this set For d2 : 2(A) = ( A \ fg3, g6g
if A For d3 : 3(A) =
( A \ fg3g A A
A A fg3, g5g; A 6 fg3g;
otherwise. of projections, 2 1 and 4 3. We can see that the constrained lattice 2(L) is included in 1(L) and 4(L) is included in 3(L).
The set of projections i forms a semi-lattice as shown in Fig. 7. We have two ways of generating the nal constrained lattice. The rst way uses the meet 5 of the most speci c projections. Lattice in Fig. 8 depicts the nal constrained lattice and the trace of changes between the original lattice and the nal constrained lattice provided by the projection 5. The second way uses all the projections to have all the traces of changes. According to the semi-lattice of the projections, because 2 1 and 4 3, in order to get all the traces of changes, 1 is applied before 2 and 3 is applied before 4. By contrast, as 2 and 4 are incompatible, it does not matter if 1 and 2 or 3 and 4 are applied rst. Thus, the projections can be applied according to either the order 1, 2, 3, 4, 5 or 3, 4. 1, 2, 5. The trace of changes can be either the chain of lattices in Figs. 3, 4, 5, 6, 8 or lattices in Figs. 5, 6, 3, 4, 8. In both cases, experts still can access the changes corresponding to each dependency.
5
6 13 18
1
14
7
20
2
16
Taking into account expert knowledge in the form of dependencies between
attributes in concept lattices has been proposed by several researchers [
To conclude, in this paper, we have presented a formal method based on extensional projections for integrating expert knowledge into concept lattices in such a way that the lattice structure and the trace of changes are preserved. The expert knowledge is encoded as a set of attribute dependencies which is aligned with the set of implications provided by the concept lattice. According to the order of projections, the method o ers two ways of generating constrained lattices. The rst way uses the meet of the most speci c projections to generate the nal constrained lattice. The second way uses all the projections to generate a set of constrained lattices. The rst way is more e cient in computation, but provides only the trace of changes between the original lattice and the nal constrained lattice while the second way provides all the traces of changes, but less e cient in computation.
Currently, we are implementing the method for experiments with large datasets. Future work includes de ning intensional projections to integrate dependencies between object sets. This is useful for many applications, e.g. when classifying documents, this can be applied to integrate a partial order of documents from experts into concept lattices. Another interesting application could be to complete de nitions in data, e.g. the method presented in this paper can be applied to add implications that experts expect to exist.
Proof (Proposition 5). 1) As the projected lattice satis es the implication x ! y, ( (y0); (y0)0) ( (x0); (x0)0) (by Proposition 2). So, (x0) (y0). 2) (y0) y0 (by the contractive property of projections). 3) As a result of 1) and 2), we have (x0) (y0) y0. 4) (x0) x0 (by the contractive property of projections). 5) As a result of 3) and 4), we have (x0) x0 \ y0. 6) For any m 2 M , m0 is the maximal set of objects having m in L. Since is contractive, this is also true in the projected lattice. Thus, (x0) is the maximal set of objects having attribute x in the projected lattice L1.
As a result of 5) and 8), (x0) = x0 \ y0.
Proof (Proposition 7). ( 2(A) \ (X10 \ X20) if A 6
X20; A 6
(9) 1(A) =
2(A) 3) This follows from Proposition 6 that the set of projections F over L is a semi-lattice, then the meet 3 = 1 ^ 2 must exist.