In Formal Concept Analysis the classical formal context is analized taking into account only the positive information, i.e. the presence of a property in an object. Nevertheless, the non presence of a property in an object also provides a signi cant knowledge which can only be partially considered with the classical approach. In this work we have modi ed the derivation operators to allow the treatment of both, positive and negative attributes which come from respectively, the presence and absence of the properties. In this work we de ne the new operators and we prove that they are a Galois connection. Finally, we have also studied the correspondence between the formal context in the new framework and the extended concept lattice, providing new interesting properties.
Data analysis of information is a well established discipline with tools and techniques well developed to challenge the identi cation of hide patterns in the data. Data mining, and general Knowledge Discovering, helps in the decision making process using pattern recognition, clustering, association and classi cation methods. One of the popular approaches used to extract knowledge is mining the patterns of the data expressed as implications (functional dependencies in database community) or association rules.
Traditionally, implications and similar notions have been built using the
positive information, i.e. information induced by the presence of attributes in objects.
In Manilla et al. [
In the framework of formal concept analysis, some authors have proposed the
mining of implications with positive and negative attributes from the apposition
of the context and its negation (KjK) [
R. Missaoui et al. [
In [
In this work we propose a deeper study of the algebraic framework for Formal Concept Analysis taking into account positive and negative information. The rst step is to consider an extension of the classical derivation operators, proving to be Galois connection. As in the classical framework, this fact will allows to built the two usual dual concept lattices, but in this case, as we shall see, the correspondence among concept lattices and formal contexts reveal several characteristics which induce interesting properties. The main aim of this work is to establish a formal full framework which allows to develop in the future new methods and techniques dealing with positive and negative information.
In Section 2 we present the background of this work: the notions related with formal concept analysis and negative attributes. Section 3 introduces the main results which constitute the contribution of this paper. 2 2.1
In this section, the basic notions related with Formal Concept Analysis (FCA)
[
X" = fm 2 M j hg; mi 2 I for all g 2 Xg Y # = fg 2 G j hg; mi 2 I for all m 2 Y g (1) (2) X" is the subset of all attributes shared by all the objects in X and Y # is the subset of all objects that have the attributes in Y . The pair ("; #) constitutes a Galois connection between 2G and 2M and, therefore, both compositions are closure operators.
A pair of subsets hX; Y i with X G and Y M such X" = Y and Y # = X is named a formal concept. X is named the extent and Y the intent of the concept. These extents and intents coincide with closed sets wrt the closure operators because X"# = X and Y #" = Y . Thus, the set of all formal concepts is a lattice, named concept lattice, with the relation [Ref] Re exivity: If B A then ` A ! B. [Augm] Augmentation: A ! B ` A [ C ! B [ C. [Trans] Transitivity: A ! B; B ! C ` A ! C.
A set of implications is considered an implicational system for K if: an implication holds in K if and only if it can be inferred, by using Armstrong's Axioms, from .
Armstrong's axioms allow us to de ne the closure of attribute sets wrt an
implicational system (the closure of a set A is usually denoted as A+) and it
is well-known that closed sets coincide with intents. On the other hand, several
kind of implicational systems has been de ned in the literature being the most
used the so-called Duquenne-Guigues (or stem) basis [
As we have mentioned in the introduction, classical FCA only discover knowledge limited to positive attributes in the context, but it does not consider information relative to the absence of properties (attributes). Thus, the Duquenne-Guigues basis obtained from Table 1 is fe ! bc; d ! c; bc ! e; a ! bg. Moreover, the implications b ! c and b ! d do not hold in Table 1 and therefore they can not be derived from the basis by using the inference system. Nevertheless, both implications correspond with di erent situations. In the rst case, some objects have attributes b and c (e.g. objects o1 and o3) whereas another objects (e.g. o2) have the attribute b and do not have c. On the other side, in the second case, any object that has the attribute b does not have the attribute d.
A more general framework is necessary to deal with this kind of information.
In [
I o1 o2 o3 o4 a b c d
e that work we emphasized the necessity of a full development of an algebraic framework.
First, we begin with the introduction of an extended notation that allows us to consider the negation of attributes. From now on, the set of attributes is denoted by M , and its elements by the letter m, possibly with subindexes. That is, the lowercase character m is reserved for positive attributes. We use m to denote the negation of the attribute m and M to denote the set fm j m 2 M g whose elements will be named negative attributes.
Arbitrary elements in M [ M are going to be denoted by the rst letters in the alphabet: a, b, c, etc. and a denotes the opposite of a. That is, the symbol a could represent a positive or a negative attribute and, if a = m 2 M then a = m and if a = m 2 M then a = m.
Capital letters A, B, C,. . . denote subsets of M [ M . If A M [ M , then A denotes the set of the opposite of attributes fa j a 2 Ag and the following sets are de ned: { Pos(A) = fm 2 M j m 2 Ag { Neg(A) = fm 2 M j m 2 Ag { Tot(A) = Pos(A) [ Neg(A) Note that Pos(A); Neg(A); Tot(A) M .
Once we have introduced the notation, we are going to summarize some
results concerning the mining of knowledge from contexts in terms of implications
with negative and positive attributes [
In our opinion, a deeper study was done by R. Missaoui et al. in [
In [
First, we extend the de nitions of derivation operators, formal concept and attribute implication.
De nition 1. Let K = hG; M; Ii be a formal context. We de ne the operators *: 2G ! 2M[M and +: 2M[M ! 2G as follows: for X G and Y M [ M , X* = fm 2 M j hg; mi 2 I for all g 2 Xg
[ fm 2 M j hg; mi 62 I for all g 2 Xg Y + = fg 2 G j hg; mi 2 I for all m 2 Y g \ fg 2 G j hg; mi 62 I for all m 2 Y g (4) (5) De nition 2. Let K = hG; M; Ii be a formal context. A mixed formal concept in K is a pair of subsets hX; Y i with X G and Y M [ M such X* = Y and Y + = X.
De nition 3. Let K = hG; M; Ii be a formal context and let A; B M [ M , the context K satis es a mixed attribute implication A ! B, denoted by K j= A ! B, if A+ B+.
For example, in Table 1, as we previously mentioned, two di erent situations were presented. Thus, in this new framework we have that K 6j= b ! d and K j= b ! d whereas K 6j= b ! c either K 6j= b ! c.
Now, we are going to introduce the mining method for mixed attribute
implications. The method is strongly based on the set of inference rules built by
supplementing Armstrong's axioms with the following ones, introduced in [
The closure of an attribute set A wrt a set of mixed attribute implications , denoted as A++, is de ned as the biggest set such that A ! A++ can be inferred from by using Armstrong's Axioms plus [Cont] and [Rft]. Therefore, a mixed implication A ! B can be inferred from if and only if B is a subset of the closure of A, i.e. B A++.
The proposed mining method, depicted in Algorithm 1, uses the inference
rules in such a way that it is not centered around the notion of key, but it
extends, in a proper manner, the classical NextClosure algorithm [
Algorithm 1: Mixed Implications Mining
Data: K = hG; M; Ii Result: set of implications begin
:= ?; Y := ?; while Y < M do foreach X Y do
A := (Y r X) [ X; if Closed(A, ) then
C := A+*; if A 6= C then :=
[ fA ! C r Ag
Y := Next(Y ) // i.e. successor of Y in the lectic order return end
The algorithm to calculate the mixed implicational system doesn't need to exhaustive traverse all the subsets of mixed attributes, but only those ones that are closed w.r.t. the set of implications previously computed. The Closed function is de ned having linear cost and is used to discern when a set of attributes is not closed and thus, the context is not visited in this case.
Function Closed(A, ): boolean
Data: A M [ M with Pos(A)\Neg(A) = ? and being a set of mixed implications.
Result: `true' if A is closed wrt or `false' otherwise.
begin foreach B ! C 2 do if B A and C * A then exit and return false if B r A = fag,
A \ C 6= ?, and a 62 A then exit and return false return true end 3
As we have mentioned, the goal of this paper is to develop a deep study of the generalized algebraic framework. In this section we are going to introduce the main results of this paper providing the properties of the generalized concept lattice. The main pillar of our new framework are the two derivation operators introduced in Equations 4 and 5. The following theorem ensures that the pair of these operators is a Galois connection: Theorem 1. Let K = hG; M; Ii be a formal context. The pair of derivation operators (*; +) introduced in De nition 1 is a Galois Connection. Proof. We need to prove that, for all subsets X G and Y
M [ M , X
Y + if and only if Y
X* First, assume X
Y +. For all a 2 Y , we distinguish two cases: 1. If a 2 Pos(Y ), exists m 2 M with a = m and, for all g 2 X, since X hg; mi 2 I and therefore a = m 2 X*. 2. If a 2 Neg(Y ), exits m 2 M with a = m and, for all g 2 X, since X hg; mi 62 I and therefore a = m 2 X*.
Conversely, assume Y X* and g 2 X. To ensure that g 2 Y +, we need to prove that hg; ai 2 I for all a 2 Pos(Y ) and hg; ai 2= I for all a 2 Neg(Y ), which is straightforward from Y X*. tu
Therefore, above theorem ensures that * + and + * are closure operators. Furthermore, as in the classical case, both closure operators provide two dually isomorphic lattices. We denote by B](G; M; I) to the lattice of mixed concepts with the relation Moreover, as in the classical FCA, mixed implications and mixed concept lattice make up the two sides of the same coin, i.e. the information mined from the mixed formal context may be dually represented by means of a set of mixed attribute implications or a mixed concept lattice.
As we shall see later in this section, unlike the classical FCA, mixed concept lattices are restricted to an speci c lattice subclass. There exist speci c properties that lattices may observe to be considered a valid lattice structure which corresponds to a mixed formal context. In fact, this is one of the main goal of this paper, the characterization of the lattices in the mixed formal concept analysis.
In Table 3 six di erent lattices are depicted. In the classical framework, all of them may be associated with formal contexts, i.e. in the classical framework any lattice corresponds with a collection of formal context. Nevertheless, in the mixed attribute framework this property does not hold anymore. Thus, in Table 3, as we shall prove later in this paper, lattices 3 and 5 cannot be associated with a mixed formal context.
The following two de nitions characterizes two kind of signi cant sets of attributes that will be used later: Y +, Y +, De nition 4. Let K = hG; M; Ii be a formal context. A set A named consistent set if Pos(A) \ Neg(A) = ?.
The set of consistent sets are going to be denoted by Ctts, i.e.
M [ M is Ctts = fA
M [ M j Pos(A) \ Neg(A) = ?g If A 2 Ctts then jAj jM j and, in the particular case where jAj = jM j, we have Tot(A) = M . This situation induces the notion of full set:
Lattice 1
Lattice 2
Lattice 3 Lattice 4
Lattice 5
Lattice 6 De nition 5. Let K = hG; M; Ii be a formal context. A set A to be full consistent set if A 2 Ctts and Tot(A) = M . The following lemma, which characterize the boundary cases, is straightforward from De nition 1.
Lemma 1. Let K = hG; M; Ii be a formal context. Then ?* = M [ M , ?+ = G and (M [ M )+ = ?.
In the classical framework, the concept lattice B(G; M; I) is bounded by hM #; M i and hG; G"i. However, in this generalized framework, as a direct consequence from above lemma, the lower and upper bounds of B](G; M; I) are h?; M [ M i and hG; G*i respectively.
Lemma 2. Let K = hG; M; Ii be a formal context. The following properties hold: 1. For all g 2 G, fgg* is a full consistent set. 2. For all g1; g2 2 G, if g1 2 fg2g*+ then fg1g* = fg2g*. 1 3. For all X G, X* = Tg2X fgg*.
Proof. 1. It is obvious because, for all m 2 M , hg; mi 2 I or hg; mi 2= I and fgg* = fm 2 M j hg; mi 2 Ig [ fm 2 M j hg; mi 2= Ig being a disjoint union.
Thus, Tot(fgg*) = M and Pos(fgg*) \ Neg(fgg*) = ?. 1 That is, g1 and g2 have exactly the same attributes. 2. Since (*; +) is a Galois connection, g1 2 fg2g*+ (i.e. fg1g fg2g*+) implies fg2g* fg1g*. Moreover, by item 1, both fg1g* and fg2g* are full consistent and, therefore, fg1g* = fg2g*. 3. In the same way that occurs in the classical framework, since (*; +) is a Galois connection between (2G; ) and (2M[M ; ), for any X G, we have that X* = Sg2X fgg * = Tg2X fgg*. tu The above elementary lemmas lead to the following theorem emphasizing a signi cant di erence with respect to the classical construction and it focuses on how the inclusion of new objects in uences the structure of mixed concept lattice. Theorem 2. Let K = hG; M; Ii be a formal context, g0 be a new object, i.e. g0 2= G, and Y M be the set of attributes that g0 satis es. Then, there exists g 2 G such that fgg* = fg0g* if and only if there exists an isomorphism between B](G; M; I) and B](G [ fg0g; M; I [ fhg0; mi j m 2 Y g).
That is, if a new di erent object (an object that di ers at least in one attribute from each object in the context) is added to the formal context then the mixed concept lattice changes.
Proof. Obviously, if there exists g 2 G such that fgg* = fg0g*, from Lemma 2 g and g0 have exactly the same attributes, and moreover the lattices B](G; M; I) and B](G [ fg0g; M; I [ fhg0; mi j m 2 Y g) are isomorphic.
Conversely, if the mixed concept lattices are isomorphic, there exists X G such that the closed set X* in B](G; M; I) coincides with fg0g*. Thus, in the mixed concept lattice B](G [ fg0g; M; I [ fhg0; mi j m 2 Xg), by Lemma 2, we have that fg0g* = X* = \g2X fgg*. Moreover, since fg0g* is a full consistent set, X 6= ? because of, by Lemma 1, ?* = M [ M . Therefore, for all g 2 X (there exists at least one g 2 X), g0 2 fgg* and, by Lemma 2, fgg* = fg0g*. tu Example 1. Let K1 = (fg1; g2g; fa; b; cg; I1) and K2 = (fg1; g2; g3g; fa; b; cg; I2) be formal contexts where I1 and I2 are the binary relations depicted in Table 4. Note that K2 is built from K1 by adding the new object g3. In the classical frameI1 g1 g2 a b c
I2 g1 g2 g3 a b c work, the concept lattices B(fg1; g2g; fa; b; cg; I1) and B(fg1; g2; g3g; fa; b; cg; I2) are isomorphic. See Figure 1.
However, the lattices of mixed concepts cannot be isomorphic because the new object g3 is not a repetition of one existing object. See Figure 2.
The following theorem characterizes the atoms of the new concept lattice B].
<g1g2g3,a> <g1,ac> <g2,ab> <g1,ac>
<g2,ab> <⦰,abc>
<⦰,abc> B(fg1; g2g; fa; b; cg; I1)
B(fg1; g2; g3g; fa; b; cg; I2) Theorem 3. Let K = hG; M; Ii be a formal context. The set of atoms in the lattice B](G; M; I) is fhfgg*+; fgg*i j g 2 Gg.
Proof. First, xed g0 2 G, we are going to prove that the mixed concept hfg0g*+; fg0g*i is an atom in B](G; M; I). If hX; Y i is a mixed concept such that h?; M [ M i < hX; Y i hfg0g*+; fg0g*i, then fg0g* Y = X* M [ M . By Lemma 2, fg0g* X* = Tg2X fgg*. Moreover, for all g 2 X 6= ?, by Lemma 2, both fg0g* and fgg* are full consistent sets and, since fg0g* fgg*, we have fg0g* = fgg*. Therefore, fg0g* = X* = Y and hX; Y i = hfg0g*+; fg0g*i.
Conversely, if hX; Y i is an atom in B](G; M; I), then X 6= ? and there exists g0 2 X. Since (*; +) is a Galois connection, fg0g* X* = Y and, therefore, hfg0g*+; fg0g*i hX; Y i. Finally, since hX; Y i is an atom, we have that hX; Y i = hfg0g*+; fg0g*i. tu
The following theorem establishes the characterization of the mixed concept lattice, proving that atoms and join irreducible elements are the same notions. Theorem 4. Let K = hG; M; Ii be a formal context. Any element in B](G; M; I) is _-irreducible if and only if it is an atom.
Proof. Obviously, any atom is _-irreducible. We are going to prove that any _-irreducible element belongs to fhfgg*+; fgg*i j g 2 Gg. Let hX; Y i be a _irreducible element. Then, by Lemma 2, Y = X* = Tg2X fgg*. Let X0 be the smaller set such that X0 X and Y = Tg2X0 fgg*. If X0 is a singleton, then hX; Y i 2 fhfgg*+; fgg*i j g 2 Gg.
Finally, we prove that X0 is necessarily a singleton. In other case, a bipartition of X0 in two disjoint sets Z1 and Z2 can be made satisfying Z1[Z2 = X0, Z1 6= ?, Z2 6= ? and Z1 \ Z2 6= ?. Then, Y = Tg2Z1 fgg* \ Tg2Z2 fgg* = Z1* \ Z2* and so hX; Y i = hZ1*+; Z1*i _ hZ2*+; Z2*i and Z1* 6= Y 6= Z*. However, it is not posible 2 because hX; Y i is _-irreducible. tu
As a nal end point of this study, we may conclude that unlike in the classical framework, not every concept lattice may be linked with a formal context. Thus, lattices number 3 and 5 from Table 3 cannot be associated with a mixed formal context. Both of them have one element which is not an atom but, at the same time, it is a join irreducible element in the lattice. More speci cally, there does not exists a mixed concept lattice with three elements. 4
In this work we have presented an algebraic study of a general framework to deal with negative and positive information. After considering new derivation operators we prove that they constitutes a Galois connection. The main results of the work are devoted to establish the new relation among mixed concept lattices and mixed formal concepts. Thus, the most outstanding conclusions are that: { the inclusion of a new (and di erent) object in a formal concept has a direct e ect in the structure of the lattice, producing a di erent lattice. { no any kind of lattice may be associated with a mixed formal context, which induces a restriction in the structure that mixed concept lattice may have.
Supported by grant TIN2011-28084 of the Science and Innovation Ministry of Spain, co-funded by the European Regional Development Fund (ERDF).