The formal similarity between possibility theory and formal concept analysis, made ten years ago, has suggested the introduction in the latter setting of the counterpart of possibilistic operators, which were ignored before. These new operators can be related to the basic operator of formal concept analysis by a triple use of negations on the contexts, on the set-valued arguments and on the obtained results, and lead to consider new compositions worth of interest. They enable us to complete the Guigues-Duquenne basis with rules having disjunctive conclusions. Besides, the approach can be naturally generalized to incomplete contexts and then to uncertain context where uncertainty is graded.
(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 fa1; :::; ang ! fb1; :::; bmg where a1; :::; an; b1; ::: and bm are attributes. It is considered that the underlying semantics is a conjunctive one. Indeed, by fa1; :::; ang ! fb1; :::; bmg, the interpretation “a1” and ... and “an” ! “b1” and ... and “bm” is implicitly agreed.
Recently, Dubois and Prade [
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,
2
Formal concept analysis [
The paradigm of formal concept analysis [
A X = fx 2 O j 8a 2 P (a 2 A ) xRa)g = fa 2 P j 8x 2 O (x 2 X ) xRa)g
corresponds to the set of of attributes that are satisfied by all objects in X.
X = A and A = X. X is called the extent and A the intent of the formal concept (X; A). For instance, (fClarag, fWoman, Parent, Motherg) is a formal concept of KS. The set of all formal concepts (denoted by B(O; P; R)) equipped with a partial order defined as: (X1; A1) (X2; A2) if X1 X2 (or equivalently, A2 A1) forms a complete lattice (denoted by L(O; P; R)).
An attribute implication is an expression A ! B where A and B are subsets of attributes (A; B 2 2P) 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 2 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 KS.
Man Woman Father Mother Parent
R John Maria Peter
Clara
The Galois derivation operator which is at the basis of FCA theory is the operator of
sufficiency (:) . Some time ago, Dubois and Prade [
(A) = fx 2 O j 9a 2 A; xRag — (A)N corresponds to the set of objects such that any attribute that satisfies one of them is necessarily in A.
(A)N = fx 2 O j 8a 2 P (xRa ) a 2 A)g (X) and (X)N are dually obtained.
where the derivation operators (:) , (:)N, (:) are applied to the complementary context
K (O; P; R) (where R = f(x; a) 2 O P j xRag), we will exceptionally use the explicit
notation (:) , (:)N , (:) . Given X O and X its complementary set (i.e. O n X), the
following recallsKsomeKuseful properties [
K
P1 : X P2 : X
K = (X ) = (X)N
K P3 : X1 X2 ) (X1) (X2) P4 : X ((X) )N P5 : (X1) [ (X2) = (X1 [ X2) P6 : X1 X2 ) (X1)N (X2)N
P7 : (X) = (((X) )N)
Let us also denote by N -pair, a formal pair (X; A) s.t. X = A and A = XN, 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 BN , whereas the set BN (E xt) (resp. BN (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 BN . Proposition 1. Let X 2 2O and A 2 2P, (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 P1 and P2 given in section 3.
It has been already established that the set BN with a partial order (denoted ) defined as (X1; A1) (X2; A2) if X1 X2 (or, equivalently, A1 A2) forms a complete lattice, called the N -lattice and denoted by LN . The following proposition gives the infima (greatest lower bound) and the suprema (least upper bound) for a given subset of LN . Proposition 2. The infima and suprema of a subset (X j; A j) (j an index set) of LN are given by:
V (X j; A j) = ( S X j; (( S A j) )N); j2J j2J j2J
W (X j; A j) = ( T X j; T A j). j2J j2J j2J 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 LN lattice corresponding to the formal context given in Table 1.
: 2P ! BN
A ! (A) = (A ; (A )N)
Proposition 3. Let A
P, then (A) = V (fag)
a2A Proof. A = S a is obtained directly by the definition of possibility operator, we a2A have (A) = (A ; (A )N) , (A) = ( S a ; ( S a )N) = V (fag)
a2A a2A a2A 4
We propose now to introduce disjunctive attribute implications of the form a1 _ ::: _ an 7 ! b1 _ ::: _ bm (equivalently denoted by W A 7 ! W B with A = fa1; :::; ang, (fg, fg) (fClarag, fMotherg) (fPeterg, fFatherg) (fMaria,Clarag, (fPeter,Clarag, (fJohn,Peterg, fWoman, Motherg) fFather,Mother,Parentg) fMan,Fatherg) (fMaria,Clara,Peterg, fWoman,Mother,Father,Parentg) (fJohn,Peter,Clarag, fMan,Father,Mother,Parentg) (fMaria,Clara,John,Peterg, fMan,Woman,Father,Mother,Parentg) context K (O; P; R) iff the attribute implication B 7 ! Proposition 4. The disjunctive attribute implication W A 7 !
W B is valid in formal A is valid in formal context
K A
K K ((B) )N .
K K Proof. Suppose B 7 ! A is valid in K . In logical terms, it means ^b2B:b ! ^a2A:a, which is logically equivalent to _a2Aa ! _b2Bb. Now, B 7 !
tu
on the possibility operator (:) is given hereafter.
Proposition 5. Given a formal context K (O; P; R) and A; B iff for each x 2 O, B * fxg or A fxg .
P, K j = W A 7 !
W B Formally, K j
= W A 7 ! fxg ^ ::: ^ an * fxg fies a disjunctive attribute implication W A 7 ! and B = fb1; :::; bmg). 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) satis
W 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.
W B, iff 8x 2 O; i f b1 * fxg ^ ::: ^ bm * fxg then a1 * obtained from concept lattice LN . The following proposition illustrates this. The disjunctive attribute implications that hold in a formal context K (O; P; R) can be (B ; (B )N) Proposition 6. Given a formal context K (O; P; R), K j = a !
W B iff (a ; (a )N) This means that we have to check in the concept lattice LN 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: fFather!Man, Mother!Woman, Father_Mother!Parent, Parent!Father_Motherg 5
R
f+; ; ?g. The interpretation of the relation R is as follows. Let x 2 O and attributes in A. (x; a; ?) 2 Rig where A
K
— (x; a; +) 2 R : it is known that the object x has the attribute a
— (x; a; ) 2 R : it is known that the object x does not have the attribute a
— (x; a; ?) 2 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 [
K (O; P; R ) are obtained as respective results of the two replacements. More formally:
= f(x; a)j(x; a; +) 2 Rig where A
K = fxjA
xR g is the set of objects certainly having all attributes in A
= fxjA
xR g is the set of objects possibly having all 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 hard to verify at first glance. The following theorem solves the problem. implication is certain if it is valid in each formal context K j; this condition may seem
K
B
K in B =) 9x 2 O jx 2 A K and x < B K =) A
K * BK .
K
BK .
But A 7 ! B is not certain implication =) 9 a formal context K jjx 2 A Kj and x < B
Kj =) 9 an object x possibly having all attributes in A and not having the certain attributes tu
are omitted due to space limitations. least ont formal context K j, the following theorem facilitates this determination. Proofs
K
B
K
This section also considers disjunctive attribute implications, presented in section 4, in incomplete formal context Ki. 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.
W A 7 !
W B is a certain disjunctive attribute implication in Ki iff A K B
K
W B is a possible disjunctive attribute implication in Ki iff A K
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 [
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 (?)
( ; 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 (+).
does not depend on u, and increases when v increases. Recall that AK 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.
A(K(u;v)) B(K(u;v)) . Therefore, the degree of certainty cert(A 7 ! 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 7 ! 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 W A 7 ! W B is valid in a formal context K if and only if the attribute implication B 7 ! A is valid in K . Therefore, the degree of certainty cert(B 7 ! A) is equal to the maximum value w such that B A , equivalent to B(K(u;v)) A(K(u;v)) , which is equivalently written: A(K(u;v)) ity degree is attached to attribute implication such that A the greater as u and v are greater. (K(u;v))
B (K(u;v)) (K(u;v)) . Also a possibil(K(u;v))
B(K(u;v)) which is all 7
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 [